About: Cycle detection     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatAlgorithms, within Data Space : dbpedia.org associated with source document(s)

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.

AttributesValues
rdf:type
rdfs:label
  • Cycle detection
  • Hase-Igel-Algorithmus
  • Algorithme du lièvre et de la tortue
  • Rilevamento dei cicli
  • フロイドの循環検出法
  • Algoritmo busca-ciclos de Floyd
  • Floyd判圈算法
rdfs:comment
  • Der Hase-Igel-Algorithmus ist ein Verfahren, mit dem in einer einfach verketteten Liste Schleifen mit der Zeitkomplexität und einer Platzkomplexität von gefunden werden können. Mathematisch betrachtet dient der Algorithmus zum Auffinden von Zyklen in Folgen. Er ist auch unter dem Namen Floyds Algorithmus zum Auffinden von Schleifen (englisch Floyd’s cycle-finding algorithm) bekannt und darf nicht mit Floyds Algorithmus aus der Graphentheorie verwechselt werden.
  • L'algorithme de Floyd de détection de cycle, encore connu sous le nom d'algorithme du lièvre et de la tortue, est un algorithme pour détecter les cycles dans des séquences arbitraires, qu'il s'agisse de structures de données ou de séquences générées à la volée (et notamment les séquences pseudo-aléatoires), en espace O(1). Cet algorithme fut énoncé par Robert Floyd en 1967, et ne doit pas être confondu avec l'algorithme de Floyd-Warshall (tous les plus courts chemins dans un graphe).
  • フロイドの循環検出法(英: Floyd's cycle-finding algorithm)とは、任意の数列に出現する循環を検出するアルゴリズムである。任意の数列とは、例えばデータ構造でもよいし、O(1)領域でその場で生成される数列(特にグラフや擬似乱数列)でもよい。ロバート・フロイドが1967年に発明した。ウサギとカメのアルゴリズムと呼ばれることもある。 グラフの最短経路問題を解くワーシャル-フロイド法とは異なる。
  • Il Rilevamento dei cicli, in informatica è 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.
  • Floyd判圈算法(Floyd Cycle Detection Algorithm),又称龟兔赛跑算法(Tortoise and Hare Algorithm)。该算法由美国科学家罗伯特·弗洛伊德发明,是一个可以在有限状态机、迭代函数或者链表上判断是否存在环,求出该环的起点与长度的算法。 如果有限状态机、迭代函数或者链表上存在环,那么在某个环上以不同速度前进的2个指针必定会在某个时刻相遇。同时显然地,如果从同一个起点(即使这个起点不在某个环上)同时开始以不同速度前进的2个指针最终相遇,那么可以判定存在一个环,且可以求出2者相遇处所在的环的起点与长度。
  • 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.
  • Algoritmo para Busca de Cíclos de Floyd é um algoritmo inventado por Robert W. Floyd em 1967 para detectar ciclos em seqüências arbitrárias, seja em estruturas de dados ou geradas ao vivo (especialmente grafos e seqüências pseudo-aleatórias) usando espaço O(1). Algumas vezes este algoritmo é chamado de algoritmo-"tartaruga e a lebre". A discussão a seguir é construída em termos de seqüências aleatórias em particular, de grande importância na análise de geradores de número pseudo-aleatórios e nas aplicações de algoritmos tais como fatoração o algoritmo rho de Pollard. Seja
sameAs
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Faceted Search & Find service v1.17_git39 as of Aug 09 2019


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3232 as of Aug 9 2019, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2019 OpenLink Software