avvisi
iscrizioni
persone
corsi
orari
tirocini
lauree
gestione

      elenco    
        corso    

Algoritmica e Laboratorio

Codice: 008AACrediti: 12Semestre: 2Sigla: AlL 
 
Settore disciplinare: INF/01 - Informatica

Docente

Giuseppe Prencipe   prencipe@di.unipi.it  Stanza 327  Tel. 0502213148

Prerequisiti

Conoscenza dei basilari Principi di Programmazione e del Linguaggio C. In particolare, per un più proficuo utilizzo delle ore di laboratorio, si consiglia fortemente di studiare approfonditamente i primi 5 capitoli del libro di testo consigliato per le attività di laboratorio (Il Linguaggio C).
 
 

Obiettivi di apprendimento

Argomenti trattati:
  • Problemi Computazionali
  • Array e liste
  • Alberi e grafi
  • Dizionari
  • Pile e code
  • NP-completezza

Programma

  1. Introduzione al Corso
  2. Introduzione informale agli algoritmi
    • I numeri di Fibonacci
    • Algoritmo numerico
    • Algoritmo ricorsivo
    • Algoritmo iterativo
    • Occupazione di memoria e altro algoritmo iterativo
    • Algoritmo basato su potenze ricorsive
    • Nota sulla dimensione dell'istanza in ingresso
  3. Modelli di calcolo e metodologie di analisi
    • Modelli di calcolo
    • Criteri di costo (uniforme e logaritmico)
    • La notazione asintotica (O, O, T)
    • Costo degli algoritmi e complessità dei problemi
    • Metodi di analisi (caso peggiore, migliore e medio)
      • Ricerca sequenziale
      • Ricerca binaria
    • Analisi di algoritmi ricorsivi
      • Metodo iterativo
      • Metodo della sostituzione
      • Analisi dell'albero di ricorrenza
      • Metodo del cambiamento di variabile
      • Master Theorem (con dimostrazione)
  4. Esercitazione
  5. Strutture dati elementari
    • Strutture indicizzate: array
    • Strutture collegate: record e puntatori
    • Dizionari
    • Pile e code
    • Alberi
      • Rappresentazioni indicizzate
      • Rappresentazioni collegate
      • Visite di alberi
  6. Ordinamento con confronti
    • Limite inferiore al problema
    • Algoritmi quadratici: Selection Sort, Insertion Sort, Bubble Sort
    • Heapsort
    • Mergesort
    • Quicksort, con analisi di complessità nel caso medio
  7. Altri tipi di ordinamento
    • Integer sort, Bucket sort, Radix sort
  8. Selezione del k-esimo elemento
    • Soluzione con k piccolo
      • Algoritmo semplice e algoritmo del torneo
  9. Laboratorio C n. 1. Per la lezione, è di fondamentale importanza conoscere:
    • Struttura generale di un programma C
    • Sintassi di:
      • Dichiarazione variabili
      • Array
      • Dichiarazione e invocazione di funzioni
  10. Selezione del k-esimo elemento
    • Heapselect
    • Quickselect
    • Mediano dei mediani
  11. Alberi di ricerca
    • Alberi binari di ricerca
    • Alberi AVL
    • Alberi 2-3
    • Panoramica sui B-Alberi
  12. Tabelle hash
  13. Liste invertite, trie, trie compatti
  14. Laboratorio C n. 2. 
    • Fibonacci numerico
    • Fibonacci ricorsivo (esponenziale)
    • Fibonacci iterativo con array
    • Fibonacci iterativo con 3 variabili
  15. Tecniche algoritmiche
    • Divide et impera
    • Programmazione dinamica
  16. Prima verifica intermedia
  17. Laboratorio C n. 3.
    • Selection Sort e Insertion Sort
    • Mergesort
    • Quicksort (con scelta random del perno)
    • Heapsort (in loco)
  18. Tecniche algoritmiche 
    • Greedy
  19. Stringhe
    • Definizioni
    • Distanza fra 2 stringhe
    • Massima sottosequenza comune (LCS)
    • String matching
    • Stringhe e automi a stati finiti
    • Algoritmo di Knuth, Morris e Pratt
  20. Grafi
    • Definizioni
    • Rappresentazione di grafi
    • Visite (ampiezza e profondità)
    • Componenti connesse di un grafo non orientato
    • Componenti fortemente connesse di un brafo orientato
    • Minimo albero di copertura
      1. Kruskal
      2. Prim
      3. Boruvka
  21. Teoria della complessità 
    • Problemi indecidibili e intrattabili
    • Classi Time,
           

      Bibliografia

      • Teoria
        • C. Demetrescu, I. Finocchi e G. F. Italiano, Algoritmi e Strutture Dati, McGraw-Hill, seconda edizione, 2008
        • P. Crescenzi, G. Gambosi e R. Grossi, Strutture di dati e algoritmi, Pearson – Addison Wesley, 2006
      • Laboratorio (Programmazione in C)
        • B.W. Kernighan, D.M. Ritchie. Il Linguaggio C, Pearson-Prentice Hall, seconda edizione, 2004

      Modalità di esame

      La prova d'esame consiste di due parti:

      1. Prova scritta individuale
      2. Prova orale individuale

      Ulteriore pagina web del corso: http://www.cli.di.unipi.it/doku/doku.php/informaticaapplicata/all/start


home


email