Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Heapsort: Heaps = ~ Quicksort: BSTs = ~ Mergesort: ___?
Proszę wybaczyć zwięzłość tytułu, mogłem poświęcić jasność na ołtarzu zwięzłości. Widać, że wstawienie elementów tablicy do binarnego drzewa wyszukiwania i ich ponowne odczytanie wymaga (przy wstawianiu) takich samych porównań, jak uruchomienie Quicksort na tej tablicy. Sekwencja osi przestawnych używanych przez Quicksort to sekwencja wstawek do drzewa wyszukiwania binarnego. Jest to …
2
Ograniczona formuła Monotone 3CNF: liczenie spełniających się zadań (oba modulo
Rozważ formułę Monotone 3CNF mającą oba następujące dodatkowe ograniczenia: Każda zmienna występuje dokładnie w klauzulach.2)22 Biorąc pod uwagę dowolne klauzule, mają one maksymalnie zmienną.2)22111 Chciałbym wiedzieć, jak ciężko jest liczyć satysfakcjonujące zadania takiej formuły. Aktualizacja 06.04.2013 12:55 Chciałbym również wiedzieć, jak trudne jest ustalenie parytetu liczby satysfakcjonujących zadań. Aktualizacja 11.04.2013 …
2
Czy adiabatyczne obliczenia kwantowe są tak potężne jak model obwodowy?
Znaczna część literatury obliczeń kwantowych koncentruje się na modelu obwodu. Adiabatyczne obliczenia kwantowe nie polegają na zastosowaniu sekwencji operatorów jednostkowych, ale na zmianie zależnego od czasu hamiltonianu. Szukam wglądu w którekolwiek z poniższych. Czy adiabatyczne obliczenia kwantowe są tak potężne jak model obwodowy, czy też są z natury mniej wydajne? …
2
Dolna granica liczby wezwań wyroczni do rozwiązania przypadków problemu zatrzymania
Spotkałem następujące pytanie, które jest łatwym ćwiczeniem (spoiler poniżej). Dostajemy wystąpień problemu z zatrzymaniem (np. TM ) i musimy dokładnie zdecydować, które z nich zatrzymają się na . Oznacza to, że musimy . Dostajemy wyrocznię za problem zatrzymania, ale musimy go użyć minimalną liczbę razy.nnnM1,...,MnM1,...,MnM_1,...,M_nϵϵ\epsilon{i:Mi halts on ϵ}{i:Mi halts on …
3
Znajdź pozostałą część dużego stałego wielomianu po podzieleniu przez niewielki nieznany wielomian
Załóżmy, że działamy w polu skończonym. Otrzymujemy duży stały wielomian p (x) (powiedzmy stopnia 1000) nad tym polem. Ten wielomian jest znany wcześniej i możemy wykonywać obliczenia przy użyciu dużej ilości zasobów w „fazie początkowej”. Wyniki te mogą być przechowywane w stosunkowo małych tabelach przeglądowych. Pod koniec „fazy początkowej” otrzymamy …
1
Na
Wiemy to L⊆NL⊆P⊆NPL⊆NL⊆P⊆NP\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}. Z twierdzenia SavitchaNL⊆L2NL⊆L2\mathcal{N\!L}\subseteq\mathcal{L}^2, a od Space Hierarchy Teorem, L≠L2L≠L2\mathcal{L}\neq\mathcal{L}^2. Ponieważ nie wiemy, czyL≠PL≠P\mathcal L\neq\mathcal Pnie wiemy czy L2⊆PL2⊆P\mathcal L^2\subseteq\mathcal Pczy wiemy o tym L2⊈PL2⊈P\mathcal L^2\not\subseteq\mathcal P? Czy ktoś próbował udowodnić, że ? Jakie są najnowsze wyniki lub wysiłki w ten sposób? Próbowałem napisać ankietę na ten …
1
Zwiększenie wydajności w celu maksymalizacji minimalnego cięcia
Rozważ wykres ze wszystkimi krawędziami o pojemności jednostkowej. Można znaleźć min. Cięcie w czasie wielomianowym. Załóżmy, że mogę zwiększyć pojemność dowolnego kkkkrawędzie do nieskończoności (równoważne scalaniu węzłów po obu stronach krawędzi). Jaki jest optymalny sposób wyboru optymalnego zestawukkk krawędzie (których pojemność zostanie zwiększona do nieskończoności), aby zmaksymalizować minimalne cięcie?
1
Zrozumienie przemówień na konferencjach i warsztatach
Jestem studentką z Indii. Jestem bardzo zainteresowany uczestnictwem w warsztatach, konferencjach i zaproszonych wykładowcach prowadzonych przez wybitnych profesorów. Pod koniec rozmowy jak zwykle niektóre osoby będą zadawać pytania, a mówca na nie odpowie. Ale moim problemem jest to, że nie rozumiem większości pytań i odpowiedzi. Nawet jeśli zadam jakieś pytanie, …
2
Jaka jest korzyść z zapisu Krivine?
Widziałem, jak niektórzy ludzie używają notacji Krivine'a do aplikacji funkcji podczas prezentacji składni dla -calculus. Na przykład -term (z normalną konwencją, że aplikacja funkcji kojarzy się z lewą stroną, więc w rzeczywistości oznacza to ) jest napisane (z podobną konwencją, że w rzeczywistości oznacza ). Nie widzę sensu posiadania kolejnej …
2
Generowanie interesujących problemów optymalizacji kombinatorycznej
Prowadzę kurs meta-heurystyki i muszę wygenerować ciekawe przykłady klasycznych problemów kombinatorycznych dla projektu semestralnego. Skupmy się na TSP. Zajmujemy się wykresami wymiarów200200200i większe. Próbowałem oczywiście wygenerować wykres z macierzą kosztów z wartościami pobranymi z losowegoU( 0 , 1 )U(0,1)U(0,1)i odkrył, że (zgodnie z oczekiwaniami) histogram kosztu ścieżki (sporządzony przez próbkowanie …
2
Formalne przedstawienie hierarchii abstrakcji
Wprowadzenie Piszę pracę doktorską na temat abstrakcyjnego modelowania delty (ADM), abstrakcyjnego algebraicznego opisu modyfikacji (znanych jako delty ) zdolnych do działania na produkty (jak w „produktach programowych”). Można to wykorzystać do zorganizowania zestawu powiązanych produktów („linii produktów”) jako prostego produktu podstawowego i zestawu warunkowo zastosowanych delt, a tym samym umożliwienia …
1
Mogą
Pozwolić ATISP(f(n),g(n))ATISP(f(n),g(n))\mathsf{ATISP}(f(n), g(n)) być klasą języków ustaloną przez naprzemienne maszyny Turinga, które zatrzymują się w czasie f(n)f(n)f(n) używając przestrzeni g(n)g(n)g(n). PozwolićAALTSP(f(n),g(n))AALTSP(f(n),g(n))\mathsf{AALTSP}(f(n), g(n)) być klasą języków ustaloną przez naprzemienne używanie maszyn Turinga f(n)f(n)f(n) alternacje i przestrzeń g(n)g(n)g(n). Ruzzo udowodnił , żeNCk=ATISP(logkn,logn)NCk=ATISP(logk⁡n,log⁡n)\mathsf{NC}^k = \mathsf{ATISP}(\log^k n, \log n). On też to pokazałNCk⊆AALTSP(logkn,logn)⊆NCk+1NCk⊆AALTSP(logk⁡n,log⁡n)⊆NCk+1\mathsf{NC}^k \subseteq …
1
Czy istnieje kandydat na postkwantowe jednokierunkowe działanie grupowe?
Czy istnieje znana rodzina działań grupowych z wyznaczonym elementem w zestawie, na którym działa się, gdzie wiadomo, jak skutecznie \: próbkuj (zasadniczo jednolicie) z grup, oblicz operacje odwrotne, \: oblicz operacje grupowe i oblicz działania grupowe i nie ma znanego wydajnego algorytmu kwantowego do osiągnięcia sukcesu z nieistotnym prawdopodobieństwem w …
2
Jak możemy wyrazić „
Zamknięte. To pytanie jest nie na temat . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby było tematem wymiany stosów teoretycznych w informatyce. Zamknięte 7 lat temu . Jak możemy wyrazić „ ” jako formułę pierwszego rzędu?P.= PS.P.A C.miP=PSPACEP=PSPACE Który poziom hierarchii arytmetycznej zawiera tę formułę (i …
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.