Algoritm degen ne hám onıń túrleri

TEMA: SHAMALIQ ALGORITMLAR VERTEX QATLAMI MENEN BAYLANISLI MÁSELE
Joba:

1. 
   Algoritm degen ne hám onıń túrleri
   
2. 
   Algoritmlardıń túrleri
   
3. 
   Shamaliq algoritmlar
   

Algoritm degen ne hám onıń túrleri
Algoritm - bul orınlawshınıń sheklengen muǵdardaǵı háreketlerde máseleni tarqatıp alıw nátiyjesine erisiw rejimin xarakteristikalaytuǵın kórsetpeler kompleksi. Eski talqinda " tártip" sózi ornına " izbe-izlik" sózi isletilingen, biraq kompyuterler jumısında parallelizm rawajlanıwı menen " izbe-izlik" sózi ulıwmalaw " tártip" sózi menen almastırila baslandı. Óytkeni, algoritmdıń birpara kórsetpeleriniń jumısı basqa kórsetpelerge yamasa olardıń jumıs nátiyjelerine baylanıslı bolıwı múmkin. Sonday etip, birpara kórsetpeler olar baylanıslı bolǵan kórsetpeler orınlanǵannan keyin qatań orınlanıwı kerek. Ǵárezsiz kórsetpeler yamasa olar baylanıslı bolǵan kórsetpelerdi toltırıw arqalı ǵárezsiz etilgen kórsetpeler, eger paydalaniletuǵın protsessor hám operatsion sistema ruxsat bergen bolsa, qálegen tártipte, parallel túrde yamasa bir waqtıniń ózinde orınlawǵa bolatuǵın.
Algoritm túsinigi matematikanıń túp, tiykarǵı, tiykarǵı túsiniklerin ańlatadı. Algoritmik xarakter degi esaplaw processleri (pútkil sanlar ústindegi arifmetik ámeller, eki sannıń eń úlken ulıwma bóliwshisin tabıw hám t.b. ) insaniyatqa áyyemginen málim bolǵan. Biraq, anıq formada, algoritm túsinigi tek 20 -ásir baslarında qáliplesken.
Algoritm kontseptsiyasın bólekan rásmiylestiriw 1928 jılda Devid Xilbert tárepinen islep shıǵılǵan rezolyutsiya mashqalasın (nem. Entscheidungsproblem) sheshiwge urınıslar menen baslandı.
Algoritmlardıń túrleri
Arnawlı bir ámeliy mashqalalardi sheshiw ushın mólsherlengen ámeliy algoritmlar bólek rol oynaydı. Eger algoritm máseleniń talaplarına juwap bersa (mısalı, fizikalıq tárepten tuwrı keletuǵın nátiyjeni beredi) tuwrı esaplanadı. Algoritm (programma ) birpara dáslepki maǵlıwmatlar ushın nadurıs nátiyjeler, buzılıwlar, buzılıwlar yamasa ulıwma nátiyje bermasa, qátelerdi óz ishine aladı. tómende bayanlainganidek:
* Mexanik algoritmlar yamasa basqasha tárzde deterministik, qatań (mısalı, mashina, dvigatel hám basqalar algoritmı ) - málim háreketlerdi ornatıp, olardı birden-bir hám isenimli izbe-izlilikde belgileydi hám nátiyjede, eger bul shártler orınlanǵan bolsa, anıq talap etiletuǵın yamasa qálegen nátiyjeni támiyinleydi. uchrashdi procesi, algoritmı islep shıǵılǵan wazıypalar.
* Maslasıwshı algoritmlar, mısalı, stokastik, yaǵnıy itimallıq hám evristik.
* Múmkinshiligıy (stokastik) algoritm mashqalanı bir neshe usılda yamasa nátiyjege erisiw múmkinshiligına alıp keletuǵın usıllarda tarqatıp alıw programmasın beredi.
* Evristik algoritm (grekshe " evrika" sózinen) - qatań tiykarlarsız hár qıylı aqılǵa say oy-pikirlerden paydalanatuǵın algoritm [11].
* Sızıqlı algoritm - orınlanǵan buyrıqlar (kórsetpeler) kompleksivaqt boyınsha izbe-iz alınǵan.
* Tarmaqlanıw algoritmı - bul keminde bir shártni óz ishine alǵan algoritm bolıp, bunıń nátiyjesinde algoritmdıń bir neshe parallel tarmaqlarına bóliniw ámelge asırılıwı múmkin. Kóplegen jaǵdaylarda, málim sharayatlarda bir háreketler izbe-izligin, basqa sharayatlarda bolsa basqasın orınlaw talap etiledi. Jawın yog'ayotgan bolsa, qasnaqtı ashıw kerek. Eger signal shalınsa, siz turıwıńız kerek. Eger men Sasha menen uchrashsam, men oǵan aytaman... Eger Sasha menen uchrashsam, men oǵan aytaman... keri jaǵdayda men onıń aldına baraman.
Hár bir insan ómirinde ápiwayı yamasa quramalı bolǵan kóplegen máseleler ushırasıp turadı. Bul máselelerdi málim qaǵıyda hám instruktsiyalarga tiykarlanǵan túrde tarqatıp alıw múmkin. Kóplegen máselelerdi tarqatıp alıwdı insan texnikalıq apparatlar -avtomatlar, exm, robotlarga tapsırıwı múmkin.
Eki túrde de qoyılǵan máseleni tarqatıp alıw ushın, aldın onıń algoritmın dúziw zárúr. A l g o r i t m dep, qoyılǵan máseleni tarqatıp alıwǵa karatilgan ámeller izbe-izligin orınlaw ushın túsinikli hám anıq kórsetpelerdi beriwge aytıladı.
Algoritm sózi, arifmetik ámellerdi orınlaw qaǵıydaların bayan kilgan, IX ásirdiń ullı matematigi Al-Xorezmiy atınıńń latınsha formasından kelip chikkan. Barinen burın algoritmlar degende kóp xanalı sanlar menen turt arifmetik ámel atqarılatuǵın qaǵıydalar tushinilar edi.
Keyinirek bul túsinik qoyılǵan máseleni tarqatıp alıwǵa alıp keletuǵın qaǵıyda hám ámeller izbe-izligin belgilew ushın qollanila basladı. Algoritm tómendegi ózgesheliklerge iye: uzluklilik, anıqlıq, nátiyjeliklıq hám ǵalabalıq.
Uzluklilik: Dáslepki berilgen maǵlıwmatlardı nátiyjege aylandırıw procesi úzliksiz túrde ámelge asıriladıki bunda waqtıniń hár bir keyingi keletuǵın úzliksiz túrde ámelge asıriladıki bunda waqtıniń hár bir keyingi keletuǵın bolǵan mikdorlar ma`nisinen málim bir qaǵıydalar buyicha alınadı.
Anıqlıq: Algoritmdıń hár bir qaǵıydası anıq hám bir bahalı bolıwı zárúrki bunda waqtıniń qandayda bir minutında alınǵan mikdorlar ma`nisi waqtıniń sonnan aldınǵı minutında alınǵan mikdorlar ma`nisi menen bir bahalı anıqlanǵan boladı.
Nátiyjelilik. Algoritm máseleniń echilishiga chekli sanına qádemler ishinde alıp keliwi yamasa máseleni echib bolmaydı degen xabar menen menen tawısıwı kerek.
Ǵalabalıq. Máseleniń tarqatıp alıw algoritmı sonday jaratılıwı kerek onı tek baslanǵısh maǵlıwmatlar menen parıq etetuǵın máselelerdi tarqatıp alıw ushın da qollanılıwı kerek. Bunda baslanǵısh maǵlıwmatlar algoritmdı qóllaw tarawi dep atalatuǵın qandayda-bir tarawdan alınadı.
Algoritmdı islep shıǵıwda onı bir neshe qıylı usıl menen ańlatpalap bersa boladı. Usılardan ushewi keń tarqalǵan:
1. Algoritmdı ápiwayı tilde xarakteristikalaw
2. Algoritmdı sistema kórinisinde ańlatıw
3. Algoritmdı arnawlı (algoritmik) tilde jazıw.
Algoritmdı ápiwayı tilde xarakteristikalaw. Algoritmlardı ańlatıwdıń eń keń tarkalgan forması bul ápiwayı tilde sózler menen bayanlaw bolıp tabıladı. Bul tekǵana esaplaw algoritmlarda bálki ómiriy turmishdagi algoritmlarǵa da tiyisli bolıp tabıladı.
Mısalı qandayda bir bir tamaq yamasa kandolat ónimin tayarlawdıń retsepti da ápiwayı tilde xarakteristikalanǵan algoritm bolıp tabıladı. Qalalararo telefon avtomat arqalı aloka ornatıwdıń ayriqsha algoritmınan paydalanasız. Dukondan jańa kir juwıw mashinası yamasa magnitafon satıp alınsa jumıstı paydalanıwdıń algoritmı menen tanısıwdan baslaymız.
Máseleni EXM de tarqatıp alıwda da kóbinese matematika tilin da uz ishine alǵan tábiy tilden paydalanıw múmkin. Algoritmdıń bunday tildegi jazıwı ızlenip atırǵan nátiyjege alıp keletuǵın ámeller ketma- ketligi kórinisinde bolıp adam tárepinen bir mánisli aqıl etiliwi kerek. Sózler menen kórsetilgen hár bir ámel algoritmdıń qádemi dep ataladı.
Qádemler tártip nomerine iye boladı. Algoritm ketma- ket qádem baqadam atqarılıwı kerek. Eger algoritm tekstinde N-sanlı qádemge utilsin dep jazılǵan bolsa bul algoritmdıń atqarılıwı kórsetilgen N- nchi qádemnen dawam etiwin ańlatadı.
Algoritmdı ápiwayı tilde ańlatıw qolay bolǵanı menen quramalı algoritmlarda kurgazmalikni jaqsı támiyinley almaydı. Bunnan tısqarı algoritmdıń sóz degi xarakteristikası esaplaw mashinasına kirgiziw ushın jaramaydı.
Onıń ushın algoritmdıń mashina tilinde sonday bayanlaw kerek, mısalı EXM de tarqatıp alıw processinde bul algoritm jumıstı avtomatikalıq basqarib turatuǵın bulsin. Mashina túsinetuǵın formada jazılǵan algoritm máseleni tarqatıp alıw programması bolıp tabıladı.
Algoritmdı ápiwayı tilde jazıwda turt qıylı ámelden ; esaplaw, N- qádemge ótiw, shártni tekseriw, esaplawdıń aqırı, sonıń menen birge kirgiziw hám shıǵarıw ámellerinen paydalanılǵan ma'kul. Bo'lar ishinde eń kóp paydalaniletuǵın esaplaw ámeli bolıp tabıladı.
Algoritm sistema kóriniste ańlatıw. Salıstırǵanda quramalı máselelerdi tarqatıp alıwda algoritmnan arnawlı bir EXM tilindegi programmaǵa ótiw júdá kiyin Bunday tikkeley ótiwde algoritmdıń ayrıqsha bólimleri arasındaǵı baylanısıw yuqoladi, algoritm quramınıń tiykarǵı hám áhmiyetli bolmaǵan bólimlerin parıqlaw kiyin bolıp qaladı.
Bunday sharayatta keyinirek anıqlaw hám tuwrılaw talay waqıt talap etetuǵın qátelerge ańsatǵana yul qoyıw múmkin. Ádetde algoritm bir neshe ret islep shıǵıladı, geyde qátelerdi tuwrılaw algoritm quramın anıqlawtırıw hám tekseriw ushın bir neshe ret keyin basıp qaytıwǵa tuwrı keledi.
Algoritm islep shıǵıwdıń birinshi bochqichida algoritmdı jazıwdıń eń qolay usılı algoritmdı tuzim kórinisinde ańlatıw bolıp tabıladı. Algoritm tuzimi bul berilgen algoritmdı ámelge asırıw daǵı ámeller izbe-izliginiń ápiwayı tildegi súwretlew elementleri menen tuldirilgan grafik suwreti bolıp tabıladı.
Algoritmdı hár bir qádemi sistemasında qandayda bir bir geometriyalıq forma blok menen hákis etiriladi. Bunda atqarılatuǵın ámeller túrine kóre túrlishe bolǵan bloklarǵa GOST buyicha suwretlenetuǵın hár qıylı geometriyalıq sırtqı kórinisler tuwrı turtburchak, romb, parallelogramm, sheńber, ovval hám xakazolar sáykes keledi.
Algoritm tuzimlarini kóriw qaǵıydaları GOST 19. 002 80 de (xalkaro standart ISO 2636 -73 ke sáykes keledi.) kat'iy belgilep qoyılǵan. GOST 19. 003-80 (ISO 1028-73 ke uyqas ) algoritm hám programmalar tuzimlarida qollanılatuǵın simvollar dizimin, bul simvollarning forması hám ólshemleriniń sonıń menen birge olar menen suwretlenetuǵın funktsiyalardı (ámellerdi) belgileydi.
Tómendegi kestede algoritmlar tuzimini ańlatıwda kóp qollanılatuǵın blok (simvol) lari keltirilgen hám olarǵa túsintirisler berilgen. Tuzim blok (simvol) lari ishinde esaplawlardıń tiyisli bochqichlari kórsetiledi. Sol erda hár bir simval tolıq tushintiriladi. Hár bir simvol (blok ) uz nomerine iye boladı. Ol tepadagi shep múyeshka chizikni úzip jazıp qóyıladı.
Tuzimdagi grafik simvollar esaplaw procesiniń rawajlanıw baǵdarınıń kórsetiwshi chiziklar menen birlestiriledi. Geyde chiziklar aldında bul jónelis qanday sharayatta saylanǵanlıǵı jazıp qóyıladı. Axborat okimining tiykarǵı baǵdarı tepadan tómenge hám shep den ońǵa ketedi.
Bul qallarda chiziklarni kórsetpesi de boladı. Basqa qallarda álbette chiziklarni qóllaw májburiy bolıp tabıladı. Blokka salıstırǵanda okim chizigi (potok linii ) kiretuǵın yamasa chikuvchi bolıwı múmkin. Blok ushın kiretuǵın chiziklar sanı shegaralanbaǵan. Chikuvchi chizik bolsa logikalıq bloklardan basqa qallarda tek bir boladı. Logikalıq bloklar eki hám odan artık okim chizigiga iye boladı.