Algoritmien teoria

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. elokuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Algoritmien teoria on matematiikan haara , joka tutkii algoritmien yleisiä ominaisuuksia ja malleja sekä erilaisia muodollisia malleja niiden esittämiseksi. Algoritmien teorian tehtäviin kuuluu muodollinen todiste ongelmien algoritmisesta ratkaisemattomuudesta , algoritmien monimutkaisuuden asymptoottinen analyysi , algoritmien luokittelu monimutkaisuusluokkien mukaan , kriteerien kehittäminen algoritmien laadun vertailevaa arviointia varten jne. Yhdessä matemaattisen logiikan kanssa algoritmien teoria muodostaa laskennallisten tieteiden [1] [2] , tiedonsiirron teorian, informatiikan , tietoliikennejärjestelmien ja muiden tieteen ja teknologian alojen teoreettisen perustan.

Historia

Algoritmien teorian kehitys alkaa Kurt Gödelin todistuksella epätäydellisyyden teoreemoista aritmetiikkaa sisältäville muodollisille järjestelmille, joista ensimmäinen todistettiin vuonna 1931 . Näiden teoreemojen yhteydessä noussut oletus monien matemaattisten ongelmien (erityisesti johdettavuuden ongelma predikaattilaskennassa ) mahdottomuudesta ratkaista algoritmisesti, aiheutti tarpeen standardoida algoritmin käsite. Ensimmäiset standardoidut versiot tästä konseptista kehittivät 1930 - luvulla Alan Turing , Emil Post ja Alonzo Church . Heidän ehdottamansa Turingin kone , Postikone ja lambda-laskenta osoittautuivat toisiaan vastaaviksi. Stephen Kleene esitteli Gödelin työhön perustuen rekursiivisen funktion käsitteen , joka myös osoittautui vastaavaksi yllä olevaa.

Yksi algoritmin menestyneimmistä standardoiduista muunnelmista on Andrey Markovin esittelemä normaalialgoritmin käsite . Se kehitettiin kymmenen vuotta Turingin, Postin, Churchin ja Kleenen työn jälkeen useiden algebrallisten ongelmien algoritmisen ratkaisemattomuuden todistamisen yhteydessä.

Myöhempinä vuosina Donald Knuth , Alfred Aho ja Jeffrey Ullman antoivat merkittävän panoksen algoritmiteoriaan .

Laskentamallit

Turingin kone on abstrakti toteuttaja (abstrakti laskentakone). Alan Turing ehdotti vuonna 1936 algoritmin käsitteen formalisoimista . Turingin kone on äärellisen automaatin jatke ja Church-Turingin teesin mukaan se pystyy jäljittelemään kaikkia muita toteuttajia (asettamalla siirtymäsääntöjä), jotka jollakin tavalla toteuttavat vaiheittaisen laskentaprosessin, jossa jokainen laskentavaihe on aika alkeellista.
Lambdalaskenta - katsotaan pari: λ-lauseke ja sen argumentti, - ja laskelma on parin ensimmäisen jäsenen sovellus tai soveltaminen toiseen. Näin voit erottaa toiminnon ja sen, mitä se koskee. Yleisemmin laskelman katsotaan olevan merkkijonoja, jotka alkavat alkuperäisestä λ-lausekkeesta, jota seuraa lopullinen λ-lausekkeiden sarja, joista kukin saadaan edellisestä käyttämällä β -pelkistystä eli korvaussääntöä .
Kombinatorinen logiikka - laskennan tulkinta on samanlainen kuin λ-laskennassa, mutta siinä on myös merkittäviä eroja (esim. kiintopistekombinaattorilla Y on kombinatorisessa logiikassa normaalimuoto, mutta ei λ-laskennassa). Kombinatorinen logiikka kehitettiin alun perin tutkimaan paradoksien luonnetta ja rakentamaan käsitteellisesti selkeä perusta matematiikalle, ja muuttujan idea suljettiin kokonaan pois, mikä auttoi selventämään muuttujien roolia ja paikkaa matematiikassa .
Rekisterikoneet , erityisesti RAM-kone , on abstrakti tietokone, joka simuloi tietokonetta, jolla on satunnainen pääsy muistiin. Juuri tätä laskentamallia käytetään useimmiten algoritmien analysoinnissa.

Church-Turingin teesi ja algoritmisesti ratkaisemattomat ongelmat

Alan Turing arveli (tunnetaan nimellä " Church-Turingin teesi "), että mikä tahansa algoritmi - sanan intuitiivisessa merkityksessä - voidaan esittää vastaavalla Turingin koneella . Sellaisen koneen käsitteen (ja muiden sitä vastaavien käsitteiden) pohjalta laskettavuuden käsitteen jalostaminen avasi mahdollisuuden todistaa tarkasti erilaisten massaongelmien (yhtenäisen menetelmän löytämisen ongelmat tietyn luokan ongelman ratkaisemiseksi) algoritminen ratkaisemattomuus . , jonka ehdot voivat vaihdella tietyissä rajoissa).

Yksinkertaisin esimerkki algoritmisesti ratkaisemattomasta massaongelmasta on algoritmin sovellettavuusongelma, pysäytysongelma , joka on seuraava: vaaditaan yleinen menetelmä, joka mahdollistaisi mielivaltaisen Turingin koneen (sen ohjelman antaman) ja tämän koneen nauhan mielivaltainen alkutila sen määrittämiseksi, päättyykö työ äärelliseen määrään vaiheita vai jatkuuko se loputtomiin?

Algoritmien teorian historian ensimmäisen vuosikymmenen aikana ratkaisemattomia massaongelmia löydettiin vain itsessään (mukaan lukien edellä kuvattu "soveltuvuusongelma") ja matemaattisesta logiikasta ("pääteltävissä oleva ongelma" klassisessa predikaattilaskennassa ). Siksi uskottiin, että algoritmien teoria on matematiikan "tienvarsi", jolla ei ole väliä sellaisille klassisille osille kuin " algebra " tai " analyysi ". Tilanne muuttui sen jälkeen, kun Andrei Markov ja Emil Post vuonna 1947 vahvistivat algebran hyvin tunnetun tasa-arvoongelman algoritmisen ratkaisemattomuuden äärellisesti generoiduille ja äärellisesti määritellyille puoliryhmille ( Thuen ongelma ). Myöhemmin määritettiin monien muiden "puhtaasti matemaattisten" massaongelmien algoritminen ratkaisemattomuus, tunnetuin tulos tällä alueella on Hilbertin kymmenennen ongelman algoritminen ratkaisemattomuus , jonka Juri Matiyasevitš todisti .

Reittiohjeet

Algoritmien teoria kehittyy pääasiassa kolmeen suuntaan:

Klassikko:
- Tehtävien muodollinen muotoilu;
- Ratkaisuongelman käsite ;
- Vaikeustasojen luokitus (" P ", " NP " ja muut).
Analyysi:
- Asymptoottinen :
  - Resurssiintensiteetin ja suoritusajan arviointi (erityisesti rekursiivisten algoritmien osalta);
  - Resurssitarpeen (esimerkiksi suoritusajan) kasvun arvioiminen tietomäärän kasvaessa.
- Käytännöllinen:
  - Työvoimaintensiteetin "selkeiden" funktioiden saaminen;
  - Toimintojen intervallianalyysi ;
  - Etsi laatukriteerit;
  - Rationaalisen valinnan metodologia.

Algoritmien monimutkaisuuden analyysi

Analyysin tarkoituksena on löytää optimaalinen algoritmi. Kriteerinä on työläisyys (algoritmin vaatimien perusoperaatioiden määrä). Työpanoksen funktio on työpanoksen suhde panostietoihin.

Syötetietojen ominaisuudet voivat vaikuttaa monimutkaisuuteen eri tavalla:

määrä;
Arvot;
Sisääntulojärjestys.

Yksi algoritmien kustannusanalyysin yksinkertaistetuista tyypeistä on asymptoottinen, ja siinä on suuri määrä syöttödataa. Käytetty työvoimaintensiteetin funktion estimaatti on algoritmin "monimutkaisuus" , jonka avulla voidaan määrittää työvoimaintensiteetin ja datamäärän välinen suhde. Algoritmien asymptoottisessa analyysissä käytetään matemaattisessa asymptoottisessa analyysissä käytettyä merkintää. Tärkeimmät vaikeusluokitukset on lueteltu alla.

Algoritmin monimutkaisuusfunktion pääarvio (jossa n on datan määrä, "syötteen pituus") on : $f(n)$ ${\boldsymbol {\Theta ))$

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

jos g > 0, n > 0, on positiivisia c 1 , c 2 , n 0 siten, että:

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

osoitteessa ; toisin sanoen, löytyy sellainen ja , joka riittävän suurelle sijoitetaan väliin : ${\displaystyle n>n_{0))$ $c_{1}$ $c_{2}$ $n$ $f(n)$

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

ja .

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

Tässä tapauksessa he myös sanovat, että funktio on asymptoottisesti tarkka estimaatti funktiosta , koska määritelmän mukaan funktio ei eroa funktiosta aina vakiotekijään asti (katso asymptoottinen yhtäläisyys ). Esimerkiksi "heapsort"-lajittelumenetelmässä työpanos on: $g(n)$ $f(n)$ $f(n)$ $g(n)$

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

, eli .

g(n)=n\log n

Alkaen seuraa . $f(n)={\boldsymbol {\Theta }}(g(n))$ $g(n)={\boldsymbol {\Theta }}(f(n))$

${\boldsymbol {\Theta }}(g(n))$ ei ole funktio, vaan joukko funktioita, jotka kuvaavat kasvua vakiotekijään asti. antaa sekä ylä- että alarajat funktion kasvulle. Näitä arvioita on usein syytä harkita erikseen. Arvio on ylempi asymptoottinen estimaatti algoritmin monimutkaisuudesta. Sanomme, että jos: $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}

Toisin sanoen merkintä tarkoittaa, että se kuuluu funktioiden luokkaan, joka ei kasva nopeammin kuin funktio vakiotekijään asti. $f(n)={\boldsymbol {O}}(g(n))$ $f(n)$ $g(n)$

Arviointi määrittää funktion kasvulle alemman asymptoottisen arvion ja määrittelee funktioiden luokan, joka ei kasva hitaammin kuin vakiotekijään asti. , jos: ${\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))

Esimerkiksi merkintä tarkoittaa funktioiden luokkaa, joka ei kasva hitaammin kuin ; tähän luokkaan kuuluvat kaikki polynomit, joiden aste on suurempi kuin yksi, sekä kaikki potenssifunktiot, joiden kantakanta on suurempi kuin yksi. $f(n)={\boldsymbol {\Omega }}(n\,\log n)$ $g(n)=n\,\log n$

Tasa -arvo pätee jos ja vain jos ja . $f(n)={\boldsymbol {\Theta }}(g(n))$ $f(n)={\boldsymbol {O}}(g(n))$ $f(n)={\boldsymbol {\Omega }}(g(n))$

Algoritmien asymptoottisella analyysillä ei ole vain käytännön, vaan myös teoreettista merkitystä. Esimerkiksi on todistettu, että kaikki elementtien parittaiseen vertailuun perustuvat lajittelualgoritmit lajittelevat n elementtiä ajassa vähintään . ${\boldsymbol {\Omega ))(n\,\log n)$

Tärkeä rooli algoritmien asymptoottisen analyysin kehittämisessä oli Alfred Aholla , Jeffrey Ullmanilla , John Hopcroftilla .

Vaikeusluokat

Klassisen teorian puitteissa ongelmat luokitellaan niiden monimutkaisuuden mukaan ( P-kova , NP-kova , eksponentiaalisesti kova ja muut):

"P" - voidaan ratkaista ajassa, polynomiaalisesti lähtötietojen määrästä riippuen käyttämällä determinististä tietokonetta (esimerkiksi " Turingin kone ");
"NP":
- Tehtävät, jotka voidaan ratkaista polynomiajassa epädeterministisellä tietokoneella (jonka seuraavaa tilaa eivät aina aiemmat määritä yksiselitteisesti). Sen työ voidaan esittää jokaisessa moniselitteisyydessä haarautuvana prosessina: ongelma ratkeaa, jos vähintään yksi haara saavuttaa vastauksen;
- Tehtävät, joiden ratkaisu ylhäältä meille annettujen polynomipituisten lisätietojen avulla voidaan tarkistaa polynomiajassa. Erityisesti luokka "NP" sisältää kaikki tehtävät, joiden ratkaisu voidaan tarkistaa polynomiajassa.

Luokka "P" sisältyy "NP":hen. Klassinen esimerkki NP-ongelmasta on " Travelling Salesman Problem ".

Koska "P" sisältyy "NP", ongelman kuuluminen luokkaan "NP" kuvastaa usein nykyistä ymmärrystämme tämän ongelman ratkaisemisesta, eikä se ole lopullista. Yleisessä tapauksessa ei ole mitään syytä uskoa, että P-ratkaisua ei löydettäisi yhteen tai toiseen NP-ongelmaan. Kysymystä luokkien "P" ja "NP" mahdollisesta vastaavuudesta (mahdollisuudesta löytää P-ratkaisu mille tahansa NP-ongelmalle) pidetään yhtenä pääasiallisista algoritmien monimutkaisuuden nykyteoriassa; vastausta ei ole löytynyt toistaiseksi. Sen muotoilu on mahdollista NP-täydellisten ongelmien käsitteen käyttöönoton ansiosta ; kaikki NP-ongelmat voidaan pelkistää niihin — ja jos P-ratkaisu löydetään NP-täydelliselle ongelmalle, niin P-ratkaisu löytyy kaikille NP-ongelmille. Esimerkki NP-täydestä ongelmasta on " Konjunktiivimuotoongelma ".

Algoritmien monimutkaisuuden tutkimukset ovat mahdollistaneet monien klassisten matemaattisten ongelmien ratkaisun tarkastelun uudella tavalla ja joidenkin niiden sarjojen (polynomien ja matriisien kertominen, lineaaristen yhtälöjärjestelmien ratkaiseminen ja muut) löytämisen vähemmän vaativia ratkaisuja. resursseja kuin perinteiset.

Algoritmien teorian matemaattiset sovellukset

Joitakin algoritmien teorian sovelluksia:

massaongelmien tutkimus;
sovellukset matematiikan perusteisiin : rakentava semantiikka ;
sovellukset matemaattiseen logiikkaan : logiikan ja aritmeettisen formalisoitujen kielten analyysi ;
laskennallinen analyysi;
numeroidut rakenteet;
sovellukset todennäköisyysteoriaan : satunnaissekvenssin määritelmät;
sovellukset informaatioteoriaan : algoritminen lähestymistapa tiedon määrän käsitteeseen;
yksittäisten ongelmien ratkaisemisen monimutkaisuuden arviointi;
Algoritmien teorian vaikutus algoritmikäytäntöön [3] .

Muistiinpanot

↑ Semjonov A. L. , Uspensky V. A. Matemaattinen logiikka laskennallisissa tieteissä ja laskennallisessa käytännössä. // Neuvostoliiton tiedeakatemian tiedote , nro 7, s. 93-103
↑ Uspensky V. A. , Semjonov A. L. Ratkaistavat ja ratkaisemattomat algoritmiset ongelmat. // Kvant , 1985, nro 7, s. 9-15
↑ V. A. Uspensky , A. L. Semenov Algoritmien teoria: tärkeimmät löydöt ja sovellukset, M., Nauka , 1987, 288 s.

Kirjallisuus

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
Donald Knuth . Tietokoneohjelmoinnin taito, osa 1. Perusalgoritmit = The Art of Computer Programming, osa 1. Perusalgoritmit. - 3. painos - M .: Williams, 2006. - 720 s. - ISBN 0-201-89683-4 .
Kolmogorov A. N. Tiedon teoria ja algoritmien teoria. - M .: Nauka, 1987. - 304 s.
Markov A. A., Nagorny N. M. Algoritmien teoria. - 2. painos - M . : Fazis, 1996.

Linkit

Luentoja kompleksisuusteoriasta ja kombinatorisista algoritmeista

Sanakirjat ja tietosanakirjat	Suuri katalaani Iso venäläinen

Matematiikan alat

Portaali "Tiede"

Matematiikan perusteet joukko teoria matemaattinen logiikka logiikan algebra

Lukuteoria ( aritmetiikka )

Algebra
Algebra	Yhtälön ratkaisu
Lineaarialgebra	Vektorilaskenta matriiseja Tensorilaskenta Multilineaarinen algebra
Yleisalgebra	Kommutatiivinen algebra Edustusteoria Differentiaalialgebra Homologinen algebra Yleisalgebra Luokkateoria

Analyysi
Klassinen analyysi	Differentiaalilaskenta Integraalilaskenta
Funktion teoria	Harmoninen analyysi Quaternion Analysis Monimutkainen analyysi mittateoria Reaalimuuttujan funktioiden teoria toiminnallinen analyysi Variaatiolaskelma
Differentiaali- ja integraaliyhtälöt	Dynaamiset järjestelmät ja ergodinen teoria Differentiaaliyhtälöt tavallinen osittaisissa johdannaisissa Integraaliyhtälöt
Vektorianalyysi Globaali analyysi Katastrofi teoria Mukautettu analyysi Sujuva äärettömän pieni analyysi

Geometria ja topologia
Geometria	Algebrallinen geometria Analyyttinen geometria Euklidinen geometria Ei-euklidinen geometria Planimetria Stereometria
Topologia	Yleinen topologia Algebrallinen topologia Differentiaaligeometria ja topologia

Diskreetti matematiikka
Kombinatoriikka graafiteoria

Sovellettu matematiikka
Matemaattinen fysiikka Matemaattinen kemia matemaattinen biologia Matemaattiset tilastot Matemaattinen mallinnus Algoritmien teoria Numeeriset menetelmät matemaattinen taloustiede talousmatematiikka Todennäköisyysteoria Toimintatutkimus Peliteoria

Portaali "Matematiikka"
Luokka "Matematiikka"