| 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)
|
| 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)
|
