Denominación de la asignatura: Algoritmia y Complejidad
Pregrado al que pertenece: Pregrado en Ingeniería Informática
Créditos ECTS: 3
Semestre en el que se imparte: Segundo semestre

Presentación

Existen múltiples ramas de la ingeniería informática para las que el ingeniero necesita identificar un algoritmo o estructura de datos que resuelva de forma eficaz el problema que pretende abordar. Un ingeniero familiarizado con los algoritmos clásicos tendrá mayor probabilidad de éxito a la hora de encontrar un algoritmo novedoso para el problema donde intenta innovar, ya que le resultará más fácil diseñar una modificación de uno o más de los principios e ideas en los que se basan estos algoritmos.

Por ello, es necesario familiarizar desde el primer curso al estudiante con las técnicas generales de diseño de algoritmos. En esta asignatura se introducen los principales algoritmos y estructuras de datos que existen en la literatura específica y sirve como base para posteriores asignaturas donde se profundiza en conocer técnicas más modernas y avanzadas.

No solo es necesario que el estudiante sepa reconocer algoritmos eficaces, sino que también sepa elegir los algoritmos más eficientes para cada situación. Esto implica el saber analizar y medir la complejidad de un algoritmo, saber identificar posibles cuellos de botella y prevenir congestiones que retarden la ejecución de su programa. Para ello, la asignatura también enseña a determinar la cantidad de recursos (temporales y de memoria) necesarios para ejecutar un algoritmo, así como a clasificar los algoritmos de acuerdo a su complejidad computacional.

Tema 1. Estrategias de diseño de algoritmos

  • ¿Cómo estudiar este tema?
  • Estrategias de diseño de algoritmos
  • Recursividad
  • Divide y conquista
  • Programación dinámica
  • Algoritmos ávidos (greedy algorithms)
  • Método del retroceso (backtracking)
  • Ramificación y poda (branch and bound)

Tema 2. Eficiencia de algoritmos

  • ¿Cómo estudiar este tema?
  • Medidas de eficiencia
  • Medir el tamaño de la entrada
  • Medir el tiempo de ejecución
  • Caso peor, mejor y medio

Tema 3. Análisis de algoritmos

  • ¿Cómo estudiar este tema?
  • Notación asintótica
  • Análisis matemático de algoritmos no recursivos
  • Análisis matemático de algoritmos recursivos
  • Análisis empírico de algoritmos

Tema 4. Algoritmos de ordenación

  • ¿Cómo estudiar este tema?
  • Concepto de ordenación
  • Ordenación de la burbuja
  • Ordenación por selección
  • Ordenación por inserción
  • Ordenación por mezcla (mergesort)
  • Ordenación rápida (quicksort)

Tema 5. Listas enlazadas

  • ¿Cómo estudiar este tema?
  • Estructuras de datos dinámicas
  • Punteros
  • Listas enlazadas
  • Otros tipos de listas

Tema 6. Pilas y colas

  • ¿Cómo estudiar este tema?
  • Tipos abstractos de datos
  • Pilas
  • Colas

Tema 7. Árboles

  • ¿Cómo estudiar este tema?
  • Concepto de árbol
  • Árboles binarios
  • Árboles binarios ordenados
  • Árboles binarios balanceados

Tema 8. Heaps y colas de prioridad

  • ¿Cómo estudiar este tema?
  • Heaps
  • Heapsort
  • Colas de prioridad

Tema 9. Grafos

  • ¿Cómo estudiar este tema?
  • Representación
  • Recorrido en anchura
  • Recorrido en profundidad
  • Ordenación topológica

Tema 10. Búsqueda de caminos mínimos

  • ¿Cómo estudiar este tema?
  • El problema del camino mínimo
  • Arcos negativos y ciclos
  • Algoritmo de Dijkstra

Tema 11. Tablas hash

  • ¿Cómo estudiar este tema?
  • Introducción
  • Prueba lineal
  • Funciones hash y clustering
  • Encadenamiento separado

Tema 12. Problemas NP

  • ¿Cómo estudiar este tema?
  • Problemas P
  • Problemas NP
  • Problemas NP-completos

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
  • Trabajo final

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

Tema 1

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 57-94). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 2

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 15-17). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 3

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 17-31). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 4

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 97-119). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 5

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 171-199). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 6

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 221-249). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 7

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 287-324). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 8

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 243-249). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 9

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 369-374). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 10

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 397-401). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 11

  • Joyanes, L. et al. (2005). Estructuras de datos en C (pp. 271-274). Madrid: McGraw-Hill.
    El libro está disponible en el aula virtual de UNIR.

Tema 12

  • Ziviani, N. (2007). Diseño de algoritmos con Implementaciones en Pascal y C (pp. 341-366). Valladolid: Paraninfo.
    El libro está disponible en el aula virtual de UNIR.

Bibliografía complementaria

  • Aho, A. V. y Ullman, J. D. (1983). Data Structures and Algorithms. Addison-Wesley.
  • Andrej Bogdanov, L. T. (2006). Average-Case Complexity. Now Publishers Inc.
  • Arova, S. y Barak B. (2009) Computational Complexity. A Modern Approach. Cambridge: Cambridge Press.
  • Cairó, O. y Guardati, S. (2006). Estructuras de datos, 3ª edición. Madrid: McGraw Hill.
  • Fortnow Lance. (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Nueva Jersey: Princeton University Press.
  • Ivor Horton. (2014). Beginning C++. Apress.
  • Leiserson, C., Rivest, R. y Stein, C. (2009). Introduction to Algorithms, 3rd edition. Massachusetts: MIT Press.
  • Levitin A. (2011). Introduction to the Design and Analysis of Algorithms, 3rd edition. Addison-Wesley.
  • Necaise, R. D. (2010). Data Structures and Algorithms Using Python. Wiley.
  • Villalobos S. Jorge A. (1996). Diseño y manejo de estructuras de datos en C. McGraw-Hill.
  • West, D. (2000). Introduction to Graph Theory. Pearson.

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 (40% de la nota final).
  • Evaluación final (60% de la nota final).
Sistema de evaluación Ponderación
Participación del estudiante (sesiones, foros, tutorías) 5%
Trabajos, proyectos, laboratorios/talleres y casos 30%
Test de autoevaluación 5%
Examen final 20%
Trabajo final 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 de Lo que necesitas saber antes de empezar. 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 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 las lecturas que se te indican en el tema. Esto te ayudará a hacerte una idea del contenido más importante del tema y de cuáles son los aspectos fundamentales. Consulta, además, las otras secciones del tema que contienen material complementario (Lecturas recomendadas y Otros recursos).
  5. Dedica tiempo al trabajo práctico (sección Actividades). En la programación semanal te detallamos cuáles son las actividades correspondientes a cada semana.
  6. Te recomendamos que participes en los eventos del curso (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 de Lo que necesitas saber antes de empezar 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: Lecturas obligatorias, Lecturas recomendadas, Otros recursos y Actividades.

Recuerda que en el aula virtual de Lo que necesitas saber antes de empezar puedes consultar el funcionamiento de las distintas herramientas del Aula virtual: Correo, Foro, Envío de actividades, etc.

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 tutor personal.
  • Recuerda que no estás solo: consulta todas tus dudas con tu profesor-tutor utilizando el correo electrónico. 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. El intercambio de opiniones, materiales e ideas nos enriquece a todos.
  • Y ¡recuerda!, estás estudiando con metodología on line: tu esfuerzo y constancia son imprescindibles para conseguir buenos resultados. ¡No dejes todo para el último día!