Baki qizlar universiteti

BAKI QIZLAR UNIVERSITETI

SERBEST IS R1-22

AD: ZEHRA

SOYAD: ISMIYEVA
IXTISAS: SOSIAL-PEDAQOJI
FAKULTE:RIYAZIYYAT VE INFORMATIKA MUELLIMLIYI
FENN: ALQORITM NEZERIYYESI
KURS: I
MUELLIM: PASAYEVA HUSNIYYE
MOVZULAR

1. 
   Markovun normal alqorifleri
   

2. 
   Alqoritmin novleri
   

3. 
   Sonlu avtomatlar
   

4. 
   Turing masinlarin formal teyini.Turing masinlarinin qurulma usullari
   

5. 
   Post masinlari formal teyini
   

1. 
   Markovun normal alqoritmleri
   

1. Əlifba və sözlərin kodlaşdırılması
2. Sözlərin çevrilməsi
3. Normal alqoritmlər
1) Bildiyimiz kimi, alqoritmlərin xassələrindən biri də onların
konstruktiv obyektlərlə işlənməsidir.Natural ədədlər, tam ədədlər, rasional
ədədlər, onların cütləri, üçlükləri, tam və ya rasional əmsallı çoxhədlilər,
rasional əmsallı xətti tənliklər və onların sistemləri belə obyektlərdir. Bu
obyektləri müəyyən sonlu əlifbanın sözləri vasitəsi ilə təsvir etmək, başqa sözlə kodlaşdırmaq olar. Qeyd edək ki, əlifba dedikdə işarələrdən
(simvollardan) ibarət sonlu çoxluq başa düşülür. Təbiidir ki, həmin çoxluq boş deyil. Əlifbanı təşkil edən simvollar onun hərifləri adlanır. Qeyd edək ki, ixtiyari təbii dilin məsələn, azərbaycan, ingilis, türk və s. dillərinin əlifbasıda elə bu cür başa düşülür.
Əlifbanın hərflərindən ibarət hər bir sonlu ardıcıllıq bu əlifbanın sözü
adlanır. Buradakı “söz” anlayışı təbii dildəki “söz” anlayışından xeyli
fərqlidir; məsələn, lüöd azərbaycan dilində heç bir məna vermədiyindən bu dilin sözü deyil.
Ümumi halda isə, konkret məna daşımasa da biz əlifbanın
simvollarının istənilən sonlu ardıcıllığından ibarət sözlərə baxacağıq.
Müəyyən obyektlərin kodlaşdırılmasına nümunələr göstərək.
Adi həyatda işlətdiyimiz kimi onluq say sistemindən istifadə etdikdə
natural ədədləri {0,1,2,3,...,9} əlifbasının sözləri şəklində, ikilik say sistemində isə {0,1} əlifbasının sözləri şəklində yazmaq olar.

Yalnız bu simvoldan – cizgidən ibarət {1} əlifbasını götürsək, bu

əlifbada I,II,III, IIII,... sözlərinə uyğun olaraq 0,1,2,3,... ədədlərinin kodları kimi baxıla bilərş Tam ədədləri iki hərfdən ibarət olan {1,-} əlifbasının sözləri vasitəsilə yazmaq olar
Bu əlifba daha bir “/” (çəp xətt) hərfini əlavə etməklə alınan üçhərfli
{1,-,1} əlifbasının sözləri ilə rasional ədədləri kodlaşdırmaq olar. Bu əlifbada
1/3, -3/4, 2/1 ədədlərini uyğun olaraq, II/III, -III/IIII, III/II şəklində
yazmaq olar. Tam ədədlərdən ibarət olan;

cədvəlini (matrisini) {0,1,-,*,□} əlifbasının sözləri ilə (“*” hərfi bir sətirdəki ədədləri “□” isə sətrləri bir-birindən ayırmaq üçündür)
IIII* -1□-III* 0
şəklində;

tənliklər sistemini {0,1,2,...,9,+,-,=,*, x, y} əlifbasında yazılmış;
2x-3y=4*+2y=-19
sözü şəklində kodlaşdırmaq olar. Alqoritmin ilkin verilənləri, aralıq və son nəticələri konstruktiv obyektlər olduğundan və bu obyektlər sonlu əlifbanın sözləri ilə təsvir edilə bildiyindən sözlər üzərində alqoritmlərə baxmaq fikri meydana çıxır.
Tutaq ki, A əlifbası cəmi iki hərfdən ibarətdir: A = {a,b}. A əlifbasının bütün sözləri çoxluğunu * A ilə işarə edək. Onda abb,ba,a,b, * aaabb A*

Sözlə daxil olan hərflər sayına sözün uzunluğu deyilir. A əlifbasının * A sözləri çoxluğuna daxil olan yuxarıdakı sözlərin uzunluğu uyğun olaraq 3,2,1,1,5- dir.

* A çoxluğunda uzunluğu 2 olan dörd söz (aa, ab,ba,bb) , uzunluğu 3
olan səkkiz söz vardır. 1 uzunluqlu sözlərin sayı isə ikiyə bərzbərdir (a,b).
Heç bir hərf saxlamayan – “0” uzunluqlu sözün mövcud olmaması daqəbul edilir. Bunu boş söz (boş çoxluğun analoqu kimi) adlandırır və A şəklində yazırlar.
Daha bir mühüm anlayışa bir sözün digərinə daxil olması münasibətinə baxaq.
Tutaq ki, müəyyən əlifbada L və M sözləri verilmişdir. Əgər L sözü
M sözünün hissəsi olarsa, deyəcəyik ki, L sözü M sözünə daxildir (və ya L
sözünün M sözünə girişi vardır). Bu zaman M sözü p1 L p2, burada p1 və p2 sözləri boş söz ola bilər. Bunların ikisi də boş söz olduqda L sözü elə M sözüdür və onlardan hər biri digərinə daxildir
Ümumiyyətlə, L sözünün M sözünə bir neçə girişi ola bilər.
Misallar.
1) L=ac; M=bacbba olduqda L sözünün M sözünə (ikinci hərfdən
başlayaraq) girişi vardır;
2) babbbaaab sözünə ab sözünün iki (birinci dəfə ikinci hərfdən,
ikinci dəfə isə səkkizinci hərfdən) girişi vardır;
3) beb sözü abcbcbab sözünə iki dəfə (birinci dəfə ikinci hərfdən,
ikinci dəfə isə dördüncü hərfdən daxildir)
Əgər M sözü p1 p2 şəklindədirsə və p1 ən kiçik uzunluğa malikdirsə buna L-in M -ə birinci girişi deyəcəyik.

Alqoritmlərin verilməsi üçün ümumi metod alqoritmik sistem adlanır. Mücərrəd əlifbanın sözlərinə əsaslanan alqoritmik sistemin tərkibinə 2 təbiətli obyektlər daxildir.

1) elementar operatorlar; 2) elementar tanıyanlar;

Elementar operatorlar verilmiş əlifba ilə təyin olunan və ardıcıl icra olunan istənilən alqoritmidir.

Elementar tanıyanlar - emal olunan alqoritmin bu və ya başqa xassələrinə dair informasiyaları tanımaq və bu tanımanın nəticəsində operatorların bir-birinin ardınca icra edilməsinə xidmət edir.

Elementar operatorların yığımının bir-birindən alınması ardığıllığını göstərmək üçün istiqamətli xüsusi qraflardan istifade edilir.

Qraf-sxemdə qrafların düyün nöqtələri bir-biri ilə birləşdirilir. Burada giriş və çıxış düyün nöqtələri vardır. Hər bir düyünə qarşı tanıyıcı var və nöqtədən düz iki qövs çıxır. Çıxış nöqtədən isa heç bir qövs çıxmır. Qraf sxemdə olan qövslərin sayı ixtiyari ola bilər.

Misal göstǝrǝk.

Giriş daxil olmanın tepe nöqtəsi üçün P və ya P(x)=0 va ya P(x)=1

Elementar operatorların təpələri üçün;

P(x) 1 va ya P(x) = 1.
elementar tanımalar üçün
P(x)=2 P(x)=2 p+(x) = 2 va ya P(x) = 2
Cixis ucun;
P+(x)=1 va ya p(x)=0 olur.

2. 
   Alqoritmin novleri
   

Alqoritmin 3 növü var.

1. Xətti alqoritm
2. Budaqlanan alqoritm
3. Dövri alqoritm

•