Xem mã nguồn của Phát hiện chu trình

{{Chú thích trong bài|date=tháng 7/2021}}
Trong [[Khoa học máy tính]], bài toán '''phát hiện chu trình''' hay '''tìm chu trình''' là bài tìm thuật toán tìm vòng lặp trong một chuỗi giá trị hàm.

Bất kỳ [[Hàm số|hàm]] <math>f</math> nào ánh xạ một [[Tập hợp hữu hạn|tập hữu hạn]] <math>S</math> tới chính nó, và bất kỳ giá trị ban đầu <math>x_0</math> trong <math>S</math>, chuỗi các giá trị hàm

: <math> x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots</math>

phải có một giá trị xuất hiện hai lần: có một số cặp ''i'' và ''j'' phân biệt sao cho <math>x_i = x_j</math>. Khi điều này xảy ra, chuỗi tiếp tục chu trình một cách định kỳ, bằng cách lặp lại chuỗi giá trị từ <math>x_i</math> tới <math>x_{j-1}</math>. Tìm chu trình là bài toán tìm ''i'' và ''j'' khi biết <math>f</math> và <math>x_0</math>.

Rất nhiều thuật toán tìm chu trình nhanh và dùng ít bộ nhớ được biết. [[Thuật toán rùa và thỏ]] của [[Robert W.Floyd]] di chuyển hai con trỏ với vận tốc khác nhau qua chuỗi cho đến khi chúng cùng chỉ một giá trị. Lựa chọn khác, ta có thuật toán của Brent dựa trên ý tưởng tìm kiếm theo cấp số mũ. Cả hai thuật toán trên chỉ dùng một số lượng cố định bộ nhớ và tính giá trị hàm một lượng tỷ lệ thuận với khoảng cách tính từ xuất phát của chuỗi đến giá trị lặp đầu tiên. Các thuật toán khác đổi bộ nhớ lớn hơn để tính ít hơn số lần tính giá trị hàm.

Ứng dụng của phát hiện chu trình bao gồm thử nghiệm chất lượng của [[bộ sinh số giả ngẫu nhiên]] và [[hàm băm mật mã học]], các thuật toán trong [[lý thuyết số tính toán]], phát hiện vòng lặp vô hạn trong các chương trình máy tính và các cấu hình tuần hoàn trong [[tế bào tự động hóa]].

== Thí dụ ==
[[Tập tin:Functional_graph.svg|nhỏ|Một hàm từ và đến tập {0,1,2,3,4,5,6,7,8} và đồ thị hàm tương ứng]]
Hình bên cho biết một hàm <math>f</math> ánh xạ tập <math>S = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}</math> tới chính nó. Nếu ta xuất phát từ <math>x_0 = 2</math> và liên tục áp dụng hàm <math>f</math>, ta sẽ được chuỗi sau

: {{Math|2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....}}

Chu trình trong chuỗi giá trị này là 6, 3, 1.

== Định nghĩa ==
Gọi {{Mvar|S}} là tập hữu hạn bất kỳ, {{Mvar|f}}  là hàm bất kỳ từ {{Mvar|S}} ánh xạ vào chính nó và {{Math|''x''<sub>0</sub>}} là phần tử bất kỳ trong {{Mvar|S}}. Với bất kỳ {{Math|''i'' > 0}}, đặt {{Math|1=''x<sub>i</sub>'' = ''f''(''x''<sub>''i'' &minus; 1</sub>)}}. Gọi {{Mvar|μ}} là chỉ số nhỏ nhất sao cho giá trị {{Math|''x''<sub>''μ''</sub>}} thường xuyên lặp lại vô hạn trong chuỗi giá trị {{Math|''x<sub>i</sub>''}} và đặt {{Mvar|λ}} (độ dài vòng lặp) là số nguyên dương nhỏ nhất sao cho {{Math|1=''x''<sub>''μ''</sub> = ''x''<sub>''λ'' + ''μ''</sub>}}. Bài toán phát hiện chu trình yêu cầu tìm hai giá trị {{Mvar|λ}} và {{Mvar|μ}}.<ref>{{citation|title=Algorithmic Cryptanalysis|first=Antoine|last=Joux|publisher=CRC Press|year=2009|isbn=9781420070033|page=223|url=https://books.google.com/books?id=buQajqt-_iUC&pg=PA223}}.</ref>

Ta có thể xét bài toán này bằng [[lý thuyết đồ thị]], bằng cách xây một [[đồ thị hàm]] (một [[đồ thị có hướng]] mà mỗi đỉnh có một cung đi ra) trong đó mỗi đỉnh là một phần tử của S, và các cung đi ra ánh xạ phần tử giá trị hàm tương ứng, như hình trên.

== Các thuật toán ==
Nếu input được đưa như một thủ tục con là để tìm f, bài toán có thể giải đơn giản dùng chỉ <math>\lambda + \mu</math> lần tính hàm, bằng cách tính chuỗi giá trị <math>x_i</math> dùng một cấu trúc dữ liệu như [[bảng băm]] để lưu các giá trị này và kiểm tra xem các giá trị sau đã được lưu chưa. Tuy nhiên, độ phức tạp bộ nhớ tỉ lệ thuận với <math>\lambda + \mu</math>, lớn không cần thiết. Do đó nghiên cứu trong khu vực này tập trung vào hai mục tiêu: dùng ít bộ nhớ hơn thuật toán trên và tìm thuật toán con trỏ dùng ít số lần kiểm tra hơn.

{{Anchor|Tortoise and hare}}
===Thuật toán rùa và thỏ của Floyd===
[[Tập tin:Tortoise and hare algorithm.svg|thumb|upright=1.25|Thuật toán rùa và thỏ của Floyd, áp dụng với chuỗi 2, 0, 6, 3, 1, 6, 3, 1,...]]
'''Thuật toán tìm chu trình của Floyd''' là thuật toán con trỏ dùng hai con trỏ, di chuyển trên cùng một chuỗi với tốc độ khác nhau. Nó cũng được gọi là "thuật toán rùa và thỏ", dựa trên câu chuyện ngụ ngôn của Aesop.

Thuật toán được đặt tên theo [[Robert W. Floyd]], người được công nhận bởi [[Donald Knuth]].<ref name="knuth">{{citation|first=Donald E.|last=Knuth|authorlink=Donald Knuth|title=The Art of Computer Programming, vol. II: Seminumerical Algorithms|publisher=Addison-Wesley|year=1969|page=7, exercises 6 and 7}}</ref><ref>''Handbook of Applied Cryptography,'' by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, [https://books.google.com/books?id=nSzoG72E93MC&pg=PA125 p. 125], describes this algorithm and others</ref> Tuy nhiên, thuật toán không xuất hiện trong các bài của Floyd, và do đó đây có thể là quy kết nhầm: Floyd mô tả các thuật toán liệt kê toàn bộ các chu trình đơn trong một [[đồ thị có hướng]] trong tờ nghiên cứu năm 1967,<ref>{{citation|last=Floyd|first=R.W.|authorlink=Robert W. Floyd|title=Nondeterministic Algorithms|journal=J. ACM|pages=636–644|volume=14|issue=4|year=1967|doi=10.1145/321420.321422|s2cid=1990464}}</ref> nhưng tờ báo đó không mô tả bài toán tìm chu trình với đồ thị hàm ở đây. Thậm chí, theo lời của Knuth (vào năm 1969), quy nó về Floyd mà không trích dẫn.<ref>''The Hash Function BLAKE,'' by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), [https://books.google.com/books?id=nhPmBQAAQBAJ&pg=PA21 p. 21], footnote 8</ref>

Yếu tố quan trọng trong thuật toán như sau. Nếu có một chu trình, thì, với bất kỳ {{math|''i'' ≥ ''μ''}} và {{math|''k'' ≥ 0}}, {{math|1=''x<sub>i</sub>'' = ''x''<sub>''i'' + ''kλ''</sub>}}, với {{mvar|λ}} là độ dài vòng lặp cần tìm và {{mvar|μ}} là vị trí của phần tử đầu tiên trong chu trình. Dựa trên đây, ta có thể chứng minh {{math|1=''i'' = ''kλ'' ≥ ''μ''}} với một vài số {{math|''k''}} khi và chỉ khi {{math|1=''x<sub>i</sub>'' = ''x''<sub>2''i''</sub>}}. Như vậy, thuật toán chỉ cần kiểm tra các giá trị lặp lại dưới dạng đặc biệt trên, với một con trỏ để cách gấp đôi từ vị trí xuất phát, để tìm chu kỳ {{mvar|ν}} cho một lần lặp là bội của {{mvar|λ}}. Một khi {{mvar|ν}} được tìm thấy, thuật toán tìm ngược lại từ lúc ban đầu để tìm giá trị đầu tiên {{math|''x''<sub>''μ''</sub>}} trong chuỗi, khi biết rằng {{mvar|λ}} là ước của {{mvar|ν}} và do đó {{math|1=''x''<sub>''μ''</sub> = ''x''<sub>''μ'' + ''v''</sub>}}.  Cuối cùng, một khi {{mvar|μ}} đã được biết, bài toán trở nên đơn giản trong việc tìm độ dài {{mvar|λ}} cho chu trình lặp lại ngắn nhất, bằng việc tìm vị trí đầu tiên của {{math|''μ'' + ''λ''}} sao cho {{math|1=''x''<sub>''μ'' + ''λ''</sub> = ''x''<sub>''μ''</sub>}}.

Thuật toán do đó dùng hai con trỏ, con trỏ đầu tiên (con rùa) nằm tại {{math|''x<sub>i</sub>''}}, và con còn lại (con trỏ) nằm tại {{math|''x''<sub>2''i''</sub>}}. Trong mỗi bước của thuật toán, tăng {{mvar|i}} bởi một, di chuyển con rùa một bước phía trước và con thỏ hai bước phía trước trong chuỗi, rồi so sánh giá trị chuỗi ở hai con trỏ này. Giá trị nhỏ nhất của {{math|''i'' &gt; 0}} sao cho rùa và thỏ đều trỏ vào cùng một giá trị là giá trị {{mvar|ν}} cần tìm.

Đoạn code [[python (ngôn ngữ lập trình)|Python]] sau mô tả ý tưởng thuật toán trên:
<!--{{hidden begin|showhide=left|title|Nhấp vào để xem đoạn mã}}-->
<syntaxhighlight lang="python">
def floyd(f, x0):
    # Main phase of algorithm: finding a repetition x_i = x_2i.
    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then,
    # at some point, the distance between them will be
    # divisible by the period λ.
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
  
    # At this point the tortoise position, ν, which is also equal
    # to the distance between hare and tortoise, is divisible by
    # the period λ. So hare moving in circle one step at a time, 
    # and tortoise (reset to x0) moving towards the circle, will 
    # intersect at the beginning of the circle. Because the 
    # distance between them is constant at 2ν, a multiple of λ,
    # they will agree as soon as the tortoise reaches index μ.

    # Find the position μ of first repetition.    
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        mu += 1
 
    # Find the length of the shortest cycle starting from x_μ
    # The hare moves one step at a time while tortoise is still.
    # lam is incremented until λ is found.
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu
</syntaxhighlight>

Thuật toán chỉ dùng con trỏ để lưu và sao chép giá trị, tính giá trị hàm và kiểm tra bằng nhau, do đó nó thỏa mãn yêu cầu của thuật toán con trỏ.Thuật toán dùng {{math|''O''(''λ'' + ''μ'')}} số phép tính trên, và {{math|''O''(1)}} bộ nhớ.<ref>{{harvtxt|Joux|2009}}, Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225–226.</ref>
<!--{{hidden end}}-->

=== Thuật toán của Brent ===

[[Richard Brent (nhà khoa học)|Richard P. Brent]] mô tả một thuật toán tìm chu trình khác, giống thuật toán rùa và con thỏ, chỉ cần hai con trỏ để duyệt dãy số.<ref name="brent">{{citation|first=R. P.|last=Brent|authorlink=Richard Brent (scientist)|title=An improved Monte Carlo factorization algorithm|journal=[[BIT Numerical Mathematics ]]|volume=20|year=1980|pages=176–184|url=http://wwwmaths.anu.edu.au/~brent/pd/rpb051i.pdf|doi=10.1007/BF01933190|issue=2|s2cid=17181286|access-date=2021-09-09|archive-date=2009-09-24|archive-url=https://web.archive.org/web/20090924082516/http://wwwmaths.anu.edu.au/~brent/pd/rpb051i.pdf}}.</ref> Tuy nhiên, nó dựa theo nguyên tắc khác: tìm giá trị [[lũy thừa bậc hai]] nhỏ nhất {{math|2<sup>''i''</sup>}} mà lớn hơn cả {{mvar|λ}} và {{mvar|μ}}. Với {{math|1=''i'' = 0, 1, 2, ...}}, thuật toán so sánh {{math|''x''<sub>2<sup>''i''</sup>&minus;1</sub>}} với mỗi giá trị phần tử tiếp theo cho đến khi gặp lũy thừa bậc hai tiếp theo, dừng khi nó gặp một cặp bằng nhau. Thuật toán có hai ưu thế so với thuật toán rùa và con thỏ: nó tìm đúng và trực tiếp giá trị {{mvar|λ}} của chu trình, thay vì phải tìm nó trong đoạn mã sau, và các bước của nó chỉ cần một phép tính  {{mvar|f}}  hơn là 3.<ref>{{harvtxt|Joux|2009}}, Section 7.1 .2, Brent's cycle-finding algorithm, pp. 226–227.</ref>

Đoạn code python sau mô tả lại ý tưởng trên.
<syntaxhighlight lang="python">
def brent(f, x0):
    # main phase: search successive powers of two
    power = lam = 1
    tortoise = x0
    hare = f(x0)  # f(x0) is the element/node next to x0.
    while tortoise != hare:
        if power == lam:  # time to start a new power of two?
            tortoise = hare
            power *= 2
            lam = 0
        hare = f(hare)
        lam += 1

    # Find the position of the first repetition of length λ
    tortoise = hare = x0
    for i in range(lam):
    # range(lam) produces a list with the values 0, 1, ... , lam-1
        hare = f(hare)
    # The distance between the hare and tortoise is now λ.

    # Next, the hare and tortoise move at same speed until they agree
    mu = 0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
 
    return lam, mu
</syntaxhighlight>

Giống thuật toán rùa và thỏ, đây là thuật toán con trỏ dùng {{math|''O''(''λ'' + ''μ'')}} lần kiểm tra và tính hàm cùng với {{math|''O''(1)}} bộ nhớ. Đồng thời cũng không quá khó để chứng minh rằng số lần tính hàm không bao giờ cao hơn số lần tính trong thuật toán của Floyd. Brent cho rằng, trên trung bình, thuật toán tìm chu trình của ông chạy khoảng 36% nhanh hơn so với cái của Floyd và nó đẩy tốc độ cho [[thuật toán Pollard rho]] bởi tầm 24%. Ông cũng xét [[phân tích trung bình]] cho phiên bản ngẫu nhiên của thuật toán trong đó dãy chỉ số xét bởi con trỏ chậm hơn không phải lũy thừa bậc hai như thường, mà là bội ngẫu nghiên của lũy thừa bậc hai. Mặc dù ông định áp dụng chủ yếu cho các thuật toán phân tích số nguyên, Brent cũng có xét tới các ứng dụng cho việc kiểm nghiệm các bộ sinh số giả ngẫu nhiên.<ref name="brent"/>

==Tham khảo==
{{tham khảo}}

[[Thể loại:Thuật toán tổ hợp]]