¿Que Es La Teoría De Redes?
• Derivada de la Ciencia de Computadoras, Ciencia de Redes y Teoría de Grafos.
• Se enfatiza en el estudio de grafos representando su forma simétrica y su forma asimétrica entre objetos discretos.
Algunos Ejemplos de Redes
• World Wide Web• Redes Regulatoria de Genes• Redes Metabólicas• Redes Sociales• Redes Epistemología
Algoritmo de Dijkstra
• Fue inventado por Edward F. Moore en 1957.
• Se utiliza para encontrar el camino más corto aplicable a un grafo y a un árbol.
• Generalmente se utiliza como problema de optimización como: llegar de un lugar a otro en el menor tiempo posible con un costo eficiente.
Problemas Solubles en Tiempo Polinómico (P)
• Son problemas matemáticos, algoritmos que pueden ser resueltos en un tiempo módico, razonable y costo eficiente.
• Ejemplos de estos problemas (P), el tiempo que toma un cartero en recorrer n casas, también relacionado con el camino mas corto y el algoritmo de Dijkstra.
• Dentro de los tiempos polinómicos, podemos distinguir los logarítmicos (log(n)), los lineales (n), los cuadráticos (n^2), cúbicos (n^3), etc.
• Funciones con 2^n, no están en tiempo polinómico, porque son números gigantescos.
Ejemplo de Problemas “P”
• La versión de decisiones en programación linear, por ejemplo el uso de matrices en programación en paralelo.
• También en calcular el divisor común mas grande; por ejemplo: el 48 tiene múltiplos de 2 x 2 x 2 x 2 x 3 y el 180 tiene múltiplos de 2 x 2 x 3 x 3 x 5, según el diagrama de Ven el 48 y el 180 tienen en común el 2 x 2 x 3 que es igual 12 como el divisor común mas grande.
Problemas “NP-Completos”
• Tarda mas tiempo que los problemas “P”, o no tienen solución.
• Si se tiene una solución para un problema de tipo “NP-Completos” debería tener solución entonces todos los problemas “NP-Completos”en un tiempo módico.
• Stephen Cook en 1971 demostró que el Problema de satisfacibilidad booleana era del tipo “NP-Completos”.
Ejemplos de Problemas “NP-Completos”
• En Teoría de Grafos es difícil demostrar que en existe un ciclo en los ciclos Hamiltonianos.
• En el Viaje del Vendedor es difícil demostrar el lugar mas corto por donde viajar dependiendo de sus pesos y sus ciclos hamiltonianos.
• El camino mas corto del árbol: también es difícil demostrar la forma mas eficiente de completar los vértices dependiendo de sus pesos.
Problemas “NP-Duros”
• Son los problemas mas difícil de resolver, se necesitarían cálculos extremos para resolverlos.
• Pueden ser resueltos efectivamente solo por supercomputadoras.
• Entre estos están los problemas de decisión, de búsqueda y optimización
Ejemplos de Problemas “NP-Duros” (Cont).
• Problemas de búsquedas:1)Buscan exhaustivamente datos hasta que lo
encuentran.2)Actualmente siguen renovando nuevos
algoritmos para una mejor búsqueda.3)El algoritmo de búsqueda Breadth-first es un
algoritmo eficiente dependiendo del tipo de búsqueda. Breadth-first tiene su parecido al algoritmo de Dijkstra en buscar la forma más rápida en resolver un problema o algoritmo.
Relación entre P,NP-Completo y NP-Duros
• Problemas P son problemas que tienen solución en tiempo módico, los Problemas NP-Completo son problemas que son difícil de resolver pero pueden ser resueltos como los P. Los problemas NP-Duros son también NP pero mucho mas complicado de resolver. Si P=NP, entonces todos los algoritmos tienen solución. Si P no es igual NP, entonces caemos en el problema que existe en la actualidad, no todo algoritmo es programable.
Bibliografías
• http://en.wikipedia.org/wiki/Main_Page• http://es.wikipedia.org/wiki/Wikipedia:Porta
da• http://au.youtube.com/results?search=relat
ed&search_query=%20computer%20science%20graphs&v=8Ls1RqHCOPw
• http://www.math.ohiou.edu/~just/bioinfo05/supplements/Lect_NP.ppt.
• http://users.iems.northwestern.edu/~giden/