Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerine matematikten miras kalan karmaşıklık teorisi (complexity theory) konularından birisidir. Aslında problem veya algoritmaların çözüme ulaşmadaki karmaşıklığını ölçmek için kullanılır. Bu tanımın ardında, her problem veya algoritmanın bir fonksiyon gibi düşünülebilmesi, ve matematikteki fonksiyonların karmaşıklığını sınıflandırmak için kullanılan karmaşıklık sınıflarının (complexity classes, asimptotik notasyonlar) , algoritmalar için uygulanması yatmaktadır. […]
Category: algoritma analizi (teory of algorithms)
Bellman Ford Algoritması
UAYRI!: Bu yazıda hatalar bulunmaktadır (Uğur Bey’e teşekkürler). Bu yazıda anlatılan algoritma verilen örnekteki özel olarak sıralanmış kenarlar için doğru çalışmakta ancak farklı durumlarda hata yapabilmektedir. Bellman-Ford algoritmasının tam ve doğru anlatımı için http://www.bilgisayarkavramlari.com/2010/08/05/bellman-ford-algoritmasi-2/ adresindeki yazıyı okuyabilirsiniz. Yazan : Şadi Evren ŞEKER Bu algoritmanın amacı, bir şekil (graph) üzerindeki, bir kaynaktan (source) bir hedefe(target veya […]
Edmonds Karp Algoritması
Edmonds Karp Algoritması Yazan : Şadi Evren ŞEKER Bu algoritmanın amacı, literatürde azami akış ( maximum flow ) olarak geçen ve düğümler (nodes) arasında akış kapasiteleri belirli bir şekildeki (graph) bir başlangıçtan bir hedefe en fazla akışın sağlandığı problemleri çözmektir. Azami akış (maximum flow) problemini örneğin şehirler arasında bağlı boru hattına veya tedarik zincirine benzetebiliriz. […]
Dijkstra Algoritması
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde kullanılan ve algoritmayı literatüre kazandıran kişinin ismini taşıyan dijkstra algoritması, verilen bir şekilde (graph) en kısa yolu (shortest path) bulmak için kullanılır. Bu algoritmanın çalışmasını örnek bir şekil( graph ) üzerinden göstermeye çalışalım. Bu gösterimin ardından Dijkstra algoritmasının başarısını ve zafiyetlerini tartışabiliriz. [flashvideo file=http://www.bilgisayarkavramlari.com/wp-content/uploads/dijkstra.flv /] Örnek olarak yukarıda […]
Cardinality (Sayısallık)
Yazan : Şadi Evren ŞEKER 1. Rasyonel / Tamsayı ilişkisi 2. Sayılabilirlik (Countability) 3. Reel / Tamsayı ilişkisi Şayet aynı isme sayıp ERD (Entity relationship diagram) üzerindeki sayısallık konusu ile ilgili yazıyı arıyorsanız bu bağlantıdan erişebilirsiniz. Algoritma analizi (algorithm analysis) ve hesaplama teorisinde (theory of computation) sıkça kullanılan anlamıyla bir kümenin eleman sayısını belirtir. Ayrıca […]
Kırmızı-Siyah Ağaçları (Red Black Trees)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde, veriyi ağaçta (tree) tutarken, ağacın dengeli (balanced) olmasını sağlayan bir algoritmadır. Algoritma, veriyi tutuş şekli sayesinde, arama, ekleme veya silme gibi temel işlemlerin en kötü durum analizi (worst case analysis) O(logn)’dir, yani algoritma n elman için bu işlemleri en kötü O(logn) zamanda yapmaktadır. Kırmızı-siyah ağaçlar (red-black trees) tanım […]
Serseri sıralaması (Stooge Sort)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde kullanılan ve tek boyutlu bir veri yapısı üzerinde (örneğin dizi (array) ) sıralama yapmaya yarayan bir algoritmadır. Algoritmanın çalışması birleştirme sıralaması (merge sort) veya hızlı sıralama (quick sort) algoritmalarına benzetilebilir. Bunun sebebi algoritmanın, sıralamak istenen sayıları 2/3 oranında iki parçaya bölmesi ve kalan sayıları kendi aralarında sıralamasıdır. Algoritmanın […]
İkili Arama Algoritması (Binary Search Algorithm)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde bir bilgi kaynağı veya veri yapısı üzerinde problemi her adımda iki parçaya bölerek yapılan arama algoritmasının ismidir. Bu anlamda bazı kaynaklarda bölerek arama olarak da geçmektedir. Arama algoritması, yapı olarak parçala fethet (divide and conquere) yaklaşımının bir uygulamasıdır. Bu yazı kapsamında diziler üzerinde ikili arama işleminin nasıl yapıldığı […]
Güvercin Yuvası Kaidesi (Pigeonhole Principle)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimleri de dahil olmak üzere pek çok matematik temelli bilim ve mühendislik alanında kullanılan oldukça basit bir umdedir. İsmini güvercin yuvalarından alan bu kaideye göre yuva sayısından fazla güvercin varsa, ve bütün güvercinler bir yuvaya girecekse, en az bir yuvaya birden fazla güvercin girmek zorundadır. Bu durumu sembollerle göstermemiz […]
Arılar Algoritması (Bees Algorithm)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde kullanılan arama algoritmalarından (search algorithms) birisinin ismidir. Bu algoritmada amaç belirli bir en iyi noktasını (optimum point) bulmaktır. Bu arama işlemi sırasında arıların bal yapmak için kullandıkları arama metodu modellenmiştir. Algoritmanın farklı çeşitleri bulunmasına karşılık en basit haliyle bir komşu arama algoritmasına benzetilebilir. Algoritmanın açıklaması Algoritmanın çalışması sırasında […]