15 kõige olulisemat algoritmi, mis aitasid määratleda matemaatikat, arvutit ja füüsikat

Algoritmid mida me kõik kasutame kogu aeg oma otseste teadmistega või ilma. Neil on rakendusi mitmel erineval erialal alates matemaatika ja Füüsika loomulikult arvutamine.

Selgub algoritmid on pika ja kuulsa ajalooga, mis ulatub tagasi iidsetesse Mesopotaamia aegadesse. Kuid milliseid neist keerukatest arvutusprotsessidest võiks pidada üheks kõige olulisemaks?

Need on 15 kõige tõenäolisemat kandidaati.

SEOTUD: KUIDAS ALGORITMID JUHTIVAD MAAILMAS, kus me elame

Algoritmide lühiajalugu

Algoritmid on eelnevalt määratletud iseseisvad käskude komplektid, mis on mõeldud mitmesuguste funktsioonide täitmiseks, ja need on olnud kasutusel kauem, kui võite arvata. Alates iidsest Babülonist kuni tänapäevani on algoritmid olnud meie ühiskonna oluline tunnus juba aastatuhandeid.

Kõige esimesteks näideteks olid lihtsad algoritmid, mida iidsed kasutasid muuhulgas oma terade ja kariloomade jälgimiseks. Nende kiuste ja vormistatud arvsüsteemi tulekuga saavutati muid tehnoloogilisi ja kontseptuaalseid hüppeid, sealhulgas leiutati abacus, algebra ja muutujate mõiste.

Vana-Kreeka mõtlejad, nagu Euclid, Archimedes ja Eratosthenes, kasutaksid varajasi algoritme selleks, et teha kindlaks näiteks erinevate arvude suurim ühine jagaja, ligikaudne Pi ja arvutada algarvud.

Aja jooksul tekitaksid sellised feats hindamissüsteemide koostamisel sümbolid ja reeglid.

Arvatakse, et mõiste „algoritm” pärineb 9. sajandi Pärsia astronoomilt ja matemaatikult Muhammad ibn Mūsā al-Khwārizmī. Seda meest peetakse laialdaselt isikuks, kes tutvustas läänemaailma arvusüsteemis esimest korda kümnendpositsioneerimist.

Tema perekonnanimi, ladina keeles Algorithmi, muutuks tööülesannete täitmise arvutuste teostamise juhiste sünonüümiks.

Samuti on talle omistatud kõigi aegade esimese süsteemi väljatöötamine lineaar- ja ruutvõrrandite lahendamiseks. Algoritmide algsed, ehkki algelised vormid, nn algoritmid, peeti reegliteks hind-araabia numbritega aritmeetiliste arvutuste tegemiseks.

Järgmine suurim hüpe algoritmide ajaloos toimus 1800ndatel suure George Boole tööga. Paljud teised liigutavad algoritme 19. ja 20. sajandil edasi, sealhulgas Giuseppe Peano ja Ada Lovelace, kui nimetada vaid mõnda.

Kuid algoritmid saaksid Emil Posti ja Alan Turingi 1930. aastatel tehtud tööde põhjal olulise täienduse, mis annaks lõpuks moodsa arvuti loomise. Miski ei oleks jälle endine.

Millised on kõige olulisemad algoritmid?

Nii et siin on pikema jututa mõned näited kõigi aegade olulisematest algoritmidest. Nimekiri sisaldab nii iidseid näiteid kui ka ajaloo kõige murrangulisemaid arvutiteaduse algoritme ja programmeerimisalgoritme.

Järgmine algoritmide loetelu pole kaugeltki ammendav ega ole mingis konkreetses järjekorras.

1. Babüloonia algoritmid on vanimad, mis kunagi leitud

Looja: Teadmata

Selle loomisel: umbes 1600 eKr

Selle mõju / mõju maailmale: Maailma esimene teadaolev algoritm

Kuigi Egiptuses on mõningaid tõendeid varajase korrutamise algoritmide kohta (umbes 2000–1700 eKr) on vanim kirjalik algoritm üldtunnustatud, kuna see on leitud Babüloonia savitahvlite komplektist, mis pärineb umbes 1800-1600 eKr.

Nende tegelik tähendus tuli ilmsiks alles ümberringi 1972, kui arvutiteadlane ja matemaatik Donald E. Knuth avaldas mitmesugused kiilkirja matemaatiliste tahvlite esimesed ingliskeelsed tõlked.

Siin on mõned väljavõtted temast 1972 käsikiri, mis selgitab neid varaseid algoritme:

"Babüloonia tahvlites kirjeldatud arvutused ei ole pelgalt konkreetsete üksikute probleemide lahendused, vaid on tegelikult üldised protseduurid terve klassi probleemide lahendamiseks." - "Muistsete Babüloonia algoritmide" leheküljed 672–673.

Näib, et tabletid on olnud ka kasutusjuhendi varajane vorm:

"Pange tähele ka stereotüüpset lõppu" See on protseduur ", mis on tavaliselt tabeli iga osa lõpus. Seega on Babüloonia protseduurid ehtsad algoritmid ja võime babüloonlasi kiita selle eest, et nad on välja töötanud kena viisi näiteks algoritmi määratlemisel ... "-" Muistsete Babüloonia algoritmide "leheküljed 672–673.

2. Eukleidese algoritm on kasutusel ka tänapäeval

Looja: Eukleides

Selle loomisel: 300 eKr

Selle mõju / mõju maailmale: Eukleidese algoritm on üks varasemaid algoritme, mis kunagi loodud ja mõningate muudatustega kasutatakse seda arvutites ka tänapäeval.

Eukleidese algoritm on protseduur, mida kasutatakse kahe positiivse täisarvu suurima ühisjaguri (GCD) leidmiseks. Esmakordselt kirjeldas seda Euclid oma käsikirjas Elemendid ümber kirjutatud 300 eKr.

See on väga efektiivne arvutus, mida arvutid mingil või teisel kujul kasutavad ka praegu.

Eukleidese algoritm nõuab tulemuste saavutamiseks järjestikust jagamist ja jääkide arvutamist. Seda saab kõige paremini kirjeldada näite abil:

Mis on 56 ja 12 GCD?

1. samm - jagage suurem väiksema arvuga: -

56/12 = 4 (ülejäänud 8)

2. samm - jagage jagaja eelmise sammu jäägiga: -

12/8 = 1 (ülejäänud 4)

3. samm - jätkake 2. sammu, kuni ühtegi järelejäänud osa pole jäänud (antud juhul on see lihtne kolmeastmeline protsess): -

8/4 = 2 (ülejäänud pole)

Sellisel juhul on GCD 4.

Seda algoritmi kasutatakse laialdaselt harilike murdude vähendamiseks madalaimatele terminitele ja arenenud matemaatika rakendustes, näiteks täisarvuliste lahendite leidmiseks lineaarvõrranditele.

3. Eratosthenese sõel on iidne, lihtne algoritm

Looja: Eratosthenes

Selle loomisel: 200 eKr

Selle mõju / mõju maailmale: Eratosthenese sõel on laialt aktsepteeritud kui üks iidsemaid algoritme läbi aegade. See võimaldab teil leida kõik algarvud etteantud arvude tabelist (nii palju kui soovite lisada).

Selle tegemiseks leiate kõik arvud, mis on suuremad kui 2, seejärel tõmmake need arvud, mis jagunevad 2-ga. Seejärel teete sama ka ületamata arvude puhul, mis on suuremad kui 3, jne ad infinitum kuni kõik liitarvud (mitte algarvud) on kriipsutatud.

4. Boole'i ​​(binaarne) algebra oli teabeajastu alus

Looja: George Boole

Selle loomisel: 1847

Selle mõju / mõju maailmale: Seda algoritmi peetakse laialdaselt tänapäevase arvutikodeerimise aluseks. Seda kasutatakse tänapäevalgi, eriti arvutiskeemides.

Mõiste Boolean võib teile olla tuttav matemaatikast, loogikast ja arvutikodeerimisest.

Boole'i ​​algebra on algebra haru, milles muutuja saab kunagi olla tõene või vale - nn tõeväärtused (tavaliselt binaarne 1 või 0). Esmakordselt leiutas selle George Boole 1845 töö Mõtteseaduste uurimine.

Boole'i ​​algebra on laialdaselt krediteeritud kui infoajastu alus.

5. Ada Lovelace'i algoritm oli esimene arvutiprogramm

Looja: Ada Lovelace

Selle loomisel: 1842

Selle mõju / mõju maailmale: Seda algoritmi peetakse laialdaselt esimeseks arvutiprogrammiks.

Ada Lovelace veetis aasta suurema osa ühe Charles Babbage'i loengu (mille Itaalia insener oli prantsuse keelde ümber kirjutanud) inglise keelde tõlkimisega. Selle protsessi käigus lisas ta kohusetundlikult omapoolsed täiendavad selgitavad märkused.

Tema märkmed olid tähistatud tähega A - G, kusjuures viimane kirjeldas "analüütilise mootori" algoritmi Bernoulli arvude arvutamiseks. Märkus G on nüüd laialt aktsepteeritud kui esimene registreeritud näide arvutikoodist - see on temast esimene arvutiprogrammeerija.

Mootorit ei ehitatud kunagi ja seega ei katsetatud tema algoritmi elu jooksul. Tema tööd avastati uuesti aastal 1953 kui tema märkmed uuesti avaldati.

6. Kiire Fourieri teisendus murrab signaale sagedustesse

Looja: Carl Gauss, Joseph Fourier, James Cooley ja John Tukey

Selle loomisel: 1802, 1822, 1965

Selle mõju / mõju maailmale: Seda algoritmi kasutatakse signaali jaotamiseks sagedusteks, mis selle moodustavad - umbes nagu muusikalist akordi võib väljendada selles sisalduva noodi sagedustes või helikõrgusetes.

Kiire Fourieri teisenduse (FTT) algoritm võib jälgida selle päritolu Carl Gaussini, kes lõi selle esmalt asteroidide trajektooride arvutamiseks. Valemit laiendas hiljem Joseph Fourier aastal 1822.

Kuid algoritmi moodsama ja laialdasemalt kasutatava vormi lõid ja avaldasid James Cooley ja John Tukey aastal 1965. See versioon on rakendusmatemaatikas kõige kaugeleulatuvam algoritm ja see muutis signaalitöötlust.

"FFT tugineb jagamise ja vallutamise strateegiale, et vähendada näiliselt O (N2) kodutööd O (N log N) hulluseks. Kuid erinevalt Quicksortist ei ole rakendus esmapilgul mõistlik ja vähem kui lihtne. See on ise andis arvutiteadusele tõuke arvutusprobleemide ja algoritmide omase keerukuse uurimiseks. " - Barry A. Cipra.

7. Google'i järjestusalgoritm (PageRank) võiks olla kõige enam kasutatav algoritm

Looja: Larry Page (peamiselt) ja Sergey Brin

Selle loomisel: 1996

Selle mõju / mõju maailmale: PageRank on vaieldamatult tänapäeval maailmas enimkasutatav algoritm. Muidugi on see Google'i otsingumootori lehtede järjestuse alus.

Huvitav on see, et PageRank on nime saanud pigem Larry Pagei järgi, kui see sõna otseses mõttes tähendab veebilehtede asetust. See pole ainus algoritm, mida Google tänapäeval oma otsingutulemustes lehtede tellimiseks kasutab, kuid see on neist vanim ja tuntuim.

PageRanki mõtlesid välja Larry Page ja Sergey Brin, kui nad õppisid Stanfordi ülikoolis osana uut tüüpi otsingumootorit käsitlevast uurimisprojektist.

Peamine eeldus oli lehtede järjestamine nende suhtelise tähtsuse või populaarsuse alusel. Üldiselt on hierarhias kõrgemal paiknevatel lehtedel rohkem tagasilinke või linke neile.

PageRanki algoritmi annab järgmine valem:

PR (A) = (1-d) + d (PR (T1) / C (T1) + ... + PR (Tn) / C (Tn))

kus:

• PR (A) on A lehe PageRank,
• PR (Ti) on lehtede Ti leht, mis viitab lehele A,
• C (Ti) on väljuvate linkide arv lehel Ti ja;
• d on summutustegur, mille saab seada vahemikku 0 kuni 1.

Näeme, et see algoritm ei reasta veebisaite tervikuna, vaid järjestab iga lehekülje eraldi. Seda võib võrrelda ka „püramiidskeemiga, kus konkreetne leht on järjestatud rekursiivselt sõltuvalt sellest, millised teised lehed sellele lingivad.

PageRank on viimastel aastatel poolehoiust välja jäänud, kuid seda kasutatakse endiselt Google'i muude algoritmide üldise komplekti osana.

8. Los Alamoses kasutati Monte Carlo meetodit (Metropolis Algorithm)

Looja: John von Neumann, Stan Ulam ja Nick Metropolis

Selle loomisel: 1946

Selle mõju / mõju maailmale: Seda kasutati Los Alamose koodsõnana stohhastiliste simulatsioonide jaoks, mida rakendati pärast Teist maailmasõda paremate aatomipommide ehitamiseks.

Monte Carlo meetod on määratletud järgmiselt: "Monte Carlo on kunst, mille järgi saab ootusi lähendada simuleeritud juhuslike muutujate funktsiooni valimi keskmise abil."

Seda olulist algoritmi kasutatakse juhusliku protsessi jäljendamise abil lahenduste ligikaudseks muutmiseks juhitamatu keerukusega arvulistele probleemidele. Tulemuse saamiseks tugineb see korduvale juhuslikule valimisele - juhuslikkuse abil lahendatakse põhimõtteliselt deterministlikud probleemid.

Algoritmi kasutatakse laialdaselt füüsikalistes ja matemaatilistes probleemides ning see on kõige kasulikum siis, kui muude lähenemisviiside kasutamine on keeruline või võimatu.

Monte Carlo meetodeid kasutatakse peamiselt kolmes probleemiklassis: optimeerimine, arvuline integreerimine ja tõenäosusjaotusest ammutatavate tõmmete genereerimine.

9. Lineaarse programmeerimise simplex-meetod võeti tööstuses laialdaselt kasutusele

Looja: George Dantzig

Selle loomisel: 1947

Selle mõju / mõju maailmale: Lineaarse programmeerimise simplex-meetod on läbi aegade üks edukamaid algoritme. Seda kasutati laialdaselt tööstusmaailmas või mõnes muus olukorras, kus majanduslik ellujäämine sõltub võimest maksimeerida eelarve tõhusust ja / või muid piiranguid.

George Dantzigi poolt 1947. aastal välja töötatud algoritmist on saanud üks ajaloo kõige levinumaid, hoolimata asjaolust, et enamik reaalsetest probleemidest on oma olemuselt väga harva lineaarsed.

See pakub aga lihtsat ja elegantset viisi probleemidele lahenduste leidmiseks. Mõned on märkinud, et eksponentsiaalsed viivitused võivad seda mõjutada, kuid on muidu väga tõhus - tavaliselt kulub 2m (kus m on võrdsuspiirangute arv) 3-nim kordused lõpule viia.

See töötab süstemaatilise strateegia abil, et luua ja kinnitada kandidaatide tipplahendusi lineaarse programmi raames. Igal iteratsioonil valib algoritm muutuja, mis teeb suurima muudatuse minimaalse kuluga lahenduse suunas.

Seejärel asendab see muutuja ühte selle muutujat, mis seda kõige drastilisemalt piirab, nihutades seeläbi simplex-meetodi lahuse komplekti teisele osale ja lõpliku lahenduse poole.

10. Krõlovi alamruumi iteratsioonimeetodeid kasutatakse tänapäevalgi

Looja (kui on teada):Magnus Hestenes, Eduard Stiefel ja Cornelius Lanczos

Selle loomisel (kui see on teada): 1950

Selle mõju / mõju maailmale: Krõlovi alamruumi iteratsioonimeetod on üks kümnest olulisimast arvumeetodite klassist maailmas.

Krõlovi alamruumi iteratsioonimeetodid on algoritmide kogum, mis töötati välja Riikliku Standardibüroo Numbrianalüüsi Instituudis 1950. aastatel. Nad käsitlevad petlikult lihtsat ülesannet võrrandite lahendamiseks kujul Ax = b.

Muidugi pole see nii lihtne, A on tohutu n-n-maatriks. Seetõttu tähendab see, et algebraline vastus x = b / A pole arvutamiseks just lastemäng.

"Iteratiivsed meetodid - näiteks vormi Kx võrrandite lahendamine_i + 1 = Kx_i + b - lihtsama maatriksiga K, mis on ideaaljuhul A-le lähedal - viivad Krõlovi alamruumide uurimiseni. Vene matemaatiku Nikolai Krõlovi nime saanud Krrylovi alamruumid ulatuvad algse “ülejäänud” vektori r suhtes rakendatud maatriksi mõjude järgi₀ = b - kirves₀. "- Barry A. Cipra.

"Lanczos leidis sellise alamruumi jaoks ortogonaalse aluse genereerimise suurepärase viisi, kui maatriks on sümmeetriline. Hestenes ja Stiefel pakkusid süsteemidele, mis on nii sümmeetrilised kui ka positiivsed, veelgi niftier meetodi, mida nimetatakse konjugaatgradiendi meetodiks."

Neid algoritme on viimase 50 aasta jooksul pidevalt muudetud. Nende praegused mittesümmeetriliste süsteemide kordused hõlmavad üldistatud minimaalse jääkmeetodi (GMRES) ja Bikonjugate'i gradientstabiliseeritud meetodit (Bi-CGSTAB).

11. Kalmani filter sobib suurepäraselt tuleviku ennustamiseks, omamoodi

Looja:Rudolf E. Kálmán

Selle loomisel (kui see on teada): 1958-1961

Selle mõju / mõju maailmale: Kalmani filter on üldine ja võimas vahend teabe ühendamiseks ebakindluse korral.

Kalmani filtreerimine (aka lineaarne ruuthinnang (LQE)) on algoritm, mis kasutab üheaegse tõenäosusjaotuse kaudu tundmatute muutujate hinnangu saamiseks ajas jälgitavaid mõõteseeriaid, sealhulgas statistilist müra.

Teisisõnu, see aitab teil haritud aimdusi selle kohta, mida süsteem tõenäoliselt mõistliku mõistuse piires edasi teeb. Kalmani filtrid sobivad suurepäraselt olukordadeks, kus süsteemid muutuvad pidevalt.

Selle algoritmi teine ​​tore asi on see, et see on "mälu" valguses. Edenemiseks on vaja ainult eelmise sammu tulemust, mis muudab selle väga kiireks ja sobib ideaalselt probleemide reaalajas lahendamiseks.

12. QR-algoritmid omaväärtuste arvutamiseks on osutunud uskumatult kasulikuks

Looja: John G. F. Francis ja Vera N. Kublanovskaja iseseisvalt

Selle loomisel: 1950. aastate lõpp

Selle mõju / mõju maailmale: QR-algoritm lihtsustab oluliselt omaväärtuste (mis on kõige olulisemad maatriksitega seotud arvud) arvutusi. Pärast selle väljatöötamist muutus nende tüütute numbrite arvutamine pigem rutiinseks ülesandeks kui tohutuks ja töömahukaks protsessiks.

QR-algoritm ehk omaväärtuse algoritm on arvulises lineaarses algebras oluline. Lisaks omaväärtuste kiire arvutamise võimaldamisele aitab see ka omavektorite töötlemist antud maatriksis.

Selle põhiülesanne on teostada QR lagundamine, kirjutada maatriks ortogonaalse maatriksi ja ülemise kolmnurkse maatriksi korrutisena ning korrutada tegurid vastupidises järjekorras ja korrata.

13. Fortrani optimeeriva kompilaatori sõnastus võib olla kõige olulisem sündmus programmeerimisajaloos

Looja: John Backus (ja IBMi meeskond)

Selle loomisel: 1957

Selle mõju / mõju maailmale: Arvatavasti kõige olulisem algoritm / sündmus arvutiprogrammeerimisel.

Fortrani töötas 1950. aastate lõpus välja John Backus ja tema meeskond IBM-is. See võimaldas teadlastel ja teistel kasutajatel arvutile tegelikult öelda, mida nad tahtsid, ilma et oleks vaja masinakoodi üksikasjadesse kinni jääda. . Fortrani optimeerimiskompilaator on tänapäevaste standardite järgi tagasihoidlik ja sisaldab "23 500 koostekeele juhist - varajane kompilaator oli siiski võimeline üllatavalt keerukate arvutuste tegemiseks". - Barry A. Cipra.

Backus mõistis selle tähtsust maailmale hiljem, 1998. aastal, kui ta meenutas Fortran I, II ja III ajalugu IEEE arvutianalüüsi aastaraamat. Koostaja Backuse sõnul "tootis sellise efektiivsusega koodi, et selle väljund ehmataks seda uurinud programmeerijad ära".

14. Quicksort aitab suurepäraselt asju sortida

Looja: Tony Hoare ettevõttest Elliott Brothers, Limited, London

Selle loomisel: 1962

Selle mõju / mõju maailmale: See võimaldas kiiresti ja tõhusalt sortida loendeid tähestiku ja numbri järgi.

Kindla hulga asjade sorteerimine kas tähestikulises või numbrilises järjestuses oli alati olnud töömahukas ja tüütu ülesanne. Tony Hoare sai hakkama, aastal 1962, et luua algoritm selle ülesande kiireks täitmiseks.

Tema Quicksorti algoritm kasutas rekursiivset strateegiat lahenduse kiireks saavutamiseks “jagamiseks ja vallutamiseks”. See osutuks kaks kuni kolm korda kiiremaks, kui tema peamised konkurendid ühendavad sorteerimise ja hulga sordi.

See töötab nii, et valitakse üks element pivotiks. Seejärel sorteeritakse kõik teised pöördetapi suhtes "suuremate" ja "väiksemate" elementide hunnikuteks.

Seejärel korratakse seda protsessi igas kuhjas.

"Kuigi kõigi N (N - 1) / 2 võrdluste tegemisel on võimalik takerduda (eriti kui kasutate pivotina esimest sorteeritud loendi üksust!), Töötab Quicksort keskmiselt O (N log N) efektiivsusega . " - Barry A. Cipra.

Selle algoritmi lihtsus ja elegants pälvisid omal ajal palju kiitust ja muutsid selle 1990ndate lõpus arvutusliku keerukusega plakatilapseks.

15. JPEG ja muud andmete tihendamise algoritmid on uskumatult kasulikud

Looja: Ühine fotoekspertide rühm, IBM, Mitsubishi Electric, AT&T, Canon Inc., ITU-T uuringurühm 16

Selle loomisel: 1992

Selle mõju / mõju maailmale: Andmete tihendamise algoritme, nagu JPEG, MP3, zip või MPEG-2, kasutatakse kogu maailmas laialdaselt. Enamik neist on saanud tegelikult nende konkreetse rakenduse jaoks. Nad on aja jooksul muutnud arvutisüsteemid odavamaks ja tõhusamaks.

Ühte kindlat andmete tihendamise algoritmi on raske välja tuua, kuna nende väärtus või olulisus sõltub failide rakendustest. Need on tänapäeval nii laialt levinud, et neid kasutatakse alati, kui laadite faili arvutisse, mängite muusikat või videomänge, voogesitate videoid, kasutate andmebaasi või suhtlete pilvega.

Vaata videot: AWS re:Invent 2019: REPEAT 1 Amazon DynamoDB deep dive: Advanced design patterns DAT403-R1 (Juuni 2022).