Page 11 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Sección i

Complejidad algorítmica

En la medida en que se refiere a la realidad, las proposiciones

de las matemáticas no son seguras, y viceversa, en la medida en

que son seguras, no se refieren a la realidad.
Albert Einstein

INtroduccIóN

Dos ideas cambiaron el mundo. En 1448, en la ciudad de Mainz, un orfebre llamado Johann Guten-
berg descubrió el camino para imprimir libros colocando juntas dos piezas metálicas móviles. En ese
momento se inició la disipación de la edad obscura, lo cual sirvió para liberar al intelecto humano.
En otras palabras, la ciencia y la tecnología triunfaron y estimularon la fermentación de una semilla
que culminó con la revolución industrial. Por eso, entre muchos historiadores persiste la idea de que
todos esos cambios se lo debemos a la tipografía, pues antes de ella solo una élite podía tener ac-
ceso al conocimiento bibliográfico. Otros historiadores, sin embargo, consideran que la llave de ese
desarrollo no lo produjo la tipografía, sino la algorítmica.

En nuestros días estamos acostumbrados a escribir números en notación decimal, de ahí que sea
sencillo olvidar que Gutenberg utilizaba la notación romana para escribir, por ejemplo, el número
1448 (es decir, MCDXLVIII). Pero, en esa época, ¿cómo se podían sumar dos números romanos?
Para cantidades pequeñas se solían emplear los dedos de las manos, pero para cifras más comple-
jas se debía utilizar el ábaco.

El sistema decimal —inventado en la India alrededor del año 600 a. C.— produjo una revolución en
el razonamiento cualitativo, pues únicamente usando diez símbolos se podían representar números
de gran tamaño sin ninguna complicación. De este modo, cualquier operación aritmética se podía
concretar de forma sencilla. No obstante, estas ideas tardaron bastante en expandirse debido a
las tradiciones, la distancia y las barreras del lenguaje. De hecho, solo fue hasta el siglo noveno de
nuestra era, aproximadamente, cuando Al Khwarizmi —un matemático, astrónomo y geógrafo per-
sa— dio a conocer los métodos básicos para la suma, la resta, la multiplicación, la división e incluso
para determinar la raíz cuadrada y el cálculo de . Sus procedimientos fueron precisos, eficientes y
correctos, y se les llamó algoritmos, un término acuñado en honor al hombre sabio.

5