Informatica II

Corso di Laurea in Matematica
Universita' di Udine
Anno Accademico 2008-2009
In collaborazione con il Dott. G. Puppis

Finalita'

Obiettivo del corso e' l'approfondimento sistematico delle tematiche affrontate nel corso di Informatica 1. Argomenti principali del corso sono lo studio, l'analisi e la sintesi di algoritmi, con particolare riferimento all'utilizzo di strutture dati opportune e alla valutazione della loro complessita' temporale e spaziale. Verranno, infine, forniti alcuni elementi di teoria della computabilita' e di complessita' computazionale, con particolare riferimento all'introduzione delle principali classi di complessita' temporale e spaziale. E' prevista attivita' di laboratorio con programmazione in linguaggi imperativi.

Argomenti

  1. Cenni di Teoria della Calcolabilita'.
    Nozione intuitiva di algoritmo. Macchine di Turing. Tesi di Church. Macchine di Turing Universali. Teorema dell'arresto. Calcolabilita' e Decidibilita'. Unlimited Register Machine.
  2. La nozione di Complessita'.
    Complessita' in termini di Tempo e Spazio. Criterio uniforme e criterio logaritmico. Tesi di Church estesa. Complessita' asintotica. Metodi di risoluzione per equazioni ricorsive di complessita'. Classi di Complessita'.
  3. Elementi di Algoritmi e Strutture Dati.
    Strutture dati: Vettori, Record, Liste, Pile, Code, Alberi, Grafi. Algoritmi: HeapSort, Moltiplicazione di Matrici, String Matching, Algoritmi su grafi.

Bibliografia

  1. Breve Introduzione Storica alla Calcolabilita' di F. Fabris.
  2. Dispense di A. Dovier e R. Giacobazzi.
  3. Hopcroft J.E., Ullman J.D., Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
  4. Cutland N., Computability, Cambridge University Press.
  5. Appunti non ufficiali del Corso di Algoritmi.
  6. Cormen T.H., Leiserson C.E., Rivest R.L, Introduction to Algorithms, MIT Press, Second edition, 2001.
  7. Bertoni A., Goldwurm M., Progetto e analisi di algoritmi, Rapporto interno n. 230-98, Dip. Scienze dell'Informazione, Universita' degli Studi di Milano, Settembre 2004.

Elenco delle Lezioni

  1. 28.10.08. Laboratorio. Allocazione Dinamica dei Vettori.
  2. 30.10.08. Complessita'. Criterio Uniforme e Logaritmico. Notazione asintotica.
  3. 04.11.08. Laboratorio. InsertionSort.
  4. 06.11.08. Stima di Somme. Equazioni ricorsive.
  5. 11.11.08. Laboratorio. QuickSort.
  6. 18.11.08. Laboratorio. Record e Puntatori.
  7. 20.11.08. Liste, Pile e Code.
  8. 12.12.08. Algoritmo Select. Heap.
  9. 16.12.08. Laboratorio. HeapSort.
  10. 18.12.08. Alberi Binari. Visite. Grafi.
  11. 15.01.09. Esercizi.

Altro Materiale

  1. Alcuni Comandi utili.
  2. Esami degli anni passati.