Corso di Algoritmi & Laboratorio

Laurea in Informatica - percorso SR

Anno accademico: 2008-2009

Docenti: Elio Giovannetti, András Horváth

Numero di ore: 54 (in aula) + 72 (in laboratorio)
Numero di CFU (Crediti Formativi Universitari): 6 (in aula) + 6 (in laboratorio)

INDICE

1. Obiettivi del corso
2. Competenze attese e propedeuticità
3. Come si svolgono le lezioni e le esercitazioni.
4. Programma/contenuti
5. Materiale didattico di supporto (a cura del docente)
6. Bibliografia (libri, articoli, documenti on-line,...)
7. Controllo dell'apprendimento (durante il corso)
8. Verifica (modalità d'esame)
9. CORSO ON-LINE (I-learn = io-imparo): è necessario iscriversi per poter seguire il corso dall'inizio e frequentare il laboratorio.

1. Obiettivi del corso

Il corso ha lo scopo di fornire gli strumenti metodologici di base per il progetto, l'analisi ed il confronto di algoritmi e di introdurre alcuni algoritmi e strutture dati fondamentali. L'attività di laboratorio è strettamente integrata con le lezioni, e permetterà di mostrare come i linguaggi imperativi tipati object-oriented class-based, fra cui Java, siano particolarmente indicati per realizzare pacchetti software che implementino algoritmi e strutture dati.

2. Competenze attese e propedeuticità

• Competenze attese in ingresso (richieste all'inizio del corso). Conoscenza delle basi della programmazione imperativa in C, delle basi della programmazione orientata agli oggetti in Java, e del concetto di ricorsione.
• Eventuali corsi propedeutici (forniscono le "competenze attese in ingresso"). Programmazione I & Laboratorio, Programmazione II & Laboratorio, Laboratorio di linguaggi, Matematica Discreta, Analisi Matematica, Logica Matematica.
• Competenze attese in uscita (acquisite durante il corso). Al termine del corso ci si aspetta che lo studente sia in grado di realizzare pacchetti software che supportino le strutture dati fondamentali e i relativi algoritmi sfruttando al meglio le caratteristiche proprie dei linguaggi imperativi tipati object-oriented class-based e utilizzando, in modo opportuno, classi e interfacce della libreria standard Java.

3. Come si svolgono le lezioni e le esercitazioni.

Le lezioni in aula si svolgono con l'ausilio del calcolatore e del proiettore (lucidi, esecuzione di programmi, ecc), integrati, quando opportuno, con l'uso di gesso e lavagna. Esse vengono condotte, per quanto possibile, in modo interattivo, sollecitando la partecipazione attiva degli studenti.

Le esercitazioni di laboratorio sono parte integrante del corso e si svolgono nel laboratorio Dijkstra. Gli studenti devono iscriversi ad uno dei due turni di laboratorio, individualmente oppure a gruppi di 2 persone. L'iscrizione potrà essere effettuata durante la prima lezione, oppure successivamente sul sito i-learn del corso..

4. Programma di massima.

• Ripasso del meccanismo della compilazione separata nel linguaggio C.
• Ripasso di alcune caratteristiche del linguaggio Java (interfacce, polimorfismo, ereditarieta', classi astratte, eccezioni).
• Problemi e algoritmi.
  
  • Problemi algoritmici e algoritmi.
  • Problemi non risolubili: indecidibilità del problema della fermata.
• Correttezza degli algoritmi.
  
  • Principio di induzione matematica semplice e di induzione completa.
  • Invariante di ciclo e suo uso nelle dimostrazioni di correttezza degli algoritmi iterativi.
  • Dimostrazioni di correttezza dell'esponenziale veloce e della ricerca binaria iterativa.
  • Correttezza degli algoritmi ricorsivi.
• Complessità computazionale.
  
  • Andamento asintotico di funzioni, e notazione O, Ω, Θ.
  • Complessità (temporale e spaziale) di algoritmi e complessità di problemi.
  • Classi di complessità, problemi e algoritmi trattabili e intrattabili.
  • Problemi "probabilmente" non risolubili in modo efficiente.
• Esempi di problemi e algoritmi.
  
  • Il problema della bandiera tricolore.
  • Il problema del segmento di somma massima: soluzioni, complessità, varianti del problema.
  • Il problema delle torri di Hanoi.
  • La sequenza di Fibonacci.
• Complessità degli algoritmi ricorsivi e equazioni di ricorrenza.
  
  • Scrittura delle equazioni di ricorrenza per un algoritmo ricorsivo e risoluzione per sviluppo (unfolding).
  • Algoritmi divide-et-impera e teorema principale delle ricorrenze.
  • Algoritmi divide-et-impera e teorema principale delle ricorrenze.
• Algoritmi divide-et-impera.
  
  • Moltiplicazione di matrici.
  • Moltiplicazione di interi di grandezza arbitraria.
  • Altri algoritmi.
• Strutture-dati e tipi astratti.
  
  • Strutture-dati, tipi astratti, rappresentazione di un tipo astratto mediante una struttura, invarianti di struttura, invarianti di rappresentazione.
  • Tipi astratti e strutture-dati in C.
  • Tipi astratti e strutture-dati nella programmazione a oggetti (Java).
  • Tipi generici.
  • Sequenze, array, liste concatenate, pile, code, realizzazione della coda per mezzo di array circolare.
  • Alberi. Alberi binari. Visite di alberi per profondità (ricorsive e semiricorsive).
  • Visite completamente iterative di alberi, per profondità e per larghezza.
• Code con priorità e heap.
• Il problema dell'ordinamento e gli algoritmi di ordinamento.
  
  • Delimitazione inferiore della complessità del problema dell'ordinamento per soli confronti.
  • Proprietà di algoritmi di ordinamento: stabilità, ordinamento sul posto.
  • Ripasso lgoritmi di ordinamento elementari: selection sort, insertion sort.
  • Algoritmi di ordinamento ottimi: mergesort, heapsort.
  • Quicksort: versioni diverse.
  • Un problema affine: il problema della selezione (ricerca dell'elemento di rango k in una sequenza).
• Algoritmi di ordinamento lineari (non per confronti).
  
  • Ordinamento per conteggio: integer sort, counting sort, radix sort, bucket sort.
• Dizionari, alberi di ricerca, tabelle hash.
  
  • Il tipo astratto Dizionario e le sue realizzazioni per mezzo di array e di liste, confronto fra complessità.
  • Alberi di ricerca binari: generi diversi di realizzazione, implementazioni diverse in C e in Java.
  • Alberi bilanciati, alberi AVL, e loro realizzazione.
  • Alberi due-tre e B-alberi.
  • Dizionari realizzati come tabelle hash. Funzioni di hash, risoluzione delle collisioni (indirizzamento aperto e indirizzamento chiuso).
• Realizzazione, utilizzando la libreria standard Java, di tipi di dati astratti (Pila, Coda, Lista, Insieme, Bag, Mappa, Coda con priorita') e strutture dati (array, lista concatenata, albero binario di ricerca, tabella hash, heap).
• Strutture union-find.
  
  • Quick-find, quick-union.
  • Unione per dimensione, unione per altezza, compressione dei cammini.
  • Calcolo della complessità.
• Programmazione dinamica.
  
  • Il problema della più lunga sottosequenza comune.
  • Il problema della minima distanza fra stringhe.
  • Altri algoritmi.
• Programmazione greedy.
  
  • Codifica di Huffman e compressione di files.
  • Altri algoritmi.
• Grafi
  
  • Rappresentazione dei grafi.
  • Visite in ampiezza e profondità.
  • Componenti fortemente connesse.
  • Minimo albero di copertura.
  • Cammini minimi.



5. Materiale didattico di supporto.


This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.

Il materiale didattico per l'a.a. 2008-09 sarà reso via via disponibile tramite il CORSO ON-LINE.


6. Bibliografia (libri, articoli, documenti on-line,...)

• Demetrescu, Ferraro Petrillo, Finocchi, Italiano
  Progetto di algoritmi e strutture dati in Java.
  McGraw-Hill, 2007.

• Crescenzi, Gambosi, Grossi
  Strutture di dati e algoritmi
  Pearson Addison-Wesley, 2006.

• utilissimo per il laboratorio:
  Horstmann
  Big Java
  2nd Edition
  John Wiley & Sons, 2006.
  

  traduzione italiana parziale (i capitoli non tradotti non riguardano argomenti del corso):
  Horstmann
  Concetti di informatica e fondamenti di Java
  Terza Edizione
  Apogeo
  Prezzo: Euro 45,00
  sconto 15% Apogeonline Euro 38,25

• Goodrich, Tamassia
  Data Structures and Algorithms in Java
  4th Edition
  John Wiley & Sons, 2006.

7. Controllo dell'apprendimento (durante il corso)

Il controllo dell'apprendimento viene effettuato dai docenti in aula attraverso domande agli studenti, discussioni, svolgimento di esercitazioni al posto e alla lavagna; in laboratorio attraverso il monitoraggio dell'attività e test al calcolatore.


8. Verifica (modalità d'esame)

L'esame è costituito di tre parti: (1) una verifica scritta che riguarda gli argomenti presentati durante le lezioni in aula, (2) una discussione dell'attività di laboratorio effettuata dal candidato (realizzazioni di progetti ed esecuzione di esercizi) e (3) un breve colloquio di carattere generale, comprendente una discussione della verifica scritta e dei "compiti" assegnati dal docente durante le lezioni in aula. Le prove (1) e (2) possono essere superate (ottenendo una valutazione sufficiente) in qualunque ordine (anche in appelli diversi). La validità di tali prove è limitata al corrente anno accademico (cioè le prove non valgono più a partire dal primo appello del corso tenuto nell'anno accademico successivo). Eventuali deroghe (in seguito a gravi e giustificati motivi) potranno essere concordate con il docente prima dell'ultimo appello utile.

Il colloquio (3) può essere sostenuto solo DOPO AVER SUPERATO entrambe le prove (1) e (2), subito prima della registrazione del voto. In linea di massima, il voto finale è ottenuto come media dei voti dello scritto e del laboratorio, che devono essere entrambi sufficienti; tuttavia l'esito del colloquio (3) può in qualche caso modificare, anche di molto, tale valore (in casi-limite, potrebbe anche risultare nel non superamento dell'esame).



Mi dispiace ...
ma la pagina che hai richiesto non è stata trovata.
Torna indietro | Vai alla Homepage
Università degli Studi di Torino - Via Verdi, 8 - 10124 Torino