Teoretyczne informatyka

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

2
Emulacja Oblivious Turing Machine w dolnej granicy
Czy istnieje dowód, że emulacji maszyny Turinga na nieświadomej maszynie Turinga nie można wykonać w mniej niż gdzie jest liczbą kroków, które wykonuje maszyna Turinga ? Czy to tylko górna granica?O ( m logm )O(mlog⁡m)\mathcal{O}\left(m\log m\right)mmm W artykule Paula Vitányi o relatywizowanych, nieświadomych maszynach Turinga, twierdzi Vitányi „Oni [ Pippenger …
1
Algorytmiczny problem wektorowy
Mam problem algebraiczny związany z wektorami w dziedzinie GF (2). Niech będą wektorami wymiaru , a . Znaleźć wielomianowej algorytm czasową znajdzie (0,1)-wektor tego samego wymiaru tak, że nie jest sumą każdy wektory między . Dodawanie wektorów odbywa się ponad polem GF (2), które ma dwa elementy 0 i 1 …
2
Koncepcyjnie proste konstrukcje drzewne z sufiksem czasu liniowego
W 1973 r. Weiner przedstawił pierwszą konstrukcję drzewek z przyrostkami. Algorytm został uproszczony w 1976 r. Przez McCreighta, aw 1995 r. Przez Ukkonen. Niemniej jednak uważam, że algorytm Ukkonen jest stosunkowo zaangażowany koncepcyjnie. Czy istnieją uproszczenia algorytmu Ukkonen od 1995 roku?
1
Złożoność dominującego problemu w określonych podklasach wykresów akordowych
Interesuje mnie złożoność problemu dominującego zestawu (DSP) w niektórych określonych klasach grafów, które są podklasami grafów akordowych . Wykres jest nieukierowanym wykresem ścieżki, jeśli jest to wykres przecięcia wierzchołków rodziny ścieżek w jakimś niekierowanym drzewie. Niech UP będzie klasą niekierowanych grafów ścieżek. Wykres jest grafem EPT, jeśli jest to wykres …
2
Zastosowanie liczb Ramseya
Definicja liczb Ramseya jest następująca: Niech jest dodatnią liczbą taką, że każdy wykres zamówienia na przynajmniej R ( , b ) obejmuje albo klika w ciągu wierzchołków lub zestaw się na stałym b wierzchołków.R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)aaabbb Pracuję nad jakimś rozszerzeniem Ramsey Numbers. Chociaż badanie ma pewne teoretyczne zainteresowania, ważne byłoby poznanie motywacji …
4
Modelowanie obiektów (OOP) w teorii typów zależnych
Interesuje mnie modelowanie obiektów, od programowania obiektowego, w teorii typów zależnych. Jako możliwą aplikację chciałbym mieć model, w którym mogę opisać różne cechy imperatywnych języków programowania. Znalazłem tylko jeden artykuł na temat modelowania obiektów w teorii typów zależnych, a mianowicie : Programowanie obiektowe w teorii typów zależnych A. Setzer (2006) …
6
Porady dla absolwentów szkół informatycznych
Szukam porady i opinii. Wstęp: Jestem studentem matematyki na studiach pierwszego stopnia, zainteresowanym informatyką teoretyczną (złożoność obliczeniowa, teoria grafów, kombinatoryka). Chcę kontynuować doktorat z informatyki i skupić się na teorii. Moje doświadczenie obejmuje matematyczne dziedziny informatyki, ale brakuje mi bardziej stosownego doświadczenia w informatyce. W szczególności muszę ukończyć kursy programowania, …
1
Terminy Lambda-Calculus, które redukują się do siebie
W mojej ciągłej próbie nauki rachunku różniczkowego lambda, „Lambda-Calculus and Combinators an Introduction” Hindleya i Seldina wymienia następujący artykuł (autorstwa Bruce'a Lerchera), który dowodzi, że jedynym redukowalnym wyrażeniem jest to samo (konwersja modulo alfa) to: .( λ x . x x ) ( λ x . x x )(λx.xx)(λx.xx)(\lambda x.xx)(\lambda …
4
Obliczanie funkcji Mobiusa
Funkcja Mobiusa jest zdefiniowana jako μ ( 1 ) = 1 , μ ( n ) = 0, jeśli n ma kwadratowy współczynnik liczby pierwszej , a μ ( p 1 … p k ) = ( - 1 ) k, jeśli wszystkie liczby pierwsze p 1 , … , …
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.