Totales Evaluaciones i424f

Act 12: Lección Evaluativa Unidad No. 3 Revisión del intento 1 Finalizar revisión Comenzado el Completado el Tiempo empleado Puntos Calificación Comentario -

sábado, 10 de mayo de 2014, 00:27 sábado, 10 de mayo de 2014, 00:48 20 minutos 45 segundos 9/10 27 de un máximo de 30 (90%) Correcto: Contestó la totalidad de las preguntas.

Question1 Puntos: 1

Dado los siguientes tres codificadores convolucionales, diseñados para trabajar de forma lineal secuencial redundante: Se da como entrada el bit “1” en el codificador 1. Haga el recorrido completo hasta llegar a la salida del codificador 3. Los bits de salida codificados finales son: Tenga en cuenta que a partir del codificador 2, los bits de salida o entrada (según el caso) se deben sobrescribir o reemplazar.

Seleccione una respuesta. a. 00 b. 11 c. 01 d. 10 Correcto

Puntos para este envío: 1/1. Question2

Puntos: 1

Una Máquina de Turing (MT) se puede comportar como un aceptador de lenguaje, de la misma forma que lo hace un Autómata finito (AF) o un Autómata de Pila (AP) así: Colocando una cadena ω en la cinta, situando la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena ω y al poner en marcha la máquina a partir de su estado inicial. Entonces ω es aceptada si, después de una secuencia de movimientos, la MT llega a un estado final y para.

Que aspectos son válidos para el comportamiento de una MT..? Seleccione al menos una respuesta. a. Es válido empezar el diseño de una MT por el diseño de un AF. Ambos son aceptadores de lenguajes. b. Para rechazar una cadena que no es aceptable, lo único que hay que hacer es evitar que se llegue a un estado final. c. La MT es un mecanismo abstracto avanzado que tiene el mismo poder computacional que las máquinas reales. d. Se pueden combinar dos Máquinas de Turing (MT) permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece. Correcto

Puntos para este envío: 1/1. Question3 Puntos: 1

Cuando se tratan los PROBLEMAS INSOLUBLES PARA LA TEORIA DE LENGUAJES, se presentan los “Problemas de decisión” (PD).

Que aspectos en análisis son válidos para apoyar esta teoría Seleccione al menos una respuesta. a. Se puede decir que un lenguaje es decidible por que existe una MT que los puede reconocer. b. Si se presenta un lenguaje decidible, es por que hay un algoritmo que la MT reconoce. c. Un PD podría ser aquél formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”. Hay problemas de decisión de tipo “soluble”, “parcialmente soluble” e “insoluble d. Mientras que los lenguajes computables son una infinidad numerable, los lenguajes no computables son una infinidad no numerable. Correcto

Puntos para este envío: 1/1. Question4 Puntos: 1

Los PROBLEMAS DE HALTING hacen referencia a: (Seleccione las opciones verdaderas). Seleccione al menos una respuesta. a. El problema de la parada o problema de la detención es de hecho soluble y la Teoría de la Computación lo definió como tal

b. El problema de “Halting” es el primer problema indecidible mediante maquinas de Turing c. El problema de tipo "insoluble" define que hay un algoritmo que lo soluciona pero que no se puede llevar a una MT o una máquina abstracta. d. Equivale a construir un programa que te diga si un problema de ordenador finaliza alguna vez o no (entrando a un bucle infinito, por ejemplo)

El problema de “Halting” es el primer problema indecidible mediante máquinas de Turing. Equivale a construir un programa que te diga si un problema de ordenador finaliza alguna vez o no (entrando a un bucle infinito, por ejemplo) Correcto

Puntos para este envío: 1/1. Question5 Puntos: 1

Indique cuál de las siguientes afirmaciones es cierta con referencia a las Máquinas de Turing: Seleccione al menos una respuesta. a. El diseño de las MT básicamente es el de un autómata finito pero un Autómata con mayor poder de reconocimiento y proceso de lenguajes, que tomas y fusiona aspectos de un PDA. b. Cualquier lenguaje puede ser reconocido por una máquina de Turing c. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena d. El diseño de una MT es procedimentalmente sencillo para programar lenguajes de máquinas reales. Correcto

Puntos para este envío: 1/1. Question6 Puntos: 1

Indique que características asocian particularidades o semejanzas válidas entre las MT y las computadoras reales. Seleccione al menos una respuesta. a. En las máquinas reales están definidos procesos de manera jerárquica. En las MT estos procesos están definidos por el número de estados. b. Los computadores electrónicos, basados en la arquitectura Von Neumann así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una Máquina de Turing (MT) si dispusieran de recursos ilimitados de tiempo y espacio. c. Las MUT son de un solo propósito. Las máquinas reales interpretan muchos programas escritos en diferentes lenguajes (multipropósito). d. Los lenguajes de programación, tienen a lo sumo el mismo poder de expresión que el de los programas para una Máquina de Turing (MT) y en la práctica no todos lo alcanzan. Correcto

Puntos para este envío: 1/1. Question7 Puntos: 1

De los modelos creados para realizar cómputos y desarrollar problemas, es válido afirmar: Seleccione una respuesta. a. La MT no es un modelo Computable ya que solo se basa en simulación. b. Las funciones computables hacen referencia o son iguales a afirmar que son modelos computables. c. Los modelos propuestos por Hilbert, solucionan cualquier problema "No soluble" d. Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado

Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado. Su creador, el matemático inglés Alan Turing (1912-1954) estaba convencido de que no existía un algoritmo para el problema de decisión planteado por Hilbert y su intención era demostrar dicha no existencia. El modelo en el que se inspiró fue el de una persona real llevando a cabo un cálculo mecánico, por ejemplo una multiplicación de dos grandes números en el sistema decimal. Correcto

Puntos para este envío: 1/1. Question8 Puntos: 1

De las siguientes características marque dos de las que corresponden con la cinta de una Máquina de Turing Seleccione al menos una respuesta. a. Puede contener un caracter por celda b. Cinta Finita hacia la derecha, por que al extremo izquierdo siempre esta un topeo carácter blanco. c. Se puede escribir en ella d. Cinta Infinita hacia la izquierda

La máquina de Turing (abreviado MT) tiene, como los autómatas finitos, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacios con el caracter blanco Correcto

Puntos para este envío: 1/1. Question9 Puntos: 1

Dado los siguientes tres codificadores convolucionales, diseñados para trabajar de forma lineal secuencial redundante: Se da como entrada el bit “1” en el codificador 1. Haga el recorrido completo hasta llegar a la salida del codificador 3 y determine el valor de “m” los bits que quedan en la memoria del código de longitud restringida: Tenga en cuenta que a partir del codificador 2, los bits de salida o entrada (según el caso) se deben sobrescribir o reemplazar.

Seleccione una respuesta. a. 100 b. 001 c. 110 d. 010 Incorrecto

Puntos para este envío: 0/1. Question10 Puntos: 1

Los problemas indecidibles, son también parte del estudio de Autómatas y lenguajes Formales. La indecibilidad de estos problemas lleva a ratificar afirmaciones que han sido demostradas mediante algoritmos complejos computables que concluyen en afirmaciones como: Seleccione una respuesta. a. Decidir si un lenguaje que se genera es vacío o no, es un problema que sí tiene solución por una MT.

b. Las MT por ser la máquina abstracta más poderosa, soluciona cualquier problema que en teoría sea indecidible. c. Hay infinitos problemas para los que no se va a tener una MT que los resuelva (ni siquiera los reconozca). d. Con un computador real, se puede determinar con certeza cualquier problema en el sentido si es decidible o no.

Una MT que los resuelva (ni siquiera los reconozca). También se ha formulado la tesis de Church-Turing, que determina el límite de los computadores actuales Correcto

Puntos para este envío: 1/1. Finalizar revisión Usted se ha autentificado como NISER CHADI MOSQUERA (Salir)

301405A

Usted está aquí

    

campus13_20141 / ► 301405A / ► Cuestionarios / ► Act 13: Quiz 3 Unidad No. 3 / ► Revisión del intento 1

Act 13: Quiz 3 Unidad No. 3 Revisión del intento 1 Finalizar revisión Comenzado el

sábado, 10 de mayo de 2014, 00:56

Completado el

sábado, 10 de mayo de 2014, 01:54

Tiempo empleado Puntos Calificación

58 minutos 54 segundos 13/15 26 de un máximo de 30 (87%)

Question1 Puntos: 1

E número de estados posibles para un diagrama de estados está dado por: Seleccione una respuesta. a. 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). b. 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. c. 2( potencia k(m-1)) Dónde: K= es el número de bits de la cadena a evaluar (antes de ser codificada). m= la salida del codificador Si K =1 ; m= 3. El total de estados es cuatro. d. 2( potencia n) 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). Para un codificador convolucional de ratio R = ½ co K=1 El total de estados es cuatro. Correcto

Puntos para este envío: 1/1. Question2 Puntos: 1

Una de las características del método de Reducibilidad de Turing es: Seleccione al menos una respuesta. a. El método no hace referencia a como se solucionan dos o mas problemas simultáneamente b. El método determina como la solución de un problema, puede llevar a solucionar otro c. El método no garantiza la solución de ningún problema pero si su decibilidad

Usted está aquí

    

campus13_20141 / ► 301405A / ► Cuestionarios / ► Act 13: Quiz 3 Unidad No. 3 / ► Revisión del intento 1

Act 13: Quiz 3 Unidad No. 3 Revisión del intento 1 Finalizar revisión Comenzado el

sábado, 10 de mayo de 2014, 00:56

Completado el

sábado, 10 de mayo de 2014, 01:54

Tiempo empleado Puntos Calificación

58 minutos 54 segundos 13/15 26 de un máximo de 30 (87%)

Question1 Puntos: 1

E número de estados posibles para un diagrama de estados está dado por: Seleccione una respuesta. a. 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). b. 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. c. 2( potencia k(m-1)) Dónde: K= es el número de bits de la cadena a evaluar (antes de ser codificada). m= la salida del codificador Si K =1 ; m= 3. El total de estados es cuatro. d. 2( potencia n) 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). Para un codificador convolucional de ratio R = ½ co K=1 El total de estados es cuatro. Correcto

Puntos para este envío: 1/1. Question2 Puntos: 1

Una de las características del método de Reducibilidad de Turing es: Seleccione al menos una respuesta. a. El método no hace referencia a como se solucionan dos o mas problemas simultáneamente b. El método determina como la solución de un problema, puede llevar a solucionar otro c. El método no garantiza la solución de ningún problema pero si su decibilidad

Act 12: Lección Evaluativa Unidad No. 3 Revisión del intento 1 Finalizar revisión Comenzado el Completado el Tiempo empleado Puntos Calificación Comentario -

viernes, 9 de mayo de 2014, 21:57 viernes, 9 de mayo de 2014, 22:56 59 minutos 7 segundos 8/10 24 de un máximo de 30 (80%) Correcto: Contestó la totalidad de las preguntas.

Question1 Puntos: 1

De los modelos creados para realizar cómputos y desarrollar problemas, es válido afirmar: Seleccione una respuesta. a. La MT no es un modelo Computable ya que solo se basa en simulación. b. Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado c. Los modelos propuestos por Hilbert, solucionan cualquier problema "No soluble" d. Las funciones computables hacen referencia o son iguales a afirmar que son modelos computables.

Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado. Su creador, el matemático inglés Alan Turing (1912-1954) estaba convencido de que no existía un algoritmo para el problema de decisión planteado por Hilbert y su intención era demostrar dicha no existencia. El modelo en el que se inspiró fue el de una persona real llevando a cabo un cálculo mecánico, por ejemplo una multiplicación de dos grandes números en el sistema decimal. Incorrecto

Puntos para este envío: 0/1. Question2 Puntos: 1

Una Máquina de Turing (MT) se puede comportar como un aceptador de lenguaje, de la misma forma que lo hace un Autómata finito (AF) o un Autómata de Pila (AP) así: Colocando una cadena ω en la cinta, situando la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena ω y al poner en marcha la máquina a partir de su estado inicial. Entonces ω es aceptada si, después de una secuencia de movimientos, la MT llega a un estado final y para.

Que aspectos son válidos para el comportamiento de una MT..? Seleccione al menos una respuesta.

Act 12: Lección Evaluativa Unidad No. 3 Revisión del intento 1 Finalizar revisión

Comenzado el

viernes, 9 de mayo de 2014, 21:57

Completado el

viernes, 9 de mayo de 2014, 22:56

Tiempo empleado Puntos Calificación Comentario -

59 minutos 7 segundos 8/10 24 de un máximo de 30 (80%) Correcto: Contestó la totalidad de las preguntas.

Question1 Puntos: 1

De los modelos creados para realizar cómputos y desarrollar problemas, es válido afirmar: Seleccione una respuesta. a. La MT no es un modelo Computable ya que solo se basa en simulación.

b. Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado

c. Los modelos propuestos por Hilbert, solucionan cualquier problema "No soluble"

d. Las funciones computables hacen referencia o son iguales a afirmar que son modelos computables.

Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado. Su creador, el matemático inglés Alan Turing (1912-1954) estaba convencido de que no existía un algoritmo para el problema de decisión planteado por Hilbert y su intención era demostrar dicha no existencia. El modelo en el que se inspiró fue el de una persona real llevando a cabo un cálculo mecánico, por ejemplo una multiplicación de dos grandes números en el sistema decimal. Incorrecto

Puntos para este envío: 0/1.

Question2 Puntos: 1

Una Máquina de Turing (MT) se puede comportar como un aceptador de lenguaje, de la misma forma que lo hace un Autómata finito (AF) o un Autómata de Pila (AP) así: Colocando una cadena ω en la cinta, situando la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena ω y al poner en marcha la máquina a partir de su estado inicial. Entonces ω es aceptada si, después de una secuencia de movimientos, la MT llega a un estado final y para.

Que aspectos son válidos para el comportamiento de una MT..? Seleccione al menos una respuesta. a. Es válido empezar el diseño de una MT por el diseño de un AF. Ambos son aceptadores de lenguajes.

b. Se pueden combinar dos Máquinas de Turing (MT) permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece.

c. La MT es un mecanismo abstracto avanzado que tiene el mismo poder computacional que las máquinas reales.

d. Para rechazar una cadena que no es aceptable, lo único que hay que hacer es evitar que se llegue a un estado final. Correcto

Puntos para este envío: 1/1. Question3 Puntos: 1

Un ascensor sin memoria de un edificio de cuatro plantas puede describirse: Seleccione una respuesta. a. Mediante un autómata finito

b. Mediante un autómata de pila, pero no mediante un autómata finito

c. Mediante una máquina de Turing, pero no mediante un autómata de pila

d. No es un problema soluble. Es un problema de decisión

Al no tener memoria, el ascensor es una máquina que experimenta una transición de estado como función exclusiva del estado en que se encuentra y el evento que recibe (botón pulsado por un ).

Correcto

Puntos para este envío: 1/1. Question4 Puntos: 1

Indique que características asocian particularidades o semejanzas válidas entre las MT y las computadoras reales. Seleccione al menos una respuesta. a. En las máquinas reales están definidos procesos de manera jerárquica. En las MT estos procesos están definidos por el número de estados.

b. Las MUT son de un solo propósito. Las máquinas reales interpretan muchos programas escritos en diferentes lenguajes (multipropósito).

c. Los computadores electrónicos, basados en la arquitectura Von Neumann así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una Máquina de Turing (MT) si dispusieran de recursos ilimitados de tiempo y espacio.

d. Los lenguajes de programación, tienen a lo sumo el mismo poder de expresión que el de los programas para una Máquina de Turing (MT) y en la práctica no todos lo alcanzan. Correcto

Puntos para este envío: 1/1. Question5 Puntos: 1

Dado los siguientes tres codificadores convolucionales, diseñados para trabajar de forma lineal secuencial redundante: Se da como entrada el bit “1” en el codificador 1. Haga el recorrido completo hasta llegar a la salida del codificador 3. Los bits de salida codificados finales son: Tenga en cuenta que a partir del codificador 2, los bits de salida o entrada (según el caso) se deben sobrescribir o reemplazar.

Seleccione una respuesta. a. 00

b. 01

c. 11

d. 10

Correcto

Puntos para este envío: 1/1. Question6 Puntos: 1

Cuando se tratan los PROBLEMAS INSOLUBLES PARA LA TEORIA DE LENGUAJES, se presentan los “Problemas de decisión” (PD).

Que aspectos en análisis son válidos para apoyar esta teoría Seleccione al menos una respuesta. a. Un PD podría ser aquél formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”. Hay problemas de decisión de tipo “soluble”, “parcialmente soluble” e “insoluble

b. Mientras que los lenguajes computables son una infinidad numerable, los lenguajes no computables son una infinidad no numerable.

c. Si se presenta un lenguaje decidible, es por que hay un algoritmo que la MT reconoce.

d. Se puede decir que un lenguaje es decidible por que existe una MT que los puede reconocer. Correcto

Puntos para este envío: 1/1. Question7 Puntos: 1

Un código convolucional se diseña cuando a partir de registros de desplazamiento lineal. Los códigos convolucionales, suelen describirse mediante: Seleccione una respuesta. a. Árboles y diagramas de estados

b. Autómatas finitos (grafos). Máquinas de estados

c. Autómatas finitos (grafos). Máquinas de estados

d. Árboles, Trellis y Diagrama de estados.

Correcto

Puntos para este envío: 1/1. Question8 Puntos: 1

Indique cuál de las siguientes afirmaciones es cierta con referencia a las Máquinas de Turing: Seleccione al menos una respuesta. a. Cualquier lenguaje puede ser reconocido por una máquina de Turing

b. El diseño de una MT es procedimentalmente sencillo para programar lenguajes de máquinas reales.

c. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena

d. El diseño de las MT básicamente es el de un autómata finito pero un Autómata con mayor poder de reconocimiento y proceso de lenguajes, que tomas y fusiona aspectos de un PDA. Correcto

Puntos para este envío: 1/1. Question9 Puntos: 1

Los problemas indecidibles, son también parte del estudio de Autómatas y lenguajes Formales. La indecibilidad de estos problemas lleva a ratificar afirmaciones que han sido demostradas mediante algoritmos complejos computables que concluyen en afirmaciones como: Seleccione una respuesta. a. Decidir si un lenguaje que se genera es vacío o no, es un problema que sí tiene solución por una MT.

b. Hay infinitos problemas para los que no se va a tener una MT que los resuelva (ni siquiera los reconozca).

c. Las MT por ser la máquina abstracta más poderosa, soluciona cualquier problema que en teoría sea indecidible.

d. Con un computador real, se puede determinar con certeza cualquier problema en el sentido si es decidible o no.

Una MT que los resuelva (ni siquiera los reconozca). También se ha formulado la tesis de Church-Turing, que determina el límite de los computadores actuales Correcto

Puntos para este envío: 1/1. Question10 Puntos: 1

Con que configuración de cinta se detendrá la máquina de Turing mostrada a continuación si comienza con la cinta configurada

xxxΔΔΔ . Asuma el orden con que están numerados los estados para el proceso.

como

La "V" indica la posición en la que estaría la máquina. Para el caso de los s+ímbolos "x" estaría representado como (x)

Seleccione una respuesta. a. xxxVΔΔ

b. xxxΔVV

c. xx(x)ΔVΔ

d. xxxΔΔV

Incorrecto

Puntos para este envío: 0/1. Finalizar revisión

Usted se ha autentificado como CARLOS GEOVANY MORAN (Salir)

Act 13: Quiz 3 Unidad No. 3 Revisión del intento 1 Finalizar revisión

Comenzado el

viernes, 9 de mayo de 2014, 23:05

Completado el

sábado, 10 de mayo de 2014, 00:03

Tiempo empleado Puntos Calificación

58 minutos 58 segundos 12/15 24 de un máximo de 30 (80%)

Question1 Puntos: 1

Un diagrama de estados puede representar un codificador convolucional porque: Seleccione al menos una respuesta. a. Se comporta como una máquina con diferentes estados

b. Es acotado y tiene memoria infinita.

c. El diagrama de estados tiene transiciones y maneja memoria finita

d. Es lineal y los desplazamientos de los bits redundantes se pueden realizaren ambas direcciones. Correcto

Puntos para este envío: 1/1. Question2 Puntos: 1

El diagrama de Viterbi, dentro de sus interacciones o validación de datos define el cambio de estados de acuerdo a los datos de entrada. Identifique el dato de entrada correcto y su cambio de estado con el dato de salida codificado correctamente. Seleccione una respuesta. a. Posición de estado (01) con entrada de dato “0”. Cambio de estado 10 con salida de dato codificado {11} b. Posición de estado (00) con entrada de dato “1”. Cambio de estado 00 con salida de dato codificado {01} c. Posición de estado (01) con entrada de dato “1”. Cambio de estado 10 con salida de dato codificado {00}

d. Posición de estado (11) con entrada de dato “0”. Cambio de estado 11 con salida de dato codificado {01} Incorrecto

Puntos para este envío: 0/1. Question3 Puntos: 1

Si se diseña una MT se está diseñando. Seleccione una respuesta. a. Se está diseñando un autómata finito que controla la cabeza y la cinta, el cual es un autómata con salida.

b. Se está diseñando una máquina universal que representa lenguajes generados pro gramáticas de tipo 2

c. Se está diseñando una AFND que puede tener lambda transiciones (dado este por su capacidad y potencia)

d. Se está diseñando una máquina abstracta sin memoria y sin procesos. Solo con cambios de estado.

Al diseñar una MT que acepte un cierto lenguaje, en realidad diseñamos el autómata finito que controla la cabeza y la cinta, el cual es un autómata con salida Así, podemos usar la notación gráfica utilizada para aquellos autómatas para indicar su funcionamiento. Incorrecto

Puntos para este envío: 0/1. Question4 Puntos: 1

Dependiendo de los diferentes tipos de Máquinas de Turing (MT), estas se comportan de manera diferente en la solución de problemas. Para una MT MULTIPISTA, indique una propiedad válida de esta. Seleccione una respuesta. a. La cinta está en un número infinito de k pistas. Por eso es MULTIPISTA

b. En esta MT no se inicializan las cintas por que tienen muchas pistas.

c. Por cada cinta , requiere de un estado de aceptación “halt”

d. La cinta esta dividida en un número finito de k pistas

Hay ciertos modelos de computación relacionados con las máquinas de Turing, que poseen el mismo potencial como reconocedor de lenguajes que el modelo básico. Dentro de esas modificaciones, una muy particular es la MULTIPISTA que resulta muy efectiva para solución de problemas extensos. Correcto

Puntos para este envío: 1/1. Question5 Puntos: 1

La característica por la que se definió o formuló una Maquina Universal de Turing (MUT) fue: Seleccione al menos una respuesta. a. Es una máquina que es capaz de simular cualquier otra máquina de Turing. (MT)

b. Simula cualquier lenguaje generado por una gramática dada.

c. La MUT se diseñó para simular algoritmos que solucionan problemas infinitos

d. Es una máquina programable, pues la entrada tiene el código de cualquier MT con sus datos de entrada. Correcto

Puntos para este envío: 1/1. Question6 Puntos: 1

Para las siguientes afirmaciones Indique cuál es verdadera: Seleccione una respuesta. a. Una máquina de Turing determinista puede meterse en un ciclo que se ejecute indefinidamente.

b. Un autómata de pila determinista nunca puede meterse en un ciclo que se ejecute indefinidamente

c. Un autómata finito nunca puede meterse en un ciclo que se ejecute indefinidamente

d. Una máquina de Turing multicinta nunca entrará en un bucle (ciclo que se ejecute indefinidamente.)

Los lenguajes formales que son aceptados por una máquina de Turing son exactamente aquellos que pueden ser generados por una gramática formal. El cálculo Lambda es una forma de definir funciones. Las funciones que pueden se computadas con el cálculo Lambda son exactamente aquellas que pueden ser computadas con una máquina de Turing. Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el cálculo Lambda son formalismos muy disímiles y fueron desarrollados por diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el mismo poder de expresión. Generalmente se toma esta notable coincidencia como evidencia de que la tesis de Church-Turing es cierta, que la afirmación de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo corresponde a la noción de cómputo en una máquina de Turing. Correcto

Puntos para este envío: 1/1. Question7 Puntos: 1

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 al menos una respuesta. a. La pista inferior y superior leen los datos simultáneamente en ambos sentidos. Luego y dependiendo de los estado repetitivos, se detiene una pista y continúa la que menos celdas tenga ocupada.

b. La pista inferior contiene la parte izquierda de la cinta M (en orden inverso).

c. La cinta superior contiene información correspondiente a la parte derecha de la cinta M a partir de un punto de referencia dado.

d. 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.

Hay otras definiciones de las máquinas de Turing que son equivalentes. Algunos de esos modelos alternativos son mucho más complicados aunque

todos tienen la misma potencia computacional (o de cálculo). Muchas de ellas dotan de mayor flexibilidad al diseño de una máquina de Turing que resuelva un problema en particular. Correcto

Puntos para este envío: 1/1. Question8 Puntos: 1

El caractér blanco que se ubica en la parte derecha de la cinta de una Máquina de Turing, está presente dada la condición de: Seleccione una respuesta. a. La cinta es infinita a la izquierda y finita a la derecha

b. La cinta es infinita a la derecha

c. La cinta es finita a la derecha y a la izquierda

d. La cinta es de solo lectura

La palabra de entrada en la MT está escrita inicialmente en la cinta, como es habitual en nuestros autómatas, pero iniciando a partir de la segunda posición de la cinta, siendo el primer cuadro un caracter blanco. Como la cinta es infinita, inicialmente toda la parte de la cinta a la derecha de la palabra de entrada está llena del caracter blanco Correcto

Puntos para este envío: 1/1. Question9 Puntos: 1

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

Seleccione una respuesta. 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 entra e un bucle indefinido

c. 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

d. La máquina recorre todas las a´s pero no se detiene

Correcto

Puntos para este envío: 1/1. Question10 Puntos: 1

Las funciones computables son usadas para: Seleccione una respuesta. a. Simular algoritmos con funciones modeladas

b. Definir algoritmos modelados.

c. Discutir computabilidad sin referirse a ningún modelo.

d. Definir funciones basados en modelos.

Las funciones computables son usadas para discutir computabilidad sin referirse a ningún modelo de computación concreto, como el de la máquina de Turing o el de la máquina de registros

Correcto

Puntos para este envío: 1/1. Question11 Puntos: 1

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 respuesta. a. Reducir la cantidad de transiciones y cálculos cuando se presentan los bits redundantes y datos codificados.

b. Identificar la mayor cantidad de bits de control para compararlos con los bits de datos.

c. 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.

d. Encontrar el último estado que posee el error.

La codificación convolucional se decodifica con ayuda del algoritmo de Viterbi. El proceso consiste en desechar algunos de todos los caminos posibles. Lo que se consigue aplicando este método es reducir el número de cálculos. Correcto

Puntos para este envío: 1/1. Question12 Puntos: 1

Cuando se realizan simulaciones ya sea con software con JFLAV o VAS o con cualquier herramienta de software que cumpla las bases de simulación de automatización, o acogiéndose a los teoremas y funciones propias de cada autómata, se puede afirmar: Seleccione una respuesta. a. Los autómatas (AFD,AFN) y los autómatas de pila (AFDP o AFPN) se pueden simular con máquinas de Turing.

b. La simulación no permite determinar el poder computacional de la máquina

c. La simulación de MT es posible solo si es una MT de una sola cinta. Para MT multicinta basta con cambiar el estado o salida final

d. La simulación de Autómatas de PILA no tiene en cuenta el manejo de memoria, sino el de estados.

La simulación de autómatas parte del principio básico de representar un autómata Finito. Correcto

Puntos para este envío: 1/1. Question13 Puntos: 1

Una analogía funcional, operacional de una Máquina de Turing con un componente físico real podría ser: Seleccione una respuesta. a. Un codificador secuencial con estados fijos pero con memoria (ej: codificador convolucional)

b. Sistemas de cómputo basados en arquitecturas como las de Neumann

c. Soluciones computacionales de arquitecturas híbridas de algoritmos infinitos.

d. Un compilador

Los computadores electrónicos, basados en la arquitectura Von Neumann así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una máquina de Turing si dispusieran de recursos ilimitados de tiempo y espacio. Como consecuencia, los lenguajes de programación tienen a lo sumo el mismo poder de expresión que el de los programas para una máquina de Turing y en la práctica no todos lo alcanzan. Los lenguajes con poder de expresión equivalente al de una máquina de Turing se denominan Turing completos Incorrecto

Puntos para este envío: 0/1. Question14 Puntos: 1

Dentro de los componentes de una máquina de Turing (MT), está el símbolo “blanco” B. El comportamiento de este símbolo es: Seleccione una respuesta.

a. También pertenece al alfabeto de cadenas a reconocer.

b. Indica un movimiento nulo de la cabeza lectora.

c. Aparece en todas las casillas excepto en aquellas que contienen los símbolos de entrada.

d. Están situados al extremo izquierdo de la cinta.

Corresponde a la formalización de las Máquinas de Turing (MT) como un séptuplo en la que hace parte el símbolo blanco. Correcto

Puntos para este envío: 1/1. Question15 Puntos: 1

Las máquinas de Turing (MT) son también aceptadoras de lenguajes. Analice si los lenguajes dados aplican a la tarea que cumplen estas máquinas Seleccione al menos una respuesta. a. El lenguaje {w pertenece {a,b}* | w contiene tantas a´s como b´s} es decidible por máquinas de Turing.

b. El lenguaje {w pertenece {a,b}* | w contiene tantas a´s como b´s} no es decidible por máquinas de Turing

c. El lenguaje {w pertenece {a,b}* | w contiene al menos una a} es decidible por máquinas de Turing.

d. El lenguaje {w pertenece {a,b}* | w contiene al menos una b} no es independiente del contexto y por tanto no es decidible por máquinas de Turing. Correcto

Puntos para este envío: 1/1. Finalizar revisión

Usted se ha autentificado como CARLOS GEOVANY MORAN (Salir)

301405A

Act 11: Reconocimiento UnidaAd No. 3 Revisión del intento 1 Finalizar revisión Comenzado el Completado el Tiempo empleado Puntos Calificación Comentario -

domingo, 4 de mayo de 2014, 23:37 lunes, 5 de mayo de 2014, 00:34 56 minutos 48 segundos 5.5/6 9.2 de un máximo de 10 (92%) Correcto: Contestó la totalidad de las preguntas.

Question1 Puntos: 1

Cuáles diferencias entre una computadora Real y una máquina de Turing (MT) son verdaderas: Seleccione al menos una respuesta. a. En una MT el nº de estados depende del algoritmo. b. En cuanto al orden de ejecución de las instrucciones, En la estructura Von Neumann el secuenciamiento lo marca el orden de colocación de las instrucciones en la memoria interna y viene asegurado por el contador de programa. c. En una MT el orden de ejecución de las instrucciones no está definido. d. En una computadora, el número de estados viene representado por el contenido de la memoria. Correcto

Puntos para este envío: 1/1. Question2 Puntos: 1

A las computadoras reales y las MT se les asocian muchas similitudes y diferencias: Cuáles diferencias entre una computadora Real y una máquina de Turing (MT) son verdaderas: Seleccione al menos una respuesta. a. En una computadora, el número de estados viene representado por el contenido de la memoria. b. En una MT el Número de estados depende de la cadena, palabra o dato que lea. c. En una MT el orden de ejecución de las instrucciones no necesariamente debe estar definido. d. En cuanto al orden de ejecución de las instrucciones, En la estructura Von Neumann el secuenciamiento lo marca el orden de colocación de las instrucciones en la memoria interna y viene asegurado por el contador de programa. Parcialmente correcto

Puntos para este envío: 0.5/1.

Question3 Puntos: 1

Cuando se transmite información, las variables a evaluar, medir, seguir y monitorear son: Seleccione al menos una respuesta. a. La veracidad de los datos en todo su sentido. b. La velocidad que se mantenga. c. Redundancia d. Nivel de ruido Correcto

Puntos para este envío: 1/1. Question4 Puntos: 1

La codificación redundante tiene como objetivo introducir símbolos para asegurar la veracidad en la trasmisión. Esto se logra por medio de algoritmos que aseguran la veracidad de la información transmitida procurando no perder velocidad en la trasmisión. Los algoritmos para la veracidad son: Seleccione una respuesta. a. Los de codificación de fuente: b. Los de codificación de ruido c. Los de codificación de canal d. Los de codificación AWGN Correcto

Puntos para este envío: 1/1. Question5 Puntos: 1

Una de las técnicas usadas que permite determinar la indecibilidad en algunos problemas computacionales es: Seleccione una respuesta. a. Usando el método de las “Funciones computables” b. Usando el método de “Halting” c. Usando el método de Reducción “Reducibilidad de Turing”

d. Usando el método de “ Decibilidad de Teorías Lógicas” Correcto

Puntos para este envío: 1/1. Question6 Puntos: 1

De la teoría de la codificación se puede decir: (señale las apreciaciones verdaderas): Seleccione al menos una respuesta. a. Los algoritmos matemáticos son métodos para lograr que la información se adapte mejor a las condiciones de las transmisiones. b. La veracidad se consigue introduciendo una redundancia c. La codificación de canales con ruido se trata únicamente con la codificación de canal. d. La codificación es una parte de la teoría de información. Correcto

Puntos para este envío: 1/1. Finalizar revisión Usted se ha autentificado como NISER CHADI MOSQUERA (Salir)

301405A

Usted está aquí

    

campus13_20141 / ► 301405A / ► Cuestionarios / ► Act 12: Lección Evaluativa Unidad No. 3 / ► Revisión del intento 1

Act 12: Lección Evaluativaa Unidad No. 3 Revisión del intento 1 Finalizar revisión Comenzado el Completado el Tiempo empleado Puntos Calificación Comentario -

Question1 Puntos: 1

sábado, 10 de mayo de 2014, 00:27 sábado, 10 de mayo de 2014, 00:48 20 minutos 45 segundos 9/10 27 de un máximo de 30 (90%) Correcto: Contestó la totalidad de las preguntas.

Dado los siguientes tres codificadores convolucionales, diseñados para trabajar de forma lineal secuencial redundante: Se da como entrada el bit “1” en el codificador 1. Haga el recorrido completo hasta llegar a la salida del codificador 3. Los bits de salida codificados finales son: Tenga en cuenta que a partir del codificador 2, los bits de salida o entrada (según el caso) se deben sobrescribir o reemplazar.

Seleccione una respuesta. a. 00 b. 11 c. 01 d. 10 Correcto

Puntos para este envío: 1/1. Question2 Puntos: 1

Una Máquina de Turing (MT) se puede comportar como un aceptador de lenguaje, de la misma forma que lo hace un Autómata finito (AF) o un Autómata de Pila (AP) así: Colocando una cadena ω en la cinta, situando la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena ω y al poner en marcha la máquina a partir de su estado inicial. Entonces ω es aceptada si, después de una secuencia de movimientos, la MT llega a un estado final y para.

Que aspectos son válidos para el comportamiento de una MT..? Seleccione al menos una respuesta. a. Es válido empezar el diseño de una MT por el diseño de un AF. Ambos son aceptadores de lenguajes. b. Para rechazar una cadena que no es aceptable, lo único que hay que hacer es evitar que se llegue a un estado final.

c. La MT es un mecanismo abstracto avanzado que tiene el mismo poder computacional que las máquinas reales. d. Se pueden combinar dos Máquinas de Turing (MT) permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece. Correcto

Puntos para este envío: 1/1. Question3 Puntos: 1

Cuando se tratan los PROBLEMAS INSOLUBLES PARA LA TEORIA DE LENGUAJES, se presentan los “Problemas de decisión” (PD).

Que aspectos en análisis son válidos para apoyar esta teoría Seleccione al menos una respuesta. a. Se puede decir que un lenguaje es decidible por que existe una MT que los puede reconocer. b. Si se presenta un lenguaje decidible, es por que hay un algoritmo que la MT reconoce. c. Un PD podría ser aquél formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”. Hay problemas de decisión de tipo “soluble”, “parcialmente soluble” e “insoluble d. Mientras que los lenguajes computables son una infinidad numerable, los lenguajes no computables son una infinidad no numerable. Correcto

Puntos para este envío: 1/1. Question4 Puntos: 1

Los PROBLEMAS DE HALTING hacen referencia a: (Seleccione las opciones verdaderas). Seleccione al menos una respuesta. a. El problema de la parada o problema de la detención es de hecho soluble y la Teoría de la Computación lo definió como tal b. El problema de “Halting” es el primer problema indecidible mediante maquinas de Turing c. El problema de tipo "insoluble" define que hay un algoritmo que lo soluciona pero que no se puede llevar a una MT o una máquina abstracta. d. Equivale a construir un programa que te diga si un problema de ordenador finaliza alguna vez o no (entrando a un bucle infinito, por ejemplo)

El problema de “Halting” es el primer problema indecidible mediante máquinas de Turing. Equivale a construir un programa que te diga si un problema de ordenador finaliza alguna vez o no (entrando a un bucle infinito, por ejemplo) Correcto

Puntos para este envío: 1/1. Question5 Puntos: 1

Indique cuál de las siguientes afirmaciones es cierta con referencia a las Máquinas de Turing: Seleccione al menos una respuesta. a. El diseño de las MT básicamente es el de un autómata finito pero un Autómata con mayor poder de reconocimiento y proceso de lenguajes, que tomas y fusiona aspectos de un PDA. b. Cualquier lenguaje puede ser reconocido por una máquina de Turing c. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena d. El diseño de una MT es procedimentalmente sencillo para programar lenguajes de máquinas reales. Correcto

Puntos para este envío: 1/1. Question6 Puntos: 1

Indique que características asocian particularidades o semejanzas válidas entre las MT y las computadoras reales. Seleccione al menos una respuesta. a. En las máquinas reales están definidos procesos de manera jerárquica. En las MT estos procesos están definidos por el número de estados. b. Los computadores electrónicos, basados en la arquitectura Von Neumann así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una Máquina de Turing (MT) si dispusieran de recursos ilimitados de tiempo y espacio. c. Las MUT son de un solo propósito. Las máquinas reales interpretan muchos programas escritos en diferentes lenguajes (multipropósito). d. Los lenguajes de programación, tienen a lo sumo el mismo poder de expresión que el de los programas para una Máquina de Turing (MT) y en la práctica no todos lo alcanzan. Correcto

Puntos para este envío: 1/1. Question7 Puntos: 1

De los modelos creados para realizar cómputos y desarrollar problemas, es válido afirmar: Seleccione una respuesta. a. La MT no es un modelo Computable ya que solo se basa en simulación. b. Las funciones computables hacen referencia o son iguales a afirmar que son modelos computables. c. Los modelos propuestos por Hilbert, solucionan cualquier problema "No soluble" d. Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado

Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado. Su creador, el matemático inglés Alan Turing (1912-1954) estaba convencido de que no existía un algoritmo para el problema de decisión planteado por Hilbert y su intención era demostrar dicha no existencia. El modelo en el que se inspiró fue el de una persona real llevando a cabo un cálculo mecánico, por ejemplo una multiplicación de dos grandes números en el sistema decimal. Correcto

Puntos para este envío: 1/1. Question8 Puntos: 1

De las siguientes características marque dos de las que corresponden con la cinta de una Máquina de Turing Seleccione al menos una respuesta. a. Puede contener un caracter por celda b. Cinta Finita hacia la derecha, por que al extremo izquierdo siempre esta un topeo carácter blanco. c. Se puede escribir en ella d. Cinta Infinita hacia la izquierda

La máquina de Turing (abreviado MT) tiene, como los autómatas finitos, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacios con el caracter blanco Correcto

Puntos para este envío: 1/1. Question9 Puntos: 1

Dado los siguientes tres codificadores convolucionales, diseñados para trabajar de forma lineal secuencial redundante: Se da como entrada el bit “1” en el codificador 1. Haga el recorrido completo hasta llegar a la salida del codificador 3 y determine el valor de “m” los bits que quedan en la memoria del código de longitud restringida: Tenga en cuenta que a partir del codificador 2, los bits de salida o entrada (según el caso) se deben sobrescribir o reemplazar.

Seleccione una respuesta. a. 100 b. 001 c. 110 d. 010 Incorrecto

Puntos para este envío: 0/1. Question10 Puntos: 1

Los problemas indecidibles, son también parte del estudio de Autómatas y lenguajes Formales. La indecibilidad de estos problemas lleva a ratificar afirmaciones que han sido demostradas mediante algoritmos complejos computables que concluyen en afirmaciones como: Seleccione una respuesta. a. Decidir si un lenguaje que se genera es vacío o no, es un problema que sí tiene solución por una MT. b. Las MT por ser la máquina abstracta más poderosa, soluciona cualquier problema que en teoría sea indecidible. c. Hay infinitos problemas para los que no se va a tener una MT que los resuelva (ni siquiera los reconozca). d. Con un computador real, se puede determinar con certeza cualquier problema en el sentido si es decidible o no.

Una MT que los resuelva (ni siquiera los reconozca). También se ha formulado la tesis de Church-Turing, que determina el límite de los computadores actuales Correcto

Puntos para este envío: 1/1. Finalizar revisión Usted se ha autentificado como NISER CHADI MOSQUERA (Salir)

301405A

Act 13: Quiz 3 Unidad No. 3 Revisión del intento 1 Finalizar revisión

Comenzado el

sábado, 10 de mayo de 2014, 00:56

Completado el

sábado, 10 de mayo de 2014, 01:54

Tiempo empleado Puntos Calificación

58 minutos 54 segundos 13/15 26 de un máximo de 30 (87%)

Question1 Puntos: 1

E número de estados posibles para un diagrama de estados está dado por: Seleccione una respuesta. a. 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).

b. 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.

c. 2( potencia k(m-1)) Dónde: K= es el número de bits de la cadena a evaluar (antes de ser codificada). m= la salida del codificador Si K =1 ; m= 3. El total de estados es cuatro.

d. 2( potencia n) 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). Para un codificador convolucional de ratio R = ½ co K=1 El total de estados es cuatro.

Correcto

Puntos para este envío: 1/1. Question2 Puntos: 1

Una de las características del método de Reducibilidad de Turing es: Seleccione al menos una respuesta. a. El método no hace referencia a como se solucionan dos o mas problemas simultáneamente

b. El método determina como la solución de un problema, puede llevar a solucionar otro

c. El método no garantiza la solución de ningún problema pero si su decibilidad

d. El método soluciona un problema en un conjunto de varios problemas tratado de forma independiente.

La reducibilidad ha permitido llegar a determinar la indecibilidad en algunos problemas computacionales: Una manera más simple de determinar la indecibilidad es utilizando el método de reducción Correcto

Puntos para este envío: 1/1. Question3 Puntos: 1

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 respuesta. 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.

La codificación convolucional se decodifica con ayuda del algoritmo de Viterbi. El proceso consiste en desechar algunos de todos los caminos posibles. Lo que se consigue aplicando este método es reducir el número de cálculos. Correcto

Puntos para este envío: 1/1. Question4 Puntos: 1

Para las siguientes afirmaciones Indique cuál es verdadera: Seleccione una respuesta. a. Un autómata de pila determinista nunca puede meterse en un ciclo que se ejecute indefinidamente

b. Una máquina de Turing determinista puede meterse en un ciclo que se ejecute indefinidamente.

c. Una máquina de Turing multicinta nunca entrará en un bucle (ciclo que se ejecute indefinidamente.)

d. Un autómata finito nunca puede meterse en un ciclo que se ejecute indefinidamente

Los lenguajes formales que son aceptados por una máquina de Turing son exactamente aquellos que pueden ser generados por una gramática formal. El cálculo Lambda es una forma de definir funciones. Las funciones que pueden se computadas con el cálculo Lambda son exactamente aquellas que pueden ser computadas con una máquina de Turing. Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el cálculo Lambda son formalismos muy disímiles y fueron desarrollados por diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el mismo poder de expresión. Generalmente se toma esta notable coincidencia como evidencia de que la tesis de Church-Turing es cierta, que la afirmación de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo corresponde a la noción de cómputo en una máquina de Turing. Correcto

Puntos para este envío: 1/1. Question5 Puntos: 1

Las máquinas de Turing han ayudado a: Seleccione al menos una respuesta.

a. El modelo de máquina abstracta, su diseño fue basado la lógica y la teoría de las decisiones.

b. Poder reconocer y procesa mas lenguajes.

c. Demostrar que los lenguajes de programación no resuelven todos los problemas computacionales

d. Construir lenguajes de programación por ser tan sencillas en su diseño.

Los modelos abstractos de computación tienen su origen en los años 30, bastante antes de que existieran los ordenadores modernos, en el trabajo de los lógicos Church, Gödel, Kleene, Post, y (Alan Mathison Turing). Estos primeros trabajos han tenido una profunda influencia no solo en el desarrollo teórico de las Ciencias de la Computación, sino que muchos aspectos de la práctica de la computación que son ahora lugar común de los informáticos, fueron presagiados por ellos; incluyendo la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajes por estructuras formales basados en reglas de producción. Correcto

Puntos para este envío: 1/1. Question6 Puntos: 1

El siguiente dato: 01011101 se ha codificado con el codificador convolucional y su salida con errores leyendo de izquierda a derecha los pares han sido: 11 00 00 10 11 01 00 01 La distancia de haming “dh” encontradas en el dato codificado son (seleccione la correcta). (de izquierda a derecha)

Seleccione una respuesta. a. Para el par 2 dh= 2 Para el par 5 dh=2 Para el par 6 dh = 2

b. Para el par 2 dh= 2 Para el par 6 dh = 2

c. Para el par 2 dh= 1 Para el par 5 dh = 1 Para el par 6 dh=1 Para el par 7 dh =2

d. Para el par 2 dh= 1 Para el par 5 dh = 1 Para el par 6 dh = 2

Incorrecto

Puntos para este envío: 0/1. Question7 Puntos: 1

Cuando se realizan simulaciones ya sea con software con JFLAV o VAS o con cualquier herramienta de software que cumpla las bases de simulación de automatización, o acogiéndose a los teoremas y funciones propias de cada autómata, se puede afirmar: Seleccione una respuesta. a. La simulación no permite determinar el poder computacional de la máquina

b. La simulación de Autómatas de PILA no tiene en cuenta el manejo de memoria, sino el de estados.

c. Los autómatas (AFD,AFN) y los autómatas de pila (AFDP o AFPN) se pueden simular con máquinas de Turing.

d. La simulación de MT es posible solo si es una MT de una sola cinta. Para MT multicinta basta con cambiar el estado o salida final

La simulación de autómatas parte del principio básico de representar un autómata Finito. Correcto

Puntos para este envío: 1/1. Question8 Puntos: 1

Seleccione cuál de las siguientes situaciones no es posible cuando una máquina de Turing determinista examina una cadena: Seleccione una respuesta.

a. El problema de parada solo aplica a Máquinas de Turing no deterministas. Las Deterministas solucionan este problema

b. La máquina abandona los cálculos por no encontrar ninguna transición aplicable

c. Se produce una terminación anormal (es decir, la cabeza lectora se desplaza a la izquierda de la primera celda de la cinta)

d. La máquina no se detiene nunca

Ya que cualquier máquina de Turing determinista es también no determinista, es lógico que una máquina de Turing determinista se pueda simular mediante una no determinista. También una máquina de Turing determinista puede simular una no determinista. Por tanto, no se gana ninguna potencia adicional a causa del no determinismo. Correcto

Puntos para este envío: 1/1. Question9 Puntos: 1

La forma correcta de operar una Máquina de Turing (MT) es: Seleccione una respuesta. a. Inicialización de la Máquina / Introducir la cadena de entrada en la cinta / La cinta está en blanco para iniciar / Se pone la unidad de control en el estado inicial / Se posiciona la cabeza sobre la primera letra de la cadena introducida

b. Inicialización de la Máquina / Introducir la cadena de entrada en la cinta / La cinta está en blanco para iniciar / Se posiciona la cabeza sobre la primera letra de la cadena introducida / Se pone la unidad de control en el estado inicial

c. Inicialización de la Máquina / Se pone la unidad de control en el estado inicial / La cinta está en blanco / Introducir la cadena de entrada en la cinta / Se posiciona la cabeza sobre la primera letra de la cadena introducida

d. Inicialización de la Máquina / La cinta está en blanco / Introducir la cadena de entrada en la cinta / Se pone la unidad de control en el estado inicial / Se posiciona la cabeza sobre la primera letra de la cadena introducida

La máquina de Turing (abreviado MT) tiene, como los autómatas que hemos visto antes, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacios con el caracter blanco (que representaremos con “t”). La cinta no es infinita hacia la izquierda, por lo que

hay un cuadro de la cinta que es el extremo izquierdo, como en la figura En la MT la cabeza lectora es de lectura y escritura, por lo que la cinta puede ser modificada en curso de ejecución. Además, en la MT la cabeza se mueve bidireccionalmente (izquierda y derecha), por lo que puede pasar repetidas veces sobre un mismo segmento de la cinta. Correcto

Puntos para este envío: 1/1. Question10 Puntos: 1

Dentro de los componentes de una máquina de Turing (MT), está el símbolo “blanco” B. El comportamiento de este símbolo es: Seleccione una respuesta. a. Aparece en todas las casillas excepto en aquellas que contienen los símbolos de entrada.

b. También pertenece al alfabeto de cadenas a reconocer.

c. Indica un movimiento nulo de la cabeza lectora.

d. Están situados al extremo izquierdo de la cinta.

Corresponde a la formalización de las Máquinas de Turing (MT) como un séptuplo en la que hace parte el símbolo blanco. Correcto

Puntos para este envío: 1/1. Question11 Puntos: 1

La teoría de Shannon pudo comprobar que para canales ruidosos al considerar que existe una probabilidad de error en la transmisión de ráfagas de símbolos para cualquier velocidad, dentro de la capacidad del canal e independientemente del tipo de información que se envié.

Su técnica de detección de errores se basó en: Seleccione una respuesta. a. Reducir la cantidad de bits a transmitir fraccionándolos en paquetes.

b. Para canales con ruido, separar en fracciones paquetes de bits enviados por paridad.

c. Introducir bits redundantes dentro de una cadena.

d. Aumentarla velocidad de transmisión solo para bits con paridad 1

La teoría de la codificación redundante se basa en los principios que Shannon formuló para canales ruidosos al considerar que existe una probabilidad de error en la transmisión de ráfagas de símbolos para cualquier velocidad, dentro de la capacidad del canal e independientemente del tipo de información que se envié. Entonces, es indispensable saber cuáles de los bits recibidos están errados, especialmente si se requiere una altísima veracidad por la transmisión de datos Incorrecto

Puntos para este envío: 0/1. Question12 Puntos: 1

La máquina universal de Turing esta diseña para realizar cualquier calculo especifico – particular debido a que: Seleccione una respuesta. a. Las instrucciones se basan en una fase del algoritmo universal

b. Es capaz de ejecutar cualquier algoritmo

c. Parará cuando el cálculo sea indeterminado.

d. Es un intérprete de la información de salida

Esta máquina Universal no debe ser diseñada para realizar un cálculo específico, sino para procesar cualquier información (realizar cualquier cálculo específico -MT particular- sobre cualquier configuración inicial de entrada correcta para esa MT particular). Correcto

Puntos para este envío: 1/1. Question13

Puntos: 1

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 al menos una respuesta. a. La pista inferior contiene la parte izquierda de la cinta M (en orden inverso).

b. La pista inferior y superior leen los datos simultáneamente en ambos sentidos. Luego y dependiendo de los estado repetitivos, se detiene una pista y continúa la que menos celdas tenga ocupada.

c. 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.

d. La cinta superior contiene información correspondiente a la parte derecha de la cinta M a partir de un punto de referencia dado.

Hay otras definiciones de las máquinas de Turing que son equivalentes. Algunos de esos modelos alternativos son mucho más complicados aunque todos tienen la misma potencia computacional (o de cálculo). Muchas de ellas dotan de mayor flexibilidad al diseño de una máquina de Turing que resuelva un problema en particular. Correcto

Puntos para este envío: 1/1. Question14 Puntos: 1

Un diagrama de estados puede representar un codificador convolucional porque: Seleccione al menos una respuesta. a. El diagrama de estados tiene transiciones y maneja memoria finita

b. Se comporta como una máquina con diferentes estados

c. Es acotado y tiene memoria infinita.

d. Es lineal y los desplazamientos de los bits redundantes se pueden realizaren ambas direcciones. Correcto

Puntos para este envío: 1/1. Question15 Puntos: 1

Dado el siguiente codificador convolucional, asuma para un dato de entrada K = 01011101 con una m=3 iniciada en 000: Calcule el dato codificado “n” sin errores después de pasar por el codificador. El dato codificado es:

Seleccione una respuesta. a. 11 01 00 10 01 10 00 01

b. 11 11 00 10 11 00 11 01

c. 11 00 00 10 11 01 00 01

d. 11 10 00 10 01 01 00 01

Correcto

Puntos para este envío: 1/1.

Finalizar revisión

Usted se ha autentificado como NISER CHADI MOSQUERA (Salir)

Act 12: Lección Evaluativa Unidad No. 3 Revisión del intento 1 Finalizar revisión

Comenzado el

sábado, 10 de mayo de 2014, 03:01

Completado el

sábado, 10 de mayo de 2014, 03:31

Tiempo empleado Puntos Calificación Comentario -

29 minutos 47 segundos 9/10 27 de un máximo de 30 (90%) Correcto: Contestó la totalidad de las preguntas.

Question1 Puntos: 1

Un código convolucional se diseña cuando a partir de registros de desplazamiento lineal. Los códigos convolucionales, suelen describirse mediante: Seleccione una respuesta. a. Autómatas finitos (grafos). Máquinas de estados

b. Autómatas finitos (grafos). Máquinas de estados

c. Árboles y diagramas de estados

d. Árboles, Trellis y Diagrama de estados.

Correcto

Puntos para este envío: 1/1. Question2 Puntos: 1

Si iniciamos la máquina de Turing siguiente con la cadena yyxyxx

Seleccione una respuesta. a. La máquina acepta la cadena

b. Hay una terminación anormal.

c. La máquina solo acepta cadenas con números de símbolos pares

d. La máquina entra en un bucle y no termina nunca.

Decimos que en la MT se llega al “final de un cálculo” cuando se alcanza un estado especial llamado halt en el control finito, como resultado de una transición. Representaremos al halt por “h”. Al llegar al halt, se detiene la operación de la MT, y se acepta la palabra de entrada. Así, en la MT no hay estados finales. En cierto sentido el halt sería entonces el único estado final, sólo que además detiene la ejecución. Correcto

Puntos para este envío: 1/1. Question3

Puntos: 1

Acerca del tipo de cadenas que puede aceptar una Máquina de Turing, determine cuál afirmación es válida. Seleccione una respuesta. a. Por ser una máquina tan simple pero a la vez tan potente, resulta fácil que cualquier lenguaje puede ser reconocido por una máquina de Turing

b. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena

c. Cuando se desea que una MT no acepte una palabra, simplemente se debe configurar para que llegue a un estado halt de parada o stop.

d. Es posible que un lenguaje sea estructurado por frases pero no exista ninguna máquina de Turing que se detenga exclusivamente cuando las cadenas escritas en su cinta pertenezcan al lenguaje

Al diseñar una MT que acepte un cierto lenguaje, en realidad diseñamos el autómata finito que controla la cabeza y la cinta, el cual es un autómata con salida. Correcto

Puntos para este envío: 1/1. Question4 Puntos: 1

La Máquina de Turing, y un autómata finito, tienen similitudes como: Seleccione al menos una respuesta. a. Un cabezal de lectura y otro para escritura

b. Una cabeza lectora

c. Un alfabeto para la cinta y un alfabeto de entrada

d. Un control finito

Máquina de Turing (abreviado MT) tiene, como los autómatas que hemos visto antes, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada Correcto

Puntos para este envío: 1/1. Question5 Puntos: 1

De los modelos creados para realizar cómputos y desarrollar problemas, es válido afirmar: Seleccione una respuesta. a. Las funciones computables hacen referencia o son iguales a afirmar que son modelos computables.

b. La MT no es un modelo Computable ya que solo se basa en simulación.

c. Los modelos propuestos por Hilbert, solucionan cualquier problema "No soluble"

d. Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado

Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado. Su creador, el matemático inglés Alan Turing (1912-1954) estaba convencido de que no existía un algoritmo para el problema de decisión planteado por Hilbert y su intención era demostrar dicha no existencia. El modelo en el que se inspiró fue el de una persona real llevando a cabo un cálculo mecánico, por ejemplo una multiplicación de dos grandes números en el sistema decimal. Correcto

Puntos para este envío: 1/1. Question6 Puntos: 1

Una Máquina de Turing (MT) se puede comportar como un aceptador de lenguaje, de la misma forma que lo hace un Autómata finito (AF) o un Autómata de Pila (AP) así: Colocando una cadena ω en la cinta, situando la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena ω y al poner en marcha la máquina a partir de su estado inicial. Entonces ω es aceptada si, después de una secuencia de movimientos, la MT llega a un estado final y para.

Que aspectos son válidos para el comportamiento de una MT..? Seleccione al menos una respuesta.

a. Se pueden combinar dos Máquinas de Turing (MT) permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece.

b. Es válido empezar el diseño de una MT por el diseño de un AF. Ambos son aceptadores de lenguajes.

c. La MT es un mecanismo abstracto avanzado que tiene el mismo poder computacional que las máquinas reales.

d. Para rechazar una cadena que no es aceptable, lo único que hay que hacer es evitar que se llegue a un estado final. Correcto

Puntos para este envío: 1/1. Question7 Puntos: 1

Un ascensor sin memoria de un edificio de cuatro plantas puede describirse: Seleccione una respuesta. a. Mediante una máquina de Turing, pero no mediante un autómata de pila

b. Mediante un autómata finito

c. No es un problema soluble. Es un problema de decisión

d. Mediante un autómata de pila, pero no mediante un autómata finito

Al no tener memoria, el ascensor es una máquina que experimenta una transición de estado como función exclusiva del estado en que se encuentra y el evento que recibe (botón pulsado por un ). Correcto

Puntos para este envío: 1/1. Question8 Puntos: 1

De las siguientes características marque dos de las que corresponden con la cinta de una Máquina de Turing Seleccione al menos una respuesta.

a. Puede contener un caracter por celda

b. Se puede escribir en ella

c. Cinta Finita hacia la derecha, por que al extremo izquierdo siempre esta un topeo carácter blanco.

d. Cinta Infinita hacia la izquierda

La máquina de Turing (abreviado MT) tiene, como los autómatas finitos, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacios con el caracter blanco Correcto

Puntos para este envío: 1/1. Question9 Puntos: 1

Dado los siguientes tres codificadores convolucionales, diseñados para trabajar de forma lineal secuencial redundante: Se da como entrada el bit “1” en el codificador 1. Haga el recorrido completo hasta llegar a la salida del codificador 3 y determine el valor de “m” los bits que quedan en la memoria del código de longitud restringida: Tenga en cuenta que a partir del codificador 2, los bits de salida o entrada (según el caso) se deben sobrescribir o reemplazar.

Seleccione una respuesta. a. 100

b. 001

c. 010

d. 110

Incorrecto

Puntos para este envío: 0/1. Question10 Puntos: 1

Con que configuración de cinta se detendrá la máquina de Turing mostrada a continuación si comienza con la cinta configurada

xxxΔΔΔ . Asuma el orden con que están numerados los estados para el proceso.

como

La "V" indica la posición en la que estaría la máquina. Para el caso de los s+ímbolos "x" estaría representado como (x)

Seleccione una respuesta. a. xxxVΔΔ

b. xx(x)ΔVΔ

c. xxxΔVV

d. xxxΔΔV

Correcto

Puntos para este envío: 1/1. Finalizar revisión

Usted se ha autentificado como TOMAS DE AQUINO MORENO CORDOBA (Salir)