Kıtlık (Starvation)
Yazan : Şadi Evren ŞEKER Bir algoritmada sıra bekleyen işlere bir türlü sıra gelmemesi durumudur. Teorik olarak sıradaki her işe birgün sıra gelecektir ancak fiiliyatta bu bir türlü gerçekleşmeyebilir. Bu tip problemler genelde öncelik tanımlanmış olan algoritmalarda çıkar. Şöyle bir…
İlk Gelen Çalışır (First Come First Serve, FCFS, FIFO)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin çeşitli alanlarında kullanılan bir yaklaşımdır. Bu yaklaşıma göre bir kaynak veya bir isıraya ilk gelenin ilk önce işini bitirerek çıkması hedeflenir. Örneğin CPU Scheduling (İşlemci zamanlama) problemi sırasında işlemciye gelen işlemlerin hangi sıra…
Komşuluk Listesi (Adjacency List)
Yazan : Şadi Evren ŞEKER Bir grafikteki her düğümün (node) komşularının listesine verilen isimdir. Örneğin aşağıdaki listeyi ele alalım: Bu grafikte hangi düğümün hangi düğümlerle komşu olduğunu tutan birer liste çıkarılması mümkündür. Örneğin A düğümünün komşuluk listesi (adjacency list) {B,C,D}…
Derin Öncelikli Arama (Depth First Search , DFS)
Derin Öncelikli Arama (Depth First Search , DFS) Yazan : Şadi Evren ŞEKER Bir ağaç dolaşma algoritmasının (tree traverse algorithm, tree traversal) ilk önce alt seviyesinde bulunan komşularını araması durumudur. Örneğin aşağıdaki ağacı ele alalım: Ağacı dolaşma sırlaması örneğin…
Sığ Öncelikli Arama (Breadth First Search , BFS)
Yazan : Şadi Evren ŞEKER Bir ağaç dolaşma algoritmasının (tree traverse algorithm, tree traversal) ilk önce aynı seviyede bulunan komşularını araması durumudur. Örneğin aşağıdaki ağacı ele alalım: Ağacı dolaşma sırlaması örneğin 5,7,8,3,2,1,9 şeklindeyse bu dolaşmaya sığ öncelikli arama ismi verilebilir….
Durma Problemi (Halting Problem)
Yazan : Şadi Evren ŞEKER Problem kısaca bir programın bir zaman sonra durup durmayacağının belirsizliği üzerine tartışmadır. Yani basitçe elimizde bir program ve bu programın parametresi olsun (programa verilebilen bir girdi). Programın bitip bitmeyeceğini bilemeyiz. Peki bunu nasıl ispatlarız? Burada…
Tersine Koyarak İspat (antitez, Contraposition)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde de kullanılan ispat yöntemlerinden birisi bir önermenin tersini ispatlayarak önermenin doğruluğunu göstermektir. Doğrudan ispat yöntemlerinde p -> q zinciri kullanılmaktadır. Bu yaklaşımda ise ¬p -> ¬q yaklaşımı ile iki önermenin de tersi alınır…
Doğrudan İspat (Direct Proofing)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin pekçok alanında da kullanılan ispat yöntemlerinden en basitidir. Bu yönteme göre ispatlanmak istenen durum genelde p->q şeklinde bir önermenin (kaziye) ispatının diğer bir önermeyi (kaziyeyi) gerektirdiği bir dizilimdir ve birisinin ispatı diğerini gerektirir….
NFA’den DFA’e çevirim (Converting NFA to DFA)
Yazan : Şadi Evren ŞEKER Bu yazıda belirsiz sonlu otomattan(NFA) Belirli sonlu otomata (gerekirci sonlu otomat, nedensel sonlu otomat, deterministic finite automata) dönüştürmenin nasıl yapıldığı anlatılmaktadır. Basitçe bir iki adımlık işlemler izlenerek bu dönüşüm gerçekleştirilebilir: Öncelikle gerekircilik (determinism) açısından birbiri…
Belirsiz Sonlu Otomat (Nondeterministic Finite Automat, NFA)
Yazan : Şadi Evren ŞEKER DFA (deterministic finite automat) belirli sonlu otomatların (özdevinirlerin) tersine her durumdan gidişin karışık olduğu ve her durum için bir sonraki kelimede nereye gidileceğinin belirli olmadığı otomatlardır. Basitçe DFA kurallarına uymayan bütün otomatlar NFA olarak adlandırılabilir….