En este problema nos piden que hagamos el diagrama de flujo de este pseudocódigo, y luego hay que simular la ejecución del algoritmo para las entradas 1, 2, 16, 49 y 53. Luego diré de que trata el algoritmo.
Para hacer el diagrama de flujo del pseudocódigo utilize el Microsoft Office Visio 2007, un programa muy bueno para hacer varios tipos de diagramas.
Este sería el diagrama de flujo del pseudocódigo.
El algoritmo nos dice si un numero es primo o no. La impresión de las entradas 1, 2, 16, 49 y 53 sería así:
En este problema hay que ejecutar paso a paso la máquina Turing definida por la siguiente función de transición:
con la entrada siendo la representación binaria del numero decimal 37
Para resolver este problema primero hay que convertir el numero decimal en bianrio, para convertirlo existen varias maneras, asi que usaré una de las más fáciles:
Nuestro numero binario serían los residuos de todas las divisiones. Nuestro número binario sería: 100101
Empezamos:
por nuestras condiciones se queda el estado s, se pone un 0 y se mueve a la derecha
ahora se queda el estado s, se pone un 1 y se mueve a la derecha
se repite una condición anterior, se queda en s, se pone un 0 y se mueve a la derecha
estado s, se pone un 0, se mueve a la derecha
estado s, se pone un 1, se mueve a la derecha
estado s, se pone un 0, se mueve a la derecha
estado s, se pone un 1, se mueve a la derecha
ahora cambió, ahora es un estado t, se pone un 0 y se mueve a la izquierda
finalmente queda en Si, se pone un 1 y termina.
el numero binario que queda es 01001110 ahora hay que convertir este numero binario en decimal (0*2^0)+(1*2^1)+(1*2^2)+(1*2^3)+(0*2^4)+(0*2^5)+(1*2^6)+(0*2^7)
= (2^1)+(2^2)+(2^3)+(2^6)
= 2+4+8+64
= 78
Lo que hace esta maquina de turing es multiplicar el numero por 2 y le suma 4. La complejidad sería O(n).
En este problema debemos encontrar una funcion que este debajo de la cota superior de g(n)
Para encontrarla use varias funciones:
1- f(n)=n^3 Intentaremos con una función cúbica. Sustituimos los valores de "n" y la grafica queda asi:
la cota de f(n)=n^3 es muy superior a la cota de g(n), por lo tanto no es la funcion que buscamos, asi que intentaremos con otra funcion.
2- f(n)=n^2 Después de sustituir los valores de "n" en la funcion la grafica queda asi:
la cota de la función sigue siendo superior a la deseada. Intentaremos con otra
3- f(n)=logn Ahora es una función logarítmica:
Esta vez la cota de la función si es menor a la de g(n), pero es un poco mas baja de lo deseado. Intentaré con otra:
4- f(n)=nlogn Otra función logarítmica multiplicada por n:
Esta función parece ser la que más se acerca a lo que deseamos, así que ésta sería la respuesta al problema planteado.
Las funciones f(n)=x^2 y f(n)=x^3 sobrepasaban mucho la cota de g(n), y la cota de f(n)=logn era muy baja. Finalmente la cota de la función f(n)=nlogn es la cota inferior que más se aproxima a g(n) y, por lo tanto, es la cota que buscábamos.
En la teoría de grafos surgen varios problemas relacionados con los caminos que existen entre pares de vértices, ya sea, encontrar los caminos más cortos de un grafo (dirigido y no dirigido), ver si el grafo es conexo, etc. En este trabajo hablaremos de la clausura transitiva(o cierre transitivo) de un grafo dirigido, tema que surgió para resolver un problema específico de grafos, pero que tiene aplicaciones en problemas reales.
El concepto de transitividad es el mismo que se utiliza en teoría matemática el cual postula que si "a" es menor a "b" y "b" es menor a c, entonces "a" es menor a "c". En el caso de clausura transitiva, el concepto se refiere a que existe un camino que une el vértice i con el vértice j, no importando que para llegar desde i a j tengamos que visitar otros vértices del grafo. Por esta razón es que el algoritmo fue diseñado para grafos dirigidos, donde si es importante hacia donde están apuntando los vértices, ya que en digrafos muy grandes, el problema de encontrar caminos entre pares de vértices es demasiado complicado, sólo siguiendo el trazado del dibujo del mismo, de ahí la importancia de este algoritmo y el interés que generó su estudio.
La clausura transitiva de una relación binaria es la relación binaria más pequeña que siendo transitiva contiene al conjunto de pares de la relación binaria original.
La clausura transitiva de un grafo G se define como el grafo G* = (V, E*), donde E*={(i, j): hay un camino desde el vértice i al vértice j en G}.
Dado el siguiente grafo dirigido, encontrar la clausura transitiva de él:
La clausura transitiva del grafo asociado es:
Algoritmo: El algoritmo utilizado para encontrar la clausura transitiva de un grafo dirigido es muy parecido al algoritmo de Floyd_Warshall, rellena la matriz de adyacencia sólo con 0 y 1, a diferencia del otro que les asocia un peso a cada arista que está en el grafo. Ahora presentaré el algoritmo propuesto:
Como podemos ver, el algoritmo tiene como entrada el grafo y como salida la matriz de alcance asociada a ese grafo. Desde la línea 1 hasta la 6, lo que hace es completar la matriz de adyacencia del grafo, notar que ésta matriz en la diagonal se le asigna el valor 1, ya que supone que hay un camino desde un vértice a él mismo en la matriz de alcance. Luego desde la línea7 a la 10 calcula las diferentes matrices, para este proceso va guardando la matriz anterior que es con la que hace el trabajo, la matriz actual sólo sirve para guardar los resultados, el n que se indica es el número de vértices que tiene el grafo, por lo tanto calcula tantas matrices como vértices tiene el grafo. Luego en la línea final(11), retorna la matriz de alcance asociada al grafo, que es la clausura transitiva del grafo.
Ahora veremos cómo trabaja el algoritmo, a través del ejemplo anterior. Teníamos que el grafo era:
El primer paso es completar la matriz de adyacencia del grafo (recordando que la diagonal se rellena con 1), por lo tanto nos queda que:
0- Matriz de Adyacencia, con la diagonal cambiada por uno.
1- Esta matriz indica si existe un camino desde el nodo i al nodo j, pasando por el nodo 1.
2- Esta matriz indica si existe un camino desde el nodo i al nodo j, pasando por el nodo 2.
3- Esta matriz indica si existe un camino desde el nodo i al nodo j, pasando por el nodo 3.
4- Esta es la matriz de alcanze que nos muestra la clausura transitiva del grafo.
El dibujo es:
El costo asociado a este algoritmo es de 0(n3), ya que el costo de encontrar la matriz de alcance está íntimamente ligado con los ciclos que se necesitan para recorrer la matriz, además por ser un algoritmo de programación dinámica el costo tiene que ser polinomial.
