ALGORITMI E STRUTTURE DATI I
cod. 14839

Anno accademico 2012/13
2° anno di corso - Secondo semestre
Docente
Grazia LOTTI
Settore scientifico disciplinare
Informatica (INF/01)
Ambito
Attività formative affini o integrative
Tipologia attività formativa
Affine/Integrativa
63 ore
di attività frontali
9 crediti
sede: PARMA
insegnamento
in - - -

Obiettivi formativi

Scopo del corso e’ familiarizzare gli studenti con gli algoritmi, le strutture
dati e con le tecniche per analizzare la loro efficienza.

Prerequisiti

- - -

Contenuti dell'insegnamento

Il corso presenta un’introduzione alle piu' importanti strutture dati e alle tecniche
di programmazione.

Programma esteso

• Indecibilita', intrattabilita' dei problemi computazionali,
• Complessita' computazionale: modelli di calcolo, analisi di algoritmi.
• Tecnica divide et impera, relazioni di ricorrenza, Lemma fondamentale.
• Strutture dati di base: linked lists, stacks, queues, trees.
• Algoritmi di sorting basati sui confronti: Insertionsort, Mergesort, Quick-
sort, Heapsort.
• Limiti inferiori all’ordinamento e alla ricerca.
• Sorting in tempo lineare.
• Mediano and statistiche d’ordine.
• Introduzione alla programmazione dinamica e alla tecnica greedy.
• Alberi binari, alberi binari di ricerca, alberi AVL, B-alberi.
• Tabelle hash.
• Grafi, BFS,DFS, DAG, ordinamento topologico, componenti fortemente
connesse.
• Union-find, MST, algoritmo di Kruskal, algoritmo di Prim.
• Algoritmo di Dijkstra, algoritmo di Bellman-Ford.

Bibliografia

• T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms,
McGraw-Hill;
• C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e strutture dati,
McGraw-Hill;

Metodi didattici

Lezioni, esercitazioni ed esercitazioni in laboratorio.

Modalità verifica apprendimento

Esame scritto e orale.

Altre informazioni

- - -

Obiettivi agenda 2030 per lo sviluppo sostenibile

- - -

Referenti e contatti

Numero verde

800 904 084

Segreteria studenti

E-mail: segreteria.scienze@unipr.it
 

Servizio per la qualità della didattica

Manager della didattica:
dott.ssa Giulia Bonamartini
T. +39 0521 904157
E-mail servizio smfi.didattica@unipr.it
E-mail del manager giulia.bonamartini@unipr.it

Presidente del corso di studio

Prof. Luca Lorenzi
E-mail: luca.lorenzi@unipr.it

Delegato orientamento in ingresso

Prof. Luca Lorenzi
E-mail: luca.lorenzi@unipr.it

Delegato orientamento in uscita

Prof.ssa Chiara Guardasoni
E-mail: chiara.guardasoni@unipr.it

Docenti tutor

Prof. Emilio Acerbi
E-mail: emilio.acerbi@unipr.it

Prof. Marino Belloni
E-mail: marino.belloni@unipr.it

Prof.ssa Maria Groppi
E-mail: maria.groppi@unipr.it

Prof.ssa Chiara Guardasoni
E-mail: chiara.guardasoni@unipr.it

Prof. Luca Lorenzi
E-mail: luca.lorenzi@unipr.it

Prof. Costantino Medori
E-mail: costantino.medori@unipr.it

Prof. Adriano Tomassini
E-mail: adriano.tomassini@unipr.it

Delegati Erasmus

Prof. Leonardo Biliotti 
E-mail: leonardo.biliotti@unipr.it 
 

Responsabile assicurazione qualità

Prof.ssa Maria Groppi
E-mail: maria.groppi@unipr.it

Referente per le fasce deboli

Prof.ssa Fiorenza Morini
E-mail: fiorenza.morini@unipr.it