• Categories
• Teoría de la complejidad computacional
• Algoritmos
• Informática
• Ciencias de la computación teórica
• Informática

Citation preview

Página Principal ► AUTOMATAS Y LENGUAJES FORMALES 301405A_474 ► Entorno de seguimiento y evaluación del aprendizaje ► Fase 5 - Reflexionar sobre el tema Comenzado el lunes, 26 de noviembre de 2018, 20:22 Estado Finalizado Finalizado en lunes, 26 de noviembre de 2018, 21:06 Tiempo empleado 44 minutos 27 segundos Puntos 12,3/15,0 Calificación 40,8 de 50,0 (82%) Comentario - Puntuación alta. Buen exámen Pregunta

1

El comportamiento de la siguiente máquina de Turing (MT) es:

Finalizado Puntúa 1,0 sobre 1,0

Seleccione una o más de una: a. No acepta cadenas de unos seguidos. Debe al menos existir un cero b. Al recorrer solo cadenas de unos , la cabeza lectora se posiciona en el extremo más izquierdo c. El autómata se puede comportar como transductor d. Para cadenas que terminen en "0", siempre devolverá 1

Pregunta

2

Teniendo el siguiente automata a pila se puede decir que lee las cadenas de:

Finalizado Puntúa 1,0 sobre 1,0

Seleccione una: a. babaa b. Todas las anteriores c. bbababab d. Lamda

3

Finalizado

Acerca de los problemas de HALTING, seleccione dos definiciones válidas para esa teoría:

Puntúa 1,0 sobre 1,0

Seleccione una o más de una:

Pregunta

a. Estos problemas los solucionan las máquinas de Pila combinadas con AF por contener una memoria que le da mayor capacidad de análisis. b. Es un problema que puede tener solución pero tiene un bucle infinito que no soluciona la MT. c. El problema de “Halting” es el primer problema indecidible mediante máquinas de Turing. d. Corresponde a problemas que tienen solución pero no se pueden representar por un algoritmo

Pregunta

4

Finalizado Puntúa 1,0 sobre 1,0

La decodificación para canales con ruido usando las técnicas de codificación convolucional, se hace mediante el algoritmo de Viterbi. El objetivo de aplicar este método es: Seleccione una: a. Que los bits redundantes que acompañan al dato, ayuden a detectar y corregir errores en la transmisión. El método separa los bits redundantes y muestra el dato. b. Reducir la cantidad de transiciones y cálculos cuando se presentan los bits redundantes y datos codificados. c. Encontrar el último estado que posee el error. d. Identificar la mayor cantidad de bits de control para compararlos con los bits de datos.

Pregunta

5

Finalizado Puntúa 1,0 sobre 1,0

En el campo de la complejidad algorítmica (problemas de algoritmos y de lógica) se presenta la “Decibilidad de teorías lógicas”. Una técnica para resolver problemas de este tipo es reducir un problema a otro para comprobar si tiene o no solución efectiva. Al hacer uso de esta estrategia en el caso que la respuesta sea negativa, se da: Seleccione una: a. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, entonces este nuevo problema tampoco tendrá solución efectiva. b. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, se determina la clase de complejidad siendo esta la solución c. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, se convierte en un problema parcialmente soluble (existe una Máquina de Turing que resuelve el problema, pero puede no parar) d. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, entonces es probable que solo se solucione usando una Máquina de Turing (MT).

Pregunta

6

Finalizado Puntúa 0,0 sobre 1,0

1.Evalúe si a siguiente Máquina de Turing (MT) e identifique que característica es propia de ella: Para M = (K, ∑, ⌠, q0, F, B,∂) dondeK = {q0,q1,q2,q3,q4} , F=q4 , ∑ = {a,b}, ⌠={M,N,Џ}

Seleccione una: a. Reconoce {a potencia "n" b potencia "m" : n ˃ 2 ; m ˃ 1 } b. Reconoce {a potencia "n" b potencia "n" : n ≥ 1} c. Reconoce {a potencia "n" b potencia "m" : n ˃ 1 ; m ˃ 2 } d. Reconoce {a potencia "n" b potencia "n" : n ˃ 1}

Pregunta

7

Finalizado Puntúa 1,0 sobre 1,0

Seleccione dos opciones: Una que identifique: El número de estados posibles para un diagrama de estados Otra que identifique: Los pares codificados en un codificador convolucional de ratio 1/2 Seleccione una o más de una: a. Los pares codificados son cuatro (4). es decir 8 bits b. El número de estados es: 2( potencia k(m-1)) Dónde: K= la secuencia en cantidad de bits que van a entrar al codificador. m= la memoria del codificador ( es restringida) n = es una salida codificada (número de bits). c. Los pares codificados son ocho (8). es decir 16 bits d. El número de estados es: 2( potencia k(n-1)) Dónde: K= es el número de bits de la cadena a evaluar (antes de ser codificada). m= la memoria del codificador ( es restringida) n = es una salida codificada (número de bits). Si K =1 ; n= 3. El total de estados es cuatro.

Pregunta

8

Finalizado

Dadas las siguientes tres máquinas (A,B,C) y determine qué características son válidas en su análisis:

Puntúa 1,0 sobre 1,0

Seleccione una: a. Para que la máquina "C" se comporte como transductor, necesita que el estado q0 también sea final. b. La máquina B demuestra que una MT se puede comportar como transductor c. Las máquinas "A" y "C" son AFND d. Todas las máquinas (A,B,C) se comportan como MT y como transductores

Pregunta

9

El comportamiento de la siguiente Máquina de Turing (MT) es:

Finalizado Puntúa 0,5 sobre 1,0

Seleccione una o más de una: a. La máquina tiene un mal diseño. No acepta las cadenas por que no se ha definido un tope de cinta. b. La máquina recorre todas las a´s que entren y borra una "a" una hasta que encuentra un símbolo blanco en la cinta y acepta la cadena c. La cinta siempre escribirá una "a" menos que la cantidad de "a" s de la cadena que reconoce. d. La máquina entra e un bucle indefinido

Pregunta

10

Finalizado

Identifique que características aplican al análisis que haga de las siguientes dos Máquinas de turing (MT).

Puntúa 1,0 sobre 1,0

Seleccione una: a. La MT (B) no acepta cadenas vacías b. La MT(A) se comporta como un transductor c. La MT(B), se comporta como un transductor d. La MT(B) para cada cadena válida que lee, al final del cálculo deja la cinta o escribe en la cinta los mismos símbolos (cadena) que está reconociendo como entrada

Pregunta

11

Finalizado Puntúa 0,8 sobre 1,0

Máquina de Turing (MT) de dos direcciones: Una Máquina de Turing con una cinta infinita en un sentido puede simular una Máquina de Turing con la cinta infinita en los dos sentidos. Sea M una Máquina de Turing con una cinta infinita en los dos sentidos, entonces: Para que se logre o se dé esta máquina se debe cumplir: Seleccione una o más de una: a. La cinta superior contiene información correspondiente a la parte derecha de la cinta M a partir de un punto de referencia dado. b. La Máquina de Turing M que tiene una Cinta Infinita en un sentido, puede simular a M si tiene una cinta con dos pistas. c. La pista inferior contiene la parte izquierda de la cinta M (en orden inverso). d. La MT multicinta puede reconocer el mismo lenguaje que una MT de una sola cinta.

Pregunta

12

Finalizado

Con respecto al siguiente autómata, evalúa según su análisis sus propiedades de “Determinismo o No determinismo”

Puntúa 0,0 sobre 1,0

Seleccione una: a. Es un AFND y el estado que lo caracteriza como tal es q1 b. Es un AFD porque no hay símbolos del alfabeto que se repitan o que generen ambigüedad desde la salida por cada estado. c. Si el AF tiene una cadena vacía, necesariamente lo caracteriza como un AFND d. Es un AFND y el estado que lo caracteriza como tal es q2.

Pregunta

13

Finalizado

Dadas las siguientes tres máquinas (A,B,C) y determine qué características son válidas en su análisis:

Puntúa 1,0 sobre 1,0

Seleccione una: a. Todas las máquinas (A,B,C) se comportan como MT y como transductores b. La máquina B demuestra que una MT se puede comportar como transductor c. Las máquinas "A" y "C" son AFND d. Para que la máquina "C" se comporte como transductor, necesita que el estado q0 también sea final.

Pregunta

14

Una cadena acpetada por la siguiente maquina de turing es:

Finalizado Puntúa 1,0 sobre 1,0

Seleccione una: a. xxyyyyyyy b. xyyyyx c. yxy d. xxyyxy

Pregunta

15

Una de las características del método de Reducibilidad de Turing es:

Finalizado Puntúa 1,0 sobre 1,0

Seleccione una: a. La reducibilidad siempre solucionará un solo problema b. Método que permite la solución de cualquier problema.. c. Método que indica como solucionando un problema puede ser el inicio de la solución de otro con similares características d. El método no garantiza la solución de ningún problema pero si su decibilidad