complejidad computacional
Páginas: 5 (1056 palabras)
Publicado: 22 de abril de 2013
UNIVERSIDAD AUTONOMA DE NUEVO LEON
FACULTAD DE INGENIERIA MECANICA Y ELECTRICA
ESTRUCTURA DE DATOS
TRABAJO DE INVESTIGACION: “Complejidad computacional”
EQUIPO 9
HORA: V1 SALON 2104
4 de Marzo del 2013
Ciudad Universitaria, San Nicolás de los Garza.
Definición
Complejidad computacional.
Definición informal: Un algoritmo es un procedimiento o métodode cálculo (con unas reglas bien determinadas') que conduce a la resolución de cualquier `instancia' de un problema especifico (en un numero nito de pasos). Ejemplos: algoritmo de ordenación de una lista de números, test de primalidad, etc.
Definición formal: Un algoritmo es una secuencia de instrucciones que determina
completamente el comportamiento de una máquina de Turing (modelo decomputación).
La complejidad computacional estudia la “dificultad” inherente de problemas de importancia teórica y/o práctica. El esfuerzo necesario para resolver un problema de forma eficiente puede variar enormemente. Un problema muy complejo se denomina “NP-completo”, lo cual básicamente significa que es imposible encontrar un algoritmo eficiente para encontrar una solución óptima. Probar que unproblema es “NP-completo” es muy importante puesto que permite abandonar un callejón sin salida (encontrar un algoritmo para la solución óptima) para centrarse en objetivos realizables (encontrar algoritmos para obtener soluciones aproximadas). El objetivo fundamental de la teoría de la complejidad computacional es facilitar el avance en aquellas áreas en las que es posible.Características
Dentro de la evolución de la teoría de complejidad, se han encontrado problemas con características similares, que pueden ser agrupados en categorías para su estudio.
Los problemas de optimización son aquellos en los cuales se busca minimizar o maximizar (es decir, optimizar) el valor de una solución en un grupo de soluciones generadas para una entrada específica (instancia).La forma general de exponer un problema de optimización es: optimizar c(s) sobre s en F(n). Los problemas de decisión son aquellos donde se busca una respuesta de ''si'' o ''no''.
Cualquier problema de optimización puede ser manejado como un problema de decisión incluyendo un valor objetivo K para la instancia n y preguntando si existe o no existe una solución factible en el conjunto desoluciones F(n), con el valor de la solución c(s) optimizado sobre K (para el caso de minimización sería c(s) £ K y c(s) ‡ K para el caso de maximización).
De esta forma, para propósitos teóricos, es más conveniente tratar con problemas de decisión que con problemas de optimización.
Tipos de complejidad computacional
Algoritmos no deterministas (ii)
Esta instrucciónpermitiría resolver el problema en un tiempo polinomial al explorar simultáneamente todas las posibilidades:
inicio
desde j‹1 hasta n hacer
ir simultáneamente a A y B
A: x (j) ‹0
B: x () ‹1
fin desde
si x satisface Ax=b entonces
escribir “sí”
si no
escribir no
fin si
fin
Si se dispusiera de ordenadores capaces de ejecutar semejante instrucción no sería necesaria la Teoría de laComplejidad Computacional. Se especula con la
posibilidad de que los ordenadores cuánticos pudieran disponer de semejante
capacidad.
Problemas P y NP
Cualquier problema de optimización puede ser transformado en un problema de decisión. En el análisis de complejidad se manejan, por lo tanto, los problemas de decisión, que incluyen a los de optimización.
Si se encuentra solución a unproblema de decisión, entonces se encuentra también solución a un problema de optimización. Al estudiar los problemas de decisión, se pueden encontrar varias clases:
La clase de problemas P está formada por todos aquellos problemas de decisión para los cuales se tiene un algoritmo de solución que se ejecuta en tiempo polinomial en una máquina determinista.
La clase de problemas NP está...
FACULTAD DE INGENIERIA MECANICA Y ELECTRICA
ESTRUCTURA DE DATOS
TRABAJO DE INVESTIGACION: “Complejidad computacional”
EQUIPO 9
HORA: V1 SALON 2104
4 de Marzo del 2013
Ciudad Universitaria, San Nicolás de los Garza.
Definición
Complejidad computacional.
Definición informal: Un algoritmo es un procedimiento o métodode cálculo (con unas reglas bien determinadas') que conduce a la resolución de cualquier `instancia' de un problema especifico (en un numero nito de pasos). Ejemplos: algoritmo de ordenación de una lista de números, test de primalidad, etc.
Definición formal: Un algoritmo es una secuencia de instrucciones que determina
completamente el comportamiento de una máquina de Turing (modelo decomputación).
La complejidad computacional estudia la “dificultad” inherente de problemas de importancia teórica y/o práctica. El esfuerzo necesario para resolver un problema de forma eficiente puede variar enormemente. Un problema muy complejo se denomina “NP-completo”, lo cual básicamente significa que es imposible encontrar un algoritmo eficiente para encontrar una solución óptima. Probar que unproblema es “NP-completo” es muy importante puesto que permite abandonar un callejón sin salida (encontrar un algoritmo para la solución óptima) para centrarse en objetivos realizables (encontrar algoritmos para obtener soluciones aproximadas). El objetivo fundamental de la teoría de la complejidad computacional es facilitar el avance en aquellas áreas en las que es posible.Características
Dentro de la evolución de la teoría de complejidad, se han encontrado problemas con características similares, que pueden ser agrupados en categorías para su estudio.
Los problemas de optimización son aquellos en los cuales se busca minimizar o maximizar (es decir, optimizar) el valor de una solución en un grupo de soluciones generadas para una entrada específica (instancia).La forma general de exponer un problema de optimización es: optimizar c(s) sobre s en F(n). Los problemas de decisión son aquellos donde se busca una respuesta de ''si'' o ''no''.
Cualquier problema de optimización puede ser manejado como un problema de decisión incluyendo un valor objetivo K para la instancia n y preguntando si existe o no existe una solución factible en el conjunto desoluciones F(n), con el valor de la solución c(s) optimizado sobre K (para el caso de minimización sería c(s) £ K y c(s) ‡ K para el caso de maximización).
De esta forma, para propósitos teóricos, es más conveniente tratar con problemas de decisión que con problemas de optimización.
Tipos de complejidad computacional
Algoritmos no deterministas (ii)
Esta instrucciónpermitiría resolver el problema en un tiempo polinomial al explorar simultáneamente todas las posibilidades:
inicio
desde j‹1 hasta n hacer
ir simultáneamente a A y B
A: x (j) ‹0
B: x () ‹1
fin desde
si x satisface Ax=b entonces
escribir “sí”
si no
escribir no
fin si
fin
Si se dispusiera de ordenadores capaces de ejecutar semejante instrucción no sería necesaria la Teoría de laComplejidad Computacional. Se especula con la
posibilidad de que los ordenadores cuánticos pudieran disponer de semejante
capacidad.
Problemas P y NP
Cualquier problema de optimización puede ser transformado en un problema de decisión. En el análisis de complejidad se manejan, por lo tanto, los problemas de decisión, que incluyen a los de optimización.
Si se encuentra solución a unproblema de decisión, entonces se encuentra también solución a un problema de optimización. Al estudiar los problemas de decisión, se pueden encontrar varias clases:
La clase de problemas P está formada por todos aquellos problemas de decisión para los cuales se tiene un algoritmo de solución que se ejecuta en tiempo polinomial en una máquina determinista.
La clase de problemas NP está...
Leer documento completo
Regístrate para leer el documento completo.