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

33

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ść?

mutelogan
źródło
Sugeruję, abyś ponownie ocenił, jaką odpowiedź zaakceptowałeś, biorąc pod uwagę, że jedna jest błędna.
BlackJack,
Właśnie to zrobiłem :)
mutelogan

Odpowiedzi:

50

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ź.

Erik Dietrich
źródło
Dzięki. Byłem naprawdę zdezorientowany, co oznacza solidność . Otrzymałem wiele odpowiedzi.
mutelogan
Szczęśliwy, jeśli to pomogło ... :)
Erik Dietrich
13
Przykładem może być wyszukiwanie binarne, to jest dźwięk, ale nie jest kompletne. Nie działa na listach nieposortowanych.
Malfist
3
@Malfist, ale czy listy posortowane według „świata programu” nie są posortowane?
Andres
1
„Nieprawidłowy algorytm zachowuje się przy nieprawidłowych danych wejściowych” nie wpływa na poprawność ani kompletność, więc wyszukiwanie binarne ani porównywanie nie są istotne - oba algorytmy są prawidłowe i kompletne dla prawidłowych danych wejściowych.
Blaisorblade,
15

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.

Daniel
źródło
Dlaczego jesteś zdezorientowany? „Algorytm działa prawidłowo, jeśli w dowolnym momencie zwraca odpowiedź, odpowiedź jest prawdziwa”. oznacza to samo co „Zasadniczo, poprawność (algorytmu) oznacza, że ​​algorytm nie daje żadnych nieprawdziwych wyników”. To znaczy to samo. Jeśli chodzi o twoją (bardzo krótką) definicję Kompletności, nie pasuje ona do nic w linku wikipedia i nie powołujesz się na żadne własne odniesienie. Muszę powiedzieć, że definicje Erika są bardziej praktyczne. Jeśli twoje są poprawne, musisz przedstawić lepsze dowody i więcej mięsa.
itsbruce
1
Aby wyjaśnić, kiedy mówisz „Kompletność mówi, że odpowiedź jest prawdziwa, jeśli zostanie zwrócona”, masz na myśli, że odpowiedź jest „poprawna”, prawda?
Dois
1
„Odpowiedź jest prawdą, jeśli zostanie zwrócona” oznacza dosłownie to samo, co „jeśli odpowiedź zostanie zwrócona, to prawda”. Ponadto odpowiedzi nie mogą być „prawdziwe”, a jedynie poprawne. softwareengineering.stackexchange.com/a/311649/21277 jest bardziej poprawny.
Blaisorblade,
2

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.

Kevin
źródło
-2

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).

wprowadź opis zdjęcia tutaj

Valentin Tihomirov
źródło