Le théorème d’Abiteboul-Vianu

Tout ce que vous voulez savoir sur ce théorème et plus important ce que veut dire complexité en temps et espace

Arthur Milchior à podcastscience : http://www.podcastscience.fm/emission/2017/05/24/podcast-science-295-le-theoreme-dabiteboul-vianu/
Mercredi 26 avril – Dossier de Arthur Milchior du podcast Trajectoires

Comment sait on si un problème informatique est vraiment complexe ? Parfois, on a des solutions qui coûtent chères (en temps de calcul, en espace mémoire, ou autre). Alors on continue de chercher des solutions, moins chères. Mais, rarement pour l’instant, on sait prouver qu’on a atteint l’optimale. La complexité computationnelle, une branche de l’informatique fondamentale, cherche ce qu’on peut dire des solutions optimales — que cette solution soit connue ou non aujourd’hui.

Les informathématiciens ont développés énormément de techniques tarabiscotés pour attaquer ce problème. En particulier, en 1991, Serge Abiteboul (invité du Podcast #266) et Victor Vianu ont publié le théorème d’Abiteboul-Vianu. Celui-dit donne une piste assez surprenante qui permettra peut-être un jour de montrer que certains problème ne pourront jamais être résolu rapidement. Ce théorème va servir de prétexte à Arthur Milchior (déjà venu parler de Calculabilité dans le podcast #290) pour vous faire découvrir ce domaine de recherche de l’informatique fondamentale.

» RDV en ligne le mercredi 26 avril 2017 à 20h30 sur live.podcastscience.fm/