User Tools

Site Tools


0129--c-u-tr-c-d-li-u-cho-c-c-t-p-h-p-kh-ng-giao-nhaula-gi

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

0129--c-u-tr-c-d-li-u-cho-c-c-t-p-h-p-kh-ng-giao-nhaula-gi [2018/11/07 17:09] (current)
Line 1: Line 1:
 +<​HTML><​br><​div id="​mw-content-text"​ lang="​vi"​ dir="​ltr"><​div class="​mw-parser-output"><​p>​Trong khoa học máy tính, <​b>​cấu trúc dữ liệu cho các tập hợp không giao nhau</​b>​ là một cấu trúc dữ liệu để lưu trữ một tập hợp các phần tử được phân chia thành nhiều tập hợp con không giao nhau. <​b>​Thuật toán hợp-tìm</​b>​ là một thuật toán cho phép thực hiện hai thao tác sau:
 +</p>
 +<​ul><​li><​i>​Tìm</​i>:​ Tìm xem một phần tử cho trước nằm trong tập hợp nào. Có thể dùng để xác định hai phần tử cho trước có nằm trong cùng một tập hợp hay không.</​li>​
 +<​li><​i>​Hợp</​i>:​ Hợp hai tập hợp làm một.</​li></​ul><​p>​Do nó hỗ trợ hai thao tác trên nên cấu trúc dữ liệu cho các tập hợp không giao nhau còn được gọi là cấu trúc dữ liệu hợp tìm. Một thao tác quan trọng nữa nhưng thường rất đơn giản là <​i>​Tạo-tập</​i>,​ dùng để tạo một tập mới chỉ chứa đúng một phần tử.
 +</​p><​p>​Để định nghĩa các thao tác trên một cách cụ thể, cần có một cách để ghi nhớ các tập. Một phương pháp phổ biến là dùng một phần tử cố định của mỗi tập để đại diện cho tập đó. <​i>​Tìm(x)</​i>​ trả về phần tử đại diện của tập chứa <​i>​x</​i>​. <​i>​Hợp</​i>​ nhận hai đối số là phần tử đại diện của hai tập.
 +</p>
 +<​h3><​span id="​R.E1.BB.ABng_c.C3.A1c_t.E1.BA.ADp_kh.C3.B4ng_giao_nhau"/><​span class="​mw-headline"​ id="​Rừng_các_tập_không_giao_nhau">​Rừng các tập không giao nhau</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Rừng các tập không giao nhau là cấu trúc dữ liệu trong đó mỗi tập được biểu diễn bởi một cây, trong đó mỗi nút lưu một con trỏ đến nút cha của nó. Cấu trúc dữ liệu này được mô tả lần đầu tiên bởi Bernard A. Galler và Michael J.Fischer năm 1964,<​sup id="​cite_ref-1"​ class="​reference">​[1]</​sup>​ nhưng độ phức tạp tính toán của nó chỉ được phân tích chính xác nhiều năm sau đó.
 +</​p><​p>​Trong rừng các tập không giao nhau, đại diện của mỗi tập là nút gốc của cây biểu diễn tập đó. Thao tác <​i>​tìm</​i>​ đi theo các con trỏ đến nút cha cho tới khi đến nút gốc. Thao tác <​i>​hợp</​i>​ hợp hai cây làm một bằng cách gắn một nút gốc vào làm nút con của nút gốc kia. Một phương pháp cài đặt các thao tác này là như sau:
 +</p>
 +<​pre><​b>​function</​b>​ Tạo-tập(x)
 +x.cha ← x
 +</​pre>​
 +<​pre><​b>​function</​b>​ Tìm(x)
 +<​b>​if</​b>​ x.cha == x <​b>​then</​b>​
 +<​b>​return</​b>​ x
 +<​b>​else</​b>​
 +<​b>​return</​b>​ Tìm(x.cha)
 +</​pre>​
 +<​pre><​b>​function</​b>​ Hợp(x, y)
 +xGốc ← Tìm(x)
 +yGốc ← Tìm(y)
 +xGốc.cha ← yGốc
 +</​pre>​
 +<​p>​Theo như cách cài đặt đơn giản như trên thì phương pháp này kém hiệu quả do các cây không cân bằng. Có hai cách để làm thuật toán hiệu quả hơn.
 +</​p><​p>​Phương pháp thứ nhất, gọi là <​i>​hợp dùng hạng</​i>,​ là luôn gắn nút gốc cây nhỏ hơn vào làm nút con của nút gốc cây lớn hơn. Cụ thể hơn, mỗi cây đều có một tham số, gọi là hạng. Cây có đúng một phần tử có hạng bằng 0. Khi hợp hai cây cùng có hạng <​i>​r</​i>,​ hạng của cây mới sẽ là <​i>​r+1</​i>​. Chỉ với phương pháp này, cấu trúc dữ liệu đã đảm bảo thời gian trừ dần <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle O(log n)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​O</​mi><​mo stretchy="​false">​(</​mo><​mi>​log</​mi><​mo>​⁡<​!-- &#8289; --></​mo><​mi>​n</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle O(log n)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​aae0f22048ba6b7c05dbae17b056bfa16e21807d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​8.336ex;​ height:​2.843ex;"​ alt="​O(log n)"/></​span>​ cho mỗi thao tác. Sau đây là mã giả mới của <​i>​Tạo-tập</​i>​ và <​i>​Hợp</​i>​ cho thuật toán cải tiến.
 +</p>
 +<​pre><​b>​function</​b>​ Tạo-tập(x)
 +x.cha ← x
 +x.hạng ← 0
 +</​pre>​
 +<​pre><​b>​function</​b>​ Hợp(x, y)
 +xGốc ← Tìm(x)
 +yGốc ← Tìm(y)
 +<​b>​if</​b>​ xGốc == yGốc <​b>​then</​b>​
 +<​b>​return</​b>​
 +<​b>​if</​b>​ xGốc.hạng &lt; yGốc.hạng <​b>​then</​b>​
 +xGốc.cha ← yGốc
 +<​b>​else if</​b>​ xGốc.hạng &gt; yGốc.hạng <​b>​then</​b>​
 +yGốc.cha ← xGốc
 +<​b>​else</​b>​
 +yGốc.cha ← xGốc
 +xGốc.hạng ← xGốc.hạng + 1
 +</​pre>​
 +<​p>​Cải tiến thứ hai, gọi là <​i>​nén đường</​i>,​ là một cách để rút ngắn đường trên cây khi thực hiện thao tác <​i>​tìm</​i>​. Ý tưởng của cải tiến này là bất cứ nút nào được thăm trong một thao tác tìm đều được gắn trực tiếp với nút gốc, để các thao tác tìm sau này nếu lại đi qua các nút này thì không cần phải lặp lại các thao tác đã thực hiện. Sau đây là mã giả mới cho thao tác <​i>​Tìm</​i>​.
 +</p>
 +<​pre><​b>​function</​b>​ Tìm(x)
 +<​b>​if</​b>​ x.cha == x <​b>​then</​b>​
 +<​b>​return</​b>​ x
 +<​b>​else</​b>​
 +x.cha ← Tìm(x.cha)
 +<​b>​return</​b>​ x.cha
 +</​pre>​
 +<​p>​Hai cải tiến này bổ trợ cho nhau. Khi sử dụng cả hai, thời gian trừ dần của mỗi thao tác là <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle O(alpha (n))}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​O</​mi><​mo stretchy="​false">​(</​mo><​mi>​α<​!-- &alpha; --></​mi><​mo stretchy="​false">​(</​mo><​mi>​n</​mi><​mo stretchy="​false">​)</​mo><​mo stretchy="​false">​)</​mo></​mstyle></​mrow>​{displaystyle O(alpha (n))}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0f2f9c5bf5571b12dd0907f0a1ef917e1c082201"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​8.274ex;​ height:​2.843ex;"​ alt="​{displaystyle O(alpha (n))}"/></​span>,<​sup id="​cite_ref-2"​ class="​reference"><​a href="#​cite_note-2">​[2]</​sup>​ trong đó <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle alpha (n)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​α<​!-- &alpha; --></​mi><​mo stretchy="​false">​(</​mo><​mi>​n</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow>​{displaystyle alpha (n)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​74c1642d9e2f86b9e5c86c0f18ee5377507da827"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​4.692ex;​ height:​2.843ex;"​ alt="​{displaystyle alpha (n)}"/></​span>​ là hàm ngược của <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f(n)=A(n,​n)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​f</​mi><​mo stretchy="​false">​(</​mo><​mi>​n</​mi><​mo stretchy="​false">​)</​mo><​mo>​=</​mo><​mi>​A</​mi><​mo stretchy="​false">​(</​mo><​mi>​n</​mi><​mo>,</​mo><​mi>​n</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle f(n)=A(n,​n)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​5a1069ffe95055bef5ab42b3d23abd3619e6cb24"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​14.957ex;​ height:​2.843ex;"​ alt="​{displaystyle f(n)=A(n,​n)}"/></​span>,​ với <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle A(n,​n)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​A</​mi><​mo stretchy="​false">​(</​mo><​mi>​n</​mi><​mo>,</​mo><​mi>​n</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle A(n,​n)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​1adad37c17f4c9d4fa4071d3587143be6740412f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​7.376ex;​ height:​2.843ex;"​ alt="​{displaystyle A(n,​n)}"/></​span>​ là <a href="​http://​vi.wikipedia.org/​wiki/​H%C3%A0m_s%E1%BB%91_Ackermann"​ title="​Hàm số Ackermann">​hàm Ackermann tăng rất nhanh. Với hầu như tất cả các giá trị thực tế của <​i>​n</​i>,​ gia trị của <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle alpha (n)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​α<​!-- &alpha; --></​mi><​mo stretchy="​false">​(</​mo><​mi>​n</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle alpha (n)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​74c1642d9e2f86b9e5c86c0f18ee5377507da827"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​4.692ex;​ height:​2.843ex;"​ alt="​{displaystyle alpha (n)}"/></​span>​ là nhỏ hơn 5.
 +</​p><​p>​Độ phức tạp tính toán trên là tối ưu: Fredman và Saks năm 1989 đã chứng minh một thuật toán hợp tìm bất kì đều cần đọc trung bình <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Omega (alpha (n))}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi mathvariant="​normal">​Ω<​!-- &Omega; --></​mi><​mo stretchy="​false">​(</​mo><​mi>​α<​!-- &alpha; --></​mi><​mo stretchy="​false">​(</​mo><​mi>​n</​mi><​mo stretchy="​false">​)</​mo><​mo stretchy="​false">​)</​mo></​mstyle></​mrow>​{displaystyle Omega (alpha (n))}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​9bfdfd41667be083aff4b7c292a9f35884b654b8"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​8.179ex;​ height:​2.843ex;"​ alt="​{displaystyle Omega (alpha (n))}"/></​span>​ ô nhớ cho mỗi thao tác.<​sup id="​cite_ref-3"​ class="​reference"><​a href="#​cite_note-3">​[3]</​sup></​p>​
 +<​h3><​span id="​Ghi_ch.C3.BA"/><​span class="​mw-headline"​ id="​Ghi_chú">​Ghi chú</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<div class="​reflist"​ style="​list-style-type:​ decimal;">​
 +<ol class="​references"><​li id="​cite_note-1"><​b>​^</​b>​ <span class="​reference-text"><​span id="​CITEREFBernard_A._Galler,​_Michael_J._Fischer"​ class="​citation">​Bernard A. Galler, Michael J. Fischer (tháng 5 1964), “An improved equivalence algorithm”,​ <​i>​Communications of the ACM</​i>​ <​b>​7</​b>​ (5), tr. 301–303</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AC%E1%BA%A5u+tr%C3%BAc+d%E1%BB%AF+li%E1%BB%87u+cho+c%C3%A1c+t%E1%BA%ADp+h%E1%BB%A3p+kh%C3%B4ng+giao+nhau&​amp;​rft.atitle=An+improved+equivalence+algorithm&​amp;​rft.au=Bernard+A.+Galler%2C+Michael+J.+Fischer&​amp;​rft.aulast=Bernard+A.+Galler%2C+Michael+J.+Fischer&​amp;​rft.btitle=Communications+of+the+ACM&​amp;​rft.date=th%C3%A1ng+5+1964&​amp;​rft.genre=bookitem&​amp;​rft.issue=5&​amp;​rft.pages=301-303&​amp;​rft.volume=7&​amp;​rft_id=http%3A%2F%2Fportal.acm.org%2Fcitation.cfm%3Fdoid%3D364099.364331&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span>​ </​span>​
 +</li>
 +<li id="​cite_note-2"><​b>​^</​b>​ <span class="​reference-text"><​span class="​citation journal">​Tarjan,​ Robert Endre (1975). “Efficiency of a Good But Not Linear Set Union Algorithm”. <​i>​Journal of the ACM</​i>​ <​b>​22</​b>​ (2): 215–225. doi:​10.1145/​321879.321884.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AC%E1%BA%A5u+tr%C3%BAc+d%E1%BB%AF+li%E1%BB%87u+cho+c%C3%A1c+t%E1%BA%ADp+h%E1%BB%A3p+kh%C3%B4ng+giao+nhau&​amp;​rft.atitle=Efficiency+of+a+Good+But+Not+Linear+Set+Union+Algorithm&​amp;​rft.au=Tarjan%2C+Robert+Endre&​amp;​rft.aufirst=Robert+Endre&​amp;​rft.aulast=Tarjan&​amp;​rft.date=1975&​amp;​rft.genre=article&​amp;​rft.issue=2&​amp;​rft.jtitle=Journal+of+the+ACM&​amp;​rft.pages=215-225&​amp;​rft.volume=22&​amp;​rft_id=http%3A%2F%2Fportal.acm.org%2Fcitation.cfm%3Fid%3D321884&​amp;​rft_id=info%3Adoi%2F10.1145%2F321879.321884&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​span>​
 +</li>
 +<li id="​cite_note-3"><​b>​^</​b>​ <span class="​reference-text"><​span id="​CITEREFM._Fredman,​M._Saks"​ class="​citation">​M. Fredman,M. Saks (tháng 5 1989), “The cell probe complexity of dynamic data structures”,​ <​i>​Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing</​i>,​ tr. 345–354</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AC%E1%BA%A5u+tr%C3%BAc+d%E1%BB%AF+li%E1%BB%87u+cho+c%C3%A1c+t%E1%BA%ADp+h%E1%BB%A3p+kh%C3%B4ng+giao+nhau&​amp;​rft.atitle=The+cell+probe+complexity+of+dynamic+data+structures&​amp;​rft.au=M.+Fredman%2CM.+Saks&​amp;​rft.aulast=M.+Fredman%2CM.+Saks&​amp;​rft.btitle=Proceedings+of+the+Twenty-First+Annual+ACM+Symposium+on+Theory+of+Computing&​amp;​rft.date=th%C3%A1ng+5+1989&​amp;​rft.genre=bookitem&​amp;​rft.pages=345-354&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span>​ "​Theorem 5: Any CPROBE(log <​i>​n</​i>​) implementation of the set union problem requires Ω(<​i>​m</​i>​ α(<​i>​m</​i>,​ <​i>​n</​i>​)) time to execute <​i>​m</​i>​ Find's and <​i>​n</​i>​−1 Union'​s,​ beginning with <​i>​n</​i>​ singleton sets."</​span>​
 +</li>
 +</​ol></​div>​
  
 +<​!-- ​
 +NewPP limit report
 +Parsed by mw1333
 +Cached time: 20181011082803
 +Cache expiry: 1900800
 +Dynamic content: false
 +CPU time usage: 0.084 seconds
 +Real time usage: 0.302 seconds
 +Preprocessor visited node count: 214/1000000
 +Preprocessor generated node count: 0/1500000
 +Post&#​8208;​expand include size: 10984/​2097152 bytes
 +Template argument size: 0/2097152 bytes
 +Highest expansion depth: 4/40
 +Expensive parser function count: 0/500
 +Unstrip recursion depth: 0/20
 +Unstrip post&#​8208;​expand size: 4951/​5000000 bytes
 +Number of Wikibase entities loaded: 0/400
 +Lua time usage: 0.027/​10.000 seconds
 +Lua memory usage: 1.49 MB/50 MB
 +-->
 +<!--
 +Transclusion expansion time report (%,​ms,​calls,​template)
 +100.00% ​  ​67.151 ​     1 B&#​7843;​n_m&#​7851;​u:​Tham_kh&#​7843;​o
 +100.00% ​  ​67.151 ​     1 -total
 + ​77.96% ​  ​52.351 ​     2 B&#​7843;​n_m&#​7851;​u:​Ch&​uacute;​_th&​iacute;​ch
 +  8.16%    5.477      1 B&#​7843;​n_m&#​7851;​u:​Ch&​uacute;​_th&​iacute;​ch_t&#​7841;​p_ch&​iacute;​
 +-->
 +
 +<!-- Saved in parser cache with key viwiki:​pcache:​idhash:​804492-0!canonical!math=5 and timestamp 20181011082803 and revision id 22079763
 + ​-->​
 +</​div><​noscript><​img src="​http://​vi.wikipedia.org/​wiki/​Special:​CentralAutoLogin/​start?​type=1x1"​ alt=""​ title=""​ width="​1"​ height="​1"​ style="​border:​ none; position: absolute;"/></​noscript></​div>​
 +
 +</​HTML>​
0129--c-u-tr-c-d-li-u-cho-c-c-t-p-h-p-kh-ng-giao-nhaula-gi.txt · Last modified: 2018/11/07 17:09 (external edit)