পাইথন দিয়ে প্রোগ্রামিং শেখা ৩য় খণ্ড : ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি

ভূমিকা

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

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

এই বইটি রিভিউ করেছেন তাহমিদ রাফি, আবু আশরাফ মাসনুন, তানভীরুল ইসলাম, শহীদুল ইসলাম (সুমন), রুহুল আমীন (সজীব)। তাঁরা বেশ কিছু ভুলত্রুটি বের করার পাশাপাশি অনেক পরামর্শও দিয়েছেন, যা বইটিকে সমৃদ্ধ করেছে। তাই তাদের কাজে আমি কৃতজ্ঞ এবং পাশাপাশি পাঠকদের পক্ষ থেকেও তাঁরা বিশেষ ধন্যবাদ প্রাপ্য।

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

বইটি সম্পর্কে যে-কোনো মতামত ও পরামর্শ দিতে চাইলে আমাকে ইমেইল করা যাবে book@subeen.com ঠিকানায়।

তামিম শাহ‍্‍রিয়ার সুবিন,
আগস্ট ২০১৭।

 

সূচীপত্র

ভূমিকা

লেখক পরিচিতি

অধ্যায় ১ : ডেটা স্ট্রাকচার (Data Structure) ও অ্যালগরিদম (Algorithm)

• ডেটা স্ট্রাকচার (Data Structure)
• অ্যালগরিদম (Algorithm)
• ডেটা স্ট্রাকচার ও অ্যালগরিদম কেন শিখব?
• বইটি কাদের জন্য এবং কীভাবে পড়তে হবে?

অধ্যায় ২ : টাইম ও স্পেস কমপ্লেক্সিটি (Time & Space Complexity)

• টাইম কমপ্লেক্সিটি (Time Complexity)
• স্পেস কমপ্লেক্সিটি (Space Complexity)
• কিছু উদাহরণ

অধ্যায় ৩ : কোড টেস্ট করার পদ্ধতি

• প্রথম পদ্ধতি
• assert-এর ব্যবহার
• ইউনিট টেস্টিং

অধ্যায় ৪ : সার্চিং অ্যালগরিদম (Searching Algorithm)

• লিনিয়ার সার্চ (Linear search)
• বাইনারি সার্চ (Binary Search)

অধ্যায় ৫ : সর্টিং অ্যালগরিদম (Sorting Algorithm)

• সিলেকশন সর্ট (Selection sort)
• বাবল সর্ট (Bubble sort)
• ইনসার্শন সর্ট (Insertion sort)

অধ্যায় ৬ : স্ট্যাক (Stack) ও কিউ (Queue)

• স্ট্যাক (Stack)
• কিউ (Queue)

অধ্যায় ৭ : লিংকড লিস্ট (Linked List)

• লিংকড লিস্টের ধারণা
• পাইথন দিয়ে লিংকড লিস্ট তৈরি
• ডবলি লিংকড লিস্ট
• লিংকড লিস্টের ব্যবহার

অধ্যায় ৮ : রিকার্শন

অধ্যায় ৯ : ট্রি (Tree)

• বাইনারি ট্রি
• ট্রি ট্রাভার্স করা

অধ্যায় ১০ : বাইনারি সার্চ ট্রি

অধ্যায় ১১ : হিপ, হিপ সর্ট ও প্রায়োরিটি কিউ

• হিপ
• হিপ সর্ট
• প্রায়োরিটি কিউ (Priority Queue)

অধ্যায় ১২ : হ্যাশ টেবিল

অধ্যায় ১৩ : আরো সর্টিং অ্যালগরিদম

• মার্জ সর্ট
• কুইক সর্ট (Quick Sort)
• কাউন্টিং সর্ট

অধ্যায় ১৪ : পাইথনের বিল্ট-ইন ডেটা স্ট্রাকচার

পরিশিষ্ট

• গাণিতিক রাশির মান নির্ণয়
• ইনফিক্স থেকে পোস্টফিক্সে রূপান্তর