Conocimientos teóricos
1. Eficacia de algoritmos: Concepto, elementos de medida, casos de medida. Análisis de bucles y selecciones. Análisis general de algoritmos recursivos.
2. Herramientas matemáticas básicas del análisis de eficacia de algoritmos: Comparación asintótica del crecimiento de funciones. Aproximación de sumas por integrales. Estimación de soluciones de desigualdades recurrentes.
3. Conocimiento detallado de algoritmos básicos de ordenación (Inserción, Shell, Quicksort, Mergesort, Heapsort, RadixSort): Pseudocódigos, evolución detallada sobre ejemplos, evolución sobre árboles de decisión. Análisis de eficacia en casos peor, medio y mejor. Cotas inferiores de rendimiento para familias de algoritmos.
4. Conocimiento detallado del funcionamiento de algoritmos de búsqueda sobre claves: Pseudocódigos, evolución detallada sobre ejemplos, evolución sobre árboles de decisión. Análisis de eficacia en casos peor, medio y mejor. Tipo de datos diccionario: implementación sobre árboles binarios de búsqueda y árboles AVL, rendimiento de primitivas.
5. Construcción de funciones hash y resolución de colisiones por encadenamiento y direccionamiento abierto.
Conocimientos prácticos
Alcance de un nivel medio-alto de programación en C: trabajo con punteros y memoria dinámica, determinación y control de errores, organización de código, archivos de cabecera.
Recomendaciones:
Conocimientos previos
Para un buen aprovechamiento del curso, es sumamente recomendable haber aprobado EDI I. El curso puede seguirse de no ser así, pero requerirá un esfuerzo extra considerable, lo que hará más difícil no sólo la superación de MTP II, sino también la de otras asignaturas en las que el alumno esté matriculado. También se supone unos conocimientos matemáticos básicos al nivel de los cursos Algebra I y Análisis Matemático I.
Asistencia a las clases
También se considera imprescindible la asistencia continua a las clases de teoría y problemas, y a las clases de prácticas. Durante el curso se fomentará la asistencia a las clases de teoría y problemas y se considerará cómo incorporar dicha asistencia y el seguimiento continuado de la asignatura a la calificación final.
La entrega de las prácticas propuestas es obligatoria. A su vez, se controlará la asistencia a las clases prácticas, procurándose que la misma influya de alguna manera en la calificación final.
Esfuerzo del estudiante
Independientemente del trabajo de preparación de exámenes, se recomienda:
Un repaso individual de 45-60 minutos por cada clase teórica.
La resolución de unos 6 problemas por semana lectiva.
Con el fin de medir el esfuerzo del estudiante en la asignatura según los criterios de European Credit Transfer System (ECTS), se efectuará al final del curso una encuesta sobre su trabajo a lo largo del curso. El enlace encuesta ECTS facilita un modelo de seguimiento semanal del trabajo en la asignatura, destinado a facilitar la realización de dicha encuesta.
Metodología Docente:
El curso constará aproximadamente de unas 14 semanas que darán lugar a
32 clases teóricas (lección magistral)
10 clases de problemas sobre asignaciones hechas previamente
28 clases prácticas con evaluación continua
Un enlace actualizado cada año indica el desarrollo concreto del curso en un año académico dado.
Programa:
Análisis de eficacia de algoritmos:
Algoritmos básicos de ordenación
Algoritmos avanzados de ordenación.
Árboles de decisión para algoritmos de ordenación.
