Programma Preliminare
Algoritmi e Strutture Dati + Laboratorio (Corso B) a.a.2002/2003
Docente: Costabile Maria Francesca
I Algoritmi e strutture dati

1. Algoritmi e programmi
   Lo sviluppo del software e la qualitą dei programmi. Principi di    
   progettazione e tecniche di programmazione. Il ruolo delle tecniche di  
   astrazione nel progetto di programmi: Astrazione dei dati e astrazione  
   funzionale. 
2. Algebre di dati
   Dati e rappresentazioni,requisiti delle astrazioni di dati,costrutti.   
   Astrazioni di dati e dati primitivi. Specifica sintattica e semantica  
   tramite pre- e post-condizioni sulle operazioni. La realizzazione 
3. Strutture lineari di dati
   Liste: specifiche, realizzazioni attraverso rappresentazioni  
   sequenziali e collegate. Pile: specifiche e realizzazioni alternative,  
   pile e procedure ricorsive. Code: specifiche e realizzazioni  
   alternative.Valutazione della complessitą degli operatori realizzati.   
   Scelta, implementazione e verifica di algoritmi per la ricerca,  
   l'ordinamento e la fusione delle strutture dati proposte 
4. Insiemi e Dizionari
   Specifiche e confronto tra realizzazioni alternative. Dizionari: 
   realizzazioni con vettori ordinati e tabelle Hash 
5. Strutture non lineari di dati
   Matrici. Alberi:alberi ordinati e relative proprietą. Alberi binari:    
   caratteristiche, la corrispondenza con le liste, specifiche e  
   realizzazioni . Alberi n-ari: specifiche, visita di alberi,  
   realizzazioni alternative con liste di figli e area libera. Grafi 
6. Code con prioritą
   Generalitą. Specifiche e realizzazioni con liste, alberi binari, heap 
7. Alberi bilanciati di ricerca
   Alberi AVL: generalitą e specifiche. Algoritmi di inserimento,  
   cancellazione e ricerca 
8. Tecniche per il progetto di algoritmi.
 
II Laboratorio

- Introduzione al C++: Struttura di un programma C++, tipi di dato,  
  espressioni ed istruzioni semplici, strutture di controllo, funzioni con 
  e senza parametri 
- Classi: Definizione, campi pubblici e privati, costruttori, funzioni 
  proprie, funzioni esterne, funzioni inline, funzioni friend, funzioni 
  operatori 
- Ereditarietą: Classi derivate, parte pubblica e protetta, ridefinizione 
  di funzioni e dati, ereditarietą multipla.
 
III Esercitazioni

- Implementazione di strutture dati in C++: 
- Realizzazione di strutture lineari dinamiche e di strutture non lineari
  in C++: liste, pile, code, alberi, dizionari,... 
- Implementazioni di alcuni algoritmi di gestione delle strutture dati in 
  C++.
 
Libri di riferimento

- M. Cadoli, M. Lenzerini, P. Naggar, A. Schaerf ''Fondamenti della 
  progettazione dei programmi'', Citta' Studi Edizioni 
- A. Bertossi ''Algoritmi e Strutture di Dati'' UTET 
- H.M. Deitel, P. J. Deitel, ''C++ Fondamenti di programmazione e 
  progettazione orientata agli oggetti con UML'', Apogeo