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ść?
algorithms
terminology
mutelogan
źródło
źródło
Odpowiedzi:
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ź.
źródło
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:
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.
źródło
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:
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.
źródło
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).
źródło