Teoretyczne informatyka

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

2
Algorytm Max-Cut, który nie powinien działać, nie wiadomo dlaczego
OK, może się to wydawać pytaniem o pracę domową iw pewnym sensie tak jest. Jako zadanie domowe w klasie algorytmów licencjackich podałem następujący klasyk: Biorąc pod uwagę nieukierowany wykres , podaj algorytm, który znajdzie cięcie taki sposób, że , gdzie to liczba krawędzi przecinających cięcie. Złożoność czasowa musi wynosić .G=(V,E)G=(V,E)G=(V,E)(S,S¯)(S,S¯)(S,\bar{S})δ(S,S¯)≥|E|/2δ(S,S¯)≥|E|/2\delta(S,\bar{S})\geq …
4
Podręcznik języka i automatów, darmowy czy tani?
W przyszłym semestrze będę prowadził standardowe studia licencjackie z języków i automatów i wolałbym korzystać z legalnego bezpłatnego lub taniego tekstu. Jakieś sugestie? Uwielbiam tekst Sipser, ale najnowsze wydanie kosztuje 196 USD, co trudno powiedzieć z prostą miną w dobie bezpłatnych kursów.
5
Powody, dla których wykres może nie być
Rozważając nieco to pytanie , próbowałem zidentyfikować wszystkie różne powody, dla których wykres może nie być k kolorowy. Są to jedyne 2 powody, które udało mi się dotychczas zidentyfikować:G=(VG,EG)G=(VG,EG)G = (V_G,E_G)kkk zawiera klikę o rozmiarze k + 1 . To oczywisty powód.GGGk+1k+1k+1 Istnieje podrozdział z G, taki że oba poniższe …
1
Jakie są kariery w informatyce teoretycznej, które nie wymagają doktoratu?
Jestem studentem i niedawno pogodziłem się z faktem, że mogę nie mieć rozumu do prowadzenia badań w dziedzinie informatyki teoretycznej lub być w stanie zostać dopuszczonym i ukończyć program doktorancki. Chciałbym jednak nadal zajmować się informatyką teoretyczną, ponieważ uważam ją za bardzo interesującą. Jak dotąd jedynymi karierami w informatyce teoretycznej, …
1
Przybliżony 1d TSP z porównaniami liniowymi?
Jednowymiarowy problem ścieżki sprzedawcy podróży jest oczywiście tym samym, co sortowanie, a zatem można go rozwiązać dokładnie przez porównanie w czasie , ale sformułowano go w taki sposób, aby przybliżenie, a także dokładne rozwiązanie ma sens. W modelu obliczeń, w którym dane wejściowe są liczbami rzeczywistymi i możliwe jest zaokrąglanie …
2
Obwody dolne granice i złożoność Kołmogorowa
Rozważ następujące uzasadnienie: Niech oznacza złożoność Kołmogorowa ciągu . Twierdzenie Chaitina o niekompletności tak mówiK(x)K(x)K(x)xxx dla jakiejkolwiek spójnej i wystarczająco silny system formalny , istnieje stała (zależnie tylko od formalnego systemu i jego języka) tak, że dla każdej struny , nie może udowodnić, że .SSSTTTxxxSSSK(x)≥TK(x)≥TK(x) \geq T Niech będzie funkcją …
1
Czy
Czy istnieje jakakolwiek prawdopodobna hipoteza złożoności / kryptografii, która wyklucza możliwość, że obwody wielomianowe mają rozmiar podwykładniczy (tj. z ) ograniczoną głębokością ( ) obwody? ϵ&lt;1d=O(1)2)O ( nϵ)2O(nϵ)2^{O(n^\epsilon)}ϵ &lt; 1ϵ&lt;1\epsilon<1re= O ( 1 )d=O(1)d = O(1) Wiemy, że każdą funkcję obliczalną przez obwód można obliczyć na podstawie obwodu głębokości (używając …
2
Czy dodawanie można przeprowadzić na głębokości mniejszej niż 5?
Stosując algorytm przenoszenia patrzeć w przyszłość możemy obliczyć dodatek za pomocą wielomianu głębokość rozmiar 5 (lub 4?) C 0 rodzinę obwodu. Czy można zmniejszyć głębokość? Czy możemy obliczyć dodanie dwóch liczb binarnych przy użyciu wielomianowej rodziny obwodów o głębokości mniejszej niż uzyskana za pomocą algorytmu carry look forward?AC0AC0AC^0 Czy są …
2
Czy obwody AND i OR P-są kompletne?
Bramka AND &amp; OR jest bramką, która ma dwa wejścia i zwraca ich AND oraz OR. Czy obwody wykonane tylko z bramki AND &amp; OR, bez fanouta, mogą wykonywać dowolne obliczenia? Mówiąc ściślej, czy obszar logiczny obliczeń wielomianowych można zredukować do obwodów AND i OR? Moja motywacja do rozwiązania tego …
3
Od ekstraktorów do generatorów pseudolosowych?
Luca Trevisan pokazał, ile konstrukcji generatorów pseudolosowych można uznać za konstrukcje ekstraktorów: http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf Czy istnieje sensowna rozmowa? Tj. Czy „naturalne” konstrukcje ekstraktorów można traktować jako konstrukcje pseudolosowych generatorów (PRG)? Konstrukcje ekstraktorów wydają się odpowiadać rozkładom na PRG (tak, że żadnemu wyróżniającemu nie uda się rozróżnić dla prawie wszystkich z nich). …
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.