ALGORITMI E STRUTTURE DATI II
cod. 16827

Anno accademico 2014/15
2° anno di corso - Primo semestre
Docente
Grazia LOTTI
Settore scientifico disciplinare
Informatica (INF/01)
Ambito
Discipline informatiche
Tipologia attività formativa
Caratterizzante
48 ore
di attività frontali
6 crediti
sede: PARMA
insegnamento
in - - -

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

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.

Altre informazioni

- - -

Obiettivi agenda 2030 per lo sviluppo sostenibile

- - -

Referenti e contatti

Numero verde

800 904 084

Segreteria studenti


E. segreteria.scienze@unipr.it

Servizio per la qualità della didattica

Manager della didattica:
Dott.ssa Claudia Buga

T. 0521 902842
E. smfi.didattica@unipr.it
E. claudia.buga@unipr.it

Presidente del corso di studio

Prof. Alessandro Dal Palù
E. alessandro.dalpalu@unipr.it

Delegato orientamento in ingresso

Prof. Vincenzo Arceri
E. vincenzo.arceri@unipr.it

Delegato orientamento in uscita

Prof.ssa Chiara Guardasoni
E. chiara.guardasoni@unipr.it

Referente piani di studio

Prof. Flavio Bertini
E. flavio.bertini@unipr.it

Referente convalide

Prof. Andrea Munaro
E. andrea.munaro@unipr.it

Docenti tutor

Prof. Enea Zaffanella
E. enea.zaffanella@unipr.it

Delegati Erasmus

Prof. Andrea Munaro
E. andrea.munaro@unipr.it

Studente tutor per scambi all'estero (in definizione)
E.

Responsabile assicurazione qualità

Prof.ssa Chiara Guardasoni
E. chiara.guardasoni@unipr.it

Tirocini formativi

Referente prof. Enea Zaffanella
E. enea.zaffanella@unipr.it

Referente per le fasce deboli

Prof. Fiorenza Morini
E. fiorenza.morini@unipr.it

Studenti tutor

Tutor a.a. 2024-2025 
Dott. Saverio Mattia Merenda
Tutorato a sportello tutti i venerdì 9:00-10:30 in aula M a Matematica previo appuntamento via e-mail:
E. saveriomattia.merenda@studenti.unipr.it
 

Rappresentanti degli studenti in CCSU

  • Lorenzo Copelli
  • Alessandro Frasconi
  • Marcello Galli
  • Samuel Seligardi