Đề cương chi tiết môn Toán rời rạc và lý thuyết đồ thị
INFO UTE LIBRARY
ĐỀ CƯƠNG CHI TIẾT MÔN HỌC
TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ ThỊ
DISCRETE MATH AND GRAPH THEORY
(Ngành Kỹ thuật Dữ liệu - Chương trình đào tạo đại học 132TC)
HCMUTE.EDU.VN - THÁNG 9 NĂM 2019
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT
THÀNH PHỐ HỒ CHÍ MINH
--------------------
ĐỀ CƯƠNG CHI TIẾT MÔN HỌC
TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊ
DISCRETE MATH AND GRAPH THEORY
(Ngành Kỹ thuật Dữ liệu - Chương trình đào tạo đại học 132TC)
HCMUTE.EDU.VN – THÁNG 9 NĂM 2019
LỜI NÓI ĐẦU
Công nghệ thông tin (IT) là một trong những động lực quan trọng
bậc nhất của sự phát triển, cùng với một số ngành công nghệ cao khác
đang làm biến đổi sâu sắc đời sống kinh tế, văn hoá, xã hội của thế giới
hiện đại. Việc ứng dụng và phát triển CNTT ở nước ta đã góp phần giải
phóng sức mạnh vật chất, trí tuệ và tinh thần, thúc đẩy công cuộc đổi
mới, phát triển nhanh và hiện đại hóa các ngành kinh tế, tăng cường năng
lực cạnh tranh của các doanh nghiệp, hỗ trợ có hiệu quả cho quá trình
chủ động hội nhập kinh tế quốc tế, nâng cao chất lượng cuộc sống của
nhân dân, đảm bảo an ninh quốc phòng góp phần thực hiện thắng lợi sự
nghiệp công nghiệp hóa, hiện đại hóa đất nước.
Hiện nay, trường Đại học Sư phạm Kỹ thuật Tp. Hồ Chí Minh
chú đã phát triển 02 chương trình đào tạo mũi nhọn hướng đến sự phát
triển của công nghệ thông tin: Chương trình đào tạo ngành “Công nghệ
thông tin” & chương trình đào tạo ngành “Kỹ thuật Dữ liệu”. Ngành “Kỹ
thuật Dữ liệu” là một nhánh rẽ quan trọng trong lĩnh vực công nghệ
thông tin và là ngành sớm khai phá những tiềm lực quan trọng thúc đẩy
sự phát triển của thế giới. Với sự phát triển nhanh chóng và lan rộng của
ngành “Kỹ thuật Dữ liệu” đã đặc biệt thu hút sự quan tâm của các chuyên
gia Việt Nam và cả trên khắp thế giới.
Để đáp ứng nhu cầu tìm kiếm và sử dụng tài liệu học tập các môn
học chuyên ngành “Kỹ thuật Dữ liệu” của sinh viên. Thư viện trường Đại
học Sư phạm Kỹ thuật TP. Hồ Chí Minh đã biên soạn tài liệu thông tin về
đề cương chi tiết môn học nhằm cung cấp cho sinh viên có thể nghiên
cứu, tìm hiểu, học tập về chuyên ngành của mình.
Tài liệu thông tin về đề cương chi tiết môn học ngành “Kỹ thuật Dữ
liệu” nhằm hướng dẫn tìm kiếm và sử dụng tài liệu học tập các môn học
chuyên ngành “Kỹ thuật Dữ liệu” sẽ mang đến cho sinh viên nắm được
phương pháp học nhanh nhất và đạt hiệu quả.
Mặc dù chúng tôi đã cố gắng, song việc biên soạn tài liệu chắc
chắn không tránh khỏi thiếu sót, rất mong nhận được những ý kiến đóng
góp từ phía người sử dụng để lần biên soạn sau được hoàn chỉnh hơn.
Thư viện ĐHSPKT TP.HCM
028.389 69 920
facebook.com/hcmute.lib
4
GIỚI THIỆU CÁC DỊCH VỤ UTE LIBRARY
Đồng hành cùng độc giả trên con đường chinh phục tri thức
Nơi cung cấp nguồn lực thông tin khoa học kỹ thuật và giáo dục
phục vụ cho nhu cầu đào tạo của Nhà trường.
Cung cấp thông tin
Nội dung phong phú
Đa dạng loại hình
Hình thức phục vụ
Đọc tại chỗ
Mượn về nhà
Cập nhật thường xuyên
Khai thác tài nguyên số 24/24
Các dịch vụ học tập trực tuyến
Các loại hình dịch vụ
1.
2.
3.
4.
Phục vụ trực tiếp tại thư viện: được hướng dẫn tận tình với hệ
thống phòng đọc & Giáo trình mở, có thể tìm đọc tài liệu dạng
giấy, CD-ROM, CSDL trực tuyến,…
Hỗ trợ công tác biên soạn xuất bản giáo trình và tài liệu học tập, kỷ
yếu hội thảo (phục vụ hoạt động NCKH, chương trình đào tạo 150
tín chỉ, bổ sung hồ sơ xét các chức danh khoa học,...).
Thiết kế website phục vụ hoạt động học tập, nghiên cứu khoa học,
hội thảo: Xây dựng template chung, Thiết lập các trang con (sub
pages), Cấp quyền và chuyển giao quyền quản trị trang con.
Xuất bản kỷ yếu hội thảo: Tư vấn, thiết kế, dàn trang, Thiết kế các
hình ảnh, nhãn hiệu liên quan đến hội nghị (logo hội nghị, banner,
poster…), Đăng ký và xin giấy phép xuất bản kỷ yếu, Giám sát các
tài liệu liên quan đến chương trình như thư, thông tin hội nghị, tài
liệu tham khảo,…
5.
6.
Xây dựng các sản phẩm phục vụ hội thảo và các hoạt động học tập:
CD-ROM chương trình và kỷ yếu, Ứng dụng tự chạy giới thiệu tài
liệu, ghi đĩa CD- ROM, DVD, USB,…
Cung cấp thông tin theo yêu cầu (danh mục tài liệu, tài liệu chuyên
ngành, kết quả nghiên cứu khoa học, tiêu chuẩn, phát minh sáng
chế…).
7.
8.
9.
Mô tả, tạo và chọn danh mục “Tài liệu tham khảo” cho luận văn,
luận án, đề tài nghiên cứu khoa học theo chuẩn quốc tế.
Chuyển dạng tài liệu (từ tài liệu dạng giấy sang file PDF, từ file
PDF sang file Word).
Cung cấp các thiết bị hỗ trợ cho việc học tập và nghiên cứu,...
10. Hỗ trợ, tư vấn và phối hợp với Thư viện các trường trong việc phát
triển các sản phẩm đặc thù của từng đơn vị.
5
Với nhiều hình thức phục vụ phong phú, thuận tiện cho người học
NGUỒN TÀI NGUYÊN THÔNG TIN
. CSDL Giáo trình và Tài liệu . CSDL Sách tham khảo Việt
học tập
văn
. CSDL Luận văn, Luận án
. CSDL Sách tham khảo Ngoại
văn
. CSDL các bài báo khoa học (các bài báo nghiên cứu của học viên
theo chương trình đào tạo sau đại học được đăng trên các tạp chí
chuyên ngành)
Địa chỉ liên hệ:
Thư viện Trường Đại học Sư phạm Kỹ thuật Tp. Hồ Chí Minh,
Số 1-3 Võ Văn Ngân, Phường Linh chiểu, Quận Thủ Đức, Tp. Hồ Chí
Minh.
Điện thoại: (+84 028) 3896 9920, 3721223 (nội bộ 8223)
Email: [email protected]
GIỚI THIỆU CÁC WEBSITE PHÁT HÀNH UTE EBOOK
“UTE EBOOK” là những tác phẩm chỉ có thể dùng các công cụ
điện tử như máy vi tính, máy trợ giúp kỹ thuật số cá nhân (thiết bị đọc,
máy tính bảng và điện thoại thông minh như iPhone, iPad, Samsung
Galaxy, HTC Tablet,...) để xem, đọc, và truyển tải.
“UTE EBOOK” là hệ thống phân phối sách điện tử, cung cấp đến người
dùng các nội dung sách,giáo trình, truyện, tạp chí, tài liệu, chuyên đề và
các thể loại văn bản đọc, audio khác trên di động, thông qua các kênh
website, wapsite và client giúp khách hàng có thể cập nhật thông tin kiến
thức mọi lúc mọi nơi.
Tên đơn vị phát
hành
Truy cập nhanh
kho giáo trình
Stt
Website
Nhà Xuất Bản Tổng
Hợp Thành Phố Hồ
Chí Minh
XU
1
Công Ty Cổ Phần
Tin Học Lạc Việt
Công Ty TNHH
Sách Điện Tử Trẻ
(YBOOK)
https://bit.ly/2Zx8Y
Zn
2
3
4
Q
Công Ty Cổ Phần
Dịch Vụ Trực Tuyến
om RM
6
VINAPO
Công Ty Cổ Phần
Thương Mại Dịch
Vụ Mê Kông COM
Thư viện Trường
Đại học Sư phạm Kỹ
thuật TP. HCM
5
6
e.edu.vn/ e.edu.vn/
DỊCH VỤ HỖ TRỢ XUẤT BẢN ĐIỆN TỬ:
Sách chuyên khảo, giáo trình, sách tham khảo, sách hướng dẫn, tài
liệu phục vụ đào tạo, Kỷ yếu hội thảo, tập san, tạp chí
Nhằm hỗ trợ Quý Thư viện các Trường Đại học, Cao đẳng về việc
xuất bản giáo trình, tài liệu học tập điện tử nội sinh,…đạt chất lượng cao
phục vụ hoạt động đào tạo, giảng dạy; Thư viện Trường Đại học Sư
phạm Kỹ thuật TP. Hồ Chí Minh giới thiệu đến Quý Thư viện các
Trường Đại học, Cao đẳng về “Chương trình hỗ trợ xuất bản điện tử:
Sách chuyên khảo, giáo trình, sách tham khảo, sách hướng dẫn, tài liệu
phục vụ đào tạo, Kỷ yếu hội thảo, tập san, tạp chí ”.
1. Cơ sở xây dựng chương trình:
Căn cứ theo công văn Số: 4301/BGDĐT-GDTX ngày 20 tháng 9
năm 2019 của Bộ trưởng Bộ Giáo dục và Đào tạo về việc xây dựng và
2. Thời gian triển khai chương trình hỗ trợ
- Giai đoạn 05 năm (Từ ngày 01/10/2019 đến hết ngày 01/10/2024)
3. Tổ chức chương trình
- Thư viện Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh.
4. Đơn vị công bố phổ biến xuất bản phẩm điện tử
- Thư viện Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh &
Các đơn vị liên kết.
- website các đơn vị liên kết.
5. Cấu trúc của xuất bản điện tử giáo trình, tài liệu học tập nội sinh
Xuất bản điện tử giáo trình, tài liệu học tập nội sinh có cấu trúc như
sau:
- Trang bìa.
- Trang bìa phụ.
7
- Lời nói đầu: Trình bày đối tượng sử dụng, mục đích yêu cầu khi sử
dụng, cấu trúc nội dung, điểm mới của giáo trình, hướng dẫn cách
sử dụng, phân công nhiệm vụ của tác giả biên soạn.
- Mục lục.
- Danh mục các từ viết tắt (nếu có).
- Danh mục hình (nếu có)..
- Danh mục bảng biểu (nếu có)..
- Nội dung chính: Trình bày các chương, mục, tiểu mục và nội dung
chi tiết của từng chương, mục, tiểu mục, nội dung thảo luận
xêmina, câu hỏi ôn tập, bài tập, các nhiệm vụ tự học và tài liệu học
tập từng chương.
- Phụ lục (nếu có).
- Tài liệu tham khảo.
6. Để biết thêm thông tin chi tiết Quý Thầy/Cô liên hệ
- Thư viện Trường Đại Học Sư phạm Kỹ thuật TP. Hồ Chí Minh.
- Số 1-3 Võ Văn Ngân, Phường Linh Chiểu, Quận Thủ Đức, TP. Hồ
Chí Minh.
- Điện thoại: 08.38969920 hoặc 0909836920; 0906836920 (ThS. Vũ
Trọng Luật)
Xin trân trọng giới thiệu đến Quý Thầy/Cô!
8
GIỚI THIỆU CÁC CƠ SỞ DỮ LIỆU TRỰC TUYẾN
TÌM KIẾM VÀ SỬ DỤNG HIỆU QUẢ
Thư viện ĐH SPKT TP. HCM
028.38969920
Nhằm tăng cường năng lực nghiên cứu của tập thể giảng viên và
sinh viên của nhà trường, từng bước nâng cao chất lượng đào tạo và nâng
vị thế của trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh lên tầm
cao mới, xứng đáng là một trong những trường đại học hàng đầu của khu
vực, nhà trường đã tiến hành mua quyền sử dụng tài khoản truy cập các
cơ sở dữ liệu trực tuyến để giảng viên và sinh viên của trường khai thác.
Việc khai thác các tư liệu điện tử, các CSDL trực tuyến sẽ góp phần tạo
thêm nhiều cơ hội tiếp cận với các kho tư liệu học thuật và nghiên cứu có
giá trị cao và được phổ biến trên toàn thế giới.
Để triển khai sử dụng và khai thác các cơ sở dữ liệu trực tuyến
đạt hiệu quả, Thư viện xin thông báo đến Quý Thầy Cô & Các Bạn Sinh
viên về nội dung triển khai và sử dụng CSDL như sau:
Thông tin triển khai sử dụng:
- Truy cập Web, không giới hạn số lượng người sử dụng, hỗ trợ
việc truy cập cho 25.000 sinh viên và gần 1.000 giảng viên, cán bộ viên
chức của nhà trường.
-
-
Sử dụng email do nhà trường cấp để tạo tài khoản đăng ký:
theo địa chỉ email của cán bộ …@hcmute.edu.vn
theo địa chỉ email của sinh viên …@student.hcmute.edu.vn
Hình thức truy cập: Theo IP đăng kí của nhà trường.
Lưu ý: Việc khai thác các CSDL được nhà xuất bản xác minh
người dùng với nhiều lớp bảo mật qua dải địa chỉ IP và
username/password, quý thầy cô và bạn đọc chỉ có thể khai thác
các CSDL này trên hệ thống máy tính được kết nối mạng trong
trường.
-
-
Thông tin hỗ trợ kỹ thuật:
Trong quá trình sử dụng, quý thầy cô và bạn đọc cần hỗ trợ kỹ
thuật xin vui lòng liên hệ:
Cô Trần Thị Ngọc Ý, Số ĐT 0919888975,
email: [email protected].vn
Thư viện trân trọng thông báo đến Quý Thầy Cô và Các Bạn Sinh
viên biết để sử dụng và khai thác các cơ sở dữ liệu trực tuyến đạt hiệu
quả.
Trân trọng!
9
ĐỀ CƯƠNG CHI TIẾT MÔN HỌC
TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊ
DISCRETE MATH AND GRAPH THEORY
Môn học Toán rời rạc và lý thuyết đồ thị gồm hai phần chính:
- Phần “Toán rời rạc” trang bị cho người học những kiến thức cơ bản về
logic mệnh đề, logic vị từ, suy diễn logic, quan hệ tương đương, quan hệ thứ tự,
dàn và đại số Bool. Cung cấp cho người học kiến thức và kỹ năng trong việc
phân tích, nhìn nhận vấn đề, trong việc xác định công thức đa thức tối tiểu bằng
phương pháp biểu đồ Karnaugh.
- Phần “Lý thuyết đồ thị” (LTĐT) trang bị sự hiểu biết về các lĩnh vực
ứng dụng của lý thuyết đồ thị, cung cấp kiến thức nền tảng về lý thuyết đồ thị
ứng dụng trong tin học. Cung cấp các thuật toán, kỹ thuật và kỹ năng lập trình
các giải thuật trong lý thuyết đồ thị.
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT
TP. HỒ CHÍ MINH
Ngành đào tạo: Kỹ thuật Dữ liệu
Trình độ đào tạo: Đại học
KHOA CÔNG NGHỆ THÔNG TIN
Chương trình đào tạo: Kỹ thuật Dữ liệu
Đề cương chi tiết môn học
1. Tên học phần: TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊ
Mã học phần: DIGR230485
2. Tên Tiếng Anh: DISCRETE MATH AND GRAPH THEORY
3. Số tín chỉ: 3 tín chỉ (2/1/6) (2 tín chỉ lý thuyết, 1 tín chỉ thực hành/ thí
nghiệm)
Phân bố thời gian: 15 tuần (2 tiết lý thuyết + 2 tiết thực hành + 6 tiết tự học/
tuần)
4. Các giảng viên phụ trách học phần:
1/ GV phụ trách chính: ……………………..
2/ Danh sách giảng viên cùng GD: ……………………..
5. Điều kiện tham gia học tập học phần
Môn học tiên quyết: Không
Môn học trước: Nhập môn lập trình
6. Mô tả học phần (Course Description)
Học phần này gồm hai phần chính:
-
Phần “Toán rời rạc” trang bị cho người học những kiến thức
cơ bản về logic mệnh đề, logic vị từ, suy diễn logic, quan hệ
10
tương đương, quan hệ thứ tự, dàn và đại số Bool. Cung cấp
cho người học kiến thức và kỹ năng trong việc phân tích, nhìn
nhận vấn đề, trong việc xác định công thức đa thức tối tiểu
bằng phương pháp biểu đồ Karnaugh.
-
Phần “Lý thuyết đồ thị” (LTĐT) trang bị sự hiểu biết về các
lĩnh vực ứng dụng của lý thuyết đồ thị, cung cấp kiến thức
nền tảng về lý thuyết đồ thị ứng dụng trong tin học. Cung cấp
các thuật toán, kỹ thuật và kỹ năng lập trình các giải thuật
trong lý thuyết đồ thị.
7. Mục tiêu học phần (Course Goals)
Mục tiêu
Mô tả
Chuẩn đầu
Trình độ
(Goals)
(Goal description)
ra
CTĐT
1.2
năng lực
(Học phần này trang bị cho sinh viên:)
Kiến thức chuyên môn về toán rời rạc và lý
thuyết đồ thị.
Khả năng phân tích, giải thích, tư duy và lập
luận giải quyết các vấn đề về toán rời rạc và
lý thuyết đồ thị.
3
3
G1
G2
1.3
2.1, 2.3, 2.4, 2, 3, 3, 2
2.5
Kỹ năng làm việc nhóm, giao tiếp, lãnh đạo 3.1
và thái độ cẩn thận, tỉ mỉ khi làm việc.
Khả năng áp dụng lý thuyết về đồ thị để giải 4.3
quyết các bài toán tin học hoặc các hệ thống
CNTT.
2
3
G3
G4
8. Chuẩn đầu ra của môn học
Mô tả
Chuẩn
đầu ra
CDIO
1.2
Trình độ
năng lực
Chuẩn đầu ra
(Sau khi học xong môn học này, người
MH
G1.1
học có thể:)
Có kiến thức cơ bản về logic mệnh đề,
logic vị từ, suy diễn logic, quan hệ tương
đương, quan hệ thứ tự, dàn và đại số Bool.
Trình bày được các khái niệm cơ bản và
các lĩnh vực ứng dụng của LTĐT
Áp dụng được phương pháp biểu đồ
Karnaugh để tìm công thức đa thức tối
tiểu.
Xác định được một suy diễn đúng hay sai.
Hiểu và cài đặt được các giải thuật (BFS,
DFS, Prim, Kruskal, Dijkstra, Ford-
Bellman, Floyd...) trong LTĐT.
3
G1
G2
1.3
3
3
3
3
G1.2
G2.1
2.1.4
2.1.4
2.5.4
G2.2
G3.1
Thể hiện sự cẩn thận, tỉ mỉ khi làm việc.
Có khả năng làm việc nhóm, giao tiếp.
3.1.2
3.2.4
3.2.6
1.2.2
1.3.1
2.1.1
2.1.2
2
2
2
3
3
3
3
G3
G4
Vận dụng được lý thuyết về đồ thị vào
giải quyết các bài toán tin học.
G4.1
11
9.
Đạo đức khoa học:
Các bài tập ở nhà và dự án phải được thực hiện từ chính bản thân sinh
viên. Nếu bị phát hiện có sao chép thì xử lý các sinh viên có liên quan bằng
hình thức đánh giá 0 (không) điểm quá trình và cuối kỳ.
10. Nội dung chi tiết môn học:
Chuẩn Trình
Phương
pháp dạy
học
Phương
pháp
đánh
giá
đầu ra
học
độ
năng
lực
Tuần
Nội dung
phần
Chương 1: Cơ sở logic
A/ Các nội dung và PPGD chính
trên lớp: (8)
G1.1
G3.1
3
3
+ Thuyết
trình
Bài tập
tại lớp.
+ Trình
chiếu
Powerpoint
Nội dung GD lý thuyết:
Giới thiệu về môn học, cách
học, tài liệu tham khảo,
nguyên tắc làm việc. Sử dụng
bài giảng PowerPoint.
Phép tính mệnh đề.
Suy diễn logic
Vị từ và lượng từ
1- 2
G1.1
G3.1
3
3
Giải bài
tập theo
nhóm.
B/ Các nội dung cần tự học ở
nhà: (16)
+ Làm 20 bài tập được giao.
-Liệt kê các tài liệu học tập cần
thiết (yêu cầu phải thống nhất với
mục 10 nêu trên)
+ Nguyễn Hữu Anh, Toán rời rạc.
ĐHKHTN TPHCM, 2003.
+ Kenneth H. Rosen, Toán học rời
rạc ứng dụng trong tin học. NXB
Khoa học và Kỹ thuật, 1997.
Chương 2: Quan hệ
G1.1
G3.1
2
2
+ Thuyết
trình
Bài tập
tại lớp.
A/ Tóm tắt các ND và PPGD
chính trên lớp: (4)
+ Trình
chiếu
Powerpoint
Nội dung GD lý thuyết:
Quan hệ
Quan hệ tương đương, quan hệ
thứ tự
Dàn.
3
+ Bài tập chương 2.
PPGD chính:
Thuyết trình
+ Trình chiếu Powerpoint
G1.1
G3.1
2
2
Giải bài
tập theo
nhóm.
B/ Các nội dung cần tự học ở
nhà: (8)
+ Đọc thêm về dàn 2E, dàn Un
+ Làm 20 bài tập được giao
12
-Liệt kê các tài liệu học tập cần
thiết (yêu cầu phải thống nhất với
mục 10 nêu trên)
+ Nguyễn Hữu Anh, Toán rời rạc.
ĐHKHTN TPHCM, 2003.
+ Nguyễn Đức Nghĩa - Nguyễn
Tô Thành, Toán rời rạc. NXB
Giáo dục,1999.
Chương 3: Đại số Bool
G2.1
G3.1
3
3
+ Thuyết
trình
Bài tập
tại lớp.
A/ Các nội dung và PPGD chính
trên lớp: (4)
+ Trình
chiếu
Powerpoint
Nội dung GD lý thuyết:
Đại số Bool.
Hàm Bool.
Mạng các cổng, phương pháp
biểu đồ Karnaugh.
+ Bài tập chương 3.
G2.1
G3.1
Giải bài
tập theo
nhóm.
B/ Các nội dung cần tự học ở
nhà: (8)
+ Chứng minh luật DeMorgan
+ Đọc thêm về dạng nối rời chính
tắc
4
+ Thể hiện phương pháp biểu đồ
Karnaugh trên máy tính.
+ Làm 20 bài tập được giao
-Liệt kê các tài liệu học tập cần
thiết (yêu cầu phải thống nhất với
mục 10 nêu trên)
+ Nguyễn Hữu Anh, Toán rời rạc.
ĐHKHTN TPHCM, 2003.
+ Nguyễn Đức Nghĩa - Nguyễn
Tô Thành, Toán rời rạc. NXB
Giáo dục,1999.
+ Kenneth H. Rosen, Toán học rời
rạc ứng dụng trong tin học. NXB
Khoa học và Kỹ thuật, 1997.
Chương 4: Mở đầu về LTĐT
G1.2
3
Bài tập
tại lớp.
A/ Các nội dung và PPGD chính
trên lớp: (8)
Thuyết
trình
Nội dung GD lý thuyết:
+ Lịch sử, ứng dụng, các khái
niệm cơ bản (đỉnh, cạnh, kề,
đường đi, chu trình, đồ thị liên
thông…)
+ Trình
chiếu
Powerpoint
5-6
Ma trận kề, ma trận trọng số,
danh sách cạnh, danh sách
cung, danh sách kề, ma trận
liên thuộc
13
+ Bài tập chương 4.
G1.2
Giải bài
tập theo
nhóm.
B/ Các nội dung cần tự học ở
nhà: (16)
+ Làm 20 bài tập được giao.
-Liệt kê các tài liệu học tập cần
thiết (yêu cầu phải thống nhất với
mục 10 nêu trên)
+ Đặng Trường Sơn – Lê Văn
Vinh, Lý thuyết đồ thị, NXB
ĐHQG TP.HCM, 2012.
+ Trần Đan Thư - Dương Anh
Đức, Lý thuyết đồ thị. NXB
ĐHQG TP.HCM.
Chương 5: Tìm kiếm trên đồ thị
G2.2
G3.1
G4.1
3
2
3
Bài
thực
hành
trên
Thuyết
trình
Trình
chiếu
Powerp
oint
A/ Các nội dung và PPGD chính
trên lớp: (8)
Nội dung GD lý thuyết:
+ Duyệt theo chiều rộng, chiều
sâu, tìm đường đi, kiểm tra liên
thông.
máy.
+ Thực
+ Bài tập chương 5.
+ Thực hành trên máy.
hành trên
máy có
hướng dẫn.
G2.2
G3.1
G4.1
B/ Các nội dung cần tự học ở
nhà: (16)
+ Cài đặt các thuật toán duyệt đồ
thị theo chiều sâu, chiều rộng, tìm
đường đi, kiểm tra tính liên thông.
+ Bài làm thêm : chu trình Euler.
-Liệt kê các tài liệu học tập cần
thiết (yêu cầu phải thống nhất với
mục 10 nêu trên)
7 –
8
+ Đặng Trường Sơn – Lê Văn
Vinh, Lý thuyết đồ thị, NXB
ĐHQG TP.HCM, 2012.
+ Trần Ngọc Danh, Toán rời rạc
nâng cao. NXB ĐHQG TP.HCM.
+ Trần Đan Thư - Dương Anh
Đức, Lý thuyết đồ thị. NXB
ĐHQG TP.HCM.
+ Nguyễn Đức Nghĩa - Nguyễn
Tô Thành, Toán rời rạc. NXB
Giáo dục,1999.
+ Kenneth H. Rosen, Toán học rời
rạc ứng dụng trong tin học. NXB
14
Khoa học và Kỹ thuật, 1997.
+ Robert Sedgewick, Cẩm nang
thuật toán. NXB Khoa học & Kỹ
thuật, 2004.
Chương 6: Cây
G2.2
G3.1
G4.1
3
2
3
Bài
thực
hành
trên
Thuyết
trình
Trình
chiếu
Powerp
oint
A/ Các nội dung và PPGD chính
trên lớp: (12)
Nội dung GD lý thuyết:
Các tính chất cơ bản, thuật toán
Kruskal, Prim.
máy.
+ Một số bài toán dẫn về cây
khung nhỏ nhất
+ Thực
+ Thực hành trên máy.
+ Bài tập chương 6.
hành trên
máy có
hướng dẫn.
G2.2
G3.1
G4.1
B/ Các nội dung cần tự học ở
nhà: (24)
Hoàn chỉnh các thuật toán đã cài
đặt ở chương trước.
+ Cài đặt các thuật toán xây dựng
cây khung nhỏ nhất (Prim,
Kruskal).
+ Làm 20 bài tập được giao.
-Liệt kê các tài liệu học tập cần
thiết (yêu cầu phải thống nhất với
mục 10 nêu trên)
9-11
+ Đặng Trường Sơn – Lê Văn
Vinh, Lý thuyết đồ thị, NXB
ĐHQG TP.HCM, 2012.
+ Trần Ngọc Danh, Toán rời rạc
nâng cao. NXB ĐHQG TP.HCM.
+ Trần Đan Thư - Dương Anh
Đức, Lý thuyết đồ thị. NXB
ĐHQG TP.HCM.
+ Nguyễn Đức Nghĩa - Nguyễn
Tô Thành, Toán rời rạc. NXB
Giáo dục,1999.
+ Kenneth H. Rosen, Toán học rời
rạc ứng dụng trong tin học. NXB
Khoa học và Kỹ thuật, 1997.
+ Robert Sedgewick, Cẩm nang
thuật toán. NXB Khoa học & Kỹ
thuật, 2004.
Chương 7: Bài toán đường đi
ngắn nhất
G2.2
G3.1
G4.1
3
2
3
Bài
thực
hành
trên
Thuyết
trình
Trình
chiếu
A/ Các nội dung và PPGD chính
trên lớp: (12)
Nội dung GD lý thuyết:
Giới thiệu bài toán, thuật toán
12-14
15
Ford-Bellman, Dijkstra, Floyd.
+ Thực hành trên máy
+ Bài tập chương 7.
Powerp
oint
+ Thực
hành trên
máy có
máy.
hướng dẫn.
G2.2
G3.1
G4.1
B/ Các nội dung cần tự học ở
nhà: (24)
5 Cài đặt các thuật toán Ford-
Bellman, Dijkstra, Floyd.
+ Làm 20 bài tập được giao
-Liệt kê các tài liệu học tập cần
thiết (yêu cầu phải thống nhất với
mục 10 nêu trên)
+ Đặng Trường Sơn – Lê Văn
Vinh, Lý thuyết đồ thị, NXB
ĐHQG TP.HCM, 2012.
+ Trần Ngọc Danh, Toán rời rạc
nâng cao. NXB ĐHQG TP.HCM.
+ Trần Đan Thư - Dương Anh
Đức, Lý thuyết đồ thị. NXB
ĐHQG TP.HCM.
+ Nguyễn Đức Nghĩa - Nguyễn
Tô Thành, Toán rời rạc. NXB
Giáo dục,1999.
+ Kenneth H. Rosen, Toán học rời
rạc ứng dụng trong tin học. NXB
Khoa học và Kỹ thuật, 1997.
+ Robert Sedgewick, Cẩm nang
thuật toán. NXB Khoa học & Kỹ
thuật, 2004.
Chương 8: Luồng cực đại trên
mạng
G2.2
G3.1
G4.1
3
2
3
Bài
thực
hành
trên
A/ Các nội dung và PPGD chính
trên lớp: (4)
Thuyết
trình
Trình
chiếu
Powerp
oint
Nội dung GD lý thuyết:
Bài toán luồng cực đại
+ Định lý Ford-Fulkerson
+ Thuật toán tìm luồng cực đại
trong mạng
máy.
+ Thực
15
+ Một số bài toán đưa về luồng.
+ Ví dụ minh họa
+ Bài tập chương 8.
hành trên
máy có
hướng dẫn
G2.2
G3.1
G4.1
B/ Các nội dung cần tự học ở
nhà: (8)
Cài đặt thuật toán tìm luồng cực
đại (ứng dụng trong các bài toán
hôn nhân bền vững, ghép đôi…)
+ Làm 10 bài tập được giao.
16
-Liệt kê các tài liệu học tập cần
thiết (yêu cầu phải thống nhất với
mục 10 nêu trên)
+ Nguyễn Hữu Anh, Toán rời rạc.
ĐHKHTN TPHCM, 2003.
+ Đặng Trường Sơn – Lê Văn
Vinh, Lý thuyết đồ thị, NXB
ĐHQG TP.HCM, 2012.
+ Trần Ngọc Danh, Toán rời rạc
nâng cao. NXB ĐHQG TP.HCM.
+ Trần Đan Thư - Dương Anh
Đức, Lý thuyết đồ thị. NXB
ĐHQG TP.HCM.
+ Nguyễn Đức Nghĩa - Nguyễn
Tô Thành, Toán rời rạc. NXB
Giáo dục,1999.
+ Kenneth H. Rosen, Toán học rời
rạc ứng dụng trong tin học. NXB
Khoa học và Kỹ thuật, 1997.
+ Robert Sedgewick, Cẩm nang
thuật toán. NXB Khoa học & Kỹ
thuật, 2004.
11. Đánh giá kết quả học tập:
- Thang điểm: 10
- Kế hoạch kiểm tra như sau:
Trình Phương Công Chuẩn
Tỉ
lệ
(%)
Hình
thức
KT
Thời
độ
điểm năng
lực
pháp
đánh
giá
cụ
KT
đầu ra
KT
Nội dung
Kiểm tra giữa kỳ
50
Nội dung chương 1 + Tuần
3, 3
Thi tự
luận
Bài
kiểm
tra
G1.1,
G2.1,
BKT#1 2 : Toán rời rạc
5
Nội dung chương 4+
BKT#2 6 : Lý thuyết đồ thị
Tuần
12-
14
3, 3
Thi tự
luận
Bài
kiểm G4.1
tra
G2.2,
Thi cuối kỳ
50
- Nội dung bao quát tất
cả các chuẩn đầu ra
quan trọng của môn
học.
- Thời gian làm bài tối
thiểu 60-90 phút.
Thi tự
luận
Bài
kiểm
tra
G1.1,
G1.2,
G2.1,
G2.2,
G4.1
CĐR
Hình thức kiểm tra
môn học
G1.1
BKT #1
x
BKT #2
Thi cuối kỳ
x
17
G1.2
G2.1
G2.2
G2.3
G3.1
G3.2
G4.1
G4.2
G4.3
x
x
x
x
x
x
x
12. Tài liệu học tập
- Sách, giáo trình chính:
Nguyễn Hữu Anh, Toán rời rạc. ĐHKHTN TPHCM, 2003
Nguyễn Thành Sơn - Đặng Trường Sơn – Lê Văn Vinh – Trần
Công Tú – Nguyễn Quang Ngọc – Nguyễn Phương, Giáo trình Lý
thuyết đồ thị. ĐH SPKT TP.HCM 2012
- Sách (TLTK) tham khảo:
Trần Ngọc Danh, Toán rời rạc nâng cao, NXB ĐHQG
TP.HCM.
Trần Đan Thư - Dương Anh Đức, Lý thuyết đồ thị, NXB
ĐHQG TP.HCM.
Nguyễn Đức Nghĩa - Nguyễn Tô Thành, Toán rời rạc. NXB
Giáo dục,1999.
Kenneth H. Rosen, Toán học rời rạc ứng dụng trong tin học.
NXB Khoa học và Kỹ thuật, 1997
Robert Sedgewick, Cẩm nang thuật toán NXB Khoa học &
Kỹ thuật, 2004
13. Ngày phê duyệt lần đầu:
14. Cấp phê duyệt:
Trưởng khoa
Trưởng BM
Nhóm biên soạn
15. Tiến trình cập nhật ĐCCT
Lần 1: Nội Dung Cập nhật ĐCCT
(người cập nhật ký và
18
lần 1: ngày tháng năm
ghi rõ họ tên)
Tổ trưởng Bộ môn:
19
GIỚI THIỆU CÁC CHƯƠNG TRÌNH ĐÀO TẠO
1.
Sinh viên có kiến thức chuyên môn vững chắc về lĩnh vực Công
nghệ thông tin (Công nghệ phần mềm, Mạng máy tính, Hệ thống thông
tin); Sinh viên được chú trọng học tập cả về lý thuyết lẫn kỹ năng thực
hành nhằm đảm bảo Sinh viên ra trường có thể tiếp cận và làm việc ngay
tại các công ty.
Ra trường, Sinh viên có thể làm việc tại: Các công ty phần mềm,
các công ty cung cấp giải pháp mạng, các công ty cung cấp giải pháp hệ
thống thông tin trong nước cũng như quốc tế,… Có thể tham gia nghiên
cứu và giảng dạy tại các Viện nghiên cứu, Trường Đại học, Cao đẳng,
Trung cấp chuyên nghiệp, cũng như các Trường phổ thông; có thể làm
việc tại các công ty ngoài lĩnh vực CNTT nhưng có áp dụng triển khai
CNTT trong hoạt động, quản lý, sản xuất.
Hiện nay nhu cầu về kỹ sư phần mềm tại Việt Nam là rất lớn bởi sự
chuyển hướng đầu tư của các công ty nước ngoài vào Việt Nam. Ngoài
ra, SV sau khi hoàn thành chương trình đại học, có khả năng học tiếp lên
các bậc học cao hơn (thạc sỹ, tiến sỹ).
Được đào tạo tại khoa Công nghệ Thông tin và khoa Đào tạo Chất
lượng cao.
2.
Ngành Kỹ thuật dữ liệu trang bị cho sinh viên cho sinh viên kiến
thức cơ sở ngành về công nghệ thông tin, và kiến thức chuyên sâu về
phân tích, thiết kế, xây dựng các mô hình vật lý và mô hình lô-gic cho dữ
liệu, xây dựng hạ tầng dữ liệu (data infrastructure, data sets) và các công
cụ phục vụ việc thiết kế, dự đoán các sản phẩm tương lai.
Các kiến thức được trang bị cho sinh viên như: Cấu trúc dữ liệu và
giải thuật, lập trình hướng đối tượng, lập trình web, trí tuệ nhân tạo, Khai
phá dữ liệu, học máy, mô hình rủi ro tài chính, v.v…
Sinh viên tốt nghiệp có thể làm việc trong các công ty Công nghệ
thông tin, cũng như bộ phận công nghệ thông ty của các công ty ở các
lĩnh vực khác. Các vị trí có thể đảm nhận trong các tổ chức gồm:
- Data Engineer (Kỹ sư dữ liệu).
- Big data Engineer (Kỹ sư quản trị dữ liệu lớn).
- Lập trình viên, chuyên viên phát triển phần mềm.
- Chuyên viên quản trị cơ sở dữ liệu, quản trị web.
- Trưởng dự án phát triển hệ thống thông tin.
20
Tải về để xem bản đầy đủ
22 trang
09/01/2024
18120
Free
Bạn đang xem 20 trang mẫu của tài liệu "Đề cương chi tiết môn Toán rời rạc và lý thuyết đồ thị", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- de_cuong_chi_tiet_mon_toan_roi_rac_va_ly_thuyet_do_thi.pdf
