Đề Cương Chi Tiết Môn Algorithms and Data Structures | Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

lOMoAR cPSD| 58605085
,TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT
Ngành đào tạo: Công nghệ Cơ điện tử TP. HỒ CHÍ MINH
Trình độ đào tạo: Đại học
KHOA CƠ KHÍ CHẾ TẠO MÁY
Chương trình đào tạo: Công nghệ Cơ điện tử
Đề cương chi tiết môn học
1. Tên môn học: Cấu trúc dữ liệu và giải thuật
Mã môn học: DSAL220229
2. Tên Tiếng Anh: DATA STRUCTURE AND ALGORITHMS
3. Số tín chỉ: 2 tín chỉ (2/0/4) 2 tín chỉ lý thuyết, 0 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 + 0 tiết thực hành + 4 tiết tự học/ tuần)
4. Các giảng viên phụ trách môn học: 1/ Th.S. Lê Thanh Tùng 2/ TS. Huỳnh Quang Duy 3/ Th.S. Trần Tiến Đức
5. Điều kiện tham gia học tập môn họcMôn học tiên quyết: Không Môn học trước: Không.
6. Mô tả môn học (Course Description)
Môn học nhằm cung cấp cho người học những kiến thức cơ bản về các cấu trúc dữ liệu cơ bản
và các thuật toán cơ bản: phân tích và xây dựng cấu trúc dữ liệu, phân tích ưu nhược điểm của cấu
trúc dữ liệu để lựa chọn cấu trúc dữ liệu và giải thuật phù hợp.
7. Chuẩn đầu ra của môn học (CLOs) CLOs
Mô tả (Sau khi học xong môn học này, người học có thể:) ELO(s)/PI(s) TĐNL
Hiểu và giải thích được các kiến thức cơ bản cấu trúc dữ liệu và ELO1/ CLO1 giải thuật PI 1.1 3
Trình bày được cú pháp lệnh và áp dụng được các cấu trúc dữ ELO1/ CLO2
liệu về mảng, danh sách liên kết, hàng đợi, ngăn xếp, cây nhị PI1.2 3 phân
Trình bày được và áp dụng các thuật toán sắp xếp và tìm kiếm ELO1/ CLO3 trên cấu trúc dữ liệu PI1.2 3
Trình bày được cách khai báo và áp dụng các kiểu cấu trúc dữ ELO1/ CLO4
liệu để lưu trữ và quản lý dữ liệu PI1.2 3
Phân tích, đánh giá tính hiệu quả của cấu trúc dữ liệu và giải ELO1/ CLO5
thuật áp dụng cho bài toán thực tế PI1.3 3
Có kỹ năng tự đọc và nghiên cứu các tài liệu tham khảo ELO4/ CLO6 PI4.1 3
8.Nội dung chi tiết môn học: lOMoAR cPSD| 58605085 Trìn
Chuẩn h độ Phương Phương Tuần Nội dung
đầu ra năng pháp dạy pháp đánh
môn học lực học giá
Chương 1: Giới thiệu tổng quan
A/ Các nội dung và PPGD chính trên lớp: (3) CLO1 3 - - Làm bài
Nội dung GD lý thuyết: Thuyết tập - Trả
1.1 Giới thiệu tổng quan về cấu trúc dữ liệu và giải giảng - lời câu
thuật: các khái niệm cơ bản, các thuật ngữ thường Trình hỏi một gặp chiếu - vấn đề
1 1.2 Giới thiệu các bài toán, ứng dụng liên quan đến Thảo đưa ra
cấu trúc dữ liệu và giải thuật luận thảo luận nhóm cho phần học này
B/ Các nội dung cần tự học ở nhà: (6) CLO1 - Đọc tài liệu - Làm bài tập.
Chương 2: Cấu trúc dữ liệu cơ bản
A/ Tóm tắt các ND và PPGD chính trên lớp: (3) CLO1 3 - - Làm bài
Nội dung GD lý thuyết: Thuyết tập - Trả
2.1 Các khái niệm cơ bản: giảng - lời câu Trình hỏi một
+ Kiểu dữ liệu có cấu trúc. chiếu - vấn đề
+ Cấu trúc dữ liệu (Data structure) Thảo đưa ra
+ Kiểu dữ liệu cơ bản trong C luận thảo luận
2.2 Cấu trúc điều khiển trong C nhóm cho phần + Cấu trúc điều kiện học này 2 + Cấu trúc lặp 2.3 Hàm trong C + Khai báo hàm trong C + Sử dụng hàm
B/ Các nội dung cần tự học ở nhà: (6) CLO1 - Đọc tài liệu - Làm bài tập. 3
Chương 2: Cấu trúc dữ liệu cơ bản (tt) lOMoAR cPSD| 58605085
A/ Các nội dung và PPGD chính trên lớp: (3) CLO3 3 - - Làm bài
Nội dung GD lý thuyết: Thuyết tập - Trả 2.4 Mảng: giảng - lời câu Trình hỏi một
+ Các khái niệm về Mảng (Array) chiếu - vấn đề
+ Cấu trúc lưu trữ mảng Thảo đưa ra
2.5 Danh sách liên kết (Linked List) luận thảo luận nhóm + Danh sách tuyến tính cho phần
+ Danh sách liên kết đơn học này
+ Danh sách liên kết đôi
+ Danh sách liên kết vòng
B/ Các nội dung cần tự học ở nhà: (6) CLO6 - Đọc tài liệu - Làm bài tập.
Chương 2: Cấu trúc dữ liệu cơ bản (tt)
A/ Các nội dung và PPGD chính trên lớp: (3) CLO4 3 - - Làm bài
Nội dung GD lý thuyết: Thuyết tập - Trả
2.6 Ngăn xếp (Stack): giảng - lời câu + Khái niệm cơ bản. Trình hỏi một chiếu - vấn đề + Ứng dụng của 4 Thảo đưa ra Stack 2.7 Hàng đợi luận thảo luận (Queue): nhóm cho phần + Giới thiệu Queue học này + Stack và Queue
B/ Các nội dung cần tự học ở nhà: (6) CLO6
Viết chương trình về các lệnh cấu trúc.
Tìm hiểu thêm về các phép toán trên mảng
Chương 2: Cấu trúc dữ liệu cơ bản (tt)
A/ Các nội dung và PPGD chính trên lớp: (3) CLO4 3 - - Làm bài
Nội dung GD lý thuyết: Thuyết tập - Trả 2.8 Cây: giảng - lời câu + Khái niệm cơ bản. Trình hỏi một chiếu - vấn đề 5 + Cây nhị phân. Thảo đưa ra + Cây tổng quát luận thảo luận + Duyệt cây nhóm cho phần học này
B/ Các nội dung cần tự học ở nhà: (6) CLO4
Viết chương trình về các lệnh cấu trúc.
Tìm hiểu thêm về các phép toán trên mảng lOMoAR cPSD| 58605085 6
Chương 2: Cấu trúc dữ liệu cơ bản (tt)
A/ Các nội dung và PPGD chính trên lớp: (3) CLO2 3 - - Làm bài
Nội dung GD lý thuyết: Thuyết tập - Trả
2.9 Các cấu trúc dữ liệu khác: giảng - lời câu + Bảng băm (Hash Table) Trình hỏi một chiếu - vấn đề
+ Hàm băm (Hash function) Thảo đưa ra luận thảo luận nhóm cho phần học này
B/ Các nội dung cần tự học ở nhà: (6) CLO6 - Đọc tài liệu - Làm bài tập..
Chương 3: Giải thuật (Algorithms)
A/ Các nội dung và PPGD chính trên lớp: (3) CLO2 3 -Thuyết - Làm bài
Nội dung GD lý thuyết: CLO3 giảng - tập - Trả
3.1 Các khái niệm cơ bản: Trình chiếu lời câu - Thảo luận hỏi một + Giới thiệu về Giải nhóm vấn đề thuật + Các giải thuật đưa ra 7 cơ bản 3.2 Đệ qui: thảo luận + Định nghĩa cho phần + Giải thuật đệ quy học này + Đệ quy và lặp
B/ Các nội dung cần tự học ở nhà: (6) CLO6 - Đọc tài liệu - Làm bài tập. CLO7
Chương 3: Giải thuật (Algorithms) (tt)
A/ Các nội dung và PPGD chính trên lớp: (3) CLO4 3 - Làm - Làm bài
3.3 Giải thuật sắp xếp: CLO5 mẫu tập
+ Giới thiệu bài toán sắp xếp - Thảo + Bubble sort luận 8 nhóm + Selection sort + Insertion sort
B/ Các nội dung cần tự học ở nhà: (6) CLO2 - Đọc tài liệu - Làm bài tập. 9
KIỂM TRA QUÁ TRÌNH lOMoAR cPSD| 58605085 CLO2 3 -Thuyết - Làm bài CLO3 giảng - tập - Trả CLO4 Trình chiếu lời câu
A/ Các nội dung và PPGD chính trên lớp: (3) CLO5 - Thảo luận hỏi một
Nội dung GD lý thuyết: nhóm vấn đề -
Kiểm tra đánh giá các nội dung đã học đưa ra thảo luận cho phần học này
B/ Các nội dung cần tự học ở nhà: (6) CLO5 - Đọc tài liệu - Làm bài tập. 10
Chương 3: Giải thuật (Algorithms) (tt)
A/ Các nội dung và PPGD chính trên lớp: (3) CLO5 3 -Thuyết - Làm bài
Nội dung GD lý thuyết: giảng - tập - Trả
3.3 Giải thuật sắp xếp: Trình chiếu lời câu - Thảo luận hỏi một + Merger sort và Quick sort nhóm vấn đề + Heap sort đưa ra + Radix sort thảo luận cho phần học này
B/ Các nội dung cần tự học ở nhà: (6) CLO6 - Đọc tài liệu - Làm bài tập.
Chương 3: Giải thuật (Algorithms) (tt)
A/ Các nội dung và PPGD chính trên lớp: (3) CLO4 3 - Làm - Làm bài
Nội dung GD lý thuyết: CLO5 mẫu tập
3.4 Giải thuật tìm kiếm: - Thảo luận + Giới thiệu 11 nhóm + Tìm kiếm tuần tự
+ Tìm kiếm theo bước nhảy (Jump search)
B/ Các nội dung cần tự học ở nhà: (6) CLO2 - Đọc tài liệu - Làm bài tập.
12 Chương 3: Giải thuật (Algorithms) (tt) lOMoAR cPSD| 58605085
A/ Các nội dung và PPGD chính trên lớp: (3) CLO6 3 -Thuyết - Làm bài
Nội dung GD lý thuyết: giảng - tập - Trả
3.4 Giải thuật tìm kiếm: Trình chiếu lời câu - Thảo luận hỏi một + Tìm kiếm nhị phân nhóm vấn đề
+ Tìm kiếm nhị phân cải tiến đưa ra thảo luận cho phần học này
B/ Các nội dung cần tự học ở nhà: (6) - Đọc tài liệu CLO6 - Làm bài tập.
Chương 3: Giải thuật (Algorithms) (tt)
A/ Các nội dung và PPGD chính trên lớp: (3) CLO4 3 -Thuyết - Làm bài
Nội dung GD lý thuyết: giảng - tập - Trả CLO5 Trình chiếu lời câu 13
3.5 Thuật toán đồ thị: - Thảo luận hỏi một
+ Giới thiệu về đồ thị: các bài toán và ứng dụng nhóm vấn đề
+ Thuật toán tìm đường đi ngắn nhất đưa ra thảo luận cho phần học này
B/ Các nội dung cần tự học ở nhà: (6) - Đọc tài liệu CLO2 - Làm bài tập..
Chương 3: Giải thuật (Algorithms) (tt)
A/ Các nội dung và PPGD chính trên lớp: (3) CLO4 3 - Làm - Làm bài
Nội dung GD lý thuyết: CLO5 mẫu tập
3.6 Thuật toán dạng cây: - Thảo luận 14 + Giới thiệu về cây nhóm + Duyệt cây
B/ Các nội dung cần tự học ở nhà: (6) CLO6 - Đọc tài liệu - Làm bài tập. 15 ÔN TẬP lOMoAR cPSD| 58605085
A/ Các nội dung và PPGD chính trên lớp: (3) CLO4 3 -Thuyết - Làm bài
Nội dung GD lý thuyết: giảng - tập - Trả CLO5
- Ôn tập toàn bộ nội dung đã học Trình chiếu lời câu - Thảo luận hỏi một nhóm vấn đề đưa ra thảo luận cho phần học này
B/ Các nội dung cần tự học ở nhà:
(6) - Đọc tài liệu - Làm bài tập. 9.
Phương pháp giảng dạy: - Phương pháp thuyết
trình - Phương pháp thảo luận nhóm
10. Đánh giá sinh viên: - Thang điểm: 10
- Kế hoạch kiểm tra như sau: Chuẩn Trình Hình Phương Thời đầu ra độ Công cụ Tỉ lệ thức Nội dung đánh năng pháp KT điểm đánh giá (%) giá đánh giá lực Bài tập trên lớp 20
Lần 1 Cho một bài toán cơ bản, yêu Tuần 8 CLO1 3 Quan sát Rubric 10 cầu sinh viên xây dựng CLO2 3
chương trình để giải quyết CLO3 CLO4
Cho một bài toán liên quan Tuần CLO5 3
cấu trúc dữ liệu và tập tin, yêu 13 CLO6 2 Lần 2 cầu sinh viên xây dựng Quan sát Rubric 10
chương trình để giải quyết Kiểm tra quá trình 30
- Bài kiểm tra tổng hợp các Tuần CLO1 3 30
kiến thức từ tuần 1 đến tuần 9 10 CLO2 3 Câu hỏi Trắc
- Thời gian làm bài 60 phút. CLO3 trắc 3 nghiệm nghiệm CLO4 Thi cuối kỳ 50 - Nội dung bao quát tất CLO3 3 50
cả cácchuẩn đầu ra quan CLO4 3 Câu hỏi trọng của môn học. Trắc CLO5 3 trắc - Thời gian làm bài 60 nghiệm CLO6 3 nghiệm phút. lOMoAR cPSD| 58605085
Nội dung giảng dạy
Hình thức kiểm tra CĐR môn học Chương Chương Chương 1 Lần 1 Lần 2 Quá trình CUỐI KỲ 2 3 CLO1 X X X X CLO2 X X X X CLO3 X X X X CLO4 X X X X X CLO5 X X X CLO6 X X X X X
11. Tài liệu học tập
- Sách, giáo trình chính: - Sách, giáo trình chính:
1. Michael T. Goodrich and Roberto Tamassia, Data structures and Algorithms in C++, Wiley2019
- Sách (TLTK) tham khảo:
1. Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, The
MIT Press and McGraw-Hill Book Company, 2020 12. Thông tin chung:
Đạo đức khoa học:
Sinh viên phải tuân thủ nghiêm các quy định về Đạo đức khoa học của Nhà trường (số
1047/QĐĐHSPKT ngày 14/3/2022). Nghiêm cấm bất kỳ hình thức đạo văn (sao chép) nào trong quá
trình học cũng như khi làm báo cáo hay thi cử. Mọi vi phạm về đạo đức khoa học của SV sẽ được xử lý theo quy định. Lưu ý thay đổi:
Các thông tin trong ĐCCT này có thể bị thay đổi trong quá trình giảng dạy tùy theo mục đích của
GV. SV cần cập nhật thường xuyên thông tin của lớp học phần đã đăng ký. Quyền tác giả:
Toàn bộ nội dung giảng dạy, tài liệu học tập của học phần này được bảo vệ bởi quy định về Sở hữu
trí tuệ (số 934/QĐ-ĐHSPKT ngày 12/3/2020) của trường ĐH SPKT TPHCM. Nghiêm cấm bất kỳ
hình thức sao chép, chia sẻ mà chưa được sự cho phép của tác giả. 13.
Ngày phê duyệt lần đầu: 14. Cấp phê duyệt:
Trưởng Khoa Trưởng Bộ môn Nhóm Biên soạn 15.
15. Tiến trình cập nhật ĐCCT
Nội Dung Cập nhật ĐCCT lần 1:
<người cập nhật ký và ghi rõ họ tên> Tổ trưởng Bộ môn:
Nội Dung Cập nhật ĐCCT lần 2:
<Đã đọc và thông qua> 16.