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
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

Generales

  • 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.

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.

Contenidos

Tema 1. Principios de computabilidad
Máquinas de Turing
Tesis de Church-Turing
NP-Completitud

Tema 2. Tratamiento de la NP-Completitud
Búsqueda inteligente: vuelta atrás
Ramificación y poda

Tema 3. Análisis de algoritmos recursivos
Planteamiento y resolución de ecuaciones de recurrencia homogéneas e inhomogéneas.
Ejemplos de ecuaciones de recurrencia

Tema 4. Análisis amortizado
El análisis agregado
El método de contabilidad
El método del potencial

Tema 5. Verificación formal de programas
Especificación de abstracciones funcionales
El lenguaje de la lógica de primer orden
El sistema formal de Hoare

Tema 6. Verificación de programas iterativos
Reglas del sistema formal de Hoare
Concepto de invariante de iteraciones

Tema 7. Algoritmo: divide y vence
Introducción
Ejemplos de algoritmos: divide y vence.

Tema 8. Algoritmo voraces
Introducción
Ejemplos de algoritmos voraces

Tema 9. Programación dinámica
Introducción
Ejemplos de algoritmos de programación dinámica

Tema 10. Optimización combinatoria
Introducción
Ejemplos de búsqueda de soluciones

Tema 11. Algoritmos de aleatorización
Introducción
Ejemplos de algoritmos de aleatorización

Tema 12. Algoritmos paralelos
Introducción
Ejemplos de algoritmos paralelos


Metodología

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.

Descarga el pdf de la programación

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

  • Estudio personal
  • Tutorías
  • Examen final presencial

Puedes personalizar tu plan de trabajo seleccionando aquel tipo de actividad formativa que se ajuste mejor a tu perfil. El profesor-tutor te ayudará y aconsejará en el proceso de elaboración de tu plan de trabajo. Y siempre estará disponible para orientarte durante el curso.

Recomendaciones técnicas

Metodología

Para la correcta participación de los alumnos en las diferentes actividades propuestas en la asignatura se recomienda disponer de un ordenador con las siguientes especificaciones mínimas recomendadas:

  • 4 GB de RAM
  • Conexión a Internet superior a 6 Mbit/s
  • Cámara web
  • Micrófono
  • Altavoces o auriculares
  • Sistema operativo Windows o Mac OS (algunas actividades pueden presentar dificultades sobre Linux. En esta circunstancia se recomienda consultar con el profesor de la asignatura)
  • Acceso de administrador al sistema (es necesario la instalación de programas, emuladores, compiladores…)
  • Navegador web Netscape, Chrome, Safari o Firefox actualizado (versiones no actualizadas pueden presentar problemas funcionales y/o de seguridad)

Bibliografía

Bibliografía básica

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 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

Kaldewaij, A. (1990). Programming: the derivation of algorithms. New Jersey: Prentice Hall.

Horowitz, E. & Sahni, S. (1984). Fundamentals of computer algorithms. Nueva Delhi: Galgotia Publications.

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é.

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

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:

calificación

El examen se realiza al final del cuatrimestre y es de carácter PRESENCIAL y OBLIGATORIO. Supone el 60% de la calificación final (6 puntos sobre 10) y para que la nota obtenida en este examen se sume a la nota final, es obligatorio APROBARLO (es decir, obtener 3 puntos de los 6 totales del examen).

La evaluación continua supone el 40% de la calificación final (es decir, 4 puntos de los 10 máximos). 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 es de 15 puntos. Así, puedes hacer las que prefieras hasta conseguir un máximo de 10 puntos (que es la calificación máxima que se puede obtener en la evaluación continua). En la programación semanal de la asignatura, se detalla la calificación máxima de cada actividad o evento concreto puntuables.

Ten en cuenta…
Si quieres presentarte sólo al examen final, tendrás que obtener una calificación de 5 puntos sobre 6 para aprobar la asignatura.

Orientaciones para el estudio

Orientación 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:

  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 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.
  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. 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).
  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 profesor-tutor te informarán de las novedades de la asignatura.
En el aula virtual del Grado 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: Ideas clave, Lo + recomendado, + Información, Actividades y Test.

Ten en cuenta estos consejos…

  • Sea cual sea tu plan de estudio, accede periódicamente al aula virtual, ya que de esta forma estarás al día de las novedades del curso y en contacto con tu profesor y con tu profesor tutor.
  • Recuerda que no estás solo: consulta todas tus dudas con tu profesor-tutor utilizando el correo electrónico. Si asistes a las sesiones presenciales virtuales también podrás preguntar al profesor sobre el contenido del tema. Además, siempre puedes consultar tus dudas sobre el temario en los foros que encontrarás en cada asignatura (Pregúntale al profesor).
  • ¡Participa! Siempre que te sea posible accede a los foros de debate y asiste a las sesiones presenciales virtuales. El intercambio de opiniones, materiales e ideas nos enriquece a todos.
  • Y ¡recuerda!, estás estudiando con metodología online: tu esfuerzo y constancia son imprescindibles para conseguir buenos resultados. ¡No dejes todo para el último día!