Politecnico di Torino
Politecnico di Torino
   
Login  
en
Politecnico di Torino
Anno Accademico 2015/16
02MNOOA, 02MNONZ
Algoritmi e programmazione
Corso di Laurea in Ingegneria Informatica - Torino
Corso di Laurea in Ingegneria Delle Telecomunicazioni - Torino
Docente Qualifica Settore Lez Es Lab Tut Anni incarico
Cabodi Gianpiero ORARIO RICEVIMENTO AC ING-INF/05 40 0 20 20 5
Camurati Paolo Enrico ORARIO RICEVIMENTO PO ING-INF/05 40 0 20 60 9
SSD CFU Attivita' formative Ambiti disciplinari
ING-INF/05 10 B - Caratterizzanti Ingegneria informatica
Presentazione
Insegnamento obbligatorio della Laurea in Ingegneria Informatica, collocato al I periodo didattico del II anno.
Il corso permette di acquisire adeguate conoscenze di algoritmi, strutture dati e loro implementazione in C per la soluzione di problemi complessi. Si accentua il passaggio dalle capacità analitiche a quelle progettuali. Vengono presentate le soluzioni algoritmiche "classiche" dei problemi e la teoria che sta alla loro base, con particolare riferimento a implementazioni in C. Si propongono agli studenti esempi pratici di soluzione di problemi complessi, con analisi dei principali paradigmi risolutivi e si svolgono esercitazioni di laboratorio ad essi connesse.
.
Risultati di apprendimento attesi
• Conoscenza dei meccanismi di allocazione della memoria e utilizzo dei puntatori
• Abilità di programmazione in C, utilizzando puntatori e strutture dati dinamiche
• Conoscenza delle nozioni elementari di analisi della complessità
• Conoscenza degli algoritmi di ordinamento
• Abilità di valutare la complessità di algoritmi e di migliorarne l'efficienza in termini di tempo di esecuzione e/o uso di memoria
• Conoscenza di strutture dati complesse e ADT (liste, code, pile, heap, alberi, tabelle di hash e grafi) e dei relativi algoritmi
• Conoscenza delle strategie elementari di programmazione modulare in C
• Conoscenza dei paradigmi di programmazione ricorsiva e greedy
• Abilità di utilizzo di strumenti di ausilio alla programmazione
• Abilità di problem solving mediante progetto di strutture dati e algoritmi
• Abilità nelle tecniche di programmazione ricorsiva
Prerequisiti / Conoscenze pregresse
• Conoscenza dell'architettura elementare dei sistemi di elaborazione (modello di Von Neumann)
• Conoscenza di sintassi, tipi di dato e costrutti base del linguaggio C
• Capacità di sviluppare semplici programmi in C, utilizzando costrutti condizionali e iterativi, dati scalari a aggregati, I/O standard, file testo e funzioni
• Capacità di soluzione di problemi (algoritmici) elementari
Programma
•• Analisi di algorítmi: analisi asintotica di complessità di caso peggiore; notazione O, , ; equazioni alle ricorrenze. (6 h)
• Algoritmi di ordinamento: ordinamenti iterativi (bubble sort, selection sort, insertion sort, shell sort, counting sort) e ricorsivi (mergesort , quicksort, heapsort). (6 h)
• Strutture dati statiche e dinamiche e loro realizzazione in C: rappresentazione dei dati in memoria e gestione della memoria in runtime; puntatori (o riferimento a oggettì); allocazione di memoria statica, su stack, e dinamica; strutture linkate; strategie per scegliere la struttura dati. (9 h)
• Modularità e realizzazione modulare di algoritmi e strutture dati: il modello implementazione-interfaccia-client; la realizzazione di un programma C con più sorgenti e header file; utilizzo elementare di strumenti di sviluppo e debug: es. make, gdb, cvs. (6 h)
• Ricorsione e programi ricorsivi: il concetto di ricorsione; funzioni matematiche ricorsive; procedure ricorsive semplici; backtrack e implementazione della ricorsione. (12 h)
• Matematica discreta: insiemi, relazioni, funzioni, grafi e alberi (3 h)
• Oggetti astratti, collezioni di oggetti e ADT: esempi modulari di strutture composte quali vettori di liste, multiliste; liste, stack, code FIFO, code generalizzate, coda prioritaria, heap. (6 h)
• Paradigmi algoritmici: divide et impera; il paradigma greedy. (5 h)
• Problem solving: strategie di analisi e di definizione di strutture dati e algoritmi; problemi di ricerca e di ottimizzazione; tecniche di esplorazione dello spazio delle possibilità. (6 h)
• Strutture dati per tabelle di simboli: Alberi Binari di Ricerca; Tabelle di hash. (9 h)
• Teoria dei grafi: rapprestazione dei grafi; visite in profondità e ampiezza; applicazioni delle visite; cammini minimi; alberi ricoprenti minimi. (12 h)
Organizzazione dell'insegnamento

Lezioni in aula (80 h), comprensive di esercitazioni integrate su puntatori e allocazione dinamica di memoria; programmi modulari e strumenti di sviluppo; programmazione ricorsiva; problem solving e paradigmi algoritmici; esempi di problem-solving complesso
Esercitazioni in laboratorio (20 h): puntatori e allocazione dinamica di memoria: vettori e matrici dinamiche, liste; programmi modulari e strumenti di sviluppo; programmazione ricorsiva con backtrack; problem solving e paradigmi algoritmici; strutture dati, ADT e tabelle di simboli: stack e FIFO, BST, tabelle di hash;
algoritmi sui grafi
Testi richiesti o raccomandati: letture, dispense, altro materiale didattico
Testi di riferimento:
• R. Sedgewick, ‘Algoritmi in C’, III edizione, Addison-Wesley
Deitel & Deitel, ‘Corso completo di programmazione C’, Apogeo
• P. Camurati, S. Quer, ‘Algoritmi e Programmazione: richiami di teoria con esercizi svolti’, CLUT, 2013

Altri testi suggeriti:
• T.H.Cormen, C.E.Leiserson, R.L.Rivest, ‘Introduction to Algorithms’, MC-Graw Hill
• P. Crescenzi, G. Gambosi, R. Grossi, ‘Strutture di dati e algoritmi’, Pearson Addison-Wesley 2006
• R. Sedgewick, K. Wayne, ‘Algorithms Part I & II’, www.coursera.org
• A. Bertossi, A. Montresor, ‘Algoritmi e strutture di dati’, Città Studi edizioni, 2014

Materiale didattico a disposizione su Web:
• trasparenze proiettate in aula
• esercizi e soluzioni
Criteri, regole e procedure per l'esame
L’esame si compone di una prova scritta con esercizi/domande sugli argomenti teorici e soluzione di un problema con un programma C e di un esame orale. La prova scritta dure indicativamente 2h30. La parte di teoria vale un massimo di 12 punti. La parte di programmazione è disponibile in 2 versioni in alternativa:
• progetto e sviluppo di un programma in grado di risolvere un problema con enfasi su problem-solving e capacità progettuali, punteggio massimo 18 punti
• sviluppo guidato della soluzione di un problema con minore enfasi sul problem-solving e sulle capacità progettuali e con maggiore enfasi sulla padronanza del C avanzato (puntatori, allocazione dinamica, ricorsione) delle strutture dati e degli algoritmi fondamentali, punteggio: massimo 12 punti.
La preparazione richiesta per entrambe le parti à la stessa. .
Materiale consultabile durante lo scritto:
• Manuale di riferimento di C: Kernighan-Ritchie, Deitel & Deitel, o simili
• NON è possibile consultare altri testi, appunti, dispense, etc.
• NON è possibile utilizzare supporti di tipo elettronico (cellulari, palmari, portatili, etc.)
Ciascuno studente è tenuto a :
• produrre (ad esempio tramite carta carbone, fotocamera o cellulare terminato lo scritto!) una copia del programma
• verificare la correttezza e la funzionalità del programma
• inviare al docente via posta il seguente materiale (entro tre giorni dalla data dello scritto) relazione (max 3 pagine) sulla soluzione adottata (strutture dati, algoritmo, etc.) e copia del programma corretto, con evidenziate le modifiche rispetto al programma consegnato.
Qualora lo studente non invii il materiale indicato entro la data prevista, la prova scritta non viene corretta.
Orario delle lezioni
Statistiche superamento esami

Programma definitivo per l'A.A.2015/16
Indietro



© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)
Contatti