• Document: Complejidad - Problemas NP-Completos Algoritmos y Estructuras de Datos III Teoría de Complejidad Un algoritmo eficiente es un algoritmo de complejidad polinomial. Un problema está bien res...
  • Size: 141.02 KB
  • Uploaded: 2021-09-13 02:34:23
  • Status: Successfully converted


Some snippets from your converted document:

Complejidad - Problemas NP-Completos Algoritmos y Estructuras de Datos III Teorı́a de Complejidad I Un algoritmo eficiente es un algoritmo de complejidad polinomial. I Un problema está bien resuelto si se conocen algoritmos eficientes para resolverlo. I El objetivo es clasificar los problemas según su complejidad. I Un problema de decisión es un problema cuya respuesta es sı́ o no. I La clasificación y el estudio de teorı́a de complejidad se hace para problemas de decisión. Distintas versiones de un problema de optimización Π Dada una instancia I del problema Π: I Versión de evaluación: Determinar el valor de una solución óptima de Π para I . I Versión de optimización: Encontrar una solución óptima del problema Π para I (de valor mı́nimo o máximo). I Versión de decisión: Dado un número k, ¿existe una solución factible S de Π para I tal que c(S) ≤ k si el problema es de minimización (o c(S) ≥ k si el problema es de maximización)? I Versión de localización: Dado un número k, determinar una solución factible S de Π para I tal que c(S) ≤ k. Ejemplo: Problema del viajante de comercio Dado un grafo G con longitudes asignadas a sus aristas: I Versión de evaluación: Determinar el valor de una solución óptima, o sea la longitud de un circuito hamiltoniano de G de longitud mı́nima. I Versión de optimización: Determinar un circuito hamiltoniano de G de longitud mı́nima. I Versión de decisión: Dado un número k, ¿existe un circuito hamiltoniano de G de longitud menor o igual a k? I Versión de localización: Dado un número k, determinar un circuito hamiltoniano de G de longitud menor o igual a k. Distintas versiones de un problema de optimización Π ¿Qué relación hay en la dificultad de resolver las distintas versiones de un mismo problema? Si resolvemos el problema de decisión, podemos en general: I Resolver el problema de evaluación usando búsqueda binaria sobre el parámetro k. I Resolver el problema de localización resolviendo el problema de decisión para el parámetro k para una versión reducida de la instancia. I Resolver el problema de optimización resolviendo el problema de decisión para el valor óptimo para una versión reducida de la instancia. Problemas intratables Definición: Un problema es intratable si no puede ser resuelto por algún algoritmo eficiente. Un problema puede ser intratable por distintos motivos: I El problema requiere una repuesta de longitud exponencial (ejemplo: pedir todos los circuitos hamiltonianos de longitud a lo sumo k). I El problema es indecidible (ejemplo: problema de la parada). I El problema es decidible pero no se conocen algoritmos polinomiales que lo resuelvan. Las clases P y NP Definiciones: I Un problema de decisión pertenece a la clase P (polinomial) si existe un algoritmo polinomial para resolverlo. I Un problema de decisión pertenece a la clase NP (polinomial no-determinı́sticamente) si dada una instancia de SI y evidencia de la misma, puede ser verificada en tiempo polinomial. Relaciones entre las clases: I P ⊆ NP I Problema abierto: ¿Es P = NP? (problema abierto más importante de teorı́a de la computación) Ejemplos de problemas en NP I Suma de enteros. I Multipliación de enteros. I Árbol generador mı́nimo. I Clique máxima. I Camino mı́nimo entre un par de nodos. I Problema del viajante de comercio. I Conjunto independiente de cardinal máximo. I Problema de satisfabilidad (SAT): Dado un conjunto de cláusulas C1 , . . . , Cm formadas por literales basados en las variables booleanas X = {x1 , . . . , xn }, determinar si hay una asignación de valores de verdad a las variables de X tal que la expresión C1 ∧ C2 ∧ . . . ∧ Cm sea verdadera. Máquinas de Turing no-determinı́sticas (MTND) Los componentes de una MTND son: I Cinta infinita dividida en celdas iguales que pueden contener un único sı́mbolo de un alfabeto finito Σ. Es la entrada. I Cabeza de lectura escritura que apunta a una de las celdas. I Un conjunto estados posibles Q. En Q hay un estado inicial q0 y al menos un estado final. En todo momento, la máquina debe estar en algun estado, llamamos al estado actual qi . I Una tabla de quintúplas T ⊂ Q × Σ × Q × Σ × {−1, +1, 0} que representa al programa. Máquinas de Turing no-determinı́sticas (MTND) La operatoria de una MTND: 1. lectura del sı́mbolo ti inscripto en

Recently converted files (publicly available):