Teoretyczne informatyka

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

4
Dlaczego traktujemy log-space jako model wydajnego obliczania (zamiast polilog-space)?
To może być pytanie subiektywne, a nie konkretne, ale tak czy inaczej. W teorii złożoności badamy pojęcie wydajnych obliczeń. Istnieją klasy takie jak oznacza czas wielomianowy , a L oznacza miejsce na log . Oba są uważane za reprezentowane jako rodzaj „wydajności” i dość dobrze wychwytują trudności niektórych problemów.PP\mathsf{P}LL\mathsf{L} Istnieje …
11
Jaki jest najskuteczniejszy sposób generowania losowej permutacji na podstawie probabilistycznych zamian par?
Pytanie, które mnie interesuje, dotyczy generowania przypadkowych permutacji. Biorąc pod uwagę probabilistyczną bramę wymiany par jako podstawowy element konstrukcyjny, jaki jest najbardziej skuteczny sposób na uzyskanie jednolicie losowej permutacji elementów? Tu stosować „probabilistyczny bramy parami wymiany” się operacja, która realizuje brama Przełączanie do wybranych elementów i z pewnym prawdopodobieństwem , …
3
Czy istnieje rozsądne pojęcie algorytmu aproksymacyjnego dla nierozwiązywalnego problemu?
Niektóre problemy są nierozstrzygalne, ale mimo to można poczynić pewne postępy w ich rozwiązywaniu. Na przykład problem zatrzymania jest nierozstrzygalny, ale można poczynić praktyczne postępy w tworzeniu narzędzi do wykrywania potencjalnych nieskończonych pętli w kodzie. Problemy z układaniem płytek są często nierozstrzygalne (np. Czy ta płytka poliomino ma jakiś prostokąt?), …
2
Teoria wykonalności: różnica mocy między rachunkiem lambda a maszynami Turinga
Mam trzy powiązane pytania, które są zaznaczone punktorami poniżej (nie, nie można ich podzielić, jeśli się zastanawiasz). Andrej Bauer napisał tutaj , że niektóre funkcje można realizować za pomocą maszyny Turinga, ale nie za pomocą rachunku lambda. Kluczowym krokiem jego rozumowania jest: Jeśli jednak użyjemy rachunku lambda, wówczas [program] c …
12
Jakie są teoretyczne podstawy programowania imperatywnego?
Programowanie funkcjonalne ma teoretyczne podstawy w rachunku lambda i logice kombinatorycznej . Jako osoba zajmująca się obliczeniami statystycznymi uważam te koncepcje za bardzo przydatne do modelowania. Czy istnieje równoważna matematyczna podstawa programowania imperatywnego , czy może po prostu wyrosła z praktycznej aplikacji sprzętowej w języku maszynowym i późniejszego rozwoju FORTRAN …
8
Czy istnieją dowody istnienia niekonstruktywnego algorytmu?
Pamiętam, że mogłem spotkać odniesienia do problemów, które zostały udowodnione, że można je rozwiązać ze szczególną złożonością, ale bez znanego algorytmu, który by faktycznie osiągnął tę złożoność. Walczę z tym, jak to się dzieje; jak wyglądałby niekonstruktywny dowód na istnienie algorytmu. Czy rzeczywiście istnieją takie problemy? Czy mają dużą wartość …
6
Sposoby, aby matematyk był informowany o bieżących badaniach w teorii złożoności
Teoria złożoności jest moim drugorzędnym zainteresowaniem, ale nie jest moim głównym zainteresowaniem badawczym, więc nie mam nadziei, że wezmę udział we wszystkich konferencjach, przeczytam wszystkie blogi i upewnię się, że „w” tłumie cc: ja na każdym gorące wiadomości. Próbuję to zrobić, ale zastanawiam się, jakie metody przyniosą mi największe zyski …
3
Płytkie kontra głębokie osadzanie
Podczas kodowania logiki w asystencie dowodu, takim jak Coq lub Isabelle, należy dokonać wyboru między użyciem płytkiego a głębokiego osadzenia. W płytkim osadzaniu formuły logiczne są zapisywane bezpośrednio w logice twierdzenia twierdzącego, podczas gdy w głębokim osadzaniu formuły logiczne są reprezentowane jako typ danych. Jakie są zalety i ograniczenia różnych …
20
Trudne problemy z NP na drzewach
Kilka problemów optymalizacyjnych, o których wiadomo, że są trudne do NP na grafach ogólnych, można w prosty sposób rozwiązać w czasie wielomianowym (niektóre nawet w czasie liniowym), gdy grafem wejściowym jest drzewo. Przykłady obejmują minimalną osłonę wierzchołków, maksymalny niezależny zestaw, izomorfizm subgrafu. Wymień niektóre naturalne problemy z optymalizacją, które na …
6
Dobre przykłady, jak dobrze pisać w TCS
Redagowałem manuskrypt studencki. Uczeń zauważył, że miło byłoby zobaczyć przykłady dobrej jakości pisania w opublikowanych pracach i zdałem sobie sprawę, że tak naprawdę nie mogę wymyślić dobrych przykładów z głowy Jakie są najlepsze przykłady wysokiej jakości pisania matematycznego, jakie widziałeś? Zasady: Wolę papiery TCS, o ile to możliwe. Nasz styl …
4
Jakie są konsekwencje
Wiemy, że L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} i że L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , gdzie L2=DSPACE(log2n)L2=DSPACE(log2⁡n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Wiadomo również, że polyL≠PpolyL≠P\mathsf{polyL} \neq \mathsf{P}ponieważ ten drugi ma całkowite problemy w przestrzeni logarytmicznej, wielokrotne redukcje jeden-jedynki, podczas gdy ten drugi nie (ze względu na twierdzenie o …
5
Jakiej najbardziej intuicyjnej teorii typów zależnych mógłbym się nauczyć?
Jestem zainteresowany uzyskaniem naprawdę solidnego zrozumienia zależnego pisania. Przeczytałem większość TaPL i przeczytałem (jeśli nie w pełni zaabsorbowane) „Typy zależne” w ATTaPL . Przeczytałem również i przejrzałem kilka artykułów na temat pisania zależnego. Wiele dyskusji na temat teorii typów wydaje się koncentrować na dodawaniu funkcji przyrostowych do poprzednich systemów typów, …
5
Czy w teorii złożoności istnieją prawa ochrony?
Zacznę od kilku przykładów. Dlaczego tak trywialne jest pokazanie, że CVP jest w P, ale tak trudno jest pokazać LP w P; podczas gdy oba są problemami typu P-zupełnego. Lub weźmy pierwszeństwo. Łatwiej jest wyświetlać kompozyty w NP niż liczby pierwsze w NP (co wymagało Pratta) i ostatecznie w P. …
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.