Obiettivi formativi
Vengono studiati, progettati e analizzati algoritmi e strutture dati per la soluzione efficiente di problemi di varia natura, mettendo in evidenza i contesti applicativi in cui tali algoritmi e strutture dati possono essere applicati con successo. Questo corso prosegue e approfondisce gli argomenti trattati nel corso di Algoritmi e Strutture dati 1.
Conoscenza e capacità di comprensione:
Lo studente alla fine del corso avra’ migliorato la conoscenza dell’utilizzo, dell’implementazione e delle prestazioni dei principali algoritmi e delle più importanti strutture dati.
Capacità di applicare conoscenza e comprensione:
lo studente sarà in grado sia di effettuare l’analisi di un problema di media difficoltà, che di progettare, analizzare e valutare le soluzioni software.
Autonomia di giudizio:
Sarà in grado di valutare la qualità di una soluzione software in termini di efficienza e possibilità di riutilizzo. Sarà in grado di valutare le implicazioni dei suoi risultati algoritmici.
Abilità comunicative:
lo studente acquisirà la capacità di comunicare ed esprimere problematiche inerenti gli studi algoritmici, anche a un pubblico non esperto. Sarà in grado di evidenziare le ricadute tecnologiche delle teorie studiate.
Capacità di apprendimento:
lo studente avrà la capacità di aggiornarsi, con la consultazione di pubblicazioni scientifiche e testi avanzati propri del settore dell’algoritmica. Le conoscenze acquisite nel corso permetteranno allo studente di seguire corsi di master di primo livello e/o di laurea magistrale
Prerequisiti
Algoritmi e strutture dati 1, Fondamenti di Programmazione A
Contenuti dell'insegnamento
Questo corso approfondisce e prosegue lo studio degli argomenti trattati nel corso di Algoritmi e Strutture dati 1.
• tecnica greedy e programmazione dinamica: ulteriori applicazioni;
• algoritmi randomizzati, algoritmo di Miller-Rabin;
• calcolo parallelo, PRAM, algoritmi elementari, teorema di Brent;
• external memory model, k-way mergesort, distribution sorting;
• cache oblivious model, algoritmi elementari;
• algoritmi online, analisi competitiva; paging: LRU, Random, Marking; web caching: greedy dual, greedy dual size;
• geometria computazionale: inviluppo convesso, algoritmo sweeping;
• DFT-IDFT: algoritmo FFT, algoritmo di Cooley-Tuckey, prodotto di polinomi, FFT in strutture finite, algoritmo di Schonhage-Strassen per il prodotto di interi (cenni);
• string matching esatto: algoritmo Knuth-Morris-Pratt, algoritmo Boyer-Moore, suffix tree, suffix array;
• classi di complessita P, NP, NPC e loro relazioni, riduzioni polinomiali,
algoritmi di approssimazione.
Programma esteso
• tecnica greedy e programmazione dinamica: ulteriori applicazioni;
• algoritmi randomizzati, algoritmo di Miller-Rabin;
• calcolo parallelo, PRAM, algoritmi elementari, teorema di Brent;
• external memory model, k-way mergesort, distribution sorting;
• cache oblivious model, algoritmi elementari;
• algoritmi online, analisi competitiva; paging: LRU, Random, Marking; web caching: greedy dual, greedy dual size;
• geometria computazionale: inviluppo convesso, algoritmo sweeping;
• DFT-IDFT: algoritmo FFT, algoritmo di Cooley-Tuckey, prodotto di polinomi, FFT in strutture finite, algoritmo di Schonhage-Strassen per il prodotto di interi (cenni);
• string matching esatto: algoritmo Knuth-Morris-Pratt, algoritmo Boyer-Moore, suffix tree, suffix array;
• classi di complessita P, NP, NPC e loro relazioni, riduzioni polinomiali,
algoritmi di approssimazione.
Bibliografia
• F.P.Preparata, M.I.Shamos, Computational Geometry, Springer-Verlag, 1985.
• J.Kleinberg, E.Tardos, Algorithm design, Addison Wesley,2006.
• C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1994
• D.Gusfield, Algorithms on String, Trees, and Sequences: Computer science and Computational Biology, Cambridge University Press, 1997.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, third edition, 2011.
• C. Demestrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, McGraw Hill, seconda edizione, 2008.
• P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Pearson, prima edizione, 2006.
Metodi didattici
Lezioni frontali
Modalità verifica apprendimento
L'esame comprende una prova scritta ed un eventuale colloquio orale che viene effettuato per sciogliere residui dubbi di valutazione. La prova scritta consiste di alcune domande di teoria e di un certo numero di esercizi, da svolgersi senza poter consultare libri o appunti. Gli esercizi possono comportare la risoluzione di problemi che sono minime varianti di questioni viste a lezione, o richiedere la risoluzione di problemi che non coincidono con nessuno dei problemi visti a lezione, ma che possono essere risolti con le tecniche sviluppate in classe.
La sufficienza può essere raggiunta rispondendo correttamente alle domande e risolvendo correttamente gli esercizi del primo tipo.
Altre informazioni
- - -
Obiettivi agenda 2030 per lo sviluppo sostenibile
- - -
