Consulta de Guías Docentes

Academic Year/course: 2022/23

439 - Bachelor's Degree in Informatics Engineering

30232 - Algorithms for Difficult Problems

Syllabus Information

Academic Year:
30232 - Algorithms for Difficult Problems
Faculty / School:
110 - Escuela de Ingeniería y Arquitectura
439 - Bachelor's Degree in Informatics Engineering
First semester
Subject Type:

1. General information

1.1. Aims of the course

The course and its expected results meet the following approaches and objectives:

In this course the students will improve their ability to design and develop algorithms focusing on probabilistic, approximate and heuristic techniques. Students will learn to recognize problems for which the solution uses these techniques, to design algorithms that use them, and to justify the correctness and efficiency of those algorithms.

These approaches and objectives are aligned with the following Sustainable Development Goals (SDGs) of the 2030 Agenda of United Nations (, in such a way that the acquisition of the  course learning results provides training and competence to contribute to some extent to its achievement:

  • Goal 8: Decent work and economic growth. Target 8.4 Improved production and efficient and respectful consumption.

1.2. Context and importance of this course in the degree

The Computer Science specialization covers a wide range of concepts, from the theoretical and algorithmic foundations to the forefront of developments in bioinformatics, robotics, computer vision, video games, and other interesting areas. Algorithms for difficult problems is the second of the courses of the specialization and is intended to complement the course of Basic algorithms with popular probabilistic algorithms and use of heuristics, among other.

1.3. Recommendations to take this course

Interest and effort are required, in addition to the knowledge acquired in previous couses of mathematics, programming, data structures and algorithms, computer theory, and basic algorithms.

2. Learning goals

2.1. Competences

After passing the course, students will be more competent to ...


1. Combine general knowledge and specialized engineering to generate innovative and competitive proposals for professional activity.
2. Solve problems and make decisions with initiative, creativity and critical thinking.
3. Communicate and transmit knowledge, skills and abilities in Castilian and English.
4. Use the techniques, skills and tools necessary for engineering practice thereof.
5. Learn continuously and develop independent learning strategies.
6. Apply the information and communications technology in Engineering.
7. Have a thorough understanding of fundamental principles and models of computation and know how to apply them to interpret, select, assess, model, and create new concepts, theories, uses and technological developments related to computer science.
8. Assess the computational complexity of a problem, knowing algorithmic strategies that can lead to resolution and recommend, develop and implement one that guarantees the best performance according to the requirements.
9. Know the fundamentals, paradigms and own techniques of intelligent systems and analyze, design and build systems, services and applications that use these techniques in any scope.

2.2. Learning goals

The student, after passing this course, achieves the following results ...

1. He/she knows the inexact computing models and is able to select the right one and use it for the modeling of heterogeneous application domains.
2. He/she is able to identify NP-hard problems.
3. He/she knows probabilistic, approximate and heuristic algorithmic techniques for NP-hard problems.
4. He/she can identify the most relevant components of a problem and select the most appropriate approximate technique to solve it, as well as give the reasons for his/her choice.
5. He/she knows how to compare problems and use this comparison to solve a problem from an efficient solution of another one.
6. He/she knows how to reason about the error rate and efficiency of approximate and probabilistic algorithms.
7. He/she knows how to apply analysis of amortized efficiency to advanced data structures.
8. He/she has the ability to work in a group, identify group goals, map out a work plan to achieve them, recognize the different roles within a team and is committed to the assigned tasks.
9. He/she can manage independent learning and development including management and organization time.
10. He/she appreciates the need for lifelong learning.

2.3. Importance of learning goals

Difficult problems from the computing point of view are usually identified with NP-hard problems that are studied in this course and cover interesting problems in all areas of knowledge. These are problems for which the usual algorithmic strategies are very inefficient, or even fail to provide the desired solution. The inexact algorithmic techniques are suitable for many of these problems and allow us to reflect useful insights for building algorithms.

3. Assessment (1st and 2nd call)

3.1. Assessment tasks (description of tasks, marking system and assessment criteria)

The student must demonstrate that he has achieved the intended learning outcomes through the following evaluation activities


Recommended option (progressive release from final exams):

Practical part:
Laboratory Practice (Group) during the semester: 20%.
Part of theory and problems:
Individual exercises during the semester: 20%.
intermediate written test: 30%.
Final exam (performed only in part): 30%.

Option based solely on final exams:

Practical part:
(Individual) programming test: 20%.
Part of theory and problems:
Final exam (in full): 80%.


Recommended option (progressive release of final exams):

  • Throughout the semester practical programming work will be proposed and must be solved in the laboratory. For this purpose teams will be formed by a certain number of students to be fixed at the beginning of the course. The papers presented by the students will be graded with a quantitative rating from 0 to 10. To obtain those grades programs will be assessed according to specifications, the quality of their design and presentation, proper application of the methods of resolution, time spent, and the ability of each team member to explain and justify the design done. Students who have met the deadlines set for the programming lab work, and have demonstrated in them a level of achievement and quality of adequate results, will obtain a grade in the practical laboratory programming part, weighing 20% of the final grade for the course.
  • In addition, throughout the semester homework sheets for individual work will be published, from which students may submit, no later than the date specified in each sheet, a certain number of exercise solutions to be set at the beginning of the course. The exercises presented by the students will be graded with a quantitative grade of 0 to 10. IMPORTANT NOTE: Before submitting an exercise solution among those proposed in a sheet the student must inform the teacher, selecting the exercise in moodle or as otherwise indicated, and wait for that teacher authorizing the carrying out of the exercise. Students who have met the deadlines set for these homework exercises will get the corresponding "individual work exercises" mark, weighing 20% of the final grade for the course.
  •  At about half semester there will be an intermediate written test consisting of individual solution for 50 minutes of an exercise proposed by the teacher. The intermediate written test will be graded with a quantitative rating from 0 to 10. Students who have completed the intermediate written test, will obtain the grade "intermediate written test", weighing 30% ​of the final grade for the course.
  • In the written exam  the student must solve problems similar to the weekly exercises proposed during the semester and to the problems in the intermediate written test, he must also answer conceptual questions and provide solution to exercises that prove his achievement of the learning results required in the course. Students who choose the "progressive release of final exams" option will be exempt from part of the written exam and must take only a mandatory part of the exam. The grade obtained in this mandatory part of the exam weighs 30% of the final grade for the course.

Option based solely on final exams (global evaluation):

The global evaluation of the course consists of two parts:

  • Individual programming test. In each call a practical laboratory programming test will be given, which will propose the student exercises similar to those made in the lab classes or in class. The grade obtained weighs 20% of the final grade for the course.
  • In the written exam  the student must solve problems similar to the weekly exercises proposed during the semester and to the problems in the intermediate written test, he must also answer conceptual questions and provide solution to exercises that prove his achievement of the learning results required in the course. Students who choose the "Option based solely on final exams" should take the written exam in full. The grade obtained in this written exam in full weighs 80% of the final grade for the course.

4. Methodology, learning tasks, syllabus and resources

4.1. Methodological overview

The methodology followed in this course is oriented towards the achievement of the learning objectives. A wide range of teaching and learning tasks are implemented such as:

  • Learning concepts and methodologies for the design and implementation of correct and efficient algorithms through lectures, in which student participation is encouraged.
  • The application of such knowledge to the design and analysis of algorithms and programs in the classes of problems. In these classes, students will play an active role in the discussion and resolution of problems.
  • Teamwork developed to address the lab practical work of the course, the result is reflected in the delivery of suitably designed and documented programs, as well as the explanation and justification of the design made and decisions taken.
  • Continued work on the understanding that combines concepts, analysis and programming problems solving using "pencil and paper" and the set-up in some computer programming projects.
  • The study and continued work from the first day of class.

4.2. Learning tasks

The course includes the following learning tasks: 

  • 1 Classes taught in the classroom will develop the syllabus of the course.
  • 2 In the classes of problems the concepts and techniques presented in the course syllabus will be applied. Problems and exercises will be proposed beforehand and different solutions to these problems will be presented and discussed in class. Other exercises will also be proposed during the problems sessions to be solved during them, some of them individually and others to be worked in groups.
  • 3 Practical work takes place in a computer lab or personal computers of students at home. In these sessions, students will work in teams and perform a number of programming assignments directly related to the topics studied in the course. For this, a series of tasks or programming exercises will be proposed for the students to solve in groups and delivered within the time limits fixed in each case.

4.3. Syllabus

The course will address the following topics: 

  • 1. Introduction. The NP-hard problems. Optimization problems.
  • 2. Approximate algorithms. Concept. Algorithm design. Guarantees and limits.
  • 3. Probabilistic Algorithms: Las Vegas and Monte Carlo. Analysis. Pseudorandom generators.
  • 4. Heuristics. Simulated annealing.
  • 5. Genetic algorithms.
  • 6. Amortized analysis. Advanced data structures.
  • 7. Specialized algorithms.

4.4. Course planning and calendar

Calendar of sessions and homework presentation

The general organization of this course is as follows.

  • Theoretical classes (2 hours per week)
  • Classes of problems (1 hour weekly)

Presentation of exercises and practical work:
The exercises proposed in class and lab work scheduled to be done in the laboratory or at home should be performed and presented when specified in each of them, and within deadlines to be announced in the description of each of the proposed works or well in advance.

Student Work

The time needed by the student to achieve the learning outcomes in this course is estimated in 150 hours distributed as follows:

  • 45 hours, approximately, of classroom activities (theoretical and problem-solving classes);
  • 45 hours of team programming work to develop proposed laboratory work programs;
  • 54 hours of effective personal study (study notes and texts, problem-solving, class preparation, program development);
  • 6 hours of a written final theory exam and practical examination in the laboratory.

The exam date and deadlines for homework and lab assignments will be announced well in advance on the website of the course.

Curso Académico: 2022/23

439 - Graduado en Ingeniería Informática

30232 - Algoritmia para problemas difíciles

Información del Plan Docente

Año académico:
30232 - Algoritmia para problemas difíciles
Centro académico:
110 - Escuela de Ingeniería y Arquitectura
439 - Graduado en Ingeniería Informática
Periodo de impartición:
Primer semestre
Clase de asignatura:

1. Información Básica

1.1. Objetivos de la asignatura

La asignatura y sus resultados previstos responden a los siguientes planteamientos y objetivos:

En esta asignatura el alumno mejorará su capacidad para diseñar y desarrollar algoritmos incidiendo en las técnicas probabilistas, aproximadas y heurísticas. El alumno aprenderá a reconocer los problemas en cuya solución se utilizan esas técnicas, a diseñar algoritmos que las utilicen y a justificar la corrección y eficiencia de los mismos.

Estos planteamientos y objetivos están alineados con los siguientes Objetivos de Desarrollo Sostenible (ODS) de la Agenda 2030 de Naciones Unidas (, de tal manera que la adquisición de los resultados de aprendizaje de la asignatura proporciona capacitación y competencia para contribuir en cierta medida a su logro:

  • Objetivo 8: Trabajo decente y crecimiento económico. Meta 8.4: Mejora de la producción y consumo eficiente y respetuoso.

1.2. Contexto y sentido de la asignatura en la titulación

La Especialidad en Computación abarca una amplia gama de conceptos, desde los fundamentos teóricos y algorítmicos hasta la vanguardia de los desarrollos en bioinformática, robótica, visión por computador, videojuegos, y otras áreas interesantes. Algoritmia para problemas difíciles es la segunda de las asignaturas de algoritmia de la Especialidad y pretende complementar la asignatura de Algoritmia Básica con los populares algoritmos probabilistas y el uso de heurísticas, entre otros.

1.3. Recomendaciones para cursar la asignatura

Interés y esfuerzo, además de los conocimientos adquiridos en las asignaturas previas de matemáticas, programación, estructuras de datos y algoritmos, teoría de la computación y algoritmia básica.

2. Competencias y resultados de aprendizaje

2.1. Competencias

Al superar la asignatura, el estudiante será más competente para...

  1. Combinar los conocimientos generalistas y los especializados de Ingeniería para generar propuestas innovadoras y competitivas en la actividad profesional.
  2. Resolver problemas y tomar decisiones con iniciativa, creatividad y razonamiento crítico.
  3. Comunicar y transmitir conocimientos, habilidades y destrezas en castellano y en inglés.
  4. Usar las técnicas, habilidades y herramientas de la Ingeniería necesarias para la práctica de la misma
  5. Aprender de forma continuada y desarrollar estrategias de aprendizaje autónomo.
  6. Aplicar las tecnologías de la información y las comunicaciones en la Ingeniería.
  7. Capacidad para tener un conocimiento profundo de los principios fundamentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática.
  8. 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.
  9. Capacidad para conocer los fundamentos, paradigmas y técnicas propias de los sistemas inteligentes y analizar, diseñar y construir sistemas, servicios y aplicaciones informáticas que utilicen dichas técnicas en cualquier ámbito de aplicación.

2.2. Resultados de aprendizaje

El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados...

  1. Conoce los modelos de computación no exactos y es capaz de seleccionar el adecuado y utilizarlo para el modelado de dominios de aplicación heterogéneos.
  2. Es capaz de identificar los problemas NP-difíciles.
  3. Conoce técnicas algorítmicas probabilistas, aproximadas y heurísticas para los mismos.
  4. Sabe identificar las componentes más relevantes de un problema y seleccionar la técnica aproximada más adecuada para el mismo, además de argumentar de forma razonada dicha elección.
  5. Sabe comparar problemas y utilizar dicha comparación para resolver un problema a partir de una solución eficiente de otro.
  6. Sabe razonar sobre la tasa de error y la eficiencia de los algoritmos aproximados y probabilistas.
  7. Sabe aplicar el análisis amortizado de eficiencia a estructuras de datos avanzadas.
  8. Puede trabajar en grupo, identificar objetivos del grupo, trazar un plan de trabajo para alcanzarlo, reconocer los diferentes papeles dentro de un equipo y asume el compromiso de las tareas encomendadas.
  9. Puede gestionar del autoaprendizaje y de desarrollo incluyendo el tiempo de gestión y de organización.
  10. Aprecia la necesidad del aprendizaje continuo.

2.3. Importancia de los resultados de aprendizaje

Los problemas difíciles a nivel informático se identifican habitualmente con los problemas NP-difíciles que se estudian en esta asignatura y abarcan problemas interesantes de todos los campos del saber. Se trata de problemas para los que las estrategias algorítmicas habituales resultan muy poco eficientes, o incluso no llegan a dar la solución buscada. Las técnicas algorítmicas no exactas son las adecuadas para muchos de estos problemas y permiten además reflejar intuiciones útiles en la construcción de algoritmos.

3. Evaluación

3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba

El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluacion


Opción recomendada (liberación progresiva de exámenes finales):

  1. Parte práctica:
    • Prácticas de laboratorio (en grupo) durante el cuatrimestre: 20%.
  2. Parte de teoría y problemas:
    • Ejercicios de trabajo individual durante el cuatrimestre: 20%.
    • Prueba escrita intermedia: 30%.
    • Examen final (realizar sólo una parte): 30%.

Opción basada exclusivamente en exámenes finales:

  1. Parte práctica:
    • Examen práctico (individual) de programación: 20%.
  2. Parte de teoría y problemas:
    • Examen final (realizarlo completo): 80%.


Opción recomendada (liberación progresiva de exámenes finales):

  • A lo largo del cuatrimestre se plantearán enunciados prácticos de programación que deberán ser resueltos en el laboratorio. Para ello se formarán equipos integrados por un número determinado de alumnos que se fijará al principio del curso. Los trabajos presentados por los alumnos se calificarán con una nota cuantitativa de 0 a 10. Para obtener dichas notas se valorará el funcionamiento de los programas según especificaciones, la calidad de su diseño y su presentación, la adecuada aplicación de los métodos de resolución, el tiempo empleado, así como la capacidad de cada uno de los integrantes del equipo para explicar y justificar el diseño realizado. Los alumnos que hayan cumplido con los plazos de entrega fijados para los trabajos prácticos de programación, y hayan demostrado en ellos un nivel de aprovechamiento y calidad de resultados adecuados, obtendrán la nota correspondiente a "Prácticas de laboratorio durante el cuatrimestre", ponderando un 20% de la nota final de la asignatura.
  • Además, a lo largo del cuatrimestre se plantearán hojas de ejercicios para trabajo individual de entre las que los alumnos podrán entregar, no más tarde de la fecha especificada en cada hoja, un número determinado que se fijará al principio del curso. Los ejercicios presentados por los alumnos se calificarán con una nota cuantitativa de 0 a 10. NOTA IMPORTANTE: Antes de realizar un ejercicio de entre los propuestos el alumno deberá informar al profesor, seleccionando dicho ejercicio en moodle o de la forma que se indique, y esperar a que dicho profesor autorice la realización del ejercicio. Los alumnos que hayan cumplido con los plazos de entrega fijados para los ejercicios de trabajo individual, obtendrán la nota correspondiente a "Ejercicios de trabajo individual durante el cuatrimestre", ponderando un 20% de la nota final de la asignatura.
  • En la mitad aproximada del cuatrimestre tendrá lugar una prueba escrita intermedia que consistirá en la realización individual durante 50 minutos de algún ejercicio propuesto por el profesor. La prueba escrita intermedia se calificará con una nota cuantitativa de 0 a 10. Los alumnos que hayan realizado la prueba escrita intermedia, obtendrán la nota correspondiente a "Prueba escrita intermedia", ponderando un 30% de la nota final de la asignatura.
  • En el Examen escrito deberán resolverse problemas de naturaleza similar a los ejercicios semanales propuestos durante el cuatrimestre, a los problemas planteados en la prueba escrita intermedia y, en su caso, responder preguntas conceptuales o resolver algún ejercicio en el que se demuestre haber logrado los resultados de aprendizaje requeridos en la asignatura. Los alumnos que opten por la opción "liberación progresiva de exámenes finales" serán exentos de realizar una parte del examen escrito, debiendo realizar sólo una parte obligatoria del examen. La calificación obtenida en dicha parte obligatoria del examen pondera un 30% de la nota final de la asignatura.

Opción basada exclusivamente en exámenes finales (Evaluación global):

La prueba global de evaluación de la asignatura consta de dos partes:

  • Examen práctico de programación individual. En cada convocatoria se realizará un examen práctico de programación, en el que se le plantearán al alumno ejercicios de naturaleza similar a los realizados en las prácticas o vistos en clase. La calificación obtenida pondera un 20% de la nota final de la asignatura.
  • Examen escrito en el que se deberán resolver problemas de naturaleza similar a los ejercicios semanales propuestos durante el cuatrimestre, a los problemas planteados en la prueba escrita intermedia y, en su caso, responder preguntas conceptuales o resolver algún ejercicio en el que se demuestre haber logrado los resultados de aprendizaje requeridos en la asignatura. Los alumnos que opten por la opción "basada exclusivamente en exámenes finales" deberán realizar el examen escrito completo. La calificación obtenida en dicho examen final completo pondera un 80% de la nota final de la asignatura.

4. Metodología, actividades de aprendizaje, programa y recursos

4.1. Presentación metodológica general

El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:

El estudio y trabajo continuado desde el primer día de clase.

El aprendizaje de conceptos y metodologías para el diseño e implementación de algoritmos correctos y eficientes a través de las clases magistrales, en las que se favorecerá la participación de los alumnos.

La aplicación de tales conocimientos al diseño y análisis de algoritmos y programas en las clases de problemas. En estas clases los alumnos desempeñarán un papel activo en la discusión y resolución de los problemas.

El trabajo en equipo desarrollado para resolver las prácticas de la asignatura, cuyo resultado se plasma en la entrega de programas  convenientemente diseñados y documentados, así como en la explicación y justificación del diseño realizado y decisiones adoptadas.

Un trabajo continuado en el que se conjugue la comprensión de conceptos, el análisis y la resolución de problemas de programación utilizando "lápiz y papel" y la puesta a punto en computador de algunos proyectos de programación.

4.2. Actividades de aprendizaje

El programa que se ofrece al estudiante para ayudarle a lograr los resultados previstos comprende las siguientes actividades...

  1. En las clases impartidas en el aula se desarrollará el temario de la asignatura.
  2. En las clases de problemas se resolverán problemas de aplicación de los conceptos y técnicas presentadas en el programa de la asignatura. Se propondrán problemas y ejercicios para ser resueltos antes de la clase de problemas en la que se presentarán y discutirán diferentes soluciones a dichos problemas. También se propondrán ejercicios durante la sesión de problemas para ser resueltos durante la misma, algunos de forma individual y otros para ser trabajados en grupo.
  3. El trabajo de prácticas se desarrolla en un laboratorio informático o bien en los computadores personales de los alumnos, en casa. En estas sesiones los alumnos deberán trabajar en equipo y realizar una serie de trabajos de programación directamente relacionados con los temas estudiados en la asignatura. Para ello se propondrán una serie de trabajos o ejercicios de programación para que los alumnos los resuelvan en grupo y los entreguen dentro de los plazos de tiempo que se fijen en cada caso.

4.3. Programa

  1. Introducción. Los problemas NP-difíciles. Los problemas de optimización.
  2. Algoritmos aproximados. Concepto. Diseño de algoritmos. Garantías y límites.
  3. Algoritmos probabilistas: Las Vegas y Montecarlo. Análisis. Generadores pseudoaleatorios.
  4. Heurísticas. Simulated annealing (templado simulado).
  5. Algoritmos genéticos.
  6. Análisis amortizado. Estructuras de datos avanzadas.
  7. Algoritmos especializados.

4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave

Calendario de sesiones presenciales y presentación de trabajos

La organización docente de la asignatura prevista es la siguiente:

  • Clases teóricas (2 horas semanales)
  • Clases de problemas (1 hora semanal)

Presentación de ejercicios y trabajos prácticos:

  • Los ejercicios propuestos en clase y los trabajos de programación a desarrollar en laboratorio o en casa deberán ser realizados y presentados de acuerdo a lo especificado para cada uno de ellos, y dentro de las fechas límite que se anunciarán en el enunciado de cada uno de los trabajos propuestos o con suficiente antelación.


Trabajo del estudiante

La dedicación del estudiante para alcanzar los resultados de aprendizaje en esta asignatura se estima en 150 horas distribuidas del siguiente modo:

  • 45 horas, aproximadamente, de actividades presenciales (clases teóricas y de problemas);
  • 45 horas de trabajo de programación en equipo para desarrollar los programas propuestos como trabajo de laboratorio;
  • 54 horas de estudio personal efectivo (estudio de apuntes y textos, resolución de problemas, preparación de clases, desarrollo de programas);
  • 6 horas de examen final de teoría escrito y de examen práctico en laboratorio.


El calendario de exámenes y las fechas de entrega de trabajos se anunciarán con suficiente antelación en la página web de la asignatura.