Informatyka

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

2
Gdzie jest błąd w tym najwyraźniej O (n lg n) algorytmie mnożenia?
Niedawny post na łamigłówce dotyczący znalezienia trzech równomiernie rozłożonych prowadzi mnie do pytania o przepełnienie stosu z najlepszą odpowiedzią, która twierdzi, że zrobię to w czasie O (n lg n). Interesujące jest to, że rozwiązanie polega na podniesieniu kwadratu do wielomianu, odnosząc się do artykułu opisującego, jak to zrobić w …
3
Obliczanie najdłuższego wspólnego podłańcucha dwóch łańcuchów przy użyciu tablic sufiksów
Po tym, jak nauczyłem się, jak budować tablicę sufiksów w złożoności , jestem zainteresowany odkrywaniem zastosowania tablic sufiksów. Jednym z nich jest znalezienie najdłuższego wspólnego podłańcucha między dwoma łańcuchami w czasie . W Internecie znalazłem następujący algorytm:O(N)O(N)O(N)O(N)O(N)O(N) połącz dwa ciągi AAA i BBB w jeden ciąg ABABAB obliczyć tablicę przyrostków …
2
Czy Hidoku NP jest kompletny?
Hidoku to siatka n×nn×nn \times n z niektórymi wstępnie wypełnionymi liczbami całkowitymi od 1 do n2n2n^2 . Celem jest znalezienie ścieżki kolejnych liczb całkowitych (od 1 do n2n2n^2 ) w siatce. Bardziej konkretnie, każda komórka siatki musi zawierać inną liczbę całkowitą od 1 do n2n2n^2 a każda komórka o wartości …
2
Jakie języki są rozpoznawane przez maszyny z jednym licznikiem?
Maszyny liczące z dwoma lub więcej licznikami są zwykle pokazywane jako równoważne maszynom Turinga w kursach teorii teorii obliczeń. Jednak nie widziałem formalnej analizy tego, które języki mogą być rozpoznawane przez maszynę z jednym kontem. Czy te języki są równoważne z językami bezkontekstowymi (być może przez jakąś sprytną konstrukcję odnoszącą …
3
Jeśli P = NP, dlaczego
Najwyraźniej, jeśli , wszystkie języki w z wyjątkiem i byłyby -kompletne.P = N PP=NP{\sf P}={\sf NP}P.P{\sf P}∅∅\emptysetΣ∗Σ∗\Sigma^*N P.NP{\sf NP} Dlaczego w szczególności te dwa języki? Czy nie możemy zredukować do nich żadnego innego języka w , wysyłając je podczas przyjmowania lub odrzucania?P.P{\sf P}
1
Znajdź proste cykle na wykresie ukierunkowanym
Dla mnie ten problem wygląda bardzo interesująco. Już miał znaleźć prosty cykl (tj. Cykl, w którym nie ma powtarzalnych węzłów) na ukierunkowanym wykresie. Moje rozwiązanie wygląda następująco, tzn. Ten wykres jest problemem przypadku: Wiem, że na wykresie jest cykl, w którym można znaleźć „tylne krawędzie” w wyszukiwaniu z głębokością pierwszą …
6
Czy może istnieć idealny algorytm szachowy?
Aktualne algorytmy szachowe idą około 1 lub może 2 poziomy w dół drzewa możliwych ścieżek w zależności od ruchów gracza i ruchów przeciwnika. Powiedzmy, że mamy moc obliczeniową do opracowania algorytmu, który przewiduje wszystkie możliwe ruchy przeciwnika w grze w szachy. Algorytm, który ma wszystkie możliwe ścieżki, które przeciwnik może …
3
Turinga pełna i obliczeniowa moc
W wykładzie profesor wspomniał, że współczesne komputery nie mają tak dużej mocy obliczeniowej jak maszyna Turinga, ponieważ nie mają nieskończonej pamięci, a ponieważ żaden komputer nie ma nieskończonej pamięci, maszyna Turinga jest zatem nieosiągalna i po prostu reprezentuje górną granicę informatyki. Czy z tego powodu istnieje miara lub definicja tego, …
1
O „Średniej wysokości posadzonych platanów” Knuth, de Bruijn i Rice (1972)
Staram się czerpać z klasycznej pracy tytułowej tylko elementarne środki (bez funkcji generujących, bez złożonej analizy, bez analizy Fouriera), choć ze znacznie mniejszą precyzją. Krótko mówiąc, „tylko” chcę udowodnić, że średnia wysokość drzewa z węzłami (to znaczy maksymalną liczbą węzłów od korzenia do liścia) spełnia .hnhnh_nnnnhn∼πn−−−√hn∼πnh_n \sim \sqrt{\pi n} Zarys …
2
Dlaczego w twierdzeniu głównym występuje warunek regularności?
Czytałem Wstęp do algorytmów Cormena i in. i czytam twierdzenie Twierdzenia Mistrza zaczynające się na stronie 73 . W przypadku 3 istnieje również warunek regularności, który należy spełnić, aby zastosować twierdzenie: ... 3. Jeśli fa( n ) = Ω ( nlogba + ε)fa(n)=Ω(nlogb⁡za+ε)\qquad \displaystyle f(n) = \Omega(n^{\log_b a + \varepsilon}) …
4
Biorąc pod uwagę zestaw zestawów, znajdź najmniejsze zestawy zawierające co najmniej jeden element z każdego zestawu
Biorąc pod uwagę zestaw zestawów, chciałbym znaleźć zestaw takie, że każdy zbiór w zawiera co najmniej jeden element . Chciałbym również, aby zawierał jak najmniej elementów, jednocześnie spełniając to kryterium, chociaż może istnieć więcej niż jeden najmniejszy z tą właściwością (rozwiązanie niekoniecznie jest unikalne).S.S.\mathbf{S}M.M.MS.S.SS.S.\mathbf{S}M.M.MM.M.MM.M.M Jako konkretny przykład, załóżmy, że zestaw …
4
Czy istnieje repozytorium dla hierarchii dowodów?
Jestem samoukiem, asystentem ds. Dowodów i postanowiłem zacząć od kilku podstawowych dowodów i podążać swoją drogą. Ponieważ dowody są oparte na innych dowodach, a zatem tworzą hierarchię, czy istnieje repozytorium hierarchii dowodów? Wiem, że mogę wybrać konkretnego asystenta proofów i przeanalizować jego bibliotekę, aby wyodrębnić jego hierarchię, jednak jeśli chcę …
2
Dlaczego kompletność Turinga jest słuszna?
Korzystam z komputera cyfrowego, aby napisać tę wiadomość. Taka maszyna ma właściwość, która, jeśli się nad tym zastanowić, jest naprawdę niezwykła: jest to jedna maszyna, która przy odpowiednim zaprogramowaniu może wykonać dowolne możliwe obliczenia . Oczywiście kalkulatory tego rodzaju wracają do starożytności. Ludzie zbudowali maszyny, które wykonują dodawanie i odejmowanie …
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.