Python - Pembenaran Algoritma

Untuk membuat klaim tentang Algoritma yang efisien kita membutuhkan beberapa alat matematika sebagai bukti. Alat-alat ini membantu kami dalam memberikan penjelasan yang memuaskan secara matematis tentang kinerja dan keakuratan algoritme. Di bawah ini adalah daftar dari beberapa alat matematika yang dapat digunakan untuk membenarkan satu algoritma di atas yang lain.

• Direct Proof:

  Ini adalah verifikasi langsung dari pernyataan tersebut dengan menggunakan perhitungan langsung. Misalnya jumlah dua bilangan genap selalu merupakan bilangan genap. Dalam hal ini tambahkan saja dua angka yang Anda selidiki dan verifikasi hasilnya sebagai genap.

• Proof by induction:

  Di sini kita mulai dengan contoh spesifik dari sebuah kebenaran dan kemudian menggeneralisasikannya ke semua kemungkinan nilai yang merupakan bagian dari kebenaran. Pendekatannya adalah dengan mengambil kasus kebenaran yang diverifikasi, kemudian membuktikannya juga benar untuk kasus berikutnya untuk kondisi tertentu yang sama. Misalnya semua bilangan positif berbentuk 2n-1 ganjil. Kami membuktikannya untuk nilai n tertentu, kemudian membuktikannya untuk nilai n berikutnya. Ini menetapkan pernyataan secara umum benar dengan bukti induksi.

• Proof by contraposition:

  Pembuktian ini didasarkan pada kondisi Jika Not A berarti Not B maka A berarti B. Contoh sederhananya adalah jika kuadrat dari n adalah genap maka n harus genap. Karena jika kuadrat pada n tidak genap maka n bukan genap.

• Proof by exhaustion:

  Ini serupa dengan pembuktian langsung tetapi ditetapkan dengan mengunjungi setiap kasus secara terpisah dan membuktikannya masing-masing. Contoh bukti tersebut adalah teorema empat warna.