Komputabilitas

Konsep dalam Ilmu Komputer

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Apa itu komputabilitas?

Masalah Komputabel

  • Keberadaan Algoritma: Ada prosedur yang jelas.
  • Waktu Berhingga: Menghasilkan keluaran dalam langkah terbatas.

Masalah Tidak Komputabel

  • Tidak Ada Algoritma: Tidak bisa diselesaikan untuk semua masukan.
  • Perhitungan Tak Hingga: Mungkin tidak pernah selesai.
1 Masalah tidak komputabel dapat menjadi komputabel setelah kita menemukan algoritma dan/atau membuat algoritma yang ada selesai dalam waktu berhingga.
Konsep dalam Ilmu Komputer

Automata

Definisi Automata

  • Mesin imajiner
  • Membantu memahami cara kerja komputasi
  • Memiliki state
  • Memiliki aturan transisi antar state

Gambar lampu lalu lintas sebagai analogi yang merepresentasikan automata

Konsep dalam Ilmu Komputer

Finite Automata (FA)

Finite Automata (FA)

  • Mesin sederhana
  • Jumlah state tetap
  • Tidak ada memori selain state saat ini

Gambar lampu lalu lintas dan state sebagai analogi untuk Finite Automata

Konsep dalam Ilmu Komputer

Pushdown Automata (PDA)

Pushdown Automata (PDA)

  • Lebih kuat
  • Memiliki state
  • Memiliki memori berbasis stack untuk keputusan lebih kompleks

Gambar lampu lalu lintas dan state sebagai analogi untuk Pushdown Automata

Konsep dalam Ilmu Komputer

Ringkasan

Finite Automata (FA)

  • Berguna untuk tugas sederhana

Pushdown Automata (PDA)

  • Lebih kuat untuk masalah yang lebih kompleks

Pentingnya

  • Jika masalah dapat dimodelkan dengan automata, kita BISA membuat algoritma untuk menyelesaikannya
Konsep dalam Ilmu Komputer

Ayo berlatih!

Konsep dalam Ilmu Komputer

Preparing Video For Download...