Métodos de Programación
Clase # 8
Algoritmos – Definición
Prof. Mauricio Rivera
Definición Historica
La palabra algoritmo se deriva de
la traducción al latín de la palabra
árabe alkhowarizmi, nombre de
un gran matemático árabe,
Mohamed Ibn Moussa Al Kow Rizmi,
quien escribió entre los años 800 y
825 en la actual nacion Iraní su
obra “Quitab Al Jabr Al Mugabala”,
donde describió la realización de
operaciones elementales en el
sistema numérico decimal
recogiendo el sistema de
numeración hindú y el concepto del
cero.
Definición Historica
Fue Fibonacci, quien tradujo la obra
de Al Kow Rizmi al latín y la inició con
las palabras: Algoritmi dicit.
Euclides, el gran matemático griego
(del siglo IV antes de Cristo) que invento
un método para encontrar el máximo
común divisor de dos números, se
considera con Al Kow Rizmi el otro
gran padre de la algoritmia (ciencia
que trata de los algoritmos).
Definición
El lenguaje algorítmico es aquel en el que se
realiza un análisis previo del problema a resolver
y con el cual se encuentra un método que
permita resolverlo.
El conjunto de todas las operaciones a realizar
en un tiempo finito y el orden en que deben
efectuarse, se le denomina algoritmo
Los pasos para resolver el problema se especifican en
base a operaciones básicas que controlan las variables y el
flujo del algoritmo
El algoritmo lleva desde un estado inicial a un estado final
El algoritmo recibe Entradas y entrega Salidas
Definición Formal
Todo Algoritmo debe ser:
Preciso. Indicando el orden de realización de
cada uno de los pasos.
Definido. Si se sigue el algoritmo varias
veces proporcionándole los mismos datos, se
deben obtener siempre los mismos resultados.
Finito. Al seguir el algoritmo, éste debe
terminar en algún momento, es decir, debe
terminar en un número finito
Definición Formal
La definición de un algoritmo debe definir tres
partes: Entrada, Proceso y Salida
Entrada
El Algoritmo tendrá cero o más entradas
Salida
El algoritmo debe tener una o más salidas, en relación con las
entradas
A menudo los algoritmos requieren una organización
bastante compleja de los datos, y es por tanto
necesario un estudio previo de las Estructuras de
Datos Fundamentales.
El uso de estructuras de datos adecuadas pueden
hacer trivial el diseño de un algoritmo, o puede
suceder que un algoritmo muy complejo utilice
estructuras de datos muy simples
Algoritmos
Caso, Instrucciones para subir una escalera
Se comienza por levantar esa parte del cuerpo situado a la
derecha abajo, envuelta casi siempre en cuero o gamuza, y que
salvo excepciones cabe exactamente en el escalón.
Puesta en el primer peldaño dicha parte, que para abreviar
llamaremos pie, se recoge la parte equivalente de la izquierda
(también llamada pie, pero que no ha de confundirse con el pie
antes citado), y llevándola a la altura del pie, se le hace seguir
hasta colocarla hasta el segundo peldaño, con lo cual en éste
descansará el pie, y en el primero descansará el pie.
Nota:
Los primero peldaños son siempre los más difíciles, hasta adquirir la
coordinación necesaria.
La coincidencia de nombre entre el pie y el pie hace difícil la
explicación.
Cuídese especialmente de no levantar al mismo tiempo el pie y el
pie.
Julio Cortazar
Escritor
Algoritmos
Otro caso
Humedezca su cabellera.
Aplique con la espuma un suave masaje al pelo.
Enjuague evitando que la espuma entre en sus ojos.
Repita
Serie de instrucciones que se encuentran en la etiqueta de
una botella de champú.
¿se ajusta a la definición técnica de algoritmo?, En otras
palabras, ¿produce un resultado?
Es posible que diga si, pero vea más de cerca.
El algoritmo requiere que usted se mantenga repitiendo el
procedimiento un número infinito de veces,
Así que, teóricamente ¡nunca deberá parar de lavar su cabello!
Un algoritmo de computadora debe terminar en un tiempo
finito.
La instrucción de repetición puede alterarse con facilidad para
hacer el algoritmo del champú técnicamente correcto:
Repita hasta que el pelo esté limpio
Algoritmos
Ahora vamos a desarrollar un algoritmo para el envío
de una carta por correo.
Primero debe escribir la dirección en el sobre, doblar la carta,
meter la carta en el sobre y cerrar el sobre con pegamento.
Necesita también una estampilla, si no tiene una, tendrá que
comprarla. Una vez que tenga la estampilla, debe colocarla en el
sobre y enviar la carta.
Algoritmos
El siguiente algoritmo resume los pasos de este proceso:
Obtener un sobre.
Escribir la dirección en el sobre.
Doblar la carta.
Meter la carta en el sobre.
Cerrar el sobre.
En caso de no tener una estampilla, entonces comprar una.
Pegar la estampilla en el sobre.
Enviar la carta por correo.
¿Esta secuencia de instrucciones se ajusta a nuestra definición
de un buen algoritmo? En otras palabras, ¿produce la
secuencia de instrucciones un resultado en una cantidad finita
de tiempo?
Sí, suponiendo que cada operación pueda ser entendida y llevada
a cabo por la persona que envíe la carta por correo.
Algoritmos
Esto trae dos características adicionales de los buenos
algoritmos:
Cada operación dentro del algoritmo debe ser bien definida y
efectiva.
Por bien definida se entiende que cada uno de los pasos debe
ser claramente entendible por personas de procesamiento de
datos.
Por efectiva, se entiende que debe existir algún medio para llevar
a cabo la operación. En otras palabras, la persona que envíe la
carta debe poder realizar cada uno de los pasos del algoritmo.
Otras Caracteristicas
A la hora de estudiar la calidad de un algoritmo, es
deseable que los algoritmos presenten también otra serie
de características
Validez.
El algoritmo construido hace exactamente lo que se pretende
hacer.
Eficiencia.
El algoritmo debe dar una solución en un tiempo razonable. Por
ejemplo, para sumar 20 a un número
Algoritmo que sume uno veinte veces.
Sería mejor hacer un algoritmo que lo haga de un modo más directo.
Optimización.
Se trata de dar respuesta a la cuestión de si el algoritmo diseñado
para resolver el problema es el mejor.
En este sentido y como norma general, será conveniente tener en
cuenta que suele ser mejor un algoritmo sencillo que no uno
complejo, siempre que el primero no sea extremadamente
ineficiente.
“Divide las dificultades que examinas en tantas partes
como sea posible para su mejor solución.”
René Descartes
Filósofo y matemático francés
