Tugas apa yang diberikan Dijkstra kepada para sukarelawan, yang disebutkan dalam makalahnya “Programer Rendah Hati”?

65

Dalam makalah Dijkstra "Programmer Humble" , ia menyebutkan bahwa ia memberi beberapa sukarelawan masalah untuk dipecahkan:

“Saya telah menjalankan percobaan pemrograman kecil dengan sukarelawan yang benar-benar berpengalaman, tetapi sesuatu yang tidak disengaja dan sangat tidak terduga muncul. Tidak ada relawan saya yang menemukan solusi yang jelas dan paling elegan. Setelah analisis lebih dekat, ini ternyata memiliki sumber yang sama: gagasan mereka tentang pengulangan begitu erat terkait dengan gagasan variabel terkontrol terkait untuk ditingkatkan, sehingga mereka secara mental terhalang untuk melihat yang jelas. Solusi mereka kurang efisien, sulit dimengerti, dan butuh waktu yang sangat lama untuk menemukannya. ”

Apa masalah yang Dijkstra berikan kepada para relawan? Apa solusinya?

algorithms history pengguna712092
sumber
3
Saya akan bertaruh pada sesuatu yang rekursif. EWD654 "Untuk menghormati Fibonacci" tampaknya menjadi kandidat yang bagus
Agak
Pertanyaan ini bisa baik-baik saja selama orang tidak menggunakan ini sebagai kesempatan untuk menebak atau berspekulasi: mungkin sulit untuk mengetahuinya, tetapi ia memiliki jawaban dan pertanyaan historis ada di topik di sini.
9
Kutipan itu datang dari EWD340 "Programmer Sangat Rendah Hati". Saya tidak dapat menemukan deskripsi yang tepat tentang apa percobaan itu, tetapi di sini ada tautan ke transkrip pembicaraan lengkapnya. cs.utexas.edu/~EWD/transcription/EWD03xx/EWD340.html
Tyler Ferraro
2
Adakah yang bisa menemukan kutipan Dijkstra yang gratis tentang apa pun? Kutipan favorit saya tentang dia adalah "kesombongan dalam ilmu komputer diukur dalam nano-Dijkstras" - Alan Kay
James Anderson
Kita harus sangat berhati-hati ketika kita memberi nasihat kepada orang yang lebih muda: kadang-kadang mereka mengikutinya! ... heh :-) sumber: en.wikiquote.org/wiki/Edsger_W._Dijkstra
Robert French

Jawaban:

11

"Masalah filsuf makan" adalah masalah yang disajikan.

Pada dasarnya ada 5 filsuf yang perlu makan. (bayangkan sepiring makanan yang tidak pernah berakhir di depan setiap filsuf), antara setiap lempengan adalah garpu (5 piring, 5 garpu, 5 filsuf).

Seorang filsuf hanya bisa makan jika dia memegang garpu ke kanan dan garpu ke kiri. (hanya dua filsuf yang bisa makan pada waktu tertentu).

Garpu dapat diambil kapan saja tersedia dan diletakkan jika disimpan. Setiap garpu harus diambil secara saling tergantung. (satu per satu).

Sementara seorang filsuf tidak makan, mereka berpikir (kebutuhan untuk mengganti keadaan adalah yang mendorong masalah).

Bagaimana Anda mengijinkan masing-masing dari mereka untuk makan dan berpikir secara bergantian (sehingga yang lain dapat makan) tanpa membuat sistem menemui jalan buntu (di mana satu filsuf memegang satu garpu dan menunggu yang lain, mencegah filsuf lain makan).

Ini berakar pada sistem konkuren dan merupakan pertanyaan khas universitas yang diajukan ketika membahas Concurrency.

Saya percaya bahwa 4 atau 5 "resmi" algoritma telah dikembangkan untuk menyelesaikan masalah tetapi pencarian cepat di google untuk "masalah makan filsuf" akan memberi Anda berbagai hasil.

Jika Anda membaca versi asli makalah dalam catatan kaki di halaman 866 itu menyatakan: "Prosiding Kongres IFIP 1965, 213-217." Solusi masalah dalam kontrol pemrograman bersamaan. "

Masalah dalam konkurensi dan sumber daya bersama adalah "Masalah Makan Filsuf". :-)

Semoga itu bisa membantu.

Robert French
sumber
6
Karena ini terutama merupakan pertanyaan historis, ada sumber?
yannis
1
Sebenarnya tidak, sumber yang Anda berikan tampaknya tidak merujuk pada masalah filsuf Makan seperti yang diberikan Dijkstra kepada para sukarelawan. Apakah saya melewatkan sesuatu? Yang saya cari adalah sumber yang dapat dipercaya untuk mendukung "Masalah filsuf makan" Anda adalah masalah yang diajukan , bukan deskripsi masalah itu sendiri (meskipun tautan Anda sangat informatif dan menarik).
yannis
@ Robert Terima kasih atas tautannya. :) (jangan hapus mereka, mereka mungkin berguna bagi orang lain) Saya menantikan apakah itu masalah yang dia berikan.
user712092
4
@RobertFrench Apa yang kami cari adalah apa masalah spesifik yang Dijkstra sebutkan dalam kutipan dalam pertanyaan, dan sumber yang membuktikannya, bukan sembarang masalah yang dirumuskan Dijkstra. Tidak ada dalam kutipan yang bahkan menunjukkan itu adalah salah satu masalahnya sendiri, itu bisa menjadi masalah sebenarnya. Tentu saja para filsuf Bersantap adalah salah satu yang asli Dijkstra (dengan bantuan dari CAR Hoare), tidak ada yang memperdebatkannya, tetapi itu tidak ada hubungannya dengan pertanyaan itu .
yannis
4
Ini benar-benar salah. "Solusi dari masalah dalam kontrol pemrograman bersamaan" adalah Masalah Filsuf Makan, dan itu direferensikan dalam Programmer Humble sebagai salah satu karya Dijkstra sebelumnya dalam kutipan, tetapi mengklaim bahwa itu juga masalah dalam kutipan tidak dapat diverifikasi.
yannis