Praktik yang baik untuk menulis algoritma

Ini tentang seberapa efektif kita dapat mengekspresikan suatu algoritma. Saya membutuhkan ini untuk pengajaran sarjana saya.

Saya mengerti tidak ada yang namanya cara standar untuk menulis kode semu. Penulis yang berbeda mengikuti konvensi yang berbeda.

Akan sangat membantu jika orang-orang di sini menunjukkan, cara mereka mengikuti dan berpikir yang terbaik.

Apakah ada buku yang membahas hal ini dengan sangat baik?

Menulis pseudocode seperti menulis kode: Ini tidak terlalu penting standar mana yang Anda ikuti, selama Anda (dan orang-orang yang menulis dengan Anda) benar-benar mengikuti beberapa standar.

Tetapi sebagai catatan, inilah standar istimewa yang saya gunakan dalam catatan kuliah, makalah penelitian, dan buku saya yang akan datang.

• Gunakan sintaks imperatif standar untuk aliran kontrol dan akses memori - jika, sementara, untuk, kembali, array [indeks], fungsi (argumen). Tuliskan "else if".

  • Tetapi gunakan $field(record)$ sebagai ganti record.fieldataurecord->field

• Gunakan standar notasi matematika untuk matematika - Menulis bukan , sebuah mod b bukan , s ≤ t bukan , bukan , bukan , bukan , bukan , dll .$xy$x*y$a\bmod b$a%b$s\le t$s <= t$\lnot p$!p$\sqrt{x}$sqrt(x)$\pi$PI$\infty$MAX_INT

  • Tetapi gunakan untuk penugasan, untuk menghindari masalah.$x\gets y$==

  • Tetapi hindari notasi (dan kodesemu!) Sepenuhnya jika bahasa Inggris lebih jelas.

    • Secara simetris, hindari Bahasa Inggris jika notasi lebih jelas!

• Minimalkan gula sintaksis - Tunjukkan struktur blok dengan indentasi yang konsisten (à la Python). Hapus kata kunci yang manis seperti "mulai / akhir" atau "do / od" atau "fi". Hapus nomor baris. Jangan tidak menekankan kata kunci seperti "untuk" atau "sementara" atau "jika" dengan menetapkan mereka dalam berbagai typefaceatau gaya . Pernah. Hanya saja, jangan.

  • Tetapi nama-nama algoritma konstanta dan konstanta dalam \ textsc {Small Caps}, nama variabel dalam huruf miring , dan string literal dalam sans serif.

  • Tetapi tambahkan sedikit ruang "bernapas" vertikal ( \\[0.5ex]) di antara potongan kode yang bermakna.

• Jangan menentukan detail yang tidak penting. Jika tidak masalah urutan apa yang Anda kunjungi simpul, cukup katakan "untuk semua simpul".

Sebagai contoh, berikut adalah formulasi rekursif dari algoritma spanning tree minimum Borůvka . Saya sebelumnya telah mendefinisikan sebagai grafik yang diperoleh dari dengan mengontrak semua tepi di set , dan Ratakan sebagai subrutin yang menghilangkan loop dan tepi paralel.$G / L$$G$$L$

Saya menggunakan algorithmlingkungan LaTeX ringan saya sendiri untuk mengeset pseudocode. (Ini hanya tabbinglingkungan di dalam \fbox.) Berikut kode sumber saya untuk algoritma Borůvka:

\begin{algorithm}
	\textul{$\textsc{Borůvka}(G)$:}\+
\\	if $G$ has no edges\+
\\		return $\varnothing$\-
\\[0.5ex]
	$L \gets \varnothing$
\\	for each vertex $v$ of $G$\+
\\		add the lightest edge incident to $v$ to $L$\-
\\[0.5ex]
	return $L \cup \textsc{Borůvka}(\textsc{Flatten}(G / L))$
\end{algorithm}

Saya cenderung menggunakan sesuatu yang menyerupai sintaksis Python. Python sudah cukup dekat dengan pseudocode sehingga dalam beberapa kasus pseudocode saya dapat berubah menjadi kode kerja aktual.

Jika Anda ingin memiliki kode yang pasti (yaitu sedikit atau tidak ada matematika, dekat dengan pemrograman nyata) Anda mungkin ingin mempertimbangkan untuk memiliki kode yang benar-benar dikompilasi. Ini memiliki beberapa keunggulan:

• Anda mendapatkan sorotan sintaksis di mana-mana.
• Compiler memeriksa sintaks untuk Anda dan menerapkan konsistensi.
• Anda dapat menguji unit implementasi Anda untuk meningkatkan kualitas kode.
• Anda dapat menjalankan algoritme dan membandingkan runtime yang diukur dengan analisis (dengan demikian memotivasi teknik analisis lanjutan).

Seorang profesor di universitas saya melakukan ini dalam kursus algoritmanya. Bahasa pilihannya adalah Modula. Tetapi saya tidak berpikir pilihan bahasa tertentu yang penting. Tetaplah pada satu (per paradigma) yang paling sesuai dengan tingkat abstraksi Anda.