Il y a plusieurs décennies, nous avions des ordinateurs analogiques. Les ordinateurs modernes sont numériques. Et les ordinateurs quantiques? Est-ce analogique ou numérique? Je pose la question car le qubit peut être beaucoup de choses en même
Tout d'abord, je voudrais dire que mon texte ci-dessous peut contenir des erreurs, alors n'hésitez pas à signaler toute erreur dans ma formulation de la question. Considérons un calcul lambda non typé avec des booléens et des instructions if dont les termes sont donnés par cette syntaxe: t ::= v |...
Le problème de l'arbre couvrant délimité par est celui où vous avez un graphe non orienté et vous devez décider s'il a ou non un arbre couvrant tel que chaque sommet a un degré d'au plus .G ( V , E ) kkkkG(V,E)G(V,E)G(V,E)kkk Je me rends compte que pour le cas , c'est le problème du chemin...
En termes d'exécution asymptotique dans le pire des cas, quel problème NP-complet a l'algorithme le plus rapide connu (exact) et quel est l'algorithme? Existe-t-il quelque chose de plus rapide que ?O ( n2∗
J'ai une question très générique à poser. Elle est liée à la recherche. Je m'intéresse à la théorie des graphes. J'ai fait un cours dedans. J'ai fait quelques sujets liés à la théorie des graphes comme point de vue de le faire en tant qu'étudiant en mathématiques et j'ai également étudié certains...
Pardonnez la naïveté qui sera évidente dans la façon dont je pose cette question ainsi que dans le fait que je la pose. Les mathématiciens utilisent généralement car c'est la base la plus simple / la plus agréable en théorie (en raison du calcul). Mais les ordinateurs semblent tout faire en...
Il y a beaucoup de détails sur les ajouteurs d'anticipation de portage tels que Kogge-Stone, Lander-Fischer, etc. dans les cours CS du collège. Ils sont décrits comme «courants dans l'industrie». Cependant, je ne trouve aucune preuve (à part peut-être la chaîne de transport Manchester) de ces...
Je suis tombé sur cette question: "Donnez des exemples de deux langues régulières dont leur union ne produit pas une langue régulière." C'est assez choquant pour moi parce que je crois que les langues régulières sont fermées sous l'union. Ce qui signifie pour moi que si je prends deux langues...
Je sais que cela peut sembler un peu hors de la boîte, en fait, je pensais toujours à l'intérieur de la boîte, mais récemment, j'ai pensé, peut-être parce que l'informatique offre un haut degré de liberté, sur les moyens de concevoir des programmes autres que ceux enseignés à l'université....
J'adore tout ce qui est temps de compilation et j'adore l'idée qu'une fois que vous compilez un programme, de nombreuses garanties sont faites concernant son exécution. De manière générale, un système de type statique (Haskell, C ++, ...) semble donner des garanties de compilation plus fortes que...
J'ai fait un peu de recherche sur Google et je suis venu un peu court. Je me demande quelles sont les principales raisons pour lesquelles les informaticiens, les programmeurs, étudient la réécriture de termes et / ou la réécriture de graphes de termes. Pour autant que je sache, cela aide simplement...
En lisant certains blogs sur la complexité de calcul (par exemple ici ), j'ai assimilé la notion qu'il est plus facile de décider si deux groupes sont isomorphes que de tester deux graphiques pour l'isomorphisme. Par exemple, sur la page indiquée, il est dit que l'isomorphisme des graphes est un...
Dans l'image ci-dessous, j'essaie de comprendre exactement ce que cette NFA accepte. Ce qui me déroute, c'est le saut à .q 0ϵϵ\epsilonq0q0q_0 Si un est entré, le système passe-t-il à la fois à et (l'état d'acceptation)?q 0 q 1000q0q0q_0 q1q1q_1 Si un est entré, le système passe-t-il à la fois à et...
Les tables de hachage parfaites dynamiques et les tables de hachage de coucou sont deux structures de données différentes qui prennent en charge les recherches O (1) les plus défavorables et les insertions et suppressions de temps O (1) attendues. Les deux nécessitent un espace auxiliaire O (n) et...
J'ai du mal à comprendre le problème de l'arrêt de Turing. Sa preuve suppose qu'il existe une machine magique qui pourrait déterminer si un ordinateur s'arrêterait ou ferait une boucle pour toujours pour une entrée donnée. Ensuite, nous attachons une autre machine qui inverse la sortie et nous...
L'objectif est de créer DFA à partir d'une expression régulière et l'utilisation de "Exp régulière> NFA> Conversion DFA" n'est pas une option. Comment faut-il s'y prendre? J'ai posé cette question à notre professeur mais il m'a dit que nous pouvions utiliser l'intuition et a gentiment refusé...
J'ai vu comment XOR-3-SAT est efficacement résoluble (par exemple, voir la section "XOR-satisfiabilité" dans l'entrée Wikipedia pour le problème de satisfiabilité booléenne ). Je me pose une question de base: XOR-k-SAT est-il efficacement résoluble, pour des formules avec des quantités variables de...
Il y a ce problème populaire [1] [2] en informatique qui consiste à trouver un nombre minimum de lignes droites couvrant un ensemble donné de points en 2D. Même si j'ai scanné de nombreux papiers, aucun d'entre eux n'a une motivation claire pour le problème. Quelle est l'utilité de résoudre ce...
C'est probablement une question stupide, mais je ne comprends tout simplement pas. Dans une autre question, ils ont proposé le théorème de dichotomie de Schaefer . Pour moi, il semble que cela prouve que chaque problème CSP est soit en P soit en NP-complet, mais pas entre les deux. Étant donné que...
Je suis curieux de savoir s'il existe des problèmes complets dans la classe de complexité Arthur-Merlin. Le graphique de non-isomorphisme (GNI) semble être l'exemple canonique d'un problème en AM, mais ce n'est probablement pas complet. Je suppose que je me demande aussi si un problème "complet"...