Subscribe to DeepL Pro to translate larger documents.

Visit [Link]/pro for more information.

Lihat diskusi, statistik, dan profil penulis untuk publikasi ini di: [Link]

Algoritma Pelacakan Mundur Serbaguna

Artikel di Jurnal Komputasi Simbolik - Juli 1994

DOI: 10.1006/jsco.1994.1035 - Sumber: DBLP

KUTIPAN MEMBACA

47 6,226

2 penulis:

Hilary Priestley Martin Ward

Universitas Oxford Universitas De Montfort
90 PUBLIKASI 9.288 KUTIPAN 76 PUBLIKASI 1.431 KUTIPAN

LIHAT PROFIL LIHAT PROFIL

Semua konten yang mengikuti halaman ini diunggah oleh Martin Ward pada tanggal 25 Oktober 2017.

Pengguna telah meminta peningkatan file yang diunduh.

 Algoritma Pelacakan Mundur Serbaguna

H.A. Priestley M.P. Ward

HAP@@[Link] [Link]@@[Link]
Mathematical Institute Departemen Ilmu Komputer
24/29, St Giles Laboratorium Sains South
Oxford OX1 3LB Rd
Durham DH1 3LE

17 Januari 2003

Abstrak
Sebuah algoritma backtracking dengan pemilihan urutan elemen disajikan, dan
efisiensinya didiskusikan dalam kaitannya dengan contoh standar dan contoh mengenai peta
yang mempertahankan relasi yang mana algoritma ini diturunkan untuk menyelesaikannya.

1 Pendahuluan
Backtracking telah lama digunakan sebagai strategi untuk menyelesaikan masalah
kombinatorial dan telah dipelajari secara ekstensif (Gerhart & Yelowitz (1976), Roever (1978),
Walker (1960), Wells (1971)). Dalam situasi terburuk, metode ini bisa jadi sangat tidak efisien,
dan analisis sistematis mengenai efisiensi sangat sulit dilakukan. Oleh karena itu, backtracking
terkadang dianggap sebagai metode pilihan terakhir. Namun demikian, algoritma-algoritma
backtracking banyak digunakan, terutama pada masalah-masalah yang tidak lengkap (NP-
complete). Untuk membuat algoritma-algoritma ini layak secara komputasi pada berbagai
macam masalah-masalah besar, algoritma-algoritma ini biasanya disesuaikan untuk aplikasi-
aplikasi tertentu (lihat, sebagai contoh, pendekatan Butler dan Lam untuk pengujian
isomorfisme dalam Butler & Lam (1985) dan pendekatan Knuth dan Szwarcfiter untuk
pengurutan topologi (yaitu, memperluas urutan-urutan parsial ke urutan-urutan linear) Knuth &
Szwarcfiter (1974)).
Pendekatan kami untuk melakukan backtracking didasarkan pada karya Ward tentang
transformasi program Ward (1989), Ward (1992), Ward (1994), Ward (1993). Kami
mendapatkan (dan sekaligus membuktikan kebenaran) sebuah algoritma backtracking sederhana
yang 'universal'. Bahkan dalam bentuk yang belum sempurna ini, algoritma kami terbukti sangat
efektif untuk jenis masalah yang dirancang. Masalah-masalah ini semua dapat dianggap sebagai masalah-
masalah yang membutuhkan penghitungan, pencatatan, atau pemrosesan, dari peta-peta yang menjaga
relasi dari sebuah struktur relasi berhingga ke struktur relasi lain dengan tipe yang sama.
Khususnya pengujian isomorfisme akan berada di bawah payung ini. Priestley secara khusus
memperhatikan masalah-masalah yang muncul sehubungan dengan dualitas tipe Stone untuk
jenis-jenis aljabar yang anggotanya adalah kisi-kisi distributif dengan struktur tambahan.
Ternyata, dalam aplikasi ini, waktu berjalannya algoritma sangat bergantung pada urutan
elemen data yang didaftarkan (dengan faktor beberapa ribu). Teknik yang sama yang
menghasilkan algoritma backtracking sederhana kemudian digunakan untuk mendapatkan versi
algoritma yang menggabungkan mekanisme untuk permutasi elemen. Dengan mengeksploitasi hal
ini dengan berbagai cara, peningkatan efisiensi yang sangat besar diperoleh yang memungkinkan
kami untuk menyelesaikan berbagai perhitungan yang sebelumnya tidak praktis. Tabel 3 dan 4 pada
Bagian 6.2 secara mencolok mengilustrasikan efek dari pemilihan urutan elemen yang bijaksana
pada satu kasus tertentu.

1
 Makalah ini ditujukan untuk dua kelompok pembaca yang (mungkin) memiliki
persinggungan yang kecil. Kelompok pertama terdiri dari mereka yang tertarik dengan
pelacakan mundur itu sendiri. Kelompok kedua terdiri dari para matematikawan yang perlu
menyelesaikan masalah-masalah dalam, contohnya, aljabar atau teori graf, dimana metode-
metode kami dapat diterapkan. Untuk kepentingan para pembaca seperti itu, kami telah menyertakan
beberapa diskusi tentang aspek-aspek pemrograman

2
cerita rakyat yang tidak diperlukan dalam makalah yang ditujukan hanya untuk ilmuwan
komputer.
Makalah ini disusun sebagai berikut. Bagian 2, yang menggunakan teka-teki delapan ratu
yang terkenal sebagai ilustrasi, memiliki dua tujuan. Bagian ini memberikan pengenalan singkat
tentang backtracking bagi mereka yang tidak terbiasa dengannya, dan juga memungkinkan kita
untuk menarik perhatian pada faktor-faktor yang mempengaruhi efisiensi yang akan kita bahas
nanti. Bagian 3 menyajikan bagian dari Bahasa Spektrum Lebar (WSL) dari Ward yang kami
gunakan, dan Bagian 4 berisi teori dari karya Ward tentang transformasi program yang menjadi
dasar dari turunan algoritma kami. Algoritma backtracking sederhana diberikan di Bagian 5.
Bagian selanjutnya membahas aplikasi-aplikasi dari algoritma ini yang menjadi dasar dari
makalah ini. Bagian ini memberikan latar belakang matematis dari berbagai contoh yang telah
kami uji dengan metode kami. Meskipun Bagian 6 cukup lengkap, bagian ini ditujukan terutama
untuk para matematikawan dengan minat yang sesuai. Bagian 7 membahas berbagai heuristik
untuk pemilihan urutan elemen, dengan ilustrasi. Kami menyimpulkan dengan beberapa
komentar singkat yang relevan dengan perkembangan lebih lanjut: kami mendiskusikan keadaan
terkini mengenai otomatisasi lengkap dari proses pengembangan algoritma, dari spesifikasi
abstrak hingga implementasi dalam bahasa pemrograman yang sesuai.
Kami menekankan bahwa pemahaman tentang mesin di Bagian 4-5 tidak diperlukan oleh
pengguna produk akhir. Teori ini menjamin bahwa algoritme memenuhi spesifikasinya. Karena
sifatnya yang universal, algoritme (dengan atau tanpa pemilihan urutan elemen) dapat dengan
mudah diadaptasi ke berbagai situasi tanpa harus mengacu pada teori. Implementasi sangat
mudah. Kami membahas masalah implementasi dalam kasus khusus di Bagian 6. Kami juga
menyertakan Lampiran yang memberikan implementasi C dari algoritma backtracking
sederhana. Kode sumber untuk semua algoritma dan file-file contoh data dapat diperoleh dari
penulis.

2 Teka-teki Delapan Ratu

Akan lebih mudah untuk memperkenalkan konsep backtracking dengan menggunakan teka-teki
sederhana, yaitu masalah delapan ratu:
Ada berapa cara untuk menempatkan delapan ratu di papan catur sedemikian rupa sehingga
tidak ada ratu yang menyerang ratu lainnya?
Dua ratu saling menyerang jika mereka berada pada baris, kolom, atau diagonal yang sama. Gambar 1
mengilustrasikan salah satu solusinya.

Gambar 1: Salah satu solusi untuk teka-teki delapan ratu.

Solusi brute force untuk masalah kombinatorial adalah menghitung semua solusi yang mungkin,

3
menguji setiap solusi secara bergantian dan menolak solusi yang tidak memenuhi syarat. Dalam
kasus ini, metode "paling kasar" menguji setiap kemungkinan susunan delapan ratu pada papan
catur. Ada 64 tempat untuk ratu pertama, untuk masing-masingnya ada 63 tempat untuk ratu kedua,
dan seterusnya, untuk

4
total 64 × 63 × - - × 57 = [Link].760 kasus. Jumlah ini dapat dikurangi secara substansial
dengan pengamatan bahwa setiap solusi yang valid harus mengandung tepat satu ratu di setiap
kolom. Jadi kita hanya perlu mempertimbangkan 88 = 16.777.216 cara untuk menempatkan
delapan ratu, satu per kolom, ke dalam delapan kolom. Setiap susunan tersebut dapat
direpresentasikan sebagai sebuah urutan delapan angka dari 1 sampai 8, contohnya situasi pada
Gambar 1 direpresentasikan sebagai ⟨3, 6, 4, 1, 8, 5, 7, 2⟩.

2.1 Mundur ke belakang

Sebuah cara sederhana untuk mengurangi jumlah kasus lebih jauh lagi sekarang muncul dengan
sendirinya. Pertimbangkan situasi di mana dua ratu pertama telah ditempatkan pada posisi 1 dan 1,
atau 1 dan 2 pada dua kolom pertama. Karena keduanya saling menyerang, kita tidak perlu
mempertimbangkan salah satu dari 26 = 262.144 cara untuk menempatkan enam ratu yang tersisa.
Demikian pula, setelah menempatkan empat ratu pertama pada Gambar 1, hanya ada dua posisi yang
valid untuk ratu kelima. Penempatan berurutan seperti itu dapat direpresentasikan sebagai sebuah
struktur pohon, seperti yang ditunjukkan pada Gambar 2 untuk teka-teki empat ratu. Empat simpul di
bawah akar
/ /// Pz P
/// \ z Pz PP
// \zP
/
////// \ z Pz PP
/ z PP P
\ z PP
z
1 / /// \2 zz PP 4
P
3
///\
/ PP //\@
PP
/ /\ PP / /\@
/ / \ PP / / \@
// / \ 13 PPP / / \ @ 24
14
11 12 //\@ //\@ 21 22 23 //\@
/ /\@ / /\@ / /\@
/ / \@ / / \@ / / \@
/ / \ @ / /142 \ @ 241 / / \ @
131 132 133 134 141 //\@ 143 144 //\@ 242 243 244
/ /\@ / /\@
/ / \@ / / \@
/ / \ @ / / \ @
1421 1422 1423 14242411 2412 2413 2414

Gambar 2: Pohon Pencarian Empat Ratu

Simpul (atas) dari pohon mewakili empat posisi untuk ratu pertama. Di bawah setiap simpul yang
valid terdapat simpul-simpul lebih lanjut yang merepresentasikan posisi-posisi untuk ratu berikutnya
yang akan ditempatkan. Perhatikan bahwa cabang 3 dan 4 dari pohon tersebut adalah bayangan
cermin dari cabang 2 dan 1, dan dihilangkan untuk mempersingkat. Solusinya adalah ⟨2, 4, 1, 3⟩ dan
bayangan cerminnya ⟨3, 1, 4, 2⟩.
Prosedur ini memangkas jumlah kasus yang diperiksa (untuk teka-teki delapan ratu) menjadi
15.720 kasus. Untuk menghitung secara sistematis semua kasus ini, kita mulai dari akar dan
bergerak ke bawah pohon, mengambil cabang paling kiri pada setiap persimpangan, tetapi jika tidak
mungkin untuk bergerak ke bawah, kita "mundur" dengan mempertimbangkan persimpangan
berikutnya pada level sebelumnya. Hal ini dapat menyebabkan penelusuran mundur lebih lanjut jika
semua persimpangan pada level sebelumnya telah tercakup. Formulasi terkomputerisasi pertama dari
metode ini adalah oleh Walker pada tahun 1958 (Walker (1960)).
Dengan mengasumsikan kita memiliki sebuah predikat valid(p) yang menguji apakah urutan
bilangan bulat p adalah sebuah susunan ratu yang valid tanpa ada ratu yang menyerang ratu yang
lain, maka prosedur rekursif berikut ini akan menyelesaikan masalah. (Notasi p ++ ⟨t⟩ menyatakan
5
urutan p dengan urutan tunggal
⟨t⟩ ditambahkan. Lihat Bagian 3 untuk penjelasan tentang notasi lainnya).
mulai
count := 0;
Ratu(⟨⟩)
di mana
proc Queens(p) ≡
if l(p) = 8 then count := count + 1

6
 else for t := 1 to 8 do
if valid(p ++ ⟨t⟩) then Queens(p ++ ⟨t⟩) fi od.
akhir
Ini adalah kasus khusus dari algoritma yang akan kita bahas di Bagian 5. Juga di Bagian 5 kita akan
mengubah algoritma rekursif ini menjadi algoritma iteratif yang setara:
count := 0;
var p := ⟨⟩, t := 1 :
while p /= ⟨⟩ ∨ t ≤ 8 do
last
jika t > 8 maka t←- p; t := t + 1
elsif valid(p ++ ⟨t⟩) ∧ l(p) = 7 then count := count + 1; t := t + 1
elsif valid(p ++ ⟨t⟩) ∧ l(p) < 7 then p := p ++ ⟨t⟩; t := 1
else t := t + 1 fi od end
Program rekursif menekankan gerakan ke bawah dalam pohon. Backtracking (pergerakan ke atas)
terjadi sebagai hal yang biasa ketika setiap posisi dalam kolom telah dipertimbangkan. Program
iteratif menekankan pelacakan balik dengan secara eksplisit mencari ke atas dan ke bawah pohon,
bekerja dari kiri ke kanan. Empat kasus dalam perulangan yang d i t a n g a n i :
1. Bergerak ke atas, yaitu mundur ke belakang;
2. Bergerak ke kanan ketika solusi telah ditemukan;
3. Pindah ke cabang paling kiri dari simpul saat ini, dan;
4. Bergerak ke kanan ketika pengaturan saat ini tidak valid.

2.2 Pemilihan Urutan Elemen

Sejauh ini kita telah mengasumsikan bahwa ratu-ratu akan ditempatkan di kolom mereka dari kiri ke
kanan, tetapi ini sama sekali tidak penting. Penempatan kelompok ratu dapat dilakukan dalam urutan
apa saja tanpa mempengaruhi hasil akhir; namun, urutan yang berbeda dapat menghasilkan lebih
sedikit kasus yang perlu dianalisis. Perhatikan situasi pada Gambar 3 di mana tiga ratu pertama telah
ditempatkan di tiga kolom pertama. Di sini, kita memiliki tiga tempat untuk ratu berikutnya di kolom
4 dan 5 (ditandai dengan s ), tetapi

Gambar 3: Solusi parsial

hanya satu tempat di kolom 6. Menempatkan ratu berikutnya pada kolom 6 (bukan kolom 4) akan
mengurangi jumlah total kasus yang akan dipertimbangkan, tanpa mempengaruhi hasilnya. Ini
adalah dasar dari berbagai heuristik "pemilihan urutan elemen" yang akan dibahas di bawah ini.
Perlu ditunjukkan bahwa untuk masalah khusus ini (dan masalah N ratu yang lebih umum),
heuristik tidak memberikan banyak manfaat. Hal ini dikarenakan:

7
 1. Ukuran total pohon pencarian hanya bertambah sekitar 2 atau 3 kali lipat ketika urutan elemen
acak dipilih daripada urutan optimal (sehingga pengurangan besar dalam jumlah percobaan
tidak mungkin dilakukan);
2. Dengan menggunakan metode Wirth (1971), solusi percobaan dapat diuji dengan sangat
efisien (sehingga tidak banyak yang dapat diperoleh dari pengurangan jumlah percobaan);
3. Solusi "naïf" dengan menempatkan ratu dari kiri ke kanan ternyata merupakan urutan yang
optimal (jika urutan elemen tetap selama perhitungan).
Untuk masalah yang ingin kami selesaikan, urutan elemen yang sesuai sangat penting dalam
menghasilkan hasil dalam waktu yang layak. Bahkan u n t u k masalah ini, dengan memulai dengan
permutasi acak setiap kali, kami dapat menghasilkan beberapa perbaikan dengan menggunakan
heuristik yang dibahas di Bagian 7. Lihat Gambar 1 untuk beberapa contoh hasil, yang masing-
masing dirata-ratakan dari sepuluh permutasi awal acak yang berbeda. Metode "pra-analisis"
menganalisis pohon pencarian untuk memilih permutasi awal. Metode "pemangkasan semak" secara
dinamis memperbarui permutasi saat pencarian berlangsung. Metode "hybrid" adalah kombinasi dari
sejumlah kecil pra-analisis, diikuti dengan pemangkasan semak. Metode ini adalah yang paling
efisien dalam hal jumlah uji coba, tetapi membebankan biaya yang lebih tinggi daripada pra-analisis
sederhana-yang merupakan yang paling efisien dalam hal waktu CPU.

Jumlah uji coba Waktu CPU

Metode yang 13 ratu 14 ratu 13 ratu 14 ratu
digunakan
tidak ada 130,150,618 899,139,237 138.43 942.14
pra-analisis 100,515,902 654,151,660 110.61 696.29
hibrida 89,088,384 569,929,575 140.00 878.52

Tabel 1: Hasil sampel dari masalah N ratu

3 Bahasa WSL
Pada bagian ini kami memberikan pengantar singkat tentang bahasa WSL (Bull (1990), Ward
(1989), Ward (1994)) "Bahasa Spektrum Luas", yang digunakan dalam pekerjaan transformasi
program Ward, yang mencakup konstruksi pemrograman tingkat rendah dan spesifikasi abstrak
tingkat tinggi dalam satu bahasa. Dengan bekerja dalam satu bahasa formal, kita dapat membuktikan
bahwa sebuah program mengimplementasikan spesifikasi dengan benar, atau bahwa sebuah
spesifikasi dengan benar menangkap perilaku sebuah program, dengan menggunakan
transformasi formal dalam bahasa tersebut. Kita tidak perlu mengembangkan transformasi
antara bahasa "pemrograman" dan "spesifikasi". Keuntungan tambahannya adalah bahwa bagian
program yang berbeda dapat diekspresikan pada tingkat abstraksi yang berbeda, jika diperlukan.
Transformasi program adalah operasi yang memodifikasi sebuah program ke dalam bentuk yang
berbeda yang memiliki perilaku eksternal yang sama (ekuivalen di bawah semantik denotasi yang
didefinisikan secara tepat). Karena program dan spesifikasi adalah bagian dari bahasa yang
sama, transformasi dapat digunakan untuk menunjukkan bahwa program yang diberikan adalah
implementasi yang benar dari spesifikasi yang diberikan. Dalam Ward (1990), Ward (1996)
transformasi program digunakan untuk mendapatkan berbagai algoritma yang efisien dari
spesifikasi abstrak. Dalam makalah ini kami menggunakan transformasi untuk menurunkan
berbagai algoritma backtracking yang efisien dari sebuah spesifikasi formal.

3.1 Sintaks Ekspresi

Ekspresi mencakup nama variabel, angka, string dengan bentuk "text...", konstanta N, R, Q, Z,
serta operator dan fungsi berikut. Perhatikan bahwa karena WSL adalah bahasa spektrum yang luas,
maka tidak boleh dibatasi pada nilai yang terbatas dan operasi yang dapat dihitung. Berikut ini e1 , e2
8
, dsb., merepresentasikan ekspresi yang valid:
Operator numerik: e1 + e2 , e1 - e2 , e1 ∗ e2 , e /e121 , ee2 dan seterusnya, dengan arti yang
biasa.

9
2. Barisan: s = ⟨a1 , a2 , . . . an ⟩ adalah sebuah barisan, elemen ke-i ai dinotasikan s[i], s[i . . j]
adalah barisan ⟨s[i], s[i + 1], . . . s[j]⟩, di mana s[i . . j] = ⟨⟩ (barisan kosong) jika i > j.
Panjang barisan s dinotasikan l(s), sehingga s[l(s)] adalah elemen terakhir dari s.
Penggabungan urutan: s1 ++ s2 = ⟨s1 [1], . . , s1 [l(s1 )], s2 [1], . . , s2 [l(s2 )]].
Tumpukan: Urutan juga digunakan untuk mengimplementasikan tumpukan, untuk tujuan ini kami
memiliki yang berikut ini
pop
notasi: Untuk sebuah urutan s dan variabel x: x←- s berarti x := s[1]; s := s[2 . . l(s)]
yang
mengeluarkan sebuah elemen dari tumpukan ke dalam variabel x. Untuk mendorong nilai
push
ekspresi e ke tumpukan s kita menggunakan: s←- e yang merepresentasikan: s := ⟨e⟩ + +
s.
last
Antrian: Pernyataan x←- s menghapus elemen terakhir dari s dan menyimpan nilainya di
dalam variabel
x. Ini setara dengan x := s[l(s)]; s := s[1 . . l(s) - 1].
Himpunan: Kita memiliki operasi himpunan biasa ∪ (gabungan), ∩ (perpotongan) dan z (selisih
himpunan), ⊆
(himpunan bagian), ∈ (elemen), ℘ (himpunan kuasa). { x ∈ A | P (x) } adalah himpunan
semua elemen di A yang
memenuhi predikat P . Untuk barisan s, himpunan (s) adalah himpunan elemen-elemen dari
barisan tersebut, yaitu
himpunan (s) = { s[i] | 1 ≤ i ≤ l(s) }. Ekspresi #A menunjukkan ukuran himpunan A.

3.2 Sintaks Formula

Dalam Q berikut ini, Q1 , Q2 , dll., mewakili rumus sembarang dan e1 , e2 , dll., ekspresi
sembarang:
Relasi: e1 = e2 , e1 /= e2 , e1 < e2 , e1 ≤ e2 , e1 > e2 , e1 ≥ e ;2
Operator logika: ¬Q, Q1 ∨ Q2 , Q1 ∧ Q2 ;
Pengukur: ∀v. Q, ∃v. Q.

3.3 Sintaks Laporan

Berikut ini, S1 , S2 dll., adalah pernyataan, Q, B dll., adalah rumus, x1 , x2 dll., adalah variabel dan
e1 , e2 dll. adalah ekspresi.
Komposisi berurutan: S1 ; S2 ; S3 ; . . . ; Sn
Penegasan: {B}. Pernyataan adalah pernyataan lompatan parsial, pernyataan ini akan batal jika
kondisinya salah, tetapi tidak melakukan apa pun jika kondisinya benar.
2. Penugasan: ⟨x1 , . . . . xn ⟩ := ⟨x' , . . . . x' ⟩.Q. Ini memberikan nilai baru pada variabel x1 , . . . ,
x .n
1 n
Dalam rumus Q, xi mewakili nilai lama dan x' mewakili
i nilai baru. Nilai-nilai baru dipilih
sehingga Q akan bernilai benar, kemudian nilai-nilai tersebut ditetapkan ke variabel. Jika
ada beberapa himpunan nilai yang memenuhi Q, maka satu himpunan dipilih secara
nondeterministik. Jika tidak ada nilai yang memenuhi Q maka pernyataan tidak diakhiri.
Sebagai contoh, penugasan
⟨x⟩ := ⟨x' ⟩.(x = 2.x' ) membagi dua x jika genap dan membatalkannya jika x ganjil. Jika
barisan berisi satu variabel maka tanda kurung kurawal bisa dihilangkan, contohnya: x :=
x' .(x = 2.x' ). Penugasan x := x' .(y = 0) memberikan sebuah nilai sembarang pada x jika y
= 0 pada awalnya, dan batal jika y = 0 pada awalnya: ini tidak mengubah nilai y.
2. Penugasan sederhana: ⟨x1 , . . . , xn ⟩ := ⟨e1 , . . . , en ⟩. Ini memberikan nilai dari ekspresi ei ke
variabel xi . Penugasan dilakukan secara bersamaan, jadi misalnya ⟨x, y⟩ :=

10
 ⟨y, x⟩ menukar nilai x dan y. Penugasan tunggal ⟨x⟩ := ⟨e⟩ dapat disingkat menjadi
x := e.
Pilihan deterministik: jika B maka S1 else S2 fi. Pilihan pernyataan mana y a n g akan dieksekusi
ditentukan oleh kondisi B.
Pilihan nondeterministik: "Perintah yang dijaga" dari Dijkstra (1976):
jika B1 → S1
H B2 → S2
. ..
H Bn → Sn fi

11
 Setiap "penjaga" B1 , B2 , . . . Bn dievaluasi, salah satu yang benar dipilih dan pernyataan yang
sesuai dieksekusi. Jika tidak ada satupun yang benar maka pernyataan tersebut batal. Jika
beberapa penjaga bernilai benar, maka salah satu dari pernyataan-pernyataan yang sesuai
dipilih secara nondeterministik.
Iterasi deterministik: while B do S od Kondisi B diuji dan S dieksekusi secara berulang-
ulang sampai B menjadi salah.
Variabel lokal yang belum diinisialisasi: var x: S end Di sini x adalah variabel lokal yang hanya
ada di dalam pernyataan S. Variabel ini harus diinisialisasi di dalam S sebelum pertama
kali diakses.
Inisialisasi variabel lokal: var x := t: S end Ini adalah singkatan dari var x: x := t; S end.
Variabel lokal diinisialisasi ke nilai t. Kita dapat menggabungkan variabel yang
diinisialisasi dan yang tidak diinisialisasi dalam satu blok, misalnya: var x := t, y: S end di
mana x diinisialisasi dan y tidak diinisialisasi.
Iterasi yang dihitung: untuk i := b sampai f langkah s lakukan S od sama dengan:
var i := b :
sementara i ≤ f lakukan
S; i := i + s od akhir
Perulangan dan jalan keluar tak terbatas: Pernyataan-pernyataan dalam bentuk do S od, di mana
S adalah sebuah pernyataan, adalah perulangan "tak terbatas" atau "tak terbatas" yang hanya
bisa diakhiri dengan eksekusi pernyataan dalam bentuk exit(n) (di mana n adalah sebuah
bilangan bulat, bukan sebuah variabel atau ekspresi) yang menyebabkan program keluar
dari perulangan yang melingkupinya. Untuk menyederhanakan bahasa, kami tidak
memperbolehkan exit yang meninggalkan blok atau perulangan selain perulangan tak
terbatas. Jenis struktur ini dijelaskan dalam Knuth (1974) dan yang terbaru dalam Taylor
(1984).

3.4 Sistem Aksi

Subbagian ini akan memperkenalkan konsep sistem aksi sebagai sekumpulan prosedur rekursif tanpa
parameter. Sebuah program yang ditulis menggunakan label dan lompatan diterjemahkan secara
langsung ke dalam sistem aksi. Namun perlu diperhatikan bahwa jika akhir dari badan aksi tercapai,
maka kontrol dikembalikan ke aksi pemanggilan, atau ke pernyataan yang mengikuti sistem aksi jika
tidak ada aksi pemanggilan, daripada "jatuh" ke label berikutnya. Pengecualian d a r i hal ini adalah
sebuah aksi khusus yang disebut dengan aksi pengakhiran, biasanya dilambangkan dengan Z, yang
ketika dipanggil akan langsung mengakhiri seluruh sistem aksi.
Sebuah aksi adalah sebuah prosedur tanpa parameter yang bekerja pada variabel-variabel
global (lihat Arsac (1982a), Arsac (1982b)). Ditulis dalam bentuk A ≡ S. dimana A adalah
sebuah variabel pernyataan (nama aksi) dan S adalah sebuah pernyataan (badan aksi). Satu set
aksi-aksi (yang saling rekursif) disebut sebuah sistem aksi. Kadang-kadang ada aksi khusus Z,
yang eksekusinya menyebabkan penghentian seluruh sistem aksi meskipun ada pemanggilan rekursif
yang belum selesai. Sebuah kejadian dari pemanggilan pernyataan X di dalam badan aksi mengacu
pada pemanggilan aksi lain.
Sistem aksi ditulis sebagai berikut, dengan aksi pertama yang akan dieksekusi (A1 di bawah)
diberi nama di awal:
tindakan A1 :
A1 ≡ S .1
A2 ≡ S .2
. ..
An ≡ Sn . endactions
Sebagai contoh, sistem tindakan ini setara dengan perulangan while while B do S

12
od: tindakan A :
A ≡ jika ¬B maka panggil Z fi;
S; panggil A. tindakan akhir
Dengan sistem aksi ini, setiap pemanggilan aksi harus mengarah ke pemanggilan aksi lainnya,
sehingga sistem hanya dapat

13
mengakhiri dengan memanggil aksi Z (yang menyebabkan penghentian langsung). Sistem aksi
seperti itu disebut reguler.

3.5 Prosedur dan Fungsi dengan Parameter

Kami menggunakan notasi berikut untuk prosedur dengan parameter:
mulai S1 di
mana
proc F (x, y) ≡ S2 .
end
dimana S1 adalah sebuah program yang berisi pemanggilan ke prosedur F yang memiliki
parameter x dan y. Tubuh S2 dari prosedur tersebut dapat berisi pemanggilan prosedur rekursif.
Kita menggunakan notasi yang sama (dengan funct dan bukan proc) untuk pemanggilan fungsi.

4 Penyempurnaan dan Transformasi Program

Bahasa WSL mencakup konstruksi spesifikasi, seperti penugasan umum, dan konstruksi
pemrograman. Salah satu tujuan dari pekerjaan transformasi program kami adalah untuk
mengembangkan program dengan menyempurnakan spesifikasi, yang diekspresikan dalam logika
tingkat pertama dan teori himpunan, menjadi algoritme yang efisien. Hal ini mirip dengan
pendekatan "kalkulus penyempurnaan" dari Hoare dkk. (1987), Morgan (1994), namun, bahasa
spektrum kami yang luas telah diperluas untuk memasukkan sistem aksi umum dan perulangan
dengan banyak jalan keluar. Perluasan ini sangat penting untuk tujuan kedua kami yang sama
pentingnya, yaitu menggunakan transformasi program untuk rekayasa balik dari program ke
spesifikasi. Dalam Ward (1993) kami menjelaskan metode kami untuk rekayasa balik formal
menggunakan transformasi.
Refinement didefinisikan dalam hal semantik denotasi bahasa: semantik dari sebuah program S
adalah sebuah fungsi yang memetakan dari sebuah keadaan awal ke sekumpulan keadaan akhir.
Himpunan keadaan akhir mewakili semua keadaan keluaran yang mungkin dari program untuk
keadaan masukan yang diberikan. D e n g a n menggunakan sekumpulan state memungkinkan kita
untuk memodelkan program nondeterministik dan spesifikasi yang terdefinisi sebagian (atau tidak
lengkap). Untuk program S1 dan S2 kita katakan S1 disempurnakan oleh S2 (atau S2 adalah
penyempurnaan dari S1 ), dan menulis S1 ≤ S2 , jika S2 lebih terdefinisi dan lebih deterministik
daripada S1 . Jika S1 ≤ S2 dan S2 ≤ S1 maka kita katakan S1 ekuivalen dengan S2 dan menulis S1 ≈
S2 . Ekuivalensi dengan demikian didefinisikan dalam hal perilaku "kotak hitam" eksternal program.
Sebuah transformasi adalah sebuah operasi yang memetakan program apapun yang memenuhi
kondisi-kondisi penerapan transformasi ke sebuah program yang ekuivalen. Lihat Ward (1989) dan
Ward (1991a) untuk deskripsi semantik dari WSL dan metode-metode yang digunakan untuk
membuktikan kebenaran dari perbaikan-perbaikan dan transformasi-transformasi.
Bagian selanjutnya dari bagian ini menjelaskan transformasi yang akan kita gunakan nanti dalam
derivasi algoritma backtracking.

4.1 Memperluas pernyataan IF

Pernyataan jika:
if B then S1 else S2 fi; S
dapat diperluas melalui pernyataan yang diberikan berikut ini:

if B then S1 ; S else S2 ; S fi

4.2 Perbaiki Penugasan

Jika Q' ⇒ Q dan ∃x. Q ⇒ ∃x. Q' maka kita dapat memperhalus penugasan x := x' .Q
14
menjadi x := x' .Q' . Sebagai contoh, jika ø /= I' ⊆ I maka x := x' .x' ∈ I ≤ x := x' .x'
∈ I .'

15
 4.3 Split Block
Jika pernyataan S2 memberikan nilai baru pada x sebelum mengaksesnya maka blok: var x : S1 ;
S2 end
dapat dipecah menjadi dua blok: var x : S1 end; var x : S2 end

4.4 Pembalikan Lingkaran

Jika pernyataan S1 tidak mengandung jalan keluar yang bisa menyebabkan penghentian dari
sebuah perulangan yang melingkupi (yaitu dalam notasi Ward (1989) ini adalah sebuah
barisan yang tepat) maka perulangan tersebut:

do S1 ; S2 od

dapat dibalik menjadi:

S1 ; do S2 ; S1 od
Transformasi ini dapat digunakan dalam arah maju untuk memindahkan uji penghentian
perulangan ke awal, sebelum mengubahnya menjadi perulangan sementara, atau dapat
digunakan dalam arah mundur untuk menggabungkan dua salinan pernyataan S .1

4.5 Membuka gulungan loop

Tiga transformasi berikutnya berkaitan dengan berbagai bentuk pembongkaran loop. Mereka
memainkan per an penting dalam pembuktian transformasi-transformasi lainnya dan juga berguna
secara umum.
Lemma 4.1 Loop Membuka Gulungan:

sedangkan B melakukan S od ≈ if B then S;

while B do S od fi Lemma 4.2 Pembatalan selektif dari perulangan selektif:

Untuk setiap kondisi Q yang kita miliki:

sedangkan B melakukan S od ≈ while B do S; jika B ∧

Q maka S fi od Lemma 4.3 Pembongkaran Seluruh Perulangan: jika B' ⇒ B

maka untuk sembarang kondisi Q:

sedangkan B melakukan S od ≈ while B do S; if Q then while B' do S od

fi od

Untuk setiap transformasi ini, ada generalisasi di mana, alih-alih menyisipkan bagian "tidak
digulung" setelah S, bagian tersebut disalin ke dalam pilihan sembarang posisi terminal di S.
Transformasi kebalikannya, secara alami, disebut loop rolling dan seluruh loop rolling.

4.6 Memperkenalkan Rekursi

Bagian ini memperkenalkan sebuah teorema penting tentang implementasi rekursif dari
pernyataan. Teorema ini menunjukkan bagaimana sebuah pernyataan umum dapat
ditransformasikan ke dalam sebuah pernyataan rekursif yang ekuivalen. Transformasi yang terlibat
dapat digunakan untuk mengimplementasikan spesifikasi rekursif sebagai prosedur rekursif, untuk
memperkenalkan rekursi ke dalam program abstrak untuk mendapatkan program yang "lebih
konkrit" (yaitu lebih dekat dengan implementasi bahasa pemrograman), dan untuk
mentransformasikan prosedur rekursif yang diberikan ke dalam bentuk yang berbeda. Teorema
ini digunakan dalam turunan algoritma dari Ward (1996) dan Ward (1989), kami akan
menggunakannya di bawah ini di Bagian 5.
16
 Misalkan kita memiliki sebuah pernyataan S' yang ingin kita ubah menjadi prosedur rekursif
proc F ≡ S. Hal ini mungkin terjadi kapanpun:
1. Pernyataan S' disempurnakan oleh S[S' /F ] (yang menyatakan S dengan semua kemunculan F
digantikan oleh S' ). Dengan kata lain, jika kita mengganti pemanggilan rekursif di S dengan
salinan dari S' maka kita mendapatkan perbaikan dari S ;'
2. Kita dapat menemukan sebuah ekspresi t (disebut fungsi varian) yang nilainya berkurang
sebelum setiap kemunculan S' dalam S[S' /F ].

17
Ekspresi t tidak perlu berupa bilangan bulat: semua himpunan Γ yang memiliki urutan yang
beralasan " cocok. Untuk membuktikan bahwa nilai t tereduksi, cukup dengan membuktikan
bahwa jika t " t0 pada awalnya, maka pernyataan {t ≺ t0 } dapat disisipkan sebelum setiap
kemunculan S' dalam S[S' /F ]. Teorema ini menggabungkan dua persyaratan ini menjadi satu
persyaratan:
Teorema 4.4 Jika " adalah sebuah order parsial yang beralasan pada suatu himpunan Γ dan t
adalah sebuah ekspresi yang memberikan nilai-nilai pada Γ dan t0 adalah sebuah variabel yang
tidak terdapat pada S maka jika untuk beberapa premis 𝑃

∀t0 . ((P ∧ t " t0 ) ⇒ S' ≤ S[{P ∧ t ≺ t0 }; S' /F ])

kemudian
P ⇒ (S' ≤ proc F ≡ S.)

Sering kali dimungkinkan untuk mendapatkan sebuah prosedur tubuh S yang sesuai dari
pernyataan S' dengan menerapkan transformasi pada S' , membaginya ke dalam kasus-kasus, dst.,
sampai kita mendapatkan pernyataan S[S' /F ] yang masih didefinisikan dalam hal S' . Jika kita dapat
menemukan sebuah fungsi varian yang sesuai untuk S[S' /F ] maka kita dapat mengaplikasikan
teorema tersebut dan menyempurnakan S[S' /F ] menjadi proc F ≡ S. yang tidak lagi didefinisikan
dalam hal S .'
Sebagai contoh, kita akan mempertimbangkan fungsi faktorial yang sudah dikenal. Misalkan
S' = r := n!. Kita dapat mengubahnya (dengan menggunakan definisi faktorial) untuk
mendapatkan:

S' ≈ if n = 0 then r := 1 else r := n.(n - 1)! fi

Pisahkan penugasan:
S' ≈ if n = 0 then r := 1 else n := n - 1; r := n!; n := n + 1; r := n.r fi
Jadi, kami sudah melakukannya:
S' ≈ if n = 0 then r := 1 else n := n - 1; S' ; n := n + 1; r := n.r fi

Bilangan bulat positif n diturunkan sebelum salinan S' , jadi jika kita menetapkan t menjadi
n, Γ menjadi N dan "
menjadi ≤ (urutan biasa pada bilangan asli), dan P benar maka kita dapat membuktikan:

n ≤ t0 ⇒ S' ≤ if n = 0 then r := 1 else n := n - 1; {n < t0 }; S' ; n := n + 1; r := n.r fi

Jadi kita bisa menerapkan Teorema 4.4 untuk mendapatkan:

S' ≤ proc X ≡ if n = 0 then r := 1 else n := n - 1; X; n := n + 1; r := n.r fi.

dan kita telah mendapatkan implementasi rekursif dari faktorial.

4.7 Mengubah Perulangan menjadi Iterasi

Transformasi penghapusan rekursi tujuan umum berikut ini disajikan dalam Ward (1992).
Buktinya dapat ditemukan di Ward (1991b).
Misalkan kita memiliki sebuah prosedur rekursif yang badannya adalah sebuah sistem aksi reguler
dalam bentuk berikut:
proc F (x) ≡
tindakan A1 :
A1 ≡ S .1
18
 . . . 2. Ai ≡ S .i
. . . Bj ≡ Sj0 ; F (gj1 (x)); Sj1 ; F (gj2 (x)); . . . ; F (gjnj (x)); S .jnj
. . . tindakan akhir.
2. dimana Sj1 , . . . , Sjnj mempertahankan nilai x dan tidak ada S yang berisi pemanggilan ke F
(yaitu semua pemanggilan ke F didaftarkan secara eksplisit di dalam aksi Bj ) dan pernyataan-
pernyataan Sj0 , Sj1 , . . dan Sjnj−1 tidak mengandung pemanggilan aksi.

19
2. Terdapat M + N aksi secara keseluruhan: A1 , . . . , AM , B1 , . . . , BN . Perhatikan bahwa
karena sistem aksi-aksi ini bersifat reguler, maka hanya dapat diakhiri dengan mengeksekusi
pemanggilan Z yang akan mengakhiri pemanggilan prosedur yang sedang berjalan.
Tujuannya adalah untuk menghapus rekursi dengan memperkenalkan tumpukan lokal L yang
mencatat operasi-operasi yang "ditunda": Ketika sebuah pemanggilan rekursif dibutuhkan, kita
"menunda" pemanggilan tersebut dengan mendorong pasangan ⟨0, e⟩ ke L (di mana e adalah
parameter yang dibutuhkan untuk pemanggilan rekursif). Eksekusi dari pernyataan-pernyataan
Sjk juga harus ditunda (karena mereka terjadi di antara pemanggilan rekursif), kita mencatat
penundaan Sjk dengan mendorong ⟨⟨j, k⟩, x⟩ ke L. Di mana badan prosedur biasanya diakhiri
(dengan memanggil Z), kita memanggil aksi baru Fˆ yang memunculkan item paling atas dari L
dan menjalankan operasi yang ditunda. Jika kita memanggil Fˆ dengan stack kosong maka
semua operasi yang ditunda telah selesai dan prosedur diakhiri dengan memanggil Z.
Teorema 4.5 Sebuah prosedur rekursif dalam bentuk:
proc F (x) ≡
tindakan A1 :
A1 ≡ S .1
. . . 2. Ai ≡ S .i
. . . Bj ≡ Sj0 ; F (gj1 (x)); Sj1 ; F (gj2 (x)); . . . ; F (gjnj (x)); S .jnj
. . . tindakan akhir.
2. dimana Sj1 , . . . Sjnj seperti di atas, ekuivalen dengan prosedur iteratif berikut ini yang
menggunakan tumpukan lokal baru L dan variabel lokal baru m:
proc F' (x) ≡
var L := ⟨⟩, m :
tindakan A1 :
A1 ≡ S1 [panggil Fˆ/panggil Z].
. . . Ai ≡ Si [panggil Fˆ/panggil Z].
. . . 2. Bj ≡ Sj0 ; L := ⟨⟨0, gj1 (x)⟩, ⟨⟨j, 1⟩, x⟩, ⟨0, gj2 (x)⟩, . . , ⟨0, gjnj (x)⟩, ⟨⟨j, nj ⟩, x⟩⟩ ++
L;
panggil F ˆ .
. . . Fˆ ≡ jika L = ⟨⟩ maka panggil Z
pop
else ⟨m, x⟩←- L;
jika m = 0 → panggil A1
H . . . H m = ⟨j, k⟩ → Sjk ; panggil Fˆ
. . fi fi. akhir tindakan akhir.
Perhatikan bahwa setiap prosedur F(x) dapat direstrukturisasi ke dalam bentuk yang
dibutuhkan; pada kenyataannya, mungkin ada beberapa cara yang berbeda untuk menyusun F(x)
yang memenuhi kriteria yang dibutuhkan.
Pertimbangkan program faktorial rekursif yang telah kita turunkan di atas (Bagian 4.6):
proc X ≡ if n = 0 then r := 1 else n := n - 1; X; n := n + 1; r := n.r fi.
Kita dapat merestrukturisasi ini sebagai:
proc X ≡
tindakan A :
A ≡ if n = 0 then r := 1; panggil Z else panggil B fi.
B ≡ n := n - 1; X; n := n + 1; r := n.r; panggil
Z. endactions.
Ini adalah bentuk yang tepat untuk menerapkan Teorema 4.5. Hal ini memberikan:
proc X ≡
var L := ⟨⟩, m :
tindakan A :
20
A ≡ jika n = 0 maka r := 1; panggil Fˆ else panggil B fi.

21
 B ≡ n := n - 1; L := ⟨0, 1⟩ ++ L; panggil F ˆ ; panggil F̂.
Fˆ ≡ jika L = ⟨⟩ maka panggil Z
pop
else ⟨m⟩←- L;
jika m = 0 → panggil A
H m = 1 → n := n + 1; r := n.r; panggil Fˆ fi fi.
akhir dari sebuah transaksi berakhir.
Perhatikan bahwa B mendorong 0 ke L, lalu memanggil Fˆ yang langsung mengeluarkan 0 dan
memanggil A. Jadi kita bisa memanggil A secara langsung:
proc X ≡
var L := ⟨⟩, m :
tindakan A :
A ≡ jika n = 0 maka r := 1; panggil Fˆ else panggil B fi.
B ≡ n := n - 1; L := ⟨1⟩ ++ L; panggil A.
Fˆ ≡ jika L = ⟨⟩ maka panggil Z
pop
else ⟨m⟩←- L;
jika m = 0 → panggil A
H m = 1 → n := n + 1; r := n.r; panggil Fˆ fi fi.
akhir dari sebuah transaksi berakhir.
Sekarang kita hanya akan memasukkan satu ke dalam L, yang perlu kita ketahui adalah panjangnya1 .
Jadi, ubahlah L menjadi sebuah variabel bilangan bulat dan hapuslah variabel lokal m yang
berlebihan:
proc X ≡
var L := 0 :
tindakan A :
A ≡ jika n = 0 maka r := 1; panggil Fˆ else panggil B fi.
B ≡ n := n - 1; L := L + 1; panggil A.
Fˆ ≡ jika L = 0 maka panggil Z
else L := L - 1; n := n + 1; r := n.r; panggil Fˆ fi.
akhir dari sebuah transaksi berakhir.
Sekarang aksi A dan B hanya menyalin n ke dalam L, mengatur r ke 1, mengatur n ke 0, dan
m e m a n g g i l F ˆ . Aksi Fˆ dapat dinyatakan sebagai perulangan sementara, jadi kita punya:
proc X ≡
var L := n :
r := 1; n := 0;
while L /= 0 do L := L - 1; n := n + 1; r := n.r od end.
Perhatikan bahwa L mencapai nol ketika n mencapai nilai aslinya, sehingga kita dapat menulis
perulangan while sebagai for
loop:
proc X ≡ r := 1; for i := 1 to n do r := i.r od.
Ini adalah algoritma faktorial yang efisien, yang diturunkan dari spesifikasi yang diberikan di Bagian
4.6

4.8 Iterasi Nondeterministik

Kami memperkenalkan notasi berikut untuk iterasi nondeterministik atas elemen-elemen himpunan
berhingga:

S var i, I' := I :
untuk i ∈ I lakukan DF
od = while I' /= ø do
i := i' .(i' ∈ I' ); I' := I' z {i}; S od end
22
 1Secara teknis, kita memperkenalkan sebuah variabel baru, katakanlah l, yang mencatat panjang L. Kemudian kita

mengganti referensi ke L dengan referensi yang sesuai dengan l (hal ini dimungkinkan karena kita hanya mengacu
pada panjang L). Kemudian L menjadi redundan dan dapat dihapus. Akhirnya kita mengganti nama l menjadi L

23
Ini mengambil elemen-elemen dari himpunan (terbatas) I dalam urutan sembarang dan
mengeksekusi S satu kali untuk setiap elemen.
Lemma 4.6 Jika I1 dan I2 partisi I (yaitu I = I1 ∪ I2 dan I1 ∩ I2 = ø) maka perulangan for
menyempurnakan pasangan perulangan tersebut:

untuk i ∈ I lakukan S od ≤ untuk i ∈ I1 do S od; untuk i ∈ I2 do S

od

Bukti: Pembuktiannya adalah dengan induksi pada ukuran himpunan (terbatas) I dengan
menggunakan transformasi 4.2, 4.3 dan 4.5.
Dengan induksi pada lemma ini, kita mendapatkan hasil yang lebih umum:
S
Lemma 4.7 Misalkan himpunan berhingga I dipartisi sebagai j∈J Ij dimana himpunan-
himpunan Ij saling lepas. Maka for di atas menyempurnakan perulangan bersarang ganda:

untuk i ∈ I lakukan S od ≤ untuk j ∈ J lakukan

untuk i ∈ Ij do S od od

Bukti: Dengan induksi pada ukuran J, menggunakan lemma sebelumnya.

5 Penelusuran Balik Sederhana: Penurunan Algoritma

Jenis algoritma yang kita bahas adalah algoritma yang ingin menghitung, atau memproses, himpunan
solusi dari suatu masalah. Solusi-solusi ini direpresentasikan sebagai urutan elemen-elemen dari
suatu domain D yang memenuhi dua sifat: "kelengkapan" dan "validitas". Kami menggunakan D∗
untuk menyatakan himpunan dari semua urutan terbatas elemen-elemen dari D. Setiap solusi akan
dibangun dengan memperluas solusi yang tidak lengkap tetapi valid secara berurutan hingga solusi
tersebut lengkap atau kami memiliki cara sederhana untuk menentukan bahwa tidak ada perluasan
yang valid. Spesifikasi kita dapat dinyatakan sebagai:
SPEC = for DF
p ∈ { x ∈ D∗ | V (x) ∧ C (x) } do proses(p) od
dimana proses adalah prosedur yang akan kita jalankan untuk setiap urutan p yang lengkap dan
valid. V (p) bernilai benar untuk setiap p yang valid dan C (p) bernilai benar untuk setiap p yang
lengkap.
Sebuah segmen awal dari sebuah barisan p' adalah sebuah barisan p sedemikian hingga ∃q ∈ D∗
. p' = p ++ q. Sebuah segmen awal yang tepat p dari p' adalah sebuah segmen awal sedemikian
hingga p /= p' . Untuk semua segmen awal yang tepat p dari p' , kita mengasumsikan bahwa:
• Nilai lengkap tidak dapat diperluas lebih lanjut, yaitu C(p) ⇒ (¬C(p' ) ∧ ¬V (p' )); dan
• Segmen awal yang tepat dari nilai yang valid juga valid, yaitu V (p' ) ⇒ V (p).
Karena kami tertarik dengan ekstensi dari solusi yang valid, kami memperluas spesifikasi untuk
memproses semua ekstensi yang valid dan lengkap dari urutan yang diberikan dalam urutan yang
sewenang-wenang:

SPEC(p) = DF
for q ∈ { x ∈ D∗ | p ± x ∧ V (x) ∧ C(x) } do proses(q) od

dimana p ± x =DF ∃p' ∈ D∗ . x = p ++ p .'

Penurunan algoritme dari spesifikasi ini mengikuti tiga tahap:
1. Memperkenalkan rekursi;
2. Mengubah rekursi menjadi iterasi;
3. Optimalisasi.

5.1 Memperkenalkan Rekursi

24
Langkah pertama adalah mengubah spesifikasi ke dalam bentuk yang cocok untuk diterjemahkan ke
prosedur rekursif menggunakan Teorema 4.4. Kita ingin mentransformasikan SPEC(p) ke dalam
sebuah pernyataan yang berisi salinan-salinan

25
dari SPEC(p) dimana nilai p "lebih kecil" menurut beberapa urutan yang beralasan. Pertama, kami
memperkenalkan sebuah pernyataan if untuk mengambil kasus-kasus khusus. Kita bisa
mengasumsikan bahwa SPEC(p) hanya dipanggil ketika V(p) benar karena p yang tidak valid tidak
bisa memiliki ekstensi-ekstensi yang valid. Kita tahu bahwa SPEC(p) ≈ proses(p) jika C(p) benar,
jadi kita memperkenalkan pernyataan if yang menguji C(P). Jika C(p) salah maka semua nilai yang
ingin kita proses harus benar-benar lebih besar dari p, jadi kita punya:
SPEC(p) ≈ jika C(p) maka proses(p)
else for q ∈ { p ++ q | q ∈ D∗ ∧ V (p ++ q) ∧ C (p ++ q) } do proses(q) od
di mana kita tahu bahwa setiap elemen dari himpunan yang kita ulangi akan lebih panjang dari p. Jadi
kita dapat menulis himpunan ini sebagai gabungan dari himpunan bagian yang terpisah:
[
{ p ++ ⟨t⟩ ++ q ∈ D∗ | V (p ++ ⟨t⟩ ++ q) ∧ C (p ++ ⟨t⟩ ++ q) } .
t∈D

Ini berarti kita dapat memperbaiki loop menjadi loop ganda (dengan Lemma 4.7):
SPEC (p) ≤
if C(p) then proses(p)
else for t ∈ D do
for q ∈ { p + q ∈ D∗ | V (p +
+⟨t⟩ +
+ +⟨t⟩ +
q) ∧ C (p +
+ +⟨t⟩ ++ q) } do
proses (q) od
Jika ¬V (p ++ ⟨t⟩) maka { p ++ ⟨t⟩ ++ q ∈ D∗ | V (p ++ ⟨t⟩ ++ q) ∧ C (p ++ ⟨t⟩ ++ q) } =
ø dan untuk
perulangan untuk dilewati:
SPEC (p) ≤
if C(p) then proses(p)
else for t ∈ D do
jika V (p ++ ⟨t⟩)
then for q ∈ { p ++ ⟨t⟩ ++ q ∈ D∗ | V (p ++ ⟨t⟩ ++ q) ∧ C (p ++ ⟨t⟩ ++ q)
} do
proses (q) od
Jadi, kami sudah melakukannya:
SPEC(p) ≤ if C(p) then proses(p)
else for t ∈ D do
if V (p ++ ⟨t⟩) then SPEC(p ++ ⟨t⟩) fi od
Kita tahu bahwa himpunan { p ++ q | q ∈ D∗ ∧ V (p ++ q) ∧ C (p ++ q) } terbatas, sehingga ada
batas atas untuk panjang urutan yang valid, katakanlah L. Jadi kita bisa menggunakan L - l(p)
sebagai fungsi varian dan mengenalkan rekursi dengan menggunakan Teorema 4.4:
SPEC(p) ≤ proc processall(p) ≡
if C(p) then proses(p)
else for t ∈ D do
if V (p ++ ⟨t⟩) then processall(p ++ ⟨t⟩) fi od.
Kita telah mengganti nama prosedur rekursif F , yang disediakan oleh Teorema 4.4, untuk memproses
semua dan membuat p
parameter dari prosedur ini.

5.2 Penghapusan Rekursi

Setelah memperkenalkan rekursi, langkah selanjutnya adalah mentransformasikan prosedur
rekursif ke sebuah prosedur iteratif yang ekuivalen, dengan menggunakan Teorema 4.5.
Pertama, perhatikan bahwa kita dapat mengganti parameter p dengan sebuah variabel global
karena kita dapat mengembalikan nilainya dan nilai t setelah pemanggilan rekursif dengan
26
 last
melakukan t←- p. Nilai dari t
Perulangan nondeterministik for memperkenalkan variabel lokal lain D' (dan juga t) yang mencatat
elemen-elemen yang tersisa dari D yang belum diproses. Jika kita mengasumsikan (tanpa kehilangan
keumuman) bahwa D adalah himpunan bilangan bulat dari 1 sampai D (ukuran D), yaitu D = { i ∈
N | 1 ≤ i ≤ D }, maka kita bisa memperbaiki perulangan for nondeterministik menjadi perulangan
deterministik yang memproses elemen-elemen dari

27
 D secara berurutan. Hal ini dikarenakan nilai t memberitahu kita elemen-elemen D mana saja yang
belum diproses, pada kenyataannya D' = { i ∈ N | t < i ≤ D }:
SPESIFIKASI ≤
var p := ⟨⟩ :
proses semua akhir
di mana
proc processall ≡ semua proses
if C(p) then proses(p)
else t := 1;
sementara t ≤ D lakukan
last
if V (p ++ ⟨t⟩) then p := p ++ ⟨t⟩; processall; t←- p fi;
t := t + 1 od.
Prosedur memproses semua ekstensi yang valid dari (variabel global) p dalam urutan tertentu.
Spesifikasi kita adalah "tidak lengkap" dalam arti bahwa spesifikasi tidak menentukan urutan
dimana elemen-elemen yang valid dan lengkap akan diproses. Sebuah implementasi dari
spesifikasi dengan demikian bebas untuk memilih urutan yang paling nyaman.
Restrukturisasi badan prosedur sebagai sistem tindakan:
proc processall ≡ semua proses
tindakan A :
A ≡ if C(p) then proses(p); panggil Z
else t := 1; panggil A1 fi.
A1 ≡ jika t ≤ D maka jika V (p ++ ⟨t⟩) maka panggil B1
Jika tidak, hubungi A2 fi
Jika tidak, panggil Z fi.
A2 ≡ t := t + 1; panggil A .1 terakhir
B1 ≡ p := p + +⟨t⟩; processall; t ←- p; panggil A2 . endactions.
Ini sekarang berada dalam bentuk yang tepat untuk menerapkan transformasi penghapusan
rekursi (Teorema 4.5). Ada satu aksi "tipe-B" (B1 ) yang berisi satu pemanggilan rekursif. Jadi
S10 = p las
:=
t
p ++ ⟨t⟩ dan
S11 = t←- p; panggil A . Menghapus rekursi yang kita dapatkan:
2
proc processall ≡ semua proses
var L := ⟨⟩, m :
tindakan A :
A ≡ jika C(p) maka proses(p); panggil Fˆ
else t := 1; panggil A1 fi.
A1 ≡ jika t ≤ D maka jika V (p ++ ⟨t⟩) maka panggil
B1
Jika tidak, hubungi A2 fi
jika tidak, panggil Fˆ fi.
A2 ≡ t := t + 1; panggil A .1
B1 ≡ p := p ++ ⟨t⟩; L := ⟨0, ⟨1, 1⟩⟩ ++ L; panggil F ˆ ; panggil F̂.
Fˆ ≡ jika L = ⟨⟩ maka panggil Z
pop
else m←- L;
jika m = 0 → panggil A
tera
H m = ⟨1, 1⟩ → tkhi
r
← - p; panggil A2 fi fi. endactions end.

5.3 Optimalisasi
Seperti algoritma faktorial (Bagian 4.7), kita mendorong 0 ke L dan langsung memunculkannya dan
memanggil A. Jadi kita bisa menghindari dorongan dan memanggil A secara langsung. Seperti
sebelumnya, kita sekarang memiliki sebuah larik berisi elemen-elemen identik yang dapat
28
diimplementasikan sebagai sebuah bilangan bulat. Tetapi dalam kasus ini, kita bisa melakukan lebih
baik lagi, karena panjang L adalah sama dengan panjang p, jadi kita bisa menguji p dan bukan L dan
menghapus L secara keseluruhan:

29
 proc processall ≡ semua proses
tindakan A :
A ≡ jika C(p) maka proses(p); panggil Fˆ
else t := 1; panggil A1 fi.
A1 ≡ jika t ≤ D maka jika V (p ++ ⟨t⟩) maka panggil B1
Jika tidak, hubungi A2 fi
jika tidak, panggil Fˆ fi.
A2 ≡ t := t + 1; panggil
A1 . B1 ≡ p := p ++ ⟨t⟩;
panggil A.
Fˆ ≡ jika p = ⟨⟩ maka panggil Z
last
else t←- p; panggil A fi. endactions.
2

Hapus sistem tindakan dan restrukturisasi:

SPEC ≈
var p := ⟨⟩, t :
do if C(p) then proses(p);
if p = ⟨⟩ then keluar dari fi;
tera
t ←-
khi p; t := t + 1
r
else t := 1 fi;
+⟨t⟩) ∧ t ≤ D then exit
do if V (p +
elsif p = ⟨⟩ ∧ t > D then exit(2)
last
jika t > D maka t←- p; t := t + 1
else t := t + 1 fi od;
p := p ++ ⟨t⟩ od end
Keluarkan pernyataan pertama dari perulangan dan ubah menjadi perulangan tunggal. Kita akan
mengasumsikan C(⟨⟩)
adalah salah (karena jika tidak, tidak ada urutan lain yang bisa valid) dan mendefinisikan
DF
C' (t, p)
= C(p ++ ⟨t⟩),
' '
V (t, p) = DF V (p ++ ⟨t⟩), proses (t, p) =DF proses (p ++ ⟨t⟩).
var p := ⟨⟩, t := 1 :
lakukan jika V' (t, p) ∧ t ≤ D maka p := p + +⟨t⟩;
last
if C(p) then proses(p); t←- p; t := t + 1
else t := 1 fi;
elsif p = ⟨⟩ ∧ t > D maka keluar
last
jika t > D maka t←- p; t := t + 1
else t := t + 1 fi od end
Dorong pernyataan p := p ++ ⟨t⟩ ke dalam pernyataan if bagian dalam:
var p := ⟨⟩, t := 1 :
do if V' (t, p) ∧ t ≤ D then if C' (t, p) then proses' (t, p); t := t + 1
else p := p ++ ⟨t⟩; t := 1 fi;
elsif p = ⟨⟩ ∧ t > D maka keluar
last
jika t > D maka t←- p; t := t + 1
else t := t + 1 fi od end
Terakhir, atur ulang pengujian untuk membuat perulangan sementara:
var p := ⟨⟩, t := 1 :
while p /= ⟨⟩ ∨ t ≤ D do
last
jika t > D maka t←- p; t := t + 1
elsif V' (t, p) then if C' (t, p) then proses' (t, p); t := t + 1
else p := p ++ ⟨t⟩; t := 1 fi
30
else t := t + 1 fi od end

31
 Ini adalah algoritma backtracking dasar kami. Penurunannya hanya menggunakan
transformasi yang telah terbukti mempertahankan semantik (Ward (1989), Ward (1991a), Ward
(1992), Ward (1994)) sehingga kami dapat menjamin bahwa algoritme ini
mengimplementasikan spesifikasi SPEC dengan benar.

6 Beberapa Aplikasi
Bagian ini menguraikan masalah-masalah yang memunculkan algoritma-algoritma yang
disajikan dalam makalah ini. Masalah-masalah ini menyangkut representasi konkrit, dengan
fungsi atau dengan himpunan, dari struktur aljabar. Dualitas batu untuk aljabar Boolean
menyediakan sebuah prototipe untuk representasi tersebut. Kami akan menguraikan latar
belakang matematisnya secara singkat, tetapi memulai dengan menjelaskan bentuk algoritma
backtracking yang kita butuhkan.

6.1 Peta yang menjaga hubungan

Kita diberikan dua struktur relasi berhingga dengan tipe yang sama. Yaitu, kita memiliki dua
himpunan berhingga X dan Y dan dua himpunan berhingga relasi RX pada X dan RY pada Y sehingga
untuk setiap relasi ρ di RX ada relasi yang sesuai ρ' di RY dengan arity yang sama, dan sebaliknya.
Untuk kesederhanaan dalam sub-bagian ini, kita akan mengasumsikan bahwa semua relasi-relasi
adalah biner. Tujuannya adalah untuk menemukan semua peta-peta Ψ: X → Y yang mempertahankan
semua relasi, yaitu untuk semua relasi ρ ∈ RX , semua pasangan elemen-elemen di X yang
berhubungan dengan ρ, dipetakan ke elemen-elemen di Y yang berhubungan dengan ρ' . Secara lebih
formal:
Definisi 6.1 Sebuah fungsi Ψ : X → Y adalah relasi yang melestarikan iff:

∀ρ ∈ RX . ∀x, y ∈ X. (x ρ y) ⇒ (Ψ(x) ρ' Ψ(y))

Oleh karena itu, kami ingin menemukan ukuran himpunan:

© }
Ψ : X → Y | ∀ρ ∈ RX . ∀x, y ∈ X. (x ρ y) ⇒ (Ψ(x) ρ' Ψ(y))

Tanpa kehilangan keumuman, kita dapat menganggap X dan Y sebagai himpunan bilangan
bulat: X = {1, 2, . . . , #X} dan Y = {1, 2, . . . , #Y }. Kita bisa merepresentasikan sebuah
peta parsial Ψ : {1, 2, . . . . n} → Y (di mana n ≤ #X) sebagai sebuah barisan p dengan
panjang n di mana p[i] = Ψ(i). Sebuah barisan yang lengkap adalah barisan dengan panjang
#X dan sebuah barisan yang valid adalah barisan yang menjaga relasi. Jadi kita memiliki
definisi-definisi:
C(p) = DF l(p) = #X
V (p) = DF ∀ρ ∈ RX . ∀x, y, 1 ≤ x, y ≤ l(p). (x ρ y) ⇒ (p[x] ρ' p[y]))

Setiap subset dari sebuah peta pelestarian relasi (parsial atau total) juga merupakan pelestarian relasi,
sehingga definisi-definisi ini jelas memenuhi kondisi-kondisi untuk algoritma pelacakan balik.
Algoritma iteratif sebenarnya menggunakan V' (t, p) (didefinisikan sebagai V' (t, p) = V (p
++ ⟨t⟩) yang hanya dievaluasi ketika V (p) benar. Ini berarti bahwa kita hanya perlu memeriksa
pasangan (x, y) di mana salah satu atau kedua dari x atau y sama dengan t. Jadi kita dapat
menggunakan definisi tersebut:

V' (t, p) = ∀ ' ' '

DFρ ∈ RX . ∀x, 1 ≤ x < n. (n ρ x ⇒ t ρ p[x]) ∧ (x ρ n ⇒ p[x] ρ t) ∧ (n ρ n ⇒ t ρ t)

C' (t, p) =DFn = #X

di mana n = l(p) + 1 (jadi V' (t, p) menguji apakah t adalah gambar yang valid untuk n dalam
perluasan p dari
32
{1, 2, . . . , n - 1} menjadi {1, 2, . . . , n}).
Untuk implementasinya, kita hanya perlu mencatat ukuran X dan Y (dalam variabel SX dan
SY). Kita merepresentasikan dua set relasi dengan menggunakan dua larik bilangan bulat tiga
dimensi RX dan RY (kita dapat menggunakan larik boolean tetapi larik bilangan bulat mungkin
sedikit lebih cepat diakses dan memori tidak terlalu besar). Bilangan bulat rho
merepresentasikan relasi ρ di mana:
( (
1 if x ρ y '
RX [rho, x, y] dan RY [rho, x, y] = 1 jika x ρ y
= 0 jika tidak 0 jika tidak

33
Tes pengawetan relasi diimplementasikan sebagai perulangan sementara bersarang ganda yang
menyimpan hasilnya dalam variabel Boolean rp. Perulangan berakhir segera setelah rp menjadi
salah, untuk menghindari pengujian yang tidak perlu. Variabel R mencatat jumlah relasi. Jadi kita
memiliki prosedur pengujian berikut ini yang menetapkan rp menjadi benar jika V' (t, p) benar,
dengan syarat n = l(p) + 1 dan V (p) benar:
proc DO(t, p, n) ≡
var np := 0 :
rp := true; rho := 1;
while rho ≤ R ∧ rp do
jika RX [rho, n, n] = 1 ∧ RY [rho, t, t] = 0
then rp := false
else np := 1;
while np < n ∧ rp do
if (RX [rho, n, np] = 1 ∧ RY [rho, t, p[np]] = 0)
∨ (RX [rho, np, n] = 1 ∧ RY [rho, p[np], t] = 0)
then rp := false fi od fi od end.
Perhatikan bahwa versi ini akan berulang kali mencari himpunan elemen yang berhubungan
dengan elemen tertentu dalam X untuk setiap relasi. Jika relasi-relasi X cukup jarang (tidak
banyak pasangan elemen yang berhubungan) maka akan lebih efisien untuk merepresentasikan
relasi-relasi X dengan menggunakan dua larik bilangan bulat rel ke X dan rel X ke yang
mencatat informasi berikut:

rel untuk X[rho, n, 0] = jumlah elemen x sedemikian sehingga n ρ x

rel untuk X[rho, n, i] = elemen ke-i xi sedemikian sehingga n ρ xi
rel X to[rho, n, 0] = jumlah elemen x sedemikian sehingga x ρ n
rel X to[rho, n, i] = elemen ke-i xi sedemikian sehingga xi ρ n

Maka versi DO kami yang telah disempurnakan adalah DO:

proc DO(p, t, n) ≡
var np := 0, numrels := 0, i := 0 :
rp := true; rho := 1;
while rho ≤ R ∧ rp do
numrels := rel to X[rho, n, 0];
i := 1;
while i ≤ numrels ∧ rp do
np := rel ke X[rho, n, i];
if np < n then if RY [rho, t, p[np]] = 0 then rp := false fi
elsif np = n then if RY [rho, t, t] = 0 then rp := false fi
fi; i := i + 1 od;
jika rp
then numrels := rel X to[rho, n, 0];
i := 1;
while i ≤ numrels ∧ rp do
np := rel X to[rho, n, i];
if np < n ∧ RY [rho, p[np], t] = 0 then rp := false fi;
i := i + 1 od fi od akhir.

6.2 Masalah dalam Teori Dualitas

Misalkan kita diberikan sebuah kelas A dari aljabar-aljabar dengan tipe yang tetap. Asumsikan lebih
lanjut bahwa A dihasilkan dari aljabar terbatas P yang diberikan dengan membentuk produk,
subaljabar, dan salinan isomorfis: dalam simbol, A = ISD (P). Struktur seperti itu sering muncul

34
sebagai model aljabar untuk logika klasik dan non-klasik, misalnya. Dalam situasi ini, P berperan
sebagai "aljabar nilai kebenaran". Sebagai contoh:

35
 1. Ambil P sebagai kisi distributif 2-elemen 2 = ({0, 1}; ∨, ∧, 0, 1) (sehingga 0 dan 1
diperlakukan sebagai operasi nullary). Kemudian A adalah kelas D dari kisi-kisi distributif {0,
1}.
2. Ambil P sebagai aljabar Boolean 2 elemen ({0, 1}; ∨, ∧,' , 0, 1). Maka A adalah kelas B dari
aljabar Boolean.
3. Dengan mengambil P sebagai ({0, a, 1}; ∨, ∧, ∼, 0, 1), di mana ({0, a, 1}; ∨, ∧, 0, 1) adalah
kisi {0, 1}-distributif dengan 0 < a < 1 dan operator negasi ∼ memenuhi ∼0 = 1, ∼1 = 0
dan ∼a = a, kita mendapatkan kelas K dari aljabar Kleene.
Dalam contoh-contoh ini dan contoh-contoh berbasis logika lainnya, P memiliki struktur kisi
yang mendasarinya, dengan operasi ∨ dan ∧ yang memodelkan disjungsi dan konjungsi.
Selanjutnya kita akan selalu mengasumsikan bahwa P memiliki sebuah reduksi kisi, karena ini
menyederhanakan teori yang menjadi dasar kita (meskipun kita mencatat bahwa ada pekerjaan
menarik yang menanti di kelas-kelas aljabar di mana batasan ini tidak terpenuhi). Dalam banyak
kasus, A = ISD(P ) bertepatan dengan ragam HSD(P ), dimana H menyatakan pembentukan
gambar homomorfik. Kemudian, dengan teorema terkenal dari G. Birkhoff, A dapat ditentukan
oleh sekumpulan identitas. Hal ini terjadi untuk setiap D, B dan K di atas. (Di mana quasivariasi
ISD (P) secara ketat lebih kecil dari variasi HSD (P), semuanya tidak hilang. Akan tetapi, sebuah teori
representasi yang lebih rumit, dengan menggunakan struktur multi-sortir, akan dibutuhkan (lihat
Davey & Priestley (1987)).
Diberikan A = ISD(P ), kita dapat mencari representasi konkrit untuk aljabar-aljabar dalam
A . Pertanyaan penting lainnya yang harus dijawab adalah penentuan aljabar bebas F A (n)
pada n generator (perhatikan bahwa aljabar-aljabar bebas di HSD (P ) selalu berada di ISD (P ),
sehingga untuk masalah ini, kita cukup mempertimbangkan kelas-kelas dengan bentuk yang
terakhir). Sebuah studi sistematis yang besar mengenai representasi aljabar, dengan cara yang
merepresentasikan aljabar bebas dengan cara yang sangat alami, dilakukan oleh B.A. Davey dan H.
Werner dalam Davey & Werner (1983). Teori mereka mencakup banyak dualitas yang terkenal
(termasuk dualitas Stone untuk B dan dualitas Priestley untuk D) dalam sebuah kerangka kerja
yang umum. Dalam makalah ini, struktur-struktur terbataslah yang menjadi perhatian kita. Oleh
karena itu, kita akan membatasi pada aljabar berhingga di A . Hal ini menghindarkan kita dari
keharusan untuk memperkenalkan mesin-mesin topologi yang terlibat dalam merepresentasikan aljabar
~
sembarang. Representasi yang kita perlukan bergantung pada pilihan yang tepat dari sebuah
struktur relasional P = (P; R) pada himpunan P yang mendasari P . Diberikan sebuah himpunan
R dari relasi-relasi pada P yang kita perluas
setiap ρ ∈ R mengarah ke pangkat dari P . Untuk setiap A yang terbatas ∈ A mendefinisikan dual
dari A sebagai D(A), dimana
D(A) adalah himpunan A (A, P ) dari A -homomorfisma dari A ke P , dengan struktur relasional yang
diwarisi
dari P A . Kemudian, dari X = D(A) kita membentuk aljabar E(X), yang didefinisikan sebagai
himpunan peta-peta yang melestarikan R∼dari X ke P , dengan struktur aljabar yang diwarisi
dari PX . Kemudian teori dalam Davey & Werner (1983) (khususnya Teorema 1.18)
mengimplikasikan bahwa kita memiliki teorema berikut.
Teorema 6.2 Asumsikan bahwa A = ISD(P ) adalah sebuah kelas aljabar sedemikian hingga P
adalah sebuah aljabar berhingga dengan sebuah struktur kisi yang mendasarinya. Maka adalah
mungkin untuk memilih R sehingga
1. A ∼= ED(A) untuk setiap A berhingga ∈ A , dan
2. D(F A (n)) = P n (sehingga F A (n) adalah aljabar dari semua peta-peta yang
melestarikan R dari Pn ke P
∼ ∼ ∼
( 1 ≤ n < ∞)).
Selanjutnya, R di atas dapat dipilih untuk terdiri dari relasi-relasi biner, yang masing-masing
merupakan subaljabar dari P .2

36
 Jika (1) pada Teorema 6.2 berlaku, kita mengatakan bahwa R menghasilkan dualitas pada
(aljabar berhingga pada) A. Untuk aljabar Boolean, kita mengambil R = ø, sementara untuk D
kita mendapatkan dualitas Priestley dengan memilih R pada {0, 1} yang mengandung relasi
tunggal ≤, relasi ketidaksamaan di mana 0 < 1 (jadi 2 adalah rantai 2 elemen,
~
qua himpunan terurut). Dalam contoh-contoh ini, diakui dengan melihat ke belakang, dualitas
sebuah himpunan yang cocok R
telah dikenal sebelum teori Davey-Werner dikembangkan. Sejak publikasi Davey & Werner (1983),
berbagai teknik (terutama metode piggyback Davey dan Werner) telah dirancang untuk
mempermudah mengidentifikasi sebuah himpunan R yang akan menghasilkan dualitas pada A .
Akan tetapi, himpunan seperti i t u seringkali terlalu besar dan kompleks untuk menghasilkan
dualitas yang dapat diterapkan. Hal ini diilustrasikan dengan jelas oleh subvarietas dari varietas Bω
dari aljabar p distributif. Variasi-variasi ini pertama kali didiskusikan oleh
K.B. Lee Lee (1970). Ia menunjukkan bahwa subvarietas non-trivial yang tepat dari Bω membentuk
sebuah rantai

37
B0 ⊂ B1 ⊂ . . . (dimana B0 = B dan B1 adalah kelas yang dikenal sebagai aljabar Stone).
Variasi-variasi ini dapat didefinisikan secara sama. Sebagai alternatif, Teorema Produk Subdirect dari
Birkhoff mengimplikasikan bahwa mereka secara ekuivalen diberikan oleh Bn = ISD (Pn ), dimana
P n = (2n ⊕ 1; ∨, ∧,∗ , 0, 1) menyatakan kisi Boolean n-atom dengan sebuah top baru yang
disatukan, dan dengan sebuah operasi∗ dari pseudokomplemen yang diberikan oleh

a∗ = max { c | a ∧ c = 0 } .

Untuk menghindari kasus-kasus yang merosot, kami selanjutnya mengasumsikan n ≥ 3. Seperti

yang ditunjukkan pada Davey & Priestley (1993a), sebuah dualitas diperoleh untuk Bn dengan
~
mengambil P n = (Pn ; Rn ), dimana himpunan Rn dari relasi-relasi terdiri dari
(i) grafik dari 3 endomorfisma, e, f , g dari Pn , dan
(ii) sebuah himpunan Tn dari subaljabar-subaljabar
n P2 yang diindeks oleh partisi-partisi bilangan
bulat n.
Pada (i), f dan g adalah automorfisma dan ditentukan oleh permutasi yang mereka timbulkan
pada atom-atom P n , yaitu siklus (1 2 . . . . n) dan (1 2). Pada (ii) |Tn | tumbuh secara
eksponensial dengan n, dan wajar untuk bertanya apakah ada subset yang tepat dari Rn yang
masih menghasilkan dualitas. Sebuah partisi dari n menjadi
Σk
k bagian adalah k-tuple (λ1 , . . . , λk ) bilangan asli dimana λ1 ≥ - - - ≥ λk dan i= λi = n. Dua
1
dari relasi yang diinduksi partisi di Tn adalah isomorfis sebagai aljabar tepat ketika terkait
partisi memiliki jumlah bagian yang sama. Dugaan yang optimis tetapi masuk akal adalah
bahwa dualitas akan diperoleh dengan mereduksi Tn dengan memilih hanya satu partisi k-bagian
untuk setiap k (memberikan n + 3 relasi secara total).
Diberikan sebuah himpunan R dari subaljabar-subaljabar dari P2 yang diketahui
menghasilkan sebuah dualitas untuk sebuah kelas A = ISD(P ), bagaimana kita dapat
menguji apakah sebuah himpunan bagian yang tepat R' = R z {ρ} masih menghasilkan
sebuah dualitas? Tentu saja jika himpunan tereduksi R' gagal memberikan A ∼= ED(A) hanya
untuk satu A ∈ A maka relasi ρ tidak dapat dibuang.
Menghilangkan sebuah relasi tidak dapat mengurangi ukuran ED(A), jadi poin yang
dipermasalahkan adalah apakah jumlah dari peta-peta yang mempertahankan R' dari D(A) ke (P ; R' )
lebih besar dari ukuran aljabar uji A. Kita mengatakan R' menghasilkan sebuah dualitas pada A jika
tidak ada peta-peta tambahan yang diijinkan.
Ketika mencoba untuk memutuskan apakah ρ ∈ R dapat dibuang, sebuah pilihan alami
untuk sebuah aljabar uji A adalah ρ, dimana yang kita maksudkan adalah relasi ρ yang dianggap
sebagai sebuah aljabar (ingat bahwa setiap relasi kita adalah sebuah subaljabar dari P2 ). Di sini
(akhirnya!) kita memiliki sebuah masalah komputasi: bandingkan ukuran dari A dengan ukuran
dari himpunan ED(A) dari R' -mempertahankan peta-peta dari D(A) ke dalam (P ; R' ). Versi
paling awal dari algoritma backtracking kami (sebuah implementasi di VAX BASIC) berhasil
mendemonstrasikan bahwa tidak ada satupun relasi-relasi yang diakibatkan oleh partisi-partisi
yang dapat dibuang dari dualitas untuk B3 (seperti yang diharapkan, karena setiap partisi 3
memiliki jumlah bagian yang berbeda). Kasus uji kritis untuk dugaan kami adalah dengan n = 4
dan relasi ρ1 dan ρ2 yang terkait dengan partisi 2-bagian (2, 2) dan (3, 1).
Di sini D(ρ1 ) = D(ρ
2
) memiliki 42 elemen, |P4 | = 17, dan |R4 | = 8. Kami berusaha menghitung
jumlah peta Ψ : D(ρi ) → P4 yang mempertahankan R4 z{ρi } (i = 1, 2). Perhitungan ini berhasil
~
dilakukan pada sebuah PC, tetapi hanya setelah pilihan yang bijaksana untuk mengurutkan elemen-
elemen dari domain
telah dibuat. Sebelum menunjukkan bagaimana urutan elemen mempengaruhi perhitungan, kami
menyimpulkan sejarah masalah Bn .
Ternyata, menjatuhkan ρ1 atau ρ2 tidak menghancurkan dualitas pada aljabar uji ρ1 = ρ 2
(meskipun menjatuhkan keduanya). Hasil negatif ini konsisten dengan dugaan bahwa hanya satu
diperlukan, tetapi tidak membuktikannya. Pada titik ini, pemeriksaan terhadap keluaran
komputer memberikan wawasan yang cukup untuk memungkinkan dugaan tersebut
38
dikonfirmasi secara matematis untuk n = 4, dan selanjutnya untuk n secara umum.
Teorema 6.3 Asumsikan A seperti pada Teorema 6.2, bahwa R menghasilkan sebuah dualitas
pada A, dan biarkan R' = Rz{ρ}
(ρ ∈ R). Kemudian R' menghasilkan sebuah dualitas pada A jika dan hanya jika R' menghasilkan
sebuah dualitas pada aljabar ρ.
Dengan demikian, pengujian untuk redundansi dari relasi yang diberikan dalam dualitas
direduksi menjadi masalah yang terbatas, yang dapat dipecahkan dengan penerapan algoritma
pelacakan balik (tentu saja tergantung pada kelayakan komputasi).

39
 Bahasa Mesin Waktu Waktu
(sederhana) (ditingkatkan)
VAX BASIC VAX tidak tersedia tidak tersedia
GW DASAR 286 PC 2 jam 24 menit tidak tersedia
GW DASAR 386 PC 49 menit tidak tersedia
C (kompiler gcc) Matahari 3,9 detik 0,84 detik
3/50
Turbo PASCAL 286 PC 7 menit 30 detik 5,1 detik
Turbo PASCAL 386 PC 1 menit 52 detik 1,2 detik
C (kompiler gcc) Sparc 2 0,43 detik 0,08 detik

Tabel 2: Pengaturan waktu untuk implementasi yang berbeda dalam memecahkan

masalah B 4

Sekarang kita kembali ke aspek komputasi dari masalah B4 . Elemen-elemen dari himpunan
domain berada dalam orbit-orbit yang terpisah di bawah aksi dari automorfisma f dan g. Juga, jika Ψ
menjaga relasi, maka jika i dipetakan ke Ψ (i) maka f (i) harus dipetakan ke f (Ψ (i)) dan g (i) ke g
(Ψ (i)). Pengamatan ini menuntun kita untuk mengurutkan domain dengan cara berikut. Kita mulai
dari elemen sembarang, dinotasikan dengan 1, dan mengambil 2 = f (1), 3 = g(1) (kecuali f (1) =
g(1)). Setelah itu, kita memilih sebagai elemen berikutnya dalam urutan gambar f atau g dari elemen
pertama yang terdaftar yang gambarnya belum disertakan sampai orbit 1 habis. Proses ini diulangi
untuk orbit yang tersisa. Dengan demikian, kita mendapatkan pohon pencarian yang sangat
ekonomis, dengan 17.391 simpul. Perhatikan bahwa heuristik-heuristik pengurutan elemen dari
Bagian 7 sangat bagus dalam menemukan rantai-rantai hubungan seperti itu secara otomatis-bahkan
dimulai dari sebuah permutasi acak, mereka sejauh ini selalu berhasil menemukan permutasi yang
lebih baik daripada usaha-usaha "buatan tangan" terbaik! Sebagai contoh, sebuah perhitungan tipikal
untuk masalah B4 menghasilkan sebuah pohon pencarian dengan 10,336 simpul.
Beberapa waktu komparatif untuk masalah B4 untuk implementasi yang berbeda ditunjukkan
pada Tabel 2.
Versi VAX BASIC adalah yang pertama kali diimplementasikan, namun tidak pernah benar-
benar digunakan untuk masalah ini, itulah sebabnya mengapa waktunya tidak tersedia.
Implementasi pertama pada Sun 3/50 ditulis dalam perl yang merupakan bahasa yang
diinterpretasikan yang lebih cocok untuk pemrosesan string daripada pemrosesan numerik. Hal
ini memberikan pengaturan waktu yang kurang lebih sama dengan versi GW BASIC. Peralihan
ke bahasa yang dikompilasi, yaitu C pada Sun 3/50, menghasilkan peningkatan dramatis dalam
hal kecepatan yang mendorong kami untuk menangani beberapa contoh yang lebih besar.
Tabel 3 dan 4 mengilustrasikan pentingnya permutasi yang "baik" untuk masalah ini, Tabel
3 menunjukkan efek dari perubahan kecil pada permutasi yang baik. Permutasi untuk setiap
entri dalam tabel dihasilkan dengan menyusun permutasi sebelumnya dengan permutasi dalam
bentuk (i i + 1 . . . j) di mana i < j. Sebagai contoh, menyusun (1 2 3 4 5 6 7 8 9) dengan (4 5 6)
menghasilkan
(1 2 3 5 6 4 7 8 9). Kami menyebut operasi ini sebagai penyisipan. Tabel 3 menunjukkan efek dari
urutan

Penyisipan Hasil Diperlukan Uji Penyisipan Hasil Diperlukan Uji

Coba Coba
1 21 56,083 6 21 261,647
2 21 196,163 7 21 527,663
3 21 211,191 8 21 1,104,847
4 21 228,327 9 21 4,495,633
5 21 211,735 10 21 6,289,235

40
 Tabel 3: Pengaruh penyisipan acak pada permutasi "baik" untuk masalah B 4

penyisipan acak dimulai dengan permutasi yang digunakan di atas. Tabel 4 menunjukkan apa yang
terjadi pada masalah yang sama ketika sebuah permutasi acak dipilih (komputasi tabel ini
membutuhkan lebih dari 1 minggu waktu CPU pada Sparc 2). Setiap pasangan hasil adalah untuk
permutasi acak yang berbeda dengan masalah yang sama seperti di atas. Nilai "perkiraan" untuk
pohon pencarian dihitung dengan menggunakan rumus Knuth

41
 Diperkirakan Sebenarnya Diperkirakan Sebenarnya
138,568,972,267 > 10, 000, 000, 000 637,837,147,299 > 10, 000, 000, 000
190,500,933 190,764,514 16,911,522,238 > 10, 000, 000, 000
174,773,383 174,780,145 530,343,262,662 > 10, 000, 000, 000
55,741,733,482,643 > 10, 000, 000, 000 740,322,532 724,756,716
868,614,966 867,753,321 259,217,324 257,759,780
17,217,321,614 > 10, 000, 000, 000 32,654,546,016 > 10, 000, 000, 000
122,313,962 121,979,114 28,751,130 28,464,800
557,074,692 554,723,651 441,680,890 441,982,864
275,179,396,064 > 10, 000, 000, 000 27,659,921,478 > 10, 000, 000, 000
31,348,549,817 > 10, 000, 000, 000 16,474,273 16,314,730
3,574,075,557 3,568,600,866 106,754,057,688 > 10, 000, 000, 000
2,342,038,092 2,347,470,755 6,362,152,171 6,417,860,672
454,900,453 454,932,869 14,821,585,522 > 10, 000, 000, 000

Tabel 4: Menggunakan permutasi acak pada soal B 4

(Knuth (1975)) dengan 1.000.000 probe, lihat Bagian 7.4 untuk detailnya. Menggunakan metode estimasi
Knuth pada 487 permutasi acak dengan 1.000.000 probe masing-masing menghasilkan ukuran pohon
pencarian rata-rata sebesar [Link].638 node. Ini sesuai dengan waktu eksekusi (pada Sparc 2)
sekitar 3 tahun, sementara metode hybrid membutuhkan rata-rata 16 detik dan memeriksa total sekitar
800.000 node.
Untuk masalah yang lebih besar dengan tipe yang sama (menguji dualitas untuk optimalitas)
dengan domain 153 elemen, rentang 33 elemen dan 7 relasi, ukuran pohon pencarian rata-rata untuk
sebuah permutasi acak adalah sekitar 5 × 1035 yang mengindikasikan waktu eksekusi 5 × 1023
tahun (sekitar 30 juta juta kali usia alam semesta yang terlihat). Metode hibrida mengurangi hal ini
menjadi 37.09.801 simpul dan 763 detik.

6.3 Aplikasi Lainnya

Dualitas Priestley memberitahu kita bahwa sebuah kisi distributif berhingga L secara konkret
direpresentasikan sebagai himpunan peta yang menjaga urutan dari dualnya D(L) = D(L, 2),
yang diurutkan secara pointwise, ke dalam rantai 2 elemen 2 . Selanjutnya, diberikan kisi-kisi
distributif
~ berhingga L dan M , terdapat bijeksi antara D
homomorfisma dari L ke M dan peta-peta yang mempertahankan order dari D(M ) ke D(L). Lihat Bab
8
Lihat Davey & Priestley (1990) untuk penjelasan buku teks tentang teori ini, yang
memungkinkan masalah-masalah tentang kisi-kisi distributif berhingga diterjemahkan ke dalam
masalah-masalah tentang himpunan terurut berhingga. Peta L '→ D(L) bertindak seperti sebuah
"logaritma": secara umum |L | tumbuh secara eksponensial dengan |D(L)|. Secara komputasi,
hal ini sangat signifikan: masalah-masalah yang tidak dapat dipecahkan dalam bentuk kisi-kisi
menjadi dapat diakses setelah diterjemahkan ke dalam himpunan terurut. Algoritma peta-peta
yang menjaga relasi jelas dapat digunakan untuk menghitung peta-peta yang menjaga urutan
dari satu himpunan terurut berhingga (P; ≤) ke himpunan yang lain (Q; ≤). Secara khusus kita
bisa menemukan peta-peta yang menjaga urutan dari (P; ≤) ke 2 . Kami mencatat bahwa
berbagai macam
∼Algoritma khusus telah diturunkan untuk menangani hal ini masalah. Algoritma kami
memiliki
Kelebihan dari algoritma ini adalah sangat mudah beradaptasi dengan berbagai macam situasi
lainnya. Kami tidak mengklaim bahwa bahkan ketika ditingkatkan dengan heuristik pada Bagian 8,
ia akan selalu mengungguli algoritma-algoritma yang dirancang untuk masalah-masalah spesifik.
Sebagai contoh, pertimbangkan penentuan kardinalitas dari kisi-kisi distributif bebas {0, 1}

42
pada n generator. Elemen-elemen dari kisi ini dikenal sebagai peta-peta yang menjaga urutan
dari 2n ke 2 ; satu bukti diberikan oleh Teorema 6.3, yang diaplikasikan pada kasus Priestley
|F∼
dualitas.
menghitungNilai-nilai dari D ( n∼
)| hanya diketahui untuk n ≤ 8 (Weidemann (1991) baru-baru ini
|F D (8)). Algoritme kami menghitung nilai-nilai ini dengan mudah untuk n ≤ 6, tetapi
dikalahkan oleh kasus n = 7,
yang mana pendekatan matematika yang lebih canggih tampaknya penting. Bukti empiris
menunjukkan bahwa penentuan jumlah peta yang mempertahankan urutan dari sebuah himpunan
terurut m-elemen menjadi

43
 2 selalu layak untuk m ≤ 26 , dan layak dalam banyak kasus untuk m ≤ 27 , tetapi dengan kasus
terburuk
~
yang membuat algoritme kami tidak praktis dalam kasus-kasus tersebut.
Sekarang asumsikan, seperti pada 6.2, bahwa sebuah himpunan R dari relasi-relasi pada P memberikan sebuah
dualitas untuk sebuah kelas aljabar
A = ISD(P ). Dengan Teorema 6.3, aljabar bebas F A (n) diberikan oleh peta-peta yang melestarikan R dari
P n ke P ), di mana P = (P ; R). Baik teori maupun pengalaman mengatakan kepada kita bahwa
untuk aljabar yang muncul di
a∼lgebra∼logika ∼ i c (the∼kelas B , nberbagai kelas aljabar Heyting, dll.) normanya adalah bahwa ini bebas
n
aljabar tumbuh sangat cepat dengan n, lebih-lebih jika |P | > 2. Sebagai contoh, |F B (n) | = 22 , dan
|F K (3) = 43, 918 sedangkan |F K (4) = 160, 297, 985, 276 (Berman & Mukaidono (1984)).
Meskipun demikian, kami telah berhasil menggunakan algoritma kami pada beberapa masalah
seperti ini: lihat misalnya Priestley (1992).
Algoritma peta pemetaan relasi dirancang untuk memungkinkan dualitas yang diberikan pada
kelas aljabar A untuk diuji keoptimalannya. Pada awalnya, file data masukan diatur dengan
perhitungan manual yang melelahkan. Dalam aplikasi yang lebih baru dari teknik ini (Davey &
Priestley (1992), Priestley (1992)), algoritma pelacakan balik (backtracking) telah digunakan untuk
menghasilkan berkas-berkas data ini. Untuk melihat mengapa hal ini m u n g k i n dilakukan,
ingatlah bahwa sebuah himpunan domain D(A) (seperti pada 6.2) adalah sebuah himpunan dari peta-
peta, yaitu homomorfisma-homomorfisma A dari A ke P. Peta-peta seperti ini hanyalah peta-peta
yang mempertahankan relasi-relasi (tidak secara umum biner) yang merupakan grafik-grafik dari
operasi-operasi. Tentu saja, prosedur-prosedur yang dijelaskan pada Bagian 6.1 dengan mudah
beradaptasi pada relasi-relasi dengan aritas yang berbeda. Dalam contoh-contoh yang telah dianalisa
sejauh ini, aljabar-aljabar di A selalu memiliki struktur kisi distributif yang mendasari, sehingga
mesin penuh dari dualitas Priestley telah tersedia bagi kita. Hal ini memungkinkan kita untuk bekerja
bukan dengan homomorfisma tetapi dengan ekuivalen gandanya, yang merupakan peta-peta yang
mempertahankan urutan tertentu; hal ini dilakukan di seluruh Davey & Priestley (1992), Davey &
Priestley (1993a), Davey & Priestley (1993b) dan Priestley (1992). Dengan demikian, kita
mendapatkan keuntungan dari fitur "logaritmik" dari dualitas. Lebih jauh lagi, dualitas sering kali
memungkinkan kita untuk mengidentifikasi secara eksplisit relasi dari deskripsi aljabar teoritis (hal
ini dilakukan, sebagai contoh, untuk Bn dalam Davey & Priestley (1993a)). Perhitungan ini, sekali
lagi, dilakukan dengan aplikasi yang sesuai dari algoritma yang diberikan pada Bagian 6.1. Program-
program yang digunakan di sini merupakan bagian dari sebuah paket yang merupakan perangkat
yang sangat berharga bagi siapa saja yang ingin menyelidiki aljabar dengan struktur kisi distributif
yang mendasarinya. Paket ini mencakup, khususnya, fasilitas-fasilitas untuk menemukan (dalam
banyak kelas aljabar) homomorfisma, kongruensi, subaljabar dan penarikan kembali, dan untuk
pengujian isomorfisma.
Teori dualitas untuk kisi distributif telah digunakan secara ekstensif, sebagian karena,
sebagai sebuah gambar, teori ini sangat mudah digunakan. Representasi memang ada untuk kisi-
kisi sembarang yang menggeneralisasi apa yang diberikan oleh dualitas Priestley. Yang
diberikan oleh A. Urquhart (Urquhart (1977)) menggantikan himpunan terurut dengan struktur
dengan dua relasi quasi-order, sementara teori G. Hartung (Hartung (1992)) menggunakan
formalisme analisis konsep (diperkenalkan oleh R. Wille dalam Rival (1982)),
Hal. 445-470. Lihat juga Ganter, Wille & Wolff (1987) atau Bab 11 dari Davey & Priestley
(1990)). Algoritma backtracking sangat cocok untuk membuat representasi ini menjadi alat
yang praktis. Dengan bantuan paket ini, sangat memungkinkan untuk mengotomatisasi
pembuatan dualitas alami yang optimal dalam sejumlah besar kasus, sebagai contoh, untuk
beberapa jenis aljabar Heyting tertentu (lihat Davey & Priestley (1993a)). Setiap perhitungan
tersebut membutuhkan banyak subrutin yang berbeda, yang masing-masing menggunakan
pelacakan balik dengan cara yang berbeda.

7 Mundur dengan Pemilihan Urutan Elemen

44
Pada Bagian 5 kita mencari urutan-urutan elemen-elemen p yang memenuhi predikat-predikat V (p)
dan
C(p). Algoritma backtracking mencoba setiap ekstensi yang mungkin dari sebuah urutan parsial
secara bergantian. Karena pada akhirnya kita harus mencoba semua ekstensi yang mungkin, tidak
ada bedanya dengan urutan yang kita pilih untuk mencobanya: semua ekstensi pada akhirnya harus
dicoba. Jika kita sedang mencari satu elemen, maka kita dapat menggunakan heuristik untuk
mencoba ekstensi-ekstensi yang "paling mungkin" terlebih dahulu. Sekarang perhatikan kasus
dimana p adalah sebuah larik yang elemen-elemennya bisa diisi dengan urutan apapun. Masalah
delapan ratu dapat diekspresikan dalam bentuk ini, seperti yang telah didiskusikan di Bagian 2.2.
Pada masalah seperti ini, urutan pengisian elemen-elemen larik dapat memiliki efek dramatis pada
waktu eksekusi, seperti

45
 diilustrasikan pada tabel 3 dan 4. Pada bagian ini kita akan membahas berbagai heuristik yang telah
kita gunakan untuk memilih urutan elemen: hal ini sering kali memungkinkan kita untuk
menyelesaikan perhitungan yang jika tidak dilakukan akan menjadi tidak mungkin.
Kami mempertimbangkan spesifikasi yang sama seperti pada Bagian 5, kecuali bahwa semua
sekuens memiliki panjang yang sama,
N , dan sebuah barisan yang valid adalah barisan yang tidak memiliki posisi yang
DF
"tidak terisi", yaitu
C(p) = ∀i, 1 ≤ i ≤ N .p[i] /=
⊥ di mana ⊥ adalah elemen baru (tidak ada di D) yang digunakan untuk mewakili posisi yang tidak
terisi.
SPEC = DF
for p ∈ { p ∈ D∗ | V (p) ∧ C (p) ∧ l (p) = N } do proses(p) od
Daripada memperluas ini untuk memproses semua ekstensi-ekstensi yang valid dari p, kita perlu
memproses semua komplemen yang valid dari p dimana urutan yang tidak lengkap adalah sebuah "larik
yang terisi sebagian". Misalkan p ∈ (D ∪ {⊥})∗ memiliki panjang N . Lalu kita definisikan:
SPEC(p) = DF
for q ∈ { q ∈ D∗ | p ± q ∧ V (q) ∧ C (q) ∧ l (q) = N } do process(q) od
dimana p ± q berarti bahwa q adalah p dengan beberapa elemen yang tidak terisi terisi, yaitu
DF
p±q=
∀i. 1 ≤
i ≤ N. (p[i] = ⊥ ∨ p[i] = q[i]).
Dengan menggunakan permutasi π : {1, 2, . . . , N } → {1, 2, . . . N } dan sebuah variabel n
untuk mencatat berapa banyak elemen dari p yang terisi, kita bisa menghindari kebutuhan akan
elemen tambahan ⊥. Permutasi juga mencatat urutan larik yang akan diisi. Elemen-elemen n
p[π[1]], . . . , p[π[n]] dari p akan terisi, dan N - n elemen p[π[n + 1]], . . . . p[π[N ]] dari p saat ini
tidak terisi. Penurunan yang serupa dengan yang ada di Bagian 5 menghasilkan algoritma berikut:
var n := 0, t := 1 :
sementara n > 0 ∨ t ≤ D lakukan
jika t > D maka t := p[π[n]]; n := n - 1; t := t + 1
jika V' (t, p, π, n) maka jika n = N maka proses' (t, p); t := t + 1
else n := n + 1; p[π[n]] := t; t := 1 fi
else t := t + 1 fi od end
Ini memberikan hasil yang sama dengan SPEC untuk setiap permutasi π : {1, 2, . . . , N } → {1, 2, . .
. , N }. Pada kenyataannya kita dapat melakukan permutasi elemen-elemen dari π[d + 1], menjadi
π[N ] kapan saja selama eksekusi program.
Pemilihan nilai yang sesuai untuk π sangat penting: kami telah menggunakan dua heuristik dasar
untuk mencapai hal ini, yang dapat digabungkan untuk membentuk metode hibrida ketiga. Metode
ini disebut "pra-analisis" dan "pemangkasan semak".
Pada algoritma-algoritma di bawah ini, kita mengisi larik p dengan urutan yang diberikan oleh π.
Akan tetapi, pada implementasi C, kita meng-update larik rel X ke dan rel ke X setiap kali π berubah
(sebagai efeknya, mengubah peta antara bilangan bulat dan elemen-elemen X). Hal ini meningkatkan
efisiensi dengan menghilangkan sebagian besar akses ke π.

7.1 Heuristik "Pra-Analisis"

Heuristik pra-analisis adalah sebuah metode untuk memilih permutasi π yang sesuai. Metode ini
melibatkan perluasan permutasi parsial yang "baik" secara iteratif dengan menambahkan sebuah
elemen dan mencari elemen-elemen yang dapat digeser untuk memperbaiki permutasi tersebut.
"Menggeser" sebuah elemen dalam sebuah permutasi berarti menyusun π dengan sebuah
permutasi (i i+1 . . . j) di mana i < j atau menyusun dengan sebuah permutasi (i i-1 . . . j) di
mana i > j. Hal ini terlihat memiliki peluang yang lebih baik untuk memperbaiki permutasi
daripada hanya menukar dua elemen yang berdekatan (menyusun dengan (i i+1)), atau menukar
dua elemen secara acak (menyusun dengan (i j)).

46
Kami menggunakan dua definisi yang berbeda tentang permutasi parsial yang "lebih baik":
1. Pilih permutasi yang menghasilkan pohon pencarian backtracking yang lebih kecil (yaitu
jumlah elemen yang diperiksa oleh prosedur processall). Jika kedua pohon pencariannya sama,
maka pilihlah permutasi yang pohon pencariannya memiliki jumlah elemen "daun" yang lebih
kecil (yaitu jumlah elemen ukuran penuh yang diperiksa oleh processall);

47
 2. Pilih permutasi yang pohon pencariannya memiliki jumlah elemen daun yang lebih kecil; jika
mereka memiliki jumlah elemen daun yang sama, pilih permutasi yang total pohon
pencariannya lebih kecil.
Kami menggunakan sebuah versi dari algoritma backtracking dasar untuk menghitung
ukuran dari pohon pencarian dan jumlah dari elemen-elemen daun untuk permutasi parsial
π[mindepth . . maxdepth], dimana elemen-elemen π[1 . . mindepth - 1] telah "dibekukan" (lihat
di bawah). Proses ini akan segera berhenti jika jumlah percobaan yang dibutuhkan untuk
perhitungan melebihi batas (setiap evaluasi dari V' (t, p, π, n) adalah satu "percobaan" karena
evaluasi-evaluasi ini mendominasi seluruh perhitungan):
proc calculate(mindepth, maxdepth, cutoff ) ≡
count := 0; trials := 0;
var n := mindepth; t := 1 :
while (n > 0 ∨ t ≤ D) ∧ percobaan ≤ batas akhir do
jika t > D maka t := p[π[n]]; n := n - 1; t := t + 1
else uji coba := uji coba + 1;
jika V' (t, p, π, n) maka jika n = maxdepth
then count := count + 1; t := t + 1
else d := d + 1; p[π[d]] := t; t := 1 fi
else t := t + 1 fi od end.
Kami berulang kali menguji "pergeseran" acak (di mana setidaknya salah satu dari i atau j
harus ada di dalam permutasi parsial) untuk melihat apakah permutasi parsial tersebut dapat
ditingkatkan. Setelah beberapa kali gagal, kita berasumsi bahwa ini adalah yang terbaik yang
dapat kita lakukan untuk ukuran permutasi parsial ini, sehingga kita meningkatkan ukurannya
dengan menambahkan satu elemen, dan kemudian mencoba meningkatkan permutasi yang lebih
besar. Perhatikan bahwa secara umum, permutasi "terbaik" dengan ukuran n + 1 bukanlah
perluasan sederhana dari permutasi "terbaik" dengan ukuran n. Kita memiliki sebuah
"anggaran" yang membatasi berapa kali kita ingin mengevaluasi fungsi V' (karena ini adalah
bagian yang paling mahal dari algoritma). Setelah anggaran ini habis, kita "membekukan"
permutasi parsial yang sedang berjalan, dan mulai membuat permutasi parsial baru dengan
elemen-elemen yang tersisa. Setelah semua elemen habis, kita menggabungkan permutasi parsial
yang "dibekukan" untuk mendapatkan permutasi lengkap yang digunakan untuk melakukan
perhitungan penuh. Kami memiliki anggaran lain untuk perhitungan penuh dan jika ini habis
sebelum perhitungan selesai maka kami menghentikan perhitungan penuh, menggandakan
anggaran analisis dan perhitungan dan mulai lagi dari awal. Program ini mencetak pesan-pesan
ketika proses berjalan (yang dapat disimpan dalam file log) sehingga pengguna dapat memantau
perkembangannya.
Dengan demikian, rutin pra-analisis bekerja dengan meningkatkan ukuran permutasi parsial saat
ini, yang disimpan di π[mindepth . . depth], dengan menambah kedalaman, dan kemudian
menyesuaikan permutasi untuk meminimumkan pohon pencarian. Subrutin menemukan elemen
kedalaman yang baik mencoba memasukkan setiap elemen π[depth + 1] ke π[SX] pada posisi
kedalaman untuk menemukan yang terbaik. Subrutin ini meng-update jumlah variabel-variabel
global dan percobaan-percobaan dengan jumlah simpul-simpul daun dalam pohon pencarian untuk
π[mindepth . . depth] dan jumlah total simpul-simpul dalam pohon tersebut. find good insert secara
berulang-ulang mengambil sepasang elemen secara acak di dalam π (setidaknya salah satu dari
elemen-elemen tersebut harus ada di dalam π[mindepth . . depth]), menyisipkan satu elemen ke
dalam posisi elemen yang lain, dan menguji apakah ini meningkatkan permutasi. Proses ini akan
berhenti ketika ia kehabisan anggaran (jumlah total percobaan yang diperbolehkan), atau ia telah
mencoba penyisipan maxgoes tanpa memperbaiki permutasi parsial. Ia menetapkan penyisipan
variabel global yang dilakukan pada jumlah penyisipan yang bagus yang ditemukan.
kedalaman pikiran := 1;
for depth := 1 to SX - 1 step 1 do

48
do menemukan elemen kedalaman yang baik (mindepth,
depth, maxtrials/10); hasil terbaik := count; percobaan
terbaik := percobaan;
jika uji coba terbaik ≥ uji coba maksimal / 10
then print("Elemen terbaik berikutnya terlampaui:", maxtrials/10,
" uji coba pada kedalaman:",
kedalaman, mindepth); mindepth := kedalaman;
for i := 1 to mindepth step 1 do p[i] := 0 od

49
 jika tidak, keluar dari fi od;
anggaran := maxtrials;
printinfo(mindepth, depth, percobaan terbaik, hasil terbaik);
if depth > mindepth
kemudian mencoba kembali := 1
do budget := maxtrials - uji coba terbaik;
find good insert(mindepth, depth, best trials, best result);
best result := count; best trials := trials;
printinfo(mindepth, depth, best trials, best result);
printinfo(mindepth, depth, best trials, best result)
percobaan ulang := percobaan ulang + 1;
if retries > maxretries ∨ sisipan selesai = 0 then keluar dari fi od od
Penugasan pada p[i] ketika mindepth dinaikkan adalah untuk mengindikasikan pada rutinitas
kalkulasi bahwa relasi-relasi yang melibatkan elemen-elemen ini tidak harus dipertahankan. Elemen
"0" dapat dianggap sebagai elemen baru, ditambahkan ke himpunan B, yang berhubungan dengan
dirinya sendiri dan semua elemen lainnya di setiap relasi di RY .
Prosedur printinfo mencetak laporan status tentang kemajuan penghitungan, termasuk total
waktu CPU yang digunakan, dan waktu CPU yang digunakan sejak laporan status terakhir.
Setelah rutinitas ini berakhir (ketika depth = SX - 1) kita menggunakan rutinitas kalkulasi dengan
anggaran total percobaan (jumlah total percobaan yang digunakan oleh pra-analisis). Jika ini gagal
karena melebihi anggarannya, maka kita menggandakan maxtrials dan maxgoes dan menjalankan
pra-analisis lagi dengan anggaran yang lebih besar. Hal ini diharapkan akan menghasilkan permutasi
yang lebih baik untuk perhitungan penuh berikutnya, yang m a n a akan memiliki anggaran yang
lebih besar untuk digunakan. Dengan demikian waktu kita akan terbagi secara merata antara pra-
analisis dan percobaan perhitungan.
Perhatikan bahwa heuristik ini bisa memakan waktu hingga empat kali lebih lama dari yang
dibutuhkan jika perhitungan yang dicoba kehabisan anggaran "tepat sebelum" perhitungan selesai.
Selain itu, tidak selalu mudah untuk melihat dari laporan status berapa lama waktu yang dibutuhkan
untuk menyelesaikan perhitungan. Produk sampingan yang berguna dari metode ini adalah cetakan
permutasi terbaik yang ditemukan.

7.2 Heuristik "Pemangkasan Semak"

Metode pra-analisis melakukan beberapa analisis awal (untuk jangka waktu tertentu) untuk
mencoba menemukan permutasi yang sesuai. Kemudian metode ini mencoba melakukan
perhitungan penuh dengan permutasi tersebut. Jika perhitungan gagal (karena kehabisan waktu
sebelum menyelesaikan pencarian), maka kita menggandakan anggaran analisis dan perhitungan
dan memulai lagi.
Sebaliknya, metode yang dijelaskan di bagian ini memulai perhitungan penuh dengan
segera, dengan permutasi awal yang diperbarui "dengan cepat" saat perhitungan berlangsung.
Hal ini bergantung pada fakta yang telah disebutkan di atas, bahwa elemen-elemen π[n + 1]
hingga π[N ] dapat dipermutasikan kapan saja tanpa mempengaruhi hasil akhir.
Metode ini disebut pemangkasan semak karena metode ini bergantung pada meminimalkan
ukuran pohon kecil2 yang dibentuk dengan menambahkan beberapa elemen ke peta parsial saat ini.
Aplikasi yang paling sederhana dari metode ini (yang telah berhasil) adalah memilih elemen dengan
gambar yang paling sedikit, setiap kali sebuah elemen ditambahkan ke peta saat ini (kecuali jika peta
saat ini sudah hampir selesai). Secara alami, jika sebuah elemen ditemukan yang tidak memiliki
gambar yang valid, maka urutan parsial saat ini dapat ditinggalkan (semak saat ini telah dipangkas
sepenuhnya!).
Pada kasus umum, metode ini membagi waktunya antara mendorong maju dengan pencarian dan
memangkas semak pada posisi saat ini. Karena yang terbaik adalah memangkas dengan frekuensi
50
yang sama pada semua tingkat pohon (selain dari 1/4 tingkat pohon terakhir yang tidak perlu
dipangkas), kami menggunakan larik semak berikutnya[1 . . N] untuk mencatat "waktu" ketika setiap
kedalaman berikutnya akan dipangkas. "Waktu" ini adalah
2Semak adalah pohon kecil!

51
diukur dalam hal jumlah total uji coba, yaitu evaluasi V' (t, p, π, n).
Algoritmanya didasarkan pada algoritma kalkulasi dengan kode pemangkasan semak yang
ditambahkan. Prosedur find good element(n) memilih elemen untuk dimasukkan ke dalam π[n]
yang memiliki jumlah terkecil dari gambar-gambar yang mempertahankan relasi di Y. find bush
size(n) mengatur bush ke ukuran bush yang "cocok" untuk pemangkasan: dengan kata lain,
menambahkan elemen-elemen bush ke permutasi parsial yang ada saat ini akan menghasilkan
pohon pencarian yang berisi tentang bush budget/bush goes node. prune bush(n, bush)
kemudian menggunakan percobaan-percobaan bush budget untuk memperbaiki bagian
permutasi antara n dan n + bush.
uji coba semak := 0; count := 0;
n := 0; t := 1;
dilakukan jika t ≤ D
maka total percobaan := total percobaan + 1;
jika V' (t, p, π, n)
maka jika n = SX maka hitung := hitung + 1; t := t + 1;
else p[π[n]] := t; n := n + 1; t := 1;
if n < 3N/4 ∧ total percobaan > next bush[n]
then bush terakhir :=
percobaan bush; cari
ukuran bush(n);
memangkas semak(n,
semak); memperbarui
semak berikutnya() fi fi
else t := t + 1 fi
else n := n - 1;
jika n = 0 maka keluar dari fi;
t := p[π[n]] + 1 fi od
di mana
proc update next bush() ≡ next bush() ≡
for i := n to n + bush langkah 1 do
semak berikutnya [i] :=total percobaan + 5 (percobaan semak - semak terakhir) od.
Perhatikan bahwa jika find bush size memperluas semak ke seluruh himpunan, maka elemen p
saat ini telah sepenuhnya ditemukan (semua ekstensi-ekstensi validnya telah ditemukan). Juga
jika find bush size atau prune bush pernah mencapai sebuah semak tanpa daun (tidak ada
ekstensi-ekstensi yang valid sampai dengan n + semak) maka tidak akan ada ekstensi-ekstensi
yang lengkap dan valid dari p saat ini. Dalam kedua kasus tersebut, kita bisa langsung melompat
ke langkah n := n - 1, dan inilah yang dilakukan oleh implementasi C. Implementasi C juga
mencetak laporan status secara berkala (setelah setiap uji coba langkah bush pr).

7.3 Metode Hibrida

Heuristik pemangkasan semak harus dimulai dengan beberapa permutasi, meskipun hanya
permutasi acak. Metode hybrid dimulai dengan melakukan pra-analisis awal untuk menyediakan
permutasi awal ini, dan kemudian beralih ke metode pemangkasan semak. "Bagian pertama" dari
permutasi ini, sampai pada titik di mana pra-analisis pertama kali meningkatkan mindepth,
dipertahankan dari modifikasi oleh pemangkasan semak. Hal ini dicapai dengan mengatur bush[i]
berikutnya untuk elemen-elemen ini ke suatu nilai yang sesuai. Bagian domain ini akan memiliki
sejumlah peta parsial, kita harus menentukan semua ekstensi yang valid dari peta-peta ini. Oleh
karena itu, kita memiliki ukuran kasar dari kemajuan melalui perhitungan dengan melihat berapa
banyak peta parsial yang telah diproses sejauh ini. Ini hanya ukuran kasar karena beberapa peta
parsial mungkin memiliki lebih banyak ekstensi yang valid daripada yang lain, tetapi ini dapat
memberikan beberapa indikasi kelayakan: misalnya jika program dibiarkan berjalan selama akhir

52
pekan dan telah memproses kurang dari 1% dari kumpulan peta parsial, maka kemungkinan akan
membutuhkan lebih banyak hari lagi untuk menjalankannya hingga selesai.

53
7.4 Heuristik berdasarkan Algoritma Estimasi Knuth
Dalam Knuth (1975), Knuth menyajikan sebuah metode untuk memperkirakan ukuran pohon
pencarian dari sebuah algoritma pelacakan balik yang sederhana. Metode ini didasarkan pada
pembuatan sejumlah "probe" acak ke d a l a m pohon, memilih jalur acak pada setiap tahap, dan
menghitung total tertimbang dari biaya perhitungan yang dilakukan pada setiap node:

C = c() + d0 c(x1 ) + d d01 c(x1 , x2 ) + d d d012 c(x1 , x2 , x3 ) + . .

Disini c(x1 , . . . ) adalah biaya dari komputasi pada simpul p = ⟨x1 , . . . ⟩ (dalam kasus kita,
biaya-biaya ini semuanya sama sehingga kita menetapkan semuanya ke 1), d0 adalah jumlah
dari elemen-elemen awal x sedemikian rupa sehingga urutan ⟨x⟩ valid. Salah satu dari elemen-
elemen ini, x1 , dipilih secara acak. Untuk setiap urutan yang valid p = ⟨x1 , . . . . xi ⟩, di+1 adalah
jumlah elemen x yang dapat ditambahkan ke p untuk mendapatkan urutan yang valid. Salah satu
dari elemen-elemen ini, xi+1 , dipilih secara acak. Prosedur ini berakhir ketika di adalah nol. C
adalah estimasi biaya dari pemeriksaan ini.
Knuth memberikan dua "bukti" ('setidaknya salah satu dari bukti-bukti tersebut haruslah
meyakinkan') bahwa nilai yang diharapkan dari C adalah biaya dari pencarian backtracking yang
lengkap. Dia mengatakan bahwa metode ini telah diuji pada lusinan aplikasi dan secara konsisten
berkinerja sangat baik, bahkan pada masalah-masalah yang dimaksudkan untuk menjadi contoh
yang buruk. Dalam hampir setiap kasus, urutan yang tepat untuk ukuran pohon ditemukan setelah
sepuluh kali percobaan. Dia membahas satu percobaan secara detail (masalah "tur ksatria") di mana
rata-rata lebih dari 1.000 jalan acak menghasilkan perkiraan dalam 0,5% dari jawaban yang
sebenarnya yaitu [Link].
Algoritma ini tampaknya menyediakan metode yang ideal untuk menentukan mana dari dua
permutasi yang lebih baik (dan dengan demikian untuk menemukan permutasi yang baik), yang tidak
seperti metode-metode kami sebelumnya, mempertimbangkan seluruh permutasi. Sayangnya, untuk
sebagian besar masalah peta pengawetan relasi kami, estimasi tampaknya kurang akurat dari
yang kami harapkan: bahkan rata-rata lebih dari 100.000 probe, dan mengambil beberapa menit
waktu CPU pada Sparc 2, estimasi akan bervariasi dengan faktor dua atau lebih, dengan
beberapa masalah memberikan estimasi yang sangat tidak akurat.
Terlepas dari hasil yang mengecewakan ini, kami mengimplementasikan algoritma
pemilihan permutasi berdasarkan metode estimasi Knuth. Algoritme ini menguji berbagai
kemungkinan penyisipan, menggunakan metode Knuth untuk melihat apakah permutasi tersebut
sudah lebih baik. Segera setelah permutasi muncul untuk memberikan pohon pencarian yang
layak, algoritme mencoba melakukan perhitungan. Jika ini gagal (dengan mengambil lebih dari
dua kali jumlah percobaan yang diperkirakan), kami berasumsi bahwa dengan merata-ratakan
lebih banyak jalan acak, kami akan mendapatkan perkiraan yang lebih baik. Oleh karena itu,
kami meningkatkan jumlah random walk (misalnya 20% hingga 50% setiap kali) hingga
estimasi lebih besar dari dua kali estimasi yang lama (kami tahu bahwa ukuran pohon pencarian
yang sebenarnya setidaknya sebesar ini). Kami mendefinisikan pohon pencarian yang "layak"
sebagai pohon pencarian yang diperkirakan membutuhkan waktu kurang dari seperempat dari
total jumlah percobaan yang telah kami lakukan dalam analisis sejauh ini: ini berarti bahwa
ketika pencarian permutasi yang baik membutuhkan waktu yang lebih lama, kami akan terus
melonggarkan syarat-syarat kelayakan.
Sayangnya, metode heuristik ini gagal total! Masalah utamanya adalah:
1. Kadang-kadang terjadi kesalahan meremehkan (bahkan dengan jumlah probe yang banyak)-hal ini
menyebabkannya berpikir bahwa penyisipan acak tertentu lebih baik, padahal mungkin lebih
buruk. Jadi, hal ini menjauhkannya dari optimalitas;
2. Banyaknya jumlah probe yang diperlukan, berarti bahwa hanya sejumlah kecil insersi
yang dapat diuji. Jadi, hanya perlu beberapa langkah untuk mencapai optimalitas.

54
3. Pada masalah-masalah yang lebih besar, alih-alih menemukan permutasi yang "bagus",
algoritma ini hanya menemukan permutasi dimana metode Knuth secara konsisten
meremehkan hasilnya. Sebagai contoh, setiap perkiraan mungkin sekitar 108 hingga 109
sementara pohon yang sebenarnya memiliki urutan yang jauh lebih besar dari 109 node.
Efeknya adalah metode ini terus melakukan perhitungan percobaan yang gagal dan
menyebabkan jumlah probe ditingkatkan ke tingkat tertentu sehingga program secara
efektif "berhenti". Dalam satu kasus, meningkatkan ukuran sampel dari 5.000 menjadi
7.500 menyebabkan estimasi menjadi

55
 20 berubah dari 10 percobaan7 yang cukup layak menjadi 10 percobaan yang sama sekali
tidak praktis. Algoritma ini kemudian "memperbaiki" permutasi ini dengan menemukan
permutasi baru yang mana metode Knuth meremehkan ukuran pohon.
Masalah ini masih ada bahkan ketika rata-rata pada jumlah probe yang sangat banyak, misalnya
dengan 100.000 sampel yang membutuhkan beberapa menit waktu CPU pada Sparc 2 untuk menguji
satu penyisipan. Akibatnya, metode ini telah ditinggalkan, meskipun kodenya tersedia dari penulis.
Tabel 5 membandingkan metode pemangkasan semak dengan metode berdasarkan algoritma Knuth
untuk beberapa contoh terkecil kami.

Jumlah uji coba Waktu CPU

Ukuran Knuth Hibrida Knuth Hibrida
Masalah
42 × 17 28,550,038 789,604 533 16
64 × 2 67,119,212 37,248,521 2,722 1,048
65 × 2 49,438,402 23,438,477 2,223 599
64 × 8 2,898,059 231,928 102 94
153 × 33 tidak 1,422,829 > 44, 000 763
diketahui3

Tabel 5: Pemangkasan Semak dibandingkan dengan metode berdasarkan algoritma estimasi Knuth.
("Ukuran masalah" mengacu pada ukuran domain dan jangkauan).

7.5 Batasan Praktis dari Metode ini

Setelah menguji berbagai metode pada banyak contoh peta pengawetan relasi dari berbagai jenis,
kesimpulan kami adalah bahwa metode hibrida, dengan anggaran 10.000 untuk pra-analisis dan
anggaran pemangkasan semak sebesar 100.000, adalah yang terbaik secara keseluruhan. Satu-
satunya batasan praktis dari metode ini adalah konsekuensi dari keumumannya: algoritme ini
dirancang untuk memproses setiap peta yang mempertahankan relasi secara individual, dan oleh
karena itu dibatasi oleh jumlah peta yang harus ditemukan, bahkan ketika "proses" adalah hitungan
sederhana. Semua contoh kami dengan hingga 10 peta9 berhasil, satu-satunya kegagalan kami
adalah masalah-masalah yang diketahui memiliki lebih banyak solusi (10 peta11 atau lebih).
Masalah-masalah seperti itu hanya dapat diselesaikan dengan menggunakan pengetahuan yang lebih
dalam tentang struktur kisi tertentu yang terlibat, untuk menghitung solusi-solusi dalam "rumpun"
yang besar, bukan satu per satu. Sebagai contoh, Berman dan Mukaidono (Berman & Mukaidono
(1984)) menggunakan simetri dan pengelompokan untuk menghitung |F K (n)|, jumlah aljabar
Kleene bebas pada n generator, untuk kasus n = 4. Hasil [Link] berada di luar rentang
yang layak untuk algoritma tujuan umum kami. Algoritma kami menangani kasus n = 3 hanya dalam
waktu 11 detik dan 500.000 percobaan.
Kode sumber untuk implementasi C yang dioptimalkan dari semua algoritma, bersama
dengan file data sampel dan file parameter, tersedia dari penulis. M. Ward akan sangat tertarik
untuk mendengar dari siapa saja yang memiliki aplikasi-aplikasi backtracking lainnya yang dapat
mengambil manfaat dari heuristik pengurutan elemen.

8 Mengotomatiskan Proses Transformasi

Teori transformasi program yang digunakan dalam makalah ini merupakan dasar dari proyek
"Maintainer's Assistant" (Bull (1990), Ward & Bennett (1993), Ward & Bennett (1995), Ward,
Calliss & Munro (1989)) di Durham University dan Centre for Software Maintenance Ltd. yang
bertujuan untuk menghasilkan alat bantu untuk membantu pemrogram pemelihara dalam
memahami dan melakukan rekayasa balik sistem perangkat lunak yang besar. Asisten
Pemelihara terdiri dari editor struktur interaktif dan pencetak cantik, yang diimplementasikan
56
pada X Windows, dan mesin transformasi, yang diimplementasikan pada LISP dan WSL. Mesin
transformasi mencakup pustaka lebih dari enam ratus transformasi yang telah terbukti,
3Program belum dihentikan setelah lebih dari 12 jam waktu CPU.

57
termasuk sebagian besar yang digunakan dalam turunan program di atas. Setelah transformasi
yang tersisa diimplementasikan, maka akan memungkinkan untuk melakukan penurunan secara
interaktif: mulai dari spesifikasi formal dan menggunakan urutan transformasi dan
penyempurnaan yang telah terbukti, dengan sistem yang memeriksa semua kondisi kebenaran
pada setiap tahap, akhirnya menerjemahkan kode WSL yang dihasilkan (yang dapat dieksekusi)
ke dalam bahasa pemrograman yang sesuai, seperti C. Salah satu hasil menarik yang kami
perhatikan dari pengalaman kami dengan transformasi manual adalah bahwa jenis kesalahan
(klerikal dan logis) yang dibuat dalam menurunkan algoritme cenderung merupakan jenis
kesalahan (misalnya menulis <, bukan >) yang ditemukan oleh beberapa kasus uji pertama.
Setelah kesalahan-kesalahan ini diperbaiki, program-program tersebut selalu lulus semua kasus
uji dengan sempurna. Hal ini berbeda dengan bug pemrograman pada umumnya yang
cenderung tidak kentara dan sangat sulit untuk dilacak.

Referensi
Arsac, J. (1982a): Transformasi Prosedur Rekursif. Dalam: Neel, D. (ed.) Alat-alat dan Notasi-notasi untuk
Konstruksi Program. Cambridge University Press, Cambridge, pp. 211-265
Arsac, J. (1982b): Transformasi Program Sumber ke Sumber Sintaksis dan Manipulasi Program. Comm.
ACM 22, 1, pp. 43-54
Berman, J. & Mukaidono, M. (1984): Pencacahan fungsi-fungsi switching fuzzy dan aljabar Kleene bebas.
Comput. Math. Appl. 10, pp. 25-35
Bull, T. (1990): Sebuah Pengantar ke Program WSL Transformer. Konferensi Pemeliharaan Perangkat Lunak
26-29 November 1990, San Diego
Butler, G. & Lam, C. W. H. (1985): Algoritma Backtrack Umum untuk Masalah I s o m o r f i s m e Objek
Kombinatorial. J. Symb. Comput.
Davey, BA & Priestley, HA (1987): Dualitas piggyback yang digeneralisasi, dengan aplikasi pada aljabar Ockham.
Houston J. Math. 13, hal. 151-198
Davey, B. A. & Priestley, H. A. (1990): Pengantar Kisi dan Keteraturan. Cambridge University Press,
Cambridge
Davey, B. A. & Priestley, H. A. (1992): Dualitas optimal untuk jenis-jenis aljabar Heyting. pracetak
Davey, BA & Priestley, HA (1993a): Dualitas alami yang diinduksi partisi untuk jenis-jenis kisi distributif
pseudokompleks. Matematika Diskrit. 113, pp. 41-58
Davey, B. A. & Priestley, H. A. (1993b): Dualitas alami yang optimal. Trans. Amer. Math. Soc. 338, hal.
655 - 677
Davey, B. A. & Werner, H. (1983): Dualitas dan ekuivalensi untuk jenis-jenis aljabar. In: Huhn, AP &
Schmidt, ET (eds.) Kontribusi pada teori kisi (Szeged, 1980). (Colloq. Math. Soc. J'anos Bolyai no.
33.) North-Holland, Amsterdam, pp. 101-275
Dijkstra, E. W. (1976): Sebuah Disiplin Pemrograman. Prentice-Hall, Englewood Cliffs, NJ
Ganter, B., Wille, R. & Wolff, K. (eds.) (1987): Beitra¨ge zur Begriffsanalyse. B.I. Wissenschaftsverlag,
Mannheim, Zu¨rich
Gerhart, S. L. & Yelowitz, L. (1976): Abstraksi Struktur Kontrol dari Teknik Pemrograman Backtracking. IEEE
Trans. Software Eng. SE 2, 4, hal. 285-292
Hartung, G. (1992): Representasi topologi dari kisi-kisi. Aljabar Universalis 29, hal. 273-299
Hoare, C. A. R., Hayes, I. J., Jifeng, H. E., Morgan, C. C., Roscoe, A. W., Sanders, J. W., Sørensen, I. H.,
Spivey, J. M. & Sufrin, B. A. (1987): Hukum Pemrograman (Laws of Programming). Comm. ACM 30,
8, pp. 672-686
Knuth, D. E. (1974): Pemrograman Terstruktur dengan Pernyataan GOTO. Comput. Survei 6, 4, hal. 261-
301
Knuth, D. E. (1975): Mengestimasi Efisiensi Algoritma Pelacakan Mundur (Backtracking). Math. of
Comput. 29, 129,
Hal. 121-136

58
Knuth, D. E. & Szwarcfiter, J. L. (1974): Sebuah Program Terstruktur untuk Menghasilkan Semua
Susunan Pengurutan Topologi. Menginformasikan. Process. Lett. 2, hal. 153-157

59
Lee, K. B. (1970): Kelas-kelas persamaan dari kisi-kisi pseudo-komplemen distributif. Canad. J. Math. 22,
Hal. 881-891
Morgan, C. C. (1994): Pemrograman dari Spesifikasi. Prentice-Hall, Englewood Cliffs, NJ. Edisi Kedua
Priestley, HA (1992): Dualitas alami untuk jenis-jenis kisi distributif dengan pengukur. Prosiding Banach
Centre Semester ke-38 tentang Logika Aljabar dan Aplikasi Ilmu Komputer akan terbit
Rival, I., (ed.) (1982): Himpunan Terurut, Reidel, Dordrecht
Roever, W. P. de (1978): Tentang Backtracking dan Titik Perbaikan Terbesar. Dalam: Neuhold, E. J. (ed.)
Deskripsi Formal dari Konstruk-konstruk Pemrograman. North-Holland, Amsterdam, pp. 621-636
Stallman, R. M. (1989): Menggunakan dan Mem-porting GNU CC. Free Software Foundation, Inc.
Taylor, D. (1984): Sebuah Alternatif untuk Sintaks Perulangan Saat Ini. SIGPLAN Notices 19, 12, hal. 48-
53 Urquhart, A. (1977): Sebuah teori representasi topologi untuk kisi-kisi. Aljabar Universalis 8, hal. 45-
58 Walker, R. J. (1960): Sebuah Teknik Enumeratif untuk sebuah kelas Masalah Kombinatorial. Dalam:
Bellman, R. E.
& Hall Jr, M. (eds.) Prosiding Simposium Matematika Terapan 10: Analisis Kombinatorial. Am. Math. Soc.,
Providence R.I.
Ward, M. (1989): Membuktikan Penyempurnaan dan Transformasi Program. Oxford University, DPhil
Thesis Ward, M. (1990): Penurunan dari sebuah Algoritma Pengurutan. Universitas Durham, Laporan
Teknis. ⟨http: // www.
dur. ac. uk/∼dcs0mpw/martin/papers/[Link]⟩
Ward, M. (1991a): Spesifikasi dan Program dalam Bahasa Spektrum Luas. Dikirimkan ke J. Assoc.
Comput. Mach.
Ward, M. (1991b): Teorema Penghapusan Rekursi-Bukti dan Aplikasi. Universitas Durham, Laporan
Teknis. ⟨[Link] dur. ac. uk/∼dcs0mpw/martin/papers/ [Link]⟩
Ward, M. (1992): Teorema Penghapusan Rekursi. Springer, New York Berlin Heidelberg. Prosiding
Lokakarya Penyempurnaan ke-5, London, 8-11 Januari. ⟨http: // www. dur. ac. uk/ ∼dcs0mpw/ martin/
papers/[Link]⟩
Ward, M. (1994): Dasar-dasar Teori Praktis tentang Penyempurnaan dan Transformasi Program.
Universitas Durham, Laporan Teknis. ⟨[Link] dur. ac.
uk/∼dcs0mpw/martin/papers/[Link]⟩
Ward, M. (1993): Mengabstraksikan Spesifikasi dari Kode. J. Pemeliharaan Perangkat Lunak: Penelitian
dan Praktek 5, 2, John Wiley & Sons, hal. 101-122.
⟨[Link]
Ward, M. (1996): Penurunan Algoritma Intensif Data dengan Transformasi Formal. IEEE Trans. Software
Eng. 22, 9, pp. 665-686. ⟨[Link] dur. ac. uk/∼dcs0mpw/martin/papers/[Link]⟩
Ward, M. & Bennett, K. H. (1993): Sistem Transformasi Program Praktis Untuk Rekayasa Balik.
Konferensi Kerja tentang Rekayasa Balik, 21-23 Mei 1993, Baltimore MA. ⟨http: // www. dur. ac. uk/
∼dcs0mpw/martin/papers/[Link]⟩
Ward, M. & Bennett, KH (1995): Metode Formal untuk Sistem Lama. J. Pemeliharaan Perangkat Lunak:
Research and Practice 7, 3, John Wiley & Sons, pp. 203-219.
⟨[Link] [Link]⟩
Ward, M., Calliss, F. W. & Munro, M. (1989): Asisten Pemelihara. Konferensi Pemeliharaan Perangkat
Lunak 16-19 Oktober 1989, Miami Florida. ⟨http: // www. dur. ac. uk/ ∼dcs0mpw/ martin/ papers/
[Link]⟩
Weidemann, D. A. (1991): Perhitungan bilangan Dedekind ke-8. Orde 8, hal. 5-6 Wells, M.
B. (1971): Elemen-elemen Komputasi Kombinatorial. Pergamon Press, New York

60
Wirth, N. (1971): Pengembangan Program dengan Penyempurnaan Bertahap. Comm. ACM 14, 4, hal. 221-227

Lampiran: C Implementasi Algoritma Backtracking Sederhana

Lampiran ini memberikan implementasi C dari algoritma backtracking sederhana (tanpa pemilihan urutan
elemen). Kode sumber dan file data sampel untuk semua algoritma tersedia dari penulis.
Perhatikan bahwa "subrutin" DO (disebut relpres di bawah ini) disalin pada tempatnya: ini untuk
menghindari overhead pemanggilan subrutin untuk kompiler-kompiler yang (tidak seperti kompiler GNU
C, gcc contohnya Stallman (1989)) tidak bisa menangani subrutin "inline". Versi ini menggunakan ii
sebagai pengganti i dan menggunakan larik psi untuk urutan p. Seperti yang telah disebutkan di atas
(Bagian 7) kita mengupdate rel ke X dan rel X ke setiap kali π berubah, ini berarti bahwa p[π[i]] dapat
disimpan di psi[i].
/*********************************************************************
*
* Menghitung dan mengembalikan jumlah peta yang menyimpan relasi
* pada bagian domain antara mindepth dan maxdepth inklusif.
* Mengasumsikan bahwa array rel_to_X dan rel_X_to telah diatur.
* Mengembalikan jumlah peta yang ditemukan.
* Mengatur percobaan variabel global ke jumlah panggilan relpres yang diperlukan.
* Segera hentikan jika jumlah percobaan melebihi batas waktu.
*
********************************************************************/

ganda
calculate (mindepth, maxdepth, cutoff)
int mindepth, maxdepth;
batas waktu ganda;
{
/* Hitung dan kembalikan jumlah peta yang menyimpan relasi:
* gunakan mindepth untuk memaksimalkan elemen domain,
* hentikan segera setelah jumlah percobaan melebihi batas waktu
*/
hitungan
ganda; int
rho;
register short rp, n, t, np;
register int ii, numrels;

percobaan = 0;
hitung = 0;
n = kedalaman
pikiran; t =
1;
for (;;) { perulangan
calc_do1: */ if (t <= SY) {
uji coba = uji coba +
1; if (uji coba >
batas akhir) {
goto calc_od1;
}
/* Memulai subrutin relpres:
* if relpres(psi,t,n) then rp=1
* relpres(psi,t,n) sama dengan psi[n]=t; relpres(psi,n)
* t adalah nilai tes untuk psi[n], relpres(psi,n-1) adalah
benar */ rp = 1;
for (rho = 0; rho < R; rho++) {
/* uji relasi rho: */
/* Elemen uji yang berhubungan
dengan X */ numrels =
61
rel_to_X[rho][n][0];
for (ii = 1; ii <= numrels; ii++) {
np = rel_to_X[rho][n][ii]; /* np adalah elt ke-i yang berhubungan dengan n
*/

62
 if (np < n) { psi[np] didefinisikan:
*/ if (RY[rho][t][psi[np]] == 0) {
rp = 0;
goto calc_end_relpres;
}
} else {
if (np == n) {/* n berhubungan dengan dirinya sendiri */
if (RY[rho][t][t] == 0) { /* periksa apakah t berhubungan
dengan dirinya sendiri */ rp = 0;
goto calc_end_relpres;
} else { np > n, yaitu tidak ada lagi elts yang
berhubungan dengan n */ goto calc_end_inner_1;
}
}/* fi (np == n) */
}/* fi np < n */
}/* Akhir dari perulangan
inner for */ calc_end_inner_1:
/* Elemen uji X berhubungan dengan
*/ numrels = rel_X_to[rho][n][0];
for (ii = 1; ii <= numrels; ii++) {
np = rel_X_to[rho][n][ii]; np adalah elt ke-i yang berhubungan
denganif (np < n) { psi[np] sudah didefinisikan: */
if (RY[rho][psi[np]][t] == 0) {
rp = 0;
goto calc_end_relpres;
}
} else { sudah dicek n berhubungan dengan n case
*/ goto calc_end_inner_2;
}/* fi np < n */
}/* Akhir dari perulangan
inner for */ calc_end_inner_2:;
}/* Akhiri perulangan for luar, relasi berikutnya */
/* Akhir dari subrutin relpres */
calc_end_relpres:
if (rp == 1) {
if (n == maxdepth) {
count++;
t++;
} else {
psi[n] = t;
n++;
t = 1;
}
} else {
t++;
}
} else { from (t <= SY) */
n--;
if (n < mindepth) {
goto calc_od1;
}
t = psi[n] + 1;
}/* fi from (t <= SY) */
}
calc_od1:
pengembalian (hitungan);
}/* Akhir dari menghitung (mindepth, maxdepth, cutoff) */

33

Lihat statistikpublikasi