Algoritmi e Strutture Dati I + Laboratorio di Informatica II D

(Corso di Diploma in Informatica)

Codice:

5I008

Crediti:

Semestre:

Sigla:

AS1

Docente

Roberto Grossi

Tel. 0502212793

Obiettivi di apprendimento

Definire formalmente la nozione di algoritmo.
Caratterizzare i dati da elaborare, organizzandoli e strutturandoli nel modo più opportuno al fine di agevolarne l'uso da parte degli algoritmi .
Progettare algoritmi corretti (che risolvono cioè sempre e solo il problema a cui si è interessati) ed efficienti (cioè che lo risolvono il più velocemente possibile o usano il minor spazio di memoria possibile), attraverso l'esame di diversi paradigmi.
Studiare le limitazioni inerenti dei problemi da risolvere, in particolare di quelli la cui soluzione richiede l'esame di tutte le possibilità.

Descrizione

Introduzione all'analisi e alla complessità degli algoritmi. Algoritmi ricorsivi e relazioni di ricorrenza. Algoritmi di ordinamento. Algoritmi greedy. Strutture dati elementari e avanzate. Enumerazione e non determinismo. Problemi NP-completi

English Description

Introduction to algorithm analysis and design. Recursive algorithms and recurrence relations. Sorting. Greedy algorithms. Elementary and advanced data structures. Enumeration and non-determinism. NP-complete problems.

Programma

Analisi di algoritmi e complessità (20 ore) Dimensione dei dati di un problema. Ordini di grandezza delle funzioni. Caso pessimo, ottimo e medio. Complessità polinomiale e superpolinomiale. Limiti superiori e inferiori della complessità di un problema. Tecniche per la dimostrazione di limiti inferiori. Relazioni di ricorrenza: metodi di soluzione e teorema principale.
Progetto di algoritmi (25 ore)
Divide et impera: Mergesort, Quicksort.
Moltiplicazione rapida.
Ordinamento in tempo lineare.
Algoritmi greedy.
Programmazione dinamica.
Strutture dati (20 ore) Strutture di base.
Dizionari. Realizzazione con vettori e tabelle hash.
Code con priorità.
Heap e Heapsort.
Alberi binari di ricerca, alberi bilanciati.
Grafi orientati e non orientati. Realizzazioni e visite in ampiezza e in profondità.
Problemi computazionalmente difficili (15 ore) Problemi decisionali, di ricerca e di ottimizzazione.
Enumerazione e backtracking. Non determinismo.
Classi di complessità. Le classi P e NP. Problemi NP-completi.

Ore lezione:

Ore esercitazione:

Bibliografia

T.H. Cormen, C.E. Leiserson, R.L. Rivest, "Introduzione agli algoritmi", Jakson Libri, Milano, seconda edizione 1999.

Modalità di esame

Scritto e orale