Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Detección de ciclos

No description
by

Cynthia Guardia Poclin

on 24 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Detección de ciclos

Detección de ciclos
La tortuga y la liebre
Aquí podemos apreciar que en el primer paso la liebre avanza 2 pasos, y luego la tortuga solo uno. En la segunda iteración, la tortuga avanza al siguiente y la liebre otros 2 pasos. En el tercer paso se encuentre un dato igual, esto quiere decir que se encontró un ciclo. Cuando se encuentra el ciclo, este proceso termina.

Pseudocódigo:
*tortuga = inicio // se inicia como puntero a un nodo predeterminado
*liebre = inicio //se inicia como puntero al mismo nodo
siempre hacer{
si ( liebre == final ) return 'No hay ciclo'
liebre = (liebre.siguiente).siguiente tortuga=tortuga.siguiente
si (tortuga == liebre) return 'Se encontró un ciclo’}



Definición
La detección de ciclos es un algoritmo que encuentra un ciclo en una secuencia de funciones que repiten valores o datos (bucles) u otro elemento del mismo tipo.

Veamos :
El algoritmo de Detección de ciclos es conocido también como «El algoritmo de la tortuga y la liebre»

Ciclo de investigación de Floyd
También llamado " el algoritmo de la tortuga y la liebre " , es un algoritmo de puntero que utiliza sólo dos punteros, que se mueven a través de la secuencia a diferentes velocidades. El algoritmo lleva el nombre de Robert W. Floyd , quien lo inventó a finales de 1960.
NOTA:
En este algoritmo es indispensable
que el puntero de la tortuga
se mueva en la misma dirección
en la que se mueve el puntero de
la liebre.
Aplicaciones de la detección de ciclos:
algoritmos numérico-teórico
Rutas de camiones
ciclos infinitos en programas de computadoras
Análisis de la forma de la lista de enlaces estructuras de datos.
Vídeo
ALGORITMO DE BRENT
Richard P.Brent se describe
un algoritmo de detección de ciclo alternativa que,al igual que el algoritmo de tortuga y liebres,solo requiere dos punteros en la secuencia.
las dos ventajas en
comparación con la tortuga y la liebre algoritmo: se encuentra en la longitud correcta del ciclo directamente,en lugar de tener que buscar en una etapa posterior,sus pasos implican sola una evaluación de F en lugar de tres.
Vídeo de BRENT
GRACIAS
4- Buscamos las aristas en las cuales el
primer vértice es el mismo.
5- Ahora insertamos los vértices en la lista.
6- Creamos un nuevo grupo
de aristas al lado derecho,
esta vez siguiendo el orden
en que escogemos las aristas.
7- Ahora alejamos escogemos el siguiente vértice en la lista.
10- Repetimos el mismo procedimiento
hasta terminar el grupo de aristas de la
sección izquierda y al terminar la fila vacía
este proceso acaba.

Ordenamiento topológico
1- Se genera un grafo cualquiera,
en este caso tendremos este grafo:


3- Creamos una lista donde insertamos
el primer vértice de una arista, en este caso
seleccionamos la primera arista.
2- Listar los nodos que se encuentran
adyacentes.
.

















8- Ahora repetimos el paso 4,5 y 6 hasta encontrar un dato igual el la lista.
9- Encontramos un ciclo! Ahora empezamos a recorrer el grupo de aristas de la derecha ya analizar la secuencia el ciclo
Detectar ciclo en un grafo dirigido
Video
Full transcript