Ilmu Komputer Teoritis

Sejak buku Chris Okasaki tahun 1998 "Struktur data murni fungsional", saya belum melihat terlalu banyak struktur data fungsional murni yang menarik muncul; Saya dapat menyebutkan beberapa saja: IntMap (juga ditemukan oleh Okasaki pada tahun 1998, tetapi tidak ada dalam buku itu) Pohon jari (dan...

Pertanyaan ini (terinspirasi oleh) / (dicuri secara memalukan dari) pertanyaan serupa di MathOverflow , tapi saya berharap jawabannya di sini akan sangat berbeda. Kita semua memiliki makalah favorit dalam bidang teori masing-masing. Sekali-sekali, seseorang menemukan kertas yang sangat...

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...

Saya telah merevisi Teori Komputasi untuk bersenang-senang dan pertanyaan ini telah mengganggu saya untuk sementara waktu (lucu tidak pernah memikirkannya ketika saya belajar Teori Automata di sarjana saya). Jadi "mengapa" tepatnya kita mempelajari automata terbatas deterministik dan...

Norbert Blum baru-baru ini diposting 38-halaman bukti bahwa P≠NPP≠NPP \ne NP . Apakah itu benar? Juga pada topik: di mana lagi (di internet) kebenarannya sedang dibahas? Catatan: fokus teks pertanyaan ini telah berubah seiring waktu. Lihat komentar pertanyaan untuk

[ Garis Waktu ] Pertanyaan ini memiliki semangat yang sama tentang makalah apa yang harus dibaca semua orang dan video apa yang harus ditonton semua orang . Ia meminta buku-buku luar biasa di berbagai bidang ilmu komputer teoretis. Buku-buku itu bisa berorientasi matematika, tetapi Anda mungkin...

Wikipedia hanya mencantumkan dua masalah di bawah "masalah yang tidak terpecahkan dalam ilmu komputer" : P = NP? Adanya fungsi satu arah Apa masalah besar lainnya yang harus ditambahkan ke daftar ini? Aturan: Hanya satu masalah per jawaban Berikan deskripsi singkat dan tautan apa pun yang...

Stanford University sekarang memiliki saluran Youtube , dengan akses gratis ke video HD kursus lengkap tentang apa saja, mulai dari sistem dinamis hingga keterikatan kuantum. Lebih banyak konferensi dan lokakarya merekam pembicaraan mereka. Apa video online yang menurut Anda harus diketahui semua...

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

Anjak dan grafik isomorfisme adalah masalah dalam NP yang tidak diketahui dalam P atau NP-Complete. Apa saja masalah alam lain (yang cukup berbeda) yang berbagi properti ini? Contoh buatan yang datang langsung dari bukti teorema Ladner tidak masuk hitungan. Apakah ada di antara contoh ini yang...

Setelah membaca pertanyaan Daniel Apon , saya mulai berpikir bahwa mungkin berguna (terutama bagi peneliti junior dan mahasiswa pascasarjana seperti saya) untuk mengajukan pertanyaan yang lebih luas dan lebih umum sehingga kita dapat belajar dari pengalaman peneliti yang lebih senior. Jadi inilah...

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...

Ada beberapa pertanyaan dengan skema yang sama seperti ini: Makalah apa yang harus dibaca semua orang Buku apa yang harus dibaca semua orang Apa buku TCS terbaru yang konsepnya tersedia online video apa yang harus ditonton semua orang Saya enggan mengirim satu lagi, tetapi catatan kuliah...

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...

Saya telah belajar beberapa bit dari teori kategori. Tentunya cara pandang yang berbeda. (Ringkasan yang sangat kasar bagi mereka yang belum melihatnya: teori kategori memberikan cara untuk mengekspresikan semua jenis perilaku matematika hanya dalam hal hubungan fungsional antara objek. Misalnya,...

Setelah posting Apa Buku Yang Harus Dibaca Semua Orang , saya perhatikan ada buku-buku terbaru yang draftnya tersedia online. Sebagai contoh, entri Algoritma Approximation dari posting di atas mengutip sebuah buku 2011 (belum dipublikasikan) berjudul Desain algoritma pendekatan . Saya pikir...

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...

Saya sedang mempersiapkan ceramah yang ditujukan untuk jurusan matematika sarjana, dan sebagai bagian dari itu, saya sedang mempertimbangkan untuk membahas konsep decidability. Saya ingin memberikan contoh masalah yang saat ini tidak kita ketahui tidak dapat ditentukan atau tidak dapat ditentukan....

Saya ingin meminta bantuan dalam menyusun daftar sebanyak mungkin konferensi dan lokakarya terkait TCS. Motivasi utama saya untuk melakukan ini adalah merencanakan kemungkinan peliputan blog dari lebih banyak tempat teori - menemukan koresponden yang menghadiri acara-acara ini yang bersedia menulis...