Teaching Guides Query



Academic Year: 2020/21

439 - Bachelor's Degree in Informatics Engineering

30229 - Basic Algorithms


Teaching Plan Information

Academic Year:
2020/21
Subject:
30229 - Basic Algorithms
Faculty / School:
110 - Escuela de Ingeniería y Arquitectura
Degree:
439 - Bachelor's Degree in Informatics Engineering
ECTS:
6.0
Year:
3
Semester:
Second semester
Subject Type:
---
Module:
---

1. General information

2. Learning goals

3. Assessment (1st and 2nd call)

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

  1. Labs: Laboratory team work, 30%.
  2. Theory and problems:
    • Project: 25%.
    • Exam: 45%.

4. Methodology, learning tasks, syllabus and resources

4.1. Methodological overview

The learning process that is designed for this subject is based on the following:

  • The study and work continued since the first day of class.
  • 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 to address the practices of the subject; the results will be reflected in the delivery of suitably designed and documented programs, as well as the explanation and justification of design and decisions adopted.
  • Continued work combining the understanding of concepts, analysis and problem solving using "pencil and paper", and the set-up of computer programming projects.

4.2. Learning tasks

The course includes the following learning tasks: 

In some classes, the previously presented concepts and techniques will be used to solve problems.
The 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 jobs directly related to the topics studied in the course. A series of jobs or programming exercises will be proposed to be solved in groups and delivered within the fixed deadlines.

4.3. Syllabus

The course will address the following topics: 

  1. Introduction.
  2. Divide and conquer.
  3. Greedy algorithms.
  4. Dynamic programming.
  5. Backtracking.
  6. Branch and bound.
  7. Linear programming and reductions.

4.4. Course planning and calendar

Scheduled sessions and presentation of works.

The organization of the subject is as follows.

  • Theoretical classes (2 hours per week)
  • Problems classes (1 hour weekly)

Presentation of practical work:

Programming jobs should be performed and presented as specified for each of them, and within deadlines to be announced.

Student Work.

The dedication of the student to achieve the learning outcomes in this subject is estimated at 156 hours distributed as follows:

  • 45 hours, approximately, of classroom activities (theoretical and problem-solving classes);
  • 45 hours of programming teamwork;
  • 60 hours of effective personal study;
  • 6 hours for exams.

4.5. Bibliography and recommended resources

http://psfunizar7.unizar.es/br13/egAsignaturas.php?codigo=30229&Identificador=14680

[BB: Basic Bibliography / BC: Complementary Bibliography]

  • [BB] 1. Introduction to algorithms / Thomas H. Cormen ... [et al.] . - 3rd ed. Cambridge, Massachusetts ; London : MIT Press, cop. 2009
  • [BB] 2. Dasgupta, Sanjoy. Algorithms / Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani . Boston [etc.] : McGraw Hill Higher Education, cop. 2008
  • [BB] 3. Brassard, Gilles : Fundamentos de algoritmia / G. Brassard, T. Bratley ; traducción, Rafael García-Bermejo ; revisión técnica, Narciso Martí, Ricardo Peña, Luis Joyanes Aguilar . - 1ª ed. en español, reimp. Madrid [etc.] : Prentice Hall, 2008
  • [BC] 5. Parberry, I. Problems on Algorithms / I. Parberry and W. Gasarch. - 2nd ed. free book, 2002
  • [BC] Kleinberg, Jon. Algorithm design / Jon Kleinberg, Eva Tardos . Boston : Pearson/Addison-Wesley, cop. 2006


Curso Académico: 2020/21

439 - Graduado en Ingeniería Informática

30229 - Algoritmia básica


Información del Plan Docente

Año académico:
2020/21
Asignatura:
30229 - Algoritmia básica
Centro académico:
110 - Escuela de Ingeniería y Arquitectura
Titulación:
439 - Graduado en Ingeniería Informática
Créditos:
6.0
Curso:
3
Periodo de impartición:
Segundo semestre
Clase de asignatura:
---
Materia:
---

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 haciendo énfasis en la identificación y aplicación de los esquemas que puedan ser utilizables para obtener soluciones eficientes a una amplia gama de problemas. Se presentarán algunos de los esquemas algorítmicos fundamentales, como: dividir para vencer, voracidad, programación dinámica, búsqueda con retroceso, ramificación y poda, etc. El alumno aprenderá a reconocer los problemas que requieren este tipo de esquemas para su resolución y cómo aplicarlos.

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 básica es la primera de las asignaturas de la Especialidad y se centra en el diseño de algoritmos correctos y eficientes mediante el conocimiento y aplicación de un conjunto de esquemas reutilizables.

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 y teoría de la computación.

2. Competencias y resultados de aprendizaje

2.1. Competencias

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

Combinar los conocimientos generalistas y los especializados de Ingeniería para generar propuestas innovadoras y competitivas en la actividad profesional.

Resolver problemas y tomar decisiones con iniciativa, creatividad y razonamiento crítico.

Comunicar y transmitir conocimientos, habilidades y destrezas en castellano y en inglés.

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.

2.2. Resultados de aprendizaje

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

Conoce esquemas algorítmicos variados y problemas fundamentales que utilizan los mismos.

Sabe particularizar esquemas algorítmicos generales para resolver problemas.

Sabe identificar las componentes más relevantes de un problema y seleccionar la técnica algorítmica más adecuada para el mismo, además de argumentar de forma razonada dicha elección.

Sabe comparar problemas y utilizar dicha comparación para resolver un problema a partir de una solución eficiente de otro.

Sabe razonar sobre la corrección y eficiencia de los algoritmos avanzados que se utilizan.

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

Gestión del autoaprendizaje y de desarrollo incluyendo el tiempo de gestión y de organización.

Apreciar la necesidad del aprendizaje continuo.

2.3. Importancia de los resultados de aprendizaje

La Algoritmia se define como el estudio de los algoritmos. Cuando nos disponemos a resolver un problema, es posible que haya toda una gama de algoritmos disponibles. En este caso, es importante decidir cuál de ellos hay que utilizar. Dependiendo de nuestras prioridades y de los límites del equipo que esté disponible para nosotros, quizá necesitemos seleccionar el algoritmo que requiera menos tiempo, o el que utilice menos espacio, o el que sea más fácil de programar y así sucesivamente. La respuesta puede depender de muchos factores, tales como los números implicados, la forma en que se presenta el problema, o la velocidad y capacidad de almacenamiento del equipo de computación disponible. Quizás suceda que ninguno de los algoritmos disponibles sea totalmente adecuado, así que tendremos que diseñar un algoritmo nuevo por nuestros propios medios. La Algoritmia es la ciencia que nos permite evaluar el efecto de estos diferentes factores externos sobre los algoritmos disponibles, de tal modo que sea posible seleccionar el que más se ajuste a nuestras circunstancias particulares; también es la ciencia que nos indica la forma de diseñar un nuevo algoritmo para una tarea concreta.

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 evaluación

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.

La presentación y defensa de trabajos prácticos de programación se valorará con una calificación de prácticas que ponderará con un 30% de la nota final de la asignatura.

Evaluación global

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

  • Parte práctica. Presentación de trabajos prácticos de programación en los que se obtendrá una calificación de prácticas que ponderará un 30% de la nota final de la asignatura.
  • Proyecto. Entrega de un trabajo conceptual y práctico sobre el tema de programación lineal y reducciones cuya evaluación ponderará un 25% de la nota final de la asignatura.
  • Examen escrito en el que se deberán resolver problemas de naturaleza similar a los planteados en clase sobre los temas de dividir para vencer, algoritmos voraces y programación dinámica. La calificación obtenida pondera un 45% 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, equipos integrados como máximo por dos alumnos, y cuyo resultado se plasma en la entrega de programas resultantes 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...

En las clases impartidas en el aula se desarrollará el temario de la asignatura.

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.

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.
  2. Divide y vencerás.
  3. Algoritmos voraces.
  4. Programación dinámica.
  5. Búsqueda con retroceso.
  6. Ramificación y poda.
  7. Programación lineal y reducciones.

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

Calendario de sesiones 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 trabajos prácticos:

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 156 horas distribuidas del siguiente modo:

  • 45 horas, aproximadamente, de actividades con el/la profesor/a (clases teóricas y de problemas);
  • 45 horas de trabajo de programación en equipo para desarrollar los programas propuestos como trabajo de laboratorio;
  • 60 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.

4.5. Bibliografía y recursos recomendados

http://psfunizar7.unizar.es/br13/egAsignaturas.php?codigo=30229&Identificador=14680

[BB: Bibliografía básica / BC: Bibliografía complementaria]

  • [BB] 1. Introduction to algorithms / Thomas H. Cormen ... [et al.] . - 3rd ed. Cambridge, Massachusetts ; London : MIT Press, cop. 2009
  • [BB] 2. Dasgupta, Sanjoy. Algorithms / Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani . Boston [etc.] : McGraw Hill Higher Education, cop. 2008
  • [BB] 3. Brassard, Gilles : Fundamentos de algoritmia / G. Brassard, T. Bratley ; traducción, Rafael García-Bermejo ; revisión técnica, Narciso Martí, Ricardo Peña, Luis Joyanes Aguilar . - 1ª ed. en español, reimp. Madrid [etc.] : Prentice Hall, 2008
  • [BC] 5. Parberry, I. Problems on Algorithms / I. Parberry and W. Gasarch. - 2nd ed. free book, 2002
  • [BC] Kleinberg, Jon. Algorithm design / Jon Kleinberg, Eva Tardos . Boston : Pearson/Addison-Wesley, cop. 2006