Jak oszukać heurystyczną kontrolę fabuły?

23

Nad tutaj , Dave Clarke zaproponował, aby porównać asymptotycznej wzrostu należy wykreślić funkcje w zasięgu ręki. Jako teoretycznie skłonny informatyk nazywam (red.) To vodoo, ponieważ fabuła nigdy nie jest dowodem. Po zastanowieniu muszę się zgodzić, że jest to bardzo użyteczne podejście, które czasami jest niedostatecznie wykorzystywane; fabuła to skuteczny sposób na uzyskanie pierwszych pomysłów, a czasem to wszystko, czego potrzebujesz.

Podczas nauczania TCS zawsze jest uczeń, który pyta: „Do czego potrzebuję formalnego dowodu, jeśli mogę po prostu wykonać X, który zawsze działa?” Do jego nauczycieli należy wskazanie i zilustrowanie błędu. Istnieje genialny zestaw przykładów widocznych wzorców, które ostatecznie ulegają awarii w matematyce.SE, ale są to dość matematyczne scenariusze.

Jak więc oszukać heurystyczną kontrolę fabuły? Istnieją przypadki, w których różnice są trudne do odróżnienia, np

przykład
^{[ źródło ]}

Zgadnij, a następnie sprawdź źródło rzeczywistych funkcji. Ale nie są one tak spektakularne, jak bym się spodziewał, w szczególności dlatego, że prawdziwe relacje można łatwo dostrzec na podstawie samych funkcji, nawet dla początkujących.

Czy istnieją przykłady (względnego) asymptotycznego wzrostu, w którym prawda nie jest oczywista z definicji funkcji, a kontrola wykresu dla stosunkowo dużego daje zupełnie błędny pomysł? Mile widziane są funkcje matematyczne i rzeczywiste zestawy danych (np. Środowisko wykonawcze określonego algorytmu); powstrzymaj się jednak od częściowych funkcji. $n$

asymptotics didactics

— Raphael
źródło

2

Właściwie zaproponowałem to jako wskazówkę do zrozumienia problemu.

— Dave Clarke

@DaveClarke: Wiem; Użyłem twojego początkowego sformułowania jedynie jako prowokujący otwieracz. Żadne przestępstwo nie jest zamierzone.

— Raphael

23

$(\log n)^a$ $n^b$ $O(\sqrt{n} \log n)$ $O(n^{0.6})$

wątek
^{[ źródło ]}

$[0,1]$ $n^{0.6}$ $n^{0.7}$ $n^{1/2}\log^{3/4}n$ $n^{2/3}$

— Peter Shor
źródło

15

Oto kolejny (co prawda raczej skonstruowany) przykład, ale wciąż taki, który wydaje mi się niezwykły. Ma to na celu wykazanie, że wykresy mogą być bardzo mylące dla oceny asymptotycznego wzrostu.

$f$ $g$

Czy potrafisz zgadnąć, która z funkcji rośnie (asymptotycznie) szybciej?

wykres f i g do 2000 wykres f i g do 10.000 wykres f i g do 200 000

$f\sim g$

f (x) = x^{2}

$f(x) = x^2$

g (x) = \iint \sin (\log (x)) + 1 d x d x = x^{2} (1 - \frac{3}{5} \cos (\log (x)) + \frac{1}{5} \sin (\log (x))) .

$g(x) = \iint \sin(\log(x))+1 \;dx\,dx = x^2\Bigl(1 - \tfrac{3}{5} \cos(\log(x)) + \tfrac{1}{5} \sin(\log(x)) \Bigr)\;.$

Więc jest zasadniczo , tj. To samo co , ale jego druga pochodna nie jest równomiernie , ale oscyluje między a z wykładniczo rosnącym okresem. Ta oscylacja nie jest widoczna na zwykłych wykresach. $g$ $x^2$ $f$ $2$ $0$ $4$

W tym przykładzie możemy zdemaskować oscylacje, biorąc pod uwagę wykres log-log:

log-log-wykres f i g do 200 000

Oczywiście ogólnie to nie pomaga; na przykład możemy mieć podwójnie wykładniczy okres ...

— Sebastian
źródło

12

Dobrym przykładem jest głęboko magiczny algorytm minimalnego DFA Brzozowskiego. Biorąc pod uwagę automat skończony , możemy obliczyć z niego minimalny deterministyczny automat skończony: $N = (Q, S \subseteq Q, F \subseteq Q, R \subseteq Q \times \Sigma \times Q)$

M i n i m i z e : N F A \to D F A = D e t e r m i n i z e \circ R e v e r s e \circ D e t e r m i n i z e \circ R e v e r s e

$\mathrm{Minimize} : \mathrm{NFA \to DFA} = \mathrm{Determinize\circ Reverse \circ Determinize \circ Reverse}$

Jest to oczywiście najgorszy przypadek algorytmu czasu wykładniczego, ponieważ może on przyjąć niedeterministyczny automat i dać ci deterministyczny (lub, co bardziej oczywiste, wywołuje konstrukcję podzbioru dwa razy).

Jeśli jednak podasz algorytmowi Brzozowskiego DFA jako dane wejściowe, na wielu popularnych rodzajach danych wejściowych może konkurować i często przewyższać wyspecjalizowane algorytmy minimalizacji DFA (zwykle lub jeśli jesteś hardkorowy i wdrażasz algorytm Hopcraft). $O(n^2)$ $O(n \log(n))$

Dotyczy to części „fabuły” heurystycznej kontroli fabuły - musimy wybrać, które punkty próbkować podczas rysowania fabuły, i można oszukać naiwną fabułę, jeśli nie starannie wybierzesz swoje punkty. Dotyczy to również innych przykładów, takich jak Quicksort i algorytm Simplex, ale dla pedagogiki wolę ten algorytm od tych dwóch.

Różnica Quicksort jest „tylko” kwadratowa względem logarytmiczno-liniowej, co jest mniej spektakularne niż różnica wielomianowa / wykładnicza. Algorytm simpleks ma podobnie spektakularną różnicę, ale jego analiza jest znacznie bardziej skomplikowana niż algorytm Brzozowskiego.

(Wydaje mi się również, że algorytm minimalizacji DFA Brzozowskiego jest znacznie mniej znany niż na to zasługuje, ale oczywiście jest to kwestia gustu.)

— Neel Krishnaswami
źródło

Przepraszam, ale nie do końca rozumiem związek z interpretowaniem wykresów funkcji.

— Raphael

3

Zakładam, że zrobiłbyś coś w rodzaju wydajności wykresu w zależności od wielkości instancji dla próbkowania instancji - a algorytm Brzozowskiego „wyglądałby” wielomianowo, chyba że wybierzesz instancję, aby uzyskać czas wykładniczy.

— Neel Krishnaswami

1

Widzę. Jest to z pewnością problem przy analizie algorytmów i wykreślaniu średnich czasów wykonywania, tj. Problem z wykreślaniem właściwych danych . Kiedy zadałem pytanie, myślałem tylko o właściwej interpretacji fabuły , która jest zupełnie inną bestią. Czy możesz dodać tę perspektywę do odpowiedzi?

— Raphael

Miałbyś ten sam problem dla wszystkich algorytmów, które mają różne średnie i najgorsze zachowanie; Przychodzą mi na myśl Quicksort i Simplex.

— Raphael

8

Matematyczną technikę dopasowania krzywej można zastosować, aby uzyskać nieskończoną liczbę odpowiedzi na twoje pytanie. Biorąc pod uwagę krzywą i zakres, można łatwo znaleźć wielomian, który pasuje do krzywej z dowolnym stopniem dokładności. Ten przykład z wikipedii pokazuje, w jaki sposób fala grzechu może być dość dokładnie dopasowana do wielomianu czwartego rzędu (niebieska krzywa).

wprowadź opis zdjęcia tutaj

Mógłbym użyć wielomianów wyższego rzędu i oszukać heurystykę inspekcji wykresu nawet lepiej niż ten wykres.

— Dave Clarke
źródło

2

To prawda. Ma również sztuczny smak. Jasne, że w ten sposób mogę generować kontrprzykłady dla studentów, ale nie widzę, by bardziej sceptyczny był do tego przekonany. Czy istnieją „naturalne” zjawiska tego zjawiska (tj. Funkcje wielomianowe wyższego stopnia, które można pomylić z innymi funkcjami), w których błędna interpretacja jest „śmiertelna”?

— Raphael

Wiem, że nie jest to odpowiedź, której szukasz.

— Dave Clarke