Pertanyaan tentang metode dan teknik umum untuk membuktikan beberapa teorema. Saat menanyakan tentang bukti dari satu pernyataan, gunakan tag yang berkaitan dengan apa yang menjadi bukti.
Ada banyak pertanyaan tentang bagaimana menganalisis waktu berjalan algoritma (lihat, misalnya, analisis runtime dan analisis algoritma ). Banyak yang serupa, misalnya yang meminta analisis biaya loop bersarang atau algoritma Divide & Conquer, tetapi sebagian besar jawaban tampaknya dibuat...
Saya pernah mendengar tentang induksi (struktural). Ini memungkinkan Anda untuk membangun struktur yang terbatas dari yang lebih kecil dan memberi Anda prinsip-prinsip bukti untuk alasan tentang struktur tersebut. Idenya cukup jelas. Tapi bagaimana dengan coinduction? Bagaimana cara kerjanya?...
Ada banyak metode untuk membuktikan bahwa suatu bahasa tidak teratur , tetapi apa yang harus saya lakukan untuk membuktikan bahwa beberapa bahasa itu teratur? Misalnya, jika saya diberi tahu bahwa adalah biasa, bagaimana saya bisa membuktikan bahwa berikut ini juga teratur?L
Dalam teori komputasi dan kompleksitas (dan mungkin bidang lainnya), reduksi ada di mana-mana. Ada banyak jenis, tetapi prinsipnya tetap sama: menunjukkan bahwa satu masalah setidaknya sekeras beberapa masalah lainnya dengan memetakan contoh dari ke yang setara dengan solusi di . Pada dasarnya,...
Saya berencana untuk mengajar kursus musim dingin tentang berbagai topik, salah satunya akan menjadi penyusun. Sekarang, saya menemukan masalah ini sambil memikirkan tugas untuk diberikan sepanjang kuartal, tapi itu membuat saya bingung sehingga saya dapat menggunakannya sebagai contoh. public...
Saya memahami bukti ketidaktentuan masalah penghentian (diberikan misalnya dalam buku teks Papadimitriou), berdasarkan diagonalisasi. Sementara buktinya meyakinkan (saya mengerti setiap langkahnya), itu tidak intuitif bagi saya dalam arti bahwa saya tidak melihat bagaimana seseorang akan...
Ketika saya menjelaskan bukti Baker-Gill-Solovay bahwa ada oracle yang dapat kita miliki, , dan sebuah oracle yang dengannya kita dapat memiliki kepada teman , muncul pertanyaan mengapa teknik seperti itu tidak cocok untuk membuktikan masalah , dan saya tidak bisa memberikan jawaban yang...
Saya memiliki algoritma serakah yang saya duga mungkin benar, tetapi saya tidak yakin. Bagaimana saya memeriksa apakah itu benar? Apa teknik yang digunakan untuk membuktikan algoritma serakah yang benar? Apakah ada pola atau teknik yang umum? Saya berharap ini akan menjadi pertanyaan referensi...
Setiap masalah yang tidak dapat dipastikan yang saya ketahui termasuk dalam salah satu kategori berikut: Masalah yang tidak dapat dipastikan karena diagonalisasi (referensi diri tidak langsung). Masalah-masalah ini, seperti masalah penghentian, tidak dapat diputuskan karena Anda dapat menggunakan...
Saya mengambil kursus kompleksitas dan saya mengalami masalah dengan datangnya pengurangan antara masalah NPC. Bagaimana saya bisa menemukan pengurangan di antara masalah? Apakah ada trik umum yang bisa saya gunakan? Bagaimana saya harus mendekati masalah yang meminta saya untuk membuktikan masalah...
Ada banyak teknik untuk membuktikan bahwa bahasa adalah tidak bebas konteks, tapi bagaimana saya membuktikan bahwa bahasa adalah bebas konteks? Teknik apa yang ada untuk membuktikan ini? Jelas, salah satu caranya adalah dengan menunjukkan tata bahasa bebas konteks untuk bahasa tersebut. Apakah ada...
Masalah saya adalah bagaimana saya bisa membuktikan bahwa tata bahasa tidak ambigu? Saya memiliki tata bahasa sebagai berikut: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then }...
Dengan adanya masalah komputasi, apakah tugas menemukan batas bawah untuk perhitungan seperti itu benar-benar mungkin? Saya kira itu bermuara pada bagaimana langkah komputasi tunggal didefinisikan dan model apa yang kita gunakan untuk bukti, tetapi mengingat itu, apakah kita benar-benar membuktikan...
Saya memiliki dua cara untuk menghasilkan daftar item dalam urutan acak dan ingin menentukan apakah mereka sama adil (tidak bias). Metode pertama yang saya gunakan adalah untuk membangun seluruh daftar elemen dan kemudian melakukan pengocokan (katakanlah Fisher-Yates shuffle). Metode kedua lebih...
Logika konstruktivis adalah sistem yang menghilangkan Hukum Tengah yang Dikecualikan, serta Negasi Ganda, sebagai aksioma. Ini dijelaskan di Wikipedia di sini dan di sini . Secara khusus, sistem tidak memungkinkan pembuktian dengan kontradiksi. Saya bertanya-tanya, apakah ada yang akrab dengan...
Menentukan bahasa formal dengan memberikan tata bahasa formal adalah tugas yang sering: kita membutuhkan tata bahasa tidak hanya untuk menggambarkan bahasa, tetapi juga untuk menguraikannya, atau bahkan melakukan sains yang tepat . Dalam semua kasus, penting bahwa tata bahasa yang ada sudah benar ,...
Saya mencari penjelasan tentang bagaimana seseorang dapat membuktikan bahwa dua model perhitungan adalah setara. Saya telah membaca buku-buku tentang masalah ini kecuali bahwa bukti kesetaraan dihilangkan. Saya punya ide dasar tentang apa artinya dua model perhitungan menjadi setara (tampilan...
Dalam matematika, ada banyak bukti keberadaan yang tidak konstruktif, jadi kita tahu bahwa ada objek tertentu meskipun kita tidak tahu bagaimana menemukannya. Saya mencari hasil yang serupa dalam ilmu komputer. Secara khusus: apakah ada masalah yang dapat kita buktikan dapat diputuskan tanpa...
Sebelum membaca The Art of Computer Programming (TAOCP) , saya belum mempertimbangkan pertanyaan-pertanyaan ini secara mendalam. Saya akan menggunakan kode pseudo untuk menggambarkan algoritma, memahaminya dan memperkirakan waktu berjalan hanya tentang pesanan pertumbuhan. The TAOCP secara...
Teorema Master adalah alat yang indah untuk memecahkan beberapa jenis perulangan . Namun, kami sering mengabaikan bagian integral ketika menerapkannya. Misalnya, selama analisis Mergesort kami dengan senang hati pergi dari T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)\qquad T(n) =...