# UAS — Kecerdasan Artifisial (MII 212401): KOMA (2024) — Model Answers

> Final Exam · Odd Semester 2024/2025 · Universitas Gadjah Mada
> Answers to `UAS - Kecerdasan Artifisial - KOM A - 2024.md`. Penomoran mengikuti transkripsi berurutan (label cetak asli di lembar ujian: 1, 3, 4, 5).

| Field | Value |
|---|---|
| **Course** | Kecerdasan Artifisial (MII 212401): KOMA |
| **Exam type** | Ujian Akhir Semester (UAS) |
| **Semester** | Gasal 2024/2025 |
| **Date** | Senin, 2 Desember 2024 |
| **Time** | 120 menit |
| **Lecturer** | Dr. Sri Mulyana, M.Kom. |
| **Exam mode** | Buku Tertutup |

**Institution:** Program Studi S1 Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Gadjah Mada

---

## Soal 1 — Forward Chaining: Membuktikan K (PLO 3; CO 4; Nilai 10%)

### Konsep

**Forward chaining** adalah penalaran *data-driven* pada sistem berbasis aturan: mulai dari fakta yang diketahui, cocokkan anteseden (bagian **IF**) setiap aturan dengan isi *working memory*, jalankan (*fire*) aturan yang terpenuhi, tambahkan konsekuennya (bagian **THEN**) sebagai fakta baru, lalu ulangi sampai goal tercapai atau tidak ada aturan yang bisa dijalankan lagi (*fixed point*). Kebalikannya, *backward chaining* (goal-driven), mulai dari goal K lalu mencari aturan yang mendukungnya.

Siklus kerja per iterasi:

1. **MATCH** — cari semua aturan yang belum dijalankan dan antesedennya ⊆ *working memory* (himpunan aturan yang cocok ini disebut *conflict set*).
2. **FIRE** — jalankan aturan-aturan yang cocok (strategi pada soal latihan seperti ini: jalankan semuanya sesuai nomor aturan), tambahkan konsekuen ke *working memory*.
3. **CEK** — jika **K ∈ WM**, goal terbukti → berhenti; jika *conflict set* kosong → berhenti (titik tetap); jika tidak → ulangi.

### Eksekusi langkah demi langkah

**Fakta awal: WM₀ = {A, E}** (A dan E benar). Goal: membuktikan **K benar**.

**Siklus 1 — WM = {A, E}** — pemeriksaan keterpenuhan anteseden:

| Aturan | Anteseden | Terpenuhi? | Konsekuen |
|---|---|---|---|
| R-1 | A & B | ✗ (B tidak ada) | — |
| R-2 | C | ✗ | — |
| R-3 | A & E | ✓ | **F** |
| R-4 | A | ✓ | **G** |
| R-5 | F & G | ✗ | — |
| R-6 | E & G | ✗ | — |
| R-7 | C & H | ✗ | — |
| R-8 | A & I | ✗ | — |
| R-9 | G | ✗ | — |
| R-10 | J | ✗ | — |

→ Fire **R-3** (A & E → F) dan **R-4** (A → G). **WM₁ = {A, E, F, G}**

**Siklus 2 — WM = {A, E, F, G}**
- R-5: F & G ✓ → **D**
- R-6: E & G ✓ → **H**
- R-9: G ✓ → **J**

→ Fire **R-5, R-6, R-9**. **WM₂ = {A, D, E, F, G, H, J}**

**Siklus 3 — WM = {A, D, E, F, G, H, J}**
- R-10: J ✓ → **K**

→ Fire **R-10**. **WM₃ = {A, D, E, F, G, H, J, K}** → **K terbukti BENAR** ✓

**Siklus 4** — tidak ada lagi aturan yang antesedennya terpenuhi (R-1 butuh B; R-2 butuh C; R-7 butuh C & H; R-8 butuh I — semuanya tidak terjangkau) → berhenti (*fixed point*).

### Rangkuman siklus

| Siklus | WM awal | Aturan di-*fire* | Fakta baru | WM akhir |
|---|---|---|---|---|
| 1 | A, E | R-3, R-4 | F, G | A, E, F, G |
| 2 | A, E, F, G | R-5, R-6, R-9 | D, H, J | A, D, E, F, G, H, J |
| 3 | A, D, E, F, G, H, J | R-10 | **K** | A, D, E, F, G, H, J, K |

Rantai derivasi ringkas:

**A, E →(R-3, R-4)→ F, G →(R-5, R-6, R-9)→ D, H, J →(R-10)→ K**

### Kesimpulan dan catatan penting

- **K BENAR** — dibuktikan dalam 3 siklus forward chaining. Aturan terpakai: R-3, R-4, R-5, R-6, R-9, R-10; WM akhir = {A, D, E, F, G, H, J, K}.
- Aturan yang **tidak pernah terpakai**: R-1, R-2, R-7, R-8. Sebabnya berantai: tidak ada fakta **B** dan tidak ada aturan yang menghasilkan B, sehingga R-1 tidak pernah bisa menghasilkan **C**; tanpa C, R-2 (C→D) dan R-7 (C & H→I) tidak aktif; tanpa I, jalur alternatif menuju J lewat R-8 (A & I→J) tertutup. K tetap tercapai lewat jalur pendek **R-4 → R-9 → R-10**.
- **Jalur minimal menuju K**: A →(R-4)→ G →(R-9)→ J →(R-10)→ K — hanya benar-benar membutuhkan fakta A. Fakta E "hanya" menghasilkan F, D, dan H, dan tidak berada pada jalur kritis menuju K (tetap tetap di-*fire* oleh forward chaining karena sifatnya mengambil semua fakta yang bisa diturunkan).
- *Cross-check* backward chaining: K ⇐ R-10 (J) ⇐ R-9 (G) ⇐ R-4 (A = fakta) — konsisten. Pencarian mundur yang mencoba R-8 dulu akan tersangkut di R-7 → R-1 karena B tidak ada (*dead end*) lalu *backtrack* ke R-9.
- Catatan: trace di atas diverifikasi dengan program *rule-chainer* sederhana (Python) — hasil identik: K dicapai pada siklus ke-3.

---

## Soal 2 — Parse Tree Top-Down: "He book a flight to Houston" (PLO 3; CO 5; Nilai 15%)

Grammar pada soal ini adalah CFG pengajaran standar (grammar "L1") dari buku teks NLP Jurafsky & Martin, yang juga membedahkan perilaku parsing top-down vs bottom-up serta ambiguitas penempatan PP [1].

### Strategi parsing top-down

Parsing **top-down** dimulai dari akar pohon, yaitu simbol awal **S**, lalu **menuruni** aturan produksi untuk menebak struktur kalimat sebelum melihat kata-katanya: produksi diekspansi *depth-first* dari kiri ke kanan; setiap kategori preterminal (Pronoun, Det, Verb, Prep, Proper-Noun, …) dicocokkan dengan kata input pada posisi tertentu; jika cocok → lanjut ke produksi berikutnya; jika tidak cocok → **backtrack** dan coba produksi alternatif. Ini kebalikan parsing **bottom-up**, yang mulai dari kata-kata lalu menggabungkannya menjadi frasa sampai terbentuk S.

Kelemahan khas top-down yang relevan pada grammar ini: aturan **rekursif-kiri** `Nominal → Nominal Noun` dan `Nominal → Nominal PP` membuat ekspansi murni dapat berputar tanpa henti (harus dibatasi kedalaman/di-*backtrack*), dan parser top-down menebak ulang subtree yang sama tanpa memanfaatkan kata yang sudah dicocokkan [1].

### Penandaan kategori tiap kata (kunci jawaban — hati-hati jebakan!)

| Kata | Kategori | Catatan |
|---|---|---|
| He | **Pronoun** | subjek |
| book | **Verb** | **JEBAKAN**: "book" tercantum di dua kategori leksikon (Noun *buku* dan Verb *memesan*). Karena mengikuti subjek pronoun dan diikuti objek NP, di kalimat ini book berperan sebagai **Verb** ("memesan") |
| a | Det | penanda nomina |
| flight | Noun | |
| to | Prep | |
| Houston | **Proper-Noun** | nama tempat, bukan Noun biasa |

(Kalimat ini sebenarnya tidak gramatikal dalam bahasa Inggris baku — seharusnya "He books a flight…" — karena leksikonnya memang grammar mainan L1 dari buku teks; yang diuji adalah mekanisme parsing, bukan kegramatikalan [1].)

### Tahapan pencarian top-down (depth-first, kiri → kanan, dengan backtracking)

Input: w1 = He, w2 = book, w3 = a, w4 = flight, w5 = to, w6 = Houston.

| # | Aksi | Posisi | Status |
|---|---|---|---|
| 1 | Coba S → Aux NP VP → Aux harus cocok dengan w1 | w1 | ✗ (leksikon Aux = {does} ≠ He) → backtrack |
| 2 | Coba S → VP → VP harus diawali Verb | w1 | ✗ (He bukan Verb) → backtrack |
| 3 | **S → NP VP** | w1 | ✓ (prediksi diterima) |
| 4 | **NP → Pronoun**; cocokkan Pronoun = He | w1 | ✓ (w1 terpakai) |
| 5 | Coba VP → Verb; Verb = book cocok | w2 | ✓, tetapi kalimat akan selesai di w2 padahal masih ada "a flight to Houston" → ✗ backtrack |
| 6 | **VP → Verb NP**; Verb = book | w2 | ✓ (w2 terpakai) |
| 7 | NP di w3: Pronoun? ✗; Proper-Noun? ✗; **NP → Det Nominal**; Det = a | w3 | ✓ (w3 terpakai) |
| 8 | Nominal → Noun; Noun = flight cocok | w4 | ✓, tetapi kalimat selesai sebelum "to Houston" → ✗ backtrack |
| 9 | Nominal → Nominal Noun (rekursif-kiri): Nominal dalam → Noun = flight ✓, tetapi tiap level luar menuntut satu Noun lagi di w5 = "to" yang bukan Noun → gagal pada semua kedalaman (dan tanpa batas kedalaman parser murni akan berputar) → ✗ backtrack |
| 10 | **Nominal → Nominal PP**: Nominal bagian dalam → **Noun** = flight | w4 | ✓ (w4 terpakai) |
| 11 | **PP → Prep NP**; Prep = to | w5 | ✓ (w5 terpakai) |
| 12 | NP di w6: Pronoun? ✗; **NP → Proper-Noun** = Houston | w6 | ✓ (semua kata terpakai) |
| 13 | Semua cabang produksi tertutup, input habis tepat saat pohon penuh | — | ✓ **PARSE BERHASIL** |

### Derivasi leftmost (ringkasan tahapan pembentukan pohon)

S ⇒ NP VP ⇒ **Pronoun** VP ⇒ He VP ⇒ He **Verb** NP ⇒ He book NP ⇒ He book **Det** Nominal ⇒ He book a Nominal ⇒ He book a **Nominal PP** ⇒ He book a **Noun** PP ⇒ He book a flight PP ⇒ He book a flight **Prep NP** ⇒ He book a flight to NP ⇒ He book a flight to **Proper-Noun** ⇒ **He book a flight to Houston** ✓

### Parse tree hasil (PP menempel pada Nominal — parse yang pertama ditemukan)

```
                     S
          ┌──────────┴───────────┐
          NP                     VP
          │              ┌───────┴───────┐
      Pronoun            Verb            NP
          │               │        ┌─────┴─────┐
         He            book       Det       Nominal
                                    │     ┌────┴────┐
                                    a  Nominal     PP
                                          │    ┌────┴────┐
                                        Noun  Prep      NP
                                          │    │         │
                                       flight  to   Proper-Noun
                                                         │
                                                     Houston
```

Bentuk bracketed:

`(S (NP (Pronoun He)) (VP (Verb book) (NP (Det a) (Nominal (Nominal (Noun flight)) (PP (Prep to) (NP (Proper-Noun Houston)))))))`

### Catatan ambiguitas — ada parse tree kedua yang juga valid

Grammar ini **ambigu** (*PP-attachment ambiguity*): frasa "to Houston" juga dapat menempel pada VP melalui produksi `VP → VP PP`, menghasilkan parse kedua yang lengkap dan valid [1]:

```
                     S
          ┌──────────┴───────────┐
          NP                     VP
          │             ┌────────┴────────┐
      Pronoun          VP                PP
          │        ┌────┴────┐       ┌────┴────┐
         He       Verb      NP     Prep       NP
                   │     ┌───┴───┐    │         │
                 book   Det   Nominal to   Proper-Noun
                         │       │                   │
                         a     Noun              Houston
                                 │
                              flight
```

Bentuk bracketed:

`(S (NP (Pronoun He)) (VP (VP (Verb book) (NP (Det a) (Nominal (Noun flight)))) (PP (Prep to) (NP (Proper-Noun Houston)))))`

Perbedaan makna: parse pertama — PP memodifikasi nomina ("penerbangan *menuju Houston*"); parse kedua — PP memodifikasi aksi ("*memesan* penerbangan, *ke Houston*"). Kedua tree diverifikasi lengkap oleh parser atas grammar yang sama (tepat 2 parse). Untuk jawaban ujian, satu tree yang benar sudah cukup; menyebut ambiguitas dan menggambar keduanya adalah nilai tambah.

---

## Soal 3 — Permasalahan yang Dapat Ditangani Pengenalan Pola (PLO 2; CO 6; Nilai 15% — label cetak "4")

### Konsep inti

**Pengenalan pola** (pattern recognition) adalah disiplin yang menetapkan suatu objek/peristiwa ke dalam **kategori (kelas)** berdasarkan hasil **pengukuran (fitur)**. Sebuah "pola" adalah vektor fitur x = (x₁, …, xₙ) hasil pengukuran instansi; tugasnya memetakan x → kelas ω₁, ω₂, …, ωc. Pipelinenya selalu sama:

**penginderaan/pengambilan data → prapemrosesan → ekstraksi fitur → klasifikasi/pelatihan.**

Konsekuensinya: **setiap permasalahan yang (1) instansinya dapat diukur menjadi fitur dan (2) memiliki kategori yang terdefinisi** dapat ditangani dengan pendekatan pengenalan pola.

### Bidang/permasalahan yang dapat ditangani

1. **Biometrik & identifikasi diri** — pengenalan sidik jari, wajah, iris/retina, suara (*speaker recognition*), tanda tangan, gaya berjalan (*gait*).
2. **Medis & kesehatan** — klasifikasi citra rontgen/CT/MRI/USG (deteksi tumor, pneumonia, retinopati), klasifikasi sinyal ECG/EEG (aritmia), sitologi/sel darah, penilaian risiko penyakit (diabetes, jantung).
3. **Dokumen & teks** — OCR (citra huruf → teks), kategorisasi dokumen, filter spam, analisis sentimen, identifikasi penulis; klasifikasi teks termasuk aplikasi pengenalan pola klasik yang juga dibahas di buku teks NLP [1].
4. **Ucapan & audio** — pengenalan ucapan (speech-to-text), identifikasi pembicara, klasifikasi genre musik, deteksi kejadian suara.
5. **Citra & computer vision** — deteksi/pengenalan objek dan pejalan kaki (kendaraan otonom), rambu lalu lintas, plat nomor, ekspresi wajah/gestur, inspeksi mutu industri (deteksi cacat produk).
6. **Pertanian** — pengenalan penyakit tanaman dari citra daun, sortir/grading buah, estimasi/prediksi panen.
7. **Penginderaan jauh & lingkungan** — klasifikasi tutupan lahan pada citra satelit (hutan, pemukiman, sawah), pemetaan bencana, estimasi kualitas udara, prediksi curah hujan.
8. **Keuangan & bisnis** — credit scoring, deteksi fraud transaksi/kartu, prediksi kebangkrutan, segmentasi pelanggan, prediksi churn, pola harga saham.
9. **Keamanan & pertahanan** — deteksi/klasifikasi target radar/sonar, pengawasan (deteksi anomali), klasifikasi malware/intrusi jaringan.
10. **Bioinformatika** — klasifikasi sekuens DNA/protein, kelas struktur protein, analisis microarray.
11. **Robotika & interaksi manusia–mesin** — pengenalan landmark untuk navigasi/SLAM, klasifikasi medan, pengenalan gestur, pengenalan aktivitas.

### Benang merah antar-aplikasi

| Domain | Contoh fitur (input) | Kelas (output) |
|---|---|---|
| Medis | ukuran, tekstur, bentuk nodul pada citra CT | {jinak, ganas} |
| Biometrik | vektor minutiae sidik jari | {identitas A, B, …} |
| Keuangan | jumlah & frekuensi transaksi, usia akun, tingkat refund | {fraud, sah} |
| Teks | frekuensi kata / TF-IDF | {spam, bukan spam} |
| Citra daun | warna, tekstur, bentuk bercak | {sehat, jamur, virus} |

Semua contoh mengikuti pola yang sama: **ukur → fitur → klasifikasi**. Hubungan dengan machine learning: pengenalan pola klasik merancang fitur secara manual lalu memakai pengklasifikasi statistik; ML/deep learning modern mengotomatisasi tahap ekstraksi fitur (*representation learning*), tetapi tetap berada dalam kerangka yang sama — belajar pemetaan fitur → kelas dari data.

---

## Soal 4 — Fitur Citra Digital (PLO 2; CO 6; Nilai 15% — label cetak "5")

### Dasar: citra digital sebagai fungsi diskret

Citra digital adalah citra kontinu f(x, y) yang didiskretisasi dua kali: **sampling spasial** (menjadi grid M×N piksel) dan **kuantisasi amplitudo** (nilai intensitas dibulatkan ke level diskret, mis. 2ᵏ level untuk kedalaman k bit). Citra digital = matriks M×N berisi nilai piksel; untuk citra warna, tiga kanal (M×N×3, mis. RGB). Fitur-fitur berikut diekstraksi dari representasi ini.

### Fitur citra digital (menurut tingkatannya)

**A. Tingkat piksel / intensitas**
- **Nilai piksel & kedalaman bit** — grayscale 8 bit = 256 level; biner 1 bit; warna 24 bit (8-8-8).
- **Brightness** (kecerahan rata-rata), **kontras** (sebaran/deviasi intensitas), **dynamic range** (rentang level yang benar-benar terpakai).
- **Resolusi** — resolusi spasial (ukuran M×N / DPI → detail spasial) dan resolusi intensitas (jumlah level abu-abu; kuantisasi terlalu kasar menimbulkan *false contouring*).

**B. Statistik & histogram**
- **Histogram** distribusi intensitas beserta statistiknya: mean, varians, skewness, kurtosis, **entropi**.
- Bentuk histogram dipakai untuk peningkatan citra (equalisasi/spesifikasi histogram) dan sebagai fitur global (citra gelap vs terang, kontras rendah vs tinggi).

**C. Warna**
- **Model warna** (RGB, HSV, CMYK, L\*a\*b\*) dan **color depth**.
- Fitur warna: rata-rata per kanal, **color moments** (mean, standar deviasi, skewness), **color histogram**, warna dominan.

**D. Tekstur** — pola permukaan: kesan halus/kasar, arah/keteraturan, granularitas.
- Metode: **GLCM/Haralick** (kontras, homogenitas, energi, entropi dari matriks co-occurrence), **Local Binary Pattern (LBP)**, filter **Gabor**, transformasi **wavelet**. Region seragam vs bertekstur dibedakan lewat statistik lokal.

**E. Tepi, bentuk & struktur geometris**
- **Tepi (edge)** — diskontinuitas intensitas (deteksi Sobel/Prewitt/Canny); kontur objek.
- **Fitur bentuk** — area, perimeter, kekompakan, eccentricity; **moment Hu** (invarian terhadap rotasi/skala/translasi); skeleton; **corner/interest point** (Harris).
- **Topologi** — ketetanggaan piksel (4-/8-connectivity), **connected component**, region hasil segmentasi, blob.

**F. Fitur domain frekuensi**
- Spektrum **Fourier/DFT**, **DCT**, **wavelet**: memuat informasi periodicitas, arah tekstur; komponen frekuensi rendah = bentuk global, frekuensi tinggi = detail/tepi/noise. (Inti kompresi JPEG adalah DCT.)

**G. Fitur kunci lokal & fitur terpelajari (deep features)**
- **Keypoint descriptors**: SIFT/SURF/ORB — titik kunci lokal yang invarian terhadap skala/rotasi/pencahayaan, untuk pencocokan (matching) dan image retrieval; **HOG** untuk deteksi objek.
- **Fitur CNN**: aktivasi lapisan konvolusi sebagai representasi terpelajari (*representation learning*) — menggantikan rekayasa fitur manual pada sistem modern.

**H. Atribut kualitas citra**
- **Noise (SNR)**, blur/ketajaman, distorsi geometris — menentukan mutu fitur yang dapat diekstraksi.

### Tabel rangkum

| Tingkat | Fitur | Contoh metode | Penggunaan khas |
|---|---|---|---|
| Piksel | brightness, kontras, bit depth, resolusi | statistik dasar | perbaikan/normalisasi kualitas citra |
| Histogram | mean, varians, entropi | histogram equalization | enhancement, fitur global |
| Warna | momen & histogram warna | histogram HSV | image retrieval, klasifikasi |
| Tekstur | kontras, homogenitas, arah | GLCM, LBP, Gabor, wavelet | klasifikasi permukaan/pola |
| Bentuk | kontur, momen Hu, corner | Canny, Harris, momen | deteksi & pengenalan objek |
| Frekuensi | koefisien spektrum | FFT, DCT, wavelet | kompresi, tekstur, denoising |
| Kunci/deep | SIFT, HOG, fitur CNN | SIFT/ORB, CNN | matching, retrieval, klasifikasi modern |

### Mengapa fitur penting (kaitan dengan pengenalan pola, Soal 3)

Tahap ekstraksi fitur memetakan citra → **vektor fitur** yang menjadi input pengklasifikasi. Mutu fitur menentukan seberapa terpisah antar kelas (*separability*): fitur yang baik membuat kelas mudah dipisahkan; fitur yang buruk tidak dapat diselamatkan oleh pengklasifikasi mana pun (*garbage in, garbage out*). Itulah sebabnya ekstraksi fitur adalah jantung pipeline pengenalan pola citra.

---

## References

1. Jurafsky & Martin, *Speech and Language Processing*, 3rd ed. draft (Stanford) — grammar L1 (S → NP VP, NP → Det Nominal, Nominal → Nominal PP, VP → VP PP, beserta leksikon Det/Noun/Verb/Prep/Proper-Noun) dan pembahasan parsing top-down vs bottom-up, backtracking, rekursi kiri, serta ambiguitas penempatan PP (bab Context-Free Grammars and Constituency Parsing).
2. Russell & Norvig, *Artificial Intelligence: A Modern Approach* — inferensi pada sistem berbasis aturan (forward/backward chaining).
3. Giarratano & Riley, *Expert Systems: Principles and Programming* — siklus match–fire forward chaining dan conflict set.
4. Bishop, *Pattern Recognition and Machine Learning*; Duda, Hart & Stork, *Pattern Classification* — definisi, pipeline, dan domain aplikasi pengenalan pola.
5. Gonzalez & Woods, *Digital Image Processing* — sampling/kuantisasi, resolusi, histogram, tekstur, dan momen citra.
6. Verifikasi numerik: trace forward chaining (Soal 1) dan kedua parse tree (Soal 2) diperiksa dengan skrip Python lokal — rule-chainer sederhana dan parser recursive-descent atas grammar yang sama. Hasil: K tercapai pada siklus ke-3 (aturan yang terpakai R-3, R-4, R-5, R-6, R-9, R-10); kalimat memiliki tepat 2 parse lengkap.

---

*Model answers prepared for revision; soal mengikuti transkripsi `UAS - Kecerdasan Artifisial - KOM A - 2024.md` (label cetak asli: 1, 3, 4, 5).*