Teoretyczne informatyka

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

4
Odzyskiwanie nachylenia cyfrowej linii
Czy były prace nad odzyskaniem nachylenia segmentu linii po digitalizacji? Oczywiście nie można tego zrobić z idealną dokładnością; to, czego się chce, to metoda wyprowadzenia z linii cyfrowej przedziału możliwych nachyleń. (Pojęcie cyfrowej linii, której używam, to Rosenfelda: zbiór par gdzie rozciąga się na liczbach całkowitych (lub bloku kolejnych liczb …
2
Czy wyroki są stowarzyszone?
To pytanie może mieć oczywistą odpowiedź ... ale oto i tak pytanie. Intuicyjnie jest to następujące prawdopodobne stwierdzenie - „maszyna z podprogramem A, który z kolei ma podprogram B, jest tym samym, co maszyna z podprogramem A, który ma dostęp do podprogramu B”. Aby formalnie zdefiniować ten problem, użyję niekonwencjonalnej …
2
Maksymalne dopasowanie M z warunkiem G [M] jest wolne od 2K_2
Czy w literaturze jest coś zbliżonego do następującego problemu: Biorąc pod uwagę dwuczęściowy wykres ze zrównoważonym dwuczęściowym , czy istnieje idealne dopasowanie w tak że dla każdej 2 krawędzi występuje krawędź lub krawędź (lub oba) w ?G ( V, E)G(V,E)G(V,E){ U, W}{U,W} \{U,W\}M.M M solG G u1w1,u2)w2)∈ M.u1w1,u2w2∈Mu_1w_1, u_2w_2\in M …
11 matching 
2
„Krewni” problemu najkrótszej ścieżki
Rozważ dołączony niekierowany wykres z nieujemnymi wagami krawędzi i dwoma wyróżnionymi wierzchołkami . Poniżej przedstawiono niektóre problemy ze ścieżką, które mają następującą postać: znajdź ścieżkę , tak aby jakaś funkcja ciężaru krawędzi na ścieżce była minimalna. W tym sensie wszyscy są „krewnymi” problemu najkrótszej ścieżki; w tym ostatnim funkcja jest …
1
Czy uczeń Alana Turinga, Robin Gandy, stwierdził, że Charles Babbage nie ma pojęcia o uniwersalnej maszynie komputerowej?
Robin Gandy był uczniem Alana Turinga . Gandy przeprowadził analizę silnika analitycznego Babbage'a (patrz „Gandy - zbieżność pomysłów w 1936 r.” Cytowany w „Herken, Rolf - Uniwersalna maszyna Turinga - badanie półwiecze. Springer Verlag”) - i powiedział, że tak (por. s. 52–53): Funkcje arytmetyczne +, -, ×, gdzie - oznacza …
1
Jak trudno jest zdecydować o istnieniu idealnego dopasowania czerwono-niebieskiego?
Idealnym rozwiązaniem dwukolorowego dopasowania jest decyzja, czy wykres ma koloryt w dwóch kolorach, tak aby każdy węzeł miał dokładnie jednego sąsiada tego samego koloru co on sam. Schaefer udowodnił, że problem jest NP-zupełny . Pozostaje NP-kompletny nawet dla płaskich wykresów sześciennych. Interesuje mnie wariant, w którym chcemy zdecydować, czy wykres …
1
Przeszkoda taka jak ETH
Wiemy, że pod miT.H.ETHETH nie możemy rozwiązać K.KK sumy w czasie fa( K) p o l y( n K.)f(K)poly(nK)f(K)poly(nK) ramach dowolnej funkcji fa( K)f(K)f(K) (zwykle 2)O ( K)2O(K)2^{O(K)} ). Czy istnieje przypuszczenie, które zapobiega złożoności ( logn )O ( K)(log⁡n)O(K)(\log n)^{O(K)} (jest to całkowicie zgodne z możliwością, ponieważ K.= Ω …
1
P i złożoność opisowa
W zoo o złożoności napisano [ 1 ], że w złożoności opisowej można zdefiniować za pomocą trzech różnych rodzajów wzorów, który jest również , a także jako .PPPFO(LFP)FO(LFP)FO(LFP)FO(nO(1))FO(nO(1))FO(n^{O(1)})SO(HORN)SO(HORN)SO(HORN) Istnieją jednak pewne wyjątki, na przykład nie może być wyrażona przez FP (FP ma taką samą moc ekspresji z LFP). i nie …
2
Intuicja za ścisłą pozytywnością?
Zastanawiam się, czy ktoś może dać mi intuicję, dlaczego ścisła pozytywność indukcyjnych typów danych gwarantuje silną normalizację. Dla jasności widzę, jak negatywne zdarzenia prowadzą do rozbieżności, tj. Poprzez zdefiniowanie: data X where Intro : (X->X) -> X możemy napisać rozbieżną funkcję. Zastanawiam się jednak, jak możemy udowodnić, że ściśle pozytywne …
1
Klasy złożoności obwodów liniowych
Klasa to funkcje klasy obliczalne przez rodziny obwodów ograniczonego wielkości i głębokości . -hierarchy jest sumą tych klas.NCjaNCi\textrm{NC}^inO ( 1 )nO(1)n^{O(1)}O ( logja( n ) )O(logi⁡(n))O(\log^i(n))NCNC\textrm{NC} Czy jest jakieś badanie wariantu wielkości hierarchicznej tej hierarchii? Czy to rodziny obwodów ograniczonego wachlarza, głębokości polilogu i rozmiaru liniowego? Wiem, że istnieje trochę …
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.