Jakie są znaczące algorytmy dla ludzkości w ostatnich dziesięcioleciach? [Zamknięte]

40

Które najważniejsze algorytmy świata najbardziej przyczyniły się do ludzkości w ciągu ostatnich dziesięcioleci?

Pomyślałem, że jest to dobra ogólna wiedza dla programisty.

Aktualizacja:
Jeśli to możliwe, zachowaj odpowiedź na określony algorytm programowania .
Chciałbym uzyskać listę najważniejszych, tylko jeden algorytm na odpowiedź.
Zastanów się, czy algorytm jest ważny i ważny ...

algorithms problem-solving knowledge Amir Rezaei
źródło
2
Jest zamykany, ponieważ (jak dotąd) cztery osoby uważają to za „nie prawdziwe pytanie”, prawdopodobnie dlatego, że nie mamy żadnego rzeczywistego pojęcia, co w izolacji jest ważnym algorytmem programowania.
David Thornley,
2
To może być nie na temat, ale to prawdziwe pytanie.
Jeremy,
1
+1 Dobre pytanie. Proponuję ponownie zadać to pytanie na cstheory.stackexchange.com
Aleksandr Levchuk
1
Dlaczego odpowiadasz na własne pytania? Kilka razy?
2
Brak błędnych odpowiedzi + nieograniczona liczba odpowiedzi + jednoznaczny komentarz z prośbą o „jedną na odpowiedź” + autor zamieszcza kilka własnych odpowiedzi = przypadek podręcznika o mało konstruktywnym pytaniu. Wiem, że jest stary, ale zamknijmy to.
Aaronaught

Odpowiedzi:

59

Szyfrowanie klucza publicznego / prywatnego jest bardzo ważne. Bez niego handel internetowy nie byłby tak wszechobecny.

Jeremy
źródło
4
+1 i dodać do swojej odpowiedzi, RSA.
zmiany
Istnieje cała grupa algorytmów i najlepszych praktyk związanych z przekształcaniem kodów kryptograficznych (takich jak RSA) w praktyczne rozwiązania.
Donal Fellows
37

Algorytm Dijkstry

Algorytm istnieje w każdym routerze na świecie do identyfikacji najlepszej trasy między dwoma węzłami w sieci.

Amir Rezaei
źródło
Jesteś pewny? Większość routerów albo wie, że należy do niego numer IP i przekazuje go do urządzenia w sieci lokalnej, albo zna router, który zna się lepiej - router domyślny - w takim przypadku pakiet trafia do tego routera. Duże routery mogą wiedzieć, że dla zakresu adresów IP X1-Y1 pakiet powinien przejść do routera R1, dla zakresu X2-Y2 pakiet powinien przejść do routera R2 itp. Nie jest w to zaangażowany algorytm Dijkstras.
2
@ Thorbjørn Ravn Andersen: Ale żeby router mógł poznać te informacje, ktoś w pewnym momencie musiałby użyć algorytmu Dijkstry. Tak, nie jest używany do faktycznego routingu każdego pojedynczego pakietu, ale jest używany do określania tabel routingu w dużych sieciach. +1.
Billy ONeal,
@Billy, gdzie dokładnie można oczekiwać, że algorytm Dijkstry jest rzeczywiście używany i przez kogo?
@ Thorbjørn Ravn Andersen: O ile mi wiadomo, odgrywa rolę w OSPF, który jest podstawą wyboru prawidłowych tras dla małych sieci. Połączenia między większymi sieciami wykorzystują protokół BGP, który jest bardziej oparty na zasadach. Nie jestem pewien, czy BGP korzysta z algorytmu Dijkstry, czy nie.
Billy ONeal,
3
@Billy, ale moim zastrzeżeniem było „istnienie w KAŻDYM routerze na świecie”. Jest to - moim zdaniem - po prostu błędne.
30

Szybka transformata Fouriera (FFT)

FFT to niezwykle ważna i szeroko stosowana metoda pozyskiwania przydatnych informacji z próbkowanych sygnałów .

Szybka transformata Fouriera (FFT) to wydajny algorytm do obliczania dyskretnej transformaty Fouriera (DFT) i jej odwrotności.

Amir Rezaei
źródło
4
Kiedyś miałem szefa, który kilkadziesiąt lat wcześniej napisał szereg funkcji FFT dla PDP-11. Sprzedał talię kart pocztowych z tymi funkcjami wraz z reklamą na tyłach Popular Science i zrobił całkiem poważny bank. Najwyraźniej miał ludzi używających jego kodu do wszystkiego, od przetwarzania sygnałów po prognozy giełdowe.
Dan Ray
26

PageRank

PageRank to algorytm analizy linków, nazwany na cześć Larry Page, wykorzystywany przez wyszukiwarkę internetową Google , która przypisuje wagę numeryczną każdemu elementowi zestawu hiperłącza, np. World Wide Web, w celu „zmierzenia” jego krewnego znaczenie w zestawie.

Amir Rezaei
źródło
haha, nasze odpowiedzi
dzieliły
żaden problem! :)
Amir Rezaei,
36
Nigdy nie zdawałem sobie sprawy, że nazwa pochodzi od Larry'ego Pagea. Zawsze zakładałem, że nazwa ma coś wspólnego ze stronami internetowymi.
JohnFx,
1
@JohnFx Whoa, bez żartów!
Mark C
+1: ale czy można go zakwalifikować, jeśli faktyczny algorytm nie jest znany ludzkości? (Wikisłownik IIRC jest przybliżeniem)
Steven Evers
22

Algorytmy kompresji danych

W informatyce i teorii informacji kompresja danych lub kodowanie źródłowe jest procesem kodowania informacji przy użyciu mniejszej liczby bitów (lub innych jednostek zawierających informacje), niż przy użyciu niekodowanej reprezentacji, przy użyciu określonych schematów kodowania.

Amir Rezaei
źródło
2
Dokładnie i myślę, że podstawowy algorytm kompresji LZW można uznać za jeden z najpiękniejszych algorytmów w inżynierii oprogramowania.
mojuba,
„jeśli to możliwe, podaj nazwę konkretnego algorytmu”
14

Smith-Waterman (i Needleman-Wunsch)

To może być zbyt daleko idące, więc proszę o komentarz.

Smith-Waterman: Algorytm wyrównywania sekwencji

Myślę, że jednym z takich przykładów są algorytmy Smitha-Watermana i Needlemana-Wunscha oraz ich aproksymacje. Wszystkie zasadniczo robią to samo: wyrównują dwa lub więcej ciągów (sekwencji) . Biologia ma znaczenie. Gdy sekwencje DNA lub białek są wyrównane - ujawniają się regiony podobieństwa strukturalnego, funkcjonalnego i ewolucyjnego.

BLAST jako potomek Smitha-Watermana

Heurystyką zbliżoną do Smitha-Watermana jest BLAST. Umożliwia wyszukiwanie sekwencji dużych baz danych pod kątem podobieństwa biologicznego. Popularność BLAST jest naprawdę świetna - najprawdopodobniej jest to najczęściej stosowany algorytm w biologii. Nowsze obszary bioinformatyki i genomiki mają nowsze i lepsze przybliżenia algorytmów Smitha-Watermana / Needlemana-Wunscha, które są dokładniejsze niż BLAST.

Zgromadzenie genomu jako potomek Smitha-Watermana

Wysokoprzepustowe aproksymacje Smitha-Watermana i Needlemana-Wunscha, które są szybsze niż BLAST, są wykorzystywane do składania genomów z sekwencjonowania strzelby - gdzie produktem maszyny sekwencera jest ogromna ilość odczytów DNA (miliardów) z dowolnych części genomu, które są bardzo krótkie (od 50 do 100 nukleotydów). Podejście to zastosowano do ukończenia projektu Human Genome. Wszystkie nowoczesne sekwencjonowanie odbywa się w ten sposób.

Wyrównanie sekwencji wielu rozszerzenie Smith-Waterman

Istnieje wiele algorytmów wyrównywania wielu sekwencji - zbliżają się one do wielosekwencyjnej wersji Smith-Waterman / Needleman-Wunsch. Wiele sekwencji jest dopasowywanych do siebie jednocześnie jako grupa. Jest to o wiele trudniejszy problem niż w parach, ale rozwiązania zapewniają znacznie lepszy wgląd w funkcję biologiczną, strukturę i historię ewolucyjną powiązanych sekwencji.

Aleksandr Levchuk
źródło
Witajcie w Programistach! Możesz podzielić tę odpowiedź na jedną dla każdego przedstawionego tutaj algorytmu, zgodnie ze zwyczajem na listach takich pytań, aby ułatwić głosowanie i sortowanie.
Yi Jiang
@Yi Jiang: Mój panteon! Źle odczytałem twój komentarz jako „ułatwienie wymiotów”. : - /
dr Hannibal Lecter
Tutaj argumentuję za tylko jednym algorytmem - Smith-Waterman (i jego wariant Needleman-Wunsch)
Aleksandr Levchuk
13

Siam wymienił następujące jako najważniejsze algorytmy XX wieku:

1946: Algorytm metropolii dla Monte Carlo . Dzięki zastosowaniu losowych procesów ten algorytm oferuje skuteczny sposób na znalezienie odpowiedzi na problemy, które są zbyt skomplikowane, aby je dokładnie rozwiązać.

1947: Metoda simpleksowa dla programowania liniowego . Eleganckie rozwiązanie typowego problemu w planowaniu i podejmowaniu decyzji.

1950: Metoda iteracji podprzestrzeni Kryłowa . Technika szybkiego rozwiązywania równań liniowych występujących w obliczeniach naukowych.

1951: Podejście rozkładowe do obliczeń macierzowych . Zestaw technik numerycznej algebry liniowej.

1957: Kompilator optymalizacyjny Fortran . Zamienia kod wysokiego poziomu w wydajny kod czytelny dla komputera.

1959: Algorytm QR do obliczania wartości własnych . Kolejna ważna operacja na matrycy sprawiła, że ​​była szybka i praktyczna.

1962: Algorytmy Quicksort do sortowania . Do wydajnej obsługi dużych baz danych.

1965: Szybka transformata Fouriera . Być może najbardziej wszechobecny obecnie używany algorytm rozkłada przebiegi (jak dźwięk) na składniki okresowe.

1977: Wykrywanie relacji liczb całkowitych . Szybka metoda dostrzegania prostych równań spełniana przez zbiory pozornie niepowiązanych liczb.

1987: Szybka metoda wielobiegunowa . Przełom w radzeniu sobie ze złożonością obliczeń n-ciała, stosowanych w problemach od mechaniki niebieskiej po fałdowanie białek.

Osobiście chciałbym wymienić Integer Powiązania Detection z PageRank .

Jason
źródło
1
Do tej listy dodałbym 2 książki, chociaż bardziej dotyczyły one „najważniejszych twierdzeń” XX wieku: Pięć Złotych Zasad amazon.com/Five-Golden-Rules-20th-Century-Mathematics/dp/… oraz Pięć dodatkowych złotych zasad. amazon.com/Five-More-Golden-Rules-20th-Century/dp/0471395285
Tangurena
Techniki Monte Carlo są nadal używane, mniej więcej w oryginalnej formie. Dotyczy to również FFT i Quicksort. Większość reszty po prostu mnie nie zna. Metoda Simplex dla LP wcale nie skaluje się dobrze w porównaniu do bardziej nowoczesnych metod.
David Thornley,
9

PageRankuj, kochaj lub nienawidzę, ale codziennie wpływa na decyzje i działania milionów ludzi na całym świecie.

Maksee
źródło
9

Gdybym musiał wymienić 3 najważniejsze algorytmy używane dzisiaj w komputerach, powiedziałbym:

  1. Wyszukiwanie binarne
  2. Szybkie sortowanie
  3. Algorytm Dijkstry

Binary Search algorytm jest używany stale do zawężenia na pozycji w liście posortowanej, większość wyszukiwań indeksu użyje coś wzdłuż tych linii w pewnym momencie. Ten algorytm umożliwia wyszukiwanie uporządkowanej listy w czasie o (log n).

Quicksort algorytm wreszcie udało się dostać do sortowania O (n log n) przeciętnego przypadku i O (n ^ 2) gorzej sprawa. Sortowanie jest jednym z najczęstszych zadań danych na komputerze i jednym z najdroższych, poprawa średniego sortowania spraw była dużym krokiem naprzód pod względem wydajności.

Jak powiedziano , algorytm Dijkstry tworzy najkrótszą ścieżkę między punktami na wykresie. Jest to szeroko stosowane we wszystkich aplikacjach do routingu, najszerzej w odniesieniu do samego Internetu, zapewniając najszybszą drogę przez splątaną sieć połączonych routerów.

Orbling
źródło
Wyszukiwanie binarne musiałoby być bardzo, bardzo stare ... Mam na myśli, że zostało sformułowane „w przeszłości” i miało miejsce „dekadę”, ale istniałoby to przez wiele setek lat.
Kirk Broadhurst
@Kirk Broadhurst: Mimo to jest to niezwykle ważny algorytm dla komputerów. Niezależnie od tego, kiedy człowiek po raz pierwszy to począł.
Orbling
8

Twierdzenie Bayesa

Prawdopodobnie najbardziej przyczynił się do utrzymania ilości marnującego czas spamu w mojej skrzynce odbiorczej na rozsądnym poziomie.

Oczywiście jestem używany w wielu innych wartościowych aplikacjach, ale moim ulubionym jest zabijanie spamu.

JohnFx
źródło
Oddałbym kciuk w górę, ale to twierdzenie (jedno z najlepszych), a nie algorytm. Jednak wiele algorytmów opiera się na tym twierdzeniu.
Amir Rezaei,
Próbowałem tylko połączyć je wszystkie w ogólną kategorię algorytmów, ale technicznie masz rację.
JohnFx,
@AmirR Technicznie poprawne, najlepszy rodzaj poprawek!
Mark C
7

TimSort

Jest to algorytm sortowania używany obecnie w Pythonie , Javie 7 i Androidzie

Gruntownie:

  • O (N log N) najgorszy przypadek (nie ulega degeneracji)
  • O (N) dla prawie posortowanej listy (w rzeczywistości N-1dokładnie na już posortowanej liście)

A jego piękno? Jest stabilny ! Dlatego nadaje się do sortowania wieloprzebiegowego według różnych kryteriów.

Nawiasem mówiąc, jeśli ktoś ma pod ręką zoptymalizowaną implementację C ++ ...

Matthieu M.
źródło
Nie może być Θ (NlogN), ponieważ ma lepsze zachowanie na już posortowanej liście. O (NlogN) jest tutaj właściwą notacją.
Donal Fellows
Chociaż ten jest fajny, z pewnością nie nazwałbym go „jednym z największych algorytmów wymyślonych w ciągu ostatnich dziesięcioleci”. Mergesort, na którym opiera się Timsort, jest prawdziwym osiągnięciem.
Billy ONeal
6

Wszystkie algorytmy zastosowane do rozwiązania problemu widoczności w animacji komputerowej 3D wydają mi się kluczowe.

Algorytm malarza

Algorytm malarza, znany również jako wypełnienie priorytetowe, jest jednym z najprostszych rozwiązań problemu widoczności w grafice komputerowej 3D. Projektując scenę 3D na płaszczyźnie 2D, w pewnym momencie należy zdecydować, które wielokąty są widoczne, a które ukryte.

Buforowanie Z.

W grafice komputerowej buforowanie Z to zarządzanie współrzędnymi głębi obrazu w grafice trójwymiarowej (3-D), zwykle wykonywane sprzętowo, czasem programowo. Jest to jedno rozwiązanie problemu widoczności, który polega na podejmowaniu decyzji, które elementy renderowanej sceny są widoczne, a które ukryte. Algorytm malarza to kolejne popularne rozwiązanie, które, choć mniej wydajne, może również obsługiwać nieprzezroczyste elementy sceny. Buforowanie Z jest również znane jako buforowanie głębokości.

Określenie ukrytej powierzchni

W grafice komputerowej 3D określanie ukrytej powierzchni (znane również jako usuwanie ukrytej powierzchni (HSR), usuwanie okluzji (OC) lub oznaczanie powierzchni widzialnej (VSD) jest procesem stosowanym do ustalenia, które powierzchnie i części powierzchni nie są widoczne z określonego punktu widzenia Algorytm określania ukrytej powierzchni jest rozwiązaniem problemu widoczności, który był jednym z pierwszych poważnych problemów w dziedzinie grafiki komputerowej 3D. Proces określania ukrytej powierzchni jest czasem nazywany ukrywaniem, a taki algorytm jest czasami nazywany ukrywaniem Analogiem do renderowania linii jest usuwanie linii ukrytych Określenie ukrytej powierzchni jest konieczne do prawidłowego renderowania obrazu, aby na przykład nie można było patrzeć przez ściany w rzeczywistości wirtualnej.

Dane
źródło
3

Niezależnie od tego, którego potrzebujesz, aby rozwiązać obecny problem.

mipadi
źródło
1
Właśnie to chciałem powiedzieć. Teraz nie muszę tego mówić.
Robert Harvey,
Którakolwiek nie jest dobrą odpowiedzią. Niezależnie od tego, które algorytmy nie są znaczące dla ludzkości.
Amir Rezaei,
6
To nie jest specyficzny algorytm, a nawet gdyby tak było, prawdopodobnie nie jest to ważne dla ludzkości.
jason
3

Soundex to algorytm fonetyczny służący do indeksowania nazw według dźwięku.

sal
źródło
W jaki sposób soundex przyczynił się do rozwoju ludzkości?
barjak
Poprawiono umiejętność posługiwania się językiem naturalnym, korygując niewielkie różnice w pisowni i wymowie regionalnej.
sal
3

Algorytm Viterbiego

Początkowo używany do dekodowania kodów korekcji błędów splotowych, obecnie służy do rozwiązywania szerokiej klasy problemów z rozpoznawaniem (od rozpoznawania mowy po bioinformatykę). Można go znaleźć w kilku urządzeniach do komunikacji i przechowywania.

Giacomo Verticale
źródło
Algorytm +1 Viterbi jest bardzo ważny. @ [Giacomo Verticale] być może powinieneś wspomnieć o jego związku z Ukrytymi Modelami Markowa (HMM).
Aleksandr Levchuk
3

MP3

Chociaż jest to bardziej ogólny termin niż konkretny algorytm, wspomnę o MP3 jako agregacji różnych algorytmów i technik, które współpracują ze sobą w celu wygenerowania tego stratnego formatu audio.

Z pewnością miało to bardzo duże znaczenie w „erze cyfrowej”.

Jens Hoffmann
źródło
3

Integracja numeryczna Runge-Kutta . Bez niego wiele symulacji nie byłoby możliwych. Bez programu kosmicznego, bez energii jądrowej, bez balistyki, bez symulacji sportowych, bez kamizelek kuloodpornych, bez symulacji testów zderzeniowych, bez symulacji ruchu płynów, bez symulacji interakcji chemicznych, bez budynków odpornych na trzęsienia ziemi ... lista jest długa.

ja72
źródło
+1 @ j172 Znam to, jest bardzo przydatne w analizie numerycznej i symulacji.
Amir Rezaei
2

Algorytm sortowania.

tia
źródło
5
nie jest to jednak specyficzny algorytm ...
Justin L.,
Tak, co powiedział Justin L., który algorytm sortowania?
dr Hannibal Lecter
„Specyficzny algorytm” powinien być połączony, pierwszy z rodzajów n lg n.
Billy ONeal,
2
@dr Hannibal Lecter: Bubble Sort oczywiście. Cała reszta to przedwczesna optymalizacja.
peterchen
2

Szybkie sortowanie

ysolik
źródło
1
Fuj! Z pewnością mam nadzieję, że ludzie nie używają Quicksort w kodzie produkcyjnym. Co ważniejsze, połączenie firmowe pojawiło się wcześniej i jest prawie tak szybkie. (Mam nadzieję, że większość kodu używa jakiegoś wariantu na Introsort)
Billy ONeal
2
@Billy ONeal, sortowanie w .NET to wszystko Quicksort. Tak więc każdy program, który wywołuje List <T> .Sort (), używa Quicksort w produkcji.
Steven Evers
@SnOrfus: Czy masz dowód na to oświadczenie? W moim rozumieniu lista <t> .Sort opiera się na introsort.
Billy ONeal,
3
@Billy ONeal: prosto z msdn - msdn.microsoft.com/en-us/library/b0zbh7b6.aspx
ysolik
3
@ Thorbjørn: To wciąż nie jest dobry algorytm ogólnego zastosowania. Introsort jest szybkim sortowaniem, ale przełącza się na sortowanie sterty, jeśli wykracza poza określoną głębokość rekurencji. Dzięki temu można mieć dobre cechy szybkiego sortowania, ale zawsze unika się patologicznych przypadków, nawet jeśli algorytm wybiera złe osie.
Billy ONeal,
1

Sortowanie przez wstawianie

Łatwy do wdrożenia, bardzo szybki na małych listach i stosowany w implementacjach Merge Sort / Quicksort, aby je przyspieszyć. Jest stabilny i działa w O (n) na posortowanych listach (po posortowaniu w porządku rosnącym).

Oliver Weiler
źródło
1

Gaussa-Jordana w obliczeniach macierzowych

xport
źródło
1

Filtr Kalmana

Jest intensywnie wykorzystywany w nawigacji, śledzeniu celu (dla prawie każdego czujnika: radaru, sonaru, FLIR, ladar). Jeden podręcznik pokazuje aplikację w kontrolerze dysku. Zrobotyzowane systemy sterowania często wykorzystują filtry Kalmana.

John R. Strohm
źródło
0

Język mówiony i pisany.

Są one obecnie jednym z najbardziej wydajnych algorytmów do przenoszenia wiedzy z jednej rzeczy na drugą. Bez języka społeczeństwo obywatelskie nie mogłoby istnieć, a informacje nie mogłyby być przekazywane.

Malfist
źródło
5
-1: Algorytmy można wyrazić za pomocą języka naturalnego, ale języki naturalne nie są algorytmami.
Steven Evers
2
Czy powiedziałbyś wtedy, że algorytmy kompresji nie są algorytmami? Wszystko, co robi język, to kompresja informacji przekazywanych ze źródła do odbiornika. Ma określone reguły, których należy przestrzegać (gramatyka), tak jak każdy inny algorytm, i pobiera dane wejściowe (twoje doświadczenia) i daje inny wynik (wiedzę). Nie rozumiem, jak nie można uznać języka za algorytm.
Malfist
Nie spełnia wszystkich standardowych definicji algorytmu na wielu frontach.
James Reinstate Monica Polk
0

Struktura danych sterty i związane z nią algorytmy budowy i konserwacji sterty.

I okaż szacunek szybkiemu sortowaniu. Nawet jeśli nie zawsze jest to wybór, jest jednym z podstawowych algorytmów w historycznym rozwoju informatyki i jest doskonałym narzędziem do zrozumienia rekurencji i analizy algorytmów. To jest piękne i tak, uwielbiam to.

James przywraca Monikę Polk
źródło
0

Algorytmy indeksowania, takie jak drzewo B, drzewo B +, indeks skrótu, indeks drzewa binarnego itp. Aby zindeksować ogromną ilość danych.

xyz
źródło
0

MapReduce jako sposób na dzielenie, podbijanie i równoległe przetwarzanie dużych zestawów danych.

Jay Elston
źródło
-1

Algorytm Brute Force!

Wiele osób nie docenia tego algorytmu brutalnej siły. W rzeczywistości służy głównie do rozwiązywania problemów, które nie mają wzorca. Bardzo to kocham!

xport
źródło
5
To nie jest algorytm. To rodzaj algorytmów.
Adam Lear
Jest to metoda zrywania szyfrowania.
Amir Rezaei,
Myślę, że jest również sklasyfikowany jako algorytm. „Zacznij od x, aby coś zrobić”. Algorytm <--- prawda?
xport
Algorytm to seria kroków do wykonania określonego zadania. To nie jest specyficzne.
Anto
-5

Sortowanie baniek!

Sortowanie bąbelkowe nie jest tak złe jak Bogosort . Dlatego głosuję na rodzaj Bubble.

xport
źródło
1
Proszę rozważyć, dlaczego algorytm jest znaczący i ważny, ludzie wydają się po prostu nie zgadzać, dlaczego sortowanie bąbelkowe może być znaczące i ważne.
Tamara Wijsman,
5
Nawet Barack Obama wie , że sortowanie baniek jest niewłaściwą drogą .
Joey Adams,
@TomWij, @Jey: zobacz moją aktualizację.
xport