En aquest tema, explorarem els diferents tipus d'algorismes que existeixen i com es poden classificar segons diverses característiques. Aquesta comprensió és fonamental per seleccionar l'algorisme adequat per a un problema específic i per optimitzar el rendiment del codi.
Classificació segons la seva Funció
- Algorismes de Cerca
Els algorismes de cerca s'utilitzen per trobar un element específic dins d'una estructura de dades. Alguns exemples comuns inclouen:
- Cerca Lineal: Recorre la llista element per element fins a trobar l'element desitjat.
- Cerca Binària: Requereix una llista ordenada i divideix repetidament la llista en meitats per trobar l'element desitjat.
Exemple de Cerca Binària en Python:
def cerca_binaria(arr, x):
esquerra, dreta = 0, len(arr) - 1
while esquerra <= dreta:
mig = (esquerra + dreta) // 2
if arr[mig] == x:
return mig
elif arr[mig] < x:
esquerra = mig + 1
else:
dreta = mig - 1
return -1
# Exemple d'ús
arr = [2, 3, 4, 10, 40]
x = 10
resultat = cerca_binaria(arr, x)
print(f'Element trobat a l\'índex {resultat}' if resultat != -1 else 'Element no trobat')
- Algorismes d'Ordenació
Els algorismes d'ordenació s'utilitzen per organitzar els elements d'una llista en un ordre específic (ascendent o descendent). Alguns exemples inclouen:
- Ordenació per Inserció: Insereix cada element en la seva posició correcta dins d'una llista ordenada.
- Ordenació per Mescla (Merge Sort): Divideix la llista en subllistes més petites i les combina de manera ordenada.
Exemple d'Ordenació per Inserció en Python:
def ordenacio_per_insercio(arr):
for i in range(1, len(arr)):
clau = arr[i]
j = i - 1
while j >= 0 and clau < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = clau
# Exemple d'ús
arr = [12, 11, 13, 5, 6]
ordenacio_per_insercio(arr)
print(f'Llista ordenada: {arr}')
- Algorismes de Caminament
Aquests algorismes s'utilitzen per trobar camins o rutes en un graf. Alguns exemples inclouen:
- Algorisme de Dijkstra: Troba el camí més curt des d'un node d'origen a tots els altres nodes en un graf amb pesos no negatius.
- Algorisme de Floyd-Warshall: Troba els camins més curts entre tots els parells de nodes en un graf.
Classificació segons la seva Estratègia
- Divideix i Venceràs
Aquesta estratègia divideix el problema en subproblemes més petits, els resol de manera recursiva i després combina les solucions. Exemples inclouen:
- Ordenació per Mescla (Merge Sort)
- Ordenació Ràpida (Quick Sort)
- Algorismes Greedy
Aquests algorismes prenen decisions locals òptimes amb l'esperança que aquestes decisions conduiran a una solució global òptima. Exemples inclouen:
- Algorisme de Kruskal per trobar l'arbre de cobertura mínima.
- Algorisme de Prim per trobar l'arbre de cobertura mínima.
- Programació Dinàmica
Aquesta estratègia resol problemes complexos descomposant-los en subproblemes més simples i emmagatzemant els resultats de subproblemes ja resolts per evitar càlculs repetits. Exemples inclouen:
- Problema del Camí Més Curt (com l'algorisme de Floyd-Warshall).
- Problema de la Mochila.
- Backtracking
Aquesta estratègia prova totes les possibles solucions i retrocedeix quan arriba a una solució invàlida. Exemples inclouen:
- Resolució del Sudoku
- Problema de les N-Reines
Exercicis Pràctics
Exercici 1: Implementació de la Cerca Binària
Implementa una funció de cerca binària en el teu llenguatge de programació preferit i prova-la amb diferents llistes ordenades.
Exercici 2: Ordenació per Inserció
Implementa l'algorisme d'ordenació per inserció i prova'l amb una llista desordenada. Compara el rendiment amb altres algorismes d'ordenació.
Exercici 3: Algorisme Greedy
Implementa un algorisme greedy per resoldre el problema de la moneda (donar canvi amb el menor nombre de monedes possibles).
Resum
En aquesta secció, hem explorat diversos tipus d'algorismes i com es poden classificar segons la seva funció i estratègia. Hem vist exemples pràctics de cerca binària i ordenació per inserció, i hem introduït conceptes clau com "divideix i venceràs", algorismes greedy, programació dinàmica i backtracking. Aquesta comprensió és essencial per seleccionar i dissenyar algorismes eficients per a diferents problemes.
En el següent tema, aprofundirem en la Notació Asimptòtica, que ens permetrà analitzar i comparar l'eficiència dels algorismes de manera formal.
Curs d'Anàlisi i Disseny d'Algorismes
Mòdul 1: Introducció als Algorismes
Mòdul 2: Anàlisi d'Algorismes
- Anàlisi de Complexitat Temporal
- Anàlisi de Complexitat Espacial
- Cases de Complexitat: Millor, Pitjor i Promig
Mòdul 3: Estratègies de Disseny d'Algorismes
Mòdul 4: Algorismes Clàssics
- Cerca Binària
- Ordenació per Inserció
- Ordenació per Mescla (Merge Sort)
- Ordenació Ràpida (Quick Sort)
- Algorisme de Dijkstra
- Algorisme de Floyd-Warshall