elenco     
        corso     

Algoritmica e Laboratorio

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

Docenti

Linda Pagli   pagli@di.unipi.it  Stanza 277  Tel. 0502212735
Paolo Ferragina   ferragin@di.unipi.it  Stanza 295  Tel. 0502212764

Prerequisiti

Conoscenza di un linguaggio di programmazione imperativo, preferibilmente il linguaggio C (che utilizzeremo per le nostre esercitazioni di laboratorio).

Dimestichezza con l'uso dei puntatori e della ricorsione.

Nozioni matematiche: proprietÓ e limiti di funzioni, sommatorie, numeri di Fibonacci, permutazioni, coefficienti binomiali, aritmetica modulare, numeri primi, metodi di dimostrazione (per induzione, per assurdo, per casi).

Obiettivi di apprendimento

Definire formalmente la nozione di algoritmo e di modello di calcolo. Caratterizzare i dati da elaborare, organizzandoli e strutturandoli nel modo pi¨ opportuno al fine di agevolarne l'uso da parte di un algoritmo. Progettare e realizzare in C algoritmi corretti (che risolvono cioÚ sempre e solo il problema a cui si Ŕ interessati) ed efficienti (cioÚ che lo risolvono il pi¨ velocemente possibile o usano il minor spazio di memoria possibile), attraverso l'esame di diversi paradigmi. Studiare le limitazioni inerenti dei problemi da risolvere, in particolare di quelli la cui soluzione richiede l'esame di tutte le possibilitÓ.

Conoscenze.

Cosa Ŕ un algoritmo e cosa Ŕ un modello di calcolo. Saper caratterizzare i dati da elaborare strutturandoli nel modo pi¨ opportuno al fine di agevolarne l'uso da parte degli algoritmi. Conoscere le strutture dati e le tecniche fondamentali per il progetto di algoritmi (di base). Conoscere le tecniche di valutazione della complessitÓ e le limitazioni inerenti dei problemi da risolvere. Caratterizzare i problemi indecidibili ed esponenziali. Conoscere il linguaggio C e saper realizzare con esso gli algoritmi e le strutture dati viste in classe.

Capacità.

Saper progettare e realizzare in un linguaggio imperativo (es. C) algoritmi corretti ed efficienti attraverso l'uso di strutture dati e tecniche algoritmiche di base. Saper valutare la complessitÓ di un algoritmo in tempo e spazio, al caso pessimo e al caso medio, e secondo la complessitÓ ammortizzata. Saper valutare le limitazioni inerenti del calcolo.

Comportamenti.

Lo studente saprÓ realizzare in un linguaggio imperativo (es. linguaggio C) gli algoritmi e le strutture dati viste in classe. Lo studente saprÓ inoltre stimare la bontÓ (leggi, efficienza in tempo e spazio) di un sofwtare sulla base delle caratteristiche progettuali salienti, prescindendo dunque dalla macchina, dal linguaggio di sviluppo o dal sistema operativo sul quale il software viene eseguito. Allo stesso modo, saprÓ stimareále prestazioni degli algoritmi prima di arrivare alla fase di programmazione, debugging e profiling, mediante l'uso di modelli matematici opportuni.

Descrizione

L'obiettivo del corso Ŕ quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Introdurremo inoltre alcune tecniche per valutare le prestazioni degli algoritmi, o le limitazioni inerenti del calcolo. Infine svolgeremo una intensa attivitÓ di laboratorio che porterÓ gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.

English Description

The goal is to introduce (basic) algorithms and data structures to solve problems on sequences, lists, trees and graphs, in efficient time and/or space. We will also deal with techniques for evaluating the complexity of algorithms and problems. Finally, we will experiment these algorithmic techniques by implementing some of them using the C language.

Indicazioni metodologiche

Il corso consiste ogni settimana di 3 lezioni teoriche e di 1 esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

Programma

Segue una descrizione di massima del programma, per i dettagli si rimanda alla pagina del corso.

  1. Breve introduzione a problemi computazionali, indecidibilitÓ, e trattabilitÓ (P, NP, NPC, EXP-TIME).
  2. ComplessitÓ computazionale: modello di calcolo, dimensione dell'input e dell'output, albero di decisione, limiti superiori e inferiori, caso pessimo e caso medio.
  3. Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
  4. Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
  5. Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
  6. Ordinamento di interi: Counting sort, Radix Sort.
  7. Oridnamento di stringhe.
  8. Problema dei matrimoni stabili e sottosequenza di somma massima.
  9. Programmazione dinamica: LCS, Partizione e Zaino
  10. Generazione di combinazioni e permutazioni
  11. Greedy: Huffman e Zaino
  12. Strutture dati auto-aggiustanti: MTF. Analisi ammortizzata e competitiva.
  13. Alberi: rappresentazione eávisite.
  14. Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto), trie.
  15. Strutture dati randomizzate: Skip List.
  16. Algoritmi randomizzati: Quicksort, Karp-Rabin.
  17. Grafi: rappresentazione, visita (DFS e BFS), DAG e ordinamento topologico, albero di copertura minimo, cammini minimi, componenti (fortemente) connesse.
Ore lezione: 48Ore esercitazione: 48   

Bibliografia

A scelta uno dei seguenti libri di testo:

Anche dispense e appunti forniti in classe dal docente

Modalità di esame

Prova in laboratorio per verificare la capacitÓ di realizzazione in C di algoritmi di base visti in classe, o per la risoluzione di semplici problemi su array, liste, alberi e grafi.

Prova scritta con esercizi atti a valutare l'apprendimento delle nozioni teoriche e la capacitÓ di "problem solving" acquisite dallo studente.

Prova orale.


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


home


email