Wdrożone podstawowe algorytmy

307

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.

Manu
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Bjørn Kjos-Hanssen

Odpowiedzi:

473

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 drzewawykorzystywane 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 .
Istnieją również takie struktury danych i algorytmy w kodzie strony trzeciej zawartym w kodzie Chromium.

  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.

Vijay D.
źródło
5
@HuckBennett, CDCL to algorytm parametryzowany przez heurystykę, ale sam nie jest heurystyką. Ma najgorsze zachowanie wykładnicze, ale pokazanie tego nie jest trywialne. Co więcej, nie jesteśmy w stanie wykazać się lepszymi wynikami i jest to najlepsze, co możemy zrobić w praktyce, więc uważam, że wszyscy informatycy powinni o tym wiedzieć! Jeśli chodzi o LRU, FIFO itp., Są one heurystyczne, ale, podobnie jak w przypadku ARC, mogą wymagać sprytnych algorytmów lub struktur danych do wdrożenia.
Vijay D
9
Czy taki komentarz nie miałby zastosowania do Simplex: początkowo niezrozumiały, a później wykazany jako wykładniczy, ale działa w praktyce, a znacznie później wykazał, że ma wielomianową wygładzoną złożoność? CDCL jest interesujący dla analizy algorytmów, ponieważ musisz przejść przez złożoność dowodu, aby uzyskać rodziny formuł wykazujących najgorsze zachowanie przypadków, a także aby pokazać, że może być wykładniczo bardziej zwięzły niż niektóre warianty rozdzielczości. Istnieją różne rozszerzenia, takie jak łamanie symetrii i techniki autarkiczne, dla których taka analiza jest nadal otwarta.
Vijay D
28
To jest skarb dla studenta
neo1691
2
@EmanueleViola, dodałem jeszcze kilka przykładów. Wpis jest już długi, więc nie chcę go przedłużać. Może powinieneś zadać nowe pytanie dotyczące implementacji filtrów Dijkstra, Simplex, Bloom jako części prawdziwego systemu, takiego jak Linux, Chrome, serwer WWW itp. Myślę, że bardziej prawdopodobne jest uzyskanie dobrych odpowiedzi, jeśli jesteś konkretny.
Vijay D,
4
Nowości hakerów i programowanie.
Vijay D
40

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

Mkπ0kπ0M

Huck Bennett
źródło
7
Nie sądzę, że jest to typowy materiał algorytmów.
Manu,
14
Nawiasem mówiąc, po raz pierwszy dowiedziałem się o PageRank w klasie algorytmów. Myślę, że profesor wybrał to, ponieważ był to dobry przykład „algorytmów stosowanych w praktyce”. Jeśli ograniczysz przykłady do materiału typu „pierwsza połowa CLRS”, lista przykładów będzie albo za długa, albo za trywialna - szybkie sortowanie, drzewa B i algorytm Dijkstry są wszechobecne.
Huck Bennett,
2
Uczymy PageRank studentów.
Aaron Roth,
6
Uczę go także studentom (zarówno w wymaganej klasie algorytmów, jak i bardziej specjalistycznych algorytmów grafowych do wyboru).
David Eppstein,
2
Poznałem PageRank jako licencjat z wyboru.
Vijay D
33

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

vb le
źródło
„badania ekonomiczne i operacyjne” nie są wystarczająco szczegółowe. CPLEX nie jest przykładem, którego szukałem, ponieważ jest to tylko implementacja algorytmu; byłoby inaczej, gdyby powiedzmy, że kompilator gcc zastosował metodę simpleks.
Manu,
12
Myślę, że „problemy z programowaniem liniowym” są wystarczająco szczegółowe, gdy mówimy o gospodarce i OR. Przez CPLEX miałem na myśli algorytm implementacji.
wb.
16
„Obecnie większość dużych firm stosuje programowanie liniowe do wyceny produktów i zarządzania łańcuchami dostaw. Firmy transportowe używają go do wyboru najtańszego sposobu konsolidacji, koordynacji i kierowania wysyłek wielu produktów od globalnie dystrybuowanych dostawców na odległe rynki z zastrzeżeniem ograniczeń przepustowości. Ropa naftowa przemysł wykorzystuje go do eksploracji, mieszania, planowania i dystrybucji produkcji. Przemysł żelazny i stalowy wykorzystuje go do oceny rud żelaza, eksploracji dodatku pieców koksowniczych i wybranych produktów ... ” news.stanford.edu/news/2005/may25/ dantzigobit-052505.html
Sasho Nikolov
Dzięki. Ale uważam ten cytat za bardzo niejasny. Myślę, że gdybym powiedział, że przed klasą studentów, połowa z nich zasnąłaby ;-) Byłoby inaczej, gdybyśmy powiedzieli coś takiego: UPS używa LP do wysyłania paczek w następujący sposób ... Nie mówię takich przykładów są łatwe do znalezienia, ale biorąc pod uwagę, że „większość dużych firm korzysta z LP”, mam nadzieję, że przynajmniej wskażemy jedną .
Manu,
10
Od samego początku, od 2007 roku LAX (lotnisko) korzysta z oprogramowania do rozwiązywania gier Stackelberg do planowania bezpieczeństwa. Rozwiązywanie dużych płyt LP jest częścią całości, patrz np . Teamcore.usc.edu/ARMOR-LAX . Poza tym zapytałbym kogoś z twojego działu badań operacyjnych: zwykle mieliby mnóstwo wojennych historii o korzystaniu z LP w prawdziwym życiu
Sasho Nikolov
30

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.

mum
źródło
Nie jestem pewien, czy stabilne małżeństwo jest typowym algorytmem.
Manu,
16
Jest w książce Tardos and Kleinberg Al Algorytmy Design, a także w Randomized Algorytmy Motwani, i obie książki są szeroko stosowane. Stabilne małżeństwo może nie być powszechnie nauczane na kursach algorytmicznych, ale na pewno jest nauczane w wielu z nich.
Sasho Nikolov,
10
Szybko odkrywa, że wykazał się CS70 Berkeley , MIT 6,042 , UMD za CMSC451 , etc ...
mhum
1
Co ciekawe, po dodaniu zadań małżeńskich problem staje się NP-zupełny: arxiv.org/abs/1308.4534 . Jednak w praktyce nie wydaje się to powodować zbyt dużego problemu: en.wikipedia.org/wiki/…
Joshua Grochow
2
@EmanueleViola, choć może nie być tradycyjnie omawiany, jego włączenie do książki Kleinberg / Tardos sprawiło, że stała się bardziej popularna (i jeśli nie powinna!)
Suresh Venkat
24

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.

mum
źródło
1
I dostałem wykład na temat kodowania Huffmana jako licencjata, który był wymagany do projektu.
Brian S,
Huffman jest w jednym z pierwszych rozdziałów CLRS, więc zdecydowanie powinien się zakwalifikować
Sasho Nikolov
21

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.
Dai Le
źródło
19

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)

Suresh Venkat
źródło
Myślę, że można się tego nauczyć, ale nie uczy się go powszechnie.
Manu,
3
Niefortunne, ale prawdziwe. Jednak warianty LSH (takie jak szkic Count-min i krewni) zaczynają pojawiać się na kursach „dużych danych” lub „eksploracji danych”. Uczę filtrów Bloom na przykład w mojej klasie algorytmów.
Suresh Venkat,
Jako osobiste doświadczenie, LSH nie skalowało się dla nas na przykładzie „dużych zbiorów danych” (100mln pozycji).
lynxoid
1
@lynxoid to osobna dyskusja / pytanie :). Istnieje wystarczająco dużo przykładów, gdzie ma pracować, że myślę, że jest to istotne dla tej konkretnej kwestii.
Suresh Venkat
18

ε

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.

Sasho Nikolov
źródło
1
Świetne przykłady (choć nie całkiem podstawowe jądro).
Manu
16

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!

Joshua Grochow
źródło
Do handlu grami planszowymi używana jest również prostsza wersja tych algorytmów: okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html
Radu GRIGore
15

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

Grigorij Jarosławcew
źródło
13
  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.
MSalters
źródło
A * jest również często nauczany w projektowaniu gier. Nie sądzę, aby współczesne gry 3D generalnie używały A * do nawigacji NPC, ale gry 2D / izometryczne, a także starsze gry, wykorzystują algorytm.
Brian S,
@BrianS Czy znasz przykłady algorytmów odnajdywania ścieżek używanych w grach 3D, w szczególności wrogich postaci niezależnych w grach (takich jak np. Strzelanka) Pamiętam, jak czytałem coś takiego ... dzieląc mapę na sektory heksagonalne i używam tego jako węzła zamiast kwadratów , a to pozwoliło na płynniejszy ruch.
Goodwine,
@ Goodwine, przepraszam, nie mam żadnych rzeczywistych przykładów algorytmów wyszukiwania ścieżek w grach 3D. Moje osobiste doświadczenia związane były ze środowiskami podobnymi do „kostki” (mapa zbudowana z kostek, na których stoją postacie - w zasadzie 2D, pomimo renderowania 3D) i sztucznymi sztucznymi inteligencjami używanymi do testowania postaci graczy.
Brian S
12

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.

Chandra Chekuri
źródło
Zobaczę, ale to nie brzmi jak typowy algorytm.
Manu,
8
Hmm, losowe zaokrąglanie jest zwykle nauczane na kursach algorytmów doktoranckich, prawda?
Chandra Chekuri,
2
Dlaczego właśnie losowe zaokrąglanie? Sanjeev Arora, Elad Hazan i Satyen Kale uważają, że nawet metoda aktualizacji wag mnogich jest na tyle podstawowa, że ​​można ją uczyć na poziomie UG :) „Uważamy, że nasz algorytm meta i jego analiza są na tyle proste i przydatne, że powinny być postrzegane jako podstawowe narzędzie uczy wszystkich studentów algorytmów wraz z podziałem i podbijaniem, programowaniem dynamicznym, losowym próbkowaniem itp. ” (por. cs.princeton.edu/~arora/pubs/MWsurvey.pdf ).
Jagadish
10

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.

dąb
źródło
10

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.

vzn
źródło
10

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.

ryxoid
źródło
Czy na pewno TSP jest problemem, który firmy kurierskie próbują rozwiązać? Myślałem, że większym praktycznym wyzwaniem był plecak i inne problemy z pakowaniem.
András Salamon
Przydziały dla kierowców zmieniają się codziennie (tzn. Pracownik UPS nie musi codziennie odwiedzać tego samego domu), więc trasy muszą być aktualizowane codziennie. To nie jest czysty TSP - istnieją dodatkowe ograniczenia, takie jak ulice jednokierunkowe, brak zawracania, dostarczanie paczek po jednej stronie ulicy, ale nie po drugiej.
lynxoid
Jestem pewien, że pakowanie jest również ważne.
lynxoid
9

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.

Alnitak
źródło
8

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

vzn
źródło
Drugi numer źródłowy pochodzi z stycznia / lutego 2000 roku wydania Computing in Science & Engineering, wspólnej publikacji American Institute of Physics i IEEE Computer Society. opracowane przez redaktorów zaproszonych Jacka Dongarrę z University of Tennessee i Oak Ridge National Laboratory oraz Francisa Sullivana z Center for Computing Sciences w Institute for Defense
Analyzes
7

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

Darth Egregious
źródło
2
Byłoby dobrze, gdybyś mógł wskazać konkretne zastosowanie. Coś jak MS Word używa KMP.
Manu,
6

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

użytkownik19461
źródło
4
Sortowanie nie jest algorytmem. Jest to zadanie, czyli coś, co chcesz wykonać, dla którego musisz zaprojektować (lub w praktyce wybrać) algorytm.
David Richerby
Nie wydaje się, aby były to konkretne przykłady wymagane w pytaniu.
Kaveh
SGBD == RDBMS FYI dla tych, którzy nie wiedzieli.
Autodidact
6

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 .

Leeor
źródło
6

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.

ClericGunem
źródło
5

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.

TimRing
źródło
2

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.

Ravi Kiran
źródło
-2

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.

vzn
źródło
-3

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

Wes Turner
źródło
W jaki sposób jest to przykład „podstawowych algorytmów ... stosowanych w komercyjnym, rządowym lub powszechnie używanym oprogramowaniu / sprzęcie”?
David Richerby,
Przydałoby się odsyłanie do implementacji każdego z doskonałych algorytmów wymienionych w innych odpowiedziach tutaj na URI Wikipedii / DBpedii. Dla wszystkich tych algorytmów nie ma identyfikatorów URI Wikipedii / DBpedii; ale są strony z kodem Rosetty.
Wes Turner
bigocheatsheet.com wymienia również złożoność Big-O i linki do artykułów Wikipedii dla kilku algorytmów.
Wes Turner
Pytanie dotyczy przykładów podstawowych algorytmów stosowanych w znaczących programach. „Oto strona internetowa z algorytmami zaimplementowanymi w milionach języków” w ogóle nie odpowiada na to pytanie. W rzeczywistości jest to dokładne przeciwieństwo tego, czego szuka pytanie.
David Richerby
Mimo to przydatne odniesienie kontekstowe.
Wes Turner
-5

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

vzn
źródło
można do tego dodać wiele cytatów. Oto jeden zacząć: DARPA i rewolucja Internet przez Waldrop
vzn
kolejne odniesienie do optymalizacji internetu, biografia Danny'ego Lewina , współzałożyciela akamai, „geniusza, który przekształcił internet”
13:13
-8

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.

Zaraz
źródło
5
Resetowanie po włączeniu nie jest algorytmem. Jest to zadanie, czyli coś, co chcesz wykonać, dla którego musisz zaprojektować algorytm.
David Richerby