Az algoritmizmus alapjai
1. Az algoritmus fogalma és tulajdonságai
2. Az algoritmusok leírásának módszerei
3. Alapvető szerkezeti algoritmikus konstrukciók
4. Hivatkozások
Bármilyen algoritmus önmagában nem létezik, hanem egy adott művész (ember, robot, számítógép, programozási nyelv stb.) Számára készült. Az a tulajdonság, amely bármelyik művészt jellemzi, az, hogy tudja, hogyan kell végrehajtani bizonyos parancsokat. Az adott végrehajtó által végrehajtott parancsok halmaza az előadó parancsrendszerének nevezhető. Az algoritmust a végrehajtó utasításai írják le, amelyek végrehajtják azt. Az objektumok, amelyek fölött az előadó képes cselekvéseket végrehajtani, az úgynevezett végrehajtó környezetet alkotnak. A forrásadatok és az algoritmusok eredményei mindig a végrehajtó azon közegéhez tartoznak, akinek az algoritmust szándékolták.
Az "algoritmus" szó jelentése nagyon hasonlít a "recept", "módszer", "folyamat" szavak jelentéséhez. A recept vagy eljárás ellentétben azonban az algoritmust a következő tulajdonságok jellemzik: diszkrétség, hatékonyság, bizonyosság, hatékonyság, formalitás.
A diszkrétség (a folytonosság ellentétes volta) a szerkezetét jellemző algoritmus tulajdonsága: minden egyes algoritmus különálló befejezett cselekvésekből áll, mondván: "lépcsőkre osztva".
Tömeg - az algoritmus alkalmazhatósága a vizsgált típus minden problémájára, minden kezdeti adat esetében. Például a kvadratikus egyenletnek az igazi tartományban történő megoldására szolgáló algoritmusnak tartalmaznia kell az oldat összes lehetséges kimenetelét, azaz a diszkriminanciaértékeket figyelembe véve az algoritmus az egyenletnek két különböző gyökereit találja meg, vagy két egyenlő, vagy arra következtet, hogy nincsenek valódi gyökerek.
A megbízhatóság (determinizmus, pontosság) az algoritmus tulajdonsága, jelezve, hogy az algoritmus minden lépését szigorúan meg kell határozni, és nem tesz lehetővé különböző értelmezéseket; Ezenkívül az egyes lépések sorrendjét szigorúan meg kell határozni. Emlékszel a mesera Ivan Tsarevicsről? "Herceg Iván az úton haladt, elért a villához. Lát egy nagy kőt, amelyen egy felirat van rajta: "Egyenesen előre fogsz menni, el fogja veszíteni a fejét, jobbra fogsz menni, megtalálod a feleségedet, balra mensz, gazdagodni fogsz." Ivan áll, és azt hiszi, mit tegyen. Az ilyen algoritmusok nem tartalmazhatnak ilyen utasításokat.
Az eredményesség olyan tulajdonság, amelyet bármelyik algoritmusnak véges (esetleg nagyon nagy) lépésekkel kell végződnie. A végtelen algoritmusok megfontolásának kérdése az algoritmusok elméletének keretein kívül marad.
Formalitás - ez a tulajdonság azt jelzi, hogy minden olyan előadóművész, aki érzékeli és végrehajtja az algoritmus utasításait, formálisan jár el. A feladat tartalmától elvonva, és csak szigorúan megfelel az utasításoknak. A "mi, hogyan és miért?" Érvelése Ha az algoritmus fejlesztője és az előadó formálisan (gondolkodás nélkül) felváltva végrehajtja a javasolt parancsokat, és megkapja a kívánt eredményt.
Vegye figyelembe az algoritmus leírásának alábbi módjait: verbális leírás, pszeudokód, blokkdiagram, program.
A verbális leírás az algoritmus struktúráját jelenti a természetes nyelvben. Például minden háztartási készülék (vasaló, elektromos fűrész, fúró stb.) Tartalmaz egy használati utasítást, pl. az algoritmus szóbeli leírása, amely szerint ezt az eszközt kell használni.
Nincsenek szabályok szóbeli leírás készítésére. Az algoritmus tetszőleges formában íródott természetes, például orosz nyelven. Így leírására nem elterjedt, mivel nem szigorúan hivatalossá (a „formális” azt jelenti, hogy a leírás teljesen komplett és figyelembe veszi az összes lehetséges helyzeteket, amelyek során felmerülhet az ítélet); lehetővé teszi az egyes tevékenységek értelmezésének kétértelműségét; szenved a verbositástól.
Pseudocode - az algoritmus struktúrájának leírása egy természetes, részlegesen formalizált nyelven, amely lehetővé teszi számunkra, hogy azonosítsuk a probléma megoldásának fő lépéseit, mielőtt pontosan rögzítenénk egy programnyelvre. Az ál-kódban néhány formális konstrukciót és általánosan elfogadott matematikai szimbólumokat használnak.
Nem létezik szigorú szintaxisszabály a pszeudokód létrehozásához. Ez megkönnyíti az algoritmus megírását a tervben, és lehetővé teszi az algoritmus leírását bármely parancskészlet segítségével. Azonban az ál-kód általában a formális nyelvekhez tartozó szerkezetek néhány részét használja fel, ami elősegíti az átmenetet a pszeudokódból az algoritmus programozási nyelven történő írásába. Nincs pszeudokód egyetlen vagy formális definíciója, így különböző pszeudo-kódok lehetségesek, eltérőek a használt szavak és konstrukciók készletében.
Blokkdiagram - az algoritmus struktúrájának leírása vonalas kapcsolatokkal rendelkező geometriai ábrák segítségével, bemutatva az egyes utasítások végrehajtásának sorrendjét. Ez a módszer számos előnnyel jár. Az egyértelműség miatt az algoritmus "olvashatóságát" biztosítja, és kifejezetten megjeleníti az egyes parancsok végrehajtási sorrendjét. Minden egyes formális terv blokkvázlatában megegyezik egy bizonyos geometriai alakkal vagy sorokkal összekapcsolt ábrákkal.
Tekintsünk néhány alapvető tervet a GOST 19.701-90 által szabályozott program algoritmusok blokkdiagramainak építésére.
Az algoritmus kezdetének / végét jellemző blokk (szubrutinok esetén - hívás / visszaadás)
A blokk egy folyamat, amely az egyéni műveletek leírására szolgál
Blokk - Elõre definiált eljárás segéd algoritmusokra (szubrutinok)
Blokk - bemenet / kimenet egy nem definiált adathordozóról vagy a forrásadatok leírása
Blokk döntés (állapotfelmérés vagy feltételes blokk)
Blokk - a ciklus határa, amely a típus ciklikus folyamatait írja le: "ciklus előfeltevéssel", "ciklus utáni állapot"
Az algoritmus leírása verbális formában, pszeudo-kódban vagy blokkdiagram-formában lehetővé teszi némi alkalmasságot a parancsok megjelenítésekor. Ugyanakkor elegendő, hogy lehetővé teszi az ember számára, hogy megértse az ügy lényegét és végrehajtsa az algoritmust. A gyakorlatban az algoritmusokat számítógépek végzik. Ezért egy számítógéppel végrehajtandó algoritmust "érthető" nyelven kell írni, így egy formalizált nyelvet programozási nyelvnek neveznek.
Program - az algoritmus struktúrájának leírása az algoritmikus programozás nyelvén.
Az algoritmus elemi lépései a következő algoritmikus konstrukciókba illeszthetők: lineáris (szekvenciális), elágazás, ciklikus előfeltétel és ciklikus posztkondíciókkal. Bármilyen algoritmust lehet létrehozni e négy algoritmikus konstrukció segítségével.
Lineynoynazyvayut algoritmikus tervezési megvalósított formájában műveletsorozat (lépések), amelyben minden egyes fellépés (lépés) az algoritmus végrehajtására csak egyszer, és miután minden egyes i-edik fellépés (lépés) végezzük (i + 1) -edik művelet (lépés), ha Az i-th akció nem az algoritmus vége.
Elágazások (ilivetvyascheysya) nevű algoritmikus tervezés biztosítja a választás a két alternatíva értékétől függően a bemeneti adatok. Minden egyes bemeneti adatkészlet esetében az elágazó algoritmus lineáris értékre csökken. Tüntesse fel a hiányos (ha - ez) és teljes (ha - ez - másként) ágakat. Teljes elágazás lehetővé teszi, hogy gondoskodjon két ág az algoritmus (azaz akár nem), amelyek mindegyike vezet közös pontja torkolatánál, így az algoritmus folytatódik, függetlenül attól, hogy melyik utat választotta (1.). Hiányos elágazási algoritmus feltételezi valamilyen beavatkozással csak egy ága (i), a második ág nincs jelen, azaz az egyik vizsgálati eredmény esetében nem szükséges végrehajtani a műveletet, a vezérlés azonnal átköltözik az egyesítés pontjára.
Ábra. 1. Teljes elágazás
Ciklikus (vagy a ciklus) az úgynevezett algoritmikus szerkezet, amelyben néhány egymást követő akciócsoport (lépések) algoritmus módon több alkalommal végrehajtható, attól függően, hogy a bemeneti adatokat, vagy a feladat feltételei. A ciklus minden egyes szakaszában ismétlődő akciók csoportját egy ciklus testnek nevezik. Bármely ciklikus szerkezet tartalmaz egy elágazó algoritmikus konstrukció elemeit.
Ciklus előfeltétele
Ebben a ciklikus szerkezetben a feltételes kifejezés (feltétel) értékét először a hurok következő lépése előtt ellenőrizzük. Ha a feltételes kifejezés értéke igaz, a hurok testét végrehajtja. Ezután a kontroll ismét átkerül az állapot ellenőrzésére stb. Ezeket a műveleteket addig ismételjük, amíg a feltételes kifejezés FALSE-ra nem kerül. Az állapot első figyelmen kívül hagyásával a ciklus befejeződik. A hurok lépéseinek száma nem előre meghatározott, és a feladat bemeneti adataitól függ. A hurok azon tulajdonsága, hogy előfeltétele az, hogy ha a feltételes kifejezés kezdetben hamis, akkor a hurok test nem fog egyszerre végrehajtani.
Ábra. 2. A ciklus blokkdiagramja előfeltétel: a kép két változata a feltételes blokk felhasználásával a) és a ciklus határoló blokk használatával b)
Cycle with postcondition
Mint az előfeltáró ciklusban, ciklusos, post-feltételes szerkezettel, a hurok test ismétléseinek száma előre nem határozható meg, ez a probléma bemeneti adataitól függ. Ellentétben egy előfeltáró hurokkal, egy ciklus utáni állapotot mindig legalább egyszer hajtanak végre, amely után a feltétel ellenőrzése megtörténik. Ebben a konstrukcióban a hurok testét addig végrehajtják, amíg a feltételes kifejezés értéke nem hamis (a hurok "vége" állapota). Amint ez igaz lesz, a parancs megszűnik. Lehetőség van ciklus létrehozására, azzal a feltétellel, hogy "folytatjuk" a ciklust, azaz. A hurok test mindaddig végrehajtódik, amíg a feltétel értéke igaz. Ennek a konstrukciónak a blokkvázlata az 1. ábrán látható. 3 két módon: a feltételes blokk a segítségével és a vezérlőegység segítségével. B.
Ábra. 3. A ciklus blokkdiagramja egy posztteremmel
Tekintsünk három ciklikus algoritmust: egy ciklust egy paraméterrel (amelyet aritmetikai ciklusnak nevezünk), egy feltételes ciklust és egy ciklus utáni állapotot (ezeket iteratívnak nevezik).
Van egyfajta ciklus, amelynek előfeltétele, egy aritmetikai ciklusnak nevezik. A számtani ciklusban a lépések számát (ismétlés) egyedileg határozza meg a paraméter megváltoztatására vonatkozó szabály, amelyet a paraméter kezdeti (N) és végleges (K) értékei és a változtatás lépése (h) határoz meg. Ie A ciklus első lépéseként a paraméter értéke N, a második - N + h, a harmadik - N + 2h, stb. A ciklus utolsó lépéseként a paraméter értéke nem nagyobb, mint K, de annak további változása nagyobb értékhez vezet; mint K.
Például nyomtassa ki a "Hello!" Szót 10-szer. A blokkdiagram a számtani ciklus kezdetének egy speciális blokkját használja, azzal a jelzéssel, hogy az i változó 1-től 10-ig 1-es lépésekben változik.
