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

Laurea in Informatica - percorso STISI

Anno accademico: 2003-2004

Docenti: Ugo de'Liguoro , Ferruccio DAMIANI

INDICE

• Obiettivi del corso
• Prerequisiti del corso
• Modalita' d'esame
• Libri di testo
• Materiale didattico di supporto
• Programma dettagliato del corso

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.

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.

Il voto d'esame sara' la media pesata (con pesi 1/3 per il laboratorio e 2/3 per la verifica scritta) del punteggio conseguito nelle due parti.

Libri di testo

• A. Bertossi.
  "Algoritmi e strutture dati".
  UTET.
• 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:
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest.
    "Introduzione agli Algoritmi" (edizione in volume unico).
    Jackson Libri, 1997.
  • 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 1 e al Modulo 2 del corso.

Programma dettagliato del corso

Modulo 1

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.
• Cenni al tipo di dato astratto grafo e alle sue possibili realizzazioni.