Indice:

1. Programa
2. Bibliografía
3. Prácticas (objetivos, enunciados, convocatoria al examen)
4. Evaluación
5. Enlaces recomendados

Programa:

• Tema 1: Eficacia de algoritmos:
• Concepto, elementos de medida, casos de medida.
• Análisis de bucles y selecciones.
• 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.
• Tema 2: Conocimiento detallado de los algoritmos básicos de ordenación: Inserción, Selección, Burbuja, Shell, Mergesort, Quicksort, Heapsort y RadixSort:
• Pseudocódigos, evolución detallada sobre ejemplos, evolución sobre árboles de decisión.
• Análisis de eficacia en casos peor, mejor y medio.
• Cotas inferiores de rendimiento para familias de algoritmos.
• Técnicas específicas para algoritmos recursivos.
• Tema 3: Conocimiento detallado del funcionamiento de algoritmos de búsqueda sobre claves (búsqueda lineal, búsqueda binaria, Hashing):
• Pseudocódigos, evolución detallada sobre ejemplos, evolución sobre árboles de decisión.
• Análisis de eficacia en casos peor, mejor y medio.
• Tipo de datos diccionario: implementación sobre árboles binarios de búsqueda y árboles AVL, rendimiento de primitivas.
• Construcción de funciones hash y resolución de colisiones por encadenamiento y direccionamiento abierto.

Bibliografía:

• Textos recomendados:
• T.H. Cormen, E. Leiserson, R.L. Rivest.
          Introduction to Algorithms.
         The MIT Press-McGraw-Hill. 1990,2001.
• M.A. Weiss.
          Data Structures and Algorithm Analysis in C, 2nd Edition.
           Addison Wesley Longman, 1997.
• A.V. Aho, J.E. Hopcroft, J.D. Ullman.
          The design and analysis of computer algorithms.
          Addison-Wesley, 1974.
• S. Baase.
           Computer Algorithms
           Addison-Wesley, 1988.

Prácticas:

    El objetivo de las prácticas es alcanzar un nivel medio-alto de programación en C con la implementación  y el análisis de varios algoritmos descritos en las clases de teoría.  Se hará énfasis en:

• el trabajo intensivo con punteros y memoria dinámica
• la determinación y el control de errores
• la organización del código
• el uso de archivos de cabecera
• la construcción de rutinas de cómputo de tiempos de ejecución.

• Todas ellas han de compilar y ejecutar sin errores, y producir resultados correctos para poder superar la parte de prácticas de la asignatura.
• Su código es la base sobre la que se desarrollará el examen de prácticas.
• Una de las entregadas se corregirá en profundidad tras el examen.

Enunciados de prácticas del curso 2002-03:

• Práctica 1  (códigos del enunciado en ascii)
• Práctica 2  (códigos del enunciado en ascii)
• Práctica 3
• Práctica 4 (códigos del enunciado en ascii)

Evaluación:

Importante: la Teoría y las Prácticas se aprobarán por separado. Para la convocatoria de Febrero, la realización de cualquiera de los dos exámenes supone consumo de convocatoria. Los aprobados parciales en uno u otro en la convocatoria de Febrero se guardarán únicamente hasta la convocatoria de Septiembre del mismo curso.

La fórmula utilizada para obtener la calificación final en la asignatura es:

Nota final: 80% Nota Teoría + 20% Nota Prácticas
 

Evaluación de contenidos teóricos:

1. Examen escrito final: 6-8 cuestiones teóricas y prácticas a desarrollar en 3 horas, sin material auxiliar, sobre definiciones y enunciados de resultados teóricos, breves justificaciones de resultados teóricos sencillos y ejercicios y problemas representativos del programa.
2. Examen intermedio: 3-4 cuestiones teóricas y prácticas a desarrollar en 1.5 horas, sin material auxiliar.

Cálculo de la nota teórica: máximo entre

1. 0.65*( Nota examen final /10) + 0.35*(Nota examen intermedio / 10)
2. Nota examen final / 10.

Evaluación de contenidos prácticos:

    Tiene como objetivo comprobar la capacidad del estudiante de:

• Programar los algoritmos asignados durante el curso y en el examen, incorporando elementos de medición de su rendimiento.
• Ejecutarlos comprobando su corrección funcional y la adecuación de las mediciones con los resultados teóricos esperados.

Los exámenes se realizarán durante las dos últimas semanas lectivas del curso, en fechas que se anunciarán oportunamente. Se aplicarán las siguientes normas:

• Es condición imprescindible para poder optar a participar en el examen el haber entregado en su momento todas las prácticas asignadas durante el curso. Como es obvio, dichas prácticas (código y memoria) se ajustarán a los guiones repartidos al efecto y deberán compilar y ejecutar correctamente.
• Los estudiantes acudirán al aula en que se les cite de manera individual, donde se les asignará un PC. Han de llevar de manera obligatoria copia, en disquete u otro medio, del código fuente que entregaron en su momento, con todas las prácticas que se han asignado durante el curso. También podrán llevar el material de apoyo que deseen.
• El examen tendrá una duración de dos horas y se efectuará sobre una práctica concreta de las entregadas por el estudiante.
• En la primera hora el estudiante programará una rutina relevante a la práctica en cuestión, que habrá de integrar en el código original de la práctica y comprobar que compila, ejecuta y produce los resultados esperados. También podrá tener que responder por escrito a alguna cuestión relativa a la práctica o a sus resultados.
• En la segunda hora el profesor verificará con cada estudiante los puntos (compilación, ejecución, primeros resultados) anteriormente citados, recogiendo el código producido y las posibles respuestas complementarias. También se podrá preguntar al alumno cuestiones sobre la organización y programación de la práctica correspondiente.

La corrección tendrá dos partes:

• Una primera en el propio examen, centrada en los aspectos anteriores.
• Una segunda fuera del examen, sobre el material recogido en el mismo y sobre la versión de la práctica inicialmente entregada. Esta segunda corrección sólo se producirá si se ha superado la primera y, en particular, si el código entregado compila sin errores y ejecuta sin interrupciones anómalas.

La normativa sobre copia de exámenes o prácticas elaborada por la ETSI se aplicará, como es natural, en todos sus puntos. En particular, la copia de prácticas o exámenes supondrá, de entrada, el suspenso de la asignatura en la convocatoria correspondiente.

Enlaces recomendados:

• Página de animación de algoritmos