Dövrün tapılması
İnformatikada dövrün tapılması iterativ funksiyalar ardıcıllığında dövrün tapılması üçün alqoritmik problemdir (alqoritmdir).
Sonlu
S
{\displaystyle S}
çoxluğunun özünə uyğun gələn, hər hansı bir
f
{\displaystyle f}
funksiyası üçün, və eyni zamanda
S
{\displaystyle S}
çoxluğundan olan
x
0
{\displaystyle x_{0}}
başlanğıc nöqtəsi üçün iterativ funksiyalar ardıcıllığı aşağıdakı kimidir:
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 }
Nəticə etibarilə burada funksiyanın eyni qiyməti aldığı cütlük olmalıdır, yəni elə bir
i
{\displaystyle i}
və
j
{\displaystyle j}
cütlüyü olmalıdır ki,
x
i
=
x
j
{\displaystyle x_{i}=x_{j}}
şərti ödənmiş olsun. Bu baş verən andan ardıcıllıq dövri olaraq
x
i
{\displaystyle x_{i}}
və
x
j
−
1
{\displaystyle x_{j-1}}
aralığında eyni ardıcıllığı təkrarlayacaqdır. Dövrün tapılması məsələsi
f
{\displaystyle f}
və
x
0
{\displaystyle x_{0}}
-a görə
i
{\displaystyle i}
və
j
{\displaystyle j}
qiymətlərinin tapılmasıdır.
Bu məsələnin həlli üçün müxtəlif alqoritmlər mövcuddur. Məsələn, Floydun "bağa və dovşan alqoritmi" iki göstəricinin müxtəlif sürətlərlə hərəkət etdirilməsi və onlarn hansısa bir nöqtədə rastlaşmasına əsaslanır. Brentin alqoritmi isə eksponensial axtarış üsuluna əsaslanıb. Hər iki alqoritm iki göstəricidən istifadə edir. Yaddaşı daha çox istismar etməklə hesablamaları bir qədər azaldan digər müxtəlif alqoritmlər də mövcuddur.
Dövrün tapılması alqoritminin tətbiqi müxtəlifdir, nümunə olaraq psevdo-təsadüfi ədədlər generatoru, kriptoqrafik həş funksiyalar, ədədi üsullar üçün alqoritmlər, kompüter proqramlarında və konfiqurasiyalarında sonsuz dövrlərin tapılması və s.
