Lab. Algoritmi e Strutture Dati 08

Attenzione: con l’inizio del corso per l’AA 2008-09 (ad Ottobre) è necessario rivolgersi al docente per qualsiasi cosa inerente il corso dell’AA 2007-08

Risultati Esame Scritto del 23/03/2008

L’esame si intende superato se avete riportato un voto maggiore o uguale a 4.

Risultati Esame Scritto del 22/02/2008

L’esame si intende superato se avete riportato un voto maggiore o uguale a 4.

Progetti

Il progetto va svolto in gruppi di 2-3 persone (3 massimo!). Non appena ricevo informazioni sulla composizione di un gruppo vi indico quale progetto svolgere.

[01] Domino
[02] Itinerari
[03] Oleodotti
[04] Percorsi
[05] Templi

Esame

L’esame è composto da tre parti:
1) [circa 25% voto finale, max 8/30esimi] Scritto che sarà svolto insieme allo scritto della parte teorica il 22/02. In alternativa la sola parte di laboratorio può essere svolta il 29/02
2) [circa 25% voto finale, max 8/30esimi] Assignment o orale (chi ha non ha svolto l’assignment o ha riportato un voto negativo deve sostenere l’orale)
3) [circa 50% voto finale, max 15/30esimi] Progetto (per la discussione contattatemi via mail)

Assignment valido per il superamento dell’esame

Testo in PDF

Elenco delle lezioni

[12/10 ore 10:00-13:00] Introduzione al corso, algoritmi e Java
[19/10 ore 10:00-13:00] Strutture dati elementari 1 2
[25/10 ore 15:00-18:00] Esercitazione su strutture dati elementari 1 2, Schema UML
[26/10 ore 10:00-13:00] Tipi di dati astratti
[08/11 ore 10:00-13:00] Alberi, Esercitazione, Schema UML
[09/11 ore 15:00-18:00] Algoritmi di ordinamento, Esercitazione
[07/12 ore 10:00-13:00] Selezione, Alberi binari di ricerca
[14/12 ore 10:00-13:00] Tabelle hash
[18/01 ore 10:00-13:00] Code con priorità, Union-find
[25/01 ore 10:00-13:00] Grafi, Minimo albero ricoprente
[01/02 ore 10:00-13:00] Cammini Minimi

Programma del corso

• Algoritmi e loro implementazione in Java
• Strutture dati elementari (array, liste concatenate,…)
• Tipi di dati astratti (stack, code FIFO e code generalizzate,…)
• Alberi e Ricorsione (algoritmi ricorsivi, divide et impera,…)
• Ordinamento (per selezione, per inserzione, Bubble Sort, Shellsort,…)
• QuickSort (algoritmo, prestazioni, gestione di elementi duplicati,…)
• Merging e mergesort ( a due vie, astratto sul posto, top-down, bottom-up, …)
• Selezione
• Alberi di Ricerca
• Tabelle hash (concatenazioni separate, scansione lineare, hashing doppio,…)
• Code con priorità e heapsort
• Union-find
• Grafi e visite di grafi
• Minimo albero ricoprente
• Cammini minimi
• …

Testi consigliati

• [Sed03] Algoritmi in JAVA (terza edizione), Robert Sedgewick, Addison-Wesley, 2003, ISBN: 88-7192-169-0
• [DPFI07] Progetto di Algoritmi e Strutture Dati in Java, C. Demetrescu, U. F. Petrillo, I. Finocchi, G. F. Italiano, McGraw-Hill, 2007, ISBN: 9788838663741 (anche se non necessario per il corso… solo la segnalazione di un buon testo)

Regolamento

Il corso ha come obiettivo quello di offrire con rigore metodologico una panoramica sulla progettazione, sviluppo e ingegnerizzazione dei principali algoritmi e strutture dati presenti in letteratura. Ogni lezione prevede un’introduzione all’argomento trattato e la presentazione di uno o più esempi. Verranno affrontate esercitazioni in aula e saranno proposti esercizi durante il corso.

L’esame prevede la realizzazione di un progetto con la relativa relazione. Vi troverete di fronte ad un problema che richiede l’uso di algoritmi e strutture dati specifiche e dovrete essere in grado di:

1. Analizzare dettagliatamente il problema
2. Fornirne una soluzione algoritmica
3. Implementare la soluzione proposta nel modo più efficiente possibile

Per ogni progetto è richiesta la consegna di:

1. Una relazione che descriva il problema, la soluzione algoritmica proposta e l’implementazione fornita

Il codice dell’applicazione opportunamente commentato

Note

1. Il linguaggio utilizzato è Java, di seguito trovate elencate alcune risorse disponibili in rete:
   1. Thinking in Java
   2. MokaByte (sezione download)
   3. Java Mattone dopo Mattone
2. L’ambiente di sviluppo è Eclipse. Tuttavia non siete obbligati, potete utilizzare l’ambiente o editor che preferite ma non sarete supportati per eventuali problemi!
3. Il codice sorgente degli esempi del libro è disponibile qui e qui
4. Java mette a disposizione numerosissime librerie con strutture dati, algoritmi, etc. La soluzione degli esercizi e del progetto finale non prevede l’uso di queste librerie poichè ha lo scopo di mostrare come librerie analoghe a queste possono essere realizzate!
5. La relazione va consegnata nel formato PDF o PS.

Organizzazione

Per la realizzazione delle esercitazioni e del progetto è consentito lavorare in gruppi di 2, massimo 3 elementi. E’ opportuno che la formazione dei gruppi avvenga il prima possibile. Per la tale scopo dovete inviare al docente una mail per gruppo con soggetto: “[LASD08] Richiesta gruppo” nella quale indicate in maniera chiara i vostri nomi, cognomi, ed indirizzi email. Riceverete come risposta una mail di accettazione con la quale vi sarà assegnato un codice/numero, nel seguito ogni comunicazione email dovrà contenere nell’oggetto la stringa [LASD08#codice] seguita poi dall’oggetto della mail.