Alqoritmlər nəzəriyyəsi

Vikipediya, azad ensiklopediya
Naviqasiyaya keç Axtarışa keç

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

[redaktə | mənbəni redaktə et]
  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.

Avtomat nəzəriyyəsi

[redaktə | mənbəni redaktə et]
Qrammatika Dillər 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

  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.