República Bolivariana de Venezuela.
Ministerio del Poder Popular para la Defensa.
Universidad Nacional Experimental Politécnica de la Fuerza Armada Nacional.
UNEFA – Ampliación Santa Elena de Uairén.
ALGORITMO
INSTRUCTORA: INTEGRANTE:
Ing. Yaselin Senteno. Franklin Rojas.
CI: 27.490.268
Carrera: ADS_U.
Santa Elena de Uairén, Enero de 2.021.
Algoritmo
En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas,
un algoritmo (del latín, dixit algorithmus y este del griego arithmos, que significa
«número», quizá también con influencia del nombre del matemático persa Al-Juarismi) es
un conjunto de instrucciones o reglas definidas y no-ambiguas, ordenadas y finitas que
permite, típicamente, solucionar un problema, realizar un cómputo, procesar datos y llevar
a cabo otras tareas o actividades. Dados un estado inicial y una entrada, siguiendo los pasos
sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto
de estudio de la algoritmia.
En la vida cotidiana, se emplean algoritmos frecuentemente para resolver problemas
determinados. Algunos ejemplos son los manuales de usuario, que muestran algoritmos
para usar un aparato, o las instrucciones que recibe un trabajador de su patrón. Algunos
ejemplos en matemática son el algoritmo de multiplicación, para calcular el producto, el
algoritmo de la división para calcular el cociente de dos números, el algoritmo de
Euclides para obtener el máximo común divisor de dos enteros positivos, o el método de
Gauss para resolver un sistema de ecuaciones lineales.
En términos de programación, un algoritmo es una secuencia de pasos lógicos que permiten
solucionar un problema.
Definición
En general, no existe ningún consenso definitivo en cuanto a la definición formal de
algoritmo. Muchos autores los señalan como listas de instrucciones para resolver
un cálculo o un problema abstracto, es decir, que un número finito de pasos convierten los
datos de un problema (entrada) en una solución (salida). Sin embargo cabe notar que
algunos algoritmos no necesariamente tienen que terminar o resolver un problema en
particular. Por ejemplo, una versión modificada de la criba de Eratóstenes que nunca
termine de calcular números primos no deja de ser un algoritmo.
A lo largo de la historia varios autores han tratado de definir formalmente a los algoritmos
utilizando modelos matemáticos. Esto fue realizado por Alonzo Church en 1936 con el
concepto de "calculabilidad efectiva" basada en su cálculo lambda y por Alan
Turing basándose en la máquina de Turing. Los dos enfoques son equivalentes, en el
sentido en que se pueden resolver exactamente los mismos problemas con ambos enfoques.
Sin embargo, estos modelos están sujetos a un tipo particular de datos como son números,
símbolos o gráficas mientras que, en general, los algoritmos funcionan sobre una vasta
cantidad de estructuras de datos. En general, la parte común en todas las definiciones se
puede resumir en las siguientes tres propiedades siempre y cuando no
consideremos algoritmos paralelos:
Tiempo secuencial. Un algoritmo funciona en tiempo discretizado –paso a paso–,
definiendo así una secuencia de estados computacionales por cada entrada válida
(la entrada son los datos que se le suministran al algoritmo antes de comenzar).
Estado abstracto. Cada estado computacional puede ser descrito formalmente
utilizando una estructura de primer orden y cada algoritmo es independiente de su
implementación (los algoritmos son objetos abstractos) de manera que en un
algoritmo las estructuras de primer orden son invariantes bajo isomorfismo.
Exploración acotada. La transición de un estado al siguiente queda completamente
determinada por una descripción fija y finita; es decir, entre cada estado y el
siguiente solamente se puede tomar en cuenta una cantidad fija y limitada de
términos del estado actual.
En resumen, un algoritmo es cualquier cosa que funcione paso a paso, donde cada paso se
pueda describir sin ambigüedad y sin hacer referencia a una computadora en particular, y
además tiene un límite fijo en cuanto a la cantidad de datos que se pueden leer/escribir en
un solo paso. Esta amplia definición abarca tanto a algoritmos prácticos como aquellos que
solo funcionan en teoría, por ejemplo el método de Newton y la eliminación de Gauss-
Jordan funcionan, al menos en principio, con números de precisión infinita; sin embargo no
es posible programar la precisión infinita en una computadora, y no por ello dejan de ser
algoritmos.
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 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 este 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
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
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 c0, c1, .... cn.
Es decir, dado un conjunto C = { c0, c1, .... cn.} se pide encontrar m tal que x ≤ 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
El algoritmo puede ser escrito de una manera más formal en el siguiente pseudocódigo:
Algoritmo Encontrar el máximo de un conjunto
función max(C)
//C es un conjunto no vacío de números//
n ← |C| // |C| es el número de elementos de C//
m ← c0
para i ← 1 hasta n hacer
si ci > m entonces
m ← ci
devolver m
Sobre la notación:
"←" representa una asignación: m ← x significa que la variable m toma el valor
de x;
"devolver" termina el algoritmo y devuelve el valor a su derecha (en este caso, el
máximo de C).
Implementación
En lenguaje C++:
int max(int c[], int n)
{
int i, m = c[0];
for (i = 1; i < n; i++)
if (c[i] > m) m = c[i];
return m;
}
