Diario delle lezioni (secondo semestre) A.A. 2011-2012 (Informatica + Automatica)
Per il testo di riferimento [T3] e le slides utilizzate nel corso, consultare la sezione
Materiale Didattico
Martedì 28/2 (Grisetti)
- Richiami sulla Gestione della memoria
- Cenni sui concetti base della programmazione:
- Astrazione
- Modellazione della realtà mediante strutture dati
- Introduzione sulle Strutture Collegate Lineari
Riferimenti: [T3] 13.1 - 13.4 e appunti della lezione.
Giovedì 1/3 (Grisetti)
- Strutture Collegate Lineari
- Definizione
- Operazioni elementari
Riferimenti: [T3] 13.5 - 13.16 e appunti della lezione.
Venerdì 2/3 (Grisetti)
- Operazioni sulle strutture collegate
- Richiami sulla ricorsione
- Implementazione ricorsiva di operazioni sulle SCL
Riferimenti: [T3] 13.17 - 13.23 e appunti della lezione.
Esercizi
1. Realizzare un metodo
NodoLista revert(
NodoLista p) che restituisce una nuova lista che ha gli elementi in ordine inverso alla lista puntata da p.
2. Realizzare un metodo
NodoLista soloPari(
NodoLista p) che data una lista di interi, restituisce una nuova lista che contiene solo gli elementi pari di p.
3. Realizzare un metodo ricorsivo
NodoLista sommaCoppie(
NodoLista p) che, data una lista di interi, restituisce una nuova lista in cui l'elemento in posizione i,
è ottenuto dalla somma degli elementi in posizione 2i e 2i+1 della lista p.
Martedì 6/3 (Grisetti)
- Soluzioni esercizi proposti
- Operazioni sulle liste
- Classe
SequenzaStringhe
- Cenni sulle eccezioni
Riferimenti: [T3] 13.17 - 13.29 e appunti della lezione.
Esercizi
1. Fornire una implementazione con side-effect della classe
SequenzaStringhe, specificata in 13.24.
2. (Facoltativo): Data la seguente definizione di una lista doppiamente collegata:
class
DoubleLinkedListNode{
}
dove prev e next sono riferimenti rispettivamente al predecessore ed al successore di un elemento, definire le seguenti operazioni:
- inserimento in testa, posizione k e coda
- rimozione in testa, posizione k e coda
Giovedì 8/3 (Patrizi)
- Implementazione funzionale della classe
SequenzaStringhe
- Condivisione di memoria
- Differenza tra sharing e interferenza
Riferimenti: [T3] 13.30 - 13.35, 13.37 e appunti della lezione.
Martedì 11/3 (Grisetti)
- Liste:
- Implementazione funzionale con ricorsione e condivisione di memoria della classe
SequenzaiF
- Ereditarieta' concetti di base e costruttori
Riferimenti:
- [T3] 13.38, 13.40 e appunti della lezione.
-
Slides Ereditarieta'∞ Pagine 1-16
Esercizio:
Realizzare la classe
ListaStringhe funzionale, senza condivisione.
Giovedì 12/3 (Grisetti)
- Ereditarieta' overloading, overriding
Riferimenti:
-
Slides Ereditarieta'∞ Pagine 16-30
Martedì 20/3 (Grisetti)descrizione
- Ereditarieta' final, classi e metodi astratti
Riferimenti:
- appunti della lezione
-
Slides Ereditarieta'∞ Pagine 30-40
-
Slides Classe Object∞ Pagine 1-23
Giovedì 21/3 (Grisetti)
- Ereditarieta' implementazione di Equals
- Packages, livelli di accesso, classpath
- Esercizi:
- Slide 26 delle slide su objects (cosa fa il programma)?
- Tutti gli esercizi nelle slides sui packages.
Riferimenti:
- appunti della lezione
-
Slides Classe Object∞ Pagine 24-30
-
Slides Package∞ , Tutte
Martedì 27/3 (Grisetti)
- Eccezioni
- Interfacce, introduzione
- Esercizio:
- Definire una eccezione non controllata
CompareExceptiion.
- Definire una interfaccia
Comparable che definisce il metodo
boolean compare(Object o).
boolean compare(Object o) ritorna true se l'oggetto e' dello stesso tipo di un altro e e' "minore", false altrimenti.
La definizione di minore e' demandata all'implementazione nella classe che implementa l'interfaccia.
Se gli oggetti sono di tipo diverso o non confrontabili, il metodo lancia un'eccezione di tipo "
CompareException".
- Definire una classe
Person con
name e
familyName come variabili di istanza che implementa l'interfaccia
Comparable
- Definire una classe
Matrix che implementa l'interfaccia
Comparable. Una matrice e' minore di un'altra se il vettore composto concatenando le sue righe "precede"
in ordine lessicografico, il vettore ottenuto concatenando le righe di un'altra matrice.
- scrivere un algoritmo di ordinamento che opera su oggetti che implementano l'interfaccia
Comparable.
Riferimenti:
- appunti della lezione
-
Slides Eccezioni∞. Tutte
-
SlidesInterfacce∞ , 1-4
Giovedì 29/3 (Grisetti)
- Interfacce
- Soluzione dell'esercizio in classe
Riferimenti:
- Slides Interfacce
SlidesInterfacce∞ (tutte)
- Soluzione in classe dell'
esercizio∞
Martedì 3/4 (Grisetti)
- Interfaccia Cloneable
- Copia profonda e superficiale
- Oggetti Immutabili e Mutabili
Riferimenti:
- Slides Cloneable
Cloneable∞ (tutte)
Esercizi:
- Data la gerarchia di classi sviluppata nell'
esercizio∞ della volta scorsa
- Rendere la classe "CompareException" una eccezione controllata e modificare il programma in modo che funzioni. Se si verifica una eccezione, il metodo di ordinamento termina e scrive su terminale il messaggio nell'eccezione.
- Implementare una funzione statica
merge(Object[] vdest, Object[] v1, Object[] v2) throws CompareException
che facendo side effect su vdest, restituisce un vettore ordinato che contiene sia gli elementi di v1 che di v2,
assumendo che v1 e v2 siano ordinati e che vdest sia di lunghezza v1.lenght+v2.lenght.
La funzione merge assume che gli oggetti implementino l'interfaccia Comparable
- implementare la funzione statica Object[] subArray(Object[] v, int min, int max) che restituisce il sottoarray di
v[min], v[min+1], ... ,v[max-1] in v.
- implementare in java la seguente funzione ricorsiva qui descritta in pseudo-codice
mergeSort(v) throws some exception{
if (v.lenght '
' 1) return;
if (v.lenght '
' 2)
in confronto qua sotto si fa sfruttando l'interfaccia Comparable
if (v[0]>v[1]) {Object ap=v[0]; v[0]=v[1]; v[1]=ap};
return;
int middle=v.length/2;
v1=subArray(v,0,middle);
mergeSort(v1);
v2=subArray(v,middle,v.length);
mergeSort(v2);
merge(v,v1,v2);
}
inserire dei contatori in posizioni opportune nelle funzioni di ordinamento (in merge e nel ciclo interno di simpleSort) e
verificare quante operazioni vengono compiute per vettori di dimensioni crescenti .
Se necessario rendere le funzioni membro di una classe (ContaOperazioni)
- data la classe
SequenzaStringhe illustrata nella Lezione di Martedi' 6/3,
- creare una classe SequenzaStringheBase, che e' poi specializzata in
SequenzaStringheLista e SequenzaStringheArray, che rappresentano la sequenza con side-effect.
- Implementare le interfacce Cloneable e Comparable per gli oggetti delle classi della gerarchia.
- Provare gli algoritmi di ordinamento su istanze di tali oggetti.
- implementare ina funzione ricorsiva,
NodoLista subsample(NoloLista p, int k) che data una lista di interi, crea una nuova lista che contiene un elemento ogni k. Usare metodi di appoggio.
- Esercizi di preparazione alla prova preliminare
- Compito e soluzioni
- Compito e soluzioni
- Compito e soluzioni
- Ricorsione
- implementare un metodo ricorsivo int trovaMinimo(int[] v) che restituisce l'indice del minimo di un vettore. Aggiungere se necessario variabili o metodi ausiliari
- implementare un metodo ricorsivo void merge(vDest, v1, v2) che fa in vdest gli elementi di v1 e v2, mantenendo l'ordine. v1 e v2 sono ordinati. Aggiungere se necessario variabili o metodi ausiliari.
Giovedì 12/4 (Grisetti)
- complementi sulla ricorsione (individuare variabili)
- operatore di postincremento (i
) e preincremento (i)
- Esercizi a lezione:
- soluzione merge ricorsivo
- convoluzione di matrici
- esercizi proposti (funzioneCampionata (da fare)
Riferimenti:
-
codice esercizi svolti e traccia di SampledFunction∞
Martedi' 17/4 (Grisetti)
- Cenni sulla complessita'
- Complessita' temporale e spaziale
- Notazione O()
- Ricerca
- Ordinamento
- Selection Sort
- Merge Sort
Riferimenti:
- [T3] 11.1-11.24, 12.1-12.3, 12.6-12.9
- appunti della lezione
- Esercizi:
- implementare l'algoritmo merge sort dallo pseudo-codice della lezione
- determinare la complessita' temporale e spaziale dei vari algoritmi proposti a lezione (ricerca sequenziale e binaria, selection sort e merge sort)
- implementare l'algoritmo merge sort che sfrutta l'interfaccia Comparable soluzione∞
Giovedì 19/4 (Patrizi)
- I tipi astratti di dato
- Definizione, uso e specifica
- Tipi di astrazione (valore o entita') e scelta dello schema realizzativo
- Astrazione di valori semplici: la classe NumeroComplesso
Riferimenti:
- [T3] 15.1-15.19
- appunti della lezione
Martedì 24/4 (Patrizi)
- I tipi astratti di dato
- Uguaglianza nelle classi astrazioni di valore ed entità
- Astrazione di valori collezione: la classe Insieme
- Realizzazione della classe Insieme con side-effect senza condivisione
Riferimenti:
- [T3] 15.20-15.27
- appunti della lezione
Giovedì 26/4 (Patrizi)
- I tipi astratti di dato
- Realizzazione della classe Insieme con schema funzionale con condivisione
- Astrazione di entità: la classe Studente
- Realizzazione della classe Studente con side-effect senza condivisione
Riferimenti:
- [T3] 15.27-15.29
- appunti della lezione
Giovedì 3/5 (Patrizi)
- Le classi generiche in Java
Riferimenti:
- Slides
Generics∞
- Appunti della lezione
- Esercizi:
- Esempio di realizzazione di struttura collegata con generics (Testo∞)
Martedì 8/5 (Patrizi)
- Il Java Collections Framework:
- Generalità
- La gerarchia delle interfacce di base
- Le interfacce Collection e Set
- Gli iteratori semplici (Iterator)
Riferimenti:
- Slides
JCF∞ (Fino a 18 inclusa)
- Appunti della lezione
Giovedì 10/5 (Patrizi)
- Il Java Collections Framework:
- Gli iteratori semplici (Iterator)
- L'interfaccia List
- Gli iteratori di lista (ListIterator)
- Esercizi
Riferimenti:
- Slides
JCF∞ (Fino a 34 inclusa)
- Appunti della lezione
Martedì 15/5 (Patrizi)
- Il Java Collections Framework:
- Le implementazioni delle interfacce Collection:
- L'interfaccia Map e la sua implementazione HashMap
- Realizzazione di tipi astratti mediante JCF:
- Realizzazione con side-effect senza condivisione del tipo astratto Coda
- Esercizi
Riferimenti:
- Slides
JCF∞ (Fino a 51 inclusa)
- Appunti della lezione
Giovedì 17/5 (Patrizi)
- Realizzazione di tipi astratti mediante JCF:
- Realizzazione funzionale (senza condivisione) del tipo astratto Coda
- Esercizi:
- Esercizio su matrici e JCF
Riferimenti:
- Slides
JCF∞
- Appunti della lezione
Martedì 22/5 (Patrizi)
- Svolgimento di esercizi estratti da appelli degli AA.AA. precedenti:
- Esercizio su vettori, ricorsione ed eccezioni
- Esercizio su SCL ed eccezioni
Riferimenti:
- Esercizi 1 e 2 delle slides
esercizi vari∞
Giovedì 24/5 (Patrizi)
- Svolgimento di esercizi estratti da appelli degli AA.AA. precedenti:
- Esercizio su file, JCF ed eccezioni
Riferimenti:
- Esercizio 3 delle slides
esercizi vari∞
Martedì 29/5 (Patrizi)
- Svolgimento di esercizi estratti da appelli degli AA.AA. precedenti:
- Esercizio su ereditarietà e classi astratte
Riferimenti:
- Esercizio 4 delle slides
esercizi vari∞