Yazan : Şadi Evren ŞEKER Klasik bir optimizasyon problemidir. Basitçe belirli bir süreye, en verimli şekilde belirli kurallara uyarak olayları yerleştirmeyi hedefler. Örneğin öğrencilerin haftalık programının yapılması, doktor / hemşirelerin nöbet çizelgeleri, televizyon kanallarının yayın akışları gibi. Daha basit anlaşılacağı için öğrenci programlarını örnek vererek konuyu açıklamaya çalışayım. Bir öğrenci probleminde, sistemin uyması istenen kıstaslar(constraints) […]
Category: algoritma analizi (teory of algorithms)
Doğrusal Programlama Örnekleri
Yazan : Şadi Evren ŞEKER Bu yazının amacı, daha önceden anlatılan doğrusal programlama (linear programming) konusunu, gerçek hayatta yaşanabilecek problemler ve bu problemlerin nasıl doğrusal denklemlerle modellendiğini örneklerle anlatmaktır. Doğrusal programlama daha önce de bahsedildiği üzere birden fazla doğrusal denklem için en verimli, en iyi noktayı bulmayı hedefler. Öncelikle bir problemin nasıl doğrusal denklemlerle ifade […]
Permutasyon Algoritması
Yazan : Şadi Evren ŞEKER Bu yazıyı Fatih Bey’in sorusu üzerine siteye eklemeye karar verdim. Fatih Bey’in sorusunu alıntılıyorum: Hocam merhabalar bir soru sormak icin rahatsız etmiştim sizi,Bir fonksiyonumuz olsun ve parametre olarak zarSayisi alsin ve bu fonksiyon zar sayısına gore olası tum sonucları(zarların permutasyonunu ekrana bassın).ornegin zar sayısı 2 ise asagıdaki gibi sonuc elde […]
EQP (Exact Quantum Polynomial)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde, kuantum hesaplama konusunda kullanılan bir karmaşıklık sınıfıdır. Literatürde tam kuantum polinom zaman (exact qunatum polynomial time) olarak geçmektedir. Özellikle olasılıksal problemler için %100 başarı ile (yani bütün ihtimalleri eleyerek) sonuç üretme süresinin polinom zamanda olduğunu belirtir. Bilindiği üzere karmaşıklık problem sınıfları tanımlanırken, klasik problemlerin (burada klasik kelimesi, kuantum […]
Çakışma Problemi (Collision Problem)
Yazan: Şadi Evren ŞEKER Bilgisayar bilimlerinde, karmaşıklık teoremi (complexity theory) ve kuantum işleme (quantum computing) gibi konularda sıkça geçen bir problemdir. Problem basitçe, bir fonksiyonun 1’e 1 veya n’e 1 olup olmadığını sorgular. Örneğin f: {1 … n } à { 1 … n } bir fonksiyon olsun. Yani n sayıdan n sayıya tanımlı bir […]
Algoritma Analizi (Analysis of Algorithms)
Algoritma Analizi (Analysis of Algorithms) Yazan : Şadi Evren ŞEKER Bu yazının amacı, bilgisayar bilimlerinin temelini oluşturan, algoritma analizini açıklamaktır. Genelde lisans seviyesinde bir dönemlik ders olarak okutulmaktadır. Bu ders hakkında çok sayıda kitap da yazılmıştır. Dolayısıyla bu yazıda sadece konu hakkında bilgi verilecektir. Bilgisayar bilimlerinde temel olarak iki önemli kaynak bulunur: Yer ( Hafıza […]
Bellman Ford Algoritması
Yazan : Şadi Evren ŞEKER Bu algoritmanın amacı, bir şekil (graph) üzerindeki, bir kaynaktan (source) bir hedefe(target veya sink) giden en kısa yolu bulmaktır. Bu anlamda, literatürde en kısa yol bulma algoritması (shortest path algorithm) olarak sınıflandırılabilir. Algoritma ağırlıklı şekiller (weighted graph) üzerinde çalışır. Kabaca, bütün düğümler için bütün kenarları dolaşır. Dolayısıyla performansı düğüm sayı […]
NL (Non-deterministic Logarithmic)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde de sıkça kullanılan ve matematiğin bir parçası olan karmaşıklı teorisi (complexity theory) içerisinde tanımlı olan bir karmaşıklık sınıfıdır (kümesidir, set) Bu kümenin özelliği, bu kümenin üyesi olan, fonksiyon, denklem veya algoritmaların logaritmik zamanda veya logaritmik hafıza ihtiyacı ile çalışıp çalışamayacağının veya çözülüp çözülemeyeceğinin belirlenememesidir. Bu kümenin tanım itibariyle […]
Bool Tatmin Problemi
Bool Tatmin Problemi Yazan : Şadi Evren ŞEKER Litartürde, Boolean Satisfiability Problem olarak geçen ve boole cebirindeki denklemlerin doğruluğunun sağlanması olarak özetlenebilecek olan problemdir. Ayrıca çeşitli kaynaklarda bu probleme, problemin İngilizce tanımında geçen Satisfiability kelimesinin kısaltması olan SAT kelimesi olarak da rastlanabilir. Bu problemi, bilgisayar bilimleri açısından ilginç kılan yanı ise, problemin yapısal olarak bir […]
Ve/Veya bağlacı normal şeklleri (Conjunction / Disjunction Normal Form)
Yazan : Şadi Evren ŞEKER Bu gösterim, bool cebirinde (boolean algebra) kullanılan ve kaziyeleri (önerme, proposition) ve (and) bağlacı ile bağlamanın özel bir şeklidir. Kısaca CNF (conjuction normal form) olarak ifade edilir. Diğer bir normal şekil olan Chomsky Normal Form (CNF) ile ilgili bilgi arıyorsanız buradan ulaşabilirsiniz. Bu özel şeklin taşıdığı kuralları aşağıdaki şekilde sıralayabiliriz: […]