2/23/2019
1
CẤU TRÚC DỮ LIỆU VÀ
GIẢI THUẬT
Data Structures & Algorithms
Giới Thiệu Giảng Viên
Th.S Đỗ Văn Tiến
Email: tiendv@uit.edu.vn
- Khoa Khoa Học Máy Tính, Trường Đại Học Công Nghệ
Thông Tin, ĐHQG TP.HCM
- Lĩnh vực nghiên cứu: Computer Vision, Data Mining,
Machine Learning, …
Giới Thiệu Môn Học
•Mã môn học: IT003
•Số tín chỉ: 4 ( 3 LT + 1 TH)
•Vai trò của môn học trong chương trình: Cung cấp các kiến thức
và kỹ năng căn bản và tư duy thuật toán.
•Môn học tiên quyết: Nhập môn lập trình
•https://courses.uit.edu.vn/
•Group facebook môn học: Xem trên Course – Mọi thông tin thông
báo đều được post trên đây
Mục tiêu môn học
1. Rèn luyện tư duy thuật toán.
2. Rèn luyện kỹ năng tự học thông qua việc tìm kiếm,
đọc các tài liệu chuyên ngành.
3. Nắm được một số khái niêm cơ bản của CTDL & GT.
4. Nắm một số CTDL và một số thuật giải cơ bản.
5. Sử dụng được ngôn ngữ lập trình (C++) để tổ chức
và viết chương trình trên máy tính.
4
Hình thức đánh giá
5
Thành phần đánh giá
Hình thức
Tỷ lệ
Quá trình
Bài tập ,
điểm danh
,…
10%
Thi giữa kỳ
Thi viết
20%
Thực hành
Lập trình
20%
LT Cuối kỳ
Thi viết
40%
Seminar
nhóm
10%
NỘI DUNG MÔN HỌC
6
Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu
Chương 2: Các chiến lược thiết kế giải thuật
Chương 3: Cấu trúc dữ liệu động: con trỏ, danh sách liên
kết, danh sách đơn
Chương 3: Ngăn xếp, hằng đợi
Chương 4: Tìm kiếm và sắp xếp
Chương 5: Cấu trúc Cây: cây nhị phân, cây nhị phân tìm
kiếm, cây cân bằng , B-tree, cây đỏ đen
Chương 6: Bảng băm
Chương 6: Đồ thị
2/23/2019
2
Các yêu cầu
(1) Đi học và làm bài tập đầy đủ.
(2) Chủ động đặt câu hỏi và trao đổi trên group môn học.
(3) Làm thât nhiều bài tập ….
(4) Tương tác trong lớp học (hỏi và trả lời)
7
Các yêu cầu
Có vở riêng của môn học để:
-Ghi chép các nội dung các bài lý thuyết
-Làm bài tập trên lớp.
Vở dùng để:
-Chấm các bài tập trên lớp
-Điểm danh
một phần trong điểm quá trình
8
9
Cách học
10
1. Nghe giảng, chú ý tập trung để hiểu bài ngay tại
lớp, nếu có gì không hiểu thì hỏi
2. Về nhà: làm lại theo hướng dẫn tại bài giảng để nắm
ý tưởng, nếu có gì không hiểu thì hỏi.
3. Đọc giáo trình/tài liệu theo yêu cầu để nắm
được nội dung chi tiết, nếu có gì không hiểu thì hỏi
4. Làm bài tập để thực sự hiểu nội dung đã học, nếu
không hiểu đề bài thì hỏi, nếu không nhớ cách làm thì
quay lại bước 2 hoặc 3, nếu vẫn không được thì hỏi.
Cách học
11
5. Đến giờ thực hành để kiểm tra kết quả bài tập đã
làm được và để được giáo viên giúp đỡ nếu gặp khó
khăn.
Hỏi ở đâu? Hỏi giáo viên trên lớp, hỏi bạn, hỏi cả
lớp trên diễn đàn, group facebook.
7. Nếu không biết làm nhưng cũng không biết hỏi
như thế nào? Hãy gặp giáo viên và trình bày tình
trạng khó khăn của bạn.
Cần thực hiện bước 2 càng sớm càng tốt sau giờ lý
thuyết để tránh quên mất các nội dung vừa học. Không
được để đến giờ thực hành mới đem bài giảng lần
trước ra đọc lại.
Cách học
12
Quy tắc ứng xử:
•Tôn trọng bản thân và tôn trọng người khác: không làm
ồn, không để cho người khác làm ồn, không quay cóp....
•Vào muộn ra sớm đừng xin phép
Lời khuyên:
•Nỗ lực bản thân là điều quan trọng nhất.
•Giáo viên không phải cái gì cũng biết.
•Giáo viên có thể sai. Sách có thể sai.
•Đừng ngại hỏi. No such thing as a stupid question
2/23/2019
3
Tài liệu tham khảo
Các nguồn tài liệu khác
•Google
•Youtube ( Lập trình C, c++, Nhập môn lập trình ..)
•Facebook group ()
•congdongcviet.com
•https://stackoverflow.com
Phần mềm thực hành
•Code Blocks
•http://www.codeblocks.org/downloads/26
Phần mềm thực hành
17
3/3/2019
1
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Data Structures & Algorithms
Các chiến lược thiết kế giải thuật
2
BẠN THƯỜNG LÀM GÌ KHI NHẬN MỘT BÀI
TẬP LẬP TRÌNH ?
3
4
Nội dung
1. Vét cạn – Complete Search/Brute-force Search
2. Chia để trị – Divide and Conquer
3. Tham lam – Greedy
4. Qui hoạch động – Dynamic Programming
Mỗi chiến lược có các tính chất riêng và chỉ thích hợp
cho một số dạng bài toán nào đó.
6
1. Vét cạn
3/3/2019
2
7
1. Vét cạn
Vét cạn theo nghĩa thông thường là xét hết mọi
đối tượng hay mọi trường hợp.
•Bài toán: Có một tập C các ứng viên và một
hàm f để đánh giá/cho điểm các ứng viên. Hãy tìm
ứng viên được đánh giá/có điểm cao nhất.
•Phương pháp giải: Duyệt tất cả các ứng viên,
tính điểm cho từng ứng viên, sau đó lấy ứng
viên có điểm cao nhất.
Ví dụ:
Tìm vị trí số x trên dãy a gồm N số thực.
•Input: dãy (a, N) – dãy gồm N số thực, số x – số cần
tìm
•Output: số nguyên – vị trí của x trên a (-1 nếu a
không có x)
8
Giải thuật vét cạn
•Ý tưởng: Thử tìm x tại từng vị trí của a, nếu tìm thấy
thì ngừng và báo vị trí. Nếu đã thử hết các vị trí mà
vẫn không thấy x thì báo -1
•Giải thuật:
1. For pos = 0 N-1
1. If (a[pos] = x)
1. Return pos
EndFor
2. Return -1
Vét cạn – dạng thức chung
Tìm lời giải cho bài toán P
1. C first(P)
2. While (c )
1. If correct(P, c) Return c;
2. c next(P, c);
End While
3. Return NULL; //không có lời giải
•Ưu điểm: luôn đảm bảo tìm ra nghiệm (nếu có) chính
xác
•Nhược điểm: thời gian thực thi lớn
11
1. Vét cạn
Chia bài toán thành các bài toán kích thước nhỏ có thể
giải quyết độc lập. Sau đó kết hợp nghiệm các bài toán
kích thước nhỏ thành nghiệm bài toán gốc
12
2. Chia để trị