Wdrożone podstawowe algorytmy

Aby zademonstrować znaczenie algorytmów (np. Dla studentów i profesorów, którzy nie zajmują się teorią lub nawet pochodzą z zupełnie innych dziedzin), czasem warto mieć pod ręką listę przykładów, w których podstawowe algorytmy zostały zastosowane w celach komercyjnych, rządowych, lub powszechnie używane oprogramowanie / sprzęt.

Szukam takich przykładów, które spełniają następujące kryteria:

1. Oprogramowanie / sprzęt korzystający z algorytmu powinien być obecnie szeroko stosowany.

2. Przykład powinien być konkretny. Proszę podać odniesienie do konkretnego systemu i określonego algorytmu.
   Np. W „algorytmie X jest przydatny do przetwarzania obrazu” termin „przetwarzanie obrazu” nie jest wystarczająco szczegółowy; w „Wyszukiwarce Google używa algorytmów grafowych” termin „algorytmy graficzne” nie jest wystarczająco precyzyjny.

3. Algorytmu należy uczyć na typowych studiach licencjackich lub doktoranckich. klasy w algorytmach lub strukturach danych. Idealnie algorytm jest opisany w typowych podręcznikach algorytmów. Np. „Dobrze znany system X wykorzystuje mało znany algorytm Y” nie jest dobry.

Aktualizacja:

Jeszcze raz dziękuję za wspaniałe odpowiedzi i linki! Niektóre osoby komentują, że trudno jest spełnić kryteria, ponieważ podstawowe algorytmy są tak wszechobecne, że trudno wskazać konkretne zastosowanie. Widzę trudność. Ale myślę, że warto wymyślić konkretne przykłady, ponieważ z mojego doświadczenia mówię ludziom: „Patrz, algorytmy są ważne, ponieważ są prawie wszędzie !” nie działa.

Moim zdaniem, algorytmy, które są głównym czynnikiem napędzającym system, są łatwiejsze do znalezienia w kursach nie-algorytmicznych z tego samego powodu, dla których twierdzenia z natychmiastowymi zastosowaniami są łatwiejsze do znalezienia w matematyce stosowanej niż w kursach matematyki czystej. Problem praktyczny rzadko ma dokładną strukturę problemu abstrakcyjnego na wykładzie. Argumentując, nie widzę powodu, dla którego modne algorytmy, takie jak mnożenie Strassena, test pierwszeństwa AKS lub algorytm Moser-Tardos, są istotne dla praktycznych problemów na niskim poziomie związanych z implementacją bazy danych wideo, kompilatora optymalizującego, systemu operacyjnego , system kontroli przeciążenia sieci lub dowolny inny system. Wartością tych kursów jest poznanie, że istnieją skomplikowane sposoby wykorzystania struktury problemu w celu znalezienia skutecznych rozwiązań. Zaawansowane algorytmy to także miejsce, w którym można spotkać proste algorytmy, których analiza nie jest trywialna. Z tego powodu nie odrzuciłbym prostych algorytmów z randomizacją ani PageRank.

Myślę, że możesz wybrać dowolny duży program i znaleźć zaimplementowane w nim podstawowe i zaawansowane algorytmy. Jako studium przypadku zrobiłem to dla jądra Linuksa i pokazałem kilka przykładów z Chromium.

Podstawowe struktury danych i algorytmy w jądrze systemu Linux

Linki do kodu źródłowego na github .

1. Związany lista , podwójnie połączonej listy , połączonej listy lock-wolny .

2. B + Drzewa z komentarzami informującymi o tym, czego nie można znaleźć w podręcznikach.

   Stosunkowo prosta implementacja drzewa B +. Napisałem to jako ćwiczenie edukacyjne, aby zrozumieć, jak działają drzewa B +. Okazało się również przydatne.

   ...

   Zastosowano sztuczki, które nie są powszechnie spotykane w podręcznikach. Najniższe wartości są po prawej, a nie po lewej. Wszystkie używane gniazda w węźle znajdują się po lewej stronie, wszystkie nieużywane gniazda zawierają wartości NUL. Większość operacji po prostu zapętla raz wszystkie szczeliny i kończy na pierwszym NUL.

3. Listy posortowane według priorytetów używane dla muteksów , sterowników itp.

4. Czerwono-czarne drzewa są wykorzystywane do planowania, zarządzania pamięcią wirtualną, aby śledzić deskryptory plików i wpisów z książki telefonicznej itp.
5. Drzewa interwałowe

6. Drzewa Radix są używane do zarządzania pamięcią , wyszukiwania związanych z NFS i funkcjonalności związanych z siecią.

   Powszechnym zastosowaniem drzewa radix jest przechowywanie wskaźników do struktury stron;

7. Kupa priorytetowa , która jest dosłownie implementacją podręcznika, używana w systemie grupy kontrolnej .

   Prosta sterta priorytetowa tylko wstawiana o wielkości statycznej zawierająca wskaźniki, oparta na CLR, rozdział 7

8. Funkcje skrótu , w odniesieniu do Knutha i artykułu.

   Knuth zaleca liczby pierwsze w przybliżeniu złotym stosunku do maksymalnej liczby całkowitej reprezentowanej przez słowo maszynowe dla multiplikatywnego mieszania. Chuck Lever zweryfikował skuteczność tej techniki:

   http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

   Te liczby pierwsze są wybierane tak, aby były rzadkie, tzn. Operacje na nich mogą używać przesunięć i dodatków zamiast mnożenia dla maszyn, na których mnożenie jest powolne.

9. Niektóre części kodu, takie jak ten sterownik , implementują własną funkcję skrótu.

   funkcja skrótu za pomocą algorytmu Rotating Hash

   Knuth, D. Sztuka programowania komputerowego, Tom 3: Sortowanie i wyszukiwanie, Rozdział 6.4. Addison Wesley, 1973

10. Tabele skrótów używane do implementacji i- węzłów , kontroli integralności systemu plików itp.

11. Tablice bitów , które są używane do radzenia sobie z flagami, przerwaniami itp. I są opisane w Knuth Vol. 4

12. Semafory i zamki spinowe

13. Wyszukiwanie binarne służy do obsługi przerwań , wyszukiwania pamięci podręcznej rejestru itp.

14. Wyszukiwanie binarne za pomocą B-drzew

15. Głębokie pierwsze wyszukiwanie i wariant używany w konfiguracji katalogu .

    Wykonuje zmodyfikowany spacer w głąb drzewa nazw, zaczynając (i kończąc) w węźle określonym przez uchwyt_początkowy. Funkcja zwrotna jest wywoływana za każdym razem, gdy zostanie znaleziony węzeł pasujący do parametru typu. Jeśli funkcja zwrotna zwraca niezerową wartość, wyszukiwanie jest natychmiast przerywane i ta wartość jest zwracana do osoby dzwoniącej.

16. Pierwsze wyszukiwanie szerokości służy do sprawdzenia poprawności blokowania w czasie wykonywania.

17. Sortowanie według list na połączonych listach służy do wyrzucania elementów bezużytecznych , zarządzania systemem plików itp.

18. Zadziwiająco zaimplementowano także sortowanie bąbelkowe w bibliotece sterowników.

19. Dopasowywanie ciągów Knuth-Morris-Pratt ,

    Implementuje algorytm dopasowywania łańcucha w czasie liniowym dzięki Knuthowi, Morrisowi i Prattowi [1]. Ich algorytm unika całkowicie jawnego obliczenia funkcji przejścia DELTA. Jego dopasowanym czasem jest O (n), przy czym n jest długością (tekstem), przy użyciu tylko funkcji pomocniczej PI [1..m], przy czym m jest długością (wzorem), wstępnie obliczonym ze wzoru w czasie O (m). Tablica PI umożliwia wydajne obliczanie funkcji przejścia DELTA „w locie” w razie potrzeby. Z grubsza mówiąc, dla każdego stanu „q” = 0,1, ..., mi dowolnego znaku „a” w SIGMA, wartość PI [„q”] zawiera informacje niezależne od „a” i potrzebne do obliczyć DELTA („q”, „a”) 2. Ponieważ tablica PI ma tylko m wpisów, podczas gdy DELTA ma wpisy O (m | SIGMA |), zapisujemy współczynnik | SIGMA | w czasie przetwarzania wstępnego, obliczając PI zamiast DELTA.

    [1] Cormen, Leiserson, Rivest, Stein Wprowadzenie do algorytmów, 2. wydanie, MIT Press

    [2] Patrz teoria skończonej automatyzacji

20. Dopasowywanie wzoru Boyera-Moore'a z referencjami i zaleceniami, kiedy preferować alternatywę.

    Implementuje algorytm dopasowywania ciągów Boyera-Moore'a:

    [1] Algorytm szybkiego wyszukiwania ciągów, RS Boyer i Moore. Komunikat Association for Computing Machinery, 20 (10), 1977, ss. 762-772. http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

    [2] Podręcznik dokładnych algorytmów dopasowania ciągów, Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

    Uwaga: Ponieważ Boyer-Moore (BM) wyszukuje dopasowania od prawej do lewej, nadal możliwe jest, że dopasowanie może być rozłożone na wiele bloków, w takim przypadku algorytm ten nie znajdzie żadnego przypadku.

    Jeśli chcesz mieć pewność, że coś takiego się nigdy nie wydarzy, użyj zamiast tego implementacji Knuth-Pratt-Morris (KMP). Podsumowując, wybierz odpowiedni algorytm wyszukiwania ciągu w zależności od ustawienia.

    Załóżmy, że korzystasz z infrastruktury wyszukiwania tekstu do filtrowania, NIDS lub
    podobnych celów związanych z bezpieczeństwem, a następnie skorzystaj z KMP. W przeciwnym razie, jeśli naprawdę zależy Ci na wydajności, powiedz, że klasyfikujesz pakiety, aby zastosować zasady jakości usług (QoS), i nie masz nic przeciwko możliwym dopasowaniom rozłożonym na wiele fragmentów, a następnie przejdź do BM.

Struktury danych i algorytmy w przeglądarce Chromium

Linki do kodu źródłowego w kodzie Google . Wymienię tylko kilka. Sugeruję skorzystanie z funkcji wyszukiwania, aby wyszukać swój ulubiony algorytm lub strukturę danych.

1. Splay drzewa .

   Drzewo jest również parametryzowane przez zasady alokacji (Alokator). Ta zasada służy do alokacji list w wolnym sklepie C lub strefie; patrz zone.h.

2. Diagramy Voronoi są używane w wersji demonstracyjnej.
3. Tabulacja oparta na algorytmie Bresenhama .

1. Drzewa binarne
2. Czerwono-czarne drzewa

   Wniosek Juliana Walkera

   Czerwone czarne drzewa to ciekawe bestie. Uważa się, że są prostsze niż drzewa AVL (ich bezpośredni konkurent), i na pierwszy rzut oka wydaje się, że tak jest, ponieważ wstawianie jest bardzo proste. Jednak gdy zaczyna się grać algorytmem usuwania, czerwone czarne drzewa stają się bardzo trudne. Jednak przeciwwagą dla tej dodatkowej złożoności jest to, że zarówno wstawianie, jak i usuwanie może być realizowane za pomocą algorytmu odgórnego z pojedynczym przejściem. Tak nie jest w przypadku drzew AVL, w których tylko algorytm wstawiania można zapisywać z góry na dół. Usunięcie z drzewa AVL wymaga algorytmu oddolnego.

   ...

   Popularne są czerwone czarne drzewa, ponieważ większość struktur danych ma kapryśną nazwę. Na przykład w Javie i C ++ struktury map biblioteki są zwykle implementowane za pomocą czerwonego czarnego drzewa. Czerwone czarne drzewa są również porównywalne pod względem prędkości do drzew AVL. Podczas gdy równowaga nie jest tak dobra, praca nad utrzymaniem równowagi jest zwykle lepsza na czerwonym czarnym drzewie. Krąży kilka nieporozumień, ale w większości szum o czerwonych czarnych drzewach jest dokładny.

3. Drzewa AVL
4. Do kompresji stosuje się dopasowanie łańcucha Rabin-Karp .
5. Oblicz przyrostki automatu .
6. Filtr Bloom wdrożony przez Apple Inc.
7. Algorytm Bresenhama .

Biblioteki języków programowania

Myślę, że warto je rozważyć. Projektanci języków programowania uznali, że warto poświęcić czas i wysiłek niektórych inżynierów na wdrożenie tych struktur danych i algorytmów, aby inni nie musieli tego robić. Istnienie bibliotek jest jednym z powodów, dla których możemy znaleźć podstawowe struktury danych zaimplementowane w oprogramowaniu napisanym w C, ale mniej w przypadku aplikacji Java.

1. C ++ STB zawiera listę stosy, kolejki, mapy wektorów i algorytmy sortowanie, wyszukiwanie i manipulacji sterty .
2. Java API jest bardzo rozbudowany i obejmuje znacznie więcej.
3. Biblioteka Boost C ++ zawiera algorytmy takie jak Boyer-Moore i Knuth-Morris-Pratt.

Algorytmy alokacji i planowania

Uważam to za interesujące, ponieważ chociaż nazywane są heurystykami, stosowane zasady określają rodzaj wymaganego algorytmu i struktury danych, dlatego należy wiedzieć o stosach i kolejkach.

1. Najmniej ostatnio używane mogą być realizowane na wiele sposobów. Realizacja lista opartych na jądrze Linux.
2. Inne możliwości to First In First Out, najmniej często używane i Round Robin.
3. Odmiana FIFO została wykorzystana przez system VAX / VMS.
4. Algorytm zegara autorstwa Richarda Carra jest używany do zastępowania ramek stron w systemie Linux.
5. Procesor Intel i860 używał zasady losowej wymiany.
6. Adaptacyjna zastępcza pamięć podręczna jest używana w niektórych kontrolerach pamięci masowej IBM i była używana w PostgreSQL, choć tylko na krótko z powodu obaw patentowych .
7. Algorytm algorytm bliźniaków , który został omówiony przez Knutha TAOCP obj. 1 jest używany w jądrze Linuksa, a współdzielący jemalloc używany przez FreeBSD i na Facebooku .

Podstawowe narzędzia w systemach * nix

1. grep i awk implementują konstrukcję NFA Thompson-McNaughton-Yamada z wyrażeń regularnych, która najwyraźniej nawet przewyższa implementację Perla .
2. tsort implementuje sortowanie topologiczne.
3. fgrep implementuje algorytm dopasowywania ciągów Aho-Corasick.
4. GNU grep , implementuje algorytm Boyera-Moore'a według autora Mike'a Haertela.
5. crypt (1) na Uniksie zaimplementował wariant algorytmu szyfrowania w maszynie Enigma.
6. Unix diff zaimplementowany przez Douga McIllroya, oparty na prototypie napisanym wspólnie z Jamesem Huntem, działa lepiej niż standardowy algorytm programowania dynamicznego używany do obliczania odległości Levenshteina. Wersja Linux oblicza najkrótszą odległość edycji.

Algorytmy kryptograficzne

To może być bardzo długa lista. Algorytmy kryptograficzne są zaimplementowane we wszystkich programach, które mogą wykonywać bezpieczną komunikację lub transakcje.

1. Drzewa merkle , a zwłaszcza wariant Tiger Tree Hash, zostały wykorzystane w aplikacjach peer-to-peer, takich jak GTK Gnutella i LimeWire .
2. MD5 służy do zapewnienia sumy kontrolnej dla pakietów oprogramowania i służy do sprawdzania integralności w systemach * nix ( implementacja Linux ), a także jest obsługiwany w systemach Windows i OS X.
3. OpenSSL implementuje wiele algorytmów kryptograficznych, w tym AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES itp.

Kompilatory

1. Analiza LALR jest implementowana przez yacc i bison.
2. Algorytmy dominujące są używane w większości optymalizujących kompilatorów opartych na formie SSA.
3. Lex i Flex kompilują wyrażenia regularne do NFA.

Kompresja i przetwarzanie obrazu

1. Algorytmy Lempel-Ziv dla formatu obrazu GIF są implementowane w programach do obróbki obrazów, poczynając od konwersji narzędzia * nix do złożonych programów.
2. Kodowanie długości przebiegu służy do generowania plików PCX (używanych przez oryginalny program Paintbrush), skompresowanych plików BMP i plików TIFF.
3. Kompresja falkowa jest podstawą formatu JPEG 2000, więc wszystkie aparaty cyfrowe, które wytwarzają pliki JPEG 2000, będą wdrażały ten algorytm.
4. Korekcja błędów Reed-Solomon jest zaimplementowana w jądrze Linuksa , napędach CD, czytnikach kodów kreskowych i została połączona ze splotem do transmisji obrazu z Voyager.

Uczenie się klauzul opartych na konflikcie

Od 2000 r. Czas działania solverów SAT w testach wzorcowych w przemyśle (zwykle z branży sprzętowej, choć wykorzystywane są również inne źródła) zmniejszał się niemal wykładniczo każdego roku. Bardzo ważną częścią tego rozwoju jest algorytm uczenia się klauzul opartych na konflikcie , który łączy algorytm propagacji ograniczeń logicznych w oryginalnym artykule Davisa Logemanna i Lovelanda z techniką uczenia klauzul, która powstała w programowaniu ograniczeń i badaniach sztucznej inteligencji. W przypadku konkretnego modelowania przemysłowego SAT jest uważany za łatwy problem ( patrz ta dyskusja)). Dla mnie jest to jeden z największych sukcesów w ostatnim czasie, ponieważ łączy postępy algorytmiczne rozłożone na kilka lat, sprytne pomysły inżynieryjne, ocenę eksperymentalną i wspólny wysiłek na rzecz rozwiązania problemu. Artykuł CACM autorstwa Malika i Zhanga jest dobrą lekturą. Algorytmu tego naucza się na wielu uniwersytetach (uczęszczałem na cztery tam, gdzie tak było), ale zazwyczaj w klasie logiki lub metod formalnych.

Zastosowań solverów SAT jest wiele. IBM, Intel i wiele innych firm mają własne implementacje solvera SAT. Menedżer pakietów w OpenSUSE wykorzystuje również solver SAT.

PageRank jest jednym z najbardziej znanych takich algorytmów. Opracowany przez współzałożyciela Google'a, Larry'ego Page'a i współautorów, stanowił podstawę oryginalnej wyszukiwarki Google i jest powszechnie uznawany za pomoc w osiągnięciu lepszych wyników wyszukiwania niż ich konkurenci w tym czasie.

Wyobrażamy sobie „losowego surfera” zaczynającego się na jakiejś stronie internetowej i wielokrotnie klikającego losowy link, aby przenieść go na nową stronę. Pytanie brzmi: „Jaką część czasu surfer spędza na każdej stronie?” Im więcej czasu internauta spędza na stronie, tym ważniejsza jest strona.

$M$

$M^k \pi_0$$k$$\pi_0$$M$

Chciałbym wspomnieć o szeroko stosowanym oprogramowaniu CPLEX (lub podobnym) wdrożeniu metody / algorytmu Simplex do rozwiązywania problemów programowania liniowego. Jest to (?) Najczęściej stosowany algorytm w badaniach ekonomicznych i operacyjnych.

„Gdyby wziąć dane statystyczne, który problem matematyczny zużywa większość czasu komputerowego na świecie, wówczas (nie licząc problemów z obsługą baz danych, takich jak sortowanie i wyszukiwanie) odpowiedzią byłoby prawdopodobnie programowanie liniowe. ” (L. Lovász, nowy algorytm programowania liniowego - lepszy czy gorszy niż metoda simpleks? Math. Intelligencer 2 (3) (1979/80) 141-146.)

Algorytm Simplex ma również duży wpływ w teorii; patrz na przykład (wielomianowa) hipoteza Hirscha .

Chyba typowy licencjat lub doktorat. klasa w algorytmach zajmuje się algorytmem Simplex (w tym podstawowymi algorytmami z algebry liniowej, takimi jak metoda eliminacji Gaussa).

(Inne udane algorytmy, w tym Quicksort do sortowania, są wymienione w Algorytmach z książki ).

Jak rozumiem, Narodowy Program Dopasowywania Mieszkańców przez długi czas był po prostu prostym zastosowaniem algorytmu Gale-Shapleya do rozwiązania problemu stabilnego małżeństwa. Od tego czasu został nieco zaktualizowany, aby obsługiwać dodatkowe szczegóły, takie jak zadania małżeńskie (inaczej „problem dwóch ciał”) itp.

Jeśli obejmujesz także przedmioty na poziomie doktoranckim, wiele (większość?) Programów studiów podyplomowych CS zawiera kurs teorii kodowania. Jeśli masz kurs teorii kodowania, na pewno obejmiesz kod Reeda-Solomona, który jest integralną częścią działania płyt kompaktowych i kodowania Huffmana, który jest używany w formatach JPEG, MP3 i ZIP. W zależności od orientacji kursu możesz również obejmować Lempel-Ziv, który jest używany w formacie GIF. Osobiście dostałem Lempel-Ziv na studiach licencjackich z algorytmów, ale myślę, że może to być nietypowe.

GNU grep to narzędzie wiersza poleceń do wyszukiwania jednego lub więcej plików wejściowych w poszukiwaniu linii zawierających dopasowanie do określonego wzorca. Powszechnie wiadomo, że grep jest bardzo szybki! Oto cytat jego autora Mike'a Haertela (zaczerpnięty stąd ):

GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the
final letter of the target string, and uses a lookup table to tell it how far
ahead it can skip in the input whenever it finds a non-matching character.

Mówiąc bardziej ogólnie, nagroda Kanellakis przyznawana jest przez ACM za dokładnie takie odkrycia teoretyczne, które miały duży wpływ na praktykę.

nagroda 2012 jest przyznawana za haszowanie wrażliwe na lokalizację , które stało się powszechną metodą zmniejszania wymiarów w eksploracji danych w przypadku problemów bliskich sąsiadów (i jest stosunkowo łatwa do nauczenia - przynajmniej sam algorytm)

$\varepsilon$

Oto niektóre przykłady przemysłowych zastosowań tych struktur danych:

• System Sawzall firmy Google do analizy danych nieustrukturyzowanych wykorzystuje Count Sketch do implementacji funkcji „najbardziej popularnych przedmiotów”
• System „strumieniowej bazy danych” AT&T Gigascope do monitorowania ruchu sieciowego implementuje szkic CountMin.
• System monitorowania ciągłego (CMON) Sprint implementuje CountMin.

Tutaj jest także strona, która zbiera informacje o aplikacjach CountMin.

Jeśli chodzi o nauczanie, wiem, że podstawowe techniki szkicowania są nauczane w Princeton na licencjackich dyskretnych kursach matematycznych. Nauczyłem się szkicu CountMin na moim pierwszym kursie algorytmów. W każdym razie analiza CountMin jest prostsza niż analiza dla prawie każdego innego randomizowanego algorytmu: jest to proste zastosowanie niezależności parowej i nierówności Markowa. Jeśli nie jest to standardowy materiał w większości kursów algorytmicznych, myślę, że dzieje się tak z przyczyn historycznych.

W ostatniej dekadzie zastosowano algorytmy w celu zwiększenia liczby (i jakości, jak sądzę?) Przeszczepów nerek za pomocą różnych programów dopasowywania dawcy nerki. Mam problem ze znalezieniem najnowszych wiadomości na ten temat, ale oto co najmniej kilka wskazówek:

• Jeszcze w 2007 roku Sojusz na rzecz Parzystej Darowizny korzystał z algorytmu Abrahama, Bluma i Sandholma . Być może nadal go używają, ale nie mogłem się dowiedzieć, szukając online. Chociaż ten algorytm prawie na pewno nie jest objęty „standardowymi” kursami, łączy w sobie kilka podstawowych pomysłów, które z pewnością są nauczane na takich kursach, aby zapewnić wystarczająco dobry algorytm dla problemu, który jest generalnie NP-zupełny (wariant Cycle Cover ).

• Krajowy rejestr nerek stosuje również niektóre standardowe algorytmy, w tym (w pewnym momencie) CPLEX. Doprowadziło to do faktycznie wykonanego łańcucha przeszczepów łączącego 60 osób .

Jest to jeden z moich ulubionych przykładów nie tylko sukcesu algorytmów, ale także znaczenia badania algorytmów dla problemów z NP-zupełnym. Mogą dosłownie ocalić życie i już to zrobili!

Algorytm Viterbiego, który jest nadal szeroko stosowany w rozpoznawaniu mowy i wielu innych aplikacjach: http://en.wikipedia.org/wiki/Viterbi_algorytm Sam algorytm jest podstawowym programowaniem dynamicznym.

Z Wikipedii: „Algorytm Viterbi został zaproponowany przez Andrew Viterbiego w 1967 r. Jako algorytm dekodowania kodów splotowych za pośrednictwem hałaśliwych cyfrowych łączy komunikacyjnych. [1] Algorytm znalazł uniwersalne zastosowanie w dekodowaniu kodów splotowych używanych zarówno w cyfrowej komórkowej sieci CDMA, jak i GSM, modemy telefoniczne, satelita, komunikacja kosmiczna i bezprzewodowe sieci LAN 802.11. Jest teraz powszechnie stosowany w rozpoznawaniu mowy, syntezie mowy, wykrywaniu słów kluczowych, lingwistyce obliczeniowej i bioinformatyce. Na przykład w mowie-na-tekście (mowa rozpoznawanie), sygnał akustyczny jest traktowany jako obserwowana sekwencja zdarzeń, a ciąg tekstu jest uważany za „ukrytą przyczynę” sygnału akustycznego. Algorytm Viterbi znajduje najbardziej prawdopodobny ciąg tekstu, biorąc pod uwagę sygnał akustyczny. ”

1. A * jest używany w wielu osobistych urządzeniach nawigacyjnych (zwanych również urządzeniami GPS)
2. * Jest bardzo dobrze zdefiniowany i został wdrożony dość prosto.
3. A * nie jest całkowicie trywialne, ale nie wymaga doktoratu. zrozumieć to.

Sprawdź projekt BonnTools Jensa Vgena dla Chip Design. http://www.or.uni-bonn.de/~vygen/projects.html Słyszałem kilka rozmów na ten temat, a także przeglądałem niektóre z ich artykułów. Wykorzystują losowe zaokrąglanie w stylu Raghavana-Thompsona, a także multiplikatywną metodę aktualizacji masy do rozwiązywania wielkoskalowych płyt LP o dużej wydajności. Jednak, jak każdy duży projekt, muszą oni również wykonać pewne prace inżynieryjne, ale metodologia opiera się w dużej mierze na dobrze znanych algorytmach.

Zabawne, że widziałem to pytanie dzisiaj, a następnie przypadkowo kliknąłem ten link na wiele zastosowań transformacji Fouriera .

Jestem raczej zaskoczony, że przy wszystkich powyższych fantazyjnych algorytmach nikt nie wspomniał o czcigodnej rodzinie algorytmów kompresji Lempel-Ziv (wynalezionej w 1977/78).

1. Są one używane wszędzie - od tekstu do obrazu w celu przetwarzania strumieniowego. Jest całkiem możliwe, że LZ * jest jedną z najczęściej używanych rodzin algorytmów.
2. Kompresja słownikowa była znaczącym przełomem w teorii kompresji i stanowczym odejściem od stylu Shannon-Fano.
3. Algorytmy w rodzinie są dość proste i łatwe do zrozumienia.

Aktualizacja

Najwyraźniej zostało już wspomniane krótko.

rozkład wartości pojedynczej (SVD) ma silny związek z analizą czynników statystycznych lub analizą głównych składników i jest zrozumiały w ramach algebry liniowej lub klasy statystycznej licencjackich oraz ma wiele ważnych właściwości teoretycznych. odgrywa również rolę w algorytmach kompresji obrazu. odegrał kluczowy element w zwycięskich pracach w konkursie o nagrodę Netflix o wartości 1 miliona USD (jeden z największych na świecie konkursów analiz danych w historii) i jest teraz wdrażany na ich stronie w celu przewidywania ocen użytkowników. wiadomo również, że jest silnie związana z samoorganizującymi się sieciami neuronowymi w języku hebrajskim, które wywodzą się z teorii biologicznej.

istnieje również związek z opadaniem gradientu, które jest szeroko stosowane w uczeniu maszynowym i sztucznych sieciach neuronowych oraz jako bardzo powszechnie stosowana technika optymalizacji, w której przypadek metoda Newtona jest podstawową formą 2D. istnieje algorytm opadania gradientu w celu uzyskania SVD.

Znalezienie ścieżki Eulera jest podstawą zestawu genomu - zadanie często wykonywane podczas pracy z pełnymi genomami (w bioinformatyce, medycynie, medycynie sądowej, ekologii).

AKTUALIZACJA Zapomniałem tego oczywistego: UPS, FedEx, USPS muszą co noc rozwiązywać duże problemy z podróżującym sprzedawcą. Oszczędza dużo czasu i pieniędzy, aby wysłać kierowców na optymalną trasę.

AKTUALIZACJA2 Problem z ustawieniem wierzchołka przy minimalnym sprzężeniu zwrotnym jest używany do rozwiązywania zakleszczeń w wielu systemach operacyjnych.

Podoba mi się ten system do ratowania maksymalnej liczby żyć w Wielkiej Brytanii z przeszczepami nerki, oparty na algorytmach maksymalnego dopasowania: sparowane i altruistyczne dawstwo nerki . Łączą osoby potrzebujące nerek, które mają niepasującego przyjaciela / krewnego gotowego oddać, z innymi ludźmi w tej samej sytuacji, w maksymalny sposób. Następnie w dniu darowizny wszyscy dawcy przekazują darowizny w tym samym czasie, po czym następuje szybki transport nerek do kraju do odbiorców.

ta stosunkowo nowa książka jest warta rozważenia jako kompletnej / szczegółowej odpowiedzi na pytanie w wygodnej, rozszerzonej / zebranej formie i która mogłaby być wykorzystana jako materiał uzupełniający dla klasy algorytmów. [niektóre z nich zostały już wspomniane; znaczące samo nakładanie się jest godne uwagi.]

• Dziewięć algorytmów, które zmieniły przyszłość: genialne pomysły, które napędzają dzisiejsze komputery MacCormick

  • indeksowanie wyszukiwarek
  • PageRank
  • kryptografia klucza publicznego
  • kody korekcji błędów
  • rozpoznawanie wzorców
  • kompresja danych
  • bazy danych
  • Podpisy cyfrowe
  • teoria obliczalności

• kolejne odniesienie nieco podobne, ale bardziej teoretyczne, The Best of the 20th Century: Redakcja wymienia Top 10 algorytmów Cipra / SIAM.

  • Metoda Monte Carlo
  • algorytm simpleks
  • Iteracja podprzestrzeni Kryłowa
  • obliczanie macierzy dekompozycji
  • Kompilator Fortran
  • Algorytm macierzy QR
  • szybkie sortowanie
  • FFT
  • wykrywanie relacji liczb całkowitych
  • szybki algorytm wielobiegunowy

Wyszukiwanie ciągów Knutha-Morrisa-Pratta jest szeroko stosowane, specyficzne i nauczane w licencjackich / magisterskich CS.

Myśląc o bardzo podstawowych algorytmach

1. Generatory liczb losowych można znaleźć wszędzie, a konkretnie we wszystkich grach.
2. Bazy danych składają się z wielu algorytmów, w tym B +, skrótów, kolejek priorytetowych, wyrażeń regularnych, kryptografii, sortowania itp. Mój przyjaciel twierdzi, że SGBD są na szczycie łańcucha żywnościowego.
3. Sortowanie jest używane wszędzie, na przykład w programie Excel. Jest używany przez cały czas w prawdziwym życiu, ale zwykle ludzie używają algorytmów ad-hoc
4. Wszędzie używane są bity parzystości
5. Kodowanie Huffmana jest w oprogramowaniu do kompresji i transmisji
6. Stosy (LIFO) są używane wszędzie. Wewnątrz języków programowania, w procesorach itp.

Miło jest pokazać, że pojawiają się w prawdziwym życiu:

A. Wiele grup korzysta z pewnego rodzaju algorytmu pokrywającego drzewa, dzieląc listy telefoniczne w sposób hierarchiczny między ludźmi B. Samochody na skrzyżowaniu zwykle używają algorytmu round-robin (w sposób dobrowolny) C. Większość miejsc, jako banki i szpital, organizuj swoich klientów w algorytmie FIFO

Fascynujący problem algorytmiczny powstaje w medycznym zastosowaniu tomografii komputerowej. W tomografii komputerowej (CT) ciało jest narażone na promieniowanie rentgenowskie pod różnymi kątami. Na jednym końcu skanera znajdują się nadajniki rentgenowskie, a na drugim końcu czujniki. Z takiej serii skanów rekonstruowany jest obraz, który lekarz może zbadać!

Przesączono powrotem występ algorytm jest podstawą do rekonstrukcji obrazu z zestawu skanowania. Algorytm ten jest właściwie formą problemu aproksymacyjnego, w którym „sygnał” jest próbkowany poniżej częstotliwości Nyquista. Algorytm ten jest stosowany „za kulisami” we wszystkich szpitalach, a podstawowa filtrowana projekcja wsteczna wykorzystuje matematykę licencjacką, taką jak transformaty Fouriera, w celu uzyskania twierdzenia plastra Fouriera .

Przykład FFT

Kiedyś pomogłem przenieść algorytm FFT na inny język systemu.

Algorytm został wykorzystany do określenia przerw linii w koncentrycznym dostarczaniu telewizji kablowej / internetu / telefonu. Zasadniczo technik poprosiłby o przesłanie sygnału do skrzynki klienta, jednocześnie wyświetlałby statystyki w czasie rzeczywistym dla konkretnego klienta, takie jak QoS, dB, ... Technik mógłby użyć dane i wykres do ustalenia w odległości kilku stóp między domem a słupem, w którym istniała częściowa przerwa (lub wielokrotne przerwy, jak mi powiedziano).

Jak wspomniano powyżej, FFT jest szeroko stosowany, ale był to jeden z bardziej rażących i oczywistych (pod względem przyczyny i sposobu), jaki widziałem w praktyce.

Przepraszam, że musiałem utrzymać go na wysokim poziomie.

Algorytm liniowy Bresenhama jest najbardziej użytecznym algorytmem, z jakim się zetknąłem. Łatwy do zrozumienia Ive wykorzystał go do wielu zastosowań, od rysowania linii, przez skomplikowany spliner do silnika odlewania 3d, aż po złożony renderer wielokątów, a także do złożonych animacji i skalowania.

Konfigurowalne planowanie trasy (Daniel Delling, Andrew V. Goldberg, Thomas Pajor i Renato F. Werneck) http://research.microsoft.com/apps/pubs/default.aspx?id=145688

uprawnienia Bing Maps: http://www.bing.com/blogs/site_blogs/b/maps/archive/2012/01/05/bing-maps-new-routing-engine.aspx

Wikipedia ma przyzwoitą kolekcję algorytmów / aplikacji sklasyfikowanych mniej więcej na liście . Microsoft zapewnia cytowane artykuły, ale bez wyraźnego wyjaśnienia dziedziny informatyki ani aplikacji. Istnieje również lista chronologiczna z różnych konferencji CS _http: //jeffhuang.com/best_paper_awards.html_ opracowana przez prof. Huanga.

Spectral Clustering to elegancki algorytm grupowania, znany jako znormalizowany algorytm cięcia wprowadzony przez Jianbo Shi i Jitendra Malik do segmentacji obrazów. Został również dobrze opracowany w aplikacjach klastrowania danych, stanowiąc dobre skrzyżowanie obu społeczności.

dwa inne ulubione przykłady mocno zakorzenione w informatyce, ale być może łatwo przeoczone przez teoretyków abstrakcjonizmu, którzy przeszli ogromny / transformacyjny postęp i od kilku do kilkudziesięciu lat odnieśli znaczący wpływ na życie codzienne / praktyczne. już całe pokolenie dorastało, nie znając świata bez nich. w zasadzie kategoria modelowania i symulacji .

• algorytmy symulacji fizyki . głównie przy użyciu praw Newtona, ale przy użyciu innych praw (takich jak dynamika płynów). stosowany w wielu różnych aplikacjach, od aplikacji inżynierskich, gier wideo, a czasem filmów. odpowiada to również za znaczną poprawę bezpieczeństwa, wydajności lub niezawodności np. samochodów i samolotów poprzez poddanie wirtualnych / testowych projektów symulowanym obciążeniom. główny pokrewny bieżący obszar badań z zakresu bioinformatyki o ogromnych implikacjach w biologii, np. projektowanie leków, zapobieganie chorobom itp .: składanie białek / przewidywanie struktury . zauważ także, że tegoroczna Nagroda Nobla w dziedzinie chemii została przyznana za symulację chemiczną Karplusowi, Levittowi i Warshel. algorytmy fizyki są bardzo zaangażowane w bezpieczeństwo / testowanie broni jądrowej np. w laboratoriach Los Alamos.

• algorytmy raytracing / CGI . Zaczęło się to jako temat badawczy zaledwie kilka dekad temu [kolega uzyskał tytuł magistra w dziedzinie pisania algorytmów śledzenia promieniowaniem CS], ale stał się bardzo stosowany np. w grach i biznesie filmowym, osiągając niezwykły poziom wiarygodności, który jest odpowiedzialny za duże ilości efekty specjalne w filmach. branże te zainwestowały dosłownie miliardy dolarów i wykorzystują te algorytmy, a całe duże korporacje opierają się na ich wykorzystaniu, np . Pixar . technika początkowo stosowana głównie w filmach scifi, obecnie jest tak rozpowszechniona, że ​​jest rutynowo stosowana nawet w filmach „typowych”. na przykład ostatnio The Great Gatsby polegał w dużej mierze na efektach CGI, aby rysować przekonujące lub stylizowane środowiska, retuszować film / postacie itp.

Rosetta Code wymienia stosowane algorytmy według Programming Task (692) i Programming Language (518) z Semantic MediaWiki.

być może w tym miejscu wspomniano o wszystkich głównych / preferowanych algorytmach będących przedmiotem zainteresowania tej grupy odbiorców. jednak kilka innych zasługuje na wzmiankę o kompletności. w tym przypadku istotna jest analiza tego, co uważa się za znaczący algorytm.

w dziedzinie CS i IT wydaje się, że dawno temu zauważono w AI zjawisko zwane „przemieszczaniem słupków bramki” . jest to zjawisko psychologiczne, w którym pole rozwija się stosunkowo szybko, ale ludzie szybko mentalnie dostosowują się do „nowej normalności” i przyjmują rzeczywiste lub nawet przełomowe postępy jako przyziemne lub nietypowe z perspektywy czasu, po dokonaniu, tj. zlekceważeniu lub zminimalizowaniu. jest to dobrze ujęte w tym pytaniu, ponieważ algorytmy przechodzą od badań i rozwoju do „wdrażania”. cytując autora pytania w późniejszych komentarzach:

W rzeczywistości niewielka część całego napisanego kodu implementuje wszystko, co jest interesujące z algorytmicznego punktu widzenia.

ale jest to problematyczne i zasadniczo redefinicja słowa „algorytm” zorientowana na TCS. przypuszczalnie interesujące algorytmy są zaawansowane. Czy to oznacza, że ​​jeśli problem zostanie zredukowany do zaawansowanego algorytmu, nie będzie już „interesujący”? a „zaawansowany” jest wyraźnie ruchomym celem. istnieje sposób na wąskie lub szerokie zdefiniowanie „algorytmów” . wydaje się, że definicja TCS zmienia się w kontekście, ale zauważ, że nawet w TCS istnieje tendencja do szerokiej definicji, np. w tak zwanej „soczewce algorytmicznej” .

czasami najbardziej wszechobecne algorytmy są również najbardziej pomijane! Internet i WWW to duże środowisko / niemal ekologia dla algorytmów. wciąż stosunkowo młody, mający zaledwie około 2 dekad (wynaleziony w 1991 r.), urósł gwałtownie i gwałtownie w krótkim czasie. Rozwój stron WWW prawdopodobnie nawet wyprzedził słynną wykładniczą ustawę Moores.

Internet / WWW są obsługiwane przez wiele wyrafinowanych algorytmów. Internet ma złożone algorytmy routingu wbudowane w routery (ponownie zasilające korporacje o wartości wielu miliardów dolarów, takie jak Cisco). istnieje pewna zaawansowana teoria, np. w algorytmach routingu . Algorytmy te były przedmiotem nowych, zaawansowanych / nowatorskich badań przed dziesięcioleciami, jednak obecnie są tak dopracowane i dobrze zrozumiane, że są nieco niewidoczne.

nie powinniśmy tak szybko zapominać, że kilkadziesiąt lat temu wiodący badacze nie byli nawet pewni, czy świat Internetu działa, czy był możliwy (obserwowany we wczesnych badaniach nad przełączaniem pakietów, radykalnie nowy wzorzec projektowy w tym czasie odchodzący od wcześniejszego przełączania obwodów), oraz jeszcze kilka lat temu istniały obawy, że w pewnym momencie nie uda się go skalować i zacznie zawodzić z powodu przytłaczających skoków głośności.

wykorzystuje również zaawansowane wykrywanie / korekcję błędów . internet prawdopodobnie największy, najbardziej odporny na uszkodzenia systemu kiedykolwiek zbudowany przez ludzi, wciąż rośnie.

następnie istnieje silny argument, aby algorytmy zasilające WWW były zaawansowane. Serwery HTTP i WWW są wysoce dostrojone / zoptymalizowane, a także wykorzystują zaawansowane protokoły bezpieczeństwa / szyfrowania (HTTPS). logika renderowania strony internetowej stała się niezwykle zaawansowana w HTML5 i CSS3 , wraz z językiem programowania Javascript .

stosunkowo nowy CSS ma różne zasady podobne do programowania OOP, takie jak możliwość ponownego użycia i dziedziczenie. Mówiąc o składzie, TeX jest ważnym, wewnętrznie złożonym naukowym systemem składu (nie różnym od języka programowania) wymyślonym przez Knutha, który można teraz renderować na stronach internetowych (i jest używany w setkach tysięcy artykułów naukowych lub więcej).

kolejny stosunkowo nowy obszar algorytmów budowanych w Internecie, wciąż powstających, opartych na zbiorowej inteligencji . Oprogramowanie Stackexchange jest przykładem zaawansowanego systemu zbiorowej inteligencji. sieci społecznościowe wykazują także kluczowe cechy inteligencji zbiorowej, a funkcje są ciągle dodawane w celu zwiększenia tej inteligencji (na przykład „polubienia” na Facebooku mają zaledwie kilka lat). dziedzina systemów oceny opiera się na algorytmach filtrowania współpracującego i wciąż ewoluuje w oparciu o nowe badania i zastosowania.

w skrócie, wszystkie rewolucyjne sukcesy przekształcające codzienne ludzkie doświadczenia faktycznie znacznie wykraczają poza zwykłe „cele terenowe”. jak podaje tytuł pytania, wszystkie zastosowane podstawowe algorytmy . teraz tak wszechobecny i niewidoczny, że może być czymś w rodzaju IT-wyrażenia, „części hydrauliki”.

Niezwykle skutecznym algorytmem (sprzętowym) jest reset po włączeniu zasilania.

Bez systemu, w którym komputer znajduje się w znanym stanie po podłączeniu zasilania, nic innego nie dzieje się dobrze .

Po zresetowaniu po włączeniu działa wszystko, co ma w sobie procesor, niezależnie od tego, czy jest wbudowane, czy nie.

Następnym razem, gdy będziesz przy wodopoju dla programistów i informatyków, podnieś szklankę sody wiśniowej do resetu po włączeniu.