Merci encore pour ce contenu de qualité. Il est encourageant de se rendre compte que la somme de nos précédentes connaissances, qui semblent parfois abstraites, permet d’en acquérir de nouvelles et de se rendre compte que le tout commence à faire plus de sens. C’est passionnant :)
Bonjour, je découvre via votre vidéo la définition de la classe NP avec la notion de certificat. Si je comprends bien on peut assimiler chaque certificat à un chemin d'exécution de la machine de Turing non déterministe. C'est bien ça ? Merci
Oui, ou à une sorte de clé permettant de produire un chemin d'exécution. En quelque sorte, on reporte sur les certificats le non-déterminisme du programme de la définition la plus courante. Remplacer le concept de complexité non déterministe polynomiale par celui de vérifiabilité polynomiale me parait plus intuitif, plus facile à appréhender en première approche.
bjr mr bailleux, peut tu m'orienter (pdf, memoir.....), je cherche une expilaction dans la reduction du sat au coloriage enla represenstant avec un graphe
Bonne vidéo ..Cependant vous auriez dû définir clairement les notions d'algorithme (machine) déterministe et non-déterministe or, c'est à ce niveau que commencent les confusions car pour certains étudiants NP= Non-polynomial . Les Problèmes de la classe NP ont ceci de particulier entre autres, que pour tenter de les résoudre lorsqu'on conçoit un algorithme pour obtenir un temps polynomial, malheureusement il a besoin d'être non-déterministe on ne sait pas les résoudre avec un algorithme déterministe polynomial et vérifiable en temps polynomial (le saint graal quoi!). il serait utile également de préciser en intro qu'il s'agit de classes de complexité liées uniquement au temps (d'exécution) car il en existe d'autres liées à l'espace (mémoire)
Il existe au moins deux manières de définir la classe NP : la définition via les certificats (ou via la notion de vérifiabilité polynomiale), et la définition via le non déterminisme. C'est la deuxième définition, faisant donc appel au non déterminisme, qui est la plus souvent utilisée, peut être parce qu'à l'origine, le concept a été introduit de cette manière, d'où le nom NP. Je pense que c'est une des raisons pour laquelle cette notion est souvent mal comprise, car le concept de machine non déterministe est très difficile à appréhender. Je trouve que l'approche basée sur la notion de certificat et de vérifiabilité polynomiale est plus facile à comprendre. Dans un cours d'introduction à la complexité des problèmes, c'est celle que j'utilise. Dans un cours plus approfondi, j'introduirais dans un second temps la notion de machine non déterministe. Mais en matière de pédagogie, il n'y a généralement pas "une" méthode adaptée à tous les apprenants. Et c'est justement tout l'intérêt de trouver en ligne des ressources variées présentant un même concept avec des points de vue différents.
Il n'existe pas de méthode pédagogique universelle qui marche avec tout le monde. Si vous pouvez me donner l'endroit exact de la vidéo où vous n'avez plus compris ce que je disais, ça pourrait m'être utile pour la prochaine version. D'autre part, vous pouvez aller voir la vidéo ua-cam.com/video/8TrIW-4kfRg/v-deo.html Elle est plus dans un esprit de vulgarisation, sauf une partie technique au milieu. Et ensuite peut-être revenir sur ma vidéo.
Cette vidéo m’a permis d’avoir plus de contexte pour comprendre mon cours de complexité, merci encore !
Merci encore pour ce contenu de qualité.
Il est encourageant de se rendre compte que la somme de nos précédentes connaissances, qui semblent parfois abstraites, permet d’en acquérir de nouvelles et de se rendre compte que le tout commence à faire plus de sens. C’est passionnant :)
Merci beaucoup pour cette vidéo instructive de qualité
Si c'était à refaire, je présenterais certaines parties différemment. Peut être un jour j'aurai le temps de m'y mettre.
Merci beaucoup ces éclaircissements sur les problèmes P et NP
Excellent cours. Bravo ! Une remarque : à la 17é minute, il me semble que la flèche qui pointe vers la bulle NP-complet n'est pas bien placée.
Bonjour,
je découvre via votre vidéo la définition de la classe NP avec la notion de certificat. Si je comprends bien on peut assimiler chaque certificat à un chemin d'exécution de la machine de Turing non déterministe. C'est bien ça ?
Merci
Oui, ou à une sorte de clé permettant de produire un chemin d'exécution. En quelque sorte, on reporte sur les certificats le non-déterminisme du programme de la définition la plus courante. Remplacer le concept de complexité non déterministe polynomiale par celui de vérifiabilité polynomiale me parait plus intuitif, plus facile à appréhender en première approche.
bjr mr bailleux, peut tu m'orienter (pdf, memoir.....), je cherche une expilaction dans la reduction du sat au coloriage enla represenstant avec un graphe
Il y a une explication ici. www.slideshare.net/felixcolella/3coloring-is-nphard
@@OlivierBailleux merci pour aide
merci beaucoup
merci pour la video
Bonne vidéo ..Cependant vous auriez dû définir clairement les notions d'algorithme (machine) déterministe et non-déterministe or, c'est à ce niveau que commencent les confusions car pour certains étudiants NP= Non-polynomial . Les Problèmes de la classe NP ont ceci de particulier entre autres, que pour tenter de les résoudre lorsqu'on conçoit un algorithme pour obtenir un temps polynomial, malheureusement il a besoin d'être non-déterministe on ne sait pas les résoudre avec un algorithme déterministe polynomial et vérifiable en temps polynomial (le saint graal quoi!).
il serait utile également de préciser en intro qu'il s'agit de classes de complexité liées uniquement au temps (d'exécution) car il en existe d'autres liées à l'espace (mémoire)
Il existe au moins deux manières de définir la classe NP : la définition via les certificats (ou via la notion de vérifiabilité polynomiale), et la définition via le non déterminisme. C'est la deuxième définition, faisant donc appel au non déterminisme, qui est la plus souvent utilisée, peut être parce qu'à l'origine, le concept a été introduit de cette manière, d'où le nom NP. Je pense que c'est une des raisons pour laquelle cette notion est souvent mal comprise, car le concept de machine non déterministe est très difficile à appréhender. Je trouve que l'approche basée sur la notion de certificat et de vérifiabilité polynomiale est plus facile à comprendre. Dans un cours d'introduction à la complexité des problèmes, c'est celle que j'utilise. Dans un cours plus approfondi, j'introduirais dans un second temps la notion de machine non déterministe. Mais en matière de pédagogie, il n'y a généralement pas "une" méthode adaptée à tous les apprenants. Et c'est justement tout l'intérêt de trouver en ligne des ressources variées présentant un même concept avec des points de vue différents.
il a précisé cela au cours de la vidéo
give me an approximate satisfiability problem algorithm and thank you
y a pas eu de démystification de mon coté.
Il n'existe pas de méthode pédagogique universelle qui marche avec tout le monde. Si vous pouvez me donner l'endroit exact de la vidéo où vous n'avez plus compris ce que je disais, ça pourrait m'être utile pour la prochaine version. D'autre part, vous pouvez aller voir la vidéo ua-cam.com/video/8TrIW-4kfRg/v-deo.html
Elle est plus dans un esprit de vulgarisation, sauf une partie technique au milieu. Et ensuite peut-être revenir sur ma vidéo.
mieux que XU.