Bu yazının amacı, istatistiksel normalleştirme (statistical normalization) konusunu açıklamaktır. Şayet ilgilendiğiniz konu, veri tabanlarında normalleştirme (database normalisation) ise lütfen aşağıdaki bağlantıya tıklayarak ilgili yazıya geçiniz.

http://www.bilgisayarkavramlari.com/2012/01/17/normallestirme-normalisation-normalizasyon/

İstatistiksel normalleştirme, özellikle, veri madenciliği (data mining) gibi bilgisayar bilimlerinin istatistiksel veri işleme alanlarında kullanılan bir yöntemdir. Yöntemin amacı, veriler arasında farklılığın çok fazla olduğu durumlarda verileri tek bir düzen içerisinde ele almaktır.

Diğer bir kullanılışı ise farklı ölçekleme sisteminde bulunan verilerin birbiri ile karşılaştırılabilmesidir. Buradaki amaç, matematiksel fonksiyonlar kullanarak, farklı sistemlerde bulunan verileri, ortak bir sisteme taşımak ve karşılaştırılabilir hale getirmektir.

Bu anlamda kullanılan normalleştirme fonksiyonları (normalization functions) aşağıda açıklanmıştır.

1.    Asgari – Azami Normalleştirmesi (Min-Max Normalisation)

Bu yöntemde, bir grup verinin içerisindeki en büyük ve en küçük değerler ele alınır. Diğer bütün veriler, bu değerlere göre normalleştirilir. Buradaki amaç en küçük değeri 0 ve en büyük değeri 1 olacak şekilde normalleştirmek ve diğer bütün verileri bu 0-1 aralığına yaymaktır.

Yukarıda verilen formüle göre her değerin normalleştirilmiş değeri hesaplanır. Bu hesaplamanın çalışmasını bir örnek sayı dizisi üzerinde gösterelim. Örneğin sayı dizimi aşağıdaki şekilde verilmiş olsun:

5, 8,9,11,20, 22,24,25,27,29

Yukarıdaki sayıların normalleştirilmiş halleri aşağıda verilmiştir:

Yukarıda görüldüğü üzere en küçük sayı 0 ve en büyük sayı 1 olarak normalleştirilmiştir. Bu sayılar dışındaki sayılar ise yer aldıkları aralığa göre değerler atanır. Örneğin sayı dizimi aşağıdaki şekilde olsaydı:

10,15,16,17,50,51,55,56,60

Bu durumda normalleştirilmiş değerler aşağıdaki şekilde olacaktı:

Görüldüğü üzere bu yeni normalleştirme sonucunda da sayılarımız 0 ile 1 arasında değerler aldılar. Şimdi bu iki farklı sayı grubunu karşılaştırabiliriz. Örneğin ilk sayı dizimizde bulunan 25, normalleştirme sonucunda 0,83 değerini almıştır. İkinci sayı grubumuzda bulunan 51 ise, normalleştirilmiş değer olarak 0,82 değerini almıştır. Bu duruma ilk sayı dizisinde bulunan 25’in sayılar arasındaki konumu, ikinci dizide bulunan 51 ile yakındır denilebilir (en azından ikinci dizide bulunan 17 sayısına göre daha yakındır çünkü ikinci dizideki 17 sayısı 0,14 gibi çok daha farklı bir değerdir).

Örnekte de görüldüğü üzere iki farklı dizide bulunan sayılar, birbiri ile karşılaştırılmak istendiğinde, ortak bir sayı sistemine çevrilerek içinde bulundukları diğer sayılara göre, göreceli olarak bir değer atanmış ve karşılaştırılmıştır. İşte normalleştirme tam olarak budur

   2. Standart Skor (Standard Score):

Diğer bir normalleştirme yöntemidir. Bir önceki yöntemde, sayılar en yüksek ve en düşük değerlere göre normalleştirilmişti. Bu yöntemde ise ortalama değer (mean value) ve standart sapma (standard deviation) değerleri göz önüne alınır.  Sistemde kullanılan standart sapmaya atfen, standart skor (standard score) olarak da isimlendirilir. Oldukça popüler normalleştirme yöntemlerinden birisidir. Formülü aşağıdaki şekilde yazılabilir:

Yukarıdaki denklemden de anlaşılacağı zere, bir değerin normalleştirilmesi sırasında, ortalama değere (μ) olan uzaklığı alınarak standart sapma değerine (σ) bölünür. Konunun anlaşılması için, bir önceki örnekte kullandığımız sayı dizisini yeniden işlemeye çalışalım:

Yukarıdaki değerleri inceleyecek olursak, 5 ve 29 sayılarının normalleştirme sonucunun mutlak değeri aynı çıkmıştır. Bunun sebebi, iki sayının ortalama değer olan 17’ye olan uzaklıklarının eşit olmasıdır ( 5-17 = -12 ve 29-17 = 12) sadece yönleri farklıdır ve bu durum normalleştirme sonucunda görülmüştür.

Gelelim ikinci dizimizin normalleştirme sonucuna:

Bir önceki normalleştirme sonucunda en büyük ve en küçük sayıların sadece yönü farklıyken bu sefer değerlerde farklılık oldu. Bunun sebebi iki sayının ortalama değere olan uzaklığının farklılaşmasıdır. Bu ikinci dizideki ortalama değer 36.667 olduğu için iki değer farklı olarak normalleştirilmiştir.

Bir önceki normalleştirme olan asgari / azami normalleştirmede bu fark görülememekteydi. Diğer bir deyişle asgari / azami normalleştirme, en büyük sayıyı hep 1 ve en küçük sayıyı hep 0 olarak kabul edip, diğer sayıları bu 0-1 aralığına yerleştirmekteydi, z-skor normalleştirmesinde ise sayılar ortalama değere göre uzaklıklarına göre normalleştirilmektedir. Ayrıca standart sapmaya bölünerek, sayılar arasındaki hareketlilik (değişim hızı) ortalamaya olan uzaklığı normalize etmektedir.

19 views

Bu yazının amacı, eş zamanlı işlemlerin (concurrent processes) yönetimini anlatmak için geliştirilmiş bir örnek olan yemek yiyen filozoflar konusunu açıklamaktır. Eş zamanlı işlemler, işletim sistemleri (operating systems), ağ programlama (network programming) gibi pek çok bilgisayar bilimi konusunda geçmektedir.

Yemek yiyen filozoflar örneği, literatüre Dijkstra tarafından kazandırılmıştır ve eş zamanlı işlem yönetimini (concurrent process management) sembolize eder.

Öncelikle örneği anlatarak konuya başlayalım. Örneğe göre, ikiden fazla ( örnek için n kadar kabul edilebilir) filozof, bir yuvarlak masanın etrafına dizilerek yemek yerler. Literatürde örnek iki şekilde anlatılmaktadır ve orijinalinde filozoflar pirinç pilavı yemektedir. Buna göre pirinç yemek için iki adet yemek sopası (chopstick) gerekmektedir. Çinlilerin yemek yerken kullandıkları sopaları düşünebilirsiniz. Tek sopa ile yemek yenmesi imkansızdır ve her filozofun en az iki sopaya ihtiyacı vardır. Olayın daha iyi anlaşılması için aşağıdaki şekilde bu durum tasvir edilmiştir:

Şekilde de görüldüğü üzere, başlangıç durumunda, her filozofun iki yanında birer sopa durmaktadır.

Örneğin biraz daha batı dünyasına uyarlanmış halinde ( buna göre batıda çatal kullanılmaktadır), her filozof makarna yemek ister ancak makarna yemek için en az iki çatala ihtiyaç vardır. Filozofların iki yanında birer çatal olduğuna göre problem bir önceki pirinç ve Çinlilerin yemek sopası probleminden bir farkı kalmaz.

Problemde, yukarıda anlatılanlara ilave olarak, filozofların belirli bir süre düşünme süreci bulunur.

Problemin buna göre filozofların hepsi örneğin sağındaki sopayı alırsa, hepsinde birer sopa olacak ve yemek yiyemeyeceklerdir. Şayet hepsi iki yanındakini birden almaya kalkarsa, bu durumda, eş zamanlı işlemlerde karşılaşılan yarış durumu (racing condition) ortaya çıkacaktır ve hangisi önce davranırsa (ki bu konuda bir garantimiz bulunmamaktadır) o yemeğini yiyebilecektir. Ve belki de hepsi birer sopa alacağı için yine hiçbirisi yemek yiyemeyecektir. Şayet hepsi birden sopalarını bir diğeri yesin diye bırakırsa, bu durumda yine hiçbirisi yiyemeyecektir. Bu tip problemler, genelde kıtlık problemi (starvation) olarak düşünülebilir. Buna göre her filozofun yemek yeme ihtimali bulunmaktadır ancak hiçbir şekilde yiyeceği garanti edilmemektedir. Örneğin filozoflardan birisi her durumda aç kalabilir ve asla sıra kendisine gelmeyebilir.

Problemde karşılaşılan diğer bir sorun ise ölümcül kilitlenmedir (deadlock). Yanlış bir tasarım sonucunda, tek çatal alan ve çatalı bırakmak için diğer filozofun bırakmasını bekleyen bir filozof sistemi kilitleyebilir. Bu da problemde bulunan ikinci risktir.

Son olarak problemin tanımında, filozoflar birbiri ile konuşamaz kuralı getirilmiştir. Bu kural önemli bir kural olmakla birlikte, aşağıdaki çözümlerin çoğunda bu kuralın ihlal edildiği görülebilir. Aslında filozoflar birbiriyle çatallar üzerinden iletişim kurmaktadır. Örneğin sağındaki veya solundaki filozofun o anda çatalı alıp almaması, yanındaki filozoflar hakkında bilgi vermekte ve bu da üstü kapalı bir iletişim olarak kabul edilmektedir. Aşağıdaki çözümlerin tamamında iletişim sadece çatalların durumuna göre sağlanmaktayken, sadece son çözüm olan chandy misra çözümünde, filozoflar doğrudan birbiri ile iletişime geçebilmektedir.

Problemin çözümü için farklı algoritmalar geliştirilmiştir. Bu algoritmalar aşağıda başlıklar altında anlatılacaktır.

1. Rastgele süre çözümü (Random Solution)

Bu çözümde, filozofların problemi çözmek için tamamen rastgele davranması öngörülür. Filozoflar, bir çatal aldıktan sonra ikincisini alabilirse yemeğini yer. Şayet ikinci çatalı alamazsa rastgele bir süre bekler ve bu süre içinde ikinci çatalın boşalmasını bekler. Şayet bu süre içerisinde diğer çatal, yanındaki filozof tarafından bırakılırsa, çatalı alır ve yemeğini yer. Şayet beklediği bu rastgele süre boyunca ikinci çatal bırakılmazsa bu durumda yemeğini yiyemeden elinde tuttuğu çatalı diğer filozofun yemesi için masaya geri bırakır.

Bu çözümde dikkat edileceği üzere, işlem tamamen rastgelelik üzerine kuruludur. Buna göre sistem tam başarı ile çalışmayabilir. Hatta sistemin çalışacağının hiçbir şekilde garantisi yoktur.

Çözüm yönteminin en önemli özelliği, çözümün gerçeklemesinin (kodlamasının) diğer bütün sistemlere göre çok daha kolay olmasıdır.

2. Garson çözümü (Conductor Solution)

Problemin bir seviye daha karmaşık ancak yine de basit bir çözümü, masanın etrafında bir garsonun (literatürde conductor ismi verilmiştir ve bu yüzden conductor solution olarak geçer) dolaşmasıdır.

Garson, sürekli olarak masada boş duran ve filozoflar tarafından yemek için kullanılan çatalların sayılarını takip etmektedir. Bir şekilde her filozof, masadan çatal alabilmek için garsonun iznini istemek zorundadır. Şayet garson izin vermezse filozof masadan çatal alamaz. Bu çözümde filozofların kıtlık problemi (starvation) ile karşılaşmaları engellenir çünkü mantıklı bir garson tasarımı, bütün filozoflara yemek imkanı tanır. Aynı zamanda ölümcül kilitlenme (deadlock) ihtimali de çözülmüştür çünkü garson hiçbir filozofu sonsuza kadar bekletmez. Yani filozofların birbirini bekleyerek sonsuza kadar yaşlanması sorunu çözülmüştür.

Çözümün daha iyi anlaşılabilmesi için, garsonun, saat yönünde masada döndüğünü, düşünelim. O anda işaretlediği filozof yemek yiyor, sonraki yemiyor sonraki yiyor ve böylece kaç filozof farsa, sırayla bir yiyor bir yemiyor şeklinde düşünülebilir. Bu durumda her filozofun yemek yemek için yeterli çatalı (veya sopası) bulunuyor demektir. Sonra garson, sırasıyla bir yönde (örneğin saat yönünde) dönerek masayı dolaşmakta ve sıradaki filozofa yemek yedirmekte (ve dolayısıyla sıradaki filozoftan sonraki yememekte ve sonraki yemekte ve böylece bütün masadakiler bir yer bir yemez şeklinde işaretlenmektedir).

3. Monitör Çözümü (Monitor Solution)

Bu çözüm, bir önceki garson çözümüne çok benzemektedir. Amaç sırasıyla her filozofun bir yiyen bir de yemeyen şeklinde sıralanmasıdır. Burada her filozof belirli bir sırayla sıralanmaktadır (örneğin saat yönünde veya saat yönünün tersi istikamette) ardından kendinden önceki filozofun durumunu kontrol ederek yemek yiyorsa yemez, kendinden önceki filozof yemek yemiyorsa bu durumda kendisi yemek yer.

Tek sayıda filozof olması durumunda yemek yeme eyleminin masada bir dalga şeklinde bir noktadan başlayarak sürekli döndüğü görülebilir. Şayet filozof sayısı çift ise bu durumda sürekli aynı filozoflar yemek yerken diğer filozoflar ölecektir. Bir çözüm olarak, şayet toplam filozof sayısı çift ise, sırasıyla tek ve çift filozoflara yemek yedirmek bir çözüm olabilir. Örneğin önce 1,3,5 numaralı filozoflar yemek yerken, sonra 2,4,6 numaralı filozoflar yemek yiyebilir.

4. Chandy Misra Çözümü (Chandy Misra Solution)

Bu çözüm, geliştiren iki kişinin ismi ile anılmaktadır (K. Mani Chandy ve J. Misra). Çözümün en önemli özelliği, merkezi bir karar mekanizmasını ortadan kaldırması ancak buna karşılık, filozoflar birbiri ile konuşamaz kuralını çiğnemesidir.

Çözüm aşağıdaki 4 adımdan oluşmaktadır denilebilir:

1. Her filozof ikilisi için bir çatal üretilir ve bu çatal en düşük sayı sahibi olan filozofa verilir. Her çatal kirli veya temiz olarak işaretlenebilir ve başlangıç durumunda bütün çatallar kirlidir.
2. Bir filozof, bir kaynak kümesini kullanmak istediğinde (yani yemek yemek istediğinde), komşusu olan çatalları kullanmak zorundadır. Elinde olmayan (ihtiyacı olan) bütün çatallara bir talep yollar.
3. Bir filozof, elindeki bir çatal için talep aldığında, şayet elindeki çatal temizse kullanmaya devam eder, şayet çatal kirli ise, çatalı masaya koyar. Ayrıca masaya konan çatal temiz olarak işaretlenerek konulur.
4. Bir filozof yemek yedikten sonra çatalı kirli olarak işaretler. Şayet bir filozof, daha önce bir çatalı talep ettiyse, çatalı temzileyerek masaya koyar.

Yukarıdaki algoritma adımlarını şu şekilde anlamak mümkündür. Öncelikle bütün çatallara bir işaret getiriliyor. Buna göre bir çatal, kirli veya temiz olabiliyor. Çatalın talep edilmesi ve edilmemesi arasındaki fark, bu işaret ile belirleniyor. Üzerinde talep olmayan çatallar temiz olarak tutulurken, üzerinde bir filozofun talebi bulunması halinde kirli oluyor. Bu durumda ikinci bir filozofun talepte bulunması engelleniyor. Her çatal sadece talep eden filozof tarafından kullanılacağı için de kullanma işlemi öncesinde tek bir filozofa atama yapılmış oluyor. Ayrıca filozofların talep işleminin gerçekleşebilmesi için çatal kümesinin (iki çatalın birden) atamasının yapılması gerekmektedir. Şayet tek bir çatal ataması yapılırsa bu durumda çatal filozofa ayrılmadan diğer filozofun kullanımı için serbest olmuş oluyor.

Burada akla, acaba bu çatal ayırımı sırasında, problemin orjinalinde bulunan kilitlenme ihtimali bulunmaz mı? Şeklinde bir soru gelebilir. Bu soru aslında mantıklı bir soru olmakla birlikte, kilitlenme probleminin önüne geçmek için, algoritma tasarımında bulunan en küçük numaraya sahip filozof koşulu getirilmiştir. Yani filozofların hepsi aynı önceliğe sahip olduğu durumlarda bir kilitlenme ihtimali bulunmakla birlikte, bu ihtimali bertaraf etmek için her filozofa bir numara verilmiş ve bu numaraya göre en düşük değere sahip filozof öncelikli olmuştur. Peki sürekli bu filozof yemek yiyerek diğerlerini bir kıtlığa sokabilir mi? Bu durumda kirli ve temiz çatal ataması ile engellenmiştir.

74 views

Bu yazının amacı, bir mantıksal devre elemanı olan kolayıcının (encoder) çalışma mantığını ve tasarımını açıklamaktır.

Basit bir kodlayıcı, kod çözücünün (decoder) tersine üssel işlemi geri alır. Örneğin bir kod çözücüde, yapılan işlem 2ⁿ şeklinde gelen girdinin (input) üstünü almaktır. 3×8 bir kod çözücüde, gelen 3 bitlik girdinin (input) değeri n olarak kabul edilirse, kod çözücü bu değere göre 8 farklı çıktıdan (output) bir tanesini seçer.

Kodlayıcı ise bu işlemin tam tersi yönde 8 farklı girdiden birisinden sinyal gelmesi halinde 3 çıktıdan (output) ilgili ihtimalleri işaretleyerek üst alma işleminin tersini (logaritma) yapar.

Örneğin aşağıda bir 4×2 kodlayıcının (encoder) doğruluk tablosu (truth table) verilmiştir:

Tabloda I ile ifade edilen kolonlar girdi (input) ve O ile ilfade edilen kolonlar ise çıktı (output) değerlerdir. Örneğin 0100 değerinin 10′luk tabanda karşılığı 4 olarak yazılabilir. Bu değerin tablodaki çıktı değeri (output) 10 olarak okunacaktır. 10 değeri ise 10′luk tabanda 2 olarak yazılabilir. Gerçekten de log₂4 = 2 olmaktadır ve kodlayıcının bir logaritma işlemi olduğu görülebilir.

Yukarıdaki tabloyu gerçekleyen kodlayıcının genelde kullanlıan blok çizimi aşağıdaki şekildedir:

Ayrıca doğruluk tablosunda görülebileceği üzere, V biti (valid bit, kabul edilebilir) kullanılarak tanımsız durumlar ortadan kaldırılabilir. Örneğin logaritmanın tanımından bilindiği üzere 0′ın logaritması tanımsızdır. Bu durumda bütün girdi (input) bitlerinin 0 olması durumunda çıktı belirsiz olacaktır. İşte bu belirsizlik durumunda çıktının kabul edilemez (invalid) olduğunu ifade için V biti 0 değerinde verilebilir.

Şayet bir kod çözücü (decoder) ile bir kodlayıcı (encoder) arka arkaya bağlanırsa, sistemin girdi değeri, çıktı değeri olarak okunur.

Yukarıdaki devrede, soldan verilen girdi sağdan değişmeden okunurken devre tam tersine çevrilerek, sağdan bir girdi verilmesi halinde de soldan okunacaktır.

Kodlayıcı devresini, kapılar kullanarak yapmak da mümkündür. Örnek bir tasarım aşağıda verilmiştir:

Doğruluk tablosunun karnaugh haritasını (karnaugh map) çizersek:

O₀ için

Yukarıdaki haritada, sonucu etkilemeyen (kodlayıcının çalışması belirsiz ve hiçbir şekilde girdi olarak gelemeyecek değerler) X ile ifade edilmiştir. Bu tip kodlayıcılara (encoder) özel olarak öncelik kodlayıcısı (priority encoder) ismi de verilmektedir. Bu haritada X değerleri 1 veya 0 olarak kabul edilebilir. O halde yukarıdaki tabloda mavi ile işaretlenmiş olan 4 ihtimal tek başına alınarak O₀ için I₀‘I₂‘ sonucuna varılabilir.

O₁ için

Yukarıdaki tabloda da benzer şekilde O₁ için I₁‘I₀‘ sonucuna varılabilir.

Yukarıdaki sonuçlara göre bir kodlayıcıyı (encoder) aşağıdaki şekilde çizebiliriz:

51 views

Bu yazının amacı, site üzerinde daha önceden anlatılmış olan birinci normal form (1NF),
ikinci normal form (2NF) ve üçüncü normal form (3NF) konularını kapsayan bir örnek çözmektir.

Genel olarak çok sayıda sınav sorusunda normalleştirme için hayali bazı tablolar sunulur ve bu tabloların normalleştirilmesi (normalizasyonu) istenir.

Örnek olarak aşağıdaki tabloyu ele alalım.

Yukarıdaki tabloda görüldüğü üzere 4 adet kolon ve her kolonda çeşitli sayılar ile gösterilmiş değerler bulunmaktadır. Bu tablonun üzerinde normalleştirme yapmaya başlamadan önce bazı konuları açıklayalım.

Örneğin yukarıdaki tabloda bir aday anahtar (candidate key) bulmamız istense ne yaparız?

Bir aday anahtar bulma işlemi için en kolay yol, tablonun birincil anahtarını (primary key) bulmaktan geçer. O halde sorumuzu öncelikle tablonun birincil anahtarını (primary key) bulmak üzere değiştirelim:

Yukarıdaki tabloda, satır bazlı olarak tekrar etmeyen bir kolon var mıdır?

Cevap : D kolonudur. Dikkat edilirse D kolonu, her satırda farklı bir değer almıştır. Demek ki tek bir kolonun birincil anahtar (primary key) olmasını istersek, D kolonunu seçmemiz yerinde olur.

Peki birden fazla kolon alınması durumunda hangi kolonları seçebiliriz?

Cevap: D kolonunun zaten her satırda tekrarsız olduğunu (unique) biliyoruz. Dolayısıyla D kolonu ile birlikte hangi kolon alınırsa alınsın bu kolonlar da tekrarsız (unique) olacaktır.

Ancak acaba D kolonunu almadan bir asil anahtar ( primary key) bulunabilir mi?

Cevap: Evet vardır. Örneğin (A,B) ikilisi de tablodaki her satırda tek başına tekrarsız (unique) olma özelliğindedir. Bir önceki cevabımızdan çıkardığımız üzere, (A,B) ikilisi ile birlikte alınacak diğer bir kolon da (örneğin C ) bu durumda birincil anahtar (primary key) olma özelliğini taşıyacaktır.

Yukarıdaki cevapların doğru olmasına karşılık, birincil anahtar (primary key) seçimi yapılırken en az sayıda kolonu içeren alternatifin seçilmesi yerinde olur. Bu anlamda, yukarıdaki anahtar ihtimallerinin hepsi birer aday anahtar (candidate key) olarak değerlendirilebilir ancak birincil anahtar olarak D kolonun tek başına seçilmesi yerinde olur.

Gelelim bir diğer soruya:

Yukarıdaki tabloya, aşağıdaki şekilde ilave bir kolon eklediğimizi düşünelim:

Yeni tablomuzda bulunan fonksiyonel bağlılıkları (functional dependency) çıkarmaya çalışalım:

Öncelikle, biliyoruz ki D kolonu birincil anahtardır (primary key) dolayısıyla zaten D kolonu bütün kolonların fonksiyonel olarak bağımlı olduğu bir kolondur ve aşağıdaki satırların tamamı doğrudur:

D à A , D àB , Dà C , Dà E

Ayrıca bir dipnot olarak, her kolonun kendisine fonksiyonel bağlı olduğunu söyleyebiliriz (self functional dependency), dolayısıyla DàD ifadesi de doğrudur ancak bu ifade, genelde veritabanı normalleştirmesinde bir anlam ifade etmediğinden göz ardı edilir.

Gelelim diğer fonksiyonel bağımlılıklara. Tabloda ikili üçlü ve dörtlü fonksiyonel bağlılıklar bulunabilir. Örneğin yukarıdaki sorularda (A,B) çiftinin de bir aday anahtar olduğundan bahsetmiştik. Bu durumda (A,B) à C, (A,B) à D , (A,B) à E ifadeleri de doğru olacaktır. Hatta D ile birlikte herhangi bir kolonun alınması da doğrudur. Örneğin (C,D) à A, (C,D) à B , (C,D) à E ifadeleri de doğrudur. Benzer şekilde D bir aday anahtar, birden fazla kolon birleşimini de fonksiyonel olarak ifade eder. Örneğin D à (A,B,C) veya Dà (B,C,E) veya (A,B) à (C,D,E) ifadelerinin tamamı da doğru kabul edilebilir.

Ancak acaba tek kolon seviyesinde başka fonksiyonel bağımlılık bulunabilir mi? Bu sorunun cevabı aslında bir kolon değişirken diğer bir kolonun değerlerinin bu değişimi yansıtıp yansıtmadığıdır.

Örneğin yukarıdaki tabloda, B ve E kolonları birlikte değişmektedir. Diğer bir deyişle B(1) à E(X) ve B(2)à E(Y) bağlantısı bulunmaktadır. Yani B tablosundaki 1 ile E tablosundaki X ve B tablosundaki 2 ile E tablosundaki Y arasında bir birliktelik söz konusudur.

Bu anlamda, BàE ve EàB ifadeleri doğrudur. Ancak konunun daha iyi anlaşılması için tabloda ufak bir oynama yapalım:

Yukarıdaki yeni tabloda, B kolonunun son satırı 3 olarak değiştirilmiştir. Bu durumda acaba BàE ve EàB ifadelerinden bahsedilebilir mi?

Tablonun yeni halinde E’deki her değişim, B’de bir değişimle karşılandığı için BàE ibaresi doğrudur ancak ne yazık ki EàB ibaresi kullanılamaz çünkü E, B’deki değişimleri göstermek için yetersizdir.

Ayrıca yukarıdaki tabloda, C kolonu, bütün diğer kolonlara fonksiyonel olarak bağımlıdır. Bunun sebebi C kolonunun sabit olması ve dolayısıyla bütün kolonlar tarafından doğası gereği fonksiyonel bağımlılığının ifade edilmesinin mümkün olmasıdır.

Gelelim tablomuzu normalleştirmeye. Tablomuzda bulunan fonksiyonel bağımlılıkları normalleştirme aşamasında kullanacağız. Normalleştirme işleminin amacını kısaca tabloda tekrar eden veri bırakmamak (veya en aza indirmek) olduğunu söyleyebiliriz.

Yukarıdaki son halini almış tablomuzda, BàE bağımlılığının bulunması bize aşağıdaki durumu oluşturma imkanı sağlar:

Görüldüğü üzere, B kolonu ve E kolonu ayrı bir tabloda tutularak, E kolonunun B kolonuna fonksiyonel bağımlılığından yararlanılmıştır. Bu durumda E kolonunun orjinal tabloda yer almasına gerek yoktur. A,B,C veya D kolonları ile birlikte karşılığı olan E kolonunu bir kişinin sorgulamak istemesi halinde, iki tablo arasında bir birleştirme (join) işlemi uygulanacak ve istenen veriye kolaylıkla ulaşılabilecektir. Bu durumda K tablosundaki B kolonu bir yabancı anahtar (foreign key) olmuş ve M tablosundaki B kolonu ise birincil anahtar (primary key) olmuştur denilebilir.

Gelelim C kolonuna. Bu kolon da herhangi bir kolona fonksiyonel bağımlı kabul edilebilir demiştik. O halde aşağıdaki şekilde bölünebilir:

Yukarıdaki gösterim doğru olmasına karşılık, aşağıdaki gösterim de doğrudur:

Veya diğer bir çözüm olarak aşağıdaki çözüm de doğrudur:

Yukarıdaki bütün çözümler doğrudur. Görüldüğü üzere, normalleştirme işleminde, tekrar eden satırlar elenmiş ve mümkün olduğunca tekrarsız satırların bırakılması amaçlanmıştır.

Burada bir soru, DàA özelliğini neden kullanmadık şeklinde sorulabilir. Yani D kolonu zaten A kolonunu veya B kolonunu belirlemektedir, o halde bu özelliği de kullanarak bir bölme işlemine daha gidilebilir mi?

Cevabı hem evet hem de hayırdır. Teorik olarak bahsedildiği gibi bir bölme olabilir. Ancak bu bölmenin hiçbir faydası olmaz. Aşağıda göstermeye çalışalım:

Bir önceki şekilde bulunan tablo K’yı tablo K ve tablo Q olarak bölmeye çalıştım. Görüldüğü üzere herhangi bir satır sayısında azalma olmamıştır. Bu tip birincil anahtar kullanarak bölme işlemleri mümkün olmakla birlikte genelde normalleştirme anlamında bir fayda sağlamaz. Bu şekilde böldükten sonra, iki tablo arasında (örneğimizdeki tablo K ve Q ) sayısallık açısından (cardinality) birebir (one-to-one) ilişki kurulmaktadır ki teorik olarak iki tablo arasında birebir ilişki varsa aslında bu iki tablo, bir tablonun ikiye bölünmüş halidir denilebilir. Genelde birebir ilişki, veritabanında hız amacıyla kullanlan (bazı kolonlara istatistiksel olarak çok nadir erişim yapıldığı biliniyorsa) veya veritabanı kısıtlarından dolayı kullanılan (örneğin veri tabanımızın tablo başına sadece 10 kolon tutmaya izin verdiği durumda 15 kolonlu bir tablo oluşturmak için) bir özelliktir.

80 views

Algoritmanın gayesi, bir metin içerisinde verilen bir dizginin (string) aranmasıdır. Literatürde arama yapılan metin için T (ingilizcedeki Text (metin) kelimesinden gelmektedir) ve aranan kelime için P (ingilizcedeki Pattern (örüntü) kelimesinden gelmektedir) kullanılmaktadır.

Klasik bir arama, yukarıdaki temsili resimde gösterilmiştir.

Algoritmanın diğer metin arama algoritmalarından en büyük farkı, aranan dizgi (pattern) yerine aranılan metin (text) üzerinden işlem yapmasıdır.

Yukarıdaki şekilde gösterildiği gibi, üzerinde arama işleminin yapıldığı metinde bulunan herhangi bir x harfi için, aranılan metin üzerindeki (pattern) en solda olan harf bulunmaya çalışılır.

arama işlemine başlanan α değerinin ardından gelen harfler eşleştiği sürece, aranan kelimenin (pattern) sonuna kadar eşleştikçe arama işlemi devam eder. Şayet bu aşama uyuşmayan bir harf olursa, zaten aranan kelimenin olmadığı sonucuna varılabilir.

Ardından uyuşma olup olmadığına bakılmaksızın aranan kelimeyi ß değerine denk gelecek şekilde kaydırma işlemi yapılır. Bu kaydırmanın olması için kelimenin (pattern) kalan kısmında ikinci bir değerinin bulunmaması gerekir.

Örnek

Algoritmanın çalışmasını bir örnek üzerinden göstermeye çalışalım.

Yukarıdaki şekilde görüldüğü üzere, aranan kelime için (P) sağdan sola doğru bir numaralandırma yapılmakta ve bu numaralandırma üzerinden aşağıda gösterilen HpBc dizisi çıkarılır. Bu dizi üzerinden metin üzerinde arama yapılır.

Sırasıyla önce, A harfi aranır. Ardından C ve G harfleri aranır. Dikkat edilirse, kelimede üç kere geçen A harfi, dizide bir kere kullanılmaktadır.

Uyuşma oldukça aranan kelime kaydırılmaktadır.

Müsvette Kod (Pseudo Code)

Algoritmanın müsvette kodu aşağıdaki şekilde yazılabilir:

Horspool (P = p₁p₂…p_m,T = t₁t₂…t_n)

Önişleme Aşaması

For c Î ∑ Do d[c] ← m

For j Î 1…m-1 Do d[p_j] ← m – j

Arama Aşaması

pos←0

While pos ≤ n-m Do

j ←m

While j > 0 And t_pos+j = p_j     Do j ← j-1

If j = 0 bulundu: pos+1

pos ← pos +d[t_pos+m]

End of while

Yukarıdaki algoritmada geçen değerlerin, örnek üzerindeki gösterimlerini adım adım anlatmaya çalışalım:

Yukarıdaki ilk adımda aranan ilk harf olan C harfi için öncelikle kümede olup olmadığı kontrolü yapılır. Bunun anlamı aranan kelimenin harflerinden birisi olmaması durumunda vakit kaybedilmemesidir.

İkinci adımda ise daha önce çıkardığımız HpBc[a] dizisine göre her harfin değerleri atanır.

Arama işleminin devamı aşağıdaki şekildedir:

GCATCGCAGAGAGTATACAGTACG

GCAGAGAG

     pos ← 0 + d[t₀₊₇] , pos ← 0 + d[A], pos ← 1

Yukarıda görüldüğü üzere, kelimenin ilk kontrolü için 1. pozisyonda bulunan A değeri aranmıştır. Ardından arama işlemi sonraki harf olan G için aşağıdaki şekilde devam eder:

GCATCGCAGAGAGTATACAGTACG

GCAGAGAG

pos ← 1 + d[t₁₊₇] , pos ← 1 + d[G], pos ← 3

G harfi ile C harfinin tutuşmamasından dolayı aranan kelime (P) kaydırılmıştır.

GCATCGCAGAGAGTATACAGTACG

GCAGAGAG

pos ← 3 + d[t₃₊₇] , pos ← 3 + d[G], pos ← 5

Benzer şekilde C ve G uyuşmamasından dolayı bir kere daha kaydırıyoruz.

GCATCGCAGAGAGTATACAGTACG

GCAGAGAG

While j > 0 And t_pos+j = p_j Do j ← j-1

If j = 0 pos+1′de bulundu

pos ← 5 + d[t₅₊₇] , pos ← 5 + d[G], pos ← 7

Görüldüğü üzere aranan kelime ile uyuşma oldu. Algoritmamızın ilgili satırlarını çalıştırıyor ve bulunduğunu rapor ediyoruz.

GCATCGCAGAGAGTATACAGTACG

GCAGAGAG

pos ← 7 + d[t₇₊₇] , pos ← 7 + d[A], pos ← 8

İkinci kere A harfini arıyoruz.

GCATCGCAGAGAGTATACAGTACG

GCAGAGAG

pos ← 8 + d[t₈₊₇] , pos ← 8 + d[T], pos ← 16

Bulunan A harfi G harfi ile uyuşmadığı için atlıyoruz:

GCATCGCAGAGAGTATACAGTACG

GCAGAGAG

pos ← 16 + d[t₁₆₊₇] , pos ← 16 + d[G], pos ← 18

pos > n-m // pos >23-7

while döngüsünden çık.

Son olarak kelimenin sonuna gelindiği halde aranan yazı bulunmadığı için algoritma sonlanıyor.

Algoritmanın Karmaşıklığı

Algoritmanın zaman karmaşıklığı aranan kelimenin boyu n ve aranılan kelimenin boyu m olmak üzere O(mn)’dir denilebilir. Çünkü en kötü durumda her aranılan kelime harfi için üzerinde arama yaptığımız her harfi karşılaştırmamız gerekebilir. Bu da her n harf için m adet karşılaştırmaya eşittir.

59 views

Bu yazının amacı, bilgisayar bilimlerinde, özellikle de mantıksal sistemlerin ispatında kullanılan ileri zincirleme ve geri zincirleme yöntemlerini açıklamaktır.

Yöntemin çalışması oldukça basittir. Öncelikle problem, mantık düzleminde modellenir. Buradaki mantık sistemi sonlu ispatı olan herhangi bir system olabilir. Örneğin birinci dereceden mantık (first order logic) veya daha özel olarak boole cebiri kullanılabilir.

Modelleme aşamasının ardından problemin çözümüne geçilir. İşte tam bu noktada ileri zincirleme (forward chaining) veya geri zincirleme (backward chaining) yöntemlerinden birisi seçilebilir.

Örneğin aşağıdaki mantıksal sistemi ve şekli ele alalım:

Sistemde görüldüğü üzere bazı mantıksal dizilimler verilmiş ve son iki satırda A ve B önermelerinin (kaziye) doğru olduğu belirtilmiştir.

Buna göre sağdaki çizim, hangi durumlarda, hangi diğer durumların doğru olacağını bu mantıksal sistemden çıkarır. Örneğin p=> q ifadesi, çizimin en tepesinde gösterilmiş ve p önermesinin (predicate, kaziyesinin) doğruluğu halinde q önermesinin de (kaziyesinin de) doğru olacağını ifade etmektedir.

Benzer şekilde, L önermesinin (kaziyesinin) doğruluğu A ve B önermelerine bağlı olduğu gibi, A ve P önermelerinin doğruluğuna da bağlanmıştır. Bu iki sistemden birisinin doğru olması sonucun doğruluğunu sağlar.

Şimdi şekilde gösterilen sistemi ileri zincirleme (forward chaining) yöntemi ile çözelim. Öncelikle sistemdeki bütün doğruluk şartlarını sayısal olarak ifade ediyoruz:

Şekilde görüldüğü üzere bütün doğruluk şartları birer sayı ile ifade edilmiştir. Söz gelimi, M önermesinin doğruluğu L ve B önermesi gibi 2 önermenin doğruluğunu gerektirir. Bu yüzden M birleşiminde 2 sayısı bulunur. Benzer şekilde Q önermesinde bulunan 1 sayısı, sadece P önermesinin doğruluğunun yeterli olduğunu ifade etmektedir.

Şimdi ileri zincirleme yöntemini kullanarak sistemin doğru olduğu verilen A ve B önermelerinden itibaren çözümünü izleyelim.

Öncelikle A ve B’ye komşu olan düğümlerdeki değerleri 1′er azaltıyoruz:

Yukarıdaki şekilde ileri zincirleme işlemi (forward chaingin) A önermesi için çalıştırılmış olup A’nın komşularını 1 azaltmıştır. Sırada B önermesi var ve onu da çalıştıralım:

Görüldüğü üzere B’nin komşuları da 1 azaldığında 0 değerine sahip bir düğüm elde ettik. Bu durumda L’nin doğru olduğunu söyleyebiliriz çünkü L’nin doğru olması için gereken 2 değer de sağlandı. Yani mantıksal sistemimizde bulunan

A Ù B Þ L

Satırını sağlamış olduk. Buradan doğruluğunu bulduğumuz L önermesinin komşularını 1 azaltıyoruz:

L’nin komşularının 1 azalması sonucunda M’nin değeri 0′a inmişi oluyor ve artık M için de doğru diyebiliyoruz. Şimdi M’nin komşularını 1 azaltalım:

Artık P için doğru sonucuna ulaştık ve P’nin iki komşusununda değerini 1 azaltarak sonucu buluyoruz:

Görüldüğü üzere zaten doğru olduğunu bildiğimiz L için tekrar doğru sonucunu bulduk ve ilave olarak Q için de doğru sonucunu bulduk.

Demek ki ilk sistem bize verildiğinde, Q’nun değeri sorulsaydı, doğru olduğunu söyleyebilirdik, ancak bunu bilgisayarın bulması için yukarıda adım adım anlatılan aşamaların tamamlanması gerekmektedir.

Geri Zincirleme (Backward Chaining)

Gelelim aynı amaç için kullanılan, yani bir mantıksal sistemi çözmek için kullanılan geri zincirleme yöntemine. İleri zincirleme yöntemine çok benzer olarak yine bir mantıksal sistem, bir şekil üzerinde gösterilebilr:

Sistemde diyelim ki Q’nun değerini merak ediyor olalım. Bilgisayar algoritması, bu defa Q’nun değerinin doğruluğunun P’nin değerinin doğruluğuna bağlı olduğunu çözerek işe başlayacaktır. Aslında geri zincirlemede kullanılan yaklaşım, tam olarak ileri zincirlemenin tersidir. İleri zincirlemede, doğruluğunu bildiğimiz önermelerden başlanırken, geri zincirlemede, doğruluğunu aradığımız önermelerden başlıyoruz. Burada doğruluğunu aradığımız önerme Q olduğuna göre, Q’dan başlayarak sistemi dolaşacağız. İlk adımda Q’nun doğruluğu, P’nin doğruluğuna bağlıdır, o halde Q yerine P doğru mudur diye sistemi çözmeye çalışırız:

P’nin doğruluğu, şekilde de görüldüğü üzere, L ve M’ye bağlıdır ve artık L ve M doğru mudur diye sorarız. Bunlardan birisinin yanlış olması halinde sonuç yanlış veya ikisinin de doğru olması halinde sonuç doğru olacaktır. Burada sonuç ile kastedilen P ve dolayısıyla Q’dur. Dikkat edilirse artık L ve M’ye bakarak Q’nun değerini tahmin edebiliyoruz. Devam edelim:

L’nin doğruluğuna bakıldığında P ve A bulunmakta, aslında bu sorunun cevabını P’nin değerini bilmediğimiz için veremeyiz. Ancak burada bir tehlike bizi bekliyor, şayet doğruluğunu araştırmak için DFS (depth first search, derin öncelikli arama) benzeri bir algoritma ile ağacı (veya şekli (graph) ) dolaşıyorsak, bu durumda bir sonsuz döngüye (fasit daire) girme ihtimalimiz bulunuyor. Bunu engellemek için diyelim ki derinliği sabitledik ve L’nin doğruluğu için A ve B ikilisine bakmaya karar verdik:

Sonuçta A ve B doğru ise L doğru demektir. O halde L doğru mu sorusunu sormayı bırakıyor ve M doğrumu A ve B doğru mu sorularını arayarak sistemi çözmeye devam ediyoruz. M’nin doğruluğu ise L ve B’ye dayanmakta, o halde bir kere daha L’nin doğruluğunu sorguluyor ve yukarıda anlatıldığı üzere bir kere daha A ve B’nin doğruluğunu sorguluyoruz. Neticede sorumuz basitçe A ve B doğru mudur şeklinde oluyor.

Verilen mantıksal sistemden de bildiğimiz üzere A ve B doğrudur, o halde Q da doğrudur diyebiliriz, çünkü sistemi buraya kadar adım adım çözdük ve neticede Q’nun doğruluğunu sorgulamanın A ve B’nin doğruluğunu sorgulamak olduğunu gördük.

Geri zincirleme (backward chaining) yaklaşımında istenirse buradan geriye dönülerek bütün sistemdeki önermelerin durumları doğru veya yanlış olarak işaretlenebilir. Ancak geri zincirleme algoritması, bu aşamada aranan Q önermesinin sonucunu bularak durabilir de. Bu iki yaklaşım arasındaki fark aslında CPS (call by passing style) ile birikimsel tarz (accumulation style) arasındaki fark gibidir.

İki yöntemde de sonuç doğru bir şekilde bulunur. Belki ufak bir fark olarak dikkat edilmesi gereken, geri zincirlemede, özel olarak aranan bir önermenin sonucuna konsantre olmamız, buna bağlı olarak da bazı büyük sistemlerde, sistemin sadece belirli bir kısmını çözüyor olmamız görülebilir. Buna mukabil, ileri zincirleme yaklaşımında, sistemin tamamı çözülmektedir.

38 views

Bu yazının amacı, PROLOG diline giriş yapmak ve basit bazı yapay zeka problemlerinin PROLOG dilinde nasıl kodlanarak çözüldüğünü göstermektir.

Kurulum ve çalıştırma:

Bu yazı kapsamında SWI-PROLOG programı kullanılacaktır. Programı, www.swi-prolog.com adresinden temin etmek mümkündür.

Yazı kapsamında MAC OSX üzerinde örnekler çalıştırılarak gösterilecektir ancak kurulum ve sonrasında başarılı bir çalıştırma yapılabiliyorsa hangi işletim sisteminde olduğunuzun bir önemi yoktur, bütün sistemlerde aynı PROLOG komutları çalışır.

Siteden indirilip kurulum yapıldıktan sonra,

$ /opt/local/bin/swipl 

Dizini altında bulunan swipl komutu çalıştırılarak, PROLOG komut satırı açılabilir.

Program çalıştırıldığında, aşağıdakine benzer bir komut satırı ile komut girilmesini bekleyecektir:

?- _

Yardım

İlk ve en önemli komutumuz olan yardım komutu ile başlayabiliriz.

?- help(help).

Bu komut, X11 ekranında, yardım dokümanını görüntüleyecektir. Basitçe herhangi bir komut hakkında bilgi alınmak istendiğinde bu komutu help fonksiyonuna parametre olarak vermek yeterlidir. Yukarıdaki kullanımda help komutunun kendisi için yardım alınmıştır.

Çıkış

Prolog komut satırından çıkmak için

?- halt.

Yazılması yeterlidir. Bu komut programı sonlandıracaktır.

Basit Kaziyeler

Aşağıdaki komutları PROLOG üzerinde çalıştıralım ve ardından burada yapılan işlemleri yorumlayalım.

Sistemimizde kayıtlı olan bir dosyayı program tarafından açıp çalıştırılır bir şekilde yüklemek için dosya ismi köşeli parantezler içerisinde verilmelidir:

?- [‘ilkdosya.pl'].

Yukarıda, bilgisayarımızda bulunan “ilkdosya.pl” isimli dosyayı sisteme tanıtarak yükledik. Bu dosyada bulunan tanımlar da otomatik olarak yüklenmiş ve sorgulanmaya / çalışmaya hazır hale getirilmiş olacaktır. Ayrıca bu dosyada bulunan genel hatalar, yükleme sırasında ekrana basılır.

PROLOG ile Faktöriyel Kodu

PROLOG dili, yapısal olarak özyineli (recursive) bir yapıdadır ve döngülerin yerine özyineli fonksiyon (recursive function) kullanılması gerekir. Bu kullanımı göreceğimiz en basit uygulamalardan birisi olan faktöriyel kodunu yazıp kodlamaya çalışalım.

Herhangi bir editör açılarak (ben tercihen vi kullanıyorum, siz de istediğiniz bir editör ile dosyayı açıp içeriğini ) aşağıdaki şekilde yazabilirsiniz:

factorial(0,1).      

factorial(A,B) :- 

             A > 0,

             C is A-1,

            factorial(C,D),

            B is A*D. 

Ardından aşağıdaki şekilde dosyamızı sisteme yükleyelim:

?- ['ilkdosya.pl'].

% ilkdosya.pl compiled 0.00 sec, 732 bytes

true.

Komut satırında dosyamızın yüklendiği ve yükleme süresi ve dosya boyutu gösterilmektedir. Son satırda yer alan true bilgisine kadar bir hata bulunmamış olması, dosyamızda bir hata olmadığını gösterir. Şimdi artık ilk fonksiyonumuzu kullanmaya başlayabiliriz.

?- factorial(5,X).

X = 120 ;

false.

Komut satırında, factorial(5,X) komutu verilerek, 5! Değerinin X değişkenine döndürülmesi istenmiştir. Burada öğrenilen birkaç önemli noktayı belirtelim. Birincisi X ile gösterilen değer bir değişkendir ve PROLOG dünyasında buna unbounded variable (bağlanmamış değişken) ismi verilir. Basitçe Prolog kodlarındaki bütün büyük harf ile başlayan ifadeler birer değişkendir ve ayrıca bir değişken tanımı yapılmaz. İkinci bir nokta, Prolog dilinde kod yazılırken girilen her satır bir emirdir ( declaration) ve yapısal olarak Prolog dili, haber mantığını (predicate calculus) barındırır. Buna göre yüklü olan dosyada bulunan komutlar yukarıdan aşağıya doğru çalıştırılırken üstte bulunan satır, alttakine gore öncelikli olur ve aynı zamanda birden fazla satırda emirin tanımlanması durumunda, sırasıyla bu emirler işlenir.

Örneğin yukarıdaki kodda, ilk satırda bulunan factorial (0,1). İfadesi, 0! = 1 anlamındadır ve bir şekilde birisi bize sıfır faktöriyeli sorarsa, ikinci değer olarak 1 sonucunu döndürmeyi gerektirir.

İkinci satırdan sonra başlayan tanımda ise, sırasıyla A>0 kontrolü yapılmış, ardından C değişkenine değer olarak A-1 değeri konmuş ve yeni bulunan C değerinin faktöriyeli hesaplanarak, B sonucuna hesaplanan bu C faktöriyel değeri ile A’nın çarpımı eklenmiştir.

Yukarıdaki şekilde kodumuzu ilkdosya.pl  dosyasına yazıp kaydettikten sonra prolog komut satırında dosyamızı yükleyip çalıştırabiliriz:

Yukarıda görüldüğü üzere faktöriyel kodumuz çalışmış ve sonucu doğru şekilde bulmuştur.

Kodun çalışmasını takip etmek için trace komutu kullanılabilir. Basitçe komut satırında:

trace.

Yazıldıktan sonra çalışmaya başlar ve bu çalışmadan sonra çağrılan fonksiyonların detayları ekrana basılır:

Görüldüğü üzere factorial fonksiyonumuzun her adımı ekrana basılmıştır.

Hanoi Kuleleri (Towers of Hanoi)

İkinci bir uygulama olarak çok klasik bilgisayar bilimleri problemlerinden olan Hanoi Kulelerini ( tower of hanoi ) kodlamaya çalışalım.

Oyunun kuralı gayet basit. Başlangıçta bir çubukta dizili olan bütün diskler her adımda tek bir disk hareket ettirerek diğer iki çubuktan birisine taşınacaktır. Bu taşıma işlemleri sırasında büyük bir disk, küçük olan bir diskin üzerine gelmeyecektir.

Ayrıca oyunun internetten oynan bir denemesi için daha önce hazırladığım aşağıdaki ödev sayfasına bakabilirsiniz:

http://www.sadievrenseker.com/c/odev5.html

Problemin çözümünde kullanacağımız kod aşağıdaki şekildedir:

SADIs-MacBook-Air:prolog sadievrenseker$ vi hanoi.pl

oyna(1,X,Y,_) :-

    write(X),

    write(‘ en üstteki diskini ‘),

    write(Y),

    write(‘ oynat ‘),

    nl.

oyna(N,X,Y,Z) :-

    N>1,

    M is N-1,

    oyna(M,X,Z,Y),

    oyna(1,X,Y,_),

    oyna(M,Z,Y,X).

Kod örneği yukarıda verilmiştir. Kodumuzun çalışmasını görüp ardından nasıl çalıştığını açıklamaya geçebiliriz.

?- oyna(4,a,b,c).

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

a en üstteki diskini c oynat

b en üstteki diskini a oynat

b en üstteki diskini c oynat

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

c en üstteki diskini a oynat

b en üstteki diskini a oynat

c en üstteki diskini b oynat

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

true .

?-

Yukarıdaki çalışmadan da görüldüğü üzere ilk baştaki 4 diskin dizili olduğu a çubuğundan bütün diskler sırasıyla b çubuğuna taşınmıştır.

Kodumuz, doğru sıra ile oynama yaklaşımı ile kodlanmıştır. Hanoi kulelerinin farklı çözümleri bulunur. Örneğin geri izleme algoritması (backtracking) kullanarak kaba kuvvetle (brute force) bütün ihtimallerin denendiği ve başarısızlık olması halinde en son iyi duruma geri dönen yaklaşımları kodlamak da mümkündür.

Bizim kodlamamızda ise her seferinde doğru çubuktan doğru diskin oynatılması esası kullanılmıştı. Bu yüzden hiç geri oynama veya yapılan hamleden vaz geçme olmamıştır.

Bu oynama esasını daha iyi anlatabilmek için daha ufak bir örnek üzerinden çalışmayı gösterelim :

?- oyna(2,a,b,c).

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

true

Görüldüğü üzere iki disklik bir dizilimde, c çubuğu geçici olarak kullanılmakta, esas büyük diskin b çubuğuna oynanması sırasında, küçük diskleri depolamak için kullanılmaktadır.

Bu durum disk sayısı artsa da değişmez. En büyük diskin a çubuğundan b çubuğuna oynanması sırasında,  diğer bütün küçük diskleri depolamak için c çubuğunu kullanırız. Buradan anlaşılacağı üzere ikinci büyük diskin c çubuğuna oynaması gerekir. Bunun için de b çubuğunu geçici depolama için kullanırız. Bu yaklaşım en büyük diskten en küçüğüne kadar aynı mantıkla işleyerek devam eder.

8 Vezir Problemi (8 Queens Problem)

Yeni bir problem olarak klasik sorulardan birisi olan 8 vezir problemini ( eight queens problem) ele alalım. Problem basitçe bir satranç tahtasına 8 veziri, birbirini yemeden nasıl yerleştireceğimizdir.

Problemin çözümü olan PROLOG kodu aşağıda verilmiştir.

perm([X|Y],Z) :- perm(Y,W), birinial(X,Z,W).

perm([],[]).

birinial(X,[X|R],R).

birinial(X,[F|R],[F|S]) :- birinial(X,R,S).

cozum(P) :-

     perm([1,2,3,4,5,6,7,8],P),

     birlestir([1,2,3,4,5,6,7,8],P,S,D),

     hepsifarkli(S),

     hepsifarkli(D).

birlestir([X1|X],[Y1|Y],[S1|S],[D1|D]) :-

     S1 is X1 +Y1,

     D1 is X1 – Y1,

     birlestir(X,Y,S,D).

birlestir([],[],[],[]).

hepsifarkli([X|Y]) :-  \+member(X,Y), hepsifarkli(Y).

hepsifarkli([X]).

Kodun çalışan örneği aşağıdaki şekildedir:

?- cozum(P).

P = [5, 2, 6, 1, 7, 4, 8, 3] ;

P = [6, 3, 5, 7, 1, 4, 2, 8] ;

P = [6, 4, 7, 1, 3, 5, 2, 8] ;

P = [3, 6, 2, 7, 5, 1, 8, 4] ;

P = [6, 3, 1, 7, 5, 8, 2, 4] ;

P = [6, 2, 7, 1, 3, 5, 8, 4] ;

P = [6, 4, 7, 1, 8, 2, 5, 3] ;

P = [3, 6, 2, 7, 1, 4, 8, 5] ;

P = [6, 3, 7, 2, 4, 8, 1, 5] ;

…

Yukarıdaki örneklerde görüldüğü üzere her kolon için, o kolondaki kaçıncı satıra vezir yerleştirilebileceği ve bu yerleştirme işlemine göre bütün kuralları sağlayan bir dizilimin nasıl elde edileceği listelenmiştir. Problemin birden fazla çözümü olduğu için her satır, çözümlerden birisini göstermektedir. Örneğin ilk çözüm satırını ele alırsak, aşağıdaki gibi bir satranç tahtası elde ederiz.

P = [5, 2, 6, 1, 7, 4, 8, 3] ;

Kodda, kabaca bütün ihtimalleri deneyen bir permütasyon algoritması geliştirilmiştir. Ardından koşulların sağlanıp sağlanmadığı kontrol edilmiş ve buna göre koşulları sağlayan ihtimaller sonuç olarak döndürülmüştür.

Algoritma, bir arama algoritması (search algorithm) şeklinde probleme yaklaştığı için, problemin çözümü sırasındaki bütün ihtimaller sadece bir kere denenecek ve denenen bir ihtimal tekrar etmeyecektir. Bu deneme sırası, permütasyon fonksiyonu ile sağlanır.

92 views

Çeşitli kayanklarda kelime aritmetiği (verbal aritmetic), kelime toplamı (word addition) veya kısaca cryptarth olarak da geçmektedir. Basitçe iki kelimenin toplamından elde edilen harf denklemidir.

Aşağıda bir cryptartihm verilmiştir:

Yazının tam bu noktasında belirtmeliyim ki tek çözümlü anlamlı bir cryptarithm bulmak oldukça zor. Bu yazıyı yazarken hiç Türkçe cryptarithm olmadığını gördüm ve yaklaşık bir saatlik bir uğraştan sonra (yüzlerce ihtimal denemesi yaparak) yukarıdaki örneği yazabildim. Elbette daha başka örnekler de Türkçe için anlamlı olarak geliştirilebilir ama en azından konuyu bundan sonra anlatırken yukarıdaki örneği kullanacak olanlar bilgisayarkavramlari.com sitesine atıfta bulunurlarsa sevinirim.

Örneğin yukarıda verilen denklemi çözmeye çalışalım. Buna göre nota + keman = musiki olduğuna göre m harfi en fazla 1 olabilir. Çünkü 4 haneli bir sayı ile 5 haneli bir sayı toplandığında çıkan 6 haneli sayının ilk hanesi 1′den büyük olamaz. Bu durumda m = 1 olarak bulunursa, k harfinin alacağı değer 9 olmuş olur. Bunun sebebi 5 haneli bir sayının ilk hanesi 9 olmalıdır ki 4 haneli sayı ile toplamındaki 4. basamaktan gelen değer 1 olduğunda (iki tek haneli sayının toplamının sonucunda elde var değerinin en fazla 1 olacağını hatırlayınız) 9 ile toplanarak 10 sonucuna ulaşılsın.

O halde k = 9 ve doğal olarak 9+1 = 10 ise m = 1 ve u = 0 olarak bulunur.

Şimdi diğer değerlere bakalım. k değeri ile toplanarak bir ilave hane çıktığına göre n + e değeri 10′dan büyük olmalıdır.

n + e > 10 ise  n + e = 10 + s

a+n = 10 + i veya i  olabilir

a + t = 9 veya 19 olduğunu biliyoruz (çünkü k = 9 olduğunu bulmuştuk)

Bu durumda a + n + 10 a + 10 t + 100 m + 100 o = 100 i + 10 k + i olmalıdır. Bu denklemde bilinenleri yerine yazarsak (m ve k )

n + 11 a + 10 t + 100 + 100 o = 101 i + 10 k denklemini buluruz.

denklemde 100′e bölünenleri ortak paranteze alırsak

100 ( 1 + o ) = 101 i + 10 ( k – t ) – 11 a – n

o halde t asgari 1 olabileceğine ve a ise azami 0 olabileceğine göre ( bu durumda eşitliğin sağ tarafı için aşağıdaki durum geçerlidir):

101 + 100 o <= 101 i + 98

3  + 100 o <= 101 i

Buna göre denklemi sağlayan tek o değeri 3 olur.

Bu haliyle denklem aşağıdaki şekildedir:

n3ta + 9e1an = 10si9i

Diğer değişkenleri bulmak artık daha da basittir:

m + o = 1 + 3 = 4 olduğuna göre i = 4 bulunur.

n3ta + 9e1an = 10s494

son iki hane için aşağıdaki denklem çıkarılabilir:

10 t + a + 10 a + n = 94 (elde var devri olmadığı için)

11 a + 10 t + n = 94 denklemindeki çözüm ihtimalleri aşağıdaki şekildedir:

Yukarıdaki ihtimaller dışında bir çözüm bulunmamaktadır.

ayrıca n + e > 9 olmalı şartını hatırlayalım. Bu durumda n değeri 0 olamaz. Son olarak a + n = 4 veya 14 olduğuna göre tabloda bu şartı sağlamayanları eleyelim:

Son olarak n = a olmadığına göre yani eşit olsalar aynı değişkenle gösterileceklerine göre kalan iki ihtimali incleyelim:

4390 + 9e104 = 10s494

denkleminde a = u olduğu için bu değerleri de alamayız.

son olarak kalan diğer ihtimale bakalım:

8326 + 97168 = 105494 olarak sonuçlar bulunur.

235 views

Veri sıkıştırmada veya verinin ikilik tabanda gösterilmesinde kullanılan bir algoritmadır. Basit bir çevirim fonksiyonu olarak da düşünülebilir. Bu yazı kapsamında birkça farklı elias kodu (elias code) şekli anlatılacaktır.

Elias-Υ Kod (Elias – Υ  Code): Elias upsilon kodlaması olarak okunur.

İki formül bu kodlama için gereklidir.

k_d = taban(log₂ k)

k_r = k_d - 2 ^log₂ k
Yukarıdaki formülde k değeri, çevirimini istediğimiz değerdir. Elias-Upsilon kodlaması ise bu değerlerden ilkinin tekil kodlaması (unary coding) ile ikincisinin ikli kodlaması (binary coding) birleşimidir (yan yana yazılması, üleştirilmesi)

Örnek olarak bazı sayıların çevirimleri aşağıda verilmiştir:

Yukarıdaki tabloda görüldüğü üzere sayılar büyüdükçe kodlama uzunluğu da değişmektedir.

Elias-δ  Kodu (Elias-δ   Code) : Elias-Delta kodlama olarak okunabilir.

Yukarıda anlatılan elias-upsilon kodlamasını daha az bit ile gösterebilmek için geliştirilmiştir. Basitçe elias-upsilon kodlaması yaklaşık 2 log ₂( k) kadar bit gerektirmektedir. Bu bit sayısını azaltmak için elias-delta kodlaması kd ve kr hesaplamalarına ilave olarak iki değer daha hesaplar.

k_dd = taban(log₂(k_d + 1))

k_dr = k_d – 2 ^{log₂(k_d + 1))}
Görüldüğü üzere aslında elias-delta kodlamasında yapılan işlem, elias-upsilon kodlamasında bulunan kd değerini yeniden aynı formüllere koymak ve kd üzerinden kdd ve kdr değerlerini hesaplamaktır. Ardından bulunan kdd kdr ve kr değerleri birleştirilerek elias-delta kodu sonucu bulunur.

Örnek bazı saylar aşağıda verilmiştir:

Yukarıda görüldüğü üzere genel olarak sayılar büyüdükçe elias-upsilon kodlamasına göre daha az bit gerekmektedir. düşük sayılarda daha fazla bit gerektiği görülmekte ve biraz da olsa işlem karmaşıklığı artmaktadır.

128 views

Verilerin tekil karşılıkla kodlanmasıdır. Buna göre her verinin kendisine ait bir basamakta karşılığı bulunur.

Basitçe k değerindeki bir sayının kodlanması için k adet 1 ve sonuna bir adet 0 konulur.

Örneğin aşağıda bazı sayıların tekil kodlama (unary coding) karşılıkları verilmiştir:

1 –> 10

2 –> 110

3 –> 1110

11 –> 111111111110

Buna göre, 1023 sayısının karşılığı olarak 1023 adet 1 ve ardından 0 gelmesi gerekir.

Tekil kodlama düşük seviyeli sinyal işleme için bazı durumlarda kullanışlıdır ve her veri ünitesinin (her sayının) bitişini belirten bir sinyal olarak 0 kullanılmıştır. Ancak tekil kodlamanın en büyük mahsuru veriyi çok uzun kodlaması ve bunun sonucunda yer israfıdır.

Örneğin ikili kodlama (binary coding) için veriler ikilik tabana çevrilir. Bu durumda yukarıdaki örnekte verilen sayıların karşılıkları aşağıdaki şekilde olacaktır:

1 –> 1

2 –> 10

3 –> 11

11 –> 1011

Görüldüğü üzere çok daha az yer kaplayan veriler elde edilebilmektedir ancak bu değerlerin sürekli olarak 1 ve 0 olarak değişmesi söz konusudur. Diğer yandan veriler arasında bir ayrım söz konusu değildir. Örneğin tekil kodlama ile yollanan aşağıdaki dizgiyi (string) ele alalım:

101101110

Bu dizginin karşılığının 123 olduğu kolayca bulunabilirken aynı verinin ikili kodlamadaki karşılığı

11011

olmakta ve bu verinin 123 mü yoksa 11 mi olduğu bilinememektedir.

56 views