Corso di Algoritmi & Laboratorio

Laurea in Informatica - percorso SR

Anno accademico: 2005-2006

Docenti: Elio Giovannetti, András Horváth

Numero di ore: 54 (in aula) + 72 (in laboratorio)
Numero di CFU (Crediti Formativi Universitari): 6 (in aula) + 6 (in laboratorio)
Moduli: MODULO 1 (Lezioni in aula), MODULO 2 (Laboratorio).

INDICE

Obiettivi del corso
Competenze attese e propedeuticità
Come si svolgono le lezioni e le esercitazioni.
1. Slides
2. Programmi Java illustrati durante il corso.
3. Testi delle esercitazioni:
Programma/contenuti
Materiale didattico di supporto (a cura del docente)
Bibliografia (libri, articoli, documenti on-line,...)
Controllo dell'apprendimento (durante il corso)
Verifica (modalità d'esame)
1. Prova scritta 5 aprile 06: parte I
CORSO ON-LINE (I-learn = io-imparo): è necessario iscriversi per poter seguire il corso dall'inizio e frequentare il laboratorio.

1. Obiettivi del corso

Il corso ha lo scopo di fornire gli strumenti metodologici di base per il progetto, l'analisi ed il confronto di algoritmi e di introdurre alcuni algoritmi e strutture dati fondamentali. L'attività di laboratorio è strettamente integrata con le lezioni, e permetterà di mostrare come i linguaggi imperativi tipati object-oriented class-based, fra cui Java, siano particolarmente indicati per realizzare pacchetti software che implementino algoritmi e strutture dati.

2. Competenze attese e propedeuticità

Competenze attese in ingresso (richieste all'inizio del corso). Conoscenza delle basi della programmazione imperativa in C, delle basi della programmazione orientata agli oggetti in Java, e del concetto di ricorsione.
Eventuali corsi propedeutici (forniscono le "competenze attese in ingresso"). Programmazione I & Laboratorio, Programmazione II & Laboratorio, Laboratorio di linguaggi, Matematica Discreta, Analisi Matematica, Logica Matematica.
Competenze attese in uscita (acquisite durante il corso). Al termine del corso ci si aspetta che lo studente sia in grado di realizzare pacchetti software che supportino le strutture dati fondamentali e i relativi algoritmi sfruttando al meglio le caratteristiche proprie dei linguaggi imperativi tipati object-oriented class-based e utilizzando, in modo opportuno, classi e interfacce della libreria standard Java.

3. Come si svolgono le lezioni e le esercitazioni.

Le lezioni in aula si svolgono con l'ausilio del calcolatore e del proiettore (lucidi, esecuzione di programmi, ecc), integrati, quando opportuno, con l'uso di gesso e lavagna. Esse vengono condotte, per quanto possibile, in modo interattivo, sollecitando la partecipazione attiva degli studenti.

Le esercitazioni di laboratorio sono dedicate alle attività di progettazione/documentazione/codifica/test di progetti assegnati dal docente (che devono essere completati e consegnati entro le scadenze fissate di volta in volta), e, in attesa dei nuovi laboratori, si svolgono per ora nel laboratorio Dijkstra a gruppi di 2 (max 3) persone per macchina. Gli studenti che intendono frequentare il laboratorio per le esercitazioni si sono quindi organizzati in gruppi di 2 (max 3) persone:

ogni gruppo si è registrato compilando e riconsegnando al docente, entro la settimana 26-30 ottobre 2005, un apposito modulo scaricabile da qui;
ad ogni gruppo, all'atto della registrazione, è stato assegnato un numero; in base ad esso, a partire dal 3 ottobre:
- i gruppi dispari frequentano il turno T1;
- i gruppi pari frequentano il turno T2;
Le esercitazioni possono anche essere svolte a casa sul proprio PC; le consegne devono in ogni caso essere effettuate elettronicamente tramite I-learn.
Eventuali prove al calcolatore con valutazione individuale richiederanno invece, ovviamente, la presenza fisica dello studente in laboratorio.

4. Programma di massima.

Modulo 1

Tipi di dato e strutture dati
- Heap, code con priorità.
- Alberi, grafi.
Analisi di algoritmi: correttezza
- Asserzioni: precondizioni e postcondizioni.
- Invarianti di ciclo.
- Correttezza degli algoritmi ricorsivi.
- Invarianti di struttura (classe).
Analisi di algoritmi: complessità
- Analisi nel caso peggiore e nel caso medio.
- Ordine di grandezza delle funzioni.
- Notazione asintotica.
- Metodi per risolvere le equazioni di ricorrenza.
Algoritmi sui grafi
- Visite in ampiezza e profondità
- Minimo albero di copertura
- Cammini minimi
Metodi di risoluzione di problemi e progetto di algoritmi
- Divide et impera
- Greedy

Modulo 2

Riepilogo del meccanismo della compilazione separata nel linguaggio C.
Riepilogo di alcune caratteristiche del linguaggio Java (interfacce, polimorfismo, ereditarieta', classi astratte, eccezioni).
Concetto di tipo di dato astratto e sua realizzazione in linguaggi imperativi tipati (come C) e in linguaggi imperativi tipati object-oriented class-based (come Java).
Realizzazione, utilizzando la libreria standard Java, di tipi di dati astratti (Pila, Coda, Lista, Insieme, Bag, Mappa, Coda con priorita') e strutture dati (array, lista concatenata, albero binario di ricerca, tabella hash, heap); discussione di realizzazioni alternative; valutazione della complessita' computazionale (in tempo e spazio) dei vari algoritmi considerati.
Tipo di dato astratto grafo, sue possibili realizzazioni, e implementazione di alcuni algoritmi sui grafi.

[Corso di Studi di Informatica]


	Last update: Jul 28, 2016