Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

7
Zastosowania teorii gier w informatyce?
Jako student informatyki zapoznałem się z teorią gier, ale nie widziałem zbyt wielu szczegółów na ten temat. Szukałem w Google i przeglądałem książki o teorii gier, które potwierdziły jej wykorzystanie w informatyce. Rozpocząłem formalne studium teorii gier z perspektywy ekonomisty. Teraz chcę poznać zastosowania teorii gier w informatyce. Jakie są …
7
Analiza matematyczna i złożoność obliczeniowa?
złożoność obliczeniowa obejmuje duże ilości kombinatoryki i teorii liczb, niektóre elementy stochastyczne i pojawiającą się ilość algebry. Jednak będąc analitykiem zastanawiam się, czy istnieją zastosowania analizy w tej dziedzinie, czy może pomysły inspirowane analizą. Wiem tylko, co nieco to odpowiada, to transformata Fouriera na grupach skończonych. Możesz mi pomóc?
2
Listy różnic w programowaniu funkcjonalnym
Pytanie Co nowego w czysto funkcjonalnych strukturach danych od czasu Okasaki? oraz epicka odpowiedź jbapple, wspomniana przy użyciu list różnic w programowaniu funkcjonalnym (w przeciwieństwie do programowania logicznego), co mnie ostatnio interesowało. To doprowadziło mnie do znalezienia implementacji listy różnic dla Haskell. Mam dwa pytania (wybacz mi / popraw, jeśli …
2
Para cykli rozłącznych wierzchołków na ukierunkowanym wykresie
Jaki jest najszybszy znany algorytm deterministyczny, który może rozpoznawać skierowane wykresy za pomocą pary rozłącznych cykli wierzchołków? Wiem, że wykresy z min. Min. Trzech zawsze mają taką parę ( Thomassen'83 ), ale mimo to nie mogę znaleźć skutecznego algorytmu w ogólnym przypadku. Czy ktoś zna odniesienia do tego?
1
„Stopień trudności Rabina w obliczeniu funkcji i częściowe uporządkowanie zbiorów rekurencyjnych”
Szukam: Michael O. Rabin, „Stopień trudności obliczenia funkcji i częściowe uporządkowanie zbiorów rekurencyjnych”, Uniwersytet Hebrajski, Jerozolima, 1960 Streszczenie: „Próbujemy zmierzyć ilość pracy związanej z obliczeniem danej funkcji obliczeniowej (rekurencyjnej). Wprowadzono i zbadano pojęcie stopnia trudności obliczeń. Pojęcie to jest niezmienne w tym sensie, że jest niezależne od wyidealizowanych komputerów (maszyn …
1
Trudne problemy z rozszerzalnością
W przypadku problemu z rozszerzeniem otrzymujemy część rozwiązania i chcemy zdecydować, czy możemy go rozszerzyć do kompletnego rozwiązania. Niektóre problemy związane z rozszerzalnością można skutecznie rozwiązać, podczas gdy inne problemy z możliwością rozbudowy przekształcają problem łatwy w trudny. Na przykład twierdzenie Koniga-Halla stwierdza, że ​​wszystkie sześcienne dwustronne wykresy można pokolorować …
1
Kolejny wariant PARTYCJI
Mam redukcję następującego problemu z partycją do pewnego problemu z planowaniem: Dane wejściowe: lista liczb całkowitych dodatnich w kolejności nie malejącej.a1⩽⋯⩽ana1⩽⋯⩽ana_1\leqslant\cdots\leqslant a_n Pytanie: Czy istnieje wektor taki, że(x1,…,xn)∈{−1,1}n(x1,…,xn)∈{−1,1}n(x_1,\ldots,x_n)\in\{-1,1\}^n ∑i=1naixi=0and∑i=1naixi=0and\sum_{i=1}^na_ix_i=0\qquad\text{and} ∑i=1kaixi⩾0for all k∈{1,…,n}∑i=1kaixi⩾0for all k∈{1,…,n}\sum_{i=1}^ka_ix_i\geqslant 0\quad\text{for all }k\in\{1,\ldots,n\} Bez drugiego warunku jest to po prostu PARTYCJA, a więc NP-twardy. Ale drugi …
1
Rozróżnianie dwóch monet
Powszechnie wiadomo, że złożoność odróżnianie się stronniczy monetę z jednego sprawiedliwego jest θ ( ε - 2 ) . Czy istnieją wyniki dla odróżnienia monety p od monety p + ϵ ? Widzę, że dla specjalnego przypadku p = 0 złożoność będzie wynosić ϵ - 1 . Mam przeczucie, że …
1
Testowanie izomorfizmu grafów asymetrycznych
Czytając pytanie Przykłady gdzie wyjątkowość rozwiązania sprawia, że łatwiej znaleźć , nowy (? Łatwiej) pytanie przyszło mi do głowy: Właściwie nie wiemy, czy izomorfizm grafów ( ) problem jest w P .GIGIGIPPP Ale co się stanie, jeśli założymy, że zarówno i G 2 są asymetryczne (tj. Oba mają jedynie trywialny …
1
Odległość między zwykłymi językami
Chcę zdefiniować pojęcie „bliskości” między dwoma regularnymi językami skończonych słów w (i / lub nieskończonych słów w Σ ω ). Podstawową ideą jest to, że chcemy, aby dwa języki były blisko siebie, jeśli nie różnią się wieloma słowami. Możemy również w jakiś sposób wykorzystać odległość edycji ... Nie mogłem znaleźć …
2
Edytuj odległość za pomocą operacji przesuwania
Motywacja: Współautor redaguje manuskrypt i chciałbym zobaczyć jasne podsumowanie edycji. Wszystkie narzędzia podobne do „diff” są zwykle bezużyteczne, jeśli zarówno przenosisz tekst (np. Reorganizując strukturę), jak i edytujesz lokalnie. Czy to naprawdę takie trudne? Definicje: Chciałbym znaleźć minimalną odległość edycji, gdzie dozwolone operacje to: „tanie” operacje: dodaj / zmień / …
2
Czy istnienie całkowitego problemu wyszukiwania
Łatwo zauważyć, że jeśli to istnieją całkowite N P problemy wyszukiwania, których nie można rozwiązać w czasie wielomianowym (stwórz całkowity problem wyszukiwania, mając zarówno świadków członkostwa, jak i świadków braku członkostwa).N P ∩ c o N P ≠ PNP∩coNP≠P\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}N P.NP\mathsf{NP} Czy odwrotna jest również prawda, tj Czy istnienie …
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.