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^[1]. 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.^[2]

Ə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.^[3]
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]
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ı	${\displaystyle \alpha \rightarrow \beta }$ (məhdudiyyətsiz)
1-ci tip	Kontekstdən aslı	Xətti məhdud qeyri-deterministik Türinq maşını	${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$
2-ci tip	Kontekstdən azad	Qeyri-deterministik jurnal yaddaşlı avtomatik maşın	${\displaystyle A\rightarrow \gamma }$
3-cü tip	Müntəzəm	Sonlu vəziyyətli avtomat	${\displaystyle A\rightarrow a}$ və ${\displaystyle A\rightarrow aB}$

İstinadlar

1. Hodges, Andrew. Alan Turing: The Enigma (The Centenary). Princeton University Press. 2012. ISBN 978-0-691-15564-7.
2. Michael Sipser. Introduction to the Theory of Computation 3rd. Cengage Learning. 2013. ISBN 978-1-133-18779-0. central areas of the theory of computation: automata, computability, and complexity. (Page 1)
3. Rabin, Michael O. Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. June 2012. 2019-06-05 tarixində arxivləşdirilib. İstifadə tarixi: 2024-10-27.
4. Donald Monk. Mathematical Logic. Springer-Verlag. 1976. ISBN 9780387901701.