RESPUESTAS AUTOMATAS UNIDAD 3

1

Puntos: 1

Cuando se transmite información, las variables a evaluar, medir, seguir y monitorear son:

Seleccione al menos una respuesta.

	a. Redundancia
	b. Nivel de ruido
	c. La velocidad que se mantenga.
	d. La veracidad de los datos en todo su sentido.

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

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

	a. 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
	b. 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)
	c. 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).
	d. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, entonces este nuevo problema tampoco tendrá solución efectiva.

Incorrecto

Puntos para este envío: 0/1.

Question3

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 computadora, el número de estados viene representado por el contenido de la memoria.
	b. En una MT el orden de ejecución de las instrucciones no está definido.
	c. 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.
	d. En una MT el nº de estados depende del algoritmo.

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Un problema de decisión (PD) es aquel formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”. Para la Teoría de Lenguajes, un problema de decisión es “insoluble” cuando:

Seleccione al menos una respuesta.

	a. Si no existe un procedimiento efectivo para determinar si la propiedad es verdadera (no existe una Máquina de Turing MT).
	b. Si no existe un algoritmo total para determinar si la propiedad y objetivo del problema es verdadera.
	c. Si no se logra representar con un diagrama de Moore el problema.
	d. Existe un procedimiento definido que determina la ambigüedad del problema

Correcto

Puntos para este envío: 1/1.

Question5

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 codificación es una parte de la teoría de información.
	c. La codificación de canales con ruido se trata únicamente con la codificación de canal.
	d. La veracidad se consigue introduciendo una redundancia

Parcialmente correcto

Puntos para este envío: 0.7/1.

Question6

Puntos: 1

Analice la codificación de la siguiente Máquina: Si lee 0101 (de izquierda a derecha), la salida correspondiente es:

Seleccione una respuesta.

	a. 0110
	b. 0111
	c. 0011
	d. 0101

Correcto

Puntos para este envío: 1/1.

1

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. Cinta Infinita hacia la izquierda
	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. Puede contener un caracter por celda

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.

Question2

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. Hay infinitos problemas para los que no se va a tener una MT que los resuelva (ni siquiera los reconozca).
	b. Las MT por ser la máquina abstracta más poderosa, soluciona cualquier problema que en teoría sea indecidible.
	c. Decidir si un lenguaje que se genera es vacío o no, es un problema que sí tiene solución por una MT.
	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.

Question3

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. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena
	b. 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.
	c. Cualquier lenguaje puede ser reconocido por una máquina de Turing
	d. El diseño de una MT es procedimentalmente sencillo para programar lenguajes de máquinas reales.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question4

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, Trellis y Diagrama de estados.
	b. Autómatas finitos (grafos). Máquinas de estados
	c. Autómatas finitos (grafos). Máquinas de estados
	d. Árboles y diagramas de estados

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. 10
	c. 11
	d. 01

Correcto

Puntos para este envío: 1/1.

Question6

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. 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
	d. Los modelos propuestos por Hilbert, solucionan cualquier problema "No soluble"

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.

Question7

Puntos: 1

Señale los aspectos de diseño válidos de una Máquina de Turing (MT).

Seleccione al menos una respuesta.

	a. En una Máquina de Turing (MT) que usa una cinta que se extiende infinitamente en una única dirección, generalmente está extendida hacia la derecha.
	b. No está permitido realizar ningún movimiento hacia la izquierda a partir de la celda del extremo izquierdo.
	c. Una palabra de entrada a reconocer en una MT se escribe símbolo por símbolo en la cinta
	d. La Máquina Universal de Turing no debe ser diseñada para realizar un cálculo específico, sino para procesar cualquier información

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Con referencia alas (MT) Máquinas de Turing, indique cuál afirmación es cierta cuando de reconocer lenguajes se trata:

Seleccione una respuesta.

	a. Una Máquina de Turing (MT) acepta su entrada si, partiendo de la configuración inicial, durante el cómputo alcanza la configuración aceptadora.
	b. Una máquina de Turing (MT) cuyo estado inicial coincida con el estado de parada, acepta toda cadena.
	c. Cualquier Lenguaje puede ser reconocido por una Máquina de Turing (MT)
	d. Una Máquina de Turing (MT) no puede aceptar el lenguaje de palíndromos, por que entraría en un ciclo repetitivo sin encontrar un estado “Halt”.

Incorrecto

Puntos para este envío: 0/1.

Question9

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. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena
	b. 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.
	c. 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
	d. 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

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.

Question10

Puntos: 1

Un ascensor sin memoria de un edificio de cuatro plantas puede describirse:

Seleccione una respuesta.

	a. Mediante un autómata de pila, pero no mediante un autómata finito
	b. Mediante una máquina de Turing, pero no mediante un autómata de pila
	c. No es un problema soluble. Es un problema de decisión
	d. 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 usuario).

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

Dada la siguiente Máquina de Turing (MT), determine que afirmaciones son válidas para su análisis:

Seleccione al menos una respuesta.

	a. La máquina acepta palabras que empiezan con “a”
	b. Si la primera letra no es una “a” la MT cae en un ciclo infinito leyendo y escribiendo “a”
	c. Si la primera letra no es una “a”, la MT cae en un ciclo infinito leyendo y escribiendo “b”
	d. La máquina acepta palabras que empiezan con “b”

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

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

Seleccione al menos una respuesta.

	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

El concepto de problema indecidible o irresoluble se aplica a problemas de decisión, es decir, problemas a los que podemos decir si tienen solución o no. Dentro de estos problemas, existe un conjunto al que no le podemos asignar una respuesta, ni afirmativa ni negativa: no existe un algoritmo que nos permita determinar si el problema tiene solución.

Correcto

Puntos para este envío: 1/1.

Question3

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. Un compilador
	c. Soluciones computacionales de arquitecturas híbridas de algoritmos infinitos.
	d. Sistemas de cómputo basados en arquitecturas como las de Neumann

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.

Question4

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. Se produce una terminación anormal (es decir, la cabeza lectora se desplaza a la izquierda de la primera celda de la cinta)
	b. La máquina no se detiene nunca
	c. El problema de parada solo aplica a Máquinas de Turing no deterministas. Las Deterministas solucionan este problema
	d. La máquina abandona los cálculos por no encontrar ninguna transición aplicable

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.

Question5

Puntos: 1

Dada la siguiente Maquia de Turing (MT). Analice su comportamiento.

Seleccione al menos una respuesta.

	a. No es una maquina válida ya que no define un estado final que acepta unas cadenas (no interpreta un lenguaje definido).
	b. Si se convierte el estado q0 en final, aceptará todas las posibles combinaciones de {01}. Aceptará secuencias de ceros y uso.
	c. Es una máquina que solo acepta lenguajes regulares.
	d. Esta máquina de Turing que se comporta como transductor, porque simplemente genera una salida en la cinta.

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

Dentro de la teoría de la información, algunas de las labores identificadas de la “Decodificación” es

Seleccione al menos una respuesta.

	a. La detección y en algunos casos, la corrección de los errores usando los bits redundantes y algoritmos.
	b. Entrega al destinatario la información sin la redundancia.
	c. Seleccionar datos de etrada.
	d. Asignar espacios de memoria (definir estados en este caso).

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question7

Puntos: 1

Si se diseña una MT se está diseñando.

Seleccione una respuesta.

	a. Se está diseñando una AFND que puede tener lambda transiciones (dado este por su capacidad y potencia)
	b. Se está diseñando una máquina abstracta sin memoria y sin procesos. Solo con cambios de estado.
	c. Se está diseñando un autómata finito que controla la cabeza y la cinta, el cual es un autómata con salida.
	d. Se está diseñando una máquina universal que representa lenguajes generados pro gramáticas de tipo 2

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.

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Para las siguientes afirmaciones Indique cuál es verdadera:

Seleccione una respuesta.

	a. Una máquina de Turing multicinta nunca entrará en un bucle (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 determinista 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.

Question9

Puntos: 1

E número de estados posibles para un diagrama de estados está dado por:

Seleccione una respuesta.

	a. 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.
	b. 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.
	c. 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).
	d. 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.

Correcto

Puntos para este envío: 1/1.

Question10

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 MT es posible solo si es una MT de una sola cinta. Para MT multicinta basta con cambiar el estado o salida final
	c. La simulación de Autómatas de PILA no tiene en cuenta el manejo de memoria, sino el de estados.
	d. Los autómatas (AFD,AFN) y los autómatas de pila (AFDP o AFPN) se pueden simular con máquinas de Turing.

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.

Question11

Puntos: 1

La demostración de que había problemas que una máquina no podía resolver , obedece a:

Seleccione una respuesta.

	a. Halting
	b. Hilbert
	c. Church
	d. Greibach

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.

Question12

Puntos: 1

Un diagrama de estados puede representar un codificador convolucional porque:

Seleccione al menos una respuesta.

	a. Es acotado y tiene memoria infinita.
	b. El diagrama de estados tiene transiciones y maneja memoria finita
	c. Es lineal y los desplazamientos de los bits redundantes se pueden realizaren ambas direcciones.
	d. Se comporta como una máquina con diferentes estados

Correcto

Puntos para este envío: 1/1.

Question13

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. Encontrar el último estado que posee el error.
	b. 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.
	c. Reducir la cantidad de transiciones y cálculos cuando se presentan los bits redundantes y datos codificados.
	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.

Question14

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. Introducir bits redundantes dentro de una cadena.
	c. Para canales con ruido, separar en fracciones paquetes de bits enviados por paridad.
	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

Correcto

Puntos para este envío: 1/1.

Question15

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 un intérprete de la información de salida
	c. Parará cuando el cálculo sea indeterminado.
	d. Es capaz de ejecutar cualquier algoritmo

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.