Algoritmi ja sen ominaisuudet.

Algoritmi- selkeä ja tarkka ohje esiintyjälle suorittaa lopullinen komentosarja, joka johtaa alkutiedoista haluttuun tulokseen.

Algoritmin toteuttaja- tämä on kohde tai kohde, jota algoritmi on suunniteltu ohjaamaan.

Esiintyjän komentojärjestelmä (SCS) on koko joukko komentoja, jotka esiintyjä voi suorittaa.

Algoritmin ominaisuudet: ymmärrettävyys, tarkkuus, rajallisuus.

Selkeys: algoritmi koostuu vain suorittajan SKI:ssä olevista komennoista.

Tarkkuus: Jokainen ohjausalgoritmin komento määrittää suorittajan yksiselitteisen toiminnan.

Viimeistely (tai suorituskyky): Algoritmin suorittamisen on johdettava tulokseen äärellisessä määrässä vaiheita.

Esittäjän ympäristö: ympäristö, jossa esiintyjä toimii.

Esiintyjän tietty toimintosarja koskee aina joitain lähdetiedot. Esimerkiksi ruoanvalmistukseen kulinaarisen reseptin mukaan tarvitset asianmukaiset tuotteet (tiedot). Matemaattisen ongelman ratkaisemiseksi (neliöyhtälön ratkaiseminen) tarvitset alustavat numeeriset tiedot (yhtälön kertoimet).

Täysi tietojoukko: tarvittava ja riittävä tietojoukko tehtävän ratkaisemiseksi (halutun tuloksen saavuttamiseksi).

Menetelmät algoritmien kirjoittamiseen.

Yleisimmät menetelmät ovat: graafinen, sanallinen ja muodossa tietokoneohjelmat.

Graafinen menetelmä sisältää tiettyjen graafisten symbolien - lohkojen - käytön.

Lohkojen kokoelma muodostaa ns algoritmin vuokaavio.

Sanallinen tallennus Algoritmit keskittyvät ensisijaisesti ihmisesittäjään ja mahdollistavat käskyjen erilaisen tallennuksen, mutta tallennuksen on oltava melko tarkkaa.

Kun kirjoitat algoritmeja muotoon ohjelmia tietokoneet käyttävät ohjelmointikieliä - järjestelmiä ohjeiden koodaukseen ja niiden käyttöä koskevia sääntöjä. Ohjelmien muodossa oleville algoritmeille on ominaista korkea formalisaatioaste.

Algoritmit määrien kanssa työskentelemiseen. Algoritmisen perusrakenteet.

Määrä on yksittäinen tietoobjekti, jolla on nimi, arvo ja tyyppi.

Summien kanssa työskentelyn algoritmien suorittaja voi olla henkilö tai erityinen tekninen laite, kuten tietokone. Tällaisella esiintyjällä täytyy olla muisti määrien varastointiin.

Määrät voivat olla vakioita tai muuttuvia.

Vakioarvo (vakio) ei muuta arvoaan algoritmin suorittamisen aikana. Vakio voidaan ilmaista omalla arvollaan (luvut 10, 3.5) tai symbolisella nimellä (luku ).

Muuttuva arvo voi muuttaa arvoa algoritmin suorittamisen aikana. Muuttuja merkitään aina symbolisella nimellä (X, A, R5 jne.).

Määrätyyppi määrittää arvojoukon, jonka arvo voi tehdä, ja joukon toimintoja, jotka voidaan suorittaa tällä arvolla. Suurten perustyypit: kokonaisluku, todellinen, symbolinen, looginen.

Ilmaisu- tietue, joka määrittää määrien toimintojen järjestyksen. Lauseke voi sisältää vakioita, muuttujia, operaatiomerkkejä ja funktioita. Esimerkki:

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

Asennuskomento on suorittajan komento, jonka tuloksena muuttuja saa uuden arvon. Komentomuoto:

muuttujan nimi>:=lauseke>

Asennuskomento suoritetaan seuraavassa järjestyksessä: ensin se lasketaan, sitten tuloksena oleva arvo annetaan muuttujalle.

Esimerkki. Olkoon muuttujan A arvo 6. Minkä arvon muuttuja A saa komennon suorittamisen jälkeen: A:= 2 * A - 1?
Ratkaisu. Laskemalla lausekkeen 2*A - 1, jossa on A=6, saadaan luku 11. Tämä tarkoittaa, että muuttujan A uusi arvo on 11.

Seuraavassa oletetaan, että määrien kanssa työskentelyn algoritmien suorittaja on tietokone. Mikä tahansa algoritmi voidaan rakentaa komennoista tehtäviä, syöttö, ulostulo, haarautuminen Ja sykli.

Syötä komento- komento, jolla muuttujan arvot asetetaan syöttölaitteiden (esimerkiksi näppäimistön) kautta.

Esimerkki: syöttö A - muuttujan A arvon syöttäminen tietokoneen näppäimistöltä.

Tulostuskomento: Komento, joka näyttää suuren arvon tietokoneen tulostuslaitteessa (kuten näytössä).

Esimerkki: johtopäätös X - X-muuttujan arvo näkyy näytöllä.

Haarakomento- jakaa algoritmin kahdeksi poluksi tietyn ehdon mukaan; sitten algoritmin suoritus siirtyy yleiseen jatkoon. Haaroittuminen voi olla täydellistä tai epätäydellistä. Haaroittamisen kuvaus lohkokaavioissa ja algoritmisella kielellä:

Tässä sarja tarkoittaa yhtä tai useampaa peräkkäistä komentoa; kv - haarautumisen loppu.

Loop-komento varmistaa komentosarjan (silmukan rungon) toistuvan suorittamisen tiettyjen ehtojen perusteella.

Silmukka ennakkoehdoin- silmukka, jonka suoritus toistetaan, kunnes silmukan ehto on tosi:

Silmukka parametrin kanssa- silmukan rungon toistuva suoritus, kun kokonaislukuparametri kulkee kaikkien arvojen joukon läpi alkuperäisestä (In) viimeiseen (Ik):

Esimerkki. Kaksi yksinkertaista murtolukua annetaan. Luo algoritmi murtoluvun saamiseksi, joka on tulos niiden jaosta.
Ratkaisu. Algebrallisessa muodossa ongelman ratkaisu näyttää tältä:
a/b: c/d = a*d/b*c = m/n
Alkutiedot ovat neljä kokonaislukusuuretta: a, b, c, d. Tuloksena on kaksi kokonaislukua m ja n.

alg jakamalla murtolukuja
ehjänä a, b, c, d, m, n
aloita syöttö a, b, c, d
m:=a*d
n:=b*c
lähtö "Numerator=", m
lähtö "Denominator=", n
koi

Huomaa, että tulostaaksesi tekstiä (mikä tahansa merkkijono), se on kirjoitettava lainausmerkeissä komennossa johtopäätös.

1. Efimova O., Morozov V., Ugrinovich N. Tietotekniikan kurssi tietojenkäsittelytieteen perusteilla. Oppikirja lukioon. - M.: LLC "AST Publishing House"; ABF, 2000
2. Tietojenkäsittelytieteen ongelmakirja-työpaja. 2 nidettä/toim. I. Semakina, E. Henner. - M.: Perustiedon laboratorio, 2001.
3. Ugrinovich N. Tietojenkäsittelytiede ja tietotekniikka. 10-11 luokka - M.: Perustietojen laboratorio, JSC "Moscow Textbooks", 2001

Tehtävät ja testit aiheesta "Algoritmit ja suorittajat"

• Artist Management valmistelija - Algoritmit 6. luokka

  Oppitunnit: 4 Tehtävät: 9 Tenttiä: 1

• 2 tehtävää: 9 koetta: 1

Rakas opiskelija!

Aiheen "Algoritmit ja toteuttajat" tuntemus on välttämätöntä ensisijaisesti ohjelmoinnin jatko-opiskelua varten. Ohjelmoinnin opiskelun perustaksi valittiin QBasic-ohjelmointikieli. Hylkäsimme ajatuksesta Visual Basicin tai minkä tahansa muun olioohjelmointikielen sisällyttämisestä kurssillemme, koska tätä lähestymistapaa ei ole vielä käytetty laajalti useimmissa Venäjän federaation toisen asteen kouluissa. Lisäksi olioohjelmointi perustuu klassisen Dos-ohjelmoinnin periaatteisiin.

Kurssi on suunniteltu yleissivistävään koulutukseen. Kun valmistaudut yliopistojen tietotekniikan pääsykokeisiin, sinun on perehdyttävä ohjelmoinnin opiskelun erityispiirteisiin tietyssä yliopistossa. Joissakin tapauksissa tarvitaan perusteellinen tutkimus useista aiheista, esimerkiksi "Matriisit". Tähän kannattaa kiinnittää huomiota ohjelmoinnin kirjallisuutta opiskellessa, ehkä kannattaa käyttää kokeisiin valmistautumiseen liittyviä metodologisia suosituksia, joita tällä hetkellä julkaistaan ​​useimmissa korkeakouluissa.

Yhteenvetona toteamme, että "lentoharrastuksen" saavuttaminen ohjelmoinnissa on mahdollista vain jatkuvalla harjoittelulla ja ratkaisemalla erityisiä sovellettavia ongelmia.

7.1. Mikä on algoritmi?

Nimi "algoritmi" tulee Keski-Aasialaisen matemaatikon al-Khwarizmi - Algorithmi -nimen latinalaisesta muodosta. Algoritmi on yksi tietojenkäsittelytieteen ja matematiikan peruskäsitteistä.

7.2. Mikä on "algoritmin suorittaja"?

Esiintyjälle on ominaista:

• • Keskiviikko;
  • perustoiminnot;
  • komentojärjestelmä;
  • kieltäytymiset.

keskiviikko(tai ympäristö) on esiintyjän "elinympäristö". Esimerkiksi koulun oppikirjan esittäjälle Robotille ympäristö on ääretön solukenttä. Myös seinät ja maalatut kennot ovat osa ympäristöä. Ja niiden sijainti ja itse robotin sijainti asettavat tietyn ympäristön tila.

Komentojärjestelmä. Jokainen suorittaja voi suorittaa komentoja vain tietystä tiukasti määritellystä luettelosta - suorittimen komentojärjestelmästä. Jokaiselle komentolle on määritettävä soveltamisedellytykset(missä ympäristötiloissa komento voidaan suorittaa) ja kuvattu komennon suorittamisen tulokset. Esimerkiksi työkomento “ylös” voidaan suorittaa, jos työn yläpuolella ei ole seinää. Sen seurauksena robotti siirtyy yhden solun ylöspäin.

Kutsuttuaan komennon esiintyjä suorittaa vastaavan alkeellista toimintaa .

Epäonnistumisia suorittajavirheitä ilmenee, jos komento kutsutaan ympäristötilassa, jota se ei voi hyväksyä.

Tietojenkäsittelytieteessä algoritmien universaali toteuttaja on tietokone.

7.3. Mitä ominaisuuksia algoritmeilla on?
Algoritmien pääominaisuudet ovat seuraavat:

Ymmärrettävyys esiintyjälle - ts. Algoritmin suorittajan on osattava suorittaa se.

Diskreetti(epäjatkuvuus, erillisyys) - ts. Algoritmin on esitettävä ongelman ratkaisuprosessi yksinkertaisten (tai aiemmin määriteltyjen) vaiheiden (vaiheiden) peräkkäisenä suorituksena.

Varmuutta- eli Algoritmin jokaisen säännön on oltava selkeä, yksiselitteinen, eikä siinä saa jättää tilaa mielivaltaisuudelle. Tämän ominaisuuden ansiosta algoritmin suoritus on luonteeltaan mekaanista eikä vaadi lisäohjeita tai -tietoja ratkaistavasta ongelmasta.

Tehokkuus (tai raajaan). Tämä ominaisuus on, että algoritmin on johdettava ongelman ratkaisemiseen äärellisessä määrässä vaiheita.

Massahahmo. Tämä tarkoittaa, että ongelman ratkaisun algoritmi kehitetään yleisessä muodossa, ts. sen pitäisi olla sovellettavissa tiettyyn ongelmaluokkaan, jotka eroavat vain lähtötiedoista. Tässä tapauksessa lähtötiedot voidaan valita tietystä alueesta, jota kutsutaan algoritmin soveltuvuusalueeksi.

Algoritmin käsite

Algoritmiset kielet

Algoritmit. Algoritmisointi.

Algoritmin käsite on tietojenkäsittelytieteen kannalta yhtä perustavanlaatuinen kuin tiedon käsite. Siksi on tärkeää ymmärtää se.

Nimi "algoritmi" tulee Keski-Aasian suurimman matemaatikon nimen latinalaisesta muodosta Muhammad ibn Musa al-Khwarizmi(Alhorithmi), joka asui 783-850. Kirjassaan "On Indian Counting" hän hahmotteli säännöt luonnollisten lukujen kirjoittamisesta arabialaisilla numeroilla ja säännöt niiden käyttämisestä "sarakkeessa", jotka ovat nyt tuttuja jokaiselle koululaiselle. 1100-luvulla tämä kirja käännettiin latinaksi ja siitä tuli laajalle levinnyt Euroopassa.

Joka päivä henkilö kohtaa tarpeen noudattaa tiettyjä sääntöjä, suorittaa erilaisia ​​​​ohjeita ja ohjeita. Esimerkiksi kun ylität tien risteyksessä ilman liikennevaloa, sinun on ensin katsottava vasemmalle. Jos autoja ei ole, ylitä puolitie, ja jos autoja on, odota, kunnes ne ohittavat, ja ylitä sitten puolivälissä. Sen jälkeen katso oikealle ja jos autoja ei ole, ylitä tie loppuun asti, ja jos autoja on, odota, kunnes ne ohittavat, ja ylitä sitten tie loppuun.

Matematiikassa tyypillisten ongelmien ratkaisemiseksi käytämme tiettyjä sääntöjä, jotka kuvaavat toimintasarjoja. Esimerkiksi säännöt murtolukujen lisäämiseksi, toisen asteen yhtälöiden ratkaisemiseksi jne. Tyypillisesti kaikki ohjeet ja säännöt ovat toimintosarja, joka on suoritettava tietyssä järjestyksessä. Ongelman ratkaisemiseksi sinun on tiedettävä, mitä annetaan, mitä pitäisi saada ja mitä toimia ja missä järjestyksessä tulisi tehdä tämän saavuttamiseksi. Resepti, joka määrittää järjestyksen, jossa tiedoille suoritetaan toimenpiteitä haluttujen tulosten saavuttamiseksi, on algoritmi.

Algoritmi- ennalta määrätty, selkeä ja tarkka ohje mahdolliselle suorittajalle suorittaa tietty toimintosarja saadakseen ratkaisun ongelmaan äärellisessä määrässä vaiheita.

Tämä ei ole määritelmä sanan matemaattisessa merkityksessä, vaan pikemminkin kuvaus intuitiivinen käsite algoritmista, paljastaen sen olemuksen.

Algoritmin käsite ei ole vain yksi matematiikan pääkäsitteistä, vaan yksi modernin tieteen pääkäsitteistä. Lisäksi tietojenkäsittelytieteen aikakauden tullessa algoritmeista tulee yksi sivilisaation tärkeimmistä tekijöistä.

Algoritmin toteuttaja- tämä on jokin abstrakti tai todellinen (tekninen, biologinen tai biotekninen) järjestelmä, joka pystyy suorittamaan algoritmin määräämiä toimia.

Esiintyjälle on ominaista:

• Keskiviikko;
• perustoiminnot;
• komentojärjestelmä;
• kieltäytymiset.

keskiviikko(tai ympäristö) on esiintyjän "elinympäristö". Esimerkiksi koulun oppikirjan esittäjälle Robotille ympäristö on ääretön solukenttä. Myös seinät ja maalatut kennot ovat osa ympäristöä. Ja niiden sijainti ja itse robotin sijainti asettavat tietyn ympäristön tila.

Komentojärjestelmä. Jokainen suorittaja voi suorittaa komentoja vain tietystä tiukasti määritellystä luettelosta - suorittimen komentojärjestelmästä. Jokaiselle komentolle on määritettävä soveltamisedellytykset(missä ympäristötiloissa komento voidaan suorittaa) ja kuvattu komennon suorittamisen tulokset. Esimerkiksi työkomento “ylös” voidaan suorittaa, jos työn yläpuolella ei ole seinää. Sen seurauksena robotti siirtyy yhden solun ylöspäin.

Kutsuttuaan komennon esiintyjä suorittaa vastaavan alkeellista toimintaa.

Epäonnistumisia suorittajavirheitä ilmenee, jos komento kutsutaan ympäristötilassa, jota se ei voi hyväksyä.

Tietojenkäsittelytieteessä algoritmien universaali toteuttaja on tietokone.

| § 2.1. Algoritmit ja toteuttajat

Oppitunti 14
§ 2.1. Algoritmit ja toteuttajat

Avainsanat:

Algoritmi
algoritmin ominaisuudet (diskreettisyys; ymmärrettävyys; varmuus; tehokkuus; massaluonne)
toimeenpanija
suorittajan ominaisuudet (ratkaistavien tehtävien valikoima; ympäristö; toimintatapa; komentojärjestelmä)
algoritmin muodollinen suoritus

2.1.1. Algoritmin käsite

Jokainen ihminen jokapäiväisessä elämässä, opiskelussa tai työssä ratkaisee valtavan määrän vaihtelevan monimutkaisia ​​ongelmia. Monimutkaiset ongelmat vaativat paljon ajattelua ratkaisun löytämiseksi; Ihminen ratkaisee yksinkertaisia ​​ja tuttuja tehtäviä ajattelematta, automaattisesti. Useimmissa tapauksissa kunkin ongelman ratkaisu voidaan jakaa yksinkertaisiin vaiheisiin (vaiheisiin). Moniin näistä tehtävistä (ohjelmiston asennus, kaapin kokoaminen, verkkosivuston luominen, teknisen laitteen käyttö, lentolipun ostaminen Internetin kautta jne.) on jo kehitetty ja tarjotaan vaiheittaiset ohjeet. joiden toteuttaminen voi johtaa haluttuun tulokseen.

Esimerkki 1. Tehtävä "Etsi kahden luvun aritmeettinen keskiarvo" ratkaistaan ​​kolmessa vaiheessa:

1) ajattele kahta numeroa;
2) lisää kaksi suunniteltua numeroa;
3) jaa saatu summa kahdella.

Esimerkki 2. Tehtävä "Talleta rahaa puhelintilillesi" on jaettu seuraaviin vaiheisiin:

1) mene maksupäätteelle;
2) valita teleoperaattori;
3) syötä puhelinnumero;
4) tarkista, että syötetty numero on oikein;
5) aseta seteli setelin vastaanottajaan;
6) odota viestiä rahan hyvityksestä tilillesi;
7) saada shekki.

Esimerkki 3."Piirrä hauska siili" -tehtävän ratkaisuvaiheet esitetään graafisesti:

Aritmeettisen keskiarvon löytäminen, rahan tallettaminen puhelintilille ja siilin piirtäminen ovat ensi silmäyksellä täysin erilaisia ​​prosesseja. Mutta niillä on yhteinen piirre: jokainen näistä prosesseista on kuvattu lyhyillä ohjeilla, joiden tiukka noudattaminen mahdollistaa vaaditun tuloksen saavuttamisen. Esimerkeissä 1-3 esitetyt käskysarjat ovat algoritmeja vastaavien ongelmien ratkaisemiseksi. Näiden algoritmien toteuttaja on henkilö.

Algoritmi voi olla kuvaus tietystä laskutoimitussarjasta (esimerkki 1) tai ei-matemaattisista vaiheista (esimerkit 2-3). Mutta joka tapauksessa, ennen sen kehittämistä alkuehdot (alkutiedot) ja saavutettava (tulos) on määriteltävä selvästi. Voidaan sanoa, että algoritmi on kuvaus ongelman ratkaisuvaiheiden sarjasta, joka johtaa lähtötiedoista vaadittuun tulokseen.

Yleisesti ottaen algoritmin toimintakaavio voidaan esittää seuraavasti (kuva 2.1).

Riisi. 2.1. Algoritmin yleinen kaavio

Algoritmit ovat koulussa opittujen lukujen yhteen-, vähennys-, kerto- ja jakolasääntöjä, monia kielioppisääntöjä, geometristen rakenteiden sääntöjä jne.

Animaatiot "Työskentely algoritmin kanssa" (193576), "Suurin yhteinen jakaja" (170363), "Pienin yhteinen kerrannainen" (170390) auttavat sinua muistamaan joitain venäjän kielen ja matematiikan tunneilla opittuja algoritmeja (http://sc.edu. ru /).

Esimerkki 4. Jotkut algoritmit johtavat siihen, että yhdestä merkkiketjusta saadaan uusi ketju seuraavasti:

1. Alkuperäisen merkkijonon pituus (merkeissä) lasketaan.
2. Jos alkuperäisen ketjun pituus on pariton, niin numero 1 lisätään oikeaan alkuperäiseen ketjuun, muuten ketju ei muutu.
3. Symbolit vaihdetaan pareittain (ensimmäinen toisen kanssa, kolmas neljännen kanssa, viides kuudennen kanssa jne.).
4. Numero 2 lisätään tuloksena olevan ketjun oikealle puolelle.

Tuloksena oleva ketju on algoritmin tulos.

Joten jos alkuketju oli A#B, niin algoritmin tulos on ketju #A1B2, ja jos alkuketju oli ABC@, niin algoritmin tulos on ketju BA@B2.

2.1.2. Algoritmin toteuttaja

Jokainen algoritmi on suunniteltu tietylle esiintyjälle.

Suoritin on esine (henkilö, eläin, tekninen laite), joka pystyy suorittamaan tietyn joukon komentoja.

Erottaa virallisia ja epävirallisia esiintyjiä. Muodollinen esiintyjä suorittaa aina saman komennon samalla tavalla. Epävirallinen toimeenpanija voi suorittaa komennon eri tavoin.

Tarkastellaanpa yksityiskohtaisemmin muodollisten esiintyjien joukkoa. Muodolliset suorittajat ovat erittäin erilaisia, mutta jokaiselle heistä voidaan määritellä seuraavat ominaisuudet: ratkaistavien tehtävien kirjo (tarkoitus), ympäristö, komentojärjestelmä ja toimintatapa.

Erilaisia ​​tehtäviä ratkaistavaksi. Jokainen esiintyjä on luotu ratkaisemaan tiettyjä ongelmia - rakentamaan symboliketjuja, suorittamaan laskelmia, rakentamaan piirustuksia tasolle jne.

Taiteilijaympäristö. Aluetta, ympäristöä, olosuhteita, joissa esiintyjä toimii, kutsutaan yleensä tietyn esiintyjän ympäristöksi. Minkä tahansa algoritmin lähdetiedot ja tulokset kuuluvat aina sen esiintyjän ympäristöön, jolle algoritmi on tarkoitettu.

Executor komentojärjestelmä. Esiintyjälle annettua ohjetta suorittaa erillinen suoritettu toiminto kutsutaan komennoksi. Joukko kaikkia komentoja, jotka joku suorittaja voi suorittaa, muodostaa tämän suorittajan komentojärjestelmän (SKI). Algoritmi on koottu ottaen huomioon tietyn esiintyjän kyvyt, toisin sanoen sen suorittavan esiintyjän komentojärjestelmässä.

Esittäjän toimintatilat. Useimmille esiintyjille tarjotaan suora ohjaus ja ohjelman ohjaustilat. Ensimmäisessä tapauksessa esiintyjä odottaa käskyjä henkilöltä ja suorittaa välittömästi jokaisen vastaanotetun komennon. Toisessa tapauksessa esiintyjälle annetaan ensin täydellinen komentosarja (ohjelma), jonka jälkeen hän suorittaa kaikki nämä komennot automaattisesti. Useat esiintyjät työskentelevät vain yhdessä nimetyistä tiloista.

Katsotaanpa esimerkkejä esiintyjistä.

Esimerkki 5. Esiintyjä Kilpikonna liikkuu tietokoneen näytöllä jättäen jäljen viivan muodossa.

Turtle-komentojärjestelmä koostuu seuraavista komennoista:

1. Eteenpäin n (jossa n on kokonaisluku) - saa kilpikonnan liikkumaan n askelta liikkeen suuntaan - suuntaan, johon sen pää ja vartalo ovat päin;
2. Oikea m (missä m on kokonaisluku) - aiheuttaa muutoksen kilpikonnan liikkeen suuntaan t astetta myötäpäivään.
Ennätys Toista k [<Команда1> <Команда2> ... <Командаn>] tarkoittaa, että suluissa oleva komentosarja toistetaan k kertaa.

Ajattele, mikä kuva ilmestyy näytölle, kun kilpikonna suorittaa seuraavan algoritmin.
Toista 12 [oikea 45 eteenpäin 20 oikea 45]

Esimerkki 6. Suoritinkomentojen järjestelmä Tietokone koostuu kahdesta komennosta, joille on annettu numerot:

1 - vähennä 1
2 - kerro 3:lla

Ensimmäinen niistä pienentää numeroa yhdellä, toinen lisää numeroa 3 kertaa. Algoritmeja kirjoitettaessa ilmoitetaan lyhyyden vuoksi vain komentojen numerot. Esimerkiksi algoritmi 21212 tarkoittaa seuraavaa komentosarjaa:

Kerro 3:lla
vähennä 1
kerro 3:lla
vähennä 1
kerro 3:lla

Tällä algoritmilla luku 1 muunnetaan 15:ksi:

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

Esimerkki 7. Performer Robot toimii ruudullisella kentällä, vierekkäisten solujen välissä voi olla seiniä. Robotti liikkuu kentän soluja pitkin ja voi suorittaa seuraavat komennot, jotka on numeroitu:

1 - ylöspäin
2 - alas
3 - oikea
4 jäljellä

Kun jokainen tällainen komento suoritetaan, robotti siirtyy viereiseen soluun osoitettuun suuntaan. Jos solujen välissä on seinä tähän suuntaan, robotti tuhoutuu.

Mitä tapahtuu robotille, jos se suorittaa komentosarjan 32323 (tässä numerot osoittavat komentonumeroita) ja alkaa liikkua solusta A? Millainen komentosarja robotin tulee suorittaa siirtyäkseen solusta A soluun B ilman, että se romahtaa osuessaan seiniin?

Kun kehität algoritmia:

1) tunnistetaan ongelmassa esiintyvät objektit, määritetään objektien ominaisuudet, objektien väliset suhteet ja mahdolliset toimet kohteiden kanssa;
2) lähtötiedot ja vaadittu tulos määritetään;
3) määritetään esiintyjän toimintojen järjestys, joka varmistaa siirtymisen lähtötiedoista tulokseen;
4) toimintojen järjestys tallennetaan suorittajan komentojärjestelmään sisältyvillä komennoilla.

Voidaan sanoa, että algoritmi on malli algoritmin suorittajan toiminnasta.

2.1.3. Algoritmin ominaisuudet

Jokaista ohjetta, käskysarjaa tai toimintasuunnitelmaa ei voida pitää algoritmina. Jokaisella algoritmilla on välttämättä seuraavat ominaisuudet: diskreetti, ymmärrettävyys, varmuus, tehokkuus ja massaluonne.

Diskreetti omaisuus tarkoittaa, että ongelman ratkaisupolku on jaettu erillisiin vaiheisiin (toimiin). Jokaisella toiminnolla on vastaava käsky (komento). Vasta yhden komennon suorittamisen jälkeen suorittaja voi aloittaa seuraavan komennon suorittamisen.

Ymmärrettävyysominaisuus tarkoittaa, että algoritmi koostuu vain esittäjän komentojärjestelmään kuuluvista komennoista, eli sellaisista komennoista, jotka esiintyjä voi havaita ja joiden mukaan hän voi suorittaa vaaditut toiminnot.

Varmuuden ominaisuus tarkoittaa, että algoritmi ei sisällä komentoja, joiden merkityksen esittäjä voi tulkita moniselitteisesti; Tilanteita ei voida hyväksyä, kun seuraavan komennon suorittamisen jälkeen esiintyjälle on epäselvää, mikä komento suorittaa seuraavaksi. Tämän ansiosta algoritmin tulos määräytyy yksiselitteisesti alkutietojoukon mukaan: jos algoritmia sovelletaan useita kertoja samaan alkutietosarjaan, tulos tuottaa aina saman tuloksen.

Suorituskykyominaisuus tarkoittaa, että algoritmin on annettava tulos äärellisen, mahdollisesti erittäin suuren askelmäärän jälkeen. Tässä tapauksessa tuloksena ei pidetä vain ongelman lausunnon määräämää vastausta, vaan myös johtopäätöstä siitä, että tämän ongelman ratkaisemista on mahdotonta jatkaa mistä tahansa syystä.

Massaluonteen ominaisuus tarkoittaa, että algoritmin on tarjottava sovelluksensa mahdollisuus ratkaista mikä tahansa ongelma tietyn luokan ongelmasta. Esimerkiksi toisen asteen yhtälön juurien löytämisalgoritmia tulisi soveltaa mihin tahansa toisen asteen yhtälöön, kadun ylittämisalgoritmia tulisi soveltaa missä tahansa kadulla, lääkkeen valmistusalgoritmia tulisi soveltaa minkä tahansa määrän valmistamiseen, jne.

Esimerkki 8. Tarkastellaan yhtä tapaa löytää kaikki alkuluvut, jotka eivät ylitä jotakin luonnollista lukua n. Tätä menetelmää kutsutaan "Eratosthenesin seulaksi" sen ehdottaneen antiikin kreikkalaisen tiedemiehen Eratosthenesin (3. vuosisadalla eKr.) mukaan.

Jos haluat löytää kaikki alkuluvut, jotka eivät ole suurempia kuin annettu luku n, seuraamalla Eratosthenes-menetelmää, sinun on suoritettava seuraavat vaiheet:

1) kirjoita peräkkäin kaikki luonnolliset luvut 2:sta n:ään (2, 3, 4, ..., n);
2) kehys 2 - ensimmäinen alkuluku;
3) yliviivaa luettelosta kaikki viimeisellä löydetyllä alkuluvulla jaolliset luvut;
4) etsi ensimmäinen merkitsemätön numero (merkityt numerot ovat yliviivattuja tai kehyksen sisällä olevia numeroita) ja sulje se kehykseen - tämä on toinen alkuluku;
5) toista vaiheita 3 ja 4, kunnes merkitsemättömiä numeroita ei ole jäljellä.

Voit saada visuaalisemman käsityksen alkulukujen löytämismenetelmästä käyttämällä animaatiota "Sieve of Eratosthenes" (180279), joka on julkaistu Unified Collection of Digital Educational Resources -kokoelmassa.

Tarkasteltu toimintosarja on algoritmi, koska se täyttää seuraavat ominaisuudet:

diskreetti- alkulukujen etsimisprosessi on jaettu vaiheisiin;
ymmärrettävyyttä- jokainen komento on tämän algoritmin suorittavan 8. luokan oppilaan ymmärrettävissä;
varmuutta- esiintyjä tulkitsee ja suorittaa jokaisen komennon yksiselitteisesti; on ohjeet komentojen suoritusjärjestyksestä;
tehokkuutta- tulos saavutetaan tietyn määrän vaiheita jälkeen;
massahahmo- toimintosarja on sovellettavissa mille tahansa luonnolliselle luvulle n.

Tarkasteltavien algoritmin ominaisuuksien avulla voimme antaa tarkemman määritelmän algoritmille.

Algoritmi on kuvaus tietylle suorittajalle tarkoitetusta toimintosarjasta, joka johtaa lähtötiedoista vaadittuun tulokseen, jolla on diskreettisyys, ymmärrettävyys, varmuus, tehokkuus ja massaluonne.

2.1.4. Mahdollisuus automatisoida ihmisen toimintaa

Algoritmin kehittäminen on yleensä työvaltainen tehtävä, joka vaatii henkilöltä syvää tietoa, kekseliäisyyttä ja paljon aikaa.

Ongelman ratkaiseminen valmiilla algoritmilla edellyttää vain, että esiintyjä noudattaa tarkasti annettuja ohjeita.

Esimerkki 9. Pinosta, joka sisältää minkä tahansa määrän esineitä enemmän kuin kolme, kaksi pelaajaa ottaa vuorotellen yhden tai kaksi esinettä kumpikin. Voittaja on se, joka voi noutaa kaikki jäljellä olevat esineet seuraavalla siirrollaan.

Tarkastellaan algoritmia, jonka jälkeen ensimmäinen pelaaja varmistaa varmasti voiton.

1. Jos pinossa olevien esineiden määrä on 3:n kerrannainen, anna periksi vastustajalle, muussa tapauksessa aloita peli ottamalla 1 tai 2 esinettä niin, että jäljellä olevien esineiden määrä on 3:n kerrannainen.
2. Lisää seuraavalla siirrollasi vastustajasi omien esineiden lukumäärä joka kerta kolmeen (jäljellä olevien objektien määrän on oltava 3:n kerrannainen).

Esiintyjä ei saa syventyä tekemisensä tarkoitukseen eikä perustella, miksi hän toimii näin eikä toisin, eli hän voi toimia muodollisesti. Esiintyjän kyky toimia muodollisesti tarjoaa mahdollisuuden automatisoida ihmisen toimintaa. Tätä varten:

1) ongelman ratkaisuprosessi esitetään yksinkertaisten operaatioiden sarjana;
2) luodaan kone (automaattilaite), joka pystyy suorittamaan nämä toiminnot algoritmissa määritellyssä järjestyksessä;
3) henkilö vapautetaan rutiinitoiminnasta, algoritmin suorittaminen uskotaan automaattiseen laitteeseen.

TÄRKEIN

Toteuttaja- jokin esine (henkilö, eläin, tekninen laite), joka pystyy suorittamaan tietyn komentosarjan.

Muodollinen esiintyjä suorittaa aina saman komennon samalla tavalla. Voit määrittää kullekin viralliselle toimeenpanijalle: ratkaistavat tehtävät, ympäristö, komentojärjestelmä ja toimintatapa.

Algoritmi- kuvaus tietylle esiintyjälle tarkoitetusta toimintosarjasta, joka johtaa lähtötiedoista vaadittuun tulokseen, jolla on diskreetin, ymmärrettävyyden, varmuuden, tehokkuuden ja massaluonteen ominaisuuksia.

Esiintyjän toimintakyky muodollisesti tarjoaa mahdollisuuden automatisoida ihmisen toimintaa.

Kysymyksiä ja tehtäviä

1. Lue oppikirjan sähköisen liitteen kappaleen esitysmateriaalit. Täydentääkö esitys kappaleen tekstin sisältämää tietoa? Millä dioilla voisit täydentää esitystäsi?

2. Mitä kutsutaan algoritmiksi?

3. Valitse synonyymit sanalle "resepti".

4. Anna esimerkkejä koulussa opiskelemistasi algoritmeista.

5. Kuka voi olla algoritmin toteuttaja?

6. Anna esimerkki muodollisesta esiintyjästä. Anna esimerkki, kun henkilö toimii muodollisena esiintyjänä.

7. Mikä määrittää "tietokoneen" suorittajan suorittamien tehtävien kirjon?

8. Ajattele tietokoneesi tekstinkäsittelyohjelmaa suorittajana. Kuvaile tämän esiintyjän ja hänen ympäristönsä ratkaisemia tehtäviä.

9. Mikä on tiimi, esiintyjien komentojärjestelmä?

10. Mitä komentoja robotin tulee suorittaa seuraavat toiminnot:

a) kassalla liikkeessä;
b) talonmies;
c) vartija?

11. Listaa algoritmin pääominaisuudet.

12. Mihin algoritmin ominaisuuden puuttuminen voi johtaa? Antaa esimerkkejä.

13. Mitä merkitystä on kyvyllä suorittaa muodollisesti algoritmi?

14. Numerosarja muodostetaan seuraavan algoritmin mukaan: sekvenssin kaksi ensimmäistä numeroa on yhtä suuri kuin 1; Sarjan jokaisen seuraavan numeron katsotaan olevan yhtä suuri kuin kahden edellisen luvun summa. Kirjoita muistiin tämän sarjan 10 ensimmäistä termiä. Ota selvää, mikä tämän sarjan nimi on.

15. Tietty algoritmi saa uuden ketjun yhdestä merkkijonosta seuraavasti. Ensin kirjoitetaan alkuperäinen merkkiketju, sen jälkeen kirjoitetaan alkuperäinen merkkiketju käänteisessä järjestyksessä, sitten kirjoitetaan se kirjain, joka seuraa venäjän aakkosissa alkuperäisen ketjun viimeisellä sijalla olleen kirjaimen jälkeen. Jos kirjain “I” on alkuperäisen ketjun viimeisellä paikalla, kirjain “A” kirjoitetaan seuraavaksi kirjaimeksi. Tuloksena oleva ketju on algoritmin tulos. Esimerkiksi, jos alkuperäinen merkkiketju oli "HOUSE", algoritmin tuloksena on ketju "DOMMODN". Merkkijono "COM" annetaan. Kuinka monta kirjainta "O" on merkkiketjussa, joka saadaan, jos käytät algoritmia tähän ketjuun ja käytät sitten algoritmia uudelleen sen työn tulokseen?

16. Etsi Internetistä animaatio Eratosthenes-algoritmin vaiheista. Käytä Eratosthenesin algoritmia löytääksesi kaikki alkuluvut, jotka eivät ylitä 50:tä.

17. Mikä on Turtle-algoritmin suorittamisen tulos (katso esimerkki 5)?

18. Kirjoita muistiin Calculator-suoritusohjelman algoritmi (katso esimerkki 6), joka sisältää enintään 5 komentoa:

a) vastaanottaa numerosta 3 numeron 16;
b) saada numerosta 1 numero 25.

19. Esittäjien komentojärjestelmä Konstruktori koostuu kahdesta komennosta, joille on annettu numerot:

1 - määritä 2
2 - jaa 2:lla

Ensimmäisen mukaan oikealla olevaan numeroon lisätään 2, toisen mukaan luku jaetaan kahdella. Miten luku 8 muunnetaan, jos esiintyjä suorittaa algoritmin 22212? Luo tämän suorittimen komentojärjestelmään algoritmi, jonka mukaan luku 1 muunnetaan luvuksi 16 (algoritmi saa sisältää enintään 5 komentoa).

20. Mihin soluun Robotin esiintyjä (esimerkki 7) tulee sijoittaa palatakseen siihen algoritmin 3241 suorittamisen jälkeen?

Ilmaiset ohjelmistot:

KuMir-järjestelmä - Joukko koulutusmaailmoja (lataa ohjelma-arkisto verkkosivustolta) tai vieraile KuMir-sivulla ((http://www.niisi.ru/kumir/)

Algoritmin käsite. Algoritmin toteuttajat. Algoritmien ominaisuudet

Algoritmin käsite on tietojenkäsittelytieteen kannalta yhtä perustavanlaatuinen kuin tiedon käsite. Algoritmille on monia erilaisia ​​määritelmiä, koska tämä käsite on melko laaja ja sitä käytetään tieteen, tekniikan ja jokapäiväisen elämän eri aloilla.

Algoritmi on selkeä ja tarkka toimintosarja, joka kuvaa prosessia, jolla objekti muunnetaan alkuperäisestä tilasta lopulliseen tilaan.

Algoritmi on tarkka kuvaus toimintosarjasta, joka on tarkoitettu tietylle suorittajalle ja jolla pyritään ratkaisemaan tietty ongelma.

Esiintyjä Algoritmi voi olla joko henkilö (ruoanlaittoreseptit, erilaiset ohjeet, matemaattisten laskelmien algoritmit) tai tekninen laite. Erilaisia ​​koneita (tietokoneet, teollisuusrobotit, nykyaikaiset kodinkoneet) ovat muodolliset toimeenpanijat algoritmeja. Muodollisen suorittajan ei tarvitse ymmärtää ratkaistavan ongelman olemusta, mutta hänen on suoritettava komentosarja tarkasti.

Algoritmi voidaan kirjoittaa eri tavoin (sanallinen kuvaus, graafinen kuvaus - lohkokaavio, ohjelma jollakin ohjelmointikielistä jne.). Ohjelma on sisään kirjoitettu algoritmiohjelmointikieli .

Algoritmin (ohjelman) luomiseksi sinun on tiedettävä:

täydellinen sarja lähtötehtävätietoja (objektin alkutila);

algoritmin luomisen tarkoitus (objektin lopullinen tila);

esiintyjän komentojärjestelmä (eli joukko komentoja, jotka esiintyjä ymmärtää ja voi suorittaa).

Tuloksena olevalla algoritmilla (ohjelmalla) on oltava seuraavat ominaisuudet:

diskreetti (algoritmi on jaettu erillisiin vaiheisiin - komentoihin);

yksiselitteisyys (jokainen komento määrittää esiintyjän ainoan mahdollisen toiminnon);

selkeys (kaikki algoritmikomennot sisältyvät suorittajakomentojen järjestelmään);

tehokkuutta (esittäjän on ratkaistava ongelma äärellisessä määrässä vaiheita).

Useimmilla algoritmeilla on myös ominaisuus massahahmo (samaa algoritmia käyttämällä voit ratkaista monia samanlaisia ​​ongelmia).

Tapoja kuvata algoritmeja

Edellä todettiin, että sama algoritmi voidaan kirjoittaa eri tavoin. Voit kirjoittaa algoritmin muistiin luonnollinen kieli. Näin käytämme reseptejä, ohjeita jne. Muodollisille esiintyjille tarkoitettujen algoritmien tallentamiseen, erityistä ohjelmointikielet. Mikä tahansa algoritmi voidaan kuvata graafisesti lohkokaavion muodossa. Tätä tarkoitusta varten on kehitetty erityinen merkintäjärjestelmä:

Otetaan esimerkki kahden suuren summaamisalgoritmin kuvauksesta lohkokaavion muodossa:

Tämä tapa kuvata algoritmia on visuaalisin ja ymmärrettävin ihmisille. Siksi muodollisten suorittajien algoritmit kehitetään yleensä ensin vuokaavion muodossa ja vasta sitten luodaan ohjelma johonkinohjelmointikielet .

Tyypillisiä algoritmirakenteita

Ohjelmoijalla on mahdollisuus rakentaa ja käyttää epätyypillisiä algoritmirakenteita, mutta tämä ei ole välttämätöntä. Mikä tahansa algoritmi, olipa se kuinka monimutkainen tahansa, voidaan kehittää kolmen tyypillisen rakenteen perusteella: seuraaminen, haarautuminen ja toisto. Tällöin rakenteet voivat sijaita peräkkäin peräkkäin tai sisäkkäin toistensa sisällä.

Lineaarinen rakenne (seuraava)

Yksinkertaisin algoritmirakenne on lineaarinen. Siinä kaikki toiminnot suoritetaan kerran siinä järjestyksessä, jossa ne on tallennettu.

Haaroittuminen

SISÄÄN täysi haarautuminen Esiintyjän toiminnoille on kaksi vaihtoehtoa loogisen lausekkeen (ehdon) arvosta riippuen. Jos ehto on tosi, vain ensimmäinen haara suoritetaan, muuten vain toinen haara.

Toinen haara voi olla tyhjä. Tätä rakennetta kutsutaan epätäydellinen haarautuminen tai ohitus.

Useista haaroista voit rakentaa rakenteen " valinta”(useita haarautumisia), joka ei valitse kahdesta, vaan suuremmasta määrästä esiintyjän toimintojen vaihtoehtoja useista ehdoista riippuen. On tärkeää, että vain yksi haara suoritetaan - tällaisessa rakenteessa ehtojen järjestys tulee tärkeäksi: jos useat ehdot täyttyvät, vain yksi niistä toimii - ensimmäinen ylhäältä.

Kierto (toisto)

Kierrävoit järjestää useita toistoja samalle komentosarjalle- sitä kutsutaan syklin rungoksi. Erityyppisissä syklisissä algoritmeissa toistojen määrä voi riippua loogisen lausekkeen (ehdon) arvosta tai se voidaan koodata itse rakenteeseen. On syklejä: " ennen», « Hei hei», silmukat laskurilla."Kun"- ja "while"-silmukoissa looginen lauseke (ehto) voi edeltää silmukan runkoa ( silmukka ennakkoehdoin) tai lopeta silmukka ( silmukka jälkiehdoin).

Pyörät« ennen» - syklin rungon toisto kunnes ehto täyttyy:

Pyörät « Hei hei» - syklin rungon toisto niin kauan kuin ehto täyttyy(totta):

Silmukat laskurilla(parametrin kanssa)– silmukan rungon toistaminen tietyn määrän kertoja:

Apualgoritmi (alirutiini, menettely)

Apualgoritmi on moduuli, johon pääsee toistuvasti pääalgoritmista. Apualgoritmien käyttö voi merkittävästi pienentää algoritmin kokoa ja yksinkertaistaa sen kehitystä.

Menetelmät monimutkaisten algoritmien kehittämiseen

Monimutkaisten algoritmien kehittämiseen on kaksi tapaa:

Menetelmä peräkkäisten tehtävien tarkentamiseen("ylhäältä alas") tarkoittaa, että alkuperäinen monimutkainen tehtävä on jaettu osatehtäviin. Jokainen osatehtävä harkitaan ja ratkaistaan ​​erikseen. Jos jokin osatehtävistä on monimutkainen, ne jaetaan myös osatehtäviin. Prosessi jatkuu, kunnes osatehtävät on pelkistetty alkeellisiin. Yksittäisten osaongelmien ratkaisut yhdistetään sitten yhdeksi algoritmiksi alkuperäisen ongelman ratkaisemiseksi. Menetelmää käytetään laajalti, koska sen avulla useat ohjelmoijat voivat samanaikaisesti kehittää yleisen algoritmin ja ratkaista paikallisia aliongelmia. Tämä on nopean ohjelmistokehityksen välttämätön edellytys.

Kokoonpanomenetelmä("alhaalta ylös") koostuu useiden ohjelmistomoduulien luomisesta, jotka toteuttavat tyypillisten ongelmien ratkaisun. Monimutkaisen ongelman ratkaisemisessa ohjelmoija voi käyttää kehitettyjä moduuleja apualgoritmeina (prosedures). Monessa ohjelmointijärjestelmät Vastaavia moduuleja on jo olemassa, mikä yksinkertaistaa ja nopeuttaa huomattavasti monimutkaisen algoritmin luomista.

Algoritmit ja ohjausprosessit

Ohjaus - kohteiden määrätietoinen vuorovaikutus, joista jotkut ovat johtajia, toiset - hallittuja.

Yksinkertaisimmassa tapauksessa tällaisia ​​kohteita on kaksi:

Tietojenkäsittelytieteen näkökulmasta ohjaustoimenpiteitä voidaan pitää ohjausinformaationa. Tietoa voidaan siirtää komentojen muodossa. Kutsutaan komentosarja ennalta määrättyyn tavoitteeseen johtavan objektin ohjaamiseksi ohjausalgoritmi. Näin ollen ohjausobjektia voidaan kutsua ohjausalgoritmin suorittajaksi. Tarkastetussa esimerkissä ohjausobjekti toimii "katsomatta" mitä ohjausobjektin kanssa tapahtuu ( avoimen silmukan ohjaus avata. Toinen ohjausjärjestelmä voi ottaa huomioon tiedot ohjausobjektissa tapahtuvista prosesseista:

Tässä tapauksessa ohjausalgoritmin on oltava riittävän joustava analysoimaan tätä tietoa ja tekemään päätöksiä jatkotoimenpiteistään ohjausobjektin tilasta riippuen ( palauteohjaus). Tätä ohjausjärjestelmää kutsutaan ns suljettu.

Johtamisprosesseja tutkitaan tarkemmin ja niistä keskustellaan kybernetiikka. Tämä tiede väittää, että yhteiskunnan, luonnon ja tekniikan monipuolisimmat johtamisprosessit tapahtuvat samalla tavalla ja ovat samojen periaatteiden alaisia.

Aiheen alkuun