Università degli Studi di Parma

il mondo che ti aspetta
  • english version

menu

ALGORITMI E STRUTTURE DATI II

PARMA
COD. 16827
Insegnamento del corso di Laurea Magistrale in MATEMATICA
Struttura di riferimento: Dipartimento di Scienze Matematiche, Fisiche e Informatiche
Tipologia insegnamento: Affine/Integrativa
Lingua di insegnamento: Italiano

Obiettivi

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

La verifica finale dell'apprendimento viene effettuata tramite esame orale sugli argomenti discussi a lezione. In itinere è richiesto lo sviluppo di progetti e/o la presentazione di seminari su argomenti nel campo dell'algoritmica. Si intende in questo modo verificare l’abilità dello studente nella progettazione e valutazione delle soluzioni software.
La sufficienza può essere raggiunta dimostrando una conoscenza non superficiale degli strumenti di analisi e di sintesi di algoritmi visti a lezione.

Obiettivi

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 consigliata

• 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

La verifica finale dell'apprendimento viene effettuata tramite esame orale sugli argomenti discussi a lezione. In itinere è richiesto lo sviluppo di progetti e/o la presentazione di seminari su argomenti nel campo dell'algoritmica. Si intende in questo modo verificare l’abilità dello studente nella progettazione e valutazione delle soluzioni software.
La sufficienza può essere raggiunta dimostrando una conoscenza non superficiale degli strumenti di analisi e di sintesi di algoritmi visti a lezione.

ANNO ACCADEMICO: 2016/2017
Anno di corso: 1
SEMESTRE: Primo Semestre
NUMERO CFU: 6
SSD: INFORMATICA (INF/01)
AMBITO: Attività formative affini o integrative
Ore di attivita' frontale: 56
Ore di studio individuale: 94

Altri insegnamenti

ANNO DI CORSO: 1

ANNO DI CORSO: 2