EDIT AU 10/12/08: Je vais essayer de modifier la question pour que plus de personnes puissent partager leurs opinions. Nous avons besoin de vos contributions! Ce billet est inspiré de celui de MO: Exemples de fausses croyances courantes en mathématiques . Les grandes listes génèrent parfois un...
Le but de cette question est de recueillir des exemples d'informatique théorique où l'utilisation systématique des ordinateurs était utile. dans la construction d'une conjecture qui mène à un théorème, falsifier une conjecture ou une approche par preuve, construire / vérifier (des parties de) une...
Dans l'article de 1965 « Sur la complexité de calcul des algorithmes » de Hartmanis et Stearns, les auteurs supposent que si une machine de Turing en temps réel calcule le nombre réel dans, par exemple, la base 10, alors est soit un nombre rationnel soit un numéro transcendantal.rrrrrr Existe-t-il...
Existe-t-il des exemples naturels connus de problèmes d'optimisation pour lesquels il est beaucoup plus facile de produire une solution optimale que d'évaluer la qualité d'une solution candidate donnée? Par souci de concrétisation, nous pouvons considérer les problèmes d'optimisation résolubles en...
Soit un alphabet, c'est-à-dire un ensemble fini non vide. Une chaîne est une séquence finie d'éléments (caractères) de Σ . Par exemple, { 0 , 1 } est l'alphabet binaire et 0110 est une chaîne pour cet alphabet.ΣΣ\SigmaΣΣ\Sigma{0,1}{0,1} \{0, 1\}011001100110 Habituellement, tant que contient plus...