Formalūs atlikėjai, tai yra tie, kurie nesupranta algoritmo prasmės, o tik atlieka nurodytus veiksmus ir negali jų redaguoti: šuo, kuris nesupranta komandų prasmės, televizorius, apskritai - bet kokie negyvi atlikėjai. . Neformalūs – tie, kurie supranta algoritmo prasmę ir gali jį pakoreguoti – tarkime, žmogus.

Kiekvienas algoritmas daro prielaidą, kad yra tam tikri pradiniai arba pradiniai duomenys, o taikymo rezultatas leidžia gauti tam tikrą norimą rezultatą. Pavyzdžiui, algoritme su kūrėju pradiniai duomenys yra didelės ir mažos pakuotės turinys, vanduo. Norimas rezultatas – paruoštas naudoti plėvelės ryškalas. Skaičiuojant matricos rangą, pradiniai duomenys yra stačiakampė lentelė, sudaryta iš racionalių skaičių, rezultatas yra natūralusis skaičius, kuris yra šios matricos rangas.

Toliau kiekvieno algoritmo taikymas vykdomas atliekant atskirą tam tikrų elementarių veiksmų grandinę (seką). Šie veiksmai vadinami žingsniais, o jų atlikimo procesas – algoritminiu procesu. Taigi pastebima algoritmo diskretiškumo savybė.

Tarp galiojančių pradinių algoritmo duomenų gali būti tokių, kuriems jis taikomas, t.y. pradedant nuo kurių galite gauti norimą rezultatą, tačiau gali būti tokių, kuriems šis algoritmas netaikomas, t.y. pradedant nuo kurių negalite gauti norimo rezultato. Algoritmo nepritaikymas galiojantiems pradiniams duomenims gali būti susijęs arba su tuo, kad algoritminis procesas niekada nesibaigia (šiuo atveju sakoma, kad jis yra begalinis), arba tame, kad jo vykdymas vieno iš žingsnių metu susiduria su kliūtimi, pasiekia aklavietė (šiuo atveju sakoma, kad baigiasi be rezultato)

41 .

Formalus Tiuringo mašinos analogas.

Tiuringo mašina (MT) susideda iš skaičiavimo juostos (padalytos į langelius ir apribotos kairėje, bet ne dešinėje), skaitymo ir rašymo galvutės, juostos mechanizmo ir veikiančios pavaros, kuri gali būti vienoje iš diskrečiųjų. būsenos qo, q1,..., qs, priklausančios kokiai nors baigtinei rinkiniui (vidinių būsenų abėcėlė). Šiuo atveju qо vadinama pradine būsena.

Skaitymo ir rašymo galvutė gali perskaityti darbinės abėcėlės raides A = [a0, a1,..., at), jas ištrinti ir atspausdinti. Kiekvieną juostos langelį kiekvienu laiko momentu užima raidė iš aibės A. Dažniausia raidė yra a0 – „tarpas“. Galvutė kiekvienu laiko momentu yra virš tam tikros juostos ląstelės - esamos darbo ląstelės. Juostos pavaros mechanizmas gali perkelti juostą taip, kad galvutė būtų virš gretimos juostos ląstelės. Tokiu atveju galimas perėjimas už kairiojo diržo krašto (LC), kuris yra avarinis (nepriimtinas), arba mašinos sustojimas (MS), kai mašina atitinka nurodymą sustoti.

MT veikimo tvarka (su darbine abėcėle a0, a1,..., at ir būsenomis q0, q1,..., qs) aprašyta Tiuringo mašinos lentelėje. Ši lentelė yra matrica su keturiais stulpeliais ir (s + 1) (t + 1) eilutėmis. Kiekviena eilutė atrodo taip

Turingo skaičiuojamosios funkcijos. Turingo disertacija.

Turingo disertacija: abstrakti Tiuringo mašina gali atlikti bet kokią operaciją, kuri paklūsta tam tikroms taisyklėms ir šia prasme yra grynai mechaninė.

Mašina veikia pagal programą taip.

Pradiniu laiko momentu juostoje įrašoma tam tikra daugybės grandinėlė V * , visi kiti juostos langeliai užpildyti simboliu #. Valdymas pradiniu momentu yra būsenoje q 0 , skaitymo ir rašymo galvutė nuskaito kairįjį įrašytos eilutės simbolį. Mašinos veikimas susideda iš šio elementarių veiksmų ciklo kartojimo:

1. Simbolio nuskaitymas iš priešais esančios ląstelės.

2. Tinkamos komandos, būtent komandos, radimas qa → q’a’d, Kur q- tam tikra kontrolės būsena, a- personažas, kurį reikia perskaityti.

3. Vykdykite rastą komandą, kuri yra tokia. Simbolis įrašomas į galvos nuskaitytą ląstelę a', simbolis a- ištrinamas, kontrolė pereina į valstybę q' o galva juda santykyje su d. Jeigu d=r galva pasislenka viena ląstele į dešinę, jei l - perkelia vieną langelį į kairę, p– neatliekamas joks judesys. Sustabdoma, jei kitame žingsnyje netaikoma jokia programos komanda. Turingo mašinos rezultatas – juostoje įrašyta grandinė.

Informatikos matematiniai pagrindai

A.G. Gein

Programa

№_LAIKRAŠČIAI	Paskaita
	1 paskaita.Kas yra „matematiniai kompiuterių mokslo pagrindai“. Kodėl kompiuterių mokslas dažnai laikomas panašiu į matematikos mama? Ar tai tiesa? Ar įmanoma informatika be matematikos? Kokią matematiką reikia išmokti? informatika? Ar mokyklinė matematika gali būti informatikos pagrindas? Informacija ir jos kodavimas. Kodų matematika. Klaidų taisymo kodai. Ekonomiškas kodavimas.
	2 paskaita.Formalių atlikėjų matematiniai modeliai. Kas yra formalus informacijos apdorojimas? Galas- naujos mašinos. Kas pirmiau: kalba ar atlikėjas? Kalbos gramatika. Pripažintos kalbos. Universalios versijos teli (Turingo mašina, Pašto mašina).
	3 paskaita.Algoritmas ir jo savybės. Algoritminis neapibrėžtumas. Apskaičiuojamumas. Sudėtingumas.
	Testas Nr.1.
	4 paskaita. Grafikai. Grafikai ir dviženkliai. Kokiose užduotyse jos kyla? Įvairios grafų savybės (Eulerio, Hamiltono) naujienos, planiškumas, dvišališkumas). Tinklai. Teka tinklais. Grafiko vaizdavimas. Pagrindiniai grafų algoritmai.
	5 paskaita. Loginiai modeliai kompiuterių moksle. Teiginių algebra. Būlio funkcijos. Normalios formos. Pilnas Būlio funkcijų klasės. Relių kontaktų schemos. Vožtuvai. Kompiuterio procesoriaus ir atminties matematiniai modeliai. Predikatai ir santykiai. Reliacinė algebra. Reliacinių DBVS teoriniai pagrindai. Loginės programavimo kalbos ir jų matematinis pagrindas.
	Testas Nr.2.
	6 paskaita. Kompiuterių skaičių teorija ir skaičiavimo geometrija. Kodėl kompiuterių moksle reikalinga skaičių teorija? mokslai? Lenktynės dėl pirminių skaičių. Kaip koeficientuoti skaičių? Kuo skiriasi teorinė geometrija ir kompiuterija? Kodėl popieriuje viskas sklandžiai, o kompiuteryje – gremėzdiška? Pagrindinės skaičiavimo taisyklės ir algoritmai geometrija.
23/2007	7 paskaita. Duomenų apsauga. Simbolinės informacijos apsauga. Ką reikia saugoti? Elektroninis parašas. Sistemos patikrinimas. Viešojo rakto kriptosistemos. Grafinės informacijos apsauga. Elektroninių vandens ženklų matematika.
24/2007	8 paskaita. Informatikos matematinių pagrindų mokymo metodų pagrindai.
	Baigiamasis darbas

2 paskaita.
Formalių vykdytojų matematiniai modeliai

„Šiame tuščiame pasaulyje malonė yra šalta“. Šią frazę sukūrė kompiuteris, naudodamas vieną pirmųjų natūralios kalbos teksto generavimo programų. Tačiau šia fraze perteikiama emocija, žinoma, kompiuteriui nepasiekiama. Ir kompiuteris negali suprasti šios frazės reikšmės. Nes jis tik formalus atlikėjas.

Mūsų visuomenės sąmonėje žodis „formalus“ dažniausiai turi neigiamą atspalvį. Paniekinamą etiketę „formalistas“ suteikiame pareigūnui, kuris veikia tik pagal jam duotus nurodymus, nenorėdamas gilintis į jam keliamos problemos esmę.

Bet ar visada blogai būti oficialiu atlikėju? Ar aviganio šeimininkas apsidžiaugs, kai išgirs komanda „Fas! jo keturkojis susimąstys, ar verta kištis su banditu. Arba kai lėktuvas, reaguodamas į piloto vairo judesį, toliau skrenda tuo pačiu kursu, nes nenorite sukti. O branduolinio reaktoriaus operatorius, atsisakęs instrukcijų, jį valdys pagal užgaidą. Sutikite, kad net ir žmogui kartais tiesiog būtina būti formaliu atlikėju. Kalbant apie automatinio informacijos apdorojimo įrenginius, neoficialus maršrutas tiesiog neįmanomas. Prisiminkime, kaip pažymėta 1 paskaitoje, kompiuterių mokslas nagrinėja automatizuotus informacijos apdorojimo procesus.

Informacijos apdorojimas (transformavimas) yra gana plačiai suprantamas informacinis procesas. Informacijos apdorojimas suprantamas kaip naujos informacijos gavimas iš esamos informacijos arba informacijos pateikimo formos pakeitimas.

Detektyvas surinko įkalčius ir nustatė, kas padarė nusikaltimą. Matematikas palygino jam žinomus teiginius ir įrodė naują teoremą. DI. Mendelejevas, remdamasis informacija apie chemines elementų savybes, suformulavo periodinį dėsnį. Visuose šiuose pavyzdžiuose nauja informacija atsirado dėl informacijos apdorojimo.

Informacijos apdorojimu reikėtų pripažinti ir dviejų skaičių sumos apskaičiavimą – juk iš dviejų žinomų duomenų gaunamas naujas, anksčiau nežinomas. Informacijos apdorojimas yra, pavyzdžiui, sakinio vertimas iš rusų kalbos į užsienio kalbą.

Iš pirmo žvilgsnio pastebimas didelis skirtumas tarp ankstesnėse dviejose pastraipose nurodytų informacijos apdorojimo procesų. Pagrindinis skirtumas čia yra tas, kad norint surasti nusikaltėlį ar įrodyti naują teoremą, nėra ir negali būti nurodytos griežtos taisyklės, kaip turi būti apdorojama pradinė informacija. Kaip sakoma, tokiais atvejais žmogus veikia euristiškai. Sudėdami du skaičius, mes jau vadovaujamės griežtai nurodytomis taisyklėmis. Toks darbas gali būti patikėtas techniniam įrenginiui, kuris sugeba suprasti ir vykdyti jam skirtas instrukcijas. Įrenginiai, kurie valdomi pagal instrukcijas ir atlieka savo darbą automatiškai, vadinami programuojamais ir savo darbą atlieka formaliai.
Visų pirma galime kalbėti apie formalų informacijos apdorojimą. Atlikėjas, atliekantis tokį apdorojimą, neturėtų gilintis į savo atliekamų veiksmų prasmę; todėl formalus informacijos apdorojimas, kaip taisyklė, susijęs su jos pateikimo formos, o ne turinio keitimu.

Taigi apdorojant informaciją patogu suprasti bet kokią jos turinio ar pateikimo formos transformaciją.

Tačiau, kad ir koks būtų informacijos apdorojimo būdas – formalus ar euristinis, kažkas ar kažkas atlieka šį apdorojimą. Paprastai tai vadinama atlikėjas.

Oficialūs atlikėjai gali būti struktūrizuoti labai įvairiai. Norint juos ištirti, kaip ir bet kuriame moksle, naudojamas modeliavimas. Šioje paskaitoje pasakosime, kokie matematiniai modeliai naudojami tiriant formalius atlikėjus.

§ 3. Formalus vykdytojas: automatas

Žmogus labai sėkmingai sukūrė įvairius įrenginius, kurie atlieka tą ar kitą darbą pagal aiškias instrukcijas. Tuo pačiu metu jam nebereikia nuolat būti šalia šio įrenginio, kad jį valdytų. Tokiu atveju jie sako, kad įrenginys darbą atlieka automatiškai, o pats toks įrenginys vadinamas automatiškai.

Tiesą sakant, lošimo automatai yra labai skirtingi. Tai gali būti priemiestinių traukinių bilietų pardavimo mašina, gatavų produktų pakavimo mašina arba bet kokių dalių gamybos mašina. Pastarojo tipo automatai dažnai vadinami pramoniniai robotai.

Informatikos požiūriu nesvarbu, iš ko mašina pagaminta. Svarbu tik tai, kad kai kuriuos signalus ji suvokia kaip komandas ir kiekvienai komandai atlieka tam tikrą veiksmą, pereidama iš vienos būsenos į kitą. Todėl galime daryti prielaidą, kad kiekvienas automatas aprašomas galimų būsenų rinkiniu, galiojančių komandų sąrašu ir sąrašu, iš kurios būsenos į kurią automatas pereina veikiamas kiekvienos komandos. Pavyzdžiui, jei yra tik dvi komandos, jos gali būti pažymėtos raidėmis, tarkime, a Ir b, arba skaičiais, mašinos būsenomis – raidėmis q 1, q 2, ..., kv.m, ir galite išvardyti perėjimo iš vienos būsenos į kitą parinktis naudodami lentelę (žr. 1 lentelę).

1 lentelė

Ląstelė, esanti eilutės ir stulpelio sankirtoje, nurodo būseną, į kurią patenka automatas, jei jis buvo tos pačios stulpelio antraštėje nurodytoje būsenoje ir gavo komandą, nurodytą tos pačios eilutės antraštėje. Visiems aišku, kad tokia lentelė yra tikros mašinos informacinis modelis.

Taip pat automatą galima apibūdinti ir kitu informaciniu modeliu – digrafu*. Dvigrafo viršūnės yra automato būsenos, o lankai – perėjimai iš vienos būsenos į kitą. Kiekvienas lankas turi ženklą, nurodantį, kuri komanda naudojama perėjimui. Tada mašina aprašyta lentelėje. 2, bus rodomas kaip parodyta ryžių. 1.

2 lentelė

Viena iš būsenų vadinama pradine būsena – būtent joje mašina yra prieš pradedant darbą. Sutikime visada žymėti pradinę būseną q 1. Kai kurios būsenos yra galutinės – mašinos atvedimas į tokią būseną yra tikslas valdyti mašiną naudojant vienokią ar kitokią komandų seką. Pavyzdžiui, jei tai yra geležinkelio bilietų pardavimo aparatas, tada pradinėje būsenoje aparatas tikisi, kad monetos pradės tekėti į monetų priėmimo įrenginį. Yra dvi galutinės būsenos: bilieto išdavimas ir pinigų grąžinimas. Be to, yra tarpinių būsenų – skaičiuojant šiuo momentu į mašiną pervestų pinigų sumą. Komandos, kurios perkelia aparatą iš vienos būsenos į kitą, yra monetos įdėjimas į monetų priėmimo įrenginį, bilieto išdavimo mygtuko paspaudimas arba pinigų grąžinimo mygtuko paspaudimas. Tai, kad ši būsena yra galutinė, pažymėsime raide K skliausteliuose šalia šios būsenos pavadinimo. Pavyzdžiui, q 2 (K).

Aišku, kad automato valdymo tikslas yra duoti jam komandų seką, kuri perkelia jį iš pradinės būsenos į kokią nors galutinę būseną. Kadangi kiekviena komanda žymima raide, šio įrenginio suprantamų komandų rinkinys gali būti laikomas tam tikra abėcėle A. Tada komandų seka, t.y. programa bus parašyta kaip žodis šioje abėcėlėje. Pavyzdžiui, žodis aba verčia mašiną, aprašytą lentelėje. 2, nuo pradinės būsenos q 1 valstybėje q 4 . Mes galime pasakyti, kad žodis aba duoto automato dvigrafe apibrėžia tam tikrą maršrutą iš būsenos q 1 valstybėje q 4 .

Visų tų žodžių, kurie perkelia automatą iš pradinės būsenos į vieną iš galutinių būsenų, aibė sudaro tam tikrą formalią kalbą. Ši kalba vadinama kalba, kurią atpažįsta šis aparatas. Jei tam tikrai kalbai yra bent vienas automatas, kurį ši kalba atpažįsta, tada tokia kalba vadinama atpažįstamas.

Įjungta ryžių. 2 parodytas automatas, turintis dvi būsenas - q 1 (K) ir q 2 - ir supranta dvi komandas, kurios žymimos skaičiais 0 ir 1. Nesunku suprasti, kad šio aparato atpažįstama kalba susideda iš tų ir tik tų žodžių, kuriuose yra lyginis vienetų skaičius ir bet koks nulių skaičius. Kitaip tariant, ši mašina apskaičiuoja dvejetainėje skaičių sistemoje įrašyto skaičiaus skaitmenų sumą.

Dabar turėkime fiksuotą abėcėlę A, Ir L- tam tikras žodžių rinkinys, sudarytas iš tam tikros abėcėlės simbolių. Ar visada galima pastatyti automatą tokį, kad rinkinys L ar tai jam buvo atpažįstama kalba? Atsakymas yra ne.

Teorema. Leisti A = {a, b}, L = {a n b n, Kur n eina per visų natūraliųjų skaičių aibę). Krūva L nėra pripažinta kalba.

Įrašas a n, esantis šios teoremos formuluotėje, reiškia, kad raidė A kartojo n kartą.

Teoremos įrodymui naudojamas vienas iš svarbiausių matematinių metodų – prieštaravimu. Taigi tarkime, kad L- pripažinta kalba. Tai reiškia, kad yra automatas, kurį bet koks šios kalbos žodis gali išversti į kokią nors galutinę būseną. Tegul ši mašina turi k teigia. Apsvarstykite žodį a k b k. Tai priklauso kalbai L ir todėl perkelia šį automatą iš pradinės būsenos q 1 į kokią nors galutinę būseną q s. Nuo laiško A kartojama ne mažiau kartų nei automato būsenų skaičius, tokia būsena yra q t , kuris skirtas pirmajam k laiškų paraiškos A bus išlaikytas du kartus (žr ryžių. 3). Pirmą kartą leiskite mašinai pereiti į būseną q t dėl ​​taikymo a u, o kitą kartą po užtepimo jis bus tokios pat būklės a u + v. Apsvarstykite žodį a k + v b k. Aišku, kad taikant šį žodį pradinei būsenai q 1 nustatys tą pačią galutinę būseną q s. Tai reiškia, kad šį žodį atpažįsta ir ši mašina, todėl jis turi priklausyti kalbai L. Bet gausiai L tokio žodžio nėra. Gautas prieštaravimas rodo, kad padaryta prielaida yra neteisinga, t.y. Nėra automato, kuriam šis rinkinys tarnautų kaip atpažįstama kalba.

Ryžiai. 3. Maršrutas ant automato digrafo nuo pradinės būsenos q 1 iki galutinės būsenos q s (valstybei q t raidė A stovi ant arkų u vieną kartą, ant ciklo – dar kartą v kartą)

Kadangi ne kiekvienas žodžių rinkinys sudaro atpažįstamą kalbą, kyla klausimas, kurie rinkiniai tinka šiam tikslui. Matematikai rado patogių būdų apibūdinti atpažįstamas kalbas, ir šie metodai sudarė pagrindą kuriant visas šiuo metu egzistuojančias programavimo kalbas.

Klausimai ir užduotys

1. Kokius du informacijos modelius gali pavaizduoti automatas?

2. Kokią kalbą atpažįsta šis aparatas?

3. Kokia kalba vadinama atpažįstama?

4. Mašinai, pavaizduotai ryžių. 1, nustatykite, kokios būsenos ji bus įvykdžius komandų seką

A) abba; V) babaabaaa;

b) abbabbb; G)* a n b n.

5. Mašinai, pavaizduotai ryžių. 2, padarykite aprašymą lentelės forma.

6. Grafo pavidalu sukonstruokite informacinį mašinos modelį, nurodytą lentelėje. 3.

3 lentelė

7. Kokią kalbą per dviejų simbolių abėcėlę (0, 1) atpažįsta mašina, parodyta ryžių. 4?

Ryžiai. 4

8. Kuri kalba yra virš dviejų simbolių abėcėlės ( a, b) atpažįsta lentelėje nurodyta mašina. 3?

9. Grafo pavidalu nubraižykite informacinį modelį automato, kuris atpažintų kalbą pagal abėcėlę (0, 1), sudarytą iš visų žodžių, turinčių lygiai 5 iš eilės.

10. Nubraižykite grafiką automato, kuris atpažintų kalbą pagal abėcėlę (0, 1), sudarytą iš visų žodžių, turinčių lygiai 5 vienetus, informacinį modelį.

11. Nubraižykite grafiką automato, kuris atpažintų kalbą pagal abėcėlę (0, 1), informacinį modelį, sudarytą iš visų žodžių, prasidedančių vienu (t. y. šis automatas skiria dvejetainėje skaičių sistemoje užrašytus natūraliuosius skaičius nuo savavališkų sekų 0 ir 1 simboliai).

12. Iš toliau išvardytų kalbų L 1 , L 2 , L 3 , L 4 apibrėžta dviejų simbolių abėcėlėje (1; 2), nurodykite, kurios iš jų yra atpažįstamos. Kiekvienai iš atpažintų kalbų sukurkite automatą, kuris ją atpažįsta; kiekvienai iš neatpažįstamų kalbų įrodykite, kad ji neatpažįstama.

A) L 1 susideda iš visų žodžių, kurie reiškia lyginius natūraliuosius skaičius, prasidedančius skaičiumi 1;

b) L 2 susideda iš visų žodžių, kurių vienetų skaičius yra natūralusis skaičius, besibaigiantis skaičiumi 3;

V) L 3 susideda iš visų žodžių, kuriuose dviejų skaičius yra pirminis skaičius;

G) L 4 sudaro visi žodžiai, kurie yra natūralūs skaičiai, dalijami iš 3.

13. Kuo skiriasi „gyvenimas pagal įstatymus“ ir „gyvenimas pagal sąvokas“ informatikos požiūriu?

§ 4. Universalus atlikėjas

Kompiuteriniai žaidimai... Turbūt kiekvienas, bent kartą susidūręs su kompiuteriu, yra matęs, o gal net žaidęs kokį kompiuterinį žaidimą. Ekrane vieni gyvų būtybių ar techninių prietaisų pavidalo objektai paklūsta žaidėjo komandoms, kiti yra valdomi kompiuterio, vykdančio tam tikrą programą. Visi šie objektai yra formalūs vykdytojai, kurių kiekvienas turi savo leistinų veiksmų rinkinį. Tik šie objektai nėra tikri, o imituojami kompiuteriu. Pasirodo, vieno formalaus atlikėjo pagalba mėgdžiojami kiti.

Jei bandysime suformuluoti, ką reiškia, kad vienas atlikėjas yra mėgdžiojamas su kito pagalba, gautume štai ką. Jie sako, kad formalus atlikėjas A imituoja formalų atlikėją IN, Jei

Kiekvienas objektas, su kuriuo atlikėjas atlieka veiksmus IN, vienareikšmiškai atitinka objektą, su kuriuo atlikėjas atlieka veiksmus A(atlikėjo aplinkos imitacija);

Kiekvienas leistinas atlikėjo veiksmas IN leistinas atlikėjo veiksmas vienareikšmiškai derinamas su vienu ar kitu aplinkos objektu A virš atitinkamo jo aplinkos objekto (veiksmų imitacija);

Kiekviena instrukcija surašyta atlikėjui IN o vedimas į tam tikrą rezultatą (t. y. į tam tikrą atlikėjo ir jo paties aplinkos būseną) gali būti paverčiamas leistinų veiksmų imitavimu į nurodymus atlikėjui. A, kurio vykdymas lemia atitinkamą rezultatą atlikėjo aplinkoje A.

Tačiau prielaida, kad atlikėjai A Ir IN skirtinga aplinka, kurioje jie egzistuoja, informacijos požiūriu nėra esminė. Pavyzdžiui, atlikėjas A užsiima skaičiais ir IN konvertuoja grafinius vaizdus. Bet jūs jau žinote, kad iš tikrųjų kiekvienu iš šių atvejų mes kalbame apie tinkamai užkoduotos informacijos transformavimą. Be to, galima daryti prielaidą, kad naudojamas tas pats dvejetainis kodas. Šia prasme galime laikyti, kad atlikėjo aplinka yra tiesiog ta pati – informacija pateikiama koduoto pranešimo forma.

Vienas iš svarbiausių teorinės informatikos klausimų: ar yra toks formalus atlikėjas, su kuriuo būtų galima mėgdžioti bet kurį formalų atlikėją? Natūralu vadinti tokį atlikėją Universalus. Nesunku suprasti, kad universalus vykdytojas neegzistuoja kaip fizinis įrenginys – juk informacija gali būti užkoduota savavališkai ilguose pranešimuose, o bet kokia fizinė terpė yra baigtinė. Jei kalbėsime apie universalų atlikėją kaip apie idealų objektą, tada paaiškėja, kad atsakymas į užduotą klausimą yra teigiamas. Ir jį beveik vienu metu ir nepriklausomai gavo du iškilūs mokslininkai – A. Turingas (1936 m.) ir E. Postas (1937 m.). Jų pasiūlyti atlikėjai skyrėsi vienas nuo kito, tačiau paaiškėjo, kad jie gali mėgdžioti vienas kitą, o svarbiausia – mėgdžioti bet kurį formalų atlikėją apskritai.

Universalus atlikėjas paprastai vadinamas mašina. Taip pat įprasta mašinas pavadinti jų išradėjų vardais. Taigi A. Turingo išrastas universalus vykdytojas vadinamas Tiuringo mašina; E. Posto aprašytas atlikėjas – Posto mašina. Vėliau pasirodė kiti universalūs atlikėjai, pavyzdžiui, „Minsky“ mašina.

Taigi, galime manyti, kad turime tam tikra abėcėle parašytą pranešimą ir jį reikia paversti kitu pranešimu. Žinoma, parašyti nurodymus oficialiam vykdytojui apdoroti konkrečią pranešimų porą nėra sudėtingas dalykas. Bet jūs jau žinote, kad tikrasis susidomėjimas yra instrukcijomis (t. y. algoritmais), kurios leidžia išspręsti visą panašių problemų klasę - vadinamąją „algoritmo masės savybę“. Pavyzdžiui, ši užduotis: bet kurio pranešimo dešinėje pridėkite kitą iš anksto nustatytą simbolį. Jei, tarkime, identiškų simbolių seka veikia kaip natūralaus skaičiaus kodas – sekoje esančių simbolių skaičius yra užkoduojamas natūralusis skaičius – tai iš tikrųjų kalbame apie skaičiaus padidinimo 1 algoritmo sukūrimą.

Natūralu manyti, kad pranešimas įrašytas į juostelę. Be to, patogu įsivaizduoti, kad ši juosta yra padalinta į lygias ląsteles ir kiekvienoje langelyje yra tiksliai vienas pranešimo simbolis. Kadangi žinutės gali būti tiek ilgos, kiek norima, sutiksime, kad sklaidos kanalas būtų begalinis. Tušti langeliai bus laikomi užpildyti „tarpo“ simboliu. Taigi paskelbėme, kad bet kurioje abėcėlėje, kurią naudosime įrašydami pranešimus į šią juostą, turi būti tarpas. Sutikime jį paskirti A 0 . Likę abėcėlės simboliai, naudojami žinutėms įrašyti į juostelę, bus pažymėti A 1 , A 2 , ..., A n. Pavyzdžiui, jei mums reikia užrašyti dviejų skaičių sumos apskaičiavimo užduotį, abėcėlę galima paimti taip: A 0 ; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; ,; +; =. Tam tikros duomenų poros (t. y. dviejų skaičių) įrašas juostoje gali atrodyti, pavyzdžiui, taip, kaip parodyta ryžių. 5.

Ryžiai. 5

Mes, žinoma, nerašysime simbolio ant juostos tuščiose ląstelėse A 0, tai reiškia, kad jis yra. Be to, sutinkame, kad pirmasis pranešimo simbolis, išskyrus tarpą, visada rodomas tame pačiame langelyje – įjungta ryžių. 4 jis pažymėtas Ї. Šią ląstelę vadinsime pradine.

Į juostą įrašytą žinutę apdoroja koks nors įrenginys, o rezultatas įrašomas atgal į juostą. Kadangi atlikėjas yra formalus, jis nesigilina į pranešimo prasmę, o pagal jam parengtas instrukcijas vienus simbolius pakeičia kitais. Mums neįdomu, kaip fiziškai atliekamas toks pakeitimas, todėl galime įsivaizduoti, kad juosta juda kažkoks automatas, kuris nuskaito simbolį iš juostos langelio, apdoroja gautą informaciją, atspausdina langelyje kitą simbolį. (jei nurodyta instrukcijose) ir pereina į gretimą langelį – į dešinę arba į kairę.

Jūs jau žinote, kad kiekvienas automatas apibūdinamas būsenų rinkiniu. Nurodyto skaitymo-spausdinimo mašinos būsenas įprasta žymėti raidėmis q 0 , q 1 , q 2 , ..., q m. Kartu sutinkame, kad mašiną įjungus, t.y. darbo pradžioje jis visada yra tos pačios būsenos, kurią pažymėsime q 0 ir yra priešais pradinį langelį.

Taigi Tiuringo mašina formaliai apibūdinama dviejų abėcėlių rinkiniu: A = {A 1 , A 2 , ..., A) Ir K = {q 0 , q 1 , q 2 , ..., q m). Abėcėlė A paskambino išorės ir skirtas įrašyti pradinius pranešimus, abėcėlę K paskambino vidinis ir aprašo skaitytuvo-spausdinimo įrenginio būsenų rinkinį. Mes pavaizduosime Tiuringo mašiną, kaip parodyta ryžių. 6.

Ryžiai. 6

Įjungta ryžių. 6 paveiksle parodytas Tiuringo mašinos veikimo momentas, kai skaitymo-spausdinimo įrenginys apžiūri trečią langelį nuo pradinės (šiuo metu joje buvo simbolis a s 3) ir yra būsenoje q k.

Taigi, leistini Tiuringo mašinos veiksmai yra šie:

Į juostos skyrių įrašykite bet kokį išorinės abėcėlės simbolį (prieš tai buvęs simbolis perrašomas);

Pereiti į kitą skyrių;

Pakeiskite būseną į vieną iš tų, kurias nurodo vidinis abėcėlės simbolis;

Sustabdyti darbą (sustoti).

Žinoma, šiame sąraše kiekviena eilutė nurodo ne vieną veiksmą, o to paties tipo veiksmų grupę - veiksmų „parašyti išorinės abėcėlės simbolį“ yra tiek, kiek yra šių simbolių, galite pereiti prie gretimų. skyrių į dešinę arba į kairę, yra tiek veiksmų, skirtų būsenai pakeisti, kiek ir šių būsenų (t. y. kiek vidinės abėcėlės simbolių).

Dabar turime pasakyti, kaip rašomos komandos nurodytiems veiksmams atlikti. Kiekvienoje mašinos komandoje yra daugiausia vienas veiksmas iš kiekvienos veiksmų grupės ir jos forma

Realios komandos atrodo taip:

a i q j - rašykite į stebimą skyrių a i , pereikite į dešinę (į kitą skyrių) ir įveskite būseną q j ;

a i q j - rašykite į stebimą skyrių a i , pereikite į kairę ir eikite į būseną q j ;

ir S q j - rašykite į stebimą skyrių ai, sustokite ir eikite į būseną q j.

Veiksmams atlikti Tiuringo mašina turi operacinį-loginį vienetą. Šis blokas turi du įėjimus: per vieną iš jų gaunama informacija apie tai, kuris simbolis yra stebimoje ląstelėje, per kitą - informacija apie tai, kokioje būsenoje yra mašina konkrečiame savo darbo etape. Ši informacija vienareikšmiškai nustato, kurią komandą mašina turi vykdyti. Kadangi komandoje gali būti nurodymas atlikti tris veiksmus – įrašyti simbolį į juostelę, perjungti ir pakeisti būseną – operatyvinis-loginis blokas turi tris išėjimus: rašyti simbolį. A, kompensuoti M ir valstybės pasikeitimas K(cm. ryžių. 7).

Ryžiai. 7. Operatyvinis-loginis Tiuringo mašinos blokas

Kadangi šis blokas turi tik du įėjimus, jo atsaką į jiems pateikiamus simbolius galima patogiai pavaizduoti stačiakampės lentelės pavidalu, kurioje eilutės ir stulpeliai atitinkamai pažymėti išorinės ir vidinės abėcėlės simboliais (žr. 4 lentelę). . Komandos rašomos lentelės langeliuose. Jei automobilis yra priešais aikštę, kurioje sakoma a i, o jos būsena yra q j, tada įvykdoma simboliu pažymėtos linijos sankirtos komanda ai, o stulpelis pažymėtas simboliu q j.

4 lentelė

Ši lentelė vadinama funkcinė diagramaši mašina; ji atlieka Turingo mašinos instrukcijos (programos) vaidmenį. Visų pirma iš jo aišku, kokia yra išorinė ir vidinė mašinos abėcėlė.

Tegul, pavyzdžiui, į juostą įrašoma tam tikro skaičiaus to paties simbolio „*“ seka. Tada lentelėje pateikta funkcinė diagrama. 5 priverčia Tiuringo mašiną padidinti žvaigždžių skaičių šioje sekoje vienu.

5 lentelė

Neįmanoma įrodyti, kad Tiuringo mašina yra universalus vykdytojas. Kaip, pavyzdžiui, fizikoje neįmanoma įrodyti energijos tvermės dėsnio. Tačiau algoritmų kūrimo praktika rodo, kad bet kokią problemą, kurią žmogus gali išspręsti šiandien, galima užprogramuoti Tiuringo mašinoje. Šis eksperimentinis faktas, vadinamas Tiuringo teze, formuluojamas taip: problemai yra algoritmas, kaip ją išspręsti tada ir tik tada, kai yra tinkama Tiuringo mašina, su kuria galima išspręsti šią problemą.

Klausimai ir užduotys

1. Kuris formalus atlikėjas vadinamas universaliu?

2. Kas yra Tiuringo mašina?

3. Kuo viena Tiuringo mašina skiriasi nuo kitos?

4. Kas vadinama Tiuringo mašinos funkcine diagrama?

5. Ar tiesa, kad Tiuringo mašina su jai parašyta funkcine schema yra baigtinių būsenų mašina?

6. Brėžinių sekos pavidalu nubrėžkite, kaip keičiasi informacija juostoje veikiant Tiuringo mašinai, aprašyta lentelėje esančia funkcine schema. 5.

7. Vadovaudamiesi lentelėje aprašyta funkcine schema. 5, Tiuringo mašina nurodytai žvaigždučių sekai priskiria dar vieną žvaigždutę kairėje. Nubraižykite funkcinę schemą, pagal kurią žvaigždutė bus priskirta nurodytos sekos dešinėje.

8. Tiuringo mašinos veikimas aprašytas tokia funkcine schema:

Nustatykite, koks pranešimas bus juostoje, kai įrenginys baigs veikti, ir nurodykite, prieš kurią langelį tuo momentu bus jo rašymo blokas.

Ryžiai. 8

Ryžiai. 9

9. Tiuringo mašinos juostoje yra eilutė, susidedanti iš kelių iš eilės einančių „*“ simbolių, po kurių seka keli „#“ simboliai, o eilutės pabaigoje yra simbolis „e“ (vienas iš galimų tokios eilutės variantų yra parodyta ryžių. 5).

Ryžiai. 10

Kiekvienai iš toliau pateiktų funkcinių diagramų nustatykite, kokiai problemai ji skirta išspręsti. (Patarimas: norėdami gauti įtikinamą atsakymą, pritaikykite funkcinę diagramą skirtingoms informacijos sklaidos kanalo užpildymo išorinės abėcėlės simbolių sekomis parinktims.)

10. Tegul išorinę abėcėlę sudaro simbolis „ a 0 ”ir skaičiai 0, 1, 2, ..., 9. Juostoje įrašomas natūralusis skaičius. Išraskite Tiuringo mašiną ir sudarykite jos funkcinę schemą, pagal kurią šis skaičius bus padidintas 1.

11. Tegul išorinę abėcėlę sudaro simbolis „ a 0 ”ir skaičiai 0, 1, 2, ..., 9. Juostoje užrašomas natūralusis skaičius. Nubraižykite Tiuringo mašinos funkcinę schemą, kuri įrašys šio skaičiaus skaitmenų sumą į juostą. Atsakymas turi būti parašytas pirminio skaičiaus dešinėje, atskirtas nuo jo tarpu.

Ryžiai. 11

P.S. Jaustis kaip Tiuringo mašina naudinga, bet varginanti. Rekomenduojame 8 ir 9 užduotis atlikti rankiniu būdu. Kalbant apie 10 ir 11 užduotis, rankinis jūsų sudarytų funkcinių diagramų testavimas gali būti neveiksmingas. Šiuo atžvilgiu siūlome panaudoti kompiuterinį R. Zartdinovo sukurtos Tiuringo mašinos įgyvendinimą. Ją galima gauti laikraščio „Informatika“ svetainėje ( inf.1september.ru). Štai kaip, pavyzdžiui, šioje mašinoje atrodo funkcinė schema iš 8 užduoties c) - skirtumai yra tokie, kad vietoj S raidės yra kelio ženklas, o vietoj simbolio „ a 0“ rašoma „_“ (tačiau įvesdami komandą į lentelės langelį turite spausti „tarpo“, o ne „_“ klavišą). Programoje pateikiama išsami pagalba, kaip su ja dirbti. Šios programos sąsaja yra labai paprasta. Be to, šio Tiuringo mašinos įgyvendinimo aprašymą galite rasti laikraštyje „Informatika“ Nr. 8, 2006. Ten taip pat rasite dar kelių Tiuringo mašinos programavimo problemų analizę; tik reikia nepamiršti, kad jie naudoja kiek kitokią (o tai visiškai neprincipą) komandų sistemą.

* Prisiminkite, kad grafikas yra taškų, vadinamų, rinkinys viršūnės, ir kai kurias viršūnes jungiančios linijos. Jei viršūnes jungiančiose linijose nurodoma kryptis, vadinasi grafikas orientuotas(sutrumpintai dvikalbis), o eilutės vadinamos jo lankai. Įprastame grafike, t.y. neorientuotos, vadinamos viršūnes jungiančios linijos šonkauliai. Grafikai bus plačiau aptariami 4 paskaitoje.

Yra dviejų tipų atlikėjai: formalus ir neformalus.

Formalus atlikėjas visada tą pačią komandą atlieka vienodai.

Neformalus vykdytojas komandą gali vykdyti įvairiais būdais.

Pavyzdžiui, pakartotinai klausantis disko su mėgstama melodija, galite būti tikri, kad grotuvas (oficialus atlikėjas) ją atkuria taip pat. Tačiau vargu ar kuris nors iš dainininkų (neformalių atlikėjų) sugebės kelis kartus lygiai taip pat atlikti dainą iš savo repertuaro.

Paprastai žmogus veikia kaip neformalus atlikėjas.

Formalūs atlikėjai daugiausia yra techniniai įrenginiai.

Neformalaus atlikėjo vaidmenį atliekantis žmogus pats atsako už savo veiksmus.

Už formalaus vykdytojo veiksmus atsako jį valdantis objektas.

Leiskite mums išsamiau apsvarstyti oficialių atlikėjų rinkinį. Formalių vykdytojų yra be galo įvairių, tačiau kiekvienam iš jų galima nurodyti sprendžiamų užduočių spektrą, aplinką, komandų sistemą, gedimų sistemą ir darbo režimus.

1. Spręstinų užduočių spektras. Kiekvienas vykdytojas yra sukurtas tam, kad išspręstų tam tikrą problemų klasę.
2. Menininko aplinka. Teritorija, aplinka, sąlygos, kuriose atlikėjas veikia, dažniausiai vadinamos duoto atlikėjo aplinka.
3. Vykdytojo komandų sistema. Nurodymas atlikti atskirą užbaigtą atlikėjo veiksmą vadinamas komanda. Visų komandų, kurias gali vykdyti koks nors vykdytojas, rinkinys sudaro SKI – vykdytojų komandų sistemą.
4. Atlikėjo gedimų sistema. „Aš nesuprantu“ atsisakymas įvyksta, kai atlikėjui duodama komanda, kuri nėra jo SKI dalis. Atsisakymas „Aš negaliu“ įvyksta, kai SCI komandos negali įvykdyti konkrečiomis aplinkos sąlygomis.
5. Atlikėjo darbo režimai. Daugumai atlikėjų yra numatyti tiesioginio ir programos valdymo režimai. Pirmuoju atveju atlikėjas laukia komandų iš žmogaus ir iš karto įvykdo kiekvieną gautą komandą. Antruoju atveju atlikėjui pirmiausia suteikiama visa komandų seka (programa), o vėliau visas šias komandas jis vykdo automatiškai. Nemažai atlikėjų dirba tik vienu iš įvardintų režimų.

Algoritmo kūrimas - daug darbo reikalaujantis darbas, reikalaujantis iš žmogaus gilių žinių ir daug laiko. Sprendžiant problemą naudojant paruoštą algoritmą, atlikėjas turi tik griežtai laikytis pateiktų nurodymų. Atlikėjas nesigilina į to, ką daro, prasmę ir nemotyvuoja, kodėl elgiasi taip, o ne kitaip – ​​elgiasi formaliai. Su tuo susijusi galimybė automatizuoti žmogaus veiklą:

• problemos sprendimo procesas pateikiamas kaip paprastų operacijų seka;
• sukuriamas aparatas (automatas), galintis atlikti šias operacijas algoritme nurodyta seka;
• žmogus išlaisvinamas nuo įprastos veiklos, algoritmo vykdymas pavedamas automatiniam įrenginiui.

Panagrinėkime informacijos proceso valdymo procesą, kai tekstas pasirenkamas kaip valdomas objektas. Kitaip tariant, panagrinėkime informacijos procesą, susijusį su teksto redagavimu (būsenos keitimu).
Pirmiausia, norint transformuoti tekstą, turi būti kažkas ar kažkas, kas atlieka šias transformacijas. Kitaip tariant, tai būtina vykdytojas šios transformacijos.
Antra, teksto konvertavimo procesas turi būti išskaidytas į atskiras operacijas, kurios turi būti parašytos kaip atskiros komandos atlikėjui. Kiekvienas atlikėjas turi tam tikrą rinkinį , komandų sistema , kurį jis gali įvykdyti. Teksto redagavimo procese galimos įvairios operacijos: jo fragmentų trynimas, kopijavimas, perkėlimas ar pakeitimas. Teksto rengyklė turi sugebėti atlikti šias operacijas.
Trečias, turi būti nustatyta pradinė objekto būsena,šiuo atveju tekstas ir jo reikalaujama galutinė būsena(transformacijos tikslas).
Sakysime, kad vadinamas informacinis procesas, turintis visas aukščiau išvardytas savybes algoritmas . Vykdytojas gali vykdyti algoritmą, jei algoritmo komandos yra įtrauktos į vykdytojo komandų sistemą.
Pavyzdžiui: vartotojas turi redaguoti tekstą taip:

1. Pasirinkite simbolius nuo 1 iki 15.

2. Iškirpkite šį fragmentą ir įdėkite jį į buferį.

3. Perkelkite žymeklį į vietą po 7-ojo simbolio.

4. Įterpkite iškirptą teksto fragmentą.

Vartotojas gali atlikti šį algoritmą formaliai. Vartotojas, vykdydamas algoritmą kompiuteryje, spaus klaviatūros klavišus, o dirbdamas su grafine sąsaja pele aktyvuos tam tikrus mygtukus, meniu elementus ir pan. Tiesą sakant, vartotojas duos komandas Windows&Office programinės įrangos aplinkos objektams atlikėjai algoritmas.

Algoritminio programavimo kalbos. Informacijos proceso atvaizdavimas algoritmo forma leidžia jį priskirti automatinisįvairių techninių įrenginių vykdymas, tarp kurių kompiuteris užima ypatingą vietą. Šiuo atveju jie sako, kad kompiuteris vykdo programą (komandų seką), kuri įgyvendina algoritmą tam tikra programavimo kalba.

14 Pagrindinės algoritmizacijos sąvokos: formalūs ir neformalūs algoritmų vykdytojai.

Vykdytojas- tai objektas (žmogus, gyvūnas, techninis įrenginys), galintis vykdyti tam tikrą komandų rinkinį.
Komandos, kurias gali vykdyti tam tikra atlikėjo forma vykdytojo komandų sistema(SLIDŽIŲ).

Atlikėjų klasė neįprastai įvairi. Visų pirma, išskiriami du atlikėjų tipai: formalus Ir neformalus. Formalus atlikėjas visada tą pačią komandą atlieka vienodai. Neformalus vykdytojas komandą gali vykdyti įvairiais būdais.

Pavyzdžiui, pakartotinai klausantis disko su mėgstamomis melodijomis, galite būti tikri, kad grotuvas (oficialus atlikėjas) jas atkuria taip pat. Tačiau vargu ar kuris nors iš dainininkų (neformalių atlikėjų) sugebės kelis kartus lygiai taip pat atlikti dainą iš savo repertuaro.

Paprastai žmogus veikia kaip neformalus atlikėjas. Formalūs atlikėjai daugiausia yra techniniai įrenginiai. Neformalaus atlikėjo vaidmenį atliekantis žmogus pats atsako už savo veiksmus. Už formalaus vykdytojo veiksmus atsako jį valdantis objektas.

Kontrolė– tai kryptingo vienų objektų įtakos kitiems procesas.

Atlikėjai yra valdymo objektai. Galite juos valdyti sukūrę jiems algoritmą.

Algoritmas- tai tikslus veiksmų sekos, skirtos konkrečiam atlikėjui, skirtos užduočiai išspręsti, aprašymas.

Algoritmai gali būti parašyti kaip lentelė, sunumeruotas sąrašas natūralia kalba arba pavaizduoti naudojant struktūrinę schemą. Programa yra algoritmas, parašytas pagal kompiuterio atlikėjui suprantamos kalbos taisykles.

15 Algoritminių projektų: linijinis, išsišakojęs, kilpos

Algoritmų atsiradimas siejamas su matematikos ištakomis. Daugiau nei prieš 1000 metų (825 m.) Khorezmo miesto mokslininkas Abdullah (arba Abu Jafaras) Muhammad bin Musa al-Khorezmi sukūrė matematikos knygą, kurioje aprašė būdus, kaip atlikti aritmetines operacijas su daugiaženkliais skaičiais. . Pats žodis algoritmas atsirado Europoje po to, kai šio matematiko knyga buvo išversta į lotynų kalbą.

Algoritmas– veiksmų sekos (plano), kurios griežtas vykdymas lemia užduoties sprendimą baigtiniu žingsnių skaičiumi, aprašymas.

Su šia sąvoka nuolat susiduri įvairiose žmogaus veiklos srityse (kulinarinės knygos, įvairių prietaisų naudojimo instrukcijos, matematinių uždavinių sprendimo taisyklės...). Įprastus veiksmus dažniausiai atliekame negalvodami, mechaniškai. Pavyzdžiui, jūs gerai žinote, kaip atidaryti duris raktu. Tačiau norėdami to išmokyti vaiką, turėsite aiškiai paaiškinti pačius šiuos veiksmus ir jų atlikimo tvarką: 1. Iš kišenės ištraukite raktą. 2. Įkiškite raktą į rakto skylutę. 3. Du kartus pasukite raktelį prieš laikrodžio rodyklę. 4. Išimkite raktą.

Jei atidžiai apsižvalgysite, rasite daugybę algoritmų, kuriuos nuolat vykdome. Algoritmų pasaulis yra labai įvairus. Nepaisant to, galima nustatyti bendrąsias bet kurio algoritmo savybes.

Algoritmų savybės: 1. Diskretiškumas (algoritmą turi sudaryti konkretūs veiksmai, atliekami tam tikra tvarka); 2. Determinizmas (bet koks veiksmas kiekvienu atveju turi būti griežtai ir nedviprasmiškai apibrėžtas); 3. Baigtumas (kiekvienas veiksmas ir visas algoritmas turi būti užbaigti); 4. Masyvumas (tas pats algoritmas gali būti naudojamas su skirtingais šaltinio duomenimis); 5. Efektyvumas (nėra klaidų, algoritmas turi duoti teisingą rezultatą visoms galiojančioms įvesties reikšmėms).

Algoritmų tipai: 1. Linijinis algoritmas (veiksmų, kurie atliekami vieną kartą tam tikra tvarka, aprašymas); 2. Ciklinis algoritmas (veiksmų, kurie turi būti kartojami tam tikrą skaičių kartų arba kol bus atlikta užduotis, aprašymas); 3. Šakojimo algoritmas (algoritmas, kuriame, priklausomai nuo sąlygos, atliekama arba viena, arba kita veiksmų seka) 4. Pagalbinis algoritmas (algoritmas, kurį galima naudoti kituose algoritmuose nurodant tik jo pavadinimą).

Norint vizualiai pavaizduoti algoritmą, jis plačiai naudojamas grafinė forma – blokinė schema, kurį sudaro standartiniai grafiniai objektai.

Standartinio grafinio objekto tipas	Tikslas
	Algoritmo pradžia
	Algoritmo pabaiga
	Atliktas veiksmas įrašomas stačiakampio viduje
	Veiksmų atlikimo sąlyga įrašyta deimanto viduje
	Įvesties išvesties

Algoritmo kūrimo etapai: 1. Algoritmas turi būti pateiktas jį kuriančiam asmeniui suprantama forma. 2. Algoritmas turi būti pateiktas suprantama forma objektui (taip pat ir asmeniui), kuris atliks algoritme aprašytus veiksmus.

Objektas, kuris vykdys algoritmą, paprastai vadinamas vykdytoju.

Vykdytojas- objektas, kuris vykdo algoritmą.

Idealūs atlikėjai yra mašinos, robotai, kompiuteriai...

Vykdytojas gali vykdyti tik ribotą skaičių komandų. Todėl algoritmas yra sukurtas ir detalizuotas taip, kad jame būtų tik tos komandos ir struktūros, kurias atlikėjas gali vykdyti.

Atlikėjas, kaip ir bet kuris objektas, yra tam tikroje aplinkoje ir gali atlikti tik joje leidžiamus veiksmus. Jei vykdytojas algoritme susiduria su nežinoma komanda, algoritmo vykdymas sustos.

Kompiuteris yra automatinis algoritmų vykdytojas.

Algoritmas, parašytas kompiuterio skaitoma programavimo kalba, vadinamas programa.

Programavimas – tai kompiuterio programos rašymo procesas. Pirmiesiems kompiuteriams programos buvo parašytos elementariųjų operacijų sekos forma. Tai buvo labai daug darbo reikalaujantis ir neefektyvus darbas. Todėl vėliau buvo sukurtos specialios programavimo kalbos. Šiuo metu yra daug dirbtinių kalbų programoms rašyti. Tačiau niekada nebuvo įmanoma sukurti idealios kalbos, kuri tiktų visiems.