Estructura de datos en c#

Solo disponible en BuenasTareas
  • Páginas : 10 (2411 palabras )
  • Descarga(s) : 4
  • Publicado : 16 de marzo de 2010
Leer documento completo
Vista previa del texto
Estructura de datos C#
1 Análisis de algoritmos.
Introduccion Primero que nada debemos saber que el término algoritmo no está exclusivamente relacionado con la matemática, ciencias de la computación o informática. Un algoritmo es un sistema por el cual se llega a una o varias soluciones, teniendo en cuenta que debe ser definido, finito y preciso. Por preciso entendemos que cada paso a seguirtiene un orden; finito implica que tiene un determinado número de pasos, o sea, que tiene un fin; y definido, que si se sigue el mismo proceso más de una vez llegaremos al mismo resultado. En realidad, en la vida cotidiana empleamos algoritmos en multitud de ocasiones para resolver diversos problemas. Algunos ejemplos son el uso de una lavadora (se siguen las instrucciones), pero no la preparaciónde una comida (porque no están perfectamente definidos los pasos) o el mismo lenguaje humano que “transforma” nuestros pensamientos en sonidos y hace que otro humano nos pueda entender. También existen ejemplos de índole matemática, como el algoritmo de la división para calcular el cociente de dos números, el algoritmo de Euclides para calcular el máximo común divisor de dos enteros positivos, oincluso el método de Gauss para resolver Sistema lineal de ecuaciones. La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real. Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota. Aefectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parametros, los más usuales son el tiempo de ejecución y la cantidad de memoria (espacio). Ocurre con frecuencia que ambos parametros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamano del mayor problema que puedo resolveren T segundos y/o con Mb bytes de memoria? Complejidad de algoritmos Es la parte de la teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema los cuales se dividen en: el tiempo y el espacio. Los problemas de decisión se clasifican en conjuntos de complejidad llamadas clases de complejidad: - Clase de complejidad P: Es el conjunto de losproblemas de decisión que puedan ser resueltos en tiempo polinómico calculado a partir de la entrada por una maquina de turins determinista y que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos. Ejemplo: 1. Saber si un número entero es primo. 2. Saber si una frase pertenece a un conjunto de frases.
1

- Clase de complejidad NP: Es el conjunto de los problemas de decisiónque pueden ser resueltos por una maquina de turins no determinista en tiempo polinómico las cuales tienen la propiedad de que su solución puede ser verificada. - Clase de complejidad NP-Completo: Es el subconjunto de los problemas de decisión en NP que destacan por su extrema complejidad y que decimos se hayan en la frontera externa de la clase NP. Notación aritmética Notación asintótica “O” grandese utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función, es decir, su utilidad radica en encontrar un limite superior del tiempo de ejecución de un algoritmo es decir el peor caso. La definición de esta notación es la siguiente: Una función g(n) pertenece a O(f(n)) si y solo si existen las constantes c y n. tales que: g(n) < = c · f(n) Para todo n > = n. y setiene que T(n) < = cn. Nota: el orden de magnitud de una función es el orden del término de la función más grande respecto de n. Notación asintótica “Omega” grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de T(n), y significa que existe una constante c tal que T(n) es mayor o igual a c(g(n)) para un número infinito de valores n. Tiempo de ejecución de un...
tracking img