Teoria de la computacion

INSTITUTO TECNOLOGICO SUPERIOR DE HUICHAPAN

17 de febrero de 2011

INGENIERIA EN SISTEMAS COMPUTACIONALES

TEORIA DE LA COMPUTACION

RESUMEN UNIDAD I

TEORÍA DE LA COMPUTACIÓN

Autómatas, Compatibilidad y Complejidad.
La teoría de la computación es una ciencia, en particular una rama de la matemática y de la computación que centra su interés en el estudio y definición formal delos cálculos (obtención de soluciones y resultados).
Un autómata es un sistema secuencial, que quiere decir que lleva una serie de pasos ordenada para llegar al fin o solución de un problema es diseñado para controlar, en tiempo real y en ambiente industrial, procesos secuenciales.
Los autómatas se refiere a las definiciones y propiedades de los modelos matemáticos de cálculo existen dos tiposde autómatas finitos e infinitos el finito se refiere a un modelo matemático que acepta cadenas de un lenguaje definido sobre un alfabeto que son estados y transiciones que dependen de los símbolos de la cadena de entrada.
La complejidad se refiere a la cantidad de tiempo y espacio en memoria que toma la ejecución de un cómputo dado.
La computabilidad se refiere a la determinación de laclase de problemas que pueden ser resueltos en la llamada máquina de Turing.

Nociones Matemáticas de Teoría de la Computación

Una proposición es una sentencia declarativa que puede ser verdadero o falso pero no ambas.
Las proposiciones serán expresadas como P, Q,.... y algunas veces son llamadas átomos o fórmulas atómicas. Una proposición compuesta se forma por una proposición modificada porla palabra no o por conectar sentencias con las palabras y, o, si... entonces, si y solo sí.
Los conectivos lógicos
Negación.
Conjunción.
Disyunción.
Implicación.
Equivalencia.

Si Juan es estudiante entonces no ha presentado su examen de titulación

A las proposiciones compuestas se les llama formulas bien formadas
La lógica es la disciplina que trata de los métodos del razonamiento.Es ampliamente utilizada en matemáticas para la demostración de teoremas, en computación para la verificación de programas y en la programación declarativa, en ciencias naturales y físicas para sacar conclusiones de experimentos, en ciencias sociales y en varias áreas más para la solución de una gran variedad de problemas.

La lógica permite estudiar los métodos para distinguir losrazonamientos correctos de los incorrectos.
Ejemplos

El ocho es un número par. (verdadero)
Cinco es menor que cuatro. (falso)
¿Cómo te llamas? No es una proposición, ya que no expresa ningún juicio del que se pueda decir si es verdadero o falso. En general, las frases interrogativas, admirativas e imperativas, no son proposiciones.
Son elementos que se usan para enlazar varias proposiciones o paramodificar el valor de verdad de una proposición (este último es el caso de la negación).

Los términos de enlace que se utilizan en las proposiciones son:

SÍMBOLO REPRESENTACIÓN SIGNIFICADO
* Negación No
* Conjunción Y
* Disyunción O
* Condicional Implica
* Bicondicional Si y sólo si

El valor de verdad de la proposición compuesta depende de los enunciados que se combinen y delos conectivos que se utilicen. Las tablas de verdad muestran los valores de verdad de los enunciados compuestos en términos de los valores de verdad de sus componentes.

Ejemplo:
v La luna es una estrella (Atómica)
v La luna no es una estrella (Molecular)
v Si estamos en diciembre entonces llegará pronto la navidad (molecular)
v Es grande o pequeño (molecular)

Conjuntos Tc.
Soncuatro los conceptos básicos de la Teoría de Conjuntos:

1. Conjunto: Colección de cualquier tipo de objetos considerada como un todo, una multiplicidad vista como unidad
2. Los objetos que forman al conjunto son nombrados: elementos del conjunto o miembros del conjunto entidad completa bien determinada.
3. Por colección entenderemos a una agrupación que está determinada por una propiedad...