Logo UAB
2023/2024

Diseño de Algoritmos

Código: 104359 Créditos ECTS: 6
Titulación Tipo Curso Semestre
2503758 Ingeniería de Datos OB 2 2

Contacto

Nombre:
Aura Hernandez Sabate
Correo electrónico:
aura.hernandez@uab.cat

Idiomas de los grupos

Puede consutarlo a través de este enlace. Para consultar el idioma necesitará introducir el CÓDIGO de la asignatura. Tenga en cuenta que la información es provisional hasta el 30 de noviembre del 2023.

Equipo docente

Enrique Ruiz Amakrache

Prerrequisitos

Aunque no es obligatorio, es muy aconsejable haber cursado las siguientes asignaturas:

·         Fonaments de Programació

·         Programació Avançada

·         Estructures de Dades

·         Anàlisi de Grafs i Cerca d’Informació

·         Enginyeria del Rendiment

Se considerará que el alumno ya ha adquirido previamente los conocimientos impartidos en estas asignaturas.

 


Objetivos y contextualización

Partiendo de la base de que el/la estudiante ya tiene unos conocimientos básicos sobre programación, esta asignatura está centrada en introducir diferentes estilos y paradigmas de diseño de algoritmos. El objetivo principal es que los estudiantes desarrollen habilidades en el diseño y análisis de algoritmos para poder resolver problemas del mundo real de manera efectiva y eficiente de acuerdo con los requisitos establecidos por un cliente potencial.

Por ello se espera que al finalizar el curso el alumnado sabrá:

  • Especificar formalmente problemas y programas, y verificarlos.
  • Utilizar pruebas formales para validar programas e invariantes para diseñar basándose en contratos.
  • Calcular la complejidad algorítmica y computacional de un algoritmo.

Por otra parte, conocerá y sabrá elegir en cada momento diferentes estilos y paradigmas de diseño de algoritmos como:

  • recursividad
  • backtracking
  • programación dinámica
  • algoritmos probabilísticos
  • Etc.

La algorítmica pretende encontrar la forma más rápida de solucionar problemas y esto tiene dos vertientes. La primera, y más importante, es encontrar algoritmos con la mínima complejidad, por lo que hagan el mínimo número de operaciones posible. La segunda, corresponde a programa las implementaciones de estos algoritmos de la forma en que la ejecución sea lo más rápida posible. Por tanto, los objetivos incluyen conocer las técnicas de desarrollo de algoritmos y la implementación de programas rápidos.


Competencias

  • Diseñar soluciones algorítmicas eficientes para problemas computacionales, implementarlas en forma de desarrollo de software robustos, estructurados y fáciles de mantener, y verificar su validez.
  • Evaluar de manera crítica el trabajo realizado.
  • 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.

Resultados de aprendizaje

  1. Decidir el método de aprendizaje de datos más adecuado según las características de los datos a analizar.
  2. Evaluar de manera crítica el trabajo realizado.
  3. 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.

Contenido

El temario de la asignatura será:

  • Tema 1. Repaso de conceptos básicos (Pre-condiciones, post-condiciones, invariantes, complejidad computacional)
  • Tema 2. Algoritmos de búsqueda. Taxonomía y estrategias
  • Tema 3. Greedy
  • Tema 4. Divide y vencerás
  • Tema 5. Backtracking
  • Tema 6. Branch & Bound
  • Tema 7. Programación dinámica
  • Tema 8. Algoritmos estocásticos

Metodología

Teniendo en cuenta que el objetivo final de la asignatura es que los alumnos desarrollen habilidades para analizar y diseñar algoritmos de forma eficiente según un problema dado, el trabajo del alumnado es el eje central de su aprendizaje, acompañado y guiado por el profesorado. Por este motivo, las sesiones dirigidas serán altamente prácticas y se centrarán en que el alumnado consolide los conocimientos que son objetivo de aprendizaje de esta asignatura.


La metodología general de la asignatura se puede dividir en tres fases:


Preparación de la clase: el objetivo de esta fase es que el alumnado pueda aprender los conceptos que se trabajarán en la sesión siguiente mediante diversas actividades ofrecidas por el profesorado como puede ser el visionado de vídeos, la lectura de textos, etc.

Clase dirigida: el objetivo de esta fase es la de consolidar los conceptos vistos y ponerlos en valor dentro del contexto de la asignatura. El profesorado velará para que el alumnado profundice en estos conceptos mediante ejercicios (más o menos) guiados durante la sesión.

Trabajo autónomo: para que el alumnado tome soltura en la programación de los algoritmos vistos este tendrá que hacer una parte del trabajo por su cuenta con

  1. ejercicios sueltos que se entregarán para ser evaluados
  2. dentro de un proyecto que se irá realizando a lo largo de todo el curso.

Proyecto de programación: Dentro del trabajo autónomo pedido al alumnado, habrá que realizar un proyecto de programación que se irá desarrollando a lo largo de todo el curso, a medida que se vaya avanzando en el temario. Cada parte del proyecto estará relacionada con uno de los temas previstos y se irán planteando dentro de las sesiones de clase. Sededicarán algunas horas de las sesiones a plantear el trabajoa realizar y  también a hacer el seguimiento del correcto desarrollo, así como el planteamiento de dudas.

Nota: se reservarán 15 minutos de una clase dentro del calendario establecido por el centro o por la titulación para que el alumnado rellene las encuestas de evaluación de la actuación del profesorado y de evaluación de la asignatura o módulo.


Actividades

Título Horas ECTS Resultados de aprendizaje
Tipo: Dirigidas      
Clases presenciales 50 2 1
Tipo: Supervisadas      
Refuerzo y seguimento en la resolución del proyecto y los ejercicios 4 0,16 2, 1
Seguimiento en la asimilación de los conceptos teóricos 4 0,16 2, 1, 3
Tipo: Autónomas      
Desarrollo de un proyecto 44 1,76 2, 1, 3
Preparación de parciales 12 0,48 2, 1
Preparación previa a las clases 12 0,48 2, 1, 3
Trabajo autónomo 12 0,48 2, 1

Evaluación

Esta asignatura no prevé el sistema de evaluación única.

Se evaluarán tres tipos de actividades de manera independiente y la suma ponderada de ellas dará la nota final. Estas tres actividades son:

  • Pruebas de síntesis (PS)
  • Ejercicios evaluables (EA)
  • Proyecto práctico (P)

1. La primera parte (PS) consiste en la realización de dos pruebas parciales en las que se evaluará al alumnado de forma individual. La nota mínima para aprobar cada prueba es de 4, pero la media de las dos deberá llegar al 5.

2. La segunda parte (EA) consistirá en la entrega de actividades a lo largo de todo el curso. Estas actividades pueden ser en forma de ejercicios, cuestionarios, informes, etc y se pueden plantear dentro de las sesiones de clase o pueden ser propuestas como deberes para casa. La nota final saldrá de la suma ponderada de las entregas fijadas que se pidan.

3. La tercera parte (P) se evaluará de manera grupal (con la entrega de un proyecto) e individual (con la evaluación de una prueba escrita). La nota final se obtendrá de la suma ponderada de la nota grupal y la individual. El proyecto consta de diferentes entregas a lo largo del curso las notas de las cuales conformarán la nota grupal. La nota mínima para aprobar el proyecto es de 5, mientras que el examen individual hay que aprobarlo con una nota mínima de 3.5. La nota final de esta parte deberá ser como mínimo un 5. Para aprobar la asignatura es necesario que la evaluación de cada una de las partes supere el mínimo exigido y que la evaluación total supere los 5 puntos.

NOTA DEL EXPEDIENTE, MATRÍCULA DE HONOR Y NO EVALUABLE


En caso de no superar la asignatura debido a que alguna de las actividades de evaluación no alcanza la nota mínima requerida, la nota numérica del expediente será la nota máxima entre los parciales suspendidos, o en su defecto, la notasuspendida máxima. Con las excepciones de los estudiantes que:

1) no participen en ninguna de las actividades de evaluación, que se otorgará la calificación de "no evaluable" (cualquier alumno que entregue una práctica o una evaluación programada tendrá nota),
2) hayan cometido irregularidades en un acto de evaluación, que se otorgará el valor menor entre 3.0 y la nota numérica máxima antes citada (y por tanto no será posible el aprobado por compensación).


Se darán tantas matrículas como puedan dentro de la normativa de la universidad, siempre y cuando la nota mínima sea un 9.


RECUPERACIÓN

PS: En el caso de suspender o no presentarse a alguna de las pruebas individuales se podrán recuperar el día asignado a la semana oficial de exámenes.

EA: Esta parte no tendrá la posibilidad de recuperarse.

P: En el caso de suspender la evaluación individual del proyecto (es necesario haberse presentado la primera vez), se podrá recuperar el día asignado en la semana oficial de exámenes. Las entregas parciales del proyecto se pueden recuperar en las siguientes entregas, con una nota final del 80% (y por lo tanto nunca superior a 8).

 

CONVALIDACIÓN
No se convalidan proyectos de años anteriores.

PLAGIOS, COPIAS, ETC:

Sin perjuicio de otras medidas disciplinarias que se estimen oportunas, y de acuerdo con la normativa académica vigente, las irregularidades cometidas por un estudiante que puedan conducir a una variación de la calificación se calificarán con un cero (0). Las actividades de evaluación calificadas de esta forma y por este procedimiento no serán recuperables. Si es necesario superar cualquiera de estas actividades de evaluación para aprobar la asignatura, esta asignatura quedará suspendida directamente, sin oportunidad de recuperarla en el mismo curso. Estas irregularidades incluyen, entre otros:

- la copia total o parcial de una práctica, informe, o cualquier otra actividad de evaluación;

- dejar copiar;

- presentar un trabajo de grupo no hecho íntegramente por los miembros del grupo;

- presentarcomo propios materiales elaborados por un tercero, aunque sean traducciones o adaptaciones, y en general trabajoscon elementos no originales y exclusivos del estudiante;

- tener dispositivos de comunicación (como teléfonos móviles, smart watches, etc.) accesibles durante las pruebas de evaluación teórico-prácticas individuales (exámenes).

En caso de que el estudiante haya cometido irregularidades en un acto de evaluación, la nota numérica del expediente será el valor menor entre 3.0 y la nota que le correspondería según el método de evaluación de la asignatura (y por tanto no será posible el aprobado por compensación).

En resumen: copiar, dejar copiar o plagiar en cualquiera de las actividades de evaluación equivale a un SUSPENSO con nota inferior a 3.0.

COMUNICACIÓN


Las fechas de evaluaciones y entregas se publicarán en Caronte y pueden estar sujetos a posibles cambios de programación por motivos de adaptación a posibles incidencias. Siempre se informará en Caronte sobre estos cambios ya que se entiende que esta es la plataforma habitual de intercambio de información entre profesorado y alumnado.

 


Actividades de evaluación continuada

Título Peso Horas ECTS Resultados de aprendizaje
Evaluación de actividades desarrolladas en el aula 10 1 0,04 2, 1, 3
Evaluación de actividades desarrolladas fuera del aula 20 1 0,04 2, 1, 3
Evaluación grupal del proyecto 30 2 0,08 2, 1, 3
Evaluación individual del proyecto 10 1 0,04 2, 3
Examen final (recuperación) 30 3 0,12 2, 1
Primer parcial teoría 15 2 0,08 2, 1
Segundo parcial teoría 15 2 0,08 2, 1

Bibliografía

  • Fundamentos de Algorítmia, G Brassard P. Bratley. Prentice Hall.
  • Análisis y diseño de algoritmos : un enfoque práctico, Eduardo Villegas Jaramillo, Luz Enith Guerrero Mendieta. (Primera edición.). Disponible en línia
  • Técnicas de Diseño de Algoritmos, Rosa Guerequeta y Antonio Vallecillo.
  • Técnicas de diseño de algoritmos, F. Perales, M. Mascaró. Universitat de les Illes Balears
  • Karumanchi, Narasimha. "Algorithm Design Techniques: Recursion, Backtracking, Greedy, Divide and Conquer, and Dynamic Programming." (2018).
  • Chun, Wesley. Core python programming. Vol. 1. Prentice Hall Professional, 2001.

Software


Se programará en lenguaje de programación Python (versión 3.4 en adelante). No imponemos ninguna restricción respecto del IDE que se quiera utilizar (Anaconda, PyCharm, Visual Studio)