Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

5
Wada mojego NP = dowód CoNP?
Mam ten bardzo prosty „dowód” na NP = CoNP i myślę, że gdzieś coś zrobiłem źle, ale nie mogę znaleźć, co jest nie tak. Czy ktoś może mi pomóc? Niech A będzie pewnym problemem w NP, i niech M będzie decydującym dla A. Niech B będzie dopełnieniem, tj. B jest …
2
Nieskończony łańcuch dużych
Po pierwsze, pozwól mi napisać definicję dużego OOO tylko po to, żeby coś wyjaśnić. 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 takie, że0≤f(n)≤cg(n),∀n≥n00≤f(n)≤cg(n),∀n≥n00\le f(n)\le cg(n), \forall n\ge n_0 Powiedzmy, że mamy skończoną liczbę funkcji: f1,f2,…fnf1,f2,…fnf_1,f_2,\dots f_n spełniające: O(f1)⊆O(f2)⋯⊆O(fn)O(f1)⊆O(f2)⋯⊆O(fn)O(f_1)\subseteq O(f_2)\dots \subseteq O(f_n) Przez przechodniość OOO mamy to: O(f1)⊆O(fn)O(f1)⊆O(fn)O(f_1)\subseteq O(f_n) Czy to chwyt …
1
Gödelizacja w maszynie Turinga
Patrzyłem na kurs Gödelization w teorii teorii obliczeń. Mogłem zrozumieć koncepcje numeracji Gödla, ale nie mogłem zrozumieć ich znaczenia w teorii obliczeń. Czy ktoś mógłby wskazać jakieś dobre materiały lub wskazać jego znaczenie.
3
Znajdowanie elementu, który występuje najczęściej w bardzo dużym pliku
Słyszałem to pytanie podczas wywiadu i miałem nadzieję uzyskać opinie na temat dobrych odpowiedzi: masz duży plik 10+ GB i chcesz dowiedzieć się, który element występuje najczęściej, co jest dobrym sposobem zrobić to? Iterowanie i śledzenie mapy prawdopodobnie nie jest dobrym pomysłem, ponieważ zużywasz dużo pamięci, a śledzenie pojawiających się …
2
Czy wszystkie języki kontekstowe są rozstrzygalne?
Przeglądałem definicję języka kontekstowego w Wikipedii i znalazłem to: Każda kategoria języków jest odpowiednim podzbiorem kategorii bezpośrednio nad nią. Każdy automat i gramatyka w każdej kategorii ma równoważny automat lub gramatykę w kategorii bezpośrednio nad nią. Widziałem, że automat ograniczany liniowo jest bezpośrednio poniżej decydującego w porządku tego artykułu. Jeśli …
7
Czy
Jeśli jest regularne, to czy wynika z tego, że jest regularne? AA2A2A^2AAA Moja próba na dowód: Tak, ponieważ sprzeczność zakłada, że nie jest regularne. Następnie .A 2 = A ⋅ AAAAA2=A⋅AA2=A⋅AA^2 = A \cdot A Ponieważ łączenie dwóch nieregularnych języków nie jest regularne, nie może być regularne. Jest to sprzeczne …
2
Układanie ortogonalnego wielokąta za pomocą kwadratów
Biorąc pod uwagę ortogonalny wielokąt (wielokąt, którego boki są równoległe do osi), chcę znaleźć najmniejszy zestaw kwadratów wewnętrznie rozłącznych, których zjednoczenie jest równe wielobokowi. Znalazłem kilka odniesień do nieco innych problemów, takich jak: Pokrycie prostopadłego wielokąta kwadratami - podobnie jak w moim problemie, ale zakrywające kwadraty mogą się pokrywać. Ten …
3
Rozbieżność między głowami a ogonami
Rozważ sekwencję rzutów bezstronnej monety. Niech oznacza wartość bezwzględną nadwyżki liczby głów nad ogonami widzianej w pierwszych rzutach . Zdefiniuj . Pokaż, że E [H_i] = \ Theta (\ sqrt {i}) i E [H] = \ Theta (\ sqrt {n}) .nnnHiHiH_iiiiH=maxiHiH=maxiHiH=\text{max}_i H_iE[Hi]=Θ(i√)E[Hi]=Θ(i)E[H_i]=\Theta ( \sqrt{i} )E[H]=Θ(n−−√)E[H]=Θ(n)E[H]=\Theta( \sqrt{n} ) Ten problem pojawia …
4
Czy ktoś może podać prosty, ale nie zabawkowy przykład gramatyki kontekstowej?
Próbuję zrozumieć gramatyki kontekstowe. Rozumiem, dlaczego języki lubią { w w ∣ w ∈ A∗}{ww∣w∈ZA∗}\{ww \mid w \in A^*\} { anbndon∣ n ∈ N }{zanbndon∣n∈N.}\{a^n b^n c^n \mid n\in\mathbb{N}\} nie są wolne od kontekstu, ale co chciałbym wiedzieć, jeśli język podobny do niepisanego rachunku lambda jest wrażliwy na kontekst. Chciałbym …
3
Dlaczego większe rozmiary wejściowe oznaczają trudniejsze instancje?
Poniżej załóżmy, że pracujemy z maszyną Turinga z nieskończoną taśmą. Wyjaśniając komuś pojęcie złożoności czasowej i dlaczego mierzy się ją względem wielkości wejściowej instancji, natknąłem się na następujące twierdzenie: [..] Na przykład naturalne jest, że potrzeba więcej kroków, aby pomnożyć dwie liczby całkowite przez 100 000 bitów, niż, powiedzmy, pomnożenie …
4
Porównywanie liczb wymiernych
Biorąc pod uwagę a , b , c , d∈ N.za,b,do,re∈N.a,b,c,d \in \mathbb N i ,b , d∉ { 0 }b,re∉{0}b,d \notin \{0\} zab&lt; cre⟺d&lt; c bzab&lt;dore⟺zare&lt;dob \begin{eqnarray*} \frac a b < \frac c d &\iff& ad < cb \end{eqnarray*} Moje pytania to: Biorąc pod uwagęa , b , c …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.