Contenuti del corso

Questo corso si compone di due parti che saranno portate avanti parallelamanete.

La prima, di circa 60 ore, si occuperà della descrizione e progettazione di algoritmi efficienti; la seconda, di circa 30 ore, si occuperà di programmazione.

Descrizione e progettazione di algoritmi efficienti

• Introduzione

  • Concetti di algoritmo, di struttura dati, di efficienza; di complessita' computazionale;

  • modello RAM; misura di costo uniforme e logaritmico.

• Notazione asintotica

  • Definizione e significato degli insiemi O, Ω e Θ

• Il problema della ricerca

  • Ricerca sequenziale in un vettore disordinato;

  • complessita' nel caso migliore, peggiore e medio

  • Ricerca dicotomica o binaria in un vettore ordinato (vers. iterativa)

  • complessita' nel caso migliore, peggiore e medio

• Introduzione alla ricorsione

  • funzioni ricorsive

  • versione iterativa e ricorsiva di algoritmi: esempi

  • occupazione in memoria: l'esempio del calcolo dei numeri di Fibonacci

  • calcolo della complessita' delle funzioni ricorsive tramite equazioni di ricorrenza

    • metodo di sostituzione

    • metodo iterativo

    • metodo dell'albero

    • teorema principale (senza dimostrazione)

• Il problema dell'ordinamento:

  • algoritmi naif: filosofia, codice e complessita'

  • limitazione inferiore sulla complessita' degli ordinamenti per confronti; dimostrazione

  • funzione di fusione e merge sort; cenno alla tecnica del divide et impera

  • quick sort e sua complessita' nel caso peggiore, migliore e medio

  • heap e heap sort

  • ordinamento in tempo lineare: counting sort

• Strutture dati fondamentali

  • insiemi dinamici ed operazioni su di essi

  • vettore non ordinato e ordinato

  • lista semplice e doppiamente puntata

  • pila e coda, funzioni di inserimento ed estrazione, coda circolare

  • coda con priorità

  • albero

    • definizione come grafo connesso aciclico

    • teorema di caratterizzazione degli alberi

    • alberi radicati, alberi binari, alberi binari completi

    • relazioni tra numero di nodi interni, numero di foglie ed altezza in un albero binario completo

    • rappresentazione in memoria di un albero binario

      • rappresentazione posizionale

      • rappresentazione con puntatori

      • vettore dei padri

    • visita in pre-, post- ed in-ordine e calcolo della complessita' tramite equazione di ricorrenza

• Dizionari

  • indirizzamento diretto

  • tabelle hash

    • scansione lineare

    • scansione quadratica

    • hashing doppio e relative prestazioni (senza dimostrazione)

  • alberi binari di ricerca

    • definizione

    • algoritmo di ricerca e sua complessita'

    • algoritmo di inserimento e sua complessita'

    • algoritmi di ricerca del massimo, minimo, successore e predecessore e loro complessita'

    • algoritmo di cancellazione e sua complessita'

  • la problematica del bilanciamento (alberi red-black)

    • rotazioni e cambi di colore

    • complessità del bilanciamento

• Grafi

  • rappresentazione in memoria

    • liste di adiacenza

    • matrice di adiacenza

    • matrice di incidenza

    • lista di archi

    • confronto della complessita' spaziale e temporale in alcune operazioni elementari

  • visita in ampiezza (BFS)

    • definizione di albero ricoprente

    • proprietà degli archi non dell'albero

    • proprieta' della distanza dalla radice

  • visita in profondita' (DFS)

    • proprietà degli archi non dell'albero

    • proprieta' del numero di archi in funzione della lunghezza del cammino più lungo

  • similitudini e differenze tra le due visite

  • loro complessita' al variare della struttura dati usata

  • Algoritmo di Dijkstra per il calcolo dei cammini minimi

    • funzionamento

    • pseudocodice

    • complessità

    • dimostrazione della correttezza

Programmazione

Per i contenuti di questa parte si vedano le informazioni fornite dal prof. Franceschini su questo sito.