El diseño de algoritmos es parte del núcleo de las ciencias de la computación. El estudio de algoritmos y estructuras de datos es fundamental para el desarrollo de soluciones computacionales eficientes a problemas de gran tamaño. El cuerpo de conocimiento desarrollado en este campo es de importancia primordial para abordar soluciones eficientes de problemas en todas las ciencias e ingenierías.



En esta asignatura se estudia una colección de algoritmos clásicos, junto con sus técnicas de análisis y diseño. Estos algoritmos son la base de la solución de problemas típicos y de utilidad general en el desarrollo de aplicaciones.



Esta asignatura es la continuación natural de la asignatura Estructuras de datos y algoritmos; y conviene tener buenos conocimientos de la misma para poder afrontar Diseño de Algoritmos sin demasiada dificultad. También conviene recordar los conocimientos básicos adquiridos en las asignaturas de Análisis Matemático y Matemática Discreta: conjuntos, funciones, límites, combinatoria y lógica formal.



Además, esta asignatura establece una base de conocimiento que beneficia el aprovechamiento de cursos de Inteligencia artificial, Minería de datos, Aprendizaje automático, Heurísticos de búsqueda o Procesamiento del lenguaje.



Añadir, que para el estudiante puede ser de interés la web de la especialidad de la que es parte la asignatura Diseño de Algoritmos (http://moodletic.ehu.es/moodle/course/view.php?id=3037). En la misma hay información sobre diversos ámbitos de aplicación de las aéreas de conocimiento de la especialidad así como algunas salidas profesionales relacionadas con las asignaturas de la especialidad. Se precisa cuenta de LDAP para acceder al portal.

Análisis de algoritmos. Resolución de recurrencias. Recorridos de grafos. Técnicas de diseño de algoritmos: Divide y Vencerás, Programación Dinámica, Algoritmos voaces, Algoritmos de vuelta atrás

Tema 1 Análisis de algoritmos. Conceptos básicos del análisis de algoritmos: operación elemental, tamaño de la entrada, función de coste. Procesos pertinentes para expresar la función de coste de los algoritmos. Análisis de un algoritmo en el caso peor y en el caso medio.

Tema 2 Notación asintótica. Definición de las notaciones asintóticas y la técnica básica para clasificar funciones en la notación asintótica correspondiente.

Tema 3 Resolución de recurrencias. Técnicas de resolución de recurrencias: por expansión, método de la ecuación característica, cambio de variable.

Tema 4 Montículos. Definición de la estructura de Montículo y presentación de implementaciones eficientes de sus operaciones relevantes, reconociendo situaciones en las que pueden utilizarse para mejorar la eficiencia de algunos procesos.

Tema 5 Divide y Vencerás. Definición de la técnica Divide y Vencerás para la resolución de problemas algorítmicos. Presentación de algoritmos clásicos que utilizan esta técnica: Ordenación_por_Mezcla, Ordenación_rápida y otros.

Tema 6 Programación Dinámica. Definición de la técnica de Programación Dinámica para la resolución de problemas algorítmicos. Presentación de algoritmos clásicos que utilizan esta técnica.

Tema 7 Algoritmos voraces. Definición de la técnica para diseñar algoritmos voraces para la resolución de problemas algorítmicos. Presentación de algoritmos clásicos que utilizan esta técnica.

Tema 8 Algoritmos sobre grafos. Resolución de problemas formalizados sobre grafos. Conectividad. Caminos mínimos. Árboles de recubrimiento mínimos

Tema 9 Algoritmos de vuelta atrás y de ramificación y poda Definición de las técnicas. Presentación de algoritmos clásicos que utilizan estas técnicas.

A lo largo del curso el estudiante realizará diversas pruebas puntuables tanto como actividades presenciales (compleción de cuestionarios y realización de parciales) como no presenciales (entregas de ejercicios de implementación).



Mediante los cuestionarios se evaluarán las 3 primeras competencias y con los parciales, principalmente, la cuarta. Los ejercicios de implementación y análisis experimental facilitarán al alumno la comprensión y asimilación de las técnicas de diseño de algoritmos trabajadas en la asignatura. Habrá un documento modelo, como ejemplo para la entrega de estos ejercicios.



Las pruebas se desarrollarán a lo largo de curso, se realizarán de forma autónoma por parte del estudiante y con feedback continuo por parte del profesor.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • Written test to be taken (%): 50
  • Team projects (problem solving, project design)) (%): 50

La asignatura tiene dos modos de evaluación: la evaluación final (o de conjunto) y la evaluación continua. La evaluación continua, a la que el alumnado podrá acogerse voluntariamente, se oferta exclusivamente a los estudiantes que puedan realizar el seguimiento continuo de la asignatura en el marco establecido de dedicación y asistencia a las actividades presenciales.



La preinscripción en el modo de evaluación continua se realizará en las fechas establecidas. La preinscripción pasará a ser definitiva tras la confirmación de la solicitud por parte del estudiante en las fechas que se establezcan (hacia la semana 12 con un 60%-80% del peso de la evaluación ya cursado) y previa verificación del rendimiento parcial por parte del profesorado.

Se realizará una prueba escrita sobre el 100% del contenido de la asignatura.

http://ocw.ehu.es/ensenanzas-tecnicas/diseno-de-algoritmos/Course_listing

Basic bibliography

Apuntes y notas editados por el profesorado.

Arruabarrena, Rosa: Algoritmika. Udako Euskal Unibertsitatea (1997).

Cormen T.H, Leiserson C.E,, Rivest R.L. y Stein C: Introduction to Algorithms (second edition) The MIT Press (2001)

In-depth bibliography

Brassard, G. y Bratley; P.: "Fundamentals of algorithmics". Prentice Hall (1997). Horowitz E., Sahni S. y Rajasekaran S.: ``Computer Algorithms". Computer Science Press (1998

Web addresses

http://ocw.ehu.es/ensenanzas-tecnicas/diseno-de-algoritmos/Course_listing http://www.cs.sunysb.edu/~algorith/video-lectures/ http://www.itl.nist.gov/div897/sqg/dads/ http://olympiads.win.tue.nl/ioi/study/books.html