Corso di Algoritmi e Strutture Dati

 

 

Docente: Floriana Esposito
Dipartimento di Informatica
Universita' di Bari
Via Orabona 4
70126 Bari - Italy

Tel/Fax: +39 0805443264
Email: esposito@di.uniba.it

 

 

Corso di Laurea in Informatica -- Materiale didattico per l'anno accademico 2012-2013

 

Modulo 1: L'Astrazione in programmazione: dall'algoritmo ai tipi di dati astratti

Presentazione del corso. Il ruolo delle tecniche di astrazione nel progetto di programmi.

Modulo 2: Astrazioni e Algebre di dati

Dati e rappresentazioni, requisiti delle astrazioni di dati, costrutti. Astrazioni di dati e dati primitivi. Specifica sintattica e semantica. La realizzazione

Modulo 3: Strutture lineari di dati - Liste

Il concetto di sequenza. Le Liste: specifiche e realizzazioni attraverso rappresentazioni sequenziali e collegate. Esempi di problemi: epurazione, fusione di liste, ordinamento di liste

Modulo 4

Complessità degli algoritmi ed efficienza dei programmi

Modulo 5: Strutture lineari di dati - Pile e Code

Pile e Code: specifiche e realizzazioni attraverso rappresentazioni sequenziali e collegate. Pile e procedure ricorsive. Code e Pile come strutture ausiliarie.

Modulo 6: Insiemi

Specifiche, rappresentazione e confronto tra realizzazioni alternative

Modulo 7: Strutture non lineari

Generalità su alberi. Alberi binari: specifiche sintattiche e semantiche. Realizzazioni. Visita di alberi binari.

Modulo 8: Strutture non lineari

Alberi n-ari: specifiche e realizzazioni. Visita di alberi n-ari.

Modulo 9: Strutture non lineari

Alberi binari di ricerca.

Modulo 10: Code con priorità

Il tipo astratto coda con priorità: specifiche sintattiche e semantiche. Realizzazioni.

Modulo 11: Tabelle Hash e Dizionari

Generalità. Dizionari: Specifiche, rappresentazione e confronto tra realizzazioni alternative.

Modulo 12: Strutture non lineari

Il tipo astratto grafo: specifiche sintattiche e semantiche. Realizzazioni. Visita di un grafo.

Modulo 13: Tecniche algoritmiche (1)

Classificazione dei problemi: problemi di ricerca, di decisione, di ottimizzazione. Lo spazio di ricerca: definizione e proprietà . Paradigma selettivo e paradigma generativo.

Modulo 14: Tecniche algoritmiche (2)

Paradigma selettivo: la tecnica enumerativa e la tecnica di backtracking.

Modulo 15: Tecniche algoritmiche (3)

Paradigma generativo: tecnica golosa e tecnica Divide-et-Impera.

 

Moduli e Materiale didattico di Laboratorio