Algoritmi e strutture dati - Teoria (2007/2008)

Corso a esaurimento

Codice insegnamento
4S00013
Docente
Alessandra Di Pierro
crediti
8
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Periodo
1° Q, 2° Q

Per visualizzare la struttura dell'insegnamento a cui questo modulo appartiene, consultare * organizzazione dell'insegnamento

Orario lezioni

1° Q
Giorno Ora Tipo Luogo Note
lunedì 10.30 - 12.30 lezione Aula A  
martedì 10.30 - 12.30 lezione Aula E  
2° Q
Giorno Ora Tipo Luogo Note
lunedì 10.30 - 12.30 lezione Aula B  
martedì 10.30 - 12.30 lezione Aula C  

Obiettivi formativi

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. In particolare, si prendono in considerazione alcuni dei problemi di primaria importanza nella biologia molecolare. Nel corso si introducono inoltre 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.

Programma

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

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

-Algoritmi di `matching' esatto su stringhe.

-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.

-Algoritmi per la costruzione di `suffix trees'.

-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, problemi NP-completi, teorema di Cook-Levin.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Crescenzi, P. - Gambosi, G. - Grossi, R. Strutture di Dati e Algoritmi Pearson Education Italia 2006 8871922735

Modalità d'esame

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.

Materiale didattico

Documenti