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 ile çalışacağı bu algoritmaya göre belirlenirse ilk gelen iş bitmeden ikinci iş başlayamaz. Bir sıra […]
Category: algoritma analizi (teory of algorithms)
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. Bu arama sıralamasında, dolaşma sıralaması aşağıdaki ihtimallerden birisi olabilir: NLR : Node Left Right (Düğüm […]
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 ispat için olmayana ergi (proof by contradiction) kullanılabilir. Önecelikle problemimizi modelleyelim: D(P,G) : P, programının […]
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 ve birbirini izlemesi gereken önermeler oldukları gösterilir. Basit bir örnek ile durumu inceleyelim. Mesela n […]
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. Örneğin: n sayısı tek sayı ise n2‘nin de tek sayı olduğunu ispatlayalım. Öncelikle biliyoruz ki […]
Taban Sıralaması (Radix Sort)
Taban Sıralaması (Radix Sort) Yazan : Şadi Evren ŞEKER Hane sıralaması, radiks sıralaması veya kök sıralaması isimleri de verilebilen sıralama algoritmasına göre sıralanacak olan değerler hanelerine (digits) göre sıralanır. En değersiz haneden (Least significant digit) en değerli haneye (most significant digit) doğru sıralama işlemi yapılır. Yani örneğin en fazla 4 haneli sayıların bulunduğu bir sayı […]
Doğrusal Arama (Linear Search)
Doğrusal Arama (Linear Search) Yazan : Şadi Evren ŞEKER Sequential Search (Sıralı arama) ismi de verilen bu arama tam anlamıya bir veriyi, arananlara teker teker bakarak aramaktır. Yani aşağıdaki sayılar arasında 15 sayısını aramak için: 4 6 12 8 5 15 25 34 Teker teker bütün sayılara bakılır. Örneğin baştan başlanarak 4 aranan sayı mı? […]
Yerleştirme Algoritmaları (Fitting Algorithms)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde kısıtlı bir alanın verimli kullanılması için geliştirilmiş algoritmalardır. Örneğin sınırlı bir hafıza ( RAM ) içerisine en verimli şekilde programları yerleştirmek, işletim sistemleri için bir problemdir. Benzer problemlerle gerçek haytta da sıkça karşılaşılmaktadır. Örneğin bir deponun verimli kullanılması veya bir kamyonun verimli yüklenmesi veya haftalık bir ders programına […]
Sonda (Probe)
Yazan : Şadi Evren ŞEKER Veri iletişimi sırasında veriye erişmek için yapılan her bir erişim işlemine verilen isimdir. Örneğin veri diskte veya hafızada duruyor olsun, veriye erişmek için yapılan her bir hafıza veya disk erişimine sonda ismi verilir. Basit bir dizide veriyi aradığımızı düşünelim. Örneğin dizimiz: int a[] = { 2 ,3 ,8 ,7}; olarak […]
Brent Yöntemi (Brent’s Method)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde dosya yönetiminde özetleme (hashing) için kullanılan bir yöntemdir. Bu yönteme göre ekleme sırasında bazı değişiklikler ile yerleştirilen kayıtların arama hızını arttırmak ön plandadır. Özet tabloya (hash table) yerleştirilen bir kayıdın çeşitli durumlarda yeri değiştirilerek okuma zamanının arttırılması hedeflenir. İki ayrı zincir tutmaktadır. Birincil sonda zincirinde (primary probe chain) […]