Teorik bilgisayar bilimi ve matematikte, hesaplama teorisi, bir hesaplama modelinde hangi problemlerin bir algoritma kullanılarak çözülebileceğini, bunların ne kadar verimli bir şekilde veya ne dereceye kadar çözülebileceğini (örneğin, yaklaşık çözümlere karşı kesin çözümler) ele alan daldır.
Alan üç ana dala ayrılmıştır: otomata teorisi ve biçimsel diller,
hesaplanabilirlik teorisi ve hesaplama karmaşıklığı teorisi; bunlar şu soruyla
bağlantılıdır: 'Bilgisayarların temel yetenekleri ve sınırlamaları nelerdir?'.
Bilgisayar bilimciler, titiz bir hesaplama çalışması gerçekleştirmek
için, hesaplama modeli adı verilen, bilgisayarların matematiksel bir
soyutlaması üzerinde çalışırlar. Kullanımda olan birçok model vardır ancak en
çok inceleneni Turing makinesidir.
Bilgisayar bilimcilerin Turing makinesi üzerinde çalışıyorlar, çünkü
formüle edilmesi basittir, analiz edilebiliyor ve sonuçları kanıtlamak için
kullanılabiliyor ve çoğu kişinin mümkün olan en güçlü ‘makul’ hesaplama
modelini temsil ediyor.
Potansiyel olarak sonsuz hafıza kapasitesi gerçekleştirilemez bir
özellik gibi görünebilir, ancak bir Turing makinesi tarafından çözülebilen
herhangi bir karar verilebilir problem her zaman yalnızca sınırlı miktarda
hafıza gerektirecektir. Dolayısıyla prensipte, bir Turing makinesi tarafından
çözülebilen (karar verilebilen) herhangi bir problem, sınırlı miktarda belleğe
sahip bir bilgisayar tarafından çözülebilir.
Dallar
·
Otomata teorisi: Otomata teorisi, soyut
makinelerin ve bu makineleri kullanarak çözülebilecek hesaplama problemlerinin
incelenmesidir.
o Biçimsel
dil teorisi: Dil teorisi, dilleri bir alfabe üzerindeki işlemler dizisi olarak
tanımlamayla ilgilenen bir matematik dalıdır. Otomatlar biçimsel dilleri
oluşturmak ve tanımak için kullanıldığından, otomat teorisi ile yakından
bağlantılıdır.
·
Hesaplanabilirlik teorisi: Hesaplanabilirlik
teorisi öncelikle bir problemin bilgisayarda ne ölçüde çözülebileceği sorusuyla
ilgilenir.
· Hesaplamalı karmaşıklık teorisi: Karmaşıklık teorisi, yalnızca bir problemin bilgisayarda çözülüp çözülemeyeceğini değil, aynı zamanda problemin ne kadar verimli bir şekilde çözülebileceğini de dikkate alır.
Şekil (e) ile ilgili
açıklamalar; hesaplamalı karmaşıklık teorisinde:
EXPSPACE, üstel uzayda deterministik
bir Turing makinesi tarafından çözülebilen tüm karar problemlerinin kümesidir.
EXPTIME karmaşıklık sınıfı,
deterministik bir Turing makinesi tarafından üstel zamanda çözülebilen tüm
karar problemlerinin kümesidir.
PSPACE, polinom miktarında bir
alan kullanan bir Turing makinesi tarafından çözülebilen tüm karar
problemlerinin kümesidir.
NP (deterministik olmayan
polinom zamanı), karar problemlerini sınıflandırmak için kullanılan bir
karmaşıklık sınıfıdır.
P: Polinom miktarda hesaplama
süresi veya polinom süresi kullanılarak deterministik bir Turing makinesi
tarafından çözülebilecek tüm karar problemlerini içerir.
NL (deterministik olmayan
logaritmik uzay), logaritmik miktarda bellek alanı kullanan deterministik
olmayan bir Turing makinesi tarafından çözülebilen karar problemlerini içeren
karmaşıklık sınıfıdır.
https://en.wikipedia.org/wiki/Theory_of_computation
28 Ocak 2024
GERİ (matematik anasayfa)
