Informatyka

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

2
Podzbiór Suma: zredukuj przypadek specjalny do ogólnego
Wikipedia stwierdza problem sumy podzbiorów jako znalezienie podzbioru danego zbioru wielu liczb całkowitych, którego suma wynosi zero. Dalej stwierdza, że ​​jest to równoważne ze znalezieniem podzbioru z sumą sss dla dowolnego danego sss . Sądzę więc, że ponieważ są one równoważne, musi nastąpić zmniejszenie po obu stronach. Jeden od sss …
1
Rozwiązywanie dziel i zdobywaj rekurencje, jeśli współczynnik podziału zależy od
Czy istnieje ogólna metoda rozwiązania problemu ponownego wystąpienia formularza: T(n)=T(n−nc)+T(nc)+f(n)T(n)=T(n−nc)+T(nc)+f(n)T(n) = T(n-n^c) + T(n^c) + f(n) dla c&lt;1c&lt;1c < 1 lub bardziej ogólnie T(n)=T(n−g(n))+T(r(n))+f(n)T(n)=T(n−g(n))+T(r(n))+f(n)T(n) = T(n-g(n)) + T(r(n)) + f(n) gdzie g(n),r(n)g(n),r(n)g(n),r(n) są niektórymi funkcjami subliniowymi nnn . Aktualizacja : Przejrzałem linki podane poniżej, a także przejrzałem wszystkie relacje powtarzalności …
1
Rygorystyczny dowód słuszności założenia
Twierdzenie Master jest pięknym narzędziem do rozwiązywania pewnych rodzajów nawrotów . Jednak często nakładamy połysk na integralną część podczas jej nakładania. Na przykład podczas analizy Mergesort z radością wychodzimy T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n) do T′(n)=2T′(n2)+f(n)T′(n)=2T′(n2)+f(n)\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n) biorąc …
3
Czy oznacza, że?
Czy to możliwe, że a liczność jest taka sama jak liczność ? Czy też oznacza, że i muszą mieć różne liczności?P N P P ≠ N P P N PP≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}P≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}
1
Problemy, dla których algorytmy oparte na zawężaniu partycji działają szybciej niż w czasie logarytmicznym
Udoskonalenie partycji to technika, w której zaczynasz od skończonego zestawu obiektów i stopniowo dzielisz zestaw. Niektóre problemy, takie jak minimalizacja DFA, można rozwiązać dość skutecznie za pomocą zawężania partycji. Nie znam żadnych innych problemów, które zwykle rozwiązuje się za pomocą udoskonalenia partycji innych niż te wymienione na stronie Wikipedii. Spośród …
3
Jak udowodnić, że DFA z NFA mogą mieć wykładniczą liczbę stanów?
Wszystkie niedeterministyczne skończone automaty można przekształcić w równoważne deterministyczne skończone automaty. Jednak deterministyczne automaty skończone zezwalają tylko na jedną strzałkę na symbol wskazującą na stan. Dlatego jego stany powinny należeć do zestawu sił stanów NFA. To wydaje się wskazywać, że liczba stanów DFA mogłaby się wykładniczo skalować pod względem liczby …
3
Jak trudno jest znaleźć dyskretny logarytm?
bbbab=cmodNab=cmodNa^b=c \bmod NaaacccNNN Zastanawiam się, w jakich grupach złożoności (np. Dla komputerów klasycznych i kwantowych) to jest i jakie podejścia (tj. Algorytmy) są najlepsze do wykonania tego zadania. Powyższy link do Wikipedii tak naprawdę nie zapewnia bardzo konkretnych środowisk uruchomieniowych. Mam nadzieję na coś bardziej podobnego do najbardziej znanych metod …
3
Problemy w P z znacznie szybszymi algorytmami randomizowanymi
Czy są jakieś problemy w które mają algorytmy losowe przekraczające dolne granice algorytmów deterministycznych? Mówiąc konkretniej, czy znamy jakieś dla którego ? Tutaj \ mathsf {PTIME} (f (n)) oznacza zestaw języków rozstrzygalnych przez losową TM z błędem o stałym ograniczeniu (jedno- lub dwustronny) w krokach f (n) .PP\mathsf{P}kkkDTIME(nk)⊊PTIME(nk)DTIME(nk)⊊PTIME(nk)\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)PTIME(f(n))PTIME(f(n))\mathsf{PTIME}(f(n))f(n)f(n)f(n) …
2
Jak opisywać algorytmy, je udowadniać i analizować?
Przed przeczytaniem „Sztuki programowania komputerowego” (TAOCP) nie zastanawiałem się głęboko nad tymi pytaniami. Używałbym pseudokodu do opisywania algorytmów, rozumienia ich i szacowania czasu działania tylko o rzędach wzrostu. TAOCP gruntownie zmienia zdanie. TAOCP używa angielskiego mieszanego z krokami i goto do opisywania algorytmu, i wykorzystuje schematy blokowe do łatwiejszego zobrazowania …
4
Jak użyć chciwego algorytmu, aby znaleźć malejącą sekwencję najbliższą podanej?
Otrzymujesz n liczb całkowitych wszystkie od do . Pod każdą liczbą całkowitą należy wpisać liczbę całkowitą między a z warunkiem, że tworzą ciąg nie malejący. Zdefiniuj odchylenie takiej sekwencji na . Zaprojektuj algorytm, który znajdzie b_i z minimalnym odchyleniem w czasie wykonywania O (n \ sqrt [4] {l}) .a1,…,ana1,…,ana_1, \ldots, …
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.