Teoretyczne informatyka

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

1
Uproszczona wersja Zwycięzca gry karcianej
Zadałem ten problem w MathOverflow , bez zadowalającej odpowiedzi. Rozważ następującą grę dla dwóch graczy, która jest uproszczeniem gry karcianej o nazwie Zwycięzca . (Poniższe sformułowanie zostało zaczerpnięte z komentarza Guillaume Brunerie na temat MathOverflow.) Jest dwóch graczy A i B. Każdy gracz ma zestaw kart (podzbiór { 1 , …
2
Zrozumienie dowodu projektu mechanizmu
Walczyłem ze szczegółami technicznymi dowodu dotyczącego teorii aukcji w tym artykule: http://users.eecs.northwestern.edu/~hartline/omd.pdf W szczególności Twierdzenie 2.5: Warunki konieczne i wystarczające dla prawdziwego mechanizmu. Mówiąc dokładniej, kierunek dowodu do przodu, podany na stronie 6. Definiując prawdziwą wartość jako oraz ogólną, być może fałszywą, wartość (np. Ofertę) jako , autor kontynuuje postulowanie …
2
Istnienie „matryc do barwienia”
Edycja: teraz jest pytanie uzupełniające związane z tym postem. Definicje Niech i będą liczbami całkowitymi. Używamy notacji .ccckkk[i]={1,2,...,i}[i]={1,2,...,i}[i] = \{1,2,...,i\} macierzy mówi się -to- barwiących matrycy , jeśli zachodzi:c×cc×cc \times cM=(mi,j)M=(mi,j)M = (m_{i,j})ccckkk mamy dla wszystkich ,mi,j∈[k]mi,j∈[k]m_{i,j} \in [k]i,j∈[c]i,j∈[c]i, j \in [c] dla wszystkich z i mamy .i,j,ℓ∈[c]i,j,ℓ∈[c]i,j,\ell \in [c]i≠ji≠ji …
1
Skutecznie rozwiązać system ścisłych nierówności liniowych ze wszystkimi współczynnikami równymi 1 bez użycia ogólnego solwera LP?
Według tytułu, oprócz korzystania z solwera LP ogólnego przeznaczenia, istnieje podejście do rozwiązywania układów nierówności względem zmiennych xja, ... ,xkxi,…,xkx_i, \ldots, x_k gdzie nierówności mają formę ∑ja ∈ jaxja&lt;∑j ∈ Jxjot∑i∈Ixi&lt;∑j∈Jxj\sum_{i \in I} x_i < \sum_{j \in J} x_j? Co ze szczególnym przypadkiem nierówności, które tworzą całkowity porządek nad sumami …
1
Liczenie liczby grubych obszarów pokrywających się z kwadratem
Pozwolić S.SSbyć kwadratem jednostkowym. W funkcjiββ\beta, jaka jest maksymalna liczba ββ\beta-tłuszczowe regiony rozłączne parami o średnicy co najmniej 1, które mogą się przecinaćS.SS? Poniżej podajemy liczbę, która to pokazuje β= 1β=1\beta=1, maksymalna liczba to 7. Po co β=2,3,…,nβ=2,3,…,n\beta = 2, 3, \ldots, n? Przywołaj definicję tłuszczu dla regionów w płaszczyźnie. …
1
Sparametryzowana złożoność liczenia rowerów
W poprzednim pytaniu Sparametryzowany algorytm znajdowania biklików zapytałem, czy istnieją szybkie sparametryzowane algorytmy do znalezieniak×kk×kk\times k-biclique in an nnn wykres wierzchołków i dowiedziałem się, że był otwarty, jeśli jest FPT wrt kkk. To samo odnosi się do liczeniak×kk×kk\times k-bikiety, czy wiadomo, że to #W\[1\]W\[1\]W\[1\]-hard wrt kkk (lub jakieś inne pojęcie …
1
Czy para rozłącznych cykli homotopowych w podwójnym rozdziela wykres?
Pozwolić solGG być wykresem osadzonym na orientowanej, zwartej powierzchni rodzaju solggtak aby osadzanie było komórkowe. Rozważ podwójność wykresusol∗G∗G^*. Pozwolićdo1C1C_1 i do2)C2C_2 być rozłącznymi cyklami w sol∗G∗G^* które są homotopiczne względem siebie i niech mi1E1E_1 i mi2)E2E_2 być ich odpowiednimi zestawami krawędzi w solGGodpowiednio. JestG ∖ (mi1∪mi2))G∖(E1∪E2)G \setminus (E_1 \cup E_2) …
2
Definicja formalna / część przeciwna w matematyce dla „obiektów” modeli obiektowych
To pytanie zadałem na forum matematyki SE i zostałem tutaj skierowany. Oto pytanie Jestem nowicjuszem zarówno w matematyce formalnej, jak i informatyce teoretycznej, więc proszę o wyrozumiałość, jeśli okaże się, że moje pytanie nie jest odpowiednio sformułowane. Modelowanie obiektowe wydaje się bardzo przydatne w definiowaniu złożonych interakcji podczas symulacji świata …
2
Wymiar VC kulek w 3 wymiarach
Szukam wymiaru VC następującego zestawu układów. Wszechświat U={p1,p2,…,pm}U={p1,p2,…,pm}U=\{p_1,p_2,\ldots,p_m\} takie, że U⊆R3U⊆R3U\subseteq \mathbb{R}^3. W ustawionym systemieRR\mathcal{R} każdy zestaw S∈RS∈RS\in \mathcal{R} odpowiada kuli w R3R3\mathbb{R}^3 tak, że zestaw SSS zawiera element w UUU tylko wtedy, gdy zawiera odpowiednią kulę R3R3\mathbb{R}^3. Szczegóły, które już znam. Wymiar VC jest co najmniej 4. Jest tak, …
2
Złożoność znalezienia separatora grafów o danej właściwości
Czy są znane wyniki na temat złożoności znalezienia separatora (dowolnej wielkości) spełniającego daną właściwość? Wiem, że separator kliki jest łatwy do znalezienia (czas wielomianowy), a także wiem, że wiele artykułów rozważa problem znalezienia małych separatorów lub separatorów, które pozostawiają połączone komponenty wielkości co najwyżej ułamka wielkości oryginalnego wykresu. Ale co, …
3
Specjalne przypadki graficzne TSP
W Graphic TSP otrzymujesz nieważony niekierowany wykressolsolG a celem jest znalezienie najkrótszej trasy w solsolGktóry odwiedza każdy wierzchołek przynajmniej raz . Zauważ, że NIE jest to to samo, co znalezienie obwodu hamiltonowskiegosolsolG. Moje pytania to: Jaka jest złożoność Graphic TSP na ograniczonych wykresach szerokości? Czy są jakieś specjalne przypadki Graficznego …
2
Wielokąt w ramach problemu generalizacji wielokąta
Chciałbym przeprosić wszystkie poniższe posty. Wybrałem niewłaściwe forum, aby pierwotnie to opublikować. Jednak zamiast uczynić to kompletnym marnotrawstwem, przerobiłem pytanie, aby było prawdziwym problemem „teoretycznej informatyki”. Problem: Utwórz algorytm, który pobiera zestaw n uporządkowanych punktów na płaszczyźnie 2D, które tworzą kontur prostego wielokąta A, który może, ale nie musi, być …
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.