Cấu trúc dữ liệu và thuật toán - Cấu trúc dữ liệu và giải thuật (ET2100) | Trường Đại học Bách khoa Hà Nội

Cấu trúc dữ liệu và thuật toán - Cấu trúc dữ liệu và giải thuật (ET2100) | Trường Đại học Bách khoa Hà Nội được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo. Mời bạn đọc đón xem!

lOMoARcPSD| 44729304
CẤU TRÚC DỮ LIỆU THUẬT TOÁN
Phiên bản:
1. THÔNG TIN CHUNG
Tên học phần:
Cấu trúc dữ liệu và thuật toán
(Data structures and Algorithms)
Mã số học phần:
IT3011
Khối lượng:
2(2-1-0-4)
- Lý thuyết: 30 tiết
- Bài tập/Bài tập lớn: 15 tiết
Học phần tiên quyết:
Học phần học trước:
- IT1110: Tin học ại cương
Học phần song hành:
Không
2. MÔ TẢ HỌC PHẦN
3. Cung cấp cho sinh viên những kiến thức bản về cấu trúc dữ liệu thuật toán cần thiết
cho việc phát triển thuật toán cài ặt phần mềm giải quyết các vấn ứng dụng. Sau khi
hoàn thành học phần này, sinh viên có khả năng hiểu, cài ặt và áp dụng các cấu trúc dữ liệu
cơ bản như ngăn xếp, hàng ợi, hàng ợi ưu tiên, danh sách, cây và bảng băm vào các bài
toán ứng dụng toán. Sinh viên phải có khả năng thiết kế và cài ặt các chương trình trong ó
có sử dụng các cấu trúc dữ liệu ể phát triển các hệ thống xử lý thông tin. Sinh viên hiểu và
cài ặt ược các thuật toán tìm kiếm, sắp xếp cơ bản như sắp xếp nhanh, sắp xếp vun ống, sắp
xếp trộn, bảng băm và các thuật toán cơ bản trên ồ thị. Sinh viên phải nắm ược các kỹ thuật
xây dựng thuật toán cơ bản như ệ qui, tham lam, chia ể trị, quy hoạch ộng ể giải quyết các
bài toán tính toán. Sinh viên biết cách phân tích ược ộ phức tạp trong ngôn ngữ ký hiệu tiệm
cận của các cấu trúc dữ liệu và thuật toán cơ bản.
4. MỤC TIÊU VÀ CHUẨN ĐẦU RA CỦA HỌC PHẦN
Sinh viên hoàn thành học phần này có khả năng:
Mục
tiêu/CĐR
Mô tả mục tiêu/Chuẩn ầu ra của học phần
CĐR ược phân
bổ cho HP/ Mức
ộ(I/T/U)
[1]
[2]
[3]
M1
Hiểu và có khả năng áp dụngcấu trúc dữ liệu và thuật
toán giải quyết các bài toán tính toán trong các hệ
thống phần mềm
1.1.4; 1.2.3;
1.2.5; 1.3.3;
1.3.4; 1.5.3; 1.6.3
lOMoARcPSD| 44729304
M1.1
Hiểu ược ý nghĩa tầm quan trọng của các kỹ thuật thuật
toán và cấu trúc dữ liệu trong việc giải quyết các bài toán
tính toán trong các hệ thống phần mềm
[1.1.4] (I); [1.2.3]
(I); [1.2.5](I);
[1.3.3](I);
[1.3.4](I);
[1.5.3](I);
[1.6.3](I)
Mục
tiêu/CĐR
Mô tả mục tiêu/Chuẩn ầu ra của học phần
CĐR ược phân
bổ cho HP/ Mức
ộ(I/T/U)
M1.2
Nhận diện hiểu các yêu cầu tính toán trong hệ
thốngphần mềm
[1.1.4] (I); [1.2.3]
(I); [1.2.5](I);
[1.3.3](I);
[1.3.4](I);
[1.5.3](I);
[1.6.3](I)
M1.3
Áp dụng cấu trúc dữ liệu và thuật toán ể giải quyết các vấn
ề tính toán trong hệ thống phần mềm
[1.2.1] (U)
M2
khnăng ánh giá, lựa chọn, vàề xuất giải phápvề
cấu trúc lưu trữ vàthuật toántốiưu hoáhiệu năng cho
các bài toán tính toán trong các hệ thống phần mềm
2.1.3; 2.1.4;
2.2.3; 2.3.4; 2.5.3
M2.1
Hiểu ánh giá ược hiệu quả của các giải pháp tính toán
trong các hệ thống phần mềm
[2.1.3](I);
[2.1.4](I);
[2.2.3](I);
M2.2
Có khả năng ề xuất giải pháp về cấu trúc lưu trữ và thuật
toán ể tối ưu hoá hiệu năng tính toán trong hệ thống phần
mềm
[2.3.4](T);
[2.5.3] (U)
5. TÀI LIỆU HỌC TẬP
Giáo trình
[1] Nguyễn Đức Nghĩa. Giáo trình Cấu trúc dữ liệu và giải thuật. ĐHBK Hà Nội, 2013.
[2] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms.
Second Edition, MIT Press, 2001.
Sách 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 ĐHQG Hà nội, 2005.
[2] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and
Algorithms. Addison-Wesley, 1983.
[3] Robert Sedgewick. Algorithms in C. Third Edition. Addison-Wesley, 1998.
[4] Robert Sedgewick. Algorithms in C++, Parts 1-4: Fundamentals, Data Structures,
Sorting, Searching. 3th Edition, Addison-Wesley, 1999.
[5] Robert Sedgewick. Algorithms in C++ Part 5: Graph Algorithms (3rd Edition). 3th
Edition, Addison-Wesley, 2002.
Điểm thành phần
Phương pháp ánh
giá cụ thể
CĐR ược
ánh giá
Tỷ
trọng
lOMoARcPSD| 44729304
[6] Michael T. Goodrich, Roberto Tamassia, David M. Mount,Data Structures and
Algorithms in C++. 704 pages. Wiley, 2003.
[7] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms .
Second Edition, MIT Press, 2001.
6. CÁCH ĐÁNH GIÁ HỌC PHẦN
[1]
[2]
[4]
[5]
A1. Điểm quá trình (*)
Đánh giá quá trình
M1.1, M1.2,
M1.3, M2.1,
M2.2
40%
A2. Điểm cuối kỳ
Thi cuối kỳ
M1.1, M1.2,
M1.3, M2.1,
M2.2
60%
* Điểm quá trình sẽ ược iều chỉnh bằng cách cộng thêm iểm chuyên cần. Điểm chuyên cần có
giá trị từ –2 ến +1, theo Quy chế Đào tạo ại học hệ chính quy của Trường ĐH Bách khoa
Hà Nội.
7. KẾ HOẠCH GIẢNG DẠY
Tuần
Nội dung
CĐR
học
phần
Hoạt ộng dạy
và học
Bài
ánh
giá
[1]
[2]
[3]
[4]
[5]
1
CHƯƠNG 1. CÁC KHÁI NIỆM CƠ BẢN
1.1. Định nghĩa và khái niệm cơ bản
1.2. Mã giả
1.2. Độ phức tạp tính toán
1.3. Ký hiệu tiệm cận
1.4 Ví dụ mở ầu
M1.1
M1.2
Giảng bài; làm
bài tập; thảo
luận
A1
2
CHƯƠNG 2. SƠ ĐỒ THUẬT TOÁN CƠ
BẢN
2.1. Đệ quy
2.2. Đệ quy có nhớ
2.3. Đệ quy quay lui
M2.1
Giảng bài; làm
bài tập; thảo
luận
A1, A2
3
CHƯƠNG 2. SƠ ĐỒ THUẬT TOÁN CƠ
BẢN
2.4. Thuật toán nhánh và cận
2.5. Thuật toán tham lam
M1.1,
M1.2,
M1.3,
M2.1,
M2.2
Giảng bài; làm
bài tập; thảo
luận
A1
A2
lOMoARcPSD| 44729304
4
CHƯƠNG 2.SƠ ĐỒ THUẬT TOÁN CƠ
BẢN
2.6. Chia ể trị
2.7 Quy hoạch ộng
M1.1;
M1.2;
M1.3;
M2.1;
M2.2
Giảng bài; làm
bài tập; thảo
luận
A1, A2
5
CHƯƠNG 3. DANH SÁCH TUYẾN TÍNH
3.1. Định nghĩa danh sách tuyến tính
3.2 Kiểu dữ liệu trừu tượng danh sách tuyến
tính
3.3 Mảng
3.4 Danh sách liên kết ơn
Tuần
Nội dung
CĐR
học
phần
Hoạt ộng dạy
và học
Bài
ánh
giá
[1]
[2]
[3]
[4]
[5]
6
CHƯƠNG 3. DANH SÁCH TUYẾN TÍNH
3.5 Danh sách liên kết ôi
3.6. Ngăn xếp
3.7. Hàng ợi
M1.1;
M1.2;
M1.3;
M2.1;
M2.2
Giảng bài; làm
bài tập; thảo
luận
A1
A2
7
CHƯƠNG 4. CÂY
4.1. Định nghĩa cây
4.2. Các khái niệm trên cây
4.3. Các phép duyệt cây
4.4. Cấu trúc lưu trữ
4.5 Cài ặt các thao tác trên cây
M1.1;
M1.2;
M1.3;
M2.1;
M2.2
Giảng bài; làm
bài tập; thảo
luận
A1
A2
8
CHƯƠNG 5. SẮP XẾP
5.1. Giới thiệu bài toán sắp xếp
5.2. Sắp xếp lựa chọn
5.3 Sắp xếp chèn
5.4 Sắp xếp nổi bọt
M1.2;
M1.3;
M2.1;
M2.2
Giảng bài; làm
bài tập; thảo
luận
A1, A2
9
Ôn tập / Kiểm tra giữa kỳ
M1.1;
M1.2;
M1.3;
M2.1;
M2.2
kiểm tra giữa kỳ
bằng hình thức
thi viết hoặc bài
tập lớn
A1
10
CHƯƠNG 5. SẮP XẾP
5.3. Sắp xếp trộn
5.4. Sắp xếp nhanh
5.5. Sắp xếp vun ống
M1.2;
M1.3;
M2.1;
M2.2
Giảng bài; làm
bài tập; thảo
luận
A1
A2
lOMoARcPSD| 44729304
11
CHƯƠNG 6. TÌM KIẾM
6.1. Tìm kiếm tuần tự và tìm kiếm nhị phân
6.2. Cây nhị phân tìm kiếm
6.3. Giới thiệu cây nhị phân tìm kiếm cân
bằng
M1.2;
M1.3;
M2.1;
M2.2
Giảng bài; làm
bài tập; thảo
luận
A1
A2
12
CHƯƠNG 6. TÌM KIẾM
6.4. Bảng băm và ứng dụng
M1.2;
M1.3;
M2.1;
M2.2
Giảng bài; làm
bài tập; thảo
luận
A1
A2
13
CHƯƠNG 7. Đồ thị
7.1. Định nghĩa và khái niệm
7.2. Biểu diễn ồ thị
M1.2;
M1.3;
Giảng bài; làm
bài tập; thảo
luận
A1
A2
Tuần
Nội dung
CĐR
học
phần
Hoạt ộng dạy
và học
Bài
ánh
giá
[1]
[2]
[3]
[4]
[5]
7.3. Duyệt ồ thị: DFS, BFS
M2.1;
M2.2
14
CHƯƠNG 7. Đồ thị
7.4. Cây khung nhỏ nhất trên ồ thị và cấu trúc
Disjoint Set
7.5 Đường i ngắn nhất trên ồ thị và cấu trúc
hàng ợi ưu tiên
M1.2;
M1.3;
M2.1;
M2.2
Giảng bài; làm
bài tập; thảo
luận
A1
A2
15
Tổng kết – Hướng dẫn ôn tập – Giải áp thắc
mắc
Bài tập; thảo
luận
8. QUY ĐỊNH CỦA HỌC PHẦN
(Các quy ịnh của học phần nếu có)
9. NGÀY PHÊ DUYỆT: …………………..
Chủ tịch Hội ồng Nhóm xây dựng ề cương
10. QUÁ TRÌNH CẬP NHẬT
Lần
cập
nhật
Nội dung iều chỉnh
Ngày
tháng
ược phê
duyệt
Áp dụng từ
kỳ/khóa
Ghi chú
lOMoARcPSD| 44729304
1
……………
2
……………………
| 1/6

Preview text:

lOMoAR cPSD| 44729304
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN Phiên bản: 1. THÔNG TIN CHUNG Tên học phần:
Cấu trúc dữ liệu và thuật toán
(Data structures and Algorithms)
Mã số học phần: IT3011 Khối lượng: 2(2-1-0-4)
- Lý thuyết: 30 tiết
- Bài tập/Bài tập lớn: 15 tiết
Học phần tiên quyết:
Học phần học trước: -
IT1110: Tin học ại cương
Học phần song hành: Không
2. MÔ TẢ HỌC PHẦN
3. Cung cấp cho sinh viên những kiến thức cơ bản về cấu trúc dữ liệu và thuật toán cần thiết
cho việc phát triển thuật toán và cài ặt phần mềm giải quyết các vấn ề ứng dụng. Sau khi
hoàn thành học phần này, sinh viên có khả năng hiểu, cài ặt và áp dụng các cấu trúc dữ liệu
cơ bản như ngăn xếp, hàng ợi, hàng ợi có ưu tiên, danh sách, cây và bảng băm vào các bài
toán ứng dụng toán. Sinh viên phải có khả năng thiết kế và cài ặt các chương trình trong ó
có sử dụng các cấu trúc dữ liệu ể phát triển các hệ thống xử lý thông tin. Sinh viên hiểu và
cài ặt ược các thuật toán tìm kiếm, sắp xếp cơ bản như sắp xếp nhanh, sắp xếp vun ống, sắp
xếp trộn, bảng băm và các thuật toán cơ bản trên ồ thị. Sinh viên phải nắm ược các kỹ thuật
xây dựng thuật toán cơ bản như ệ qui, tham lam, chia ể trị, quy hoạch ộng ể giải quyết các
bài toán tính toán. Sinh viên biết cách phân tích ược ộ phức tạp trong ngôn ngữ ký hiệu tiệm
cận của các cấu trúc dữ liệu và thuật toán cơ bản.
4. MỤC TIÊU VÀ CHUẨN ĐẦU RA CỦA HỌC PHẦN
Sinh viên hoàn thành học phần này có khả năng: CĐR ược phân Mục
Mô tả mục tiêu/Chuẩn ầu ra của học phần bổ cho HP/ Mức tiêu/CĐR ộ(I/T/U) [1] [2] [3] M1
Hiểu và có khả năng áp dụngcấu trúc dữ liệu và thuật 1.1.4; 1.2.3;
toán giải quyết các bài toán tính toán trong các hệ 1.2.5; 1.3.3; thống phần mềm 1.3.4; 1.5.3; 1.6.3 lOMoAR cPSD| 44729304
M1.1 Hiểu ược ý nghĩa và tầm quan trọng của các kỹ thuật thuật [1.1.4] (I); [1.2.3]
toán và cấu trúc dữ liệu trong việc giải quyết các bài toán (I); [1.2.5](I);
tính toán trong các hệ thống phần mềm [1.3.3](I); [1.3.4](I); [1.5.3](I); [1.6.3](I) CĐR ược phân Mục
Mô tả mục tiêu/Chuẩn ầu ra của học phần bổ cho HP/ Mức tiêu/CĐR ộ(I/T/U)
M1.2 Nhận diện và hiểu rõ các yêu cầu tính toán trong hệ [1.1.4] (I); [1.2.3] thốngphần mềm (I); [1.2.5](I); [1.3.3](I); [1.3.4](I); [1.5.3](I); [1.6.3](I)
M1.3 Áp dụng cấu trúc dữ liệu và thuật toán ể giải quyết các vấn [1.2.1] (U)
ề tính toán trong hệ thống phần mềm M2
Có khả năng ánh giá, lựa chọn, vàề xuất giải phápvề 2.1.3; 2.1.4;
cấu trúc lưu trữ vàthuật toántốiưu hoáhiệu năng cho 2.2.3; 2.3.4; 2.5.3
các bài toán tính toán trong các hệ thống phần mềm
M2.1 Hiểu và ánh giá ược hiệu quả của các giải pháp tính toán [2.1.3](I);
trong các hệ thống phần mềm [2.1.4](I); [2.2.3](I);
M2.2 Có khả năng ề xuất giải pháp về cấu trúc lưu trữ và thuật [2.3.4](T);
toán ể tối ưu hoá hiệu năng tính toán trong hệ thống phần [2.5.3] (U) mềm 5. TÀI LIỆU HỌC TẬP Giáo trình
[1] Nguyễn Đức Nghĩa. Giáo trình Cấu trúc dữ liệu và giải thuật. ĐHBK Hà Nội, 2013.
[2] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms.
Second Edition, MIT Press, 2001. Sách 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 ĐHQG Hà nội, 2005.
[2] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and
Algorithms. Addison-Wesley, 1983.
[3] Robert Sedgewick. Algorithms in C. Third Edition. Addison-Wesley, 1998.
[4] Robert Sedgewick. Algorithms in C++, Parts 1-4: Fundamentals, Data Structures,
Sorting, Searching. 3th Edition, Addison-Wesley, 1999.
[5] Robert Sedgewick. Algorithms in C++ Part 5: Graph Algorithms (3rd Edition). 3th
Edition, Addison-Wesley, 2002. Phương pháp ánh CĐR ược Tỷ Điểm thành phần giá cụ thể Mô tả ánh giá trọng lOMoAR cPSD| 44729304
[6] Michael T. Goodrich, Roberto Tamassia, David M. Mount,Data Structures and
Algorithms in C++. 704 pages. Wiley, 2003.
[7] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms .
Second Edition, MIT Press, 2001.
6. CÁCH ĐÁNH GIÁ HỌC PHẦN [1] [2] [3] [4] [5]
A1. Điểm quá trình (*) Đánh giá quá trình Thi viết M1.1, M1.2, 40% M1.3, M2.1, M2.2
A2. Điểm cuối kỳ Thi cuối kỳ Thi viết M1.1, M1.2, 60% M1.3, M2.1, M2.2
* Điểm quá trình sẽ ược iều chỉnh bằng cách cộng thêm iểm chuyên cần. Điểm chuyên cần có
giá trị từ –2 ến +1, theo Quy chế Đào tạo ại học hệ chính quy của Trường ĐH Bách khoa Hà Nội.
7. KẾ HOẠCH GIẢNG DẠY CĐR Bài Hoạt ộng dạy Tuần Nội dung học ánh phần và học giá [1] [2] [3] [4] [5] 1
CHƯƠNG 1. CÁC KHÁI NIỆM CƠ BẢN M1.1 Giảng bài; làm A1
1.1. Định nghĩa và khái niệm cơ bản bài tập; thảo M1.2 1.2. Mã giả luận
1.2. Độ phức tạp tính toán 1.3. Ký hiệu tiệm cận 1.4 Ví dụ mở ầu 2
CHƯƠNG 2. SƠ ĐỒ THUẬT TOÁN CƠ
M2.1 Giảng bài; làm A1, A2 BẢN bài tập; thảo 2.1. Đệ quy luận 2.2. Đệ quy có nhớ 2.3. Đệ quy quay lui 3
CHƯƠNG 2. SƠ ĐỒ THUẬT TOÁN CƠ M1.1, Giảng bài; làm A1 BẢN M1.2, bài tập; thảo A2
2.4. Thuật toán nhánh và cận M1.3, luận 2.5. Thuật toán tham lam M2.1, M2.2 lOMoAR cPSD| 44729304 4
CHƯƠNG 2.SƠ ĐỒ THUẬT TOÁN CƠ
M1.1; Giảng bài; làm A1, A2 BẢN M1.2; bài tập; thảo 2.6. Chia ể trị M1.3; luận 2.7 Quy hoạch ộng M2.1; M2.2 5
CHƯƠNG 3. DANH SÁCH TUYẾN TÍNH
3.1. Định nghĩa danh sách tuyến tính
3.2 Kiểu dữ liệu trừu tượng danh sách tuyến tính 3.3 Mảng
3.4 Danh sách liên kết ơn CĐR Bài Hoạt ộng dạy Tuần Nội dung học ánh phần và học giá [1] [2] [3] [4] [5] 6
CHƯƠNG 3. DANH SÁCH TUYẾN TÍNH M1.1; Giảng bài; làm A1
3.5 Danh sách liên kết ôi M1.2; bài tập; thảo A2 3.6. Ngăn xếp M1.3; luận 3.7. Hàng ợi M2.1; M2.2 7 CHƯƠNG 4. CÂY M1.1; Giảng bài; làm A1 4.1. Định nghĩa cây M1.2; bài tập; thảo A2 luận
4.2. Các khái niệm trên cây M1.3; M2.1; 4.3. Các phép duyệt cây M2.2 4.4. Cấu trúc lưu trữ
4.5 Cài ặt các thao tác trên cây 8 CHƯƠNG 5. SẮP XẾP
M1.2; Giảng bài; làm A1, A2
5.1. Giới thiệu bài toán sắp xếp M1.3; bài tập; thảo 5.2. Sắp xếp lựa chọn luận M2.1; 5.3 Sắp xếp chèn M2.2 5.4 Sắp xếp nổi bọt 9
Ôn tập / Kiểm tra giữa kỳ M1.1; kiểm tra giữa kỳ A1 M1.2; bằng hình thức M1.3; thi viết hoặc bài M2.1; tập lớn M2.2 10 CHƯƠNG 5. SẮP XẾP M1.2; Giảng bài; làm A1 5.3. Sắp xếp trộn M1.3; bài tập; thảo A2 5.4. Sắp xếp nhanh luận M2.1; 5.5. Sắp xếp vun ống M2.2 lOMoAR cPSD| 44729304 11 CHƯƠNG 6. TÌM KIẾM M1.2; Giảng bài; làm A1
6.1. Tìm kiếm tuần tự và tìm kiếm nhị phân M1.3; bài tập; thảo A2
6.2. Cây nhị phân tìm kiếm luận M2.1;
6.3. Giới thiệu cây nhị phân tìm kiếm cân M2.2 bằng 12 CHƯƠNG 6. TÌM KIẾM M1.2; Giảng bài; làm A1
6.4. Bảng băm và ứng dụng M1.3; bài tập; thảo A2 M2.1; luận M2.2 13 CHƯƠNG 7. Đồ thị M1.2; Giảng bài; làm A1
7.1. Định nghĩa và khái niệm M1.3; bài tập; thảo A2 7.2. Biểu diễn ồ thị luận CĐR Bài Hoạt ộng dạy Tuần Nội dung học ánh phần và học giá [1] [2] [3] [4] [5]
7.3. Duyệt ồ thị: DFS, BFS M2.1; M2.2 14 CHƯƠNG 7. Đồ thị M1.2; Giảng bài; làm A1
7.4. Cây khung nhỏ nhất trên ồ thị và cấu trúc M1.3; bài tập; thảo A2 Disjoint Set M2.1; luận
7.5 Đường i ngắn nhất trên ồ thị và cấu trúc M2.2 hàng ợi ưu tiên 15
Tổng kết – Hướng dẫn ôn tập – Giải áp thắc Bài tập; thảo mắc luận
8. QUY ĐỊNH CỦA HỌC PHẦN
(Các quy ịnh của học phần nếu có)
9. NGÀY PHÊ DUYỆT: …………………..
Chủ tịch Hội ồng
Nhóm xây dựng ề cương
10. QUÁ TRÌNH CẬP NHẬT Ngày Lần tháng Áp dụng từ cập
Nội dung iều chỉnh ược phê Ghi chú kỳ/khóa nhật duyệt lOMoAR cPSD| 44729304 1 …………… 2 ……………………