Algoritme

En normal algoritme (algoritme i forfatterens skrift) af Markov er et system af successive anvendelser af substitutioner, der implementerer visse procedurer til at opnå nye ord fra de grundlæggende, bygget ud fra tegnene i et bestemt alfabet. Som en Turing-maskine udfører normale algoritmer ikke selve beregningerne: de udfører kun ordtransformationer ved at erstatte bogstaver efter givne regler [10] .

En normalt beregnelig funktion er en funktion, der kan implementeres af en normal algoritme. Det vil sige en algoritme, der omdanner hvert ord fra funktionens gyldige datasæt til dets begyndelsesværdier [11] ..

Skaberen af ​​teorien om normale algoritmer A. A. Markov fremsatte en hypotese, som blev kaldt Markov-normaliseringsprincippet:

At finde værdierne af en funktion givet i et eller andet alfabet, hvis og kun hvis der er en eller anden algoritme, når funktionen normalt er talbar.

Ligesom teserne fra Turing og Church kan Markov-normaliseringsprincippet ikke bevises med matematiske midler.

Stokastiske algoritmer

Ovenstående formelle definition af algoritmen kan dog være for streng i nogle tilfælde. Nogle gange er der behov for at bruge stokastiske variable [12] . En algoritme, hvis drift bestemmes ikke kun af de indledende data, men også af værdierne opnået fra tilfældig talgeneratoren kaldes stokastisk (eller randomiseret, fra den engelske  randomiseret algoritme ) [13] . Stokastiske algoritmer er ofte mere effektive end deterministiske, og i nogle tilfælde den eneste måde at løse et problem på [12] .

I praksis bruges en pseudo-tilfældig talgenerator i stedet for en tilfældig talgenerator .

Man bør dog skelne mellem stokastiske algoritmer og metoder, der giver et korrekt resultat med stor sandsynlighed. I modsætning til metoden giver algoritmen korrekte resultater selv efter en lang løbetur.

Nogle forskere indrømmer muligheden for, at den stokastiske algoritme vil give et forkert resultat med en forudbestemt sandsynlighed. Derefter kan stokastiske algoritmer opdeles i to typer [14] :

• Algoritmer som Las Vegas giver altid det korrekte resultat, men deres køretid er ikke defineret.
• Monte Carlo type algoritmer , i modsætning til de foregående, kan give forkerte resultater med en kendt sandsynlighed.

Andre formaliseringer

For nogle opgaver kan ovennævnte formaliseringer gøre det svært at finde løsninger og udføre research. For at overvinde forhindringer blev begge modifikationer af de "klassiske" ordninger udviklet, og nye modeller af algoritmen blev skabt. Man kan især nævne:

• multi-tape og ikke-deterministiske Turing-maskiner;
• register og RAM-maskine  - en prototype af moderne computere og virtuelle maskiner;
• finite og cellulære automater

Typer af algoritmer

Typerne af algoritmer som logiske og matematiske midler afspejler de angivne komponenter af menneskelig aktivitet og tendenser, og selve algoritmerne, afhængigt af målet, indledende betingelser for problemet og måder at løse det på. Det skal understreges den grundlæggende forskel mellem algoritmer af beregningsmæssig karakter, der konverterer nogle inputdata til outputdata (det er deres formalisering, at de ovennævnte Turing-, Post-, PAM-maskiner, normale Markov-algoritmer og rekursive funktioner) og interaktive algoritmer (Turing har i forvejen en C-maskine, fra engelsk  valg  - et valg der afventer ekstern påvirkning, i modsætning til den klassiske A-maskine, hvor alle indledende data er givet før start af beregningen og udgangsdataene først er tilgængelige i slutningen af regnestykket). Sidstnævnte er designet til at interagere med et kontrolobjekt og er designet til at sikre den korrekte udstedelse af kontrolhandlinger afhængigt af den aktuelle situation, reflekteret af de signaler, der kommer fra kontrolobjektet [15] [16] . I nogle tilfælde sørger kontrolalgoritmen slet ikke for færdiggørelsen af ​​arbejdet (for eksempel opretholder den en endeløs cyklus af at vente på begivenheder, hvorpå der udstedes en passende reaktion), på trods af dette, er den fuldstændig korrekt.

Algoritmer kan også skelnes:

• Mekaniske algoritmer , eller på anden måde deterministiske , stive (f.eks. algoritmen til drift af en maskine, motor osv.) - indstiller bestemte handlinger, angiver dem i en enkelt og pålidelig rækkefølge, og giver derved et utvetydigt påkrævet eller ønsket resultat, hvis de procesbetingelser er opfyldt opgaver, som algoritmen er udviklet til.
• Fleksible algoritmer , såsom stokastiske, dvs. probabilistiske og heuristiske.
• En probabilistisk (stokastisk) algoritme giver et program til at løse et problem på flere måder eller måder, der fører til den sandsynlige opnåelse af et resultat.
• Heuristisk algoritme (fra det græske ord " eureka ") - en algoritme, der bruger forskellige rimelige overvejelser uden strenge begrundelser [17] .
• En lineær algoritme  er et sæt kommandoer (instruktioner), der udføres sekventielt i tid efter hinanden.
• En forgreningsalgoritme  er en algoritme, der indeholder mindst én betingelse, som resulterer i, at en opdeling i flere alternative grene af algoritmen kan udføres.
• En cyklisk algoritme  er en algoritme, der involverer gentagen gentagelse af den samme handling (samme operationer). De fleste af beregningsmetoderne og opremsningen af ​​muligheder er reduceret til cykliske algoritmer. En programcyklus er en sekvens af kommandoer (serier, cykluslegeme), der kan udføres flere gange.
• En hjælpe ( underordnet ) algoritme ( procedure ) er en algoritme, der tidligere er udviklet og udelukkende brugt til algoritmisering af et specifikt problem. I nogle tilfælde, hvis der er identiske sekvenser af instruktioner (kommandoer) for forskellige data, skelnes der også en hjælpealgoritme for at forkorte posten. På alle stadier af forberedelsen til algoritmiseringen af ​​problemet er den strukturelle repræsentation af algoritmen meget brugt.
• Strukturelt blokdiagram , grafdiagram af algoritmen  - en grafisk repræsentation af algoritmen i form af et diagram af blokke forbundet med pile (overgangslinjer) - grafiske symboler, som hver svarer til et trin i algoritmen. Inde i blokken gives en beskrivelse af den tilsvarende handling. Den grafiske repræsentation af algoritmen er meget brugt før programmering af opgaven på grund af dens klarhed, da visuel perception normalt letter processen med at skrive et program, rette det i tilfælde af mulige fejl og forstå informationsbehandlingsprocessen. Du kan endda støde på en sådan erklæring: "Udvendigt er algoritmen et skema - et sæt rektangler og andre symboler, indeni hvilke det er skrevet, hvad der beregnes, hvad der indtastes i maskinen, og hvad der udstedes til udskrivning og andre midler til at vise information."

Algoritmenummerering

Nummereringen af ​​algoritmer spiller en vigtig rolle i deres undersøgelse og analyse [18] . Da enhver algoritme kan specificeres som et endeligt ord (repræsenteret som en finit sekvens af symboler i et eller andet alfabet), og mængden af ​​alle finite ord i et endeligt alfabet kan tælles , så kan sættet af alle algoritmer også tælles. Dette betyder eksistensen af ​​en en-til-en mapping mellem sættet af naturlige tal og sættet af algoritmer, det vil sige muligheden for at tildele et tal til hver algoritme.

Nummereringen af ​​algoritmer er samtidig nummereringen af ​​alle algoritmisk beregnede funktioner, og enhver funktion kan have et uendeligt antal tal.

Eksistensen af ​​nummerering gør det muligt at arbejde med algoritmer på samme måde som med tal. Nummerering er især nyttig i studiet af algoritmer, der fungerer sammen med andre algoritmer.

Algoritmisk uløselige problemer

Formaliseringen af ​​begrebet en algoritme gjorde det muligt at undersøge eksistensen af ​​problemer, som der ikke er algoritmer til at finde løsninger på. Efterfølgende blev umuligheden af ​​algoritmisk beregning af løsninger på en række problemer bevist, hvilket gør det umuligt at løse dem på nogen computerenhed. En funktion kaldes beregnelig , hvis der er en Turing-maskine , der beregner værdien for alle elementer i funktionsdefinitionssættet. Hvis en sådan maskine ikke findes, siges funktionen at være ikke-beregnerlig. Funktionen vil blive betragtet som ikke-beregnelig, selvom der er Turing-maskiner, der er i stand til at beregne en værdi for en delmængde af hele sættet af input [19] .  

Tilfældet, hvor resultatet af evalueringen af ​​en funktion er det logiske udtryk "sand" eller "falsk" (eller mængden {0, 1}), kaldes et problem, der kan være løseligt eller uløseligt, afhængigt af funktionens beregnelighed [19] .

Det er vigtigt nøjagtigt at specificere det tilladte sæt af inputdata, da et problem kan være løseligt for et sæt og uløseligt for et andet.

Et af de første problemer, hvor uløselighed blev bevist, er det stoppende problem . Den er formuleret som følger:

Givet en beskrivelse af programmet for en Turing-maskine, er det nødvendigt at bestemme, om programmet afsluttes i en begrænset tid eller kører på ubestemt tid givet nogle input. [tyve]

Beviset for uløseligheden af ​​det stoppende problem er vigtigt, fordi andre problemer kan reduceres til det. For eksempel kan et simpelt standsningsproblem reduceres til et standsningsproblem på en tom linje (når du skal bestemme for en given Turing-maskine, om den vil stoppe, når den startes på en tom linje), og derved bevise sidstnævntes uafgørlighed. [19] .

Analyse af algoritmer

Sammen med udbredelsen af ​​informationsteknologi er risikoen for softwarefejl steget. En af måderne til at undgå fejl i algoritmer og deres implementeringer er at bevise korrektheden af ​​systemer med matematiske midler.

Brugen af ​​matematiske apparater til analyse af algoritmer og deres implementeringer kaldes formelle metoder. Formelle metoder involverer brugen af ​​formelle specifikationer og normalt et sæt værktøjer til at analysere og bevise specifikationernes egenskaber. Abstraktion fra implementeringsdetaljer giver dig mulighed for at indstille systemets egenskaber uafhængigt af dets implementering. Derudover gør nøjagtigheden og unikheden af ​​matematiske udsagn det muligt at undgå tvetydigheden og unøjagtigheden af ​​naturlige sprog [21] .

Ifølge Richard Maces hypotese er "fejlundgåelse bedre end fejleliminering" [22] . Ifølge Hoares formodning løser "bevis for programmer problemet med korrekthed, dokumentation og kompatibilitet" [23] . Beviset for rigtigheden af ​​programmer giver os mulighed for at afsløre deres egenskaber i forhold til hele rækken af ​​inputdata. For at gøre dette blev begrebet korrekthed opdelt i to typer:

• Delvist korrekt  - programmet giver det korrekte resultat i de tilfælde, hvor det afsluttes.
• Fuld korrekthed  - programmet afsluttes og producerer det korrekte resultat for alle elementer fra inputdataområdet.

Under bevis for korrekthed sammenlignes programmets tekst med specifikationen af ​​det ønskede forhold mellem input-outputdata. For beviser af Hoare-typen tager specifikationen form af udsagn, som kaldes forudsætninger og efterbetingelser. Sammen med selve programmet kaldes de også for Hoare-trippelen . Disse udsagn er skrevet som

hvor P  er de forudsætninger, der skal være sande, før programmet Q køres , og S er de efterbetingelser, der er sande efter programmets afslutning.

Formelle metoder er med succes blevet anvendt på en lang række problemer, især: udvikling af elektroniske kredsløb, kunstig intelligens, automatiske systemer på jernbanen, verifikation af mikroprocessorer , specifikation af standarder og specifikation og verifikation af programmer [24] .

Åbningstider

Et almindeligt kriterium for evaluering af algoritmer er køretiden og rækkefølgen, hvori køretiden vokser afhængigt af mængden af ​​inputdata. [25]

For hver specifik opgave udgør de et bestemt tal, som kaldes dets størrelse. For eksempel kan størrelsen af ​​opgaven med at beregne produktet af matricer være den største størrelse af matrixfaktorer, for opgaver på grafer kan størrelsen være antallet af grafkanter.

Den tid en algoritme bruger som funktion af opgavestørrelsen kaldes tidskompleksiteten af ​​den algoritme T ( n ). Asymptotikken for denne funktions adfærd, når problemets størrelse øges, kaldes asymptotisk tidskompleksitet, og notationen "O" stor bruges til at betegne det . For eksempel, hvis en algoritme behandler inputdata i tiden cn² , hvor c  er en eller anden konstant , så siges tidskompleksiteten af ​​en sådan algoritme at være O ( n² ).

Den asymptotiske kompleksitet er vigtig, fordi den er en karakteristik af algoritmen, og ikke for dens særlige implementering: ved at "optimere" operationerne, uden at ændre algoritmen, kan kun den multiplikative koefficient c ændres , men ikke asymptotikken. Som regel er det den asymptotiske kompleksitet, der er hovedfaktoren, der bestemmer størrelsen af ​​de opgaver, som algoritmen er i stand til at bearbejde.

Under udviklingen af ​​en algoritme forsøger man ofte at reducere den asymptotiske tidskompleksitet i de værste tilfælde. I praksis er der tilfælde, hvor en algoritme, der "normalt" kører hurtigt, er tilstrækkelig.

Groft sagt kan analysen af ​​den gennemsnitlige asymptotiske tidskompleksitet opdeles i to typer: analytisk og statistisk. Analysemetoden giver mere præcise resultater, men er svær at bruge i praksis. Men den statistiske metode giver dig mulighed for hurtigt at analysere komplekse problemer [26] .

Følgende tabel viser almindelige asymptotiske kompleksiteter med kommentarer [27] .

Tilstedeværelse af indledende data og nogle resultater

En algoritme er en præcist defineret instruktion, anvender den sekventielt på de indledende data, kan du få en løsning på problemet. For hver algoritme er der et bestemt sæt af objekter, der kan bruges som inputdata. For eksempel i algoritmen til at dividere reelle tal kan udbyttet være hvad som helst, og divisoren kan ikke være lig med nul.

Algoritmen tjener som regel til at løse ikke et specifikt problem, men en bestemt klasse af problemer. Så additionsalgoritmen gælder for ethvert par naturlige tal. Dette udtrykker dens masseegenskab, det vil sige evnen til gentagne gange at anvende den samme algoritme til enhver opgave i samme klasse.

Til udvikling af algoritmer og programmer bruges algoritmisering  - processen med systematisk kompilering af algoritmer til løsning af anvendte problemer. Algoritmisering betragtes som et obligatorisk trin i processen med at udvikle programmer og løse problemer på en computer. Det er for anvendte algoritmer og programmer, at determinisme, effektivitet og massekarakter, såvel som rigtigheden af ​​resultaterne af løsningen af ​​de stillede opgaver, er fundamentalt vigtige.

En algoritme er en klar og præcis instruktion til udøveren om at udføre en sekvens af handlinger rettet mod at nå målet.

Repræsentation af algoritmer

Algoritme notationsformer:

• verbal eller verbal: i naturligt sprog;
• i algoritmisk sprog: programmeringssprog eller pseudokode ;
• i maskinkode (computerprocessorkode);
• i matematisk notation (se ovenstående muligheder);
• skematisk:
  • grafik (for eksempel flowcharts og DRAKON-diagrammer );
  • strukturogrammer ( Nassi-Schneiderman-diagrammer ).

Normalt er algoritmen først (på idéniveau) beskrevet i ord, men efterhånden som den nærmer sig implementering, får den flere og mere formelle konturer og formuleringer i et sprog, der er forståeligt for udføreren (for eksempel maskinkode ).

Algoritmers effektivitet

Selvom definitionen af ​​algoritmen kun kræver et begrænset antal trin, der kræves for at opnå et resultat, fører implementeringen af ​​et stort antal trin i praksis til langsigtet eksekvering af programmer, og der er normalt andre begrænsninger (på størrelsen af programmet, om tilladte handlinger). I denne henseende introduceres sådanne begreber som kompleksiteten af ​​algoritmen ( tid , programstørrelse, beregningsmæssig og andre).

For hver opgave kan der være mange algoritmer, der fører til målet. At øge effektiviteten af ​​algoritmer er et af computervidenskabens problemer , siden 1940'erne er der i forbindelse hermed bygget en række mere asymptotisk effektive algoritmer til traditionelle problemer (f.eks. hurtige multiplikationsalgoritmer , Chudnovskys algoritme for beregner antallet ).

Eksempel

Euklids algoritme  er en effektiv metode til at beregne den største fælles divisor (gcd). Opkaldt efter den græske matematiker Euklid; en af ​​de ældste algoritmer, der stadig er i brug [28] .

Beskrevet i "Begyndelsen" af Euklid (ca. 300 f.Kr.), nemlig i bog VII og X. I den syvende bog er en algoritme for heltal beskrevet, og i den tiende - for længderne af segmenter.

Der er flere varianter af algoritmen, nedenfor er en rekursiv version skrevet i pseudokode :

GCD af numrene 1599 og 650:

Se også

• Metaalgorithme
• Auktion af algoritmer
• Liste over algoritmer
• Teori om algoritmer

Noter

1. ↑ Semenov A. L. ALGORITHM . Stor russisk encyklopædi. Elektronisk version (2016). Hentet 29. oktober 2018. Arkiveret fra originalen 30. oktober 2018. (ubestemt)
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 s. — ISBN 9780262731447 . Arkiveret 17. november 2021 på Wayback Machine
6. ↑ (Igoshin, s. 317)
7. ↑ V. A. Uspensky: "Matematik er en humanitær videnskab"  // Trinity Variant. - 2014. - 28. januar ( nr. 2 (146) ). - S. 4-6 . Arkiveret fra originalen den 27. november 2018. (Russisk)
8. ↑ Grundlæggende: Turing-maskinen (med en tolk!) . God matematik, dårlig matematik (9. februar 2007). Arkiveret fra originalen den 2. februar 2012. (ubestemt)
9. ↑ (Igoshin, afsnit 33)
10. ↑ Encyclopedia of Cybernetics , bind 2 , s. 90-91.
11. ↑ (Igoshin, afsnit 34)
12. ↑ 1 2 "Sandsynlighedsalgoritmer bør ikke forveksles med metoder (som jeg nægter at kalde algoritmer), som producerer et resultat, der har stor sandsynlighed for at være korrekt. Det er vigtigt, at en algoritme producerer korrekte resultater (der rabatterer menneskelige eller computerfejl), selvom dette sker efter meget lang tid." Henri Cohen. Et kursus i beregningsmæssig algebraisk talteori  . - Springer-Verlag , 1996. - S.  2 . — ISBN 3-540-55640-0 .
13. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives't, Clifford Stein. Introduktion til  algoritmer . - 2. - MIT Press , 2001. - S. 531. - ISBN 0-262-03293-7 .
14. ↑ (Afsnit 12, s. 12-22 i Atallah, 2010)
15. ↑ Dina Goldin, Peter Wegner. Oprindelsen af ​​Turing-afhandlingens myte , CS-04-14, oktober 2004
16. ↑ Interaktiv beregning er mere kraftfuld end ikke-interaktiv Arkiveret 19. november 2015 på Wayback Machine , c2.com
17. ↑ M. Gary, D. Johnson, Computermaskiner og vanskelige problemer, M .: Mir, 1982, C. 155.
18. ↑ (Igoshin, afsnit 36)
19. ↑ 1 2 3 Peter Linz. En introduktion til formelle sprog og automater  . - Jones og Bartlett Publishers, 2000. - ISBN 0-7637-1422-4 .
20. ↑ beregnelighed og kompleksitet, Encyclopedia of Computer Science and Technology , Facts On File, 2009, ISBN 978-0-8160-6382-6 . 
21. ↑ (O'Regan, afsnit 4.5)
22. ↑ (afsnit 5.3.6 i Enders, 2003)
23. ↑ (afsnit 5.3.7 i Enders, 2003)
24. ↑ (O'Regan, s. 119)
25. ↑ A. Aho , J. Hopcroft , J. Ullman . Konstruktion og analyse af beregningsalgoritmer = The Design and Analysis of Computer Algorithms . - M . : "Mir", 1979. (Russisk)
26. ↑ (afsnit 11 i Atallah, 2010)
27. ↑ (afsnit 1 i Atallah, 2010)
28. ↑ Knuth D. Kunsten at programmere computer , bind 2 : Seminumeriske algoritmer  . — 3. — Addison–Wesley , 1997. — ISBN 0201896842 .

Litteratur

• Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: Konstruktion og analyse = Introduktion til algoritmer, tredje udgave. - 3. - M. : "Williams" , 2013. - 1328 s. - ISBN 978-5-8459-1794-2 .
• Donald Knuth . The Art of Computer Programming = The Art of Computer Programming, vol. 1. Grundlæggende algoritmer. - 3. udgave - M . : "Williams" , 2006. - V. 1. Grundlæggende algoritmer. - S. 720. - ISBN 0-201-89683-4 .
• Thomas H. Cormen. Algoritmer: Introduktionskursus = Algorithms Unlocked. - M. : "Williams" , 2014. - 208 s. — ISBN 978-5-8459-1868-0 .
• Igoshin VI Matematisk logik og teori om algoritmer. - 2. udg., slettet .. - M . : Informationscenter "Academy", 2008. - 448 s. — ISBN 5-7695-1363-2 .

Links

• " Ordet "algoritme": oprindelse og udvikling ", V. V. Shilov, Potential magazine  - en kilde til historisk information.
• Om algoritmen  (utilgængeligt link fra 22-05-2013 [3452 dage] - historie ,  kopi ) i encyklopædien "Jorden rundt"

Ordbøger og encyklopædier	Flot dansk Fantastisk catalansk stor kinesisk Fantastisk norsk Stor russer italiensk jorden rundt kroatisk Britannica (online) Brockhaus Treccani Moderne Ukraine
I bibliografiske kataloger BNE : XX527980 BNF : 119358199 GND : 4001183-5 J9U : 987007293927505171 LCCN : sh85003487 NDL : 00560337 NKC : ph114026