Discrete math-এর মানচিত্র — কেন কম্পিউটার বিজ্ঞানের ভাষা এটি

১ · “Discrete” মানে কী — সিঁড়ি বনাম ঢাল

একটি বাড়িতে ওপরে ওঠার দুটি পথ ভাবুন। একটি সিঁড়ি, আরেকটি হুইলচেয়ারের ঢাল। সিঁড়িতে আপনি তৃতীয় ধাপে থাকতে পারেন, চতুর্থ ধাপেও, কিন্তু “সাড়ে তিন নম্বর ধাপে” দাঁড়ানোর জায়গা নেই। ঢালে যেকোনো উচ্চতায় থামা যায়: ১.৭ মিটার, ১.৭১ মিটার, ১.৭১৪ মিটার, যত সূক্ষ্ম চান। সিঁড়ি হলো discrete (বিচ্ছিন্ন): মানগুলো আলাদা আলাদা, মাঝখানে ফাঁক। ঢাল হলো continuous (অবিচ্ছিন্ন): দুটি মানের মাঝে সবসময় আরও মান আছে।

দৈনন্দিন জীবনে দুটোই আছে। বাজারঘর নামের একটি কাল্পনিক অনলাইন দোকান (এই কোর্সের চলমান উদাহরণ) একদিনে কয়টি অর্ডার পেল, সেটি discrete: ১৪৭টি হতে পারে, ১৪৭.৫টি নয়। কিন্তু একটি চালের বস্তার ওজন continuous: ২৫ কেজি, ২৫.০৩ কেজি, মাপার যন্ত্র যত সূক্ষ্ম, তত দশমিক। ক্রিকেটে রান discrete; বলের গতি continuous. পরীক্ষার রোল নম্বর discrete; আপনার উচ্চতা continuous.

“গোনা যায়” কথাটির একটি নিখুঁত গাণিতিক রূপ আছে। একটি সেট countable যদি সেটি সসীম হয়, অথবা তার উপাদানগুলোকে ১ম, ২য়, ৩য়… এভাবে একটি তালিকায় সাজানো যায় যাতে প্রতিটি উপাদান কোনো এক জায়গায় আসে। সব পূর্ণসংখ্যার সেট অসীম, কিন্তু countable: 0, 1, −1, 2, −2, 3, … এভাবে তালিকা করা যায়। অথচ সব বাস্তব সংখ্যাকে এমন কোনো তালিকায় আনা যায় না; Georg Cantor ১৮৯১ সালে তাঁর বিখ্যাত diagonal যুক্তিতে এটি দেখান। সেই প্রমাণ আসবে পর্ব ১৮-এ (Cardinality — countable, uncountable আর Cantor-এর diagonal).

কম্পিউটার কেন discrete যন্ত্র

কম্পিউটারের মেমরিতে প্রতিটি ঘরে থাকে 0 অথবা 1; মাঝামাঝি কিছু নয়। ৬৪টি bit দিয়ে ঠিক 2⁶⁴টি আলাদা অবস্থা লেখা যায়, তার বেশি নয়। তাহলে কম্পিউটার দশমিক সংখ্যা রাখে কীভাবে? সসীম একটি সংখ্যার তালিকা থেকে সবচেয়ে কাছেরটি বেছে নিয়ে। এজন্যই Python-এ 0.1 + 0.2 লিখলে আসে 0.30000000000000004: 0.1, 0.2 বা 0.3, এদের কোনোটিই সেই সসীম তালিকায় হুবহু নেই। কম্পিউটারের “বাস্তব সংখ্যা” আসলে বাস্তব সংখ্যার কাছাকাছি একটি বিশাল কিন্তু সসীম, discrete সেট। অংশ ৬-এর Python ব্লকে এর একটি চমকপ্রদ প্রমাণ দেখবেন।

২ · কম্পিউটার বিজ্ঞানের কোথায় এই গণিত

“Discrete math কেন পড়ব?” প্রশ্নের সবচেয়ে ভালো উত্তর হলো একটি তালিকা: কম্পিউটার বিজ্ঞানের প্রায় প্রতিটি শাখা এর কোনো না কোনো অংশের ওপর দাঁড়িয়ে আছে। নিচের সারণিতে বাঁ দিকে গণিতের অংশ, মাঝে সেটি কোথায় কাজে লাগে, আর ডানে এই কোর্সের কোন মডিউলে আসবে।

তিনটি ছোট উদাহরণ, বাজারঘর থেকে

১. যুক্তি: কুপনের নিয়ম। বাজারঘরের ম্যানেজার লিখলেন: “অর্ডার ৫০০ টাকার বেশি এবং গ্রাহক নতুন অথবা কুপন কোড আছে, তাহলে ছাড়।” Programmer দুইভাবে পড়তে পারেন: “(৫০০-এর বেশি এবং নতুন) অথবা কুপন”, কিংবা “৫০০-এর বেশি এবং (নতুন অথবা কুপন)”। তিনটি শর্তের সত্য-মিথ্যার ২ × ২ × ২ = ৮টি সমন্বয়ের মধ্যে দুটিতে এই দুই রকম বোঝার উত্তর আলাদা: যখন অর্ডার ৫০০ টাকার বেশি নয় কিন্তু কুপন আছে। বাস্তবে এর মানে কোনো গ্রাহক ভুলভাবে ছাড় পাবেন, অথবা প্রাপ্য ছাড় পাবেন না। যুক্তির প্রতীক (∧ মানে “এবং”, ∨ মানে “অথবা”) আর বন্ধনী এই দ্ব্যর্থতা দূর করে; পর্ব ০২-এ এটি পুরো truth table দিয়ে দেখবেন।

২. প্রমাণ: “সবসময়” শব্দটির দাম। বাজারঘরের ডেলিভারি সফটওয়্যার শত শত test-এ ঠিক চলল। তবু কি নিশ্চিতভাবে বলা যায় যে এটি সব অর্ডারে ঠিক চলবে? Test কেবল কিছু ইনপুট দেখে; প্রমাণ সব ইনপুটের কথা বলে। DSA কোর্সের পর্ব ০৩ algorithm-এর সঠিকতা প্রমাণের কৌশল দেখায়; এই কোর্স সেই প্রমাণ-লেখার গণিতটি শেখাবে।

৩. গণনা: password কতগুলো। নিরাপত্তার অনেক প্রশ্ন আসলে গণনার প্রশ্ন। ৪ অঙ্কের PIN কতগুলো হতে পারে? প্রতিটি ঘরে ১০টি বিকল্প, চারটি ঘর, তাই ১০ × ১০ × ১০ × ১০ = ১০,০০০টি। এটি গুণের নিয়ম, পর্ব ৩১-এর বিষয়। নিচের ব্লক একই সংখ্যা দুইভাবে বের করে: একবার সব PIN একটি একটি করে তৈরি করে গুনে (brute force), একবার সূত্র দিয়ে। এরপর দেখায় ৮ আর ১২ অক্ষরের password-এ brute force কেন অসম্ভব হয়ে পড়ে। (এই কোর্সের Python ব্লক আপনার ব্রাউজারেই চলে; প্রথমবার চালাতে কয়েক সেকেন্ড লাগতে পারে, কারণ ব্রাউজার তখন Python নামিয়ে আনে।)

from itertools import product
import string

# ৪ অঙ্কের PIN: সব সম্ভাবনা একটি একটি করে তৈরি করে গোনা
pins = list(product("0123456789", repeat=4))
print("PIN, brute force :", len(pins))
print("PIN, formula 10^4:", 10 ** 4)
print("first three:", ["".join(p) for p in pins[:3]])

# ৮ অক্ষরের password: a-z, A-Z, 0-9
alphabet = string.ascii_letters + string.digits
total = len(alphabet) ** 8
print("alphabet size:", len(alphabet))
print("8-char passwords:", total)

# ধরে নেওয়া গতি: সেকেন্ডে 10^9টি চেষ্টা (শুধু হিসাবের জন্য)
days = total / 10 ** 9 / 86400
print("days to try all 8-char :", round(days, 1))
years12 = len(alphabet) ** 12 / 10 ** 9 / 86400 / 365
print("years to try all 12-char:", f"{years12:.2e}")

PIN, brute force : 10000
PIN, formula 10^4: 10000
first three: ['0000', '0001', '0002']
alphabet size: 62
8-char passwords: 218340105584896
days to try all 8-char : 2.5
years to try all 12-char: 1.02e+05

৩ · কোর্সের মানচিত্র — ১৪টি মডিউল

৮৩টি পর্ব একসাথে দেখলে ভয় লাগতে পারে। কিন্তু কাঠামোটি সরল। ভিত্তিতে তিনটি মডিউল: যুক্তি, প্রমাণ, আর সেট-ফাংশন। এগুলো গণিতের “ব্যাকরণ”: সব পরের মডিউল এই ভাষাতেই লেখা। তার ওপর তিনটি ধারা পাশাপাশি চলে: সংখ্যার ধারা, গণনার ধারা, কাঠামোর ধারা। শেষে সব ধারা মেলে গণনার মডেলে, আর সবার শেষে পরীক্ষা ও ইন্টারভিউর প্রস্তুতি।

ছবির প্রতিটি মডিউল কী দেবে, তার সংক্ষিপ্ত তালিকা নিচে। প্রতিটি পর্বের পূর্ণ নাম বাঁ পাশের সূচিপত্রে (ফোনে ওপরের মেনুতে) পাবেন।

মডিউল ১৩-এ finite automaton আর Turing machine-এর শুধু পরিচয় থাকবে। Automata, grammar আর computability নিয়ে পূর্ণ গভীরতার একটি আলাদা “Theory of Computation” কোর্স পরে আসবে।

৪ · আপনার পথ বেছে নিন — তিনটি পড়ার পথ

সবাই একই কারণে discrete math পড়েন না। কেউ বিষয়টি ভিত্তি থেকে বুঝতে চান, কেউ সামনের চাকরির পরীক্ষা বা ইন্টারভিউর জন্য প্রস্তুতি নিচ্ছেন, কেউ programming contest-এ ভালো করতে চান। তিনজনের জন্য কোর্সের ক্রম একটু আলাদা হতে পারে। নিচের stepper-এ “পরে” চেপে তিনটি পথ দেখুন। প্রতিটি পথের তালিকায় পর্বের নম্বর দেওয়া আছে; পর্বগুলোর নাম সূচিপত্রে পাবেন।

ক) বিষয়টি ভিত্তি থেকে বুঝতে
খ) চাকরির পরীক্ষা বা ইন্টারভিউ
গ) programming contest
তিন পথেই শুরু: পর্ব ১–৪

মডিউল ১ → ২ → ৩ (পর্ব ১–১৯)
তারপর ৪ → ৫ আর ৬ → ৭ → ৮
তারপর ৯ → ১০ → ১১
শেষে ১২, ১৩, ১৪
প্রথমবার: "আরও গভীরে" বাদ
দ্বিতীয়বার: সব বাক্স

যুক্তি: পর্ব ২, ৩, ৪, ৬
প্রমাণ: পর্ব ৮, ১০
সেট-ফাংশন: পর্ব ১৪–১৬
গণনা: পর্ব ৩১–৩৪
সম্ভাবনা: পর্ব ৩৮–৪০
সংখ্যা: পর্ব ২০–২২
গ্রাফ: পর্ব ৫৭, ৬০, ৬৩, ৬৫
শেষে: পর্ব ৭৯–৮৩

সংখ্যাতত্ত্ব: পর্ব ২০–২৫
গণনা: পর্ব ৩১–৩৭
Recurrence: পর্ব ৪৪–৫০
সম্ভাবনা: পর্ব ৩৮–৪০
গ্রাফ ও tree: পর্ব ৫৭–৬৮
শেষে: পর্ব ৮৩

১. সংজ্ঞা নিজের ভাষায় লিখুন
২. ছোট উদাহরণ হাতে করুন
৩. Python দিয়ে যাচাই করুন
৪. প্রমাণের প্রতিটি কারণ খুঁজুন
৫. অনুশীলন আর quiz শেষ করুন

৫ · সংজ্ঞা, উপপাদ্য আর প্রমাণ — গণিত পড়ার নিয়ম

গল্পের বইয়ে একটি বাক্য না বুঝলেও এগিয়ে যাওয়া যায়; গণিতে একটি শব্দ ভুল বুঝলে পরের পুরো পাতা ভুল দাঁড়ায়। তাই গণিত পড়ুন কলম-খাতা হাতে, প্রতিটি লাইনে থেমে। এই কোর্সে বারবার কয়েক রকম লেখা পাবেন:

উপপাদ্যের বাইরে আরও দুটি শব্দ দেখবেন: lemma হলো বড় প্রমাণের পথে ব্যবহারের জন্য প্রমাণ করা একটি ছোট সহায়ক ফল, আর corollary হলো একটি উপপাদ্য থেকে প্রায় সরাসরি বেরিয়ে আসা ফল। প্রমাণের শেষের ∎ চিহ্নের (tombstone) অর্থ “প্রমাণ শেষ”; পুরোনো বইয়ে এর জায়গায় লেখা থাকে Q.E.D. (লাতিন “quod erat demonstrandum”, অর্থাৎ “যা দেখানোর ছিল”)।

এবার একটি সংজ্ঞা আর একটি উপপাদ্য ধরে ধরে পড়ি। এটিই এই কোর্সের প্রথম প্রমাণ।

এখন একই প্রমাণ পরিষ্কার আকারে লিখি, যেভাবে খাতায় বা পরীক্ষায় লিখবেন: প্রতিটি ধাপের পাশে তার কারণ।

এই ধাঁচের প্রমাণকে বলে direct proof: শর্ত ধরে নিয়ে সোজা সিদ্ধান্তে পৌঁছানো। আরও দুটি পদ্ধতি আসবে পর্ব ০৮-এ (প্রমাণের পদ্ধতি — direct, contrapositive আর contradiction).

৬ · প্রতীকের প্রাথমিক পরিচয় — আর ৮টি ওয়ার্ম-আপ প্রশ্ন

গণিতের প্রতীক হলো শর্টহ্যান্ড: লম্বা বাক্যকে ছোট আর দ্ব্যর্থহীন করে। এই কোর্সে প্রথম দিন থেকেই যে প্রতীকগুলো দেখবেন, সেগুলো নিচে। প্রতিটি পরে নিজের পর্বে বিস্তারিত আসবে; এখানে শুধু চেনা-পরিচয়।

ওয়ার্ম-আপ: নিজেকে যাচাই করুন

আগে খাতায় উত্তর লিখুন, তারপর নিচের উত্তর আর Python ব্লক মিলিয়ে নিন। ৬টি বা তার বেশি ঠিক হলে আপনি মডিউল ১-এর জন্য তৈরি। কম হলে চিন্তা নেই; প্রতিটি বিষয় পরের পর্বগুলোতে আবার আসবে।

1. ∑_i=1¹⁰ i = ?
2. ⌊7/2⌋ + ⌈7/2⌉ = ?
3. ⌊−3.2⌋ = ?
4. 5! আর 0! কত?
5. 17 mod 5 আর −17 mod 5 কত?
6. 0.5 ∈ ℚ? আর −3 ∈ ℕ?
7. ∑_k=0³ 2^k = ?
8. ১ থেকে ১০০-এর মধ্যে কয়টি সংখ্যা 7 দিয়ে বিভাজ্য?

import math
from fractions import Fraction

print("Q1 sum of 1..10      :", sum(range(1, 11)))
print("Q2 floor(7/2)+ceil(7/2):", math.floor(7 / 2) + math.ceil(7 / 2))
print("Q3 floor(-3.2)       :", math.floor(-3.2))
print("Q4 5!, 0!            :", math.factorial(5), math.factorial(0))
print("Q5 17 mod 5, -17 mod 5:", 17 % 5, -17 % 5)
print("Q6 0.5 as a fraction :", Fraction(0.5))
print("   sqrt(2) as float  :", Fraction(math.sqrt(2)))
print("Q7 2^0+2^1+2^2+2^3   :", sum(2 ** k for k in range(4)))
by_hand = sum(1 for m in range(1, 101) if m % 7 == 0)
print("Q8 multiples of 7    :", by_hand, "| floor(100/7) =", 100 // 7)

Q1 sum of 1..10      : 55
Q2 floor(7/2)+ceil(7/2): 7
Q3 floor(-3.2)       : -4
Q4 5!, 0!            : 120 1
Q5 17 mod 5, -17 mod 5: 2 3
Q6 0.5 as a fraction : 1/2
   sqrt(2) as float  : 6369051672525773/4503599627370496
Q7 2^0+2^1+2^2+2^3   : 15
Q8 multiples of 7    : 14 | floor(100/7) = 14

৭ · Python দিয়ে যাচাই — brute force বনাম প্রমাণ

এই কোর্সের প্রতিটি পর্বে Python ব্লক থাকবে। তাদের কাজ তিনটি: একটি সূত্রকে ছোট n-এ গুনে মেলানো, একটি দাবির বিরুদ্ধে counterexample খোঁজা, আর বড় হিসাব (যেমন 2¹⁰⁰⁰ mod 97) হাতে না করে কম্পিউটারে করা। কিন্তু একটি বিষয় শুরুতেই পরিষ্কার থাকা দরকার: কম্পিউটারের যাচাই কোথায় থামে।

বিখ্যাত একটি উদাহরণ: f(n) = n² + n + 41. n = 0 বসালে 41, মৌলিক। n = 1-এ 43, n = 2-এ 47, n = 3-এ 53: সবই মৌলিক সংখ্যা। এই বহুপদীটি সাধারণত Euler-এর নামে পরিচিত; তিনি ১৭৭২ সালের দিকে এর এই আশ্চর্য ধর্ম লক্ষ করেছিলেন বলে উল্লেখ পাওয়া যায়। কেউ যদি বলেন “f(n) সব n-এর জন্য মৌলিক”, কীভাবে যাচাই করবেন? নিচের stepper দেখুন।

একই পরীক্ষা কোডে। নিচের ব্লক f(n) মৌলিক থাকা পর্যন্ত n বাড়াতে থাকে, প্রথম ব্যর্থতায় থামে, তারপর প্রমাণের ভবিষ্যদ্বাণীটি (41 দিয়ে বিভাজ্যতা) কয়েকটি n-এ মেলায়।

def is_prime(m):
    if m < 2:
        return False
    d = 2
    while d * d <= m:
        if m % d == 0:
            return False
        d += 1
    return True

def f(n):
    return n * n + n + 41

n = 0
while is_prime(f(n)):          # দাবি না ভাঙা পর্যন্ত এগোই
    n += 1
print("prime for every n from 0 to", n - 1)
print("first failure: n =", n, "f(n) =", f(n), "=", 41, "*", f(n) // 41)

hits = sum(is_prime(f(k)) for k in range(100))
print("primes among n = 0..99:", hits, "of 100")

for k in range(1, 5):          # প্রমাণ বলে: f(41k) সবসময় 41 দিয়ে বিভাজ্য
    v = f(41 * k)
    print(f"n = {41 * k:3d}  f(n) = {v:6d}  f(n) % 41 = {v % 41}")

prime for every n from 0 to 39
first failure: n = 40 f(n) = 1681 = 41 * 41
primes among n = 0..99: 86 of 100
n =  41  f(n) =   1763  f(n) % 41 = 0
n =  82  f(n) =   6847  f(n) % 41 = 0
n = 123  f(n) =  15293  f(n) % 41 = 0
n = 164  f(n) =  27101  f(n) % 41 = 0

এখন প্রশ্ন জাগে: অন্য কোনো বহুপদী কি আছে যা সব n-এ মৌলিক দেয়? উত্তর “না”, আর এটি প্রমাণ করা যায়। প্রমাণের ধারণাটি ঠিক উপরের 41-এর কৌশল, শুধু সাধারণ আকারে।

f(n) = n² + n + 41-এ a = 0, p = 41 নিলে ঠিক উপরের stepper-এর শেষ ধাপটি পাই: f(41k) সব সময় 41 দিয়ে বিভাজ্য। প্রমাণ শুধু “মিথ্যা” বলেনি; বলেছে কেন মিথ্যা, আর সেটি সব বহুপদীর জন্য।

আরেকটি বিখ্যাত দাবি: Fermat-এর সংখ্যা

১৬৪০ সালের দিকে Pierre de Fermat লক্ষ করেন যে F_k = 2^2k + 1 সংখ্যাগুলো k = 0, 1, 2, 3, 4-এর জন্য মৌলিক: 3, 5, 17, 257, 65537. তিনি অনুমান করেন যে সব F_k মৌলিক। প্রায় এক শতাব্দী পরে, সাধারণত বলা হয় ১৭৩২ সালে, Leonhard Euler দেখান যে F₅ = 4294967297 = 641 × 6700417. আজ আমাদের কাছে যে হিসাব কয়েক মিলিসেকেন্ডের, Euler-কে তা হাতে করতে হয়েছিল (তিনি কোন কোন ভাজক পরীক্ষা করার দরকার, তা চতুর যুক্তিতে কমিয়ে এনেছিলেন)।

def smallest_factor(m):
    d = 2
    while d * d <= m:
        if m % d == 0:
            return d
        d += 1
    return m                    # কোনো ভাজক নেই: m নিজেই মৌলিক

for k in range(6):
    F = 2 ** (2 ** k) + 1       # Fermat সংখ্যা F_k
    p = smallest_factor(F)
    if p == F:
        print(f"F{k} = {F}  prime")
    else:
        print(f"F{k} = {F} = {p} * {F // p}")

F0 = 3  prime
F1 = 5  prime
F2 = 17  prime
F3 = 257  prime
F4 = 65537  prime
F5 = 4294967297 = 641 * 6700417

৮ · AI-এর যুগে discrete math — সহকারী, বিচারক নয়

আজ যেকোনো AI সহকারীকে একটি প্রমাণ বা একটি গণনার সমস্যা দিলে কয়েক সেকেন্ডে আত্মবিশ্বাসী, সুন্দর করে সাজানো উত্তর আসে। অনেক সময় উত্তরটি ঠিকও থাকে। সমস্যা হলো, ভুল উত্তরও একই আত্মবিশ্বাস আর একই সুন্দর ভাষায় আসে। গণিতে “প্রায় ঠিক” প্রমাণ মানে ভুল প্রমাণ। তাই এই কোর্সের একটি বড় লক্ষ্য: AI-এর লেখা গণিত যাচাই করার দক্ষতা।

AI-এর দেওয়া গণিত হাতে পেলে — যাচাইয়ের চেকলিস্ট

• দাবির শর্ত আর সিদ্ধান্ত আলাদা করে লিখেছি, আর প্রমাণ সঠিক দিকেই এগিয়েছে (উল্টো দাবি নয়)
• প্রতিটি ধাপের কারণ বুঝেছি; কোথাও “স্পষ্টতই” বা “সহজেই দেখা যায়” লিখে ফাঁক রাখা হয়নি
• ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত আমার ক্ষেত্রে সত্যিই খাটে
• ছোট ক্ষেত্রে Python দিয়ে brute force-এ ফল মিলিয়েছি, আর এলোমেলো কিছু ইনপুটেও চালিয়েছি
• সীমার মান (0, 1, ঋণাত্মক, ফাঁকা সেট) বসিয়ে দেখেছি
• কোনো বই বা পেপারের উল্লেখ থাকলে, সেটি সত্যিই আছে কি না নিজে খুঁজে দেখেছি