অ্যালগোরিদম ও উপাত্ত সংগঠনসমূহ

অ্যালগোরিদম ও উপাত্ত সংগঠনসমূহ

অ্যালগোরিদম ও উপাত্ত সংগঠনসমূহ ব্যবহার করেই কম্পিউটার প্রোগ্রাম রচনা করা হয়। প্রথীতযশা কম্পিউটার বিজ্ঞানী নিকলাউস ভির্টের একটি সুবিখ্যাত বইয়ের নাম ছিল Algorithms + Data Structures = Programs (১৯৭৫)। অ্যালগোরিদম (algorithm) হল সুনির্দিষ্ট ও সসীম সংখ্যক ধাপবিশিষ্ট পদ্ধতি, যা সসীম সময়ের মধ্যে ও সসীম পরিমাণ কম্পিউটার মেমরি ব্যবহার করে কোন সমস্যার সমাধান করে। অতিব্যবহৃত অ্যালগোরিদমগুলোর মধ্যে আছে কোন উপাত্ত সংগ্রহ অনুসন্ধান (searching), উপাত্ত বিন্যস্তকরণ (sorting), মেট্রিক্স গুণন ও অন্যান্য সাংখ্যিক অপারেশনসমূহ, ইত্যাদি। কোন উপাত্ত সংগঠন (data structure) হল তথ্যের একটি নির্দিষ্ট ধরনের সুবিন্যস্ত রূপ, যা উপাত্তের বিভিন্ন মানের মধ্যে সম্পর্ক স্থাপন করে। লিস্ট, অ্যারে, রেকর্ড, স্ট্যাক, কিউ, ট্রি, ইত্যাদি কিছু বহু-ব্যবহৃত উপাত্ত সংগঠন।

অ্যালগোরিদম কম্পিউটার বিজ্ঞানের একটি মৌলিক বিষয়। কোন্‌ অ্যালগোরিদম পচ্ছন্দ করা হয়েছে এবং সেটি কীভাবে বাস্তবায়ন করা হয়েছে --- এই দুইটি বিষয় বাস্তব বিশ্বে যেকোন সফটওয়্যার ব্যবস্থার কর্মদক্ষতা নির্ধারণ করে। ভাল অ্যালগোরিদমের ডিজাইন তাই সফটওয়্যারের সাফল্যের চাবিকাঠি। তাছাড়া অ্যালগোরিদম নিয়ে গবেষণা প্রোগ্রামিং ভাষা, ঘরানা, কিংবা কম্পিউটার হার্ডওয়্যার নির্বিশেষে বিভিন্ন সমস্যার অন্তর্নিহিত প্রকৃতি বুঝতে সহায়তা করে। কম্পিউটার বিজ্ঞানের অন্যতম একটি লক্ষ্য হল কোন একটি বিশেষ উদ্দেশ্যের জন্য কোন্‌ অ্যালগোরিদমটি সবচেয়ে শক্তিশালী ও উপযোগী, কিংবা এরকম আদৌ কোন অ্যালগোরিদম আছে কি না, তা বের করা। অ্যালগোরিদমের সব ধরনের আলোচনায় তাই দক্ষতার পরিমাপের ব্যাপারটি ঘুরে ফিরে আসে।

অ্যালগোরিদম তত্ত্বের মধ্যে রয়েছে গণনাযোগ্যতার তত্ত্ব, গণনামূলক জটিলতা, তথ্য-ভিত্তিক জটিলতা, সহবর্তমানতা তত্ত্ব, সম্ভাবনাভিত্তিক অ্যালগোরিদম, আরোহী ডাটাবেস তত্ত্ব ও সাম্পর্কিক ডাটাবেস তত্ত্ব, দৈবকৃত অ্যালগোরিদম, বিন্যাস-মিলানো অ্যালগোরিদম, গ্রাফ ও নেটওয়ার্ক অ্যালগোরিদম, বীজগাণিতিক অ্যালগোরিদম, গুচ্ছবিন্যাসতাত্ত্বিক সর্বোচ্চ অনুকূলীকরণ, এবং তথ্যগুপ্তিবিদ্যা। অ্যালগোরিদম তত্ত্ব অন্যান্য যেসব জ্ঞানের শাখার ওপর ভিত্তি করে দাঁড়িয়ে আছে সেগুলো হল বিচ্ছিন্ন গণিত (যার মধ্যে পড়ে গ্রাফ তত্ত্ব, পৌনঃপুনিক ফাংশন, পুনর্ঘটন সম্পর্কসমূহ, গুচ্ছবিন্যাস তত্ত্ব), ক্যালকুলাস, আরোহী পদ্ধতি, বিধেয় যুক্তিবিজ্ঞান, সময়ভিত্তিক যুক্তিবিজ্ঞান, অর্থবিজ্ঞান, সম্ভাবনা ও পরিসংখ্যান।

জটিল অ্যালগোরিদম এবং বাস্তব অভিজ্ঞতাভিত্তিক সমস্যাগুলির ক্ষেত্রে পরীক্ষা-নিরীক্ষার সহায়তা নেয়া হয়। অ্যালগোরিদমসমূহকে টেস্ট কেসের সুইট দিয়ে মূল্যায়ন করা হয়। বিভক্তি-ও-বিজয় অ্যালগোরিদম, লোভী অ্যালগোরিদম, ডাইনামিক প্রোগ্রামিং, সসীম অবস্থার যন্ত্র ইন্টারপ্রেটার, স্ট্যাক যন্ত্র ইন্টারপ্রেটার, অভিজ্ঞতাভিত্তিক অনুসন্ধান ও দৈবকৃত অ্যালগোরিদমের আচরণ নির্ধারণে পরীক্ষা-নিরীক্ষা ব্যাপক সাহায্য করেছে। এছাড়াও পরীক্ষার মাধ্যমে সমান্তরাল ও বিতরণকৃত অ্যালগোরিদমের কর্মদক্ষতা সম্পর্কে অন্তর্দৃষ্টি লাভ করা সম্ভব হয়েছে।

অ্যালগোরিদম ও উপাত্ত সংগঠন এলাকায় আলোচিত বিষয়গুলির মধ্যে আছে:

প্রাথমিক অ্যালগোরিদম বিশ্লেষণ: জটিলতার ঊর্ধ্ব ও গড় সীমার অসীমতটীয় বিশ্লেষণ; সর্বোৎকৃষ্ট, গড় ও সর্বনিকৃষ্ট আচরণের পার্থক্য; বৃহৎ ওমেগা, ক্ষুদ্র ওমেগা, ওমেগা ও থেটা লিখনপদ্ধতি, আদর্শ জটিলতা শ্রেণীসমূহ, কর্মদক্ষতার অভিজ্ঞতাবাদী পরিমাপ, অ্যালগোরিদমের সময় ও স্থান-বিষয়ক মূল্য, পুনরাবর্ত অন্বয় ব্যবহার করে পুনরাবৃত্তিমূলক অ্যালগোরিদম বিশ্লেষণ
ব্রুট-ফোর্স অ্যালগোরিদম, লোভী অ্যালগোরিদম, বিভাজন-ও-বিজয়, পশ্চাদপসরণ, শাখায়ন-ও-বন্ধন, অভিজ্ঞতাভিত্তিক নিয়ম, বিন্যাস মিলানো অ্যালগোরিদম, স্ট্রিং অ্যালগোরিদম, সাংখ্যিক আসন্নীকরণ অ্যালগোরিদম।
সাংখ্যিক অ্যালগোরিদম, ধারাবাহিক ও বাইনারি অনুসন্ধান অ্যালগোরিদম, দ্বিঘাত সর্টিং অ্যালগোরিদম (বাছাই, অনুপ্রবেশ), O(NlogN) অ্যালগোরিদম (কুইকসর্ট, হিপসর্ট, মার্জসর্ট), হ্যাশ টেবিল (সংঘর্ষ এড়ানোর কৌশল), বাইনারি অনুসন্ধান বৃক্ষ, গ্রাফের উপস্থাপন (সংলগ্নতা তালিকা, সংলগ্নতা মেট্রিক্স), গভীরতা-ভিত্তিক ও প্রস্থ-ভিত্তিক বিচরণ, ক্ষুদ্রতম পথ অ্যালগোরিদম (ডিয়েকস্ট্রা ও ফ্লয়েডের অ্যালগোরিদসমূহ), অনুবর্তী আবদ্ধতা, সর্বনিম্ন প্রজনন বৃক্ষ (প্রিম ও ক্রুস্কালের অ্যালগোরিদমসমূহ), টপোগাণিতিক সর্ট।
বিতরণকৃত অ্যালগোরিদম, ঐকমত্য এবং নির্বাচন, সমাপ্তি নিরূপন, ত্রুটি সহনশীলতা, স্থিতিশীলকরণ।
গণনীয়তা, সসীম অবস্থা যন্ত্র, প্রসঙ্গমুক্ত ব্যাকরণ, নিয়ন্ত্রণযোগ্য ও অনিয়ন্ত্রণযোগ্য সমস্যা, অগণনীয় ফাংশন, বিরতি সমস্যা।
পি এবং এনপি শ্রেণী, এনপি-সম্পূর্ণতা, আদর্শ এনপি-সম্পূর্ণ সমস্যাসমূহ, লঘূকরণ কৌশল।
স্বয়ংক্রিয়া তত্ত্ব, নিষ্পত্তিমূলক সসীম স্বয়ক্রিয় যন্ত্র, অ-নিষ্পত্তিমূলক সসীম স্বয়ংক্রিয় যন্ত্র, নিয়মিত এক্সপ্রেশন, পাম্পিং সহায়িকা, নিম্নগামী স্বয়ংক্রিয়ক, টুরিং যন্ত্র, নিয়মিত ভাষা, চম্‌স্কি অনুক্রম, চার্চ-টুরিং বিবৃতি।
প্রাগসর অ্যালগোরিদম বিশ্লেষণ: অ্যামর্টাইজ্‌ড বিশ্লেষণ, অনলাইন ও অফলাইন অ্যালগোরিদম, দৈবকৃত অ্যালগোরিদম, ডায়নামিক প্রোগ্রামিং, গুচ্ছবিন্যাসীয় সর্বানুকূলীকরণ।
তথ্যগুপ্তিবিদ্যা-সংক্রান্ত অ্যালগোরিদম: ব্যক্তিগত-চাবি তথ্যগুপ্তি, চাবি-হস্তান্তর সমস্যা, উন্মুক্ত-চাবি তথ্যগুপ্তি, ডিজিটাল স্বাক্ষর, নিরাপত্তা প্রোটোকল, শূন্য-জ্ঞান প্রমাণ, বৈধতা নির্ণয়।
জ্যামিতিক অ্যালগোরিদম: রেখাংশের ধর্ম, ছেদ, উত্তল হাল অনুসন্ধান অ্যালগোরিদম
সমান্তরাল অ্যালগোরিদম: প্র্যাম মডেল, এক্সক্লুসিভ/কনকারেন্ট রিড/রাইট, পয়েন্টার লাফানো, ব্রেন্টের উপপাদ্য।