Кіріспе
Алгоритмдік мәселе: итерацияланған функциялар
iterated functions
In computer science, cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values. For any function f that maps a finite set S to itself, and any initial value x0 in S, the sequence of iterated function values
must eventually use the same value twice: there must be some pair of distinct indices i and j such that 1=xi = xj. Once this happens, the sequence must continue periodically, by repeating the same sequence of values from xi to xj − 1. Cycle detection is the problem of finding i and j, given f and x0. Several algorithms are known for finding cycles quickly and with little memory. Robert W. Floyd's tortoise and hare algorithm moves two pointers at different speeds through the sequence of values until they both point to equal values. Alternatively, Brent's algorithm is based on the idea of exponential search. Both Floyd's and Brent's algorithms use only a constant number of memory cells, and take a number of function evaluations that is proportional to the distance from the start of the sequence to the first repetition. Several other algorithms trade off larger amounts of memory for fewer function evaluations. The applications of cycle detection include testing the quality of pseudorandom number generators and cryptographic hash functions, computational number theory algorithms, detection of infinite loops in computer programs and periodic configurations in cellular automata, automated shape analysis of linked list data structures, and detection of deadlocks for transactions management in DBMS.
Компьютерлік ғылымда циклді анықтау немесе циклді табу – итерацияланған функция мәндерінің тізбегінде циклді табудың алгоритмдік мәселесі. Кез келген f функциясы үшін, ол шекті жиын S-ті өзіне бейімдейтін болса, және S жиынындағы кез келген бастапқы x0 мәні үшін, итерацияланған функция мәндерінің тізбегі әрине бір мәнді екі рет пайдалануы керек: i және j әртүрлі индекстердің жұбы болуы керек, яғни xi = xj. Мұндай жағдай туғаннан кейін, тізбек xi-ден xj-1-ге дейінгі мәндердің тізбегін қайталап, кезеңдік түрде жалғасуы керек. Циклді анықтау – f және x0 берілген жағдайда i және j индекстерін табу мәселесі. Циклдерді жылдам және аз жадты пайдалана отырып табуға арналған бірнеше алгоритмдер белгілі. Роберт В. Флойдтың «тасбақа мен қоян» алгоритмі екі көрсеткішті әртүрлі жылдамдықпен мәндер тізбегі бойынша қозғалысқа жібереді, олар екі мән тең болағанша. Балама ретінде, Бренттің алгоритмі экспоненциалды іздеу идеясына негізделген. Флойд және Брент алгоритмдері тек тұрақты көлемдегі жад ұяларын пайдаланады және функцияны бағалау саны тізбектің басынан бастап алғашқы қайталануға дейінгі қашықтыққа пропорционалды болады. Кейбір басқа алгоритмдер функцияны бағалау санын азайту үшін жадтың үлкен көлемін пайдалануға дайын. Циклді анықтаутың қолданылу салаларына псевдорандомдық сандар генераторларының және криптографиялық хэш-функциялардың сапасын тексеру, есептеулік сан теориясының алгоритмдері, компьютерлік бағдарламалардағы шексіз циклдерді және жасушалық автоматтарындағы кезеңдік конфигурацияларды анықтау, байланыстырылған тізімдер деректерінің автоматтандырылған пішіндегі талдауы және ДБҚЖ-да транзакцияларды басқару кезіндегі тұйықтарды анықтау кіреді.
iterated functions
In computer science, cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values. For any function f that maps a finite set S to itself, and any initial value x0 in S, the sequence of iterated function values
must eventually use the same value twice: there must be some pair of distinct indices i and j such that 1=xi = xj. Once this happens, the sequence must continue periodically, by repeating the same sequence of values from xi to xj − 1. Cycle detection is the problem of finding i and j, given f and x0. Several algorithms are known for finding cycles quickly and with little memory. Robert W. Floyd's tortoise and hare algorithm moves two pointers at different speeds through the sequence of values until they both point to equal values. Alternatively, Brent's algorithm is based on the idea of exponential search. Both Floyd's and Brent's algorithms use only a constant number of memory cells, and take a number of function evaluations that is proportional to the distance from the start of the sequence to the first repetition. Several other algorithms trade off larger amounts of memory for fewer function evaluations. The applications of cycle detection include testing the quality of pseudorandom number generators and cryptographic hash functions, computational number theory algorithms, detection of infinite loops in computer programs and periodic configurations in cellular automata, automated shape analysis of linked list data structures, and detection of deadlocks for transactions management in DBMS.
Мысал
Суретте f функциясы 1=S = {0,1,2,3,4,5,6,7,8} жиынын өзіне бейімдейді. Егер 1=x0 = 2 нүктесінен бастап, f функциясын қайталап қолдансақ, 2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1 мәндерінің тізбегін көреміз. Осы мәндер тізбегіндегі цикл 6, 3, 1 болып табылады.
2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1,
The cycle in this value sequence is 6, 3, 1.
Анықтамалар
S кез келген шекті жиын болсын, f – S-тен өзіне кез келген функция болсын, ал x0 – S-тің кез келген елемі болсын. I > 0 үшін xi = f(xi − 1) болсын. μ – xi мәндерінің тізбегінде xμ мәні шексіз көп рет қайталануын қамтамасыз ететін ең кіші индекс болсын, ал λ (цикл ұзындығы) – 1=xμ = xλ + μ шартын қанағаттандыратын ең кіші оң бүтін сан болсын. Циклды анықтау мәселесі – λ және μ табу есебі болып табылады. Осы мәселені функционалдық граф (яғни, әрбір төбесінен бір ғана шығу жиегі бар бағытталған граф) құру арқылы теориялық тұрғыдан қарастыруға болады, мұнда төбелер S элементтерінен, ал жиектер элементті тиісті функциялық мәніне бейнелейді, суретте көрсетілгендей. Бастапқы төбе x0-дан қол жетімді төбелер жиынтығы грек әрпі rho (ρ) пішініне ұқсас кіші графты құрайды: x0-дан λ төбелі циклға дейінгі ұзындығы μ болатын жол.
Қолданбалар
Циклді анықтау көптеген қолданбаларда қолданылады. Псевдокездейі сан генераторының циклының ұзындығын анықтау оның беріктігін өлшеудің бір тәсілі болып табылады. Бұл Кнут Флойд әдісін сипаттағанда айтқан қолданба. және оның дискретті логарифмдер мәселесі бойынша кенгуру алгоритмі. Криптографиялық қолданбаларда, кейбір криптографиялық функция ƒ арқылы бірдей xμ мәніне бейімделген xμ−1 және xλ+μ−1 екі түрлі мәнін табу мүмкіндігі ƒ-ның осалдығын көрсетеді. Мысалы, Квискватер және Делескайль ДЭС-ке шабуыл жасау үшін циклді анықтау алгоритмдерін пайдаланады. Бұл техника криптографиялық хэш-функциядағы қақтығысты табу үшін де қолданылуы мүмкін. Циклді анықтау белгілі бір компьютерлік бағдарламаларда шексіз циклдерді анықтаудың бір жолы ретінде көмектесе алады. Ұялы автоматтардың симуляцияларындағы кезеңдік конфигурациялар автоматтардың күйлерінің тізбегіне циклді анықтау алгоритмдерін қолдану арқылы табылуы мүмкін. Common Lisp-те S өрнегі принтері *print circle* айнымалысының бақылауымен дөңгелек тізім құрылымын анықтап, оны ықшам түрде басып шығарады. Теске есептеулік топтар теориясындағы қолданбаларды сипаттайды: оның генераторлары жиынтығынан Абельдік топтың құрылымын анықтау. Калиски және басқалардың криптографиялық алгоритмдерін белгісіз топтың құрылымын анықтауға талпыну ретінде қарастыруға болады. Уильям Каханға сілтеме жасай отырып, аспан механикасының компьютерлік симуляциясына қолданылуын қысқаша айтады. Бұл қолданбада орбиталық жүйенің фазалық кеңістігіндегі циклді анықтау жүйенің симуляцияның дәлдігі шегінде периодты екенін анықтау үшін қолданылуы мүмкін. Мандельброт жиынының фракталдарын жасауда бейне жасау жылдамдығын арттыру үшін кейбір орындау техникалары қолданылады. Олардың бірі "периодты тексеру" деп аталады, ол нүктелік орбитадағы циклдарды табудан тұрады. Бұл мақалада "периодты тексеру" техникасы сипатталған. Сіз басқа түсіндірмені мұнда таба аласыз. Бұл техниканы іске асыру үшін кейбір циклді анықтау алгоритмдерін іске асыру қажет.