ÓZBEKSTAN RESPUBLIKASÍ JOQARÍ HÁM ORTA ARNAWLÍ BILIMLENDIRIW MINISTRLIGI BERDAQ ATÍNDAǴÍ QARAQALPAQ MÁMLEKETLIK UNIVERSITETI
Ámeliy matematika tálim baǵdarı 3D-kurs studenti Abdibaev Asılbektin' “Jasalma intellekt hám neyron torlı texnologiyalar” páninen
Óz betinshe jumısı
Tema:ALGORITMLERDI ANALIZLEW
Orınlaǵan: Abdibaev.A Qabıllaǵan: Urimbetova Z
Nókis – 2023
Rejesi:
Algoritm túsinigi.
Algoritmlerdiń qásiyetleri.
Algoritmlerdi analizlew.
Algoritm túsinigi. Dáslep algoritm túsinigi IX ásirde jasap dóretiwshilik etken ullı babamımız Muhammad al-Xorezmiy atı menen tıǵız baylanıslılıǵın túsindiriw kerek. Algoritm sózi al Xorezmiydiń arifmetikaǵa arnalǵan shıǵarmasınıń dáslepki betindegi “Dixit Algoritmi” (“dediki al-Xorezmiy” dıń latınsha kórinisi) 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, shekli 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ı algoritmlerden biri Evklid algoritmi (eramızǵa shekemgi III ásir) dep esaplanadı – eki sannıń eń úlken ulıwma bóliwshisin tabıw.
Algoritmlerdiń zamanagóy teoriyası nemec matematikagi Kurt Gyodel (1931) dóretpeleri menen baslandı, ol ózleriniń rásmiy, izbe-iz aksiomalar sisteması sheńberinde sheship bolmaytuǵın máseleler bar ekenligin kórsetti. Algoritmler teoriyası boyınsha birinshi fundamental jumıslar 1936-jılda payda bolǵan.
ALGORITMLERDI ANALIZLEW
Algoritm analizin, qoyılǵan máseleni bul algoritm menen sheshiw qansha waqıt talap etiwi dárejesi dep oyda sawlelendiriw múmkin. Hár bir qaralayotgan algorimtni N ólshewli baslanǵısh maǵlıwmatlar dızbekindegi máselelerdiń qanshellilik tez sheshiliwi menen bahalaymiz. Mısalı, saralaw algoritmı N ta bahadan ibarat dizimdi ósiw tártibinde jaylastırıw ushın qansha salıstırıwlaw talap etedi yamasa N*N ólshemli eki matritsani kóbeytiwde qansha arifmetik ámeller zárúr ekenligin esaplaw. Bir máseleni túrli algoritmlar menen sheshiw múmkin. Algoritmlar analizi bizge algoritmdı tańlaw ushın qural boladı. Tórtew bahadan eń úlkenin tańlaytuǵın eki algoritmdı qaraymız :
Misla:
largest = a
if b > largest then
largest = b
end if
return a
if s > largest then
largest = s end if
if d > largest then
largest = d end if
return largest
if a > b then if a > s then if a > d then
return a
else
return d end if
else
if s > d then return s
else
return d end if end if
else
if b > s then if b > d then
return b
else
return d end if
else
if s > d then
return s
else
return d
end if end if end if
Kórinip turıptı, olda, qaralayotgan algoritmlardıń hár birinde ush salıstırıwlaw atqarıladı. Birinshi algoritmdı oqıw hám túsiniw ańsat, biraq kompyuterde atqarılıw kózqarasınan olardıń quramalılıq dárejeleri teń. Bul eki algoritm waqıt kózqarasınan teń, lekin birinshi algoritm largest atlı qosımsha ózgeriwshi esabına kóbirek yad talap etedi. Egerde san yamasa belgiler salıstırıwlansa, bul qosımsha ózgeriwshi úlken áhmiyetke iye bolmaydı, lekin basqa túrdegi maǵlıwmatlar menen islegende bul zárúrli áhmiyetke iye. Kóplegen zamanagóy programmalastırıw tilleri úlken hám quramalı ob'ektlerdi yamasa jazıwlardı salıstırıwlaw operatorların anıqlaw imkaniyatın beredi. Bunday jaǵdaylarda qosımsha ózgeriwshilerdi jaylastırıw úlken jay talap etedi. Algoritmlardıń effektivligini analizi qılıwda bizni birinshi náwbette waqıt máselesi qızıqtiradi, biraq yad zárúrli rol atqaratuǵın jaǵdayda onı da talqılaw etemiz. Algoritmlaring túrli ózgeshelikleri bir máseleni sheshiwshi eki túrdegi algoritmlardıń effektivligini salıstırıwlaw ushın xızmet etedi. Biz sol sebepli hesh qashan matritsalarni kóbeytiw algoritmı menen saralaw algoritmın emes, bálki eki túrli saralaw algoritmların bir-biri menen salıstırıwlaymız.
Algoritm analiziniń nátiyjesi - belgilengen algoritmdıń kompyuterden qansha waqıt yamasa tákirarlaw talap etiwin anıq esaplaytuǵın formula emes. Bunday maǵlıwmat zárúrli emes, bul jaǵdayda kompyuter túri, ol bir yamasa odan artıq paydalanıwshı tárepinen isletilyaptimi, onıń protsessori hám chastotası qanday, protsessor chipida komandalar tolıqpa hám kompilyator atqarılıp atırǵan kodtı qaysı dárejede ámelge asırıp atır sıyaqlı táreplerdi názerde tutıw kerek. Bul shártler algoritm atqarılıw nátiyjesinde programmanıń islew tezligine tásir etedi. Joqarıdaǵı shártler esabına programmanı basqa tez isleytuǵın kompyuterge ótkerilgende algoritm jaqsı islegendey orınlanıwı tezirek ámelge asadı. Tiykarınan bolsa oday emes, biz sol sebepli analizimizde kompyuterdiń múmkinshiliklerin inabatqa almaymız.
Ápiwayı hám úlken bolmaǵan programmalarda atqarılatuǵın ámeller sanın N dıń funkciyası kórinisinde anıq esaplaw múmkin. Kópshilik jaǵdaylarda buǵan zárúriyat qalmaydı. 8. 4 § de keltirilgen N =5 hám N =250 ta ámel atqarılatuǵın eki algoritm arasında N dıń jetkiliklishe úlken bahalarında derlik parq bolmaydı. Soǵan qaramay, biz algoritmlardı atqarılatuǵın ámeller sanına qaray analiz etemiz.
Algoritm tárepinen atqarılatuǵın processler bar, biz olardıń hámmesin esaplab o'tirmaymiz, óytkeni sonda, hátte onıń eń kishi sazlawı da nátiyjelililiktiń sezilmas jaqsılanıwına alıp keledi. Mısalı, fayl daǵı túrli belgiler sanın esaplaytuǵın algoritmdı qaraymız. Bul másele sheshimi ushın algoritmdıń shamalıq kórinisi tómendegishe boladı :
for all 256 belgilerdi do
esaplagichni nolge teńles end for
while eger faylda belgi qalsa do
náwbettegi belgin kórset hám esaplagichni birge asır end while do
esaplagichni nolge teńlestiriw end for
while faylda belgi ámeldegi bolsa do
náwbettegi belgin kórset hám esaplagichni birge asır
end while
Bul algoritmdı kórip shıǵamız. Ol tákirarlanıw orınlanıwında 256 ótiw etedi. Eger berilgen faylda N ta belgi bolsa ol jaǵdayda ekinshi tákirarlanishda N ta ótiw etiledi. «Bul qanday esaplaw? » degen soraw tuwıladı. For siklida aldın cikl ózgeriwshisi atqarıladı, keyin hár bir ótiwde onıń cikl shegarasınan shıqpayotganligi tekseriledi hám ózgeriwshi ma`nisin asıradı. Bul bolsa cikl orınlanıwında 257 júklew atqarıladı (biri cikl ózgeriwshisi, 256 tasi esaplaǵısh ushın ), yaǵnıy 256 asırıw hám 257 cikl shegarasınan shıqpaǵanlıǵın tekseriw (bir ámel siklni toqtatıw ushın qosılǵan ). Ekinshi siklda N + 1 ret shárt tekseriledi (+1 fayl bos bolǵandaǵı aqırǵı tekseriw), hám N esaplagichni asırıw. Jámi ámeller:
Oshirish
|
