Presentación

Esta es una asignatura práctica en la que se van a aplicar a multitud de problemas de todo tipo las técnicas de diseño de algoritmos más utilizadas. Asimismo se aprenderá a verificar de forma certera si un programa en efecto cumple sus especificaciones.

El profundo cambio que ha supuesto en nuestro modo de vivir, no solamente en la informática y el tratamiento de la información, los algoritmos en los que se basa Google, basta para hacerse una idea de la importancia fundamental que tiene una asignatura como ésta.

En esta asignatura se va a profundizar en las técnicas de diseño de algoritmos, o si se quiere en las técnicas de resolución de problemas. No se va a centrar en un lenguaje de programación en concreto, aunque la posibilidad de implementar un algoritmo en una aplicación que pueda ser ejecutada en un ordenador, es fundamental para entender el funcionamiento y la eficiencia de los algoritmos que veamos.

Hablando de eficiencia, es un concepto fundamental a la hora de juzgar la bondad de los algoritmos. Evidentemente se pide que un algoritmo resuelve un problema dado, pero también se le pide que lo haga con los recursos adecuados de los que disponemos o de los que podemos disponer razonablemente. La tecnología de nuestros computadores avanza al parecer exponencialmente, pero al mismo tiempo la cantidad de datos que deseamos, no, que necesitamos procesar en el mismo tiempo crece a un ritmo siempre mayor.

Tema 1. Análisis de algoritmos recursivos

• Introducción
• Planteamiento y resolución de ecuaciones de recurrencia homogéneas y no homogéneas.
• Ejercicios de ecuaciones de recurrencia

Tema 2. Divide y conquista

• Introducción
• Descripción general de la estrategia
• Ejemplos de algoritmos: divide y conquista

Tema 3. Análisis amortizado

• Introducción
• El análisis agregado
• El método de contabilidad
• El método del potencial

Tema 4. Programación dinámica

• Introducción
• Características de la programación dinámica
• Ejemplos de algoritmos de programación dinámica

Tema 5. Algoritmos para problemas NP

• Introducción
• Vuelta atrás: backtracking
• Ramificación y poda

Tema 6. Optimización combinatoria

• Introducción
• Representación de problemas
• Optimización en 1D

Tema 7. Algoritmos de aleatorización

• Introducción
• Ejemplos de algoritmos de aleatorización
• El teorema Buffon
• Algoritmo de Monte Carlo
• Algoritmo Las Vegas

Tema 8. Búsqueda local y con candidatos

• Introducción
• Garcient ascent
• Hill climbing
• Simulated annealing
• Tabu search
• Búsqueda con candidatos

Tema 9. Verificación formal de programas

• Introducción
• Especificación de abstracciones funcionales
• El lenguaje de la lógica de primer orden
• El sistema formal de Hoare

Tema 10. Verificación de programas iterativos

• Introducción
• Reglas del sistema formal de Hoare
• Concepto de invariante de iteraciones

Tema 11. Métodos numéricos

• Introducción
• El método de la bisección
• El método de Newton Raphson
• El método de la secante

Tema 12. Algoritmos paralelos

• Introducción
• Operaciones binarias paralelas
• Operaciones paralelas con grafos
• Paralelismo en divide y vencerás
• Paralelismo en programación dinámica

Las actividades formativas de la asignatura se han elaborado con el objetivo de adaptar el proceso de aprendizaje a las diferentes capacidades, necesidades e intereses de los alumnos.

Las actividades formativas de esta asignatura son las siguientes:

• Casos prácticos. En la programación semanal, puedes consultar cuándo hacerlos y en el Aula virtual encontrarás toda la información sobre cómo desarrollarlos y cómo y cuándo entregarlos. 
  
• Participación en eventos. Son eventos programados todas las semanas del cuatrimestre: sesiones presenciales virtuales, foros de debate.

Descargar programación

Estas actividades formativas prácticas se completan, por supuesto, con estas otras:

• Estudio personal
• Tutorías. Las tutorías se pueden articular a través de diversas herramientas y medios. Durante el desarrollo de la asignatura, el profesor programa tutorías en días concretos para la resolución de dudas de índole estrictamente académico a través de las denominadas “sesiones de consultas”. Como complemento de estas sesiones se dispone también del foro “Pregúntale al profesor de la asignatura” a través del cual se articulan algunas preguntas de alumnos y las correspondientes respuestas en el que se tratan aspectos generales de la asignatura. Por la propia naturaleza de los medios de comunicación empleados, no existen horarios a los que deba ajustarse el alumno.
• Examen final online

Bibliografía básica

Recuerda que la bibliografía básica es imprescindible para el estudio de la asignatura. Cuando se indica que no está disponible en el aula virtual, tendrás que obtenerla por otros medios: librería UNIR, biblioteca...

Los textos necesarios para el estudio de la asignatura han sido elaborados por UNIR y están disponibles en formato digital para consulta, descarga e impresión en el aula virtual.

Además, en algunos temas deberás estudiar los siguientes manuales de la asignatura:

Brassard, P. B. & Bratley, T. (1997). Fundamentos de algoritmia. Madrid: Pearson.

Díaz de Ilarraza, A. y Lucio, F. (1990). Verificación de programas y metodología de la programación. Bilbao: Universidad del País Vasco.

Guerequeta, R. & Vallecillo, A. (1998). Técnicas de diseño de algoritmos. Málaga: Universidad de Málaga.

Navarro, G. (2012). Teoría de la computación. Chile: Universidad de Chile.

Vargas, L. E. (2010). Problemas y algoritmos. Autoedición: Etnassoft.

Bibliografía complementaria

• Erciyes, K. (2018). Guide to Graph Algorithms: Sequential, Parallel and Distributed. Nueva York: Springer.
• Horowitz, E. & Sahni, S. (1984). Fundamentals of computer algorithms. Nueva Delhi: Galgotia Publications.
• Kaldewaij, A. (1990). Programming: the derivation of algorithms. New Jersey: Prentice Hall.
• Knuth, D. E. (1980). Algoritmos fundamentales. Barcelona: Reverté.
• Knuth, D. E. (1986). Seminuméricos. Barcelona: Reverté.
• Knuth, D. E. (1987). Algoritmos combinatorios. Barcelona: Reverté.
• Knuth, D. E. (1987). Clasificación y búsqueda. Barcelona: Reverté.
• Riolo, R. y Worzel, B. (2018). Genetic Programming Theory and Practice. Nueva York: Springer.
• Sedgewick, R. (1995). Algoritmos en C++. Madrid: Ediciones Díaz de Santos.
• Wirth, N. (1986). Algoritmos + estructuras de datos. México: Ediciones Castillo.

El sistema de calificación se basa en la siguiente escala numérica:

0 - 5,9	Suspenso	(SS)
6 - 10	Aprobado	(AP)

• Escala de calificaciones. En las calificaciones definitivas el docente utilizará una escala numérica con un rango que va de cero (0) a diez (10), donde cero (0) es la nota más baja y diez (10) la más alta.
• Calificación reprobada. Una calificación total inferior a seis (6) en la suma de las actividades y el examen significará el suspenso de la materia.
• Evaluaciones parciales o continuas (60% de la nota final).
• Evaluación final (40% de la nota final).

Sistema de evaluación	PONDERACIÓN MIN-MAX
Participación del estudiante (sesiones y foros)	0%-60%
Trabajos (trabajos, laboratorios y casos prácticos)	0%-60%
Test de autoevaluación	0%-60%
Examen final online	40%-40%

Obviamente, al tratarse de formación online puedes organizar tu tiempo de estudio como desees, siempre y cuando vayas cumpliendo las fechas de entrega de actividades, trabajos y exámenes. Nosotros, para ayudarte, te proponemos los siguientes pasos:

1. Desde el Campus virtual podrás acceder al aula virtual de cada asignatura en la que estés matriculado y, además, al aula virtual del Curso de introducción al campus virtual. Aquí podrás consultar la documentación disponible sobre cómo se utilizan las herramientas del aula virtual y sobre cómo se organiza una asignatura en la UNIR y también podrás organizar tu plan de trabajo con tu tutor personal.
2. Observa la programación semanal. Allí te indicamos qué parte del temario debes trabajar cada semana.
3. Ya sabes qué trabajo tienes que hacer durante la semana. Accede ahora a la sección Temas del aula virtual. Allí encontrarás el material teórico y práctico del tema correspondiente a esa semana.
4. Comienza con la lectura de las Ideas clave del tema. Este resumen te ayudará a hacerte una idea del contenido más importante del tema y de cuáles son los aspectos fundamentales en los que te tendrás que fijar al estudiar el material básico. Consulta, además, las secciones del tema que contienen material complementario.
5. Dedica tiempo al trabajo práctico (sección Actividades y Test). En la programación semanal te detallamos cuáles son las actividades correspondientes a cada semana y qué calificación máxima puedes obtener con cada una de ellas.
6. Te recomendamos que participes en los eventos del curso (sesiones presenciales virtuales, foros de debate…). Para conocer la fecha concreta de celebración de los eventos debes consultar las herramientas de comunicación del aula vitual. Tu profesor y tu tutor personal te informarán de las novedades de la asignatura.

En el aula virtual del Curso de introducción al campus virtual encontrarás siempre disponible la documentación donde te explicamos cómo se estructuran los temas y qué podrás encontrar en cada una de sus secciones.

Recuerda que en el aula virtual del Curso de introducción al campus virtual puedes consultar el funcionamiento de las distintas herramientas del aula virtual: Correo, Foro, Sesiones presenciales virtuales, Envío de actividades, etc.