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 |
|||||||||||||||||||||||||
|
|||||||||||||||||||||||||
|
|||||||||||||||||||||||||
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 |
|