Fondamenti di Informatica, anno accademico 2008-2009 |
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. Algoritmi di base su matrici. Ordinamento: selection sort, merge sort, quick sort, bubble sort. Algoritmo di Euclide per la ricerca del Massimo Comun Divisore (MCD).
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.
25 febbraio 2009 | ||
2 marzo 2009 | 3 marzo 2009 (lab) | 4 marzo 2009: annullata |
9 marzo 2009 | 10 marzo 2009 (lab) | 11 marzo 2009 |
16 marzo 2009 | 17 marzo 2009 (lab) | 18 marzo 2009 |
23 marzo 2009 | 24 marzo 2009 (lab) | 25 marzo 2009 |
30 marzo 2009 | 31 marzo 2009 (lab) | 1 aprile 2009 |
6 aprile 2009 | 7 aprile 2009 (lab) | 8 aprile 2009 |
vacanze pasquali | vacanze pasquali | 15 aprile 2009 |
20 aprile 2009 | 21 aprile 2009 (lab) | 22 aprile 2009 |
27 aprile 2009 | 28 aprile 2009 (lab) | 29 aprile 2009 |
4 maggio 2009: annullata | 5 maggio 2009 (lab) | 6 maggio 2009 |
11 maggio 2009 | 12 maggio 2009 (lab) | 13 maggio 2009 |
18 maggio 2009 | 19 maggio 2009 (lab) | 20 maggio 2009 |
25 maggio 2009 | 26 maggio 2009 (lab) | 27 maggio 2009: annullata causa commissione di laurea |
25 febbraio 2009 | |
---|---|
Argomenti | Introduzione al corso Concetto di algoritmo Esempi di algoritmi:
|
Riferimenti al testo | Capitolo 1 |
torna all'elenco delle lezioni
2 marzo 2009 | |
---|---|
Argomenti |
Architettura di un sistema di elaborazione Origini del linguaggio Java Compilazione e interpretazione di un programma in Java: codice sorgente, codice intermedio (bytecode); il ciclo di compilazione/esecuzione di programmi in Java; la Java Virtual Machine Esempi di programmi Java Tipi primitivi: aritmetici, carattere, boolean Dichiarazione di variabili Istruzione di assegnazione |
Riferimenti al testo | Capitolo 3 |
torna all'elenco delle lezioni
3 marzo 2009 (laboratorio) | |
---|---|
Argomenti | 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
|
Listati ed esercizi proposti | Esercitazione 1 |
torna all'elenco delle lezioni
9 marzo 2009 | |
---|---|
Argomenti | Tipi primitivi: aritmetici, carattere, boolean Dichiarazione di variabili Uso di literal (costanti) Operatori aritmetici Costruzione di espressioni complesse Precedenza tra operatori Conversioni implicite ed esplicite, operatore Assegnazioni tra tipi disomogenei |
Riferimenti al testo | Capitolo 3 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
10 marzo 2009 (laboratorio) | |
---|---|
Argomenti | Operatori relazionali: Uso della istruzione Istruzioni Input/output attraverso metodi della classe |
Esercizi proposti | Esercitazione 2 |
torna all'elenco delle lezioni
11 marzo 2009 | |
---|---|
Argomenti | Istruzione composta Espressioni booleane complesse: operatori Operatori di preincremento e postincremento Istruzioni di ciclo: l'istruzione Uso di variabili boolean per il controllo di cicli Istruzione Istruzioni di assegnazione con modifica |
Riferimenti al testo | Capitoli 4 e 5 |
Listati ed esercizi proposti |
|
16 marzo 2009 | |
---|---|
Argomenti | Esempi di semplici programmi con cicli e istruzioni di selezione |
Riferimenti al testo | Capitoli 4 e 5 |
Listati ed esercizi proposti | Vedi lezione precedente |
torna all'elenco delle lezioni
17 marzo 2009 (laboratorio) | |
---|---|
Argomenti | Metodi di input/output della classe JOptionPane Uso del ciclo while Ricerca di massimo e minimo di un insieme |
Riferimenti al testo | Capitoli 4 e 5 |
Listati ed esercizi proposti | Esercitazione 3 |
torna all'elenco delle lezioni
18 marzo 2009 | |
---|---|
Argomenti |
Soluzione dell'esercizio proposto nella esercitazione precedente: stampa di un triangolo di asterischi di lato n con vari orientamenti StampaTriangolo.java Istruzione di ciclo Istruzione di ciclo 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
23 marzo 2009 | |
---|---|
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 |
Data in input una sequenza di interi, che rappresentano frequenze, stampare:
|
torna all'elenco delle lezioni
24 marzo 2009 (laboratorio) | |
---|---|
Argomenti | Semplici esercizi su arrays |
Listati ed esercizi proposti | Esercitazione 4 |
torna all'elenco delle lezioni
25 marzo 2009 | |
---|---|
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
30 marzo 2009 | |
---|---|
Argomenti |
I metodi Definizione e chiamata di metodi La signature di un metodo I metodi Parametri formali e parametri attuali Passaggio di parametri per valore Passaggio di parametri array |
Riferimenti al testo | Capitolo 7 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
31 marzo 2009 | |
---|---|
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) Esercitazione 5 svolta |
torna all'elenco delle lezioni
1 aprile 2009 | |
---|---|
Argomenti |
L'algoritmo di ordinamento per selezione (selection sort) Cenni alla complessità computazionale del selection sort Calcolo del fattoriale |
Riferimenti al testo | Capitolo 7 |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
6 aprile 2009 | |
---|---|
Argomenti | Misure di complessità: la notazione asintotica O() Esempi di classi di funzioni Uso delle notazioni asintotiche per esprimere limitazioni superiori della complessità di algoritmi 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
7 aprile 2009 (lab) | |
---|---|
Argomenti | Esercitazione su:
|
Listati ed esercizi proposti | Esercitazione 6 |
torna all'elenco delle lezioni
8 aprile 2009 (lab) | |
---|---|
Argomenti | Esercizi di programmazione |
torna all'elenco delle lezioni
15 aprile 2009 | |
---|---|
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
20 aprile 2009 | |
---|---|
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: |
Riferimenti al testo | Capitoli 8 e seguenti |
Listati proposti |
Soluzione dell'esercizio proposto il 15 aprile
|
torna all'elenco delle lezioni
21 aprile 2009 (laboratorio) | |
---|---|
Argomenti | Accesso a file di testo |
Listati ed esercizi proposti | Esercitazione 7: accesso a file di testo. Nella stessa pagina è disponibile una soluzione alla esercitazione |
torna all'elenco delle lezioni
22 aprile 2009 | |
---|---|
Argomenti |
Eccezioni: eccezioni controllate e non controllate Gestione delle eccezioni (costrutto Posizionamento della gestione delle eccezioni Introduzione alla ricorsione. Esempio di algoritmo ricorsivo per il calcolo del fattoriale. L'algoritmo di Euclide per il calcolo del Massimo Comun Divisore
Analisi di complessità dell'algoritmo MCD di Euclide. |
Riferimenti al testo | Capitolo 12 e seguenti |
torna all'elenco delle lezioni
27 aprile 2009 | |
---|---|
Argomenti | L'algoritmo di ordinamento per fusione (Merge Sort)
Analisi di complessità del Merge Sort. |
torna all'elenco delle lezioni
28 aprile 2009 (laboratorio) | |
---|---|
Argomenti | Filtraggio righe da file di testo |
Listati ed esercizi proposti |
torna all'elenco delle lezioni
29 aprile 2009 | |
---|---|
Argomenti |
Il paradigma divide et impera. 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 L'algoritmo Quick sort (è disponibile una versione che mostra il funzionamento per ciascuna chiamata ricorsiva: QuickSort.java) |
Riferimenti al testo | Cormen, Leiserson, Rivest (pagine indicate) |
torna all'elenco delle lezioni
5 maggio 2009 (laboratorio) | |
---|---|
Argomenti | Merge di file di testo: metodi della classe String e StringBuffer
|
Listati ed esercizi proposti |
Una soluzione è disponibile in MergeFiles.java o in MergeFiles1.java |
torna all'elenco delle lezioni
6 maggio 2009 | |
---|---|
Argomenti | Algoritmo per il calcolo del k-esimo elemento: Selection.java Algoritmo di ordinamento a bolle (Bubble sort) e suoi miglioramenti |
torna all'elenco delle lezioni
11 maggio 2009 | |
---|---|
Argomenti | Codifica dell'informazione:
|
Riferimenti al testo | appunti delle lezioni e testo di Ceri, Mandrioli, Sbattella |
torna all'elenco delle lezioni
12 maggio 2009 (laboratorio) | |
---|---|
Argomenti | Scrittura di metodi su array bidimensionali, rappresentati in files di testo. |
Listati ed esercizi proposti |
torna all'elenco delle lezioni
13 maggio 2009 | |
---|---|
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
18 maggio 2009 | |
---|---|
Argomenti | Programmazione a oggetti:
|
Riferimenti al testo |
torna all'elenco delle lezioni
19 maggio 2009 (lab) | |
---|---|
Argomenti | Completamento della classe |
torna all'elenco delle lezioni
20 maggio 2009 | |
---|---|
Argomenti | Definizione di sottoclassi, Ereditarietà di campi e metodi. Specializzazione di metodi per la
sottoclasse attraverso la loro riscrittura (overriding). Il metodo |
Riferimenti al testo |
torna all'elenco delle lezioni
25 maggio 2009 | |
---|---|
Argomenti | Classi astratte e totalmente astratte ( |
Riferimenti al testo |
torna all'elenco delle lezioni
Scritto del 4 Giugno 2009 Scritto2009-06-04.pdf
Scritto del 25 Giugno 2009 Scritto2009-06-25.pdf
Scritto dell'8 Settembre 2009 Scritto2009-09-08.pdf