Teoretyczne informatyka

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

2
Czy jest jakiś problem w
ΣP2Σ2P\mathsf{\Sigma^P_2}PP\mathsf{P} na ograniczonych wykresach szerokości drzewa. W rzeczywistości myślę, że te problemy są trudniejsze niż użycie normalnego programowania dynamicznego na wykresach ograniczonej szerokości do ich rozwiązania.
2
Czy szachy mogą symulować uniwersalną maszynę Turinga?
Szukam konkretnej odpowiedzi na pytanie tytułowe. Czy istnieje zbiór zasad, które przekładają dowolny program na konfigurację skończonych elementów na nieskończonej planszy, tak że jeśli czarno-biały gra tylko legalne ruchy, gra kończy się w skończonym czasie, jeśli program się zatrzymuje? Zasady są takie same jak zwykłe szachy minus 50 zasada ruchu, …
1
Czy możesz zdecydować o równoważności monotonicznych wyrażeń boolowskich, które nie zawierają negacji w PTIME?
Czy następujący problem występuje w trybie PTIME lub coNP-hard: Biorąc pod uwagę dwa wyrażenia logiczne i w zmiennyche1e1e_1e2e2e_2 , bez negacji (tzn. Wyrażenia są w całości budowane przez ∧ i ∨ ). Zdecyduj, czy e 1 ≡ e 2 , czyli mają taką samą wartość dla wszystkich przypisań do zmiennych.x1,…,xnx1,…,xnx_1,\dots,x_n∧∧\wedge∨∨\veee1≡e2e1≡e2e_1 …
4
Kiedy jest mniej publikacji?
Czy istnieją przypadki, w których dodatkowe publikacje mogą zaszkodzić Twojej dokumentacji? Pozwala to uniknąć oczywistych przypadków, w których publikujesz nieprawidłowe lub kontrowersyjne wyniki. Unikaj także przypadku czasu skończonego: masz tylko tyle czasu na myślenie i pisanie, więc napisanie artykułu może spowodować utratę czasu na inny projekt. Przykładem zastosowania może być: …
1
Algorytm optymalizacji drzew decyzyjnych
tło Binarne drzewo decyzja TTT jest zakorzenione drzewo gdzie każdy węzeł wewnętrzny (i korzeń) jest oznaczony przez indeks w j∈{1,...,n}j∈{1,...,n}j \in \{1,..., n\} taki sposób, że żadna ścieżka od korzenia do liścia nie powtarza indeksu, liście są oznaczone wyjściami w {A,B}{A,B}\{A,B\} , a każda krawędź jest oznaczona przez 000 dla …
2
Paradygmaty analizy złożoności algorytmów
Analiza najgorszych i średnich przypadków to dobrze znane miary złożoności algorytmu. Niedawno wygładzona analiza pojawiła się jako kolejny paradygmat wyjaśniający, dlaczego niektóre algorytmy wykładnicze w najgorszym przypadku działają tak dobrze w praktyce, na przykład algorytm simpleksowy. Moje pytanie brzmi - czy istnieją jakieś inne paradygmaty do pomiaru złożoności algorytmu? Szczególnie …
1
Skuteczne połączenie DFA?
Istnieją teoretyczne dowody na to, że naiwna konstrukcja produktu kartezjańskiego na przecięciu DFA jest „najlepsza, co możemy zrobić”. Co z konkatenacją dwóch DFA? Trywialna konstrukcja polega na przekształceniu każdego DFA w NFA, dodaniu przejścia epsilon i określeniu wynikowego NFA. Czy możemy zrobić lepiej? Czy znane jest ograniczenie wielkości minimalnej DFA …
1
Poszukuję oryginalnego papieru LCF Scotta
Czy następujący manuskrypt jest publicznie dostępny? Dana Scott, 1969, Teoria funkcji obliczeniowych wyższego typu . Niepublikowane notatki z seminarium, 7 stron, University of Oxford. Omówienie tego artykułu znajduje się w rozdziale 8.1.2, Typy jako zbiory , w Cardone i Hindley, 2006 Historia rachunku Lambda i logiki kombinatorycznej ; dodatkowo rozdział …
1
Jak nazywa się ten problem z grafem skierowanym?
Wykonaj ukierunkowany wykres gdzie krawędzie są ozdobione naturalną liczbą. Chcemy zestawu wszystkich ścieżek między dwoma wierzchołkami v 1 i tak aby każda kolejna krawędź ścieżki była ozdobiona liczbą naturalną, która jest większa niż liczba naturalna dekorująca poprzednią krawędź.GGGv 2P.P.Pv1v1v_1v2)v2)v_2 Przykładem może być rozkład jazdy autobusów lub pociągów. Jeśli próbujesz ustalić …
3
Czy istnieje nazwa „rzeczy fizycznych, z których można zbudować maszynę Turinga”?
Jedną z niesamowitych rzeczy w informatyce jest to, że fizyczne wdrożenie jest w pewnym sensie „nieistotne”. Ludzie z powodzeniem zbudowali komputery z kilku różnych podłoży - przekaźników, lamp próżniowych, dyskretnych tranzystorów itp. Ludzie mogą wkrótce odnieść sukces w budowie komputerów Turinga z nieliniowych materiałów optycznych, różnych biomolekuł i kilku innych …
3
Czy istnieje jakaś teoria języka programowania opisująca obce interfejsy funkcji (FFI) i powiązania wielu języków?
Czy istnieje jakaś teoria języka programowania opisująca obce interfejsy funkcji (FFI) i powiązania wielu języków? Zadałem kilka problemów związanych z implementacją przepływu stosu , co tutaj nie jest odpowiednie. Ale chciałbym zapytać z widoku tej strony i zobaczyć, co mógłbym stąd uzyskać. Naprawdę doceniam twoją odpowiedź! Dzięki Dave'owi Clarke'owi za …
1
Tautologie / sprzeczności średnich przypadków, poza przypadkowym modelem k-CNF
Jest dobrze wiadomo, że losowy Preparaty -cnf na n zmiennymi c n klauzule unsatisfiable (tj sprzeczności), z dużym prawdopodobieństwem, na wystarczająco dużej stałej C . Tak więc losowe formuły k- CNN (dla c wystarczająco dużych) stanowią naturalny rozkład w niezadowalających formułach boolowskich (lub podwójnie w tautologiach, tj. Negacjach sprzeczności). Ten …
3
Ładowanie struktury palca
Po dłuższej pracy z 2-3 palcami jestem pod wrażeniem ich szybkości w większości operacji. Jednak jedynym problemem, na jaki natknąłem się, jest duży koszt związany z początkowym utworzeniem dużego drzewa palców. Ponieważ budowanie jest definiowane jako sekwencja operacji konkatenacji, kończy się budowanie dużej liczby niepotrzebnych struktur drzewa palcowego. Ze względu …
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.