Graflar

GRAFLAR

Merhaba arkadaşlar,

Bugünkü yazımda sizlerle graflar hakkındaki bilgilerimi paylaşacağım. Graf tanımı olarak çok kısa ve net bir tanım vereceğim.

Graf : Bilgi parçaları arasındaki ilişkileri gösterir. Bir G grafı V ile gösterilen düğümlerden (verteks) ve E ile gösterilen kenarlardan (edge) oluşur.

Matematiksel olarak modellersek  G=(V,E) şeklindeki yapı  olarak tanımlayabiliriz.

Peki ne işe yarar bu graflar nerede kullanılırlar ?

Bu sorunun yanıtı için günlük hayattan çok sayıda örnekler verebiliriz.

Ulaşım hatlarında, elektronik devrelerde, bilgisayar ağlarında, veritabanı sistemlerinde kullanıldığını görebiliriz. Hemen bir örnek ile daha açık bir hale getirelim.

Örnek :  Bursaray metrosundaki durakları ele alabiliriz.

Gördüğünüz gibi durakların birbiriyle bağlantılarını anlatan graf modelini oluşturduk.

Graflar yönlü, ağırlıklı olarak çeşitlendirilebilir ilerleyen bölümlerde ele alacağım.

Şimdi bir grafın matematiksel modelini daha ayrıntılı ele alalım.

Yukarıdaki  G grafının düğüm kümesi  {v1,v2,v3,v4} ve ayrıt kümesi {e1,e2,e3,e4,e5} tir.

f: E­­ → P(V)  fonksiyonu şöyle tanımlanmaktadır.

f : e1→ a{V1}

f : e2→ a{V1,V2}

f : e3→ a{V1,V3}

f : e4→ a{V2,V3}

f : e5→ a{V2,V3}

Bu dönüşümler sayesinde e1 ayrıtının V1 düğümünü kendisine, e2 ayrıtının V1 düğümü ile V2 düğümünü birbirine bağladığını görüyoruz.Yani kısaca V1 ve V2 noktaları arasında yönsüz olarak bir bağlantı olduğunu çıkarıyoruz.

Burada en önemli nokta şekil olarak verilen model bir graf değildir. Çünkü bir grafı farklı şekillerde birden fazla gösterebiliriz. Buda bize bir grafı bir fonksiyon ile göstermemiz gerektiğini belirtir.Graflar ile ilgili bazı tanımları yapalım.

Digraf: Bir grafta ayrıtların düğümleri bağlarken yön kavramı mevcut ise bu graflara digraflar denir.

Ağırlıklı Graf: Graftaki her bir ayrıtın kendine ait ağırlıkları mevcut ise bu graflara ağırlıklı graf denir.

Komşuluk : e1, e2 grafın 2 ayrıtı olsun. Eğer e1 ve e2 nin bağlı olduğu ortak bir düğüm var ise bu ayrıtlar birbirine komşudur.

Derece: Bir v düğümünün derecesi kendisine bağlı olan ayrıt sayısıdır. Eğer  bir ayrıt v yi kendisine bağlıyor ise ve herhangi bir belirtme yapılmamış ise bu ayrıt v düğümünün derecesini 2 arttırır.

KomşulukMatrisi: Graflar için önemli bir tanımdır.Bir G grafında V={vq,v2,…,vn} düğüm kümesi olsun.

Aij , vi düğümünün vj düğümüne bağlantılı olup olmadığını ve bağlantı sayısını belirtir.  Örnek olarak ;

Grafının komşuluk matrisini oluşturalım.

Şeklinde oluştururuz burada satırlar ve sütunlar düğümleri matristeki değerlerde o düğümler arasındaki ayrıt sayısını vermektedir. Dikkat ettiyseniz matrisimiz köşegene göre simetriktir.Komşuluk matrisleri eğer graf yönlü bir graf değil ise her zaman simetriktir.  Ve matrisimiz daima nxn lik kare matristir ki buradaki n değişkeni düğümler kümesindeki toplam düğüm sayısına eşittir. A² matrisimizde grafın herhangi bir düğümünün 2 birim uzaklıkla ulaşabildiği düğümleri belirtir. Aynı şekilde Aⁿ matriside n birim uzaklıkla ulaşılabilen düğümleri belirtir. A.A = A² matris işlemiyle herhangi bir düğümden 2 birim uzaklıkla ulaşılabilen düğümleri görebiliriz.

YOLLAR ve DEVRELER :

Yol: Bir yol v1 den vn e kadar sıralı düğümleri  (v1,v2), (v2,v3),…(v(n-1),vn)  ayrıtlarıyla birbirine bağlar.Eğer bu yol boyunca herhangi bir düğüm tekrarı yok ise bu yol Basit Yol olarak adlandırılır.

Çevre:  Başlangıç ve bitiş noktaları aynı düğüm olan yollara çevre denir. Eğer çevre içerisinde düğüm tekrarı yok ise basit çevre olarak adlandırılır. 

Örnek :  v2,v3,v4,v5,v3,v2 bir çevre, v2,v3,v4,v2 ise basit çevredir.

Euler ve Hamilton teoremleri ile ilgili ilerleyen zamanlarda yazacağım.

Algoritma ve Programlama

Merhaba arkadaşlar bu yazımda sizlerle algoritma ve programlama temeli hakkındaki bilgilerimi paylaşacağım.

Öncelikle algoritma tanımı ile başlayalım.

Algoritma : Bir problemi çözüme kavuşturmak için kullanılan sıralı , mantıksal  adımların bütünüdür.

Çeşitli dillerde yazılabilir. Algoritma yazarken dikkat edilmesi gereken bazı hususlar vardır.

·        *  Her adım belirleyici olmalıdır.

·        * Mutlaka sonlandırılmalıdır.

·         * En önemli özellik olarak ta karşılaşılabilecek tüm durumlar göz önüne alınarak oluşturulmalıdır.

Algoritma kelimesi Türk Matematikçi olan El-Harezmi’nin isminden türemiştir.

Algoritma bir çok dille ifade edilebilir bir kavramdır. Genel olarak ortak kullanılan “pseudo code  (sahte kod)” ile ifade edilir.

Programlama dilini de tanımlayacak olursak bir problemin algoritmik çözümününün bilgisayar ortamında olmasını sağlayan belirli kurallar dizisidir.

Genel  tanımlamaları kısa tutup örnekler vermenin daha yararlı olacağını düşünüyorum.

Genel anlamda açıklayıcı bir örnekle başlayalım.

Örnek:  

1. Pastanın yapımı için gerekli malzemeleri hazırla

2. Yağı bir kaba koy

3. Şekeri aynı kaba yağın üzerine koy

4. Yağ ve şekeri çırp

5. Karışımın üzerine yumurtayı kır

6. Tekrar çırp

7. Kıvama geldi mi diye kontrol et

8. a. Kıvamlı ise 9. adıma devam et b. Değilse 6. adıma dön.

9. Karışıma un koy

10.Karışıma vanilya, kabartma tozu vb. koy

11.Karışımı Kıvama gelinceye kadar çırp

12.Pastayı Kek kalıbına koy

13.Yeteri kadar ısınan fırına pastayı koy

14.Pişimi diye kontrol et

15. a. Pişmiş ise 16. adıma devam et b. Değilse 14. adıma dön

16.Keki fırından çıkart

17.Fırını kapat

18.Kekin ı kapat

19.Kekin soğumasını bekle

20.Keki servis edebilirsin.

Örnekten de anlayabileceğimiz gibi aslında hepimiz yaşantımızda bazı çözümler yaparken bir algoritma oluşturup uygulamış oluruz.

“Matematik Hayattır. “ sözüne istinaden algoritmalar oluşturulurken temelinde matematiksel işlemler çok büyük önem taşır.

Örnek : : Bir marangoz atölyesinde 4 tür sandalye üretilmektedir. Her sandalye türünden kaçar tane üretildiğini bulan bir algoritma yazalım. (Her bir sandalye türünü T1,T2,T3 ve T4  ile gösterelim.)

A1: Başla.

A2: T1, T2, T3 ve T4 ün başlangıç değerleri sıfır al.

A3: Üretilen sandalye türünü öğren.

A4: Eğer tür T1 ise T1 in değerini 1 arttır ve sonucu T1 e ata ve A8 e git.

A5: Eğer tür T2 ise T2 in değerini 1 arttır ve sonucu T2 ye ata ve A8 e git.

A6: Eğer tür T3 ise T3 in değerini 1 arttır ve sonucu T3 e ata veA8 e git.

A7: Eğer tür T4 ise T4 in değerini 1 arttır ve sonucu T4 e ata ve A8 e git.

A8: Başka sandalye üretildimi öğren. (Evet veya Hayır yanıtını belirtiniz)

A9: Yanıtınız Evet ise A11 e git.

A10:Yanıtınız Hayır ise A12 ye git.

A11:A3 e git.

A12: T1,T2,T3 ve T4 değerlerini belirt.

A13: Dur.

Tabii ki algoritmalar çok daha zor ve karmaşık problemlerin çözümünde kullanılırlar. Benim amacım sizlere basit bilgiler vermekten çok anlaşılır örnekler verebilmek.

Örnek :

** Verilen bir k pozitif tamsayısına kadar olan tüm tamsayılar için

·         T(k)=k²-3k+5/4 ifadesini hesaplayan,

·         T(k)>25 lerin toplamını bulan,

·         Negatif T(k)ların ortalamasını bulan algoritmayı yazın.

                 Print ‘pozitif bir tamsayı öğren’

               read k

                 i =  0 , top  = 0, topneg = 0, sn = 0

basla:   i= i+1

                T=i*i-3*i+5/4

If   T>25     Then       top=top+T

Endif

If   T<0     Then        topneg =topneg+T

                                                       Sn=sn+1

                Endif

If i<k then go to basla

Print ‘T(k)>25 lerin toplamı’,top

Print ‘T(k)<0 ların ortalaması’, topneg/sn

End

Yukarıda verilen bir fonksiyona göre istenilen yargıların sonuçlarını bulduran bir algoritma yazdım.

Algortimalar konusu çok derin detaylı bir konu olduğundan çok fazla detayına girmek istemiyorum. Birkaç algoritma örneği daha verip yazımı bitiriyorum.

Örnek : Klavyeden girilen bir N değerine kadar Fibonacci Dizisi bulan algoritma.

A1 : Başla

A2 : A=1

A3 : B=1

A4 : A,B yaz

A5 : C=A+B

A6 :EĞER C>N ise A11 e git.

A7 : C yaz

A8 : A=B

A9 : B=C 

A10 : A5 e git.

A11: Bitir.

Örnek : Girilen bir sayının asal sayı olduğunu bulduran program.

A1 : Başla

A2 : A sayısını giriniz.

A3 : t=2

A4 : Amod t = 0 ise “Sayı asal değildir” Aksi halde “sayı asaldır.”

A5 : t= t+1

A6 : Eğer t < TAM(A/2)  ise A4 e git.

A7 : Bitir.

Örnek : Girilen sayının faktöriyelini bulan program.

A1 : Başla

A2 : A sayısını giriniz

A3 : i =1 , fak =1

A4 : Eğer i = A ise A8 e git.

A5 : fak = fak*i

A6 : i = i+1

A7 : A4 e git.

A8 : “fak değeri sayının faktöriyelidir.”

A9 : Bitir.

İlerleyen zamanlarda algoritma ve karmaşıklıklar konuları hakkında da yazmaya çalışacağım Umarım faydalı olmuştur.

Önermeler ve Mantık

Önermeler  ve Mantık

Merhaba arkadaşlar,

Bu yazımda sizlerle Önermeler ve Mantık konusunda paylaşımda bulunacağım.

Önerme :  Bir doğruluk değerine sahip olan bir  ifadedir. Doğruluk değeri kavramının elemanları {0,1} dir. Doğru bir önermenin doğruluk değeri “1”, yanlış bir önermenin ise doğruluk değeri “0” olarak alınır.

*Bu durumda soru anlamı taşıyan hiçbir ifade önerme olarak kabul edilemez.

Mantık : Mantık önermelerin geçerli olup olmadıklarını bazı kurallar çerçevesinde ifade etmeye yarar.

*Mantık önermelerin ne olduğu ile ilgilenmez yalnızca doğruluk değerleri ile ilgilenir.

Örnek:  Aşağıda bazı önerme ve önerme olmayan ifade örnekleri mevcuttur.

1-      Bugün günlerden Salıdır.

2-      4x4 = 64.

3-      Türkiye’nin başkenti Ankara’dır.

4-      Dün gece partidemiydin ?  (Önerme Değildir)

5-      Çok yaşa FENERBAHÇE. (Önerme Değildir)

*Genel olarak önermeler matematiksel olarak “p,q,r,s,t” gibi sembollerle ifade edilirler.

Önermeler  basit ve birleşik olarak sınıflandırılırlar. Yukarida ki önermeler basit önermelerdir.

Öngörürsünüz ki, basit önermeler  belirli bağlaçlarla birleşik önerme haline getirilebilir. Şimdi bu bağlaçları inceleyelim.

Değil  Bağlacı (Tersini Alma): Bir önermenin doğruluk değerini tersi ile değiştiren bağlaçtır.

­­­­­­­(¬p),(p’) şeklinde gösterilir.

Mantık önermelerin doğruluk değerleri ile ilgilenir demiştik.Bunu en net görüp anlayabilceğimiz yapıda ” Doğruluk Tablosu ” diyebiliriz. Ohalde değil bağlacını doğruluk tablosu ile inceleyelim.

p	¬p
0	1
1	0

Yukarıdaki tabloda herhangi bir p önermesinin ve değil bağlacı ile p nin değili ya da p nin tersi olan ifadenin doğruluk değerlerini görüyoruz.

‘Ve’ Bağlacı : İki tane basit önermenin arasına ‘ ve’ kelimesi olarak koyduğumuz bağlaçtır.

p˄q  olarak ifade ederiz. Aslında ve bağlacı ile bildiğimiz bu bağlacın yaptığı işlem kesişim işlemidir.

Kümelerde kesişimi biliyoruz ve mantıkta da kesişim iki ifadenin de doğruluk değeri  1 olduğunda  doğruluk değeri  1 olan ifadedir. Aşağıda doğruluk tablosundaki değerlerini görebiliriz.

p	q	p˄q
0	0	0
0	1	0
1	0	0
1	1	1

‘Veya’ Bağlacı : İki tane basit önermenin arasına ‘ veya’ kelimesi olarak koyduğumuz bağlaçtır.

p˅q  olarak ifade ederiz. Aslında veya  bağlacı ile bildiğimiz bu bağlacın yaptığı işlem birleşim işlemidir.Yine kümelerdeki  birleşim işlemini hatırlayacak olursak bir elemanın herhangi bir kümede olması yeterli olduğunu anımsarız. Veya bağlacı ile oluşturulmuş birleşik önermesinde de herhangi bir önermenin doğruluk değerinin 1 olması sonucun doğruluk değerinin 1 olmasını gerektirir.

p	q	p˅q
0	0	0
0	1	1
1	0	1
1	1	1

‘İse’ Bağlacı : İki tane basit önermenin arasına ‘ise’ kelimesi olarak koyduğumuz bağlaçtır.Koşullu önermeler oluşturmak için kullandığımız bir bağlaçtır.

p => q şeklinde gösterilir. Örnek olarak p: bugün pazartesidir. q: bugün haftanın ilk günüdür.

p => q ifadesi “bugün pazartesi ise haftanın ilk günüdür.”

‘İse’ bağlacı ile oluşturulan birleşik önerme yalnızca 1. önermenin doğruluk değeri 1 ve 2. önermenin doğruluk değeri  0 iken 0 doğruluk değerine sahiptir. Aksi halde doğruluk değeri 1 dir.

p	q	P=>q
0	0	1
0	1	1
1	0	0
1	1	1

‘Ancak ve Ancak’ Bağlacı : İki tane basit önermenin arasına ‘ancak ve ancak’ kelimesi olarak koyduğumuz bağlaçtır.Koşullu önermeler oluşturmak için kullandığımız bir bağlaçtır.

p <=> q şeklinde gösterilir.

‘Ancak ve Ancak’ bağlacı ile oluşturulan birleşik önermede iki önermenin de doğruluk değeri birbirine eşit iken doğruluk değeri 1 Aksi halde doğruluk değeri 0 dir.

p	q	P<=>q
0	0	1
0	1	0
1	0	0
1	1	1

Ancak ve Ancak ifadesini (p=>q)˄(q=>p) şeklinde düşünebiliriz. Şimdi bunun ispatını yapalım.

p	q	p=>q	q=>p	(p=>q)˄(q=>p)
0	0	1	1	1
0	1	1	0	0
1	0	0	1	0
1	1	1	1	1

Doğruluk tablosunu oluşturduğumuzda  p<=>q ile (p=>q)˄(q=>p) ifadelerinin doğruluk değerlerinin birbirine eşit olduğunu görüyoruz.

** Sizde p=>q birleşik önermesinin  p’˅q  ile ifade edilebilceğini ispatlayabilirsiniz.

Totoloji ve Çelişki Kavramları :

Totoloji : Bir birleşik önermeyi oluşturan basit önermelerin doğruluk değerleri ne olursa olsun sonucun doğruluk değerinin daima 1 olduğu ifadelere denir.

Çelişki : Totoloji ye benzer bir tanımı vardır. Yalnızca sonuç olarak 0 doğruluk değerine sahiptir.

Örnek olarak;   (p˄q)˅(p˄q)’ ifadesini ele alalım.

p	q	p˄q	(p˄q)’	(p˄q)˅(p˄q)’
0	0	0	1	1
0	1	0	1	1
1	0	0	1	1
1	1	1	0	1

Yukarıda görüldüğü gibi sonuç daima 1 doğruluk değerine sahiptir o halde (p˄q)˅(p˄q)’ birleşik önermesi bir totolojidir.

Mantıksal Denklik :

İki birleşik önerme kendilerini oluşturan önermelerin tüm doğruluk değerleri için aynı doğruluk değerine sahip ise bu iki önerme mantıksal denktir denir. P≡Q şeklinde gösterilir.

Aslında konunun temelini oluşturan önemli bir tanımdır.Örnek olarak p’˅q’  ile (p˄q)’ ifadelerinin mantıksal denk olduğunu doğruluk tablosu yardımıyla görebilirsiniz.

Buraya kadar anlattıklarım önermeler mantığı ile ilgili temel ve basit bilgilerdir.Şimdi konuyu daha derinlemesine ele alacağım.

Önermeler Cebiri :

Önermeler Cebiri yukarıdaki bilgilerin sonucunda mantıksal denklikler ele alınarak oluşturulmuştur.

1-Aynılık (Tek Kuvvet Özelliği):

p ˄ p ≡ p

p ˅ p ≡ p

2- Değişme Özelliği :

p ˄ q ≡ q ˄ p

p ˅ q ≡ q ˅ p

p <=> q ≡ q <=> p

3- Birleşme Özelliği:

(p ˄ q) ˄  r ≡ p ˄ (q ˄ r)

(p ˅ q) ˅  r ≡ p ˅ (q ˅ r)

(p <=> q) <=>  r ≡ p <=> (q <=> r)

4-Yutan Eleman Özelliği :

p ˄ (p ˅ q) ≡ p

p ˅ (p ˄ q) ≡ p

5-Dağılma Özelliği :

p ˄ (q ˅ r) ≡ (p ˄ q) ˅ (p ˄ r)

p ˅ (q ˄ r) ≡ (p ˅ q) ˄ (p ˅ r)

6-Çift Ters Özelliği :

(p’)’ ≡ p

7-De Morgan Kuralları :

(p ˅ q)’ ≡ p’ ˄ q’    ** Burada “Ve” işleminin değilinin “Veya” işlemine dönüştüğünü görüyoruz.

(p ˄ q)’ ≡ p’ ˅ q’    ** Burada da “Veya” işleminin değilinin “Ve” işlemine dönüştüğünü görüyoruz.

8-Tamamlama Özelliği :

p ˅ p’ ≡ 1

p ˄ p’ ≡ 0

9-Özdeşlik Özelliği :

p ˅ 1 ≡ 1

p ˅ 0 ≡ p

p ˄ 1 ≡ p

p ˄ 0 ≡ 0

Birkaç tane daha özellik tanımı yapılabilir fakat en önemlisi bu özellikleri mantıksal denklikleri kullanarak bizde bulabiliriz.

Asıl önemli olan Önermeler Cebiri bize doğruluk tablosu kullanmadan ispat yapmayı sağlar. Çok sayıda önermelerden oluşan bir sistemi doğruluk tablosuna koyarak sonucu bulmaya çalışmak gerçekten çok zor.Şimdi sizlere Önermeler Cebiri kullanarak ispatlar birbirine mantıksal denk olan ifadelerin ispatlarını sunacağım.

Örnek :  (p’ ˄ q) ˅ (p ˅ q)’ ≡ p’ ifadesini ispatlayalım.

** (p’ ˄ q) ˅ (p ˅ q)’ ≡ (p’ ˄ q) ˅ (p’ ˄ q’)            2. Birleşik önermeye De Morgan Kuralı uyguladık.

** (p’ ˄ q) ˅ (p ˅ q)’ ≡ p’ ˄ (q ˅ q’)                      Dağılma özelliğini kullandık.

** (p’ ˄ q) ˅ (p ˅ q)’ ≡ p’ ˄ 1                                Tamamlama Özelliğini uyguladık.

** (p’ ˄ q) ˅ (p ˅ q)’ ≡ p’                                      Özdeşlik Özelliğini uyguladık.

Örnek : (p ˄ q)’ ˅ (p’ ˄ q) ˅ (p’ ˄ q’) ≡ p’˅ q’      ifadesini ispatlayalım

** (p’ ˅ q’)  ˅ (p’ ˄ q) ˅ (p’ ˄ q’)                         1. Birleşik önermeye De Morgan Kuralı uyguladık.

** (p’ ˅ q’)  ˅ (p’ ˄ (q ˅ q’))                                 Dağılma Özelliğini uyguladık.

** (p’ ˅ q’)  ˅ (p’ ˄ 1)                                          Tamamlama Özelliğini uyguladık.

** (p’ ˅ q’)  ˅ p’                                                   Özdeşlik Özelliğini uyguladık.

** (p’ ˅ p’)  ˅ q’                                                   Değişme Özelliğini uyguladık.

** p’ ˅ q’                                                              Aynılık Özelliğini uyguladık.

Görüldüğü gibi doğruluk tablosu kullanmak yerine Önermeler Cebiri tanımlarını kullanarak çok daha kolay bir şekilde ispatlarımızı tamamladık.

Bugünkü yazımın sonuna geldim. Umarım faydalı olmuştur.