Estructuras de Datos y Algoritmos (EDA)

Quedan muy pocos días para realizar las encuestas sobre la docencia.
Son muy importantes para facilitar la mejora, año a año, de la asignatura.
Si no lo habéis hecho todavía, os rogamos unos minutos para responderlas.
http://encuestas.unizar.es/

Se han publicado en la página de material del grupo de mañana algunos enunciados de ejercicios para trabajar en los próximos dos viernes (12 y 19 de diciembre).

Se han publicado en la página de material del grupo de mañana algunos ejercicios con los que trabajaremos en la clase de este viernes. Se recomienda trabajar en ellos con anterioridad a esa clase.

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.”

Se han publicado en la página de material del grupo de mañana algunos ejercicios sobre montículos, con los que trabajaremos en la clase de este viernes. Se recomienda trabajar en ellos con anterioridad a esa clase.

Se han publicado en la página de material del grupo de mañana algunos ejercicios sobre árboles n-arios, con los que trabajaremos en la clase de este viernes. Se recomienda trabajar en ellos con anterioridad a esa clase.

Una alternativa a los árboles AVL para construir árboles binarios de búsqueda de altura logarítmica en el número de nodos son los árboles rojinegros.

Aquí tenéis unas transparencias bastante autocontenidas (acceso restringido, acceder con usuario y clave habituales):

Y el capítulo de un libro con una implementación “top-down”: en C++, y en Java (acceso restringido, acceder con usuario y clave habituales).

Si bien la lección no está incluida en el programa de la asignatura, se incluye aquí un texto que trata la transformación de algoritmos recursivos en iterativos.
[issuu width=420 height=297 embedBackground=%23000000 backgroundColor=%23222222 documentId=121105155255-44efe93b155e49a6a28f9f29874148d6 name=recursivo_a_iterativo username=javier.campos tag=algoritmos unit=px v=2]
Pdf descargable aquí (autor: Javier Campos).

Se han publicado en la página de material del grupo de mañana algunos ejercicios sobre árboles binarios de búsqueda, con los que trabajaremos en la clase de este viernes. Se recomienda trabajar en ellos con anterioridad a esa clase.

Se ha publicado en la página de material adicional un documento con más ejercicios de los Temas I y II (especificación e implementación de TAD’s lineales).