কম্পিউটার বিজ্ঞানের ভিত্তি/পুনরাবৃত্তি পুনর্বিবেচনা
পুনরায় রিকার্শন
[সম্পাদনা]রিকার্শিভ সমাধানগুলো স্বয়ংসম্পূর্ণ সমস্যাগুলি সমাধানের আরেকটি শক্তিশালী উপায় সরবরাহ করে। উদাহরণ হিসেবে আমরা বাইনারি সার্চ সমাধানটি পর্যালোচনা করব।
কিভাবে বাইনারি সার্চ কাজ করে?
[সম্পাদনা]একটি সাজানো তালিকায় একটি লক্ষ্য আইটেম চিহ্নিত করার প্রক্রিয়া। আপনি প্রথমে বেস কেস দিয়ে শুরু করেন, যা হল সরাসরি সমাধান করা যে মধ্যম আইটেমটি লক্ষ্য আইটেমের সমান কিনা। যদি মধ্যম আইটেমটি লক্ষ্য আইটেমের সমান হয় তাহলে সার্চ সম্পূর্ণ হয় এবং সূচকটি রিপোর্ট করা হয়। যদি তালিকাটি খালি থাকে তাহলে সার্চ -1 বা পাওয়া যায়নি রিপোর্ট করে। অন্যথায়, লক্ষ্য আইটেমটি মধ্যম আইটেমটির থেকে বড় বা ছোট তা নির্ধারণ করুন যাতে তালিকার কোন অংশটি সার্চ করা হবে তা নির্ধারণ করা যায়।
পরবর্তীতে, যদি মধ্যম আইটেমটি লক্ষ্য আইটেমের থেকে বড় হয় তাহলে তালিকার প্রথম অংশটি সার্চ করা হয়, অন্যথায়, আমরা তালিকার দ্বিতীয় অংশটি সার্চ করি। এটি একই সমস্যা যা আমরা প্রথমে শুরু করেছিলাম, যা এটিকে একটি রিকার্শিভ বা স্বয়ংসম্পূর্ণ সমস্যা তৈরি করে।
নীচের ছবিটি বাইনারি সার্চ কোডের বাস্তবায়ন। বেস কেস এবং রিকার্শিভ কেসগুলি লেবেল করা হয়েছে।
বাইনারি সার্চ: বিমূর্ত সরলীকরণ
[সম্পাদনা]বাইনারি সার্চ সমাধানটি সরল করার একটি চমৎকার উপায় হল বিমূর্ততা ব্যবহার করা। পূর্বে প্রদর্শিত ছবিটি একটি হেল্পার ব্লক ব্যবহার করে যা "মধ্যমের মধ্যে" নামে পরিচিত, যা একটি সাজানো তালিকার প্রথম এবং শেষ সূচক দেওয়া হলে মধ্যম সূচক খুঁজে বের করতে ব্যবহৃত হয় (নীচে দেখুন)।
আরেকটি উপায় হল বাইনারি সার্চ সমাধানটি সরলীকরণ করতে আরেকটি স্তরের বিমূর্ততা যোগ করা। নিচের হেল্পার ব্লকটি দেখায় যে লক্ষ্য এবং তালিকা "বাইনারি সার্চের জন্য" ব্লকে ইনপুট হিসাবে পাঠানো হয়েছে (নীচে দেখুন)। প্রকৃত রিকার্শিভ সমাধানটি বাস্তবায়িত হয় যখন রিকার্শিভ সার্চ ব্লকটি একটি সাজানো তালিকার প্রথম এবং শেষ সূচক সনাক্ত করে। "বাইনারি সার্চের জন্য" ব্লকটি ব্যবহারকারীদের রিকার্শিভ সার্চ কল করতে দেয়, প্রথম এবং শেষ সূচক সরবরাহ করার প্রয়োজন ছাড়াই। ব্যবহারকারী কেবল বাইনারি সার্চ শুরু করার জন্য প্রয়োজনীয় তথ্য এবং/অথবা ব্লকগুলি দেখতে পাবেন। ব্যবহারকারী রিকার্শিভ সার্চ বা সমাধানের অন্তর্দৃষ্টিগুলি দেখতে পাবেন না।
বাইনারি সার্চ: ট্রেসিং
[সম্পাদনা]আমরা পূর্বে "বাইনারি সার্চের জন্য" ব্যবহার করে আমাদের রিকার্শিভ সার্চ ইন্টারফেসটি সরল করার আলোচনা করেছি যা লক্ষ্য এবং তালিকা ইনপুট হিসাবে গ্রহণ করে (নীচে উদাহরণ দেখুন)। তারপর "রিকার্শিভ সার্চের জন্য" কল করা হয় এবং প্রথম বেস কেসটি অবিলম্বে সমাধান করা হয় কারণ আমাদের লক্ষ্য, 9, 5 এর সমান নয়। যেহেতু লক্ষ্য 9 হল 5 এর থেকে বড় (মধ্যম সূচকে উপাদান), আমরা তালিকার দ্বিতীয় অংশটি (সূচক 4 থেকে সূচক 5) অনুসন্ধান করি। প্রক্রিয়াটি পুনরাবৃত্তি হয় এবং তালিকাটি বিভক্ত হয় প্রথম উপাদানটি অবস্থান এবং/অথবা সূচক 4 তে পরীক্ষা করে। লক্ষ্যটি 7 এর থেকে বড় এবং রিকার্শিভ সার্চটি আবার পুনরাবৃত্তি হয় তালিকার দ্বিতীয় অংশটি আবার অনুসন্ধান করে। বেস কেস 2 অবিলম্বে সমাধান করে যে লক্ষ্য 9 তালিকায় 9 এর সমান; যা মধ্যম সূচক 5 এ অবস্থিত।
এখন, যেহেতু লক্ষ্যটি সূচক 5 এ পাওয়া গেছে, রিকার্শিভ সার্চ দ্বিতীয় রিকার্শিভ সার্চে রিপোর্ট করে যা প্রথম রিকার্শিভ সার্চে রিপোর্ট করে। অবশেষে, সূচক 5 "বাইনারি সার্চের জন্য" ব্লকের শীর্ষ স্তরে ব্যবহারকারীর কাছে রিপোর্ট করা হয়।
যদি তালিকায় লক্ষ্যটি পাওয়া না যায় তাহলে বাইনারি সার্চ -1 রিপোর্ট করে (নীচে দেখুন)। একই রিকার্শিভ সার্চ কলগুলি করা হয়, তবে শেষ কলটিতে শুরু সূচকটি শেষ সূচকের থেকে বড় নির্দেশ করে যে লক্ষ্যটি পাওয়া যায়নি এবং তালিকার শেষটি ঘটেছে।
কচ কার্ভ
[সম্পাদনা]১৯০৪ সালে, হেলগে ভন কচ আবিষ্কার করেন ভন কচ স্নোফ্লেক কার্ভ, "ফ্রাক্টাল জ্যামিতি অধ্যয়নে গুরুত্বপূর্ণ একটি ক্রমাগত কার্ভ"। কচ কার্ভ একটি একক লাইন সেগমেন্ট দিয়ে শুরু হয় যা ১ ইউনিট লম্বা। তারপর, সেগমেন্টটি চারটি নতুন সেগমেন্ট দ্বারা প্রতিস্থাপিত হয়, প্রতিটি মূলের এক-তৃতীয়াংশ দৈর্ঘ্য, যা জেনারেটরও বলা হয়। প্রক্রিয়াটি অনির্দিষ্টকাল পর্যন্ত পুনরাবৃত্তি হয় এবং কচ কার্ভ তৈরি করে। নীচের চিত্রটি পর্যায় ০ থেকে ২ পর্যন্ত এই প্রক্রিয়াটি দেখায়।
কচ কার্ভের দৈর্ঘ্য অসীম। কার্ভটি রিকার্শনের আরেকটি আকর্ষণীয় বাস্তবায়ন যেখানে এটি স্বয়ংসম্পূর্ণ; কার্ভটি নিজেকে বারবার অনুলিপি করে।
কচ স্নোফ্লেক
[সম্পাদনা]একটি সমবাহু ত্রিভুজের সব তিনটি পাশে একই কচ কার্ভ জেনারেটর ব্যবহার করে আমরা পুনরাবৃত্তি গুলি দেখতে পাই যা অবশেষে স্নোফ্লেকের মতো দেখতে শুরু করে (দয়া করে দেখুন কচ স্নোফ্লেক)। স্নোফ্লেকের অসীম পরিধি এবং সসীম ক্ষেত্রফল রয়েছে।
কচ স্নোফ্লেকের প্রতিটি পর্যায় পরীক্ষা করে দেখা যায় একটি প্যাটার্ন তৈরি হয় প্রতি পাশে সেগমেন্টের সংখ্যা, দৈর্ঘ্য এবং কার্ভের মোট দৈর্ঘ্যের জন্য। প্রতি পাশে সেগমেন্টের সংখ্যা পূর্বের পর্যায়ের চারগুণ বৃদ্ধি পায়। সেগমেন্টের দৈর্ঘ্য প্রতিবার সমান তৃতীয়াংশে বিভক্ত হয় যা আমাদের সেগমেন্টের দৈর্ঘ্য দেয়। মূল পর্যায়, একটি সমবাহু ত্রিভুজ, হল কেন আমরা প্রতি পাশে সেগমেন্টের সংখ্যা তিনগুণ নিই সেগমেন্টের দৈর্ঘ্য দ্বারা ভাগ করে যা বর্তমানে বাস্তবায়িত পর্যায়ের সংখ্যায় উন্নীত হয়।
অন্বেষণ প্রশ্ন
[সম্পাদনা]কচ কার্ভ এবং স্নোফ্লেক প্যাটার্নগুলি অধ্যয়ন করে প্রতিষ্ঠিত হয় এবং দেখায় কিভাবে একই প্রক্রিয়াটি প্রতিটি পর্যায় তৈরি করতে পুনরাবৃত্তি হয়। আমরা একই সমস্যার বিমূর্ততা সমাধান করতে রিকার্শিভ প্রক্রিয়া ব্যবহার করতে পারি।
- N-তম পুনরাবৃত্তির মোট দৈর্ঘ্য কত হবে? সংখ্যাগুলির দ্বারা তৈরি প্যাটার্নগুলি সহজ এবং সহজ করার আগে এবং পরে দেখুন।
- কচ কার্ভ দেখতে কেমন হবে বলে আপনি কি আশা করেন? অন্য কথায়, আপনি যদি এটি অসীমবার পুনরাবৃত্তি করেন তবে কি আশা করবেন?
- কচ কার্ভের দৈর্ঘ্য কত?
- আপনি কি প্রতিটি পর্যায়ে ক্ষেত্রফল অনুমান করতে পারেন? চূড়ান্ত স্নোফ্লেকের ক্ষেত্রফল কত?
পূর্বের প্রশ্নগুলি পর্যালোচনা করে আমরা কচ কার্ভ এবং কচ স্নোফ্লেকের আচরণ পর্যবেক্ষণ করতে পারি।
- প্রতিষ্ঠিত প্যাটার্নগুলির উপর ভিত্তি করে এটি স্পষ্ট যে N-তম পুনরাবৃত্তির মোট দৈর্ঘ্য হবে 3*(4/3)n।
- যেহেতু কচ কার্ভ অনির্দিষ্টকাল পর্যন্ত পুনরাবৃত্তি হয় এটি আরও মসৃণ দেখাবে যেহেতু লাইনগুলি আরও কাছাকাছি আসবে যদিও কখনও স্পর্শ করবে না।
- কচ কার্ভের দৈর্ঘ্য অসীম (জেনারেটরটি অসীম সংখ্যক বার প্রয়োগ করার পরে)।
- চূড়ান্ত স্নোফ্লেকের ক্ষেত্রফল সসীম।
- ↑ Niels Fabian Helge von Koch. (2014). In Encyclopædia Britannica. Retrieved from http://www.britannica.com/EBchecked/topic/958515/Niels-Fabian-Helge-von-Koch
