Ejercicios Ruta Mas Corta Y Maquina De Estado Finito
Páginas: 8 (1864 palabras)
Publicado: 8 de agosto de 2011
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
CONCLUSION:
El algoritmo de Bellman-Ford, genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que elAlgoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo.
El Algoritmo de Bellman-Ford es, en su estructura básica, muy parecido al algoritmo de Dijkstra, pero en vez de seleccionar vorazmente el nodo de peso mínimo aun sin procesar para relajarlo, simplemente relaja todas las aristas, y lo hace |V|-1 veces, siendo |V| el número de vértices en el grafo. Lasrepeticiones permiten a las distancias mínimas recorrer el árbol, ya que en la ausencia de ciclos negativos, el camino más corto solo visita cada vértice una vez.
Máquina de estados
Se denomina máquina de estados a un modelo de comportamiento de un sistema con entradas y salidas, en donde las salidas dependen no sólo de las señales de entradas actuales sino también de las anteriores. Las máquinas deestados se definen como un conjunto de estados que sirve de intermediario en esta relación de entradas y salidas, haciendo que el historial de señales de entrada determine, para cada instante, un estado para la máquina, de forma tal que la salida depende únicamente del estado y las entradas actuales.
Una máquina de estados se denomina máquina de estados finitos (FSM por finite state machine) si elconjunto de estados de la máquina es finito, este es el único tipo de máquinas de estados que podemos modelar en un computador en la actualidad; debido a esto se suelen utilizar los términos máquina de estados y máquina de estados finitos de forma intercambiable.
Entre las máquinas de estado finito diseñadas especialmente para el reconocimiento de lenguajes, están los autómatas deestado finito (máquinas de estado finito sin salida).
Máquinas de estado finito, puede utilizarse para especificar aspectos dinámicos de problemas. Dichos problemas, probablemente también posean aspectos estáticos: estructuras de datos necesarias, entidades relacionadas entre sí, invariantes, etc. Muchos de estos aspectos pueden modelarse a través de un modeloconceptual.
Todas las máquinas de estado finito tienen un conjunto de estados, incluido el estado inicial, un alfabeto fuente y una función de transición que a cada pareja de estado y dato de entrada le asigna el estado siguiente. Los estados de la maquina le dan unas capacidades de memoria limitadas.
Como ejemplo, consideremos un muy simplificado sistema de control de un ascensor.Ventajas de las Máquinas de Estado Finito
• Son intuitivas y fáciles de entender.
• Abstraen convenientemente detalles secundarios que no son necesarios para el análisis del sistema a un alto nivel y se centran en aspectos claves del mismo.
• Son universalmente aplicables.
• Su uso es común en sistemas de transmisión de datos y el uso de protocolos de comunicación.
• En programaciónminimiza grandemente la tendencia a escribir "código espagueti" y puede ayudar a reducir la cantidad de variables globales necesarias, aumentando al mismo tiempo la confiabilidad del sistema.
Ejemplo 1.
En una estación del Metro una máquina distribuye tiquetes sencillos a $600 pesos el tiquete. La máquina acepta monedas de $100, $200, $500, $1000. Mediante una tabla,describa los diferentes estados de la máquina y la salida.
Solución.
Se supondrá que la máquina se encuentra en el estado e0 perteneciente a E en el tiempo t0. Al introducir una moneda en el tiempo ti la salida será g(x, es) donde es es el estado de la máquina en el tiempo ti. A esta salida le sigue una transición de la máquina en el tiempo ti+1dado por f(x, es).
Para el ejemplo, los estados del...
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
CONCLUSION:
El algoritmo de Bellman-Ford, genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que elAlgoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo.
El Algoritmo de Bellman-Ford es, en su estructura básica, muy parecido al algoritmo de Dijkstra, pero en vez de seleccionar vorazmente el nodo de peso mínimo aun sin procesar para relajarlo, simplemente relaja todas las aristas, y lo hace |V|-1 veces, siendo |V| el número de vértices en el grafo. Lasrepeticiones permiten a las distancias mínimas recorrer el árbol, ya que en la ausencia de ciclos negativos, el camino más corto solo visita cada vértice una vez.
Máquina de estados
Se denomina máquina de estados a un modelo de comportamiento de un sistema con entradas y salidas, en donde las salidas dependen no sólo de las señales de entradas actuales sino también de las anteriores. Las máquinas deestados se definen como un conjunto de estados que sirve de intermediario en esta relación de entradas y salidas, haciendo que el historial de señales de entrada determine, para cada instante, un estado para la máquina, de forma tal que la salida depende únicamente del estado y las entradas actuales.
Una máquina de estados se denomina máquina de estados finitos (FSM por finite state machine) si elconjunto de estados de la máquina es finito, este es el único tipo de máquinas de estados que podemos modelar en un computador en la actualidad; debido a esto se suelen utilizar los términos máquina de estados y máquina de estados finitos de forma intercambiable.
Entre las máquinas de estado finito diseñadas especialmente para el reconocimiento de lenguajes, están los autómatas deestado finito (máquinas de estado finito sin salida).
Máquinas de estado finito, puede utilizarse para especificar aspectos dinámicos de problemas. Dichos problemas, probablemente también posean aspectos estáticos: estructuras de datos necesarias, entidades relacionadas entre sí, invariantes, etc. Muchos de estos aspectos pueden modelarse a través de un modeloconceptual.
Todas las máquinas de estado finito tienen un conjunto de estados, incluido el estado inicial, un alfabeto fuente y una función de transición que a cada pareja de estado y dato de entrada le asigna el estado siguiente. Los estados de la maquina le dan unas capacidades de memoria limitadas.
Como ejemplo, consideremos un muy simplificado sistema de control de un ascensor.Ventajas de las Máquinas de Estado Finito
• Son intuitivas y fáciles de entender.
• Abstraen convenientemente detalles secundarios que no son necesarios para el análisis del sistema a un alto nivel y se centran en aspectos claves del mismo.
• Son universalmente aplicables.
• Su uso es común en sistemas de transmisión de datos y el uso de protocolos de comunicación.
• En programaciónminimiza grandemente la tendencia a escribir "código espagueti" y puede ayudar a reducir la cantidad de variables globales necesarias, aumentando al mismo tiempo la confiabilidad del sistema.
Ejemplo 1.
En una estación del Metro una máquina distribuye tiquetes sencillos a $600 pesos el tiquete. La máquina acepta monedas de $100, $200, $500, $1000. Mediante una tabla,describa los diferentes estados de la máquina y la salida.
Solución.
Se supondrá que la máquina se encuentra en el estado e0 perteneciente a E en el tiempo t0. Al introducir una moneda en el tiempo ti la salida será g(x, es) donde es es el estado de la máquina en el tiempo ti. A esta salida le sigue una transición de la máquina en el tiempo ti+1dado por f(x, es).
Para el ejemplo, los estados del...
Leer documento completo
Regístrate para leer el documento completo.