Ciencia Cibernética: Teoria Complejidad Computacional, Carlos Andres Castañeda Osorio

Introduccion

La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que ésta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.

GLOSARIO DE TERMINOS:

Algoritmo: un algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persa Al Juarismi ¹ ) es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien deba realizar dicha actividad. Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia.

Ingeniería De Sistemas: Es un modo de enfoque interdisciplinario que permite estudiar y comprender la realidad, con el propósito de implementar u optimizar sistemas complejos. Puede verse como la aplicación tecnológica de la teoría de sistemas a los esfuerzos de la ingeniería, adoptando en todo este trabajo el paradigma sistémico. La ingeniería de sistemas integra otras disciplinas y grupos de especialidad en un esfuerzo de equipo, formando un proceso de desarrollo estructurado.

La teoría general de sistemas (TGS) o teoría de sistemas o enfoque sistémico: Es un esfuerzo de estudio interdisciplinario que trata de encontrar las propiedades comunes a entidades llamadas sistemas. Éstos se presentan en todos los niveles de la realidad, pero que tradicionalmente son objetivos de disciplinas académicas diferentes. Su puesta en marcha se atribuye al biólogo austriaco Ludwig von Bertalanffy, quien acuñó la denominación a mediados del siglo XX.

MARCO TEORICO:

Un problema dado puede verse como un conjunto de preguntas relacionadas, donde cada pregunta se representa por una cadena de caracteres de tamaño finito. Por ejemplo, el problema factorización entera se describe como: Dado un entero escrito en notación binaria, retornar todos los factores primos de ese número. Una pregunta sobre un entero específico se llama una instancia. por ejemplo, "Encontrar los factores primos del número 15" es una instancia del problema factorización entera.

La complejidad temporal de un problema es el número de pasos que toma resolver una instancia de un problema, a partir del tamaño de la entrada utilizando el algoritmo más eficiente a disposición. Intuitivamente, si se toma una instancia con entrada de longitud n que puede resolverse en n² pasos, se dice que ese problema tiene una complejidad en tiempo de n². Por supuesto, el número exacto de pasos depende de la máquina en la que se implementa, del lenguaje utilizado y de otros factores. Para no tener que hablar del costo exacto de un cálculo se utiliza la notación O. Cuando un problema tiene costo en tiempo O(n²) en una configuración de computador y lenguaje dado, este costo será el mismo en todos los computadores, de manera que esta notación generaliza la noción de coste independientemente del equipo utilizado.

ii.

1. Extraer cualquier elemento de un vector. La indexación en un vector o array lleva el mismo tiempo sea cual fuere el índice que se quiera buscar, por tanto es una operación de complejidad constante O(1).

2. El proceso más común para ordenar un conjunto de elementos tiene complejidad cuadrática. El procedimiento consiste en crear una colección vacía de elementos. A ella se añade, en orden, el menor elemento del conjunto original que aún no haya sido elegido, lo que implica hacer un recorrido completo del conjunto original (O(n), siendo n el número de elementos del conjunto). Este recorrido sobre el conjunto original se realiza hasta que todos sus elementos están en la secuencia de resultado. Se puede ver que hay que hacer n selecciones (se ordena todo el conjunto) cada una con un coste n de ejecución: el procedimiento es de orden cuadrático O(n²). Hay que aclarar que hay diversos algoritmos de ordenación con mejores resultados.

iii.

¿Cómo se relacionan la Ingeniería de Sistemas, la teoría de la complejidad computacional y la TGS?

R//= La principal relación entre estos tres temas es principalmente la resolución de problemas, en el caso de la ingeniería de sistemas, siempre busca una mejora en la realización de aparatos electrónicos, esto a través tanto del hardware como del software, a su vez la teoría de la complejidad ayuda a que las personas que se encuentran envueltas en el tema de ingeniería de sistemas, logren resolver los problemas que se le presenten a través de un algoritmo; y por último La Teoría General de sistemas es aquella que nos ayuda a ver todo a nuestro alrededor como un sistema, esto nos ayuda a ver las cosas de manera más sencilla y que puede estar a su vez ayudando a su mejoramiento o reparación; por esto, la relación principal que podemos encontrar entre estos tres temas es el mejoramiento y reparación de un problema ya sea computable o de la vida real, viéndolo como sistema, Ayudándonos con algoritmos y mejorándolo a través de las soluciones planteadas por la ingeniería de sistemas.

iv. Bibliografía

Teoría de la complejidad computacional y ejemplos:

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_complejidad_computacional

Algoritmo:

http://es.wikipedia.org/wiki/Algoritmo

Ingeniería de Sistemas:

http://es.wikipedia.org/wiki/Ingenier%C3%ADa_de_sistemas

Teoría General de Sistemas:

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_sistemas

Ver mas acerca de Complejidad Computacional:

· http://homepage.mac.com/eravila/complejidad.pdf

· http://www.slideshare.net/joemmanuel/complejidad-computacional