Teoretyczne informatyka

3

Kontekst To pytanie jest motywowane grą planszową o nazwie „Dracula”. W tej grze jest jeden wampir i czterech łowców, których celem jest złapanie wampira. Gra toczy się w Europie. Gra wygląda następująco: 1. Łowca umieszcza wszystkich łowców w miastach. W tym samym mieście można umieścić więcej niż jednego myśliwego. 2. …

13 graph-theory co.combinatorics board-games combinatorial-game-theory

1

Największy wspólny podgraf dwóch maksymalnych wykresów płaskich

Rozważ następujący problem - Biorąc pod uwagę maksymalne płaskie wykresy i G 2 , znajdź wykres G z maksymalną liczbą krawędzi, tak że w G 1 i G 2 jest podgraph (niekoniecznie indukowany), który jest izomorficzny do Gsol1G1G_1sol2)G2G_2solGGsol1G1G_1sol2)G2G_2solGG . Czy można to zrobić w czasie wielomianowym? Jeśli tak, to jak? …

13 ds.algorithms graph-algorithms planar-graphs

2

Przegląd transformacji związanych z wykorzystaniem solverów SAT

Zaczynam badać możliwość polegania na rozwiązaniu SAT w celu rozwiązania problemu optymalizacji, który mnie interesuje, i obecnie szukam ankiety, która zawierałaby przykłady „sprytnych” przekształceń w warianty SAT (tj. Przekształcenia, które wynikają w problemie o rozsądnej wielkości, ponieważ nie jestem zainteresowany udowodnieniem wyników twardości, ale faktycznym rozwiązaniem problemu), w przybliżeniu w …

13 ds.algorithms reference-request sat optimization

6

„Naturalne” rozstrzygalne problemy, o których wiadomo, że nie występują w NP.

Za każdym razem, gdy uczę kompletności NP, uczniowie pytają „czy są jakieś problemy, o których wiadomo, że nie należą do NP?” Jak byś odpowiedział? Zazwyczaj daję im nierozstrzygalny problem jako przykład, ale często nie wychodzi to dobrze: (a) jeśli daję im problem z zatrzymaniem, myślą, że to jakiś głupi przypadek, …

13 cc.complexity-theory complexity-classes teaching

1

Asymptotyki do wymiany monet

Podano nominałów monet, przy czym i są liczbami losowymi równomiernie rozmieszczonymi w przedziale . Asymptotycznie, dla jakiej części monet chciwy algorytm generuje optymalną zmianę przy użyciu tego zestawu nominałów?c 1 = 1 c 2 < c 3 < . . < c n [ 2 , N ]nnnc1=1c1=1c_1=1c2<c3<..<cnc2<c3<..<cnc_2<c_3<..<c_{n}[2,N][2,N][2,N] Odpowiedź jest …

13 ds.algorithms

6

Każdy problem algorytmiczny ma złożoność czasową zdominowaną przez liczenie?

To, co nazywam liczeniem, to problem polegający na znalezieniu liczby rozwiązań funkcji. Dokładniej, biorąc pod uwagę funkcję fa: N→ { 0 , 1 }f:N→{0,1}f:N\to \{0,1\} (niekoniecznie czarna skrzynka), przybliżone # { x ∈ N∣ f( x ) = 1 } = | fa- 1( 1 ) |#{x∈N∣f(x)=1}=|f−1(1)|\#\{x\in N\mid f(x)= 1\}= …

13 ds.algorithms reference-request counting-complexity time-complexity

2

Czy problem z ukończeniem koNP ma podwykonawczy certyfikat rozmiaru?

Zakładając, że NP! = CoNP, to nie ma certyfikatu wielomianu dla problemu pełnego coNP. Ale co z podwykładniczym certyfikatem wielkości? Czy w szczególności w przypadku coSAT istnieje podwykładniczy dowód wielkości, aby udowodnić, że formuła jest niezadowalająca? Jeśli nie, jakie są negatywne dowody? Dzięki

13 cc.complexity-theory proof-complexity

2

Zależność między stałym parametrem a algorytmem aproksymacyjnym

Stały parametr i przybliżenie to zupełnie inne podejścia do rozwiązywania trudnych problemów. Mają inną motywację. Przybliżenie szuka szybszego wyniku dzięki przybliżonemu rozwiązaniu. Naprawiono parametr szuka dokładnego rozwiązania ze złożonością czasową pod względem wykładniczej lub jakiejś funkcji k i funkcji wielomianowej n, gdzie n jest wielkością wejściową, a k jest parametrem. …

13 cc.complexity-theory reference-request approximation-algorithms fixed-parameter-tractable

1

Jaki jest kompromis między wielkością populacji a liczbą pokoleń w algorytmach genetycznych

Algorytmy genetyczne ewoluują w mniejszej liczbie pokoleń z większą populacją, ale także obliczanie pokolenia trwa dłużej. Czy istnieją jakieś wytyczne dotyczące równoważenia tych dwóch czynników, aby jak najszybciej znaleźć realne rozwiązanie? Czy to najlepsze miejsce na pytanie?

13 ds.algorithms machine-learning genetic-algorithms

4

Relaksacja LP niezależnego zestawu

Próbowałem następującej relaksacji LP maksymalnie niezależnego zestawu max∑iximax∑ixi\max \sum_i x_i s.t. xi+xj≤1 ∀(i,j)∈Es.t. xi+xj≤1 ∀(i,j)∈E\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E xi≥0xi≥0x_i\ge 0 Dostaję 1/21/21/2 za każdą zmienną za każdy sześcienny dwudzielny wykres, który próbowałem. Czy to prawda dla wszystkich połączonych sześciennych dwudzielnych grafów? Czy istnieje relaksacja LP, która działa lepiej …

13 graph-theory co.combinatorics linear-programming

1

Jaka jest złożoność obliczania optymalnych kodów wolnych od prefiksów, gdy częstotliwości są podobne?

Dobrze wiadomo, że istnieje najgorszy przypadek optymalnego algorytmu do obliczania kodu Huffmana w czasie . Poprawiono to na dwa ortogonalne sposoby:θ(nlgn)θ(nlg⁡n)\theta(n\lg n) Optymalne kody wolne od prefiksów można obliczyć szybciej, jeśli zestaw różnych częstotliwości jest mały (np. Rozmiar ): posortuj częstotliwości za pomocą [Munro i Spira, 1976], aby skorzystać z …

13 cc.complexity-theory

3

Jak napisać negatywną recenzję do artykułu konferencyjnego?

Jest to związane z ogólnym pytaniem „ Jak sędziować artykuł? ”. Recenzuję artykuł na konferencję i ten artykuł powinien zostać odrzucony, ponieważ nie jest wystarczająco znaczący dla publikacji i ma wady w niektórych jego szczegółach technicznych. Papier nie jest zły, ale sposoby, w jakie jest poprawne, nie są zbyt interesujące. …

13 soft-question paper-review

6

Jakie są praktycznie obliczalne właściwości znakowanych układów przejściowych?

Znalazłem systemy przejściowe oznaczone jako dobry model dla mojej aplikacji, a mianowicie jest artykuł na temat modelowania przypadków użycia przy użyciu LTS. Pytanie brzmi: co można łatwo udowodnić w LTS? Chciałbym ponownie wykorzystać istniejące rozwiązania, aby sprawdzić, czy są one przydatne w mojej aplikacji. Chciałbym wiedzieć, jakie właściwości LTS (i …

13 lo.logic formal-modeling model-checking program-verification automated-theorem-proving

5

Twardość problemów FPT

Osłonę wierzchołka można łatwo zredukować do zestawu niezależnego i odwrotnie. Jednak w kontekście sparametryzowanej złożoności zestaw niezależny jest trudniejszy niż osłona wierzchołka. Jądro z wierzchołków istnieje problem pokrycia wierzchołkowego, ale niezależnego zestawu jest biała 1 dysku.2k2k2k Jak zmienia się natura Independent Set w kontekście FPT i dlaczego?

13 cc.complexity-theory parameterized-complexity fixed-parameter-tractable

2

Jakie są obecnie otwarte problemy w teorii kompilatora?

Teoria kompilatora wydaje się być dość sprawdzonym przedmiotem. Jakie są otwarte problemy lub aktualne badania w tej dziedzinie?

13 soft-question big-list open-problem compilers