Toujours aussi...pédagogique, clair, lumineux...Rendre les graphes à la portée de tous, c'est une Vraie réussite !!! Votre livre est de la même veine: un régal ! Merci beaucoup pour votre travail. J'espère que vos étudiants mesurent leur chance !!
bjr, vos explications sur la theorie des graphes est une mine, et j'espere qu'elle deviendra une reference d'apprentissage, je voudrais vous poser une question a propos des problemes np-complets, comme ils sont des probleme different il ya surement un moyen de les resoudre par des methodes approchees l'une de l'autre d'ou p=np, mais pourqoi on dit que c'est une menace pour la securite informatique alors qu'on est pas entrains de parler de vitesse de chercher un code, hach ....., on parle juste de moyen court pour resoudre un probleme
La sécurité des algorithmes utilisés pour protéger les systèmes informatiques est souvent basé sur des problèmes difficiles à résoudre. Si quelqu'un montrait que P=NP alors il est probable que certains de ces problèmes pourraient être résolus et, du coup, la sécurité de certains systèmes serait compromises.
merci pour vos explications j'ai mis un pouce pour vous encourager. A un moment dans la vidéo vous dites qu'il n'y a pas d'algorithme pour ce probleme. Il semblerait que ce soit une erreur et je vous invite a voir celui ci cordialement. Algorithme de Brélaz - Ordonner les sommets par ordre décroissant de degrés. - Colorer un sommet de degré maximum avec la couleur 1. TantQue il y a des Sommets non colorés Faire - Choisir un sommet avec DSAT maximum (en cas d'égalité, choisir un sommet de degré maximal. - Colorer ce sommet avec la plus petite couleur possible Fin TantQue DSAT(v)= nombre de couleurs différentes dans les sommets adjacents à
Bonjour. Ce que je voulais dire dans ma vidéo est qu'il n'y a, à ce jour, pas d'algorithme connu de coloration qui aient les deux propriétés suivantes : 1/ Une complexité polynomiale. 2/ Qui construise une coloration optimale (utilisant un nombre minimal de couleurs). Le problème de décision associé à ce problème est NP-complet. Dans une autre vidéo je décris un algorithme glouton bien connu qui est satisfait le point 1/ mais pas le point 2/ (comme celui que vous décrivez).
Mon livre est encore en vente. Ici par exemple www.amazon.fr/découverte-graphes-algorithmes/dp/2759818306/ref=sr_1_1?__mk_fr_FR=ÅMÅŽÕÑ&dchild=1&keywords=Graphes+laforest&qid=1611854779&sr=8-1