Algoritms un tā īpašības.

Algoritms- skaidrs un precīzs norādījums izpildītājam izpildīt pēdējo komandu secību, kas ved no sākotnējiem datiem līdz vēlamajam rezultātam.

Algoritma izpildītājs- tas ir objekts vai subjekts, kura vadīšanai ir paredzēts algoritms.

Izpildītāja komandu sistēma (SCS) ir viss komandu kopums, ko izpildītājs var izpildīt.

Algoritma īpašības: saprotamība, precizitāte, galīgums.

Skaidrība: algoritms sastāv tikai no komandām, kas iekļautas izpildītāja SKI.

Precizitāte: Katra vadības algoritma komanda nosaka izpildītāja nepārprotamo darbību.

Nobeigums (vai veiktspēja): algoritma izpildei jānoved pie rezultāta ierobežotā soļu skaitā.

Izpildītāja vide: vide, kurā izpildītājs darbojas.

Uz dažiem vienmēr attiecas noteikta izpildītāja darbību secība avota dati. Piemēram, lai pagatavotu ēdienu pēc kulinārijas receptes, nepieciešami atbilstoši produkti (dati). Matemātiskas problēmas risināšanai (kvadrātvienādojuma atrisināšanai) nepieciešami sākotnējie skaitliskie dati (vienādojuma koeficienti).

Pilna datu kopa: nepieciešams un pietiekams datu kopums, lai atrisinātu uzdevumu (iegūtu vēlamo rezultātu).

Algoritmu rakstīšanas metodes.

Visizplatītākās metodes ir: grafisks, verbāls un formā datorprogrammas.

Grafiskā metode ietver noteiktu grafisko simbolu - bloku izmantošanu.

Bloku kolekcija veido t.s algoritma blokshēma.

Verbāls ieraksts algoritmi ir vērsti galvenokārt uz cilvēka izpildītāju un ļauj veikt dažādu instrukciju ierakstīšanu, taču ierakstam jābūt diezgan precīzam.

Rakstot algoritmus formā programmas datori izmanto programmēšanas valodas - instrukciju kodēšanas sistēmas un to lietošanas noteikumus. Algoritmu rakstīšanai programmu formā ir raksturīga augsta formalizācijas pakāpe.

Algoritmi darbam ar daudzumiem. Algoritmiskās pamatstruktūras.

Daudzums ir viens informācijas objekts, kam ir nosaukums, vērtība un veids.

Algoritmu izpildītājs darbam ar daudzumiem var būt cilvēks vai īpaša tehniska ierīce, piemēram, dators. Tādam izpildītājam jābūt atmiņa daudzumu uzglabāšanai.

Daudzumi var būt nemainīgi vai mainīgi.

Konstanta vērtība (konstante) nemaina savu vērtību algoritma izpildes laikā. Konstanti var apzīmēt ar tās vērtību (skaitļi 10, 3.5) vai ar simbolisku nosaukumu (skaitlis ).

Mainīga vērtība var mainīt vērtību algoritma izpildes laikā. Mainīgais vienmēr tiek apzīmēts ar simbolisku nosaukumu (X, A, R5 utt.).

Daudzuma veids definē vērtību kopu, ko vērtība var veikt, un darbību kopu, ko var veikt ar šo vērtību. Lielumu pamatveidi: vesels skaitlis, reāls, simboliskais, loģiskais.

Izteiksme- ieraksts, kas nosaka darbību secību ar daudzumiem. Izteiksmē var būt konstantes, mainīgie, darbības zīmes un funkcijas. Piemērs:

A + B; 2*X-Y; K + L — grēks(X)

Piešķiršanas komanda ir izpildītāja komanda, kuras rezultātā mainīgais saņem jaunu vērtību. Komandas formāts:

mainīgā nosaukums>:=izteiksme>

Piešķiršanas komanda tiek izpildīta šādā secībā: vispirms tiek aprēķināta, pēc tam iegūtā vērtība tiek piešķirta mainīgajam.

Piemērs. Lai mainīgajam A ir vērtība 6. Kādu vērtību mainīgais A saņems pēc komandas izpildes: A:= 2 * A - 1?
Risinājums. Aprēķinot izteiksmi 2*A - 1 ar A=6, tiks iegūts skaitlis 11. Tas nozīmē, ka mainīgā A jaunā vērtība būs vienāda ar 11.

Turpmāk tiks pieņemts, ka algoritmu izpildītājs darbam ar daudzumiem ir dators. Jebkuru algoritmu var izveidot no komandām uzdevumiem, ievade, izvade, zarošanās Un cikls.

Ievadiet komandu- komanda, ar kuru mainīgās vērtības tiek iestatītas, izmantojot ievades ierīces (piemēram, tastatūru).

Piemērs: ievade A - mainīgā A vērtības ievadīšana no datora tastatūras.

Izvades komanda: komanda, kas parāda daudzuma vērtību datora izvades ierīcē (piemēram, monitorā).

Piemērs: secinājums X - ekrānā tiek parādīta X mainīgā vērtība.

Filiāles komanda- sadala algoritmu divos ceļos atkarībā no kāda nosacījuma; tad algoritma izpilde iet uz vispārīgu turpinājumu. Sazarošanās var būt pilnīga vai nepilnīga. Sazarojumu apraksts blokshēmās un algoritmiskajā valodā:

Šeit sērija nozīmē vienu vai vairākas secīgas komandas; kv - atzarojuma beigas.

Cilpas komanda nodrošina atkārtotu komandu secības izpildi (cilpas pamatteksts), pamatojoties uz kādu nosacījumu.

Cilpa ar priekšnosacījumu- cilpa, kuras izpilde tiek atkārtota, līdz cilpas nosacījums ir patiess:

Cilpa ar parametru- atkārtota cilpas korpusa izpilde, kamēr veselais skaitļa parametrs iet cauri visu vērtību kopai no sākotnējās (In) līdz galīgajai (Ik):

Piemērs. Ir dotas divas vienkāršās daļas. Izveidojiet algoritmu, lai iegūtu daļu, kas ir to dalīšanas rezultāts.
Risinājums. Algebriskā formā problēmas risinājums izskatās šādi:
a/b: c/d = a*d/b*c = m/n
Sākotnējie dati ir četri veseli skaitļi: a, b, c, d. Rezultāts ir divi veseli skaitļi m un n.

alg dalīšanas daļas
neskarts a, b, c, d, m, n
sākuma ievade a, b, c, d
m:=a*d
n:=b*c
izeja "Numerators=", m
izvade "Saucējs=", n
koi

Lūdzu, ņemiet vērā, ka, lai izvadītu tekstu (jebkuru rakstzīmju secību), tas komandā jāraksta pēdiņās secinājums.

1. Efimova O., Morozovs V., Ugrinovich N. Datortehnoloģijas kurss ar datorzinātņu pamatiem. Mācību grāmata vidusskolai. - M.: SIA "Izdevniecība AST"; ABF, 2000. gads
2. Problēmgrāmata-darbnīca datorzinātnēs. 2 sējumos/Red. I. Semakina, E. Hennere. - M.: Pamatzināšanu laboratorija, 2001.g.
3. Ugrinovičs N. Datorzinātne un informācijas tehnoloģijas. 10-11 klase - M.: Pamatzināšanu laboratorija, AS "Maskavas mācību grāmatas", 2001.g.

Uzdevumi un testi par tēmu "Algoritmi un izpildītāji"

• Mākslinieku menedžmenta sagatavotājs - Algoritmi 6. klase

  Nodarbības: 4 Uzdevumi: 9 Pārbaudījumi: 1

• 2 Uzdevumi: 9 Pārbaudījumi: 1

Cienījamais student!

Zināšanas par tēmu "Algoritmi un izpildītāji" ir nepieciešamas galvenokārt turpmākai programmēšanas apguvei. Par pamatu programmēšanas apguvei tika izvēlēta QBasic programmēšanas valoda. Mēs atteicāmies no idejas iekļaut savā kursā Visual Basic vai jebkuru citu objektorientētu programmēšanas valodu, jo šī pieeja vēl nav plaši izmantota lielākajā daļā Krievijas Federācijas vidusskolu. Turklāt objektorientētā programmēšana balstās uz klasiskās Dos programmēšanas principiem.

Mūsu kurss ir paredzēts vispārējās izglītības programmai. Gatavojoties iestājeksāmeniem informācijas tehnoloģijās augstskolās, jāiepazīstas ar programmēšanas studiju specifiku attiecīgajā augstskolā. Dažos gadījumos ir nepieciešama vairāku tēmu padziļināta izpēte, piemēram, "Masīvi". Tam vajadzētu pievērst uzmanību, studējot programmēšanas literatūru, iespējams, vajadzētu izmantot metodiskos ieteikumus, gatavojoties eksāmeniem, kas šobrīd publicēti lielākajā daļā augstskolu.

Noslēgumā mēs atzīmējam, ka “aerobātikas” sasniegšana programmēšanā ir iespējama tikai ar pastāvīgu praksi un risinot konkrētas lietišķas problēmas.

7.1. Kas ir algoritms?

Nosaukums "algoritms" cēlies no Vidusāzijas matemātiķa al-Khwarizmi vārda latīņu formas - Algorithmi. Algoritms ir viens no datorzinātņu un matemātikas pamatjēdzieniem.

7.2. Kas ir "algoritma izpildītājs"?

Izpildītāju raksturo:

• • trešdiena;
  • elementāras darbības;
  • komandu sistēma;
  • atteikumiem.

trešdiena(vai iestatījums) ir izpildītāja “dzīvesvieta”. Piemēram, izpildītājam Robotam no skolas mācību grāmatas vide ir bezgalīgs šūnu lauks. Sienas un krāsotas šūnas arī ir daļa no vides. Un to atrašanās vieta un paša Robota novietojums nosaka konkrētu vides stāvokli.

Komandu sistēma. Katrs izpildītājs var izpildīt komandas tikai no noteikta stingri noteikta saraksta - izpildītāju komandu sistēmas. Katrai komandai ir jānorāda piemērojamības nosacījumi(kādos vides stāvokļos komandu var izpildīt) un aprakstīts komandas izpildes rezultāti. Piemēram, darba komandu “uz augšu” var izpildīt, ja virs Darba nav sienas. Tā rezultāts ir robota pārvietošanās vienu šūnu uz augšu.

Pēc komandas izsaukšanas izpildītājs veic atbilstošo elementāra darbība .

Neveiksmes izpildītāja kļūdas rodas, ja komanda tiek izsaukta vides stāvoklī, kas tai ir nepieņemama.

Datorzinātnē universālais algoritmu izpildītājs ir dators.

7.3. Kādas īpašības piemīt algoritmiem?
Algoritmu galvenās īpašības ir šādas:

Saprotamība izpildītājam - t.i. Algoritma izpildītājam ir jāzina, kā to izpildīt.

Diskrētība(pārtraukums, nošķirtība) - t.i. Algoritmam ir jāattēlo problēmas risināšanas process kā vienkāršu (vai iepriekš definētu) soļu (posmu) secīga izpilde.

Noteiktība- t.i. Katram algoritma noteikumam jābūt skaidram, nepārprotamam un nedrīkst atstāt vietu patvaļai. Pateicoties šai īpašībai, algoritma izpildei ir mehānisks raksturs un nav nepieciešami nekādi papildu norādījumi vai informācija par risināmo problēmu.

Efektivitāte (vai ekstremitāte). Šī īpašība ir tāda, ka algoritmam ir jānoved pie problēmas risināšanas ierobežotā soļu skaitā.

Masu raksturs. Tas nozīmē, ka problēmas risināšanas algoritms tiek izstrādāts vispārīgā formā, t.i. tai vajadzētu būt piemērojamai noteiktai problēmu klasei, kas atšķiras tikai ar sākotnējiem datiem. Šajā gadījumā sākotnējos datus var atlasīt no noteikta apgabala, ko sauc par algoritma pielietojamības zonu.

Algoritma koncepcija

Algoritmiskās valodas

Algoritmi. Algoritmizācija.

Algoritma jēdziens datorzinātnēs ir tikpat svarīgs kā informācijas jēdziens. Tāpēc ir svarīgi to saprast.

Vārds "algoritms" nāk no lielākā Vidusāzijas matemātiķa vārda latīņu formas Muhameds ibn Musa al Khvarizmi(Alhorithmi), kurš dzīvoja 783.-850. Savā grāmatā “Par Indijas skaitīšanu” viņš izklāstīja noteikumus par naturālu skaitļu rakstīšanu, izmantojot arābu ciparus, un noteikumus par to lietošanu “kolonnā”, kas tagad ir pazīstami katram skolēnam. 12. gadsimtā šī grāmata tika tulkota latīņu valodā un kļuva plaši izplatīta Eiropā.

Katru dienu cilvēks saskaras ar nepieciešamību ievērot noteiktus noteikumus, izpildīt dažādus norādījumus un norādījumus. Piemēram, šķērsojot ceļu krustojumā bez luksofora, vispirms jāskatās pa kreisi. Ja mašīnas nav, tad šķērsojiet pusceļu, un, ja ir mašīnas, pagaidiet, līdz tās pabrauc garām, tad šķērsojiet pusi. Pēc tam skaties pa labi un, ja mašīnu nav, tad šķērso ceļu līdz galam, un, ja ir mašīnas, pagaidi, kamēr tās brauks garām, un tad šķērso ceļu līdz galam.

Matemātikā, lai atrisinātu tipiskas problēmas, mēs izmantojam noteiktus noteikumus, kas apraksta darbību secību. Piemēram, noteikumi daļskaitļu pievienošanai, kvadrātvienādojumu risināšanai utt. Parasti jebkuras instrukcijas un noteikumi ir darbību secība, kas jāveic noteiktā secībā. Lai atrisinātu problēmu, jums jāzina, kas tiek dots, kas jāsaņem un kādas darbības un kādā secībā jāveic, lai to izdarītu. Recepte, kas nosaka secību, kādā ar datiem tiek veiktas darbības, lai iegūtu vēlamos rezultātus, ir algoritms.

Algoritms- iepriekš noteikta, skaidra un precīza instrukcija iespējamajam izpildītājam veikt noteiktu darbību secību, lai iegūtu problēmas risinājumu ierobežotā soļu skaitā.

Tā nav definīcija šī vārda matemātiskajā nozīmē, bet gan drīzāk apraksts intuitīva algoritma koncepcija, atklājot tā būtību.

Algoritma jēdziens ir ne tikai viens no galvenajiem matemātikas jēdzieniem, bet arī viens no galvenajiem mūsdienu zinātnes jēdzieniem. Turklāt, atnākot datorzinātņu laikmetam, algoritmi kļūst par vienu no svarīgākajiem civilizācijas faktoriem.

Algoritma izpildītājs- tā ir kāda abstrakta vai reāla (tehniska, bioloģiska vai biotehniska) sistēma, kas spēj veikt darbības, ko nosaka algoritms.

Izpildītāju raksturo:

• trešdiena;
• elementāras darbības;
• komandu sistēma;
• atteikumiem.

trešdiena(vai iestatījums) ir izpildītāja “dzīvesvieta”. Piemēram, izpildītājam Robotam no skolas mācību grāmatas vide ir bezgalīgs šūnu lauks. Sienas un krāsotas šūnas arī ir daļa no vides. Un to atrašanās vieta un paša Robota novietojums nosaka konkrētu vides stāvokli.

Komandu sistēma. Katrs izpildītājs var izpildīt komandas tikai no noteikta stingri noteikta saraksta - izpildītāju komandu sistēmas. Katrai komandai ir jānorāda piemērojamības nosacījumi(kādos vides stāvokļos komandu var izpildīt) un aprakstīts komandas izpildes rezultāti. Piemēram, darba komandu “uz augšu” var izpildīt, ja virs Darba nav sienas. Tā rezultāts ir robota pārvietošanās vienu šūnu uz augšu.

Pēc komandas izsaukšanas izpildītājs veic atbilstošo elementāra darbība.

Neveiksmes izpildītāja kļūdas rodas, ja komanda tiek izsaukta vides stāvoklī, kas tai ir nepieņemama.

Datorzinātnē universālais algoritmu izpildītājs ir dators.

| 2.1. §. Algoritmi un izpildītāji

14. nodarbība
2.1. §. Algoritmi un izpildītāji

Atslēgvārdi:

Algoritms
algoritma īpašības (diskrētums; saprotamība; noteiktība; efektivitāte; masas raksturs)
izpildītājs
izpildītāja īpašības (risināmo uzdevumu loks; vide; darbības režīms; komandu sistēma)
algoritma formāla izpilde

2.1.1. Algoritma koncepcija

Katrs cilvēks ikdienas dzīvē, mācībās vai darbā risina milzīgu skaitu dažādas sarežģītības problēmu. Sarežģītas problēmas prasa daudz domāšanas, lai atrastu risinājumu; Cilvēks nedomājot, automātiski risina vienkāršus un pazīstamus uzdevumus. Vairumā gadījumu katras problēmas risinājumu var iedalīt vienkāršos posmos (soļos). Daudziem no šiem uzdevumiem (programmatūras instalēšana, skapja komplektēšana, tīmekļa vietnes izveide, tehniskās ierīces darbība, aviobiļetes iegāde internetā utt.) jau ir izstrādātas un tiek piedāvātas soli pa solim instrukcijas, secīgi. kuru īstenošana var novest pie vēlamā rezultāta.

1. piemērs. Uzdevums “Atrast divu skaitļu vidējo aritmētisko” tiek atrisināts trīs soļos:

1) izdomā divus skaitļus;
2) pievieno divus plānotos skaitļus;
3) iegūto summu dala ar 2.

2. piemērs. Uzdevums “Iemaksāt naudu tālruņa kontā” ir sadalīts šādos posmos:

1) dodieties uz maksājumu termināli;
2) izvēlēties telekomunikāciju operatoru;
3) ievadiet tālruņa numuru;
4) pārbaudiet, vai ievadītais numurs ir pareizs;
5) ievietot banknoti vekseļa pieņēmējā;
6) sagaidi ziņojumu par naudas ieskaitīšanu tavā kontā;
7) saņemt čeku.

3. piemērs. Grafiski parādīti uzdevuma “Uzzīmējiet smieklīgu ezi” risināšanas posmi:

Vidējā aritmētiskā atrašana, naudas iemaksa telefona kontā un eža uzzīmēšana no pirmā acu uzmetiena ir pavisam citi procesi. Bet tiem ir kopīga iezīme: katrs no šiem procesiem ir aprakstīts ar īsu instrukciju secību, kuras stingra ievērošana ļauj iegūt vajadzīgo rezultātu. 1.-3.piemērā dotās instrukciju secības ir atbilstošo problēmu risināšanas algoritmi. Šo algoritmu izpildītājs ir cilvēks.

Algoritms var būt noteiktas aprēķinu secības apraksts (1. piemērs) vai nememātiska rakstura soļi (2.-3. piemēri). Bet jebkurā gadījumā pirms tā izstrādes ir skaidri jādefinē sākotnējie nosacījumi (sākotnējie dati) un iegūstamais (rezultāts). Var teikt, ka algoritms ir problēmas risināšanas darbību secības apraksts, kas ved no sākotnējiem datiem līdz vajadzīgajam rezultātam.

Kopumā algoritma darbības diagrammu var attēlot šādi (2.1. att.).

Rīsi. 2.1. Algoritma vispārīgā shēma

Algoritmi ir skolā apgūti skaitļu saskaitīšanas, atņemšanas, reizināšanas un dalīšanas noteikumi, daudzi gramatikas likumi, ģeometrisko konstrukciju noteikumi utt.

Animācijas “Darbs ar algoritmu” (193576), “Lielākais kopīgais dalītājs” (170363), “Mazākais kopīgais daudzkārtnis” (170390) palīdzēs atcerēties dažus krievu valodas un matemātikas stundās apgūtos algoritmus (http://sc.edu. ru /).

4. piemērs. Daži algoritmi noved pie tā, ka no vienas rakstzīmju ķēdes tiek iegūta jauna ķēde šādi:

1. Tiek aprēķināts sākotnējās rakstzīmju virknes garums (rakstzīmēs).
2. Ja sākotnējās ķēdes garums ir nepāra, tad oriģinālajai ķēdei labajā pusē tiek pievienots skaitlis 1, pretējā gadījumā ķēde nemainās.
3. Simboli tiek apmainīti pa pāriem (pirmais ar otro, trešais ar ceturto, piektais ar sesto utt.).
4. Iegūtās ķēdes labajā pusē tiek pievienots skaitlis 2.

Iegūtā ķēde ir algoritma rezultāts.

Tātad, ja sākotnējā ķēde bija A#B, tad algoritma rezultāts būs ķēde #A1B2, un, ja sākotnējā ķēde bija ABC@, tad algoritma rezultāts būs ķēde BA@B2.

2.1.2. Algoritma izpildītājs

Katrs algoritms ir paredzēts konkrētam izpildītājam.

Izpildītājs ir objekts (persona, dzīvnieks, tehniska ierīce), kas spēj izpildīt noteiktu komandu kopumu.

Atšķirt formālie un neoficiālie izpildītāji. Formāls izpildītājs vienmēr izpilda vienu un to pašu komandu vienādi. Neformāls izpildītājs var izpildīt komandu dažādos veidos.

Ļaujiet mums sīkāk apsvērt formālo izpildītāju kopumu. Formālie izpildītāji ir ārkārtīgi dažādi, taču katram no tiem var norādīt šādus raksturlielumus: risināmo uzdevumu loks (mērķis), vide, komandu sistēma un darbības režīms.

Risināmo uzdevumu klāsts. Katrs izpildītājs ir izveidots, lai atrisinātu noteiktu uzdevumu loku - konstruētu simbolu ķēdes, veiktu aprēķinus, konstruētu zīmējumus uz plaknes utt.

Mākslinieka vide. Teritorija, uzstādījums, apstākļi, kādos izpildītājs darbojas, parasti tiek saukti par dotā izpildītāja vidi. Jebkura algoritma avota dati un rezultāti vienmēr pieder tā izpildītāja videi, kuram algoritms ir paredzēts.

Izpildītāju komandu sistēma. Instrukciju izpildītājam veikt atsevišķu pabeigtu darbību sauc par komandu. Visu komandu kopa, ko var izpildīt kāds izpildītājs, veido šī izpildītāja komandu sistēmu (SKI). Algoritms tiek sastādīts, ņemot vērā konkrēta izpildītāja iespējas, citiem vārdiem sakot, izpildītāja komandu sistēmā, kurš to izpildīs.

Izpildītāju darbības režīmi. Lielākajai daļai izpildītāju tiek nodrošināti tiešās vadības un programmas vadības režīmi. Pirmajā gadījumā izpildītājs gaida komandas no personas un nekavējoties izpilda katru saņemto komandu. Otrajā gadījumā izpildītājam vispirms tiek dota pilnīga komandu secība (programma), un pēc tam viņš visas šīs komandas izpilda automātiski. Vairāki izpildītāji strādā tikai vienā no nosauktajiem režīmiem.

Apskatīsim izpildītāju piemērus.

5. piemērs. Izpildītājs Bruņurupucis pārvietojas datora ekrānā, atstājot pēdas līnijas veidā.

Bruņurupuču komandu sistēma sastāv no šādām komandām:

1. Uz priekšu n (kur n ir vesels skaitlis) - liek Bruņurupucim pārvietot n soļus kustības virzienā - virzienā, kurā ir vērsta tā galva un ķermenis;
2. Labais m (kur m ir vesels skaitlis) - izraisa Bruņurupuča kustības virziena izmaiņas par t grādiem pulksteņrādītāja virzienā.
Ieraksts Atkārtojiet k [<Команда1> <Команда2> ... <Командаn>] nozīmē, ka komandu secība iekavās tiks atkārtota k reizes.

Padomājiet par to, kāda figūra parādīsies ekrānā pēc tam, kad Bruņurupucis izpildīs tālāk norādīto algoritmu.
Atkārtot 12 [pa labi 45 uz priekšu 20 pa labi 45]

6. piemērs. Izpildītāju komandu sistēma Dators sastāv no divām komandām, kurām ir piešķirti numuri:

1 - atņemiet 1
2 - reiziniet ar 3

Pirmais no tiem samazina skaitli par 1, otrais palielina to 3 reizes. Rakstot algoritmus, īsuma labad tiek norādīti tikai komandu numuri. Piemēram, algoritms 21212 nozīmē šādu komandu secību:

Reiziniet ar 3
atņemt 1
reizināt ar 3
atņemt 1
reizināt ar 3

Izmantojot šo algoritmu, skaitlis 1 tiks pārvērsts par 15:

((1 3 - 1) 3 - 1) 3 = 15.

7. piemērs. Izpildītājs Robots darbojas rūtainā laukā, starp blakus esošajām šūnām var būt sienas. Robots pārvietojas pa lauka šūnām un var izpildīt šādas komandas, kurām ir piešķirti numuri:

1 — uz augšu
2 - uz leju
3 - pa labi
4 - pa kreisi

Izpildot katru šādu komandu, robots virzās uz blakus esošo šūnu norādītajā virzienā. Ja šajā virzienā starp šūnām ir siena, tad Robots tiek iznīcināts.

Kas notiks ar Robotu, ja tas izpildīs komandu secību 32323 (šeit cipari norāda komandu numurus), sākot pārvietoties no šūnas A? Kāda komandu secība ir jāizpilda robotam, lai pārietu no šūnas A uz šūnu B, nesabrūkot, atsitoties pret sienām?

Izstrādājot algoritmu:

1) tiek identificēti problēmā sastopamie objekti, tiek noteiktas objektu īpašības, attiecības starp objektiem un iespējamās darbības ar objektiem;
2) tiek noteikti sākotnējie dati un nepieciešamais rezultāts;
3) tiek noteikta izpildītāja darbību secība, nodrošinot pāreju no sākuma datiem uz rezultātu;
4) darbību secība tiek ierakstīta, izmantojot komandas, kas iekļautas izpildītāja komandu sistēmā.

Var teikt, ka algoritms ir algoritma izpildītāja darbības modelis.

2.1.3. Algoritma īpašības

Ne katru instrukciju, instrukciju secību vai rīcības plānu var uzskatīt par algoritmu. Katram algoritmam noteikti ir šādas īpašības: diskrētums, saprotamība, noteiktība, efektivitāte un masveida raksturs.

Diskrēts īpašums nozīmē, ka ceļš uz problēmas risināšanu ir sadalīts atsevišķos soļos (darbībās). Katrai darbībai ir atbilstoša instrukcija (komanda). Tikai pēc vienas komandas izpildes izpildītājs var sākt izpildīt nākamo komandu.

Saprotamības īpašība nozīmē, ka algoritms sastāv tikai no komandām, kas iekļautas izpildītāja komandu sistēmā, t.i., no tādām komandām, kuras izpildītājs var uztvert un saskaņā ar kurām viņš var veikt nepieciešamās darbības.

Pārliecības īpašība nozīmē, ka algoritms nesatur komandas, kuru nozīmi izpildītājs var interpretēt neviennozīmīgi; Nav pieļaujamas situācijas, kad pēc nākamās komandas izpildes izpildītājam nav skaidrs, kuru komandu izpildīt nākamo. Pateicoties tam, algoritma rezultātu unikāli nosaka sākotnējo datu kopa: ja algoritms tiek lietots vairākas reizes vienai un tai pašai sākotnējo datu kopai, tad izvade vienmēr rada vienu un to pašu rezultātu.

Veiktspējas īpašums nozīmē, ka algoritmam jāsniedz rezultāts pēc ierobežota, iespējams, ļoti liela soļu skaita. Šajā gadījumā rezultāts tiek uzskatīts ne tikai par atbildi, ko nosaka problēmas izklāsts, bet arī par secinājumu par neiespējamību turpināt šīs problēmas risināšanu jebkāda iemesla dēļ.

Masu rakstura īpašība nozīmē, ka algoritmam ir jānodrošina tā pielietošanas iespēja, lai atrisinātu jebkuru problēmu no noteiktas uzdevumu klases. Piemēram, kvadrātvienādojuma sakņu atrašanas algoritmam jābūt piemērojamam jebkuram kvadrātvienādojumam, ielas šķērsošanas algoritmam jābūt piemērojamam jebkurā vietā uz ielas, zāļu pagatavošanas algoritmam jābūt piemērojamam jebkura to daudzuma pagatavošanai, utt.

8. piemērs. Apskatīsim vienu no metodēm, kā atrast visus pirmskaitļus, kas nepārsniedz kādu naturālu skaitli n. Šo metodi sauc par “Eratostena sietu” pēc sengrieķu zinātnieka Eratostena (3. gadsimtā pirms mūsu ēras), kurš to ierosināja.

Lai atrastu visus pirmskaitļus, kas nav lielāki par doto skaitli n, izmantojot Eratostena metodi, jāveic šādas darbības:

1) pierakstiet pēc kārtas visus naturālos skaitļus no 2 līdz n (2, 3, 4, ..., n);
2) kadrs 2 - pirmais pirmskaitlis;
3) izsvītro no saraksta visus skaitļus, kas dalās ar pēdējo atrasto pirmskaitli;
4) atrodiet pirmo neatzīmēto skaitli (atzīmētie skaitļi ir izsvītroti skaitļi vai skaitļi, kas ir ietverti rāmī) un ielieciet to rāmī - tas būs vēl viens pirmskaitlis;
5) atkārtojiet 3. un 4. darbību, līdz vairs nav palicis neviens neatzīmēts numurs.

Vizuālāku priekšstatu par pirmskaitļu atrašanas metodi var iegūt, izmantojot animāciju “Eratostena siets” (180279), kas ievietota Vienotajā digitālo izglītības resursu kolekcijā.

Aplūkotā darbību secība ir algoritms, jo tā atbilst šādām īpašībām:

diskrētums- pirmskaitļu atrašanas process ir sadalīts soļos;
saprotamība- katra komanda ir saprotama 8. klases skolēnam, veicot šo algoritmu;
noteiktību- katru komandu izpildītājs interpretē un izpilda nepārprotami; ir norādījumi par komandu izpildes kārtību;
efektivitāti- pēc noteikta soļu skaita tiek sasniegts rezultāts;
masu raksturs- darbību secība ir piemērojama jebkuram naturālam skaitlim n.

Aplūkotās algoritma īpašības ļauj sniegt precīzāku algoritma definīciju.

Algoritms ir konkrētam izpildītājam paredzētas darbību secības apraksts, kas ved no sākotnējiem datiem līdz vajadzīgajam rezultātam, kam piemīt diskrētuma, saprotamības, noteiktības, efektivitātes un masveida rakstura īpašības.

2.1.4. Cilvēka darbību automatizācijas iespēja

Algoritma izstrāde parasti ir darbietilpīgs darbs, kas no cilvēka prasa dziļas zināšanas, atjautību un daudz laika.

Lai atrisinātu problēmu, izmantojot gatavu algoritmu, izpildītājam ir tikai stingri jāievēro sniegtie norādījumi.

9. piemērs. No kaudzes, kurā ir jebkurš objektu skaits, kas lielāks par trim, divi spēlētāji pārmaiņus paņem katrs vienu vai divus priekšmetus. Uzvar tas, kurš savā nākamajā gājienā var paņemt visas atlikušās preces.

Apskatīsim algoritmu, pēc kura pirmais spēlētājs noteikti nodrošinās uzvaru.

1. Ja objektu skaits kaudzē ir reizināts ar 3, tad dodiet ceļu pretiniekam, pretējā gadījumā sāciet spēli, paņemot 1 vai 2 objektus, lai atlikušo objektu skaits būtu 3 reizes.
2. Ar nākamo gājienu katru reizi pievienojiet pretinieka paņemto objektu skaitu līdz 3 (atlikušo objektu skaitam ir jābūt reizinātam ar 3).

Izpildītājs var neiedziļināties tajā, ko viņš dara, un nedomāt, kāpēc viņš rīkojas tā un ne citādi, tas ir, viņš var rīkoties formāli. Izpildītāja spēja rīkoties formāli nodrošina cilvēka darbības automatizācijas iespēju. Priekš šī:

1) problēmas risināšanas process tiek pasniegts kā vienkāršu darbību secība;
2) ir izveidota mašīna (automātiskā iekārta), kas spēj veikt šīs darbības algoritmā noteiktajā secībā;
3) cilvēks tiek atbrīvots no rutīnas darbībām, algoritma izpilde tiek uzticēta automātiskai iekārtai.

SVARĪGĀKĀ

Izpildītājs- kāds objekts (persona, dzīvnieks, tehniska ierīce), kas spēj izpildīt noteiktu komandu kopu.

Formāls izpildītājs vienmēr izpilda vienu un to pašu komandu vienādi. Katram oficiālajam izpildītājam varat norādīt: risināmo uzdevumu klāsts, vide, komandu sistēma un darbības režīms.

Algoritms- konkrētam izpildītājam paredzēto darbību secības apraksts, kas ved no sākotnējiem datiem līdz vajadzīgajam rezultātam, kuram piemīt diskrētuma, saprotamības, noteiktības, efektivitātes un masveida rakstura īpašības.

Izpildītāja spēja darboties formāli nodrošina iespēju automatizēt cilvēka darbības.

Jautājumi un uzdevumi

1. Izlasiet mācību grāmatas elektroniskajā pielikumā ietvertās rindkopas prezentācijas materiālus. Vai prezentācija papildina rindkopas tekstā ietverto informāciju? Kādus slaidus jūs varētu izmantot, lai papildinātu savu prezentāciju?

2. Ko sauc par algoritmu?

3. Izvēlieties sinonīmus vārdam “recepte”.

4. Sniedziet skolā apgūto algoritmu piemērus.

5. Kas var būt algoritma izpildītājs?

6. Sniedziet formāla izpildītāja piemēru. Sniedziet piemēru, kad persona darbojas kā formāls izpildītājs.

7. Kas nosaka “datora” izpildītāja veicamo uzdevumu loku?

8. Uzskatiet tekstapstrādes programmu savā datorā par izpildītāju. Aprakstiet šī izpildītāja un viņa vides atrisināto uzdevumu klāstu.

9. Kas ir komanda, izpildītāju komandu sistēma?

10. Kādas komandas robotam jāveic šādas funkcijas:

a) kasiere veikalā;
b) sētnieks;
c) apsargs?

11. Uzskaitiet galvenās algoritma īpašības.

12. Pie kā var novest algoritma īpašību neesamība? Sniedziet piemērus.

13. Kāda nozīme ir spējai formāli izpildīt algoritmu?

14. Skaitļu secība tiek konstruēta pēc šāda algoritma: secības pirmie divi skaitļi tiek pieņemti vienādi ar 1; Katrs nākamais skaitlis secībā ir vienāds ar divu iepriekšējo skaitļu summu. Pierakstiet šīs secības pirmos 10 vārdus. Uzziniet, kā sauc šo secību.

15. Noteikts algoritms iegūst jaunu ķēdi no vienas rakstzīmju virknes šādi. Vispirms tiek uzrakstīta sākotnējā rakstzīmju ķēde, pēc tās tiek rakstīta sākotnējā rakstzīmju ķēde apgrieztā secībā, pēc tam tiek rakstīts burts, kas seko krievu alfabētā pēc burta, kas bija pēdējā vietā sākotnējā ķēdē. Ja burts “I” atrodas sākotnējā ķēdes pēdējā vietā, tad burts “A” tiek rakstīts kā nākamais burts. Iegūtā ķēde ir algoritma rezultāts. Piemēram, ja sākotnējā rakstzīmju ķēde bija “HOUSE”, tad algoritma rezultāts būs ķēde “DOMMODN”. Tiek dota rakstzīmju virkne “COM”. Cik burtu “O” būs rakstzīmju ķēdē, kas tiks iegūta, ja šai ķēdei piemērosit algoritmu un pēc tam vēlreiz piemērosit algoritmu tās darba rezultātam?

16. Atrodiet internetā Eratostena algoritma soļu animāciju. Izmantojiet Eratostena algoritmu, lai atrastu visus pirmskaitļus, kas nepārsniedz 50.

17. Kāds būs algoritma bruņurupuča izpildes rezultāts (skat. 5. piemēru)?

18. Pierakstiet kalkulatora izpildītāja algoritmu (skatiet 6. piemēru), kas satur ne vairāk kā 5 komandas:

a) saņemot no skaitļa 3 skaitli 16;
b) saņemot no skaitļa 1 skaitli 25.

19. Izpildītāju komandu sistēma Konstruktors sastāv no divām komandām, kurām ir piešķirti numuri:

1 — piešķirt 2
2 - dalīt ar 2

Saskaņā ar pirmo no tiem skaitlim labajā pusē tiek pievienots 2, saskaņā ar otro skaitli dala ar 2. Kā tiks pārvērsts skaitlis 8, ja izpildītājs izpilda algoritmu 22212? Šī izpildītāja komandu sistēmā izveidojiet algoritmu, saskaņā ar kuru skaitlis 1 tiks pārveidots par skaitli 16 (algoritmā jābūt ne vairāk kā 5 komandām).

20. Kurā šūnā jāatrodas Robota izpildītājam (7. piemērs), lai atgrieztos tajā pēc algoritma 3241 izpildes?

Bezmaksas programmatūra:

KuMir sistēma - izglītības pasauļu komplekts (lejupielādējiet programmas arhīvu no vietnes) vai apmeklējiet KuMir lapu ((http://www.niisi.ru/kumir/)

Algoritma jēdziens. Algoritmu izpildītāji. Algoritmu īpašības

Algoritma jēdziens datorzinātnēs ir tikpat svarīgs kā informācijas jēdziens. Algoritmam ir daudz dažādu definīciju, jo šis jēdziens ir diezgan plašs un tiek izmantots dažādās zinātnes, tehnoloģiju un ikdienas dzīves jomās.

Algoritms ir skaidra un precīza darbību secība, kas apraksta objekta pārveidošanas procesu no sākotnējā stāvokļa uz galīgo stāvokli.

Algoritms ir precīzs darbību secības apraksts, kas paredzēts konkrētam izpildītājam un kuras mērķis ir atrisināt noteiktu problēmu.

Izpildītājs Algoritms var būt vai nu cilvēks (gatavošanas receptes, dažādas instrukcijas, matemātisko aprēķinu algoritmi), vai tehniska ierīce. Ir dažādas mašīnas (datori, industriālie roboti, moderna sadzīves tehnika). formālie izpildītāji algoritmi. Formālajam izpildītājam nav jāsaprot risināmās problēmas būtība, bet gan precīzi jāizpilda komandu secība.

Algoritmu var rakstīt dažādos veidos (verbāls apraksts, grafiskais apraksts - blokshēma, programma kādā no programmēšanas valodām utt.). Programma ir algoritms, kas ierakstītsprogrammēšanas valoda .

Lai izveidotu algoritmu (programmu), jums jāzina:

sākotnējā uzdevuma datu pilns komplekts (objekta sākotnējais stāvoklis);

algoritma izveides mērķis (objekta gala stāvoklis);

izpildītāja komandu sistēma (tas ir, komandu kopums, ko izpildītājs saprot un var izpildīt).

Iegūtajam algoritmam (programmai) ir jābūt šādai īpašību kopai:

diskrētums (algoritms ir sadalīts atsevišķos soļos - komandās);

nepārprotamība (katra komanda nosaka vienīgo iespējamo izpildītāja darbību);

skaidrība (visas algoritmu komandas ir iekļautas izpildītāju komandu sistēmā);

efektivitāti (izpildītājam uzdevums ir jāatrisina ierobežotā soļu skaitā).

Lielākajai daļai algoritmu ir arī īpašums masu raksturs (izmantojot to pašu algoritmu, jūs varat atrisināt daudzas līdzīgas problēmas).

Algoritmu aprakstīšanas veidi

Iepriekš tika atzīmēts, ka vienu un to pašu algoritmu var uzrakstīt dažādos veidos. Jūs varat pierakstīt algoritmu dabiskā valoda. Tā mēs izmantojam receptes, instrukcijas utt. Lai ierakstītu algoritmus, kas paredzēti formāliem izpildītājiem, speciālā programmēšanas valodas. Var aprakstīt jebkuru algoritmu grafiski blokshēmas veidā. Šim nolūkam ir izveidota īpaša apzīmējumu sistēma:

Sniegsim piemēru divu lielumu summēšanas algoritma aprakstam blokshēmas veidā:

Šāds algoritma aprakstīšanas veids ir visredzamākais un cilvēkiem saprotamākais. Tāpēc formālo izpildītāju algoritmi parasti vispirms tiek izstrādāti blokshēmas veidā un tikai pēc tam izveido programmu vienā noprogrammēšanas valodas .

Tipiskas algoritmiskās struktūras

Programmētājam ir iespēja konstruēt un izmantot netipiskas algoritmiskas struktūras, tomēr tas nav nepieciešams. Jebkuru algoritmu, neatkarīgi no tā, cik sarežģīts, var izstrādāt, pamatojoties uz trim tipiskām struktūrām: sekošanu, sazarošanu un atkārtošanos. Šajā gadījumā struktūras var atrasties secīgi viena pēc otras vai ligzdotas viena otrā.

Lineāra struktūra (seko)

Vienkāršākā algoritmiskā struktūra ir lineārs. Tajā visas darbības tiek veiktas vienu reizi tādā secībā, kādā tās ierakstītas.

Sazarošanās

IN pilna zarošanās Izpildītāja darbībām ir divas iespējas atkarībā no loģiskās izteiksmes (nosacījuma) vērtības. Ja nosacījums ir patiess, tiks izpildīts tikai pirmais zars, pretējā gadījumā tikai otrais zars.

Otrais zars var būt tukšs. Šo struktūru sauc nepilnīga atzarošana vai apvedceļš.

No vairākām filiālēm jūs varat izveidot struktūru " izvēle”(vairāku atzarojumu), kas izvēlēsies nevis no divām, bet no lielāka skaita izpildītāja darbību opcijām atkarībā no vairākiem nosacījumiem. Svarīgi, lai tiktu izpildīts tikai viens zars - šādā struktūrā svarīga kļūst nosacījumu secība: ja ir izpildīti vairāki nosacījumi, tad derēs tikai viens no tiem - pirmais no augšas.

Cikls (atkārtojums)

Ciklsļauj organizēt vairākas vienas un tās pašas komandu secības atkārtojumus- to sauc par cikla ķermeni. Dažāda veida cikliskajos algoritmos atkārtojumu skaits var būt atkarīgs no loģiskās izteiksmes (nosacījuma) vērtības vai arī var būt stingri iekodēts pašā struktūrā. Ir cikli: " pirms tam», « Uz redzēšanos», cilpas ar skaitītāju. Cilpās "līdz" un "kamēr" loģiska izteiksme (nosacījums) var būt pirms cilpas pamatteksta ( cilpa ar priekšnosacījumu) vai beidz cilpu ( cilpa ar pēcnosacījumu).

Cikli« pirms tam» - cikla ķermeņa atkārtošanās līdz nosacījums ir izpildīts:

Cikli « Uz redzēšanos» - cikla ķermeņa atkārtošanās kamēr nosacījums ir izpildīts(patiesa):

Cilpas ar skaitītāju(ar parametru)– atkārtojot cilpas pamattekstu noteiktu skaitu reižu:

Papildalgoritms (apakšprogramma, procedūra)

Palīg algoritms ir modulis, kuram var piekļūt atkārtoti no galvenā algoritma. Papildalgoritmu izmantošana var ievērojami samazināt algoritma izmēru un vienkāršot tā izstrādi.

Sarežģītu algoritmu izstrādes metodes

Ir divas metodes sarežģītu algoritmu izstrādei:

Secīgo uzdevumu detalizācijas metode(“no augšas uz leju”) nozīmē, ka sākotnējais sarežģītais uzdevums ir sadalīts apakšuzdevumos. Katrs no apakšuzdevumiem tiek izskatīts un atrisināts atsevišķi. Ja kāds no apakšuzdevumiem ir sarežģīts, tie arī tiek sadalīti apakšuzdevumos. Process turpinās, līdz apakšuzdevumi tiek reducēti uz elementāriem. Pēc tam atsevišķu apakšproblēmu risinājumi tiek apvienoti vienā algoritmā sākotnējās problēmas risināšanai. Metode tiek plaši izmantota, jo ļauj vairākiem programmētājiem vienlaikus izstrādāt vispārīgu algoritmu un risināt lokālas apakšproblēmas. Tas ir nepieciešams nosacījums ātrai programmatūras izstrādei.

Montāžas metode(“no apakšas uz augšu”) ir dažādu programmatūras moduļu izveide, kas īsteno tipisku problēmu risinājumu. Risinot sarežģītu uzdevumu, programmētājs izstrādātos moduļus var izmantot kā palīgalgoritmus (procedūras). Daudzos programmēšanas sistēmas Līdzīgi moduļu komplekti jau pastāv, kas ievērojami vienkāršo un paātrina sarežģīta algoritma izveidi.

Algoritmi un kontroles procesi

Kontrole - mērķtiecīga objektu mijiedarbība, no kuriem daži ir vadītāji, citi - pārvaldīti.

Vienkāršākajā gadījumā ir divi šādi objekti:

No datorzinātņu viedokļa kontroles darbības var uzskatīt par kontroles informāciju. Informāciju var pārsūtīt komandu veidā. Tiek izsaukta komandu secība, lai kontrolētu objektu, kas ved uz iepriekš noteiktu mērķi kontroles algoritms. Līdz ar to vadības objektu var saukt par vadības algoritma izpildītāju. Aplūkotajā piemērā vadības objekts darbojas “neskatoties” uz to, kas notiek ar kontroles objektu ( atvērtās cilpas vadība atvērts. Citā vadības shēmā var ņemt vērā informāciju par procesiem, kas notiek vadības objektā:

Šajā gadījumā vadības algoritmam jābūt pietiekami elastīgam, lai analizētu šo informāciju un pieņemtu lēmumus par turpmākajām darbībām atkarībā no vadības objekta stāvokļa ( atgriezeniskās saites kontrole). Šo kontroles shēmu sauc slēgts.

Vadības procesi tiek pētīti sīkāk un apspriesti kibernētika. Šī zinātne apgalvo, ka visdažādākie vadības procesi sabiedrībā, dabā un tehnoloģijās notiek līdzīgi un ir pakļauti vieniem un tiem pašiem principiem.

Līdz tēmas sākumam