- Docente: Alan Albert Bertossi
- Crediti formativi: 12
- SSD: INF/01
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Bologna
- Corso: Laurea in Informatica (cod. 8009)
Conoscenze e abilità da conseguire
Al termine del corso, lo studente: - conosce gli algoritmi per risolvere problemi computazionali di base su strutture di dati elementari; - conosce le tecniche di base per calcolare il costo computazionale degli algoritmi; - conosce le classi di complessità computazionale P, NP e NP-hard; - è in grado di progettare algoritmi efficienti per risolvere semplici problemi computazionali; - è in grado di stimare in ordine di grandezza il costo computazionale degli algoritmi; - è in grado di analizzare la complessità computazionale di problemi computazionali di base; - è in grado di dare una valutazione circa l'efficienza e la correttezza di un algoritmo; - è capace di elaborare e di presentare un progetto per la risoluzione di problemi computazionali di base.
Contenuti
Progettazione e analisi di algoritmi.
Complessita' computazionale. Ordini di grandezza. Equazioni di
ricorrenza lineari di ordine costante e con partizione bilanciata.
Limitazioni inferiori.
Strutture di dati. Vettori, record e matrici. Liste, pile e code. Alberi. Visite di alberi (anticipata, simmetrica, differita, per livelli.) Insiemi. Dizionari. Ricerca binaria e per interpolazione. Tabelle hash. Code con priorita'. Heap. Alberi bilanciati di ricerca. Alberi red-black. MFSET. Grafi. Visite DFS e BFS.
Tecniche di progettazione: divide-et-impera, backtrack, greedy, ricerca locale, programmazione dinamica, randomizzazione.
Algoritmi di ordinamento: Mergesort,
Countingsort, Heapsort, Quicksort, Shellsort.
Complessita'. Le classi P ed NP. NP-completezza. Algoritmi pseudo-polinomiali, di approssimazione, branch-&-bound, ed euristici.
Testi/Bibliografia
A.A. Bertossi & A. Montresor, Algoritmi e Strutture di Dati, Citta' Studi Edizioni, Torino, 2010
Metodi didattici
lezioni, esercitazioni
Modalità di verifica e valutazione dell'apprendimento
esame finale scritto
Strumenti a supporto della didattica
lavagna luminosa
Link ad altre eventuali informazioni
http://www.cs.unibo.it/~bertossi
Orario di ricevimento
Consulta il sito web di Alan Albert Bertossi