চূড়ান্ত প্রকল্প — একাধিক ক্ষেত্র একত্র করে বাস্তব সমস্যা সমাধান

১ · প্রকল্পের প্রেক্ষাপট

কল্পনা করুন একটি ছোট ডেলিভারি কোম্পানি ৬টি শহরের মধ্যে একটি রুট ও যোগাযোগ ব্যবস্থা পরিচালনা করে — এবং তাদের তিনটি ভিন্ন গাণিতিক প্রশ্নের উত্তর দরকার: (১) তাদের রোড নেটওয়ার্কে কি এমন একটি রুট আছে যা প্রতিটি রাস্তা ঠিক একবার ব্যবহার করে? (২) তাদের ডেলিভারি সিস্টেমে বার্তা কীভাবে নিরাপদে এনক্রিপ্ট করা হয়? (৩) সব শহর পরিদর্শনের সর্বোত্তম ক্রম খুঁজতে কতটা কম্পিউটেশনাল কাজ লাগবে? আমরা এই তিনটি প্রশ্নের প্রতিটিকে এই কোর্সের একটি নির্দিষ্ট মডিউলের গণিত দিয়ে সমাধান করব।

২ · ধাপ ১ (M4, গ্রাফ থিওরি) — ইউলার পথ যোগ্যতা

৬টি শহর — ঢাকা, চট্টগ্রাম, সিলেট, রাজশাহী, খুলনা, বরিশাল — একটি চক্র (cycle) আকারে সংযুক্ত (ঢাকা→চট্টগ্রাম→ সিলেট→রাজশাহী→খুলনা→বরিশাল→ঢাকা), প্লাস একটি অতিরিক্ত সরাসরি রাস্তা ঢাকা-রাজশাহী (দ্রুত রুটের জন্য)। মোট $V=6$টি শহর, $E=7$টি রাস্তা।

L20-এর ইউলার থিওরেমEuler's Theoremএকটি কানেক্টেড গ্রাফে ইউলার সার্কিট থাকে যদি প্রতিটি ভার্টেক্সের ডিগ্রি জোড় হয়; ঠিক ২টি বিজোড়-ডিগ্রি ভার্টেক্স থাকলে ইউলার পথ (সার্কিট নয়) থাকে। স্মরণ করুন: কানেক্টেড গ্রাফে ইউলার সার্কিট থাকে যদি প্রতিটি ভার্টেক্সের ডিগ্রি জোড় হয়; ঠিক ২টি বিজোড়-ডিগ্রি ভার্টেক্স থাকলে ইউলার পথ (সার্কিট নয়) থাকে; ২-এর বেশি বিজোড়-ডিগ্রি ভার্টেক্স থাকলে কোনোটিই সম্ভব নয়। অতিরিক্ত ঢাকা-রাজশাহী রাস্তাটি ঠিক এই দুটি শহরের ডিগ্রি ১ বাড়িয়ে জোড় থেকে বিজোড় করে দেয় — বাকি চারটি শহর জোড়-ডিগ্রিই থেকে যায়। নিচের কোড এই ডিগ্রি-চেক লাইভ চালিয়ে নিশ্চিত করবে ঢাকা ও রাজশাহীর মধ্যে একটি ইউলার পথ (প্রতিটি রাস্তা ঠিক একবার ব্যবহার করে) সম্ভব কি না।

৩ · ধাপ ২ (M5, নাম্বার থিওরি) — RSA এনক্রিপশন (L28 পুনর্ব্যবহার)

কোম্পানির ডেলিভারি অর্ডার নম্বর নিরাপদে পাঠাতে আমরা ঠিক L28-এর টয় RSA উদাহরণ পুনর্ব্যবহার করব — একই প্রাইম-জোড়া থেকে আসা $n=3233$, পাবলিক এক্সপোনেন্ট $e=17$, প্রাইভেট এক্সপোনেন্ট $d=2753$ (যেখানে $\varphi(3233)=3120$ এবং $17 \times 2753 \equiv 1 \pmod{3120}$, L28-এ যাচাই করা হয়েছিল)। বার্তা $m=65$ এনক্রিপ্ট করতে $c = m^e \bmod n$ এবং ডিক্রিপ্ট করতে $m = c^d \bmod n$ — কোড সেলে pow(m, e, n) ও pow(c, d, n) দিয়ে লাইভ গণনা করে দেখানো হবে ডিক্রিপ্ট করা মান ঠিক মূল বার্তায় ফিরে আসে কি না।

৪ · ধাপ ৩ (M3, কম্বিনেটরিক্স) — রুট অর্ডারিং গণনা

কোম্পানি যদি প্রতিদিন ৬টি শহরের সবগুলোতেই ডেলিভারি দিতে চায় এবং সবচেয়ে ছোট (দ্রুততম) রুট খুঁজতে চায়, তাহলে L13-এর পারমুটেশন গণনা অনুযায়ী সম্ভাব্য ভ্রমণ-ক্রমের সংখ্যা $6! = 720$টি। এটি নিজে থেকে বড় সংখ্যা মনে না হলেও — L39 স্মরণ করুন — শহরের সংখ্যা সামান্য বাড়লেই ($n=15$-এ $15! \approx 1.3 \times 10^{12}$) এই সংখ্যা কম্পিউটেশনালি অসম্ভব হয়ে যায়। এই "সব রুট চেষ্টা করে সেরাটা বাছাই" সমস্যাটিই আসলে Traveling Salesman Problem (TSP)-এর decision version — যা L42-এ দেখা হয়েছে NP-সম্পূর্ণ।

৫ · ধাপ ৪ (M8, অ্যালগরিদম বিশ্লেষণ) — প্রতিটি ধাপের Big-O

৬ · সম্পূর্ণ কোড — তিনটি ধাপই একসাথে

নিচের কোড সেল তিনটি ধাপই চালিয়ে একটি "চূড়ান্ত রিপোর্ট" তৈরি করে — ঠিক যেমন একটি বাস্তব সিস্টেম করত।

import math
from collections import defaultdict

# ============ ধাপ ১ · গ্রাফ থিওরি (M4) — ইউলার পথ যাচাই ============
cities = ["Dhaka", "Chittagong", "Sylhet", "Rajshahi", "Khulna", "Barisal"]
roads = [
    ("Dhaka", "Chittagong"), ("Chittagong", "Sylhet"), ("Sylhet", "Rajshahi"),
    ("Rajshahi", "Khulna"), ("Khulna", "Barisal"), ("Barisal", "Dhaka"),
    ("Dhaka", "Rajshahi"),   # অতিরিক্ত দ্রুত-রুট রাস্তা
]

degree = defaultdict(int)
for u, v in roads:
    degree[u] += 1
    degree[v] += 1

odd_degree_cities = [c for c in cities if degree[c] % 2 == 1]
V, E = len(cities), len(roads)

print("=== ধাপ ১ · গ্রাফ থিওরি (M4) — ইউলার পথ যাচাই (L20) ===")
for c in cities:
    print(f"  {c}: degree {degree[c]}")
print("বিজোড়-ডিগ্রি শহর:", odd_degree_cities)

if len(odd_degree_cities) == 0:
    euler_result = "প্রতিটি রাস্তা ঠিক একবার ব্যবহার করে ইউলার সার্কিট সম্ভব।"
elif len(odd_degree_cities) == 2:
    euler_result = f"{odd_degree_cities[0]} থেকে {odd_degree_cities[1]} পর্যন্ত ইউলার পথ সম্ভব (সার্কিট নয়)।"
else:
    euler_result = "কোনো ইউলার পথ সম্ভব নয় — ২-এর বেশি বিজোড়-ডিগ্রি ভার্টেক্স আছে।"
print("ফলাফল:", euler_result)

# ============ ধাপ ২ · নাম্বার থিওরি (M5) — RSA (L28-এর ঠিক একই সংখ্যা) ============
n, e, d = 3233, 17, 2753
message = 65
ciphertext = pow(message, e, n)
decrypted = pow(ciphertext, d, n)

print("\n=== ধাপ ২ · নাম্বার থিওরি (M5) — RSA এনক্রিপশন (L28 পুনর্ব্যবহার) ===")
print(f"পাবলিক কী (n,e) = ({n},{e}) | প্রাইভেট কী d = {d}")
print(f"বার্তা m = {message}  ->  সাইফারটেক্সট c = {ciphertext}  ->  ডিক্রিপ্ট = {decrypted}")
assert decrypted == message, "RSA রাউন্ড-ট্রিপ ব্যর্থ!"
print("ডিক্রিপশন যাচাই: সফল — RSA সঠিকভাবে কাজ করছে।")

# ============ ধাপ ৩ · কম্বিনেটরিক্স (M3) — রুট অর্ডারিং গণনা (L13) ============
num_cities = len(cities)
num_orderings = math.factorial(num_cities)

print("\n=== ধাপ ৩ · কম্বিনেটরিক্স (M3) — রুট অর্ডারিং গণনা (L13) ===")
print(f"{num_cities}টি শহর ভ্রমণের সম্ভাব্য ক্রম সংখ্যা = {num_cities}! = {num_orderings}")
print(f"(তুলনার জন্য, L39-এর মতো: ১৫টি শহর হলে 15! = {math.factorial(15):,} — ব্যবহারিকভাবে অসম্ভব)")

# ============ ধাপ ৪ · অ্যালগরিদম বিশ্লেষণ (M8) — প্রতিটি ধাপের জটিলতা ============
print("\n=== ধাপ ৪ · অ্যালগরিদম বিশ্লেষণ (M8) — প্রতিটি ধাপের Big-O ===")
print(f"গ্রাফ ডিগ্রি-চেক (V={V}, E={E})         -> O(V + E)")
print("RSA মডুলার এক্সপোনেনশিয়েশন (fast pow) -> O(log e)   [Class P]")
print(f"সব রুট এনুমারেট করা (n={num_cities})           -> O(n!)     [NP-সম্পূর্ণ, decision version]")

# ============ চূড়ান্ত রিপোর্ট ============
print("\n=== চূড়ান্ত রিপোর্ট ===")
print(f"ইউলার পথযোগ্যতা : {euler_result}")
print(f"RSA রাউন্ড-ট্রিপ : সফল (m={message} -> c={ciphertext} -> m={decrypted})")
print(f"রুট বিকল্প সংখ্যা : {num_orderings}")