Rilevamento dei cicli
# Rilevamento dei cicli

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.

    $x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots$

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.

## Algoritmo di ricerca del ciclo di Floyd

Sia μ l'indice del primo elemento del ciclo.

Per ogni intero i ≥ μ e per ogni intero k ≥ 0, abbiamo che per tutti gli elementi all'interno del ciclo vale la relazione $x_i$ = $x_{i+kλ,}$ dove λ rappresenta la lunghezza del ciclo che vogliamo individuare.

In particolare, nel caso in cui i=kλ, abbiamo che $x_i$ = $x_{2i}$

Quindi l'algoritmo deve solo trovare dei valori ripetuti di questa particolare forma, in cui uno dei valori si trova al doppio della distanza dall'inizio del ciclo rispetto all'altro, in maniera tale da individuare un periodo di ripetizione v che sia un multiplo di λ.

L'algoritmo quindi mantiene 2 puntatori nella sequenza, uno (la tartaruga) puntato ad $x_i$ e l'altro (la lepre) puntato ad $x_{2i}$

Ad ogni passo dell'algoritmo, i viene aumentato di uno, facendo sì che la tartaruga si muova di 1 passo, e la lepre di 2 passi in avanti nella sequenza. Quindi vengono comparati i valori dei due puntatori. Il più piccolo valore di i > 0 per cui la tartaruga e la lepre puntano a valori uguali è il valore desiderato di v.

Una volta che v è stato individuato, l'algoritmo ripercorre la sequenza dall'inizio per trovare il primo valore ripetuto $x_μ$ nella sequenza, sfruttando il fatto che v è un multiplo di λ. Quindi possiamo dire che $x_μ=x_{μ+v}$

Infine, una volta che il valore di μ è conosciuto, è facile trovare la lunghezza λ del più piccolo dei cicli, cercando il primo valore μ+λ per cui $x_{μ+λ}$ = $x_μ$

## Algoritmo di Brent

Codice Python che mostra come funziona la tecnica:

