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
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

I.
Giới thiệu chung
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

Phan Đình Diệu.
6
6
Chương 1: Giới thiệu về thuật
Chương 1: Giới thiệu về thuật
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.

đ
ư
ợ
c

s
ắ
p

x
ế
p
Thuật toán sắp xếp
8
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
9
Sắp xếp chèn vào

1
3
3
1
1
2 4 5 6
2 4 5 6
3
3
1 2 3 4 5 6
1 2 3 4 5 6
10
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]; //

if
p < r
p < r
then
then
{
{
2.
2.
q =
q =
[(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);
}
}
}

bước 5:
θ
θ
(n)
(n)
Tổng kết
Tổng kết
:
:
T(n) =
T(n) = θ
θ
(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
14
Đánh giá thuật toán

: - không phụ thuộc ngôn ngữ lập trình, loại máy
: - không phụ thuộc ngôn ngữ lập trình, loại máy
tính
tính- Biết được tính hiệu quả của thuật toán đối với
- Biết được tính hiệu quả của thuật toán đối với
các dữ liệu có kích thước lớn.
các dữ liệu có kích thước lớn.
16
16
Đánh giá thuật toán trong trường
Đánh giá thuật toán trong trường
hợp xấu nhất và theo trung bình
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

T{index = T{i};
T{index = T{i};
T{i} = x;
T{i} = x;
}
}
}
}
17
17
Ví dụ
Ví dụ
Hãy chạy thuật toán
Hãy chạy thuật toán
Insertion-Sort
Insertion-Sort
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
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:

then
thenreturn
return
n;
n;
else return
else return
f(n-1) + f(n-2);
f(n-1) + f(n-2);
}
}
fonction
fonction
fib2(n){
fib2(n){
a= 0; b = 1;
a= 0; b = 1;
for
for
k = 1
k = 1
to
to
n
n
do
do

(n lẻ)
(n lẻ)
then
then
{ t = jh;
{ t = jh; j = ih + jk +t;
j = ih + jk +t;i = ik +t;}
i = ik +t;}
t = h^2;
t = h^2;
h = 2kh+t;
h = 2kh+t;
k = k^2+t;
k = k^2+t;
n = n div 2;
n = n div 2;
}
}
return
return
j;
j;
}
}

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

structure
structure
{
{
value: information element;
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 =