sans etre force a comprendre ce que sont vraiment les classes de complexite j'aurais abandonner rapidement.
C'est probablement une question de caractère, et puis t'a du faire le choix de plus te concentrer sur les sujets présentés dans tes études, c'est une stratègie.
Quand on connait les principaux problemes NP-complets (SAT, voyageur de commerce, coloration de graphe...) on arrive a voir que les problemes qu'on essaye de resoudre sont equivalents a l'un de ceux-la.
Bien ce que je pensait : tu fait au feeling, comme font tout les programmeurs (même si ils vont dire "y'a pas d'algo adapté à de grande quantitées" au lieu de "np-complet").
Et sur wikipedia, ils vont trouver ca: Classe NP : c'est la classe des problèmes de décision pour lesquels la réponse oui peut être décidée par un algorithme non-déterministe en un temps polynomial par rapport à la taille de l'instance. Bon, donne ca a un lyceen de base qui se prend pour Blake Ross ("pas besoin de faire des etudes pour etre informaticien !") et regarde la tete qu'il fait :).
Et ensuite un problème np-complet c'est un problème qui a la même complexité que celui qui permet de trouver les clefs privées de GPG à partir des clefs publiques (la déf d'au dessus dit que c'est possible avec des ordinateurs quantiques (seuls ordinateur non déterministes dont j'ai entendu parler)).
[^] # Re: Enfin bon
Posté par un_brice (site web personnel) . En réponse au journal Les informaticiens précoces. Évalué à 1.
Bien ce que je pensait : tu fait au feeling, comme font tout les programmeurs (même si ils vont dire "y'a pas d'algo adapté à de grande quantitées" au lieu de "np-complet").
La wikipedia est un peu trop technique sur le coup... Heuresement il reste Google.
Ça: http://w3.ift.ulaval.ca/~abali/ift-17582/Semaine14/Complexit(...) , ça explique la notion de complexité.
Et ensuite un problème np-complet c'est un problème qui a la même complexité que celui qui permet de trouver les clefs privées de GPG à partir des clefs publiques (la déf d'au dessus dit que c'est possible avec des ordinateurs quantiques (seuls ordinateur non déterministes dont j'ai entendu parler)).