Pertanyaan tentang instruksi yang didefinisikan dengan baik untuk menyelesaikan tugas, dan analisis yang relevan dalam hal waktu / memori / dll.
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...
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...
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
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...
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...
Banyak algoritma pencarian jalur telah dikembangkan dalam beberapa tahun terakhir yang dapat menghitung jalur terbaik dalam menanggapi perubahan grafik jauh lebih cepat daripada A * - apa sajakah itu, dan bagaimana perbedaannya? Apakah mereka untuk situasi yang berbeda, atau melakukan beberapa yang...
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...
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...
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...
Secara luas diduga bahwa , eksponen optimal untuk perkalian matriks, sebenarnya sama dengan 2. Pertanyaan saya sederhana:ωω\omega Apa alasan yang kita miliki untuk meyakini bahwa ?ω=2ω=2\omega = 2 Saya mengetahui algoritma cepat seperti Coppersmith-Winograd, tapi saya tidak tahu mengapa ini...
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...
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...
Dua cara menganalisis efisiensi suatu algoritma adalah untuk menempatkan batas atas asimptotik pada runtime, dan untuk menjalankannya dan mengumpulkan data eksperimental. Saya ingin tahu apakah ada kasus yang diketahui di mana ada kesenjangan yang signifikan antara (1) dan (2). Maksud saya,...
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...
Misalkan saya memiliki grafik asiklik terarah dengan bobot bilangan real pada simpulnya. Saya ingin menemukan pemesanan topologi DAG di mana, untuk setiap awalan pemesanan topologis, jumlah bobot adalah non-negatif. Atau jika Anda lebih suka terminologi teoretis pesanan, saya memiliki urutan...
Saya selalu mengalami kesulitan dalam memahami pentingnya Integrality Gap (IG) dan terikat padanya. IG adalah rasio (kualitas) jawaban integer optimal untuk (kualitas) solusi nyata optimal dari relaksasi masalah. Mari kita pertimbangkan vertex cover (VC) sebagai contoh. VC dapat dinyatakan sebagai...
Saya mencari dugaan tentang algoritme dan kompleksitas yang dipandang kredibel oleh banyak orang di beberapa titik waktu, tetapi kemudian mereka ditolak, atau setidaknya tidak dipercaya, karena pemasangan kontra-bukti. Berikut adalah dua contoh: Hipotesis oracle acak: hubungan antara kelas-kelas...
Jika Anda dapat mengubah nama pemrograman dinamis, apa
Penjelasan teoretis apa yang ada untuk keberhasilan praktis pemecah SAT, dan dapatkah seseorang memberikan ikhtisar dan penjelasan "gaya-wikipedia" yang mengikat semuanya? Secara analogi, analisis yang dihaluskan ( versi arXiv )) untuk algoritme simpleks melakukan pekerjaan yang hebat...
Di utas lain , Joe Fitzsimons bertanya tentang "batas bawah terbaik saat ini pada 3SAT." Saya ingin pergi ke arah lain: Apa batas atas terbaik saat ini di 3SAT? Dengan kata lain, apa kompleksitas waktu dari pemecah SAT yang paling efisien? Secara khusus, apakah mungkin untuk menemukan algoritma...