UPV



Resultados de la búsqueda By Etiquetas: problema-de-decision


¿Cómo decidir cuando tenemos un dilema? El óptimo de Pareto

Los problemas de decisión están presentes en todos los ámbitos del ser humano: finanzas, empresa, ingeniería, salud, etc. Una de las grandes dificultades al tomar una decisión ocurre cuando queremos conseguir varios objetivos distintos, muchos de ellos incompatibles o contradictorios. Por ejemplo, si queremos un vehículo que sea muy veloz, debería tener un perfil aerodinámico que a veces es incompatible con la comodidad de los usuarios;  si queremos hacer un negocio con grandes beneficios, a veces tenemos que asumir ciertos riesgos, etc. Una herramienta que permite afrontar este tipo de problemas de decisión es el denominado “óptimo de Pareto“. A continuación os paso un vídeo explicativo de este tema. Espero que os guste.

15 Febrero, 2015
 
|   Etiquetas: ,  ,  |  

¿Qué es un algoritmo?

Algoritmo de Euclides

Un algoritmo es un conjunto prescrito de reglas o instrucciones bien definidas para la resolución de un problema. En general, se trata de encontrar el método más “eficiente”, no siendo baladí el modo de medir dicha eficiencia. Para resolver esta circunstancia, en la década de los 70 numerosos científicos se interesaron por la complejidad computacional de los problemas y los algoritmos. En muchos casos se asimila el rendimiento algorítmico a la medida del tiempo medio de ejecución empleado por un procedimiento para completar su operación con un conjunto de datos. Además, es posible relacionar el esfuerzo de cálculo con la dimensión del problema a resolver.

Un algoritmo muestra una complejidad polinómica si necesita un tiempo O(nk), donde n muestra la dimensión de entrada y k es una constante independiente de n. Si la función que denota la complejidad no está acotada por un polinomio, el algoritmo presenta una complejidad en tiempo exponencial.

 Un problema de decisión es aquel que puede ser contestado con una afirmación o una negación. Llamemos P a la clase de problemas de decisión que pueden ser resueltos en tiempo cálculo que crece de forma polinomial ante incrementos lineales del número de elementos que intervienen, y NP aquellos solubles en un tiempo polinomial indeterminado, es decir, que se puede resolver en tiempo polinomial con una máquina Turing no determinística (ordenador). Un ordenador no determinístico puede ser contemplado como un autómata capaz de ejecutar un número ilimitado (pero finito) de ejecuciones en paralelo. Sólo los problemas en P son resolubles eficientemente mediante algoritmos, no conociéndose un procedimiento polinomial de resolución para los NP, siendo obvio que P pertenezca NP. Si lo contrario también ocurriera, P pertenecería a NP, querría decir que para la mayoría de los problemas de interés existen algoritmos eficientes que los resolvieran. Sin embargo, no se conoce la forma de demostrar que la igualdad P=NP sea cierta, ni tampoco que haya problemas en NP que no estén en P, es decir, la existencia de algún problema en NP que no se pueda resolver en tiempo polinómico (ver Díaz et al., 1996).

Un problema X se dice que es NP-completo (NPC) si (más…)

Universidad Politécnica de Valencia