Syllabus del corso

Esporta

Conoscenza e capacità di comprensione
Questo insegnamento fornisce le conoscenze basilari e capacità di comprensione relativamente a:

  • tecnica algoritmica della programmazione dinamica per la risoluzione di problemi di ottimizzazione combinatoria
  • algoritmi paradigmatici per problemi di ottimizzazione combinatoria su sequenze, insiemi e grafi (Longest Common Subsequence, Weighted Interval Scheduling, ... e loro varianti) basati sulla tecnica della programmazione dinamica e proprietà della sottostruttura ottima.
  • tecnica algoritmica della programmazione greedy per la risoluzione di problemi di ottimizzazione combinatoria
  • strutture dati per insiemi disgiunti e, in base alla rappresentazione ed ai modi di implementare le operazioni, complessità computazionale degli algoritmi che ne fanno uso
  • algoritmi per il calcolo di alberi di copertura minimi (Kruskal, Prim)
  • algoritmi per il calcolo di cammini minimi su grafi (Floyd-Warshall e Dijkstra)
  • tabelle ad indirizzamento diretto e tabelle Hash
  • le classi P, NP e problemi NP completi
  • riduzione tra problemi

Conoscenza e capacità di comprensione applicate

Capacità di risolvere mediante la tecnica della programmazione dinamica problemi di ottimizzazione combinatoria (e versioni decisionali) su sequenze, insiemi e grafi, essendo in grado di

  • definire i sottoproblemi, i relativi coefficienti (variabili) e la struttura dati per memorizzarli.
  • riformulare il problema in termini ricorsivi fornendo il caso base ed il passo ricorsivo delle equazioni di ricorrenza
  • fornire il valore ottimo del problema sulla base dei valori di tutti i coefficienti
  • disegnare un algoritmo bottom-up efficiente per il calcolo dei valori di tutti i coefficienti e del valore ottimo, stabilendone la complessità computazionale
  • disegnare un algoritmo efficiente per la ricostruzione della soluzione del problema (sottosequenza di valore ottimo, sottoinsieme di valore ottimo, cammini sul grafo di valore ottimo)

Capacità di comprendere se e quando la tecnica di programmazione greedy puo' essere utilizzata con successo per risolvere un problema di ottimizzazione combinatoria.

Capacità di utilizzare le strutture dati per insiemi disgiunti nel contesto di algoritmi su grafi.

Capacità di costruire l'istanza di un problema a partire dall'istanza del problema dal quale esso è ridotto.

Autonomia di giudizio

Capacità di individuare la tecnica algoritmica e la struttura dati piu' idonee per risolvere in modo efficiente specifici problemi computazionali.

Abilità comunicative

Capacità di esporre in maniera chiara e rigorosa i contenuti teorici, le tecniche algoritmiche e gli algoritmi, incluse le dimostrazioni.

Capacità di apprendere

Capacità di ricercare e apprendere autonomamente nuovi algoritmi e strutture dati per rispolvere problemi computazionali.
Capacità di affrontare nuovi problemi computazionali.

L'insegnamento intende introdurre le principali tecniche algoritmiche (programmazione dinamica, greedy), con particolare attenzione agli aspetti di efficienza degli algoritmi, con i relativi strumenti di analisi. Verranno illustrati i principali algoritmi per risolvere vari problemi di ottimizzazione combinatoria specialmente su insiemi, sequenze e grafi, tra cui la ricerca di cammini minimi in un grafo pesato e la costruzione di alberi di copertura minimi.

1. Strumenti matematici (ripasso)

  • Crescita delle funzioni, notazioni asintotiche
  • Calcolo del tempo di esecuzione per algoritmi iterativi
  • Ricorsione e algoritmi ricorsivi
  • Ricorrenze e tempi di calcolo di algoritmi ricorsivi

2. Tecniche algoritmiche: Programmazione Dinamica (DP)

  • Esempi introduttivi
  • Caratteristiche principali - Ricorsione e proprietà della sottostruttura ottima.
  • Implementazione con matrici
  • Problemi di ottimizzazione combinatoria su sequenze, insiemi e grafi. Varianti decisionali. Proprietà della sottostruttura ottima.
  • Risoluzione mediante: definizione dei coefficienti (variabili) associati ai sottoproblemi e relativa struttura dati per memorizzarli, formulazione delle equazioni di ricorrenza (caso base e passo ricorsivo) per il calcolo dei valori di tutti i coefficienti, individuazione del valore ottimo sulla base dei valori di tutti i coeffiecienti, algoritmo bottom-up per il calcolo dei coefficienti e del valore ottimo, algoritmo di ricostruzione di una soluzione (sottosequenza, sottoinsieme o cammini di valore ottimo).

3. Tecniche algoritmiche: il metodo Greedy (goloso)

  • Esempi introduttivi .
  • Analogie e differenze con la tecnica della programmazione dinamica.
  • Sistemi di Indipendenza e Matroidi
  • Problema di massimo/minimo associato ad un sistema d'indipendenza pesato e relativo algoritmo greedy.
  • Teorema di Rado
  • Matroide Grafico

4\ Strutture dati per insiemi digiunti

  • Definizioni e operazioni.
  • Rappresentazione mediante liste concatenate e mediante foreste

5. Alberi di copertura minimi

  • Algoritmo generico
  • Algoritmo di Kruskal
  • Algoritmo di Prim

6. Problemi di cammino minimo

  • Algoritmo di Dijkstra
  • Algoritmo di Floyd-Warshall

7. Tabelle Hash

  • Tabelle ad indirizzamento diretto
  • Tabelle Hash

8. Introduzione a NP completezza e riduzioni

  • le classi P, NP e problemi NP completi
  • riduzione tra problemi: nozione di riduzione e vari esempi

Nozioni base di programmazione, algoritmi e strutture dati

Lezioni, esercitazioni ed esercitazioni laboratoriali in aula ed in presenza.

Le lezioni (32h) prevedono una modalità didattica erogativa.
Le ore di esercitazioni ed esercitazioni laboratoriali (20h+24h) prevedono una modalità didattica erogativa nella parte iniziale ed interattiva nella parte successiva.

La lingua del corso è l'italiano.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture dati, Ed. Mc. Graw Hill

Materiale integrativo (lucidi ed esercizi) disponibili sul sito e-learning.

Primo semestre

Prova scritta: Essa consiste di:

- esercizi relativi ai contenuti del corso

- domande aperte relative alle nozioni teoriche presentate a lezione

La valutazione totale massima derivante da esercizi e domande aperte è di 31 punti.
L'esame è considerato superato se la valutazione finale è di almeno 18.
Possono essere assegnati ulteriori 3 punti aggiuntivi (relativi ad una domanda/esercizio facoltativo).
Il punteggio finale dà automaticamente origine al voto in trentesimi (30 e lode per punteggi superiori a 30).

Prove parziali:
La prova scritta puo' essere sostituita da due prove parziali, che si tengono a meta' e fine corso.
Ogni prova parziale verte sugli argomenti trattati nella corrispondente parte del corso. Consiste di esercizi e domande aperte relative alle nozioni teoriche presentate a lezione.

Ogni prova parziale ha valutazione massima di 31 punti: la valutazione finale si ottiene dalla media dei voti delle due prove parziali. L'esame è considerato superato se la valutazione di ogni prova parziale è maggiore di 14 e la valutazione finale è di almeno 18.
Possono essere assegnati ulteriori 3 punti aggiuntivi (relativi ad una domanda/esercizio facoltativo).

Il punteggio finale corrisponderà esattamente al voto in trentesimi (30 e lode per punteggi superiori a 30).

su appuntamento

Esporta

Students will acquire knowledge of the main techniques for the design and analysis of algorithms and the ability to identify the most appropriate algorithmic techniques to efficiently solve specific computational problems.

Knowledge and understanding

This course provides basic knowledge and understanding on:

  • Dynamic Programming (DP) algorithmic technique for solving combinatorial optimization problems
  • paradigmatic algorithms for combinatorial optimization problems over sequences, sets, and graphs (Longest Common Subsequence, Weighted Interval Scheduling, ..., and their variants) based on the dynamic programming technique, optimal substructure property
  • Greedy algorithmic tecnique for solving combinatorial optimization problems
  • Disjoint-set data structure and computational complexity of the related algorithms on the basis of the representation of the data structure and the way of implementing its operations.
  • Algorithms for computing minimum spanning trees (Kruskal and Prim algorithms)
  • Algorithms for computing shortest path on graphs (Floyd-Warshall and Dijkstra algorithms)
  • direct-address tables and Hash tables
  • the classes P, NP and NP-complet problems
  • reducibility between problems

Ability to apply knowledge and understanding

Ability to solve combinatorial optimization problems (and their decision versions) over sequences, sets, and graphs by the dynamic Programming technique, being able to:

  • define the sub-problems, the related coefficients (variables) data structure for storing them,
  • reformulate the problem in recursive terms providing the base case and recursive step of the recurrence equations
  • provide the optimal value of the problem on the basis of the values of all coefficients
  • design an efficient bottom-up algorithm for computing the values of all coefficients and the optimal value
  • design an efficient algorithm for reconstructing a solution to the problem (subsequence, subset or paths of optimal value)

Ability to understand whether and when the greedy technique can be successfully employed for solving a combinatorial optimization problem.

Abilty to use disjoint-set data structure as far as graph algorithms are concerned.

Ability to build the instance of a problem starting from the instance of the problem from which the former has been reduce.

Making judgements

Ability to identify the most suitable algorithmic technique and data structures for efficiently solving specific computational problems.

Communication skills

Ability to explain in a clear and rigorous way, the theoretical contents, the algorithmic techniques and the algorithms discussed, including the proofs.

Learning Skills

Ability to independently search for and learn new algorithms and data structures to solve computational problems.
Tackle new computational problems.

The course will introduce the main algorithmic techniques (dynamic programming, greedy), with particular attention to the efficiency of the algorithms, with the main analysis methods. The main algorithms for several combinatorial optimization problems, especially over sets, sequences, and graphs will be presented, including minimum spanning trees construction and shortest path problems.

1. Mathematical tools (review)

  • Growth of functions, asymptotic notations
  • Execution time of iterative algorithms
  • Recursion and recursive algorithms
  • Recurrence equations and Execution times of recursive algorithms

2. Algorithmic Techniques: Dynamic Programming (DP)

  • Introductory examples
  • Main features - Recursion and optimal substructure property
  • Implementation with matrices
  • Combinatorial optimization problems over sequences, sets and graphs. Decision Variants. Optimal substructure property
  • Resolution by: definition of coefficients (variables) associated with the sub-problems and related data structure for storing them, formulation of recurrence equations (base case and recursive step) for computing the values of all coefficients, identification of the optimal value on the basis of the values of all coefficients, bottom-up algorithm for computing the values of all coefficients and the optimal value, algorithm for reconstructing a solution to the problem (subsequence, subset or paths of optimal value).

3. Algorithmic Techniques: Greedy method

  • Introductory examples
  • Similarities and differences with the dynamic programming technique
  • Independence systems and Matroids
  • Optimization (maximum/minimum) problem associated with a weighted independence system and related greedy algorithm
  • Rado Theorem
  • Graphic Matroid

4. Disjoint-set data structure

  • Definitions and operations
  • Linked list representation and forest representation

5. Minimum spanning trees

  • Generic algorithm
  • Kruskal algorithm
  • Prim algorithm

6. Shortest path problems

  • Dijkstra Algorithm
  • Floyd-Warshall Algorithm

7. Hash Tables

  • Direct-address tables
  • Hash tables

8. Introduction to NP-completeness and reducibility

  • The class P, NP and NP-complet problems
  • Reducibility between problems: reducibility notion and various examples.

Basic notions of programming, algorithms and data structures

Lectures, practice exercises, and classroom laboratory exercises all in presence.

Lectures (32h) will be carried out in unidirectional lecture mode.
Practice exercises and classroom laboratory exercises acivities (20h+24h) will be carried out with an initial part in unidirectional mode and a second part in interactive mode.

The course is in Italian.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture dati, Ed. Mc. Graw Hill

Further material and exercises are available through the e-learning website.

First semester

Written examination: It consitsts of

- exercises related to the main topics

- open questions on the theoretical aspects of the topics explained in the course

The maximum total score deriving from exercises and open questions is 31 points.
The exam is passed only if the final score is at least equal to 18.
3 additional points may be assigned (related to an optional exercise/open question).
The final score will just correspond to the usual score expressed in thirtieths (30 e lode if the final score is greater than 30).

Partial written examinations:
The written exam can be substituted by two partial written examinations in the middle and at the end of the course.

Each partial written examination is about the topics of the corresponding part of the course and it consists of exercises to the main topics and open questions on the related theoretical aspects.

Each partial written examination has a maximum score of 31/31: the final score of the exam is the average of the two partial scores. The exam is passed only if the score of each partial examination is greater than 14 and the final score is at least equal to 18.
3 additional points may be assigned (related to an optional exercise/open question).

The final score will just correspond to the usual score expressed in thirtieths (30 e lode if the final score is greater than 30).

By appointment

Entra

Scheda del corso

Settore disciplinare
INF/01
CFU
8
Periodo
Primo Semestre
Tipo di attività
Obbligatorio
Ore
0
Tipologia CdS
Laurea Triennale
Lingua
Italiano

Staff

    Docente

  • PB
    Paola Bonizzoni
  • AD
    Alberto Dennunzio
  • RR
    Raffaella Rizzi

Opinione studenti

Vedi valutazione del precedente anno accademico

Bibliografia

Trova i libri per questo corso nella Biblioteca di Ateneo

Metodi di iscrizione

Iscrizione manuale