TRƯỜNG ĐH TÀI CHÍNH – NGÂN HÀNG HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN TIN ỨNG DỤNG
ĐỀ CƯƠNG CHI TIẾT HỌC PHẦN
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Hệ đào tạo: Đại học chính quy
Ngành: Công nghệ thông tin
- Thông tin chung về học phần
– Tên học phần: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
(Data structures and algorithms)
– Mã học phần: DCT.02.06
– Số tín chỉ: 3 (60 tiết, mỗi tiết 45 phút)
– Phân bổ giờ tín chỉ đối với các hoạt động: (số lượng tiết)
+ Lý thuyết: 33 tiết
+ Bài tập lớn, thảo luận, kiểm tra: 9 tiết
+ Tự học: 18 tiết.
– Khoa, Bộ môn phụ trách học phần: Bộ môn Tin ứng dụng Khoa CNTT
- Các học phần tiên quyết
Các học phần tiên quyết:
- Tin cơ sở (Mã số DCT.02.03)
- Mục tiêu của học phần:
3.1 Mục tiêu chung:
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à giải thuật; các cấu trúc dữ liệu và các phương pháp sắp xếp, tìm kiếm cơ bản.
3.2 Mục tiêu cụ thể
- a) Về kiến thức: Trang bị cho sinh viên các kiến thức về cấu trúc dữ liệu và giải thuật. Các cấu trúc dữ liệu và các phương pháp sắp xếp, tìm kiếm cơ bản
- b) Về kỹ năng: Dạy cho sinh viên phương pháp tư duy logic, cách xây dựng các vấn đề, bài toán cũng như cách áp dụng các cấu trúc dữ liệu và giải thuật đó để lập trình giải quyết các bài toán thực tế.
- c) Về thái độ: Giúp sinh viên nhận thức được vai trò, trách nhiệm của người làm công việc phát triển ứng dụng tin học: cẩn thận, làm việc từng bước theo đúng quy trình.
- Chuẩn đầu ra của học phần
4.1. Nội dung chuẩn đầu ra học phần:
1) Về kiến thức:
CLO 1: Hiểu được các kiến thức về cấu trúc dữ liệu và giải thuật, các cấu trúc dữ liệu và các phương pháp sắp xếp, tìm kiếm cơ bản để vận dụng vào thực tế tin học hóa của doanh nghiệp.
CLO 2 Vận dụng được các kiến thức cấu trúc dữ liệu và giải thuật, các phương pháp sắp xếp tìm kiếm vào lập trình, giải quyết các bài toán thực tế.
CLO 3 Phân tích, đánh giá được tính hiệu quả của các cấu trúc dữ liệu và giải thuật, xây dựng các phần mềm ứng dụng trong doanh nghiệp với cấu trúc và giải thuật tối ưu.
2) Về kỹ năng
CLO 4: Có kỹ năng giải quyết, vận dụng kiến thức về cấu trúc dữ liệu và giải thuật vào việc thiết kế, lập trình các hệ thống phần mềm ứng dụng trong doanh nghiệp. Có kỹ năng phân tích, đánh giá các cấu trúc dữ liệu và giải thuật được áp dụng trong thiết kế phần mềm ứng dụng trong doanh nghiệp.
CLO 5: Có kỹ năng lãnh đạo, quản lý, làm việc nhóm trong các hoạt động thuộc lĩnh vực công nghệ thông tin.
CLO 6: Có kỹ thuyết trình, thương thảo trong các hoạt động thuộc lĩnh vực công nghệ thông tin.
3) Về phẩm chất
CLO 7: Có phẩm chất chính trị; có trách nhiệm công dân, trách nhiệm cộng đồng. Có đạo đức nghề nghiệp, có tinh thần hợp tác và thái độ phục vụ tốt. Năng động, có hoài bão về nghề nghiệp.
Ghi chú: CLO = Course Learning Outcomes = Chuẩn đầu ra của học phần.
4.2. Ma trận nhất quán giữa chuẩn đầu ra học phần (CLO) với chuẩn đầu ra chương trình đào tạo (PLO):
| PLO1 | PLO2 | PLO3 | PLO4 | PLO5 | PLO6 | PLO7 | PLO8 | PLO9 | |
| CLO 1 | H | M | M | ||||||
| CLO 2 | H | M | M | ||||||
| CLO 3 | H | M | M | ||||||
| CLO 4 | M | H | M | ||||||
| CLO 5 | M | H | M | ||||||
| CLO 6 | M | H | M | ||||||
| CLO 7 | M | H | M | ||||||
| Tổng hợp toàn bộ học phần | M | M | M |
Ghi chú:
– PLO = Program Learning Outcomes = Chuẩn đầu ra của chương trình đào tạo
– Mức độ đóng góp của CLO và PLO được xác định cụ thể như sau:
L (Low) – CLO có đóng góp ít vào PLO
M (Medium) – CLO có đóng góp vừa vào PLO
H (High) – CLO có đóng góp nhiều vào PLO
Chú thích: H – cao; M – vừa; L – thấp – phụ thuộc vào mức hỗ trợ của CLO đối với PLO ở mức bắt đầu (L) hoặc mức nâng cao hơn mức bắt đầu; có nhiều cơ hội được thực hành, thí nghiệm, thực tế (mức M) hay mức thuần thục, thành thạo (H)).
4.3. Ma trận nhất quán giữa phương pháp, hình thức kiểm tra, đánh giá với chuẩn đầu ra học phần (CLO)
Ghi chú: Khi xây dựng bảng này, xem mục 5.1 để về các hình thức kiểm tra, đánh giá mà giảng viên sử dụng khi giảng dạy học phần
| Hình thức đánh giá | CLO1 | CLO2 | CLO3 | CLO4 | CLO5 | CLO6 | CLO7 |
| 1. Chuyên cần | H | H | H | M | M | M | M |
| 2. Vấn đáp | |||||||
| 3. Viết | H | H | H | M | M | M | M |
| 4. Thực hành | H | H | H | H | H | H | H |
4.4. Ma trận nhất quán giữa phương pháp dạy học với chuẩn đầu ra học phần (CLO)
| Phương pháp giảng dạy | CLO1 | CLO2 | CLO3 | CLO4 | CLO5 | CLO6 | CLO7 |
| 1. Thuyết trình (Trực tiếp, Online) | M | M | M | M | M | M | M |
| 2. Dạy & học thực hành | H | H | H | H | H | H | H |
| 4. Hướng dẫn tự học | M | M | M | M | M | M | M |
4.5. Ma trận nhất quán các chương với chuẩn đầu ra học phần (CLO)
Chú thích: I: Introduction/ Giới thiệu
P: Proficient/ Thuần thục, đủ
A: Advanced/ Nâng cao
| CLO1 | CLO2 | CLO3 | CLO4 | CLO5 | CLO6 | CLO7 | |
| Bài 1 | I | I | I | P | P | P | P |
| Bài 2 | A | A | A | I | I | I | P |
| Bài 3 | A | A | A | A | A | A | P |
| Bài 4 | A | A | A | I | I | I | P |
| Bài 5 | A | A | A | I | I | I | P |
| Bài 6 | A | A | A | I | I | I | P |
| Bài 7 | A | A | A | I | I | I | P |
| Bài 8 | A | A | A | I | I | I | P |
| Bài 9 | A | A | A | I | I | I | P |
| Bài 10 | A | A | A | I | I | I | P |
| Bài 11 | A | A | A | I | I | I | P |
| Bài 12 | A | A | A | I | I | I | P |
| Bài 13 | A | A | A | I | I | I | P |
| Bài 14 | A | A | A | I | I | I | P |
| Bài 15 | A | A | A | I | I | I | P |
| Bài 16 | A | A | A | I | I | I | P |
| Bài 17 | A | A | A | I | I | I | P |
| Bài 18 | A | A | A | I | I | I | P |
| Bài 19 | A | A | A | I | I | I | P |
| Bài 20 | A | A | A | I | I | I | P |
(Xem chi tiết tiêu đề các Bài dạy ở Mục 8)
- Nhiệm vụ của sinh viên
- Tham dự giờ lên lớp: tối thiểu 80% số tiết học trên lớp, trong phòng thực hành có sự giảng dạy, hướng dẫn trực tiếp của giáo viên;
– Bài tập, thảo luận:
+ Đọc tài liệu, chuẩn bị và tham gia thảo luận theo hướng dẫn của giáo viên;
+ Thực hiện đầy đủ các bài tập được giao;
– Làm bài kiểm tra định kỳ;
– Tham gia thi kết thúc học phần.
- Tài liệu học tập:
6.1. Giáo trình chính:
[1]. Đinh Mạnh Tường (2013), Cấu trúc dữ liệu và giải thuật, NXB Khoa học và Kỹ thuật
6.2. Sách tham khảo:
[1]. Hàn Viết Thuận, Nguyễn Anh Phương 2014), Giáo trình Cấu trúc dữ liệu và giải thuật, NXB ĐH Kinh tế Quốc dân. [2]. Đỗ Xuân Lôi (2006), Cấu trúc dữ liệu và giải thuật, NXB ĐHQG Hà nội.- Mô tả vắn tắt nội dung học phần:
Học phần gồm: Các kiến thức cơ bản về giải thuật; cách diễn đạt và đánh giá giải thuật; các phương pháp phân tích, thiết kế giải thuật; giải thuật đệ qui; một số cấu trúc dữ liệu và các phương pháp sắp xếp, tìm kiếm cơ bản..
Các nội dung trên được trình bày trong 3 chương sau:
Chương 1:Giải thuật. Nội dung chủ yếu của chương này là nêu các khái niệm cơ bản về giải thuật, phân tích thiết kế giải thuật từ bài toán đến chương trình, phân tích giải thuật, đánh giá giải thuật. Các khái niệm và giải thuật đệ quy, cách thiết kế giải thuật đệ quy và hiệu lực của đệ quy.
Chương 2: Cấu trúc dữ liệu. Nội dung chủ yếu của chương này là nêu các cấu trúc dữ liệu cơ bản: mảng, danh sách liên kết, ngăn xếp, hàng đợi, cây và đồ thị
Chương 3: Sắp xếp và tìm kiểm. Nội dung chủ yếu của chương này là nêu khái niệm về sắp xếp, các phương pháp sắp xếp từ cơ bản đến nâng cao, các bài toán và giải thuật tìm kiếm
- Kế hoạch giảng dạy:
| Bài dạy | Nội dung giảng dạy | Số tiết
(LT, BT, TH) |
Tài liệu đọc trước | Nhiệm vụ của sinh viên |
| Bài 1 | Chương 1. GIẢI THUẬT
1.1. Các khái niệm cơ bản về giải thuật 1.1.1. Giải thuật và cấu trúc dữ liệu 1.1.2. Các vấn đề liên quan 1.1.3. Diễn đạt giải thuật |
3 tiết LT | Đọc trước giáo trình | |
| Bài 2 | 1.2. Phân tích và thiết kế giải thuật
1.2.1.Từ bài toán đến chương trình 1.2.2. Phân tích thiết kế giải thuật 1.2.3.Đánh giá giải thuật |
3 tiết LT
|
Tự nghiên cứu | |
| Bài 3 | 1.3. Đệ qui và giải thuật đệ qui
1.3.1. Khái niệm về đệ qui 1.3.2. Giải thuật và thủ tục đệ qui 1.3.3. Thiết kế giải thuật đệ qui 1.3.4. Hiệu lực của đệ qui |
3 tiết LT | Đọc trước giáo trình | |
| Bài 4 | Kiểm tra giữa kỳ | 3 tiết trên lớp | Ôn tập và nghiên cứu giáo trình các phần đã học | |
| Bài 5 | Chương 2. CẤU TRÚC DỮ LIỆU
2.1. Mảng và danh sách 2.1.1. Các khái niệm 2.1.2. Cấu trúc lưu trữ mảng |
3 tiết LT | Đọc trước giáo trình | |
| Bài 6 | 2.1.3. Danh sách tuyến tính
2.1.4. Danh sách móc nối 2.1.6. Áp dụng |
3 tiết LT | Tự nghiên cứu | |
| Bài 7 | 2.2. Ngăn xếp và hàng đợi
2.2.1. Stack 2.2.2. Ứng dụng của Stack |
3 tiết LT
|
Đọc trước giáo trình | |
| Bài 8 | 2.2.3. Queue
2.2.4. Stack và queue móc nối |
3 tiết LT | Đọc trước giáo trình | |
| Bài 9 | 2.3. Cây
2.3.1. Định nghĩa và khái niệm 2.3.2. Cây nhị phân |
3 tiết LT | Đọc trước giáo trình | |
| Bài 10 | 2.3.3. Cây tổng quát
2.3.4. Áp dụng |
3 tiết LT | Tự nghiên cứu | |
| Bài 11 | 2.4. Đồ thị
2.4.1. Định nghĩa và khái niệm 2.4.2. Biểu diễn đồ thị |
3 tiết LT | Đọc trước giáo trình | |
| Bài 12 | 2.4.3. Phép duyệt đồ thị
2.4.4. Cây khung tối thiểu |
3tiết LT | Tự nghiên cứu | |
| Bài 13 | Kiểm tra giữa kỳ | 3 tiết trên lớp | Ôn tập và nghiên cứu giáo trình các phần đã học | |
| Bài 14 | Chương 3. SẮP XẾP, TÌM KIẾM
3.1. Sắp xếp 3.1.1. Khái niệm chung 3.1.2. Các phương pháp sắp xếp cơ bản (chọn, chèn, đổi chỗ) |
3 tiết LT | Đọc trước giáo trình | |
| Bài 15 | 3.1.3. Sắp xếp kiểu phân đoạn | 3 tiết LT | Đọc trước giáo trình | |
| Bài 16 | 3.1.4. Sắp xếp kiểu vun đống | 3 tiết LT | Tự nghiên cứu | |
| Bài 17 | 3.2. Tìm kiếm
3.2.1. Bài toán 3.2.2. Tìm kiếm tuần tự |
3 tiết LT | Đọc trước giáo trình | |
| Bài 18 +19 | 3.2.3. Tìm kiếm nhị phân
3.2.4. Cây nhị phân tìm kiếm 3.2.5. Cây nhị phân cân đối AVL |
6 tiết LT | Tự nghiên cứu | |
| Bài 20 | Kiểm tra cuối kỳ | 3 tiết trên lớp | Ôn tập và nghiên cứu giáo trình các phần đã học |
- Cơ sở vật chất phục vụ giảng dạy:
– Tên giảng đường:
– Danh mục trang thiết bị: Projector, Phòng máy tính thực hành với máy tính có cấu hình phù hợp, cài đặt được các phần mềm phục vụ dạy và học.
- Kiểm tra, đánh giá kết quả học tập:
10.1. Phương pháp, hình thức kiểm tra, đánh giá
10.1.1 Kiểm tra – đánh giá thường xuyên: Trên lớp (Lấy điểm chuyên cần)
| STT | Hình thức đánh giá | Trọng số | Yêu cầu chung, mục đích, minh chứng |
| 1. | Điểm chuyên cần: Đánh giá mức độ thực hiện các nhiệm vụ sinh viên, bao gồm việc tham gia học tập trên lớp và kiểm tra, đánh giá thường xuyên trên lớp | 10% | + Mục đích: Giúp sinh viên duy trì ý thức, kỷ luật trong học tập.
+ Yêu cầu: · Sinh viên đi học đều đặn, đúng giờ. · Sinh viên thực hiện đầy đủ các yêu cầu chuẩn bị học tập của GV. |
10.1.2. Kiểm tra – đánh giá định kỳ, thi kết thúc học phần
| STT | Hình thức đánh giá | Trọng số | Yêu cầu chung, mục đích, minh chứng |
| 1. | 03 bài kiểm tra tự luận 60 phút | 30% | + Mục đích: Giúp sinh viên củng cố kiến thức đã được học.
+ Yêu cầu: Sinh viên làm việc độc lập |
| 2. | Bài thi hết học phần tự luận 90 phút | 60% | + Mục đích: Đánh giá kết quả học tập toàn bộ học phần của SV.
+ Yêu cầu: Sinh viên làm việc theo nhóm và thực hiện nhiệm vụ theo sự phân công của Trưởng nhóm. |
10.2. Miêu tả chi tiết các bài kiểm tra trong kỳ, bài thi hết học phần và bộ tiêu chí đánh giá:
– Bài kiểm tra trong kỳ, bài thi hết học phần: Viết bài.
– Mô tả chi tiết:
(1) Sinh viên sẽ làm 03 bài kiểm tra viết 60 phút vào giữa kỳ và cuối kỳ trong phạm vi nội dung đã được học.
(2) Sinh viên sẽ làm bài thi hết học phần theo hình thức bài tự luận.
(3) Các bài kiểm tra viết này thể hiện kết quả học trên lớp, tự học, thực hành, làm bài tập mà sinh viên đã thưc hiện cũng như khả năng vận dụng những kiếm thức đã được học.
- Tiêu chí đánh giá bài kiểm tra tự luận trong kỳ và thi tự luận hết học phần
| Tiêu chí đánh giá | Mức chất lượng | Thang điểm |
| · Nội dung đủ, trả lời đúng 100% câu hỏi.
· Trình bày rõ ràng, diễn đạt ngắn gọn, súc tích, logic. · Không có lỗi về thuật ngữ chuyên môn. · Không có lỗi chính tả. |
Xuất sắc |
9-10 |
| · Trả lời đúng 70-80% câu hỏi.
· Trình bày rõ ràng, diễn đạt logic. · Mắc ít lỗi (1-2 lỗi) về thuật ngữ chuyên môn. · Còn lỗi chính tả. |
Khá- Giỏi |
7-8 |
| · Trả lời đúng 50-60% câu hỏi.
· Trình bày không rõ ý, chưa logic. · Mắc lỗi về thuật ngữ chuyên môn (3-4 lỗi). · Còn lỗi chính tả. |
Trung bình |
5-6 |
| · Trả lời sai, lạc đề, hoặc phần trả lời đúng dưới mức 50% câu hỏi.
· Không làm hết câu hỏi, bỏ nội dung hơn 50%. · Trình bày tối nghĩa, diễn đạt không rõ ý. · Mắc nhiều lỗi về thuật ngữ chuyên môn (5-6 lỗi). · Nhiều lỗi chính tả. |
Yếu |
3-4 |
| · Trả lời sai, lạc đề, phần trả lời đúng dưới mức 20%.
· Không làm hết câu hỏi, bỏ đến 80% nội dung. · Trình bày tối nghĩa, diễn đạt không rõ ý. · Nhiều lỗi chính tả. |
Kém |
0-2 |
- Tiêu chí đánh giá Bài tập lớn
| Tiêu chí đánh giá | Mức chất lượng | Thang điểm |
| · Thực hiện đầy đủ và xuất sắc yêu cầu của Bài tập lớn
· Khảo sát và đặc tả yêu cầu nghiệp vụ tốt · Phân tích, thiết kế tốt · Xây dựng, cài đặt được ứng dụng và kiểm thử lỗi tốt. · Bố cục rõ ràng, cấu trúc phù hợp, văn phong khoa học · Trình bày Bài tập lớn (phần nhiệm vụ được giao) rõ ràng, diễn đạt logic. · Trả lời được tất cả các câu hỏi của GV |
Xuất sắc |
9-10 |
| · Thực hiện đầy đủ yêu cầu của Bài tập lớn
· Khảo sát và đặc tả yêu cầu nghiệp vụ tốt · Phân tích, thiết kế tốt · Xây dựng và cài đặt được ứng dụng chạy tốt. · Bố cục rõ ràng, cấu trúc phù hợp, văn phong khoa học · Trình bày Bài tập lớn (phần nhiệm vụ được giao) rõ ràng, diễn đạt logic. · Trả lời đúng 70-80% câu hỏi của GV. |
Khá- Giỏi |
7-8 |
| · Thực hiện hầu hết yêu cầu của Bài tập lớn
· Khảo sát và đặc tả yêu cầu nghiệp vụ đầy đủ · Phân tích, thiết kế còn có một số sai sót. · Xây dựng và cài đặt được ứng dụng nhưng còn có một số lỗi. · Cấu trúc Báo cáo chưa thật phù hợp · Trình bày Bài tập lớn (phần nhiệm vụ được giao) còn lúng túng. · Trả lời đúng 50-60% câu hỏi của GV. |
Trung bình |
5-6 |
| · Thực hiện được ít yêu cầu của Bài tập lớn
· Khảo sát và đặc tả yêu cầu nghiệp vụ sơ sài, còn thiếu và nhiều sai sót. · Phân tích, thiết kế không tốt, có nhiều lỗi. · Xây dựng và cài đặt được ứng dụng nhưng chưa chạy được. · Trình bày Bài tập lớn (phần nhiệm vụ được giao) còn lúng túng, chưa hiểu hết các nhiệm vụ được giao. · Trả lời đúng 30-40% câu hỏi của GV. |
Yếu |
3-4 |
| · Thực hiện được rất ít yêu cầu của Bài tập lớn
· Khảo sát và đặc tả yêu cầu nghiệp vụ rất sơ sài, còn thiếu rất nhiều và nhiều sai sót. · Phân tích, thiết kế không tốt, có rất nhiều lỗi. · Chưa xây dựng và cài đặt được ứng dụng. · Trình bày Bài tập lớn (phần nhiệm vụ được giao) còn lúng túng, không hiểu các nhiệm vụ được giao. · Trả lời đúng dưới 20% câu hỏi của GV.. |
Kém |
0-2 |
10.3. Chính sách trong đánh giá chuyên cần:
– Sinh viên vắng mặt quá 20% số buổi sẽ không được làm bài thi kết thúc học phần.
– Có điểm thưởng cho sinh viên tích cực phát biểu, ham học hỏi, có sự sáng tạo trong thảo luận, tranh biện.
Hà Nội, ngày 31 tháng 10 năm 2019
| Hiệu trưởng
PGS.TS. Phạm Ngọc Ánh |
Trưởng Khoa
TS. Phùng Văn Ổn |
Trưởng bộ môn
ThS. Vũ Minh Tâm |
Người soạn đề cương
ThS. Vũ Minh Tâm |
Facebook
