Cấu trúc dữ liệu và giải thuật
Học kỳ 1, năm học 2026-2027
Lớp học phần: 66KTRB.1 và 66KTRB.2
Giảng viên: Nguyễn Mạnh Hiển
Liên hệ: hiennm@tlu.edu.vn
Giới thiệu môn học
Số tiết: 30 lý thuyết + 15 thực hành (3 tín chỉ).
Môn học cung cấp kiến thức cơ bản về các cấu trúc dữ liệu (tức là phương pháp tổ chức dữ liệu trong bộ nhớ máy tính) và phân tích thuật toán (tức là ước lượng thời gian chạy của các thuật toán).
Nội dung chính: Phân tích thuật toán; danh sách, ngăn xếp, hàng đợi; cây nhị phân tìm kiếm, cây AVL; bảng băm; hàng đợi ưu tiên; các thuật toán sắp xếp. Vì thời lượng môn học có hạn, một số nội dung không được đưa vào giảng dạy, bao gồm đồ thị (có trong môn Toán rời rạc) và các kỹ thuật thiết kế thuật toán (có trong môn Thuật toán ứng dụng).
Thực hành dùng ngôn ngữ lập trình C++ và môi trường phát triển Dev-C++. Vì môn Nhập môn lập trình (học trước môn này) chưa giảng dạy một số kiến thức C++ cần thiết, môn học này sẽ có một buổi giới thiệu bổ sung các kiến thức lập trình đó.
Giáo trình
Bản gốc: Data Structures and Algorithm Analysis in C++ (Mark A. Weiss, 3rd ed., 2006).
Bản dịch: Cấu trúc dữ liệu và phân tích thuật toán trong C++ (Có thể mượn ở Thư viện Trường Đại học Thủy Lợi).
Đánh giá môn học
Điểm quá trình: 50%
Chuyên cần: 20% (điểm danh)
Bài tập lập trình: 40% (giao trong các buổi thực hành)
Kiểm tra giữa kỳ: 40% (tự luận, 35 phút, 2-3 câu hỏi, không dùng tài liệu)
Điểm thi kết thúc học phần: 50%
Trắc nghiệm trên phần mềm iTest
60 phút, 40 câu hỏi, không dùng tài liệu
Điều kiện dự thi kết thúc học phần:
Không vắng mặt quá 20% x 30 = 6 tiết = 3 buổi lý thuyết
Không vắng mặt quá 20% x 15 = 3 tiết = 1 buổi thực hành
Có tham dự bài kiểm tra giữa kỳ và đạt 4 điểm trở lên
Lịch giảng dự kiến
Tuần 1 (31/8 - 6/9)
Thứ 6 (LT1): Giới thiệu môn học; Bổ sung kiến thức lập trình C++
Tuần 2 (7/9 - 13/9)
Thứ 3 (LT2): Phân tích thuật toán
Thứ 6 (LT3): Phân tích thuật toán (tiếp)
Tuần 3 (14/9 - 20/9)
Thứ 3 (LT4): Vector (Nghỉ học do mưa ngập)
Thứ 6 (LT5): Danh sách liên kết
Tuần 4 (21/9 - 27/9)
Thứ 3 (LT6): Danh sách liên kết (tiếp)
Thứ 6 (LT7): Ngăn xếp và hàng đợi
Thứ 4/7 (TH1): Thực hành vector
Tuần 5 (28/9 - 4/10)
Thứ 3 (LT8): Cây và cây nhị phân
Thứ 6 (LT9): Kiểm tra giữa kỳ
Thứ 4/7 (TH2): Thực hành danh sách liên kết
Tuần 6 (5/10 - 11/10)
Thứ 3 (LT10): Cây nhị phân tìm kiếm
Thứ 6 (LT11): Cây AVL
Tuần 7 (12/10 - 18/10)
Thứ 3 (LT12): Bảng băm
Thứ 6 (LT13): Hàng đợi ưu tiên
Thứ 4/7 (TH4): Thực hành cây nhị phân tìm kiếm
Tuần 8 (19/10 - 25/10)
Thứ 3 (LT14): Sắp xếp
Thứ 6 (LT15): Sắp xếp
Thứ 4/7 (TH5): Thực hành bảng băm và hàng đợi ưu tiên