Bagian Uji penguasaan
Empat butir berikut merupakan materi asli pendamping. Kerjakan tanpa membuka petunjuk terlebih dahulu, lalu gunakan pembahasan untuk mengaudit perhitungan dan argumen batas bawah Anda.
Dalam \(\{0,1\}^7\text{,}\) ambil \(x=1011010\text{,}\) \(y=0011111\text{,}\) dan \(z=0011011\text{.}\) Hitung ketiga jarak pasangan dan tentukan apakah pertidaksamaan segitiga menjadi kesamaan melalui \(z\text{.}\)
Petunjuk.
Jawaban.
Solusi.
Petunjuk. Tandai koordinat yang berbeda untuk setiap pasangan secara terpisah.
\(d_H(x,y)=3\text{,}\) \(d_H(x,z)=2\text{,}\) dan \(d_H(z,y)=1\text{;}\) jadi kesamaan segitiga berlaku.
Kata \(x,y\) berbeda pada koordinat \(1,5,7\text{,}\) sehingga \(d_H(x,y)=3\text{.}\) Kata \(x,z\) berbeda pada koordinat \(1,7\text{,}\) sehingga jaraknya \(2\text{.}\) Kata \(z,y\) hanya berbeda pada koordinat kelima, sehingga jaraknya \(1\text{.}\) Maka \(d_H(x,y)=3=2+1=d_H(x,z)+d_H(z,y)\text{;}\) \(z\) berada pada suatu lintasan terpendek dari \(x\) ke \(y\) dalam kubus Hamming.
Pemeriksaan D.10. Penguasaan 2: kapan dekode terdekat bersifat unik.
Misalkan jarak minimum antara dua kata kode berbeda dalam \(C\) adalah \(\delta\text{.}\) Buktikan: jika kata diterima \(r\) memenuhi \(d_H(r,c)<\delta/2\) untuk suatu \(c\in C\text{,}\) maka \(c\) adalah satu-satunya kata kode terdekat dengan \(r\text{.}\)
Petunjuk.
Jawaban.
Solusi.
Petunjuk. Andaikan ada \(c'\ne c\) dengan \(d_H(r,c')\leq d_H(r,c)\text{,}\) lalu gunakan pertidaksamaan segitiga pada \(c,r,c'\text{.}\)
Benar. Kata kode lain yang setidaknya sama dekat akan memaksa \(d_H(c,c')<\delta\text{,}\) bertentangan dengan definisi jarak minimum kode.
Andaikan \(c'\in C\text{,}\) \(c'\ne c\text{,}\) dan \(d_H(r,c')\leq d_H(r,c)\text{.}\) Pertidaksamaan segitiga memberi
\begin{equation*}
d_H(c,c')\leq d_H(c,r)+d_H(r,c')
\leq 2d_H(r,c)<\delta.
\end{equation*}
Namun dua kata kode berbeda harus berjarak sedikitnya \(\delta\text{.}\) Kontradiksi ini menunjukkan bahwa tidak ada \(c'\) yang sama dekat atau lebih dekat daripada \(c\text{.}\) Jadi dekode terdekatnya unik.
Pemeriksaan D.11. Penguasaan 3: jarak “kitten” dan “sitting”.
Hitung jarak Levenshtein antara “kitten” dan “sitting”. Berikan urutan edit yang mencapai nilai tersebut dan sertakan alasan bahwa dua operasi tidak cukup.
Petunjuk.
Jawaban.
Solusi.
Petunjuk. Dua substitusi dan satu penyisipan memberi batas atas; gunakan rekurensi awalan untuk batas bawah.
\(d_L(\text{kitten},\text{sitting})=3\text{.}\)
Urutan “kitten” → “sitten” → “sittin” → “sitting” memakai substitusi “k” menjadi “s”, substitusi “e” menjadi “i”, lalu penyisipan “g”. Jadi jaraknya paling besar tiga.
Rekurensi awalan dari pembahasan tugas Levenshtein 3, dengan kolom berlabel awalan “sitting”, menghasilkan baris terakhir untuk “kitten” \((6,6,5,4,3,3,2,3)\text{.}\) Unsur terakhir adalah tiga. Karena rekurensi itu menguji ketiga kemungkinan operasi terakhir dan dimulai dari nilai batas yang tepat, tidak ada urutan sepanjang dua. Maka jaraknya tepat tiga.
Pemeriksaan D.12. Penguasaan 4: membandingkan Hamming dan Levenshtein.
Untuk dua untai biner \(x,y\) dengan panjang sama, buktikan \(d_L(x,y)\leq d_H(x,y)\text{.}\) Tunjukkan bahwa pertidaksamaan dapat ketat dengan menghitung kedua jarak bagi \(x=0101\) dan \(y=1010\text{.}\)
Petunjuk.
Jawaban.
Solusi.
Petunjuk 1. Substitusikan tepat koordinat yang berbeda untuk memperoleh batas umum.
Petunjuk 2. Pada contoh, satu penghapusan dan satu penyisipan memindahkan pola bergantian.
Selalu berlaku \(d_L\leq d_H\text{.}\) Pada contoh, \(d_H(0101,1010)=4\text{,}\) sedangkan \(d_L(0101,1010)=2\text{.}\)
Jika \(x,y\) berbeda pada \(k=d_H(x,y)\) koordinat, substitusikan huruf \(x\) pada masing-masing koordinat tersebut dengan huruf \(y\text{.}\) Urutan ini mengubah \(x\) menjadi \(y\) dalam \(k\) operasi, sehingga minimum Levenshtein memenuhi \(d_L(x,y)\leq k\text{.}\)
Keempat koordinat \(0101\) dan \(1010\) berbeda, jadi jarak Hamming-nya empat. Untuk Levenshtein, hapus nol pertama dari “0101” sehingga diperoleh “101”, lalu sisipkan nol di ujung sehingga diperoleh “1010”; jadi \(d_L\leq2\text{.}\) Jaraknya bukan nol karena untainya berbeda. Jaraknya juga bukan satu: satu penyisipan atau penghapusan akan mengubah panjang, sedangkan satu substitusi hanya dapat mengubah satu dari empat koordinat yang berbeda. Jadi \(d_L=2<4=d_H\text{.}\)
