Riassunto esame Algoritmi e strutture dati, Prof. Cabodi Giampiero, libro consigliato Appunti di Algoritmi e strutture Dati, Antonio Emmanuel Messina

Algoritmi E Strutture Dati | Messina Antonio Emmanuel ALGORITMI E STRUTTURE DATI MESSINA ANTONIO EMMANUEL Politecnico di Torino 2023/2024 pag. 0 Algoritmi E Strutture Dati | Messina Antonio Emmanuel Gli appunti sono divisi in due parti analogamente all’organizzazione del corso. Si consiglia di dare prima un’occhiata alla parte di programmazione per capire meglio alcune strutture dati utilizzate nella parte di teoria. In caso di errori, sviste, contattarmi personalmente scrivendo una mail a mesemi26@gmail.com. Indice TEORIA T.1 Ricorsione • T.1.1 Introduzione • T.1.2 Analisi di Complessità • T.1.3 Problemi ricorsivi in ambito matematico • T.1.3.1 Fattoriale • T.1.3.2 Fibonacci • T.1.3.3 Massimo comun divisore • T.1.3.4 Il massimo di un vettore • T.1.3.5 Ricerca binaria • T.1.3.6 Torri di Hanoi • T.1.3.7 Righello • T.1.4 Meccanismi computazionali per eseguire funzioni ricorsive • T.1.5 Ordinamenti Ricorsivi • T.1.5.1 Merge Sort • T.1.5.2 Quick Sort T.2 Problemi di ricerca e ottimizzazione • T.2.1 Introduzione • T.2.2 Esplorazione • T.2.3 Calcolo combinatorio • T.2.4 Insieme delle parti • T.2.5 Esplorazione esaustiva dello spazio delle soluzioni • T.2.6 Principio di moltiplicazione • T.2.7 Modelli • T.2.7.1 Disposizioni semplici • T.2.7.2 Disposizioni ripetute • T.2.7.3 Permutazioni semplici • T.2.7.4 Permutazioni ripetute • T.2.7.5 Combinazioni semplici • T.2.7.6 Combinazioni ripetute • T.2.7.7 L’insieme delle parti • T.2.7.8 Partizioni di insieme • T.2.8 Esplorazione esaustiva dello spazio delle soluzioni: singola soluzione • T.2.9 Pruning T.3 Esempi di problemi di ricerca e di ottimizzazione • T.3.1 Controllo di lampadine • T.3.2 Longest Increasing Sequence • T.3.3 Le 8 regine • T.3.4 Aritmetica Verbale • T.3.5 I 36 ufficiali di Eulero • T.3.6 Sudoku T.4 Programmazione dinamica • T.4.1 Introduzione alla programmazione dinamica • T.4.2 Catena di montaggio • T.4.3 Parentesizzazione ottima pag. 1 Algoritmi E Strutture Dati | Messina Antonio Emmanuel • T.4.4 Longest Increasing Sequence • T.4.5 Lo zaino (discreto) • T.4.6 Memoization T.5 Paradigma Greedy • T.5.1 Attività compatibili • T.5.2 Il cambiamonete • T.5.3 Lo zaino discreto/continuo • T.5.4 Codici di Huffman T.6 Code a Priorità e Heap • T.6.1 ADT Heap • T.6.2 Coda a priorità T.7 Alberi binari di ricerca • T.7.1 Alberi binari • T.7.2 Esempi d’uso • T.7.3 Alberi Binari di ricerca BST • T.7.4 Estensione dei BST elementari • T.7.5 Interval BST T.8 Tabelle di Hash • T.8.1 Tabelle di Hash • T.8.2 Tipologie di funzioni di hash • T.8.3 Linear Chaining e Open Addressing • T.8.4 Funzioni di probing T.9 Teoria dei grafi • T.9.1 Modello di grafo • T.9.2 ADT Grafo • T.9.3 Multigrafo • T.9.4 Generazione casuale dei grafi • T.9.5 Cammino semplice • T.9.6 Cammino di Hamilton T.10 Algoritmi di visita dei grafi • T.10.1 Visita in profondità (DFS) • T.10.2 Vis