1
1
Thiết kế và đánh giá
Thiết kế và đánh giá
thuật toán
thuật toán
Cao học, khoa công nghệ thông tin
Cao học, khoa công nghệ thông tin
Đại học quốc gia Hà nội.
Đại học quốc gia Hà nội.
Phan Thị Hà Dương
Phan Thị Hà Dương
Viện Toán học.
Viện Toán học.
[email protected]
[email protected]
2
Chương trình
Chương trình
Chương 1
Chương 1
: Giới thiệu về thuật toán
: Giới thiệu về thuật toán
Chương 2
Chương 2
: Phân tích tính hiệu quả của thuật
: Phân tích tính hiệu quả của thuật
toán
toán
Chương 3
Chương 3

Giới thiệu chung
II.
II.
Thuật toán trên đồ thị
Thuật toán trên đồ thị
1)
1)
Cây bao trùm nhỏ nhất
Cây bao trùm nhỏ nhất
2)
2)
Đường đi ngắn nhất
Đường đi ngắn nhất
III.
III.
Thuật toán sắp xếp lịch làm việc
Thuật toán sắp xếp lịch làm việc
IV.
IV.
Thuật toán “heurisitic”
Thuật toán “heurisitic”
1)
1)
Tô màu đồ thị
Tô màu đồ thị
2)
2)
Người đưa hàng
Người đưa hàng
4

toán
toán
I.
I.
Khái niệm thuật toán
Khái niệm thuật toán
II.
II.
Một số ví dụ
Một số ví dụ
III.
III.
Đánh giá thuật toán trong trường hợp
Đánh giá thuật toán trong trường hợp
xấu nhất và theo trung bình
xấu nhất và theo trung bình
IV.
IV.
Về thuật toán hiệu quả
Về thuật toán hiệu quả
V.
V.
Một số bài toán cụ thể
Một số bài toán cụ thể
VI.
VI.
Cấu trúc dữ liệu
Cấu trúc dữ liệu
7
Khái niệm về thuật toán

ắ
p

x
ế
p
Thuật toán sắp xếp
8
Một số từ khóa
Một số từ khóa
if (điều kiện) then {…} else
if (điều kiện) then {…} else
for (điều kiện) do {…}
for (điều kiện) do {…}
while (điều kiện) do {…}
while (điều kiện) do {…}
procedure (T, a, b) {…}
procedure (T, a, b) {…}
function(A) {… return r; }
function(A) {… return r; }
9
Sắp xếp chèn vào
Sắp xếp chèn vào
5
5
2
2
4 6 1 3
4 6 1 3
2

3
1 2 3 4 5 6
1 2 3 4 5 6
10
Thuật toán xếp chèn vào
Thuật toán xếp chèn vào
Insertion-Sort (A) {
Insertion-Sort (A) {
for
for
j = 2
j = 2
to
to
length (A)
length (A)
do
do
{
{
k = A[j]; //
k = A[j]; //
chèn A[j] vào dãy đã sắp A[1..j-1]
chèn A[j] vào dãy đã sắp A[1..j-1]
j = j-1;
j = j-1;
while
while
i > 0 and A[i] > k do {
i > 0 and A[i] > k do {

[(p+r-1)/2];
[(p+r-1)/2];
3.
3.
Merge-Sort(A,p,q);
Merge-Sort(A,p,q);
4.
4.
Merge-Sort(A,q+1,r);
Merge-Sort(A,q+1,r);
5.
5.Merge(A,p,q,r);
Merge(A,p,q,r);
}
}
}
}
13
Phân tích thuật toán Merge-Sort
Phân tích thuật toán Merge-Sort
Đây là một thuật toán chia để trị.
Đây là một thuật toán chia để trị.
Chia
Chia
:
:
bước 2:


θ
θ
(1)
(1)
nếu n=1
nếu n=1
2T(n/2) +
2T(n/2) +
θ
θ
(n)
(n)
nếu n >1
nếu n >1
14
Đánh giá thuật toán
Đánh giá thuật toán
Giải quyết một bài toán.
Giải quyết một bài toán.
Vấn đề:
Vấn đề:
Có nhiều thuật toán. Chọn thuật toán nào ?
Có nhiều thuật toán. Chọn thuật toán nào ?
Mô hình hóa
Lập chương trình
Viết thuật toán
15
Phương pháp đánh giá
Phương pháp đánh giá

hợp xấu nhất và theo trung bình
Ví dụ
Ví dụ
: Sắp xếp lựa chọn
: Sắp xếp lựa chọn
Select-Sort
Select-Sort
(A){
(A){
for
for
i=1
i=1
to
to
n-1
n-1
do
do
{
{
index = i; x = T[i];
index = i; x = T[i];
for
for
j= i+1
j= i+1
to
to
n

Merge-Sort
Merge-Sort
Đối với các bảng sau :
Đối với các bảng sau :
A = [3,1,4,1,5,9,2,6,5,3]
A = [3,1,4,1,5,9,2,6,5,3]
B = [1,2,3,4,5,6]
B = [1,2,3,4,5,6]
C = [6,5,4,3,2,1]
C = [6,5,4,3,2,1]
18
Thời gian chạy trong trường hợp xấu nhất:
Thời gian chạy trong trường hợp xấu nhất:
là cận trên đối với mọi dữ liệu vào.
là cận trên đối với mọi dữ liệu vào.
Thời gian chạy trung bình: thường khó phân
Thời gian chạy trung bình: thường khó phân
tích và đánh giá hơn.
tích và đánh giá hơn.
19
Ví dụ: dãy Fibonacci
Ví dụ: dãy Fibonacci
Dãy Fibonacci được định nghĩa:
Dãy Fibonacci được định nghĩa:
F(0) = 0, F(1) = 1, và
F(0) = 0, F(1) = 1, và
F(n) = F(n-1) + F(n-2) với n > 1.
F(n) = F(n-1) + F(n-2) với n > 1.
Tìm thuật toán tính số Fibonacci thứ n.
Tìm thuật toán tính số Fibonacci thứ n.

a= 0; b = 1;
for
for
k = 1
k = 1
to
to
n
n
do
do
{c=b; b = a+b; a=c;}
{c=b; b = a+b; a=c;}
return
return
b;
b;
}
}
21
Thuật toán thứ ba
Thuật toán thứ ba
fonction
fonction fib3(n){
fib3(n){
i = 1; j = 0; k = 0; h = 1;
i = 1; j = 0; k = 0; h = 1;

n = n div 2;
n = n div 2;
}
}
return
return
j;
j;
}
}
22
Ví dụ về thời gian chạy
Ví dụ về thời gian chạy
(Pascal, CDC Cyber 835)
(Pascal, CDC Cyber 835)n
n
10
10
20
20
30
30
50
50
100
100
10000

ms
½ ms
½ ms
¾ ms
¾ ms
3/2
3/2
ms
ms
150
150
ms
ms
15 s
15 s
25
25
min
min
fib3
fib3
1/3
1/3
ms
ms
2/5
2/5
ms
ms
½ ms

type
type
elem =
elem =
structure
structure
{
{
value: information element;
value: information element;
next: * elem;}
next: * elem;}
6
7
3
1
4
24
Đồ thị
Đồ thị
type
type
adjgraph =
adjgraph =
structure
structure
{
{
value[1..n]: information elements;
value[1..n]: information elements;

value: information element;
children: array[ ] of * treenodes;
children: array[ ] of * treenodes;
}
}
type
type
treenode =
treenode =
structure
structure
{
{
value: information element;
value: information element;
first child: * treenode;
first child: * treenode;
next brother: * treenode;
next brother: * treenode;
}
}
type
type
binarytreenode =
binarytreenode =
structure
structure
{
{
value: information element;