Considérons un graphe . Chaque arête a deux poids et . Trouvez un arbre couvrant qui minimise le produit . L'algorithme doit s'exécuter en temps polynomial par rapport à.G(V,E)G(V,E)G(V,E)eeeAeAeA_eBeBeB_e(∑e∈TAe)(∑e∈TBe)(∑e∈TAe)(∑e∈TBe)\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in...
Je veux prouver que le complément de { 0n1n∣ n ≥0 }{0n1n∣n≥0}\{0^n1^n \mid n \geq{} 0\} n'est pas régulier en utilisant des propriétés de fermeture. Je comprends que le lemme de pompage peut être utilisé pour prouver que { 0n1n∣ n ≥0 }{0n1n∣n≥0}\{0^n1^n \mid n \geq{} 0\}n'est pas une langue...
J'étudie récemment la conception de compilateurs. J'ai appris l'existence de deux types de grammaire: la grammaire LL et la grammaire LR. Nous savons également que chaque grammaire LL est LR, c'est-à-dire que la grammaire LL est un sous-ensemble approprié de la grammaire LR. Le premier est utilisé...
Je parcourais la définition de Wikipedia du langage contextuel et j'ai trouvé ceci: Chaque catégorie de langues est un sous-ensemble approprié de la catégorie directement au-dessus. Tout automate et toute grammaire dans chaque catégorie a un automate ou une grammaire équivalent dans la catégorie...
Étant donné et b , d ∉ { 0 } ,a , b , c , d∈ Na,b,c,d∈Na,b,c,d \in \mathbb Nb , d∉ { 0 }b,d∉{0}b,d \notin \{0\} uneb< cré⟺un d< c bab<cd⟺ad<cb \begin{eqnarray*} \frac a b < \frac c d &\iff& ad < cb \end{eqnarray*} Mes questions sont: Étant donné a , b , c , da,b,c,da,b,c,d En supposant...
Ceci est une question du Dragon Book. Voici la grammaire: S→AaAb∣BbBaS→AaAb∣BbBaS \to AaAb \mid BbBa A→εA→εA \to \varepsilon B→εB→εB \to \varepsilon La question demande comment montrer qu'il s'agit de LL (1) mais pas de SLR (1). Pour prouver qu'il s'agit de LL (1), j'ai essayé de construire sa...
J'ai entendu cette question d'interview demander beaucoup et j'espérais avoir des opinions sur les bonnes réponses: vous avez un gros fichier de 10+ Go et vous voulez savoir quel élément se produit le plus, quelle est la bonne façon pour faire ça? Itérer et garder une trace dans une carte n'est...
Considérons une séquence de nnn flips d'une pièce non biaisée. Soit HiHiH_i la valeur absolue de l'excédent du nombre de têtes sur les queues vu dans les premiers iii flips. Définissez H=maxiHiH=maxiHiH=\text{max}_i H_i . Montrer que E[Hi]=Θ(i√)E[Hi]=Θ(i)E[H_i]=\Theta ( \sqrt{i}...
Quelles sont les principales différences entre ces trois termes isomorphisme, automorphisme et homomorphisme dans un langage simple profane et pourquoi nous faisons isomorphisme, automorphisme et
J'essaie de comprendre les grammaires contextuelles. Je comprends pourquoi des langues comme { w w ∣ w ∈ A∗}{ww∣w∈A∗}\{ww \mid w \in A^*\} { anbncn∣ n ∈ N }{anbncn∣n∈N}\{a^n b^n c^n \mid n\in\mathbb{N}\} ne sont pas sans contexte, mais ce que j'aimerais savoir si un langage similaire au calcul...
On dit que la théorie de la calculabilité est également appelée théorie de la récursivité. Pourquoi ça s'appelle comme ça? Pourquoi la récursivité a-t-elle autant
Tout d'abord, permettez-moi d'écrire la définition du grand juste pour rendre les choses explicites.OOO f(n)∈O(g(n))⟺∃c,n0>0f(n)∈O(g(n))⟺∃c,n0>0f(n)\in O(g(n))\iff \exists c, n_0\gt 0 tel que0≤f(n)≤cg(n),∀n≥n00≤f(n)≤cg(n),∀n≥n00\le f(n)\le cg(n), \forall n\ge n_0 Disons que nous avons un...
Je me demande cela en se basant sur plusieurs endroits en ligne qui appellent co- un problème ouvert majeur ... mais je ne trouve aucune indication quant à savoir si c'est la même chose que Problème ...N P P = N PNP=NP=\sf NP=NPNP\sf NPP=NPP=NP\sf
Si est régulier, cela signifie-t-il que est régulier?A2A2A^2AAA Ma tentative de preuve: Oui, car la contradiction suppose que n'est pas régulier. Ensuite .AAAA2=A⋅AA2=A⋅AA^2 = A \cdot A Comme la concaténation de deux langues non régulières n'est pas régulière, ne peut pas être régulier. Cela...
Donc, je sais que tester si un langage régulier RRR est un sous-ensemble du langage régulier SSS est décidable, car nous pouvons les convertir tous les deux en DFA, calculer R∩S¯R∩S¯R \cap \bar{S} , puis tester si ce langage est vide. Cependant, comme cela nécessite une conversion en DFA, il est...
Dites, L⊆{0}∗L⊆{0}∗L \subseteq \{0\}^* . Comment alors prouver que L∗L∗L^* est régulier? Si LLL est régulier, alors bien sûr L∗L∗L^* est également régulier. Si LLL est fini, alors il est régulier et encore L∗L∗L^* est régulier. J'ai également remarqué que, pour L={0p∣p is a prime}L={0p∣p is a...
Je pense comprendre comment la déforestation consomme et produit une liste en même temps (à partir d'une fonction de pliage et de dépliage - voir cette bonne réponse sur CodeReview ici ), mais quand je l'ai comparé avec l' entrée de wikipedia sur la technique dont il a parlé de `` supprimer arbres...
Quelqu'un pourrait-il m'expliquer les différences et similitudes entre l'apprentissage automatique et l'identification des systèmes? S'agit-il seulement de deux noms de la même chose? Dans cette page , ils disent: Les communautés d'apprentissage automatique et d'identification de systèmes sont...
Je comprends que les grammaires sans contexte peuvent être utilisées pour représenter des langues sans contexte, ce qui peut avoir des ambiguïtés. Nous avons également des formes normales comme la forme normale de Chomsky et Greibach . Je ne pouvais pas comprendre le besoin de cela. Pourquoi...
J'ai cette "preuve" très simple pour NP = CoNP et je pense que j'ai fait quelque chose de mal quelque part, mais je ne trouve pas ce qui ne va pas. Est-ce que quelqu'un peut m'aider? Soit A un problème dans NP, et soit M le décideur de A. Soit B le complément, c'est-à-dire que B est dans CoNP....