DIPARTIMENTO   DI   INFORMATICA
Università di Torino

Corso di Algoritmi & Sperimentazioni

Laurea in Informatica - percorso STISI

Anno accademico: 2005-2006

Docente: Ferruccio DAMIANI

Numero di ore: 54 (in aula) + 36 (in laboratorio)
Numero di CFU (Crediti Formativi Universitari): 6 (in aula) + 3 (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,...)

Testi adottati: Testi di consultazione (alcune copie di questi testi sono disponibili in biblioteca --- controllare come alcuni argomenti sono presentati in modo diverso a seconda del testo rappresenta, di norma, un utile esercizio):
  • Per le lezioni in aula:
    • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein.
      "Introduzione agli algoritmi e alle strutture dati"
      McGraw-Hill, 2005.
    • A. Bertossi.
      Algoritmi e strutture dati,
      UTET, 2000.
  • 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 pesata rispetto al numero dei crediti (3 per il laboratorio, 6 per lo scritto) delle votazioni, entrambe sufficienti, conseguite nelle due prove.

Esempi di prove scritte per il Modulo 1:

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 del corso di Algoritmi & Laboratorio (percorso SR) tenuto lo scorso anno accademico.



[Corso di Studi di Informatica]
Last update: Jul 20, 2006