1. Home
  2. Education
  3. Degree programme courses
  4. Algorithms and Complexity

Algorithms and Complexity

A.Y. 2018/2019
6
Max ECTS
48
Overall hours
SSD
INF/01
Language
Italian
Learning objectives
Il corso consiste nella discussione di algoritmi di approssimazione per problemi NP-difficili; difficoltà di approssimazione dei problemi (in particolare, di alcuni affrontati nella prima parte); cenni della teoria della complessità di approssimazione (in particolare, il PCP); strutture dati succinte.
Expected learning outcomes
Undefined

Lesson period: First semester

Lessons timetable

Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi

Exams calendar

Single course

This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.

Search a single course
Course syllabus and organization

Milan

Responsible
Vigna Sebastiano
Lesson period
First semester
ATTENDING STUDENTS
Course syllabus
- Approximation algorithms for NP-hard problems.
- Proofs of hardness of approximation using the gap method.
- PCP and related inapproximability results.
- Succinct data structures
Website
NON-ATTENDING STUDENTS
Course syllabus
- Approximation algorithms for NP-hard problems.
- Proofs of hardness of approximation using the gap method.
- PCP and related inapproximability results.
- Succinct data structures
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor: Vigna Sebastiano
Professor(s)