Codice insegnamento

4S02709

Docente

Roberto Segala

Coordinatore

Roberto Segala

Crediti

12

Offerto anche nei corsi:

• Algoritmi del corso Laurea in Matematica Applicata [L-35]

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

INF/01 - INFORMATICA

Periodo

II semestre, I semestre

Corsi Singoli

Autorizzato

Orario Lezioni Moodle Seminari 0

Obiettivi di apprendimento

Il corso si propone di fornire gli strumenti per la progettazione di soluzioni algoritmiche a problemi concreti, con particolare attenzione ai principali algoritmi di ordinamento, selezione, gestione code, visita grafi, cammini minimi alberi di copertura, flusso massimo. Fornire le tecniche di valutatazione e confronto di algoritmi in base alla quantità di risorse che richiedono.
Al termine dell'insegnamento, lo studente dovrà:
- Dimostrare di conoscere e comprendere i principali algoritmi per la risoluzione di problemi noti;
- Saper applicare le conoscenze acquisite per valutare e confrontare algoritmi sulla base della loro complessità computazionale;
- Essere in grado di scegliere autonomamente l'algoritmo più adatto ad una specifica situazione, anche in funzione della complessità di realizzazione;
- Saper argomentare in modo tecnico e preciso una specifica scelta algoritmica;
- Essere in grado di ampliare autonomamente le conoscenze al fine di comprendere soluzioni algoritmiche a nuovi problemi.

Prerequisiti e nozioni di base

Programmazione

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.

Bibliografia

Modalità didattiche

Lezioni in presenza ed esercitazioni

Modalità di verifica dell'apprendimento

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.

Criteri di valutazione

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)

Criteri di composizione del voto finale

Vedi modalità di esame

Lingua dell'esame

Italiano