Accueil/ expose
Définir et mesurer la complexité : la théorie algorithmique de l'information
jeudi 22 mai 2014

Loading the player...
Descriptif

Conférence de Jean-Paul Delahaye organisée par le département d'informatique.

La théorie de la calculabilité propose une définition de la complexité des objets numériques : la complexité de Kolmogorov (introduite en 1965). Celle-ci est une mesure du « contenu incompressible d’information », mais ne doit pas être conçue comme une mesure de la « richesse en structures ou en organisation » (complexité structurelle), qui elle serait mathématiquement définie par la profondeur logique de Bennett (introduite en 1977). Les applications de la complexité de Kolmogorov (par le biais des algorithmes de compression de données) sont maintenant nombreuses : classification de textes et de musiques, évaluation de la ressemblance entre séquences génétiques, comparaison d’images, repérage du plagiat, identification des spam, détection des tentatives d’intrusion dans les systèmes informatiques, etc. L’évaluation de la complexité structurelle est plus difficile en pratique, mais des progrès ont été faits récemment qui permettent d’envisager des applications comme pour la complexité de Kolmogorov.

Voir aussi


  • Le Bitcoin : quand la cryptographie réin...
    Jean-Paul Delahaye
  • Recent Progress in Leakage-Resilient Cry...
    Yevgeniy Dodis
  • Composer le temps
    Gérard Berry
  • Approximation Bounds for Sparse Principa...
    Alexandre D’Aspremont
  • Diviser-pour-Régner & Inférence Statisti...
    Michael I. Jordan
  • Logarithmes discrets dans les corps fini...
    Antoine Joux
  • Une théorie de l'information mentale
    Claude Berrou
  • Exponential Mechanism for Social Welfar...
    Sampath Kannan
  • Untangling knots using combinatorial opt...
    Benjamin Burton
  • De la convexité tropicale aux jeux répé...
    Stéphane Gaubert
  • A Foundation for Flow-Based Program Matc...
    Julia Lawall
  • Comment faire confiance à un compilateu...
    Xavier Leroy
  • Construction à large couverture de la re...
    Benoît Crabbé
  • Rendre la virgule flottante plus rigoure...
    Jean-Michel Muller
  • Approximations for stochastic graph rewr...
    Vincent Danos
  • Social Networks : a research vision and ...
    Peter Marbach
  • Three discrete geometric structures and ...
    Nabil Mustafa
  • From spanners to distance oracles and co...
    Laurent Viennot
  • Cognitive Computing
    Jérôme Pesenti
  • Vers les nouvelles bases de données pers...
    Serge Abiteboul
  • Structured Parallel Programming Primitiv...
    Vivek Sarkar
  • Manipuler les réseaux euclidiens
    Damien Sthelé
  • Réduction de modèles de voies de signali...
    Jérôme Feret
  • Le patient numérique personnalisé
    Nicholas Ayache
  • Scade 6: conception d'un langage de prog...
    Bruno Pagano
  • Co-Adaptive Instruments. Can we reinven...
    Wendy Mackay
  • Analyse de pire temps d’exécution et pro...
    Pascal Raymond
  • Chiffrer mieux pour (dé)chiffrer plus
    Anne Canteaut
  • New Results at the Crossroads of Convexi...
    Sébastien Bubeck
Auteur(s)
Jean-Paul Delahaye
Université Lille 1 - Sciences et Technologies
Professeur émérite

Plus sur cet auteur
Voir la fiche de l'auteur

Cursus :

Mathématicien de formation, Jean-Paul Delahaye est professeur d'informatique à l'université Lille 1 depuis 1988 et chercheur au sein du Laboratoire d'informatique fondamentale de Lille (UMR CNRS 8022), rattaché à cette université, depuis 1983.

Ses travaux de recherche portent sur la Théorie de la complexité, la finance computationnelle et la définition et perception du hasard.

Cliquer ICI pour fermer
Annexes

Dernière mise à jour : 02/07/2014