Riassunti VERIFICATO
Algoritmi e strutture dati
23 visualizzazioni
37 download
Nessun voto ancora
Di cosa parla
- Teorema del Master: Analizza le relazioni di ricorrenza tipiche degli algoritmi Divide et Impera, come T(n) = aT(n/b) + cn^β. Applicato a esempi come T(n) = 2T(n/2) + n/2 (O(n log n)).
- Analisi Ammortizzata: Valuta il costo medio di una sequenza di operazioni (es. ridimensionamento ArrayList, costo ammortizzato O(k)).
- Strutture Merge-Find (Disjoint Set Union): Gestiscono insiemi disgiunti.
- Quick Find: Rappresentante O(1), unione O(n).
- Quick Union: Unione O(1), rappresentante O(n).
- Euristiche (peso/rango): Ottimizzano find e merge a O(log n).
- Divide et Impera: Suddivisione, risoluzione ricorsiva, combinazione. Esempi: Torre di Hanoi (O(2^n)), moltiplicazione interi (Karatsuba, O(n^1.59)), matrici (Strassen, O(n^2.81)).
- Programmazione Dinamica: Tecnica bottom-up che risolve sottoproblemi una sola volta memorizzando i risultati. Esempi:
- Fibonacci: Da O(2^n) a O(n) (anche O(1) spazio).
- Sottovettore Massimo: O(n).
- Seam Carving: Rimodimensionamento immagini basato su costo minimo di “cuciture” di pixel.
- Algoritmi Greedy: Scelgono localmente l'opzione migliore per un ottimo globale. Esempi:
- Problema del Resto: Semplice scelta greedy.
- Codifica di Huffman: Crea codici a lunghezza variabile per caratteri, minimizzando la lunghezza totale.
- Algoritmi sui Grafi:
- Alberi di Copertura Minima (MST):
- Kruskal: Aggiunge archi in ordine di peso crescente se non formano cicli (usa Merge-Find). Complessità O(m log n).
- Prim: Cresce l'MST da un nodo iniziale aggiungendo l'arco di peso minimo. Complessità O(m log n).
- Percorsi Minimi:
- Bellman-Ford: Percorsi minimi da sorgente singola, gestisce pesi negativi (non cicli negativi). O(nm).
- Dijkstra: Percorsi minimi da sorgente singola con pesi non negativi. O((n+m) log n).
- Floyd-Warshall: Tutti i percorsi minimi, gestisce pesi negativi e rileva cicli. O(n^3).
- Alberi di Copertura Minima (MST):