border=0

Algemiene oanpak

In krekte beskriuwing fan 'e klasse fan partielrekurzjende funksjes yn' e mande mei de tsiis fan tsjerke jout ien fan 'e mooglike oplossingen foar it probleem fan it begripen fan in algoritme. Dizze oplossing is lykwols net folslein rjochtfeardich, om't it begryp fan in kwalitêre funksje sekundêr is foar it begryp fan in algoritme. De fraach is, is it mooglik om it konsept fan in algoritme direkt te ferklearjen en dan, mei har help, krekt krewearjen en de klasse fan komputerbere funksjes? Soks in sykjen rjochting liedt ta de bou fan in algoritme-modellen fan oare klassen as rekursive funksjes. It haad idee is dat algoritmyske prosessen binne prosessen dy't op in bepaalde wize troch in masine útfierd wurde kinne, sadat it útfieren fan yndividuele operaasjes troch de minske is. It funksjonearjen fan sa'n masine is de útfiering fan in bepaalde algoritme. Op grûn fan de eigenskippen fan it algoritme (seksje 7.1) is it mooglik om algemiene easken foar sokke masines te formulearjen:

1) de natuer fan har funksjonearjen moat diskreet wêze, d. bestiet út aparte stappen *, elk fan elk is allinne dien nei de foltôging fan de foarige;

* Yn Fierdere ynstruksjes oer de útfiering fan 'e stap wurde in ploech neamd.

2) hannelingen moatte deterministysk wêze, d. stappen wurde yn stringige oarder útfierd, en har resultaat wurdt bepaald troch de stap sels en de resultaten fan de foargeande stappen;

3) foardat it wurk begjint, wurdt de masine as earste data út it domein fan 'e algoritme definysje;

4) Foar in definityf tal masinistappen, moat in resultaat krigen wurde (of ynformaasje oer wat as gefolch is as gefolch);

5) de machine moat universele wêze, d. sadat it brûkt wurde kin om elk algoritme út te fieren.

De ienfâldiger de struktuer (dat is it apparaat) fan 'e beskreaune masine en de mear elemintêre syn stappen, de mear reden om te leauwen dat syn wurk de útfiering fan' e algoritme is. Om de fraach te beantwurdzjen, hokker masine operaasje-stappen moatte oan elemintêre oanbean wurde, lit ús weromkomme yn 'e omstannichheid dat wy be>finite alfabet. De needsaak fan finiteness fan it alfabet is in dúdlike konsekwinsje fan it feit dat de oplossing yn in finite oantal stappen krigen wurde moat. As de ynformaasje net presintearre is yn in diskrete foarm, bygelyks in echte nûmer, dan is de ferwurking yn it algemien gefal in unfinityf tal stappen befetsje (bygelyks de sifers fan it nûmer te finen of de fjouwerkantwurde út 2) te finen. Sa wurdt it algoritme útskreaun as in definitive folchoarder fan aksjes dy't útfierd binne op data dy't fertsjinwurdige wurde mei in finite alfabet. Mei it each op it hjirboppe wurdt de definysje fan 'e algoritme dat VM Glushkov jout [12, p.38] dúdlik:

In algoritme is in finite systeem fan regels om konvertearjen fan ynformaasje (gegevens) oer elk finite alfabet.

Lit de boarnegegevens fan it domein fan 'e algoritme fertsjintwurdige wurde troch it alfabet A en foarmje in definitive folchoarder fan tekens { a 1 ... a n } - dizze folchoarder wurdt in wurd neamd. As gefolch fan de algoritmeútfiering sil in nij wurd { b 1 ... bm } foarme wurde, fertsjintwurdige, yn algemien, yn in oar alfabet 6. Op 'e earste kear, om sokke transformaasje út te fieren, binne de folgjende operaasjes (stappen) ûnderskiedend as elementarysk:

1) de ferfanging fan ien karakter fan it orizjinele wurd in i troch it teken b j út it alfabet B ;

2) fuortheljen fan it teken fan it orizjinele wurd;

3) taheakke oan it orizjinele wurd in teken út it alfabet B.

As in alfabetysk karakter yn 'e alfabetten opnommen is , wurdt it tafoeging fan it wurd op' e lofter of rjochter dit wurd net feroare (analogue fan numerike nul), dan is it maklik te sjen dat de operaasje (2) nimmen mear is as it ferbrekken fan in i mei in lege teken, en de operaasje (3) is de ferfanging fan it lege teken troch it teken b j . Sa wurde alle mooglike alfabetyske transformationen ferlege foar de operaasje (1) -replikaasje fan ien karakter troch in oar. It is dêrom dat it funksjonearjen fan in abstrakte masine fergrutte wurdt omdat it tekenjen fan 'e karakters (dat lêzen en te erkennen hat) skreaun yn' t ûnthâld (as in endless tape), en ôfhinklik fan syn steat en wat it symboal liket te sjen , it ferfangt it mei in oar symboal; Dêrnei giet it yn in nije state, lêst it folgjende karakter, en sa op. foardat it team it wurk stoppe. Om't sokke masines in gewoane model, teoretyske bou, binne se abstrakte masines neamd en wurde beskôge as ien fan 'e mooglike universele algoritmyske systemen.

It konsept fan 'e algoritme as in abstrakte masine waard hast simultaneit (1936 - 1937) troch de Ingelske wiskundige Alan Turing en syn Amerikaanske kollega Emil Post. De hege betsjutting fan har konstruksjes is ek yn it feit dat se yn in abstrakte foarm de wichtichste funksjes fan echte data-ferwurkingsapparaten (kompjûters) foarstelle, dy't allinich nei 8-9 jier ferskynden.





Sjoch ek:

Foarbyld 5.2

Haadstik 9. Understanding fan de steat masine

Grafike foarm fan opnimmen

Foarbyld 7.9

Foarbyld 4.6

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

2019 @ edudocs.fun