Teoría de la Computación: autómatas, computabilidad, conjuntos y relaciones
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.
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 HTMLPreguntas 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
Preguntas generadas con IA a partir del documento: comprueba las respuestas con el texto.