Definicion De Algoritmo

Definicion De Algoritmo

Algoritmo

De Wikipedia, la enciclopedia libre

En matemáticas, ciencias de la computación, y disciplinas relacionadas, un algoritmo (del latín, dixit algorithmus y éste a su vez del matemático persa al-Jwarizmi) es una lista bien definida, ordenada y finita de operaciones que permite hallar la solución a un problema. Dado un estado inicial y una entrada, a través de pasos sucesivos y bien definidos se llega a un estado final, obteniendo una solución. Los algoritmos son objeto de estudio de la algoritmia, y su definición queda formalizada por el modelo computacional de la Máquina de Turing.

Su importancia radica en mostrar la manera de llevar a cabo procesos y resolver mecánicamente problemas matemáticos o de otro tipo. Al igual que las funciones matemáticas, los algoritmos reciben una entrada y la transforman en una salida, comportándose como una caja negra. Sin embargo, para que un algoritmo pueda ser considerado como tal, debe ser determinista, tener un número finito de instrucciones y debe acabar. Por determinista se entiende que, si se sigue el mismo proceso más de una vez, se llega siempre al mismo resultado.

El concepto de algoritmo, aunque similar y obviamente relacionado, no debe confundirse con el concepto de programa. Mientras el primero es la especificación de un conjunto de pasos (operaciones, instrucciones, órdenes,…) orientados a la resolución de un problema, el segundo es ese conjunto de operaciones especificadas en un determinado lenguaje de programación y para un computador concreto, susceptible de ser ejecutado (o compilado o interpretado). Un algoritmo, estrictamente hablando, no puede ejecutarse hasta que se implementa, ya sea en un lenguaje de programación, en un circuito eléctrico, en un aparato mecánico, usando papel y lápiz, o en algún otro modelo de computación.

En la vida cotidiana se emplean algoritmos en multitud de ocasiones para resolver diversos problemas. Algunos ejemplos se encuentran en los instructivos (manuales de usuario), los cuales muestran algoritmos para usar el aparato en cuestión o inclusive en las instrucciones que recibe un trabajador por parte de su patrón. 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 el método de Gauss para resolver un Sistema lineal de ecuaciones. Tabla de contenidos [ocultar]

1 Características de los algoritmos

2 Medios de expresión de un algoritmo

2.1 Diagrama de flujo

2.2 Pseudocódigo

2.3 Máquina de Turing

2.4 Implementación

3 Análisis de algoritmos

4 Ejemplo de algoritmo

4.1 Descripción de alto nivel

4.2 Descripción formal

4.3 Implementación

4.4 Análisis

5 Historia

6 Tipos de algoritmos según su función

7 Técnicas de diseño de algoritmos

8 Temas relacionados

9 Disciplinas relacionadas

10 Libros sobre Algoritmia

11 Enlaces externos

Características de los algoritmos [editar]

El científico de computación Donald Knuth ofreció una lista de cinco propiedades, que son ampliamente aceptadas como requisitos para un algoritmo:

1. Carácter finito. “Un algoritmo siempre debe terminar después de un número finito de pasos”.

2. Precisión. “Cada paso de un algoritmo debe estar precisamente definido; las operaciones a llevar a cabo deben ser especificadas de manera rigurosa y no gua para cada caso”.

3. Entrada. “Un algoritmo tiene cero o más entradas: cantidades que le son dadas antes de que el algoritmo comience, o dinámicamente mientras el algoritmo corre. estas entradas son tomadas de conjuntos específicos de objetos”.

4. Salida. “Un algoritmo tiene una o más salidas: cantidades que tienen una relación específica con las entradas”.

5. Eficacia. “También se espera que un algoritmo sea eficaz, en el sentido de que todas las operaciones a realizar en un algoritmo deben ser suficientemente básicas como para que en principio puedan ser hechas de manera exacta y en un tiempo finito por un hombre usando lápiz y papel”.

Knuth admite que, aunque su descripción pueda ser intuitivamente clara, carece de rigor formal, puesto que no está exactamente claro qué significa “precisamente definido”, “de manera rigurosa y no ambigua”, o “suficientemente básicas”, y así sucesivamente.

A partir del caracter finito y de la salida se deduce que ante una misma situación inicial (o valores de entrada) un algoritmo debe proporcionar siempre el mismo resultado (o salida), con excepción de los algoritmos probabilistas.

Medios de expresión de un algoritmo [editar]

Los algoritmos pueden ser expresados de muchas maneras, incluyendo al lenguaje natural, pseudocódigo, diagramas de flujo y lenguajes de programación entre otros. Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El usar pseudocódigo y diagramas de flujo evita muchas ambigüedades del lenguaje natural. Dichas expresiones son formas más estructuradas para representar algoritmos; no obstante, se mantienen independientes de un lenguaje de programación específico.

La descripción de un algoritmo usualmente se hace en tres niveles:

1. Descripción de alto nivel. Se establece el problema, se selecciona un modelo matemático y se explica el algoritmo de manera verbal, posiblemente con ilustraciones y omitiendo detalles.

2. Descripción formal. Se usa pseudocódigo para describir la secuencia de pasos que encuentran la solución.

3. Implementación. Se muestra el algoritmo expresado en un lenguaje de programación específico o algún objeto capaz de llevar a cabo instrucciones.

También es posible incluir un teorema que demuestre que el algoritmo es correcto, un análisis de complejidad o ambos.

Diagrama de flujo [editar]

Diagrama de flujo que expresa un algoritmo para calcular la raíz cuadrada de un número x

Diagrama de flujo que expresa un algoritmo para calcular la raíz cuadrada de un número x

Artículo principal: Diagrama de flujo

Los diagramas de flujo son descripciones gráficas de algoritmos; usan símbolos conectados con flechas para indicar la secuencia de instrucciones y están regidos por ISO.

Los diagramas de flujo son usados para representar algoritmos pequeños, ya que abarcan mucho espacio y su construcción es laboriosa. Por su facilidad de lectura son usados como introducción a los algoritmos, descripción de un lenguaje y descripción de procesos a personas ajenas a la computación.

Pseudocódigo [editar]

Artículo principal: Pseudocódigo

Pseudocódigo es la descripción de un algoritmo que asemeja a un lenguaje de programación pero con algunas convenciones del lenguaje natural. Tiene varias ventajas con respecto a los diagramas de flujo, entre las que se destaca el poco espacio que se requiere para representar instrucciones complejas. El pseudocódigo no está regido por ningún estándar. pseudo viene de falso y por ende es un codigo al que aunque es entendible no se aplica al proceso que debe realizar la maquina.

Máquina de Turing [editar] Artículo principal: Máquina de Turing

La máquina de Turing es un modelo matemático, diseñado por Alan Turing, que formaliza el concepto de algoritmo. A este modelo se le refiere comúnmente como la “descripción de más bajo nivel” por el hecho de que no utiliza ninguna expresión coloquial.

Implementación [editar]

Muchos algoritmos son ideados para implementarse en un programa. Sin embargo, los algoritmos pueden ser implementados en otros medios, como una red neuronal, un circuito eléctrico o un aparato mecánico. Algunos algoritmos inclusive se diseñan especialmente para implementarse usando lápiz y papel. El algoritmo de multiplicación tradicional, el algoritmo de Euclides, la criba de Eratóstenes y muchas formas de resolver la raíz cuadrada son sólo algunos ejemplos.

Análisis de algoritmos [editar] Artículo principal: Análisis de algoritmos

Como medida de la eficiencia de un algoritmo, se suelen estudiar los recursos (memoria y tiempo) que consume el algoritmo. El análisis de algoritmos se ha desarrollado 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.

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 Léxico, 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 sea 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 de algoritmo [editar]

El problema consiste en encontrar el máximo de un conjunto de números. Para un ejemplo más complejo véase Algoritmo de Euclides.

Descripción de alto nivel [editar]

Dado un conjunto finito C de números, se tiene el problema de encontrar el número más grande. Sin pérdida de generalidad se puede asumir que dicho conjunto no es vacío y que sus elementos están numerados como c_0,c_1,\dots,c_n.

Es decir, dado un conjunto C=\{c_0,c_1,\dots,c_n\} se pide encontrar m tal que x\leq m para todo elemento x que pertenece al conjunto C.

Para encontrar el elemento máximo, se asume que el primer elemento (c0) es el máximo; luego, se recorre el conjunto y se compara cada valor con el valor del máximo número encontrado hasta ese momento. En el caso que un elemento sea mayor que el máximo, se asigna su valor al máximo. Cuando se termina de recorrer la lista, el máximo número que se ha encontrado es el máximo de todo el conjunto.

Descripción formal [editar]

El algoritmo escrito de una manera más formal, esto es, en pseudocódigo tendría el siguiente aspecto: Algoritmo Encontrar el máximo de un conjunto

función \max©\,

    //C es un conjunto no vacío de números//

    n\gets|C| // | C | es el número de elementos de C//

    m\gets c_0

   para i\gets 1 hasta n\, hacer

        si c_i > m\, entonces

            m\gets c_i

    devolver m\,

Sobre la notación:

gets” representa la asignación entre dos objetos. Por ejemplo, m\leftarrow x significa que el objeto m cambia su valor por el de x

devolver” termina el algoritmo y devuelve el valor a su derecha (en este caso, el máximo de C)

Implementación [editar]

En lenguaje Visual Basic 8 (2005):

Public Function max(C As Integer()) As Integer

Dim n As Integer = C.Get Length?(0)

Dim m As Integer = C(0)

For i As Integer = 1 To n

If C(i) > m Then

m = C(i)

End If

Next

Return m

End Function

En lenguaje Delphi:

function Max(const Lista Numeros?: array of Integer): Integer; var

vTemp, i: Integer;

egin

vTemp:= 0;

for i:= 1 to High(Lista Numeros) do

if Lista Numeros[i] > vTemp then

vTemp:= Lista Numeros[i];

Result:= vTemp; end;

Análisis [editar]

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 adicional 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 [editar]

La palabra algoritmo proviene del nombre del matemático llamado Muhammad ibn Musa al-Jwarizmi 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 logro no fuera el de crear nuevos teoremas o corrientes de pensamiento, sino el de simplificar la matemática a punto tal que pudieran ser comprendidas y aplicadas por un mayor número de personas. 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 aún 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ó.

La falta de rigor matemático en la definición de “procedimiento bien definido” para los algoritmos trajo algunas dificultades a los matemáticos y lógicos del siglo XIX y comienzos de XX. Este problema fue en gran parte resuelto con la descripción de la máquina de Turing, un modelo abstracto de computadora formulado por Alan Turing, y la demostración de que cualquier método anticipado por otros matemáticos que pueda encontrarse para describir “procedimientos bien definidos” puede ser emulado en una máquina de Turing (una afirmación conocida como “tesis de Church-Turing”).

En la actualidad, el criterio formal para definir un algoritmo es que se trata de un proceso que puede implementarse en una máquina de Turing completamente especificada, o en alguno de los formalismos equivalentes. El interés original de Turing era el problema de la detención: decidir cuándo un algoritmo describe un procedimiento de terminación. En términos prácticos importa más la teoría de la complejidad computacional, que incluye los problemas llamados NP-completos, es decir aquellos sobre los que generalmente se presume que requerirán tiempo más que polinómico para cualquier algoritmo (determinístico). NP denota la clase de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinística.

Tipos de algoritmos según su función [editar]

Algoritmo de ordenamiento

Algoritmo de búsqueda

Técnicas de diseño de algoritmos [editar]

Algoritmos voraces (greedy): 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: permiten la división de un problema en subproblemas de forma que se puedan ejecutar de forma simultánea en varios procesadores.

Algoritmos probabilísticos: algunos de los pasos de este tipo de algoritmos están en función de valores pseudoaleatorios.

Algoritmos determinísticos: sus pasos están perfectamente definidos y aportan una solución exacta.

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.

Metaheurísticas: encuentran soluciones aproximadas (no óptimas) 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 (Backtracking): se construye el espacio de soluciones del problema en un árbol que se examina completamente, almacenando las soluciones menos costosas.

Temas relacionados [editar]

Cota superior asintótica

Cota inferior asintótica

Cota ajustada asintótica

Complejidad computacional

Máquina de Turing

Disciplinas relacionadas [editar]

Ciencias de la Computación

Análisis de algoritmos

Complejidad computacional

Informática

Inteligencia artificial

Investigación operativa

Matemáticas

Programación

Libros sobre Algoritmia [editar]

Fundamentos de Algoritmia, G. Brassard y P. Bratley. (ISBN 848966000) The Art of Computer Programming, Knuth, D. E. [quien fue también, el creador del TeX] Introduction to Algorithms (2nd ed), Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. Introduction to Algorithms. A Creative Approach, Mamber, U. Algorithms in C (3r ed), Sedgewick, R. (también existen versiones en C++ y Java) The Design and Analysis of Computer Algorithms, Aho, A. www.rodrigoseenojayseva.com.ar Mario Diaz Mario? Diaz

Enlaces externos [editar]

Soluciones de Algoritmos Wikilibros

Colabora en Wikilibros Wikilibros alberga un libro o manual sobre Algoritmia.

Wikcionario

Colabora en Wikcionario Wikcionario tiene una entrada sobre algoritmo. Portal de algoritmia

Técnicas de Diseño de Algoritmos manual que explica y ejemplifica los distintos paradigmas de diseño de algoritmos. Rosa Guerequeta y Antonio Vallecillo (profesores de la Universidad de Málaga).

Transparencias de la asignatura “Esquemas Algorítmicos”, Campos, J.

Apuntes y problemas de Algorítmica por Domingo Giménez Cánovas

Curso de Diseño de Algoritmos de Carlos Pes

Algoritmo para calcular una Raíz Cuadrada con lápiz y papel

Obtenido de “http://es.wikipedia.org/wiki/Algoritmo

Categoría: Algoritmos

Categorías ocultas: Wikipedia:Artículos destacados en w:en | Wikipedia:Artículos destacados en w:sr | Wikipedia:Artículos buenos en w:en Vistas

Artículo

Editar

Historial

Herramientas personales

Registrarse/Entrar

Navegación

Portada

Portal de la comunidad

Actualidad

Cambios recientes

Página aleatoria

Ayuda

Donativos

Buscar

Herramientas

Lo que enlaza aquí

Cambios en enlazadas

Subir archivo

Páginas especiales

Versión para imprimir

Enlace permanente

Citar este artículo

otros proyectos

Wikilibros

Wikcionario

Otros idiomas

Afrikaans

Aragonés

العربية

Asturianu

Беларуская

Беларуская (тарашкевіца)

Български

বাংলা

Bosanski

Català

Česky

Dansk

Deutsch

Ελληνικά

English

Esperanto

Eesti

فارسی

Suomi

Français

Galego

עברית

हिन्दी

Hrvatski

Magyar

Interlingua

Bahasa Indonesia

Íslenska

Italiano

日本語

ქართული

한국어

Lëtzebuergesch

Lietuvių

Latviešu

Македонски

Bahasa Melayu

Nederlands

‪Norsk (nynorsk)‬

‪Norsk (bokmål)‬

Polski

Português

Română

Русский

سنڌي

Srpskohrvatski / Српскохрватски

Simple English

Slovenčina

Slovenščina

Shqip

Српски / Srpski

Basa Sunda

Svenska

Тоҷикӣ/tojikī

ไทย

Tagalog

Türkçe

Українська

Tiếng Việt

Walon

中文

Powered by Media Wiki? Wikimedia Foundation

Esta página fue modificada por última vez el 08:21, 14 abr 2008. Contenido disponible bajo los términos de la Licencia de documentación libre de GNU (véase Derechos de autor). Wikipedia® es una marca registrada de la organización sin ánimo de lucro Wikimedia Foundation, Inc. Política de privacidad Acerca de Wikipedia Limitación de responsabilidad

Algoritmo. (2008, 14) de abril. Wikipedia, La enciclopedia libre. Fecha de consulta: 16:20, abril 14, 2008 from http://es.wikipedia.org/w/index.php?title=Algoritmo&oldid=16601007.


Mis sitios nuevos:
Emprendedores
Politica de Privacidad