10 Problèmes algorithmiques Encore à résoudre - les nuls

Les algorithmes existent depuis des siècles, donc on pourrait penser que les scientifiques auraient déjà découvert et résolu tous les algorithmes. Malheureusement, le contraire est vrai. Résoudre un algorithme particulier présente souvent quelques questions de plus que l'algorithme ne résout pas et qui ne semble pas apparente jusqu'à ce que quelqu'un ait trouvé la solution.

Les algorithmes sont une série d'étapes utilisées pour résoudre un problème, et vous ne devez pas les confondre avec d'autres entités, telles que des équations. Un algorithme n'est jamais une solution à la recherche d'un problème. Personne ne créerait une série d'étapes pour résoudre un problème qui n'existe pas encore (ou pourrait ne jamais exister).

Cette liste concerne les problèmes algorithmiques qui pourraient servir à un but si quelqu'un devait trouver une solution pour eux.

Traiter les recherches de texte

De nombreuses recherches de texte impliquent l'utilisation d'expressions régulières - une sorte de raccourci qui indique à l'ordinateur ce qu'il doit trouver. La grammaire utilisée pour l'expression régulière dépend de la langue ou de l'application, mais vous trouvez des expressions régulières utilisées dans un certain nombre d'endroits, y compris les traitements de texte, les applications de messagerie, les boîtes de dialogue de recherche et toutes sortes d'autres termes pour une gamme d'éléments de texte.

L'un des problèmes actuels avec les expressions régulières est qu'il semble que chaque environnement d'application possède un ensemble de règles similaires, mais avec juste assez de différences pour rendre difficile la création d'un terme de recherche. Le problème de hauteur d'étoile généralisé cherche à découvrir s'il existe une syntaxe d'expression régulière généralisée. Si c'est le cas, l'algorithme résultant permettrait à quelqu'un d'apprendre une seule méthode de création d'expressions régulières pour effectuer des recherches.

Différencier les mots

Lorsque vous travaillez avec des caractères, un ordinateur voit des chiffres, pas des lettres. Les chiffres sont en fait juste une série de 0 et 1 à l'ordinateur et n'ont pas de sens. La combinaison de caractères en chaînes rend la série de 0 et de 1 plus longue. Par conséquent, comparer deux chaînes de caractères, ce qu'un humain peut faire en un coup d'œil, peut prendre du temps dans un ordinateur, et la confusion est probable entre les conjugués. Par exemple, à moins que vous soyez prudent dans la construction de l'algorithme, un ordinateur pourrait confondre enlist et écouter. Plus important, l'ordinateur aurait besoin de temps pour discerner la différence entre les deux. Le problème des mots de séparation cherche à trouver l'algorithme le plus petit (et le plus rapide) possible (un automate fini déterministe, DFN, dans ce cas) pour effectuer la séparation des mots.Le but est d'accepter un mot et de rejeter un autre, donné deux mots d'une longueur particulière.

Déterminer si une application va se terminer

L'un des problèmes proposés par Alan Turing en 1936 est de savoir si un algorithme, étant donné la description d'un programme et d'une entrée, pourrait déterminer si le programme s'arrêterait (le problème d'arrêt). Lorsque vous travaillez avec une application simple, il est facile de déterminer dans de nombreux cas si le programme va s'arrêter ou continuer à fonctionner dans une boucle sans fin. Cependant, à mesure que la complexité du programme augmente, il devient plus difficile de déterminer le résultat de l'exécution du programme avec une entrée donnée. Une machine de Turing ne peut pas faire cette détermination; le résultat est un code buggé avec des boucles infinies. Aucune quantité de tests utilisant la technologie actuelle ne peut résoudre ce problème.

Un hypercomputeur est un modèle informatique qui va au-delà de la machine de Turing pour résoudre des problèmes tels que le problème de l'arrêt. Cependant, de telles machines ne sont pas possibles en utilisant la technologie actuelle. Si c'était possible, vous seriez en mesure de leur demander toutes sortes d'impondérables auxquels les ordinateurs ne peuvent pas actuellement répondre. Cet article vous donne une bonne idée de ce qui se passerait si quelqu'un était capable de résoudre ce problème.

Créer et utiliser des fonctions unidirectionnelles

Une fonction unidirectionnelle est une fonction facile à utiliser pour obtenir une réponse dans un sens, mais presque impossible à utiliser avec l'inverse de cette réponse. En d'autres termes, vous utilisez une fonction à sens unique pour créer quelque chose comme un hachage qui apparaîtrait comme faisant partie d'une solution de cryptographie, d'identification personnelle, d'authentification ou d'autres besoins de sécurité des données.

L'existence d'une fonction unidirectionnelle est moins mystérieuse et plus une question de preuve. De nombreux systèmes de télécommunications, de commerce électronique et d'e-banking reposent actuellement sur des fonctions censées être unilatérales, mais personne ne sait vraiment si elles sont à sens unique. L'existence d'une fonction unidirectionnelle est actuellement une hypothèse, pas une théorie. Si quelqu'un était capable de prouver qu'une fonction unidirectionnelle existe, les problèmes de sécurité des données seraient plus faciles à résoudre du point de vue de la programmation.

Multiplier de très grands nombres

De très grands nombres existent dans de nombreux endroits. Par exemple, pensez à effectuer les calculs impliquant des distances vers Mars, ou peut-être Pluton. Des méthodes existent actuellement pour effectuer la multiplication sur de très grands nombres, mais elles ont tendance à être lentes car elles nécessitent plusieurs opérations à compléter. Le problème se produit lorsque les nombres sont trop grands pour tenir dans les registres du processeur. À ce stade, la multiplication doit se produire en plus d'une étape, ce qui ralentit considérablement les choses. Les solutions actuelles comprennent:

• algorithme de multiplication complexe de Gauss
• multiplication de Karatsuba
• méthodes de transformée de Fourier

Même si de nombreuses méthodes actuellement disponibles donnent des résultats acceptables, elles prennent du temps, et Lorsque vous avez beaucoup de calculs à effectuer, le problème de temps peut devenir critique. Par conséquent, la multiplication des grands nombres est l'un de ces problèmes qui nécessite une meilleure solution que ceux disponibles aujourd'hui.

Diviser une ressource équitablement

Diviser les ressources équitablement peut ne pas sembler difficile, mais les humains, étant le genre envieux, pourraient voir la ressource inégalement divisée à moins de trouver un moyen d'assurer à chacun que la division est juste. C'est le problème du gâteau-coupe sans envie. Bien sûr, quand vous coupez un gâteau, peu importe à quel point vous essayez de le faire, il y a toujours la perception que la division est injuste. Créer une répartition équitable des ressources est important dans la vie quotidienne pour minimiser les conflits entre les parties prenantes dans toute organisation, rendant tout le monde plus efficace.

Deux solutions existent déjà pour un problème de coupe de gâteau sans envie avec un nombre spécifique de personnes, mais aucune solution générale n'existe. Quand il y a deux personnes impliquées, la première coupe le gâteau et la seconde choisit la première pièce. De cette manière, les deux parties sont assurées d'une division égale. Le problème devient plus difficile avec trois personnes, mais vous pouvez essayer la solution Selfridge-Conway pour le problème. Cependant, après avoir atteint quatre personnes, aucune solution n'existe.

Réduction du temps de calcul de la distance d'édition

La distance d'édition entre deux chaînes est le nombre d'opérations nécessaires pour transformer une chaîne dans l'autre chaîne. Le calcul de la distance tourne autour des opérations de distance Levenshtein, qui sont la suppression, l'insertion ou la substitution d'un caractère dans la chaîne. Cette technique particulière voit l'utilisation dans les interfaces de langage naturel, la quantification de séquence d'ADN, et toutes sortes d'autres endroits où vous pouvez avoir deux chaînes similaires qui nécessitent une sorte de comparaison ou de modification. Un certain nombre de solutions à ce problème existent actuellement, toutes assez lentes. En fait, la plupart d'entre eux prennent un temps exponentiel, de sorte que le temps requis pour effectuer une transformation s'ajoute rapidement au point où les humains peuvent voir des pauses dans le traitement de l'entrée. La pause n'est pas si mauvaise lorsque vous utilisez un traitement de texte qui effectue des vérifications automatiques des mots et transforme un mot mal orthographié en mot correct. Cependant, lorsque vous utilisez des interfaces vocales, la pause peut devenir tout à fait perceptible et provoquer des erreurs chez l'opérateur humain.

Résolution rapide des problèmes

Alors que l'apprentissage automatique décolle et que nous comptons de plus en plus sur les ordinateurs pour résoudre les problèmes, la question de la rapidité avec laquelle un ordinateur peut résoudre un problème devient critique. Le problème P versus NP demande simplement si un ordinateur peut résoudre un problème rapidement lorsqu'il peut vérifier rapidement la solution au problème. En d'autres termes, si l'ordinateur peut raisonnablement vérifier qu'une réponse humaine à un problème est correcte en temps polynomial ou moins, peut-il également résoudre le problème lui-même en temps polynomial ou moins?

Cette question a été discutée à l'origine dans les années 1950 par John Nash dans des lettres adressées à la National Security Agency (NSA) et encore une fois dans des lettres entre Kurt Gödel et John von Neumann. En plus de l'apprentissage automatique (et de l'IA en général), ce problème particulier concerne de nombreux autres domaines, notamment les mathématiques, la cryptographie, la recherche algorithmique, la théorie des jeux, le traitement multimédia, la philosophie et l'économie.

Jouer le jeu de la parité

Au début, résoudre un jeu peut ne pas sembler utile dans la vie réelle. Oui, les jeux sont amusants et intéressants, mais ils ne fournissent pas vraiment de base pour faire quelque chose d'utile - du moins, c'est la théorie générale. Cependant, la théorie des jeux entre en jeu dans un grand nombre de scénarios de la vie réelle, dont beaucoup impliquent des processus complexes que quelqu'un peut comprendre plus facilement en tant que jeux que comme processus réels. Dans ce cas, le jeu aide les gens à comprendre la vérification automatisée et la synthèse du contrôleur, entre autres choses. Vous pouvez en savoir plus sur le jeu de parité. En fait, vous pouvez le jouer.

Comprendre les problèmes spatiaux

Pour replacer ce problème particulier dans son contexte, pensez à déplacer des boîtes dans un entrepôt ou à d'autres situations dans lesquelles vous devez considérer l'espace dans lequel les choses bougent. Évidemment, si vous avez beaucoup de boîtes dans un grand entrepôt et qu'elles ont toutes besoin d'un chariot élévateur à fourche, vous ne voulez pas essayer de trouver comment les stocker de manière optimale en les réorganisant physiquement. C'est ici que vous devez résoudre le problème en visualisant une solution.

Cependant, la question est de savoir si tous les problèmes spatiaux ont une solution. Dans ce cas, pensez à l'un des puzzles de ces enfants qui vous permet de mettre une photo ensemble en faisant glisser les petits carreaux autour. Il semble qu'une solution devrait exister dans tous les cas, mais dans certains cas, un mauvais point de départ peut entraîner une situation sans solution.

Des mathématiciens comme Sam Loyd utilisent souvent des puzzles pour illustrer des problèmes mathématiques complexes, dont certains n'ont pas de solution aujourd'hui. Visiter ces sites est amusant parce que vous avez non seulement des divertissements gratuits, mais aussi de la matière à réflexion. Les problèmes que ces puzzles soulèvent ont des applications pratiques, mais ils sont présentés de façon amusante.