BÀI GI NG TH VI N SẢ Ư Ệ Ố
Ch ng 2: ươ MÔ HÌNH HÌNH TH C CHO TH VI N S DLỨ Ư Ệ Ố
TS. Đ QUANG VINHỖ
HÀ N I - 2013Ộ
2
2
N I DUNGỘ
I. T NG QUAN V TH VI N S DLỔ Ề Ư Ệ Ố
II. MÔ HÌNH HÌNH TH C CHO TH VI N S DLỨ Ư Ệ Ố
III. CH M C TÀI LI UỈ Ụ Ệ
IV. TÌM KI M THÔNG TINẾ
V. CÁC CHU N S D NG TRONG TH VI N SẨ Ử Ụ Ư Ệ Ố
VI. TH C HÀNH H PH N M M Ự Ệ Ầ Ề
TH VI N S GREENSTONEƯ Ệ Ố
3
3
II. MÔ HÌNH HÌNH TH C CHO TH VI N S DLỨ Ư Ệ Ố
1. C s toán h cơ ở ọ
Đ nh nghĩa 2.1ị: M t ột p h pậ ợ là m t s u t p không s p x p ộ ư ậ ắ ế
các th c th phân bi t.ự ể ệ
Đ nh nghĩa 2.2ị: M t ộquan hệ nh phânị R trên t p h p A và B ậ ợ
là m t t p con c a A x B. Ký hi u (a,b) ộ ậ ủ ệ ∈ R là aRb. M t quan ộ
h R n-phân trên các t p h p A1, A2, ..., An là m t t p con ệ ậ ợ ộ ậ
c a tích Đ các A1x A2 x ... x Anủ ề
Đ nh nghĩa 2.3ị: Cho tr c hai t p h p A và B, m t ướ ậ ợ ộ hàm f là
m t quan h nh phân trên A x B sao cho đ i v i m i m t a ộ ệ ị ố ớ ỗ ộ ∈
A t n t i b ồ ạ ∈ B sao cho (a,b) ∈ f và n u (a,b) ế∈ f và (a,c) ∈ f
thì b = c. T p h p A đ c g i là mi n xác đ nh c a f và t p ậ ợ ượ ọ ề ị ủ ậ
h p B đ c g i là mi n giá tr c a f. Ký pháp f : A ợ ượ ọ ề ị ủ → B và b
= f(a) là m t ký pháp chung đ i v i (a,b) ộ ố ớ ∈ f. T p h p {f(a)| a ậ ợ
∈ A} đ c g i là vùng c a f.ượ ọ ủ
Đ nh nghĩa 2.4ị: M t ộdãy là m t hàm f , có mi n xác đ nh là ộ ề ị
t p h p các s t nhiên ho c t p con ban đ u nào đó c a {1, ậ ợ ố ự ặ ậ ầ ủ
2, ... , n} c a các s t nhiên và mi n giá tr c a nó là t p b t ủ ố ự ề ị ủ ậ ấ
kỳ.
4
4
Đ nh nghĩa 2.5ị:
M t ộb ộlà m t dãy h u h n th ng đ c ký hi u b ng cách ộ ữ ạ ườ ượ ệ ằ
li t kê d i các giá tr c a hàm nh <f(1), f(2), ... , f(n)>.ệ ả ị ủ ư
Đ nh nghĩa 2.6ị:
M t ộxâu là m t dãy h u h n các ký t ho c ký hi u rút ra t ộ ữ ạ ự ặ ệ ừ
m t t p h p h u h n v i ít nh t hai ph n t , đ c g i là b ng ch . ộ ậ ợ ữ ạ ớ ấ ầ ử ượ ọ ả ữ
M t xâu th ng đ c ký hi u b ng cách n i v i nhau d i các giá tr ộ ườ ượ ệ ằ ố ớ ả ị
không có ký t phân cách.ự
Cho Σ là m t b ng ch . ộ ả ữ Σ* ký hi u t p h p t t c xâu t ệ ậ ợ ấ ả ừ Σ,
bao hàm xâu r ng (m t dãy r ng ỗ ộ ỗ ε). M t ngôn ng là m t t p con ộ ữ ộ ậ
c a ủΣ*.
5
5
Đ nh nghĩa 2.7ị:
M t ộđ thồ ị G là m t c p (V, E), trong đó V là m t t p đ nh ộ ặ ộ ậ ỉ
không r ng và E là m t t p c a m t t p c nh {u, v}, u, v ỗ ộ ậ ủ ộ ậ ạ ∈ V. M t ộ
đ th có h ng G là m t c p (V, E), trong đó V là m t t p đ nh (nút) ồ ị ướ ộ ặ ộ ậ ỉ
không r ng và E là m t t p c nh (cung) trong đó m i m t c nh là ỗ ộ ậ ạ ỗ ộ ạ
m t c p th t đ nh phân bi t (vi, vj) v i vi, vj ộ ặ ứ ự ỉ ệ ớ ∈ V và vi ≠ vj. C nh ạ
(vi, vj) đ c g i là liên thu c trên các đ nh vi và vj, trong đó vi k ượ ọ ộ ỉ ề
v i vj và vj k t vi.ớ ề ừ
Đ nh nghĩa 2.8ị:
M t ộvăn ph m phi ng c nhạ ữ ả là m t b b n (V, ộ ộ ố Σ, R, s0) trong
đó V là m t t p bi n g i là không k t thúc, ộ ậ ế ọ ế Σ là b ch ký hi u k t ộ ữ ệ ế
thúc, R là m t t p lu t h u h n và s0 là m t ph n t phân bi t c a ộ ậ ậ ữ ạ ộ ầ ử ệ ủ
V g i là ký hi u b t đ u.ọ ệ ắ ầ
M t lu t/ m t s n xu t là m t ph n t c a t p V x (V ộ ậ ộ ả ấ ộ ầ ử ủ ậ ∪
Σ)*. M i m t s n xu t có d ng SX ỗ ộ ả ấ ạ → α trong đó SX là m t ký hi u ộ ệ
không k t thúc và ếα là m t xâu ký hi u (k t thúc và/ho c không k t ộ ệ ế ặ ế
thúc).