J'ai le problème algorithmique suivant: Déterminer l'espace Turing complexité de reconnaître les chaînes d'ADN qui sont des palindromes Watson-Crick. Les palindromes Watson-Crick sont des chaînes dont le complément inversé est la chaîne d'origine. Le complément est défini par lettre, inspiré de...
Étant donné un entier et un ensemble de triplets d'entiers distincts trouver un algorithme qui trouve soit une permutation de l'ensemble telle que ou détermine correctement qu'aucune telle permutation n'existe. Moins formellement, nous voulons réorganiser les nombres de 1 à ; chaque triple dans...
Je comprends qu'un chiffre d'église ressemble à (... n fois ...) . Cela ne signifie rien de plus que "la fonction appliquée fois à la fonction ". λ s . λ z . s scncnc_nλ s . λ z. sλs.λz.s\lambda s. \lambda z. ss n zszszs\;zsssnnnzzz Une définition possible de la fonction est la suivante: . En...
Dans de nombreux textes, une borne inférieure pour trouver le ème plus petit élément est dérivée en utilisant des arguments utilisant des médianes. Comment puis-je en trouver un en utilisant un argument adversaire?kkk Wikipedia dit que l'algorithme du tournoi s'exécute en , et est donné comme borne...
Soit A et B des langues avec A ⊆ B, et B est reconnaissable par Turing. A ne peut-il pas être reconnu par Turing? Si oui, y a-t-il un
Mon livre dit ceci Si un problème de décision B est dans P et A se réduit à B, alors le problème de décision A est dans P. Un problème de décision B est NP-complet si B est dans NP et pour chaque problème dans A dans NP, A se réduit à B. Un problème de décision C est NP-complet si C est dans NP et...
Il est bien connu que les polygones monotones jouent un rôle crucial dans la triangulation des polygones . Définition: Un polygone dans le plan est appelé monotone par rapport à une droite , si chaque ligne orthogonale à coupe au plus deux fois.L L PPPPLLLLLLPPP Étant donné une ligne et un polygone...
Sera-t-il nécessaire de changer les définitions de la sécurité si nous avons des ordinateurs quantiques? Quelles constructions cryptographiques vont casser? Connaissez-vous une enquête ou un article qui explique ce qui sera nécessaire pour
En raison de la nature de la question, je dois inclure beaucoup d'informations de base (parce que ma question est: comment puis-je restreindre cela?) Cela dit, cela peut être résumé (à ma connaissance) comme: Quelles méthodes existent pour trouver des optimums locaux sur des espaces de recherche...
J'essaie de travailler sur une tâche (tirée du livre Algorithms - par S. Dasgupta, CH Papadimitriou et UV Vazirani , Chap 8, problème 8.6a), et je paraphrase ce qu'il dit: Étant donné que 3SAT reste NP-complet même lorsqu'il est limité à des formules dans lesquelles chaque littéral apparaît au plus...
Existe-t-il un moyen d'estimer la quantité de données ajoutées au World Wide Web chaque seconde? Y a-t-il des études à ce
Y at - il un besoin pour être infini indécidable?L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* Je veux dire que si nous choisissons une langue être une version finie bornée de , c'est-à-dire , ( ), avec . Est-il possible que soit un langage indécidable? L ⊆ Σ ∗ | L ′ | ≤ N N ∈ N L ′ ⊂ L L ′L′L′L' L⊆Σ∗L⊆Σ∗L\subseteq...
Y a-t-il des avantages à avoir plus de 2 couches cachées dans un réseau neuronal? J'ai vu des endroits qui le recommandent, d'autres prouvent qu'il n'y a aucun avantage. Lequel a
Formulation alternative Je suis venu avec une formulation alternative au problème ci-dessous. La formulation alternative est en fait un cas particulier du problème ci-dessous et utilise des graphiques bipartites pour décrire le problème. Cependant, je crois que la formulation alternative est...
Je me moquais de la démo de Google Blocky Maze et je me souvenais de l'ancienne règle selon laquelle si vous voulez résoudre un labyrinthe, gardez simplement votre main gauche contre le mur. Cela fonctionne pour tout labyrinthe simple connecté et peut être mis en œuvre par un transducteur fini. Que...
J'obtiens la preuve de passer d'un énumérateur à une machine de Turing (continuez à exécuter l'énumérateur et voyez si cela correspond à l'entrée) mais je ne vois pas comment fonctionne l'autre sens. Selon mes notes et le livre (Intro to the Theory of Computation - Sipser), pour obtenir...
J'ai un problème dans mon esprit, je pense que c'est un problème de PNJ mais je ne sais pas comment le prouver. Voici le problème: Il y a k îles dans un lac très grand, et il y a n pontons en forme d' éventail. Ces pontons sont de la même taille mais ont des directions initiales différentes et sont...
Il est prouvé que les réseaux de neurones avec des poids rationnels ont la puissance de calcul de la calculabilité universelle de Turing Machine Turing avec des réseaux de neurones . D'après ce que j'ai obtenu, il semble que l'utilisation de poids réels donne encore plus de puissance de calcul,...
Pour un graphe planaire donné noyé dans le plan, défini par un ensemble de segments de droite , chaque segment est représenté par ses extrémités . Construisez une structure de données DCEL pour la subdivision planaire, décrivez un algorithme, prouvez son exactitude et montrez la complexité.G ( V,...
J'ai étudié le coefficient de corrélation de rang du Spearman .ρ = ∑je( xje- x¯) ( yje- y¯)∑je( xje- x¯)2∑je( yje- y¯)2-------------------√ρ=∑je(Xje-X¯)(yje-y¯)∑je(Xje-X¯)2∑je(yje-y¯)2\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2...