Pytania otagowane jako reference-request

Pytania wymagające literatury na temat konkretnych, wąskich zagadnień.

2
Żądanie referencyjne: Teoria kategorii w odniesieniu do układów typów
Ciągle słyszę o tym, jak należy nauczyć się teorii kategorii, aby naprawdę zrozumieć teorię języka programowania. Do tej pory nauczyłem się sporo PL bez wchodzenia w sferę kategorii. Uznałem jednak, że nadszedł czas, aby zrobić krok, aby zobaczyć, co straciłem. Niestety, żadne ze źródeł, które mogę znaleźć, nie wydają się …
4
Czy problem izomorfizmu grafu został rozwiązany?
Wydaje się, że strona problemu z izomorfizmem grafu w Wikipedii wskazuje, że nie, nie została rozwiązana. Jednak mój przyjaciel zwrócił uwagę na algorytm wielomianu czasowego dla izomorfizmu grafowego . Nie jestem wystarczająco wyrafinowany, aby podążać za rozumowaniem zawartym w artykule. Mam własną bardzo trudną próbę zastosowania algorytmu wielomianowego bez żadnego …
4
Twierdzenia mostkowe dla teorii grup i języków formalnych
Czy istnieje jakiś naturalny lub znaczący sposób na powiązanie lub połączenie grup matematycznych i języków formalnych CS lub jakieś inne podstawowe pojęcie CS, np. Maszyny Turinga? Szukam referencji / aplikacji. Zauważ jednak, że jestem świadomy związku między półgrupami a językami CS (mianowicie za pośrednictwem automatów skończonych ). (Czy ta literatura …
1
Jaki jest pożytek ze znalezienia minimalnej liczby linii prostych w celu pokrycia zestawu punktów?
Istnieje popularny problem [1] [2] w informatyce, który polega na znalezieniu minimalnej liczby linii prostych pokrywających dany zestaw punktów w 2D. Mimo że zeskanowałem wiele artykułów, żaden z nich nie ma wyraźnej motywacji do rozwiązania problemu. Jaki jest pożytek z rozwiązania tego problemu? Czy istnieje dokument, który to wyjaśnia?
3
Multicore SAT Solver
Próbuję rozwiązać problem SAT z 25k klauzul 5k zmiennych. Ponieważ działa od godziny (precosat), a potem chciałbym rozwiązać większe, szukam wielordzeniowego SAT-Solvera. Ponieważ wydaje się, że jest wiele rozwiązań SAT, jestem całkiem zagubiony. Czy ktoś mógłby wskazać mi najlepszy dla mojej sprawy? Byłbym również szczęśliwy, gdyby ktoś mógł podać mi …
2
Czy istnieje formalna definicja CS VCS i wersji plików?
Nie wiem, czy to był żart, ale kiedy przeczytałem coś, co nazywano formalną definicją pliku w systemie kontroli wersji, takim jak git, hg lub svn. To było coś w rodzaju przedmiotu matematycznego, takiego jak homeomorfizm. Czy to był żart, czy naprawdę istnieje teoria informatyki na temat systemów wersjonowania i matematyki …
2
Jaka jest złożoność problemu pustki dla dwukierunkowych DFA?
Zastanawiam się, jaka jest złożoność czasowa określania pustki dla dwukierunkowych DFA? Oznacza to, że skończone automaty mogą przesuwać się wstecz na swojej taśmie wejściowej tylko do odczytu. Według Wikipedii są one równoważne DFA, chociaż równoważny DFA może być wykładniczo większy. Znalazłem złożoność stanu dla ich uzupełnień i skrzyżowań, ale nie …
1
Narzędzie do prototypowania semantyki języka programowania
Czy jest jakieś narzędzie do prototypowania semantyki języka programowania i systemu typów, a także umożliwia pewnego rodzaju sprawdzanie modelu standardowych właściwości, takich jak poprawność typu? Pytam o to, ponieważ czytam książkę o stopie i zapewnia on dokładnie taką funkcjonalność, jakiej chcę, ale dla modeli wyrażonych za pomocą logiki relacyjnej. Zdaję …
1
Czy problem trudny dla NP może być średnio wielomianowy?
Zastanawiam się, czy są jakieś problemy twarde typu , które w przeciętnym przypadku są `` wielomianowe ''. Sądzę, że istnieją dwa sposoby interpretacji tego?N.P.N.P.NP Jeśli , czy może istnieć algorytm rozwiązujący problem twardości N P z zamortyzowanym (przypadkiem średnim) czasem pracy O ( n k ) dla stałej k ?P.≠ …
3
Książka wprowadzająca na temat logiki i obliczeń
Czy możesz podać mi sugestie dotyczące dobrej wstępnej (ale wyczerpującej) książki o logice i obliczeniach? Niektóre rozmyte tematy, które mam na myśli to: Presburger artihm., PA, ZF, ZFC, HOL Teoria zbiorów, teoria typów Obliczenia modelowe (maszyny Turinga) w różnych teoriach Linki o złożoności obliczeniowej (FMT, złożoność opisowa)
1
Dlaczego wszystkie problemy w FPTAS występują również w FPT?
Zgodnie z artykułem Wikipedii na temat schematów aproksymacji czasu wielomianowego : Wszystkie problemy w FPTAS są możliwe do rozwiązania ze stałymi parametrami. Ten wynik mnie zaskakuje - te klasy wydają się zupełnie różne od siebie. FPTAS charakteryzuje problemy na podstawie ich łatwości do przybliżenia, podczas gdy FPT charakteryzuje problemy na …
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.