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 trattano aspetti avanzati del linguaggio C, quali puntatori, allocazione dinamica della memoria, modularità e realizzazione di Tipi di Dato Astratti. 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.

• Conoscenza dei meccanismi di allocazione della memoria e utilizzo dei puntatori • Abilità di programmazione avanzata 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, dinamica e greedy • Abilità di problem solving mediante progetto di strutture dati e algoritmi • Abilità nelle tecniche di programmazione ricorsiva, dinamica e greedy • Abilità di utilizzo di strumenti di ausilio alla programmazione

Vista la natura incrementale di questo corso rispetto a quello del I anno “Informatica”, vi sono prerequisiti stringenti in termini di abilità di programmazione e conoscenza del linguaggio C, in particolare: • Architettura elementare dei sistemi di elaborazione (modello di Von Neumann) • 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

• Costrutti fondamentali del linguaggio C e problem-solving elementare (11h) • Analisi di algorítmi (3h) o analisi asintotica di complessità di caso peggiore o notazione O, Omega, Theta o equazioni alle ricorrenze • Algoritmi di ordinamento (8h) o ordinamenti iterativi (bubble sort, selection sort, insertion sort, shell sort, counting sort) o ordinamenti ricorsivi (mergesort, quicksort, heapsort) • Strutture dati statiche e dinamiche e loro realizzazione in C (15h) o rappresentazione dei dati in memoria e gestione della memoria in runtime o puntatori (o riferimento a oggetti) o allocazione di memoria statica, su stack, e dinamica o strutture linkate o strategie per scegliere la struttura dati • Modularità e realizzazione modulare di algoritmi e strutture dati (10h) o il modello implementazione-interfaccia-client o la realizzazione di un programma C con più sorgenti e header file o utilizzo elementare di strumenti di sviluppo e debug: es. make, gdb, cvs • Ricorsione e programmi ricorsivi (10h) o il concetto di ricorsione o funzioni matematiche ricorsive o procedure ricorsive semplici o backtrack e implementazione della ricorsione • Matematica discreta (4h) o insiemi, relazioni, funzioni o grafi e alberi, liste • Oggetti astratti, collezioni di oggetti e ADT (10h) o esempi modulari di strutture composte quali vettori di liste, multiliste o liste, stack, code FIFO, code generalizzate, code a priorità, heap • Paradigmi algoritmici (12h) o divide et impera o il paradigma della programmazione dinamica o il paradigma greedy • Problem solving (14h) o strategie di analisi e di definizione di strutture dati e algoritmi o problemi di ricerca e di ottimizzazione o tecniche di esplorazione dello spazio delle possibilità basate su calcolo combinatorio e ricorsione • Strutture dati per tabelle di simboli (8h) o Alberi Binari di Ricerca o Tabelle di hash • Teoria dei grafi (15h) o rappresentazione dei grafi o visite in profondità e ampiezza e loro applicazioni o cammini minimi o alberi ricoprenti minimi.

Le lezioni in aula (80h) sono comprensive di esercitazioni integrate. Lezioni in aula ed esercitazioni in laboratorio (20h) sono integrate con ulteriori 20h per consolidamento delle nozioni apprese. Alcuni dei laboratori possono essere valutati e dare adito ad un bonus di al massimo 2/30.

Testi di riferimento: • Deitel & Deitel, ‘Corso completo di programmazione C’, Apogeo, 2010 • P. Camurati, S. Quer, ‘Algoritmi e Programmazione: richiami di teoria con esercizi svolti’, CLUT, IV edizione, 2017 • G. Cabodi, P. Camurati, P. Pasini, D. Patti, D. Vendraminetto, ‘Dal problema al programma: introduzione al problem-solving in linguaggio C’, Apogeo, II edizione, 2016 • G. Cabodi, P. Camurati, P. Pasini, D. Patti, D. Vendraminetto, ‘Ricorsione e problem-solving: strategie algoritmiche in linguaggio C’, Apogeo, 2015 • G. Cabodi, P. Camurati, P. Pasini, D. Patti, D. Vendraminetto, ‘Puntatori e strutture dati dinamiche: allocazione della memoria e modularità in linguaggio C’, Apogeo, 2016 • G. Cabodi, P. Camurati, P. Pasini, D. Patti, D. Vendraminetto, ‘Algoritmi in pratica’ (titolo provvisorio), Apogeo, 2018 Altri testi suggeriti: • R. Sedgewick, ‘Algoritmi in C’, IV edizione, Pearson, 2015 • T.H.Cormen, C.E.Leiserson, R.L.Rivest, C. Stein, ‘Introduzione agli Algoritmi e alle Strutture Dati’, III edizione, Mc-Graw Hill, 2010 • 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 (in inglese) • 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 • videolezioni (a.a. 2016/17)

Modalità di esame: Prova scritta (in aula); Prova orale obbligatoria;

Exam: Written test; Compulsory oral exam;

... L’esame si compone di: • una prova scritta (durata massima 2h30) • un esame orale. La prova scritta consta di: • una parte con esercizi/domande sugli argomenti teorici, punteggio massimo 12 punti, durata massima 50 min. • una parte di programmazione, durata massima 1h40, disponibile in 2 modalità alternative: o progetto e sviluppo di un programma in grado di risolvere un problema con enfasi su problem-solving e capacità progettuali, punteggio massimo 18 punti o 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 • Header file per funzioni/ADT standard se non vietato esplicitamente • 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 • caricare sulla pagina del corso 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 carichi il materiale indicato entro la data prevista, la prova scritta non viene corretta. Criterio di ammissione all'orale: votoTeoria≥soglia1 && votoC ≥soglia2 && votoTeoria+votoC ≥15/30 soglia1 e soglia2 sono definite di volta in volta in funzione della difficoltà del compito scritto. L’orale consiste in: • domande su tutti gli argomenti del corso per accertare le conoscenze teoriche acquisite • programmi in C per accertare la capacità di realizzare e manipolare di strutture dati mediante funzionalità avanzate del linguaggio e di implementare varianti di algoritmi visti durante il corso • domande sugli esercizi di laboratorio consegnati. La valutazione è complessiva ed integra, non media, i risultati nelle singole parti di cui consta l’esame. Eventuali bonus per laboratori valutati non sono additivi, bensì inclusi nella valutazione complessiva.

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.