---++ <font color=990000> <b>Programma del corso di Introduzione agli Algoritmi (canale EO, A.A. 2008-2009)</b></font> Se non diversamente specificato, i riferimenti bibliografici sono relativi al libro di testo "Algoritmi e strutture dati", 2/ed. Demetrescu, Finocchi, Italiano, !McGraw-Hill, 2008. *<font color= 990000 >a) Introduzione</font>* * Progettazione ed analisi di algoritmi * verifica di correttezza * analisi del tempo di esecuzione * analisi dell'occupazione di memoria * Un esempio "giocattolo": il calcolo dei numeri di Fibonacci _Rif._ Capitolo 1: tutto. *<font color= 990000 >b) Metodologie di analisi</font>* * Ordine di grandezza delle funzioni, la notazione asintotica O, Omega, Theta * Algebra della notazione asintotica; analisi delle costanti additive e moltiplicative * Delimitazioni inferiori e superiori alla complessità di un problema rispetto ad una data risorsa di calcolo * Analisi nel caso peggiore e migliore * Analisi di algoritmi ricorsivi: * equazioni di ricorrenza, albero della ricorsione * risoluzione di ricorrenze tramite analisi dell'albero della ricorsione * metodo dell'iterazione * metodo della sostituzione * il teorema fondamentale delle ricorrenze (teorema master): enunciato ed esempi. _Rif._ Capitolo 2: paragrafi 2.2, 2.3, 2.4 (tranne caso medio), 2.5. Appendice: paragrafi 17.1, 17.2, 17.4 *<font color= 990000 >c) Algoritmi di ricerca e di ordinamento</font>* * Ricerca sequenziale e binaria: analisi nel caso peggiore e migliore. * Delimitazione inferiore al tempo di esecuzione di algoritmi di ordinamento basati su confronti: alberi di decisione * Algoritmi di ordinamento quadratici (con analisi nel caso peggiore): insertionSort, selectionSort, bubbleSort * Un algoritmo di ordinamento ottimo basato sulla tecnica del divide et impera (con analisi nel caso peggiore): mergeSort * Un algoritmo di ordinamento ottimo basato sull'uso di strutture dati efficienti (con analisi nel caso peggiore): heapSort * la struttura dati heap * cancellazione del minimo e costruzione di un heap in tempo lineare * rappresentazione posizionale di alberi binari * ordinamento in loco * Un algoritmo efficiente nel caso medio: quickSort (analisi nel caso peggiore, intuizione caso medio) * Il concetto di stabilità nell'ordinamento. * Ordinamento in tempo lineare: algoritmi intergerSort e bucketSort _Rif._ Capitolo 2: paragrafo 2.4 (tranne caso medio). Capitolo 4: tutto tranne paragrafo 4.7. Appendice: paragrafo 17.4. Paragrafi 7.1, 7.2 e 7.4.1 del libro [CLRS01]. *<font color= 990000 >d) Dizionari</font>* * Implementazioni banali: array ordinati e liste collegate * Alberi binari di ricerca: * operazioni search, insert, delete * ricerca del massimo, del minimo, del predecessore e del successore * Bilanciamento in altezza: alberi AVL * calcolo del fattore di bilanciamento * limitazione superiore all'altezza di un albero AVL * rotazioni semplici e doppie * mantenimento del bilanciamento durante inserimenti e cancellazioni * Tabelle ad accesso diretto * Tabelle hash * funzioni hash perfette * uniformità semplice * paradosso del compleanno e collisioni * liste di collisione * indirizzamento aperto: scansione lineare, quadratica e doppia _Rif._ Capitolo 3: paragrafo 3.1. Capitolo 6: paragrafi 6.1 e 6.2. Capitolo 7: tutto. *<font color= 990000 >e) Strutture dati elementari ed alberi</font>* * Alberi: definizioni e proprietà fondamentali * Rappresentazioni in memoria * strutture indicizzate * strutture collegate * Algoritmo di visita generica di un albero * analisi del numero di iterazioni * tempo di esecuzione in funzione della rappresentazione usata * Richiami a pile e code * Visita in profondità (implementazione iterativa e ricorsiva) * visita preorder, simmetrica e postorder * esempi di applicazione delle visite * Visita in ampiezza _Rif._ Capitolo 3: tutto (tranne la tecnica del raddoppiamento-dimezzamento nel paragrafo 3.1). <!-- PROGRAMMA VECCHIO (2005-2006) *a) Richiami di concetti fondamentali* * Specifica di algoritmi; astrazione dei dati. * Progettazione, validazione, analisi e verifica di algoritmi. * Esempi di progetto di algoritmi. *b) Analisi di algoritmi* * Analisi di algoritmi: analisi del caso peggiore, medio, migliore. * Ordine di grandezza delle funzioni, notazione asintotica. * Algebra della notazione asintotica; analisi delle costanti additive e moltiplicative. * Richiamo degli algoritmi di ordinamento Bubble, Selection e Insertion Sort. * Calcolo della complessità degli algoritmi di ordinamento in forma iterativa. * Alberi di decisioni, limiti inferiori per l'ordinamento. * Il concetto di stabilità nell'ordinamento. * Ordinamento in tempo O(n): ordinamento per conteggio. * Algoritmi ricorsivi. * Confronto fra implementazione ricorsiva e iterativa di uno stesso algoritmo. * Risoluzione di ricorrenze per iterazione e tramite albero. * Calcolo della complessità nel caso peggiore dell'algoritmo di mergesort in forma ricorsiva. * Calcolo della complessità nel caso peggiore e migliore dell'algoritmo quicksort in forma ricorsiva. *c) Strutture dati:* * Gli alberi come tipi di dati astratti. Alberi binari, alberi m-ari. * Rappresentazione in memoria di alberi: rappresentazione tramite vettore o tramite struttura linkata; vettore dei padri. Rappresentazione degli alberi m-ari come alberi binari. * Visita di un albero per livelli. * Heap e code di priorità: costruzione di un heap, operazioni di inserimento e cancellazione. * Heapsort. * Calcolo della complessità nel caso peggiore dell'algoritmo heapsort in forma iterativa e ricorsiva. * I grafi come tipi di dati astratti. * Rappresentazione in memoria di un grafo: matrici e liste di adiacenza; matrici di incidenza; lista di archi. Ordinamento in tempo lineare di una lista di adiacenza. * Visita di un grafo: visita in ampiezza e in profondità. * Alberi ricoprenti. * Caratterizzazione di alberi ricoprenti ottenuti per visite in ampiezza e profondità. * Numerazione dei nodi degli alberi di copertura rispetto alla visita eseguita. * Partizione degli spigoli degli alberi di copertura rispetto alla visita eseguita. *d) Algoritmi su alberi e su grafi:* * Generazione del grafo complemento e del grafo trasposto. * Ricerca dei cicli in un grafo e caratterizzazione dei cicli tramite spigoli non dell'albero della visita in profondita'. * Ricerca delle componenti connesse di un grafo. * Ricerca dei cammini minimi da sorgente singola. * Come verificare se un grafo è bipartito o aciclico. * Ricerca di un accoppiamento massimale in un grafo. * Ricerca delle componenti debolmente e fortemente connesse in un grafo orientato. * 2 algoritmi per la generazione di un ordinamento topologico. *e) Gestione di dizionari:* * Alberi binari di ricerca : operazioni di ricerca, inserimento e cancellazione. * Ricerca del max, del min, del predecessore e del successore in un albero binario di ricerca. * Confronto della complessità delle operazioni di base sulle diverse strutture dati analizzate. * Alberi di ricerca bilanciati: alberi AVL. * Computo del fattore di bilanciamento. * Calcolo delle limitazioni inferiori e superiori per l'altezza di un albero AVL. * Operazioni di rotazione per ribilanciare un albero AVL dopo l'inserimento e la cancellazione. -->
This topic: Intro_algo/EO
>
WebHome
>
ProgrammaDelCorso
Topic revision: r3 - 2009-05-26 - IreneFinocchi
Copyright © 2008-2025 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback