Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde bir programın istenen özellikleri yerine getirip getirememesine verilen isimdir. Buna göre şayet bir program, beklenen özellikleri tam ve eksiksiz yerine getiriyor, istenmeyen sonuçlar ortaya çıkmıyor ve program başladıktan sonra her durumda başarılı bir şekilde bitiyorsa bu programa tam doğru ( total correctness) ismi verilir. Durma probeleminden (halting problem) […]
Category: algoritma analizi (teory of algorithms)
Rastgele Sayılar (Random Numbers)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde çeşitli amaçlarla rastgele sayılara ihtiyaç duyulur. Örneğin şifreleme algoritmalarında önemli bir role sahip olan rastgele sayılar şifreleme işleminin gizliliği ve güvenilirlik açısından önemlidir. Benzer şekilde bir oyun programlanırken veya bir simülasyon sırasında rastgele cereyan eden olaylar modellenirken rastgele sayılara (random numbers) ihtiyaç duyulur ve bu sayıların gerçekten rastgele […]
Matematiksel Tümevarım Teoremi (Mathematical Induction Principle)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin de için de bulunduğu pek çok mühendislik ve bilim disiplinlerinin kullandığı ispat yöntemlerindendir. Temel olarak mantıktaki istikra (tümevarım) yaklaşımından faydalanır. Basitçe bir eşitliği ispatlamak için, eşitliğin her iki tarafı da birer kere ilerlettirilir (bir sonraki terimler için hesaplanır) şayet bu durum eşitliği bozmuyorsa ve eşitlik bir seri (sequence) […]
Özyineli Diller (Recursive Languages)
Yazan : Şadi Evren ŞEKER Özyineli diller matematik, mantık veya bilgisayar bilimlerinde geçen muntazam dillerden (formal language) birisidir. Genellikle kararverilebilir yani Turing makinesi (Turing machine) tarafından işlenebilir diller olarak kabul edilirler. Özyineli diller Chomsky hiyerarşisinde yer almamaktadır. Bir özyineli dili tanımlamak için iki önemli tanım yapılır. Birincisi dilin içerdiği alfabeden üretilebilen güç kümesinin (power set) […]
Karar Problemi (Decision Problem)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin de içinde bulunduğu pek çok bilim ve mühendislik dalını yakından ilgilendiren hesaplanabilirlik teorisi (computability theory) konusundaki problemlerden birisidir. Problemi basitçe tanımlama gerekirse bir koşulun (ki biz buna karar ismini vereceğiz) sağlanıp sağlanamadığını evet-hayır şeklinde ikili olarak (duality) sorgulamaktır. Örneğin x gibi bir sayının ikiye tam bölünüp bölünememesi bir […]
Turing Makinesi (Turing Machine)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin önemli bir kısmını oluşturan otomatlar (Automata) ve Algoritma Analizi (Algorithm analysis) çalıştırmalarının altındaki dil bilimin en temel taşlarından birisidir.1936 yılında Alan Turing tarafından ortaya atılan makine tasarımı günümüzde pekçok teori ve standardın belirlenmesinde önemli rol oynar. Turing Makinesinin Tanımı Basitçe bir kafadan (head) ve bir de teyp bandından […]
Özyineli sayılabilir küme (Recursively Enumerable Sets)
Yazan : Şadi Evren ŞEKER Hesaplanabilirlik teorisine (Computability Theory) bir sayı kümesi elemanlarının tamamının bir algoritma için çalışıp son bulma şartını sağlıyorsa özyineli sayılabilir küme olarak sınıflandırılır. Daha basit bir anlatımla kümede bulunan bütün elemanlar bir algoritma için, o algoritmanın bitmesini sağlayacak elemanlar olmalıdır. Daha akademik bir tanımla bir özyineli hesaplanabilir fonksiyon (Recursively Computable Function) […]
Hesaplanabilir Fonksiyon (Computable Function)
Yazan : Şadi Evren ŞEKER Hesaplanabilirlik teorisinin (Computability Theory) temel taşlarından birisi olan özel bir fonksiyon (function) tipidir. Bu fonksiyonların özelliği herhangi bir formal dilbilgisi (formal grammer) yardımıyla açıklanmayan fonksiyonlar olmalarıdır. Genellikle karıştırıldıkları için karmaşıklık teorisi (complexity theory) ile hesaplanabilirlik teorisi (computability theory) arasındaki farkı bu fonksiyonlar üzerinde de vurguluamakta yarar vardır. Basitçe bir fonksiyonun […]
Özyineli Küme (Recursive Set)
Yazan : Şadi Evren ŞEKER Hesaplanabilirlik teorisine (Computability Theory) göre bir doğal sayılardan oluşan bir kümedeki bütün elemanlar bir algoritmanın belirli bir zaman sonra sona ermesini sağlıyorsa bu kümeye özyineli küme ismi verilir. Şayet kümenin elemanlarından bir veya daha fazlası algoritmanın belirli bir zamanda bitmesini sağlamıyorsa bu kümeye hesaplanamaz (noncomputable) veya karar verilemez (undecidable) ismi […]
Hesaplanabilirlik Teorisi (Computability Theory)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimleri ve matematik açısından bir problemin sonucunun bulunup bulunamayacağı veya bir problemin sonucunun hesaplanabilir oldup olmadığı ile ilgilenen çalışma alanıdır. Karmaşıklık teorisi ile sıkça karıştırıldığı için aralarındaki farkı söyleyerek başlamakta yarar var. Karmaşıklık teorisi (complexity theory) bir problemin çözümünün ne kadar karmaşık olduğunu ve ne kadar zaman ve yer […]