top of page

Complexité

avec Enrico PORRECA et Nathanael EON

Responsable UE: Di Molfetta

Objectif: Principales techniques de conception et analyse d'algorithmes pour les problèmes polynomiaux et les problèmes NP-complets. Complexité de l'approximation, du comptage. Complexité paramétrée. Classes probabilistes.

TD 1 Ordre de grandeur, codage, langage et problème   

TD 2 Machines de Turing

TD 3 La complexité est une fonction de la taille des entrées  

TD 4 Classes P et NP 

TD 5 The complexity cake 

TD 6 Contrôle Continu (1h) 

TD 7 Deviner, et charactérisation existentielle de NP

TD 8  Réductions, NP-difficulté, NP-complétude

TD 9  Révisions I 

TD 10  Révisions II

             

TP 1 Machines de Turing - Simulateur d'une Machine de Turing, ici 

     corrigé

TP 2 RACSO online judge

TP 3 Le réflexe minisat

​

​

​

​

Controle Continu: 2018 - 2019

TP noté: 2018 - 2019

Examen 1ère session: 2018 - --

Examen 2ème session: --

​

​

​

La presentation du 10 Octobre 2018 faite par Antonio E. Porreca. "Membrane Computing": téléchargez-la ici

​

​

Bibliographie:

​

- Perifel, Sylvain. Complexité algorithmique. 2014.

Envie de faire un stage en théorie de la complexité? N'hésitez pas à contacter les membres de notre équipe de calcul naturel CaNa ou à m'écrire, on en discutera ensemble (bientôt une liste de stages proposés).

More to explore:

​

- S. Aaranson web site-  Quantum Complexity and Computation. Un article interessant sur la question: ici

-Complexity zoo: glossaire de toutes les classes de complexité connues.

​

A suivre un video publié par #hackerdashery comme intro aux classes de complexité.

bottom of page