elenco     
        corso     

Algoritmica e Laboratorio B

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

Docenti

Linda Pagli   pagli@di.unipi.it  Stanza 277  Tel. 0502212735
Anna Bernasconi   annab@di.unipi.it  Home Page di Anna Bernasconi  Stanza 322  Tel. 0502213121
Rossano Venturini   rossano@di.unipi.it  Stanza 361  Tel. 0502213139
Alina Sirbu   alina.sirbu@unipi.it  Home Page di Alina Sirbu  Stanza 331  Tel. 0502212745

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. Generazione di combinazioni e permutazioni.
  3. Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, albero di decisione, limiti superiori e inferiori, caso pessimo e caso medio.
  4. Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
  5. Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
  6. Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
  7. Ordinamento di interi: Counting sort, Radix Sort.
  8. Oridnamento di stringhe.
  9. Analisi ammortizzata: doubling di array.
  10. Sottosequenza di somma massima.
  11. Programmazione dinamica: LCS, Partizione e Zaino
  12. Generazione di combinazioni e permutazioni
  13. Alberi: rappresentazione e visite.
  14. Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto).
  15. Algoritmi randomizzati: Quicksort.
  16. Grafi: rappresentazione, visita (DFS e BFS), DAG e ordinamento topologico, albero di copertura minimo, cammini minimi, componenti connesse.
Ore lezione: 48Ore esercitazione: 24Ore laboratorio: 24  

Bibliografia

A scelta uno dei seguenti libri di testo:

 

Anche dispense e appunti forniti in classe dal docente

Per il laboratorio, un testo fra:

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://didawiki.cli.di.unipi.it/doku.php/informatica/all-b/start


home


email