Cấu trúc dữ liệu và giải thuật
Trần Minh Thái Email: minhthai@itc.edu.vn Website: www.minhthai.edu.vn
1
NỘI DUNG
Thông tin môn học
1
Mục tiêu môn học
2
Yêu cầu đối với sinh viên
3
Phương pháp và thang điểm đánh giá
4
Công cụ, phần mềm sử dụng học tập
5
2
Thông tin môn học
Tên học phần: Cấu trúc dữ liệu & giải thuật
Số tín chỉ: 2
Phân bổ thời gian giảng dạy, học tập:
Giờ giảng trên lớp: 30 tiết (2 tiết/ tuần x 15 tuần)
Giờ tự học của sinh viên: 60 giờ
Các học phần tiên quyết
3
Tin học đại cương
Kỹ thuật lập trình Cơ bản và nâng cao
Tóm tắt nội dung môn học
Cung cấp cho sinh viên những kiến thức nâng
cao về lập trình cấu trúc, cách thức tổ chức cấu
trúc dữ liệu: danh sách liên kết, hàng đợi, ngăn
xếp, cây nhị phân tìm kiếm, kỹ thuật sắp xếp cơ
bản trên mảng một chiều lưu trên bộ nhớ chính
như: Interchange Sort, Selection Sort, Insertion
Sort, Quick Sort, …
4
Tài liệu tham khảo
Giáo trình chính: Trần Hạnh Nhi – Dương Anh Đức, Giáo trình cấu trúc dữ liệu 1, NXB ĐH CNTT Tp. HCM, 2003
Tài liệu tham khảo:
[1] Nguyễn Trung Trực, Cấu trúc dữ liệu và giải
[2] Robert Sedgewick, Cẩm nang thuật toán tập 1
thuật, NXB ĐH Bách Khoa Tp. HCM, 1990
5
(bản dịch), NXB Khoa học kỹ thuật, 2004
Mục tiêu môn học
ủ ấ
ữ ệ
§ N m v ng vai trò c a c u trúc d li u và
ắ ả
ữ ậ i thu t
gi
ượ
§ Tính toán đ
c các phép so sánh hay phép
ặ
ị
hoán v (gán) khi cài đ t các gi
ả ượ
ắ
ữ
ậ i thu t c các gi
ắ
§ N m v ng và minh h a đ ế
ả
ậ ề
ả ộ ợ
ặ ượ
ả
i thu t tìm ki m, s p x p trên m ng m t chi u, danh sách liên k t đ n, hàng đ i, ị ngăn x p, cây nh phân tìm ki m c các gi
ế § Cài đ t đ
ọ ế ế ơ ế ậ ằ i thu t b ng C/ C++ 6
Yêu cầu đối với sinh viên
Đọc trước tài liệu, làm bài tập về nhà
Tham gia đầy đủ các buổi học, ra vào lớp
đúng giờ, trao đổi, đóng góp ý kiến tích cực
trong buổi học
Làm đầy đủ các bài kiểm tra tại lớp
Cài đặt các bài tập bằng C/C++
7
Một số qui định
Vắng mặt từ 2 lần kiểm tra tại lớp trở lên sẽ bị
cấm thi
Khi vào lớp học phải có tài liệu học tập
Không làm việc riêng trong lớp học
Hoàn thành các bài tập, thực hành, kiểm tra
theo đúng thời gian qui định
8
ộ ầ
Lịch học Tu nầ
N i dung
ề ả ổ ng 1. T ng quan v gi i
1
ươ ậ ữ ệ ấ Ch thu t & c u trúc d li u
Yêu c u sinh viên ọ Đ c giáo trình chính theo ộ n i dung (trang 4 – trang 31)
ắ ế ươ ng 2. Tìm ki m & s p
ế 2
ọ Đ c giáo trình chính theo ộ n i dung (trang 35 – trang 43)
ị
Làm bài t p v nhà
ề ậ
Ch x pế ế Tìm ki m tuy n tính ế Tìm ki m nh phân Bài t pậ
ng 2 (tt) ươ ỗ ọ ươ Ch Ph
3
ổ ng pháp đ i ch , ch n ự ế và chèn tr c ti p
Bài t pậ
ọ Đ c giáo trình chính theo ộ n i dung (trang 43 – trang 49; trang 54 – trang 64)
Làm bài t p v nhà
9
ề ậ
Lịch học
ộ ầ Tu nầ N i dung Yêu c u sinh viên
(tt) ọ ộ n i dung
ế ươ Ch Ph ng pháp s p x p
4
ắ ạ n i b t, phân ho ch
ng 2. ươ ổ ọ Bài t pậ
Đ c giáo trình chính theo (trang 50 – trang 54; trang 59 – trang 64; trang 77 – trang 81) ậ Làm bài t p v nhà
ề
Đ c giáo trình chính theo
ươ
5 ọ ộ n i dung
ộ Ch ng 3. CTDL đ ng ỏ ể ữ ệ Ki u d li u con tr Đ nh nghĩa, các hình
Làm bài t p v nhà
(tr. 100 – tr.110) ậ ề
10
ị ứ ổ ứ th c t ch c DSLK
Lịch học
Tuần Nội dung Yêu cầu sinh viên
Đ c giáo trình chính theo
ươ ng 3
6 ọ ộ n i dung
Làm bài t p v nhà
(tr.111 – tr.123) ậ ề
Đ c giáo trình chính theo
(tt)
Ch (tt) ế ơ Danh sách liên k t đ n Thao tác trên dslk đ nơ Bài t pậ ươ ng 3 Ch Thao tác trên dslk đ n ơ
7 ọ ộ n i dung
Làm bài t p v nhà
Đ c giáo trình chính theo
(tr.124 – tr.136) ậ ề
(tt) Bài t pậ ươ ng 3. Ch (tt) Thao tác trên dslk đ n ơ
8 ọ ộ n i dung
Làm bài t p v nhà
(tr.124 – tr.136) ậ ề
11
(tt) Bài t pậ
Lịch học
Tuần Nội dung Yêu cầu sinh viên
ậ ế
ữ ỳ ể ế ả 9 Ki m tra gi a k
Ôn các thu t toán tìm ki m, ắ s p x p trên m ng, dslk đ nơ
ế ươ ng 4. Ngăn x p & hàng
10 ọ Đ c giáo trình chính theo ộ n i dung (trang 136 – trang
148) Ch đ iợ Ngăn x p ế Hàng đ iợ
ng 4. (tt)
11 ọ Đ c giáo trình chính theo ộ n i dung (trang 136 – trang
ươ Ch Bài t pậ
12
148)
Nội dung Yêu cầu sinh viên
Lịch học Tuầ n
ng 5. Cây NPTK
Đ c giáo trình chính theo (trang 190 – trang
ọ ộ n i dung
12
ệ ấ Ch C u trúc cây Đ nh nghĩa, tính ch t, duy t 198)
ươ ấ ị cây ậ
ươ ọ ộ n i dung ng 5. (tt) ề Làm bài t p v nhà Đ c giáo trình chính theo (trang 190 – trang
13
ơ ả Ch Các thao tác c b n trên cây 198)
ậ
ọ ộ n i dung ng 5. (tt) ề Làm bài t p v nhà Đ c giáo trình chính theo (trang 190 – trang
14
13 ậ
ươ Ch Bài t pậ 198)
Làm bài t p v nhà Xem l
ạ ộ 15 Ôn t pậ ề ọ i các n i dung đã h c
Phương pháp đánh giá
Kiểm tra giữa kỳ:
Hình thức: Điểm trung bình các bài kiểm tra tại
lớp, chấm điểm bài tập
Thời điểm: Ngẫu nhiên trong các buổi học
Kiểm tra cuối kỳ:
(Đối với những sinh viên không bị cấm thi)
Hình thức: Thi viết, thời gian 45 phút, không
dùng tài liệu
Thời điểm: Sau khi kết thúc học phần, theo
lịch thi chung
14
Thang điểm đánh giá môn học
15
Công cụ và phần mềm học tập
16
Công cụ và phần mềm học tập
Microsoft Visual Studio tải tại trang
Dream Spark bằng tài khoản DreamSpark của
mỗi sinh viên
Slide bài giảng và bài tập thực hành “Cấu trúc
dữ liệu & giải thuật” tải tại địa chỉ web:
http://www.minhthai.edu.vn
17
Q&A
?
18
