ContenutiDelCorso < Infogen

Tags: view all tags

---+++ <font color="990000" size="+2">Contenuti del corso</font>

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*.

---+++ <font color="990000" size="+1"> Descrizione e progettazione di algoritmi efficienti</font>
   * 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, &Omega; e &Theta;
   * 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
      * [[http://twiki.dsi.uniroma1.it/pub/Infogen/DispenseELibriDiTesto/Dijkstra.pdf][Algoritmo di Dijkstra per il calcolo dei cammini minimi]]
         * funzionamento
         * pseudocodice
         * complessità
         * dimostrazione della correttezza

---+++ <font color="990000" size="+1">Programmazione</font>

*Per i contenuti di questa parte si vedano le informazioni fornite dal prof. Franceschini su [[https://sites.google.com/uniroma1.it/programmazioneinc/home-page][questa pagina]].*