Appunti VERIFICATO

2017 - Appunti_Algoritmi_by_Draghetti

Università degli Studi di Milano sicurezza dei sistemi e delle reti informatiche 2017
157 visualizzazioni
5 download
Nessun voto ancora
Condividi: WhatsApp Telegram

Di cosa parla

Riassunto AI · si legge in un minuto

I riassunti degli appunti coprono algoritmi fondamentali come Dijkstra per i cammini minimi, Kruskal per gli alberi ricoprenti e Moore per lo scheduling. Vengono inoltre analizzate le strutture dati, inclusi gli alberi binari di ricerca con le loro visite in ordine, preordine e postordine, e la gestione delle cancellazioni non commutative. Il testo descrive anche tecniche di hashing per gestire le collisioni, l'approccio backtracking per la costruzione di soluzioni e il funzionamento del QuickSort nel caso peggiore. Infine, si menzionano concetti come grafi planari e alberi AVL bilanciati essenziali per l'efficienza computazionale.
Leggi il riassunto completo
  • 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.

Riassunto generato con l'intelligenza artificiale a partire dagli appunti. Come lo facciamo

Anteprima pagina 1 — 2017 - Appunti_Algoritmi_by_Draghetti Anteprima pagina 2 — 2017 - Appunti_Algoritmi_by_Draghetti Anteprima pagina 3 — 2017 - Appunti_Algoritmi_by_Draghetti

Stai vedendo l'anteprima delle prime pagine. Registrati per sbloccare le pagine restanti.

Studia questi appunti con l'AI

Riassunto e domande d'esame sono gratis: chiedili e ti mandiamo un'email quando sono pronti.

Registrati e scarica gratis questo appunto.

Simula l'esame con domande costruite su questi appunti.

Di cosa parla l'insegnamento

Algoritmi e strutture dati · 2° anno · 1° semestre · 12 CFU · INFO-01/A

L'insegnamento ha l'obiettivo di introdurre i concetti fondamentali relativi alla progettazione e analisi di algoritmi e delle strutture dati che questi utilizzano. L'insegnamento illustrerà le principali strutture dati e si focalizzerà su alcuni algoritmi specifici, studiandone anche la complessità computazionale.…

Scheda completa nella pagina del corso

Altri appunti di Algoritmi e strutture dati

Condividi questi appunti

WhatsApp Telegram