Fondamenti di Informatica, anno accademico 2009-2010
(Statistica Gestionale, 9 crediti)
Docente: Paolo Franciosa

Introduzione al corso

Architettura di un sistema di elaborazione

Origini del linguaggio Java

Compilazione e interpretazione di un programma in Java: codice sorgente, codice intermedio (bytecode); il ciclo di compilazione/esecuzione di programmi in Java; la Java Virtual Machine

Esempi di semplici programmi Java

Un semplicissimo programma Java PrimoProgramma.java

Tipi primitivi: aritmetici, carattere, boolean

Dichiarazione di variabili

Istruzione di assegnazione

Uso di literal (costanti)

Operatori aritmetici

Semplici espressioni

• Stampa di tutti i multipli di 7 compresi tra 0 e 100
  • Versione semplice StampaMultipliDi7.java
  • Versione complicata e meno efficiente StampaMultipliDi7Bis.java
• Stampa della somma dei primi cento naturali StampaSommaNaturali.java

Descrizione dei pacchetti JRE (Java Runtime Environment) e SDK (Software Development Kit)

Editing di programmi Java con Blocco Note

Compilazione ed esecuzione da "Prompt dei comandi" usando gli strumenti javac e java del SDK

Assegnazioni, uso di semplici espressioni

Cenni sull'uso di cicli e istruzioni condizionali

• Uso di tipi primitivi TipiPrimitivi.java
• Esercitazione 1

Costruzione di espressioni complesse

Precedenza tra operatori

Conversioni implicite ed esplicite, operatore cast

Assegnazioni tra tipi disomogenei

Operatori relazionali:    >   >=   <    <=   ==   !=

Istruzione if() ... else ...

Istruzione if() ...

Istruzioni if nidificate

• Date tre variabili int, contenenti valori distinti a piacere, stamparli in ordine crescente. Il programma deve funzionare correttamente per qualsiasi terna di interi

Istruzione composta { ... } e ambito di visibilità delle variabili

Espressioni booleane complesse: operatori && || !

Operatori di preincremento e postincremento ++, predecremento e postdecremento --

Istruzioni di ciclo: l'istruzione while

Uso di variabili boolean per il controllo di cicli

Istruzione break;

Istruzioni di assegnazione con modifica += -= *= /= %=

• Ordina tre numeri: Ordina3.java
• Verifica se tre interi sono i lati di un triangolo e individua il tipo di triangolo: Triangolo.java
• Decidere se tre reali sono i lati di un triangolo rettangolo, acutangolo od ottusangolo
• Dato capitale iniziale e interesse annuo, calcolare il capitale dopo un anno e dopo 3 anni
• Date le coordinate di due punti trovare la loro distanza euclidea (usare il metodo Math.sqrt() per il calcolo della radice quadrata)

• Calcola il numero di anni necessari per raggiungere un dato importo a partire da un capitale iniziale e un tasso di interesse annuo dati CapitaleObiettivo.java
• Incremento di capitale con capitalizzazione degli interessi Capitale.java
• Verifica se un naturale è primo
  • versione semplice Primalita.java
  • versione migliorata PrimalitaEfficiente.java
  • altri miglioramenti proposti:
    • terminare il ciclo appena trovato un divisore
    • evitare la divisione per numeri pari maggiori di 2
    • scrivere un programma che combina tutti i miglioramenti elencati
• Stampa il numero di divisori di un naturale (si possono utilizzare alcune delle idee a proposito del test di primalità)

Input/output attraverso un oggetto della classe Scanner

Uso di cicli per l'esame di una sequenza di interi da tastiera

Esempi di semplici programmi con cicli e istruzioni di selezione

• Primalità (vedi lezione precedente)
• Stampa di un triangolo di asterischi di lato n (fornito in input) con vari orientamenti StampaTriangolo.java

  ****
  ***
  **
  *
  
  *
  **
  ***
  ****
  
     *
    **
   ***
  ****
  
  ****
   ***
    **
     *
  

• Stampa di un albero di natale di altezza n (fornito in input) AlberoDiNatale.java. Ad esempio, per n=6 bisogna visualizzare il seguente disegno:

        *
       ***
      *****
     *******
    *********
   ***********
        *
        *
  

Soluzione dell'esercizio proposto nella esercitazione precedente: stampa di un triangolo di asterischi di lato n con vari orientamenti StampaTriangolo.java

Istruzione di ciclo for, analogie con istruzione while

Istruzione di ciclo do ... while, differenze rispetto all'istruzione while

Sviluppo di algoritmi: approccio top-down

Algoritmo di bisezione per la soluzione di una equazione in una variabile, e sua implementazione BisezioneSemplice.java

• Stampa della tavola pitagorica n per n TavolaPitagorica.java, assicurando che che l'input (n) sia compreso nell'intervallo [1,18]

Metodi di input/output della classe JOptionPane

Generazione di numeri pseudocasuali con Math.random()

Esempi di programmi con cicli: verificare se una sequenza di numeri reali in input è crescente.

Soluzione degli esercizi proposti nella esercitazione del 19 ottobre 2009

• TavolaPitagoricaIncolonnata.java
• sequenza random: VerificaSequenzaRandomAlmenoUnMaggiore.java
• sequenza random: VerificaSequenzaTuttiMaggiori.java
• sequenza random: VerificaSequenzaCrescente.java
• sequenza random: ContaSequenzeMassimaliCrescenti.java
• sequenza random: MisuraMassimaSequenzaMassimaleCrescente.java

Esercizi sull'uso di cicli e istruzioni di selezione

• contare il numero di massimi locali in una sequenza di numeri random di lunghezza definita dall'utente
• generazione della sequenza dei numeri di Fibonacci

Introduzione agli array monodimensionali: dichiarazione, allocazione ed uso

Inizializzazione di array

La proprietà .length di array

Input e output di array

• Leggi da tastiera una sequenza di double, memorizzala in un array, stampa la somma degli elementi SommaArray.java
• Leggi da tastiera una sequenza di double, memorizzala in un array, crea un array che contiene una copia degli elementi del primo array CopiaArray.java
• Leggi da tastiera una sequenza di double, memorizzala in un array, crea un array che contiene una copia degli elementi del primo array, ma in ordine inverso CopiaOrdineInverso.java
• Leggi da tastiera una sequenza di int che rappresenta delle frequenze, memorizzala in un array, crea un array che contiene le frequenze cumulate e stampa, in due colonne, la sequenza delle frequenze (sulla sinistra) e la sequenza delle frequenze cumulate (sulla destra) Cumula.java

Data in input una sequenza di interi, che rappresentano frequenze, stampare:

• la frequenza massima e la frequenza minima;
• calcolare l'array delle frequenze relative e stamparlo;
• calcolare l'array delle frequenze relative cumulate e stamparlo;
• stampare in quale posizione si trovano la frequenza massima e la frequenza minima.

Variabili riferimento: il caso degli arrays

Assegnazione tra arrays

Arrays multidimensionali

Esempi di algoritmi su arrays

• Ricerca sequenziale in un array disordinato RicercaValore.java
• Ricerca sequenziale di più valori in un array disordinato RicercaRipetutaValore.java
• Leggi da tastiera una sequenza di interi (la lunghezza è data anch'essa da tastiera), memorizzala in un array, verifica se la sequenza è in ordine non decrescente VerificaOrdine.java
• Modificare il programma precedente per verificare se la sequenza è crescente, non decrescente, non crescente o decrescente
• Leggi da tastiera una sequenza di interi (la lunghezza è data anch'essa da tastiera), memorizzala in un array, inverti l'array, stampa l'array ottenuto. Il problema deve essere risolto SENZA USARE ALTRI ARRAYS
• Dato un array bidimensionale di int (preferibilmente inizializzato nel codice):
  • stamparlo in forma di tabella (questo punto è risolto in StampaMatrice.java)
  • stampare la somma di tutti gli elementi
  • costruire un array nel quale memorizzare la somma di ciascuna riga
  • trovare qual è la riga di somma massima (risolvere questo problema sia usando il risultato del punto precedente, sia senza utilizzare alcun altro array)
• Dato un array bidimensionale che rappresenta una matrice quadrata, trovare il massimo elemento della diagonale
• Dato un array di double, che rappresenta i valori di una funzione di due variabili calcolati sui punti di una griglia bidimensionale, individuare i punti in cui la funzione presenta un massimo locale (definiamo un punto di massimo locale come un punto interno alla griglia nel quale la funzione assume un valore strettamente maggiore di tutti gli otto punti adiacenti ad esso). I punti sul bordo della griglia non possono essere punti di massimo locale

Esercitazione su arrays multidimensionali

I metodi

Definizione e chiamata di metodi static

La signature di un metodo

I metodi void

Parametri formali e parametri attuali

Passaggio di parametri per valore

Passaggio di parametri array

• Esempio di metodi con o senza parametri o valore di ritorno Metodi.java
• Stampa i primi compresi tra 1 e un intero N fornito in input, utilizzando un metodo che verifica la primalità di un intero restituendo un boolean
• Scrivere un metodo che trova la radice cubica di un intero (la soluzione sarà un intero che approssima la soluzione esatta)
• Scrivere un metodo che trova la radice cubica di un double x, utilizzando un metodi di ricerca binaria. L'intervallo iniziale di ricerca sarà da 0 a x, il metodo si ferma appena viene raggiunta una approssimazione fissata a priori

Esercitazione su metodi su arrays

Esercitazione 6

Ecco un esempio di soluzione (da leggere solo dopo aver tentato a lungo di risolvere l'esercizio) Esercitazione 6 svolta

Precisazioni sul pasaggio di parametri riferimento parametri.pps.zip

L'algoritmo di ordinamento per selezione (selection sort)

Cenni alla complessità computazionale del selection sort

Calcolo del fattoriale

• SelectionSort.java
• Calcolo del fattoriale di un intero non negativo Fattoriale.java
• Utilizzando i metodi definiti dei listati precedenti:
  • complessità del selection sort: stampare una tabella nella quale vengono mostrato il tempo impiegato per ordinare array random di double di dimensione crescente (199, 1000, 10000, 100000). I tempi possono essere calcolati attraverso la differenza tra i valori restituiti dal metodo System.currentTimeMillis(), immediatamente prima e immediatamente dopo l'ordinamento. È utile definire un metodo che alloca e restituisce un array random, la cui dimensione viene passata come parametro, e modificare il metodo ordinaConSelectionSort in modo che invece di essere void restituisca il numero di millisecondi impiegati
  • Come al punto precedente, ordinando però con il metodo Arrays.sort() (importare java.util.Arrays).
  • verificare qual è il massimo intero di cui è possibile calcolare il fattoriale in una variabile di tipo long

Ricerca sequenziale su un array (non ordinato)

L'algoritmo di ricerca binaria su array ordinati

Analisi della complessità dell'algoritmo di ricerca binaria

• Ricerca binaria in array ordinato RicercaBinaria.java
• Scrivere un programma che:
  • genera un array di dimensione letta da tastiera
  • lo inizializza con interi random tra 0 e 1000000
  • lo ordina (usando un qualsiasi metodo di ordinamento)
  • chiede ripetutamente un intero da cercare nell'array e stampa ogni volta il numero di iterazioni eseguite dall'algoritmo di ricerca binaria per trovare l'elemento o per verificarne l'assenza
• Valutare la complessità dell'algoritmo di ricerca binaria nel caso in cui l'intervallo di ricerca non fosse diviso ogni volta a metà, ma in due porzioni di lunghezza rispettivamente un terzo e due terzi della lunghezza dell'intervallo di ricerca precedente. Riferirsi al caso più sfavorevole.

Esercitazione su:

• packages
• parametri del main
• Javadoc
• calcolo del numero di elementi distinti in un array

Eccezioni: eccezioni controllate e non controllate

Gestione delle eccezioni (costrutto try ... catch ... finally) e propagazione delle eccezioni (costrutto throws ...)

Posizionamento della gestione delle eccezioni

L'algoritmo di Euclide per il calcolo del Massimo Comun Divisore (versione iterativa) MCDiterativo.java

Analisi di complessità dell'algoritmo MCD di Euclide.

Capitolo 12 e seguenti

Cormen, Leiserson, Rivest

Introduzione alla ricorsione.

Esempio di algoritmo ricorsivo per il calcolo del fattoriale Fattoriale.java

L'algoritmo di Euclide per il calcolo del Massimo Comun Divisore: versione ricorsiva MCDricorsivo.java

L'algoritmo di ordinamento per fusione (Merge Sort) MergeSort.java

Capitolo 12 e seguenti

Cormen, Leiserson, Rivest

Esercizi di programmazione

Introduzione alla programmazione a oggetti

Principio dell'information hiding

Da variabile-tipo a oggetto-classe

Variabili membro e metodi membro

Privatezza delle variabili membro

Definizione della classe Contatore

• descrizione dei requisiti
  • creazione dell'oggetto
  • incremento
  • restituzione del valore
• signature dei metodi membro
• variabili membro
• costruttori
• implementazione dei metodi membro

Definizione della classe Osservazioni

• descrizione dei requisiti
  • creazione dell'oggetto
  • aggiunta di un valore osservato
  • restituzione del numero di valori osservati
  • restituzione della media dei valori osservati

• realizzazione di una semplice classe Contatore (Contatore.java)
• programma che usa un oggetto di classe Contatore (Divisori.java)
• realizzazione della classe Osservazioni (Osservazioni.java)
• programma che usa un oggetto di classe Osservazioni (UsaOsservazioni.java)

• Scrivere una classe Java in grado di soddisfare le richieste del codice ProfittoStudente.java

Algoritmo di ordinamento a bolle (Bubble sort) e suoi miglioramenti

Esercitazione 8: accesso a file di testo. Nella stessa pagina è disponibile una soluzione alla esercitazione

Esempio di definizione ed uso di una classe

Sovraccarico del costruttore: uso del this()

L'oggetto di invocazione: uso del this nella disambiguazione dei riferimenti

Definizione ed invocazione di metodi static e metodi membro

Alcune classi predefinite con metodi static: Arrays, Math

Alcune classi predefinite per costruire oggetti (quindi con metodi non static): StringTokenizer, Scanner, Random

• schema della soluzione: EsamiSchema.java
• soluzione completa: Esami.java

Misure di complessità: le notazioni asintotiche O(), Ω(), Θ()

Esempi di classi di funzioni

Uso delle notazioni asintotiche per esprimere limitazioni superiori della complessità di algoritmi

Il paradigma divide et impera.

L'algoritmo Quick sort: QuickSort.java)

Versione animata dell'algoritmo Quick sort, che mostra il funzionamento per ciascuna chiamata ricorsiva: QuickSortAnimato.java

Algoritmo per il calcolo del k-esimo elemento: Selection.java

Versione animata dell'algoritmo Selection, che mostra il funzionamento per ciascuna chiamata ricorsiva: SelectionAnimato.java

Il paradigma divide et impera.

Analisi della complessità computazionale di algoritmi ricorsivi.

Soluzione di equazioni di ricorrenza attraverso il teorema principale (senza dimostrazione)

Esempi di applicazione del teorema principale:ricerca binaria, merge sort, algoritmo di Euclide per il MCD, quick sort nel caso migliore.

Analisi della complessità computazionale del merge sort senza utilizzare il teorema principale

Esercitazione 9: filtraggio righe da files di testo

Codifica dell'informazione:

• Generalità sulla notazione posizionale per numeri naturali, interpretazione di numeri espressi in base b
• conversione da base b a base 10 e da base 10 a base b
• rappresentazione di numeri interi in modulo e segno
• rappresentazione di numeri interi in complemento a due
• Codifica ottale ed esadecimale, conversione da e verso la base 2
• codifica di caratteri: ASCII, ASCII esteso, Unicode, codifica delle interruzioni di linea

CodificaPosizionale.java

Definizione di sottoclassi, ... extends ....
Chiamata del costruttore della superclasse super(...) e chiamata di metodi della superclasse super.nomeMetodo(...)

Ereditarietà di campi e metodi. Specializzazione di metodi per la sottoclasse attraverso la loro riscrittura (overriding).
La classe Object.

Il metodo toString() e sua ridefinizione (overriding). I metodi clone() e equals(Object)

Uso di classi geometriche dell'ambiente Java: Esercitazione 10

Esercizi di programmazione