Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về cấu trúc dữ liệu và thuật toán

hí thấp 
“Một máy tính siêu hạng vẫn không thể cứu vãn một
thuật toán tồi!”
hung
4
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
10
Thuật Toán
 Thuật toán: Một dãy hữu hạn các chỉ thị có thể
thi hành để đạt mục tiêu đề ra nào đó.
 Ví dụ: Thuật toán tính tổng tất cả các số nguyên
dương nhỏ hơn n gồm các bước sau:
Bước 1: S=0, i=1;
Bước 2: nếu i<n thì s=s+i;
Ngược lại: qua bước 4;
Bước 3:
i=i+1;
Quay lại bước 2;
Bước 4: Tổng cần tìm là S.
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
11
Các Tiêu Chuẩn Của Thuật Toán
 Xác định
 Hữu hạn
 Đúng
 Tính hiệu quả
 Tính tổng quát
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
12
Biễu Diễn Thuật Toán
 Dạng ngôn ngữ tự nhiên
 Dạng lưu đồ (sơ đồ khối)
 Dạng mã giả
 Ngôn ngữ lập trình
hung
5
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
13
Biểu Diễn Bằng Ngôn Ngữ Tự Nhiên
 NN tự nhiên thông qua các bước được tuần
tự liệt kê để biễu diễn thuật toán.
 Ưu điểm:
 Đơn giản, không cần kiến thức về về
cách biểu diễn (mã giả, lưu đồ,...)
 Nhược điểm:
 Dài dòng, không cấu trúc.
 Đôi lúc khó hiểu, không diễn đạt được
thuật toán.
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
14
Lưu Đồ
 Là hệ thống các nút, cung hình dạng khác nhau
thể hiện các chức năng khác nhau.
A
B
A
Begin
End
Thực hiện A Gọi hàm A Vào / Ra dữ liệu
Điều kiện rẻ nhánh B
Đúng
Sai
Nút giới hạn bắt đầu /
kết thúc chương trình
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
15
Biểu Diễn Bằng Lưu Đồ
Bắt đầu amax = a0
i<n
i = 1
amax là lớn nhất Kết thúc
amax < ai
i = i+1
amax =ai
S
S
Đ
Đ
Tìm phần tử mang
giá trị lớn nhất
trong mảng
hung
6
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
16
Biểu Diễn Bằng Mã Giả
 Ngôn ngữ tựa ngôn ngữ lập trình:
 Dùng cấu trúc chuẩn hóa, chẳng hạn
tựa Pascal, C.
 Dùng các ký hiệu toán học, biến, hàm.
 Ưu điểm:
 Đỡ cồng kềnh hơn lưu đồ khối.
 Nhược điểm:
 Không trực quan bằng lưu đồ khối.
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
17
Biểu Diễn Bằng Mã Giả
 Một số quy ước
1. Các biểu thức toán học
2. Lệnh gán: “=” (AB)
3. So sánh: “==”, “!=”
4. Khai báo hàm (thuật toán)
Thuật toán ()
Input: 
Output: 
End
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
18
Biểu Diễn Bằng Mã Giả
5. Các cấu trúc:
Cấu trúc chọn:
if … then … [else …] fi
Vòng lặp:
while … do
do … while (…)
for … do … od
6. Một số câu lệnh khác:
Trả giá trị về: return [giá trị]
Lời gọi hàm: (tham số)
hung
7
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
19
Biểu Diễn Bằng Mã Giả
 Ví dụ: Tìm phần tử lớn nhất trong mảng một
chiều.
amax=a0;
i=1;
while (i<n)
if (amax<ai) amax = ai;
i++;
end while;
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
20
Biểu Diễn Bằng Ngôn Ngữ Lập Trình
 Dùng ngôn ngữ máy tính (C, Pascal,...) để
diễn tả thuật toán, CTDL thành câu lệnh.
 Kỹ năng lập trình đòi hỏi cần học tập và
thực hành (nhiều).
 Dùng phương pháp tinh chế từng bước để
chuyển hoá bài toán sang mã chương trình
cụ thể.
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
21
Độ Phức Tạp Của Thuật Toán
 Một thuật toán hiệu quả:
 Chi phí cần sử dụng tài nguyên thấp: Bộ nhớ,
thời gian sử dụng CPU, …
 Phân tích độ phức tạp thuật toán:
 N là khối lượng dữ liệu cần xử lý.
 Mô tả độ phức tạp thuật toán qua một hàm
f(N).
 Hai phương pháp đánh giá độ phức tạp của
thuật toán:
 Phương pháp thực nghiệm.
 Phương pháp xấp xỉ toán học.
hung
8
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
22
Phương Pháp Thực Nghiệm
 Cài thuật toán rồi chọn các bộ dữ liệu thử nghiệm.
 Thống kê các thông số nhận được khi chạy các
bộ dữ liệu đó.
 Ưu điểm: Dễ thực hiện.
 Nhược điểm:
 Chịu sự hạn chế của ngôn ngữ lập trình.
 Ảnh hưởng bởi trình độ của người lập trình.
 Chọn được các bộ dữ liệu thử đặc trưng cho
tất cả tập các dữ liệu vào của thuật toán: khó
khăn và tốn nhiều chi phí.
 Phụ thuộc vào phần cứng.
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
23
Phương Pháp Xấp Xỉ
 Đánh giá giá thuật toán theo hướng tiệm xấp xỉ
tiệm cận qua các khái niệm O().
 Ưu điểm: Ít phụ thuộc môi trường cũng như phần
cứng hơn.
 Nhược điểm: Phức tạp.
 Các trường hợp độ phức tạp quan tâm:
 Trường hợp tốt nhất (phân tích chính xác)
 Trường hợp xấu nhất (phân tích chính xác)
 Trường hợp trung bình (mang tích dự đoán)
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
24
Đánh giá thuật giải
 Gọi n là số lượng dữ liệu nhập vào và t là
thời gian thực hiện một lệnh.
 Tính f(n) là tổng số lần thực hiện các lệnh
=> T/gian thực hiện thuật toán là T = f(n)*t
 Cho n-> vô cực thì f(n)->g(n);
 O(g(n)) gọi là độ phức tạp của thuật toán
hung
9
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
25
Sự Phân Lớp Theo Độ Phức Tạp Của Thuật Toán
 Sử dụng ký hiệu BigO
 Hằng số : O(c)
 logN : O(logN)
 N : O(N)
 NlogN : O(NlogN)
 N2 : O(N2)
 N3 : O(N3)
 2N : O(2N)
 N! :O(N!)
Độ phức tạp tăng dần
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
26
Đồ thị hàm số
a
log(n)
n
n
n2
n3
Nhận xét: Ta thấy khi n->vc thì
n3 lớn rất nhanh, do đó những
thuật toán có độ phức tạp là
O(n3),O(2n), O(n!), O(nn) khó sử
dụng được khi n rất lớn
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
27
Vi dụ: đánh giá giải thuật tìm số lớn nhất của n số
 Giải thuật:
B0: nhập n và dãy n số nguyên a[0], a[1],…,a[n-1]
B1: max=a[0]; i=1;
B2: Trong khi i<n lặp lại các bước sau:
B2.1: Nếu a[i]>max thì max=a[i];
B2.2: i=i+1;
B3: In max.
 Đánh giá: trường hợp dữ liệu xấu nhất (dãy tăng)
Tính các bước?
hung
10
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
28
Tổng hợp các bước
4nf(n)=
13
n-12.2
2(n-1)2.1
n2
21
Số lần thực hiện lệnhBước
 G.sử: t =10-3ms (t.gian thực hiện 1 lệnh)
 TH xấu nhất: T = 4n*10-3
 Cho n->vc thì f(n)->n  Độ phức tạp của thuật toán: O(n)
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
29
Vi dụ: đánh giá giải thuật sort n số nguyên
 Giải thuật:
B0: nhập n, nhập dãy n số nguyên a[0], a[1],…,a[n-1]
B1: i=0;
B2: Trong khi i<n-1 lặp lại các bước sau:
B2.1: m=i, j=i+1;
B2.2: Trong khi j<n lặp lại các bước sau:
B2.2.1: Nếu a[j]<a[m] thì m=j;
B2.2.2: j=j+1;
B2.3: Nếu (m!=i) thì { t=a[i]; a[i]=a[m]; a[m]=t; }
B2.4: i=i+1;
B3: In dãy a[0], a[1],…,a[n-1] .
 Đánh giá: trường hợp dữ liệu xấu nhất là dãy giảm
Tính các bước?
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
30
Tổng hợp các bước
f(n)=
n
n-1
3(n-1)
a-1
2(a-1)
n+(n-1)+…+2 = n(n+1)/2 – 1
2(n-1)
n
1
Số lần thực hiện lệnh
= a
gán
TC
3
2.4
2.3
2.2.2
2.2.1
2.2
2.1
2
1
Bước
hung
11
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
31
 Cho n->vc thì f(n)->n2
 Vậy độ phức tạp của thuật toán là O(n2) .
 Nhận xét chung: Nếu thuật toán có
Một vòng lặp thì độ phức tạp của thuật
toán là O(n)
Hai vòng lặp lồng nhau là O(n2)
 Ba vòng lặp lồng nhau là O(n3)
 vv…
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
32
Dữ Liệu
 Theo từ điển Tiếng Việt: số liệu, tư liệu đã có,
được dựa vào để giải quyết vấn đề
 Tin học: Biểu diễn các thông tin cần thiết cho bài
toán.
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
33
Cấu Trúc Dữ Liệu
 Cách tổ chức lưu trữ dữ liệu.
 Các tiêu chuẩn của CTDL:
 Phải biểu diễn đầy đủ thông tin.
 Phải phù hợp với các thao tác trên đó.
 Phù hợp với điều kiện cho phép của NNLT.
 Tiết kiệm tài nguyên hệ thống.
hung
12
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
34
Vai Trò Của Cấu Trúc Dữ Liệu
 Cấu trúc dữ liệu đóng vai trò quan trọng
trong việc kết hợp và đưa ra cách giải quyết
bài toán.
 CTDL hỗ trợ cho các thuật toán thao tác
trên đối tượng được hiệu quả hơn
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
35
Thực Hiện Và Hiệu Chỉnh Chương Trình
 Chạy thử.
 Lỗi và cách sửa:
 Lỗi thuật toán.
 Lỗi trình tự.
 Lỗi cú pháp.
 Xây dựng bộ test.
 Cập nhật, thay đổi chương trình theo yêu
cầu (mới).
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
36
Tiêu Chuẩn Của Một Chương Trình
 Tính tin cậy
 Giải thuật + Kiểm tra cài đặt
 Tính uyển chuyển
 Đáp ứng quy trình làm phần mềm.
 Tính trong sáng
 Dễ hiểu và dễ chỉnh sửa
 Tính hữu hiệu.
 Tài nguyên + giải thuật
hung
13
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
37
Quy Trình Làm Phần Mềm
 Bước 0: Ý tưởng (concept).
 Bước 1: Xác định yêu cầu (Requirements
Specification).
 Bước 2: Phân tích (Analysis).
 Bước 3: Thiết kế (Design).
 Bước 4: Cài đặt (Implementation).
 Bước 5: Thử nghiệm (Testing).
 Bước 6: Vận hành, theo dõi và bảo dưỡng
(Operation, follow-up and Maintenance).
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
38
Các kiểu dữ liệu
 Kiểu dữ liệu cơ sở
 Kiểu dữ liệu cấu trúc (structure)
 Kiểu dữ liệu động (Dynamic)
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
39
Tổ chức Seminar
 Mỗi nhóm 5 sinh viên
 Mỗi buổi ~2 nhóm trình bày
 Trình bày trong 20-30 phút (kể cả thảo luận)
 Trình bày bằng slide (~30 slide)
 Nội dung:
Mục tiêu, phạm vi của vấn đề
Mô tả thuật toán, hướng giải quyết
Các ứng dụng có thể sử dụng
 Kết luận
hung
14
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
40
Tổ chức thảo luận trên group
 Thảo luận theo chủ đề được đưa ra hàng
tuần/tháng
 Mục tiêu: Tăng khả năng làm việc nhóm và
tìm kiếm thông tin.
 Thắc mắc email tới về sacvn@yahoo.com
C
ẤU
 T
R
Ú
C
 D
Ữ
LI
ỆU
 V
À
G
IẢ
IT
H
U
ẬT
41
Chủ đề tuần đầu tiên
 Các phương pháp tìm kiếm
 Các khó khăn & Hướng giải quyết cho các
bài toán tìm kiếm với dữ liệu lớn