Aller au menu Aller au contenu
Une voie, plusieurs choix
Informatique et Mathématiques appliquées
Une voie, plusieurs choix

> Formation > Cursus ingénieur

Advanced algorithms approximation parallel and randomized algorithms - Complexity - 4MMALGA6

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In
  • Number of hours

    • Lectures : 16.5
    • Tutorials : 16.5
    • Laboratory works : -
    • Projects : -
    • Internship : -
    • Written tests : -
    ECTS : 3.0
  • Officials : -

Goals

This course presents the complexity theory (lower bounds, complexity classes and reduction, NP classification) and presents the main techniques to design efficient algorithms: parallel, randomized and approximation algorithms, heuristics.
The course is coupled to a practical project on the programming of a multi-players game in C++.

Content

1. Machine models, Problem Complexity. Heuristics (e.g. alpha-beta)
2. Complexity; lower bounds; reduction.
3. Complexity classes P, NP, NP-complete.
4. Approximation algorithms. APX classes.
5. Randomized Algorithms. [BRZ]PP classes.
6. Parallel Algorithms. [ RZ][AN]C classes.
7. Interactive algorithms and proofs (IP). Polynomial hierarchy.

Prerequisites

Very good understanding of cost analysis for simple sequential algorithms (iterative / loops, recursive / divide and conquer).
Prerequisites: Algorithms and programming (1st year, 3MMALG2), elementary notions on graphs (3MMRO) and on computation models (3MMTL2).

Tests

One individual written examination (2h)(E: coef 3 / 4). One programming work with report (P: coef 1 / 4).

N1=3/4E1+1/4P
N2=3/4E2+1/4P

Calendar

The course exists in the following branches:

  • Curriculum - Math. Modelling, Image & Simulation - Semester 8
  • Curriculum - Information Systems Engineering - Semester 8
  • Curriculum - Financial Engineering - Semester 8
see the course schedule for 2020-2021

Additional Information

Course ID : 4MMALGA6
Course language(s): FR

The course is attached to the following structures:

You can find this course among all other courses.

Bibliography

S. Arora, B. Barak, Computaional complexity: a modern approach, 2009
P. Berlioux, M.-P. Cani, A. Lux, R. Mohr, D. Naddef, J.-L. Roch : Algorithmique II.. Polycopié ENSIMAG
T. Cormen, C.E. Leiserson, R. Rivest, C. Stein : Introduction to Algorithms, 2nd edition, 2001

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

Date of update January 15, 2017

Université Grenoble Alpes