CÁC PHƯƠNG PHÁP TỔ HỢP CHO BÀI TOÁN

CÁC PHƯƠNG PHÁP TỔ HỢP CHO BÀI TOÁN

Chương 1

Các kiến thức chuẩnbị

Trong chương 1, chúng tôi trình bàylạicác kiến thứccầnchuẩnbịđểphụcvụcho việc tìm hiểu và nghiêncứunhữngnộidungcủacác chương tiếp theo. Các vídụởchươngđượctrình bày theo góc nhìncủachính chúng tôi.

1.1 Các thuậtngữtrênđồthị

Địnhnghĩa 1.1.1 (trang 2, [8])

MộtđồthịlàmộtcặpG= (V, E) trongđó:

•V làtậphữuhạncácđỉnh(hoặc nút, hoặc điểm).

•E⊆[V ]² làtậpcác cạnh,mỗicạnh làmộttậpcongồm2 phầntửcủaV .

TậpV (G) và E(G)lầnlượtgọilàtậpđỉnhvàtậpcạnhcủađồthịG.Địnhnghĩa 1.1.2 (trang 3, [8])

Haiđỉnhu, v∈V (G)gọilàkềnhau (adjacent)nếu{u, v}∈E(G). Khiđó,cạnh {u, v}đượcgọilà cạnhnốiu và v.

Địnhnghĩa 1.1.3 (trang 3, [8])

MộtđồthịconcủaG = (V, E) làmộtđồthịG^′= (V^′, E^′) thỏa V^′⊆V và E^′⊆E∩[V^′]². NếuE^′ chứatấtcảcác cạnhcủaG cócảhaiđầumút thuộc V^′, thì G^′ đượcgọilàđồthị

ĐỗNgọc Liêm Luận văn Thạc sĩ

5

concảmsinh (induced subgraph), ký hiệu G[V^′].Địnhnghĩa 1.1.4 (trang 5, [8])

Bậc(degree)củamộtđỉnhv∈V(G), ký hiệu deg(v), làsốcạnh có v làđầumút.Nếu

deg(v) = 0, ta nói rằng v làmộtđỉnhcôlập(isolated vertex).

Địnhnghĩa 1.1.5 (trang 127, [8])MộtđồthịcóhướngG = (V, E) gồm: -Mộttậphợp V gồmcácđỉnh.

-MộttậphợpE các cung (cạnh có hướng), trongđómỗiphầntửcủaE làmộtcặpcóthứtự(u, v)vớiu, v∈V .Cặp(u, v) biểu diễnmộtcung đitừđỉnhuđếnđỉnhv.

Chúý

-Mộtđồthịcóhướngcóthểcó cungnốimộtđỉnhvớichính nó.

-Mộtđồthịcóthểcócảhai cung (u, v) và (v, u) giữa haiđỉnhkhác nhau.

-Nếugiữa cùngmộtcặpđỉnhcó nhiều cung trùng hướng,đồthịđượcgọilà đađồthịcóhướng.

Địnhnghĩa 1.1.6 (trang 128, [8]) TrongmộtđồthịcóhướngG = (V, E),đốivớimỗiđỉnhv∈V :

-Bậc đi racủav, ký hiệu deg⁺(v), làsốlượngcác cung cóhướngbắtđầutừđỉnhv.

-Bậc đi vàocủav, ký hiệu deg⁻(v), làsốlượngcác cung cóhướngkếtthúctạiđỉnhv. Chúý

-Tổngtấtcảbậcđi racủacácđỉnhbằng tổngsốcungcủađồthị,tứclà:

deg⁺(v) = |E|.

v∈V

-Tươngtự,tổngtấtcảbậcđi vàocủacácđỉnhcũng bằng tổngsốcung:

deg⁻(v) = |E|.

v∈V

Địnhnghĩa 1.1.7 (trang 6, [8])

Mộtđườngđi (path) làmộtdãy x₀, x₁, . . . , x_k cácđỉnhphân biệt sao chomỗicặpliên tiếp {x_i, x_i+1}∈E(G). Khiđó,đườngđi cóđộdài k, vàtậpcạnh là {x₀x₁, x₁x₂, . . . , x_k−1x_k}.Địnhnghĩa 1.3.8 (trang 9, [8])

ĐỗNgọc Liêm Luận văn Thạc sĩ

6

Mộtđồthịđượcgọilà liên thông (connected)nếuvớimọicặpđỉnhu, v∈V (G),tồntại mộtđườngđinốiu và v.

Mệnhđề1.1.1 (trang 24, [8]) XétđồthịG = (V, E)với|V | = n, |E| = m.Gọima trận

xuất hiện (incidence matrix) B = (bij)∈Fn×m2 đượcxácđịnhbởi:



1 nếuđỉnhv_i làmộtđầumútcủacạnh e_j,





bij =

0 ngượclại.







Ký hiệu B^T là chuyểnvịcủaB, và xem B và B^T như các ánhxạtuyến tính:

B : F^m₂→Fⁿ₂, B^T : Fⁿ₂→F^m₂.

Khiđó:

(i) Nhân (kernel)củaB là không gian chu trình C(G). (ii)Ảnh(image)củaB^T là không giancắtC^∗(G).

Định nghĩa 1.1.8 (trang 24, [8]) Cho một đồ thị G = (V, E) với tập đỉnh V = {v₁, v₂, . . . , v_n}.Ma trận liềnkềA = (a_ij)_n×n củaGđượcđịnhnghĩa bởi:



e_ij, nếucó cungtừv_i đếnv_j,





aij :=

0, ngượclại.







Chúý

-e_ij làsốlượngcác cung đitừđỉnhv_i đếnđỉnhv_j. -Nếuđồthịđơn, e_ij chỉnhận giátrị0 hoặc 1.

-Nếuđồthịđa cung, e_ij làsốnguyên không âm tùy theosốlượngcung giữa v_i và v_j. Vídụ1.1 XétđồthịG = (V, E)đượcmôtảbởisơđồtrạng thái sau:

ĐỗNgọc Liêm Luận văn Thạc sĩ

7

2

0

2

q1

q0

3

1

1

0

1

0

2

q2

2

1,2

Hình 1.1:Đồthịtrạng thái G = (V, E)đượcmôtảtrong vídụ1.1.

Tậpđỉnhcủađồthị:

V (G) = {q₀, q₁, q₂}.

Tậpcung (cạnh có hướng)củađồthị:

E(G) = {(q₀, q₀), (q₁, q₁), (q₂, q₂), (q₀, q₁), (q₀, q₂), (q₁, q₂), (q₁, q₀), (q₂, q₀), (q₂, q₁)}.

Mỗicungđượcgắnnhãnbởicác ký hiệu tươngứng(0, 1, 2 hoặc 3). Bậcđi ra deg⁺(v) vàbậcđi vào deg⁻(v)củacácđỉnh:

deg⁺(q₀) = 3, deg⁻(q₀) = 3,

deg⁺(q₁) = 3, deg⁻(q₁) = 3,

deg⁺(q₂) = 3, deg⁻(q₂) = 3.

Mỗiđỉnhđềucó 3 cung đi ra và 3 cung đi vào.

2 2 0

-Đườngđi vídụ:q0→−q1→−q2→−q0

.

-Độdàiđườngđi này là 3.

ĐồthịG là liên thông, vìvớimọicặpđỉnhbấtkỳ,luôntồntạimộtđườngđinốihai đỉnh. Ma trận liềnkềA = (a_ij)_3×3 vớii, j∈{0, 1, 2}đượccho bởi:

ĐỗNgọc Liêm Luận văn Thạc sĩ

8









A=















1 1 1



1 1 1









1 1 2

1.2 Lý thuyết automata

Khái niệm 1.2 (trang 1–2, [6]) Lý thuyết automata nghiêncứucác thiếtbịtính toán trừu tượng.Từthập niên 1930, Alan Turingđãgiới thiệu mô hình Turing machine nhằm xácđịnhgiớihạntính toáncủamáy móc.

Trong thập niên 1940–1950, các mô hìnhđơngiản hơngọilà finite automatađược phát triểnđểmô phỏng hoạtđộngcủahệthốnghữuhạntrạng thái, vàđãđượcứngdụng trong thiếtkếtrình biên dịch, kiểm tra giao thức và nhận dạng mẫu.

Mộtfinite automaton làhệthốngchỉởmộttrạng tháitạimỗithờiđiểm,thayđổi trạng thái theo quytắcxácđịnhdựatrênđầuvào. Vídụđiểnhình là côngtắcbật/tắt giữa hai trạng thái on và off.

Địnhnghĩa 1.2.1 (trang 45, [6])Mộtdeterministic finite automaton (DFA) là một bộgồm5 thành phần:

M = (Q,Σ, δ, q₀, F)

trongđó:

•Q làtậphữuhạncác trạng thái,

•Σlà bảngchữcáiđầuvào (input alphabet),

•δlà hàm chuyển trạng tháitừQ×ΣđếnQ,tứclàδ: Q×Σ→Q,

•q₀∈Q là trạng tháibắtđầu(start state),

•F⊆Q làtậpcác trạng thái chấp nhận (accepting states).

ĐỗNgọc Liêm Luận văn Thạc sĩ

9

MộtDFAđọcmộtchuỗi các ký hiệutừbảngchữcáiđầuvào và chuyển trạng thái theo hàmδ.Nếusau khiđọcxong chuỗi mà máykếtthúcởtrạng thái thuộctậpF,mộtchuỗiđượcchấp nhậnbởimáy M;ngượclại,kếtquảsẽlàtừchối.

Địnhnghĩa 1.2.2 (trang 52, [6]) Ngônngữđónnhận L làtậptấtcảcác chuỗiđónnhậnđượcbởiM,đượcgọilà ngônngữđónnhậnbởiM.

Địnhnghĩa 1.2.3 (trang 52, [6]) Chomộtbộtựđộnghữuhạnxácđịnh(DFA) A =

(Q,Σ, δ, q₀, F), tađịnhnghĩa ngônngữđónnhậnbởiA, ký hiệu L(A), làtậphợptấtcảcác chuỗi w∈Σ^∗ sao cho:

L(A) = {w |δˆ(q₀, w)∈F},

trongđó:

•δˆ(q₀, w) là trạng thái mà Ađạttớisau khibắtđầutừq₀ vàđọctoànbộchuỗi w,

•F⊆Q làtậpcác trạng thái chấp nhận.

Nói cách khác, ngônngữL(A) baogồmtấtcảcác chuỗi w sao cho khi thực hiện dãy chuyển theo wtừtrạng tháibắtđầuq₀,bộtựđộngsẽkếtthúcởmộttrạng thái thuộc tậpF .

Địnhnghĩa 1.2.4 (trang 54, [6]) HaibộtựđộnghữuhạnA₁ = (Q₁,Σ,δ₁, q₀¹, F₁) và

A₂ = (Q₂,Σ,δ₂, q₀²

tứclà:

, F₂)đượcgọilà tươngđươngnếuchúng chấp nhận cùngmộtngôn ngữ,

L(A₁) = L(A₂),

nghĩa làmỗichuỗi w∈Σ^∗ đượcchấp nhậnbởiA₁ thì cũngđượcchấp nhậnbởiA₂ vàngượclại.

Vídụ1.2.1 Xét DFA M = (Q,Σ, δ, q₀, F)vớicác thành phần sau:

•Q = {q₀, q₁}: làtậphữuhạncác trạng thái.

•Σ= {0, 1}: bảngchữcáiđầuvàogồmhai ký hiệunhịphân.

ĐỗNgọc Liêm Luận văn Thạc sĩ

10

•q₀: là trạng tháibắtđầu.

•F = {q₀}: làtậpcác trạng thái chấp nhận.

•Hàm chuyển trạng tháiδđượcchobởibảng sau:

Diễn giải hoạtđộng:DFA này hoạtđộngnhư sau:

•Nếuđọcký hiệu 0, máysẽchuyểnvềtrạng thái q₀ (hoặcgiữnguyênnếuđangởq₀).

•Nếuđọcký hiệu 1, máysẽchuyển sang trạng thái q₁ (hoặcgiữnguyênnếuđangở

q₁).

Ýnghĩa: Máychỉchấp nhận chuỗinếuký hiệu cuối cùng là 0, vì khiđómáykếtthúc tạitrạng thái q₀∈F.

Mộtsốchuỗicụthể:

•Chuỗi 0: q₀→−⁰

•Chuỗi 1: q₀→−¹

q₀⇒chấp nhận.

q₁⇒từchối.

•Chuỗi 10: q₀→−¹q₁→−⁰q₀⇒chấp nhận.

•Chuỗi 1101: q₀→−¹q₁→−¹q₁→−⁰q₀→−¹

•Chuỗi 1100: q₀→−¹q₁→−¹q₁→−⁰q₀→−⁰

q₁⇒từchối.

q₀⇒chấp nhận.

ĐỗNgọc Liêm Luận văn Thạc sĩ

11

1

0

1

q₁

q₀

0

Hình 1.2: Sơđồtrạng tháicủaDFA nhận các chuỗikếtthúc bằng ký hiệu 0.

DFAkếtthúcởtrạng thái q₀ nếuvàchỉnếuký hiệu cuối cùng là 0, dođóchỉchấp nhận các chuỗikếtthúc bằng 0.

Tiếp theo, chúng tôi xét DFA M^′= (Q^′,Σ,δ^′, p₀, F^′)vớicác thành phần sau:

•Q^′= {p₀, p₁}: làtậphữuhạncác trạng thái.

•Σ= {0, 1}: bảngchữcáiđầuvàogồmhai ký hiệunhịphân.

•p₀: là trạng tháibắtđầu.

•F^′= {p₀}: làtậpcác trạng thái chấp nhận.

•Hàm chuyển trạng tháiδ^′ đượcchobởibảng sau:

Diễn giải hoạtđộng:

•Nếuđọcký hiệu 0,bấtkểtừp₀ hay p₁, máysẽvềp₀.

•Nếuđọcký hiệu 1, máysẽchuyển sang p₁ (hoặcgiữnguyênnếuđãởp₁).

Ýnghĩa: DFA này cũngchỉchấp nhận chuỗinếuký hiệu cuối cùng là 0, giống với DFA M banđầu.

Mộtsốchuỗicụthể:

ĐỗNgọc Liêm Luận văn Thạc sĩ

12

•Chuỗi0: p₀→−⁰p₀⇒chấp nhận.

•Chuỗi 1: p₀→−¹p₁⇒từchối.

•Chuỗi 10: p₀→−¹p₁→−⁰p₀⇒chấp nhận.

•Chuỗi 1101: p₀→−¹p₁→−¹p₁→−⁰p₀→−¹

•Chuỗi 1100: p₀→−¹p₁→−¹p₁→−⁰p₀→−⁰

p₁⇒từchối.

p₀⇒chấp nhận.

1

0

1

p₁

p₀

0

Hình 1.3: Sơđồtrạng tháicủaDFA M^′ nhận các chuỗikếtthúc bằng ký hiệu 0.

1

0

1

p₁

p₀

0

Kếtluận: Hai DFA M và M^′ cócấutrúc trạng thái khác nhau nhưng chấp nhận cùngmộtngôn ngữ:

L(M) = L(M^′) = {w∈{0, 1}^∗| ký hiệu cuối cùngcủaw là 0}.

Dođó,M và M^′ là hai máytựđộngtương đương.

Địnhnghĩa 1.2.5 (trang 57, [6])Mộtnon-deterministic finite automaton (NFA) làmộtbộ5 thành phần:

A = (Q,Σ, δ, q₀, F)

trongđó:

•Q: làtậphữuhạncác trạng thái.

ĐỗNgọc Liêm Luận văn Thạc sĩ

13

•Σ: là bảngchữcáiđầuvào (tậphợpcác ký hiệuđầuvào).

•δ: Q×Σ→P(Q): là hàm chuyển trạng thái, nhậnmộttrạng thái vàmộtký hiệu,

trảvềmộttậpcác trạng thái.

•q₀∈Q: là trạng tháibắtđầu.

•F⊆Q: làtậphợpcác trạng thái chấp nhận (trạng tháikếtthúc).

KhácvớiDFA,tạimỗibướcxửlý ký hiệuđầuvào,mộtNFA có thể:

•Chọnmộttrong nhiều trạng thái có thể;

•Không có chuyển trạng thái nào (vô hiệu hóamộtsốnhánh);

•Mộtsốtrườnghợpkhôngcầnký hiệuđầuvào (nếu làε-NFA). Vídụ1.2.2 Xét NFA M = (Q,Σ, δ, q₀, F)vớicác thành phần sau:

•Q = {q₀, q₁, q₂}:tậpcác trạng thái.

•Σ= {0, 1}: bảngchữcáinhịphân.

•q₀: trạng tháibắtđầu.

•F = {q₂}:tậptrạng thái chấp nhận.

•Hàm chuyển trạng tháiδđượcchobởibảng sau:

Diễn giải hoạtđộng:

ĐỗNgọc Liêm Luận văn Thạc sĩ

14

•Từq₀,nếuđọc ký hiệu 0, NFA cóthểởlạiq₀ hoặc chuyển sang q₁.

•Từq₁,nếuđọcký hiệu 1, NFA chuyển sang q₂.

•Trạng thái q₂ là trạng tháikếtthúc.

Ýnghĩa: NFA này chấp nhận các chuỗinhịphân có dạng:

0ⁿ1, vớin≥1

Điềunày có nghĩalảchuỗi chứa ít nhấtmộtký hiệu 0, theo saubởiđúngmộtký hiệu 1. Mộtsốchuỗi minh họa:

•1→từchối (không cóđườngđitừq₀ theo 1).

•0→từchối (chưađếnđượcq₂).

•01→chấp nhận ( q₀→−⁰q₁→−¹q₂ ).

•001→chấp nhận ( q₀→−⁰q₀→−⁰

•0001→chấp nhận.

•10→từchối.

q₁→−¹q₂ ).

0

1

0

q₂

q₁

q₀

Hình 1.4: Sơđồtrạng tháicủaNFA nhận các chuỗikếtthúctạitrạng thái chấp nhận q₂.

NFA nàythểhiện rõ tính không xácđịnhvìtừtrạng thái q₀ vớiđầuvào 0, máy cóthểchọn giữa haihướngđi:ởlạihoặc chuyển tiếp sang q₁. Chuỗiđượcchấp nhận nếu tồntạiít nhấtmộtnhánhdẫnđếnq₂.

ĐỗNgọc Liêm Luận văn Thạc sĩ

15

Bảng 1.1: So sánh giữa DFA và NFA (trang 60–64, [6]).

ĐỗNgọc Liêm Luận văn Thạc sĩ

16

Địnhnghĩa 1.2.6 ( [6], trang 160) Minimization of DFA (Tối tiểu hóa DFA) là quátrình tìmmộtbộtựđộnghữuhạnxácđịnh(DFA) tươngđươngvớiDFAđãcho nhưng cósốlượngtrạng thái ít nhất. Quá trình nàygồmcácbướcchính: (1) loạibỏcác trạng thái khôngthểđạtđược,(2) xácđịnhcáccặptrạng thái cóthểphân biệtđược,và (3) gộpcác trạng thái khôngthểphân biệt thành cùngmộttrạng thái. DFA thuđượcsẽchấp nhận cùngmộtngônngữnhư DFA banđầuvà cósốlượngtrạng tháitốithiểu.

1

1

1

1

0

0

0

1

0

0

1

0

0

1

2

Hình 1.5: Vídụtốitiểu hóa DFA bằng cách loạibỏtrạng thái dư thừa. Bên trái: DFA banđầu.Bên phải: DFAtốitiểu.

1

1

1

0

0

1

1

0, 2

1

0

0

0

1

0

2

Hình 1.6: Vídụtốitiểu hóa DFA bằng cáchgộpcác trạng thái tương đương. Bên trái:

DFA banđầu.Bên phải: DFAtốitiểuvớitrạng thái 0, 2.

ĐỗNgọc Liêm Luận văn Thạc sĩ

17

1.3 Hệcó ràng buộc

Địnhnghĩa 1.3.1 (trang 39, [4])Mộthệràng buộc (constrained system) S làtậphợp tấtcảcáctừ(chuỗi ký hiệuhữuhạn) cóthểthuđượctừviệcđọccác nhãncủacácđườngđi trongmộtđồthịcóhướngcó nhãn G = (V, E,L), trongđó:

•V làtậpđỉnhhữuhạn;

•E⊆V×V làtậpcác cung có hướng;

•L : E→Σlà hàm gán nhãn, ánhxạmỗicung thànhmộtký hiệutừbảngchữcái

hữuhạnΣ.

Tậptấtcảcáctừthuđượcbằng cáchnốiliên tiếp các nhãn trên cácđườngđi trong Gđượcký hiệu là S(G), và ta nói rằng G làmộtbiểu diễncủahệthống ràng buộc S, với:

S = S(G) = L(e₁)L(e₂) . . . L(e_k) (e₁, e₂, . . . , e_k) làmộtđườngđi trong G .

ĐỗNgọc Liêm Luận văn Thạc sĩ

18

Hình 1.7: Các vídụcơbảnvềhệthống ràng buộc.

Đồthị1

1

1

1

0

0

Đồthị2

1

1 0

1

0

0

1

Đồthị3

0

1

0

1

0

0

0

1

1

1

0

Địnhnghĩa 1.3.2 (trang 3, [4]) Cho haisốnguyên d và k thỏa mãn 0≤d≤k. Mộtchuỗinhịphânđượcgọilà thỏa mãn ràng buộc (d, k)-Run-Length-Limited (gọi tắt là ràng buộc (d, k)-RLL)nếunó thỏa mãn cácđiềukiện sau:

-Giữa hai ký hiệu 1 liên tiếp trong chuỗi,sốlượngký hiệu 0nằmtrong khoảngtừdđến k,tứclà có ít nhất d và nhiều nhất k ký hiệu 0.

-Chuỗi các ký hiệu 0ởđầuchuỗi hoặcởcuối chuỗi (nếu có) khôngbịápđặtđiềukiệnvề

ĐỗNgọc Liêm Luận văn Thạc sĩ

19

độdài,tứclàđượcphép cóđộdài tùy ý.

Nói cách khác, trong chuỗinhịphân thỏa mãn ràng buộc (d, k)-RLL,mỗilầnxuất hiện mộtký hiệu 1, cácsố0 liền sau nó (chođếnký hiệu 1kếtiếp) phải cóđộdài khôngnhỏhơn d và khônglớnhơn k.

Địnhnghĩa 1.3.3 (trang 69, [4]) Chomộthệràng buộc (constrained system), ký hiệu N(n) làsốlượngcác chuỗihợplệcóđộdài n. Dunglượngcủahệđượcđịnhnghĩa bởi:

1

C = lim sup

n→∞ n

log₂ N(n)

Ýnghĩa: DunglượngC đotốcđộtăng trưởngcủasốlượngcác chuỗihợplệkhiđộdài chuỗi tiếntớivô hạn, phản ánhtốcđộcựcđại(bit trênmỗikýtự)củahệthốngdướicác ràng buộcđãcho.

Nếutồntạigiớihạnthông thường, ta có:

1

C = lim

n→∞n

log₂ N(n)

Hơn nữa,nếuhệthống cóthểđượcbiểu diễnbởimộtđồthịliên thông mạnh có trọngsốthì dunglượngcóthểđượctính bởi:

C = log₂λ

vớiλlàtrịriêng thực dươnglớnnhấtcủama trận liềnkềcủađồthịđó.

1.4 Địnhlý Perron–Frobenius

Địnhlý 1.4.1 (trang 72, [4]) Cho ma trận A khôngkhảquy. Khiđó,tồntạimộttrịriêngλ(A)củaA thỏa mãn:

-λ(A) làmộttrịriêng thực và dương.

-Tồntạicác vectơ riêng phải và vectơ riêng trái tươngứngvớiλ(A),vớitấtcảcác thành phầncủacác vectơ nàyđềudươngmộtcách nghiêm ngặt.

Địnhlý sauđâybiểu diễn dunglượngcủamộthệthống ràng buộc khôngkhảquy thông

ĐỗNgọc Liêm Luận văn Thạc sĩ

20

quatrịriênglớnnhấtcủama trậnkềcủamộtbiểu diễnmấtthông tincủahệthốngđó.Địnhlý 1.4.2 (trang 72, [4])GiảsửS làmộthệthống ràng buộc khôngkhảquy và G làmộtbiểu diễnmấtthông tin(đặcbiệt, xácđịnh)khôngkhảquycủaS. Khiđó,dung lượngcủaSđượcxácđịnhbởicông thức:

cap(S) = logλ(A_G),

trongđóλ(A_G) làtrịriênglớnnhấtcủama trậnkềA_G củađồthịG.

Địnhlý 1.4.3 (trang 91, [4]) Cho S làmộthệthốngbịràng buộcđượcbiểu diễn bởi mộtđồthịG không tiêu hao vàbấtkhảquy. Khiđó,

sup H(P) = logλ(A_G) = cap(S),

P

trongđó,supremumđượclấytrêntấtcảcác chuỗi Markov dừng trên G. Hệquả1.4 (trang 522, [7])

GiảsửA = [a_ij]∈M_n là ma trận không âm.Nếuxảyramộttrong haiđiềukiện sau:

• ⁿ_j=1 a_ij > 0 vớimọii = 1, . . . , n,

• ⁿ_i=1 a_ij > 0 vớimọij = 1, . . . , n,

thì bán kínhphổρ(A) > 0.Đặcbiệt,nếun≥2 và A là ma trận không âm vàbấtkhảquy, thì:

ρ(A) > 0.

Bổđề1.4 (trang 533, [7])

Cho A∈M_n làmộtma trận không âm. Khiđó,A là ma trậnbấtkhảquynếuvàchỉnếu:

(I + A)ⁿ⁻¹ > 0.

Địnhlý 1.4.4: Perron–Frobenius (trang 534, [7])

GiảsửA∈R^n×n làmộtma trận không âm (A≥0) vàbấtkhảquy . Khiđótồntạicác

kếtquảsau:

ĐỗNgọc Liêm Luận văn Thạc sĩ

21

(i)Tồntạimộtgiátrịriêng thực dươnglớnnhấtρ(A) > 0gọilà Perron root, thỏa

mãn Ax =ρ(A)xvớimộtvector riêng x > 0.

(ii)ρ(A)≥|λ|vớimọigiátrịriêngλ∈CcủaA.

(iii)ρ(A) làmộtnghiệmđơncủađa thứcđặctrưng det(A−λI), nghĩa làbộiđạisốcủa

nó bằng 1.

(iv)NếuA là ma trận nguyên thủy, thìmọigiátrịriêngλ=ρ(A)đềuthỏa |λ| <ρ(A). Chứng minh:

(a)Tồntạiρ(A) > 0:ĐiềunàyđượcđảmbảobởiHệquả8.1.25 ngaycảkhi không giảsửtínhbấtkhảquy.

(b) Giátrịriêngρ(A) là đơn:Giảsửρ(A) làmộtnghiệmbộicủađa thứcđặctrưng củaA. Khiđó,theo (8.4.2),ρ(I + A) =ρ(A) + 1sẽlàmộtnghiệmbộicủaI + A. Do

(I + A)ⁿ⁻¹ là ma trận dương,địnhlý 8.2.8(b) cho thấyρ(I + A) khôngthểlà nghiệm bội, dẫnđếnmâu thuẫn.

(c)Tồntạivector riêng dươngứngvớiρ(A):Địnhlý 8.3.1 cho tamộtvector x≥

0, x = 0 sao cho Ax =ρ(A)x. Do (I + A)ⁿ⁻¹ là ma trận dương (theobổđề8.4.1), nên

(I + A)ⁿ⁻¹x > 0. Dođó,

x = (1 +ρ(A))¹⁻ⁿ(I + A)ⁿ⁻¹x > 0.

Nếuchuẩn hóa bằng e^T x = 1, thì (b)đảmbảotính duy nhấtcủavector x.

(d)Tồntạivector riêng trái dương yứngvớiρ(A):Điềunày suy ra bằng cách áp dụng (c) cho ma trận chuyểnvịA^T .

1.5 Hàm sinh

Địnhnghĩa 1.5.1 (trang 33, [5]) Ký hiệu

f

ops

←→{a_n}

∞

0

ĐỗNgọc Liêm Luận văn Thạc sĩ

22

nghĩa là chuỗi f là hàm sinh dạng chuỗi lũy thừa thông thường (ordinary power series–

ops)củadãysố{a_n}^∞_n=0. Nói cách khác,điềunày có nghĩa là:

∞

f = a_nxⁿ.

n=0

Vídụ1.5.1.Dãysốtựnhiên Xét dãysố{a_n} với:

a_n = n vớimọin≥0.

Hàm sinh thường tươngứnglà:

∞ ∞

A(x) = a_nxⁿ = nxⁿ.

n=0 n=0

Áp dụng công thức:

∞

n

x

nx =

n=0

(1−x)

₂ , với|x| < 1,

ta có:

A(x) =

x

(1−x)₂ .

Vậyhàm sinh thườngcủadãy {0, 1, 2, 3, 4, . . .} là:

x

A(x) =

(1−x)₂ .

Vídụ1.5.2. Dãysốhằng

Xét dãysốa_n = 1vớimọin≥0. Hàm sinh thường là:

∞

A(x) = xn = 1

n=0 1−x

, với|x| < 1.

Vậyhàm sinh thườngcủadãy {1, 1, 1, 1, . . .} là:

1

A(x) =

1−x

.

ĐỗNgọc Liêm Luận văn Thạc sĩ

23

Vídụ1.5.3.Dãysốchẵn Xét dãy a_n = 2n (n≥0). Hàm sinh thường:

∞ ∞

A(x) = 2nxⁿ = 2 nxⁿ.

n=0 n=0

Áp dụng công thức:

∞

n x

nx =

n=0

(1−x)

₂,

ta có:

A(x) =

2x

(1−x)₂.

Vậyhàm sinh thườngcủadãy {0, 2, 4, 6, 8, . . .} là:

2x

A(x) =

(1−x)₂.

Quytắc1. (trang 34, [5])

Nếuf←→^ops{a

n}∞0, thìvớimọisốnguyên h > 0,

∞ ops

f−a₀−a₁x−···−a_h−1x^h−1

{a_n+h}0 ←→ x

h .

Quytắc2. (trang 35, [5])

Nếuf←→^ops{a

n}∞0, và P làmộtđa thức, thì:

P (xD)f←→ops{P (n)an}n≥0,

trongđóD = _dx^d và xD = x·_dx ^d.

Quytắc3. (trang 35–36, [5])

Nếuf←→^ops{a

n}∞0 và g←→ops{bn}∞0

, thì:

fg←→ops

n ∞

a_rb_n−r .

r=0 0

ĐỗNgọc Liêm Luận văn Thạc sĩ

24

Quytắc4. (trang 36, [5])

Nếuf(x)←→ops{an}∞0, và k∈Z+, thì:

f(x)k ←→ops

Quytắc5. (trang 37, [5])

Nếuf(x)←→ops{an}∞0, thì:

f(x)

n1+···+nk=n

n

ops

∞

a_n1 ···a_nk .

0

∞

1−x

Mệnhđề1.5. (trang 31, [5]) Mộtchuỗi hình thức

←→ a_j .

j=0 0

f = a_nxⁿ

n≥0

có nghịchđảo(đốivớiphép nhân chuỗi hình thức)nếuvàchỉnếua₀ = 0. Trong trường hợpđó,nghịchđảolà duy nhất.

Chứng minh.Giảsửf có nghịchđảo,tứclà

1

f

= b_nxⁿ

n≥0

.

Khiđó:

1

f·

f

= a_nxⁿ

n≥0

· b_nxⁿ

n≥0

= 1.

Tíchcủahai chuỗi hình thức trên làmộtchuỗi mới:

Vì f·_f¹

n

c_nxⁿ vớic_n = a_kb_n−k.

n≥0 k=0

= 1, nên:

c₀ = a₀b₀ = 1⇒a₀ = 0.

Vớimọin≥1, ta có:

n

c_n = a_kb_n−k = 0.

k=0

Tách hạngtửk = 0 ra, ta có:

n

a₀b_n + a_kb_n−k = 0.

k=1

ĐỗNgọc Liêm Luận văn Thạc sĩ

25

Dođó:

1

b_n = −

a₀

n

a_kb_n−k vớin≥1.

k=1

ĐỗNgọc Liêm Luận văn Thạc sĩ

26

Chương 2

Các phương pháp tính dung lượng củahệcó ràng buộc

Trong chương này, chúng tôitậptrung trình bày chi tiếtvềmô hình kênhđọccó trọng số, mộtmô hình toánhọcphản ánh quá trìnhđọcdữliệutừchuỗinhịphân thông qua các cửasổtrượtcó kíchthướccốđịnh.Điểmquan trọng nhấtcủachương này là chúng tôi trình bày các phương pháp tính capacitycủakênh. Các phương pháp mà chúng tôi trình bày phầnlớndựavào hai công trình nghiêncứutiêu biểu: công trìnhcủaYerushalmi, Etzion và Yaakobivềkênhđọccó trọngsốtrong lưutrữDNA [1], và công trìnhcủaChee, Vardy và cộngsựvềmã hóa transverse-read trongbộnhớdomain wall [2].

2.1 Mô hình kênhđọc

Địnhnghĩa 2.1.1 ([1], trang 2)

Cho chuỗinhịphân x = (x₁, x₂, . . . , x_n)∈{0, 1}ⁿ, cùng haisốnguyên dươngℓvàδsao choδ| (n−ℓ). Khiđó,read vector tươngứngvớimô hình (ℓ,δ)-read channel là:

R_ℓ,δ(x) = (wt(x[1,ℓ]), wt(x[δ+ 1,ℓ]), . . . , wt(x[tδ + 1,ℓ])) ,

vớiwt(x[a,ℓ]) là trọngsốHamming(sốlượngbit 1) trongđoạnconđộdàiℓbắtđầutại

ĐỗNgọc Liêm Luận văn Thạc sĩ

27

vịtrí a, và t =^n−ℓ_δ.

Vídụ2.1.1. Xét chuỗinhịphân x = (1, 1, 0, 0, 1, 1, 0, 1, 0) cóđộdài n = 9, với các thamsốcửasổ:

ℓ= 3, δ= 2.

Ta tiến hành xây dựng vectorđọcR_ℓ,δ(x) bằng cách dịchcửasổtrượtđộdàiℓ= 3 theo từngbướcnhảyδ= 2. Khiđó,sốlầnđọc(haysốđoạntrích) là:

n−ℓ 9−3

t = + 1 =

δ 2

+ 1 = 4.

Ta có cácđoạnđượcđọclầnlượtlà:

x_0:3 = (1, 1, 0), wt(x_0:3) = 2,

x_2:5 = (0, 0, 1), wt(x_2:5) = 1,

x_4:7 = (1, 1, 0), wt(x_4:7) = 2,

x_6:9 = (0, 1, 0), wt(x_6:9) = 1.

Dođó,vectorđọctươngứnglà:

R_3,2(x) = (2, 1, 2, 1) .

Trongđó,mỗiphầntửtrong vector R_3,2(x) tươngứngvớitrọngsốHamming (Hamming weight)củađoạncon cóđộdài 3tạicácvịtrí:

Vịtríbắtđầu:0, 2, 4, 6.

Vectorđọcnày phản ánhsốlượngbit 1 xuất hiện trongmỗicửasổcon, và làđặc trưng cho quá trình quan sátđượctừkênhđọccó thamsố(ℓ,δ). Vídụnàythểhiện cáchánhxạmộtchuỗinhịphân thành vectorđọcvà làbướckhởiđầuquan trọng cho bài toán mã hóa hoặc táitạochuỗi banđầutừvectorđọcđãcho.

Địnhnghĩa 2.1.2 ([1], trang 2)

Cho haisốnguyên dươngℓvàδ,mộtchuỗinhịphân x = (x₁, x₂, . . . , x_n)∈{0, 1}ⁿđượcđưavào mô hình (ℓ,δ)-read channel như sau:

ĐỗNgọc Liêm Luận văn Thạc sĩ

28

Tatrượtmộtcửasổcóđộdàiℓtrên chuỗi x,mỗilầntrượtmộtbướcδvịtrí.Tạimỗi vịtrí, ta tính trọngsốHamming (tổngsốlượngbit 1) trongcửasổhiện tại.

Vectorđọcđầura là:

R_ℓ,δ(x) = (wt(x[1,ℓ]), wt(x[δ+ 1,ℓ]), . . . , wt(x[tδ + 1,ℓ])) ,

vớiwt(·) là hàm trọngsốHamming, và t =^n−ℓ_δ,giảsửδ| (n−ℓ).

Vídụ2.1.3Vớiℓ= 3,δ= 2, và chuỗi x = (1, 0, 1, 1, 0, 0, 1, 0, 1), ta có:

R_3,2(x) = (wt(x[1, 3]), wt(x[3, 3]), wt(x[5, 3]), wt(x[7, 3])) = (2, 2, 1, 2).

Địnhnghĩa 2.1.3 ([2], trang 2)

Mô hình (ℓ,δ)-transverse-read channelđượcđịnhnghĩa trênmộtchuỗinhịphân x =

(x₁, x₂, . . . , x_n)∈{0, 1}ⁿ như sau:

Tạimỗilầnđọc,mộtđoạncon cóđộdàiℓđượctrích ra,bắtđầutừvịtrí 1,δ+ 1, 2δ+

1, . . . , kδ + 1,tiến hành ghi nhận trọngsốHammingcủamỗiđoạnởmỗilầntrượt. Tagiảsửn = kδ +ℓ.

Vector transverse-read là:

TR_ℓ,δ(x) = (wt(x[1,ℓ]), wt(x[δ+ 1,ℓ]), . . . , wt(x[kδ + 1,ℓ])) .

Vídụ2.1.4Vớiℓ= 4,δ= 2, và chuỗi x = (0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0), ta có:

TR_4,2(x) = (wt(x[1, 4]), wt(x[3, 4]), wt(x[5, 4]), wt(x[7, 4]), wt(x[9, 4])) = (1, 2, 3, 2, 0).

Tính chất 2.1.1. ([1], trang 2) Kênh khôngđơnánh (Non-injective)

Vớimô hình R_ℓ,δ,tồntạicác chuỗinhịphân khác nhau x = y sao cho:

R_ℓ,δ(x) = R_ℓ,δ(y)

Điềunày cho thấy quá trình ánhxạtừchuỗinhịphânđầuvào sang vectorđọckhông phải làđơnánh, vàdẫnđếnhiệntượngmơhồkhi giải mã gây khó khăn cho việc tìm ra thứtựcác xâunhịphân trong chuỗi.

ĐỗNgọc Liêm Luận văn Thạc sĩ

29

Vídụ2.1.5Vớiℓ= 5,δ= 3, ta có:

x = (1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1) y = (1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1)

Ta xây dựng cácđoạnconđộdài 5bắtđầutạivịtrí:

1, 4, 7, 10

Sauđó,tính trọngsốHammingcủatừngđoạnnhịphân:

Vớix:

x[1; 5] = (1, 0, 1, 1, 0)⇒wt = 3

x[4; 5] = (1, 0, 1, 1, 0)⇒wt = 3

x[7; 5] = (1, 0, 0, 1, 0)⇒wt = 2

x[10; 5] = (1, 0, 1, 0, 0)⇒wt = 2

Vớiy:

y[1; 5] = (1, 1, 0, 1, 0)⇒wt = 3

y[4; 5] = (1, 0, 0, 1, 0)⇒wt = 2

y[7; 5] = (1, 1, 0, 0, 0)⇒wt = 2

y[10; 5] = (1, 0, 0, 0, 1)⇒wt = 2

R_5,3(x) = (3, 3, 2, 2), R_5,3(y) = (3, 3, 2, 2)

Mặcdù hai chuỗinhịphân x = y, tavẫncó:

R_5,3(x) = R_5,3(y)

Điềunày khẳngđịnhrằng mô hình R_ℓ,δ khôngbảotoànmộtcách hoàn toàn thông tin và cóthểánhxạnhiều chuỗiđầuvào khác nhauvềcùngmộtvectorđọc,gây ra hiện tượngkhôngđơnánh.

ĐỗNgọc Liêm Luận văn Thạc sĩ

30

Tính chất 2.1.2 ([1], trang 3) Dunglượngkênhbịgiớihạnbởiđộchồnglấp

Nếuℓ>δ, cáccửasổđọcbịchồng lấp, khiến thông tin trong cácđoạnkếtiếp khôngđộclập.Điềunày làm giảm đángkểcapacity, và gây nhiễu giữa các ký hiệu (inter-symbol interference).

Tính chất 2.1.3. ([2], trang 2)Tỷlệmãtốiđaphụthuộc vàoℓvàδVớicác giátrịcụthể, ta có:

•Nếuℓ=δ, thì R(ℓ,δ) =

•Nếuℓ= 1, thì R(1,δ) =

log₂(ℓ+ 1)

ℓ

1

δ

•Nếuδ= 1, thì R(ℓ,1) = 1

•Nếuℓ≤δ, thì R(ℓ,δ) =

log₂(ℓ+ 1)

δ

Tính chất 2.1.4. ([2], trang 3)Tồntạicáccậndướivà trên chặt cho dunglượngkênh Khiδ= 2 vàℓchẵn, ta có:

R(ℓ,2) = log₂ 3

2

≈0.7925

Tính chất 2.1.5. ([2], trang 3) Mãđọctransverse cóthểđượcbiểu diễn bằng ngôn ngữchính quy

Tậphợpcác vectorđọchợplệcóthểđượcbiểu diễn nhưmộtngônngữchính quy (regular language) và cóthểmô hình hóa bằngmộtautomaton.Điềunày cho phép áp dụng cáckỹthuậttừmã hóabịràng buộc (constrained codes)đểxây dựng các mã hiệu quả.

Tính chất 2.1.6. ([1], trang 6) Cóthểchuyển mô hình kênhđọcthànhđồthịhữu hạn

Kênh (ℓ,δ) cóthểđượcbiểu diễndướidạngmộtđồthịchuyển trạng thái G(ℓ,δ) hoặc H(ℓ,δ)vớicácđỉnhđạidiện cho trạng thái chuỗi con, và các cạnh mang nhãn là trọng sốHamming. Việc phân tíchđồthịcho phép tínhgầnđúng dunglượngcủakênhđọc.

ĐỗNgọc Liêm Luận văn Thạc sĩ

31

2.2 Mô hình kênhđọccó trọngsố

Địnhnghĩa 2.2.1. ([1], trang 3)TậpđỉnhcủađồthịG(ℓ,δ)

Cho haisốnguyên dươngℓvàδ,đồthịG(ℓ,δ)đượcxây dựngđểmô hình hóa các chuyểnđổigiữa các trạng thái trong quá trìnhđọctrượtcủachuỗinhịphân.Tậpđỉnhđượcđịnhnghĩa là:

V (G(ℓ,δ)) = {s∈Σℓ−δ2}

trongđóΣℓ−δ2 = {0, 1} là bảngchữcáinhịphân.Mỗiđỉnhs làmộtchuỗi conđộdàiℓ−δ,

đạidiện cho phần chồnglấpgiữa hailầnđọcliên tiếp trong mô hình (ℓ,δ)-read channel.

Vídụ2.2.1Vớiℓ= 6,δ= 3, ta có:

ℓ−δ= 3⇒V (G(6, 3)) =Σ³ ₂= {000, 001, 010, 011, 100, 101, 110, 111}

Như vậy,đồthịG(6, 3) có tổng cộng 2³ = 8đỉnh,mỗiđỉnhbiểu diễnmộttrạng tháikhảdĩcủa3 bit.

Địnhnghĩa 2.2.2. ([1], trang 3)TậpcạnhcủađồthịG(ℓ,δ)

Cho haisốnguyên dươngℓvàδ,vớiδ<ℓ, mô hình kênhđọc(ℓ,δ) cóthểđượcbiểu diễn bằngmộtđồthịcóhướngG(ℓ,δ), trongđó:

Tậpcạnhđượcđịnhnghĩa là:

E(G(ℓ,δ)) = u−→^αv :∃x∈Σ^ℓ₂, u = x[1 :ℓ−δ], v = x[δ+ 1 :ℓ],α= wt(x)

Trongđó:

•u, v∈Σℓ−δ2: là haiđỉnh(tức là hai chuỗi conđộdàiℓ−δ),

•x∈Σ^ℓ₂: là chuỗinhịphânđộdàiℓ,

•x[1 :ℓ−δ] = u, x[δ+ 1 :ℓ] = v,

•wt(x): là trọngsốHammingcủachuỗi x,tứclàsốlượngbit 1 trong x,

ĐỗNgọc Liêm Luận văn Thạc sĩ

32

•α∈{0, 1, . . . ,ℓ}: là nhãngắnvớicạnh,đạidiện chođầuracủalầnđọctươngứng

trong mô hình kênh.

Mỗicạnh trongđồthịtươngứngvớimộtchuỗi conđộdàiℓđượcquét quacửasổđọc,trongđóphầnđầulà trạng thái hiệntạiu, phần cuối là trạng thái tiếp theo v, vànhãn cạnh là giátrịđầura (tổng trọngsốHamming)củađoạnx.

Địnhnghĩa 2.3.3. ([1], trang 3) Nhãn trênmỗicạnhcủađồthịG(ℓ,δ)

TrongđồthịcóhướngG(ℓ,δ),mỗicạnh mangmộtnhãn trọngsốHamming.Cụthể,

vớimỗicạnh u−→^α

v∈E(G(ℓ,δ)),tồntạimộtchuỗinhịphân x∈Σ^ℓ₂ sao cho:

u = x[1 :ℓ−δ] v = x[δ+ 1 :ℓ]

α= wt(x)

Trongđó:

•wt(x) là trọngsốHammingcủachuỗi x,tứclàsốlượngbit 1 trong chuỗiđó.

•Nhãnα∈{0, 1, . . . ,ℓ}đạidiện chođầuratạithờiđiểmđọcđoạnx trong mô hình

kênhđọc.

Mỗicạnh trongđồthịkhôngchỉmôtảmốiliênkếtgiữa hai trạng thái chồnglấpu và v, mà còn mang theo thông tinđầuracủakênhđọcdướidạngmộtsốnguyên là trọng sốHamming.

Vídụ2.2.2.Vớiℓ= 3,δ= 1, ta có:

ℓ−δ= 2⇒V (G(3, 1)) =Σ²₂

Tứclàtậpđỉnhgồmtấtcảcác chuỗinhịphânđộdài 2. Khiđó,ta có tổng cộng 2² = 4đỉnh,cụthểlà: {00, 01, 10, 11}.

Xét chuỗinhịphân:

x = (1, 0, 1)∈Σ³₂

ĐỗNgọc Liêm Luận văn Thạc sĩ

33

Ta xácđịnh:

u= x[1 : 2] = (1, 0) = 10 v = x[2 : 3] = (0, 1) = 01

α= wt(x) = tổngsốbit 1 trong x = 2

Dođó,ta có cạnh:

10→−²01∈E(G(3, 1))

Cạnh này biểu diễn quá trình chuyển trạng thái trong mô hình R_3,1,vớinhãn là 2.Điềunày có nghĩa làđoạnđọcgồm3 bit có tổng trọngsốHamming là 2.

Vídụ2.2.3Vớiℓ= 11,δ= 2, ta có:

ℓ−δ= 9⇒V (G(11, 2)) =Σ⁹₂

Tứclàtậpđỉnhgồmtấtcảchuỗinhịphânđộdài 9. Khiđó,ta có tổng cộng 2⁹ = 512đỉnh.

Xét chuỗinhịphân:

x = (1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0)∈Σ¹¹₂

Ta xácđịnh:

u = x[1 : 9] = (1, 0, 1, 1, 0, 0, 1, 1, 0) = 101100110

v = x[3 : 11] = (1, 1, 0, 0, 1, 1, 0, 1, 0) = 110011010α= wt(x) = tổngsốbit 1 trong x = 6

Dođó,ta có cạnh:

101100110→−⁶110011010∈E(G(11, 2))

Cạnh này biểu diễn quá trình chuyển trạng thái trong mô hình R_11,2,vớinhãn là 6.Điềunày có nghĩa làđoạnđọcgồm11 bit có tổng trọngsốHamming là 6.

LIÊN HỆ:

SĐT+ZALO: 0935568275

KHO TÀI LIỆU.rar\TÀI LIỆU 2025 – RAR archive, unpacked size 64,245,423 bytes/ CÁC PHƯƠNG PHÁP TỔ HỢP CHO BÀI TOÁN

CÁC PHƯƠNG PHÁP TỔ HỢP CHO BÀI TOÁN CÁC PHƯƠNG PHÁP TỔ HỢP CHO BÀI TOÁN