Hesaplamalı karmaşıklık teorisi
 | Bu madde hiçbir kaynak içermemektedir. (Şubat 2020) (Bu şablonun nasıl ve ne zaman kaldırılması gerektiğini öğrenin) |
Hesaplamalı karmaşıklık teorisi, hesaplama problemlerini kendi zorluklarına göre sınıflandırmaya ve bu sınıfları birbirleriyle ilişkilendirmeye odaklanan teorik bilgisayar bilimlerinde hesaplama teorisinin bir dalıdır. Bir hesaplama probleminde prensip, algoritmada belirtilen matematiksel adımların mekaniğe uygulanması yoluyla probleme yaklaşmaktır. Ve bununla beraber hesaplama karmaşıklık teorisindeki problemler, eşdeğer bir bilgisayar tarafından çözülebilen ortamlarda kullanılır.
Kullanılan algoritma ne olursa olsun, çözümünde daha fazla kaynağa ihtiyaç duyulursa, bu sorun doğal olarak zor olarak kabul edilir. Teori, bu problemleri incelemek için matematiksel hesaplama modelleri geliştirerek ve bunları çözmek için ihtiyaç duyulan zaman ve depolama gibi kaynakları nicelleştirerek bu probleme ilişkin bir perspektif çizer. İletişim miktarı (iletişim karmaşıklığında kullanılan), bir devredeki kapıların sayısı (devre karmaşıklığında kullanılır) ve işlemci sayısı (paralel hesaplamada kullanılır) gibi diğer karmaşıklık önlemleri de kullanılır. Hesaplamalı karmaşıklık teorisinin rollerinden biri, bilgisayarların yapabilecekleri ve yapamayacaklarını izah edip, pratikte ise bütün bunların sınırlarını belirlemektir.
Teorik bilgisayar bilimlerinde, algoritmalar ve hesaplanabilirlik teorisi analizi yakından ilgili alanlardır. Algoritmaların ve hesaplama karmaşıklığı teorisinin analizi arasındaki temel ayrım ise şudur:
Algoritmalarda bir problemi çözmek için belirli bir algoritma seçilip, seçilen algoritma için ihtiyaç duyulan kaynakların miktarı analiz edilir. Hesaplama karmaşıklığında ise, bir problemi çözmek için kullanılabilecek olası tüm algoritmalar ele alınarak,bunlar arasında sorular sorulur ve çözümlenmeye çalışılır. Daha kesin bir ifadeyle, hesaplama karmaşıklığı teorisi, uygun kısıtlanmış kaynaklarla çözülebilen veya çözülemeyen problemleri sınıflandırmaya çalışır.
Önemli karmaşıklık sınıfları
[değiştir | kaynağı değiştir]Birçok önemli karmaşıklık sınıfı, algoritma tarafından kullanılan zaman veya uzayı sınırlayarak tanımlanabilir. Bu şekilde tanımlanan karar problemlerinin bazı önemli karmaşıklık sınıfları şöyledir:
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Diğer önemli karmaşıklık sınıfları arasında olasılık tabanlı Turing makineleri kullanılarak tanımlanan BPP, ZPP ve RP listelenebilir.Yine örnek olarak, boolean devreleri kullanılarak tanımlanan AC ve NC sınıfları ve kuantum Turing makineleri kullanılarak belirlenmiş BQP ve QMA sınıfları verilebilir.#P ise sayım problemlerinde kullanılan önemli başka bir tür karmaşıklık sınıfıdır.ALL sınıfı ise bütün kararların sınıfıdır.
 | Bilgisayar ile ilgili bu madde taslak seviyesindedir. Madde içeriğini genişleterek Vikipedi'ye katkı sağlayabilirsiniz. |
Bilgisayar biliminin alt dalları | ||
|---|---|---|
| Matematiksel temeller |  | |
| Hesaplama teorisi | ||
| Algoritmalar ve veri yapıları | ||
| Programlama dilleri ve derleyiciler | ||
| Eşzamanlı, paralel ve dağıtık sistemler | ||
| Yazılım mühendisliği | ||
| Sistem mimarisi | ||
| Telekomünikasyon ve ağ oluşturma | ||
| Veritabanları | ||
| Yapay zekâ | ||
| Bilgisayar grafikleri | ||
| İnsan-bilgisayar etkileşimi | ||
| Bilimsel hesaplama | ||
Bilgisayar bilimi, ACM Hesaplama ve Sınıflandırma Sistemi'ne göre farklı konu ve alanlara ayrılabilir. | ||
