TAILIEUCHUNG - Lý thuyết ngôn ngữ hình thức và ôtômát - Phụ lục

Có những bài toán thực tế mà cho đến nay vẫn chưa xây dựng được thuật toán hiệu quả để giải (đó là thuật toán có độ phức tạp tính toán là đa thức) và chứng minh được mức độ khó thực chất của nó. | PHỤ LỤC CÁC LỚP P VÀ NP VÀ LỚP CÁC BÀI TOÁN NP-ĐẦY ĐỦ Có những bài toán thực tế mà cho đến nay vẫn chưa xây dựng được thuật toán hiệu quả để giải đó là thuật toán có độ phức tạp tính toán là đa thức và chứng minh được mức độ khó thực chất của nó. Trong số các bài toán như vậy có thể kể ra các bài toán nổi tiếng sau Bài toán người du lịch Bài toán chu trình Hamilton Bài toán tô màu đồ thị Bài toán tìm đường đi đơn dài nhất của đồ thị. Ta có thể quy lỗi cho việc thiết kế và phân tích thuật toán hay lý thuyết độ phức tạp hay không Liệu trên thực tế có thuật toán hiệu quả để giải quyết các bài toán này không Trong phần này ta sẽ có một kết quả nổi tiếng mỗi thuật toán hiệu quả để giải một trong số các bài toán vừa kể trên sẽ cũng cho ta thuật toán hiệu quả để giải tất cả các bài toán còn lại. Ta chưa biết những bài toán này là dễ hay khó giải nhưng ta biết rằng tất cả chúng có độ phức tạp như nhau. Ý nghĩa thực tế quan trọng của các bài toán này là đảm bảo rằng mỗi một bài toán này là đối tượng của những cố gắng tìm thuật toán hiệu quả để giải. 1. LỚP P VÀ LỚP NP. . Định nghĩa Cho M là một máy Turing. Hàm T n được gọi là độ phức tạp tính toán của M nếu với mọi xâu vào 0 có độ dài n thì đều tồn tại một dãy hình trạng có nhiều nhất là T n bước đoán nhận 0 ở đây T n là một số nguyên dương . Nếu có một xâu nào đó có độ dài n mà máy Turing không dừng thì đối với n đó T n không xác định. . Định nghĩa Lớp P là lớp các ngôn ngữ được đoán nhận bởi máy Turing đơn định và độ phức tạp tính toán là đa thức. Có thể phát biểu một cách khác là một bài toán được coi là thuộc lớp P nếu tồn tại một thuật toán đa thức để giải nó. Người ta nói rằng những bài toán thuộc lớp P là dễ. . Chú ý Theo quan điểm toán học lớp P là rất tự nhiên. Điều này thấy được từ việc nó là bất biến cao đối với mô hình tính toán được dùng. Chẳng hạn các máy Turing M1 với nhiều băng là nhanh hơn các máy Turing thông thường tức là độ phức tạp tính toán của chúng nhận các giá trị nhỏ hơn. Tuy nhiên nếu độ

• Thư viện thông tin
• ngôn ngữ hình thức
• Lý thuyết ôtômát
• máy turing
• trình biên dịch
• ô tô mát hữu hạn
• Giáo trình Lý thuyết ngôn ngữ hình thức
• Lý thuyết ngôn ngữ hình thức và ô tô mát
• Lý thuyết ngôn ngữ hình thức
• Ngôn ngữ hình thức và ô tô mát
• Khái niệm otô mát
• Ngôn ngữ phi ngữ cảnh
• Lí thuyết Ngôn ngữ hình thức
• Bài giảng Lí thuyết Ngôn ngữ hình thức
• Lí thuyết Ngôn ngữ hình thức và ôtômat
• Lý thuyết ngôn ngữ
• Ngôn ngữ lập trình
• Văn phạm hình thức
• Kỹ thuật lập trình
• Đề thi học kỳ
• Đề thi Lý thuyết ngôn ngữ hình thức
• Bài tập Lý thuyết ngôn ngữ hình thức
• Lý thuyết ngôn ngữ hình thức và ôtômat
• Lý thuyết ngôn ngữ hình thức và atomat
• Bài giảng Ngôn ngữ hình Đại cương về ngôn ngữ
• Biểu diễn ngôn ngữ
• Hệ viết lại
• Phép toán trên tập hợp
• Lí thuyết ngôn ngữ hình thức và ôtômát
• Lí thuyết ngôn ngữ
• Ngôn ngữ chính quy
• Ôtômát hữu hạn
• Lớp ngôn ngữ chính quy
• Bài giảng Trị liệu ngôn ngữ
• Trị liệu ngôn ngữ
• Đánh giá ngôn ngữ
• Các dạng ngôn ngữ
• Các hình thức ngôn ngữ
• Trẻ bị rối loạn ngôn ngữ
• Âm vị học ngữ pháp
• Bài giảng Ngôn ngữ hình thức
• Ngôn ngữ hình thức và ôtômát
• Phép toán trên từ
• Phép toán trên ngôn ngữ
• Dạng chuẩn Chomsky
• Văn phạm phi ngữ cảnh
• Otomat đẩy xuống
• Chương trình dịch
• Ngôn ngữ học
• vai trò của ngôn ngữ
• ngôn ngữ và sự chắc chắn
• ngôn ngữ và nhận thức
• tri thức và ngôn ngữ
• tìm hiểu ngôn ngữ học
• Automat hữu hạn
• Bài giảng Ôtômát và ngôn ngữ hình thức
• Phân cấp văn phạm
• Cấu tạo Ôtômát
• Xây dựng văn phạm cho ngôn ngữ
• Phép toán trên xâu
• Ngôn ngữ lập trình Pascal
• Văn phạm chính quy
• Bài toán bao hàm ngôn ngữ
• Giáo trình Ôtômát và ngôn ngữ hình thức
• Ngôn ngữ sinh
• Văn phạm tương đương
• Phân loại ngôn ngữ
• Phương pháp biểu diễn ôtômát
• Ôtômát đẩy xuống
• Suy dẫn phi ngữ cảnh
• Cây suy dẫn
• Tìm về cội nguồn ngôn ngữ
• Cội nguồn ngôn ngữ
• Hình thức gốc của ý thức
• Động tác chỉ dẫn
• Cội nguồn ý thức
• Ngôn ngữ Ý thức
• Ngôn ngữ hỗn hợp