Mitä ovat algoritmit ja miksi niitä tarvitaan? Algoritmi. Sen tyypit ja ominaisuudet Määritysalgoritmin mukaan

Algoritmi- täsmällisten ja ymmärrettävien käskyjen järjestelmä, määritelty alkutietojen perustoimintojen sarja, jonka toteuttaminen varmistaa tämäntyyppisten ongelmien ratkaisun.

Algoritmin ominaisuudet:

-diskreetti- ongelmanratkaisun (prosessin) järjestys on jaettava yksittäisten vaiheiden sarjaan.

-selkeys- Algoritmin on oltava esiintyjän ymmärrettävissä. Tässä suhteessa algoritmi on kehitettävä keskittyen tiettyyn esiintyjään, ts. Algoritmi voi sisältää komentoja tietyn suorittajan komentojärjestelmistä.

-determinismi- Ymmärrettävänä algoritmi ei saa sisältää komentoja, joiden merkitys voidaan ymmärtää epäselvästi. Algoritmien kääntäjien rikkominen näitä vaatimuksia johtaa siihen, että sama ohjelma ei tuota samoja tuloksia, kun eri suorittajat suorittavat sen.

-tehokkuutta– koostuu siitä, että algoritmin kaikkien komentojen tarkalla suorituksella ongelmien ratkaisuprosessin on pysähdyttävä äärelliseen määrään vaiheita ja samalla on saatava tehtävien asettelussa määritetty tulos.

-massahahmo- algoritmin soveltuvuus tietyn luokan ongelmien ratkaisemiseen.

Tapoja kirjoittaa algoritmi:

-sanallinen– luonnollisen kielen menetelmä.

-graafinen-algoritmin kuvaus kaavioiden avulla.

Operaatioiden tai operaatioryhmien suoritusprosessi

lähtötietojen syöttäminen, tulosten tulostaminen

Päätös - toteutussuunnan valinta

Muokkaus on toimintojen suorittamista, jotka muuttavat komentoja tai komentoryhmiä, jotka muuttavat ohjelmia.

Linjaliittimet yhdellä sivulla.

Interpage-liittimet.

-ohjelmointikieli- Kätevä syöttää tietokoneeseen.

-pseudokoodi on kieli, joka käyttää melko formalisoidun kielen rakennetta ja syntaksia ja mahdollistaa samalla luonnollisten rakenteiden. Kieli.

Algoritmien tyypit ja algoritmien laatimisen perusperiaatteet.

-Lineaarinen– algoritmi, jossa komennot suoritetaan peräkkäin peräkkäin niiden luonnollisessa esiintymisjärjestyksessä, ehdoista riippumatta. S1, s2, S3…Sn

- haarautuminen (haarautuminen)- tämä on prosessi, jossa sen toteutus tapahtuu yhdessä useista ennalta määrätyistä suunnista riippuen lähtötiedoista tai välituloksista.

Täysi ehdollinen rakenne (täysi haarautuminen)

· Epätäydellinen ehdollinen rakenne

· Valitse useista

-syklinen– algoritmi, jossa sarja voidaan suorittaa useammin kuin kerran.

Silmukka parametrin kanssa

· Silmukka ennakkoehdoin. Sitä ei ehkä koskaan toteuteta. Silmukan rungon tulee sisältää operaattori, joka muuttaa lohkossa Q olevan muuttujan arvoa.

· Silmukka jälkiehdoin. Toteutetaan vähintään kerran.

Algoritmisoinnin perusperiaatteet:

1. Tunnista lähdetiedot, tulokset ja anna niille nimet.

2. Ongelmanratkaisumenetelmä.

3. Jaa tehtävien ratkaisutapa vaiheisiin.

4. Algoritmin graafisessa esityksessä jokainen vaihe on vastaavan lohkon muodossa - kaavio algoritmista ja niiden suoritusjärjestyksestä on ilmaistu tietoliikennelinjoilla.

5. Tuloksena olevassa kaaviossa mille tahansa laskentavaihtoehdolle.

Järjestä tulosten tai viestien julkaiseminen niiden puuttumisesta.

Tarjoa mahdollisuuksia siirtyä jollakin tavalla loppulohkoon minkä tahansa toiminnon suorittamisen jälkeen.

40.Algoritmisen perusrakenteet

Olemme jo tarkastelleet ohjelmoinnin peruskäsitteitä ja siirrymme hieman lähemmäs asiaa (mutta vain lähemmäksi, ohjelmoitamme myöhemmin).

Katsotaanpa algoritmien päärakenteita, ja niitä on kuusi:

· Seurata. Tämä on algoritmin lohkojen (tai lohkoryhmien) sarja. Ohjelmassa seuraava on esitetty toimintojen peräkkäisen suorituksen muodossa

·
Haaroittuminen. Tätä algoritmista rakennetta käytetään, kun ehdoista riippuen on tarpeen suorittaa yksi tai toinen toimenpide

·
Ohittaa. Tämä rakenne on haaroittamisen erikoistapaus, kun yhdessä haarassa ei ole toimintaa.

·
Monivalinta. Tämä rakenne on haaroittamisen yleistys, jossa on tarpeen suorittaa yksi useista toiminnoista riippuen muuttujan A arvosta.

Ongelman ratkaisemiseen tarkoitetun ohjelman kääntämiseksi tietokoneessa on laadittava algoritmi sen ratkaisemiseksi.

Algoritmi on tarkka ohje, joka määrittelee prosessin, joka johtaa syöttötiedoista haluttuun lopputulokseen. Algoritmeja ovat esimerkiksi yhteen-, kertolasku-, algebrallisten yhtälöiden ratkaisemisen, matriisikertomisen jne. säännöt. Sana algoritmi tulee sanasta algoritmi, joka on latinalainen translitterointi 800-luvun khorezmilaisen matemaatikon arabiankielisestä nimestä al-Khwarizmi. Kiitos tutkielman latinankielisestä käännöksestä al-Khwarizmi Eurooppalaiset tutustuivat paikkalukujärjestelmään 1100-luvulla, ja keskiaikaisessa Euroopassa algoritmia kutsuttiin desimaalipaikkalukujärjestelmäksi ja sen laskentasäännöiksi.

Suhteessa tietokoneeseen algoritmi määrittelee laskennallisen prosessin, joka alkaa tietyn mahdollisen lähtötiedon joukon käsittelystä ja pyrkii saamaan näiden lähtötietojen määräämiä tuloksia. Termi laskentaprosessi ulottuu muun tyyppisen tiedon, esimerkiksi symbolisen, graafisen tai äänen, käsittelyyn.

Jos laskennallinen prosessi päättyy tulosten saamiseen, niin vastaavan algoritmin sanotaan olevan sovellettavissa tarkasteltavalle lähtötietojoukolle. Muutoin he sanovat, että algoritmia ei voida soveltaa lähtötietojen joukkoon. Kaikilla soveltuvilla algoritmeilla on seuraavat ominaisuudet tärkeimmät ominaisuudet :

tehokkuus;

varmuus;

massahahmo.

Tehokkuus tarkoittaa mahdollisuutta saada tulos sen jälkeen, kun on suoritettu äärellinen määrä operaatioita.

Varmuutta koostuu saatujen tulosten yhteensattumisesta riippumatta käyttäjästä ja käytetyistä teknisistä keinoista.

Massahahmo piilee mahdollisuudessa soveltaa algoritmia koko luokkaan samanlaisia ​​ongelmia, jotka eroavat lähtötietojen tietyistä arvoista.

Algoritmin määrittämiseksi on tarpeen kuvata sen seuraavat elementit:

joukko objekteja, jotka muodostavat mahdollisten lähtötietojen, väli- ja lopputulosten kokonaisuuden;

aloitussääntö;

tietojen suoran käsittelyn sääntö (toimintojen järjestyksen kuvaus);

päättymissääntö;

tulosten poimimisen sääntö.

Algoritmi on aina suunniteltu tietylle esiintyjälle. Meidän tapauksessamme tällainen esiintyjä on tietokone. Toteutuksen mahdollistamiseksi tietokoneella algoritmi on kuvattava tietokoneelle ymmärrettävällä kielellä eli ohjelmointikielellä.

Siten voimme antaa seuraavan määritelmän ohjelmalle.

Tietokoneohjelma on kuvaus algoritmista ja tiedoista jollain ohjelmointikielellä, tarkoitettu myöhempään automaattiseen suoritukseen.

Tapoja kuvata algoritmeja

Tärkeimmät tavat kuvata algoritmeja ovat seuraavat:

sanallinen muoto;

rakenne- tai lohkokaavio;

käyttämällä graafisia kaavioita;

käyttäen Petri-verkkoja.

Ennen ohjelmien laatimista käytetään useimmiten verbaal-formulaarisia ja vuokaaviomenetelmiä. Joskus ennen ohjelmien laatimista matalan tason ohjelmointikielillä, kuten Assembly-kielellä, ohjelma-algoritmi kirjoitetaan käyttämällä jonkin korkean tason ohjelmointikielen rakenteita. On kätevää käyttää ohjelmistokuvausta monimutkaisten ohjelmistojärjestelmien toimintaan tarkoitetuista algoritmeista. Siten käyttöjärjestelmän toimintaperiaatteiden kuvaamiseen käytettiin Algol-tyyppistä korkean tason ohjelmointikieltä.

klo sanallinen ja kaavamainen tapa Algoritmi on kirjoitettu tekstin muodossa kaavoilla, jotka määrittävät toimintojen järjestyksen.

Oletetaan esimerkiksi, että sinun on löydettävä seuraavan lausekkeen arvo:

y = 2a – (x+6).

Sanallisesti ja kaavallisesti algoritmi tämän ongelman ratkaisemiseksi voidaan kirjoittaa seuraavassa muodossa:

1. Syötä arvot A Ja X.

2. Lisää x ja 6.

3. Kerro a 2. päivänä.

4. Vähennä arvosta 2a summa (x+6).

5. Nosta klo lausekkeen arvioinnin tuloksena.

klo lohkokaavio Kuvauksessa algoritmi on kuvattu geometrisilla kuvioilla (lohkoilla), jotka on yhdistetty ohjauslinjoilla (virtaussuunnat) nuolilla. Lohkot tallentavat toimintosarjan.

Tällä menetelmällä on useita etuja verrattuna muihin algoritmin kirjoitusmenetelmiin. Se on visuaalisin: jokainen laskentaprosessin operaatio on kuvattu erillisenä geometrisena kuviona. Lisäksi algoritmin graafinen esitys näyttää selkeästi ongelman ratkaisutapojen seuraukset erilaisista olosuhteista riippuen, laskentaprosessin yksittäisten vaiheiden toistumisen ja muut yksityiskohdat.

Ohjelmien suunnittelun on täytettävä tietyt vaatimukset. Tällä hetkellä käytössä on yhtenäinen ohjelmadokumentaatiojärjestelmä (USPD), joka määrittää säännöt ohjelmien ja ohjelmadokumentaation kehittämiselle, suorittamiselle. ESPD määrittelee myös säännöt algoritmien vuokaavioiden suunnittelulle (GOST 10.002-80 ESPD, GOST 10.003-80 ESPD).

Tietojenkäsittelytoiminnot ja tallennusvälineet on kuvattu kaaviossa vastaavasti lohkot. Suurin osa lohkoista on perinteisesti merkitty suorakulmioon, jossa on sivut a ja b. Minimiarvo A = 10 mm, lisääntyä A on moninkertainen 5 mm. Koko b = 1,5a. Yksittäisten lohkojen välinen suhde a ja b, yhtä suuri kuin 1:2. Samassa kaaviossa on suositeltavaa kuvata samankokoisia lohkoja. Kaikki lohkot on numeroitu. Päälohkojen tyypit ja käyttötarkoitukset on esitetty taulukossa. 1.

Taulukko 1. Algoritmien lohkokaavioiden symbolit

Jokainen algoritmi käsittelee dataa - syöttöä, väli- ja lähtötietoa.

Raaja. Se ymmärretään kahdella tavalla: ensinnäkin algoritmi koostuu yksittäisistä alkeisvaiheista tai toiminnoista, ja algoritmin muodostavat tietysti monet eri vaiheet. Toiseksi algoritmin täytyy päättyä äärelliseen määrään vaiheita. Jos konstruoidaan ääretön prosessi, joka konvergoi haluttuun ratkaisuun, se katkeaa tietyssä vaiheessa ja tuloksena oleva arvo otetaan likimääräiseksi ratkaisuksi tarkasteltavaan ongelmaan. Approksimaation tarkkuus riippuu vaiheiden määrästä.

Elementaarisuus (ymmärrettävyys). Algoritmin jokaisen vaiheen on oltava yksinkertainen, jotta toiminnot suorittava laite voi suorittaa sen yhdessä vaiheessa.

Diskreetti. Ongelman ratkaisuprosessi on esitetty yksittäisten vaiheiden äärellisenä sarjana, ja jokainen algoritmin vaihe suoritetaan äärellisessä (ei välttämättä yksikkö) ajassa.

Determinismi (varmuus). Algoritmin jokaisen vaiheen on oltava yksilöllisesti ja yksiselitteisesti määritelty, eikä se saa sallia mielivaltaista tulkintaa. Jokaisen vaiheen jälkeen joko ilmoitetaan, mikä vaihe otetaan seuraavaksi, tai annetaan stop-komento, jonka jälkeen algoritmin työ katsotaan suoritetuksi.

Tuottavuus. Algoritmilla on tietty määrä syöttösuureita - argumentteja. Algoritmin suorittamisen tarkoituksena on saada tietty tulos, jolla on hyvin tarkka suhde alkuperäiseen dataan. Algoritmin on pysähdyttävä rajallisen askelmäärän jälkeen tiedoista riippuen ja ilmoitettava, mitä pitää tuloksena. Jos ratkaisua ei löydy, on ilmoitettava, mitä tässä tapauksessa katsotaan tulokseksi.

Massahahmo. Algoritmi ongelman ratkaisemiseksi 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 tietyltä alueelta nimeltä algoritmin käyttöalue.

Tehokkuus. Sama ongelma voidaan ratkaista eri tavoilla ja vastaavasti eri aikoina ja eri muistikustannuksilla. On toivottavaa, että algoritmi koostuu vähimmäismäärästä vaiheita ja että ratkaisu täyttää tarkkuusehdon ja vaatii mahdollisimman vähän muita resursseja.

Algoritmin tarkkaa matemaattista määrittelyä vaikeuttaa se, että määrättyjen ohjeiden tulkinta ei saisi riippua niitä suorittavasta henkilöstä. Älytasostaan ​​riippuen hän ei ehkä ymmärrä ollenkaan, mitä ohjeissa tarkoitetaan, tai päinvastoin, tulkitsee sen tahattomasti.

Sääntöjen tulkintaongelma voidaan kiertää, jos määräysten sanamuodon ohella selitetään tulkkauslaitteen rakenne ja toimintaperiaate. Tämä välttää epävarmuuden ja epäselvyyden samojen ohjeiden ymmärtämisessä. Tätä varten on tarpeen määrittää kieli, jolla kuvataan monia käyttäytymissääntöjä tai toimintosarja, sekä itse laite, joka osaa tulkita tällä kielellä tehtyjä lauseita ja suorittaa jokaisen tarkasti määritellyn prosessin askel askeleelta. . Osoittautuu, että tällainen laite (kone) voidaan toteuttaa muodossa, joka pysyy vakiona kyseessä olevan toimenpiteen monimutkaisuudesta riippumatta.

Tällä hetkellä voidaan erottaa kolme päätyyppiä universaaleja algoritmimalleja. Ne eroavat toisistaan ​​lähtöoletuksissaan algoritmin käsitteen määrittelystä.

Ensimmäinen tyyppi yhdistää algoritmin käsitteen perinteisimpiin matematiikan käsitteisiin - laskelmiin ja numeerisiin funktioihin. Toinen tyyppi perustuu ajatukseen algoritmista tiettynä deterministisenä laitteena, joka pystyy suorittamaan vain hyvin primitiivisiä operaatioita kulloinkin. Tämä esitys varmistaa algoritmin yksiselitteisyyden ja sen vaiheiden alkeisluonteen. Lisäksi tämä ajatus vastaa tietokoneiden rakentamisen ideologiaa. Tämän tyyppinen tärkein teoreettinen malli, luotu 1930-luvulla. Englantilainen matemaatikko Alan Turing on Turingin kone.

Kolmas tyyppi– nämä ovat mielivaltaisten aakkosten sanojen muunnoksia, joissa perusoperaatiot ovat substituutioita, ts. sanan osan korvaaminen (sana on aakkosmerkkijono) toisella sanalla. Tämän tyyppisen mallin etuja ovat sen maksimaalinen abstraktio ja kyky soveltaa algoritmin käsitettä mielivaltaisiin (ei välttämättä numeerisiin) objekteihin. Esimerkkejä kolmannen tyypin malleista ovat amerikkalaisen matemaatikon Emil L. Postin kanoniset järjestelmät ja neuvostomatemaatikon A. A. Markovin esittelemät normaalialgoritmit.

Toisen ja kolmannen tyypin mallit ovat melko läheisiä ja eroavat toisistaan ​​pääasiassa heurististen aksenttien suhteen, joten ei ole sattumaa, että ne puhuvat Postin koneesta, vaikka Post itse ei siitä puhunut.

Algoritmin tallennus jollakin kielellä on ohjelma. Jos ohjelma on kirjoitettu erityisellä algoritmikielellä (esimerkiksi PASCAL, BASIC tai jollain muulla), puhumme alkuperäinen ohjelma. Ohjelmaa, joka on kirjoitettu kielellä, jota tietokone voi suoraan ymmärtää (yleensä binäärikoodeja), kutsutaan kone, tai binääri.

Mikä tahansa tapa kirjoittaa algoritmi edellyttää, että jokainen sen avulla kuvattu objekti määritellään tietyksi edustajaksi usein äärettömälle objektiluokalle, joka voidaan kuvata tällä tavalla.

Algoritmien kirjoittamiseen käytetyt keinot määräytyvät suurelta osin sen mukaan, kuka on esiintyjä.

Jos esiintyjä on henkilö, nauhoitus ei välttämättä ole täysin muodollinen selkeys ja näkyvyys. Tässä tapauksessa tallentamiseen voidaan käyttää algoritmikaavioita tai sanallista merkintää.

Automaattien suorittajille tarkoitettujen algoritmien kirjoittamiseen tarvitaan formalisointi, joten tällaisissa tapauksissa käytetään muodollisia erikoiskieliä. Formaalisen merkintätavan etuna on, että se mahdollistaa algoritmien tutkimisen matemaattisina objekteina; tässä tapauksessa algoritmin muodollinen kuvaus toimii perustana tämän algoritmin älylliseen ymmärtämiseen.

Algoritmien kirjoittamiseen käytetään monenlaisia ​​​​tapoja. Työkalun valinta määräytyy suoritettavan algoritmin tyypin mukaan. Erotetaan seuraavat: tärkeimmät tavat kirjoittaa algoritmeja:

■ sanallinen– algoritmi on kuvattu ihmiskielellä;

■ symbolinen– algoritmi kuvataan käyttämällä symbolijoukkoa;

■ graafinen– algoritmi kuvataan graafisten kuvien avulla.

Yleisesti hyväksyttyjä tapoja kirjoittaa algoritmi ovat graafinen tallennus käyttämällä algoritmikaavioita (vuokaavioita) ja symbolinen merkintä käyttämällä jotain algoritmista kieltä.

Algoritmin kuvaamiseksi kaavioita käytetään kuvaamaan yhdistettyä geometristen kuvioiden sarjaa, joista jokainen tarkoittaa algoritmin tietyn toiminnon suorittamista. Toimintojen järjestys on merkitty nuolilla.

Algoritmikaavioissa käytetään seuraavan tyyppisiä graafisia symboleja.

alkaa Ja loppu Algoritmi on merkitty samoilla symboleilla (kuva 21.1).

Riisi. 21.1.

Algoritmin vaihe, joka liittyy uuden arvon määrittämiseen tietylle muuttujalle, tietyn arvon muuntamiseen toisen arvon saamiseksi, esitetään symbolilla "käsitellä asiaa"(Kuva 21.2).

Riisi. 21.2.

Algoritmin suoritussuunnan valintaa joistakin muuttuvista olosuhteista riippuen edustaa symboli " ratkaisu"(Kuva 21.3).

Riisi. 21.3.

Tässä R tarkoittaa predikaattia (ehdollinen lauseke, ehto). Jos ehto täyttyy (predikaatti saa arvon TOSI), siirrytään algoritmin yhteen vaiheeseen ja jos ei täyty, niin toiseen.

Tietojen syöttö- ja tulostusoperaatioille on primitiivit sekä muut graafiset symbolit. Tällä hetkellä ne määritellään GOST 19.701-90 (ISO 5807-85) -standardissa "Algoritmien, tietoohjelmien ja -järjestelmien skeemat ja suoritussäännöt". ESPD-kokoelma sisältää yhteensä 28 asiakirjaa.

Algoritmikaavion avulla on helppo koota alkuohjelma algoritmisella kielellä.

Algoritmin toimintosarjan mukaan erotetaan lineaarisen, haarautuneen ja syklisen rakenteen algoritmit.

Algoritmeissa lineaarinen rakenne toiminnot suoritetaan peräkkäin peräkkäin.

Algoritmeissa haarautunut rakenne Riippuen minkä tahansa ehdon täyttymisestä tai täyttymättä jättämisestä, suoritetaan erilaisia ​​toimintosarjoja. Jokaista tällaista toimintosarjaa kutsutaan algoritmin haara.

Algoritmeissa syklinen rakenne Minkä tahansa ehdon täyttymisestä tai täyttymättä jäämisestä riippuen suoritetaan toistuva toimintosarja, jota kutsutaan syklin runko. Sisäkkäinen silmukka on sellainen, joka on toisen silmukan rungon sisällä. Iteratiivinen sykli on sykli, jonka toistojen määrää ei ole määritelty, mutta se määräytyy syklin suorittamisen aikana.

Tässä tapauksessa kutsutaan yksi syklin toisto iteraatio.

esiintyjälle ymmärrettävällä kielellä muotoiltu sääntöjärjestelmä, joka määrittää siirtymisprosessin hyväksyttävästä lähtötiedosta tiettyyn tulokseen ja jolla on massan, äärellisyyden, varmuuden ja determinismin ominaisuuksia.

Sana "algoritmi" tulee 8.-9. vuosisadan suuren Keski-Aasian tiedemiehen nimestä. Al-Khorezmi (Khorezmin historiallinen alue nykyaikaisen Uzbekistanin alueella). Al-Khorezmin matemaattisista teoksista vain kaksi on saavuttanut meidät: algebrallinen (tämän kirjan nimestä syntyi sana algebra) ja aritmetiikka. Toista kirjaa pidettiin pitkään kadonneena, mutta vuonna 1857 sen latinaksi käännös löydettiin Cambridgen yliopiston kirjastosta. Se kuvaa neljä aritmeettisten operaatioiden sääntöä, melkein samoja, joita käytetään nyt. Tämän kirjan ensimmäiset rivit käännettiin seuraavasti: "Sanottu algoritmi. Ylistäkäämme Jumalaa, johtajaamme ja suojelijaamme." Joten nimi Al-Khorezmi tuli Algoritmi, josta sana algoritmi tuli. Termiä algoritmi käytettiin kuvaamaan neljää aritmeettista operaatiota, ja tässä mielessä se tuli joihinkin eurooppalaisiin kieliin. Esimerkiksi arvovaltaisessa englannin sanakirjassa Websterin uuden maailman sanakirja, julkaistiin vuonna 1957, sana algoritmi on merkitty "vanhentuneeksi" ja sen selitetään suorittavan aritmeettisia operaatioita arabialaisilla numeroilla.

Sanaa "algoritmi" käytettiin jälleen elektronisten tietokoneiden tultua käyttöön kuvaamaan joukko toimintoja, jotka muodostavat tietyn prosessin. Tämä ei tarkoita vain tietyn matemaattisen ongelman ratkaisemista, vaan myös kulinaarista reseptiä ja pesukoneen käyttöä koskevia ohjeita ja monia muita peräkkäisiä sääntöjä, jotka eivät liity matematiikkaan, kaikki nämä säännöt ovat algoritmeja. Sana "algoritmi" on nykyään kaikkien tiedossa, että se on tullut puhekieleen niin luottavaisesti, että nykyään sanomalehtien sivuilta ja puheissa esiintyy usein ilmaisuja "käyttäytymisalgoritmi", "menestysalgoritmi" jne. poliitikot.

Turing A. Osaako kone ajatella?? M., Mir, 1960
Uspenski V. Postin auto. Tiede, 1988
Cormen T., Leiserson, Rives R. Algoritmit. Rakentaminen ja analyysi. M., MTsNMO, 1999

Etsi "ALGORITHM" päällä

Ennen kuin alamme kirjoittaa superohjelmia, selvitetään mikä ohjelma on? Ohjelma on tietty algoritmi, joka tietokoneen on suoritettava.

No, nyt pääkysymys: Mikä on algoritmi?

Algoritmien ominaisuudet

En keksi pyörää uudelleen, vaan yksinkertaisesti luettelen algoritmin ominaisuudet, jotka ovat olleet tiedossa monta vuotta.

1. Äärimmäisyys (tehokkuus) algoritmi tarkoittaa, että tulos täytyy saada äärellisessä määrässä vaiheita;
2. Diskreetti Algoritmi tarkoittaa, että algoritmi on jaettava vaiheiden sarjaan;
3. Ymmärrettävyys Algoritmi tarkoittaa, että algoritmi saa sisältää vain ne komennot, jotka sisältyvät komentosarjaan, jonka tietty suorittaja voi suorittaa;
4. Tarkkuus algoritmi tarkoittaa, että jokainen komento on ymmärrettävä yksiselitteisesti;
5. Massahahmo Algoritmi tarkoittaa, että algoritmin on käännettyään soveltuva ratkaisemaan samanlaisia ​​ongelmia eri lähtötiedoilla.
6. Determinismi (varmuus). Algoritmilla on determinismin ominaisuus, jos se tuottaa samoilla lähtötietosarjoilla saman tuloksen, ts. tulos määräytyy yksiselitteisesti alkutietojen perusteella.

Täten, Algoritmi- Tämä on selkeä ja tarkka ohje esiintyjälle suorittaa lopullinen vaihesarja, joka johtaa alkutiedoista haluttuun tulokseen.

Kuvittele, että minun täytyy leikata appelsiini veitsellä. Tämän toiminnon suorittamiseksi tarvitsen algoritmin.

Haluan leikata appelsiinin. Kuinka tehdä se?

Algoritmien tyypit

• Lineaarinen (komennot ovat peräkkäisiä ilman toistoja tai siirtymiä);

Esimerkki algoritmista:

alkaa
ota veitsi pois
leikkaa appelsiini (se on appelsiini, ei mikään muu hedelmä. TARKKUUS on vastuussa tästä)
syö appelsiini
loppu

• Syklinen (On joukko toimintoja, jotka toistetaan jonkin ehdon mukaan);

Esimerkki algoritmista:

alkaa
ota veitsi pois
Kunnes appelsiinit ovat poissa
leikkaa appelsiini
syö kaikki appelsiinit
loppu

• Haaroittuminen (komennon suoritus riippuu ehdosta).

Esimerkki algoritmista:

alkaa
ota veitsi pois
JOS veitsi on tylsä, teroita se
leikkaa appelsiini
syö appelsiini
loppu

Siinä kaikki. Seuraavalla oppitunnilla tarkastellaan ohjelman rakennetta Pascalissa.

Tietojenkäsittelytieteen loppukoe

1. Mikä oli antiikin Kreikassa käytetyn laskentalaitteen nimi?

1. laskin
2. Pascalin kone
3. lisäyskone
4. logaritminen viivain

2. Ensimmäisen ohjelmistoohjatun koneen projekti kehitettiin:

1. Charles Babbage
2. Blaise Pascal
3. John von Neumann
4. S.A. Lebedev
5. John Napier

3. Ohjelmien ja tietojen syöttämiseen ensimmäisen sukupolven tietokoneisiin he käyttivät

1. magneettiset rummut
2. optiset levyt
3. magneettiset levyt
4. reikäkortteja
5. magneettinauhat

4. Ensimmäisen sukupolven alkuainepohja olivat

1. transistorit
2. mikroprosessorit
3. integroidut piirit
4. tyhjiöputket
5. sähkömekaaninen rele

5. Ensimmäinen tietokone oli nimeltään...

6. Kuka suunnitteli ensimmäiset kotimaiset tietokoneet?

7. Mikä oli ensimmäisen massatuotannon henkilökohtaisen tietokoneen nimi?

8. Kolmannen sukupolven tietokoneiden alkuainekanta olivat

1. mikroprosessorit
2. transistorit
3. integroidut piirit
4. tyhjiöputket
5. sähkömekaaninen rele

9. Mitä informatisointi on?

1. tietokoneohjelmisto
2. asiakirjojen valmistelutekniikka
3. joukko menetelmiä ja tekniikoita tiedon tallentamiseksi, lähettämiseksi ja käsittelemiseksi
4. tietovälineiden ja -tekniikoiden luomis-, kehitys- ja massasovellusprosessi
5. tietokannan ohjausjärjestelmä

10. Tietoyhteiskunta on nimeltään:

1. kansallisten julkisten instituutioiden järjestelmä
2. Internetin käyttäjiä
3. verkko, joka yhdistää useita paikallisia verkkoja sekä yksittäisiä tietokoneita
4. yhteiskunnan kehitysvaihe, jossa tiedosta tulee ihmisten työtoiminnan pääkohde
5. yhteiskunta, jolle on ominaista korkea avoimuus ja tiedon saatavuus instituutioiden, järjestöjen, virkamiesten jne. toiminnasta. julkista tietoa ja keskustelua varten

11. Mikä seuraavista EI koske informatisoinnin tavoitteita?

1. tietotuki ihmisten aktiiviseen virkistykseen ja vapaa-aikaan
2. ihmisten tietotarpeiden muodostuminen ja kehittäminen
3. edellytysten muodostuminen, jotka varmistavat informatisoinnin toteuttamisen
4. tietotuki kaikentyyppisille toimille
5. kaikkien tietoresurssien siirtäminen digitaaliseen muotoon

12. Kansallisia tietolähteitä ovat mm

1. lääketieteelliset laitokset
2. kirjaston ja arkiston kokoelmia
3. yliopistot, instituutit, akatemiat
4. kaasu, öljy
5. julkisia järjestöjä

13. SE EI koske tietoturvatoimenpiteitä

1. tekniset toimenpiteet tietokonerikoksilta suojaamiseksi
2. oikeudelliset toimenpiteet tietokonerikoksilta suojaamiseksi
3. teknologioiden kehittäminen turvallisten automaattisten tietojenkäsittelyjärjestelmien luomiseksi
4. turvallisuusmääräysten noudattaminen työskennellessäsi tietokoneen kanssa
5. hallinnolliset toimenpiteet tietokonerikoksilta suojaamiseksi

14. Suora viestintälinja lähettää

1. ohjauskomennot ja tiedot ohjausobjektista
2. tietoa ohjausobjektin tilasta
3. tietoa ohjausjärjestelmän tilasta
4. ohjauskomennot
5. ohjauskomennot ja tiedot ohjausjärjestelmästä

15. Mikä objekteista voi olla algoritmien suorittaja?

16. Algoritmeja, jotka ratkaisevat jonkin päätehtävän alitehtävän ja jotka pääsääntöisesti suoritetaan toistuvasti, kutsutaan:

1. syklinen
2. apu
3. lineaarinen
4. pää
5. haarautuminen

Lue myös: Mitä asiakirjoja on toimitettava irtisanomisen yhteydessä?

17. Algoritmia kutsutaan lineaariseksi:

1. jos sen suorittamisen kulku riippuu tiettyjen ehtojen totuudesta
2. jos sen suorittamiseen liittyy samoja operaatioita toistuvasti
3. jos toiminnot suoritetaan niiden luonnollisessa järjestyksessä peräkkäin, ehdoista riippumatta
4. jos esitämme sen taulukkomuodossa
5. jos toiminnot suoritetaan alusta loppuun

18. Algoritmin ymmärrettävyys tarkoittaa, että se tulee kirjoittaa käyttämällä:

1. komennot ovat algoritmin luojan ymmärtämiä
2. komennot suorittajan komentojärjestelmästä
3. algoritmin käyttäjän ymmärtämät komennot
4. tietokoneella luettavat komennot
5. ohjelmointikielen operaattorit

19. Algoritmin äärellisyys tarkoittaa, että:

1. sen tulee sisältää tulostulostusoperaattori
2. sen täytyy ratkaista laskennallinen ongelma
3. sen tulee sisältää avainsana, joka ilmaisee algoritmin päättymisen
4. sen on sovelluttava kaikkien tietyntyyppisten ongelmien ratkaisemiseen
5. tulos on saatava äärellisessä määrässä vaiheita

20. Mikä on määritelmää vastaavan algoritmin ominaisuuden nimi: "Algoritmi on kirjoitettava komennoista, jotka ovat esittäjän ymmärtämiä, jokaisen komennon tulee määrittää suorittajan yksiselitteinen toiminta"?

1. massahahmo
2. tarkkuus
3. raaja
4. selkeys
5. diskreetti

21. Algoritmi on

1. äärellinen käskyjoukko, joka määrittää ongelman ratkaisun äärellisen määrän operaatioita
2. tiettyjen toimien suorittamista koskevat säännöt
3. tietokoneen komentosarja
4. tietokoneverkkoprotokolla
5. ohjaamalla esiintyjää suorittamaan toimintosarja

22. Voit kirjoittaa sen laskentataulukon soluun.

1. vain kaava
2. vain numero tai teksti
3. vain numero
4. numero, kaava tai teksti
5. kaavio

23. Laskentataulukon solualue on

1. monet solut muodostavat mielivaltaisen muodon alueen
2. monet täytetyt ET-solut
3. monia tyhjiä ET-soluja
4. monet solut muodostavat suorakaiteen muotoisen alueen
5. monet solut muodostavat neliön muotoisen alueen

24. Kuinka monta solua on solualueella A5:D8?

25. ET-solua kutsutaan nykyiseksi if

1. solu näkyy näytöllä
2. se sisältää tietoa
3. solu on tyhjä
4. solu sisältää kaavan
5. se sisältää kohdistimen

26. Laskentataulukon solun osoite on

1. nimi, joka koostuu merkkijonosta
2. nimi, joka koostuu sarakkeen nimestä ja rivin numerosta
3. solulle varatun RAM-tavun osoite
4. solulle varatun RAM:n konesanan osoite
5. solulle varattu RAM-tavumäärä

27. Mikä on binäärilukujen 110110 ja 101 summa?

28. Seuraava väite on virheellinen:

1. tietue sisältää useita kenttiä
2. kenttä sisältää useita merkintöjä
3. Jokaisella tietokantakentällä on oma kokonsa
4. Tietokannan rakenne on jäykkä
5. jokaisella kentällä on nimi

29. Tietokannan rakenne muuttuu, jos

1. lisää/poista kenttä
2. muokkaa merkintää
3. vaihtaa merkintöjä
4. Lisää merkintä
5. poista merkintä

30. Relaatiotietokannassa tiedot järjestetään muotoon

1. hierarkinen rakenne
2. tiedosto
3. puu
4. suorakaiteen muotoinen pöytä

31. Mikä tekee tietokoneen yhdistämisestä maailmanlaajuiseen verkkoon mahdotonta:

1. Tietokoneen tyyppi
2. Oheislaitteiden kokoonpano
3. Ei levykeasemaa
4. Ei verkkokorttia

32. Tietoliikennekanavia käytetään yleensä tietokoneverkoissa:

1. Johdot
2. Kaapelit
3. Radioviestintä
4. Kaikki yllä oleva

33. Tietokoneviestinnän tehokkuus riippuu yleensä:

1. Kaistanleveys
2. CPU:n suorituskyky
3. Muistin kapasiteetti
4. Kaikki yllä oleva

34. Laitetta, joka muuntaa analogiset signaalit digitaalisiksi signaaleiksi ja päinvastoin, kutsutaan:

35. Kaukoetäisyydellä sijaitsevien tietokoneiden ja paikallisten verkkojen yhdistämistä maailman tietoresurssien yhteistä käyttöä varten kutsutaan.

1. paikalliseen verkkoon
2. maailmanlaajuinen verkosto
3. yritysverkosto
4. alueellinen verkko

36. Paikallisverkot käyttävät:

1. Johdot ja kaapelit
2. Puhelinlinjat
3. Elektroniset putket
4. Kristalli

37. World Wide Web on järjestelmä maailmanlaajuisessa verkossa, jota kutsutaan nimellä:

38. Protokollat ​​ovat...

1. erikoistyökaluja, jotka mahdollistavat käyttäjien viestinnän reaaliaikaisen organisoinnin tietokoneviestintäkanavien kautta
2. säännöstö, joka säätelee tiedonvaihtoa verkossa
3. sähköinen tiedonsiirtojärjestelmä, jonka avulla jokainen verkon käyttäjä pääsee käsiksi etätietokoneeseen tallennettuihin ohjelmiin ja asiakirjoihin

39. Selain on...

1. tietojärjestelmä, jonka pääkomponentit ovat hypertekstidokumentteja
2. nettiselain
3. Internet-palvelu, jonka avulla voit vaihtaa sähköisiä viestejä tietokoneiden välillä verkon kautta

40. Sähköpostiosoite tallennetaan tiettyjen sääntöjen mukaisesti. Poista tarpeettomat asiat

1. petrov_yandex.ru
2. [sähköposti suojattu]
3. [sähköposti suojattu]

Tietojenkäsittelytieteen lopputesti aiheesta "Ohjaus ja algoritmit" (luokka 9)

Mikä on CYBERNETICS?

tietojenkäsittelytieteen ala, jonka tarkoituksena on älykkäiden järjestelmien kehittäminen; tiede, joka tutkii tiedon siirto-, tallennus- ja käsittelymenetelmiä tietokoneen avulla;

tiede elävien ja elottomien järjestelmien hallinnasta;

Tiede älyllisen kognitiivisen toiminnan muodoista, menetelmistä ja laeista loogisen kielen avulla formalisoituna;

biotiede, yksi luonnontieteistä, jonka aiheena on elävät olennot ja niiden vuorovaikutus ympäristön kanssa.

Lue myös: Valtionveron palautus välimiesoikeudessa hylättyjen kanteiden yhteydessä

Kuka perusti CYBERNETICSin?

unkarilais-saksalainen matemaatikko John von Neumann;

kreikkalainen filosofi Platon;

ranskalainen fyysikko André Ampère;

venäläinen tiedemies Vladislav Zakrevsky;

Amerikkalainen matemaatikko Norbert Wiener.

Mistä elementeistä jokainen ohjausjärjestelmä koostuu kybernetiikan näkökulmasta?

palautekanava;

16+ Mediarekisteröintitodistus:
El-nro FS77-60625, päivätty 20. tammikuuta 2015.

Lupa koulutustoiminnan harjoittamiseen: nro 5201, 20.5.2016.

Toimitus- ja julkaisuosoite: 214011, Venäjän federaatio,
Smolensk, st. Verkhne-Sennaya, 4.
Yhteystiedot: [sähköposti suojattu]

INFOUROC-tavaramerkin tekijänoikeuden haltija: Infourok LLC (sertifikaatti nro 581999)

Kaikki sivustolle lähetetyt materiaalit ovat sivuston kirjoittajien luomia tai sivuston käyttäjien lähettämiä, ja ne esitetään sivustolla vain tiedoksi. Materiaalin tekijänoikeudet kuuluvat niiden laillisille tekijöille. Sivuston materiaalin osittainen tai täydellinen kopioiminen ilman sivuston hallinnon kirjallista lupaa on kielletty! Toimituksellinen mielipide voi olla erilainen kuin kirjoittajien.

Vastuu materiaaliin ja niiden sisältöön liittyvien kiistanalaisten ongelmien ratkaisemisesta on materiaalin sivustolle lähettäneillä käyttäjillä. Sivuston toimittajat ovat kuitenkin valmiita antamaan kaiken mahdollisen tuen sivuston työhön ja sisältöön liittyvien ongelmien ratkaisemisessa. Jos huomaat, että tällä sivustolla käytetään materiaalia laittomasti, ilmoita siitä sivuston ylläpitäjälle palautelomakkeella.

1. Mikä on algoritmin ominaisuuden nimi?
a) selkeys
b) varmuus
c) tehokkuus
d) massaosallistuminen
2. Mikä on algoritmin ominaisuuden nimi, joka tarkoittaa, että se johtaa aina tulokseen äärellisen, mahdollisesti erittäin suuren askelmäärän jälkeen?
a) diskreetti
b) ymmärrettävyys
c) tehokkuus
d) massaosallistuminen
3. Mikä on algoritmin ominaisuuden nimi, mikä tarkoittaa, että se määritellään sellaisilla käskyillä, jotka suorittaja voi havaita ja joiden mukaan hän voi suorittaa vaaditut toiminnot?
a) diskreetti
b) ymmärrettävyys
c) varmuus
d) massaosallistuminen
4. Mikä on algoritmin ominaisuuden nimi, joka tarkoittaa, että ongelman ratkaisu on jaettu erillisiin vaiheisiin?
a) diskreetti
b) varmuus
c) tehokkuus
d) massaosallistuminen
5. Mikä on algoritmin ominaisuuden nimi, joka tarkoittaa, että ongelman ratkaisupolku on täysin yksiselitteisesti määritelty, eikä epäselvyyksiä tai pois jättämistä sallita missään vaiheessa?
a) diskreetti
b) ymmärrettävyys
c) varmuus
d) tehokkuus

Vahvistetut vastaukset sisältävät luotettavaa tietoa. “Knowledgesta” löydät miljoonia käyttäjien itsensä parhaiksi merkitsemiä ratkaisuja, mutta vain asiantuntijoidemme vastauksen tarkistaminen takaa sen oikeellisuuden.

Vastataan kysymyksiin aiheesta "Algoritmin ominaisuudet":

Ennen kuin vastaat testikysymyksiin, muistetaan algoritmin ominaisuudet:

1. Ymmärrettävyys— komentojen sisältö, jonka esiintyjä ymmärtää;
2. Varmuutta— tulos määräytyy yksiselitteisesti lähtötietojen perusteella, jokainen algoritmin vaihe on tarkasti määritelty.
3. Tehokkuus— tuloksen saaminen äärellisellä määrällä vaiheita.
4. Massahahmo— tällaisten ongelmien ratkaisemiseen voidaan käyttää tiettyä algoritmia.
5. Diskreetti— algoritmin jakaminen peräkkäisiin toimintoihin (vaiheisiin).
6. Tarkkuus— Kaikki komennot on ymmärrettävä selvästi (yksiselitteisesti).

Kysymys nro 1
Mikä on algoritmin ominaisuuden nimi, joka tarkoittaa, että algoritmia voidaan soveltaa ratkaista koko luokan ongelmia ?
a) ymmärrettävyys;
b) varmuus;
c) tehokkuus;
G) massahahmo— tiettyä algoritmia voidaan käyttää ratkaisemaan koko luokan samanlaisia ​​ongelmia .
VASTAUS: D) MASSIIVISUUS

Kysymys nro 2
Mikä on algoritmin ominaisuuden nimi, joka tarkoittaa, että se aina johtaa tulos finaaliin asti. ehkä erittäin suuri vaiheiden määrä ?
a) diskreetti;
b) ymmärrettävyys;
c) tehokkuus - tulosten saaminen kautta rajallinen määrä askeleita ;
d) massaosallistuminen.
VASTAUS: B) SUORITUSKYKY .

Kysymys #3
Mikä on algoritmin ominaisuuden nimi, joka tarkoittaa, että se määritellään sellaisilla käskyillä, että esiintyjä voi havaita ja minkä mukaan voi suorittaa vaaditut toimenpiteet ?
a) diskreetti;
b) selkeys- sisältö komennot esittäjälle ymmärrettäviä ;
c) varmuus;
d) massaosallistuminen.
VASTAUS: B) RAJOITUS.

Kysymys nro 4
Mikä on algoritmin ominaisuuden nimi, joka tarkoittaa sitä tapa ratkaista ongelma on jaettu erillisiin vaiheisiin ?
a) diskreetti - erottelu algoritmi peräkkäiseen Toiminnot (Askeleet);
b) varmuus;
c) tehokkuus
d) massaosallistuminen
VASTAUS: A) HYVÄSTI

Kysymys nro 5
Mikä on algoritmin ominaisuuden nimi, joka tarkoittaa ratkaisupolku tehtäviä määritelty melko ehdottomasti. Eikö epäselvyyksiä tai puutteita sallita missään vaiheessa?
a) diskreetti;
b) ymmärrettävyys;
V) varmuutta— tulos määräytyy yksiselitteisesti lähtötietojen perusteella, jokainen algoritmin vaihe on tarkasti määritelty;
d) tehokkuus.
VASTAUS: B) MÄÄRITYS.

Ilmainen apu kotitehtäviin

Johdatus algoritmin käsitteeseen

Algoritmin käsite

Nyky-yhteiskunnassa sana "algoritmi" on niin laajalle levinnyt, että useimmat ihmiset ymmärtävät sen intuitiivisesti. Sillä tarkoitamme mitä tahansa vaihesarjaa tietyn tavoitteen saavuttamiseksi. Teoreettiselle tieteelle "algoritmin" käsite on kuitenkin melko monimutkainen.