Teoretyczne informatyka

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

1
Przewodnictwo i średnica na zwykłych wykresach
G=(V,E)G=(V,E)G=(V,E)minS⊂V e(S,Sc)min(|S|,|Sc|),minS⊂V e(S,Sc)min(|S|,|Sc|),\min_{S \subset V} ~\frac{e(S,S^c)}{\min(|S|,|S^c|)},e(S,Sc)e(S,Sc)e(S,S^c)SSSScScS^c Bardziej konkretnie przypuszczać wiem średnica wynosi co najmniej (albo co najwyżej) . Co to mówi mi o przewodności, jeśli w ogóle? I odwrotnie, przypuśćmy, że wiem, że przewodnictwo wynosi co najmniej (lub przynajmniej) . Co to mówi mi o średnicy, jeśli w ogóle?DDDαα\alpha
1
Uderzanie w nieparzyste cykle
Czy jest coś znanego na temat następującego problemu? Czy to w ogóle ma sens? Jak to jest nazywane? Czy jest to banalnie równoważne z jakimś innym problemem? Jaka jest złożoność czasu? Biorąc pod uwagę nieukierowany (ogólny / płaski / ograniczony / itd.) Wykres G = (V, E), znajdź maksymalny podzbiór …
2
Dark Integers: Obliczenia ogólnego przeznaczenia na routerach internetowych
Greg Egan w swojej powieści „Dark Integers” (opowieść o dwóch wszechświatach z dwiema różnymi matematykami komunikującymi się poprzez dowodzenie twierdzeń o niespójności arytmetycznej) twierdzi, że możliwe jest zbudowanie komputera ogólnego przeznaczenia wyłącznie na istniejących routerach internetowych przy użyciu tylko jego podstawowej funkcjonalności przełączania pakietów (a dokładniej korekty sumy kontrolnej). Czy …
5
Najlepsza książka na temat implementacji metody Simplex?
Interesuje mnie implementacja SM dla zadania LP, jednak słyszałem o możliwych pułapkach: książka Cormena mówi, że możliwe jest posiadanie danych wejściowych, które sprawią, że naiwna implementacja zachowa się w wykładniczym czasie. Słyszałem również, że naiwna implementacja może zapętlać dane. Czy istnieje książka / artykuł / źródło wyjaśniające niuanse praktycznego wdrażania …
6
Graf płaski na przecięciu grubych rzeczy?
Istnieje piękne twierdzenie Koebe'a (patrz tutaj ), które stwierdza, że ​​każdy płaski wykres można narysować jako wykres całowania dysków (bardzo romantyczny ...). (Mówiąc nieco inaczej, każdy wykres płaski można narysować jako wykres przecięcia dysków.) Twierdzenie Koebe'a nie jest łatwe do udowodnienia. Moje pytanie: czy istnieje łatwiejsza wersja tego twierdzenia, w …
2
Klasa złożoności odpowiadająca sortowaniu
Dwie części TCS to algorytmy i złożoność. Upraszczając powiem, że algorytmy to badanie górnych granic, pokazujące, że możesz coś zrobić (przy danych ograniczonych zasobach), a złożoność polega na pokazaniu, że nie możesz tego zrobić bez minimalnych zasobów. Tak często problem algorytmiczny pojawia się w modelu decyzyjnym, aby umieścić go w …
1
Dolne granice wielkości CFG dla określonych języków skończonych
Rozważ następujące naturalne pytanie: Biorąc pod uwagę skończony język , jaka jest najmniejsza bezkontekstowa gramatyka generująca ?L.L.LL.L.L Możemy uczynić pytanie bardziej interesującym, określając sekwencję języków , na przykład jest zbiorem wszystkich permutacji : intuicyjnie, CFG dla „musiałby” mieć rozmiar . Jesteśmy więc zainteresowani asymptotycznym rozmiarem najmniejszych CFG dla języków.L.nL.nL_nL.nL.nL_n{ 1 …
3
Dolne granice dla struktur danych
Czy znane są wyniki, które wykluczają istnienie struktur danych „zbyt dobrych, by były prawdziwe”? Na przykład: czy można dodać funkcjonalność SplitSplitSplit i do struktury danych obsługi zamówień (patrz Dietz i Sleator STOC '87 ) i nadal uzyskiwać operacje czasowe ?JoinJoinJoinO(1)O(1)\mathcal{O}(1) Lub: czy można zaimplementować uporządkowany zestaw z kluczami całkowitymi i …
2
Kompromis czasoprzestrzenny i najlepszy algorytm
Rozważmy język taki jak:LLL L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) i tak L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) Innymi słowy, najszybsza maszyna oblicza L w czasie O ( f ( n ) ), a najbardziej wydajna pod względem przestrzeni maszyna M ' oblicza L , używając przestrzeni O ( g ( n …
2
Algorytm sortowania par liczb
Zadałem już to pytanie przy przepełnieniu stosu , ale może lepiej pasuje do tej witryny. Problemem jest: Mam N par liczb całkowitych bez znaku. Muszę je posortować. Wektor końcowy par należy posortować nie malejąco według pierwszej liczby w każdej parze i nieskończenie według drugiej liczby w każdej parze. Każda para …
4
Zliczanie liczby osłon wierzchołków: kiedy jest to trudne?
Rozważmy problem # P-zupełny liczenia liczby osłon wierzchołków danego wykresu G=(V,E)G=(V,E)G = (V, E) . Chciałbym wiedzieć, czy jest jakikolwiek wynik pokazujący, jak twardość takiego problemu zmienia się w zależności od parametru (na przykład ).GGGd=|E||V|d=|E||V|d = \frac{|E|}{|V|} Mam wrażenie, że problem powinien być łatwiejszy zarówno wtedy, gdy jest rzadki, jak …
6
Co wiadomo na temat skuteczności niezawodnego przetwarzania?
Jak dobrze zbadano następujący problem w TCS? (Przepraszam, jeśli opis problemu brzmi niejasno!) Biorąc pod uwagę model obliczeń MC (maszyna Turinga, automaty komórkowe, maszynę Kolmogorov-Uspenskii ... itd.) Oraz model hałasu, który mógłby wpływać na obliczenia MC, istnieje sposób na odzyskanie po błędach spowodowanych przez ten hałas w skuteczny sposób? Na …
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.