Mục tiêu
Cung cấp cho sinh viên các kiến thức nền tảng về lý thuyết tập hợp, các phép tính tổ hợp, lôgic toán, đại số Boole và lý thuyết đồ thị và một số thuật toán cơ bản để sinh viên có thể tiếp thu các môn học khác của ngành CNTT.
Nội dung
Lý thuyết tổ hợp gồm mở đầu, bài toán đếm, bài toán tồn tại, bài toán liệt kê, bài toán tối ưu tổ hợp. Lý thuyết đồ thị gồm các khái niệm cơ bản của lý thuyết đồ thị, biểu diễn đồ thị trên máy tính, tìm kiếm trên đồ thị, đồ thị Euler và đồ thị Hamilton, cây và liệt kê cây. Logic toán.
Giáo trình
Nguyễn Tô Thành - Nguyễn Đức Nghĩa, Toán rời rạc, Nhà xuất bản Giáo dục
Tài liệu tham khảo
Kenneth H. Rosen, Toán rời rạc ứng dụng trong tin học, Người dịch: Phạm Văn Thiều - Đặng Hữu Thịnh, Nhà xuất bản Giáo dục
Phân bố thời lượng
|
Nội dung
(Tên chương)
|
Tổng lượng /thời gian /chương
|
Phân bố
|
|
Lý thuyết
|
Bài tập
|
Thảo luận (xêmina)
|
Kiểm tra có đánh giá
|
Ghi chú
|
|
Phần 1
Lý thuyết tổ hợp
|
18
|
8
|
10
|
|
|
|
|
Phần 2
Lý thuyết đồ thị
|
18
|
10
|
8
|
|
|
|
|
Phần 3
Logic toán và đại số Boole
|
9
|
5
|
4
|
|
|
|
|
Tổng cộng
|
45
|
23
|
22
|
|
1
|
|
Nội dung chi tiết
PHẦN 1: LÝ THUYẾT TỔ HỢP
CHƯƠNG I. MỞ ĐẦU
1.2. Nhắc lý thuyết tập hợp
1.2. Sơ lược về Lý thuyết tổ hợp
1.3. Nguyên lý cộng, nguyên lý nhân
1.4. Các cấu hình tổ hợp đơn giản
1.5. Các cấu hình tổ hợp suy rộng
CHƯƠNG II. BÀI TOÁN ĐẾM
2.1. Giới thiệu bài toán
2.2. Qui về các bài toán đơn giản
2.3. Nguyên lý bù trừ
2.4. Công thức truy hồi
CHƯƠNG III. BÀI TOÁN TỒN TẠI
3.1. Nguyên lý Dirichlet
3.2. Phương pháp phản chứng
3.3. Hệ đại điện phân biệt
CHƯƠNG IV. BÀI TOÁN LIỆT KÊ
4.1. Phương pháp sinh
4.2. Thuật toán quay lui
CHƯƠNG V. BÀI TOÁN TỐI ƯU
5.1. Các thuật toán duyệt
5.2. Thuật toán nhánh cận
5.3. Bài toán lập lịch gia công trên hai máy
Phần 2: LÝ THUYẾT ĐỒ THỊ
CHƯƠNG I. CÁC KHÁI NIỆM CƠ BẢN
1.1. Định nghĩa đồ thị
1.2. Các thuật ngữ cơ bản
1.3. Đường đi, chu trình, đồ thị lien thông
CHƯƠNG II. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
2.1. Ma trận kề, ma trận trọng số
2.2. Danh sách cạnh (cung)
2.3. Danh sách kề
CHƯƠNG II. CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ
3.1. Tìm kiếm theo chiều rộng
3.2. Tìm kiếm theo chiều sâu
3.3. Tìm đường đi và kiểm tra tính liên thông
CHƯƠNG IV. ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMINTON
4.1. Đồ thi Euler
4.2. Đồ thị Haminton
CHƯƠNG V. CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
5.1. Cây và tính chất của cây
5.2. Cây khung của đồ thị
5.3. Bài toán cây khung nhỏ nhất
CHƯƠNG VI. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
6.1. Các khái niệm mở đầu
6.2. Đường đi ngắn nhất xuất phát từ một đỉnh
6.3. Thuật toán Dijkstra
6.4. Đườgn đi ngắn nhất giữa tất cả các cặp đỉnh
PHẦN 3: LOGIC TOÁN VÀ ĐẠI SỐ BOOLE
CHƯƠNG I. LOGIC MỆNH ĐỀ
1.1.Mệnh đề và các phép toán trên mệnh đề
1.2. Biểu thức logic
1.3. Sự tương đương của mệnh đề logic
1.4. Các dạng chuẩn tắc. Tìm dạng chuẩn tắc của một công thức
1.5. Các qui tắc suy luận logic
CHƯƠNG II. LOGIC VỊ TỪ
2.1. Vị từ và các phép toán trên vị từ
2.2. Các lượng từ tồn tại, với mọi
CHƯƠNG III. ĐẠI SỐ BOOLE
3.1. Biểu thức Boole và hàm Boole
3.2. Tính đầy đủ của các phép toán cơ bản
3.3. Tối thiểu hoá hàm Boole
3.4. Tối thiểu hoá sơ đồ mạch
Liên hệ
Khoa Công nghệ Thông tin
Trường Đại học UTM, tòa nhà N3, Hồ Tùng Mậu, Mai dịch, Cầu giấy, Hà nội
Điện thoại: (84-4) - 37632890, máy lẻ: 471. Fax: (84-4) -37632893