CẤU TRÚC RỜI RẠC (DISCRETE STRUCTURES)

[Admin]

ĐỀ CƯƠNG CHI TIẾT

1. Tên học phần: CẤU TRÚC RỜI RẠC
(DISCRETE STRUCTURES)
2. Mã học phần: 2101011003
3. Số tín chỉ : 4(4,0,
4. Trình độ : Dành cho sinh viên năm thứ 1
5. Phân bố thời gian:
- Lên lớp : 60 tiết
- Thực tập phòng thí nghiệm: 0 tiết
- Thực hành: 0
- Tự học: 120 tiết
6. Điều kiện tiên quyết:
7. Mục tiêu của học phần:
Sau khi hoàn tất học phần này, sinh viên được trang bị kiến thức toán phục vụ chuyên ngành Tin học.
8. Mô tả vắn tắt nội dung học phần:
Số học trên các số nguyên. Phép chứng minh phản chứng và quy nạp. Lý thuyết tập hợp: quan hệ, hàm, lượng số, quan hệ thứ tự, dàn. Tổ hợp: phép đếm, nguyên lý cộng, nhân, chia, bao gồm và loại trừ. Đếm bằng hàm sinh. Nhóm các phép hoán vị. Lý thuyết đồ thị: có hướng, vô hướng, có trọng số, cây, duyệt cây, sự đẳng cấu của đồ thị. Logic mệnh đề: ngôn ngữ, công thức, biễu diễn công thức, các tiên đề, các quy tắc ngữ nghĩa, dạng chuẩn tắc trong logic mệnh đề. Logic vị từ: ký hiệu, công thức, ngữ nghĩa, dạng chuẩn tắc của công thức logic vị từ.
9. Nhiệm vụ của sinh viên:
Tham dự học, thảo luận, kiểm tra, thi theo qui chế 04/1999/QĐ-BGD&ĐT, qui định 25/2006/QĐ-BGD&ĐT và qui chế học vụ hiện hành của nhà trường
- Dự lớp: trên 75%
- Bài tập: trên lớp và ở nhà
- Khác: theo yêu cầu của giảng viên
10. Tài liệu học tập:
 Sách, giáo trình chính:
[1] Kenneth H.Rosen, Toán rời rạc - Ứng dụng trong tin học, NXB Khoa học kỹ thuật. Hà nội-1997. (Phạm Văn Thiều và Đặng Hữu Thịnh dịch).

 Tài liệu tham khảo:
[2] James L. Hein, Discrete Mathematics, Jones and Bartlett Publisher
[3] Trần Đức Quang, Cơ sở toán cho máy tính - NXB đại học quốc gia tp Hồ Chí Minh – 2003
[4] Đỗ Đức Giáo, Toán rời rạc – NXB đại học quốc gia Hà nội , 2002
[5] Seymour Lupschutz, Mare Lars Lipson,Tuyển chọn 1800 bài tập toán rời rạc , NXB Thống kê

11. Tiêu chuẩn đánh giá sinh viên:
- Dự lớp: trên 75%
- Thảo luận theo nhóm
- Thuyết trình: Mỗi nhóm sẽ thuyết trình trong từng buổi học
- Tiểu luận: không
- Kiểm tra thường xuyên: bài làm ở nhà
- Thi giữa học phần
- Thi kết thúc học phần
- Khác: theo yêu cầu của giảng viên
12. Thang điểm: Theo học chế tín chỉ
13. Nội dung chi tiết học phần:

TT Nội dung Số tiết Phân bổ thời gian Ghi Chú
Lý thuyết Thực hành Tự học
1 Tập hợp và hàm 5 5 0 10
2 Thuật toán và độ phức tạp thuật toán 5 5 0 10
3 Các phương pháp chứng minh 5 5 0 10
4 Phương pháp đếm 5 5 0 10
5 Quan hệ 5 5 0 10
6 Đại số Boole 5 5 0 10
7 Đồ thị 10 10 0 20
8 Cây 5 5 0 10
9 Logic mệnh đề 15 15 0 30
TỔNG 60
60
0 120


Chương 1. TẬP HỢP VÀ HÀM

1.1. Tập hợp
1.1.1. Mở đầu
1.1.2. Tập luỹ thừa
1.1.3. Tích đề các
1.2. Các phép toán tập hợp
1.2.1. Mở đầu
1.2.2. Các hằng đẳng thức tập hợp
1.2.3. Hợp và giao tổng quát
1.2.4. Biểu diễn các tập hợp trên máy tính
1.3. Hàm
1.3.1. Mở đầu
1.3.2. Các hàm đơn ánh và toàn ánh
1.3.3. Hàm ngược và hợp thành của các hàm
1.3.4. Đồ thị của hàm
1.3.5. Một số hàm quan trọng

Chương 2. THUẬT TOÁN VÀ ĐỘ PHỨC TẠP THUẬT TOÁN

2.1. Thuật toán
2.1.1. Mở đầu
2.1.2. Các cách biểu diễn thuật toán
2.1.3. Một số thuật toán cơ bản
2.1.3.1.Thuật toán số học
2.1.3.2.Thuật toán tìm kiếm
2.1.3.3.Thuật toán sắp xếp
2.2. Độ phức tạp của thuật toán

Chương 3. CÁC PHƯƠNG PHÁP CHỨNG MINH

3.1. Các phương pháp chứng minh
3.1.1. Mở đầu
3.1.2. Các quy tắc suy luận
3.1.3. Nguỵ biện
3.1.4. Các phương pháp chứng minh định lý
3.2. Quy nạp toán học
3.2.1. Mở đầu
3.2.2. Tính được sắp tốt
3.2.3. Quy nạp toán học
3.2.4. Các ví dụ
3.2.5. Nguyên lý thứ hai của quy nạp toán học
3.3. Định nghĩa bằng đệ quy
3.3.1. Mở đầu
3.3.2. Các hàm được định nghĩa bằng đệ quy
3.3.3. Các tập hợp được định nghĩa bằng đệ quy
3.4. Các thuật toán đệ quy
3.4.1. Mở đầu
3.4.2. Đệ quy và lặp

Chương 4. PHƯƠNG PHÁP ĐẾM

4.1. Cơ sở của phép đếm
4.1.1. Mở đầu
4.1.2. Những nguyên lý đếm cơ bản
4.1.3. Những bài toán đếm phức tạp
4.1.4. Nguyên lý bù trừ
4.1.5. Biểu đồ cây
4.2. Nguyên lý lồng chim bồ câu
4.2.1. Mở đầu
4.2.2. Nguyên lý Dirichlet tổng quát
4.2.3. Một vài ứng dụng của nguyên lý Dirichlet
4.3. Hoán vị và tổ hợp
4.3.1. Mở đầu
4.3.2. Hoán vị và chỉnh hợp
4.3.3. Tổ hợp
4.3.4. Hệ số nhị thức
4.4. Tổ hợp và chỉnh hợp suy rộng
4.4.1. Mở đầu
4.4.2. Hoán vị có lặp
4.4.3. Tổ hợp lặp
4.4.4. Hoán vị của tập hợp có các phần tử giống nhau
4.5. Kỹ thuật đếm cao cấp
4.5.1. Hệ thức truy hồi
4.5.2. Giải các hệ thức truy hồi
4.5.3. Quan hệ chia để trị
4.5.4. Nguyên lý bù trừ

Chương 5. QUAN HỆ

5.1. Quan hệ và các tính chất của nó
5.1.1. Mở đầu
5.1.2. Hàm như một quan hệ
5.1.3. Các quan hệ trên một tập hợp
5.1.4. Các tính chất của quan hệ
5.1.5. Tổ hợp các quan hệ
5.2. Quan hệ n- ngôi và những ứng dụng của nó
5.2.1. Mở đầu
5.2.2. Quan hệ n – ngôi
5.2.3. Cơ sở dữ liệu và các quan hệ
5.3. Biểu diễn các quan hệ
5.3.1. Mở đầu
5.3.2. Biểu diễn quan hệ bằng ma trận
5.3.3. Biểu diễn quan hệ bằng các đồ thị có hướng
5.4. Bao đóng của các quan hệ
5.4.1. Mở đầu
5.4.2. Bao đóng
5.4.3. Đường đi trong các đồ thị có hướng
5.4.4. Bao đóng bắc cầu
5.4.5. Thuật toán WARSHALL
5.5. Quan hệ tương đương
5.5.1. Mở đầu
5.5.2. Quan hệ tương đương
5.5.3. Các lớp tương đương
5.5.4. Các lớp tương đương và sự phân hoạch

Chương 6. ĐẠI SỐ BOOLE

6.1. Hàm boole
6.2. Biểu diễn các hàm Boole
6.3. Các cổng logic
6.4. Cực tiểu hoá mạch
6.4.1. Mở đầu
6.4.2. Bản đồ Karnaugh
6.4.3. Các điều kiện “không cần quan tâm”
6.4.4. Phương pháp Quine – McCluskey

Chương 7. ĐỒ THỊ

7.1. Mở đầu
7.1.1. Các loại đồ thị
7.1.2. Các mô hình đồ thị
7.2. Các thuật ngữ về đồ thị
7.2.1. Mở đầu
7.2.2. Những thuật ngữ cơ sở
7.2.3. Những đồ thị đơn đặt biệt
7.2.4. Đồ thị phân đôi
7.2.5. Một vài ứng dụng của các đồ thị đặt biệt
7.3. Biểu diễn đồ thị và sự đẳng cấu
7.3.1. Mở đầu
7.3.2. Biểu diễn đồ thị
7.3.3. Ma trận liên kề
7.3.4. Ma trận liên thuộc
7.3.5. Sự đẳng cấu của các đồ thị
7.4. Tính liên thông
7.4.1. Mở đầu
7.4.2. Đường đi
7.4.3. Tính liên thông trong đồ thị vô hướng
7.4.4. Tính liên thông trong đồ thị có hướng
7.5. Đường đi Euler và đường đi Hamilton
7.5.1. Mở đầu
7.5.2. Các điều kiện cần và đủ cho chu trình và đường đi Euler
7.5.3. Đường đi và chu trình Hamilton
7.6. Bài toán đường đi ngắn nhất
7.6.1. Mở đầu
7.6.2. Thuật toán tìm đường đi ngắn nhất

Chương 8. CÂY

8.1. Mở đầu về cây
8.2. Các ứng dụng của cây
8.2.1. Mở đầu
8.2.2. Cây nhị phân tìm kiếm
8.2.3. Cây quyết định
8.2.4. Các mã tiền tố
8.3. Các phương pháp duyệt cây
8.4. Cây và bài toán sắp xếp
8.4.1. Mở đầu
8.4.2. Độ phức tạp của sắp xếp
8.4.3. Sắp xếp kiểu nổi bọt
8.4.4. Sắp xếp kiểu hoà nhập
8.5. Cây khung
8.5.1. Mở đầu
8.5.2. Những thuật toán xây dựng cây khung
8.5.3. Kỹ thuật quay lui
8.6. Cây khung nhỏ nhất

Chương 9. LOGIC MỆNH ĐỀ

9.1. Logic
9.1.1 Mở đầu
9.1.2. Mệnh đề
9.1.3. Dịch những câu thông thường
9.1.4. Các phép toán logic
9.2. Sự tương đương của các mệnh đề
9.1. Mở đầu
9.2.1. Tương đương logic
9.3. Vị từ và lượng từ
9.3.1. Mở đầu
9.3.2. Lượng từ
9.3.3. Dịch các câu thông thường thành các biểu thức logic
9.3.4. Các biến ràng buộc

14. Phê duyệt


Trưởng đơn vị đào tạo


Nguyễn Chí Hiếu Tp. HCM, Ngày… tháng năm 2007
Đại diện Tổ trưởng bộ môn


DOWNLOAD:

(toàn bộ giáo trình là những link tải ở dưới)

http://www.ziddu.com/download/9718998/GiaoTrinhCTRR_C6_DSBOOLE.pdf.html

http://www.ziddu.com/download/9718999/GiaoTrinhCTRR_C1_TapHop.pdf.html

http://www.ziddu.com/download/9719000/GiaoTrinhCTRR_C4.pdf.html

http://www.ziddu.com/download/9719001/GiaoTrinhCTRR_C3.pdf.html

http://www.ziddu.com/download/9719002/GiaoTrinhCTRR_C7.pdf.html

http://www.ziddu.com/download/9719003/GiaoTrinhCTRR_C9.pdf.html

http://www.ziddu.com/download/9719004/GiaoTrinhCTRR_C5_QuanHe.pdf.html

http://www.ziddu.com/download/9719005/GiaoTrinhCTRR_C8.pdf.html

http://www.ziddu.com/download/9719006/GiaoTrinhCTRR_LoinoidauMucluc.pdf.html

http://www.ziddu.com/download/9719007/GiaoTrinhCTRR_C2_HamSo.pdf.html

http://www.ziddu.com/download/9719038/GiaoTrinhCTRR_C12_LogicMenhDe.pdf.html

http://www.ziddu.com/download/9719039/GiaoTrinhCTRR_C14_LogicViTu.pdf.html

http://www.ziddu.com/download/9719040/GiaoTrinhCTRR_C11.pdf.html

http://www.ziddu.com/download/9719041/GiaoTrinhCTRR_C13_CacPPChungMinh.pdf.html

http://www.ziddu.com/download/9719042/GiaoTrinhCTRR_C10_Cay.pdf.html