Laboratorio di Algoritmi e Strutture Dati

Docente:

• Luca Tesei

Orario delle Lezioni:

• Giovedì 10 - 13 (Aula, A. Turing)

Ricevimento studenti:

• Il Ricevimento è tutti i mercoledì dalle 11.30 alle 14.00 nella stanza CS 07 al secondo piano del Polo Tecnologico Palazzo Battibocca, via del Bastione 1, Camerino. Per eventuali variazioni si consulti preventivamente questa pagina.
• A partire dal 13 Giugno 2016 l'orario di ricevimento valido sarà solo quello indicato su questa pagina

Gli obiettivi indicati sono quelli del corso intero, comprensivo della parte teorica e della parte di laboratorio.

CONOSCENZA E CAPACITÀ DI COMPRENSIONE

Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

• Comprendere la nozione di complessità computazionale di un algoritmo in tempo e in spazio
• Illustrare le principali tecniche di progettazione di algoritmi
• Conoscere le strutture dati di base e le principali strutture dati evolute per risolvere problemi specifici di ricerca e rappresentazione di strutture complesse

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE

Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

• Applicare le principali tecniche di progettazione di algoritmi
• Classificare ed analizzare gli algoritmi in base alla loro complessità computazionale
• Ideare e implementare algoritmi per risolvere problemi specifici utilizzando le tecniche e le strutture dati conosciute

AUTONOMIA DI GIUDIZIO

Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

• Scegliere (ed implementare) le strutture dati più adatte alla risoluzione di un dato problema realizzando opportuni compromessi tra esigenze conflittuali come costo, semplicità ed efficienza.

ABILITÀ COMUNICATIVE

Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

• Produrre una relazione dettagliata sull’ideazione e l’implementazione di un progetto
• Avere la capacità di lavorare in gruppo per la realizzazione di un progetto

CAPACITÀ DI APPRENDIMENTO

Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

• Ricercare, comprendere e implementare algoritmi e strutture dati esistenti, ma non trattati nel corso, per la risoluzione di problemi specifici

La parte di laboratorio verterà sui seguenti contenuti:

• Richiami di Java e programmazione orientata agli oggetti, ereditarietà e polimorfismo, uguaglianza e ordinamento fra gli elementi di una classe
• Tipi generici e Collections
• Implementazione di tipi di dato astratto tramite tipi generici e interfacce di specifica: liste, pile, code, insiemi
• Implementazione di diversi algoritmi di ordinamento generici, realizzazione di un benchmark per la valutazione numerica della loro complessità computazionale e per la loro comparazione
• Implementazione di algoritmi su strutture dati dinamiche: alberi bilanciati, alberi binari di ricerca
• Rappresentazione di grafi e alberi, implementazione di visite e altri algoritmi su grafi e alberi

Slides e Codice

• 03/03/2016 Richiami di Java e OOP Codice Java su Equazioni di Secondo Grado
• 10/03/2016: Interfacce, Polimorfismo, Ereditarietà Codice DataSets Codice BankAccounts
• 17/03/2016: Collections - Tutorial Java sui Generics
• 24/03/2016: Liste Concatenate Doppie Implementazione (parziale) sviluppata a lezione
• 31/03/2016: Implementazione di Liste Concatenate Doppie con Iteratore Implementazione di Alberi Binari. Visite e alcune funzioni ricorsive.
• 07/04/2016: Alberi, Alberi Binari, Alberi Generici, Metodi Ricorsivi su Alberi Codice Sviluppato a Lezione su Alberi, Alberi Binari, Alberi Generici, Metodi Ricorsivi su Alberi
• 14/04/2016: Slides: Framework di Valutazione di Algoritmi di Ordinamento (Parziale) Codice del Framework di Valutazione di Algoritmi di Ordinamento (Parziale) con implementazione di Bubble Sort Codice del Framework di Valutazione di Algoritmi di Ordinamento (Parziale) con implementazione di Bubble Sort, Insertion Sort e Merge Sort
• 21/04/2016: Framework di valutazione per Algoritmi di Ordinamento con quattro algoritmi implementati e uno (HeapSort) da testare, Implementazione fatta a lezione di Heap binomiali (da testare), Esempio di valutazione della complessità computazionale nel caso medio usando i dati generati dal framework di valutazione
• 28/04/2016: Codice per tabella hash statica (sviluppato a lezione), Codice della classe per Alberi Binari di Ricerca (parziale)
• 05/05/2016: BackTracking e Problema delle otto regine, Strutture dati per la rappresentazione dei grafi (parziale, da completare nella prossima lezione)
• 12/05/2016: Interface generica per grafi e classe per gli archi, Esercitazione: implementazione dell'interfaccia tramite una classe per grafi non diretti rappresentati con liste di adiacenza.
• 19/05/2016: Nuova interfaccia generica per grafi e codice dell'implementazione dell'interfaccia tramite una classe per grafi non diretti rappresentati con liste di adiacenza - Implementazione di una generica visita in ampiezza con calcolo di albero di copertura e distanza minima data dal numero di archi da attraversare per raggiungere il nodo sorgente.
• 26/05/2016: Alberi minimi di copertura. Algoritmo di Prim. Codice sviluppato a lezione per implementazione senza coda di priorità (manca Test)
• 09/06/2016: Presentazioni degli studenti riguardo argomenti concordati: Algoritmi di ordinamento non basati su confronti. Algoritmi di scheduling. Algoritmi per cammini minimi su grafi.

Testi di Riferimento

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture Dati, McGraw-Hill, 2005
• C. Toffalori, F. Corradini, S. Leonesi, S. Mancini, Teoria della computabilità e della complessità, McGraw-Hill, 2005
• Saranno fornite dal docente dispense e slides integrative su cui studiare e fare esercizi. Per scaricare le dispense si consulti questo sito, nella sezione qui sopra.

Testi di Approfondimento

• Maurizio Gabbrielli, Simone Martini, “Linguaggi di programmazione - Principi e paradigmi 2/ed”, McGraw-Hill, 2011, ISBN: 9788838665738, Sito Web
• Duane A. Bailey, “Java Structures. Data Structures in Java, for the Principled Programmer”, Sito Web con versione pdf: http://www.cs.williams.edu/~bailey/JavaStructures

Regole di consegna dei Mini Progetti

• I file da consegnare per ogni Mini Progetto (indicati nel testo) dovranno essere caricati, entro la scadenza, in una cartella Google Drive dal nome ASDL1516CodiceMiniProgetto-CognomeStudente-NomeStudente che deve essere condivisa, in sola lettura, tramite l'account nome-studente.cognome-studente@studenti.unicam.it con gli account:
• luca.tesei@unicam.it (docente) e
• lorenzo.rossi@studenti.unicam.it (tutor).

Ad esempio, lo studente Mario Rossi, alla consegna del Mini Progetto 1 con codice MP1 dovrà caricare i file nella cartella ASDL1516MP1-Rossi-Mario.

Per la scadenza, farà fede la data dei file su Google Drive.

Testo dei Mini Progetti e Scadenze

• Mini Progetto 1 (Codice MP1) - Scadenza 16 Marzo 2016 ore 23.59
• ATTENZIONE: Versione del testo modificata il 7 Aprile 2016 ore 15.06: Mini Progetto 2 (Codice MP2) - Scadenza 20 Aprile 2016 ore 23.59 - Allegati: Stub del codice da implementare. Implementazione di MyList<E> con liste concatenate doppie.
• Mini Progetto 3 (Codice MP3) - Scadenza 11 Maggio 2016 ore 23.59 - Allegati: Codice Framework di valutazione e codice degli altri algoritmi di ordinamento, Esempio di valutazione
• Mini Progetto 4 (Codice MP4) Attenzione!!! Versione corretta del 1 Giugno 2016. Correzione: GenericGraphDFS<E,V> –> GenericGraphDFS<V,E> - Scadenza 13 Giugno 2016 ore 23.59 - Allegati: Codice dell'interfaccia Graph<V, E> e della classe Edge<V, E>

VALUTAZIONE PARZIALI E VERBALIZZAZIONE

La valutazione di tutti i mini progetti è disponibile sul foglio di valutazione Google Drive condiviso con lo studente. Il voto finale, con la data di attribuzione, è visibile anche alla prof.ssa Merelli che provvede alla determinazione della media finale delle due prove e alla verbalizzazione dei 12 CFU. Per gli orari e le modalità di verbalizzazione si prega di fare riferimento alla prof.ssa Merelli e alla Dott.ssa Michela Quadrini (michela <dot> quadrini <at> unicam <dot> it).

Regole di consegna dei Progetti Totali

I file .java per le classi, senza indicazione di package (cioè appartenenti al package di default), e il file con la relazione in pdf, devono essere caricati entro la data di scadenza dell'appello scelto per la consegna (si vedano le date nella sezione “Esami” qui sotto) in una cartella Google Drive dal nome

ASDL1516PTN-APPX-CognomeStudente-NomeStudente

dove N è il numero della traccia e X è il numero dell'appello in cui si consegna il progetto. La cartella deve essere condivisa, in sola lettura, tramite l'account

nome-studente.cognome-studente@studenti.unicam.it

di uno degli studenti del gruppo con gli account:

• luca.tesei@unicam.it
• emanuela.merelli@unicam.it

e con gli account degli altri studenti del gruppo.

Per la scadenza, farà fede la data dei file su Google Drive.

Testi proposti per i Progetti Totali

• Progetto totale 1 - Codice PT1 - max 2 studenti
• Progetto totale 2 - Codice PT2 - max 3 studenti, Codice allegato per l'interfaccia Graph<V, E> e per la classe Edge<V, E>.

Date Esami A.A. 2015/2016

Di seguito sono indicati gli appelli fissati con le relative date per la prova scritta (teoria) e la consegna dei progetti totali (laboratorio senza parziali):

• Appello I
  • Prova Scritta: 06/06/2016, ore 11.00, Aula Turing (ex Tribunale)
  • Consegna Progetto Totale di Laboratorio: entro Lun 13/06/2016 ore 23:59
  • Pubblicazione Calendario orali: Mar 14/06/2016 su questo sito
  • Orali: NON CI SONO PROGETTI CONSEGNATI
• Appello II
  • Prova Scritta: 01/07/2016, ore 11.00, Aula Turing (ex Tribunale)
  • Consegna Progetto Totale di Laboratorio: entro Dom 10/07/2016 ore 23:59
  • Pubblicazione Calendario orali: Lun 11/07/2016 su questo sito
  • Orali: Luca Tasso e Simone Dominici - Mer 13/07/16 ore 12:00 Sala Riunioni Palazzo Battibocca
• Appello III
  • Prova Scritta: 25/07/2016, ore 11.00, Aula Turing (ex Tribunale)
  • Consegna Progetto Totale di Laboratorio: entro Dom 24/07/2016 ore 23:59
  • Pubblicazione Calendario orali: Lun 25/07/2016 su questo sito
  • Giorni possibili per l'orale: Mar 26/07/2016 - Ven 29/07/2016
• Appello IV
  • Prova Scritta: 12/09/2016, ore 11.00, Aula Turing (ex Tribunale)
  • Consegna Progetto Totale di Laboratorio: entro Lun 05/09/2016 ore 23:59
  • Pubblicazione Calendario orali: Mar 06/09/2016 su questo sito
  • Giorni possibili per l'orale: Mer 07/09/2016 - Ven 09/09/2016
• Appello V
  • Prova Scritta: 30/09/2016, ore 11.00, Aula Turing (ex Tribunale)
  • Consegna Progetto Totale di Laboratorio: entro Lun 19/09/2016 ore 23:59
  • Pubblicazione Calendario orali: Mar 20/09/2016 su questo sito
  • Giorni possibili per l'orale: Mer 21/09/2016 - Ven 23/09/2016
• Appello VI
  • Prova Scritta: 07/11/2016, ore 11.00, Aula Turing (ex Tribunale)
  • Consegna Progetto Totale di Laboratorio: entro Mar 08/11/2016 ore 23:59
  • Pubblicazione Calendario orali: Mer 09/11/2016 su questo sito
  • Giorni possibili per l'orale: Gio 10/11/2016 - Ven 11/11/2016

Regole di esame: la parte di laboratorio assegna un voto che fa media con il voto ottenuto nella parte teorica. La registrazione del voto è unica per il totale di 12 CFU. Il voto per la parte di laboratorio può essere ottenuto presentando un progetto, assegnato dal docente, svolto singolarmente o in gruppi di massimo 2 o 3 persone (il progetto indicherà il numero massimo di componenti del gruppo). Gli studenti che seguono le lezioni potranno sostituire la realizzazione del progetto consegnando, nei tempi previsti, dei Mini Progetti (si veda la sezione apposita qui sopra) assegnati durante il corso. Questi ultimi potranno essere svolti solo singolarmente.

Voto Finale e Registrazione

• Il voto ottenuto nella parte di laboratorio sarà comunicato al docente della parte teorica che provvederà a fare la media e alla registrazione
• Qualora lo studente ottenga il voto nella parte di laboratorio prima di ottenere un voto nella parte teorica, tale voto potrà rimanere congelato, in attesa dell'ottenimento del voto nella parte teorica, per un massimo di 6 appelli.