Estructuras de Datos y Algoritmos (EDA)

“Last year, a group of us were lucky enough to visit the U.K. Prime Minister’s residence at 10 Downing Street, as part of the Silicon Valley Comes to the U.K. initiative. While there, we asked about some of the paintings on the wall. When we got to a large portrait of a regally dressed woman, our host said “and of course, that’s Lady Lovelace.” So much of world history leaves out or minimizes the contributions of women, and so “of course” most of us had no idea who she was. You can imagine our surprise when we learned she was considered by some to be the world’s first computer programmer—having published the first algorithm intended for use on Charles Babbage’s Analytical Engine…”

[Seguir leyendo]

Leonardo de Pisa, Leonardo Pisano o Leonardo Bigollo (c. 1170 – 1250), también llamado Fibonacci, fue un matemático italiano, famoso por haber difundido en Europa el sistema de numeración indo-arábigo actualmente utilizado, el que emplea notación posicional (de base 10, o decimal) y un dígito de valor nulo: el cero; y por idear la sucesión de Fibonacci. [leer más…]

En cuanto a la razón áurea…

Por si os perdisteis la presentación de la Escuela (EINA) en el curso pasado, os incluimos aquí la presentación de este curso (se recomienda: hacer clic 1º en la flecha negra, luego seleccionar “fullscreen” en el menú “more”, y finalmente ir avanzando haciendo clic con el ratón sobre la flecha de avance).

La historia de los lenguajes de programación de alto nivel se extiende ya por más de medio siglo. En la siguiente imagen se incluyen algunos de los más representativos en el periodo 1954-2004, en los paradigmas imperativo, modular, objetual, funcional y lógico.

Los 50 primeros años de los lenguajes de programación (haz clic para verlo en grande en un fichero PDF)

En el año 2012 se cumple el centenario del nacimiento de Alan Turing; matemático, científico de la computación, criptógrafo y filósofo inglés, se le considera uno de los precursores de la Informática.

Información:

• En Wikipedia.
• Sitio web sobre Alan Turing administrado por Andrew Hodges, autor de la biografía “Alan Turing: The Enigma”.
• Sitio web “The Turing Digital Archive”.
• Sitio web del centenario.

El problema de las ocho reinas ha recibido mucha atención en el último siglo. Aquí tenéis un resumen de trabajos sobre el problema. Aquí está la solución habitual de backtracking. Aquí un ejemplo de solución de dividir para vencer. Aquí un ejemplo de solución de búsqueda paralela. Aquí un applet para visualizar el problema, y aquí otro applet.

La Algoritmia persigue continuamente soluciones mejores para problemas conocidos. Uno de ellos es la multiplicación de matrices.

• El algoritmo estándar (basado en la aplicación directa de la definición del producto de matrices) requiere O(N³) operaciones aritméticas (sumas y multiplicaciones), para multiplicar matrices N x N.
• Es muy sencillo reducir ese coste a O(N^2,807), con un algoritmo de “divide y vencerás”, el algoritmo de Strassen (véase wikipedia o transparencias de “divide y vencerás” de la asignatura de Esquemas Algorítmicos).
• Durante veinte años, el algoritmo conocido con menor coste asintótico ha sido el de Coppersmith y Winograd, que requiere O(N^2,376).
• El año pasado, en su tesis doctoral, Andy Stothers propuso un algoritmo con coste asintótico O(N^2,374).
• Justamente ayer Virginia Vassilevska Williams dio a conocer la solución más rápida conocida hasta el momento, con un coste O(N^2,373).

El Premio Fundación BBVA Fronteras del Conocimiento en la categoría de Tecnologías de la Información y la Comunicación ha sido concedido en su tercera edición al científico estadounidense Donald E. Knuth, por “hacer de la programación informática una ciencia introduciendo técnicas matemáticas para el análisis riguroso de los algoritmos”, señala el acta del jurado. Además, el galardonado ha promovido “la escritura de un código sencillo, compacto y comprensible de forma intuitiva”.

La noticia completa puede leerse en la web de la Fundación BBVA.

La implementación habitual (vista en clase) de un montículo es estática, es decir, basada en almacenar el árbol en un vector, por niveles, desde la raíz hacia abajo y de izquierda a derecha para cada nivel.

Lógicamente, esa implementación plantea el típico problema (en representaciones estáticas) de saturación cuando la capacidad del vector se completa.

Hay una solución para ese problema. Se basa en tener un vector de punteros a vectores de datos en el que inicialmente sólo se usa el primer puntero a vector, y apunta a un montículo almacenado como el visto en clase (en el vector, por niveles de arriba a abajo y de izquierda a derecha). Cuando ese primer vector de datos se llena, se usa el siguiente puntero a vector para apuntar a un nuevo vector en el que se guardará el siguiente nivel del montículo. Si ese nivel también se llena, se genera espacio para un nuevo nivel (puntero a un nuevo vector), etcétera.

Está explicado en esta página.

The Art of Computer Programming (TAOCP) es probablemente el libro más famoso de las Ciencias de la Computación. Tal es así, que suele conocerse como “la biblia de los informáticos” y su autor, Donald E. Knuth, es uno de los más reconocidos expertos en la Historia de la Informática.

A finales de 1999, TAOCP fue incluido por la publicación American Scientist entre los 12 libros más importantes de las “ciencias físicas” (las “no biológicas”) en el siglo XX, junto con el de Dirac sobre mecánica cuántica, el de Einstein sobre relatividad, el de Mandelbrot sobre fractales, el de Pauling sobre el enlace químico, el de Russell y Whitehead sobre fundamentos de matemáticas, el de von Neumann y Morgenstern sobre teoría de juegos, el de Wiener sobre cibernética, el de Woodward y Hoffmann sobre simetría orbital, el de Feynman sobre electrodinámica cuántica, el de Smith sobre la búsqueda de estructura, y la colección de artículos de Einstein de 1902 a 1909.

En el archivo MacTutor de Historia de las Matemáticas aparece una reseña biográfica de D. Knuth, en la que se cuenta lo siguiente sobre los orígenes de su libro TAOCP:

“Knowledge of his computing expertise was so well established by 1962 that, although he was still a doctoral student at the time, Addison-Wesley approached him and asked him to write a text on compilers. He began that project in the summer of 1962. […] By 1966 his book on compilers had grown to 3000 handwritten pages and Addison-Wesley realised that here was a much more major work than they had originally envisaged. Discussions led to a decision that Knuth should produce a seven volume work covering much more than compilers. The work became The Art of Computer Programming and publication began in 1968 when Volume 1: Fundamental Algorithms appeared. Volume 2: Seminumerical algorithms came out in the following year, and Volume 3: Sorting and searching in 1973. In the Preface Knuth writes that these are:

… books that have been designed to train the reader in the various skills which go into a programmer’s craft… [They are] not meant to serve as an introduction to computer programming; the reader is supposed to have some previous experience. [I aim to provide] (a) reference books which summarize the knowledge which has been acquired in several important fields, and (b) textbooks for self-study or for college courses in the computer and information sciences.

Knuth’s aim was to:

… organize and summarize what is known about the fast subject of computer methods and to give it firm mathematical and historical foundations.

… show that the connection between computers and mathematics is far deeper and more intimate than these traditional relationships would imply.”