lunes, 01 de mayo de 2006
$>ALGORITMO
Un algoritmo es un conjunto finito de instrucciones o pasos que sirven para ejecutar una tarea o resolver un problema. De un modo más formal, un algoritmo es una secuencia finita de operaciones realizables, no ambiguas, cuya ejecución da una solución de un problema en un tiempo finito.
los Diagrama de flujo se usan habitualmente para representar algoritmos.El término algoritmo no está exclusivamente relacionado con las matemáticas, ciencias de la computación o informática. 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), o la preparación de una comida (siguiendo los pasos de una receta). 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, o incluso el método de Gauss para resolver sistemas de ecuaciones.
Tabla de contenidos [ocultar]
1 Concepto
2 Implementación
3 Ejemplo
4 Historia
5 Técnicas de diseño de algoritmos
6 Temas relacionados
7 Disciplinas relacionadas
8 Libros sobre Algoritmia
9 Enlaces externos
Concepto
La definición de algoritmo aún no cuenta con la formalidad científica que podría ser ideal para ciencias como las matemáticas y las ciencias de la computación (donde los algoritmos son esenciales pero a falta de formalidad no pueden incluirse fácilmente en las demostraciones formales de estas ciencias). Sin embargo, si existe un concepto intuitivo de algoritmo.
Un algoritmo es un sistema por el cual se llega a una solución, teniendo en cuenta que debe de ser definido, finito y preciso. Por preciso entendemos que cada paso a seguir tiene 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 un vez llegaremos al mismo resultado.
Estructura Básica:
inicio
datos de entrada (operaciones básicas)
procesamiento de los datos
datos de salida
fin
Implementación
Algunas veces, en una red neuronal biológica (por ejemplo, el cerebro humano implementa la aritmética básica o, incluso, una rata sigue un algoritmo para conseguir comida), también en circuitos eléctricos, en instalaciones industriales o maquinaria pesada.
El análisis y estudio de los algoritmos es una disciplina de las ciencias de la computación, y en la mayoría de los casos, su estudio es completamente abstracto sin usar ningún tipo de lenguaje de programación ni cualquier otra implementación; por eso, en ese sentido, comparte las características de las disciplinas matemáticas. Así, el análisis de los algoritmos se centra en los principios básicos del algoritmo, no en los de la implementación particular. Una forma de plasmar (o algunas veces codificar) un algoritmo es escribirlo en pseudocódigo o utilizar un lenguaje muy simple tal como Lexico cuyos códigos pueden estar en el idioma del programador.
Algunos escritores restringen la definición de algoritmo a procedimientos que deben acabar en algún momento, mientras que otros consideran procedimientos que podrían ejecutarse eternamente sin pararse, suponiendo el caso en el que existiera algún dispositivo físico que fuera capaz de funcionar eternamente. En este último caso, la finalización con éxito del algoritmo no se podría definir como la terminación de éste con una salida satisfactoria, sino que el éxito estaría definido en función de las secuencias de salidas dadas durante un periodo de vida de la ejecución del algoritmo. Por ejemplo, un algoritmo que verifica que hay más ceros que unos en una secuencia binaria infinita debe ejecutarse siempre para que pueda devolver un valor útil. Si se implementa correctamente, el valor devuelto por el algoritmo será válido, hasta que evalúe el siguiente dígito binario. De esta forma, mientras evalúa la siguiente secuencia podrán leerse dos tipos de señales: una señal positiva (en el caso de que el número de ceros es mayor que el de unos) y una negativa en caso contrario. Finalmente, la salida de este algoritmo se define como la devolución de valores exclusivamente positivos si hay más ceros que unos en la secuencia, y en cualquier otro caso, devolverá una mezcla de señales positivas y negativas..
Ejemplo
Se presenta el algoritmo para encontrar el máximo de un conjunto de enteros positivos. Se basa en recorrer una vez cada uno de los elementos, comparándolo con un valor concreto (el máximo entero encontrado hasta ahora). En el caso de que el elemento actual sea mayor que el máximo, se le asigna su valor al máximo.
El algoritmo escrito de una manera más formal, esto es, en pseudocódigo tendría el siguiente aspecto:
ALGORITMO Maximo
ENTRADAS: Un conjunto no vacío de enteros C.
SALIDAS: El mayor número en el conjunto C.
maximo ← -∞
PARA CADA elemento EN el conjunto C, HACER
SI valor_del_elemento > maximo, HACER
maximo ← valor_del_elemento
DEVUELVE maximo
Sobre la notación:
"←" representa la asignación entre dos objetos. Por ejemplo, maximo ← valor_del_elemento significa que el objeto maximo cambia su valor por el de valor_del_elemento.
"DEVUELVE" termina el algoritmo y devuelve el valor a su derecha (en este caso maximo).
Como medida de la bondad de un algoritmo, se suelen estudiar los recursos (memoria y tiempo) que consume el algoritmo. Por eso, se ha desarrollado el análisis de algoritmos para obtener valores que de alguna forma indiquen (o especifiquen) la evolución del gasto de tiempo y memoria en función del tamaño de los valores de entrada. Por ejemplo, el algoritmo anterior tiene un orden de eficiencia en tiempo de O(n), en la notación O mayúscula, siendo n el tamaño de la entrada, más concretamente, en este caso, el número de elementos de C. Además, como el algoritmo necesita recordar un único valor (el máximo) requiere un espacio de O(1) (hay que tener en cuenta que el tamaño de las entradas no se considera como memoria usada por el algoritmo).
Historia
La palabra algoritmo proviene del nombre del matemático llamado Abu Abdullah Muhammad bin Musa al-Khwarizmi que vivió entre los siglos VIII y IX. Su trabajo consistió en preservar y difundir el conocimiento de la antigua Grecia y de la India. Sus libros eran de fácil comprensión, de ahí que su principal valor no fuera el de crear nuevos teoremas o nuevas corrientes de pensamiento, sino el de simplificar las matemáticas a un nivel lo suficientemente bajo para que pudiera ser comprendido por un amplio público. Cabe destacar cómo señaló las virtudes del sistema decimal indio (en contra de los sistemas tradicionales árabes) y cómo explicó que, mediante una especificación clara y concisa de cómo calcular sistemáticamente, se podrían definir algoritmos que fueran usados en dispositivos mecánicos en vez de las manos (por ejemplo, ábacos). También estudió la manera de reducir las operaciones que formaban el cálculo. Es por esto que aun no siendo el creador del primer algoritmo, el concepto lleva aunque no su nombre, sí su pseudónimo.
Así, de la palabra algorismo, que originalmente hacía referencia a las reglas de uso de la aritmética utilizando dígitos árabes, se evolucionó a la palabra latina, derivación de al-Khwarizmi, algobarismus, que más tarde mutaría a algoritmo en el siglo XVIII. La palabra ha cambiado de forma que en su definición se incluye a todos los procedimientos finitos para resolver problemas.
Ya en el siglo XIX, se produjo el primer algoritmo escrito para un computador. La autora fue Ada Byron, en cuyos escritos se detallaban la máquina analítica en 1842. Por ello que es considerada por muchos como la primera programadora aunque, desde Charles Babbage, nadie completó su máquina, por lo que el algoritmo nunca se implementó.
Técnicas de diseño de algoritmos
Algoritmos voraces: seleccionan los elementos más prometedores del conjunto de candidatos hasta encontrar una solución. En la mayoría de los casos la solución no es óptima.
Algoritmos paralelos
Algoritmos probabilísticos
Algoritmos determinísticos
Algoritmos no determinísticos
Divide y vencerás: dividen el problema en subconjuntos disjuntos obteniendo una solución de cada uno de ellos para después unirlas, logrando así la solución al problema completo.
Heurísticas: encuentran soluciones a problemas basándose en un conocimiento anterior (a veces llamado experiencia) de los mismos.
Programación dinámica: intenta resolver problemas disminuyendo su coste computacional aumentando el coste espacial.
Ramificación y acotación: se basa en la construcción de las soluciones al problema mediante un árbol implícito que se recorre de forma controlada encontrando las mejores soluciones.
Vuelta Atrás: se construye el espacio de soluciones del problema en un árbol que se examina completamente, almacenando las soluciones menos costosas
los Diagrama de flujo se usan habitualmente para representar algoritmos.El término algoritmo no está exclusivamente relacionado con las matemáticas, ciencias de la computación o informática. 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), o la preparación de una comida (siguiendo los pasos de una receta). 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, o incluso el método de Gauss para resolver sistemas de ecuaciones.
Tabla de contenidos [ocultar]
1 Concepto
2 Implementación
3 Ejemplo
4 Historia
5 Técnicas de diseño de algoritmos
6 Temas relacionados
7 Disciplinas relacionadas
8 Libros sobre Algoritmia
9 Enlaces externos
Concepto
La definición de algoritmo aún no cuenta con la formalidad científica que podría ser ideal para ciencias como las matemáticas y las ciencias de la computación (donde los algoritmos son esenciales pero a falta de formalidad no pueden incluirse fácilmente en las demostraciones formales de estas ciencias). Sin embargo, si existe un concepto intuitivo de algoritmo.
Un algoritmo es un sistema por el cual se llega a una solución, teniendo en cuenta que debe de ser definido, finito y preciso. Por preciso entendemos que cada paso a seguir tiene 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 un vez llegaremos al mismo resultado.
Estructura Básica:
inicio
datos de entrada (operaciones básicas)
procesamiento de los datos
datos de salida
fin
Implementación
Algunas veces, en una red neuronal biológica (por ejemplo, el cerebro humano implementa la aritmética básica o, incluso, una rata sigue un algoritmo para conseguir comida), también en circuitos eléctricos, en instalaciones industriales o maquinaria pesada.
El análisis y estudio de los algoritmos es una disciplina de las ciencias de la computación, y en la mayoría de los casos, su estudio es completamente abstracto sin usar ningún tipo de lenguaje de programación ni cualquier otra implementación; por eso, en ese sentido, comparte las características de las disciplinas matemáticas. Así, el análisis de los algoritmos se centra en los principios básicos del algoritmo, no en los de la implementación particular. Una forma de plasmar (o algunas veces codificar) un algoritmo es escribirlo en pseudocódigo o utilizar un lenguaje muy simple tal como Lexico cuyos códigos pueden estar en el idioma del programador.
Algunos escritores restringen la definición de algoritmo a procedimientos que deben acabar en algún momento, mientras que otros consideran procedimientos que podrían ejecutarse eternamente sin pararse, suponiendo el caso en el que existiera algún dispositivo físico que fuera capaz de funcionar eternamente. En este último caso, la finalización con éxito del algoritmo no se podría definir como la terminación de éste con una salida satisfactoria, sino que el éxito estaría definido en función de las secuencias de salidas dadas durante un periodo de vida de la ejecución del algoritmo. Por ejemplo, un algoritmo que verifica que hay más ceros que unos en una secuencia binaria infinita debe ejecutarse siempre para que pueda devolver un valor útil. Si se implementa correctamente, el valor devuelto por el algoritmo será válido, hasta que evalúe el siguiente dígito binario. De esta forma, mientras evalúa la siguiente secuencia podrán leerse dos tipos de señales: una señal positiva (en el caso de que el número de ceros es mayor que el de unos) y una negativa en caso contrario. Finalmente, la salida de este algoritmo se define como la devolución de valores exclusivamente positivos si hay más ceros que unos en la secuencia, y en cualquier otro caso, devolverá una mezcla de señales positivas y negativas..
Ejemplo
Se presenta el algoritmo para encontrar el máximo de un conjunto de enteros positivos. Se basa en recorrer una vez cada uno de los elementos, comparándolo con un valor concreto (el máximo entero encontrado hasta ahora). En el caso de que el elemento actual sea mayor que el máximo, se le asigna su valor al máximo.
El algoritmo escrito de una manera más formal, esto es, en pseudocódigo tendría el siguiente aspecto:
ALGORITMO Maximo
ENTRADAS: Un conjunto no vacío de enteros C.
SALIDAS: El mayor número en el conjunto C.
maximo ← -∞
PARA CADA elemento EN el conjunto C, HACER
SI valor_del_elemento > maximo, HACER
maximo ← valor_del_elemento
DEVUELVE maximo
Sobre la notación:
"←" representa la asignación entre dos objetos. Por ejemplo, maximo ← valor_del_elemento significa que el objeto maximo cambia su valor por el de valor_del_elemento.
"DEVUELVE" termina el algoritmo y devuelve el valor a su derecha (en este caso maximo).
Como medida de la bondad de un algoritmo, se suelen estudiar los recursos (memoria y tiempo) que consume el algoritmo. Por eso, se ha desarrollado el análisis de algoritmos para obtener valores que de alguna forma indiquen (o especifiquen) la evolución del gasto de tiempo y memoria en función del tamaño de los valores de entrada. Por ejemplo, el algoritmo anterior tiene un orden de eficiencia en tiempo de O(n), en la notación O mayúscula, siendo n el tamaño de la entrada, más concretamente, en este caso, el número de elementos de C. Además, como el algoritmo necesita recordar un único valor (el máximo) requiere un espacio de O(1) (hay que tener en cuenta que el tamaño de las entradas no se considera como memoria usada por el algoritmo).
Historia
La palabra algoritmo proviene del nombre del matemático llamado Abu Abdullah Muhammad bin Musa al-Khwarizmi que vivió entre los siglos VIII y IX. Su trabajo consistió en preservar y difundir el conocimiento de la antigua Grecia y de la India. Sus libros eran de fácil comprensión, de ahí que su principal valor no fuera el de crear nuevos teoremas o nuevas corrientes de pensamiento, sino el de simplificar las matemáticas a un nivel lo suficientemente bajo para que pudiera ser comprendido por un amplio público. Cabe destacar cómo señaló las virtudes del sistema decimal indio (en contra de los sistemas tradicionales árabes) y cómo explicó que, mediante una especificación clara y concisa de cómo calcular sistemáticamente, se podrían definir algoritmos que fueran usados en dispositivos mecánicos en vez de las manos (por ejemplo, ábacos). También estudió la manera de reducir las operaciones que formaban el cálculo. Es por esto que aun no siendo el creador del primer algoritmo, el concepto lleva aunque no su nombre, sí su pseudónimo.
Así, de la palabra algorismo, que originalmente hacía referencia a las reglas de uso de la aritmética utilizando dígitos árabes, se evolucionó a la palabra latina, derivación de al-Khwarizmi, algobarismus, que más tarde mutaría a algoritmo en el siglo XVIII. La palabra ha cambiado de forma que en su definición se incluye a todos los procedimientos finitos para resolver problemas.
Ya en el siglo XIX, se produjo el primer algoritmo escrito para un computador. La autora fue Ada Byron, en cuyos escritos se detallaban la máquina analítica en 1842. Por ello que es considerada por muchos como la primera programadora aunque, desde Charles Babbage, nadie completó su máquina, por lo que el algoritmo nunca se implementó.
Técnicas de diseño de algoritmos
Algoritmos voraces: seleccionan los elementos más prometedores del conjunto de candidatos hasta encontrar una solución. En la mayoría de los casos la solución no es óptima.
Algoritmos paralelos
Algoritmos probabilísticos
Algoritmos determinísticos
Algoritmos no determinísticos
Divide y vencerás: dividen el problema en subconjuntos disjuntos obteniendo una solución de cada uno de ellos para después unirlas, logrando así la solución al problema completo.
Heurísticas: encuentran soluciones a problemas basándose en un conocimiento anterior (a veces llamado experiencia) de los mismos.
Programación dinámica: intenta resolver problemas disminuyendo su coste computacional aumentando el coste espacial.
Ramificación y acotación: se basa en la construcción de las soluciones al problema mediante un árbol implícito que se recorre de forma controlada encontrando las mejores soluciones.
Vuelta Atrás: se construye el espacio de soluciones del problema en un árbol que se examina completamente, almacenando las soluciones menos costosas
AQUI ENCONTRARAS MUCHA INFORMACION SOBRE LA COMPUTACION, MANUALES, HISTORIA DE LA COMPUTACION Y MUCHAS COSAS MAS QUE SERAN DE MUCHA AYUDA PARA AQUELLOS QUE DISFRUTAN DE ESTE MUNDO DE LA COMPUTACION
