Հանգույցների հայտնաբերում

Համակարգչային գիտության մեջ հանգույցների հայտնաբերումը իտեգրացված ֆունկցիայի արժեքների հաջորդականության մեջ հանգույցի որոնման ալգորիթմական խնդիրն է։
Ցանկացած ƒ ֆունկցիայի համար, որն արտապատկերում է S վերջավոր բազմությունն ինքն իր վրա, և ցանկացած սկզբնական x0 արժեք S-ում, իտեգրացված ֆունկցիայի արժեքների հաջորդականությունը՝

  
    
      
        
          x
          
            0
          
        
        ,
         
        
          x
          
            1
          
        
        =
        f
        (
        
          x
          
            0
          
        
        )
        ,
         
        
          x
          
            2
          
        
        =
        f
        (
        
          x
          
            1
          
        
        )
        ,
         
        …
        ,
         
        
          x
          
            i
          
        
        =
        f
        (
        
          x
          
            i
            −
            1
          
        
        )
        ,
         
        …
      
    
    {\displaystyle x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots }
  Ի վերջո պետք է օգտագործի միևնույն արժեքն երկու անգամ. պետք է լինի մի որոշ i ≠ j այնպես, որ xi = xj։ Սա մեկ անգամ կատարվելուց հետո հաջորդականությունը պետք է շարունակվի կրկնելով xi-ից xj−1-ը ընկած արժեքների հանգույցը։ Հանգույցի հայտնաբերումը i-ի և j-ի որոնման խնդիրն է, երբ տված են ƒ-ն ու x0-ն։


== Օրինակ ==

Նկարը ցույց է տալիս ƒ ֆունկցիան, որն արտապատկերում է S = {0,1,2,3,4,5,6,7,8} բազմությունն ինքն իր վրա։ Երբ մեկը սկսվում է x0 = 2 և հաջորդաբար կիրառում է ƒ-ը, մյուսը կտեսնի հետևյալ արժեքների հաջորդականությունը

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ...Հանգույցը, որն անհրաժեշտ է հայտնաբերել հանդիսանում է այս հաջորդականության 6, 3, 1 արժեքների կրկնվող ենթահաջորդականությունը։


== Սահմանումներ ==
Դիցուք S-ը ներկայացնում է ցանկացած վերջավոր բազմություն, ƒ-ը S-ից S-ի վրա ցանկացած ֆունկցիա է, իսկ x0-ն S-ի որևէ տարր։ Ցանկացած i > 0, ենթադրենք xi = ƒ(xi−1)։ Ենթադրենք μ-ն ներկայացնում է փոքրագույն ինդեքսը այնպես, որ xμ-ն հայտնվում է անսահման հաճախ xi արժեքների բազմությունում, և դիցուք λ (հանգույցի երկարությունը) ներկայացնում է փոքրագույն ամբողջ թիվը այնպես, որ xμ = xλ+μ։ Հանգույցի հայտնաբերման խնդիրը կայանում է λ-ի և μ-ի որոնման մեջ։
Նույն խնդիրը հանդես է գալիս գրաֆների տեսությունում, կառուցելով ֆունկցիոնալ գրաֆ, որի գագաթները S բազմության տարրերն են և որը կողերը արտապատկերում են տարրերը համապատասխան ֆունկցիայի արժեքի, ինչպես պատկերված է նկարում։ Ցանկացած x0 գագաթով սկսվող հասանելի գագաթների բազմությունը ձևավորում է ենթագրաֆ կառուցվածքով նման ρ. x0-ից λ գագաթների հանգույց եղած μ երկարության ճանապարհը։


== Ալգորիթմներ ==
Եթե մուտքը տված է որպես ƒ-ի հաշվարկման պրոցեդուրա, ապա հանգույցի հայտնաբերումը կարող է հեշտորեն լուծվել օգտագործելով միայն λ+μ ֆունկցիայի կիրառություններ, պարզապես հաշվելով xi արժեքների հաջորդականությունը և օգտագործելով այնպիսի տվյալների կառուցվածք՝ ինչպիսին է հեշ-աղյուսակը, այս արժեքները պահելու և ստուգելու, թե արդյոք յուրաքանչյուր արժեք պահպանվել է արդեն։


=== Բրենտի ալգորիթմ ===
Ռիչարդ Պ. Բրենտը նկարագրել է հանգույցների հայտնաբերման այլընտրանքային ալգորիթմ, որը, ինչպես և կրիայի և ճագարի ալգորիթմը, պահանջում է միայն երկու ցուցիչ բազմության մեջ։ Ինչևէ, այն հիմնված է այլ սկզբունքի վրա. որոնում է փոքրագույն 2i-ն, որն ավելի մեծ է, քան λ-ն և μ-ն։ i = 0, 1, 2, և այլն, ալգորիթմը համեմատում է x2i−1-ը յուրաքանչյուր հաջորդիվ հաջորդականության արժեքի հետ մինչև հաջորդ երկուսի աստիճանը, դադարելով, երբ գտնում է համապատասխանություն։
Հետևյալ ծրագրային կոդը գրված Python-ով ցուցադրում է այս մեթոդը ավելի մանրամասն

Բրենտի ալգորիթմի իրականացումը C++ լեզվով (Boost գրադարանի տարբերակ).

Ինչպես և կրիայի և ճագարի ալգորիթմը, սա ևս ցուցիչ ալգորիթմ է, որն օգտագործում է O(λ+μ) թեստեր և ֆունկցիայի գնահատումներ և O(1) հիշողության տարածք։ Դժվար չէ ցույց տալ, որ ֆունկցիայի գնահատումների քանակը երբեք չի գերազանցի Ֆլոյդի ալգորիթմինը։ Բրենտը պնդում է, որ միջին հաշվով, նրա հանգույցների հայտնաբերման ալգորիթմը աշխատում է 36% ավելի արագ, քան Ֆլոյդինը և որ արագությունը գերազանցում է Փոլլարդի ռո ալգորիթմը մոտ 24%-ով։