Pytania otagowane jako formal-methods

szczególny rodzaj techniki opartej na matematyce do specyfikacji, rozwoju i weryfikacji systemów oprogramowania i sprzętu.

2
Co to jest koindukcja?
Słyszałem o indukcji (strukturalnej). Pozwala budować struktury skończone z mniejszych i zapewnia zasady dowodowe dla uzasadnienia takich struktur. Pomysł jest wystarczająco jasny. A co z koindukcją? Jak to działa? Jak można powiedzieć coś rozstrzygającego o nieskończonej strukturze? Są (przynajmniej) dwa kąty, którymi należy się zająć, a mianowicie koindukcja jako sposób …
6
Algorytm rozwiązywania „problemu zatrzymania” Turinga
To pytanie zostało przeniesione z Teoretycznej informatyki stosu wymiany, ponieważ można na nie odpowiedzieć w sprawie informatyki stosu wymiany. Migrował 7 lat temu . „Alan Turing udowodnił w 1936 r., Że nie może istnieć ogólny algorytm rozwiązania problemu zatrzymania dla wszystkich możliwych par danych wejściowych programu” Czy mogę znaleźć ogólny …
3
Ścieżka do metod formalnych
Często zdarza się, że studenci rozpoczynają doktoraty z ograniczonym doświadczeniem w matematyce i formalnych aspektach informatyki. Oczywiście takim studentom bardzo trudno będzie zostać teoretycznym informatykiem, ale dobrze by było, gdyby mogli się zorientować w stosowaniu metod formalnych i czytaniu artykułów zawierających metody formalne. Jaka jest dobra, krótkoterminowa ścieżka, którą mogą …
2
Czym jest ta ułamkowa notacja „dyskretna matematyka” stosowana w formalnych regułach?
W artykule „Bezkonfliktowy zreplikowany typ danych JSON” napotkałem ten zapis do formalnego definiowania „reguł”: Jak nazywa się ten zapis? Jak to czytać? Na przykład: DOCreguła nie ma nic w „liczniku” - dlaczego nie? te EXECi GETzasady wydają się mieć dwa oddzielne terminy powyżej linii, co to znaczy? VARreguła wyróżnia się …
5
Czy można rozwiązać problem zatrzymania, jeśli masz ograniczony lub przewidywalny wkład?
Problemu zatrzymania nie można rozwiązać w ogólnym przypadku. Można wymyślić zdefiniowane reguły, które ograniczają dozwolone dane wejściowe i czy problem zatrzymania można rozwiązać w tym szczególnym przypadku? Na przykład wydaje się prawdopodobne, że język, który nie dopuszcza na przykład pętli, bardzo łatwo będzie stwierdzić, czy program się zatrzyma, czy nie. …
4
Jak sprawdzić, czy dwa algorytmy zwracają ten sam wynik dla dowolnego wejścia?
Jak sprawdzisz, czy dwa algorytmy (powiedzmy: Sortuj i Naiwne) zwracają ten sam wynik dla dowolnego wejścia, gdy zestaw wszystkich danych wejściowych jest nieskończony? Aktualizacja: Dziękuję Ben za opisanie, w jaki sposób niemożliwe jest algorytmiczne wykonanie tego przypadku w ogólnym przypadku. Odpowiedź Dave'a jest doskonałym podsumowaniem metod algorytmicznych i ręcznych (w …
2
Poprawność programu, specyfikacja
Z Wikipedii: W informatyce teoretycznej poprawność algorytmu jest stwierdzana, gdy mówi się, że algorytm jest poprawny w odniesieniu do specyfikacji. Problem polega jednak na tym, że uzyskanie „właściwej” specyfikacji nie jest trywialnym zadaniem i nie ma 100% poprawnej metody (o ile wiem), aby uzyskać właściwą, to tylko oszacowanie, więc jeśli …
3
Dlaczego stan pozostaje niezmieniony w niewielkiej semantyce operacyjnej pętli while?
Zwykle widzę, że w strukturalnej reprezentacji operacyjnej semantyki dla pętli while stan programu nie zmienia się: (whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S) \> else \> SKIP, \sigma) Dla mnie nie jest to intuicyjne, jeśli stan się nie …
2
Wprowadzenie do weryfikacji logicznej pierwszego rzędu
Próbuję nauczyć się różnych podejść do weryfikacji oprogramowania. Przeczytałem kilka artykułów. O ile się dowiedziałem, logika zdaniowa z temporalnym na ogół wykorzystuje sprawdzanie modelu za pomocą solverów SAT (w systemach trwających - reaktywnych), ale co z logiką pierwszego rzędu z temporalną? Czy wykorzystuje dowody twierdzeń? Czy może również używać SAT? …
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.