Algoritmos

Cap´ ıtulo 1

Los algoritmos y la computaci´n o
Antes de comenzar, debemos hacernos las siguientes preguntas: ¿Que son los algoritmos? ¿Porqu´ vale la pena estudiar los algoritmos? e ¿Cual es la relaci´n de los algoritmos con otras tecnolog´ o ıas?

1.1.

Algoritmos

Podemos definir a un algoritmo como un procedimiento computacional bien definido y finito, el cual toma un conjunto devalores como entrada y produce un conjunto de valores de salida. Tambi´n puede ser visto como una e secuencia de pasos que transforma la entrada en una salida. Desde otra perspectiva es posible ver a un algoritmo como una herramienta para resolver un problema computacional bien definido. La definici´n del o problema especifica la relaci´n que existe entre la entrada y la salida. o Un ejemplo t´ ıpico de unproblema computacional es el ordenamiento de un conjunto de n´ meros, es decir, dado un conjunto de n´meros, tenemos la u u tarea de encontrar una permutaci´n de dicho conjunto en el cual dichos n´meros o u esten colocados en orden no decreciente. Este problema es muy utilizado como introducci´n a los algoritmos debido a la existencia de diversas y muy variadas o t´cnicas de an´lisis y dise˜o dealgoritmos. Formalmente podemos definir el e a n problema del ordenamiento de la siguiente manera: ENTRADA: Conjunto de n n´meros a1 , a2 , . . . , an . u SALIDA: Conjunto de n n´meros a1 , a2 , . . . , an , el cual es una permutaci´n u o de la entrada que cumple la siguiente relaci´n de orden a1 ≤ a2 ≤ · · · ≤ an . o Veamos un ejemplo, dada la siguiente secuencia de entrada: 9, 2, 8, 7, 3, 4, 1 12

´ CAP´ ITULO 1. LOS ALGORITMOS Y LA COMPUTACION

un algoritmo de ordenamiento que reciba esta entrada obtendr´ la siguiente ıa salida: 1, 2, 3, 4, 7, 8, 9 Una secuencia de entrada es conocida como una instancia del problema, la cual debe cumplir con las restricciones definidas para el problema, necesarias para calcular la salida de dicha instancia. El ordenamiento es una operaci´nfundamental en cualquier ´rea dentro de o a las ciencias de la computaci´n, ya que muchos algoritmos lo utilizan como un o paso intermedio, por lo que se han desarrollado un amplio conjunto de algoritmos para resolver dicho problema. Al existir diversos algoritmos para resolver este problema, quisieramos saber cual es el mejor de entre todos ellos. Existen diversos factores, de los cuales dependen laelecci´n del mejor, entre los cuales o destacan el n´mero de elementos a ordenar, la cantidad de elementos que de u antemano est´n ordenados, algunas restricciones en los valores, y el tipo de a dispositivos de almacenamiento (memoria, disco duro o cintas). Un algoritmo se dice que es correcto si para cada instancia del problema, calcula la salida correcta, en este caso decimos que el algoritmoresuelve el problema computacional. Un algoritmo incorrecto no obtendr´ la salida correca ta al menos para una instancia del problema. Contrariamente, con lo que uno podr´ pensar, los algoritmos incorrectos no son del todo in´tiles, si la tasa de ıa u error se puede mantener controlada. De cualquier forma, por el momento s´lo o nos interesar´n los algoritmos considerados como correctos. a ¿Qu´ tiposde problemas pueden resolver los algoritmos? e El ordenamiento es tan s´lo un ejemplo de un tipo de problema que puede o ser resuelto por los algoritmos. La aplicaci´n de los algoritmos est´ en todos o a lados. A continuaci´n se presentan algunos ejemplos: o El proyecto del genoma humano tiene como objetivos identificar los 100,000 genes en el ADN(´cido desoxirribonucleico) del genoma humano,determia nar la secuencia de las 3 billones de bases qu´ ımicas que conforman al ADN, almacenar dicha informaci´n en una base de datos y desarrollar o herramientas para analizar dicha informaci´n. Cada uno de estos pasos o requiere de algoritmos sumamente sofisticados. La mayor´ de estas tareas ıa est´n fuera de nuestro alcance, al menos por el momento, sin embargo a las ideas desarrolladas a lo largo...