Programmazione 2 (canale P-Z)

Corsi di Laurea in Informatica/Tecnologie Informatiche

Anno Accademico 2007/08

Stefano Guerrini

guerrini at di.uniroma1.it

Calendario delle Lezioni e
Argomenti Trattati

[ Lezioni ] [ Sorgenti ] [ Esercitazioni ] [ Corso 2007-08 ] [ Pagina principale ]

• lun 25/02
  
• mer 27/02
  
• lun 03/03
  Il principio di induzione. Semplici esempi di funzioni ricorsive: il fattoriale, l'algoritmo di eulero, Fibonacci. Ricorsione multipla ed esplosione esponenziale. Definizioni ricorsive efficienti: calcolo dell'esponenziale. Fibonacci efficiente. Implementazione della ricorsione: record di attivazione e stack delle chiamate di funzione. Costo della ricorsione. Tail recursion. Vantaggi e svantaggi della ricorsione. Stampa invertita di una stringa letta da input.
  • Lucidi: Ricorsione (formato pdf, 4 lucidi per pagina).
  • Sorgenti: Fattoriale
  • Sorgenti: Algoritmo di Eulero per il MCD
  • Sorgenti: Fibonacci
  • Sorgenti: Esponenziale

• mer 05/03
  Cenni di complessità asintotica
  Costo di esecuzione dei programmi. Spazio. Tempo: funzione costo, caso peggiore, analisi asintotica. Esplosione esponenziale. Le costanti. Costanti e analisi asintotica. Upper e lower-bound.
  • Lucidi: Costo (formato pdf, 4 lucidi per pagina).

• lun 10/03
  Esercitazioni

• mer 12/03
  Cenni di complessità asintotica
  Notazione O-grande, Omega-grande, Teta-grande. Operazione dominante.
  Tipi di dato astratti
  Definizione e semplici esempi. Pile e code.
  • Lucidi: Costo (formato pdf, 4 lucidi per pagina).
  • Lucidi: ADT (formato pdf, 4 lucidi per pagina).

• lun 10/03
  Esercitazioni

• mer 19/03
  Struttura di un tipo di dato astratto: interfaccia e implementazione.
  Implementazione di pile.
  • Sorgenti: Pile implementate mediante liste
  • Sorgenti: Pile implementate con vettori
  • Sorgenti: Pile mediante liste con gestione errore
  • Sorgenti: Pile mediante vettori con gestione errore

• mer 26/03
  Esercizi su pile. Parentesi bilanciate.
  • Sorgenti: Bilanciamento parentesi (versione con pila)
  • Sorgenti: Bilanciamento parentesi (versione ricorsiva)
    La soluzione ricorsiva pubblicata sul sito è leggermente diversa da quella vista a lezione, usa un while al posto di una ricorsione di coda. Nei prossimi giorni sarà pubblicata anche la soluzione vista a lezione.

• lun 31/03
  Implementazione di code.
  • Sorgenti: Code implementate mediante liste
  • Sorgenti: Code implementate con vettori

• mer 02/04
  Esercizi

• lun 07/04
  Esercizi

• mer 09/04
  Esercitazioni

• lun 14/04
  Sospensione della didattica per le elezioni politiche

• mer 16/04
  Un esempi di backtracking, la risoluzione di un labirinto.
  Soluzione ricorsiva e soluzione iterativa con pila.
  
  • Sorgenti: Labirinto

• lun 21/4 - gio 24/5 Settimana prove intermedie
  mer 23/4 Esonero

• lun 28/04
  Alberi binari: definizione di base.
  
  • Lucidi: ADT (formato pdf, 4 lucidi per pagina).

• mer 30/04
  Esercitazioni

• lun 05/05
  Alberi binari bilanciati.
  
  • Lucidi: ADT (formato pdf, 4 lucidi per pagina).

• mer 07/05
  Esercizi su alberi binari.

• lun 12/05
  Rappresentazione con vettori di alberi binari. Rappresentazione parentetica di alberi binari. Lettura di alberi binari.
  Alberi binari di ricerca.
  
  • Lucidi: ADT (formato pdf, 4 lucidi per pagina).

• mer 14/05
  Esercitazioni

• lun 19/05
  Versione iterativa della visita in preordine di un albero (visita mediante stack). Atre visite iterative: utilizzo di una coda, visita per livelli.
  Alberi n-ari: rappresentazione mediante lista dei figli, rappresentazione mediante albero binario.
  

• mer 21/05
  Testing.
  Versione finale della soluzione del problema del labirinto.
  
  • Lucidi: ADT (formato pdf, 4 lucidi per pagina).
    
  • Sorgenti: Labirinto

• lun 26/05
  Valutazione di espressioni in notazione infissa e in notazione polacca.
  
  • Sorgenti: Espressioni

• mer 28/05
  Esercizi.

• lun 02/06
  FESTA

• mer 04/06
  Esercizi di verifica.

• lun 09/06
  Esercitazioni di preparazione all'esame.

• mer 11/06
  Esercitazioni di preparazione all'esame.