. Existe un algoritmo de coste asintótico lineal, en el caso peor, para el cálculo del estadístico de orden k de un vector de tamaño n. Por tanto, en particular, puede usarse para el cálculo de la mediana (haciendo k = techo(n/2) ). Puede verse aquí.

Me habéis preguntado en clase si se conoce algún algoritmo mejor que el de coste cuadrático visto en clase para el problema de la transparencia 84 de algoritmos voraces. He encontrado una respuesta en el libro Computer Algorithms, de Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran (Computer Science Press, 1998): It can be reduced from O(n2) [...]

. Hemos visto en clase que algunos problemas poseen la estructura algebraica subyacente de matroide y en ese caso pueden resolverse correctamente con un algoritmo voraz. Existe una extensión del concepto de matroide que permite llegar un poco más lejos, para resolver más problemas con algoritmos voraces: se trata de los gridoides. En Wikipedia o en [...]

Podría pensarse que el coste de la creación de un montículo (heap) con n elementos está en O(n log n), dado que hay que insertar n datos y cada inserción, en el caso peor, sería O(log n). Pues bien, haciendo el “cálculo fino” (penúltima transparencia de este fichero) puede demostrarse que realmente ese coste está [...]

Hoy, para ver una implementación eficiente del algoritmo de Kruskal, hemos hablado de la función α como inversa de la función de Ackerman. Si alguien anda buscando crecimientos grandes para perder un poco el tiempo, puede echar un vistazo a la notación sagital de Knuth, a la notación sagital encadenada de Conway, a la notación de Steinhaus–Moser, a los números [...]

Algunas aplicaciones del problema del árbol de recubrimiento de coste mínimo: Diseño de redes (de telefonía, eléctricas, hidráulicas, de TV por cable, de computadores, de carreteras…) Algoritmos aproximados para problemas NP => asignatura “Algoritmia para problemas difíciles” Algoritmos de agrupamiento (clustering analysis) Aplicaciones indirectas: caminos cuello de botella códigos LDPC para corrección de errores registro [...]

. Hoy hace un día estupendo para responder la encuesta de docencia de Algoritmia Básica. ¡A por ella! http://encuestas.unizar.es

. Ver esta entrada anterior…

. Las transparencias sobre la solución del problema del viajante de comercio con programación dinámica están basadas en el material del libro: Algorithmics. Theory and Practice, de Gilles Brassard y Paul Bratley (ed. Prentice Hall, 1988). En este enlace (acceso restringido) pueden encontrarse las páginas correspondientes.

. Hablaremos en clase de la distancia de edición entre secuencias de caracteres. El problema tiene aplicaciones, entre otras muchas, en los dominios de la bioinformática (ver el enlace http://webdiis.unizar.es/asignaturas/AB/?p=93) y de la robótica (ver http://webdiis.unizar.es/asignaturas/AB/?p=1144).