Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/safehtml.php on line 308
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 159
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 161
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 162
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 163
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 165
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 166
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 167
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 243
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 250
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 259
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 266
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 273
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 280
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 467
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 469
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 471
Diario delle lezioni
Settimana 1
Lunedi 14 Gennaio
Inquadramento del corso. Metodologie dell'ingegneria degli algoritmi: analisi dei requisiti, valutazione difficoltà, progetto algoritmo, analisi teorica, implementazione, analisi sperimentale e ingegnerizzazione [
T2, capitolo 1] [
S1]. Esempi di differenze tra teoria e pratica: domini numerici in matematica vs. loro rappresentazione negli elaboratori, costo temporale asintotico vs. secondi, modello piatto della memoria vs. memoria gerarchica (esempio della scansione di una matrice per righe e per colonne [
T3, paragrafo 6.2][
L3]), costo costante per operazione vs. pipeline nei microprocessori, ecc. [
S1].
Martedi 15 Gennaio
Il problema della verifica di duplicati in una sequenza: progetto, analisi, implementazione e validazione sperimentale della predizione di costo teorica; soluzioni con costi teorici O(n
2), O(n log n) e O(n); problematiche e tranelli implementativi usando il Java Collections Framework [
T2, capitolo 1]. Workflow di progetto, analisi teorica e implementazione di algoritmi [
S1].
Mercoledi 17 Gennaio
Metodologie di analisi sperimentale di algoritmi: specifica obiettivi, definizione dell'impianto sperimentale e interpretazione dei risultati. Aspetti legati all'impianto sperimentale: dati di test reali e sintetici, piattaforma di calcolo, misure di prestazioni, riproducibilità [
T2, capitolo 1] [
A1]. Esempi di conclusioni errate ed esempi di conclusioni corrette. Stessa interfaccia, algoritmi diversi: realizzazione polimorfica mediante late binding in Java [
T2, capitolo 1].
Settimana 2
Lunedi 21 Gennaio
Tecniche di analisi ammortizzata. Il metodo dei crediti. Esempio del contatore binario [
T1, capitolo 2]. Tecniche di rappresentazione efficiente di strutture lineari dinamiche mediante array: la tecnica del raddoppiamento/dimezzamento [
T1, capitolo 3].
Martedi 22 Gennaio
Tipo di dato
ArrayDinamico: implementazione basata su array con tecnica del raddoppiamento/dimezzamento ed analisi ammortizzata del costo delle operazioni [
T1, capitolo 3].
Mercoledi 23 Gennaio
Metodi per ridurre gli errori di misurazione dei tempi di esecuzione, se troppo bassi rispetto alla precisione delle primitive di accesso al tempo di sistema. Picchi spuri sul tempo di esecuzione e loro eliminazione in fase di analisi dei risultati [Appunti]. Implementazione del tipo di dato ArrayDinamico con tempo di esecuzione O(log* n) per operazione nel caso peggiore [Appunti] e definizione della funzione logaritmo iterato log* [
L1]. Idee per l'implementazione del tipo di dato ArrayDinamico con tempo di esecuzione O(1) per operazione nel caso peggiore [Appunti].
Settimana 3
Lunedi 28 Gennaio
Analisi delle prestazioni dell'algoritmo per la verifica dei duplicati basato su tabelle hash: calcolo della probabilità di avere duplicati in una sequenza casuale (paradosso del compleanno) [
L2]. Discussione di possibili implementazioni del tipo di dato ArrayDinamico con tempo di esecuzione O(1) per operazione nel caso peggiore [Appunti].
Martedi 29 Gennaio
Soluzione homework 2: implementazione semplificata di ArrayDinamico con tempo di esecuzione O(1) per operazione nel caso peggiore e spazio O(n). Confronto prestazionale di ArrayDinamico e delle classi Java standard ArrayList e LinkedList: tempo medio e tempo massimo per operazione. Analisi sperimentale del comportamento del gestore di memoria della JVM su una sequenza casuale di allocazioni/deallocazioni di blocchi di dimensione fissa: possibile deterioramento esponenziale delle prestazioni quando ci si avvicina alla massima dimensione di heap [
S2].
Mercoledi 30 Gennaio
Sviluppo di un semplice allocatore in Java per blocchi di dimensione fissa; confronto sperimentale dell'allocatore su una sequenza di operazioni casuali di allocazione/deallocazione di blocchi di dimensione fissa rispetto al gestore di memoria della JVM.
Settimana 4
Lunedi 4 Febbraio
Strategie, politiche e meccanismi di allocazione della memoria. Politiche di allocazione: pattern di riuso della memoria, divisione/fusione di blocchi, problematiche di selezione dei blocchi liberi, soglie nella divisione dei blocchi. Meccanismi implementativi: header, boundary tags e allineamento dei blocchi; link integrati nei blocchi; lookup table; trattamento speciale dei blocchi di piccole dimensioni; trattamento speciale dell'ultimo blocco dello heap. Cenni ai meccanismi di allocazione: sequential fit, segregated free lists, buddy systems, indexed fits, bitmapped fits [
A2]. Buddy system binari [
T4, Volume 1, Paragrafo 2.5]. Cenni a Fibonacci buddies, buddies pesati e buddies doppi [
A2]. Cenni ai meccanismi impiegati dalle versioni moderne dell'allocatore malloc.c incluso nelle distribuzioni Linux/FreeBSD [
C2, C3, C4]. Introduzione all'homework 5 sugli allocatori di memoria.
Martedi 5 Febbraio
Realizzazione in Java di una struttura dati grafo. Rappresentazione mediante liste di adiacenza con tecnica di cancellazione lazy degli archi e analisi ammortizzata [
T1, capitolo 12]. Garbage collection periodico per la rimozione dei nodi eliminati [A].
Mercoledi 6 Febbraio
Lezione annullata per malattia del docente.
Settimana 5
Lunedi 11 Febbraio
Schema di visita generica di grafi, classe Java VisitaGenerica e specializzazione mediante late-binding dei metodi [
T1, capitolo 12]. Esempi di specializzazione mediante estensione della classe VisitaGenerica: visita in ampiezza (BFS) [
T1, capitolo 12], calcolo del cammino minimo da un nodo sorgente a tutti gli altri nodi nel caso pesato (Dijkstra) [
T1, capitolo 14] e non pesato (BFS) [
T1, capitolo 12].
Martedi 12 Febbraio
Modelli di costo che tengono in considerazione la struttura gerarchica delle memorie: modello a due livelli con conoscenza della block size (modello a memoria esterna). Misura di prestazioni in termini di numero di accessi alla memoria lenta (I/O) in funzione della dimensione N dei dati, della block size B e della dimensione della memoria interna M [
T1, capitolo 2]. Progetto di algoritmi e strutture dati efficienti nel modello a memoria esterna: la struttura dati B-tree. Altezza massima di un B-tree di ordine t. Operazioni di inserimento, cancellazione e ricerca di una chiave in un B-tree di ordine B e costi in termini di numero di operazioni T(N) e di accessi a disco IO(N,M,B) [
T1, capitolo 6].
Mercoledi 13 Febbraio
Realizzazione di un B-tree in linguaggio C: strutture dati e dettagli implementativi [
codice∞].
Settimana 6
Lunedi 18 Febbraio
Realizzazione di un B-tree in linguaggio C: implementazione delle operazioni search e insert [
codice∞]. Analisi sperimentale delle prestazioni della insert su una sequenza di inserimenti di chiavi casuali [A].
Martedi 19 Febbraio
Lower bound sul numero di I/O richiesti da qualunque algoritmo di ricerca in un dizionario in memoria esterna in un modello basato su confronti [
A4].
Mercoledi 20 Febbraio
Ordinamento in memoria esterna: algoritmo multiway mergesort. Lower bound sul numero di I/O richiesti da qualunque algoritmo di ordinamento in memoria esterna in un modello basato su confronti [
A3, S3, S4].
Settimana 7
Lunedi 25 Febbraio
Lower bound sul numero di confronti per il problema dell'ordinamento. Dimostrazioni di lower bound basate su alberi di decisione. Esempio di algoritmo di ordinamento in tempo lineare (bucketsort) non basato su confronti. Il tipo di dato coda con priorità. La struttura dati d-heap e le sue proprietà. Altezza di un d-heap con n nodi. Rappresentazione di un d-heap mediante array [
T1].
Martedi 26 Febbraio
Alberi binomiali e heap binomiali. Realizzazione di una coda con priorità basata su heap binomiali [
T1].
Mercoledi 27 Febbraio
Heap binomiali rilassati e analisi ammortizzata delle operazioni. Numeri di Fibonacci e sezione aurea. Heap di Fibonacci: proprietà strutturali [
T1].
Settimana 8
Lunedi 3 Marzo
Operazione DecreaseKey negli Heap di Fibonacci: analisi di costo ammorizzato e analisi di correttezza (dimensione minima di ogni sottoalbero nell'heap) [
T1].
Martedi 4 Marzo
Aspetti implementativi connessi con la realizzazione di code con priorità: tipo di dato albero radicato ennario non ordinato e sua implementazione mediante struttura dati primo figlio-fratello successivo. Studio delle prestazioni di un d-heap in funzione del rapporto K fra il numero di operazioni insert+decreaseKey e delete+deleteMin+increaseKey in una sequenza di operazioni. Prestazioni di un K-heap e sua applicazione all'algoritmo di Dijkstra per il calcolo dei cammini minimi a sorgente singola in un grafo [
T2].
Mercoledi 5 Marzo
Interfaccia Java CodaPriorita. Realizzazione di un d-heap in Java: strutture dati e operazioni muoviAlto, muoviBasso, scambia. Realizzazione di un heap binomiale in Java, strutture dati e operazioni insert e ristruttura. Heap binomiali rilassati come estensione degli heap binomiali e heap di Fibonacci come estensione degli heap binomiali rilassati [
T2].
Settimana 9
Lunedi 10 Marzo
Progetto di algoritmi che traggono vantaggio da proprietà strutturali dell'input. Esempio del calcolo dei cammini minimi fra tutte le coppie di nodi in un grafo con pesi non negativi. Richiami sull'algoritmo di Dijkstra, correttezza e tempo di esecuzione [
T1]. Implementazione come specializzazione dell'algoritmo di visita generica [
T2]. Nozione di cammini localmente minimi e loro proprietà. Numero di cammini localmente minimi in un grafo con cammini minimi unici. Tie-breaking rule deterministica per grafi con cammini minimi multipli e cammini minimi canonici [
S5].
Martedi 11 Marzo
Variante dell'algoritmo di Dijkstra per il calcolo dei cammini minimi fra tutte le coppie di nodi (
Dijkstra_APSP). Ulteriore variante basata su cammini localmente minimi (
Dijkstra_APSP_LSP). Analisi di correttezza e tempo di esecuzione [
S5].
Mercoledi 12 Marzo
Discussione risultati sperimentali dell'algoritmo
Dijkstra_APSP_LSP su reti stradali USA e su grafi casuali. Riepilogo argomenti del corso.