Corso di
Algoritmi & Laboratorio
Laurea in Informatica - percorso SR
Anno accademico: 2007-2008
Numero di ore:
54 (in aula) + 72 (in laboratorio)
Numero di CFU (Crediti Formativi Universitari):
6 (in aula) + 6 (in laboratorio)
INDICE
-
Obiettivi del corso
-
Competenze attese e propedeuticità
-
Come si svolgono le lezioni e le esercitazioni.
-
Programma/contenuti
-
Materiale didattico di supporto (a cura del docente)
-
Bibliografia (libri, articoli, documenti on-line,...)
-
Controllo dell'apprendimento (durante il corso)
-
Verifica (modalità d'esame)
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 tramite apposito modulo che sarà reso scaricabile
da questa pagina.
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, W, Θ.
- 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.
Il materiale didattico per l'a.a. 2007-08 sarà
via via disponibile nel
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).
[Guida
ufficiale del corso] (contiene le stesse informazioni riportate, in maggior dettaglio, in questa pagina).
404 File not found
Mi dispiace ...
ma la pagina che hai richiesto non è stata trovata.