Laboratorio di Algoritmi e Strutture Dati

News

  • 9 Giugno 2016: Il corso termina con le presentazioni di argomenti non trattati a lezione da parte di alcuni studenti
  • 3 Marzo 2016: Il modulo inizia alle ore 10.00 in Aula “A. Turing” del palazzo di Informatica (ex-tribunale), per la mappa delle aule si veda qui

Informazioni Generali

Docente:

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

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

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

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