Patrizia Scandurra


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


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 data fissata per l'appello; la vera prova orale avrà luogo in una data successiva 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

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

 



Programma

  • Progettazione in "grande": Si analizza la suddivisione del software per componenti funzionali e lo scambio dati tra questi ultimi.
    Argomenti: processi di sviluppo agili, AMDD, gestione 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 per il calcolo di metriche e per il re factoring del SW.
  • 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).

 


Materiale didattico

  • ven 30 Set 2011 14:00 – 17.00 - aula 17
    Introduzione al corso, introduzione alla progettazione in “piccolo” ed in “grande”, introduzione informale agli algoritmi
    Vedi contenuti:

  • mer 5 Ott 2011 8.30 – 10.30 - aula 18
    Complessità di un algoritmo e notazione asintotica, calcolo della complessità di un algoritmo, esercizi
    vedi contenuti (unico zip):

  • ven 7 Ott 2011 14.00-17.00 - aula 17
    Sommatorie, complessità di un problema, caso medio, migliore e peggiore, analisi di algoritmi ricorsivi (tecnica di sostituzione, iterazione, teorema master), esercizi.
    Vedi contenuti:

  • mer 12 Ott 2011 8.30 – 10.30 - aula 5
    Sviluppo di codice algoritmico in Java, le API JFC (Java Foundation Classes), esercizi.
    Vedi contenuti:
    Vedi soluzioni esercizi     by E. Bacis:

  • ven 14 Ott 2011 14:00 – 17:00 - aula 17
    Strutture dati elementari (liste, pile, code), alberi e proprietà, sorgentti Java per Coda e Albero Binario

    Vedi contenuti:

 

  • mer 19 Ott 2011 8.30 – 10.30 - aula 5
    Valutazioni espressioni aritmetiche e notazioni (infisse, postfisse e prefisse), esercizi su strutture dati elementari (Stack).
    Vedi contenuti: Vedi soluzioni esercizi by Bacis & Santini, Sangregorio & Carminati:

  • ven 21 Ott 2011 14.00-17.00 - aula 17
    Alberi e visite (vedi lezione di venerdì 14 Ott), alberi binari di ricerca (proprietà, ricerca, min e max, predecessore e successore, inserimento, cancellazione), codice sorgente Java per albero Binario di Ricerca.
    Vedi contenuti:

     

  • mer 26 Ott 2011 8.30 – 10.30 - aula 5
    Esercizi su strutture dati elementari (alberi binari).
    Vedi contenuti:

 

  • ven 28 Ott 2011 14.00-17.00 - aula 17
    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, strategia di design dive-et-impera ed algoritmi di ordinamento ottimi (Mergesort e QuickSort), codice sorgente Java per MergeSort e QuickSort.
    Vedi contenuti:

 

  • mer 2 Nov 2011 8.30 – 10.30 - aula 5
    Sviluppo di Java GUI (Parte 1): Introduzione a JFC/Swing, Frame, Java 2D, la gestione eventi, Model-View-Controller (MVC), componenti Swing di base
    Vedi contenuti:

 

  • mer 2 Nov 2011 11.30 – 14.00 - aula 5
    Seminario sul cloud Computing by Paolo Tortiglione -- CONNET Consulting

 

  • ven 4 Nov 2011 14.00-17.00 - aula 17
    Algoritmi di ordinamento lineari (Integersort,Bucketsort e RadixSort), codice sorgente Java per IntegerSort (vedi lucidi della lezione del 28 Ott), B-albero (proprietà, ricerca, split/join, inserimento e cancellazione).
    Vedi contenuti:

     

  • mer 9 Nov 2011 8.30 – 10.30 - aula 5
    Esercizi su alberi binari di ricerca e ordinamento
    Vedi contenuti:


  • ven 11 Nov 2011 14.00-17.00 - aula 17
    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.
    Vedi contenuti:

  • mer 16 Nov 2011 8.30 – 10.30 - aula 5
    Sviluppo di Java GUI (Parte 2): MVC ed il design pattern observer/observable, editor di interfacce grafiche (Jigloo, Window builder)
    Vedi contenuti: e per un tutorial su Windowbuilder


  • ven 18 Nov 2011 14.00-17.00 - aula 17
    Altre strategie di design e limiti del divide-et-impera, strategia greedy ed esempi (sequenziamento, distributore automatico di resto), Grafi (definizioni e visite)
    Vedi contenuti:

  • mer 23 Nov 2011 8.30 – 10.30 - aula 5
    Esercitazione tabelle hash
    Vedi contenuti:


  • ven 25 Nov 2011 14.00-17.00 - aula 17
    Esempio di compito
    Cammini minimi in un grafo: definizioni, tecnica del rilassamento e proprietà, algoritmo di Dijkstra da singola sorgente.
    Vedi contenuti:

  • mer 30 Nov 2011 8.30 – 10.30 - aula 5
    Processare documenti XML con l'approccio SAX, le API JAXP, esercizio
    Vedi contenuti:

  • ven 2 Dic 2011 14.00-17.00 - aula 20
    Processi di sviluppo agili, il processo AMDD (Agile Model-Driven Development), analisisi dei requisiti e modellazione dei casi d'uso in UML.
    Vedi contenuti:
    Restricted Use Case Modeling (RUCM): caso di studio dell'ATM (dalla tesi di Laurea Specialistica Arnoldi-Dolci UN AMBIENTE PER LA PROTOTIPAZIONE AUTOMATICA E LA VALIDAZIONE DEI REQUISITI SOFTWARE, Luglio 2011).

  • mer 7 Dic 2011 9.00 – 11.00 - aula 5
    Processare documenti XML con l'approccio DOM, le API JAXP, esercizio
    Vedi contenuti:

  • ven 9 Dic 2011 14.00-17.00 - aula 17
    Design dell'architettura software: component-based development, diagramma UML delle componenti/classi/deployment. Vedi contenuti:
    Programmazione orientata ai servizi, Service Component Architecture (SCA). Vedi contenuti:


  • mer 14 Dic 2011 8.30 – 11.30 - aula 5
    Testing di unità in Java, il framework Junit per l'automazione. Vedi contenuti:
    Analisi statica, metriche e refactoring. Vedi contenuti:

  • mar 20 Dic 2011 - aula 5
    Logging, subversion e deployment di applicazioni Java. Vedi contenuti:


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


30 Settembre 2011 14.00 – 17:00 aula 17


Seminario sul Cloud Computing
by Paolo Tortiglione -- CONNET Consulting


2 Novembre 2011, alle 11.30 aula 21


Pre-compitino


21 dicembre 2011, alle 10.30