Bagaimana loop invarian diperoleh dalam algoritma pencarian akar terikat kuadrat ini?

Awalnya pada matematika. SE tetapi tidak dijawab di sana.

Pertimbangkan algoritma berikut.

u := 0
v := n+1;
while ( (u + 1) is not equal to v) do
   x :=  (u + v) / 2;
   if ( x * x <= n) 
     u := x;
   else
     v := x;
   end_if
end_while 

di mana u, v, dan n adalah bilangan bulat dan operasi divisi adalah pembagian integer.

• Jelaskan apa yang dihitung oleh algoritma.
• Dengan menggunakan jawaban Anda untuk bagian I sebagai kondisi akhir untuk algoritme, buat loop invarian dan tunjukkan bahwa algoritme berakhir dan sudah benar.

Di kelas, post-kondisi ditemukan dan Invarian adalah . Saya tidak begitu mengerti tentang bagaimana post-kondisi dan invarian diperoleh. Saya pikir kondisi posting adalah ... yang jelas bukan itu masalahnya. Jadi saya bertanya-tanya bagaimana cara mendapatkan post-condition dan invarian. Saya juga bertanya-tanya tentang bagaimana pra-kondisi dapat diperoleh dengan menggunakan post-kondisi.$0 \leq u^2 \leq n < (u + 1)^2$$0 \leq u^2 \leq n < v^2, u + 1 \leq v$$u + 1 = v$

Gilles benar bahwa teknik umumnya adalah memancing untuk pengamatan yang menarik.

Dalam hal ini, Anda dapat mengamati bahwa program tersebut adalah turunan dari pencarian biner, karena memiliki bentuk sebagai berikut:

while i + 1 != k
  j := strictly_between(i, k)
  if f(j) <= X then i := j
  if f(j) > X then k := j

Kemudian Anda cukup memasukkan tertentu f, X... ke dalam invarian umum untuk pencarian biner. Dijkstra memiliki diskusi yang bagus tentang pencarian biner .

$u+1=v$ memang post-kondisi dari loop sementara (mengapa Anda pikir itu "jelas" bukan itu masalahnya?). Ini selalu terjadi dengan loop sementara yang tidak mengandung a break: ketika loop keluar, itu hanya bisa karena kondisi loop (di sini, ) salah. Bukan satu-satunya hal yang akan menjadi kenyataan ketika loop keluar di sini (algoritma ini sebenarnya menghitung sesuatu yang menarik, seperti yang Anda lihat di kelas Anda, jadi dan juga post-kondisi), tetapi itu adalah yang paling jelas.$u+1 \neq v$$u = \text{[this interesting thing]}$$v = \text{[this interesting thing]}$

Sekarang, untuk menemukan properti menarik lainnya, tidak ada resep umum. Bahkan, ada beberapa pengertian formal di mana tidak ada resep umum untuk menemukan invarian loop. Yang terbaik yang dapat Anda lakukan adalah menerapkan beberapa teknik yang hanya berfungsi dalam beberapa kasus, atau biasanya memancing untuk pengamatan yang menarik (yang bekerja lebih baik dan lebih baik saat Anda semakin berpengalaman).

Jika Anda menjalankan loop untuk beberapa iterasi dengan nilai , Anda akan melihat itu di setiap iterasi:$n$

• baik melompat ke ;$u$$(u+v)/2$
• atau melompat ke .$v$$(u+v)/2$

Secara khusus, memulai kurang dari , dan tidak akan pernah menyalipnya. Selanjutnya, mulai positif dan meningkat, sedangkan dimulai pada dan menurun. Jadi adalah invarian di seluruh program ini.$u$$v$$u$$v$$n+1$$0 \le u \le v \le n+1$

Satu hal yang tidak begitu jelas adalah apakah bisa sama dengan . Itu penting: jika dan pernah menjadi sama, kita akan memiliki dan loop akan terus berjalan selamanya. Jadi, Anda perlu membuktikan bahwa dan tidak pernah menjadi sama untuk membuktikan bahwa algoritma tersebut benar (yaitu tidak berulang selamanya). Setelah kebutuhan ini telah diidentifikasi, mudah untuk membuktikan (saya meninggalkan ini sebagai latihan) bahwa adalah invarian loop (perlu diingat bahwa dan adalah bilangan bulat, jadi ini setara dengan ).$u$$v$$u$$v$$x = u = v$$u$$v$$u < v$$u$$v$$u+1 \le v$

Karena pada akhir program, post-kondisi yang diberikan kepada Anda juga dapat ditulis (bagian sepele). Alasan kami menginginkan post-kondisi seperti ini, yang melibatkan , adalah bahwa kami ingin mengikat hasil program dengan input . Kenapa kondisinya tepat seperti ini? Kami sedang mencari sesuatu yang setepat mungkin, dan kami melihat di mana muncul di dalam loop:$v = u+1$$u^2 \le n < v^2$$0 \le u^2$$n$$n$$n$

• kami memiliki ;$u \le x \le v$
• ketika , kita memilih berikutnya menjadi , sehingga (dan tidak berubah);$x^2 \le n$$u$$x$$u^2 \le n$$v$
• ketika , kita memilih berikutnya menjadi , sehingga (dan tidak berubah).$x^2 > n$$v$$x$$n < v^2$$u$

Petunjuk dikotomi ini bahwa mungkin sepanjang waktu. Dengan kata lain, kami menduga itu loop invarian. Memverifikasi ini dibiarkan sebagai latihan untuk pembaca (ingat untuk memeriksa bahwa properti itu benar pada awalnya).$u^2 \le n < v^2$

Dan sekarang setelah kita melakukan semua ini, kita melihat bahwa dan : adalah akar kuadrat dari dibulatkan ke bilangan bulat terdekat.( u + 1 ) 2 > n u $u^2 \le n$$(u+1)^2 > n$$u$$n$