Análisis y Diseño de Algoritmos
Código: 102783 Créditos ECTS: 6| Titulación | Tipo | Curso |
|---|---|---|
| Ingeniería Informática | OB | 3 |
| Ingeniería Informática | OT | 4 |
Contacto
- Nombre:
- Francisco Javier Sánchez Pujadas
- Correo electrónico:
- javier.sanchez.pujadas@uab.cat
Equipo docente
- Pau Cano Ribe
Idiomas de los grupos
Puede consultar esta información al final del documento.
Prerrequisitos
No hay prerequisitos formales, pero se recomienda haber aprobado las siguientes asignaturas:
Primer curso del grado:
- Fundamentos de informática
- Metodología de la programación
- Matemática discreta
Segundo curso del grado:
- Laboratorio de programación
Objetivos y contextualización
Esta asignatura es la continuación de las asignaturas de programación vistas a primero y segundo, como Fundamentos de informática, Metodología de la programación y Laboratorio de programació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
- Ingeniería Informática
- Adquirir hábitos de pensamiento.
- Capacidad para concebir, desarrollar y mantener sistemas, servicios y aplicaciones informáticas empleando los métodos de la ingeniería del software como instrumento para el aseguramiento de su calidad.
- Capacidad para definir, evaluar y seleccionar plataformas hardware y software para el desarrollo y la ejecución de sistemas, servicios y aplicaciones informáticas.
- Capacidad para 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.
- Trabajar en equipo.
Resultados de aprendizaje
- Conocer los mecanismos de funcionamiento de los diferentes paradigmas de programación.
- Desarrollar el pensamiento científico.
- Desarrollar la capacidad de análisis, síntesis y prospectiva.
- Evaluar la complejidad de los algoritmos y identificar sus puntos débiles.
- Identificar y seleccionar estrategias algorítmicas adecuadas al problema.
- Seleccionar la mejor técnica de programación para la resolución de problemas complejos.
- Trabajar cooperativamente.
Contenido
- Tema 1. Precondiciones, postcondiciones e invariantes
- Tema 2. Recursividad y Complejidad Computacional
- Tema 3. Divide y vencerás
- Tema 4. Backtracking
- Tema 5. Branch & Bound
- Tema 6. Programación Dinámica
- Tema 7. Greedy
- Tema 8. Algoritmos Probabilísticos
- Tema 9. Análisis de algoritmos
Actividades formativas y Metodología
| Título | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|
| Tipo: Dirigidas | |||
| Clases presenciales | 50 | 2 | 4, 1, 3, 5, 6, 7 |
| Tipo: Supervisadas | |||
| Refuerzo y seguimento en la resolución del proyecto y los ejercicios | 4 | 0,16 | 4, 3, 5, 6 |
| Seguimiento en la asimilación de los conceptos teóricos | 4 | 0,16 | 4, 1, 3, 5, 6 |
| Tipo: Autónomas | |||
| Desarrollo de un proyecto | 36 | 1,44 | 4, 1, 2, 3, 5, 7 |
| Elaboración de informes prácticos | 8 | 0,32 | 2, 3, 7 |
| Preparación de parciales | 12 | 0,48 | 4, 1, 3, 5, 6 |
| Preparación previa a las clases | 12 | 0,48 | 2, 3, 5, 6 |
| Trabajo autónomo | 12 | 0,48 | 4, 1, 2, 3, 5, 6, 7 |
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
- ejercicios sueltos que se entregarán para ser evaluados
- 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. Se dedicará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.
COMPETENCIAS TRANSVERSALES: En esta asignatura se trabajarán y evaluarán las siguientes competencias transversales:
T01.02 - Desarrollar la capacidad de análisis, síntesis y prospectiva
T01.03 - Desarrollar el pensamiento científico
T03.01 -Trabajar cooperativamente
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.
Evaluación
Actividades de evaluación continuada
| Título | Peso | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|---|
| Evaluación grupal del proyecto | 30 | 2 | 0,08 | 4, 1, 2, 3, 5, 6, 7 |
| Evaluación de actividades desarrolladas en el aula | 10 | 1 | 0,04 | 4, 1, 2, 3, 5, 6, 7 |
| Evaluación de actividades desarrolladas fuera del aula | 20 | 1 | 0,04 | 4, 1, 2, 3, 5, 6, 7 |
| Evaluación exàmen del projecte | 10 | 1 | 0,04 | 2, 3 |
| Examen Final (recuperación) | 30 | 3 | 0,12 | 4, 1, 2, 3, 5, 6 |
| Primer Examen Parcial Teórico-Práctico | 15 | 2 | 0,08 | 4, 1, 2, 3, 5 |
| Segundo Examen Parcial Teórico-Práctico | 15 | 2 | 0,08 | 4, 1, 2, 3, 5, 6 |
Se evaluarán tres tipos de actividades de forma independiente y la suma ponderada de ellas dará la nota final. Estas tres actividades son:
- Pruebas de síntesis (PS exámenes)
- 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 será de 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 realizar en casa. La nota final saldrá de la suma ponderada de las entregas fijadas que se soliciten.
3. La tercera parte (P) se evaluará de forma individual con la entrega de un proyecto y 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, cuyas notas conformarán la nota grupal. La nota mínima para aprobar el proyecto es de 5, mientras que el examen individual debe aprobarse con una nota mínima de 5. La nota final de esta parte deberá ser como mínimo un 5.
Las notas mínimas de 5 serán de 4 en caso de que los alumnos asistan a más del 50% de las clases.
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.
RECUPERACIÓN
PS: En 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 caso de suspender la prueba escrita del proyecto (hay que haberse presentado la primera vez), se podrá recuperar el día asignado a la semana oficial de exámenes. Las entregas parciales del proyecto pueden recuperarse en las siguientes entregas, con una nota final del 80% de la mejora de la nota.
REVISIÓN DE CALIFICACIONES
La revisión de las notas de los exámenes se realizará el día que indique el profesorado después de cada examen.
La revisión de entregas se pedirá por e-mail y podrá ser presencial, no presencial o por e-mail.
MATRÍCULA DE HONOR
Se darán tantas matrículas como puedan dentro de la normativa de la universidad, siempre que la nota final obtenida sea como mínimo un 9.
NO EVALUABLE
No haber presentado alguna parte evaluable de la asignatura.
Las partes no presentadas de la asignatura tendrán nota 0.
CONVALIDACIÓN
No se convalidan proyectos de años anteriores.
NOTA DEL EXPEDIENTE
Elementos que se evaluarán:
Exámenes:
Primero parcial de teoría.
Segundo parcial de teoría.
Examen de prácticas (verifica que se ha trabajado en la práctica).
Examen de recuperación de teoría (los parciales eliminan materia).
Examen de recuperación de prácticas.
Problemas:
Problemas entregados por los alumnos.
Práctica:
Entregas de las prácticas.
Nota Teoría: corresponde a dos exámenes parciales de teoría sobre la asignatura. Se deben aprobar los exámenes parciales para eliminar materia en el examen de recuperación.
Nota de problemas: Corresponde la nota obtenida por una serie de problemas quedeberá entregar al alumno. No existe recuperación para las entregas de problemas.
Nota Prácticas: En este apartado hay una nota de las entregas y una nota del examen de prácticas:
Nota de las entregas: Corresponde a la nota obtenida en las entregas de la práctica. Las entregas de prácticas suspendidas se pueden recuperar en entregas posteriores. El valor de mejora de la nota será del 80%.
Nota examen de prácticas: Es la puntuación obtenida en el examen de prácticas. Habrá recuperación del examen de prácticas. El examen de prácticas se realiza el mismo día que el examen del segundo parcial y del examen de recuperación.
La asistencia a clase no es obligatoria, pero muy recomendable para aprobar la asignatura.
Existe control de asistencia a clase automatizado con el servidor de corrección.
Asistencia y evaluación de la asignatura:
La nota mínima para poder promediar será de 4 (MinMedia=4) si la asistencia a clase es superior al 50% de las clases. En caso contrario la nota mínima para promediar será de 5 (MinMedia=5).
Esta nota mínima se aplica a todos los exámenes, entregas de prácticas y notas intermedias de teoría y prácticas.
La nota final de la asignatura se obtiene combinando la evaluación de estas tres actividades de la siguiente forma:
Si Nota Teoría> = MinMitjana y Nota Prácticas> = MinMitjana SEMILLAS Nota Final = 0,4 * Nota Teoría + 0,2 * Nota problemas + 0,4 * Nota Prácticas
SINO Nota Final = MIN (Nota Teoría, Nota Prácticas)
SI Notaexamen primer parcial>=MinMedia y Nota examen segundo parcial>=MinMedia SEMILLAS 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)
Nota problemas = Media de los problemas entregados.
NOTA DEL EXPEDIENTE
Elementos que se evaluarán:
Exámenes:
Primero parcial de teoría.
Segundo parcial de teoría.
Examen de prácticas (verifica que se ha trabajado en la práctica).
Examen de recuperación de teoría (los parciales eliminan materia).
Examen de recuperación de prácticas.
Problemas:
Problemas entregados por los alumnos.
Práctica:
Entregas de las prácticas.
Nota Teoría: corresponde a dos exámenes parciales de teoría sobre la asignatura. Se deben aprobar los exámenes parciales para eliminar materia en el examen de recuperación.
Nota de problemas: Corresponde la nota obtenida por una serie de problemas que deberá entregar al alumno. No hay recuperación para las entregas de problemas.
Nota Prácticas: En este apartado hay una nota de las entregas y una nota del examen de prácticas:
Nota de las entregas: Corresponde a la nota obtenida en las entregas de la práctica. Las entregas de prácticas suspendidas se pueden recuperar en entregas posteriores.
Nota examen de prácticas: Es la puntuación obtenida en el examen de prácticas. Habrá recuperación del examen de prácticas.
La asistencia a clase no es obligatoria, pero muy recomendable para aprobar la asignatura.
Existe control de asistencia a clase automatizado con el servidor de corrección.
Asistencia y evaluación de la asignatura:
La nota mínima para promediar será de 4 (MinMitjana=4) si la asistencia a clase es superior al 50% de las clases. En caso contrario la nota mínima para promediar será de 5 (MinMitjana=5).
Esta nota mínima se aplica a todos los exámenes, entregas de prácticas y notas intermedias de teoría y prácticas.
La nota final de la asignatura se obtiene combinando la evaluación de estas tres actividades de la siguiente forma:
Si Nota Teoría> = MinMitjana y Nota Prácticas> = MinMitjana SEMILLAS Nota Final = 0,4 * Nota Teoría + 0,2 * Nota problemas + 0,4 * Nota Prácticas
SINO Nota Final = MIN (Nota Teoría, Nota Prácticas)
SI Notaexamen primer parcial>=MinMedia y Nota examen segundo parcial>=MinMedia SEMILLAS 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)
Nota problemas = Media de los problemas entregados.
SI Nota examen de prácticas >= MinMitjana y Nota entregas>= MinMitjana SEMILLAS Nota Prácticas = 0,2 * Nota examen de prácticas + 0,8 * Nota entregas
SINO Nota Prácticas = MIN(Nota examen de prácticas, Nota entregas)
Nota Entregas = Media ponderada de las entregas de prácticas si todas superan MinMedia, sino el mínimo de las notas de las entregas.
Las partes no presentadas de la asignatura tendrán nota 0.
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á recuperable. Directamente, sin oportunidad de recuperarla en el mismo curso. Estas irregularidades incluyen, entre otras:
- 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 realizado íntegramente por los miembros del grupo;
- presentar como propios materiales elaborados por un tercero, aunque sean traducciones o adaptaciones, y en general trabajos con 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 resumen: copiar, dejar copiar o plagiar en cualquiera de las actividades de evaluación equivale a un SUSPENSO con nota inferior a 3.5.
USO DE INTELIGENCIA ARTIFICIAL
Está permitido un uso restringido de la IA. Normalmente, para resolver dudas y facilitar el aprendizaje. Un uso de la IA que limite el aprendizaje del alumno se considerará como plagio o copia. plagio.
COMUNICACIÓN
Las fechas de evaluaciones y entregas se publicarán en el campus virtual y pueden estar sujetas a posibles cambios de programación por motivos de adaptación a posibles incidencias. Siempre se informará al Campus Virtual sobre estos cambios ya que se entiende que ésta es la plataforma habitual de intercambio de información entre profesores y estudiantes. La plataforma de comunicación síncrona será preferentemente Teams.
EVALUACIÓN ÚNICA
Se evaluará al igual que la evaluación continua. Pero con las siguientes diferencias:
Las prácticas y problemas se entregarán el día del examen de recuperación de la asignatura. En este caso las prácticas no tienen la posibilidad de recuperación, ya que el alumno no puede corregir y vivir la nota las veces que quiera antes de la entrega.
Debido a que no existe un seguimiento del trabajo del alumno, será obligatorio realizar un examen de validación de prácticas, que es obligatorio aprobar.
Los exámenes de teoría y prácticas se realizarán el día del examen de recuperación de la asignatura.
En caso necesario, se convocará a los alumnos para realizar los exámenes de recuperación de teoría y prácticas.
Bibliografía
- Brassard, G., Bratley, P., & Garcia-Bermejo, R. (1997). Fundamentos de algoritmia (Vol. 86). Madrid: Prentice Hall.
- Guerequeta, R., & Vallecillo, A. (2019). Técnicas de diseño de algoritmos.
- Villegas Jaramillo, & Guerrero Mendieta, L. E. (2016). 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
- Eckel, B. (2021). Thinking in C++.
- Stroustrup, B. (1993). C++ el lenguaje de Programación. Eddison Wesley/Díaz de Santos.
- http://en.cppreference.com/w/
- http://www.cplusplus.com/
Web:
- Algoritmo, https://es.wikipedia.org/wiki/Algoritmo
- http://en.cppreference.com/w/
- http://www.cplusplus.com/
-
Algoritmo voraz, https://es.wikipedia.org/wiki/Algoritmo_voraz
- Recursión (ciencias de computación), https://es.wikipedia.org/wiki/Recursi%C3%B3n_(ciencias_de_computaci%C3%B3n)
- Algoritmo divide y vencerás, https://es.wikipedia.org/wiki/Algoritmo_divide_y_vencer%C3%A1s
- Vuelta atrás, https://es.wikipedia.org/wiki/Vuelta_atr%C3%A1s
- Ramificación y poda, https://es.wikipedia.org/wiki/Ramificaci%C3%B3n_y_poda
- Programación dinámica, https://es.wikipedia.org/wiki/Programaci%C3%B3n_din%C3%A1mica
- Algoritmo probabilista, https://es.wikipedia.org/wiki/Algoritmo_probabilista
- ¿Cuál es el algoritmo MÁS IMPORTANTE de la historia? https://www.youtube.com/watch?v=kflbmvCWdwk
- La destacable historia detrás del algoritmo más importante de todos los tiempos https://www.youtube.com/watch?v=2Xkv-W9tOXU
Software
Se programará en C ++ básico y se utilizará Microsoft Visual Studio 2022 (licencia UAB). Para la instalación de VS2022 se utilizarán las siguientes opciones:
• Microsoft Visual Studio Community 2022
• Desktop development with C ++
• C ++ MFC latest v142
Los alumnos deben llevar un ordenador portátil con Windows 10/11 para realizar problemas y prácticas en clase.
Grupos e idiomas de la asignatura
La información proporcionada es provisional hasta el 30 de noviembre de 2025. A partir de esta fecha, podrá consultar el idioma de cada grupo a través de este enlace. Para acceder a la información, será necesario introducir el CÓDIGO de la asignatura
| Nombre | Grupo | Idioma | Semestre | Turno |
|---|---|---|---|---|
| (PAUL) Prácticas de aula | 440 | Catalán | primer cuatrimestre | manaña-mixto |
| (PAUL) Prácticas de aula | 441 | Catalán | primer cuatrimestre | manaña-mixto |