Riassunti VERIFICATO
Riassunto di tutto il corso
168 visualizzazioni
29 download
Nessun voto ancora
Di cosa parla
Riassunto AI · si legge in un minuto
Questo documento offre un compendio essenziale di algoritmi e strutture dati fondamentali per l'informatica. Include algoritmi di ricerca (binaria, liste, hash), gestione di array statici e dinamici, operazioni su liste collegate, tavole hash (indirizzamento diretto, aperto, con chaining) e code (implementazioni su array e liste). Vengono trattati in dettaglio gli alberi (binari, K-ari, BST, Rosso-Neri) con operazioni di cardinalità, altezza, traversata, inserimento e cancellazione. Inoltre, copre gli heap (costruzione, inserimento, estrazione, ordinamento) e algoritmi sui grafi, inclusa la visita (DFS), componenti fortemente connesse, Minimum Spanning Tree (Kruskal, Prim) e cammini minimi (Dijkstra). Un riferimento rapido per lo studio degli algoritmi.
Leggi il riassunto completo
- Ricerca Binaria (BinSearch-Ric): Implementazione ricorsiva per la ricerca efficiente di un elemento in un array ordinato.
- Array Statici: Operazioni base di inserimento (ARRAY_INSERT), cancellazione (ARRAY_DELETE) e ricerca (ARRAYSEARCH) in array a dimensione fissa.
- Array Dinamici: Gestione di array con dimensione variabile, includendo inserimento (DYN_ARRAY_INSERT), cancellazione (DYN_ARRAY_DELETE) e espansione (ARRAY_EXTEND) con logiche di riallocazione.
- Liste: Algoritmi per la ricerca (LIST_SEARCH, LIST_SEARCH_SEN con sentinella), inserimento (LIST_INSERT, LIST_INSERT_SEN in testa) e cancellazione (LIST_DELETE, LIST_DELETE_SEN) in liste collegate, con e senza sentinelle.
- Tavole Hash (Indirizzamento Diretto): Operazioni di inserimento (TABLEINSERT), cancellazione (TABLEDELETE) e ricerca (TABLESEARCH) dirette.
- Tavole Hash (con liste/chaining): Inserimento (HASHINSERT), ricerca (HASHSEARCH) e cancellazione (HASHDELETE) tramite liste di appoggio per la gestione delle collisioni.
- Tavole Hash (Indirizzamento Aperto): Inserimento (HASHINSERT) e ricerca (HASHSEARCH) utilizzando una funzione hash con probing per risolvere le collisioni.
- Code (Implementazione con Array): Funzioni per determinare la dimensione (Size), verificare se vuota (Empty), calcolare la cella successiva (NextCell), inserire (Enqueue) ed estrarre (Dequeue) elementi.
- Code (Implementazione con Lista): Funzioni simili a quelle su array, ma basate su liste per l'inserimento (Enqueue), dimensione (Size), verifica di vuoto (Empty), accesso al fronte (Front) ed estrazione (Dequeue).
- Alberi (Binari K-ari): Calcolo della cardinalità (CARDINALITY_BINARY, CARDINALITY_K) e altezza (HEIGHT_BINARY, HEIGHT_K) degli alberi, oltre a una visita per livelli (VISITA_TREE).
- Alberi Binari di Ricerca (BST): Stampa in ordine (Stampa_inOrdine), ricerca ricorsiva (SearchRecursive) e iterativa (SearchIterative), ricerca del massimo (TrovaMassimo), successore (TrovaSuccessore), inserimento (Inserimento_BRT) e cancellazione (1_Cancellazione per un figlio, 2_Cancellazione per due figli).
- Alberi Rosso-Neri: Rotazione a sinistra (LEFT-ROTATE) e procedure di fix-up (RB-INSERT-FIXUP, RB-DELETE-FIXUP) per mantenere l'equilibrio dopo inserimenti e cancellazioni.
- Heap: Funzioni per navigare lo heap (PARENT, LEFT, RIGHT), inserimento (HEAP_INSERT), mantenimento della proprietà di heap (HEAPIFY), estrazione del massimo (HEAP-EXTRACT), costruzione (BUILD_HEAP) e ordinamento (HEAP-SORT).
- Algoritmi sui Grafi: Visita generica (VISITA_GENERICA), visita in profondità (DFS con INIT, VisitAll, Visit), e calcolo delle Componenti Fortemente Connesse (CFC).
- Algoritmo di Kruskal (MST-Kruskal): Per trovare un Minimum Spanning Tree usando insiemi disgiunti.
- Algoritmo di Prim (Primm): Per trovare un Minimum Spanning Tree usando una coda a priorità.
- Algoritmo di Dijkstra: Per trovare i cammini minimi da una sorgente singola in grafi con pesi non negativi.
Riassunto generato con l'intelligenza artificiale a partire dagli appunti. Come lo facciamo
Stai vedendo l'anteprima delle prime pagine. Il file completo è gratis: registrati per leggerlo tutto.
Studia questi appunti con l'AI
Riassunto e domande d'esame sono gratis: chiedili e ti mandiamo un'email quando sono pronti.
In preparazione: di solito è pronto in giornata.
Questo appunto è gratis. Registrati in 30 secondi per leggere tutte le pagine e scaricarlo.
Simula l'esame con domande costruite su questi appunti.
Di cosa parla l'insegnamento
ALGORITMI E STRUTTURE DATI · 2° anno · 9 CFU · INF/01
L’insegnamento ha lo scopo di introdurre i concetti e le tecniche fondamentali per l’analisi e la progettazione di algoritmi, che sono alla base dello sviluppo del software. Gli obiettivi dell'insegnamento degli algoritmi fanno parte degli Obiettivi formativi specifici del CdS in Informatica (L31), in particolare…