Aller à : contenu haut bas recherche
 
 
EN     FR
Vous êtes ici:   UNIL > HEC Inst. > HEC App. > SYLLABUS
 
 

Computational Complexity I

  • Enseignant(s):   J.Duparc  
  • Titre en français: Compléxité computationnelle I
  • Cours donné en: anglais
  • Crédits ECTS: 3 crédits
  • Horaire: Semestre d'automne 2020-2021, 2.0h. de cours (moyenne hebdomadaire)
  •  séances
  • site web du cours site web du cours
  • Formations concernées:
    Maîtrise universitaire ès Sciences en management, Orientation marketing

    Maîtrise universitaire ès Sciences en management, Orientation comportement, économie et évolution

    Maîtrise universitaire ès Sciences en management, Orientation business analytics

    Maîtrise universitaire ès Sciences en management, Orientation stratégie, organisation et leadership

 

Objectifs

Understanding the basic concepts of computational complexity theory and being able to recognize typical P-complete, NP-complete, PSPACE-complete problems.

Contenus


The theory of Computational Complexity focuses on classifying problems that are solvable by computers, relatively to their difficulty -- which is usually measured in how much time is needed or how much space (memory) is required. This leads on one hand to the definition of various complexity classes, and on the other hand to the comparison of computable problems by mean of reduction relations.
This course introduces to the basic concepts of computational complexity theory and gives an overview of some of the major P and NP complete problems by going through the following notions:

- Strings, languages and decision problems

- Finite automata, determinism and non-determinism√A computation model: the Turing machine

- Recursive and recursively enumerable languages and functions

- The universal Turing machine and the halting problem

- Computable and uncomputable, decidability and undecidability

- Space and time efficiency, the big-Oh notation

- Deterministic time and P

- Non-deterministic time and NP

- Reducibility and completeness

- P-complete problems such as circuit value problem, Horn clauses, linear programming, Conway's game of life

- NP-complete problems such as SAT, 3SAT, travelling salesman problem, graph coloring, Hamiltonian path problem

- LOGSPACE, PSPACE, EXPTIME, EXPSPACE.

Références

- Sanjeev Arora, Boaz Barak "Computational Complexity: A Modern Approach"

- Oded Goldreich "P, NP, and NP-Completeness: The Basics of Computational Complexity"

- Christos H. Papadimitriou "Computational Complexity"

- Michael Sipser "Introduction to the Theory of Computation"

Pré-requis

none.

Evaluation

1ère tentative

Examen:
Sans examen (cf. modalités)  
Evaluation:

- 30' oral exam organized during the semester.

- exercise participation grade

Final grade: 1/2 oral exam + 1/2 participation grade

Rattrapage

Examen:
Oral 0h30 minutes
Documentation:
Autorisée avec restrictions
Calculatrice:
Autorisée avec restrictions
Evaluation:

- 30' oral exam

- exercise participation grade

Final grade: 1/2 oral exam + 1/2 participation grade



[» page précédente]           [» liste des cours]
 
Recherche


Internef - CH-1015 Lausanne - Suisse  -   Tél. +41 21 692 33 00  -   Fax +41 21 692 33 05
Swiss University