Strumenti Utente

Strumenti Sito


informatica:all-b:algob_14:start

Questa è una vecchia versione del documento!


Algoritmica e Laboratorio - Corso B

Anno accademico 2014/2015

Informazioni Generali

Docenti: Anna Bernasconi, Rossano Venturini, Nadia Pisanti

(Docenti corso A: Linda Pagli, Rossano Venturini)

Assistenti: Giovanna Rosone

Impegno: 12 CFU.

Codice: 008AA

Periodo: primo anno, secondo semestre.

Il corso consiste ogni settimana di tre lezioni di didattica frontale in aula e di una esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

Anni accademici precedenti

Orario Lezioni

Orario delle Lezioni
Martedì 11-13 B Teoria
Mercoledì 11-13 B Teoria
Giovedì 14-16 H,M Laboratorio
Venerdì 11-13 B Teoria

Si pregano gli studenti che dispongono di un portatile di portarlo in Laboratorio.

Obiettivi del Corso

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. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo.

Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.

Modalità e Appelli di Esame

L'esame consiste di tre prove:

  • Una prova scritta con esercizi atti a valutare l'apprendimento delle nozioni teoriche e la capacità di “problem solving” dello studente. Tale prova viene valutata in trentesimi, e si intende superata se la valutazione è maggiore o uguale a 18, nel qual caso lo studente è ammesso a sostenere la prova di laboratorio.
  • Una prova in laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi su array, liste, alberi e grafi. Tale prova è da intendersi come un test di idoneità il cui superamento permette allo studente di essere ammesso a sostenere la prova orale. Possono sostenere la prova di laboratorio solo gli studenti che hanno superato la prova scritta.
  • Una prova orale sul programma del corso, la cui valutazione è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta.

Le prove possono essere sostenute in appelli diversi. Se una prova non viene passata, occorre risostenere soltanto quella.

Per avere una idea della tipologia delle prove, si consultino i testi dell'anno scorso.

Data Tipo Prova Documento Note

Prossime date per le prove di laboratorio:

Data Ora Aule Documento

Prossime date per le prove orali:

Data Ora Aula

Libri di testo

  • [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, Terza edizione, 2010.

Per il laboratorio, un testo fra:

  • [KR] B.W. Kernighan, D.M. Ritchie. Il Linguaggio C, Pearson-Prentice Hall, seconda edizione, 2008.
  • [KP] A. Kelley, I. Pohl. C: Didattica e Programmazione, Addison-Wesley, quarta edizione, 2004.

Materiale per il Laboratorio

  • Prerequisito: Conoscenza approfondita della programmazione C per ciò che concerne gli operatori (aritmetici e relazionali), il flusso del controllo (If-then-else, while, for), le funzioni, gli array, i puntatori, le stringhe e l'allocazione dinamica della memoria. Quindi i capitoli 1-5 del libro “Il Linguaggio C”, B.W. Kernighan e D.M. Ritchie, Pearson-Prentice Hall, seconda edizione, 2008.
  • Strumenti per la programmazione: Un editore testuale (tipo Emacs), e il compilatore gcc, sono sufficienti per apprendere e testare le varie nozioni algoritmiche e di coding che verranno discusse in Laboratorio. I programmatori più esperti potranno eventualmente utilizzare un framework di sviluppo come Eclipse esteso con il suo plug-in Eclipse C/C++ Development Tooling. Per chi si trova a operare sotto Windows suggeriamo il compilatore e il debugger disponibili con MinGW, e consigliamo di istallare i 3 componenti suddetti secondo la sequenza: Eclipse-MinGW-CDevTool. Oppure istallare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux sopra. Il consiglio è però quello di adoperare la combinazione minimale editor+gcc al fine di non perdersi nei meandri e nelle opzioni dei vari tools (non necessari per il corso), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.
  • Sistema di Autovalutazione: http://vinello.isti.cnr.it:8888

Programma del corso

  1. Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
  2. Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
  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. Ordinamento di stringhe: qsort-based.
  8. Sottosequenza di somma massima.
  9. Programmazione dinamica: LCS, Partizione e Zaino
  10. Algoritmi randomizzati: Quicksort.
  11. Generazione di combinazioni e permutazioni
  12. Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
  13. Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto).
  14. Alberi: rappresentazione e visite.
  15. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
  16. Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
  17. Grafi III: Minimum Spanning Tree e Shortest Path.
  18. Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).

Registro delle Lezioni

Data Argomento Rif. Biblio
informatica/all-b/algob_14/start.1423144774.txt.gz · Ultima modifica: 05/02/2015 alle 13:59 (7 anni fa) da anna bernasconi