Professor in Computer Science
IUF fellow
HDR Computer Science
PhD Quantum Theoretical Physics
MSc Theoretical Physics of Complex Systems
MSc Theoretical Economics
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
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
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é.
