ER03 (2012) : Calculabilité sur les entiers et les réels : de l’œuvre de Turing à la recherche actuelle

Intervenants : Laurent Bienvenu, Alexander Shen

En cette année 2012, qui célèbre les 100 ans après la naissance d’Alan Turing, nous présenterons les bases de la théorie qu’il a contribué à fonder, celle de la calculabilité. Nous rappellerons les concepts de base (machines de Turing, fonctions calculables) pour arriver rapidement à présenter quelques résultats et techniques fondamentaux de la calculabilité.

Le programme (prévisionnel) du cours est le suivant.

  1. Rappels de concepts de base
    • Machines de Turing
    • Ensembles et fonctions calculables, ensembles récursivement énumérables
  2. Indécidabilité
    • Problème de l’arrêt. Indécidabilité, et many-one complétude
    • Autres exemples de problèmes indécidables équivalents à l’arrêt:
      équations diophantiennes, problème du mot dans les semi-groupes,
      logique du premier ordre, etc.
  3. Oracles et réductions
    • Machines de Turing à oracle
    • Réduction Turing, degrés de Turing
  4. Hiérarchie arithmétique
    • Le jump comme opérateur sur les degrés.
    • Lemme de Schoenfield
    • La hiérarchie arithmétique et ses liens avec l’opérateur de jump
    • Complétude des ensembles \Sigma^0_n et \Pi^0_n, exemples de problèmes complets
  5. Résultats avancés sur les degrés
    • Existence de degrés non comparables (2 preuves: par diagonalisation et probabiliste par le théorème de Sacks)
    • Existence de deux degrés r.e. par la méthode de priorité de Friedberg-Muchnik
    • Existence d’un degré de Turing minimal
    • (Plus si le temps le permet: degrés « low », « high » et leur existence)
  6. Calculabilité sur les réels
    • Définition des fonctions calculables sur les réels et leurs propriétés élémentaires
    • Analyse calculable: théorèmes effectifs et non-effectifs

Les exposés seront donnés en anglais.

Dates : 16 au 20/01/2011

Planning:

– Lundi: 10h30-12h cours/TD; 14h-16h30 cours/TD
– Mardi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD
– Mercredi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD
– Jeudi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD
– Vendredi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD

Examen vendredi jusqu’à 18h3o (à confirmer)

Correspondante locale : Natacha Portier

Complexité algorithmique

Programme de l’UE

What computing resources do we need to solve a computational problem? The computational complexity theory studies this question from a structural point of view. Building up on the Turing machine model, we will discover and study deterministic and nondeterministic complexity classes, space and time complexity and hierarchy, completeness, randomized algorithms classes, boolean circuits and counting classes.

 

Bibliography:

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak (mostly chapters 1 to 7)

more about computational complexity

 

De quelles ressources avons nous besoins pour résoudre un problème, faire un calcul ? La théorie de la complexité algorithmique étudie ce problème d’un point de vue structurel. En nous appuyant sur le modèle des machines de Turing, nous étudierons les classes de complexité déterministes et non déterministes, en temps et en espace, les hiérarchies entre ces classes, les problèmes complets, les algorithmes et classes probabilistes, les classes définies par les circuits ainsi que quelques notions sur les classes de comptage.

 

Bibliographie :

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, principalement les chapitres 1 à 7

Pour en savoir plus sur la théorie de la complexité algorithmique

https://fr.wikipedia.org/wiki/Théorie_de_la_complexité_(informatique_théorique)

Page du cours (for 2013-2014)

Intervenants

  • Omar Fawzi, MdC ENS Lyon