No Image

Số người trực tuyến

No Image
Lý thuyết tính toán PDF In E-mail
27/07/2007
Người soạn:Th.s.Nguyễn Thị Thu Hương
1. Tên học phần : Nhập môn lý thuyết tính toán
2. Số đơn vị học trình: 4 đvht
3. Trình độ : sinh viên năm thứ 3 chuyên ngành Công nghệ Thông tin
4. Điều kiện tiên quyết:
Học qua các học phần :Toán rời rạc, Cấu trúc dữ liệu và giải thuật, Điện tử số.
5. Mô tả vắn tắt nội dung học phần:
Cung cấp những kiến thức cơ bản về mô hình tính toán lý thuyết , ngôn ngữ hình thức và lý thuyết độ phức tạp tính toán. Máy tính không bộ nhớ (các mạch logic). Máy tính có bộ nhớ . Máy hữu hạn trạng thái , máy truy cập ngẫu nhiên . Các loại văn phạm, đặc biệt là văn phạm phi ngữ cảnh
Máy Turing và khái niệm Turing tính được. Hàm đệ quy.Thuật toán . Bài toán quyết định. Tính giải được. Lý thuyết độ phức tạp tính toán . Lớp bài toán P và NP. Lớp bài toán NP đầy đủ và phép quy dẫn
6. Tài liệu học tập:
Giáo trình chính
§ Ngôn ngữ hình thức. Nguyễn Văn Ba. NXB Khoa học kỹ thuật - 2002
Tài liệu tham khảo
§ Models of Computation. Exploring the Power of Computing. J.E. Savage. Addison – Wesley. 2000.
§ Introduction to Automata Theory, Languages and Computation. J.E.Hopcroft, J.D. Ullman.Addison-Wesley. 1979
§ Formal Languages and their Relation to Automata . J.E.Hopcroft, J.D. Ullman.Addison-Wesley. 1970
§ The theory of Parsing, Translation and Compiling. J.E.Hopcroft, J.D. Ullman.Addison-Wesley. 1977
7. Mục tiêu của học phần:
Sinh viên nắm được các mô hình tính toán tổng quát, các khái niệm cơ bản về độ phức tạp tính toán, phương pháp chứng minh hình thức. Có khả năng minh hờa hoạt động của các mô hình đó bằng chương trình.
8. Nội dung chi tiết của học phần:
CHƯƠNG I . MỞ ĐẦU
I.1. Sơ lược lịch sử phát triển của khoa học tính toán
I.2. Cơ sở toán học
I.2.1.Các khái niệm của lý thuyết tập hợp
I.2.2. Các hệ đếm
I.2.3. Ngôn ngữ và xâu
I.2.4. Đồ thị và mối liên hệ với mạch logic
I.2.5. Hàm và tốc độ tăng của hàm
I.3. Các phương pháp chứng minh
I.3.1. Phương pháp phản chứng
I.3.2. Nguyên tắc Dirichlet
I.3.3. Phương pháp quy nạp toán học
CHƯƠNG II . CÁC MÔ HÌNH TÍNH TOÁN TỔNG QUÁT
II.1. Mạch logic
II.1.1. Các khái niệm cơ bản
II.1.2. Độ phức tạp mạch
II.2. Máy có bộ nhớ
II.2.1. Máy hữu hạn trạng thái
II.2.2. Máy truy nhập ngẫu nhiên
II.2.3. Máy Turing
CHƯƠNG III : ÔTÔMAT HỮU HẠN VÀ ÔTÔMAT ĐẨY XUờNG
III.1. Ôtômat hữu hạn
III.1.1. Ôtômat hữu hạn đơn định
III.1.2. Ôtômat hữu hạn không đơn định
III.1.3. Biểu thức chính quy
III.1.4. Bổ đề bơm
III.2. Ôtômat đẩy xuống
III.2.1. Ôtômat đẩy xuống không đơn định
III.2.2. Tương đương giữa hai dạng của ôtômat đẩy xuống
III.2.3. Ôtômat đẩy xuống đơn định
CHƯƠNG IV. VĂN PHẠM
IV.1. Văn phạm
IV.1.1. Định nghĩa hình thức
IV.1.2. Suy dẫn
IV.1.3. Ngôn ngữ sản sinh bởi văn phạm
IV.2. Văn phạm chính quy
IV.2.1. Định nghĩa
IV.2.2. Tương đương giữa văn phạm chính quy và ôtômat hữu hạn
IV.3. Văn phạm phi ngữ cảnh
IV.3.1. Định nghĩa
IV.3.2. Cây suy dẫn của văn phạm phi ngữ cảnh
IV.3.3. Tính đơn nghĩa của văn phạm phi ngữ cảnh
IV.3.4. Tương đương giữa văn phạm phi ngữ cảnh và ôtômat đẩy xuống
IV.3.5. Dạng chuẩn Chomsky
IV.3.6. Định lý “uvwxy”
IV.3.7. Giải thuật CYK
IV.3. Văn phạm cảm ngữ cảnh
IV.4. Văn phạm ngữ cấu
CHƯƠNG V : MÁY TURING VÀ HÀM ĐỆ QUY
V.1. Máy Turing
V.1.1. Máy Turing chuẩn đơn định
V.1.2. Dạng mã chuẩn của máy Turing
V.1.3. Tương đương giữa máy Turing và văn phạm ngữ cấu
V.1.4. Các dạng mở rộng của máy Turing
V.2. Hàm tính được bởi máy Turing
V.2.1. Máy Turing đảm nhiệm chức năng tính toán
V.2.2. Sự “thích dụng”
V.2.3. Hàm tính được bởi máy Turing
V.2.4. Hàm Turing- tính được
V.2.5. Luận đề Turing – Church
V.3. Hàm đệ quy
V.3.1. Phép hợp thành
V.3.2. Phép đệ quy nguyên thuỷ
V.3.3. Hàm đệ quy nguyên thuỷ
V.3.4. Phép cực tiểu hoá
V.3.5. Hàm đệ quy
V.3.6. Tương đương giữa hàm đệ quy và hàm Turing tính được
CHƯƠNG VI. LÝ THUYẾT ĐỘ PHỨC TẠP TÍNH TOÁN
VI.1. Bài toán quyết định
VI.1.1. Định nghĩa.
VI.1.2. Tính giải được.
VI.2.3. Một số bài toán quyết định không giải được.
VI.2. Phép quy dẫn
VI.3. Lớp bài toán P
VI.4. Lớp bài toán P đầy đủ
VI.5. Lớp bài toán NP
VI.6. Lớp bài toán NP đầy đủ
VI.7. Vấn đề P=NP ?
Cập nhật ( 04/10/2007 )
 
< Trước
No Image
No Image No Image No Image
Bản quyền thuộc về Trung tâm đào tạo Tài năng - Đại học Bách Khoa Hà nội