Denominación de la asignatura: Algoritmia y Complejidad
Grado al que pertenece: Grado en Ingeniería Informática
Créditos ECTS: 6
Curso y cuatrimestre en el que se imparte: Primer curso, segundo cuatrimestre
Carácter de la asignatura: Básico

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.

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

  • CG8: Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones.

Competencias específicas

  • CB04: Conocimientos básicos sobre el uso y programación de los ordenadores, sistemas operativos, bases de datos y programas informáticos con aplicación en ingeniería.
  • CB05: Conocimiento de la estructura, organización, funcionamiento e interconexión de los sistemas informáticos, los fundamentos de su programación, y su aplicación para la resolución de problemas propios de la ingeniería.

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.

Tema 1. Introducción a las estrategias de diseño de algoritmos

  • Introducción y objetivos
  • Recursividad
  • Divide y conquista
  • Otras estrategias

Tema 2. Eficiencia de los algoritmos

  • Introducción y objetivos
  • 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

  • Introducción y objetivos
  • Notación asintónica
  • Criterios de 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

  • Introducción y objetivos
  • Concepto de ordenación
  • Ordenación de la burbuja
  • Ordenación por selección
  • Ordenación por inserción
  • Ordenación por mezcla (merge_sort)
  • Ordenación rápida (quick_sort)

Tema 5. . Algoritmos con árboles

  • Introducción y objetivos
  • Concepto de árbol
  • Árboles binarios
  • Recorridos de árbol
  • Representar expresiones

Tema 6. Algoritmos con árboles ordenados y balanceados

  • Introducción y objetivos
  • Árboles binarios ordenados
  • Árboles binarios balanceados

Tema 7. Algoritmos con heaps

  • Introducción y objetivos
  • Los heaps
  • El algoritmo heapsort
  • Las colas de prioridad

Tema 8. Algoritmos con grafos

  • Introducción y objetivos
  • Representación
  • Recorrido en anchura
  • Recorrido en profundidad
  • Ordenación topológica

Tema 9. Algoritmos greedy

  • Introducción y objetivos
  • La estrategia greedy
  • Elementos de la estrategia greedy
  • Cambio de monedas
  • Problema del viajante
  • Problema de la mochila

Tema 10. Búsqueda de caminos mínimos

  • Introducción y objetivos
  • El problema del camino mínimo
  • Arcos negativos y ciclos
  • Algoritmo de Dijkstra

Tema 11. Algoritmos greedy sobre grafos

  • Introducción y objetivos
  • El árbol de recubrimiento mínimo
  • El algoritmo de Prim
  • El algoritmo de Kruskal
  • Análisis de complejidad

Tema 12. Backtracking

  • Introducción y objetivos
  • El backtracking
  • Técnicas alternativas

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. Se trata de actividades de diferentes tipos: reflexión, análisis de casos, prácticas, etc.
  • 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. Cada laboratorio contemplará varias opciones de asistencia que habrás de reservar por anticipado.
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 presencial

Las horas de dedicación a cada actividad se detallan en la siguiente tabla:

ACTIVIDADES FORMATIVAS HORAS POR ASIGNATURA % PRESENCIAL
Clases en directo 15 horas 100%
Recusos didácticos audiovisuales 6 horas 0
Estudio del material básico 50 horas 0
Lectura del material complementario 25 horas 0
Trabajos, casos prácticos, test 17 horas 0
Prácticas de laboratorios virtuales 12 horas 16,7%
Tutorías 16 horas 30%
Trabajo colaborativo 7 horas 0
Examen final presencial 2 horas 100%
Total 150 horas -

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. Madrid: McGraw-Hill.
Disponible en la Biblioteca Virtual de UNIR.

Guerequeta, R. y Vallecillo, A. (1998). Técnicas de diseño de algoritmos. Málaga: Servicio de Publicaciones de la Universidad de Málaga.
Disponible a través del aula virtual.

Temas 2 a 8

Joyanes, L. et al. (2005). Estructuras de datos en C. Madrid: McGraw-Hill.
Disponible en la Biblioteca Virtual de UNIR.

Tema 9

Guerequeta, R. y Vallecillo, A. (1998). Técnicas de diseño de algoritmos. Málaga: Servicio de Publicaciones de la Universidad de Málaga.
Disponible a través del aula virtual.

Tema 10

Joyanes, L. et al. (2005). Estructuras de datos en C. Madrid: McGraw-Hill.
Disponible en la Biblioteca Virtual de UNIR.

Temas 11 y 12

Guerequeta, R. y Vallecillo, A. (1998). Técnicas de diseño de algoritmos. Málaga: Servicio de Publicaciones de la Universidad de Málaga.
Disponible a través del aula virtual.

Bibliografía complementaria

  • Aho, A. V. y Ullman, J. D. (1983). Data Structures and Algorithms. Massachusetts: Addison-Wesley.
  • Arova, S. y Barak B. (2009). Computational Complexity. A Modern Approach. Cambridge: Cambridge University Press
  • Cairó, O. y Guardati, S. (2006). Estructuras de datos, 3.ª edición. Madrid: McGraw Hill.
  • Horowitz, E. y 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). Clasificación y búsqueda. Barcelona: Reverté.
  • Knuth, D. E. (1987). Algoritmos combinatorios. Barcelona: Reverté.
  • Leiserson, C., Rivest, R. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición. Massachusetts: MIT Press.
  • Levitin A. (2011). Introduction to the Design and Analysis of Algorithms, 3.ª edición. Addison-Wesley.
  • Necaise, R. D. (2010). Data Structures and Algorithms Using Python. Nueva York: John Wiley & Sons.
  • Sedgewick, R. (1995). Algoritmos en C++. Madrid: Ediciones Díaz de Santos.
  • West, D. (2000). Introduction to Graph Theory. Pearson.
  • 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 - 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 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 de la asignatura, se detalla la calificación máxima de cada actividad o evento concreto puntuables.

Sistema de evaluación Ponderación min - max
Prueba de evaluación final presencial 60% - 60%
Evaluación de prácticas de laboratorios virtuales 0% - 40%
Resolución de trabajos, proyectos y casos 0% - 40%
Participación en foros y otros medios participativos 0% - 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.

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 tutor personal 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!