Apa artinya mengatakan suatu algoritma adalah Suara dan Lengkap?

Saya mendengar berbagai interpretasi suara dan lengkap . Saya mengerti bahwa kelengkapan berarti menemukan solusi jika ada. Apa artinya mengatakan suatu algoritma adalah suara .

Apa artinya mengatakan suatu algoritma adalah Suara dan Lengkap?

Ini adalah istilah yang sangat spesifik terkait dengan logika.

Inilah beberapa poin awal:

http://en.wikipedia.org/wiki/Soundness

http://en.wikipedia.org/wiki/Completeness_(logic)

Pada dasarnya, tingkat kesehatan (dari suatu algoritma) berarti bahwa algoritma tersebut tidak menghasilkan hasil yang tidak benar. Jika, misalnya, saya memiliki algoritme pengurutan yang kadang-kadang tidak mengembalikan daftar yang diurutkan, algoritme tidak bersuara.

Kelengkapan, di sisi lain, berarti bahwa algoritma alamat semua input yang mungkin dan tidak ketinggalan. Jadi, jika algoritma pengurutan saya tidak pernah mengembalikan daftar yang tidak disortir, tetapi hanya menolak untuk bekerja pada daftar yang berisi angka 7, itu tidak akan lengkap.

Lengkap dan masuk akal jika bekerja pada semua input (semantik berlaku di dunia program) dan selalu mendapatkan jawaban yang benar.

Saya menemukan jawaban Erik Dietrich agak membingungkan. Berikut ini lebih baik:

Algoritma adalah suara jika, kapan saja mengembalikan jawaban, jawaban itu benar. Algoritma selesai jika menjamin untuk mengembalikan jawaban yang benar untuk setiap input yang sewenang-wenang (atau, jika tidak ada jawaban, itu menjamin untuk mengembalikan kegagalan).

Dua poin penting:

1. Kesehatan adalah jaminan yang lemah. Itu tidak menjanjikan bahwa A akan berakhir.
2. Kesehatan dan Kelengkapan adalah konsep terkait; Bahkan mereka adalah kebalikan dari satu sama lain. yaitu Soundness mengatakan bahwa jika jawaban dikembalikan jawaban itu benar. Kelengkapan mengatakan bahwa jawaban itu benar jika dikembalikan.

Pertimbangkan untuk contoh algoritma pengurutan A yang menerima sebagai input daftar angka. Kami mengatakan bahwa A adalah bunyi jika setiap kali mengembalikan hasil yang hasilnya adalah daftar diurutkan. Demikian juga, kami mengatakan bahwa A lengkap jika jaminan untuk mengembalikan daftar yang diurutkan setiap kali kami memberikan daftar angka.

Istilah-istilah ini berasal dari teori komputasi, sehingga mereka lebih bermakna dalam konteks teori komputasi daripada dalam konteks rekayasa perangkat lunak

Dalam sebagian besar model komputasi standar, masalah komputasi direpresentasikan sebagai bahasa . Bahasa adalah seperangkat string. Algoritme, kemudian, hanyalah sebuah sistem atau prosedur yang memutuskan apakah string yang diberikan adalah anggota dari beberapa bahasa (dengan mengembalikan benar atau salah). Dalam istilah rekayasa perangkat lunak, teori perhitungan secara khusus berkaitan dengan fungsi yang terlihat seperti ini, dengan asumsi string tidak berubah:

boolean some_function(string argument){...}

Kami menyebut fungsi ini selesai jika mengembalikan true untuk setiap argumen yang merupakan anggota bahasa. Kami menyebutnya bunyi jika menghasilkan false untuk setiap argumen yang bukan anggota bahasa.

Dengan kata lain, itu lengkap jika selalu mengembalikan true ketika kita ingin mengembalikan true, dan terdengar jika itu selalu mengembalikan false ketika kita ingin itu mengembalikan false.

Bagaimana ini diterjemahkan ke jenis fungsi lainnya? Ternyata, hampir selalu mungkin untuk memasukkan jumlah data yang berubah-ubah menjadi string dan menyusunnya kembali di dalam fungsi. Jadi pembatasan pada tipe argumen dan arity tidak lebih dari penyederhanaan teoretis. Namun, pembatasan jenis pengembalian lebih penting. Masalah yang membutuhkan hasil boolean disebut masalah keputusan . Banyak teori perhitungan melibatkan masalah keputusan; set P dan NP dibatasi untuk masalah keputusan (dan NP, setidaknya, tidak dapat didefinisikan secara wajar tanpa batasan ini). Masalah penghentian adalah contoh lain dari masalah keputusan yang banyak dipelajari.

Saya berpendapat bahwa istilah-istilah ini tidak menggeneralisasi di luar domain masalah keputusan, sehingga perbedaan di antara mereka tidak benar-benar bermakna ketika membahas fungsi umum.

Ada jawaban yang jauh lebih baik di SO . Pada dasarnya, Anda memberikan beberapa pengumpulan data dan kriteria untuk dicari. Algoritma suara hanya menangkap Anda ikan yang cocok dengan kriteria tetapi mungkin melewatkan beberapa item data. Algoritma lengkap menghasilkan superset dari hasil yang diminta, yang berarti Anda menerima beberapa sampah di atas hasil yang diminta. Algoritma suara lebih konservatif.

Ahli statistik mungkin akan mengatakan bahwa algoritma suara bias bias kesalahan tipe I (itu tidak menerima kandidat yang benar), sedangkan algoritma lengkap bias terhadap kesalahan tipe II (untuk menerima kandidat palsu).