Jeśli możesz zmienić nazwę programowania dynamicznego…
Gdybyś mógł zmienić nazwę programowania dynamicznego, jak byś to
43
pytania dotyczące definicji, terminów i nazw zwyczajowych w informatyce teoretycznej.
Gdybyś mógł zmienić nazwę programowania dynamicznego, jak byś to
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ęść...
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...
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...
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...
Czy istnieją problemy w CS, w których nie są znane wydajne algorytmy, pomimo twierdzeń o istnieniu dowodzących, że takie wydajne algorytmy muszą istnieć? Jak nazywają się te problemy? Gdzie mogę dowiedzieć się
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...
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...
Przepraszam, jeśli to naiwne pytanie, ale nie mogłem znaleźć uzasadnienia w żadnej z głównych książek, takich jak Bondy-Murty, Diestel czy West. Idealne wykresy mają wiele pięknych właściwości, ale jaki jest jedyny powód, dla którego nazywane są idealnymi? A może to tylko preferencja estetyczna...
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...
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...
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 -> b seq ⊥ b =...
Mówimy, że funkcja jest konstruowalna w czasie , jeśli istnieje deterministyczna wielopasmowa maszyna Turinga M, która na wszystkich wejściach długości n wykonuje co najwyżej f ( n ) kroki i dla każdego n istnieje pewien wkład długość n, na której M wykonuje dokładnie f ( n ) kroki.fa: N →...
To pytanie może nie mieć charakteru technicznego. Jako nie-native speaker i TA dla klasy algorytmów zawsze zastanawiałem się, co oznacza gadżet w „gadżet klauzulowy” lub „gadżet zmienny”. Słownik mówi, że gadżet jest maszyną lub urządzeniem, ale nie jestem pewien, co to kolokwialne znaczenie ma w...
Jedyną znaną mi definicją „rachunku różniczkowego” jest badanie granic, pochodnych, całek itp. W analizie. W jakim sensie rachunek lambda (lub rzeczy takie jak rachunek mu) jest „rachunkiem”? Jak to się ma do rachunku różniczkowego w
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...
Zastanawiam się, czy następujący problem ma nazwę lub wyniki z nim związane. Niech będzie wykresem ważonym, gdzie oznacza wagę krawędzi między i , a dla wszystkich , . Problem polega na znalezieniu podzbioru wierzchołków, który maksymalizuje sumę wag sąsiadujących z nimi krawędzi: Zauważ, że...
Wszyscy wiemy, że minimalną złożonością algorytmu sortowania opartego na porównaniu są porównania . Próbuję wykonać sortowanie w ciemno , tzn. Biorąc pod uwagę liczbę wyjdź z obwodu (z bramkami logicznymi, arytmetycznymi i „porównawczymi”), który sortuje listę elementów.Ω ( n logn...
Kolorowy wykres można opisać jako krotkę (G,c)(G,c)(G,c)gdzie jest wykresem, a jest kolorem. Mówi się, że dwa kolorowe wykresy i są izomorficzne, jeśli istnieje izomorfizm prawy tak, że przestrzegane jest zabarwienie, tj. dla wszystkich .GGGc:V(G)→Nc:V(G)→Nc : V(G) \rightarrow...