En la página de material adicional de esta web puede encontrarse:
- Un artÃculo que describe un par de métodos de ordenación por fusión (o mezcla) “in situ” y analiza su coste (acceso con clave aquÃ).
- Un par de capÃtulos de libros sobre métodos de ordenación en memoria externa basados en la idea de la ordenación por fusión (acceso con clave aquà y aquÃ).
- La demostración de que el coste promedio del quicksort está en n log n (acceso con clave aquÃ).
- Comparación práctica de velocidades de métodos de ordenación: un applet, otro applet.
Se ha publicado una hoja de problemas (algoritmos de divide y vencerás).
Una compañÃa de televisión por cable pretende dar servicio a un nuevo barrio de la ciudad. Tiene restricciones impuestas por el ayuntamiento, de manera que sólo puede echar el cable por algunas de las calles. Además, algunas de las conexiones posibles entre las casas serÃan muy costosas, por ser demasiado largas o por requerir un soterramiento demasiado profundo. Asà que la compañÃa tiene que calcular la forma más barata de llegar a todas las casas por medio del cable.
La solución de este problema se obtiene representando las conexiones posibles entre las casas con un grafo (las casas serÃan los vértices y las aristas las calles por las que se tiene permiso para echar el cable), y calculando el árbol de recubrimiento de peso mÃnimo (minimum spanning tree).
Los dos algoritmos más conocidos para resolver el problema anterior, el de Prim y el de Kruskal, son ejemplos tÃpicos de algoritmos voraces. En esta asignatura veremos en qué consiste el esquema voraz de resolución de problemas y en qué casos da lugar a algoritmos correctos y por qué.
Haz clic en la imagen inferior para ver un applet que resuelve el problema.
Inicio de clases de Algoritmia Básica (curso 2016-17): el 8 de febrero a las 15:00 horas en el aula 12 del edificio Ada Byron.
Está disponible en el foro de moodle la evaluación de la segunda convocatoria.
El examen escrito tendrá lugar el 13 de septiembre de 2016 a las 10:00 horas en el Seminario A.22 del edificio Ada Byron. Ver en la nota (*) lo que dice la normativa de evaluación en relación con este examen.
Aclaraciones:
- Se debe ir provisto del DNI o carnet universitario.
- Se permite llevar al examen los apuntes que se desee.
- No se permite utilizar ningún dispositivo electrónico (teléfonos, tabletas, lectores electrónicos, portátiles, etc).
Nota:
(*) Examen escrito en el que se deberán resolver problemas de naturaleza similar a los ejercicios planteados en clase durante el cuatrimestre, a los problemas planteados en la prueba escrita intermedia y, en su caso, responder preguntas conceptuales o resolver algún ejercicio en el que se demuestre haber logrado los resultados de aprendizaje requeridos en la asignatura. La calificación obtenida pondera un 70% de la nota final de la asignatura. Los alumnos que hayan realizado la prueba escrita intermedia serán exentos de realizar una parte del examen escrito, debiendo realizar sólo una parte obligatoria del examen, que se determinará en ese mismo momento. En ese caso, la calificación obtenida en la prueba escrita intermedia pondera un 30%, y la de la parte obligatoria del examen escrito final un 40%. El examen de laboratorio para quienes renuncien a las prácticas realizadas durante el curso: contactar con el profesor.
