Co to znaczy powiedzieć, że algorytm to Dźwięk i kompletność?

Słyszałem różne interpretacje dźwięku i kompletności . Rozumiem, że kompletność oznacza znalezienie rozwiązania, jeśli takie istnieje. Co to znaczy powiedzieć, że algorytm to dźwięk .

Co to znaczy powiedzieć, że algorytm to Dźwięk i kompletność?

Są to bardzo specyficzne terminy związane z logiką.

Oto kilka punktów wyjścia:

http://en.wikipedia.org/wiki/Soundness

http://en.wikipedia.org/wiki/Completeness_(logic)

Zasadniczo solidność (algorytmu) oznacza, że ​​algorytm nie daje żadnych nieprawdziwych wyników. Jeśli na przykład mam algorytm sortowania, który czasami nie zwraca posortowanej listy, algorytm nie jest prawidłowy.

Z drugiej strony kompletność oznacza, że ​​algorytm odnosi się do wszystkich możliwych danych wejściowych i niczego nie przeoczy. Tak więc, jeśli mój algorytm sortowania nigdy nie zwrócił nieposortowanej listy, ale po prostu odmówił pracy na listach zawierających liczbę 7, to nie byłaby kompletna.

Jest kompletny i solidny, jeśli działa na wszystkich wejściach (semantycznie poprawnych w świecie programu) i zawsze otrzymuje właściwą odpowiedź.

Uważam, że odpowiedź Erika Dietricha jest nieco myląca. Lepiej jest:

Algorytm działa prawidłowo, jeśli w dowolnym momencie zwraca odpowiedź, odpowiedź jest prawdziwa. Algorytm jest kompletny, jeśli gwarantuje zwrócenie poprawnej odpowiedzi na dowolne dane wejściowe (lub, jeśli nie ma odpowiedzi, gwarantuje zwrócenie błędu).

Dwa ważne punkty:

1. Solidność jest słabą gwarancją. Nie obiecuje, że A zakończy się.
2. Solidność i kompletność to powiązane pojęcia; w rzeczywistości są one logiczną rozmową między sobą. tj. Soundness mówi, że jeśli odpowiedź zostanie zwrócona, odpowiedź jest prawdziwa. Kompletność mówi, że odpowiedź jest prawdziwa, jeśli zostanie zwrócona.

Rozważmy na przykład algorytm sortowania A, który otrzymuje jako dane wejściowe listę liczb. Mówimy, że A jest dźwiękiem, jeśli za każdym razem zwraca wynik, którego wynikiem jest posortowana lista. Podobnie, mówimy, że A jest kompletne, jeśli gwarantujemy, że zwróci posortowaną listę za każdym razem, gdy damy jej listę liczb.

Terminy te pochodzą z teorii obliczeń, więc mają większe znaczenie w kontekście teorii obliczeń niż w kontekście inżynierii oprogramowania

W większości standardowych modeli obliczeniowych problemy obliczeniowe są reprezentowane jako języki . Język to zestaw ciągów znaków. Algorytm jest więc systemem lub procedurą, która decyduje, czy dany łańcuch należy do jakiegoś języka (zwracając wartość prawda czy fałsz). W terminologii inżynierii oprogramowania teoria obliczeń dotyczy w szczególności funkcji, które wyglądają tak, zakładając, że ciągi są niezmienne:

boolean some_function(string argument){...}

Tę funkcję nazywamy pełną, jeśli zwraca wartość true dla każdego argumentu należącego do języka. Nazywamy to dźwiękiem, jeśli zwraca wartość false dla każdego argumentu, który nie jest członkiem danego języka.

Innymi słowy, jest kompletny, jeśli zawsze zwraca true, gdy chcemy, aby zwrócił true, i brzmi, jeśli zawsze zwraca false, gdy chcemy, aby zwrócił false.

Jak to się przekłada na inne rodzaje funkcji? Jak się okazuje, prawie zawsze można upchnąć dowolną ilość danych w łańcuch i odtworzyć je w funkcji. Tak więc ograniczenie rodzaju argumentów i arity jest niczym więcej niż teoretycznym uproszczeniem. Ważniejsze jest jednak ograniczenie typu zwrotu. Problemy wymagające wyniku logicznego nazywane są problemami decyzyjnymi . Wiele teorii obliczeniowych wiąże się z problemami decyzyjnymi; zestawy P i NP są ograniczone do problemów decyzyjnych (a NP, przynajmniej nie można byłoby rozsądnie zdefiniować bez tego ograniczenia). Problem zatrzymania jest kolejnym przykładem mocno zbadanego problemu decyzyjnego.

Moim zdaniem te terminy nie uogólniają się poza domeną problemów decyzyjnych, więc różnica między nimi nie jest tak naprawdę znacząca przy omawianiu ogólnej funkcji.

Istnieją znacznie lepsze odpowiedzi na SO . Zasadniczo podajesz pewne dane i kryteria wyszukiwania. Algorytm dźwięku łapie tylko rybę, która spełnia kryteria, ale może brakować niektórych elementów danych. Kompletny algorytm tworzy zbiór żądanych wyników, co oznacza, że ​​oprócz żądanych wyników otrzymujesz śmieci. Algorytm dźwięku jest bardziej konserwatywny.

Statystyk prawdopodobnie powiedziałby, że algorytm dźwięku jest tendencyjny do błędów typu I (nie przyjmuje poprawnych kandydatów), podczas gdy kompletny algorytm jest tendencyjny do błędów typu II (do przyjęcia fałszywych kandydatów).