ProgrammaDelCorso < Infogen

Tags: view all tags
---+++ <font color=990000 size="+2">Programma</font>
Il programma di questo corso si compone di due parti che saranno portate avanti parallelamanete.<br>
Una si occuperà della descrizione e progettazione di algoritmi efficienti, <br>l'altra 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, &#937; e &#920;
   * 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
      * <A href=http://twiki.dsi.uniroma1.it/pub/Infogen/DispenseELibriDiTesto/Dijkstra.pdf>Algoritmo di Dijkstra per il calcolo dei cammini minimi</A>
         * funzionamento
         * pseudocodice
         * complessità
         * dimostrazione della correttezza

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

Si assume che gli studenti abbiano familiarità con i fondamenti del C <br>e che siano in grado di usare variabili di tipo semplice (int, char, double, float), <br>
e di tipo array (allocati staticamente), 
il concetto di funzione <br> ed il passaggio dei parametri (almeno per valore).

   * Esecutori e programmi. L'esecutore Tiny C.
      * Programmare per gerarchie di astrazioni: dal Tiny C alla risoluzione di problemi complessi.
      * Funzioni somma, differenza, esponenziale, e predecessore in Tiny C.
      * Moltiplicazione (ed esponenziale) egiziana.
      * Cenni alla completezza computazionale del Tiny C.
      * Conseguenze sulla complessità nell'usare un sistema unario di calcolo.	
   * Correttezza dei programmi: introduzione all'uso di asserzioni logiche.
      * Pre-condizioni e post-condizioni di una funzione.
      * Correttezza dei programmi iterativi: invarianti di ciclo.
      * Progettazione di funzioni partendo dalla loro specifica logica: divisione intera.
   * Rivisitazione dei puntatori in C.
      * Operatori di referenziazione e dereferenziazione di un puntatore.
      * Uno strano tipo: void *.
   * Passaggio di parametri ed esecuzione delle funzioni.
      * Passaggi per indirizzo e passaggi per valore.
      * Regole di scoping: variabili locali e variabili globali.
      * Fenomeni pericolosi: alias e side-effects. Il caso della funzione scambia senza variabile di appoggio. 
      * Lo stack di attivazione delle chiamate di funzione.
   * Ricorsione [2 lezioni]. 
      * Esempi di funzioni ricorsive. 
      * Valutazione della correttezza di un programma ricorsivo per induzione. 
      * Potenziali rischi di inefficienza della ricorsione. Il caso del calcolo dei numeri di Fibonacci.
      * Funzione ricorsiva efficiente per i numeri di Fibonacci.
      * Traduzione di un generico programma iterativo in ricorsivo. 
      * Problemi a soluzione inerentemente ricorsiva. Il problema della Torre di Hanoi.
      * Cenni alla completezza computazionale della ricorsione.
   * Vettori: 
      * Allocazione statica di un vettore.
      * Puntatori e vettori: scansione di vettori mediante l'aritmetica dei puntatori.
      * Passaggio di un vettore come parametro.
      * Sviluppo di funzioni su vettori con asserzioni logiche.
      * Introduzione all'allocazione dinamica di memoria: vettori allocati dinamicamente.
      * Cenni alle stringhe.
   * Vettori bidimensionali: 
      * Dichiarazione, rappresentazione in memoria.
      * Allocazione dinamica di una matrice bidimensionale.
      * Passaggio di un vettore bidimensionale come parametro.
      * Metodologia di programmazione Top-Down. Esempio: il gioco del Forza4.
   * Liste in C [2 lezioni].
      * Specifica induttiva del tipo di dato sequenza.
      * Rappresentazione a puntatori di una sequenza in C. Creare nuovi tipi: typedef.
      * Ancora sull'allocazione dinamica della memoria.
      * Costruttori e distruttori di un tipo di dato e loro implementazione per il tipo sequenza.
      * Specifica mediante equazioni ricorsive di una funzione su sequenze.
      * Rivisitazione dei side-effects nel caso di liste.
      * Stile funzionale nella programmazione su liste: evitare i side-effects e garantire la trasparenza referenziale.
      * Tipici problemi sulle liste: concatenazione, rovesciamento, fusione ordinata di liste ordinate.
      * Trucchi del mestiere: uso dei parametri per memorizzare dati intermedi di un calcolo in una scansione ricorsiva di una lista.
      * Applicazioni delle liste: implementazione tipo di dato Coda e Pila.
      * Cenni alla traduzione di programmi ricorsivi in iterativi attraverso la simulazione della pila di attivazione delle chiamate ricorsive.
   * Alberi binari [2 lezioni]
      * Specifica induttiva del tipo albero binario.
      * Rappresentazione a puntatori di un albero in C.
      * Costruttori e distruttori del tipo albero binario e loro implementazione in C.
      * Specifica mediante equazioni ricorsive di una funzione su alberi.
      * Tipici problemi su alberi binari: uguaglianza, sottoalbero, bilanciamento. 
      * Versioni ingenue e versioni che fanno un'unica scansione dell'albero.

In laboratorio:
   * Compilazione ed esecuzione di un programma C in Linux
      * Dal file C al file eseguibile: preprocessore, compilazione, linking
      * Assistenza allo sviluppo e testing di programmi.
      * Assistenza allo svolgimento degli homework.

Essendo un corso di algoritmi e programmazione, è stato ritenuto opportuno usare il linguaggio C, <br>
evitando le complicazioni derivanti dall'uso di un linguaggio orientato agli oggetti come il C++.<br>
La codifica in programma di un algoritmo infatti prevalentemente riguarda gli aspetti imperativi/funzionali<br>
dei linguaggi di programmazione, tutti presenti nel C (che è il nucleo imperativo del C++).<br>
La programmazione a oggetti, viceversa, mostra la sua utilità maggiore nella progettazione e sviluppo <br>
di software di medie e grandi dimensioni e nell'integrazione di software scritto da diversi programmatori.


<!-- Start of StatCounter Code -->
<script type="text/javascript">
var sc_project=6759759; 
var sc_invisible=1; 
var sc_security="81bd8f62"; 
</script>

<script type="text/javascript"
src="http://www.statcounter.com/counter/counter.js"></script><noscript><div
class="statcounter"><a title="joomla visitor"
href="http://statcounter.com/joomla/" target="_blank"><img
class="statcounter"
src="http://c.statcounter.com/6759759/0/81bd8f62/1/"
alt="joomla visitor" ></a></div></noscript>
<!-- End of StatCounter Code -->