Teori om algoritmer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 augusti 2021; verifiering kräver 1 redigering .

Algoritmteorin är en gren av matematiken som studerar algoritmers allmänna egenskaper och mönster och olika formella modeller för deras representation. Uppgifterna för teorin om algoritmer inkluderar formellt bevis på den algoritmiska olösbarheten av problem, asymptotisk analys av komplexiteten hos algoritmer , klassificering av algoritmer i enlighet med komplexitetsklasser , utveckling av kriterier för en jämförande bedömning av algoritmernas kvalitet, etc. Tillsammans med matematisk logik utgör teorin om algoritmer den teoretiska grunden för beräkningsvetenskaper [1] [ 2] , teorin om informationsöverföring, informatik , telekommunikationssystem och andra områden inom vetenskap och teknik.

Historik

Utvecklingen av teorin om algoritmer börjar med Kurt Gödels bevis på ofullständighetsteorem för formella system som involverar aritmetik, varav den första bevisades 1931 . Antagandet som uppstod i samband med dessa satser om omöjligheten av algoritmisk lösning av många matematiska problem (särskilt problemet med deducerbarhet i predikatkalkyl ) orsakade behovet av att standardisera begreppet en algoritm. De första standardiserade versionerna av detta koncept utvecklades på 1930-talet av Alan Turing , Emil Post och Alonzo Church . Deras föreslagna Turing -maskin , Post-maskin och lambda-kalkyl visade sig vara likvärdiga med varandra. Baserat på Gödels arbete, introducerade Stephen Kleene begreppet en rekursiv funktion , som också visade sig vara likvärdig med ovanstående.

En av de mest framgångsrika standardiserade varianterna av algoritmen är konceptet med en normal algoritm som introducerats av Andrey Markov . Den utvecklades tio år efter Turing, Post, Church och Kleenes arbete i samband med beviset på den algoritmiska olösligheten för ett antal algebraiska problem.

Under senare år gjordes betydande bidrag till algoritmteorin av Donald Knuth , Alfred Aho och Jeffrey Ullman .

Beräkningsmodeller

Turing-maskinen är en abstrakt executor (abstrakt datormaskin). Det föreslogs av Alan Turing 1936 för att formalisera konceptet med en algoritm . En Turing-maskin är en förlängning av en finit automat och kan enligt Church-Turing-avhandlingen imitera alla andra exekutörer (genom att sätta övergångsregler) som på något sätt implementerar en steg-för-steg-beräkningsprocess där varje beräkningssteg är ganska elementärt.
Lambdakalkyl - ett par betraktas: ett λ-uttryck och dess argument, - och beräkningen är tillämpningen, eller tillämpningen, av den första medlemmen i paret på den andra. Detta gör att du kan separera funktionen och vad den gäller. Mer generellt anses en beräkning vara strängar som börjar med ett initialt λ-uttryck följt av en slutlig sekvens av λ-uttryck, som vart och ett erhålls från det föregående genom att tillämpa β-reduktion , det vill säga substitutionsregeln .
Kombinatorisk logik - tolkningen av beräkningen liknar λ-kalkylen, men det finns också viktiga skillnader (till exempel har fixpunktskombinatorn Y en normal form i kombinatorisk logik, men inte i λ-kalkylen). Kombinatorisk logik utvecklades ursprungligen för att studera paradoxernas natur och för att bygga en konceptuellt tydlig grund för matematik, och idén om en variabel uteslöts helt, vilket hjälpte till att klargöra variablernas roll och plats i matematik .
Registermaskiner , i synnerhet en RAM-maskin , är en abstrakt dator som simulerar en dator med slumpmässig tillgång till minne. Det är denna beräkningsmodell som oftast används vid analys av algoritmer.

The Church-Turing-avhandling och algoritmiskt olösliga problem

Alan Turing gissade (känd som " Church-Turing tesen ") att vilken algoritm som helst - i ordets intuitiva bemärkelse - kan representeras av en motsvarande Turing-maskin . Förfining av begreppet beräkningsbarhet baserat på konceptet för en sådan maskin (och andra begrepp motsvarande den) öppnade möjligheten att noggrant bevisa den algoritmiska olösbarheten för olika massproblem (problem med att hitta en enhetlig metod för att lösa en viss klass av problem villkoren kan variera inom vissa gränser).

Det enklaste exemplet på ett algoritmiskt olösligt massproblem är problemet med tillämpligheten av algoritmen, stoppproblemet , som är följande: det krävs att man hittar en generell metod som skulle möjliggöra en godtycklig Turing-maskin (given av dess program) och ett godtyckligt initialtillstånd för bandet på denna maskin för att avgöra om arbetet kommer att avsluta maskinen i ett begränsat antal steg, eller kommer det att fortsätta på obestämd tid?

Under det första decenniet av teorin om algoritmer hittades olösbara massproblem endast i sig själv (inklusive "tillämpningsproblemet" som beskrivits ovan) och i matematisk logik ("problemet med deducerbarhet" i den klassiska predikatkalkylen ). Därför trodde man att teorin om algoritmer är en "vägkant" av matematik, vilket inte spelar någon roll för sådana klassiska avsnitt som " algebra " eller " analys ". Situationen förändrades efter att Andrei Markov och Emil Post 1947 fastställde den algoritmiska olösligheten hos det välkända jämlikhetsproblemet i algebra för ändligt genererade och ändligt definierade semigrupper ( Thues problem ). Därefter fastställdes den algoritmiska olösbarheten för många andra "rent matematiska" massproblem, det mest kända resultatet på detta område är den algoritmiska olösligheten för Hilberts tionde problem bevisat av Yuri Matiyasevich .

Vägbeskrivning

Algoritmteorin utvecklas huvudsakligen i tre riktningar:

Klassisk:
- Formell formulering av uppgifter;
- Konceptet med ett lösningsproblem ;
- Klassificering av svårighetsnivåer ( " P ", " NP " och andra).
Analys:
- Asymptotisk :
  - Uppskattning av resursintensitet och exekveringstid (särskilt för rekursiva algoritmer);
  - Uppskattning av ökningen av resursbehov (till exempel exekveringstid) med en ökning av mängden data.
- Praktisk:
  - Erhålla "explicita" funktioner för arbetsintensitet;
  - Intervallanalys av funktioner;
  - Sök efter kvalitetskriterier;
  - Metodik för rationellt val.

Analys av komplexiteten hos algoritmer

Syftet med analysen är att hitta den optimala algoritmen. Kriteriet är mödosamt (antalet elementära operationer som krävs av algoritmen). Arbetsinsatsens funktion är förhållandet mellan arbetsinsats och indata.

Komplexiteten kan påverkas i olika utsträckning av egenskaperna hos indata:

Volym;
Värderingar;
Inträdesordning.

En av de förenklade typerna av kostnadsanalys av algoritmer är asymptotisk, med en stor mängd indata. Uppskattningen av arbetsintensitetsfunktionen som används är algoritmens "komplexitet" , som gör det möjligt att bestämma förhållandet mellan arbetsintensitet och mängden data. I den asymptotiska analysen av algoritmer används notationen som används i matematisk asymptotisk analys. De viktigaste svårighetsgraderna listas nedan.

Huvuduppskattningen av algoritmens komplexitetsfunktion (där n är mängden data, "längden på indata") är : $f(n)$ ${\boldsymbol {\Theta ))$

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

om för g > 0, för n > 0, finns det positiva c 1 , c 2 , n 0 så att:

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

vid ; med andra ord kan man hitta sådana och , som, för tillräckligt stora , kommer att vara inneslutna mellan: $n>n_{0}$ $c_{1}$ $c_{2}$ $n$ $f(n)$

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

och .

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

I det här fallet säger de också att funktionen är en asymptotiskt exakt uppskattning av funktionen , eftersom funktionen per definition inte skiljer sig från funktionen upp till en konstant faktor (se asymptotisk jämlikhet ). Till exempel, för sorteringsmetoden "heapsort" är arbetsinsatsen: $g(n)$ $f(n)$ $f(n)$ $g(n)$

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

, det vill säga .

g(n)=n\log n

Från följer . $f(n)={\boldsymbol {\Theta }}(g(n))$ $g(n)={\boldsymbol {\Theta }}(f(n))$

${\boldsymbol {\Theta }}(g(n))$ är inte en funktion, utan en uppsättning funktioner som beskriver tillväxt upp till en konstant faktor. ger både övre och nedre gränser för funktionens tillväxt. Det är ofta nödvändigt att överväga dessa uppskattningar separat. Uppskattningen är en övre asymptotisk uppskattning av algoritmens komplexitet. Vi säger att om: $f(n)$ ${\boldsymbol {\Theta ))$ ${\boldsymbol {O}}$ $f(n)={\boldsymbol {O}}(g(n))$

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

Med andra ord betyder notationen att den tillhör den klass av funktioner som inte växer snabbare än funktionen upp till en konstant faktor. $f(n)={\boldsymbol {O}}(g(n))$ $f(n)$ $g(n)$

Uppskattningen specificerar en lägre asymptotisk uppskattning för tillväxten av en funktion och definierar en klass av funktioner som inte växer långsammare än upp till en konstant faktor. , om: ${\boldsymbol {\Omega ))$ $f(n)$ $g(n)$ $f(n)={\boldsymbol {\Omega }}(g(n))$

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

Till exempel betecknar notationen en klass av funktioner som inte växer långsammare än ; denna klass inkluderar alla polynom med en grad större än en, såväl som alla potensfunktioner med en bas större än ett. $f(n)={\boldsymbol {\Omega ))(n\,\log n)$ $g(n)=n\,\log n$

Jämlikhet gäller om och bara om och . $f(n)={\boldsymbol {\Theta }}(g(n))$ $f(n)={\boldsymbol {O}}(g(n))$ $f(n)={\boldsymbol {\Omega }}(g(n))$

Den asymptotiska analysen av algoritmer har inte bara praktisk utan också teoretisk betydelse. Till exempel har det bevisats att alla sorteringsalgoritmer baserade på parvis jämförelse av element kommer att sortera n element i tiden inte mindre än . ${\boldsymbol {\Omega ))(n\,\log n)$

En viktig roll i utvecklingen av den asymptotiska analysen av algoritmer spelades av Alfred Aho , Jeffrey Ullman , John Hopcroft .

Svårighetsklasser

Inom ramen för den klassiska teorin klassificeras problem efter deras komplexitet ( P-hårda , NP-hårda , exponentiellt hårda och andra):

"P" - kan lösas i tid, polynomiskt beroende på mängden initiala data, med hjälp av en deterministisk dator (till exempel " Turing-maskin ");
"NP":
- Problem som kan lösas i polynomtid med hjälp av en icke -deterministisk dator (vars nästa tillstånd inte alltid bestäms unikt av de föregående). Dess arbete kan representeras som en process som förgrenar sig vid varje tvetydighet: problemet löses om åtminstone en gren når svaret;
- Problem vars lösning med hjälp av ytterligare information av polynomlängd som ges till oss ovanifrån, kan vi checka in polynomtid. Speciellt inkluderar klassen "NP" alla problem vars lösning kan kontrolleras i polynomtid.

Klassen "P" finns i "NP". Ett klassiskt exempel på ett NP-problem är " Traveling Salesman Problem ".

Eftersom "P" finns i "NP", återspeglar tillhörigheten av ett problem till klassen "NP" ofta vår nuvarande förståelse för hur man löser detta problem och är inte slutgiltig. I det allmänna fallet finns det ingen anledning att tro att en P-lösning inte kan hittas för ett eller annat NP-problem. Frågan om den möjliga ekvivalensen för klasserna "P" och "NP" (möjligheten att hitta en P-lösning för vilket NP-problem som helst) anses vara en av de viktigaste i den moderna teorin om komplexiteten hos algoritmer; inget svar har hittats hittills. Dess själva formulering är möjlig tack vare introduktionen av begreppet NP-kompletta problem ; alla NP-problem kan reduceras till dem — och om en P-lösning hittas för ett NP-komplett problem, så kommer en P-lösning att hittas för alla NP-problem. Ett exempel på ett NP-komplett problem är " Konjunktivformproblemet ".

Studier av komplexiteten hos algoritmer har gjort det möjligt att ta en ny titt på lösningen av många klassiska matematiska problem och för vissa av deras serier (multiplikation av polynom och matriser, lösa linjära ekvationssystem och andra) hitta lösningar som kräver mindre resurser än traditionella.

Matematiska tillämpningar av teorin om algoritmer

Några tillämpningar av teorin om algoritmer:

forskning av massproblem;
tillämpningar på matematikens grunder : konstruktiv semantik ;
tillämpningar för matematisk logik : analys av formaliserade språk för logik och aritmetik ;
beräkningsbar analys;
numrerade strukturer;
tillämpningar av sannolikhetsteori : definitioner av en slumpmässig sekvens;
tillämpningar på informationsteori : en algoritmisk metod för begreppet informationskvantitet;
bedömning av komplexiteten i att lösa individuella problem;
inverkan av teorin om algoritmer på algoritmisk praktik [3] .

Anteckningar

↑ Semyonov A. L. , Uspensky V. A. Matematisk logik i beräkningsvetenskap och beräkningspraktik. // Bulletin of the Academy of Sciences of the USSR , nr 7, sid. 93 - 103
↑ Uspensky V. A. , Semyonov A. L. Lösbara och olösliga algoritmiska problem. // Kvant , 1985, nr 7, sid. 9 - 15
↑ V. A. Uspensky , A. L. Semenov Algorithms teori: huvudupptäckter och tillämpningar, M., Nauka , 1987, 288 sid.

Litteratur

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - 1296 sid. — ISBN 5-8459-0857-4 .
Donald Knuth . Konsten att programmera, vol. 1. Grundläggande algoritmer = Konsten att programmera, vol. 1. Grundläggande algoritmer. - 3:e uppl. - M. : Williams, 2006. - 720 sid. - ISBN 0-201-89683-4 .
Kolmogorov A. N. Teori om information och teori om algoritmer. - M. : Nauka, 1987. - 304 sid.
Markov A. A., Nagorny N. M. Theory of Algoritms. - 2:a upplagan - M . : Fazis, 1996.

Länkar

Föreläsningar om komplexitetsteori och kombinatoriska algoritmer

Ordböcker och uppslagsverk	Stor katalanska Stor ryss

Matematikens grenar

Portal "Science"

Grunderna för matematik mängdteori matematisk logik logikens algebra

Talteori ( aritmetik )

Algebra
Elementär algebra	Ekvationslösning
Linjär algebra	Vektorkalkyl matriser Tensorkalkyl Multilinjär algebra
Allmän algebra	Kommutativ algebra Representationsteori Differentialalgebra Homologisk algebra Universal algebra Kategoriteori

Analys
Klassisk analys	Differentialkalkyl Integralkalkyl
Funktionsteori	Harmonisk analys Kvaternionanalys Komplex analys måttteori Teori om funktioner för en reell variabel funktionell analys Variationskalkyl
Differentialekvationer och integralekvationer	Dynamiska system och ergodisk teori Differentialekvationer vanlig i partiella derivat Integralekvationer
Vektoranalys Global analys Katastrofteori Anpassad analys Smidig infinitesimal analys

Geometri och topologi
Geometri	Algebraisk geometri Analytisk geometri Euklidisk geometri Icke-euklidisk geometri Planimetri Stereometri
Topologi	Allmän topologi Algebraisk topologi Differentialgeometri och topologi

Diskret matematik
Kombinatorik grafteori

Tillämpad matematik
Matematisk fysik Matematisk kemi matematisk biologi Matematik statistik Matematisk modellering Teori om algoritmer Numeriska metoder matematisk ekonomi finansiell matematik Sannolikhetsteori Operationsforskning Spel teori

Portalen "Matematik"
Kategori "Matematik"