T61. Algorísmia. Complexitat computacional

Desarrollo del tema

# ALGORÍSMIA. COMPLEXITAT COMPUTACIONAL

## 1. Introducció

L'**algorísmia** és la branca de les matemàtiques i la informàtica que estudia els **algorismes**: seqüències finites d'instruccions ben definides que resolen un problema o realitzen un càlcul. El terme prové del matemàtic persa **Al-Khwarizmi** (s. IX), considerat el pare de l'àlgebra.

La **complexitat computacional** mesura els recursos (temps i espai) necessaris per executar un algorisme en funció de la mida de l'entrada. Aquesta disciplina ens permet comparar l'eficiència de diferents solucions i determinar si un problema és tractable computacionalment.

## 2. Concepte d'Algorisme

### 2.1 Definició Formal

Un **algorisme** és un procediment computacional que: - Rep una **entrada** (input) - Produeix una **sortida** (output) - Té un nombre **finit** de passos - Cada pas està **ben definit** (no ambigüitat) - És **efectiu** (cada operació és realitzable)

### 2.2 Propietats Fonamentals

**Finitud:** L'algorisme ha d'acabar després d'un nombre finit de passos.

**Definició precisa:** Cada instrucció ha de ser clara i sense ambigüitat.

**Entrada:** Pot tenir zero o més dades d'entrada.

**Sortida:** Ha de produir almenys un resultat.

**Efectivitat:** Totes les operacions han de ser prou bàsiques per ser executables.

### 2.3 Representació d'Algorismes

**Pseudocodi:** Descripció en llenguatge natural estructurat.

**Diagrames de flux:** Representació gràfica amb símbols estàndard (rectangles per processos, rombes per decisions, etc.).

**Llenguatges formals:** Màquines de Turing, càlcul lambda.

## 3. Exemples Clàssics d'Algorismes

### 3.1 Algorisme d'Euclides (MCD)

Calcula el màxim comú divisor de dos enters positius $a$ i $b$:

``` Algorisme Euclides(a, b): Mentre b ≠ 0: r ← a mod b a ← b b ← r Retornar a ```

**Exemple:** MCD(48, 18) - 48 mod 18 = 12 → (18, 12) - 18 mod 12 = 6 → (12, 6) - 12 mod 6 = 0 → (6, 0) - Resultat: MCD = 6

### 3.2 Cerca Binària

Cerca un element $x$ en un array ordenat $A[1..n]$:

``` Algorisme CercaBinaria(A, x): esquerra ← 1 dreta ← n Mentre esquerra ≤ dreta: mig ← ⌊(esquerra + dreta) / 2⌋ Si A[mig] = x: Retornar mig Si A[mig] < x: esquerra ← mig + 1 Sinó: dreta ← mig - 1 Retornar "No trobat" ```

### 3.3 Algorismes d'Ordenació

**Ordenació per bombolla (Bubble Sort):** Compara elements adjacents i els intercanvia si estan desordenats. Complexitat $O(n^2)$.

**Ordenació per fusió (Merge Sort):** Divideix l'array en dues meitats, ordena recursivament i fusiona. Complexitat $O(n \log n)$.

**Ordenació ràpida (Quick Sort):** Tria un pivot, parteix l'array en elements menors i majors, i ordena recursivament. Complexitat mitjana $O(n \log n)$, pitjor cas $O(n^2)$.

## 4. Anàlisi de Complexitat

### 4.1 Complexitat Temporal

Mesura el nombre d'operacions bàsiques en funció de la mida de l'entrada $n$.

**Casos d'anàlisi:** - **Millor cas:** Entrada més favorable - **Pitjor cas:** Entrada més desfavorable - **Cas mitjà:** Mitjana sobre totes les entrades possibles

### 4.2 Notació Asimptòtica

Descriu el comportament de funcions quan $n \to \infty$.

**Notació O-gran (cota superior):** $$f(n) = O(g(n)) \iff \exists c > 0, n_0 : \forall n \geq n_0, f(n) \leq c \cdot g(n)$$

**Notació Ω-gran (cota inferior):** $$f(n) = \Omega(g(n)) \iff \exists c > 0, n_0 : \forall n \geq n_0, f(n) \geq c \cdot g(n)$$

**Notació Θ-gran (cota ajustada):** $$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ i } f(n) = \Omega(g(n))$$

### 4.3 Classes de Complexitat Comunes

| Notació | Nom | Exemple | |---------|-----|---------| | $O(1)$ | Constant | Accés a array per índex | | $O(\log n)$ | Logarítmica | Cerca binària | | $O(n)$ | Lineal | Cerca seqüencial | | $O(n \log n)$ | Quasi-lineal | Merge Sort | | $O(n^2)$ | Quadràtica | Bubble Sort | | $O(n^3)$ | Cúbica | Multiplicació de matrius | | $O(2^n)$ | Exponencial | Subconjunts | | $O(n!)$ | Factorial | Permutacions |

### 4.4 Complexitat Espacial

Mesura la memòria addicional necessària. Per exemple: - Merge Sort: $O(n)$ espai extra - Quick Sort (in-place): $O(\log n)$ per la pila de recursió

## 5. Recurrències

Molts algorismes recursius tenen complexitat descrita per **equacions de recurrència**.

### 5.1 Exemples

**Cerca binària:** $$T(n) = T(n/2) + O(1)$$ Solució: $T(n) = O(\log n)$

**Merge Sort:** $$T(n) = 2T(n/2) + O(n)$$ Solució: $T(n) = O(n \log n)$

### 5.2 Teorema Mestre

Per recurrències de la forma $T(n) = aT(n/b) + f(n)$ amb $a \geq 1$, $b > 1$:

Sigui $c = \log_b a$. Llavors:

1. Si $f(n) = O(n^{c-\epsilon})$ per algun $\epsilon > 0$: $T(n) = \Theta(n^c)$ 2. Si $f(n) = \Theta(n^c)$: $T(n) = \Theta(n^c \log n)$ 3. Si $f(n) = \Omega(n^{c+\epsilon})$ i $af(n/b) \leq kf(n)$ per $k < 1$: $T(n) = \Theta(f(n))$

**Exemple (Merge Sort):** $a=2, b=2, f(n)=n$ - $c = \log_2 2 = 1$ - $f(n) = n = \Theta(n^1)$ → Cas 2 - $T(n) = \Theta(n \log n)$

## 6. Classes de Complexitat Computacional

### 6.1 Problemes de Decisió

Un **problema de decisió** té resposta SÍ o NO. Exemple: "Existeix un camí de A a B amb cost ≤ k?"

### 6.2 Classe P

Conté els problemes de decisió resolubles en temps **polinòmic** per una màquina de Turing determinista.

$$P = \bigcup_{k \geq 0} \text{TIME}(n^k)$$

**Exemples en P:** - Ordenació - Cerca - Camí mínim en grafs - Primalitat (AKS, 2002)

### 6.3 Classe NP

Conté els problemes de decisió on una solució pot ser **verificada** en temps polinòmic.

Equivalentment: problemes resolubles en temps polinòmic per una màquina de Turing **no determinista**.

**Exemples en NP:** - SAT (Satisfactibilitat booleana) - Problema del viatjant de comerç (versió decisió) - Suma de subconjunts - Clique en grafs

### 6.4 Relació P vs NP

Clarament $P \subseteq NP$ (si pots resoldre, pots verificar).

**El problema del mil·lenni:** És $P = NP$?

Si fos cert, tots els problemes verificables en temps polinòmic serien també resolubles en temps polinòmic. La majoria d'experts creuen que $P \neq NP$.

### 6.5 NP-Completesa

Un problema és **NP-complet** si: 1. Està en NP 2. Tot problema en NP es pot reduir a ell en temps polinòmic

**Teorema de Cook-Levin (1971):** SAT és NP-complet.

Si es trobés un algorisme polinòmic per a qualsevol problema NP-complet, llavors $P = NP$.

**Exemples NP-complets:** - SAT, 3-SAT - Clique - Conjunt independent - Cobertura de vèrtexs - Problema de la motxilla (versió decisió) - Viatjant de comerç

### 6.6 Classe NP-Hard

Problemes almenys tan difícils com els NP-complets, però no necessàriament en NP (poden ser problemes d'optimització).

## 7. Estratègies Algorísmiques

### 7.1 Força Bruta

Explorar totes les possibilitats. Sempre funciona però sol ser ineficient.

### 7.2 Divideix i Venceràs

1. **Dividir** el problema en subproblemes més petits 2. **Resoldre** recursivament 3. **Combinar** les solucions

Exemples: Merge Sort, Quick Sort, cerca binària.

### 7.3 Programació Dinàmica

Descompondre en subproblemes **superposats**, emmagatzemant resultats per evitar recàlculs.

**Exemple (Fibonacci):** ``` fib(n): Si n ≤ 1: Retornar n Si memo[n] definit: Retornar memo[n] memo[n] ← fib(n-1) + fib(n-2) Retornar memo[n] ```

### 7.4 Algorismes Cobdiciosos (Greedy)

Prendre la decisió localment òptima a cada pas, esperant arribar a l'òptim global.

**Exemple:** Algorisme de Dijkstra per camins mínims.

### 7.5 Backtracking

Exploració sistemàtica amb retrocés quan es detecta que una branca no porta a solució.

**Exemple:** N-reines, Sudoku.

## 8. Màquines de Turing

Model matemàtic de computació proposat per **Alan Turing** (1936).

**Components:** - Cinta infinita dividida en cel·les - Capçal de lectura/escriptura - Conjunt finit d'estats - Funció de transició

**Tesi de Church-Turing:** Tot el que és computable pot ser calculat per una màquina de Turing.

### 8.1 Problemes Indecidibles

Existeixen problemes que cap algorisme pot resoldre.

**Problema de l'aturada (Halting Problem):** No existeix cap algorisme que, donat un programa P i una entrada x, determini si P s'atura amb entrada x.

**Demostració (per contradicció):** Suposem que existeix HALT(P, x). Construïm D(P) que s'atura si HALT(P, P) = "no s'atura" i fa un bucle infinit si HALT(P, P) = "s'atura". Llavors D(D) porta a contradicció.

## 9. Aplicacions Didàctiques

### 9.1 ESO

- **Algorismes quotidians:** Receptes de cuina, instruccions de muntatge - **Diagrames de flux:** Processos simples (decidir roba segons meteorologia) - **Jocs:** Endevinar un nombre amb cerca binària - **Scratch:** Programació visual per entendre seqüències i bucles

### 9.2 Batxillerat

- **Anàlisi de complexitat:** Comparar algorismes d'ordenació - **Recurrències:** Resoldre amb el teorema mestre - **Programació:** Implementar algorismes clàssics - **Discussió P vs NP:** Implicacions pràctiques i filosòfiques

## 10. Conclusions

L'algorísmia proporciona les eines per dissenyar solucions eficients a problemes computacionals. La teoria de la complexitat ens permet classificar problemes segons la seva dificultat intrínseca i entendre els límits de la computació. La distinció entre P i NP, i l'existència de problemes NP-complets, té profundes implicacions teòriques i pràctiques en criptografia, optimització i intel·ligència artificial.