Fondamenti di Informatica, anno accademico 2016-2017 |
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.
26 settembre 2016 | 28 settembre 2016 (lab) | 30 settembre 2016 |
3 ottobre 2016 | 5 ottobre 2016 (lab) | 7 ottobre 2016 |
10 ottobre 2016 | 12 ottobre 2016 (lab) | 14 ottobre 2016 |
17 ottobre 2016 | 19 ottobre 2016 (lab) | 21 ottobre 2016 |
24 ottobre 2016 | 26 ottobre 2016 (lab) | 28 ottobre 2016 |
sospensione attività didattica per verifiche strutturali |
2 novembre 2016 (lab) | 4 novembre 2016 |
7 novembre 2016 | interruzione attività didattica per svolgimento prove intermedie | |
14 novembre 2016 | 16 novembre 2016 (lab) | 18 novembre 2016 |
21 novembre 2016 | 23 novembre 2016
aula 14b, 8:30-10:30 |
23 novembre 2016 (lab)
gruppi riuniti, 10:30-12:30 |
25 novembre 2016 |
28 novembre 2016 | 30 novembre 2016
aula 14b, 8:30-10:30 |
30 novembre 2016 (lab)
gruppi riuniti, 10:30-12:30 |
2 dicembre 2016 |
sospensione | 7 dicembre 2016
aula 14b, 8:30-10:30 |
7 dicembre 2016 (lab)
gruppi riuniti, 10:30-12:30 |
sospensione |
12 dicembre 2016 | 14 dicembre 2016
aula 14b, 8:30-10:30 |
14 dicembre 2016 (lab)
gruppi riuniti, 10:30-12:30 |
16 dicembre 2016 |
26 settembre 2016 | |
---|---|
Argomenti |
|
torna all'elenco delle lezioni
28 settembre 2016 (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
30 settembre 2016 | |
---|---|
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
3 ottobre 2016 | |
---|---|
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
5 ottobre 2016 (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
7 ottobre 2016 | |
---|---|
Argomenti |
Lettura di valori da tastiera con oggetti Istruzione composta Uso dell'istruzione composta nella istruzione Istruzione Istruzioni |
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
10 ottobre 2016 | |
---|---|
Argomenti |
Espressioni booleane complesse: operatori L'istruzione di ciclo Esercizi sull'uso di cicli e istruzioni condizionali |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
12 ottobre 2016 (lab) | |
---|---|
Argomenti |
Istruzioni di assegnazione con modifica Semplici programmi con cicli Analisi di una sequenza di numeri |
Esercizi proposti |
torna all'elenco delle lezioni
14 ottobre 2016 | |
---|---|
Argomenti |
Uso di variabili boolean per il controllo di cicli Esercizi sull'uso di cicli e istruzioni condizionali Istruzione 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
17 ottobre 2016 | |
---|---|
Argomenti |
Istruzione di ciclo Operatori di preincremento e postincremento Esempi di programmi con cicli nidificati |
torna all'elenco delle lezioni
19 ottobre 2016 (laboratorio) | |
---|---|
Argomenti |
Metodi di input/output della classe Esame di una sequenza. |
Listati ed esercizi proposti | Esercitazione 4 |
torna all'elenco delle lezioni
21 ottobre 2016 | |
---|---|
Argomenti |
Esercizi di programmazione |
torna all'elenco delle lezioni
24 ottobre 2016 | |
---|---|
Argomenti |
Introduzione agli array monodimensionali: dichiarazione, allocazione ed uso Inizializzazione di array 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
26 ottobre 2016 (laboratorio) | |
---|---|
Argomenti |
Esercizi su array monodimensionali. |
Listati ed esercizi proposti | Esercitazione 5 |
torna all'elenco delle lezioni
28 ottobre 2016 | |
---|---|
Argomenti |
Algoritmo di ordinamento selection sort |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
2 novembre 2016 (laboratorio) | |
---|---|
Argomenti |
Array bidimensionali. |
Listati ed esercizi proposti | Esercitazione 6 |
torna all'elenco delle lezioni
4 novembre 2016 | |
---|---|
Argomenti |
Algoritmo di ordinamento a bolle (Bubble sort) e suoi miglioramenti (Bubble sort migliorato) Analisi della prestazioni del bubble sort |
torna all'elenco delle lezioni
7 novembre 2016 | |
---|---|
Argomenti |
L'algoritmo di ricerca binaria su array ordinati |
Listati ed esercizi proposti |
Ricerca binaria in array ordinato RicercaBinaria.java |
Riferimenti al testo |
Cormen, Leiserson, Rivest, pagg. 21-26 |
torna all'elenco delle lezioni
14 novembre 2016 | |
---|---|
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
16 novembre 2016 | |
---|---|
Argomenti | Metodi, accesso a classi esterne
|
torna all'elenco delle lezioni
18 novembre 2016 | |
---|---|
Argomenti |
Il passaggio dei parametri
|
Listati ed esercizi proposti |
Ricerca sequenziale in array RicercaSequenziale.java Selection sort con metodi su array SelectionSortMetodi.java |
torna all'elenco delle lezioni
21 novembre 2016 | |
---|---|
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 |
Listati ed esercizi proposti |
Ricerca binaria in array ordinato RicercaBinaria.java |
Riferimenti al testo |
Cormen, Leiserson, Rivest, pagg. 21-26 |
torna all'elenco delle lezioni
23 novembre 2016 | |
---|---|
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
23 novembre 2016 | |
---|---|
Argomenti |
Ulteriori metodi su arrays |
Listati ed esercizi proposti |
torna all'elenco delle lezioni
25 novembre 2016 | |
---|---|
Argomenti |
L'algoritmo di ordinamento per fusione (Merge Sort)
Complessità computazionale del merge sort |
Riferimenti al testo | Cormen, Leiserson, Rivest |
Link utili | animazione di algoritmi di sorting |
torna all'elenco delle lezioni
28 novembre 2016 | |
---|---|
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) |
Animazione di algoritmi di ordinamento https://www.toptal.com/developers/sorting-algorithms |
torna all'elenco delle lezioni
30 novembre 2016 | |
---|---|
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
30 novembre 2016 (laboratorio) | |
---|---|
Argomenti |
Accesso a file di testo
Gestione delle eccezioni: il costrutto |
Listati ed esercizi proposti |
Esercitazione 9: accesso a file di testo. |
torna all'elenco delle lezioni
2 dicembre 2016 | |
---|---|
Argomenti |
Introduzione alla programmazione a oggetti
Definizione della classe
|
Listati proposti |
|
torna all'elenco delle lezioni
7 dicembre 2016 | |
---|---|
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 Definizione di sottoclassi Chiamata del costruttore della superclasse attraverso |
Listati proposti |
|
torna all'elenco delle lezioni
7 dicembre 2016 (laboratorio) | |
---|---|
Argomenti |
Ereditarietà Overriding: ridefinizione di metodi in sottoclassi Il metodo Chiamata di metodi della superclasse attraverso Esercitazione sulla programmazione a oggetti |
torna all'elenco delle lezioni
12 dicembre 2016 | |
---|---|
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
14 dicembre 2016 | |
---|---|
Argomenti | Differenza tra metodi
Chiamata di metodi
Metodi della classe
|
Listati ed esercizi proposti |
torna all'elenco delle lezioni
14 dicembre 2016 (laboratorio) | |
---|---|
Argomenti |
Esercizi di programmazione |
torna all'elenco delle lezioni
16 dicembre 2016 | |
---|---|
Argomenti |
Esercizi di programmazione |