- Donald Knuth, 2024 Stanford Noel konferansında yönlü graflardaki strong components ve weak components konularını ele alıyor; Tarjan’ın strong components algoritmasını en sevdiği algoritma olarak seçiyor
- Bir strong component tek bir düğüme indirgenince döngüsüz bir DAG oluşur; algoritma, sink strong component’i bulup kaldıran bir akışla çalışır
- Buradaki weak component, yönleri yok sayan bağlı bileşen değil; strong components’ı yeniden gruplayarak linear order oluşturan daha genel bir partition’dır
- Tarjan algoritması DFS sırasında tree arc, back arc, loop, forward arc ve cross arc ayrımı yapar; strong components ile bunların topolojik sıralamasını birlikte elde eder
- Knuth’un vurguladığı çekicilik yalnızca prosedürde değil, gerekli karar bilgisini tam doğru anda erişilebilir kılacak şekilde düzenlenmiş derin veri yapısında yatar
Konferansın çıkış noktası ve Knuth’un yeni kitabı
- Konferansın başındaki güncel durum, yeni kitabı Constraint Satisfaction etrafında şekilleniyor
- İç taslağı bir gün önce yayınevine göndermiş; ön sipariş de mümkün hale gelmiş
- Noel’den önce basılması zor olabilir; resmî çıkış tarihi 3 Şubat gibi görünüyor
- Kitabın içinde baskı tarihi Ocak olarak görünüyor ve son 5 yıl boyunca Knuth’un ana projesi olmuş
- Bu konunun, yani Strong Components and Weak Components’ın daha ayrıntılı içeriği pre-fascicle 12A’da yer alıyor
- Mevcut kitap volume 4 Fascicle 7; önceki fascicle’lar volume 4A ve 4B olarak ciltli yayımlandı
- Bu içerik ileride volume 4C’nin ilk üçte birini oluşturacak
- Konferansın alt başlığı “Which algorithm do you love the most?” sorusuna yakın
- Knuth normalde “en sevdiğin algoritma”yı seçme sorusundan hoşlanmadığını, ancak bu durumda net yanıtın Tarjan’ın strong components algoritması olduğunu söylüyor
- 1973’te bu prosedürü öğrendiğinde, veri yapılarının da teoremler veya algoritmalar gibi “derin” olabileceğini ilk kez anladığını belirtiyor
Strong component ile weak component arasındaki fark
- Yönlü graf, düğümlerden ve yönlü oklardan oluşur
- İki düğüm u ve v birbirlerine ulaşabiliyorsa aynı strong component içindedir
- Bir döngü üzerindeki düğümlerin tümü aynı strong component’e dahildir
- Birçok yerden yol gelse bile dışarı çıkışı olmayan bir düğüm tek başına bir strong component olabilir
- Knuth’un kullandığı weak component, yönleri yok sayan undirected component’ten farklıdır
- Yönleri yok sayınca bağlanan bileşene “undirected component” denmesi gerektiği görüşündedir
- weak component, strong components’ı indirgedikten sonra elde edilen DAG’i yeniden partition ederek bütünün doğrusal bir sıra oluşturmasını sağlayan kavramdır
- strong components’ın her biri tek bir “super vertex”e indirgenirse döngüsüz bir graf oluşur
- Bu, kısmi sıra (partial order) olarak görülebilir
- weak components’a kadar indirgenirse total order veya linear order oluşur
- Topolojik sıralama (topological sorting) ile de doğrudan bağlantılıdır
- Bir x, tüm topological sorting’lerde her zaman y’den önce geliyorsa ikisi farklı weak component’lerdedir
- Bir sıralamada x y’den önce, başka bir sıralamada y x’ten önce gelebiliyorsa ikisi aynı weak component’tedir
- Knuth bunu mutual incomparability ile ilişkilendiriyor
Kavramın ve algoritmanın tarihi
- weak component kavramı; Knuth, Ron Graham ve Mazkin olarak yazılan bir profesörün başka bir problem üzerine mektuplaşmaları sırasında ortaya çıktı
- Mazkin’in 28 Şubat 1970’te Graham’a gönderdiği mektupta, partition ile total order elde etme içeriği vardı
- Aralık 1970’te Knuth, Graham’a üç kişinin her birinin farklı yaklaşımlarla daha genel bir sonucu kanıtladığını yazdı
- Knuth, Mazkin’i ortak yazar olarak dahil etmeye karar verdi; ancak hemen ardından Mazkin’in kalp kriziyle aniden öldüğü haberini aldı
- İlgili makale 1972’de Discrete Mathematics volume 2 number 1’de yayımlandı
- O dönemde Discrete Mathematics yeni başlamış bir dergiydi ve sonrasında ne kadar çok iyi makalenin yayımlanacağını kimse öngörmemişti
- Tarjan’ın strong components algoritması 1972’de SIAM Journal on Computing volume 1 number 2’de yayımlandı
- Tarjan o sırada lisansüstü öğrencisiydi ve bu makale yayın listesinde 6. sıradaydı
- Knuth bu makaleyi Ocak 1973’te okuyup algoritmayı sevmeye başladı
- Aho, Hopcroft, Ullman’ın algoritma ders kitabında da Tarjan algoritması iyi biçimde düzenlenmiştir
- Hopcroft, Stanford’daki sabatik yılı sırasında Tarjan ile aynı ofisi paylaşarak birçok algoritma geliştirdi
- Hopcroft’un undirected graph’ların biconnected components algoritması için bir fikri vardı; Tarjan benzer bir fikri directed graph’ların strong components’ına uyguladı
- Shimon Even’ın kitabı, Tarjan algoritmasının low point kavramını ele alır
- Component bulmak için low point gerekir, low point’i hesaplamak için de component’i bilmek gerekir gibi görünen döngüsel durumu Tarjan çözdü
DFS ile strong components bulma yöntemi
- Knuth graf aramayı mağara keşfine benzetiyor
- Her room bir vertex, her room’dan gidilebilecek diğer room’ların listesi de outgoing arc’tır
- Bilgisayar çizime bakmaz; yalnızca vertex listesi ve arc listesine bakarak arama yapar
- Temel arama yöntemi depth-first search’tür
- Henüz görülmemiş outgoing arc’ı takip ederek derine iner
- Gidecek yer kalmayınca önceki konuma geri döner
- Daha önce ziyaret edilmiş bir vertex ile karşılaşınca o arc’ın türünü belirler
- DFS’te arc beş türe ayrılır
- tree arc: Yeni bir vertex’i ilk kez keşfederken oluşturulan DFS tree’nin arc’ı
- back arc: ancestor’a geri dönen arc
- loop: Kendisine giden arc’tır ve strong components üzerinde etkisi yoktur
- forward arc: descendant’a giden arc
- cross arc: Ne ancestor ne de descendant olan bir vertex’e giden arc
- Algoritma her strong component keşfettiğinde, henüz kalan graftaki sink component’i bulur
- Sonlu DAG’de her zaman bir sink vardır
- sink strong component’i kaldırıp kalan graf üzerinde yeniden arama yaparak ilerler
- Bu süreçte strong components bulunurken aynı zamanda topological sort da elde edilir
- Performansının çok hızlı olduğu belirtiliyor
- M arc ve N vertex için en kötü durumda memory access sayısı 5M + 17N düzeyindedir
- arc listesinin sonunu kontrol etme, pointer güncelleme gibi işlemler de bu sayıya dahildir
Weak components, iyileştirilmiş sürüm ve uygulama
- weak components algoritması da strong components bulma süreciyle birlikte yürütülebilir
- strong components’ın sağdan sola, yani sink’ten başlayarak keşfedilmesi özelliğinden yararlanır
- Yeni bir strong component sola eklendiğinde, mevcut weak components ile nasıl birleşeceğine karar verir
- weak component kararında her component içindeki source ve sink önemlidir
- Bir weak component’in tüm sink’lerinin, bir sonraki weak component’in tüm source’larına arc’ı olmalıdır
- Bu koşul weak components’a sahip olmanın gerek ve yeter şartıdır
- Programlarken yalnızca source’u izlemekle de update yapılabilir
- Tarjan, 1974’te Information Processing Letters volume 3 number 1’de weak components bulmaya yönelik 3 sayfalık bir algoritma makalesi yayımladı
- Knuth bu içeriği kendi pre-fascicle 12A’sında düzenledi
- worst-case linear time garantileyecek kadar yeterli data structure’ı korumak basit değildir
- Dijkstra da strong components problemini ele aldı
- Dijkstra’nın kitabının 25. bölümü “Finding the maximal strong components in a directed graph” konusunu işler
- Dijkstra, sink strong component’i kaldırarak ilerleyen yapıyı kullandı, ancak Tarjan’ın low point sadeleştirmesine ulaşamadı
- Dijkstra’nın çözümü, yapıyı izlemek için dört yeni array getirir
- Knuth ve Tarjan yakın dönemde mevcut algoritmayı yeniden inceleyerek daha iyi tanımlar ve iyileştirilmiş bir sürüm oluşturdu
- Kurki-Suonio’nun 1970’lerdeki fikrini temel alarak düzelttiler, ancak özgün makalede bir fallacy vardı
- Eski yöntemde arc başına yaklaşık 7 erişim olan düzeyi yaklaşık 5’e indirdiler
- Bazı field’ları birleştirerek daha karmaşık ama daha hızlı bir biçime getirdiler; buna “premature optimization” değil “post-mature optimization” diye şaka yapıyor
- Uygulama CWEB programı olarak sunuluyor
- Program adı olarak Tarjan strong and weak, Tarjan strong anılıyor
- Girdi, Stanford GraphBase formatında bir graph’tır
- Knuth, web sitesindeki programları daha kolay bulunacak şekilde düzenleyeceğini ve 2022’den beri güncellenmemiş olma durumunu düzelteceğini söylüyor
- Stanford GraphBase’te, Roget’s thesaurus category’lerinden yaklaşık 1.000 tanesini vertex, synonym veya antonym ilişkilerini de arc olarak alan bir directed graph örneği bulunuyor
1 yorum
Hacker News yorumları
2022'de San Francisco'yu ziyaret ettiğimde Stanford kampüsünü gezerken, sessiz ve boş bir yaz dönemi binasının koridorlarından geçip çıkmak üzereyken tesadüfen Knuth'un ofisini gördüm
Ününe kıyasla şaşırtıcı derecede küçüktü; dönüp bir daha baktım ama tam da onun mütevazı kişiliğine uygun bir mekân gibi hissettirdi
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
Ödül çekinden de bir değil, iki tane var. Küçük yazım hatalarıydı ama bu iki belgeye sahip olmak gerçekten harika
Kimse kötüye kullanmaz ama kendi ofisimin fotoğrafının haberim olmadan internete konduğunu öğrenmek beni epey ürpertirdi
Boş zamanlarımda TAOCP 4A ve 4B okuyorum; gerçekten mükemmel, şiddetle tavsiye ederim.
Programcıların çoğu için pratik olmayabilir ama Knuth’un algoritma tasarlama ve açıklama biçimi şaşırtıcı ve benzersiz.
Özellikle 4B’deki Dancing Links uygulaması, ünlü makaleden bu yana ciddi biçimde güncellenmiş; zarif ve güzel bir veri yapısı olmasının yanında çok da hızlı. 80’lerinde bile hâlâ muazzam.
Bizim ölçeğimiz için gereken maliyeti hesaplayınca on milyonlarca dolar çıkıyordu, oysa Route 53’ün tüm altyapı bütçesi on binlerce dolar düzeyindeydi. Edge’de, diski arızalanmış CloudFront sunucularını ad sunucusu olarak yeniden kullanıyorduk; API sunucuları da mütevazıydı, ekip de yaklaşık 6 kişiydi. AWS tarzı “dişe diş zorlama”, neredeyse hiç para harcamadan, aşağı yönlü riski azaltarak ve hızlıca işi bitirmek demekti.
Bu yüzden packet scrubber’lar için on milyonlarca dolar isteyemezdik; gelmeleri de uzun sürecekti ve belirli bir tedarikçiye fazla bağımlı kalabilirdik.
Başta Route 53 ad sunucularını özel IP aralıklarında çalıştırarak bir ölçüde yalıtmaya karar verdik; özel ağ bağlantılarıyla Amazon’un diğer altyapısının etkilenmemesini sağlayabiliyorduk. Ancak Route 53 müşterilerinin kendi aralarında kader birliği yapması sorununu çözmüyordu; gerçek plan da “bir sorun olursa mevcut ağ ve sistem araçlarıyla çok iyi filtreleme yaparız” düzeyindeydi.
O yılın yaz başında Knuth’un 4A ile ilgili en yeni fasikülünü okuyup kombinatoryal algoritmalara dalmıştım. Bir gece, çok sayıda sanal ad sunucusu oluşturursak her müşteriye dört sanal ad sunucusundan oluşan benzersiz bir kombinasyon atayabileceğimiz fikri bir anda “şimşek gibi” çaktı. Örtüşme derecesini de kontrol edebiliyorduk; kabaca 2.000 ad sunucusuyla herhangi iki müşterinin ikiden fazla ad sunucusunu paylaşmayacağını garanti edebileceğimizi hızlıca hesapladım. Deneylere göre bir alan adı, iki ad sunucusuna ulaşılamasa bile düzgün çözümleniyordu; ama daha fazlasında sorun çıkıyordu, bu yüzden bu sayı önemliydi.
IP atayan özyinelemeli arama algoritması doğrudan 4A’daki algoritmalardan ilham aldı ve müşteri alan adlarından bağımsız iki ek yalıtım boyutu sağladı. Müşteri, dört bağımsız “stripe” içinden dört ad sunucusu alıyordu; bunlar ad sunucusu adlarında kullanılan farklı üst düzey alan adlarına (co.uk, com, net, org) karşılık geliyordu. Böylece bunlardan bir üst düzey alan adında DNSSEC hatası gibi bir sorun yaşansa bile yalnızca tek bir ad sunucusu etkileniyordu.
Ayrıca bunların dört bağımsız “braid”den gelmesini sağlayarak herhangi iki ad sunucusunun belirli bir ağ yolunu veya fiziksel donanımı paylaşmamasını garanti edebiliyorduk. İstatistik ve kriptografi geçmişim sayesinde kombinatorikleri biliyordum ama 4A’yı okumamış olsaydım böyle bir tasarım yapamazdım.
Hiçbir çözüm beni bunun kadar heyecanlandırmamıştı. Çünkü fiilen ek altyapı maliyeti olmadan müşteri alan adları arasında kanıtlanabilir, ağ IP düzeyinde yalıtım sağlıyordu. Matematikti. Tamamen ücretsiz değildi: 2.000 anycast IP adresi kullanmamız gerekiyordu ve birçok üst düzey alan adının ad sunucusu kaydı ile glue kayıtlarını zorunlu kılma biçimi nedeniyle 512 alan adı da kaydetmemiz gerekti. Kayıt kuruluşuyla bu süreci yürütmek epey eğlenceliydi ama sonunda başardık.
Bu yönteme Shuffle Sharding adını verdik; icattan çok keşfe yakındı. Rastgele yerleştirme kullanan birçok çok kiracılı sistem bir tür shuffle sharding elde eder; Stochastic Fair Blue gibi ağ filtreleme teknikleri de zaman tabanlı hashing ile benzer etki yaratır. Ama bizim uygulayabildiğimiz düzeyde kontrol sağlayan aynı yöntemi hiç görmemiştim; yalnızca çağıranı değil, “başkası adına çağırma” örüntüsünde çağıranın çağıranını da kapsayacak daha fazla seviyeyi yalıtan özyinelemeli iç içe shuffle sharding’e kadar genişletebiliyorduk.
Birkaç yıl sonra minnettarlıkla Knuth’un Noel konferansını bizzat izlemeye gittim ve en ön sıraya oturdum. Neyin ilham vereceğini bilemeyeceğiniz için bugün hâlâ Knuth’un yayımladığı her şeyi okuyorum. Buna org besteleri de dahil.
Bu yüzden Knuth’un kitaplarının programcılar için şaşırtıcı derecede pratik olduğunu düşünüyorum. Düşünce ufkunu genişletiyor ve anlayışı derinleştiriyor; daha ne istenebilir ki?
Orijinal Dancing Links makalesi en sevdiğim makalelerden biri. “Bu süreç, küresel veri yapısındaki işaretçi değişkenlerine incelikle koreografisi yapılmış bir dans yaptırır” gibi cümlelerde Knuth’un algoritma sevgisi olduğu gibi görülüyor.
Bunu çapraz bulmaca üretiminde kullanıyorum; yatay ve dikey kelimelerin ızgaranın exact cover’ını oluşturmasını sağlayan bir yöntem.
Güncellenmiş algoritmanın daha az bellek kullanıp kullanmadığını merak ediyorum.
Bu büyük problemde yaklaşık 100 milyon çözüm olduğu tahmin ediliyor; saniyede 100 tane bulsa bile bitirmesi yaklaşık on gün sürer.
Üzerinde çalıştığım problem, ‘Fancy Tetris Houten Puzzel’de aynı renkteki parçaların en az bir kenar boyunca temas ederek tamamının bağlı olduğu durumların sayısını saymak.
Bu exact cover problemini çözmek için belleğe daha az duyarlı başka algoritmaları da düşünüyorum.
Bunu, bilgisayar bilimi literatürünü ancak yakın zamanda okumaya başlamış biri olarak soruyorum.
Birkaç yıl önce San Francisco’ya gittiğimde Donald Knuth’un hâlâ hayatta olmasının yanı sıra Stanford’da her yıl konferans vermeye devam ettiğini öğrenince şaşırmıştım.
Kampüste binayı bulup, takip etmesi neredeyse zor bir konu hakkında konuşmasını bizzat izlediğim o gece uzun süre aklımda kalacak. Donald Knuth gerçekten bir efsane.
Ekipten biri geçen ay Seminumerical Algorithms’te bir hata bulup 1 hexadecimal dollar ödül çeki aldı; çek, orijinal e-posta çıktısının üzerine elle yazılmış notlarla birlikte geldi.
Donald Knuth’ta bana en çok ilham veren şey, onlarca yıldır süren adanmışlığı ve disiplini.
Sürekli proje, dil ve dağıtım değiştiren biri olarak ondan öğreneceğim gerçekten çok şey var.
Kıyafeti çok canlı ve parlak; eski köylerde giyilen dünya/folk kıyafetleri gibi görünüyor ama İran tarzı mı, Slav tarzı mı, arada bir şey mi tam çıkaramadım.
Daha iyi tahmin edebilecek biri var mı?
Hatırladıklarım bulanık; eşiyle de bağlantılı olabilir. 2010'ların ortalarından sonraki konuşmalarında sıkça giyiyor gibi ve bir yerlerde açıklaması olmalı.
2012'de Manchester Town Hall önündeki meydana Olimpiyat meşalesinin gelişini izlemek için pencere pervazına tırmanmaya çalışan Knuth'un yanında bulunmuştum. Onunla konuştum; pencereden düşecek diye bir an elimi uzattım ama sorun olmadı. Bana meraklı, soruları ve zekâsı parlayan, yaşından genç görünen biri gibi gelmişti.
İkimiz de Alan Turing'in doğumunun 100. yılı anma etkinliğine katılıyorduk; Knuth, Gary Kasparov, Fred Brooks, Vint Cerf gibi bilgisayar biliminin devleriyle aynı odada olmak şaşırtıcıydı. Öğle arasında Olimpiyat meşalesi dışarıdaki meydana geldi ve o kendini tutamayıp izlemeye gitti. Buna heyecanlanan tek kişi oymuş gibi görünüyordu.
O akşam yemekte konuşma yaptı; daha sonra 4B yeni yayımlandığında Manchester'da tekrar karşılaştığımızda kitabımı imzalamasını isteyince, beni önceki etkinlikten belli belirsiz tanıdı.
Bu hikâyeyi anlatma nedenim, gömleğinin çok daha eklektik ve meraklı bir zihne işaret ettiğini düşünmem. Bunun kanıtlarını başka yerlerde de açıkça gördüm.
Bu yüzden geleneksel Sami kıyafetine duyduğu sevgi oradan gelmiş olabilir.
[0]: https://youtu.be/jB0aeePskBg
https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
Kontrol ettim, 87 yaşındaymış. Donald Knuth 10 Ocak 1938 doğumlu.
Vay be.
Knuth hâlâ şaşırtıcı.
Ama Stanford'da bu düzeyde bir materyale yakışır ses kaydını kimsenin düzgünce halledememiş olması çok şaşırtıcı ve hayal kırıklığı yaratıcı. Sanki biri cebindeki kayıt cihazıyla kaydetmiş gibi duyuluyor.
Knuth'un yaşlılık sesinden bahsetmiyorum; durup izleyicilerden soru aldığında ses kalitesinin ne kadar kötü olduğuna bakmanız yeterli.
Böyle videolar, bilgisayarları başta neden sevdiğimi bana hatırlatıyor.
Hâlâ bu kadar keskin olması oldukça şaşırtıcı. Ne yazık ki ben 20 küsur yıl önce lisans öğrencisiyken artık ders vermiyordu.
Soruları ele alış biçimini seviyorum: https://youtu.be/Hi8r_63LGyg?t=827
Ne sorulduğunu anlamaya zaman ayırıyor ve çok net yanıt veriyor.