- Dalam Kuliah Natal Stanford 2024, Donald Knuth membahas strong components dan weak components pada graf berarah, dan menyebut algoritme strong components Tarjan sebagai algoritme yang paling ia cintai
- Jika sebuah strong component diringkas menjadi satu simpul, hasilnya menjadi DAG tanpa siklus, dan algoritmenya bekerja dengan alur menemukan lalu menghapus sink strong component
- Di sini, weak component bukanlah komponen terhubung yang mengabaikan arah, melainkan partition yang lebih umum yang mengelompokkan kembali strong components agar menjadi linear order
- Algoritme Tarjan membedakan tree arc, back arc, loop, forward arc, dan cross arc selama DFS, serta sekaligus memperoleh strong components dan pengurutan topologis-nya
- Daya tarik yang ditekankan Knuth bukan hanya prosedurnya, melainkan struktur data yang mendalam yang disusun agar informasi keputusan yang diperlukan dapat diakses tepat pada saatnya
Titik awal kuliah dan buku baru Knuth
- Kabar terbaru di awal kuliah berfokus pada buku baru Constraint Satisfaction
- Naskah internalnya dikirim ke penerbit sehari sebelumnya, dan prapemesanan juga sudah tersedia
- Pencetakan sebelum Natal mungkin sulit, dan tanggal rilis resminya tampaknya 3 Februari
- Di dalam buku tercantum dicetak pada Januari, dan buku ini merupakan proyek utama Knuth selama 5 tahun terakhir
- Rincian lebih lanjut tentang topik kali ini, Strong Components and Weak Components, ada di pre-fascicle 12A
- Buku yang ada saat ini adalah volume 4 Fascicle 7, dan fascicle sebelumnya telah diterbitkan dalam sampul keras sebagai volume 4A dan 4B
- Materi ini kelak akan menjadi sepertiga pertama dari volume 4C
- Subjudul kuliah ini kira-kira “Which algorithm do you love the most?”
- Knuth biasanya tidak suka pertanyaan yang memintanya memilih “algoritme favorit”, tetapi dalam kasus ini ia mengatakan algoritme strong components Tarjan adalah jawaban yang jelas
- Ketika mempelajari prosedur ini pada 1973, ia untuk pertama kalinya memahami bahwa struktur data juga bisa “mendalam” seperti teorema atau algoritme
Perbedaan strong component dan weak component
- Graf berarah terdiri dari simpul dan panah berarah
- Jika dua simpul u dan v dapat saling mencapai, keduanya termasuk dalam strong component yang sama
- Semua simpul yang berada pada sebuah siklus termasuk dalam strong component yang sama
- Sebuah simpul yang memiliki jalur masuk dari berbagai tempat tetapi tidak dapat keluar bisa menjadi satu strong component tersendiri
- Weak component yang digunakan Knuth berbeda dari undirected component yang mengabaikan arah
- Ia berpendapat bahwa komponen yang terhubung ketika arah diabaikan seharusnya disebut “undirected component”
- Weak component adalah konsep yang mem-partition kembali DAG yang diperoleh dengan meringkas strong components, sehingga keseluruhannya membentuk urutan lurus
- Jika setiap strong component diringkas menjadi satu “super vertex”, graf yang dihasilkan tidak memiliki siklus
- Ini dapat dilihat sebagai partial order
- Jika diringkas lagi hingga weak components, hasilnya menjadi total order atau linear order
- Ini juga terhubung langsung dengan topological sorting
- Jika x selalu berada sebelum y dalam setiap topological sorting, keduanya berada dalam weak component yang berbeda
- Jika dalam satu pengurutan x bisa berada sebelum y dan dalam pengurutan lain y bisa berada sebelum x, keduanya berada dalam weak component yang sama
- Knuth mengaitkan hal ini dengan mutual incomparability
Sejarah konsep dan algoritme
- Konsep weak component muncul ketika Knuth, Ron Graham, dan seorang profesor yang ditulis sebagai Mazkin saling berkirim surat mengenai masalah lain
- Dalam surat Mazkin kepada Graham pada 28 Februari 1970, terdapat gagasan memperoleh total order melalui partition
- Pada Desember 1970, Knuth menulis kepada Graham bahwa ketiganya telah membuktikan hasil yang lebih umum dengan pendekatan masing-masing yang berbeda
- Knuth memutuskan untuk menyertakan Mazkin sebagai rekan penulis, tetapi tak lama setelah itu ia menerima kabar bahwa Mazkin meninggal mendadak karena serangan jantung
- Makalah terkait diterbitkan pada 1972 di Discrete Mathematics volume 2 nomor 1
- Saat itu Discrete Mathematics adalah jurnal yang baru dimulai, dan belum ada yang menduga betapa banyak makalah bagus yang kelak akan terbit di sana
- Algoritme strong components Tarjan diterbitkan pada 1972 di SIAM Journal on Computing volume 1 nomor 2
- Saat itu Tarjan masih mahasiswa pascasarjana, dan makalah tersebut adalah publikasi ke-6 dalam daftar publikasinya
- Knuth membaca makalah ini pada Januari 1973 dan menjadi menyukai algoritmenya
- Algoritme Tarjan juga dijelaskan dengan baik dalam buku teks algoritme karya Aho, Hopcroft, dan Ullman
- Hopcroft berbagi kantor dengan Tarjan selama masa sabatikal di Stanford dan merancang berbagai algoritme
- Hopcroft memiliki gagasan algoritme biconnected components untuk undirected graph, dan Tarjan menerapkan gagasan serupa pada strong components di directed graph
- Buku Shimon Even membahas low point dalam algoritme Tarjan
- Tarjan memecahkan situasi melingkar yang tampaknya mengharuskan kita mengetahui low point untuk menemukan component, tetapi juga mengetahui component untuk menghitung low point
Cara menemukan strong components dengan DFS
- Knuth menganalogikan penelusuran graf dengan eksplorasi gua
- Setiap room adalah vertex, dan daftar room lain yang dapat dicapai dari setiap room adalah outgoing arc
- Komputer tidak melihat gambar, melainkan menelusuri hanya berdasarkan daftar vertex dan daftar arc
- Metode penelusuran dasarnya adalah depth-first search
- Masuk semakin dalam mengikuti outgoing arc yang belum dilihat
- Jika tidak ada lagi tempat untuk pergi, kembali ke posisi sebelumnya
- Jika menemukan vertex yang sudah dikunjungi, algoritme menentukan jenis arc tersebut
- Dalam DFS, arc dibagi menjadi lima jenis
- tree arc: arc pada DFS tree yang terbentuk saat pertama kali menemukan vertex baru
- back arc: arc yang kembali ke ancestor
- loop: arc yang menuju dirinya sendiri dan tidak memengaruhi strong components
- forward arc: arc yang menuju descendant
- cross arc: arc yang menuju vertex yang bukan ancestor maupun descendant
- Setiap kali menemukan strong component, algoritme menemukan sink component dari graf yang masih tersisa
- DAG terbatas selalu memiliki sink
- Prosesnya berjalan dengan menghapus sink strong component lalu mencarinya lagi pada graf yang tersisa
- Dalam proses ini, algoritme sekaligus menemukan strong components dan topological sort-nya
- Kinerjanya disajikan sebagai sangat cepat
- Untuk M arc dan N vertex, pada kasus terburuk jumlah memory access berada di kisaran 5M + 17N
- Angka ini mencakup operasi seperti memeriksa akhir daftar arc dan memperbarui pointer
Weak components, versi perbaikan, dan implementasi
- Algoritme weak components juga dapat dijalankan bersama proses menemukan strong components
- Ia memanfaatkan fakta bahwa strong components ditemukan dari kanan ke kiri, yaitu mulai dari sink
- Ketika strong component baru masuk di sisi kiri, algoritme menentukan bagaimana ia digabungkan dengan weak components yang sudah ada
- Dalam penentuan weak component, source dan sink di dalam setiap component penting
- Semua sink dari satu weak component harus memiliki arc ke semua source dari weak component berikutnya
- Kondisi ini adalah syarat perlu dan cukup untuk memiliki weak components
- Saat memprogram, update dapat dilakukan dengan hanya melacak source
- Pada 1974, Tarjan menerbitkan makalah algoritme 3 halaman untuk menemukan weak components di Information Processing Letters volume 3 nomor 1
- Knuth merangkum materi ini dalam pre-fascicle 12A miliknya
- Menjaga struktur data yang memadai untuk menjamin worst-case linear time bukanlah hal sederhana
- Dijkstra juga membahas masalah strong components
- Bab 25 dari buku Dijkstra membahas “Finding the maximal strong components in a directed graph”
- Dijkstra menggunakan struktur yang menghapus sink strong component satu per satu, tetapi tidak sampai pada penyederhanaan low point milik Tarjan
- Solusi Dijkstra memperkenalkan empat array baru untuk melacak struktur
- Knuth dan Tarjan baru-baru ini meninjau kembali algoritme lama dan membuat definisi serta versi perbaikan yang lebih baik
- Mereka memperbaikinya berdasarkan gagasan Kurki-Suonio dari 1970-an, tetapi makalah aslinya memiliki fallacy
- Mereka mengurangi akses yang sebelumnya sekitar 7 kali per arc menjadi sekitar 5 kali
- Beberapa field digabungkan sehingga bentuknya lebih kompleks tetapi lebih cepat, dan ini mereka kelakarkan bukan sebagai “premature optimization”, melainkan “post-mature optimization”
- Implementasinya disediakan sebagai program CWEB
- Nama program yang disebutkan adalah Tarjan strong and weak dan Tarjan strong
- Inputnya adalah graph dalam Stanford GraphBase format
- Knuth mengatakan ia akan menata program-program di situs webnya agar lebih mudah ditemukan, dan memperbaiki kondisi yang belum diperbarui sejak 2022
- Stanford GraphBase memiliki contoh directed graph yang menggunakan sekitar 1.000 kategori thesaurus Roget sebagai vertex, dengan relasi synonym atau antonym sebagai arc
1 komentar
Komentar Hacker News
Saat mengunjungi San Francisco pada 2022, saya berkeliling kampus Stanford dan, ketika hendak keluar melewati lorong gedung musim panas yang sepi dan kosong, tanpa sengaja melihat kantor Knuth
Ukurannya mengejutkan kecil dibandingkan dengan reputasinya, sampai saya melihatnya lagi, tetapi justru terasa seperti ruang yang sangat cocok dengan kepribadiannya yang sederhana
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
Saya juga punya bukan satu, melainkan dua cek hadiah darinya. Memang hanya untuk salah ketik kecil, tetapi rasanya sangat keren memiliki dua dokumen ini
Mungkin tidak ada yang akan menyalahgunakannya, tetapi kalau saya tahu foto kantor saya diunggah tanpa sepengetahuan saya, rasanya akan cukup merinding
Saya sedang membaca TAOCP 4A dan 4B di waktu luang, dan isinya benar-benar luar biasa, jadi sangat saya rekomendasikan
Bagi kebanyakan programmer mungkin tidak praktis, tetapi cara Knuth merancang dan menjelaskan algoritma itu menakjubkan dan tiada duanya
Khususnya implementasi Dancing Links di 4B telah banyak diperbarui sejak makalah terkenalnya; itu struktur data yang canggih dan indah, sekaligus sangat cepat. Bahkan di usia 80-an, ia masih luar biasa
Saat kami menghitung biaya yang diperlukan untuk skala kami, angkanya mencapai puluhan juta dolar, sementara seluruh anggaran infrastruktur Route 53 hanya di kisaran puluhan ribu dolar. Di edge, kami memakai ulang server CloudFront yang hard disknya rusak sebagai nameserver, server API juga sederhana, dan timnya sekitar 6 orang. Cara AWS “mengupayakan mati-matian” berarti hampir tidak mengeluarkan uang, menurunkan risiko downside, dan menyelesaikannya dengan cepat
Jadi kami tidak bisa meminta puluhan juta dolar untuk packet scrubber; barangnya juga lama datang, dan kami bisa menjadi terlalu bergantung pada vendor tertentu
Pada awalnya kami memutuskan menjalankan nameserver Route 53 di rentang IP khusus agar agak terisolasi, dan dengan link jaringan khusus kami memang bisa memastikan infrastruktur Amazon lainnya tidak terdampak. Namun itu tidak menyelesaikan masalah bahwa pelanggan Route 53 saling berbagi nasib; rencana nyatanya kira-kira hanya “kalau ada masalah, kita filter dengan sangat baik memakai jaringan dan tool sistem yang ada”
Awal musim panas tahun itu, saya sedang tergila-gila pada algoritma kombinatorial sambil membaca fascicle terbaru terkait 4A dari Knuth. Suatu malam, tiba-tiba terpikir: jika kita membuat banyak nameserver virtual, kita bisa menetapkan kombinasi empat nameserver virtual yang unik untuk setiap pelanggan. Tingkat tumpang tindihnya juga bisa dikendalikan, dan saya cepat menghitung bahwa dengan sekitar 2.000 nameserver, kita bisa menjamin tidak ada dua pelanggan yang berbagi lebih dari dua. Dalam eksperimen, domain tetap ter-resolve dengan baik meski dua nameserver tidak bisa dijangkau, tetapi mulai bermasalah jika lebih dari itu; karena itulah angka ini penting
Algoritma pencarian rekursif untuk menetapkan IP terinspirasi langsung dari algoritma di 4A, dan memberi dua dimensi isolasi tambahan yang independen terhadap domain pelanggan. Pelanggan mendapat empat nameserver dari empat “stripe” independen, yang berkaitan dengan top-level domain berbeda yang dipakai pada nama nameserver (co.uk, com, net, org). Jadi jika salah satu top-level domain itu mengalami masalah seperti kesalahan DNSSEC, hanya satu nameserver yang terdampak
Kami juga membuatnya berasal dari empat “braid” independen, sehingga bisa menjamin tidak ada dua nameserver yang berbagi jalur jaringan atau perangkat keras fisik tertentu. Meski saya tahu kombinatorika dari latar belakang statistik dan kriptografi, tanpa membaca 4A saya tidak akan bisa membuat desain seperti ini
Saya tidak pernah segembira itu terhadap solusi apa pun. Sebab pada dasarnya, tanpa biaya infrastruktur tambahan, kami bisa memberikan isolasi tingkat IP jaringan yang dapat dibuktikan di antara domain pelanggan. Itu matematika. Memang tidak sepenuhnya gratis: kami harus memakai 2.000 alamat IP anycast, dan karena banyak top-level domain mewajibkan registrasi nameserver serta glue record, kami juga harus mendaftarkan 512 domain. Proses berurusan dengan registrar cukup menarik, tetapi akhirnya berhasil
Kami menamai pendekatan ini Shuffle Sharding, dan rasanya lebih seperti penemuan daripada penciptaan. Banyak sistem multitenant yang memakai penempatan acak pada akhirnya memperoleh semacam shuffle sharding, dan teknik pemfilteran jaringan seperti Stochastic Fair Blue juga menghasilkan efek serupa melalui hashing berbasis waktu. Namun saya belum pernah melihat metode yang persis sama dengan tingkat kendali yang bisa kami terapkan, dan itu bahkan bisa diperluas menjadi shuffle sharding bertumpuk rekursif yang mengisolasi lebih banyak tingkat—bukan hanya pemanggil, tetapi juga pemanggil dari pemanggil dalam pola “memanggil atas nama”
Beberapa tahun kemudian, sebagai ungkapan terima kasih, saya pergi langsung menonton kuliah Natal Knuth dan duduk di baris paling depan. Karena kita tidak pernah tahu apa yang akan memberi inspirasi, sampai sekarang saya membaca semua materi yang Knuth keluarkan. Termasuk karya-karya organnya
Jadi menurut saya buku-buku Knuth luar biasa praktis bagi programmer. Buku-buku itu memperluas cara berpikir dan memperdalam pemahaman; apa lagi yang bisa diharapkan selain itu
Makalah Dancing Links yang asli adalah salah satu makalah favorit saya. Kalimat seperti “proses ini membuat variabel-variabel pointer dalam struktur data global melakukan tarian yang dikoreografikan dengan cermat” benar-benar menunjukkan kecintaan Knuth pada algoritma
Saya memakai ini untuk pembuatan teka-teki silang, dengan cara membuat kata-kata mendatar dan menurun membentuk exact cover pada grid
Saya penasaran apakah algoritma yang diperbarui memakai lebih sedikit memori
Untuk masalah besar ini, saya memperkirakan ada sekitar 100 juta solusi, dan bahkan jika menemukan 100 per detik, butuh sekitar sepuluh hari untuk menyelesaikannya
Masalah yang sedang saya kerjakan adalah menghitung jumlah kasus pada ‘Fancy Tetris Houten Puzzel’ ketika potongan-potongan dengan warna yang sama semuanya terhubung dengan setidaknya berbagi satu sisi
Saya juga sedang memikirkan algoritma lain yang kurang sensitif terhadap memori untuk menyelesaikan masalah exact cover ini
Saya bertanya sebagai orang yang baru belakangan ini mulai membaca literatur ilmu komputer
Beberapa tahun lalu saat pergi ke San Francisco, saya terkejut mengetahui bahwa Donald Knuth bukan hanya masih hidup, tetapi juga masih terus memberi kuliah tahunan di Stanford
Malam ketika saya mencari gedungnya di kampus dan menyaksikan langsung ia berbicara tentang topik yang hampir sulit saya ikuti akan lama saya ingat. Donald Knuth benar-benar legenda
Seorang rekan tim bulan lalu menemukan kesalahan di Seminumerical Algorithms dan menerima cek hadiah senilai 1 hexadecimal dollar; cek itu datang bersama cetakan email asli yang diberi catatan tulisan tangan
Bagian yang paling menginspirasi dari Donald Knuth bagi saya adalah dedikasi dan disiplin yang berlangsung selama puluhan tahun
Sebagai orang yang terus berganti-ganti proyek, bahasa, dan distribusi, saya benar-benar punya banyak hal untuk dipelajari darinya
Pakaiannya sangat cerah dan hidup, terlihat seperti busana dunia/folk yang dulu dipakai di desa-desa lama; saya tidak yakin apakah itu gaya Iran, Slavia, atau entah di antaranya
Adakah yang bisa menebak dengan lebih baik?
Ingatan saya samar, dan mungkin juga ada kaitannya dengan istrinya. Sepertinya ia sering memakainya dalam kuliah-kuliah sejak pertengahan 2010-an, jadi mestinya ada penjelasannya di suatu tempat
Saya pernah berada di sebelah Knuth pada 2012, di alun-alun depan Manchester Town Hall, saat ia mencoba naik ke ambang jendela untuk melihat obor Olimpiade masuk. Saya menyapanya, dan sempat spontan mengulurkan tangan karena khawatir ia jatuh ke luar jendela, tetapi ternyata baik-baik saja. Ia terasa seperti orang yang penuh rasa ingin tahu, pertanyaan dan kecerdasannya bersinar, dan tampak lebih muda daripada usianya
Kami sama-sama menghadiri acara peringatan 100 tahun kelahiran Alan Turing, dan saya takjub karena di ruangan yang sama ada para tokoh besar ilmu komputer seperti Knuth, Gary Kasparov, Fred Brooks, Vint Cerf, dan lainnya. Saat makan siang, obor Olimpiade masuk ke alun-alun di luar, dan ia tidak tahan untuk tidak pergi melihatnya. Sepertinya hanya dia yang begitu bersemangat soal itu
Ia memberikan ceramah pada jamuan malam hari itu, dan kemudian ketika saya bertemu lagi dengannya di Manchester saat 4B baru saja terbit dan meminta tanda tangannya di buku, ia samar-samar mengenali saya dari acara sebelumnya
Alasan saya menceritakan ini adalah karena menurut saya kemejanya mengisyaratkan pikiran yang jauh lebih eklektik dan penuh rasa ingin tahu. Saya jelas melihat bukti seperti itu juga di tempat lain
Jadi mungkin kecintaannya pada pakaian tradisional Sami berasal dari sana
[0]: https://youtu.be/jB0aeePskBg
https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
Saya cek, ternyata usianya 87 tahun. Donald Knuth lahir pada 10 Januari 1938
Wow
Knuth masih tetap mengagumkan
Namun cukup mengejutkan dan mengecewakan bahwa di Stanford tidak ada yang benar-benar mengurus rekaman audio yang layak untuk materi sepenting ini. Kedengarannya seperti direkam dengan perekam di dalam saku seseorang
Saya tidak sedang membicarakan suara Knuth di usia senja, tetapi coba dengarkan betapa buruk kualitas audionya ketika ia berhenti dan menerima pertanyaan dari audiens
Video seperti ini mengingatkan saya kenapa sejak awal saya jatuh cinta pada komputer
Cukup menakjubkan bahwa ia masih begitu tajam. Sayangnya, saat saya masih mahasiswa S1 sekitar 20-an tahun lalu, ia sudah tidak lagi mengajar
Saya suka caranya menangani pertanyaan: https://youtu.be/Hi8r_63LGyg?t=827
Ia meluangkan waktu untuk memahami apa yang ditanyakan, lalu menjawab dengan sangat jelas