Corso di Algoritmi & Laboratorio

Laurea in Informatica - percorso SR

Anno accademico: 2006-2007

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)

INDICE

1. Obiettivi del corso
2. Competenze attese e propedeuticità
3. Come si svolgono le lezioni e le esercitazioni.
4. Programma/contenuti
5. Materiale didattico di supporto (a cura del docente)
6. Bibliografia (libri, articoli, documenti on-line,...)
7. Controllo dell'apprendimento (durante il corso)
8. Verifica (modalità d'esame)
9. 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 parte integrante del corso e si svolgono nel laboratorio Dijkstra. Gli studenti devono iscriversi ad uno dei due turni di laboratorio, individualmente oppure a gruppi di 2 persone. L'iscrizione potrà essere effettuata durante la prima lezione, oppure successivamente tramite apposito modulo che sarà reso scaricabile da questa pagina.

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.

5. Materiale didattico di supporto.

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.

Slides del corso - versione con 6 slides per pagina
Slides del corso - versione con 2 slides per pagina
Slides prof. Horvath
Esercitazioni

6. Bibliografia (libri, articoli, documenti on-line,...)

7. Controllo dell'apprendimento (durante il corso)

Il controllo dell'apprendimento viene effettuato dai docenti in aula attraverso domande agli studenti, discussioni, svolgimento di esercitazioni al posto e alla lavagna; in laboratorio attraverso il monitoraggio dell'attività e test al calcolatore.

8. Verifica (modalità d'esame)

L'esame è costituito di tre parti: (1) una verifica scritta che riguarda gli argomenti presentati durante le lezioni in aula, (2) una discussione dell'attività di laboratorio effettuata dal candidato (realizzazioni di progetti ed esecuzione di esercizi) e (3) un breve colloquio di carattere generale, comprendente una discussione della verifica scritta e dei "compiti" assegnati dal docente durante le lezioni in aula. Le prove (1) e (2) possono essere superate (ottenendo una valutazione sufficiente) in qualunque ordine (anche in appelli diversi). La validità di tali prove è limitata al corrente anno accademico (cioè le prove non valgono più a partire dal primo appello del corso tenuto nell'anno accademico successivo). Eventuali deroghe (in seguito a gravi e giustificati motivi) potranno essere concordate con il docente prima dell'ultimo appello utile.

Il colloquio (3) può essere sostenuto solo DOPO AVER SUPERATO entrambe le prove (1) e (2), subito prima della registrazione del voto. In linea di massima, il voto finale è ottenuto come media dei voti dello scritto e del laboratorio, che devono essere entrambi sufficienti; tuttavia l'esito del colloquio (3) può in qualche caso modificare, anche di molto, tale valore (in casi-limite, potrebbe anche risultare nel non superamento dell'esame).

Esempi di prove scritte per il Modulo 1:

• 21 Dicembre 2004
• 7 Gennaio 2005
• 1 Aprile 2005
• 14 Aprile 2005

[Guida ufficiale del corso] (contiene le stesse informazioni riportate, in maggior dettaglio, in questa pagina).

[Corso di Studi di Informatica]

	Last update: Jul 28, 2016