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.

La teoría y los ejemplos de aplicación se hirán presentando de forma más o menos paralela a lo largo del curso.

Las cinco horas semanales en promedio de la asignatura se organizan en dos bloques de horas cada semana y un bloque de dos horas en semanas alternas.

La evaluación constará de un examen parcial, un
examen ante ordenador, un examen final y un
trabajo práctico voluntario.

El examen parcial (P) es una prueba escrita donde entra
la materia de los temas 1 a 4.

El examen ante ordenador (M) es una prueba
consistente en resolver dos problemas sobre la
materia de los temas 2, 4, 5 y 6 ante
el ordenador y utilizando el sistema del Juez.

El examen final (F) es una prueba escrita donde entra
toda la materia de la asignatura.

El trabajo práctico voluntario (V) consiste en la
implementación de un jugador para un juego.

La nota de la asignatura se calcula así:

NOTA = min (10, max (25% P + 25% M + 50% F, 100% F) + 20% V)


La temporización es la siguiente:

El examen parcial se hace a mediados de curso, el examen
ante ordenador a finales de curso y el examen
final una vez terminado el curso. El trabajo voluntario
debe entregarse a finales de curso.


El mecanismo del examen ante máquina es el
siguiente:

Delante del ordenador, los estudiantes reciben dos
problemas. Un problema se define con un
enunciado, uno o más juegos de pruebas públicos y,
quizá, cierto código ya implementado. Cuando un estudio
quiera entregar su solución para alguno de los
problemas, lo envía a un juez automático que, en
poco segundos, le devolverá el veredicto sobre el
comportamiento de su programa. El estudiante puede
reenviar hasta 10 soluciones para el mismo
problema. Los profesores corregirán el último
envío realizado por cada problema.


El mecanismo del trabajo práctico voluntario es el
siguiente:

Después del parcial, se entregará el enunciado del
trabajo práctico voluntario, que consistirá en la
descripción de un juego. Los estudiantes que quieran
llevar a cabo el trabajo práctico voluntario deberán
de programar un jugador para este juego (es decir,
implementar una estrategia para intentar ganar el
juego). Junto con el enunciado, los profesores
también entregarán el código de un jugador muy sencillo:
el tonto.

A finales de curso, habrá un enfrentamiento público
a través de un sistema de rondas que incluirá todos
los jugadores entregados por los estudiantes y el tonto.
De este enfrentamiento se deducirá una clasificación
y se nombrará un campeón.

La nota del trabajo práctico voluntario se calcula
automáticamente a partir de la posición en la
clasificación, de forma lineal y garantizando que el
campeón tenga un 10 y que todos los participantes
que ganen al tonto tengan una nota mínima de 5.
Los jugadores que no ganen al tonto tendrán una
nota de 0.

La entrega del trabajo práctico voluntario
implica aceptar que, si se comprueba que ha
habido fraude en su realización, se restarán
sus puntos (en lugar de sumarlos) a los de
la asignatura.

• R. Sedgewick Bundle of Algorithms in CPP, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition), Addison-Wesley, 2001.
• Mark Allen Weiss Data structures and algorithm analysis in C++, Pearson Education, 2006.
• Thomas H. Cormen ... [et al.] Introduction to algorithms, MIT Press, 2001.
• G. Brassard, T. Bratley Fundamentos de algoritmia, Prentice Hall,, 1996.

• Mark Allen Weiss Data structures and problem solving using C++, Pearson Education International, 2003.
• Ian Parberry Problems on algorithms, Prentice Hall, 1995.
• Narciso Martí Oliet, Yolanda Ortega Mallén, José Alberto Verdejo López. Estructuras de datos y métodos algorítmicos : ejercicios resueltos, Pearson Educación, 2001.

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.