Patrizia Scandurra


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


Orario delle lezioni


Lunedì: 10.30-13.30 aula 5 Mercoledì: 9.30-11.30 aula 24



 

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
  • Appello 03 Febbraio 2014: 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.

 

Argomenti in dettaglio per lezione:

 

Lezioni in aula:

 

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

  • Lez2: 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: Analisi di algoritmi ricorsivi (tecnica di sostituzione, iterazione, teorema master), esercizi, strutture dati elementari (liste, pile, code), alberi (definizioni).

  • Lez4: Alberi e visite, Alberi binari di ricerca (proprietà, ricerca, min e max, predecessore e successore, inserimento, cancellazione),Alberi binari perfettamente bilanciati (definizione APB).
  • Lez5: 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. Strategia di design dive-et-impera ed algoritmi di ordinamento ottimi (Mergesort e QuickSort), codice sorgente Java per MergeSort e QuickSort.
  • Lez6: Algoritmi di ordinamento lineari (Integersort,Bucketsort e RadixSort), codice sorgente Java per IntegerSort, B-albero (proprietà, ricerca, split/join, inserimento e cancellazione).
  • Lez7: B-albero (cont.).
  • Lez8: 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.
  • Lez9: 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).
  • Lez10: Grafi (visite), Cammini minimi in un grafo: definizioni, tecnica del rilassamento e proprietà, algoritmo di Dijkstra da singola sorgente.
  • Lez11: Progettazione agile con AMDD, requisiti e casi d’uso UML, il metodo Restricted Use Case Modeling (RUCM) e il caso di studio dell'ATM.
  • Lez12: Architetture SW, design a componenti e diagramma UML delle componenti e di deployment, approfondimenti diagrammi delle classi UML, presentazione tool UML Modelio.
  • Lez13: Caso di studio CoCoME (The Common Component Modelling Example) (aspetti teorici ed implementativi in Java dell'architettura SW).
  • Lez14: Design pattern architetturali.
  • Lez 15: Illustrazione esempi di compiti, Service oriented computing, SCA, caso di studio RESTAURANT.
  • Lez 16: Analisi statica e metriche.

     

Lezioni di laboratorio:

 

  • Lab1: Sviluppo di codice algoritmico in Java, le API JFC (Java Foundation Classes), esercizi.
  • Lab2: Esercizi su strutture dati elementari (Coda e Pila).
  • Lab3: Processare documenti XML (alberi) con SAX e DOM, esercizi. By Paolo Vavassori
  • Lab4: Esercizi alberi e alberi binari.
  • Lab5: Esercizi su alberi binari di ricerca, ordinamento e divide-et-impera.
  • Lab6: Java convention, Deployment (jar) e Subversioning, Java GUI (Parte 1). By Paolo Vavassori
  • Lab7: Java GUI (Parte 2). By Paolo Vavassori
  • Lab8: Esercizi su tabelle hash (classe Java Hashtable ed il metodo hashcode).
  • Lab9: Analisi statica del codice con Code Pro by Google: metriche e refactoring, Junit e ECLEMMA. By Paolo Vavassori




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 dopo le lezioni, Edificio B, terzo piano



Avvisi

Inizio lezioni


23 Settembre 2013 10.30 – 13:30 aula 9