Pytania otagowane jako terminology

pytania dotyczące definicji, terminów i nazw zwyczajowych w informatyce teoretycznej.

6
Wyrażenia regularne nie są
Zapytaj nawet kogoś, kto ma doświadczenie w informatyce, co to jest wyrażenie regularne, a odpowiedź prawdopodobnie wykroczy poza ograniczenie bycia w zasięgu automatu skończonego. Na przykład „wyrażenie regularne” /^1?$|^(11+?)\1+$/ stworzona przez znaną osobowość Perla Abigail (i część zestawu testów Perla od 2002 r.) opisuje maszynę, która akceptuje tylko złożone liczby …
1
Problem satysfakcji z ograniczeń (CSP) vs. teoria modulo satysfakcji (SMT); z kodą na temat programowania ograniczeń
Czy ktoś odważy się wyjaśnić, jaki jest związek tych kierunków studiów, czy może nawet bardziej konkretną odpowiedź na poziomie problemów? Który obejmuje, który obejmuje niektóre powszechnie akceptowane formulacje. Jeśli dobrze to zrozumiałem, przechodząc z SAT do SMT, po prostu wchodzisz w pole CSP; i na odwrót, jeśli ograniczysz CSP do …
2
Geneza i zastosowania teorii A vs. teorii B?
W kilku ostatnich pytaniach ( q1 q2 ) omawiano „Teorię A” vs. „Teorię B”, najwyraźniej w celu uchwycenia podziału między nauką logiki i języków programowania a badaniem algorytmów i złożoności. Ta terminologia była dla mnie nowa, a szybkie wyszukiwanie w Internecie nie przyniosło żadnych oczywistych referencji. Czy ktoś wie o …
3
Jaka jest różnica między przepisywaniem terminów a dopasowywaniem wzorców?
Ponieważ w Lambda Ultimate nie było odpowiedzi , próbuję tutaj jeszcze raz: systemy przepisywania terminów są używane na przykład w automatycznym twierdzeniu potwierdzającym obliczenia symboliczne i oczywiście do zdefiniowania gramatyki formalnej. Istnieje kilka języków programowania opartych na przepisywaniu terminów, ale o ile rozumiem, pojęcie to jest bardziej znane jako dopasowanie …
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 …
2
Czy rozstrzyganie propozycji jest kompletnym systemem dowodowym?
To pytanie dotyczy logiki zdań i wszystkie wystąpienia „rozstrzygania” należy interpretować jako „rozstrzyganie zdań”. To pytanie jest bardzo proste, ale od dłuższego czasu mnie niepokoi. Widzę, że ludzie twierdzą, że rozwiązanie zdań jest kompletne, ale widzę też, że ludzie twierdzą, że rozwiązanie jest niepełne. Rozumiem sens niepełnej rozdzielczości. Rozumiem również, …
4
Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b …
1
Jak problem może występować w NP, być trudnym NP, a nie kompletnym NP?
Najdłużej myślałem, że problem był NP-zupełny, jeśli jest zarówno (1) NP-trudny, jak i (2) jest w NP. Jednak w słynnym artykule „Metoda elipsoidy i jej konsekwencje w optymalizacji kombinatorycznej” autorzy twierdzą, że problem ułamkowej liczby chromatycznej należy do NP i jest trudny do NP, ale nie jest znany jako NP-zupełny. …
1
Co to jest „pseudo-czas” w porównaniu z semaforami
Obecnie słucham przemówienia Alana Kaysa „Czy to naprawdę skomplikowane, czy tylko skomplikowaliśmy?” ( Https://www.youtube.com/watch?v=ubaX1Smg6pY&= ), w którym mówi, że „semafory były złym pomysłem i nie było coś, co nazywa czas pseudo że była lepsza” (at 51:40 na połączonego materiału wideo). Może źle zrozumiałem słowo „pseudo-czas”, ale czy wiesz coś o …
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.