Cycle detection (original) (raw)
Le problème algorithmique de détection de cycle consiste à trouver un cycle dans la suite des valeurs d'une fonction itérée. Il existe plusieurs algorithmes pour ce problème comme l'algorithme du lièvre et de la tortue et l'algorithme de Brent. Ce problème apparait dans des contextes divers : les générateurs de nombres pseudo-aléatoires, la théorie des nombres, la cryptographie, les automates cellulaires, etc.
| Property | Value |
|---|---|
| dbo:abstract | في علوم الكمبيوتر، تحديد الحلقة أو إيجاد الحلقة عبارة عن مشكلة خوارزمية لايجاد حلقة في تسلسل لقيم مكررة. بالنسبة لأي دالة f تقوم بربط مجموعة منتهية S بذاتها، وبأي قيمة أولية x0في S ، فإن تسلسل قيم الدوال المكررة كالتالي يجب في النهاية استخدام نفس القيمة مرتين: يجب أن يكون هناك زوج من المؤشرات المميزة i و j بحيث يكون xi = xjيجب أن يستمر التسلسل بشكل دوري، من خلال تكرار نفس سلسة القيم من xiإلى xj − 1. تحديد الحلقة هو مشكلة إيجاد i و j، إذا كان لدينا فرضاً f و x0. يوجد العديد من الخوارزميات المعروفة لتحديد الحلقات بسرعة وبقليل من الذاكرة. تحرك خوارزمية السلحفاة والأرنب روبرت دبليو فلويد مؤشرين بسرعات مختلفة من خلال سلسلة من القيم حتى يشير كلاهما إلى قيم متساوية. عوضاً عن ذلك، تعتمد خوارزمية برينت Brent على فكرة البحث الأسي. تستخدم كل من خوارزميات فلويد وبرنت عددًا ثابتًا من خلايا الذاكرة، وتأخذ عددًا من تقييمات الدوال التي تتناسب مع المسافة من بداية السلسلة إلى التكرار الأول. تقوم العديد من الخوارزميات بمقايضة كميات أكبر من الذاكرة من أجل تقييم أقل للدوال. تشمل تطبيقات التحديد الحلقي اختبار جودة مولدات الأرقام العشوائية الزائفة (شبه عشوائية) و دوال هاش للتشفير، وخوارزميات نظرية العدد الحاسوبي، والكشف عن الحلقات اللانهائية في برامج الكمبيوتر والتكوينات الدورية في الأتمتة الخلوية، وتحليل الشكل الآلي لهياكل بيانات القائمة المتصلة . (ar) Hledání cyklu funkce je úloha z oblasti matematické informatiky. Předpokládá zadanou funkci na konečné množině a posloupnost hodnot Protože se jedná o posloupnost na konečné množině, musí se časem nějaká hodnota zopakovat, a od té chvíle se bude jednat o , neboť od dané zopakované hodnoty jsou odvozeny stejně i všechny hodnoty následující. Cílem úlohy je zjistit, od jaké položky je posloupnost periodická a jakou má délku periody. Délka periody se tradičně v tomto kontextu označuje řeckým písmenem λ, délka řeckým písmenem μ. Algoritmy úlohu řešící jsou aplikovány například pro testování kvality generátorů pseudonáhodných čísel a kryptografických hašovacích funkcí, detekce nekonečných cyklů v počítačových programech a stavech celulárních automatů, případně i nalezení cyklu v lineárních seznamech. (cs) 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 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 for finding cycles quickly and with little memory are known. 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. (en) Le problème algorithmique de détection de cycle consiste à trouver un cycle dans la suite des valeurs d'une fonction itérée. Il existe plusieurs algorithmes pour ce problème comme l'algorithme du lièvre et de la tortue et l'algorithme de Brent. Ce problème apparait dans des contextes divers : les générateurs de nombres pseudo-aléatoires, la théorie des nombres, la cryptographie, les automates cellulaires, etc. (fr) In informatica, il rilevamento dei cicli è un problema algoritmico riguardante la ricerca di un ciclo in una sequenza di valori di funzione iterata. Per ogni funzione ƒ che mappa un insieme finito S su se stesso, ed ogni valore iniziale x0 in S, la sequenza dei valori della funzione iterata. deve infine usare lo stesso valore 2 volte: ci deve essere qualcosa i ≠ j come xi = xj. Una volta che ciò accade, la sequenza deve continuare dal ciclo ripetuto di valori da xi a xj-1.La rilevazione dei cicli è il problema di trovare i e j dato ƒ e x0. (it) В інформатиці виявлення циклу — це алгоритмічна задача пошуку циклу в послідовності ітераційних значень функції. Для будь-якої функції f, яка відображає скінченну множину S на саму себе, і будь-якого початкового значення x0 з S, послідовність ітераційних значень функції зрештою буде двічі використовувати одне й те ж значення, тобто знайдеться пара різних індексів i та j таких, що xi = xj. Як тільки це трапиться, послідовність буде продовжуватися, повторюючи ту саму послідовність значень від xi до xj − 1. Виявлення циклу — це задача пошуку i та j для заданих f та x0. Відомо кілька алгоритмів швидкого знаходження циклів з незначним використанням пам'яті. Алгоритм черепахи та зайця Роберта У. Флойда переміщує два вказівника з різною швидкістю по послідовності значень, поки обидва не вкажуть на рівні значення. Алгоритм Брента базується на ідеї . Алгоритми Флойда і Брента використовують сталий об'єм пам'яті, а кількість разів обчислення значеннь функції пропорційна відстані від початку послідовності до першого повторення. Кілька інших алгоритмів використовують більший об'єм пам'яті для меншої кількості обчислень значень функції. Серед застосунків виявлення циклів є перевірка якості генераторів псевдовипадкових чисел та криптографічних хеш-функцій, алгоритмів обчислювальної теорії чисел, виявлення нескінченних циклів у комп'ютерних програмах та періодичних конфігурацій у клітинних автоматах, автоматизований в таких структурах даних, як зв'язаний список, взаємне блокування при обробці транзакцій в СУБД. (uk) Нахождение цикла — алгоритмическая задача поиска цикла в последовательности значений . Для любой функции f, отображающей конечное множество S в себя, и для любого начального значения x0 из S последовательность итеративных значений функции: должна в конечном счёте использовать одно значение дважды, то есть должна существовать такая пара индексов i и j, что xi = xj. Как только это случится, последовательность будет продолжаться периодически, повторяя ту же самую последовательность значений от xi до xj − 1. Нахождение цикла — это задача поиска индексов i и j при заданной функции f и начальном значении x0. Известно несколько алгоритмов поиска цикла быстро и при малой памяти. Алгоритм «черепахи и зайца» Флойда передвигает два указателя с различной скоростью через последовательность значений, пока не получит одинаковые значения. Другой алгоритм, алгоритм Брента, основан на идее . Оба алгоритма, Флойда и Брента, используют только фиксированное число ячеек памяти, и число вычислений функции пропорционально расстоянию от стартовой точки до первой точки повторения. Некоторые другие алгоритмы используют большее количество памяти, чтобы получить меньшее число вычислений значений функции. Задача нахождения цикла используется для проверки качества генераторов псевдослучайных чисел и криптографических хеш-функций, в алгоритмах , для определения бесконечных циклов в компьютерных программах и периодических конфигураций клеточных автоматов, а также для автоматического связных списков. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Functional_graph.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.gabrielnivasch.org/fun/cycle-detection http://www.inwap.com/pdp10/hbaker/hakmem/flows.html https://web.archive.org/web/20160304043822/http:/www.siafoo.net/algorithm/11 https://web.archive.org/web/20160313063357/http:/www.siafoo.net/algorithm/10 http://math.bu.edu/DYSYS/FRACGEOM/node1.html%23SECTION00010000000000000000 http://wiki.c2.com/%3FTortoiseAndHare |
| dbo:wikiPageID | 670279 (xsd:integer) |
| dbo:wikiPageLength | 31563 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120501293 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_of_two dbr:Python_(programming_language) dbr:Robert_W._Floyd dbr:Ron_Rivest dbr:Bill_Gosper dbr:Algorithm dbc:Fixed_points_(mathematics) dbr:Rho_(letter) dbr:Cycle_(graph_theory) dbr:Cycle_detection dbr:Deadlock dbr:Infinite_loop dbr:Integer_factorization dbr:Common_Lisp dbr:Cryptographic_hash_function dbr:Cryptography dbr:Oscillator_(cellular_automaton) dbr:Function_(mathematics) dbr:Greatest_common_divisor dbr:Linear_congruential_generator dbr:Mandelbrot_Set dbr:Computational_group_theory dbr:Computational_number_theory dbr:Computer_program dbr:Computer_science dbr:Computer_simulation dbr:Phase_space dbr:Pointer_(computer_programming) dbr:Pollard's_kangaroo_algorithm dbr:Burt_Kaliski dbc:Combinatorial_algorithms dbr:Data_Encryption_Standard dbr:Data_structure dbr:William_Kahan dbr:Hash_collision dbr:Linked_list dbr:Alan_Sherman dbr:Database dbr:Finite_set dbr:Number_theory dbr:Celestial_mechanics dbr:Cellular_automaton dbr:Directed_graph dbr:Discrete_logarithm dbr:Graph_theory dbr:S-expression dbr:Mathematical_folklore dbr:Pseudorandom_number_generator dbr:Reachability dbr:Hash_table dbr:Iterated_function dbr:Abelian_group dbc:Articles_with_example_Python_(programming_language)_code dbr:The_Tortoise_and_the_Hare dbr:Stack_(data_structure) dbr:Donald_Knuth dbr:Average-case_complexity dbr:Pollard's_rho_algorithm dbr:Sequence dbr:Exponential_search dbr:Pointer_machine dbr:Periodic_sequence dbr:Space_complexity dbr:Pointer_algorithm dbr:Transaction_manager dbr:Richard_Brent_(scientist) dbr:Functional_graph dbr:Pollard_rho_algorithm dbr:Shape_analysis_(software) dbr:File:Functional_graph.svg dbr:File:Tortoise_and_hare_algorithm.svg dbr:Wikibooks:Fractals/Iterations_in_the_complex_plane/Mandelbrot_set/mandelbrot |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Anchor dbt:Harvtxt dbt:Math dbt:Mvar dbt:Reflist dbt:Technical |
| dct:subject | dbc:Fixed_points_(mathematics) dbc:Combinatorial_algorithms dbc:Articles_with_example_Python_(programming_language)_code |
| rdf:type | yago:WikicatCombinatorialAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment | Le problème algorithmique de détection de cycle consiste à trouver un cycle dans la suite des valeurs d'une fonction itérée. Il existe plusieurs algorithmes pour ce problème comme l'algorithme du lièvre et de la tortue et l'algorithme de Brent. Ce problème apparait dans des contextes divers : les générateurs de nombres pseudo-aléatoires, la théorie des nombres, la cryptographie, les automates cellulaires, etc. (fr) In informatica, il rilevamento dei cicli è un problema algoritmico riguardante la ricerca di un ciclo in una sequenza di valori di funzione iterata. Per ogni funzione ƒ che mappa un insieme finito S su se stesso, ed ogni valore iniziale x0 in S, la sequenza dei valori della funzione iterata. deve infine usare lo stesso valore 2 volte: ci deve essere qualcosa i ≠ j come xi = xj. Una volta che ciò accade, la sequenza deve continuare dal ciclo ripetuto di valori da xi a xj-1.La rilevazione dei cicli è il problema di trovare i e j dato ƒ e x0. (it) في علوم الكمبيوتر، تحديد الحلقة أو إيجاد الحلقة عبارة عن مشكلة خوارزمية لايجاد حلقة في تسلسل لقيم مكررة. بالنسبة لأي دالة f تقوم بربط مجموعة منتهية S بذاتها، وبأي قيمة أولية x0في S ، فإن تسلسل قيم الدوال المكررة كالتالي يجب في النهاية استخدام نفس القيمة مرتين: يجب أن يكون هناك زوج من المؤشرات المميزة i و j بحيث يكون xi = xjيجب أن يستمر التسلسل بشكل دوري، من خلال تكرار نفس سلسة القيم من xiإلى xj − 1. تحديد الحلقة هو مشكلة إيجاد i و j، إذا كان لدينا فرضاً f و x0. (ar) Hledání cyklu funkce je úloha z oblasti matematické informatiky. Předpokládá zadanou funkci na konečné množině a posloupnost hodnot Protože se jedná o posloupnost na konečné množině, musí se časem nějaká hodnota zopakovat, a od té chvíle se bude jednat o , neboť od dané zopakované hodnoty jsou odvozeny stejně i všechny hodnoty následující. Cílem úlohy je zjistit, od jaké položky je posloupnost periodická a jakou má délku periody. Délka periody se tradičně v tomto kontextu označuje řeckým písmenem λ, délka řeckým písmenem μ. (cs) 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 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. (en) Нахождение цикла — алгоритмическая задача поиска цикла в последовательности значений . Для любой функции f, отображающей конечное множество S в себя, и для любого начального значения x0 из S последовательность итеративных значений функции: Задача нахождения цикла используется для проверки качества генераторов псевдослучайных чисел и криптографических хеш-функций, в алгоритмах , для определения бесконечных циклов в компьютерных программах и периодических конфигураций клеточных автоматов, а также для автоматического связных списков. (ru) В інформатиці виявлення циклу — це алгоритмічна задача пошуку циклу в послідовності ітераційних значень функції. Для будь-якої функції f, яка відображає скінченну множину S на саму себе, і будь-якого початкового значення x0 з S, послідовність ітераційних значень функції зрештою буде двічі використовувати одне й те ж значення, тобто знайдеться пара різних індексів i та j таких, що xi = xj. Як тільки це трапиться, послідовність буде продовжуватися, повторюючи ту саму послідовність значень від xi до xj − 1. Виявлення циклу — це задача пошуку i та j для заданих f та x0. (uk) |
| rdfs:label | تحديد حلقي (ar) Hledání cyklu funkce (cs) Cycle detection (en) Rilevamento dei cicli (it) Détection de cycle (fr) Нахождение цикла (ru) Виявлення циклу (uk) |
| owl:sameAs | freebase:Cycle detection yago-res:Cycle detection wikidata:Cycle detection dbpedia-ar:Cycle detection dbpedia-az:Cycle detection dbpedia-cs:Cycle detection dbpedia-fa:Cycle detection dbpedia-fr:Cycle detection http://hy.dbpedia.org/resource/Հանգույցների_հայտնաբերում dbpedia-it:Cycle detection dbpedia-ru:Cycle detection dbpedia-sr:Cycle detection dbpedia-uk:Cycle detection dbpedia-vi:Cycle detection https://global.dbpedia.org/id/5re1K |
| prov:wasDerivedFrom | wikipedia-en:Cycle_detection?oldid=1120501293&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Functional_graph.svg wiki-commons:Special:FilePath/Tortoise_and_hare_algorithm.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Cycle_detection |
| is dbo:wikiPageDisambiguates of | dbr:Cycle |
| is dbo:wikiPageRedirects of | dbr:Tortoise_and_hare_algorithm dbr:The_Tortoise_and_the_Hare_algorithm dbr:Applications_of_cycle_detection dbr:Algorithms_for_cycle_detection dbr:Distinguished_point dbr:Floyd's_cycle-finding_algorithm dbr:Floyd's_cycle-finding_algorithm. dbr:Floyd_cycle-finding_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Python_(programming_language) dbr:List_of_algorithms dbr:Monogenic_semigroup dbr:Tortoise_and_hare_algorithm dbr:Bellman–Ford_algorithm dbr:Perfect_digital_invariant dbr:Cycle_(graph_theory) dbr:Cycle_detection dbr:Infinite_loop dbr:Integer_factorization dbr:Pseudoforest dbr:Perfect_digit-to-digit_invariant dbr:Timeline_of_algorithms dbr:Dudeney_number dbr:Cycle dbr:Linked_list dbr:Factorion dbr:Fibonacci_number dbr:Flix_(programming_language) dbr:Faith_Ellen dbr:Happy_number dbr:Kaprekar's_routine dbr:Kaprekar_number dbr:Rete_algorithm dbr:Attractor dbr:Iterated_function dbr:Jeep_Compass dbr:Telephone_number_(mathematics) dbr:The_Tortoise_and_the_Hare dbr:The_Tortoise_and_the_Hare_algorithm dbr:Pollard's_rho_algorithm dbr:Applications_of_cycle_detection dbr:Algorithms_for_cycle_detection dbr:Brent's_algorithm dbr:Distinguished_point dbr:Narcissistic_number dbr:Sum-product_number dbr:Periodic_sequence dbr:Floyd's_cycle-finding_algorithm dbr:Floyd's_cycle-finding_algorithm. dbr:Floyd_cycle-finding_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Cycle_detection |
