Yapay zeka, makinelerin insana özgü sanılan davranışları — öğrenme, akıl yürütme, örüntü tanıma — sergilemesini sağlayan bir disiplindir. Ama dikkat: bu bir tanım değil, bir davettir. Asıl soru şu: özgü kelimesini ne zamana kadar kullanabileceğiz?
Devamı...SQL temellerini bilen ama sorguları daha bilinçli yazmak isteyenler için 70 konu, açıklama, örnek ve pratik notlarla hazırlanmış kapsamlı bir çalışma rehberi.
Devamı...Çizgi süpürme algoritmaları, geometrik problemleri düzlemdeki noktaları temsil eden olaylar kümesine dönüştürerek çözer. Olaylar $x$ veya $y$ koordinatına göre sıralanır ve soldan sağa (ya da aşağıdan yukarıya) sırayla işlenir; böylece iki boyutlu problem tek boyutlu bir taramaya indirgenir.
Motivasyon örneği: $n$ çalışanı olan bir ofiste her çalışanın giriş ve çıkış saatleri bilinmektedir. Herhangi bir anda ofiste bulunan en fazla çalışan sayısını bul.
Her çalışan iki olay üretir: giriş (+1) ve çıkış (−1). Olaylar zamana göre sıralanır ve bir sayaç tutulur:
Devamı...Geometri problemlerinde kolay koda dökülebilecek bir çözüm bulmak genellikle zordur; özel durum sayısı fazladır. İyi bir yaklaşım, özel durumları minimize eden matematiksel araçlar seçmektir. Bu bölümdeki temel araçlar karmaşık sayılar ve vektörel çarpım olacaktır.
Örnek: Bir dörtgenin alanı, köşeleri $s = (a+b+c)/2$ olmak üzere Heron Formülü ile iki üçgene bölerek hesaplanabilir; ama hangi köşegen seçileceği özel durumlar doğurur. Bunun yerine doğrudan genel formül:
\[\text{Alan} = \frac{|x_1 y_2 - x_2 y_1 + x_2 y_3 - x_3 y_2 + x_3 y_4 - x_4 y_3 + x_4 y_1 - x_1 y_4|}{2}\]Bu formülün avantajı hiç özel durum içermemesi ve tüm çokgenlere genellenebilmesidir.
Devamı...Karekök algoritmaları, zaman karmaşıklığı $O(\sqrt{n})$ bileşeni içeren algoritmalardır. Karekök, “fakir adamın logaritması” olarak nitelendirilebilir:
\[O(\log n) \;<\; O(\sqrt{n}) \;<\; O(n)\]Pratikte karekök algoritmaları hem yeterince hızlı hem de uygulaması görece basittir. Temel fikir, bir diziyi $\sqrt{n}$ büyüklüğündeki bloklara ayırmaktır.
Devamı...Yazı algoritmaları, metinleri verimli şekilde işlemek için kullanılır. Pek çok yazı problemi $O(n^2)$’de kolayca çözülse de asıl hedef $O(n)$ veya $O(n \log n)$’e inmektir. Temel örnek örüntü bulma problemidir: $n$ uzunluğundaki yazıda $m$ uzunluğundaki örüntü nerede geçiyor?
Devamı...Oyun teorisi, rastgele eleman içermeyen iki kişilik oyunları analiz eder. Amaç; rakip ne yaparsa yapsın, eğer varsa oyunu kesinlikle kazandıracak bir strateji bulmaktır. Bu oyunlar nim teorisi ile analiz edilir.
Devamı...Olasılık, rastgele bir sürecin sonuçlarını sayısal olarak ifade eder. $0$ ile $1$ arasında bir değer olan $P(A)$, $A$ olayının gerçekleşme ihtimalini verir; $P(A) = 0$ imkânsızı, $P(A) = 1$ kesinliği temsil eder.
Zar atma örneğiyle:
Matris, programlamadaki iki boyutlu dizinin matematikteki karşılığıdır. $m \times n$ büyüklüğündeki bir matris $m$ satır ve $n$ sütundan oluşur; $A[i, j]$ gösterimi $i$. satır ve $j$. sütundaki elemanı verir. Özel bir durum olarak $n \times 1$ büyüklüğündeki matrise vektör denir.
$A$ matrisinin transpozu $A^T$, satırlar ile sütunların yer değiştirmesinden elde edilir: $A^T[i, j] = A[j, i]$. Satır ve sütun sayısı eşit olan matris kare matristir.
Devamı...Kombinatorik, nesnelerin kombinasyonlarını sayma yöntemlerini araştırır. Genelde amaç her kombinasyonu ayrı ayrı oluşturmadan toplam sayıyı hesaplamaktır.
Örneğin toplamı $n$ olan tam sayı dizisi sayısı gibi problemler özyinelemeli formüllerle ele alınır. $f(n)$, $n$’yi toplam olarak yazma yollarının sayısı olsun:
\[f(n) = \begin{cases} 1 & n = 0 \\ f(0) + f(1) + \cdots + f(n-1) & n > 0 \end{cases}\]İlk değerler: $f(0)=1,\ f(1)=1,\ f(2)=2,\ f(3)=4,\ f(4)=8$. Bu durumda kapalı form $f(n) = 2^{n-1}$’dir; çünkü $n-1$ boşluktan istediğimizi seçip $+$ ya da hiç koyabiliriz.
Devamı...Sayılar teorisi, matematiğin tam sayılarla ilgilenen alt dalıdır. İlginç bir konudur; çünkü tam sayı içeren pek çok soru ilk bakışta kolay görünse de çözümü son derece zor olabilir. Örneğin $x^3 + y^3 + z^3 = 33$ eşitliğini sağlayan üç tam sayı bulmak hâlâ açık bir matematik problemidir.
Bu bölümde sayılar teorisinin rekabetçi programlamada sık karşılaşılan temel kavramları ve algoritmaları ele alınmaktadır.
Devamı...Bu bölümde iki temel soru üzerine yoğunlaşıyoruz:
Her iki problem için girdi; kaynak (kendisine gelen kenar bulunmayan) ve musluk (kendisinden çıkan kenar bulunmayan) olmak üzere iki özel düğüm içeren, yönlü ve ağırlıklı bir çizgedir.
Bu iki sorunun cevabı her zaman birbirine eşittir. Maksimum akış ile minimum kesim sanki paranın iki yüzüdür; Ford-Fulkerson Algoritması hem maksimum akışı hem de minimum kesimi aynı anda çözer.
Devamı...Bu bölümde çizgeler üzerindeki iki temel yol türü inceleniyor:
İlk bakışta birbirine benzer görünen bu iki kavram aslında tamamen farklı zorluktadır. Bir çizgenin Euler yolu içerip içermediğini belirlemek ve varsa bulmak çok verimli biçimde yapılabilir. Hamilton yolu ise NP-hard bir problemdir; bunu verimli çözen bilinen bir algoritma yoktur.
Devamı...Bu bölümde köklü ağaçların alt ağaçları ve yolları üzerinde yapılan sorguları çözme yöntemlerini inceliyoruz. Ele alınan sorgu türleri şunlardır:
Yönlü bir çizgede kenarlar yalnızca tek yönlü geçilir. Bu nedenle çizge bağlı olsa bile her düğümden diğerine gidileceği garanti edilemez. Daha güçlü bir bağlanırlık kavramına ihtiyaç vardır.
Bir çizge, her düğümden diğer tüm düğümlere gidilebiliyorsa güçlü bağlanılmış (strongly connected) olarak adlandırılır. Güçlü bağlanılmamış bir çizgede ise bazı düğüm çiftleri arasında tek yönlü bir ulaşım bile mümkün olmayabilir.
Güçlü bağlanılmış parçalar (strongly connected components, SCC), çizgeyi olabildiğince büyük güçlü bağlanılmış bölümlere ayırır. Bu parçalar, orijinal çizgenin derin yapısını ortaya koyan asiklik bir bileşen çizgesi (component graph) oluşturur.
Devamı...Bu bölümde yönlü çizgelerin iki türünden bahsedeceğiz:
Her iki durumda da bu özellikler sayesinde çeşitli verimli algoritmalar tasarlanabilir.
Devamı...Kapsayan ağaç (spanning tree), bir çizgenin bütün düğümlerini bağlı olacak şekilde birleştiren, çizgenin bazı kenarlarını içeren bir ağaçtır. Ağaçlardaki gibi, kapsayan ağaçlar da bağlı ve asikliktir. Genelde, kapsayan ağaç oluşturmanın birkaç yolu vardır.
Kapsayan ağacın ağırlığı kenar ağırlıklarının toplamıdır. En küçük kapsayan ağaç (minimum spanning tree), ağırlığı en küçük olan kapsayan ağaçtır. Benzer şekilde en büyük kapsayan ağaç, en büyük ağırlığa sahip kapsayan ağaçtır.
Bir çizgenin birkaç tane en küçük ve en büyük kapsayan ağacı olabilir; yani bu ağaçlardan sadece bir tane olmak zorunda değildir.
En küçük ve en büyük kapsayan ağaçları bazı açgözlü yöntemler kullanarak oluşturabiliriz. Bu bölümde kenarların ağırlıklarına göre sıralayarak yapılan iki algoritmadan bahsedeceğiz. Her ne kadar bölümde en küçük kapsayan ağaçları bulmaya odaklanacak olsak bile, en büyük kapsayan ağaç da kenarları ters sırada işleyerek bulunabilir.
Kruskal’ın Algoritması’nda başlangıçtaki kapsayan ağaçta sadece çizgenin düğümleri bulunur ve herhangi bir kenar içermemektedir. Sonrasında algoritma kenarlara ağırlıklarına göre bakar ve eğer kenar döngü oluşturmuyorsa kenarı kapsayan ağaca ekler.
Algoritma, ağacın parçalarını tutar. İlk başta çizgenin her düğümü ayrı bir parçadır. Her seferinde ağaca bir kenar eklendiği zaman iki parça birleşir. Sonunda bütün düğümler aynı parçaya ait olur ve en küçük kapsayan ağaç bulunur.
Algoritmanın ilk adımında kenarlar, ağırlıklarına göre küçükten büyüğe doğru sıralanır:
| Kenar | Ağırlık |
|---|---|
| 5–6 | 2 |
| 1–2 | 3 |
| 3–6 | 3 |
| 1–5 | 5 |
| 2–3 | 5 |
| 2–5 | 6 |
| 4–6 | 7 |
| 3–4 | 9 |
Bundan sonra algoritma listeden geçer ve kenar iki ayrı parçayı bağlıyorsa kenarı ağaca ekler. Başta her düğüm kendisine ait parçadadır. Ağaca ilk eklenen kenar 5–6 kenarıdır; bu kenar ${5}$ ve ${6}$ parçalarını ${5, 6}$ şeklinde birleştirir. Ardından 1–2, 3–6 ve 1–5 kenarları benzer şekilde eklenir.
Bu adımlardan sonra ağaçta iki parça kalmıştır: ${1, 2, 3, 5, 6}$ ve ${4}$. Listedeki sonraki kenar 2–3‘tür, ancak 2 ve 3 düğümleri aynı parçaya ait olduğundan bu kenar ağaca eklenmez. Aynı nedenden dolayı 2–5 kenarı da eklenmez. En sonunda 4–6 kenarı ağaca eklenir ve algoritma tamamlanır. Oluşan en küçük kapsayan ağacın ağırlığı $2 + 3 + 3 + 5 + 7 = 20$ olur.
Çizgedeki minimum ağırlıklı kenarı eklemediğimizi varsayalım. Bu durumda mevcut kapsayan ağaçtan bir kenarı çıkartıp yerine minimum ağırlıklı kenarı eklediğimizde daha küçük ağırlığa sahip bir kapsayan ağaç elde ederiz. Bu çelişki, en küçük ağırlığa sahip kenarı eklemenin her zaman optimal olduğunu gösterir. Benzer mantık sonraki kenarlar için de geçerlidir; dolayısıyla Kruskal’ın Algoritması her zaman doğru sonucu verir.
Kruskal’ın Algoritması’nı koda geçirirken çizgeyi bir kenar listesinde tutmak daha rahat olur. Algoritmanın ilk aşamasında listedeki kenarlar $O(m \log m)$ zamanda sıralanır. Bundan sonra algoritma en küçük kapsayan ağacı şu şekilde oluşturur:
Devamı...Bir ağaç (tree), $n$ düğüm ve $n - 1$ kenardan oluşan bağlı ve asiklik (döngüsüz) bir çizgedir. Ağaçtan herhangi bir kenarı çıkarmak onu iki parçaya böler; herhangi bir kenar eklemek ise bir döngü oluşturur. Her iki düğüm arasında tam olarak bir yol bulunur.
Örneğin 8 düğüm ve 7 kenardan oluşan bir ağaçta yapraklar (leaves), derecesi 1 olan yani tek komşusu bulunan düğümlerdir. Köklü bir ağaçta düğümlerden biri kök seçilir ve diğer tüm düğümler onun altına yerleştirilir. Köklü ağaçta bir düğümün çocukları (children) onun alt komşuları, ebeveyni (parent) ise üst komşusudur. Her düğümün kök hariç tam bir ebeveyni vardır.
Köklü ağacın yapısı özyinelemelidir: her düğüm, kendisini ve tüm torunlarını kapsayan bir alt ağacın kökü gibi davranır.
Genel çizge dolaşım algoritmaları ağaçlarda da kullanılabilir. Ancak ağaçlar döngü içermediğinden ve bir düğüme birden fazla yoldan ulaşılamadığından implementasyon genel çizgelere kıyasla çok daha sadedir.
Ağacı dolaşmanın klasik yolu herhangi bir düğümden DFS başlatmaktır:
Devamı...Bir çizgede iki düğüm arasındaki en kısa yolu bulmak, pek çok pratik uygulamaya sahip temel bir problemdir. Klasik bir örnek, yol uzunlukları bilinen bir ağda iki şehir arasındaki en kısa rotayı hesaplamaktır. Ağırlıksız çizgelerde yol uzunluğu kenar sayısına eşit olduğundan BFS ile çözülebilir; bu bölümde ise ağırlıklı çizgeler için geliştirilmiş algoritmalara bakacağız.
Bellman–Ford algoritması1, başlangıç düğümünden çizgedeki tüm düğümlere en kısa mesafeyi bulur. Negatif döngü içermeyen her türlü çizgede çalışır; üstelik çizgede negatif döngü varsa bunu tespit edebilir.
Algoritma, başlangıç düğümüne 0, diğer tüm düğümlere sonsuz mesafe atayarak başlar. Her turda tüm kenarlar incelenerek mesafeler kısaltılmaya çalışılır. Hiçbir mesafe artık kısalımıyorsa algoritma durur.
Aşağıdaki 5 düğümlü ağırlıklı çizgede 1. düğümden başlayan Bellman–Ford adımları:
Başlangıç: Mesafeler $[0, \infty, \infty, \infty, \infty]$
1. tur — 1. düğümden çıkan tüm kenarlar mesafeleri azaltır:
\[[0,\ 5,\ 3,\ 7,\ \infty]\]2. tur — $2 \to 5$ ve $3 \to 4$ kenarları devreye girer:
\[[0,\ 5,\ 3,\ 4,\ 7]\]3. tur — Son bir güncelleme daha:
\[[0,\ 5,\ 3,\ 4,\ 6]\]Artık hiçbir kenar mesafeyi azaltamaz; başlangıç düğümünden tüm düğümlere en kısa mesafeler bulunmuştur. Örneğin 1. düğümden 5. düğüme en kısa mesafe 3’tür.
Algoritma R. E. Bellman ve L. R. Ford tarafından birbirinden habersiz biçimde sırasıyla 1958 ve 1956 yıllarında yayınlanmıştır. ↩
Bu bölümde iki temel çizge dolaşma algoritması ele alınacaktır: derinlik öncelikli arama (DFS) ve genişlik öncelikli arama (BFS). Her ikisinin de bir başlangıç noktası vardır ve başlangıç düğümünden ulaşılabilen tüm düğümleri gezerler. İki algoritma arasındaki fark, düğümleri dolaşma sırasıdır.
Derinlik öncelikli arama (Depth-First Search — DFS), sezgisel bir çizge dolaşma tekniğidir. Algoritma başlangıç düğümünden hareket ederek çizgenin kenarlarını kullanır ve ulaşılabilir tüm düğümleri ziyaret eder. DFS, yeni bir düğüm buldukça tek bir yolu izlemeye devam eder; çıkmaza girdiğinde ise geri dönerek çizgenin diğer bölgelerini keşfeder. Her düğüm yalnızca bir kez ziyaret edilip işlenir.
Algoritmanın zaman karmaşıklığı $O(n + m)$’dir; burada $n$ düğüm sayısı, $m$ ise kenar sayısıdır. Bu, algoritmanın her düğümü ve kenarı tam bir kez işlemesinden kaynaklanır.
Aşağıdaki beş düğümlü çizgede DFS’in 1. düğümden nasıl ilerlediğini izleyelim:
Devamı...