Algoritm ja selle omadused.

Algoritm- selge ja täpne juhend sooritajale, et täita lõplik käskude jada, mis viib algandmetest soovitud tulemuseni.

Algoritmi täitja- see on objekt või subjekt, mille juhtimiseks algoritm on loodud.

Esitaja käsusüsteem (SCS) on kogu käskude komplekt, mida esineja saab täita.

Algoritmi omadused: arusaadavus, täpsus, lõplikkus.

Selgus: Algoritm koosneb ainult täitja SKI-s sisalduvatest käskudest.

Täpsus: Iga juhtimisalgoritmi käsk määrab täitja ühemõttelise tegevuse.

Viimistlus (või jõudlus): Algoritmi täitmine peab viima tulemuseni piiratud arvu sammudega.

Esineja keskkond: keskkond, milles esineja tegutseb.

Mõne puhul kehtib alati esineja teatud toimingute jada lähteandmed. Näiteks kulinaarse retsepti järgi roa valmistamiseks on vaja vastavaid tooteid (andmeid). Matemaatilise ülesande lahendamiseks (ruutvõrrandi lahendamiseks) on vaja algseid arvandmeid (võrrandi koefitsiente).

Täielik andmekogum:ülesande lahendamiseks (soovitud tulemuse saamiseks) vajalik ja piisav andmekogum.

Algoritmide kirjutamise meetodid.

Kõige tavalisemad meetodid on: graafiline, verbaalne ja kujul arvutiprogrammid.

Graafiline meetod hõlmab teatud graafiliste sümbolite – plokkide – kasutamist.

Plokkide kogu moodustab nn algoritmi vooskeem.

Verbaalne salvestamine algoritmid on keskendunud eelkõige inimesinejale ja võimaldavad käskude erinevat salvestamist, kuid salvestamine peab olema üsna täpne.

Algoritmide vormis kirjutamisel programmid arvutid kasutavad programmeerimiskeeli - juhiste kodeerimise süsteeme ja nende kasutamise reegleid. Algoritmide kirjutamist programmide kujul iseloomustab kõrge vormistatus.

Algoritmid kogustega töötamiseks. Algoritmilised põhistruktuurid.

Kogus on üksik teabeobjekt, millel on nimi, väärtus ja tüüp.

Kogustega töötamise algoritmide teostajaks võib olla inimene või spetsiaalne tehniline seade, näiteks arvuti. Sellisel esinejal peab olema mälu koguste hoidmiseks.

Kogused võivad olla püsivad või muutuvad.

Konstantne väärtus (konstantne) ei muuda selle väärtust algoritmi täitmise ajal. Konstanti saab tähistada tema enda väärtusega (numbrid 10, 3.5) või sümboolse nimega (arv ).

Muutuv väärtus saab väärtust algoritmi täitmise ajal muuta. Muutujat tähistatakse alati sümboolse nimega (X, A, R5 jne).

Koguse tüüp määrab väärtuste komplekti, mida väärtus võib võtta, ja tegevuste komplekti, mida saab selle väärtusega teha. Suuruste põhitüübid: täisarv, reaalne, sümboolne, loogiline.

Väljendus- kirje, mis määrab suurustega seotud toimingute jada. Avaldis võib sisaldada konstante, muutujaid, tehtemärke ja funktsioone. Näide:

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

Määramiskäsk on täitja käsk, mille tulemusena saab muutuja uue väärtuse. Käsuvorming:

muutuja nimi>:=avaldis>

Omistamiskäsk täidetakse järgmises järjekorras: kõigepealt arvutatakse see välja, seejärel omistatakse muutujale saadud väärtus.

Näide. Olgu muutuja A väärtus 6. Millise väärtuse saab muutuja A pärast käsu täitmist: A:= 2 * A - 1?
Lahendus. Avaldise 2*A - 1 arvutamisel A=6 saadakse arv 11. See tähendab, et muutuja A uus väärtus võrdub 11-ga.

Järgnevalt eeldatakse, et suurustega töötamise algoritmide teostajaks on arvuti. Käskudest saab ehitada mis tahes algoritmi ülesandeid, sisend, väljund, hargnemine Ja tsükkel.

Sisestage käsk- käsk, mille abil määratakse muutujate väärtused sisendseadmete (näiteks klaviatuuri) kaudu.

Näide: sisend A - muutuja A väärtuse sisestamine arvuti klaviatuurilt.

Väljundkäsk: käsk, mis kuvab arvuti väljundseadmel (nt monitoril) suuruse väärtuse.

Näide: järeldus X - ekraanile kuvatakse muutuja X väärtus.

Haru käsk- jagab algoritmi olenevalt mingist tingimusest kaheks teeks; siis läheb algoritmi täitmine üldisele jätkamisele. Hargnemine võib olla täielik või mittetäielik. Hargnemise kirjeldus plokkskeemides ja algoritmilises keeles:

Siin tähendab seeria ühte või mitut järjestikust käsku; kv - hargnemise lõpp.

Loop käsk tagab mõne tingimuse alusel käskude jada (silmuse keha) korduva täitmise.

Silmus eeltingimusega- tsükkel, mille täitmist korratakse, kuni tsükli tingimus on tõene:

Silmus parameetriga- tsükli keha korduv täitmine, kui täisarvuline parameeter jookseb läbi kõigi väärtuste komplekti algsest (In) kuni lõpliku (Ik):

Näide. On antud kaks lihtmurdu. Looge nende jagamise tulemuseks oleva murdosa saamiseks algoritm.
Lahendus. Algebralises vormis näeb ülesande lahendus välja järgmine:
a/b: c/d = a*d/b*c = m/n
Algandmed on neli täisarvu suurust: a, b, c, d. Tulemuseks on kaks täisarvu m ja n.

alg murdude jagamine
terved a, b, c, d, m, n
käivitage sisend a, b, c, d
m:=a*d
n:=b*c
väljund "Numerator=", m
väljund "Denominator=", n
koi

Pange tähele, et teksti (mis tahes märgijada) väljastamiseks tuleb see käsus kirjutada jutumärkidesse järeldus.

1. Efimova O., Morozov V., Ugrinovich N. Arvutitehnoloogia kursus arvutiteaduse alustega. Õpik gümnaasiumile. - M.: LLC "Kirjastus AST"; ABF, 2000
2. Probleemraamat-töötuba arvutiteaduses. 2 köites/Toim. I. Semakina, E. Henner. - M.: Algteadmiste labor, 2001.
3. Ugrinovich N. Arvutiteadus ja infotehnoloogiad. 10-11 klass - M.: Algteadmiste labor, JSC "Moskva õpikud", 2001

Ülesanded ja testid teemal "Algoritmid ja täitjad"

• Kunstniku juhtimise koostaja - Algoritmid 6. klass

  Tunnid: 4 Ülesanded: 9 Kontrolltööd: 1

• 2 ülesannet: 9 testi: 1

Kallis üliõpilane!

Teema "Algoritmid ja täitjad" tundmine on vajalik eelkõige programmeerimise edasiseks õppimiseks. Programmeerimise õppimise aluseks valiti programmeerimiskeel QBasic. Loobusime mõttest lisada oma kursusesse Visual Basic või mõni muu objektorienteeritud programmeerimiskeel, kuna seda lähenemist pole enamikus Vene Föderatsiooni keskkoolides veel laialdaselt kasutatud. Lisaks sellele põhineb objektorienteeritud programmeerimine klassikalise Dos programmeerimise põhimõtetel.

Meie kursus on mõeldud üldharidusprogrammi jaoks. Ülikoolide infotehnoloogia sisseastumiseksamiteks valmistudes tuleb end kurssi viia antud ülikoolis programmeerimise õppimise spetsiifikaga. Mõnel juhul on vajalik mitmete teemade süvendatud uurimine, näiteks "Massiivid". Programmeerimisalast kirjandust uurides tuleks sellele tähelepanu pöörata, võib-olla tuleks kasutada eksamiteks valmistumise metoodilisi soovitusi, mis praegu avaldatakse enamikus kõrgkoolides.

Kokkuvõtteks märgime, et programmeerimises on „aerobaatika” saavutamine võimalik ainult pideva harjutamise ja konkreetsete rakendusprobleemide lahendamisega.

7.1. Mis on algoritm?

Nimi "algoritm" pärineb Kesk-Aasia matemaatiku al-Khwarizmi nime ladinakeelsest vormist - Algorithmi. Algoritm on arvutiteaduse ja matemaatika üks põhimõisteid.

7.2. Mis on "algoritmi täitja"?

Esinejat iseloomustavad:

• • kolmapäev;
  • elementaarsed toimingud;
  • käsusüsteem;
  • keeldumised.

kolmapäeval(või keskkond) on esineja "elupaik". Näiteks kooliõpiku esineja Robot jaoks on keskkond lõpmatu rakuväli. Seinad ja värvitud rakud on samuti osa keskkonnast. Ja nende asukoht ja Roboti asend määravad konkreetse keskkonnaseisundit.

Käsusüsteem. Iga täitja saab käske täita ainult kindlast rangelt määratud loendist – täitjakäskude süsteemist. Iga käsu jaoks tuleb täpsustada kohaldamistingimused(millistes keskkonnaseisundites saab käsku täita) ja kirjeldada käsu täitmise tulemused. Näiteks töökäsku "üles" saab täita, kui töö kohal pole seina. Selle tulemuseks on roboti nihkumine ühe raku võrra ülespoole.

Pärast käsu kutsumist sooritab esitaja vastava elementaarne tegevus .

Ebaõnnestumised täituri vead tekivad, kui käsk kutsutakse välja keskkonnaseisundis, mis on selle jaoks vastuvõetamatu.

Arvutiteaduses on algoritmide universaalne täitja arvuti.

7.3. Millised omadused on algoritmidel?
Algoritmide peamised omadused on järgmised:

Arusaadavus esineja jaoks - st. Algoritmi täitja peab teadma, kuidas seda täita.

Diskreetsus(katkestus, eraldatus) – s.t. Algoritm peab kujutama probleemi lahendamise protsessi lihtsate (või eelnevalt määratletud) sammude (etappide) järjestikuse täitmisena.

Kindlus- st. Algoritmi iga reegel peab olema selge, üheselt mõistetav ega jätma ruumi meelevaldsusele. Tänu sellele omadusele on algoritmi täitmine oma olemuselt mehaaniline ega vaja täiendavaid juhiseid ega teavet lahendatava probleemi kohta.

Tõhusus (või jäseme). See omadus seisneb selles, et algoritm peab viima probleemi lahendamiseni piiratud arvu sammudega.

Massi iseloom. See tähendab, et ülesande lahendamise algoritm töötatakse välja üldkujul, s.o. see peaks olema rakendatav teatud probleemide klassi jaoks, mis erinevad ainult algandmete poolest. Sel juhul saab lähteandmed valida teatud piirkonnast, mida nimetatakse algoritmi rakendusalaks.

Algoritmi kontseptsioon

Algoritmilised keeled

Algoritmid. Algoritmiseerimine.

Algoritmi mõiste on arvutiteaduses sama oluline kui teabe mõiste. Sellepärast on oluline seda mõista.

Nimi "algoritm" tuleb Kesk-Aasia suurima matemaatiku nime ladinakeelsest vormist Muhammad ibn Musa al-Khwarizmi(Alhorithmi), kes elas aastatel 783-850. Oma raamatus “India loendamine” kirjeldas ta araabia numbreid kasutades naturaalarvude kirjutamise reegleid ja nende “veerus” kasutamise reegleid, mis on nüüd tuttavad igale koolilapsele. 12. sajandil tõlgiti see raamat ladina keelde ja see sai Euroopas laialt levinud.

Iga päev puutub inimene kokku vajadusega järgida teatud reegleid, täita erinevaid juhiseid ja juhiseid. Näiteks foorita ristmikul teed ületades tuleb esmalt vaadata vasakule. Kui autosid pole, siis risti poolel teel ja kui autosid on, siis oota, kuni need mööduvad, siis risti poolel teel. Pärast seda vaadake paremale ja kui autosid pole, siis ületage tee lõpuni ja kui autosid on, oodake, kuni need mööduvad, ja siis ületage tee lõpuni.

Matemaatikas kasutame tüüpiliste ülesannete lahendamiseks teatud reegleid, mis kirjeldavad tegevuste jadasid. Näiteks reeglid murdude liitmiseks, ruutvõrrandite lahendamiseks jne. Tavaliselt on mis tahes juhised ja reeglid toimingute jada, mis tuleb sooritada kindlas järjekorras. Probleemi lahendamiseks peate teadma, mida antakse, mida tuleks vastu võtta ning milliseid toiminguid ja millises järjekorras tuleks selleks teha. Retsept, mis määrab soovitud tulemuste saavutamiseks andmetega toimingute tegemise järjekorra, on algoritm.

Algoritm- etteantud, selge ja täpne juhis võimalikule tegijale teatud toimingute jada sooritamiseks, et saada probleemile lahendus lõpliku arvu sammudega.

See pole definitsioon selle sõna matemaatilises tähenduses, vaid pigem kirjeldus Algoritmi intuitiivne kontseptsioon, mis paljastab selle olemuse.

Algoritmi mõiste ei ole mitte ainult üks matemaatika põhimõisteid, vaid üks kaasaegse teaduse põhimõisteid. Veelgi enam, arvutiteaduse ajastu tulekuga muutuvad algoritmid tsivilisatsiooni üheks olulisemaks teguriks.

Algoritmi täitja- see on mingi abstraktne või reaalne (tehniline, bioloogiline või biotehniline) süsteem, mis on võimeline sooritama algoritmi poolt ette nähtud toiminguid.

Esinejat iseloomustavad:

• kolmapäev;
• elementaarsed toimingud;
• käsusüsteem;
• keeldumised.

kolmapäeval(või keskkond) on esineja "elupaik". Näiteks kooliõpiku esineja Robot jaoks on keskkond lõpmatu rakuväli. Seinad ja värvitud rakud on samuti osa keskkonnast. Ja nende asukoht ja Roboti asend määravad konkreetse keskkonnaseisundit.

Käsusüsteem. Iga täitja saab käske täita ainult kindlast rangelt määratud loendist – täitjakäskude süsteemist. Iga käsu jaoks tuleb täpsustada kohaldamistingimused(millistes keskkonnaseisundites saab käsku täita) ja kirjeldada käsu täitmise tulemused. Näiteks töökäsku "üles" saab täita, kui töö kohal pole seina. Selle tulemuseks on roboti nihkumine ühe raku võrra ülespoole.

Pärast käsu kutsumist sooritab esitaja vastava elementaarne tegevus.

Ebaõnnestumised täituri vead tekivad, kui käsk kutsutakse välja keskkonnaseisundis, mis on selle jaoks vastuvõetamatu.

Arvutiteaduses on algoritmide universaalne täitja arvuti.

| § 2.1. Algoritmid ja täitjad

14. õppetund
§ 2.1. Algoritmid ja täitjad

Märksõnad:

Algoritm
algoritmi omadused (diskreetsus; mõistetavus; kindlus; tõhusus; massiline iseloom)
testamenditäitja
täitja omadused (lahendatavate ülesannete hulk; keskkond; töörežiim; käsusüsteem)
Algoritmi formaalne täitmine

2.1.1. Algoritmi kontseptsioon

Iga inimene lahendab igapäevaelus, õppimises või tööl tohutul hulgal erineva keerukusega probleeme. Keerulised probleemid nõuavad lahenduse leidmiseks palju läbimõtlemist; Inimene lahendab lihtsaid ja tuttavaid ülesandeid mõtlemata, automaatselt. Enamasti saab iga probleemi lahenduse jagada lihtsateks etappideks (sammudeks). Paljude nende ülesannete jaoks (tarkvara installimine, korpuse kokkupanek, veebisaidi loomine, tehnilise seadme kasutamine, lennupileti ostmine Interneti kaudu jne) on samm-sammult juhised juba välja töötatud ja neid pakutakse, järjestikune. mille rakendamine võib viia soovitud tulemuseni.

Näide 1.Ülesanne “Leia kahe arvu aritmeetiline keskmine” lahendatakse kolmes etapis:

1) mõtle välja kaks numbrit;
2) lisada kaks planeeritud numbrit;
3) jagage saadud summa 2-ga.

Näide 2.Ülesanne “Raha sissemakse telefonikontole” on jagatud järgmisteks sammudeks:

1) mine makseterminali;
2) valida sideoperaator;
3) sisestage telefoninumber;
4) kontrollima sisestatud numbri õigsust;
5) panema rahatäht arve vastuvõtjasse;
6) oodake teadet raha laekumise kohta teie kontole;
7) saada tšekk.

Näide 3.Ülesande “Joonista naljakas siil” lahendamise etapid on esitatud graafiliselt:

Aritmeetilise keskmise leidmine, raha telefonikontole kandmine ja siili joonistamine on esmapilgul täiesti erinevad protsessid. Kuid neil on ühine joon: kõiki neid protsesse kirjeldatakse lühikeste juhiste jadaga, mille range järgimine võimaldab teil saada vajaliku tulemuse. Näidetes 1-3 toodud juhiste jadad on algoritmid vastavate ülesannete lahendamiseks. Nende algoritmide täitja on inimene.

Algoritmiks võib olla teatud arvutustejada kirjeldus (näide 1) või mittematemaatilist laadi sammud (näited 2-3). Kuid igal juhul tuleb enne selle väljatöötamist selgelt määratleda algtingimused (algandmed) ja saadav (tulemus). Võime öelda, et algoritm on ülesande lahendamise sammude jada kirjeldus, mis viib algandmetest nõutava tulemuseni.

Üldiselt saab algoritmi tööskeemi esitada järgmiselt (joonis 2.1).

Riis. 2.1. Algoritmi üldskeem

Algoritmid on koolis õpitud arvude liitmise, lahutamise, korrutamise ja jagamise reeglid, paljud grammatikareeglid, geomeetriliste konstruktsioonide reeglid jne.

Animatsioonid "Algoritmiga töötamine" (193576), "Suurim ühisjagaja" (170363), "Vähim ühiskordne" (170390) aitavad teil meeles pidada mõningaid vene keele ja matemaatika tundides õpitud algoritme (http://sc.edu. ru /).

Näide 4. Mõni algoritm viib selleni, et ühest tähemärkide ahelast saadakse uus ahel järgmiselt:

1. Arvutatakse algse märgijada pikkus (märkides).
2. Kui algse keti pikkus on paaritu, siis lisatakse paremal olevale originaalketile number 1, vastasel juhul kett ei muutu.
3. Sümbolid vahetatakse paarikaupa (esimene teisega, kolmas neljandaga, viies kuuendaga jne).
4. Saadud ahelast paremale lisatakse number 2.

Saadud ahel on algoritmi tulemus.

Seega, kui algahelaks oli A#B, siis on algoritmi tulemuseks ahel #A1B2 ja kui algahelaks oli ABC@, siis on algoritmi tulemuseks ahel BA@B2.

2.1.2. Algoritmi täitja

Iga algoritm on loodud konkreetse esineja jaoks.

Täitja on objekt (inimene, loom, tehniline seade), mis on võimeline täitma teatud käskude komplekti.

Eristama ametlikud ja mitteametlikud esinejad. Formaalne täitja täidab sama käsku alati ühtemoodi. Mitteametlik täitja võib käsku täita erineval viisil.

Vaatleme üksikasjalikumalt ametlike esinejate komplekti. Formaalsed täitjad on äärmiselt mitmekesised, kuid igaühe kohta saab määrata järgmised omadused: lahendatavate ülesannete ring (eesmärk), keskkond, käsusüsteem ja töörežiim.

Lahendatavate ülesannete hulk. Iga esineja on loodud teatud hulga probleemide lahendamiseks – sümboliahelate konstrueerimine, arvutuste tegemine, tasapinnal jooniste konstrueerimine jne.

Kunstniku keskkond. Piirkonda, seadet, tingimusi, milles esineja tegutseb, nimetatakse tavaliselt antud esineja keskkonnaks. Iga algoritmi lähteandmed ja tulemused kuuluvad alati selle teostaja keskkonda, kellele algoritm on mõeldud.

Täitja käsusüsteem. Korraldust sooritajale eraldi lõpetatud toimingu sooritamiseks nimetatakse käsuks. Kõigi käskude kogum, mida mõni täitja saab täita, moodustab selle täitja käskude süsteemi (SKI). Algoritm on koostatud võttes arvesse konkreetse esineja võimalusi ehk teisisõnu seda täitva esineja käskude süsteemis.

Esineja töörežiimid. Enamiku esinejate jaoks on ette nähtud otsejuhtimis- ja programmijuhtimisrežiimid. Esimesel juhul ootab esitaja inimeselt käsklusi ja täidab kohe iga saadud käsu. Teisel juhul antakse esitajale esmalt täielik käskude jada (programm) ja seejärel täidab ta kõik need käsud automaatselt. Paljud esinejad töötavad ainult ühes nimetatud režiimis.

Vaatame näiteid esinejatest.

Näide 5. Esineja Kilpkonn liigub arvutiekraanil, jättes jälje joone kujul.

Turtle käsusüsteem koosneb järgmistest käskudest:

1. Edasi n (kus n on täisarv) - paneb Kilpkonna liikuma n sammu liikumissuunas - suunas, kuhu tema pea ja keha on suunatud;
2. Parempoolne m (kus m on täisarv) – põhjustab Kilpkonna liikumissuuna muutuse t kraadi võrra päripäeva.
Salvestus Korda k [<Команда1> <Команда2> ... <Командаn>] tähendab, et sulgudes olevate käskude jada korratakse k korda.

Mõelge, milline kujund ilmub ekraanile pärast seda, kui kilpkonn on järgmise algoritmi täitnud.
Korda 12 [paremale 45 edasi 20 paremale 45]

Näide 6. Täitjate käskude süsteem Arvuti koosneb kahest käsust, millele on määratud numbrid:

1 – lahuta 1
2 - korrutage 3-ga

Esimene neist vähendab arvu 1 võrra, teine ​​suurendab arvu 3 korda. Algoritmide kirjutamisel on lühiduse huvides märgitud ainult käskude numbrid. Näiteks algoritm 21212 tähendab järgmist käskude jada:

Korrutage 3-ga
lahutada 1
korrutada 3-ga
lahutada 1
korrutada 3-ga

Seda algoritmi kasutades teisendatakse number 1 15-ks:

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

Näide 7. Performer Robot tegutseb ruudulisel väljal, külgnevate lahtrite vahel võivad olla seinad. Robot liigub mööda välja lahtreid ja suudab täita järgmisi käske, millele on määratud numbrid:

1 - üles
2 - alla
3 - õige
4 - vasakule

Iga sellise käsu täitmisel liigub robot näidatud suunas kõrvalasuvasse lahtrisse. Kui rakkude vahel on selles suunas sein, siis Robot hävib.

Mis juhtub robotiga, kui ta täidab käskude jada 32323 (siin tähistavad numbrid käsunumbreid), alustades liikumist lahtrist A? Milliseid käskude jada peaks robot täitma, et liikuda lahtrist A lahtrisse B, ilma et see seinale põrkuvalt kokku kukuks?

Algoritmi väljatöötamisel:

1) tuvastatakse probleemis esinevad objektid, tehakse kindlaks objektide omadused, objektidevahelised seosed ja võimalikud tegevused objektidega;
2) tehakse kindlaks lähteandmed ja nõutav tulemus;
3) määratakse teostaja tegevuste järjekord, tagades ülemineku algandmetelt tulemusele;
4) toimingute jada salvestatakse sooritaja käsusüsteemi kuuluvate käskude abil.

Võime öelda, et algoritm on algoritmi täitja tegevuse mudel.

2.1.3. Algoritmi omadused

Mitte iga juhendit, juhiste jada või tegevusplaani ei saa pidada algoritmiks. Igal algoritmil on tingimata järgmised omadused: diskreetsus, mõistetavus, kindlus, tõhusus ja massiline iseloom.

Diskreetne omadus tähendab, et tee probleemi lahendamiseni on jagatud eraldi sammudeks (toiminguteks). Igal toimingul on vastav käsk (käsk). Alles pärast ühe käsu täitmist saab täitja alustada järgmise käsu täitmist.

Arusaadavuse omadus tähendab, et algoritm koosneb ainult sooritaja käskude süsteemi kuuluvatest käskudest, s.o sellistest käskudest, mida sooritaja suudab tajuda ja mille järgi saab sooritada vajalikke toiminguid.

Kindluse omadus tähendab, et algoritm ei sisalda käske, mille tähendust saab täitja mitmetähenduslikult tõlgendada; Olukorrad on vastuvõetamatud, kui pärast järgmise käsu täitmist on esitajale ebaselge, millist käsku järgmisena täita. Tänu sellele määrab algoritmi tulemuse üheselt algandmete kogum: kui algoritmi rakendada mitu korda samale lähteandmete kogumile, annab väljund alati sama tulemuse.

Jõudlusomadused tähendab, et algoritm peab andma tulemuse pärast lõplikku, võib-olla väga suurt arvu samme. Sel juhul ei loeta tulemuseks mitte ainult probleemi avaldusega määratud vastust, vaid ka järeldust selle kohta, et probleemi ei ole mingil põhjusel võimalik jätkata.

Massilise iseloomu omadus tähendab, et algoritm peab andma võimaluse selle rakendamiseks lahendada mis tahes ülesandeid teatud probleemide klassist. Näiteks ruutvõrrandi juurte leidmise algoritm peaks olema rakendatav iga ruutvõrrandi jaoks, tänava ületamise algoritm peaks olema rakendatav kõikjal tänaval, ravimi valmistamise algoritm peaks olema rakendatav selle mis tahes koguse valmistamiseks, jne.

Näide 8. Vaatleme ühte meetodit kõigi algarvude leidmiseks, mis ei ületa mõnda naturaalarvu n. Seda meetodit nimetatakse "Eratosthenese sõelaks" Vana-Kreeka teadlase Eratosthenese (3. sajand eKr) järgi, kes selle välja pakkus.

Kõigi algarvude leidmiseks, mis ei ole suuremad kui etteantud arv n, järgides Eratosthenese meetodit, peate tegema järgmised toimingud:

1) kirjutage ritta kõik naturaalarvud 2 kuni n (2, 3, 4, ..., n);
2) kaader 2 - esimene algarv;
3) kriipsutab loendist maha kõik viimase leitud algarvuga jaguvad arvud;
4) leida esimene märgistamata arv (märgitud numbrid on läbikriipsutatud numbrid või raami sees olevad numbrid) ja sulgeda see raami - sellest saab teine ​​algarv;
5) korrake samme 3 ja 4, kuni pole enam ühtegi märgistamata numbrit.

Visuaalsema ettekujutuse algarvude leidmise meetodist saate digitaalsete õpperessursside ühtsesse kogusse postitatud animatsiooni "Sieve of Eratosthenes" (180279) abil.

Vaadeldav toimingute jada on algoritm, kuna see vastab järgmistele omadustele:

diskreetsus- algarvude leidmise protsess on jagatud sammudeks;
mõistetavus- iga käsk on arusaadav seda algoritmi sooritavale 8. klassi õpilasele;
kindlus- iga käsku tõlgendab ja täidab esitaja üheselt; seal on juhised käskude täitmise järjekorra kohta;
tõhusust- pärast teatud arvu samme saavutatakse tulemus;
massiline iseloom- toimingute jada on rakendatav mis tahes naturaalarvu n korral.

Algoritmi vaadeldavad omadused võimaldavad anda algoritmi täpsema definitsiooni.

Algoritm on konkreetsele sooritajale mõeldud toimingute jada kirjeldus, mis viib algandmetest nõutud tulemuseni, millel on diskreetsuse, arusaadavuse, kindluse, tõhususe ja massilisuse omadused.

2.1.4. Inimtegevuse automatiseerimise võimalus

Algoritmi väljatöötamine on tavaliselt töömahukas töö, mis nõuab inimeselt sügavaid teadmisi, leidlikkust ja palju aega.

Ülesande lahendamine valmis algoritmi abil eeldab ainult täitjalt etteantud juhiste ranget järgimist.

Näide 9. Kuhjast, milles on suvaline arv objekte, mis on suuremad kui kolm, võtavad kaks mängijat kordamööda ühe või kaks objekti. Võidab see, kes saab järgmisel käigul kõik ülejäänud esemed üles korjata.

Vaatleme algoritmi, mille järgimine tagab võidu kindlasti esimene mängija.

1. Kui hunnikus olevate objektide arv on 3-kordne, siis anna teed vastasele, vastasel juhul alusta mängu 1 või 2 objekti võtmisega nii, et järelejäänud objektide arv on 3-kordne.
2. Järgmise käiguga lisage iga kord vastase võetud objektide arv 3-ni (ülejäänud objektide arv peab olema 3-kordne).

Esineja ei pruugi süveneda sellesse, mida ta teeb, ja mitte põhjendada, miks ta nii ja mitte teisiti käitub, ehk ta võib käituda formaalselt. Esineja võime formaalselt tegutseda annab võimaluse inimtegevuse automatiseerimiseks. Selle jaoks:

1) ülesande lahendamise protsess esitatakse lihtsate toimingute jadana;
2) luuakse masin (automaatseade), mis on võimeline neid toiminguid sooritama algoritmis määratud järjekorras;
3) inimene vabastatakse rutiinsetest tegevustest, algoritmi täitmine usaldatakse automaatsele seadmele.

KÕIGE TÄHTSAM

Täitja- mingi objekt (inimene, loom, tehniline seade), mis on võimeline täitma teatud käskude komplekti.

Formaalne täitja täidab sama käsku alati ühtemoodi. Iga ametliku täitja jaoks saate määrata: lahendatavate ülesannete ring, keskkond, käsusüsteem ja töörežiim.

Algoritm- konkreetsele tegijale mõeldud toimingute jada kirjeldus, mis viib algandmetest nõutava tulemuseni, millel on diskreetsuse, arusaadavuse, kindluse, tõhususe ja massilisuse omadused.

Esineja tegutsemisoskus formaalselt annab võimaluse inimtegevusi automatiseerida.

Küsimused ja ülesanded

1. Lugege läbi õpiku elektroonilises lisas sisalduva lõigu esitlusmaterjalid. Kas esitlus täiendab lõigu tekstis sisalduvat teavet? Milliseid slaide saaksite oma esitlusele lisada?

2. Mida nimetatakse algoritmiks?

3. Valige sõnale "retsept" sünonüümid.

4. Too näiteid koolis õpitud algoritmide kohta.

5. Kes saab olla algoritmi täitja?

6. Tooge näide ametlikust esinejast. Tooge näide, kui inimene tegutseb ametliku esinejana.

7. Mis määrab "arvuti" sooritaja poolt sooritatavate ülesannete ulatuse?

8. Täitjaks pidage oma arvuti tekstitöötlusprogrammi. Kirjeldage selle esineja ja tema keskkonna lahendatud ülesandeid.

9. Mis on meeskond, sooritajate käskude süsteem?

10. Milliseid käske peaks robot täitma järgmisi funktsioone:

a) kassapidaja kaupluses;
b) korrapidaja;
c) turvamees?

11. Loetlege algoritmi peamised omadused.

12. Milleni võib viia algoritmi ühegi omaduse puudumine? Too näiteid.

13. Mis tähtsus on algoritmi formaalse täitmise oskusel?

14. Arvude jada konstrueeritakse järgmise algoritmi järgi: jada kaks esimest arvu võetakse võrdseks 1-ga; Iga järgmine arv järjestuses on võrdne kahe eelmise arvu summaga. Kirjutage üles selle jada esimesed 10 liiget. Uurige, kuidas seda järjestust nimetatakse.

15. Teatud algoritm saab ühest märgijadast uue ahela järgmiselt. Kõigepealt kirjutatakse esialgne märgiahel, pärast seda kirjutatakse vastupidises järjekorras esialgne märgiahel, seejärel kirjutatakse täht, mis järgneb vene tähestikus pärast seda tähte, mis oli algses ahelas viimasel kohal. Kui täht “I” on algahelas viimasel kohal, siis järgmise tähena kirjutatakse täht “A”. Saadud ahel on algoritmi tulemus. Näiteks kui algne tähemärkide ahel oli “HOUSE”, siis on algoritmi tulemuseks kett “DOMMODN”. Antakse märgistring "COM". Mitu tähte “O” on märgiahelas, mis saadakse, kui rakendate sellele ahelale algoritmi ja seejärel rakendate algoritmi uuesti selle töö tulemusele?

16. Leidke Internetist animatsioon Eratosthenese algoritmi sammudest. Kasutage Eratosthenese algoritmi, et leida kõik algarvud, mis ei ületa 50.

17. Mis on kilpkonna algoritmi täitmise tulemus (vt näide 5)?

18. Kirjutage üles kalkulaatori täituri algoritm (vt näide 6), mis ei sisalda rohkem kui 5 käsku:

a) numbrilt 3 numbri 16 saamine;
b) numbrilt 1 numbri 25 saamine.

19. Esitaja käskude süsteem Konstruktor koosneb kahest käsust, millele on määratud numbrid:

1 – määrake 2
2 - jagage 2-ga

Neist esimese järgi liidetakse parempoolsele numbrile 2, teise järgi jagatakse arv 2-ga. Kuidas teisendatakse arv 8, kui sooritaja täidab algoritmi 22212? Looge selle täitja käsusüsteemis algoritm, mille järgi number 1 teisendatakse arvuks 16 (algoritm ei tohiks sisaldada rohkem kui 5 käsku).

20. Millises lahtris peaks asuma roboti esitaja (näide 7), et pärast algoritmi 3241 täitmist sinna naasta?

Tasuta tarkvara:

KuMiri süsteem – haridusmaailmade komplekt (laadige programmi arhiiv alla veebisaidilt) või külastage KuMiri lehte ((http://www.niisi.ru/kumir/)

Algoritmi mõiste. Algoritmi täitjad. Algoritmide omadused

Algoritmi mõiste on arvutiteaduses sama oluline kui teabe mõiste. Algoritmi määratlusi on palju, kuna see mõiste on üsna lai ja seda kasutatakse erinevates teaduse, tehnoloogia ja igapäevaelu valdkondades.

Algoritm on selge ja täpne toimingute jada, mis kirjeldab objekti algolekust lõppolekusse teisendamise protsessi.

Algoritm on konkreetsele tegijale mõeldud toimingute jada täpne kirjeldus, mille eesmärk on antud probleemi lahendamine.

Esineja Algoritmiks võib olla kas inimene (toiduvalmistamise retseptid, erinevad juhised, matemaatiliste arvutuste algoritmid) või tehniline seade. Erinevad masinad (arvutid, tööstusrobotid, kaasaegsed kodumasinad) on ametlikud testamenditäitjad algoritmid. Ametlik täitja ei pea mõistma lahendatava probleemi olemust, kuid ta peab käskude jada täpselt täitma.

Algoritmi saab kirjutada mitmel viisil (sõnaline kirjeldus, graafiline kirjeldus - plokkskeem, programm mõnes programmeerimiskeeles jne). Programm on sisse kirjutatud algoritmprogrammeerimiskeel .

Algoritmi (programmi) loomiseks peate teadma:

lähteülesande andmete täielik komplekt (objekti algseisund);

algoritmi loomise eesmärk (objekti lõppseisund);

esineja käsusüsteem (ehk käskude kogum, mida esitaja mõistab ja suudab täita).

Saadud algoritmil (programmil) peavad olema järgmised atribuudid:

diskreetsus (algoritm on jagatud eraldi sammudeks - käsud);

ühemõttelisus (iga käsk määrab sooritaja ainsa võimaliku tegevuse);

selgus (kõik algoritmikäsud on kaasatud täitjakäskude süsteemi);

tõhusust (esineja peab ülesande lahendama piiratud arvu sammudega).

Enamikul algoritmidel on ka omadus massiline iseloom (sama algoritmi kasutades saate lahendada palju sarnaseid probleeme).

Algoritmide kirjeldamise viisid

Eespool märgiti, et sama algoritmi saab kirjutada erineval viisil. Algoritmi saab üles kirjutada loomulik keel. Nii kasutame retsepte, juhiseid jne. Formaalsetele esinejatele mõeldud algoritmide salvestamiseks spetsiaalne programmeerimiskeeled. Kirjeldada saab mis tahes algoritmi graafiliselt plokkskeemi kujul. Selleks on välja töötatud spetsiaalne märgistussüsteem:

Toome näite kahe suuruse summeerimise algoritmi kirjeldusest plokkskeemi kujul:

Selline algoritmi kirjeldamise viis on inimestele kõige visuaalsem ja arusaadavam. Seetõttu töötatakse formaalsete täitjate algoritmid tavaliselt kõigepealt välja vooskeemi kujul ja alles seejärel luuakse programm ühelprogrammeerimiskeeled .

Tüüpilised algoritmilised struktuurid

Programmeerijal on võimalus konstrueerida ja kasutada ebatüüpilisi algoritmilisi struktuure, kuid see pole vajalik. Iga algoritmi, olenemata sellest, kui keeruline see on, saab välja töötada kolme tüüpilise struktuuri alusel: järgimine, hargnemine ja kordamine. Sel juhul võivad struktuurid paikneda järjestikku üksteise järel või üksteise sees pesastatud.

Lineaarne struktuur (järgnev)

Lihtsaim algoritmiline struktuur on lineaarne. Selles tehakse kõik toimingud üks kord nende salvestamise järjekorras.

Hargnemine

IN täielik hargnemine Sõltuvalt loogilise avaldise (tingimuse) väärtusest on sooritaja toimingute jaoks kaks võimalust. Kui tingimus on tõene, siis täidetakse ainult esimene haru, vastasel juhul ainult teine ​​haru.

Teine haru võib olla tühi. Seda struktuuri nimetatakse mittetäielik hargnemine või ümbersõit.

Mitmest harust saate ehitada struktuuri " valik”(mitu hargnemist), mis valib sõltuvalt mitmest tingimusest esineja toimingute jaoks mitte kahe, vaid suurema hulga valikuvõimaluste hulgast. Tähtis on, et teostataks ainult üks haru – sellises struktuuris muutub oluliseks tingimuste järjekord: kui on täidetud mitu tingimust, siis töötab neist ainult üks – ülalt esimene.

Tsükkel (kordus)

Tsükkelvõimaldab korraldada sama käskude jada mitu kordamist- seda nimetatakse tsükli kehaks. Erinevat tüüpi tsüklilistes algoritmides võib korduste arv sõltuda loogilise avaldise (tingimuse) väärtusest või olla struktuuris endas kõvasti kodeeritud. Seal on tsüklid: " enne», « Hüvasti», aasad loenduriga."Kuni" ja "while" tsüklites võib loogiline avaldis (tingimus) eelneda tsükli kehale ( silmus eeltingimusega) või lõpetage silmus ( silmus järeltingimusega).

Tsüklid« enne» - tsükli keha kordamine kuni tingimus on täidetud:

Tsüklid « Hüvasti» - tsükli keha kordamine seni, kuni tingimus on täidetud(tõsi):

Aasad loenduriga(koos parameetriga)– tsükli põhiosa kordamine määratud arv kordi:

Abialgoritm (alamprogramm, protseduur)

Abialgoritm on moodul, millele pääseb põhialgoritmi kaudu korduvalt juurde. Abialgoritmide kasutamine võib oluliselt vähendada algoritmi suurust ja lihtsustada selle väljatöötamist.

Keeruliste algoritmide väljatöötamise meetodid

Keeruliste algoritmide väljatöötamiseks on kaks meetodit:

Ülesande järjestikuse täpsustamise meetod("ülevalt alla") on see, et algne keeruline ülesanne on jagatud alamülesanneteks. Iga alaülesannet käsitletakse ja lahendatakse eraldi. Kui mõni alamülesanne on keeruline, jagatakse need ka alamülesanneteks. Protsess jätkub seni, kuni alamülesanded on taandatud elementaarseteks. Seejärel kombineeritakse üksikute alamprobleemide lahendused üheks algprobleemi lahendamise algoritmiks. Meetodit kasutatakse laialdaselt, kuna see võimaldab mitmel programmeerijal üheaegselt välja töötada üldalgoritmi ja lahendada lokaalseid alamprobleeme. See on tarkvara kiire arendamise vajalik tingimus.

Kokkupanek meetod(“alt-üles”) seisneb mitmesuguste tarkvaramoodulite loomises, mis rakendavad tüüpiliste probleemide lahendust. Keerulise ülesande lahendamisel saab programmeerija kasutada väljatöötatud mooduleid abialgoritmidena (protseduuridena). Paljudes programmeerimissüsteemid Sarnased moodulite komplektid on juba olemas, mis oluliselt lihtsustab ja kiirendab keerulise algoritmi loomist.

Algoritmid ja juhtimisprotsessid

Kontroll - objektide eesmärgipärane suhtlemine, millest mõned on juhid, teised - juhitud.

Lihtsamal juhul on selliseid objekte kaks:

Arvutiteaduse vaatenurgast kontrollitoiminguid võib pidada kontrolliteabeks. Teavet saab edastada käskude kujul. Välja kutsutakse käskude jada objekti juhtimiseks, mis viib etteantud eesmärgini juhtimisalgoritm. Järelikult võib juhtobjekti nimetada juhtimisalgoritmi teostajaks. Vaadeldavas näites töötab juhtobjekt "vaatamata" juhtobjektiga toimuvat ( avatud ahela juhtimine avatud. Teine juhtimisskeem võib võtta arvesse teavet juhtimisobjektis toimuvate protsesside kohta:

Sel juhul peab juhtimisalgoritm olema piisavalt paindlik, et seda teavet analüüsida ja teha otsuseid oma edasiste toimingute kohta sõltuvalt juhtobjekti olekust ( tagasiside juhtimine). Seda juhtimisskeemi nimetatakse suletud.

Juhtimisprotsesse uuritakse põhjalikumalt ja arutatakse küberneetika. See teadus väidab, et kõige erinevamad juhtimisprotsessid ühiskonnas, looduses ja tehnoloogias toimuvad sarnaselt ja alluvad samadele põhimõtetele.

Teema algusesse