control de lectura_capitulo 10 - Mauricio axel 20

Vista previa del material en texto

Lenguajes y autómatas 1 
INSTITUTO TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE ACAPULCO
Ingeniería en sistemas computacionales
Lenguajes y autómatas 1
Control de lectura 
10.-Problemas intratables
Profesor: Bedolla Solano Silvestre
López Anselmo Mauricio Axel 
CONTROL: 18320904
10.-Problemas intratables
Resumen.
vamos a presentar la teoría de la “intratabilidad”; es decir, las técnicas que demuestran que existen problemas que no pueden resolverse en un tiempo polinómico. Vamos a empezar con un problema concreto (la cuestión de si es posible satisfacer una expresión booleana; es decir, que la cuestión sea verdadera para ciertas asignaciones de los valores de verdad TRUE y FALSE a sus variables). Este problema desempeña el mismo papel para los problemas intratables que L u o el PCP desempeñan para los problemas indecidibles. Es decir, empezamos con el “Teorema de Cook”, que establece que la satisfacibilidad de las fórmulas booleanas no se puede decidir en un tiempo polinómico.
Las clases P y NP
En esta sección vamos a presentar los conceptos básicos de la teoría de la intratabilidad: las clases P y NP de problemas resolubles en tiempo polinómico mediante máquinas de Turing deterministas y no deterministas, respectivamente, y la técnica de reducción en tiempo polinómico. También vamos a definir el concepto de “NP-completo”, una propiedad que tienen determinados problemas de NP. Se trata de problemas como mínimo tan complejos (salvo diferencias polinómicas de tiempo) como cualquier problema de NP.
 Ejemplo: algoritmo de Kruskal
Probablemente esté familiarizado con muchos problemas para los que existen soluciones eficientes; quizá, haya estudiado algunos en un curso sobre estructuras de datos y algoritmos. Generalmente, estos problemas son de clase P. Vamos a considerar uno de estos problemas: determinar el árbol de recubrimiento de peso mínimo de un grafo.MWSR, minimum-weight spanning tree.Informalmente, interpretamos los grafos como diagramas como el mostrado en la Figura 10.1. En este grafo de ejemplo, los nodos están numerados de 1–4 y se muestran los arcos dibujados entre los pares de nodos. Cada arco tiene un peso, que es un entero. Un árbol de recubrimiento es un subconjunto de los arcos tales que todos los nodos están conectados a través de dichos arcos, sin que exista ningún ciclo. en este caso, está formado por los tres arcos dibujados con líneas más gruesas. Un árbol de recubrimiento de peso mínimo es aquel que tiene la menor suma total posible de los pesos de los arcos de todos los árboles de recubrimiento. Existe un “voraz” algoritmo bien conocido, denominado algoritmo de Kruskal,que permite determinar el árbol de recubrimiento de peso mínimo. He aquí un esquema informal de las ideas en las que se basa:1. Para cada nodo, elegir la componente conexa en la que aparece el nodo, utilizando cualesquiera de los arcos del árbol que hayan sido seleccionados hasta el momento. Inicialmente,no hay seleccionado ningún arco, por lo que todos los nodos formarán por sí mismos una componente conexa.2. Considerar el arco de menor peso que aún no se haya tenido en cuenta y romper las ligaduras como se desee. Si este arco conecta dos nodos que actualmente pertenecen a componentes conexas diferentes,entonces:a) Seleccionar dicho arco para el árbol de recubrimiento y b) Unir las dos componentes conexas, cambiando el número de componente de todos los nodos de una de las dos componentes, para que sea el mismo que el número de componente de la otra. Si, por el contrario, el arco seleccionado conecta dos nodos de la misma componente, entonces este arco no pertenece al árbol de recubrimiento, porque crearía un ciclo.
Bibliografías.
2008 por PEARSON EDUCACIÓN S.A.Ribera del Loira, 2828042 Madrid
Introducción a la teoría de autómatas, lenguajes y computaciónHopcroft, J. E.; Motwani, R.; Ullman, J. D.
Página 1 | 1
Acapulco Gro. 10 de diciembre de 2020