আসুন এক অন্যরকম ভূতের রাজ্যে পা বাড়াই -৩

পূর্বের পর্বগুলো পড়ে আসার অনুরোধ রইলো

এখন তাহলে শেষ পর্বটি শুরু করা যাক । আজকের বিষয় হচ্ছে কিভাবে এসিএম(ACM) শুরু করা যায়। যদিও এসিএম(ACM) জগৎ অনেক বিশাল তবুও এসিএম(ACM) শুরু করার জন্যে নিচের তালিকাগুলো নতুনদের জন্য যথেষ্ট। তাহলে আর কথা না বাড়িয়ে শুরু করা যাক  ।

এসিএম(ACM) এর বিষয়গুলোকে নিম্নোক্ত অংশে ভাগ করা যায়

  • অ্যাড হোক (Add Hoc)
  • গনিত (Mathmatics)
  • সিমুল্যাশন (Simulation)
  • স্ট্রিং প্রসেসিং (String Processing)
  • সার্চ (Searching)
  • সর্টিং (Sorting)
  • গণনীয় জ্যামিতি (Computational Geometry) 
  • গ্রাফ (Graph)
  • ডাইনামিক প্রোগ্রামিং (Dynamic Programming)

এসিএম(ACM) করার সময় আপনাকে প্রায়  ব্রুট ফোর্স(Brute Force) এর নাম শুনতে হবে।ব্রুট ফোর্স(Brute Force) হচ্ছে সম্ভাব্য সকল সম্ভাবনা যাচাই করা । যেমনঃ ধরুন আপনি প্রাইম সংখ্যা বের করতে চাচ্ছেন। আপনাকে প্রদত্ত সংখ্যাটিকে অন্যান্য সংখ্যা দিয়ে যাচাই করে দেখতে হবে যে প্রদত্ত সংখ্যাটি বিভাজনসাধ্য কিনা। এখানে আপনি সম্ভাব্য সকল সম্ভাবনা যাচাই করে দেখছেন।

অ্যাড হোক (Add Hoc)

যারা এসিএম(ACM) শুরু করবেন বা ইতিমধ্যে  শুরু করে ফেলেছেন, তাদেরকে অ্যাড হোক (Add Hoc) দিয়ে শুরু উচিত। অ্যাড হোক (Add Hoc) মানে হলো  যেই প্রব্লেমগুলোকে কোন ক্যাটাগরিতে ফেলা যায় না মানে তারা পূর্বনির্ধারিত কোন অ্যালগরিদমকে অনুসরন করে না। তাই বলে সব অ্যাড হোক (Add Hoc) সহজ হবে এমন কোন নিশ্চয়তা নেই কিন্তু অ্যাড হোক (Add Hoc) অন্যান্য সমস্যাগুলোর তুলনায় তুলনামুলক ভাবে সহজ হয়। ইউভিএ (UVA) তে কোনগুলো অ্যাড হোক (Add Hoc) তা জানার  জন্যে ভালো একটি ওয়েবসাইট রয়েছে

এই ওয়েবসাইটি আপনাকে অ্যাড হোক (Add Hoc) এর পাশাপাশি অন্যান্য বিভাগের সমস্যাগুলো খুঁজতে সাহায্য করবে ।

গনিত (Mathmatics)

এই বিভাগের মধ্যে রয়েছে

  • প্রাইম নাম্বার (Prime Number)
  • বিগ ইন্টিজার (Big Integer)
  • বিন্যাস (Permutation)
  • নাম্বার থিওরি (Number Theory)
  • ফ্যাক্টোরিয়াল (Factorial)
  • ফিবোনাক্কি (Fibonacci)
  • সিকুয়েন্স (Sequences)
  • মডুলাস (Modulus)

নতুনদের অবশ্যই গ.সা.গু(GCD) জানা প্রয়োজন। গ.সা.গু(GCD) অনেক সমস্যা সমাধানে প্রয়োজন হয়। তারপর প্রাইম নাম্বারের জন্যে সীভ (SIEVE) জানা লাগবে ।

সিমুল্যাশন (Simulation)

এই বিভাগের সমস্যাগুলো সমাধান করার জন্যে ধাপে ধাপে এগুতে হয়। সিমুল্যাশন (Simulation) এর মধ্যে একটি হচ্ছে জসেফাস(Josephus) । জসেফাস(Josephus) অনেক মজার একটি অ্যালগরিদম। উইকিপেডিয়াতে সার্চ দিলে পেয়ে যাবেন । ইউভিএ (UVA) তে অনেক সমস্যা রয়েছে জসেফাস(Josephus) কে নিয়ে ।

স্ট্রিং প্রসেসিং (String Processing)

ইউভিএ (UVA) তে অ্যাড হোক (Add Hoc) বিভাগে অনেক স্ট্রিং প্রসেসিং সম্পর্কিত সমস্যা রয়েছে কিন্তু লাইটোজে(LightOJ) সহজ স্ট্রিং প্রসেসিং সম্পর্কিত কোন সমস্যা নেই তবে অ্যাডভান্স স্ট্রিং প্রসেসিং সম্পর্কিত সমস্যা রয়েছে।

কিছু অ্যাডভান্সড মানের স্ট্রিং প্রসেসিং

  • সাফিক্স অ্যারে (Suffix Array)
  • কনুথ-মরিস-প্রাত (Knuth-Morris-Pratt )

কিছু সাধারণ মানের স্ট্রিং প্রসেসিং

  • স্ট্রিং ম্যাচিং (String Matching)
  • প্যাটার্ন ম্যাচিং (Pattern Matching)

সার্চ (Searching)

সার্চের মধ্যে অনেক ধরনের সার্চ রয়েছে

  • লিনিয়ার সার্চ (Linear Search)
  • বাইনারি সার্চ (Binary Search)
  • বাইনারি সার্চ ট্রি (Binary Search Tree[BST])

সর্টিং (Sorting)

সর্টিংয়ের  মধ্যে রয়েছে

  • বাবল সর্ট (Bubble Sort)
  • কুইক সর্ট (Quick Sort)
  • মার্জ সর্ট (Merge Sort)
  • সিলেকশন সর্ট (Selection Sort)
  • ইন্সারসন সর্ট (Insertion Sort)
  • রেডিক্স সর্ট (Radix Sort)
  • বাকেট সর্ট (Bucket Sort)

এদের মধ্যে কুইক সর্ট আর মার্জ সর্ট খুব দ্রুত কাজ করে বাকিদের তুলনায়।

গণনীয় জ্যামিতি (Computational Geometry) 

কন্টেস্টে অন্যতম কঠিন বিষয় হচ্ছে জ্যামিতি ।

গণনীয় জ্যামিতির  মধ্যে উল্লেখযোগ্য

  • কনভেক্স হূল (Convex Hull)

গ্রাফ (Graph)

গ্রাফের মধ্যে  উল্লেখযোগ্য হচ্ছে

  • ট্রাভারসাল (Traversal)
  • ফ্লাড ফীল (Flood Fill)
  • ফ্লয়েড ওয়ারসাল (Floyed Warshal)
  • এমএসটি (MST)
  • ম্যাক্স বাইপারটিট ম্যাচিং (Max Bipertite Matching)
  • নেটওয়ার্ক ফ্লো (Network Flow)
  • অ্যারটিকুলেশন পয়েন্ট (Articulation Point) 

ডাইনামিক প্রোগ্রামিং (Dynamic Programming)

ডাইনামিক প্রোগ্রামিংয়ের মধ্যে উল্লেখযোগ্য

  • লংগেস্ট কমন সাবসিকুয়েন্স (Longest Common Subsequence [LCS])
  • লংগেস্ট ইঙ্ক্রেজিং সাবসিকুয়েন্স (Longest Increasing Subsequence [LIS])
  • এডিট ডিস্টেন্স (Edit Distance)
  • ০/১ ন্যাপ্সাক (0/1 Knapsack)
  • কয়েন চ্যাঞ্জ (Coin Change)
  • ম্যাট্রিক্স চেইন মালটিপ্লিকেশন (Matrix Chain Multiplication[MCM])
  • ম্যাক্স ইন্টারভাল সাম (Max Interval Sum [MIS])

এখানে শুধু ধারনা দেয়া হয়েছে যে নতুনদেরকে কোন কোন অ্যালগরিদম শিখে সামনে আগাতে হবে । তবে একটি কথা আপনাদের অবশ্যই মাথায় রাখতে হবে সমস্যায় কখনই সরাসরি বলা থাকবে না যে কোন অ্যালগরিদম ব্যবহার করতে হবে । সমস্যাকে সমাধান করতে কোন অ্যালগরিদম ব্যবহার করতে হবে তা আপনাকে সিধান্ত নিতে হবে।

নতুনদের জন্যে ক্রম অনুসারে বিষয়গুলো উল্লেখ করা হল

  • গ.সা.গু (GCD)
  • ল.সা.গু (LCM )
  • প্রাইম জেনারেশন (Prime Generation[Sieve of Eratosthenes] )
  • প্রাইম ফ্যাক্টরাইজেশন (Prime Factorization)
  • বাবল সর্ট (Bubble sort)
  • ইন্সারসন সর্ট (Insertion Sort)
  • সিলেকশন সর্ট (Selection Sort)
  • কুইক সর্ট (Quick Sort)
  • মার্জ সর্ট (Merge Sort)
  • লিনিয়ার সার্চ (Linear Search)
  • বাইনারি সার্চ (Binary search)
  • ফ্যাক্টোরিয়াল (Factorial)
  • ফিবোনাক্কি (Fibonacci)
  • লিঙ্কড লিস্ট (Link List)
  • স্ট্যাক (Stack)
  • কিউ (Queue)

নতুনদের লজিকের উপরে বেশি গুরুত্ব দেয়া উচিত । উপরের উল্লেখিত বিষয়গুলো শিখে সমস্যার সমাধানে ব্যবহার করতে থাকুন।যতো অনুশীলন করবেন ততো পারদর্শী হবেন। উপরোক্ত বিষয়গুলো যখন ভালোভাবে রপ্ত করে ফেলবেন তখন  গ্রাফ নিয়ে বসবেন এরপর শুরু করবেন ডাইনামিক প্রোগ্রামিং।

এখন চলুন তাহলে জেনে নেই সমস্যা পেলে তার সমাধানের দিকে কিভাবে আগাবেন । যখন কোন সমস্যা পাবেন তখন ভালো মত একবার পড়বেন। যদি প্রথমবার পড়ে কিছু না বুঝেন তাহলে আবারও পড়বেন (পড়ার কোন বিকল্প নেই)।

কিন্তু সমস্যায় কি চাওয়া হচ্ছে যখন বুঝে যাবেন তখন স্যাম্পল ইনপুট আউটপুট বিভাগে গিয়ে ইনপুট এর সাথে অউটপুট মিলাতে যাবেন, যে কিভাবে উল্লেখিত ইনপুটের  সাপেক্ষে উল্লেখিত আউটপুট আসছে । যদি তা ধরে ফেলতে পারেন তাহলে আগে খাতায় সুডো কোড লিখে ফেলবেন।তারপর কোড করতে বসবেন। এটি অনেক ভালো অভ্যাস। এমন অনেক সমস্যা পাবেন যেগুলো আপনি খাতায় সিমুল্যাট না করে কখনই মিলাতে পারবেন না। সমস্যার সমাধান করতে থাকলে এক পর্যায়ে আপনি সমস্যা দেখা মাত্রই বলে ফেলতে পারবেন যে কোন অ্যালগরিদম দিয়ে সমাধান করতে হবে।কিন্তু এর জন্যে প্রয়োজন পরিশ্রম আর ধৈর্য।এসিএম(ACM) এ অ্যালগরিদমের শেষ নেই এবং একজনের পক্ষে সব জানা কিংবা সব বিভাগে পারদর্শী হওয়া সম্ভব নয়।

এখানে আমরা হীরক রাজার দেশে ছবিটার মগজ ধোলাইয়ের সুত্র প্রয়োগ করতে পারি

জানার কোন শেষ নাই, জানার চেষ্টা বৃথা তাই

সুতরাং যে বিভাগ আপনি ভালো বুঝবেন বা আপনার কাছে মজাদার বলে মনে হবে সে বিভাগে বেশি মনোযোগ দিবেন। অনেক কথা হলো এবার আর বসে না থেকে শুরু করে দিন সমস্যার সমাধান আর ঢুকে পরুন এক অন্যরকম ভূতের রাজ্যে। এই অন্যরকম ভূত পারবে আপনাকে সাফল্যের উচ্চ শিখরে নিয়ে যেতে।

বিঃ দ্রঃ

কোন বানান,উক্তি,চিন্তা ইত্যাদি ভুল লিখে ফেললে দয়া করে কমেন্টে সঠিক অংশগুলো উল্লেখ করে দিবেন কারন মানুষ মাত্রই ভুল।


লেখকের অনুমতি ব্যাতিত প্রোগ্রামিংয়ের চাক থেকে লেখা অনুলিপন করা আইনত দণ্ডনীয়।

৯২২ বার মোট দেখা হয়েছে ১ বার আজ দেখা হয়েছে

মন্তব্য সমূহ