Algorytmy z książki.

Paul Erdos mówił o „Księdze”, w której Bóg przechowuje najbardziej elegancki dowód każdego twierdzenia matematycznego. To nawet zainspirowało książkę (która, jak sądzę, jest teraz w czwartym wydaniu): Dowody z książki .

Gdyby Bóg miał podobną książkę na temat algorytmów, jaki według ciebie algorytm byłby kandydatem (kandydatami)?

Jeśli to możliwe, proszę również podać klikalne odniesienie i kluczowe informacje, dzięki którym to działa.

Poproszę tylko jeden algorytm na odpowiedź.

Union-find to piękny problem, którego najlepszy algorytm / struktura danych (Disjoint Set Forest ) opiera się na stosie spaghetti. Choć bardzo proste i intuicyjne, aby wyjaśnić inteligentne dziecko, zajęło kilka lat, aby ściśle związać się z jego środowiskiem uruchomieniowym. Ostatecznie odkryto, że jego zachowanie jest powiązane z odwrotną funkcją Ackermanna, funkcją, której odkrycie oznaczało zmianę perspektywy obliczeniowej (i faktycznie zostało uwzględnione w Hilbert's On the Infinite ).

Wikipedia stanowi dobre wprowadzenie do Disjoint Set Forests .

Dopasowywanie ciągów Knuth-Morris-Pratt . Najsprytniejsze osiem wierszy kodu, jakie kiedykolwiek zobaczysz.

Algorytm Bluma, Floyda, Pratta, Rivesta i Tarjana do znalezienia k- tego elementu nieposortowanej listy w czasie liniowym jest pięknym algorytmem i działa tylko dlatego, że liczby są w sam raz, aby zmieścić się w twierdzeniu głównym. Wygląda to następująco:

1. Posortuj każdą sekwencję pięciu elementów.
2. Wybierz medianę w każdym z nich.
3. Powtórz, aby znaleźć medianę tej listy.
4. Pivot na środkowej medianie (jak w Quicksort)
5. Wybierz właściwą stronę listy i pozycję na tej liście, a następnie powtórz.

Wyszukiwanie binarne to najprostszy, najpiękniejszy i najbardziej użyteczny algorytm, na jaki kiedykolwiek wpadłem.

Dziwi mnie, że nie widzę tutaj algorytmu Floyda-Warshalla dla wszystkich par najkrótszych ścieżek:

d[]: 2D array. d[i,j] is the cost of edge ij, or inf if there is no such edge.

for k from 1 to n:
  for i from 1 to n:
    for j from 1 to n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

$O(n^3)$$O(n^2)$

Algorytm euklidesowy do obliczania największego wspólnego dzielnika (GCD)

Może to wydawać się nieco trywialne (szczególnie w porównaniu z innymi odpowiedziami), ale myślę, że Quicksort jest naprawdę elegancki. Pamiętam, że kiedy go zobaczyłem, myślałem, że to naprawdę skomplikowane, ale teraz wydaje się zbyt proste.

Kodowanie Huffmana do kompresji danych.

Test pierwszeństwa Millera-Rabina (i podobne testy) powinien znajdować się w Księdze. Chodzi o to, aby wykorzystać właściwości liczb pierwszych (tj. Używając małego twierdzenia Fermata), aby probabilistycznie szukać świadka, że ​​liczba nie jest liczbą pierwszą. Jeśli po wystarczającej liczbie losowych testów nie zostanie znaleziony świadek, liczba zostanie sklasyfikowana jako liczba pierwsza.

W związku z tym test pierwszeństwa AKS, który wykazał PRIMES jest w P, z pewnością powinien być w Księdze!

Testowanie tożsamości wielomianowej za pomocą lematu Schwartza-Zippla :

Gdyby ktoś obudził cię w środku nocy i poprosił o przetestowanie dwóch jednoznacznych wyrażeń wielomianowych pod kątem tożsamości, prawdopodobnie zredukowałbyś je do normalnej postaci sumy produktów i porównałbyś pod względem tożsamości strukturalnej. Niestety redukcja może potrwać wykładniczo; jest to analogiczne do redukowania wyrażeń logicznych do rozłącznej postaci normalnej.

Zakładając, że lubisz algorytmy losowe, następną próbą prawdopodobnie będzie ocena wielomianów w losowo wybranych punktach w poszukiwaniu kontrprzykładów, deklarując, że wielomiany będą prawdopodobnie identyczne, jeśli przejdą wystarczającą liczbę testów. Lemat Schwartza-Zippela pokazuje, że wraz ze wzrostem liczby punktów prawdopodobieństwo fałszywie dodatniego bardzo szybko maleje.

Nie jest znany żaden deterministyczny algorytm problemu, który działałby w czasie wielomianowym.

Głębokie pierwsze wyszukiwanie . Jest podstawą wielu innych algorytmów. Jest to również zwodniczo proste: na przykład, jeśli zastąpisz kolejkę w implementacji BFS stosem, czy otrzymujesz DFS?

Algorytm Dijkstry : problem najkrótszej ścieżki z jednego źródła dla wykresu z nieujemnymi kosztami ścieżki krawędziowej. Jest używany wszędzie i jest jednym z najpiękniejszych algorytmów. Bez niego Internet nie mógłby być routowany - jest to podstawowa część protokołów routingu IS-IS i OSPF (Open Shortest Path First).

1. Przypisz do każdego węzła wartość odległości. Ustaw go na zero dla naszego początkowego węzła i na nieskończoność dla wszystkich innych węzłów.
2. Oznacz wszystkie węzły jako niezwiedzone. Ustaw węzeł początkowy jako bieżący.
3. W przypadku bieżącego węzła weź pod uwagę wszystkich jego niewidzianych sąsiadów i oblicz ich wstępną odległość (od początkowego węzła). Na przykład, jeśli bieżący węzeł (A) ma odległość 6, a krawędź łącząca go z innym węzłem (B) wynosi 2, odległość do B do A będzie wynosić 6 + 2 = 8. Jeśli ta odległość jest mniejsza niż poprzednio zarejestrowana odległość (nieskończoność na początku, zero dla początkowego węzła), zastąp odległość.
4. Kiedy skończymy, biorąc pod uwagę wszystkich sąsiadów bieżącego węzła, oznacz go jako odwiedzony. Odwiedzony węzeł nie będzie już nigdy sprawdzany; zarejestrowana teraz odległość jest ostateczna i minimalna.
5. Jeśli wszystkie węzły zostały odwiedzone, zakończ. W przeciwnym razie ustaw nie odwiedzony węzeł na najmniejszą odległość (od węzła początkowego) jako następny „aktualny węzeł” i kontynuuj od kroku 3.

Sito Eratostenesa , prosty i intuicyjny.

Lubię też piękno algorytmu Hornera .

Schemat w pełni homomorficznego szyfrowania Gentry'ego (albo nad idealnymi sieciami, albo nad liczbami całkowitymi) jest strasznie piękny. Umożliwia stronom trzecim wykonywanie dowolnych obliczeń na zaszyfrowanych danych bez dostępu do klucza prywatnego.

Schemat szyfrowania wynika z kilku przenikliwych obserwacji.

• Aby uzyskać w pełni homomorficzny schemat szyfrowania, wystarczy mieć schemat homomorficzny w stosunku do dodawania i mnożenia. Wynika to z tego, że dodawanie i mnożenie (mod 2) wystarczą, aby uzyskać bramki AND, OR i NOT (a zatem Turing Completeness).
• Że gdyby taki schemat miał być zastosowany, ale z powodu pewnych ograniczeń można go wykonać tylko dla obwodów o pewnej skończonej głębokości, wówczas można homomorficznie ocenić procedurę deszyfrowania i ponownej interpretacji w celu zresetowania ograniczenia głębokości obwodu bez poświęcania prywatności klucza.
• Że przez „zmiażdżenie” głębokości obwodowej wersji funkcji deszyfrowania dla schematu można włączyć schemat pierwotnie ograniczony do skończonych, płytkich obwodów o dowolnej liczbie obliczeń.

W swojej pracy Craig Gentry rozwiązał długotrwały (i wspaniały) otwarty problem w kryptografii. Fakt, że istnieje schemat w pełni homomorficzny, wymaga od nas uznania, że ​​istnieje pewna nieodłączna struktura obliczalności, którą w przeciwnym razie moglibyśmy zignorować.

http://crypto.stanford.edu/craig/craig-thesis.pdf

http://eprint.iacr.org/2009/616.pdf

http://portal.acm.org/citation.cfm?id=1666420.1666445

Cooley-Tukeya Algorytm FFT .

Algorytm Strassena do mnożenia macierzy.

Gale-Shapley algorytm stabilny małżeństwo . Ten algorytm jest zachłanny i bardzo prosty, na początku nie jest oczywiste, dlaczego miałby działać, ale potem dowód poprawności jest znowu łatwy do zrozumienia.

Algorytm czasu liniowego do konstruowania tablic sufiksów jest naprawdę piękny, chociaż tak naprawdę nie otrzymał uznania, na które zasługiwał, http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf

Eliminacja Gaussa. Uzupełnia sekwencję generalizacji od euklidesowego algorytmu GCD do Knuth-Bendix.

Byłem pod wrażeniem, gdy pierwszy raz zobaczyłem algorytm próbkowania zbiornika i jego dowód. Jest to typowa łamigłówka typu „łamigłówka” z niezwykle prostym rozwiązaniem. Myślę, że zdecydowanie należy do tej książki, zarówno dotyczącej algorytmów, jak i twierdzeń matematycznych.

Jeśli chodzi o książkę, historia głosi, że kiedy Erdös zmarł i poszedł do nieba, poprosił o spotkanie z Bogiem. Prośba została przyjęta, a na spotkanie Erdös miał tylko jedno pytanie. „Czy mogę zajrzeć do książki?” Bóg powiedział „tak” i doprowadził do tego Erdösa. Erdös, oczywiście bardzo podekscytowany, otwiera książkę tylko po to, by zobaczyć następujące rzeczy.

Twierdzenie 1: ...
Dowód: oczywiste.

Twierdzenie 2: ...
Dowód: oczywiste.

Twierdzenie 3: ...
Dowód: oczywiste.

Żółw i zając Algorithm . Podoba mi się, ponieważ jestem pewien, że nawet gdybym zmarnował całe życie, próbując go znaleźć, nie ma mowy, żebym wpadł na taki pomysł.

Przykład tak fundamentalny i „trywialny” jak dowód Euclida na nieskończenie wiele liczb pierwszych:

2-aproksymacja dla MAX-CUT - Niezależnie dla każdego wierzchołka, przypisz go do jednej z dwóch partycji z jednakowym prawdopodobieństwem.

Zawsze byłem częściowo zwolennikiem algorytmu Christofidesa, który daje (3/2) aproksymację dla metrycznego TSP. Zadzwoń do mnie łatwo, ale podobał mi się nawet algorytm 2-aproksymacyjny, który był wcześniej . Sztuczka Christofidesa polegająca na stworzeniu drzewa Eulerian o minimalnej masie, dodając dopasowanie jego wierzchołków o nieparzystym stopniu (zamiast duplikowania wszystkich krawędzi), jest prosta i elegancka, i niewiele trzeba, aby przekonać jednego, że to dopasowanie nie przekracza połowy masy optymalnej trasy.

Scal sortowanie . Prosty, elegancki, wydajny.

$O(\sqrt N)$

Algorytmy programowania liniowego : Simplex, Elipsoida i metody punktów wewnętrznych.

http://en.wikipedia.org/wiki/Linear_programming#Al Algorytmy

Algorytm Robin Moser do rozwiązywania określonej klasy instancji SAT. Takie przypadki rozwiązuje Lovasz Local Lemma. Algorytm Mosera jest rzeczywiście de-randomizacją zdania lematu.

Myślę, że za kilka lat jego algorytm (i technika jego sprawdzania poprawności) zostanie dobrze przetrawiony i dopracowany do tego stopnia, że ​​stanie się realnym kandydatem na algorytm z Księgi .

Ta wersja jest przedłużeniem jego oryginalnej pracy napisanej przez Gábora Tardosa.

Najszybszy i najkrótszy algorytm Marcusa Huttera dla wszystkich dobrze zdefiniowanych problemów .

Ten rodzaj jest sprzeczny z duchem innych ofert na tej liście, ponieważ ma on jedynie charakter teoretyczny, a nie praktyczny, ale znowu tytuł mówi wszystko. Być może powinien zostać uwzględniony jako opowieść ostrzegawcza dla tych, którzy patrzą tylko na asymptotyczne zachowanie algorytmu.

Knuth's Algorytm X znajduje wszystkie rozwiązania dokładnego problemu z okładką . To, co jest w tym magiczne, to technika, którą zaproponował, aby skutecznie go wdrożyć: Dancing Links .

Myślę, że musimy włączyć Schiebera-Vishkina , który odpowiada na najniższe wspólne zapytania przodków w stałym czasie, wstępnie przetwarzając las w czasie liniowym.

Lubię ekspozycję Knutha w tomie 4 Fascicle 1 i jego zadumanie . Powiedział, że zajęło mu to całe dwa dni, aby to w pełni zrozumieć, i pamiętam jego słowa:

Myślę, że jest dość piękny, ale co zaskakujące, ma złą prasę w literaturze (..) Opiera się na matematyce, która mnie ekscytuje.