Encuestas
Hoy se abre el plazo para realizar las encuestas de evaluación de la enseñanza y de la labor docente del profesorado. En este curso se ha eliminado el uso de papel como soporte. Toda la información sobre el tema está en la página:
Las encuestas pueden realizarse bien desde un computador, en la página:
https://janovas.unizar.es/atenea/ate100bienvenida.xhtml
o bien desde un teléfono móvil, accediendo a la página de Unizar y siguiendo la banderola correspondiente.
Vuestra participación es muy importante para ayudarnos a mejorar.
Este jueves tiene horario de lunes
El jueves 12 de diciembre tiene horario de lunes.
Clase de problemas de la semana próxima
El martes 3 de diciembre habrá clase de problemas. Los enunciados están disponibles en la página de material del grupo de mañana (y en la de material adicional).
Mejora del quicksort para conseguir coste O(n log n) en el caso peor
El quicksort, tal y como aparece en los libros, tiene un coste asintótico cuadrático en el caso peor.
No obstante, existe una modificación no trivial del quicksort que sí consigue un coste asintótico O(n logn). Consiste en elegir la mediana como el pivote que se utiliza para la partición del vector en dos trozos, en cada llamada recursiva del quicksort.
El cálculo de la mediana de los n datos de un vector es un caso particular del conocido como problema de selección, consistente en calcular el estadístico de orden k de esos datos (es decir, el dato que ocuparía la posición k en el supuesto en que se ordenasen los datos de menor a mayor). Si n es impar, la mediana sería el estadístico de orden (n+1)/2; si por el contrario n es par, hay dos medianas que son los estadísticos de orden n/2 y n/2 + 1.
Como decía, se conoce un algoritmo de coste asintótico lineal en el caso peor para el problema de selección y, por tanto, para el cálculo de la mediana. Os lo incluyo aquí debajo, extraído del libro Introducion to Algorithms, de Cormen, Leiserson, Rivest y Stein.
Uso de colas con prioridad en el algoritmo de Dijkstra
Las colas con prioridad (y por tanto la estructura de datos montículo con la que se representan en memoria) se utilizan a menudo para mejorar la eficiencia de algoritmos en los que iterativamente se precisa conocer el mínimo (o máximo) de un conjunto de valores y eliminarlo del conjunto. Ejemplo:
Si utilizamos una cola con prioridades (montículo), añadiéndole una operación de reducción de clave, el algoritmo anterior queda de la siguiente forma:
(Detalles: en la asignatura Algoritmia Básica, de la Especialidad en Computación)
———
Por supuesto, la utilidad del algoritmo anterior se obtiene si n es grande.
| n | 10 | 100 | 1000 | 10000 | 100000 | 1000000 |
| n log n | 30 | 600 | 10000 | 130000 | 1600000 | 19000000 |
| n2 | 100 | 10000 | 1000000 | 100000000 | 10000000000 | 1000000000000 |
Nuevas hojas de ejercicios
En la semana próxima (o en la siguiente) haremos dos horas de problemas. Los enunciados están disponibles en la página de material de clase.
Más ejercicios de los Temas I y II
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).
Árboles rojinegros
Una alternativa a los árboles AVL son los árboles rojinegros.
Aquí tenéis unas transparencias bastante autocontenidas:
Un applet para probarlos: aquí (seleccionar “R-B” en el panel de la derecha).
Y el capítulo de un libro con una implementación “top-down”: con código Java y con código C++ (acceso restringido, acceder con usuario y clave habituales).
Clase de problemas del 8 de noviembre
El próximo viernes (8 de noviembre) hay clase de problemas (NIPs impares en el aula habitual, NIPs pares en el aula alternativa). Están disponibles los enunciados en las páginas de material de clase y también en la página de material adicional. Se recomienda haberlos trabajado con anterioridad a la clase.
Se han publicado también en la página de material de clase algunas soluciones de ejercicios de hojas anteriores.
Donald Knuth y el arte de programar ordenadores
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.”