De Cuong Trr

1. Tài liệu học tập: 1. Kenneth H. Rosen: Toán học rời rạc, bản dịch của NXB KH&KT 2000. 2. Kenneth A. Ross: Charles R. B. Wright: Discrete Mathematics. Pearson Education In. 2003. 3. Vũ Đình Hòa: Lí thuyết tổ hợp và các bài toán ứng dụng, Nhà xuất bản Giáo dục, Hànội 2002, 4. Vũ Đình Hòa: Toán rời rạc, Giáo trình hệ dạy học từ xa, NXB ĐHSP HN 2003. 5. Vũ Đình Hòa: Lý thuyết đồ thị, Giáo trình các trường cao đẳng sư phạm, NXB ĐHSP HN 2006.

2. Tiêu chuẩn đánh giá sinh viên: Nắm chắc được lý thuyết, vận dụng giải được bài tập và đặc biệt nắm vững các thuật toán để áp dụng vào lập trình. 3. Thang điểm: thang điểm 10. 4. Mục tiêu của học phần: 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. 5. Nội dung chi tiết học phần. CHƯƠNG 1: TẬP HỢP, ÁNH XẠ. (9 LT: 3 BT )

1.1.

Khái niệm tập hợp và các cách biểu diễn.

1.2.

Tập hợp con và tập hợp bằng nhau.

1.3.

Các phép toán của tập hợp

1.4.

Ánh xạ và hàm số

1.5.

Lực lượng, tập hợp đếm được và tập hợp không đếm được.

CHƯƠNG 2: MỘT SỐ CÁC CÔNG THỨC TÍNH TỔ HỢP. (12 LT: 4 BT)

2.1.

Một số công thức cơ sở

2.2.

Dãy k phần tử có lặp (chỉnh hợp có lặp)

2.3.

Dãy k phần tử không có lặp (chỉnh hợp không lặp)

2.4.

Hoán vị và hoán vị vòng quanh

2.5.

Tổ hợp

2.6.

Xếp có lặp với tần số cho trước (chỉnh hợp với tần số xuất hiện cho trước)

2.7.

Hai quy tắc tính toán cơ bản: quy tắc nhân và quy tắc cộng

2.8.

Công thức tổ hợp trong tập hợp

2.9.

Nhị thức Newton và khai triển đa thức

CHƯƠNG 3: LÔGIC MỆNH ĐỀ VÀ ĐẠI SỐ BOOLE (15 LT: 5BT)

3.1.

Mệnh đề hình thức

3.2.

Liên mệnh đề lôgic và bảng giá trị chân lý

3.3.

Các phép toán lôgic

3.4.

Biểu thức lôgic và tương đương lôgic

3.5.

Vị ngữ và lượng tử

3.6.

Các luật suy diễn

3.7.

Đệ qui và phương pháp định nghĩa bằng đệ qui

3.8.

Các phép toán bit

3.9.

Biểu thức Boole và hàm Boole

3.10. Các hằng đẳng thức của đại số Boole 3.11. Luật đối ngẫu 3.12. Biểu diễn một hàm số Boole qua biểu thức Boole 3.13. Sơ đồ mạch và đại số Boole CHƯƠNG 4: LÝ THUYẾT ĐỒ THỊ (9 LT : 3 BT)

4.1.

Định nghĩa đồ thị và ví dụ

4.2.

Phân loại đồ thị

4.3.

Biểu diễn phẳng của đồ thị và đẳng cấu

4.4.

Các yếu tố cơ bản của đồ thị

4.5.

Đồ thị đầy đủ, đồ thị đều, đồ thị lưỡng phân, cây, đồ thị phẳng

4.6.

Một số thuật toán trong đồ thị có trọng số (Dijkstra, Prim, Kruska)

4.7.

Đồ thị có hướng và thuật toán Ford-Fulkerson