Nội dung ôn tập môn Toán rời rạc DH Cần Thơ

ĐỀ CƯƠNG ÔN TẬP MÔN TOÁN
(30 tiết)
MỤC TIÊU

Hệ thống lại một số kiến thức quan trọng của các môn học cơ sở Toán cho Tin học
NỘI DUNG
I- Cơ sở lôgic (5 tiết)
1. Phép tính mệnh đề và vị từ
- Khái niệm về mệnh đề và vị từ
- Các phép tính cơ bản NOT - AND - OR
2. Quy tắc suy luận
- Quy tắc cộng
- Quy tắc rút gọn
- Quy tắc Modus Ponens
- Quy tắc Modus Tollens - Chứng minh phản chứng
- Tam đoạn luận
3. Nguyên lý quy nạp
- Nguyên lý quy nạp - Hệ tiên đề Peano
- Chứng minh quy nạp
II- Đại số bool (7 tiết)
1. Quan hệ thứ tự và tập hợp thứ tự
- Quan hệ thứ tự
- Tập hợp thứ tự - Sơ đồ Hasse
- Các phần tử đặc biệt trên một tập hợp thứ tự
2. Dàn (lattice) và đại số bool
- Định nghĩa dàn và đại số bool
- Các tính chất của dàn và đại số bool
3. Hàm bool
- Hàm bool n biến
- Đại số bool các hàm bool
- Dạng tuyển chuẩn tắc và dạng hội chuẩn tắc
4. Công thức tối tiểu của hàm bool
- Định nghĩa công thức tối tiểu của hàm bool
- Các phương pháp tìm công thức tối tiểu: Karnaugh, Consensus và Mc. Quine Cluskey
5. Hệ phương trình bool và hệ phủ tối tiểu
- Định nghĩa hệ phương trình bool
- Phương pháp giải hệ phương trình bool
- Bài toán phủ tối tiểu
III- Phép đếm (3 tiết)
1. Nguyên lý cộng, nguyên lý nhân và nguyên lý bù trừ
2. Giải tích tổ hợp
3. Nguyên lý Dirichlet
4. Công thức đệ quy
IV- Lý thuyết đồ thị (10 tiết)
1. Đại cương về đồ thị
- Định nghĩa và các thuật ngữ cơ bản về đồ thị
- Phân loại đồ thị
2. Đồ thị liên thông
- Khái niệm về liên thông, liên thông mạnh và liên thông yếu
- Giải thuật kiểm tra tính liên thông
3. Đường đi ngắn nhất (Shortest Path Problem)
- Bài toán đường đi ngắn nhất
- Giải thuật tìm đường đi ngắn nhất Dijkstra , Ford và Floyd
4. Cây khung có trọng lượng nhỏ nhất (Minimum Spanning Trees)
- Bài toán cây khung có trọng lượng nhỏ nhất
- Giải thuật tìm cây khung có trọng lượng nhỏ nhất Kruskal và Prim
5. Luồng cực đại trên mạng
- Bài toán luồng cực đại trên mạng
- Giải thuật xác định luồng cực đại trên mạng: Ford - Fulkerson
V- Số học (5 tiết)
1. Lý thuyết chia
- Phép chia hết và chia có dư
- Ước chung lớn nhất, bội chung nhỏ nhất
- Số nguyên tố và hợp số
2. Lý thuyết đồng dư
- Quan hệ đồng dư và các tính chất
- Phương trình đồng dư bậc nhất một ẩn
- Hệ phương trình đồng dư bậc nhất một ẩn

TÀI LIỆU THAM KHẢO
[1] Nguyễn Đức Nghĩa và Nguyễn Tô Thành- Toán rời rạc
Nhà xuất bản Giáo dục 1997
[2] Nguyễn Hữu Anh - Toán rời rạc
Nhà xuất bản Giáo dục 1999
[3] Khoa CNTT&TT - Bài giảng Toán rời rạc 1,2,3,4
Đại học Cần Thơ 2005
[4] Nguyễn Tiến Tài và Nguyễn Hữu Hoan - Số học
Nhà xuất bản Giáo dục 2001
[5] J. Vélu - Méthodes mathématiques pour l'informatique
Dunod 1989
[6] J. E. Munro - Discrete mathematic for computing
Thomas Nelson Australia 1992

ĐỀ CƯƠNG ÔN TẬP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT

PHẦN I. CẤU TRÚC DỮ LIỆU

I. Một số cấu trúc dữ liệu cơ sở
1. Ánh xạ (map), mảng (array)
2. con trỏ (pointer)
3. mẩu tin (record)
II. Kiểu dữ liệu trừu tượng (ADT)
1. Kiểu (type)
2. Kiểu dữ liệu trừu tượng (Abstract Data Type)
3. Hạng mục dữ liệu (Data item)
III. Danh sách (list), ngăn xếp (stack), hàng đợi (queue)
1. Danh sách
a. Kiểu dữ liệu trừu tượng danh sách
b. Cài đặt danh sách dựa trên mảng
c. Cài đặt danh sách dựa trên con trỏ
d. Danh sách liên kết đơn (Simple Linked Lists)
e. Danh sách liên kết kép (Double Linked Lists)
f. Danh sách liên kết vòng (Circular Linked Lists)
2. Ngăn xếp
a. Kiểu dữ liệu trừu tượng ngăn xếp
b. Cài đặt ngăn xếp dựa trên mảng
c. Cài đặt ngăn xếp dựa trên con trỏ
d. Cài đặt đệ quy
3. Hàng đợi
a. Kiểu dữ liệu trừu tượng hàng đợi
b. Cài đặt hàng đợi dựa trên mảng
c. Cài đặt hàng đợi dựa trên con trỏ
IV. Cây (tree)
1. Các định nghĩa và tính chất
2. Duyệt cây
3. Kiểu dữ liệu trừu tượng cây
4. Cài đặt cây dựa trên mảng
5. Cài đặt cây dựa trên con trỏ
V. Đồ thị (graph)
1. Các định nghĩa và tính chất
2. Cài đặt đồ thị
3. Duyệt đồ thị
VI. Tập hợp (set), tự điển (dictionary)
1. Tập hợp
a. Các định nghĩa và tính chất
b. Kiểu dữ liệu trừu tượng tập hợp
c. Cài đặt tập hợp bởi hàm đặc trưng (characteristic-function/bitmap/bit-vector)
d. Cài đặt tập hợp bởi danh sách
2. Tự điển
a. Các định nghĩa và tính chất
b. Kiểu dữ liệu trừu tượng tự điển
c. Cài đặt tự điển
d. Cây tìm kiếm và tự điển
VII. Băm (hashing)
1. Băm đóng
2. Băm mở
VIII. B-cây (B-tree)
1. Định nghĩa
2. Cài đặt B-cây


PHẦN II. GIẢI THUẬT

I. Kỹ thuật phân tích giải thuật
a. Sự cần thiết phải phân tích, đánh giá giải thuật.
b. Khái niệm độ phức tạp của giải thuật.
c. Phương pháp xác định độ phức tạp của giải thuật.
II. Các giải thuật sắp xếp
a. Các giải thuật sắp xếp đơn giản
b. QuickSort
c. HeapSort
III. Các kỹ thuật thiết kế giải thuật
a. Chia để trị (Divide and Conquer)
b. Quy hoạch động (Dynamic Programming)
c. Các thuật toán "tham ăn" (Greedy Algorithms)
d. Lần ngược (Backtracking)
e. Các thuật toán tìm kiếm địa phương (local Search Algorithms)
IV. Cấu trúc dữ liệu và giải thuật lưu trữ ngoài
a. Sắp xếp ngoài
b. Tập tin tuần tự
c. Tập tin bảng băm
d. Tập tin chỉ mục
e. Tập tin B-cây

Tài liệu tham khảo
1. Derick Wood - Data Structures, Algorithms and Performance – Addison-wesley Publishing Company - 1993
2. A Practical Introduction to Data Structures and Algorithm Analysis – Clifford A. Shaffer – Prentice Hall, Upper Saddle River, New Jersey – 1997
3. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman - Data Structures and Algorithms – Addison Wesley Publishing Company - 1982
4. William H. Murray, Chris H. Pappas - Data Structures with STL – Prentice Hall – 2001
5. Jacques Courtin, Irène Kowarski - Initiation à l'Algorithmique et aux Structures de données (volume 1, 2) – Dunod – 1995
6. Jeffrey H Kingston; Algorithms and Data Structures; Addison-Wesley; 1998.
7. Đinh Mạnh Tường; Cấu trúc dữ liệu & Thuật toán; Nhà xuất bản khoa học và kĩ thuật; Hà nội-2001.
8. Đỗ Xuân Lôi; Cấu trúc dữ liệu & Giải thuật; 1995.
9. Giáo trình Cấu trúc dữ liệu, khoa Công nghệ Thông tin, 2003
10. Giáo trình Giải thuật, khoa Công nghệ Thông tin, 2003
11. http://pauillac.inria.fr/algo/AofA/
12. http://www.cs.pitt.edu/~kirk/algorithmcourses/