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. Complessità computazionale. 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. Copertura minima, cricca massima, insieme indipendente massimo
  4. Cammino di Eulero, cammino Hamiltoniano e TSP
  5. Colorazione di grafi
  6. Isomorfismo di grafi
  7. Compressione di grafi

Tecniche euristiche e complessità computazionale

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

Teoria della computazione

Lezioni frontali

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.

Su appuntamento con i docenti

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. Computational complexity. 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. Minimal cover, maximum clique, maximum independent set
  4. Eulerian path, Hamiltonian path, and Travelling Salesman Problem (TSP)
  5. Graphg coloring
  6. Graph isomorphism
  7. Graph compression

Heuristic techniques and computational complexity

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

Theory of computation

Lectures

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.

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

Enter

Key information

Field of research
INF/01
ECTS
6
Term
First semester
Activity type
Mandatory to be chosen
Course Length (Hours)
48
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)