Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin bir çalışma alanı olan veri güvenliği konusunda kullanılan bir algoritmadır. Sıfır bilgi protokolü (zero knowledge protocol) ismi de verilir. Algoritmanın çözmeye çalıştığı problem aslında oldukça eski ve sık rastlanır bir problemdir. “Bir bilgiyi bildiğimi, karşı tarafa bu bilgiyi vermeden nasıl ispat edebilirim?” şeklindeki bir soruya cevap arar. Yani […]
Category: algoritma analizi (teory of algorithms)
Laplas Matrisi (Laplacian Matrix)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin de içinde bulunduğu pekçok bilim ve mühendislik alanında kullanılan graf teorisi (graph theory) açısından önemli bir matristir. Laplas matrisinin özelliği her düğümün derecesini (node order) ve diğer düğümlerle olan komşuluk ilişkisini (adjacency list) tutmasıdır. Laplas matrisine giriş matrisi (admittance matrix) veya Kirchhoff matirisi ( Kirchhoff matrix ) isimleri […]
Denkşekillilik (Isomorphism)
Yazan : Şadi Evren ŞEKER İki şeklin birbirinden farklı ancak denk olması durumudur. Bilgisayar bilimleri de dahil olmak üzere pek çok bilim ve mühendislik alanında kullanılan graf teorisine (graph theory) göre iki şekil birbirinden farklı çizilmiş ancak işlev ve değer olarak aynı olabilir. Tanım ve örnek Örneğin aşağıdaki iki şekli ele alalım: Yukarıda verilen graftaki […]
Öyler Yolu (Eulerian Path)
Yazan : Şadi Evren ŞEKER Bilgisayar mühendisliği de dahil olmak üzere pekçok bilim ve mühendislik alanında kullanılan graf teorisindeki özel bir yol (path) şeklidir. Bu yolun özelliği her kenardan (edge) bir kere (en az ve en çok) geçen yolu bulmaktır. İçerik Teorinin tarihi çıkışı Teorinin tanımı Öyler yollarının özellikleri Bir graftaki farklı öyler yollarının […]
Markof Modeli (Markov Model)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimleri de dahil olmak üzere pekçok bilim ve mühendislik alanında kullanılan markof modelleri aslında graf teorisinin (graph theory) bir uygulamasıdır. Basitçe düğümleri (nodes) durumlardan oluşan ve bu durumlar arasında istatistiksel geçişi modelleyen kenarları (edges) bulunan graflardır. Markof modellerine (markof zinciri (markov chain) ismi de kullanılmaktadır) göre bir durum belirli […]
Hamilton Yolu (Hamiltonian Path,hamiltonian circuit)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde veri modellemede kullanılan graf teorisinde (graph theory) kullanılan bir yol (path) biçimidir. Tanımı oldukça basittir. Buna göre bir yolun (path) Hamilton yolu olabilmesi için bir kere geçilen kenardan (edge) tekrar geçilmemesi gerekir ve ayrıca yolun bütün düğümleri (nodes) birer kere ziyaret etmesi gerekir. Bir hamilton yolu başladığı yerde […]
Augmented Transition Network (ATN, Uzatılmış Geçiş Ağı)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde özellikle de yapay zeka konusunda ve buna bağlı diğer alt dallarda (örneğin doğal dil işleme) kullanılan bir graf teori (graph theory) gösterimidir. Kelime anlamı olarak uzatılmış geçiş ağı (tehir-i intikal şebekesi) denilen ağların amacı toplanan bilgilere göre bir karar vermek ve karar verme işlemi sırasında da bir belirsizlik […]
Özyinelilerde Ana Teorem (Master Theorem)
Özyinelilerde Ana Teorem (Master Theorem) Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin en önemli konularından birisi olan algoritma analizinin vazgeçilmez teoremidir. Kısaca özyineli (recurrence) bir problemin çözümü için kullanılır. Üç farklı değerin bulunmasını sağlar. Bunlar sırasıyla O (büyük O, big-oh) : En kötü durum analizidir (worst case analysis) (büyük teta, Theta) : Ortalama durum analizi […]
Floyd-Warshall Algoritması
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin önemli konularından olan algoritma analizi sırasında sıkça bahsi geçen bir algoritmadır. Algoritmanın ana amacı belirli bir graf üzerinde bir başlangıçtan(source) bir bitiş düğümüne (sink, end, target) en kısa yoldan (shortest path) ulaşmaktır. Bu özelliğinden dolayı, maksimum akış (maximum flow) problemleri olarak bilinen, ve örneğin bir dağıtım şebekesinde bir […]
Boyer Moore Dizgi Arama Algoritması (Boyer-Moore String Search)
Yazan : Şadi Evren ŞEKER İçerik Algoritmanın çalışması Örnek çalışma Tek harfli atlama tabloları Gelişmiş atlama tabloları Algoritma performansı Bir metin veya hedef dizgi (string) içerisinde bir başka dizginin (string) aranması sırasında kullanılan algoritmalardan birisidir. KMP (Knuth Morris Prat) algoritması ile birlikte en çok kullanılan arama algoritmalarındandır. Bu algoritmadaki amaç bütün harfleri teker teker kontrol […]