Algorytmy z książki.

358

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

Aryabhata
źródło
11
Świetne pytanie! [Edytuj:} Jedno pytanie. Gdzie wyznaczamy granicę między algorytmami a strukturami danych? Co jeśli kluczowy wgląd w algorytm jest ściśle związany z strukturą danych (na przykład UNION FIND w odwrotnej funkcji Ackermanna)?
Ross Snider
4
doskonałym źródłem i być może kandydatem do takiej książki jest „Encyklopedia algorytmów” springer.com/computer/theoretical+computer+science/book/…
Marcos Villagra,
21
Jestem trochę zaskoczony, że algorytmy, które uważam za dość trudne (KMP, tablice sufiksów liniowych), są przez innych uważane za „z Księgi”. Dla mnie „z Księgi” oznacza proste i oczywiste, ale tylko z perspektywy czasu. Jestem ciekawy, jak inni interpretują słowo „elegancki”.
Radu GRIGore
49
@ supercooldave Nie musisz wierzyć w Boga, ale powinieneś wierzyć w jego książkę. ;-)
Ross Snider
10
Podczas wykładu w 1985 r. Erdős powiedział: „Nie musisz wierzyć w Boga, ale powinieneś wierzyć w Księgę”.
Robert Massaioli,

Odpowiedzi:

116

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 .

Jukka Suomela
źródło
109

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

Jukka Suomela
źródło
4
To trochę oszałamiające, gdy zdaje sobie sprawę, że to było coś, co kiedyś nie było oczywiste i jest teraz oczywiste, ponieważ wymyślili to i nauczyliśmy się tego ... Myślę, że powinniśmy zastosować teorię historii Carra do matematyki i informatyki .
Ritwik Bose
1
Według opisu powiedziałbym, że jest to związane z szybkim wyszukiwaniem podciągów Boyera-Moore'a.
bart
2
@Mechko Fakt, że ten algorytm został odkryty jednocześnie i niezależnie przez oddzielne osoby, świadczy o tym, że jest do pewnego stopnia oczywisty. To, czy coś jest „oczywiste”, jest funkcją ograniczeń projektu i szerszego środowiska programistycznego. Jeśli potrzebujesz (1) szybkiego wyszukiwania tekstu i (2) zdajesz sobie sprawę ze znaczenia prawdziwych algorytmów O (n), oraz (3) wcześniej napotkałeś tekst z częściowymi dopasowaniami i (4) masz czas aby robić rzeczy „dobrze”, ten algorytm jest prawdopodobnie oczywisty.
Matt Gallagher,
W wywiadzie Knuth powiedział, że pomysł na algorytm zrodził się z badania dwukierunkowego skończonego automatu Stephena Cooka dla palindromów.
Kaveh
@Kaveh Proszę przeczytać rozdział 7 (uwagi historyczne) z oryginalnego dokumentu KMP. Ma świetne uwagi. O Morrisie napisaniu edytora tekstu, który „był zbyt skomplikowany, aby inni implementatorzy systemu mogli go zrozumieć”. O Knutcie „po raz pierwszy z doświadczenia Knutha teoria automatów nauczyła go, jak lepiej rozwiązywać prawdziwe problemy programistyczne, niż mógł je rozwiązać wcześniej”. I „Knuth był niezadowolony, gdy dowiedział się, że Morris już odkrył algorytm, nie znając twierdzenia Cooka;”. ZABAWA.
Hendrik Jan
93

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.
Derrick Stolee
źródło
3
To jeden z moich ulubionych algorytmów. Lubię intuicję, której nauczyłem się z książki rozbieżności Chazelle: zbiór median grup elementów jest jak -net dla przedziałów na uporządkowanej liście liczb wejściowych. Algorytm działa więc zgodnie z ogólnym paradygmatem: oblicz szybko -net, rozwiąż problem w sieci, powtórz na pewnej części danych wejściowych, aby dopracować rozwiązanie, dopóki nie znajdziesz dokładnego rozwiązania. to bardzo przydatna technikaϵ ϵ1/ϵϵϵ
Sasho Nikolov
5
BTW, kiedy sparametryzujesz rozmiar grup, stałe nie są już tak magiczne. są oczywiście zoptymalizowane, aby dać właściwą rzecz w twierdzeniu Mistrza
Sasho Nikolov
Implementacja Ruby, gist.github.com/chadbrewbaker/7202412 Czy istnieje wersja algorytmu, która wykorzystuje przestrzeń (stałą, log), czy też musisz używać liniowej przestrzeni do rysowania, aby utrzymać mediany?
Chad Brewbaker
2
Twierdzenie, że „działa to tylko dlatego, że liczby są w sam raz, aby zmieścić się w twierdzeniu głównym”, nie jest tak naprawdę prawdą. Jeśli zamienisz liczbę na większą liczbę , łatwo zauważyć, że dwie liczby, które muszą sumować się do mniej niż zbiegają się do i , więc wszystkie wystarczająco duże działają. to tylko pierwsza cyfra, która działa, to nie jedyna. n 1 3 / 4 0 N 55n13/40n5
Will Sawin,
88

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

michalmocny
źródło
Zamieniłbym elegancki na intuicyjny. Nie ma w tym nic eleganckiego; jego prostota to prawdziwe piękno.
Robert Massaioli,
@Robert Massaili: Wymieniłem elegancki na piękny. Miałeś rację co do tego.
michalmocny
2
I niesamowicie trudno pisać poprawnie - patrz „ Czy jesteś jednym z 10% programistów, którzy mogą pisać wyszukiwanie binarne?
jon
Na moim pierwszym kursie dla absolwentów z algorytmów mieliśmy 15-minutowe quizy, w których musieliśmy ręcznie rozwiązać 2-3 problemy. Pierwszy taki quiz obejmował drzewo wyszukiwania binarnego i dwa pytania o stosy. Byłem zawstydzony i przerażony, gdy dowiedziałem się, że źle popełniłem problem z wyszukiwaniem binarnym, zanim dowiedziałem się, że w klasie około 30 osób były dwie poprawne odpowiedzi. Ale nawet wiedząc o tym, fakt, że społeczność zawodowa zajęła 15 lat, by to naprawić, jest oszałamiający.
Stella Biderman
84

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(n3)O(n2)

użytkownik651
źródło
2
Algorytm ten można również uogólnić w naprawdę zgrabny sposób. Patrz np. R6.ca/blog/20110808T035622Z.html i cl.cam.ac.uk/~sd601/papers/semirings.pdf
Michaił
73

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.

Jukka Suomela
źródło
10
Quicksort rodzi również interesujące pytania dotyczące tego, czym dokładnie jest istota algorytmu. Np. Standardowa elegancka implementacja Haskell wygląda dokładnie tak, jak standardowa definicja pseudokodu, ale ma inną asymptotyczną złożoność. A zatem, czy Quicksort jest po prostu dzieleniem i podbijaniem, czy sprytne manipulowanie wskaźnikami na miejscu jest istotną częścią Quicksort? Czy Quicksort można nawet wdrożyć w czysto funkcjonalnym otoczeniu, czy też wymaga modyfikacji?
Jörg W Mittag,
2
Idea „esencji” lub „moralności” algorytmu pochodzi oczywiście od pięknego artykułu The Genuine Sieve of Eratosthenes autorstwa Melissy E. O'Neill ( cs.hmc.edu/~oneill/papers/Sieve-JFP. pdf ), a szybka dyskusja pochodzi z dyskusji LtU tego artykułu ( lambda-the-ultimate.org/node/3127 ), a konkretnie zaczynając od tego komentarza: lambda-the-ultimate.org/node/3127/#comment-45549
Jörg W Mittag,
8
@ Jörg: Wdrożenie quicksort na połączonych listach jest całkowicie sensowne i ma taki sam asymptotyczny czas działania, jak jego implementacja w miejscu na tablicach (cholera, nawet naiwna implementacja poza miejscem na tablicach ma ten sam czas działania) - oba na średnia, aw najgorszym przypadku. Jeśli chodzi o wykorzystanie miejsca, to rzeczywiście jest inne, ale trzeba powiedzieć, że nawet wersja „na miejscu” wymaga nietrwałej dodatkowej przestrzeni (stos wywołań!), Co jest faktem łatwo przeoczanym.
Konrad Rudolph,
Warto również wspomnieć o podwójnym przegubie Vladimira Yaroslavskiya Quicksort. To powinno być o co najmniej 20% szybsze oryginalne szybkie
łącze
Teoretycznie Quicksort jest prosty (może być opisany w 4 krokach) i może być wysoce zoptymalizowany, ale w praktyce bardzo trudno jest poprawnie kodować. Dlatego nie dostaje mojego głosu.
Dennis
50

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!

Jukka Suomela
źródło
49

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.

Per Vognsen
źródło
To powinno być zasugerowane dawno temu! Dzięki!
arnab
1
Istnieje kilka innych losowych algorytmów, które zasługują na znaczące miejsce w Księdze. Dla nich kontrast między deterministycznymi i probabilistycznymi alternatywami jest mniej uderzający: algorytm deterministyczny zwykle istnieje, ale jest znacznie bardziej skomplikowany.
Per Vognsen,
Niezależnie wynalazłem ten sam algorytm, gdy kilka lat temu pracowałem nad dokumentem, dopóki ktoś mnie nie zapytał, czy to nie jest lemat Schwartza-Zippela? I powiedziałem, co to jest? :)
Helium
46

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?

Radu GRIGore
źródło
1
To także podstawa wykonania Prologu!
muad
1
Jaki jest sens BFS ze stosem, którego mi brakuje? Myślałem, że odpowiedź brzmi „tak, masz DFS”.
Omar Antolín-Camarena
1
Wydaje się, że wszyscy uważają ten problem za trywialny. Ponadto wydaje się, że wszyscy myślą, że odpowiedź brzmi „tak”, co jest błędne. Odpowiedź brzmi „zależy od tego, od której implementacji BFS zaczynasz”. Zobacz cs.stackexchange.com/questions/329/... (To pytanie zadałem, aby pomóc w fazie beta CS.SE)
Radu GRIGore
Jest również krótko omówione tutaj: ics.uci.edu//~eppstein/161/960215.html
Radu GRIGore
42

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.
David Sifry
źródło
40

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

Ross Snider
źródło
38

Algorytm Strassena do mnożenia macierzy.

Kaveh
źródło
Prawdopodobnie zaczekam, aż dowiemy się, czy jest to optymalne.
Thomas Ahle,
Nie jest to optymalne, przynajmniej asymptotycznie ... Myślę, że włączenie algorytmu Strassena zmusza cię do włączenia najpierw algorytmu Karatsuba.
Timothy Sun
35

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.

Konrad Swanepoel
źródło
+1, ponieważ jest też rozdział w opublikowanych dowodach z książki o małżeństwach ...
ixtmixilix
34

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

zotachidil
źródło
I nie sądzę, że to nie otrzymał uznanie na jakie zasługuje - co sprawia, że myślisz inaczej? Na przykład jest zaimplementowany w bibliotece analizy sekwencji C ++ SeqAn.
Konrad Rudolph,
Warto wspomnieć, że istnieje obecnie szereg innych algorytmów budowy tablicy liniowych i nieliniowych sufiksów czasowych, które, choć nie są tak ładne, mogą być znacznie szybsze w praktyce. „Wydajne, wszechstronne podejście do sortowania sufiksów”, Journal of Experimental Al algorytmics (JEA), tom 12, czerwiec 2008 ma pewne wyniki eksperymentalne zgodne z tymi wytycznymi.
Raphael
@Raphael: Jestem nieco nieufny wobec faktu, że na str. 3 z tego artykułu JEA, dają tylko to, co „uważają” za „luźną” granicę O (n ^ 2 log n) ... Czy znasz jakieś dokumenty z możliwymi do udowodnienia algorytmami czasu liniowego , które są szybsze w praktyce niż Algorytm skosu?
user651
32

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

Mitch
źródło
BTW, jaka jest sekwencja uogólnienia i gdzie pasuje do niej algorytm Buchbergera dla podstawy Grobnera? (Wydaje się to analogiczne do Knuth-Bendix, ale gdzieś widziałem wzmiankę, że uogólnia eliminację Gaussa…)
ShreevatsaR
6
sekwencja jest następująca: euklidesowa GCD -> eliminacja Gaussa -> Buchberger -> Knuth-Bendix. Można także wprowadzić (zamiast eliminacji Gaussa) jednomianowy podział wielomianowy i modulo (w kolejności uogólnienia jest to „oprócz” eliminacji Gaussa, GE to wielowymiarowy stopień 1, pierścień wielomianowy jest nieograniczony jednowymiarowy, stopień nieograniczony wielowymiarowy. skok uogólnienia jest największy z EGCD ​​do GE lub pierścienia wielomianowego z powodu dodania zmiennych, a następnie duży z Buchbergera do KB z powodu nieograniczonej sygnatury
Mitch
+1: algorytm euklidesowy rozwiązuje najbardziej znane równanie ax-by = 1 w matematyce. Dlaczego nie pojawia się częściej w CS, jest tajemnicą.
Tegiri Nenashi,
32

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.

Arnar
źródło
4
Twierdzenie 4:… Dowód: ćwiczenie dla czytelnika.
jon
31

Żół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ł.

Tobias Neukom
źródło
6
Czy znasz głupi algorytm, który rozwiązuje problem z tymi samymi asymptotykami i postępuje według algorytmicznego wzorca projektowego? Mówię o iteracyjnym pogłębianiu. W n-tej iteracji zaczynasz od 2 ^ n-tego następcy roota i patrzysz 2 ^ n następców w poszukiwaniu rekurencji. Mimo że przy każdej iteracji niektóre kroki są odtwarzane, geometryczne tempo wzrostu promienia wyszukiwania oznacza, że ​​nie wpływa to na asymptotykę.
Per Vognsen,
30

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.

arnab
źródło
6
Tak, bardzo fajny algorytm. Mniej trywialnie, kosztem innego współczynnika 2, algorytm ten działa również w celu maksymalizacji dowolnej funkcji podmodularnej, nie tylko funkcji cięcia wykresu. Jest to wynik Feige, Mirrokni i Vondrak z FOCS 07
Aaron Roth
30

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.

James King
źródło
Rzeczywiście istnieje również wiele innych prostych i eleganckich algorytmów aproksymacyjnych z przyzwoitymi gwarancjami aproksymacji.
Janne H. Korhonen
27

O(N)

Joe Fitzsimons
źródło
25

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

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

Kaveh
źródło
I rzeczywiście, kilka nagród Nobla zostało przyznanych za lepsze zrozumienie tych problemów.
Ross Snider
@Ross Kantorovich zdobył nagrodę Nobla w dziedzinie ekonomii za opracowanie LP i zastosowanie jej do alokacji zasobów. O jakich innych nagrodach myślałeś?
Mark Reitblatt
@Mark Koopermans otrzymał nagrodę Nobla wraz z Kantorowiczem, ale nadal nie mogłem powiedzieć „kilka”.
Ross Snider,
22

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.

MassimoLauria
źródło
21

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 .

Diego de Estrada
źródło
20

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.

Diego de Estrada
źródło
10
Chwila, może być piękna, ale jeśli Knuth potrzebował dwóch całych dni, aby to w pełni zrozumieć, czy to naprawdę „z książki”?
ShreevatsaR
@ShreevatsaR Książka ma drobny druk w przypisach :)
hsmyers