Bagaimana cara menggambarkan algoritma, membuktikan dan menganalisisnya?

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 menyeluruh berubah pikiran saya.

TAOCP menggunakan bahasa Inggris yang dicampur dengan langkah-langkah dan goto untuk menggambarkan algoritma, dan menggunakan diagram alur untuk menggambarkan algoritma dengan lebih mudah. Tampaknya level rendah, tetapi saya menemukan bahwa ada beberapa keuntungan, terutama dengan diagram alur, yang telah saya abaikan banyak. Kami dapat memberi label pada masing-masing panah dengan pernyataan tentang keadaan saat ini pada saat perhitungan melintasi panah itu, dan membuat bukti induktif untuk algoritme. Penulis mengatakan:

Ini adalah pendapat penulis bahwa kita benar-benar mengerti mengapa suatu algoritma hanya valid ketika kita mencapai titik yang secara implisit mengisi semua pikiran kita, seperti yang dilakukan pada Gambar.4.

Saya belum mengalami hal seperti itu. Keuntungan lain adalah bahwa, kita dapat menghitung berapa kali setiap langkah dieksekusi. Sangat mudah untuk memeriksa dengan hukum pertama Kirchhoff. Saya belum menganalisis waktu berjalan dengan tepat, sehingga beberapa mungkin telah dihapus ketika saya memperkirakan waktu berjalan.$\pm1$

Analisis pesanan pertumbuhan terkadang tidak berguna. Sebagai contoh, kita tidak dapat membedakan quicksort dari heapsort karena semuanya adalah , di mana adalah jumlah yang diharapkan dari variabel acak , jadi kita harus menganalisis konstanta, katakanlah, dan , sehingga kita dapat membandingkan dan lebih baik. Dan juga, terkadang kita harus membandingkan jumlah lain, seperti varian. Hanya analisis kasar dari pesanan pertumbuhan waktu berjalan tidak cukup. Sebagai TAOCPE X X E ( T 1 ( n ) ) = A 1 n lg n + B 1 n + O ( log n ) E ( T 2 ( n ) ) = A 2 lg n + B 2 n + O $E(T(n))=\Theta(n\log n)$$EX$$X$$E(T_1(n))=A_1n\lg n+B_1n+O(\log n)$T 1 T $E(T_2(n))=A_2\lg n+B_2n+O(\log n)$$T_1$$T_2$ menerjemahkan algoritma ke dalam bahasa rakitan dan menghitung waktu berjalan, Ini terlalu sulit bagi saya, jadi saya ingin tahu beberapa teknik untuk menganalisis waktu berjalan sedikit lebih kasar, yang juga berguna, untuk bahasa tingkat yang lebih tinggi seperti C, C ++ atau kode palsu.

Dan saya ingin tahu gaya deskripsi apa yang terutama digunakan dalam karya penelitian, dan bagaimana cara mengatasi masalah ini.

Ada berbagai macam pendekatan yang layak. Yang paling cocok tergantung pada

• apa yang Anda coba tunjukkan,
• berapa banyak detail yang Anda inginkan atau butuhkan.

Jika algoritme adalah yang dikenal luas yang Anda gunakan sebagai subrutin, Anda sering tetap berada pada level yang lebih tinggi. Jika algoritme adalah objek utama yang sedang diselidiki, Anda mungkin ingin lebih detail. Hal yang sama dapat dikatakan untuk analisis: jika Anda memerlukan batas atas runtime yang kasar, Anda melanjutkan secara berbeda dari saat Anda menginginkan jumlah pernyataan yang tepat.

Saya akan memberi Anda tiga contoh untuk algoritma Mergesort yang terkenal yang mudah-mudahan menggambarkan ini.

Level tinggi

Algoritma Mergesort mengambil daftar, membaginya dalam dua (sekitar) bagian yang sama-sama panjang, berulang pada daftar parsial tersebut dan menggabungkan hasil (diurutkan) sehingga hasil akhirnya diurutkan. Pada daftar tunggal atau kosong, ini mengembalikan input.

Algoritma ini jelas merupakan algoritma pengurutan yang benar. Memisahkan daftar dan menggabungkannya masing-masing dapat diimplementasikan dalam waktu , yang memberi kita perulangan untuk runtime kasus terburuk T ( n ) = 2 T ( $\Theta(n)$. Dengan teorema Master, ini dievaluasi menjadiT(n)∈Θ(nlogn).$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$$T(n) \in \Theta(n\log n)$

Tingkat Sedang

Algoritma Mergesort diberikan oleh pseudo-code berikut:

procedure mergesort(l : List) {
  if ( l.length < 2 ) {
    return l
  }

  left  = mergesort(l.take(l.length / 2)
  right = mergesort(l.drop(l.length / 2)
  result = []

  while ( left.length > 0 || right.length > 0 ) {
    if ( right.length == 0 || (left.length > 0 && left.head <= right.head) ) {
      result = left.head :: result
      left = left.tail
    }
    else {
      result = right.head :: result
      right = right.tail
    }
  }

  return result.reverse
}

Kami membuktikan kebenaran dengan induksi. Untuk daftar panjang nol atau satu, algoritme itu sepele benar. Sebagai hipotesis induksi, anggap mergesortberkinerja benar pada daftar panjang paling banyak untuk beberapa arbitrer, tetapi tetap alami n > 1 . Sekarang mari L menjadi daftar panjang n + 1 . Dengan hipotesis induksi, dan tahan (tidak menurun) versi yang diurutkan dari resp pertama. paruh kedua L setelah panggilan rekursif. Oleh karena itu, loop memilih di setiap iterasi elemen terkecil yang belum diselidiki dan menambahkannya ; dengan demikian adalah daftar yang tidak diurutkan yang mengandung semua elemen dari$n$$n>1$$L$$n+1$leftright$L$whileresultresultleftdan right. Kebalikannya adalah versi yang tidak diurutkan secara bertahap , yang merupakan hasil - dan yang diinginkan - yang dikembalikan.$L$

Sedangkan untuk runtime, mari kita hitung perbandingan elemen dan operasi daftar (yang mendominasi runtime tanpa gejala). Daftar panjangnya kurang dari dua tidak menyebabkan keduanya. Untuk daftar panjang , kami memiliki operasi yang disebabkan oleh menyiapkan input untuk panggilan rekursif, yang dari panggilan rekursif sendiri ditambah loop dan satu . Kedua parameter rekursif dapat dihitung dengan paling banyak n operasi daftar masing-masing. The loop dieksekusi persis n kali dan setiap iterasi penyebab paling banyak satu perbandingan elemen dan tepat dua operasi daftar. Final dapat diimplementasikan menggunakan 2 $n>1$whilereverse$n$while$n$reverse$2n$operasi daftar - setiap elemen dihapus dari input dan dimasukkan ke dalam daftar output. Oleh karena itu, hitungan operasi memenuhi pengulangan berikut:

$\qquad \begin{align}T(0) = T(1) &= 0 \\ T(n) &\leq T\left(\left\lceil\frac{n}{2}\right\rceil\right) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + 7n\end{align}$

Karena jelas tidak menurun, cukup untuk mempertimbangkan n = 2 k untuk pertumbuhan asimptotik. Dalam hal ini , perulangan disederhanakan menjadi$T$$n=2^k$

$\qquad \begin{align}T(0) = T(1) &= 0 \\ T(n) &\leq 2T\left(\frac{n}{2}\right) + 7n\end{align}$

Dengan teorema Master, kita mendapatkan yang meluas ke runtime .$T \in \Theta(n \log n)$mergesort

Tingkat sangat rendah

Pertimbangkan penerapan Mergesort di Isabelle / HOL ini :

types dataset  =  "nat * string"

fun leq :: "dataset \<Rightarrow> dataset \<Rightarrow> bool" where
   "leq (kx::nat, dx) (ky, dy) = (kx \<le> ky)"

fun merge :: "dataset list \<Rightarrow> dataset list \<Rightarrow> dataset list" where
"merge [] b = b" |
"merge a [] = a" |
"merge (a # as) (b # bs) = (if leq a b then a # merge as (b # bs) else b # merge (a # as) bs)"

function (sequential) msort :: "dataset list \<Rightarrow> dataset list" where
  "msort []  = []" |
  "msort [x] = [x]" |
  "msort l   = (let mid = length l div 2 in merge (msort (take mid l)) (msort (drop mid l)))"
by pat_completeness auto
  termination
  apply (relation "measure length")
by simp+

Ini sudah termasuk bukti-bukti yang jelas dan terminasi. Temukan (hampir) bukti kebenaran lengkap di sini .

Untuk "runtime", yaitu jumlah perbandingan, perulangan yang serupa dengan yang ada di bagian sebelumnya dapat diatur. Alih-alih menggunakan teorema Master dan melupakan konstanta, Anda juga dapat menganalisisnya untuk mendapatkan perkiraan yang secara asimtotik sama dengan kuantitas sebenarnya. Anda dapat menemukan analisis lengkap dalam [1]; di sini adalah garis besar kasar (tidak sesuai dengan kode Isabelle / HOL):

Seperti di atas, pengulangan untuk jumlah perbandingan adalah

$\qquad \begin{align}f_0 = f_1 &= 0 \\ f_n &= f_{\left\lceil\frac{n}{2}\right\rceil} + f_{\left\lfloor\frac{n}{2}\right\rfloor} + e_n\end{align}$

di mana adalah jumlah perbandingan yang diperlukan untuk menggabungkan hasil parsial². Untuk menyingkirkan lantai dan langit-langit, kami melakukan perbedaan kasus tentang apakah n genap:$e_n$$n$

$\qquad \displaystyle \begin{cases} f_{2m} &= 2f_m + e_{2m} \\ f_{2m+1} &= f_m + f_{m+1} + e_{2m+1} \end{cases}$

Menggunakan perbedaan maju / mundur bersarang dari dan e n kita mendapatkan itu$f_n$$e_n$

.$\qquad \displaystyle \sum\limits_{k=1}^{n-1} (n-k) \cdot \Delta\kern-.2em\nabla f_k = f_n - nf_1$

Jumlahnya cocok dengan sisi kanan rumus Perron . Kami mendefinisikan Dirichlet pembangkit seri dari sebagai$\Delta\kern-.2em\nabla f_k$

$\qquad \displaystyle W(s) = \sum\limits_{k\geq 1} \Delta\kern-.2em\nabla f_k k^{-s} = \frac{1}{1-2^{-s}} \cdot \underbrace{\sum\limits_{k \geq 1} \frac{\Delta\kern-.2em\nabla e_k}{k^s}}_{=:\ \boxminus(s)}$

yang bersama-sama dengan formula Perron membawa kita ke

$\qquad \displaystyle f_n = nf_1 + \frac{n}{2\pi i} \int\limits_{3-i\infty}^{3+i\infty} \frac{\boxminus(s)n^s}{(1-2^{-s})s(s+1)}ds$

$\boxminus(s)$

$\qquad \displaystyle f_n \sim n \cdot \log_2(n) + n \cdot A(\log_2(n)) + 1$

$A$$[-1,-0.9]$

1. Transformasi Mellin dan asimptotik: rekurensi mergesort oleh Flajolet dan Golin (1992)
2. $e_n = \left\lfloor\frac{n}{2}\right\rfloor$
   $e_n = n-1$
   $e_n = n - \frac{\left\lfloor\frac{n}{2}\right\rfloor}{\left\lceil\frac{n}{2}\right\rceil + 1} - \frac{\left\lceil\frac{n}{2}\right\rceil}{\left\lfloor\frac{n}{2}\right\rfloor + 1}$

"Disiplin Pemrograman" Dijkstra adalah tentang menganalisis dan membuktikan algoritma dan merancang untuk kemampuan. Dalam kata pengantar untuk buku itu, Dijkstra menjelaskan bagaimana sebuah bahasa mini yang sangat sederhana yang dirancang dengan baik untuk dianalisis cukup untuk menjelaskan banyak algoritma secara formal:

Ketika memulai sebuah buku seperti ini, seseorang langsung dihadapkan pada pertanyaan: "Bahasa pemrograman mana yang akan saya gunakan?", Dan ini bukanhanya pertanyaan presentasi! Aspek yang paling penting, tetapi juga paling sulit dipahami, dari alat apa pun adalah pengaruhnya terhadap kebiasaan mereka yang melatih diri dalam penggunaannya. Jika alat ini adalah bahasa pemrograman, pengaruh ini - apakah kita suka atau tidak - pengaruh pada kebiasaan berpikir kita. Setelah menganalisis pengaruh itu sepengetahuan saya, saya sampai pada kesimpulan bahwa tidak ada bahasa pemrograman yang ada, maupun sebagian dari mereka, yang sesuai dengan tujuan saya; di sisi lain saya tahu diri saya sangat tidak siap untuk merancang bahasa pemrograman baru sehingga saya telah bersumpah untuk tidak melakukannya selama lima tahun ke depan, dan saya memiliki perasaan yang sangat berbeda bahwa periode itu belum berlalu! (Sebelum itu, di antara banyak hal lainnya, monograf ini harus ditulis.

Kemudian dia menjelaskan betapa kecilnya dia berhasil mendapatkan bahasa mini.

Saya berhutang pada pembaca mengapa saya menggunakan bahasa mini begitu kecil sehingga tidak mengandung prosedur dan rekursi. ... Intinya adalah bahwa saya merasa tidak membutuhkan mereka untuk menyampaikan pesan saya, yaitu. bagaimana pemisahan keprihatinan yang dipilih dengan cermat sangat penting untuk desain dalam semua hal, program-program berkualitas tinggi; alat-alat sederhana dari bahasa mini memberi kami lebih dari cukup garis lintang untuk desain nontrivial, namun sangat memuaskan.