Introducció
En aquest primer tema del curs d'Algorismes Avançats, ens centrarem en establir una base sòlida de conceptes bàsics i notació que seran essencials per comprendre els temes més avançats que vindran. Aquests conceptes inclouen la definició d'algorismes, la notació asimptòtica, i altres termes fonamentals en l'estudi dels algorismes.
Què és un Algorisme?
Un algorisme és una seqüència finita de passos ben definits que es duen a terme per resoldre un problema o per realitzar una tasca específica. Els algorismes són essencials en la informàtica perquè proporcionen una manera sistemàtica de resoldre problemes.
Característiques d'un Algorisme
- Finitud: Un algorisme ha de tenir un nombre finit de passos.
- Definició: Cada pas de l'algorisme ha d'estar clarament definit.
- Entrada: Un algorisme ha de tenir zero o més entrades.
- Sortida: Un algorisme ha de produir almenys una sortida.
- Eficàcia: Cada pas de l'algorisme ha de ser executable en un temps finit.
Notació Asimptòtica
La notació asimptòtica és una manera de descriure el comportament de la complexitat d'un algorisme quan la mida de l'entrada creix. Les notacions més comunes són:
- O(gran O): Representa un límit superior asimptòtic. Es llegeix com "O de".
- Ω(gran Omega): Representa un límit inferior asimptòtic. Es llegeix com "Omega de".
- Θ(gran Theta): Representa un límit ajustat asimptòtic. Es llegeix com "Theta de".
Notació O(gran O)
La notació O(gran O) proporciona un límit superior per a la funció de temps d'execució d'un algorisme. Formalment, una funció \( f(n) \) és \( O(g(n)) \) si existeixen constants positives \( c \) i \( n_0 \) tals que per a tot \( n \geq n_0 \), \( f(n) \leq c \cdot g(n) \).
Exemple
En aquest cas, el temps d'execució de l'algorisme és \( O(n) \) perquè el bucle s'executa \( n \) vegades.
Notació Ω(gran Omega)
La notació Ω(gran Omega) proporciona un límit inferior per a la funció de temps d'execució d'un algorisme. Formalment, una funció \( f(n) \) és \( Ω(g(n)) \) si existeixen constants positives \( c \) i \( n_0 \) tals que per a tot \( n \geq n_0 \), \( f(n) \geq c \cdot g(n) \).
Notació Θ(gran Theta)
La notació Θ(gran Theta) proporciona un límit ajustat per a la funció de temps d'execució d'un algorisme. Formalment, una funció \( f(n) \) és \( Θ(g(n)) \) si existeixen constants positives \( c_1 \), \( c_2 \) i \( n_0 \) tals que per a tot \( n \geq n_0 \), \( c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \).
Exemples de Notació Asimptòtica
| Funció | Notació O | Notació Ω | Notació Θ |
|---|---|---|---|
| Constant | \( O(1) \) | \( Ω(1) \) | \( Θ(1) \) |
| Logarítmica | \( O(\log n) \) | \( Ω(\log n) \) | \( Θ(\log n) \) |
| Lineal | \( O(n) \) | \( Ω(n) \) | \( Θ(n) \) |
| Quadràtica | \( O(n^2) \) | \( Ω(n^2) \) | \( Θ(n^2) \) |
| Exponencial | \( O(2^n) \) | \( Ω(2^n) \) | \( Θ(2^n) \) |
Exercicis Pràctics
Exercici 1
Pregunta: Determina la complexitat temporal del següent algorisme utilitzant la notació O(gran O).
Solució: El bucle s'executa \( n \) vegades, per tant, la complexitat temporal és \( O(n) \).
Exercici 2
Pregunta: Determina la complexitat temporal del següent algorisme utilitzant la notació O(gran O).
def suma_quadrats(n):
suma = 0
for i in range(1, n + 1):
for j in range(1, n + 1):
suma += i * j
return sumaSolució: El bucle extern s'executa \( n \) vegades i el bucle intern també s'executa \( n \) vegades per cada iteració del bucle extern. Per tant, la complexitat temporal és \( O(n^2) \).
Resum
En aquesta secció hem après els conceptes bàsics d'algorismes i la notació asimptòtica, incloent les notacions O(gran O), Ω(gran Omega) i Θ(gran Theta). Aquests conceptes són fonamentals per a l'anàlisi i la comprensió dels algorismes avançats que veurem en els següents mòduls del curs.
En el següent tema, ens endinsarem en l'anàlisi de complexitat, on explorarem com calcular la complexitat temporal i espacial dels algorismes de manera més detallada.
Algoritmes Avançats
Mòdul 1: Introducció als Algoritmes Avançats
Mòdul 2: Algoritmes d'Optimització
- Programació Lineal
- Algoritmes d'Optimització Combinatòria
- Algoritmes Genètics
- Optimització de Colònia de Formigues
Mòdul 3: Algoritmes en Grafs
- Representació de Grafs
- Cerca en Grafs: BFS i DFS
- Algoritmes de Camins Mínims
- Algoritmes de Flux Màxim
- Algoritmes d'Aparellament en Grafs
Mòdul 4: Algoritmes de Cerca i Ordenació
Mòdul 5: Algoritmes d'Aprenentatge Automàtic
- Introducció a l'Aprenentatge Automàtic
- Algoritmes de Classificació
- Algoritmes de Regressió
- Xarxes Neuronals i Deep Learning
- Algoritmes de Clustering
Mòdul 6: Casos d'Estudi i Aplicacions
- Optimització en la Indústria
- Aplicacions de Grafs en Xarxes Socials
- Cerca i Ordenació en Grans Volums de Dades
- Aplicacions d'Aprenentatge Automàtic en la Vida Real