Fondamenti di Informatica, anno accademico 2017-2018 |
Obiettivi | Programma | Materiale didattico |
Orario delle lezioni | Ricevimento studenti | Modalità d'esame |
Diario delle lezioni | Prove d'esame |
Vengono presentati alcuni algoritmi fondamentali per problemi di ordinamento, ricerca e selezione, alcuni problemi numerici, evidenziandone le caratteristiche di efficienza attraverso l'analisi di complessità asintotica.
Vengono descritti i principali metodi di codifica dell'informazione.
Alla fine del corso lo studente sarà in grado di:
Componenti di un sistema di elaborazione: hardware, software, principali unità periferiche. Interazione con un sistema operativo basato su finestre. Il sistema operativo: funzioni principali, gestione dei processi, gestione della memoria, file system. Concetto di cartella, documento, applicazione/programma.
Rappresentazione dell'informazione: codifica di informazioni numeriche - sistemi di numerazione posizionali, codifica binaria, ottale, esadecimale, conversioni di base. Rappresentazione di numeri interi negativi. Rappresentazione in virgola mobile. Codifica di caratteri.
Concetto di algoritmo. Esempi di algoritmi in linguaggio naturale. Generalità sui linguaggi di programmazione, compilatori.
Programmazione in linguaggio Java: la Java Virtual Machine, ambienti di programmazione, compilazione ed esecuzione di programmi Java. Costrutti essenziali del linguaggio: variabili, espressioni, oggetti. Assegnazioni, metodi di input/output, istruzioni di selezione, ed iterazione. Uso di classi predefinite, invocazione di metodi. Consultazione della documentazione standard Java. Definizione di classi, principio della riutilizzazione del codice. Implementazione di vettori e matrici. Ereditarietà e polimorfismo.
Algoritmi fondamentali: Ricerca sequenziale, ricerca dicotomica su un vettore ordinato. Ordinamento: selection sort, merge sort, quick sort, bubble sort. Algoritmo di Euclide per la ricerca del Massimo Comun Divisore (MCD). Algoritmo per la ricerca del k-esimo elemento. Algoritmi di base su matrici.
Introduzione alla complessità computazionale: concetto di complessità di un algoritmo, notazioni asintotiche. Equazioni di ricorrenza e metodi per la loro soluzione. Complessità computazionale degli algoritmi studiati.
L'esame consiste in una prova scritta e un colloquio. Nella prova scritta si richiede di scrivere programmi in Java e di rispondere a domande su argomenti teorici.
25 settembre 2017 | 27 settembre 2017 (lab) | 29 settembre 2017 |
2 ottobre 2017 | 4 ottobre 2017 (lab) | 6 ottobre 2017 |
9 ottobre 2017 | 11 ottobre 2017 (lab) aula 5 - aula 8 |
13 ottobre 2017 |
16 ottobre 2017 | 18 ottobre 2017 (lab) | 20 ottobre 2017 |
23 ottobre 2017 | 25 ottobre 2017 (lab) | 27 ottobre 2017 |
30 ottobre 2017 | festività | |
interruzione attività didattica per svolgimento prove intermedie | ||
13 novembre 2017 | 15 novembre 2017 (lab) | 17 novembre 2017 |
25 settembre 2017 | |
---|---|
Argomenti |
|
torna all'elenco delle lezioni
27 settembre 2017 (lab) | |
---|---|
Argomenti |
Descrizione dei pacchetti JRE (Java Runtime Environment) e JDK (Java Development Kit) Editing di programmi Java con Blocco Note Compilazione ed esecuzione da "Prompt dei comandi" usando gli strumenti Esempi di semplici programmi Java I metodi Correzione di errori sintattici e semantici |
Esercizi proposti | Primo programma: primo programma |
torna all'elenco delle lezioni
29 settembre 2017 | |
---|---|
Argomenti |
Tipi primitivi: interi, reali, carattere, boolean Dichiarazione di variabili Identificatori Istruzione di assegnazione Uso di literal (costanti) Operatori aritmetici Semplici espressioni Overflow Assegnazioni, uso di semplici espressioni Precedenza tra operatori |
Listati ed esercizi proposti |
calcolo perimetro e area di un rettangolo CalcoloPerimetro.java Uso di tipi primitivi TipiPrimitivi.java |
torna all'elenco delle lezioni
2 ottobre 2017 | |
---|---|
Argomenti |
Conversione implicita Conversione esplicita (cast) Assegnazioni tra tipi disomogenei Precedenza tra operatori Costruzione di espressioni complesse |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
4 ottobre 2017 (lab) | |
---|---|
Argomenti |
Invocazione di metodi e uso del valore restituito Generazione di numeri pseudocasuali con Introduzione alle istruzioni condizionali |
Esercizi proposti |
torna all'elenco delle lezioni
6 ottobre 2017 | |
---|---|
Argomenti |
Istruzione Operatori relazionali: Istruzione composta Espressioni boolean: gli operatori logici Uso dell'istruzione composta nella istruzione Istruzione Istruzioni |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
9 ottobre 2017 | |
---|---|
Argomenti |
Lettura di valori da tastiera con oggetti Espressioni booleane complesse: operatori L'istruzione di ciclo Esercizi sull'uso di cicli e istruzioni condizionali |
Listati ed esercizi proposti |
Input da tastiera
Esaminare il programma
Negli esercizi proposti di seguito, utilizzare lo stesso schema per immettere valori da tastiera.
Per leggere un ... int a; double x; Scanner lettore; lettore = new Scanner(System.in); System.out.print("Digita un numero intero: "); a = lettore.nextInt(); System.out.print("Digita un numero reale: "); x = lettore.nextDouble(); ... Scrivere un programma che accetta da tastiera tre numeri reali e ne stampa massimo e media. Soluzione: MaxMedDaTastiera.java
|
torna all'elenco delle lezioni
11 ottobre 2017 aula 8 |
|
---|---|
Argomenti |
Uso di variabili boolean per il controllo di cicli Esercizi sull'uso di cicli e istruzioni condizionali Istruzione |
Esercizi proposti |
torna all'elenco delle lezioni
13 ottobre 2017 |
|
---|---|
Argomenti |
Istruzioni di assegnazione con modifica Operatori di preincremento e postincremento Semplici programmi con cicli Esempi di programmi con cicli multipli e istruzioni di selezione Istruzioni di ciclo |
Listati ed esercizi proposti |
Somme di quadratiScrivere un programma che, dato in input un numero naturale n, stampa tutte le coppie di naturali x, y tali che x^2 + y^2 = z^2, con x, y <= n e z naturale. Per n = 20 le soluzioni dovrebbero essere le seguenti: 3^2 + 4^2 = 5^2 5^2 + 12^2 = 13^2 6^2 + 8^2 = 10^2 8^2 + 15^2 = 17^2 9^2 + 12^2 = 15^2 12^2 + 16^2 = 20^2 Soluzione |
torna all'elenco delle lezioni
16 ottobre 2017 | |
---|---|
Argomenti |
Esercizi di programmazione |
torna all'elenco delle lezioni
18 ottobre 2017 (laboratorio) | |
---|---|
Argomenti |
Metodi di input/output della classe Riepilogo: input da tastiera con oggetti Esame di una sequenza. |
Listati ed esercizi proposti | Esercitazione 3 |
torna all'elenco delle lezioni
20 ottobre 2017 | |
---|---|
Argomenti |
Introduzione agli array monodimensionali: dichiarazione, allocazione ed uso La proprietà Input e output di array |
Listati ed esercizi proposti |
Esercizi di base su array:
Data in input una sequenza di interi che rappresentano frequenze:
Soluzione: Frequenze.java |
torna all'elenco delle lezioni
23 ottobre 2017 | |
---|---|
Argomenti |
Precisazioni sugli array monodimensionali: dichiarazione, allocazione e assegnazione del riferimento. Assegnazioni tra array. Inizializzazione di array. Algoritmo di ordinamento selection sort |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
25 ottobre 2017 (laboratorio) | |
---|---|
Argomenti |
Esercizi su array monodimensionali. |
Listati ed esercizi proposti | Esercitazione 5 |
torna all'elenco delle lezioni
27 ottobre 2017 | |
---|---|
Argomenti |
Algoritmo di ordinamento a bolle (Bubble sort) e suoi miglioramenti (Bubble sort migliorato) Analisi della prestazioni del bubble sort |
Listati ed esercizi proposti |
Dato un array di double di lunghezza n e un intero k<n, calcolare l'array delle n-k+1 medie mobili di lunghezza k. La media mobile di lunghezza k è la media di k elementi consecutivi, e naturalmente può essere calcolata a partire dalla prima posizione, dalla seconda, e così via fino ad iniziare in posizione n-k+1. Arricchire il programma del punto precedente individuando anche la posizione in cui si trovano la massima e la minima media mobile. |
torna all'elenco delle lezioni
30 ottobre 2017 | |
---|---|
Argomenti |
I metodi Definizione e chiamata di metodi Metodi Parametri formali e parametri attuali: il passaggio dei parametri di tipo primitivo La signature di un metodo Overloading di metodi |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
13 novembre 2017 | |
---|---|
Argomenti |
Il passaggio dei parametri
L'algoritmo di ricerca dicotomica (o ricerca binaria, ricerca logaritmica) |
Listati ed esercizi proposti |
Ricerca sequenziale in array RicercaSequenziale.java Selection sort con metodi su array SelectionSortMetodi.java Ricerca binaria (in array ordinato) RicercaBinaria.java Ricerca binaria (in array ordinato): soluzione con metodi RicercaBinariaMetodi.java |
Riferimenti al testo |
Cormen, Leiserson, Rivest, pagg. 21-26 |
torna all'elenco delle lezioni
15 novembre 2017 | |
---|---|
Argomenti | Metodi, accesso a classi esterne
|
torna all'elenco delle lezioni
17 novembre 2017 | |
---|---|
Argomenti |
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: selection sort, bubble sort, ricerca sequenziale e ricerca binaria |
Riferimenti al testo |
Cormen, Leiserson, Rivest, pagg. 21-26 |
torna all'elenco delle lezioni
20 novembre 2017 | |
---|---|
Argomenti |
Introduzione alla ricorsione. Esempio di algoritmo ricorsivo per il calcolo del fattoriale
Il paradigma divide et impera. Somma di un array applicando il paradigma divide et impera
Fusione di due array ordinati L'algoritmo di Euclide per il calcolo del Massimo Comun Divisore: versione ricorsiva
Complessità computazionale dell'algoritmo MCD di Euclide |
Riferimenti al testo | Cormen, Leiserson, Rivest |
Listati proposti |
|
torna all'elenco delle lezioni
22 novembre 2017 (aula) | |
---|---|
Argomenti |
L'algoritmo di ordinamento per fusione (Merge Sort)
Complessità computazionale del merge sort Array bidimensionali. |
Riferimenti al testo | Cormen, Leiserson, Rivest |
Link utili | Aminazione di algoritmi di ordinamento https://www.toptal.com/developers/sorting-algorithms |
torna all'elenco delle lezioni
22 novembre 2017 (laboratorio) | |
---|---|
Argomenti |
Esercitazione su array bidimensionali. |
Listati ed esercizi proposti | Esercitazione 6 |
torna all'elenco delle lezioni
24 novembre 2017 | |
---|---|
Argomenti |
L'algoritmo quick sort: QuickSort.java Versione animata dell'algoritmo quick sort, che mostra il funzionamento per ciascuna chiamata ricorsiva: QuickSortAnimato.java |
Riferimenti al testo | Cormen, Leiserson, Rivest (pagine indicate) |
Link utili | Aminazione di algoritmi di ordinamento https://www.toptal.com/developers/sorting-algorithms |
torna all'elenco delle lezioni
27 novembre 2017 | |
---|---|
Argomenti |
Analisi della complessità computazionale di algoritmi ricorsivi.
Complessità computazionale del quick sort nel caso peggiore Algoritmo per il calcolo del k-esimo elemento: Selection.java e sua complessità computazionale Versione animata dell'algoritmo Selection, che mostra il funzionamento per ciascuna chiamata ricorsiva: SelectionAnimato.java |
Riferimenti al testo | Cormen, Leiserson, Rivest (pagine indicate) |
torna all'elenco delle lezioni
29 novembre 2017 | |
---|---|
Argomenti |
Introduzione alla programmazione a oggetti
Definizione della classe
|
Listati proposti |
|
torna all'elenco delle lezioni
29 novembre 2017 (laboratorio) | |
---|---|
Argomenti |
Ulteriori metodi su arrays |
Listati ed esercizi proposti |
torna all'elenco delle lezioni
1 dicembre 2017 | |
---|---|
Argomenti |
Esempio di definizione ed uso di una classe Sovraccarico del costruttore: uso del L'oggetto di invocazione: uso del Definizione ed invocazione di metodi |
Listati proposti |
|
torna all'elenco delle lezioni
4 dicembre 2017 | |
---|---|
Argomenti |
Sottoclassi ed ereditarietà Definizione di sottoclassi definizione di una sottoclasse di Persona: Studente.java Chiamata del costruttore della superclasse attraverso esempio di uso della classe Studente: UsaStudente.java Il Ereditarietà Overriding: ridefinizione di metodi in sottoclassi Il metodo Chiamata di metodi della superclasse attraverso |
torna all'elenco delle lezioni
6 dicembre 2017 | |
---|---|
Argomenti | Codifica dell'informazione:
|
Riferimenti al testo | appunti delle lezioni e testo di Ceri, Mandrioli, Sbattella |
Listati ed esercizi proposti |
torna all'elenco delle lezioni
6 novembre 2017 (laboratorio) | |
---|---|
Argomenti |
Esercitazione sulla programmazione a oggetti |
torna all'elenco delle lezioni
11 dicembre 2017 | |
---|---|
Argomenti |
Esercizi di programmazione |
Listati ed esercizi proposti |
torna all'elenco delle lezioni
13 dicembre 2017 | |
---|---|
Argomenti |
Exceptions Il costrutto Il costrutto Esempio: lettura e scrittura di file di testo |
torna all'elenco delle lezioni
13 dicembre 2017 (laboratorio) | |
---|---|
Argomenti |
Accesso a file di testo
Uso del costrutto |
Listati ed esercizi proposti |
Esercitazione 9: accesso a file di testo. |
torna all'elenco delle lezioni
15 dicembre 2017 | |
---|---|
Argomenti |
Uso di oggetti Esercizi di programmazione Lettura di arrays da file di testo |
Listati ed esercizi proposti |
Metodi per la lettura di array monodimensionale e bidimensionali da file di testo MetodiFile.java |
torna all'elenco delle lezioni
20 dicembre 2017 | |
---|---|
Argomenti |
Esercizi di programmazione |
torna all'elenco delle lezioni
20 dicembre 2017 (laboratorio) | |
---|---|
Argomenti |
Esercizi di programmazione |
torna all'elenco delle lezioni
22 dicembre 2017 | |
---|---|
Argomenti |
Esercizi di programmazione |