Buenos para esta clase estuve investigando sobre los problemas de np completos yo elegí el problemas de las particiones ya que me pareció interesante la forma en que un disco duro puede ser divido.
Este tipo de algoritmos puede servir como por ejemplo particionar un disco duro e instalar dos sistemas operativos como por ejemplo uno de sus aplicaciones.
Bueno primero que nada tenemos que saber que es la complejidad computacional.
La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable. 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).
Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que ésta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.
Fuente
Problema de la partición es un problema NP-completo, que visto como un problema de decisión, consiste en decidir si, dado un multiconjunto de números enteros, puede éste ser particionado en dos "mitades" tal que sumando los elementos de cada una, ambas den como resultado la misma suma.
Más precisamente, dado un multiconjunto S de enteros: ¿existe alguna forma de particionar S en dos subconjuntos S1 y S2, tal que la suma de los elementos en S1 sea igual que la suma de los elementos en S2
El problema de partición es equivalente a un caso particular del problema de la suma de subconjuntos, el cual dice: dado un conjunto S de enteros, ¿existe algún subconjunto S1 de S cuyos elementos suman exactamente t /2, donde t es la suma de todos los elementos de S?
La equivalencia puede verse definiendo S2 como la diferencia
S − S1. Por lo tanto, la solución con programación dinámica existente para resolver el problema de suma de subconjuntos, utilizando tiempo pseudo-polinomial, también es aplicable al problema de partición.
Aquí les dejo una pagina interesante que encontré de los problemas de la particiones y de sodoku de una forma interactiva.
Aquí dejo otro link muy interesante me hubiera gustado hablar sobre ello pero creo que tendré que esperar para una futura entrada es sobre Reduction of the Three-Partition Problem y aquí les dejo este pdf muy bueno que viene hablando sobre ello.
Otro link muy bueno es un pdf que habla sobre problemas np completos y en también habla del problema de la partición.
Saludos...
También contiene un botón que es el que hace la acción de calcular el valor de las resistencias ya una vez seleccionado los colores:
