- BÀI 10: Định nghĩa giải thuật. - Bài toán của Hilbert. - Một giải thuật là tập các lời chỉ dẫn đơn giản để thực hiện một vài nhiệm vụ nào đó. - Giải thuật = thủ tục = công thức. - Giải thuật đóng vai trò quan trọng cho rất nhiều nhiệm vụ khác nhau. - Ví dụ: tìm số nguyên tố, tìm ước số chung lớn nhất. - Trước thế kỉ XX, chưa tồn tại khái niệm giải thuật (các khái niệm mang tính trực giác về giải thuật). - Năm 1900 nhà toán học David Hilbert đưa ra một bài toán có liên quan đến giải thuật. - Xét bài toán đa thức:. - Ví dụ: 6x 3 yz 2 + 3xy 2 − x 3 − 10. - Bài toán của Hilbert là hãy đưa ra 1 giải thuật để kiểm tra 1 đa thức có nghiệm nguyên hay không. - Cần phải có định nghĩa về giải thuật mới có thể giải quyết được bài toán trên. - Alonzo Church và Alan Turing đã đưa ra một phép tính Lamda (λ) để định nghĩa các giải thuật tương đương. - Mối liên hệ giữa khái niệm không hình thức của giải thuật và định nghĩa chính xác → Luận đề Church-Turing. - Giải thuật ≡ Máy Turing. - Các cách để mô tả giải thuật:. - Mô tả các trạng thái, bộ chữ, hàm chuyển dịch → Là mô tả mức thấp nhất, đầy đủ nhất. - Đặc tả thực thi (Implementation-level specification) Sử dụng văn xuôi để mô tả. - Ví dụ. - Bài toán: Cho đồ thị G= (V,E) hãy cho biết đồ thị có liên thông hay không?. - A = {<G>| G là một đồ thị liên thông. - Ví dụ (2). - Biểu diễn đồ thị G thành một ngôn ngữ. - Ví dụ: G . - Ví dụ (3). - Mô tả ở mức cao của TM quyết định A. - là mã hóa của đồ thị G:. - Chọn nút đầu tiên của đồ thị G và đánh dấu nó. - Với mỗi nút trong đồ thị G, đánh dấu nó nếu tồn tại một cạnh đi từ nó đến 1 nút đã đánh dấu. - Nếu tất cả các nút đã được đánh dấu → Chấp thuận. - Nếu còn nút chưa được đánh dấu → Bác bỏ. - Ví dụ (4). - Mô tả ở mức thực thi. - Kiểm tra chuỗi đầu vào đã đúng là mã hóa của 1 đồ thị chưa. - Duyệt danh sách nút để tìm ra nút không được đánh dấu. - Ví dụ (5). - Ví dụ (6). - Ví dụ (7). - Ví dụ (8). - Đồ thị liên thông. - Mô tả định nghĩa hình thức của NFA trên. - Hãy đưa ra biểu đồ trạng thái của DFA tương đương với NFA trên và mô tả định nghĩa hình thức. - Hãy mô tả ngôn ngữ mà NFA trên đoán nhận
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt