rafael angel garc´ıa leiva´ july 9, 2006 filechapter 1 el arte de programar la mayor´ıa de las...

El Mundo de los Algoritmos

Rafael Angel Garcıa Leiva

July 9, 2006

Prologo

Hablar sobre la dificultad de encontrar referencias bibliograficas en castellano.

1

Chapter 1

El Arte de Programar

La mayorıa de las ciudades de hoy en dıa funcionan gracias a los ordenadores.Sea cual sea el lugar a donde vayamos siempre encontraremos un ordenadorcerca. Son ya tan comunes que ni siquiera nos damos cuenta de que estan ahı,pero basta con detenemos un momento y fijamos con atencion para verlos, puedeincluso que los encontremos en los lugares mas insospechados. En la oficina ten-emos ordenadores que nos ayudan a hacer nuestro trabajo; en casa tenemos unordenador como centro de ocio, para juegos, musica y video, o miniordenadoresempotrados dentro de los mas variados electrodomesticos, como la television, elequipo de alta fidelidad, e incluso en el microondas; en el supermercado de laesquina hay unos cuantos ordenadores mas, las cajas registradoras, los equiposde inventario; en nuestro coche esta el famoso ordenador de abordo, que vig-ila que todo funciona correctamente; y ası un largo etcetera. Y tambien estanaquellos ordenadores que llevamos todo el dıa de un lado a otro con nosotros,como el telefono movil, la agenda electronica, o el reloj. Hemos llegado a unasituacion de dependencia tal que nos resulta muy difıcil concebir el mundo sinla existencia de los ordenadores1.

Lo que nunca hacemos, a menos que uno sea un profesional que trabaja enel mundo de la informatica, es pararnos a reflexionar sobre como funcionanantodos estos ordenadores. Nos han dicho muchas veces que los ordenadores sonen realidad maquinas muy tontas, que para funcionar correctamente necesitande un conjunto de instrucciones que les digan con todo lujo de detalles que es loque tienen que hacer en cada momento, y como lo tienen que hacer. Tambiensabemos que estos conjuntos de instrucciones se llaman programas, y que losprogramas se escriben utilizando los llamados lenguajes de programacion, queson muchos y muy variados. Seguramente nos suenen nombres como VisualBasic, Java o C++. Pero en realidad sabemos muy poco sobre la forma ycontenido de estos programas, lo cual es perfectamente comprensible, porque apriori parece un tema irrelevante y sumamente aburrido. ¿A quien se le ocur-rirıa estudiar en su tiempo libre el programa que controla un aparato de aire

1Otra cuestion muy distinta es si realmente en todos los casos el ordenador nos hace lavida mas facil, pero este es un tema del que no vamos a hablar en este libro.

2

CHAPTER 1. EL ARTE DE PROGRAMAR 3

acondicionado? Sin embargo, los programas no son tan aburridos como parece.En el corazon de los programas se encuentran los algoritmos. La mayorıa de lasveces, estos algoritmos son simples sucesiones de pasos triviales que conducen ala solucion de un problema. Por ejemplo, si la temperatura de la habitacion hasuperado los 25o centıgrados, entonces enciende el compresor del aire acondi-cionado. Pero otras veces, los alogitmos que implementan los programas deordenador son verdaderas obras de arte del intelecto humano. Quien sabe, a lomejor el funcionamiento de nuestro aparato de aire acondicionado esta basadoen una interesantısima teorıa matematica de logica difusa, donde las cosas noson solo ciertas o falsas, sino que pueden ser medio ciertas o tres cuartos falsas.

En este libro vamos a ver algunas de esas joyas de la programacion que hayescondidas dentro de los ordenadores. Veremos como problemas aparentementemy simples requieren de algoritmos muy complejos para su solucion, o de al-goritmos que en la practica resultan inutiles porque requieren cientos de anosde calculo. Tambien estudiaremos ejemplos del caso contrario, es decir, comoproblemas que en un principio parecıan intratables son resueltos de manera muysimple, generalmente gracias a la ayuda de alguna idea brillante. Aprendere-mos como comparar algoritmos, en base al tiempo que tardan en resolver unproblema, y a la cantidad de memoria que necesitan para ello, y veremos quepueden existir enormes diferencias entre dos algoritmos que resuelven un mismoproblema. Por utimo estudiaremos las tecnicas mas comunes de resolucion deproblemas de las que se valen los programadores para hacer su trabajo. Todoello mezclado con algunas notas historicas, anecdotas, preguntas sin respuestaconocida, y sobre todo, con numerosos problemas propuestos para que el lectorpueda divertirse creando sus propios algoritmos.

1.1 Pero, ¿que es un algoritmo?

Hasta ahora he asumido que el lector tiene al menos una idea intuitiva de loque es un algoritmo, y tambien que tiene unos conocimientos mınimos sobre elfuncionamiento de los ordenadores (que es un programa de ordenador, cual es ladiferencia entre hardware y software, etcetera). Pero para poder continuar connuestro viaje por el maravilloso mundo de los algoritmos, y para poder apreciarmejor la belleza del paisaje que se nos ofrece, tenemos que definir de maneramas precisa que entendemos por algoritmo y aclarar algunos conceptos basicos.

La Real Academia de la Lengua define la palabra algoritmo como conjuntoordenado y finito de operaciones que permite hallar la solucion de un problema.Aunque quizas no seamos conscientes de ello, es muy normal que nos ayudemosde algoritmos en nuestra vida contidiana, y no solo cuando utilizamos orde-nadores o realizamos calculos algebraicos. Por ejemplo, cuando compramos unaestanterıa barata de las de montela usted mismo, junto con las tablas de maderaencontramos un folleto de instrucciones con un algoritmo que nos indica comomontarla; cuando nos subimos en nuestro coche seguimos un algoritmo precisoque nos indica como conducir (introducir la llave, girarla a la posicion de con-tacto, volverla a girar hasta la posicion de arranque, soltar la llave cuando el


motor arranque, pisar el embrague, introducir la marcha primera, etc); o cuandoinvitamos a unos amigos a cenar a casa y queremos sorprenderlos con un menuespecial, consultamos un libro de recetas de cocina, que en definitiva no es otracosa que un libro lleno de algoritmos culinarios.

Veamos uno de estos ejemplos con mas detalle. Imaginemos que queremoshacer una tortilla de patatas pero, como nos ha pasado a todos en algun mo-mento de nuestra vida, no sabemos como se hace. Ası que cojemos nuestrolibro de recetas de concina para hijos recien emancipados, y buscamos la recetacorrespondiente a la tortilla. Seguramente el libro encontraremos algo parecidoa:

Trocear las patatas en taquitos de medio centımetro cuadrado,y freirlas en una sarten con aceite abundante y no muy caliente. Alpoco rato, anadir la cebolla y dejar que se frıa junto con las patatas.En un cuenco batimos los huevos, le echamos sal, y anadimos laspatatas y cebolla ya fritas, mezclandolo todo bien. Dejamos un pocode aceite en la sarten y hechamos la mezcla. Esperamos a que secuaje un poco, le damos la vuelta, y la dejamos a fuego lento hastaque termine de cuajar.

Evidentemente el parrafo anterior, aunque resulta facil de entender para cualquierser humano, es totalmente incomprensible para un ordenador. Podrıamos ree-scribir la receta de manera algo mas formal y precisa, intentando darle aparienciade programa de ordenador (vease el cuadro titulado Algorimo 1), pero aun asıseguirıa siendo un galimatıas ininteligible para las maquinas. De hecho, auncontando con instrucciones tan precisas de como se hace una tortilla de patatas,es normal que a cada uno de nosotros nos salgan tortillas completamente difer-entes (yo personalmente, aun no consigo entender que hace mi mujer para quea ella le salgan las tortillas mucho mas ricas que a mi). El problema es que nue-stro algoritmo “Tortilla de Patatas” contiene todavıa muchos elementos que, obien tienen interpretaciones subjetivas (¿a que temperatura se entiende que elaceite no esta muy caliente?), o bien estan descritos de manera demasiado vaga(¿que se entiende por cuajar?), y por tanto, no son directamente interpretablespor un ordenador. Las recetas, tal y como nos las encontramos en los libros deconcina, no entrarıan dentro de lo que en informatica se conoce como proced-imientos computacionalmente bien definidos, y por tanto, no son directamenteinterpretables por los ordenadores. Los algoritmos utilizados en informaticatienen que ser bastante mas precisos que nuestro ejemplo de la tortilla, y basaseen pasitos mas pequenos.

Un algoritmo para ordenador esta compuesto de un conjunto de pasos muysimples y muy bien definidos. Ejemplos tıpicos de posibles pasos son: sumardos numeros dados, comparar si un numero es mayor que otro, comprobar sila tercerla letra de la palabra “ejemplo” es una “e”, etcetera. Estos pasossuelen venir agrupados en bloques que se pueden repetir varias veces, tambienexisten pasos en los que es posible tomar decisiones, llamadas a grupos de pasoscomunes, etc. Ademas, para que el algoritmo este completo, es fundamental


Algorithm 1 Tortilla de Patatas1 Cortar patatas en tacos2 Calentar aceite en sarten3 A~nadir patatas a sarten4 A~nadir cebolla a sarten5 Freir patatas y cebolla6 Batir huevos en cuenco7 A~nadir patatas y cebolla al cuenco8 Quitar aceite sarten9 Hechar la mezcla de cuenco a sarten10 Cuajar un poco y dar la vuelta11 Terminar de cuajar

indicar cuales son los valores de entrada del mismo, y cuales son los resultadoso valores de salida. Por ejemplo, un algoritmo podrıa tener como entrada unconjunto de diez numeros (17, 1, 5, 13, 15, 9, 21, 2, 4, 8), y como salida devolverel mismo conjunto de numeros pero ordenados de mayor a menor (21, 17, 15,13, 9, 8, 5, 4, 2, 1).

Pero no se preocupe el lector si por ahora no entiende del todo como sonlos algoritmos que utilizan los ordenadores, ya que todas estas cuestiones iranquedando mas claras a lo largo de este libro.

1.2 Un poco de historia

Antes de entrar a fondo en materia es conveniente dedicar algo de tiempo arevisar los orıgenes de los algoritmos, como ha ido evolucionando el concepto dealgoritmo a lo largo de la historia, y sobre todo, quienes han sido los artıficesde todas estas ideas tan maravillosas.

Euclides de Alejandrıa (325 adC, 265 adC) fue el mas importante de losmatematicos de la antiguedad, sin embargo, se sabe muy poco de su vida, ex-cepto que enseno en Alejandrıa, y en Egipto. Euclides debio de haber estudiadoen la Academia de Platon en Atenas, donde aprendio la geometrıa de Eudoxusy Theaetetus, con los que estaba muy familiarizado. Su trabajo mas conocidoes un tratado en matematicas titulado Los Elementos. El tratado es un com-pendio del conocimento matematico de la epoca, que se convirtio en el centrode la ensenanza de las matematicas durante mas de 2000 anos. La durabilidadde los Elementos hacen de Euclides el profesor de matematicas lıder indiscutiblede la antiguedad, y quizas de todos los tiempos. Seguramente los resultados queencontramos en Los Elementos no fueron demostrados por primera vez por Eu-clides, pero la organizacion del material y la exposicion son con toda seguridadsuyas. Desde que fue escrito y hasta la fecha, Los Elementos han constituidouna continua e importante influencia, consituyendo una fuente primaria para elrazonamiento geometrico, teoremas y metodos. A veces se dice que, junto con


Figura 1.1: Imagen de Al-Khwarizmi en un sello sovietico

la Biblia, los Elementos puden ser el libro de texto mas traducido, publicado yestudiado del mundo occidental.

Los Elementos se dividen en 13 libros. Los libros de uno a seis tratan de lageometrıa del plano; los libros de siete a nueve tratan de la teorıa de numeros;el libro diez trata de la teorıa de los numeros irracionales; y los libros de oncea trece tratan de la geometrıa en tres dimensiones. En particular nos aquı nosinteresa el libro numero siete, una introduccion auto-contenida de la teorıa denumeros, porque contiene el famoso algoritmo de Euclides, un metodo muy as-tuto para calcular el maximo comun divisor de dos numeros (vease la Seccion1.3), y que esta considerado como el primer alroritmo de la historia de la hu-manidad.

La palabra algoritmo proviene del nombre del matematico persa del sigloIX Abu Abdullah Muhammad bin Musa al-Khwarizm (vease Figura 1.1). Al-Khwarizmi fue el matematico mas influyente de su tiempo, y su legado incluyealgunos conceptos que hoy dıa resultan basicos en algebra. En realidad se conocemuy poco sobre la vida de Al-Khwarizmi, se sabe que trabajo en la Casa dela Sabidurıa de Bagdad, y que su trabajo consistıa fundamentalmente en latraduccion de manuscritros cientıficos griegos, aunque tambien hizo importantescontribuciones en algebra, geometrıa y astronomıa.

Sin duda, el trabajo mas importante y conocido de Al-Khwarizmi es sutratado sobre algebra al-jabr w’al-muqabal. Este tratado es el primer libro dela historia donde se estudia en profundidad y de manera sistematica el algebra,y por tanto, se habla de Al-Khwarizmi como fundador de esta rama de lamatematica (de hecho, el tıtulo del tratado al-jabr ha dado origen a la propiapalabra algebra). El tratado sobre algebra de Al-Khwarizmi tambien es impor-tante porque describe el sistema posicional hindu de numeracion, basado en losguarismos decimales 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, y que ahora conocemos comun-mente como numeros arabigos. Aunque no seamos consciente de ello, el sistemaposicional es fundamental en algebra, y si no, trate el lector de multiplicar 728por 293 utilizando el sistema de numeracion romano (es decir DCCXXVIII por


Figure 1.2: Ada Lovelace

CCXCIII). En el tratado tambien se introduce el uso del cero como contenedorde lugar en la notacion basada en posiciones, otra idea fundamental para eldesarrollo actual del algebra, que nos permite distinguir entre, por ejemplo, lascantidades 202, 220 y 22. De echo, hay autores que opinan que la invencciondel cero fue mas importante que la invencion de la propia rueda.

Originalmente la palabra algoritmo se referıa unicamente al conjunto dereglas necesarias para realizar aritmetica utilizando los numeros arabigos. Fueen el sigo XVIII cuando el concepto evoluciono para incluir a todo procedimientobien definido para resolver un problema dado, o realizar una tarea concreta.

El primer ejemplo de algoritmo escrito especıficamente para un ordenadorfue realizado por Augusta Ada King (vease la Figura 1.2), Condesa de Lovelace,en 1842. El ordenador en cuestion era el Ingenio Analıtico de Charles Bab-bage, concebido en 1834. El Ingenio Analıtico de Babbage era una computa-dora mecanica programable, de caracterısticas muy similares a los ordenadoreselectronicos modernos: disponıa de un sistema de entrada de datos basado entarjetas perforadas, una memoria con capacidad para almacenar 1000 numerosde 50 dıgitos, una unidad capaz de realizar las cuatro operaciones aritmeticasbasicas, y una impresora.

Ada Lovelace tradujo para Babbage el memorandum que el matematico LuigiMenabrea habıa escrito sobre el Ingenio Analıtico. Junto a la traduccion, Adaanadio un conjunto de notas en las que describia en detalle un procedimientopara calcular numeros de Bernoulli2 utilizando la maquina, y que ha sido recono-cido por los historiadores como el primer programa de ordenador. En realidadel Ingenio Analıtico no era una maquina tangible, sino que se trataba de un con-junto de disenos que Babbage fue perfeccionando a lo largo de su vida. Dadoque Babbage nunca llego a construir su ingenio analıtico, el algoritmo de AdaLovelace no se llego a implementar. A pesar de ello, para muchos (incluido elautor de este libro) Ada Lovelace es considerada como la primera programadora

2Secuencia de numeros racionales con importantes implicaciones en teoria de numeros yanalisis matematico.


Figure 1.3: Alan Turing

de ordenadores de la historia. Ada Lovelace tambien es conocida, aparte depor ser la unica hija legıtima del poeta Lord Byron, por haber dado nombre allenguaje de programacion Ada3.

La falta de rigor matematico en la definicion algoritmo como procedimentobien definido creo muchas dificultades a los matematicos y logicos del siglo XIXy principios del XX. Este problema fue en gran medida resuelto gracias a ladescripcion formal de algoritmo proporcionada por lo que hoy se conoce con elnombre de Maquina de Turing, un modelo abstracto de computadora formuladopor el matematico britanico Alan Mathision Turing en 1936.

Turing hizo importantes contribuciones en matematicas, logica y criptoanalisis.Durante la segunda guerra mundial trabajo para los aliados descifrando losmensajes del ejercito aleman, y en concreto, descifrado el codigo secreto de lafamosa maquina Enigma. Una vez finalizada la guerra trabajo en el desarrollode software para uno de los primeros ordenadores de la histororia, el Mark Ide Manchester, ademas de que diseno su propia computadora, llamada ACE,que no llego a construirse. Turing tambien es conocido por sus ideas en el areade la inteligencia artificial, donde proporciono un experimento conocido con elnombre de Test de Turing que nos permite determinar si una maquina es o nointeligente. Pero sin lugar a dudas, el trabajo mas influyente de Turing es sucontribucion a los fundamentos de la informatica: actualmente las maquinasde Turing constituyen una parte fundamental en el estudio de la teorıa de lacomputacion.

Turing fue un homosexual durante una epoca donde la homosualidad era ile-gal. En 1952 fue condenado por actitudes indecentes al admitir que habıa man-tenido relaciones sexuales con un hombre en Manchester. La condena tambien

3Ada es un lenguaje de proposito general que fue desarrollado por el departamento de de-fensa norteamericano en un intento de contener la torre de babel de lenguajes de programacionen la que se habıan convertido los proyectos informaticos (en 1983 se estimaba que habıa delorden de 450 lenguajes de programacion diferentes en uso en el departamento).


le impuso que siguiera una terapia hormonal para corregir su homosexualidad.Dos anos despues, en Junio de 1954, Alan Turing fue encontrado muerto en sucasa al haber ingerido una manzana impregnada con cianuro. Si fue un sui-cidio, o un accidente (Turing disponia de un laboratorio de fotografıa en el queutilizaba habitualmente cianuro), es algo que todavıa no esta resuelto.

Dede el ano 1966 la asociacion internacional de informatica ACM (Associ-ation for Computing Machinery) concede anualmente el premio Turing, que esotorgado a aquellos investigadores que hayan destacado por sus contribucionestecnicas a la comunidad informatica. Estos premios estan considerados comolos equivalentes en informatica a los premios Nobel.

1.3 El algoritmo de Euclides

Por fin ha llegado el momento de ver nuestros primeros algoritmos. En concretovamos a estudiar dos ejemplos de algoritmos, que aunque son totalmente difer-entes, resuelven exactamente el mismo problema: calculan el maximo comundivisor de dos numeros dados. El primero de ellos esta basado en un metodomas bien ingenuo para el calculo del maximo comun divisor; el segundo se basaen una idea muy original que nos simplificara enormemente la tarea. Estos dosalgoritmos nos van a permitir introducir algunos conceptos importantes sobrealgorıtmica y la programacion de ordenadores, y tambien nos van a ayudar adefinir la notacion que vamos a utilizar a lo largo de este libro para la descripcionde los algoritmos.

Antes de empezar a estudiar en detalle estos algoritmos, me gustarıa asegu-rarme de que todos mis lectores tienen los conocimientos necesarios para enten-der lo que vamos a hacer. Para ello, aquellos lectores que no tengan experienciaprevia en la programacion de ordenadores, y que no conozcan ningun lenguaje deprogramacion, deberıan leer primero el Apendice 12 donde se proporciona unaintroduccion a la programacion lo suficientemente detallada para entender loscontenidos de este libro. Aquellos lectores que tengan cierta experiencia previaen el manejo de ordenadores, y que conozcan algun lenguaje de programacion,pueden continuar leyendo directamente, aunque tambien se les recomienda quehechen un vistazo rapido al Apendice 12, con la idea de familizarizarse con lanotacion en pseudocodigo que vamos a utilizar en el libro.

Vamos a la tarea. Recordemos que el maximo comun divisor de dos numerosenteros positivos a y b, escrito como MCD(a, b), es el mayor de los divisorescomunes de a y de b, es decir, el mayor de aquellos numeros que dividen a lavez a ambos. Por ejemplo MCD(5, 3) = 1, MCD(15, 9) = 3, y MCD(60, 15) =5. El calculo del maximo comun divisor resulta muy util a la hora de simplificarfacciones, por ejemplo la fraccion 60

15 podrıamos simplificarla a 12x53x5 = 12

3 .En el Algoritmo 2 podemos encontrar el primer metodo para el calculo del

maximo comun divisor. El algoritmo recibe como parametros de entrada dosnumeros, a y b, y como resultado nos muestra en pantalla el MCD(a, b). Paraello, el algoritmo se basa en un procedimiento muy simple: primero calcula cuales el menor de los numeros a y b, a continuacion recorre todos los numeros que


Algorithm 2 Calculo del MCDfuncion MCD(a, b)min := mınimo(a, b);para x := 1 hasta min hacer

si (modulo(a, x) = 0 ) & (modulo(b, x) = 0) entoncesmcd := x

finsifinparaescribir(mcd)

van desde 1 hasta el menor de a y b, y para cada uno de ellos comprueba sidividen a la vez a ambos. Para comprobar si un numero x divide a otro y, lo quehacemos es utilizar la funcion modulo, que nos devuelve el resto de la divisionenterea entre x e y (por ejemplo modulo(7, 2) = 1, o modulo(6, 2) = 0, encuyo caso 2 es un divisor de 6 pero no de 7). Al final del bucle para, tendremosen la variable mcd el mayor de los numeros que han dividido a la vez a a y b, esdecir, su maximo comun divisor.

Existen muchas formas de mejorar el algoritmo anterior. Por ejemplo, noharıa falta comprobar cuales son los divisores de a y b desde 1 hasta mınimode a y b, bastarıa con comprobar desde 1 hasta la raiz cuadrada del mınimo(piense el lector por que).

Otra manera mas refinada de calcular el MCD serıa mediante la factorizacionde los numeros a y b. Recordemos que cualquier numero entero puede serdescompuesto de manera unica mediante el producto de numeros primos. Porejemplo: 6 = 2 ∗ 3, 15 = 3 ∗ 5, y 60 = 22 ∗ 3 ∗ 5. En general cualquer numero npuede ser factorizado como:

n = pf11 ∗ pf1

1 ∗ . . . ∗ pf11

donde pi son numeros primos, y f i el numero de veces que aparecen di-chos numeros. Una vez factorizados ambos numeros tan solo tendrıamos quequedamos con los factores primos comunes, elevados a la mınima potencia. AsıMCD(6, 60) = 2 * 3 = 6. Sin embargo, descomponer un numero en sus fac-tores primos no es una tarea facil, como veremos mas adelante cuando tratemosel tema de la criptografıa.

En lugar de factorizar ambos numeros, vamos a utilizar otro metodo, cono-cido como algoritmo de Euclides, que nos permite calcular el maximo comundivisor de una manera facil, elegante, y rapida. El algoritmo de Euclides se basaen la siguiente propiedad:

si a y b son dos numeros enteros cualesquiera, entonces MCD(a, b)= MCD(a-b, b).

Podrıamos hacer unos cuantos ejemplos a mano para convencernos a nosotrosmismos de que esta propiedad es cierta, y aquellos lectores que sean mas habiles


Figure 1.4: Regla divisora

con las matematicas, podrıan incluso intentar dar una demostracion formal.Pero en realidad no hace falta complicarse tanto la vida. Solo tenemos quepensar un poco que es lo que realmente significa esta propiedad para darnoscuenta de que la idea es trivial (y como toda idea trivial que se precie, tuvieronque pasar muchos anos hasta que alguien se percato de ella).

Imaginemos que tenemos dos barras de acero de longitudes a y b respecti-vamente, y que queremos medirlas utilizando para ello una pequena regla demadera. Si la regla de madera nos da un numero entero de medidas en una delas barras es porque la regla es un divisor de dicha barra. Si despues de medirnos sobra un poquito de barra, es porque la regla no es un divisor. De entretodas las reglas que miden a ambas barras a y b nos quedamos con la que tengauna longitud mayor, que sera precisamente el maximo comun divisor (vease laFigura 1.4).

Ahora bien, si encontramos una regla que divide a la barra b, para ver sitambien divide a la barra a bastarıa con comprobar que divide a aquella partede la barra a que sobresale de la barra b (es decir b-a), ya que la otra parte yaha sido medida. Si ahora cortamos lo que sobresale de la barra a, podrıamosrepetir de nuevo el proceso pero utizando la barra cortada b-a y la barra b. Setratarıa de resolver el mismo problema pero invertidos los papeles de las barras.

Basandonos en esta idea, podemos escribir el siguiente Algoritmo de Euclides(vease el Algoritmo 3). La idea consiste en ir cortando alternativamente de labarra mas larga la parte que sobresale de la barra mas pequena, hasta queambas barras tengan exactamente la misma logitud, que sera el maximo comundivisor.

El algoritmo puede ser mejorado todavıa un poco mas, utilizando para ellola funcion modulo que hemos visto mas arriba, pero esta mejora se la dejopropuesta al lector como ejercicio.

1.4 Ciencia, arte o ingenierıa

Practicamente desde que aparecieron las primeras computadoras electronicas, ycon ellas los primeros programadores, ha habido un debate sobre si la progra-macion de ordenadores es una ciencia, un arte o un proceso de ingenierıa. Elproblema radica en que no existe ningun metodo formal para disenar algorit-mos, es decir, no existe ningun algoritmo que nos permita escribir algoritmos,


Figure 1.5: Interpretacion geometrica del algoritmo de Euclides

Algorithm 3 Algoritmo de Euclidesfuncion MCD Euclides(a, b)mientras a != b hacer

si a < b entoncesa := a - b

sinob := b - a

finsifinmientrasescribir(a)


y por tanto, los programadores han de ingeniarselas con cada nuevo problemaque tienen que resolver. Tan solo disponemos de un conjunto de tecnicas gen-erales y de buenas practicas, que iremos viendo a lo largo de este libro, y quenos pueden servir como base para disenar nuestros propios algoritmos. Peroal final, el disenador de algoritmos ha de basarse mas en su experiencia y suintuicion que en ningun metodo formal.

En la seccion 1.2 mencionamos los premios Turing, que la asociacion ACMconcede cada ano, en honor al matematico Alan Turing, a aquellos investigadoresque hayan destacado por sus contribuciones tecnicas a la comunidad informatica.En el ano 1974 el premio Turing fue concedio al profesor Donald E. Knuth, dela Universidad de Stanford (EEUU), por sus contribuciones en el analisis dealgoritmos y en el diseno de lenguajes de programacion, y en particular por susfamosa serie de libros “El Arte de Programar Ordenadores”.

En 1968 el profesor Knuth publico el primero de una serie de libros conel animo de recopilar todo el conocimiento disponible sobre el “arte” de pro-gramar ordenadores. El primer volumen estaba dedicado a los algoritmos masfundamentales; el segundo volumen, publicado en 1969, trataba de los algorit-mos seminumericos; y el tercer volumen, publicado en 1973, sobre algoritmosde ordenacion y busqueda. El cuarto volumen, aun no publicado, tratara sobrealgoritmos combinatorios, y finalmente, el quinto volumen, que se espera para elano 2010, hablara de los algoritmos sintacticos4. Para hacerse una idea de la im-portancia de la serie de libros publicada por el profesor Knuth, basta mencionarque en el ano 1999, la revista American Scientist, los incluyo en una lista conlas doce mejores monografıas de la ciencia del siglo XX, junto con tıtulos comola relatividad de Einstein, la mecanica cuantica de Dirac, o los fundamentos dela matematica de Russell y Whitehead.

Durante la entrega de la medalla Turing, el profesor Knuth hizo una ardientedefensa de la idea de que la programacion es, ante todo, un arte. El profesornos ensenaba sobre la necesidad de buscar la belleza en la programacion:

Preparar un programa, es como escribir poesıa o componer musica;como Adrei Ershov dijo una vez, la programacion puede darnos satis-faccion emocional e intelectual a la vez, porque es un verdadero logrodominar la complejidad y establecer un sistema de reglas consis-tentes. Ademas, cuando leemos los programas que otros han escrito,podemos reconocer algunos de ellos un genuino trabajo artıstico [...]Algunos programas son elegantes, otros son esquisitos, y otros sonbrillantes. Creo que es posible escribir programas excelentes, pro-gramas nobles, y programas realmente magnıficos.

Finalmente, el profesor Knuth concluye su disertacion diciendo:

“Hemos visto que la programacion de ordenadores es un arte,porque aplica el conocimiento acumulado al mundo, porque requiere

4Aunque quizas el profesor nos sorprenda con dos volumentes mas: volumen 6, sobre lateorıa de los lenguajes libres de contexto, y el volumen 7, sobre tecnicas para compiladores.


habilidad e ingenuidad, y sobre todo porque produce objetos bellos.Un programador que inconscientemente se ve a sı mismo como unartista se divertira con lo que hace, y lo hara mucho mejor.”

Mi opinion personal es que la programacion de ordenadores es una mezcla detodo, de ciencia, de arte y de ingenierıa, y que estas diferentes visiones se com-plementan entre sı. El programador de hoy dıa ha de conocer y manejar cor-rectamente estas tres facetas. Ha de conocer los metodos de ingenierıa de laprogramacion si quiere ser capaz de gestionar la complejidad de los grandesproyectos. Ademas, el programador ha de estar familiarizado con los funda-mentos teoricos y cientıficos de la programacion de ordenadores. Y sobre todo,el programador ha de buscar la belleza de los algoritmos que escribe.

1.5 Algoritmos y lenguajes de programacion

No me gustarıa finalizar este capıtulo si escribir unas palabras sobre los lengua-jes de programacion. Sabemos que para que un ordenador pueda ejecutar unalgoritmo primero tenemos que traducirlo a alguno de los muchos lenguajes deprogramacion de ordenadores que existen. Los ordenadores de hoy en dıa no soncapaces de procesar directamente el lenguaje pseudocodigo que vamos a utilizaren este libro para escribir los algoritmos. El problema es que el pseudocodigoaquı utilizado, aunque es lo suficientemente claro y conciso para los humanos,contiene demasiadas ambiguedades que son insuperables por los ordenadores.De ahı que necesitamos primero traducir nuestro pseudocodigo a algun lenguajede programacion formal antes de poder ver nuestros algoritmos funcionando enun ordenador.

Existen numeros lenguajes de programacion, que se basan a su vez en paradig-mas. Por ejemplo, tenemos la programacion estructurada con los lenguajes Pas-cal y C, la programacion orientada a objetos con Java o C++, la programacionlogica con Prolog, la programacion funcional con LISP, etc. Pero no vamos a en-trar a estudiar los detalles de cada uno de estos paradigmas y lenguajes, porqueesto nos llevarıa demasiado tiempo. Tampoco voy a proporcionar la traducciondel pseudocodigo de los ejemplos a alguno de estos lenguajes de programacion;en primer lugar porque para ello primero tendrıa que elegir uno de lenguajesexistentes (C, Pascal, Java, etc.), y elija el que elija, seguro que el 80% de mislectores se enfadarıa por la eleccion (existen unas terribles guerras de religionen cuanto cual es el mejor lenguaje de programacion que existe); en segundolugar porque pienso que el pseudocodigo que he utilizado en los ejemplos es losuficientemente claro para que los lectores no tengan dificultad para traducirloellos mismos a su lenguaje favorito.

Tan solo hacer una pequena advertencia a los lectores, y es que tengan encuenta que segun que problema queramos resolver, es mejor utilizar un lenguajeque otro. Es decir, que a pesar de que disponemos de lenguajes que por suversatilidad son conocidos como lenguajes de proposito general, algunas cosasson mas faciles de hacer en algunos lenguajes que en otros. Luego no es buenaidea conocer un unico lenguaje.


1.6 Para divertirse mas ...

Existen muchos, y muy buenos, libros sobre algorıtmica y sobre la programacionde ordenadores. En esta seccion solo voy a comentar algunos de ellos, para que ellector los tenga como referencia por si quiere profundizar mas sobre la materia.

Un excelente recopilacion del conocimiento actual sobre los algoritmos es ellibro Introduction to Algorithms, de Thomas H. Cormen et al. (editorial MITPress), pero no tiene traduccion al castellano.

Tambien en ingles, y mucho mas accesible que el anterior, tenemos el li-bro Algorithmics, the Spirit of Computing, de David Harel y Yishai Feldman(editorial Addison Wesley).

De dibulgacion y en castellano podemos encontrar el libro De Euclides aJava, de Ricardo Pena Marı (editorial Nivola).

Importancia del cero

No bromeaba cuando afirmaba que el concepto de cero es una de las ideas masimportantes de la historia de la humanidad. Para saber mas sobre el genesisde la idea de cero, y sobre sus implicaciones, recomiendo la lectura del libro LaBiografıa de una Idea Peligrosa, de Charles Seife (de Ediciones Ellago).

Charles Babage

Charles Babbage sı que intento construir otra maquina mas simple que su In-genio Analıtico, denominada Ingenio de Diferencias, pero desgraciadamente elproyecto acabo en el mas absoluto fracaso. Son muchos los historiadores queopinan que Chales Babagge fue un adelantado a su tiempo, ya que con la tec-nologıa disponible en la epoca Victoriana no era posible construir semejanteartilugio. Sin embargo, la reciente construccion con exito en el Museo de laCiencia de Londres de uno de los ingenios calculadores disenados por Babbageha demostrado que la historia ha juzgado erroneamente al precursor de la com-putacion automatica. Los ingenieros del museo demostraron que las maquinasde Babbage no contenıan errores logicos o de diseno graves, y tecnicamente eranviables para lo que los artesanos del siglo XIX podıan fabricar. El fracaso delproyecto fue debido mas a un problema de gestion del mismo que a problemastecnicos o de concepto.

Para saber mas sobre la computadora mecanica de Charles Babbage re-comiendo la lectura del artıculo de Doron D. Swade en la revista Investigaciony Ciencia (Abril 1993).

En otra lınea esta el libro de Willian Gibson, The Difference Engine, unanovela de ficcion que narra como hubiera sido la evolucion de la humanidad siCharles Babbage hubiese conseguido finalizar su computadora, adelantando elinicio de la era de la informacion un siglo.


Alan Turing

Sobre Alan Turing hay muchos libros escritos. Le recomiendo al lector queademas de leer alguna biografıa de Turing, tambien intente buscar informacionsobre los siguientes apasionantes temas: la maquina universal de Turing, elcodigo enigma y el test de Turing.

Donald Knuth

La trilogıa de libros El Arte de Programar Ordenadores de Donald Knuth, hasido publicada en castellano por la editoriral Reverte.

La disertacion del profesor Knuth durante la recepcion de premio Turingtitulada Computer Programming as an Art fue publicada por la revista Com-munications of the ACM (volumen 17, numero 12, Diciembre de 1974).

Chapter 2

Algunos Ejemplos

Antes de pasar directamente a revisar cuales son las principales tecnicas deresolucion de problemas utilizadas en algorıtmica, vamos a ver unos ejemplosde algoritmos, con la idea de allanar el camino y familizarizarnos con el tema.

2.1 Complejidad Algorıtmica

Como hemos visto, los algoritmos juegan un papel muy importante en el mundode la informatica. Resulta de vital importancia contar con buenos algoritmos,que soluciones los problemas de manera rapida, y que a la vez consuman pocosrecursos, como memoria. Piensese por ejemplo en el caso de los buscadores de in-formacion en internet, aquel buscador que posea el mejor algoritmo de busqueda,que sea capaz de proporcionar informacion relevante para el usuario, sera el queconsiga mayor cuota de mercado (un mercado muy lucrativo, por cierto). Opor ejemplo en el area de la seguridad informatica y la criptografıa, donde esfundamental contar con algoritmos de encriptacion que sean indescifrables, almenos desde un punto de vista practico. O en el caso de las bases de datos, tancomunes en bancos, departamentos de contabilidad, administraciones y muchosotros lugares, donde es necesario contar con algoritmos de busqueda que nosproporcionen la informacion que necesitamos en un tiempo razonable. La al-gorıtmica es la rama de la informatica encargada de buscar y analizar algoritmoseficientes que solucionen problemas comunes (que entendemos por algoritmo efi-ciente es algo que veremos en detalle mas adelante).

Ejemplos con algoritmos de ordenacion2.- Complejidad AlgorıtmicaAntes de empezar a estudiar las diferentes tecnicas de solucion de proble-

mas, deberıamos hacer una pequena revision de las herramientas matematicasque nos permiten estudiar los diferentes algoritmos. Primero, revisaremos lasdefiniciones y terminos matematicos que vamos a usar en el resto del libro. Aldisponer de este vocabulario matematico podremos ser mas precisos y formularlos problemas de manera mas facil. Despues, revisaremos las tecnicas existentes

17

CHAPTER 2. ALGUNOS EJEMPLOS 18

para analizar el tiempo de ejecucion de un algoritmo. En el resto del libro, de-spues de cada algoritmo proporcionaremos un analisis de su tiempo de ejecuciony una prueba de su correcteness.

Notacion AsintoticaDenotamos porel conjunto de los numeros naturales (tales como 1, 2, 3,

etcetera). En complejidad algorıtmica estamos interesados en funciones de Nen N, tales como n2, 2n y n3-2n+5.

Decimos que un algoritmo es O(g(n)), pronunciado orden de g(n), si f crececomo g o mas lento.

Analyzing an algorithm has come to mean predicting the resources thatthe algoritm requires. Occasionally, resource such as memory, communicationsbandwidth, or computer hardware are of primary concern, but most often it iscomputational time that we want to measure. Generally, by analyzing severalcandidate algorithms for a problem, a most efficient one can be easily identified.Such analysis may indicate more than one viable candidate, but several infe-rior algorithms are usually discarded in the process. Asymptotic Notation Inaddition to correctness another important characteristic of a useful algorithmis its time and memory consumption. Time and memory are both valuableresources and there are important differences (even when both are abundant)in how we can use them. How can you measure resource consumption? Oneway is to create a function that describes the usage in terms of some charac-teristic of the input. One commonly used characteristic of an input dataset isthe its size. For example, suppose an algorithm takes as input an array of nintegers. We can describe the time this algorithm takes as a function f writtenin terms of n. For example, we might write: f(n) = n2 + 3n + 14 where thevalue of f(n) is some unit of time (in this discussion the main focus will beon time, but we could do the same for memory consumption). Rarely are theunits of time actually in seconds, because that would depend on the machineitself, the system its running, and its load. Instead, the units of time typicallyused are in terms of the number of some fundamental operation performed. Forexample, some fundamental operations we might care about are: the numberof additions or multiplications needed; the number of element comparisons; thenumber of memory-location swaps performed; or the raw number of machineinstructions executed. In general we might just refer to these fundamental op-erations performed as steps taken. Is this a good approach to determine analgorithm’s resource consumption? Yes and no. When two different algorithmsare similar in time consumption a precise function might help to determinewhich algorithm is faster under given conditions. But in many cases it is eitherdifficult or impossible to calculate an analytical description of the exact numberof operations needed, especially when the algorithm performs operations con-ditionally on the values of its input. Instead, what really is important is notthe precise time required to complete the function, but rather the degree thatresource consumption changes depending on its inputs. Concretely, considerthese two functions, representing the computation time required for each size ofinput dataset: f(n) = n3 - 12n2 + 20n + 110 g(n) = n3 + n2 + 5n + 5 Theylook quite different, but how do they behave? Let’s look at a few plots of the


function (f(n) is in red, g(n) in blue):Plot of f and g, in range 0 to 5Plot of f and g, in range 0 to 15Plot of f and g, in range 0 to 100Plot of f and g, in range 0 to 1000In the first, very-limited plot the curves appear somewhat different. In the

second plot they start going in sort of the same way, in the third there is onlya very small difference, and at last they are virtually identical. In fact, theyapproach n3, the dominant term. As n gets larger, the other terms become muchless significant in comparison to n3. As you can see, modifying a polynomial-time algorithm’s low-order coefficients doesn’t help much. What really mattersis the highest-order coefficient. This is why we’ve adopted a notation for thiskind of analysis. We say that: f(n) = n3 - 12n2 + 20n + 110 = O(n3) Weignore the low-order terms. We can say that: This gives us a way to moreeasily compare algorithms with each other. Running an insertion sort on nelements takes steps on the order of O(n2). Merge sort sorts in O(nlogn) steps.Therefore, once the input dataset is large enough, merge sort is faster thaninsertion sort. In general, we write f(n) = O(g(n)) That is, f(n) = O(g(n)) holdsif and only if there exists some constants c and n0 such that for all n > n0 f(n)is positive and less than or equal to cg(n). Note that the equal sign used in thisnotation describes a relationship between f(n) and g(n) instead of reflecting atrue equality. In light of this, some define Big-O in terms of a set, stating that:when Big-O notation is only an upper bound; both these two are both true: n3= O(n4) n4 = O(n4) If we use the equal sign as an equality we can get verystrange results, such as: n3 = n4 which is obviously nonsense. This is why theset-definition is handy. You can avoid these things by thinking of the equal signas a one-way equality, i.e: n3 = O(n4) does not imply O(n4) = n3 Always keepthe O on the right hand side. Big Omega Sometimes, we want more than anupper bound on the behavior of a certain function. Big Omega provides a lowerbound. In general, we say that f(n) = ?(g(n)) when I.e. f(n) = O(g(n)) if andonly if there exist constants c and n0 such that for all n>n0 f(n) is positive andgreater than or equal to cg(n). So, for example, we can say that n2 - 2n = ?(n2)- (c=1/2, n0=4) or n2 - 2n = ?(n) - (c=1, n0=3), but it is false to claim thatn2 - 2n = ?(n3).

Big Theta When a given function is both O(g(n)) and ?(g(n)), we say it is?(g(n)), and we have a tight bound on the function.

From Papa It is importan, however, to identify the source of our satisfac-tion: It is the rate of growth O(n2). In the course of this book we shall regardsuch polynomial rates of growth as acceptable time requirements, as a sign thatthe problem has been solved statisfactorily. In contrast, exponential rates suchas 2ˆn, even worse, n! Will be a cause of concern. If they persists, and algo-rithm after algorithm we devise fails to solve the problem in polynomial time,we generally consider this as evidence that the problem in hand is perhapsintractable, not amenable to a proactically efficient solution. This dichotomybetween polynomial and nonpolynomial time bounds, and the identificationof polynomial algorithms with the intuitive notion of practically feasible com-


putation, is not uncontroversial. There are efficient computation that are otpolynomial, and polynomial computations that are not efficent in practice. [Infact, there is an important problem that provides examples for both kind ofexceptions: Linear programming. A widely used classical algorithm for thisbasic problem, the simplex method, is know to be exponential in the worstcase, but has consistently superb performance in practice; in fact, its expectedperformace is probably polynomial. In contrast, the first polynomial algorithmdiscovered for this problem, the ellipsoid algorithm, appears to be impracticallyslow. But the storiy of linear programming may in fact be a subtle argumentfor, not against, the methodology of complexity theory: It seems to indicatethat problems that have practical algorithms are indeed polynomial-time solv-able althogh the polynomial-time algorithm and the empirically good one maynot necessarily coincide.] For example, an nˆ80 algorithm would probably be oflimited practical value, and an algorithm with an exponential growth rate suchas 2ˆ(n/100) (or, more intriguing, a subexponential one such as nˆ(log n) ) maybe far more useful. There are, however, strong arguments in favor of the poly-nomial paradigm. First, it is a fact that any polynomial rate will be overcomeeventually by any exponetial one, and so the latter is to be preferred for all buta finite set of instances of the problem but of course this finite set may containall instances that are likely to come up in practice, or that can exist within theconfines of our universe ... More to the point, experience with algorithms hasshown that exrem rate of growth, such as nˆ80 and 2ˆ(n/100), rarely come upin practice. Polynomial algorithms typically have small exponents and reason-able multiplicative constans, and exponential algorithms are usually impracticalindeed. Another potential criticism of our point of view is that it only examineshow the algorithm performs in the least favorable situations. The exponentialworst-case performance of an algorithm may be due to a statistically insignifi-cant furaction of the inputs, although the algorithm may perform satisfactorilyon the average. Surely an analysis of the expected, as opposed to the worst-case,behavior of an algorithm would be more informative. Unfortunately, in practicewe rarely know the input distribution of a problem that is, the probability withwhich each possible instance is likely to occur as an input to our algorithm andthus a truly informative average-case analysis is impossible. Besides, if we wishto solve just one particular instanc, and our algorithm prforms abysmally onit, knowing that w have stumbld upon a statistically insignificant exception isof litle help or consollation. It should not com as a surpris that our choic ofpolynomial algorithms as the mathmatical concpt that is supposd to capturethe informal notion of practically fficient computation is open to criticism forall sides. Any attempt, in any field of mathematics, to capture an intuiive, real-life notion by a mathematical concept is bound to include certain undesirablespcecimens, while excluding others that arguable should be embraced. Ulti-mately, our argument of choice must be this: Adopting polynomial worst-caseperformance as our criterion of effciency results in an elegant and useful theorythat says something meaningfull about practical computation, and whould beimpossible without this simplification.

Hablar tambien de los requerimientos de espacio.


Past experience in the field seems to suggest that, as a rule, once a polyno-mial algorithm for a problem has been developed, the time requirements undergoa series of improvements that bring the probme in the real of realistic compu-tation. The important step is to break the barrier of exponentiality to comeup with the first polynomial time algorithm. A central concep in algorithmsis that of a reduction. A reduction is an algorithm that solves problem A bytransforming any instance of A to an equivalent instance of a previously solvedproblem B.

2.2 ¿Esta usted seguro?

Una de los principales problemas de la algorıtmica es como estar seguros de queun algoritmo es correcto. Es decir, como sabemos que un algoritmo va a dar larespuesta correcta a los parametros de entrada proporcionados.

Chapter 3

Recursividad

Metodos Iterativos y Metodos Recursivos. Calculo de n! Series de Fibonacci.

22

Chapter 4

Divide y Venceras

Si el presidente de mi paıs me llamase por telefono para pedirme consejo so-bre como conquistar algun paıs vecino, seguramente lo que le recomendarıa esque tratase de dividir el ejercito de nuestro rival, es decir, que aplicase la viejaestrategia de Divide y Venceras. La maxima divide y venceras (del latin Di-vide et Impera) es atribuida a Maquiavelo, aunque es una tactica que se vieneutilizando desde muy antiguo. Por ejemplo, es de sobra conocido que el Cesarseguramente la tenıa en la mente cuando, uno por uno, ya sea en el campo debatalla o por medios diplomaticos, consiguio que los jefes locales aceptaran laautoridad de Roma. La estrategia divide y venceras tambien ha sido utilizadacon gran acierto por los administradores de los grandes imperios, incluyendo elimperio britanico, el cual jugaba a enfrentar una tribu contra otra para man-tener el control de sus colonias con un numero mınimo de fuerzas. El conceptode “divide y venceras” gano especial relevancia cuando la India entro a formarparte del imperio britanico. Los britanicos utilizaron esta estrategia de man-era efectiva para ganar control de un territorio muy extenso como es la Indiamanteniendo su gente dividida con la religion, el idioma, las castas, etc. Losbritanicos tomaron el control de pequenos estados principescos hindues en lugarde unir Inida en una unica nacion.

En polıtica y sociologıa, el metodo divide y venceras es una estrategia desobra conocida para ganar y mantener el poder mediante la division de grandesconcentraciones de poder en grupos que individualmente tienen menos poderque el que aplica la estrategia. Aunque en realidad, a menudo se refiere a unaestrategia donde los pequenos grupos de poder se previene que se enlacen yse conviertan en mas poderosos, dado que es mas dificil romper estructuras depoder ya existentes.

Pero volvamos a los algoritmos, que es lo que en realidad nos interesa, yveamos como podemos aplicar la estrategia divide y venceras para resolver mu-chos problemas. Muchos algoritmos utiles son recursivos en estructura: pararesolver un problema, se llaman a sı mismos recursivamente una o mas ve-ces para tratar con subproblemas relacionados. Estos algoritmos tıpicamentesiguen un metodo divide-y-venceras: parten el problema en subproblemas que

23

CHAPTER 4. DIVIDE Y VENCERAS 24

son similares al problema original pero mas pequenos en tamao, y resuelven elproblema de manera recursiva, y despues combinan estas soluciones para crearuna solucion al problema original.

El paradigma de resolucion de problemas divide y venceras involucra tespasos a cada nivel de la recursion:

• Divide el problema en un numero de subproblemas.

• Conquista cada subproblema resolviendolo de manera recursiva. Si eltamano de los subproblemas es lo suficientemente pequeno, sin embargo,tan solo soluciona los problema de una manera directa.

• Combina la solucion de los subproblemas en la solucion del problema orig-inal.

4.1 Merge Sort

4.2 Multiplicacion?

Multiplicacion divide y venceras

4.3 La Transformada de Fourier

Chapter 5

Fuerza Bruta

Una tecnica de resolucion de problemas para la que los ordenadores estan espe-cialmente bien dotados es la conocida como fuerza bruta. Basicamente la ideacosiste en dado un problema, intentar de manera sistematica todas las solucionesposibles hasta dar con la solucion buscada. Un ejemplo de algoritmo basado enfuerza bruta lo vimos en la seccion 1.3 al calcular el maximo comun divisor dedos numeros naturales a y b, para ello enumerabamos todos los enteros desde1 hasta el mınimo de a y b, y comprobabamos si dividıan a ambos numeros ala vez. La fuerza bruta es un metodo de resolucion de problemas muy ingenuo,y que apriori puede parecernos que no deberıa tener mucho exito. El princi-pal inconveniente que tiene es su coste computacional, que es proporcional alnumero de soluciones candidatas a examinar, y que en el caso de muchos prob-lemas practicos, tiende a crecer de manera muy rapida cuando el tamano delproblema se incrementa. Sin embargo, si tenemos en cuenta la fantastica habil-idad de calculo de los ordenadores de hoy dıa, capaces de realizar millones deoperaciones por segundo, entenderemos que para el caso de aquellos problemasen los que no se conoce una solucion mejor, la fuerza bruta puede ser una buenaalternativa. Ademas, la fuerza bruta tambien se suele aplicar en aquellos proble-mas cuyo tamano esta limitado, o cuando existen tecnicas heurısticas especıfcasdel problema que pueden ser utilizadas para reducir el conjunto de solucionescandidatas a examinar a un tamano razonable.

5.1 El problema de la mochila

El problema de la mochila.

5.2 Maquinas que juegan al ajedrez

Seguramente muchos de los lectores saben jugar al ajedrez, y son conscientes delo complicado que resulta dominar el juego. Aunque en realidad, si uno lo piensaun poco, no se trata de un juego tan difıcil. Las reglas pueden aprenderse en

25

CHAPTER 5. FUERZA BRUTA 26

varios minutos de practica; y la estrategia a seguir es muy clara: en cada posicionhacer aquella jugada que maximice las posibilidades de que ganemos y minimicelas posibilidades de que gane nuestro rival. Para ello lo unico que tenemos quehacer es revisar todos los movimientos posibles a nuestro alcance, y para cadauno de ellos todas las posibles respuestas del bando contrario, y para cada unade las posibles respuestas miramos todas nuestras posibles respuestas, y asısucesivamente hasta completar unas diez o doce jugadas por adelantado. Estatecnica de juego, basada en la fuerza bruta, deberıa garantizarnos la victoria.

La pregunta es: ¿cuantas posiciones tendrıamos que analizar? Al empezar lapartida, las blancas tienen a su disposicion un total de 20 movimientos distintos,podemos adelantar cada uno de los peones una o dos casillas, junto con los cuatromovimientos posibles de los caballos. Para cada uno de los 20 movimientos delas blancas, las negras pueden a su vez responder con otros 20 movimientos, loque hace un total de 400 diferentes posiciones posibles. En la siguiente jugada,las blancas pueden optar entre 5362 posiciones diferentes, y las negras, en surespuesta por 71842. En la tercera jugada ya hablamos de mas de 800.000posiciones para las blancas, y mas de 9 millones para las negras. Se estima queun Gran Maestro de ajedrez puede examinar y evaluar del orden de 3 posicionespor segundo, y por tanto, calcular y evaluar todas las posibles posiciones paralos tres primeros movimientos del juego, requerirıa nada menos que 100 dıas.

Evidentemente, a pesar de ser una estrategia correcta desde un punto de vistateorico, desde un punto de vista practico resulta totalmente irrealizable, y de ahıque los humanos tengamos que utilizar estrategias alternativas. Basicamente loque hacemos cuando jugamos es descartar la mayorıa de las posibles jugadas,utilizando para ello nuestro conocimiento del juego. Un Gran Maestro del aje-drez no suele considerar mas de 3 o 4 posibles alternativas en cada posicion. Sinembargo, los ordenadores son maquinas de calcular por excelencia, y quizas estaestrategia para jugar al ajedrez puede que este dentro de sus posibilidades decalculo. Por ejemplo, la maquina Deep Blue disenada por IBM en 1997 para ju-gar contra el campeon del Mundo Garry Kasparov, podıa examinar y evaluar delorden de 200 millones de posiciones por segundo. Esta maquina tardarıa menosde un segundo en evaluar las tres primeros movimientos del juego. ¿Es la fuerzabruta una tecnica viable para jugar al ajedrez? A esta pregunta intentaremosresponder en esta seccion.

5.2.1 Arboles de Juego

Los principales programas de ajedrez funcionan median la busqueda de un arbolde movimientos y contramovimientos. El programa empieza con la posicion ac-tual y genera todos los movimientos, todas las respuestas legales a esos movimien-tos, y ası sucesivamente hasta que una profundidad fijada es alcanzada. A cadanodo hoja, se aplica una funcion de evaluacion la cual le asigna un valor numericoa cada posicion. Estas puntuaciones son retroasignada mediante un proceso lla-mado minimax, el cual simplemente asume que cada bando escogera aquellalına de juego que le es mas favorable en cada momento. Si un valor positivoes bueno para las blancas, simplemente escogemos aquel movimiento con mayor


valor, y las negras escogeran aquella jugada con menor valor. Estos conceptosestan ilustrados en la Figura ?.

La funcion de evaluacion empleada es simplemente una combinacion de equi-librio de material y varios otros terminos que representan factores posicionales.Los terminos posicionales son pequenas cantidades pero son importantes dadoque el equilibrio de material rararmente cambia en el juego del ajedrez en tor-neos.

El problema de este metodo basado en la fuerza bruta es que el tamanodel arbol explota combinacionalmente. El “factor de ramificacion” o numerode movimientos legales posibles en una posicion tıpica des de 35. Para poderjuegar a nivel de maestro de ajedrez es necesario utilizar una profundidad de 8jugadas, lo que implica un arbol de 35**8 nodos finales.

Fortunately, there is a better way. Alpha-beta pruning is a technique whichalways gives the same answer as brute-force searching without looking at somany nodes of the tree. Intuitively, alpha-beta pruning works by ignoring sub-trees which it knows cannot be reached by best play (on the part of both sides).This reduces the effective branching factor from 35 to about 6, which makesstrong play possible.

The idea of alpha-beta pruning is illustrated in Figure 14.4. Assume that allchild nodes are searched in the order of left to right in the figure. On the left sideof the tree (the first subtree searched), we have minimaxed and found a score of+4 at depth one. Now, start to analyze the next subtree. The children reportback scores of +5, -1, . The pruning happens after the score of -1 is returned:since we are taking the minimum of the scores +5, -1, , we immediately havea bound on the scores of this subtree-we know the score will be no larger than-1. Since we are taking the maximum at the next level up (the root of the tree)and we already have a line of play better than -1 (namely, the +4 subtree), weneed not explore this second subtree any further. Pruning occurs, as denotedby the dashed branch of the second subtree. The process continues through therest of the subtrees.

The amount of work saved in this small tree was insignificant but alpha-beta becomes very important for large trees. From the nature of the pruningmethod, one sees that the tree is not evolved evenly downward. Instead, thealgorithm pursues one branch all the way to the bottom, gets a “score to beat”(the alpha-beta bounds), and then sweeps across the tree sideways. How wellthe pruning works depends crucially on move ordering. If the best line of playis searched first, then all other branches will prune rapidly.

Actually, what we have discussed so far is not full alpha-beta pruning, butmerely “pruning without deep cutoffs.” Full alpha-beta pruning shows up onlyin trees of depth four or greater. A thorough discussion of alpha-beta with someinteresting historical comments can be found in Knuth and Moore [Knuth:75a].


5.2.2 Evaluacion de Posiciones

5.2.3 El Juego del Go

El juego del Go es de una naturaleza diferente al del Ajedrez.

5.3 El Viajante

Vamos a ver ahora un problema clasico en la teorıa de algoritmos, que ha sidocon diferencia, el problema mas difıcil de resolver, y por ahora, el mayor de losfracasos. Ademas, este problema ha supuesto una de las principales motiva-ciones para el desarrollo de la teorıa de la complejidad computacional.

Descripcion del problema .... y su version equivalente como problema dedecision

Evidentemente, el problema puede ser resuelto mediante la enumeracion detodas las posibles soluciones, calculando el coste de cada una, y seleccionandola mejor entre ellas. Este procedimiento requerirıa un tiempo proporcional a n!(existen 1

2 (n-1)! Rutas a considerar), que no es un tiempo polinomial. Noteseque este algoritmo se comporta muy bien en cuanto a requerimientos de espacio:solo require un espacio proporcional a n, ya que solo necesitamos recordar la per-mutacion que estamos analizando en este momento, y la mejor ruta encontradahasta el momento.

No se conoce ninguna solucion al problema del viajante en tiempo poli-nomial. Podemos mejorar el n! Tiempo un poco mediante el metodo de laprogramacion dinamica (aunque a costa de utilizar unos requerimientos de es-pacio exponenciales). Existen algoritmos eurısticos que se comportan bien, yencuentran rutas que no estan lejos de la ruta optima cuando se le proporcio-nan instancias tıpicas. Pero, si insistimos en algoritmos que garanticen el valoroptimo, el estado del arte solo ofrece respuestas exponenciales. Y esto no esdebido a una falta de interes, ya que el problema del viajante es probablementeuno de los algoritmos que mas se han estudiado.

Nos sentimos tentados a suponer que hay un impedimento fundamental,un lınea divisoria dramatica entre el problema del viajante y otros problemassimilares. Podrıamos suponer que no hay solucion en tiempo polinomico parael problema del viajante. Esta afirmacion es una de las muchas maneras deformular la famosa afirmacion de P != NP, el mas importante de los problemasen informatica teorica.

Decir algo sobre los problemas del milenio y la fundacion Clay

5.4 Criptografıa

brute-force attack


5.5 Para divertirse mas

Existen dos tipos de problemas relacionados con el ajedrez1.- Cuantas piezas de un tipo dado pueden colocarse en un mismo tablero

sin que se ataquen? Problema de las 8 reinas.2.- ¿Cual es el mınimo numero de piezas necesarias para ocupar o atacar

cada cuadrado del tablero?3.- El problema de la vuelta del caballo

Chapter 6

Metodos Aleatorios

Calculo de Pi.

30

Chapter 7

Otros Metodos

Programacion Dinamica: Fibonacci Greedy Algorithms Hill Climbing: Networkflow (mapa de carreteras?)

31

Chapter 8

Algunos Problemas Clasicos

Torres de Hanoi

32

Chapter 9

Programacion Concurrente

Los Filosofos Comensales

33

Chapter 10

Imitando a la Naturaleza

Metodos aleatorios? Aloritmos Geneticos. Redes Neuronales. Hormigas. Enfri-amiento Estadıstico

34

Chapter 11

Epılogo

11.1 Algoritmos y patentes

Patentabilidad de los algoritmos

35

Chapter 12

Apendice 1: Introduccion ala Programacion

Introduccion a la programacionOperador de asignacion :=

Sentencias Condicionales

si condicion entoncessentencias

finsi

Operadores relacionales<, >, =, <=, >=, !=Operadorres logicos&|!

Bucles

mientrasfinmientraspara inicializacion hasta finalizacion hacer

sentencias

finpara

Funciones

36

Chapter 13

Apendice 3: Solucion a losEjercicios

37

Chapter 14

Notas

Notas varias

Tecnicas de resolucion de problemas

Listado de tecnicas de resolucion de problemas existentes, y secciones en las queson cubiertas:

recursividadfuerza brutadivide y vencerasbacktrakinggreedy algorithmsprogramacion dinamicaprogramacion lineal

El Arte de Programar

Un poco de historiaSe podrıa extender un poco mas el tema de la multiplicacion de numeros

romanos, y hablar del algoritmo que tenıan los romanos para ello.Hablar de Granada (una de las seis universidades en las que he estudiado) de

aquello de que quien divide por cero en Junio dividira por cero en Septiembre.De que debe haber algo fundamentalmente erroneo en la idea de cero. Ver alguntruquito de cosas raras que pasan cuando uno divide por cero. ¿Hablar de losproblemas que tienen los ordenadores para dividir por cero?

Pseudocodigo UtilizadoPendiente: Estudiar similitud con Logo.para i de 1 hasta 100 repetir fin parasi condicion entonces sino fin simientras condicion repetir fin mientrasleer variableescribir variable | texto

38

CHAPTER 14. NOTAS 39

(wikipedia algorithms)For a solvable problem, there are four different levels an algorithmic solution

to the problem could be done: 1.the obvious way; 2.the methodical way; 3.theclever way; and 4.the miraculous way. On the first and most basic level, the”obvious” solution might try to exhaustively search for the answer. Intuitively,the obvious solution is the one that comes easily if you’re familiar with a pro-gramming language and the basic problem solving techniques. The second levelis the methodical level and is the heart of this book: after understanding thematerial presented here you should be able to methodically turn most obviousalgorithms into better performing algorithms. The third level, the clever level,requires more understanding of the elements involved in the problem and theirproperties or even a reformulation of the algorithm (e.g., numerical algorithmsexploit mathematical properties that are not obvious). A clever algorithm maybe hard to understand by being non-obvious that it is correct, or it may behard to understand that it actually runs faster than what it would seem to re-quire. The fourth and final level of an algorithmic solution is the miraculouslevel: this is reserved for the rare cases where a breakthrough results in a highlynon-intuitive solution. Naturally, all of these four levels are relative, and someclever algorithms are covered in this book as well, in addition to the methodicaltechniques.

Maquinas de TuringThe Turing machine is a formal method for expressing arbitrary algorithms.

• Serıa interesante comentar algo sobre la universalidad de los algoritmos.Es decir, que no necesitamos necesariamente un ordenador para poderimplementarlos, quizas nos baste con unas cajas de cerillas y unas bolitas,una mesa de billar, o unos clavos y unas gomas elasticas. Quizas en elapartado en el que se hable de maquinas de Turing.

• Cita: “homines dum docent discunt” que significa “la gente aprende cuandoensena” (Seneca, Epistulae Morales, 7.8).

14.1 Otros Posibles Temas

Temas de los que se podrıa hablar en el libro:

• Criptografıa

• El cubo de Rubik

• Maquinas de Turing

• Torres Quevedo

• Laberintos: Altoritmos para escapar de un laberinto. Laberintos conexos.Mitologıa.

• Los top 10 de los algorithmos

CHAPTER 14. NOTAS 40

• Morphogenesis

• numerical recipes

• Dijkstraa

14.2 Ejemplos

• numeros perfectos

• cuadrados magico

14.3 A Investigar

• Ariadne’s thread

Chapter 15

Bibliografıa

BibliografıaLibrosAlgorithmics: The Spirit of Computing David Harel Addison-Wesley, Read-

ing, Mass., 1987A History of Algorithms: From the Pebble to the Microchip E. Barbin et al.

SpringerWikibook?Turing OmnibusThe Art of Computer Programming Donald KnuthIntroduction to Algorithms Thomas H. Cormen et al MIT Press and McGraw

HillThe Design and Analysis of Computer Algorithms Alfred V. Aho Addison-

WesleyAlgorithms Robert Sedgewick Addison-WesleyAlgorithms + Data Structures = Programs Niklaus Wirth Prentice HallAlgoritmos de ordenacionhttp://www.algoritmia.net/articles.php?id=31 http://dir.yahoo.com/Science/Computer Science/Algorithms/Sorting Algorithms/Backtrackinghttp://www.algoritmia.net/articles.php?id=33Divide y Vencerashttp://www.algoritmia.net/articles.php?id=34Bibliografıa RecomendadaRevisar textoEn este apartado ...Ademas de las referencias bibliograficas escritas, tambien se ha incluido un

numeroso conjunto de referencias a documentos en internet. Sin embargo, dadala volatilidad de los contenidos en internet, donde documentos aparecen y desa-parecen, y las direcciones cambian, las referencias no son del todo fiables. Paraintentar solucionar este problema, junto a las direcciones en internet o URL,se ha incluıdo suficiente informacion para que, con la ayuda de un buscador eninternet, el lector pueda buscar la nueva localizacion del documento.

41

CHAPTER 15. BIBLIOGRAFIA 42

Capıtulo 1.- El Arte de ProgramarThe MacTutor History of Mathematics archiveCreated by John J O’Connor and Edmund F Robertsonhttp://www-history.mcs.st-andrews.ac.uk/ School of Mathematics and Statis-

tics University of St Andrews ScotlandEn castellano la wikipedia.Edicion impresa:Euclides Elementos (3 volumenes) Biblioteca Clasica Gredos Editorial Gre-

dosEdicion en Internet, en ingles con comentarios y programas de muestra:D. E. Joyce Dept. Math. & Comp. Sci. Clark University http://aleph0.clarku.edu/˜djoyce/java/elements/elements.htmlTraducida al castellano por Jaume Domenech Larraz en http://www.euclides.org/

rafael angel garc´ıa leiva´ july 9, 2006 filechapter 1 el arte de programar la mayor´ıa de las...

Documents