 |
UNIVERSIDAD PILOTO DE COLOMBIA SECCIONAL ALTO MAGDALENA GIRARDOT |
|
       |
||
|
ALGORITMO Conjunto ordenado y finito de operaciones que permite hallar la solución de un problema. para que un algoritmo pueda ser considerado como tal, debe ser:
DETERMINISTA: que si se sigue el mismo proceso más de una vez se llega siempre al mismo resultado FINITO: implica que tiene un determinado número de pasos, es decir, que termina EFICIENTE: que las instrucciones encuentran la solución en el menor tiempo posible.
CARACTERISTICAS DE LOS ALGORITMOS Carácter finito Precisión Entrada Salida Eficacia
TEORIA DE LA COMPUTABILIDAD
¿Qué pueden hacer los ordenadores (sinrestricciones de espacio, tiempo o dinero )?
¿Cuales son las limitaciones inherentes a
los métodos automáticos de cálculo?
COMIENZO DE LA TEORIA
Church, Gödel, Kleene, Post, y Turing.
Máquina de Turing
Teoría de la complejidad computacional
Rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cálculo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema).
clases de complejidad Las clases de complejidad clasifican los problemas de decisión en conjuntos de complejidad comparables
Clase P (Polinómico determinista ) Clase NP (Polinómico no determinista ) Clase P-completo (Tiempo polinómico) Clase NP-Completo (Tiempo no polinómico)
Clase P Es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina determinista en tiempo polinómico, lo que corresponde intuitivamente a problemas que pueden ser resueltos aún en el peor de sus casos.
Clase NP
Se le da el nombre de clase NP a problemas que pueden resolverse por una máquina no determinista en tiempo polinomial.
Una computadora no determinística es
aquella que en cualquier paso de sus cálculos puede encontrarse
con dos o más cursos alternativos de acción y puede
producir copias de sí misma, incluyendo el contenido de su
memoria, y continuar con su trabajo de forma independiente para
cada alternativa.
Problema de satisfacibilidad booleana En donde se desea saber si una cierta fórmula de lógica proposicional puede ser cierta para algún conjunto de valores booleanos para las variables.
Problema del viajante Donde se quiere saber si existe una ruta óptima que pasa por todos los nodos en un cierto grafo
Clase P-completo Es un conjunto de problemas de decisión de gran utilidad para identificar los problemas que pueden ser resueltos eficientemente en máquinas paralelas. Problema del valor de una compuerta en un circuito (Circuit Value Problem o CVP) - Dado un circuito booleano, sus entradas y una compuerta lógica en el circuito, calcular la salida de la puerta Programación lineal Maximizar una función lineal sujeta a restricciones expresadas como desigualdades Pertenencia a una gramática libre de contexto - Dado una gramática libre de contexto y una palabra, saber si la palabra pertenece al lenguaje generado por la gramática
Clase NP-completo Es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema de NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico.
SOLUCIONES APROXIMADAS Aproximación: Un algoritmo que rápidamente encuentra una solución no necesariamente óptima, pero dentro de un cierto rango de error. Probabilístico: Un algoritmo probabilístico obtiene en promedio una buena solución al problema planteado, para una distribución de los datos de entrada dada. Casos particulares: Cuando se reconocen casos particulares del problema para los cuales existen soluciones rápidas. Heurísticas: Un algoritmo que trabaja razonablemente bien en muchos casos. En general son rápidos, pero no existe medida de la calidad de la respuesta. Algoritmo genético: Algoritmos que mejoran las posibles soluciones hasta encontrar una que posiblemente esté cerca del óptimo. Tampoco existe forma de garantizar la calidad de la respuesta.
Problema de satisfacibilidad booleana (SAT) Problema de la mochila (knapsack) Problema del ciclo hamiltoniano Problema del vendedor viajero Problema de la clique
Tipos de Problemas
Problemas Decidibles Problemas Tratables Problemas Intratables Problemas NO Decidibles Problemas NO Computables Problemas Fuertemente No Computables
|
||
Jose Said Uricoechea Sandoval - Jose Roberto Reyes - Elkin Espinosa Ingenieria de Sistemas VI Semestre |
||
