Teoría de la Computación: autómatas, computabilidad, conjuntos y relaciones

Informática y TelecomunicacionesActualizado el 8,61 KB

Resumen

Este documento recoge preguntas y respuestas sobre la Teoría de la Computación, sus subramas (autómatas, computabilidad y complejidad) y las nociones matemáticas básicas que la sustentan. Repasa conjuntos, relaciones, funciones, lenguajes, cadenas e inducción matemática. Es útil para revisar los fundamentos formales de la informática.

Puntos clave

  • La Teoría de la Computación estudia de forma formal los cómputos y sus límites.
  • Sus subramas principales son la teoría de autómatas, la computabilidad y la complejidad computacional.
  • La teoría de la computabilidad se pregunta qué problemas puede resolver una máquina de Turing.
  • Un lenguaje es un subconjunto de un conjunto de cadenas; el lenguaje vacío y el total son casos extremos.
  • Las propiedades de las relaciones son la reflexiva, la simétrica y la transitiva.
  • La inducción matemática demuestra propiedades en tres pasos: caso base, hipótesis y paso inductivo.

Ponte a prueba

1.- ¿Qué es la Teoría de la Computación? R=Es una ciencia que centra sus intereses en el estudio y definición formal de los cómputos., 2.- ¿Que áreas carecen de la Teoría de la Computación? R=Arquitectura de Computadoras, Algoritmos y Estructuras, Teoría de Circuitos, Sistemas Operativos., 3.- ¿Cuáles materias constituyen hoy en día los fundamentos teóricos de la Informática bajo el nombre de Teoría de la Computación? R=Teoría de Autómatas, Teoría de los lenguajes Formales, Computabilidad y Complejidad Algorítmica., 4.- ¿Durante que siglos diversos corrientes filosóficos allanaron el camino de la Computación a partir de las definiciones de sistemas formales? R=En el siglo XIX y XX, 5.- ¿Mencione las Subramas de la Teoría de la Computación? R=La teoría de los lenguajes y gramáticas funcionales.La Complejidad o el estudio de la cantidad de tiempo.Teoría de la Computabilidad., 6.- ¿Que son los autómatas? R=Son mecanismos formales que ``realizan'' derivaciones en gramáticas formales. La manera en que las realizan es mediante la noción de reconocimiento, 7.- ¿Que estudia la teoría de los autómatas? R=Estudia matemáticamente máquinas abstractas y problemas que éstas son capaces de resolver, 8.- ¿Que es computabilidad? R=Acción de ser computable, esto es, dado un determinado problema, existe un algoritmo representable en una computadora que puede hallar su solución, 9.- ¿En que preguntas se interesa la teoría de la computabilidad? R=Se interesa a cuatro preguntas:¿Qué problemas puede resolver una máquina de Turing?,¿Qué otros formalismos equivalen a las máquinas de Turing?,¿Qué problemas requieren máquinas más poderosas?,¿Qué problemas requieren máquinas menos poderosas?, 10.- ¿Que es La teoría de la complejidad computacional? R=Es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema., 11.- ¿Qué es una noción matemática en teoría de la computación? R=Son las relaciones, conjuntos, funciones y tablas de verdad que matemáticamente puede realizar la computadora., 12.- ¿Cuál es la aplicación autónoma en computación? R=Diseño de circuitos digitales.Analizadores léxicos para compiladores.Búsqueda de palabras clave en Internet.Verificación de sistemas de estados finitos (por ejemplo protocolos de comunicación).Modelado de sistemas discretos en general., 13.- ¿De un ejemplo de una relación? R=Sean A y B dos conjuntos. El producto cartesiano de A y B, denotado por AxB, es el conjunto de los pares ordenados (a, b) donde a A y b B:AxB={(a,b): a A y b B}, 14.- ¿Cuáles son las tablas de verdad? R=La disyunción de dos proposiciones p, q es la operación binaria que da por resultado p ó q, notación p v q, y tiene la siguiente tabla:



15.-Define que es un conjunto: R=Puede ser definido como una colección de objetos, 16.- ¿Cómo se llama el objeto perteneciente a un conjunto? R=Elemento o miembro,17.- ¿Que se representa por {}? R=A un conjunto que no tienen ningún elemento, llamado conjunto vacío, 18.-Menciona las operaciones sobre conjuntos: R=Unión, intersección, diferencia y producto., 19.-¿Qué es una relación? R=Podemos definir una relación como un conjunto de elementos, que son en esencia combinaciones de objetos de un determinado tipo que están relacionados de alguna forma., 20.- ¿Cómo podemos definir a una función? R=Se llama función a una relación en la cual a cada elemento del conjunto de partida le corresponde sólo un elemento del conjunto de llegada., 21.- ¿Qué dice la propiedad simétrica de una relación? R=La propiedad simétrica dice que si un elemento está relacionado con otro, este segundo también está relacionado con el primero, 22.- ¿Qué indica la propiedad reflexiva de una relación? R=La propiedad reflexiva dice que todos los elementos de un conjunto están relacionados con sí mismos, 23.- ¿Qué cita la propiedad transitiva de una relación? R=La propiedad transitiva dice que si un elemento está relacionado con otro, y este a su vez relacionado con un tercero, el primer elemento está relacionado con tercero, 24.- ¿Qué es un lenguaje? R=Un lenguaje es un subconjunto de cualquier diccionario. Ô Y ? son los lenguajes vacío y total, respectivamente., 25.- ¿Qué es una cadena? R=Una cadena de caracteres, palabra o frase es una secuencia ordenada de longitud arbitraria (aunque finita) de elementos que pertenecen a un cierto alfabeto., 26.-Menciona algunas operaciones de cadena: R=Concatenación: unir dos cadenas de caracteres. Multiplicar una cadena: repetir una cadena un número de veces, 27.- ¿Qué es inducción? R=La inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro n que toma una infinidad de valores, usualmente en el conjunto de los enteros naturales, 28.- ¿Para qué sirve la Inducción Matemática? R=Es un método que se utiliza para demostrar propiedades, formulas, validarlas y probar que son verdaderas. Es un método simple que consta de tres pasos fundamentales en los cuales se debe demostrar la propiedad reemplazando su incógnita por 1, luego por k y finalmente por k+1. 29.- ¿Quién propuso las propiedades fundamentales y cuantas propiedades son? R=G. Peano (1858-1932) propuso cinco propiedades fundamentales que caracterizan a los números naturales, Axiomas de Peano.

Descargar

PDF Word HTML

Preguntas frecuentes

¿Qué es la Teoría de la Computación?

Es una ciencia que se ocupa del estudio y la definición formal de los cómputos. Sus fundamentos incluyen la teoría de autómatas, de lenguajes formales, la computabilidad y la complejidad algorítmica.

¿Qué estudia la teoría de la complejidad computacional?

Estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema.

¿Para qué sirve la inducción matemática?

Sirve para demostrar propiedades y fórmulas que dependen de un parámetro n con infinitos valores. Consta de tres pasos: comprobar el caso 1, suponer cierto el caso k y demostrar el caso k+1.

Ponte a prueba

Tarjetas de repaso

Pulsa una tarjeta para ver la respuesta.

Test

1. ¿Qué es la Teoría de la Computación según el documento?
2. ¿Cuál de estas es una subrama de la Teoría de la Computación?
3. ¿Qué estudia la teoría de los autómatas?
4. ¿Cuántas propiedades fundamentales de los números naturales propuso G. Peano?
5. ¿Qué dice la propiedad transitiva de una relación?
6. ¿Qué es un conjunto vacío?
7. ¿Cómo se define una función según el texto?

Preguntas generadas con IA a partir del documento: comprueba las respuestas con el texto.