Appunti VERIFICATO
2017 - Appunti_Algoritmi_by_Draghetti
105 visualizzazioni
5 download
Nessun voto ancora
Stai vedendo l'anteprima delle prime pagine. Registrati per sbloccare le pagine restanti.
Di cosa parla
- L'algoritmo di Dijkstra risolve il problema dei cammini minimi in grafi con pesi non negativi, mentre Kruskal calcola gli alberi ricoprenti minimi ordinando gli archi per costo crescente.
- L'algoritmo di Moore ottimizza lo scheduling dei programmi su un processore minimizzando le scadenze mancate, raggiungendo una complessità O(n log n) tramite l'uso di una coda di priorità a heap.
- Nel caso degli alberi binari di ricerca, la cancellazione non è commutativa e richiede distinzioni tra nodi foglia, nodi con un figlio e nodi con due figli sostituendoli con il successore.
- I metodi di gestione delle collisioni nelle tabelle hash includono la scansione lineare, quella quadratica e l'hashing doppio, tutti basati sulla ricerca della prima cella libera in sequenza.
- La tecnica Backtrack si fonda sul principio di costruire parzialmente una soluzione e annullarla per riprovare se il risultato non è quello previsto, utile anche nel matching delle stringhe.
Registrati e sblocca subito 3 appunti gratis, questo incluso.