Patrizia Scandurra


Informatica III-B
Progettazione e algoritmi
Docente: Patrizia Scandurra - Università degli Studi di Bergamo
a.a. 2012-13


Orario delle lezioni


Mercoledì: 8.30-10.30 aula 5

Venerdì: 14.00-17.00 aula 17



 

N.B.: Per comunicazioni relative alle lezioni, a date di appelli d'esame, ecc. consultare la sezione avvisi in fondo a questa pagina.

 



Presentazione del corso e modalità d'esame

L'esame consta di una prova scritta (che verte sulla parte di algoritmi e strutture dati) e di una prova orale (quest'ultima verte sulla discussione del progetto software da sviluppare). La consegna dei progetti (SW + documentazione) avrà luogo nella stessa data fissata per l'appello, ovvero occorre presentare il progetto UNITAMENTE alla prova scritta, indipendentemente dal superamento o meno di quest'ultima. La prova orale avrà luogo in una data successiva e solo se si è superata la prova scritta!

 

L'applicazione SW da sviluppare deve avere certe caratteristiche obbligatorie. Per maggiori dettagli (modalità d'esame, programma, ecc..) vedi la presentazione del corso: pdf



Prove d'esame e risultati

  • Esempio di compito 1
  • Esempio di compito 2
  • Pre-compitino del 21 Dicembre 2011: testo, soluzione e risultati (vedi ultima pagina del documento in pdf)
  • Altri testi di prove d'esame sono disponibili sul repository Dropbox.

 

  • Pre-compitino del 19 Dicembre 2012: Testo con soluzione e risultati.
  • Appello 14 Gennaio 2013: testo, soluzione e risultati



Programma

  • Progettazione in "piccolo": Analisi di dettaglio di ogni componente e definizione degli algoritmi.
    Argomenti: Introduzione agli algoritmi e strutture dati, ciclo di sviluppo di codice algoritmo, complessità del calcolo e notazione asintotica, realizzazione di algoritmi e tipi astratti di dati in Java, strutture dati e algoritmi fondamentali (liste, pile, code), algoritmi di ordinamento, alberi e loro gestione, alberi di ricerca (alberi binari di ricerca, B-trees), applicazioni degli alberi per il processamento di documenti XML, tabelle hash, grafi e loro rappresentazione e gestione, cammini minimi, metodologie di progettazione di algoritmi (incrementale,divide-et-impera,greedy,programmazione dinamica).
  • Progettazione in "grande": Si progetta ed analizza l'architettura del software per componenti funzionali e interazioni tra questi ultimi.
    Argomenti: processi di sviluppo agili, AMDD, specifica dei requisiti e modellazione dei casi d'uso, sviluppo del SW per componenti/oggetti, progettazione OO e delle componenti in UML, Service-Component Architecture (SCA), design pattern "a livello di architettura SW", sviluppo di componenti grafiche in Java, testing di unità delle componenti e copertura di una applicazione software, strumenti di analisi statica per il calcolo di metriche e per il re-factoring del SW.

 


Materiale didattico

Il materiale didattico/lucidi delle singole lezioni è disponibile su Dropbox! Il link della cartella condivisa è stato comunicato a lezione dal docente. Se lo avete smarrito, richiedetelo via e-mail al docente.

 

Lezioni in aula:

 

  • Lez1 26/09/2012: Introduzione al corso, introduzione alla progettazione in “piccolo” ed in “grande”, introduzione informale agli algoritmi. 26/09/2012

  • Lez2 28/09/2012: Complessità di un algoritmo e notazione asintotica, calcolo della complessità di un algoritmo, sommatorie, complessità di un problema, caso medio, migliore e peggiore, esercizi.

  • Lez3 05/10/2012: Analisi di algoritmi ricorsivi (tecnica di sostituzione, iterazione, teorema master), esercizi, strutture dati elementari (liste, pile, code), sorgentti Java per Coda e Albero Binario.

  • Lez4 11/10/2012: Alberi e visite, Alberi binari di ricerca (proprietà, ricerca, min e max, predecessore e successore, inserimento, cancellazione), codice sorgente Java per albero Binario di Ricerca.
  • Lez5 12/10/2012: Alberi binari perfettamente bilanciati (definizione APB), il problema dell'ordinamento basato su "confronti", Limite inferiore al problema dell’ordinamento basato su confronti, algoritmi di ordinamento elementari (InsertionSort, SelectionSort e BubbleSort) e la strategia di design incrementale.
  • Lez6 26/10/2012: Strategia di design dive-et-impera ed algoritmi di ordinamento ottimi (Mergesort e QuickSort), codice sorgente Java per MergeSort e QuickSort. Algoritmi di ordinamento lineari (Integersort,Bucketsort e RadixSort), codice sorgente Java per IntegerSort, B-albero (proprietà, ricerca, split/join, inserimento e cancellazione).
  • Lez7 09/11/2011: B-albero (continuazione lezione precedente), Tabelle hash, risoluzione delle collisioni (liste di collisione, indirizzamento aperto), tabelle hash nel JCF (Hashtable, HashMap e HashSet), overriding del metodo hashCode() della classe Java Object.
  • Lez8 16/11/2011: Altre strategie di design e limiti del divide-et-impera, programmazione dinamica ed esempi, strategia greedy ed esempi (sequenziamento, distributore automatico di resto), Grafi (definizioni).
  • Lez9 23/11/2012: Grafi (visite), Cammini minimi in un grafo: definizioni, tecnica del rilassamento e proprietà, algoritmo di Dijkstra da singola sorgente. Illustrazione esempi di compiti.
  • Lez10 30/11/2012: Processi di sviluppo agili, nozioni base sul testing e terminologia, il processo AMDD (Agile Model-Driven Development), analisisi dei requisiti e modellazione dei casi d'uso in UML.
  • Lez11 07/12/2012: il metodo Restricted Use Case Modeling (RUCM) e il caso di studio dell'ATM, Architetture SW, design a componenti e diagramma UML delle componenti e di deployment, caso di studio CoCoMe.
  • Lez12 14/12/2012: Design pattern architetturali, OO design pattern, illustrazione esempi di compiti.
  • Lez13: 19/12/2012: Pre-compitino, Approfondimenti diagrammi delle classi UML, presentazione tool UML Modelio, approfondimenti di analisi statica e metriche, programmazione orientata ai servizi e service-oriented computing, Service Component Architecture (SCA), caso di studio RESTAURANT.

     

Lezioni di laboratorio:

 

  • Lab1 03/10/2012: Sviluppo di codice algoritmico in Java, le API JFC (Java Foundation Classes), esercizi.
  • Lab2 10/10/2012: Esercizi su strutture dati elementari (Coda e Pila).
  • Lab3 17/10/2012: Processare documenti XML (alberi) con SAX e DOM, esercizi. By Andrea Luzzana
  • Lab4 24/10/2012: Esercizi alberi e alberi binari.
  • Lab5 31/10/2012: Esercizi su alberi binari di ricerca, ordinamento e divide-et-impera.
  • Lab6 07/11/2012: Java GUI (Parte 1). By Andrea Luzzana
  • Lab7 14/11/2012: Java GUI (Parte 2). By Andrea Luzzana
  • Lab8 21/11/2012: Esercizi su tabelle hash (classe Java Hashtable ed il metodo hashcode).
  • Lab9 28/11/2012: Java convention, Deployment (jar) e Subversioning, analisi statica del codice: metriche e refactoring. By Andrea Luzzana
  • Lab10 05/12/2012: Junit e ECLEMMA. By Andrea Luzzana
  • Lab11: 28/11/2012:Architettura SW: Caso di studio CoCoME (The Common Component Modelling Example). By Andrea Luzzana




Tool e tutorial di supporto allo sviluppo

Se siete interessati anche a visualizzare i grafi (ad es. per scopi di debugging dei vostri algoritmi): JGraph - the de facto Java Swing graph visualization library worldwide http://www.jgraph.com/

Altre API alternative: Jung, yworks e BFG



Libri di testo

C. Demetrescu, I. Finocchi, G. F. Italiano: Algoritmi e strutture dati, McGraw-Hill, ISBN: 978-88-386-6468-7, seconda edizione, Gennaio 2008
sito web

Per approfondimenti:

  • Introduzione agli algoritmi e strutture dati 3/ed - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
    Copyright © 2010 - The McGraw-Hill Companies
  • C.A.Shaffer: A practical Introduction to data structures and algorithm analysis.
    http://people.cs.vt.edu/~shaffer/Book/Java3e20100119.pdf
  • The Object Primer 3rd Edition: Agile Model Driven Development with UML 2, Cambridge University Press, 2004 ISBN 0-521-54018-6


Ricevimento

Su appuntamento o nel pomeriggio dopo le lezioni, Edificio B, terzo piano, ufficio 2



Avvisi

Inizio lezioni


26 Settembre 2012 8.30 – 10:30 aula 20
Recupero lezione


11 Ottobre 2012 9.30 – 12:30 aula 21