Bài giảng Lý thuyết tính toán: Bài 10 - Phạm Xuân Cường
lượt xem 2
download
Bài giảng Lý thuyết tính toán: Bài 10 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về định nghĩa giải thuật; khái niệm định nghĩa giải thuật; bài toán của Hilbert; luận đề Church-Turing;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Lý thuyết tính toán: Bài 10 - Phạm Xuân Cường
- LÝ THUYẾT TÍNH TOÁN BÀI 10: Định nghĩa giải thuật Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@tlu.edu.vn
- Nội dung bài giảng 1. Khái niệm 2. Bài toán của Hilbert 3. Luận đề Church-Turing 1
- Khái niệm
- Khái niệm • 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) 2
- Bài toán của Hilbert
- Bài toán của Hilbert • 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 Một nghiệm của đa thức là bộ các giá trị x, y, z sao cho đa thức có giá trị bằng 0 x = 5, y = 3, z = 0 • 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 3
- Bài toán của Hilbert • 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 4
- Luận đề Church-Turing
- Luận đề Church-Turing Giải thuật ≡ Máy Turing Các cách để mô tả giải thuật: • Đặc tả hình thức - 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ả - Nội dung của băng nhớ - Cách thức biểu diễn dữ liệu - Cách hoạt động của đầu đọc • Đặc tả mức cao (High-level specification) Sử dụng văn xuôi để mô tả (Bỏ qua các chi tiết thực thi) - Mã giả (Pseudo-code) 5
- 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? 1 2 3 4 → Ta đưa về bài toán đoán nhận ngôn ngữ: A = {| G là một đồ thị liên thông } → Ta cần đưa ra một máy Turing đoán nhận A 6
- Ví dụ (2) • Biểu diễn đồ thị G thành một ngôn ngữ Ví dụ: G = ({1,2,3,4},{(1,2),(1,3),(1,4),(2,3)}) → = (1,2,3,4)((1,2),(1,3),(1,4),(2,3)) → Σ= {(, ), 1, 2, 3, 4,. . . } 7
- Ví dụ (3) Mô tả ở mức cao của TM quyết định A M = "Trên dữ liệu vào là mã hóa của đồ thị G: 1. Chọn nút đầu tiên của đồ thị G và đánh dấu nó 2. Lặp lại giai đoạn sau đến khi không còn nút nào được đánh dấu 3. 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 4. Kiểm tra tất cả các nút của G để xác định xem tất cả các nút đã được đánh dấu chưa • 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ỏ 8
- Ví dụ (4) Mô tả ở mức thực thi 1. Kiểm tra chuỗi đầu vào đã đúng là mã hóa của 1 đồ thị chưa • Kiểm tra danh sách nút - Kiểm tra từng ký tự 1 xem nó có bị lặp lại không • Kiểm tra danh sách cạnh - ... 2. Đánh dấu nút đầu tiên → Thêm dấu chấm vào nút đầu tiên 3. Duyệt danh sách nút để tìm ra nút không được đánh dấu • ... 9
- Ví dụ (5) = (1,2,3,4)((1,2),(1,3),(1,4),(2,3)) 1 2 3 4 10
- Ví dụ (6) 1 2 3 4 11
- Ví dụ (7) 1 2 3 4 12
- Ví dụ (8) 1 2 3 4 → Đồ thị liên thông 13
- Bài tập ôn tập KT Bài 1: Cho bộ chữ Σ= {0,1} a. Hãy đưa ra biểu đồ trạng thái của NFA đoán nhận ngôn ngữ tương đương với biểu thức chính quy Σ*0Σ b. Mô tả định nghĩa hình thức của NFA trên c. 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 d. Hãy mô tả ngôn ngữ mà NFA trên đoán nhận 14
- Bài tập ôn tập KT Bài 2: Cho ngôn ngữ L = {an b n c m d m | n,m > 0}. Hãy chứng minh L là không phi ngữ cảnh. Bài 3: Cho ngôn ngữ L = {ai b j c k | k = i + j; i, j, k ≥ 0} a. Hãy đưa ra biểu đồ trạng thái cho máy Turing quyết định L b. Hãy đưa ra lịch sử tính toán trên TM ở phần a với chuỗi aabbcccc 15
- Questions? 15
CÓ THỂ BẠN MUỐN DOWNLOAD
-
lý thuyết tính toán
0 p | 112 | 93
-
Bài giảng Lý thuyết xác suất và thống kê toán - Chương 1: Khái niệm cơ bản của lý thuyết xác suất
69 p | 27 | 5
-
Bài giảng Lý thuyết xác suất thống kê toán - Chương 1: Biến cố - Các công thức tính xác suất
58 p | 73 | 3
-
Bài giảng Lý thuyết tính toán: Bài 11 - Phạm Xuân Cường
21 p | 22 | 3
-
Bài giảng Lý thuyết tính toán: Bài 9 - Phạm Xuân Cường
38 p | 19 | 2
-
Bài giảng Lý thuyết tính toán: Bài 8 - Phạm Xuân Cường
24 p | 23 | 2
-
Bài giảng Lý thuyết tính toán: Bài 13 - Phạm Xuân Cường
21 p | 25 | 2
-
Bài giảng Lý thuyết tính toán: Bài 6 - Phạm Xuân Cường
30 p | 19 | 2
-
Bài giảng Lý thuyết tính toán: Bài 5 - Phạm Xuân Cường
18 p | 29 | 2
-
Bài giảng Lý thuyết tính toán: Bài 14 - Phạm Xuân Cường
35 p | 19 | 2
-
Bài giảng Lý thuyết tính toán: Bài 3 - Phạm Xuân Cường
30 p | 17 | 2
-
Bài giảng Lý thuyết tính toán: Bài 2 - Phạm Xuân Cường
26 p | 27 | 2
-
Bài giảng Lý thuyết tính toán: Bài 1 - Phạm Xuân Cường
32 p | 25 | 2
-
Bài giảng Lý thuyết tính toán: Bài 12 - Phạm Xuân Cường
5 p | 19 | 2
-
Bài giảng Lý thuyết tính toán: Bài 7 - Phạm Xuân Cường
27 p | 40 | 1
-
Bài giảng Lý thuyết tính toán: Bài 4 - Phạm Xuân Cường
29 p | 28 | 1
-
Bài giảng Lý thuyết tính toán: Bài mở đầu - Phạm Xuân Cường
7 p | 45 | 1
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn