Algoritmi e strutture dati - Laboratorio (2008/2009)

Corso disattivato non visibile

Codice insegnamento
4S00013
Docente
Roberto Posenato
crediti
2
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Sede
VERONA
Periodo
2° Q dal 26-gen-2009 al 27-mar-2009.
Pagina Web
http://profs.sci.univr.it/~posenato/home/courses/labASD

Per visualizzare la struttura dell'insegnamento a cui questo modulo appartiene, consultare * organizzazione dell'insegnamento

Orario lezioni

Obiettivi formativi

Nel modulo di laboratorio di Algoritmi e Strutture Dati vengono raffinate le conoscenze dello studente circa la pratica della programmazione a oggetti studiando l'implementazione di algoritmi e strutture dati visti nel modulo di teoria.

Il modulo viene svolto in 24 ore di lezione frontale in aula. Nelle rimanenti 26 ore (il modulo vale 2 crediti) lo studente è tenuto a studiare, realizzare e verificare le implementazioni in laboratorio.

Il linguaggio di programmazione usato è Java di cui si assume una conoscenza di base.

Programma

Lezione 1: Uso del meccanismo dell'Interfaccia. Richiamo dei concetti relativi al Javadoc e alle Eccezioni.

Lezione 2: Esempio di applicazione con l'implementazione dell'ADT Lista, Coda e Pila.

Lezione 3: Uso dell'interfaccia Comparable. Tecniche di confronto di implementazioni. Confronto tra QuickSort e MergeSort.

Lezione 4: Implementazioni dell'ADT HashTable.

Lezione 5: Implementazione di un algoritmo di programmazione dinamica: ricerca massima sottosequenza comune (LCS).

Lezione 6: Implementazioni dell'ADT Albero e Albero di ricerca binario. Uso dell'interfaccia Iterator. Implementazioni metodi di visita.

Lezione 7: Implementazione di un algoritmo greedy: algoritmo di Kruskal.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Giovanni Pighizzini, Mauro Ferrari Dai fondamenti agli oggetti. Corso di programmazione JAVA (Edizione 3) Pearson Addison-Wesley 2008 978 88 7192 448 9

Modalità d'esame

L'esame di laboratorio di Algoritmi e Strutture Dati consiste di una prova scritta contenente una serie di esercizi che richiedono la conoscenza delle esercitazione fatte in laboratorio. Questo significa che le esercitazioni stesse (comprensive di tutti i concetti ad esse collegate) e variazioni di esse sono da considerarsi argomento d'esame. L'obiettivo dell'esame è quello di verificare la capacità di formulare un algoritmo o una struttura dati nel linguaggio Java. Il risultato della prova di laboratorio viene integrato con il risultato della prova di teoria secondo le modalità descritte nel modulo di teoria.

La seguente lista indica i primi 10 algoritmi che si devono conoscere a memoria (senza appunti) sia dal punto di vista teorico sia dal punto di vista laboratorio (implementazione in Java).

Le prove d'esame sia di teoria sia di laboratorio potranno richiedere di presentare questi algoritmi o varianti di essi.

1. algoritmo di ordinamento Merge Sort
2. algoritmo di ordinamento Quick Sort
3. algoritmo di ordinamento Heap Sort
4. algoritmo di ordinamento Bucket Sort
5. algoritmo per la sottosequenza di lunghezza massima
6. algoritmo di selezione di attività
7. algoritmi di Kruskal e Prim
8. algoritmi di Dijkstra e Bellman-Ford
9. algoritmi di Floyd-Warshall e Johnson
10. algoritmo di Ford-Fulkerson

Condividi