Laboratorio di Algoritmi e Strutture Dati


News

  • 31 Gennaio 2017:

Recupero Mini Progetti di Laboratorio

Gli studenti possono rimpiazzare il voto di MP1, MP2, MP3 o recuperare il voto di MP1, MP2, MP3 (in caso uno di questi non sia stato consegnato) facendo una presentazione orale (con slides e codice da implementare e illustrare) su un argomento da scegliere fra una lista di proposte.

Gli studenti interessati possono compilare il seguente form a partire dal 31/01/2017:

https://goo.gl/forms/Xb6HoSy7yRILCZEk1

Coloro che richiedono di rimpiazzare/recuperare MP1 ed MP2 potranno scegliere da subito l'argomento (con modalità First-In-First-Out). La lista sarà comunicata dopo la richiesta tramite il form.

Coloro che aspettano l'esito di MP3 per esprimersi potranno scegliere successivamente. Per motivi di tempo non potrà essere richiesto il rimpiazzamento o il recupero di MP4.

  • 19 Dicembre 2016:

A causa di un impegno del docente su un progetto EU la lezione di Lunedì 19 Dicembre è cancellata.

  • 1 Dicembre 2016:

Avviso riguardo la ripresa delle lezioni. La prima lezione sarà Giovedì 1 dicembre alle ore 14 in aula LA1 del Polo Lodovici, Via Madonna delle Carceri 9, Camerino. In via eccezionale, fino a Natale 2016, si terranno solo lezioni di ASDL e non di ASDT. Si veda la sezione “Informazioni Generali” qui sotto per l'orario completo.

  • 9 Novembre 2016:

Avviso riguardo il Mini Progetto 1 di ASDL. Ho ricevuto diverse richieste da parte di studenti che non hanno accesso al pc perché rimasto nelle case del centro storico di Camerino. Tali studenti hanno difficoltà a consegnare anche entro la nuova data di scadenza del 15 Novembre. Per coloro che si trovano in questa situazione o che per altri motivi non possono consegnare in tempo il MP1 (o anche uno dei successivi MP), sarà possibile alla fine del corso (fine gennaio 2017) recuperare uno qualsiasi dei Mini Progetti (quindi anche MP1) attraverso una attività di studio individuale + presentazione pubblica su una tematica da concordare con il docente.

  • 2 Novembre 2016:

A seguito degli eventi sismici, le lezioni dal 27/10/2016 sono sospese fino a nuova comunicazione da parte dell'Ateneo. La scadenza del mini progetto 1 in data 4 novembre è stata posticipata al 15 novembre 2016.

  • 29 Ottobre 2016:

Per coloro che sono su Facebook, è disponibile il gruppo ASD-2016-2017 al seguente link

  • 7 Settembre 2016:

La pagina del corso 2016/17 è on-line. Gli studenti che vogliono fare gli esami della sessione di settembre/ottobre 2016 devono fare riferimento al sito del corso dell'anno scorso, sempre su questo wiki: Laboratorio di Algoritmi e Strutture Dati 2015/16


Informazioni Generali

Docente:

Orario delle Lezioni:

  • Tutti i giovedì dalle 15.00 alle 18.00 in Aula Turing (Palazzo di Informatica, ex Tribunale) orario e aula da ridefinire alla ripresa delle lezioni dopo gli eventi sismici.

Nuovo orario a partire dal 30/11/2016

  • Giovedì 14-17 Aula LA1 del Polo Lodovici, Via Madonna delle Carceri 9, Camerino. Gli studenti possono seguire la lezioni in streaming tramite il sistema WebEx collegandosi a questo link: https://cmr-em.webex.com/meet/pololodo.aulalab1.unicam. Le istruzioni per usare il sistema di web conference si possono trovare qui.
  • In via eccezionale, fino al 20/12/2016, si terranno lezioni di ASDL a posto di quelle di ASDT (Algoritmi e strutture dati - Teoria) nei seguenti orari:
    • Lunedì 14-16 Aula LA2 del Polo Lodovici, Via Madonna delle Carceri 9, Camerino. Gli studenti possono seguire la lezioni in streaming tramite il sistema WebEx collegandosi a questo link: https://cmr-em.webex.com/meet/pololodo.aulalab2.unicam. Le istruzioni per usare il sistema di web conference si possono trovare qui.
    • Martedì 14-16 Aula AB2 del Polo Lodovici, Via Madonna delle Carceri 9, Camerino. Gli studenti possono seguire la lezioni in streaming tramite il sistema WebEx collegandosi a questo link: https://cmr-em.webex.com/meet/pololodo.aulaab2.unicam. Le istruzioni per usare il sistema di web conference si possono trovare qui.

Ricevimento studenti:

  • A partire dal 3 Ottobre 2016 l'orario di ricevimento sarà tutti i mercoledì dalle 15.00 alle 17.00 salvo modifiche che saranno indicate settimana per settimana su questa pagina. Il ricevimento si tiene nel mio studio, stanza CS07 al secondo piano del Palazzo Battibocca, Via del Bastione 1, Camerino
  • A seguito degli eventi sismici, gli studenti possono richiedermi un ricevimento online tramite Google Hangout o Skype via email a luca.tesei@unicam.it indicando una o più date/ore in cui sarebbero disponibili per il ricevimento online.
  • A partire dal 09/01/2017 il ricevimento ci sarà tutti i Giovedì dalle ore 12 alle ore 14 nel mio studio al primo piano del Polo Lodovici, via Madonna delle Carceri 9, Camerino. Gli studenti impossibilitati a recarsi fisicamente a Camerino potranno collegarsi alla mia stanza virtuale Webex nell'orario indicato oppure richiedere un altro orario via email.

Acronimo ufficiale del corso:

  • ASDL1617

Obiettivi del Corso

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

Contenuti del Corso

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

Materiale

Slides e Codice

Testi di Riferimento

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture Dati, McGraw-Hill, 2005, 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
  • 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

  • C. Toffalori, F. Corradini, S. Leonesi, S. Mancini, Teoria della computabilità e della complessità, McGraw-Hill, 2005, Sito Web
  • Maurizio Gabbrielli, Simone Martini, “Linguaggi di programmazione - Principi e paradigmi 2/ed”, McGraw-Hill, 2011, ISBN: 9788838665738, Sito Web

Mini Progetti per i Frequentanti

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 ASDL1617CodiceMiniProgetto-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
  • matteo.micheletti@unicam.it (tutor)

Ad esempio, lo studente Mario Rossi, alla consegna del Mini Progetto 1 con codice MP1 dovrà caricare i file nella cartella ASDL1617MP1-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 4 Novembre 2016 ore 23.59 - Nuova scadenza a seguito del terremoto Martedì 15 Novembre 2016 ore 23.59 - Valutazione rilasciata il 14/12/2016 - Ogni studente ha ottenuto in condivisione il proprio foglio di valutazione personale su Google Drive (controllare l'email @studenti.unicam.it oppure la meta-cartella “File Condivisi con Me” su Google Drive accedendo con il proprio account @studenti.unicam.it)
  • Mini Progetto 2 (Codice MP2) - Scadenza 13 Gennaio 2017 ore 23.59 - ATTENZIONE: Versione del testo modificata il 27 Dicembre 2016 ore 16.30 - non va implementato il metodo “List<E> subList(int fromIndex, int toIndex)”, Nuovo Testo
  • Mini Progetto 4 (Codice MP4), Codice Allegato - Scadenza 3 Marzo 2017 ore 23.59 - Precisazione su MP4: in caso di archi etichettati, tra due stessi nodi ci possono essere anche due o più archi orientati con etichetta diversa e con stessa sorgente e destinazione. Non è obbligatorio nel progetto prevedere anche questo caso, cioè è accettabile anche definire la matrice di adiacenza in modo tale che tra due stessi nodi sorgente-destinazione sia possibile rappresentare al più un arco orientato.

Recupero Mini Progetti di Laboratorio

Gli studenti possono rimpiazzare il voto di MP1, MP2, MP3 o recuperare il voto di MP1, MP2, MP3 (in caso uno di questi non sia stato consegnato) facendo una presentazione orale (con slides e codice da implementare e illustrare) su un argomento da scegliere fra una lista di proposte.

Gli studenti interessati possono compilare il seguente form a partire dal 31/01/2017:

https://goo.gl/forms/Xb6HoSy7yRILCZEk1

Coloro che richiedono di rimpiazzare/recuperare MP1 ed MP2 potranno scegliere da subito l'argomento (con modalità First-In-First-Out). La lista sarà comunicata dopo la richiesta tramite il form.

Coloro che aspettano l'esito di MP3 per esprimersi potranno scegliere successivamente. Per motivi di tempo non potrà essere richiesto il rimpiazzamento o il recupero di MP4.

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).


Progetti Totali per i non Frequentanti

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

ASDL1617PTN-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


Esami

Date Esami A.A. 2016/2017

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 Aggiornato per slittamento semestri a causa del terremoto
    • Prova Scritta: si veda ESSE3 (prof.ssa Merelli)
    • Consegna Progetto Totale di Laboratorio: entro Lun 30/01/2017 Lun 20/02/2017 ore 23:59
    • Pubblicazione Calendario orali: Mar 31/01/2017 Mar 21/02/2017 su questo sito
    • Orali:
      • Massimiliano Sampaolo - Giovedì 23/02/2017 ore 10.00 Polo Lodovici Aula da definire sul momento o ufficio Tesei
      • Giulio Quaresima - Giovedì 23/02/2017 ore 10.30 Polo Lodovici Aula da definire sul momento o ufficio Tesei
  • Appello II Aggiornato per slittamento semestri a causa del terremoto
    • Prova Scritta: si veda ESSE3 (prof.ssa Merelli)
    • Consegna Progetto Totale di Laboratorio: entro Dom 12/02/2017 Lun 06/03/2017 ore 23:59
    • Pubblicazione Calendario orali: Lun 13/02/2017 Mar 07/03/2017 su questo sito
    • Orali: da Mar 14/02/2017 a Gio 16/02/2017 da Mer 08/03/2017 a Ven 10/03/2017
  • Appello III Aggiornato per slittamento semestri a causa del terremoto
    • Prova Scritta di Teoria: 19/06/2017 - Iscrizione su ESSE3 (prof.ssa Merelli)
    • Consegna Progetto Totale di Laboratorio: entro Lun 26/06/2017 ore 23:59
    • Iscrizione su ESSE3 alla prova parziale “Progetto Lab - III Appello”: entro Lun 26/06/2017 ore 23:59
    • Pubblicazione Calendario Orali Laboratorio: Mar 27/06/2017 su questo sito e tramite Google Calendar
    • Orali Laboratorio: da Mer 28/06/2017 a Ven 30/06/2017
    • Registrazione Esame (12 CFU): Lun 03/07/2017 previa iscrizione su ESSE3 al “III Appello ASD” (prof.ssa Merelli)
  • Appello IV Aggiornato per slittamento semestri a causa del terremoto
    • Prova Scritta di Teoria: 10/07/2017 - Iscrizione su ESSE3 (prof.ssa Merelli)
    • Consegna Progetto Totale di Laboratorio: entro Lun 10/07/2017 ore 23:59
    • Iscrizione su ESSE3 alla prova parziale “Progetto Lab - IV Appello”: entro Lun 10/07/2017 ore 23:59
    • Pubblicazione Calendario Orali Laboratorio: Mar 11/07/2017 su questo sito e tramite Google Calendar
    • Orali Laboratorio: da Mer 12/07/2017 a Gio 13/07/2017
    • Registrazione Esame (12 CFU): Ven 14/07/2017 previa iscrizione su ESSE3 al “IV Appello ASD” (prof.ssa Merelli)
  • Appello V
    • Prova Scritta di Teoria: 04/09/2017 - Iscrizione su ESSE3 (prof.ssa Merelli)
    • Consegna Progetto Totale di Laboratorio: entro Lun 11/09/2017 ore 23:59
    • Iscrizione su ESSE3 alla prova parziale “Progetto Lab - V Appello”: entro Lun 11/09/2017 ore 23:59
    • Pubblicazione Calendario Orali Laboratorio: Mar 12/09/2017 su questo sito e tramite Google Calendar
    • Orali Laboratorio: da Mer 13/09/2017 a Gio 14/09/2017
    • Registrazione Esame (12 CFU): Ven 15/09/2017 previa iscrizione su ESSE3 al “V Appello ASD” (prof.ssa Merelli)
  • Appello VI
    • Prova Scritta di Teoria: 18/09/2017 - Iscrizione su ESSE3 (prof.ssa Merelli)
    • Consegna Progetto Totale di Laboratorio: entro Lun 25/09/2017 ore 23:59
    • Iscrizione su ESSE3 alla prova parziale “Progetto Lab - VI Appello”: entro Lun 25/09/2017 ore 23:59
    • Pubblicazione Calendario Orali Laboratorio: Mar 26/09/2017 su questo sito e tramite Google Calendar
    • Orali Laboratorio: da Mer 27/09/2017 a Gio 28/09/2017
    • Registrazione Esame (12 CFU): Ven 29/09/2017 previa iscrizione su ESSE3 al “VI Appello ASD” (prof.ssa Merelli)
  • Appello VII
    • Prova Scritta di Teoria: 05/02/2018 - Iscrizione su ESSE3 (prof.ssa Merelli)
    • Consegna Progetto Totale di Laboratorio: entro Lun 05/02/2018 ore 23:59
    • Iscrizione su ESSE3 alla prova parziale “Progetto Lab - VII Appello”: entro Lun 05/02/2018 ore 23:59
    • Pubblicazione Calendario Orali Laboratorio: Mar 06/02/2018 su questo sito e tramite Google Calendar
    • Orali Laboratorio: da Mer 07/02/2018 a Ven 09/02/2018
      • Gio 8/2/2018 ore 10.30 Lombardi-Grammatico (Polo Lodovici Ufficio Tesei)
      • Gio 8/2/2018 ore 11.00 Montecchiari (Polo Lodovici Ufficio Tesei)
    • Registrazione Esame (12 CFU): Lun 12/02/2018 previa iscrizione su ESSE3 al “VII Appello ASD” (prof.ssa Merelli)
  • Appello VIII
    • Prova Scritta di Teoria: 19/02/2018 - Iscrizione su ESSE3 (prof.ssa Merelli)
    • Consegna Progetto Totale di Laboratorio: entro Lun 19/02/2018 ore 23:59
    • Iscrizione su ESSE3 alla prova parziale “Progetto Lab - VIII Appello”: entro Lun 19/02/2018 ore 23:59
    • Pubblicazione Calendario Orali Laboratorio: Mar 20/02/2018 su questo sito e tramite Google Calendar
    • Orali Laboratorio: da Mer 21/02/2018 a Gio 22/02/2018
      • Gio 22/2/2018 ore 9.30 Montecchiari (Polo Lodovici Ufficio Tesei)
      • Gio 22/2/2018 ore 10.00 Doti-Bollici (Polo Lodovici Ufficio Tesei)
    • Registrazione Esame (12 CFU): Ven 23/02/2018 previa iscrizione su ESSE3 al “VIII Appello ASD” (prof.ssa Merelli)

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.