Foundationপ্রথম নীতি থেকে
LEVEL 0লেসন ৮/১৬কঠিন১ ঘণ্টা ৫ মিনিট

Relations — নির্ভরতা, সমতুল্যতা আর ক্রম

Relations, Equivalence and Order

Equivalence relation জিনিসকে শ্রেণিতে ভাগ করে, partial order নির্ভরতা সাজায়, আর transitive closure বলে কোথা থেকে কোথায় পৌঁছানো যায় — তিনটাই প্রতিদিনের সফটওয়্যারে।

এই লেসন শেষে আপনি পারবেন

  • একটা relation-এর reflexive, symmetric, transitive, antisymmetric ধর্ম যাচাই করতে পারবেন
  • Equivalence relation থেকে partition বানাতে পারবেন এবং উল্টোটাও
  • Partial order চিনতে পারবেন এবং topological sort ব্যাখ্যা করতে পারবেন
  • Transitive closure হিসাব করতে পারবেন এবং তার ব্যবহার বলতে পারবেন
  • Database-এর relational model কেন এই নামে তা ব্যাখ্যা করতে পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

এই তিনটা প্রশ্ন একই ধরনের:

  • “এই দুইটা commit কি একই বাগ ঠিক করে?”
  • “এই package install করতে আগে কী কী লাগবে?”
  • “এই microservice থেকে কি ঐ database-এ পৌঁছানো যায়?”

তিনটাই সম্পর্ক নিয়ে প্রশ্ন — জিনিসগুলো নিজে নয়, তাদের মধ্যকার সংযোগ নিয়ে।

গত লেসনে আমরা set শিখেছি: “কী কী আছে”। আজ শিখব relation: “কে কার সাথে কীভাবে যুক্ত”।

আর একটা চমৎকার ব্যাপার হলো — মাত্র চারটা ধর্ম (reflexive, symmetric, antisymmetric, transitive) দিয়ে relation-দের যে শ্রেণিবিভাগ হয়, সেটাই ব্যাখ্যা করে দেয় কেন == আর \< এত আলাদা আচরণ করে, কেন dependency cycle বিপজ্জনক, আর কেন Git-এর history একটা DAG।

মূল ধারণা

Relation কী

গত লেসনে দেখেছি Cartesian product:

A×B={(a,b):a∈A,  b∈B}A \times B = \{(a,b) : a \in A,\; b \in B\}

একটা relation হলো সেই product-এর একটা উপসেট:

R⊆A×BR \subseteq A \times B

(a, b) ∈ R লেখার বদলে সাধারণত লেখা হয় a R b।

উদাহরণ: A = {1, 2, 3}, আর R = “ছোট” সম্পর্ক:

R = { (1,2), (1,3), (2,3) }

A × A-তে ৯টা জোড়া সম্ভব ছিল; R তার মধ্যে ৩টা বেছে নিয়েছে।

তিনভাবে একই জিনিস দেখা

একটা relation R on A = {a, b, c}:

১. জোড়ার set:

R = { (a,b), (b,c), (a,c) }

২. Matrix:

     a  b  c
  a [0  1  1]
  b [0  0  1]
  c [0  0  0]

৩. Directed graph:

  a ──→ b ──→ c
  └──────────↗

তিনটা রূপই সমান দরকারি, আর কোনটা ব্যবহার করবেন তা নির্ভর করে কী হিসাব করতে চান তার উপর:

প্রশ্নসেরা রূপ
a R b কি?matrix বা hash set — O(1)
a-এর সব প্রতিবেশী?adjacency list
Transitive closure?matrix (Warshall) বা graph (DFS)
Memory কম চাই?sparse হলে adjacency list

Level 6-এ graph representation নিয়ে বিস্তারিত দেখব।

চারটা মৌলিক ধর্ম

R একটা relation on set A। চারটা প্রশ্ন করুন:

ধর্মসংজ্ঞাসাধারণ ভাষায়
Reflexive∀a (a R a)প্রত্যেকে নিজের সাথে সম্পর্কিত
Symmetric∀a,b (a R b → b R a)সম্পর্ক দুইমুখী
Antisymmetric∀a,b (a R b ∧ b R a → a = b)দুইমুখী শুধু নিজের সাথে
Transitive∀a,b,c (a R b ∧ b R c → a R c)চেইন সংক্ষিপ্ত হয়

কয়েকটা পরিচিত relation যাচাই করি:

RelationReflSymAntisymTrans
= (সমান)✅✅✅✅
≤✅❌✅✅
\<❌❌✅✅
⊆ (subset)✅❌✅✅
“একই বাড়িতে থাকে”✅✅❌✅
“বন্ধু” (সামাজিক)❌✅❌❌
“সরাসরি নির্ভর করে”❌❌✅❌

শেষ দুইটা লক্ষ্য করুন:

  • বন্ধুত্ব transitive নয় — আমার বন্ধুর বন্ধু আমার বন্ধু নাও হতে পারে
  • সরাসরি নির্ভরতা transitive নয় — A → B → C মানে A সরাসরি C-র উপর নির্ভর করে না (যদিও পরোক্ষভাবে করে)

Equivalence relation — জিনিসকে শ্রেণিতে ভাগ করা

একটা relation equivalence relation যদি সেটা reflexive, symmetric আর transitive — তিনটাই হয়।

স্মরণসূত্র: RST।

উদাহরণ:

  • = — সবচেয়ে মৌলিক
  • “একই সপ্তাহের দিনে জন্ম”
  • a ≡ b (mod n) — modular সমতা
  • “একই connected component-এ” (graph-এ)
  • “একই git commit থেকে এসেছে”

সবচেয়ে গুরুত্বপূর্ণ theorem

Theorem: একটা set-এর উপর equivalence relation আর সেই set-এর partition — এই দুইটা একই জিনিস।

Partition মানে set-কে এমন কিছু অ-খালি, পরস্পর-বিচ্ছিন্ন অংশে ভাগ করা যাদের union পুরো set।

কেন এরা একই? প্রতিটা equivalence relation একটা partition বানায়:

[a]={x∈A:x∼a}(a-এর equivalence class)[a] = \{ x \in A : x \sim a \} \qquad \text{(a-এর equivalence class)}

আর প্রতিটা partition একটা equivalence relation বানায়: “একই অংশে আছে”।

উদাহরণ — mod 3:

ℤ কে ভাগ করে তিনটা class-এ:

[0] = { …, −6, −3, 0, 3, 6, … }
[1] = { …, −5, −2, 1, 4, 7, … }
[2] = { …, −4, −1, 2, 5, 8, … }

তিনটা class পরস্পর-বিচ্ছিন্ন, আর একসাথে পুরো ℤ ঢাকে। ✓

Partial order — নির্ভরতার গণিত

একটা relation partial order যদি সেটা reflexive, antisymmetric আর transitive হয়।

Symmetric-এর জায়গায় antisymmetric — এই একটা বদলই সবকিছু পাল্টে দেয়। Equivalence “একরকম” বলে; partial order “আগে-পরে” বলে।

সাধারণত ≼ চিহ্ন ব্যবহার হয়। উদাহরণ:

  • ≤ সংখ্যায়
  • ⊆ set-এ
  • “ভাগ করে” (a | b) পূর্ণসংখ্যায়
  • “task A, task B-এর আগে হতে হবে”
  • Type hierarchy — “A, B-এর subtype”

কেন “partial”?

কারণ কিছু জোড়া অতুলনীয় (incomparable) হতে পারে।

⊆ -এর উদাহরণ: {1,2} আর {2,3} — কোনোটাই অন্যটার subset নয়। এরা তুলনীয় নয়।

যদি প্রতিটা জোড়া তুলনীয় হয়, তখন সেটা total order (বা linear order)। সংখ্যায় ≤ total; set-এ ⊆ শুধু partial।

Hasse diagram

Partial order আঁকার সংক্ষিপ্ত উপায় — reflexive আর transitive edge বাদ দিয়ে শুধু “সরাসরি উপরে” সম্পর্কগুলো আঁকা।

{1,2,3}-এর power set, ⊆ অনুসারে:

              {1,2,3}
             /   |   \
        {1,2}  {1,3}  {2,3}
          | \  /  \  / |
          |  \/    \/  |
          |  /\    /\  |
         {1}   {2}   {3}
           \    |    /
            \   |   /
               ∅

∅ ⊆ {1,2,3} -ও সত্য, কিন্তু আঁকা হয়নি — transitivity থেকে বোঝা যায়।

ভেতরে কী ঘটছে

Transitive closure — “কোথায় পৌঁছানো যায়”

একটা relation R-এর transitive closure R⁺ হলো সবচেয়ে ছোট transitive relation যা R-কে ধারণ করে।

সহজ ভাষায়: a R⁺ b মানে a থেকে b-তে এক বা একাধিক ধাপে পৌঁছানো যায়।

উদাহরণ — package নির্ভরতা:

R (সরাসরি নির্ভরতা):
  app    → express
  express→ body-parser
  body-parser → bytes

R⁺ (সব নির্ভরতা):
  app → express, body-parser, bytes
  express → body-parser, bytes
  body-parser → bytes

npm ls আপনাকে R দেখায়; npm ls --all কার্যত R⁺।

Warshall’s algorithm

Matrix রূপে transitive closure বের করার সবচেয়ে সরল উপায়:

def transitive_closure(M):
    """M: n×n boolean matrix. In-place-এ R⁺ বানায়।"""
    n = len(M)
    for k in range(n):                 # মধ্যবর্তী node
        for i in range(n):
            if not M[i][k]:            # i → k না থাকলে বাদ
                continue
            for j in range(n):
                if M[k][j]:
                    M[i][j] = True
    return M

O(n³)। যুক্তিটা সুন্দর: বাইরের loop-টা বলে “শুধু 0..k node-গুলো মধ্যবর্তী হিসেবে ব্যবহার করলে কোথায় পৌঁছানো যায়” — আর এটা k-এর উপর induction।

DAG আর topological sort

একটা directed graph DAG (Directed Acyclic Graph) যদি তাতে কোনো চক্র না থাকে।

মূল theorem:

একটা directed graph-এর topological sort আছে যদি এবং কেবল যদি সেটা একটা DAG।

কেন cycle থাকলে হয় না: যদি A → B → C → A চক্র থাকে, তাহলে A-কে B-এর আগে, B-কে C-এর আগে, আর C-কে A-এর আগে রাখতে হবে। অর্থাৎ A-কে A-এর আগে রাখতে হবে। অসম্ভব।

Kahn’s algorithm:

from collections import deque

def topo_sort(nodes, edges):
    """edges: dict node → নির্ভরশীলদের list (node আগে হতে হবে)"""
    indeg = {n: 0 for n in nodes}
    for u in nodes:
        for v in edges.get(u, []):
            indeg[v] += 1

    ready = deque(n for n in nodes if indeg[n] == 0)
    order = []

    while ready:
        u = ready.popleft()
        order.append(u)
        for v in edges.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                ready.append(v)

    if len(order) != len(nodes):
        cyclic = [n for n in nodes if indeg[n] > 0]
        raise ValueError(f"চক্র আছে, এই node-গুলো জড়িত: {cyclic}")
    return order

O(V + E)।

একাধিক বৈধ ক্রম — আর সেটাই parallelism

A → C
B → C
C → D

বৈধ ক্রম: A B C D বা B A C D — দুটোই ঠিক।

কারণ A আর B অতুলনীয় — তাদের মধ্যে কোনো নির্ভরতা নেই। তাই তারা সমান্তরালে চালানো যায়।

একটা partial order কোথায় কোথায় কাজ করছে
  1. Makefile-এর নির্ভরতাকোন target আগে
  2. make -j8অতুলনীয় target সমান্তরালে
  3. Package manager (apt, cargo)install ক্রম
  4. Compiler-এর instruction schedulingস্বাধীন instruction পুনর্বিন্যাস
  5. CPU-র out-of-order executiondependency graph দেখে চালায়
  6. Memory orderingকোন write কোনটার আগে দৃশ্যমান

লক্ষ্য করুন — সবচেয়ে নিচের তিনটা স্তরে CPU নিজেই একটা partial order নিয়ে কাজ করছে। Out-of-order execution মানে CPU instruction-দের dependency graph বানিয়ে যেগুলো অতুলনীয় সেগুলো সমান্তরালে চালায়। Level 3 আর Level 11-এ আমরা সেটা দেখব।

Cycle detection — বাস্তবে সবচেয়ে দরকারি

Topological sort ব্যর্থ হলে চক্র আছে। কিন্তু কোন চক্র? ব্যবহারকারীকে সেটা বলতে পারা জরুরি।

def find_cycle(nodes, edges):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {n: WHITE for n in nodes}
    parent = {}

    def dfs(u):
        color[u] = GRAY
        for v in edges.get(u, []):
            if color[v] == GRAY:              # back edge → চক্র
                cycle, cur = [v], u
                while cur != v:
                    cycle.append(cur)
                    cur = parent[cur]
                cycle.append(v)
                return list(reversed(cycle))
            if color[v] == WHITE:
                parent[v] = u
                found = dfs(v)
                if found: return found
        color[u] = BLACK
        return None

    for n in nodes:
        if color[n] == WHITE:
            c = dfs(n)
            if c: return c
    return None

তিনটা রঙের অর্থ:

  • WHITE — এখনো দেখা হয়নি
  • GRAY — বর্তমান DFS path-এ আছে (recursion stack-এ)
  • BLACK — সম্পূর্ণ প্রক্রিয়াকৃত

একটা GRAY node-এ পৌঁছানো মানে back edge — অর্থাৎ চক্র।

উদাহরণ

Union-Find — equivalence class ব্যবস্থাপনা

Equivalence relation-এর সবচেয়ে ব্যবহারিক data structure।

সমস্যা: গতিশীলভাবে জিনিস “একই দলে” ঘোষণা করা হচ্ছে, আর জিজ্ঞেস করা হচ্ছে “এই দুইটা কি একই দলে?”

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))     # শুরুতে প্রত্যেকে নিজের class-এ
        self.rank = [0] * n
        self.count = n                    # কতগুলো আলাদা class

    def find(self, x):
        """x-এর equivalence class-এর প্রতিনিধি"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])   # path compression
        return self.parent[x]

    def union(self, a, b):
        """a আর b কে একই class-এ আনুন"""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                  # আগে থেকেই একই class
        if self.rank[ra] \< self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

    def same(self, a, b):
        return self.find(a) == self.find(b)

তিনটা RST ধর্মই এখানে স্বতঃসিদ্ধভাবে রক্ষিত:

  • Reflexive — same(a, a) সবসময় True, কারণ find(a) == find(a)
  • Symmetric — same(a,b) আর same(b,a) একই হিসাব
  • Transitive — a আর b একই root-এ, b আর c একই root-এ, তাই a আর c-ও একই root-এ

Data structure-টা গাণিতিক ধর্মগুলো গঠনগতভাবে নিশ্চিত করে — আলাদা করে যাচাই করতে হয় না।

Complexity: path compression + union by rank দিয়ে amortized O(α(n)), যেখানে α হলো inverse Ackermann function। বাস্তব সব input-এর জন্য α(n) ≤ 4 — কার্যত ধ্রুবক।

Version control-এর relation

Git-এর commit history একটা DAG — আর এটা বহু জিনিস ব্যাখ্যা করে।

        C ─── D
       /       \
A ─── B         F        (F একটা merge commit)
       \       /
        E ────

R = “সরাসরি parent”। R⁺ = “পূর্বপুরুষ”।

এখন প্রশ্নগুলো relation-এর ভাষায়:

Git প্রশ্নRelation প্রশ্ন
git merge-base D Eসর্বনিম্ন সাধারণ পূর্বপুরুষ
git log A..BB-এর পূর্বপুরুষ বিয়োগ A-এর পূর্বপুরুষ
“এই commit কি release-এ আছে?”commit R⁺ release?
Fast-forward সম্ভব?একটা কি অন্যটার পূর্বপুরুষ?

কেন cycle অসম্ভব: প্রতিটা commit-এর hash তার parent-এর hash অন্তর্ভুক্ত করে। একটা commit নিজের পূর্বপুরুষ হতে হলে তার hash নিজেকে অন্তর্ভুক্ত করতে হতো — যা hash function-এর সংজ্ঞায় অসম্ভব।

গঠনগতভাবে DAG নিশ্চিত — Git-কে আলাদা করে cycle check করতে হয় না। এটা cryptographic hash-এর একটা সুন্দর পার্শ্বফল। Level 10-এ আমরা দেখব blockchain-ও ঠিক এই নীতিতেই চলে।

Antisymmetry ভাঙলে কী হয়

ধরুন আপনি একটা task scheduler লিখছেন, আর কেউ ভুল করে লিখল:

build:
  needs: [test]
test:
  needs: [build]

build ≼ test এবং test ≼ build, কিন্তু build ≠ test। Antisymmetry ভেঙে গেল — এটা আর partial order নয়।

ফলাফল: topological sort অসম্ভব, indeg কখনো শূন্য হয় না, কোনো task কখনো চলে না।

ভালো tool এই অবস্থাটা ধরে ফেলে আর চক্রটা দেখায়:

Error: circular dependency detected
  build → test → build

খারাপ tool infinite loop-এ পড়ে বা deadlock করে।

নিজে চালিয়ে দেখুন

EXPERIMENT

নিজের প্রজেক্টের dependency graph দেখুন

Linux / macOS· ১৫ মিনিট

Node.js প্রজেক্টে:

# সরাসরি নির্ভরতা — এটাই R
cat package.json | python3 -c "import json,sys; d=json.load(sys.stdin); print(len(d.get('dependencies',{})))"

# transitive closure — এটাই R⁺
ls node_modules | wc -l

# গভীরতা দেখুন
npm ls --all --depth=99 2>/dev/null | head -40

সাধারণত ৫টা সরাসরি dependency থেকে ৩০০+ package আসে। R ছোট, R⁺ বিশাল।

Python-এ:

pip install pipdeptree
pipdeptree --graph-output dot > deps.dot
# চক্র থাকলে pipdeptree সতর্ক করে
pipdeptree --warn fail

যেকোনো ভাষায় — নিজে হিসাব করুন:

import json, subprocess
from collections import defaultdict, deque

def load_npm_tree():
    out = subprocess.run(["npm", "ls", "--all", "--json"],
                         capture_output=True, text=True).stdout
    return json.loads(out)

def flatten(node, edges, name=None):
    deps = node.get("dependencies", {})
    for child, sub in deps.items():
        if name:
            edges[name].add(child)
        flatten(sub, edges, child)
    return edges

edges = flatten(load_npm_tree(), defaultdict(set), "ROOT")

# transitive closure — BFS দিয়ে
def reachable(start):
    seen, q = set(), deque([start])
    while q:
        u = q.popleft()
        for v in edges.get(u, ()):
            if v not in seen:
                seen.add(v); q.append(v)
    return seen

direct = edges["ROOT"]
allof  = reachable("ROOT")
print(f"সরাসরি নির্ভরতা (R)      : {len(direct)}")
print(f"সব নির্ভরতা (R⁺)         : {len(allof)}")
print(f"বিস্তার অনুপাত            : {len(allof)/max(len(direct),1):.1f}×")
এটা কী প্রমাণ করে

Transitive closure একটা বিমূর্ত ধারণা নয় — আপনার প্রতিটা প্রজেক্টের ভেতরে একটা বিশাল DAG আছে, আর তার আকার প্রায়ই বিস্ময়কর।

EXPERIMENT

Cycle detection — নিজে ভাঙুন

Python 3· ১০ মিনিট
from collections import deque

def topo_sort(edges):
    nodes = set(edges) | {v for vs in edges.values() for v in vs}
    indeg = {n: 0 for n in nodes}
    for u in edges:
        for v in edges[u]:
            indeg[v] += 1

    ready = deque(sorted(n for n in nodes if indeg[n] == 0))
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in sorted(edges.get(u, [])):
            indeg[v] -= 1
            if indeg[v] == 0:
                ready.append(v)

    if len(order) != len(nodes):
        stuck = sorted(n for n in nodes if indeg[n] > 0)
        raise ValueError(f"চক্র আছে — আটকে থাকা node: {stuck}")
    return order


# ── বৈধ DAG ─────────────────────────────────────────────────
build = {
    "parse":   ["typecheck"],
    "typecheck": ["optimize"],
    "optimize":  ["codegen"],
    "codegen":   ["link"],
    "lint":      ["link"],          # lint স্বাধীন — parse-এর সাথে সমান্তরাল
}
print("ক্রম:", topo_sort(build))

# ── কোনগুলো সমান্তরালে চালানো যায়? ──────────────────────────
def parallel_layers(edges):
    nodes = set(edges) | {v for vs in edges.values() for v in vs}
    indeg = {n: 0 for n in nodes}
    for u in edges:
        for v in edges[u]:
            indeg[v] += 1
    layers, remaining = [], dict(indeg)
    while remaining:
        layer = sorted(n for n, d in remaining.items() if d == 0)
        if not layer:
            raise ValueError("চক্র")
        layers.append(layer)
        for n in layer:
            del remaining[n]
            for v in edges.get(n, []):
                if v in remaining:
                    remaining[v] -= 1
    return layers

print("\nসমান্তরাল স্তর:")
for i, layer in enumerate(parallel_layers(build), 1):
    print(f"  ধাপ {i}: {layer}")

# ── এবার একটা চক্র ঢোকান ────────────────────────────────────
broken = dict(build)
broken["link"] = ["parse"]          # ⚠ চক্র!

try:
    topo_sort(broken)
except ValueError as e:
    print("\nধরা পড়ল:", e)

Output:

ক্রম: ['lint', 'parse', 'typecheck', 'optimize', 'codegen', 'link']

সমান্তরাল স্তর:
  ধাপ 1: ['lint', 'parse']
  ধাপ 2: ['typecheck']
  ধাপ 3: ['optimize']
  ধাপ 4: ['codegen']
  ধাপ 5: ['link']

ধরা পড়ল: চক্র আছে — আটকে থাকা node: ['codegen', 'link', 'optimize', 'parse', 'typecheck']

লক্ষ্য করুন ধাপ ১-এ lint আর parse একসাথে — কারণ তারা অতুলনীয়। এই একটা তথ্যই make -j কে কাজ করতে দেয়।

এবার নিজে চেষ্টা করুন:

  1. এমন একটা graph বানান যেখানে ৩টা স্তরে মোট ১০টা task আছে — speedup কত হবে?
  2. find_cycle যোগ করুন যা শুধু “চক্র আছে” না বলে কোন পথে চক্র সেটা দেখায়
  3. এমন dependency লিখুন যাতে কোনো parallelism সম্ভব নয় (একটা সরলরেখা)
এটা কী প্রমাণ করে

একটা partial order-এ antisymmetry ভাঙলে topological sort অসম্ভব হয়ে যায় — আর ভালো tooling সেটা স্পষ্ট বার্তা দিয়ে জানায়, চুপচাপ ঝুলে থাকে না।

নিজে বানান

BUILD IT

Relation Analyzer

Python · ●●●○○
  1. একটা relation-এর চারটা ধর্ম যাচাই করার function লিখুন
  2. সেই ধর্ম দেখে relation-টা কী ধরনের তা শ্রেণিবদ্ধ করুন
  3. Equivalence relation হলে equivalence class বের করুন
  4. Partial order হলে topological sort করুন
  5. Transitive closure হিসাব করুন এবং তুলনা করুন
from itertools import product
from collections import defaultdict, deque


class Relation:
    def __init__(self, elements, pairs):
        self.E = list(elements)
        self.R = set(pairs)

    def holds(self, a, b):
        return (a, b) in self.R

    # ── চারটা ধর্ম ────────────────────────────────────────────
    def is_reflexive(self):
        return all(self.holds(a, a) for a in self.E)

    def is_irreflexive(self):
        return not any(self.holds(a, a) for a in self.E)

    def is_symmetric(self):
        return all(self.holds(b, a) for a, b in self.R)

    def is_antisymmetric(self):
        return all(a == b for a, b in self.R if self.holds(b, a))

    def is_transitive(self):
        return all(
            self.holds(a, c)
            for a, b in self.R
            for c in self.E
            if self.holds(b, c)
        )

    # ── শ্রেণিবিভাগ ───────────────────────────────────────────
    def classify(self):
        r, s, a, t = (self.is_reflexive(), self.is_symmetric(),
                      self.is_antisymmetric(), self.is_transitive())
        kinds = []
        if r and s and t:  kinds.append("Equivalence relation")
        if r and a and t:  kinds.append("Partial order")
        if r and a and t and self._is_total(): kinds.append("Total order")
        if self.is_irreflexive() and a and t: kinds.append("Strict partial order")
        if not kinds:      kinds.append("(কোনো বিশেষ শ্রেণি নয়)")
        return kinds

    def _is_total(self):
        return all(self.holds(a, b) or self.holds(b, a)
                   for a, b in product(self.E, repeat=2))

    # ── Equivalence class ────────────────────────────────────
    def classes(self):
        if not (self.is_reflexive() and self.is_symmetric() and self.is_transitive()):
            raise ValueError("equivalence relation নয়")
        seen, out = set(), []
        for a in self.E:
            if a in seen: continue
            cls = sorted(b for b in self.E if self.holds(a, b), key=str)
            seen.update(cls)
            out.append(cls)
        return out

    # ── Transitive closure (Warshall) ────────────────────────
    def closure(self):
        idx = {e: i for i, e in enumerate(self.E)}
        n = len(self.E)
        M = [[False]*n for _ in range(n)]
        for a, b in self.R:
            M[idx[a]][idx[b]] = True
        for k in range(n):
            for i in range(n):
                if not M[i][k]: continue
                for j in range(n):
                    if M[k][j]: M[i][j] = True
        pairs = {(self.E[i], self.E[j])
                 for i in range(n) for j in range(n) if M[i][j]}
        return Relation(self.E, pairs)

    # ── Topological sort ─────────────────────────────────────
    def topo(self):
        adj = defaultdict(list)
        indeg = {e: 0 for e in self.E}
        for a, b in self.R:
            if a == b: continue                 # reflexive edge উপেক্ষা
            adj[a].append(b); indeg[b] += 1
        q = deque(sorted((e for e in self.E if indeg[e] == 0), key=str))
        order = []
        while q:
            u = q.popleft(); order.append(u)
            for v in sorted(adj[u], key=str):
                indeg[v] -= 1
                if indeg[v] == 0: q.append(v)
        if len(order) != len(self.E):
            raise ValueError("চক্র আছে — topological sort অসম্ভব")
        return order

    def report(self, name):
        print(f"\n── {name} " + "─" * max(0, 46 - len(name)))
        print(f"  reflexive     : {self.is_reflexive()}")
        print(f"  irreflexive   : {self.is_irreflexive()}")
        print(f"  symmetric     : {self.is_symmetric()}")
        print(f"  antisymmetric : {self.is_antisymmetric()}")
        print(f"  transitive    : {self.is_transitive()}")
        print(f"  → {', '.join(self.classify())}")
        try:
            print(f"  equivalence class: {self.classes()}")
        except ValueError:
            pass
        try:
            print(f"  topological order: {self.topo()}")
        except ValueError as e:
            print(f"  topo: {e}")
        c = self.closure()
        print(f"  |R| = {len(self.R)},  |R⁺| = {len(c.R)}")


# ── উদাহরণ ──────────────────────────────────────────────────
E = [1, 2, 3, 4]

Relation(E, {(a, b) for a in E for b in E if a == b}
         ).report("সমতা (=)")

Relation(E, {(a, b) for a in E for b in E if a <= b}
         ).report("কম-বা-সমান (≤)")

Relation(E, {(a, b) for a in E for b in E if a \< b}
         ).report("কম (\<)")

Relation(E, {(a, b) for a in E for b in E if a % 2 == b % 2}
         ).report("একই জোড়/বিজোড় (mod 2)")

Relation(E, {(a, b) for a in E for b in E if b % a == 0}
         ).report("ভাগ করে (a | b)")

# একটা নির্ভরতা graph
tasks = ["parse", "typecheck", "optimize", "codegen", "lint", "link"]
deps  = {("parse","typecheck"), ("typecheck","optimize"),
         ("optimize","codegen"), ("codegen","link"), ("lint","link")}
Relation(tasks, deps).report("build নির্ভরতা")

# চক্র সহ
Relation(tasks, deps | {("link","parse")}).report("চক্র সহ")

নিজে বাড়ান:

  1. is_total() কে আরো দক্ষ করুন — বর্তমানে O(n²) জোড়া দেখে
  2. Hasse diagram ছাপুন — reflexive আর transitive edge বাদ দিয়ে
  3. closure() কে DFS দিয়ে লিখুন এবং sparse graph-এ Warshall-এর সাথে সময় তুলনা করুন
  4. একটা relation দিলে সেটা equivalence relation বানাতে সবচেয়ে কম কতগুলো জোড়া যোগ করতে হবে বের করুন (reflexive-symmetric-transitive closure)
  5. Union-Find দিয়ে classes() লিখুন এবং বড় input-এ তুলনা করুন

বাস্তব সিস্টেমে

Relation কোথায় কোথায়

Build system। Make, Bazel, Gradle, Ninja — প্রতিটার কেন্দ্রে একটা DAG আর topological sort। make -j8 কাজ করে কারণ partial order-এ অতুলনীয় target সমান্তরালে চালানো যায়।

Package manager। apt, cargo, npm, pip — dependency resolution মানে একটা DAG বানিয়ে topological sort করা। চক্র থাকলে error, না থাকলে install ক্রম।

Spreadsheet। Excel-এর প্রতিটা cell একটা node, প্রতিটা formula একটা edge। Recalculation হলো topological sort। আর “circular reference” error হলো cycle detection।

Compiler। Instruction scheduling — কোন instruction কোনটার উপর নির্ভর করে তার DAG বানিয়ে পুনর্বিন্যাস। Register allocation-এ interference graph। Dataflow analysis-এ partial order-এর উপর fixed point।

CPU-র out-of-order execution। Hardware নিজেই একটা dependency graph রাখে (reorder buffer + reservation station) আর অতুলনীয় instruction সমান্তরালে চালায়। Level 3-এ দেখব।

Type system। Subtyping একটা partial order। Dog ≼ Animal, কিন্তু Dog আর Cat অতুলনীয়। Type checker এই order-এ চলাচল করে।

Git। Commit DAG। merge-base হলো সর্বনিম্ন সাধারণ পূর্বপুরুষ। rebase হলো DAG-এর একটা অংশ পুনর্লিখন।

Kubernetes। Init container-এর ক্রম, resource-এর owner reference — সবই DAG। Garbage collection owner reference-এর transitive closure ধরে চলে।

Distributed system-এ causality। Lamport-এর happens-before (→) একটা strict partial order। দুইটা event অতুলনীয় মানে তারা concurrent। Level 9-এ এটাই vector clock-এর ভিত্তি।

Memory model। C++ আর Java-র memory model বলে কোন write কোন read-এর কাছে দৃশ্যমান — সেটা একটা partial order (happens-before)। Level 11-এ দেখব।

যে ভুলগুলো সবাই করে

“'বন্ধুর বন্ধু আমার বন্ধু' — তাই বন্ধুত্ব transitive।”

সামাজিক বন্ধুত্ব transitive নয়, আর এই ভুল ধারণাটা সফটওয়্যারে বাস্তব bug তৈরি করে।

Access control-এ ভাবুন: A বিশ্বাস করে B-কে, B বিশ্বাস করে C-কে। তাহলে A কি C-কে বিশ্বাস করে?

  • যদি হ্যাঁ ধরেন — তাহলে transitive trust, আর একটা compromised account থেকে পুরো নেটওয়ার্কে ছড়াতে পারে
  • যদি না ধরেন — তাহলে প্রতিটা সম্পর্ক আলাদা করে যাচাই করতে হয়

PGP-র web of trust ইচ্ছাকৃতভাবে সীমিত transitivity ব্যবহার করে — trust depth-এর একটা সীমা থাকে। কারণ পূর্ণ transitive closure নিলে একটা খারাপ key পুরো নেটওয়ার্ক দূষিত করত।

নকশাগত প্রশ্ন: আপনার সিস্টেমের relation-গুলো transitive হওয়া উচিত কি না — এটা একটা সচেতন সিদ্ধান্ত হতে হবে, ঘটনাচক্রে নয়।

“Partial order মানে 'অসম্পূর্ণ' বা 'ত্রুটিপূর্ণ' order।”

“Partial” মানে অসম্পূর্ণ নয় — মানে কিছু জোড়া তুলনীয় নয়। আর সেটা প্রায়ই একটা সুবিধা, ত্রুটি নয়।

A আর B-এর মধ্যে নির্ভরতা না থাকা মানে তারা সমান্তরালে চলতে পারে। Total order আরোপ করলে সেই সুযোগটা নষ্ট হতো।

Partial order:  A ∥ B → C        দুইটা core ব্যবহার করা যায়
Total order:    A → B → C        সবসময় একটা core

Distributed system-এ এটা আরো গুরুত্বপূর্ণ: দুইটা event concurrent হওয়া মানে তাদের মধ্যে কোনো causal সম্পর্ক নেই, তাই আলাদা node-এ স্বাধীনভাবে ঘটতে পারে। জোর করে total order আরোপ করা (যেমন একটা global sequencer দিয়ে) কাজ করে, কিন্তু সেটাই bottleneck হয়ে যায়।

Partial order = concurrency-র গাণিতিক রূপ।

“Transitive closure হিসাব করা সবসময় ভালো — সব তথ্য পাওয়া যায়।”

প্রায়ই না, দুইটা কারণে।

১. আকার বিস্ফোরিত হয়। n node-এর একটা chain-এ R-এ n−1 টা edge, কিন্তু R⁺-এ n(n−1)/2 টা। ১০০০ node মানে ৯৯৯ থেকে ৫ লক্ষ।

২. তথ্য হারায়। R⁺ বলে “পৌঁছানো যায়”, কিন্তু “সরাসরি” আর “পরোক্ষ”-এর পার্থক্য মুছে দেয়।

R  : app → express → body-parser
R⁺ : app → express, app → body-parser, express → body-parser

R⁺ দেখে আপনি বুঝবেন না body-parser একটা transitive dependency — মনে হবে সরাসরি। অথচ এই পার্থক্যটাই গুরুত্বপূর্ণ: সরাসরি dependency আপনি বেছে নিয়েছেন, transitive-টা আপনার উপর চাপিয়ে দেওয়া হয়েছে।

উল্টো operation-টাও দরকারি: transitive reduction — সবচেয়ে কম edge রেখে একই reachability। DAG-এ এটা অনন্য, আর Hasse diagram আসলে সেটাই।

npm ls (reduction) আর npm ls --all (closure) — দুটোই দরকার, ভিন্ন প্রশ্নের জন্য।

“`==` যেকোনোভাবে define করা যায়, এটা শুধু একটা convention।”

না — == কে equivalence relation হতেই হবে, নাহলে ভাষার data structure ভেঙে পড়ে।

তিনটা ধর্ম না মানলে কী হয়:

Reflexive ভাঙলে (a != a):

float('nan') == float('nan')    # False

এটাই কেন NaN কে list.index() দিয়ে খুঁজে পাওয়া যায় না, আর কেন NaN-যুক্ত sort অদ্ভুত আচরণ করে।

Symmetric ভাঙলে (a == b কিন্তু b != a):

class Weird:
    def __eq__(self, o): return isinstance(o, int)

Weird() == 5    # True
5 == Weird()    # Python fallback করে, কিন্তু সবসময় নয়

in, dict lookup — সব অপ্রত্যাশিত আচরণ করবে।

Transitive ভাঙলে (a == b, b == c, কিন্তু a != c): set -এ কোনটা রাখা হবে তা insertion order-এর উপর নির্ভর করবে। একই ডেটা, ভিন্ন ফল।

Java-র Comparable documentation স্পষ্টভাবে বলে দেয় contract-টা, আর সেটা ভাঙলে TreeMap-এর আচরণ undefined। Rust-এ Eq trait আক্ষরিকভাবে বলে “এটা একটা equivalence relation” (আর PartialEq সেই গ্যারান্টি দেয় না — এজন্যই float শুধু PartialEq)।

বুঝেছেন কি না দেখুন

1

A = {1,2,3,4,5,6} -এর উপর relation R = {(a,b) : a আর b -এর একই ভাজক সংখ্যা}। এটা কি equivalence relation? হলে equivalence class বের করুন।

প্রয়োগ

প্রথমে ভাজক সংখ্যা গুনি:

nভাজকসংখ্যা
111
21,22
31,32
41,2,43
51,52
61,2,3,64

তিনটা ধর্ম যাচাই:

  • Reflexive — a-এর ভাজক সংখ্যা a-এর ভাজক সংখ্যার সমান ✓
  • Symmetric — সমতা symmetric ✓
  • Transitive — সমতা transitive ✓

তিনটাই ✓ — হ্যাঁ, equivalence relation।

Equivalence class:

[1] = {1}           — ১টা ভাজক
[2] = {2, 3, 5}     — ২টা ভাজক (মৌলিক সংখ্যা)
[4] = {4}           — ৩টা ভাজক
[6] = {6}           — ৪টা ভাজক

Partition যাচাই: চারটা class পরস্পর-বিচ্ছিন্ন, আর union = {1,2,3,4,5,6} ✓

একটা সাধারণ pattern: যেকোনো function f : A → B স্বয়ংক্রিয়ভাবে একটা equivalence relation বানায়:

a∼b  ⟺  f(a)=f(b)a \sim b \iff f(a) = f(b)

একে বলে kernel of f। এখানে f(n) = ভাজক সংখ্যা।

এটা প্রোগ্রামিং-এ সর্বত্র:

from itertools import groupby
data = sorted(items, key=f)
for key, group in groupby(data, key=f):
    ...        # প্রতিটা group একটা equivalence class

GROUP BY clause আক্ষরিকভাবে একটা equivalence relation দিয়ে partition করছে। SQL-এর নকশাটা এই গণিতের সরাসরি প্রতিফলন।

আর লক্ষ্য করুন [2] = {2,3,5} ঠিক মৌলিক সংখ্যাগুলো — কারণ “ঠিক দুইটা ভাজক” হলো মৌলিকতার সংজ্ঞা।

2

কেন \< (কঠোরভাবে কম) partial order নয়, যদিও সেটা antisymmetric আর transitive?

যুক্তি

কারণ \< reflexive নয় — a \< a কখনো সত্য নয়।

Partial order-এর সংজ্ঞায় reflexive লাগে, তাই \< সেই সংজ্ঞা মানে না।

\< কে বলে strict partial order — irreflexive, transitive, আর (স্বয়ংক্রিয়ভাবে) asymmetric।

দুইটার সম্পর্ক একের সাথে এক:

থেকেতেকীভাবে
≤ (partial order)\< (strict)a \< b ⟺ a ≤ b ∧ a ≠ b
\< (strict)≤a ≤ b ⟺ a \< b ∨ a = b

তাই কোনটা ব্যবহার করবেন সেটা সুবিধার প্রশ্ন, গভীর পার্থক্য নয়।

কিন্তু প্রোগ্রামিং-এ পার্থক্যটা বাস্তব।

C++-এর std::sort একটা strict weak ordering দাবি করে, অর্থাৎ comparator-টা irreflexive হতে হবে — cmp(a, a) অবশ্যই false।

এই নিয়ম ভাঙলে কী হয়:

// ভুল — reflexive comparator
std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });

a <= a → true। libstdc++-এর introsort তখন array-র সীমার বাইরে পড়তে পারে — segfault বা memory corruption, কোনো warning ছাড়াই।

কারণ sort-এর ভেতরের partition loop while (cmp(*i, pivot)) ++i; এমন লেখা যেখানে pivot নিজেই sentinel হিসেবে কাজ করে। Comparator reflexive হলে pivot-এ এসে loop থামে না।

একটা গাণিতিক ধর্ম লঙ্ঘন → memory safety bug। এটাই কারণ Level 0-এ এই ধর্মগুলো শেখা।

3

আপনার একটা microservice আর্কিটেকচার আছে যেখানে service-রা পরস্পরকে call করে। কোন relation ধর্মটা আপনি জোর করে আরোপ করতে চাইবেন, আর কেন?

ডিজাইন

Acyclicity — অর্থাৎ call graph-টা একটা DAG হতে হবে।

সমতুল্যভাবে: “A, B-কে call করে” relation-এর transitive closure antisymmetric হতে হবে।

চক্র থাকলে যেসব সমস্যা:

সমস্যাব্যাখ্যা
Cascading failureA → B → A — একটা ধীর হলে দুটোই আটকে যায়
Deploy ক্রম নেইকোনটা আগে deploy করবেন?
DeadlockSynchronous call-এ resource waiting cycle
Retry stormচক্রে retry ঘুরতে থাকে, load বহুগুণ
বোঝা কঠিনকোনো “স্তর” নেই, সব সবার সাথে যুক্ত

২০২১-এর Facebook outage (৬ ঘণ্টা, বিশ্বব্যাপী) ছিল আংশিকভাবে এই শ্রেণির সমস্যা: BGP configuration ভুলে DNS server অগম্য হলো, কিন্তু ভেতরের tool-গুলো ঠিক করার জন্য সেই DNS-এর উপরই নির্ভরশীল ছিল। পুনরুদ্ধারের পথে একটা চক্র।

কীভাবে আরোপ করবেন:

১. Layered architecture — service-দের স্তরে ভাগ করুন, আর নিয়ম করুন call শুধু নিচের দিকে যাবে:

Layer 3: API gateway, BFF
Layer 2: domain service
Layer 1: platform service (auth, config)
Layer 0: datastore

Layer সংখ্যা একটা total order, আর “শুধু নিচে call” নিয়মটা গঠনগতভাবে চক্র অসম্ভব করে দেয় — ঠিক যেমন lock ordering deadlock প্রতিরোধ করে।

২. CI-তে যাচাই — service manifest থেকে call graph বানিয়ে প্রতিটা PR-এ cycle detection চালান। চক্র ঢুকলে build fail।

৩. চক্র সত্যিই লাগলে asynchronous করুন — direct call-এর বদলে event/queue ব্যবহার করুন। তখন call graph-এ edge থাকে না; নির্ভরতাটা সময়ে বিচ্ছিন্ন হয়ে যায়।

সমস্যা:   A --sync--> B --sync--> A     চক্র
সমাধান:   A --sync--> B
          B --event--> queue --> A       চক্র নেই

৪. যেখানে চক্র অনিবার্য, সেখানে circuit breaker — চক্র ভাঙা না গেলে অন্তত cascading failure আটকান।

একটা সূক্ষ্মতা: পুরোপুরি acyclic architecture সবসময় ব্যবহারিক নয়। লক্ষ্য হওয়া উচিত — চক্র থাকলে সেটা জেনেশুনে, নথিভুক্ত, আর async দিয়ে ভাঙা। দুর্ঘটনাক্রমে চক্র তৈরি হওয়াটাই আসল বিপদ।

Level 9 (distributed systems) আর Level 12 (cloud)-এ আমরা এগুলো বিস্তারিত দেখব।

4

n node-এর একটা DAG-এ transitive closure-এ সর্বোচ্চ কতগুলো edge থাকতে পারে? কোন গঠনে সেটা হয়?

প্রয়োগ

সর্বোচ্চ:

(n2)=n(n−1)2\binom{n}{2} = \frac{n(n-1)}{2}

কেন এটাই সীমা: DAG-এ কোনো চক্র নেই, তাই যেকোনো জোড়া (a, b)-র জন্য সর্বোচ্চ একটা দিকে পথ থাকতে পারে (দুইদিকেই থাকলে চক্র হতো)। আর n node-এর জোড়া সংখ্যা C(n,2)।

কোন গঠনে অর্জিত হয়: একটা total order — সরলরেখা।

1 → 2 → 3 → 4 → 5

মূল edge: ৪টা। Transitive closure: (1,2),(1,3),(1,4),(1,5),(2,3), (2,4),(2,5),(3,4),(3,5),(4,5) = ১০টা = C(5,2) ✓

অনুপাতটা লক্ষ্য করুন:

nR (chain)R⁺বৃদ্ধি
54102.5×
100994,95050×
1,000999499,500500×
10,0009,999~50M5,000×

O(n) থেকে O(n²) — এই কারণেই transitive closure precompute করা প্রায়ই খারাপ ধারণা।

বাস্তব প্রভাব — SQL-এ ancestor query:

-- বিকল্প ১: closure table (precomputed R⁺)
CREATE TABLE ancestor (descendant int, ancestor int, depth int);
-- দ্রুত query, কিন্তু O(n²) storage আর প্রতিটা insert-এ O(depth) row

-- বিকল্প ২: recursive CTE (চাহিদামতো হিসাব)
WITH RECURSIVE anc AS (
    SELECT parent_id FROM node WHERE id = 42
    UNION ALL
    SELECT n.parent_id FROM node n JOIN anc a ON n.id = a.parent_id
)
SELECT * FROM anc;
-- O(1) storage overhead, কিন্তু প্রতিটা query-তে traversal

Trade-off: closure table read-heavy workload-এ ভালো (read দ্রুত, write ধীর), recursive CTE write-heavy-তে ভালো।

আর তৃতীয় একটা বিকল্প আছে — nested set model বা materialized path — যা O(n) storage-এ O(1) ancestor check দেয়, কিন্তু tree পুনর্বিন্যাস ব্যয়বহুল করে।

Level 8-এ আমরা hierarchical data-র এই তিনটা মডেল তুলনা করব।

5

Distributed system-এ “happens-before” (→) একটা strict partial order। দুইটা event a আর b অতুলনীয় হওয়ার মানে কী, আর এর ব্যবহারিক তাৎপর্য কী?

যুক্তি

a আর b অতুলনীয় মানে না a → b, না b → a — অর্থাৎ তারা concurrent।

Lamport-এর সংজ্ঞায় a → b হয় তিনভাবে:

  1. একই process-এ a, b-এর আগে ঘটেছে
  2. a একটা message পাঠানো, b সেটা গ্রহণ
  3. Transitivity

কোনোটাই না হলে দুইটা event concurrent।

ব্যবহারিক তাৎপর্য — চারটা:

১. কোনো “সঠিক” ক্রম নেই। দুইজন পর্যবেক্ষক দুই ক্রমে দেখতে পারে, আর দুজনেই ঠিক। “কোনটা আগে হয়েছিল” প্রশ্নটার উত্তর নেই।

২. Wall clock দিয়ে সমাধান হয় না। দুইটা machine-এর ঘড়ি NTP দিয়ে sync করলেও কয়েক মিলিসেকেন্ড পার্থক্য থাকে। তাই timestamp দেখে “এটা আগে” বলা অনির্ভরযোগ্য।

Google Spanner এই সমস্যা সমাধান করে TrueTime দিয়ে — atomic clock আর GPS ব্যবহার করে uncertainty interval (ε) হিসাব করে, তারপর commit-এর সময় ε অপেক্ষা করে যাতে ক্রম নিশ্চিত হয়। হার্ডওয়্যার দিয়ে গণিতের সমস্যা সমাধান — ব্যয়বহুল কিন্তু কার্যকর।

৩. Conflict সম্ভব। দুইটা concurrent write একই key-তে হলে কোনটা রাখবেন? সিদ্ধান্তগুলো:

কৌশলআচরণ
Last-write-winstimestamp দেখে — ডেটা হারায়
Multi-valueদুটোই রাখুন, application সিদ্ধান্ত নিক (Dynamo)
CRDTmerge function এমন যে conflict-ই হয় না

৪. Vector clock এই order-টা ধরে রাখে। Lamport timestamp (একটা সংখ্যা) শুধু total order দেয় — concurrent আর causal আলাদা করতে পারে না। Vector clock (প্রতি node-এ একটা counter) partial order-টাই encode করে:

V(a) \< V(b)   →  a happens-before b
V(b) \< V(a)   →  b happens-before a
কোনোটাই না    →  concurrent

গভীর পয়েন্ট: distributed system-এ event-দের প্রকৃত কাঠামো একটা partial order। যেকোনো total order (একটা global log, একটা sequence number) সেই কাঠামোর উপর একটা কৃত্রিম আরোপ — যা সুবিধাজনক কিন্তু coordination-এর দাম দিয়ে কেনা।

আর সেই coordination-ই latency আর availability-র উপর সীমা টানে — CAP theorem-এর গোড়ায় এই গাণিতিক সত্যটাই আছে।

Level 9-এ আমরা vector clock নিজে implement করব আর Raft-এর safety proof-এ এই partial order ব্যবহার করব।

এরপর কী

Relation আমাদের শিখিয়েছে জিনিসগুলোর মধ্যকার সম্পর্ক কীভাবে গঠন করে।

পরের লেসনে আসছে functions — যা relation-এরই একটা বিশেষ শ্রেণি (প্রতিটা input-এর ঠিক একটা output)। সেখান থেকে আসবে injective, surjective, bijective — আর সেই ধারণাগুলো সরাসরি ব্যাখ্যা করবে কেন hash collision অনিবার্য, কেন lossless compression সব ফাইল ছোট করতে পারে না, আর কেন একটা encoding “invertible” হওয়া মানে কী।

আরও পড়ুন