Jak oszukać heurystykę „wypróbuj niektóre przypadki testowe”: Algorytmy, które wydają się prawidłowe, ale w rzeczywistości są nieprawidłowe

105

Aby spróbować sprawdzić, czy algorytm dla jakiegoś problemu jest prawidłowy, zwykle punktem wyjścia jest próba uruchomienia algorytmu ręcznie na kilku prostych przypadkach testowych - wypróbuj go na kilku przykładowych przypadkach problemów, w tym na kilku prostych „przypadkach narożnych” „. To świetna heurystyka: to świetny sposób na szybkie wyeliminowanie wielu niepoprawnych prób algorytmu i uzyskanie zrozumienia, dlaczego algorytm nie działa.

Jednak podczas uczenia się algorytmów niektórzy uczniowie mają pokusę, aby na tym poprzestać: jeśli ich algorytm działa poprawnie na kilku przykładach, w tym we wszystkich przypadkach, w których mogą spróbować, to dochodzą do wniosku, że algorytm musi być poprawny. Zawsze jest uczeń, który pyta: „Dlaczego muszę udowodnić, że mój algorytm jest poprawny, jeśli mogę po prostu wypróbować go na kilku testowych przypadkach?”

Jak więc oszukać heurystykę „wypróbuj kilka przypadków testowych”? Szukam kilku dobrych przykładów, które pokazują, że ta heurystyka nie wystarczy. Innymi słowy, szukam jednego lub więcej przykładów algorytmu, który na pozór wygląda na poprawny, i który daje prawidłową odpowiedź na wszystkie małe dane wejściowe, które ktoś może wymyślić, ale gdzie algorytm faktycznie nie działa Być może algorytm po prostu działa poprawnie na wszystkich małych wejściach i zawodzi tylko w przypadku dużych danych wejściowych lub tylko w przypadku danych wejściowych o nietypowym wzorze.

W szczególności szukam:

  1. Algorytm. Wada musi być na poziomie algorytmu. Nie szukam błędów implementacyjnych. (Na przykład, jako minimum, przykład powinien być niezależny od języka, a wada powinna dotyczyć problemów algorytmicznych, a nie inżynierii oprogramowania lub problemów z implementacją).

  2. Algorytm, który ktoś może wymyślić. Pseudokod powinien wyglądać co najmniej poprawnie (np. Zaciemniony lub oczywiście wątpliwy kod nie jest dobrym przykładem). Punkty bonusowe, jeśli jest to algorytm, który wymyślił uczeń podczas próby rozwiązania zadania domowego lub egzaminu.

  3. Algorytm, który z dużym prawdopodobieństwem przejdzie rozsądną strategię testów manualnych. Ktoś, kto wypróbuje kilka małych przypadków testowych ręcznie, raczej nie powinien odkryć wady. Na przykład „symulowanie QuickCheck ręcznie na tuzinie małych przypadków testowych” raczej nie powinno ujawnić, że algorytm jest nieprawidłowy.

  4. Najlepiej algorytm deterministyczny. Widziałem wielu uczniów, którzy uważają, że „wypróbowanie niektórych przypadków testowych ręcznie” jest rozsądnym sposobem sprawdzenia, czy algorytm deterministyczny jest prawidłowy, ale podejrzewam, że większość studentów nie założyłaby, że próba kilku przypadków testowych jest dobrym sposobem na sprawdzenie prawdopodobieństwa algorytmy. W przypadku algorytmów probabilistycznych często nie można stwierdzić, czy dane dane wyjściowe są poprawne; i nie można ręcznie przekręcić wystarczająco dużo przykładów, aby wykonać użyteczny test statystyczny rozkładu wyjściowego. Wolałbym więc skupić się na algorytmach deterministycznych, ponieważ łatwiej dostrzegają sedno nieporozumień uczniów.

Chciałbym nauczyć znaczenie sprawdzania poprawności algorytmu i mam nadzieję, że wykorzystam kilka takich przykładów, aby zmotywować dowody poprawności. Wolałbym przykłady, które są stosunkowo proste i dostępne dla studentów; przykłady wymagające ciężkiego sprzętu lub tony matematyki / algorytmu są mniej przydatne. Nie chcę też algorytmów, które są „nienaturalne”; chociaż może być łatwo skonstruować jakiś dziwny sztuczny algorytm oszukiwania heurystyki, jeśli wygląda on bardzo nienaturalnie lub ma oczywiste backdoora zbudowane tylko w celu oszukiwania tej heurystyki, prawdopodobnie nie będzie to przekonujące dla studentów. Jakieś dobre przykłady?

DW
źródło
2
Uwielbiam twoje pytanie, jest ono również związane z bardzo interesującym pytaniem, które widziałem kiedyś w matematyce, odnoszącym się do obalenia przypuszczeń o dużych stałych. Można go znaleźć tutaj
ZeroUltimax
1
Jeszcze trochę kopania i znalazłem te dwa algorytmy geometryczne.
ZeroUltimax
@ZeroUltimax Masz rację, nie można zagwarantować, że punkt środkowy 3 dowolnych nietkniętych linii jest w środku. Szybkim rozwiązaniem jest zdobycie pt na linii między najdalszą lewą a najdalszą prawą stroną. Czy jest jeszcze problem gdzie?
Poinformowano
Przesłanka tego pytania wydaje mi się dziwna z tego powodu, że mam trudności z poruszeniem głowy, ale myślę, że sprowadza się to do procesu projektowania algorytmu, jak opisano, jest zasadniczo zepsuty. Nawet dla studentów, którzy nie „kończą się”, jest to skazane na niepowodzenie. 1> algorytm zapisu, 2> pomyśl / uruchom przypadki testowe, 3a> stop lub 3b> sprawdź poprawność. Pierwszym krokiem dość dużo ma być zidentyfikowanie klas wejściowe dla domeny problemu. Z nich wynikają przypadki narożne i sam algorytm. (ciąg dalszy)
Mr.Mindor
1
Jak formalnie odróżnić błąd implementacji od wadliwego algorytmu? Zainteresowało mnie twoje pytanie, ale jednocześnie niepokoiło mnie to, że opisywana sytuacja wydaje się być raczej regułą niż wyjątkiem. Wiele osób testuje to, co implementuje, ale zwykle nadal mają błędy. Drugi przykład najbardziej uprzywilejowanej odpowiedzi to właśnie taki błąd.
babou

Odpowiedzi:

70

Myślę, że częstym błędem jest stosowanie chciwych algorytmów, co nie zawsze jest poprawnym podejściem, ale może działać w większości przypadków testowych.

Przykład: nominały monet, i liczba , jako sumę : s przy jak najmniejszej monet. n n d id1,,dknndi

Naiwne podejście polega na tym, aby najpierw użyć jak największej monety i zachłannie wyprodukować taką sumę.

Na przykład monety o wartości , i dają prawidłowe odpowiedzi z zachłannością dla wszystkich liczb od do z wyjątkiem liczby .5 1 1 14 10 = 6 + 1 + 1 + 1 + 1 = 5 + 565111410=6+1+1+1+1=5+5

Per Alexandersson
źródło
10
To rzeczywiście dobry przykład, w szczególności, że uczniowie rutynowo się mylą. Musisz nie tylko wybrać określone zestawy monet, ale także określone wartości, aby algorytm zawiódł.
Raphael
2
Ponadto pozwól mi powiedzieć, że uczniowie często będą mieli błędne dowody w tym przykładzie (przedstawiając naiwne argumenty, które nie przejdą dokładniejszego badania), więc można wyciągnąć więcej niż jedną lekcję.
Raphael
2
Dawny brytyjski system monet (przed dziesiętną wersją z 1971 r.) Miał tego prawdziwy przykład. Chciwy algorytm odliczania czterech szylingów używałby połowy korony (2½ szylingów), monety o jednym szylingu i sześciu pensów (½ szylinga). Ale optymalne rozwiązanie wykorzystuje dwa floreny (2 szylingi każdy).
Mark Dominus
1
Rzeczywiście w wielu przypadkach zachłanne algorytmy wydają się rozsądne, ale nie działają - innym przykładem jest maksymalne dopasowanie dwustronne. Z drugiej strony istnieją również przykłady, w których wydaje się, że chciwy algorytm nie powinien działać, ale działa: maksymalne drzewo rozpinające.
jkff
62

Natychmiast przypomniałem sobie przykład z R. Backhouse'a (mógł być w jednej z jego książek). Najwyraźniej przydzielił mu zadanie programistyczne, w ramach którego uczniowie musieli napisać program Pascal, aby sprawdzić równość dwóch łańcuchów. Jeden z programów oddanych przez studenta był następujący:

issame := (string1.length = string2.length);

if issame then
  for i := 1 to string1.length do
    issame := string1.char[i] = string2.char[i];

write(issame);

Możemy teraz przetestować program przy użyciu następujących danych wejściowych:

„uniwersytet” „uniwersytet” Prawda; dobrze

„kurs” „kurs” Prawda; dobrze

„” „ Prawda; dobrze

kurs „uniwersytecki” Fałsz; dobrze

„wykład” „kurs” Fałsz; dobrze

Wszystko to wydaje się bardzo obiecujące: może program rzeczywiście działa. Ale dokładniejsze testowanie z powiedzeniem „czysty” i „prawdziwy” ujawnia wadliwy wynik. W rzeczywistości program mówi „prawda”, jeśli ciągi mają tę samą długość i ten sam ostatni znak!

Testowanie było jednak dość dokładne: mieliśmy ciągi o różnej długości, ciągi o tej samej długości, ale o różnej zawartości, a nawet równe ciągi. Ponadto uczeń przetestował i wykonał każdy oddział. Naprawdę nie można twierdzić, że testy były tutaj nieostrożne - biorąc pod uwagę, że program jest naprawdę bardzo prosty, może być trudno znaleźć motywację i energię, aby przetestować go wystarczająco dokładnie.


Innym uroczym przykładem jest wyszukiwanie binarne. W TAOCP Knuth mówi, że „chociaż podstawowa idea wyszukiwania binarnego jest stosunkowo prosta, szczegóły mogą być zaskakująco trudne”. Najwyraźniej błąd w implementacji Java w wyszukiwaniu binarnym pozostawał niezauważony przez dekadę. Był to błąd przepełnienia liczb całkowitych, który przejawiał się tylko przy wystarczająco dużym wejściu. Podstępne szczegóły implementacji wyszukiwania binarnego omawia także Bentley w książce Programming Pearls .

Konkluzja: zaskakująco trudno jest mieć pewność, że algorytm wyszukiwania binarnego jest poprawny, po prostu go testując.

Juho
źródło
9
Oczywiście wada jest dość widoczna ze źródła (jeśli wcześniej napisałeś podobną rzecz).
Raphael
3
Nawet jeśli prosta wada w przykładowym programie zostanie poprawiona, łańcuchy dają całkiem interesujące problemy! Odwracanie ciągów to klasyk - „podstawowym” sposobem na to jest po prostu odwrócenie bajtów. Następnie zaczyna się kodowanie. Następnie zastępuje (zwykle dwa razy). Problem polega oczywiście na tym, że nie ma łatwego sposobu formalnego udowodnienia, że ​​metoda jest poprawna.
Ordous
6
Być może błędnie interpretuję to pytanie, ale wydaje się, że jest to wada w implementacji, a nie wada w samym algorytmie .
Mr.Mindor,
8
@ Mr.Mindor: w jaki sposób można stwierdzić, czy programista zapisał poprawny algorytm, a następnie nieprawidłowo go zaimplementował, czy też zapisał niepoprawny algorytm, a następnie wdrożył go wiernie (waham się powiedzieć „poprawnie”!)
Steve Jessop
1
@wabbit To dyskusyjne. To, co dla ciebie oczywiste, może nie być oczywiste dla studenta pierwszego roku.
Juho
30

Najlepszym przykładem, z jakim się zetknąłem, jest testowanie pierwotności:

wejście: liczba naturalna p, p! = 2
wynik: czy pa jest liczbą pierwszą, czy nie?
algorytm: oblicz 2 ** (p-1) mod p. Jeśli wynik = 1, to p jest liczbą pierwszą, inaczej p nie jest.

Działa to dla (prawie) każdej liczby, z wyjątkiem kilku przykładów liczników, a tak naprawdę potrzebna jest maszyna do znalezienia kontrprzykładu w realistycznym okresie czasu. Pierwszy kontrprzykład to 341, a gęstość kontrprzykładów faktycznie maleje wraz ze wzrostem p, choć prawie logarytmicznie.

Zamiast po prostu użyć 2 jako podstawy potęgi, można ulepszyć algorytm, stosując także dodatkowe, zwiększające się małe liczby pierwsze jako podstawę w przypadku, gdy poprzednia liczba pierwsza zwróci 1. I nadal istnieją kontrprzykłady do tego schematu, mianowicie liczby Carmichaela, dość rzadkie

Franki
źródło
Test pierwotności Fermata jest testem probabilistycznym, więc stan po porodzie jest nieprawidłowy.
Femaref
5
często jest to test probabilistyczny, ale odpowiedź ładnie pokazuje (bardziej ogólnie), w jaki sposób algorytmy probabilistyczne mylone z dokładnymi mogą być źródłem błędu. więcej na temat liczb Carmichaela
2014
2
To dobry przykład, z ograniczeniem: do praktycznego wykorzystania znanych mi testów pierwotności, a mianowicie asymetrycznego generowania klucza kryptograficznego, używamy algorytmów probabilistycznych! Liczby są zbyt duże do dokładnych testów (gdyby nie były, nie byłyby odpowiednie do szyfrowania, ponieważ klucze można było znaleźć brutalną siłą w realistycznym czasie).
Gilles
1
ograniczenie, o którym mówisz, jest praktyczne, a nie teoretyczne, a testy podstawowe w systemach kryptograficznych, np. RSA, podlegają rzadkim / wysoce nieprawdopodobnym awariom z dokładnie tych powodów, ponownie podkreślając znaczenie tego przykładu. tzn. w praktyce czasami to ograniczenie jest akceptowane jako nieuniknione. istnieją algorytmy czasowe P do testowania pierwotności, np. AKS, ale ich użycie w praktyce zajmuje zbyt dużo czasu.
vzn
Jeśli testujesz nie tylko z 2 p, ale z p dla 50 różnych losowych wartości 2 ≤ a <p, wtedy większość ludzi będzie wiedziała, że ​​jest to probabilistyczne, ale z awariami tak mało prawdopodobnymi, że bardziej prawdopodobne jest, że wystąpi awaria komputera Błędna odpowiedź. W przypadku 2 p, 3 p, 5 p i 7 p awarie są już bardzo rzadkie.
gnasher729
21

Oto jeden, który został rzucony na mnie przez przedstawicieli Google na konwencie, na którym pojechałem. Został napisany w C, ale działa w innych językach, które używają referencji. Przepraszamy za konieczność kodowania na [cs.se], ale jest to jedyna ilustracja.

swap(int& X, int& Y){
    X := X ^ Y
    Y := X ^ Y
    X := X ^ Y
}

Ten algorytm będzie działał dla wszystkich wartości podanych x i y, nawet jeśli będą miały tę samą wartość. Nie zadziała jednak, jeśli zostanie wywołany jako swap (x, x). W tej sytuacji x kończy się na 0. Teraz to może cię nie zadowolić, ponieważ możesz w jakiś sposób udowodnić, że operacja jest poprawna matematycznie, ale nadal zapominasz o tym przypadku krawędzi.

ZeroUltimax
źródło
1
Ta sztuczka została wykorzystana w podstępnym konkursie C do stworzenia wadliwej implementacji RC4 . Po ponownym przeczytaniu tego artykułu zauważyłem, że ten hack prawdopodobnie został zgłoszony przez @DW
CodesInChaos
7
Ta wada jest rzeczywiście subtelna - ale wada jest jednak specyficzna dla języka, więc nie jest to tak naprawdę wada algorytmu; jest to błąd we wdrażaniu. Można wymyślić inne przykłady osobliwości językowych, które ułatwiają ukrywanie subtelnych wad, ale tak naprawdę nie tego szukałem (szukałem czegoś na poziomie abstrakcji algorytmów). W każdym razie ta wada nie jest idealnym dowodem na wartość dowodu; chyba że już myślisz o aliasingu, możesz zapomnieć o tym samym problemie, kiedy wypiszesz swój „dowód” poprawności.
DW
Dlatego dziwię się, że tak wysoko zagłosowano.
ZeroUltimax
2
@DW To jest kwestia tego, w jakim modelu zdefiniujesz algorytm. Jeśli przejdziesz do poziomu, w którym odwołania do pamięci są jawne (zamiast wspólnego modelu, który zakłada brak udostępniania), jest to usterka algorytmu. Wada tak naprawdę nie jest specyficzna dla języka, pojawia się w każdym języku, który obsługuje dzielenie się referencjami pamięci.
Gilles
16

Istnieje cała klasa algorytmów z natury trudnych do przetestowania: generatory liczb pseudolosowych . Nie możesz przetestować pojedynczego wyjścia, ale musisz zbadać (wiele) szereg wyników za pomocą statystyk. W zależności od tego, co i jak testujesz, możesz przegapić nieprzypadkowe cechy.

Jednym ze znanych przypadków, w których sprawy potoczyły się bardzo źle, jest RANDU . Przeszedł kontrolę dostępną w tym czasie - która nie uwzględniła zachowania krotek kolejnych wyników. Już trzykrotnie pokazują wiele struktur:

Zasadniczo testy nie obejmowały wszystkich przypadków użycia: podczas gdy jednowymiarowe użycie RANDU było (prawdopodobnie w większości) w porządku, nie wspierało używania go do próbkowania punktów trójwymiarowych (w ten sposób).

Właściwe pobieranie próbek pseudolosowych to trudna sprawa. Na szczęście istnieją potężne zestawy testowe, np. Zagorzali specjalizujący się w wyrzucaniu wszystkich statystyk, które znamy na proponowany generator. Wystarczy?

Szczerze mówiąc, nie mam pojęcia, co możesz w praktyce udowodnić w przypadku PRNG.

Raphael
źródło
2
fajny przykład, ale tak naprawdę ogólnie nie ma sposobu, aby udowodnić, że żaden PRNG nie ma wady, istnieje tylko nieskończona hierarchia testów słabszych i silniejszych. faktycznie udowodnienie, że ktoś jest „przypadkowy” w jakimkolwiek ścisłym sensie, jest prawdopodobnie nierozstrzygalne (choć nie widziałem tego udowodnionego).
vzn
1
To dobry pomysł na coś, co trudno przetestować, ale RNG jest również trudne do udowodnienia. PRNG są nie tyle podatne na błędy implementacyjne, co na złe określenie. Testy takie jak diehard są dobre dla niektórych zastosowań, ale w przypadku kryptografii możesz przejść diehard i nadal wyśmiewać się z pokoju. Nie ma „sprawdzonego bezpiecznego” CSPRNG, najlepsze, co możesz mieć nadzieję, to udowodnić, że jeśli twoje CSPRNG jest zepsute, to również AES.
Gilles
@Gilles Nie próbowałem wchodzić w krypto, tylko statystyczna losowość (myślę, że te dwa mają dość ortogonalne wymagania). Czy powinienem to wyjaśnić w odpowiedzi?
Raphael
1
Losowość kryptograficzna oznacza losowość statystyczną. O ile mi wiadomo, nie ma też matematycznie formalnej definicji oprócz idealnego (i sprzecznego z koncepcją PRNG zaimplementowanego na deterministycznej maszynie Turinga) pojęcia losowości teoretyczno-informacyjnej. Czy statystyczna losowość ma formalną definicję wykraczającą poza „musi być niezależna od rozkładów, na podstawie których będziemy ją testować”?
Gilles
1
@vzn: co to znaczy być losową sekwencją liczb, można zdefiniować na wiele możliwych sposobów, ale prostą jest „duża złożoność Komolgorowa”. W takim przypadku łatwo jest wykazać, że określenie losowości jest nierozstrzygalne.
cody
9

Lokalne maksimum 2D

n×nA

(i,j)A[i,j]

A[i,j+1],A[i,j1],A[i1,j],A[i+1,j]A

0134323125014013

następnie każda pogrubiona komórka jest lokalnym maksimum. Każda niepusta tablica ma co najmniej jedno maksimum lokalne.

O(n2)

AXXA(i,j)X(i,j)(i,j)

AXAX(i,j)A

AA

(i,j)AA(i,j)

n2×n2A(i,j)

T(n)n×nT(n)=T(n/2)+O(n)T(n)=O(n)

W ten sposób udowodniliśmy następujące twierdzenie:

O(n)n×n

A może my?

Neal Young
źródło
T(n)=O(nlogn)T(n)=T(n/2)+O(n)
2
To jest piękny przykład! Kocham to. Dziękuję Ci. (W końcu odkryłem wadę tego algorytmu. Na podstawie znaczników czasu możesz ustalić dolną granicę czasu, jaki zajęło mi. Jestem zbyt zawstydzony, aby ujawnić rzeczywisty czas. :-)
DW
1
O(n)
8

Są to przykłady pierwotności, ponieważ są powszechne.

(1) Pierwszeństwo w SymPy. Wydanie 1789 . Nieprawidłowy test został przeprowadzony na dobrze znanej stronie internetowej, która zakończyła się niepowodzeniem dopiero po 10 ^ 14. Chociaż poprawka była poprawna, to po prostu łatała dziury, a nie przemyślała problem.

(2) Pierwszeństwo w Perlu 6. Perl6 dodał is-prime, który wykorzystuje szereg testów MR ze stałymi zasadami. Znane są kontrprzykłady, ale są one dość duże, ponieważ domyślna liczba testów jest ogromna (w zasadzie ukrywa prawdziwy problem poprzez obniżenie wydajności). Zajmie się tym wkrótce.

(3) Pierwszeństwo we FLINT. n_isprime () zwraca true dla kompozytów , ponieważ naprawiono. Zasadniczo ten sam problem co SymPy. Korzystając z bazy danych Feitsma / Galway dla pseudopierwszych liczb SPRP-2 do 2 ^ 64, możemy je teraz przetestować.

(4) Math Perla :: Pierwszeństwo. is_aks_prime uszkodzony . Ta sekwencja wydaje się podobna do wielu implementacji AKS - dużo kodu, który albo działał przez przypadek (np. Zgubił się w kroku 1 i skończył robić całą rzecz przez podział próbny), albo nie działał dla większych przykładów. Niestety AKS jest tak wolny, że trudno go przetestować.

(5) Pari w wersji wcześniejszej niż 2.2 is_prime. Matematyka :: bilet Pari . Używał 10 losowych zasad do testów MR (z ustalonym początkiem podczas uruchamiania, a nie stałym początkiem GMP przy każdym wywołaniu). Dzięki temu dowiesz się, że 9 to pierwsze około 1 na każde 1M połączeń. Jeśli wybierzesz odpowiedni numer, możesz go stosunkowo często zawieść, ale liczby stają się rzadsze, więc w praktyce nie pokazuje się zbyt wiele. Od tego czasu zmienili algorytm i interfejs API.

To nie jest źle, ale to klasyk testów probabilistycznych: ile rund dajesz, powiedzmy, mpz_probab_prime_p? Jeśli damy mu 5 rund, na pewno wygląda to dobrze - liczby muszą przejść test Fermata base-210, a następnie 5 wstępnie wybranych testów Millera-Rabina. Nie znajdziesz kontrprzykładu do 3892757297131 (z GMP 5.0.1 lub 6.0.0a), więc musisz go dużo przetestować, aby go znaleźć. Ale są tysiące kontrprzykładów poniżej 2 ^ 64. Więc ciągle podnosisz liczbę. Jak daleko? Czy jest przeciwnik? Jak ważna jest poprawna odpowiedź? Czy mylisz losowe bazy ze stałymi bazami? Czy wiesz, jakie rozmiary wejściowe otrzymasz?

1016

Są one dość trudne do prawidłowego przetestowania. Moja strategia obejmuje oczywiste testy jednostkowe oraz przypadki brzegowe, a także przykłady błędów zaobserwowanych przed lub w innych pakietach, w miarę możliwości testuj w porównaniu ze znanymi bazami danych (np. Jeśli wykonujesz pojedynczy test MR bazy 2, to zmniejszyłeś niewykonalność obliczeniowo zadanie przetestowania 2 ^ 64 liczb do przetestowania około 32 milionów liczb) i wreszcie wielu losowych testów z wykorzystaniem innego pakietu jako standardu. Ostatni punkt działa w przypadku funkcji takich jak prymityw, w których dane wejściowe są dość proste i znane, ale jest kilka takich zadań. Wykorzystałem to do znalezienia wad zarówno w moim własnym kodzie programistycznym, jak i sporadycznych problemów w pakietach porównawczych. Ale biorąc pod uwagę nieskończoną przestrzeń wejściową, nie możemy wszystkiego przetestować.

Jeśli chodzi o udowodnienie poprawności, oto kolejny przykład pierwszorzędności. Metody BLS75 i ECPP mają pojęcie certyfikatu pierwszeństwa. Zasadniczo po rezygnacji z wyszukiwania w celu znalezienia wartości, które sprawdzą się w przypadku ich proofów, można je wydrukować w znanym formacie. Następnie można napisać weryfikator lub poprosić kogoś innego o napisanie go. Działają one bardzo szybko w porównaniu do tworzenia, a teraz albo (1) oba fragmenty kodu są niepoprawne (dlatego dlaczego wolisz innych programistów dla weryfikatorów), lub (2) matematyka stojąca za ideą dowodu jest błędna. # 2 jest zawsze możliwe, ale zazwyczaj są one publikowane i recenzowane przez wiele osób (w niektórych przypadkach są wystarczająco łatwe do przejścia przez siebie).

Dla porównania, metody takie jak AKS, APR-CL, podział próbny lub deterministyczny test Rabina nie dają żadnych wyników innych niż „pierwszorzędne” lub „kompozytowe”. W tym drugim przypadku możemy mieć czynnik, który w ten sposób możemy zweryfikować, ale w pierwszym przypadku nie pozostaje nam nic innego, jak tylko ten jeden wynik. Czy program działał poprawnie? Dunno.

Ważne jest, aby przetestować oprogramowanie na więcej niż kilku przykładach zabawek, a także przejrzeć kilka przykładów na każdym etapie algorytmu i powiedzieć „biorąc pod uwagę te dane wejściowe, czy to ma sens, że jestem tutaj z tym stanem?”

DanaJ
źródło
1
Wiele z nich wygląda jak (1) błędy implementacji (podstawowy algorytm jest poprawny, ale nie został poprawnie zaimplementowany), które są interesujące, ale nie o to chodzi w tym pytaniu, lub (2) celowy, świadomy wybór wyboru czegoś, co jest szybki i przeważnie działa, ale może zawieść z bardzo małym prawdopodobieństwem (w przypadku kodu, który testuje jedną losową bazę lub kilka stałych / losowych baz, mam nadzieję, że ktokolwiek to zrobi, będzie wiedział, że dokonuje kompromisu wydajności).
DW
Masz rację w pierwszym punkcie - poprawny algorytm + błąd nie jest najważniejszy, chociaż dyskusja i inne przykłady również je łączą. Pole jest dojrzałe z przypuszczeniami, które działają na małe liczby, ale są niepoprawne. W przypadku punktu (2) jest to prawdą w przypadku niektórych, ale moje przykłady # 1 i # 3 nie były tym przypadkiem - uważano, że algorytm jest poprawny (te 5 zasad daje sprawdzone wyniki dla liczb poniżej 10 ^ 16), a potem odkryłem, że tak nie było.
DanaJ
Czy to nie jest fundamentalny problem z testami pseudo-pierwotności?
asmeurer
asmeurer, tak w moim # 2 i późniejszej dyskusji na ich temat. Jednak zarówno nr 1, jak i 3 dotyczyły zastosowania Millera-Rabina ze znanymi zasadami w celu uzyskania deterministycznie poprawnych wyników poniżej progu. Tak więc w tym przypadku „algorytm” (luźne użycie terminu w celu dopasowania OP) był niepoprawny. # 4 nie jest prawdopodobnym testem podstawowym, ale jak zauważył DW, algorytm działa dobrze, tylko implementacja jest trudna. Zawarłem go, ponieważ prowadzi to do podobnej sytuacji: testowanie jest potrzebne i jak daleko wykraczasz poza proste przykłady, zanim powiesz, że to działa?
DanaJ
Niektóre z twoich postów wydają się pasować do pytania, a inne nie (por. Komentarz DW). Usuń przykłady (i inne treści), które nie odpowiadają na pytanie.
Raphael
7

Algorytm tasowania Fishera-Yatesa-Knutha jest (praktycznym) przykładem, o którym skomentował jeden z autorów tej strony .

Algorytm generuje losową permutację danej tablicy jako:

 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

ij0ji

„Naiwnym” algorytmem może być:

 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ n-1
       exchange a[j] and a[i]

Gdzie w pętli element do zamiany jest wybierany ze wszystkich dostępnych elementów. Jednak powoduje to stronnicze próbkowanie permutacji (niektóre z nich są nadmiernie reprezentowane itp.)

Właściwie można wymyślić tasowanie rybackiego-knutha za pomocą prostej (lub naiwnej) analizy liczenia .

nn!=n×n1×n2..nn1

Główny problem ze sprawdzeniem, czy algorytm tasowania jest poprawny, czy nie ( tendencyjny czy nie ) polega na tym, że ze względu na statystyki potrzebna jest duża liczba próbek. Artykuł o kodowaniu horroru, który zamieszczam powyżej, dokładnie to wyjaśnia (i przy rzeczywistych testach).

Nikos M.
źródło
1
Zobacz tutaj przykładowy dowód poprawności algorytmu losowego.
Raphael
5

Najlepszy przykład (czytaj: rzecz, w której najbardziej bolą mnie tyłki), jaką kiedykolwiek widziałem, dotyczy przypuszczeń collatz. Brałem udział w konkursie programistycznym (z nagrodą w wysokości 500 dolarów na linii za pierwsze miejsce), w którym jednym z problemów było znalezienie minimalnej liczby kroków, jakie trzeba wykonać, aby dwie liczby osiągnęły tę samą liczbę. Rozwiązaniem jest oczywiście naprzemienne stawianie każdego z nich, dopóki nie osiągną czegoś, co było wcześniej widoczne. Otrzymaliśmy zakres liczb (myślę, że było to od 1 do 1000000) i powiedzieliśmy, że hipoteza collatz została zweryfikowana do 2 ^ 64, więc wszystkie podane liczby ostatecznie zbiegną się w 1. Użyłem 32-bitowego liczby całkowite, z którymi należy wykonać kroki. Okazuje się, że istnieje jedna niejasna liczba między 1 a 1000000 (170 tysięcy czegoś), która spowoduje przepełnienie 32-bitowej liczby całkowitej w odpowiednim czasie. W rzeczywistości liczby te są niezwykle rzadkie poniżej 2 ^ 31. Przetestowaliśmy nasz system pod kątem OGROMNYCH liczb znacznie większych niż 1000000, aby „upewnić się”, że nie nastąpiło przepełnienie. Okazuje się, że znacznie mniejsza liczba, której nie przetestowaliśmy, spowodowała przepełnienie. Ponieważ użyłem „int” zamiast „long”, dostałem tylko 300 dolarów nagrody, a nie 500 dolarów.

Jake
źródło
5

Problem Knapsack 0/1 jest taki, że prawie wszyscy uczniowie uważają, że można go rozwiązać za pomocą chciwego algorytmu. Zdarza się to częściej, jeśli wcześniej pokazałeś niektóre chciwe rozwiązania jako problematyczną wersję Knapsacka, w której działa chciwy algorytm .

W przypadku tych problemów w klasie powinienem pokazać dowód na Knapsack 0/1 ( programowanie dynamiczne ), aby usunąć wszelkie wątpliwości, a także na chciwą wersję problemu. W rzeczywistości oba dowody nie są trywialne i uczniowie prawdopodobnie uważają je za bardzo pomocne. Ponadto komentarz na ten temat znajduje się w CLRS 3ed , rozdział 16, strona 425-427 .

Problem: złodziej okradający sklep i może przenosić maksymalną wagę W do swojego plecaka. Jest n przedmiotów i i przedmiot ważą wi i jest wart vi dolarów. Jakie przedmioty powinien wziąć złodziej? zmaksymalizować swój zysk ?

Problem z plecakiem 0/1 : Konfiguracja jest taka sama, ale przedmiotów nie można podzielić na mniejsze części , więc złodziej może zdecydować, czy wziąć przedmiot, czy go zostawić (wybór binarny), ale nie może wziąć części ułamka przedmiotu .

I możesz uzyskać od studentów kilka pomysłów lub algorytmów zgodnych z tym samym pomysłem co chciwy problem z wersją, to jest:

  • Weź całkowitą pojemność torby i umieść jak najwięcej przedmiotu o największej wartości i iteruj tę metodę, dopóki nie będziesz mógł umieścić więcej przedmiotów, ponieważ torba jest pełna lub nie ma przedmiotów o mniejszej lub równej wadze do umieszczenia w torbie.
  • Innym niewłaściwym sposobem jest myślenie: odkładaj lżejsze przedmioty i umieszczaj je od najwyższej do najniższej ceny.
  • ...

Czy to ci pomaga? wiemy, że problem z monetą to wersja problemu z plecakiem. Ale w lesie problemów z plecakiem jest więcej przykładów, na przykład, co z Knapsack 2D (jest to naprawdę pomocne, gdy chcesz wyciąć drewno do wyrobu mebli , widziałem w miejscowym z mojego miasta), bardzo często myśli się, że chciwy też tu działa, ale nie.

jonaprieto
źródło
Chciwy został już uwzględniony w przyjętej odpowiedzi , ale problem plecaka jest szczególnie odpowiedni do zastawiania pułapek.
Raphael
3

Częstym błędem jest nieprawidłowe wdrażanie algorytmów tasowania. Zobacz dyskusję na wikipedii .

n!nn(n1)n

Per Alexandersson
źródło
1
Jest to dobry błąd, ale nie jest dobrą ilustracją oszukiwania heurystycznych przypadków testowych, ponieważ testowanie tak naprawdę nie dotyczy algorytmów tasowania (jest losowe, więc jak byś je przetestował? jak byś to wykrył, patrząc na wynik?)
DW
Oczywiście testujesz to statystycznie. Jednolita losowość jest daleka od „wszystko może się wydarzyć na wyjściu”. Czy nie byłbyś podejrzliwy, gdyby program, który miał emulować kostkę, dał ci 100 3 z rzędu?
Per Alexandersson,
Ponownie mówię o heurystyce studenta dotyczącej „wypróbowania niektórych przypadków testowych ręcznie”. Widziałem wielu uczniów, którzy uważają, że jest to rozsądny sposób sprawdzenia, czy algorytm deterministyczny jest poprawny, ale podejrzewam, że nie zakładają, że jest to dobry sposób na sprawdzenie, czy algorytm tasowania jest prawidłowy (ponieważ algorytm tasowania jest losowy, istnieje nie ma sposobu, aby stwierdzić, czy dane dane wyjściowe są poprawne; w każdym razie nie można ręcznie przekręcić wystarczającej liczby przykładów, aby wykonać użyteczny test statystyczny). Nie spodziewam się więc, że algorytmy tasowania pomogą znacznie wyjaśnić powszechne nieporozumienia.
DW
1
@PerAlexandersson: Nawet jeśli wygenerujesz tylko jedno losowanie, nie będzie to naprawdę losowe przy użyciu MT z n> 2080. Teraz odchylenie od oczekiwanego będzie bardzo małe, więc prawdopodobnie nie będziesz się tym przejmować ... ale dotyczy to nawet jeśli generujesz o wiele mniej niż okres (jak wskazał wyżej asmeurer).
Charles
2
Wydaje się, że ta odpowiedź stała się nieaktualna w przypadku bardziej złożonej odpowiedzi Nikosa M. ?
Raphael
2

Pytony PEP450, które wprowadziły funkcje statystyczne do standardowej biblioteki, mogą być interesujące. W ramach uzasadnienia posiadania funkcji, która oblicza wariancję w standardowej bibliotece pytona, autor Steven D'Aprano pisze:

def variance(data):
        # Use the Computational Formula for Variance.
        n = len(data)
        ss = sum(x**2 for x in data) - (sum(data)**2)/n
        return ss/(n-1)

Powyższe wydaje się być poprawne w przypadku zwykłego testu:

>>> data = [1, 2, 4, 5, 8]
>>> variance(data)
  7.5

Ale dodanie stałej do każdego punktu danych nie powinno zmienić wariancji:

>>> data = [x+1e12 for x in data]
>>> variance(data)
  0.0

A wariancja nigdy nie powinna być ujemna:

>>> variance(data*100)
  -1239429440.1282566

Problem dotyczy liczb i tego, jak traci się precyzja. Jeśli chcesz maksymalnej precyzji, musisz w określony sposób zamówić swoje operacje. Naiwna implementacja prowadzi do niepoprawnych wyników, ponieważ niedokładność jest zbyt duża. To był jeden z problemów, które dotyczyły mojego kursu numerycznego na uniwersytecie.

chrześcijanin
źródło
1
n1
2
@Raphael: Chociaż uczciwie, wybrany algorytm jest dobrze znany jako zły wybór dla danych zmiennoprzecinkowych.
2
Nie chodzi tylko o wdrożenie operacji o numeryce i o utratę precyzji. Jeśli chcesz maksymalnej precyzji, musisz w określony sposób zamówić swoje operacje. To był jeden z problemów, które dotyczyły mojego kursu numerycznego na uniwersytecie.
Christian
Oprócz dokładnego komentarza Raphaela wadą tego przykładu jest to, że nie sądzę, aby dowód poprawności pomógłby uniknąć tej wady. Jeśli nie znasz subtelności arytmetyki zmiennoprzecinkowej, możesz pomyśleć, że udowodniłeś, że jest to poprawne (poprzez udowodnienie, że formuła jest poprawna). Nie jest to więc idealny przykład, aby nauczyć uczniów, dlaczego ważne jest udowodnienie, że ich algorytmy są poprawne. Gdyby uczniowie zobaczyli ten przykład, podejrzewam, że zamiast tego wyciągnęliby lekcję: „obliczenia zmiennoprzecinkowe / numeryczne są trudne”.
DW
1

Chociaż prawdopodobnie nie jest to dokładnie to, czego szukasz, z pewnością łatwo jest to zrozumieć i przetestowanie niektórych małych przypadków bez żadnego innego myślenia doprowadzi do nieprawidłowego algorytmu.

nn2+n+410<dd divides n2+n+41d<n2+n+41

Proponowane rozwiązanie :

int f(int n) {
   return 1;
}

n=0,1,2,,39n=40

To podejście „wypróbuj kilka małych przypadków i wywnioskuj algorytm z wyniku” pojawia się często (choć nie tak bardzo jak tutaj) w konkursach programistycznych, w których presja polega na opracowaniu algorytmu, który (a) można szybko wdrożyć i (b ) ma szybki czas działania.

Rick Decker
źródło
5
Nie sądzę, że jest to bardzo dobry przykład, ponieważ niewiele osób próbowałoby znaleźć dzielniki wielomianu, zwracając 1.
Brian S
1
nn3n
Może to być istotne w tym sensie, że zwracanie stałej wartości dla dzielników (lub innej kaklulacji) może być wynikiem niewłaściwego algorytmicznego podejścia do problemu (na przykład problemu statystycznego lub nieobsługiwania skrajnych przypadków algorytmu). Jednak odpowiedź wymaga przeredagowania
Nikos M.
@NikosM. Heh Wydaje mi się, że biję tutaj martwego konia, ale drugi akapit pytania brzmi: „jeśli ich algorytm działa poprawnie na kilku przykładach, w tym wszystkich przypadkach narożnych, które mogą spróbować, to dochodzą do wniosku, że algorytm musi bądź poprawny. Zawsze jest uczeń, który pyta: „Dlaczego muszę udowodnić, że mój algorytm jest poprawny, jeśli mogę po prostu wypróbować go na kilku testowych przypadkach?” W tym przypadku dla pierwszych 40 wartości (znacznie więcej niż student jest prawdopodobnie spróbuje), poprawne jest zwrócenie 1. Wydaje mi się, że właśnie tego szukał OP
Rick Decker,
Ok, tak, ale to sformułowanie jest banalne (może typowo poprawne), ale nie w duchu pytania. Nadal potrzebowałbym przeredagowania
Nikos M.,