Yazan : Şadi Evren ŞEKER Algoritma iki dizgiyi (string) karşılaştırmak için kullanılır. Basitçe bir dizgide aranan daha kısa dizginin öncelikle aşağıdaki şekilde karşılaştırılması ile başlanır. Ardından şayet uyum sağlanıyorsa bulundu olarak sonuç döndürülür, şayet uyum sağlanmıyorsa iki ihtimal vardır, dizgilerin karşılaştırılan kısımlarından uyan en uzun eke kadar kaydırma yapılır veya hiç uyuşma yoksa aranan dizgi […]
Category: Automata (otomatlar, özdevinirler)
Özdevinimliler, Özdevinirler veya otomatlar olarak türkçede geçen ve ingilizce literatüründe automata olan konu başlığı için ayrılmış kategöridir.
Emil Post Makinesi
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde özellikle özdevinirliler kuramında (automata theory) geçen bir makine modelidir. Yapı olarak Turing makinesine (Turing machine) çok benzer hatta ufak farklılıklar dışında neredeyse aynı olduğu söylenebilir. Turing makinesini geliştiren Alan Turing ile bağımsız olarak geliştirilmiştir. Bu anlamda Post makinesi bazı kaynaklarda Post-Turing makinesi (Post Turing Machine) olarak da geçmektedir. […]
Post Karşılık Problemi (Post Correspondence Problem)
Yazan : Şadi Evren ŞEKER Emil Post tarafından 1946 yılında ortaya atılan ve belirsiz karar problemi olarak sınıflandırılabilecek olan (undecidable decision problem) problemin ismidir. Literatürde kısaca PCP olarak da geçmektedir. Bu problem, yine Emil Post tarafından geliştirilen, Post Makinesi (post machine) olarak bilinen ve Turing makinesinin (Turing Machine) bir benzeri olan makinenin geliştirilmesini sağlamıştır. Problem, […]
Mealy ve Moore Makineleri (Mealy and Moore Machines)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde sıkça kullanılan sonlu durum makinelerinin (finite state machine, FSM veya Finite State Automaton , FSA) gösteriminde kullanılan iki farklı yöntemdir. Genelde literatürde bir FSM’in gösteriminde en çok moore makinesi kullanılır. Bu iki yöntem (mealy ve moore makinaları) sonuçta bir gösterim farkı olduğu için bütün mealy gösterimlerinin moore ve […]
Eşit a ve b bulunduran Turing Makinesi örneği
Yazan : Şadi Evren ŞEKER Turing makinesini anlattığım bu yazıda gelen bir soru üzerine, sorunun cevabını yayınlıyorum. Soruyu soran, onur bey, eşit sayıda a ve b bulunan bir kelimeyi kabul eden Turing makinesi tasarımı istemiş. Şimdi bu soru iki türlü anlaşılabilir. Kolay olanı anbn şeklinde a ve b harflerinin sırayla gelmesi. yani n tane a […]
Von Neumann Makinesi
Yazan : Şadi Evren ŞEKER Bilgisayar bilimleri açısından, von neumann makineleri, günümüz klasik bilgisayarlarının temellerini oluşturur. Bu makine tanımında basitçe bir işlemci, bir hafıza ve giriş / çıkış sistemleri modellenmiştir. Yukarıdaki şekilde görüldüğü üzere, hafıza (memory) ile bir kontrol birimi (control unit) ve bir de aritmetik mantıksal birim (artihmetic logical unit) arasında iletişim kurulmaktadır. Ayrıca […]
Ve/Veya bağlacı normal şeklleri (Conjunction / Disjunction Normal Form)
Yazan : Şadi Evren ŞEKER Bu gösterim, bool cebirinde (boolean algebra) kullanılan ve kaziyeleri (önerme, proposition) ve (and) bağlacı ile bağlamanın özel bir şeklidir. Kısaca CNF (conjuction normal form) olarak ifade edilir. Diğer bir normal şekil olan Chomsky Normal Form (CNF) ile ilgili bilgi arıyorsanız buradan ulaşabilirsiniz. Bu özel şeklin taşıdığı kuralları aşağıdaki şekilde sıralayabiliriz: […]
CYK Parçalama
Yazan : Şadi Evren ŞEKER CYK parçalama algoritması (parse algorithm), verilen girdinin (input), bir içerikten bağımsız dil (context free language) için nasıl parçalanabileceğini gösterir. CYK algoritmasının ismi, algoritmayı bulan kişilerin baş harflerinden oluşur: Cocke–Younger–Kasami. Algoritmadaki amaç, içerikten bağımsız dilin üretebileceği parçalama ağaçlarını veya alternatif parçalama yöntemlerini gösterebilmektir. [flashvideo file=http://www.bilgisayarkavramlari.com/wp-content/uploads/cyk.flv /] Bu durumu bir örnek üzerinden […]
DFA Metin Arama Algoritması (DFA Text Search)
Yazan : Şadi Evren ŞEKER 1. Otomatın İnşası 2. Algoritmanın arama aşaması 3. Algoritmanın çalışması 4. Algoritmanın kodlanması Bilgisayar bilimlerinde, bir metnin içerisinde farklı bir metnin veya bir kelimenin aranması sırasında kullanılan algoritmalardan birisidir. Algoritma, aranan kelime için bir otomat (automaton) oluşturur ve hedef metin içerisinde bu otomata göre arama işlemi yapar. Oluşturulana otomatın DFA […]
Push Down Automata
Yazan : Şadi Evren ŞEKER Aşağı sürüklemeli otomatlar (push down automaton) yapı olarak birer otomat makineleridir. Normal bir sonlu otomattan farkı, belirli (deterministic) olması ve ilave bir yığın (stack) bulundurmasıdır. Yani makinemiz basitçe her adımda ne yapacağından tam olarak emindir (belirli ,deterministict) ve veri depolamak için hafızada bulunan bir yığından (stack) istifade edebilir. Düzeltme (Tarık […]