border=0

Fergeliking fan algoritmyske modellen

Lit ús weromkomme nei de formulearring fan it probleem, de oplossing dêrfan is besprutsen. Guon teoretyske problemen (bygelyks it probleem fan algoritmyske solvabiliteit) en praktyske behoeften (bygelyks it needsaak om de prinsipes fan 'e operaasje fan apparaten dy't automatisearre ynformaasjeferwurking produsearje) soenen de bou fan in stringende definysje fan it algoritme ferplette. Ferskate oplossings foar it probleem liede ta de bou fan de saneamde abstrakte algoritmyske systemen (dy wurde ek algoritmyske modellen neamd). Allinnich inkele fan harren wurde beskôge; har folsleine list kin yllustrearre wurde troch it skema as yn fig. 7.3. Litte wy besykje te finen wat de relaasje fan yndividuele modellen is.

Alle algoritmyske taken kinne ferdield wurde yn twa grutte lessen: de earste is de taken dy't ferbûn binne mei de berekkening fan de wearde fan in funksje; De twadde is taken dy't relatearre binne oan de erkenning fan it gehiel fan in objekt op in bepaalde set (dat is lykweardich foar in antwurd op 'e fraach: in doel hat in eigenskip besiket eigendom?). Yn it earste gefal begjint de Q- algoritme mei de oarspronklike gegevens te wurkjen - it wurd P, gearstald op basis fan it alfabet A, en yn in finite oantal stappen (transformationen) moat it resultaat P k = f Q (P) stoppje en produsearje . It resultaat hinget (in funksje) is op it boarne wurd, lykas de ferwurkingsseking, d. algoritme sels. Yn dit gefal wurdt de berekkening begrepen yn in brede sin - as in alfabetyske transformaasje.

Yn taak dy't relatearre binne oan de twadde klasse, as gefolch fan de útfiering fan it algoritme, krije wy in antwurd op 'e fraach: "Is it wier dat x M ? of, wat itselde is, wurdt it predikaat x kontrolearre M en út ien fan twa resultaten útjûn: TRUE of FALSE. Dizze klasse kin beskôge wurde as in fariasje fan 'e earste, omdat it predikaat in funksje hat dy't twa wearden nedich is ôfhinklik fan de betingsten. Dochs is de ôfskieding fan dizze klassen fan problemen nuttich, om't it liedt ta twa wichtige begripen fan 'e teory fan algoritme - in komputerbere funksje en in lestige betingst.

In funksje wurdt rekkenskipber as der in algoritme is dat syn wearde berekkent.

In set wurdt as solvabel neamd as der in algoritme is dat foar elke objekt lit ús bepale oft it heart by in befêstige set of net.

As earder neamd binne dizze definysjes net formal strak, d. Se litte wy ús net prate wurde oft in bepaalde funksje útwurke is, of net (of, wat is itselde: hoe kinne wy ​​de natuer fan 'e funksje bepale, kinne wy ​​in algoritme oanmeitsje om it te berekkenjen?). Hjirtroch hat de tsiis fan 'e tsjerke, dy't argumentearre dat elk diels rekurvende funksje komputerber wie, tige wichtich foar it bouwen fan in teory fan algoritmen. Mei oare wurden, as wy it funksjonearjen fan 'e funksje mei superposysje, rekreaasje en minimisearring fan' e simpelste arithmetyk, dan is der in algoritme dat it berekkent. Dit waard folge troch de Turing-thesis, dy't bewiisde dat foar elke komputerbere funksje in Turing-masine oanbiede koe dy't it berekkent. It kin bewiisd wurde dat Post algoritmen wurde ek ferkocht oan algoritmen dy't útfierd binne mei diels rekurvende funksjes. De konversaasje is ek wier. Benammen de problemen foar it Postautomint yn haadstik 7.3.2 binne in foarbyld fan 'e ymplemintaasje fan ien fan' e ienfâldichste rekursive funksjes - de direkte folgjende funksje. Letter waard in teoremus op 'e fergrutting fan ien algoritmyske model nei in oar bewearde, wêrtroch't in ferklearring wie: "elke rekursive funksje kin berekkene wurde mei de gearhing fan de Turing-masine" of "foar elke probleem oplost troch de Turing-masine, is der in beslút normaal Markov-algoritme". Sa kinne alle modellen lykweardich wurde, dy't in djippe betsjutting sjen litte, om't it resultaat fan ynformaasjeferwurking, fansels, bepaald wurdt troch de natuer fan 'e funksje (algoritme) en de ynputgegevens, mar net ôfhinklik fan it type algoritmyske model.





Sjoch ek:

De klasse fan algoritmyske (of masine-komputerbere) dielsnûmerfunksjes fermindere mei de klasse fan alle parten rekkenjende funksjes.

Foarbyld 4.3

Nûmersystemen

Serial data transmission

Foarbyld 4.13

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info