কমপ্লেক্সিটি থিওরি ও অ্যালগরিদম ডিজাইন

১ · NP-কমপ্লিটনেস চেনা কেন প্র্যাক্টিক্যালি গুরুত্বপূর্ণ

M10/L45-L47-এ আমরা দেখেছিলাম কীভাবে একটি সমস্যা NP-কমপ্লিট প্রমাণ করতে হয় — একটি পলিনমিয়াল-টাইম রিডাকশন দিয়ে। এই পাঠের কেন্দ্রীয় বার্তা হলো: এই স্কিলটি শুধু তাত্ত্বিক পরীক্ষার জন্য নয়, বরং বাস্তব ইঞ্জিনিয়ারিং সময় বাঁচানোর একটি হাতিয়ার। যখন আপনি চিনতে পারেন "এই শিডিউলিং/রাউটিং/ম্যাচিং সমস্যাটি মূলত ছদ্মবেশে TSP/vertex-cover/graph-coloring" (M10/L47) — তখন আপনি জানেন একটি নিখুঁত, দ্রুত সমাধান খোঁজা যুক্তিসঙ্গত সময়ের মধ্যে সম্ভব নয় (M11/L49-এর শক্তিশালী তাত্ত্বিক প্রমাণের ভিত্তিতে) — এবং সরাসরি M11/L50-এর বিকল্পগুলোতে চলে যেতে পারেন: অ্যাপ্রক্সিমেশন, হেউরিস্টিক, বা সমস্যাকে একটি বিশেষ সহজতর সাব-কেসে সীমাবদ্ধ করা।

২ · ডায়নামিক প্রোগ্রামিং — ওভারল্যাপিং সাবপ্রবলেম এড়ানো

M6/L28-এর CYK অ্যালগরিদম ইতিমধ্যে ডায়নামিক প্রোগ্রামিংDynamic Programmingওভারল্যাপিং সাবপ্রবলেমের ফলাফল একবার সংরক্ষণ করে বারবার পুনঃগণনা এড়ানোর একটি অ্যালগরিদম-ডিজাইন টেকনিক।-এর একটি TOC-সংলগ্ন উদাহরণ ছিল — একটি টেবিলে ছোট সাবস্ট্রিং-এর ফলাফল সংরক্ষণ করে বড় সাবস্ট্রিং গণনায় পুনরায় ব্যবহার করা, বারবার পুনঃগণনা এড়িয়ে। এই টেকনিকের মূল অন্তর্দৃষ্টি — একটি সমস্যা ওভারল্যাপিং সাবপ্রবলেম ধারণ করলে (একই সাবপ্রবলেম বারবার সমাধান করার প্রয়োজন হয়), তাহলে সেই ফলাফল একবার সংরক্ষণ করে (memoization বা bottom-up টেবিল দিয়ে) পুনরায় ব্যবহার করাই একটি সত্যিকারের এক্সপোনেনশিয়াল-দেখতে সমস্যাকে গোপনে পলিনমিয়াল বানিয়ে দিতে পারে।

৩ · গ্রিডি অ্যালগরিদম — গতির জন্য অপ্টিমালিটি বিনিময়

M11/L50-এর vertex-cover অ্যাপ্রক্সিমেশন একটি গ্রিডি কৌশলের উদাহরণ ছিল — প্রতিটি ধাপে স্থানীয়ভাবে সবচেয়ে ভালো মনে হওয়া পছন্দ করা, পুরো সমস্যা পুনর্বিবেচনা না করেই। গ্রিডি অ্যালগরিদম দ্রুত কিন্তু সাধারণত নিখুঁত অপ্টিমাল সমাধানের গ্যারান্টি দেয় না — শুধুমাত্র সমস্যার একটি নির্দিষ্ট গাণিতিক structure (যেমন "matroid structure," একটি উন্নত ধারণা, শুধু নামমাত্র উল্লেখ) থাকলেই গ্রিডি প্রমাণিতভাবে সঠিক ফলাফল দেয়।

৪ · কোড দিয়ে যাচাই — LCS: naive exponential বনাম DP

নিচের কোড সেলে longest common subsequence (LCS) সমস্যার দুটি সমাধান তুলনা করা হয়েছে — একই ছোট ইনপুটে, একই সঠিক উত্তর দেয়, কিন্তু recursive-call সংখ্যায় নাটকীয় পার্থক্য।

# LCS -- naive exponential recursion বনাম DP -- একই উত্তর, ভিন্ন খরচ

def lcs_naive(x, y):
    calls = [0]
    def rec(i, j):
        calls[0] += 1
        if i == 0 or j == 0:
            return 0
        if x[i-1] == y[j-1]:
            return 1 + rec(i-1, j-1)
        return max(rec(i-1, j), rec(i, j-1))  # -- ওভারল্যাপিং সাবপ্রবলেম বারবার পুনঃগণনা হয়
    result = rec(len(x), len(y))
    return result, calls[0]

def lcs_dp(x, y):
    calls = [0]
    m, n = len(x), len(y)
    table = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            calls[0] += 1  # প্রতিটি টেবিল-সেল গণনা = একটি "কল" -- প্রতিটি সাবপ্রবলেম ঠিক একবার সমাধান হয়
            if x[i-1] == y[j-1]:
                table[i][j] = 1 + table[i-1][j-1]
            else:
                table[i][j] = max(table[i-1][j], table[i][j-1])
    return table[m][n], calls[0]

pairs = [("ABCBDAB", "BDCABA"), ("AGGTAB", "GXTXAYB"), ("ABCDEFGH", "ACBDEGFH")]
print(f"{'x':>10} {'y':>10} | naive-উত্তর | dp-উত্তর | naive-কল | dp-কল | speedup")
print("-" * 78)
for x, y in pairs:
    a1, c1 = lcs_naive(x, y)
    a2, c2 = lcs_dp(x, y)
    assert a1 == a2, f"গরমিল {x},{y}: {a1} != {a2}"
    print(f"{x:>10} {y:>10} | {a1:>10} | {a2:>7} | {c1:>8} | {c2:>5} | {c1/c2:>6.1f}x")