Complejidad

Solo disponible en BuenasTareas
  • Páginas : 6 (1450 palabras )
  • Descarga(s) : 0
  • Publicado : 24 de febrero de 2011
Leer documento completo
Vista previa del texto
Complejidad Computacional

Objetivo: Medir la complejidad computacional de un problema. Vale decir: Medir la cantidad de recursos computacionales necesarios para solucionar un problema. - Tiempo. - Espacio. - ... Para hacer esto primero tenemos que introducir la noci´n de o problema.
1

Problemas de decisi´n o

Alfabeto A: Conjunto finito de s´ ımbolos. - Ejemplo: A = {0, 1}. Palabra w:Secuencia finita de s´ ımbolos de A. - Ejemplo: w = 01101. A∗ : Conjunto de todas las palabras construidas con s´ ımbolos de A. Lenguaje L: Conjunto de palabras. - Ejemplo: L = {0n 1n | n ∈ N}.
2

Problemas de decisi´n o
Problema de decisi´n asociado a un lenguaje L: Dado w ∈ A∗ , o decidir si w ∈ L. Ejemplo: Podemos ver SAT como un problema de decisi´n. o
Supongamos que P = {p, q}: - A = {p,q, ¬, ∧, ∨, →, ↔, (, )} Algunas palabras de A∗ representan f´rmulas de L(P ), mientras que o otras tales como ¬¬ y p¬q ∧ ∧ ∨ q no representan f´rmulas. o - SAT = {w ∈ A∗ | w representa una f´rmula de L(P ) y w es o satisfacible}. Ejercicio: Represente el problema de 3-coloraci´n de grafos como un o problema de decisi´n. o
3

Complejidad de un problema de decisi´n o
La complejidad de unlenguaje L es la complejidad del problema de decisi´n asociado a L. o ¿Cu´ndo decimos que L puede ser solucionado eficientemente? a - Cuando existe un algoritmo eficiente que decide L.
Ejercicio: Muestre que L = {w ∈ {0, 1}∗ | n´mero de 0s y 1s en w es el u mismo} puede ser resuelto eficientemente.

¿Cu´ndo decimos que L es un problema dif´ a ıcil? - Cuando no existe un algoritmo eficiente que decide L.4

M´quinas de Turing a
¿C´mo podemos demostrar que un problema es dif´ o ıcil? - Para hacer esto, primero tenemos que formalizar la noci´n de o algoritmo. ¿Qu´ es un algoritmo? ¿Podemos formalizar este concepto? e - M´quinas de Turing: Intento por formalizar este concepto. a ¿Podemos demostrar que las m´quinas de Turing capturan la a noci´n de algoritmo? o - No, el concepto de algoritmo esintuitivo.
5

M´quinas de Turing a
¿Por qu´ creemos que las m´quinas de Turing son una buena e a formalizaci´n del concepto de algoritmo? o - Porque cada programa de una m´quina de Turing puede ser a implementado. - Porque todos los algoritmos conocidos han podido ser implementados en m´quinas de Turing. a - Porque todos los otros intentos por formalizar este concepto fueron reducidos a lasm´quinas de Turing. a
- Los mejores intentos resultaron ser equivalentes a las m´quinas a de Turing. - Todos los intentos “razonables” fueron reducidos eficientemente.

- Tesis de Church: Algoritmo = M´quina de Turing. a
6

M´quinas de Turing: Componentes a

Dado: Alfabeto A que no contiene s´ ımbolo especial B. Componentes: - Memoria: Arreglo infinito (en ambas direcciones) que en cadaposici´n almacena un s´ o ımbolo de A ∪ {B}. - Control: Conjunto finitos de estados, una cabeza lectora, un estado inicial y un conjunto de estados finales. - Programa: Conjunto de instrucciones.

7

M´quinas de Turing: Funcionamiento a

Inicialmente:
- La m´quina recibe como entrada una palabra w. a - Coloca esta palabra en alguna parte del arreglo. En las posiciones restantes el arreglo contienes´ ımbolo blanco B. - La cabeza lectora se coloca en la primera posici´n de w y la o m´quina queda en el estado inicial q0 . a

8

M´quinas de Turing: Funcionamiento a

En cada paso:
- La m´quina lee el s´ a ımbolo a en la celda apuntada por la cabeza lectora y determina en que estado q se encuentra. - Busca en el programa una instrucci´n para (q, a). Si esta instrucci´n o o no existe,entonces la m´quina se detiene. a - Si la instrucci´n existe, entonces la ejecuta: Escribe un s´ o ımbolo en la posici´n apuntada por la cabeza lectora, pasa a un nuevo estado o y mueve la cabeza lectora a la derecha o a la izquierda.

Si la m´quina se detiene en un estado final, entonces la m´quina a a acepta w.
9

M´quinas de Turing: Formalizaci´n a o

M´quina de Turing: (Q, A, q0 , δ, F...
tracking img