Yazan: Şadi Evren ŞEKER Latince bölünemez anlamına gelen atom kökünden üretilen bu kelime, bilgisayar bilimlerinde çeşitli alanlarda bir bilginin veya bir varlığın bölünemediğini ifade eder. Örneğin programlama dillerinde bir dilin atomic (bölünemez) en küçük üyesi bu anlama gelmektedir. Mesela C dilinde her satır (statement) atomic (bölünemez) bir varlıktır. Benzer şekilde bir verinin bölünemezliğini ifade etmek […]
Category: algoritma analizi (teory of algorithms)
İçerik Bağımsız Gramerler için Pompalama Önsavı (Pumping Lemma for Context Free Grammers)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde bir dilin, içerik bağımsız gramer (context free grammer, CFG) ile gösterilemeyeceğini ispatlamaya yarar. Yani pompalama ön savı sayesinde bir dilin CFG olmadığı ispatlanabilir ancak olduğu ispatlanamaz. Şayet pompalama önsavını geçemyorsa CFG değildir denilebilir ancak geçmesi olmasını gerektirmez. Pomplama önsavı (pumping lemma) kısaca bir dili aşağıdaki gramere uydurmaya çalışır: […]
Düzenli İfadelerde Pompalama Önsavı (Pumping Lemma for Regular Expressions)
Yazan : Şadi Evren ŞEKER Bir dilin Düzenli ifadele (Regular expression) olup olmadığının belirlenmesi için kullanılan pomplama önsavıdı (pumping lemma). Basitçe düzenli ifadede olup olmadığı sınanacak bir w dili için (yani L = w için) w= xyz şeklinde bir açılım sınanır. Buradaki sınama sırasında aşağıdaki koşulların sağlanması beklenir: |y| ≥ 1 |xy| ≤ p bütün […]
Pompalama Önsavı (Pumping Lemma)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde dil tasarımı (language design, compiler design) konusunda önemli araçlardan birisidir. Bu önsava (lemma) göre şayet bir dil, bir herhangi bir gruba ( içerik bağımsız dil (context free language) veya düzenli ifadeler (Regular expression) yada farklı bir dil grubu ) dahil olarak kabul ediliyorsa, bu dil ne kadar pompalanırsa […]
İçerikten Bağımsız Gramer (context free grammer, CFG)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde, dil tasarımı sırasında kullanılan bir gramer tipidir. Basitçe bir dilin kurallarını (dilbilgisini, grammer) tanımlamak için kullanılır. Örneğin: S -> a Yukarıdaki dil tanımında bir büyük harfle gösterilen (S) bir de küçük harfle gösterilen (a) sembolleri bulunmaktadır. Bu satır, S devamlısının(nonterminal) a sonuncusuna(terminal) dönüştüğünü göstermektedir. Kısaca dildeki kuralları ifade […]
İçerikten bağımsız dil (Context Free Language, CFL)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde bir dilin tasarımı sırasında, içerik bağımsız bir gramer ile oluşturulması durumudur. Basitçe bir aşağı sürüklemeli otomat (push down automata) tarafından kabul edilen dil çeşididir. Bazı kaynaklarda bağlamdan bağımsız dil olarak da geçmektedir. Örneğin çok meşhur L= {anbn , n>0} dilini ele alalım. Bu dil örneğinin bu kadar meşhur […]
Dolaylı sıralama (Indirect Sort, Gayrimüstakim sıralama)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde sıralama işleminin çok büyük veriler üzerinde yapılması durumunda tercih edilen bir sıralama yöntemidir. Basitçe sıralama işleminin doğrudan verilerin yerinin değiştirilemsi ile değil de daha çok bu verileri gösteren gösterici (pointer) veya nesne atıfları (object referrer) ile yapılmasıdır. Örneğin sistemimizdeki öğrencileri sıralamak isteyelim. Her öğrenci bilgisi de sistemde 1MB […]
Harici Sıralama (External Sort)
Yazan : Şadi Evren ŞEKER Bir sıralama algoritmasının tamamının bilgisayarın hafızasına (Memory, RAM) yüklü olmaması durumudur. Yani klasik olarak bir dizi (array) veya bağlı liste (linked list) üzerinde yapılan sıralamaları dahili sıralama (internal sort) olarak isimlendirmek mümkündür. Harici sıralama klasik sıralamalardan farklı olarak, verinin ancak bir kısmının RAM’de durması durumunda devreye girer. Örneğin hafızamızın 100MB […]
A Yıldız Arama Algoritması (A Star Search Algorithm, A*)
A Yıldız Arama Algoritması (A Star Search Algorithm, A*) Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde en kısa yol bulmak için kullanılan algoritmalardan birisidir. Örneğin seyyar tüccar problemi (travelling salesman problem, TSP) gibi bir problemin çözümünde kullanılabilir. Benzer şekilde oyun programlamada, oyunda bulunan oyuncuların en kısa yolu bularak hedefe gitmeleri için de sıklıkla kullanılan algoritmadır. […]
Sezgi Üstü Algoritmalar (Üstsezgisel Algoritmalar, Meta Heuristic Algorithms)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde kullanılan algoritma tiplerinden birisi de sezgisel algoritmalardır. Temel olarak çalışmalarında kesinlik bulunmayan bu algoritmalar ya her zaman aynı performans ile çalışmaz ya da her zaman sonuç vermeyi garanti etmez ancak yine de problemi iyileştirme (optimisation) için kullanışlı algoritmalardır. Üstsezgisel algoritmalar ise bu sezgisel algoritmalar üzerinde çalışan bir karar […]