EITC/IS/CCTF Hesaplamalı Karmaşıklık Teorisinin Temelleri, aynı zamanda İnternette yaygın olarak kullanılan klasik asimetrik açık anahtarlı şifrelemenin temeli olan bilgisayar biliminin temellerinin teorik yönleri üzerine Avrupa BT Sertifikasyon programıdır.
EITC/IS/CCTF Hesaplamalı Karmaşıklık Teorisi Temelleri müfredatı, bilgisayar biliminin temelleri hakkında teorik bilgileri ve deterministik ve deterministik olmayan sonlu durum makineleri, düzenli diller, bağlamdan bağımsız gramerler ve diller teorisi, otomata teorisi, Turing gibi temel kavramlar üzerine hesaplamalı modelleri kapsar. Bu EITC Sertifikasyonu için referans olarak kapsamlı video didaktik içeriği kapsayan, aşağıdaki yapı içinde temel güvenlik uygulamaları için makineler, sorunların karar verilebilirliği, özyineleme, mantık ve algoritmik karmaşıklık.
Bir algoritmanın hesaplama karmaşıklığı, onu çalıştırmak için gereken kaynak miktarıdır. Zaman ve hafıza kaynaklarına özel önem verilir. Bir problemin karmaşıklığı, onu çözmek için en iyi algoritmaların karmaşıklığı olarak tanımlanır. Algoritmaların analizi, açıkça verilen algoritmaların karmaşıklığının incelenmesidir, hesaplama karmaşıklığı teorisi ise en iyi bilinen algoritmalarla problem çözümlerinin karmaşıklığının incelenmesidir. Her iki alan da iç içedir, çünkü bir algoritmanın karmaşıklığı, çözdüğü problemin karmaşıklığı üzerinde her zaman bir üst sınırdır. Ayrıca, verimli algoritmalar oluştururken belirli bir algoritmanın karmaşıklığını, çözülecek problemin karmaşıklığıyla karşılaştırmak sıklıkla gereklidir. Çoğu durumda, bir problemin zorluğuyla ilgili mevcut olan tek bilgi, bunun bilinen en verimli tekniklerin karmaşıklığından daha az olduğudur. Sonuç olarak, algoritma analizi ve karmaşıklık teorisi arasında çok fazla örtüşme vardır.
Karmaşıklık teorisi, yalnızca bilgisayar biliminin temeli olarak hesaplama modellerinin temellerinde değil, aynı zamanda modern ağlarda, özellikle internette yaygın olarak kullanılan klasik asimetrik kriptografinin (açık anahtarlı kriptografi olarak adlandırılır) temellerinde de önemli bir rol oynar. Açık anahtar şifrelemesi, örneğin büyük sayıları asal faktörlerine ayırma gibi belirli asimetrik matematiksel problemlerin hesaplama zorluğuna dayanır (bu işlem karmaşıklık teorisi sınıflandırmasında zor bir problemdir, çünkü çözülecek bilinen verimli klasik algoritmalar yoktur. orijinal büyük sayıyı vermek için bilinen asal faktörlerle çarpmanın çok basit bir ters işleminin aksine, sorunun giriş boyutunun artmasıyla üstel olarak değil, polinom olarak ölçeklenen kaynaklarla). Bu asimetriyi açık anahtar şifreleme mimarisinde kullanmak (genel anahtar arasında, özel bir anahtardan kolayca hesaplanabilen, hesaplamalı olarak asimetrik bir ilişki tanımlayarak, özel anahtar bir açık anahtardan kolayca bilgisayar olamazken, genel olarak açık anahtarı duyurur ve diğer iletişim taraflarının bunu, verilerin asimetrik şifrelemesi için kullanmasını sağlar; bu, daha sonra yalnızca birleştirilmiş özel anahtarla şifresi çözülebilir, üçüncü taraflara hesaplamalı olarak sunulmaz, böylece iletişimi güvenli hale getirir).
Hesaplamalı karmaşıklık teorisi, esas olarak, İkinci Dünya Savaşı'nı kazanan müttefiklerde derin bir rol oynayan Nazi Almanyası'nın Enigma şifresini kırmada kritik öneme sahip olan Alan Turing gibi bilgisayar bilimi ve algoritmik öncülerinin başarıları üzerine geliştirildi. Gizli bilgileri ortaya çıkarmak için verilerin (esas olarak şifreli iletişim) analiz edilmesinin hesaplama süreçlerini tasarlamayı ve otomatikleştirmeyi amaçlayan şifreleme analizi, kriptografik sistemleri ihlal etmek ve genellikle stratejik askeri öneme sahip şifreli iletişimin içeriğine erişim sağlamak için kullanıldı. Aynı zamanda ilk modern bilgisayarların (başlangıçta stratejik bir kod kırma hedefine uygulanan) gelişimini katalize eden de kriptanalizdi. British Colossus'tan (ilk modern elektronik ve programlı bilgisayar olarak kabul edilir) önce, Marian Rejewski tarafından Enigma şifrelerini kırmaya yardımcı olmak için tasarlanan ve Polonya istihbaratı tarafından Büyük Britanya'ya teslim edilen elektronik bir hesaplama cihazı olan Polonya "bombası" vardı. Polonya'nın 1939'da Almanya tarafından işgal edilmesinden sonra ele geçirilen Alman Enigma şifreleme makinesi. Alan Turing, bu cihaz temelinde, daha sonra modern bilgisayarlara dönüştürülecek olan Alman şifreli iletişimini başarıyla kırmak için daha gelişmiş muadilini geliştirdi.
Bir algoritmayı çalıştırmak için gereken kaynak miktarı girdinin boyutuna göre değiştiğinden, karmaşıklık genellikle f(n) işlevi olarak ifade edilir; burada n girdi boyutudur ve f(n) ya en kötü durum karmaşıklığıdır ( n boyutundaki tüm girdiler için gereken maksimum kaynak miktarı) veya ortalama durum karmaşıklığı (n boyutundaki tüm girdiler üzerindeki kaynak miktarının ortalaması). n boyutundaki bir girdi üzerindeki gerekli temel işlemlerin sayısı, genel olarak zaman karmaşıklığı olarak ifade edilir; burada temel işlemlerin belirli bir bilgisayarda sabit bir süre aldığına ve farklı bir makinede çalıştırıldığında yalnızca sabit bir faktörle değiştiğine inanılır. Bir algoritmanın n boyutundaki bir girdide ihtiyaç duyduğu bellek miktarı, uzay karmaşıklığı olarak bilinir.
Zaman en çok düşünülen kaynaktır. "Karmaşıklık" terimi niteleyici olmadan kullanıldığında, genellikle zamanın karmaşıklığını ifade eder.
Geleneksel zaman birimleri (saniye, dakika vb.), seçilen bilgisayara ve teknolojinin ilerlemesine çok bağımlı oldukları için karmaşıklık teorisinde kullanılmaz. Örneğin, günümüzde bir bilgisayar, 1960'lardaki bir bilgisayardan önemli ölçüde daha hızlı bir algoritma yürütebilir, ancak bu, algoritmanın doğal kalitesinden ziyade bilgisayar donanımındaki teknolojik atılımlardan kaynaklanmaktadır. Karmaşıklık teorisinin amacı, algoritmaların doğal zaman ihtiyaçlarını veya bir algoritmanın herhangi bir bilgisayara dayatacağı temel zaman sınırlamalarını ölçmektir. Bu, hesaplama sırasında kaç temel işlemin gerçekleştirildiğini sayarak gerçekleştirilir. Bu prosedürlere genellikle adım denir çünkü belirli bir makinede sabit zaman aldıkları düşünülür (yani girdi miktarından etkilenmezler).
Diğer bir önemli kaynak, algoritmaları gerçekleştirmek için gereken bilgisayar belleği miktarıdır.
Sık kullanılan bir diğer kaynak ise aritmetik işlemlerin miktarıdır. Bu senaryoda, "aritmetik karmaşıklık" terimi kullanılır. Bir hesaplama sırasında meydana gelen sayıların ikili gösteriminin boyutu üzerinde bir üst kısıtlama biliniyorsa, zaman karmaşıklığı genellikle sabit bir faktör tarafından aritmetik karmaşıklığın ürünüdür.
Bir hesaplama sırasında kullanılan tam sayıların boyutu birçok yöntem için kısıtlanmamıştır ve aritmetik işlemlerin sabit bir süre gerektirdiğini varsaymak gerçekçi değildir. Sonuç olarak, bit karmaşıklığı olarak da bilinen zaman karmaşıklığı, aritmetik karmaşıklıktan önemli ölçüde daha yüksek olabilir. Örneğin, bir nn tamsayı matrisinin determinantını hesaplamanın aritmetik zorluğu, standart teknikler (Gauss eleme) için O(n^3)'tür. Hesaplama sırasında katsayıların boyutu üstel olarak genişleyebileceğinden, aynı yöntemlerin bit karmaşıklığı n'de üsteldir. Bu teknikler çok modüllü aritmetik ile birlikte kullanılırsa, bit karmaşıklığı O(n^4)'e düşürülebilir.
Bit karmaşıklığı, resmi terimlerle, bir algoritmayı çalıştırmak için gereken bitler üzerindeki işlem sayısını ifade eder. Çoğu hesaplama paradigmasında sabit bir faktöre kadar geçici karmaşıklığa eşittir. Bilgisayarların ihtiyaç duyduğu makine kelimeleri üzerindeki işlem sayısı, bit karmaşıklığı ile orantılıdır. Gerçekçi hesaplama modelleri için zaman karmaşıklığı ve bit karmaşıklığı bu nedenle aynıdır.
Sıralama ve aramada genellikle dikkate alınan kaynak, giriş karşılaştırmalarının miktarıdır. Veriler iyi düzenlenmişse, bu zaman karmaşıklığının iyi bir göstergesidir.
Tüm potansiyel girdilerde, bir algoritmadaki adım sayısını saymak imkansızdır. Bir girdinin karmaşıklığı boyutuyla birlikte arttığından, genellikle girdi boyutunun (bit cinsinden) bir fonksiyonu olarak temsil edilir ve dolayısıyla karmaşıklık n'nin bir fonksiyonudur. Ancak aynı büyüklükteki girdiler için bir algoritmanın karmaşıklığı önemli ölçüde değişebilir. Sonuç olarak, çeşitli karmaşıklık işlevleri rutin olarak kullanılmaktadır.
En kötü durum karmaşıklığı, tüm n boyutundaki girdiler için tüm karmaşıklığın toplamı iken, ortalama durum karmaşıklığı, tüm n boyutundaki girdiler için tüm karmaşıklıkların toplamıdır (belirli bir boyuttaki olası girdilerin sayısı sonlu). "Karmaşıklık" terimi daha fazla tanımlanmadan kullanıldığında, en kötü durum zaman karmaşıklığı dikkate alınır.
En kötü durum ve ortalama durum karmaşıklığını doğru hesaplamak herkesin bildiği gibi zordur. Ayrıca, bu kesin değerlerin çok az pratik uygulaması vardır çünkü makine veya hesaplama paradigmasındaki herhangi bir değişiklik karmaşıklığı biraz değiştirecektir. Ayrıca, n'nin küçük değerleri için kaynak kullanımı çok önemli değildir, bu nedenle uygulama kolaylığı genellikle küçük n için düşük karmaşıklıktan daha çekicidir.
Bu nedenlerle, en çok dikkat, karmaşıklığın yüksek n için davranışına, yani n sonsuza yaklaşırken asimptotik davranışına verilir. Sonuç olarak, karmaşıklığı belirtmek için büyük O gösterimi yaygın olarak kullanılır.
Hesaplamalı modeller
Bir zaman biriminde gerçekleştirilen temel işlemlerin belirlenmesinden oluşan bir hesaplama modelinin seçimi, karmaşıklığın belirlenmesinde çok önemlidir. Bu, hesaplama paradigması özel olarak tanımlanmadığında bazen çok bantlı Turing makinesi olarak adlandırılır.
Deterministik bir hesaplama modeli, makinenin sonraki durumlarının ve gerçekleştirilecek işlemlerin tamamen önceki durum tarafından tanımlandığı bir modeldir. Özyinelemeli fonksiyonlar, lambda hesabı ve Turing makineleri ilk deterministik modellerdi. Rastgele erişimli makineler (RAM makineleri olarak da bilinir), gerçek dünya bilgisayarlarını simüle etmek için popüler bir paradigmadır.
Hesaplama modeli tanımlanmadığında, genellikle çok bantlı bir Turing makinesi olduğu varsayılır. Çoklu bant Turing makinelerinde, çoğu algoritma için zaman karmaşıklığı RAM makinelerinde olduğu gibidir, ancak bu eşdeğerliği elde etmek için verilerin bellekte nasıl depolandığına oldukça dikkat edilmesi gerekebilir.
Deterministik olmayan Turing makineleri gibi deterministik olmayan bir hesaplama modelinde hesaplamanın bazı adımlarında çeşitli seçimler yapılabilir. Karmaşıklık teorisinde, tüm uygun seçenekler aynı anda dikkate alınır ve deterministik olmayan zaman karmaşıklığı, her zaman en iyi seçimler yapıldığında gereken süredir. Başka bir deyişle, hesaplama gerektiği kadar (özdeş) işlemci üzerinde eşzamanlı olarak yapılır ve deterministik olmayan hesaplama süresi, ilk işlemci tarafından hesaplamayı tamamlamak için geçen süredir. Bu paralellik, örneğin Shor'un küçük tamsayıları çarpanlara ayırması gibi özel kuantum algoritmaları çalıştırırken üst üste binmiş dolanık durumlar kullanılarak kuantum hesaplamada kullanılabilir.
Böyle bir hesaplama modeli şu anda uygulanabilir olmasa bile, özellikle “polinom zamanı” ve “deterministik olmayan polinom zamanı” kullanılarak üretilen karmaşıklık sınıflarının en az üstte olup olmadığını soran P = NP problemi ile ilgili olarak teorik öneme sahiptir. sınırlar aynıdır. Deterministik bir bilgisayarda, bir NP algoritmasını simüle etmek "üstel zaman" gerektirir. Bir görev, deterministik olmayan bir sistemde polinom zamanında çözülebiliyorsa, NP zorluk sınıfına aittir. Bir sorun NP'deyse ve diğer herhangi bir NP sorunundan daha kolay değilse, bunun NP-tamamlanmış olduğu söylenir. Sırt Çantası problemi, gezgin satıcı problemi ve Boolean tatmin edilebilirlik problemi, hepsi NP-tam kombinatoryal problemlerdir. En iyi bilinen algoritma, tüm bu problemler için üstel karmaşıklığa sahiptir. Bu sorunlardan herhangi biri deterministik bir makinede polinom zamanında çözülebilirse, tüm NP problemleri polinom zamanında da çözülebilir ve P = NP kurulur. 2017 itibariyle, P NP'nin, NP problemlerinin en kötü durumlarının temelde çözülmesinin zor olduğunu, yani, ilginç girdi uzunlukları verilen herhangi bir uygun zaman aralığından (on yıllar) çok daha uzun sürdüğünü ima ettiği yaygın olarak varsayılmaktadır.
Paralel ve dağıtılmış bilgi işlem
Paralel ve dağıtılmış bilgi işlem, işlemin tümü aynı anda çalışan birden çok işlemciye bölünmesini içerir. Çeşitli modeller arasındaki temel ayrım, işlemciler arasında veri gönderme yöntemidir. İşlemciler arasındaki veri iletimi, paralel hesaplamada tipik olarak çok hızlıyken, dağıtılmış hesaplamada işlemciler arasındaki veri aktarımı bir ağ üzerinden yapılır ve bu nedenle önemli ölçüde daha yavaştır.
N işlemci üzerinde bir hesaplama, tek bir işlemcide geçen sürenin en azından N kadar bölümünü alır. Gerçekte, bazı alt görevler paralelleştirilemediğinden ve bazı işlemcilerin başka bir işlemciden bir sonuç beklemesi gerekebileceğinden, teorik olarak bu ideal sınıra asla ulaşılmayacaktır.
Bu nedenle temel karmaşıklık sorunu, işlemci sayısı ile hesaplama süresinin çarpımı, aynı hesaplamayı tek bir işlemci üzerinde gerçekleştirmek için gereken süreye mümkün olduğunca yakın olacak şekilde algoritmalar geliştirmektir.
Kuantum hesaplama
Kuantum bilgisayar, kuantum mekaniğine dayalı hesaplama modeline sahip bir bilgisayardır. Church-Turing tezi, kuantum bilgisayarlar için geçerlidir ve bir kuantum bilgisayarın çözebileceği herhangi bir sorunun bir Turing makinesi tarafından da çözülebileceğini ima eder. Bununla birlikte, bazı görevler, önemli ölçüde daha düşük zamansal karmaşıklığa sahip klasik bir bilgisayar yerine bir kuantum bilgisayar kullanılarak teorik olarak çözülebilir. Hiç kimse pratik bir kuantum bilgisayarının nasıl geliştirileceğini bilmediğinden, şimdilik, bu kesinlikle teoriktir.
Kuantum karmaşıklığı teorisi, kuantum bilgisayarlar tarafından çözülebilecek farklı sorun türlerini araştırmak için oluşturuldu. Kuantum bilgisayar saldırılarına dirençli kriptografik protokoller oluşturma süreci olan kuantum sonrası kriptografide kullanılır.
Problemin karmaşıklığı (alt sınırlar)
Keşfedilmemiş teknikler de dahil olmak üzere sorunu çözebilecek algoritmaların karmaşıklığının en azı, sorunun karmaşıklığıdır. Sonuç olarak, bir problemin karmaşıklığı, onu çözen herhangi bir algoritmanın karmaşıklığına eşittir.
Sonuç olarak, büyük O gösteriminde verilen herhangi bir karmaşıklık, hem algoritmanın hem de beraberindeki sorunun karmaşıklığını temsil eder.
Öte yandan, sorun karmaşıklığına ilişkin önemsiz olmayan alt sınırlar elde etmek genellikle zordur ve bunu yapmak için çok az strateji vardır.
Çoğu sorunu çözmek için, verilerin büyüklüğüyle orantılı olarak zaman alan tüm girdi verilerinin okunması gerekir. Sonuç olarak, bu tür problemler en azından doğrusal karmaşıklığa veya büyük omega gösteriminde Ω(n) karmaşıklığına sahiptir.
Bilgisayar cebiri ve hesaplamalı cebirsel geometri gibi bazı problemlerin çok büyük çözümleri vardır. Çıktının yazılması gerektiğinden, karmaşıklık çıktının maksimum boyutuyla sınırlıdır.
Bir sıralama algoritması için gereken karşılaştırma sayısı, Ω(nlogn) doğrusal olmayan bir alt sınırına sahiptir. Sonuç olarak, en iyi sıralama algoritmaları, karmaşıklıkları O(nlogn) olduğundan en verimli olanlardır. n olduğu gerçeği! n şeyi organize etmenin yolları bu alt sınıra götürür. Çünkü her karşılaştırma bu n! siparişler iki parçaya bölünürse, tüm siparişleri ayırt etmek için gereken N karşılaştırma sayısı 2N > n! olmalıdır, bu da Stirling'in formülüne göre O(nlogn) anlamına gelir.
Bir problemi başka bir probleme indirgemek, azaltılmış karmaşıklık kısıtlamaları elde etmek için yaygın bir stratejidir.
algoritma geliştirme
Bir algoritmanın karmaşıklığını değerlendirmek, beklenebilecek performans hakkında faydalı bilgiler sağladığı için tasarım sürecinin önemli bir unsurudur.
Modern bilgisayar gücünün üstel büyümesini öngören Moore yasasının bir sonucu olarak, algoritmaların karmaşıklığını değerlendirmenin daha az alakalı hale geleceği sık sık yapılan bir yanlış anlamadır. Bu yanlıştır çünkü artan güç, büyük miktarda verinin (büyük veri) işlenmesine izin verir. Örneğin, bir kitabın bibliyografyası gibi birkaç yüz girdiden oluşan bir listeyi alfabetik olarak sıralarken herhangi bir algoritma bir saniyeden daha kısa sürede iyi çalışmalıdır. Öte yandan, bir milyon giriş için (örneğin, büyük bir şehrin telefon numaraları), O(n2) karşılaştırması gerektiren temel algoritmalar, 10 hızında üç saat sürecek bir trilyon karşılaştırma yapmak zorunda kalacaktı. saniyede milyon karşılaştırma. Öte yandan, hızlı sıralama ve birleştirme sıralama, yalnızca nlogn karşılaştırmaları gerektirir (birincisi için ortalama durum karmaşıklığı, ikincisi için en kötü durum karmaşıklığı olarak). Bu, n = 30,000,000 için yaklaşık 1,000,000 karşılaştırma üretir; bu, saniyede 3 milyon karşılaştırmada yalnızca 10 saniye sürer.
Sonuç olarak, karmaşıklığın değerlendirilmesi, uygulamadan önce birçok verimsiz algoritmanın ortadan kaldırılmasına izin verebilir. Bu, olası tüm değişkenleri test etmek zorunda kalmadan karmaşık algoritmalara ince ayar yapmak için de kullanılabilir. Karmaşıklık çalışması, karmaşık bir algoritmanın en maliyetli adımlarını belirleyerek bir uygulamanın verimliliğini artırma çabasına odaklanmayı sağlar.
Kendinizi sertifika müfredatı hakkında ayrıntılı olarak tanımak için aşağıdaki tabloyu genişletebilir ve analiz edebilirsiniz.
EITC/IS/CCTF Hesaplamalı Karmaşıklık Teorisi Temelleri Sertifikasyon Müfredatı, açık erişimli didaktik materyalleri bir video biçiminde referans verir. Öğrenme süreci, ilgili müfredat bölümlerini kapsayan adım adım bir yapıya (programlar -> dersler -> konular) bölünmüştür. Alan uzmanları ile sınırsız danışmanlık da sağlanmaktadır.
Sertifikasyon prosedürü kontrolü ile ilgili ayrıntılar için Nasıl Çalışır?.
Birincil destekleyici müfredat okuma materyalleri
S. Arora, B. Barak, Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım
https://theory.cs.princeton.edu/complexity/book.pdf
İkincil destekleyici müfredat okuma materyalleri
O. Goldreich, Karmaşıklık Teorisine Giriş:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Ayrık matematik üzerine destekleyici müfredat okuma materyalleri
J. Aspnes, Ayrık Matematik Üzerine Notlar:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Grafik teorisi üzerine destekleyici müfredat okuma materyalleri
R. Diestel, Grafik Teorisi:
https://diestel-graph-theory.com/
EITC/IS/CCTF Hesaplamalı Karmaşıklık Teorisi Temelleri programına yönelik çevrimdışı kendi kendine öğrenme hazırlık malzemelerinin tamamını PDF dosyası olarak indirin
EITC/IS/CCTF hazırlık materyalleri – standart versiyon
EITC/IS/CCTF hazırlık materyalleri – inceleme sorularını içeren genişletilmiş versiyon