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

Kümeler, sayma, mantık, bağıntılar, fonksiyonlar ve graf teorisinin yanında rekürans bağıntıları, graf renklendirme, değişmezler, tümevarım ve algoritmik doğrulamayı birleştiren ayrık matematik ders notları.

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ş

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.

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.

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.

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.

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.

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.

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.

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|

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.

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.

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.

Sıralı ikili 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.

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.

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.

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.

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

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.

Ünite 2: Permütasyon ve Kombinasyon

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.

Sayma ilkeleri

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.

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.

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.

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:

Bileşke işlemi kapalıdır. İki permütasyonun bileşkesi yine bir permütasyondur.
İşlem birleşmelidir.
Her elemanı kendisine eşleyen birim permütasyon vardır.
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.

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.

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ʳ

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.

Ünite 3: Önermeler Mantığı

Ö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.

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.

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

Evetleme

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

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

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.

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.

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.

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'

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.

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.

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.

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.

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.

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.

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.

Ünite 4: Bağıntı

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.

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.

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.

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.

Simetrik bağıntı

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

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

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.

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.

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.

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:

Her eleman kendi sınıfındadır. Hiçbir sınıf boş değildir.
İki denklik sınıfı ya özdeştir ya da ayrıktır. Kısmen örtüşme olamaz.
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.

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.

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.

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.

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

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:

A kümesinin her elemanı eşlenmiş olmalıdır.
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.

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.

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.

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.

İkili iş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.

İş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

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.

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.

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.

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.

Ağaçlar

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

Denk tanımlar şunlardır:

Devresiz ve bağlantılıdır.
Her düğüm çifti arasında tam bir yol vardır.
Bağlantılıdır ve kenar sayısı n − 1'dir.
Devresizdir ve kenar sayısı n − 1'dir.
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.

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.

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.

Ağırlıklı graflar ve minimum kapsayan ağaç

Ağırlıklı bir grafta toplam kenar ağırlığını en aza indiren kapsayan ağacın vurgulanması — En küçük 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:

Kenarlar ağırlığa göre artan sırada sıralanır.
En küçük ağırlıklı kenar seçilir.
Seçilen kenar devre oluşturmuyorsa ağaca eklenir, oluşturuyorsa atlanır.
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.

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.

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.

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.

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.

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.

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.

Ünite 7: Algoritmalar

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.

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.

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.

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.

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.

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.

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.

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.

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.

Genel Kavramsal Çerçeve

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.

Kavramsal Ayrımlar

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.

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.

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.

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.

İspat, karşı örnek ve yapı arasındaki iliş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.

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.

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?

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.

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.

Kaynakça

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

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

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.