Algoritm

En normal algoritm (algoritm i författarens skrift) av Markov är ett system av successiva tillämpningar av substitutioner som implementerar vissa procedurer för att erhålla nya ord från basen, byggda från tecknen i ett visst alfabet. Som en Turing-maskin utför normala algoritmer inte beräkningarna själva: de utför bara ordtransformationer genom att ersätta bokstäver enligt givna regler [10] .

En normalt beräkningsbar funktion är en funktion som kan implementeras med en normal algoritm. Det vill säga en algoritm som omvandlar varje ord från uppsättningen av giltiga data för funktionen till dess initiala värden [11] ..

Skaparen av teorin om normala algoritmer A. A. Markov lade fram en hypotes, som kallades Markovs normaliseringsprincip:

För att hitta värdena för en funktion som ges i något alfabet, om och bara om det finns någon algoritm, när funktionen normalt är uppräknad.

Liksom teserna om Turing och kyrkan kan Markovs normaliseringsprincip inte bevisas med matematiska medel.

Stokastiska algoritmer

Ovanstående formella definition av algoritmen kan dock vara för strikt i vissa fall. Ibland finns det behov av att använda slumpvariabler [12] . En algoritm vars funktion inte bara bestäms av initialdata utan också av värden som erhålls från slumptalsgeneratorn kallas stokastisk (eller randomiserad, från den engelska  randomiserade algoritmen ) [13] . Stokastiska algoritmer är ofta mer effektiva än deterministiska, och i vissa fall det enda sättet att lösa ett problem [12] .

I praktiken, istället för en slumptalsgenerator , används en pseudoslumptalsgenerator .

Man bör dock skilja på stokastiska algoritmer och metoder som ger ett korrekt resultat med hög sannolikhet. Till skillnad från metoden ger algoritmen korrekta resultat även efter en lång löpning.

Vissa forskare medger möjligheten att den stokastiska algoritmen ger ett felaktigt resultat med en viss förutbestämd sannolikhet. Då kan stokastiska algoritmer delas in i två typer [14] :

• Algoritmer som Las Vegas ger alltid rätt resultat, men deras körtid är inte definierad.
• Algoritmer av typen Monte Carlo , till skillnad från de tidigare, kan ge felaktiga resultat med en känd sannolikhet.

Andra formaliseringar

För vissa uppgifter kan ovan nämnda formaliseringar göra det svårt att hitta lösningar och bedriva forskning. För att övervinna hinder utvecklades båda modifieringarna av de "klassiska" systemen, och nya modeller av algoritmen skapades. I synnerhet kan man nämna:

• multi-tape och icke-deterministiska Turing-maskiner;
• register och RAM-maskin  - en prototyp av moderna datorer och virtuella maskiner;
• finita och cellulära automater

Typer av algoritmer

Typerna av algoritmer som logiska och matematiska medel återspeglar de angivna komponenterna i mänsklig aktivitet och trender, och själva algoritmerna, beroende på målet, initiala förutsättningar för problemet och sätt att lösa det. Det bör betonas den grundläggande skillnaden mellan algoritmer av beräkningskaraktär som omvandlar en del indata till utdata (det är deras formalisering att de ovan nämnda Turing-, Post-, PAM-maskinerna, normala Markov-algoritmer och rekursiva funktioner) och interaktiva algoritmer (Turing har redan en C-maskin, från engelska  val  - ett val som väntar på extern påverkan, till skillnad från den klassiska A-maskinen, där alla initiala data ges innan beräkningens start och utdata inte är tillgängliga förrän i slutet av uträkningen). De senare är utformade för att interagera med något kontrollobjekt och är utformade för att säkerställa korrekt utfärdande av kontrollåtgärder beroende på den aktuella situationen, reflekterad av signalerna som kommer från kontrollobjektet [15] [16] . I vissa fall ger kontrollalgoritmen inte fullbordandet av arbetet alls (till exempel upprätthåller den en oändlig cykel av väntan på händelser som en lämplig reaktion utfärdas), trots detta, är den helt korrekt.

Algoritmer kan också särskiljas:

• Mekaniska algoritmer , eller på annat sätt deterministiska , stela (till exempel algoritmen för driften av en maskin, motor, etc.) - ställ in vissa åtgärder, beteckna dem i en enda och tillförlitlig sekvens, vilket ger ett otvetydigt nödvändigt eller önskat resultat om de processvillkor är uppfyllda uppgifter som algoritmen är utvecklad för.
• Flexibla algoritmer , såsom stokastiska, d.v.s. probabilistiska och heuristiska.
• En probabilistisk (stokastisk) algoritm ger ett program för att lösa ett problem på flera sätt eller sätt som leder till troligt resultat.
• Heuristisk algoritm (från det grekiska ordet " eureka ") - en algoritm som använder olika rimliga överväganden utan strikta motiveringar [17] .
• En linjär algoritm  är en uppsättning kommandon (instruktioner) som exekveras sekventiellt i tid efter varandra.
• En grenalgoritm  är en algoritm som innehåller minst ett villkor, vilket gör att en uppdelning i flera alternativa grenar av algoritmen kan utföras.
• En cyklisk algoritm  är en algoritm som involverar upprepad upprepning av samma åtgärd (samma operationer). De flesta av beräkningsmetoderna och uppräkningen av alternativ reduceras till cykliska algoritmer. En programcykel är en sekvens av kommandon (serier, cykelkropp) som kan utföras flera gånger.
• En extra ( underordnad ) algoritm ( procedur ) är en algoritm som tidigare utvecklats och helt användes vid algoritmiseringen av ett specifikt problem. I vissa fall, om det finns identiska sekvenser av instruktioner (kommandon) för olika data, urskiljs också en hjälpalgoritm för att förkorta posten. I alla stadier av förberedelserna för algoritmiseringen av problemet används den strukturella representationen av algoritmen i stor utsträckning.
• Strukturellt blockdiagram , grafdiagram av algoritmen  - en grafisk representation av algoritmen i form av ett diagram av block sammankopplade med pilar (övergångslinjer) - grafiska symboler, som var och en motsvarar ett steg i algoritmen. Inuti blocket ges en beskrivning av motsvarande åtgärd. Den grafiska representationen av algoritmen används ofta före programmering av uppgiften på grund av dess tydlighet, eftersom visuell uppfattning vanligtvis underlättar processen att skriva ett program, korrigera det i händelse av eventuella fel och förstå informationsbearbetningsprocessen. Du kan till och med stöta på ett sådant uttalande: "Utåt är algoritmen ett schema - en uppsättning rektanglar och andra symboler, inuti vilka det är skrivet, vad som beräknas, vad som matas in i maskinen och vad som utfärdas för utskrift och annat sätt att visa information."

Algoritmnumrering

Numreringen av algoritmer spelar en viktig roll i deras studier och analys [18] . Eftersom vilken algoritm som helst kan specificeras som ett ändligt ord (representerat som en ändlig sekvens av symboler i något alfabet), och mängden av alla ändliga ord i ett ändligt alfabet kan räknas , är mängden av alla algoritmer också räknebar. Detta innebär att det finns en en-till-en-mappning mellan mängden naturliga tal och mängden algoritmer, det vill säga möjligheten att tilldela varje algoritm ett nummer.

Numreringen av algoritmer är samtidigt numreringen av alla algoritmiskt beräknade funktioner, och vilken funktion som helst kan ha ett oändligt antal siffror.

Förekomsten av numrering gör det möjligt att arbeta med algoritmer på samma sätt som med siffror. Numrering är särskilt användbart vid studiet av algoritmer som fungerar med andra algoritmer.

Algoritmiskt olösliga problem

Formaliseringen av begreppet en algoritm gjorde det möjligt att undersöka förekomsten av problem som det inte finns några algoritmer för att hitta lösningar på. Därefter bevisades omöjligheten av algoritmisk beräkning av lösningar på ett antal problem, vilket gör det omöjligt att lösa dem på någon datorenhet. En funktion kallas beräkningsbar om det finns en Turing-maskin som beräknar värdet för alla element i funktionsdefinitionsuppsättningen. Om en sådan maskin inte finns, sägs funktionen vara icke-beräknbar. Funktionen kommer att anses vara icke-beräknbar även om det finns Turing-maskiner som kan beräkna ett värde för en delmängd av hela uppsättningen av ingångar [19] .  

Det fall då resultatet av utvärderingen av en funktion är det logiska uttrycket "sant" eller "falskt" (eller mängden {0, 1}) kallas ett problem som kan vara lösbart eller olösligt, beroende på funktionens beräkningsbarhet [19] .

Det är viktigt att exakt specificera den tillåtna uppsättningen av indata, eftersom ett problem kan vara lösbart för en uppsättning och olösligt för en annan.

Ett av de första problemen för vilka olöslighet bevisades är det stoppande problemet . Den är formulerad enligt följande:

Givet en beskrivning av programmet för en Turing-maskin, krävs det att avgöra om programmet avslutas inom en begränsad tid eller körs på obestämd tid givet viss input. [tjugo]

Beviset på olösligheten av det stoppande problemet är viktigt eftersom andra problem kan reduceras till det. Till exempel kan ett enkelt stoppproblem reduceras till ett stoppproblem på en tom linje (när du behöver bestämma för en given Turing-maskin om den kommer att stanna när den startas på en tom linje), och därigenom bevisa den senares oavgörbarhet. [19] .

Analys av algoritmer

Tillsammans med informationsteknologins spridning har risken för mjukvarufel ökat. Ett av sätten att undvika fel i algoritmer och deras implementeringar är att bevisa systemens korrekthet med matematiska medel.

Användningen av matematiska apparater för analys av algoritmer och deras implementeringar kallas formella metoder. Formella metoder innebär användning av formella specifikationer och vanligtvis en uppsättning verktyg för att analysera och bevisa specifikationernas egenskaper. Abstraktion från implementeringsdetaljer låter dig ställa in egenskaperna för systemet oberoende av dess implementering. Dessutom gör noggrannheten och unikheten hos matematiska påståenden det möjligt att undvika tvetydigheten och felaktigheten hos naturliga språk [21] .

Enligt Richard Maces hypotes är "fel undvikande bättre än feleliminering" [22] . Enligt Hoares gissning löser "bevis på program problemet med korrekthet, dokumentation och kompatibilitet" [23] . Beviset på riktigheten av program gör att vi kan avslöja deras egenskaper i förhållande till hela utbudet av indata. För att göra detta var begreppet korrekthet uppdelat i två typer:

• Delvis korrekt  - programmet ger rätt resultat för de fall det avslutas.
• Fullständig korrekthet  - programmet avslutas och ger rätt resultat för alla element från indataområdet.

Under bevis på korrekthet jämförs programmets text med specifikationen av det önskade förhållandet mellan in- och utdata. För bevis av Hoare-typ tar specifikationen formen av påståenden, som kallas förvillkor och eftervillkor. Tillsammans med själva programmet kallas de även för Hoare-trippeln . Dessa uttalanden är skrivna som

där P  är de förutsättningar som måste vara sanna innan programmet Q körs och S är de eftervillkor som är sanna efter att programmet avslutats.

Formella metoder har framgångsrikt tillämpats på en lång rad problem, särskilt: utveckling av elektroniska kretsar, artificiell intelligens, automatiska system på järnvägen, verifiering av mikroprocessorer , specifikation av standarder och specifikation och verifiering av program [24] .

Öppettider

Ett vanligt kriterium för att utvärdera algoritmer är körtiden och i vilken ordning körtiden växer beroende på mängden indata. [25]

För varje specifik uppgift utgör de ett visst antal, som kallas dess storlek. Till exempel kan storleken på uppgiften att beräkna produkten av matriser vara den största storleken på matrisfaktorer, för uppgifter på grafer kan storleken vara antalet grafkanter.

Den tid en algoritm spenderar som en funktion av uppgiftens storlek kallas tidskomplexiteten för den algoritmen T ( n ). Asymptotiken för beteendet hos denna funktion när problemets storlek ökar kallas asymptotisk tidskomplexitet, och notationen "O" stor används för att beteckna det . Till exempel, om en algoritm bearbetar indata i tiden cn² , där c  är någon konstant , då sägs tidskomplexiteten för en sådan algoritm vara O ( n² ).

Den asymptotiska komplexiteten är viktig eftersom den är en egenskap hos algoritmen och inte för dess speciella implementering: genom att "optimera" operationerna, utan att ändra algoritmen, kan endast den multiplikativa koefficienten c ändras , men inte asymptotiken. Som regel är det den asymptotiska komplexiteten som är huvudfaktorn som avgör storleken på de uppgifter som algoritmen klarar av att bearbeta.

Under utvecklingen av en algoritm försöker man ofta minska den asymptotiska tidskomplexiteten för de värsta fallen. I praktiken finns det fall då det räcker med en algoritm som "vanligtvis" går snabbt.

Grovt sett kan analysen av den genomsnittliga asymptotiska tidskomplexiteten delas in i två typer: analytisk och statistisk. Analysmetoden ger mer exakta resultat, men är svår att använda i praktiken. Men den statistiska metoden låter dig snabbt analysera komplexa problem [26] .

Följande tabell listar vanliga asymptotiska komplexiteter med kommentarer [27] .

Närvaro av initiala data och visst resultat

En algoritm är en exakt definierad instruktion, genom att tillämpa den sekventiellt på de initiala data, kan du få en lösning på problemet. För varje algoritm finns det en viss uppsättning objekt som kan användas som indata. Till exempel, i algoritmen för att dividera reella tal, kan utdelningen vara vad som helst, och divisorn kan inte vara lika med noll.

Algoritmen tjänar som regel inte till att lösa ett specifikt problem, utan en viss klass av problem. Så additionsalgoritmen är tillämplig på alla naturliga talpar. Detta uttrycker dess massegenskap, det vill säga förmågan att upprepade gånger tillämpa samma algoritm för alla uppgifter i samma klass.

För utveckling av algoritmer och program används algoritmisering  - processen för systematisk sammanställning av algoritmer för att lösa tillämpade problem. Algoritmisering anses vara ett obligatoriskt steg i processen att utveckla program och lösa problem på en dator. Det är för tillämpade algoritmer och program som determinism, effektivitet och masskaraktär, såväl som riktigheten av resultaten av att lösa de uppsatta uppgifterna, är fundamentalt viktiga.

En algoritm är en tydlig och exakt instruktion till utföraren att utföra en sekvens av åtgärder som syftar till att uppnå målet.

Representation av algoritmer

Algoritmnotationsformer:

• verbalt eller verbalt: i naturligt språk;
• i algoritmiskt språk: programmeringsspråk eller pseudokod ;
• i maskinkod (datorprocessorkod);
• i matematisk notation (se alternativen ovan);
• schematisk:
  • grafik (till exempel flödesscheman och DRAKON-diagram );
  • strukturgram ( Nassi-Schneiderman-diagram ).

Vanligtvis, till en början (på idénivå), beskrivs algoritmen i ord, men när den närmar sig implementering får den mer och mer formella konturer och formuleringar på ett språk som är förståeligt för utföraren (till exempel maskinkod ).

Algoritmers effektivitet

Även om definitionen av algoritmen bara kräver ett ändligt antal steg som krävs för att uppnå ett resultat, leder implementeringen av ett stort antal steg i praktiken till långvarig exekvering av program, och det finns vanligtvis andra begränsningar (på storleken på programmet, om tillåtna åtgärder). I detta avseende introduceras sådana begrepp som komplexiteten hos algoritmen ( tid , programstorlek, beräkningsteknik och andra).

För varje uppgift kan det finnas många algoritmer som leder till målet. Att öka effektiviteten av algoritmer är ett av datavetenskapens problem , sedan 1940-talet har man i samband med detta byggt ett antal mer asymptotiskt effektiva algoritmer för traditionella problem (till exempel snabba multiplikationsalgoritmer , Chudnovskys algoritm för beräknar antalet ).

Exempel

Euklids algoritm  är en effektiv metod för att beräkna den största gemensamma divisorn (gcd). Uppkallad efter den grekiske matematikern Euklid; en av de äldsta algoritmerna som fortfarande används [28] .

Beskrivs i "Början" av Euklid (cirka 300 f.Kr.), nämligen i böckerna VII och X. I den sjunde boken beskrivs en algoritm för heltal, och i den tionde - för segmentens längder.

Det finns flera varianter av algoritmen, nedan är en rekursiv version skriven i pseudokod :

GCD för nummer 1599 och 650:

Se även

• Metaalgorithm
• Auktion av algoritmer
• Lista över algoritmer
• Teori om algoritmer

Anteckningar

1. ↑ Semenov A. L. ALGORITHM . Stora ryska encyklopedin. Elektronisk version (2016). Hämtad 29 oktober 2018. Arkiverad från originalet 30 oktober 2018. (obestämd)
2. ↑ Kleene 1943 i Davis 1965: 274
3. ↑ Rosser 1939 i Davis 1965: 225
4. ↑ Knuth, 2006 , 1.1. Algoritmer.
5. ↑ Robert Andrew Wilson, Frank C. Keil. MIT Encyclopedia of the Cognitive Sciences . - MIT Press, 2001. - S. 11. - 1106 sid. — ISBN 9780262731447 . Arkiverad 17 november 2021 på Wayback Machine
6. ↑ (Igoshin, s. 317)
7. ↑ V. A. Uspensky: "Matematik är en humanitär vetenskap"  // Trinity Variant. - 2014. - 28 januari ( nr 2 (146) ). - S. 4-6 . Arkiverad från originalet den 27 november 2018. (ryska)
8. ↑ Grunderna: Turingmaskinen (med en tolk!) . Good Math, Bad Math (9 februari 2007). Arkiverad från originalet den 2 februari 2012. (obestämd)
9. ↑ (Igoshin, avsnitt 33)
10. ↑ Encyclopedia of Cybernetics , volym 2 , sid. 90-91.
11. ↑ (Igoshin, avsnitt 34)
12. ↑ 1 2 "Probabilistiska algoritmer ska inte förväxlas med metoder (som jag vägrar kalla algoritmer), som ger ett resultat som har stor sannolikhet att vara korrekt. Det är viktigt att en algoritm ger korrekta resultat (rabatterar mänskliga eller datorfel), även om detta händer efter mycket lång tid.” Henri Cohen. En kurs i beräkningsalgebraisk talteori  . - Springer-Verlag , 1996. - P.  2 . — ISBN 3-540-55640-0 .
13. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives't, Clifford Stein. Introduktion till  algoritmer . - 2:a. - MIT Press , 2001. - P. 531. - ISBN 0-262-03293-7 .
14. ↑ (Avsnitt 12, s. 12-22 i Atallah, 2010)
15. ↑ Dina Goldin, Peter Wegner. Ursprunget till Turing Thesis Myth , CS-04-14, oktober 2004
16. ↑ Interaktiv beräkning är mer kraftfull än icke-interaktiv Arkiverad 19 november 2015 på Wayback Machine , c2.com
17. ↑ M. Gary, D. Johnson, Datormaskiner och svåra problem, M .: Mir, 1982, C. 155.
18. ↑ (Igoshin, avsnitt 36)
19. ↑ 1 2 3 Peter Linz. En introduktion till formella språk och automater  . – Jones och Bartlett Publishers, 2000. - ISBN 0-7637-1422-4 .
20. ↑ beräkningsbarhet och komplexitet, Encyclopedia of data Science and Technology , Facts On File, 2009, ISBN 978-0-8160-6382-6 . 
21. ↑ (O'Regan, avsnitt 4.5)
22. ↑ (avsnitt 5.3.6 i Enders, 2003)
23. ↑ (avsnitt 5.3.7 i Enders, 2003)
24. ↑ (O'Regan, s. 119)
25. ↑ A. Aho , J. Hopcroft , J. Ullman . Konstruktion och analys av beräkningsalgoritmer = The Design and Analysis of Computer Algorithms . - M . : "Mir", 1979. (ryska)
26. ↑ (avsnitt 11 i Atallah, 2010)
27. ↑ (avsnitt 1 i Atallah, 2010)
28. ↑ Knuth D. Konsten att programmera , volym 2 : Seminumeriska algoritmer  . — 3:a. — Addison–Wesley , 1997. — ISBN 0201896842 .

Litteratur

• Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: Konstruktion och analys = Introduktion till algoritmer, tredje upplagan. - 3:a. - M. : "Williams" , 2013. - 1328 sid. - ISBN 978-5-8459-1794-2 .
• Donald Knuth . The Art of Computer Programming = The Art of Computer Programming, vol. 1. Grundläggande algoritmer. - 3:e upplagan - M . : "Williams" , 2006. - V. 1. Grundläggande algoritmer. - S. 720. - ISBN 0-201-89683-4 .
• Thomas H. Cormen. Algoritmer: Introduktionskurs = Algoritmer olåsta. - M. : "Williams" , 2014. - 208 sid. — ISBN 978-5-8459-1868-0 .
• Igoshin VI Matematisk logik och teori för algoritmer. - 2:a uppl., raderad .. - M . : Informationscentrum "Academy", 2008. - 448 sid. — ISBN 5-7695-1363-2 .

Länkar

• " Ordet "algoritm": ursprung och utveckling ", V. V. Shilov, Potential magazine  - en källa till historisk information.
• Om algoritmen  (otillgänglig länk från 2013-05-22 [3452 dagar] - historia ,  kopia ) i uppslagsverket "Jorden runt"

Ordböcker och uppslagsverk	Stor dansk Stor katalanska stor kines Stor norsk Stor ryss italienska runt världen Kroatisk Britannica (online) Brockhaus Treccani Moderna Ukraina
I bibliografiska kataloger BNE : XX527980 BNF : 119358199 GND : 4001183-5 J9U : 987007293927505171 LCCN : sh85003487 NDL : 00560337 NKC : ph114026