Estructuras de Datos y Algoritmos (EDA)

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

Según nos informa el Servicio de Mantenimiento del Campus, este sábado, día 20, hay un corte de corriente programado en el Edificio Ada Byron para la realización de unas obras (instalación de unos nuevos equipos de protección).

Al realizarse el corte fuera del horario laboral del Personal de Administración y Servicios del DIIS capacitado para realizar las operaciones de apagado y encendido de servidores, en esta ocasión (debido a compromisos previos) no es posible ajustar al máximo el tiempo de pérdida de servicio (como se ha hecho otras veces).

Por lo tanto, el calendario de actuaciones será:

• Viernes 19, a partir de las 14:30, comienza el apagado de servidores del DIIS, quedando todo apagado (incluidos los servidores web) excepto lo mínimo imprescindible para la realización de prácticas.
• Viernes 19, a partir de las 20:00, se apaga el servidor de prácticas y resto de infraestructuras de la sala de servidores; queda todo apagado durante todo el fin de semana.
• Lunes 22, a partir de las 8:00, comienza el encendido de servidores (condicionado al funcionamiento de la infraestructura de comunicaciones); se interará que a la misma hora el SICUZ verifique también los servicios de red.

Los árboles AVL se proponen por primera vez en la literatura en el artículo:

G.M. Adelson-Velskii y E.M. Landis: “An algorithm for the organization of information”. Proceedings of the USSR Academy of Sciences, vol. 146, pp. 263–266, 1962 (en ruso).

Los autores son los matemáticos Georgi Maksimovich Adelson-Velskii (Samara, Rusia, 1922 – ) y Evgenii Mikhailovich Landis (Járkov, Ucrania, 1921 – 1997).

G.M. Adelson-Velskii (izquierda) y E.M. Landis (derecha)

En la página de prácticas se ha publicado el enunciado de la cuarta práctica. Puede descargarse directamente de:

• [PDF] Enunciado práctica 4. Para realizar entre el 18 y el 25 de noviembre, según el horario de cada grupo. Entregar no más tarde del 1 de diciembre.

En las entrevistas que hemos realizado durante la semana pasada ya los he ido comentando con vosotros individualmente, pero creo que puede ser provechoso para todos poner un pequeño resumen aquí. Se trata de errores que hemos podido ver en vuestro código; en muchos casos no perjudican la funcionalidad del programa, pero sí que afectan a todo lo que tiene que ver con la legibilidad y mantenibilidad del código (lo que pasaría si tenemos que volver a trabajar sobre el código de esta práctica un poco más adelante):

• Repetición de código:
  • En muchos casos se ha desarrollado código para hacer las mismas cosas en distintos procedimientos y funciones. Por ejemplo, para desarrollar quitar del TAD multiconjunto es necesario buscar el elemento; también es necesario buscarlo para desarrollar pertenece. También puede ser necesario (en algunas implementaciones del tipo, no en todas) para desarrollar poner. Es una mala práctica copiar y pegar el mismo código (o prácticamente el mismo) en cada caso.
  • Ocurre algo parecido cuando se necesita añadir caracteres a una cadena. Por ejemplo en getcad, o en str2cad, donde lo natural sería utilizar aniadeCar.
  • Unos pocos, además, han repetido el código a la hora de hacer putcad y putcad_line, cuando claramente la segunda puede hacerse llamando a la primera.
  • Finalmente, parece que desconocíais la existencia de los descriptores de ficheros asociados a la entrada estándar (Standard_Input) y la salida estándar (Standard_Output) que os hubieran permitido desarrollar las funciones de entrada y salida sin parámetro de fichero a partir de las otras
• ¡Cuidado con los límites!
  • Sobre todo en implementaciones estáticas (tablas, vectores) hay que comprobar y tener en cuenta que la estructura de datos puede estar vacía (índice 0, ¿es posible?) o completamente llena (¿qué pasa cuándo queremos añadir un dato a una estructura en la que ya no caben más?).
  • En estructuras dinámicas también hay que tener cuidado, en este caso con los punteros (el valor NULL del ‘siguiente’ del último dato indica el final de la lista).
  • Finalmente, algunos getcad de los que habéis desarrollado no contemplaban la posibilidad de que la cadena fuera vacía (el usuario le da al retorno de carro cuando estamos leyendo).
• Modificación de las especificaciones: Algunos grupos han evitado el problema de la lectura de cadenas del programa principal modificando la entrada esperada por el programa (normalmente, separando la cadena que se leía del carácter en líneas diferentes). Otros han modificado la especificación del programa para que tuviera que leer desde un fichero. Es mala idea hacer ese tipo de modificaciones porque a la hora de usar vuestro programa hay que ‘aprender’ su funcionamiento. Además, evitáis algunos de los problemas interesantes que planteaba la especificación original.

Nos comunica el Subdirector del CPS que…

“ha comenzado la 1ª FASE del proceso de evaluación de la docencia de las asignaturas correspondientes al PRIMER cuatrimestre. En la dirección http://www.unizar.es/evaluaciondocencia/ podrás cumplimentar el formulario on-line. El plazo para la cumplimentación de las encuestas finaliza el próximo día 22 de noviembre.

Animándote a participar en el proceso de opinión y mejora de la docencia y agradeciendo por anticipado tu colaboración, aprovecho la ocasión para transmitirte un cordial saludo. Aprovecho la ocasión para indicarte que la 2ª fase del proceso (cuya normativa puedes consultar en https://gestiona.unizar.es/evaluaciondocencia/doc/Normativa-basica.pdf), se realizará de forma presencial, entre el 15 de diciembre de 2010 y el 22 de enero de 2011.”

MEJORAR LA DOCENCIA: TÚ TIENES LA PALABRA

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

Se suspende la clase del grupo de mañana del próximo lunes 15 de noviembre por imposibilidad del profesor para asistir (por causas médicas).

En la página de prácticas se ha publicado el enunciado de la tercera práctica. Puede descargarse directamente de:

• [PDF] Enunciado práctica 3. Para realizar entre el 4 y el 11 de noviembre, según el horario de cada grupo. Entregar antes del 17 de noviembre.

Se ha habilitado el sistema para enviar la práctica 2, con una pequeña variación con respecto al enunciado de la práctica. La forma de hacerlo es mediante la instrucción:


someter eda_10 p2.tar

La lista para apuntarse para la entrevista sobre la práctica estará disponible a lo largo de la mañana del jueves día 4 de noviembre.