# Complejidad Algoritmica **¿Para qué utilizamos algoritmos?** * En ciencias de la computación utilizamos algoritmos para resolver problemas. * Siempre estamos en la búsqueda de los algoritmos más eficientes que resuelvan cierta clase de problemas. **¿Cómo son estos problemas a los que nos enfrentamos?** * Problemas con diversos niveles de dificultad. **¿Cómo podemos distinguirlos?** * Estableciendo un criterio objetivo que permita diferenciar y categorizar cualquier problema de acuerdo con su nivel de dificultad. **¿Cómo se establece ese criterio?** * Ese criterio de dificultad de cada problema se ha establecido como una relación directa con la complejidad temporal del algoritmo que lo resuelve. * Existen diversos algoritmos que resuelven un mismo problema, cada uno con una complejidad temporal diferente. **¿Cuáles son los tipos básicos de problemas?** * Se considera que el grado de dificultad para resolver un problema está dado por la complejidad del mejor de todos los algoritmos encontrados que lo resuelven. * Gran parte de los problemas que inicialmente se estudian en los cursos de algoritmos se pueden solucionar a través de algoritmos **eficientes**. A estos se les llama problemas tratables o fáciles. * Sin embargo, aquellos problemas cuyo mejor algoritmo para resolverlo es **ineficiente** se les llama problemas intratables o difíciles. **¿Qué es la teoría de la Complejidad Computacional?** * Es la rama de la teoría de la computación que se enfoca en la clasificación de problemas computacionales de acuerdo a su dificultad inherente y en la relación que existe entre dichas clases de complejidad. **¿Qué son las clases de complejidad?** * Son las categorías en las cuales se han clasificado los problemas de acuerdo con la complejidad de los algoritmos que los resuelven de forma más eficiente. * Existen diversas clases de complejidad, incluso hay una clase para los problemas para los que **NO** existe un algoritmo que entregue la solución. * A estos problemas se les llama **indecidibles o irresolubles**. **¿Qué es la clase de complejidad P?** * Pertenecen a esta clase todos los problemas que pueden ser resueltos por un algoritmo eficiente. * Formalmente, la clase **P** consiste de todos aquellos problemas de decisión que pueden ser resueltos en una máquina determinista secuencial en un período de tiempo polinómico en proporción a los datos de entrada. **¿Qué es la clase de complejidad NP?** * Esta compuesta por los problemas que son verificables de manera eficiente. Es decir, si se ofrece una alternativa de solución, ésta puede ser verificada (indicar si es correcta o no) de manera eficiente. * **NP** es el acrónimo en inglés de *nondeterministic polynomial time*, es decir, tiempo polinomial no determinista. * Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista. **¿Qué es la clase de complejidad NP-completo?** * Es el subconjunto de los problemas en **NP** tal que todo problema en **NP** se puede reducir en cada uno de los problemas de **NP-completo**. ![Complejidad](/3_Estructuras_NO_Recursivas/1_ComplejidadTemp/Images/complejidad.png) **¿Por qué resultan tan interesantes los problemas NP-completo?** * La razón es que de tenerse una solución polinómica para un problema **NP-completo**, todos los problemas de **NP** tendrían también una solución en tiempo polinómico. * Si se demostrase que un problema **NP-completo**, llamémoslo **A**, no se pudiese resolver en tiempo polinómico, el resto de los problemas **NP-completos** tampoco se podrían resolver en tiempo polinómico. * Esto se debe a que si uno de los problemas **NP-completos** distintos de **A**, digamos **X**, se pudiese resolver en tiempo polinómico, entonces **A** se podría resolver en tiempo polinómico, por definición de **NP-completo**. * Varios problemas **NP-completo** son similares a otros problemas a los que se les conocen algoritmos eficientes para solucionarlos. * Un pequeño cambio a la declaración del problema puede causar un gran cambio en lo que respecta a la eficiencia del mejor algoritmo para solucionar dicho problema. * Es importante conocer acerca de problemas **NP-completo** ya que, sorprendentemente, su aparición resulta frecuente en aplicaciones de la vida real. * Al poder reconocer un problema como **NP-completo** se puede evitar realizar un trabajo infructuoso tratando de conseguir la mejor solución. * Si se prueba que el problema encontrado es **NP-completo**, se puede dedicar el tiempo a encontrar un algoritmo que dé una solución correcta, aunque no sea la óptima. ## Modelos de Computación **¿Qué es un modelo de computación?** - Una definición formal y abstracta de un computador. - Un modelo abstracto que describe una forma de computar. - Es la definición de un conjunto de operaciones permitidas utilizadas en el cómputo y sus respectivos costos. - Al asumir un cierto modelo de computación es posible analizar los recursos de cómputo requeridos, como el tiempo de ejecución o el espacio de memoria, o discutir las limitaciones de algoritmos o computadores. **¿Qué aspectos se deben tener en cuenta al definir un modelo de computación?** - Representación de las entradas y salidas. - Operaciones elementales. - Combinación de las operaciones para el desarrollo del programa. **¿Qué modelos de computación existen?** - Existe una amplia variedad de modelos de computación que difieren en el conjunto de operaciones permitidas y su costo de computación. - Máquinas de acceso aleatorio (RAM). - Circuitos combinacionales. - Autómatas finitos. - Máquinas de Turing. - ... --- ## Modelo RAM ![Modelo RAM](/3_Estructuras_NO_Recursivas/1_ComplejidadTemp/Images/ram.jpg) - Es un modelo simple de cómo los computadores se desempeñan. - Bajo el modelo RAM se mide el tiempo de ejecución de un algoritmo al contar la cantidad de pasos que se toma para una instancia de problema dada. - Está formado por una cinta de entrada, una de salida, un conjunto de registros y un programa (secuencia de instrucciones). **¿Qué se debe tener en cuenta en el modelo RAM?** - Cada operación simple solo toma un paso. - Los ciclos y las subrutinas no se consideran operaciones simples. - Estas operaciones se consideran una composición de operaciones de un solo paso. - Cada acceso a memoria toma un solo paso. - El modelo RAM no tiene en cuenta si un elemento está en caché o en disco, lo cual simplifica el análisis. --- ## Circuitos Combinacionales ![Compuertas lógicas](/3_Estructuras_NO_Recursivas/1_ComplejidadTemp/Images/compuertas.png) - **Entradas:** codificación binaria. - **Salidas:** codificación binaria. - **Operaciones elementales:** compuertas lógicas. --- ## Autómatas Finitos ![Autómata](/3_Estructuras_NO_Recursivas/1_ComplejidadTemp/Images/automata.png) - Procesan cadenas de entrada, las cuales son aceptadas o rechazadas. - Leen símbolos escritos sobre una cinta semi infinita, dividida en celdas, sobre la cual se escribe una cadena de entrada. - Poseen una cabeza lectora que contiene configuraciones internas llamadas estados. --- ## Máquinas de Turing ![Máquina de Turing](/3_Estructuras_NO_Recursivas/1_ComplejidadTemp/Images/turing.png) - Es el modelo de autómata con máxima capacidad computacional. - **Entradas:** cinta sin fin formada por celdas que almacenan símbolos. - **Salidas:** contenido final de la cinta. - **Operaciones elementales:** - Transición de estado. - Lectura de un símbolo de la cinta. - Escritura de un símbolo en la cinta. - Movimiento sobre la cinta (izquierda o derecha).