Programma A.A. 2019/20

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à dei principi della buona programmazione.

Descrizione e progettazione di algoritmi efficienti

  • Introduzione
    • Concetti di algoritmo, di struttura dati, di efficienza; di costo 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;
    • costo computazionale nel caso migliore, peggiore e medio
    • Ricerca dicotomica o binaria in un vettore ordinato (vers. iterativa)
    • costo computazionale 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 del costo computazionale delle funzioni ricorsive tramite equazioni di ricorrenza
      • metodo di sostituzione
      • metodo iterativo
      • metodo dell'albero
      • teorema principale ( dimostrazione facoltativa )
  • Il problema dell'ordinamento
    • algoritmi naif: filosofia, pseudocodice e costo computazionale
      • insertion, selection e bubble sort
    • limitazione inferiore sul costo computazionale degli algoritmi di ordinamento per confronti; dimostrazione
    • funzione di fusione e merge sort; cenno alla tecnica del divide et impera
    • ordinamento in tempo lineare: counting sort e bucket sort
    • quick sort e suo costo computazionale nel caso peggiore, migliore e medio
    • heap e heap sort
  • Strutture dati fondamentali
    • insiemi dinamici ed operazioni su di essi
    • vettore non ordinato e ordinato
    • pila e coda, funzioni di inserimento ed estrazione, coda circolare
    • lista semplice e doppiamente puntata
    • coda con priorità
    • albero
      • definizione come grafo connesso aciclico
      • teorema di caratterizzazione degli alberi e dimostrazione
      • alberi radicati, alberi binari, alberi ordinati, 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 del costo computazionale tramite equazione di ricorrenza
  • Dizionari
    • indirizzamento diretto
    • tabelle hash
      • collisioni
      • soluzione delle collisioni per concatenazione (liste di trabocco e fattore di carico)
      • costo computazionale nel caso medio
      • soluzioni delle collisioni con indirizzamento aperto
      • vari tipi di scansione (lineare, quadratica ed hashing doppio)
      • costo computazionale nel caso medio
    • alberi binari di ricerca
      • definizione
      • algoritmo di ricerca e suo costo computazionale
      • algoritmi di ricerca del massimo, minimo, successore e predecessore e loro costo computazionale
      • algoritmo di inserimento e suo costo computazionale
      • algoritmo di cancellazione e suo costo computazionale
    • la problematica del bilanciamento per la limitazione del costo computazionale
      • alberi red black e teorema per la limitazione dell'altezza ( rotazioni ed altri dettagli facoltativi )
  • Grafi
    • rappresentazione in memoria
      • liste di adiacenza
      • matrice di adiacenza
      • matrice di incidenza
      • lista di archi
      • confronto del costo computazionale in termini di spazio e tempo 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 profondità (DFS)
      • proprietà degli archi non dell'albero
      • proprietà del numero di archi in funzione della lunghezza del cammino più lungo
    • similitudini e differenze tra le due visite
    • loro costo computazionale al variare della struttura dati usata
    • esempi di utilizzo delle visite
    • grafi euleriani e loro caratterizzazione
  • argomenti facoltativi:
    • grafi bipartiti e loro caratterizzazione (con dimostrazione)
    • accoppiamenti massimi e accoppiamenti massimali
    • accoppiamenti completi per grafi bipartiti e teoram di P. Hall (con dimostrazione)
    • colorazione di grafi ed enunciato del teroema di Brooks
    • grafi planari e formula di Eulero (con dimostrazione)
    • enunciato del teorema dei 4 colori

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" >
Topic attachments
I Attachment History Action Size Date WhoSorted ascending Comment
PDFpdf grafi.pdf r3 r2 r1 manage 1031.3 K 2011-05-26 - 13:39 TizianaCalamoneri  
Edit | Attach | Watch | Print version | History: r21 < r20 < r19 < r18 < r17 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r21 - 2020-01-14 - TizianaCalamoneri






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