Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
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ı
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 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 seviyesindedir. Madde içeriğini genişleterek Vikipedi'ye katkı sağlayabilirsiniz. |
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Hesaplamali karmasiklik teorisi hesaplama problemlerini kendi zorluklarina gore siniflandirmaya ve bu siniflari birbirleriyle iliskilendirmeye odaklanan teorik bilgisayar bilimlerinde hesaplama teorisinin bir dalidir Bir hesaplama probleminde prensip algoritmada belirtilen matematiksel adimlarin mekanige uygulanmasi yoluyla probleme yaklasmaktir Ve bununla beraber hesaplama karmasiklik teorisindeki problemler esdeger bir bilgisayar tarafindan cozulebilen ortamlarda kullanilir Karmasiklik siniflari arasindaki iliskinin bir gosterimi Kullanilan algoritma ne olursa olsun cozumunde daha fazla kaynaga ihtiyac duyulursa bu sorun dogal olarak zor olarak kabul edilir Teori bu problemleri incelemek icin matematiksel hesaplama modelleri gelistirerek ve bunlari cozmek icin ihtiyac duyulan zaman ve depolama gibi kaynaklari nicellestirerek bu probleme iliskin bir perspektif cizer Iletisim miktari iletisim karmasikliginda kullanilan bir devredeki kapilarin sayisi devre karmasikliginda kullanilir ve islemci sayisi paralel hesaplamada kullanilir gibi diger karmasiklik onlemleri de kullanilir Hesaplamali karmasiklik teorisinin rollerinden biri bilgisayarlarin yapabilecekleri ve yapamayacaklarini izah edip pratikte ise butun bunlarin sinirlarini belirlemektir Teorik bilgisayar bilimlerinde algoritmalar ve hesaplanabilirlik teorisi analizi yakindan ilgili alanlardir Algoritmalarin ve hesaplama karmasikligi teorisinin analizi arasindaki temel ayrim ise sudur Algoritmalarda bir problemi cozmek icin belirli bir algoritma secilip secilen algoritma icin ihtiyac duyulan kaynaklarin miktari analiz edilir Hesaplama karmasikliginda ise bir problemi cozmek icin kullanilabilecek olasi tum algoritmalar ele alinarak bunlar arasinda sorular sorulur ve cozumlenmeye calisilir Daha kesin bir ifadeyle hesaplama karmasikligi teorisi uygun kisitlanmis kaynaklarla cozulebilen veya cozulemeyen problemleri siniflandirmaya calisir Onemli karmasiklik siniflariBircok onemli karmasiklik sinifi algoritma tarafindan kullanilan zaman veya uzayi sinirlayarak tanimlanabilir Bu sekilde tanimlanan karar problemlerinin bazi onemli karmasiklik siniflari soyledir Karmasiklik sinifi Hesaplama modeli Kaynagin siniriDeterministik zaman f n Deterministik Turing makinesi Zaman f n Deterministik Turing makinesi Zaman poly n Deterministik Turing makinesi Zaman 2poly n Deterministik olmayan zaman f n Deterministik olmayan Turing makinesi Zaman f n Deterministik olmayan Turing makinesi Zaman poly n Deterministik olmayan Turing makinesi Zaman 2poly n Karmasiklik sinifi Hesaplama modeli Kaynagin siniriDeterministik uzay f n Deterministik Turing makinesi Uzay f n Deterministik Turing makinesi Uzay O log n Deterministik Turing makinesi Uzay poly n Deterministik Turing makinesi Uzay 2poly n Deterministik olmayan uzay f n Deterministik olmayan Turing makinesi Uzay f n Deterministik olmayan Turing makinesi Uzay O log n Deterministik olmayan Turing makinesi Uzay poly n Deterministik olmayan Turing makinesi Uzay 2poly n Diger onemli karmasiklik siniflari arasinda olasilik tabanli Turing makineleri kullanilarak tanimlanan BPP ZPP ve RP listelenebilir Yine ornek olarak boolean devreleri kullanilarak tanimlanan AC ve NC siniflari ve kullanilarak belirlenmis BQP ve QMA siniflari verilebilir P ise sayim problemlerinde kullanilan onemli baska bir tur karmasiklik sinifidir ALL sinifi ise butun kararlarin sinifidir Bilgisayar ile ilgili bu madde taslak seviyesindedir Madde icerigini genisleterek Vikipedi ye katki saglayabilirsiniz