ACTIVIDAD DE COMPUTABILIDAD Y COMPLEJIDAD

ACTIVIDAD DE COMPUTABILIDAD Y COMPLEJIDAD

Autómata

Un autómata es un sistema secuencial, aunque en ocasiones la palabra es utilizada también para referirse a un robot y puede definirse como un equipo electrónico programable en lenguaje informático diseñado para controlar en tiempo real y en ambiente industrial procesos secuenciales. Sin embargo la rápida evolución de los autómatas hace que esta definición no esté cerrada.

Un autómata programable se puede considerar como un sistema basado en un micro procesador siendo sus partes fundamentales la Unidad Central de Procesos (CPU) la memoria y el sistema de entradas y salidas (E/S) por lo que realiza control interno y externo del autómata y la interpretación de las instrucciones del programa. Se describen tres tipos de autómatas que reconocen tipos diferentes de lenguajes los autómatas finitos, autómatas a pila y máquinas de Turing.

COMPUTABILIDAD

Es la parte de la computación que estudia los problemas decisión y pueden ser resueltos con un algoritmo o la misma máquina de Turing. Por lo que es llevar acabo registros que pueden ser realizados por humanos para ser automatizados y estar libres de errores.

¿Qué es computabilidad?

Consiste en ser capaz de encontrar la representación adecuada para la descripción de un problema o fenómeno se dice que un algoritmo es una manera formal y sistemática de representar la descripción de un proceso.

Computabilidad son cosas que pueden ser realizadas por un ser humano y que pudieran automatizar el trabajo tedioso y lleno de errores del ser humano.

v  Para tal representación es necesario:

v  Un conjunto finito de símbolos.

v  Hacer asociaciones entre conceptos y elementos del lenguaje (de símbolos)

v  Encontrar las combinaciones adecuadas de símbolos para evitar ambigüedad.

v  Definir una manera de confirmar tal descripción para que terceros puedan reproducirla y llegar a los mismos resultados.

Teoría de la computabilidad

La Teoría de la Computabilidad consiste en encontrar maneras de representar descripciones de procesos, de tal manera que se pueda asegurar si existe o no una representación.

Se dice que un algoritmo es una manera formal y sistemática de representar la descripción de un proceso

Los problemas se clasifican en esta teoría de acuerdo a su grado de imposibilidad:

·         Los computables son aquellos para los cuales sí existe un algoritmo que siempre los resuelve cuando hay una solución y además es capaz de distinguir los casos que no la tienen. También se les conoce como decidibles, resolubles o recursivos.

·         Los semicomputables son aquellos para los cuales hay un algoritmo que es capaz encontrar una solución si es que existe, pero ningún algoritmo que determine cuando la solución no existe (en cuyo caso el algoritmo para encontrar la solución entraría a un bucle infinito). El ejemplo clásico por excelencia es el problema de la parada. A estos problemas también se les conoce como listables, recursivamente enumerables o reconocibles, porque si se enlistan todos los casos posibles del problema, es posible reconocer a aquellos que sí tienen solución.

·         Los incomputables son aquellos para los cuales no hay ningún algoritmo que los pueda resolver, no importando que tengan o no solución. El ejemplo clásico por excelencia es el problema de la implicación lógica, que consiste en determinar cuándo una proposición lógica es un teorema; para este problema no hay ningún algoritmo que en todos los casos pueda distinguir si una proposición o su negación es un teorema.

Problemas computables y no computables

El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límites teóricos de los ordenadores. Además de las cuestiones sobre algoritmos, se han encontrado numerosos problemas menos "generales" que han resultado ser no computables. La mayoría de las demostraciones de no computabilidad se basan en el método de la diagonal. Como ejemplos de estos problemas podemos citar:

1.- El problema de la palabra para Grupos.- Dado un subconjunto S de elementos de un grupo G, se trata de decidir si una expresión compuesta por elementos de S y con las operaciones del grupo es igual al elemento neutro del grupo. Durante muchos años se buscaron ejemplos de grupos finitamente presentados para los que este problema fuese indecidible. La existencia de uno de estos grupos fue encontrada por Novikov en 1955 y por Boone en 1957. En el álgebra moderna hay abundantes ejemplos de interesantes problemas no computables; una gran cantidad de ellos sobre propiedades de palabras o generadores semejantes al problema de la palabra para grupos.

2.- Décimo problema de Hilbert. Una ecuación diofántica es la ecuación de los ceros enteros de un polinomio con coeficientes enteros. El décimo problema de Hilbert, propuesto en 1900, pregunta si hay un procedimiento efectivo que determine si una ecuación diofántica tiene o no solución. Y. Matiyasevich demostró en 1970 que este problema no tiene solución.

3.- Decibilidad de las teorías lógicas. El desarrollo de la teoría de la computabilidad ha ido íntimamente ligado al desarrollo de la lógica matemática. Esto ha sido así porque la decibilidad de los distintos sistemas lógicos es una cuestión fundamental. Es bastante fácil ver que el cálculo proposicional es decidible. Church y Turing demostraron en 1936 que el cálculo de predicados no era decidible. Por otro lado, para cada una de las distintas teorías se ha ido estudiando su posible decibilidad. Como ejemplo más ilustrativo, Tarski demostró que la teoría de los números reales era decidible.

Por otro lado, son muchos los problemas interesantes que se han demostrado computables. Todas las funciones construidas por recursividad primitiva o minimalización a partir de funciones calculables resultan ser calculables como consecuencia de los trabajos de Church y Turing. Pero además, otras funciones más complejamente definidas también son computables, siendo el resultado más significativo en relación con esta cuestión el dado por el siguiente teorema:

Primer teorema de Recursión. Todo operador entre funciones calculables que sea recursivo (esto es que se defina la imagen de f mediante una función calculable en términos de una parte finita de f), tiene una función parcial computable que es el menor punto fijo, es decir, esta función es un punto fijo y cualquier otro punto fijo del operador es una extensión de esa función.

Este teorema recibe su nombre porque podemos definir una función mediante una ecuación recursiva más general que la permitida por la recursividad primitiva, a saberdonde  es un operador recursivo. El primer teorema de recursión nos dice que esta definición es posible; hay una función recursiva que satisface esta ecuación. Como en matemáticas se requiere que la definición sea unívoca, se dice que dicha ecuación define el menor punto fijo del operador. Así, y de acuerdo al primer teorema de recursión, la clase de las funciones calculables es cerrada bajo una muy general forma de definición por recursión.

A menudo se utiliza la técnica de reducir un problema a otro para comprobar si tiene o no solución efectiva. La estrategia en el caso de la respuesta negativa es la siguiente, si se reduce de forma efectiva un problema sin solución efectiva a otro problema (mediante una función calculable), entonces este nuevo problema tampoco tendrá solución efectiva. La razón es muy simple, si tuviese solución efectiva, componiendo el algoritmo solución con el algoritmo de transformación obtendríamos una solución para el problema efectivamente irresoluble.

En sentido inverso, si se reduce un problema a otro para el que se conoce una solución efectiva, entonces componiendo se obtiene una solución para el primer problema. Esta técnica es muy útil y se utiliza a menudo. Por otro lado, esta misma técnica es muy empleada en el campo de la complejidad algorítmica. Para asegurarse de que un problema está en una clase de complejidad, basta reducir el problema a otro de dicha clase sin más que asegurarse que la reducción se realiza en la correspondiente clase de complejidad.

COMPLEJIDAD

Es la cualidad de lo que está compuesto diversos elementos la complejidad tiende a ser utilizada para caracterizar algo con muchas partes que forman un conjunto intrincado.

La palabra proviene del latín complectere que significa trenzar, enlazar  al agregado prefijo “com” añade el sentido de la dualidad de dos elementos opuestos que se enlazan íntimamente pero sin anular su dualidad y esta es una noción utilizada en filosofía y epistemología y varía según el área de conocimiento.

Es un estudio de la cantidad de tiempo (número de pasos de ejecución de un algoritmo para resolver un problema) y de espacio (cantidad de memoria utilizada para resolver un problema), que toma la ejecución de un cómputo dado.

La terminología utilizada para describir la complejidad de los algoritmos es:

Ejemplos:

1.- Encuentra el mayor de cien números de una lista de n € ( n ≥ 100 )

C1=Complejidad constante

2.- Búsqueda binaria

C2=Complejidad logarítmica

3.- Búsqueda lineal

C3=Complejidad lineal

CLASES DE COMPLEJIDAD

Existen problemas tratables, pues pueden resolverse utilizando un algoritmo de complejidad 5, con una entrada de datos razonable en un tiempo relativamente corto.

Los problemas intratables, son todos aquellos que no se pueden resolver con un algoritmo de complejidad polinomica en el peor de los casos.

Generalmente requieren un tiempo extremadamente largo aun con un valor de entrada pequeño, en la práctica se utilizan soluciones aproximadas que no difieren muchos con las exactas.

Para algunos problemas no existen algoritmos que puedan solucionarlos, por lo que estos se les denominaran no resolubles o irresolubles.