Complejidad Algoritmica Matematica Discreta
Páginas: 3 (574 palabras)
Publicado: 9 de julio de 2011
COMPLEJIDAD DE ALGORITMOS
Un algoritmo es una secuencia finita y ordenada de instrucciones elementales que, dados los valores de entrada de un problema, en algún momento finaliza y devuelve lasolución.
La Teoría de Algoritmos es una ciencia que estudia cómo construir algoritmos para resolver diferentes problemas. La Teoría de Algoritmos también proporciona herramientas formales que nos van apermitir decidir qué algoritmo es mejor en cada caso.
Una característica importante deseable para un algoritmo es su transportabilidad,conse- cuencia de su generalidad, la cual debe permitir laadaptación del algoritmo para que pueda ser ejecutado por máquinas muy diferentes. Podemos ahora precisar un poco más el concepto de algoritmo: Además de estar cons- tituido por una secuencia deoperaciones que llevan a la resolución de un tipo concreto de problemas dentro de un modelo prefijado, en un algoritmo es preciso que se verifique:
1. Existencia de un conjunto de entradas. Debe existir unconjunto específico de objetos cada uno de los cuales son los datos iniciales de un caso particular del problema que resuelve el algoritmo. Este conjunto se llama conjunto de entradas del problema.2. Definibilidad. Cada paso debe ser definible de forma precisa y sin ninguna ambigüedad.
3. Efectividad. Todas las operaciones a realizar en el algoritmo han de ser suficientemente básicas para quese puedan hacer en un tiempo finito en el procesador que ejecuta el algoritmo.
4. Finitud. El algoritmo debe acabar en un número finito de pasos. Unmétodo de cálculo puede no tener estarestricción.
5. Corrección. El algoritmo debe ser capaz de encontrar la respuesta correcta al problema planteado.
6. Predecibilidad. Siempre consigue el mismo resultado para un mismo conjunto de entradas.7. Existencia de un conjunto de salidas. El resultado del algoritmo asociado al conjunto de entradas.
Existe un principio fundamental en Teoría de Algoritmos, llamado principio de invarianza,...
Un algoritmo es una secuencia finita y ordenada de instrucciones elementales que, dados los valores de entrada de un problema, en algún momento finaliza y devuelve lasolución.
La Teoría de Algoritmos es una ciencia que estudia cómo construir algoritmos para resolver diferentes problemas. La Teoría de Algoritmos también proporciona herramientas formales que nos van apermitir decidir qué algoritmo es mejor en cada caso.
Una característica importante deseable para un algoritmo es su transportabilidad,conse- cuencia de su generalidad, la cual debe permitir laadaptación del algoritmo para que pueda ser ejecutado por máquinas muy diferentes. Podemos ahora precisar un poco más el concepto de algoritmo: Además de estar cons- tituido por una secuencia deoperaciones que llevan a la resolución de un tipo concreto de problemas dentro de un modelo prefijado, en un algoritmo es preciso que se verifique:
1. Existencia de un conjunto de entradas. Debe existir unconjunto específico de objetos cada uno de los cuales son los datos iniciales de un caso particular del problema que resuelve el algoritmo. Este conjunto se llama conjunto de entradas del problema.2. Definibilidad. Cada paso debe ser definible de forma precisa y sin ninguna ambigüedad.
3. Efectividad. Todas las operaciones a realizar en el algoritmo han de ser suficientemente básicas para quese puedan hacer en un tiempo finito en el procesador que ejecuta el algoritmo.
4. Finitud. El algoritmo debe acabar en un número finito de pasos. Unmétodo de cálculo puede no tener estarestricción.
5. Corrección. El algoritmo debe ser capaz de encontrar la respuesta correcta al problema planteado.
6. Predecibilidad. Siempre consigue el mismo resultado para un mismo conjunto de entradas.7. Existencia de un conjunto de salidas. El resultado del algoritmo asociado al conjunto de entradas.
Existe un principio fundamental en Teoría de Algoritmos, llamado principio de invarianza,...
Leer documento completo
Regístrate para leer el documento completo.