Atqardı : Bayniyazov. O qabılladı : Qutlimuratov. Y joba

Nukus Innovatsion Instituti IT injenering qanigeligi 1-kurs studenti Bayniyazov Orinbasardin' Algaritim ham belgiler strukturalari pa’ninen

O’zbetinshe jumısi
v

Tema : Algoritmlardıń eń jaman hám ortasha jaǵdayın bahalaw.
Atqardı : Bayniyazov.O
Qabılladı : Qutlimuratov.Y
Joba :
1. Nátiyjelililik kórsetkishleri.
2. Esaplaw qábileti
3. Algoritmlardı asimptotik tártipleri.
4. Polinomial waqıt nátiyjelililik kórsetkishi retinde

1. Nátiyjelililik kórsetkishleri.

Algoritmlardı analiz qılıwdıń tiykarǵı waziypası kirisiw maǵlıwmatları kóleminiń asıp barıwı menen resurslarǵa bolǵan talaptı (waqıt hám yad ǵárejetleri) ólshew usılların anıqlaw bolıp tabıladı. Sonnan keyin, ósiw páti nizamlıqların xarakteristikalaw ushın zárúr bolǵan matematikalıq mexanizm islep shıǵıladı. Kirisiw maǵlıwmatları kólemin asırıw menen hár qıylı funkciyalar ; " bir funkciya basqasına qaraǵanda tezirek ósedi" sóz dizbegi neni ańlatıwın anıqlap alıwǵa járdem beredi. Birpara jaǵdaylarda, jaqsı atqarılıw waqtına erisiw jáne de quramalı maǵlıwmatlar strukturalarınan paydalanıwǵa baylanıslı hám bólim aqırında biz bunday maǵlıwmatlar strukturasınıń júdá paydalı mısalın kórip shıǵamız : ústin turatuǵın gezekler hám olardı úyin (kúsha, heap) tiykarında ámelge asırıw.
Tiykarǵı tema - esaplaw máseleleriniń nátiyjeli algoritmların izlew. Bul ulıwmalıq dárejesinde kompyuterdi esaplawdıń pútkil tarawı bul tema menen baylanıslı bolıp tuyuladi; biziń jantasıwımız basqalardan qanday parıq etedi? Algoritmlardı islep shıǵıwda ulıwma temalar hám proektlestiriw principlerıni anıqlawǵa háreket etemiz. Bizni nátiyjeli algoritmlardı proektlestiriwdiń tiykarǵı usılların minimal maǵlıwmat menen kórsetiw etiwshi paradigmatik máseleler hám usıllar qızıqtiradi.
2. Esaplaw qábileti
Kóplegen máselelerde ushraytuǵın taǵı bir ózgeshelik - bul olardıń tiykarlanıp diskretligi. Kóplegen máselelerde ushraytuǵın taǵı bir ózgeshelik-bul olardıń tiykarǵı ajralıp turıwı. Basqasha etip aytqanda, bul sonday máselelerki, olarda sheshim kombinatorial variantlardıń keń kompleksinen izlep tabıladı ; maqset anıq belgilengen shártlerdi qánaatlantiradigan sheshimdi nátiyjeli tabıw bolıp tabıladı.
Esaplaw natiyjeliligi túsinigin anıqlaw ushın, biz birinshi náwbette jumıs waqtıniń natiyjeliligine itibar qaratamız : algoritmlar tez islewi kerek. Biraq algoritmlar basqa resursrlardan paydalanıw kózqarasınan da nátiyjeli bolıwı múmkinligin túsiniw zárúrli bolıp tabıladı. Atap aytqanda, algoritm tárepinen isletilinadigan yad muǵdarı da nátiyjelililiktiń zárúrli jixati bolıwı múmkin.

Algoritm natiyjeliligi

(1) T: algoritm nátiyjeli dep ataladı eger real kirisiw maǵlıwmatları ushın ol operativ ámelge asırılsa.
(2) T: algoritm nátiyjeli dep ataladı eger ol sapalı atqarılıwdı “tolıq qıdırıw” (polniy perebor) ga salıstırǵanda tezirek támiyinlasa.
" Tolıq qıdırıw" usılına qaraǵanda talay jaqsı islewdi támiyinleytuǵın algoritmlar, derlik mudamı qımbatlı evristik ideyanı óz ishine aladı, bunıń nátiyjesinde bul jaqsılanishga eriwiladi; Bunnan tısqarı, olar kórip shıǵılıp atırǵan máseleniń ishki dúzilisi hám esaplaw qábileti haqqında paydalı maǵlıwmatlardı usınıs etediler.
Polinomial waqıt nátiyjelililik kórsetkishi retinde
Tábiyiy kombinatorial máselelerde qıdırıw waqtı, kirisiw maǵlıwmatları N kólemine salıstırǵanda eksponensional ósiwge beyim bolıp tabıladı; eger ólshem birge kópaysa, ol jaǵdayda múmkinshilikler kolemi bir neshe ret kópayadi. Bunday máselelerdi sheshiw ushın jaqsı algoritm jáne de nátiyjeli kólemlew modeline ıyelewi kerek; kirisiw maǵlıwmatlarınıń úlkenlesip barıwı menen ózgermeytuǵın kópaytuvchiga (aytaylik, eki ese) asıwı menen algoritmdıń atqarılıw waqtı da qanday da ózgermeytuǵın S kópaytuvchiga kóbeyiwi kerek.
Matematikalıq kózqarastan bul masshtablaw modelin tómendegishe qáliplestiriw múmkin. Aytaylik, algoritm tómendegi ózgeshelikke iye: c> 0 hám d> 0 absolyut konstantalar barki, hár qanday N kólemli kirisiw maǵlıwmatları kompleksi ushın, atqarılıw waqtı cN^d sandaǵı eń ápiwayı operatsiyalar sanı menen shegaralanadı. Basqasha etip aytqanda, atqarılıw waqtı N^d ga proportsionallıqtan kóp emes. Qanday bolmaydıin, birpara c hám d lar ushın atqarılıw waqtı bul shegaradan aspaǵanda, algoritm polinomial atqarılıw waqtın támiyinleydi deymiz yamasa ol polinomial waqıtqa iye bolǵan algoritmlar qatlamına kiredi.polinomial waqıtqa iye hár qanday shegara joqarıdaǵı masshtablawǵa iye boladı.
(3) T: Eger algoritm polinomial atqarılıw waqtına iye bolsa, ol nátiyjeli dep ataladı.
Lekin, polinomial waqıt d dıń úlken bahalarında jaqsı nátiyje bermasligi múmkin, mısalı d>=100 jaǵdayda bul san kútá úlken boladı, nátiyjede polinomial atqarılıw waqtı úlkenlesip ketedi. Algoritm isleyveradi. Bul túrde N^d tek shegara wazıypasın oteydi.
Polinomial waqıtqa iye bolǵan algoritmlar ámeldegi bolǵan máseleler ushın bul algoritmlar derlik mudamı n, n*log n, n^2 yamasa n^3 sıyaqlı ortasha ósiw páti menen kópaytuvchilarga proporcional túrde isleydi. hám kerisinshe, Polinomial waqıtqa iye bolmaǵan algoritmlı máseleler ushın atqarılıw waqtı oǵırı úlkenlesip ketedi, onı bahalaw belgisiz boladı, ádetde bunday máselelerdi sheshiw júdá quramalı bolıp shıǵadı. Ulıwma alǵanda, bunday bahalawlar birpara máselelerde dárejediń yamasa koefficiyentlerdiń úlkenligi sebepli jaqsı nátiyje bermeydi, algoritm jaqsı sonda da. Ájepsi mınada, kóbinese polinomial waqtın matematikalıq anıqlaw algoritmlardıń natiyjeliligi hám real turmıs daǵı máselelerdi sheshiw boyınsha baqlawlarımız menen sáykes keledi. Bunday máselelerdi polinomial sheshiw múmkin bolǵan máseleler dep ataladı. Sonday eken, 3-tariypni málim mániste talapǵa juwap beretuǵın tariyp desek baladı. Ol túrde Polinomial waqıtqa iye bolmaǵan algoritmlardı qayta kórip shıǵıw kerek.
Polinomial waqıtqa iye bolǵan algoritmlardı islep shıǵıw ne ucgun zárúr ekenligin tómendegi keste maǵlıwmatların analiz etip biliw múmkin. Algoritmlardıń islew waqıtları