Fondamenti di Informatica, anno accademico 2018-2019 |
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.
24 settembre 2018 | |
---|---|
Argomenti |
|
Materiale | Compilare il questionario con informazioni generali sugli studenti |
torna all'elenco delle lezioni
26 settembre 2018 (lab) | |
---|---|
Importante: comunica il tuo indirizzo e-mail | |
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
26 settembre 2018 | |
---|---|
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
1 ottobre 2018 | |
---|---|
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
3 ottobre 2018 (lab) | |
---|---|
Argomenti |
Invocazione di metodi e uso del valore restituito Generazione di numeri pseudocasuali con Stampa formattata con il metodo |
Esercizi proposti |
torna all'elenco delle lezioni
3 ottobre 2018 | |
---|---|
Argomenti |
Operatori relazionali: Istruzione Istruzione Istruzione composta Espressioni boolean complesse: gli operatori logici Uso dell'istruzione composta nella istruzione Istruzioni |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
8 ottobre 2018 | |
---|---|
Argomenti |
Lettura di valori da tastiera con oggetti 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 = 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
8-10 ottobre 2018 (lab) aula XI e aula 16 |
|
---|---|
Argomenti |
Esercizi sull'uso di cicli e istruzioni condizionali |
Esercizi proposti |
torna all'elenco delle lezioni
10 ottobre 2018 | |
---|---|
Argomenti |
Istruzioni di assegnazione con modifica Operatori di preincremento e postincremento Uso di variabili boolean per il controllo di cicli Semplici programmi con cicli Istruzione Esempi di programmi con cicli e istruzioni di selezione Istruzione 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: TernePitagoriche.java |
torna all'elenco delle lezioni
15 ottobre 2018 | |
---|---|
Argomenti |
Istruzione Esempi di programmi con cicli multipli e istruzioni di selezione Istruzione di ciclo Esercizi di programmazione |
torna all'elenco delle lezioni
15 ottobre 2018 (laboratorio) | |
---|---|
Argomenti |
Metodi di input/output della classe |
Listati ed esercizi proposti | Esercitazione 4 |
torna all'elenco delle lezioni
17 ottobre 2018 | |
---|---|
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
22 ottobre 2018 | |
---|---|
Argomenti |
Precisazioni sugli array monodimensionali: dichiarazione, allocazione e assegnazione del riferimento. Assegnazioni tra array. Inizializzazione di array. Algoritmo di ordinamento selection sort SelectionSortSemplice.java |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
22-24 ottobre 2018 (laboratorio) | |
---|---|
Argomenti |
Esercizi su array monodimensionali. |
Listati ed esercizi proposti | Esercitazione 5 |
torna all'elenco delle lezioni
24 ottobre 2018 | |
---|---|
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
31 ottobre 2018 (laboratorio) | |
---|---|
Argomenti |
Introduzione agli array bidimensionali. |
Listati ed esercizi proposti | Esercitazione 6 |
torna all'elenco delle lezioni
31 ottobre 2018 | |
---|---|
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
12 novembre 2018 | |
---|---|
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
12 e 14 novembre 2018 | |
---|---|
Argomenti | Metodi, accesso a classi esterne
Esercitazione7Svolta.java usando i metodi nella classe MieiMetodi.java |
torna all'elenco delle lezioni
14 novembre 2018 | |
---|---|
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
19 novembre 2018 | |
---|---|
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
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
21 novembre 2018 (laboratorio) | |
---|---|
Argomenti |
Ulteriori metodi su arrays |
Listati ed esercizi proposti |
torna all'elenco delle lezioni
21 novembre 2018 | |
---|---|
Argomenti |
Questo non è un algoritmo ricorsivo: fusione di due array ordinati in un nuovo array ordinato ( L'algoritmo di ordinamento per fusione (Merge Sort)
Complessità computazionale del merge sort |
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
26 novembre 2018 | |
---|---|
Argomenti |
L'algoritmo quick sort: QuickSort.java Versione animata dell'algoritmo quick sort, che mostra il funzionamento per ciascuna chiamata ricorsiva: QuickSortAnimato.java fuori programma: dimostrazione della complessità minima possibile (lower bound) per il problema dell'ordinamento basato su confronti |
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
28 novembre 2018 (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
28 novembre 2018 | |
---|---|
Argomenti |
Introduzione alla programmazione a oggetti
Definizione della classe
|
Listati proposti |
|
torna all'elenco delle lezioni
3 dicembre 2018 | |
---|---|
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
3 dicembre 2018 | |
---|---|
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
5 dicembre 2018 (laboratorio) | |
---|---|
Argomenti |
Esercitazione sulla programmazione a oggetti |
torna all'elenco delle lezioni
5 dicembre 2018 h 12:30 | |
---|---|
Argomenti |
Esercizi di programmazione Definizione di una classe EsperimentoLanciDado |
torna all'elenco delle lezioni
10 dicembre 2018 h 12:30 | |
---|---|
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
10 dicembre 2018 | |
---|---|
Argomenti |
Exceptions Il costrutto Il costrutto Esempio: lettura e scrittura di arrays da file di testo MetodiFile.java |
torna all'elenco delle lezioni
12 dicembre 2018 (laboratorio) | |
---|---|
Argomenti | Accesso a file attraverso oggetti JFileChooser
|
torna all'elenco delle lezioni
12 dicembre 2018 | |
---|---|
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
17 dicembre 2018 | |
---|---|
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
19 dicembre 2018 (lab) | |
---|---|
Argomenti |
Esercizi di programmazione |
Listati ed esercizi proposti |
|