Tags:
create new tag
view all tags

Programma

Il programma di questo corso si compone di due parti che saranno portate avanti parallelamanete.
Una si occuperÓ della descrizione e progettazione di algoritmi efficienti,
l'altra 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

Si assume che gli studenti abbiano familiaritÓ con i fondamenti del C
e che siano in grado di usare variabili di tipo semplice (int, char, double, float),
e di tipo array (allocati staticamente), il concetto di funzione
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,
evitando le complicazioni derivanti dall'uso di un linguaggio orientato agli oggetti come il C++.
La codifica in programma di un algoritmo infatti prevalentemente riguarda gli aspetti imperativi/funzionali
dei linguaggi di programmazione, tutti presenti nel C (che Ŕ il nucleo imperativo del C++).
La programmazione a oggetti, viceversa, mostra la sua utilitÓ maggiore nella progettazione e sviluppo
di software di medie e grandi dimensioni e nell'integrazione di software scritto da diversi programmatori.

<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" >
Edit | Attach | Watch | Print version | History: r12 < r11 < r10 < r9 < r8 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r12 - 2016-02-16 - IvanoSalvo






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback