Última revisión realizada: 23/05/2022
Denominación de la asignatura |
Diseño Avanzado de Algoritmos |
| Grado al que pertenece |
Grado en Ingeniería Informática |
| Créditos ECTS |
6 |
| Curso y cuatrimestre en el que se imparte |
Primer cuatrimestre |
| Materia |
Programación y Algoritmia III |
| Carácter de la asignatura | Optativa |
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.Competencias
Competencias básicas
- CB1: Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio.
- CB2: Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio.
- CB3: Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética.
- CB4: Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado.
- CB5: Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía.
Competencias generales
- CG09. Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática.
- CB-01. Capacidad para la resolución de los problemas matemáticos que puedan plantearse en la ingeniería. Aptitud para aplicar los conocimientos sobre: álgebra lineal; cálculo diferencial e integral; métodos numéricos; algorítmicos numéricos; estadísticos y optimización.
- CB-03. Capacidad para comprender y dominar los conceptos básicos de matemática discreta, lógica, algorítmica y complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería.
- CB-06.Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos.
Competencias específicas
- CC-03. Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.
Competencias transversales
- CT1: Capacidad de innovación y flexibilidad en entornos nuevos de aprendizaje como es la enseñanza on-line.
- CT2: Conocer, y utilizar con habilidad, los mecanismos básicos de uso de comunicación bidireccional entre profesores y alumnos, foros, chats, etc.
- CT3: Utilizar las herramientas para presentar, producir y comprender la información que les permita transformarla en conocimiento.
Contenidos
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. Optimización multiobjetivo
Representación y modelización
Fórmula ponderada
Aproximación lexicográfica
Fronteras de Pareto
Tema 9. Algoritmos de optimización con campos aleatorios
Introducción
Modelización del campo aleatorio
Estimación de parámetros
Tema 10. Resolución numérica de ecuaciones no lineales
Introducción
El método de la bisección
El método de Newton-Raphson
El método de la secante
Tema 11. Diferenciación e integración
Introducción
Diferenciación numérica
Integración numérica
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
Metodología
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:
- Trabajos y Lecturas. Se trata de actividades de diferentes tipos: reflexión, análisis de casos, prácticas, etc. Además de análisis de textos relacionados con diferentes temas de la asignatura.
- Participación en eventos. Son eventos programados todas las semanas del cuatrimestre: sesiones presenciales virtuales, foros de debate, test.
- Laboratorios. Actividad práctica que se realiza en tiempo real e interactuando con otros alumnos. En el laboratorio los estudiantes tendrán que desarrollar los ejercicios propuestos en un entorno de simulación online. Los estudiantes contarán en todo momento con el apoyo de un tutor de laboratorio, que ayudará al
alumno a desarrollar su actividad. El tutor de laboratorio podrá asignar grupos de alumnos para que, de forma
colaborativa, alcancen los resultados solicitados. Este tipo de actividad posee un peso considerable en la
evaluación continua del alumno, por lo que, a pesar de no ser obligatoria su realización, se recomienda firmemente la participación en los mismos.
En la programación semanal puedes consultar cuáles son las actividades concretas que tienes que realizar en esta asignatura.
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 presencial u online
Las horas de dedicación a cada actividad se detallan en la siguiente tabla:
ACTIVIDADES FORMATIVAS |
HORAS |
% PRESENCIAL |
| Sesiones presenciales virtuales | 15 |
100% |
| Recursos didácticos audiovisuales | 6 |
0 |
| Estudio del material básico | 50 |
0 |
| Lectura del material complementario | 25 |
0 |
| Trabajos, casos prácticos, test | 17 |
0 |
| Prácticas de laboratorios virtuales | 12 |
16,7% |
| Tutorías | 16 |
30% |
| Trabajo colaborativo | 7 |
0 |
| Realización de examen final presencial | 2 |
100% |
| Total | 150 |
Bibliografía
Bibliografía básica
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 el siguiente manual 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.
Evaluación y calificación
El sistema de calificación se basa en la siguiente escala numérica:
0 - 4, 9 |
Suspenso |
(SS) |
5,0 - 6,9 |
Aprobado |
(AP) |
7,0 - 8,9 |
Notable |
(NT) |
9,0 - 10 |
Sobresaliente |
(SB) |
La calificación se compone de dos partes principales:
El examen se realiza al final del cuatrimestre y es de carácter PRESENCIAL U ONLINE y OBLIGATORIO. Supone el 60% de la calificación final y para que la nota obtenida en este examen se sume a la nota final, es obligatorio APROBARLO.
La evaluación continua supone el 40% de la calificación final. Este 40% de la nota final se compone de las calificaciones obtenidas en las diferentes actividades formativas llevadas a cabo durante el cuatrimestre.
Ten en cuenta que la suma de las puntuaciones de las actividades de la evaluación continua permite que realices las que prefieras hasta conseguir el máximo puntuable mencionado en la programación semanal. En ella se detalla la calificación máxima de cada actividad o evento concreto puntuables.
Para aprobar la asignatura será necesario aprobar cada una de las partes.
El sistema de evaluación de la asignatura es el siguiente:
SISTEMA DE EVALUACIÓN |
PONDERACIÓN MIN. |
PONDERACIÓN MÁX. |
| Prueba de evaluación final | 60% |
60% |
| Evaluación de prácticas de laboratorios virtuales | 0% |
40% |
| Resolución de trabajos, proyectos y casos | 0% |
40% |
| Test de autoevaluación | 0% |
20% |
| Participación en foros y otros medios participativos | 0% |
40% |
Profesorado
Andrés Gaspar Castillo Sanz
Formación: Doctor en Ingeniería del Software por la Universidad Pontificia de Salamanca. Licenciado en Ciencias Físicas y Sociología.
Experiencia: Profesor Universitario desde hace veinticinco años. Investigador en temas de salud en el Hospital Niño Jesús y en temas sociales con Cáritas y otras ONGs.
Líneas de investigación: En el terreno de Ingeniería Informática ha investigado y dirigido varias tesis doctorales y publicaciones en torno a los sistemas multiagentes, la inteligencia artificial y la seguridad. En el ámbito de la investigación social sus aportaciones se centran en los movimientos sociales, el análisis e intervención frente a la pobreza y la exclusión social y las metodologías de la educación no formal.
Orientaciones para el estudio
Obviamente, al tratarse de formación on-line 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:
- 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 Grado. 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 personal con tu profesor-tutor.
- Observa la programación semanal. Allí te indicamos qué parte del temario debes trabajar cada semana.
- 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.
- 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. Lee siempre el primer apartado, ¿Cómo estudiar este tema?, porque allí te especificamos qué material tienes que estudiar. Consulta, además, las secciones del tema que contienen material complementario (Lo + recomendado y + Información).
- 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.
- 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 profesor-tutor te informarán de las novedades de la asignatura.
|
Ten en cuenta estos consejos…
|