Knuth dinleyicilerine şaka yaparak, “Benim gibi eski insanlar, kibrimiz nedeniyle, tüm önemli veri yapılarının 1970 veya 1980’de iyice anlaşıldığını düşünürdük.” diye şaka yaptı. “Yani daha fazla bir şey öğrenmenize gerek yok.“
“Ama bugün bahsettiğim şey üç yıl önce öğrendiğim bir şey…”
Bunların hepsi her zaman keşfedilecek daha eğlenceli matematiksel sürprizlerin olduğunun kanıtı. 60 yılı aşkın bir süre önce, 1962’de, 24 yaşındaki Donald Knuth ilk olarak Bilgisayar Programlama Sanatı‘nı yazmaya başladı; kapsamlı bir algoritma analizi olan bu kitabı 2023’te hâlâ tamamlamaya çalışıyor.
Ve 30 yıl önce Knuth, her Aralık ayında Stanford öğrencilerinin izleyicileri önünde nadir canlı performanslar sergilemeye başladı. Beş yıl önce New York Times, Knuth’u “algoritmik dünyanın ruh rehberi” olarak adlandırmıştı ve onu canlı görmenin, kendi kişisel düşünceli analiz markasını paylaşmanın özel bir yanı vardı.
Onlarca yılın ardından Knuth, gülümseyerek nazik meraklılığını göstermeye devam etti.
Yakın zamanda Stanford, Knuth’un geçmiş Noel derslerinden birkaç on yılı ve 1985’ten itibaren “‘Aha’ Oturumları” (matematiksel problem çözme kursları) başlıklı 22 videodan oluşan bir seriyi yükledi. Ayrıca 1981’den kalma, Knuth’un yeni yarattığı dizgi sistemi TeX’i tanıttığı beş videodan oluşan iki farklı set de var. Knuth’un “dahili ayrıntılarla ilgili yoğun bir kurs” olarak adlandırdığı şeyin 1982’den kalma 12 videosu bile var.
Ve 6 Aralık’ta geleneksel kahverengi tatil kazağını giyen Knuth, onu ünlü yapan güzel netlikteki hassasiyetin bir başka canlı gösterisini daha yaptı.
İşte Donald Knuth’un son dersi:
Dans eden bağlantıların ötesinde
Peki bu yılın konusu ne?
Yeni başlayan programcılara bağlantılı listeler öğretilir; listedeki her öğe yalnızca bir değer değil, aynı zamanda sonraki ve önceki öğelerin konumunu da içeriyor. Knuth, “Bilgisayardaki bu sayıların zarif bir şekilde koreografisi yapılmış bir dansı takip ettiği görülüyor ve bu yüzden buna dans bağlantıları diyorum.” diyor. Bunlar, 2018’de tartışıldı ve bu yılki ders bir nevi devam filmi olarak tanımlandı.
“Artık dans hücrelerini cazip bir isimle anan bir şeyle dans bağlantılarını geliştirdik.”
Ve sonra, Geçmiş Noel’in Hayaleti gibi, Knuth da neredeyse yarım yüzyıl öncesine baktı. Alfred Aho, Jeffrey Ullman ve John Hopcroft’un yazdığı Bilgisayar Algoritmalarının Tasarımı ve Analizi kitabının köşeli kopyasını koyarak izleyicilere “Bütün hikaye bilgisayar bilimi hakkındaki gerçekten harika ilk kitaplardan biriyle başlıyor.” dedi.
1974 tarihli bu kitap, okuyucuları ilk erişildiğinde bir matrisin değerlerini her zaman sıfır olarak başlatmanın bir yolunu bulmaya zorlayan bir alıştırma içeriyordu. Ve çözümün hem akıllıca hem de beklenmedik şekilde faydalı olduğu ortaya çıktı. Yalnızca bilinen değerlerin çok daha küçük bir listesinin tutulmasını içeriyor.
Yaklaşık 20 yıl sonra, 1993 tarihli bir makale bu fikri yeniden ele aldı. Makale, 1974 tarihli ders kitabına bile atıfta bulunarak çözümlerinin “unutulmaz bir ev ödevi probleminden ilham aldığını…” belirtiyor.
Knuth dinleyicilerine alaycı bir tavırla “Başka bir deyişle,” diyor, “ev ödevi sorunları aslında bir şekilde fark ediliyor.“
1993’teki araştırmacılar değerleri silmek için akıllıca bir işlem de eklemişlerdi ve Knuth, Bilgisayar Programlama Sanatı’nın son güncellemesi olan 4B cildinde (2022’de yayınlandı) bununla ilgili bir tartışmaya yer verdi. Knuth izleyicilere “Harika bir Noel hediyesi olur” diye şaka yaparak bazı takdir dolu kahkahalara yol açtı.
Ancak bu aynı zamanda Knuth için dikkat çekici derecede verimli veri işlemeyi gösterme şansıydı…
Sayı listesindeki bir değeri silmenin inanılmaz derecede kolay bir yolu olduğu ortaya çıktı. Artık listenizin uzunluğunu aşan bir konuma sahip tüm numaraların silindiği biliniyor ve bunlar, silinen tüm değerlerin kullanışlı bir kümesini oluşturuyor. Doğal olarak oluşan bir düzen nedeniyle, en son silinen numaralar ilk önce görünecek şekilde sırayla bile görünüyorlar.
“Algoritma ilerledikçe buradaki sayılar biraz dans ediyor.” Bu, çift bağlantılı bir listedeki yolları belirleyen “dans eden bağlantılar” algoritmasına benziyor, ancak şimdi “silinmiş” veya “silinmemiş” durumunu izliyor. Dolayısıyla bu fenomen için bilgisayar bilimi profesörü Christine Solnon daha iyi bir isim buldu: “Dans eden hücreler.“
Sonra Knuth zamanda atlayarak 2013’te bu fikrin önemini vurgulayan bir makaleye atladı.
Büyük final
Knuth, kısıtlama memnuniyeti problemleri kavramının bir açıklamasına başladı; çeşitli değişkenlerin değerleri için tüm gereksinimlerin karşılanıp karşılanamayacağı veya tüm Boolean değişkenlerinin doğru olup olamayacağı.
Knuth, dinleyicilerine bu modellerden bazılarının bir kez oluşturulduktan sonra sonsuz sayıda değere uygulanabileceğini söyleyerek sıcak bir kahkaha attı. “Fakat bu beni aşan bir şey. Ben sınırlı bir adamım.”
Bir haritanın renklerle kaplanmasını içeren üçüncü bir sorun alt kümesi daha var; Knuth’un espri yaptığı bu konu o kadar belirsiz ki, “Bugün itibariyle haritanın hâlâ bir Wikipedia sayfası yok… Bu çok yazık.” diye ekliyor. “İnsanların bunun ne kadar harika bir şey olduğunu anlamalarını bekliyorum.”.
Ders, bu tür sorunların, çoğu durumda eski “Dans eden bağlantılar” algoritmasından bazen 20 kat daha verimli ve daha hızlı olan “Dans eden hücreler” algoritmaları kullanılarak nasıl çözülebileceğini göstererek sona eriyor.
Knuth, gelecekte bu fikri popülerleştirmek için bir konferans verebileceğini ve dünyanın bu gelişmeyi yakalamasına yardımcı olabileceğini söylüyor. Ancak bunun da ötesinde,
“Bekleyecek zamanım yok. Daha fazla kitap yazmam gerekiyor.”
