Algoritmi e strutture dati (2008/2009)

Corso a esaurimento

Codice insegnamento
4S00013
Crediti
10
Coordinatore
Alessandra Di Pierro
L'insegnamento è organizzato come segue:
Modulo Crediti Settore disciplinare Periodo Docenti
Laboratorio 2 INF/01-INFORMATICA 1° Q, 2° Q Manuele Bicego
Teoria 8 INF/01-INFORMATICA 1° Q, 2° Q Alessandra Di Pierro

Obiettivi formativi

Modulo: Teoria
-------
Il corso e' incentrato sullo studio dei problemi computazionali. Tale studio permette di esplorare le possibilita' offerte dal calcolatore per la risoluzione di problemi reali attraverso la scelta degli algoritmi piu' adatti. Nel corso si introducono i principi matematici per l'analisi e per il confronto delle varie soluzioni algoritmiche rispetto alla loro efficienza. Parte integrante del corso e' lo studio delle strutture matematiche necessarie per rappresentare i dati dei problemi concreti nel mondo virtuale del calcolatore.

Nel corso di laboratorio vengono raffinate le conoscenze dello studente circa la pratica della programmazione a oggetti, soprattutto nell'implementazione di algoritmi e strutture dati avanzate. Le lezioni sono svolte in linguaggio Java di cui si assume una conoscenza di base.


Modulo: Laboratorio
-------
Nel corso di laboratorio di Algoritmi e Strutture Dati vengono raffinate le conoscenze dello studente circa la pratica della programmazione ad oggetti, soprattutto nell'implementazione di algoritmi e strutture dati avanzate. Le lezioni sono svolte in linguaggio Java di cui si assume una conoscenza di base.

Programma

Modulo: Teoria
-------
-Problemi computazionali: indecidibilita', trattabilita', modello di calcolo e complessita' computazionale.

-Analisi degli algoritmi, notazione asintotica.

-Array e liste: ricerca binaria, ricorsione, liste doppie e circolari.

-Alberi: algoritmi ricorsivi su alberi binari, inserimento e cancellazione, visita per ampiezza e rappresentazione di alberi.

-Dizionari: alberi binari di ricerca, alberi binari di ricerca bilanciati.

-Programmazione dinamica e algoritmi golosi.

-Grafi: problemi su grafi, rappresentazione di grafi, cammini minimi.

-Pile e code: implementazione, visite di grafi.

-Code con priorita': heap, implementazione, costruzione e ordinamento.

-NP-completezza: riducibilita' polinomiale e problemi NP-completi.


Modulo: Laboratorio
-------
Lezione 1: Uso del meccanismo dell'Interfaccia. Esempio di applicazione con l'implementazione dell'ADT Lista, Coda e Pila.

Lezione 2: Uso dell'interfaccia Comparable. Implementazione degli algoritmi di ordinamento per inserimento (InsertionSort) e per passo calante (ShellSort).

Lezione 3: Tecniche di confronto di implementazioni. Confronto tra due implementazioni di algoritmi di ordinamento: QuickSort e MergeSort.

Lezione 4: Richiamo dei concetti relativi al Javadoc e alle Eccezioni. Implementazioni dell'ADT Albero e Albero di ricerca binario.

Lezione 5: Uso dell'interfaccia Iterator. Implementazioni metodi di visita alberi. Cenni ad algoritmi di costruzione di "suffix tree".

Lezione 6: Implementazione di un algoritmo di programmazione dinamica: ricerca massima sottosequenza comune (MaxSSC).

Lezione 7: Algoritmi per il "matching" esatto di stringhe.

Lezione 8: Implementazione di un algoritmo greedy: algoritmo di Kruskal.

Modalità d'esame

Modulo: Teoria
-------
L'esame e' articolato su due parti relative al modulo di teoria e al modulo di laboratorio rispettivamente. La parte di teoria consiste in un'esercitazione scritta di due ore e viene superata solo se la votazione ottenuta e' superiore o uguale a 18/30. La parte di laboratorio consiste in un'esercitazione scritta di 1 ora e viene superata solo se la votazione ottenuta e' superiore o uguale a 18/30.
L'esame si intende superato se il candidato ha superato sia la prova relativa al modulo di teoria sia quella relativa al modulo di laboratorio. Il voto (unico) finale viene calcolato come media tra i voti dei due moduli di teoria e laboratorio pesati rispettivamente 4/5 e 1/5.


Modulo: Laboratorio
-------
L'esame e' articolato su due parti relative al modulo di teoria e al modulo di laboratorio. La parte di teoria consiste in un'esercitazione scritta di due ore e viene superata solo se la votazione ottenuta e' superiore o uguale a 18/30. La parte di laboratorio consiste in un'esercitazione scritta di un'ora e viene superata solo se la votazione ottenuta e' superiore o uguale a 18/30.

L'esame si intende superato se il candidato ha superato sia la prova relativa al modulo di teoria sia quella relativa al modulo di laboratorio. Il voto (unico) finale viene calcolato come media tra i voti dei due moduli di teoria e laboratorio pesati rispettivamente 4/5 e 1/5.

Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

Statistiche esiti
Esiti Esami Esiti Percentuali Media voti Deviazione Standard
Positivi 37.73% 24 3
Respinti 11.32%
Assenti 50.94%
Ritirati --
Annullati --
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
0.0% 7.5% 7.5% 10.0% 15.0% 12.5% 12.5% 2.5% 2.5% 2.5% 7.5% 10.0% 7.5% 2.5%

Valori relativi all'AA 2008/2009 calcolati su un totale di 106 iscritti. I valori in percentuale sono arrotondati al numero intero più vicino.