Skip to main content
If you continue browsing this website, you agree to our policies:
  • Condizioni di utilizzo e trattamento dei dati
Continue
x
If you continue browsing this website, you agree to our policies:
  • Condizioni di utilizzo e trattamento dei dati
Continue
x
e-Learning - UNIMIB
  • Home
  • More
Listen to this page using ReadSpeaker
You are currently using guest access
 Log in
e-Learning - UNIMIB
Home
Percorso della pagina
  1. Science
  2. Master Degree
  3. Informatica [F1802Q - F1801Q]
  4. Courses
  5. A.A. 2022-2023
  6. 2nd year
  1. Large-Scale Graph Algorithms
  2. Summary
Insegnamento Course full name
Large-Scale Graph Algorithms
Course ID number
2223-2-F1801Q162
Course summary SYLLABUS

Course Syllabus

  • Italiano ‎(it)‎
  • English ‎(en)‎
Export

Obiettivi

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.

Contenuti sintetici

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

Programma esteso

  • 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

Prerequisiti

Teoria della computazione

Modalità didattica

Lezioni frontali

Materiale didattico

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.

Periodo di erogazione dell'insegnamento

Primo semestre

Modalità di verifica del profitto e valutazione

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.

Orario di ricevimento

Su appuntamento con i docenti

  • https://www.unimib.it/gianluca-della-vedova
  • claudio.zandron@unimib.it
Export

Aims

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.

Contents

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

Detailed program

  • 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

Prerequisites

Theory of computation

Teaching form

Lectures

Textbook and teaching resource

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.

Semester

First semester

Assessment method

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 hours

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

  • https://www.unimib.it/gianluca-della-vedova
  • claudio.zandron@unimib.it
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)

You are currently using guest access (Log in)
Policies
Get the mobile app
Powered by Moodle
© 2025 Università degli Studi di Milano-Bicocca
  • Privacy policy
  • Accessibility
  • Statistics