DIPARTIMENTO   DI   INFORMATICA
Università di Torino

Corso di: Algoritmi & Laboratorio [Modulo 1(CFU 6) + Modulo 2(CFU 6)]

Laurea in Informatica - percorso SR

Anno accademico: 2003-2004

Docenti: Maddalena Zacchi , Ferruccio DAMIANI

INDICE

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.
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.

Prerequisiti

Contenuti dei corsi di "Programmazione I & Laboratorio", "Programmazione II & Laboratorio", e "Laboratorio di Linguaggi". In particolare si presuppone la conoscenza delle basi della programmazione imperativa in C, delle basi della programmazione orientata agli oggetti in Java, e del concetto di ricorsione.

Modalità d'esame

L'esame si compone di due parti: una discussione del progetto di laboratorio e una verifica scritta sui contenuti delle lezioni. Le prove finali possono essere superate (ottenendo una valutazione sufficiente)  in qualunque ordine, purchè a distanza non superiore a un anno l'una dall'altra.

Il voto d'esame è ottenuto come media delle votazioni, entrambe sufficienti, conseguite nelle due prove.

Libri di testo

  • Cormen, C.E. Leiserson, R.L. Rivest.

    • "Introduzione agli Algoritmi" (edizione in volume unico).
    Jackson Libri, 1999.
     
  • 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).
     
  • J. R. Hubbard.

    • Strutture dati in Java.
    McGraw-Hill.
    (ATTENZIONE: alcuni degli esempi di codice proposti in questo libro costituiscono, in realtà, pessimi esempi di programmazione, molto utili per capire quello che NON si deve fare).
     
  • Si consiglia inoltre la consultazione di alcuni capitoli dei libri:
    • A. Bertossi.

      • "Algoritmi e strutture dati".
      UTET.T.H.
    • Ken Arnold, James Gosling, David Holmes.

      • "The Java Programming Language" (3rd edition),
      (si vedano le pagine web a cura della SUN e a cura della Addison-Wesley ),
      Addison-Wesley, 2000
      (Manuale di riferimento per il linguaggio).

Materiale didattico di supporto

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

Programma del corso

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: Mar 08, 2004