Corso di Algoritmi & Laboratorio

Laurea in Informatica - percorso SR

Anno accademico: 2004-2005

Docente: Ferruccio DAMIANI
Tutor (art. 33): Dott. Gian Luca POZZATO

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 (lezioni in laboratorio).

INDICE

1. Obiettivi del corso
2. Competenze attese e propedeuticità
3. Come si svolgono le lezioni (supporti alla didattica in uso alla docenza)
4. Programma/contenuti
5. Materiale didattico di supporto (a cura del docente)
6. Bibliografia (libri, articoli, documenti on-line,...)
7. Controllo dell'appprendimento (durante il corso)
8. Verifica (modalità d'esame)

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. Le sperimentazioni hanno lo scopo di presentare alcuni degli algoritmi e delle strutture dati fondamentali attraverso il linguaggio Java e di mostrare come i linguaggi imperativi tipati object-oriented class-based, come 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 Matematematica, 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 (supporti alla didattica in uso alla docenza)

Le lezioni (sia in aula che in laboratorio) sono svolte sia con l'usilio di lavagna e gesso che con l'ausilio del calcolatore (proiezione di lucidi animati). Una parte rilevante delle lezioni in laboratorio č dedicata 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 dal docente).

4. Programma/contenuti

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 (a cura del docente)

Il materiale didattico di supporto si trova alle pagine web relative al Modulo 1 e al Modulo 2 del corso.

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

• Per le lezioni in aula:
  • Demetrescu, Finocchi, Italiano.
    Algoritmi e strutture dati.
    McGraw-Hill, 2004.
• Per le lezioni in laboratorio:
  • C.S. Horstmann
    Concetti di Informatica e fondamenti di JAVA 2 - SECONDA EDIZIONE.
    Apogeo.
    (È il libro di testo utilizzato per i corsi di "Programmazione I e Laboratorio" e "Programmazione II e Laboratorio" - gli esempi di codice proposti in questo libro sono in generale ottimi esempi di programmazione).
  • Ken Arnold, James Gosling (creatore di Java), David Holmes
    JAVA (Manuale Ufficiale) - SECONDA EDIZIONE ITALIANA.
    Addison-Wesley, 2001. (Di quest'ultimo testo potrebbe essere sufficiente una copia per ogni 5/6 gruppi di laboratorio.)

• Per le lezioni in aula:
  • A. Bertossi.
    Algoritmi e strutture dati,
    UTET, 2000.
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest.
    "Introduzione agli Algoritmi" (edizione in volume unico).
    Jackson Libri, 1999.
    
• Per le lezioni in laboratorio:
  • R. Sedgewick.
    Algoritmi in Java (3 ed.).
    Pearson - Addison Wesley, 2003

7. Controllo dell'apprendimento (durante il corso)

Il controllo dell'apprendimento (per entrambi i moduli) è basato sulle domande che gli studenti fanno durante le ore di lezione e durante i ricevimenti. Inoltre, per quanto riguarda il Modulo 2 (lezioni in laboratorio), il docente controllerā lo stato di avanzmento dei progetti assegnati e eseguirā un primo test (alla presenza degli studenti) nella settimana precedente (o in quella successiva) alla consegna (i progetti assegnati devono essere completati e consegnati entro le scadenze fissate di volta in volta dal docente).

8. Verifica (modalità d'esame)

L'esame si compone di due parti: una discussione dei progetti svolti in laboratorio durante il corso e una verifica scritta sui contenuti delle lezioni. Le prove finali possono essere superate (ottenendo una valutazione sufficiente) in qualunque ordine. La validita' di tali prove e' limitata al corrente anno accademico (ovvero le prove non valgono piu' 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 voto d'esame è ottenuto come media delle votazioni, entrambe sufficienti, conseguite nelle due prove.

Esempi di prove scritte per il Modulo 1:

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

Esercizi da svolgere per il Modulo 2:

Gli esercizi da svolgere in laboratorio (assegnati periodicamente durante il corso) sono reperibili alla pagina web del Modulo 2. Altri esempi di progetti da svolgere in laboratorio sono reperibili alla pagina web del Modulo 2 tenuto lo scorso anno accademico .