BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC SƯ PHẠM

MAI THỊ THANH THỦY

KHÔNG GIAN MÊTRIC SUY RỘNG BAIRE
VÀ ỨNG DỤNG

Chuyên ngành : TOÁN GIẢI TÍCH
Mã số : 60 46 01 02

LUẬN VĂN THẠC SĨ TOÁN HỌC

Cán bộ hướng dẫn khoa học:
TS. LÊ THỊ NHƯ BÍCH

HUẾ, 2016

i


LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu
của riêng tôi, các số liệu và kết quả nào trong
luận văn là trung thực, được các đồng tác giả
cho phép sử dụng và chưa từng được công bố
trong bất kỳ một công trình nào khác
Mai Thị Thanh Thủy

ii

LỜI CẢM ƠN
Luận văn này được hoàn thành dưới sự gợi ý của Thầy giáo, PGS.TS
Lê Văn Hạp và sự hướng dẫn khoa học tận tình, chu đáo của Cô giáo,
TS Lê Thị Như Bích. Tôi xin gửi đến quý Thầy, quý Cô sự trân trọng và
biết ơn sâu sắc.
Xin được bày tỏ lòng biết ơn và kính trọng đến kính Thầy giáo :
PGS.TS Lê Viết Ngư, PGS.TS Nguyễn Hoàng, TS Trương Văn Thương,
PGS.TS Huỳnh Thế Phùng, PGS.TS Phan Nhật Tĩnh, những người đã
tận tình giảng dạy và luôn động viên, khích lệ trong suốt quá trình học
tập.
Tôi cũng xin chân thành cảm ơn BGH trường ĐHSP Huế, các Thầy
Cô Khoa Toán trường ĐHSP Huế, ĐHKH Huế và PQLSĐH trường ĐHSP
Huế, những người đã giúp tôi có được kiến thức khoa học cũng như những
điều kiện để hoàn thành công việc học tập, nghiên cứu của mình.
Xin trân trọng và chân thành cảm ơn!

iii


Mục lục
Trang phụ bìa

i

Lời Cam Đoan

ii


Lời cảm ơn

iii

Mục lục

1

Lời nói đầu

3

1 Một số kiến thức cơ sở

5

1.1

1.2

Không gian mêtric . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.1

Định nghĩa không gian mêtric . . . . . . . . . . . . . . . . .

5


1.1.2

Sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.1.3

Không gian mêtric đầy đủ . . . . . . . . . . . . . . . . . . .

6

1.1.4

Định lý điểm bất động trong không gian mêtric . . . . . .

7

Không gian quasi-mêtric . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2.1

Định nghĩa không gian quasi-mêtric . . . . . . . . . . . . .

7

1.2.2


Quan hệ thứ tự trong không gian quasi-mêtric . . . . . . .

9

1.2.3

Định lý ánh xạ co trong không gian quasi-mêtric . . . . . .

9

1.3

Không gian độ phức tạp (complexity space) . . . . . . . . . . . . . 11

1.4

Thuật toán Chia để trị (Divide và Conquer) và phương trình đệ
quy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.5

1.4.1

Thuật toán Chia để Trị . . . . . . . . . . . . . . . . . . . . 14

1.4.2

Phương trình đệ quy . . . . . . . . . . . . . . . . . . . . . . 14

Nghiệm của phương trình đệ quy trong thuật toán Chia để trị . . 15


2 Không gian mêtric suy rộng Baire

1

18


2.1

2.2

2.3

Không gian p-mêtric (mêtric riêng) . . . . . . . . . . . . . . . . . . 18
2.1.1

Định nghĩa không gian p-mêtric . . . . . . . . . . . . . . . 18

2.1.2

Sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1.3

Quan hệ thứ tự trên không gian p-mêtric . . . . . . . . . . 20

2.1.4

Không gian p-mêtric đầy đủ . . . . . . . . . . . . . . . . . . 22


Không gian p-mêtric Baire . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.1

Định nghĩa không gian p-mêtric Baire . . . . . . . . . . . . 29

2.2.2

Định lí điểm bất động trong không gian p-mêtric Baire . . 31

Không gian tựa p-mêtric Baire . . . . . . . . . . . . . . . . . . . . 32
2.3.1

Không gian tựa p-mêtric . . . . . . . . . . . . . . . . . . . . 32

2.3.2

Không gian tựa p-mêtric Baire . . . . . . . . . . . . . . . . 40

3 Ứng dụng của không gian mêtric suy rộng Baire

43

3.1

Phân tích tiệm cận độ phức tạp của thuật toán thông qua tựa
p-mêtric Baire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2


Độ phức tạp của thuật toán Quicksort và Mergesort . . . . . . . . 45

3.3

Độ phức tạp của thuật toán Largetwo . . . . . . . . . . . . . . . . 47

3.4

Bài toán tháp Hà Nội . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Kết luận

55

Tài liệu tham khảo

58

2


LỜI NÓI ĐẦU
Khái niệm không gian mêtric được giới thiệu bởi nhà toán học nổi tiếng
người Pháp Maurice Fréchet vào năm 1905. Đó là một cặp (X, d), trong đó X là
một tập hợp khác rỗng và d : X × X −→ R là một ánh xạ thỏa mãn 3 điều kiện:
Với mọi x, y, z ∈ X ta có:
(1) d(x, y) ≥ 0 và d(x, y) = 0 ⇔ x = y ;
(2) d(x, y) = d(y, x);
(3) d(x, y) ≤ d(x, z) + d(z, y).
Kể từ đó cho đến nay đã có nhiều nghiên cứu mở rộng về không gian này

theo hai hướng:
1) Xây dựng không gian tổng quát theo hướng thay thế R bởi một không gian
Banach thực có thứ tự (cho bởi nón).
2) Mở rộng không gian mêtric bằng cách giảm nhẹ các điều kiện đặt trên các
tiên đề mêtric:
• Bỏ điều kiện (2) d(x, y) = d(y, x) và giữ nguyên hai điều kiện (1), (3) ta
có định nghĩa không gian tựa mêtric (quasi-metric: W.A. Wilson -1931,

pseudo-metric...).
• Thay đổi điều kiện (3) bởi điều kiện d(x, y) ≤ K(d(x, z) + d(y, z)) với là K

hằng số dương và giữ nguyên hai điều kiện còn lại ta có định nghĩa không
gian b-metric (bounded- metric space).
• Năm 1994, S.G. Matthews đã giới thiệu khái niệm không gian p-mêtric

(partial metric space), bằng cách bỏ điều kiện x = y ⇒ d(x, y) = 0, thay đổi
điều kiện (3) bởi điều kiện d(x, y) ≤ d(x, z) + d(z, y) − d(z, z) và giữ nguyên
các điều kiện còn lại của mêtric ta có định nghĩa p-mêtric, một công cụ
toán học thích hợp cho sự kiểm tra việc chạy chương trình máy tính.
Sau đó, M.P. Schellekens đã đưa ra lí thuyết Không gian độ phức tạp (Complexity Space), nhằm nghiên cứu bản chất tôpô, nền tảng của sự phân tích tiệm
cận độ phức tạp của chương trình và thuật toán (thuật toán Divide và Conquer)
trong Khoa học máy tính.
Liệu rằng định lí điểm bất động Matthews trong không gian p-mêtric có
phải là công cụ thích hợp để phân tích tiệm cận độ phức tạp của các thuật toán
3


theo hướng của Schellekens? Hay cần mở rộng một không gian khác hữu ích hơn
(không gian mêtric suy rộng Baire) để phân tích tiệm cận độ phức tạp của các
thuật toán?

Với sự hấp dẫn của không gian mêtric suy rộng Baire và mong muốn tìm
hiểu một số tính chất đặc biệt của không gian mêtric suy rộng này và ứng dụng
của nó trong Khoa học máy tính, được sự gợi ý của PGS.TS. Lê Văn Hạp và sự
hướng dẫn tận tình của TS. Lê Thị Như Bích, tôi đã chọn đề tài ”Không gian
mêtric suy rộng Baire và ứng dụng” để tìm hiểu và nghiên cứu.
Mục đích của luận văn nhằm đưa ra định nghĩa và tìm hiểu một số tính
chất của không gian mêtric suy rộng Baire mà đặc biệt là những tính chất liên
quan đến định lí điểm bất động và ứng dụng của nó. Do đó, nội dung của luận
văn được chia làm 3 chương.
Chương 1 trình bày các khái niệm không gian độ phức tạp, thuật toán Chia
để trị, phương trình đệ quy và tìm hiểu các tính chất của không gian mêtric,
không gian tựa mêtric; tạo điều kiện thuận lợi cho việc tìm hiểu các vấn đề liên
quan ở các chương tiếp theo.
Chương 2 trình bày các khái niệm, tính chất của không gian p-mêtric và
không gian mêtric suy rộng Baire.
Chương 3 trình bày ứng dụng của không gian mêtric suy rộng Baire vào
phân tích tiệm cận độ phức tạp của các thuật toán.

Huế, ngày 10 tháng 10 năm 2016
Mai Thị Thanh Thủy

4


Chương 1
Một số kiến thức cơ sở
1.1

Không gian mêtric


1.1.1

Định nghĩa không gian mêtric

Định nghĩa 1.1.1 [1]. Cho X là một tập khác rỗng. Ánh xạ d: X × X −→ R+
(R+ = [0, ∞)) được gọi là một mêtric trên X nếu:
i) ∀x, y ∈ X : x = y ⇔ d(x, y) = 0;
ii) ∀x, y ∈ X : d(x, y) = d(y, x);
iii) ∀x, y, z ∈ X : d(x, z) ≤ d(x, y) + d(y, z).
Lúc đó cặp (X, d) được gọi là một không gian mêtric.
Ví dụ 1.1.1 [1].
1) d(x, y) = |x − y| , ∀ x, y ∈ R xác định một mêtric trên R và được gọi là
mêtric thông thường trên R.
2) Với hai điểm x = (x1 , x2 , ..., xk ) và y = (y1 , y2 , ..., yk ) trên Rk ta định nghĩa
k

(xi − yi )2

d(x, y) =

1
2

i=1

thì d là một mêtric trên Rk và gọi là mêtric thông thường trên Rk .
3) C[a,b] là tập hợp các hàm nhận giá trị thực và liên tục trên [a, b]. Với x, y ∈
C[a,b] , ta định nghĩa
d(x, y) = max |x(t) − y(t)|
t∈[a,b]


thì d xác định một mêtric trên C[a,b] .
5


1.1.2

Sự hội tụ

Định nghĩa 1.1.2 [1]. Cho (xn ) là dãy trong không gian mêtric (X, d), x0 ∈ X.
Ta nói dãy (xn ) hội tụ về x0 nếu lim d(xn , x0 ) = 0. Ký hiệu lim xn = x0 hay
n→∞
n→∞
xn → x0 .
Như vậy
lim xn = x0 ⇔ lim d(xn , x0 ) = 0

n→∞

n→∞

⇔ ∀ ε > 0, ∃ n0 ∈ N, ∀ n ∈ N, n ≥ n0 ⇒ d(xn , x0 ) < ε.

Lúc đó x0 được gọi là giới hạn của dãy (xn ).

1.1.3

Không gian mêtric đầy đủ

Định nghĩa 1.1.3 [1]. Cho không gian mêtric (X, d). Một dãy (xn ) trong X

được gọi là dãy Cauchy hay dãy cơ bản nếu lim d(xm , xn ) = 0.
m,n→∞

Điều này có nghĩa là (xn ) trong X được gọi là dãy Cauchy nếu ∀ε > 0 bất kỳ,
tồn tại n0 ∈ N sao cho ∀m, n ∈ N mà m, n ≥ n0 thì d(xm , xn ) < ε.
Nhận xét 1.1.1 [1].
1) Nếu dãy (xn ) hội tụ trong không gian mêtric thì (xn ) là dãy Cauchy. Tuy
nhiên, chiều ngược lại, mọi dãy Cauchy đều hội tụ là không đúng. Chẳng
1
hạn, cho X=(0, 1]. Khi đó dãy ( ) là dãy Cauchy nhưng không hội tụ trong
n
X.
2) Nếu (xn ) là dãy Cauchy và có một dãy con hội tụ về x0 thì dãy (xn ) hội tụ
về x0 .
Định nghĩa 1.1.4 [1]. Không gian mêtric (X, d) được gọi là đầy đủ nếu mọi
dãy Cauchy trong X đều hội tụ về một phần tử của X.
Ví dụ 1.1.2 [1].
1) R với mêtric thông thường là đầy đủ.
2) Không gian Rk với mêtric thông thường là đầy đủ.
3) Không gian C[a,b] với mêtric được định nghĩa ở ví dụ 1.1.1 là đầy đủ.
Định lí 1.1.5 [1]. Tập con đóng của không gian mêtric đầy đủ là không gian
đầy đủ.
6


1.1.4

Định lý điểm bất động trong không gian mêtric

Định nghĩa 1.1.6 [1]. Cho X là một tập khác rỗng và ánh xạ f : X → X . Điểm

x0 được gọi là một điểm bất động của ánh xạ f nếu f (x0 ) = x0 .
Định nghĩa 1.1.7 [1]. Cho (X, d) là không gian mêtric. Ánh xạ f : X → X
được gọi là ánh xạ co nếu tồn tại số thực k ∈ [0, 1) sao cho d(f (x), f (y)) ≤ k.d(x, y),
∀x, y ∈ X .
Định lí 1.1.8 [1]. Cho (X, d) là không gian mêtric đầy đủ và f : X → X là ánh
xạ co. Khi đó f có duy nhất một điểm bất động.
Chứng minh: Xem tài liệu số [1]
Định lí 1.1.9 Cho X là không gian mêtric đầy đủ và f : X → X là ánh xạ .
Nếu tồn tại k ∈ N sao cho f k là ánh xạ co thì f có duy nhất một điểm bất động
trong X.
Chứng minh:
Gọi α là hệ số co của ánh xạ co f k , α ∈ [0, 1). Lúc đó ánh xạ f k có duy nhất
điểm bất động x0 , nghĩa là f k (x0 ) = x0 .
Ta có
d(f (x0 ), x0 ) = d(f k+1 (x0 ), f k (x0 )) ≤ α.d(f (x0 ), x0 ),

mà α ∈ [0, 1) nên d(f (x0 ), x0 ) = 0. Suy ra f (x0 ) = x0 . Hay x0 là điểm bất động
của f .
Giả sử x1 là điểm bất động của f , (x1 = x0 ). Khi đó f (x1 ) = x1 nên f k (x1 ) = x1 ,
với k ∈ N bất kỳ. Do đó x1 là điểm bất động của f k , k ∈ N. Điều này mâu thuẫn
vì ánh xạ f k có duy nhất điểm bất động x0 .
Vậy f có duy nhất một điểm bất động trong X.

1.2
1.2.1

Không gian quasi-mêtric
Định nghĩa không gian quasi-mêtric

Định nghĩa 1.2.1 [4]. Cho X là một tập khác rỗng. Một hàm d: X×X −→ [0, ∞)

được gọi là một quasi-mêtric (q-mêtric hay tựa mêtric) nếu:
i) ∀x, y ∈ X : x = y ⇔ d(x, y) = d(y, x) = 0;
7


ii) ∀x, y, z ∈ X : d(x, z) ≤ d(x, y) + d(y, z).
Lúc đó cặp (X, d) được gọi là một không gian quasi-mêtric hay là không gian
q-mêtric.
Nhận xét 1.2.1 Nếu d là một q-mêtric mà thỏa thêm tính chất:
d(x, y) = d(y, x), ∀x, y ∈ X

thì d là một mêtric.
Ví dụ 1.2.1 Một hàm u trên R × R xác định: u(x, y) = max(y − x, 0), ∀x, y ∈ R
là một quasi-mêtric nhưng không phải là một mêtric trên R.
Thật vậy,
1) Dễ thấy x = y ⇔ u(x, y) = u(y, x) = 0, ∀x, y ∈ R.
2)

i) Nếu z ≥ x thì u(x, z) = z − x.
+ Nếu x ≥ y thì z ≥ y . Lúc đó u(x, y) = 0 và u(y, z) = z − y .
Suy ra u(x, z) ≤ u(x, y) + u(y, z).
+ Nếu x < y thì u(x, y) = y − x
. Nếu y ≥ z thì u(y, z) = 0. Suy ra u(x, z) ≤ u(x, y) + u(y, z).
. Nếu y < z thì u(y, z) = z − y . Suy ra u(x, z) ≤ u(x, y) + u(y, z).
ii) Nếu z < x thì tương tự ta cũng có u(x, z) ≤ u(x, y) + u(y, z).
Do đó ∀ x, y, z ∈ R : u(x, z) ≤ u(x, y) + u(y, z).

Vậy u là một quasi-mêtric. Dễ dàng nhận thấy u không phải là một mêtric trên
R.
Ví dụ 1.2.2 Cho X = (0, ∞]. Hàm u−1 được xác định:

1 1
u−1 (x, y) = max( − , 0); ∀x, y ∈ X
y x

là một quasi-mêtric.
Thật vậy, ta dễ dàng kiểm tra u−1 thỏa mãn các điều kiện của một q-mêtric trên
X.

8


1.2.2

Quan hệ thứ tự trong không gian quasi-mêtric

Định nghĩa 1.2.2 [4]. Một quan hệ thứ tự riêng là một quan hệ nhị phân
⊆ X 2 thỏa mãn:
i) ∀x ∈ X, x

x;

ii) ∀x, y ∈ X, x

x ⇒ x = y;

y và y

iii) ∀x, y, z ∈ X, x

y và y


z⇒x

z.

Bổ đề 1.2.3 [4]. Với mỗi quasi-mêtric d: X × X −→ [0, ∞), quan hệ
được định nghĩa:
∀x, y ∈ X, x

qy

q

⊆ X2

⇔ d(x, y) = 0

là một quan hệ thứ tự riêng.
Bổ đề 1.2.4 [4]. Cho quasi-mêtric d: X × X −→ [0, ∞). Tập tất cả các hình cầu
mở có dạng
Bd (x, ε) = {y ∈ X : d(x, y) < ε} , ∀x ∈ X, ε > 0

là cơ sở của tôpô yếu T (d) trên

1.2.3

q.

Định lý ánh xạ co trong không gian quasi-mêtric


Định nghĩa 1.2.5 Cho d là một q-mêtric trên X. Hàm ds : X × X −→ [0, ∞)
được định nghĩa như sau:
ds (x, y) = max(d(x, y), d(y, x)), ∀x, y ∈ X

Dễ dàng kiểm tra được ds là một mêtric trên X.
Định nghĩa 1.2.6 Không gian quasi-mêtric (X, d) được gọi là song đầy đủ nếu
không gian mêtric (X, ds ) đầy đủ.
Ví dụ 1.2.3 Cho d là q-mêtric trên R được xác định như sau:
d(x, y) = max(y − x, 0), ∀x, y ∈ R

Khi đó ds (x, y) = |x − y| là một mêtric thông thường trên R nên (R, ds ) là không
gian mêtric đầy đủ. Do đó (R, d) là không gian q-mêtric song đầy đủ.

9


Ví dụ 1.2.4 Không gian ((0, ∞] , u−1 ), trong đó
1 1
u−1 (x, y) = max( − , 0), ∀x, y ∈ (0, ∞]
y x

là không gian quasi-mêtric song đầy đủ.
Thật vậy, ((0, ∞] , u−1 ) là không gian q-mêtric (theo ví dụ 1.2.2).
1
1
x
y
Khi đó ds (u, v) = |v − u|, ∀u, v ∈ [0, ∞) .

Đặt u = , v = , ∀x, y ∈ (0, ∞] ta có u−1 (x, y) = max(v − u, 0) = d(u, v).


Mà (R, ds ) là không gian mêtric đầy đủ và [0, ∞) đóng trong R.
Do đó ([0, ∞) , ds ) đầy đủ hay ((0, ∞] , us−1 ) đầy đủ.
Vậy không gian q-mêtric ((0, ∞] , u−1 ) song đầy đủ.
Định lí 1.2.7 [4]. Cho quasi-mêtric d : X × X −→ [0, ∞) song đầy đủ và hàm
f : X → X sao cho tồn tại c ∈ [0, 1) sao cho d(f (x), f (y)) ≤ c.d(x, y), ∀x, y ∈ X .
Khi đó tồn tại duy nhất a ∈ X sao cho a = f (a).
Chứng minh: Lấy x0 ∈ X . Đặt x1 = f (x0 ), x2 = f (x1 ), ..., xn = f (xn−1 ), ...
Với mỗi n ∈ N ta có
d(xn , xn+1 ) = d(f (xn−1 ), f (xn )) ≤ c.d(xn−1 , xn )
= c.d(f (xn−2 ), f (xn−1 )) ≤ c2 .d(xn−2 , xn−1 )
...
≤ cn .d(x0 , x1 )
∀n, p ∈ N,
d(xn , xn+p ) ≤ d(xn , xn+1 ) + d(xn+1 , xn+2 ) + ... + d(xn+p−1 , xn+p )
≤ cn .d(x0 , x1 ) + cn+1 .d(x0 , x1 ) + ... + cn+p−1 .d(x0 , x1 )
= (cn + cn+1 + ... + cn+p−1 ).d(x0 , x1 )
1 − cp
= cn .
.d(x0 , x1 )
1−c
cn
≤
.d(x0 , x1 ) ≤ cn .d(x0 , x1 )
1−c

Vì c ∈ [0, 1) nên lim d(xn , xn+p ) = 0.
n,p→∞

Tương tự lim d(xn+p , xn ) = 0.

n,p→∞

Suy ra ∀ε > 0, ∃ nε sao cho d(xn , xm ) < ε, ∀n, m ≥ nε hay (xn ) là dãy Cauchy
trong không gian (X, d).
Vì (X, d) là không gian q-mêtric song đầy đủ nên tồn tại a ∈ X sao cho
lim d(xn , a) = 0 = lim d(a, xn )

n→∞

n→∞

10


Ta có
d(a, f (a)) ≤ d(a, xn+1 ) + d(xn+1 , f (a)) = d(a, xn+1 ) + d(f (xn ), f (a))
≤ d(a, xn+1 ) + c.d(xn , a), ∀n ∈ N

Suy ra d(a, f (a)) = 0.
Tương tự, d(f (a), a) = 0.
Do đó
d(a, f (a)) = d(f (a), a) = 0

Suy ra a = f (a).
Giả sử f có điểm bất động b ∈ X mà b = a. Khi đó
0 ≤ d(a, b) = d(f (a), f (b)) ≤ c.d(a, b) < d(a, b)

Vì 0 ≤ c < 1 nên mâu thuẫn.
Vậy f có điểm bất động duy nhất a ∈ X .
Không gian quasi-mêtric đóng vai trò quan trọng trong lý thuyết không gian

độ phức tạp của Schellekens, là nền tảng cho sự phân tích tiệm cận độ phức tạp
của các chương trình và thuật toán.

1.3

Không gian độ phức tạp (complexity space)

Một bài toán thường có nhiều thuật toán để giải. Tùy vào mục đích và tình
huống cụ thể mà ta sẽ chọn các thuật toán giải cho phù hợp. Thông thường,
người ta quan tâm tới thuật toán nào giải nhanh nhất, tốn ít thời gian nhất.
Thời gian thực hiện thuật toán phụ thuộc vào các yếu tố sau:
• Kích thước dữ liệu: nói chung, dữ liệu càng lớn thì thời gian xử lý càng

chậm. Nếu gọi n là kích thước dữ liệu thì thời gian thực hiện thuật toán
có thể biểu diễn một hàm của n là T(n).
• Phần cứng máy tính.
• Ngôn ngữ, chương trình dịch ngôn ngữ.

Vì vậy, ta không thể chỉ dựa vào thời gian thực hiện thuật toán để xác định
T(n), vì nó còn phụ thuộc vào các yếu tố khác (máy tính, chương trình,...). Cách
đánh giá thời gian thực hiện thuật toán độc lập với máy tính và các yếu tố liên
quan khác (ngôn ngữ, chương trình,...) dẫn đến khái niệm độ phức tạp của thuật
toán.
11


Đánh giá thời gian thực hiện thuật toán không phải là xác định thời gian
tuyệt đối để thực hiện thuật toán (chạy thuật toán mất bao nhiêu giây, phút,...)
mà là xác định mối liên quan giữa dữ liệu đầu vào và chi phí (số thao tác, số
phép tính cộng, trừ, nhân, chia, khai căn,...) để thực hiện thuật toán. Người ta

không quan tâm đến thời gian tuyệt đối của thuật toán vì yếu tố này phụ thuộc
vào tốc độ của máy tính, các máy tính khác nhau thì tốc độ khác nhau. Chi phí
thực hiện thuật toán là một hàm số phụ thuộc vào dữ liệu đầu vào. Khi phân
tích thuật toán, thường chỉ chú ý đến mối liên quan giữa độ lớn dữ liệu vào và
chi phí. Độ lớn dữ liệu vào thường được thể hiện bằng số tự nhiên n và chi phí
thực hiện thuật toán là một hàm phụ thuộc n là T = f (n).
Ta cần lưu ý rằng f (n) không chỉ phụ thuộc độ lớn n mà còn phụ thuộc dữ
liệu vào cụ thể là gì và phân bố trong bộ nhớ ra sao. Vì vậy, cùng một thuật
toán, thực hiện trên cùng một máy tính có thể cho ra các thời gian chạy khác
nhau. Ta phân biệt ba trường hợp sau:
• Trường hợp xấu nhất: thời gian chạy lớn nhất của thuật toán trên tất cả

các dữ liệu cùng kích cỡ n.
• Trường hợp tốt nhất: thời gian chạy ít nhất của thuật toán trên tất cả các

dữ liệu cùng kích cỡ n.
• Trường hợp trung bình: trung bình thời gian chạy của thuật toán trên tất

cả các dữ liệu cùng kích cỡ n.
Để xác định chính xác thời gian chạy của thuật toán là nhiệm vụ khó khăn.
Tuy nhiên trong nhiều tình huống, ta chỉ cần biết xấp xỉ thời gian chạy của
thuật toán tốt hơn là thời gian chính xác. Vì vậy, phân tích tiệm cận độ phức
tạp thuật toán tập trung vào việc đánh giá thời gian chạy thuật toán.
Định nghĩa 1.3.1 Đặt RT = {f : N → (0, +∞]}; g, f ∈ RT . Ta nói g ∈ O(f )
nếu tồn tại n0 ∈ N, c ∈ [0, ∞) sao cho g(n) ≤ c.f (n), ∀n ∈ N, n ≥ n0 .
Như vậy, nếu g ∈ O(f ) thì hàm f đưa ra một tiệm cận chặn trên của thời gian
chạy g và cho ta thông tin xấp xỉ về thời gian chạy g .
Định nghĩa 1.3.2 Tập O(f ) được gọi là lớp tiệm cận độ phức tạp của f .
Ký hiệu:
∞


C=

2−n .

f ∈ RT
n=1

12

1
<∞
f (n)


Hàm dC được định nghĩa:
∞

2−n .max(

dC (f, g) =
n=1

1
1
−
, 0), ∀f, g ∈ C
g(n) f (n)

1

= 0.
∞
Dễ dàng kiểm tra được dC là một quasi-mêtric trên C .

Ở đây ta quy ước

Mệnh đề 1.3.3 Không gian quasi-mêtric (C, dC ) là song đầy đủ.
Chứng minh:
Ta có ∀n ∈ N, f (n) ∈ (0, +∞].

1
1
−
, 0) = u−1 (f (n), g(n)), ∀n ∈ N, ∀f, g ∈ C .
g(n) f (n)
Mà không gian q-mêtric ((0, +∞] , u−1 ) song đầy đủ (theo ví dụ 1.2.4). Từ đó

Mặt khác, max(

suy ra không gian (C, dC ) là song đầy đủ.
Định nghĩa 1.3.4 Hàm f thuộc tập C được gọi là hàm độ phức tạp. Không
gian quasi-mêtric (C, dC ) được gọi là không gian độ phức tạp.
Một không gian con bất kỳ của không gian (C, dC ) cũng được gọi là không gian
độ phức tạp.
Nhận xét 1.3.1 Với f, g ∈ C, f = g ta có
∞

2−n .max(

dC (f, g) =

n=1

1
1
−
, 0).
g(n) f (n)

Khi đó dC (f, g) = 0 ⇔ f (n) ≤ g(n), ∀n ∈ N ⇒ f ∈ O(g).
Ký hiệu C ∗ =

f : N → R+

∞

2−n .f (n) < ∞ , dC ∗ được định nghĩa:

n=1
∞

2−n .max(g(n) − f (n), 0), ∀f, g ∈ C ∗

dC ∗ (f, g) =
n=1

Ta có dC ∗ là một quasi-mêtric trên C ∗ , không gian (C ∗ , dC ∗ ) là không gian quasimêtric.
1
Xét hàm ϕ : C ∗ → C , với ϕ(f ) = , ∀f ∈ C ∗ .
f


Ta có ϕ là một phép đẳng cự. Thật vậy,
1 1
dC (ϕ(f ), ϕ(g)) = dC ( , ) = dC ∗ (f, g), ∀f, g ∈ C ∗ .
f g

Định nghĩa 1.3.5 [7]. Không gian (C ∗ , dC ∗ ) được gọi là không gian độ phức tạp
đối ngẫu.
13


1.4

Thuật toán Chia để trị (Divide và Conquer) và
phương trình đệ quy

Ứng dụng của lý thuyết Không gian độ phức tạp là để phân tích tiệm cận
độ phức tạp của thuật toán Chia để trị, được nghiên cứu bởi Schellekens. Ông
đã chứng minh rằng thuật toán Mergesort có tiệm cận thời gian chạy trung bình
là tối ưu. Để làm điều này, ông đã giới thiệu phương pháp mới dựa vào định lý
điểm bất động của phiếm hàm được định nghĩa trên không gian độ phức tạp
vào chính nó để phân tích thời gian chạy của thuật toán Chia để Trị. Để hiểu
được ý nghĩa và ứng dụng của không gian mêtric suy rộng Baire trình bày trong
luận văn, trong phần này, ta sẽ tìm hiểu một cách sơ lược thuật toán Chia để
trị và phương trình đệ quy.

1.4.1

Thuật toán Chia để Trị

1. Nội dung thuật toán gồm ba phần:

. Chia: phân tích bài toán có kích thước dữ liệu n thành các bài toán
có kích thước dữ liệu nhỏ hơn.
. Trị: giải bài toán con bằng phương pháp đệ quy cho đến khi bài toán
con đủ nhỏ có thể giải quyết theo cách đơn giản.
. Tổng hợp: tổng hợp nghiệm của các bài toán con thành nghiệm bài
toán ban đầu (bài toán gốc).
2. Các bài toán phổ biến sử dụng thuật toán Chia để Trị:
1) Sắp xếp kiểu trộn (Mergesort).
2) Sắp xếp nhanh (Quicksort).
3) Tìm kiếm nhị phân (Binary search).
4) Nhân các số nguyên lớn.
5) Xếp lịch thi đấu thể thao.
...

1.4.2

Phương trình đệ quy

Phương trình đệ quy là phương trình biểu diễn mối liên hệ giữa T (n) và
T (k), trong đó, T (n) là thời gian thực hiện chương trình với kích cỡ dữ liệu nhập
14


là n, T (k) là thời gian thực hiện chương trình với kích cỡ dữ liệu nhập là k ,
k < n.
Ta gọi T (n) là thời gian để giải bài toán kích thước n, T (k) là thời gian để
giải bài toán kích thước k . Khi đệ quy dừng, ta phải xem xét khi đó chương
trình cần làm gì và tốn bao nhiêu thời gian, giả sử là c(n). Khi đệ quy chưa dừng
thì ta xem xét có bao nhiêu lời gọi đệ quy với kích thước k , ta sẽ có bấy nhiêu
T (k). Ngoài ra, ta phải xét thêm thời gian để phân chia bài toán và tổng hợp

các lời giải, giả sử là h(n).
Dạng tổng quát của một phương trình đệ quy là:
c(n)

T (n) =

F (T (k)) + h(n)

trong đó c(n) là thời gian thực hiện chương trình ứng với trường hợp đệ quy
dừng
F (T (k)) là đa thức của các T (k), h(n) là thời gian phân chia bài toán và tổng
hợp các kết quả.
Trong luận văn này, ta quan tâm đến việc giải nghiệm của phương trình đệ
quy sau:
c
nếu n = 1
T (n) =
(1)
n
a.T ( ) + h(n) nếu n ∈ ωb
b

n
b

trong đó T (n) là thời gian để giải bài toán kích thước n, T ( ) là thời gian để
n
, T (1) = c. Khi n > 1, ta phải giải đệ quy a bài toán
b
n

n
con kích thước nên thời gian cho a lời giải đệ quy là a.T ( ). Ngoài ra, thời
b
b
gian để phân chia bài toán và tổng hợp các kết quả là h(n), ωb = bk : k ∈ N ,

giải bài toán kích thước

c ∈ [0, ∞).

Nghiệm của phương trình đệ quy (1) cho ta thời gian chạy của thuật toán
và xác định độ phức tạp của thuật toán.

1.5

Nghiệm của phương trình đệ quy trong thuật
toán Chia để trị

Ký hiệu Cb,c = {f ∈ C : f (1) = c, f (n) = ∞, ∀n ∈
/ ωb , n > 1}. Ta có Cb,c ⊂ C .
Vì không gian q-mêtric (C, dC ) song đầy đủ nên (C, dsC ) đầy đủ. Mà Cb,c đóng
trong (C, dsC ). Do đó (Cb,c , dsC ) đầy đủ. Suy ra không gian (Cb,c , dC ) song đầy đủ.
15


Xét phiếm hàm ΦT : Cb,c → Cb,c được xác định như sau:

nếu n = 1

c

∞
nếu n ∈
/ ωb , n > 1 (2)
ΦT (f )(n) =

 a.f ( n ) + h(n) nếu n ∈ ω , n > 1.
b
b

Nhận xét 1.5.1 T(n) là nghiệm của phương trình đệ quy (1) khi và chỉ khi nó
là điểm bất động của phiếm hàm ΦT .
Định lí 1.5.1 [9]. Cho ΦT là phiếm hàm trên Cb,c được xác định như trên. Khi
đó ΦT là ánh xạ co, có điểm bất động duy nhất.
Chứng minh: Ta có
∞

2−n .max(

dC (ΦT (f ), ΦT (g)) =
n=1

1
1
−
, 0).
ΦT (g) ΦT (f )

Nếu n = 1 hoặc n > 1 mà n ∈
/ ωb thì dC (ΦT (f ), ΦT (g)) = 0, do đó
2−n .(


dC (ΦT (f ), ΦT (g)) =
n=bk ,k≥0

1
1
−
).
ΦT (g) ΦT (f )

Khi k = 0 thì ΦT (f )(1) = c = ΦT (g)(1).
Nên
1
1
−
)
n
n
)
+
h(n)
)
+
h(n)
a.g(
a.f
(
{n=bk ,k≥1}
b
b

n
n
a.f ( ) + h(n) − (a.g( ) + h(n))
−n
b
b
=
2 .
n
n
(a.g( ) + h(n)).(a.f ( ) + h(n))
{n=bk ,k≥1}
b
b
n
n
a.(f ( ) − g( ))
−n
b
b
≤
n
n .2
{n=bk ,k≥1} a.f ( b ).a.g( b )
1
f (n) − g(n) −n
.2
≤ .
a
f (n).g(n)

k
2−n .(

dC (ΦT (f ), ΦT (g)) =

{n=b ,k≥0}

1
≤ .
a

(
{n=bk ,k≥0}

1
1
1
−
).2−n ≤ .dC (f, g).
g(n) f (n)
a

Vì a > 1 nên ΦT là một ánh xạ co. Mặt khác, không gian (Cb,c , dC ) là không
gian đầy đủ nên phiếm hàm ΦT có điểm bất động duy nhất. Vì vậy phương trình
đệ quy (1) có duy nhất nghiệm.
16


Nhận xét 1.5.2 ΦT là hàm đơn điệu trên Cb,c , nghĩa là ∀f, g ∈ Cb,c , f ≤ g ⇒
ΦT (f ) ≤ ΦT (g).

Định nghĩa 1.5.2 [9]. Cho C ⊆ RT , phiếm hàm Φ : C → C được gọi là một
phiếm hàm cấp tiến (improver) đối với hàm f ∈ C nếu và chỉ nếu
Φn+1 (f ) ≤ Φn (f ), ∀n ∈ N.

Ta quy ước φ0 (f ) = f . Khi Φ đơn điệu, để chỉ ra Φ là một cấp tiến đối với hàm
f thì ta chỉ cần chứng tỏ Φ(f ) ≤ f .
Từ các kết quả trên, ta có định lí sau:
Định lí 1.5.3 [5]. Phương trình đệ quy của thuật toán Chia để trị dạng (1) có
duy nhất nghiệm fT trong Cb,c . Hơn nữa, nếu phiếm hàm ΦT tương ứng với dạng
phương trình đệ quy (1) là đơn điệu và được cho bởi (2) là một phiếm hàm cấp
tiến đối với một hàm g ∈ Cb,c thì nghiệm fT của phương trình đệ quy thỏa mãn
fT ∈ O(g).

17


Chương 2
Không gian mêtric suy rộng Baire
Khi một chương trình sử dụng quá trình đệ quy để tìm nghiệm bài toán, sau
mỗi bước đệ quy, ta luôn thu được nghiệm tốt hơn, theo nghĩa có độ chính xác
cao hơn và nghiệm cuối cùng thu được là giới hạn của một quá trình tính toán.
Dựa trên lý thuyết sắp thứ tự và tôpô, Scott đã mô hình hóa quá trình đệ quy
như những dãy tăng các phần tử của tập sắp thứ tự hội tụ đến chặn trên nhỏ
nhất đối với tôpô đã cho. Năm 1994, Matthews đã giới thiệu khái niệm p-mêtric
(partial metric hay mêtric riêng) cung cấp một công cụ toán học hỗ trợ việc mô
hình hóa quá trình tính toán dựa trên ý tưởng của Scott. Không gian p-mêtric
đóng vai trò quan trọng trong lịch sử hình thành không gian mêtric suy rộng
Baire. Trong phần tiếp theo, ta sẽ tìm hiểu một số khái niệm, tính chất p-mêtric
để biết tầm quan trọng của nó.


2.1
2.1.1

Không gian p-mêtric (mêtric riêng)
Định nghĩa không gian p-mêtric

Định nghĩa 2.1.1 [4]. Cho X là một tập khác rỗng. Một hàm p: X × X −→ R+
(R+ = [0, ∞)) được gọi là một p-mêtric (partial metric, mêtric riêng) nếu:
i) ∀ x, y ∈ X : x = y ⇔ p(x, x) = p(x, y) = p(y, y);
ii) ∀ x, y ∈ X : p(x, x) ≤ p(x, y);
iii) ∀ x, y ∈ X : p(x, y) = p(y, x);
iv) ∀ x, y, z ∈ X : p(x, y) ≤ p(x, z) + p(z, y) − p(z, z).
Lúc đó cặp (X, p) được gọi là một không gian p-mêtric hay là không gian mêtric
riêng.
18


Ví dụ 2.1.1 Cho X = R+ = [0, ∞), p: X × X −→ R+ xác định bởi:
p(x, y) = max{x, y}, ∀x, y ∈ X.

Khi đó (X, p) là một không gian p-mêtric.
Dễ dàng kiểm tra p thỏa mãn các điều kiện i), ii), iii) và iv) của một p-mêtric.
Do đó (X, p) là một không gian p-mêtric.
Nhận xét 2.1.1
i) p là một mêtric nếu p là một p-mêtric thỏa mãn ∀ x ∈ X : p(x, x) = 0.
ii) Nếu p(x, y) = 0 thì từ các tính chất i), ii), iii) suy ra x = y .
Nhưng ngược lại không đúng. Thật vậy, xét không gian ở ví dụ 2.1.1,
p(x, x) = x không nhất thiết phải bằng 0.
iii) Nếu p là một p-mêtric trên X thì hàm pm : X × X −→ R+ xác định bởi:
pm (x, y) = 2.p(x, y) − p(x, x) − p(y, y), ∀ x, y ∈ X


là một mêtric trên X.
Định nghĩa 2.1.2 [2]. Cho (X, p) là không gian p-mêtric , x0 ∈ X, ε > 0.
Bp (x0 , ε) = {y ∈ X | p(x0 , y) < ε + p(x0 , x0 )}

được gọi là hình cầu mở tâm x0 , bán kính ε.
Định lí 2.1.3 [4]. Tập tất cả các hình cầu mở của không gian p-mêtric (X, p)
là cơ sở của tô pô T (p) trên X.

2.1.2

Sự hội tụ

Định nghĩa 2.1.4 [10]. Cho (X, p) là không gian p-mêtric, (xn ) là một dãy
trong X và x0 ∈ X . Ta nói dãy (xn ) hội tụ về x0 nếu lim p(xn , x0 ) = p(x0 , x0 ) và
n→∞

ký hiệu xn → x0 .
Lúc đó x0 được gọi là giới hạn của dãy (xn ).
Như vậy,
xn → x0 ⇔ lim p(xn , x0 ) = p(x0 , x0 )
n→∞

⇔ ∀ ε > 0, ∃ n0 ∈ N, ∀ n ≥ n0 : |p(xn , x0 ) − p(x0 , x0 )| < ε
⇔ ∀ ε > 0, ∃ n0 ∈ N, ∀ n ≥ n0 : p(xn , x0 ) − p(x0 , x0 ) < ε.
19


Nhận xét 2.1.2 Giới hạn của dãy (nếu có) là không duy nhất.
Thật vậy, cho X = R− , p(x, y) = − min {x, y} , ∀ x, y ∈ R− . Ta có p là p-mêtric


1
1
n
n
1
Với mọi ε > 0, tồn tại n0 ∈ N sao cho ∀n ∈ N, n ≥ n0 mà − > x, ta có
n

1
n

trên R− . Xét dãy (− ), ∀n ∈ N∗ . Khi đó ∀ x ∈ X : p(− , x) = −min − , x .

1
p(− , x) = −x = p(x, x) < p(x, x) + ε.
n

Suy ra
1
p(− , x) − p(x, x) < ε.
n
1
n

Do đó (− ) hội tụ về x không duy nhất.
Định nghĩa 2.1.5 [14]. Dãy (xn ) trong không gian p-mêtric (X, p) được gọi là
hội tụ thực sự (properly converges) về x0 nếu (xn ) hội tụ về x0 và
lim p(xn , xn ) = p(x0 , x0 ).


n→∞

Như vậy, (xn ) hội tụ thực sự đến x0 ⇔ lim p(xn , xn ) = lim p(xn , x0 ) = p(x0 , x0 ).
n→∞

n→∞

Nhận xét 2.1.3 Giới hạn của một dãy hội tụ thực sự (nếu có) là duy nhất.
Thật vậy, giả sử (xn ) hội tụ thực sự đến x, x . Ta có:
p(x, x ) − p(x, x) ≤ p(x, xn ) + p(xn , x ) − p(xn , xn ) − p(x, x)
= p(xn , x) − p(x, x) + p(x , xn ) − p(xn , xn )

Vì (xn ) hội tụ thực sự về x, x nên p( xn , x)−p(x, x) < 2ε và p( xn , x )−p( xn , xn ) < 2ε .
Suy ra p( x, x ) − p( x, x) < ε, ∀ ε > 0. Nên p( x, x ) = p( x, x). Tương tự, ta có
p( x, x ) = p( x , x ). Do đó p( x, x ) = p( x, x) = p( x , x ). Vậy x = x .

2.1.3

Quan hệ thứ tự trên không gian p-mêtric

Định nghĩa 2.1.6 [4]. Cho (X, p) là không gian p-mêtric, p : X × X −→ R+ .
p là một quan hệ hai ngôi sao cho
∀x, y ∈ X : x

py

⇔ p(x, x) = p(x, y)

Định lí 2.1.7 [4]. Cho X là tập khác rỗng, p-mêtric p : X × X −→ R+ . Khi đó
p là một quan hệ thứ tự riêng.

20


Chứng minh: Ta chứng minh
i) ∀ x ∈ X, x

px

p

có tính phản xạ, đối xứng và bắc cầu.

⇔ p(x, x) = p(x, x).

ii) ∀x, y ∈ X,
x

py

⇒ p(x, x) = p(x, y) = p(y, x)

y

px

⇒ p(y, y) = p(x, y) = p(y, x)

⇒ p(x, x) = p(x, y) = p(y, y) ⇒ x = y.

iii) ∀x, y, z ∈ X ,

x

py

và y

pz

⇒

p(x, y) = p(x, x)
p(y, y) = p(y, z)

Mà p(x, z) ≤ p(x, y) + p(y, z) − p(z, z).
Suy ra p(x, z) ≤ p(x, y) = p(x, x).
Mặt khác, p(x, x) ≤ p(x, z), ∀ x, z ∈ X .
Do đó p(x, z) = p(x, x). Vậy x

pz.

Định nghĩa 2.1.8 Cho tập X khác rỗng. (X, p,
p-mêtric trên tập có thứ tự nếu

p)

được gọi là một không gian

i) (X, p) là không gian p-mêtric;
ii) (X,


p)

là một tập thứ tự.

Định lí 2.1.9 [4]. Cho (X, p) là không gian p-mêtric, p : X × X −→ R+ . Hàm
dp : X × X −→ R+ được xác định như sau:
dp ( x, y) = p(x, y) − p(x, x), ∀ x, y ∈ X

là một q-mêtric mà T (p) = T (dp ) và

q

=

p.

Chứng minh: Trước tiên, ta chứng minh dp là một quasi-mêtric.
i) ∀ x, y ∈ X : x = y ⇒ p(x, x) = p(x, y) = p(y, y)
⇒ dp (x, y) = 0 = dp (y, x).

∀ x, y ∈ X, dp (x, y) = dp (y, x) = 0
⇒ p(x, y) − p(x, x) = p(y, x) − p(y, y) = 0
⇒ p(x, y) = p(x, x) = p(y, y) ⇒ x = y.
21


ii) ∀ x, y, z ∈ X : p(x, z) ≤ p(x, y) + p(y, z) − p(y, y)
⇒ dp (x, z) = p(x, z) − p(x, x) ≤ p(x, y) + p(y, z) − p(y, y) − p(x, x)
≤ dp (x, y) + dp (y, z)


Vậy dp là q-mêtric.
Tiếp theo, ta chứng minh T (p) = T (dp ) và

q

p.

=

Thật vậy, lấy x ∈ X , ε > 0. Giả sử y ∈ Bdp (x, ε). Khi đó
dp (x, y) = p(x, y) − p(x, x) < ε

Suy ra p(x, y) < ε + p(x, x). Nên y ∈ Bp (x, ε).
Do đó T (dp ) ⊆ T (p).
Ngược lại, nếu y ∈ Bp (x, ε).Ta có
p(x, y) < ε + p(x, x) ⇒ dp (x, y) = p(x, y) − p(x, x) < ε.

Do đó y ∈ Bdp (x, ε) và T (p) ⊆ T (dp ).
Vậy T (p) = T (dp ).
Vì ∀ x, y ∈ X, p(x, x) = p(x, y) ⇔ dp (x, y) = 0 nên

2.1.4

q

=

p.

Không gian p-mêtric đầy đủ


Định nghĩa 2.1.10 [10] Cho (X, p) là không gian p-mêtric. Dãy (xn ) trong X
được gọi là dãy Cauchy nếu tồn tại lim p(xn , xm ) hữa hạn.
n,m→∞

Định lí 2.1.11 [10]. Dãy (xn ) trong không gian p-mêtric (X, p) được gọi là dãy
Cauchy nếu và chỉ nếu (xn ) là dãy Cauchy trong không gian mêtric ( X, pm ),
trong đó:
pm (x, y) = 2.p(x, y) − p(x, x) − p(y, y), ∀ x, y ∈ X.

Bổ đề 2.1.12 [11]. Cho (X, p) là không gian p-mêtric. Dãy (xn ) trong X là dãy
Cauchy nếu và chỉ nếu
∀ε > 0, ∃n0 ∈ N : p(xn , xm ) − p(xn , xn ) < ε, ∀m, n ≥ n0 . (∗)

Chứng minh:
(⇐) Cho (xn ) là dãy trong (X, p) thỏa (∗).
22