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

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?

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 $d_1,\dots,d_k$$n$$n$$d_i$

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 + $6$$5$$1$$1$$14$$10 = 6+1+1+1+1 = 5+5$

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$\Rightarrow$

„kurs” „kurs” Prawda; dobrze$\Rightarrow$

„” „ Prawda; dobrze$\Rightarrow$

kurs „uniwersytecki” Fałsz; dobrze$\Rightarrow$

„wykład” „kurs” Fałsz; dobrze$\Rightarrow$

$\Rightarrow$

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.

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

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.

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

Lokalne maksimum 2D

$n \times n$$A$

$(i,j)$$A[i,j]$

$A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$$A$

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

$O(n^2)$

$A$$X$$X$$A$$(i, j)$$X$$(i, j)$$(i', j')$

$A \setminus X$$A$$X$$(i', j')$$A'$

$A'$$A$

$(i', j')$$A'$$A'$$(i', j')$$\diamond$

$\frac{n}{2}\times\frac{n}{2}$$A'$$(i, j)$

$T(n)$$n\times n$$T(n) = T(n/2) + O(n)$$T(n) = O(n)$

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

$O(n)$$n\times n$

A może my?

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?

$10^{16}$

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?”

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]

$i$$j$$0 \le j \le i$

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

$n$$n! = n \times n-1 \times n-2 ..$$n$$n-1$

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

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.

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.

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

$n!$$n^n$$(n-1)^n$

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.

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.

$n$$n^2+n+41$$0<d$$d\text{ divides } n^2+n+41$$d < n^2+n+41$

Proponowane rozwiązanie :

int f(int n) {
   return 1;
}

$n= 0, 1, 2, \dotsc, 39$$n=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.