Algoritma - Algorithm


Vikipedi, özgür ansiklopedi

Akış Şeması bir algoritma ( Öklid algoritması iki sayı en büyük ortak böleni (gcd) hesaplanması için) a ve b testi B ≥ Bir "evet" verir EĞER: iki halkası ardışık çıkarılması ile daha algoritma hasılatı bir adlandırılmış yerlerde ve B. (ya da doğru) (daha doğru bir sayı b konumu B'de daha büyük ya da eşit olan sayısı, a konumu A) daha sonra, algoritma B ← B belirtir - bir (sayı anlamına b - bir eski yerine b). Benzer şekilde, bir> B, daha sonra bir ← bir IF - (içeriği) Oda A'da gcd elde 0 olduğunda, B. işlemi sona (Scott 2009 türetilen Algoritma: 13 1977'de Tausworthe sembolleri ve çizim tarzı) .

Gelen matematik ve bilgisayar biliminin , bir algoritma ( / æ l ɡ ə r ɪ ïğîãğ əm /  ( dinleme )Bu ses hakkında ) problemlerin bir sınıfını çözmek için nasıl kesin bir özelliğidir. Algoritmalar gerçekleştirebilir hesaplama , veri işleme ve otomatikleştirilmiş muhakeme görevleri.

Bir olarak etkili bir yöntem , bir algoritma alanı ve sonlu bir zaman miktarı içinde ve hesaplanması için, iyi tanımlanmış bir resmi dili ile ifade edilebilir fonksiyonu . Bir ilk durumu ve ilk giriş (belki başlanarak boş ), talimatlar bir tarif hesaplama zaman çalıştırılır sonunda "çıkış" üretilmesi ve son bir son durum son bulan, iyi tanımlanmış, ardışık durumları sınırlı bir sayıda ilerler. Sonraki bir durumdan geçiş zorunlu değildir belirleyici ; olarak bilinen bazı algoritmalar, randomize algoritmaları , rasgele girişi dahil.

Algoritmanın kavramı yüzyıllardır var olmuştur. Yunan matematikçiler içinde algoritmaları kullanılan örneğin, Eratosthenes elek asal sayılar ve bulmak için Öklid algoritması bulmak için büyük ortak böleni iki sayının.

Kelimesinin algoritması kendisi 9. yüzyılda mathematician türeyen Hârizmî , Latinized Algoritmi . Algoritmasının Modern kavramı haline gelecek kısmi resmileştirilmesi çözmek için girişimlerde ile başladı Entscheidungsproblem yarattığı (Karar problemi) David Hilbert "define teşebbüsleri gibi çerçeveli edildi 1928. Daha sonra biçimlendirmelerden içinde etkili hesaplanabilirlik " veya "etkili bir yöntem". Bu biçimlendirmelerden dahil Gödel - Herbrand - Kleene özyinelemeli fonksiyonlar 1930, 1934 ve 1935, ve Alonzo Church 'ın lambda hesap 1936, Emil Mesaj ' in Formülasyon 1 1936 ve Alan Turing'in 'ın Turing makineleri 1936-37 ve 1939.

etimoloji

Kelimesi algoritması 'adını Latinizing kökleri Hârizmî için bir birinci adımda algorismus . Harizmi ( Farsça : خوارزمی ., C 780-850) bir oldu Pers matematikçi, astronom , coğrafyacı içinde ve alim Bilgelik Evi de Bağdat ismi 'arasında yerli demektir Harezm ', parçası olan bir bölge Antik İran ve şimdi Özbekistan .

Yaklaşık 825, el-Khwarizmi bir yazdı Arap dili üzerine bir risale Hindu-Arap rakam sistemi çevrildi, Latince başlığı altında 12. yüzyılda Algoritmi'nin de Numero Indorum . Bu unvan "Algoritmi'nin" çevirmenin oldu "Kızılderililerin numaraları algoritma" anlamına Latince sözcükler Harizmi adının. Harizmi öncelikle Kitaplarından, diğeri vasıtasıyla, Geç Ortaçağ'da Avrupa'da en çok okunan matematikçi oldu Cebir . Geç Ortaçağ Latin, içinde algorismus , İngilizce ' Arap rakamları ', onun adının yolsuzluk, basitçe "ondalık sayı sistemi" anlamına geliyordu. 15. yüzyılda, Yunanca kelime ἀριθμός 'numara' (etkisiyle krş 'aritmetik'), Latince kelime için değiştirildi Algorithmus ve karşılık gelen İngilizce terim 'algoritma' ilk 17. yüzyılda ispatlanmıştır; Modern anlamda 19. yüzyılda tanıtıldı.

İngilizce, ilk hakkında 1230 yılında kullanıldı ve o sırada Chaucer 1391 yılında İngilizce Fransızca terim kabul ama "algoritma" modern İngilizce olduğu anlam kazandı 19. yüzyıla kadar değildi.

Kelimenin diğer bir erken kullanımı başlıklı bir kılavuzda, 1240 dan Carmen de Algorismo tarafından bestelenen Alexandre de Villedieu . Böylece başlar:

HAEC algorismus ars Praesens dicitur, nereye içinde / Talibus Indorum fruimur bis adresi için beş figuris.

hangi anlamına:

Arap rakamları biz bu Hint rakamları, iki numaralı beş kat kullanmak şu anda hangi sanattır.

şiir birkaç yüz satır uzunluğundadır ve yeni Hint zar tarzında ya Talibus Indorum veya Hindu rakamları ile hesaplanması sanatını özetlemektedir.

Gayri tanım

Gayri resmi tanımı "tam operasyonların bir diziyi tanımlayan kurallar kümesi" olabilir. hangi sayısal hesaplamalar olmayan programlar dahil olmak üzere tüm bilgisayar programları, içerecektir. sonunda durursa Genellikle bir programın sadece bir algoritmadır.

Diğer bir algoritma prototip örneği Öklid algoritması iki tamsayı maksimum ortak böleni belirlemek; Bir örnek, (orada diğerleri) tarif edilir akış şeması üzerinde ve daha sonraki bir bölümde bir örnek olarak.

Boolos Jeffrey & 1974, 1999 fırsat şunları alıntıda kelimenin gayrı anlamı:

Hiçbir insan yeterince hızlı yazma veya yeterince uzun ya kadar küçük olabilir † bir tüm üyelerini listelemek için († "sınırı olmadan daha küçük ve daha küçük ... Eğer elektronların üzerine, atomlar üzerinde, moleküller üzerinde yazmaya çalışırdım") numaralanabilir sonsuz bazı gösterimde, isimlerini, birbiri ardına yazılarak ayarlanır. Fakat, insanlar belli numaralanabilir sonsuz kümeler halinde eşit olarak yararlı bir şey, bunu yapabilirsiniz: Onlar verebilir belirlenmesi için açık talimat n kümesinin üyesi inci keyfi sonlu için, n . Bu talimatlar hangi bir formda, oldukça açık bir şekilde verilecek olan bir işlem makinesi ile takip edilebilir , ya da bir ile semboller üzerine çok basit işlemleri gerçekleştirme kapasitesine sahip olan bir insan.

Bir "numaralanabilir sonsuz kümesi" kimin elemanları tamsayılar ile bire-bir yazışma içine konabilir biridir. Böylece, Boolos Jeffrey bir algoritma bir çıktısı tamsayılar "yaratır" bir işlem için talimatlar ima söylüyor keyfi teoride, keyfi büyük olabilir, "giriş" tamsayı veya tamsayılar. Dolayısıyla, bir algoritma gibi bir cebirsel denklem olabilir y = m + n , iki rasgele "girdi değişkenleri" - m ve n bir çıkış üretmek y . Ama kavramını tanımlamak için çeşitli yazarların girişimleri kelime (toplama gibi) mertebesinde bir şey bundan daha fazla ima göstermektedir:

"Bilgisayar" "hamle" belirten bir hızlı, verimli, "iyi" süreci için ( "bilgisayar" anlayacağı dilde) Eksiksiz talimatları bulmak için (gerekli donatılmış makine veya insan, içten bilgileri ve yetenekleri içeriyordu) kod çözme, ve daha sonra işlem rasgele giriş tamsayı / semboller m ve n , semboller + ve = ... ve "etkili bir şekilde" "uygun" bir süre içinde üretilmesi, çıkış tamsayı y , belirli bir yerde ve belirli bir biçimde.

Kavramı, algoritma ayrıca kavramını tanımlamak için kullanılır saptanabilirlik . Bu kavramı açıklayan merkezi olan sistemler biçimsel küçük bir set başlayarak meydana gelen aksiyomları ve kurallar. Gelen mantığı o görünüşte bizim örf fiziksel boyuta ilişkili değildir gibi bir algoritma tamamlamak için gerekli zamanı, ölçülemez. Devam eden çalışmaları karakterize böyle belirsizlikler, itibaren, bir tanımının kullanılamazlık kaynaklanıyor algoritması (bazı anlamda) hem beton uyan ve terimin soyut kullanımı.

resmileştirme

Algoritmalar yol bilgisayarları işlem verilerine esastır. Birçok bilgisayar programları bu tür çalışanların maaşını veya baskı öğrencilerin karneleri hesaplanırken olarak (belirli bir sırayla) bir bilgisayar gerçekleştirmelisiniz özel talimatları belirli bir görevi yürütmek için detay algoritmalarını içerir. Bu durumda, bir algoritma bir simüle edilebilir işlemlerin herhangi bir sekans olarak kabul edilebilir Turing komple sistem. Bu tezi iddia Yazarlar Minsky (1967), Savage (1987) ve Gurevich (2000) şunlardır:

Minsky: "Ama aynı zamanda Turing ile sürdürecek herhangi bir prosedür olduğunu... 'Doğal olarak' etkili çağrılacak, aslında, bir (basit) makine tarafından gerçekleştirilebilir bu, argümanlar aşırı görünse de... . onun lehine "çürütmek zordur.

Gurevich: ": Savage [1987], bir algoritma bir Turing makinesi tarafından tanımlanan bir hesaplama süreçtir göre ... her algoritmanın Turing makinesi tarafından simüle edilebilir ... tezi lehinde Turing'in gayri argümanı daha güçlü bir tez haklı" .

Bir algoritma bilgi işlem ile ilişkilidir Tipik olarak, veri bir giriş kaynağı, bir çıkış cihazına yazılı ve daha sonraki işlemler için depolanır okunabilir. Saklanan veri algoritması gerçekleştiren kuruluşun iç devletin parçası olarak kabul edilmektedir. Pratikte, durum, bir ya da daha fazla depolanan veri yapıları .

Bazı tür hesaplama işlemi için algoritma titizlikle tanımlanmış olmalıdır: o ortaya çıkabilecek olası tüm durumlar için geçerlidir şekilde belirtilmiş. Yani, herhangi bir koşullu adım sistematik ile durum-durum ele alınması gereken bir; Her bir durum için kriterler açık (ve hesaplanabilir) olması gerekir.

Bir algoritma kesin adımların kesin liste olduğundan, hesaplama sırası her zaman algoritmanın işleyişi için çok önemlidir. Talimatlar genelde açıkça sıralanabilir varsayılır ve "yukarıdan" başlayan ve, daha resmen açıklanan bir fikir "dibine kadar" gidiş olarak tarif edilmektedir kontrol akışından .

Şimdiye kadar, bir algoritma formelleşmesinin bu tartışma tesislerinde üstlendi şart programlama . Bu, en yaygın anlayış olduğunu ve ayrık, "mekanik" yollarla bir görevi tanımlamak için çalışır. Resmileştirdi algoritmaları bu anlayışına özgü Atama işlemi bir değişkenin değerini ayarlayarak,. Bu "nin sezgi türetilmiştir bellekten bir Not Defteri olarak". Böyle bir atama aşağıda bir örnek yoktur.

Bir algoritma oluşturan şeyin bazı alternatif kavramların için bkz fonksiyonel programlama ve mantık programlama .

algoritmaları ifade

Algoritmalar içeren gösterimde, birçok türde ifade edilebilir doğal dilleri , pseudocode , akış şemaları , drakon-grafikler , programlama dilleri ya da kontrol tabloları (işlenen sözlü ). Algoritmaların Doğal dil ifadeleri ayrıntılı ve belirsiz olma eğilimindedir ve nadiren karmaşık veya teknik algoritmalar kullanılır. Pseudocode akış şemaları, drakon-çizelgeleri ve kontrol tabloları doğal dil tablolara ortak belirsizlikler birçok önlemek algoritmalarını ifade etmek yapılandırılmış yollarıdır. Programlama dilleri öncelikle bir bilgisayar tarafından yürütüldüğünde, ancak genellikle bir tanımlamak için veya bu şekilde doküman algoritmaları olarak kullanıldığı bir biçimde algoritmaları ifade etmek için tasarlanmıştır.

Orada olası temsilleri çok çeşitli ve biri belirli bir ifade edebilir Turing makinesi makinesi tabloları (en fazla görmek bir dizi olarak bir program sonlu hal makinesi , durum geçiş tablo ve kontrol tablo akış şemaları ve benzeri gibi), drakon çizelgeleri (en fazla görmek durum diyagramı ), ya da basit bir biçimi olarak makine kodu ya da montaj kodu "dörtgen kümeleri" olarak adlandırılan (daha bakınız Turing makinesi ).

algoritmaların Beyanlar Turing makinası açıklamasının üç kabul seviyelere sınıflandırılabilir:

1 Yüksek seviyeli açıklaması
"... Bu seviyede, biz makine onun kaset veya kafasını nasıl yönettiğini söz gerekmez. Uygulama detaylarını da önemsemeyerek, bir algoritma tarif etmek nesir."
2 Uygulama tanımı
"... nesir Turing makinası başını kullanma şeklini ve onun kasete veri depolayan biçimini tanımlamak için kullanılır. Bu seviyede, biz devletler veya geçiş fonksiyonunun ayrıntıları vermeyin."
3 formal açıklaması
En ayrıntılı, "düşük seviye", Turing makinenin "devlet tablosu" verir.

Basit bir algoritma bir örnek için "m + n Ekle" üç düzeyde tarif edilmiştir, bakınız Algoritma # Örnekler .

dizayn

Algoritma tasarım problem çözme ve mühendislik algoritmaları için bir usul ya da matematiksel işlemi belirtir. Algoritmalarının tasarımı birçok çözüm teorileri bir parçası olan operasyon araştırması gibi dinamik programlama ve böl ve Fetihten . Algoritma tasarımları tasarlanması ve uygulanması için teknikler ayrıca şablon yöntemi desen ve dekoratör deseni olarak algoritma tasarımı desenleri, denir.

Algoritma tasarımının en önemli yönlerinden biri, aynı zamanda olarak da bilinen etkin bir çalışma zamanı, sahip olan bir algoritma yaratıyor Büyük O .

algoritmaların geliştirilmesinde tipik adımlar:

  1. Problem tanımı
  2. Bir model geliştirilmesi
  3. algoritmanın Şartname
  4. bir algoritma tasarlama
  5. algoritmanın doğruluğunu kontrol etme
  6. algoritması analizi
  7. algoritmanın uygulanması
  8. Programı test
  9. Belgeler hazırlığı

uygulama

Mantıksal NAND algoritması elektronik uygulanan 7400 çip

Çoğu algoritmalar olarak uygulanmak üzere tasarlanmıştır bilgisayar programları . Bununla birlikte, algoritmalar aynı zamanda, bir ve ayrıca diğer vasıtalarla, tarafından uygulanan biyolojik sinir ağı (örneğin, insan beyninin uygulanması aritmetik veya bir böcek yiyecek arayan) bir in, elektrik devresi veya mekanik bir cihaz olarak.

Bilgisayar algoritmaları

Akış Şeması kanonik örnekleri Böhm-Jacopini yapıları : SIRASI (sayfa inen dikdörtgenler), WHILE-DO ve IF-THEN-ELSE. Üç yapı ilkel koşullu GOTO yapılmıştır ( IF testi = doğru ve GOTO adım xxx ) (elmas), koşulsuz GOTO (dikdörtgen), çeşitli atama operatörleri (dikdörtgen) ve durdur (dikdörtgen). Atama-blokların içindeki bu yapıların Yuvalama karmaşık şemalar (: 100.114 cf Tausworthe 1977) ile sonuçlanır.

Olarak bilgisayar sistemleri , bir algoritma, temel olarak bir örneğidir mantık üretmeye yönelik "hedef" bilgisayar (lar) için etkili olduğu, yazılım geliştiricilerinin yazılımda yazılan çıkışı verilen (belki de null) girişi . Hatta eski donanımda çalışan bir uygun algoritma, non-optimal (daha yüksek daha hızlı sonuç üretecektir zaman karmaşıklığı daha etkili donanımda çalışan, aynı amaç için) algoritması; algoritmalar, bilgisayar donanımı gibi, dikkate alınan teknoloji neden olmasıdır.

"Zarif" (kompakt) programları, "iyi" (hızlı) programları : "sadelik ve şıklık" kavramı gayri görünen Knuth ve tam olarak Chaitin :

Knuth:.." .We istiyorum iyi ...... Bilgisayarlara algoritması, basitliği ve zerafet uyum bazı gevşek tanımlanan estetik anlamda algoritmaları Bir kriter algoritmasını gerçekleştirmek için .. Diğer kriterleri alınan sürenin uzunluğudur vardır , vb"
Chaitin: ".. Bir program hangi bunu mümkün olan en küçük program yaptığı çıktıyı üretmek için olduğu anlamına 'zarif' olduğunu"

"Sana bir programın zarif olduğunu ispat edemez göstereceğiz: Chaitin ile yaptığı tanımını önsözle başlar ' bir kanıtı çözecek -bunlar" Halting sorunu (age).

Bir algoritma ile hesaplanabilir fonksiyon karşı Algoritma : belirli bir fonksiyon için, birden fazla algoritma mevcut olabilir. Bu bile programcı uygun durumda komut setini genişleyen olmadan doğrudur. Rogers "Öyle... Önemli kavramına ayırt etmek gözlemlemiştir algoritmasına , yani prosedürü ve kavramı algoritması tarafından hesaplanabilir fonksiyon . Prosedürü ile elde, yani haritalama aynı işlevi birkaç farklı algoritmalar olabilir".

Ne yazık ki, -bir zarif programı bir daha zarif daha hesaplamasını tamamlamak için daha fazla adım atabileceği iyilik (hız) ve zerafet (kompakt) arasında bir tercih söz olabilir. Öklid algoritmasını kullanan bir örnek aşağıda verilmiştir.

Bilgisayar (ve computors), hesaplama modelleri : bir bilgisayar (ya da insan "bilgisayar ortamında") makinenin sınırlı bir türü, kör talimatları takip eden "ayrı belirleyici mekanik cihaz" dir. (İ) ayrı ayrı, ayırt: Melzak en ve Lambek ilkel modelleri dört elemanlara bu durumu düşük yerler , (ii) ayrı ayrı, ayırt edilemez sayaçlar (iii) bir madde ve talimatların, (iv) bir listesidir etkili kabiliyeti göre ajan.

Minsky "Çok basit Üs onun içinde Lambek yönettiği "Abaküs" modelinin daha cana varyasyonu açıklar Hesaplanabilirlik ". Minsky makine talimatları, bir koşullu Eğer-ise GOTO veya koşulsuz GOTO ya sürece dizisinin üzerinden program akışının değiştirir (bir sayısı şekline bağlı olarak, ya da altı) sırayla beş ilerler. HALT yanı sıra, Minsky makinesi, üç içerir atama (örneğin, L ← L HALEFİ (örneğin, L ← L + 1), ve azaltma: 1 - ZERO (L ← 0, 0 ile ikame konumu, örneğin içeriği:) (değiştirme, ikame) işlemler ). Nadiren böyle sınırlı bir komut seti ile bir programcı yazma "kod" olmalıdır. Ama Minsky gösterir onun makinedir ki (Melzak ve Lambek yapmak gibi) tam Turing sadece dört genel ile tiplerinin talimatların: koşullu GOTO, koşulsuz GOTO, atama / değiştirme / ikamesi ve HALT.

Bir algoritma simülasyonu: Bilgisayar (bilgisayar ortamında) dili : Knuth o okuyucuyu önerir ".. Bir algoritma öğrenmenin en iyi yolu onu denemek için hemen kalem ve kağıt alıp bir örnek üzerinde çalışalım". Ama asıl şey bir simülasyon ya da yürütme ne olacak? Programcı simülatörü / bilgisayar / bilgisayar ortamında bir dile algoritması çevirmek gerekir etkin bir yürütün. Taş bu bir örnek verir: Bir kuadratik denklemin kökleri hesaplanırken bilgisayar ortamında bir karekökünü almak için bilmeniz gerekir. Onlar yoksa, o zaman algoritma, etkili olabilmek için, bir karekök ayıklanması için bir dizi kural sağlamalıdır.

Bu programcı hedef hesaplama ajan (bilgisayar / bilgisayar ortamında) göre etkili bir "dil" bilmek gerektiği anlamına gelir.

Ama ne modeli simülasyonu için kullanılmalıdır? Van Emde Boas "Biz temel bile gözlemler karmaşıklık teorisi beton makineleri yerine soyut üzerinde, bir model seçimi keyfilik kalır. Bu fikri bu noktada simülasyonu girer". Hız ölçülüyorsa, talimat meseleleri ayarlayın. Programcı bir "olsaydı Örneğin, kalan hesaplamak için Öklid algoritması alt program çok daha hızlı çalıştıracaktır modülü (: sadece Minsky "eksiltme" ya da kötü) mevcuttur yerine sadece çıkarma" talimatı.

Yapısal programlama, kanonik yapılar : Başına Church-Turing tezi , herhangi algoritma olduğu bilinen bir model tarafından hesaplanabilir tam Turing ve Minsky gösteriler başına, Turing tamlığı sadece dört talimat türlerinin-şartlı GOTO, koşulsuz GOTO, atama, DURDURMASI gerektirir. Kemeny ve Kurtz gözlemlemek, bu süre koşulsuz GOTOs ve "disiplinsiz" kullanım koşullu SONRA İSE-GOTOs "neden olabilir spagetti kod ", bir programcı sadece bu talimatları kullanarak yapılandırılmış programlar yazabilirsiniz; Öte yandan "yapısal bir dilde kötü yapılandırılmış programlar yazmak için, çok zor da mümkündür ve değil". Tausworthe üç arttırır Böhm-Jacopini kanonik yapılar : SIRASI, IF-THEN-ELSE ile, ve WHILE-DO iki tane daha: DO-WHILE ve VAKA. Yapısal bir programın bir diğer yararı da, kendisi verir olmasıdır doğruluğu delillerinden kullanılarak matematik indüksiyonu .

Kanonik akış şeması sembolleri grafiksel yardımcısı olarak adlandırılan akış şeması , bir algoritma (ve bir bir bilgisayar programı) tarif ve doküman için bir yol sunar. Bir Minsky makinesinin program akışı gibi, bir akış şeması her zaman sayfanın üst kısmında başlar ve aşağı ilerler. Birincil semboller, sadece dört olan: yönlendirilmiş ok gösteren program akışı, dikdörtgen (SEKANS GOTO), elmas (IF-THEN ELSE) ve nokta (TD-bağlayıcı). Böhm-Jacopini kanonik yapılar, bu ilkel şekillerde imal edilmiştir. Alt yapı ancak tek çıkış üstyapısından oluşursa yalnızca, dikdörtgenler halinde "iç içe" can. Semboller ve kanonik yapıları inşa etmek için kullanımları diyagramında gösterilmiştir.

Örnekler

Algoritma örneği

Bir animasyon quicksort algoritması rasgele değerler dizisini sıralama. Kırmızı çubuklar Pivot elemanı işaretlemek; animasyon başlangıcında, sağ taraftaki eleman uzak eksen olarak seçilir.

En basit algoritmalar biri rasgele sayıları listesindeki en büyük sayı bulmaktır. Çözüm bulmak listedeki her numara bakarak gerektirir. Bu İngiliz nesir gibi bir üst düzey açıklama belirtilen basit bir algoritma aşağıdaki Gönderen:

Üst düzey açıklaması:

  1. Hiçbir sayılar kümesinde varsa o zaman hiçbir yüksek sayı yoktur.
  2. sette ilk sayı kümesinden en büyük sayıdır varsayın.
  3. kümesinde kalan her numara için: bu sayı büyük cari sayısından daha büyükse, bu sayı sette en fazla sayıda olduğunu düşünüyoruz.
  4. yineleme yapmak için sette sol hiçbir sayı olduğunda, büyük mevcut sayısı kümesinin en fazla sayıda olduğunu düşünüyoruz.

(Adeta) resmi açıklaması: nesir Yazılı ancak bir bilgisayar programının üst düzey dili çok daha yakın, aşağıdaki algoritmanın daha resmi kodlama olduğu pseudocode veya pidgin kodu :

Algorithm LargestNumber
  Input: A list of numbers L.
  Output: The largest number in the list L.
  if L.size = 0 return null
  largestL[0]
  for each item in L, do
    if item > largest, then
      largestitem
  return largest
  • "←" belirtmektedir atama . Örneğin, " büyüköğesi " nin bu değeri ifade eder büyük değerine değişiklikleri öğe .
  • " Geri dönüş " algoritması sonlandırır ve bir sonraki değerini verir.

Öklid algoritması

Daha ayrıntılı TL Heath (1908), adlı Öklid 'algoritma örneği diyagramı ilave edildi. Öklid üçüncü ölçüm ötesine geçerek hiçbir sayısal örnekler verir vermez. Nicomachus 49 ve 21 örnek verir:" daha az çıkarma; 28 sol olduğu; 7 sol olduğu;, ı 21 bu çıkarma, 14, daha sonra tekrar (mümkün olduğu için) 21, aynı Bu çıkarma sol (bu mümkün için) tekrar 7 çıkarma gösterilmiştir; "7 bırakılır, ancak 7 7. çıkarılır edilemez Heath "son cümle meraklı, ama bunun anlamı 'birinde ve aynı sayıda' biten hakkında ifade de anlam olarak, yeterince açıktır." Yorumunu yapmaktadır (Heath 1908: 300).

Euclid hesaplamak için algoritması büyük ortak böleni iki numaraya (GCD) onun Kitabı VII ( 'Sayılar Teorisi') olarak Proposition II olarak görünür Elements . Öklid sorunu şu şekilde ortaya: "Onların büyük ortak ölçü bulmak için, birbirine asal değil iki sayıyı göz önüne alındığında". O tanımlayan "bir dizi [olması] birimlerden oluşan bir çokluk": bir sayma sayısı, sıfır dahil bir pozitif tamsayıdır. "Ölçmek" için kısa bir ölçüm uzunluğu yerleştirmektir s , art arda ( q Daha uzun boyunca kez) l kalan kısmı kadar R daha kısa uzunlukta daha azdır s . Modern bir deyişle, geri kalan kısım olarak r = l - q x s , q bölüm olmak ya da geri kalan R tamsayıdır-kesir kısmı bölünme sonra kalan "modül" dir.

uzunlukları sıfır olmamalıdır, (i), (ii) çıkarma “uygun” olmalıdır;: Öklid yöntemi başarılı olması için, başlangıç ​​uzunlukları iki gereksinimi karşılamak zorundadır yani bir test (böylece onların çıkarma verimi sıfır alternatif olarak, iki eşit olabilir) büyük çıkarılır iki sayı daha küçük olduğunu garanti etmelidir.

Öklid'in özgün kanıtı üçüncü şartı ekler: İki uzunlukları birbirine asal olmamalıdır. O bir inşa diye Öklid bu öngörülen reductio reklamı absurdum iki numaralama ortak ölçü aslında dair kanıt büyük . Nicomachus' algoritma numaraları birbirine asal Öklid yıllardan, aynı olmakla birlikte, bunların ortak ölçü için '1' sayısını verir. Yani, kesin konuşmak gerekirse, şu gerçekten Nicomachus' algoritmasıdır.

Öklid algoritması grafiksel anlatım 1599 ve 650 için en büyük ortak böleni bulmak için.
 1599 = 650×2 + 299
 650 = 299×2 + 52
 299 = 52×5 + 39
 52 = 39×1 + 13
 39 = 13×3 + 0

Öklid algoritması için bilgisayar dili

Sadece birkaç talimat tipleri Öklid algoritması-bazı mantıksal testler (şartlı GOTO), koşulsuz GOTO, atama (yedek) ve çıkarma yürütmek için gereklidir.

  • Bir yer vb büyük harf (ler), örneğin, S, A, ile sembolize edilir
  • Bir yerde değişen miktarda (sayı) küçük harfle (ler) ve (genellikle) yerin adı ile ilişkili olarak yazılmıştır. Örneğin, başlangıçta yer L numarası içerebilir l = 3009.

Öklid algoritması için bir inelegant programı

"Kaba" bölünme onun kullanımı yerine, bir çıkarma tabanlı kalan-döngü (ya da "modül" komutu) ile algoritması Knuth versiyonu tercümesidir. 2-4: Knuth 1973 elde edilmiştir. İki sayının bağlı "inelegant" "Zarif" den daha az adımda gcd hesaplayabilir.

Aşağıdaki algoritma Öklid en ve Nicomachus', fakat daha çok kalan bulmak için bölme kullanarak daha arasında Knuth dört aşamalı bir versiyonu olarak çerçeveli, daha kısa uzunlukta ardışık çıkarmalar kullanır s kalan uzunluğu ile ilgili r kadar r daha azdır s . Kalın olarak gösterilen yüksek düzeyde bir açıklama, Knuth 1973 uyarlanmıştır: 2-4:

GİRİŞ :

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
  INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:
  R ← L

E0: [sağlamak rs .]

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
  IF R > S THEN
    the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
    GOTO step 6
  ELSE
    swap the contents of R and S.
4   L ← R (this first step is redundant, but is useful for later discussion).
5   R ← S
6   S ← L

E1: [Kalan bulun] : kalan uzunluk kadar R R daha kısa uzunlukta daha az ler S, art arda ölçüm sayısı çıkarma s kalan uzunluğu mesafede S r R.

7 IF S > R THEN
    done measuring so
    GOTO 10
  ELSE
    measure again,
8   R ← R − S
9   [Remainder-loop]:
    GOTO 7.

E2: [kalan sıfır mi?] : Son ölçü R içinde bir kalan sayısı: ya (i) son ölçü R kalan sıfırdır ve program durdurabilir veya (ii) algoritması devam etmelidir, tam olarak S. sayısının ölçülmesi daha az

10 IF R = 0 THEN
     done so
     GOTO step 15
   ELSE
     CONTINUE TO step 11,

E3: [ara- s ve r ] : Öklid algoritması somunu. Geri kalan kullanarak r daha önce daha küçük bir sayı ne ölçmek s ; L geçici bir konuma olarak hizmet vermektedir.

11  L ← R
12  R ← S
13  S ← L
14  [Repeat the measuring process]:
    GOTO 7

ÇIKIŞ :

15 [Done. S contains the greatest common divisor]:
   PRINT S

YAPILAN :

16 HALT, END, STOP.

Öklid algoritması için şık bir programdır

Öklid algoritması aşağıdaki sürümü "inelegant" gereği yapmak zorunda hangi on üç yapmak için sadece altı temel talimatları gerektirir; daha da kötüsü, "inelegant" daha fazlasını gerektirir türlerini talimatların. "Şık" nin akış şeması, bu makalenin başında bulunabilir. (Yapılandırılmamış) Temel dilinde adımlar numaralandırılmış ve talimat ← simgelediği atama talimatıdır. LET [] = []

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "Type two integers greater than 0"
  10 INPUT A,B
  20 IF B=0 THEN GOTO 80
  30 IF A > B THEN GOTO 60
  40 LET B=B-A
  50 GOTO 20
  60 LET A=A-B
  70 GOTO 20
  80 PRINT A
  90 END

Aşağıdaki sürümü Object Oriented dillerle kullanılabilir:

// Euclid's algorithm for greatest common divisor
integer euclidAlgorithm (int A, int B){
     A=Math.abs(A);
     B=Math.abs(B);
     while (B!=0){
          if (A>B) A=A-B;
          else B=B-A;
     }
     return A;
}

Nasıl "Zarif" çalışır : bir dış "Öklid döngü" yerine, "Zarif" ileri geri iki "eş-döngüler" arasında kaydırır, A ← A hesaplar bir A> B loop - döngü ≤ B ve B bu B ← B hesaplar - son çıkartılan M çıkan s (Farkı = çıkartılan - Çıkarılmış) daha az ya da eşit olduğu zaman A Bu çalışır, çünkü, çıkartılan olabilir s (yeni ölçüm uzunluğu) ve çıkan can yeni hale r (ölçülecek olan uzunluk); başka bir deyişle çıkarma "duygusu" tersine çevirir.

Öklid algoritmaları test

Bir algoritma yazarı bunu yapmak istediğini yapar mı? Birkaç test durumları genellikle temel işlevleri teyit etmek yeterlidir. Bir kaynak 3009 kullanır ve 884 Knuth 40902, 24140. başka ilginç durum iki önerdi aralarında asal sayılar 14157 ve 5950.

Ama istisnai vakalar tespit ve test edilmelidir. "Zarafetsiz" düzgün gerçekleştirecek zaman R> S, S> R, R = S? "Zarif" için Aynen: B> A, A> B, A = B? (Hepsine evet). Tek sayı sıfır olduğunda ne her iki sayı sıfır olur? ( "Zarafetsiz" her durumda sonsuza hesaplar; "Zarif" sonsuza kadar hesaplar zaman A = 0.) ne olur negatif sayılar girilir? Fraksiyonel numaralar? Giriş numaraları, yani ise alan algoritması / program tarafından hesaplanan fonksiyon, sıfır dahil olmak üzere, sadece pozitif tamsayılar, o zaman sıfırdan arızalar algoritması (ve program göstermektedir dahil etmektir örneğini o) a nın kısmi bir fonksiyonu yerine bir toplam fonksiyonu . İstisnalar nedeniyle dikkate değer bir başarısızlık Ariane 5 Flight 501 roket arızası (4 Haziran 1996).

Matematiksel tümevarım kullanılarak program doğruluğunun kanıtı : Knuth uygulanmasını gösteren matematiksel tümevarım Öklid algoritması bir "genişletilmiş" sürümüne ve o "herhangi algoritmanın geçerliliğini kanıtlayan için geçerli genel bir yöntem" önermektedir. Tausworthe bir programın karmaşıklığı bir ölçüsüdür onun doğruluğu ispat uzunluğu olmasını önermektedir.

Öklid algoritmaları ölçümü ve iyileştirilmesi

Elegance iyilik (hız) karşı (doluluk) : Sadece altı temel talimatları ile, "Elegant" onüç talimatlar kısmındaki "inelegant" ile karşılaştırıldığında, net kazanır. Ancak, "inelegant" dır hızlı (Bu daha az adımda HALT ulaşır). Algoritma analizi "Şık" yapar: Bu durumda neden gösterir iki "inelegant" sadece birini yapar, oysa her çıkarma döngüde koşullu testleri. Algoritma (genellikle) birçok döngü geçişi, gerektirdiği ortalama çok zaman bir "B = 0?" Yaptığını boşa Geri kalan hesaplanır sonra sadece gerekli olan test edin.

Algoritmalar geliştirilebilir mi? : Programcı hâkim sonra, onun tarafından işlev amaçlanan hesaplamasıdır -yani bir program "etkili" "uyum" ve yazar-sonra soru olur bu geliştirilebilir?

"Zarafetsiz" kompaktlığı beş adımdan ortadan kaldırılması ile iyileştirilebilir. Ama Chaitin bir algoritma sıkıştırma genelleştirilmiş algoritması tarafından otomatik olamaz kanıtladı; Aksine, yalnızca yapılabilir sezgisel ; yani, ayrıntılı arama ile (örnekler bulunabilir için meşgul kunduz ), deneme yanılma, zeka, fikir, uygulama indüktif akıl yürütme , vs. olduğu 4, 5 ve 6, adım 11, 12 ve 13 Karşılaştırma tekrarlanır adımları dikkate "Yakın" birlikte adım 2 ve 3 ile bu adımlar, elimine edilebilir bir ipucu sağlar. Bu dokuz adımlarda, "Zarif" olmadığı kadar "daha şık" yapar thirteen'den sekize çekirdek talimatlar sayısını azaltır.

"Yakın" hız hareket iyileştirilebilir "B = 0?" iki çıkarma halkaların dışında testi. Bu değişiklik, üç talimatlarına (B = 0 ?, A = 0 ?, GOTO) eklenmesi için çağırır. Şimdi "Zarif" hızlı ornek-sayılar hesaplar; bu her zaman, herhangi bir A için geçerli olup olmadığını, B ve R, S ayrıntılı bir analiz gerektirmektedir.

algoritmik analiz

Teorik olarak verilen bir algoritma için gereklidir nasıl belirli bir kaynağın çok (bu zamana veya depolama gibi) bilmek sıkça önemlidir. Yöntem için geliştirilmiştir algoritma analizi gibi nicel yanıt (tahminler) elde etmek üzere; örneğin, sıralama algoritması yukarıda O (bir zaman gereksinimi vardır , n kullanarak) büyük O notasyonu ile n listesi uzunluğu ile ilişkilidir. En fazla sayıda bugüne kadar bulunmuş ve giriş listesindeki geçerli konumu: Tüm zamanlarda algoritma sadece iki değeri hatırlaması gerekir. Nedenle, bir alan gereksinimi olduğu söylenir O (1) giriş numaralarını saklamak için gereken alan sayıldı, veya O (değilse, n ) o sayılır ise.

Farklı algoritmalar, farklı bir az veya daha fazla sürede talimat setinde, uzay, ya da 'ile aynı görevi tamamlayabilir çaba diğerlerinden daha'. Örneğin, bir ikili arama algoritması için kullanılan sıralı bir arama (maliyet O (n)) daha iyi performans (maliyet, O (n) log) Tablo aramaları sıralanmış listeleri veya diziler üzerinde.

ampirik formel

Algoritmaların analizi ve çalışma disiplini olan bilgisayar bilimleri ve genellikle belirli kullanılmadan soyut uygulanmaktadır programlama dili ya da uygulanması. O algoritmanın yatan özelliklerine değil, herhangi bir uygulama özelliklerini üzerinde duruluyor ki bu anlamda, algoritma analizi diğer matematiksel disiplinler benzer. Genellikle yalancı kod bu en basit ve en genel temsilidir olarak analiz için kullanılır. Ancak, sonuçta, en algoritmalar genellikle belirli donanım / yazılım platformlarında uygulamalar gerçekleştirilmiş ve algoritmik verimliliği sonunda gerçek kodu kullanarak teste tabi. (N çok büyük olmadığı sürece) bir "kapalı" sorunun çözümü için, belirli bir algoritma verimliliği önemli sonuçlara yol olmayabilir ama hızlı, etkileşimli ticari veya uzun ömürlü bilimsel kullanım için tasarlanmış algoritmalar için çok önemli olabilir. Büyük n küçük n dan ölçekleme sık aksi huyludur verimsiz algoritmalar ortaya çıkarır.

Performansı etkileyen beklenmedik etkileşimleri ortaya çıkarabilir çünkü Ampirik test yararlıdır. Deneyler programı iyileştirmeden sonra da bir algoritmaya potansiyel iyileştirmeler önce / sonra karşılaştırmak için kullanılabilir. Ampirik testler olsa, resmi analiz yerini alamaz ve adil bir şekilde gerçekleştirmek için önemsiz değildirler.

Yürütme verimliliği

Olası potansiyel iyileştirmeleri dahi köklü algoritmalar, yakın tarihli önemli yenilik, ilgili göstermek için FFT (görüntü işleme alanında yoğun kullanılan) algoritmaları, tıbbi görüntüleme gibi uygulamalar için 1.000 kez işlem süresi kadar azaltabilir. Genel olarak, hız iyileştirmeleri pratik uygulamalarda çok yaygındır sorunun özel özelliklerine bağlıdır. Bu büyüklükte speedups az güç tüketmek için (dijital kameralar ve tıbbi malzeme gibi) görüntü işleme kapsamlı kullanan bilgisayar cihazları sağlar.

sınıflandırma

algoritmalar, kendi yararları ile her sınıflandırmak için çeşitli yollar vardır.

uygulanması ile

algoritmalar sınıflandırmak için bir yolu uygulama aracılığıyla olur.

özyineleme
Bir geri dönüşümlü algoritma için ortak bir yöntem olan, belirli bir durum (aynı zamanda terminasyon koşulu olarak da bilinir) ile eşleşen, kadar sürekli olarak kendini çağırır (referans yapan) biri işlevsel programlama . Yinelemeli algoritmaları gibi tekrarlayan yapıları kullanın döngüler gibi bazen ek veri yapıları yığınlarının verilen sorunları çözmek için. Bazı sorunlar doğal olarak bir uygulamaya ya da diğer için uygundur. Örneğin, Hanoi kuleleri de özyinelemeli uygulama kullanarak anlaşılmaktadır. Her yinelemeli versiyonu (belki daha fazla ya da daha az karmaşık ama) iteratif versiyon, ya da tam tersi bir eşdeğerine sahiptir.
Mantıksal
Bir algoritma, kontrol olarak görülebilir mantıksal kesinti . Bu kavram olarak ifade edilebilir Algoritma = mantık + kontrol . Mantık modülünde tespitinde kullanılan ve kontrol bileşeni kesinti varsayımlarına uygulandığı yolu belirler edilebilir belitleri ifade eder. Bu temeli olan mantık programlama paradigması. Saf mantık programlama dilleri, kontrol bileşeni sabittir ve algoritmalar sadece mantık komponent tedarik tarafından belirtilir. Bu yaklaşımın itiraz zarif semantik : aksiyomların bir değişiklik algoritmasında iyi tanımlanmış değişikliğe neden olur.
Seri veya paralel dağıtımı
Algoritmalar genellikle bilgisayarlar bir anda bir algoritma öğretisini yürütmek varsayımıyla tartışılmıştır. Bu bilgisayarlar bazen seri bilgisayarlar denir. Bir tasarlanmış bir algoritma ile tersine, bu gibi bir ortamda, bir seri algoritması olarak adlandırılan algoritmaları paralel ya da dağıtılmış algoritma . Birkaç işlemciler aynı anda bir problem üzerinde çalışabilirsiniz nerede dağıtılan algoritmalar bir bağlı çok yönlü makinaları kullanmak oysa Paralel algoritmalar, bilgisayar mimarileri yararlanmak bilgisayar ağı . Paralel veya dağıtılmış algoritmalar daha simetrik ya da asimetrik alt problemlerden içine sorunu bölmek ve tekrar bir araya sonuçları toplamak. Bu tür algoritmalar kaynak tüketimi sadece her bir işlemci üzerinde işlemci çevrimleri değil, aynı zamanda işlemci arasındaki iletişim yükü olan. Bazı sıralama algoritmaları verimli parallelized edilebilir, ancak kendi iletişim havai pahalıdır. İteratif algoritmalar genellikle paralelleştirilebilir bulunmaktadır. Bazı sorunlar hiçbir paralel algoritmalar var ve seri problemler doğal olarak adlandırılır.
Deterministik ya da olmayan deterministik
Deterministik algoritmalar ise algoritma her aşamasında tam karar sorunu çözmek deterministik olmayan algoritmalar tipik tahmin kullanımı ile daha doğru çekilmiş, ancak tahmin ile sorunları çözmek sezgisel .
Tam veya yaklaşık
Birçok algoritmalar kesin çözüme ulaşılması da, yakınsama algoritmaları gerçek çözüme daha yakın bir yaklaşım ararlar. Yaklaşım deterministik ya da rastgele bir strateji kullanılarak, ya ile ulaşılabilir. Böyle algoritmalar birçok sert sorunları için pratik değeri vardır. Yaklaşık bir algoritmanın örneklerinden biri Sırt çantası sorun . Sırt çantası problemi verilen öğeler kümesi olduğu bir sorundur. Problemin amacı maksimum toplam değeri elde etmek çantasını paketi etmektir. Her öğe biraz kilo ve bazı değeri vardır. Biz taşıyabilir Toplam ağırlık Yani, biz öğelerin ağırlıkları hem de kendi değerini göz önüne almalıyız bazı sabit X numaralı başka bir şey değildir.
kuantum algoritması
Onlar gerçek bir modeli üzerinde çalışan kuantum hesaplama . Terim genellikle doğal olarak kuantum gibi, ya da bazı gerekli özelliğini kullanan algoritmalar için kullanılan kuantum bilgisayar gibi kuantum üst üste ya da kuantum dolaşıklık .

tasarım paradigma tarafından

algoritmalar sınıflandırmak bir başka yolu, tasarım metodolojisi veya paradigma gereğidir. her biri diğerinden farklı paradigmaların belirli sayıda vardır. Bundan başka, bu kategorilerin her algoritmaları birçok farklı türlerini içerir. Bazı yaygın paradigmalar şunlardır:

Kaba kuvvetle ya da kapsamlı arama
Bu en iyi olduğunu görmek için mümkün olan her çözüm çalışmakla naif bir yöntemdir.
Bölmek ve fethetmek
Bir bölme ve ele geçir algoritması tekrar tekrar (genellikle aynı sorun, bir veya daha fazla küçük örneklerine sorun örneğini azaltır yinelemeli örnekleri kolayca çözmek için yeterince küçük olana kadar). Böl ve istilası biri, örneğin bir sıralama birleştirme . Sıralama segmentleri veri bölünmesi ve parça birleştirme ile fethetmek aşamasında elde edilebilir tüm veri sıralama sonra verilerin her bir segment üzerinde yapılabilir. Böl ve istilası daha basit bir varyantı olarak adlandırılır azalmaya ve algoritma ele bu aynı subproblem çözer ve daha büyük sorunu çözmek için, bu subproblem çözümünü kullanır. Böl ve yen çoklu alt problemler içine problem böler ve bu fethetmek aşaması azaltmak ve ele algoritmalar daha karmaşıktır. Azalma ve fethet algoritma örneği olan ikili arama algoritması .
Arama ve numaralandırma
(Örneğin, oyun gibi birçok sorun satranç ) ilgili sorunlar olarak modellenebilir grafikler . Bir grafik arama algoritması bir grafik etrafında hareket etmek için kuralları belirtir ve bu problemleri çözmek için yararlı. Bu kategori içeren arama algoritmaları , dal ve sınır numaralandırma ve geriye gidilmiştir .
Rastgele algoritması
Bu tür algoritmalar bazı seçenekler rasgele (veya psödo-rasgele) olun. Bu pratik olabilir kesin çözüm bulmak sorunlar için yaklaşık çözümler bulmak oldukça yararlı olabilir (aşağıda sezgisel şekli). Bu sorunların bazıları için, en hızlı yaklaşımlar bazı içermek zorunda olduğu bilinmektedir rastgeleliğine . İle randomize algoritmaları İster polinom zaman karmaşıklığı bazı sorunlar için hızlı algoritmalar olabilir diye bilinen açık bir sorudur P eşit midir NP problemi . Böyle algoritmaların iki büyük sınıfa ayrılır:
  1. Monte Carlo algoritmaları yüksek olasılıklı bir doğru cevabı döndürür. Örneğin RP çalıştırmak olduğunu bunların alt sınıfıdır polinom zamanda .
  2. Las Vegas algoritmaları her zaman doğru yanıt dönmek, ama onların çalışma süresi sadece olasılıksal örneğin bağlıdır ZPP .
karmaşıklık Azaltma
Bu teknik biz (umarım) sahip olduğu için daha iyi bilinen bir sorun haline dönüştürerek zor sorunun çözümü içerir sonu§urda en algoritmalar. Amaç kimin indirgeyici algoritma bulmaktır karmaşıklık çıkan azaltılmış algoritma yıllardan hakim değildir. Örneğin, bir seçme algoritması kriteri listesinde orta eleman ilk listeyi (pahalı kısım) sıralama içermektedir sıralanmamış listesinde medyan bulma ve dışarı çekilmesi için (ucuz kısmı). Bu teknik olarak da bilinir dönüşümü ve ele .
Geri izleme
Bu yaklaşımda, çoklu çözümler aşamalı inşa edilmiş ve bunların geçerli bir tam çözüme götürmeyeceğini olabilir bulunduğunun tespit edildiği hallerde terk edilir.

Optimizasyon problemleri

İçin optimizasyon problemlerinin algoritmaları daha spesifik bir sınıflandırma yoktur; Bu tür sorunlar için bir algoritma, aşağıdakilerin bir veya içine ve aynı zamanda yukarıda tarif edilen genel kategoriye ayrılmaktadır düşebilir:

Doğrusal programlama
Lineer eşitlik ve eşit kısıtlamalarına bağlı bir doğrusal fonksiyonu için en uygun çözümler aranırken, sorun kısıtlamaları uygun çözümleri üretiminde doğrudan kullanılabilir. Böyle popüler olarak bu kategoride hiçbir sorunu çözebilir algoritmalar vardır simpleks algoritması . Doğrusal programlama ile çözülebilir sorunlar bulunmaktadır maksimum akış problemi yönlendirilmiş grafikler için. Bir sorun, ek gerektiriyorsa bilinmeyen bir ya da daha fazla bir olmalıdır tamsayıdır sonra sınıflandırılır tamsayı programlama . O tamsayı değerleri için tüm kısıtlamalar çözümler zaten bu sınırlamaları karşılamak, yani yüzeysel olduğu ispat edilebilirse doğrusal programlama algoritması böyle bir sorunu çözebilir. Genel durumda, özel bir algoritma ya da yaklaşık çözüm bulan bir algoritma sorun zorluğuna bağlı olarak kullanılır.
Dinamik program
Bir sorun gösterdiğinde optimum altyapıyı alt problemlerden en uygun çözümlerden inşa edilebilecek bir sorunun en iyi çözümü anlam - - ve örtüşen altproblemleri birçok farklı sorun örneklerini çözmek için kullanılanlarla aynı altproblemleri anlam, daha hızlı bir yaklaşım olarak adlandırılan dinamik programlama recomputing çözümler kaçındığı zaten bilgisayarlı edilmiştir. Örneğin, Floyd-Warshall algoritması , ağırlıklı olarak bir tepe bir hedef için en kısa yol grafiği tüm bitişik köşeler hedef için en kısa yol kullanılarak bulunabilir. Dinamik programlama ve memoization birlikte gidin. Alt problemler bölmek daha fazla veya daha az bağımsızdır ve ele bu alt problemler dinamik programlama yer itibariyle dinamik programlama ve böl ve istilası arasındaki temel fark vardır. Dinamik programlama ve anlaşılır özyineleme arasındaki fark önbelleğe alma veya özyinelemeli aramaların memoization içindedir. Alt problemler bağımsızdır ve tekrarlanmayacağını olduğunda, memoization yardımcı olmaz; dolayısıyla dinamik programlama bütün karmaşık sorunları için bir çözüm değildir. Memoization kullanarak veya muhafaza etmek suretiyle masa alt problemlerden zaten çözülmüş, dinamik programlama polinom karmaşıklığına birçok problemlerin üstel doğasını azaltır.
methot
Bir açgözlü algoritma değil sorunun ancak belirli bir çözümün bu durumda, inceleyerek alt yapı çalışır o dinamik programlama algoritması benzer. Bu tür algoritmalar verilebilir ya da bir şekilde inşa edilmiştir ve küçük değişiklikler yaparak bunu geliştirmek bir çözeltisi ile başlar. Diğerleri için onlar durdurmak sırasında bazı sorunlar için onlar en uygun çözüm bulabiliriz yerel optima yani algoritma geliştirilebilir değil ama en iyi değildirler olabilir çözümlere,. Açgözlü algoritmalar en popüler kullanımı optimum çözüm bulunması bu yöntemle mümkün olmaktadır minimum yayılan ağaç bulmakta içindir. Huffman Ağacı , Kruskal , Prim , Sollin bu optimizasyon sorunu çözebilir açgözlü algoritmalar bulunmaktadır.
buluşsal yöntem
In optimizasyon problemlerinin , sezgisel algoritmalar optimum çözüm bulma pratik olmadığı durumlarda optimum çözüme yakın bir çözüm bulmak için kullanılabilir. Bu algoritmalar onlar ilerledikçe optimum çözüme yaklaştıkça alarak çalışır. Zamanın sonsuz miktarda çalıştırırsanız Prensip olarak, onlar optimum çözüm bulacaktır. Onların hak ki nispeten kısa sürede optimum çözüme çok yakın bir çözüm bulmak olabilir. Bu tür algoritmalar içerir yerel arama , tabu arama , simüle tavlama ve genetik algoritmalar . Diğerleri, tabu arama gibi deterministik iken Bazıları, tavlama benzetimi gibi, deterministik olmayan algoritmalar bulunmaktadır. Optimum olmayan çözeltinin hata bağlanmış bir bilinen, algoritma ayrıca olarak kategorize edilir yaklaşım algoritması .

Çalışmanın Alana göre

Bilimin her alanını kendi sorunları var ve verimli algoritmalar ihtiyacı vardır. Bir alanda İlgili problemler sık birlikte incelenir. Bazı örnek sınıfları arama algoritmaları , sıralama algoritma , birleştirme algoritmaları , sayısal algoritmalar , grafik algoritmaları , string algoritmaları , hesaplama geometrik algoritmalar , kombinatoryal algoritmalar , tıbbi algoritmalar , makine öğrenme , şifreleme , veri sıkıştırma algoritmaları ve ayrıştırma teknikleri .

Alanlar birbiriyle örtüşen eğilimindedir ve bir alanda algoritma gelişmeler bazen tamamen ilgisiz diğer kişiler, alanlar artırabilir. Örneğin, dinamik programlama sektöründe kaynak tüketiminin optimizasyonu için icat edilmiştir ancak şimdi birçok alanda sorunların geniş bir yelpazede çözümünde kullanılmaktadır.

karmaşıklığı

Algoritmalar onların giriş boyutuna oranla tamamlamak için gereken süreyi tarafından sınıflandırılabilir:

  • Sabit süresi: algoritması tarafından gerekli zamanı ne olursa olsun giriş büyüklüğünün aynı olması durumunda. Örneğin, bir bir erişim dizi elemanı.
  • Doğrusal zamanı: Zaman giriş büyüklüğü ile orantılı olup olmadığını. Örneğin bir listenin çapraz.
  • Logaritmik zamanı: Zaman giriş boyutta bir logaritmik fonksiyonu ise. Örneğin ikili arama algoritması .
  • Polinom zamanı: Zaman giriş boyutta bir güç ise. Örneğin kabarcık sıralama algoritması kuadratik zaman karmaşıklığı vardır.
  • Üstel süresi: zaman giriş boyutlu bir üstel fonksiyon ise. Örneğin Kaba kuvvetle arama .

Diğer sorunlar hiçbir algoritmaları veya bilinen hiçbir verimli algoritmalar olabilir Bazı problemler, farklı karmaşıklık birden çok algoritmanın sahip olabilir. diğer sorunlara bazı problemlerden eşleştirmeleri de vardır. Bu sayede, bu sorunları kendileri yerine onlar için mümkün olan en iyi algoritmaların karmaşıklığı dayalı denklik sınıfa algoritmaları sınıflandırmak için daha uygun olduğu bulunmuştur.

Sürekli algoritmalar

kelimenin uygulandığında sıfat "sürekli" "algoritma" anlamına gelebilir:

  • Bu veri algoritmaları incelenmiştir ayrık bu yaklaşık değerler ile temsil edilir olsa da, sürekli miktarlarda temsil veri üzerinde işlem bir algoritma sayısal analiz ; veya
  • Bir şeklinde bir algoritma , diferansiyel denkleme bir çalışan, veri sürekli olarak çalışır analog bilgisayar .

Yasal sorunlar

Algoritmalar, tek başlarına genellikle patent verilebilir değildir. Amerika Birleşik Devletleri'nde, soyut kavramlar, sayılar veya sinyallerin basit manipülasyon sadece oluşan bir iddia "süreçleri" (2006 USPTO) teşkil etmez ve dolayısıyla algoritmaları (gibi patentsizdir Gottschalk v. Benson ). Ancak algoritmaların pratik uygulamaları bazen patent bulunmaktadır. Örneğin, elmas s. Diehr , basit bir uygulama geri besleme algoritması sertleştirilmesi yardımcı olmak üzere sentetik kauçuk patent görülmüştür. Yazılımın patent yüksek tartışmalıdır ve algoritmalar, özellikle kapsayan yüksek eleştirilmiştir patent bulunmaktadır veri sıkıştırma gibi algoritmaları, Unisys'ten ' LZW patent .

Ayrıca, bazı kriptografik algoritmalar ihracat kısıtlamaları (bkz sahip şifrelemenin ihracat ).

Tarih: "algoritma" kavramının geliştirilmesi

Antik Yakın Doğu

Algoritmalar Antik Yunanistan'da kullanılmıştır. İki örnek olarak Eratosthenes Sieve tarif edilmiştir, Aritmetik Introduction tarafından Nicomachus ve Öklid algoritma , ilk olarak tarif edilmiştir, Öklid 'Elemanlar (c. 300 BC). Babil kil tabletleri tarif ve önemli astronomik olayların yeri ve zamanı hesaplamak için algoritmik prosedürlerini kullanır.

Kesikli ve ayırt semboller

Tally-işaretleri : sopalarla üzerine çizilmiş taş veya işaretleri biriken veya kil ayrık semboller yapma: sürülerindeki, tahıl onların çuval ve paralarını eskilerin Sayım işlemleri kullanılan izlemek için. İşaretleri ve semboller, sonunda Babil ve Mısır kullanımı sayesinde Roma rakamlarıyla ve abaküs gelişti (Dilson, s. 16-41). Tally işaretleri belirgin görünür tekli rakamı sistemi kullanılan aritmetik Turing makinası ve Sonrası Turing makinası hesaplamaları.

sayılar için "yer tutucular" olarak sembollerin manipülasyonu: cebir

Antik işi Yunan geometri ( Öklit algoritması ), Hint matematikçi Brahmagupta ve Pers matematikçi Harizmi (adı terimleri "dan Arap rakamları ve Batı Avrupa matematikçiler sonuçlandı" ve "algoritma" türetilmiştir) Leibniz 'in kavramı taşı ratiocinator (1680 ile ca):

İyi bir yüzyıl ve öncesinde yaptığı zaman bir buçuk, Leibniz, sıradan cebir sayılar manipüle kurallarını belirten bir şekilde mantıksal kavramları işlemek için kuralları belirtmek istiyorum bir cebir mantığı bir cebir önerdi.

ayrık devletlerle Mekanik kurmaca

Saat : Bolter ağırlık güdümlü icat kredi saatinin özellikle "[Ortaçağ'da Avrupa] tuşuna buluş" olarak, eşiğinde maşası mekanik bir saatin kene ve tock bize sağlar. Hemen "mekanik yol açtı "doğru otomatik makine" otomata 13. yüzyılda başlayan" ve nihayet "hesaplama makineleri" ni- fark motoru ve analitik motorları arasında Charles Babbage ve Kontes Ada Lovelace , 19. yüzyılın ortalarında. Lovelace bir bilgisayarda işlenmesinde kullanılan bir algoritma ilk yaratılış ile yatırılmaktadır - Babbage'ın analitik motoru, ilk cihaz gerçek olarak kabul Turing-tam yerine sadece bilgisayar hesap makinesi ve bazen sonuç olarak "tarihin ilk programcı" denir - Babbage'ın ikinci cihazın tam olarak uygulanması yaşamı onlarca yıl sonra fark olmaz gerçi.

Mantıksal makineleri 1870- Stanley Jevons ' 'mantıksal abaküs' ve 'mantıksal makine' : teknik sorun azaltmak oldu Boole denklemler artık olarak bilinen benzer bir biçimde sunulduğunda Karnaugh haritaları . (1880) Jevons mekanik birinci [mantıksal] kombinasyonlarından herhangi bir bölümü ya da sınıf üzerinden çekilmesi ve böylece uydurulmasının pim ile donatılmış ahşap makbuzları" basit "abaküsümü" tarif etmektedir... Daha yakın zamanlarda, ancak, azalttı tamamen mekanik forma sistem ve dolayısıyla bir adlandırılabilir ne çıkarımın dolaylı sürecin bütününü somutlaşan gelmiş Mantıksal makine dibinde belli hareketli ahşap çubuklar "ve '' Onun makine ile donatılmış geldi" olanlar gibi 21 anahtarları bir piyano [vb]... ". Bu makine ile o bir "analiz edebilirsiniz tasımı veya başka herhangi bir basit mantıksal argüman".

Bu makine Royal Society Fellows önce 1870 yılında sergiledi. Başka mantıkçı John Venn , ancak, onun 1881 yılında Sembolik Mantık , bu çabaya Sarılıklı gözü döndü: "Ben hiçbir yüksek faiz veya bazen mantıksal makineleri denilen şeyin önemi kendim tahmin var ... o bana görünmüyor bilinen veya gerçekten keşfedilmeyi olasılığı şu anda herhangi bir kurmaca "mantıksal makinelerin ismini hak; En fazla görmek Algoritma karakterizasyonu . Ama o da Prof. Jevon en, ben tutuklama, bir plan biraz benzer" takdim altta kalmamak abaküs ... [Ve] Prof Jevons mantıksal makineye karşılık gelen [a] kazanç, aşağıdaki contrivance. Tercihim tarif edilebilir sadece mantıksal-diyagramı makinesi diyoruz ... ama çok tamamen bütün rasyonel herhangi mantıksal makinesi" beklenen edilebileceğini yapabileceğini varsaymak.

Jakarlı, Hollerith kartları, telgraf ve telefon-elektromekanik röle yumruk : Bell ve Newell (1971) göstermektedir jakarlı (1801), habercisidir Hollerith kartları (yumruk kartları, 1887) ve "telefon anahtarlama teknolojileri" olduğunu kökler bir ağacın ilk bilgisayarların gelişmesine yol açar. 19. yüzyılda telgraf , telefon öncüsü, dünya genelinde kullanılmakta olan oldu, "noktalar ve çizgiler" ortak ses olarak harflerin onun ayrık ve ayırt kodlama. 19. yüzyılın sonlarında By senedi bant 1890 ABD nüfus sayımında Hollerith kartlarının kullanılması gibi (ca 1870), kullanımda oldu. Sonra geldi telem onun delinmiş kağıdı kullanımı ile (takriben 1910) Baudot kodu kasete.

Telefon-anahtarlama ağları elektromekanik ait röleleri (1835 icat) çalışmalarına arkasında George Stibitz (1937), dijital ekleyerek cihazın mucidi. O Bell Laboratories çalışmış, o ". Vitesli mekanik hesap makineleri külfetli' kullanımını 'gözlemlenen O müdahalesi sona erdiğinde ..., Stibitz' ikili cihazı ekleyerek inşa etmişti fikrini test etmek isteyen 1937 yılında bir akşam eve gittim .

(2000) Davis (iki "ikili devletler" ile elektromekanik rölenin önem gözlemler açık ve kapalı ):

Bu makineler Babbage'den öngördüğü kapsama sahip inşa edildiğini, elektrik röleleri kullanılarak elektromekanik hesap makineleri, 1930'larda başlayan, ancak gelişme ile oldu."

20. yüzyılın ortalarında 19. yüzyıl sırasında Matematik

Semboller ve kurallar : hızlı arkaya olarak, matematik George Boole (1847 1854) adlı eserinde Gottlob Frege (1879), ve Giuseppe Peano (1888-1889) kuralları tarafından manipüle sembollerin bir dizisine aritmetik azaltmıştır. Peano yeni bir yöntem sunduğu aritmetik ilkeleri, (1888) "sembolik dille matematik aksiyomatikleştirilmesini ilk yapıldığında" oldu.

Ama Heijenoort (1879) bu şeref Frege veriyor: Frege yönettiği "belki bir bakın hangi hiç mantığı ile yazılmış en önemli tek eser ..." 'formülü dil', yani bir olduğunu lingua characterica , özel sembollerle yazılmış bir dil "saf düşünce için", yani retorik bezemeleri arınmış ... kesin kurallar" göre manipüle belirli sembollerle inşa. Frege işi daha da basitleştirilmiş ve tarafından güçlendirilmiş oldu Alfred North Whitehead ve Bertrand Russell onların içinde Principia Mathematica (1910-1913).

Paradokslar : Aynı zamanda rahatsız edici paradoks bir dizi özellikle, literatürde ortaya çıktı Burali-Forti paradoksu (1897), Russell paradoksu (1902-1903) ve Richard Paradox . Yol çıkan hususlar Kurt Gödel 'in kağıt (1931) -O özellikle yalancı-tamamen kurallarını azaltır paradoksu değinir özyineleme numaralarına.

Etkili hesaplanabilirlik : çözmek için bir çaba Entscheidungsproblem 1928 yılında Hilbert tarafından kesin olarak tanımlanmış, matematikçiler ilk olarak bir "etkili bir yöntem" veya "etkili hesaplama" veya "etkili hesaplanabilirlik" demek ne tanımlamak için yaklaşık set (yani bir hesaplama başarılı olacağını ). Peş peşe şu ortaya çıktı: Alonzo Church , Stephen Kleene ve JB Rosser 'ın λ-taşı Gödel önerileri üzerinde hareket etme işten 'genel özyineleme' bir bilenmiş tanımını Jacques Herbrand (Bkz 1934 Gödel'in Princeton dersler) ve Kleene tarafından sonradan basitleştirmeler. Kilisenin kanıtı Entscheidungsproblem, çözümsüz olduğunu Emil Mesaj bir işçi sersemce sola veya sağa oda dizisi boyunca ve hareket etmek talimatları listesini şu şekilde etkili hesaplanabilirlik ait 'in tanımı ya işareti ya da orada bir kağıt silmek veya kağıt gözlemlemek ve yaparken evet-hayır sonraki talimatla ilgili karar. Bu Entscheidungsproblem Alan Turing'in dayanıklı onun "a [Otomatik-] makine" Post "formülasyon" hemen hemen aynı -in etkisi kullanımı ile çözülemeyen olduğu , J. Barkley Rosser "bir açısından 'etkili bir yöntem' 's tanımı makine". SC Kleene habercisi için 'nin 'ın önerisi Kilisesi tezi o 'Tez ben' denilen' ve daha sonra Kleene en Onun Tezi 'Kilise'nin Tezi' yeniden adlandırma ve 'Turing'in Tezi' öneren bir kaç yıl.

Emil Mesaj (1936) ve Alan Turing (1936-1937, 1939)

İşte iki erkek birbirini bilerek ama erkekler-as-bilgisayarlar üzerinde çalışan bir işlemi açıklayan değil bir dikkate değer bir tesadüf hesaplamaların-ve onlar neredeyse özdeş tanımlarını verir.

Emil Mesaj (1936) bir "bilgisayar" (insan) aşağıdaki gibi eylemlerini tarif:

" ... iki kavram yer şunlardır: a bu sembol mekan cevaplamak için problemden açan çalışma yapılacak olduğu ve sabit bir değişmez yönlere seti .

Onun sembolü boşluk olurdu

"Boşluk veya kutuların iki yönlü sonsuz dizisi ... problem çözücü veya işçi .... bir kutu olma yeteneğine sahip, ve bir seferde kutuya ama bir faaliyet bu sembol uzayda hareket ve çalışma etmektir boş veya işaretsiz olduğu ve onunla tek bir işareti olan, fakat iki olası durumların yani itiraf etmektir, dikey bir vuruş söylüyorlar.
"Bir kutu saydı ve başlangıç ​​noktası olarak adlandırılabilir etmektir. ... Özel bir sorun kutuları [yani GİRİŞ] bir vuruş ile işaretlenen bir sonlu sayıda sembolik formda verilebilir etmektir. Benzer şekilde, bu sorunun cevabı [yani OUTPUT] işaretli kutuları gibi bir konfigürasyon ile sembolik formda verilmek üzere olan ...
"Bu tip (C) yönünde geldiği zaman her bir özel sorun uygulandığında genel soruna aktarılamaz yönde bir dizi deterministik işlemi oluşturur. Bu işlemi sona [yani, DUR"]. Daha fazla görün Sonrası Turing makinası
En Alan Turing'in heykeli Bletchley Park

Alan Turing'in çalışmaları (1937) Stibitz bu önce; o Stibitz Turing çalışmalarını biliyordu olup olmadığı bilinmemektedir. Turing'in biyografisini bir daktilo benzeri modelinin Turing'in kullanımı genç ilgi türetilen inanıyordu: "Alan çocukken daktilo icat etme hayali vardı; Bayan Turing daktilo vardı ve o da arayarak doğmuşum kendini sorarak başlamış olabilir bir daktilo " 'mekanik'. Hepimizin etkisi olduğunu varsayım olabilir Mors kodu ve telgrafçılığın senedi bant makineleri ve teleks cihazı yaygınlığı göz önüne alındığında.

Hesaplamanın Turing-onun modeli artık denir Turing makinası diye basit bir temel hareketlerin seti ve "aklın devletler" aşağı WHITTLES bir insan bilgisayarın bir analizi ile, Post yaptığı gibi, -begins. Ama o bir adım daha devam eder ve sayıların hesaplama model olarak bir makine oluşturur.

"Bilgi İşlem normalde kağıt üzerinde belirli simgeleri yazarak yapılır. Bu kağıt bir çocuğun aritmetik kitap gibi karelere bölünmüş varsayalım olabilir ... Ben hesaplama bölünmüş bir kasette, yani tek boyutlu kağıt, üzerinde yapılır o zaman varsayalım kare şeklinde. Ben de basılabilir sembollerin sayısının sonlu olduğunu varsayalım eder ...
o anda ruh hali ' "her an bilgisayarın davranışı o gözlemlemektir semboller ve onun tarafından belirlenir'. Biz semboller veya kareler bilgisayar can sayısında bir sınır B olduğunu varsayalım olabilir bir anda gözlemlemek. o daha gözlemlemek isterse, bunu izleyen gözlemleri kullanmalıdır. Ayrıca dikkate alınması gereken aklın ülkelerinin sayısı sonlu olduğunu varsayalım olacak ...
"Bize bilgisayar tarafından gerçekleştirilen operasyonlar onları daha da bölünmüş hayal etmek kolay değildir ki ilköğretim vardır 'basit operasyonlar' bölünmüş olması olduğunu düşünelim."

Turing'in azaltma şu sonucu verir:

"Basit işlemler dolayısıyla içermelidir:
"Gözlemlenen meydanlarından birinde sembolü (a) Değişiklikler
"(B) daha önce gözlemlenen kareler birinin L kareler içinde başka bir kareye gözlenen kareler birinin değişiklikler.

"Bu değişim bazı ille ruh hali değişikliği çağırmak olabilir en genel tek operasyon, bu nedenle, aşağıdakilerden biri için alınmalıdır.:

ruh hali olası bir değişikliği ile birlikte sembolün "(A) muhtemel bir değişiklik (a).
"Birlikte ruh hali olası bir değişikliği ile (B) gözlenen, karelerden oluşan bir muhtemel değişim, (b)"
"Artık bu bilgisayarın işi yapmak için bir makine inşa edilebilir."

Birkaç yıl sonra, Turing Bunu şu güçlü ifadesi ile yaptığı analiz (tez, tanım) genişletilmiş:

Bunu değerleri bazı tamamen mekanik işlem ile bulunabilir ise 'etkin bir şekilde hesaplanabilir "bir fonksiyon olduğu söylenir.' fikrin sezgisel kavramak için oldukça kolay olmasına rağmen, bazı daha kesin matematiksel eksprese tanımı için yine de gerekli olduğu .... Biz tamamen mekanik bir süreç teker anlamıyla anlaşılmasını bu açıklamayı sürebilir.. [o hemen hemen Gödel, Herbrand, Kleene, Kilise, Turing ve Post'a göre yukarıda sunulan tanım tarihini tartışıyor] hangi bir makine tarafından yürütülen mümkündür. makinelerin yapıların belli bir normal formda, matematiksel tanımını vermek mümkündür. bu fikirlerin gelişimi hesaplanabilir fonksiyonun yazarın tanımına yol açar ve bir tanıtımına etkili hesaplanabilirlik ile computability †....
hesaplanabilir fonksiyon "Biz ifade kullanmak zorundadır † '' bir makine tarafından hesaplanabilir bir işlev demek ve biz sağlamak için '' Bu tanımlardan herhangi biri ile belirli kimlik olmadan sezgisel fikrine başvurmak" etkili bir şekilde hesaplanabilir.

JB Rosser (1939) ve SC Kleene (1943)

J. Barkley Rosser aşağıdaki şekilde (yatık eklenmiştir) içinde bir 'etkili [matematik] yöntemi' tanımlanır:

" 'Etkin yöntem' her adımı tam kararlı ve sonlu adımda sayısında cevabı üretmek için belli olan bir yöntemin oldukça özel anlamda burada kullanılır. Bu özel anlamı ile üç farklı kesin tanımları verilmiş bugüne kadar [onun dipnot 5.; hemen aşağıdaki tartışmaya bakınız]. (nedeni Posta ve Turing kadar) devlete bu en basit olduğunu esasen söylüyor. biri daha sonra olacak bir makine inşa eğer sorunların belli setleri çözme etkili bir yöntem var soru ekleme ve (daha sonra) cevap okuma dışında hiçbir insan müdahalesi ile kümesinin herhangi bir sorunu çözmek , kullanıldığı hangisinin önemi yoktur bu yüzden. her üç tanımlar, eşdeğerdir. Üstelik her üç eşdeğer olduğu gerçektir bir herhangi birinin doğruluğu için çok güçlü argüman." (Rosser 1939: 225-6)

Rosser en dipnot No 5 referansları işi (1) Kilisesi ve Kleene ve bunun özellikle Kilise'nin kullanımında λ-tanımlanabilirlik onların tanımı, İlköğretim Sayılar Teorisi bir Çözümsüz Sorunu (1936); (2) Herbrand ve Gödel ve ünlü kağıt özellikle Gödel'in kullanımda ya yinelenen kullanımları Principia Mathematica ve İlgili Sistemler ben Resmen undecidable Önermeler Açık (1931); ve hesaplamanın kendi mekanizması-modellerinde (3) Gönder (1936) ve Turing (1936-1937).

Stephen C. Kleene olarak bilinen onun artık ünlü "Ben Tez" olarak tanımlanan Church-Turing tezi . Ama o bağlamda aşağıdaki (orijinalde kalın yazı tipi) bu yaptı:

"12. Algoritmik teoriler ... tam bir algoritmik teori kurma olarak, ne yapmamız zorunlu sonlandırır prosedür bağımsız değişkenlerin değerlerinin her set için performable ve böyle bir şekilde bir prosedür, tanımlamaktır sonucundan biz bu kesin bir cevap okumak, "evet" veya "hayır" sorusuna, "gerçek yüklem değeri nedir?""(Kleene 1943: 273)

Tarihçe 1950 sonrası

Çabaları bir dizi "algoritma" tanımına daha fazla geliştirilmesiyle yönlendirilir ve aktivite devam eden, çünkü çevredeki özellikle sorunların olduğunu edilmiştir matematik temellerini (özellikle Church-Turing tezi ) ve zihin felsefesi (özellikle argümanlar hakkında yapay zeka ). Daha fazla bilgi için, bkz Algoritma karakterizasyonları .

Ayrıca bakınız

notlar

Kaynakça

  • Axt, P (1959). "Bir Subrecursive Hiyerarşi ve İlkel Rekürsif Derece Üzerine". Amerikan Matematik Derneği İşlemler . 92 : 85-105. doi : 10,2307 / 1993169 . JSTOR  1993169 .
  • Bell, C. Gordon ve Newell, Allen (1971), Bilgisayar Yapıları: Okumalar ve Örnekler , McGraw-Hill Book Company, New York. ISBN  0-07-004357-4 .
  • Blass Andreas ; Gurevich Yuri (2003). "Algoritmalar: Mutlak Tanımlar Arayışı" (PDF) . Teorik Bilgisayar Bilimi Avrupa Birliği Bülteni . 81 . 56 referansların mükemmel bir bibliyografya vardır.
  • Eleme, David J. (1984). Turing'in Adam: Bilgisayar Çağında Batı Kültürü (1984 ed.). North Carolina Press Üniversitesi, Chapel Hill NC. ISBN  0-8078-1564-0 ., ISBN  0-8078-4108-0 PBK.
  • Boolos George ; Jeffrey Richard (1999) [1974]. Hesaplanabilirlik ve Mantık (4 ed.). Cambridge University Press, Londra. ISBN  0-521-20402-X .: Karş Bölüm 3 Turing makineleri onlar tartışmak "belli enumerable setleri değil etkin bir (mekanik) enumerable".
  • Burgin Mark (2004). Süper Rekörsif Algoritma . Springer. ISBN  978-0-387-95569-8 .
  • Campagnolo, ML, Moore, C , ve Costa, JF (2000) subrecursive fonksiyonların bir analog karakterizasyonu. İn Proc. Gerçek Sayılar ve bilgisayarları 4 Konferansı , Odense Üniversitesi, s. 91-109
  • Kilise, Alonzo (1936a). "Sayılar Teorisine bir çözümsüz Sorunu". Matematik American Journal . 58 (2): 345-363'te. doi : 10,2307 / 2371045 . JSTOR  2371045 .İçerisinde yayımlanmaktadır undecidable , s. 89ff. "Kilisenin Tez" ilk ifadesi. Belirli bir sayfa 100 (See undecidable o "bir algoritma" anlamında "etkili hesaplanabilirlik" kavramını tanımlar) ve o kelime "sona erer" vb kullanır
  • Kilise, Alonzo (1936b). "Entscheidungsproblem Üzerine Bir Not". Sembolik Mantık Dergisi . 1 (1): 40-41. doi : 10,2307 / 2269326 . JSTOR  2269326 .Kilise, Alonzo (1936). "Entscheidungsproblem bir Not Düzeltme". Sembolik Mantık Dergisi . 1 (3): 101-102 ° C. doi : 10,2307 / 2269030 . JSTOR  2269030 .İçerisinde yayımlanmaktadır undecidable , s. 110ff. Kilise Entscheidungsproblem metnin yaklaşık 3 sayfa ve dipnotlar 3 sayfalarında çözülemez olduğunu göstermektedir.
  • Daffa' Ali Abdullah (1977) el-. Müslüman katkısı matematik . Londra: Croom Helm. ISBN  0-85664-464-1 .
  • Davis, Martin (1965). Undecidable: undecidable önermeler, Çözümsüz Sorunları ve hesaplanabilir fonksiyonlar On Temel Kağıtlar . New York: Raven Press. ISBN  0-486-43228-9 .Davis her makaleden önce yorum sağlar. Ait Kağıtlar Gödel , Alonzo Church , Turing , Rosser , Kleene ve Emil mesaj dahildir; maddesinde belirtilen kişiler yazarın adıyla burada listelenir.
  • Davis, Martin (2000). Mantık Motorlar: Matematikçiler ve Bilgisayar Kökeni . New York: WW Nortion. ISBN  0-393-32229-7 .Davis özlü biyografileri sunmaktadır Leibniz , Boole , Frege , Cantor , Hilbert ile, Gödel ve Turing von Neumann gösterisi çalan kötü adam olarak. Çok kısa bios Joseph-Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken vb
  •  Bu makale içeriyor kamu malı olan materyaller  arasından  NIST belgede:  Siyah Paul E. "algoritma" . Algoritmalar ve Veri Yapıları Sözlüğü .
  • Dean, Tim (2012). "Evrim ve ahlaki çeşitlilik". Biliş, Mantık ve Haberleşme Baltık Uluslararası Yıllığı . 7 .
  • Dennett'in Daniel (1995). Darwin'in Tehlikeli Fikri . New York: Touchstone / Simon & Schuster. ISBN  0-684-80290-2 .
  • Dilson Jesse (2007). Abacus ((1968,1994) ed.). St Martin Press, NY. ISBN  0-312-10409-X ., ISBN  0-312-10409-X (PBK.)
  • Yuri Gurevich , Sıralı Özet Devlet Makineleri Sıralı Algoritmalar Yakalama , Hesaplamalı Logic, Cilt 1, no 1 (Temmuz 2000) üzerinde ACM İşlemler sayfalar 77-111. 33 kaynakların bibliyografya vardır.
  • Van Heijenoort Jean (2001). Frege itibaren Gödel, Matematiksel Mantık, 1879-1931 A Kaynak Kitabı ((1967) ed.). Harvard University Press, Cambridge, MA. ISBN  0-674-32449-8 ., 3. baskı 1976 [?], ISBN  0-674-32449-8 (PBK.)
  • Hodges, Andrew (1983). Alan Turing'in: Enigma . New York: Simon and Schuster . ISBN  0-671-49207-1 ., ISBN  0-671-49207-1 . Krş Bölüm giden bir geçmişi için "Hakikat Ruhu" ve bir tartışma, onun kanıtı.
  • Kleene, Stephen C. (1936). "Doğal Sayıların Genel Rekürsif İşlevleri" . Mathematische Annalen . 112 (5): 727-742. doi : 10.1007 / BF01565439 .Amerikan Matematik Derneği, Eylül 1935. yayımlanmaktadır Sunulan undecidable , s. 237ff. (Mu-özyineleme olarak şimdi bilinir) "genel özyineleme" nin Kleene'nin tanımı yaptığı 1.935 kağıt Kilisesi tarafından kullanıldı İlköğretim Numarası Teorisine bir Çözümsüz Sorunu (yani negatif sonuç) "Karar problemi" "undecidable" olduğunu kanıtladı.
  • Kleene, Stephen C. (1943). "Yinelemeli Yüklem ve Nicelemeler". Amerikan Matematik Derneği İşlemleri . 54 (1): 41-73. doi : 10,2307 / 1990131 . JSTOR  1990131 .İçerisinde yayımlanmaktadır undecidable , s. 255ff. Kleene "genel yineleme" kendi tanımını rafine ve bölüm "12. algoritmik teori" "Tezi I" tayin etmenin (s 274). İlerledi; (yani: (317 Kleene'nin 1952) ve "Kilisenin Tezi" adını: (300 Kleene 1952 yılında) daha sonra bu tezi tekrarlamak istiyorum Kilise tezi ).
  • Kleene, Stephen C. (1991) [1952]. Metamatematik giriş (Onuncu ed.). Kuzey Hollanda Yayıncılık Şirketi. ISBN  0-7204-2103-9 . Mükemmel erişilebilir matematiksel "vakıf" için, okunabilir referans kaynağı.
  • Knuth, Donald (1997). Temel Algoritmalar, Üçüncü Baskı . Okuma, Massachusetts: Addison-Wesley. ISBN  0-201-89683-4 .
  • Knuth, Donald (1969). Cilt 2 / Seminumerical Algoritmalar, Bilgisayar Programlama Birinci Baskı Sanatı . Okuma, Massachusetts: Addison-Wesley.
  • Kosovski'nin, NK Matematiksel Mantık Elemanları ve Subrecursive Algoritmaların teorisine Uygulanması , LSU Publ., Leningrad, 1981
  • Kowalski, Robert (1979). "Algoritma = Mantık + Kontrol". ACM İletişim . 22 (7): 424-436. doi : 10,1145 / 359.131,359136 .
  • AA Markov (1954) algoritmaların Teorisi . Damga Moskova, SSCB Bilimler Akademisi [Jacques J. Schorr-Kon ve PST personeli tarafından çevrilmiş] 1954 [yani, Kudüs, Bilimsel çevirileri 1961 için İsrail Programı; Teknik Hizmetler Dairesi, ABD Ticaret Bölümü, Washington] Açıklama 444 s edinilebilir. 28 cm. . TEORIYA algerifmov: Matematik Enstitüsü, SSCB Bilimler Akademisi, v 42. Orijinal başlık Eserlerinin Rus Çeviride eklendi tp. [QA248.M2943 Dartmouth Koleji kütüphanesi. ABD Ticaret Bölümü, Teknik Hizmetler Dairesi, numara 60-51085 OTS.]
  • Minsky'nin Marvin (1967). Hesaplama: Sonlu ve Sonsuz Makineleri (İlk ed.). Prentice-Hall, Englewood Cliffs, NJ. ISBN  0-13-165449-7 .Minsky bölüm 5.1 de "... bir algoritma-etkili prosedürün ... fikrini" onun genişletir Hesaplanabilirlik, Etkili Usul ve Algoritmalar. Sonsuz makineleri.
  • Mesaj Emil (1936). "Sonlu Combinatory Süreçler, Formülasyon I". Sembolik Mantık Dergisi . 1 (3): 103-105. doi : 10,2307 / 2269031 . JSTOR  2269031 .İçerisinde yayımlanmaktadır undecidable , s. 289ff. O basit talimatları listesini şu şekilde Post bir adamın basit bir algoritmik benzeri sürecini işaretlerin yazılması veya işaretlerini silme ve kutudan kutuya gidiyor ve sonunda durdurma tanımlar. Bu onun "Tez I", sözde bir kaynak olarak Kleene tarafından çağırılır Church-Turing tezi .
  • Rogers, Jr., Hartley (1987). Rekürsif Fonksiyonlar ve Etkili Hesaplanabilirlik Teorisi . The MIT Press. ISBN  0-262-68052-1 .
  • Rosser, JB (1939). "Godel'in Teoremi Kanıtlarının ve Kilise'nin Teoremi An Gayri Exposition". Sembolik Mantık Dergisi . 4 (2): 53-60. doi : 10,2307 / 2269059 . JSTOR  2269059 .İçerisinde yayımlanmaktadır undecidable , s. 223ff. ... "Her adımı kesin önceden belirlenmiş bir yöntem ve sonlu adımda sayıda ... sonra herhangi sorunu çözecek bir makinede cevap üretmek için belli olan: Burada "etkili bir yöntem" nin Rosser ünlü tanımıdır "cevabını okuma (daha sonra) soru ve ekleme dışında hiçbir insan müdahalesi ile seti (s. 225-226, undecidable )
  • Santos-Lang, Christopher (2014). "Ahlaki Ekoloji Makinesi Etik Yaklaşımlar". Van Rysewyk, Simon ise; Pontier Matthijs. Makine Tıbbi Etik (PDF) . İsviçre: Springer. s. 111-127. doi : 10.1007 / 978-3-319-08108-3_8 .
  • Scott, Michael L. (2009). Programlama Dili Edimbilim (3 ed.). Morgan Kaufmann Publishers / Elsevier. ISBN  978-0-12-374514-9 .
  • Sipser Michael (2006). Hesaplama Teorisine Giriş . PWS Publishing Company. ISBN  0-534-94728-X .
  • Ayık, Elliott; Wilson, David Sloan (1998). Bencil Davranış Evrimi ve Psikoloji: Diğerleri Unto . Cambridge: Harvard University Press.
  • Taş Harold, S. (1972). Bilgisayar Organizasyonu ve Veri Yapıları giriş (1972 ed.). McGraw-Hill, New York. ISBN  0-07-061726-0 .Krş Özellikle ilk bölüm başlıklı: Algoritmalar, Turing Makineleri ve Programlar . Onun öz gayri tanım: "... bir robot tarafından itaat edilebilir talimatların herhangi dizisi, bir denir algoritma (. S 4)".
  • Tausworthe, Robert C (1977). Bilgisayar Yazılım Bölüm 1 Yöntemlerinin Standartlaştırılmış Gelişimi . Englewood Cliffs NJ: Prentice-Hall, Inc. ISBN  0-13-842195-1 .
  • Turing Alan M. (1936-1937). "Entscheidungsproblem Bir Uygulamayla Hesaplanabilir Sayılar Üzerine". London Mathematical Society Kitabı . Seri 2. 42 : 230-265. doi : 10,1112 / PLMS / s2-42.1.230 .. Düzeltmeler, aynı eserde, Cilt. 43 (1937), s. 544-546. İçerisinde yayımlanmaktadır undecidable , s. 116ff. King College Cambridge İngiltere'de iken yüksek lisans tez olarak tamamlanan Turing'in ünlü kağıt.
  • Turing Alan M. (1939). "Mantık Sistemleri Ordinaller dayanarak". London Mathematical Society Kitabı . 45 : 161-228. doi : 10,1112 / PLMS / s2-45.1.161 .İçerisinde yayımlanmaktadır undecidable , s. 155ff. "Oracle" tanımlı Turing'in kağıt ederken Princeton ABD de doktora tezi oldu.
  • ABD Patent ve Marka Ofisi (2006), 2106,02 **> Matematiksel Algoritmalar: 2100 Patentlenebilirlilik , Patent elle incelenmesi Prosedürü (MPEP). Son revizyon Ağustos 2006

daha fazla okuma

Dış bağlantılar

Algoritma depoları
Ders Notları