Corso di: Programmazione 1
Laurea in Informatica
Anno accademico: 2003-2004
Docente: Barbara DEMO
INDICE
Calendario delle lezioni
Lezione 1 - Giovedi' 2/10 . Obiettivi del corso: introdurre alla programmazione pensando
alle proprieta' di efficienza e correttezza dei programmi
Esempio del calcolo con una calcolatrice
della somma degli interi da 1 ad n con la formula di Gauss e con una iterazione per
sommare 1+2+.. +i +... +n. Stima del numero di operazioni.
Struttura fondamentale di un calcolatore.
Riferimenti: Capitolo 1 del libro di testo.
Lezione 2 - Lunedi' 6/10 : Codice macchina, ling. assembler, ling. di alto livello. Esempi.
Algoritmo e specifica in linguaggio formale.
Compilatore: analisi sintattica e traduzione. Un primo programma Java. Macchina virtuale java.
Errori sintattici ed errori in fase di esecuzione.
Riferimenti: Capitolo 1 del libro di testo e lucidi
Lezione 3 - Martedi' 7/10: Specifica in linguaggio Java degli algoritmi
di somma degli interi da 1 ad un n dato. Cenni ai tipi di dati: int e stringhe.
Introduzione dell'iterazione con l'istruzione for.
Specifica dell'invariante di ciclo
Riferimenti: Algoritmo di costo costante
e Algoritmo di costo proporzionale ad n o lineare in n
Lezione 4 - Giovedi' 9/10: Riscrittura della specifica degli algoritmi per
la somma degli interi da 1 ad un n dato in un programma con due diversi metodi ed il main
che li invoca.
Ricalcolato il numero di operazioni per i due metodi.
Riferimenti: metodi per la somma da 1 ad n
Lezione 5 - Lunedi' 13/10: Metodi: specifica ed invocazione. Parametri formali ed attuali.
Trovare il massimo di due numeri: introduzione dell'istruzione di condizione(if).
Introduzione della classe Console e Console.readInt
per la lettura di interi.
Riferimenti: capitolo 5
Lezione 6 - Martedi'14/10: Tipi di dati fondamentali: int, double; boolean.
Assegnazioni, conversioni, cast.
Riferimenti: capitolo 3 senza stringhe.
Lezione 7 - Giovedi'16/10: Trovare il massimo in una sequenza di interi: iterazione
con l'istruzione while. Specifica di asserzione iniziale, invariante di ciclo,
asserzione finale
Esercizio: Sommare una sequenza di interi letti da consolle.
Variare gli esercizi di somma e ricerca del massimo introducendo il calcolo della cardinalita' della
sequenza terminata da 0 e la restituzione della posizione nella sequenza della prima occorrenza
del massimo.
Specifica di Invariante di ciclo con osservazioni di confronto sulle asserzioni viste finora.
Riferimenti: paragrafo 6.1 e
Operazioni su di una sequenza
Lezione 8 - Lunedi' 20/10: array e loro allocazione in heap con new.
Modello della memoria con pila e heap. Valori e riferimenti ad oggetti.
Visibilita' delle variabili: variabili locali al metodo.
Esempi
riprendendo gli esercizi sulla sequenza di interi letti da console. Per esercizio
completare la riformulazione degli esercizi sulla sequenza al caso in cui si usa un array.
Riferimenti: Paragrafi 12.4 e 12.5 del testo.
Lezione 9 - Martedi'21/10: Metodo per la lettura di un array restituito a chi
lo invoca. Ricerca lineare di un intero in un array di interi non ordinato.
Esercizi: 1.trovare la posizione di un elemento in un array, altrimenti restituire -1;
2.trovare tutte le occorrenze di un elemento dato in un array e la loro posizione.
Ricordare di specificare: asserzione iniziale e asserzione finale per ogni metodo e
per ogni ciclo l'asserzione invariante valida ad ogni esecuzione del ciclo immediatamente prima
della prima istruzione del blocco iterazione.
Invariante di ciclo dell'esercizio 1.
Puntualizzazione su metodi e parametri attuali e formali.
Esempi su metodi che tornano booleani. Esercizio:
scrivere un metodo che trovi se un array di interi e` ordinato non decrescente,
se c'e` un elemento dato,
se c'e` almeno un elemento pari e simili.
Osservazioni sul tipo di dato riferimento ad array e tipi di dati fondamentali.
E' impossibile scambiare due interi con un metodo che abbia due interi come parametri formali.
Riferimenti: Testo: paragrafo 5.4 e capitolo 7 (senza pacchetti) e
classe ImpossibileScambia
Lezione 10 - Giovedi'23/10:
Schema generale di un metodo che opera su un array totalmente riempito.
Array parzialmente riempiti.
Inserimento di un elemento in un array ordinato conservando l'ordine con Invariante di ciclo.
Considerazioni sul numero di operazioni e su varianti dell'algoritmo.
Riferimento: Inserimento ordinato:
metodo inserisci
Lezione 11 - Lunedi' 27/10: Ordinamento per inserimento.
Stima del numero di operazioni dell'algoritmo.
Riferimenti: Testo: capitolo 16 e per il metodo di inserimento ordinato:
metodo ordinaIns
Lezione 12 - Giovedi' 30/10:
Disegniamo l'invariante di ciclo per alcuni algoritmi su array considerati nelle precedenti lezioni:
inserimento in array ordinato non completamente riempito.
Esercizio: compattazione di un array non ordinato totalmente riempito da cui si vogliono togliere
le occorrenze di un elemento dato. Verifica che un array sia l'inverso di un secondo array
entrambi totalmente riempiti.
Riferimenti: per l'invariante, materiale prof Giovannetti
parte 9, pdf
Lunedi' 3/11: ESONERO
Lezione 13 - Martedi' 4/11: La bandiera olandese.
Esercizio 1: In un array non ordinato eliminare e spostare in coda tutte le occorrenze
di un dato elemento x: il
numero di operazioni dell'algoritmo e' proporzionale alla lunghezza dell'array.
Esercizio 2: in un array non ordinato spostare gli elementi in modo tale che
tutti gli elementi dispari precedano gli elementi pari.
Riferimenti. Sulla bandiera olandese:
materiale prof Giovannetti
e per l'esercizio 1, metodi eliminaTutti e spostaInCoda in: codice.
Lezione 14 - Giovedi' 6/11:Ricerca binaria di un elemento in un array ordinato
e totalmente riempito.
Problema della fusione: dati due array a e b, rispettivamente di l_a ed l_b elementi, totalmente riempiti, con eventuali
ripetizioni e ordinati, scrivere un metodo FONDI che produca un terzo array c con tutti gli elementi in a e b,
mantenendo le ripetizioni eventuali cosi' da avere l_a + l_b elementi; c deve essere
totalmente riempito e ordinato. Il numero di operazioni dell'algoritmo deve essere proporzionale alla somma l_a + l_b.
Riferimenti. Testo: capitolo 16 paragrafo 6 e per l'operazione di fusione:
Codice
Lezione 15 - Lunedi' 10/11: Classi ed oggetti: introduzione;
variabili pubbliche, private, statiche
Modello della memoria: pila, heap, area delle classi o method area
Da fare individualmente: l'esempio sulla classe Rectangle
nel pacchetto java.awt del capitolo 2 del testo.
Riferimenti. Testo: capitolo 2 e capitolo 7 paragrafo 7.
Per il modello della memoria: materiale prof Giovannetti,
parte 11, pdf
Lezione 16 - Giovedi' 12/11:
Consideriamo un insieme memorizzato in un array totalmente riempito, ordinato e senza ripetizioni
(poiche' contiene i dati di un insieme).
Progettare e scrivere la specifica dei metodi che realizzano le OPERAZIONI INSIEMISTICHE: unione,
intersezione e differenza.
Riferimenti. Testo: capitolo 16 paragrafo 6 e per l'operazione di intersezione
metodo intersezione
Per il modello della memoria: materiale prof Giovannetti,
parte 11, pdf
Lezione 17 - Lunedi' 17/11: Su come i metodi possono ritornare all'ambiente chiamante dei risultati.
Esempio: classi Coppia (di interi) e ProvoCoppia dove un metodo che trova il min ed il massimo in un array
torna questi valori 1.in un oggetto Coppia poi 2. in un vettore di due interi: discussione.
Codice
Esercizio sui vettori: dati due array a e b totalm. riempiti, ordinati crescenti e senza valori ripetuti
costruire un terzo array c che sia l'unione di a e b, cioe' che contenga tutti i valori in a e b senza ripetizioni e
mantenendo l'ordinamento.
Riferimenti:
per l'operazione di unione metodo unione.
Lezione 18 - Martedi' 18/11: Osservazioni sulle operazioni insiemistiche su insiemi rappresentati in array
totalmente riempiti, ordinati e senza ripetizioni: i metodi restituiscono array totalmente riempiti
ordinati e senza ripetizioni
Considerazioni sul numero degli elementi dell'insieme risultato nei due casi.
Operazione differenza tra gli insiemi a e b. Calcolare la cardinalita' degli insiemi
unione, intersezione, differenza senza calcolare gli insiemi medesimi.
Riferimenti:
operazioni su insiemi.
Lezione 19 - Giovedi' 20/11:
Ordinamento di un array con l'algoritmo di selezione (del minimo). Discussione e codice
Riferimenti: Testo: capitolo 16 paragrafo 1.
Lunedi' 17/11: inaugurazione aa.
Lezione 20 - Martedi' 25/11: Stringhe
Esercizi: varie forme di compattazione di array parzialmente riempito
metodi per la compattazione.
Riferimenti: Testo: capitolo 3, paragrafi 5.2.3 e 10.7.1
Lezione 21 - Giovedi' 26/11:Esercizio. Senza usare la classe Math scrivere due metodi
espLento ed espVeloce che calcolano l'elevazione a potenza di x alla n
espLento: moltiplicando x per se stesso esponente volte oppure
espVeloce: applicando una strategia di calcolo che distingue se n e' pari o dispari come segue
se n e' pari allora esp(x,n) = esp(x*x, n/2)
se n e' dispari allora esp(x,n) = x* esp(x,n-1).
Completare le specifiche con asserzione iniziale,finale ed invariante di ciclo.
Riferimenti: Testo:paragrafi 7.5 e Argomenti avanzati 6.8.
Lezione 22 - Lunedi' 1/12: Dimensione del problema risolto da cui dipende il numero di
ripetizioni di una iterazione in un algoritmo: ricerca in array e ordinamento di array, Gauss costante
e proporzionale ad n, esponenziale veloce.
Tempi di esecuzione costanti, proporzionali ad n, quadratici, logaritmici.
Numeri casuali e java.util.Random.
Riferimenti: Testo: paragrafo 6.5.
Lezione 23 - Martedi' 2/12: Esercizi sul modello della memoria con pila
e heap dagli
esami degli anni precedenti.
Lezione 24 - Giovedi' 4/12: Esercizi dagli esami degli anni precedenti.
e
Modalita' di esame.
Elenco del materiale di laboratorio o relativo agli esami scritti che sto aggiornando:
per fine anno spero contenga soltanto materiale NON gia'
allegato al Calendario delle lezioni.
Altro materiale, link, suggerimenti
Curiosare nel materiale relativo al corso
Programmazione 1 B e a tutti i laboratori.
| 