Trường DH Tự Nhiên

Trường Đại học Khoa học Tự Nhiên
Khoa CNTT

ĐỀ CƯƠNG ÔN THI TUYỂN SINH SAU ĐẠI HỌC
MÔN CƠ BẢN: TOÁN RỜI RẠC (Số tiết: 45 tiết)
(Môn cơ bản dành cho chuyên ngành Khoa học máy tính, Hệ thống thơng tin)

1. Cơ sở Logic.
1.1. Phép tính mệnh đề. Các phép nối. Dạng mệnh đề. Các qui luật logic.
1.2. Qui tắc suy diễn : mô hình suy diễn, các qui tắc suy diễn, phản ví dụ.
1.3. Vị từ : các phép nối trên vị từ. Lượng từ.
1.4. Nguyên lý qui nạp.
2. Lý thuyết Tổ hợp
2.1. Tập hợp. Ánh xạ.
2.2. Bài toán đếm. Nguyên lý cộng và nguyên lý nhân. Tích Descartes.
2.3. Giải tích tổ hợp, số đơn ánh giữa hai tập hợp hữu hạn.
2.4. Nguyên lý chuồng bồ câu (Nguyên lý Dirichlet).
2.5. Hệ thức đệ qui (công thức truy hồi). Hệ thức đệ qui tuyến tính cấp hai với hệ số hằng
3. Quan hệ
3.1. Quan hệ, quan hệ chiếu.
3.2. Quan hệ tương đương. Phép đồng dư modulo n, các phép toán trên Zn .
3.3. Thứ tự. Biểu đồ Hasse.
4. Hàm Bool (Hàm đại số logic)
4.1. Đại số Bool.
4.2. Hàm Bool. Từ đơn và từ tối tiểu. Dạng nối rời chính tắc (Dạng tuyển chuẩn tắc)
4.3. Mạng các cổng. Công thức đa thức tối tiểu (Dạng tuyển tối tiểu)
4.4. Phương pháp biểu đồ Karnaugh để tìm công thức đa thức tối tiểu.
5. Lý thuyết đồ thị
5.1. Các khái niệm cơ bản. Đường đi, chu trình. Đồ thị liên thông.
5.2. Biễu diễn ma trận của một đồ thị (ma trận kề)
5.3. Bài toán đường đi ngắn nhất.
5.4. Đường đi Euler. Đường đi Hamilton.
6. Cây
6.1. Định nghĩa và tính chất.
6.2. Cây có hướng. Thứ tự duyệt.
6.3. Đường đi trong và đường đi ngoài.
6.4. Ứng dụng

Tài liệu tham khảo
1. K.Rosen, Discrete mathematics and its Applications, McGrawHill Book Co, 1991
2. R.P.Grimaldi, Addison-Wesley, Discrete and Combinatorial Mathematics, 1994.
3. Nguyễn Hữu Anh, Toán rời rạc, Nhà xuất bản Giáo Dục, 1999
4. K.Ross , Discrete mathematics
5. J. Vélu, Dunod, Méthodes mathématiques pour l’informatique, 1989.
6. Hoàng Tụy, Đồ thị hữu hạn và các ứng dụng trong vận trù học, NXB KH Xã hội Hà Nội, 1964
7. Phan Đình Diệu, Lý thuyết Automat hữu hạn và thuật toán, NXB ĐHTHCH, Hà Nội, 1977.

ĐỀ ÔN TẬP TUYỂN SINH SAU ĐẠI HỌC
MÔN CƠ SỞ: TIN HỌC CƠ SỞ (45 tiết)
(Môn cơ sở dành cho chuyên ngành Khoa học máy tính)

1. Cơ sở lập trình
Các cấu trúc điều khiển cơ bản
Hàm và cơ chế truyền tham số
- Các loại tham số
- Biến cục bộ
- Hiệu ứng lề
Lập trình có cấu trúc
- Chất lượng của một chương trình (tính đúng đắn, độ phức tạp, khả năng tái sử dụng, dễ đọc, dễ bảo trì)
- Việc tổ chức mã nguồn chương trình: hàm và các đơn thể mã nguồn
Lập trình đệ qui
- Kỹ thuật giải bài toán bằng phương pháp đệ qui
- Điều kiện dừng khi viết chương trình đệ qui
- Phân loại các chương trình đệ qui
- Các thuật toán đệ qui thông dụng: tính toán dãy truy hồi, quay lui, chia để trị
- Tính hiệu quả của chương trình đệ qui và những ví dụ về cải tiến cách viết chương trình (cũng dùng đệ qui nhưng hiệu quả hơn hoặc là không dùng đệ qui)
Lập trình hướng đối tượng
- Khái niệm về đối tượng, lớp, phương thức
- Những kỹ thuật cơ bản về lập trình hướng đối tượng (kế thừa, phương thức ảo và tính đa hình, lớp trừu tượng)
- Vận dụng kỹ thuật hướng đối tượng trong việc lập trình giải quyết các bài toán thông dụng

2. Cấu trúc dữ liệu
Các cấu trúc dữ liệu cơ bản và những kiểu dữ liệu trừu tượng
- Danh sách liên kết
- Ngăn xếp (stack), hàng đợi (queue), hàng đợi có độ ưu tiên (priority queue)
Cây
- Các tính chất tổng quát
- Cây nhị phân và phương pháp duyệt, các thao tác xử lý
- Cây nhị phân tìm kiếm cân bằng (cây AVL, cây đỏ-đen)
Đồ thị
- Các phương pháp biểu diễn và lưu trữ đồ thị
- Các phương pháp duyệt và thao tác trên đồ thị

3. Thuật toán và khái niệm về độ phức tạp tính toán
Thuật toán và cài đặt thuật toán
Một số thuật toán thông dụng
- Sắp xếp, tìm kiếm
- Thuật toán đồ thị
- Thuật toán quy hoạch động
Khái niệm về độ phức tạp tính toán và kỹ thuật ước lượng sơ bộ
- Kích thước bài toán
- Ký hiệu O-lớn (Big-O) và ý nghĩa
- Ước lượng các phép toán đóng vai trò chủ yếu trong một thuật toán
- Ví dụ về ước lượng một vài thuật toán thông dụng
Tận dụng kỹ thuật cài đặt để tối ưu hóa thuật toán (nhằm mục đích cải tiến độ phức tạp tính toán): các ví dụ cụ thể và áp dụng.

Tài liệu tham khảo:
1. Robert Sedgewick, Algorithms, Addison-Wesley Longman, 1988.
(Có bản dịch tiếng Việt – Nhà xuất bản Khoa học và Kỹ thuật)
2. Mark Allen Weiss, Data structures & Algorithm Analysis in C++, Addison-Wesley, 1999.
3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, The MIT Press, McGraw-Hill, 2001 (Second Edition).
(Có bản dịch tiếng Việt – Nhà xuất bản Thống kê)