Quels sont les problèmes pratiquement insolubles dans le monde de la programmation ?

Question

Le problème du voyageur de commerce est dit être pratiquement "insoluble" lorsque le nombre de nœuds augmente.

Quels autres problèmes de programmation sont considérés comme insolubles ?

Answer 1

Si vous cherchez des problèmes similaires au problème du voyageur de commerce, je vous suggère de chercher sur Google les problèmes NP-complets. Il s'agit d'une classe de problèmes qui n'ont pas de solution efficace connue, c'est-à-dire un algorithme qui calcule le résultat en temps polynomial. Ce qui est intriguant avec la classe des problèmes NP, c'est que personne n'a été capable de montrer qu'un algorithme pour les résoudre. doit prennent un temps exponentiel. C'est peut-être la plus grande question non résolue en informatique.

Il convient toutefois de préciser qu'il est souvent assez facile de trouver a solution à un problème NP, l'affaire délicate est de trouver la optimal solution.

Voici une liste d'autres problèmes NP-complets :

• L'emballage des poubelles, comment remplir un récipient de manière à ce qu'un nombre optimal de choses puissent y entrer. Je connais un type qui dirige une entreprise qui aide les compagnies maritimes à emballer leurs navires de la meilleure façon possible. Son programme ne trouve pas la meilleure solution mais peut généralement aider à emballer les navires de manière plus intelligente que ce qui peut être fait manuellement.
• La résolution SAT, qui consiste à montrer qu'une formule propositionnelle est satisfaisable. Il s'agit d'un problème plutôt théorique, mais il est utilisé par Intel, entre autres, pour prouver automatiquement que la conception de leurs circuits est correcte. Les solveurs SAT sont de plus en plus performants de nos jours et peuvent résoudre des problèmes assez importants assez rapidement.
• L'ordonnancement, compte tenu d'un certain nombre de tâches à accomplir et d'un certain nombre de ressources nécessaires pour accomplir ces tâches, calcule la manière la plus efficace d'accomplir ces tâches. Les compagnies aériennes doivent souvent résoudre ce problème car elles disposent de ressources, de personnel et d'avions, qu'elles veulent utiliser le plus efficacement possible tout en assurant tous les vols. Des sociétés comme Jeppesen ont des programmes pour optimiser cela.
• Coloration des graphiques. Prenez un graphe non orienté et essayez de colorer chaque nœud de telle sorte que deux nœuds adjacents reliés par une arête n'aient pas la même couleur. Le but est d'utiliser le moins de couleurs possible. Cette méthode est utilisée par les compilateurs pour affecter des registres à des variables locales. Plus l'algorithme de coloration du graphe est bon, plus les variables sont placées dans des registres au lieu d'être en mémoire.

Je pourrais continuer, mais je pense que la plupart des autres problèmes que je connais sont plutôt théoriques. Vous feriez mieux de chercher sur Google par vous-même.

Answer 2

J'essaie de trouver un développeur qui est satisfait du code qu'il a écrit !

Answer 3

Comme de nombreuses personnes l'ont déjà répondu, l'ur-problème qui est impossible à résoudre est le problème de halting : écrire un programme H qui prend un programme P comme entrée et répond si le programme d'entrée P va tourner en boucle ou pas. Notez que notre programme H peut répondre correctement pour de nombreux programmes d'entrée, le défi est d'écrire un programme qui peut répondre à cette question pour todo programmes.

Pourquoi le problème du halting est-il insoluble ? La preuve est assez simple et plutôt amusante : Supposons que l'on puisse écrire le programme H ce qui résout le problème de la halte. (Le but est de montrer qu'en supposant cela, nous allons produire des résultats qui n'ont aucun sens, donc que notre hypothèse est erronée). Maintenant, construisez un programme EVIL qui utilise H comme une sous-routine. Nous pouvons écrire EVIL así:

EVIL p = if H p then loop
                else false

Une brève explication s'impose. EVIL prend un programme et si ce programme s'arrête, alors EVIL boucles. Si le programme d'entrée boucle indéfiniment, alors EVIL retourne faux.

L'étape suivante est vraiment cool : appliquer EVIL à lui-même ! La question est de savoir quelle sera la réponse de EVIL EVIL être ? Cela dépend clairement du fait que EVIL est en train de boucler pour toujours ou pas. Considérons les deux alternatives :

• Supposons que EVIL des boucles pour toujours. Mais quand on lui donne un programme en entrée, il doit retourner false depuis H a détecté que ça tournerait en boucle pour toujours. Mais en retournant false contredit ce que nous avons d'abord dit que EVIL des boucles pour toujours, donc cela ne peut clairement pas être le cas.

• Ok, alors qu'est-ce que EVIL ne fait pas de boucle. Eh bien, quand on alimente EVIL à lui-même, il tournera en boucle parce que H a retourné true . Nous avons donc une contradiction ici aussi.

Bummer ! Les deux alternatives ( EVIL boucles ou pas) conduit à des contradictions. Nos hypothèses doivent donc être erronées. Il n'existe pas de programme tel que H qui peut décider si une fonction s'arrête ou non.

---

Il existe de nombreux problèmes intéressants qui ne sont pas calculables et qui découlent du problème de la halte. Certains de mes préférés proviennent de la technologie des compilateurs. Par exemple : trouver le plus petit programme équivalent.

Un autre exemple est le suivant : étant donné que vous avez annoté votre programme avec des assertions, écrivez un programme qui vérifie si l'une des assertions sera violée au moment de l'exécution. Un tel programme est parfois appelé un vérificateur de modèle, et ils peuvent être vraiment utiles mais ils ne peuvent jamais être complets, c'est-à-dire qu'ils doivent parfois répondre "je ne sais pas" quand le problème devient trop difficile.

Answer 4

Je trouve le problème de sac à dos particulièrement intéressant car il s'applique à de nombreux domaines différents.

Answer 5

Obtenir les trois éléments suivants : portée (fonctionnalités), calendrier (échéancier), budget (ressources-développeurs) ; au lieu de "choisir deux".