Maǵlıwmatlardıń abstrak túrleri hám maǵlıwmatlar strukturaları

Kirisiw. Esaplaw modelleri, algoritmlar hám olardıń
quramalılıǵı
Algoritm túsinigi. Áwele algoritm túsinigi IX asirde jasap óretiwshilik etken ullı túp babaımız Muhammad al-Xorezmiy atı menen tıǵız baylanıslılıǵın túsindiriw kerek. Algoritm sózi al Xorezmiyning arifmetikaga arnalǵan shıǵarmasınıń dáslepki betidagi “Dixit Algoritmi” (“dediki al-Xorezmiy” dıń latınsha ańlatpası ) degen gáplerden kelip shıqqan. Sonnan keyin al-Xorezmiyning sanaq sistemasın jetilistiriwge qosqan úlesi, onıń dóretpeleri algoritm túsiniginiń kiritiliwine sebep bolǵanlıǵı aytıp ótiledi. Algoritm ne degen sorawǵa, ol tiykarǵı túsinik retinde qabıl etilgenliginen, onıń tek xarakteristikası beriledi, yaǵnıy qandayda bir maqsetke erisiwge yamasa qanday da máseleni sheshiwge qaratılǵan kórsetpelerdiń (buyrıqlardıń ) anıq, túsinikli, chekli hám de tolıq sisteması túsiniledi.
Algoritm túsinigi anıq formada 20 -ásir baslarında D. Gilbert, K.Gyodel, S. Klin, A. Chyorch, E. Post, A. Tyuring, N. viner, A. A.Markov sıyaqlı ilimpazlardıń dóretpeleri sebepli qáliplesti. Eń áyyemgi cifrlı algoritmlardan biri Yevklid algoritmı (eramızǵa shekemgi III ásir) dep esaplanadı - eki sannıń eń úlken ulıwma bóliwshisin tabıw. Algoritmlardıń zamanagóy teoriyası nemis matematikası Kurt Gyodel (1931) dóretpeleri menen baslandı, olar ózleriniń rásmiy, izbe-iz hákisiomalar sisteması sheńberinde sheship bolmaytuǵın máseleler bar ekenligin kórsetdi. Algoritmlar teoriyası boyınsha birinshi fundamental jumıslar 1936 yilda payda bolǵan.
Tyuring mashinası, Post hám Chyorch tárepinen esabı usınıs etiledi. Bul mashinalar algoritmdıń formallashtirilgan rásmiylestiriliwi edi. Algoritmdı atqarap atırǵan kisi - atqarıwshı, tiykarǵı algoritmdı anıqlawtiruvchi algoritm - járdemshi algoritm ekenligin da aytıp ótiw kerek. Ulıwma, algoritmdıń qanday maqsetke mólsherlengenliginen qaramastan onı tabıs menen orınlaw múmkinligin aytıp ótiw kerek bolıp tabıladı.Algoritmdıń bir neshe tariypi bar.
Olardan ayırımların keltirip ótemiz:- ―Algoritm - bul belgileytuǵın sheklengen qaǵıydalar kompleksi, arnawlı bir wazıypalar kompleksin sheshiw boyınsha ámeller izbe-izligi hám besew zárúrli qasiyetke iye: anıqlıq, túsiniklilik, kirgiziw, shıǵarıw, nátiyjelililik‖. (D. E. Knut).
- ―Algoritm - bul qatań belgilengen qaǵıydalar tiykarında atqarılatuǵın
hár qanday esaplaw sisteması bolıp tabıladı, bul málim bir Qatar basqıshlardan keyin, anıq qoyılǵan máseleni sheshiwge alıp keledi"
(A. Kolmogorov).
- ―Algoritm - bul hár túrlı baslanǵısh maǵlıwmatlardan kerekli
nátiyjege ótetuǵın esaplaw procesin belgileytuǵın anıq izbe-izlik"
(A. Markov).
1950-jıllarda algoritm teoriyasına óz úleslerin Kolmogorov hám
Markov dóretpeleri qosqan. 1960 -1970 jıllarda algoritm teoriyasında
tómendegi izertlew baǵdarları qáliplesti:
1) Algoritmlardıń klassik teoriyası (rásmiy tiller noqatı názerinen máselelerdi qáliplestiriw, sheshiwshilik mashqalası túsinigi, quramalılıq klassların kirgiziw, P = NP (?) máselesin qáliplestiriw, NP-dıń tolıq máselelerin klası jáne onı úyreniw);
2) Algoritmlardı asimptotik analiz qılıw teoriyası (algoritmdıń quramalılıǵı túsinigi, algoritmlardı bahalaw kriteriyalari,
asimptotik bahalardı alıw usılları, atap aytqanda, rekursiv algoritmlar ushın, quramalılıqtı yamasa atqarılıw waqtın asimptotik analiz qılıw );
3) Esaplaw algoritmların ámeliy analiz qılıw teoriyası (funksiyalardıń intervallı analizi, algoritmlar sapasınıń ámeliy kriteryaları, ratsional algoritmlardı tańlaw metodikası ).
Algoritmlar teoriyasında hal etilgen maqset hám wazıypalar :
- " algoritm" túsinigin formallashtirish (rásmiylestiriw) hám
formal (rásmiy) algoritmik sistemalardı úyreniw;
- mashqalalardıń algoritmik sheshimin rásmiy tastıyıqlaw ;
- wazıypalardı klassifikaciyalaw, quramalılıq klassların anıqlaw hám izertlew qılıw ;
- algoritmlardıń quramalılıǵın asimptotik analiz qılıw ;
- rekursiv algoritmlardı úyreniw hám analiz qılıw ;
- algoritmlar sapasın salıstırıwiy bahalaw kriteryaların islep shıǵıw.
Algoritm túsinigin formallashtirish
1-ta‟rif. Algoritm - bul málim bir tilde berilgen, múmkin bolǵan
dáslepki maǵlıwmatlar klası ushın máseleni sheshiw ushın múmkin
bolǵan elementar ámellerdiń sheklengen izbe-izligi.
Máseleniń dáslepki maǵlıwmatlarınıń kompleksi D bolsın hám R -
múmkin bolǵan nátiyjeler kompleksi, sonda algoritm 𝐃 → 𝐑 kórinisinde suwretlenedi. Bul suwretleniw tolıq bolmawi múmkin.
Eger nátiyje tek birpara 𝑑 ∈ 𝐷 ushın alınǵan bolsa, algoritm bólegiy
algoritm hám eger barlıq 𝑑 ∈ 𝐷 ushın tuwrı nátiyje alsa tolıq algoritm
dep ataladı.
2-ta‟rif. Algoritm - bul sheklengen waqıt ishinde máseleni sheshiw
nátiyjesine erisiw ushın atqarıwshınıń háreketleri rejimin xarakteristikalaytuǵın anıq kórsetpeler kompleksi.
Algoritmdıń anıq yamasa tikkeley bolmaǵan hár qıylı tariypleri bir qatar
talaplardı keltirip shıǵaradı :

- algoritmda sheklengen muǵdardaǵı elementar orınlawǵa bolatuǵın

bolǵan izbe-izlik bolıwı kerek, yaǵnıy jazıwdıń anıqlıǵı talabı
orınlanıwı kerek;
- algoritm máseleni sheshiwde sheklengen sanlı basqıshlardı
orınlawı kerek, yaǵnıy háreketlerdiń anıqlıǵı talabı orınlanıwı kerek;
- barlıq qabıl etilgen kirisiw maǵlıwmatları ushın algoritm birdey
bolıwı kerek, yaǵnıy universallıq talabına juwap beriw;
- algoritm qoyılǵan wazıypaǵa salıstırǵanda tuwrı sheshimge alıp keliwi
kerek, yaǵnıy tuwrılıq talabı orınlanıwı kerek.
Algoritmdıń tiykarǵı ózgeshelikleri haqqında tómendegilerdi atap ótiw
múmkin:
1-qasiyet. Diskretlilik, yaǵnıy algoritmdı chekli sandaǵı ápiwayı
kórsetpeler izbe-izligi formasında ańlatıw múmkin.
2-qasiyet. Túsiniklilik, yaǵnıy atqarıwshına usınıs atırǵan
kórsetpeler onıń ushın túsinikli bolıwı shárt, keri jaǵdayda atqarıwshı
Ápiwayı ámeldi de atqara almay qalıwı múmkin. Hár bir atqarıwshınıń
atqara alıwı múmkin bolǵan kórsetpeler sisteması bar.
3-qasiyet. Anıqlıq, yaǵnıy atqarıwshına berilip atırǵan kórsetpeler anıq
mazmunda bolıwı kerek hám de tek algoritmda kórsetilgen tártipte
orınlanıwı shárt.
4-qasiyet. Ǵalabalıq, yaǵnıy hár bir algoritm mazmunına kóre bir
túrdegi máselelerdiń barlıǵı ushın jaramlı bolıwı kerek. Mısalı,
eki ápiwayı bólshek ulıwma bólimin tabıw algoritmı hár qanday bólshekler
ulıwma bólimin tabıw ushın isletiledi.
5-qasiyet. Juwmaqlawshılıq, yaǵnıy hár bir algoritm chekli sandaǵı
qádemlerden keyin álbette nátiyje beriwi kerek.
Bul ózgeshelikler mánisin úyreniw hám konkret algoritmlar ushın
qaray shıǵıw studentlerdiń ózgeshelikler mazmunın bilip alıwlarına járdem beredi.
Algoritmdıń súwretlew usılları haqqında sóylegende algoritmdıń
beriliw usılları túrli-tumanlıǵı hám olar arasında eń kóp ushraytuǵınları
tómendegiler ekenligin kórsetip ótiw kerek:
1. Algoritmdıń sózler arqalı ańlatılıwı.
2. Algoritmdıń formulalar járdeminde beriliwi.
3. Algoritmdıń keste kórinisinde beriliwi, mısalı, túrli
matematikalıq kesteler, lotereya jetiskenlikleri kestesi, funksiyalar bahaları kesteleri buǵan mısal boladı.
4. Algoritmdıń programma formasında ańlatılıwı, yaǵnıy algoritm
kompyuter atqarıwshısına túsinikli bolǵan programma formasında beriledi.
5. Algoritmdıń algoritmik tilde suwretleniwi, yaǵnıy algoritm bir
qıylı hám anıq ańlatıw, orınlaw ushın qollanılatuǵın belgilew hám qaǵıydalar kompleksi algoritmik til arqalı ańlatıw bolıp tabıladı. Olardan oqıw úyreniw tili retinde paydalanılıp atır. Bo'lardan E-praktikum yamasa E-tili algoritm atqarıwshısı algoritmik tili de bar.
6. Algoritmlardıń grafik formada suwretleniwi. Mısalı,
grafiklar, sxemalar yaǵnıy blok - sxema buǵan mısal bóle aladı. Blok
sxemanıń tiykarǵı elementleri tómendegiler: súyri-sopaq (ellips forması )-algoritm baslanıwı hám tamamlanishi, tuwrı múyeshli tórtmuyush-baha beriw yamasa tiyisli kórsetpelerdi orınlaw. Romb - shárt tekseriwdi Belgileydi. Onıń jóneltiruvchilari tarmaqlar boyınsha biri awa ekinshisi joq jónelislerdi beredi, parallelogramm- maǵlıwmatlardı kirgiziw yamasa
shıǵarıw, járdemshi algoritmǵa shaqırıq - parallelogramm eki
tárepi sızıq, jóneltiriwshi sızıq - blok -sxema daǵı háreket
basqarıwı, noqat -tuwrı sızıq (eki parallel) - baha beriw.
Algoritmda orınlanıwı pıtken ámeller izbe-izligi algoritm
qádemi dep júritiledi. Hár bir bólek qádemdi jırlaw ushın
orınlanıwı kerek bolǵan ámeller haqqındaǵı kórsetpe buyrıq dep
aytıladı.
Algoritmlardı kórgezbeliroq etip súwretlew ushın bloksxema,

yaǵnıy

geometriyalıq usıl kóbirek qollanıladı. Algoritmdıń bloksxemasi

algoritmdıń tiykarǵı dúzilisiniń ayqın geometriyalıq suwreti:

algoritm blokları, yaǵnıy geometriyalıq sırtqı kórinisler kórinisinde, bloklar
arasındaǵı baylanıs bolsa baǵıtlanǵan sızıqlar menen kórsetiledi.
Sızıqlardıń baǵdarı bir bloktan keyin qaysı blok orınlanıwın
ańlatadı. Algoritmlardı bul usılda ańlatıwda wazıypası, tutqan
ornına qaray tómendegi geometriyalıq forma (blok ) lardan paydalanıladı.
Algoritmlar beriliwi hám ańlatılıwına qaray: sızıqlı,
tarmaqlanıwshı hám tákirarlanıwshı túrlerge bólinedi.
Algoritmdıń túrleri menen tanıstırǵanda, áwele hesh qanday shárt
tekserilbeytuǵın hám tártip menen tek izbe-iz atqarılatuǵın
processlerdi ańlatatuǵın sızıqlı algoritmlar aytıp ótiledi.
Algoritm qáte nátiyjelerdi keltirip shıǵaratuǵın yamasa ulıwma nátiyje
bermeytuǵın bolsa, qátelerdi óz ishine aladı.
Algoritm hár qanday tuwrı kirisiw ushın tuwrı nátiyjelerdi
beretuǵın bolsa, qátesinińz boladı.
Maǵlıwmatlardı kirisiw hám shıǵıw túrleri boyınsha parıqlaw múmkin
- Cifrlı máselelerdi sheshiw algoritmları (birinshi bolıp payda
boldı );
- Cifrlı bolmaǵan algoritmlar.
1. 2. Esaplaw modelleri
Esaplaw teoriyası hám esaplaw quramalılıǵı teoriyası esaplaw
modelin tekǵana esaplaw ushın paydalaniletuǵın qabıl etiletuǵın
Ámeller kompleksiniń tariypi, bálki olardı qóllawdıń salıstırmalı ǵárejetleri
retinde de kórip shıǵadı. Kerekli esaplaw dáreklerin - jırlaw
waqtın, yad kólemin, sonıń menen birge algoritmlardıń sheklenishlarini yamasa
kompyuterdi xarakterlew múmkin - tek málim bir esaplaw modeli
saylanǵan táǵdirde.
Modelge tiykarlanǵan injenerlikte esaplaw modeli jáne onıń
tańlawı, eger onıń bólek bólimleriniń minez-qulqları málim bolsa,
ulıwma sistema qanday isleydi degen sorawǵa juwap beredi.
Esaplaw quramalılıǵınıń asimptotik bahosida esaplaw modeli
málim baha menen qabıl etiletuǵın primitiv ámeller arqalı anıqlanadı.
Málim ámeller kompleksine hám olardıń esaplaw quramalılıǵına
qaray bir qatar esaplaw modelleri málim. Olar tómendegi keń
taypalarǵa bólinedi: algoritm esaplawdıń quramalılıǵın joqarı
shegarasın alıw ushın paydalaniletuǵın abstrakt mashinalar hám
algoritmik máseleler ushın esaplaw quramalılıǵınıń tómengi
shegarasın alıw ushın isletiletuǵın qarar modelleri.
Tyuring tezisi. Chyorch tezisi. Algoritm túsinigin
anıqlawǵa jantasıwlar. Algoritm túsinigin anıqlaw boyınsha
jantasıwlardı úsh tiykarǵı jóneliske bolıw múmkin.
Birinshi jónelis effektiv esaplanıwshı funksiya túsinigin
anıqlaw menen baylanıslı. Bul jónelis boyınsha A. Chyorch, K. Gyodel,
S. Klini
1
izertlew jumısların aparıwǵan.
1932-1935-jıllar dawamında A. Chyorch hám S. Klini tárepinen
úyrenilgen hám ―

-anıqlanıwshı funksiyalar‖ dep atalǵan, tuwrı
anıqlanǵan esaplanıwshı teoriyalıq -sanlı funksiyalar klasınıń ―

anıqlanıwshı

funksiyalar‖ klası biziń intuitiv oyda sawlelendiriwimiz boyınsha

esaplanıwshı dep qaralatuǵın hámme funksiyalardı qamtıp alıwı
múmkin degen pikir tuwıllıǵi 1935-jılda daǵaza etildi. Bul qápelimde
nátiyje edi.
J. Erbranning
2
bir ideyası tiykarında 1934-jılda K. Gyodel tárepinen
anıqlanǵan hám ―umumrekursiv funksiyalar‖ dep atalǵan basqa
Esaplanıwshı funksiyalar klası da ―

-anıqlanıwshı funksiyalar‖
ózgesheliklerine uqsas ózgesheliklerge iye edi.
1936 -jılda A. Chyorch hám S. Klini tárepinen bul eki klass birdey
klass ekenligi tastıyıqlandi, yaǵnıy hár qanday

-anıqlanıwshı funksiya
umumrekursiv funksiya bolıwı hám hár qanday umumrekursiv funksiya

-anıqlanıwshı funksiya ekenligi tastıyıqlandi.
1936 jılda Chyorch tómendegi tezisti járiyaladı : hár qanday intuitiv
effektiv (nátiyjeli) esaplanıwshı funksiyalar umumrekursiv
funksiyalar bolıp tabıladı.
Bul teorema emes, bálki tezis bolıp tabıladı: tezis quramında intuitiv anıqlanǵan
effektiv esaplanıwshı funksiya túsinigi, anıq matematikalıq atamalarda
anıqlanǵan umumrekursiv funksiya túsinigi menen áyne
teńlestirilgen. Sol sebepli bul tezisti tastıyıqlaw múmkin emes.
Biraq Chyorch hám basqa ilimpazlar tárepinen bul tezisti quwatlaytuǵın
kóp dáliller kórsetildi.
Ekinshi jónelis algoritm túsinigin tikkeley anıqlaw menen
baylanıslı : 1936 -1937-jıllarda, A. Tyuring
3
Chyorch jumıslarınan xabarsız
halda jańa funksiyalar klasın kirgizdi. Bul funksiyalardı ―Tyuring
boyınsha esaplanıwshı funksiyalar‖ dep atadılar. Bul klass da joqarıda
aytılǵan ózgesheliklerge iye edi hám bunı Tyuring tezisi dep aytamiz. 1937 yilda

A. Tyuring tastıyıqladıki, onıń esaplanıwshı funksiyaları


anıqlanıwshı

funksiyalardıń ózi hám, sonday eken, umumrekursiv

funksiyalardıń dál ózi eken. Sol sebepli Chyorch tezisi menen
Tyuring tezisi ekvivalent bolıp tabıladı.
1936 -jılda E. Post (Tyuring jumıslarınan xabarsız halda ) áyne
Tyuring erisken nátiyjelerge sáykes keletuǵın nátiyjelerdi járiyaladı hám
1943-jılda, 1920 -1922-jıllardaǵı baspa etilmegen jumıslarına tıykarlanıp,
tórtinshi ekvivalent tezisti baspa etdi. Sonday etip, algoritm
túsinigin tikkeley anıqlawǵa hám keyininen onıń járdeminde
esaplanıwshı funksiya túsinigin anıqlawǵa birinshi bolıp birbiridan
xabarsız
halda
E.
Post
hám
A.
Tyuring
eristiler.

Post hám Tyuring algoritmik processler málim bir dúzılıwǵa iye

bolǵan ―mashina‖ atqaratuǵın processler ekenligin kórsetiwdi. Olar
Bul ―mashinalar‖ járdeminde barlıq esaplanıwshı funksiyalar klası
menen barlıq bólegiy rekursiv funksiyalar klası birdey ekenligin
kórsetdiler hám sonday eken, Chyorch tezisiniń taǵı bir fundamental
tastıyıǵı júzege keldi.
Úshinshi jónelis - Rossiya matematigi A. Markov
tárepinen
islep shıǵılǵan normal algoritmlar túsinigi menen baylanıslı.
1. 3. Algoritmlardıń quramalılıǵı
Algoritmlardıń quramalılıǵı. Esaplaw máseleleri
sheklengen yad resurslarınan paydalanǵan halda aqılǵa say waqıt ishinde
sheshiliwi kerek. Bul algoritmdıń waqıt hám keńislikdegi quramalılıǵı
túsinigine alıp keledi. Qaǵıyda jol menende, algoritm túrli waqıtlardı
orınlawı múmkin bolǵan hár qıylı ámellerdi óz ishine aladı.
Algoritmlardı bahalaw ushın kóplegen kriteryalar bar. Ádetde
kiritiwshi berilgenlerdi kóbeyiwinde máseleni sheshiw ushın kerek
bolatuǵın waqıt hám yad kólemlerin ósiw rejimin anıqlaw mashqalası
qóyıladı. Hár bir anıq másele menen kirgizetuǵın berilgenlerdi muǵdarın
anıqlawshı qanday da sannı bólew zárúr. Bunday san máseleniń
úlkenligi dep qabıl etiledi. Mısalı, eki matritsani kóbeytiw
máselesiniń ólshemi bolıp, matritsalar úlkenligig xizmet etiwi
múmkin. Graflar haqqındaǵı máselede ólshem retinde graf úshleriniń
sanı bolıwı múmkin.
Algoritm sarplanıp atırǵan waqıt máseleniń ólshemi funksiyası
retinde algoritmdı waqıt boyınsha qıyınlıǵı dep ataladı. Bunday
funksiyaǵa máseleniń úlkenligi asqanda limit astındaǵı ózgeris
asimptotik qıyınlıq dep aytıladı.
Quramalılıqtı bahalaw. Algoritmlardıń quramalılıǵı ádetde
atqarılıw waqtı yamasa isletilingen yad boyınsha bahalanadı. Eki
jaǵdayda da, quramalılıq kiritilgen maǵlıwmatlardıń kólemine baylanıslı :
100 dane elementten ibarat dızbeki tap soǵan uqsas 1000 ta
elementten ibarat dızbekke qaraǵanda tezirek qayta islenedi. Usınıń menen
birge, anıq waqıt menen bir neshe kisi qızıǵadı : bul protsessorga baylanıslı,
Maǵlıwmatlar túri, programmalastırıw tili hám basqa kóplegen parametrlerge de
baylanıslı. Tek ǵana asimptotik quramalılıq zárúrli, yaǵnıy kirisiw
maǵlıwmatlarınıń úlkenligi sheksizlikke umtılıp atırǵan daǵı quramalılıq.
Mısalı, birpara algoritmǵa kirisiw maǵlıwmatlarınıń n ta
elementlerin qayta islew ushın 4 n
3
+ 7 n ta shártli ámellerdi orınlaw
kerek. n dıń artpaqtası menen jumıstıń ulıwma dawam etiw waqti n dıń kubi onı
4 ke kópaytirgandan yamasa 7 n ni qosqannan kóre kóbirek tásir etedi.
Bul algoritmdıń waqıt quramalılıǵı O (n
3
), yaǵnıy ol kubik menen
kiritilgen maǵlıwmatlardıń kólemine baylanıslı boladı.
Bas hárip O den paydalanıw matematikadan kelip shıǵadı, bul jerde
bul belgi funksiyalardıń asimptotik háreketlerin salıstırıwlaw ushın
isletiledi. Rásmiy túrde O (f (n)) algoritmdıń islew waqtı (yamasa
iyelegen yad muǵdarı ), kiritilgen maǵlıwmatlardıń kólemine qaray,
f (n) ga kóbeytiriletuǵın birpara konstantalardan tezirek emesligin
ańlatadı.
O (n) - sızıqlı quramalılıq. Bunday quramalılıq, mısalı,
saralanmagan dızbektegi eń úlken elementti tabıw algoritmına iye.
Qay-qaysısı maksimal ekenligin anıqlaw ushın dızbektiń barlıq n
elementlerinen ótiwimiz kerek boladı.
O (log n) - logaritmik quramalılıq. Eń ápiwayı mısal - ekilik
qıdırıw. Eger dızbek saralanǵan bolsa, onı yarımına bolıw arqalı
málim bir mániske iye ekenligin tekseriwimiz múmkin. Orta
elementti tekserip kóremiz, eger ol úlkenlew bolsa, ol jaǵdayda dızbektiń
ekinshi yarımın tastap jiberemiz. Eger kishilew bolsa, ol jaǵdayda
kerisinshe - biz dáslepki yarımın taslaymiz hám sol tárzde ekige
bóliniwdi dawam ettiremiz, nátiyjede (logn) elementlerin tekseremiz.
O (n
2
) - kvadratik quramalılıq. Bunday quramalılıq, mısalı,
element qosılıwı nátiyjesinde jańa saralaw algoritmına iye. Kanonik
programmada bul eki ishki sikldan ibarat : biri pútkil dızbekti basıp ótiw,
ekinshisi bolsa qashannan berli ajıratılǵan bólekten keyingi element ushın jay
tabıw. Sonday etip, ámeller sanı n*n, yaǵnıy n
2
sıyaqlı dızbek ólshemine
baylanıslı boladı.
Quramalılıqtıń basqa kórinisleri de ámeldegi, biraq olardıń
barlıǵı birdey principke tiykarlanadı.
Algoritmdıń islew waqtı ulıwma kiritilgen maǵlıwmatlardıń
kólemine baylanıslı emesligi de júz boladı. Bul halda quramalılıq O (1)
menen belgilenedi. Mısalı, dızbektiń úshinshi elementi ma`nisin
anıqlaw ushın elementlerdi eslep qalıwıńız yamasa olar arqalı bir neshe
bar ótiwińiz shárt emes. Siz mudamı maǵlıwmatlardı kirgiziw
aǵımındaǵı úshinshi elementti kútiwińiz kerek jáne bul bolsa siz ushın
nátiyje boladı, bul hár qanday maǵlıwmat ushın esaplaw ushın birdey
waqtın aladı.
Bahalaw zárúrli bolǵan táǵdirde yaddan tap sol tárzde
ámelge asıriladı. Biraq, algoritmlar kirisiw maǵlıwmatlarınıń kólemi
basqalarǵa salıstırǵanda úlkenlashganda sezilerli dárejede kóbirek yaddan
paydalanıwı múmkin, biraq olar tezirek isleydi hám kerisinshe. Bul házirgi
sharayat hám talaplar tiykarında mashqalalardi sheshiwdiń eń jaqsı
usılların tańlawǵa járdem beredi.
Algoritmlar quramalılıǵınıń ósiw tártibi
Quramalılıqtıń ósiw tártibi (yamasa hákisiomatik quramalılıq )
úlken kirisiw kólemi ushın algoritmdıń quramalılıq funksiyasınıń
shamalıq minez-qulqın xarakteristikalaydı. Bunnan kelip shıǵadıki, waqıt
quramalılıǵın bahalawda elementar ámellerdi kórip shıǵıwdıń zárúrligi
joq, algoritm qádemlerin kórip shıǵıw jetkilikli.
Algoritm qádemi - bul izbe-iz jaylastırılǵan elementar ámeller
kompleksi, onıń atqarılıw waqtı kirisiw qádemine baylanıslı emes, yaǵnıy
joqarıdan qanday da turaqlı menen shegaralanǵan.
Asimptotik bahalawdıń kórinisleri. F (n) >0 quramalılıǵın,
birdey tártip degi g (n) >0 funksiyasın, kirisiw n>0 ólshemin kórip
shıǵayıq.
Eger f (n) = O (g (n)) hám n> n
0
ushın c>0, n
> 0 konstantalar ámeldegi
bolsa, ol halda 0 0



Bul halda g (n) funksiyası f (n) ushın asimptotik-anıq baha
esaplanadı. Eger f (n) algoritmdıń quramalılıq funksiyası bolsa, ol jaǵdayda
quramalılıq tártibi f (n) ushın - O (g (n)) dep belgilenedi. Bul sóz dizbegi
turaqlı koefficiyentge shekem g (n) den tez o'smaydigan funksiyalar klasın
belgileydi.
Asimptotik funksiyalarǵa mısallar

f(n)	g(n)
2n^2+7n-3	n^2
98n*In(n)	n*In(n)
5n+2	n
8	1

1. 4. Algoritmlardıń jaman, orta, jaqsı jaǵdayları túsinikleri
Algoritm quramalılıǵınıń ósiw tártibi O (n) dep aytqanda
neni názerde qamtımız? Bul ortasha? Yamasa eń jamanı? Itimal,
eń jaqsısı?
Eger eń jaman jaǵday hám ortasha kórsetkishler bir-birinen parq
etpese, ádetde, eń jaman jaǵday názerde tutıladı. Mısalı, biz ortasha
O (1) ósetuǵın, lekin waqtı -waqtı menen O (n) ga aylanatuǵın
algoritmlardıń mısalların kórip shıǵamız (mısalı, dızbekke element
qosıw ). Bunday halda, algoritm ortasha waqıt ishinde turaqlı jumıslashini
kórsetemiz hám quramalılıq asatuǵın jaǵdaylardı túsintiremiz.
Algoritmlar hám maǵlıwmatlar strukturalarıniń quramalılıǵın
ólshewde ádetde eki zat haqqında soylesemiz: jumıstı orınlaw ushın
zárúr bolǵan ámeller sanı (esaplaw quramalılıǵı ) hám algoritm zárúr
bolǵan resurslar, atap aytqanda, yad (keńislikdegi quramalılıq ).
On teńdey tezirek isleytuǵın, biraq on ese kóbirek jay
isletetuǵın algoritm kóbirek yadlı server mashinası ushın jaqsı
Bolıwı múmkin. Biraq yad kólemi chekli ornatılǵan sistemalarda
bul algoritmnan paydalanıp bolmaydı.
Ádetde, tómendegi ámeller esapqa alınadı :
1) salıstırıwlashlar (" úlken", " kishi", " teń");
2) ózlestiriw (támiyinlew);
3) yad ajıratıw.
Qaysı ámeldi esaplaw bolsa, ádetde kontekstte anıqlanadı.
Mısalı, maǵlıwmatlar quramındaǵı elementti tabıw algoritmın
xarakteristikalawda biz derlik salıstırıwlaw ámellerin názerde qamtımız. Qıdırıw,
eń dáslep, oqıw procesi bolıp tabıladı, sol sebepli támiyinlew yamasa yad
ajıratıwda hesh qanday mánis joq.
Tártiplew haqqında sóylegende bolsa, salıstırıwlaw, yad ajıratıw hám
támiyinlew ámellerin esapqa alıwımız múmkin. Bunday jaǵdaylarda biz
qaysı ámellerdi kórip shıǵıp atırǵanimizni anıq kórsetip beremiz.
Algoritmlar teoriyasınıń tiykarların biliw hár qanday programmist
ushın júdá zárúrli bolıp tabıladı, sebebi naǵız ózi pán algoritmlardıń ulıwma
qásiyetlerin hám olardı kórsetiwdiń rásmiy modellerin
úyrenedi. Hátte informatika sabaqlarınan baslap da bizge kestelerdi
dúziwdi úyretip atırlar, bul keyinirek mektepke qaraǵanda talay
quramalı máselelerdi jazıwda járdem beredi. Bunnan tısqarı,
málim bir mashqalanı sheshiwdiń derlik mudamı bir neshe jolı
bar ekenligi sır emes: geyparaları kóp waqıt, basqa resursların jumsawdı óz
ishine aladı, basqaları bolsa tek shamalıq sheshim tabıwǵa járdem
beredi.
Siz mudamı tapsırmaqa muwapıq túrde eń maqul túsetuǵın zattı
izlewińiz kerek, atap aytqanda, máseleler klasın sheshiw algoritmların
islep shıǵıwda.
Algoritmdı hár túrlı kólem hám muǵdarlardıń baslanǵısh bahaları
menen qanday islewin, qanday dereklerge mútajlik bar ekenin hám juwmaqlawshı
nátiyjeni shıǵarıw ushın qansha waqıt ketiwin bahalaw da zárúrli bolıp tabıladı.
Kóbinese, algoritm analizi birdey máseleni sheshiw ushın eki qıylı
algoritmlardı salıstırıwlaw yamasa algoritmdıń ámeliy qollanılıwın
anıqlaw ushın isletiledi. Algoritmlardı orınlaw waqtı boyınsha
bahalawǵa toqtalamiz. Algoritmlardı orınlaw waqtına qaray
Bahalawdıń jantasıwlarınan biri bul algoritmdı ápiwayıǵana
kompyuterde jumısqa túsiriw jáne onı ol yamasa bul tárzde waqıtqa salıw bolıp tabıladı.
Bul jantasıwdıń kóplegen kemshilikleri bar. Birinshiden,
orınlaw waqtı algoritm islep atirǵan kompyuterge júdá baylanıslı.
Ekinshiden, bunday shama kirgiziw maǵlıwmatlarınıń málim bir
ólshewi ushın tek bir bahanı beredi. Eger bizde hár túrlı ólshewler
boyınsha shamalıq keste ámeldegi sonda da, odan jumıs waqtıniń kirisiw
maǵlıwmatlarınıń ólshemine funksional baylanıslılıǵın alıw júdá
mashqalalı.
Sol sebepli algoritmdı atqarılıw waqtı boyınsha bahalaw ushın
kirisiw maǵlıwmatlarınıń ólshemleri boyınsha orınlanǵan elementar
ámeller sanınıń funksional baylanıslılıǵın tabıwǵa háreket qılıw bolıp tabıladı.
Algoritm quramalılıǵınıń tiykarǵı kórsetkishi bul mashqalanı hal
qılıw ushın sarplanatuǵın waqıt hám kerekli yad kólemi.
Sonıń menen birge, máseleler klası ushın quramalılıqtı analiz qılıwda
málim bir maǵlıwmat muǵdarı - kirisiw úlkenligin xarakteristikalaytuǵın málim
bir nomer anıqlanadı. Sonday etip, biz algoritmdıń quramalılıǵı
kirisiw ólsheminiń funksiyası degen juwmaqqa keliwimiz múmkin.
Jaman, ortasha yamasa eń jaqsı dárejedegi quramalılıq
túsinikleri bar. Ádetde, eń jaman jaǵdaydıń quramalılıǵı
bahalanadı.
Eń jaman jaǵdayda waqıt quramalılıǵı - bul berilgen shama daǵı
máseleni sheshiwde algoritm islewi dawamında atqarılatuǵın
ámellerdiń maksimal sanına teń bolǵan kirisiw úlkenliginiń
funksiyası bolıp tabıladı.
Eń jaman kólemli quramalılıq - bul kirisiw kóleminiń málim
kólem degi mashqalalardi sheshiwde erisilgen maksimal yad
yacheykalari sanına teń funksiyası.
Algoritm quramalılıǵın bahalaw kriteriyalari. Birdey
me‟yorda ólshew kriteriyasi algoritmdıń hár bir basqıshı bir waqıt
birliginde, yad yacheykasi bolsa kólemdiń bir birliginde (konstanta
boyınsha anıqlıqta ) orınlanıwın názerde tutadı.