Fondamenti di Informatica, anno accademico 2010-2011 |
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. Concetto di cartella, documento, applicazione. Il sistema operativo: funzioni principali, gestione dei processi, gestione della memoria, file system.
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 o completare sorgenti Java e di rispondere a domande su argomenti teorici.
28 settembre 2010 (laboratorio) | |
---|---|
Argomenti |
Introduzione al corso 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 Assegnazioni, uso di semplici espressioni Cenni sull'uso di cicli e istruzioni condizionali Esempi di semplici programmi Java |
Riferimenti al testo | Capitolo 3 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
30 Settembre 2010 | |
---|---|
Argomenti |
Tipi primitivi: interi, reali, carattere, boolean Dichiarazione di variabili Istruzione di assegnazione Uso di literal (costanti) Operatori aritmetici Semplici espressioni Assegnazioni tra tipi disomogenei Conversione implicita Conversione esplicita (cast) |
Riferimenti al testo | Capitolo 1, Capitolo 3 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
4 ottobre 2010 | |
---|---|
Argomenti | Costruzione di espressioni complesse Precedenza tra operatori Operatori relazionali: Istruzione Istruzione Istruzioni |
Riferimenti al testo | Capitolo 3 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
6 ottobre 2010 (laboratorio) | |
---|---|
Argomenti |
Correzione di errori sintattici e semantici Input/output attraverso un oggetto della classe Esercizi su assegnazioni e istruzioni condizionali |
Esercizi proposti | Esercitazione 1 |
torna all'elenco delle lezioni
8 ottobre 2010 | |
---|---|
Argomenti | Istruzione composta Espressioni booleane complesse: operatori Istruzioni di ciclo: l'istruzione |
Riferimenti al testo | Capitoli 4 e 5 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
11 ottobre 2010 | |
---|---|
Argomenti |
Operatori di preincremento e postincremento Uso di variabili boolean per il controllo di cicli Istruzioni di assegnazione con modifica |
Riferimenti al testo | Capitoli 4 e 5 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
13 ottobre 2010 (laboratorio) | |
---|---|
Argomenti |
|
Esercizi proposti | Esercitazione 2 |
torna all'elenco delle lezioni
15 ottobre 2010 | |
---|---|
Argomenti | Istruzione Istruzione di ciclo Istruzione di ciclo Esempi di semplici programmi con cicli e istruzioni di selezione |
Riferimenti al testo | Capitoli 4 e 5 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
18 ottobre 2010 | |
---|---|
Argomenti |
Soluzione dell'esercizio proposto nella esercitazione precedente: stampa di un triangolo di asterischi di lato n con vari orientamenti StampaTriangolo.java Sviluppo di algoritmi: approccio top-down Algoritmo di bisezione per la soluzione di una equazione in una variabile, e sua implementazione BisezioneSemplice.java |
Riferimenti al testo | Capitolo 5 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
20 ottobre 2010 (laboratorio) | |
---|---|
Argomenti |
Metodi di input/output della classe Generazione di numeri pseudocasuali con Esempi di programmi con cicli: verificare se una sequenza di numeri reali in input è crescente. |
Listati ed esercizi proposti | Esercitazione 3 |
torna all'elenco delle lezioni
22 ottobre 2010 | |
---|---|
Argomenti |
Esercizi su cicli |
Listati ed esercizi proposti |
Soluzione degli esercizi proposti nella esercitazione del 20 ottobre 2010
|
torna all'elenco delle lezioni
25 ottobre 2010 | |
---|---|
Argomenti |
Introduzione agli array monodimensionali: dichiarazione, allocazione ed uso Inizializzazione di array La proprietà Input e output di array |
Riferimenti al testo | Capitolo 6 |
Listati ed esercizi proposti |
Esercizi di base su array:
Data in input una sequenza di interi che rappresentano frequenze:
|
torna all'elenco delle lezioni
27 ottobre 2010 (laboratorio) | |
---|---|
Argomenti | Semplici esercizi su arrays |
Listati ed esercizi proposti | Esercitazione 4 |
torna all'elenco delle lezioni
29 ottobre 2010 | |
---|---|
Argomenti |
Variabili riferimento: il caso degli arrays Assegnazione tra arrays Arrays multidimensionali Esempi di algoritmi su arrays |
Riferimenti al testo | Capitolo 6 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
3 novembre 2010 (lab) | |
---|---|
Argomenti | Esercitazione su arrays multidimensionali |
Listati ed esercizi proposti | Esercitazione 5
Soluzione primo esercizio: Esercitazione5Svolto.java Soluzione secondo esercizio: Esercitazione5Prodotto.java |
torna all'elenco delle lezioni
5 novembre 2010 | |
---|---|
Argomenti |
I metodi Definizione e chiamata di metodi I metodi Parametri formali e parametri attuali: il passaggio dei parametri parametri.pps Passaggio di parametri per valore |
Riferimenti al testo | Capitolo 7 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
8 novembre 2010 | |
---|---|
Argomenti |
La signature di un metodo overloading di metodi
Accesso a metodi di classi esterne, chiamata di metodi Passaggio di parametri array (parametri riferimento) Calcolo del fattoriale Metodi che restituiscono un riferimento a array Ricerca sequenziale su un array (non ordinato) |
Riferimenti al testo | Capitolo 7 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
10 novembre 2010 | |
---|---|
Argomenti | Esercitazione su metodi su arrays |
Listati ed esercizi proposti |
Ecco un esempio di soluzione (da leggere solo dopo aver tentato a lungo di risolvere l'esercizio) Esercitazione6Svolta.java |
torna all'elenco delle lezioni
12 novembre 2010 | |
---|---|
Argomenti |
L'algoritmo di ordinamento per selezione (selection sort) Analisi della complessità computazionale del selection sort |
Riferimenti al testo | Cormen, Leiserson, Rivest, pagg. 21-26 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
15 novembre 2010 | |
---|---|
Argomenti |
Algoritmo di ordinamento a bolle (Bubble sort) e suoi miglioramenti Analisi della complessità computazionale del bubble sort L'algoritmo di ricerca binaria su array ordinati Analisi della complessità dell'algoritmo di ricerca binaria |
Riferimenti al testo | Cormen, Leiserson, Rivest, pagg. 21-26 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
17 novembre 2010 (lab) | |
---|---|
Argomenti | Esercitazione su:
|
Listati ed esercizi proposti | Esercitazione 7 |
torna all'elenco delle lezioni
19 novembre 2010 | |
---|---|
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 |
Riferimenti al testo | Capitolo 12 e seguenti Cormen, Leiserson, Rivest, pagg. 21-26 |
torna all'elenco delle lezioni
22 novembre 2010 | |
---|---|
Argomenti |
Introduzione alla ricorsione. Esempio di algoritmo ricorsivo per il calcolo del fattoriale L'algoritmo di Euclide per il calcolo del Massimo Comun Divisore: versione ricorsiva
L'algoritmo di ordinamento per fusione (Merge Sort)
|
Riferimenti al testo | Capitolo 12 e seguenti |
torna all'elenco delle lezioni
24 novembre 2010 (lab) | |
---|---|
Argomenti |
Eccezioni: eccezioni controllate e non controllate Gestione delle eccezioni (costrutto Posizionamento della gestione delle eccezioni |
Listati ed esercizi proposti | Esercitazione 8 Una soluzione è disponibile in Esercitazione8Svolta.java. |
torna all'elenco delle lezioni
26 novembre 2010 | |
---|---|
Argomenti |
Il paradigma divide et impera. L'algoritmo Quick sort: QuickSort.java Versione animata dell'algoritmo Quick sort, che mostra il funzionamento per ciascuna chiamata ricorsiva: QuickSortAnimato.java 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 |
Riferimenti al testo | Cormen, Leiserson, Rivest (pagine indicate) |
torna all'elenco delle lezioni
29 novembre 2010 | |
---|---|
Argomenti |
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). Analisi della complessità computazionale del merge sort senza utilizzare il teorema principale. |
Riferimenti al testo | Cormen, Leiserson, Rivest (pagine indicate) |
torna all'elenco delle lezioni
1 dicembre 2010 (lab) | |
---|---|
Argomenti | Esercizi di programmazione: Esercitazione 9 |
torna all'elenco delle lezioni
3 dicembre 2010 | |
---|---|
Argomenti |
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
Definizione della classe
|
Riferimenti al testo | Capitoli 8 e seguenti |
Listati proposti |
|
Esercizi proposti |
|
torna all'elenco delle lezioni
6 dicembre 2010 | |
---|---|
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 Alcune classi predefinite con metodi Alcune classi predefinite per costruire oggetti (quindi con metodi non |
Riferimenti al testo | Capitoli 8 e seguenti |
Listati proposti |
Soluzione dell'esercizio ProfittoStudente.java, proposto il 25 novembre:
|
torna all'elenco delle lezioni
10 dicembre 2010 | |
---|---|
Argomenti | Definizione di sottoclassi, Ereditarietà di campi e metodi. Specializzazione di metodi per la
sottoclasse attraverso la loro riscrittura (overriding). Il metodo la classe |
Riferimenti al testo |
torna all'elenco delle lezioni
13 dicembre 2010 | |
---|---|
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
15 dicembre 2010 (laboratorio) | |
---|---|
Argomenti | Accesso a file di testo
La classe |
Listati ed esercizi proposti |
Esercitazione 10: accesso a file di testo. Nella stessa pagina è disponibile una soluzione alla esercitazione |
torna all'elenco delle lezioni
10 gennaio 2011 | |
---|---|
Argomenti | Esercizi di programmazione Uso della classe |
torna all'elenco delle lezioni
12 gennaio 2011 (laboratorio) | |
---|---|
Argomenti | Esercitazione sulla programmazione a oggetti |
torna all'elenco delle lezioni
Scritto del 10 Novembre 2010 Scritto2010-11-10.pdf
Scritto del 19 Gennaio 2011 Scritto2011-01-19.pdf
Scritto del 14 Febbraio 2011 Scritto2011-02-14.pdf
Scritto del 7 Giugno 2011 Scritto2011-06-07.pdf
Scritto del 5 Luglio 2011
Scritto del 14 Settembre 2011
risultati