Đại số gia tử và bài toán sắp xếp mở tài liệu Tiếng Việt

oˆng phu. thuoˆ.c va`o doˆ´i soˆ´ va` ky´ hieˆ.u la` fm(h) go. i la` doˆ. do t´ınh mo`
. cu’a gia tu.’ h.
Meˆ.nh de`ˆ 1.1. Cho fm la` ha`m doˆ. do t´ınh mo`
. treˆn X. Ta co´:
i) fm(c−) + fm(c+) = 1.
DA. I SO´ˆ GIA TU
.’ VA` BA`I TOA´N SA´˘P XE´ˆP MO`
.
TA`I LIEˆ. U TIE´ˆNG VIEˆ. T 91
ii)
p+q∑
i=1
fm(hic) = fm(c), c ∈ {c
+, c−}.
iii)
p+q∑
i=1
fm(hix) = fm(x).
iv) Neˆ´u x = him...hi2hi1 th`ı fm(x) = fm(him...hi2hi1c) = fm(him)...fm(hi1)fm(c).
v)
p∑
i=1
fm(hi) = α,
p+q∑
i=p+1
fm(hi) = β sao cho α + β = 1, α, β > 0.
Di.nh ngh˜ıa 3. Ha`m daˆ´u sign : X → {−1, 0, 1} du
.o.. c di.nh ngh˜ıa deˆ. quy nhu
. sau:
i) sign(c−) = −1 va` neˆ´u hc− c− th`ı
sign(hc−) = −sign(c−).
sign(c+) = +1 va` neˆ´u hc+ > c+ th`ı sign(hc+) = sign(c+), neˆ´u hc+ < c+ th`ı sign(hc+) =
−sign(c+).
ii) sign(h′hx) = −sign(hx) neˆ´u h′ aˆm doˆ´i vo´.i h va` h′hx 6= hx.
iii) sign(h′hx) = sign(hx) neˆ´u h′ du.o.ng doˆ´i vo´.i h va` h′hx 6= hx.
iv) sign(h′hx) = 0 neˆ´u h′hx = hx.
Meˆ.nh de`ˆ 1.2. Vo´
.i mo. i gia tu
.’ h va` pha`ˆn tu.’ x ∈ X neˆ´u sign(hx) = +1 th`ı hx > x va` neˆ´u
sign(hx) = −1 th`ı hx < x.
Di.nh ngh˜ıa 3. f : X → [0, 1] go. i la` ha`m di.nh lu
.o.. ng ngu˜
. ngh˜ıa cu’a X neˆ´u:
i) f ba’o toa`n thu´. tu.. treˆn X .
ii) Vo´.i mo.i h, k thuoˆ.c H
+ hoa˘.c h, k thuoˆ. c H
− va` x, y thuoˆ.c X :
f(hx)− f(x)
f(kx)− f(x)
=
f(hy)− f(y)
f(ky)− f(y)
.
Cho fm la` ha`m doˆ. do t´ınh mo`
. treˆn X . Ha`m di.nh lu
.o.. ng ngu˜
. ngh˜ıa v : X → [0, 1] du.o.. c
xaˆy du.. ng nhu
. sau (x = him...hi2hi1):
i) v(c−) = w − αfm(c−), v(c+) = w + αfm(c+).
ii) v(hjx) = v(x)+sign(hjx)
[
p∑
i=j
fm(hix)−
1
2
(1− sign(hjx)sign(hihjx)(β − α)fm(hjx)
]
neˆ´u j ≤ p
va` v(hjx) = v(x)+sign(hjx)
[
j∑
i=p+1
fm(hix)−
1
2
(1− sign(hjx)sign(hihjx)(β − α)fm(hjx)
]
neˆ´u j > p.
Meˆ.nh de`ˆ 3.1. Cho fm la` ha`m doˆ. do t´ınh mo`
. treˆn X, v la` ha`m di.nh lu
.o.. ng ngu˜
. ngh˜ıa da˜ xaˆy
du.. ng tru
.´o.c daˆy. Khi do´ ta co´:
i) 0 ≤ v(x) ≤ 1, ∀x ∈ X.
ii) Neˆ´u x < y th`ı v(x) < v(y) vo´.i mo. i x, y thuoˆ. c X.
Tu`. keˆ´t qua’ treˆn ta thaˆ´y ha`m di.nh lu
.o.. ng ngu˜
. ngh˜ıa la` ha`m do.n dieˆ.u ta˘ng trong doa.n [0,1]
, do do´ toˆ`n ta. i ha`m ngu
.o.. c v
−1 : [0, 1]→ X. Keˆ´t qua’ na`y se˜ du`ng ve`ˆ sau.
2.2. Gia’i ba`i toa´n sa˘´p xeˆ´p mo`. theo ca´ch tieˆ´p caˆ.n DSGT
Xin nha˘´c la. i, ba`i toa´n sa˘´p xeˆ´p (hay da´nh gia´) co´ theˆ’ neˆu moˆ. t ca´ch toˆ’ng qua´t nhu
. sau:
ca˘n cu´. va`o dieˆ’m n chuyeˆn gia J1, J2, .., Jn da´nh gia´ m doˆ´i tu.o.. ng O1, O2, .., Om theo k tieˆu
92 TRA`ˆN THA´I SO.N, LEˆ QUO´ˆC THA´I, NGUYE˜ˆN VA˘N NAM
ch´ı C1, C2, .., Ck, ha˜y sa˘´p xeˆ´p m doˆ´i tu.o.. ng do´ theo thu´
. tu.. ta˘ng (hoa˘. c gia’m) da`ˆn cu’a tieˆu
ch´ı toˆ’ng ho..p. Gia’ su
.’ dieˆ’m chuyeˆn gia Jh cho doˆ´i tu.o.. ng Oi theo tieˆu ch´ı Ct la` Dhit. Dhit o
.’
daˆy co´ theˆ’ la` soˆ´ (nhu. 5, 7, 9...), co´ theˆ’ mo`. (nhu. “khoa’ng 8 dieˆ’m” hay “kha´”, “raˆ´t toˆ´t”...).
Trong tru.`o.ng ho..p mo. i Dhit de`ˆu la` soˆ´ thu
.
. c va` ca´c tro.ng soˆ´ (neˆ´u co´) cu˜ng la` soˆ´ thu
.
. c th`ı ngu
.`o.i
ta su.’ du. ng moˆ.t phe´p keˆ´t nhaˆ.p na`o do´ nhu
. du`ng ha`m trung b`ınh coˆ.ng co´ tro. ng soˆ´ (thu
.`o.ng
ga˘.p ho
.n ca’) hay laˆ´y MAX, MIN (trong tru.`o.ng ho.. p da´nh gia´ du
.
. a treˆn gia´ tri. cu
.
. c da. i hay cu
.
. c
tieˆ’u)... O
.’ daˆy su.. phu´
.c ta.p cu’a ba`i toa´n na`˘m o
.’ choˆ˜ du.a ra ca´ch da´nh gia´ phu` ho.. p, tu´
.c lu.. a
cho.n ha`m keˆ´t nhaˆ.p. Vı´ du. do
.n gia’n nhu. ba`i toa´n da´nh gia´ ho. c sinh, tu`
. tru.´o.c deˆ´n nay ngu.`o.i
ta ca˘n cu´. va`o dieˆ’m soˆ´ (co´ ca’ dieˆ’m da.o du´
.c) deˆ’ laˆ´y trung b`ınh coˆ.ng (co´ theˆ’ co´ moˆn co´ heˆ.
soˆ´ 2) roˆ`i xeˆ´p ha.ng. Vieˆ.c na`y do
.n gia’n ve`ˆ ma˘. t thao ta´c nhu
.ng ch´ınh xa´c hay khoˆng th`ı co`n
nhie`ˆu tranh ca˜i. Tuy nhieˆn trong tru.`o.ng ho.. p Dhit co´ theˆ’ nhaˆ.n gia´ tri. khoˆng ch´ınh xa´c (mo`
.),
th´ı du. nhu
. “xaˆ´p xı’ 7”, “khoˆng du.´o.i 8” hay “toˆ´t”, “raˆ´t ke´m” th`ı vieˆ.c xu
.’ ly´ da˜ tro.’ neˆn phu´.c
ta.p ho
.n nhie`ˆu. Theo L. Zadeh, moˆ˜i taˆ.p mo`
. co´ theˆ’ u´.ng vo´.i moˆ.t ha`m soˆ´ thu
.
. c tu`
. taˆ.p mie`ˆn tri.
va`o doa.n [0,1] , tu`
. do´ vieˆ.c t´ınh toa´n treˆn dieˆ’m du
.o.. c chuyeˆ’n sang t´ınh toa´n treˆn tu`
.ng gia´ tri.
cu’a ha`m thu.. c du
.o.. c go. i la` ha`m thuoˆ.c (membership function) na`y. Ca´ch na`y co´ nhu˜
.ng nhu.o.. c
dieˆ’m lo´.n la` ca´ch cho.n ha`m thuoˆ.c raˆ´t kho´, khoˆng co´ quy ta˘´c na`o; vieˆ.c t´ınh toa´n treˆn ca´c ha`m
thuoˆ.c thu
.`o.ng phu´.c ta.p; vieˆ.c gia’ i mo`
. tu`. ca´c keˆ´t qua’ t´ınh toa´n du.o.. c la` die`ˆu ga`ˆn nhu
. khoˆng
theˆ’ cho neˆn vo´.i ca´c da´nh gia´ ba`˘ng tu`. ngu˜. tu.. nhieˆn, keˆ´t qua’ se˜ raˆ´t khoˆng phu` ho
.
. p.
Trong [5] chu´ng toˆi da˜ tr`ınh ba`y gia’ i pha´p cho ba`i toa´n sa˘´p xeˆ´p mo`. du.. a treˆn DSGT. Gia’ i
pha´p na`y da˜ kha˘´c phu.c du
.o.. c nhu˜
.ng nhu.o.. c dieˆ’m keˆ’ treˆn, tuy nhieˆn pha’ i du
.a treˆn moˆ.t gia’
thieˆ´t khoˆng du.o.. c hoa`n toa`n tu
.
. nhieˆn la` ca´c gia tu
.’ ta´c doˆ.ng leˆn ca´c pha`ˆn tu
.’ sinh pha’ i cho ra
taˆ.p phaˆn boˆ´ de`ˆu treˆn tru. c bieˆ’u die˜ˆn gia´ tri. (hoa˘. c neˆ´u khoˆng ta pha’ i boˆ’ xung theˆm ca´c gia´ tri.
nhaˆn ta.o deˆ’ co´ phaˆn boˆ´ de`ˆu). Vo´
.i ca´c keˆ´t qua’ nghieˆn cu´.u mo´.i ga`ˆn daˆy ve`ˆ DSGT, cu. theˆ’ la`
ca´c ha`m di.nh lu
.o.. ng ngu˜
. ngh˜ıa, ta da˜ co´ theˆ’ t´ınh du.o.. c ca´c gia´ tri. cu’a moˆ. t tu`
. baˆ´t ky` trong
taˆ.p gia´ tri. cu’a bieˆ´n ngoˆn ngu˜
. ma` khoˆng ca`ˆn du.. a va`o gia’ thieˆ´t phaˆn boˆ´ de`ˆu nhu
. treˆn (vo´.i lu.. a
cho.n α, β khoˆng ba`˘ng nhau, su
.
. phaˆn boˆ´ de`ˆu se˜ khoˆng co´). Ngoa`i ra, cu˜ng du
.
. a treˆn ha`m di.nh
lu.o.. ng ngu˜
. ngh˜ıa, co´ theˆ’ chuyeˆ’n ca’ ca´c gia´ tri. da´nh gia´ ba`˘ng soˆ´ thu
.
. c ve`ˆ mo`
. deˆ’ ta.o neˆn su
.
.
thoˆ´ng nhaˆ´t trong nhu˜.ng t´ınh toa´n tieˆ´p theo. Vieˆ.c mo`
. hoa´ na`y hoa`n toa`n co´ theˆ’ ly´ gia’ i du.o.. c
do vieˆ.c cho dieˆ’m la` do ca´c chuyeˆn gia (tu´
.c la` con ngu.`o.i) xa´c di.nh du
.
. a treˆn kinh nghieˆ.m va`
da´nh gia´ chu’ quan cu’a moˆ˜i ngu.`o.i, kho´ co´ theˆ’ ch´ınh xa´c tuyeˆ.t doˆ´i du
.o.. c. Vieˆ.c mo`
. hoa´ do vaˆ.y
khoˆng chı’ la` yeˆu ca`ˆu chuyeˆn moˆn ma` co`n la` do`i ho’ i kha´ch quan. To´m la. i, co´ theˆ’ tieˆ´n ha`nh
gia’ ba`i toa´n sa˘´p xeˆ´p mo`. nhu. sau:
Neˆ´u Dhit nhaˆ.n gia´ tri. soˆ´, tru
.´o.c heˆ´t ta se˜ tieˆ´n ha`nh quy chuaˆ’n khoa’ng xa´c di.nh cu’a mie`ˆn
gia´ tri. cu’a Dhit, th´ı du. ve`ˆ doa.n [1,10] (theo ca´ch cho dieˆ’m phoˆ’ bieˆ´n hieˆ.n nay). Vo´
.i gia´ tri.
mo´.i cu’a Dhit treˆn [1,10], tra theo ba’ng ta du.o.. c gia´ tri. ngoˆn ngu˜
. tu.o.ng u´.ng. Laˆ´y gia´ tri. di.nh
lu.o.. ng ngu˜
. ngh˜ıa cu’a gia´ tri. ngoˆn ngu˜
. na`y thay cho Dhit la`m gia´ tri. t´ınh toa´n.
Neˆ´u Dhit nhaˆ.n gia´ tri. ngoˆn ngu˜
., ta laˆ´y gia´ tri. di.nh lu
.o.. ng ngu˜
. ngh˜ıa cu’a Dhit la`m gia´ tri.
t´ınh toa´n.
Tu.o.ng tu.. vo´
.i ca´c tro.ng soˆ´ neˆ´u co´.
Ba`i toa´n baˆy gio`. tro.’ la. i la` ba`i toa´n sa˘´p xeˆ´p vo´
.i ca´c soˆ´ thu.. c va` ta co´ theˆ’ su
.’ du. ng mo. i keˆ´t
qua’ nghieˆn cu´.u da˜ bieˆ´t ve`ˆ vieˆ.c na`y deˆ’ gia’ i quyeˆ´t.
DA. I SO´ˆ GIA TU
.’ VA` BA`I TOA´N SA´˘P XE´ˆP MO`
.
TA`I LIEˆ. U TIE´ˆNG VIEˆ. T 93
3. GIA’ I PHA´P CHO BA`I TOA´N SA´˘P XEˆ´P MO`
.
TA`I LIEˆ. U
Gia’ i pha´p cu’a chu´ng toˆi neˆu ra o.’ daˆy cho ba`i toa´n sa˘´p xeˆ´p mo`. ta`i lieˆ.u tieˆ´ng Vieˆ.t goˆ`m hai
pha`ˆn ch´ınh.
3.1. Xu.’ ly´ caˆu ho’i cu’a ngu.`o.i su.’ du.ng
Nhu. da˜ neˆu o.’ treˆn, tieˆ´ng Vieˆ.t va` tieˆ´ng Anh co´ su
.
. kha´c bieˆ. t ve`ˆ caˆ´u ta.o aˆm tieˆ´t. Cho neˆn,
deˆ’ xu.’ ly´ du´ng yeˆu ca`ˆu cu’a ngu.`o.i su.’ du. ng, bu
.´o.c ta´ch tu`. la` moˆ. t bu
.´o.c ca`ˆn thieˆ´t trong gia’ i
pha´p. Bu.´o.c ta´ch tu`. na`y nha`˘m ca´c mu. c d´ıch: ta´ch du
.o.. c taˆ.p ca´c tu`
. khoa´, bo’ ca´c tu`. khoˆng
ca`ˆn thieˆ´t va` ta.o ca’ taˆ.p tu`
. tu.o.ng du.o.ng (doˆ`ng ngh˜ıa). Vı` ba`i ba´o taˆ.p trung va`o vaˆ´n de`ˆ sa˘´p
xeˆ´p neˆn pha`ˆn na`y chu´ng toˆi chı’ su.’ du. ng nhu˜
.ng gia’ i pha´p da˜ bieˆ´t cu’a ca´c nha` nghieˆn cu´.u
trong vieˆ.c ta´ch caˆu tieˆ´ng Vieˆ.t. Ca´ch do
.n gia’n nhaˆ´t la` duyeˆ.t caˆu tu`
. tra´i qua pha’ i roˆ`i cho.n tu`
.
co´ nhie`ˆu aˆm tieˆ´t nhaˆ´t co´ ngh˜ıa (tra tu`. dieˆ’n) la`m tu`. ca`ˆn t`ım va` la˘.p la. i qua´ tr`ınh do´ cho deˆ´n
heˆ´t caˆu. Theo ca´ch na`y, nhu˜.ng caˆu kieˆ’u “ho.c sinh ho.c sinh ho.c” se˜ khoˆng ta´ch du
.o.. c du´ng,
nhu.ng deˆ’ taˆ.p trung va`o vieˆ.c sa˘´p xeˆ´p neˆn vaˆ´n de`ˆ ta´ch tu`
. trong caˆu tieˆ´ng Vieˆ.t chu´ng toˆi se˜
quay la. i trong ba`i ba´o kha´c. Sau khi ta´ch du
.o.. c ca´c tu`
., ta ca`ˆn tieˆ´n ha`nh loa. i bo’ tu
.
. doˆ.ng ca´c
hu. tu`., tu´.c la` ca´c tu`. mang t´ınh ga˘´n keˆ´t, th´ı du. “la`”, “va`”... v`ı ca´c tu`
. na`y khoˆng co´ y´ ngh˜ıa
trong vieˆ.c t`ım kieˆ´m. Vieˆ.c na`y du
.o.. c tieˆ´n ha`nh ba`˘ng ca´ch tra tu`
. dieˆ’n. Cuoˆ´i cu`ng, vo´.i taˆ.p ca´c
tu`. t`ım du.o.. c, ta cu˜ng lu
.u luoˆn ca’ ca´c tu`. doˆ`ng ngh˜ıa vo´.i chu´ng, cu˜ng ba`˘ng ca´ch tra tu`. dieˆ’n
ca´c tu`. doˆ`ng ngh˜ıa.
3.2. Sa˘´p xeˆ´p ta`i lieˆ.u theo thu´
. tu.. u
.u tieˆn
Sau khi t`ım ra du.o.. c taˆ´t ca’ ca´c va˘n ba’n tu`
. kho du˜. lieˆ.u co´ chu´
.a taˆ.p ca´c tu`
. khoa´ co´ trong
yeˆu ca`ˆu cu’a ngu.`o.i su.’ du.ng, bu
.´o.c tieˆ´p theo la` sa˘´p xeˆ´p ca´c ta`i lieˆ.u na`y theo thu´
. tu.. mu´
.c doˆ.
thoa’ ma˜n yeˆu ca`ˆu ngu.`o.i su.’ du.ng gia’m da`ˆn. Deˆ’ la`m die`ˆu do´, vo´
.i moˆ˜i tieˆu ch´ı da˜ neˆu o.’ pha`ˆn
treˆn, thu.. c hieˆ.n da´nh gia´ cu. theˆ’ nhu
. sau: (trong tru.`o.ng ho.. p na`y, soˆ´ lu
.o.. ng chuyeˆn gia se˜ la`
1).
- Neˆ´u taˆ´t ca’ ca´c tu`. khoa´ trong yeˆu ca`ˆu t`ım kieˆ´m de`ˆu co´ ma˘. t trong tieˆu de`ˆ ta`i lieˆ.u, mu´
.c
doˆ. phu` ho
.
. p se˜ la` cao nhaˆ´t (ma˘. c di.nh la` “raˆ´t toˆ´t”, hoa˘. c theo tuy` cho.n cu’a ngu
.`o.i su.’ du. ng).
Neˆ´u thieˆ´u moˆ.t tu`
. khoa´ se˜ “toˆ´t”... gia’m da`ˆn deˆ´n “khoˆng toˆ´t” khi khoˆng co´ tu`. khoa´ na`o na`˘m
trong tieˆu de`ˆ.
- Khoa’ng ca´ch giu˜.a ca´c tu`. khoa´ du.o.. c do ba`˘ng soˆ´ aˆm tieˆ´t na`˘m giu˜
.a chu´ng (ba`˘ng soˆ´ khoa’ng
troˆ´ng t´ınh du.o.. c). De˜ˆ da`ng thaˆ´y di.nh ngh˜ıa na`y thoa’ ca´c tieˆn de`ˆ ve`ˆ khoa’ng ca´ch. Khoa’ng
ca´ch no´i chung ba`˘ng toˆ’ng ca´c khoa’ng ca´ch no´i treˆn... Khoa’ng ca´ch nho’ nhaˆ´t co´ du.. oc se˜ u´
.ng
vo´.i da´nh gia´ “raˆ´t toˆ´t” (hoa˘. c theo tuy` cho.n cu’a ngu
.`o.i su.’ du. ng, chı’ ca`ˆn ba’o toa`n quan heˆ. thu´
.
tu.. ), khoa’ng ca´ch lo´
.n nhaˆ´t u´.ng vo´.i “khoˆng toˆ´t”.
- Soˆ´ la`ˆn xuaˆ´t hieˆ.n lo´
.n nhaˆ´t cu’a ca´c tu`. khoa´ trong va˘n ba’n u´.ng vo´.i da´nh gia´ “raˆ´t toˆ´t”, ı´t
nhaˆ´t u´.ng vo´.i “khoˆng toˆ´t”.
- Ca´c trang WEB co´ theˆ’ du.o.. c sa˘´p xeˆ´p theo soˆ´ lu
.o.. ng ngu
.`o.i truy nhaˆ.p (co´ coˆng cu. treˆn
WEB chuyeˆn la`m vieˆ.c na`y). Vı` vaˆ.y vieˆ.c da´nh gia´ ta`i lieˆ.u t`ım du
.o.. c theo uy t´ın cu’a trang
WEB la` hoa`n toa`n la`m du.o.. c va` cu˜ng sa˘´p xeˆ´p tu`
. trang uy t´ın nhaˆ´t la` “raˆ´t toˆ´t” deˆ´n trang thu´.
10 cha˘’ ng ha.n la` “khoˆng toˆ´t” (nhu˜
.ng trang sau de`ˆu la` “raˆ´t khoˆng toˆ´t”).
94 TRA`ˆN THA´I SO.N, LEˆ QUO´ˆC THA´I, NGUYE˜ˆN VA˘N NAM
- Neˆ´u co´ ca´c tu`. nhaˆ´n (gia tu.’ ) di cu`ng ca´c tu`. khoa´, vieˆ.c da´nh gia´ tuaˆn theo ly´ thuyeˆ´t ve`ˆ
DSGT: neˆ´u va˘n ba’n co´ tu`. khoa´ x du.o.. c da´nh gia´ la` “y” th`ı va˘n ba’n co´ cu.m tu`
. αx se˜ du.o.. c
da´nh gia´ la` αy. Cha˘’ ng ha.n neˆ´u va˘n ba’n co´ tu`
. khoa´ “nha` to” du.o.. c da´nh gia´ la` “toˆ´t” th`ı va˘n
ba’n co´ chu´.a cu.m tu`
. “nha` tu.o.ng doˆ´i to” se˜ du.o.. c da´nh gia´ la` “tu
.o.ng doˆ´i toˆ´t”.
Sau khi co´ ca´c da´nh gia´, co´ theˆ’ t´ınh ca´c gia´ tri. di.nh lu
.o.. ng ngu˜
. ngh˜ıa cu’a ca´c gia´ tri. cu’a
ca´c pha`ˆn tu.’ cu’a DSGT co´ ca´c pha`ˆn tu.’ sinh la` “toˆ´t” va` “khoˆng toˆ´t”. Co´ theˆ’ xem [3] deˆ’ thaˆ´y
moˆ. t ba’ng t´ınh cu. theˆ’ (trong do´ neˆu ca´ch t´ınh cho DSGT vo´
.i ca´c pha`ˆn tu.’ sinh la` “small” va`
“large” nhu.ng vo´.i hai pha`ˆn tu.’ sinh cu’a ta la` “toˆ´t” va` “khoˆng toˆ´t”, ca´ch t´ınh hoa`n toa`n khoˆng
kha´c bieˆ.t). Tu`
. keˆ´t qua’ co´ du.o.. c, co´ theˆ’ toˆ´ng ho
.
. p la. i deˆ’ co´ keˆ´t qua’ cuoˆ´i cu`ng theo nhu˜
.ng gia’ i
pha´p thoˆng thu.`o.ng, cha˘’ ng ha.n laˆ´y trung b`ınh coˆ.ng co´ tro.ng soˆ´ hay trung b`ınh b`ınh phu
.o.ng
(co´ tro.ng soˆ´)...
4. CHU
.
O
.
NG TRI`NH TI`M KIEˆ´M VA` SA´˘P XEˆ´P THU
.
. C NGHIEˆM
Chu´ng toˆi da˜ tieˆ´n ha`nh vieˆ´t chu.o.ng tr`ınh thu.’ nghieˆ.m phu
.o.ng pha´p neˆu treˆn, du.. a treˆn
pha`ˆn me`ˆm ma˜ nguoˆ`n mo.’ nutch (co´ ta. i trang WEB  Vieˆ.c
da´nh gia´ ca´c trang ta`i lieˆ.u t`ım du
.o.. c ca˘n cu´
. va`o ca´c tieˆu ch´ı neˆu treˆn va` co´ du`ng tro.ng soˆ´.
Vieˆ.c keˆ´t nhaˆ.p ca´c da´nh gia´ rieˆng le’ la` du`ng trung b`ınh coˆ.ng (co´ tro.ng soˆ´). Keˆ´t qua’ cho thaˆ´y
bu.´o.c da`ˆu hieˆ.u qua’ cu’a phu
.o.ng pha´p du.a ra: soˆ´ ta`i lieˆ.u du
.o.. c du
.a ra la` ı´t ho.n ha˘’ n (do loa. i
ca´c ta`i lieˆ.u khoˆng lieˆn quan v`ı khaˆu xu
.’ ly´ ta´ch tu`.) va` du.o.. c sa˘´p xeˆ´p tu
.o.ng doˆ´i toˆ´t.
4.1. Xu.’ ly´ ta´ch tu`. kho´a tu`. caˆu truy vaˆ´n cu’a ngu.`o.i su.’ du.ng
Ta thaˆ´y keˆ´t qua’ sau khi xu.’ ly´ (ta´ch tu`.) la` soˆ´ lu.o.. ng ta`i lieˆ.u t`ım thaˆ´y ı´t ho
.n ha˘’ n do khoˆng
du.a ra ca´c ta`i lieˆ.u khoˆng theo du´ng yeˆu ca`ˆu (nhu
. ca´c ta`i lieˆ.u chı’ chu´
.a tu`. “sinh” trong th´ı du.
da`ˆu, tu`. “xa˜” trong th´ı du. thu´
. hai...).
4. 2. Sa˘´p xeˆ´p ta`i lieˆ.u du
.
. a treˆn da´nh gia´ mo`
.
Ca´c th´ı du. sau cho thaˆ´y hieˆ.u qua’ bu
.´o.c da`ˆu cu’a vieˆ.c u´
.ng du. ng ba`i toa´n sa˘´p xeˆ´p mo`
..
Vı´ du. 1. Tu`
. khoa´ “kinh teˆ´ doˆ thi.”, keˆ´t qua’ t`ım kieˆ´m cho ra 286 ta`i lieˆ.u. Tu`
. vi. tr´ı thu´
. tu.
ca´c ta`i lieˆ.u co´ thay doˆ’i so tru
.´o.c khi sa˘´p xeˆ´p va` sau khi sa˘´p xeˆ´p (ch´ınh xa´c ho.n la` chı’ sa˘´p xeˆ´p
theo pha`ˆn me`ˆm ma˜ nguoˆ´n mo.’ da˜ co´ va` theˆm va`o su.. sa˘´p xeˆ´p theo thuaˆ´t toa´n cu’a chu´ng toˆi
du.a ra). Tuy nhieˆn ca´c ta`i lieˆ.u thay theˆ´ nhau o
.’ vi. tr´ı na`y cu˜ng khoˆng thaˆ. t kha´c bieˆ.t ve`ˆ ma˘. t
da´p u´.ng caˆu ho’ i ngu.`o.i su.’ du. ng.
Vı´ du. 2. Tu`
. khoa´ “kinh teˆ´ ha`ng hoa´”, keˆ´t qua’ t`ım kieˆ´m cho ra 648 ta`i lieˆ.u. Kha´c bieˆ.t giu˜
.a
DA. I SO´ˆ GIA TU
.’ VA` BA`I TOA´N SA´˘P XE´ˆP MO`
.
TA`I LIEˆ. U TIE´ˆNG VIEˆ. T 95
hai danh sa´ch (tru.´o.c khi sa˘´p xeˆ´p va` sau khi sa˘´p xeˆ´p) ba˘´t da`ˆu tu`. vi. tr´ı thu´
. 5, nhu.ng cu˜ng
nhu. Vı´ du. treˆn, kha´c bieˆ.t khoˆng thaˆ. t ro˜.
Vı´ du. 3. Tu`
. khoa´ “ma´y t´ınh xa´ch tay Vieˆ.t Nam”, keˆ´t qua’ t`ım kieˆ´m cho ra 12 ta`i lieˆ.u. Tru
.´o.c
khi sa˘´p xeˆ´p, vi. tr´ı thu´
. 2 la` ta`i lieˆ.u “Long ma.ch:Tra’ lo`
.i nhu˜.ng caˆu ho’ i” cu’a Bu`i Tro.ng Lie˜ˆu
, sau khi sa˘´p xeˆ´p ta`i lieˆ.u na`y bi. daˆ’y xuoˆ´ng raˆ´t saˆu trong danh sa´ch. Noˆ. i dung ba`i na`y no´i
ve`ˆ long ma.ch (phong thuy’), chı’ co´ moˆ.t caˆu co´ tu`
. khoa´: “Co`n chuyeˆ.n moˆ˜i la`ˆn no´ (tu´
.c long
ma.ch) di do`
.i di daˆu, th`ı co´ pha’ i di do`.i theo no´ khoˆng, theo toˆi khoˆng co´ vaˆ´n de`ˆ : o.’ theˆ´ kı’ 21
na`y, no´ cu˜ng nhu. ca´i dieˆ.n thoa. i di doˆ.ng hay ca´i ma´y t´ınh xa´ch tay, di daˆu xa´ch no´ theo cu˜ng
du.o.. c ma`! ”. Ro˜ ra`ng noˆ. i dung ba`i ba´o raˆ´t ı´t lieˆn quan deˆ´n tu`
. khoa´ “ma´y t´ınh xa´ch tay Vieˆ.t
Nam”, neˆn vieˆ.c xeˆ´p no´ xuoˆ´ng ph´ıa du
.´o.i danh sa´ch la` ho.. p ly´.
Vı´ du. 4. Tu`
. khoa´ “gia´o tr`ınh ky˜ thuaˆ.t dieˆ.n”, keˆ´t qua’ t`ım kieˆ´m cho ra 25 ta`i lieˆ.u. Tru
.´o.c
khi sa˘´p xeˆ´p, vi. tr´ı thu´
. 2 la` ta`i lieˆ.u “Gia´o tr`ınh dieˆ.n tu
.’ ”, du.a ra danh mu. c ca´c gia´o tr`ınh dieˆ.n
tu.’ (tu´.c gia´o tr`ınh o.’ da.ng lu
.u treˆn ma.ng ve`ˆ du’ ca´c l˜ınh vu
.
. c nha.c hoa. , ngoa. i ngu˜
., vi t´ınh...
(khoˆng lieˆn quan maˆ´y deˆ´n gia´o tr`ınh ky˜ thuaˆ.t dieˆ.n). Sau khi sa˘´p xeˆ´p ta`i lieˆ.u na`y cu˜ng bi. daˆ’y
xuoˆ´ng cuoˆ´i danh sa´ch.
Vı´ du. 5. Tu`
. khoa´ “ca`i da˘.t windows XP”, keˆ´t qua’ t`ım kieˆ´m cho ra 20 ta`i lieˆ.u. Tru
.´o.c khi
sa˘´p xeˆ´p, vi. tr´ı thu´
. 3 la` ta`i lieˆ.u “ Loˆ˜i nghieˆm tro.ng cu’a Windows 2000 khieˆ´n ngu
.`o.i du`ng...“loˆ.
ha`ng”, co´ noˆ. i dung to´m ta˘´t nhu
. sau: “Moˆ.t nho´m chuyeˆn gia cu’a Israel tuyeˆn boˆ´ vu`
.a pha´t
hieˆ.n du
.o.. c moˆ. t loˆ˜ hoˆ’ng da˘.c bieˆ.t nghieˆm tro.ng beˆn trong heˆ. die`ˆu ha`nh Windows 2000 cu’a
Microsoft, cho phe´p hacker theo do˜i toa`n boˆ. nhu˜
.ng du˜. lieˆ.u da.ng text tu`
.ng du.o.. c go˜ va`o ma´y
t´ınh, bao goˆ`m email, maˆ. t khaˆ’u va` ca’ soˆ´ the’ t´ın du. ng.”. Noˆ. i dung na`y ro˜ ra`ng khoˆng ma´y lieˆn
quan deˆ´n tu`. khoa´ “ca`i da˘.t windows XP” va` do do´, vieˆ.c no´ bi. xeˆ´p xuoˆ´ng du
.´o.i sau khi sa˘´p xeˆ´p
theo thuaˆ.t toa´n mo`
. la` die`ˆu de˜ˆ hieˆ’u.
Vı´ du. 6. Tu`
. khoa´ “pha`ˆn me`ˆm ma˜ nguoˆ`n mo.’ ”, keˆ´t qua’ t`ım kieˆ´m cho ra 52 ta`i lieˆ.u. Tru
.´o.c
khi sa˘´p xeˆ´p, vi. tr´ı thu´
. 3 la` ta`i lieˆ.u “ Gio´
.i thieˆ.u ve`ˆ maˆ.t ma˜ lu
.o.. ng tu
.’ ” co´ noˆ. i dung to´m ta˘´t
la`: “Maˆ. t ma˜ lu
.o.. ng tu
.’ la` coˆng ngheˆ. cho phe´p ba’o maˆ. t thoˆng tin truye`ˆn di ba`˘ng truye`ˆn thoˆng
quang, qua quang so.. i cu˜ng nhu
. qua khoˆng gian (FSO - Free Space Optical communications).
No´ cho phe´p thoˆng tin du.o.. c ba’o maˆ. t ”tuyeˆ.t doˆ´i”, khoˆng phu. thuoˆ.c va`o doˆ. ma.nh cu’a ma´y
t´ınh, doˆ. toˆ´i taˆn cu’a du. ng cu. hay su
.
. xa’o quyeˆ.t cu’a hacker.” Ro˜ ra`ng noˆ. i dung na`y raˆ´t ı´t lieˆn
quan deˆ´n tu`. khoa´ “’pha`ˆn me`ˆm ma˜ nguoˆ`n mo.’ ”. Trong danh sa´ch ta`i lieˆ.u sau khi sa˘´p xeˆ´p theo
thuaˆ.t toa´n sa˘´p xeˆ´p mo`
., no´ cu˜ng bi. daˆ’y xuoˆ´ng du
.´o.i.
Qua ca´c v´ı du. treˆn ta thaˆ´y hieˆ.u qua’ bu
.´o.c da`ˆu cu’a thuaˆ.t toa´n, giu´p sa˘´p xeˆ´p ca´c ta`i lieˆ.u
t`ım thaˆ´y theo thu´. tu.. ho
.
. p ly´ kha’ na˘ng da´p u´
.ng yeˆu ca`ˆu ngu.`o.i su.’ du. ng. Thuaˆ.t toa´n cu˜ng nhu
.
chu.o.ng tr`ınh se˜ du.o.. c tieˆ´p tu. c hoa`n thieˆn trong tho`
.i gian to´.i.
5. KEˆ´T LUAˆ. N
Bu.´o.c da`ˆu chu.o.ng tr`ınh thu.’ nghieˆ.m chu´
.ng to’ du.o.. c u
.u dieˆ’m cu’a phu.o.ng pha´p du.a ra trong
ba`i ba´o. Deˆ’ hoa`n thieˆn, moˆ. t soˆ´ ca´c tieˆu ch´ı se˜ tieˆ´p tu. c du
.o.. c nghieˆn cu´
.u du.a va`o chu.o.ng
tr`ınh, doˆ`ng tho`.i ca´c tro.ng soˆ´ se˜ du
.o.. c chı’nh theo ca´c maˆ˜u ho.c deˆ’ di to´
.i ca´c tham soˆ´ chuaˆ’n
ho.n. Ngoa`i ra, khaˆu ta´ch tu`. cu˜ng se˜ du.o.. c hoa`n thieˆ.n deˆ’ co´ moˆ. t pha`ˆn me`ˆm co´ theˆ’ du
.a va`o
96 TRA`ˆN THA´I SO.N, LEˆ QUO´ˆC THA´I, NGUYE˜ˆN VA˘N NAM
su.’ du. ng trong thu
.
. c teˆ´.
TA`I LIEˆ. U THAM KHA
’O
[1] N.C. Ho and W.Wechler, Hedge algebras, An algebraic approach to structures of sets of linguistic
domains of linguistic truth variable, Fuzzy Sets and Systems 35 (3) (1990) 281–293.
[2] N. Cat Ho and W. Wechler, Extended hedge algebras and their application to Fuzzy logic, Fuzzy
Sets and Systems 52 (1992) 259–281.
[3] N.C. Ho, T.T. Son, T. D. Khang and L. X. Viet, Fuzzyness measure, quantified semantic map-
ping and interpolative method of approximate reasoning in medical expert systems, Journal of
Informatics and Cybernetics 18 (3) (2002) 237–252.
[4] Nguye˜ˆn Ca´t Hoˆ`, Tra`ˆn Tha´i So.n, Logic mo`. va` quyeˆ´t di.nh mo`
. du.. a treˆn caˆ´u tru´c thu´
. tu.. cu’a gia´
tri. ngoˆn ngu˜
., Ta.p ch´ı Tin ho. c va` Die`ˆu khieˆ’n ho. c 4 (1983).
[5] Nguye˜ˆn Ca´t Hoˆ`, Tra`ˆn Tha´i So.n, Ve`ˆ khoa’ng ca´ch giu˜.a ca´c gia´ tri. cu’a bieˆ´n ngoˆn ngu˜
. trong Da. i
soˆ´ gia tu.’ va` ba`i toa´n sa˘´p xeˆ´p mo`., Ta. p ch´ı Tin ho. c va` Die`ˆu khieˆ’n ho. c (1) (1995) 10–20.
Nhaˆ. n ba`i nga`y 3 - 12 - 2007
Nhaˆ. n la. i sau su
.’ a nga`y 24 - 1 -2008