Ters Parça Algoritması (Reverse Factor Algorithm)
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…
SLR(1)
Yazan : Şadi Evren ŞEKER Bu yazının amacı, özellikle derleyici tasarımı (compiler design) konusunda sıkça kullanılan parçalama algoritmalarından (parse algorithm) birisi olan SLR(1) algoritmasını açıklamaktır. Algoritma, klasik LR algoritmalarından LR(1) algoritmasının basitleştirilmiş halidir. Bu anlamda Simplified LR(1) şeklinde okunabilir. LR(1)…
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…
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…
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…
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ü…
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…
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…
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…
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…