Vai al contenuto principale Vai al footer
Università degli Studi di Parma Università degli Studi di Parma
Laurea in
Informatica
Università degli Studi di Parma
Dipartimento di Scienze Matematiche, Fisiche e Informatiche

ALGORITMI E STRUTTURE DATI I
cod. 14839

Anno accademico 2010/11
1° anno di corso - Secondo semestre
Docente
Grazia LOTTI
Settore scientifico disciplinare
Informatica (INF/01)
Ambito
Discipline informatiche
Tipologia attività formativa
Caratterizzante
76 ore
di attività frontali
9 crediti
sede:
insegnamento
in - - -
orari del corso non disponibili
appelli d'esame
Stampa

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;
• R. Sedgwick, Algorithms in C++, Princeton University.

Metodi didattici

Lezioni, esercitazioni ed esercitazioni in laboratorio.

Modalità verifica apprendimento

Esame scritto e orale.

Altre informazioni

- - -

Obiettivi agenda 2030 per lo sviluppo sostenibile

- - -