Sectorizacion

Páginas: 18 (4264 palabras) Publicado: 5 de febrero de 2011
Complejidad computacional
La Teoría de la Complejidad Computacional es la parte de la teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema. Un cálculo resulta complejo si es difícil de realizar. En este contexto podemos definir la complejidad de cálculo como la cantidad de recursos necesarios para efectuar un cálculo. Así, un cálculo difícilrequerirá más recursos que uno de menor dificultad. Los recursos comúnmente estudiados son el tiempo (número de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (cantidad de memoria utilizada para resolver un problema) [WEISS,+95]. Un algoritmo que resuelve un problema pero que tarda mucho en hacerlo, difícilmente será de utilidad. Igualmente un algoritmo que necesite ungigabyte de memoria no será probablemente utilizado. A estos recursos se les puede añadir otros, tales como el número de procesadores necesarios para resolver el problema en paralelo. Si un cálculo requiere más tiempo que otro decimos que es más complejo y lo llamamos complejidad temporal. Por otro lado, si un cálculo requiere más espacio de almacenamiento que otro decimos que es más complejo, eneste caso hablamos de una complejidad espacial. Es claro que el tiempo que se requiere para efectuar un cálculo en un computador moderno es menor que el requerido para hacer el mismo cálculo con las máquinas de las década pasadas, y seguramente que el tiempo en una máquina de la próxima generación será mucho menor [Bassiliades,+04].
El estudio de los procesos computacionales, conduce a unaclasificación de los problemas en dos grandes clases: los problemas con solución y los problemas sin solución. Los problema solucionables, requieren gran cantidad de recursos como tiempo y espacio de almacenamiento. El análisis requerido para estimar el uso de recursos de un algoritmo es una cuestión teórica, y por tanto necesita un marco normal[Chesnevar,+04]. El formalismo y abstracción constituyeun método necesario para la programación, considerada como disciplina científica en la que se prioriza la actividad de diseño y razonamiento, sobre la de depuración mediante prueba y error en un contexto artesanal.
Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se relaciona linealmente con su tamaño. Aunque actualmente lamayoría de los algoritmos resueltos por las máquinas tienen como máximo una complejidad o costo computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica.
Hasta el momento las computadoras resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre eltamaño de los datos de entrada y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en la clase P. Los problemas que no pueden ser resueltos por nuestras computadoras (las cuales son Máquinas Determinísticas), que en general poseen costes factorial o combinatorio pero que podrían ser procesados por una máquina No Determinista, están agrupados en la clase NP[Hopcroft,+93]. Estos problemas no tienen una solución práctica, es decir, una máquina determinística (como una computadora actual) no puede resolverlos en un tiempo razonable.
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.
Ejemplo, "Encontrar los factores primos del número 24" 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...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Sectorizacion
  • Sectorizacion mexicana
  • Sectorización de Parroquia
  • Sectorizacion
  • Sectorizacion
  • sectorizacion
  • Sectorizacion
  • Sectorizaciòn

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS