Tính khả tính

Các Khái Niệm trong Khoa Học Máy Tính

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Tính khả tính là gì?

Bài toán khả tính

  • Tồn tại thuật toán: Có quy trình rõ ràng.
  • Thời gian hữu hạn: Cho ra kết quả sau số bước hữu hạn.

Bài toán không khả tính

  • Không tồn tại thuật toán: Không giải được cho mọi đầu vào.
  • Tính toán vô hạn: Có thể không bao giờ kết luận.
1 Các bài toán không khả tính có thể trở nên khả tính khi ta tìm được thuật toán và/hoặc làm cho thuật toán đã biết kết thúc trong thời gian hữu hạn.
Các Khái Niệm trong Khoa Học Máy Tính

Máy tự động

Định nghĩa Máy tự động

  • Máy tưởng tượng
  • Giúp hiểu cách tính toán vận hành
  • Có các trạng thái
  • Có quy tắc chuyển trạng thái

Hình đèn giao thông như phép ẩn dụ cho máy tự động

Các Khái Niệm trong Khoa Học Máy Tính

Máy tự động hữu hạn (FA)

Máy tự động hữu hạn (FA)

  • Máy đơn giản
  • Số trạng thái cố định
  • Không có bộ nhớ ngoài trạng thái hiện tại

Hình đèn giao thông và các trạng thái như phép ẩn dụ cho Máy tự động hữu hạn

Các Khái Niệm trong Khoa Học Máy Tính

Máy tự động đẩy xuống (PDA)

Máy tự động đẩy xuống (PDA)

  • Mạnh hơn
  • Có các trạng thái
  • Có bộ nhớ ngăn xếp để quyết định phức tạp hơn

Hình đèn giao thông và các trạng thái như phép ẩn dụ cho Máy tự động đẩy xuống

Các Khái Niệm trong Khoa Học Máy Tính

Tóm tắt

Máy tự động hữu hạn (FA)

  • Hữu ích cho tác vụ đơn giản

Máy tự động đẩy xuống (PDA)

  • Mạnh hơn cho bài toán phức tạp

Tầm quan trọng

  • Nếu mô hình hóa bài toán bằng máy tự động, TA có thể triển khai thuật toán để giải
Các Khái Niệm trong Khoa Học Máy Tính

Ayo berlatih!

Các Khái Niệm trong Khoa Học Máy Tính

Preparing Video For Download...