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:
- Jorge Bernal del Nozal
- Correo electrónico:
- jorge.bernal@uab.cat
Uso de idiomas
- Lengua vehicular mayoritaria:
- catalán (cat)
- Algún grupo íntegramente en inglés:
- No
- Algún grupo íntegramente en catalán:
- Sí
- Algún grupo íntegramente en español:
- No
Equipo docente
- Jorge Bernal del Nozal
Prerequisitos
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 los alumnos tienen unos conocimientos básicos sobre programación y estructuras de datos adquiridos en asignaturas anteriores, se pretende que el alumno sea capaz de analizar, diseñar e implementar algoritmos basándose en las técnicas de diseño de algoritmos existentes. Para cumplir con este objetivo, el alumno adquirirá los conocimientos sobre:
- Especificación formal de problemas. Cómo pasar de una descripción de un problema a una especificación válida para el desarrollo de un algoritmo que lo resuelva.
- Pruebas formales para validar programas. Diseño basado en contratos. Precondiciones, postcondiciones e invariantes.
- Paradigmas para el diseño de algoritmos. Algoritmos de búsqueda, greedy, recursividad, backtracking, branch & bound, programación dinámica, algoritmos probabilísticos, etc.
El desarrollo de un algoritmo empieza por formalizar el enunciado de un problema. A partir de este enunciado se diseña un algoritmo que solucione el problema, pero esto no es suficiente, también es importante considerar cuánto tardará el algoritmo en darnos la solución. Así que nos interesa crear algoritmos lo más rápidos posibles. De esta forma podremos crear programas que solucionen problemas lo más grandes posibles en tiempos aceptables. Esta rapidez se consigue diseñando algoritmos que minimicen el número de operaciones a realizar para resolver un problema y desarrollando una implementación eficiente de las operaciones del algoritmo. Esto supondrá que en esta asignatura el alumno adquirirá conocimientos sobre algorítmica e implementación eficiente de algoritmos.
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
- Decidir el método de aprendizaje de datos más adecuado según las características de los datos a analizar.
- 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.
Contenido
El temario de la asignatura será:
- Tema 1. Repaso de conceptos básicos (Pre-condiciones, post-condiciones, invariantes)
- Tema 2. Complejidad computacional
- Tema 3. Algoritmos de búsqueda. Taxonomía y estrategias
- Tema 4. Greedy
- Tema 5. Recursividad
- Tema 6. Divide y vencerás
- Tema 7. Backtracking.
- Tema 8. Branch & Bound.
- Tema 9. Programación dinámica.
- Tema 10. Algoritmos estocásticos
Metodología
Teniendo en cuenta que el objetivo final de la asignatura es que el alumnado sea capaz de analizar y diseñar algoritmos de forma eficiente según un problema dado, el trabajo personal del alumnado deberá ser la parte principal para obtener los objetivos de aprendizaje, siempre acompañado y guiado por el profesorado. Por este motivo, las clases presenciales 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 presencial: 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. Así la clase empezará con una explicación resumida de los conceptos que el alumno habrá estudiado en la preparación de la clase. Este resumen dará una visión general sobre los conceptos en estudio y dará pie a que los alumnos puedan resolver las dudas que tengan. Luego se explicará el problema o trabajo práctica a realizar durante la segunda parte de la clase. Estos problemas o prácticas se realizarán con ordenador, ya que en muchos casos supondrán implementar algoritmos.
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, ya sean ejercicios sueltos o dentro de un proyecto.
La metodología docente y la evaluación propuestas pueden experimentar alguna modificación en función de las restricciones a la presencialidad que impongan las autoridades sanitarias
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 | |||
| Clase de Teoría | 22 | 0,88 | 1 |
| Tipo: Supervisadas | |||
| Clase de problemas | 14 | 0,56 | 2, 1 |
| Clases de prácticas | 14 | 0,56 | 2, 1, 3 |
| Tipo: Autónomas | |||
| Estudio de la materia impartida en teoría | 40 | 1,6 | 1 |
| Realización de problemas | 25,5 | 1,02 | 2, 1, 3 |
| Resolver la práctica | 25 | 1 | 2, 1, 3 |
Evaluación
Criterios e indicadores de evaluación:
- Comprensión de los conceptos teóricos de la asignatura.
- Implementación correcta y eficiente de algoritmos.
Actividades e instrumentos de evaluación:
- Nota Teoría: corresponde a dos exámenes parciales de teoría sobre la asignatura. Se han aprobar los exámenes parciales para eliminar materia en el examen de recuperación.
- Nota de problemas: Corresponde a la nota obtenida por una serie de problemas que tendrá que entregar el alumno. No hay recuperación para las entregas de problemas.
- Nota seguimiento del progreso de aprendizaje: corresponde a la nota obtenida en las diferentes actividades de seguimiento del aprendizaje que se realizarán durante el curso (cuestionarios en Caronte, Kahoots) y que se llevarán a cabo siempre durante las clases presenciales. No hay recuperación para estas actividades.
- Nota Prácticas: En este apartado hay una nota de grupo y una individual:
- Nota de grupo: Corresponde a la nota obtenida a las entregas por grupos de la práctica. Las entregas de prácticas suspendidas se puedes recuperar en entregas posteriores.
- Nota individual: Es la puntuación obtenida en el examen de prácticas. Habrá recuperación del examen de prácticas.
La nota final de la asignatura se obtiene combinando la evaluación de estas cuatro actividades de la siguiente manera:
- A. Nota Teoría
SI Nota examen primer parcial >=5 y Nota examen segundo parcial>=5 ENTONCES
Nota Teoría= 0,5 * Nota examen primer parcial + 0,5 * Nota examen segundo parcial
SINO Nota Teoría=MIN(Nota examen primer parcial, Nota examen segundo parcial)
- B. Nota Problemas
Nota problemas = Media ponderada de los problemas entregados.
- C. Nota Seguimiento
Nota seguimiento = Nota acumulada recogida de los diferentes sistemas de evaluación presencial.
- D. Nota Prácticas
SI Nota Individual>=5 y Nota Grupo>=5 ENTONCES
Nota Prácticas = 0,2 * Nota Individual + 0,8 * Nota Grupo
SINO Nota Prácticas =MIN(Nota Individual, Nota Grupo)
Donde:
- Nota Individual = Examen de prácticas.
- Nota Grupo = Media ponderada de las entregas de prácticas si todas están aprobadas, sino el mínimo de las notas de las entregas. Si la práctica se hace de manera individual, no habrá examen de prácticas.
- Recuperación de prácticas: En el caso de haber suspendido una entrega de grupo, se podrá recuperar en las siguientes entregas de la práctica. La nota será 0.75 * (max (nota recuperación, nota entrega suspendida) –Nota entrega suspendida) + nota entrega suspendida. En el caso de suspender el examen de prácticas, el alumno deberá presentar a un examen de recuperación de prácticas el mismo día del examen de recuperación final.
Nota Final
Si Nota Teoría>=5 y Nota Prácticas >=5 ENTONCES
Nota Final = 0,35 * Nota Teoría + 0,2*Nota problemas + 0,1* Nota seguimiento + 0,35 * Nota Prácticas
SINO Nota Final =MIN(Nota Teoría, Nota Prácticas)
Condiciones para aprobar la asignatura:
Para aprobar la asignatura se ha de haber aprobado (nota mayor o igual a 5):
- Nota final
- Nota teoría.
- Nota prácticas.
- Notas entregas de prácticas.
- Exámenes.
Condiciones para no evaluable:
- No tener ninguna parte de la asignatura suspendida y no cumplir las condiciones para aprobar.
Condiciones para el suspenso:
- No alcanzar una nota media superior o igual a 5.
- Suspender alguna de las actividades de evaluación de la asignatura, aunque la media supere el 5. En este caso, la nota será la nota mínima obtenida de alguna de las partes (exámenes o prácticas).
Condiciones para la matrícula de honor:
La matrícula de honor se puede conseguir con una nota media superior o igual a 9,0.
Debido a que hay un número limitado de matrículas de honor que se pueden dar por grupo, se otorgarán por orden de nota de mayor a menor.
Prácticas, trabajos o exámenes copiados:
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.
Publicación de notas, fechas de exámenes, etc:
Las fechas de evaluación continua y entrega de trabajos se publicarán en el campus virtual y pueden estar sujetos a cambios de programación por motivos de adaptación a posibles incidencias. Siempre se informará en el campus virtual sobre estos cambios ya que se entiende que es el mecanismo habitual de intercambio de información entre profesor y estudiantes.
Procedimiento de revisión de las calificaciones
Para cada actividad de evaluación, se indicará un lugar, fecha y horade revisión en la que el estudiante podrá revisar la actividad con el profesor. En este contexto, se podrán hacer reclamaciones sobre la nota de la actividad, que serán evaluadas por el profesorado responsable de la asignatura. Si el estudiante no se presenta en esta revisión, no se revisará posteriormente esta actividad.
Actividades de evaluación
| Título | Peso | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|---|
| Evaluación de prácticas | Ver actividades e instrumentos de evaluación | 2 | 0,08 | 2, 1, 3 |
| Examen de prácticas | Ver actividades e instrumentos de evaluación | 1 | 0,04 | 2, 3 |
| Examen final | Ver actividades e instrumentos de evaluación | 2,5 | 0,1 | 1 |
| Primer parcial teoría | Ver actividades e instrumentos de evaluación | 2 | 0,08 | 2, 1 |
| Segundo parcial teoría | Ver actividades e instrumentos de evaluación | 2 | 0,08 | 2, 1 |
Bibliografía
- Fundamentos de Algorítmia, G Brassard P. Bratley. Prentice Hall.
- 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
Para hacer las prácticas se utilizará el lenguaje de progamación Python (versión 3.4 en adelante). No imponemos ninguna restricción respecto del IDE que se quiera utilizar (Anaconda, PyCharm, Visual Studio)