3-Laboratoriyalıq jumıs. Tyuring mashinasın jasaw. Jumıstıń maqseti

1-Laboratoriyalıq jumısı. Algoritmlardi analizlew.

Jumıstıń maqseti: Algoritmler túrleri menen tanısıw hám analizlew hám olardı járiyalaw.
Qoyilgan masala: Algoritmlerni jaratıw hám olarǵa baylanıslı mısallardıń programmasın islep shıǵıw.
Islew tártibi:

• 
  Laboratoriyalıq jumıstıń teoriyalıq maǵlıwmatların úyreniw;
  
• 
  Berilgen tapsırmanıń algoritmin islep shıǵıw;
  
• 
  C++ tilinde programmasın jaratıw;
  
• 
  Nátiyjelerdi tekseriw;
  
• 
  Esabattı tayarlaw hám tapsırıw.
  

Teoriyalıq maǵlıwmatlar

Algoritmlerdi analiz etiwdiń maqseti – algoritmlerge maǵlıwlmatlardı anıq, nátiyjeli qayta islew ushın kerek bolatuǵın yad kólemi islew waqtınıń bahaları hám shegaraların alıw bolıp esaplanadı. Algoritmler tiykarınan programmalıq qayta erisiw ushın isletiledi. Biz bir pikr yaki shablondı C, C++ yaki Java sıyaqlı tillerde ámelge asırıp sheshim qabıl etiwimiz múmkin. Algoritm tiykarınan bir mashqalanıń sheshiliw usillarınıń kórsetpeler jıynaǵı bolıp tabıladı. Bul kem bolmaǵan kóp sanlı algoritmli mashqalalardı sheshiw ushın qollanıladı, biraq belgili bir dárejedegi algoritmdi saylap alıw lazım.
2 dana analiz qilinǵan algoritmlerden birewiniń orınlaniw waqti tezirek boladi, oni yad kólemi boyinshada analiz qiliw kerek hám bunday analizler quramaliliq teoriyasına tuwri keledi.
Maxsimumdi tabiw máselesi.
X1,x2,…,xn berilgen elementler boyinsha m hám j lardi sonday tabiń m=max xk{1<=k<=n}=xj bolsin. Bul jerde j múmkin bolǵaninsha maksimal bolsin.
Sózli algoritm:

1. 
   Baslaniw
   
2. 
   j:=n;k:=n-1;m:=xn;
   
3. 
   eger k::=0 bolsa onda 7 ótiń
   
4. 
   eger xk<=m bolsa onda 6 ótiń
   
5. 
   j:=k;m:=xk;
   
6. 
   k:=k-1; 3 ótiń
   
7. 
   Tamam
   

Algoritm apiwayi hám analizge mútaj emes dep esaplanadi. Biraq bul misalda quramalialgoritm qalayinsha analiz qiliw kerekligin kórsetiwi múmkin. Algoritm analizi programmalastiriw ushın juda kerek.
Biz tek ǵana bul algoritmdi orınlaw ushın kerek bolatuǵin waqıtti analiz qilamiz. Buniń ushın har bir adim neshe márte orınlaniwin esaplaymiz:

Adim nomeri	Neshe márte orınlaniwi
2	1
3	N
4	n-1
5	A
6	n-1

Hár bir adim neshe márte orınlanǵanin bilgen jaǵdayda kompyuterge máseleni orınlaw ushın qansha waqıt kerek ekenligin esaplap shiǵiw múmkin.

Kesteda A dan tisqari hamme mánisler belgili.A- bul maksimum mánisti neshe márte ózgertiw kerekligi kórsetkishi. Analizimiz toliq boliwi ushın Ani kórip shiǵamiz. Analizlewden maqsetimiz A ushın minimum hám maksimum mánislerdi tabiw.

1. 
   MinA=0,
   

Bul jaǵday xn=max xk {1<=k<=n} bolǵanda kóriledi.

2. 
   MaxA=n-1;
   

Bul mániske x1>x2>…>xn bolǵanda erisiledi.
Solay etip Aniń analizi 0 hám n-1 lerdiń orta arifmetik mánisi hám orta kvadrati járdeminde tabiw máselesine alip keledi.

Evklid algoritmi:

Masalaniń qoyilishi.
Eki oń m hám n sanlari berilgen. Olardiń uliwma bóliwshisin tabiw talap qilinadi. Yaǵniy eń ulken pútin oń san tabiw kerek, oǵan m hám n di bólgende pútin san shiqsin.