Il Corso ha lo scopo di illustrare le principali tecniche di progettazione di algoritmi e di descrivere ed analizzare gli algoritmi di base più diffusi e le strutture dati in essi utilizzate, con particolare riferimento agli aspetti di complessità computazionale.

English version: the aim of the course is to illustrate the main techniques for algorithms design and to describe and analyze the most known basic algorithms together with respective used data structures, with particular focus on computational complexity facets.

01. Introduzione agli algoritmi e alle strutture dati:

  01.01 Algoritmi e loro tipologie.

  01.02 Correttezza di un algoritmo rispetto ad un problema.

  01.03 Complessità di un algoritmo rispetto all'uso di risorse.

  01.04 Strutture dati e loro tipologie.

02. Classi di problemi:

  02.01 Problemi decidibili e indecidibili.

  02.02 Problemi trattabili e intrattabili.

  02.03 Teorema di Cook.

  02.04 NP-completezza.

03. Complessità degli algoritmi:

  03.01 Notazioni per esprimere la complessità asintotica.

      03.02 Calcolo della complessità di algoritmi non ricorsivi.

  03.03 Calcolo della complessità di algoritmi ricorsivi.

04. Algoritmi per array:

  04.01 Array: definizioni di base e problemi classici.04.02 Algoritmo di visita per array.

  04.03 Algoritmo di ricerca lineare per array.

  04.04 Algoritmo di ricerca binaria per array ordinati.

  04.05 Criteri di confronto per algoritmi di ordinamento per array.

  04.06 Insertsort.

  04.07 Selectsort.

  04.08 Bubblesort.

  04.09 Mergesort.

  04.10 Quicksort.

  04.11 Heapsort.

  04.12 Code con priorità basate su heap binari.

05. Algoritmi per liste:

  05.01 Liste: definizioni di base e problemi classici.

  05.02 Algoritmi di visita, ricerca, inserimento e rimozione per liste.

  05.03 Algoritmi di inserimento e rimozione per code.

  05.04 Algoritmi di inserimento e rimozione per pile.

06. Algoritmi per alberi:

  06.01 Alberi: definizioni di base e problemi classici.

  06.02 Algoritmi di visita e ricerca per alberi binari.

  06.03 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca.

  06.04 Criteri di bilanciamento per alberi binari di ricerca.

  06.05 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca rosso-nero.

07. Algoritmi per grafi:

  07.01 Grafi: definizioni di base e problemi classici.

  07.02 Algoritmi di visita e ricerca per grafi.

  07.03 Algoritmo di ordinamento topologico per grafi diretti e aciclici.

  07.04 Algoritmo delle componenti fortemente connesse per grafi.

  07.05 Algoritmo di Kruskal.

  07.06 Algoritmo di Prim.

  07.07 Proprietà del percorso più breve.

  07.08 Algoritmo di Bellman-Ford.

  07.09 Algoritmo di Dijkstra.

  07.10 Algoritmo di Floyd-Warshall.

08. Algoritmi per stringhe:

  08.01 Stringhe: definizioni di base e problemi classici.

  08.02 Algoritmo ingenuo di string matching.

  08.03 Algoritmo per il calcolo della distanza di edit tra stringhe.

  08.04 Algoritmo per il calcolo della massima sottosequenza comune.

09. Selezione e statistiche d'ordine:

  09.01 Definizioni di base e problemi.

  09.02 Heapselect.

  09.03 Selezione randomizzata.

  09.04 Selezione deterministica.

10. Tecniche algoritmiche:

  10.01 Tecnica del divide et impera.

  10.02 Programmazione dinamica.

  10.03 Tecnica golosa.

  10.04 Tecnica per tentativi e revoche.

11. Attività di laboratorio:

  11.01 Elementi di linguaggio C: richiami, editing, compilazione, debugging.

  11.02 Generatori di numeri pseudocasuali: funzioni rand e srand.

  11.03 Valutazione sperimentale della complessità degli algoritmi: timing e contatori.

  11.04 Confronto sperimentale degli algoritmi di ordinamento per array.

  11.05 Confronto sperimentale degli algoritmi di ricerca per alberi binari.

  11.06 Implementazione di algoritmi su grafi: visita in ampiezza e profondità di un grafo, algoritmo di Dijkstra.

  11.07 Implementazione di algoritmi su stringhe: Edit Distance e LCS.

English version:

01. Introduction to algorithms and data structures:

  01.01 Algorithms and their typologies

  01.02 Correctness of an algorithm with respect to a problem

  01.03 Complexity of an algorithm with respect to resource usage

  01.04 Data structures and their typologies

02. Classes of problems:

  02.01 Decidable and undecidable problems

  02.02 Tractable and intractable problems

  02.03 Cook theorem

  02.04 NP-completeness

03. Complexity of the algorithms:

  03.01 Notations to express the asymptotic complexity

  03.02 Computing the complexity of non-recursive algorithms

  03.03 Computing the complexity of recursive algorithms

04. Array algorithms:

  04.01 Arrays: basic definitions and classical problems

  04.02 Traversal algorithm for arrays

  04.03 Linear search algorithm for arrays

  04.04 Binary search algorithm for sorted arrays

  04.05 Comparison criteria for sorting algorithms for arrays

  04.06 Insertsort

  04.07 Selectsort

  04.08 Bubblesort

  04.09 Mergesort

  04.10 Quicksort

  04.11 Heapsort

  04.12 Priority queues based on binary heaps

05. List algorithms:

  05.01 Lists: basic definitions and classical problems

  05.02 Traversal, search, insertion and removal algorithms for lists

  05.03 Insertion and removal algorithms for queues

  05.04 Insertion and removal algorithms for stacks

06. Tree algorithms:

  06.01 Trees: basic definitions and classical problems

  06.02 Traversal and search algorithms for binary trees

  06.03 Search, insertion and removal algorithms for binary search trees

  06.04 Balancing criteria for binary search trees

  06.05 Search, insertion and removal algorithms for red-black binary search trees

07. Graph algorithms:

  07.01 Graphs: basic definitions and classical problems

  07.02 Traversal and search algorithms for graphs

  07.03 Topological sorting algorithm for direct acyclic graphs

  07.04 Strongly connected component algorithm for graphs

  07.05 Kruskal algorithm

  07.06 Prim algorithm

  07.07 Properties of the shortest path

  07.08 Bellman-Ford algorithm

  07.09 Dijkstra algorithm

  07.10 Floyd-Warshall algorithm

08. String algorithms:

  08.01 Strings: basic definitions and classical problems

  08.02 String matching naive algorithm

  08.03 Edit distance computation algorithm

  08.04 Longest common subsequence algorithm

09. Selection and order statistics:

  09.01 Basic definitions and problems

  09.02 Heapselect

  09.03 Randomized selection

  09.04 Deterministic selection

10. Algorithmic techniques:

  10.01 Divide-and-conquer technique

  10.02 Dynamic programming

  10.03 Greedy technique

  10.04 Backtracking technique

11. Laboratory activity:

  11.01 C language fundamentals: recall, editing, compilation, debugging

  11.02 Pseudorandom number generators: rand and srand functions

  11.03 Algorithms complexity experimental evaluation: timing and counters

  11.04 Experimental comparison of sorting algorithms for arrays

  11.05 Experimental comparison of search algorithms for binary trees

  11.06 Implementation of graph algorithms: breadth-first and depth-first traversal algorithms, Dijkstra algorithm

  11.07 Implementation of string algorithms: Edit Distance and LCS

Programmazione degli Elaboratori, Analisi Matematica.

Modalità didattiche

Lezioni teoriche ed esercitazioni di laboratorio, sia in presenza che a distanza.

English version: theory lectures and laboratory exercises, both face-to face and on-line.

Testi di studio

Cormen, Leiserson, Rivest, Stein, "Introduzione agli Algoritmi e alle Strutture Dati", McGraw-Hill, 2005.

(Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2001.)
Demetrescu, Finocchi, Italiano, "Algoritmi e Strutture Dati", McGraw-Hill, 2004.

Crescenzi, Gambosi, Grossi, "Strutture di Dati e Algoritmi", Pearson/Addison-Wesley, 2006.
Sedgewick, "Algoritmi in C", Pearson/Prentice Hall, 2002.

(Sedgewick, "Algorithms in C", Addison-Wesley, 1997.)

Modalità di
accertamento

Progetto individuale di laboratorio, prova scritta e prova orale .

English version: Individual project, written exam, and oral exam.

Disabilità e DSA

Le studentesse e gli studenti che hanno registrato la certificazione di disabilità o la certificazione di DSA presso l'Ufficio Inclusione e diritto allo studio, possono chiedere di utilizzare le mappe concettuali (per parole chiave) durante la prova di esame.

A tal fine, è necessario inviare le mappe, due settimane prima dell’appello di esame, alla o al docente del corso, che ne verificherà la coerenza con le indicazioni delle linee guida di ateneo e potrà chiederne la modifica.

L'insegnamento è erogato sia in presenza che a distanza nel Corso di Laurea in Informatica Applicata.

English version: The course is offered both face-to-face and on-line within the Laurea Degree Program in Applied Computer Science.