Algoritma, jejak, dan bukti kebenaran
Diperkenalkan| English | Makna |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algoritma |
| boundary test/ˈbaʊndəri test/ | uji batas |
Apa yang akan menjelaskan pengamatan ini?
- Sebuah algoritma dapat bekerja untuk satu contoh namun gagal pada batas. Pengujian harus dirancang berdasarkan spesifikasi, bukan hanya jalur yang berhasil (happy path).
- Mulailah dengan prediksi. Nyatakan besaran atau fitur apa yang akan Anda bandingkan, lalu tentukan bukti apa yang dapat membedakan dua penjelasan.
Bangun modelnya
- Sebuah algoritma adalah prosedur terbatas dan tak ambigu untuk suatu tugas. Jejak mencatat perubahan keadaan. Invarian perulangan menggambarkan sifat yang dipertahankan oleh setiap iterasi dan membantu membenarkan kebenaran.
- algoritma: Prosedur terbatas yang menyelesaikan tugas yang dinyatakan; uji batas: Tes pada batas rentang input yang diperbolehkan.
Apa yang harus berlaku sebelum menerapkan pencarian biner biasa pada sebuah daftar?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Pencarian biner membuang setengah daftar dengan membandingkan nilai tengah, yang hanya berfungsi jika daftar terurut sesuai aturan perbandingan. Nilai duplikat diperbolehkan, dan panjang berapa pun bisa digunakan.
Pasangkan setiap istilah teknis dengan maknanya yang tepat.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Gunakan definisi untuk membedakan besaran dan proses yang terkait.
Pilih bukti yang boleh mengujinya
- Nyatakan kondisi input dan output yang diharapkan. Gunakan kasus batas, koleksi kosong jika diperbolehkan, duplikat, dan nilai tidak valid. Bedakan algoritma yang salah dari implementasi yang salah atau persyaratan yang tidak lengkap.
- Jejakkan pencarian pada daftar fiksi terurut kecil. Nyatakan konvensi indeksasi. Untuk pencarian biner, perbarui batas sehingga interval sisa mengecil dan tolak input yang tidak terurut kecuali penyortiran merupakan bagian dari tugas.
Dua kebiasaan manakah yang membuat penyelidikan atau model dalam kasus ini lebih dapat dipertanggungjawabkan?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Menyatakan kondisi dan asumsi memungkinkan orang lain mengulangi pekerjaan persis seperti itu, dan mencatat bukti pendukung memungkinkan mereka memeriksa kesimpulan. Menyembunyikan hasil yang bertentangan menghilangkan bukti yang dapat menentang kesimpulan yang salah, dan satu pengukuran tidak pernah dapat menetapkan klaim yang lebih luas.
Bekerja daripada kuantiti yang diketahui
- Nyatakan nilai yang diketahui dan unitnya. Pilih hubungan kerana asumsinya sesuai dengan kes ini, kemudian susun semula sebelum menggantikan.
- Diketahui: pencarian linear pada daftar delapan item dapat memerlukan delapan perbandingan ketika item yang dicari berada di posisi terakhir atau tidak ada. Menggandakan panjang daftar menggandakan jumlah perbandingan kasus terburuk di bawah model ini. Pencarian biner mengurangi interval sekitar setengah setiap langkah tetapi membutuhkan struktur terurut yang sesuai.
Pencarian linear memindai semua 14 item tanpa kecocokan. Berapa banyak perbandingan item yang terjadi? Gunakan urutan yang sama: besaran diketahui → model → hubungan → substitusi → unit dan interpretasi.
Pencarian linear memeriksa semua 14 item tanpa menemukan kecocokan. Berapa banyak perbandingan item yang terjadi?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Hasilnya adalah 14 perbandingan. Diketahui: pencarian linier atas 14 item tanpa kecocokan. Setiap item harus dibandingkan sebelum ketiadaan pasti, sehingga perbandingan = 14. Pencarian yang tidak berhasil selalu memakan biaya sepanjang daftar.
Semak kesimpulan dan had-hadnya
- Tes sampel yang sukses tidak membuktikan kebenaran untuk semua input valid. Jangan mengimpor sintaks pseudocode spesifik Cambridge ke dalam kursus IB tanpa sumber kursus.
- Kembali ke pengamatan awal. Jelaskan apa hasil tersebut mendukung, kondisi apa yang diasumsikannya, dan satu cara untuk menguji penjelasan saingan.
Satu sampel uji yang berhasil membuktikan bahwa algoritma benar untuk setiap input yang valid. Klaim ini salah: Satu uji yang lolos hanya menunjukkan bahwa algoritma bekerja pada input tersebut saja. Kebenaran memerlukan penalaran atas semua input yang valid atau pembuktian—kasus batas seperti daftar kosong dan nilai ambang batas justru merupakan tempat di mana kode yang tidak teruji gagal.
Algoritma, jejak, dan bukti kebenaran: Nyatakan kondisi input dan output yang diharapkan. Gunakan kasus batas, koleksi kosong jika diperbolehkan, duplikat, dan nilai tidak valid. Bedakan algoritma yang salah dari implementasi yang salah atau persyaratan yang tidak lengkap.
Satu tes sampel yang berhasil membuktikan algoritma benar untuk setiap input valid.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Satu tes lulus menunjukkan algoritma bekerja pada input itu saja. Kebenaran memerlukan penalaran atas semua input valid atau pembuktian - kasus tepi seperti daftar kosong dan nilai batas adalah tempat di mana kode yang tidak diuji gagal.
Prosedur terbatas yang menyelesaikan tugas yang dinyatakan: tulis istilah teknisnya.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
algoritma berarti Prosedur terbatas yang menyelesaikan tugas yang dinyatakan.