Problemi
çizersen
çözülür.
Önceki ünitede algoritmayı yazmayı öğrendin. Burada kurmayı öğreneceksin: yedi köprüden bir kez geçmek, n kişilik grupta kaç tokalaşma olduğunu bulmak, bir bozuk parayı en az tartımla yakalamak, çöp arabasını en kısa yoldan dolaştırmak. Ortak araç çizge kuramı: nesneleri düğüm, ilişkileri ayrıt yapıp problemin resmini çizmek.
Çizge kuramı, nesneler arasındaki ilişkileri düğümler (noktalar) ve bu düğümleri birbirine bağlayan ayrıtlar (çizgi) kullanarak inceler. En basit örnek iki kişinin tokalaşmasıdır: A ve B düğümleri kişileri, aralarındaki ayrıt tokalaşmayı gösterir. Bu kadar sade bir modelin gücü şurada: çizgeler; sosyal ağlardan genel ağ bağlantılarına, yol bulma sistemlerinden elektrik devrelerine kadar birçok gerçek yaşam problemi için bir model sunar. Algoritmalar, bu modeller üzerinde çalışarak belirli problemleri çözmek için kullanılır.
Bir düğüme bağlı ayrıt sayısına o düğümün
derecesi denir. Tabloda bu, “Tüm düğümlerin tek ya da
çift sayıda ayrıta sahip olma durumu” sütunudur.
İlk satırdaki iki düğümlü çizgede örnek çözüm:
“A ve B düğümlerine bağlı ikişer ayrıt vardır. Tüm düğümler, çift
sayıda ayrıta sahiptir.” Bu yüzden A’dan çıkan kişi a ayrıtıyla B’ye ulaşır ve b ayrıtıyla
başladığı düğüme döner.
Derecenin neden bu kadar önemli olduğunu bir cümleyle anlarsın:
bir düğüme her girişinin bir çıkışı olmalıdır. Girişler ve
çıkışlar ayrıtları ikişer ikişer harcadığı için, başladığın yere dönebilmek isteniyorsa
her düğümün derecesi çift olmalıdır.
İsviçreli matematikçi Euler, Pregel Nehri üzerinde yedi köprünün yer aldığı Königsberg şehrinde 1736’da bir yürüyüş rotası problemi üzerine çalışmıştır. Şehrin köprülerini, yürüyüş yollarını ve A noktasının üzerinde olduğu adayı modelleyerek her köprüden yalnızca bir kez geçmek şartıyla başlangıç noktasına dönmenin mümkün olup olmadığını araştırmıştır.
· Bir çizgede tüm düğümler çift sayıda ayrıta sahipse yolu
başladığınız noktaya dönecek şekilde tamamlayabilirsiniz.
· Königsberg şehrinde her köprüden yalnızca bir kez geçmek şartıyla
başlangıç noktasına dönmek mümkün değildir.
İkinci cümlenin sebebi birincisidir. Königsberg çizgesinde derece dağılımı
A: 5, B: 3, C: 3, D: 3’tür — dördü
de tek. Tek dereceli tek bir düğüm bile başlangıca dönmeyi imkânsız kılar; burada dört tane
var.
Ders kitabı yalnızca “başa dönme” durumunu yazıyor. Euler’in
sonucunun tamamı, sınavda çok işe yarayan ikinci bir şık daha içerir:
Bağlantılı bir çizgede tek dereceli düğüm sayısı
· 0 ise → her ayrıttan bir kez geçip
başladığın yere dönebilirsin (kapalı yol).
· tam 2 ise → her ayrıttan bir kez geçebilirsin ama
tek dereceli düğümlerden birinden başlayıp ötekinde bitmen
gerekir (açık yol, başa dönemezsin).
· 2’den fazlaysa → hiçbir şekilde
olmaz.
Bir de değişmez bir gerçek var: tek dereceli düğüm sayısı her zaman
çifttir. Çünkü bütün derecelerin toplamı ayrıt sayısının iki katıdır, yani çifttir;
çift bir toplamda tek sayıların adedi tek olamaz. Bu yüzden “tam 1 tek dereceli düğüm” diye bir
durum hiç yoktur.
Königsberg problemini çözümleyen bir algoritma için
gerekli girdileri ve beklenen çıktıları tanımlatıyor. Yukarıdaki
kuralla birlikte cevap çok kısadır:
Girdi: düğüm listesi ve ayrıt listesi (hangi düğüm hangisine kaç
köprüyle bağlı).
İşlem: her düğümün derecesini say; tek derecelileri say.
Çıktı: tek dereceli düğüm sayısı 0 ise
“Mümkün, başa dönülür”; 2 ise
“Mümkün ama başa dönülmez”; değilse
“Mümkün değil”.
Dikkat çekici olan şu: algoritma rotayı denemez. Yedi köprü için
bütün yolları tek tek denemek binlerce ihtimal demektir; oysa
dört sayıya bakmak yetiyor. Ünite boyunca anlatılan
“algoritmik yaklaşım” tam olarak budur: problemi denemekten
kurtaracak bir ölçüt bulmak.
n kişilik bir grupta herkes diğerleriyle birer kez tokalaşıyor. Tablo: 2 kişi → 1, 3 → 3, 4 → 6, 5 → 10, 6 → 15. Peki n kişi için? Kaydırağı çek, hem çizgeyi hem sayıyı gör.
Sayma yoluyla: her kişi kendisi hariç
n − 1 kişiyle tokalaşır. n kişi olduğuna göre
n · (n − 1) tokalaşma sayılır — ama her tokalaşmayı
iki kez saymış oluruz (biri A’nın, biri B’nin gözünden). Bu
yüzden ikiye bölünür:
Toplam tokalaşma = n · (n − 1) / 2
Fark yoluyla: tabloya bak — 1, 3, 6, 10, 15. Aradaki farklar
2, 3, 4, 5. Yani gruba katılan her yeni kişi, mevcut
herkesle tokalaşır. n kişilik grubun cevabı, (n−1) kişilik
grubunkine n − 1 eklenerek bulunur:
1 + 2 + 3 + … + (n − 1) = n(n − 1)/2.
“Kişi sayısı artarsa algoritmanın performansı nasıl etkilenir?” diye sorulur. Cevap,
hangi algoritmayı seçtiğine bağlıdır ve bu ünitenin ana
fikridir:
· Tek tek sayan algoritma: bütün çiftleri gezer. n = 6 için 15
adım, n = 100 için 4950 adım, n = 1000 için
499 500 adım. Kişi sayısı 10 kat artınca iş yaklaşık
100 kat artar.
· Formülü kullanan algoritma: n ne olursa olsun
bir çıkarma, bir çarpma, bir bölme. n = 1000 ile n = 1 000 000
arasında hiçbir fark yoktur.
“Tablo mu şema mı, hangisi daha sistematik ve etkili?” sorusunun cevabı da budur:
tablo küçük n için görmeyi kolaylaştırır, cebirsel temsil her n
için çalışır.
İki ayrı problem aslında aynı fikri anlatıyor: n tane bozuk para içinden kütlesi farklı olanı bulmak ve 163 000 km²’lik bir bölgede Anadolu parsını bulmak. İkisinde de her adımda arama alanının büyük kısmını eleyip küçük bir parçayla devam ediyorsun. Fark: terazi üçe, harita ikiye böler.
İki kefeli bir terazi tek bir tartımda üç farklı sonuç verir:
sol ağır, sağ ağır,
denge. Bu yüzden paraları
üç eşit gruba ayırıp ikisini tartarsın:
· Denge varsa tartmadığın grup sahtedir.
· Denge yoksa ağır (ya da hafif) taraf sahtedir.
Her tartımda grup üçte bire indiğinden, n paradan tek bir para
kalana kadar geçen tartım sayısı:
en az tartım = ⌈log₃ n⌉
(⌈ ⌉ işareti “yukarı yuvarla” demektir: 3’ün kaçıncı kuvveti n’ye
yetişiyorsa o sayı.) Bu bağıntı ders kitabında yazmaz; orada tablo
doldurtup genellemeyi öğrenciye buldurur.
Kontrol Noktası’nda geçen madde tam da buna işaret ediyor:
“Kütlesi farklı olan paranın diğerlerine göre hafif ya da ağır
olması, tartım sayısını ve algoritmanın işleyişini etkilemektedir.”
Yön biliniyorsa (sahte para kesin hafif ya da kesin ağır):
⌈log₃ n⌉ tartım yeter.
Yön bilinmiyorsa her para için iki ihtimal doğar (hafif ya da
ağır) ve tek tartımın verebileceği bilgi aynı kalır. Bu durumda w tartımla en fazla
(3ʷ − 3) / 2 para arasından sahteyi ayırt edebilirsin.
8. sorudaki 1024 vida için: (3⁶ − 3)/2 = 363 < 1024,
(3⁷ − 3)/2 = 1092 ≥ 1024 ⇒ 7
tartım. Yön bilinse de 3⁶ = 729 < 1024 ≤ 3⁷ = 2187 olduğundan yine 7.
9. sorudaki 2187 kapsül ise ayrımı görmenin en iyi yeri:
yön biliniyorsa 2187 = 3⁷ olduğu için tam 7; “etken maddesi
eksik veya fazla” yani yön bilinmiyorsa 1092 < 2187
olduğundan 8 tartım gerekir.
Anadolu parsı, Türkiye’nin en büyük kedi türü olan; postu sarımsı,
üzeri siyah benekli, çevik, yırtıcı, etçil, memeli bir hayvandır. Hayvan bilimci Zehra, araştırma
ekibiyle birlikte nesli tükenmekte olan Anadolu parsının takibini
163 000 km²’lik bir bölgede yapmaktadır.
İkili arama, sıralanmış bir veri seti içinde bir elemanın
bulunmasını hızlı bir şekilde gerçekleştirmek için kullanılan bir arama algoritmasıdır.
Zehra her adımda araziyi iki eşit parçaya bölüp sadece bir
tarafında parsın olup olmadığını kontrol edecek; parsın tespit edildiği taraf yeniden ikiye
bölünecek ve arama alanı 1 km²’den az olduğunda parsın tespit
edildiği varsayılacaktır. Zehra her gün sadece bir alanı kontrol etmektedir.
Algoritmik doğal dil: 1. adım Başla · 2. adım alanın ikiye
bölünmesi (kullanıcıdan bölgenin alanını al) · 3. adım ilk yarının kontrol edilmesi (pars
buradaysa bu bölgeyi detaylı incele, değilse diğer yarıya geç) · 4. adım incelenen alanın
büyüklüğünün kontrolü (alan 1 km²’den küçükse parsın tespit edildiğini varsay, değilse 2. adıma
dön) · 5. adım Bitir.
Kaç gün sürer? Her gün alan yarıya iner:
163 000 → 81 500 → 40 750 → … Alanın 1 km²’nin altına inmesi için
2ᵏ > 163 000 olmalıdır. 2¹⁷ = 131 072 < 163 000 ve
2¹⁸ = 262 144 > 163 000 olduğundan 18 adım, yani
18 gün gerekir.
Bu sayının küçüklüğü şaşırtıcıdır: 163 000 km²’yi 1 km²’lik
karelere bölseydin 163 000 gün, yani 446 yıl ederdi. Bölerek arama, aynı işi
18 günde bitirir. “Algoritmik yaklaşımın gücü” denen şey
bu farktır.
Çizgenin ayrıtlarına sayı yazarsan (mesafe, süre, maliyet) yeni bir soru sorabilirsin: en ucuz tur hangisi? Ayrıtlara yön verirsen bambaşka bir soru çıkar: bu ağda kim daha etkili?
Bir çöp arabası; sorumluluk sahasındaki A, B, C ve D çöp
depoları arasında bir yolculuk yapacaktır. A’dan hareket edip B, C
ve D’yi tek bir kez ziyaret ettikten sonra yine A’ya dönecektir. Mesafe tablosu
(birim):
A–B: 133 · B–C: 96 · C–A: 100 · C–D: 103 · D–A: 70 · B–D: 200
Amaç, yakıt tüketimini daha temiz bir çevre için azaltmak: yani
gezilen mesafelerin toplamı en az olmalı.
A’dan başlayıp A’ya dönen turlar üç tanedir (ters yönleri aynı turu verir):
· A–B–C–D–A = 133 + 96 + 103 + 70 = 402
· A–B–D–C–A = 133 + 200 + 103 + 100 = 536
· A–C–B–D–A = 100 + 96 + 200 + 70 = 466
En kısa tur: A–B–C–D–A, 402 birim.
Bu problemde akla ilk gelen algoritma şudur: bulunduğun yerden en
yakın ziyaret edilmemiş depoya git. A’dan başla → en yakın D (70) → D’den en yakın C (103) →
C’den B (96) → B’den A (133). Toplam:
70 + 103 + 96 + 133 = 402. Bu problemde
doğru cevabı verdi.
Ama bu bir tesadüftür. “En yakına git” algoritması
bir sonraki adıma bakar, turun tamamına bakmaz; sonda kalan
uzun ayrıta mecbur bırakabilir. 7. soru (“depo sayısı artarsa performans nasıl
etkilenir?”) tam bu yüzden sorulmuştur.
Bütün turları denemek de bir yol ama çok çabuk büyür:
4 depo için 3, 5 depo için 12, 6 depo için 60, 10 depo için
181 440 farklı tur vardır. Bu yüzden gerçek hayatta
kesin en iyi yerine yeterince
iyi sonuç veren algoritmalar kullanılır — “alternatif algoritma yaklaşımları neler
olabilir?” sorusunun cevabı budur.
Bir veri merkezinde üç sunucu (A, B, C) ve
üç veri deposu (Ç, D, E) vardır. Her sunucu, her veri deposundan
yüksek hızda ve güvenilir şekilde veri alışverişi yapabilmelidir. Tasarım kuralı gereği
sunucular ve depolar arasında çapraz (kesişme) bağlantı
olmamalıdır.
Bu, ünitenin en zor sorusudur ve cevabı şaşırtıcıdır:
bu çizge kâğıt üzerinde kesişmeden çizilemez. Üç sunucu ile üç
deponun hepsini birbirine bağlayan çizge 9 ayrıt içerir ve
matematikte düzlemsel olmayan çizgelerin en bilinen iki örneğinden
biridir. Kaç kez denersen dene, en az bir kesişme kalır.
Bunun pratikteki karşılığı şudur: bu bağlantıları tek bir kat
üzerine döşeyemezsin. Gerçek veri merkezlerinde ve devre kartlarında sorun tam olarak böyle
çözülür — kablolar birden fazla katmana ayrılır ya da araya bir
anahtar (switch) konur. Bir problemin “çözümü yok” olduğunu
ispatlamak da bir algoritmik sonuçtur; Euler’in Königsberg
cevabı da tam olarak buydu.
Sosyal ağ hesabına giriş yaparken belirlediğin şifre; “Amerikan Bilgi Değişimi İçin Standart Kod” ifadesinin İngilizce karşılığının baş harflerinden elde edilen ASCII karakter kümesinden seçilen harfler, sayılar ve sembollerden oluşur. ASCII karakter kümesindeki her bir karakter, belirli bir sayısal değerle temsil edilir.
1. adım: ASCII karakter kümesi yardımıyla her karakter kendisine
karşılık gelen ASCII değerine dönüştürülür.
A → 65 · L → 76 · ters eğik çizgi → 92 · T → 84 · z → 122
2. adım: Bu değerlerin bilgisayar sistemindeki karşılıkları
bulunur.
1000001 · 1001100 · 1011100 · 1010100 · 1111010
Dönüşüm şöyle: 65 sayısı 64 + 1 olarak yazılır; sürekli ikiye bölerek
1000001 elde edilir.
Bilgisayar donanımının elektrik sinyallerini iki durum (açık veya
kapalı) kullanarak kolayca temsil edebilmesi tercih edilir; bu yüzden bilgisayarlarda tüm
veriler 0’lar ve 1’ler olarak saklanır ve işlenir.
Gerçek siber güvenlik sistemlerinde parolalar, bilgisayarda
doğrudan ASCII veya ikilik (binary) hâlleriyle saklanmaz. Bunun yerine parolalar özel
matematiksel işlemlerden (örneğin SHA-256 gibi algoritmalar) geçirilerek dönüştürülür ve sadece
bu dönüştürülmüş hâli, yani özeti sistemde saklanır.
Sebebi şu: ASCII bir şifreleme değil, bir kodlamadır.
“z” harfinin 122 olduğu herkesin bildiği bir bilgidir; 122’den z’ye geri dönmek
bir bakış meselesidir. Özet alan algoritmalar ise
tek yönlüdür: ileri gitmesi kolay, geri dönmesi pratikte
imkânsızdır — tıpkı bir önceki ünitedeki RSA gibi.
ASCII karakter kümesinin standartlaştırılması, farklı bilgisayar ve
ağ sistemlerinin birbiriyle daha kolay iletişim kurmasını sağlamıştır ancak ASCII yalnızca
İngiliz alfabesi ve temel sembollerle sınırlıdır. Bu nedenle
Genişletilmiş ASCII ve Unicode
gibi daha kapsamlı kodlama sistemleri geliştirilmiştir. Unicode, dünya genelindeki hemen hemen
tüm dilleri destekleyecek şekilde tasarlanmıştır ve
ASCII karakter kümesinin doğrudan bir uzantısı olarak
görülebilir. Türkçedeki ç, ğ, ı, ö, ş, ü harflerinin ASCII tablosunda
bulunmamasının sebebi de budur.
Sorular karışık sırayla geliyor. Dereceyi say, formülü uygula, en kısa turu bul.
Bir problemi düğüm ve ayrıtla çizebiliyorsan, bu ünitedeki algoritmalar sana çalışır. Aşağıdaki dokuz sahnenin hepsi böyle.
Sosyal medyada takip yönlü bir ayrıttır: sen birini takip
edersin, o seni etmeyebilir. Tokalaşma ise yönsüzdür; iki
taraflıdır.
Bu yüzden 20 kişilik bir sınıfta olabilecek en fazla
arkadaşlık sayısı 20·19/2 = 190,
en fazla takip sayısı ise
380’dir — tam iki katı.
PageRank örneğinde de aynı ayrım var: A → B oku varken B → A oku yok.
Etkiyi ölçen şey, gelen oklardır.
Arkadaşın 1 ile 1000 arasında bir sayı tuttu, sen “büyük mü küçük mü?” diye soruyorsun.
Ortadan sorarsan (500, sonra 250 ya da 750 …) en fazla
on soru yeter; çünkü 2¹⁰ = 1024 > 1000.
Bu, Zehra’nın pars araması ile aynı algoritmadır. Tek tek
saysaydın en kötü durumda bin kez sormak gerekirdi.
Sınavda dikkat: “en fazla kaç adım?” diye sorulur, cevap
⌈log₂ n⌉’dir. 1 milyon için sadece
20 adım yeter.
Bir şehir hattı haritası ders kitabındaki çizgenin aynısıdır:
duraklar düğüm, hatlar ayrıt. Aktarma yapılan büyük duraklar
yüksek dereceli düğümlerdir.
Telefonundaki harita uygulaması “en hızlı rota” derken çöp arabası problemindekine benzer bir iş
yapar; farkı, ayrıtlara mesafe yerine
süre yazmasıdır — ve süre trafiğe göre değiştiği için ağırlıklar
gün içinde değişir.
Bu yüzden aynı iki nokta arasında sabah ve akşam farklı rota önerilebilir:
çizge aynı, ağırlıklar farklı.
Çocukken çizilen “kalem kaldırmadan zarf çizme” oyununun cevabı bu ünitede:
tek dereceli düğüm sayısına bak.
0 ise her yerden başlayabilir ve başladığın yere dönersin. Tam 2
ise mutlaka tek dereceli düğümlerden birinden başlaman
gerekir; yanlış yerden başlarsan çizim tamamlanmaz. 2’den fazlaysa hiç uğraşma.
ipucunun aynısı: “başlangıç noktasının rotanız
üzerindeki etkisini değerlendiriniz.” Başlangıç noktası, bazı çizgelerde
her şeyi belirler.
Sınıflar arası turnuvada 8 takım herkes herkesle oynayacaksa
maç sayısı 8·7/2 = 28’dir — tokalaşma formülünün ta
kendisi.
Eleme usulü olsaydı çok daha az maç olurdu: her maç bir takımı
eler, 8 takımdan 7’si elenmelidir, yani 7 maç.
Aynı turnuva, iki farklı formatta 28’e karşı 7 maç.
Format seçmek, algoritma seçmektir; birincisi adil, ikincisi hızlıdır.
Seri bağlı 32 ampullü bir süs zincirinde biri bozuk ve zincir hiç yanmıyor. Tek tek denersen
en kötü durumda 32 deneme.
Zinciri ortadan ikiye ayırıp hangi yarının çalışmadığına bakarsan
5 denemede bulursun: 2⁵ = 32.
Bu, tartım probleminin ikiye bölen hâlidir. Terazi üçe
böldüğü için daha da hızlıydı: 32 için ⌈log₃ 32⌉ =
4 tartım yeterdi.
Müzik uygulamasının “bunu dinleyenler şunu da dinledi” önerisi bir
çizge üzerinde yürümedir: şarkılar düğüm, birlikte dinlenmeler
ayrıt.
Çok bağlantılı bir şarkı, PageRank’teki kullanıcı C gibi öne
çıkar ve daha çok kişiye önerilir. Yeni çıkmış bir şarkı ise kullanıcı E gibidir: kimse ona
bağlanmadığı için görünmez.
Bu, “zengin daha zengin olur” döngüsü yaratır; uygulamalar bunu kırmak için önerilere
rastgelelik ekler.
Bir kuryenin 6 adrese uğrayıp depoya dönmesi, çöp arabası problemidir.
6 adres için farklı tur sayısı 60; 10 adres için
181 440; 15 adres için
43 milyardan fazla.
Bu yüzden kargo firmaları en iyi turu aramaz;
iyi bir tur bulup zamanında dağıtır.
“Performansı artırmak için hangi stratejileri önerirsiniz?” sorusunun gerçek hayattaki
cevabı budur: şehri bölgelere ayır, her bölgeyi ayrı ayrı
çöz.
Performans görevi, sıralama algoritmalarını karşılaştırmayı istiyor ve bir ipucu
veriyor: büyük veri kümeleri için Quick Sort, küçük veri kümeleri
için Bubble Sort tercih edebilirsiniz.
25 kâğıdı numaraya göre dizerken sen de aslında bir algoritma seçersin: teker teker doğru yere
sokuşturmak (küçük destede hızlı) ya da desteyi ikiye bölüp ayrı ayrı sıralayıp birleştirmek
(büyük destede çok daha hızlı).
Ve şu kural her yerde geçerli: sıralı bir listede arama çok
hızlıdır. Kâğıtları önce sıralamak, sonra 300 kez arama yapmak; hiç sıralamadan 300 kez
taramaktan kısa sürer.
48 soruluk test · çizge kuramı ve derece kuralı, Königsberg problemi, tokalaşma sayısının n(n−1)/2 temsili, üçe bölen tartım algoritması, ikili arama, en kısa tur, PageRank ve ASCII ile ikilik gösterim
Nesneler arasındaki ilişkileri düğüm (nokta) ve
ayrıt (çizgi) ile inceler.
Sosyal ağ, yol bulma, elektrik devresi — hepsi çizgeyle modellenir.
Tüm düğümler çift dereceliyse her ayrıttan bir kez geçip
başladığın düğüme dönebilirsin.
Tek dereceli düğüm sayısı 2 ise geçersin ama dönemezsin;
daha fazlaysa hiç olmaz.
Euler, 1736, yedi köprü.
Dereceler 5, 3, 3, 3 — dördü de tek.
Başlangıç noktasına dönmek mümkün değildir.
2 → 1, 3 → 3, 4 → 6, 5 → 10, 6 → 15
n kişi → n(n − 1)/2
Aynı sayı, tam çizgenin ayrıt sayısıdır.
Terazinin üç cevabı var ⇒ ⌈log₃ n⌉ tartım.
n: 2→1 · 3→1 · 4→2 · 8→2 · 9→2 · 16→3 · 27→3 · 32→4 · 64→4 · 81→4
Hafif mi ağır mı bilinmiyorsa bir tartım daha gerekebilir.
Sıralanmış bir veri setinde hızlı arama.
Her adımda alan yarıya iner ⇒ ⌈log₂ n⌉ adım.
163 000 km² → 1 km²: 18 gün.
A–B–C–D–A = 402 (en kısa)
A–C–B–D–A = 466 · A–B–D–C–A = 536
Depo sayısı artınca tur sayısı patlar.
Düğümlerin önemini ölçer; ayrıtlar
yönlüdür.
A 0,269 · B 0,157 · C 0,277 (en etkili) · D 0,266 ·
E 0,03 (en düşük)
A = 65 = 1000001 · L = 76 · T = 84 · z = 122
Bilgisayar iki durum (açık/kapalı) kullanır.
Parolalar ASCII olarak değil, özeti alınarak saklanır.