Estructuras de Datos y Algoritmos (EDA)

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 examen se realizará en los PCs de los laboratorios donde se ha convocado el examen, y con el software instalado en ellos para las prácticas de la asignatura: Java (JavaSE 1.6) y el entorno de programación Eclipse.

No se permite utilizar apuntes ni ningún otro material auxiliar durante los exámenes de la asignatura. Es decir, no está permitido el uso de libros, apuntes, ni el uso de instrumentos electrónicos (móviles, calculadoras, portátiles, lectores de libros electrónicos, etc.).

Las calificaciones obtenidas en cada una de las prácticas, asi como la nota final obtenida (sobre 10 puntos) pueden consultarse aquí. Para cualquier duda o aclaración, cada alumno deberá dirigirse a su profesor tutor de prácticas.

Solo obtienen nota de prácticas los alumnos que han entregado todas las prácticas de la asignatura, y aquellos que no obtienen al menos 5 puntos como nota final deberán presentarse al examen de prácticas para tener opción a aprobar la asignatura.  Más información sobre la evaluación de la asignatura y la convocatoria de exámenes aquí.

Firmado,

Los profesores de prácticas

• Examen escrito: sábado 28 de enero de 2012 a las 10:00 horas. Aulas A03 y A04.
• Examen práctico: martes 31 de enero de 2012 a las 10:00 horas. Laboratorios L0.03 y L0.04.

Más información en la página sobre “evaluación”.

Dos cosas:

• las encuestas de docencia se realizarán al principio de la clase del lunes 16 de enero;
• se ha añadido una lista de enunciados de ejercicios recomendados al final de la página de material del grupo de mañanas.

¡Felices fiestas!

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.

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.

Los montículos 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 cambiante de valores. Ejemplo:

Detalles: aquí (transparencias 26 a 37).

———

Por supuesto, utilidad de lo anterior: si n es grande.

Están disponibles las soluciones de los ejercicios de clase de los días 13 y 16 de diciembre.