Ayrık Matematik: Kümeler, Mantık, Bağıntılar ve Graflar

Ayrık Matematik, algoritmaların altında kullanılan matematiksel dili kümeler, mantık, bağıntılar, kombinatorik ve graflar üzerinden tek bir omurgada toplar. Tanımlar ve gösterimler daha sonraki algoritmik problemlerde yeniden kullanılabilecek biçimde ele alınır.

Bu dersin değeri sürekli matematikten “daha kolay” olmasında değil, bilgisayar bilimindeki nesnelerin çoğunun doğal olarak ayrık olmasında yatıyor. Bir durum makinesi, erişilebilirlik ilişkisi, doğruluk tablosu, kombinasyon sayısı veya graf yolu aynı düşünme disiplinini paylaşır: nesneleri açıkça tanımlamak ve sonucun hangi kurallardan çıktığını izleyebilmek.

Ünite 1: Kümeler Teorisine Giriş

1.1. Küme Kavramı

Bir bütün olarak ele alınan nesne topluluğuna küme denir. Topluluğu oluşturan nesnelere eleman denir.

Kümeler büyük harfle, elemanlar küçük harfle gösterilir. Aitlik ilişkisi iki simgeyle yazılır:

a ∈ A     a, A kümesinin elemanıdır
b ∉ B     b, B kümesinin elemanı değildir

Bir kümenin verilmesi için elemanlarının kesin biçimde belirlenmesi gerekir. İki gösterim kullanılır.

Liste yöntemi: elemanlar tek tek yazılır.

A = {1, 2, 3}

Ortak özellik yöntemi: elemanları ayırt eden karakteristik özellik verilir.

B = { x : x tam sayı ve x > 0 }

Tanımın belirleyici koşulu şudur. Bir nesnenin kümeye ait olup olmadığı kesin olarak karara bağlanabilmelidir.

Kümede sıra ve tekrar önemsizdir. {1, 2, 2, 3} ile {3, 1, 2} aynı kümedir.

Kapsam, kümeler kuramının aksiyomatik kuruluşu yerine kümeler cebri düzeyindedir.

1.2. Venn Diyagramları

Kümeler düzlemde kapalı bölgelerle gösterilir. Evrensel küme dikdörtgenle çizilir.

Diyagram ispat aracı değildir. Bağıntıları görselleştirir ve karşı örnek aramayı kolaylaştırır.

1.3. Sonlu ve Sonsuz Kümeler

Eleman sayısı bir doğal sayıyla ifade edilebilen kümeye sonlu küme denir. Eleman sayısına kardinalite denir ve s(A) ya da |A| ile gösterilir.

Sonlu olmayan kümeye sonsuz küme denir.

Sonsuz kümeler ikiye ayrılır. Doğal sayılarla birebir eşlenebilenlere sayılabilir sonsuz denir. Tam sayılar ve rasyonel sayılar bu sınıftadır. Eşlenemeyenlere sayılamaz denir. Reel sayılar bu sınıftadır.

1.4. Boş Küme

Hiç elemanı olmayan kümeye boş küme denir. ∅ ya da { } ile gösterilir.

Boş küme tektir. Her kümenin alt kümesidir.

{∅} kümesi boş küme değildir. Tek elemanlı bir kümedir ve elemanı boş kümedir.

1.5. Alt Küme ve Özalt Küme

A kümesinin her elemanı B kümesinde de bulunuyorsa A, B'nin alt kümesidir:

A ⊆ B  ⟺  ∀x (x ∈ A ⟹ x ∈ B)

A ⊆ B ve A ≠ B ise A, B'nin özalt kümesidir. A ⊂ B yazılır.

Her küme kendisinin alt kümesidir. Özalt kümesi değildir.

n elemanlı bir kümenin alt küme sayısı 2ⁿ'dir. Özalt küme sayısı 2ⁿ − 1'dir.

Bir kümenin bütün alt kümelerinden oluşan kümeye kuvvet kümesi denir. P(A) ile gösterilir ve |P(A)| = 2ⁿ olur.

1.6. Kümelerin Eşitliği

İki küme aynı elemanlardan oluşuyorsa eşittir:

A = B  ⟺  A ⊆ B  ve  B ⊆ A

Bu ölçüt küme eşitliği ispatlarının standart yöntemidir. İki kapsama ayrı ayrı gösterilir.

1.7. Evrensel Küme

Belirli bir incelemede söz konusu olan bütün elemanları içeren kümeye evrensel küme denir. E ya da U ile gösterilir.

Evrensel küme mutlak değildir. Probleme göre seçilir.

1.8. Birleşim

En az birine ait olan elemanlardan oluşan kümedir:

A ∪ B = { x : x ∈ A veya x ∈ B }

Özellikleri:

A ∪ B = B ∪ A                    değişme
(A ∪ B) ∪ C = A ∪ (B ∪ C)        birleşme
A ∪ ∅ = A                        birim eleman
A ∪ A = A                        eş güçlülük
A ∪ E = E                        yutan eleman
A ⊆ B  ⟺  A ∪ B = B

Sonlu kümelerde eleman sayısı içerme dışlama ilkesiyle bulunur:

|A ∪ B| = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

1.9. Kesişim

Her ikisine birden ait olan elemanlardan oluşan kümedir:

A ∩ B = { x : x ∈ A ve x ∈ B }

Özellikleri birleşimle simetriktir:

A ∩ B = B ∩ A
(A ∩ B) ∩ C = A ∩ (B ∩ C)
A ∩ E = A
A ∩ A = A
A ∩ ∅ = ∅
A ⊆ B  ⟺  A ∩ B = A

Kesişimi boş küme olan kümelere ayrık kümeler denir.

Dağılma özellikleri iki işlemi birbirine bağlar:

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

İki yönde de dağılma geçerlidir. Sayılarda toplama ve çarpma arasında bu simetri yoktur.

1.10. Tümleyen ve Fark

Evrensel kümede olup A kümesinde olmayan elemanlar A kümesinin tümleyenidir:

A' = { x ∈ E : x ∉ A }

Fark işlemi:

A \ B = { x : x ∈ A ve x ∉ B } = A ∩ B'

Temel özellikler:

(A')' = A
A ∪ A' = E
A ∩ A' = ∅
E' = ∅,   ∅' = E

De Morgan kuralları tümleyeni işlemin içine taşır:

(A ∪ B)' = A' ∩ B'
(A ∩ B)' = A' ∪ B'

Kurallar sonlu sayıda kümeye genişler. Tümleyen alındığında birleşim ve kesişim yer değiştirir.

1.11. Simetrik Fark

Yalnız birine ait olan elemanlardan oluşan kümedir:

A Δ B = (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B)

Değişme ve birleşme özellikleri vardır. A Δ A = ∅ ve A Δ ∅ = A olur.

Mantıktaki "dışlayan veya" işleminin küme karşılığıdır.

1.12. Sıralı İkili ve Kartezyen Çarpım

Sırası önemli olan iki elemanlı yapıya sıralı ikili denir. (a, b) ile gösterilir.

Eşitlik ölçütü şudur:

(a, b) = (c, d)  ⟺  a = c ve b = d

Kümede sıra önemsizdi. Sıralı ikilide belirleyicidir.

Kartezyen çarpım bütün sıralı ikililerin kümesidir:

A × B = { (a, b) : a ∈ A, b ∈ B }

Eleman sayısı çarpılır:

|A × B| = |A| · |B|

Kartezyen çarpım değişmeli değildir. A × B ile B × A genelde farklıdır.

İşlem, birleşim ve kesişim üzerine dağılır.

1.13. Kümelerde Boole Cebri

Küme işlemleri belirli aksiyomları sağlar. Kuvvet kümesi, birleşim, kesişim ve tümleyen işlemleriyle birlikte bir Boole cebri oluşturur.

Sağlanan aksiyomlar şunlardır: değişme, birleşme, dağılma, birim eleman ve tümleyen.

İkilik ilkesi bu yapının en kullanışlı sonucudur. Doğru bir eşitlikte ∪ ile ∩ ve E ile ∅ karşılıklı değiştirilirse yine doğru bir eşitlik elde edilir.

Aynı cebirsel yapı önermeler mantığında ve anahtarlama devrelerinde ortaya çıkar. Üç alan aynı kurallarla işler. Ünite 3'te bu bağ kurulur.

1.14. Sayı Kümeleri

Kapsama zinciri şöyledir:

ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ

Doğal sayılar ℕ = {0, 1, 2, ...} sayma sayılarıdır.

Tam sayılar ℤ negatifleri de içerir. Çıkarma işlemine göre kapalıdır.

Rasyonel sayılar ℚ, a/b biçiminde yazılabilen sayılardır. b ≠ 0 olmalıdır. Ondalık açılımları sonlu ya da devirlidir.

İrrasyonel sayılar kesir biçiminde yazılamaz. Ondalık açılımları sonsuz ve devirsizdir. √2, π ve e bu sınıftadır.

Reel sayılar ℝ, rasyonel ve irrasyonel sayıların birleşimidir.

1.15. Aralıklar

[a, b] = { x : a ≤ x ≤ b }      kapalı
(a, b) = { x : a < x < b }      açık
[a, b) ve (a, b]                yarı açık

Sonsuz uçlar her zaman açık yazılır.

1.16. Mutlak Değer

|x| = x,   x ≥ 0
|x| = −x,  x < 0

Geometrik anlamı, sayının sıfıra uzaklığıdır. |x − a| ifadesi x ile a arasındaki uzaklıktır.

Temel özellikler:

|x| ≥ 0
|x·y| = |x|·|y|
|x/y| = |x|/|y|
|x + y| ≤ |x| + |y|          üçgen eşitsizliği
||x| − |y|| ≤ |x − y|

Eşitsizlik çözümlerinde iki dönüşüm kullanılır:

|x| < a  ⟺  −a < x < a
|x| > a  ⟺  x < −a  veya  x > a

1.17. Tam Kısım

x sayısını aşmayan en büyük tam sayıya tam kısım denir. ⌊x⌋ ile gösterilir.

⌊3,7⌋ = 3
⌊−3,7⌋ = −4

Negatif sayılarda aşağı yuvarlama yapılır. En sık yapılan hata, kesir kısmının atılacağı varsayımıdır.

Temel bağıntı:

⌊x⌋ ≤ x < ⌊x⌋ + 1

x − ⌊x⌋ farkına kesir kısmı denir ve her zaman [0, 1) aralığındadır.

Tavan fonksiyonu ⌈x⌉, x'ten küçük olmayan en küçük tam sayıdır. Algoritma analizinde blok sayısı hesaplarında kullanılır.

1.18. Sayılabilirlik ve Kardinalite

Sonlu kümelerde eleman sayısı doğrudan bir doğal sayıdır. Sonsuz kümelerde ise “kaç eleman var?” sorusu bire bir eşleme üzerinden tanımlanır. İki küme arasında bijeksiyon kurulabiliyorsa bu kümelerin kardinaliteleri eşittir.

Doğal sayılar kümesiyle bijeksiyon kurulabilen sonsuz kümelere sayılabilir sonsuz denir. Tam sayılar ilk bakışta doğal sayılardan daha büyük görünür; buna rağmen elemanları uygun bir sıraya dizildiğinde doğal sayılarla bire bir eşlenebilir. Rasyonel sayılar da uygun bir tarama düzeniyle sayılabilir.

Reel sayılar aynı sınıfta değildir. Cantor'un köşegen düşüncesi, [0,1] aralığındaki reel sayıların doğal sayılarla bijektif biçimde listelenemeyeceğini gösterir. Böylece sonsuz kümelerin de farklı büyüklükleri olduğu görülür.

Kardinalite, algoritmik açıdan da önemlidir. Bir veri alanının sonlu, sayılabilir ya da sürekli olması; tüm durumların taranabilir olup olmadığını, temsil biçimini ve doğrulama stratejisini doğrudan etkiler.

1.19. Mantık, Kombinatorik ve Graf Yapılarını Aynı Ayrık Modelde Okumak

Dersin yedi ünitesi ayrı görünür. Tek bir fikir hepsini bağlar.

O fikir sonlu yapıların ilişki olarak modellenmesidir.

Zincir şöyle kurulur:

küme
   ↓
kartezyen çarpım
   ↓
bağıntı
   ↓
fonksiyon
   ↓
graf
   ↓
matris ve algoritma

Küme temel nesnedir. Kartezyen çarpım eleman çiftlerini üretir. Bağıntı, bu çiftlerin bir alt kümesidir. Fonksiyon, ek koşul taşıyan bir bağıntıdır. Graf, bağıntının görsel karşılığıdır. Matris, grafın makine karşılığıdır. Algoritma, matris üzerinde işleyen yordamdır.

Her halka bir öncekinin özelleşmesi ya da başka bir dildeki karşılığıdır.

İkinci bağ aynı cebrin üç yüzüdür. Küme işlemleri, önerme bağlaçları ve anahtarlama devreleri aynı Boole cebrini kullanır.

∪    ∨    paralel bağlama    OR
∩    ∧    seri bağlama       AND
'    ¬    açık anahtar       NOT

De Morgan kuralı üç alanda da aynıdır. Bir alanda yapılan sadeleştirme diğerinde geçerlidir. Bu nedenle küme cebri öğrenmek, devre sadeleştirme öğrenmektir.

Üçüncü bağ sayma ile yapının birbirini beslemesidir. Alt küme sayısının 2ⁿ olması kombinasyon toplamından çıkar. Bağıntı sayısının 2^(n²) olması aynı hesabın kartezyen çarpım üzerine uygulanmasıdır. Permütasyon hem bir sayma sonucudur hem bir grup yapısıdır.

Dördüncü bağ temsil seçiminin maliyeti belirlemesidir. Aynı bağıntı listeyle, matrisle ya da bit vektörüyle temsil edilir. Üçü de doğrudur. Hangi işlemin sık yapılacağı hangisinin seçileceğini belirler. Bu, ayrık matematiği doğrudan yazılım mühendisliğine bağlayan noktadır.

Beşinci bağ denklik ile sıralamanın karşıtlığıdır. İki bağıntı türü tek bir koşulla ayrılır. Simetri denklik verir ve kümeyi parçalara ayırır. Ters simetri sıralama verir ve kümeye düzen koyar. Ayırmak ve düzenlemek, ayrık yapılarla yapılan iki temel iştir.

1.20. Bağıntı, Fonksiyon, Graf ve Algoritma Kavramlarını Ayırmak

Temel kavramsal ayrımlar:

∈ ≠ ⊆. Aitlik eleman ile küme arasındadır. Kapsama iki küme arasındadır.

∅ ≠ {∅}. Boş kümenin elemanı yoktur. İkincisi tek elemanlıdır.

Alt küme ≠ özalt küme. Her küme kendisinin alt kümesidir, özalt kümesi değildir.

Küme ≠ sıralı ikili. Kümede sıra önemsizdir. Sıralı ikilide belirleyicidir.

A × B ≠ B × A. Kartezyen çarpım değişmeli değildir.

Permütasyon ≠ kombinasyon. Sıra sonucu değiştiriyorsa permütasyondur.

Toplama ilkesi ≠ çarpma ilkesi. Seçimler arasında "veya" varsa toplanır, "ve" varsa çarpılır.

Önerme ≠ önermesel. Önermenin doğruluk değeri vardır. Önermeselde değişken bulunur.

Kapsayan veya ≠ dışlayan veya. ∨ her ikisi doğruyken de doğrudur. ⊕ değildir.

p ⟹ q ≠ q ⟹ p. Karşıt önerme özgün önermeye denk değildir.

p ⟹ q ≡ q' ⟹ p'. Bir koşullu önerme yalnız karşıt tersine denktir.

Totoloji ≠ çelişme. İlki her durumda doğru, ikincisi her durumda yanlıştır.

Denklik bağıntısı ≠ sıralama bağıntısı. Biri simetrik, diğeri ters simetriktir.

Simetrik ≠ ters simetrik. İkisi birden olan bağıntı vardır. Hiçbiri olmayan da vardır.

Yansıyan olmamak ≠ yansımaz olmak. İlkinde bazı elemanlar eksiktir, ikincisinde hiçbiri yoktur.

Denklik sınıfları örtüşmez. İki sınıf ya özdeştir ya ayrıktır.

Kısmi sıralama ≠ tam sıralama. Tam sıralamada her çift karşılaştırılabilir.

Bağıntı ≠ fonksiyon. Fonksiyon iki ek koşul taşıyan bağıntıdır.

Bire bir ≠ örten. Sonsuz kümelerde biri diğerini gerektirmez.

(g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹. Bileşkenin tersinde sıra ters döner.

Euler devresi ≠ Hamilton devresi. İlki kenardan, ikincisi düğümden geçer.

Euler koşulu basittir, Hamilton koşulu değildir. Hamilton devresi problemi NP-tamdır.

Ağaç ≠ bağlantılı graf. Ağaç devresizdir ve kenar sayısı tam n − 1'dir.

Kruskal ≠ Prim. İlki kenar tabanlı, ikincisi düğüm tabanlıdır. İkisi de minimum kapsayan ağaç bulur.

Komşuluk matrisi ≠ komşuluk listesi. Matris yoğun, liste seyrek graflarda verimlidir.

Geçişken kapanış ≠ geçişkenlik denetimi. Kapanış eksik ikilileri ekler, denetim yalnız sınar.

Warshall döngü sırası değiştirilemez. Ara düğüm döngüsü en dışta olmalıdır.

Algoritma ≠ program. Algoritma dilden bağımsızdır.

WHILE ≠ FOR. İlki koşula, ikincisi sayaca dayanır.

Ayrık matematikte iyi çözüm çoğu zaman uzun hesap değil, doğru temsil seçimidir. Aynı problem küme, bağıntı, önerme veya graf diliyle ifade edildiğinde ispatın ve algoritmanın yapısı değişebilir. Bu nedenle notların ortak hedefi formül toplamaktan çok, problemi ayrık bir modele dönüştürme alışkanlığıdır.

Ünite 2: Permütasyon ve Kombinasyon

2.1. Faktöriyel

Ardışık pozitif tam sayıların çarpımına faktöriyel denir:

n! = n · (n−1) · (n−2) · ... · 2 · 1

Tanım gereği 0! = 1 alınır. Bu, boş dizilimin tek biçimde yapılabilmesinin karşılığıdır.

Yineleme bağıntısı:

n! = n · (n−1)!

Faktöriyel çok hızlı büyür. 20! değeri 64 bitlik tam sayıya sığar, 21! sığmaz. Kombinatorik hesaplarda taşma bu yüzden erken oluşur.

2.2. Sayma İlkeleri

Toplama ilkesi: bir iş ayrık yollardan biriyle yapılabiliyorsa toplam yol sayısı, yol sayılarının toplamıdır.

Çarpma ilkesi: bir iş ardışık aşamalardan oluşuyorsa toplam yol sayısı, aşama sayılarının çarpımıdır.

n₁ · n₂ · ... · nₖ

Ayrım şu sorudadır. Seçimler arasında "veya" varsa toplanır, "ve" varsa çarpılır.

Güvercin yuvası ilkesi: n kutuya n+1 nesne yerleştirilirse en az bir kutuda birden çok nesne bulunur.

İlke basittir, sonuçları güçlüdür. Genelleştirilmiş biçiminde n nesne k kutuya konursa en az bir kutuda ⌈n/k⌉ nesne bulunur.

2.3. Permütasyon

Bir kümenin elemanlarının sıralı dizilişine permütasyon denir.

n elemanın tümünün permütasyon sayısı:

P(n, n) = n!

n elemandan r tanesinin sıralı seçimi:

P(n, r) = n! / (n − r)! = n · (n−1) · ... · (n−r+1)

Belirleyici özellik sıradır. Aynı elemanlar farklı sırada farklı permütasyon sayılır.

2.4. Tekrarlı Permütasyon

Bazı elemanlar özdeş ise sıralamalar tekrar eder. n elemanın içinde k tür varsa ve tekrar sayıları n₁, n₂, ..., nₖ ise:

n! / (n₁! · n₂! · ... · nₖ!)

Her elemanın her seferinde seçilebildiği durumda, r uzunluklu diziliş sayısı nʳ olur. Şifre ve karakter dizisi sayımlarında bu biçim kullanılır.

Dairesel permütasyon sabit bir başlangıç noktası olmadığından farklıdır. n elemanın dairesel diziliş sayısı (n−1)! olur.

2.5. Permütasyonlar Grubu

Sonlu bir kümenin kendi üzerine bire bir ve örten fonksiyonlarına da permütasyon denir. Bu bakış, sayma yerine yapı üzerinedir.

n elemanlı kümenin bütün permütasyonlarının kümesi Sₙ ile gösterilir. Eleman sayısı n! olur.

Bileşke işlemi altında Sₙ bir grup oluşturur. Grup koşulları şunlardır:

1. Bileşke işlemi kapalıdır. İki permütasyonun bileşkesi yine bir permütasyondur.
2. İşlem birleşmelidir.
3. Her elemanı kendisine eşleyen birim permütasyon vardır.
4. Her permütasyonun bir tersi vardır. Ters permütasyon, eşlemenin yönünü çevirir.

Bileşke işlemi değişmeli değildir. n ≥ 3 için Sₙ değişmeli bir grup değildir.

2.6. Kombinasyon

Sıranın önemsiz olduğu seçime kombinasyon denir:

C(n, r) = n! / [ r! · (n − r)! ]

Gösterimler: C(n, r), ⁿCᵣ ve binom katsayısı biçimi.

Permütasyonla ilişkisi şudur:

C(n, r) = P(n, r) / r!

r! bölümü, aynı seçimin farklı sıralarını tek sayıma indirger.

Ayrımı belirleyen tek soru şudur: sıra sonucu değiştiriyor mu? Değiştiriyorsa permütasyon, değiştirmiyorsa kombinasyondur.

2.7. Kombinasyonun Özellikleri

C(n, 0) = C(n, n) = 1
C(n, 1) = n
C(n, r) = C(n, n−r)                     simetri
C(n, r) = C(n−1, r−1) + C(n−1, r)       Pascal kuralı
Σ C(n, r) = 2ⁿ,   r = 0..n

Simetri özelliğinin anlamı şudur. r eleman seçmek, seçilmeyecek n−r elemanı seçmekle aynıdır.

Pascal kuralı, Pascal üçgeninin kuruluş kuralıdır. Belirli bir elemanın seçilip seçilmemesine göre ayrıştırma yapılır.

Alt küme sayısının 2ⁿ olması, bütün kombinasyonların toplamından da çıkar.

Binom teoremi kombinasyonu cebire bağlar:

(x + y)ⁿ = Σ C(n, r) · xⁿ⁻ʳ · yʳ

2.8. Tekrarlı Kombinasyon

n türden r nesnenin sırasız ve tekrarlı seçimi:

C(n + r − 1, r)

Bu formül, r özdeş nesnenin n kutuya dağıtılması problemine denktir. Çubuk ve yıldız yöntemiyle türetilir.

2.9. İçerme-dışlama İlkesi

Birden çok özelliği aynı anda taşıyabilen nesneleri sayarken kesişim bölgeleri tekrar tekrar sayılabilir. İçerme-dışlama ilkesi bu tekrarları işaret değiştirerek düzeltir.

İki küme için:

|A ∪ B| = |A| + |B| − |A ∩ B|

Üç kümede ikili kesişimler çıkarılır, üçlü kesişim yeniden eklenir:

|A ∪ B ∪ C|
= |A| + |B| + |C|
− |A ∩ B| − |A ∩ C| − |B ∩ C|
+ |A ∩ B ∩ C|

Genel durumda tekli kümeler eklenir, ikili kesişimler çıkarılır, üçlü kesişimler eklenir ve işaret bu biçimde sırayla değişir.

İlkenin önemli kullanım alanlarından biri örten fonksiyonları saymaktır. Tanım kümesindeki elemanların değer kümesindeki her sınıfa en az bir kez ulaşması isteniyorsa, en az bir hedefi boş bırakan atamalar içerme-dışlama ile toplamdan çıkarılır.

Bu yöntem yalnız formül ezberi değildir. Asıl teknik, “hangi nesneler birden çok kez sayıldı?” sorusunu katmanlar halinde cevaplamaktır.

Ünite 3: Önermeler Mantığı

Bir mantıksal önermenin doğruluğu değerlendirilirken önce atomik önermeler ayrılır ve bağlaçların kapsamı parantezlerle kesinleştirilir. Sonra doğruluk tablosu veya eşdeğerlik dönüşümleri kullanılır; dönüşüm zincirinin her adımı mantıksal eşdeğerliği korumalıdır. Nicelendiriciler söz konusuysa değişkenin tanım evreni ve nicelendirici sırası açıkça belirtilir. Karşı örnek, evrensel bir iddiayı çürütmek için yeterli olabilirken birkaç olumlu örnek iddiayı kanıtlamaz.

3.1. Önerme

Doğru ya da yanlış olduğu kesin biçimde söylenebilen ifadeye önerme denir.

Doğru ya da yanlışlığına 1 ve 0 ile değer verilir. Buna doğruluk değeri denir.

Soru, emir ve ünlem cümleleri önerme değildir. Doğruluk değeri taşımayan ifadeler dışarıda kalır.

İçinde belirsiz değişken bulunan ve değişkene değer verildiğinde önermeye dönüşen ifadeye önermesel denir. "x > 3" ifadesi önermesel, "5 > 3" ifadesi önermedir.

Önermeler p, q, r gibi harflerle gösterilir.

3.2. Bileşik Önerme ve Doğruluk Tablosu

Birden çok önermenin bağlaçlarla birleştirilmesiyle bileşik önerme elde edilir.

Bileşik önermenin doğruluk değeri, bileşenlerin değerlerine bağlıdır. Bu bağımlılık doğruluk tablosuyla gösterilir.

n önerme içeren bir bileşik önermenin doğruluk tablosunda 2ⁿ satır bulunur.

3.3. Değilleme

Bir önermenin doğruluk değerini tersine çeviren işlemdir. p' ya da ¬p ile gösterilir.

p    p'
1    0
0    1

Çift değilleme özgün önermeye döner:

(p')' = p

3.4. Evetleme

"VE" bağlacıyla kurulur. p ∧ q ile gösterilir.

Yalnız her iki önerme de doğruyken doğrudur.

p  q   p∧q
1  1    1
1  0    0
0  1    0
0  0    0

3.5. Ayrıklık

"VEYA" bağlacıyla kurulur. p ∨ q ile gösterilir.

En az biri doğruyken doğrudur. Yalnız her ikisi yanlışken yanlıştır.

p  q   p∨q
1  1    1
1  0    1
0  1    1
0  0    0

Bu işlem kapsayan veya anlamındadır. Günlük dildeki "ya o ya bu" anlamı farklıdır ve dışlayan veya ile karşılanır. p ⊕ q yalnız tam olarak biri doğruyken doğrudur.

3.6. Koşullu Önerme

"eğer p ise q" biçimindeki önermedir. p ⟹ q ile gösterilir. p hipotez, q hüküm adını alır.

Yalnız hipotez doğru ve hüküm yanlışken yanlıştır.

p  q   p⟹q
1  1    1
1  0    0
0  1    1
0  0    1

Hipotez yanlışken önermenin doğru sayılması sezgiye aykırı görünür. Tanım şu ilkeye dayanır: yanlış bir varsayımdan çıkarılan hiçbir sonuç yanlış sayılamaz. Buna boş doğruluk denir.

Koşullu önerme diğer işlemlerle yazılabilir:

p ⟹ q  ≡  p' ∨ q
(p ⟹ q)'  ≡  p ∧ q'

3.7. Karşıt, Ters ve Karşıt Tersi

p ⟹ q önermesinden üç türev önerme elde edilir:

q ⟹ p       karşıt (converse)
p' ⟹ q'     ters (inverse)
q' ⟹ p'     karşıt tersi (contrapositive)

Denklik ilişkisi kesindir. Bir önerme yalnız karşıt tersine denktir:

(p ⟹ q) ≡ (q' ⟹ p')

Karşıt ile ters birbirine denktir. Özgün önermeye denk değildirler.

Bu ayrım ispat yöntemlerinin temelidir. Doğrudan ispat zorsa karşıt tersi ispatlanır. Sonuç aynıdır.

3.8. Karşılıklı Koşullu Önerme

"p ancak ve ancak q" biçimindedir. p ⟺ q ile gösterilir.

İki önermenin doğruluk değerleri aynıyken doğrudur.

p ⟺ q  ≡  (p ⟹ q) ∧ (q ⟹ p)

Matematiksel tanımlar bu biçimdedir. İki yönlü ispat gerektirir.

3.9. Denk Önermeler ve Standart Biçim

Doğruluk tabloları aynı olan önermelere denk önermeler denir. p ≡ q yazılır.

Denklik bağıntısı yansıyan, simetrik ve geçişkendir.

Önermeler cebirsel işlemlerle sadeleştirilir. Standart biçime indirgeme, karmaşık ifadeyi az sayıda bağlaçla yazmaktır.

3.10. Totoloji ve Çelişme

Bileşenlerin bütün değerlerinde doğru olan önermeye totoloji ya da özdoğruluk denir.

Bütün değerlerde yanlış olan önermeye çelişme denir.

Örnekler:

p ∨ p'          totoloji
p ∧ p'          çelişme
(p ∧ q) ⟹ p     totoloji

Bir totolojinin değili çelişmedir.

p ≡ q ile p ⟺ q totolojidir ifadeleri aynı anlama gelir. Denklik, karşılıklı koşullunun totoloji olmasıdır.

3.11. Mantık Kanunları

p ∨ p ≡ p,   p ∧ p ≡ p                      eş güçlülük
p ∨ q ≡ q ∨ p,   p ∧ q ≡ q ∧ p              değişme
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)                   birleşme
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)             dağılma
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)             dağılma
(p ∨ q)' ≡ p' ∧ q'                          De Morgan
(p ∧ q)' ≡ p' ∨ q'                          De Morgan
p ∨ 0 ≡ p,   p ∧ 1 ≡ p                      birim eleman
p ∨ 1 ≡ 1,   p ∧ 0 ≡ 0                      yutan eleman
p ∨ (p ∧ q) ≡ p                             yutulma

Bu kanunlar küme işlemlerindeki kanunlarla birebir örtüşür. ∨ birleşime, ∧ kesişime, değilleme tümleyene karşılık gelir.

İki alan da Boole cebridir. Aynı sadeleştirme aynı adımlarla yapılır.

3.12. Quine Yöntemi

Bir önermenin totoloji olup olmadığını doğruluk tablosu kurmadan sınayan yöntemdir.

Değişkenlerden birine bir değer atanır. İfade bu değere göre sadeleştirilir. İşlem, bütün değişkenler tükenene kadar sürer.

Yöntemin dayanağı yutan elemanlardır. Bir alt ifade 1 değerini aldığında, onun dahil olduğu bütün ayrıklıklar 1 olur ve incelenmez.

Değişken sayısı arttıkça kazanç büyür. Doğruluk tablosu 2ⁿ satır ister. Quine yöntemi çoğu durumda dalların erken kapanmasıyla bunun altında kalır. En kötü durumda üstel kalır.

3.13. Mantıksal Devreler

Önermeler cebri anahtarlama devrelerine doğrudan uygulanır. Anahtarın kapalı olması 1, açık olması 0 değerine karşılık gelir.

Seri bağlama VE işlemini gerçekleştirir. Akım geçmesi için iki anahtar da kapalı olmalıdır.

Paralel bağlama VEYA işlemini gerçekleştirir. Akım geçmesi için en az bir anahtarın kapalı olması yeterlidir.

Bağlantılar genelleştirilir. n anahtarın seri bağlanması n değişkenli VE, paralel bağlanması n değişkenli VEYA işlemidir.

Köprü devreleri salt seri ve paralel bileşimlere ayrılamayan yapılardır. Devre işlevi, akımın geçtiği bütün yolların ayrıklığı olarak yazılır.

Devrelerin indirgenmesi, devre fonksiyonunun mantık kanunlarıyla sadeleştirilmesidir. Doğruluk tablosu aynı kalan iki devreye denk devre denir. Sadeleştirme, daha az anahtarla aynı işlevi verir.

Bugünkü karşılığı mantık kapılarıdır. Anahtar yerine AND, OR ve NOT kapıları kullanılır. NAND ve NOR kapıları tek başına bütün Boole işlevlerini üretir; bu nedenle işlevsel olarak tamdır. Devre sadeleştirme, tümdevre tasarımında kapı sayısını ve gecikmeyi azaltmak için aynı cebirle yapılır.

Karar problemleri de bu yolla çözülür. Oylama sisteminde her üyenin oyu bir değişkendir. Kararın çıkması bir Boole fonksiyonu olarak yazılır ve devreye dönüştürülür.

3.14. Yüklemler ve Niceleyiciler

Önerme mantığında her atomik ifade doğrudan doğru ya da yanlıştır. Yüklem mantığı ise değişken içeren ifadeleri ele alır. P(x) ifadesi tek başına önerme olmak zorunda değildir; x belirli bir değer aldığında veya bir niceleyiciyle bağlandığında doğruluk değeri kazanır.

İki temel niceleyici vardır:

∀x P(x)    her x için P(x)
∃x P(x)    en az bir x için P(x)

Niceleyicinin etki ettiği kümeye evren ya da söylem alanı denir. Aynı sembolik ifade farklı evrenlerde farklı doğruluk değeri alabilir.

Niceleyicilerin değili dikkatle alınmalıdır:

¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x)

“Her kullanıcı yetkilidir” ifadesinin değili “hiçbir kullanıcı yetkili değildir” değil, “en az bir kullanıcı yetkili değildir” biçimindedir. Yazılım gereksinimlerinin ve erişim kurallarının biçimsel ifadesinde bu ayrım kritiktir.

3.15. İç İçe Niceleyiciler

Birden çok niceleyici bulunduğunda sıra genellikle anlamı değiştirir:

∀x ∃y R(x,y)
∃y ∀x R(x,y)

İlk ifade her x için ona bağlı bir y bulunabileceğini söyler. İkinci ifade ise bütün x değerleri için çalışan tek bir y bulunduğunu ileri sürer. Bu iki iddia genel olarak denk değildir.

İç içe niceleyicileri okurken üç adım güvenlidir: evreni belirlemek, niceleyicileri soldan sağa bağlamak ve her değişkenin hangi niceleyiciye bağlı olduğunu açıkça işaretlemek.

3.16. Çıkarım Kuralları ve İspat Kalıpları

Geçerli bir argümanda öncüller doğru olduğunda sonuç zorunlu olarak doğrudur. Sık kullanılan çıkarım kuralları arasında modus ponens, modus tollens, hipotetik kıyas ve ayrık kıyas bulunur.

p
p → q
∴ q

modus ponens örneğidir. Çıkarım kuralı, belirli bir konuya özgü değildir; doğruluk değerlerinin yapısından gelir.

Ayrık yapılarda kullanılan temel ispat kalıpları şunlardır:

• Doğrudan ispat: varsayımdan başlayıp sonucu türetmek.
• Karşıt ters ile ispat: p → q yerine denk olan ¬q → ¬p ifadesini göstermek.
• Çelişki ile ispat: önermenin değili varsayılıp mantıksal çelişkiye ulaşmak.
• Durumlara ayırma: olası durumları kapsayıcı ve ayrık sınıflara bölmek.
• Varlık ispatı: gerekli nesneyi kurmak ya da varlığını dolaylı göstermek.
• Teklik ispatı: iki çözüm varsayıp bunların aynı olmak zorunda olduğunu göstermek.
• Karşı örnek: evrensel bir iddiayı tek geçerli örnekle çürütmek.

Bir örneğin bir iddiayı desteklemesi ispat değildir. Buna karşılık evrensel bir iddianın yanlışlığını göstermek için tek karşı örnek yeterlidir.

3.17. Matematiksel, Kuvvetli ve Yapısal Tümevarım

Matematiksel tümevarım, doğal sayılarla indekslenen önermeler için iki aşamalıdır:

1. Başlangıç durumu doğrulanır.
2. P(k) doğru varsayıldığında P(k+1) sonucunun çıktığı gösterilir.

Bu iki adım tamamlandığında önerme başlangıç indeksinden sonraki bütün doğal sayılar için geçerlidir.

Kuvvetli tümevarımda P(k+1) ispatlanırken yalnız P(k) değil, önceki bütün durumlar P(n0), ..., P(k) doğru kabul edilebilir. Asal çarpanlara ayırma veya bir nesnenin daha küçük alt yapılara ayrıldığı problemlerde bu biçim daha doğaldır.

Yapısal tümevarım, doğal sayı yerine özyineli tanımlanmış bir yapının kuruluş kurallarını izler. Bir ağacın, mantıksal ifadenin veya sözdizim ağacının temel durumları doğrulanır; ardından yapı kurucularının özelliği koruduğu gösterilir.

Program doğruluğundaki döngü değişmezleri de aynı fikri kullanır: başlangıçta doğru olan bir özellik her yinelemede korunuyorsa döngü boyunca geçerliliğini sürdürür.

3.18. İnşa ile İspat: Varlığı Nesneyi Kurarak Göstermek

Bir varlık iddiasını ispatlamanın en doğrudan yollarından biri, koşulları sağlayan nesneyi açıkça inşa etmektir. Bu yaklaşım yalnız "vardır" sonucunu vermez; çoğu zaman aynı zamanda nesnenin nasıl üretileceğini gösteren bir algoritma da sağlar.

Örneğin şu iddiayı ele alalım:

Her çift n >= 4 için n düğümlü basit bir 3-düzenli graf vardır.

Önce zorunlu koşul görülebilir. El sıkışma lemmasına göre derece toplamı kenar sayısının iki katıdır:

sum(deg(v)) = 2|E|

3-düzenli bir grafta sol taraf 3n olur. 3n çift olmak zorunda olduğundan n de çift olmalıdır. Bu yalnız gerekliliği gösterir; varlığı henüz ispatlamaz.

Varlık için düğümleri 0,1,...,n-1 olarak bir çember üzerine yerleştirelim. Önce çevrim kenarlarını ekleyelim:

{i, (i+1) mod n}

Sonra her düğümü karşısındaki düğümle eşleyen şu kenarları ekleyelim:

{i, i+n/2}   for 0 <= i < n/2

Çevrim her düğüme iki komşu, eklenen perfect matching ise üçüncü komşuyu verir. n >= 4 olduğunda self-loop veya yinelenen kenar oluşmaz; böylece her düğümün derecesi tam 3 olur. İnşa aynı zamanda O(n) sayıda kenar üretimiyle gerçeklenebilecek bir algoritmadır.

Bu örnek, üç ispat katmanını birbirinden ayırır:

zorunlu koşul -> neden bazı n değerleri mümkün değil?
inşa          -> uygun nesne nasıl kurulur?
doğrulama     -> kurulan nesne bütün koşulları gerçekten sağlıyor mu?

Özellikle bilgisayar biliminde yapıcı ispatlar, varlık önermesini doğrudan üretim algoritmasına dönüştürebildiği için önemlidir.

3.19. İspat, Karşı Örnek ve Yapı Arasındaki İlişki

Ayrık matematikte bir önermeyi birkaç örnekte doğrulamak ispat değildir. Evrensel bir iddiayı çürütmek için tek bir karşı örnek yeterli olabilir; doğrulamak için ise tanım, çıkarım kuralı veya uygun bir ispat yöntemi gerekir. Özellikle P → Q ile karşıtı Q → P aynı önerme değildir. Buna karşılık karşıt tersi ¬Q → ¬P, ilk önerme ile mantıksal olarak denktir.

Tümevarım iki ayrı yükümlülük taşır: başlangıç durumu ve geçiş adımı. Geçişte amaç P(k) doğru varsayımından P(k+1) sonucunu çıkarmaktır; yalnız P(k+1) için örnek hesap yapmak yeterli değildir. Güçlü tümevarımda ise önceki tüm durumlar varsayım olarak kullanılabilir.

Bağıntılarda yansıma, simetri, ters simetri ve geçişme birbirinden bağımsız özelliklerdir. Eşdeğerlik bağıntısı yansımalı, simetrik ve geçişlidir; kısmi sıralama ise yansımalı, ters simetrik ve geçişlidir. Bu iki yapı benzer görünse de ürettikleri sınıflandırma farklıdır: eşdeğerlik bağıntısı kümeyi eşdeğerlik sınıflarına, kısmi sıralama ise karşılaştırılabilirlik yapısına dönüştürür.

Graf sorularında yol, iz, çevrim, bağlılık ve derece kavramları ayrılmalıdır. Bir grafın bütün düğümlerinin derecesini topladığınızda her kenar iki uçta sayıldığı için sonuç 2|E| olur. Bu el sıkışma lemması, tek dereceli düğüm sayısının neden çift olmak zorunda olduğunu da açıklar.

Sayma problemlerinde önce sıranın önemli olup olmadığı, tekrarın izinli olup olmadığı ve seçimlerin bağımsız olup olmadığı sorulmalıdır. Permütasyon ve kombinasyon formüllerini ezberlemek yerine bu üç soruya cevap vermek doğru modeli seçmeyi kolaylaştırır.

Ünite 4: Bağıntı

4.1. Bağıntı Kavramı

A × B kartezyen çarpımının her alt kümesine A'dan B'ye bir bağıntı denir.

β bir bağıntı ve (a, b) ∈ β ise a, b ile bağıntılıdır denir ve a β b yazılır.

A × A alt kümelerine A üzerinde bağıntı denir. Buradaki inceleme esas olarak bu durum üzerindedir.

n elemanlı bir küme üzerinde tanımlanabilecek bağıntı sayısı 2^(n²) olur. A × A kümesinin n² elemanı vardır ve her alt kümesi bir bağıntıdır.

Bağıntının tanım kümesi, birinci bileşenlerin kümesidir. Görüntü kümesi, ikinci bileşenlerin kümesidir.

4.2. Gösterim Biçimleri

Liste: sıralı ikililer yazılır.

Ok diyagramı: elemanlar noktalarla, ilişkiler oklarla gösterilir.

Koordinat diyagramı: sıralı ikililer düzlemde nokta olarak işaretlenir.

Matris: satır ve sütunlar elemanlara karşılık gelir. İlişki varsa 1, yoksa 0 yazılır.

Yönlü graf: elemanlar düğüm, ilişkiler yönlü kenardır.

Son iki gösterim bilgisayarda kullanılan biçimlerdir.

4.3. Ters Bağıntı

Sıralı ikililerin bileşenleri yer değiştirilerek elde edilir:

β⁻¹ = { (b, a) : (a, b) ∈ β }

Ters bağıntının tersi kendisidir. Matris gösteriminde ters bağıntı, matrisin devriğidir.

4.4. Yansıyan Bağıntı

Her elemanın kendisiyle bağıntılı olması koşuludur:

∀a ∈ A :  (a, a) ∈ β

Matriste köşegenin tümü 1 olur. Yönlü grafta her düğümde bir ilmek bulunur.

Hiçbir elemanın kendisiyle bağıntılı olmadığı durumda bağıntı yansımazdır. Yansıyan olmamak ile yansımaz olmak farklı kavramlardır.

4.5. Simetrik Bağıntı

(a, b) ∈ β  ⟹  (b, a) ∈ β

Matris simetriktir. Grafta her ok çift yönlüdür.

4.6. Ters Simetrik Bağıntı

(a, b) ∈ β  ve  (b, a) ∈ β  ⟹  a = b

Farklı iki eleman arasında karşılıklı ilişki bulunmaz.

Simetrik ile ters simetrik birbirinin karşıtı değildir. Bir bağıntı ikisi birden olabilir. Köşegen bağıntı bu türdendir. Hiçbiri de olmayabilir.

4.7. Geçişken Bağıntı

(a, b) ∈ β  ve  (b, c) ∈ β  ⟹  (a, c) ∈ β

Grafta iki adımda ulaşılan her düğüme doğrudan ok bulunmalıdır.

Geçişkenlik en sık atlanan koşuldur. Sınamada bütün ikili zincirler taranmalıdır.

4.8. Denklik Bağıntısı

Yansıyan, simetrik ve geçişken bağıntıya denklik bağıntısı denir.

Üç koşul birlikte aranır. Biri sağlanmazsa bağıntı denklik bağıntısı değildir.

Tipik örnekler: eşitlik, doğruların paralelliği, tam sayılarda mod n denkliği.

4.9. Denklik Sınıfları ve Parçalanma

a elemanına denk olan bütün elemanların kümesine denklik sınıfı denir:

[a] = { x ∈ A : x β a }

Temel özellikler:

1. Her eleman kendi sınıfındadır. Hiçbir sınıf boş değildir.
2. İki denklik sınıfı ya özdeştir ya da ayrıktır. Kısmen örtüşme olamaz.
3. Sınıfların birleşimi kümenin tamamını verir.

Bu üç özellik şu anlama gelir: her denklik bağıntısı kümeyi bir parçalanmaya ayırır. Karşıtı da doğrudur. Her parçalanma bir denklik bağıntısı tanımlar.

Denklik sınıflarının kümesine bölüm kümesi denir. A/β ile gösterilir.

Mod n denkliğinde tam sayılar n adet sınıfa ayrılır. Kalan sınıfları bu parçalanmanın elemanlarıdır.

4.10. Sıralama Bağıntıları

Yansıyan, ters simetrik ve geçişken bağıntıya kısmi sıralama bağıntısı denir.

Denklik bağıntısından tek farkı simetri koşulunun yerine ters simetrinin gelmesidir. Bu tek değişiklik yapıyı bütünüyle değiştirir. Denklik ayırır, sıralama düzenler.

Örnekler: sayılarda ≤ bağıntısı, kümelerde ⊆ bağıntısı, tam sayılarda bölünebilme.

Kısmi sıralamada her eleman çifti karşılaştırılabilir olmak zorunda değildir. Alt küme bağıntısında ayrık iki küme karşılaştırılamaz.

Her eleman çifti karşılaştırılabiliyorsa bağıntı tam sıralamadır:

∀a, b :  a β b  veya  b β a

Sayılarda ≤ tam sıralamadır. Kümelerde ⊆ genelde değildir.

4.11. Hasse Diyagramı ve Kısmi Sıralamanın Yapısı

Sonlu bir kısmi sıralama, bütün geçişken kenarları çizmek yerine Hasse diyagramı ile daha okunabilir gösterilebilir. Yansıyan ilmekler gösterilmez; geçişkenlik nedeniyle zorunlu olan kenarlar da çıkarılır. Daha büyük elemanlar geleneksel olarak daha yukarı yerleştirilir.

Bir kısmi sıralı kümede minimal eleman ile en küçük eleman aynı kavram değildir. Minimal elemanın altında başka eleman yoktur; en küçük eleman ise bütün elemanlardan küçük veya onlara eşittir. Birden çok minimal eleman olabilir, fakat en küçük eleman varsa tektir. Maksimal ve en büyük ayrımı da simetriktir.

Bir alt kümenin bütün elemanlarından büyük olan elemanlar üst sınır, küçük olanlar alt sınırdır. Bunların en küçüğü en küçük üst sınır, en büyüğü en büyük alt sınır olarak adlandırılır. Her iki işlemin uygun eleman çiftleri için var olduğu kısmi sıralı yapılar kafes düşüncesine açılır.

Bu kavramlar bağımlılık çözümleme, sürüm sıralaması ve öncelik ilişkileri gibi problemlerde “tek bir küresel sıra” varsaymadan düzen kurmayı sağlar.

4.12. Bağıntı Matrisi

Bağıntı, 0 ve 1 değerlerinden oluşan kare matrisle temsil edilir.

Özellikler matris üzerinden okunur:

• Yansıyan: köşegen tümüyle 1.
• Simetrik: matris devriğine eşit.
• Ters simetrik: köşegen dışında karşılıklı iki konum birlikte 1 değil.
• Geçişken: M² matrisinde 1 olan her konum M matrisinde de 1.

Bileşke bağıntının matrisi, Boole matris çarpımıyla bulunur. Çarpma ∧, toplama ∨ işlemine karşılık gelir.

4.13. Kapanışlar

Bir bağıntıya, istenen özelliği sağlaması için eklenmesi gereken en az sayıda ikili eklenerek kapanış elde edilir.

Yansıyan kapanış: eksik olan köşegen ikilileri eklenir.

r(β) = β ∪ Δ

Simetrik kapanış: her ikilinin tersi eklenir.

s(β) = β ∪ β⁻¹

Geçişken kapanış: zincirle ulaşılabilen bütün ikililer eklenir.

t(β) = β ∪ β² ∪ β³ ∪ ... ∪ βⁿ

n, küme eleman sayısıdır. Daha uzun zincir yeni ikili üretmez, çünkü her yol en çok n düğüm içerir.

Kapanış, özgün bağıntıyı içeren ve istenen özelliği sağlayan en küçük bağıntıdır. Fazla ekleme yapılırsa kapanış olmaz.

4.14. Warshall Algoritması

Geçişken kapanışı matris üzerinde hesaplayan yöntemdir. Ardışık matris çarpımından belirgin biçimde hızlıdır.

Fikir şudur. Ara düğümler sırayla devreye alınır. k. adımda, yalnız ilk k düğümü ara nokta olarak kullanan yollar hesaba katılır.

FOR k = 1 TO n
  FOR i = 1 TO n
    FOR j = 1 TO n
      M[i][j] = M[i][j] OR (M[i][k] AND M[k][j])

Üç iç içe döngü çalışır. Karmaşıklık Θ(n³) düzeyindedir.

Döngü sırası önemlidir. Ara düğüm döngüsü en dışta olmalıdır. Sıra değiştirilirse algoritma yanlış sonuç üretir.

Aynı yapı, ağırlıklı graflarda en kısa yol matrisini hesaplar. Boole işlemleri toplama ve enküçük alma işlemleriyle değiştirilir.

Ünite 5: Fonksiyonlar ve İşlemler

5.1. Fonksiyon

A kümesinin her elemanını B kümesinin bir ve yalnız bir elemanına eşleyen bağıntıya fonksiyon denir.

Fonksiyon, özel bir bağıntıdır. İki ek koşul taşır:

1. A kümesinin her elemanı eşlenmiş olmalıdır.
2. Hiçbir eleman birden çok elemanla eşlenmemelidir.

Üçüncü koşul yoktur. B kümesinin bir elemanına A kümesinin birden çok elemanı eşlenebilir.

A tanım kümesi, B değer kümesidir. Görüntülerin kümesine görüntü kümesi denir.

5.2. Fonksiyon Türleri

İçine fonksiyon: görüntü kümesi, değer kümesinin gerçek alt kümesidir.

Örten fonksiyon: görüntü kümesi değer kümesine eşittir. B kümesinde açıkta eleman kalmaz.

Bire bir fonksiyon: farklı elemanların görüntüleri farklıdır.

f(x₁) = f(x₂)  ⟹  x₁ = x₂

Bire bir örten fonksiyon: iki koşulu birlikte sağlar. Yalnız bu fonksiyonların tersi vardır.

Birim fonksiyon: her elemanı kendisine eşler.

Sabit fonksiyon: bütün elemanları tek bir elemana eşler.

Sonlu kümelerde eleman sayıları belirleyicidir. |A| > |B| ise bire bir fonksiyon yoktur. Bu, güvercin yuvası ilkesinin fonksiyon diliyle ifadesidir. |A| < |B| ise örten fonksiyon yoktur. |A| = |B| ise bire birlik ile örtenlik birbirine denktir.

5.3. Ters Fonksiyon

f bire bir ve örten ise ters fonksiyon tanımlıdır:

f⁻¹(y) = x  ⟺  f(x) = y

Ters fonksiyonun tanım kümesi f'nin değer kümesidir.

Bağıntı olarak her fonksiyonun tersi vardır. Bu ters bir fonksiyon olmayabilir.

5.4. Bileşke Fonksiyon

(g ∘ f)(x) = g(f(x))

Tanımlı olması için f'nin görüntü kümesi g'nin tanım kümesinde bulunmalıdır.

Özellikler:

• Değişme özelliği yoktur. g ∘ f ile f ∘ g genelde farklıdır.
• Birleşme özelliği vardır: (h ∘ g) ∘ f = h ∘ (g ∘ f).
• Birim fonksiyon etkisizdir: f ∘ I = I ∘ f = f.
• Ters fonksiyonla bileşke birim fonksiyon verir: f ∘ f⁻¹ = I.

Bileşkenin tersi, terslerin ters sıradaki bileşkesidir:

(g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹

Sıranın tersine dönmesi tanımın doğrudan sonucudur. En sık yapılan hata sırayı korumaktır.

İki bire bir fonksiyonun bileşkesi bire birdir. İki örten fonksiyonun bileşkesi örtendir.

5.5. İkili İşlem

A × A kümesinden A kümesine tanımlı fonksiyona ikili işlem denir.

Tanım gereği işlem sonucu yine A kümesindedir. Bu, kapalılığın tanıma gömülü olması demektir.

Tek bir elemana uygulanan işleme birli işlem denir. Tümleyen ve değilleme bu türdendir.

Sonlu kümelerde işlem, işlem tablosuyla verilir.

5.6. İşlemin Özellikleri

Kapalılık: her a, b ∈ A için a * b ∈ A olmalıdır. İşlem tablosunda kümeye ait olmayan eleman görünmemelidir.

Değişme: a b = b a. İşlem tablosu köşegene göre simetriktir.

Birleşme: (a b) c = a (b c).

Birim eleman: her a için a e = e a = a sağlayan e elemanıdır. Varsa tektir. İşlem tablosunda satırı ve sütunu başlık sırasını yineler.

Ters eleman: a * a⁻¹ = e sağlayan elemandır. Birim eleman yoksa terslikten söz edilemez. İşlem birleşmeli ise ters tektir.

Dağılma: iki işlem arasında tanımlıdır.

a * (b ∘ c) = (a * b) ∘ (a * c)

Sol ve sağ dağılma ayrı ayrı incelenir. İşlem değişmeli değilse ikisi farklı olabilir.

Bu özellikler cebirsel yapıları tanımlar. Kapalı, birleşmeli, birim elemanlı ve her elemanı tersinir olan yapıya grup denir. Grup ayrıca değişmeli ise değişmeli grup adını alır.

Ünite 6: Graf Teorisi

Bir graf probleminde önce düğüm ve kenarların neyi temsil ettiği, grafın yönlü ve ağırlıklı olup olmadığı belirlenir. Erişilebilirlik için dolaşma yöntemi, en kısa yol için ağırlık koşulları, minimum kapsayan ağaç için ise bağlanırlık ve ağırlık yapısı incelenir. Negatif kenarlar içeren bir probleme negatif olmayan ağırlık varsayan bir yöntem doğrudan uygulanmamalıdır. Çözüm, tanımlanan graf üzerinde ölçülerek; farklı bir modelin sonucuyla karıştırılmadan doğrulanır.

6.1. Königsberg Köprüleri Problemi

Graf teorisi somut bir problemle doğdu. Königsberg şehrinde yedi köprü, nehrin ayırdığı dört kara parçasını birleştiriyordu. Soru şuydu: her köprüden yalnız bir kez geçerek bütün köprüler dolaşılabilir mi?

Euler problemi soyutladı. Kara parçaları düğüm, köprüler kenar olarak alındı. Şehrin geometrisi silindi; yalnız bağlantı yapısı kaldı.

Sonuç şudur. Her kenardan bir kez geçen kapalı bir yol için bütün düğümlerin derecesi çift olmalıdır. Yol kapalı olmayacaksa tam iki düğümün derecesi tek olabilir; başlangıç ve bitiş bu düğümlerdir. Tek dereceli düğüm sayısı ikiden fazlaysa çizim yapılamaz.

Königsberg'de dört düğümün de derecesi tektir. Problem çözümsüzdür.

6.2. Temel Terimler

Graf, düğümler kümesi ile kenarlar kümesinden oluşan yapıdır. G = (V, E) ile gösterilir.

Düğüm (köşe, vertex) grafın noktalarıdır.

Kenar iki düğümü birleştiren bağdır. Uç noktaları aynı olan kenara ilmek denir. Aynı iki düğümü birleştiren birden çok kenar varsa bunlara paralel kenar denir.

İlmek ve paralel kenar içermeyen grafa basit graf denir.

Derece, bir düğüme bağlı kenar sayısıdır. İlmek dereceyi iki artırır.

El sıkışma teoremi: derecelerin toplamı, kenar sayısının iki katıdır.

Σ deg(v) = 2·|E|

Doğrudan sonucu şudur: tek dereceli düğüm sayısı her zaman çifttir.

Her düğümü diğer bütün düğümlere bağlı olan grafa tam graf denir. Kₙ ile gösterilir ve kenar sayısı C(n, 2) olur.

6.3. Yörünge, Zincir ve Devre

Yürüyüş, ardışık kenarlardan oluşan dizidir.

Zincir kenarların tekrar etmediği yürüyüştür.

Yol düğümlerin de tekrar etmediği zincirdir.

Başlangıç ve bitiş düğümü aynı olan kapalı yürüyüşe devre denir.

Euler devresi her kenardan tam bir kez geçen kapalı devredir. Varlık koşulu bağlantılılık ve bütün derecelerin çift olmasıdır.

Hamilton devresi her düğümden tam bir kez geçen kapalı devredir. Euler koşulu gibi basit ve genel bir varlık ölçütü yoktur. Hamilton devresi bulma problemi NP-tam sınıfındadır.

İki kavram karıştırılmamalıdır. Euler kenar üzerinden, Hamilton düğüm üzerinden tanımlıdır.

6.4. Bağlantılılık ve Alt Graflar

Her düğüm çifti arasında bir yol varsa graf bağlantılıdır.

Bağlantılı olmayan graf, bağlantılı bileşenlere ayrılır. Her bileşen kendi içinde bağlantılıdır ve bileşenler arasında kenar yoktur.

Düğüm ve kenar kümeleri, özgün grafın alt kümesi olan grafa alt graf denir.

Silindiğinde bileşen sayısını artıran kenara köprü, düğüme kesim noktası denir. Ağ güvenilirliği analizinde bu iki kavram tek arıza noktalarını gösterir.

6.5. Ağaçlar

Devre içermeyen bağlantılı grafa ağaç denir.

Denk tanımlar şunlardır:

1. Devresiz ve bağlantılıdır.
2. Her düğüm çifti arasında tam bir yol vardır.
3. Bağlantılıdır ve kenar sayısı n − 1'dir.
4. Devresizdir ve kenar sayısı n − 1'dir.
5. Herhangi bir kenar eklenirse devre oluşur; herhangi bir kenar silinirse bağlantı kopar.

n düğümlü ağacın kenar sayısı her zaman n − 1'dir. Ağaç, bağlantılı kalabilen en seyrek yapıdır.

Bağlantılı grafın, bütün düğümleri içeren ağaç alt grafına kapsayan ağaç denir. Her bağlantılı grafın en az bir kapsayan ağacı vardır.

Derecesi 1 olan düğümlere yaprak denir. Her ağaçta en az iki yaprak bulunur.

6.6. Ağaçların Eşdeğer Karakterizasyonları

Sonlu, yönsüz bir graf için ağaç kavramı birden fazla eşdeğer biçimde tanınabilir. n düğümlü bir graf için aşağıdaki yapılar aynı ağacı farklı yönden tarif eder:

• graf bağlantılıdır ve devre içermez,
• graf bağlantılıdır ve tam n-1 kenarı vardır,
• graf devresizdir ve tam n-1 kenarı vardır,
• her iki düğüm arasında tam bir basit yol vardır,
• herhangi bir kenar silinirse bağlantılılık bozulur,
• yeni bir kenar eklendiğinde tam bir devre oluşur.

Bu eşdeğerlikler yalnız teori değildir. Bir veri yapısının gerçekten ağaç olup olmadığını doğrularken kullanılabilecek farklı değişmezler verir. Bir temsil için kenar sayısını, başka bir temsil için bağlantılılık ve çevrimsizlik koşullarını kontrol etmek daha ucuz olabilir.

6.7. Yönlendirilmiş Graflar

Kenarların yön taşıdığı grafa yönlü graf denir.

Derece ikiye ayrılır. Düğüme gelen kenar sayısı iç derece, çıkan kenar sayısı dış derecedir. İki toplam birbirine ve kenar sayısına eşittir.

Bağlantılılık iki düzeyde tanımlanır. Her düğümden her düğüme yönlere uyularak gidilebiliyorsa graf güçlü bağlantılıdır. Yönler yok sayıldığında bağlantılı ise zayıf bağlantılıdır.

Yönlü ve devresiz graflar iş sıralama problemlerinde kullanılır. Topolojik sıralama bu yapıda tanımlıdır.

Bağıntılar yönlü graflarla temsil edilir. Yansıyanlık ilmek, simetri çift yönlü kenar, geçişkenlik kısayol kenarı olarak görünür.

6.8. Yapısal Ağ Analizi: Çekirdek, Kesim ve Yönlü Bileşenler

Bir düğümün derecesi yerel bağlantı sayısını verir; ağın daha içteki yoğun yapısında bulunup bulunmadığını tek başına göstermez. Bu ayrım için k-core kullanılır. Bir grafın k-coreu, içindeki her düğümün yine bu alt graf içinde en az k komşuya sahip olduğu en büyük alt graftır. Bir düğümün ait olabildiği en büyük k değeri core number olarak adlandırılır.

Basit fikir yinelemeli elemedir:

1. derecesi k'den küçük düğümleri çıkar
2. komşuların derecelerini güncelle
3. yeni oluşan düşük dereceli düğümleri çıkar
4. değişiklik kalmayana kadar sürdür

Verimli gerçeklenim uygun derece kovalarıyla O(V + E) zamanda yapılabilir. Yüksek core number, düğümün yoğun bağlı bir alt yapının içinde bulunduğunu gösterir; tek başına liderlik, önem veya nedensel rol kanıtı değildir. Minimum dereceye dayalı bu çekirdek yaklaşımın klasik kaynaklarından biri Stephen B. Seidman'ın 1983 tarihli Network Structure and Minimum Degree çalışmasıdır: https://doi.org/10.1016/0378-8733(83)90028-X

Köprü ve kesim noktası kavramları da yalnız tanımsal değildir. Derinlik öncelikli aramada her düğüm için keşif zamanı disc[v] ve alt ağaçtan geri erişilebilen en erken ata zamanı low[v] tutulduğunda bir ağaç kenarı (u,v) için:

low[v] > disc[u]

koşulu kenarın köprü olduğunu gösterir. Kök olmayan bir u düğümü için bir çocuk v üzerinde:

low[v] >= disc[u]

olması, uygun koşullarda u düğümünün kesim noktası olduğunu gösterir. DFS tabanlı düşük-bağ (low-link) yaklaşımı bağlantılı bileşenlerle birlikte O(V + E) sınıfında hesaplanabilir. Robert Tarjan'ın 1972 tarihli çalışması DFS'nin güçlü bağlantılı ve iki-bağlantılı yapıların doğrusal zamanda çözümündeki temel kaynaklardan biridir: https://doi.org/10.1137/0201010

Yönlü graflarda zayıf bağlantılı bileşen (WCC) ile güçlü bağlantılı bileşen (SCC) ayrımı özellikle veri kalitesiyle birlikte düşünülmelidir. WCC için yönler yok sayılır. SCC'de ise her düğümden diğerine yönlere uyan bir yol gerekir. Bir kenarın yönü bilinmiyorsa onu iki yönlü kabul etmek yeni bilgi üretmek anlamına gelir; bu nedenle eksik yön bilgisinin olduğu veri kümelerinde WCC ve SCC aynı kanıt düzeyinde yorumlanmamalıdır.

Yönlü ağlarda başka bir ölçü PageRanktir. En yalın biçimde:

PR(v) = (1-d)/N + d * sum(PR(u) / outdeg(u))
                         u -> v

olarak yazılır. d sönüm katsayısıdır. Çıkışı olmayan düğümlerin olasılık kütlesi ayrıca ele alınır. PageRank bir düğümün yalnız kaç bağlantı aldığına değil, bağlantı aldığı düğümlerin kendi yapısal ağırlığına da bağlıdır. Bununla birlikte yüksek PageRank'i bağlamdan bağımsız "önem" olarak yorumlamak matematiksel ölçüye taşımadığı bir anlam yükler. Yöntemin büyük ölçekli Web bağlamındaki klasik açıklaması Brin ve Page'in 1998 tarihli çalışmasındadır: https://doi.org/10.1016/S0169-7552(98)00110-X

Klasik yol problemi yalnız düğüm ve kenar sırasını kullanır. Olayların zaman taşıdığı bir ağda ise zamana saygılı yol için kenarların zamanları da artmalıdır:

v0 --t1--> v1 --t2--> v2 ... --tk--> vk

t1 <= t2 <= ... <= tk

Uygulamaya göre ardışık olaylar arasına maksimum süre veya bütün yol için maksimum zaman açıklığı konabilir. Böylece yapısal olarak var olan fakat olay sırası nedeniyle fiilen gerçekleşemeyecek bir zincir ile zaman içinde mümkün olan zincir ayrılır. Bu ayrım, statik grafı olay verisine uygularken temsil seçiminin sonucu nasıl değiştirdiğinin iyi bir örneğidir.

6.9. Graf Eşbiçimliliği ve Yapısal Değişmezler

İki grafın düğüm adlarının farklı olması, yapılarının farklı olduğu anlamına gelmez. Düğümler arasında komşuluğu koruyan bire bir ve örten bir eşleme varsa graflar eşbiçimlidir.

Eşbiçimlilikte düğüm etiketleri değil yapı önemlidir. Derece çokluğu, bileşen sayısı, devre uzunlukları ve köprü sayısı gibi nicelikler eşbiçimlilik altında değişmez. Bu niceliklerden biri farklıysa graflar kesinlikle eşbiçimli değildir. Buna karşılık bütün basit değişmezlerin eşit çıkması tek başına eşbiçimliliği kanıtlamaz.

Bu ayrım, veri sistemlerinde kimlik ile yapı arasındaki farkı gösterir: düğüm numaraları değişebilir, fakat bağlantı örüntüsü aynı kalabilir.

6.10. Düzlemsel Graflar ve Euler Bağıntısı

Bir graf, kenarlar yalnız ortak uç noktalarında kesişecek biçimde düzlemde çizilebiliyorsa düzlemseldir. Belirli bir çizimde kenarların kesişmesi, grafın düzlemsel olmadığını tek başına göstermez; başka bir çizim kesişmeleri kaldırabilir.

Bağlantılı düzlemsel bir grafın belirli bir düzlemsel çiziminde düğüm, kenar ve yüz sayıları arasında:

V − E + F = 2

bağıntısı vardır.

Bu eşitlik planarlık için güçlü bir gerek koşul üretir. Basit, bağlantılı ve V ≥ 3 olan düzlemsel graflarda:

E ≤ 3V − 6

olmalıdır. Üçgen içermeyen düzlemsel graflarda sınır daha da sıkıdır:

E ≤ 2V − 4

Bu eşitsizliklerin bozulması, grafın düzlemsel olamayacağını gösterir. Sağlanmaları ise tek başına yeterli değildir.

6.11. Ağırlıklı Graflar ve Minimum Kapsayan Ağaç

Kenarlara sayısal değer atanmışsa graf ağırlıklıdır. Ağırlık uzaklık, maliyet ya da süre olabilir.

Minimum kapsayan ağaç problemi: bütün düğümleri bağlayan ve toplam ağırlığı en küçük olan ağacı bulmaktır.

Kruskal algoritması kenar tabanlıdır:

1. Kenarlar ağırlığa göre artan sırada sıralanır.
2. En küçük ağırlıklı kenar seçilir.
3. Seçilen kenar devre oluşturmuyorsa ağaca eklenir, oluşturuyorsa atlanır.
4. n − 1 kenar seçilene kadar üçüncü adım yinelenir.

Algoritma açgözlüdür. Her adımda yerel en iyi seçim yapılır ve sonuç küresel en iyidir. Bu, açgözlü yaklaşımın doğru sonuç verdiği az sayıdaki problemden biridir.

Devre denetimi ayrık kümeler yapısıyla yapılır. Sıralama baskın maliyettir; karmaşıklık O(E log E) düzeyindedir.

Prim algoritması düğüm tabanlı alternatiftir. Tek bir düğümden başlar ve ağacı her adımda en ucuz kenarla büyütür.

6.12. Matrisler ve Graflar

Komşuluk matrisi, düğüm sayısı kadar satır ve sütundan oluşur. i ile j arasında kenar varsa 1, yoksa 0 yazılır. Yönsüz grafta matris simetriktir. Ağırlıklı grafta 1 yerine ağırlık yazılır.

Matrisin kuvvetleri yol sayısını verir. Aᵏ matrisinin (i, j) elemanı, i düğümünden j düğümüne giden k uzunluklu yürüyüş sayısıdır.

En kısa uzaklık matrisi, her düğüm çifti arasındaki en kısa yol uzunluğunu tutar. Floyd-Warshall algoritmasıyla Θ(n³) sürede hesaplanır. Yapı, geçişken kapanış algoritmasıyla aynıdır; Boole işlemleri toplama ve enküçük alma ile değiştirilir.

Komşuluk listesi ikinci gösterim biçimidir. Her düğüm için komşularının listesi tutulur.

Seçim graf yoğunluğuna bağlıdır. Komşuluk matrisi Θ(n²) yer kaplar ve kenar sorgusunu sabit sürede yanıtlar. Komşuluk listesi Θ(n + m) yer kaplar ve seyrek graflarda belirgin biçimde ekonomiktir. Gerçek uygulamalardaki grafların çoğu seyrektir.

6.13. Graf Modelinden İletişim İlişkisi Analizine

Graf kuramı, iletişim kayıtları gibi olay verilerine uygulandığında ilk karar algoritma değil temsil modelidir. Düğümün kişi, cihaz veya başka bir tanımlayıcıyı; kenarın tekil bir olayı mı yoksa belirli bir zaman aralığında toplanmış ilişkiyi mi temsil ettiği açıkça tanımlanmalıdır. Tekil olayları ayrı kenarlar olarak tutan çoklu graf ile A-B arasındaki tüm olayları tek ağırlıklı kenarda birleştiren ilişki grafı aynı bilgiyi taşımaz.

Bu ayrım yön, ağırlık ve zaman için de geçerlidir. Arama/aranma gibi yön bilgisi mevcutsa yönlü graf kullanılabilir; yön bilinmiyorsa kenarı iki yönlü varsaymak gözlenmemiş bilgi üretir. Kenar ağırlığı olay sayısı, toplam süre veya başka bir ölçü olabilir; farklı tanımlar aynı merkezilik değerini farklılaştırır. Zaman damgalı olaylarda yapısal bir yolun bulunması, olayların kronolojik sırada gerçekleşebildiği anlamına gelmez; zamana saygılı yol ayrıca zaman kısıtını taşır.

Merkezilik, bileşen, köprü, kesim noktası veya topluluk ölçüleri bu nedenle yapısal betimleyicidir; tek başına hukuki, sosyal veya nedensel önem kanıtı değildir. Sonucun denetlenebilir olması için graf kenarından kaynak kayda geri izlenebilirlik korunmalı, kapsam dışında kalan kayıtların ve bilinmeyen yön/zaman bilgisinin sonucu nasıl sınırladığı belirtilmelidir.

Bu modelleme ilkelerinin kamuya açık bir uygulama bağlamı HTS Analizi dersinde; olay grafı ile toplulaştırılmış ilişki grafının ayrımı, zamansal ilişkiler, merkezilik ve kaynak kayda geri izlenebilirlik üzerinden ele alınır. İlgili HTS/CDR Analyzer for Java araştırma yazılımı da Zenodo'da kalıcı bir kayıtla yayımlanmıştır (doi:10.5281/zenodo.22685947). Bu köprü, graf kuramındaki soyut yapıların gerçek veri modelleme kararlarına nasıl dönüştüğünü gösterir; herhangi bir düğüm veya ilişkinin anlamına ilişkin otomatik bir hüküm üretmez.

6.14. Gantt Diyagramları ve Faaliyet Ağları

Proje planlaması graf teorisinin doğrudan uygulama alanıdır.

Gantt diyagramı, faaliyetleri zaman ekseni üzerinde yatay çubuklarla gösterir. Sürelerin ve örtüşmelerin okunması kolaydır.

Faaliyet ağı öncelik ilişkilerini yönlü grafla gösterir. Bir faaliyetin başlaması için tamamlanması gereken faaliyetler kenarlarla bağlanır.

İki gösterim kullanılır. Faaliyet kenarda gösterilirse ok üzerinde faaliyet diyagramı, düğümde gösterilirse bağda faaliyet diyagramı elde edilir.

Kukla faaliyet, süresi sıfır olan yapay kenardır. İki amaçla kullanılır. Öncelik ilişkisini doğru kurmak ve iki faaliyetin aynı düğüm çiftini paylaşmasını önlemek.

En uzun süreli yola kritik yol denir. Bu yol üzerindeki faaliyetlerde gecikme projeyi doğrudan geciktirir. Diğer faaliyetlerin bolluk süresi vardır.

Kritik yol, devresiz yönlü grafta en uzun yol problemidir. Topolojik sırada tek geçişle hesaplanır.

6.15. Rekürans Bağıntıları ve Graf Renklendirme

Ayrık yapıların önemli bir bölümü "bir sonraki değerin önceki değerlere bağlı olması" veya "komşu nesnelerin aynı kaynağı paylaşamaması" biçiminde ortaya çıkar. Rekürans bağıntıları ve graf renklendirme bu iki problem sınıfını ortak ayrık matematik diliyle ifade eder.

6.15.1. Rekürans Bağıntıları

Bir dizi terimi önceki terimlerle tanımlanıyorsa rekürans bağıntısı elde edilir:

a_n = 2 a_(n-1) + 1

Başlangıç koşulu verilmeden bu bağıntı tek bir dizi tanımlamaz. Örneğin a_0 = 0 ile:

0, 1, 3, 7, 15, ...

dizisi oluşur.

Birinci mertebe doğrusal bağıntılar cebirsel olarak çözülebilir. Böl-ve-yönet algoritmalarında ise:

T(n) = 2T(n/2) + n

gibi reküranslar, algoritmanın problem boyutu küçülürken yaptığı toplam işi modeller.

Rekürans çözümünde amaç yalnız kapalı form bulmak değildir. Monotonluk, üst-alt sınır ve asimptotik büyüme de çoğu algoritmik soruda yeterli bilgiyi verir.

6.15.2. Graf Renklendirme

Graf renklendirmede komşu düğümlere aynı renk verilmez. Kullanılan minimum renk sayısı grafın kromatik sayısıdır.

A --- B
|     |
D --- C

Bu çevrim iki renkle boyanabilir. Tek uzunluklu çevrim ise iki renkle boyanamaz.

Bipartite graf tam olarak iki renklenebilir graf sınıfıdır; BFS/DFS sırasında düğümlere dönüşümlü renk atayarak test edilebilir.

6.15.3. Renklendirmenin Mühendislik Karşılıkları

"Renk" fiziksel renk olmak zorunda değildir. Aynı kaynağı eş zamanlı kullanamayan işler için:

• sınav/iş zamanlama,
• radyo frekansı atama,
• register allocation,
• çakışan görevların kaynak tahsisi

renklendirme problemi olarak modellenebilir.

Buradaki önemli ayrım model ile çözüm yöntemidir. Problemi grafa dönüştürmek doğru soyutlamayı sağlar; optimum renklendirmeyi bulmanın hesaplama maliyeti ise ayrı konudur.

Rekürans ve renklendirme birlikte şu ortak ilkeyi gösterir: ayrık matematik, programın kendisinden önce problemin yapısını görünür hâle getirir.

6.16. Klik, Bağımsız Küme, Düzenlilik ve Hipergraf

Grafın yerel yoğunluğu ve seyrekliği iki tamamlayıcı kavramla okunabilir. Bir düğüm kümesi içindeki her farklı düğüm çifti birbirine komşuysa bu küme klik; hiçbir farklı düğüm çifti komşu değilse bağımsız küme oluşturur.

Tümleyen graf bu iki kavram arasında doğrudan bir eşdeğerlik kurar:

S, G içinde klik
    <=>
S, complement(G) içinde bağımsız küme

Burada maksimal ile maksimum aynı değildir. Maksimal klik, başka düğüm eklenerek büyütülemeyen kliktir; maksimum klik ise bütün klikler arasında en büyük kardinaliteye sahip olandır. Aynı ayrım bağımsız kümeler için de geçerlidir. Yerel olarak büyütülemeyen bir çözümün küresel optimum olduğu sonucu çıkarılamaz.

Bir graf k-düzenli ise her düğümün derecesi k değerindedir. El sıkışma lemması hemen şu zorunlu koşulu verir:

k * |V| = 2|E|

Dolayısıyla k|V| çift olmalıdır. Bu basit parite testi, bazı düzenli graf iddialarını daha inşa aşamasına geçmeden elemek için kullanılabilir.

Hipergraf, sıradan grafın ikili ilişki varsayımını genişletir. Bir graf kenarı iki düğümü bağlarken hipergrafta bir hiperkenar herhangi sayıda düğümü aynı ilişki içinde tutabilir:

G = (V, E),       e in E -> |e| = 2
H = (V, E_hyper), e in E_hyper -> e is a subset of V

Üç veya daha fazla varlığın tek bir olay, işlem ya da grup içinde birlikte bulunması doğal olarak hipergrafla temsil edilebilir. Hipergrafı bütün düğüm çiftlerini birbirine bağlayan sıradan grafa projekte etmek mümkündür; fakat bu dönüşüm "hangi düğümlerin aynı hiperkenara birlikte ait olduğu" bilgisini kaybedebilir. Bu nedenle temsil seçimi, daha sonra çalıştırılacak graf algoritmasından önce gelen bir modelleme kararıdır.

6.17. Ayrık Yapılardan Arama, Planlama ve Graf Tabanlı Öğrenmeye

Ayrık matematik, yapay zekânın özellikle sembolik ve kombinatoryal tarafına doğrudan temel sağlar. Kümeler, mantık, bağıntılar, fonksiyonlar, sayma ve graflar; durumların açık biçimde temsil edildiği arama, planlama, kısıt sağlama (constraint satisfaction) ve bilgi temsili problemlerinin doğal dilidir.

Önermeler mantığında bir bilgi tabanı, doğru veya yanlış olabilen önermeler ve bunlar arasındaki bağlarla ifade edilebilir. Örneğin:

A → B
A
─────
B

biçimindeki çıkarım, veriden istatistiksel örüntü öğrenmekten farklıdır. Burada sonuç, verilen mantıksal öncüller ve çıkarım kuralları altında geçerlidir. Sembolik yapay zekânın önemli bölümü bu açık temsil fikrinden doğar. Modern öğrenen sistemler sembolik yöntemi ortadan kaldırmaz; bazı sistemlerde öğrenilmiş algı ile mantıksal kısıtlar birlikte kullanılabilir.

Graf teorisi yapay zekâda daha geniş bir köprü kurar. Bir durum uzayında düğümler durumları, kenarlar geçişleri temsil edebilir. Yol bulma, oyun oynama ve planlama bu graf üzerinde arama problemine dönüşür. Aynı graf yapısı bilgi grafında varlıkları ve ilişkileri, sosyal ağda kullanıcıları ve bağlantıları, molekülde atomları ve bağları temsil edebilir.

Graf Sinir Ağı (GNN) yaklaşımında her düğüm komşularından bilgi toplar. Basitleştirilmiş mesaj geçişi:

h_v^(k+1) = UPDATE(h_v^k, AGGREGATE({h_u^k : u ∈ N(v)}))

biçiminde düşünülebilir. Buradaki öğrenme işlemi modern olsa da temel nesne hâlâ graftır: komşuluk, derece, yol ve bağlantı yapısı ayrık matematiğin konusudur.

Kombinatorik de arama maliyetini açıklar. n nesnenin tüm permütasyonları n! büyür. Çok sayıda planlama, çizelgeleme veya özellik alt kümesi problemi bu nedenle adayların tamamının denenemeyeceği kadar hızlı genişler. Sezgisel arama, dal ve sınır (branch-and-bound), yerel arama veya evrimsel yöntemlerin gerekliliği çoğu zaman bu kombinatoryal patlamadan doğar.

Bağıntılar ve eşdeğerlik sınıfları, veri temsilinde de önemlidir. İki nesnenin “aynı”, “benzer”, “erişebilir” veya “önce gelir” ilişkileri aynı matematiksel özelliklere sahip değildir. Bir ilişki yansımalı, simetrik veya geçişli olabilir. Yapay zekâ sisteminde benzerlik skorunun eşdeğerlik bağıntısı gibi kullanılması hatalı olabilir; yüksek benzerlik her zaman geçişmeli değildir.

Kümeler ise sınıf, özellik uzayı ve olay tanımlarının temelidir. Bulanık mantıkta üyelik 0 veya 1 yerine derece alabilir; olasılıkta ise belirsizlik farklı bir matematiksel nesnedir. Bu ayrım Bulanık Mantık ve Olasılık ve İstatistik ile birlikte okunmalıdır.

Mantık ve graf yapılarının bir başka kullanım alanı kısıt sağlama problemidir. Değişkenler, alanlar ve kısıtlar açıkça tanımlanır:

X_i ∈ D_i
C_1(X), C_2(X), ...

Amaç bütün kısıtları sağlayan atama bulmaktır. Zamanlama, kaynak tahsisi ve bazı planlama problemleri bu çerçeveye girer. Öğrenen yöntemler arama sırasını iyileştirebilir; fakat kısıtın mantıksal anlamı yine ayrık yapıda kalır.

Ayrık matematik bu nedenle bütün yapay zekânın tek matematiksel temeli değildir. Sürekli optimizasyon için analiz, temsil için lineer cebir, belirsizlik için olasılık gerekir. Ancak sembolik çıkarım, graf tabanlı temsil, kombinatoryal arama ve kısıtlı karar problemlerinin temel yapısını ayrık matematik sağlar.

6.18. Statik Graftan Zamansal Grafa

Zamansal ağlarda bir kenarın varlığı kadar ne zaman gerçekleştiği de yapının parçasıdır. Zamana bağlı bir grafı tek statik komşuluk matrisi altında toplamak, kenarların oluş sırasını sildiği için gerçekte ardışık olarak yürünemeyecek yolları varmış gibi gösterebilir; tersine yalnız kısa bir zaman penceresinde görülen fakat yapısal olarak önemli temaslar toplam ağırlık içinde kaybolabilir. Bu nedenle time-respecting path, temporal reachability, edge persistence, burstiness ve dönemsel merkezilik gibi ölçüler statik derece veya tek bir topluluk bölmesinin tamamlayıcısıdır.

• Bir yolun topolojik olarak var olup zaman sırası nedeniyle kullanılamadığı örneklerin kurulması.
• Snapshot boyutunun bulunan topluluk ve merkezilik sonuçlarına etkisinin gösterilmesi.
• Yönlü, ağırlıklı ve zamansal kenarların aynı veri modelinde açıkça ayrılması.

6.19. Alt Küme Seçimi ve Marjinal Bilgi Kazancı

Bir belge koleksiyonundan sınırlı sayıda cümle seçilmesi, graf merkeziliği kadar bir küme seçimi problemidir. Her aday cümle belirli konuları, zaman dilimlerini veya belge bölgelerini temsil edebilir. Seçilen cümle kümesine S denildiğinde, yeni bir x cümlesinin marjinal katkısı F(S ∪ {x}) - F(S) farkıyla ifade edilir. Bir konunun ilk kez temsil edilmesi yüksek katkı sağlarken aynı konuyu tekrar eden cümlenin katkısı daha düşük olabilir.

Kapsama işlevi monoton ve altmodüler özellik taşıyorsa açgözlü seçim, her adımda en yüksek marjinal kazancı veren öğeyi ekleyerek güçlü bir yaklaşım sunar. Klasik kardinalite kısıtı altında bilinen yaklaşım garantileri belirli varsayımlara dayanır; olumsuzluk, zorunlu kronolojik sıra veya sert belge kotası eklendiğinde aynı garantiyi otomatik olarak taşımak doğru değildir. Bu nedenle uygulamanın amaç işlevi ve kısıtları birbirinden açıkça ayrılmalıdır.

Metin seçimi özelinde bir başka kısıt, iki cümlenin benzer görünmesine rağmen karşıt iddialar taşıyabilmesidir. “Gelecek” ve “gelmeyecek” ifadeleri ortak sözcükler yüzünden yüksek benzerlik puanı alabilir; ancak aynı olgu olarak birleştirilmeleri anlamsal hata oluşturur. Küme kuramı, temsil edilen bilgi birimleri ile yüzey sözcük kümelerinin farklı nesneler olduğunu göstermeye yarar.

En kısa yol yönteminin ön koşulunu karşı örnekle sınamak. Yönlü bir graf üzerinde A → B kenarı 2, A → C kenarı 5, C → B kenarı −4 ağırlığına sahip olsun. A noktasından B noktasına doğrudan gitmenin maliyeti 2 iken A → C → B yolunun maliyeti 5 − 4 = 1 olur. Dijkstra yöntemi negatif kenar yok varsayımıyla ilk B düğümünü 2 uzaklıkla kesinleştirebileceğinden bu örnekte gerçek en kısa yolu kaçırabilir. Dolayısıyla algoritma seçiminden önce kenar ağırlıklarının işareti denetlenmelidir. Negatif ağırlıklı kenarlar bulunduğunda ve negatif çevrim bulunmadığında Bellman–Ford benzeri gevşetme temelli yöntemler kullanılabilir; negatif çevrim varsa bazı hedefler için sonlu en kısa yol hiç tanımlı olmayabilir. Bu kontrol, yöntemin zaman karmaşıklığına bakmaktan önce yapılmalıdır.

6.20. Graf Bağıntıları, Erişilebilirlik ve Zamansal Yol

Bir graf üzerinde iki düğüm arasında yol bulunması, aralarında doğrudan kenar bulunduğu anlamına gelmez. Yönlü bir graf \(G=(V,E)\) için \((u,v)\in E\) doğrudan ilişkiyi; \(u\) düğümünden \(v\) düğümüne ulaşılabilmesi ise bir veya daha fazla kenarın ardışıklığını belirtir. Geçişlilik, yönsüz bağlantılılık ve kuvvetli bağlantılılık farklı özelliklerdir. Özellikle ilişki incelemesinde aynı bileşende bulunma'' ile doğrudan iletişim kurma'' ayrı kanıt düzeyleri olarak işaretlenmelidir.

Kenarların zaman etiketleri bulunduğunda statik graf üzerindeki her yol fiziksel olarak geçerli bir olay sırası üretmeyebilir. Örneğin \(A\to B\) kenarı saat 15.00, \(B\to C\) kenarı 14.00'te oluşmuşsa bu iki kenar statik graf üzerinde yol meydana getirir; ancak 15.00'te başlayan zamanla uyumlu bir bilgi aktarım zinciri olarak sunulamaz. Zamansal yol için kenar zamanlarının sıra koşulu ve varsa aktarım gecikmesi ayrı tanımlanmalıdır.

Graf algoritmasının çıktı sözleşmesi düğüm ve kenar kimliğini, yol uzunluğunu, yön varsayımını ve filtrelenen zaman aralığını korumalıdır. BFS en az kenar sayılı yolu bulabilir; kenar ağırlıkları veya zaman kısıtları varsa problem farklı bir optimizasyon modeline dönüşür. Matematiksel erişilebilirlik, nedensellik veya gerçek dünyadaki koordinasyon iddiasına tek başına yeterli değildir.

Ünite 7: Algoritmalar

7.1. Algoritma Kavramı

Bir problemi çözmek için izlenen sonlu ve kesin adımlar dizisine algoritma denir.

Taşıması gereken nitelikler şunlardır:

• Kesinlik: her adım tek anlamlı olmalıdır.
• Sonluluk: sonlu sayıda adımda bitmelidir.
• Girdi ve çıktı: tanımlı girdiler alır, en az bir çıktı üretir.
• Etkinlik: her adım sonlu sürede yapılabilir olmalıdır.
• Genellik: aynı türden bütün problemleri çözmelidir.

Algoritma, programlama dilinden bağımsızdır. Aynı algoritma farklı dillerde gerçeklenebilir.

7.2. Sözde Kod

Algoritmayı belirli bir dile bağlanmadan yazma biçimine sözde kod (pseudocode) denir.

Doğal dil ile programlama dili arasında durur. Söz dizimi katı değildir; anlam kesindir.

Standart bir yazımı yoktur. Ders boyunca kullanılan yapılar aşağıdadır.

7.3. Karar Yapısı

IF <koşul> THEN
    <işlemler>
ELSE
    <işlemler>
END IF

Koşul bir önermedir. Doğruluk değerine göre iki daldan biri işletilir. ELSE bloğu isteğe bağlıdır.

İç içe karar yapıları kurulabilir. Çok dallı seçimlerde bu yapı zincirlenir.

7.4. Döngü Yapıları

WHILE, koşul doğru olduğu sürece yineler:

WHILE <koşul>
    <işlemler>
END WHILE

Koşul her yinelemenin başında sınanır. Koşul başta yanlışsa gövde hiç işletilmez.

Sonsuz döngüden kaçınmak için gövdenin koşulu etkilemesi gerekir. Döngü değişkeni her adımda ilerlemelidir.

FOR, yineleme sayısı bilindiğinde kullanılır:

FOR i = 1 TO n
    <işlemler>
END FOR

Sayaç otomatik olarak artar. Yineleme sayısı baştan bellidir.

İki yapı birbirine dönüştürülebilir. FOR döngüsü, sayaç yönetimi açıkça yazılarak WHILE ile ifade edilir.

7.5. Alt Program ve Fonksiyon

Bir işlem dizisi birden çok yerde kullanılıyorsa ayrı bir birim olarak yazılır.

Alt program (subroutine), çağrıldığı yerde işini yapar ve döner. Değer döndürmesi gerekmez.

SUBROUTINE <ad>
    <işlemler>
END SUBROUTINE

Çağrı CALL komutuyla yapılır.

Fonksiyon bir değer üretir ve RETURN ile döndürür:

FUNCTION <ad>(<parametreler>)
    <işlemler>
    RETURN <değer>
END FUNCTION

Alt program kullanmanın üç yararı vardır. Kod tekrarı azalır, okunabilirlik artar, değişiklik tek noktadan yapılır.

Dallanma (branch), akışın sıradan sonraki adım yerine başka bir noktaya aktarılmasıdır. Koşullu ve koşulsuz dallanma vardır. Koşulsuz dallanmanın yaygın kullanımı akış izlemeyi zorlaştırır; yapısal programlamada karar ve döngü yapıları tercih edilir.

7.6. En Büyük Değerin Bulunması

Temel bir tarama algoritmasıdır. Yapısı, birçok dizi algoritmasının kalıbıdır.

ALGORITHM ENBUYUK
    MAX = A[1]
    FOR i = 2 TO n
        IF A[i] > MAX THEN
            MAX = A[i]
        END IF
    END FOR
    RETURN MAX
END ALGORITHM

Dört aşama ayırt edilir: ilk değer ataması, tarama, karşılaştırma ve güncelleme, sonuç döndürme.

Dizi n − 1 kez karşılaştırılır. Karmaşıklık Θ(n) düzeyindedir. Daha azı mümkün değildir; her eleman en az bir kez okunmak zorundadır.

Boş dizi durumu ayrıca ele alınmalıdır. İlk değer ataması bu durumda tanımsızdır.

7.7. Kümelerin Bilgisayarda Temsili

Evrensel küme sıralanır. Her eleman için bir bit ayrılır. Eleman kümede varsa bit 1, yoksa 0 olur. Bu gösterime bit vektörü denir.

Küme işlemleri bit işlemlerine dönüşür:

birleşim   →  OR
kesişim    →  AND
tümleyen   →  NOT
fark       →  AND NOT
simetrik fark → XOR

Kazanç büyüktür. İşlemci bir komutta 64 biti işler. Eleman eleman dolaşan bir gerçeklemeye göre çok daha hızlıdır.

Yöntemin koşulu, evrensel kümenin sonlu ve baştan bilinen bir sıralamaya sahip olmasıdır. Eleman sayısı çok büyük ve küme seyrek ise bit vektörü yer bakımından verimsiz kalır; bu durumda karma tablo ya da sıralı liste kullanılır.

7.8. Bağıntı ve Grafların Bilgisayarda Gösterimi

Bağıntı matrisi, n × n boyutlu bit matrisidir. Bellek kullanımı Θ(n²) olur.

Bağlı liste, her düğüm için komşularının zincirini tutar. Bellek kullanımı Θ(n + m) olur.

Seçim ölçütü graf yoğunluğudur. m değeri n² mertebesindeyse matris uygundur. m değeri n mertebesindeyse liste uygundur.

İşlem maliyetleri de değişir. Matriste "i ile j komşu mu" sorusu sabit sürede yanıtlanır. Listede komşu taranır. Buna karşılık bir düğümün bütün komşularını dolaşmak listede derece kadar, matriste n kadar sürer.

7.9. Geçişme Algoritması

Warshall algoritması sözde kodla şöyle yazılır:

ALGORITHM WARSHALL
    M = bağıntı matrisi
    FOR k = 1 TO n
        FOR i = 1 TO n
            FOR j = 1 TO n
                M[i][j] = M[i][j] OR (M[i][k] AND M[k][j])
            END FOR
        END FOR
    END FOR
    RETURN M
END ALGORITHM

Üç döngü n kez çalışır. Karmaşıklık Θ(n³) düzeyindedir. Bellek kullanımı Θ(n²) olur; matris yerinde güncellenir.

Algoritmanın doğruluğu tümevarımla gösterilir. k. adımdan sonra M matrisi, yalnız ilk k düğümü ara nokta olarak kullanan bütün yolları içerir.

7.10. Asimptotik Büyüme ve Karmaşıklık Sınıfları

Bir algoritmanın maliyeti yalnız belirli bir makinedeki saniye cinsinden çalışma süresiyle ölçülmez. Girdi boyutu n büyürken işlem sayısının hangi hızla arttığı incelenir.

Büyük O üstten asimptotik sınırı, Büyük Ω alttan asimptotik sınırı, Büyük Θ ise aynı büyüme sınıfını ifade eder:

f(n) = O(g(n))      yeterince büyük n için f, g'nin sabit katıyla üstten sınırlı
f(n) = Ω(g(n))      yeterince büyük n için f, g'nin sabit katıyla alttan sınırlı
f(n) = Θ(g(n))      iki koşul birlikte

Sabit katsayılar ve düşük dereceli terimler asimptotik sınıfı değiştirmez:

7n² + 4n + 20 = Θ(n²)

Bu gösterimler eşitlik gibi okunmamalıdır. O(n²), fonksiyonun tam maliyetini değil bir üst büyüme sınıfını ifade eder.

Algoritma karşılaştırırken en kötü durum, ortalama durum ve en iyi durum ayrılmalıdır. Aynı algoritmanın üçü farklı sınıflarda olabilir. Ayrıca zaman ile bellek karmaşıklığı farklı kaynakları ölçer.

7.11. Bölünebilirlik, Modüler Aritmetik ve Öklid Algoritması

a sayısı b sayısını tam bölüyorsa a | b yazılır. Tam sayılarda bölme algoritması:

a = bq + r,   0 ≤ r < |b|

biçimindedir. Buradaki kalan, modüler aritmetiğin temelidir.

a ≡ b (mod m)

ifadesi m | (a − b) anlamına gelir. Aynı kalan sınıfındaki sayılar toplama ve çarpma altında uyumlu davranır:

a ≡ b (mod m), c ≡ d (mod m)
⇒ a+c ≡ b+d (mod m)
⇒ ac ≡ bd (mod m)

İki tam sayının en büyük ortak böleni Öklid algoritmasıyla hesaplanır:

gcd(a,b) = gcd(b, a mod b)

kalan sıfır olana kadar işlem yinelenir. Bu yöntem büyük sayılarda bile etkilidir ve genişletilmiş biçimi ax + by = gcd(a,b) eşitliğini sağlayan katsayıları da üretir.

Modüler aritmetik karma tablolarından saat hesaplarına, hata denetiminden açık anahtarlı kriptografinin matematiksel temeline kadar birçok ayrık yapıda görülür. Burada amaç kriptografik protokol tasarlamak değil, bu protokollerde kullanılan tam sayı cebrinin temelini kurmaktır.

7.12. Modüler Aritmetikten Sonlu Alanlara: AES Örneği

Modüler aritmetik ile kriptografide kullanılan sonlu alan aritmetiği aynı şey değildir. Z_m üzerinde toplama ve çarpma mod m yapılır; m asal değilse sıfırdan farklı her elemanın çarpımsal tersi bulunmaz ve yapı alan değildir. AES ise bir baytı yalnız 0..255 arasında kalan bir tam sayı olarak değil, katsayıları GF(2) üzerinde olan yedinci dereceye kadar bir polinom olarak yorumlar ve işlemleri sekizinci dereceden indirgenemez bir polinoma göre yürütür. FIPS 197'de kullanılan polinom:

m(x) = x^8 + x^4 + x^3 + x + 1

olup ikili gösterimde 0x11B ile ilişkilidir. Bu nedenle AES'teki çarpma "256'ya göre sıradan tam sayı çarpımı" değildir; GF(2^8) alanındaki polinom çarpımı ve indirgemesidir.

Bu cebir iki temel AES adımında doğrudan görünür. SubBytes, sıfır dışındaki bayt için GF(2^8) çarpımsal tersini ve ardından afin dönüşümü kullanır. MixColumns ise durum sütununu sabit katsayılı bir matrisle yine GF(2^8) üzerinde çarpar. Böylece ayrık matematikteki eşdeğerlik sınıfları, polinom aritmetiği ve ters kavramı, gerçek bir blok şifrenin dönüşüm katmanlarına kadar uzanır (NIST FIPS 197).

Sitedeki AES Kriptanalizinde Cebirsel Temsil bu cebirsel yapıyı saldırı/denklem modelleme yönünden, C ile Hafif AES-128 Gerçekleştirimi ise uygulama yönünden ele alır. İlgili açık kaynak Lightweight AES-128 yazılımı Zenodo'da kalıcı olarak arşivlenmiştir (doi:10.5281/zenodo.22117428). Buradaki kişisel bağ genel AES matematiğinin kaynağı değildir; teorik yapının doğrulanabilir bir yazılım artefaktına uzandığını gösterir.

7.13. Özyineleme Bağıntılarını Çözme

Bir dizi önceki terimleriyle tanımlanıyorsa özyineleme bağıntısı elde edilir. Örneğin ikinci mertebeden lineer homojen biçim:

a_n = c1 a_(n−1) + c2 a_(n−2)

için a_n = r^n biçiminde çözüm denenir ve karakteristik denklem kurulur:

r² − c1 r − c2 = 0

Farklı kökler r1 ve r2 ise genel çözüm:

a_n = A r1^n + B r2^n

biçimindedir. Katsayılar başlangıç koşullarından bulunur. Tekrarlı kökte ikinci bağımsız terim n r^n biçiminde ortaya çıkar.

Böl-ve-yönet algoritmalarında maliyet çoğu zaman:

T(n) = a T(n/b) + g(n)

tipindedir. Burada a alt problem sayısını, n/b alt problem boyutunu, g(n) ise bölme ve birleştirme maliyetini temsil eder. Bağıntı yalnız diziyi tanımlamaz; algoritmanın yapısını görünür kılar.

7.14. Üretici Fonksiyonlar

Bir dizinin terimleri bir biçimsel kuvvet serisinin katsayıları olarak kodlanabilir:

G(x) = a0 + a1 x + a2 x² + ...

G(x) dizinin üretici fonksiyonudur. Buradaki seri öncelikle cebirsel bir kodlama aracıdır; yakınsaklık her uygulamada temel konu değildir.

Özyineleme bağıntısı terim terim x^n ile çarpılıp toplanarak G(x) için cebirsel bir denkleme dönüştürülebilir. Bu denklem çözüldüğünde katsayılar geri okunarak dizinin kapalı biçimi elde edilebilir.

Üretici fonksiyonların ikinci gücü saymadadır. Bağımsız seçimlerin üretici fonksiyonları çarpıldığında, belirli bir kuvvetin katsayısı toplam kısıtı sağlayan seçim sayısını verebilir. Böylece sayma problemi katsayı çıkarma problemine dönüşür.

Üretici fonksiyonlar, Matematik II içindeki analitik kuvvet serileriyle aynı gösterimi paylaşır; ancak ayrık matematikte temel amaç çoğu zaman yakınsaklık değil, diziyi ve sayma yapısını cebirsel olarak temsil etmektir.

7.15. Bézout Eşitliği, Modüler Ters ve Euler-Fermat Bağlantısı

Öklid algoritmasının genişletilmiş biçimi gcd(a,b) ile birlikte:

ax + by = gcd(a,b)

bağıntısını sağlayan x ve y katsayılarını üretir. Eğer gcd(a,m)=1 ise:

ax + my = 1

olur ve mod m altında:

a x ≡ 1 (mod m)

elde edilir. Böylece x, a sayısının modüler tersidir.

Euler teoremi, gcd(a,n)=1 iken:

a^phi(n) ≡ 1 (mod n)

bağıntısını verir. Asal p için Fermat'nın küçük teoremi bunun özel ve çok kullanılan bir sonucudur. Bu sonuçlar ayrık cebirin ve açık anahtarlı kriptografinin matematiksel temelindedir; protokol tasarımının kendisi ise kriptografi dersinin konusudur.

7.16. Özyineleme ile Dinamik Programlama Arasındaki Matematiksel Köprü

Bir problemin alt problemlerle tanımlanması önce matematiksel bir özyineleme bağıntısı üretir. Dinamik programlama ise aynı bağıntının hesaplama düzenini değiştirir: tekrar hesaplanan durumlar saklanır veya bağıntı tabandan yukarı doğru değerlendirilir.

Bir DP modelini kurarken dört matematiksel unsur açık olmalıdır:

• durumun neyi temsil ettiği,
• geçiş bağıntısının hangi önceki durumlara bağlı olduğu,
• başlangıç veya sınır koşullarının neler olduğu,
• istenen çözümün hangi durumdan ve gerekiyorsa hangi geri izleme bilgisiyle çıkarıldığı.

Bu nedenle dinamik programlama, yalnız bir kodlama kalıbı değildir; özyinelemeli tanımın hesaplanabilir bir sıraya dönüştürülmesidir. Ayrıntılı veri yapısı, bellek ve yeniden yapılandırma tasarımı Algoritma Analizi dersinin doğal devamıdır.

7.17. Değişmezler ve Tümevarımı Program Doğruluğuna Bağlamak

Matematiksel tümevarım yalnız sayı dizilerini kanıtlama tekniği değildir. Döngü değişmezi, algoritmanın her iterasyonunda korunan bir önermedir ve başlangıç-koruma-sonlanma üçlüsüyle program doğruluğuna bağlanır.

Örneğin binary search'te "aranan değer varsa mevcut [low, high] aralığındadır" önermesi her adımda korunur. İndeks güncellemesindeki küçük bir +1/-1 hatası bu değişmezi bozduğu için sınır hatasını yalnız testle değil mantıksal olarak da yakalamak mümkündür.

Graf problemlerinde de değişmezler güçlüdür. Dijkstra algoritmasında işlenmiş düğümlerin kesinleşmiş en kısa mesafeleri, union-find yapısında temsilci ilişkisi ve topolojik sıralamada indegree koşulu, algoritmanın neden çalıştığını açıklayan matematiksel omurgadır.

7.18. Karşı Örnek ve Değişmezlerle Doğrulama

Ayrık matematikte bir önermenin doğru görünmesi yeterli değildir. Evrensel bir iddiayı çürütmek için tek karşı örnek yeterliyken, doğrulamak için ispat gerekir. Bu ayrım algoritma doğruluğunda da geçerlidir.

Graf algoritmalarında küçük elle kurulmuş örnekler yararlıdır: bağlantısız graf, döngü, paralel kenar, negatif ağırlık ve tek düğüm gibi durumlar varsayımı görünür kılar. Dijkstra gibi algoritmalarda ön koşul ihlal edilirse test sonucu tesadüfen doğru çıkabilir.

Döngü değişmezleri ve tümevarım, program davranışını biçimsel açıklamaya bağlar. Başlangıç, koruma ve sonlanma adımları açık olduğunda doğruluk yalnız örnek çıktılara dayanmaz.

7.19. Biçimsel Diller ve Otomatlara Geçiş

Ayrık matematik yalnız kümeler, bağıntılar ve graflardan oluşmaz; hesaplamanın hangi sembol dizilerini kabul ettiğini ve hangi problemlerin hangi soyut makineyle çözülebileceğini açıklayan biçimsel dil kuramının da matematiksel temelidir. Türkiye'deki bilgisayar mühendisliği programlarında bu konu kimi zaman Ayrık Matematik'in devamında, kimi zaman Biçimsel Diller ve Otomata veya Otomata Teorisi adıyla ayrı bir derste işlenir.

Bir alfabe sonlu bir sembol kümesidir. Bu alfabeden oluşturulan sonlu dizilere sözcük veya dizi (string), dizilerin oluşturduğu kümeye dil denir. Örneğin {0,1} alfabesi üzerindeki “sonu 01 ile biten bütün diziler” bir dildir. Buradaki önemli nokta, dilin programlama dili olmak zorunda olmamasıdır; protokol mesaj biçimleri, belirli bir desene uyan log satırları ve sözcüksel belirteçler de biçimsel dil olarak incelenebilir.

7.20. Düzenli Diller ve Sonlu Otomatlar

Düzenli ifadeler, düzenli diller ve sonlu otomatlar aynı ifade gücü sınıfının farklı gösterimleridir. Deterministik sonlu otomat (DFA) her durum ve giriş sembolü için tek bir sonraki duruma sahiptir. Deterministik olmayan sonlu otomat (NFA) birden çok olası geçişe izin verebilir; ancak kabul edebildiği dil sınıfı DFA'dan daha geniş değildir. Her NFA uygun bir durum-kümesi dönüşümüyle eşdeğer bir DFA'ya dönüştürülebilir.

girdi sembolleri
      ↓
 [başlangıç durumu]
      ↓
   geçişler
      ↓
[kabul / ret durumu]

Sonlu otomatın belleği, bulunduğu durumla sınırlıdır. Bu nedenle keyfi derinlikte iç içe parantezleri saymak gibi sınırsız yığın belleği isteyen yapıları genel durumda tanıyamaz. Bu sınır, “hangi algoritma daha hızlı?” sorusundan önce gelen daha temel bir sorudur: bu hesaplama modeli problemi ifade etmeye yeterli mi?

7.21. Bağlamdan Bağımsız Gramer ve Yığıtlı Otomat

Programlama dillerinin sözdiziminde bloklar, ifadeler ve iç içe yapılar bulunduğu için düzenli diller çoğu zaman yeterli değildir. Bağlamdan bağımsız gramer (CFG), terminaller, terminal olmayan semboller, üretim kuralları ve başlangıç sembolüyle daha zengin yapıları tanımlar. Bu dil sınıfının doğal makine modeli yığıtlı otomat (pushdown automaton)tır.

karakterler
   ↓
sözcüksel çözümleme       düzenli dil / sonlu otomat
   ↓
belirteçler
   ↓
sözdizimsel çözümleme     CFG / yığıtlı otomat
   ↓
sözdizim ağacı

Bu ayrım Programlama Dilleri dersindeki derleyici hattını açıklar: sözcüksel çözümleme ile ayrıştırma aynı problem değildir. Bir gramerin bir diziyi üretebilmesi de programın anlamsal olarak doğru olduğu anlamına gelmez; tür denetimi, ad bağlama ve çalışma zamanı davranışı daha sonraki katmanlardır.

7.22. Turing Makinesi, Hesaplanabilirlik ve Karar Verilebilirlik

Turing makinesi, sonlu kontrol birimine ek olarak kuramsal olarak sınırsız bir bant üzerinde okuyup yazabilen soyut hesaplama modelidir. Buradaki amaç gerçek işlemciyi taklit etmek değil, “algoritmayla çözülebilir” kavramına makineden bağımsız bir sınır çizmektir.

Bir karar problemi, her girdi için evet/hayır sonucu ister. Problem için her girdide sonlanan doğru bir algoritma varsa problem karar verilebilirdir. Bazı problemler ise hiçbir genel algoritmayla bütün girdiler için çözülemez. Durdurma probleminin önemi burada ortaya çıkar: program davranışının her özelliğini genel ve kusursuz bir çözümleyiciyle önceden belirleyemeyeceğimizi gösterir.

Hesaplanabilirlik ile karmaşıklık karıştırılmamalıdır:

hesaplanabilirlik: Bir çözüm algoritması var mı?
karmaşıklık:        Varsa ne kadar zaman/bellek gerektiriyor?

Bu nedenle otomata kuramı, yalnız derleyici tasarımının tarihsel bir konusu değildir. Düzenli ifade motorlarından protokol doğrulamaya, sözdizimi çözümlemeden model denetimine kadar birçok alanda kullanılan durum, dil ve kabul kavramlarının ortak matematiksel dilini sağlar.

7.23. Modüler Algoritma ve Karmaşıklık Sınırı

Genişletilmiş Öklid algoritması, iki tamsayı için EBOB ile birlikte Bézout katsayılarını üretir. Algoritmanın her turda tuttuğu eşitlikler, modüler tersin varlık koşulunu açıkça gösterir. İkili üs alma, üssün bitlerini işleyerek a^e mod n hesabını doğrusal sayıda çarpma yerine yaklaşık O(log e) çarpma ile tamamlar; ancak büyük tamsayı çarpmasının bit maliyeti ayrıca dikkate alınmalıdır. CRT aralarında asal modüllerde çözüm birleştirmesini sağlar.

Bu dersin katkısı RSA uygulaması öğretmek değil, kullanılan algoritmaların doğruluk değişmezlerini ve maliyetini göstermektir. Kriptografik anahtar üretimi ve yan kanal koşulları Kriptoloji dersine aittir.

Kaynakça

• Ahmet Yesevi Üniversitesi Bilgisayar Mühendisliği Bölümü. Ayrık Matematik (TBIL108) ders materyalleri.

• Albert-László Barabási. Network Science.

• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th Edition. McGraw-Hill, 2019.

• Muhammet Ali Köker. HTS/CDR Analyzer for Java v1.0.1 (araştırma yazılımı). Zenodo, 2026. doi:10.5281/zenodo.22685947

• Muhammet Ali Köker. lightweight-aes-128-c (araştırma yazılımı). Zenodo, 2026. doi:10.5281/zenodo.22117428

• National Institute of Standards and Technology. Advanced Encryption Standard (AES), FIPS PUB 197. doi:10.6028/NIST.FIPS.197

• Petter Holme; Jari Saramäki (eds.). Temporal Network Theory. 2nd ed. Springer Nature Switzerland, 2023.

• Ralph P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction, 5th Edition. Pearson, 2003.

• Reinhard Diestel. Graph Theory, 5th Edition. Springer, 2017.

• Stuart Russell, P. N. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2021.

• Susanna S. Epp. Discrete Mathematics with Applications, 5th Edition. Cengage, 2019.

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 4th Edition. MIT Press, 2022.
• Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, 3rd ed., 2025. https://www.routledge.com/Introduction-to-Modern-Cryptography/Katz-Lindell/p/book/9781040366493