Canal-U

Mon compte
Inria

Quelques rudiments de calculabilité et de complexité


Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="http://www.canal-u.tv/video/inria/embed.1/quelques_rudiments_de_calculabilite_et_de_complexite.6494?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Auteur(s) :
GASTIN Paul

Producteur Canal-U :
Inria
Contacter le contributeur
J’aime
Imprimer
partager facebook twitter Google +

Les chapitres


Quelques rudiments de calculabilité et de complexité

Dans cet exposé, Paul Gastin, à travers des exemples concrets tel que le jeu du Sudoku, pose les deux problématiques fondamentales de l'algorithmique théorique que sont calculabilité et complexité, en définissant les notions et en donnant des jalons historiques de Hilbert à Gödel et Turing sur les grandes étapes des idées à ce sujet. Il définit les classes de complexité et donne quelques clés pour les évaluer.

Ce cours a été donné en juin 2010 lors des journées de formation à l'informatique organisées par l'INRIA à destination des professeurs de mathématiques d'Ile de France. Il est composé d'une présentation et d'une séance de questions-réponses.

 

commentaires


Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)
 

Dans la même collection

 Les réseaux WiFi : principes et performances
 L'intelligence ambiante
 Probabilité et Informatique : du modèle à l'algorithme
 L’analyse non lisse pour la modélisation et la simulation
 Intelligence artificielle et reconnaissance visuelle
 Objets connectés et communications sans fil : fuites de données et traçage
 Propagation d'espèces en biologie
 Apport de l'informatique à la génomique des cancers
 Modélisation de l'évolution des espèces
 Optimisation multi-objectifs
 Modélisation de nano-structures
 Architectures multi-coeurs, fiabilité et optimisation
 Langages et sémantique
 Statistique des événements extrêmes
 HPC, architectures et performances
 Smartphones et vie privée
 Arithmétique et calcul
 Grands systèmes informatiques
 Systèmes de prévision numérique en environnement
 Internet, un réseau de réseaux : fonctionnement et organisation
 Femmes et informatique
 Détection d'objets sur des images
 Bio-informatique et applications
 Internet et sécurité des données
 Les réseaux radio de la ville numérique : 1ère partie
 Les réseaux radio de la ville numérique : 2ème partie
 Géométrie numérique : du réel au virtuel : 1ère partie
 Géométrie numérique : du réel au virtuel : 2ème partie
 Théorie algorithmique de l'information
 Introduction à la calculabilité
 Technologie des moteurs de recherche sur le web : systèmes de gestion des données
 Les nombres et l'ordinateur
 Éléments d'algorithmique : mariages stables
 Interprétation de contenus d'images (Visual object recognition) : 1ère partie
 Interprétation de contenus d'images (Visual object recognition) : 2eme partie
 Modélisation mathématique en biologie : quand les gènes jouent la montre : 1ère partie
 Modélisation mathématique en biologie : quand les gènes jouent la montre : 2ème partie
 Comment se déplacent les robots ? : 1ère partie
 Comment se déplacent les robots ? : 2ème partie
 Reconnaissance d'activités en environnement "intelligent"
 Le hasard fait bien les choses : 1ère partie
 Le hasard fait bien les choses : 2ème partie
 Les robots, des puces plein la tête
 Epistémologie de l'informatique et applications
 Accès aux vidéos en ligne : comment repousser les limites des tuyaux ?: 1ère partie
 Accès aux vidéos en ligne : comment repousser les limites des tuyaux ?: 2ème partie
 Analyse de programmes : A quoi ça sert ? Comment ça marche ? : 1ère partie
 Analyse de programmes : A quoi ça sert ? Comment ça marche ? : 2ème partie
 Création de mondes virtuels animés : 1ère partie
 Création de mondes virtuels animés : 2ème partie
 Algorithmes et génomes : analyse informatique de l'information génétique : 1ere partie
 Algorithmes et génomes : analyse informatique de l'information génétique : 2ème partie
 Premiers principes des langages de programmation
 Les machines d'aujourd'hui et de demain
 Introduction à l'algorithmique, structures de contrôle et de données
 Résolutions numériques de problèmes, quelques grandes familles d'algorithmes
 Codage et cryptographie
 Algorithmes de transmission et de recherche de l'information dans les réseaux de communication
 La recherche d'information, les moteurs de recherche et le pageRank
 Expériences sur l’enseignement d’informatique en Tunisie
 Combien d’objets dans une image ?
 Pourquoi mon ordinateur calcule faux?
 L'imagerie satellitaire : une aide à l'enseignement de l'informatique
 Calcul en précision arbitraire
 L’informatique dans les sciences de la vie
 Expériences personnelles dans l’enseignement de l’informatique et du monde numérique
 Les algorithmes de classement utilisés dans les moteurs de recherche
FMSH
 
Facebook Twitter Google+
Mon Compte