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

• 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

• 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

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

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

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.