Teori om algoritmer

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. august 2021; verifikation kræver 1 redigering .

Teorien om algoritmer er en gren af matematikken , der studerer de generelle egenskaber og mønstre af algoritmer og forskellige formelle modeller for deres repræsentation. Algoritmeteoriens opgaver omfatter formelt bevis for problemernes algoritmiske uløselighed , asymptotisk analyse af algoritmernes kompleksitet , klassificering af algoritmer i overensstemmelse med kompleksitetsklasser , udvikling af kriterier for en sammenlignende vurdering af kvaliteten af algoritmer osv. Sammen med matematisk logik danner teorien om algoritmer det teoretiske grundlag for beregningsvidenskab [1] [2] , teorien om informationstransmission, informatik , telekommunikationssystemer og andre områder inden for videnskab og teknologi.

Historie

Udviklingen af teorien om algoritmer begynder med Kurt Gödels bevis for ufuldstændighedsteoremer for formelle systemer, der involverer aritmetik, hvoraf den første blev bevist i 1931 . Den antagelse, der opstod i forbindelse med disse teoremer om umuligheden af algoritmisk løsning af mange matematiske problemer (især problemet med deducerbarhed i prædikatregning ) forårsagede behovet for at standardisere begrebet en algoritme. De første standardiserede versioner af dette koncept blev udviklet i 1930'erne af Alan Turing , Emil Post og Alonzo Church . Deres foreslåede Turing -maskine , Post-maskine og lambda-regning viste sig at være ækvivalente med hinanden. Baseret på Gödels arbejde introducerede Stephen Kleene begrebet en rekursiv funktion , som også viste sig at svare til ovenstående.

En af de mest succesrige standardiserede varianter af algoritmen er konceptet med en normal algoritme introduceret af Andrey Markov . Den blev udviklet ti år efter Turing, Post, Church og Kleenes arbejde i forbindelse med beviset for en række algebraiske problemers algoritmiske uløselighed.

I senere år blev væsentlige bidrag til algoritmeteori givet af Donald Knuth , Alfred Aho og Jeffrey Ullman .

Beregningsmodeller

Turing-maskinen er en abstrakt executor (abstrakt computermaskine). Det blev foreslået af Alan Turing i 1936 for at formalisere begrebet en algoritme . En Turing-maskine er en forlængelse af en endelig automat og er ifølge Church-Turing-afhandlingen i stand til at efterligne alle andre eksekutører (ved at sætte overgangsregler), der på en eller anden måde implementerer en trin-for-trin beregningsproces, hvor hvert beregningstrin er ret elementært.
Lambdaregning - et par betragtes: et λ-udtryk og dets argument, - og beregningen er anvendelsen eller anvendelsen af det første medlem af parret til det andet. Dette giver dig mulighed for at adskille funktionen og hvad den gælder for. Mere generelt anses en beregning for at være strenge, der starter med et indledende λ-udtryk efterfulgt af en endelig sekvens af λ-udtryk, som hver er opnået fra den foregående ved at anvende β-reduktion , det vil sige substitutionsreglen .
Kombinatorisk logik - fortolkningen af beregningen ligner λ-regningen, men der er også vigtige forskelle (f.eks. har fastpunktskombinatoren Y en normal form i kombinatorisk logik, men ikke i λ-regningen). Kombinatorisk logik blev oprindeligt udviklet til at studere paradoksers natur og for at bygge et konceptuelt klart grundlag for matematik, og ideen om en variabel blev fuldstændig udelukket, hvilket hjalp med at afklare variables rolle og plads i matematik .
Registermaskiner , især en RAM-maskine , er en abstrakt computer, der simulerer en computer med tilfældig adgang til hukommelse. Det er denne beregningsmodel, der oftest bruges i analyse af algoritmer.

The Church-Turing-afhandling og algoritmisk uløselige problemer

Alan Turing formodede (kendt som " Church-Turing-tesen "), at enhver algoritme - i ordets intuitive betydning - kan repræsenteres af en tilsvarende Turing-maskine . Forfining af begrebet beregnelighed baseret på konceptet om en sådan maskine (og andre begreber svarende til det) åbnede muligheden for strengt at bevise den algoritmiske uløselighed af forskellige masseproblemer (problemer med at finde en samlet metode til at løse en bestemt klasse af problemer , hvis betingelser kan variere inden for visse grænser).

Det enkleste eksempel på et algoritmisk uløseligt masseproblem er problemet med anvendeligheden af algoritmen, stopproblemet , som er som følger: det er nødvendigt at finde en generel metode, der ville tillade en vilkårlig Turing-maskine (givet af dens program) og en vilkårlig starttilstand for båndet af denne maskine for at bestemme, om arbejdet vil afslutte maskinen i et begrænset antal trin, eller vil det fortsætte i det uendelige?

I løbet af det første årti af teorien om algoritmer blev uløselige masseproblemer kun fundet i sig selv (inklusive "anvendelighedsproblemet" beskrevet ovenfor) og i matematisk logik ("problemet med deducerbarhed" i den klassiske prædikatregning ). Derfor mente man, at teorien om algoritmer er en "vejkant" af matematik, hvilket ikke betyder noget for sådanne klassiske sektioner som " algebra " eller " analyse ". Situationen ændrede sig efter Andrei Markov og Emil Post i 1947 etablerede den algoritmiske uløselighed af det velkendte lighedsproblem i algebra for endeligt genererede og endeligt definerede semigrupper ( Thues problem ). Efterfølgende blev den algoritmiske uløselighed af mange andre "rent matematiske" masseproblemer etableret, det mest berømte resultat på dette område er den algoritmiske uløselighed af Hilberts tiende problem bevist af Yuri Matiyasevich .

Rutevejledning

Teorien om algoritmer udvikler sig hovedsageligt i tre retninger:

Klassisk:
- Formel formulering af opgaver;
- Begrebet et løsningsproblem ;
- Klassificering af sværhedsgrader (" P ", " NP " og andre).
Analyse:
- Asymptotisk :
  - Estimering af ressourceintensitet og eksekveringstid (især for rekursive algoritmer);
  - Estimering af væksten i ressourcebehov (f.eks. eksekveringstid) med en stigning i mængden af data.
- Praktisk:
  - Opnåelse af "eksplicitte" funktioner for arbejdsintensitet;
  - Intervalanalyse af funktioner;
  - Søg efter kvalitetskriterier;
  - Metode til rationelt valg.

Analyse af kompleksiteten af algoritmer

Formålet med analysen er at finde den optimale algoritme. Kriteriet er besværlighed (antallet af elementære operationer, der kræves af algoritmen). Funktionen af arbejdsinput er forholdet mellem arbejdsinput og inputdata.

Kompleksiteten kan påvirkes i forskellig grad af egenskaberne for inputdata:

Bind;
Værdier;
Indgangsrækkefølge.

En af de forenklede typer omkostningsanalyse af algoritmer er asymptotisk med en stor mængde inputdata. Estimatet af den anvendte arbejdsintensitetsfunktion er "kompleksiteten" af algoritmen , som gør det muligt at bestemme forholdet mellem arbejdsintensitet og mængden af data. I den asymptotiske analyse af algoritmer bruges notationen, der bruges i matematisk asymptotisk analyse. De vigtigste sværhedsgrader er angivet nedenfor.

Hovedestimatet af kompleksitetsfunktionen af algoritmen (hvor n er mængden af data, "længden af inputtet") er : $f(n)$ ${\boldsymbol {\Theta }}$

f(n)={\boldsymbol {\Theta }}(g(n))

hvis for g > 0, for n > 0, er der positive c 1 , c 2 , n 0 , således at:

c_{1}\cdot g(n)\leq \;f(n)\leq \;c_{2}\cdot g(n)

kl ; med andre ord kan man finde sådan og , som for tilstrækkelig stor vil være indesluttet mellem: ${\displaystyle n>n_{0))$ $c_{1}$ $c_{2}$ $n$ $f(n)$

c_{1}\cdot \;g(n)

og .

c_{2}\cdot \;g(n)

I dette tilfælde siger de også, at funktionen er et asymptotisk nøjagtigt estimat af funktionen , da funktionen per definition ikke adskiller sig fra funktionen op til en konstant faktor (se asymptotisk lighed ). For eksempel for sorteringsmetoden "heapsort" er arbejdsindsatsen: $g(n)$ $f(n)$ $f(n)$ $g(n)$

f(n)={\boldsymbol {\Theta }}(n\log n)

, altså .

g(n)=n\log n

Fra følger . $f(n)={\boldsymbol {\Theta }}(g(n))$ $g(n)={\boldsymbol {\Theta }}(f(n))$

${\boldsymbol {\Theta }}(g(n))$ er ikke en funktion, men et sæt funktioner, der beskriver vækst op til en konstant faktor. giver både øvre og nedre grænser for funktionens vækst. Det er ofte nødvendigt at overveje disse skøn separat. Estimatet er et øvre asymptotisk estimat af kompleksiteten af algoritmen. Vi siger, at hvis: $f(n)$ ${\boldsymbol {\Theta }}$ ${\boldsymbol {O}}$ $f(n)={\fedsymbol {O}}(g(n))$

\eksisterer \;c>0,n_{0}>0:0\leq \;f(n)\leq \;cg(n),\foralt \;n>n_{0}

Med andre ord betyder notationen , at den tilhører klassen af funktioner, der ikke vokser hurtigere end funktionen op til en konstant faktor. $f(n)={\fedsymbol {O}}(g(n))$ $f(n)$ $g(n)$

Estimatet specificerer et lavere asymptotisk estimat for væksten af en funktion og definerer en klasse af funktioner, der ikke vokser langsommere end op til en konstant faktor. , hvis: ${\boldsymbol {\Omega ))$ $f(n)$ $g(n)$ $f(n)={\fedsymbol {\Omega }}(g(n))$

{\displaystyle \exists \;c>0,n_{0}>0:0\leq \;c\,g(n)\leq \;f(n),\foralt \;n>n_{0))

For eksempel angiver notationen en klasse af funktioner, der ikke vokser langsommere end ; denne klasse omfatter alle polynomier med en grad større end én, såvel som alle potensfunktioner med en grundtal større end én. $f(n)={\boldsymbol {\Omega }}(n\,\log n)$ $g(n)=n\,\log n$

Ligestilling gælder hvis og kun hvis og . $f(n)={\boldsymbol {\Theta }}(g(n))$ $f(n)={\fedsymbol {O}}(g(n))$ $f(n)={\fedsymbol {\Omega }}(g(n))$

Den asymptotiske analyse af algoritmer har ikke kun praktisk, men også teoretisk betydning. For eksempel er det blevet bevist, at alle sorteringsalgoritmer baseret på parvis sammenligning af elementer vil sortere n elementer i tid ikke mindre end . ${\boldsymbol {\Omega }}(n\,\log n)$

En vigtig rolle i udviklingen af den asymptotiske analyse af algoritmer blev spillet af Alfred Aho , Jeffrey Ullman , John Hopcroft .

Sværhedsklasser

Inden for rammerne af den klassiske teori klassificeres problemer efter deres kompleksitet ( P-hårde , NP-hårde , eksponentielt hårde og andre):

"P" - kan løses i tide, polynomielt afhængigt af mængden af indledende data, ved hjælp af en deterministisk computer (for eksempel " Turing-maskine ");
"NP":
- Problemer, der kan løses i polynomisk tid ved hjælp af en ikke -deterministisk computer (hvis næste tilstand ikke altid er entydigt bestemt af de foregående). Dets arbejde kan repræsenteres som en proces, der forgrener sig ved hver tvetydighed: problemet er løst, hvis mindst én gren når frem til svaret;
- Problemer, hvis løsning ved hjælp af yderligere information af polynomiel længde givet til os fra oven, kan vi tjekke i polynomiel tid. Specielt inkluderer klassen "NP" alle problemer, hvis løsning kan kontrolleres i polynomisk tid.

Klassen "P" er indeholdt i "NP". Et klassisk eksempel på et NP-problem er " Travelling Salesman Problem ".

Da "P" er indeholdt i "NP", afspejler tilhørsforholdet af et problem til klassen "NP" ofte vores nuværende forståelse af, hvordan man løser dette problem og er ikke endeligt. I den generelle sag er der ingen grund til at tro, at der ikke kan findes en P-løsning for et eller andet NP-problem. Spørgsmålet om den mulige ækvivalens af klasserne "P" og "NP" (muligheden for at finde en P-løsning for ethvert NP-problem) betragtes som en af de vigtigste i den moderne teori om kompleksiteten af algoritmer; intet svar er fundet indtil videre. Selve dens formulering er mulig takket være introduktionen af begrebet NP-komplette problemer ; eventuelle NP-problemer kan reduceres til dem - og hvis der findes en P-løsning for et NP-komplet problem, så vil der blive fundet en P-løsning for alle NP-problemer. Et eksempel på et NP-komplet problem er " Konjunktivformproblemet ".

Undersøgelser af kompleksiteten af algoritmer har gjort det muligt at tage et nyt kig på løsningen af mange klassiske matematiske problemer og finde løsninger for nogle af deres serier (multiplikation af polynomier og matricer, løsning af lineære ligningssystemer og andre) løsninger, der kræver mindre ressourcer end traditionelle.

Matematiske anvendelser af teorien om algoritmer

Nogle anvendelser af teorien om algoritmer:

forskning i masseproblemer;
anvendelser på matematikkens grundlag : konstruktiv semantik ;
applikationer til matematisk logik : analyse af formaliserede sprog af logik og aritmetik ;
beregnelig analyse;
nummererede strukturer;
anvendelser til sandsynlighedsteori : definitioner af en tilfældig sekvens;
anvendelser til informationsteori : en algoritmisk tilgang til begrebet informationsmængde;
vurdering af kompleksiteten af at løse individuelle problemer;
teorien om algoritmers indflydelse på algoritmisk praksis [3] .

Noter

↑ Semyonov A. L. , Uspensky V. A. Matematisk logik i beregningsvidenskab og beregningspraksis. // Bulletin of the Academy of Sciences of the USSR , nr. 7, s. 93 - 103
↑ Uspensky V. A. , Semyonov A. L. Løsbare og uløselige algoritmiske problemer. // Kvant , 1985, nr. 7, s. 9 - 15
↑ V. A. Uspensky , A. L. Semenov Algorithms teori: vigtigste opdagelser og anvendelser, M., Nauka , 1987, 288 s.

Litteratur

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
Donald Knuth . The Art of Computer Programming, bind 1. Grundlæggende algoritmer = The Art of Computer Programming, bind 1. Grundlæggende algoritmer. - 3. udg. - M. : Williams, 2006. - 720 s. - ISBN 0-201-89683-4 .
Kolmogorov A. N. Teori om information og teori om algoritmer. - M. : Nauka, 1987. - 304 s.
Markov A. A., Nagorny N. M. Algoritmerteori. - 2. udgave - M . : Fazis, 1996.

Links

Forelæsninger om kompleksitetsteori og kombinatoriske algoritmer

Ordbøger og encyklopædier	Fantastisk catalansk Stor russer

Grene af matematik

Portal "Science"

Grundlaget for matematik mængdeteori matematisk logik logikkens algebra

Talteori ( aritmetik )

Algebra
Elementær algebra	Ligningsløsning
Lineær algebra	Vektorregning matricer Tensorregning Multilineær algebra
Generel algebra	Kommutativ algebra Repræsentationsteori Differentiel algebra Homologisk algebra Universal Algebra Kategori teori

Analyse
Klassisk analyse	Differentialregning Integralregning
Funktionsteori	Harmonisk analyse Kvaternion Analyse Kompleks analyse måle teori Teori om funktioner af en reel variabel funktionel analyse Variationsberegning
Differential- og integralligninger	Dynamiske systemer og ergodisk teori Differentialligninger almindelig i partielle derivater Integralligninger
Vektoranalyse Global Analyse Katastrofe teori Tilpasset analyse Glat infinitesimal analyse

Geometri og topologi
Geometri	Algebraisk geometri Analytisk geometri Euklidisk geometri Ikke-euklidisk geometri Planimetri Stereometri
Topologi	Generel topologi Algebraisk topologi Differentialgeometri og topologi

Diskret matematik
Kombinatorik grafteori

Anvendt matematik
Matematisk fysik Matematisk kemi matematisk biologi Matematik statistik Matematisk modellering Teori om algoritmer Numeriske metoder matematisk økonomi finansiel matematik Sandsynlighedsteori Operationsforskning Spilteori

Portal "Matematik"
Kategori "Matematik"