| TRƯỜNG ĐẠI HỌC NHA TRANG CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
KHOA CÔNG NGHỆ THÔNG TIN Độc lập - Tự do - Hạnh phúc
 Bộ môn: Hệ Thống Thông Tin
CHƯƠNG TRÌNH GIẢNG DẠY HỌC PHẦN
1. 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
Mã học phần: INS326 Số tín chỉ: 3
Đào tạo trình độ: Đại học
Học phần tiên quyết: Tin học cơ sở, Kỹ thuật lập trình.
Bộ môn quản lý học phần: Hệ thống Thông tin
Giảng dạy cho các lớp/nhóm: 55TH1
2. Mô tả tóm tắt học phần
Học phần trang bị cho người học kiến thức về 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..
3. Thông tin về giảng viên
Họ và tên: Trần Minh Văn Chức danh, học vị: Thạc sỹ
Điện thoại: 01225403070. Email: minhvan@ntu.edu.vn
Địa chỉ trang web/nguồn dữ liệu internet của giảng viên:……...
Địa điểm, lịch tiếp SV: Buổi sáng 2, 3, 4, 5, 6. văn phòng Bộ môn Hệ thống thông tin, Khoa Công nghệ thông tin. Giảng đường G6.
4. Mục tiêu và phương pháp dạy - học của các chủ đề
4.1 Mục tiêu và phương pháp dạy - học của các chủ đề lý thuyết
Chủ đề 1: Đánh giá độ phức tạp của thuật toán
Nội dung
|
Mục tiêu dạy - học
|
Phương pháp dạy - học
| -
Khái niệm độ phức tạp
|
SV nắm được các tham số ảnh hưởng đến tốc độ thực hiện thuật toán
|
Thuyết giảng
| -
Tính số lần thực hiện lệnh. Độ phức tạp
|
SV hiểu cách tính số lấn thực hiện lệnh. Phân biệt các trường hợp (n), (n2), (2n), (logn)
|
Thuyết giảng, giải bài tập
| -
Trường hợp tốt nhất, xấu nhất.
|
SV hiểu về trường hợp tốt nhất, xấu nhất
|
Thuyết giảng
| -
Độ phức tạp O
|
SV hiểu khái niệm độ phức tạp chặn trên. So sánh với
|
Thuyết giảng, giải bài tập
|
Chủ đề 2: Đệ qui.
Nội dung
|
Mục tiêu dạy – học
|
Phương pháp dạy – học
| -
Khái niệm đệ qui
|
SV hiểu về lớp bài toán quy nạp, truy hồi. Khái niệm hàm đệ qui
|
Thuyết giảng
| -
Giải thuật đệ qui
|
Một số bài toán kinh điển sử dụng giải thuật đệ quy
|
Thuyết giảng, giải bài tập, bài tập thực hành
| -
Giải thuật quay lui
|
SV hiểu các khái niệm quay lui, vét cạn, thử và sai. Áp dụng đệ quy để xử lý quay lui. Một số bài toán kinh điển về quay lui
|
Thuyết giảng, giải bài tập, bài tập thực hành
|
Chủ đề 3: Tìm kiếm và sắp xếp trên mảng.
Nội dung
|
Mục tiêu dạy - học
|
Phương pháp dạy - học
| -
Tìm kiếm nhị phân
|
Tìm kiếm nhị phân giúp giảm tốc độ thuật toán còn O(logn)
|
Thuyết giảng
| -
Các phương pháp sắp xếp đơn giản: Selection Sort, Insertion Sort, Bubble Sort.
|
Hiểu nguyên tắc sắp xếp. Tính được độ phức tạp giải thuật.
|
Thuyết giảng, minh họa video.
Giải bài tập
| -
Các phương pháp sắp xếp đệ quy: Quick Sort, Merge Sort.
|
Hiểu và so sánh được sự khác nhau giữa sắp xếp đơn giản và sắp xếp đệ quy chia để trị.
|
Thuyết giảng, minh họa video.
Giải bài tập.
| -
Ứng dụng của sắp xếp
|
SV biết cách ứng dụng sắp xếp vào các bài toán thực tế
|
Giải bài tập,
Bài tập thực hành
|
Chủ đề 4: Danh sách liên kết
Nội dung
|
Mục tiêu dạy - học
|
Phương pháp dạy - học
| -
Kiểu dữ liệu có cấu trúc. Con trỏ.
|
Phân biệt biến tĩnh và biến cấp phát động. Lý do cần có cấp phát động.
|
Thuyết giảng
| -
Danh sách liên kết
|
Cấu trúc tổ chức danh sách liên kết. Các thao tác trên danh sách liên kết
|
Thuyết giảng,
| -
Stack/ Queue.
|
Nguyên tắc của Stack và Queue
|
Thuyết giảng, giải bài tập
| -
Ứng dụng ngăn xếp:
|
Tính toán và chuyển đổi biểu thức hậu tố Balan.
|
Giải bài tập, Bài tập thực hành
|
Chủ đề 5: Cây nhị phân.
Nội dung
|
Mục tiêu dạy - học
|
Phương pháp dạy - học
| -
Cây tổng quát
|
Cấu trúc cây tổng quát, một số khái niệm liên quan.
|
Thuyết giảng
| -
Cây nhị phân và biểu diễn cây nhị phân
|
Sinh viên biết cách biểu diễn cây nhị phân trong máy tính.
|
Thuyết giảng
| -
Duyệt cây nhị phân
|
SV nằm được các phép duyệt theo thứ tự trước, giữa và sau.
|
Thuyết giảng, giải bài tập
Bài tập thực hành
| -
Biểu diễn cây nhị phân bằng mảng. Sắp xếp heap sort.
|
SV nắm được phương pháp sắp xếp HeapSort, độ phức tạp O(nlogn)
|
Thuyết giảng, giải bài tập
| -
Cây nhị phân tìm kiếm
|
Cây nhị phân giúp giảm thời gian tìm kiếm và thời gian thêm xóa sửa là O(logn)
|
Thuyết giảng, giải bài tập
|
4.2 Mục tiêu dạy - học của các chủ đề/bài thực hành
Chủ đề/bài thực hành
|
Mục tiêu dạy-học
|
1.Đệ quy và quay lui
|
Sinh viên rèn luyện kỹ năng lập trình đệ quy giải quyết các bài toán thực tế
|
2.Sắp xếp mảng
|
Sinh viên áp dụng các phương pháp sắp xếp mảng vào các bài toán thực tế
|
3.Danh sách ngăn xếp
|
Sinh viên rèn luyện kỹ năng sử dụng ngăn xếp vào các bài toán thực tế
|
4. Cây nhị phân
|
Sinh viên rèn luyện kỹ năng sử dụng cây nhị phân vào các bài toán thực tế
|
5. Phân bổ thời gian của học phần
Chủ đề lý thuyết
|
Số tiết
|
Chủ đề/bài thực hành
|
Số tiết
|
1
|
8
|
1
|
3
|
2
|
6
|
2
|
2
|
3
|
8
|
3
|
2
|
4
|
8
|
4
|
2
|
5
|
6
|
|
|
Tổng số tiết
|
36
|
Tổng số tiết
|
9
|
6. Tài liệu
TT
|
Tên tác giả
|
Tên tài liệu
|
Năm
xuất bản
|
Nhà
xuất bản
|
Địa chỉ khai thác tài liệu
|
1
|
Lê Minh Hoàng
|
Chuyên đề: Cấu trúc dữ liệu
|
2004
|
ĐHSP Hà Nội
|
Ebook
|
2
|
Đinh Mạnh Tường
|
Cấu trúc dữ liệu
|
2009
|
ĐH QG Hà Nội
|
Thư viện
|
3
|
A. V. Aho, J. E. Hopcroft, and J. D. Ullman
|
The Design and Analysis of Computer Algorithms
|
1983
|
Addison – Wesley, Reeding. Mass.,
|
GV cung cấp
|
4
|
Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest
|
Giáo trình Thuật toán
|
2002
|
Thống kê
|
Thư viện
|
7. Yêu cầu của giảng viên đối với học phần
-
Sinh viên xem tài liệu tham khảo, làm bài tập về nhà và trả lời câu hỏi kiểm tra trên website môn học: http://webmonhoc.ntu.edu.vn
-
Sinh viên giải bài tập trên website lập trình: http://laptrinh.ntu.edu.vn
8. Đánh giá kết quả học tập
8.1 Lịch kiểm tra giữa kỳ (dự kiến)
Lần kiểm tra
|
Tuần thứ
|
Hình thức kiểm tra
|
Chủ đề/Nội dung được kiểm tra
|
1.
|
8
|
Viết
|
Độ phức tạp giải thuật
Sắp xếp mảng
|
2.
|
10
|
Thực hành
|
Giải thuật đệ quy, sắp xếp mảng
|
8.2 Thang điểm học phần
TT
|
Điểm đánh giá
|
Trọng số
(%)
|
1
|
Điểm các lần kiểm tra giữa kỳ
|
20
|
2
|
Điểm chuyên cần/thái độ
|
10
|
3
|
Điểm thực hành
|
20
|
|
Thi kết thúc học phần:
-
Hình thức thi: Viết
-
Đề mở: □ Đề đóng:
|
50
|
TRƯỞNG BỘ MÔN GIẢNG VIÊN
(Ký và ghi họ tên) (Ký và ghi họ tên)
Phạm Thị Thu Thúy Trần Minh Văn
Chia sẻ với bạn bè của bạn: |
