Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

2
Czy Logical Min-Cut NP-Complete?
To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 7 lat temu . Definicja problemu Logical Min Cut (LMC) Załóżmy, że jest nieważonym wykresem, i są dwoma wierzchołkami , a jest osiągalne z . LMC Problem badania jak możemy nieosiągalny ze …
1
Rozróżnij procedurę decyzyjną w porównaniu do solvera SMT vs provera twierdzeń vs solvera z ograniczeniami
Te terminologie mylą mnie. Jak rozumiem Solver SAT: decyduje o spełnianiu logiki zdań (za pomocą DPLL lub wyszukiwania lokalnego). Procedura decyzyjna to procedura decydująca o spełnieniu pewnej rozstrzygalnej teorii pierwszego rzędu. Solver SMT to solver SAT + procedura decyzyjna. Przysłowie twierdzące wskazuje na coś takiego jak logika dynamiczna, np. Narzędzie …
4
Czy w logice konstruktywistycznej istnieją niezdecydowane języki?
Logika konstruktywistyczna to system, który usuwa Prawo Akceptowanego Środka, a także Podwójną Negację, jako aksjomaty. Jest opisany na Wikipedii tutaj i tutaj . W szczególności system nie dopuszcza dowodu sprzeczności. Zastanawiam się, czy ktoś wie, jak to wpływa na wyniki dotyczące maszyn Turinga i języków formalnych? Zauważam, że prawie każdy …
2
Problemy z optymalizacją „NP-complete”
To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 7 lat temu . Jestem nieco zdezorientowany pewną terminologią, którą napotkałem, dotyczącą złożoności problemów związanych z optymalizacją. W klasie algorytmów miałem duży problem z oszczędnością opisany jako NP-zupełny. Nie jestem jednak do …
2
Jeśli mogę rozwiązać Sudoku, czy mogę rozwiązać problem Traveling Salesman (TSP)? Jeśli tak to jak?
Powiedzmy, że istnieje program taki, że jeśli podasz częściowo wypełnione Sudoku o dowolnym rozmiarze, otrzymasz odpowiednie wypełnione Sudoku. Czy możesz potraktować ten program jako czarną skrzynkę i użyć go do rozwiązania TSP? Mam na myśli, czy istnieje sposób na przedstawienie problemu TSP jako częściowo wypełnionego Sudoku, więc jeśli dam ci …
2
Czy jakieś języki programowania wykorzystują ogólne funkcje rekurencyjne jako podstawę?
To naiwne i dlatego prawdopodobnie źle sformułowane pytanie, więc z góry przepraszamy! Moim zdaniem maszynę Turinga można postrzegać jako podstawę obliczeniową dla proceduralnych / imperatywnych języków programowania. Podobnie, rachunek lambda jest podstawą funkcjonalnych języków programowania. Niedawno dowiedziałem się, że teza Churcha-Turinga wykazuje również wzajemną równoważność z trzecim modelem obliczeń: ogólnymi …
1
Czy można udowodnić nierozstrzygalność problemu zatrzymania w Coq?
Oglądałem „ Pięć etapów akceptacji konstruktywnej matematyki ” Andreja Bauera i mówi on, że istnieją dwa rodzaje dowodów sprzeczności (lub dwie rzeczy, które matematycy nazywają dowodem sprzeczności): Załóżmy, że jest fałszywe ... bla bla bla, sprzeczność. Dlatego jest prawdziwe.P.P.PP.P.P Załóżmy, że jest prawdą ... bla bla bla, sprzeczność. Dlatego P …
8
Język programowania, w którym każde wyrażenie ma sens
Zgodnie z zaleceniem przesyłam ponownie z Przepełnienia stosu . Ostatnio zastanawiałem się nad następującym problemem. Rozważ kod standardowego „Hello world!” program: main() { printf("Hello World"); } Teraz prawie każda zmiana w tym kodzie sprawi, że będzie on całkowicie bezużyteczny, w rzeczywistości prawie każda zmiana uniemożliwi kompilację kodu. Na przykład: main(5 …
4
Dlaczego funkcje obliczalne nazywane są również funkcjami rekurencyjnymi?
W teorii obliczalności funkcje obliczeniowe nazywane są również funkcjami rekurencyjnymi. Przynajmniej na pierwszy rzut oka nie mają one nic wspólnego z tym, co nazywasz „rekurencyjnym” w codziennym programowaniu (tj. Funkcjami, które same się nazywają). Jakie jest rzeczywiste znaczenie rekurencji w kontekście obliczalności? Dlaczego te funkcje nazywane są „rekurencyjnymi”? Innymi słowy: …
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.