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]
- 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]
- 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ı.
- 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.
- Təsadüfi alqoritmlər — həll prosesi təsadüfi ədədlərə əsaslanan metodlarla həyata keçirilir.
- 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.
| Qrammatika | Maşın | İstehsal qaydaları (məhdudiyyətlər) | |
|---|---|---|---|
| 0-cı tip | Rekursiv sadalanan | Türinq maşını | (məhdudiyyətsiz) |
| 1-ci tip | Kontekstdən aslı | Xətti məhdud qeyri-deterministik Türinq maşını | |
| 2-ci tip | Kontekstdən azad | Qeyri-deterministik jurnal yaddaşlı avtomatik maşın | |
| 3-cü tip | Müntəzəm | Sonlu vəziyyətli avtomat | və |
- ↑ Hodges, Andrew. Alan Turing: The Enigma (The Centenary). Princeton University Press. 2012. ISBN 978-0-691-15564-7.
- ↑ 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)
- ↑ 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.
- ↑ Donald Monk. Mathematical Logic. Springer-Verlag. 1976. ISBN 9780387901701.