Chodzi o to, jak skutecznie możemy wyrazić algorytm. Potrzebuję tego do moich studiów licencjackich. Rozumiem, że nie ma czegoś takiego jak standardowy sposób pisania pseudo kodu. Różni autorzy stosują różne konwencje. Byłoby pomocne, gdyby ludzie tutaj wskazywali, w jaki sposób podążają i myślą...
Stan naszej wiedzy o ogólnych obwodach arytmetycznych wydaje się być podobny do stanu naszej wiedzy o obwodach boolowskich, tzn. Nie mamy dobrych dolnych granic. Z drugiej strony mamy wykładnicze granice wielkości dla monotonicznych obwodów boolowskich . Co wiemy o monotonii obwodach...
Ponieważ nie pozwala na niekończące się obliczenia, Coq niekoniecznie nie jest kompletny w Turingu. Jaką klasę funkcji może obliczyć Coq? (czy istnieje ich interesująca
Słynny Yao Minimax Zasada stwierdza zależność między złożonością i dystrybucyjnej randomizowanym złożoności. Niech PPP być problemu ze skończonego zbioru wejść i skończonego zbioru deterministycznego algorytmu rozwiązania . Niech także oznacza rozkład wejściowy, a niech oznacza rozkład...
Czytałem „ Czy P w porównaniu z NP jest formalnie niezależny? ”, Ale mnie to zaskoczyło. Uważa się, że w teorii złożoności . Moje pytanie dotyczy tego, co jeśli nie da się tego udowodnić (powiedzmy w Z F C ). (Załóżmy, że dowiadujemy się tylko, że P ≠ N P jest niezależny od Z F C, ale nie ma...
Podczas majstrowania przy niekanonicznym analizowaniu LR wymyśliłem metodę analizy (z tabelami o nieskończonych rozmiarach, co czyni ją nieco niepraktyczną ), która jest w stanie przeanalizować dokładnie jednoznaczne gramatyki w czasie , i zastanawiałem się, czy można to zrobić lepiej...
W grze typu tower defense masz siatkę NxM z początkiem, wykończeniem i wieloma ścianami. Wrogowie podążają najkrótszą ścieżką od początku do końca, nie przechodząc przez ściany (zwykle nie są ograniczeni do siatki, ale dla uproszczenia powiedzmy, że są. W obu przypadkach nie mogą poruszać się po...
Interesuje mnie złożoność decydowania, czy dany nie-prosty wielokąt jest prawie prosty, w jednym z dwóch różnych formalnych zmysłów: słabo prostym lub nie-samokreślącym . Ponieważ te terminy nie są powszechnie znane, zacznę od niektórych definicji. Wieloboku jest zamknięty cykl odcinków łączenia...
Istnieje wiele niedopuszczalności wyników, które opierają się na unikalnym założeniu gier. Na przykład, Zakładając unikalną hipotezę gier, NP jest trudne do przybliżenia maksymalnego problemu cięcia w ramach współczynnika R dla dowolnej stałej R > R GW . (Tutaj R GW = 0,878… jest...
Czy ktoś zna odniesienia, które precyzyjnie określają związek między algorytmem unifikacji a eliminacją Gaussa? Szczególnie interesuje mnie związek między podstawieniami trójkątnymi a rozkładami LU. Wayne Snyder i Jean Gallier wspominają o tej analogii, przekazując w swojej pracy, Revisited...
Podczas testowania właściwości wykresu algorytm wysyła zapytanie do wykresu docelowego o obecność lub brak krawędzi i musi ustalić, czy cel ma określoną właściwość, czy też jest -far od posiadania tej właściwości. (Algorytm może zostać poproszony o powodzenie z błędem 1-stronnym lub 2-stronnym.)...
Czas dojazdu na połączonym wykresie definiuje się jako oczekiwaną liczbę kroków w losowym marszu rozpoczynającym się od , przed odwiedzeniem węzła a następnie ponownie osiągnięciem węzła . Jest to w zasadzie suma dwóch czasów uderzenia i .i j i H ( i , j ) H ( j , i...
Czy istnieje przydatny opis przyszłości lub obietnic w kategoriach teorii kategorii? W szczególności, czym może być kategoryczny dualność
Wykresy sześcienne to wykresy, w których każdy wierzchołek ma stopień 3. Zostały one szeroko zbadane i jestem świadomy, że kilka problemów trudnych dla NP pozostaje trudnych dla NP nawet ograniczonych do podklas grafów sześciennych, ale niektóre inne stają się łatwiejsze. Nadklasą wykresów...
Szukam nieukierunkowanych, nieważonych połączonych wykresów , w których dla każdej pary u , v ∈ V istnieje unikalna ścieżka u → v, która realizuje odległość d ( u , v ) .G = ( V, E)sol=(V.,mi)G=(V,E)u , v ∈ V.u,v∈V.u,v \in Vu → vu→vu \rightarrow vre( u , v )re(u,v)d(u,v) Czy ta klasa grafów jest...
Rozważmy sieć elektryczną zamodelowaną jako płaski wykres G, gdzie każda krawędź reprezentuje rezystor 1 Ω. Jak szybko możemy obliczyć dokładną efektywną rezystancję między dwoma wierzchołkami w G? Równolegle, jak szybko możemy obliczyć dokładny prąd płynący wzdłuż każdej krawędzi, jeśli podłączymy...
W świetle niedawnej otchłani na głębokości 3 wynik (który między innymi daje głębokości 3 arytmetyczna obieg donxndeterminant naC) I mają następujące pytania: Grigoriev i Karpińskiokazałosię2omów(n)dolna granica dla każdego arytmetyczna obwodu głębokości-3 obliczeniowej wyznacznikanxnmacierze nad...
Szukam zwięzłego tekstu wprowadzającego na temat algorytmów z omówioną teorią wysokiego współczynnikatheory coveredtotal number of pages.theory coveredtotal number of pages.\frac{\mbox{theory covered}}{\mbox{total number of pages}}.Powinno zacząć się od początku, ale potem szybko postępować, nie...
Projektuję prosty funkcjonalny język programowania o typie statycznym jako sposób uczenia się. Wygląda na to, że system typów, który do tej pory wdrożyłem, może (przy odrobinie dodatkowej pracy) zawierać typy skrzyżowań i złączy, np. Możesz mieć: <Union String Integer> <Union Integer...
Pracowałem nad wprowadzeniem niektórych wyników złożoności obliczeniowej do biologii teoretycznej, zwłaszcza ewolucji i ekologii , aby być interesującym / użytecznym dla biologów. Jedną z największych trudności, jakie napotkałem, jest uzasadnienie przydatności asymptotycznej analizy najgorszego...