---

1.Tên học phần:CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (ALGORITHMS AND DATA STRUCTURES)
2.Hệ đào tạo: Đại học
3.Ngành: CNTT
4.Mã học phần: 412CDG240
5.Loại môn học: Cơ sở ngành bắt buộc
6.Khoa: CNTT
7.Thời lượng: 4 dvht
-Lý thuyết: 45 tiết
-Thực hành: 14 tiết
-Kiểm tra: 1 tiết.
8.Yêu cầu kiến thức: Toán cao cấp A1, A2, A3
9.Giới thiệu học phần:
Mục đích môn học nhằm giúp học sinh nắm bắt được phương pháp tổ chức lưu trữ thông tin máy tính. Từ đó biết lựa chọn cấu trúc dữ liệu để giải quyết các bài toán. Nội dung môn học bao gồm hai phần: Những vấn đề cơ bản và mối quan hệ giữa cấu trúc dữ liệu và giải thuật, phân tích thiết kế thuật toán, giải thuật đệ qui; Giới thiệu một số cấu trúc dữ liệu (mảng, danh sách, cây, đồ thị...), thuật toán sắp xếp, tìm kiếm.
II. ĐỀ CƯƠNG CHI TIẾT
Chương 1: Phân tích, thiết kế giải thuật
1.1.Giải thuật và ngôn ngữ diễn đạt giải thuật
1.2.Các bước cơ bản để giải quyết tập bài toán
1.3.Chiến lược thiết kế giải thuật
1.4.Phân tích giải thuật độ phức tạp thời gian và độ phức tạp tính toán
Chương 2: Giải thuật đệ qui
2.1.Khái niệm về đệ qui
2.2.Thiết kế giải thuật đệ qui
2.2.1.Bài toán tháp Hà Nội
2.2.2.Áp dụng giải thuật đệ qui cho bài toán sắp xếp
2.3.Đệ qui và qui nạp toán học
Bài tập
Chương 3 : Mảng và danh sách tuyến tính
3.1.Các khái niệm mảng và danh sách tuyến tính
3.2.Cấu trúc dữ liệu lưu trữ của mảng
3.3.Cấu trúc lưu trữ kế tiếp của danh sách tuyến tính
3.4.Danh sách kiểu ngăn xếp (Stack)
3.5.Danh sách kiểu hàng đợi (Queue)
Bài tập
Chương 4: Danh sách móc nối
4.1.Danh sách móc nối đơn
4.2.Danh sách móc nối vòng
4.3.Danh sách móc nối kép
4.4.Stack và Queue móc nối
Bài tập
Chương 5: Cây
5.1.Định nghĩa và khái niệm
5.2.Cây nhị phân
5.2.1.Định nghĩa, tính chất
5.2.2.Biểu diễn cây nhị phân
5.2.3.Phép duyệt
5.3.Cây tổng quát
5.3.1. Biểu diễn
5.3.2. Phép duyệt
Bài tập
Chương 6: Các giải thuật sắp xếp và tìm kiếm
6.1. Một số phương pháp sắp xếp đơn giản
6.2. Sắp xếp kiểu phân đoạn (Quicksort)
6.3. Sắp xếp kiểu vun đống (Heapsort)
6.4. Sắp xếp kiểu hoà trộn (Mergesort)
6.5. Nhận xét, đánh giá
6.6. Tìm kiếm tuần tự
6.7. Tìm kiếm nhị phân
6.8. Cây nhị phân tìm kiếm
6.9. Nhận xét, đánh giá
Bài tập
III. TÀI LIỆU HỌC TẬP
- Tài liệu tham khảo
[1]. Đỗ Xuân Lôi. Cấu trúc dữ liệu và giải thuật. Nhà xuất bản Khoa học và Kỹ thuật, 1998
[2]. Nguyễn Xuân Huy. Thuật toán. Nhà xuất bản Thống kê, 1988
[3]. Robert Sedgewick. Algorithms. Bản dịch tiếng Việt, Nhà xuất bản Khoa học và Kỹ thuật, 1994
[4]. Nicklaus Wirth. Algorithms+Data structure=Program. Bản dịch tiếng Việt, Nhà xuất bản Khoa học và Kỹ thuật, 1993
http://www.e-ptit.edu.vn/hoctap/hoclieu/CTDLGT.pdf