Alqoritmlər nəzəriyyəsi

Alqoritmlər nəzəriyyəsi (ing. Theory of computation) — hesablama nəzəriyyəsinin bir sahəsidir və müəyyən bir tapşırığı həll etmək üçün dəqiq addımların müəyyənləşdirilməsinə yönəlmişdir. Bu nəzəriyyə informasiyanın işlənməsinin, avtomatlaşdırılmış qərar qəbulunun və verilənlər üzərində müxtəlif əməliyyatların həyata keçirilməsinin əsasını təşkil edir.

Əsas sahələri

1. Alqoritmlərin effektivliyi və mürəkkəbliyi — alqoritmlərin hansı resurslardan (zaman və yaddaş) nə dərəcədə səmərəli istifadə etdiyini araşdırır.
2. Qraf nəzəriyyəsi — qovşaqlar və kənarlardan ibarət qraf strukturlarının araşdırılması, məsələn, qısa yol tapma və qrafda axtarış metodları.
3. Dinamik proqramlaşdırma — təkrarlanan altproblemləri yadda saxlamaqla daha böyük problemləri həll etməyə yönəlmiş metod.
4. Qridi metodları — verilən problemi yerinə yetirmək üçün hər mərhələdə ən yaxşı yerli seçimi etməklə optimal nəticəyə çatmağa çalışır.
5. Təsadüfi alqoritmlər — həll prosesi təsadüfi ədədlərə əsaslanan metodlarla həyata keçirilir.
6. Paralel və paylanmış alqoritmlər — alqoritmlərin çoxsaylı prosessor və ya kompüterlərdə yerinə yetirilməsi ilə əlaqədardır.

Alqoritmlərin nəzəriyyəsi həm də NP-tamlıq, hesablama çətinliyi sinifləri, qərarvermə alqoritmləri kimi sahələri əhatə edir və optimal həllərin tapılması üçün yeni metodların işlənib hazırlanmasına əsaslanır.

Növləri

Avtomat nəzəriyyəsi

Qrammatika	Dillər	Maşın	İstehsal qaydaları (məhdudiyyətlər)
0-cı tip	Rekursiv sadalanan	Türinq maşını	$\alpha \rightarrow \beta$ (məhdudiyyətsiz)
1-ci tip	Kontekstdən aslı	Xətti məhdud qeyri-deterministik Türinq maşını	$\alpha A\beta \rightarrow \alpha \gamma \beta$
2-ci tip	Kontekstdən azad	Qeyri-deterministik jurnal yaddaşlı avtomatik maşın	$A\rightarrow \gamma$
3-cü tip	Müntəzəm	Sonlu vəziyyətli avtomat	$A\rightarrow a$ və $A\rightarrow aB$