ContenutiDelCorso < Infogen

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