Model perhitungan mana yang "terbaik"?

Pada 1937 Turing menggambarkan mesin Turing. Sejak itu banyak model komputasi telah diuraikan dalam upaya untuk menemukan model yang seperti komputer nyata tetapi masih cukup sederhana untuk merancang dan menganalisis algoritma.

Akibatnya, kami memiliki selusin algoritma untuk, misalnya, masalah SORT untuk model komputasi yang berbeda. Sayangnya, kami bahkan tidak dapat memastikan bahwa implementasi suatu algoritma dengan waktu berjalan O (n) dalam RAM kata dengan operasi bit-vektor diperbolehkan akan berjalan lebih cepat daripada implementasi algoritma dengan waktu berjalan O (n⋅logn) di RAM kata (saya berbicara tentang implementasi "baik" saja, tentu saja).

Jadi, saya ingin memahami model mana yang ada adalah "yang terbaik" untuk merancang algoritma dan saya mencari survei terbaru dan terperinci tentang model perhitungan, yang memberikan pro dan kontra dari model dan kedekatan mereka dengan kenyataan.

Saya selalu menganggap model RAM Word standar sebagai "yang terbaik" menurut Anda. Setiap orang yang belajar memprogram dalam bahasa seperti C (atau padanan yang longgar seperti Java, dll.) Memiliki model ini di benak ketika mereka memikirkan komputer.

Tentu saja, Anda terkadang perlu generalisasi tergantung pada rezim tempat Anda bekerja. Model memori eksternal adalah yang penting untuk diingat. Ini berlaku tidak hanya ketika Anda bekerja dengan disk, tetapi juga dalam memahami (memaksa Anda untuk peduli) cache. Tentu saja, memperlakukannya terlalu serius juga dapat menyebabkan hasil yang tidak masuk akal, karena model memori eksternal murni tidak menghitung perhitungan. Generalisasi lain dari Word RAM adalah paralelisme, tetapi di sana kita semua sedikit bingung saat ini :)

$O(n)$$O(n \lg n)$$n$$n$

Komentar akhir tentang algoritme dan "kenyataan": selalu ingat apa yang ingin Anda capai. Saat kami bekerja dalam algoritme, kami mencoba menyelesaikan masalah tersulit di luar sana (misalnya SAT pada 50 variabel, atau mengurutkan satu miliar angka). Jika Anda mencoba mengurutkan 200 angka atau menyelesaikan SAT pada 20 variabel, Anda tidak memerlukan algoritma yang bagus. Itu sebabnya sebagian besar algoritma pada kenyataannya agak sepele. Ini tidak mengatakan hal buruk tentang penelitian algoritmik - kita hanya tertarik pada 1/1000 masalah nyata yang terjadi menjadi sulit ...

Tidak ada satu model komputasi yang benar-benar memuaskan di mana untuk menganalisis algoritma sedih, bahkan dalam apa yang mungkin dianggap sebagai pengaturan tradisional. Itu dengan asumsi semua data mudah diakses dan ruang kerja tidak terikat secara efektif.

Mesin Turing multi-tape, secara teoritis ditentukan dengan baik dan banyak algoritma telah dirancang dan dianalisis dalam model ini selama bertahun-tahun. Namun, bagi sebagian orang itu tidak cukup erat kaitannya dengan bagaimana komputer nyata bekerja untuk benar-benar menjadi model yang baik untuk digunakan di abad ke-21. Di sisi lain, model kata-RAM telah menjadi populer dan tampaknya menangkap lebih akurat kerja komputer modern (operasi kata-kata bukan bit, akses waktu yang konstan ke lokasi memori). Namun, ada aspek yang kurang ideal. Misalnya, tidak ada model RAM satu kata. Pertama-tama kita harus menentukan operasi kata mana yang diizinkan dalam waktu konstan. Ada banyak opsi untuk ini tanpa jawaban tunggal yang diterima. Kedua, ukuran kata w biasanya diatur untuk tumbuh dengan ukuran input (yang setidaknya secepat log (n)) untuk memungkinkan setiap item dalam memori ditangani dengan menggunakan jumlah kata yang konstan. Ini berarti bahwa seseorang harus membayangkan kelas mesin tanpa batas di mana algoritma Anda dijalankan atau bahkan lebih buruk, bahwa mesin berubah ketika Anda memberinya lebih banyak data. Setidaknya ini adalah pemikiran yang paling membingungkan di antara murid-murid saya. Akhirnya, Anda mendapatkan hasil kompleksitas yang agak mengejutkan dengan model word-RAM yang mungkin tidak cocok dengan yang dipelajari sebagai siswa. Sebagai contoh, perkalian dua angka n-bit adalah O (n) waktu dalam model ini dan hanya membaca dalam string n-bit adalah operasi waktu sublinear secara tiba-tiba. Ini berarti bahwa seseorang harus membayangkan kelas mesin tanpa batas di mana algoritma Anda dijalankan atau bahkan lebih buruk, bahwa mesin berubah ketika Anda memberinya lebih banyak data. Setidaknya ini adalah pemikiran yang paling membingungkan di antara murid-murid saya. Akhirnya, Anda mendapatkan hasil kompleksitas yang agak mengejutkan dengan model word-RAM yang mungkin tidak cocok dengan yang dipelajari sebagai siswa. Misalnya, perkalian dua angka n-bit adalah O (n) waktu dalam model ini dan hanya membaca dalam string n-bit adalah operasi waktu sublinear tiba-tiba. Ini berarti bahwa seseorang harus membayangkan kelas mesin tanpa batas di mana algoritma Anda dijalankan atau bahkan lebih buruk, bahwa mesin berubah ketika Anda memberinya lebih banyak data. Setidaknya ini adalah pemikiran yang paling membingungkan di antara murid-murid saya. Akhirnya, Anda mendapatkan hasil kompleksitas yang agak mengejutkan dengan model word-RAM yang mungkin tidak cocok dengan yang dipelajari sebagai siswa. Sebagai contoh, perkalian dua angka n-bit adalah O (n) waktu dalam model ini dan hanya membaca dalam string n-bit adalah operasi waktu sublinear secara tiba-tiba.

Setelah mengatakan semua itu, jika Anda hanya ingin tahu apakah algoritme Anda kemungkinan akan berjalan cepat, kemungkinan besar akan dilakukan :-)

Model hanyalah model. Saya tidak akan mendorongnya terlalu jauh; mereka mengatakan sesuatu tentang beberapa aspek dari algoritma Anda, tetapi tidak sepenuhnya benar.

Saya menyarankan agar Anda cukup menggunakan model RAM kata standar dalam analisis Anda dan mengimplementasikan algoritma dan melihat seberapa baik kinerjanya dalam praktik.

(Sebenarnya hanya menerapkan algoritma Anda tanpa pernah menjalankannya memberitahu Anda sudah banyak tentang hal itu ... Untuk satu hal, itu kemudian terbukti dapat diimplementasikan.)

Jika tugas komputasi Anda lebih banyak tentang memindahkan data daripada melakukan operasi (aritmatika), (kumpulan data sangat besar sehingga mereka bahkan tidak masuk ke memori utama), maka model I / O (diperkenalkan oleh Aggarwal dan Vitter pada 1988 ) bisa sangat akurat. Untuk tugas-tugas seperti permutasi array elemen besar di memori utama, dapat membantu untuk menggunakan algoritma yang I / O-optimal (dalam implementasi yang hati-hati).

Untuk komputer multi-core modern, varian paralel yang diperkenalkan oleh Arge, Goodrich, Nelson dan Sitchinava pada 2008 dapat menjadi model yang akurat.

Jika Anda memaksudkan model komputasi "terbaik" untuk membuat hidup Anda lebih rumit, maka Anda dapat menggunakan mesin turing universal 2-simbol, 3-simbol Wolfram.

PROS : tidak ada kecuali sensasi berjalan di garis tipis antara akal dan kegilaan;

CONS : ton ...

:-D (hanya bercanda, pada dasarnya saya setuju dengan jawaban sebelumnya ...)

Pada catatan yang lebih teoretis: Artikel Ultimate teoretis model nanocomputers berpendapat bahwa model mesh 3D reversibel adalah model fisik optimal dari komputasi, dalam arti bahwa tidak ada model fisik lain yang bisa secara asimptot lebih cepat. Pertimbangan fisik seperti kecepatan cahaya, prinsip Landauer , dan ikatan Bekenstein dibahas.

Mengutip dari abstrak:

Kami menemukan bahwa menggunakan teknologi saat ini, mesin reversibel yang hanya berisi beberapa ratus lapisan sirkuit dapat mengungguli semua mesin yang ada, dan bahwa komputer yang dapat dibalik berdasarkan nanoteknologi hanya perlu beberapa mikron saja untuk mengungguli segala teknologi ireversibel yang mungkin.

Kami berpendapat bahwa implementasi silikon mesh 3D reversibel dapat berharga hari ini untuk mempercepat perhitungan ilmiah dan teknik tertentu, dan mengusulkan bahwa model harus menjadi fokus studi masa depan dalam teori algoritma paralel untuk berbagai masalah.