Ensayo Teoria De Complejidad Computacional
Páginas: 3 (610 palabras)
Publicado: 12 de noviembre de 2012
Complejidad Computacional
La teoria de complejidad computacional se define por el tratamiento de recursos necesarios para la resolucion de un problema en funcion de un sistema de computo, dondese estudia el tamaño del espacio de busqueda y el tiempo total de ejecucion de las operaciones para resolver el problema.
La complejidad de la instancia de un problema se calcula a partir delnúmero de pasos que toma resolverlo, considerando el tamaño de la entrada como espacio de busqueda y utilizando el algoritmo más eficiente que se conoce. Supongase que se toma n² pasos para resolverse, sedice entonces que la instancia del problema tiene una complejidad de n².
Es interesante que el conjunto de problemas pueden ser redactados como problemas de decision para determinar si existe ono solucion al mismo en un modelo de longitud finita. De ahi entonces, que tales problemas se clasifican por su factibilidad en: decidibles e indecidibles.
Los problemas indecidibles son aquellosque no poseen una estrategia finita de pasos ordenados para su solucion y que resulta imposible determinarla con el poder de la tecnología existente. Mientras tanto, los problemas decidibles pueden sertratados por algoritmos deterministas y no deterministas de acuerdo a la clase de complejidad que se discute a continuacion.
En el espacio de problemas decidibles se encuentran dos categoríasprincipales: Los problemas P y NP.
Los problemas P se caracterizan por ser problemas de los cuales se conoce un algoritmo de solucion determinista que examina todo el espacio de busqueda en tiempopolinomial, es decir que el tiempo de su resolucion se relaciona linealmente con su tamaño.
Mientras que los problemas NP se caracterizan por no conocer un algoritmo determinista con ejecución en tiempopolinomico, de tal modo que las estrategias de solucion dado el espacio de busqueda, se desempeñan en complejidad exponencial. Por tal motivo, el estudio de estos ultimos aborda modelos no...
La teoria de complejidad computacional se define por el tratamiento de recursos necesarios para la resolucion de un problema en funcion de un sistema de computo, dondese estudia el tamaño del espacio de busqueda y el tiempo total de ejecucion de las operaciones para resolver el problema.
La complejidad de la instancia de un problema se calcula a partir delnúmero de pasos que toma resolverlo, considerando el tamaño de la entrada como espacio de busqueda y utilizando el algoritmo más eficiente que se conoce. Supongase que se toma n² pasos para resolverse, sedice entonces que la instancia del problema tiene una complejidad de n².
Es interesante que el conjunto de problemas pueden ser redactados como problemas de decision para determinar si existe ono solucion al mismo en un modelo de longitud finita. De ahi entonces, que tales problemas se clasifican por su factibilidad en: decidibles e indecidibles.
Los problemas indecidibles son aquellosque no poseen una estrategia finita de pasos ordenados para su solucion y que resulta imposible determinarla con el poder de la tecnología existente. Mientras tanto, los problemas decidibles pueden sertratados por algoritmos deterministas y no deterministas de acuerdo a la clase de complejidad que se discute a continuacion.
En el espacio de problemas decidibles se encuentran dos categoríasprincipales: Los problemas P y NP.
Los problemas P se caracterizan por ser problemas de los cuales se conoce un algoritmo de solucion determinista que examina todo el espacio de busqueda en tiempopolinomial, es decir que el tiempo de su resolucion se relaciona linealmente con su tamaño.
Mientras que los problemas NP se caracterizan por no conocer un algoritmo determinista con ejecución en tiempopolinomico, de tal modo que las estrategias de solucion dado el espacio de busqueda, se desempeñan en complejidad exponencial. Por tal motivo, el estudio de estos ultimos aborda modelos no...
Leer documento completo
Regístrate para leer el documento completo.