Cấu trúc dữ liệu và giải thuật
Học kỳ 2, năm học 2025-2026
Lớp học phần: 67HTTT1 và 67HTTT2
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 LT = 3 buổi LT
Không vắng mặt quá 20% x 15 = 3 tiết TH = 1 buổi TH
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 (13/4 - 19/4)
LT1 (thứ tư): Giới thiệu môn học; Bổ sung kiến thức lập trình C++
LT2 (thứ bảy): Phân tích thuật toán
Tuần 2 (20/4 - 26/4)
LT3 (thứ tư): Phân tích thuật toán (tiếp)
LT4 (thứ bảy): Vector
Tuần 3 (4/5 - 10/5)
TH1 (thứ hai/năm): Thực hành vector
LT5 (thứ tư): Danh sách liên kết
LT6 (thứ bảy): Danh sách liên kết (tiếp)
Tuần 4 (11/5 - 17/5)
TH2 (thứ hai/năm): Thực hành danh sách liên kết
LT7 (thứ tư): Ngăn xếp và hàng đợi
LT8 (thứ bảy): Cây và cây nhị phân
Tuần 5 (18/5 - 24/5)
LT9 (thứ tư): Kiểm tra giữa kỳ
LT10 (thứ bảy): Cây nhị phân tìm kiếm
Tuần 6 (25/5 - 31/5)
TH4 (thứ hai/năm): Thực hành cây nhị phân tìm kiếm
LT11 (thứ tư): Cây AVL
LT12 (thứ bảy): Bảng băm
Tuần 7 (1/6 - 7/6)
TH5 (thứ hai/năm): Thực hành bảng băm
LT13 (thứ tư): Hàng đợi ưu tiên
LT14 (thứ bảy): Sắp xếp
Tuần 8 (8/6 - 14/6)
LT15 (thứ tư): Sắp xếp (tiếp)