Teoretyczne informatyka

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

4
Czym różnią się języki rozkazujące od języków funkcjonalnych?
Czytam Simona Peytona Jonesa Implementation of Functional Programming Languages i jest jedno zdanie, które mnie trochę zaskoczyło (na stronie 39): W znacznie większym stopniu niż w przypadku języków imperatywnych języki funkcjonalne są w dużej mierze odmianami składniowymi, przy stosunkowo niewielkich różnicach semantycznych. Teraz zostało to napisane w 1987 roku i …
3
Czy istnieje algorytm aproksymacji stałego współczynnika dla problemu kolorowania prostokąta 2D?
Problem, który rozważamy tutaj, to rozszerzenie znanego problemu kolorowania interwałów. Zamiast przedziałów uważamy prostokąty o bokach równoległych do osi. Celem jest pokolorowanie prostokątów przy użyciu minimalnej liczby kolorów, tak aby każdemu z dwóch nachodzących na siebie prostokątów przypisano różne kolory. Ten problem jest znany jako trudny dla NP. Xin Han, …
3
Wydajne algorytmy przestrzeni logów
Łatwo zauważyć, że każdy problem, który można rozstrzygnąć w deterministycznej przestrzeni logicznej ( ), pojawia się co najwyżej w czasie wielomianowym ( P ). Wiele znanych algorytmów przestrzeni logicznej (na przykład: nieukierowana łączność st, izomorfizm płaskiego wykresu) działa w O ( n k ), gdzie k jest niesamowicie duże.L.L.LP.P.PO ( …
4
Złożoność znalezienia drugiego rozwiązania przy poprawnym rozwiązaniu problemu NP-zupełnego
Chcę dowiedzieć się, czy istnieją jakieś ogólne wyniki lub przykłady dotyczące kompletności NP problemu znalezienia drugiego rozwiązania problemu NP-zupełnego. Dokładniej, jestem zainteresowany wszelkimi problemami następującej formy: Biorąc pod uwagę rozwiązanie na przykład I z NP-pełnej problemem jest to, że roztwór S ' ≠ S do I ?SSSIjaIS′≠SS′≠SS' \neq SIII Docenione …
2
Czas pokrycia kierowanych wykresów
Biorąc pod uwagę losowy spacer na wykresie, czas pokrycia jest pierwszym (oczekiwana liczba kroków), że każdy wierzchołek został trafiony (pokryty) przez spacer. W przypadku podłączonych niekierowanych wykresów czas pokrycia jest znany z górnej granicy . Istnieją silnie połączone digrafy z wykładniczym czasem pokrycia w n . Przykładem tego jest dwuznakiem …
1
Zestawy stopni dla liniowych wykresów rozszerzenia
Liniowe rozszerzenie L.L.L z poset P.P.\mathcal{P} jest liniowy porządek na elementach P.P.\mathcal{P} tak, że x ≤ yx≤yx \leq y w implikuje w dla wszystkich . x ≤ y L x , y ∈ PP.P.\mathcal{P}x ≤ yx≤yx \leq yL.L.Lx , y∈ P.x,y∈P.x,y\in\mathcal{P} Liniowy wykres przedłużenie jest wykresem na zestawie liniowe przedłużenie …
1
Struktura instancji patologicznych dla algorytmów simpleks
O ile rozumiem, wszyscy znają deterministyczne reguły przestawne dla algorytmów simpleksowych mają określone dane wejściowe, na których algorytm wymaga czasu wykładniczego (lub przynajmniej nie wielomianowego), aby znaleźć optymalne. Nazwijmy te przypadki „patologicznymi”, ponieważ zwykle (tj. Na większości danych wejściowych) algorytm simpleks kończy się szybko. Pamiętam z mojego kursu programowania matematycznego, …
5
Satysfakcja z ograniczeń otwartych lub interaktywnych
W przeszłości wdrażałem modele koordynacji, wykorzystując SAT i regularną satysfakcję z ograniczeń jako podstawowy koń roboczy w ich silnikach. Kontynuując tę ​​linię pracy, chciałbym uczynić modele bardziej interaktywnymi, a najlepszym sposobem, jaki to widzę, jest otwarcie solvera więzów, aby nie był już czarną skrzynką. Dlatego chcę dowiedzieć się więcej na …
17 sat  lo.logic  csp 
5
Czy komputer może symulować się jako część symulowanego świata?
Załóżmy, że budujesz komputer, który będzie obliczał stan wszystkich atomów we Wszechświecie w pewnym momencie w przyszłości. Ponieważ Wszechświat jest z definicji wszystkim, co istnieje (i wszystkim, co wchodzi w interakcję z resztą), obejmuje także komputer, który budujesz. Czy potrafisz obliczyć stan wszystkich atomów we Wszechświecie za pomocą komputera, w …
3
Formalna reprezentacja pierścieni w obliczeniach
Czytając artykuł na temat stosowania metod algebraicznych do wykrywania niektórych indukowanych subgrafów, okazuje się, że ideał krawędzi jest ważnym narzędziem łączącym algebrę komutacyjną i teorię grafów. Skoro nie znam obliczeń obiektów algebraicznych, czy są jakieś dobre odniesienia lub książki na ten temat? Szczególność w reprezentowaniu pierścienia R na maszynie Turinga …
3
Randomize or Not?
To pytanie jest inspirowane koszulką Georgia Tech Al Algorytmy i Randomness Center , która pyta „Randomize or not ?!” Istnieje wiele przykładów, w których randomizacja pomaga, szczególnie podczas działania w środowiskach przeciwnych. Istnieją również ustawienia, w których losowanie nie pomaga ani nie boli. Moje pytanie brzmi: Jakie są ustawienia, kiedy …
3
Właściwości losowo ukierunkowanych wykresów z ustalonym kątem końcowym
Interesują mnie właściwości losowo ukierunkowanych wykresów o ustalonym out-stopniu ddd . Wyobrażam sobie losowy model wykresu, w którym każdy wierzchołek wybiera u sąsiadów (powiedzmy z zamiennikiem) Pytanie : Czy coś wiadomo o rozkładzie stacjonarnym i czasach mieszania losowych spacerów na tych losowych grafach (dla różnych wartości )? ddd Szczególnie interesuje …
2
Twardość sparametryzowanego CLIQUE?
Niech 0≤p≤10≤p≤10\le p\le 1 i rozważmy problem decyzyjny Klika P Wejście: całkowita s , wykres G z T wierzchołki krawędzie Pytanie: sposób zawierać klika na co najmniej wierzchołki?pp_p sssGGGtttGs⌈p(t2)⌉⌈p(t2)⌉\lceil p\binom{t}{2} \rceil GGGsss Instancja CLIQUE zawiera proporcję spośród wszystkich możliwych krawędzi. Wyraźnie CLIQUE jest łatwy dla niektórych wartości . CLIQUE zawiera …
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.