Fondamenti di Informatica, anno accademico 2013-2014
(Statistica Gestionale e mutuato da Statistica, Economia e Società, 9 crediti)
Docente: Paolo Franciosa

• Introduzione al corso
• Concetto di problema e di algoritmo
• Esempi di algoritmi
• Linguaggi di programmazione
  • dall'algoritmo al programma eseguibile
  • compilazione/interpretazione
  • errori sintattici/semantici
  • il caso del linguaggio 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

Errori sintattici e semantici

Il primo programma Java

I metodi System.out.print() e System.out.println()

Si invitano tutti gli studenti del corso a iscriversi al gruppo facebook del corso chiedendo amicizia a Paolo Giulio Franciosa. Sul gruppo verranno scambiate domande, chiarimenti, esercizi, soluzioni relative agli argomenti del corso

Tipi primitivi: interi, reali, carattere, boolean

Dichiarazione di variabili

Identificatori

Istruzione di assegnazione

Uso di literal (costanti)

Operatori aritmetici

Semplici espressioni

Assegnazioni, uso di semplici espressioni

Precedenza tra operatori

calcolo perimetro e area di un rettangolo CalcoloPerimetro.java

Uso di tipi primitivi TipiPrimitivi.java

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

Editing di programmi Java con Blocco Note e Notepad++

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

Esempi di semplici programmi Java

Correzione di errori sintattici e semantici

Esempi di overflow

Conversione implicita

Conversione esplicita (cast)

Assegnazioni tra tipi disomogenei

Precedenza tra operatori

Costruzione di espressioni complesse

Invocazione di metodi e uso del valore restituito

1. Date le coordinate di due punti trovare la loro distanza euclidea (usare il metodo Math.sqrt() per il calcolo della radice quadrata) Soluzione: DistanzaEuclidea.java
2. Date le coordinate di tre punti a=(xa, ya), b=(xb, yb), c=(xc, yc) stampare la distanza euclidea tra il punto a e il punto b, tra il punto b e il punto c, tra il punto a e il punto c
3. 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 (assumendo che siano reali).
   La radice quadrata si può calcolare con l'espressione Math.sqrt(....), dove i puntini rappresentano una qualsiasi espressione numerica con valore non negativo Soluzione: EquazioneSecondoGradoSoluzioniReali.java
4. Dato capitale iniziale e interesse annuo (ad esempio 4.5 se l'interesse è del 4,5% annuo), calcolare il capitale dopo un anno e dopo 3 anni Soluzione: Capitale3Anni.java
5. Stampare (per ora senza usare cicli) una tabella con il valore del seno e del coseno degli angoli da 0 a 90 gradi, con incrementi di 10 gradi.

   angolo   seno         coseno
   0        0            1
   10       0.17364...   0.98480...
   20       0.34202...   0.93969...
   30   .....
   ...
   90       1            0
   
   

   Soluzione: TabellaAngoli.java
   La documentazione sui metodi della classe Math è disponibile su http://docs.oracle.com/javase/7/docs/api/java/lang/Math.html. Notare che i metodi Math.sin e Math.cos richiedono che il valore dell'angolo sia specificato in radianti, e il metodo Math.toRadians permette di convertire una misura in gradi in una misura in radianti

Generazione di numeri pseudocasuali con Math.random()

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

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

Istruzione if() ... else ...

Espressioni booleane complesse: operatori && || !

Istruzione if() ...

Istruzioni if nidificate

1. Date le coordinate di tre punti a=(xa, ya), b=(xb, yb), c=(xc, yc) decidere quale tra b e c è il più vicino al punto a Soluzione: PiuVicino.java
2. 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. (Soluzione: EquazioneSecondoGrado.java)
3. Ordina tre numeri. Dati tre numeri interi distinti stamparli in ordine crescente. Si può decidere di eseguire i confronti e stampare i tre valori nell'ordine richiesto oppure di usare altre tre variabili alle quali assegnare rispettivamente il valore minimo, mediano e massimo e poi stampare le tre variabili: Ordina3.java
4. Verifica se tre interi possono essere le misure dei lati di un triangolo e individua il tipo di triangolo. Per esempio, 3, 2 e 8 non possono esserlo perché ... il triangolo non si riesce a "chiudere"! Soluzione: Triangolo.java
5. Come al punto precedente, ma in caso affermativo decidere se il triangolo è rettangolo, acutangolo od ottusangolo (suggerimento: se vael il teorema di Pitagora è rettangolo, altrimenti ...)
6. Dati due intervalli I1=[a, b] e I2=[c, d], rappresentati nel programma da quattro variabili int a, b, c, d;, con a<b e c<d, decidere se l'intervallo I1 contiene l'intervallo I2 (come ad esempio nel caso I1=[3, 40] e I2=[12, 25]) oppure I2 contiene I1, oppure non c'è relazione di contenimento (come ad esempio nel caso I1=[11, 56] e I2=[28, 80]. Visualizzare gli intervalli e un messaggio che indica l'eventuale contenimento. Soluzione: Intervalli.java

Programmi con istruzioni condizionali

Lettura di valori da tastiera con oggetti Scanner

Esercitazione 2

L'istruzione di ciclo while

Esercizi sull'uso di cicli e istruzioni condizionali

Uso di variabili boolean per il controllo di cicli

• 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 b, stampi il valore di ab, senza utilizzare il metodo Math.pow(..., ...) Soluzione: Potenza.java
• Scrivere un programma che stampi i numeri della successione di Fibonacci minori o uguali a 200 Soluzione: Fibonacci.java
• Scrivere un programma che stampi i primi 50 elementi della successione di Fibonacci Soluzione: PrimiNFibonacci.java
• 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à) Soluzione: ContaDivisori.java Soluzione più efficiente: ContaDivisoriVeloce.java

Semplici programmi con cicli

Analisi di una sequenza di numeri

Esercitazione 3

Esercizi sull'uso di cicli e istruzioni condizionali

Istruzioni break; e continue;

Istruzione di ciclo for, analogie con istruzione while

Esempi di programmi con cicli multipli e istruzioni di selezione

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

• Dato un numero naturale n, stampare un quadrato (pieno) di asterischi di lato n. Il quadrato sarà formato da n righe, ciascuna contenente n asterischi.

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

  Soluzione: QuadratoAsterischi.java
• Dato un numero naturale n, stampare un quadrato (solo il bordo) di asterischi di lato n. Il quadrato dovrà avere l'aspetto seguente:

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

  Soluzione: QuadratoBordoAsterischi.java
• Dati due numeri naturali n e b, con b < n/2, stampare un quadrato di asterischi di lato n con il bordo di spessore b. Ad esempio, se il valore di b fosse 3, il quadrato dovrebbe avere l'aspetto seguente:

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

  Soluzione: QuadratoBordoSpessoAsterischi.java
• Dato un numero naturale n, stampare un triangolo rettangolo (pieno) di asterischi di lato n. Il triangolo sarà formato da n righe di lunghezza crescente.

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

  Soluzione: TriangoloAsterischi.java
• Dato un numero naturale n, stampare un triangolo rettangolo (solo il bordo) di asterischi di lato n. Il triangolo dovrà avere l'aspetto seguente:

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

• Stampare la somma dei primi n termini della serie armonica: 1/1 + 1/2 + 1/3 + ... + 1/n SerieArmonicaSemplice.java
• Come sopra, mostrando la differenza tra il risultato ottenuto eseguendo la somma in un senso o in senso opposto: 1/1 + 1/2 + 1/3 + ... + 1/n rispetto a 1/n + 1/(n-1) + 1/(n-2) + ... + 1/2 + 1/1 SerieArmonica.java
• Mostrare l'andamento della somma della serie armonica, visualizzandone il valore ogni 100 termini aggiunti fino a un massimo numero di termini immesso da tastiera.
  Mostrare che la differenza tra la somma dei primi n termini e il logaritmo naturale (Math.log) di n, al crescere di n, tende a una costante. SerieArmonicaConTraccia.java
• Stampa della tavola pitagorica n per n TavolaPitagorica.java, assumendo che che l'input (n) sia compreso nell'intervallo [1,18] (Suggerimento: per ottenere la tabella ben incolonnata usare il metodo System.out.printf invece del metodo System.out.print)

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.

Soluzione: Frequenze.java

Metodi di input/output della classe JOptionPane

Esercizi su array monodimensionali.

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

Array bidimensionali. La proprietà length su array bidimensionali

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

• Leggi da tastiera una sequenza di interi (la lunghezza è data anch'essa da tastiera), memorizzala in un array monodimensionale, 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):
  1. stamparlo in forma di tabella (questo punto è risolto in StampaMatrice.java)
  2. trovare il massimo elemento della diagonale principale (assumendo che la matrice sia quadrata)
  3. stampare la somma di tutti gli elementi della matrice
  4. separatamente per ciascuna riga, stampare la somma degli elementi della riga
  5. separatamente per ciascuna colonna, stampare la somma degli elementi della colonna
  6. stampare la somma di tutti gli elementi sulla diagonale principale (assumendo che la matrice sia quadrata)
  7. stampare la somma di tutti gli elementi sulla diagonale secondaria (assumendo che la matrice sia quadrata)
  8. stampare la posizione (riga e colonna) dell'elemento massimo
  9. verificare se la matrice (che si assume quadrata) è simmetrica
  10. contare il numero di elementi paro a 0 nel triangolo inferiore (elementi al di sotto della diagonale principale), assumendo che la matrice sia quadrata

  Soluzione: MatriceVarie.java

• Dato un array bidimensionale 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

Esercizi su array bidimensionali.

Esercizi su array

Esercizi su array

Esercizi su array bidimensionali.

I metodi

Definizione e chiamata di metodi static

Metodi void, metodi che restituiscono valori

Parametri formali e parametri attuali: il passaggio dei parametri di tipo primitivo

• Esempio di metodi con o senza parametri o valore di ritorno Metodi.java
• Metodo che restituisce la media di due interi
• Metodo che restituisce il massimo tra due interi
• Metodo che restituisce il massimo tra tre interi

  Soluzione: SempliciMetodi.java

• Metodo che, dato come parametro un naturale, restituisce true se è primo o false se è composto
• 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

  Soluzione: StampaPrimi.java

• Metodo che, dati come parametri due naturali a e b, restituisce il valore ab
• Metodo che, dato come parametro un array di interi, restituisce la media dei valori dell'array
• Metodo che, dato come parametro un array di interi, stampa su una riga i valori degli elementi separati da spazio e termina andando a capo

La signature di un metodo

Overloading di metodi

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

programma che crea un array monodimensionale di int la cui dimensione è letta da tastiera, poi legge da tastiera gli elementi dell'array e poi, usando metodi, risolve i punti seguenti:

• stampa, in riga, gli elementi dell'array;
• stampa la media degli elementi dell'array;
• stampa la varianza degli elementi dell'array questo metodo ha bisogno di calcolare la media);
• stampa il numero di elementi maggiori di 100;
• stampa il numero di elementi maggiori di 130 (per questi due punti è utile usare lo stesso metodo);

Soluzione: MediaVarianzaEtcSuArray.java

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

Esercitazione su metodi su arrays

Esercitazione8.java

Ecco un esempio di soluzione (da leggere solo dopo aver tentato a lungo di risolvere l'esercizio) Esercitazione8/MieiMetodi.java

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

Complessità computazionale di semplici algoritmi

Capitolo 12 e seguenti

Cormen, Leiserson, Rivest, pagg. 21-26

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

Complessità computazionale della ricerca binaria

Passaggio dei parametri: riferimenti ad array:

• Ricerca binaria in array ordinato RicercaBinaria.java

Ulteriori metodi su arrays

• Esercitazione9.html
• altri esercizi

L'algoritmo di ordinamento per selezione (selection sort)

Analisi della complessità computazionale del selection sort

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

Analisi della complessità computazionale del bubble sort

Capitolo 12 e seguenti

Cormen, Leiserson, Rivest, pagg. 21-26

• 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 mostrati i tempi impiegati 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 System.currentTimeMillis() 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).

Introduzione alla ricorsione.

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

Il paradigma divide et impera.

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

Cmplessità computazionale del merge sort

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.

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

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

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, basandosi sulle chiamate presenti nel programma al punto successivo (ecco una possibile soluzione: Osservazioni.java)
• programma che usa un oggetto di classe Osservazioni (UsaOsservazioni.java)

• 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, ...

Gestione delle eccezioni: il costrutto try ... catch ...

Esercitazione 10: 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

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

Esercitazione sulla programmazione a oggetti

Definizione di sottoclassi

Chiamata del costruttore della superclasse attraverso super

Ereditarietà

Overriding: ridefinizione di metodi in sottoclassi

Il metodo toString() di Object e sua ridefinizione

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

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

Complessità computazionale dell'algoritmo MCD di Euclide