Lecturer (Information and Communication Technology) বিষয় ঃ কম্পিউটার বিজ্ঞান (Computer Science)
কোডঃ ৪৩১
পূর্ণমান-১০০
Exam Duration: Three Hours
সিলেবাসঃ কাজ চলছে
Unit 2: Data Structure and Algorithm
Basics of data structure, big o notation, complexity of algorithm and time space tradeoff, pseudo code;
Array, heap, stack, queue, linked list (singly and double) recursion, trees;
Sorting algorithms (insertion sort, selection sort, bubble sort, quick sort, merge sort, radix sort, heap sort, etc.);
Factorial and tower of hanoi problem;
Searching techniques (linear and binary search); Tree traversal algorithm, greedy algorithms, graph searching, BFS, DFS;
Divide and conquer algorithms: the greedy method; dynamic programming, basic traversal & search techniques, backtracking, branch and bound.
Basics of data structure
ডাটা স্ট্রাকচার বলতে বোঝায় ডেটা যেভাবে সংগ্রহিত এবং সংরক্ষিত করা হয় এমনভাবে যাতে এটি কম্পিউটার থেকে সহজে অ্যাক্সেস করা ও পরিবর্তন করা যায়। ডাটা স্ট্রাকচারের মৌলিক ধারণাগুলি হল:
১। অ্যারে: একই ধরনের ডেটা উপাদানের সংগ্রহ যা কন্টিগিউাস মেমোরি লোকেশনে সংরক্ষিত এবং একটি ইনডেক্স ব্যবহার করে অ্যাক্সেস করা যেতে পারে।
২। লিঙ্কড লিস্ট: ডেটা উপাদানের সংগ্রহ যা একটি ক্রম মধ্যে সংরক্ষিত এবং পয়েন্টার দ্বারা সংযুক্ত করে একটি চেইন ধরনের স্ট্রাকচার তৈরি করে।
৩। স্ট্যাক: একটি ডাটা স্ট্রাকচার যা তথ্য সরবরাহ করতে এবং "শেষে আসা তথ্য প্রথমে" (LIFO) ভাবে অ্যাক্সেস করার জন্য অনুমতি দেয়।
৪। কিউ একটি ডাটা স্ট্রাকচার যা ফার্স্ট ইন ফার্স্ট আউট (FIFO) মডেলে কাজ করে। এটি ডেটা ইনসার্ট এবং ডিলিটের জন্য দুটি পয়েন্টার, হেড এবং টেইল, ব্যবহার করে। হেড পয়েন্টার একটি পয়েন্টার যা প্রথম এলিমেন্ট বা হেড অংশটি নির্দেশ করে এবং টেইল পয়েন্টার সর্বশেষ এলিমেন্ট বা টেইল অংশটি নির্দেশ করে। ডাটা ইনসার্ট করা হলে এটি টেইল এবং ডিলিট করা হলে এটি হেড পয়েন্টারের উপর সংঘটিত হয়।
৫। ট্রি: একটি হায়ারারকিয় ডাটা স্ট্রাকচার যা নোডগুলি এজ দ্বারা সংযুক্ত করে তৈরি হয়। প্রতিটি নোড ডেটা এবং তার সন্তান নোডগুলির উপর সংযুক্ত হয়।
৬। গ্রাফ: নোডগুলি বা ভার্টেক্সগুলি এজ দ্বারা সংযুক্ত এবং নির্দেশিত বা অনির্দেশিত, ওজনযুক্ত বা অওজনযুক্ত হতে পারে।
৭। হ্যাশ টেবিল: হ্যাশ ফাংশন ব্যবহার করে কীগুলি ইনডেক্স মানে ম্যাপ করতে এবং এটি খুব দ্রুত ডেটা খোঁজ এবং অ্যাক্সেস করার জন্য একটি ডাটা স্ট্রাকচার।
ডাটা স্ট্রাকচারের এই মৌলিক ধারণাগুলি বুদ্ধিমান এলগোরিদম এবং সফটওয়্যার প্রোগ্রাম উন্নয়নের জন্য গুরুত্বপূর্ণ।
big o notation,
Big O নোটেশন হলো কম্পিউটার সায়েন্সে ব্যবহৃত একটি গানিতিক নোটেশন, যা একটি ফাংশন বা অ্যালগরিদমের limiting behavior প্রদর্শন করে। এটি অ্যালগরিদমের টাইম কমপ্লেক্সিটি বা স্পেস কমপ্লেক্সিটির উপর নির্ভর করে, এবং ইনপুট সাইজ যত বাড়বে ততই বেশি কম্পিউটেশনাল রিসোর্স ব্যবহৃত হবে।
এর মাধ্যমে আমরা একটি অ্যালগরিদমের ক্ষমতা বা কর্মদক্ষতা নির্ধারণ করতে পারি, যাতে আমরা বোঝাতে পারি যে এটি বড় সংখ্যক ডেটা সেট এর সাথে কাজ করতে পারবে কিনা।
Big O নোটেশন অ্যালগরিদমগুলিকে শ্রেণীবদ্ধ করার জন্য কীভাবে তাদের রান টাইম বা স্পেসের প্রয়োজনীয়তা ইনপুটের আকার বৃদ্ধির সাথে সাথে বৃদ্ধি পায়।
complexity of algorithm
একটি অ্যালগরিদমের জটিলতা বলতে বোঝায় ইনপুট ডেটার আকার বাড়ার সাথে সাথে কোন সমস্যা সমাধানের জন্য অ্যালগরিদম দ্বারা প্রয়োজনীয় সময় এবং স্পেসের পরিমাণ ।
একটি অ্যালগরিদমের জটিলতা সাধারণত বিগ ও নোটেশন ব্যবহার করে প্রকাশ করা হয়, যা ইনপুট আকার বাড়ার সাথে সাথে অ্যালগরিদমের রানটাইম বা স্পেস ব্যবহারের বৃদ্ধির হারের উপর একটি উচ্চতর সীমাবদ্ধতা সরবরাহ করে।
অ্যালগরিদমের জটিলতার দুটি প্রধান প্রকার হ'ল
সময় জটিলতা এবং
স্থান জটিলতা।
সময় জটিলতা একটি সমস্যা সমাধানের জন্য অ্যালগরিদম দ্বারা প্রয়োজনীয় সময়ের পরিমাণ বোঝায়,
স্থান জটিলতা একটি সমস্যা সমাধানের জন্য অ্যালগরিদম দ্বারা প্রয়োজনীয় মেমরির পরিমাণ বোঝায়।
প্রায় সকল ক্ষেত্রে সময় জটিলতা এবং স্থান জটিলতা দুটোই সাধারণত কম হতে চাই। কারণ যে অ্যালগরিদম কম সময় ও কম স্থান ব্যবহার করে প্রবলেমটি সমাধান করতে পারে, সেটি অন্য অ্যালগরিদম থেকে বেশি কাজের এবং সঠিকতার দিকে উপকারী হতে পারে। তবে, একটি প্রবলেমের জন্য সেরা অ্যালগরিদম নির্ধারণ করা হলে একটি ক্ষেত্রে সময় জটিলতা উপকারী হতে পারে আর অন্য ক্ষেত্রে স্থান জটিলতা উপকারী হতে পারে।
time space tradeoff
টাইম-স্পেস ট্রেড-অফ একটি ধারণা যা সাধারণত কম্পিউটার বিজ্ঞান এবং সম্পর্কিত ক্ষেত্রগুলিতে ব্যবহৃত হয়। এটি এই বিষয় বোঝায় যে কম্পিউটারের অনেক কাজের ক্ষেত্রে কাজ সম্পন্ন করতে যে পরিমাণ সময় লাগে এবং কাজটি সম্পাদনের জন্য প্রয়োজনীয় স্থানের পরিমাণ (মেমরি বা স্টোরেজ) এর মধ্যে একটি মৌলিক ট্রেড-অফ রয়েছে।
সাধারণভাবে, টাইম-স্পেস ট্রেড-অফটি নিম্নরূপ বর্ণনা করা যেতে পারে: যদি আমাদের সীমিত পরিমাণে স্থান থাকে (উদাহরণস্বরূপ, কম্পিউটারের হার্ড ড্রাইভে), তাহলে স্থান সংরক্ষণের জন্য আমাদের কোনও কাজ সম্পাদন করতে আরও অতিরিক্ত সময় ব্যয় করতে হতে পারে (উদাহরণস্বরূপ, একটি বড় ফাইল সংকুচিত করা)। বিপরীতে, যদি আমাদের প্রচুর জায়গা উপলব্ধ থাকে তবে আমরা একই কাজটি আরও দ্রুত সম্পাদন করতে সক্ষম হতে পারি, তবে আরও মেমরি বা স্টোরেজ ব্যবহারের ব্যয়ে।
বাস্তবে, সফ্টওয়্যার সিস্টেমগুলি ডিজাইন এবং প্রয়োগ করার সময় টাইম-স্পেস ট্রেড-অফ প্রায়শই একটি মূল বিবেচনা। বিভিন্ন কাজের জন্য প্রয়োজনীয় সময় এবং স্থানের পরিমাণ সাবধানতার সাথে ভারসাম্য বজায় রেখে, ডেভেলপাররা দক্ষ, উচ্চ-কর্মক্ষমতা সিস্টেম তৈরি করতে পারে যা তাদের ব্যবহারকারীদের প্রয়োজনের জন্য উপযুক্ত।
pseudo code
সুডোকোডঃ প্রোগ্রামের ধরন ও কার্যাবলী
তুলে ধরার জন্য কিছু সংখ্যক নির্দেশ বা স্টেটমেন্টর সমাহারকে সুডোকোড বলে।
উদাহারন সরুপনিচে একটু সুডো কোড দেয়া হল
// Input: two numbers a and b
// Prompt the user to enter the first number
display "Enter the first number: "
a = read input
// Prompt the user to enter the second number
display "Enter the second number: "
b = read input
// Calculate the sum of the two numbers
sum = a + b
// Display the result to the user
Array, heap, stack, queue, linked list (singly and double) recursion, trees;
১। অ্যারে: একই ধরনের ডেটা উপাদানের সংগ্রহ যা কন্টিগিউাস মেমোরি লোকেশনে সংরক্ষিত এবং একটি ইনডেক্স ব্যবহার করে অ্যাক্সেস করা যেতে পারে।
২। লিঙ্কড লিস্ট: ডেটা উপাদানের সংগ্রহ যা একটি ক্রম মধ্যে সংরক্ষিত এবং পয়েন্টার দ্বারা সংযুক্ত করে একটি চেইন ধরনের স্ট্রাকচার তৈরি করে।
৩। স্ট্যাক: একটি ডাটা স্ট্রাকচার যা তথ্য সরবরাহ করতে এবং "শেষে আসা তথ্য প্রথমে" (LIFO) ভাবে অ্যাক্সেস করার জন্য অনুমতি দেয়।
৪। কিউ একটি ডাটা স্ট্রাকচার যা ফার্স্ট ইন ফার্স্ট আউট (FIFO) মডেলে কাজ করে। এটি ডেটা ইনসার্ট এবং ডিলিটের জন্য দুটি পয়েন্টার, হেড এবং টেইল, ব্যবহার করে। হেড পয়েন্টার একটি পয়েন্টার যা প্রথম এলিমেন্ট বা হেড অংশটি নির্দেশ করে এবং টেইল পয়েন্টার সর্বশেষ এলিমেন্ট বা টেইল অংশটি নির্দেশ করে। ডাটা ইনসার্ট করা হলে এটি টেইল এবং ডিলিট করা হলে এটি হেড পয়েন্টারের উপর সংঘটিত হয়।
৫। ট্রি: একটি হায়ারারকিয় ডাটা স্ট্রাকচার যা নোডগুলি এজ দ্বারা সংযুক্ত করে তৈরি হয়। প্রতিটি নোড ডেটা এবং তার সন্তান নোডগুলির উপর সংযুক্ত হয়।
৬। হিপ: একটি বিশেষ ধরণের গাছ-ভিত্তিক ডেটা কাঠামো যেখানে পিতামাতার নোড সর্বদা তার শিশু নোডের চেয়ে বেশি (বা কম) থাকে।
৭। পুনরাবৃত্তি recursion: একটি প্রোগ্রামিং কৌশল যেখানে একটি ফাংশন নিজেকে কল করে, সমস্যার পুনরাবৃত্তি সমাধানের অনুমতি দেয়।
Sorting algorithms (insertion sort, selection sort, bubble sort, quick sort, merge sort, radix sort, heap sort, etc.);
insertion sort
ইনসারশন সর্ট হলো এমন একটি সর্টিং এলগরিদম যা অ্যারে এর উপর কাজ করে। এই এলগরিদম মূলত দুটি ভাগে বিভক্ত হয়ে থাকে। প্রথম ভাগ হলো সর্টেড অ্যারে এবং দ্বিতীয় ভাগ হলো অনসর্টেড অ্যারে। আমরা সর্টেড অ্যারের প্রথম উপাদান হিসেবে নির্বাচন করি এবং অন্য সব উপাদান এক এক করে তার ঠিক আগে প্রবেশ করি। যদি প্রবেশ করতে হওয়া উপাদান সর্টেড অ্যারের কোনো উপাদানের চেয়ে ছোট হয় তবে তাদের স্থান পরিবর্তন করে দেওয়া হয়। এই পদক্ষেপটি প্রতিটি উপাদানের জন্য পুনরাবৃত্তি করা হয় এবং সম্পূর্ণ অ্যারে সর্টেড হওয়া পর্যন্ত এই পদক্ষেপগুলো অব্যাহত থাকে।
ইনসারশন সর্ট অ্যালগরিদমের সময়কাল খুবই বেশি অর্থাৎ স্লো হওয়ায় সাধারণত ব্যবহার করা হয় না।
একটি উদাহরণ দেখা যাক। ধরুন আমরা নিচের অ্যারেটি সর্ট করতে চাইব।
[8, 5, 2, 9, 3, 6]
আমরা শুরুতে প্রথম উপাদান 8 কে সর্টেড অ্যারে হিসেবে নির্বাচন করব। সর্টেড অ্যারে শুরুতে কোনো উপাদান নেই তাই নির্বাচিত উপাদান সর্টেড অ্যারের প্রথম উপাদান হিসেবে যোগ করে দেওয়া হবে। তাহলে আমাদের সর্টেড অ্যারে হবে [8] এখন।
এরপর আমরা দ্বিতীয় উপাদান 5 এর কাছে পৌঁছাতে যাচ্ছি। আমরা সর্টেড অ্যারেতে সবচেয়ে ডান পক্ষের উপাদান হতে চাই। তাই 8 এর সাথে 5 তুলনা করলে দেখা যাবে যে 5 হলো 8 এর চেয়ে ছোট। সুতরাং আমাদের সর্টেড অ্যারে এখন হবে [5, 8]।
এখন আমরা তৃতীয় উপাদান 2 এর দিকে চলে গেলাম। একবার আবার আমরা সর্টেড অ্যারেতে সবচেয়ে ডান পক্ষের উপাদান হতে চাই। তাই 8 এবং 5 এর সাথে 2 তুলনা করলে
2 হলো সবচেয়ে ছোট উপাদান। এখন সর্টেড অ্যারে হবে [2, 5, 8]।
তারপর আমরা চতুর্থ উপাদান 9 কে সর্টেড অ্যারের সাথে তুলনা করব। এবার আমরা সর্টেড অ্যারেতে সবচেয়ে বাম পক্ষের উপাদান হতে চাই। তাই 8 এবং 5 এর সাথে 9 তুলনা করলে দেখা যাবে যে 9 হলো 8 এবং 5 এর চেয়ে বড়। সুতরাং আমরা 9 কে সর্টেড অ্যারের সর্বশেষে যোগ করে দিলে সর্টেড অ্যারে হবে [2, 5, 8, 9]।
অনুরুপ ভাবে আমরা পাই [2,3, 5, 6,8, 9]।
selection sort
সিলেকশন সর্ট হল একটি সরলীকরণ এলগরিদম। এটি অ্যারে ব্যবহার করে কাজ করে এবং দুটি লুপ ব্যবহার করে। প্রথম লুপটি প্রতিটি ইলিমেন্ট নির্বাচন করে এবং দ্বিতীয় লুপটি সম্পর্কিত এলিমেন্টকে পরীক্ষা করে সর্বোচ্চ এলিমেন্ট নির্বাচন করে। এরপর এই সর্বোচ্চ এলিমেন্টকে প্রথম এলিমেন্টের সাথে পরিবর্তন করে এবং এই পদক্ষেপটি সম্পূর্ণ অ্যারে এর শেষ এলিমেন্ট নির্বাচন পর্যন্ত পুনরাবৃত্তি করা হয়।
এই বিন্যাসে, আমরা অ্যারে দিয়ে যেসব উন্নত অংশগুলি নির্বাচন করে সবচেয়ে ছোট তারপর অংশটি ছোট থেকে বড় সিলেক্ট করব। তারপর তার সাথে প্রথম অংশটি একসাথে পরিবর্তন করে সংখ্যাটি নিয়ে আবার শুরু করা হবে। সম্পূর্ণ অ্যারেটি সাজানো হয় যতক্ষণ না সম্পূর্ণ সংখ্যাগুলি সাজানো হয়।
একটি উদাহরণ ইনপুট হিসাবে [64, 25, 12, 22, 11] দেওয়া হলে অ্যালগোরিদমটি কিভাবে কাজ করে তা নিচে দেখানো হলো:
প্রথম অংশে যাওয়া হয়: 11 সবচেয়ে ছোট সংখ্যা তাই প্রথম অংশ (64) দিয়ে পরিবর্তন করে নতুন অ্যারে হলো [11, 25, 12, 22, 64]।
দ্বিতীয় অংশে যাওয়া হয়: 12 অ্যারের উন্নত অংশে সবচেয়ে ছোট সংখ্যা তাই দ্বিতীয় অংশ (25) দিয়ে পরিবর্তন করে নতুন অ্যারে হলো [11, 12, 25, 22, 64]।
তৃতীয় অংশে যাওয়া হয়: 22 অ্যারের উন্নত অংশে সবচেয়ে ছোট সংখ্যা তাই তৃতীয় অংশ (25) দিয়ে পরিবর্তন করে নতুন অ্যারে হলো [11, 12, 22, 25, 64]।
চতুর্থ অংশে যাওয়া হয়: 25 ইতিমধ্যে সঠিক অবস্থায় আছে তাই কোন পরিবর্তন করা হয় না, নতুন অ্যারে হলো [11, 12, 22, 25, 64]।
পঞ্চম অংশে যাওয়া হয়: 64 ইতিমধ্যে সঠিক অবস্থায় আছে তাই কোন পরিবর্তন করা হয় না, নতুন অ্যারে হলো [11, 12, 22, 25, 64]।
সাজানো অ্যারে হলো [11, 12, 22, 25, 64]।
bubble sort
বাবল সর্ট হলো একটি সর্টিং এলগোরিদম যা সমস্ত উপাদানকে দুটি দুটি পরস্পর তুলনা করে সঠিক অবস্থানে পাঠানোর চেষ্টা করে। এই এলগোরিদম মৌলিকভাবে দুটি উপাদান একসাথে নেওয়ার পর সেই উপাদান সম্পর্কে তুলনা করে তাদের সঠিক অবস্থানে পাঠায় এবং এই পদক্ষেপটি অবস্থান সঠিক না হওয়া পর্যন্ত আবার একই পদক্ষেপটি পুনরাবৃত্তি করে থাকে
এভাবে ধাপ চলতে থাকবে এবং এক সময় পর্যায় ক্রমিক ভাবে বড় সংখ্যাটি শেষে চলে যাবে এ
quick sort
কুইক সর্ট একটি জনপ্রিয় সাজানো এলগরিদম যা একটি সংখ্যার অ্যারে সাজানোর জন্য ব্যবহৃত হয়। এটি দ্বারা-বিভক্ত পদক্ষেপ ব্যবহার করে অ্যারেটি সাজানো হয়। এটি অ্যারেটি দুটি উপ-অ্যারে তৈরি করে যেটি পিভট সংখ্যার উপর ভিত্তি করে একটি সংখ্যার অ্যারেকে বিভক্ত করে। একটি উপ-অ্যারে পিভটের চেয়ে ছোট উপ-অ্যারে হবে এবং অন্যটি পিভটের চেয়ে বড় বা সমান হবে। এরপর একই পদক্ষেপ ব্যবহার করে প্রতিটি উপ-অ্যারেকে আবারও সাজানো হয়।
নিম্নলিখিত পূর্ণসংখ্যার তালিকায় দ্রুত প্রয়োগ ের একটি উদাহরণ এখানে দেওয়া হল: [5, 3, 7, 2, 8, 4, 1, 6]
পিভট হিসাবে প্রথম উপাদান, 5 চয়ন করুন।
অ্যারেটিকে দুটি উপ-অ্যারেতে বিভক্ত করুন:
[৩, ২, ৪, ১] এবং [৭, ৮, ৬]
পুনরাবৃত্তভাবে সাব-অ্যারেগুলিতে দ্রুত ধরণের প্রয়োগ করুন:
প্রথম সাব-অ্যারের জন্য, পিভট হিসাবে 3 টি চয়ন করুন, এটিকে [2, 1] এবং [4] বিভক্ত করুন, তারপরে প্রতিটি উপ-অ্যারে বাছাই করুন।
দ্বিতীয় সাব-অ্যারের জন্য, পিভট হিসাবে 7 টি চয়ন করুন, এটিকে [6] এবং [8] বিভক্ত করুন, তারপরে প্রতিটি সাব-অ্যারে বাছাই করুন।
চূড়ান্ত বাছাইকৃত অ্যারে পেতে বাছাই করা উপ-অ্যারেগুলিকে তাদের মধ্যে পিভট উপাদান দিয়ে সংজ্ঞায়িত করুন: [1, 2, 3, 4, 5, 6, 7, 8]
দ্রুত প্রকারের সময় জটিলতা গড় ক্ষেত্রে ও (এন লগ এন) হয়, তবে সবচেয়ে খারাপ ক্ষেত্রে ও (এন ^ 2) হতে পারে। যাইহোক, সবচেয়ে খারাপ কেসটি একটি ভাল পিভট চয়ন করে এড়ানো যেতে পারে, যেমন সাব-অ্যারের মধ্যবর্তী, বা একটি এলোমেলো পিভট নির্বাচন ব্যবহার করে।
merge sort
মার্জ সর্ট অ্যালগরিদমটি একটি জনপ্রিয় সর্টিং অ্যালগরিদম, যা একটি উপাদানের অ্যারেকে সাজানোর জন্য ভাগ করো এবং জয়েন করো পদ্ধতি ব্যবহার করে। এটি কাজ করে একটি অ্যারেকে ছোট উপাদানের উপশ্রেণীতে বিভক্ত করে, সেগুলি সাজিয়ে রাখে, এবং তারপর পুনরাবৃত্তি করে এবং পুনর্বিন্যাস করে উপশ্রেণীগুলি একত্রে মিলিয়ে সাজানো হয় সাজানোর জন্য বিভক্ত-এবং-জয়েন পদক্ষেপ ব্যবহার করে।
এখানে মার্জ সর্ট অ্যালগরিদমের বিস্তারিত উদাহরণ দেওয়া হয়েছে:
প্রাথমিক অ্যারে: [38, 27, 43, 3, 9, 82, 10]
পদক্ষেপ 1: অ্যারেকে দুটি ভাগে ভাগ করুন
বাম অর্ধ: [38, 27, 43, 3]
ডান অর্ধ: [9, 82, 10]
পদক্ষেপ 2: বাম অর্ধকে পুনরাবৃত্তিভূক্ত সাজান
বাম অর্ধ: [38, 27]
ডান অর্ধ: [43, 3]
বাম অর্ধ: [38, 27] -> [27, 38]
ডান অর্ধ: [43, 3] -> [3, 43]
পদক্ষেপ 3: ডান অর্ধকে পুনরাবৃত্তিভূক্ত সাজান
বাম অর্ধ: [27, 38]
ডান অর্ধ: [3, 43, 9]
পদক্ষেপ 4: বাম এবং ডান অর্ধকে পুনরাবৃত্তিভূক্ত সাজান
বাম অর্ধ: [27, 38]
ডান অর্ধ: [3, 9, 43, 82, 10]
পদক্ষেপ 5: বাম এবং ডান অর্ধকে একত্রে মেলানো এবং সাজানো হয়
সাজানো অ্যারে: [3, 9, 27, 38, 43, 82, 10]
এটি একটি সম্পূর্ণ মার্জ সর্ট সিদ্ধান্ত যা ছোট উপাদানের উপশ্রেণীতে অ্যারেকে বিভক্ত করে সাজানোর জন্য বিভক্ত-এবং-জয়েন পদক্ষেপ ব্যবহার করে।
radix sort
রেডিক্স সর্ট একটি অ্যালগরিদম যা প্রদত্ত তালিকার প্রতিটি উপাদানের সংখ্যাতুলনা করে ডেটা বাছাই করে। এটি উপাদানগুলিকে একই সংখ্যার সাথে গ্রুপ করে এবং একই বালতিতে রেখে ডেটা বাছাই করে। তারপরে এটি পরবর্তী সংখ্যার উপর ভিত্তি করে প্রতিটি বালতি বাছাই করার প্রক্রিয়াটি পুনরাবৃত্তি করে, যতক্ষণ না সমস্ত সংখ্যা বাছাই করা হয়।
রেডিক্স সর্ট অ্যালগরিদম বাস্তবায়নের জন্য এখানে ধাপে ধাপে প্রক্রিয়া রয়েছে:
ডেটা সেটের সর্বাধিক সংখ্যার সংখ্যা নির্ধারণ করুন।
প্রতিটি ডিজিট পজিশনের জন্য, ডানতম অবস্থান থেকে শুরু করে, সেই ডিজিট দ্বারা সেট করা ডেটা বাছাই করুন।
একটি নির্দিষ্ট সংখ্যা দ্বারা বাছাই করতে, একটি স্থিতিশীল সর্ট অ্যালগরিদম ব্যবহার করুন যেমন গণনা সর্ট বা বালতি সর্ট। গণনা প্রকারটি প্রায়শই ব্যবহৃত হয় কারণ এতে ও (এন) এর একটি সময় জটিলতা রয়েছে, যা এটি পৃথক সংখ্যাগুলি বাছাই করার জন্য দক্ষ করে তোলে।
একটি অঙ্ক দ্বারা বাছাই করার পরে, ফলাফলগুলি যে ক্রমঅনুসারে সাজানো হয়েছিল সেগুলিতে সামঞ্জস্য করুন।
প্রতিটি সংখ্যার অবস্থানের জন্য ধাপ 2-4 পুনরাবৃত্তি করুন, ডানতম সংখ্যা থেকে শুরু করুন।
এখানে রেডিক্স প্রকারের একটি উদাহরণ নিম্নলিখিত পূর্ণসংখ্যার তালিকায় প্রয়োগ করা হচ্ছে:
[170, 45, 75, 90, 802, 24, 2, 66]
সংখ্যার সর্বাধিক সংখ্যা 3, তাই আমরা তালিকাটি এক, দশ এবং শত শত স্থান দ্বারা বাছাই করব।
একটি জায়গা থেকে শুরু করে, আমরা গণনা সর্ট ব্যবহার করে এই সংখ্যা দ্বারা তালিকাটি বাছাই করি:
[170, 90, 802, 2, 24, 45, 75, 66]
ফলাফলগুলি একত্রিত করা আমাদের দেয় [170, 90, 802, 2, 24, 45, 75, 66]
এরপরে, আমরা দশটি স্থান দ্বারা তালিকাটি বাছাই করি:
[802, 2, 24, 45, 66, 170, 75, 90]
ফলাফলগুলি সংজ্ঞায়িত করা আমাদের দেয় [802, 2, 24, 45, 66, 170, 75, 90]
অবশেষে, আমরা শত শত স্থান দ্বারা তালিকাটি বাছাই করি:
[2, 24, 45, 66, 75, 90, 170, 802]
ফলাফল গুলি আমাদের দেয় [2, 24, 45, 66, 75, 90, 170, 802]
চূড়ান্ত ফলাফলটি হ'ল ক্রমবর্ধমান ক্রমঅনুসারে পূর্ণসংখ্যাগুলির একটি সাজানো তালিকা। রেডিক্স প্রকারের সময় জটিলতা হল O(d * (n + k)), যেখানে d হল সংখ্যার সর্বাধিক সংখ্যা, n হল উপাদানের সংখ্যা, এবং k হল প্রতিটি সংখ্যার জন্য মানগুলির পরিসীমা। রেডিক্স সর্ট একটি রৈখিক সময় অ্যালগরিদম যখন ডি একটি ধ্রুবক বা ছোট হয় এবং কে এন এর চেয়ে উল্লেখযোগ্যভাবে বড় নয়।
heap sort
হিপ সর্ট একটি তুলনা-ভিত্তিক সর্টিং অ্যালগরিদম যা একটি অ্যারেতে উপাদানগুলি বাছাই করতে বাইনারি হিপ ডেটা কাঠামো ব্যবহার করে। একটি স্তূপ একটি বাইনারি গাছ যেখানে প্রতিটি পিতামাতার নোড তার বাচ্চাদের চেয়ে বড় বা সমান (সর্বাধিক স্তূপ), বা প্রতিটি পিতামাতার নোড তার বাচ্চাদের চেয়ে কম বা সমান (মিন স্তূপ)।
হিপ সর্ট অ্যালগরিদম বাস্তবায়নের জন্য এখানে ধাপে ধাপে প্রক্রিয়া রয়েছে:
অ্যারে থেকে একটি সর্বাধিক স্তূপ তৈরি করুন।
অ্যারের শেষ উপাদানটির সাথে প্রথম উপাদানটি (যা সর্বাধিক স্তূপের বৃহত্তম) বিনিময় করুন।
স্তূপ থেকে শেষ উপাদানটি সরান (যা এখন সাজানো হয়েছে), এবং স্তূপের আকার হ্রাস করুন।
মূল উপাদানের উপর একটি স্তূপ অপারেশন সম্পাদন করে সর্বাধিক স্তূপ বৈশিষ্ট্য টি পুনরুদ্ধার করুন।
স্তূপের আকার 1 না হওয়া পর্যন্ত ধাপ 2-4 পুনরাবৃত্তি করুন।
অ্যারেতে উপাদানগুলি বিপরীত করে সাজানো অ্যারে পাওয়া যায়।
এখানে পূর্ণসংখ্যার নিম্নলিখিত তালিকায় প্রয়োগ করা হচ্ছে এমন স্তূপ প্রকারের একটি উদাহরণ দেওয়া হল: [5, 3, 7, 2, 8, 4, 1, 6]
অ্যারে থেকে একটি সর্বাধিক স্তূপ তৈরি করুন:
[8, 6, 7, 2, 3, 4, 1, 5]
প্রথম এবং শেষ উপাদানগুলি পরিবর্তন করুন:
[5, 6, 7, 2, 3, 4, 1, 8]
স্তূপ থেকে শেষ উপাদানটি সরান এবং স্তূপের আকার হ্রাস করুন:
স্তূপ: [7, 6, 4, 2, 3, 5, 1]
সাজানো হয়েছে:[8]
সর্বাধিক স্তূপ বৈশিষ্ট্য পুনরুদ্ধার করুন:
স্তূপ: [7, 6, 5, 2, 3, 4, 1]
স্তূপের আকার 1 না হওয়া পর্যন্ত ধাপ 2-4 পুনরাবৃত্তি করুন:
[5, 6, 4, 2, 3, 1, 7]
[1, 6, 4, 2, 3, 5, 7]
[5, 3, 4, 2, 1, 6, 7]
[1, 3, 4, 2, 5, 6, 7]
[3, 2, 4, 1, 5, 6, 7]
[1, 2, 4, 3, 5, 6, 7]
[2, 1, 4, 3, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
চূড়ান্ত বাছাইকৃত অ্যারে পেতে অ্যারের উপাদানগুলি বিপরীত করুন: [1, 2, 3, 4, 5, 6, 7, 8]
সবচেয়ে খারাপ ক্ষেত্রে হিপ সর্টের সময় জটিলতা হল ও (এন লগ এন) এবং এটির ও (1) এর স্থান জটিলতা রয়েছে কারণ এটি অ্যারেকে জায়গায় শ্রেণিবদ্ধ করে। হিপ সর্ট প্রায়শই এমন পরিস্থিতিতে ব্যবহৃত হয় যেখানে মেমরি স্পেস সীমিত এবং দ্রুত বাছাই বা মার্জ সর্ট সম্ভব নাও হতে পারে।
Factorial and tower of hanoi problem;
ফ্যাক্টোরিয়াল হলো একটি গাণিতিক অপারেশন যা একটি বিস্ময়কর (!) চিহ্ন দ্বারা প্রতিনিধিত্ব করা হয়। এটি একটি নির্দিষ্ট সংখ্যার প্রথম থেকে সকল সক্ষম সংখ্যা এর গুণফল হিসাবে সংজ্ঞায়িত করা হয়। উদাহরণস্বরূপ, 5 এর ফ্যাক্টোরিয়াল (5!) হিসাব করা হয় নিম্নলিখিত প্রকারে:
5! = 5 x 4 x 3 x 2 x 1 = 120
ফ্যাক্টোরিয়াল অপারেশনটি সম্ভাবনা থিওরি এর মধ্যে সাধারণত ব্যবহৃত হয় যাতে কোন সেট অবজেক্ট কে কিভাবে বিন্যাস করা যাবে তা হিসাব করা যায়।
হ্যানয় টাওয়ার একটি গাণিতিক ধাঁধা যা তিনটি টাওয়ার (পেগ) নিয়ে গঠিত এবং একাধিক রিং চিত্রিত হয়েছে -
এই রিংগুলি বিভিন্ন আকারের এবং একটি ক্রমবর্ধমান ক্রমের মধ্যে স্ট্যাক করা হয়, অর্থাত্ ছোটটি বৃহত্তরটির উপরে বসে। ধাঁধার অন্যান্য বৈচিত্র রয়েছে যেখানে ডিস্কের সংখ্যা বৃদ্ধি পায়, তবে টাওয়ার গণনা একই থাকে।
নিয়ম
মিশনটি হ'ল ব্যবস্থার ক্রম লঙ্ঘন না করে সমস্ত ডিস্ককে অন্য কোনও টাওয়ারে সরানো। হ্যানয় টাওয়ারের জন্য অনুসরণ করা কয়েকটি নিয়ম হ'ল -
যে কোনও সময়ে টাওয়ারগুলির মধ্যে কেবল একটি ডিস্ক সরানো যেতে পারে।
কেবলমাত্র "শীর্ষ" ডিস্কটি অপসারণ করা যেতে পারে।
কোনও বড় ডিস্ক একটি ছোট ডিস্কের উপরে বসতে পারে না।
নীচে তিনটি ডিস্ক দিয়ে হ্যানয়ের একটি টাওয়ার ধাঁধা সমাধানের একটি অ্যানিমেটেড উপস্থাপনা রয়েছে।
এন ডিস্ক সহ হ্যানয় ধাঁধার টাওয়ারটি ন্যূনতম 2n−1 ধাপে সমাধান করা যেতে পারে। এই উপস্থাপনাটি দেখায় যে 3 ডিস্ক সহ একটি ধাঁধা 23 - 1 = 7 পদক্ষেপ নিয়েছে।
এ্যালগোরিদম
টাওয়ার অফ হ্যানয়ের জন্য একটি অ্যালগরিদম লিখতে, প্রথমে আমাদের শিখতে হবে কিভাবে কম পরিমাণে ডিস্ক দিয়ে এই সমস্যাটি সমাধান করা যায়, যেমন → 1 বা 2। আমরা নাম, উত্স, গন্তব্য এবং অক্স দিয়ে তিনটি টাওয়ার চিহ্নিত করি (শুধুমাত্র ডিস্কগুলি সরাতে সহায়তা করার জন্য)। আমাদের যদি কেবল একটি ডিস্ক থাকে তবে এটি সহজেই উত্স থেকে গন্তব্য পেগে সরানো যেতে পারে।
আমাদের যদি 2 টি ডিস্ক থাকে -
প্রথমত, আমরা ছোট (উপরের) ডিস্কটি অক্স পেগে সরান।
তারপরে, আমরা বৃহত্তর (নীচের) ডিস্কটি গন্তব্য পেগে সরিয়ে নিই।
এবং অবশেষে, আমরা ছোট ডিস্কটি অক্স থেকে গন্তব্য পেগে স্থানান্তর করি।
সুতরাং এখন, আমরা দুটিরও বেশি ডিস্ক সহ হ্যানয়ের টাওয়ারের জন্য একটি অ্যালগরিদম ডিজাইন করার অবস্থানে আছি। আমরা ডিস্কের স্ট্যাককে দুটি অংশে ভাগ করি। বৃহত্তম ডিস্ক (এনটিএইচ ডিস্ক) এক অংশে এবং অন্যান্য সমস্ত (এন -1) ডিস্ক দ্বিতীয় অংশে রয়েছে।
আমাদের চূড়ান্ত লক্ষ্য হ'ল ডিস্ক এন উত্স থেকে গন্তব্যে সরানো এবং তারপরে অন্যান্য সমস্ত (এন 1) ডিস্কগুলি এটিতে স্থাপন করা। আমরা ডিস্কের সমস্ত সেটের জন্য পুনরাবৃত্ত উপায়ে এটি প্রয়োগ করার কল্পনা করতে পারি।
অনুসরণ করার পদক্ষেপগুলি হ'ল -
ধাপ 1 − n-1 ডিস্কগুলি উত্স থেকে অক্সে সরান
ধাপ 2 − nth ডিস্ককে উত্স থেকে ডেস্টে সরান
ধাপ 3 - n-1 ডিস্কগুলি অক্স থেকে ডেস্টে সরান
START
Procedure Hanoi(disk, source, dest, aux)
IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, aux, dest, source) // Step 3
END IF
END Procedure
STOP
Searching techniques (linear and binary search)
লিনিয়ার সার্চ এলগরিদম হল একটি সার্চিং এলগরিদম যেখানে একটি একটি ইনপুট এলিমেন্টকে এক এক করে চেক করে আবদ্ধকৃত টার্গেট এলিমেন্ট খুঁজে বের করে। এই অ্যালগরিদম পারফরমেন্স ওভারহেড কম থাকলেও সাধারণত বেশ ধীর।
একটি লিনিয়ার সার্চ এলগরিদমের উদাহরণ হলঃ
ধরুন আমরা একটি লিস্ট [4, 6, 3, 2, 8, 1, 7, 5] এর মধ্যে এলিমেন্ট 8 খুঁজতে চাই।
প্রথমে আমরা লিস্টের প্রথম এলিমেন্ট থেকে শুরু করে একটি ফর লুপ চালাবে। লুপের প্রতিটি পাশে একটি ইনপুট এলিমেন্ট চেক করা হবে এবং সেটি আবদ্ধকৃত টার্গেট এলিমেন্ট সমান কিনা তা চেক করা হবে। সমান না হলে লুপের পরবর্তী ইনপুট এলিমেন্ট চেক করা হবে এবং এক্ষেত্রে লুপ কন্টিনিউ করবে।
সমান হলে, লুপ থেমে যাবে এবং আবদ্ধকৃত টার্গেট এলিমেন্ট যেখানে পাওয়া গেছে সেই ইনডেক্স রিটার্ন করবে। আর যদি লুপ শেষ হয় এবং কোন এলিমেন্ট পাওয়া না যায় তখন -1 রিটার্ন করবে।
উপরের উদাহরণ এর ক্ষেত্রে, আবদ্ধকৃত টার্গেট এলিমেন্ট হল 8। লুপ চালানোর পর সংখ্যা 8 এর ইনডেক্স হল 4, তাই ফাংশনটি রিটার্ন করবে 4।
লিনিয়ার সার্চ এলগরিদম খুব সিম্পল এবং সহজ ব্যবহার করা যায়। তবে, খুব বড় ডেটাসেট ব্যবহার করলে পারফরমেন্স কম হতে পারে। এছাড়াও, একটি সার্চ টার্গেট এলিমেন্ট খুজে না পেলে এলগরিদমটি সম্পূর্ণ পরিস্কার করে শেষ হয় যা কমপক্ষে একটি প্রশ্নকে উল্লঘণ করবে।
বাইনারি সার্চ
বাইনারি সার্চ একটি খুব জনপ্রিয় অ্যালগরিদম যা অ্যারে বা লিস্ট থেকে একটি নির্দিষ্ট উপাদান খুঁজে বের করে। এই অ্যালগরিদমে একটি সর্টেড অ্যারে অথবা লিস্ট নেয়া হয় এবং একটি উপাদান দেওয়া হয় যা খুঁজা হবে। প্রথমে সর্টেড অ্যারের মধ্যে উপাদানটি মধ্যবর্তী উপাদান হিসেবে নেওয়া হয়। এখানে যদি উপাদানটি মধ্যবর্তী উপাদানের সমান হয় তবে উপাদানটি বের করা হয়। আর যদি উপাদানটি মধ্যবর্তী উপাদানের চেয়ে ছোট হয়, তবে সর্টেড অ্যারের বামপাশের সাব অ্যারেটি নিয়ে পুনরায় বাইনারি সার্চ করা হয়। আর যদি উপাদানটি মধ্যবর্তী উপাদানের চেয়ে বড় হয়, তবে সর্টেড অ্যারের ডানপাশের সাব অ্যারেটি নিয়ে পুনরায় বাইনারি সার্চ করা হয়।
একটি উদাহরণ দেখা যাক। ধরা যাক একটি সর্টেড অ্যারে রয়েছে [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] এবং আমরা 7 খুঁজছি।
প্রথমে মধ্যবর্তী উপাদান নির্ণয় করা হয়। মধ্যবর্তী উপাদান হলো 9। এখন উপাদান 7 মধ্যবর্তী উপাদান 9 এর চেয়ে ছোট হয়। সুতরাং বামপাশের সাব অ্যারে [1, 3, 5, 7] নিয়ে পুনরায় বাইনারি সার্চ করা হয়।
এখন সাব অ্যারেটির মধ্যবর্তী উপাদান হলো 3। উপাদান 7 মধ্যবর্তী উপাদান 3 এর চেয়ে বড় হয়। তাই ডানপাশের সাব অ্যারে [5, 7] নিয়ে পুনরায় বাইনারি সার্চ করা হয়।
এখন সাব অ্যারেটির মধ্যবর্তী উপাদান হলো 7। উপাদান 7 খুঁজে পাওয়া গেছে। এবং ফলস্বরূপ পাওয়া উপাদানের ইনডেক্স হল 3।
সুতরাং, বাইনারি সার্চ অ্যালগরিদম ব্যবহার করে 7 উপাদানটি খুঁজে বের কর
Tree traversal algorithm
ট্রি ট্রাভার্সাল হল একটি নির্দিষ্ট ক্রমে, ট্রি ডাটা স্ট্রাকচারের প্রতিটি নোডকে ঠিক একবার দেখার একটি প্রক্রিয়া। তিনটি প্রধান ট্রাভার্সাল অ্যালগরিদম আছে:
ইন-অর্ডার ট্রাভার্সাল: ইন-অর্ডার ট্রাভার্সালে, প্রথমে বাম সাবট্রি পরিদর্শন করা হয়, তারপরে রুট নোড এবং তারপরে ডান সাবট্রিতে দেখা হয়। এটি লেফট-রুট-রাইট (L-R-D) ট্রাভার্সাল নামেও পরিচিত।
প্রি-অর্ডার ট্রাভার্সাল: একটি প্রি-অর্ডার ট্রাভার্সালে, রুট নোডটি প্রথমে পরিদর্শন করা হয়, তারপরে বাম সাবট্রি এবং তারপর ডান সাবট্রিতে। এটি রুট-লেফট-রাইট (R-L-D) ট্রাভার্সাল নামেও পরিচিত।
পোস্ট-অর্ডার ট্রাভার্সাল: পোস্ট-অর্ডার ট্রাভার্সালে, প্রথমে বাম সাবট্রি পরিদর্শন করা হয়, তারপরে ডান সাবট্রি এবং তারপর রুট নোড। এটি লেফট-রাইট-রুট (L-D-R) ট্রাভার্সাল নামেও পরিচিত।
এই ট্রাভার্সাল অ্যালগরিদমগুলির প্রত্যেকটির নিজস্ব সুবিধা এবং ব্যবহারের ক্ষেত্রে রয়েছে, অ্যাপ্লিকেশন এবং সমস্যা সমাধানের উপর নির্ভর করে। উদাহরণস্বরূপ, ইন-অর্ডার ট্রাভার্সাল বাইনারি সার্চ ট্রিতে নোডগুলিকে সাজানো ক্রমে পুনরুদ্ধার করতে ব্যবহার করা যেতে পারে, যখন পোস্ট-অর্ডার ট্র্যাভার্সাল বাইনারি ট্রিতে সমস্ত নোড মুছে ফেলার জন্য ব্যবহার করা যেতে পারে।
উদাহারন
1
/ \
2 3
/ \ \
4 5 6
Preorder traversal: 1 2 4 5 3 6
Inorder traversal: 4 2 5 1 3 6
Postorder traversal: 4 5 2 6 3 1
greedy algorithms
একটি লোভী অ্যালগরিদম হল এক ধরনের অ্যালগরিদমিক কৌশল যা একটি বিশ্বব্যাপী সর্বোত্তম সমাধান খুঁজে পাওয়ার আশায় প্রতিটি ধাপে স্থানীয়ভাবে সর্বোত্তম পছন্দ করে। অন্য কথায়, একটি লোভী অ্যালগরিদম ভবিষ্যতের পরিণতি বিবেচনা না করে বর্তমান মুহূর্তে উপলব্ধ সেরা বিকল্পটি বেছে নেয়।
একটি লোভী অ্যালগরিদমের একটি সর্বোত্তম উদাহরণ হল "মুদ্রা পরিবর্তনের সমস্যা", যা একটি নির্দিষ্ট পরিমাণ অর্থের জন্য পরিবর্তন করতে প্রয়োজনীয় ন্যূনতম সংখ্যক কয়েন খুঁজে বের করে। ধরুন আমাদের কাছে {1, 5, 10, 25} মূল্যের মুদ্রার একটি সেট আছে এবং আমরা 47 সেন্টের জন্য পরিবর্তন করতে চাই। একটি লোভী অ্যালগরিদম সবচেয়ে বড় মূল্যের মুদ্রা বাছাই করে শুরু করবে যা বাকি অর্থের চেয়ে কম বা সমান, এই ক্ষেত্রে, 25 সেন্ট মুদ্রা। আমরা 22 সেন্ট রেখে 47 সেন্ট থেকে 25 সেন্ট বিয়োগ করব। এর পরে, আমরা সবচেয়ে বড় মূল্যের মুদ্রা বাছাই করব যা বাকি টাকার পরিমাণের চেয়ে কম বা সমান, যা হল আরেকটি 25 সেন্ট মুদ্রা। আমরা 22 সেন্ট থেকে 25 সেন্ট বিয়োগ করব, -3 সেন্ট রেখে। যেহেতু আমাদের ঋণাত্মক সেন্ট থাকতে পারে না, তাই আমরা এখানে থামব এবং এই উপসংহারে উপনীত হব যে কয়েনের এই সেটটি ব্যবহার করে 47 সেন্টের জন্য পরিবর্তন করতে প্রয়োজনীয় কয়েনের ন্যূনতম সংখ্যা দুটি।
যাইহোক, এই লোভী অ্যালগরিদম সর্বদা সর্বোত্তম সমাধান প্রদান করে না। উদাহরণস্বরূপ, যদি আমাদের কাছে {1, 3, 4} মূল্যের মুদ্রার একটি সেট থাকে এবং আমরা 6 সেন্টের জন্য পরিবর্তন করতে চাই, তাহলে লোভী অ্যালগরিদম দুটি 3 সেন্টের কয়েন বেছে নেবে, যার ফলে মোট 2টি কয়েন হবে। যাইহোক, সর্বোত্তম সমাধান হবে দুটি 3 সেন্ট কয়েন এবং একটি 1 সেন্ট কয়েন ব্যবহার করা, যার ফলে মোট 3টি কয়েন হবে। অতএব, কিছু ক্ষেত্রে লোভী অ্যালগরিদম কার্যকর হতে পারে, তারা সর্বদা সর্বোত্তম সমাধান নাও দিতে পারে।
graph searching, BFS, DFS;
গ্রাফ অনুসন্ধান হল গ্রাফের সমস্ত শীর্ষবিন্দু (নোড) এবং প্রান্তগুলি (সংযোগ) দেখার জন্য একটি গ্রাফ ডেটা কাঠামো অতিক্রম করার প্রক্রিয়া। গ্রাফ অনুসন্ধান কম্পিউটার বিজ্ঞানের একটি গুরুত্বপূর্ণ সমস্যা এবং এটি বিভিন্ন অ্যাপ্লিকেশনে ব্যবহৃত হয়, যেমন ওয়েব ক্রলিং, সামাজিক নেটওয়ার্ক বিশ্লেষণ এবং সুপারিশ ব্যবস্থা।
দুটি প্রধান ধরনের গ্রাফ অনুসন্ধান অ্যালগরিদম আছে:
প্রস্থ-প্রথম অনুসন্ধান (BFS): BFS-এ, গ্রাফটি একটি প্রদত্ত শীর্ষবিন্দু ("উৎস" শীর্ষবিন্দু) থেকে শুরু করে এবং পরবর্তী স্তরে যাওয়ার আগে একই স্তরে সমস্ত শীর্ষবিন্দু পরিদর্শন করে স্তর দ্বারা স্তরে প্রবেশ করা হয়। BFS একটি সারির ডেটা স্ট্রাকচার ব্যবহার করে ভিজিট করা শীর্ষবিন্দুগুলির ট্র্যাক রাখতে। এই অ্যালগরিদমটি সাধারণত একটি ওজনহীন গ্রাফে দুটি শীর্ষবিন্দুর মধ্যে সংক্ষিপ্ততম পথ খুঁজে পেতে ব্যবহৃত হয়।
Depth-first search (DFS): DFS-এ, ব্যাকট্র্যাক করার আগে প্রতিটি শাখা বরাবর যতদূর সম্ভব অন্বেষণ করে গ্রাফটি অতিক্রম করা হয়। DFS একটি স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করে ভিজিট করা শীর্ষস্থানগুলির ট্র্যাক রাখতে। এই অ্যালগরিদমটি সাধারণত একটি গ্রাফে দুটি শীর্ষবিন্দুর মধ্যে সম্ভাব্য সমস্ত পথ খুঁজে পেতে এবং একটি গ্রাফে চক্র সনাক্ত করতে ব্যবহৃত হয়।
বিএফএস এবং ডিএফএস উভয়েরই নিজস্ব সুবিধা এবং অসুবিধা রয়েছে, নির্দিষ্ট সমস্যার সমাধান হওয়ার উপর নির্ভর করে। BFS একটি ওজনহীন গ্রাফে সংক্ষিপ্ততম পথ খুঁজে পাওয়ার নিশ্চয়তা দেয়, তবে কিছু ক্ষেত্রে ধীর হতে পারে। DFS সাধারণত দ্রুত এবং আরও মেমরি-দক্ষ, কিন্তু সর্বদা সর্বোত্তম সমাধান খুঁজে নাও পেতে পারে এবং গ্রাফে চক্র থাকলে অসীম লুপে আটকে যেতে পারে।
সাধারণভাবে, উপযুক্ত গ্রাফ অনুসন্ধান অ্যালগরিদম নির্বাচন করা নির্দিষ্ট সমস্যা সমাধান করা এবং গ্রাফ ডেটা কাঠামোর বৈশিষ্ট্যগুলির উপর নির্ভর করে।
Divide and conquer algorithms
ডিভাইড এবং জয় অ্যালগরিদম হল কম্পিউটার সায়েন্সে একটি ধরণের অ্যালগরিদম ডিজাইন প্যারাডাইম। এটি সমস্যাটি ছোট উপসমস্যাগুলি ভেঙ্গে ফেলা, প্রতিটি উপসমস্যাকে স্বতন্ত্রভাবে সমাধান করা এবং তারপর সাবপ্রবলেমগুলির সমাধানগুলি একত্রিত করে মূল সমস্যার সমাধানে পৌঁছানোর জন্য ব্যবহৃত হয়।
ডিভাইড এবং জয় অ্যালগরিদম ডিজাইন করার জন্য মৌলিক পদক্ষেপগুলি হল:
১। Divide: সমস্যাটি ছোট উপসমস্যাগুলি ভেঙ্গে ফেলা যা স্বতন্ত্রভাবে সমাধান করা যাবে।
২। Conpuare: প্রতিটি সাবপ্রবলেমকে রিকার্সিভভাবে সমাধান করা। যদি সাবপ্রবলেমটি যথাক্রমে ছোট হয়, তবে এটি সরাসরি সমাধান করা হয়।
৩। Combain: সাবপ্রবলেমগুলির সমাধানগুলি একত্রিত করে মূল সমস্যার
!
সমাধান পেতে মৌলিক প্রবলেমটি সমাধান করার সাথে সাথে সাবপ্রবলেমগুলির সমাধানগুলি সংযোজন করা হয়।
এই প্রক্রিয়াটি সর্টিং, সার্চিং এবং ম্যাট্রিক্স মাল্টিপ্লিকেশনের জন্য অ্যালগরিদমে ব্যবহৃত হয়। উদাহরণস্বরূপ, কুইকসর্ট অ্যালগরিদমে, সাজানো লিস্টটি দুটি সাবলিস্টে ভাগ করা হয়, প্রতিটি সাবলিস্টকে স্বতন্ত্রভাবে সাজানো হয় এবং তারপর একটি পিভট উপাদান ব্যবহার করে চতুর্থ তালিকা তৈরি করে ফাইনাল সর্টেড লিস্টটি তৈরি করা হয়।
ডিভাইড এবং জয় অ্যালগরিদমের একটি উপকারিতা হল যে এগুলি অন্যান্য প্রকার অ্যালগরিদমের তুলনায় সাধারণত আগে চলতে থাকে
বিভাজন এবং জয় অ্যালগরিদমের একটি উদাহরণ হ'ল বিখ্যাত "বাইনারি অনুসন্ধান" অ্যালগরিদম। অ্যালগরিদমটি অনুসন্ধানব্যবধানকে বারবার অর্ধেকে ভাগ করে উপাদানগুলির একটি সাজানো অ্যারের মধ্যে একটি নির্দিষ্ট মান খুঁজে পেতে ব্যবহৃত হয়।
এটি কীভাবে কাজ করে তা এখানে:
প্রথমত, অ্যালগরিদম অ্যারের মধ্যবর্তী উপাদানের সাথে লক্ষ্য মান তুলনা করে।
যদি মধ্যম উপাদানটি লক্ষ্য মানের সমান হয় তবে অনুসন্ধানটি সম্পূর্ণ হয় এবং অ্যালগরিদম টি মধ্য উপাদানের সূচকটি ফিরিয়ে দেয়।
যদি লক্ষ্য মান টি মাঝারি উপাদানের চেয়ে কম হয় তবে অ্যালগরিদম অ্যারের বাম অর্ধেক অনুসন্ধান করে।
যদি লক্ষ্য মানটি মাঝারি উপাদানের চেয়ে বেশি হয় তবে অ্যালগরিদম অ্যারেটির ডান অর্ধেক অনুসন্ধান করে।
অ্যালগরিদমটি লক্ষ্য মান না পাওয়া পর্যন্ত বা অবশিষ্ট অ্যারে খালি না হওয়া পর্যন্ত অ্যারের অবশিষ্ট অর্ধেকে 1-4 ধাপ পুনরাবৃত্তি করে।
এই অ্যালগরিদমের ও (লগ এন) এর একটি সময় জটিলতা রয়েছে, যার অর্থ অ্যারেতে উপাদানগুলির সংখ্যার সাথে অনুসন্ধানের সময় লগারিদমিকভাবে বৃদ্ধি পায়। এটি বড় অ্যারে অনুসন্ধানের জন্য এটি খুব দক্ষ করে তোলে।
Dynamic Programming:
ডায়নামিক প্রোগ্রামিং হল কম্পিউটার বিজ্ঞান এবং গণিতে ব্যবহৃত একটি সমস্যা-সমাধান কৌশল যা একটি জটিল সমস্যাকে ছোট ছোট উপ-সমস্যায় ভাগ করে এবং প্রতিটি উপ-সমস্যা শুধুমাত্র একবার সমাধান করে। উপ-সমস্যাগুলির সমাধানগুলি তারপর মূল সমস্যা সমাধানের জন্য একত্রিত হয়।
কৌশলটি বিশেষত সেই সমস্যার জন্য উপযোগী যেখানে একই উপ-সমস্যা বহুবার পুনরাবৃত্তি হয়, কারণ এটি অপ্রয়োজনীয় গণনা এড়ায় এবং সামগ্রিক গণনার সময় হ্রাস করে।
ডায়নামিক প্রোগ্রামিংয়ে সাধারণত চারটি ধাপ থাকে:
একটি সর্বোত্তম সমাধানের গঠন চিহ্নিত করুন
ছোট উপ-সমস্যাগুলির পরিপ্রেক্ষিতে একটি সর্বোত্তম সমাধানের মান পুনরাবৃত্তিমূলকভাবে সংজ্ঞায়িত করুন
একটি যৌক্তিক ক্রমে সাব-সমস্যাগুলি সমাধান করে, নীচে-আপ ফ্যাশনে একটি সর্বোত্তম সমাধানের মান গণনা করুন
গণনাকৃত তথ্য থেকে মূল সমস্যার একটি সর্বোত্তম সমাধান তৈরি করুন।
প্রযুক্তিটি অপ্টিমাইজেশান, কন্ট্রোল থিওরি, গেম থিওরি এবং বায়োইনফরমেটিক্স সহ বিভিন্ন ক্ষেত্রে ব্যবহৃত হয়। ডায়নামিক প্রোগ্রামিং সমস্যার কিছু ক্লাসিক উদাহরণের মধ্যে রয়েছে ন্যাপস্যাক সমস্যা, দীর্ঘতম সাধারণ পরবর্তী সমস্যা এবং গ্রাফ তত্ত্বের সংক্ষিপ্ত পথ সমস্যা।
basic traversal & search techniques
ট্রাভার্সাল এবং অনুসন্ধান কৌশলগুলি কম্পিউটার বিজ্ঞানের মৌলিক ক্রিয়াকলাপ যা ডেটা কাঠামোর মধ্যে ডেটা অন্বেষণ এবং সনাক্ত করতে ব্যবহৃত হয়। এখানে কিছু মৌলিক ট্রাভার্সাল এবং অনুসন্ধান কৌশল রয়েছে:
Liniar Search: অনুক্রমিক অনুসন্ধান হিসাবেও পরিচিত, এই কৌশলটিতে একটি ডেটা কাঠামোর প্রতিটি উপাদান একে একে চেক করা জড়িত যতক্ষণ না পছন্দসই উপাদানটি পাওয়া যায় বা কাঠামোর শেষ না পৌঁছায়। রৈখিক অনুসন্ধান সহজ কিন্তু বড় ডেটা স্ট্রাকচারের জন্য ধীর হতে পারে।
bainary Search: এই কৌশলটি বারবার অনুসন্ধানের ব্যবধানকে অর্ধেক ভাগ করে একটি সাজানো অ্যারে অনুসন্ধানের জন্য ব্যবহার করা হয়। বাইনারি অনুসন্ধান বড় ডেটা স্ট্রাকচারের জন্য লিনিয়ার অনুসন্ধানের চেয়ে অনেক দ্রুত।
ডেপথ-ফার্স্ট সার্চ (DFS): এটি একটি ট্রাভার্সাল কৌশল যা ব্যাকট্র্যাক করার আগে প্রতিটি শাখা বরাবর যতদূর সম্ভব অন্বেষণ করে। DFS সাধারণত গাছ এবং গ্রাফ ট্রাভার্সিং জন্য ব্যবহৃত হয়.
Breath First Search (BFS): এটি একটি ট্রাভার্সাল কৌশল যা একটি গ্রাফ বা গাছের সমস্ত শীর্ষবিন্দুকে প্রস্থ-প্রথম ক্রমে পরিদর্শন করে, অর্থাৎ, পরবর্তী স্তরে যাওয়ার আগে এটি একই স্তরে সমস্ত শীর্ষবিন্দু পরিদর্শন করে। BFS সাধারণত সংক্ষিপ্ত পথ সমস্যা সমাধানের জন্য ব্যবহৃত হয়।
ইন-অর্ডার ট্রাভার্সাল: এটি একটি ট্রাভার্সাল কৌশল যা বাম সাবট্রি, তারপর রুট এবং অবশেষে ডান সাবট্রি পরিদর্শন করে। ইন-অর্ডার ট্রাভার্সাল সাধারণত বাইনারি অনুসন্ধান গাছের জন্য ব্যবহৃত হয়।
প্রি-অর্ডার ট্রাভার্সাল: এটি একটি ট্রাভার্সাল কৌশল যা প্রথমে রুট নোড, তারপর বাম সাবট্রি এবং অবশেষে ডান সাবট্রিতে যায়।
পোস্ট-অর্ডার ট্রাভার্সাল: এটি একটি ট্রাভার্সাল কৌশল যা বাম সাবট্রি, তারপর ডান সাবট্রি এবং অবশেষে রুট নোড পরিদর্শন করে।
এগুলি কম্পিউটার বিজ্ঞানে ব্যবহৃত কিছু মৌলিক ট্রাভার্সাল এবং অনুসন্ধান কৌশল। বিভিন্ন অ্যাপ্লিকেশনে ব্যবহৃত এই কৌশলগুলির অনেক বৈচিত্র এবং এক্সটেনশন রয়েছে।
BackTracking:
ব্যাকট্র্যাকিং হল একটি সাধারণ অ্যালগরিদমিক কৌশল যা একটি প্রার্থীর সমাধানকে ক্রমবর্ধমানভাবে তৈরি করে এবং এটি সম্ভাব্য নয় বা বৈধ সমাধান নয় বলে নির্ধারিত হওয়ার সাথে সাথে এটি ত্যাগ করার মাধ্যমে সমস্যার সমস্ত সম্ভাব্য সমাধান অন্বেষণ করে। ব্যাকট্র্যাকিং সমস্যা সমাধানের জন্য ব্যবহার করা হয় যেখানে একাধিক প্রার্থীর সমাধান রয়েছে এবং সর্বোত্তম সমাধান শুধুমাত্র সম্ভাব্য সমস্ত সমাধানের মূল্যায়ন করে পাওয়া যেতে পারে।
ব্যাকট্র্যাকিং অ্যালগরিদম এই পদক্ষেপগুলি অনুসরণ করে কাজ করে:
সমস্যা এবং সীমাবদ্ধতাগুলি সংজ্ঞায়িত করুন যা অবশ্যই সন্তুষ্ট হতে হবে।
সমস্যার সম্ভাব্য সমাধান বেছে নিন।
পরীক্ষা করুন যদি নির্বাচিত সমাধানটি সমস্যার সীমাবদ্ধতাগুলিকে সন্তুষ্ট করে।
যদি সমাধানটি সীমাবদ্ধতাগুলিকে সন্তুষ্ট করে, তবে এটি সর্বোত্তম সমাধান কিনা তা পরীক্ষা করে দেখুন।
যদি সমাধানটি সর্বোত্তম না হয়, তাহলে পিছনে যান এবং একটি ভিন্ন সমাধান চেষ্টা করুন।
ব্যাকট্র্যাকিং-এর মূল ধারণা হল পদ্ধতিগতভাবে কোনো সমস্যার সব সম্ভাব্য সমাধান অন্বেষণ করা এবং যখন কোনো সমাধান সম্ভব নয় বা সর্বোত্তম নয় বলে পাওয়া যায় তখন ব্যাকট্র্যাক করা। কৌশলটি সাধারণত এন-কুইন্স সমস্যা, সুডোকু এবং ভ্রমণ বিক্রয়কর্মী সমস্যাগুলির মতো সমন্বিত অপ্টিমাইজেশন সমস্যাগুলিতে ব্যবহৃত হয়।
ব্যাকট্র্যাকিং অ্যালগরিদমগুলি পুনরাবৃত্তিমূলকভাবে বা পুনরাবৃত্তিমূলকভাবে প্রয়োগ করা যেতে পারে, সমস্যার প্রয়োজনীয়তা এবং সীমাবদ্ধতার উপর নির্ভর করে। রিকার্সিভ ব্যাকট্র্যাকিং সাধারণত এমন সমস্যাগুলির জন্য ব্যবহার করা হয় যেখানে স্টেট স্পেস বড় এবং সমাধানটি একটি গাছের মতো গঠন করা হয়, যখন পুনরাবৃত্তিমূলক ব্যাকট্র্যাকিং সমস্যাগুলির জন্য ব্যবহৃত হয় যেখানে সমাধানটি একটি গ্রাফ বা লিঙ্কযুক্ত অবস্থার একটি সেট হিসাবে গঠন করা হয়।
Branch and Bound:
শাখা এবং আবদ্ধ একটি অ্যালগরিদমিক কৌশল যা অপ্টিমাইজেশান সমস্যাগুলি সমাধান করতে ব্যবহৃত হয়, বিশেষ করে যেগুলি সম্মিলিত অনুসন্ধান জড়িত। এই কৌশলটিতে একটি সমস্যাকে পদ্ধতিগতভাবে ছোট ছোট উপসমস্যাগুলিতে ভাগ করা এবং তারপর উপসমস্যাগুলিকে ছাঁটাই করা যা সাবঅপ্টিমাল সমাধানের জন্য গ্যারান্টিযুক্ত, এইভাবে সামগ্রিক অনুসন্ধানের স্থান হ্রাস করে।
শাখা এবং আবদ্ধের সাধারণ পদ্ধতি হল প্রার্থীর সমাধানগুলির একটি সেট তৈরি করা এবং অনুসন্ধান স্থানটিকে বিচ্ছিন্ন সাবস্পেস বা শাখাগুলির একটি সেটে ভাগ করা। প্রতিটি শাখা প্রার্থী সমাধানের একটি উপসেট প্রতিনিধিত্ব করে। সর্বোত্তম দ্রবণে একটি নিম্ন সীমা প্রতিটি শাখার জন্য গণনা করা হয়, এবং যদি নিম্ন সীমাটি বর্তমান সর্বোত্তম সমাধানকে অতিক্রম করে, শাখাটি ছাঁটাই করা হয়। প্রক্রিয়াটি চলতে থাকে যতক্ষণ না সমস্ত সাবস্পেস অন্বেষণ করা হয় এবং সর্বোত্তম সমাধান পাওয়া যায়।
শাখা এবং আবদ্ধ অ্যালগরিদম এই পদক্ষেপগুলি অনুসরণ করে কাজ করে:
ইনিশিয়ালাইজেশন: ইনফিনিটিতে প্রারম্ভিক উপরের বাউন্ড সেট করুন এবং একটি প্রাথমিক সম্ভাব্য সমাধান তৈরি করুন।
ব্রাঞ্চিং: ব্রাঞ্চ করার জন্য একটি ভেরিয়েবল নির্বাচন করে সমস্যাটিকে সাব-প্রবলেমগুলিতে ভাগ করুন এবং দুই বা ততোধিক সাব-সমস্যা তৈরি করুন যার প্রতিটিতে নির্বাচিত ভেরিয়েবলের জন্য আলাদা মান রয়েছে।
লোয়ার বাউন্ডিং: সেই সাব-সমস্যা অন্বেষণ করে পাওয়া যায় এমন সর্বোত্তম সম্ভাব্য সমাধান খুঁজে বের করে প্রতিটি উপ-সমস্যার জন্য একটি নিম্ন সীমা গণনা করুন।
ছাঁটাই: যে কোনো উপসমস্যা বাদ দিন যার নিম্ন সীমা বর্তমান উপরের সীমা ছাড়িয়ে গেছে।
উপরের বাউন্ড আপডেট করা: যদি একটি উপ-সমস্যার বর্তমান সেরা সমাধানের চেয়ে ভাল সমাধান থাকে, তাহলে বর্তমান সেরা সমাধানটি আপডেট করুন।
সমাপ্তি: সমস্ত উপ-সমস্যা অন্বেষণ করা হয়ে গেলে থামুন।
ব্রাঞ্চ এবং বাউন্ড সাধারণত ট্রাভেলিং সেলসম্যান সমস্যা, ন্যাপস্যাক সমস্যা এবং কাজের সিকোয়েন্সিং সমস্যা সমাধানের জন্য ব্যবহৃত হয়। কৌশলটি বিশেষভাবে কার্যকর হয় যখন সমস্যার একটি বড় অনুসন্ধানের স্থান থাকে এবং সর্বোত্তম সমাধানে একটি নিম্ন আবদ্ধ গণনা করে সমাধান করা যেতে পারে।
0 comments:
Post a Comment