Tests d'identité polynomiale est l'exemple type d'un problème connu pour être co-RP mais pas connu pour être en P . Sur les circuits arithmétiques , cela semble en effet difficile, car le degré du polynôme peut être rendu exponentiellement grand par quadrature répétée. Cette question aborde la...
J'ai fait le programme Haskell (non golfé) suivant pour le défi de golf de code de calculer les premières valeurs de A229037 .nnn Voici ma solution proposée pour calculer la ème valeur:nnn a n | n<1 = 0 | n<3 = 1 | otherwise = head (goods n) goods n = [x | x <- [1..], isGood x n] isGood x...
Je n'ai pas pu trouver de graphique décrivant ou de texte répondant à la question suivante: Existe-t-il une relation directe entre la complexité d'un algorithme (tel que le meilleur / pire cas de tri rapide) et la classe d'automates qui peuvent implémenter l'algorithme. Par exemple, existe-t-il une...
Je serais surpris si ce n'était pas un problème bien étudié, mais je ne sais pas quoi chercher d'autre à ce stade: on vous donne un ensemble de -vecteurs binaires . Le problème est de trouver un autre ensemble de vecteurs binaires , avec une taille minimale, de sorte que chaque vecteur de peut être...
Ma question porte essentiellement sur trois langues A, B et L, où L est A et B concaténés ensemble et B se révèle non régulier, est-il possible de trouver un A qui rend L
Dans la théorie des types podcast ep. 3 , Dan Licata affirme que le fait que pour chaque entrée, insertionsort et mergesort donnent le même résultat n'implique pas que le résultat serait égal lorsqu'il est utilisé en tant que fonctions d'ordre supérieur comme arguments d'une troisième fonction,...
Je comprends ce que c'est, mais je ne vois pas à quoi ça sert les algorithmes ou quoi que ce soit. Peut-être que je manque quelque chose. J'ai besoin que quelqu'un me donne un exemple de la façon dont il peut être utilisé pour que je puisse mieux le
J'ai besoin d'une structure de données pour stocker un numéro nnn d'éléments, dont chacun est associé à un moment différent tjetjet_i. nnn varie et même si elle a une limite supérieure théorique, elle est de plusieurs ordres de grandeur supérieure à ce qui est généralement utilisé. Grâce à ma...
Nous venons de terminer notre leçon "Constructibilité du temps" en classe la semaine dernière, et nous avons, par exemple, montré que nk,2nnk,2nn^k, 2^n sont entièrement constructibles dans le temps, c'est-à-dire qu'il existe une machine de Turing (déterministe multi-bandes) nnn donné, s'arrête...
J'essaie d'estimer la complexité d'un algorithme que j'ai écrit pour le décompilateur Reko , où j'essaie de "défaire" la transformation effectuée par un compilateur en une division entière par une constantex/nx/nx / n. Le compilateur a converti la division en une multiplication entière et un...
Je pensais que tout FOT est un sous-ensemble de FOL, mais cela ne semble pas être le cas, car FOL est complet (chaque formule est soit valide soit invalide), tandis que certains FOT (comme l'arithmétique d'entier linéaire) ne sont pas complets. Alors, FOL est-il plus expressif que n'importe quel...
À propos de l'état de l'art que je suis en avance sur la théorie des types, j'ai ces questions toutes liées à l'histoire des types. D'où est venue l'idée de Type ? (Il semble que tout commence lorsque Russell et Whitehead proposent un moyen d'éviter la contradiction que nous connaissons aujourd'hui...
L:={w∈{0,1}∗|L:={w∈{0,1}∗|L := \{w \in \{0,1\}^* | la longueur de est impaire 1 est au milieu dewww∧∧ \wedge w}w}w\} Donc l'alphabet est . Mon problème est que je ne peux pas suivre l'égalité des caractères avant et après . Un DFA limité pour une longueur inférieure à 6:{0,1}∗{0,1}∗\{0,1\}^*111...
Quand je lis à propos de la thèse de Church-Turing, il semble être une affirmation courante que «la réalité physique est calculable par Turing». Quelle est la base de cette réclamation? Y a-t-il des résultats théoriques dans ce sens? Pour le contexte, je suis un chercheur qui travaille sur des...
Dis, je voulais créer mon propre langage de programmation. En supposant que j'ai pris toutes les décisions sur la façon dont je veux qu'il ressemble et agisse, ai-je juste besoin d'écrire un compilateur pour cela? Par exemple, le code Java de haut niveau est-il autre chose que du texte et ce texte...
Karlheinz Brandenburg représente un encodeur MP3 comme celui-ci: Source: MP3 et AAC expliqués J'ai marqué la FFT car je ne sais pas trop pourquoi il est réellement nécessaire d'en effectuer une. Pourquoi le modèle psychoacoustique ne peut-il pas être appliqué aux soi-disant lignes après la...
Je un ensemble de nombres, et souhaite calculer le sous - ensemble maximal de telle sorte que la somme de deux quelconques des éléments de ce n'est pas divisible par un nombre entier . J'ai essayé de résoudre ce problème, mais j'ai trouvé la solution quadratique, qui n'est pas une réponse efficace....
L' autre jour, je lisais le document intitulé Fundamental Concepts in Programming Languages de C. Strachey , dans lequel j'ai lu quelque chose qui m'était assez étrange. Citant directement (avec la partie étrange surlignée par moi): Face à la situation telle qu'elle existe aujourd'hui, où il...
L'analyse du flux de données fonctionne sur un graphique de flux de contrôle. Lorsqu'un langage considéré prend en charge les exceptions, le graphique du flux de contrôle peut exploser. Quelles sont les techniques standard pour faire face à cette explosion? Pouvons-nous ignorer les bords induits...
Définition. Étant donné un graphiqueG = ( V, E)G=(V,E)G=(V,E) et deux sommets sss et ttt, le kkkproblème le plus court est de trouver le kkk chemins simples les plus courts entre sss et ttt dans gGG. Notez que la longueur de ces chemins n'est pas nécessairement égale, et les sommets sss et ttt...