2014
2014
Sei collegato come utente non registrato
Riepilogo dell'insegnamento: Algoritmi e strutture dati e laboratorio
| Informazioni generali | |||
| Corso di Laurea | Informatica | Percorso | Informatica |
|---|---|---|---|
| CFU | 10 | Università | MOLISE |
| Ore di didattica frontale per CFU | 8 | Settore Scientifico Disciplinare | INF/01 |
| Commento | L'obiettivo del corso è introdurre gli studenti alle tecniche di base per l'analisi e la progettazione degli algoritmi. Dopo aver affrontato i concetti fondamentali, il corso prende in esame le tecniche classiche di progettazione e valutazione di un algoritmo applicandole alla risoluzione di problematiche pratiche quali l'ordinamento, la selezione, la moltiplicazione tra matrici, la gestione delle code con priorità. Inoltre, saranno descritti ed analizzati gli algoritmi più diffusi e le strutture dati in essi utilizzate facendo riferimento agli aspetti di complessità computazionale e di correttezza. A tale scopo all'interno del corso sono inizialmente discussi, facendo particolare riferimento alla rappresentazione, gli ADT di base (Liste, Pile, Code, Grafi ed Alberi). Dopodichè la discussione viene spostata sugli algoritmi più noti atti a risolvere i problemi classici (Ricerca, Union Find, MST, SP, LCS). | ||
10 cfu così ripartiti nelle aree:
- 1 CFU nell'area A - Fondamenti
- 9 CFU nell'area B - Algoritmi
Sillabo dell'insegnamento
- A - Fondamenti
-
COM - Complessita'
Algoritmi e Programmi: Algoritmi, problemi e programma. Irresolubilità e intrattabilità. Modelli di calcolo. Complessità degli algoritmi. Algoritmi ottimali. Complessità degli algoritmi espressi in pseudo-codice. Regole per il calcolo di O. - B - Algoritmi
-
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Algoritmi ricorsivi: Ricorsione. Divide et Impera. Merge Sort. Algoritmo di Strassen. Metodi di risoluzione delle equazioni di ricorrenza ed il Teorema Principale. - *
SDF - Strutture di Dati Fondamentali
Heaps: Gli operatori della heap. Costruzione di una heap. Code con priorità. Heapsort. Tecniche Hash. Funzioni hash note. Schemi ad indirizzamento aperto. Schemi a concatenamento. - *
A - Algoritmi fondamentali
Bucket Sort. Limite inferiore degli algoritmi di ordinamento con scambi e confronti. L'algoritmo del bucket sort. Il problema della selezione. Introduzione e Algoritmo di selezione in tempo lineare. -
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
NP-Completezza. La classe P e NP, Le riduzioni, La classe NP-C, L'interrogativo: P=NP?, Tecniche di riconoscimento di un problema NP-C, Alcuni problemi NP-C - *
A - Algoritmi fondamentali
Problema della ricerca. Alberi binari di ricerca, alberi AVL, alberi 2-3, B- Alberi, Bit Vector - *
A - Algoritmi fondamentali
Union Find. Rappresentazione Quick Find, rappresentazione Quick Union, euristiche di bilanciamento, off line min problem - *
ASC - Algoritmi su Strutture Combinatorie
Minimo Albero Ricoprente. Formulazione del problema, la soluzione greedy, l'algoritmo di Kruskal, implementazione mediante l'ADT Union Find - *
ASC - Algoritmi su Strutture Combinatorie
Il problema del cammino di costo minimo. Formulazione del problema, soluzioni che si basano sulla distanza, algoritmo di Dijkstra: implementazione mediante coda semplice, implementazione mediante coda a priorità - *
A - Algoritmi fondamentali
Programmazione dinamica. Introduzione, la più lunga sottosequenza comune (LCS)
(*) Le sottoaree con asterisco sono quelle che il GRIN auspica facciano parte in via prioritaria dei sillabi degli insegnamenti assegnati all?area stessa
