Teorik bilgisayar bilimindeki önemli yayınların listesi - List of important publications in theoretical computer science
Bu, teorik bilgisayar bilimlerindeki önemli yayınların alana göre düzenlenmiş bir listesidir .
Belirli bir yayının önemli olarak görülmesinin bazı nedenleri:
- Konu yaratıcısı – Yeni bir konu oluşturan bir yayın
- Atılım – Bilimsel bilgiyi önemli ölçüde değiştiren bir yayın
- Etki – Dünyayı önemli ölçüde etkilemiş veya teorik bilgisayar bilimi öğretimi üzerinde büyük bir etkisi olan bir yayın.
hesaplanabilirlik
Cutland'ın Hesaplanabilirliği: Özyinelemeli Fonksiyon Teorisine Giriş (Cambridge)
- Cutland, Nigel J. (1980). Hesaplanabilirlik: Özyinelemeli Fonksiyon Teorisine Giriş . Cambridge Üniversitesi Yayınları . ISBN'si 978-0-521-29465-2.
Purdue Üniversitesi'nden ( Endüstriyel ve Uygulamalı Matematik İncelemeleri Derneği'nde) Carl Smith tarafından yapılan bu erken metnin incelemesi, bunun "ispatların açıklanmasında... klasik özyineleme teorisinin sonuçları [RT]... bir tarzda... minimum matematiksel altyapıya sahip lisans öğrencilerinin erişebileceği bir tarzda". Matematik öğrencileri için "[RT]'de bir giriş dersi için mükemmel bir giriş metni olacağını" belirtirken, bilgisayar bilimi öğrencileriyle birlikte kullanıldığında "öğretmenin materyali önemli ölçüde artırmaya hazır olması gerektiğini" öne sürer ( bu alana RT uygulamaları konusunda malzeme kıtlığı verildi).
Sonsuz ağaçlar üzerinde ikinci dereceden teorilerin ve otomatların karar verilebilirliği
- Michael O. Rabin
- Amerikan Matematik Derneği İşlemleri , cilt. 141, s. 1-35, 1969
Açıklama: Makale , otomatların bir uzantısı olan ağaç otomatını sundu . Ağaç otomatının programların doğruluğunu kanıtlamak için sayısız uygulaması vardı .
Sonlu otomatlar ve karar problemleri
- Michael O. Rabin ve Dana S. Scott
- IBM Araştırma ve Geliştirme Dergisi , cilt. 3, s. 114–125, 1959
- Çevrimiçi sürüm
Tanım: Otomatların matematiksel olarak işlenmesi, temel özelliklerin ispatı ve deterministik olmayan sonlu otomatın tanımı .
Otomata Teorisine, Dillere ve Hesaplamaya Giriş
Açıklama: Popüler bir ders kitabı.
gramerlerin belirli biçimsel özellikleri üzerine
- Chomsky, N. (1959). "Dilbilgilerinin belirli biçimsel özellikleri üzerine" . Bilgi ve Kontrol . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .
Açıklama: Bu makale, şu anda Chomsky hiyerarşisi olarak bilinen , resmi diller oluşturan resmi dilbilgisi sınıflarının bir sınırlama hiyerarşisini tanıttı .
Hesaplanabilir sayılarda, Entscheidungsproblem'e bir uygulama ile
- Alan Turing
-
Londra Matematik Derneği Bildirileri , Seri 2 , cilt. 42, s. 230–265, 1937, doi : 10.1112/plms/s2-42.1.230 .
Hatalar ciltte göründü. 43, pp. 544–546, 1938, doi : 10.1112/plms/s2-43.6.544 . - HTML sürümü , PDF sürümü
Açıklama: Bu makale bilgisayar biliminin sınırlarını belirler. Tüm hesaplamalar için bir model olan Turing Makinesini tanımladı . Öte yandan, durma probleminin ve Entscheidungsproblem'in kararsızlığını kanıtladı ve bunu yaparak olası hesaplamanın sınırlarını buldu.
Rekursive Funktionen
- Peter, Rozsa (1951). Rekursive Funktionen . Akademik Basın. ISBN'si 9780125526500.
Özyinelemeli fonksiyonlar teorisi üzerine ilk ders kitabı . Kitap birçok kez basılmış ve Péter kazanılan Kossuth Ödülü gelen Macar hükümeti. Tarafından Yorumlar Raphael M. Robinson ve Stephen Kleene öğrenciler için etkili bir temel giriş sağlamak için kitabı övdü.
Sinir Ağlarında ve Sonlu Otomatlarda Olayların Temsili
- SC Kleene
- ABD Hava Kuvvetleri Projesi Rand Araştırma Memorandumu RM-704 , 1951
- Çevrimiçi sürüm
- yeniden yayınlandı: Shannon, Claude ; McCarthy, John , ed. (1956). Otomata Çalışmaları . OCLC 564148 .
Açıklama: Bu makale sonlu otomatları , düzenli ifadeleri ve düzenli dilleri tanıttı ve bağlantılarını kurdu.
Hesaplamalı karmaşıklık teorisi
Arora & Barak'ın Hesaplamalı Karmaşıklığı ve Goldreich'in Hesaplamalı Karmaşıklığı (her ikisi de Cambridge)
- Sanjeev Arora ve Boaz Barak, "Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım", Cambridge University Press, 2009, 579 sayfa, Ciltli
- Oded Goldreich, "Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, 606 sayfa, Ciltli
Bu son metinleri öne çıkaran saygın basının yanı sıra, Arkansas Üniversitesi'nden Daniel Apon tarafından ACM'nin SIGACT Haberlerinde çok olumlu bir şekilde gözden geçirildiler ve bunları "erken mezunları hedefleyen karmaşıklık teorisi dersi için ders kitapları… veya ... ileri düzey lisans öğrencileri… [ile] sayısız, benzersiz güçlü ve çok az zayıf nokta" ve her ikisinin de şöyle olduğunu belirtiyor:
"hesaplama karmaşıklığı teorisinin hem genişliğini hem de derinliğini kapsamlı bir şekilde kapsayan mükemmel metinler... yazarlar tarafından... her biri [her biri] bilgisayar teorisinde dev [her biri olacak] ... alan... [ve bu] ...herhangi bir düşünce okulunun teorisyenleri, araştırmacıları ve eğitmenleri her iki kitabı da faydalı bulacaktır."
Eleştirmen, "[Arora ve Barak]'ta çok güncel materyalleri dahil etme yönünde kesin bir girişim olduğunu, Goldreich'in ise sunulan her kavram için bağlamsal ve tarihsel bir temel geliştirmeye odaklandığını" ve "alkışladığını[ları] belirtiyor. ] tüm… olağanüstü katkıları için yazarlar."
Özyinelemeli fonksiyonların karmaşıklığının makineden bağımsız teorisi
- Blum, Manuel (1967). "Öyinelemeli Fonksiyonların Karmaşıklığına İlişkin Makineden Bağımsız Bir Teori" (PDF) . ACM Dergisi . 14 (2): 322-336. doi : 10.1145/321386.321395 . S2CID 15710280 .
Açıklama: Blum aksiyomları .
Etkileşimli ispat sistemleri için cebirsel yöntemler
- Lund, C. ; Fortnow, L .; Karloff, H.; Nisan, N. (1992). "Etkileşimli ispat sistemleri için cebirsel yöntemler". ACM Dergisi . 39 (4): 859-868. CiteSeerX 10.1.1.41.9477 . doi : 10.1145/146585.146605 . S2CID 207170996 .
Açıklama: Bu makale, PH'nin IP'de bulunduğunu gösterdi .
Teorem kanıtlama prosedürlerinin karmaşıklığı
- Cook, Stephen A. (1971). "Teorem Kanıtlama Prosedürlerinin Karmaşıklığı" (PDF) . Bilgisayar Teorisi Üzerine 3. Yıllık ACM Sempozyumu Tutanakları : 151–158. CiteSeerX 10.1.1.406.395 . doi : 10.1145/800157.805047 . S2CID 7573663 .
Açıklama: Bu makale, NP-Tamamlanma kavramını tanıttı ve Boolean tatmin edilebilirlik sorununun (SAT) NP-Complete olduğunu kanıtladı . Benzer fikirlerin biraz sonra bağımsız olarak Leonid Levin tarafından "Levin, Universal Search Problems. Problemy Peredachi Informatsii 9(3):265–266, 1973"de geliştirildiğini unutmayın.
Bilgisayarlar ve İnatçılık: NP-Bütünlük Kuramı İçin Bir Kılavuz
- Garey, Michael R. ; Johnson, David S. (1979). Bilgisayarlar ve İnatçılık: NP-Bütünlük Kuramı İçin Bir Kılavuz . New York: Freeman. ISBN'si 978-0-7167-1045-5.
Tanım: Bu kitabın asıl önemi, 300'den fazla NP-Complete probleminden oluşan kapsamlı listesinden kaynaklanmaktadır . Bu liste ortak bir referans ve tanım haline geldi. Kitap, kavramın tanımlanmasından sadece birkaç yıl sonra yayınlanmış olmasına rağmen, bu kadar kapsamlı bir liste bulundu.
Bir fonksiyonu hesaplamanın zorluk derecesi ve özyinelemeli kümelerin kısmi sıralaması
- Rabin, Michael O. (1960). "Bir işlevi hesaplamanın zorluk derecesi ve özyinelemeli kümelerin kısmi sıralaması" (PDF) . Teknik Rapor No. 2 . Kudüs: İbrani Üniversitesi.
Açıklama: Bu teknik rapor, daha sonra hesaplama karmaşıklığı olarak yeniden adlandırılan şeyden bahseden ilk yayındı.
Simpleks yöntemi ne kadar iyi?
- Victor Klee ve George J. Minty
- Klee, Victor ; Minty, George J. (1972). "Simpleks algoritması ne kadar iyi?". Shisha'da, Oved (ed.). Eşitsizlikler III (Kaliforniya Üniversitesi, Los Angeles, Kaliforniya'da düzenlenen Üçüncü Eşitsizlikler Sempozyumu Tutanakları, 1-9 Eylül 1969, Theodore S. Motzkin'in anısına adanmıştır) . New York-Londra: Akademik Basın. s. 159–175. MR 0332165 .
Açıklama: ebatlan "Klee-Minty küp" inşa D 2, D köşeli bir tarafından ziyaret Dantzig sitesindeki simpleks algoritması için doğrusal optimizasyonu .
Rastgele fonksiyonlar nasıl oluşturulur
- Goldreich, O .; Goldwasser, S .; Micali, S. (1986). "Rastgele işlevler nasıl oluşturulur" (PDF) . ACM Dergisi . 33 (4): 792-807. doi : 10.1145/6490.6503 . S2CID 17064126 .
Açıklama: Bu makale, tek yönlü fonksiyonların varlığının hesaplamalı rastgeleliğe yol açtığını gösterdi .
IP = UZAY
- Shamir, A. (1992). "IP = PSPACE". ACM Dergisi . 39 (4): 869-877. doi : 10.1145/146585.146609 . S2CID 315182 .
Açıklama: IP, karakterizasyonu ( etkileşimli kanıt sistemlerine dayalı ) olağan zaman/uzay sınırlı hesaplama sınıflarından oldukça farklı olan bir karmaşıklık sınıfıdır . Bu yazıda, Shamir Lund ve diğerleri, önceki kağıt tekniği genişletilmiş., Göstermek için Pspace içerdiği IP dolayısıyla IP = Pspace ve bir karmaşıklık sınıftaki her bir sorun, diğer çözülebilir olduğu, böylece.
Kombinatoryal problemler arasında indirgenebilirlik
- RM Karp
- RE Miller ve JW Thatcher, editörler, Complexity of Computer Computations , Plenum Press, New York, NY, 1972, s. 85–103
Açıklama: Bu kağıt gösterdi 21 farklı sorunlar vardır NP-Complete ve kavramın önemini gösterdi.
Etkileşimli Kanıt Sistemlerinin Bilgi Karmaşıklığı
- Goldwasser, S .; Micali, S. ; Rackoff, C. (1989). "Etkileşimli Kanıt Sistemlerinin Bilgi Karmaşıklığı" (PDF) . SIAM J. Comput. 18 (1): 186–208. doi : 10.1137/0218012 .
Açıklama: Bu makale sıfır bilgi kavramını tanıttı .
Gödel'den von Neumann'a bir mektup
- Kurt Gödel
- A Letter Gödel için John von Neumann , 20 Mart 1956
- Çevrimiçi sürüm
Açıklama: Gödel , verimli evrensel teorem ispatlayıcı fikrini tartışıyor.
Algoritmaların hesaplama karmaşıklığı hakkında
- Hartmanis, Juris ; Stearns, Richard (1965). "Algoritmaların hesaplama karmaşıklığı üzerine" . Amerikan Matematik Derneği'nin İşlemleri . 117 : 285–306. doi : 10.1090/s0002-9947-1965-0170805-7 .
Açıklama: Bu makale, hesaplama karmaşıklığına adını ve tohumunu verdi .
Yollar, ağaçlar ve çiçekler
- Edmonds, J. (1965). "Yollar, ağaçlar ve çiçekler". Kanada Matematik Dergisi . 17 : 449-467. doi : 10.4153/CJM-1965-045-4 .
Açıklama: İki parçalı olmayan bir grafikte maksimum eşleşmeyi bulmak için bir polinom zaman algoritması vardır ve hesaplama karmaşıklığı fikrine doğru başka bir adım . Daha fazla bilgi için [2]'ye bakın .
Kapı fonksiyonlarının teorisi ve uygulamaları
- Yao, AC (1982). "Teori ve trapdoor fonksiyonlarının uygulaması". 23. Yıllık Bilgisayar Biliminin Temelleri Sempozyumu (SFCS 1982) . s. 80–91. doi : 10.1109/SFCS.1982.45 .
Açıklama: Bu makale, trapdoor işlevleri için teorik bir çerçeve oluşturur ve kriptografide olduğu gibi bazı uygulamalarını açıklar . Kapak kapısı işlevleri kavramının altı yıl önce "Kriptografide yeni yönler"de getirildiğini unutmayın (Bkz. Bölüm V "Sorun İlişkileri ve Tuzak Kapıları").
Hesaplamalı Karmaşıklık
Açıklama: Hesaplamalı karmaşıklık teorisine bir giriş olan kitap, yazarının P-SPACE ve diğer sonuçları karakterize etmesini açıklar.
Etkileşimli kanıtlar ve yaklaşan kliklerin sertliği
- Feige, U. ; Goldwasser, S .; Lovász, L. ; Safra, S. ; Szegedy, M. (1996). "Etkileşimli kanıtlar ve yakınlaşan kliklerin sertliği" . ACM Dergisi . 43 (2): 268-292. doi : 10.1145/226643.226652 .
İspatların olasılıksal kontrolü: NP'nin yeni bir karakterizasyonu
- Arora, S. ; Safra, S. (1998). "İspatların olasılıksal kontrolü: NP'nin yeni bir karakterizasyonu". ACM Dergisi . 45 : 70–122. doi : 10.1145/273865.273901 . S2CID 751563 .
Kanıt doğrulama ve yaklaşım problemlerinin sertliği
- Arora, S. ; Lund, C. ; Motwani, R .; Sudan, M .; Szegedy, M. (1998). "Kanıt doğrulama ve yaklaşım problemlerinin sertliği". ACM Dergisi . 45 (3): 501–555. CiteSeerX 10.1.1.145.4652 . doi : 10.1145/278298.278306 . S2CID 8561542 .
Açıklama: Bu üç makale, yalnızca yaklaşık bir çözüm gerekli olduğunda bile NP'deki belirli sorunların zor kaldığı şaşırtıcı gerçeğini ortaya koydu. PCP teoremine bakın .
Fonksiyonların İçsel Hesaplama Zorluğu
- Cobham, Alan (1964). "İşlevlerin İçsel Hesaplamalı Zorluğu" (PDF) . 1964 Uluslararası Mantık, Metodoloji ve Bilim Felsefesi Kongresi Tutanakları : 24-30.
Açıklama: Karmaşıklık sınıfı P'nin ilk tanımı. Karmaşıklık teorisinin kurucu makalelerinden biri.
algoritmalar
"Teoremi kanıtlamak için bir makine programı"
- Davis, M .; Logemann, G.; Loveland, D. (1962). "Teorem kanıtlamak için bir makine programı" (PDF) . ACM'nin İletişimi . 5 (7): 394-397. doi : 10.1145/368273.368557 . hdl : 2027/mdp.39015095248095 . S2CID 15866917 .
Açıklama: DPLL algoritması . SAT ve diğer NP-Complete problemleri için temel algoritma .
"Çözünürlük ilkesine dayalı makine odaklı bir mantık"
- Robinson, JA (1965). "Çözüm İlkesine Dayalı Bir Makine Yönelimli Mantık". ACM Dergisi . 12 : 23–41. doi : 10.1145/321250.321253 . S2CID 14389185 .
Tanım: Otomatik teorem ispatında kullanılan çözümleme ve birleştirmenin ilk tanımı ; kullanılan Prolog ve mantık programlama .
"Gezgin-satıcı problemi ve minimum kapsayan ağaçlar"
- Tutulan, M .; Karp, RM (1970). "Gezgin-Satıcı Problemi ve Minimum Yayılan Ağaçlar". Yöneylem Araştırması . 18 (6): 1138-1162. doi : 10.1287/opre.18.6.1138 .
Açıklama: NP-Tam seyahat eden satıcı problemi için bir yaklaşım algoritması olarak minimum yayılan ağaç için bir algoritmanın kullanımı . Yaklaşım algoritmaları , NP-Complete problemleriyle başa çıkmak için yaygın bir yöntem haline geldi.
"Doğrusal programlamada bir polinom algoritması"
- LG Khaçiyan
- Sovyet Matematiği - Doklady , cilt. 20, s. 191–194, 1979
Açıklama: Uzun süredir, doğrusal programlama problemi için kanıtlanabilir bir polinom zaman algoritması yoktu . Khachiyan, polinom olan bir algoritma sağlayan ilk kişiydi (ve önceki algoritmalar gibi çoğu zaman yeterince hızlı değildi). Daha sonra Narendra Karmarkar daha hızlı bir algoritmayı şu adreste sundu: Narendra Karmarkar, "Doğrusal programlama için yeni bir polinom zaman algoritması", Combinatorica , cilt 4, no. 4, s. 373-395, 1984.
"İlkelliği test etmek için olasılıksal algoritma"
- Rabin, M. (1980). "İlkelliği test etmek için olasılıksal algoritma" . Sayı Teorisi Dergisi . 12 (1): 128–138. doi : 10.1016/0022-314X(80)90084-0 .
Açıklama: Makale Miller-Rabin asallık testini sundu ve rastgele algoritmaların programını özetledi .
"Simüle edilmiş tavlama ile optimizasyon"
- Kirkpatrick, S. ; Gelatt, CD; Vecchi, MP (1983). "Simüle Tavlama ile Optimizasyon". Bilim . 220 (4598): 671-680. Bibcode : 1983Sci...220..671K . CiteSeerX 10.1.1.123.7607 . doi : 10.1126/science.220.4598.671 . PMID 17813860 . S2CID 205939 .
Açıklama: Bu makalede , artık NP-Complete sorunları için çok yaygın bir buluşsal yöntem olan benzetilmiş tavlama anlatılmıştır .
Bilgisayar Programlama Sanatı
Açıklama: Bu monografın popüler algoritmaları kapsayan dört cildi vardır. Algoritmalar hem İngilizce hem de MIX derleme dilinde (veya daha yeni fasiküllerde MMIX derleme dilinde) yazılmıştır . Bu, algoritmaları hem anlaşılır hem de kesin hale getirir. Bununla birlikte, düşük seviyeli bir programlama dilinin kullanılması , modern yapılandırılmış programlama dillerine daha aşina olan bazı programcıları hayal kırıklığına uğratır .
Algoritmalar + Veri Yapıları = Programlar
- niklaus wirth
- Prentice Salonu, 1976, ISBN 0-13-022418-9
Tanım: Pascal'da uygulamalarla, algoritmalar ve veri yapıları hakkında erken ve etkili bir kitap.
Bilgisayar Algoritmalarının Tasarımı ve Analizi
- Alfred V. Aho , John E. Hopcroft ve Jeffrey D. Ullman
- Addison-Wesley, 1974, ISBN 0-201-00029-6
Açıklama: Yaklaşık 1975–1985 dönemi için algoritmalar üzerine standart metinlerden biri.
Bilgisayarla Nasıl Çözülür
- Dromey, RG (1982). Bilgisayarla Nasıl Çözülür ? Prentice-Hall Uluslararası. ISBN'si 978-0-13-434001-2.
Açıklama: açıklar Neden ler algoritma ve veri yapıları. Açıklar Yaratıcı Süreci , MUHAKEMENİN Hattı , Tasarım Faktörler yenilikçi çözümler arkasında.
algoritmalar
- Robert Sedgewick
- Addison-Wesley, 1983, ISBN 0-201-06672-6
Açıklama: 1980'lerin sonlarında algoritmalar üzerine çok popüler bir metin. Aho, Hopcroft ve Ullman'dan daha erişilebilir ve okunabilirdi (ancak daha basitti). Daha yeni baskılar var.
Algoritmalara Giriş
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest ve Clifford Stein
- 3. Baskı, MIT Press, 2009, ISBN 978-0-262-03384-8 .
Açıklama: Bu ders kitabı o kadar popüler hale geldi ki, temel algoritmaları öğretmek için neredeyse fiili standart haline geldi. İlk baskı (ilk üç yazarlı) 1990'da, 2. baskı 2001'de ve 3. baskı 2009'da yayınlandı.
Algoritmik bilgi teorisi
"Rastgele Sayıların Tablolarında"
- Kolmogorov, Andrei N. (1963). "Rastgele Sayıların Tablolarında". Sankhya Ser. Bir . 25 : 369-375. MR 0178484 .
- Kolmogorov, Andrei N. (1963). "Rastgele Sayıların Tablolarında" . Teorik Bilgisayar Bilimi . 207 (2): 387–395. doi : 10.1016/S0304-3975(98)00075-9 . MR 1643414 .
Açıklama: Olasılığa hesaplamalı ve kombinatoryal bir yaklaşım önerdi.
"Endüktif çıkarımın resmi bir teorisi"
- Ray Solomonoff
- Bilgi ve Kontrol , cilt. 7, s. 1-22 ve 224-254, 1964
- Çevrimiçi kopya: Kısım I , Kısım II
Açıklama: Bu, algoritmik bilgi teorisinin ve Kolmogorov karmaşıklığının başlangıcıydı . Kolmogorov karmaşıklığının adını Andrey Kolmogorov'dan almasına rağmen , bu fikrin tohumlarının Ray Solomonoff'tan kaynaklandığını söyledi . Andrey Kolmogorov bu alana çok katkıda bulundu, ancak sonraki makalelerde.
"Algoritmik bilgi teorisi"
- Chaitin, Gregory (1977). "Algoritmik bilgi teorisi" (PDF) . IBM Araştırma ve Geliştirme Dergisi . 21 (4): 350–359. CiteSeerX 10.1.1.48.3094 . doi : 10.1147/rd.214.0350 . Orijinalinden (PDF) 2009-05-30 tarihinde arşivlendi .
Tanım: Bölgedeki önemli kişilerden biri tarafından algoritmik bilgi teorisine giriş .
bilgi teorisi
"Bir matematiksel iletişim teorisi"
- Shannon, CE (1948). "Bir matematiksel iletişim teorisi" . Bell Sistemi Teknik Dergisi . 27 (3): 379–423, 623–656. doi : 10.1002/j.1538-7305.1948.tb01338.x . hdl : 10338.dmlcz/101429 .
Açıklama: Bu makale, bilgi teorisi alanını oluşturdu .
"Hata algılama ve hata düzeltme kodları"
- Hamming, Richard (1950). "Hata algılama ve hata düzeltme kodları" . Bell Sistemi Teknik Dergisi . 29 (2): 147–160. doi : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 .
Açıklama: Bu yazıda, Hamming hata düzeltme kodu fikrini tanıttı . Hamming kodunu ve Hamming mesafesini yarattı ve kod optimalliği kanıtları için yöntemler geliştirdi.
"Minimum artıklık kodlarının oluşturulması için bir yöntem"
- Huffman, D. (1952). "Minimum Fazlalık Kodlarının Oluşturulması İçin Bir Yöntem" (PDF) . IRE'nin Bildirileri . 40 (9): 1098-1101. doi : 10.1109/JRPROC.1952.273898 .
Açıklama: Huffman kodlaması .
"Sıralı veri sıkıştırma için evrensel bir algoritma"
- Ziv, J .; Lempel, A. (1977). "Sıralı veri sıkıştırma için evrensel bir algoritma" . Bilgi Teorisi Üzerine IEEE İşlemleri . 23 (3): 337-343. CiteSeerX 10.1.1.118.8921 . doi : 10.1109/TIT.1977.1055714 . hdl : 10338.dmlcz/142947 . Arşivlenmiş orijinal 2003-12-04 tarihinde.
Açıklama: LZ77 sıkıştırma algoritması.
Bilgi Teorisinin Unsurları
- T. Kapak ; J. Thomas (1991). Bilgi Teorisinin Unsurları . s. 38-42 . ISBN'si 978-0-471-06259-2.
Açıklama: Bilgi teorisine popüler bir giriş.
Resmi doğrulama
Programlara Anlam Atama
- Floyd, Robert (1967). "Programlara Anlam Atama". Bilgisayar Biliminin Matematiksel Yönleri (PDF) . Uygulamalı Matematikte Sempozyum Bildirileri. 19 . s. 19–32. doi : 10.1090/psapm/019/0235771 . ISBN'si 9780821813195.
Açıklama: Robert Floyd'un dönüm noktası niteliğindeki makalesi Programlara Anlam Atama, tümevarımsal iddialar yöntemini tanıtıyor ve birinci dereceden iddialarla açıklamalı bir programın bir ön ve son koşul belirtimini karşıladığının nasıl gösterilebileceğini açıklıyor – makale ayrıca değişmez döngü kavramlarını da tanıtıyor. ve doğrulama koşulu.
Bilgisayar programlaması için belitsel bir temel
- Hoare, ARABA (Ekim 1969). "Bilgisayar programlama için bir aksiyomatik temel" (PDF) . ACM'nin İletişimi . 12 (10): 576–580. doi : 10.1145/363235.363259 . S2CID 207726175 . Arşivlenmiş orijinal (PDF) 2016-03-04 tarihinde.
Açıklama: Tony Hoare'nin Bilgisayar Programlama için Aksiyomatik Bir Temel adlı makalesi, (şimdiki adıyla) Hoare üçlüleri cinsinden tanımlanan Algol benzeri bir programlama dilinin parçaları için bir dizi çıkarım (yani biçimsel kanıt) kuralı tanımlar.
Korunan Komutlar, Belirsizlik ve Programların Resmi Türetilmesi
- Dijkstra, EW (1975). "Korumalı komutlar, belirsizliği ve programların resmi türetilmesi" . ACM'nin İletişimi . 18 (8): 453-457. doi : 10.1145/360933.360975 . S2CID 1679242 .
Açıklama: Edsger Dijkstra'nın Korumalı Komutlar, Belirsizlik ve Programların Resmi Türevi (1976 lisansüstü ders kitabı A Discipline of Programming tarafından genişletilmiş) başlıklı makalesi, bir programı yazıldıktan sonra (yani post facto) resmi olarak doğrulamak yerine, programların ve bunların resmi kanıtları el ele geliştirilmelidir (en zayıf ön koşulları aşamalı olarak iyileştirmek için yüklem dönüştürücüler kullanılarak), program (veya resmi) iyileştirme (veya türetme) olarak bilinen bir yöntem veya bazen "yapıya göre doğruluk".
Paralel Programlar Hakkındaki İddiaları Kanıtlamak
- Edward A. Ashcroft
- J. Bilgisayar. Sist. bilim 10(1): 110–135 (1975) doi : 10.1016/s0022-0000(75)80018-3
Açıklama: Eşzamanlı programların değişmezlik kanıtlarını tanıtan kağıt.
Paralel Programlar için Aksiyomatik Bir Kanıt Tekniği I
- Susan S. Owicki , David Gries
- Acta Bilgi. 6: 319–340 (1976)
Açıklama: Bu makalede, aynı yazarların "Verifying Properties of Parallel Programs: An Axiomatic Approach. Commun. ACM 19(5): 279–285 (1976)" başlıklı makalesiyle birlikte paralel program doğrulamaya aksiyomatik yaklaşım sunulmuştur.
Bir Programlama Disiplini
- Edsger W. Dijkstra
- 1976
Tanım: Edsger Dijkstra'nın klasik lisansüstü düzeydeki ders kitabı A Discipline of Programming, daha önceki kitabı Korumalı Komutlar, Belirsizlik ve Programların Biçimsel Türetilmesi'ni genişletir ve programların (ve kanıtlarının) spesifikasyonlarından resmi olarak türetilmesi ilkesini kesin olarak belirler.
düz anlambilim
- Joe Stoy
- 1977
Tanım: Joe Stoy'un Denotational Semantics'i, programlama dillerinin biçimsel semantiğine (operasyonel ve cebirsel yaklaşımların aksine) matematiksel (veya işlevsel) yaklaşımın kitap uzunluğundaki ilk (lisansüstü düzeyde) açıklamasıdır.
Programların geçici mantığı
- Pnueli, A. (1977). "Programların geçici mantığı". 18. Yıllık Bilgisayar Biliminin Temelleri Sempozyumu (SFCS 1977) . IEEE. s. 46-57. doi : 10.1109/SFCS.1977.32 . S2CID 117103037 .
Açıklama: Biçimsel doğrulama için bir yöntem olarak zamansal mantığın kullanılması önerildi.
Sabit noktaları kullanarak paralel programların doğruluk özelliklerini karakterize etme (1980)
- E. Allen Emerson , Edmund M. Clarke
- Proc. Otomata Dilleri ve Programlama üzerine 7. Uluslararası Kolokyum, sayfa 169-181, 1980
Açıklama: Model kontrolü, eşzamanlı programların doğruluğunu kontrol etmek için bir prosedür olarak tanıtıldı.
Sıralı Süreçlerin İletişimi (1978)
- ARABA
- 1978
Açıklama: Tony Hoare'nin (orijinal) iletişim kuran ardışık süreçler (CSP) makalesi, değişkenleri paylaşmayan, bunun yerine yalnızca eşzamanlı mesajları değiş tokuş ederek işbirliği yapan eşzamanlı süreçler (yani programlar) fikrini ortaya koymaktadır.
İletişim Sistemleri Hesabı
- Robin Milner
- 1980
Açıklama: Robin Milner'ın İletişim Sistemleri Hesabı (CCS) makalesi, daha önceki eşzamanlılık modelleri (semaforlar, kritik bölümler, orijinal CSP) için mümkün olmayan bir şey olan, eşzamanlı süreç sistemlerinin resmi olarak gerekçelendirilmesine izin veren bir süreç cebirini açıklar.
Yazılım Geliştirme: Titiz Bir Yaklaşım
- uçurum Jones
- 1980
Açıklama: Cliff Jones'un ders kitabı Yazılım Geliştirme: Titiz Bir Yaklaşım, önceki on yılda IBM'in Viyana araştırma laboratuvarında (esas olarak) gelişen ve program fikrini birleştiren Viyana Geliştirme Yöntemi'nin (VDM) ilk kapsamlı açıklamasıdır. arıtma göre Dijkstra veri arıtma (veya şeyleşme) o ile cebirsel tanımlanmış veri tipleri resmi giderek daha "beton" temsilleri haline getirilmesi mümkündür.
Programlama Bilimi
- David Gries
- 1981
Açıklama: David Gries'in Programlama Bilimi ders kitabı, Dijkstra'nın daha önceki A Discipline of Programming'inden çok daha erişilebilir bir yol dışında, Dijkstra'nın en zayıf önkoşul biçimsel program türetme yöntemini tanımlar .
Doğru çalışan programların nasıl oluşturulacağını gösterir (yazma hataları dışında hatasız). Bunu, programların oluşturulma şeklini yönlendirmek için ön koşul ve son koşul yüklem ifadelerinin ve program kanıtlama tekniklerinin nasıl kullanılacağını göstererek yapar.
Kitaptaki örneklerin tümü küçük ölçeklidir ve açıkça akademiktir (gerçek dünyanın aksine). Sıralama ve birleştirme ve dizi işleme gibi temel algoritmaları vurgularlar. Alt yordamlar (işlevler) dahil edilmiştir, ancak nesne yönelimli ve işlevsel programlama ortamları ele alınmamıştır.
Ardışık Süreçlerin İletişimi (1985)
- ARABA
- 1985
Açıklama: Tony Hoare'nin Communicating Sequential Processes (CSP) ders kitabı (şu anda tüm zamanların en çok atıfta bulunulan üçüncü bilgisayar bilimleri referansı), işbirliği yapan süreçlerin program değişkenlerine bile sahip olmadığı ve CCS gibi süreç sistemlerinin işlem sistemlerine izin verdiği güncellenmiş bir CSP modeli sunar. resmi olarak mantıklı olun.
Doğrusal mantık (1987)
- Girard, J.-Y (1987). "Doğrusal Mantık" (PDF) . Teorik Bilgisayar Bilimi . 50 (1): 1–102. doi : 10.1016/0304-3975(87)90045-4 . Orijinalinden (PDF) 2006-11-29 tarihinde arşivlendi .
Tanım: Girard'ın lineer mantığı , özellikle kaynak bilinçli tipleme sistemleri için sıralı ve eşzamanlı hesaplama için tipleme sistemleri tasarlamada bir atılımdı.
Mobil Süreçler Hesabı (1989)
Açıklama: Bu makale , süreç hareketliliğine izin veren CCS'nin bir genellemesi olan Pi-Calculus'u tanıtmaktadır . Hesap son derece basittir ve programlama dilleri, yazım sistemleri ve program mantıklarının teorik çalışmasında baskın paradigma haline gelmiştir.
Z Notasyonu: Bir Referans Kılavuzu
- Spivey, JM (1992). Z Notasyonu: Bir Referans Kılavuzu (2. baskı). Prentice Hall Uluslararası. ISBN'si 978-0-13-978529-0. Arşivlenmiş orijinal 2016-06-20 tarihinde . 2009-08-24 alındı .
Açıklama: Mike Spivey'in klasik ders kitabı The Z Notation: A Reference Manual , Jean-Raymond Abrial tarafından ortaya çıkmasına rağmen (esas olarak) Oxford Üniversitesi'nde önceki on yılda geliştirilmiş olan resmi belirtim dili Z notasyonunu özetler .
İletişim ve Eşzamanlılık
- Robin Milner
- Prentice-Hall Uluslararası, 1989
Açıklama: Robin Milner'ın İletişim ve Eşzamanlılık ders kitabı, teknik olarak hala gelişmiş olmasına rağmen, daha önceki CCS çalışmalarının bir açıklamasıdır.
Pratik bir Programlama Teorisi
- Eric Hehner
- Springer, 1993, güncel baskı burada çevrimiçi
Açıklama: Tahmine dayalı programlamanın güncel sürümü . CAR Hoare'nin UTP'sinin temeli . En basit ve en kapsamlı biçimsel yöntemler.
Referanslar
- ACM Algoritmalar ve Hesaplama Teorisi Özel İlgi Grubu (2011). "Ödüller: Gödel Ödülü" . Arşivlenmiş orijinal 22 Nisan 2018 . Erişim tarihi: 8 Ekim 2011 .