L600T
AM
KHOA
HOC VA CONG
NGHE VIET
NAM
iw^ACH
DAI HOC VA SAU DAI HOC
•
• • • •
LE
CONG
THANH
NHA
XUAT
BAN
KHOA
HOC
TU" NHIEN
VA CONG
NGHE
L
LE
CONG THANH
Bien
muc tren xuat ban pham cua
Thu
vien Quoc gia Viet Nam
Le
Cong Thanh
Ly
DAI
HOC
VA SAU DAI HOC
HOI
DONG
BIEN TAP
Chu
t[ch
HQI
dong:
GS. TSKH. NGUYEN DINH CONG
Cac
uy vien:
1.
GS.
TSKH.
Ngo
Viet
Trung,
2.
GS. TS. Nguyen Dai Hung,
3. GS. TSKH.Tn\nVanSung,
4.
GS. TS. Le Tran
Binh.
'i'f
I
(if
\
I
kit qua nghien cuu cd gid tri cua Vien da ra dai phuc vu ddc
luc
cho su nghiep xdy dung vd bdo v^ To quoc. De tong hap vd
giai
thieu c6 he thong a trinh do cao cdc cong trinh vd ket qud
nghien cuu tai ban doc trong nuac vd quoc te, Vien
Khoa
hoc vd
Cong
nghe Viet Nam quyet dinh xudt bdn bo sdch chuyen khdo.
Bo
sdch tap trung vdo bdn
iTnh
vuc sau:
-
ling
dung
vd
phdt trien cong nghe cao;
-
Tdi nguyen thien nhien vd mdi truang
Viet
Nam;
-
Bien
vd cong nghe bien;
-
Gido
trinh dgi
hQC
manh me trong khoang bon
miroi
nam qua. Ly thuyet nay nghien
ciiu
tinh
hieu qua cua cac mo
hinh
tinh
toan va cua thuat toan noi rieng, nhSm phan chia cac bai
toan theo do phiic tap cua thuat toan
giai
chung thanh nhiing Idp
phutc tap khac nhau, va qua do tao nen mot hinh anh khai quat ve
tinh
phiic tap cua cac bai toan noi chung.
Ly
thuyet do philc tap
tinh
toan, dac biet nhiing kgt qua khao
sat ve moi quan he
giiia
cac 16p phiic tap va ve ban chat cua mot
so Idp quan trong, cho ta nhiing
hidu
biet t6ng quat ve van de phiic
tap va hudng dan ta
each
xii
ly
diing
sau sic vg qua
trinh
tinh
toan cua thuat toan
giiip
ta phan
tich
va danh gia mot
each
chuin xac do phiic tap
ciia
thuat toan. Han
niia,
nhiing
hi6u
biet ay c6 thg goi md cho ta hudng cai
tign
hoac
tim
kiem thuat toan tot hon.
Nhu
vay, ly thuyet do phiic tap
tinh
toan khong chi cho ta mot
each
nhin thong nhat ve van de phiic tap cua cac bai toan ma con
giiip
ta tim ra hudng
giai
quyet hop ly khi xem xet nhiing bai to^n
la
nham dap ling phan nao nhu cau cua doc gia muon tim hi6u noi
dung cd ban cua ly thuyet nay, trong boi canh tai lieu tieng
Viet
vg
linh
vuc nay con rat khan hiem.
Mong
muon la vay, nhimg nhOlng
muc tieu nay kho c6 the dat
dUdc
tron ven. B5i vi, ly thuyet do
phiic tap
tinh
toan qua that la philc tap va dang diroc phat trign
manh me, cho nen mot vai hu6ng nghien
cilu
md\i nhuing ket qua
ly thu va nhieu ufng dung hieu qua cua no ciing kho c6 the
duoc
trinh
bay trong mot khuon kh5 han che.
V6i muc tieu kg trgn, tac gia c6
gSng
lua chon nhflng chu de
thiet
thuc va
trinh
bay rnot
each
tinh
toan tSng quat, mo hinh
may Turing, cung nhu
viec
phan chung thanh nhUng Idp phiic tap.
Chuong 1 nghien
ciiu
may Turing va cac bien thg chinh cua no,
chii
yeu la khao sat kha nSng doan nhan ngon ngu cua may, nhSim
ly giai tai sao may Turing
duoc
chon lam mo
hinh
tmh toan tSng
quat. Do may Turing
duoc
de xuat v6i muc dich chinh xac hoa
khai
niem thuat toan, tao co sd dg c6 thg chiing minh "cac bai toan
khong giai
duoc",
cho ngn phan cuoi chuong nay gidi thieu mot vai
VI
du don gian nhu nhung minh chiing ve cac bai toan khong giai
duoc
de doc gia tham khao them. Hon nfla, noi dung ciia phan nay
tuy
nam
ngoai
thdi
gian va
trat
tu khong gian
doi vdi cac Idp phflc tap nham chflng to
tinh
nan giai cua nhigu bai
toan.
Phan
con lai ciia chfldng nay gidi thieu
each
tiep can mot van
d^
trung
tarn
va kha nan giai hien nay, van dg P = NP.
Chuong cuoi ciing, CliUdng 5, danh dg gidi thieu cac hudng
nghign cflu ma e6 kha nang mang lai nhflng giai phap
tich
cue doi
vdi cac van de nay sinh, dac biet trong hoat
dong
thuc tign.
Nhu tren da ngu, do khuon kho han che, mot so chu de ly thu
nhung khong
dUOc
dua vao cuon
sach
nay, nhu He bhng chiing xac
suat va Tinh toan
tinh
toan va ciia ly thuygt do phflc tap
tinh
toan
noi
rigng; cuon
sach
[11] chuygn ve
tinh
NP-day
du, ngn cd phan
Phu luc - mot Danh
sach
bao gom hon ba tram bai toan
NP-day
dii
duoc
biet dgn cho tdi
thdi
digm do. Danh
sach
nay hien nay vln
duoc
nhieu ngudi sfl dung.
B6n chuong dau cua cuon
sach
nay cd thg dung lam chuygn de
giang
day cao hoc
hoac
nhung nhan xet va gop y cua dong nghiep va cua doc gia gan xa
ve cuon sach nay. Moi nhan xet v^ gop y xin dtroc giii vg dia chi:
leecthanhSgmail. com/.
Ha Noi, thang 8 nam 2013
Tac gia
Muc luc
L6i tiia iii
0 Md d§u 1
0.1 Cac thuat ngu: va khai niem 2
0.1.1 Tap hop 2
0.1.2 Ham 4
0.1.3 Bicn do tiem can cua ham 6
0.1.4 Logic Boole 8
0.1.5 Dothi 13
0.1.6 Ngon ngu: hinh thiic 18
0.2 Vc ly thuyet do phurc tap tinh toan 20
0.2.1 Vi tri trong Ly thuyet tinh toan 20
0.2.2 Sir ra ddi va phat trien 22
0.3 Cach tiep can cac bai toan 25
0.3.1 Bai toan tim kiem va bai toan quyet dinh . 27
0.3.2 Ngon ngfl bigu dign bai toan quygt dinh . . 29
0.3.3 Doan nhan ngon ngii 32
Bai tap 32
1 May Turing va Thuat toan 35
1.1 May Turing 36
1.1.1 Mo ta 36
1.1.2 Dinh nghia hinh thi'ic 42
1.1.3 Cac chute nang chinh cua may Turing 49
1.2 Mot vai bien thg ciia may Turing 58
1.2.1 May Turing nhieu bang 59
117
2.1 Do phufc tap
thdi
gian cua cac loai may Turing . . . 118
2.1.1 Quy chuin ve
thdi
gian
hoat
dOng cua may . 118
2.1.2
Phan
tich thuat toan 122
2.1.3 Quan he
tlidi
gian giiia cac loai may 132
2.2 May Turing tat dinh
thdi
gian da thufc 138
2.2.1 Thdi gian da thufc va Idp P 138
2.2.2 Thi du ve cac bai toan thuOc Idp P 142
2.3 May Turing khong tat dinh
thdi
gian da thufc . . . 153
2.3.1 Ldp NP va ngon ngfr kic^m chiing nhanh . . 154
2.3.2 Thi du vg cac bai toan thuoc ldp NP 161
2.3.3
VandeP
= NP 166
2.4 Tinh NP-day du 168
2.4.1 Quy dan
3.1.3 Do phufc tap khong gian cua may Turing
khong tat dinh 222
3.2 Nhiing moi quan he co ban ve do phufc tap 224
3.2.1 Quan he giiia
thdi
gian va khong gian 225
3.2.2 Quan he giiia tat dinh va khong tat dinh . . 227
3.3 Do phiic tap khong gian da thiic 229
3.3.1 Cac ldp phufc tap PS va NPS 230
3.3.2 Tinh
PS-day
du 232
3.4 Do phiic tap khong gian loga 242
3.4.1 Cac ldp phiic tap LS va NLS 243
3.4.2 Tinh NLS-day du 245
3.4.3 Quan he giiia NLS va
eo-NLS
251
Bai tap 255
4 Tinh nan giai 259
4.1 Trat tu cua cac ldp phufc tap 260
4.1.1 Trat tir khong gian 260
4.1.2 Trat tii
thdi
gian 267
4.2 Phuong phap quan he hoa va van de P = NP . . . . 271
4.2.1 May Turing vdi tii van 271
4.2.2 Han chl ciia phuong phap dudng
cheo
275
5.2.1 Cac mach
Boole
dong bo 305
5.2.2 Ldp phiic tap NC 308
5.2.3 Tinh
P-day
du 311
X
MUC LUC
5.3 Thuat toan xac suit 312
5.3.1 May Turing xac
suat
va Idp BPP 312
5.3.2 Tinh nguyen to 316
5.3.3 Cac chuong
trinh
phan nhanh 324
5.4 Thuat toan xap xi , 331
5.4.1 Bai toan tap bao quat nho nhat 333
5.4.2 Bai toan do thi con day du Idn nhat 336
5.5 Phan tich xac
suat
cac thuat toan 338
5.5.1 Hieu suit hau
chac
chan cua thuat toan . . 343
5.5.2 Do phirc tap
thdi
gian
trung
trong ciing mot
llnh
vuc - ly thuyet
tinh
toan, va cuoi cung
la
gidi
thieu noi dung chinh cua ly thuyet do phirc tap
tinh
toan,
do la viec phan chia cac bai toan thanh cac Idp theo "dO phiic tap"
cua thuat toan giai chiing.
Dg
CO
the phan Idp d6i vdi cac bai toan thuoc nhigu
linh
vuc
khac
nhau, ly thuyet do phutc tap
tinh
toan xem xet cac bai toan
theo mot thg thong nhat, nhd do
dign
dat chung bang ngon ngiJ
hinh
thufc va tien hanh giai chung
trgn
cung mot mo
hinh
tinh
de ra ma con duoc sii dung thudng
xuyen
trong tai lieu nay.
2 Md dau
0.1
Cac
thuat
ngvt
va
khai niem
0.1.1
Tap hgfp
TSiP
hop
Ih
mot
khai
niem
co
ban cua toan
hoc vk
khong thi
dinh
nghia
duoc
mot
each
chinh xac.
Theo
true quan,
hop thudng
duge
ky
hieu
bdi
cac
chu: cai
La
tinh
A,B,C, ,
hoac
hdi cac
chii
cai
Hy Lap c6
nhir
r,
E,
f), Dg
bilu
thi
"x la
phan
tijf
cua tap hop
E" ta
dung
ky hieu
x G E (doc la
"x thuoc
cua tap hop ay roi dg vko
gifla hai'dau
ngoac
nhgn.
Thi
du,
E
=
{3,5,15,a,i,c,«}
la
tap hop bao gom cac so
3,5,15,
cac
chii
cai
a, b,
c va ky ttr [t-
Ta
CO
3 e E va 5 6 E, con 35 ^ E,
v.v
Viee
mo ta
tap hop b^ng
each
liet
kg
tat
ca cac
phan
la "cac
phan
tii
con
duoc
tiep
tuc
liet
kg
mai mai".
Chang
han, b^ng
each
nay ta
dign
ta tap cdc s6 tii
nhien
N va
tap
cdc so
nguyen
Z
nhu sau:
<
N
=
{i,2,3, }
Z
=
{ ,-2,-1,0,1,2,
each
thong dung hon,
tap
hgp
dugc
dign
ta
bang
each
bilu
thi
dac
tinh
cua cac
phan
tijt
tao nen tap hgp iy, ta eo thg
viet
{
X
I X
CO
dac
tinh
nao do }.
Thi du,
tap cac so
chinh phuong
dugc
dign
khia canh
do.
Nhan
thg ta ky
hieu
tap cdc sd
hitu
ti va tap cdc s6
thiic
tuong ling
la Q va R. Cac ky
hieu
Z+, Q+ va R+
dugc
dung
dg
chi
cdc tap nhflng s6 khong
am
thuoc
Z, Q va R
tuong ling.
Tap
khong
ehiia phan tii
nao
dugc
ggi la tap
rSng
va
ky
hieu \h
A ^ R.
Doi
vdi
hai
tap hgp A vk R,
ta. noi rang
A la tap con
cua
R,
va
ky
hieu
Ik A C B
hoac
R D
A,neu m5i phan tii cua
A
eung deu
la
phan tii
cua R. Ta eon noi
f&ng
A la tap con
thtXc sytcna.
R,
ky higu
la
/I
phan tii eung
thuOe
A va
thuoc
R.
Hieu cua
Avk R,
dugc
ky
hieu
la
>1
\a
tap
bao gom cac
phan tii thuoc
A va
khong thuoc
R.
AUR
AnR
Hinh
0.1
Hgp,
giao
va
hieu cua hai
tap hgp
4
Mci
trirdng
hop khi tat ca k tap deu bang nhau, ta viet
k
AXAX XA
= A'^.
0.1.2 Ham -'-^
•
- - '
'-^^-'^
Ham
la mot d6i tirong quan trong cua toan hoc, phan anh moi quan
he vao-ra tir tap hop nay den tap hop kia. Ham f til tap hop X
den tap hop Y, ta viet f:X —> y, la mot quy tac ma
theo
do m6i
phan
tijf
dau vao thuoc X tao ra
nhiSu
nhdt
mot phan
tiJt
tuong
ling
thuoc Y.
Theo
ham f: X —^ K, khi phan tii x € X c6 phan tut tuong
ling
y
eY,ta
'
xac
dinh
(domain)
cua /. Tap tat ca cac gia tri cua ham /, tiic
i
0.1 Cac
thuat
ngii
vd
khdi
niem
5
tap R = {y\ e Y,3x e X : f(x) = y},
duoc
goi la
miin
gia,
tri
(range)
cua ham do. Ham /
duoc
goi la ham
hoan
toan
xac
dinh,
neu no xac dinh tai moi x 6 X, nghia la D = X. Khi R = Y,
ta noi rang / la ham len.
Vay la khi noi dgn "ham" ta can higu rang do la ham bo
ham /abs, hai so vdi dau. doi
nguoc
nhau
duoc
tudng
ling
vdi ciing mot so,
/abs(")
=
/abs(-^0
= "
doi
vdi moi n > 0. Dua
theo
ham /add) rat nhieu gia tri dau vao
khac
nhau
duoc
tuong
ling
vdi ciing mOt gia tri dau ra,
chang
han
/add(«, -•''0 = 0 doi vdi moi n > 0.
Nhu
vay, ham /: X —> Y la mot mo hinh toan hoc dign dat
quan he vao-ra tiT tap X dgn tap Y, ma
theo
do mOi phan tut cua
X
mot ham tii tap X den tap cac gia tri
chan
ly {DUNG, SAl}. Dg ti?n
dung,
tap {DUNG, SAl} thudng dudc thay thg bdi tap {1,0} neu
khdng
gay nham Ian.
6
M6
dau
Cung
nhu doi vdi bat cuf mo
hinh
nao, mieu ta ham mot each
ro
rang la rat can thiet. Ta c6 thg mo ta ham b^ng nhieu each khac
nhau. Chang han, khi ham /: X —> Y c6 mien xac
dinh
D huu
han va khong qua Idn, ta lap mot danh
sach
theo titng gia tri thuoc
D
ma moi dong la mot cong thute dang f{x) = y vdi day du gia
tri
cu the cua
bi6n
x va gia tri tudng utng y cua ham/,
hoac
lict
tiic
la vdi moi n
hit
dau tit mot so
HQ
nao do. Ta noi do la can tiem can hay la bien
dg
tiem can
cua.
hhin
f
{n).
• • • •
•
Can tren
tiem
can. Ta noi rang "/('O O-ldn cua
(ji^iif
va
ta
viet
/(n) =
0[f/(ri)],
neu ton tai cac so tu nhien c va no sac cho,
doi
vdi moi s6 tu nhien n > no,
/(")
<
cyiji).
Khi
Dieu
nay hoan toan thoa man
dinh
nghIa
hinh
thiic.
0.1 Cac thuat
ngU
va khdi niem
7
That
vay, cho c = 6 va no = 7, ta co 5/)^ + 3n^ + 18/t + 7 < 6n^ doi
vdi
moi n > 7. Hdn
nila,
J\{n) =
t>[n^]
bdi vi n**
luon
16n hdn n^
va
do do cung la can tren
tiem
can cua
/i(n).
The nhung, /i(n)
khong
the la
0[n'^]
bdi
=
txtc va rt^ la
nhiing
can
dudi
tiem
can eua
/i(n).
Tuy
nhien, n'' khong la can
dudi
tiem
can cua
/i(n).
•
Can sat
tiem
can. Ta
viet
/(n) =
e[(y(n)],
neu /(n) =
0[g{n)
va
/(n) =
^[g{n)].
Mot each tUdng
diTdng,
neu ton tai ba so
diidng
o-be
ciia
g{iiy\u
Noi
each khac, f{n) =
o[g{n)\d nghIa rang, ddi vdi mOi s6 thue
c
> 0, ton tai mot n, sao cho f{n) < cg{n) d6i vdi moi n > n,.
Cac
khai
niem
O-ldn
va
0-1)6
tao thanh mot cap tUdng
d&ng.
Khai
niem
O-ldn
the hien ham no khong Idn han mot each item can
so vdi ham kia, eon
khai
niem o-be the hien ham no nho han mot
each
tiem can so vdi ham kia. Sxt khac nhau
gifla
hai
khai
mem
O-ldn
la cac gia
tri chan
ly
DUNG
va
SAI
(TRUE
va
FALSE).
Hinh
thanh
trong
khung canh
cua
toan
hoc
Ung dung, ngay
nay
logic Boole diioc
coi
la
CO
sd cua
dien toan
va
thict
kc may
tinh.
Trudc
khi
nhir
da neu
tren, thudng
duoc
bigu
thi b5i 1 va 0. Ta sut
dung
cac gia tri
Boole trong
cac
boi
canh
hay
trong
cac
tinh
huong vdi
hai kha
nSng
c6 the xay ra.
Chang
han nhu
khi
ta can xcm xet cac sir
kien:
trdi
c6 thg
"tanh"
hoac
"mua",
cac
bien Boole cung dudc
ky
hieu
bcii
cac
chO
cai La
tinh
x,
y, z,
hay
xi,x-2,
Tren
cac
bien Boole, thirc chat
la
tren
cac gia tri
Boole,
ta c6
thg
thao
tac cac
phep
toan
vdi
tinh
sang
tao
doi nguoc
vdi no. Nhu
vay,
ta c6 0 = 1 va
-il
= 0.
Phep
hoi
{conjunction)
hay la
phep
AND, duoc
ky
hieu
bdi
A.
Hoi cua hai
bien
Boole
nhan
gia
tri
1 neu ca hai
bien cung
lay gia tri 1.
Phep
tuyen
{disjunction)
hay la
phep
9
Day
la ba
phep
toan
cd sd cua
logic Boole
va
duoc
the
hien
day
dii
nhu sau:
-,0
= 1 .: 0A0 = 0 0V0 = O
^1
= 0 ' 0A1 = 0 0V1 = 1
1
A 0 0 1 V 0 = 1
1
A 1 - 1 1 V 1 = 1
Ngoai
ra, mot vai
phep
toan Boole khac cung thudng duoc
sii
dung,
do la
phep
chi
neu x va y
nhan nhung
gia
tri
nhu
nhau. Tiep theo,
x
—>
y = 0
neu
va chi neu .; - 1 va y = 0.
Cuoi cung,
x y = 0
neu
va chi
neu X
va y
nhan
cac gia
tri khac nhau.
Cu thg ta c6:
0®0=0
0^0=1 0^0=1
0©1=1
0^1-1 0^1=0
1©0=
1 • 1-^0 = 0 1^0 = 0
1®1
= 0 1-^1 = 1 1^1 = 1
trdi
tanh",
nghia
la x
nhan
gia
tri
1
(trdi
tanh)
va gia
tri
0
(trdi
mua).
Gia
sut
y la mot
bien Boole
bigu
thi
"Ngay
mai
chung
toi
chac
chan
sc di
Choi",
tire
bigu
thi bdi
cong tlnic
don
gian
nhu x ^ y.
Tiep theo,
nhd cac
phep
toan Boole,
ta c6 thg kgt
noi
cac
cong
thilc
Boole
ddn
gian
vdi
nhau
dg thu
dUdc
cac
cong
thilc
Boole phirc
hop, dap
urng
uliuiig
ygu cau
thiic
Boole;
2. Neu A vd B Id cac
cong
thxic
Boole,
thi
cung
Id cac
cong
thiic
Boole;
3.
Khong
c6 mot
cong
thiic
Boole
ndo
khdc
ngodi
cac
cong
thiic
— thu
duac
theo
cac quy tdc I vd2.
Can
liru
xac
dinh
mot ham
P(X1,X2, ,X„) :
{0.1}"
—^
{0,1}.
Dinh
nghia 0.1.2
Cong
thiic
Boole
P
dupe
goi la
hang dung
neu no
dung,
tiic
nhan
gid tri 1, vdi moi
cdch
gdn tri
Boole
cho cdc
bien
cua no; P
duac
goi Id
hang
bu6c
quan trong trong lap luan toan hoc la viec thay
the mOt menh de nay bang mot menh d6
khac
vai cung cac gia tri
0.1 Cdc
thudt
ngU vd
khdi
niem
11
chan ly. Cac menh de vdi cung cac gia tri chan ly duoc coi la
tuang
duang
nhau.
Khai niem nay dudc
dinh
nghia chinh xac nhu sau.
Dinh
nghia 0.1.3 Cdc
cong
thiic
Boole
P vd Q
dupe
gpi Id
Mdng
dvCdng
{equivalent),
vd
-1-P = P
3. Luat suy diSn
p^g
= -PVQ.
4. Luat suy
dign
thuan nghich
p^Q
= (p-g)A(g p).
5. Luat phan phoi ',
PA(gv7?)
= (PAQ)
V(PAP),
py{QAR) =
(PVQ)
A(PV7?).
Nhd
cac bigu thiic tuang duang nay, moi cong thiic
Boole
dgu
CO
thI
bilu
dien dugc
dudi
dang dan gian han ma trong do chi can
Md dau
sil
dung cac
phep
neu cr = 0,
neu (7 = 1
neu cr = 0, • I ' "
neu (7 = 1.
Khi
do,
bang
each
ap dung cac bi6u thiic tUdng duong neu tren, ta
de dang thu dixoc cac dang hOi va tuygn
chuSn
tic ciia mot
cong
thiic
Boole.
'1 '
Dinh ly 0.1.4 Moi cong thvcc Boole P(xi, ,x„) deu c6 cac
dang biiu diin sau day:
(i) Dfing tuyin chudn tdc
P(xi, ,
Xn)
(ii)
Dang hoi chudn tac
P(xi, ,x„)
= V (4' A Ax^");
P(<ji, ,<j„)=i
= /\f V Vx^").
P(<^l,-,<T„) =
()
0.1 Cac thuat ngU vd khdi niem
thii
txi G = {V, P),
trong
do V la mot tap gom
hiiu
han cac phan tii, con P la mot
tap nhflng cSp khong
thii
tu cac phan tii
khac
nhau thuoc V,
tilc
P C {{u, v}
I
u,
V
eV vk u / v]. Phan
tijt
cua V
dugc
goi la
dinh
{vertex),
con phan tii {u, v} cua P dudc goi la
canh
{edge) va
duac
ky hieu bcii uv. Nhu vay uu va vu la cac ky hieu cua cung mot canh.
Ngoai
each
V2V4, V2V5,
VsVr,}),
va do thi
G2= {{a,b,c,d,e,f,g,h},{ub,ac,ad,bc,cd,ef,fg}).
® © ® ®
G2
Hinh 0.2 Cac bigu dien true
giac
ciia do thi Gi va G2
14
M6
dau
V6i iru di6m nhtr vay,
bieu
dien
true
giac cua do
thi thirdng
duoc
diing
d6
di6n
ta
nhiing
so do ve
"mute
do"
quan
he
giiJa tdng
thong
dirdng
bo
giiia
eac
thanh
pho
bang
each gan cho m6i
dinh
ten cua mot
thanh
pho va noi hai
dinh
vdi
nhau
bdi mot
doan
thing
hoae eong,
bigu
thi
tuyen
quoc lO qua hai
thanh
pho
tirong uTng. Tren
m8i
doan
ay duoe ghi
Dinh (ND), Thai
Binh
(TB),
Phil
Ly (PL),
Ninh Binh
(NB) va
Thanh
Hoa (TH).
Hinh
0.3 He
thong
quoc lo
viing
Dong-Nam
Hk Noi
0.1 Cdc
thuat
ngU va
khdi
niem
15
Tiep
theo,
dg chi su phu
thuoc
vao do thi G, tap
dinh
va tap
canh
dinh
v
lien
thuoc
(incident)
canh
c. Hai
dinh
duoc goi la ke
nhau {adjacent),
hay la
Idng
gieng
(neighbour)
cua
nhau,
neu
cluing
duoc noi v6i
nhau
bdi
mot
canh,
tiie lien
thuoc
ciing
mot
canh.
Hai
canh
gian
la
deg(v)
khi
khong
gay
nham
lln,
dudc
dinh
nghia
bcii
so tat ca cac
lang
gieng
cua v
trong
G.
Dinh
vdi bac 0 duoc goi la
dinh
cd lap
{isolated vertex).
Bay gi5,
ta noi
rang
do
thi
H = (W, F) la dd thi con
(subgraph)
(path) trong
do thi G la mot day cac
dinh
doi mot
khac
nhau
(uo,
ui, ,
ujt), trong
do
dinh
ke vdi
dinh
Ui doi
vdi
m6i / =
1, A;.
Mot
dirdng
di nhu vay con duoc ky
hieu
la
P= UQUX
Uk.TR
noi
rang trong
do
tin
G, hai
dinh
dudng
di P,
duoc ky
hieu
bdi /(P), la so cac
canh
ciia
no,
tiic
l(P) = k.
Trong
do thi Gi
trgn Hinh
0.2, cac
dinh
va
U2
duoc noi vdi
nhau
bdi
dudng
di
uxu^Ui
do dai 2, va con bdi
dudng
di
uiu^v^Ui
do dai 3.
Do thi
duoc goi la
{cxjde)
trong
do thi G la
dudng
di
(uo, ui,
•
•.,
Uk)
do
dai > 2 ma hai
dinh
dau mut
UQ
va
ciing
kg
nhau trong
G.
Noi
each
kliac,
chu
trlnh
la mot
"dudng
di
khep kin", nghia
la
dirdng
Hinh
0.2, do
thi
Gi la chu
trlnh
Hamilton,
con
trong
do thi G2 c6 tat ca 3 chu
trlnh:
1 chu
trlnh
dang "hlnh vuong"
ahcd,
2 chu
trlnh
dang "tam
giac"
ahc va acd.
Cay
{tree)
la
mot
do
thi lien thong
va
khong
c6
chu
trlnh.
tiic
la mot
do
thi
khong
CO
chu
trlnh.
Hinh
0.4
Rirng gom
3 cay -rdn
Trong
cac do thi da
duoc
xcm xet, ncu moi
canh
{u, u}
duoc
tliay
the
bang mot
cSp c6
thiJ
tu
(u,
u)
hohc/vk
{u,
u),
v)
thudng duoc bi6u
thi bdi
r-'
• -
0.1
Cac
thuat
ngU va
khdi niem
17
mot doan thing
hoac
cong
ciing vdi mui
ten
hudng
theo
chieu
tii
u
den V. Thi
du,
Hlnh
0.5 sau day cho ta
bifni
dicn true
giac
mot
do thi
do thi
CO
hudng,
mot
dinh
v c6 the la
didm
dau cua mOt so
cung
nay
va cung
cd the la
diem cuoi
cua mot vai
cung
khac.
V\, doi
vdi
dinh
V trong
do
thi
co
hudng,
ta can
phaii bict
"bac ra" va "bac vao"
cua
no. Bac ra
{outdejjree)
chu
trlnh,
lien thong,
cay, )
cung duoc chuygn
the cho do thi
CO
hudng.
Thi
di.i. diidng
di c6
htCdng
[directed
path)
trong
do
thi
G la mot day cac
dinh doi
mot
nhau
khac
nhau (uo,
ui, ,
ujt),
trong
do
dinh
Ui_,
dudc noi vdi dinh
dinh
c6 the la nhiing thanh pho va cac canh la nhflng
doan quoc 15 noi lien chiing,
hoac
cac
dinh
la nhiing tram dicn va
cac canh la nhiing day dan lien kct chiing. D6 dign ta mot each ro
rang,
ta dan nhan cho cac
dinh
va/hoac
cac canh ciia do thi, va ta
thu
dUdc do thi duCdc dan nhan [labeled graph)^ nhu
Hinh
0.3.
0.1.6
Ngon
ngi? hinh thut • E
• Bang
chiJ.
Xau cac ky tir, hdcic cac dac
tinh
noi chung, la
khoi
(block)
dong vai tro nhu mot ddn vi
kicn
thict
thudng dudc ky hieu bdi
chii
cai Hy Lap c6,
nhu
E, r va H; con cac ky tii cua bang
chii
thudng duoc
lict
ke theo
mot thu: tit xac
dinh.
Thi du, cac tap sau day la cac bang
chii:
r
= {a, b, c, d, f, g,
h,
i,
j,
k, 1,
m,
n,
o, p, q, r, s, t,
u,
v, w, x, y, z},
n
=
{0.1,«,x,y,z}.
0.1 Cac thuat ngvc va khdi niem
19
• Tii. Tie (word), hay con duoc goi la xau (string), tren mot
he dem so. Ngtidc (reverse) cua tit w, duoc ky hieu bdi u;^, la
tir
nhan dUdc b^ing each viet cac ky tu ciia w theo
thii
tu nguoc,
tufc
=
(yn(^n-\ • •<72cri. Tir V la tie con (subword) cua w, ngu
cdc ky tu cua v xuat hien lien tiep trong w. Til con
aia2-
• -
(^i, vdi
I
< i <n, dudc goi la
khuc
dau (prefix) cua w.
Cho hai tir u = ui Um va v = vi
Vn.
Phep ghep (concate-
nation) u vdi V, ta ky hieu la uu, dUdc thuc hien b^ng each viet
them
tii v vao cuoi tii tt,
tiic
uv = ui
Um'Ui
Vn- Trong trudng
A:
hop, khi tit u dude
ghep
k Ian vdi chinh no, ta viet mT'Tli = u'^.
= {O'lO'l I =
1,2, }.
20
M6
dau
De tien dung, cac ttf trong E* duoc liet ke theo thit tiX tH
diin
quen thuoc, tren co sci
thii
tu cua cac ky tu trong E va dong
thdi
theo do dM ciia t\i. Thi du, doi v6i bang chu: E = {a, b, c}, ta c6
E*
=
{e,
a, b, c, aa, ab, ac, ba, bb, be, ca, cb, cc, aaa, aab, }.
0.2 Ve ly
thuyet
do phiJc tap tinh
toan
0.2.1 Vi tri
trong
Ly
thuyet
tinh
toan
Ta hay bat dau bang viec
gidi
thieu mot
each
hop Cling nhau kham pha nhflng tiem nang va nhiJng han che chinh
cua
tinh
toan noi chung, ca
tinh
toan ly thuyet Ian
tinh
toan thuc te.
Van
de nay dira ta quay trd lai v6i nhiJng nam 30 cua the ki XX,
khi
cac nha logic toan bat dau xem xet mot
each
than trong ve
gidi
han cua
tinh
toan. Cac ket qua ly thuyet thu duoc trong khoa hoc
tinh
toan, nhu viec de xuat mot s6 mo
hinh
ciia cac qua
trinh
tinh
toan va cua thuat toan noi rieng, va dac biet la viec chi ra mot so
bai toan khong giai duqe, da cho ta biet duqc phan nao noi dung
cua van de, til pham vi ly luan den quan niem thue tien. Den nay,
du
khoa hoe va eong nghe ngay mot phat
trign
phan chia cac bai toan giai duoc thanh cac Idp
khae
nhau theo imic do kho khan khi giai clmng.
0.2 Ve ly
thuyet
do
phitc
tap
tinh
toan
21
Trong
m6i
linh
vUc nghien
ciiu,
van d^ kham pha noi tren duqc
thi
hien theo nhUng khia canh phu hop vdi chute
nSng
cua
tvfng
linh
virc. D6
hinh
dung duqc su anh hudng qua lai giiia ba
linh
vUc
trong
su phat
toan giai no dgu phai thieh hop vdi nhiing trang thiet bi
tinh
toan
hien
co.
Nhiing
trang thiet bi nay co duqc la nhd cac thanh tUu ciia
eong nghg mang lai, ma co sd ly luan cua no dua tren nhiing kgt
qua nghien
ciiu
cua ly
thuyet
otomat.
Doi
khi trong qua
trinh
giai bai toan, mac dii da rat co g^ng
nhung
ta vtn khong thg tim duqc mOt thuat toan giai no. Kho khan
nay co thg do ban
chat
phiic tap cua bai toan chuf khong phai vi ta
kem coi. Khing
dinh
dieu nay, tiic la viec ehdng to khong co thuat
toan giai bai toan, la phan su ciia ly
thuyet
ve kha
ndng
tinh
hoc dung hay sai, bai toan tuong
ilng
Pots,
bai toan
thuf
mudi cua
Hilbert
va v.v Kham pha nay khong chi la hien tuong phi thu5ng
ma no con thg hien ban chat chinh xac cua toan hoc.
Mat
khac,
ngay
ca trong trudng hap ta da xay dung
dudc
thuat
toan giai bai toan, nhung tren thuc tc doi khi d6 nhan dtrdc mot
Idi
giai thoa dang lai rat gian nan, du ta
dUdc
cung cap day du cac
trang
thiet bi tien tien nhat.
Nhil
vay, giiJa "giai
dUdc
ve mat ly
thuyet"
va "giai diTdc mot
each
thuc te" c6 mot sir
ket qua sau sac vg cac bai toan khong giai
dUdc
la sir
tri§n
khai
nhiing
tu tudng ve cac mo hinh ly thuyet cua may
tinh
va cuoi cung
dan den sir ra d6i cua may
tinh
thuc tc. Day la mot
bade
tien quan
trong
cua khoa hoc
cong
nghe.
Sau khi may
tinh
dien tut ra ddi, tucing rang vdi nhflng phudng
tien
tinh
toan hien dai nhir vay,
viec
thirc hien thuat toan d6 giai
tiep bai toan la mot
viec
lam ddn gian.
Song,
mot
each
nhanh chdng chi tren mot may
tinh
nho. Trong khi
do, doi vdi bai toan lap
lich
bieu cho mot trudng dai hoc thi van
de lai trd nen kha phflc tap.
Viec
bo tri phong hoc cho cac Idp chi
can dam bao mOt yen cau thong thudng, sao cho khong cd hai Idp
0.2 Vi ly
thuyet
do phiic tap tinh toan
23
dUdc
bo tri vao ciing mot phong hoc tai cung mot
thdi
diim.
D6 cd
dUdc
mot
thdi
gian bigu cho mOt trudng dai hoc, gom khoang 100
Idp
vdi mSt so thay co va mot luqng phong hoc nao do, cd khi ddi
hoi
mOt
thdi
khac
nd lai cho ket qua cham. Hdn
nfla,
gifla giai
dUdc
ve mat ly thuyet va giai
dUdc
mOt
each
thuc te
doi vdi nhieu bai toan cung cd nhflng
khac
biet dang kg.
Nhflng
dieu ndi
trgn
la hien tUdng kha pho bien.
Viec
kham pha
nguygn nhan dan den hien tUdng nhu vay se cd y nghia quan trong
ve mat ly thuyet va cd gia
tri
to Idn ve mat flng dung. Nguygn nhan
ay phai
chang
la do ban chat phflc tap cua bai toan, hay la do thuat
toan ma ta xay dung
chua
that hieu qua, va cung cd thg la do cac
trang
gian" vh
"do phflc tap khong gian" cua thuat toan nhu nhflng ham phu
thuoc
vao "kich
Cd"
cua bai toan. Nhd dd ta cd
dUdc
mot
each
nhin thong
nhat
ve do phflc tap cua cac thuat toan.
Ra ddi va phat
trign
manh me khoang bon mUdi nam qua, ly
thuygt
do phflc tap
tinh
toan tuy vln
chua
cd
duqc
mot ly giai thoa
dang cho nhung hien tUdng phd bign ngu
tren,
nhung nd da cd mot
budc
tign
dang kg vdi nhieu ket qua phong phu cd y nghia nhat
24
tinh
toan la nghien
ciiu
kham pha mot ludc do tao nha nham phan
loai
cac bai toan theo "do phiic tap
tinh
toan" cua thuat toan
giai
chung, mot luoc do tudng tu nhu bang tuan hoan cac nguyen to
hoa hoc duoc phan Idp theo
tinh
chat hoa hoc cua
chiing.
Qua lUdc
do ly tudng ay, ta c6 thg biet dudc bai toan nao de, bai toan nao
kho
ma khong can phai
giai
chung. Day la mot hudng nghien
ciiu
vdi
mot tam nhin bao quat.
Trong
trudng hop cu thg, khi duong dau vdi mot bai toan xem ra
la
kho
giai,
ta c6 the
xiJt
bai toan toi Uu ma khong thg
giai
dUdc mot
each
thuc te, viec
tim
mot 16i
giai
gan dung dg
dang
hdn dang kg so vdi viec tim mOt
Idi
giai
chinh xac. Cdch
xvc
ly
thi2
ha, ta c6 thg de xuat cac thuat
toan
giai
nhanh doi vdi "hau het" cac trudng hdp cua bai toan va
chi
gap kho khan trong mot so it "trudng hdp xau";
hoac
xay dung
cac thuat toan vdi "do phiic tap trung binh"
viia
phai. Cach
xiJt
ly
vUc khac nhau
va
CO
nhang dang phan biet, nhung da phan la dang bai
toan
quyet
djnh
hoac
bai
toan
tim
kiem,
trong do noi rieng la dang bai
toan
toi uu. Day la nhiing bai toan thuan tuy toan hoc va cung c6 thg
la nhiing bai toan thong dung nay sinh tii hoat dong thuc tien.
Cac bai toan do c6 thg
dupe
phat
bigu
chinh xac bang ngon
ngii
toan hoc, nhung doi khi cung dUdc phat
bigu
theo mot ngon
ngii
tu
nhien
dan da. Trong trudng hop khi bai toan chua duoc phat
bilu
dang tdng quat nhu sau:
MAX-KNAPSACK
DQ
ki$n: Cho "hai day so nguyen dudng
Si,S2, ,Sn,-5
va
Y^u
cdu: Tim mot tap con / C
{1,2,n}
sao cho
^
Si < 5 va E
'^i
—' "^ax-
26 Md dau |
Lap
dudc mo hinh thich hop nhir vay cho hhi toan la mot budc
quan trong, nhung mdi chi la phln
khdi
dau cua qua
trinh
giai
bai
toan. Trong viec hoan tat qua
trinh
giai,
khau cd ban nhat la dtra
tren
mo hinh toan hoc cua bai toan ta can de xuat mot phuong
phap
dung. Dg c6 dUdc
nhiing
kgt luan hay nhiing ket qua nghien
ciiu
mang
tinh
khai quat,
cdc bai toan can dUdc xem xet trong mot khuon kh6 chung. Cac
nghign
ciiu
nhu vay giup ta c6 mot
each
nhin thong nhat doi v6i
van
d§"
phiic
tap cua cac bai toan, dong
thdi
cho ta nhiing hieu biet
khai
quat va nhiing hudng dan can thiet trong cac
tinh
huong cu
thg,
va vi the no khong chi c6 y nghia ly luan ma eon rat
thiit
thuc
cho
ling
dung. Viec nghien
ciiu
lign
quan den van de phiic tap cua bai toan quyet dinh, ta c6 thg di den
nhiing
ket luan thich hop doi vdi bai toan da cho.
De cac bai toan thuoe nhieu
linh
vuc
khae
nhau c6 the
duoe
xem
xet trong mot khuon kh6 chung va
dupe
giai
quyet trgn
ciing
mSt mo hinh
tinh
toan, sau day ta hay
tiing
bude
cu the hoa cac
digm
CO
ban trong
each
tiep can bai toan.
0.3 Cdch
tiep
can trd Idi don gian la "dung"
hoac
"sai". Bai toan vdi cau hoi
nhu
vay
dupe
gpi la bai
toan
guy it dinh {decision problem).
Loai
thii
hai la ygu cau Tim
kiem
nghiem doi vdi dii kien bat ky cho
triidc.
Bai toan vdi ygu cau nhu vay c6 tgn gpi la bdi
toan
tim
kiim
{search problem). Trong Idp cac bai toan tim
kiem,
cac bdi
todn
toi Uu (optimization problems) eo mot vi tri quan trpng. Bdi
toan
cite
dai hoa (maximization problem) va bdi
todn
cue
tiiu
Hamilton
trong
moi do thi cho trude"
dupe
tuong
ling
vdi bai toan quyet dinh
sau day:
HAMILTONIAN
CYCLE
Da kien: Cho mot do thi G.
Cau
hoi: Phai chang trong G c6 chu
trinh
Hamilton?
Tuy
nhien, cac bai toan toi liu
dupe
tuong
ling
vdi cac bai toan
quyet dinh thich hpp hon. Bai toan quyet dinh tUOng
ling
vdi bai
28
M6 dau
to4n
circ
dai hoa (bai toan
cttc
c6 mot
nghiem
chap
nhan
duac
vdi gia tri
khong
nho han B
{khong
Idn han B, tudng ijfng)?
Thi
du, bai toan cue dai hoa MAX-KNAPSACK
duoc
tuong
ling
vdi
bai toan quyet dinh sau day:
KNAPSACK
•
••
• •
• • • • '•'
DO
kien:
Cho hai day s6 nguyen duang
iwii
n ;> ^' •^li ^2, S„, S
va
Cau hoi:
Phai
mot ngon ngu hinh thiic nao do,
bang
each
ma hoa (tufc mieu ta)
tiing
du: kien bai toan bdi mot tit tren
bang
chii thich hop va xac
dinh
ngon ngu: tuong
ling
vdi bai toan ay.
Viec
ma hoa nay eo thi
duoc
thuc hien
theo
mot quy
trinh
ehung vdi mot vai rang
buoc
can thiet. Sau day la mot quy
trinh
ma hoa thong dung mang
tinh
nguygn t^c. . , ,
0.3
Cdch
tiep
can cdc bai
man cac ticu chuin sau day:
(ci)
Tiit
ma (xau bigu dien) cua moi dfl kien bai toan phai ngan
gon va khong dUdc "don them" nhUng thong tin khong
can thiet.
(C2)
Cac so tham gia trong dfl kien bai toan can
duoc
bigu dign
dudi
dang nhi phan
hoac
theo
mot co s6 nao do Idn hon 1
(bdi VI
dang bigu dign
theo
co s6 1 dai hon c3 ham mfl so vdi
bat ky dang bigu dien n^o
theo
cO so A; vdi > 2).
• Sd do ma hoa
chu§n.
Doi vdi
tflng
bai toan cu the ta dg dang
xay dung
duoc
mot phep ma hoa thich hop. Tuy nhign,
xau
lign
ket bieu thi "tgn" cua doi tugng mang so hieu k.
(ea) Neu </i, ^2,
•
•, ym la cac xau
lign
kgt bigu thi cac doi tugng
Yi,Y2, ,
y„„ thi
(yi,
^2,
•
•, 'Jm) la mot xau lien kgt bigu
thi
day {Y,,Y2, ,YJ.
30
Ma dau
Dxta
theo
so do ma hoa nay, ta c6 the bieu dien cac du; kien bai
toan bdi cac xau lien ket tren mot
bang
chii: nao do chiia cac ky
tu
thuoc
bang
chii ke tren. Di nhien, day la mot sd do nen no
chi mang tinh nguyen tac. D6 dap utng yeu cau ve tmh sue tich cua
ngon ngfl, trong ttog trudng hop cu thg ta c6 thg b6 sung nhung
la xau lien kgt bigu dign phan tii X, tUdng
iJng
ciia day, \ i < n.
Mot ham f : X Y dUdc bieu dien b6i mot xau lign ket
((:ci,yi)(x2,y2)
• • •
(x„, :(/„)), trong do Xi la xau lien ket bigu dien
phan tijf Xj G X va yt la xau lign ket bigu dien phan tur /(X^) e Y,
l<i< n.
Mot so hHu ti q = rn/n, trong do rn va n la cac so tu nhign
nguygn to ciing nhau, dUdc bigu dign bdi xau lien ket (m, /i), trong
do rii va h la bigu dign nhi phan cua cac so rn va n tiTdng
ling.
Mot do thi CO
hxldng
G = {V, A) dildc bieu dien bdi mot xau
lign
ket (x,y), ta ky hieu la (G) ^ (x,y), trong do x la xau lien
ket bigu dien tap dinh V va y la xau lign ket bieu dien tap cung
A
cua do thi (m5i phan
tilt
ciia A la mot cap cac dinh
thuoc
V).
Cu thg, vdi V =
{vuV2, ,
Vn} va A =
{ui,
a2, •,
do xau
trudc
ky tu t)
bigu
dign
tap dinh va xau sau JJ
bigu
dign
cac
cung
cua
do thi. Thi du, do thi hinh
ngoi
sao nam
canh
Gj vdi tap dinh
{vi,V2,
V3, V4, Us} (Hinh 0.2)
dudc
bigu
dign
bdi xau lien ket
(Gi) =
i,2,3,4,5«(i,3)(i,4)(2,4)(2,5)(3,5).
•
Ngon
ngiJ
dac
trtfng
cua bai
trong trudng hdp
ngUdc
lai.
Quid)
= SAL
Gia
sijr e la mot
phep
ma hoa
thich
hdp n^G do doi vdi bai
toan
n, ma
theo
d6 moi dU kien bai
toan
dUdc
bigu
dien
bdi mot
xau lien kgt
tren
bang
chfl E. Nhu vay, e anh xa cac dU kien bai
toan
thanh
cac xau
thuoc
£*. Dg ddn
gian,
ngU dac
trxing
cua IT, hay
ngon
ngvC
tuCdng
"^ng vdi bai
toan
U, va dUdc ky hieu
ngan
gon bdi chfl
nghigng
77.
Ta CO
32
Md dau
0.3.3
Doan
nhan
ngon
ngu*
Cho n la mot bai toan quyet dinh, L{Du) 1^ ngon ngfl tren bang
chO: E bieu dign tap dii kien cua n, va /7 la ngon ngu: tircng urng vdi
bM toan IT. Gia sijt ton tai mot mo hinh
tinh
toan hinh thiic, m^
khi
xiJt ly tren m6i xau thuoc L{Dn), hay thuoc E* noi chung, no
CO
thg phan biet dirac xau nao thuoc 17 va xau nao khong; nghia
duoc
sii dung nhu mot
cong
cu
kha thuan tien trong
viec
khao sat cac qua
trinh
tinh
toan noi
chung, va dac biet trong vi^c phan tich do phiic tap cua thuat toan.
Bai tap
0.1 Hay dien ta mot
each
phi hinh thilc bang tieng Viet tiing tap
hop sau day:
a.
{1,3,5,7, }.
b.
{ ,-4,-2,0,2,4, }.
c.
{n
I
n = 2m doi vdi m6i m thuoc N}.
d. {n| n = 2rn doi v6i mot m nho 66 thuoc N, ; .
va n = 3k doi vdi mot k nho do thuQc N}.
Bai
tap
33
0.2 Hay di6n ta mot
nhigu
phan tut?
0.5 Neu C CO c phan tut, thi ho tat ca cac tap con cua C, tiic
V{C),
CO,
bao nhieu phan tut?
0.6 Hay cho bigt, trong so nhiing dieu sau day, digu nao dung vk
dieu nao
sai?
n
a. 3n = 0
b. n^ = 0[n].
c.
n^ = 0[nlog^n.
d. n log
71
= 0[n^
e. 3" =
2°t"l.
f. 22" = Of22"l.
Copyright: Tài liệu đại học ©