Pertanyaan yang diberi tag «ds.algorithms»

Pertanyaan tentang instruksi yang didefinisikan dengan baik untuk menyelesaikan tugas, dan analisis yang relevan dalam hal waktu / memori / dll.

Algoritma dari Kitab.
Paul Erdos berbicara tentang "Buku" di mana Tuhan menyimpan bukti paling elegan dari setiap teorema matematika. Ini bahkan mengilhami buku (yang saya percaya sekarang dalam edisi ke-4): Bukti dari Buku . Jika Tuhan memiliki buku yang serupa untuk algoritma, menurut Anda algoritma apa yang akan dijadikan kandidat? Jika memungkinkan, berikan …

Algoritma inti dikerahkan
Untuk menunjukkan pentingnya algoritma (misalnya untuk mahasiswa dan profesor yang tidak melakukan teori atau bahkan dari bidang yang sama sekali berbeda) kadang-kadang berguna untuk siap memberikan daftar contoh di mana algoritma inti telah digunakan dalam komersial, pemerintahan, atau perangkat lunak / perangkat keras yang banyak digunakan. Saya mencari contoh seperti …

Masalah Super Mario Galaxy
Misalkan Mario sedang berjalan di permukaan sebuah planet. Jika dia mulai berjalan dari lokasi yang diketahui, ke arah yang tetap, untuk jarak yang telah ditentukan, seberapa cepat kita dapat menentukan di mana dia akan berhenti? PPPsssPPPvvvpppℓℓ\ellPPPPPP PPPsssvvvℓℓ\ell PPPO(1)O(1)O(1)ℓℓ\ellPPP (Dalam praktiknya, panjang jalur sebenarnya tidak terikat; ada batas atas global dalam …

Seberapa keras unshuffling string?
Acak dua string dibentuk dengan memotong karakter ke string baru, menjaga karakter masing-masing string dalam urutan. Misalnya, MISSISSIPPIadalah shuffle dari MISIPPdan SSISI. Biarkan saya memanggil string kuadrat jika itu adalah shuffle dari dua string yang identik. Sebagai contoh, ABCABDCDadalah kuadrat, karena itu adalah shuffle dari ABCDdan ABCD, tetapi string ABCDDCBAtidak …

Contoh harga abstraksi?
Ilmu komputer teoretis telah memberikan beberapa contoh "harga abstraksi." Dua yang paling menonjol adalah untuk eliminasi Gaussian dan sortasi. Yaitu: Diketahui bahwa eliminasi Gaussian optimal untuk, katakanlah, menghitung determinan jika Anda membatasi operasi pada baris dan kolom secara keseluruhan [1]. Algoritma Strassen jelas tidak mematuhi batasan itu, dan secara asimptotik …


Apa kompleksitas waktu aktual dari eliminasi Gaussian?
Dalam jawaban untuk pertanyaan sebelumnya , saya menyebutkan kepercayaan umum tetapi salah bahwa eliminasi "Gaussian" berjalan dalam waktu . Meskipun jelas bahwa algoritma ini menggunakan operasi aritmatika , implementasi ceroboh dapat membuat angka dengan banyak bit secara eksponensial. Sebagai contoh sederhana, misalkan kita ingin mendiagonalisasi matriks berikut:O(n3)O(n3)O(n^3)O(n3)O(n3)O(n^3) ⎡⎣⎢⎢⎢⎢⎢⎢⎢211⋮1021⋮1002⋮1⋯⋯⋯⋱⋯000⋮2⎤⎦⎥⎥⎥⎥⎥⎥⎥[200⋯0120⋯0112⋯0⋮⋮⋮⋱⋮111⋯2]\begin{bmatrix} 2 & …

Algoritma yang kuat terlalu rumit untuk diimplementasikan
Apa saja beberapa algoritma utilitas yang sah yang terlalu rumit untuk diterapkan? Biarkan saya menjadi jelas: Saya tidak mencari algoritma seperti algoritma multiplikasi matriks optimal asimptotik saat ini (Coppersmith-Winograd), yang masuk akal untuk diimplementasikan tetapi memiliki konstanta yang membuatnya tidak berguna dalam praktiknya. Saya mencari algoritma yang mungkin memiliki nilai …

Algoritma polinomial-waktu dengan eksponen / konstanta besar
Apakah Anda tahu algoritma masuk akal yang berjalan dalam waktu polinomial dalam (Panjang input + Panjang output), tetapi yang menjalankan waktu asimtotik dalam ukuran yang sama memiliki eksponen / konstanta yang sangat besar (setidaknya, di mana batas atas terbukti pada waktu berjalan adalah dalam sedemikian rupa)?


Satu Tumpukan, Dua Antrian
Latar Belakang Beberapa tahun yang lalu, ketika saya masih sarjana, kami diberi pekerjaan rumah tentang analisis diamortisasi. Saya tidak dapat menyelesaikan salah satu masalah. Saya telah menanyakannya dalam teori comp.the , tetapi tidak ada hasil yang memuaskan muncul. Saya ingat kursus TA bersikeras pada sesuatu yang tidak bisa dia buktikan, …

Pernyataan yang dapat dibuktikan tentang algoritma genetika
Algoritma genetika tidak mendapatkan banyak daya tarik dalam dunia teori, tetapi mereka adalah metode metaheuristik yang cukup baik digunakan (oleh metaheuristik maksud saya teknik yang berlaku secara umum di banyak masalah, seperti anil, keturunan gradien, dan sejenisnya). Faktanya, teknik mirip GA cukup efektif untuk Euclidean TSP dalam praktiknya. Beberapa metaheuristik …

Untuk masalah dalam P apakah lebih mudah untuk memverifikasi hasil daripada menemukannya?
Untuk (versi pencarian) dari masalah NP- lengkap, verifikasi suatu solusi jelas lebih mudah daripada menemukannya, karena verifikasi dapat dilakukan dalam waktu polinomial, sementara menemukan saksi membutuhkan waktu (mungkin) eksponensial. Dalam P , bagaimanapun, solusinya juga dapat ditemukan dalam waktu polinomial, sehingga tidak tampak jelas kapan verifikasi lebih cepat daripada menemukan …


Apakah ada bukti keberadaan algoritma yang tidak konstruktif?
Saya ingat saya mungkin menemukan referensi untuk masalah yang telah terbukti dapat dipecahkan dengan kompleksitas tertentu, tetapi tanpa algoritma yang dikenal untuk benar-benar mencapai kompleksitas ini. Saya berjuang membungkus pikiran saya di sekitar bagaimana ini bisa terjadi; bagaimana bukti non-konstruktif untuk keberadaan suatu algoritma akan terlihat seperti. Apakah memang ada …

Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.