Metodologias Datawerehouse
Páginas: 2 (288 palabras)
Publicado: 26 de noviembre de 2012
Explique qué es una máquina de turing no determinista
Máquina de Turing indeterminista o no determinista.
Una máquina de Turing indeterminista se define de la formaesperada. En cada punto en una computación la máquina puede proceder de acuerdo a varias posibilidades. La función de transición para una máquina de Turing indeterminista tiene laforma
δ: Q x Γ → P(Q x Γ x { L, R })
En general, un cálculo, en una máquina no determinista, es un árbol de descripciones instantáneas (DI), en lugar de ser una secuencialineal de DI, que es el caso de las máquinas deterministas.
Explique qué es la transformación polinómica
En teoría de la complejidad computacional, una Transformaciónpolinomial, también conocida como una reducción de Karp, es una forma de reducir un problema de decisión en otro de forma que cualquier algoritmo que resuelva el primer problemaproduzca inmediatamente una solución al segundo, por un coste polinómico.
Explique qué son los problemas NP-Completo.
En teoría de la complejidad computacional, la clase decomplejidad 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 puededecir 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 unasolución polinómica para un problema NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico.
LA CLASE NP contiene los problemas de decisión queson resueltos por una MT no determinista en tiempo polinómico y de ahí su nombre: Non-Deterministic Polynomial-time.
Diego Monsalve Cárdenas
Análisis de Algoritmo.
Máquina de Turing indeterminista o no determinista.
Una máquina de Turing indeterminista se define de la formaesperada. En cada punto en una computación la máquina puede proceder de acuerdo a varias posibilidades. La función de transición para una máquina de Turing indeterminista tiene laforma
δ: Q x Γ → P(Q x Γ x { L, R })
En general, un cálculo, en una máquina no determinista, es un árbol de descripciones instantáneas (DI), en lugar de ser una secuencialineal de DI, que es el caso de las máquinas deterministas.
Explique qué es la transformación polinómica
En teoría de la complejidad computacional, una Transformaciónpolinomial, también conocida como una reducción de Karp, es una forma de reducir un problema de decisión en otro de forma que cualquier algoritmo que resuelva el primer problemaproduzca inmediatamente una solución al segundo, por un coste polinómico.
Explique qué son los problemas NP-Completo.
En teoría de la complejidad computacional, la clase decomplejidad 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 puededecir 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 unasolución polinómica para un problema NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico.
LA CLASE NP contiene los problemas de decisión queson resueltos por una MT no determinista en tiempo polinómico y de ahí su nombre: Non-Deterministic Polynomial-time.
Diego Monsalve Cárdenas
Análisis de Algoritmo.
Leer documento completo
Regístrate para leer el documento completo.