De ce matematica pentru informatică?

Informatica e construită pe matematică, nu invers. Algoritmii sunt demonstrații. Bazele de date sunt logică predicativă. Criptografia e teoria numerelor. Machine learning-ul e algebră liniară și probabilități.

1. Algebra booleană și logică

Operatori logici

| Operator | Simbol | Explicație | |---|---|---| | ȘI (AND) | ∧ | Adevărat doar dacă ambele sunt adevărate | | SAU (OR) | ∨ | Adevărat dacă cel puțin una e adevărată | | NU (NOT) | ¬ | Inversează valoarea | | XOR | ⊕ | Adevărat dacă exact una e adevărată |

Legi fundamentale

• Comutativitate: A ∧ B = B ∧ A
• Asociativitate: (A ∧ B) ∧ C = A ∧ (B ∧ C)
• Distributivitate: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
• Legile lui De Morgan: ¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B

Implicație

A → B (dacă A atunci B) e echivalent cu ¬A ∨ B. Reciproca nu e adevărată: A → B nu implică B → A.

2. Mulțimi și relații

O mulțime e o colecție de elemente distincte.

Exemplu: A = {1, 2, 3}, B = {2, 3, 4}

| Operație | Notație | Rezultat | |---|---|---| | Reuniune | A ∪ B | {1, 2, 3, 4} | | Intersecție | A ∩ B | {2, 3} | | Diferență | A \ B | {1} |

O relație binară între mulțimile A și B e o submulțime a produsului cartezian A × B.

Proprietăți ale relațiilor pe aceeași mulțime:

• Reflexivă: x R x pentru orice x
• Simetrică: x R y ⇒ y R x
• Tranzitivă: x R y ∧ y R z ⇒ x R z

O relație reflexivă, simetrică și tranzitivă e o relație de echivalență. Partitionează mulțimea în clase de echivalență.

3. Teoria numerelor

Divizibilitate

a | b dacă există k întreg astfel încât b = a·k.

Algoritmul lui Euclid

cmmdc(a, b) = cmmdc(b, a mod b). Termină în O(log min(a,b)).

Congruența

a ≡ b (mod n) dacă n | (a - b). Adică a și b au același rest la împărțirea cu n.

Mica teoremă a lui Fermat

Dacă p e prim și a nu e divizibil cu p, atunci a^(p-1) ≡ 1 (mod p).

Aplicație: Testul de primalitate Miller-Rabin.

Modul Expert

4. Analiza combinatorică

Permutări

Numărul de moduri de a aranja n elemente: P(n) = n!

Aranjamente

Numărul de moduri de a alege k elemente din n în ordine: A(n,k) = n! / (n-k)!

Combinări

Numărul de moduri de a alege k elemente din n fără ordine: C(n,k) = n! / (k! · (n-k)!)

Proprietăți:

• C(n,k) = C(n, n-k)
• C(n,k) + C(n,k+1) = C(n+1, k+1) (triunghiul lui Pascal)
• Σ C(n,k) = 2^n (toate submulțimile)

Principiul includerii și excluderii

|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

Generalizare: alternăm sumele unităților, perechilor, tripletelor...

5. Algebră liniară avansată

Spații vectoriale

Un spațiu vectorial peste un corp K e o mulțime V cu două operații: adunare și înmulțire cu scalari, care satisfac 8 axiome.

Exemplu: R^n e un spațiu vectorial peste R.

Baze și dimensiune

O bază e o mulțime de vectori liniar independenți care generează tot spațiul. Dimensiunea e numărul de vectori din bază.

Valori și vectori proprii

A·v = λ·v, unde A e o matrice, v e vector propriu, λ e valoare proprie.

Aplicații: PCA (reducere dimensionalitate), PageRank, mecanica cuantică, compresie de imagini.

Descompunerea în valori singulare (SVD)

Orice matrice A (m×n) poate fi descompusă: A = U·Σ·V^T

U = vectori singulari stânga (ortonormați) Σ = valori singulare (diagonală) V = vectori singulari dreapta (ortonormați)

Aplicații: Compresia imaginilor, sisteme de recomandare (Netflix Prize), LSI (procesare text).

6. Probabilități și statistică

Probabilitatea condiționată

P(A|B) = P(A∩B) / P(B).

Teorema lui Bayes

P(A|B) = P(B|A)·P(A) / P(B). Fundamentală pentru machine learning.

Variabila aleatoare

X: Ω → R, unde Ω e spațiul de evenimente.

Valoarea așteptată

E[X] = Σ x·P(X=x). Linearitate: E[aX + bY] = a·E[X] + b·E[Y].

Atenție: E[X·Y] ≠ E[X]·E[Y] în general. Egalitatea doar pentru variabile independente.

Legea numerelor mari

Media observațiilor converge la valoarea așteptată pe măsură ce n → ∞.

Teorema limită centrală

Suma a n variabile aleatoare independente identic distribuite tinde la o distribuție normală. Explică de ce multe fenomene naturale au distribuție normală.

7. Teoria grafurilor

Definiții

Un graf G = (V, E) unde V = noduri, E = muchii.

| Tip | Descriere | |---|---| | Neorientat | Muchii fără direcție | | Orientat | Muchii cu direcție (arce) | | Ponderat | Muchii cu costuri | | DAG | Graf orientat aciclic |

Proprietăți

• Un arbore cu n noduri are n-1 muchii
• Un graf complet K_n are n·(n-1)/2 muchii
• Un graf bipartit poate fi colorat cu 2 culori

Algoritmi fundamentali

BFS: Cel mai scurt drum în grafuri neponderate. O(V+E). DFS: Detectare cicluri, sortare topologică, componente tare conexe. O(V+E). Dijkstra: Cel mai scurt drum în grafuri cu ponderi nenegative. O((V+E)·log V). Bellman-Ford: Cel mai scurt drum cu ponderi negative. O(V·E). Floyd-Warshall: Drum minim între toate perechile. O(V^3). Kruskal: Arbore parțial minim. O(E·log E). Prim: Arbore parțial minim. O(E·log V).

8. Funcții generatoare

O funcție generatoare e o serie formală de puteri care codifică un șir.

G(x) = a_0 + a_1·x + a_2·x^2 + ...

Exemplu — șirul Fibonacci: G(x) = x / (1 - x - x^2). Coeficientul lui x^n e F_n.

Aplicație: Rezolvarea recurențelor, combinatorică, analiza algoritmilor.

9. Matematica în spatele algoritmilor

| Algoritm | Concept matematic | |---|---| | PageRank | Vectori proprii (matrice stocastică) | | QuickSort | Analiza probabilistică, variabile aleatoare | | RSA | Teoria numerelor, numere prime, exponențiere modulară | | KMP | Automate finite, funcție de prefix | | Minimax | Teoria jocurilor, cuantificatori (∀∃) | | Monte Carlo | Legea numerelor mari, estimare statistică | | Naive Bayes | Teorema lui Bayes, independență condiționată | | Gradient Descent | Derivate parțiale, gradient, optimizare convexă |

Vezi și

• Algebră liniară pentru ML
• Big O
• Numere prime
• Teorema lui Bayes
• Entropia informațională
• P vs NP