তত্ত্ব ও গবেষণা

লেসন

1. 01Formal Languages ও Chomsky Hierarchy — ভাষার ক্ষমতার সিঁড়িচারটা স্তরের একটা সিঁড়ি — regular থেকে recursively enumerable পর্যন্ত — যা বলে দেয় একটা ভাষা চিনতে কতটা memory ও কী ধরনের কাঠামো লাগবে; আর কেন lexer আর parser দুইটা আলাদা স্তরে বাস করে।কঠিন১ ঘণ্টাEXPERIMENTBUILD
2. 02Finite Automata — DFA, NFA, ও তাদের সমতুল্যতাDFA আর NFA-র 5-টুপল সংজ্ঞা, subset construction দিয়ে NFA→DFA রূপান্তরের সম্পূর্ণ হাতে-কলমে হিসাব, আর কেন দুইটা একই ভাষা চেনে অথচ একটা লিখতে সহজ, আরেকটা চালাতে।কঠিন১ ঘণ্টা ৫ মিনিটEXPERIMENTBUILD
3. 03Regular Expressions ও Pumping Lemma — ক্ষমতা আর তার সীমাRegex-এর আনুষ্ঠানিক সংজ্ঞা, Thompson's construction দিয়ে regex→NFA, backtracking engine কেন ও কখন exponential সময় নেয় (ReDoS), আর pumping lemma দিয়ে প্রমাণ কোন ভাষা regex দিয়ে কখনোই ধরা সম্ভব না।অ্যাডভান্সড১ ঘণ্টাEXPERIMENTBUILD
4. 04Context-Free Grammar ও Pushdown Automata — Stack যখন MemoryCFG আর pushdown automaton (PDA) একই ক্ষমতার দুই রূপ — DFA-র সসীম state-এর সাথে মাত্র একটা stack যোগ করলেই `0ⁿ1ⁿ`-এর মতো ভাষা চেনা সম্ভব হয়, আর recursive descent parser-এর call stack-ই সেই PDA stack, লুকিয়ে থাকা অবস্থায়।অ্যাডভান্সড১ ঘণ্টা ৫ মিনিটEXPERIMENTBUILD
5. 05Turing Machine — গণনার সবচেয়ে সরল আনুষ্ঠানিক মডেলTape, head, আর একটা সসীম transition table — এই তিনটা জিনিস দিয়ে বানানো একটা যন্ত্র, যাকে বিশ্বাস করা হয় 'গণনাযোগ্য' প্রতিটা কিছু গণনা করতে সক্ষম। আর সেই যন্ত্রেরই একটা বিশেষ সংস্করণ — যেটা নিজের প্রোগ্রাম tape-এ ডেটা হিসেবে পড়ে — আধুনিক কম্পিউটারের জন্মকথা।কঠিন১ ঘণ্টাEXPERIMENTBUILD
6. 06Church-Turing Thesis — যে দাবিটা প্রমাণ করা যায় না, তবু বিশ্বাস করিএকটা দাবি যা কোনো গণিতবিদ কখনো প্রমাণ করতে পারবেন না — 'algorithm' শব্দের স্বজ্ঞাত অর্থে যা গণনাযোগ্য, তা Turing machine দিয়েও গণনাযোগ্য। প্রমাণ নেই, কিন্তু প্রমাণের চেয়ে শক্তিশালী একটা যুক্তি আছে: তিনটা স্বাধীন পথ, একই গন্তব্যে।কঠিন৪৫ মিনিটEXPERIMENT
7. 07Decidability ও The Halting Problem — গণনার তত্ত্বের সবচেয়ে গুরুত্বপূর্ণ প্রমাণগণনার তত্ত্বের একক সবচেয়ে গুরুত্বপূর্ণ প্রমাণ — diagonalization দিয়ে দেখানো যে 'এই প্রোগ্রাম কি থামবে' প্রশ্নের কোনো সাধারণ algorithm নেই, কখনো থাকবেও না। এই একটা প্রমাণই ব্যাখ্যা করে কেন কোনো antivirus নিখুঁত হতে পারে না, আর কেন compiler-এর warning কখনো সম্পূর্ণ নিশ্চিত হয় না।অ্যাডভান্সড১ ঘণ্টা ৫ মিনিটEXPERIMENTBUILD
8. 08Reduction — একবার প্রমাণ করে বারবার ধার করাএকটা কৌশল যা দিয়ে গণনার তত্ত্বের প্রায় প্রতিটা undecidability প্রমাণ হয়, নতুন করে diagonalization না লিখেই — 'যদি আমি B সমাধান করতে পারতাম, আমি A-ও সমাধান করতে পারতাম, তাই B অন্তত A-এর মতোই কঠিন'। এই একই যুক্তি কয়েক লেসন পরে NP-completeness-এর ভিত্তি হয়ে ফিরে আসবে।অ্যাডভান্সড১ ঘণ্টাEXPERIMENTBUILD
9. 09Rice's Theorem — একটা বাক্য যা ডজন ডজন প্রমাণকে অপ্রয়োজনীয় করে দেয়একটা মাত্র উপপাদ্য — একটা প্রোগ্রাম কী করে (তার input-output আচরণ) সম্পর্কে যেকোনো non-trivial প্রশ্নই, ব্যতিক্রমহীনভাবে, undecidable। এই একটা বাক্যই ব্যাখ্যা করে কেন প্রতিটা linter, প্রতিটা static analyzer, প্রতিটা type checker কখনো নিখুঁত হতে পারবে না — বাজে ডিজাইনের কারণে না, গাণিতিক অনিবার্যতার কারণে।অ্যাডভান্সড৫০ মিনিটBUILD
10. 10Complexity Classes — P, NP, PSPACE: সমাধান খোঁজা বনাম যাচাই করাসমাধান খুঁজে বের করা আর হাতে-পাওয়া সমাধান যাচাই করা — এই দুইয়ের মধ্যে পার্থক্যই P আর NP-কে আলাদা করে। Turing machine দিয়ে চারটা class-এর আনুষ্ঠানিক সংজ্ঞা, আর কেন তাদের মধ্যে সম্পর্কটা আজও পুরোপুরি অজানা।অ্যাডভান্সড১ ঘণ্টা ৫ মিনিটEXPERIMENT
11. 11NP-completeness ও Cook-Levin Theorem — একটা সমস্যা যা সবাইকে বহন করে১৯৭১ সালে Stephen Cook (আর স্বাধীনভাবে Leonid Levin) দেখান SAT-ই NP-এর সবচেয়ে কঠিন সমস্যা — আর তারপর হাজার হাজার ভিন্ন সমস্যা মাত্র একটা করে reduction দিয়ে NP-complete প্রমাণিত হয়ে গেছে। এই লেসনে reduction-এর যন্ত্রটা হাতে-কলমে চালানো।রিসার্চ-লেভেল১ ঘণ্টা ১০ মিনিটEXPERIMENTBUILD
12. 12P vs NP-এর তাৎপর্য — একটা প্রমাণ যা পৃথিবী বদলে দিতP = NP প্রমাণিত হলে গণিত, ক্রিপ্টোগ্রাফি, আর optimization-এর জগৎ বদলে যেত — কিন্তু ঠিক কীভাবে, সেটা যতটা মনে হয় তার চেয়ে সূক্ষ্ম। আর কেন এই প্রশ্নটা ৫০ বছরের সেরা প্রচেষ্টাকেও হারিয়ে দিয়েছে, তার পেছনে আছে প্রমাণ-পদ্ধতি নিজের গাণিতিক সীমাবদ্ধতা।কঠিন৪৫ মিনিটEXPERIMENT
13. 13Approximation ও Randomized Complexity — যখন নিখুঁত উত্তর অপেক্ষা করতে পারে নাNP-hard সমস্যার জন্য exact polynomial algorithm সম্ভবত নেই — তাই বাস্তব দুনিয়া তিনটা অস্ত্র ব্যবহার করে: provable-ratio approximation, bounded-error randomization, আর heuristic। আর PCP theorem দেখায় কিছু সমস্যায় 'প্রায় সঠিক' উত্তর খোঁজাও সমান কঠিন।অ্যাডভান্সড১ ঘণ্টাEXPERIMENTBUILD
14. 14Formal Methods — Hoare Logic, Model Checking, TLA+Testing দেখায় bug আছে; formal methods দেখায় bug নেই — কিন্তু শুধু যা আপনি স্পেসিফাই করেছেন তার জন্য। Hoare logic দিয়ে sequential program-এর deductive proof, model checking দিয়ে exhaustive state-space exploration, আর TLA+ দিয়ে distributed protocol স্পেসিফিকেশন — তিনটা ভিন্ন হাতিয়ার, একই লক্ষ্য।অ্যাডভান্সড১ ঘণ্টা ৫ মিনিটEXPERIMENTBUILD
15. 15Lambda Calculus — তিনটা নিয়মে সব গণনাVariable, abstraction, application — মাত্র তিনটা construct, একটা মাত্র reduction rule। ১৯৩৬ সালে কম্পিউটার তৈরি হওয়ার আগেই Alonzo Church দেখিয়েছিলেন এটা দিয়ে যেকোনো কিছু গণনা করা যায় — আর আজকের প্রতিটা `lambda`, arrow function, আর closure তারই সরাসরি বংশধর।অ্যাডভান্সড১ ঘণ্টা ৫ মিনিটEXPERIMENTBUILD
16. 16Type Theory ও Curry-Howard — প্রমাণ আসলে প্রোগ্রামUntyped lambda calculus-এ টাইপ যোগ করলে Ω-এর মতো infinite loop ব্যাকরণগতভাবেই বাতিল হয়ে যায় — আর সেই একই টাইপিং নিয়ম, অবাক করা মিল, ঠিক প্রমাণ-লেখার নিয়মও। একটা type-checker আসলে একটা proof-checker; Coq/Agda/Lean-এ এভাবেই CompCert আর seL4-এর মতো সফটওয়্যার machine-verified হয়।অ্যাডভান্সড১ ঘণ্টাEXPERIMENTBUILD
17. 17Information Theory Basics — তথ্যের একক কীএকটা ফাইল-কম্প্রেসর দাবি করছে 'যেকোনো ফাইল ১ বাইটে সংকুচিত করে দেব, নিশ্চিত' — এটা কেন গাণিতিকভাবে অসম্ভব, আর সংকোচনের প্রকৃত সীমা কোথায়, তার নির্ভুল উত্তর দিয়েছিলেন Claude Shannon ১৯৪৮ সালে একটা মাত্র সংখ্যা দিয়ে — entropy।কঠিন৫৫ মিনিটEXPERIMENTBUILD
18. 18AI/ML Foundations — একদম প্রথম নীতি থেকেMachine learning আসলে data থেকে function approximate করা — জাদু নয়, calculus আর linear algebra। Linear regression শূন্য থেকে derive করে, bias-variance tradeoff সংখ্যায় দেখে, আর সবচেয়ে গুরুত্বপূর্ণ — ML-এর তত্ত্ব এখনো কতটা অসম্পূর্ণ তা সৎভাবে স্বীকার করে।কঠিন১ ঘণ্টা ১০ মিনিটEXPERIMENTBUILD
19. 19কীভাবে Academic Paper পড়তে হয়Paper শুরু থেকে শেষ পর্যন্ত লাইন ধরে পড়া একটা সাধারণ ভুল — practitioner-রা পড়েন উল্টো ক্রমে: abstract, figure, conclusion, তারপর intro। এই লেসন সেই ক্রম, আর একটা systems paper থেকে ঠিক কী বের করে আনতে হয় তা শেখায়।মাঝারি৪০ মিনিটBUILD
20. 20Hypothesis Formation ও Experiment Designএকটা আবছা প্রশ্ন ('index কি query দ্রুত করে?') কীভাবে একটা falsifiable hypothesis-এ রূপান্তর করতে হয় — independent/dependent/confounding variable, control condition, আর কেন pre-registration p-hacking ঠেকানোর একমাত্র নির্ভরযোগ্য উপায়।মাঝারি৪৫ মিনিটEXPERIMENTBUILD
21. 21Benchmarking ও Statistical Analysisadvanced-architecture module-এর benchmarking লেসন CPU-microbenchmark-এর engineering সমাধান দিয়েছিল — এই লেসন সেই একই সংখ্যাগুলোর পেছনের পরিসংখ্যান ব্যাখ্যা করে, সাধারণভাবে: confidence interval, p-value-এর প্রকৃত অর্থ, আর bootstrap resampling — যেকোনো research claim-এ প্রযোজ্য, শুধু CPU benchmark-এ না।কঠিন৫৫ মিনিটEXPERIMENTBUILD
22. 22Reproducibility — আবার চালালে কি একই ফল পাওয়া যায়?একটা documented সংকট — psychology-তে শুরু, এখন ML/CS পর্যন্ত পৌঁছেছে: প্রকাশিত ফলাফলের একটা বড় অংশ আবার চালালে একই উত্তর দেয় না। Reproducibility বনাম replicability-র পার্থক্য, আর নিজের কাজকে reproducible রাখার একটা বাস্তব checklist।মাঝারি৪০ মিনিটEXPERIMENTBUILD
23. 23Technical Writing ও Peer Review — কারিকুলামের শেষ লেসনগবেষণার শেষ, কিন্তু সবচেয়ে গুরুত্বপূর্ণ ধাপ — অন্য মানুষকে বোঝানো। Technical report-এর কাঠামো লেখকের দৃষ্টিতে, অনিশ্চয়তা সততার সাথে লেখার শিল্প, peer review আসলে কী যাচাই করে আর কেন সেটা নিখুঁত না — আর এই পুরো কারিকুলামের একটা যাত্রা-সমাপ্তি।মাঝারি৪৫ মিনিটBUILD

যা যা থাকছে

• Formal languages ও Chomsky hierarchy
• Finite automata — DFA, NFA, equivalence
• Regular expressions ও pumping lemma
• Context-free grammars ও pushdown automata
• Turing machines
• Church-Turing thesis
• Decidability ও the halting problem
• Reductions ও undecidable problems
• Rice's theorem
• Complexity classes — P, NP, co-NP, PSPACE
• NP-completeness ও Cook-Levin
• P vs NP-এর তাৎপর্য
• Approximation ও randomized complexity
• Formal methods — Hoare logic, model checking, TLA+
• Lambda calculus
• Type theory ও Curry-Howard
• Information theory basics
• AI/ML foundations from first principles
• কীভাবে academic paper পড়তে হয়
• Hypothesis formation ও experiment design
• Benchmarking ও statistical analysis
• Reproducibility
• Technical writing ও peer review

প্রজেক্ট