Course Syllabus

Export

Al termine dell’insegnamento, gli studenti avranno conoscenze nel campo della teoria dei grafi ed in particolare su algoritmi efficienti per alcuni problemi fondamentali. Inoltre avranno conoscenze relative a complessità computazionale e alle tecniche algoritmiche associate, e competenze relative all’implementazione di algoritmi efficienti, anche euristici, su grafi di grandi dimensioni.

Conoscenza e comprensione

Questo insegnamento permetterà di comprendere come rappresentare grafi, anche di grandi dimensioni. Inoltre gli studenti acquisiranno conoscenza dei principali algoritmi su grafi, incluse alcune tecniche euristiche necessarie per trattare grafi di grandi dimensioni.

Capacità di applicare conoscenza e comprensione

Alla fine dell'insegnamento gli studenti saranno in grado di analizzare un problema concreto, modellarlo come problema computazionale su grafi, selezionare la tecnica algoritmica più adatta per la soluzione del problema.

Introduzione alla teoria dei grafi.
Problemi computazionali su grafi.
Tecniche di disegno di euristiche per grafi di grandi dimensioni.

  • Grafi: definizioni fondamentali. Rappresentazioni di grafi: liste di adiacenza, matrice di adiacenza. Strutture dati efficienti e succinte per le rappresentazioni.

Problemi su grafi

  1. Calcolo delle componenti connesse, biconnesse, triconnesse
  2. Matching
  3. Tagli e flussi
  4. Copertura minima, cricca massima, insieme indipendente massimo
  5. Cammino di Eulero, cammino Hamiltoniano e TSP
  6. Colorazione di grafi
  7. Isomorfismo di grafi
  8. Compressione di grafi
  9. Grafi planari e disegno di grafi

Tecniche euristiche e complessità computazionale

  1. Complessità parametrica. Algoritmi per la copertura di grafi
  2. Risolutori SAT
  3. Algoritmo di Lin-Kernighan
  4. Simulated Annealing
  5. Complessità di approssimazione.
  6. Particle Swarm Optimization
  7. Algoritmi Streaming
  8. Ant Colony

Teoria della computazione

Tutte le attività sono tenute in presenza e non vengono registrate nè trasmesse in streaming. L'insegnamento è erogato in Inglese. Le attività previste sono:

  • 24 lezioni da 2 ore svolte in modalità erogativa nella parte iniziale ed in modalità interattiva nella parte successiva

Il testo utilizzato è Graph Algorithms, una collezione curata di articoli di Wikipedia.

I docenti non distribuiranno il materiale utilizzato in classe. Gli studenti sono incoraggiati a seguire le lezioni e prendere appunti.

Primo semestre

L'esame consiste in una prova orale con domande aperte su tutti gli argomenti trattati nel corso.

La prova verrà valutata principalmente in base alla correttezza e alla completezza delle risposte fornite. Criteri secondari di valutazione saranno la capacità di contestualizzare le risposte rispetto agli altri argomenti trattati nell'insegnamento e all'utilizzo corretto dei formalismi.

Non sono previste prove in itinere.
Si ricorda che è necessario essere iscritti alle prove d'esame tramite segreterie online. Non ci saranno eccezioni al riguardo.

Su appuntamento con i docenti

SALUTE E BENESSERE | IMPRESE, INNOVAZIONE E INFRASTRUTTURE | CITTÀ E COMUNITÀ SOSTENIBILI
Export

The course will present some efficient algorithms concerning fundamental problems in graph theory.
Moreover, we will discuss some computational complexity aspects and the related algorithm design techniques, as well as techniques for implementing efficient (and heuristic) algorithms on large-scale graphs.

Knowledge and understanding
Student will learn how to represent standard graphs and large-dimension graphs, and they will learn some fundamental graph algorithms and heuristics techniques to tackle computational problems on small and large graphs.

Applying knowledge and understanding
At the end of the course, students will be able to model a real-world problem in terms of a graph problem, and to design specific algorithms to efficiently solve the problem.

Graph theory fundamentals.
Computational problems on graphs.
Heuristic approaches on large-scale graphs.

  • Graph: basic notions. Representation of graphs: adjacency lists, adjacency matrices. Efficient and succint data structures for graph representation.

Graph problems

  1. Connected components, bi- and tri- connected components
  2. Graph matching
  3. Cuts and flows
  4. Minimal cover, maximum clique, maximum independent set
  5. Eulerian path, Hamiltonian path, and Travelling Salesman Problem (TSP)
  6. Graph coloring
  7. Graph isomorphism
  8. Graph compression
  9. Graph planarity and graph drawing

Heuristic techniques and computational complexity

  1. Parametric complexity. Graph cover algorithms
  2. SAT solvers
  3. Lin-Kernighan algorithm
  4. Simulated Annealing
  5. Approximation complexity
  6. Particle Swarm Optimization
  7. Streaming Algorithms
  8. Ant Colony

Theory of computation

All activities are in-person and will be neither recorded nor streamed. The teaching language of this course is English. The activities will be:

  • 24 lectures, 2 hours each, with an initial part in unidirectional mode and a second part in interactive mode.

The text we will be using is Graph Algorithms, a collection of readings compiled from Wikipedia.

Lecture materials will not be distributed to the class; instead, you are encouraged to attend the lecture yourself and take your own notes.

First semester

The exam consists of an oral exam, with open-ended questions over all topics of the course.

The main criteria to evaluate the exam are correctness and completeness of the answers. Secondary criteria are the correct use of formal aspects and the ability to discuss how the answer is related to different course topics.
Beware that you must be registered via "segreterie online" to take the exam. If you are not registered, you will not allowed to take the exam. No exceptions will be made.

Office hourse are online.
You can book a meeting at:

GOOD HEALTH AND WELL-BEING | INDUSTRY, INNOVATION AND INFRASTRUCTURE | SUSTAINABLE CITIES AND COMMUNITIES
Enter

Key information

Field of research
INF/01
ECTS
6
Term
First semester
Activity type
Mandatory to be chosen
Course Length (Hours)
0
Degree Course Type
2-year Master Degreee
Language
English

Staff

    Teacher

  • Gianluca Della Vedova
    Gianluca Della Vedova
  • CZ
    Claudio Zandron

Students' opinion

View previous A.Y. opinion

Bibliography

Find the books for this course in the Library

Enrolment methods

Manual enrolments
Self enrolment (Student)

Sustainable Development Goals

GOOD HEALTH AND WELL-BEING - Ensure healthy lives and promote well-being for all at all ages
INDUSTRY, INNOVATION AND INFRASTRUCTURE - Build resilient infrastructure, promote inclusive and sustainable industrialization and foster innovation
SUSTAINABLE CITIES AND COMMUNITIES - Make cities and human settlements inclusive, safe, resilient and sustainable