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.
The course allows the student to acquire adequate knowledge and skills in algorithms, data structures and their implementation in C to solve complex problems. The student should gradually evolve from more analytic to more design-oriented skills. Algorithmic solutions to 'classical' problems are introduced, together with their theoretical foundations, and the implementations in C. Advanced aspects of C are considered, like pointers, dynamic memory allocation, modularity and Abstract Data Type implementation. The student has the opportunity to analyze practical examples, describing solutions to complex problems, and the related algorithmic paradigms. Knowledge and programming skills are applied during lab sessions.
• 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
• Knowledge of techniques for memory allocation and use of pointers
• Programming skills in C, using pointers and dynamic data structures
• Knowledge of basic complexity analysis
• Knowledge of sorting algorithms
• Ability to evaluate algorithm complexity and improve efficiency in terms of execution time and/or memory use
• Knowledge of complex data structures and ADTs (linked lists, queues, stacks, heaps, trees, hash tables and graphs) and related algorithms
• Knowledge of simple strategies for modular programming in C
• Knowledge of recursive, dynamic programming and greedy problem-solving paradigms
• Skills in problem solving, based on design of data structures and algorithms
• Skills in recursive programming techniques
• Skills to exploit tools for program development
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
Due to the incremental nature of the course with respect to the first year class “Computer Science”, there are several strict prerequisites in terms of programming skills and programming language knowledge, with particular emphasis on the following topics:
• Elementary computer systems architecture (Von Neumann model)
• Syntax of C, basic data types and constructs
• Basic programming skills in C, using conditional and iterative constructs, scalar and aggregate data, standard I/O, text files and functions
• Skills in elementary (algorithmic) problem solving
• 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.
• Review of basic language construct and basic problem solving (11h)
• Algorithm analysis (3h)
o Asymptotic worst-case complexity analysis
o O, Omega, Theta notations
o Recurrence equations
• Sorting algorithms (8h)
o Iterative sorting (bubble sort, selection sort, insertion sort, shell sort, counting sort)
o Recursive sorting (mergesort, quicksort, heapsort)
• Static and dynamic data structures and their implementation in C (15h)
o Data representation in memory and runtime memory management
o Pointers (or references to objects)
o Static, on stack and dynamic memory allocation
o Linked structures
o Strategies for data structure selection
• Modularity and modular implementation of algorithms and data structures (10h)
o The implementation-interface-client model
o Implementation in C of programs with multiple source and header files
o Basic use of development and debug tools, like make, gdb, cvs
• Recursion and recursive programs (10h)
o The notion of recursion
o Mathematical recursive functions
o Simple recursive procedures
o Backtrack and implementation of recursion
• Discrete mathematics (4h)
o Sets, relations, functions
o Lists, graphs and trees
• Abstract objects, collections of objects and ADTs (10h)
o Modular examples of composed structures, like arrays of lists and multilists
o Linked lists, stacks, FIFO queues, generalized queues, priority queues, heaps
• Algorithmic paradigms (12h)
o Divide and conquer
o Dynamic Programming
o Greedy
• Problem solving (14h)
o Analysis and definition of strategies for data structures and algorithms
o Search and optimization problems
o Techniques to explore the state space based on combinatorics
• Data structures for symbol tables (8h)
o Binary search trees
o Hash tables
• Graph theory (15h)
o Graph representation
o Depth-first and breadth-first search and their applications
o Shortest paths
o Minimum spanning trees.
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.
Lectures (80h) include practice lessons. Lectures and lab sessions (20h) are extended with 20 additional hours in class or lab to consolidate what the student has learned. Selected lab sessions may be ranked and contribute a bonus (max 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)
Textbooks (in Italian):
• 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
Other suggested readings:
• R. Sedgewick, ‘Algoritmi in C’, IV edizione, Pearson, 2015 (in Italian)
• T.H.Cormen, C.E.Leiserson, R.L.Rivest, C. Stein, ‘Introduzione agli Algoritmi e alle Strutture Dati’, III edizione, Mc-Graw Hill, 2010 (in Italian)
• P. Crescenzi, G. Gambosi, R. Grossi, ‘Strutture di dati e algoritmi’, Pearson Addison-Wesley 2006 (in Italian)
• R. Sedgewick, K. Wayne, ‘Algorithms Part I & II’, www.coursera.org (in English)
• A. Bertossi, A. Montresor, ‘Algoritmi e strutture di dati’, Città Studi edizioni, 2014 (in Italian)
Teaching material available on the Web:
• Lecture transparencies
• Exercises and solutions
• Videolectures (academic year 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.
Exam: Written test; Compulsory oral exam;
The exam consists in:
• a written part (maximum duration 2h30)
• an oral exam.
The written part includes:
• exercises/questions on theoretical aspects, maximum 12 points, maximum duration 50min
• a programming part, maximum duration 1h40, available in 2 alternative modes:
• design and development of a program in C to solve a problem, the emphasis being on problem-solving and design skills (max 18 points)
• guided development of the solution to a problem, with less emphasis on design and problem-solving skills and more on the ability to use advanced C features (pointers, dynamic allocation, recursion) and on the knowledge of basic data structures and algorithms (max 12 points).
Both modes require the same approach to the subject.
Material available during the written part:
• C manual: Kernighan-Ritchie, Deitel & Deitel, or similar
• Header files for standard functions/ADTs unless explicitly forbidden
• NO other books, notes, transparencies etc.
• NO electronic communication tools (cell phones, tablets, laptops, etc.)
Each student must :
• make a copy of the program at the end of the written part (using carbon copy paper, cell phones, cameras etc)
• verify the correctness of the program
• upload on the course webpage within 3 working days: a report (max 3 pages) describing the solution (data structures, algorithm, etc) and a copy of the working program, showing the changes with respect to the version handed in for ranking.
In case the above material is not uploaded, the written exam will not be ranked.
Criterior for admission to the oral exam:
theoryMark≥threshold1 && programmingMark ≥threshold2 && theoryMark+programmingMark ≥15/30
threshold1 and threshold2 are defined at each "appello" based on the difficulty of the written exam.
The oral exam consists in:
• questions on all the topics of the course, the goal being to rank the grade of theoretical knowldege
• programs in C to evaluate skills related to the implementation and manipulation of data structures by means of advanced C programming constructs and to the implementation of variants of standard algorithms
• questions on uploaded lab exercises.
The final mark integrates partial results and is not a mere average. Lab bonusses are not added to, rather they are included in the final mark.
In addition to the message sent by the online system, students with disabilities or Specific Learning Disorders (SLD) are invited to directly inform the professor in charge of the course about the special arrangements for the exam that have been agreed with the Special Needs Unit. The professor has to be informed at least one week before the beginning of the examination session in order to provide students with the most suitable arrangements for each specific type of exam.