Programacion

Algoritmo

Definimos como algoritmo a un conjunto de pasos necesarios para resolver un problema ya sea manualmente o por m´todos mecanizados que, e son los m´s usuales en la actualidad. El concepto de algoritmos fue definido a inicialmente por el matem´tico Persa Al-Khowˆrizmˆ en el siglo diecinueve. a a ı La ejecuci´n de un algoritmo no debe incluir procedimientos intuitivos o o que requierancreatividad. Por ejemplo, una receta de cocina puede denominarse un algoritmo si contiene las instrucciones precisas para preparar algo, siempre y cuando no tenga detalles tales como sal al gusto, o cocinar hasta que est´ suave, que son apreciaciones subjetivas del que prepara la receta. e Debemos indicar que los algoritmos deben cumplir un requisito fundamental y es que todo algoritmo debe terminaren un n´mero finito de pasos. u Si consideramos el sistema operativo veremos que no es un algoritmo porque no termina nunca, dado que est´ en un ciclo infinito. a 1

2

1. ALGOR´ ITMICA ELEMENTAL

Podemos citar algunos ejemplos de algoritmos conocidos, el m´todo de e multiplicar que aprendimos en la escuela, el algoritmo para verificar si un n´mero es primo y muchos otros. u

1.3.Problemas e instancias

Si pensamos los procedimientos para multiplicar n´meros que conocemos u veremos que hay varias formas de resolver el problema de multiplicaci´n. o Tenemos los m´todos que aprendimos en la escuela, m´todos por divisi´n y e e o multiplicaci´n por 2 denominado multiplicaci´n a la rusa y otros. ¿Cu´l de o o a ´stas posibles soluciones hay que implementar? Esta decisi´n correspondea e o un ´rea muy desarrollada en el campo de la inform´tica denominada an´lisis a a a de algoritmos. Una instancia particular ser´ por ejemplo multiplicar el n´mero 123 por ıa u el 4567 pero un algoritmo debe ser capaz de funcionar correctamente no solo en una instancia del m´todo sino m´s bien en todas las instancias posibles. e a Para demostrar que un algoritmo es incorrecto, es suficientedemostrar que es incorrecto para una instancia . As´ como es dif´ probar que un ı ıcil teorema es correcto tambi´n es dif´ probar que un algoritmo es correcto. e ıcil Existen limitaciones propias de las computadoras que ponen restricciones a los algoritmos. Estas pueden ser debido al tama˜o de los n´meros, n u espacio de memoria o almacenamiento. En el an´lisis de los algoritmos, se a trata deanalizarlos en forma abstracta inicialmente, pero en el transcurso del texto tambi´n tocaremos aspectos espec´ e ıficos sobre la implementaci´n y o la eficiencia de los mismos.

1.4.

Eficiencia

Cuando tenemos que resolver un problema pueden existir muchos algoritmos disponibles. Obviamente quisi´ramos escoger el mejor. De aqu´ nos e ı viene la pregunta ¿Cu´l es mejor? a Si tenemos un problemasencillo con algunas pocas instancias escogemos, lo m´s f´cil y nos despreocupados de la eficiencia. a a Para analizar ´sto tenemos dos m´todos. El m´todo emp´rico tambi´n e e e ı e llamado a posteriori, consiste en programar todos los m´todos y probarlos e con diferentes instancias y con la ayuda de la computadora analizamos y

1.4. EFICIENCIA

3

escogemos alguno. El segundo llamado m´todoapriori es el an´lisis te´rico del algoritmo, e a o que con la ayuda de las matem´ticas podemos determinar la cantidad de los a recursos requeridos por cada algoritmo en base del tama˜o de las instancias n consideradas. El tama˜o de una instancia normalmente est´ definida por el n´mero de n a u bits, en el caso de un grafo por el n´mero de nodos y v´rtices, o en otros u e por el n´mero de elementos aprocesar. La ventaja del m´todo te´rico es que u e o no depende de la computadora, lenguaje de programaci´n o implementaci´n o o particular. En el tratamiento del tema utilizaremos en algunos casos un m´todo e h´ ıbrido donde se determinar´ la eficiencia en forma te´rica y se hallar´n los a o a valores num´ricos en forma experimental. e Retornando a la pregunta debemos indicar que la eficiencia se...