Fondamenti di Informatica II: Registro lezioni A.A. 2000-01

Università di Roma "La Sapienza" -- Facoltà di Ingegneria

Registro del corso di
Fondamenti di Informatica II
Prof. Marco Cadoli
Corso di Laurea in Ingegneria Informatica
Anno Accademico 2000-01

Materiale didattico: testi di riferimento

[T1] M. Cadoli, M. Lenzerini, P. Naggar, A. Schaerf, Fondamenti della progettazione dei programmi: principi, tecniche e loro applicazione in C++, CittàStudiEdizioni, UTET Libreria, 1997.
[T2] M. Cadoli, M. Lenzerini, E. Panizzi, A. Schaerf, Esercizi di progettazione dei programmi in C++, UTET Libreria, 1998.
[T3] C. Batini, L. Carlucci Aiello, M. Lenzerini, A. Miola, A. Marchetti Spaccamela, Fondamenti di Programmazione dei Calcolatori Elettronici, Franco Angeli, 10a edizione, 1999.
[T4] D. M. Capper, Introduzione a C++ per le scienze e l'ingegneria, McGraw-Hill, 1997.
[D] M. Cadoli, G. De Giacomo, M. Schaerf, Programmazione orientata agli oggetti e Java, in M. Cadoli, M. Lenzerini, Dispensa del corso A.A. 2000/01. In distribuzione presso la libreria L'UNIVERSITARIA, V.le Ippocrate 99, Roma.

PRIMA PARTE

Lezioni 1,2 -- 28/2/2001

Argomenti trattati [T1, Par. 3.1, 3.2, 3.3] [T4, Cap. 2 e Cap. 4]

Presentazione del corso
Introduzione al C++
Struttura di un programma C++
Istruzioni, cicli, dichiarazioni, istruzioni di I/O

Programmi svolti

Stampa di un messaggio sullo schermo (file ciao.cpp)
Stampa della somma dei primi 10 numeri naturali (file somma.cpp)
Stampa della somma di 10 numeri interi letti da tastiera (file leggi.cpp)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Struttura del corso e sue relazioni con altri corsi
- Materiale didattico che si utilizza nel corso (si veda anche il programma d'esame)
- Differenza tra programmazione e progettazione del software
- Scrivere e provare semplici programmi C++
Esercizi proposti
- Riscrivere il programma della stampa della somma di 10 numeri interi letti da tastiera usando il costrutto while al posto del for (file leggi2.cpp)
- Scrivere un programma C++ per la stampa di una piramide di asterischi (soluzione: file piramide.cpp)

Lezioni 3,4 -- 1/3/2001

Argomenti trattati [T1, Par. 3.1, 3.2, 3.3] [T4, Cap. 2 e Cap. 4]
- Istruzioni di ciclo
- Istruzioni condizionali
- Funzioni in C++ (iterative e ricorsive)
- Overloading di funzioni; argomenti di default
- Modalità del passaggio di parametri ad una funzione
- Esecuzione di funzioni ricorsive (si veda una simulazione del calcolo del fattoriale )
Programmi svolti
- Differenza fra while e do ... while (file do-while.cpp)
- Stampa del massimo fra due numeri interi letti da tastiera (file max.cpp)
- Fattoriale iterativo (calcolato nel main()) (file fatt.cpp)
- Fattoriale iterativo (calcolato mediante funzione apposita) (file fattoriale.cpp)
- Fattoriale ricorsivo (calcolato mediante funzione apposita) (file fattric.cpp)
- Passaggio di un parametro per valore e per riferimento (file ordina.cpp)
- Funzioni sovraccariche e con argomenti di default (file overloading-funzioni.cpp)
Cosa lo studente dovrebbe sapere dopo la lezione
- Scrivere qualsiasi programma C++ che non richieda l'utilizzo di strutture di dati
- Come strutturare un programma C++ in più funzioni
Esercizi proposti
- Scrivere un programma C++ per lettura di n numeri interi positivi da tastiera e calcolo del massimo (soluzione: file printmax.cpp)
- Scrivere un programma C++ per la stampa di una piramide di numeri (soluzione: file piramide2.cpp)
- Scrivere un programma per il calcolo della data del giorno successivo (soluzione: file data.cpp)
- Scrivere un programma che legga da tastiera una sequenza di 0 e 1, terminata da 2 e calcoli la lunghezza della più lunga sottosequenza di 0, e la stampa. ESEMPIO: 0 0 1 0 1 0 0 0 2: STAMPA 3

Lezioni 5,6 -- 2/3/2001

Argomenti trattati [T1, Par. 3.5] [T4, Cap. 5]
- Tipi di dato primitivi: interi, reali, caratteri
- Booleani
- Tipi enumerati
- Conversione di tipo: automatica (coercion) ed esplicita (cast)
- Differenza fra espressioni ed istruzioni
- Tipo alias
- Passaggio e restituzione di un valore per riferimento (file alias.cpp)
- Puntatori
Cosa lo studente dovrebbe sapere dopo la lezione:
- Differenza tra alias e puntatore
- Quando (e come) usare alias
- Meccanismo di passaggio di parametro per riferimento e ritorno per riferimento
Esercizi proposti
- Scrivere funzione che modifica una data (giorno, mese ed anno) in input, assegnandole quella di n giorni dopo
- Ripassare le principali strutture di dati studiate nel corso di Fondamenti di Informatica I e loro rappresentazioni: vettori, matrici, liste, pile, code, insiemi, alberi binari [T3, Cap. 3]

Lezioni 7,8 -- 5/3/2001

Argomenti trattati [T1, Par. 3.5] [T4, Cap. 5]
- Array statici (mono e multidimensionali)
- Array dinamici (mono e multidimensionali)
- Passaggio di parametri vettore (file funzioni-vettore.cpp )
- Funzioni e procedure che manipolano array statici e dinamici, a una o più dimensioni (file matrici.cpp)
- Stringhe
Cosa lo studente dovrebbe sapere dopo la lezione:
- Quando (e come) usare un array statico o un array dinamico in C++
Esercizi proposti
- Scrivere un programma che legga una frase, conclusa da un punto, e determini se è una frase palindroma oppure no. Vanno scritte due versioni del programma:
  - la frase è lunga al massimo 100 lettere (soluzione: file palindromo.cpp)
  - la frase è lunga al massimo n lettere, dove n è un numero letto da tastiera prima della frase (soluzione: file palindromo.cpp)
- Tutti quelli di [T2, Cap. 1].

Lezioni 9,10 -- 6/3/2001

Argomenti trattati [T1, Par. 3.4, 3.6] [T3, Cap. 6]
- Tipi di dato composti, struct
- Record e puntatori
- Creazione e stampa ricorsive di una lista (file liste.cpp)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Quando (e come) usare un array statico, un array dinamico, o una lista in C++
Esercizi proposti
- Scrivere procedure (funzioni che restituiscono void) ricorsive per:
  - creare una lista con inserimento in testa (gestione a pila)
  - stampare il contenuto di una lista
  - effettuare l'inversione di una lista
  Scrivere un opportuno programma per verificare le procedure.
- Scrivere un'ulteriore versione del programma che legge una frase, conclusa da un punto, e determina se è una frase palindroma oppure no:
  - non si conosce a priori la lunghezza della frase
- Tutti quelli di [T2, Cap. 2].

Lezioni 11,12 -- 7/3/2001

Argomenti trattati [T1, Par. 3.4, 3.6]
- Alberi binari in C++
- Varie funzioni su alberi binari in C++ (visita, contare numero di foglie, calcolare la profondità, costruzione data la rappresentazione in forma parentetica letta da tastiera, etc.) (file albbin.cpp)
- Rappresentazione di alberi in C++
Cosa lo studente dovrebbe sapere dopo la lezione:
- Come si rappresentano alberi binari in C++
- Progettare semplici funzioni ricorsive per la manipolazione di alberi binari
Esercizi proposti
- Scrivere una funzione che accetta come parametri i puntatori alla radice di due alberi binari, e restituisce true se e solo se i due alberi sono uguali in maniera profonda, ritorna false, altrimenti (soluzione: funzione Uguali() del file albbin.cpp)
- Tutti quelli di [T2, Cap. 3] e [T2, Cap. 4].

Lezioni 13,14 -- 8/3/2001

Argomenti trattati [T1, Par. 3.4] [T4, Cap. 6]
- Regole di visibilità in C++ (singolo file) (file scope.cpp)
- Riassunto visibilità a livello di file (file scope2.cpp)
- Visibilità per programmi divisi in più file: include, extern, static, compilazione separata (file extern.cpp e extern2.cpp)
- Applicazione: gestione di un contatore: modulo che eroga il servizio (file cont.cpp) e modulo che usa il servizio (file usacont.cpp)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Regole per determinare la visibiltà in un solo file ed in più file
Esercizi proposti
- Tutti quelli di [T2, Cap. da 1 a 7].

Lezioni 15,16 -- 9/3/2001 --- Esercitazione di laboratorio

Argomenti trattati (dettagli nel file cosasifa.txt)
- Programmi elementari in Turbo C++
  - lettura di n numeri interi positivi da tastiera e calcolo del massimo (file printmax.cpp)
  - stampa di una piramide di numeri (file piramide.cpp)
  - calcolo del fattoriale (file fatt.cpp)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Scrivere e provare semplici programmi C++
Esercizi proposti
- Compilare e fare eseguire tutti i programmi visti fin'ora durante le lezioni, in particolare quelli che utilizzano strutture dinamiche e quelli divisi in più file

SECONDA PARTE

Torna all'indice delle lezioni

Lezioni 17,18 -- 12/3/2001 [Prof. Maurizio Lenzerini]

Argomenti trattati [T1, Cap. 4, par. 4.1 - 4.5] [T4, Cap. 8]
- Introduzione alle classi in C++
- File .h e file .cpp
- La dichiarazione di una classe
- Parte pubblica e parte privata
- Campi dato e campi funzione
- La nozione di oggetto di invocazione
- Costruttori
Cosa lo studente dovrebbe sapere dopo la lezione:
- Le prime nozioni sulle classi in C++

Lezioni 19,20 -- 13/3/2001 [Prof. Maurizio Lenzerini]

Argomenti trattati [T1, Cap. 4, par. 4.1 - 4.5] [T4, Cap. 8,9,10]
- Ancora su costruttori:
  - concetto di costruttore di copia
  - costruttore unario (convertitore di tipo)
  - costruttori e new
- Assegnazione e inizializzazione; differenze rispetto al costruttore; concetto di distruttore
- Oggetti anonimi
Cosa lo studente dovrebbe sapere dopo la lezione:
- Definire classi con costruttori
Esercizi proposti
- Compilare la classe tempo finora vista
- Classe per la rappresentazione di vettori nello spazio

Lezioni 21,22 -- 15/3/2001

Argomenti trattati [T1, Cap. 4, par. 4.7, 4.8, 4.9.2]
- Overloading di operatori; operatori forniti dal C++
- Overloading di operatori con funzioni esterne
Cosa lo studente dovrebbe sapere dopo la lezione:
- Definire classi con costruttori e operatori
- Quando e come usare operatori ridefiniti tramite funzioni esterne
Esercizi proposti
- Compilare la classe tempo finora vista

Lezioni 23,24 -- 16/3/2001

Argomenti trattati [T1, Cap. 4, par. 4.10 -- 4.12, 4.14 ]
- Campi static di tipo dato e funzione. Applicazione: una classe che rappresenta un intero e gestisce il numero di oggetti attivi (nel loro tempo di vita) istante per istante:
Cosa lo studente dovrebbe sapere dopo la lezione:
- Quando e come usare campi static
Esercizi proposti
- Modificare la classe tempo in maniera che gestisca istante per istante le informazioni relative al numero di oggetti che sono nel loro tempo di vita

Lezioni 25,26 -- 19/3/2001 [Prof. Maurizio Lenzerini]

Argomenti trattati [T1, Cap. 4, par. 4.15 -- 4.17, 4.19]
- Modularizzazione mediante classi: la classe telefonata e la classe bolletta.
Cosa lo studente dovrebbe sapere dopo la lezione:
- Come usare le direttive di isolamento
- Quando e come usare campi puntatore
Esercizi proposti
- Modificare la parte privata della classe tempo rappresentando i dati con tre campi interi, per ore, minuti e secondi. Verificare che la classe telefonata non deve essere modificata.

Lezioni 27,28 -- 20/3/2001 [Prof. Giuseppe De Giacomo]

Argomenti trattati [T1, Cap. 5, parr. 5.1--5.3]
- Introduzione all'ereditarietà
- Ridefinizione di funzioni e dati
Programmi ausiliari
- Programma che mostra la compatibilità fra classe base e classe derivata (file parametricompatibili.cpp)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Dichiarazione di classi derivate
- Parte protetta di una classe
- Tipi di derivazione

Esercizi proposti

Si consideri il seguente programma C++.

class B                       class A: *ALFA* B
{ private:                    { private:
    void f();                     void fa() {f();}
  protected:                    public:
    void g();                     void ha() {g();}
  public:                     };
    void h();
};

void main()
{ A x; B y;
  x.g();  x.h();  x.ha();  x.fa();
  y.ha();  y.g();  y.h();
}

Si analizzino i tre casi di: *ALFA* è uguale a public *ALFA* è uguale a protected *ALFA* è uguale a private e si indichino gli errori che il compilatore segnala in ognuno dei tre casi. (Soluzione)

Lezioni 29,30 -- 21/3/2001 --- Esercitazione di laboratorio

Argomenti trattati (dettagli nel file cosasifa.txt)
Progettazione di classi elementari
- Classe per la rappresentazione di vettori nello spazio (file vettori.h, vettori.cpp)
- Un file per il test della classe (file test.cpp)
- Un programma (modulo cliente) per la gestione di due vettori (file usovett.cpp)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Progettare e testare semplici classi in C++
Esercizi proposti
- Tutti quelli che non si riesce a finire in laboratorio

Lezioni 31,32 -- 22/3/2001

Argomenti trattati [T1, Cap. 4, par. 4.15 -- 4.17, 4.19, 4.22]
- Il problema dell'interferenza
- Overloading dell'assegnazione, del costruttore di copia
Cosa lo studente dovrebbe sapere dopo la lezione:
- Perché l'interferenza è un problema; cosa la causa; come si risolve
Esercizi proposti
- Compilare la classe bolletta finora vista

Lezioni 33,34 -- 23/3/2001

Argomenti trattati [T1, Cap. 4, par. 4.15 -- 4.17, 4.19, 4.22]
- Overloading del distruttore
- Template; classi generiche; la classe collezione
Cosa lo studente dovrebbe sapere dopo la lezione:
- Perché va recuperata la memoria tramite il distruttore
- Come si dichiarano classi generiche
Programmi ausiliari
- Classe intero per la rappresentazione di interi positivi di qualsiasi dimensione, con il sovraccarico dell'operatore '+':
  - file intero.h
  - file intero.cpp
  - file testint.cpp (programma di prova della classe)
  - file usoint.cpp (programma con menu a scelta multipla)
  - file somma.cpp (programma che somma tutti gli interi contenuti in un file)
- NOTA : un programma che illustra l'uso delle stringhe "di basso livello" (quelle del C) del C++ (file stringhe.cpp)
Esercizi proposti
- Migliorare la classe intero, aggiungendo gli operatori unari '++' (soluzione: file operator++.cpp) e '--' e gli operatori binari '-', '*', '/', '%'.
- Migliorare ulteriormente la classe intero, prevedendo la possibilità di rappresentare anche interi negativi.

Lezioni 35,36 -- 26/3/2001 --- Esercitazione di laboratorio

Argomenti trattati (dettagli nel file cosasifa.txt)
- Progettazione di classi con campi puntatore (file poli.h, poli.cpp)
- Un file per il test della classe (file testpoli.cpp)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Ridefinire costruttore di copia, distruttore, assegnazione
Esercizi proposti
- Tutti quelli che non si riesce a finire in laboratorio.

Lezioni 37,38 -- 27/3/2001 [Prof. Giuseppe De Giacomo]

Argomenti trattati [T1, Cap. 5, parr. 5.4, 5.7]
- Funzioni virtuali
- Classi base astratte
Programmi ulteriori
- Realizzazione di una gerarchia di classi in C++ e progettazione di una funzione cliente (file figure.cpp)
- Esercizio: realizzazione di una gerarchia di classi in C++:
  - schema concettuale
  - Soluzione
- esercizio d'esame del 1/07/1998: problema 4 (testo e soluzione)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Quando e come ridefinire una funzione in una classe derivata
- Quando e come usare le funzioni virtuali
Esercizi proposti
- Tutti quelli di [T1, Cap. 5]
- Problema 3 dell' appello d'esame del 5/7/1997 (testo e soluzione).

Lezioni 39,40 -- 29/3/2001

Argomenti trattati [T1, Capp. 1, 2, Parr. 9.1--9.2]
- Considerazioni generali sullo sviluppo dei programmi
- Ciclo di vita del software
- Qualità del software
- La modularizzazione: caratterizzazione, qualità.
Cosa lo studente dovrebbe sapere dopo la lezione:
- Differenza fra committente, progettista, utente e manutentore di un prodotto software
- Ciclo di sviluppo "a cascata"
- Qualità interne ed esterne del software
- Caratteristiche generali di un modulo.
- Saper riconoscere moduli di buona qualità.
Esercizi proposti
- (Cfr. esercizio 9.2 di [T1]) In questo direttorio si illustra una modularizzazione di scarsa qualità. Riprogettare i vari moduli per aumentarla ( soluzione).

Lezioni 41,42 -- 30/3/2001

Argomenti trattati [T1, Cap. 9, Parr. 9.2--9.3]
- La fase di progettazione: concettualizzazione e realizzazione
- La modularizzazione: tipi
- La modularizzazione in fase di concettualizzazione
- Specifica e realizzazione di un modulo funzionale
- Specifica e realizzazione di un modulo per singolo oggetto
Cosa lo studente dovrebbe sapere dopo la lezione:
- Differenza fra moduli funzionali, per singolo oggetto, e per tipo astratto.
- Come si specifica un modulo funzionale e per singolo oggetto
- Come si realizza in C++ un modulo funzionale e per singolo oggetto
Esercizi proposti
- Progettare un modulo concettuale PER SINGOLO OGGETTO per rappresentare e gestire un'area rettangolare 18 X 78 (di fatto si desidera modellare lo schermo di un terminale a caratteri 25 X 80, a cui vengono sottratte alcune righe e colonne per la visualizzazione di informazioni).
  Le operazioni che si intendono eseguire sono le seguenti:
  - metti un rettangolo, specificando le coordinate di due suoi vertici (basso sinistra ed alto destra);
  - togli un rettangolo, specificando le coordinate di due suoi vertici (basso sinistra ed alto destra);
  - stampa l'area, evidenziando le zone coperte da rettangoli;
  - cancella tutti i rettangoli presenti nell'intera area;
  - dato un punto dell'area, dire da quanti rettangoli è ricoperto.
- Realizzare il modulo in C++ ( soluzione)

Lezioni 43,44 -- 2/4/2001

Argomenti trattati [T1, Cap. 9, Parr. 9.4--9.6 + Cap. 10, Parr. 10.1--10.3]
- Schema concettuale di progetto
- Relazioni tra moduli
- Metodologia basata sulla modularizzazione.
- Introduzione alla specifica dei tipi astratti
- La specifica del tipo astratto Pila
- Funzioni in pseudo-C++: Svuota(Pila(Interi)) ===> Pila(Interi);
Cosa lo studente dovrebbe sapere dopo la lezione:
- Produrre uno schema concettuale per una semplice applicazione.
- Fornire la specifica di un tipo astrazione di valori
- Definizione di tipo astratto, sorta, e segnatura
Esercizi proposti
- Scrivere in pseudo-C++ la funzione:
  Concatena(Pila,Pila) ===> Pila.
  Esempio: Concatena(<1,2,3>,<4,5,6>) = <1,2,3,4,5,6>
  Soluzione
- La specifica del tipo astratto Coda

Lezioni 45,46 -- 3/4/2001

Argomenti trattati [T1, Cap. 10, Parr. 10.1--10.3]
- La specifica del tipo astratto Lista
- Funzione in pseudo-C++: Concatena(Lista,Lista) ===> Lista.
  Esempio: Concatena( (1 (2) 3),(4 (5 6)) ) = ( (1 (2) 3 4 (5 6)) )
  Soluzione
- Tipi come astrazione di entità: CassaCambio
Cosa lo studente dovrebbe sapere dopo la lezione:
- Differenza fra un tipo astrazione di valori e un tipo astrazione di entità
Esercizi proposti
- Studiare la specifica degli altri tipi astratti di [T1, Par. 10.2] (Coda, Array, Albero Binario, Albero, ListaSemplice, ...)
- Scrivere in pseudo-C++ le seguenti funzioni:
  - Inverti(Lista) ===> Lista.
    Esempio: Inverti( (1 (2) 3 4 (5 6)) ) = ((5 6) 4 3 (2) 1)
  - InvertiTutte(Lista) ===> Lista.
    Esempio: InvertiTutte( (1 (2) 3 4 (5 6)) )= ( ((6 5) 4 3 (2) 1) )
  - Speculare(Albero) ===> Albero.
    Esempio: Speculare =( (1(2(5()())(3()()))(4()())) ) = (1(4()())(2(3()())(5()())))

Lezioni 47,48 -- 4/4/2001

Argomenti trattati [T1, Cap. 12, Parr. 12.1-12.5]
- Generalità sulla realizzazione di tipi astratti mediante classi in C++
- Rappresentazione dei valori del tipo
- Generalità sulla scelta dello schema realizzativo
- Dalla segnatura all'interfaccia della classe
- Realizzazione del tipo astratto Insieme(Elem) secondo lo schema funzionale con condivisione (file Insieme-FC.h e Insieme-FC.cpp )
Programmi ausiliari:
Cosa lo studente dovrebbe sapere dopo la lezione:
- Come si usano: incapsulamento, information hiding, parametrizzazione e overloading di operatori per la realizzazione di tipi astratti

Lezioni 49,50 -- 6/4/2001 -- al laboratorio

Argomenti trattati (dettagli nel file cosasifa.txt)
- Realizzazione di un'applicazione con un modulo funzionale ed un modulo per tipo astratto (AlbBinario(Intero)), quest'ultimo secondo lo schema funzionale con condivisione
Cosa lo studente dovrebbe sapere dopo la lezione:
- Effettuare la realizzazione di un tipo astratto secondo lo schema funzionale con condivisione
Esercizi proposti
- Tutti quelli che non si riesce a finire in laboratorio.

Lezioni 51,52 -- 9/4/2001

Argomenti trattati [T1, Cap. 12, Parr. 12.5, 12.6.1]
- Approfondimenti sulla realizzazione del tipo astratto Insieme(Elem) secondo lo schema funzionale con condivisione
- Cenni all'efficienza della rappresentazione (spazio e tempo)
- Realizzazione di moduli clienti: la funzione Somma(Insieme(Elem)) ==> Elem
Cosa lo studente dovrebbe sapere dopo la lezione:
- Saper dichiarare una funzione C++ a partire dalla segnatura della corrispondente funzione del tipo astratto
- Comprendere i meccanismi per evitare side-effect nell'ambito delle realizzazioni con condivisione di memoria
- Vantaggi e svantaggi principali dello schema realizzativo funzionale con condivisione

Lezioni 53,54 -- 10/4/2001

Argomenti trattati [T1, Cap. 12, Parr. 12.6.2, 12.6.3, 12.6.4]
- Realizzazione del tipo astratto Insieme(Elem) secondo lo schema funzionale senza condivisione. Vantaggi e svantaggi
- Realizzazione del tipo astratto Insieme(Elem) secondo lo schema con side-effect senza condivisione
  - dichiarazione e definizione del costruttore di copia e di "=" come funzioni pubbliche
  - dichiarazione del costruttore di copia e di "=" nella parte privata (senza definizione)
- Realizzazione di moduli clienti: la funzione Somma(Insieme(Elem)) ==> Elem
- Realizzazione del tipo astratto Insieme(Elem) secondo lo schema con side-effect e condivisione
Cosa lo studente dovrebbe sapere dopo la lezione:
- Comprendere i meccanismi per evitare interferenza nell'ambito delle realizzazioni viste
Esercizi proposti
- Realizzazione in C++ delle funzioni
  - Unione(Insieme(Elem),Insieme(Elem)) ===> Insieme(Elem)
  - Intersezione(Insieme(Elem),Insieme(Elem)) ===> Insieme(Elem)
  - Differenza(Insieme(Elem),Insieme(Elem)) ===> Insieme(Elem)
  usando le realizzazioni del tipo astratto Insieme(Elem) secondo i quattro diversi schemi visti
- Progettare l'interfaccia pubblica delle classi che realizzano i tipi astratti: Pila, Lista, Albero, AlberoBinario, secondo gli schemi realizzativi funzionale/condivisione e side-effect/senza condivisione
- Scrivere in C++ le funzioni (precedentemente specificate)
  - Concatena(Pila,Pila) ===> Pila.
  - Concatena(Lista,Lista) ===> Lista.
  - Inverti(Lista) ===> Lista.
  - InvertiTutte(Lista) ===> Lista.
  - Speculare(Albero) ===> Albero.
  usando l'opportuna interfaccia pubblica dell'esercizio precedente. Scrivere le funzioni per entrambi gli schemi realizzativi.

Lezioni 55,56 -- 11/4/2001

Argomenti trattati [T1, Cap. 12, Parr. 12.6.4, 12.7]
- Riassunto della metodologia di realizzazione di tipi astrazione di valori e di scelta dello schema realizzativo.
- Realizzazione dei tipi astrazione di entità
  - Tipo astratto CassaCambio (file CassaCambio.h e CassaCambio.cpp )
  - Tipo astratto Deposito (file deposito.h e deposito.cpp )
Cosa lo studente dovrebbe sapere dopo la lezione:
- Comprendere i meccanismi per evitare interferenza nell'ambito delle realizzazioni con side-effect senza condivisione di memoria
- Tecniche fondamentali per la realizzazione di tipi astrazione di entità
Esercizi proposti
- Capitoli 8 e 9 di [T2]

************** INTERRUZIONE DIDATTICA PER VACANZE PASQUALI *************

Lezioni 57,58 -- 18/4/2001

Argomenti trattati [T1, Cap. 12, Parr. 12.7, 12.8]
- Realizzazione delle relazioni has-a e has-many.
- Sharing
Cosa lo studente dovrebbe sapere dopo la lezione:
- Differenze fra sharing e condivisione di memoria. Differenze fra aggiornamento e interferenza.
- Vantaggi dello sharing. Quando è obbligatorio usare lo sharing.
Esercizi proposti
- Realizzazione del tipo astratto Persona (esempio 12.8.1 di [T1])

Lezioni 59,60 -- 19/4/2001

Argomenti trattati [T1, Cap. 5, par. 5.8, Cap. 13, parr. 13.1, 13.2]
- Uso dell'ereditarietà nella realizzazione di tipi astratti:
  - generalità
  - realizzazione della relazione is-a
Programmi ausiliari: Realizzazione di una gerarchia di classi in C++ (docenti universitari):
- specifica
- realizzazione
Esercizi proposti:
- Specifica del tipo astratto Studente e dei suoi sottotipi. (Specifica dei tipi)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Come si realizza la relazione is-a in C++

Lezioni 61,62 -- 20/4/2001 -- al laboratorio

Argomenti trattati (dettagli nel file cosasifa.txt)
- Realizzazione di un tipo astrazione di entità (Disco)
- Realizzazione della relazione has-many fra il tipo astratto Disco e il tipo astratto File
- Uso della classe Disco realizzata da parte di un modulo cliente
Cosa lo studente dovrebbe sapere dopo la lezione:
- Realizzare un tipo astrazione di entità tramite un modulo C++
- Realizzare una relazione has-many fra tipi astratti
- Usare il modulo progettato mediante una funzione cliente
Esercizi proposti
- Tutti quelli che non si riesce a finire in laboratorio.

Lezioni 63,64 -- 23/4/2001

Argomenti trattati [T1, Cap. 13, parr. 13.3]
- Uso dell'ereditarietà nella realizzazione di tipi astratti.
  - Raffinamento della rappresentazione.
  - Tipo astratto Grafo e sua realizzazione con una classe base atratta e una sottoclasse ( file sorgente)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Realizzare moduli clienti per la classe Grafo che siano indipendenti dalla rappresentazione scelta
Esercizi proposti
- Scrivere una funzione C++ che costruisca la lista dei nodi pozzo di un grafo ( soluzione )
- Scrivere una funzione C++ che costruisca l'insieme dei nodi pozzo (dei nodi sorgente) di un grafo
- Scrivere una funzione C++ che calcoli il numero massimo di archi uscenti in un nodo ( soluzione)

Lezioni 65,66 -- 24/4/2001

Argomenti trattati [T1, Cap. 13, 13.4, 13.5]
- Uso dell'ereditarietà nella realizzazione di tipi astratti
  - classe base come supporto per la rappresentazione (delegation)
  - classe base Vettore e classe derivata Pila ( file sorgente )
  - altri usi dell'ereditarietà
Cosa lo studente dovrebbe sapere dopo la lezione:
- tutti i metodi principali di uso dell'ereditarietà per la realizzazione di tipi astratti
- quando usare derivazione pubblica, protetta o privata
- strutturare i campi di una classe base nelle parti pubblica, protetta e privata
Esercizi proposti
- Tutti quelli di [T1, Cap. 13]
- [T1, Cap. 14]
- [T2, Cap. 13-17]
- Tutti quelli dati agli esami, nella prima prova scritta (parte su orientazione agli oggetti)

Lezioni 67,68 -- 26/4/2001

Argomenti trattati [D, Cap. 2]
- Introduzione a Java
- Il primo programma in Java: Ciao.java
- Aspetti fondamentali del linguaggio:
  - tipi di dato di base, costruttori di tipo,
  - allocazione della memoria,
  - meccanismi di comunicazione fra unità di programma
Cosa lo studente dovrebbe sapere dopo la lezione:
- Stuttura di un programma Java
- Compilazione ed esecuzione di un programma Java
- Differenze fondamentali fra Java e C++ nell'allocazione della memoria e nella comunicazione fra unità di programma

Lezioni 69,70 -- 27/4/2001

Argomenti trattati [D, Cap. 2]
- assenza dei template in Java; simulazione della genericità mediante derivazione da Object; limitazioni di questa tecnica
- allocazione statica e dinamica in Java; garbage collection automatica; assenza del distruttore
- classi in Java:
  - campi di una classe
  - livello di accesso di un campo
  - qualificatori di un campo (static, final, abstract)
  - class, abstract class e interface
- simulazione dell'ereditarietà multipla in Java
Cosa lo studente dovrebbe sapere dopo la lezione:
- come si simula la genericità in Java
- differenza fra class, abstract class e interface
- come si simula l'ereditarietà multipla in Java

Lezioni 71,72 -- 30/4/2001

Argomenti trattati [D, Cap. 2]
- Costruttori in Java
- La classe Object e le sue funzioni speciali: clone(), equals() e toString()
- La classe Class ed il suo uso per la simulazione della genericità in Java
Cosa lo studente dovrebbe sapere dopo la lezione:
- Come si simula la genericità in Java
- Quali sono le funzioni speciali di una classe Java e come si realizzano

Lezioni 73,74 -- 2/5/2001

Argomenti trattati [D, Cap. 2, Cap. 3]
- Principali regole per la visibilità
- Package e classpath
- Realizzazione modulo funzionale gestione vettori di interi Vettori.java
  - creazione
  - lettura da tastiera
  - calcolo media valori
- Realizzazione modulo funzionale gestione liste di interi Liste.java
  - creazione/lettura da tastiera
  - stampa
  - inversione
Cosa lo studente dovrebbe sapere dopo la lezione:
- Metodologia per lo scambio di informazioni fra moduli Java

Lezioni 75,76 -- 3/5/2001

Argomenti trattati [D, Cap. 2]
- Realizzazione di classi in Java: classe Tempo Tempo.java
- Classe cliente: ProvaTempo.java
- Derivazione fra classi in Java: classe DataTempo DataTempo.java
- Classe cliente: ProvaDataTempo.java
- Gestione di eccezioni in Java
- Input da tastiera in Java: calcolo del fattoriale:
  - senza input
  - input da linea di comando
  - input da tastiera, senza gestione eccezioni
  - input da tastiera, con gestione eccezioni
  - Modulo gestione input da tastiera InOut.java
Cosa lo studente dovrebbe sapere dopo la lezione:
- Gestione delle eccezioni tramite blocco try-catch
- Come si realizzano le funzioni speciali di una classe Java
Esercizi proposti
- Tutti quelli su Java assegnati durante le prove d'esame dell'ultimo anno accademico (di molti è riportata la soluzione)

Lezioni 77,78 -- 4/5/2001 -- al laboratorio

Argomenti trattati (dettagli nel file cosasifa.txt)
- Applicazioni distribuite in Java
  - Appunti della lezione (formato PDF, file slides.pdf)
  - Codice sorgente dei file Java usati (lato client e lato server)
Cosa lo studente dovrebbe sapere dopo la lezione:
- Nozioni fondamentali sulle applicazioni distribuite e su Remote Method Invocation (RMI)
- Trasformare una classe Java in una classe adatta a fungere da server
Esercizi proposti
- Tutti quelli che non si riesce a finire in laboratorio.

Lezioni 79,80 -- 7/5/2001

Argomenti trattati [D, Cap. 3]
- Metodologia realizzazione tipi astratti in Java:
  - realizzazione di moduli funzionali
  - realizzazione di moduli per tipo astratto (astrazione di valori ed astrazione di entità)
  - realizzazione di relazioni has-a, has-many, is-a
- Esercizio: realizzazione tipo astratto Insieme
  - Schema realizzativo funzionale con condivisione: InsiemeFC.java
  - Modulo cliente: ProvaInsiemeFC.java
  - Schema realizzativo side-effect senza condivisione: InsiemeSS.java
  - Modulo cliente: ProvaInsiemeSS.java
- Esercizio: realizzazione del tipo astratto Persona:
- Esercizio: realizzazione di una gerarchia di classi in Java:
  - schema concettuale
  - Soluzione
Cosa lo studente dovrebbe sapere dopo la lezione:
- Come si realizza un tipo astratto in Java
Esercizi proposti
- Realizzare in Java almeno un tipo astratto fra quelli visti a lezione

TERZA PARTE

Torna all'indice delle lezioni

Lezioni 81,82 -- 8/5/2001

Argomenti trattati [T1, parr. 15.1-15.2]
- Introduzione alle tecniche algoritmiche
- Specifica di un problema
Cosa lo studente dovrebbe sapere dopo la lezione:
- Classificazione dei problemi (ricerca, decisione, ottimizzazione)
Esercizi proposti
- Dare la specifica dei seguenti problemi: partizionamento, ordinamento di un vettore, minimizzazione degli incroci in un grafo bipartito.

Lezioni 83,84 -- 9/5/2001

Argomenti trattati [T1, par. 15.3]
- Introduzione allo spazio di ricerca
- Vari spazi di ricerca per il problema delle N regine
- Spazio di ricerca per il problema della bisaccia
Cosa lo studente dovrebbe sapere dopo la lezione:
- Differenza fra spazio delle soluzioni e spazio di ricerca
- Scegliere uno spazio di ricerca a partire dalla specifica di un problema
Esercizi proposti
- Determinare spazi di ricerca per i seguenti problemi: partizionamento, ordinamento di un vettore, minimizzazione degli incroci in un grafo bipartito.
- Tutti quelli di [T1, cap. 15]

Lezioni 85,86 -- 10/5/2001

Argomenti trattati [T1, parr. 16.1,16.2,16.4]
- Enumerazione per problemi di ricerca: schema realizzativo
- Enumerazione per problemi di ottimizzazione: schema realizzativo
Cosa lo studente dovrebbe sapere dopo la lezione:
- Usare l'architettura generale per la soluzione di un problema con la tecnica enumerativa
- Scrivere una procedura che genera tutte le permutazioni di ordine n

Lezioni 87,88 -- 11/5/2001

Argomenti trattati [T1, parr. 16.3,16.5]
- Enumerazione per problemi di ricerca: soluzione del problema delle N regine
- Discussione su spazio di ricerca
Cosa lo studente dovrebbe sapere dopo la lezione:
- Sapere risolvere ogni problema di ricerca con la tecnica dell'enumerazione
Esercizi proposti: Risolvere con la tecnica dell'enumerazione tutti i seguenti problemi:
- Problema della soddisfacibilità [T1, esercizio 16.9]
- Problema della colorabilità di un grafo: testo in [T2, Cap. 18] (soluzione)

Lezioni 89,90 -- 15/5/2001

Argomenti trattati [T1, parr. 16.3,16.5]
- Enumerazione per problemi di ottimizzazione: soluzione del problema della bisaccia
- Discussione su spazio di ricerca
Cosa lo studente dovrebbe sapere dopo la lezione:
- Sapere risolvere ogni problema (di ricerca o di ottimizzazione) con la tecnica dell'enumerazione
Esercizi proposti: Risolvere con la tecnica dell'enumerazione tutti i seguenti problemi:
- Tutti quelli di [T1, Cap. 16]
- Tutti quelli di [T1, Parte V]
- Tutti quelli di [T2, Parte IV]

Lezioni 91,92 -- 16/5/2001

Argomenti trattati [T1, parr. 17.1-17.3]
- Backtracking per problemi di ricerca: schema realizzativo
- Backtracking per problemi di ricerca: soluzione del problema delle N regine
Cosa lo studente dovrebbe sapere dopo la lezione:
- Sapere risolvere ogni problema di ricerca con la tecnica del backtracking
Esercizi proposti: Risolvere con la tecnica del backtracking tutti i problemi di r icerca fra i seguenti:
- Tutti quelli di [T1, Cap. 16]
- Tutti quelli di [T1, Parte V]
- Tutti quelli di [T2, Parte IV]

Lezioni 93,94 -- 17/5/2001

Argomenti trattati [T1, parr. 17.1-17.3]
- Backtracking per problemi di ottimizzazione: schema realizzativo
- Backtracking per problemi di ottimizzazione: il problema della bisaccia
Cosa lo studente dovrebbe sapere dopo la lezione:
- Sapere risolvere ogni problema di ottimizzazione con la tecnica del backtracking
Esercizi proposti: Risolvere con la tecnica del backtracking tutti i problemi di ottimizzazione fra i seguenti:
- Tutti quelli di [T1, Cap. 16]
- Tutti quelli di [T1, Parte V]
- Tutti quelli di [T2, Parte IV]

Lezioni 95,96 -- 18/5/2001

Argomenti trattati
- Esercitazione su alcuni compiti di esame
  - Problema 1, domanda 2 del compito del 98-07-01
  - Problema 1, domanda 2 del compito del 99-07-05
  - Problema 1, domanda 2 del compito del 99-02-16
- NOTA i testi dei compiti d'esame degli appelli degli ultimi anni accademici (molti dei quali con soluzione) si trovano quì.

Lezioni 97, 98 -- 21/5/2001

Argomenti trattati [T1, parr. 8.1-8.6]
- Complessità
Cosa lo studente dovrebbe sapere dopo la lezione:
- Modello di riferimento per il calcolo della complessità di un algoritmo
- Regole fondamentali per il calcolo della complessità di un algoritmo

Lezioni 99,100 -- 22/5/2001

Argomenti trattati [T1, parr. 8.7-8.8]
- Regole fondamentali per il calcolo della complessità di un algoritmo
- Complessità di un problema
Cosa lo studente dovrebbe sapere dopo la lezione:
- Valutare la complessità di un algoritmo
Esercizi proposti
- Problema 3 del compito d'esame del 17/7/97 ( Soluzione )
- NOTA: Molti esercizi d'esame negli appelli passati hanno riguardato la complessità. Alcune soluzioni possono essere trovate qui.
- NOTA: Molti esercizi di [T2] contengono approfondite analisi della complessità dei programmi proposti
- Tutti quelli di [T1, cap. 8]

Lezioni 101,102 -- 23/5/2001

Argomenti trattati
- Complessità delle funzioni di una classe
- Complessità rispetto allo spazio
- Esercitazione su alcuni compiti di esame

Lezioni 103,104 -- 24/5/2001

Argomenti trattati [T1, Cap. 18, def. 15.4.2]
- La tecnica golosa
Cosa lo studente dovrebbe sapere dopo la lezione:
- Quando e come affrontare un problema con la tecnica golosa
Esercizi proposti:
- Tutti quelli di [T1, Cap. 18]
- Scrivere programmi C++ che usano la tecnica golosa per i seguenti problemi:
  - codifica di costo minimo (specifica [T2, cap. 22], soluzione)
  - alberi annotati (specifica [T2, cap. 23], soluzione)

FINE DEL CORSO

Ultimo aggiornamento di questo file: Last modified: Wed May 23 14:23:40 2001

Torna all'indice delle lezioni del corso
Home page del Corso di Fondamenti di Informatica II del Corso di Laurea in Ingegneria Informatica dell'Università di Roma "La Sapienza"