Análisis y Diseño de Algoritmos (ADA)

Proveer al estudiante de las técnicas básicas de algorítmica que permiten abordar el desarrollo de programas correctos y eficientes para resolver problemas no triviales. Dichas técnicas básicas incluyen conocimientos teóricos y prácticos, habilidades, experiencias y sentido crítico, todas ellas fundamentadas en teorías y técnicas sólidas, comprobadas y bien establecidas.

Conocimientos

1. Análisis de algoritmos: Eficiencia, costes, casos, notación asintótica, resolución de recurrencias simples.
2. Estructuras de datos: Colas de prioridad, diccionarios, grafos.
3. Esquemas algorítmicos: Dividir y vencer, voraces, búsqueda exhaustiva, programación dinámica.
4. Algoritmos fundamentales: Ordenación, caminos mínimos, árboles de expansión...

Habilidades

1. Entrar en contacto con algunas técnicas fundamentales de diseño y análisis de algoritmos y de estructuras de datos.
2. Adquirir una metodología para la especificación, el uso, el diseño y la implementación de TAD.
3. Conocer y saber usar una variedad de técnicas de implementación eficientes de estructuras de datos.
4. Conocer TAD genéricos, saber usarlos y saber adaptarlos para dar soluciones a necesidades específicas.
5. Saber razonar sobre la corrección y la eficiencia tanto de las implementaciones de TAD como de los algoritmos que se usan.
6. Disponer de criterios que permitan -durante las etapas de especificación, diseño e implementación- escoger la alternativa más adecuada y disponer de elementos para argumentar de forma razonada las elecciones realizadas.
7. Conocer algunos algoritmos clásicos para problemas fundamentales.
8. Saber particularizar esquemas algorítmicos generales para resolver problemas.

Competencias

1. Capacidad para el razonamiento crítico y lógico-matemático.
2. Capacidad para resolver problemas aplicando los métodos de la ciencia y la ingeniería.
3. Capacidad para diseñar sistemas, componentes o procesos que se ajusten a unas necesidades, usando los métodos, técnicas y herramientas más adecuadas en cada caso.
4. Capacidad de abstracción. Capacidad para enfrentarse a problemas nuevos recurriendo conscientemente a estrategias que han resultado útiles en problemas resueltos anteriormente.
5. Saber aplicar el ciclo de resolución de problemas típico de la ciencia y la ingeniería: especificación, generación de ideas y alternativas, diseño de una estrategia de solución, ejecución de la estrategia, validación, interpretación y evaluación de los resultados. Capacidad para analizar el proceso una vez ha acabado.
6. Capacidad para estudiar de diversas fuentes, identificando cuándo la información recibida en clase no es suficiente y buscando información complementaria.
7. Capacidad para relacionar y estructurar información de varias fuentes, para integrar ideas y conocimientos.

El temario se expone de forma muy práctica, a través de la presentación de muchos ejemplos.

Las clases se dividen en dos tipos: sesiones de teoría y sesiones de problemas. En media, las clases de teoría y problemas tienen el mismo número de horas semanales.



Las sesiones de teoría son clases de tipo magistral, es decir, clases en las que el profesor aporta a los alumnos nuevos conceptos o nuevas técnicas, así como ejemplos seleccionados que los motiven o ilustren.



Las clases de problemas tienen como objetivo desarrollar ejercicios o casos de estudio. Los profesores son quienes proponen los problemas que deben resolverse. Por lo que respecta a los ejercicios, la finalidad es la presentación y discusión de soluciones a enunciados relativamente simples que requieran pocos conocimientos teóricos o técnicos. En general, se trata de ejercicios escogidos con tal de ilustrar conceptos que se han explicado en las sesiones de teoría más recientes. Para los casos de estudio, los problemas propuestos tienen una mayor complejidad que la de los ejercicios y, además, incluyen diferentes conceptos teóricos que es necesario combinar para obtener una buena solución.

La evaluación constará de dos examenes parciales (PAR1 i PAR2),
y un examen final (FINAL), este último para los alumnos que hayan optado por no acogerse a la evaluación
continuada o que hayan obtenido una nota inferior a 4 en el primer parcial (PAR1). En el examen FINAL entra toda la materia de la asignatura.

Además, a lo largo del curso,
el alumno puede obtener entre 0 y 1 puntos correspondientes a trabajos voluntarios propuestos por los profesores (TV), consistentes en la realización de pequeños ejercicios de programación.

El primer examen parcial libera la primera parte de temario, en la que entran típicamente
los temas 1 a 4
del temario. Los alumnos que no quieran acogerse a la evaluación continuada (y por tanto no se han presentado al primer parcial) o que
obtengan una nota inferior a 4 en este
parcial habrán de presentarse al examen final.
Quienes hayan obtenido una nota mayor o igual a 4 en el parcial PAR1 pueden presentarse al examen final si lo desean, pero en tal caso no se les conservará la nota PAR1.
La nota de la asignatura se calcula de la siguiente manera:

[si PAR1 < 4 ó PAR1 = NP ] NF = min(FINAL + TV, 10)

Quienes obtienen una nota superior o igual a 4 en el primer parcial,
podrán escojer entre hacer el segundo parcial o el examen final.
En el segundo parcial entran típicamente los temas 5 a 7.
La nota de estos estudiantes será, según si hacen el segundo parcial o el final:

[si PAR1 >= 4 i PAR2 != NP] NF = min((PAR1 + PAR2) / 2 + TV, 10)
[si PAR1 >= 4 i PAR2 = NP i FINAL != NP] NF = min(FINAL + TV, 10)

El segundo examen parcial PAR2 se realiza en el mismo día y hora que el examen
FINAL, pero es de menor duración ya que sólo cubre una parte de temario.

Los exámenes consistirán en la resolución de problemas que permitan evaluar el grado de consecución de los objetivos específicos. Como mínimo un 80% de la nota de todas las pruebas provendrá de problemas basados en los que aparecen en la colección de problemas de la asignatura y que está a disposición de los estudiantes. Cada cuatrimestre habrá dos ediciones de la colección, una a comienzos del cuatrimestre (de cara a PARA1) y otra hacia mitad de curso (de cara a PAR2 y FINAL). No habrá ninguna otra modificación de la colección a lo largo del curso.

• R. Sedgewick Bundle of Algorithms in CPP, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition), Addison-Wesley, 2001.
• M.A. Weiss Data Structures and Algorithm Analysis in CPP (2nd Edition), Addison-Wesley, 1999.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein Introduction to Algorithms, Second Edition, MIT Press, 2001.
• Brassard, Bratley Fundamentos de Algoritmia, Prentice Hall, 1997.

• M.A. Weiss Data Structures and Problem Solving Using CPP (Second Edition), Addison-Wesley,, 2000.
• Ian Parberry and William Gasarch Problems on Algorithms, 2a edició disponible online a http://hercule.csci.unt.edu/ian/books/poa.html, 2002.
• N. Martí, Y. Ortega, J.A. Verdejo Estructuras de datos y métodos algorítmicos - Ejercicios resueltos, Prentice Práctica, 2003.

Dominio de las técnicas de programación imperativa basada en objetos:
- paso de parámetros,
- clases,
- objetos,
- métodos,
- punteros,
- memoria dinámica,
- genericidad,
- uso de clases estándar.

Conocer bien al menos un lenguaje imperativo orientado a objetos, preferentemente C++.
Recursividad.
Concepto de TAD.

TAD secuenciales:
- pilas,
- colas,
- listas con punto de interés,
- listas con iteradores.

Uso e implementación interna de los TAD secuenciales.

TAD arbóreos:
- árbol binario,
- árbol n-ario,
- árbol general,
- recorridos.

Uso e implementación interna de los TAD arbóreos.

Conocimientos matemáticos sobre grafos, sumatorios, límites. Matemática discreta. Capacidad para seguir y proponer razonamientos matemáticos.

Algunos conocimientos rudimentarios de estadística y probabilidades: espacio de probabilidad, acontecimientos, funciones de distribución, variable aleatoria, esperanza.