Algoritmide omadused

Eespool toodud algoritmi definitsiooni ei saa pidada rangeks – pole päris selge, mis on “täpne ettekirjutus” või “nõutud tulemuse tagav tegevuste jada”. Seetõttu on tavaliselt sõnastatud mitmed algoritmide üldised omadused, et eristada algoritme teistest juhistest.

Need omadused on:

Diskreetsus (katkestavus, eraldatus) - algoritm peab kujutama probleemi lahendamise protsessi lihtsate (või eelnevalt määratletud) sammude järjestikuse täitmisena. Iga algoritmi pakutav toiming täidetakse alles pärast seda, kui eelmine on täitmise lõpetanud.

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

Efektiivsus (lõplikkus) – algoritm peab viima ülesande lahendamiseni piiratud arvu sammudega.

Masskaala - probleemi lahendamise algoritm on välja töötatud üldisel kujul, see tähendab, et 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.

Aritmeetiliste toimingute või geomeetriliste konstruktsioonide sooritamise reeglid on algoritmid. Samas jääb vastuseta küsimus: kuidas algoritmi mõiste erineb sellistest mõistetest nagu “meetod”, “meetod”, “reegel”. Võib isegi kohata väidet, et sõnad “algoritm”, “meetod”, “reegel” väljendavad sama asja (st need on sünonüümid), kuigi selline väide läheb ilmselgelt vastuollu “algoritmi omadustega”.

Väljend "algoritmi omadused" ei ole täiesti õige. Objektiivselt olemasolevatel reaalsustel on omadused. Võime rääkida näiteks aine omadustest. Algoritm on kunstlik struktuur, mille ehitame oma eesmärkide saavutamiseks. Et algoritm oma eesmärki täidaks, peab see olema üles ehitatud teatud reeglite järgi. Seetõttu peame rääkima mitte algoritmi omadustest, vaid algoritmi koostamise reeglitest või algoritmile esitatavatest nõuetest.

Algoritmide koostamise reeglid

Esimene reegel on see, et algoritmi koostamisel on kõigepealt vaja määrata objektide komplekt, millega algoritm töötab. Nende objektide formaliseeritud (kodeeritud) esitust nimetatakse andmeteks. Algoritm hakkab töötama teatud andmehulgaga, mida nimetatakse sisendiks ja oma töö tulemusena toodab andmeid, mida nimetatakse väljundiks. Seega teisendab algoritm sisendandmed väljundandmeteks.

See reegel võimaldab teil kohe eraldada algoritmid "meetoditest" ja "meetoditest". Kuni me pole sisendandmeid vormistanud, ei saa me algoritmi koostada.

Teine reegel on see, et algoritm nõuab töötamiseks mälu. Mällu salvestatakse sisendandmed, millega algoritm tööle hakkab, vaheandmed ja väljundandmed, mis on algoritmi tulemus. Mälu on diskreetne, s.t. mis koosneb üksikutest rakkudest. Nimega mälukohta nimetatakse muutujaks. Algoritmide teoorias ei ole mälumahud piiratud, st usutakse, et suudame algoritmi varustada mis tahes tööks vajaliku mälumahuga.

Koolis "algoritmide teooria" neid kahte reeglit ei arvestata. Samal ajal algab nende reeglite rakendamisega praktiline töö algoritmidega (programmeerimine). Programmeerimiskeeltes teostavad mälu eraldamist deklaratiivsed operaatorid (muutuvad deklaratsiooni operaatorid).

Kolmas reegel on diskreetsus. Algoritm on üles ehitatud üksikutest sammudest (toimingud, toimingud, käsud). Algoritmi moodustavad muidugi palju samme.

Neljas reegel on determinism. Pärast iga sammu peate märkima, milline samm järgmisena sooritatakse, või andma stop-käskluse.

Viies reegel on konvergents (efektiivsus). Algoritm peab lõppema pärast piiratud arvu samme. Sel juhul on vaja näidata, mida peetakse algoritmi tulemuseks.

Niisiis, algoritm on algoritmide teoorias määratlemata mõiste. Algoritm seob iga konkreetse sisendandmete komplekti teatud väljundandmete komplektiga, st arvutab (rakestab) funktsiooni. Algoritmide teooria spetsiifiliste küsimuste käsitlemisel peame alati silmas mõnda konkreetset algoritmi mudelit.

Sõna tähendus algoritm väga sarnane sõnade tähendusega retsept,juhiseid. Kuid igal algoritmil, erinevalt retseptist või meetodist, on tingimata järgmised omadused.

1. Algoritmi täitmine on jagatud lõpetatud toimingute-sammude jadaks. Alles pärast ühe toimingu (käsu) täitmist saate hakata täitma järgmist. Seda algoritmi omadust nimetatakse diskreetsus. Iga üksiktoimingu sooritamiseks antakse täitjale korraldus algoritmikirjes (käskluses) oleva spetsiaalse juhisega.

2. Arusaadavus- algoritm ei tohiks sisaldada juhiseid, mille tähendust saab esitaja mitmeti mõistetavalt tajuda, s.t. algoritmi salvestamine peaks olema nii selge ja täielik, et esinejal ei oleks vajadust teha iseseisvaid otsuseid. Algoritm on alati loodud „mittemõtlevale“ esitajale täitmiseks. Algoritm koosneb SKI-s sisalduvatest käskudest.

Vaatleme "igapäevase" algoritmi tuntud näidet - tänavaületusalgoritmi: "Vaadake vasakule. Kui autosid pole, kõndige tänava keskele. Kui on, oodake, kuni need mööduvad jne. Kujutage ette olukorda: vasakul on auto, kuid see ei liigu - selle rehvi vahetatakse. Kui arvate, et algoritmi täitja peab ootama, siis saate sellest algoritmist aru. Kui otsustate, et tänavat on võimalik ületada, pidades algoritmi korrigeerituks ettenägematute (teie arvates!) asjaolude tõttu, siis pole te algoritmi mõistet valdanud.

3. Determinism (kindlus ja kindlus). Algoritmi iga käsk määrab täitja üheselt mõistetava toimingu ning üheselt peab olema määratud, milline käsk järgmisena täidetakse. See tähendab, et kui algoritmi rakendatakse korduvalt samale lähteandmete kogumile, on selle vastuvõetav väljund iga kord sama tulemus.

4. Tõhusus- algoritmi täitmine peab olema lõpule viidud piiratud arvu etappidega ja saada ülesande lahendamise tulemus. Üheks võimalikuks tulemuseks võib olla tõsiasja tuvastamine, et probleemil pole lahendusi.

Tõhususe omadus sisaldab omadust jäsemed- algoritmi lõpuleviimine piiratud arvu etappidega.

5. Massi iseloom- algoritm sobib mistahes ülesande lahendamiseks teatud ülesannete klassist, s.t. algoritm töötab õigesti teatud lähteandmete kogumi puhul, mida nimetatakse algoritmi rakendusalaks.

Massilise iseloomu omadus määrab pigem algoritmi kvaliteedi, mitte ei kuulu kohustuslike omaduste hulka (nagu diskreetsus, arusaadavus jne). On algoritme, mille rakendusala on piiratud ühe sisendandmete komplektiga või isegi nende puudumisega (näiteks arvu p kindla arvu õigete numbrite saamine). Õigem on öelda, et algoritm peaks olema rakendatav mis tahes selle definitsioonipiirkonna andmetele ja sõnale massiline tegelane ei sobi alati sellise omaduse kirjeldamiseks.

Algoritmi kontseptsioon

Ülaltoodut kokku võttes sõnastame järgmise kontseptsioon algoritm.

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

Ülaltoodud definitsioon ei ole definitsioon selle sõna matemaatilises tähenduses, s.t. see ei ole formaalne definitsioon (algoritmi formaalset definitsiooni vt artiklist " Algoritmide teooria”).

Pange tähele, et iga esineja lubatavate toimingute kogum (SAC) on alati piiratud - ei saa olla täitjat, kelle jaoks mõni toiming on lubatud. I. Kanti parafraseeritud arutluskäik põhjendab sõnastatud väidet järgmiselt: „Kui selline esitaja oleks olemas, siis oleks tema lubatavate tegude hulgas ka kivi loomine, mida ta tõsta ei saa. Kuid see on vastuolus tegevuse "Tõstke iga kivi" lubatavusega.

Huvitav on see, et on probleeme, mida inimene saab üldiselt lahendada, teadmata selle lahendamise algoritmi. Näiteks on inimesel ees fotod kassidest ja koertest. Ülesanne on kindlaks teha, kas konkreetne foto on kass või koer. Inimene lahendab selle probleemi, kuid algoritmi kirjutamine selle probleemi lahendamiseks on endiselt äärmiselt keeruline.

Teisest küljest on probleeme, mille lahendamiseks on üldiselt võimatu konstrueerida lahendusprotseduuri. Pealegi saab seda fakti rangelt tõestada. Selle kohta saate lugeda artiklist " Algoritmiliselt lahendamatud probleemid” 2.

Graafiline viis algoritmi kirjeldamiseks

3.Mis on joonisel kujutatud ploki sümboli nimi? ?

4.Mis on joonisel kujutatud ploki sümboli nimi? ?

5.Mis on joonisel kujutatud ploki sümboli nimi? ?

Võrrelge plokkskeemides kasutatavaid sümboleid ja nende eesmärki

a) b) c) d) e)

Valige vaste kõigi 5 vastusevariandi jaoks:

1) otsustusplokk (tingimuste kontrollimine)

2) Algoritmi alguse ja lõpu plokk

3) andmete kirjeldamise plokk

4) andmetöötlusplokk (toimingu täitmine)

5) muutmisplokk

8. Algoritm, mis hõlmab probleemi lahendamiseks teatud toimingute jada kordamist, on järgmine:

9. Koguseid, mille väärtused algoritmi täitmise ajal muutuvad, nimetatakse:

10. Mis tüüpi algoritm on algoritm, mis on kirjutatud algoritmilises keeles, kasutades järgmist konstruktsiooni:

KUI - SIIS - MUUD - KÕIK

11. Mis tüüpi algoritm on algoritm, mis on kirjutatud algoritmilises keeles, kasutades järgmist konstruktsiooni:

NC BYE tingimus

Silmuskorpus

12. Mis tüüpi algoritm on algoritm, mis on kirjutatud algoritmilises keeles, kasutades järgmist konstruktsiooni:

NC FOR i ALT i1 KUNI i2

Silmuskorpus

13. Lineaarse algoritmi fragment on antud:

b:=5+2*a

a:=b/5*a

Mis on muutuja a väärtus pärast selle täitmist?

Vigade tuvastamist ja nende kõrvaldamist nimetatakse...

Eraldi juhendamine esinejale on...

Toimingute korraldamise vormi, kus sama käsuplokki täidetakse mitu korda, nimetatakse ...

Vooskeem on...

Millise toimingu kommentaariplokk määratleb?

20. Vooskeemis on algoritmi algus ja lõpp näidatud joonisega:

a) b) c) d) e)

21. Vooskeemis on algoritmi toiming tähistatud joonisega:

a) b) c) d) e)

22. Plokkskeemil tähistatakse tingimust joonisega:

a) b) c) d) e)

23. Plokkskeemil on andmete väljund ja sisend tähistatud joonisega:

a) b) c) d) e)

24. Algoritmi kindlus tähendab:

25. Algoritmi tõhusus tähendab:

26. Algoritmi massiline olemus tähendab:

27. Algoritmi diskreetsus tähendab:

28. Algoritmi lõplikkus tähendab:

29. Algoritmi omadus “diskreetsus” tähendab:

64. Algoritmi omadus "tõhusus" tähendab:

Mida tähendab algoritmi omaduse nimi see algoritm viib tulemuseni alati pärast piiratud arvu samme

Kuidas nimetatakse algoritmi omadust, mis tähendab, et see on täpsustatud selliste juhiste abil, mida teostaja tajub ja mille järgi saab teha vajalikke toiminguid?

Kuidas nimetatakse algoritmi omadust, mis tähendab, et tee ülesande lahendamiseni on jagatud eraldi sammudeks?

Igaüks meist lahendab pidevalt palju probleeme: kuidas kiiremini tööle saada, kuidas kõige paremini planeerida jooksvaid asju ja palju muud. Iga probleemi lahendus on alati jagatud lihtsateks toiminguteks, millest algoritm koosneb.

Algoritm- on mis tahes toimingute jada, mis viib antud probleemi lahendamiseni.

Sõna "algoritm" ilmus keskajal, kui eurooplased said tuttavaks usbeki matemaatiku Muhammad bin Musa al-Khwarizmi ("al-Khwarizmi" on isik kümnendarvusüsteemis) aritmeetiliste toimingute sooritamise meetoditega. Khorezmi linn, praegu Usbekistani Horezmi oblastis Khiva). Sõna "algoritm" on sõnade "al-Khwarizmi" euroopaliku häälduse tulemus.

Algoritmi iseloomustavad järgmised omadused: diskreetsus, massi iseloom, kindlus, efektiivsus.

Diskreetsus on omadus, mis tähendab järgmist: iga algoritm koosneb üksikutest lõpetatud toimingutest, st "jagatud sammudeks".

Massi iseloom- algoritmi rakendatavus kõigi seda tüüpi probleemide puhul, mida algandmete puhul käsitletakse.

Kindlus- algoritmi omadus, mis seisneb üksikute sammude sisu ja täitmise järjekorra ranges määramises.

Tõhusus- omadus, et iga algoritm peab lõpliku arvu sammudega lahenduse leidma.

Algoritmide kirjeldamiseks on mitu võimalust: sõnaline kirjeldus, vooskeem, algoritmiline keel ja programm.

Verbaalne kirjeldus kujutab loomulikus keeles algoritmi struktuuri. Näiteks igal kodumasinal (raud, elektrisaag, trell jne) on kasutusjuhend ehk suuline kirjeldus algoritmist, mille järgi seda seadet kasutada tuleks.

Algoritm on kirjutatud vabas vormis loomulikus keeles, näiteks vene keeles. See kirjeldamismeetod ei ole laialt levinud, kuna see ei ole rangelt formaliseeritud, võimaldab mõne tegevuse kirjeldamisel tõlgendada mitmeti mõistetavat ja kannatab paljusõnalisuse all.

Plokkskeem- algoritmi ülesehituse kirjeldus, kasutades geomeetrilisi kujundeid koos ühendusjoontega, mis näitavad üksikute käskude täitmise järjekorda. Sellel meetodil on mitmeid eeliseid. Tänu oma selgusele tagab see algoritmi “loetavuse” ja kuvab selgelt üksikute käskude täitmise järjekorra. Plokkskeemis vastab iga formaalne kujundus konkreetsele geomeetrilisele joonisele või joontega ühendatud jooniste komplektile. Plokkskeemide koostamiseks kasutatavad põhilised geomeetrilised kujundid hõlmavad järgmist.

Iseloomulikud plokid algust Ja lõppu algoritm:

Blokeeri kuvamine protsess (operaator), mõeldud üksikute toimingute kirjeldamiseks:

Kirjeldusplokk silmus parameetriga:

Blokeeri I/O mis tahes andmekandjalt:

Algoritmi kirjeldus verbaalses vormis või vooskeemi kujul võimaldab käskude kujutamisel mõningast meelevaldsust. Samal ajal võimaldab see inimesel hõlpsasti mõista asja olemust ja täita algoritmi.

Algoritmiline keel viidatud kui pseudokood, on algoritmide salvestamine, sarnaselt loomulikus ja programmeerimiskeeles algoritmi kirjutamisega. Algoritmi kirjeldamisel pseudokoodis kasutatakse järgmisi konstruktsioone:

np- tsükli algus; kp_ - tsükli lõpp; Sest- silmus parameetriga; Kui- seisund; siis on tingimuse täitmise tulemus; muidu- tingimuse täitmata jätmise tulemus; Kõik- seisukorra lõpp; Hüvasti- silmuse seisund.

Vaatame kolme peamise algoritmitüübi plokkskeemide näiteid: lineaarne, hargnev ja tsükliline. Lineaarne on algoritm, milles kõik ülesande lahendamise etapid viiakse läbi rangelt järjestikku.

Lineaarse algoritmi vooskeem täisnurkse kolmnurga perimeetri leidmiseks R teadaolevate jalgade pikkusega a, b näidatud joonisel fig. 5.1.

Hargnemine algoritm on algoritm, milles on valitud üks arvutusprotsessi mitmest võimalikust teest. Iga sellist teed nimetatakse algoritmi haruks. Hargnemisalgoritmi märk on tingimuse olemasolu.

Seal on puudulikud (kui-siis) ja täielik (kui-siis-muidu) hargnemise tüübid.

Mittetäielik hargnemine eeldab väite olemasolu ainult ühel harul (see; jah; tõsi), teisel harul operaatorit pole ja juhtimine läheb kohe üle liitmispunkti

Täielik hargnemine võimaldab korraldada algoritmis kahte haru (See või muidu; Jah või Ei; Tõsi või valetab), millest igaüks viib nende ühinemise ühise punktini (joon. 5.26).

tsükliline, või lihtsalt tsükkel, on algoritm, mille puhul tulemus saadakse samu toiminguid korduvalt sooritades. Korduvate operatsioonide rühma nimetatakse tsükli keha.

Laialdaselt kasutatakse kolme tüüpi silmuseid: parameetriga silmus, eeltingimusega silmus ja järeltingimusega silmus.

Parameetriga tsüklit kasutatakse juhtudel, kui väärtus on teada k, st tsükli elementide või sammude arv.

Tsükli sammude arv eeltingimusega ei ole ette määratud. Esmalt kontrollib, kas tingimus on täidetud. Kui see Tõsi (jah) siis käivitatakse tsükli keha, misjärel kontrollitakse uuesti tingimust. Määratud toiminguid kontrollitakse seni, kuni tingimus on hinnatud Vale (ei).

Tsükkel järeltingimustega erineb eeltingimusega tsüklist tingimuse asukoha poolest ja selle poolest, et silmuse keha täidetakse alati vähemalt korra. Selle tsükli põhiosa täidetakse kuni tingimuseni Vale (ei).

Tootlikkuse ja töökvaliteedi parandamiseks on igal programmeerimiskeelel struktureeritud andmetüüp - massiivi.

Massiiv on järjestatud kogum sama tüüpi üldnimetust omavatest kogustest, mille elemente eristavad seerianumbrid, mida nimetatakse indeksiteks.