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

Introduzione al corso

Concetto di problema e di algoritmo

Esempi di algoritmi

Assegnazioni, uso di semplici espressioni

Operatori aritmetici

Semplici espressioni

Precedenza tra operatori

Conversione implicita

Conversione esplicita (cast)

Assegnazioni tra tipi disomogenei

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

Cenno sull'uso di istruzioni condizionali

Esempi di semplici programmi Java

Correzione di errori sintattici e semantici

Esercizi su assegnazioni e istruzioni condizionali

Costruzione di espressioni complesse

Precedenza tra operatori

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

Istruzione if() ... else ...

Istruzione if() ...

Istruzioni if nidificate

• Date tre variabili double, contenenti valori distinti a piacere, che rappresentano i coefficienti di una equazione di secondo grado in una variabile, trovare le soluzioni (se reali) oppure stampare un messaggio (se complesse). Il programma deve funzionare correttamente per qualsiasi terna di interi.
  La radice quadrata si può calcolare con l'espressione Math.sqrt(....), dove i puntini rappresentano una qualsiasi espressione numerica con valore non negativo
• 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 && || !

Istruzioni di ciclo: l'istruzione while

• 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)
• Scoprire cosa fa il programma seguente: Ignoto.java
• Fare in modo che il programma Ignoto.java funzioni anche quando a e/o b contengono valori negativi
• Scrivere un programma che, dati due numeri naturali a e/o b, stampi il valore di ab, senza utilizzare il metodo Math.pow
• Scrivere un programma che stampi i primi 50 elementi della successione di Fibonacci

• Come modificare la variabile PATH di Windows per compilare ed eseguire programmi in Java
• Input/output attraverso un oggetto della classe Scanner
• Analisi di una sequenza di numeri da tastiera
• Successione di Fibonacci

Esercizi sull'uso di cicli e istruzioni condizionali

Uso di variabili boolean per il controllo di cicli

• 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à)

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

Uso di variabili boolean per il controllo di cicli

Istruzioni break; e continue;

Istruzione di ciclo for, analogie con istruzione while

Esempi di semplici programmi con cicli e istruzioni di selezione

• Stampa della tavola pitagorica n per n TavolaPitagorica.java, assumendo che che l'input (n) sia compreso nell'intervallo [1,18]
• Stampa di un quadrato di lato n (fornito in input) bordato di asterischi

    *******...**
    *          *
    *          *
    ............
    *          *
    *******...**
  
  

• Stampa di un quadrato di lato n (fornito in input) con due bordi di asterischi

    *********...**
    *********...**
    **          **
    ............
    **          **
    *********...**
    *********...**
  
  

• Stampa di un quadrato di lato n (fornito in input), con k (fornito in input) bordi di asterischi dove k < n/2 (ecco la soluzione QuadratoBordato.java)
• Stampa di un triangolo di asterischi di lato n (fornito in input) con vari orientamenti (l'utente sceglie l'orientamento voluto inserendo un intero tra 1 e 4) StampaTriangolo.java

    ****      *            *      ****
  1 ***     2 **      3   **    4  ***
    **        ***        ***        ** 	
    *         ****      ****         *
  
  

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

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

Metodi di input/output della classe JOptionPane

Generazione di numeri pseudocasuali con Math.random()

Esempi di programmi con cicli: verificare varie proprietà di una sequenza di numeri reali.

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

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

Esercizi su cicli

Soluzione degli esercizi proposti nella esercitazione del 19 Ottobre 2011

Introduzione agli array monodimensionali: dichiarazione, allocazione ed uso

Inizializzazione di array

La proprietà .length di array

Input e output di array

Esercizi di base su 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.

Ricerca sequenziale in un array non ordinato

Esercizi su array

Algoritmi di base su array:

• Ricerca sequenziale RicercaValore.java
• Ricerca sequenziale modificata RicercaValoreCompatto.java
• Soluzione ultima parte della esercitazione 4 Media.java
• Soluzione alternativa ultima parte della esercitazione 4 MediaOpt.java

Introduzione agli array bidimensionali: dichiarazione, allocazione ed uso

Inizializzazione di array bidimensionali

La proprietà .length di array bidimensionali

Leggi da tastiera le dimensioni di una matrice e suoi elementi, memorizzandoli in un array bidimensionale LeggiMatrice.java

Esercitazione su array bidimensionali: Esercitazione 5

Esercizi su array bidimensionali

• 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

I metodi

Definizione e chiamata di metodi static

Accesso a metodi di classi esterne, chiamata di metodi public static

Metodi void, metodi che restituiscono valori

Parametri formali e parametri attuali: il passaggio dei parametri

La signature di un metodo

overloading di metodi

• versione HTML parametri/index.html
• versione PowerPoint parametri.pps
• versione PDF parametri.pdf (far scorrere verso il basso le varie pagine)

• 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 e restituisce un boolean
• Scrivere un metodo che, a partire da un parametro array monodimensionale di int, lo stampa separando ciascun elemento con un carattere"\t"
• Scrivere un metodo che, a partire da un parametro array bidimensionale di int, lo stampa per righe
• Scrivere un metodo che, a partire da due array monodimensionali di double, restituisce true se ciascun elemento del primo è maggiore del corrisponente elemento del secondo, altrimenti restituisce false. Questa definizione ha senso solo se gli arrays hanno la stessa lunghezza, altrimenti il metodo deve restituire false

Esercitazione su metodi su arrays

Esercitazione6.java

Implementazione di un metodo per la ricerca sequenziale in un array disordinato

Ricerca sequenziale in un array ordinato

L'algoritmo di ricerca binaria su array ordinati

• Ricerca binaria in array ordinato RicercaBinaria.java

Introduzione alla complessità computazionale: concetto di risorsa

Analisi di complessità di semplici algoritmi: ricerca sequenziale, test di primalità

Analisi della complessità dell'algoritmo di ricerca binaria

Applicaizone del principio di bisezione alla soluzione numerica di una equazione definita da una funzione continua

• Soluzione numerica di una equazione attraverso ilmetodo di bisezione BisezioneSempliceMetodo.java

Assegnazione tra arrays

Passaggio di parametri array (parametri riferimento)

Metodi che restituiscono un riferimento a array

Esercitazione su metodi su arrays

Esercitazione7.html

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

Esempi di classi di funzioni

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

Capitolo 12 e seguenti

Cormen, Leiserson, Rivest, pagg. 21-26

L'algoritmo di ordinamento per selezione (selection sort)

Analisi della complessità computazionale del selection sort

• SelectionSort.java
• 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.
• Utilizzando i metodi definiti nei listati precedenti:
  • efficienza del selection sort: stampare una tabella nella quale vengono mostrato il tempo impiegato per ordinare array random di double di dimensione crescente (100, 200, 400, 800, 1600, 3200, 6400, ...).
    I tempi possono essere calcolati attraverso la differenza tra i valori restituiti dal metodo System.currentTimeMillis(), chiamandolo immediatamente prima e immediatamente dopo l'ordinamento; il metodo restituisce, sotto forma di long, il numero di millisecondi trascorsi da una origine convenzionale del tempo.
    È 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).

Esercizi di programmazione: Esercitazione 8

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

Analisi della complessità computazionale del bubble sort

Introduzione alla ricorsione.

Esempio di algoritmo ricorsivo per il calcolo del fattoriale

Il paradigma divide et impera.

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

Capitolo 12 e seguenti

Cormen, Leiserson, Rivest

Eccezioni: eccezioni controllate e non controllate

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

Posizionamento della gestione delle eccezioni

• CalcoloFrequenze.java
• SequenzeTestaCroce.java

L'algoritmo Quick sort: QuickSort.java

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

Complessità computazionale del quick sort nel caso peggiore

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

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

Complessità computazionale dell'algoritmo MCD di Euclide

• Introduzione al'uso di oggetti: la classe String e alcuni suoi metodi
• Uso della classe Scanner:
  • costruttori Scanner(String) e Scanner(File)
  • metodi hasNextInt(), hasNextDouble(), ...
  • metodi nextInt(), nextDouble(), nextLine(), ...
• classi wrapper: Integer, Double, ...

La classe BigInteger

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

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, algoritmo per il k-esimo elemento (selection).

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
  • azzeramento
• signature dei metodi membro
• variabili membro
• costruttori
• implementazione dei metodi membro

Equaz. di ricorrenza: Cormen, Leiserson, Rivest (pagine indicate)

Programmazione a oggetti: capitoli 8 e seguenti del testo Java

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

Esercitazione sulla definizione di classi

Estensione della classe Osservazioni in OsservazioniEsteso, come richiesto dal programma UsaOsservazioniEsteso.java

Soluzione: OsservazioniEsteso.java, con commenti Javadoc

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 2
• 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
• rappresentazione di caratteri: codifiche ASCII, ASCII esteso, Unicode

CodificaPosizionale.java

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

Definizione di sottoclassi: chiamata del costruttore della superclasse attraverso super

• definizione di una classe Persona.java
• esempio di uso della classe Persona: UsaPersona.java
• definizione di una sottoclasse di Persona: Studente.java
• esempio di uso della classe Studente: UsaStudente.java

Overriding: ridefinizione di metodi in sottoclassi

Il metodo toString() di Object e sua ridefinizione

Esercitazione sulla programmazione a oggetti