Lab. Algoritmi e Strutture Dati 09

Attenzione: con l’inizio del corso per l’AA 2009-10 (ad Ottobre) è necessario rivolgersi al docente per qualsiasi cosa inerente i corsi degli anni precedenti

Progetti

L’ assegnazione del progetto viene fatta via mail o a lezione.

[01] Marble Game
[02] Light Bulbs
[03] The Great Wall Game
[04] Tunnels
[05] Zones
[06] Consanguine Calculations

Elenco delle lezioni

[10/10 ore 10:00-13:00] Introduzione al corso, Algoritmi e Java, Esempio interface

[17/10 ore 10:00-13:00] Strutture Dati Elementari

[24/10 ore 10:00-13:00] Es. 01 Strutture Dati Elementari, Codice: “base”, completo

[31/10 ore 10:00-13:00] Alberi, UML Strutture Dati Elementari, UML Alberi

[21/11 ore 10:00-13:00] Ordinamenti

[27/11 ore 15:00-18:00] Es. 02 Ordinamenti, codice

[28/11 ore 10:00-13:00] Selezione

[12/12 ore 10:00-13:00] Alberi di ricerca

[17/12 ore 15:00-18:00] Es.03 Alberi di Ricerca, codice

[09/01 ore 10:00-13:00] Tabelle Hash

Descrizione del corso

Il corso ha come obiettivo quello di offrire con rigore metodologico una panoramica sulla progettazione, sviluppo e ingegnerizzazione dei principali algoritmi e strutture dati. 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.

Esame

L’esame prevede, oltre il superamento di una verifica scritta, la realizzazione di un progetto e la stesura della 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: (i) analizzare dettagliatamente il problema, (ii) progettare una soluzione algoritmica, (iii) implementare la soluzione proposta nel modo più efficiente possibile.

Per ogni progetto è richiesta la consegna di:

1. Il codice dell’applicazione opportunamente commentato
2. Una relazione che descriva il problema, la soluzione algoritmica proposta e l’implementazione fornita

L’esame è composto da due parti:

1. [circa 50% voto finale] Scritto, svolto in genere nelle stesse date dello scritto di teoria e/o segnalate sul sito
2. [circa 50% voto finale] Progetto. La discussione viene svolta dopo lo svolgimento dello scritto. Occorre presentare il codice funzionante e la relazione stampata.
   Attenzione: (i) Non sono ammesse modifiche del codice “al volo” durante lo svolgimento dell’esame. Siente pregati di testare il vostro cosdice prima di presentarlo. (ii) La relazione va stampata. (iii) DURANTE LA DISCUSSIONE DEL PROGETTO POSSONO ESSERE EFFETTUATE DOMANDE RELATIVE AL COMPITO SCRITTO!

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

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
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 3 persone. 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: “[LASD09] Richiesta gruppo” nella quale indicate in maniera chiara i vostri nomi e cognomi. 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 [LASD09#codice] seguita poi dall’oggetto della mail. PER LE COMUNICAZIONI MAIL DOVETE UTILIZZARE L’INDIRIZZO MAIL CHE VI E’ STATO ASSEGNATO DA UNICAM (@studenti.unicam.it )