Ir al contenido principal

Optmizacion

Estamos de Regreso!!!!!
Despues de unas cortas y bien merecidas vacaciones, es hora de continuar con las entradas. En estos momentos estoy llevando la materia de "topicos selectos de optimizacion" mejor conocida como "opti-2" y como primera tarea es escoger un problema de complejidad NP he decidido hacer esta entrada de introducción "Complejidad computacional: NP-completos", para desvancer las dudas. Espero y les sirva como a mi.

Complejidad computacional: NP

La importancia de esta clase de problemas de decisión es que contiene muchos problemas de búsqueda y de optimización para los que se desea saber si existe una cierta solución o si existe una mejor solución que las conocidas. En esta clase están el problema del viajante (también llamado "problema del agente de ventas" o "problema del agente viajero") donde se quiere saber si existe una ruta óptima que pasa por todos los nodos en un cierto grafo y el 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.

Dada su importancia, se han hecho muchos esfuerzos para encontrar algoritmos que decidan algún problema de NP en tiempo polinómico. Sin embargo, pareciera que para algunos problemas de NP (los del conjunto NP-completo) no es posible encontrar un algoritmo mejor que simplemente realizar una búsqueda exhaustiva.


Relación con otras clases de complejidad

NP contiene todos los problemas pertenecientes a las clases P y NP-C, y a su vez está contenido en el conjunto de los PSPACE. Aún se desconoce si estas inclusiones son estrictas o no, y si la intersección entre los NP y Co-NP es o no vacía.
En particular, el mayor problema en ciencias de la computación consiste en responder al siguiente problema de decisión: ¿P=NP?



Ahora, nuestra tarea consta en escoger un problema NP-completo. Pero como es en equipo, estamos a la espera de los demas integrantes para poder escoger el problema.

Entonces que es NP-completo?


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 NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico.


Ejemplos de problemas NP-Completos


Existe una lista de 21 Problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos, y que cumplen la característica en común de que todos ellos pertenecen a la clase de complejidad de los NP-completos. Esta lista fue elaborada en 1972 por el informático teórico Richard Karp, en su trabajo seminal "Reducibility Among Combinatorial Problems" (Reducibilidad entre Problemas Combinatorios), como profundización del trabajo de Stephen Cook, quien en 1971 había demostrado uno de los resultados más importantes y pioneros de la complejidad computacional: la NP-completitud del Problema de satisfacibilidad boole.



Tras un tiempo se descubrió que muchos de estos problemas podían ser resueltos si su enunciado se particularizaba a unas ciertas clases, o podían ser resueltos aproximadamente con un error máximo de un cierto porcentaje. Sin embargo David Zuckerman demostró en 1996 que cada uno de estos 21 problemas tiene una versión restringida de optimización que es no aproximable a menos que P = NP, demostrando que la versión de la reducción, dada por Karp, generaliza un tipo específico de reducción por aproximación.

Soluciones Aproximadas

Actualmente, todos los algoritmos conocidos para problemas NP-completos utilizan tiempo exponencial con respecto al tamaño de la entrada. Se desconoce si hay algoritmos más rápidos, por lo cual, para resolver un problema NP-completo de tamaño arbitrario, se utiliza uno de los siguientes enfoques:
  • Aproximación: Un algoritmo que rápidamente encuentra una solución no necesariamente óptima, pero dentro de un cierto rango de error. En algunos casos, encontrar una buena aproximación es suficiente para resolver el problema, pero no todos los problemas NP-completos tienen algoritmos de aproximación.
  • Probabilístico: Un algoritmo probabilístico utiliza aleatoriedad para obtener en promedio una buena solución al problema planteado con una pequeña probabilidad de fallar, para una distribución de los datos de entrada dada.
  • Restricciones: Restringiendo la estructura de las entradas se pueden encontrar algoritmos más rápidos.
  • Casos particulares: Puede ocurrir que se reconozcan casos particulares del problema para los cuales existen soluciones rápidas.
  • 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.
  • 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. Las aproximaciones metaheurísticas suelen ser empleadas.




Comentarios

Entradas populares de este blog

Pequeño Juego con LEDS y Dip Switch

Siguiendo con los mini-proyectos, lo que quería hacer originalmente era un tipo "candado" con push-button y LEDs, el objetivo seria, meter la combinacion de botones correcta y los LEDS encendería por un motivo practico, en forma de serpiente. El objetivo no cambio, pero por falta de "material" lo hice con un dip switch de X entradas(depende de que tan grande quieras la combinación). CONOCIMIENTOS(max. 7 estrellas): Electronica:     ★ ★ Programación: ★ ★ Juego de Combinación + LEDs El programa es un poco mas complicado que el mini-proyecto pasado , pero aun asi es basico. Guardamos las salidas de los LEDs en un arreglo, despues con los valores recibidos y comparados de los dip switch jugamos con los LEDś. Hardware Requerido (1) Arduino Uno (6) LED (8) Resistencias 330 Ω (1) Dip Switch Circuito Usamos las salidas del ARduino 2-7 para los LEDS Usamos la salida A5, A4 para el dip switch Para hacer prender los LEDS tienes que encontrar la

Tarea #5 - Codigo Hamming - Python

Codigo hamming Liga al repo Teoria segun wikipedia Antes de los códigos Hamming se utilizaron ciertos códigos detectores de error, como lo fueron el código linteing, pero ninguno llegó a ser tan eficaz como los de Hamming. A continuación se describen algunos de estos códigos. Paridad   La   paridad   consiste en añadir un bit, denominado   bit de paridad , que indique si el número de los bits de valor 1 en los datos precedentes es par o impar. Si un solo bit cambiara por error en la transmisión, el mensaje cambiará de paridad y el error se puede detectar (nótese que el bit donde se produzca el error puede ser el mismo bit de paridad). La convención más común es que un valor de paridad   1   indica que hay un número impar de unos en los datos, y un valor de paridad de   0   indica que hay un número par de unos en los datos. info. completa y un vídeo que me ayudo mucho para esta tarea: (TIENEN QUE VERLO - OBLIGATORIO) http://www.youtube.com/watch?v=xiDPFm9PeLU Impleme

Potenciometro + pushboton + led

Bueno, estos días he estado practicando con los ejemplos de la pagina de Arduino , algunos que me llamaron la atención los voy a compartir, por supuesto con modificaciones. Nivel de conocimientos: Electronica:        ★   Programació n :    ★    Potenciometro + push-boton = LEDintensidad El mini-proyecto es controlar la intensidad de un LED mediante un potenciometro el cual combinado con push-botton para prenderlo o apagarlo. Hardware Requerido (1) Arduino UNO (1) Potenciometro (1) Push-boton (1) LED (1) Resistencia 330 Ω Circuito Conectamos el LED al PIN 9 del Arduino Conectamos el PUSH_BOTON al PIN ANOLOGICO 0 (A0) Conectamos el POTENCIOMETRO al PIN ANOLOGICO 1 (A1) El funcionamiento del circuito es basico, mientras tengas pulsado el Push-Boton el LED se mantendrá encendido y con el pontenciometro controlas la intensidad del LED. Código Video