Essential complexity
অপরিহার্য জটিলতা একটি সংখ্যাসূচক পরিমাপ যা টমাস জে ম্যাককেব, সিনিয়র দ্বারা সংজ্ঞায়িত করা হয়েছে, তাঁর অত্যন্ত উদ্ধৃত, 1976 সালের গবেষণাপত্রে সাইক্লোম্যাটিক জটিলতা প্রবর্তনের জন্য বেশি পরিচিত। ম্যাককেব প্রয়োজনীয় জটিলতাকে সমস্ত কাঠামোগত প্রোগ্রামিং নিয়ন্ত্রণ কাঠামোকে পুনরাবৃত্তভাবে প্রতিস্থাপন (হ্রাস) করার পরে হ্রাসকৃত সিএফজি (নিয়ন্ত্রণ-প্রবাহ গ্রাফ) এর সাইক্লোম্যাটিক জটিলতা হিসাবে সংজ্ঞায়িত করেছেন, অর্থাৎ। যাদের একটি একক প্রবেশ বিন্দু এবং একটি একক প্রস্থান বিন্দু রয়েছে (উদাহরণস্বরূপ যদি-তারপর-অন্য এবং যখন লুপ) স্থানধারক একক বিবৃতি সহ। ম্যাককেবের হ্রাস প্রক্রিয়াটি নিয়ন্ত্রণ কাঠামোর ধারণাগত প্রতিস্থাপনকে (এবং তাদের প্রকৃত বিবৃতিগুলি) সাবরুটিন কলগুলির সাথে অনুকরণ করার উদ্দেশ্যে করা হয়েছে, তাই নিয়ন্ত্রণ কাঠামোগুলির জন্য একটি একক প্রবেশ এবং একটি একক প্রস্থান পয়েন্ট থাকা প্রয়োজন। (আজকাল এই ধরনের একটি প্রক্রিয়া রিফ্যাক্টরিং-এর ছত্রছায়ায় পড়ে।) সমস্ত স্ট্রাকচার্ড প্রোগ্রামের স্পষ্টতই ম্যাককেব দ্বারা সংজ্ঞায়িত 1-এর একটি অপরিহার্য জটিলতা রয়েছে কারণ তাদের সকলকে পুনরাবৃত্তিমূলকভাবে একটি শীর্ষ-স্তরের সাবরুটিনে একক কল করা যেতে পারে। ম্যাককেব তাঁর গবেষণাপত্রে যেমন ব্যাখ্যা করেছেন, তাঁর অপরিহার্য জটিলতা মেট্রিক একটি প্রদত্ত প্রোগ্রাম এই আদর্শ (সম্পূর্ণরূপে কাঠামোগত হওয়ার) থেকে কতটা দূরে ছিল তার একটি পরিমাপ প্রদান করার জন্য ডিজাইন করা হয়েছিল। সুতরাং 1 টিরও বেশি প্রয়োজনীয় জটিলতা সংখ্যা, যা শুধুমাত্র অ-কাঠামোগত প্রোগ্রামগুলির জন্য প্রাপ্ত করা যেতে পারে, ইঙ্গিত দেয় যে তারা কাঠামোগত প্রোগ্রামিং আদর্শ থেকে আরও দূরে রয়েছে। কাঠামোগত প্রোগ্রামগুলিতে হ্রাসযোগ্যতার বিভিন্ন ধারণার মধ্যে বিভ্রান্তি এড়াতে, এটি লক্ষ করা গুরুত্বপূর্ণ যে ম্যাককেবের গবেষণাপত্রটি সংক্ষেপে আলোচনা করে এবং তারপরে এস রাও কোসারাজুর 1973 সালের গবেষণাপত্রের প্রসঙ্গে কাজ করে, যা কাঠামোগত প্রোগ্রাম উপপাদ্যের একটি পরিমার্জন (বা বিকল্প দৃষ্টিভঙ্গি) দেয়। বোহম এবং জ্যাকোপিনির 1966 সালের মৌলিক গবেষণাপত্রে দেখা গেছে যে সমস্ত প্রোগ্রাম শুধুমাত্র কাঠামোগত প্রোগ্রামিং গঠন ব্যবহার করে লেখা যেতে পারে, (ওরফে ডি কাঠামোঃ ক্রম, যদি-তারপর-অন্য, এবং ওয়াইল-লুপ), তবে, একটি এলোমেলো প্রোগ্রামকে একটি কাঠামোগত প্রোগ্রামে রূপান্তর করার জন্য অতিরিক্ত ভেরিয়েবল প্রবর্তনের প্রয়োজন হতে পারে (এবং পরীক্ষায় ব্যবহৃত) এবং কিছু কোড প্রতিলিপি করা যেতে পারে। তাদের গবেষণাপত্রে, বোহম এবং জ্যাকোপিনি অনুমান করেছিলেন, তবে প্রমাণ করেননি যে নির্দিষ্ট ধরণের অ-কাঠামোগত প্রোগ্রামগুলির জন্য এই জাতীয় অতিরিক্ত ভেরিয়েবল প্রবর্তন করা প্রয়োজন ছিল যাতে সেগুলিকে কাঠামোগত প্রোগ্রামে রূপান্তরিত করা যায়। প্রোগ্রামের একটি উদাহরণ (যা আমরা এখন জানি) এর জন্য এই ধরনের অতিরিক্ত ভেরিয়েবলের প্রয়োজন হয় একটি লুপ যার ভিতরে দুটি শর্তাধীন প্রস্থান রয়েছে। বোহম এবং জ্যাকোপিনির অনুমানকে সম্বোধন করার জন্য, কোসারাজু বোহম এবং জ্যাকোপিনির দ্বারা ব্যবহৃত টুরিং সমতুল্যতার চেয়ে প্রোগ্রাম হ্রাসের আরও সীমাবদ্ধ ধারণাকে সংজ্ঞায়িত করেছিলেন। মূলত, কোসারাজুর হ্রাসের ধারণাটি এই সুস্পষ্ট প্রয়োজনীয়তা ছাড়াও আরোপ করে যে দুটি প্রোগ্রামকে অবশ্যই একই ইনপুট দেওয়া একই মান গণনা করতে হবে (বা শেষ না করে), যে দুটি প্রোগ্রামকে অবশ্যই একই আদিম ক্রিয়া এবং ভবিষ্যদ্বাণী ব্যবহার করতে হবে, পরেরটি শর্তাবলীতে ব্যবহৃত অভিব্যক্তি হিসাবে বোঝা যায়। এই বিধিনিষেধের কারণে, কোসারাজুর হ্রাস অতিরিক্ত চলকগুলির প্রবর্তনের অনুমতি দেয় না; এই চলকগুলিকে বরাদ্দ করা নতুন আদিম ক্রিয়া তৈরি করবে এবং তাদের মানগুলি পরীক্ষা করা শর্তাবলীতে ব্যবহৃত ভবিষ্যদ্বাণীগুলিকে পরিবর্তন করবে। হ্রাসের এই আরও সীমাবদ্ধ ধারণাটি ব্যবহার করে, কোসারাজু বোহম এবং জ্যাকোপিনির অনুমানকে প্রমাণ করেছিলেন, যথা দুটি প্রস্থান সহ একটি লুপকে অতিরিক্ত ভেরিয়েবল প্রবর্তন না করে একটি কাঠামোগত প্রোগ্রামে রূপান্তরিত করা যায় না, তবে আরও এগিয়ে গিয়ে প্রমাণ করেছিলেন যে বহু-স্তরের বিরতি (লুপ থেকে) ধারণকারী প্রোগ্রামগুলি একটি শ্রেণিবিন্যাস গঠন করে, যাতে কেউ সর্বদা গভীরতার এন-এর বহু-স্তরের বিরতি সহ একটি প্রোগ্রাম খুঁজে পেতে পারে যা অতিরিক্ত ভেরিয়েবল প্রবর্তন না করে আবার এন-এর চেয়ে কম গভীরতার সাথে বহু-স্তরের বিরতির প্রোগ্রামে হ্রাস করা যায় না। ম্যাককেব তাঁর গবেষণাপত্রে উল্লেখ করেছেন যে কোসারাজুর ফলাফলের পরিপ্রেক্ষিতে, তিনি তাদের নিয়ন্ত্রণ-প্রবাহ গ্রাফের পরিপ্রেক্ষিতে অ-কাঠামোগত প্রোগ্রামগুলির প্রয়োজনীয় বৈশিষ্ট্যগুলি ধরার একটি উপায় খুঁজে বের করতে চেয়েছিলেন। তিনি প্রথমে ক্ষুদ্রতম অ-কাঠামোগত প্রোগ্রামগুলির সাথে সম্পর্কিত নিয়ন্ত্রণ-প্রবাহ গ্রাফগুলি চিহ্নিত করে এগিয়ে যান (যার মধ্যে একটি লুপে শাখা করা, একটি লুপের বাইরে শাখা করা এবং তাদের যদি-তারপর-অন্য প্রতিরূপগুলি অন্তর্ভুক্ত থাকে) যা তিনি কুরাটোভস্কির উপপাদ্যের অনুরূপ একটি উপপাদ্য তৈরি করতে ব্যবহার করেন এবং তারপরে তিনি একটি প্রোগ্রামের নিয়ন্ত্রণ-প্রবাহ গ্রাফটি কাঠামোগত কিনা বা না এই প্রশ্নের হ্যাঁ/না উত্তরের পরিবর্তে একটি স্কেল উত্তর (তার কথায় "একটি প্রোগ্রামের কাঠামোর পরিমাপ") দেওয়ার জন্য প্রয়োজনীয় জটিলতার ধারণাটি প্রবর্তন করেন। পরিশেষে, সি. এফ. জি সঙ্কুচিত করার জন্য ম্যাককেবের দ্বারা ব্যবহৃত হ্রাসের ধারণাটি কোসারাজুর ফ্লোচার্ট হ্রাস করার ধারণার মতো নয়। সি. এফ. জি-তে সংজ্ঞায়িত হ্রাস প্রোগ্রামের ইনপুট সম্পর্কে জানে না বা যত্ন করে না, এটি কেবল একটি গ্রাফ রূপান্তর। উদাহরণস্বরূপ, নিম্নলিখিত সি প্রোগ্রাম খণ্ডে 1 এর একটি অপরিহার্য জটিলতা রয়েছে, কারণ অভ্যন্তরীণ যদি বিবৃতি এবং জন্য হ্রাস করা যেতে পারে, অর্থাৎ। এটি একটি কাঠামোবদ্ধ কর্মসূচি। এর জন্য (i = 0; i <3; i + +) {যদি (a [i] = = 0) b [i] + = 2;} নিম্নলিখিত সি প্রোগ্রাম খণ্ডের চারটি অপরিহার্য জটিলতা রয়েছে; এর সিএফজি অপরিবর্তনীয়। প্রোগ্রামটি z-এর প্রথম সারিটি খুঁজে পায় যা সম্পূর্ণ শূন্য এবং সেই সূচকটি i-তে রাখে; যদি কিছুই না থাকে, তবে এটি-1 কে i-তে রাখে। তবে একক-প্রবেশ এবং একক-প্রস্থান নিয়ন্ত্রণ কাঠামোর কাঠামোগত প্রোগ্রামিং থেকে ধারণাটি প্রাকৃতিক লুপের সাথে প্রতিস্থাপিত হয়, যা একটি "একক-প্রবেশ, একাধিক-প্রস্থান লুপ হিসাবে সংজ্ঞায়িত করা হয়, যার মধ্যে থেকে প্রবেশের জন্য কেবল একটি শাখা রয়েছে।" সি. এফ. জি-র যে ক্ষেত্রগুলিকে প্রাকৃতিক লুপগুলিতে হ্রাস করা যায় না সেগুলিকে অনুপযুক্ত অঞ্চল বলা হয়; এই অঞ্চলগুলির মোটামুটি সহজ সংজ্ঞা রয়েছেঃ একাধিক-প্রবেশ, সি. এফ. জি-র দৃঢ়ভাবে সংযুক্ত উপাদান। সবচেয়ে সহজ অনুপযুক্ত অঞ্চলটি হল দুটি প্রবেশ বিন্দু সহ একটি লুপ। একাধিক প্রস্থান আধুনিক সংকলকগুলিতে বিশ্লেষণ সমস্যা সৃষ্টি করে না। অনুপযুক্ত অঞ্চলগুলি (লুপগুলিতে একাধিক-প্রবেশ) কোড অপ্টিমাইজ করার ক্ষেত্রে অতিরিক্ত অসুবিধা সৃষ্টি করে। আরও দেখুন সফ্টওয়্যার ইঞ্জিনিয়ারিংয়ের ইতিহাস সিদ্ধান্ত-থেকে-সিদ্ধান্তের পথ সাইক্লোম্যাটিক জটিলতা রেফারেন্স সফ্টওয়্যার প্রকল্প পরিচালনা সফ্টওয়্যার মেট্রিক্স