Algoritmi (2018/2019)

Codice insegnamento
4S02709
Docente
Roberto Segala
Coordinatore
Roberto Segala
crediti
12
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Periodo
II semestre, I semestre

Orario lezioni

Vai all'orario delle lezioni

Obiettivi formativi

Il corso si propone di fornire gli strumenti fondamentali per la progettazione di soluzioni algoritmiche a problemi concreti. Gli algoritmi
vengono valutati e confrontati in base alla quantità di risorse che richiedono. Al termine del corso lo studente dovrà dimostrare di avere conoscenze e capacità di comprensione degli algoritmi principali per i problemi di ordinamento, selezione, gestione di code con priorità, visita di grafi, cammini minimi, alberi di copertura, flusso massimo; avere capacità di applicare le conoscenze acquisite e capacità di comprensione per confrontare algoritmi sulla base della loro complessità; saper scegliere autonomamente l'algoritmo più adatto ad una specifica situazione; saper sviluppare le competenze necessarie per ampliare autonomamente le conoscenze apprese al fine to comprendere soluzioni algoritmiche a nuovi problemi.

Programma

Complessità: complessità degli algoritmi, notazione asintotica, metodi di risoluzione delle equazioni di ricorrenza. Ordinamento e selezione: richiamo di insertion sort, richiamo di merge sort, heap sort, quick
sort, quick sort probabilistico. Algoritmi lineari, counting sort, radix sort, bucket sort. Algoritmi di Selezione.
Strutture dati: heap, alberi binari di ricerca, alberi RB, B-alberi heap binomiali, tabelle hash, code con priorita`
insiemi disgiunti, tecniche di estensione di una struttura dati, grafi.
Progetto ed analisi di algoritmi: divide et impera, greedy, programmazione dinamica, ricerca locale, backtracking
e branch and bound.
Algoritmi fondamentali: alberi di copertura di costo minimo (Prim e Kruskal), programmazione lineare (simplesso
e cenno all'algoritmo polinomiale basato sugli ellissoidi) cammini minimi a sorgente singola (Dijkstra e Bellman-
Ford) e multipla (Floyd-Warshall e Johnson), flusso massimo (Ford-Fulkerson, Karp), matching massimale su
grafo bipartito.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
T. Cormen, C. Leiserson, R. Rivest, C. Stein Introduzione agli Algoritmi e Strutture Dati (Edizione 2) McGraw-Hill 2005 88-386-6251-7

Modalità d'esame

L'esame consiste in una prova scritta di tre ore, suddivisa in due parti, e di un eventuale colloquio orale.

La prima parte della prova scritta è un test a risposte multiple e viene valutata con un punteggio tra 0 e 30. Chi ottiene una valutazione inferiore a 18 è respinto, mentre chi ottiene una valutazione compresa tra 18 e 23 termina l'esame. La seconda parte della prova scritta, alla quale si è ammessi ottenendo una valutazione di almeno 24 nella prima parte, consiste di uno o più esercizi di difficoltà crescente. Viene valutata con un punteggio tra 24 e 30.

La prova orale, facoltativa, è riservata a chi ottiene almeno 27 punti nella seconda parte della prova scritta.

La scala della valutazione finale è la seguente. 18-21 (conoscenza puramente nozionistica), 22-24 (comprensione accettabile degli argomenti), 25-27 (capacità di applicare i concetti appresi), 28-30 (capacità di elaborare idee proprie sulla base dei concetti appresi)

Opinione studenti frequentanti - 2017/2018