J'ai un petit problème pour comprendre la preuve du théorème de la hiérarchie temporelle (Hennie et Stearns, 1966) qui garantit l'existence d'un langage acceptable en mais non acceptable en pour toutes les fonctions , tel que est constructible dans le temps etU( n )U(n)U(n)T(n )T(n)T(n)T( n) , U( n...
Si vous avez une langue L, sans faire de preuves, existe-t-il un moyen de savoir si elle est reconnaissable ou co-reconnaissable ou décidable? Fondamentalement, tous les conseils ou astuces qui peuvent être utilisés pour le dire. Ou peut-être les modèles communs à rechercher pour savoir de quel...
Notre PC fonctionne-t-il comme machine de Turing? Le modèle d'une machine de Turing se compose d'une bande mémoire infinie, ce qui signifie des états infinis. Mais supposons que si notre PC a 128 Mo de mémoire et 30 Go de disque, il aurait 256 ^ 30128000000 états et donc, il a des états finis. Je...
Considérez ce problème: Étant donné un graphique non orienté G = ( V, E)g=(V,E)G = (V, E), trouver g′= (V′,E′)g′=(V′,E′)G' = (V', E') tel que: g′g′G' est un sous-graphique induit de ggG g′g′G' n'a pas de 3 cliques |V′||V′||V'| est maximal Donc, le moins de sommets doit être éliminé de ggG afin que...
De l'isomorphisme des graphes, nous savons que deux graphes A et B sont isomorphes s'il existe une matrice de permutation P telle que A = P× B ×P- 1A=P×B×P−1A = P \times B \times P^{-1} Donc, pour résoudre le problème, si deux graphes sont isomorphes, nous devons trouver une telle matrice de...
Laisser LLLêtre une langue régulière. Prouve-le: L+−−={w:∃u|u|=2|w|∧wu∈L}L+−−={w:∃u|u|=2|w|∧wu∈L}L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\} L++−={w:∃u2|u|=|w|∧wu∈L}L++−={w:∃u2|u|=|w|∧wu∈L}L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}...
Quel modèle parallèle théorique est le plus proche du modèle de programmation CUDA / OpenCL? Par exemple, il correspond dans une certaine mesure au modèle générique de machine d'accès parallèle parallèle (PRAM). Cependant, c'est trop générique, car cela rend abstraction les diverses latences...
J'essaie de comprendre (intuitivement) les deux termes «décidabilité» et «vérifiabilité». J'ai fait un nombre raisonnable de recherches et de lecture des différents textes sur lesquels je peux mettre la main. Cependant, leur compréhension intuitive semble m'échapper, spécialement pour le second....
Considérez le problème d'univers suivant . Le problème de l'univers. Étant donné un ensemble fini pour une classe de langages, et un automate acceptant le langage L , décidez si L = \ Sigma ^ * .ΣΣ\SigmaLLLL=Σ∗L=Σ∗L=\Sigma^* Dans [1], il est indiqué et prouvé que le problème de l'univers est...
Ces diapositives de cours esquissent une preuve queL = {unenbn∣ n ≥ 0 } ∪ {unenb2 n∣ n ≥ 0 }L={anbn∣n≥0}∪{anb2n∣n≥0}L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \} ne peut être accepté par aucun automate déterministe à refoulement. Malheureusement, les diapositives ne donnent...
Définir l' équivalence de Nérode sur une langueL⊆Σ∗L⊆Σ∗L \subseteq \Sigma^{*} comme u∼Lvu∼Lvu \sim_L v ssi uw∈L⇔vw∈Luw∈L⇔vw∈Luw \in L \Leftrightarrow vw \in L pour chaque w∈Σ∗w∈Σ∗w \in \Sigma^{*}. L'équivalence Nerode ∼L∼L{\sim}_L a un nombre fini de classes d'équivalence précisément lorsque...
Étant donné un graphique , trouvez sommets , dont la suppression aboutirait à un graphique avec la plus petite composante la plus grande. G=(V,E)G=(V,E)G = (V, E)kkk{v∗1,…,v∗k}{v1∗,…,vk∗}\{v^*_1,\dots,v^*_k\} Je suppose que pour grandet grand le problème est difficile (NP-difficile), mais je...
C'est quelque peu lié à une autre question que j'ai posée , mais je pense qu'elle est suffisamment différente pour justifier sa propre question. Je fais des recherches où j'essaie de trouver la structure des compléments d'une certaine classe de langages finis. Il est facile pour moi d'obtenir les...
Lors du calcul de la dépendance d'exécution à l'entrée, quels calculs sont pris en compte? Par exemple, je pense avoir appris que l'indexation des tableaux ainsi que les instructions d'affectation ne sont pas comptées,
Je travaille actuellement sur ma thèse de master, et c'est sur le clustering sur les graphes. Je travaille avec une idée utilisant des fourmis pour résoudre le problème. Je travaille actuellement sur l'implémentation et je me demande exactement comment bien représenter les bords du graphique....
Étant donné un tableau trié d'entiers, je veux trouver le nombre de paires qui totalisent . Par exemple, étant donné , le nombre de paires somme à zéro est .000{ - 3 , - 2 , 0 , 2 , 3 , 4 }{−3,−2,0,2,3,4}\{-3,-2,0,2,3,4\}222 Soit le nombre d'éléments dans le tableau d'entrée. Si j'utilise la...
Selon CLRS, les algorithmes de Prim sont implémentés comme ci-dessous - MST-PRIM(G,w,r)MST-PRIM(G,w,r)\mathtt{\text{MST-PRIM}}(G,w,r) pour chaque u∈V[G]u∈V[G]u \in V[G] faire key[u]←∞key[u]←∞\mathtt{\text{key}}[u] \leftarrow \infty π[u]←NILπ[u]←NIL\pi[u] \leftarrow \mathtt{\text{NIL}}...
Je suis un doctorant débutant. étudiant en informatique, et j'essaie de comprendre certains articles classiques de théorie des jeux, tels que ceux de Nash, Kalai et Smorodinsky. Mais j'ai du mal à comprendre les parties mathématiques. Il semble que ces articles ont été écrits par des...
Je recherche un algorithme qui fournit une chaîne canonique pour un graphique coloré donné. C'est à dire. un algorithme qui renvoie une chaîne pour un graphique, de telle sorte que deux graphiques obtiennent la même chaîne si et seulement s'ils sont isomorphes. En particulier, je recherche un...
Plusieurs algorithmes d'apprentissage automatique populaires tels que la régression logistique ou les réseaux de neurones nécessitent que ses entrées soient numériques. Ce qui m'intéresse, c'est comment vous faites fonctionner ces algorithmes sur des entrées non numériques (telles que des chaînes...