Deterministik algoritma - Deterministic algorithm

İçinde bilgisayar Bilimi, bir deterministik algoritma bir algoritma belirli bir girdi verildiğinde, temeldeki makine her zaman aynı durum dizisinden geçerken daima aynı çıktıyı üretecektir. Deterministik algoritmalar, gerçek makinelerde verimli bir şekilde çalıştırılabildikleri için en pratik algoritmaların yanı sıra en çok çalışılan ve bilinen algoritmadır.

Biçimsel olarak, deterministik bir algoritma bir matematiksel fonksiyon; bir işlev, içindeki herhangi bir girdi için benzersiz bir değere sahiptir. alan adı ve algoritma, bu belirli değeri çıktı olarak üreten bir süreçtir.

Resmi tanımlama

Deterministik algoritmalar, aşağıdaki terimlerle tanımlanabilir: durum makinesi: a durum Bir makinenin belirli bir zamanda ne yaptığını açıklar. Durum makineleri, bir durumdan diğerine ayrı bir şekilde geçer. Girişe girdikten hemen sonra, makine kendi başlangıç ​​hali veya başlangıç ​​durumu. Makine deterministik ise, bu, bu noktadan itibaren mevcut durumunun bir sonraki durumunun ne olacağını belirlediği anlamına gelir; bir dizi durumdaki gidişatı önceden belirlenmiştir. Bir makinenin deterministik olabileceğini ve yine de asla durmayacağını veya bitmediğini ve bu nedenle bir sonuç veremeyeceğini unutmayın.

Belirli örnekler soyut makineler deterministik olanlar şunları içerir: deterministik Turing makinesi ve deterministik sonlu otomat.

Algoritmaları deterministik olmayan yapan nedir?

Çeşitli faktörler, bir algoritmanın deterministik veya deterministik olmayan bir şekilde davranmasına neden olabilir:

• Giriş dışında kullanıcı girişi, global değişken, donanım zamanlayıcı değeri, a gibi harici durum kullanıyorsa rastgele değer veya depolanan disk verileri.
• Zamanlamaya duyarlı bir şekilde çalışıyorsa, örneğin aynı veriye aynı anda birden çok işlemcinin yazması durumunda. Bu durumda, her işlemcinin verilerini yazdığı kesin sıra sonucu etkileyecektir.
• Bir donanım hatası durumunun beklenmedik bir şekilde değişmesine neden oluyorsa.

Gerçek programlar nadiren tamamen deterministik olsa da, insanlar ve diğer programlar için olan programlar hakkında akıl yürütmek daha kolaydır. Bu nedenle çoğu Programlama dilleri ve özellikle fonksiyonel programlama diller, kontrollü koşullar dışında yukarıdaki olayların meydana gelmesini önlemek için çaba gösterir.

Yaygınlığı çok çekirdekli işlemciler paralel programlamada determinizme olan ilginin artmasına neden olmuştur ve determinizm olmayışının zorlukları iyi belgelenmiştir.^[1][2] Zorlukların üstesinden gelmeye yardımcı olacak bir dizi araç önerilmiştir^[3][4][5][6] başa çıkmak kilitlenmeler ve yarış koşulları.

Determinizmin dezavantajları

Bazı durumlarda, bir programın belirleyici olmayan davranış sergilemesi avantajlıdır. Bir oyunda kullanılan bir kart karıştırma programının davranışı blackjack örneğin, programın kaynak kodu görünse bile, oyuncular tarafından tahmin edilebilir olmamalıdır. A kullanımı sözde rasgele sayı üreteci oyuncuların karıştırma işleminin sonucunu tahmin edememesini sağlamak için genellikle yeterli değildir. Zeki bir kumarbaz, jeneratörün seçeceği sayıları tam olarak tahmin edebilir ve böylece destenin tüm içeriğini önceden belirleyerek hile yapmasına izin verebilir; örneğin, Trusted Software Technologies'deki Yazılım Güvenlik Grubu bunu ASF Software, Inc tarafından dağıtılan bir Texas Hold'em Poker uygulaması için yapabildi ve böylece ellerin sonucunu tutarlı bir şekilde önceden tahmin etmelerine olanak sağladı.^[7] Bu problemler, kısmen, bir kriptografik olarak güvenli sözde rastgele sayı üreteci ama yine de öngörülemeyen bir rastgele tohum Jeneratörü başlatmak için kullanılacak. Bu amaçla, bir belirleyici olmayan kaynak gereklidir, örneğin bir donanım rasgele sayı üreteci.

Olumsuz bir yanıt olduğuna dikkat edin. P = NP sorunu Belirsiz çıktıya sahip programların teorik olarak deterministik çıktıya sahip programlardan daha güçlü olduğu anlamına gelmez. NP (karmaşıklık) Belirsizliğe herhangi bir atıfta bulunmadan tanımlanabilir. doğrulayıcı tabanlı tanım.

Dillerde determinizm kategorileri

Merkür

Bu mantıksal işlevsel programlama dili, referans modları için farklı determinizm kategorileri oluşturur.^[8][9]

Haskell

Haskell birkaç mekanizma sağlar:

determinizm olmama veya Başarısızlık kavramı

• Olabilir ve Ya türleri sonuçtaki başarı kavramını içerir.
• başarısız Monad sınıfının yöntemi, sinyal vermek için kullanılabilir başarısız istisna olarak.
• Belki monad ve MaybeT monad transformatörü başarısız hesaplamaları sağlar (hesaplama sırasını durdurun ve Nothing döndür)^[10]

determinizm / çoklu çözümlerle algılanmayan

Sonuç türünü bir MonadPlus'a sararak çoklu sonuç hesaplamasının tüm olası sonuçlarını alabilirsiniz. monad. (yöntemi mzero bir sonucun başarısız olmasına neden olur ve mplus başarılı sonuçları toplar).^[11]

Makine öğrenimi ailesi ve türetilmiş diller

Görüldüğü gibi Standart ML, OCaml ve Scala

• seçenek tip başarı kavramını içerir.

Java

• boş referans değeri, başarısız (alan dışı) bir sonucu gösterebilir.

Referanslar