Dđề toán rời rạc đại học công nghiệp hà nội năm 2024

Toán rời rạc ứng dụng trong tin học là môn học trang bị cho người học kiến thức về logic; lý thuyết đồ thị và cây; ngôn ngữ hình thức và otomat đẩy xuống; nghiên cứu các đối tượng rời rạc trong Khoa học và Kỹ thuật máy tính nhằm giúp sinh viên hiểu sâu về các khía cạnh trừu tượng trong cấu tạo và hoạt động của các hệ thống tính toán; xây dựng thuật toán.

3.2 Mục tiêu cụ thể

1. a) Về kiến thức: Cung cấp cho sinh viên kiến thức cơ bản về lôgic mệnh đề; lý thuyết đồ thị, cây ; ngôn ngữ hình thức và automat đẩy xuống.
2. b) Về kỹ năng: Giúp sinh viên thực hiện được các phương pháp suy diễn logic, tối thiểu hóa được các hàm lôgic; giải quyết được các bài toán tối ưu tìm đường đi trên đồ thị; tô màu đồ thị; xây dựng cây tìm kiếm nhị phân; duyệt cây theo thứ tự; xây dựng được các automat; sinh ra ngôn ngữ chính quy từ văn phạm; kỹ năng làm việc nhóm, kỹ năng thuyết trình.
3. c) Về năng lực tự chủ và trách nhiệm: Giúp sinh viên có khả năng lập kế hoạch quản lý, khả năng đưa ra kết luận chuyên môn; khả năng tự học, tự nghiên cứu nâng cao trình độ chuyên môn.
4. Chuẩn đầu ra của học phần

4.1. Về kiến thức

CLO 1.1: Vận dụng được các kiến thức toán rời rạc (logic toán, lý thuyết đồ thị, cây, ngôn ngữ hình thức, otomat) để xây dựng các giải thuật cho các bài toán ứng dụng thực tế của doanh nghiệp.

4.2. Về kỹ năng

CLO 2.1: Mô hình hoá được bài toán ứng dụng thực tế của doanh nghiệp bằng các mô hình toán rời rạc.

4.3. Về năng lực tự chủ và trách nhiệm

CLO 3.1: Có khả năng tự định hướng, thích nghi với môi trường làm việc khác nhau, khả năng tự học, tự nghiên cứu nâng cao trình độ chuyên môn.

• Ghi chú: CLO = Course Learning Outcomes = Chuẩn đầu ra của học phần.
• Ma trận mức độ đóng góp của CĐR học phần (CLO) vào CĐR của CTĐT (PLO/PIs) PLO

PIs

CLOs

PLO1.2 PLO2.2 PLO3.2 PI 1.2-2 PI 12-3 PI 2.4-1 PI2 .4-2 PI 3.2-1 PI 3.2-2 1 CLO 1.1: Vận dụng được các kiến thức toán rời rạc (logic toán, lý thuyết đồ thị, ngôn ngữ hình thức, otomat) để xây dựng các giải thuật cho các bài toán ứng dụng thực tế của doanh nghiệp M M 2 CLO 2.1: Mô hình hoá được bài toán ứng dụng thực tế của doanh nghiệp bằng các mô hình toán rời rạc. M M 3 CLO 3.1: Có khả năng tự định hướng, thích nghi với môi trường làm việc khác nhau, khả năng tự học, tự nghiên cứu nâng cao trình độ chuyên môn. M M Tổng hợp toàn bộ học phần M M M M M M

1. Nhiệm vụ của sinh viên

– Tham dự giờ lên lớp: Tối thiểu 80% số tiết học trên lớp, trong phòng thực hành có sự giảng dạy, hướng dẫn trực tiếp của giáo viên;

– Bài tập, thảo luận:

+ Đọc tài liệu, chuẩn bị và tham gia thảo luận theo hướng dẫn của giáo viên;

+ Thực hiện đầy đủ các bài tập được giao;

– Làm bài kiểm tra định kỳ;

– Tham gia thi kết thúc học phần.

1. Tài liệu học tập:

7.1. Giáo trình chính:

[1]. Đỗ Văn Nhơn, Giáo trình toán rời rạc, 2014, NXB ĐH quốc gia TP HCM.

7.2. Sách tham khảo:

[1]. ĐH Nam Cần Thơ, Giáo trình toán rời rạc 2, 2018.

[2]. Đỗ Đức Giáo (2011), Toán rời rạc ứng dụng trong Tin học, NXB Giáo dục.

1. Nội dung học phần

8.1 Mô tả tóm tắt nội dung học phần

Toán rời rạc là cơ sở lý thuyết để biểu diễn logic và nghiên cứu các đối tượng rời rạc trong Khoa học và Kỹ thuật Máy tính, đặc biệt là cơ sở toán học để mô hình hóa, hình thức hóa các hệ thống thông tin dựa trên máy tính một cách đúng đắn và hiệu quả. Những nội dung này rất quan trọng nhằm giúp sinh viên chuyên ngành CNTT hiểu sâu về các khía cạnh trừu tượng trong cấu tạo và hoạt động của các hệ thống tính toán.

Học phần bao gồm các nội dung:

Chương 1 Chương này trình bày những khái niệm cơ sở của toán rời rạc. Những nội dung được đề cập tới là các quy tắc logic, bảng giá trị chân lý của các mệnh đề toán học, tập hợp và hàm.

Chương 2 Chương này trình bày những khái niệm cơ bản về đồ thị: đồ thị và phân loại, các cách biểu diễn đồ thị, tính liên thông trong đồ thị ,… Đồng thời xem xét hai lớp đồ thị tiêu biểu là đồ thị Euler và đồ thị Hamilton cũng như việc ứng dụng đồ thị để giải quyết một số bài toán thực tế.

Chương 3 Cây được sử dụng rất nhiều trong tin học. Chương này sẽ trình bày khái niêm cây, tính chất của cây, các phương pháp duyệt cây. Đặc biệt là việc sử dụng cây và một số thuật toán để giải quyết các bài toán tối ưu trên thực tế

Chương 4 Giới thiệu về ngôn ngữ hình thức và automat.

8.2 Ma trận phù hợp giữa các Chương của học phần với CĐR học phần (CLO)

STT Chương CLO 1.1 CLO 2.1 CLO 3.1 1 Chương 1: Logic mệnh đề P P P 2 Chương 2: Lý thuyết đồ thị P P P 3 Chương 3: Cây P P P 4 Chương 4: Ngôn ngữ hình thức và otomat đẩy xuống. P P P

• Ghi chú: I: Introduction/ Giới thiệu

P: Proficient/ Thuần thục, đủ

A: Advanced/ Nâng cao

1. Kế hoạch giảng dạy:

( Phổ biến Kế hoạch giảng dạy và các CĐR, cách thi, kiểm tra cho sinh viên )

Bài dạy Nội dung giảng dạy Số tiết CLO Nhiệm vụ của sinh viên LT,

KT

BT,TL,TH Buổi 1 Chương 1. Lôgic mệnh đề

1.1 Các phép toán và công thức

1.2 Điều kiện đồng nhất đúng, điều kiện đồng nhất sai

2 tiết 1 tiết CLO1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 2 1.3 Các quy tắc suy diễn trong logic mệnh đề

1.4 Vị từ, lượng từ

2 tiết 1 tiết CLO1.1

CLO2.1

Nghiên cứu giáo trình và làm bài tập. Buổi 3 – Bài tập, thảo luận chương 1

– Kiểm tra viết BKT số 1

1 tiết 2 tiết CLO 1.1

CLO 2.1

CLO 3.1

Làm BT được giao Buổi 4 Chương 2. Lý thuyết đồ thị

2.1.Khái niệm cơ bản của lí thuyết đồ thị

2.1.1. Đồ thị và phân loại đồ thị

2.1.2. Những thuật ngữ cơ bản

2.1.3. Đồ thị đơn đặc biệt

2.1.4. Đồ thị phân đôi

2.2. Biểu diễn đồ thị

2.2.1 Mở đầu

2.2.2 Biểu diễn đồ thị

2.2.3 Ma trận liền kề

2 tiết 1 tiết CLO 1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 5 2.3. Tính liên thông

2.3.1 Mở đầu

2.3.2 Đường đi

2.3.3 Tính liên thông trong đồ thị

2.3.4 Bài toán đếm đường đi giữa các đỉnh

1 tiết 2 tiết CLO 1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 6 2.4 Đồ thị Euler, đồ thị Haminton và bài toán đường đi ngắn nhất

2.4.1 Mở đầu

2.4.2 Đồ thị Euler

2.4.3 Đồ thị Haminton

2.4.4 Bài toán đường đi ngắn nhất và thuật toán Dijkstra

2 tiết 1 tiết CLO1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 7 2.5 Đồ thị phẳng và tô màu đồ thị

2.5.1 Mở đầu

2.5.2 Công thức Euler

2.5.3 Định lí Kuratowski

2.5.4 Bài toán tô màu đồ thị và lập lịch thi

2 tiết 1 tiết CLO1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 8 2.6 Các bài toán trên đồ thị

2.6.1 Mạng, luồng trong mạng và bài toán luồng cực đại

2.6.2 Lát cắt. Đường tăng luồng. Định lý Ford-Fullkerson

2.6.3 Thuật toán tìm luồng cực đại trong mạng

1 tiết 2 tiết CLO 1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 9 – Bài tập, thảo luận chương 2

– Kiểm tra viết BKT số 2

1 tiết 2 tiết CLO 1.1

CLO 2.1

CLO 3.1

Làm BT được giao. Buổi 10 Chương 3. Lý thuyết Cây

3.1 Mở đầu về cây

3.1.1 Khái niệm về cây

3.1.2 Tính chất cây

3.1.3 Cây tìm kiếm

3.1.4 Cây quyết định

3.1.5 Các mã tiền tố

2 tiết 1 tiết CLO1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 11 3.2 Phương pháp duyệt cây

3.2.1 Mở đầu

3.2.2 Hệ địa chỉ phổ dụng

3.2.3 Các thuật toán duyệt cây

3.2.4 Các ký pháp trung tố, tiền tố và hậu tố

1 tiết 2 tiết CLO1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 12 3.3 Cây khung và cây khung nhỏ nhất

3.3.1 Mở đầu

3.3.2 Những thuật toán xây dựng cây khung

3.3.3 Cây khung nhỏ nhất

2 tiết 1 tiết CLO1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 13 – Bài tập, thảo luận chương 3

– Kiểm tra viết BKT số 3

1 tiết 2 tiết CLO 1.1

CLO 2.1

CLO 3.1

Làm BT được giao. Buổi 14 Chương 4. Ngôn ngữ hình thức và Automat

4.1. Văn phạm và ngôn ngữ sinh bởi văn phạm

4.1.1. Khái niệm ngôn ngữ

4.1.2. Văn phạm và ngôn ngữ sinh bởi văn phạm

2 tiết 1 tiết CLO1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 15 Chương 4. ( tiếp )

4.1.3. Tính chất của văn phạm

2 tiết 1 tiết CLO1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 16 Chương 4. ( tiếp )

4.2. Automat hữu hạn và ngôn ngữ chính quy

4.2.1. Automat hữu hạn

4.2.2. Ngôn ngữ chính quy

4.2.3.Quan hệ giữa Automat hữu hạn và ngôn ngữ chính quy

2 tiết 1 tiết CLO1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 17 Chương 4. ( tiếp )

4.3. Ngôn ngữ phi ngữ cảnh và Automat đẩy xuống

4.3.1. Văn phạm phi ngữ cảnh

4.3.2. Dạng chuẩn Chomsky

2 tiết 1 tiết CLO1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 18 4.3.3. Automat đẩy xuống 2 tiết 1 tiết CLO 1.1 Nghiên cứu giáo trình và làm bài tập. Buổi 19 Bài tập, thảo luận 3 tiết CLO1.1

CLO2.1

CLO 3.1

Làm BT được giao. Buổi 20 Tổng kết học phần, công bố điểm. 3 tiết CLO 1.1

CLO 2.1

CLO 3.1

Ôn tập, hệ thống lại kiến thức. Tổng cộng 30 tiết 30 tiết

1. Phương pháp dạy học

10.1 Các phương pháp dạy học được sử dụng

STT Phương pháp dạy học Lựa chọn 1 Phương pháp chung là thuyết trình kết hợp linh hoạt với các phương pháp dạy học tích cực sau đây: x 2 Phương pháp dạy học theo nhóm: Thảo luận nhóm. x 3 Phương pháp dạy học theo dự án mô phỏng thực tế 4 Dạy học thực hành (trong phòng máy tính, tại doanh nghiệp) 5 Dạy học trải nghiệm: Kiến tập, thực tập doanh nghiệp 6 Hướng dẫn tự học x

10.2 Ma trận phù hợp giữa phương pháp dạy học với CLO

STT Phương pháp dạy học CLO 1.1 CLO 2.1 CLO 3.1 1 Thuyết trình x x 2 Phương pháp dạy học theo vấn đề x x x 3 Hướng dẫn tự học x x

1. Đánh giá kết quả học tập

11.1. Phương pháp, hình thức đánh giá

11.1.1 Các phương pháp đánh giá

1. Đánh giá chuyên cần (Tham gia học trên lớp; ý thức, thái độ, chất lượng tham gia các hoạt động học tập)