domov › Navigatorji › Izvedba algoritma za določeno odločitev izvajalca. Računalništvo in informacijska tehnologija. Načini opisovanja algoritmov

Izvedba algoritma za določeno odločitev izvajalca. Računalništvo in informacijska tehnologija. Načini opisovanja algoritmov

Ključne besede:

algoritem
lastnosti algoritma
- diskretnost
- jasnost
- gotovost
- učinkovitost
- množični značaj
izvršitelj

lastnosti izvajalca
- nabor nalog, ki jih je treba rešiti
- sreda
- način delovanja
- ukazni sistem
formalna izvedba algoritma

3.1.1. Koncept algoritma

Vsaka oseba v Vsakdanje življenje, pri študiju ali v službi rešuje ogromno problemov različnih zahtevnosti. Kompleksni problemi zahtevajo veliko razmišljanja, da bi našli rešitev; Človek rešuje preproste in znane naloge brez razmišljanja, samodejno. V večini primerov lahko rešitev vsake težave razdelimo na preproste stopnje (korake). Za številna taka opravila (namestitev programsko opremo, sestava kabineta, izdelava spletne strani, upravljanje tehnične naprave, nakup letalske vozovnice preko interneta ipd.) so že razviti in ponujeni navodila po korakih, ki ob doslednem izvajanju lahko vodi do želenega rezultata.

Primer 1. Nalogo »Poišči aritmetično sredino dveh števil« rešujemo v treh korakih:

pomislite na dve številki;
seštejte dve števili v mislih;
dobljeno količino delite z 2.

Primer 2. Naloga »Polog denarja na vaš telefonski račun« je razdeljena na naslednje korake:

pojdite na plačilni terminal;
izberite telekomunikacijskega operaterja;
vnesite telefonsko številko;
preverite pravilnost vnesene številke;
vstavite bankovec v sprejemnik;
počakajte na sporočilo o nakazilu denarja na vaš račun;
prejeti ček.

Primer 3. Faze reševanja problema "Nariši smešnega ježa" so predstavljene grafično:

Iskanje aritmetične sredine, polaganje denarja na telefonski račun in risanje ježka so na prvi pogled povsem različni procesi. Vendar imajo skupno lastnost: vsak od teh procesov je opisan z zaporedjem kratkih navodil, katerih dosledno upoštevanje vam omogoča, da dobite zahtevani rezultat. Zaporedja ukazov, podana v primerih 1-3, so algoritmi za reševanje ustreznih problemov. Izvajalec teh algoritmov je oseba.

Algoritem je lahko opis določenega zaporedja izračunov (primer 1) ali korakov nematematične narave (primeri 2-3). Toda v vsakem primeru, pred njegovim razvojem, začetni pogoji(vhodni podatki) in kaj je treba pridobiti (rezultat). Lahko rečemo, da je algoritem opis zaporedja korakov pri reševanju problema, ki vodi od začetnih podatkov do zahtevanega rezultata.

Na splošno lahko diagram delovanja algoritma predstavimo na naslednji način (slika 3.1):

riž. 3.1.
Splošna shema algoritma

Algoritmi so pravila seštevanja, odštevanja, množenja in deljenja števil, slovnična pravila, pravila geometrijskih konstrukcij itd., Ki se učijo v šoli.

Animacije »Delo z algoritmom«, »Največji skupni delitelj«, »Najmanjši skupni večkratnik« (http://school-collection.edu.ru/) vam bodo pomagale zapomniti nekaj algoritmov, ki ste jih preučevali pri lekcijah ruskega jezika in matematike.

Primer 4. Neki algoritem vodi do dejstva, da iz ene verige znakov dobimo novo verigo, kot sledi:

Izračuna se dolžina (v znakih) izvornega niza znakov.
Če je dolžina prvotne verige liha, se prvotni verigi na desni doda številka 1, sicer se veriga ne spremeni.
Simboli se zamenjajo v parih (prvi z drugim, tretji s četrtim, peti s šestim itd.).
Desno od nastale verige se doda številka 2.

Nastala veriga je rezultat algoritma.

Torej, če je bila začetna veriga A#B, bo rezultat algoritma veriga #A1B2, in če je bila začetna veriga ABC@, bo rezultat algoritma veriga BA@B2.

3.1.2. Izvajalec algoritma

Vsak algoritem je zasnovan za določenega izvajalca.

Obstajajo formalni in neformalni izvajalci. Formalni izvajalec vedno izvede isti ukaz na enak način. Neformalni izvajalec lahko ukaz izvede na različne načine.

Oglejmo si podrobneje nabor formalnih izvajalcev. Formalni izvajalci so izjemno raznoliki, vendar je za vsakega od njih mogoče določiti naslednje značilnosti: obseg nalog, ki jih je treba rešiti (namen), okolje, sistem poveljevanja in način delovanja.

Obseg nalog, ki jih je treba rešiti. Vsak izvajalec je ustvarjen za reševanje določenega obsega problemov - konstruiranje verig simbolov, izvajanje izračunov, konstruiranje risb na ravnini itd.

Umetniško okolje. Območje, okolje, razmere, v katerih izvajalec deluje, običajno imenujemo okolje danega izvajalca. Izvorni podatki in rezultati katerega koli algoritma vedno pripadajo okolju izvajalca, ki mu je algoritem namenjen.

Sistem ukazov izvajalca. Navodilo izvajalcu za izvedbo ločenega dokončanega dejanja se imenuje ukaz. Množica vseh ukazov, ki jih lahko izvaja nek izvajalec, tvori sistem ukazov za ta izvajalec (SKI). Algoritem je sestavljen ob upoštevanju zmožnosti določenega izvajalca, z drugimi besedami, v sistemu ukazov izvajalca, ki ga bo izvajal.

Načini delovanja izvajalca. Za večino izvajalcev so načini neposrednega nadzora in nadzor programa. V prvem primeru izvajalec čaka na ukaze osebe in takoj izvede vsak prejeti ukaz. V drugem primeru izvajalec najprej dobi celotno zaporedje ukazov (program), nato pa vse te ukaze izvede v avtomatski način. Številni izvajalci delujejo samo v enem od imenovanih načinov.

Poglejmo primere izvajalcev.

Primer 5. Izvajalec Želva se premika po računalniškem zaslonu in pušča sled v obliki črte. Želvin sistem ukazov je sestavljen iz dveh ukazov:

Desno m (kjer je m celo število) - povzroči, da se smer gibanja želve spremeni za m stopinj v smeri urinega kazalca.

Snemaj Ponovi k [<Команда1> <Команда2> ... <Командаn>] pomeni, da se bo zaporedje ukazov v oklepajih ponovilo k-krat.

Pomislite, katera številka se bo pojavila na zaslonu, ko bo želva dokončala naslednji algoritem.

Ponovi 12 [desno 4 5 naprej 20 desno 45]

Primer 6. Sistem izvršilnih ukazov Računalnik je sestavljen iz dveh ukazov, ki imata dodeljene številke:

Prvi izmed njih zmanjša število za 1, drugi poveča število za 3-krat. Pri pisanju algoritmov so zaradi jedrnatosti navedene samo številke ukazov. Na primer, algoritem 21212 pomeni naslednje zaporedje ukazov:

S tem algoritmom bo število 1 pretvorjeno v 15: ((1-3-1)-3-1)-3 = 15.

Primer 7. Performer Robot deluje na karirastem polju, med sosednjimi celicami so lahko zidovi. Robot se premika po celicah polja in lahko izvaja naslednje ukaze, ki so jim dodeljene številke:

Pri izvajanju vsakega takega ukaza se robot premakne v sosednjo celico v navedeni smeri. Če je v tej smeri med celicami zid, je robot uničen. Kaj se bo zgodilo z robotom, če izvede zaporedje ukazov 32323 (tukaj številke označujejo številke ukazov), ki se začne premikati iz celice A? Katero zaporedje ukazov mora izvesti robot, da se premakne iz celice A v celico B, ne da bi se zrušil, ko trči ob stene?

Pri razvoju algoritma:

identificirani so predmeti, ki se pojavljajo v problemu, lastnosti predmetov, odnosi med objekti in možna dejanja s predmeti;
določeni so začetni podatki in zahtevani rezultat;
določeno je zaporedje dejanj izvajalca, ki zagotavlja prehod od začetnih podatkov do rezultata;
zaporedje dejanj se zabeleži z ukazi, vključenimi v ukazni sistem izvršitelja.

Lahko rečemo, da je algoritem model aktivnosti izvajalca algoritma.

3.1.3. Lastnosti algoritma

Vsako navodilo, zaporedje navodil ali akcijski načrt ni mogoče obravnavati kot algoritem. Vsak algoritem ima nujno naslednje lastnosti: diskretnost, razumljivost, gotovost, učinkovitost in masovnost.

Lastnost diskretnosti pomeni, da je pot do rešitve problema razdeljena na ločene korake (akcije). Vsako dejanje ima ustrezno navodilo (ukaz). Šele po izvedbi enega ukaza lahko izvajalec začne izvajati naslednji ukaz.

Lastnost razumljivosti pomeni, da je algoritem sestavljen samo iz ukazov, ki so vključeni v sistem ukazov izvajalca, to je iz takšnih ukazov, ki jih izvajalec lahko zazna in po katerih lahko izvaja zahtevana dejanja.

Lastnost gotovosti pomeni, da algoritem ne vsebuje ukazov, katerih pomen si lahko izvajalec razlaga dvoumno; Nesprejemljive so situacije, ko izvajalcu po izvedbi naslednjega ukaza ni jasno, kateri ukaz naj izvede v naslednjem koraku.

Lastnost učinkovitosti pomeni, da mora biti algoritem sposoben pridobiti rezultat po končnem, po možnosti zelo velikem številu korakov. V tem primeru se za rezultat ne šteje le odgovor, določen z izjavo o problemu, temveč tudi sklep o nezmožnosti nadaljnjega reševanja tega problema iz katerega koli razloga.

Lastnost masovne proizvodnje pomeni, da mora algoritem zagotavljati možnost njegove uporabe za reševanje katerega koli problema iz določenega razreda problemov. Na primer, algoritem za iskanje korenin kvadratne enačbe bi moral biti uporaben za katero koli kvadratno enačbo, algoritem za prečkanje ulice bi moral biti uporaben kjer koli na ulici, algoritem za pripravo zdravila bi moral biti uporaben za pripravo katere koli količine zdravila, itd.

Primer 8. Oglejmo si eno od metod za iskanje vseh praštevil, ki ne presegajo n. Ta metoda se imenuje "Eratostenovo sito", poimenovana po starogrškem znanstveniku Eratostenu, ki jo je predlagal.

Če želite najti vsa praštevila, ki niso večja od danega števila n, po Eratostenovi metodi, morate izvesti naslednje korake:

zapiši vsa cela števila od 2 do n po vrsti (2, 3, 4, ..., n);
okvir 2 - prvo praštevilo;
s seznama prečrtajte vsa števila, ki so deljiva z zadnjim najdenim praštevilom;
poišči prvo neoznačeno število (označena števila so prečrtana števila ali števila, zaprta v okvir) in ga obdaj v okvir - to bo drugo praštevilo;
ponavljajte koraka 3 in 4, dokler ne ostane nobena neoznačena številka.

Z animacijo »Eratostenovo sito« (http://school-collection.edu.ru/) lahko dobite bolj vizualno predstavo o metodi iskanja praštevil.

Obravnavano zaporedje dejanj je algoritem, saj izpolnjuje naslednje lastnosti:

diskretnost - postopek iskanja praštevil je razdeljen na korake;
razumljivost - vsak ukaz je razumljiv učencu 9. razreda, ki izvaja ta algoritem;
gotovost - vsak ukaz izvajalec nedvoumno razlaga in izvaja; obstajajo navodila o vrstnem redu izvajanja ukazov;
učinkovitost - po določenem številu korakov je dosežen rezultat;
množični značaj - zaporedje dejanj velja za vse naravne n.

Obravnavane lastnosti algoritma nam omogočajo natančnejšo definicijo algoritma.

3.1.4. Možnost avtomatizacije človekovih dejavnosti

Razvoj algoritma je običajno delovno intenzivna naloga, ki od osebe zahteva globoko znanje, iznajdljivost in veliko časa.

Reševanje problema z že pripravljenim algoritmom od izvajalca zahteva le dosledno upoštevanje danih navodil.

Primer 9. Iz kupa, ki vsebuje poljubno število predmetov, večje od treh, dva igralca izmenično vzameta enega ali dva predmeta. Zmagovalec je tisti, ki lahko na naslednji potezi pobere vse preostale predmete.

Oglejmo si algoritem, po katerem bo prvi igralec zagotovo zagotovil zmago.

Če je število predmetov v kupu večkratnik števila 3, popustite nasprotniku, sicer začnite igro.
Z naslednjo potezo vsakič dodajte število predmetov, ki jih je vzel nasprotnik, na 3 (število preostalih predmetov mora biti večkratnik 3).

Izvajalec se lahko ne poglablja v pomen tega, kar počne, in ne utemeljuje, zakaj ravna tako in ne drugače, torej lahko ravna formalno. Sposobnost izvajalca, da deluje formalno, daje možnost avtomatizacije človekove dejavnosti. Za to:

proces reševanja problema je predstavljen kot zaporedje preprostih operacij;
nastane stroj ( avtomatska naprava), sposobni izvajati te operacije v zaporedju, določenem v algoritmu;
oseba je osvobojena rutinskih dejavnosti, izvajanje algoritma je zaupano avtomatski napravi.

Najpomembnejše

Izvajalec - nek predmet (oseba, žival, tehnična naprava), ki lahko izvajajo določen nabor ukazov. Formalni izvajalec vedno izvede isti ukaz na enak način. Za vsakega formalnega izvajalca lahko določite: obseg nalog, ki jih je treba rešiti, okolje, sistem ukazov in način delovanja.

Algoritem je opis zaporedja dejanj, namenjenih določenemu izvajalcu, ki vodijo od začetnih podatkov do zahtevanega rezultata, ki ima lastnosti diskretnosti, razumljivosti, gotovosti, učinkovitosti in masovnosti.

Sposobnost izvajalca, da deluje formalno, daje možnost avtomatizacije človekove dejavnosti.

Vprašanja in naloge

Kako se imenuje algoritem?
Poiščite sinonime za besedo "recept".
Navedite primere algoritmov, ki ste se jih učili v šoli.
Kdo je lahko izvajalec algoritma?
Navedite primer formalnega izvajalca. Navedite primer, ko oseba nastopa kot uradni izvajalec.
Katere ukaze naj robot opravlja kot: a) blagajnik v trgovini; b) hišnik; c) varnostnik?
Kaj določa obseg nalog, ki jih izvaja »računalniški« izvajalec?
Razmislite kot izvajalec urejevalnik besedil, ki je na voljo v vašem računalniku. Opišite obseg nalog, ki jih rešuje ta izvajalec in njegovo okolje.
Kaj je ekipa, sistem izvajalskih ukazov?
Navedite glavne lastnosti algoritma.
Do česa lahko privede odsotnost katere koli lastnosti v algoritmu? Navedite primere.
Zakaj je pomembno, da lahko formalno izvedemo algoritem?
Zaporedje številk je sestavljeno po naslednjem algoritmu: prvi dve številki zaporedja sta enaki 1; Vsako naslednje število v zaporedju je enako vsoti prejšnjih dveh števil. Zapišite prvih 10 členov tega zaporedja.
Nekateri algoritmi pridobijo novo verigo iz enega niza znakov, kot sledi. Najprej se napiše izvirna veriga znakov, za njo se napiše prvotna veriga znakov v obratnem vrstnem redu, nato se napiše črka, ki sledi v ruski abecedi za črko, ki je bila v prvotni verigi na zadnjem mestu. Če je zadnje mesto v prvotni verigi črka Z, se kot naslednja črka zapiše črka A. Nastala veriga je rezultat algoritma. Na primer, če je bila prvotna veriga znakov DOM, bo rezultat algoritma veriga DOMMODN. Podan je niz znakov COM. Koliko črk O bo v verigi simbolov, ki jo bomo dobili, če algoritem uporabimo za to verigo in nato ponovno uporabimo algoritem za rezultat njegovega dela?
Na internetu poišči animacijo korakov Eratostenovega algoritma. Uporabite Eratostenov algoritem, da poiščete vsa praštevila, ki ne presegajo 50.
Kakšen bo rezultat Turtle-jeve izvedbe (glej primer 5) algoritma?
Zapišite algoritem za izvajalca kalkulatorja (primer 6), ki ne vsebuje več kot 5 ukazov:
Sistem izvajalskih ukazov Konstruktor je sestavljen iz dveh ukazov, ki imata dodeljene številke:
Po prvem od njih se številki na desni doda 2, po drugem pa se število deli z 2. Kako se pretvori število 8, če izvajalec izvede algoritem 22212? V sistemu ukazov tega izvajalca ustvarite algoritem, po katerem se bo število 1 pretvorilo v število 16 (algoritem naj vsebuje največ 5 ukazov).
V kateri celici naj se nahaja izvajalec robota (primer 7), da se vanjo vrne po izvedbi algoritma 3241?

| § 2.1. Algoritmi in izvajalci

Lekcija 14
§ 2.1. Algoritmi in izvajalci

Ključne besede:

Algoritem
lastnosti algoritma (diskretnost; razumljivost; gotovost; učinkovitost; množičnost)
izvršitelj
značilnosti izvajalca (nabor nalog, ki jih je treba rešiti; okolje; način delovanja; sistem ukazov)
formalna izvedba algoritma

2.1.1. Koncept algoritma

Vsak človek v vsakdanjem življenju, med študijem ali pri delu rešuje ogromno težav različne kompleksnosti. Kompleksni problemi zahtevajo veliko razmišljanja, da bi našli rešitev; Človek rešuje preproste in znane naloge brez razmišljanja, samodejno. V večini primerov lahko rešitev vsake težave razdelimo na preproste stopnje (korake). Za mnoga od teh opravil (namestitev programske opreme, sestavljanje omare, izdelava spletne strani, upravljanje s tehnično napravo, nakup letalske vozovnice preko interneta itd.) so že izdelana in so na voljo navodila po korakih, zaporedni katerih izvajanje lahko vodi do želenega rezultata.

Primer 1. Nalogo »Poišči aritmetično sredino dveh števil« rešujemo v treh korakih:

1) pomislite na dve številki;
2) seštejte dve načrtovani številki;
3) dobljeni znesek razdelite na 2.

Primer 2. Naloga »Polog denarja na vaš telefonski račun« je razdeljena na naslednje korake:

1) pojdite na plačilni terminal;
2) izberite telekomunikacijskega operaterja;
3) vnesite telefonsko številko;
4) preverite pravilnost vnesene številke;
5) vstavite bankovec v sprejemnik;
6) počakajte na sporočilo o nakazilu denarja na vaš račun;
7) prejeti ček.

Primer 3. Faze reševanja problema "Nariši smešnega ježa" so predstavljene grafično:

Algoritem je lahko opis določenega zaporedja izračunov (primer 1) ali korakov nematematične narave (primeri 2-3). Vsekakor pa je treba pred njegovim razvojem jasno določiti začetne pogoje (začetne podatke) in kaj naj bi dobili (rezultat). Lahko rečemo, da je algoritem opis zaporedja korakov pri reševanju problema, ki vodi od začetnih podatkov do zahtevanega rezultata.

Na splošno lahko diagram delovanja algoritma predstavimo na naslednji način (slika 2.1).

riž. 2.1. Splošna shema algoritma

Algoritmi so pravila seštevanja, odštevanja, množenja in deljenja števil, ki se preučujejo v šoli, številna slovnična pravila, pravila geometrijskih konstrukcij itd.

Animacije »Delo z algoritmom« (193576), »Največji skupni delitelj« (170363), »Najmanjši skupni večkratnik« (170390) vam bodo pomagale zapomniti nekaj algoritmov, ki ste jih preučevali pri lekcijah ruskega jezika in matematike (http://sc.edu. ru /).

Primer 4. Neki algoritem vodi do dejstva, da iz ene verige znakov dobimo novo verigo, kot sledi:

1. Izračuna se dolžina (v znakih) izvirnega niza znakov.
2. Če je dolžina prvotne verige liha, se številka 1 doda prvotni verigi na desni, sicer se veriga ne spremeni.
3. Simboli se zamenjajo v parih (prvi z drugim, tretji s četrtim, peti s šestim itd.).
4. Desno od nastale verige se doda številka 2.

Nastala veriga je rezultat algoritma.

Torej, če je bila začetna veriga A#B, bo rezultat algoritma veriga #A1B2, in če je bila začetna veriga ABC@, bo rezultat algoritma veriga BA@B2.

2.1.2. Izvajalec algoritma

Vsak algoritem je zasnovan za določenega izvajalca.

Eksekutor je objekt (oseba, žival, tehnična naprava), ki je sposoben izvajati določen niz ukazov.

Razlikovati formalni in neformalni izvajalci. Formalni izvajalec vedno izvede isti ukaz na enak način. Neformalni izvajalec lahko ukaz izvede na različne načine.

Načini delovanja izvajalca. Za večino izvajalcev so na voljo neposredni nadzor in načini programskega nadzora. V prvem primeru izvajalec čaka na ukaze osebe in takoj izvede vsak prejeti ukaz. V drugem primeru izvajalec najprej dobi celotno zaporedje ukazov (program), nato pa vse te ukaze samodejno izvede. Številni izvajalci delujejo samo v enem od imenovanih načinov.

Poglejmo primere izvajalcev.

Primer 5. Izvajalec Želva se premika po računalniškem zaslonu in pušča sled v obliki črte.

Sistem ukazov Turtle je sestavljen iz naslednjih ukazov:

1. Naprej n (kjer je n celo število) - povzroči, da se želva premakne za n korakov v smeri gibanja - v smeri, v katero sta obrnjena njena glava in telo;
2. Desno m (kjer je m celo število) - povzroči spremembo smeri gibanja želve za t stopinj v smeri urnega kazalca.
Zapis Ponovi k [<Команда1> <Команда2> ... <Командаn>] pomeni, da se bo zaporedje ukazov v oklepajih ponovilo k-krat.

Pomislite, katera številka se bo pojavila na zaslonu, ko bo želva dokončala naslednji algoritem.
Ponovi 12 [desno 45 naprej 20 desno 45]

Primer 6. Sistem izvršilnih ukazov Računalnik je sestavljen iz dveh ukazov, ki imata dodeljene številke:

1 - odštej 1
2 - pomnožimo s 3

Pomnoži s 3
odštej 1
pomnoži s 3
odštej 1
pomnoži s 3

S tem algoritmom bo število 1 pretvorjeno v 15:

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

Primer 7. Performer Robot deluje na karirastem polju, med sosednjimi celicami so lahko zidovi. Robot se premika po celicah polja in lahko izvaja naslednje ukaze, ki so jim dodeljene številke:

1 - gor
2 - navzdol
3 - desno
4 - levo

Pri izvajanju vsakega takega ukaza se robot premakne v sosednjo celico v navedeni smeri. Če je v tej smeri med celicami zid, je robot uničen.

Kaj se bo zgodilo z robotom, če izvede zaporedje ukazov 32323 (tukaj številke označujejo številke ukazov), ki se začne premikati iz celice A? Katero zaporedje ukazov mora izvesti robot, da se premakne iz celice A v celico B, ne da bi se zrušil, ko trči ob stene?

Pri razvoju algoritma:

1) identificirani so predmeti, ki se pojavljajo v problemu, ugotovijo se lastnosti predmetov, razmerja med predmeti in možna dejanja s predmeti;
2) določeni so začetni podatki in zahtevani rezultat;
3) določeno je zaporedje dejanj izvajalca, ki zagotavlja prehod od začetnih podatkov do rezultata;
4) zaporedje dejanj se zabeleži z ukazi, ki so vključeni v ukazni sistem izvajalca.

Lahko rečemo, da je algoritem model aktivnosti izvajalca algoritma.

2.1.3. Lastnosti algoritma

Diskretna lastnina pomeni, da je pot do rešitve problema razdeljena na ločene korake (akcije). Vsako dejanje ima ustrezno navodilo (ukaz). Šele po izvedbi enega ukaza lahko izvajalec začne izvajati naslednji ukaz.

Lastnost razumljivosti pomeni, da je algoritem sestavljen samo iz ukazov, ki so vključeni v sistem ukazov izvajalca, torej iz takih ukazov, ki jih izvajalec lahko zazna in po katerih lahko izvaja zahtevana dejanja.

Lastnost gotovosti pomeni, da algoritem ne vsebuje ukazov, katerih pomen si izvajalec lahko razlaga dvoumno; Nesprejemljive so situacije, ko izvajalcu po izvedbi naslednjega ukaza ni jasno, kateri ukaz naj izvrši naslednji. Zahvaljujoč temu je rezultat algoritma enolično določen z nizom začetnih podatkov: če se algoritem večkrat uporabi za isti niz začetnih podatkov, potem rezultat vedno proizvede enak rezultat.

Lastnost uspešnosti pomeni, da mora algoritem zagotoviti rezultat po končnem, po možnosti zelo velikem številu korakov. V tem primeru se za rezultat ne šteje le odgovor, določen z izjavo o problemu, temveč tudi sklep o nezmožnosti nadaljnjega reševanja tega problema iz katerega koli razloga.

Lastnost množičnega značaja pomeni, da mora algoritem zagotavljati možnost njegove uporabe za reševanje katerega koli problema iz določenega razreda problemov. Na primer, algoritem za iskanje korenin kvadratne enačbe bi moral biti uporaben za katero koli kvadratno enačbo, algoritem za prečkanje ulice bi moral biti uporaben kjer koli na ulici, algoritem za pripravo zdravila bi moral biti uporaben za pripravo katere koli količine zdravila, itd.

Primer 8. Oglejmo si eno od metod za iskanje vseh praštevil, ki ne presegajo nekega naravnega števila n. Ta metoda se imenuje "Eratostenovo sito" po starogrškem znanstveniku Eratostenu (3. stoletje pr. n. št.), ki jo je predlagal.

Če želite najti vsa praštevila, ki niso večja od danega števila n, po Eratostenovi metodi, morate izvesti naslednje korake:

1) zapiši zaporedoma vsa naravna števila od 2 do n (2, 3, 4, ..., n);
2) okvir 2 - prvo praštevilo;
3) s seznama prečrtajte vsa števila, ki so deljiva z zadnjim najdenim praštevilom;
4) poiščite prvo neoznačeno število (označena števila so prečrtana števila ali števila, obdana z okvirjem) in ga obdajte v okvir - to bo drugo praštevilo;
5) ponavljajte koraka 3 in 4, dokler ne ostane nobena neoznačena številka.

Z animacijo »Eratostenovo sito« (180279), objavljeno v Enotni zbirki digitalnih izobraževalnih virov, lahko dobite bolj vizualno predstavo o metodi iskanja praštevil.

Obravnavano zaporedje dejanj je algoritem, saj izpolnjuje naslednje lastnosti:

diskretnost- postopek iskanja praštevil je razdeljen na korake;
razumljivost- vsak ukaz je razumljiv učencu 8. razreda, ki izvaja ta algoritem;
gotovost- vsak ukaz izvajalec razlaga in izvaja nedvoumno; obstajajo navodila o vrstnem redu izvajanja ukazov;
učinkovitost- po določenem številu korakov je dosežen rezultat;
množični značaj- zaporedje dejanj velja za poljubno naravno število n.

Obravnavane lastnosti algoritma nam omogočajo natančnejšo definicijo algoritma.

2.1.4. Možnost avtomatizacije človekovih dejavnosti

Razvoj algoritma je običajno delovno intenzivna naloga, ki od osebe zahteva globoko znanje, iznajdljivost in veliko časa.

Reševanje problema z že pripravljenim algoritmom od izvajalca zahteva le dosledno upoštevanje danih navodil.

Primer 9. Iz kupa, ki vsebuje poljubno število predmetov, večje od treh, dva igralca izmenično vzameta enega ali dva predmeta. Zmagovalec je tisti, ki lahko na naslednji potezi pobere vse preostale predmete.

Oglejmo si algoritem, po katerem bo prvi igralec zagotovo zagotovil zmago.

1. Če je število predmetov v kupu večkratnik 3, popustite nasprotniku, drugače začnite igro tako, da vzamete 1 ali 2 predmeta, tako da je število preostalih predmetov večkratnik 3.
2. Z naslednjo potezo vsakič dodajte število predmetov, ki jih je vzel nasprotnik, na 3 (število preostalih predmetov mora biti večkratnik 3).

1) postopek reševanja problema je predstavljen kot zaporedje preprostih operacij;
2) ustvarjen je stroj (avtomatska naprava), ki je sposoben izvajati te operacije v zaporedju, določenem v algoritmu;
3) oseba je osvobojena rutinskih dejavnosti, izvedba algoritma je zaupana avtomatski napravi.

NAJPOMEMBNEJŠE

Izvršitelj- nek predmet (oseba, žival, tehnična naprava), ki je sposoben izvajati določen niz ukazov.

Formalni izvajalec vedno izvede isti ukaz na enak način. Za vsakega formalnega izvajalca lahko določite: obseg nalog, ki jih je treba rešiti, okolje, sistem ukazov in način delovanja.

Algoritem- opis zaporedja dejanj, namenjenih določenemu izvajalcu, ki vodijo od začetnih podatkov do zahtevanega rezultata, ki ima lastnosti diskretnosti, razumljivosti, gotovosti, učinkovitosti in množičnosti.

Igralska sposobnost izvajalca formalno omogoča avtomatizacijo človeških dejavnosti.

Vprašanja in naloge

1. Preberite predstavitveno gradivo za odstavek v elektronska prijava k učbeniku. Ali predstavitev dopolnjuje informacije v besedilu odstavka? Katere diapozitive bi lahko dodali svoji predstavitvi?

2. Kaj imenujemo algoritem?

3. Izberite sinonime za besedo »recept«.

4. Navedite primere algoritmov, ki ste se jih učili v šoli.

5. Kdo je lahko izvajalec algoritma?

6. Navedite primer formalnega izvajalca. Navedite primer, ko oseba nastopa kot uradni izvajalec.

7. Kaj določa obseg nalog, ki jih izvaja »računalniški« izvajalec?

8. Urejevalnik besedil v vašem računalniku obravnavajte kot izvajalca. Opišite obseg nalog, ki jih rešuje ta izvajalec in njegovo okolje.

9. Kaj je tim, sistem izvajalskih ukazov?

10. Katere ukaze naj robot izvaja za naslednje funkcije:

a) blagajnik v trgovini;
b) hišnik;
c) varnostnik?

11. Naštejte glavne lastnosti algoritma.

12. Do česa lahko privede odsotnost katerekoli lastnosti v algoritmu? Navedite primere.

13. Kakšen je pomen zmožnosti formalnega izvajanja algoritma?

14. Zaporedje številk je sestavljeno po naslednjem algoritmu: prvi dve številki zaporedja sta enaki 1; Vsako naslednje število v zaporedju je enako vsoti prejšnjih dveh števil. Zapišite prvih 10 členov tega zaporedja. Ugotovite, kako se imenuje to zaporedje.

15. Določen algoritem pridobi novo verigo iz enega niza znakov, kot sledi. Najprej se napiše izvirna veriga znakov, za njo se napiše prvotna veriga znakov v obratnem vrstnem redu, nato se napiše črka, ki sledi v ruski abecedi za črko, ki je bila v prvotni verigi na zadnjem mestu. Če je črka "I" na zadnjem mestu v prvotni verigi, potem je črka "A" zapisana kot naslednja črka. Nastala veriga je rezultat algoritma. Na primer, če je bila prvotna veriga znakov »HIŠA«, bo rezultat algoritma veriga »DOMMODN«. Podan je niz znakov »COM«. Koliko črk "O" bo v verigi znakov, ki jih boste dobili, če algoritem uporabite za to verigo in nato ponovno uporabite algoritem za rezultat njegovega dela?

16. Na internetu poišči animacijo korakov Eratostenovega algoritma. Uporabite Eratostenov algoritem, da poiščete vsa praštevila, ki ne presegajo 50.

17. Kakšen bo rezultat Turtle-jeve izvedbe (glej primer 5) algoritma?

18. Zapišite algoritem za izvajalca kalkulatorja (glej primer 6), ki vsebuje največ 5 ukazov:

a) prejemanje od števila 3 števila 16;
b) prejemanje od števila 1 števila 25.

19. Sistem izvajalskih ukazov Konstruktor je sestavljen iz dveh ukazov, ki imata dodeljene številke:

1 - dodeli 2
2 - delite z 2

Po prvem od njih se številki na desni doda 2, po drugem pa se število deli z 2. Kako se pretvori število 8, če izvajalec izvede algoritem 22212? V sistemu ukazov tega izvajalca ustvarite algoritem, po katerem se bo število 1 pretvorilo v število 16 (algoritem naj vsebuje največ 5 ukazov).

20. V kateri celici naj se nahaja izvajalec robota (primer 7), da se vanjo vrne po izvedbi algoritma 3241?

Brezplačna programska oprema:

Sistem KuMir - Komplet izobraževalnih svetov (prenesite arhiv programa s spletne strani) ali obiščite stran KuMir ((http://www.niisi.ru/kumir/)

Začasno ustavite AdBlock na tem spletnem mestu.

V tej lekciji si bomo ogledali nekaj teoretičnih konceptov, ki formalizirajo koncept programiranja. Hkrati bomo natančneje oblikovali glavno nalogo vašega treninga.

Za začetek predlagam, da se malo poigrate z naslednjo otroško igračo. Izpolnite prvih pet nalog, pojdite nazaj in nadaljujte z branjem lekcije.

Slika 1 Posnetek zaslona igralnega polja na code.org

Upam, da se ti je vse izšlo. Zdaj bomo s tem primerom opisali nekaj osnovnih konceptov:

izvršitelj;
sistem izvajalskih ukazov;
algoritem.

V igrači upravljamo rdečo ptico. Cilj vsake stopnje je pripeljati ptico do prašiča. Ptica lahko izvaja določene ukaze, na primer: premakni se naprej, zavij levo, zavij desno itd.

Oseba, stroj ali naprava, ki lahko izvaja nekatere ukaze, se imenuje izvršitelj. V tej igrači je očitno izvajalec ptica. Nabor ukazov, ki jih izvajalec razume in jih lahko izvede, se imenuje sistem izvajalskih ukazov.

Zaporedje ukazov, ki jih mora izvajalec izvesti za rešitev problema, se imenuje algoritem.

Osredotočiti se je treba na več točk.

Izvajalec lahko izvaja le tiste ukaze, ki so vključeni v njegov ukazni sistem.

To na primer pomeni, da izvajalcu ptic ne morete napisati: "Pojdi k pujsu!" Lahko zapišeš bolj natančno, pa se ne bo zgodilo nič, ker... izvajalec takšnih ukazov ne pozna.

Razpoložljive ukaze lahko zapišete v poljubnem vrstnem redu, ki se vam zdi pravilen. Vaša naloga kot programerja je razdeliti veliko kompleksno nalogo na majhne posamezne korake, od katerih bo vsak razumljiv izvajalcu. Ponovno je na delu načelo »deli in vladaj«.

Izvajalec naredi točno to, kar mu algoritem naroči.

Izvajalec ptic je zelo zaupljiv. Ne dvomi o tem, kaj pišete v programu. Če na primer pozabite obrniti ptico, se bo zaletela v steno. Zato morate vse spremljati sami.

Vaši prihodnji programi pogosto ne bodo delovali, kot ste nameravali. Napake se dogajajo vsem. Tukaj je pomembno razumeti, da ni računalnik neumen, ampak ste naredili napako v algoritmu. Ne bodite kot slabi programerji, ki jim je vedno za vse kriv program.

Zdaj pa preidimo od ilustrativnega primera k računalniški realnosti. Programe pišemo za računalnik, kar pomeni, da je računalnik v našem primeru izvajalec. Sistem ukazov so standardne funkcije in konstrukti jezika C.

Kaj je glavni cilj vašega poučevanja osnov programiranja? Obvladajte veščino algoritemskega razmišljanja. To pomeni, da se naučite zapisati rešitev različnih problemov v obliki algoritma za določenega izvajalca (v našem primeru računalnik).

Torej, če povzamem:

Računalniški program– algoritem za reševanje problema, napisan v programskem jeziku.

Algoritem je natančen opis vrstnega reda dejanj, ki jih mora izvajalec izvesti, da reši problem.

Izvajalec je oseba ali neka naprava, ki lahko razume in izvede določen niz ukazov.

Beseda "algoritem" izhaja iz imena arabskega matematika al-Hvarizmija iz 9. stoletja, ki je oblikoval pravila za izvajanje aritmetičnih operacij.

Algoritem– natančno in razumljivo navodilo izvajalcu za izvedbo končnega zaporedja ukazov, ki vodijo od začetnih podatkov do začetnega rezultata.

Primeri: dnevna rutina, vrstni red kuhanja, navodila itd.)

Izvajalec algoritma– to je tisti, ki izvaja algoritem (oseba, žival, stroj, računalnik).

Sistem ukazov izvajalca- to je celoten niz ukazov, ki jih izvajalec zna izvesti (razume). Algoritem je mogoče zgraditi le iz ukazov, ki so vključeni v sistem izvajalskih ukazov.

Na primer, izvajalec Robot lahko izvaja ukaze naprej, nazaj, levo, desno, slikaj. Premika se po celičnem polju, ki ga omejuje stena in vsebuje stene. Robot ne more skozi zid.

Lastnosti algoritma:

1.Učinkovitost (udov)– sposobnost pridobitve rezultata iz začetnih podatkov v končnem številu korakov. (Na primer, ko izvajamo algoritem za seštevanje 2 števil, bi morali dobiti vsoto).

2.Množični značaj– sposobnost uporabe algoritma za veliko število različnih izvornih podatkov. (Na primer, seštejete lahko poljubni 2 številki, če poznate algoritem seštevanja.)

3.determinizem(gotovost, natančnost) – vsak ukaz mora enolično določati dejanje izvajalca.

4.Razumljivost– ukaz mora biti napisan v računalniku razumljivem jeziku.

5.Diskretnost– razdelitev algoritma na ločene ukaze.

Načini pisanja algoritma:

1) V naravnem jeziku – zapis v obliki ločenih ukazov v človeku razumljivem jeziku.

2) Grafični – v jeziku diagramov poteka z uporabo geometrijskih oblik (oval, pravokotnik, paralelogram, romb).

3) V algoritemskem jeziku - jezik za pisanje algoritmov za poučevanje programiranja. Ukazi so napisani v ruščini.

4) V programskem jeziku - program. Programski jeziki: Basic, Pascal, C, Visual Basic.

B7.Osnovne algoritemske strukture: sledenje, razvejanje, zanka; slika na blokovnih diagramih. Razčlenitev nalog na podnaloge. Pomožni algoritmi.

Algoritemske zasnove. Znotraj algoritmov lahko ločimo skupine korakov, ki se razlikujejo po notranji zgradbi – algoritemske konstrukcije.

Osnovne algoritemske konstrukcije so linearno zaporedje korakov (ali sledenje), razvejanje in zankanje.

Pokliče se algoritem, v katerem se ukazi izvajajo zaporedno drug za drugim linearni algoritem.

Tako izgleda linearni algoritem v jeziku blokovnih diagramov:

Primer: algoritem za vklop računalnika:

Vklopite računalnik (pritisnite gumb za vklop prenapetostna zaščita).
Vklopite monitor in tiskalnik.
Kliknite Gumb za prižig na sistemska enota.
Počakajte na nalaganje operacijski sistem in videz namizja.
Pojdi v službo.

V tem algoritmu je treba vsa dejanja izvajati zaporedno eno za drugim: ne morete začeti delati, če napajanje ali monitor nista vklopljena.

V algoritemsko strukturo " razvejanje» vključeno stanje, odvisno od resničnosti pogoja, se izvede eno ali drugo zaporedje ukazov (nizov).

Pogoj je izjava, ki je lahko resnična ali napačna. V pogoju sta dve števili, dva niza, dve spremenljivki ali nizovni izrazi primerjani med seboj z uporabo primerjalnih operatorjev (>,<, =, >=, <=).

Zapis v algoritemskem jeziku: IfCondition Then Series 1 (If Pogoj res, potem res 1. epizoda, Če Pogoj false, potem se nič ne izvede). Primer: Če je danes nedelja, potem ni treba iti v šolo. Polna oblika razvejanja

V algoritemskih strukturah cikel vključuje vrsto ukazov, ki se izvajajo večkrat. To zaporedje ukazov se imenuje telo zanke.

Obstajata dve vrsti cikličnih algoritemskih struktur:

nasprotne zanke, v kateri se telo zanke izvede določeno število krat;
pogojne zanke, v katerem se telo zanke izvaja, dokler je izpolnjen pogoj.

Zanka s števcem– uporablja se, ko je vnaprej znano, koliko ponovitev telesa zanke je treba izvesti.

Algoritem in njegove lastnosti.

Algoritem- jasno in natančno navodilo izvajalcu za izvedbo končnega zaporedja ukazov, ki vodijo od začetnih podatkov do želenega rezultata.

Izvajalec algoritma- to je objekt ali subjekt, za katerega je algoritem zasnovan za nadzor.

Izvajalčev ukazni sistem (SCS) je celoten nabor ukazov, ki jih lahko izvajalec izvede.

Lastnosti algoritma: razumljivost, natančnost, končnost.

Jasnost: algoritem je sestavljen le iz ukazov, vključenih v izvajalčev SKI.

Natančnost: Vsak ukaz krmilnega algoritma določa nedvoumno dejanje izvajalca.

Dokončnost (ali zmogljivost): izvajanje algoritma mora pripeljati do rezultata v končnem številu korakov.

Izvajalčevo okolje: okolje, v katerem izvajalec deluje.

Za nekatere vedno velja določeno zaporedje dejanj izvajalca izvorni podatki. Na primer, za pripravo jedi po kulinaričnem receptu potrebujete ustrezne izdelke (podatke). Za rešitev matematičnega problema (reševanje kvadratne enačbe) potrebujete začetne numerične podatke (koeficiente enačbe).

Celoten nabor podatkov: potreben in zadosten nabor podatkov za rešitev naloge (pridobitev želenega rezultata).

Metode za pisanje algoritmov.

Najpogostejše metode so: grafični, verbalno in v obliki računalniški programi.

Grafična metoda vključuje uporabo določenih grafičnih simbolov – blokov.

Ime bloka	Oznaka bloka	Vsebina
Proces		Obdelava podatkov
Odločanje		Logični blok za preverjanje resničnosti ali napačnosti določenega pogoja
Prenos podatkov		Vnos ali izhod informacij
Začni, nehaj		Začetek ali konec programa
Sprememba		Organizacija cikličnega procesa - glava cikla

Zbirka blokov tvori t.i diagram poteka algoritma.

Verbalni zapis algoritmi so osredotočeni predvsem na človeka izvajalca in omogočajo različno zapisovanje navodil, vendar mora biti zapis precej natančen.

Pri pisanju algoritmov v obliki programi računalniki uporabljajo programske jezike - sisteme za kodiranje navodil in pravil za njihovo uporabo. Za pisanje algoritmov v obliki programov je značilna visoka stopnja formalizacije.

Algoritmi za delo s količinami. Osnovne algoritemske strukture.

Količina je en sam informacijski objekt, ki ima ime, vrednost in vrsto.

Izvajalec algoritmov za delo s količinami je lahko oseba ali posebna tehnična naprava, na primer računalnik. Tak izvajalec mora imeti spomin za shranjevanje količin.

Količine so lahko konstantne ali spremenljive.

Konstantna vrednost (konstanta) med izvajanjem algoritma ne spremeni svoje vrednosti. Konstanto lahko označimo z lastno vrednostjo (števili 10, 3,5) ali s simboličnim imenom (število ).

Spremenljiva vrednost lahko spremeni vrednost med izvajanjem algoritma. Spremenljivka je vedno označena s simboličnim imenom (X, A, R5 itd.).

Vrsta količine definira nabor vrednosti, ki jih lahko sprejme vrednost, in nabor dejanj, ki jih je mogoče izvesti s to vrednostjo. Osnovne vrste količin: cele, realne, simbolne, logične.

Izraz- zapis, ki določa zaporedje dejanj na količine. Izraz lahko vsebuje konstante, spremenljivke, operacijske znake in funkcije. primer:

A + B; 2*X-Y; K + L - sin(X)

Ukaz za dodelitev je ukaz izvajalca, ki povzroči, da spremenljivka prejme novo vrednost. Oblika ukaza:

ime spremenljivke>:=izraz>

Ukaz za dodelitev se izvede v naslednjem vrstnem redu: najprej se izračuna, nato se dobljena vrednost dodeli spremenljivki.

Primer. Naj ima spremenljivka A vrednost 6. Kakšno vrednost bo dobila spremenljivka A po izvedbi ukaza: A:= 2 * A - 1?
rešitev. Izračun izraza 2*A - 1 z A=6 bo dal število 11. To pomeni, da bo nova vrednost spremenljivke A enaka 11.

V nadaljevanju se bo domnevalo, da izvajalec algoritmov za delo s količinami je računalnik. Vsak algoritem je mogoče zgraditi iz ukazov naloge, vnos, izhod, razvejanje in cikel.

Ukaz za vnos- ukaz, s katerim se vrednosti spremenljivk nastavijo prek vnosnih naprav (na primer tipkovnice).

primer: vnos A - vnos vrednosti spremenljivke A s tipkovnice računalnika.

Izhodni ukaz: ukaz, ki prikaže vrednost količine na računalniški izhodni napravi (kot je monitor).

primer: sklep X - vrednost spremenljivke X je prikazana na zaslonu.

Poveljstvo veje- razdeli algoritem na dve poti, odvisno od nekega pogoja; nato pa gre izvajanje algoritma na splošno nadaljevanje. Razvejanje je lahko popolno ali nepopolno. Opis razvejanja v blokovnih diagramih in v algoritemskem jeziku:

Tukaj niz pomeni enega ali več zaporednih ukazov; kv - konec razvejanja.

Ukaz zanke zagotavlja ponavljajoče se izvajanje zaporedja ukazov (telo zanke) na podlagi nekega pogoja.

Zanka s predpogojem- zanka, katere izvedba se ponavlja, dokler ni pogoj zanke resničen:

Zanka s parametrom- ponavljajoče se izvajanje telesa zanke, medtem ko celoštevilski parameter teče skozi nabor vseh vrednosti od začetne (In) do končne (Ik):

Primer. Podana sta dva preprosta ulomka. Ustvarite algoritem za pridobitev ulomka, ki je rezultat njihovega deljenja.
rešitev. V algebraični obliki je rešitev problema videti takole:
a/b: c/d = a*d/b*c = m/n
Začetni podatki so štiri cele količine: a, b, c, d. Rezultat sta dve celi števili m in n.

alg deljenje ulomkov
nedotaknjen a, b, c, d, m, n
začetek vnosa a, b, c, d
m:=a*d
n:=b*c
izpis "Števec=", m
izpis "Denominator=", n
koi

Upoštevajte, da mora biti za izhod besedilo (poljubno zaporedje znakov) v ukazu napisano v narekovajih sklep.

Efimova O., Morozov V., Ugrinovich N. Tečaj računalniške tehnologije z osnovami računalništva. Vadnica za srednjo šolo. - M .: LLC "Založba AST"; ABF, 2000
Problemska knjiga-delavnica iz računalništva. V 2 zvezkih / ur. I. Semakina, E. Henner. - M.: Laboratorij za osnovno znanje, 2001.
Ugrinovich N. Računalništvo in Informacijska tehnologija. 10-11 razredi - M .: Laboratorij za osnovno znanje, JSC "Moscow Textbooks", 2001

Naloge in testi na temo "Algoritmi in izvajalci"

Artist Management risar - Algoritmi 6. razred
Lekcije: 4 Naloge: 9 Testi: 1
2 nalogi: 9 testov: 1

Dragi študent!

Poznavanje teme "Algoritmi in izvajalci" je potrebno predvsem za nadaljnji študij programiranja. Za osnovo študija programiranja je bil izbran programski jezik QBasic. Zamisel o vključitvi Visual Basica ali katerega koli drugega objektno usmerjenega programskega jezika v naš tečaj smo opustili, saj ta pristop še ni bil široko uporabljen v večini srednjih šol v Ruski federaciji. Poleg tega objektno orientirano programiranje temelji na principih klasičnega Dos programiranja.

Naš tečaj je zasnovan za splošno izobraževalni program. Ko se pripravljate na sprejemne izpite iz informacijske tehnologije na univerze, se morate seznaniti s posebnostmi študija programiranja na določeni univerzi. V nekaterih primerih je potrebna poglobljena študija številnih tem, na primer "Matrike". Na to morate biti pozorni, ko preučujete literaturo o programiranju; morda bi morali uporabiti metodološka priporočila o pripravah na izpite, ki so trenutno objavljeni na večini visokošolskih zavodov.

Na koncu ugotavljamo, da je doseganje "aerobatike" v programiranju mogoče le s stalno prakso in reševanjem specifičnih uporabnih problemov.

Priljubljeno v kategoriji: