১সাজানোর দৌড়: কোন অ্যালগরিদম জেতে?
দলগুলো কম্পিউটারের ভূমিকায় অভিনয় করে। প্রতিটি দল ১৬টি এলোমেলো সংখ্যার কার্ড পায় আর কড়া নিয়ম মেনে সাজাতে হয়: এক দল বাবল সর্ট, আরেক দল সিলেকশন সর্ট, তৃতীয় দল মার্জ সর্ট। একজন রেফারি প্রতিটি তুলনা গোনে। তারপর দলগুলো ৩২টি কার্ড নিয়ে দৌড়ায় আর আবিষ্কার করে যে তালিকা বড় হলে কিছু অ্যালগরিদম অন্যগুলোর চেয়ে অনেক বেশি ধীর হয়, যা অ্যালগরিদমের দক্ষতার মূল ধারণা।
- ক্লাস ও বয়স
- ক্লাস ১১ · ১৬–১৭
- কাজের ধরন
- দলগত
- সময় লাগবে
- ৬০ মিনিট
- কাঠিন্য
- মাঝারি
- আনুমানিক খরচ
- ৳০–৳২০
গাণিতিক ধারণা
- নির্ভুল ধাপে ধাপে নিয়ম হিসেবে অ্যালগরিদম
- কাজ (তুলনা) গোনা
- n² বনাম n log₂ n-এর বৃদ্ধি
- সেরা, সবচেয়ে খারাপ আর গড় অবস্থা
শেখার উদ্দেশ্য
- সাজানোর অ্যালগরিদম ঠিকভাবে অনুসরণ আর বর্ণনা করা।
- একটি অ্যালগরিদম কত কাজ করে তা গোনা।
- ইনপুটের আকারের সাথে অ্যালগরিদম কীভাবে বাড়ে তুলনা করা।
- বড় তথ্যে দক্ষতা কেন গুরুত্বপূর্ণ ব্যাখ্যা করা।
বাস্তব জীবনের সাথে সম্পর্ক
সার্চ ইঞ্জিন, ব্যাংক আর ফোনের কন্টাক্ট তালিকা লাখ লাখ জিনিস সাজায়। একটি দক্ষ অ্যালগরিদম বাছাই এক সেকেন্ডে উত্তর আর কয়েক ঘণ্টায় উত্তরের মধ্যে পার্থক্য গড়তে পারে।
প্রয়োজনীয় উপকরণ
- প্রতি দলের জন্য ১৬ আর ৩২টি সংখ্যার কার্ডের সেট
- প্রতিটি অ্যালগরিদমের ছাপানো নিয়মের কার্ড
- রেফারির ট্যালি শিট, স্টপওয়াচ
ধাপে ধাপে নির্দেশনা
- তোমার অ্যালগরিদমের নিয়মের কার্ড পড়ো। সবাই ঠিকভাবে অনুসরণ করতে না পারা পর্যন্ত ৬টি কার্ডে অনুশীলন করো।
- ১৬টি কার্ড এলোমেলো করো। সাজাও, আর রেফারি দুটি কার্ডের প্রতিটি তুলনা গোনে।
- তুলনা আর সময় লেখো। নতুন করে এলোমেলো করে আবার করো।
- এবার ৩২টি কার্ড সাজাও। আগে পূর্বাভাস দাও: গোনা কি দ্বিগুণ হবে?
- বোর্ডে দলগুলোর ফলাফল তুলনা করো।
- বাবল সর্টে n কার্ডের সবচেয়ে খারাপ অবস্থা বের করো: n(n − 1) ÷ 2। ১৬টি কার্ডে তা ১২০টি তুলনা।
- মার্জ সর্টে দেখো তালিকা প্রায় log₂ n বার অর্ধেক হয়, তাই কাজ n log₂ n-এর মতো বাড়ে। ১৬টি কার্ডে সর্বোচ্চ ৪৯টি তুলনা লাগে।
- একটি কম্পিউটার সেকেন্ডে একশো কোটি তুলনা করলে ১০,০০,০০০টি জিনিসে প্রতিটি পদ্ধতিতে কত সময় লাগবে আন্দাজ করো।
গাণিতিক ব্যাখ্যা
বাবল সর্ট পাশাপাশি দুটি তুলনা করে অদলবদল করে, তালিকার মধ্য দিয়ে বারবার যায়। সবচেয়ে খারাপ অবস্থায় এটি প্রতিটি জোড়া তুলনা করে, n(n − 1) ÷ 2 বার, তাই তালিকা দ্বিগুণ হলে কাজ প্রায় চারগুণ হয়। মার্জ সর্ট বারবার তালিকা অর্ধেক করে আর সাজানো অর্ধেকগুলো মেলায়, প্রায় log₂ n স্তরের প্রতিটিতে প্রায় n তুলনা করে। দশ লাখ জিনিসে n² ÷ 2 প্রায় 5 × 10¹¹টি তুলনা (সেকেন্ডে একশো কোটি হলে কয়েক মিনিট), অথচ n log₂ n প্রায় 2 × 10⁷ (এক সেকেন্ডের পঞ্চাশ ভাগের এক ভাগ)। কম্পিউটারের গতির চেয়ে কাজ কীভাবে বাড়ে তা বেশি গুরুত্বপূর্ণ।
প্রত্যাশিত ফলাফল
১৬ আর ৩২টি কার্ডের তুলনার ফলাফলের সারণি, একটি বৃদ্ধির গ্রাফ আর অ্যালগরিদমের দক্ষতা নিয়ে একটি ছোট নোট।
যে দক্ষতা গড়ে ওঠে
- অ্যালগরিদমিক চিন্তা
- গোনা আর বৃদ্ধির হার
- নিয়ম মানায় নির্ভুলতা
- দলগত কাজ
মূল্যায়নের মানদণ্ড
- অ্যালগরিদম ঠিকভাবে অনুসরণ করা হয়েছে।
- তুলনা সঠিকভাবে গোনা হয়েছে।
- ১৬ থেকে ৩২টি কার্ডে বৃদ্ধি ব্যাখ্যা করা হয়েছে।
- দশ লাখ জিনিসের আন্দাজ যুক্তিসঙ্গত।
এক্সটেনশন চ্যালেঞ্জ
অ্যালগরিদমগুলোর একটি পাইথন বা ব্লক ভাষায় লেখো, স্বয়ংক্রিয়ভাবে তুলনা গোনো আর ১০ থেকে ১,০০০ জিনিসের তালিকার জন্য গ্রাফ আঁকো।
নিরাপত্তা ও অন্তর্ভুক্তি
বিশেষ কোনো নিরাপত্তার প্রয়োজন নেই। নিয়ম যাতে ঠিকভাবে মানা হয় সেজন্য কাজটি শান্তভাবে করবে।