border=0

Soft-definition algoritme

Histoarysk is de term "algoritme" ûntstien út 'e famyljelid fan in Uzbekistyske wiskundige fan' e 9e ieu, Muhammad ibn Musa al-Khorezmi, dy't earst de regels fan fjouwer basearre arithmetike operaasjes formulearre. Yn earste ynstânsje wie it dizze regels dy't algoritme neamd waarden, mar dan waard de term foaral yn 'e wiskunde fierder ûntwikkele - elke metoade fan berekkening, dy't deselde is foar in beskate klas fan ynputgegevens, bygelyks it fûnen fan' e derivative fan in funksje, waard de algoritme. Ien fan 'e wichtichste taken fan it learen fan wiskunde is krekt de ûntwikkeling fan algemiene komputative algoritme. Mei oare wurden, as in studint leard wurdt om in kwalifikaasje te kombinearjen troch in kolom twa nûmers, dan wurdt bepaald dat hy net leart om de bepaalde selektearre nûmers te multipline, mar in universele metoade (algoritme), dy't letter brûkt wurde kin om it produkt fan alle pear finitennûmers te finen.

Der binne in soad fergelykbere foarbylden, en net allinich yn wiskunde - de term "algoritme" is gewoan brûkt. Hjirtroch is de fraach ûntstien: is it mooglik om in algemiene en krekte definysje fan in algoritme (de alinea 's "algoritme") op te bouwen , bygelyks om it te brûken om te ûnderskieden of in aggregaat fan oantsjuttingen is in algoritme of net? Op it nivo fan geweldich sin kinne wy ​​sizze dat in algoritme in kreft definiearre (single-wearde) sesje fan ienfâldige (elemintêre) hannelingen dy't in oplossing foar elke probleem leverje fan in bepaalde klasse. Dizze ferklearring kin lykwols net as stringende definysje fan 'e algoritme nommen wurde, om't it oare ûnbegryplike begripen brûke kin - ienheid, elemintariteit, ensfh. It begryp kin klarifye wurde troch it bepalen fan in list mei mienskiplike eigenskippen dy't karakterisearre binne foar algoritmen. Dit ûnder oaren:

1. Dissigens fan 'e algoritme betsjuttet dat de algoritme ferdield is yn aparte stappen (aksjes), en de neikommende stap kin allinich dien wurde nei alle operaasjes yn' e foarige stap binne foltôge. Yn dat gefal is de set fan intermediate gegevens finite en it wurdt neffens guon regels fan 'e gegevens fan' e foarige stap.

2. De determinisme fan 'e algoritme bestiet yn it feit dat de totaliteit fan intermediate wearden op elke stap ienichste bepaald wurdt troch it systeem fan wearden dy't beskikber binne op' e foargeande stap. Dit eigenskip betsjuttet dat it resultaat fan it útfieren fan in algoritme net ôfhinklik fan wa (of wat) it docht (dus op 'e útfierer fan' e algoritme), mar wurdt allinich troch de ynputgegevens en stappen (folchoarder fan hannelingen) fan 'e algorithm sels bepaald.

3. Eardere stappen: it wet fan it folgjende systeem fan wearden fan 'e foarige berjochten moat ienfâldich en lokale wêze. Hokker stap (aksje) kin elemintêr beskôge wurde wurde bepaald troch de skaaimerken fan 'e útfierer fan' e algoritme.

4. Directionaliteit fan 'e algoritme: as de metoade fan it folgjen fan oanfoljende mjitten fan elke earste begjint net ta in resultaat, dan moat it fêstlein wurde wat wat as gefolch fan it algoritme beskôge wurde moat.

5. Mass algoritme: it earste systeem fan wearden kin selektearre wurde fan in bepaalde set.

De lêste eigendom betsjut dat ien algoritme, d. De selde folchens fan aksjes, yn algemien, kin brûkt wurde om in beskate klasse (dus, in soad) taken op te lossen. Foar praktyk en benammen it probleemjen fan in probleem op in komputer, is dizze eigenskip essinsjeel, om't de regelwearde fan in programma de hegere is, hoe grutter it berik fan likense taken is dat it makliker te meitsjen. Foar de bou fan in algoritmyske teory is dit eigendom net essensjaal en ferplichtend.

It begryp fan 'e algoritme, yn guon ekstreemde troch it opnimmen fan eigenskippen 1-5, kin ek net rigint beskôge wurde, om't it wurdearring fan' e eigenskippen de termen "kwantiteit", "metoade", "ienfâldich", "lokale" en oaren brûkte, de krekte betsjutting dêrfan net fêstige is. Yn 'e gefolch wurdt dizze definysje leksjes fan / neamd en (somtiden wurdt it yntuïtypt neamd ) it begryp fan in algoritme.

De fraach is ûntstien: is it echt be>

In oar reden dy't de bou fan in krekte definysje fan 'e algoritme nedich wie, wie de dûbeldens fan' e begryp 'elemintêre stap' by it útfieren fan algoritmyske aksjes. Wylst de wiskunde ûndersocht om numerike objekten te studearjen, waarden aksjes mei har ferdwûn ta in bepaalde folchoare fan komputaasjeteams, en arithmetike operaasjes waarden as elementarysk beskôge, en ek ferskate logyske wurden dy't relatearre binne om te kontrolearjen fan de relaasjes tusken de mjittingen (lykweardigens, yngling, mear, minder, ensfh.). Letter wikselde de wiskunde nei de stúdzje fan eigenskippen en aksje mei komplekse objekten - fekkers, matrizen, sets, funksjes - en de begryp fan 'e elemintêre aard fan in algoritme stap wie net >

Yn dy situaasjes wêrby't de opdracht de bou fan meardere algoritmen foar it oplossen bringt, fan 'e teoretyske en praktyske punten is it fan essinsjeel om har te fergelykjen en it effisjintal algoritme te kiezen, dat ek ûnmooglik is sûnder syn stringende definysje.

Sa waard it nedich om it begryp "algoritme" goed te definiearjen , d. as algemien in definysje as mooglik foar alle tinkbere soarten fan algoritme. Yn 'e jierren '20. XX ieu. De bou fan 'e definysje fan' e algoritme is ien fan 'e sintrale mathemale problemen wurden. Dizze definysje, op 'e iene kant, moat oerienkomme mei de essensje fan it yntuitive begryp fan' e algoritme, en op 'e oare kant, wurde formele strikt. Besocht om sokke konsept te formulearjen liede ta it ferskinen yn 'e jierren '30. XX ieuske teory fan algoritme as in ûnôfhinklike wittenskip, dy't, mei wiskundige logika, de basisynstruminten fan wiskunde ûndersiket - metoaden fan bewiis, metoaden fan it bouwen fan axiatyske teoryen, eigenskippen fan wiskundige prosedueres, ensfh. As yn 'e jierren 40 - 50. It begjin fan 'e rappe ûntwikkeling fan kompjûterjen en wittenskippers dy't ferbân hâlde mei har operaasje en gebrûk, die bliken dat de teory fan algoritme ek de basis fan dizze wittenskip wêze moat , om't in kompjûter allinich prosedueres útfiere kin dy't algoritme fertsjintwurdige wurde. Elke programma is nimmen mear as de opname fan in algoritme yn in taal dy't "útfine" kin troch in útfierer - in komputer. Sa is, fanút in praktyske tema, it ek wichtich om it begryp fan in algoritme te klarjen.

Ferbining fan it begryp fan 'e algoritme wurdt makke yn it ramt fan algoritmyske modellen. It model beskiedt in opset fan ynstruminten, it gebrûk fan dat is tagelyk by it oplossen fan in probleem, d. list fan elemintêre stappen, manieren om de folgjende stap te bepalen, ensfh. Algoritmyske modellen kinne teoretysk en praktysk wêze. Fanút in teoretysk perspektyf, fan grutste be>universele wêze, d. soe elke algoritme beskriuwe, en op 'e oare hân, sa ienfâldich as mooglik , d. de minimale middels brûke om it probleem te heljen. De easken fan ienfâld is wichtich om de echt needsaaklike eleminten en eigenskippen fan 'e algoritme te markearjen en bewiis foar de algemiene ferklearring oer dizze eigenskippen. Yn praktyske en oanwêzige modellen is de behearsking fan programmearring en komputaasjene effisjinsje mear betsjutting, dus binne har middels - in set fan elemintêre stappen, en sa op - binne folle riker en komplekser, dy't de teoretyske analyze maklik makket.

Yn 'e teoretyske oanpak fan' e bou fan in strikte definysje fan it begryp fan in algoritme binne trije wichtige rjochtingen historysk útsteld.

De earste rjochting is oansluten by it beskôgjen fan algoritmen dy't ien jilde om de wearde fan numerike funksjes te berekkenjen dy't ôfhinklik binne fan yntegerwearden fan 'e arguminten - soksoarte funksjes wurde rekkenberamd neamd . It begryp fan in komputerbere funksje is net strang, lykas it konsept fan in algoritme. Troch de wurken fan A. Tsjerke, K. Gödel, S. Kleene, is de identiteit fan 'e klasse fan oeral definieare komputerbere funksjes mei de klasse fan partielrekursive funksjes, dy't stringend definiearre is, fersterke. Dit hat ús tastien om it probleem fan algoritmyske ferlientigens te ferleegjen nei it bewiis fan 'e mooglikheid (of ûnmooglikheid) fan it konstruearjen fan in rekursive funksje dy't it probleem beheart. It wie op dy manier dat A. Cherch de ûnstjerlikheid fan ien fan 'e problemen fan wiskundige logika bewiisd hat, de kalkulaasje fan' e wierheid fan predikaaten.

De twadde rjochting is ferbûn mei masinesmateriaal. It haad idee fan dizze rjochting is dat algoritmyske prosessen binne prosessen dy't útfierd wurde kinne troch in passend arranzjearre "masine". Yn oerienstimming mei dit idee beskreaun se earder in smelle masine fan masines yn krekte wiskundige termen, mar waard bewiisd dat troch dizze masines it mooglik is om alle algoritmyske prosessen út te fieren of neimittearje dy't eartiids troch mathematikers beskreaun binne. Dizze oanpak waard ûntwikkele yn 'e wurken fan E. Post en A. Turing tagelyk mei de hjirboppe neamde oanpak. De bewiis fan 'e algoritmyske beslútigens fan' e probleem wurdt ferlege oan it bewiis fan it bestean fan in masine dy't it liedt.

De tredde rjochting is ferbûn mei it konsept fan normale algoritme, yntrodusearre en ûntwikkele troch de Russyske mathematiker A. A. Markov yn 'e begjin 1950er jierren. XX ieu.

Yn 'e neikommende paragrafen wurde alle trije gebieten yn meardere diskusjes besprutsen. Mar foardat it oanwêzich is, wol ik graach sjen dat in strang formalisearre approach foar it definiearjen fan it begryp "algoritme" wurdt allinich direkt yn 'e wiskundige teory fan algoritme sels brûkt, wêrby't de algemiene eigenskippen fan algoritme ûndersocht wurde, it bewiis foar algoritmyske decidabiliteit wurdt útfierd, ensfh.In praktyske tapassingen, ynklusyf yn kompjûterwittenskip, strik formalisearring kin liede ta in wichtige komplikaasje fan 'e taak; Tagelyk kinne jo in oantal situaasjes oantsjutte yn hokker ôfwizing fan dat is tagelyk.

1. It gebrûk fan útfierders kin komplekse kommando's útfiere. De definysje fan 'e term "algoritme-performer" is gewoan fanselssprekkend:

De útfierer fan 'e algoritme is in ûnderwerp of in apparaat dat goedmeitsje kin om de beskriuwing fan' e algoritme goed te ynterpretearjen en út te fieren de list fan aksjes dy't ynhelle binne.

Ynstruksjes foar it útfieren fan aksjes foar elke útfierer wurde formulearre yn in taal dy't in set fan tsjinstwurden befettet mei aksjes (kommando's), en ek syntaktyske regels foar kombinaasje fan har. It set fan jildige kommando's foarmet in systeem fan ploegen fan 'e Executive (SKI). Difference mei SKI ferskate keunstners kinne de beskriuwing fan 'e aksje detaillearje. As jo ​​hjirûnder sjen litte, is in elemintêre (ienfâldichste) aksje yn 'e ferwurking fan diskrete ynformaasje de ferfanging fan ien teken troch de oaren. Jo kinne lykwols in abstrakt of echte apparaat bouwe dy't in folsleine keten fan sokke elementêre aksjes dwaan kinne neffens de regel yn 'e regel - in soarte kompleks (yntegraal) aksje. By it bouwen fan in algoritme foar sa'n artist, moat de ûntwikkelder allinich de sesje fan yntegraal kommando's opjaan, en har omskriuwing yn in keten fan echte elemintêre stappen wurdt dien troch de útfierder sels. Sa'n "multi-stage" algoritmatisaasje is breed brûkt yn kompjûterbehear.

Wierlikens moat elemintarysk beskôge wurde as de aksjes fan de prosessor (hoewol har totale nûmer yn moderne ferwurkingen berikt inkele hûndert of sels dûzen) - se wurde masinesbehearders neamd , en harren beëiningen binne masineskoades. It earste (leechste) nivo wêryn in ôfwiking fan masjestrukturen foarkomt, is de assembler-koade - in ynterne (ie, apparaat-ôfhinklike) taal. It kombinearjen fan elemintêre aksjes yn komplekse kommando's op dit nivo is noch net slagge en it totale oantal assemblerkommando's fynt oerien mei it oantal prozessorbehearders, lykwols wurdt de symboalyske representaasje fan masinekoades en prosessor registers - mnemonics - brûkt , wat makliker is foar de brûker as binêre komputerkoade.

De oersetting fan memonemyen yn masinekommando's wurdt útfierd troch in assemblerprogramma; It is by har dat de programmator mei as útfiner behannelet. Kommando's dy't in tal primêre aksjes kombinearje, ferskine op heechste nivo-programmearrings, bygelyks yn it programma-tekst it genôch om "Skriuw" te skriuwen , en de oersetter fan 'e taal sil it oersetten yn in folchoarder fan elemintêre stappen: interrupten, transfers, ensfh. Yn relaasje mei de programmer de ynsteller yn dit gefal It bliuwt de programmierspraat oersetter. In noch grutter yntegraasje fan elemintêre kommando's kin bepaald wurde troch it applikaasjeprogramma, dat is de útfierer yn relaasje mei de einbehearder. De SKI fan sokke keunstners befettet alle kontrolearrings dy't presintearre wurde yn 'e foarm fan menus, on-screen-knoppen, ynstellingsfinsters en oare interface-eleminten. Mei ien inkelde kommando kin in ketting fan komplekse aksjes feroarsake wurde, bygelyks de alaarming fan in protte tekstlinen.

As jo ​​algoritme skriuwe, kinne situaasjes mooglik wêze as de presintaasjetaal fan 'e algoritme is formele, mar it brûkt komplekse kommando's dat de útfierder sels oersettet nei it nivo fan echte elemintêre aksjes.

2. De admission fan net string formalisaasje fan 'e presintaasje fan algoritmen, as de útfierer in persoan is. In persoan hat syn eigen tinken en kennis, basearre op hokker hy de kompensaasje fan 'e algoritme kompensearje kin, aksjes útfiere en resultaten berikke. Sokke algoritmen moatte noch minder strang wurde beskôge as dy yn it begjin fan 'e rubryk beskôge wurde, om't se yn' e regel allinich de neikommende eigenskippen hawwe. Foarbylden lykas boarstreizen, ynstruksjes foar it brûken fan húshâldlike apparaten, algoritme foar it oplossen fan skoalleproblemen.

3 It útwreidzjen fan de tapassing fan it begryp fan 'e algoritme oan in folchoarder fan eventuele diskrete aksjes. Troch definikaart moat de algoritme needsaaklik wêze mei de ferwurking fan diskrete ynformaasje. Dochs wurdt deselde termyn ek brûkt om aksjes foar it bestjoeren fan in útfierder dy't gjin ynformaasje direkt feroarje. Bygelyks yn 'e skoalle fan informatika binne ûnderwiisynstellers "Draftsman", "Parketchik", "Turtle" breedte brûkt , de SKI dêr't ûnder oaren om it skerm hinne rûnen en útfierd wurde fan guon operaasjes ("tekenje" , ensfh.). Itselde jildt foar de ynstruksjes foar it bestjoeren fan ienheden en apparaten.





Sjoch ek:

Normaal Markov-algoritme

It algemien skema fan ynformaasjeferfier yn 'e kommunikaasjeburo

Ynformaasje en alfabet

Probleemintwurding

String verbal algoritme

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

2019 @ bibinar.info