Scheda programma d'esame
ALGORITMICA E LABORATORIO
NADIA PISANTI
Anno accademico2019/20
CdSINFORMATICA
Codice008AA
CFU12
PeriodoSecondo semestre
LinguaItaliano

ModuliSettore/iTipoOreDocente/i
ALGORITMICA E LABORATORIOINF/01LEZIONI96
ANNA BERNASCONI unimap
GIULIO ERMANNO PIBIRI unimap
NADIA PISANTI unimap
ROSSANO VENTURINI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo.

Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.

Knowledge

The goal is to introduce (basic) algorithms and data structures to solve problems on sequences, lists, trees and graphs, in efficient time and/or space. We will also deal with techniques for evaluating the complexity of algorithms and problems. Finally, we will experiment these algorithmic techniques by implementing some of them using the C language.

Modalità di verifica delle conoscenze

Le conoscenze dello studente saranno verificate sulla base della sua capapcità di discutere e mettere in pratica i concetti e le tecniche più importanti presentati nel corso.

Assessment criteria of knowledge

The student's knowledge will be assessed on her/his demonstrated ability to discuss and put into practice the main topics presented during the course.

Capacità

Capacità fondamentali nel progetto di algoritmi e strutture dati e nella valutazione degli algoritmi.

Skills

Basic skills on algorithm and data structure design and time/space complexity evaluation.

Modalità di verifica delle capacità

Esame scritto, prova di laboratorio, ed eventuale orale.

Assessment criteria of skills

Written and programming test, and a possible oral.

Comportamenti

Gli studenti saranno in grado di valutare le performance di algoritmi di base prima della loro implementazione direttamente da progetto; di conoscere problemi difficili per cui le scelte algoritmiche di progetto possono influenzare pesantemente il risultato.

Behaviors

Students will be able to evaluate performance of basic algorithms before their implementation, directly from their design. Know some difficult problems and which algorithmic design choices can impact positively or negatively the algorithm design.

Modalità di verifica dei comportamenti

Esame scritto, prova di laboratorio, ed eventuale orale.

Assessment criteria of behaviors

Written and programming test, and a possible oral.

Prerequisiti (conoscenze iniziali)

Fondamenti di matematica e di linguaggio C. 

Prerequisites

Basics of Maths and C programming.

Corequisiti

Matematica Discreta: Serie Numeriche, Principio di induzione, Dimostrazioni per induzione, Sommatorie.

Co-requisites

Discrete Mathematics such as Numerical Series, Induction, Proving by Inducion, Sums.

Teaching methods

Delivery: face to face

Learning activities:

attending lectures
participation in discussions
individual study
Laboratory work
Attendance: Advised

Teaching methods:

Lectures
laboratory
For details look at the home page of the course.

Programma (contenuti dell'insegnamento)
  1. Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
  2. Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
  3. Limiti del calcolo: albero di decisione, limiti superiori e inferiori. 
  4. Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
  5. Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
  6. Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
  7. Ordinamento di interi: Counting sort, Radix Sort. 
  8. Ordinamento di stringhe: qsort-based.
  9. Sottosequenza di somma massima.
  10. Programmazione dinamica: LCS, Partizione e Zaino
  11. Algoritmi randomizzati: Quicksort.
  12. Generazione di combinazioni e permutazioni
  13. Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
  14. Dizionari: Alberi bilanciati (Alberi 2-3), Tabelle hash (liste di trabocco e indirizzamento aperto).
  15. Alberi: rappresentazione e visite.
  16. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
  17. Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
  18. Grafi III: Minimum Spanning Tree e Shortest Path.

 

Syllabus

SYLLABUS
Short introduction to computational issues: decidability and tractability (P, NP, NPC, EXP-TIME). Computational complexity: computation model, input and output size, decision tree, lower and upper bounds, worst and avarage case. Divide-et-impera; recurrence relations, fundamental theorem. Algorithms on static/dinamic sequences: search and sorting. Stable marrigies problem and maximum sum subsequence. Dynamic Programming: LCS, Partition and Backpack. Combination and permutation generation. Greedy: Knapsack and its variants. Trees representation and visit. Dictionaries: 2-3 trees, hash tables, trie. Randomized Algorithms: Quicksort, QuickSelect. Graphs: representation and visit (DFS e BFS), DAG and topological sorting.

Bibliografia e materiale didattico

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.

Altri riferimenti verrano indicati e pubblicati sulla pagina web del corso.

Bibliography

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.

Further bibliography will be indicated and linked in the home page of the course.

Indicazioni per non frequentanti

Si segua la pagina web del corso.

Non-attending students info

Regularly visit the web page

Modalità d'esame

Esame scritto, test di programmazione C, eventuale orale.

Assessment methods

Written exams, a C programming test, and possibly an oral.

Altri riferimenti web

http://didawiki.di.unipi.it/doku.php/informatica/all-b/start

Additional web pages

http://didawiki.di.unipi.it/doku.php/informatica/all-b/start

Ultimo aggiornamento 01/08/2019 15:22