. 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á [...]

Como se dijo en clase y aparece en la Guía académica oficial, se estima que es necesario un trabajo personal no presencial de 4 horas semanales, en promedio, para superar esta asignatura (además de la asistencia a clase y de la realización de las prácticas de laboratorio). En la página de “Problemas” podéis encontrar ya [...]

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 [...]

Tenemos varios: En clase (aula A12). Tutorías en el despacho (dentro o fuera del horario, mejor quedar antes por mail). Esta página web (podéis leer contenidos directamente desde RSS, comentarlos…). Moodle2 (acceso), para difundir anuncios o comentarlos (llega copia por correo electrónico a todos). Twitter (enlace): noticias, curiosidades, enlaces adicionales… (tú nos sigues, si quieres; nosotros NO [...]

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 [...]

Empezamos mañana martes, a las 15 horas, en el Aula 12 del Edificio Ada Byron con la presentación de la asignatura.