Scopi

Il modulo completa l' avvio alla programmazione quale strumento per la soluzione di problemi. Si accentua il passaggio dalle capacità analitiche a quelle progettuali.
Il modulo presenta le soluzioni algoritmiche "classiche" dei problemi, e la teoria che sta alla loro base, con particolare riferimento a realizzazioni in C e affronta casi di studio di maggiori dimensioni risolti mediante strategie algoritmiche implementate in C.

Precedenza di acquisto:
Informatica II

Ulteriore propedeuticità concettuale: è prerequisito fondamentale per il corso la conoscenza della programmazione in linguaggio C.

• Analisi di algoritmi: analisi asintotica e complessità di caso peggiore; notazione Ο, Θ, Ω;
• Algoritmi elementari: ordinamento quadratico (selection sort, insertion sort), lineare (counting sort) e logaritmico (quicksort, heapsort, mergesort); attraversamenti di alberi e grafi
• Strutture dati: rappresentazione dei dati in memoria; puntatori; allocazione di memoria statica, e dinamica; strutture linkate; gestione della memoria in runtime; strategie per scegliere la struttura dati
• Ricorsione: il concetto di ricorsione; funzioni matematiche ricorsive; procedure ricorsive semplici; backtrack e implementazione della ricorsione
• Paradigmi algoritmici: divide-and-conquer; greedy
• Algoritmi classici: tabelle di hash; alberi binari di ricerca e varianti; B-alberi
• Algoritmi sui grafi: cammini minimi; alberi ricoperti minimi

Il tutorato in aula privilegia la parte di programma più applicativa relativa alla programmazione in linguaggio C: Si procederà all'analisi e implementazione degli algoritmi e delle strutture dati oggetto di studio. Tali componenti verranno utilizzate per lo sviluppo di programmi avanzati in linguaggio C.

Testi consigliati dal docente responsabile del corso:

Testi di riferimento tradotti in italiano

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati, seconda edizione, McGraw Hill.
• R. Sedgewick, Algoritmi in C, Pearson Ed. Italia.
• Brian W. Kernighan, Dennis M. Ritchie, Linguaggio C, Addison Wesley / Pearson Education, Italia.
• Brian W. Kernighan, Dennis M. Ritchie, Linguaggio C, Jackson Libri (non più in stampa).

Testi di riferimento in lingua inglese

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, The MIT Press and McGraw-Hill.
• Brian W. Kernighan, Dennis M. Ritchie, The C Programming Language, Prentice Hall.

Guida alla lettura per [Cormen, 2a edizione, McGraw-Hill, 2005]

• Cap. 1: Ruolo degli algoritmi nell'elaborazione dei dati
  sez. 1-2
• Cap. 2: Per incominciare
  sez. 1-3
• Cap. 6: Heapsort
  sez. 1-5
• Cap. 7: Quicksort
  sez. 1-2
• Cap. 8: Ordinamento in tempo lineare
  sez. 2
• Cap.10: Strutture dati elementari
  sez. 1-2
• Cap.11: Hashing
  sez. 1-4
• Cap.12: Alberi binari di ricerca
  sez. 1-3
• Cap.15: Programmazione dinamica
  sez. 1-5 (accenni)
• Cap.22: Algoritmi elementari per grafi
  sez. 1-5
• Cap.23: Alberi di connessione minimi
  sez. 1-2
• Cap.24: Cammini minimi da sorgente unica
  sez. 1-4

Questa raccolta di materiale, prodotta ad uso interno, è stata realizzata per i moduli del Politecnico di Torino ed è disponibile in formato .pdf.
Ne è vietata la riproduzione e qualsiasi forma di commercializzazione.

• Dispense A.A. 2006 - 2007 (3.4 MB) a cura dell'Ing. A. Servetti
• Dispense A.A. 2003 - 2004 (3.4 MB) a cura dell'Ing. G. Squillero.
• Dispense A.A. 2002 - 2003 (757 KB) a cura dei Proff. M. Sonza Reorda e F. Corno.

Gli argomenti del corso sono trattati nel CD-ROM omonimo.
Per maggiori ragguagli circa le specifiche relative ai CD-ROM prodotti consultare l'Area CD-ROM multimediali.

Ulteriore materiale e aggiornamenti sono disponibili nelle pagine personali del tutore relative alla didattica:

• http://media.polito.it/servetti/teaching/

All'indirizzo http://www.cad.polito.it/staff/squillero/dida/09eip/ sono archiviate le risorse (non più aggiornate) degli anni precedenti.

Questa raccolta di materiale, prodotta ad uso interno, è stata realizzata per i moduli del Politecnico di Torino ed è in formato .pdf. Ne è vietata la riproduzione e qualsiasi forma di commercializzazione.

• Appello del 13/05/2007 (teoria) ( 66 KB)
• Appello del 13/05/2007 (programmazione) ( 287 KB)
• Appello del 19/09/2007 (teoria) ( 87 KB)
• Appello del 19/09/2007 (programmazione) ( 116 KB)
• Appello del 09/07/2007 (teoria) ( 82 KB)
• Appello del 09/07/2007 (programmazione) ( 100 KB)
• Appello del 14/05/2007 (teoria) ( 84 KB)
• Appello del 14/05/2007 (programmazione) ( 60 KB)
• Appello del 19/12/2006 (teoria) ( 99 KB)
• Appello del 23/09/2003 ( 11 KB)
• Appello del 22/09/2003 ( 17 KB)
• Appello del 21/07/2003 ( 12 KB)
• Appello del 22/05/2003 ( 15 KB)
• Appello del 17/04/2003 ( 15 KB)
• Appello del 24/03/2003 ( 16 KB)
• Appello del 23/01/2003 ( 128 KB)
• Appello del 11/11/2002 ( 126 KB)
• Appello del 25/09/2002 ( 136 KB)
• Appello del 23/07/2002 ( 101 KB)
• Appello del 19/03/2002 (teoria) ( 105 KB)
• Appello del 19/03/2002 (programmazione) ( 58 KB)
• Appello del 02/03/2002 ( 119 KB)

• L'esame ¿ composto da due scritti.
  Il primo serve a valutare la conoscenza teorica degli algoritmi e delle strutture dati.
  Il secondo la capacità di impostare un programma complesso e la capacità di analizzare un problema (la sintassi del C è un prerequisito).
• Per superare l'esame ¿ necessario (ma non sufficiente) raggiungere un punteggio ≥ (simbolo del superiore/uguale) 10/15 nel primo scritto (teoria) e ≥ (idem) 4/15 nel secondo (programmazione).
• I due scritti possono essere svolti in appelli differenti durante l'anno accademico.
• Dopo lo scritto di programmazione, gli studenti sono tenuti a correggere e completare autonomamente il programma consegnato ed inviare una versione funzionante al tutore. La prova svolta in aula sarà valutata solo dopo aver verificato il funzionamento di tale programma. (Si suggerisce di utilizzare carta carbone per conservare una copia di quanto consegnato in aula).