martedì, 15 marzo 2011
Prof. P. Terrevoli. Presentazione del corso, obiettivi, materiale didattico e libri di testo. Struttura del calcolatore; macchina di Von Neumann: CPU, memoria, I/O; connessione a bus. Struttura della CPU: unità di controllo e ALU; registri aritmetici e di controllo. Struttura della memoria; locazioni di memoria, indirizzi, capacità di memoria; memoria come contenitore di dati e programma; fase di fetch ed execute del processore. Linguaggio macchina; esempio di programma in linguaggio macchina. Concetti di algoritmo, programma, processo. Cenni ai modelli di calcolo; esistenza di funzioni non calcolabili. Paradigmi imperativo e funzionale e a oggetti; gerarchie dei linguaggi di programmazione.

mercoledì, 16 marzo 2011
Prof. P. Terrevoli. Rappresentazione delle informazioni. Codifica. Alfabeto e stringhe su un alfabeto. Alfabeto binario e rappresentazione delle informazioni alfanumeriche: codice ASCII e UNICODE. Informazioni numeriche: sistemi di numerazione posizionali; definizione del valore di un numero. Aritmetica in altre basi: invarianza degli algoritmi di calcolo rispetto alla base. Esempi con base la base 5 e la base 2. Metodi per la trasformazione della rappresentazione di un numero dalla base b alla base 10 (metodo del polinomio) e viceversa (metodo delle divisioni successive). Rappresentazione dei numeri negativi; metodo del modulo e segno e suoi svantaggi. Rappresentazione con il complemento alla base; operazioni con numero finito di cifre e overflow. Interi di varia lunghezza: byte, int, short, int, long.

venerdì, 18 marzo 2011
Prof. F. Sarracco. Variabili come astrazione di locazioni di memoria. Dichiarazione e assegnazione di variabili. I tipi int, short, byte e long. Identificatori e letterali. Assegnazione di un valore ad una variabile. Rappresentazione grafica di una variabile. Primo esempio di programma Java: PrimoProgramma.java Compilazione ed esecuzione. I comandi javac e java Secondo esempio di programma Java: SecondoProgramma.java Evoluzione temporale della memoria: TerzoProgramma.java Uso di più variabili: PrimaDomanda.java Espressioni e regole di precedenza fra operatori.

martedì, 22 marzo 2011
Prof. P. Terrevoli. Esempi di operazioni in complemento a 2:situazioni di overflow. Rappresentazione IEEE754 dei numeri in virgola mobile: mantissa ed esponente; rappresentazione in eccesso 127. Non uniforme distribuzione dei numeri; underflow. Numeri normalizzati, non normalizzati, infinito e NaN. Scrittura di un programma Java; uso dell'editor multidocumento (Notepad++). Finestra del prompt dei comandi: compilazione di un file Java. Prodotto della compilazione (file .class). Esecuzione di un programma dalla finestra dei comandi. Variabili intere di lunghezza diversa. Assegnazione di byte a short e viceversa: type casting.

mercoledì, 23 marzo 2011
Prof. P. Terrevoli: esercitazione. Editing di un programma Java. Utilizzo di Notepad++ Finestra del prompt dei comandi. Esecuzione del comando di compilazione javac Interpretazione dei messaggi di errore Esecuzione di un programma: comando java Esercizi sui tipi numerici fondamentali. Promozioni di tipo; casting. Errori di approssimazione. Perdite di precisione nel casting. Overloading dell'operatore + Conversione automatica di valori numerici in stringhe. Costanti numeriche di varia lunghezza. Costanti ottali ed esadecimali. Divisione intera. Operatore resto.

giovedì, 24 marzo 2011
Prof. F. Sarracco. Rassegna dei tipi primitivi numerici in Java e gerarchia di casting Il tipo char e sua conversione da e verso intero Il tipo di dato boolean e letterali booleani Operatori booleani e operatori di confronto Espressioni booleane Istruzioni condizionali if e if ... else: EsempioIf.java e EsempioIfElse.java Blocco di codice e regole di indentazione Errore: punto e virgola dopo l'if: DomandaIf.java

venerdì, 25 marzo 2011
Prof. F. Sarracco. Il ciclo while. Esempio: BartCiclo.java Cicli definiti. Esempi: stampare tutti i numeri pari fino a 100. StampaPari1.java, StampaPari2.java Cicli indefiniti. Esempi: massimo divisore di un numero. MassimoDivisore1.java, MassimoDivisore2.java L'istruzione for. Esempio: MassimoDivisore2For.java Esempio: calcolo del massimo comun divisore con l'algoritmo di Euclide. McdEuclide.java Esercizi per casa: riscrivere il programma McdEuclide utilizzando l'istruzione for. E possibile diminuire ulteriormente il numero di iterazioni effettuate dal programma nel caso ad esempio dei valori 100'000 e 100'002?

martedì, 29 marzo 2011
Prof. P. Terrevoli. Operatori di pre-post incremento/decremento, di modifica. Conversione da stringa a intero e a double: metodi Integer.parseInt() e Double.parseDouble(). Lettura di valori da tastiera: classe Scanner, metodo nextInt(). Cluasola import. Struttura di selezione: esercizi proposti. Ciclo di lettura con valore sentinella. Ciclo di lettura con numero di valori predeterminato. Ciclo di lettura con uscita anticipata: istruzione break. Ciclo equivalente realizzato con variabile booleana. Struttura iterativa: esercizi proposti.

giovedì, 31 marzo 2011
Prof. F. Sarracco. Array come collezione indicizzata di dati; Dichiarazione, creazione e inizializzazione di array (l'istruzione new); Accesso agli elementi di un array; Errore nell'accesso a indici fuori limite: ArrayIndexOutOfBoundsException; Dimensione di un array: length; Esempio: stampare gli elementi di un array (StampaArray.java); Esempio: calcolare la media sugli elementi di un array (ArrayMedia.java); Dichiarazione di valori costanti con final; Esempio: calcolare il numero di valori che superano una determinata soglia (ArraySoglia.java); Esempio: invertire gli elementi di un array (InversioneArray1.java, InversioneArray2.java); Semantica dell'operazione di assegnazione fra array.

venerdì, 01 aprile 2011
Prof. F. Sarracco. Esercizi sulla manipolazione di array: InserimentoArrayTesta.java, InserimentoArrayCoda.java, ArrayPalindromo.java, CopiaPari.java. Esercizio per casa: scrivere un programma che, dato un array di interi, elimina da tale array tutti gli elementi pari. Revisione di alcuni esercizi dell'esercitazione del 30 Marzo.

martedì, 05 aprile 2011
Prof. P. Terrevoli. Strutture if nidificate e loro codifica. Esempi. ed esercizi proposti. Analisi di una sequenza di input: ricerca del massimo e minimo. Problema dell'inizializzazione delle variabili. Terminazione della sequenza: metodo della sentinella. Metodo hasNextInt() della classe Scanner. Struttura switch .. case e sua semantica. Uso dell'istruzione break per evitare la sequenzialità dei casi. Esempi Esercizio proposto: ricerca di un valore in un array non ordinato.

mercoledì, 06 aprile 2011
Prof. P. Terrevoli: esercitazione. Efficienza nell'esecuzione di un programma. Caso del calcolo dei numeri primi. Programma per il conteggio dei numeri primi. Struttura di un programma a menu, Uso della struttura switch nella realizzazione di un programma a menu. Metodi statici di una classe. Dichiarazione del metodo. Intestazione del metodo: nome parametri e tipo del valore di ritorno. Corpo del metodo. Richiamo di un metodo. Programma Menu01.java Esercizio proposto: ricerca di un valore in un array ordinato.

giovedì, 07 aprile 2011
Prof. F. Sarracco. Dinamica dell'invocazione di un metodo: passaggio dei parametri. Parametri formali e parametri attuali. Esempio: stampa dei valori di un array (StampaArray.java). Visibilità e tempo di vita delle variabili locali e dei parametri formali di un metodo: record di attivazione. Regola di visibilità degli identificatori. Esempio: modifica di un parametro di tipo int (ModificaIntero.java). Esepmio: calcolo del maggiore fra due mcd (MaxMcd.java. Passaggio di parametri per valore e parametri di tipo array.. Esempio: modifica di un parametro di tipo int[] (ModificaArray.java). Passaggio di parametri da riga di comando. Esempio: RigaDiComando.java. Istruzioni per il parsing di stringhe in tipi primitivi. Classi wrapper di tipi primitivi.

venerdì, 08 aprile 2011
Prof. F. Sarracco. Overloading di metodi ed invocazione di metodi overloaded.. Esempio: MaxOverloaded.java. Esempio: TestOverloading.java. Matrici e loro rappresentazione in Java. Inizializzazione di matrici. Esempio: metodo che indica se una matrice e' quadrata (MatriceQuadrata.java). Esempio: calcolo del numero di valori positivi nella matrice (MatricePositivi.java). Generazione di numeri casuali con Math.random(). Esercizi per casa:
  • Scrivere un metodo int matriceRandom(int m, int n, int x, int y) che generi e restituisca una matrice di dimensione m x n ed i cui elementi siano valori casuali compresi fra x e y.
  • Scrivere un metodo boolean matriceTriangolareSuperiore(int[][] m) che restituisca il valore true se la matrice passata come parametro e' una matrice quadrata triangolare superiore.
  • Scrivere un metodo double determinante(int[][] m) che calcoli il determinante della matrice passata come parametro.
  • Scrivere un metodo int[][] inversa(int[][] m) che restituisca l'inversa della matrice passata come parametro.

martedì, 12 aprile 2011
Prof. P. Terrevoli.
  • Soluzione di alcuni esercizi precedenti: data giorno successivo, intersezione rettangoli utilizzando array e metodi.
  • Utilizzo di un array per rappresentare una funzione in forma tabellare.
  • Programma InserimentoInUnArrayNonOrdinato01.java
    • Inserimento di un elemento in un array non ordinato: creazione di un nuovo array con copiatura degli elementi preesistenti.
    • Immagazzinamento di una sequenza letta da tastiera in un array.
    • Ricerca di un elemento in un array non ordinato: varie terminazioni del ciclo di ricerca.
    • Uso non strutturato dell'istruzione return.
  • Creazione di una classe per contenere una libreria di metodi statici: EserciziArray01.java
  • Richiamo di metodi statici di una classe da un'altra classe. Classe di test: InserimentoInUnArrayNonOrdinato02.java
  • Dichiarazione public. Default package.
  • Esercizi proposti:
    • Scrivere un metodo statico che restituisca un array di interi letti da tastiera.
    • Scrivere un metodo statico che, dato un array a restituisca le posizioni dell'elemento più piccolo e dell'elemento più grande contenuto in a.
    • Scrivere un metodo statico che, dato un array a di interi, non ordinato, e un intero x restituisca:
      • -1 se x non appartiene all'array
      • l'indice della componente avente valore uguale a x se x appartiene all'array.
      NB: se x compare più volte restituire l'indice di una qualsiasi occorrenza oppure restituire un array con gli indici delle occorrenze di x in a.
    • Ripetere l'esercizio precedente con un array ordinato
    • Scrivere un metodo statico che, dato un array a, ordinato in ordine crescente, e un intero x inserisca l'elemento x ordinatamente nell'array a.
    • Dato un array a e un intero x, eliminare tutte le occorrenze di x in a
    • Dato un array a, eliminare tutti i doppioni degli elementi di a
    • Dato un array a e un intero k, scrivere un metodo statico che elimini i primi k elementi di a.
    • Dato un array a e un intero k, scrivere un metodo statico, che ruoti gli elementi di a di k posizioni a destra.
    • Dato un array a di n interi, un intero k e un booleano d, scrivere un metodo statico, che ruoti gli elementi di a di k posizioni a destra se d = false, a sinistra se d = true.
    • Dati due array di interi a e b verificare se il secondo array compare nel primo (subarray)
    • Scrivere un metodo statico che dati due array a e b ordinati in ordine crescente, restituisca un array c contenente gli elementi di a e b anch'esso ordinato in ordine crescente.
    • Dato un polinomio in x rappresentato con un array di coefficienti, e il valore di x, calcolare il valore del polinomio utilizzando la regola di Horner.
    • Scrivere un metodo statico che dati due insiemi rappresentati con array, restituisca un terzo insieme risultante dall'operazione di unione.
    • Scrivere un metodo statico che dati due insiemi rappresentati con array, restituisca un terzo insieme risultante dall'operazione di intersezione.
    • Scrivere un metodo statico che dati due insiemi rappresentati con array, restituisca un terzo insieme risultante dall'operazione di differenza.

giovedì, 14 aprile 2011
Prof. P. Terrevoli. Soluzioni di alcuni esercizi proposti. Overloading di metodi: ininfluenza del tipo di ritorno nella distinzione tra metodi e sua motivazione. Metodo equals per le stringhe. Passaggio di argomenti sulla riga di comando: esempi applicativi. Passaggio di parametri per valore. Impossibilità di side-effect sulle variabili atomiche. Side-effect sugli array. Esempio della rotazione degli elementi di un array. Introduzione ai tipi di dato e alle classi.

venerdì, 15 aprile 2011
Prof. P. Terrevoli. Tipo di dati: insieme supporto e operazioni. La classe come strumento per realizzare un tipo di dati. Attributi e metodi. Creazioni di oggetti come istanze di una classe: operazione new. Costruttore di default di una classe. Inizializzazione degli attributi. Metodi di istanza. Accessibilità di un attributo: dichiarazione private. Metodi accessori per accedere allo stato di un oggetto. Metodi modificatori per modificare lo stato di un oggetto. Classi di test. Esempio del conto corrente bancario: varie versioni. Esercizio proposto: modificare la classe conto corrente in modo da non accettare più di N prelievi tra due depositi.

martedì, 19 aprile 2011
Prof. P. Terrevoli. Variabili di classe, di istanza, locali, di blocco, parametri. Ambito di visibilità di una variabile. Oscuramento delle variabile di istanza da parte di variabili locali e parametri. Parametro implicito this. Passaggio da una approccio imperativo ad un approccio ad oggetti alla soluzione di un problema. Esempio riguardante un punto del piano cartesiano: approccio statico e approccio ad oggetti. Costruttori di un oggetto. Overloading dei costruttori. Inizializzazione delle variabili: valori di default. Riferimento null. Documentazione ufficiale Java. Metodo toString() e conversione automatica in stringa. Classe Object e gerarchia di ereditarietà. Comportamenti predefiniti. Esempi: Esercizi proposti:
  • conto corrente con limite ai prelievi giornalieri e mensile: testo, programma di test e risultato atteso.
  • gestione di insiemi di interi con array riempito parzialmente: strategia del raddoppio e del dimezzamento della dimensione massima (testo).

giovedì, 28 aprile 2011
Prof. P. Terrevoli. Soluzione di esercizi proposti: gestione di insiemi con array parzialmente riempiti, conto corrente con limiti di prelievo. Packages: organizzazione di classi in packages, dichiarazione package. Esempi: esercizi.contoCorrente05wPack, esercizi.contoCorrente06, esercizi.ausilio. Ambito di visibilità protected. Richiamo di costruttori fra di loro: this() Effetti collaterali accettabili di un metodo su parametri espliciti. Clonazione di oggetti nel passaggio di parametri, per evitare effetti collaterali. Clonazione di oggetti nella restituzione di risultati per non rompere l'incapsulamento dei dati.

venerdì, 29 aprile 2011
Prof. P. Terrevoli. Variabili di classe e loro utilizzo e accesso dgli oggetti. Classi senza metodi modificatori. Classi immutabili. Libertà nell'utilizzo dei riferimenti a oggetti immutabili. Esempio: String, MyDate (versione immutabile). Classi ausiliarie non pubbliche definite nello stesso file. Tipi enumerativi: enum come caso particolare di classe. Classi definite in altre classi (cenno). Grafi UML per la rappresentazione delle classi e delle relazioni tra di esse. Ereditarietà tra classi. Clausola extends. Fattorizzazione degli attributi e dei metodi. Ridefinizione dei metodi e dei costruttori (Overriding). Modalità di accesso alla super classe nei metodi e nei costruttori: super. Dichiarazione protected: accesso ad un attributo da una sottoclasse anche se in altro package. Esempi proposti: Conto Corrente (versione 07), Fattoria.

martedì, 03 maggio 2011
Prof. P. Terrevoli. Metodi astratti senza corpo. Metodi astratti. Classi astratte. Dichiarazione abstract. Esempio della fattoria (ver. 4). Fattorizzazione dei metodi. Binding dinamico dei metodi: es. del conto bancario. Interfacce. Significato e dichiarazione interface. Classi che implementano una interfaccia. Corrispondente diagramma UML. Dichiarazione di una variabile avente tipo interface. Interfacce e polimorfismo. Esempio del DataSet.

mercoledì, 04 maggio 2011
Prof. P. Terrevoli: esercitazione. Estensione di una classe. Costruttori, richiamo super in un costruttore e in un metodo. Ridefinizione dei metodi toString(), equals, clone. Schema generico del metodo equals nel caso di una classe e di una sottoclasse. Schema generico del metodo clone nel caso di una classe e di una sottoclasse. Copia superficiale e copia in profondità. Clonazione degli attributi mutevoli. Testo dell'esercitazione.

giovedì, 05 maggio 2011
Prof. Sarracco. La ricorsione. Definizione di metodi ricorsivi. Definizione induttiva e implementazione ricorsiva del fattoriale. Confronto fra implementazione ricorsiva ed iterativa del fattoriale. Implementazione ricorsiva delle funzioni somma, prodotto ed elevamento a potenza. Dinamica dei record di attivazione nei metodi ricorsivi. Esempio: lunghezza di una stringa e numero di occorrenze di un carattere in una stringa. Esercizio per casa: implementare un metodo ricorsivo void stampaInv(String s) che stampi a video i caratteri di una stringa in ordine inverso. Esempio: stampa a video delle righe di un file (BufferedReader) in versione iterativa e ricorsiva, e stampa delle righe in ordine inverso. Esercizio per casa: implementare un metodo ricorsivo int conta(BufferedReader br) che restituisca il numero di righe del file (ovvero leggibili dal BufferedReader br). Esercizio per casa: implementare un metodo ricorsivo int condConta(BufferedReader br, char c) che restituisca il numero di righe del file che iniziano con il carattere specificato dal parametro c. Esercizio per casa: implementare un metodo ricorsivo int massimo(BufferedReader br) che restituisca il massimo fra i valori letti da un file di testo (si assuma che il file contenga solo valori interi, uno per ciascuna riga).

venerdì, 06 maggio 2011
Prof. Sarracco. Gestione della memoria nella JVM a run-time Zona del bytecode Java Heap e garbage collector Stack e struttura di un record di attivazione Esempio di esecuzione di programma in memoria, evoluzione dello heap e dello stack e analisi dell'output Numeri di fibonacci: dinamica dello stack nel caso di ricorsione multipla Soluzione dell'esercizio per casa: implementare un metodo ricorsivo void stampaInv(String s) che stampi a video i caratteri di una stringa in ordine inverso. Soluzione dell'esercizio per casa: : implementare un metodo ricorsivo int condConta(BufferedReader br, char c) che restituisca il numero di righe del file che iniziano con il carattere specificato dal parametro c (CondConta.java).

mercoledì, 11 maggio 2011
Prof. Sarracco. La gestione delle eccezioni.

giovedì, 12 maggio 2011
Prof. F. Sarracco. Costo computazionale di un programma. Il problema della misura del costo computazionale. Modello astratto di costo. Esempio di calcolo del costo del metodo di ricerca sequenziale. Caso migliore, caso medio e caso peggiore. Comportamento asintotico, notazione O-grande. Stima dei tempi di calcolo associati alle funzioni di costo.

venerdì, 13 maggio 2011
Prof. Sarracco. Problema della dimensione dell'input Operazioni dominanti, esempi Ricerca binaria Implementazione iterativa e ricorsiva della ricerca binaria Costo rispetto allo spazio Esercizio: individuare il costo rispetto al tempo e allo spazio delle implementazioni iterative e ricorsive della ricerca binaria e della ricerca sequenziale

martedì, 17 maggio 2011
Prof. Sarracco Il problema dell'ordinamento Algoritmo selection sort, analisi del costo computazionale Algoritmo bubble sort, analisi del costo computazionale Il metodo compareTo() dell'interfaccia Comparable

mercoledì, 18 maggio 2011
Prof. Terrevoli: esercitazione. Esercitazione su array ordinati: verifica ordinamento, ricerca binaria e sequenziale, selection sort e bubble sort. Versioni iterative e ricorsive. Generalizzazione con l'interfaccia Comparable. Testo dell'esercitazione.

venerdì, 20 maggio 2011
Prof. P. Terrevoli. Ancora sull'interfaccia Comparable. Utilizzo di un array di Comparable con valori primitivi: auoboxing delle classi wrapper Integer, Double ecc. Strutture collegate. Definizione ricorsiva di una classe. Campo informazione e campo riferimento al nodo successivo. Operazioni elementari: inserimento, cancellazione, ricerca, scansione, accesso al nodo k-esimo. Inserimento/cancellazione in testa, in coda, in posizione intermedia ecc. Realizzazione con side-effect: ListeWSE.zip. Metodo hashCode() per identificare i nodi. Esercizi proposti: inserimento/cancellazione in posizione k, inversione degli elementi di una lista, estrazione degli elementi pari, estrazione degli elementi di posto pari.

martedì, 24 maggio 2011
Prof. P. Terrevoli. Operazioni sulle liste; implementazione con side-effects. Versione iterativa delle operazioni. Soluzione degli esercizi proposti. Versione aggiornata di ListeWSE.zip. Implementazione funzionale delle operazioni sulle liste. Versione ricorsiva delle operazioni sulle liste. Condivisione dei nodi tra più liste condizioni per non avere side-effect. ListeF.zip.

giovedì, 26 maggio 2011
Prof. P. Terrevoli Ancora operazioni sulle liste (versioni ricorsive funzionali con condivisione di memoria). Inversione degli elementi di una lista Separazione di una lista in elementi di posto pari e dispari: esempio di ricorsione mutua. Inserimento ordinato in una lista ordinata. Ordinamento di una lista con l'insertion sort. Merge di due liste ordinate. Esercizio proposto: mergesort di una lista.

venerdì, 27 maggio 2011
Prof. F. Sarracco Gli alberi e loro usi in informatica Definizioni di radice, nodo padre, nodo figlio, nodi fratelli, nodi interni, nodi foglia, livello di un nodo, profondità di un albero, sottoalbero. Alberi binari, definizione induttiva, alberi binari completi Rappresentazione indicizzata di alberi binari (tramite array) Rappresentazione collegata di alberi binari: strutture collegate non lineari Visita in ampiezza e in profondità di un albero Visita simmetrica, in pre-ordine e in post-ordine di un albero binario: implementazioni tramite metodi ricorsivi Esercizio: implementare un metodo statico int profondita(NodoBin r) che restituisca la profondità dell'albero avente r come radice. Calcolarne la complessità computazionale nel caso peggiore. Esercizio: implementare un metodo statico boolean presente(NodoBin r, String x) che restituisca true se e solo se il campo info di almeno uno dei nodi dell'albero avente r come radice è uguale alla stringa x. Calcolarne la complessità computazionale nel caso peggiore. Esercizio: implementare un metodo statico void visitaAmpiezza(NodoBin r) che effettui la visita in ampiezza dell'albero avente r come radice. Calcolarne la complessità computazionale nel caso peggiore.

martedì, 31 maggio 2011
Prof. P. Terrevoli Strutture astratte di dati. Specifica funzionale. Dominio di interesse. Es. numeri naturali, algebra di Boole, liste parametriche. Rappresentazione concreta di un ADT mediante classi Java. Astrazione di valori semplici e collezione. Astrazione di entità. Implementazione con side-effect, senza condivisione di memoria. Implementazione funzionale con condivisione di memoria. Esempi: Applicazioni sugli alberi binari:
  • visita in profondità di un albero binario (versione iterativa con pila ausiliaria)
  • visita in ampiezza di un albero binario con l'ausilio di una coda.
Esercizi proposti:
  • implementazione di una coda con una lista circolare e un solo puntatore di accesso.
  • implementazione di una struttura per la gestione del minimo di un insieme (heap).

martedì, 07 giugno 2011
Prof. P. Terrevoli Introduzione al Collection framework di Java. Interfacce principali e loro gerarchia di ereditarietà. Contratto e firma dei metodi d'interfaccia. Collection e suoi metodi. Set e suoi metodi. List e suoi metodi. SortedSet e suoi metodi. Map e sui metodi. Iteratori: interfacce Iterator e ListIterator. Invalidazione di un iteratore. Principali classi del CF. ArrayList, LinkedList, TreeSet, HashSet. Interfaccia Comparator. Tabelle: chiave e valore. Hashmap e Treemap. Implementazione di una tavola hash. Problema delle collisioni. Risoluzione con le liste di trabocco (buckets).