Datos Identificativos 2023/24
Asignatura (*) Diseño y Análisis de Algoritmos Código 614G02011
Titulación
Grao en Ciencia e Enxeñaría de Datos
Descriptores Ciclo Periodo Curso Tipo Créditos
Grado 1º cuatrimestre
 Segundo Obligatoria 6
Idioma
Castellano
Modalidad docente Presencial
Prerrequisitos
Departamento Ciencias da Computación e Tecnoloxías da Información
Coordinador/a
Hernandez Pereira, Elena Maria
 Correo electrónico
elena.hernandez@udc.es
Profesorado
Cancela Barizo, Brais
Gómez Rodríguez, Carlos
Hernandez Pereira, Elena Maria
Vilares Calvo, David
 Correo electrónico
brais.cancela@udc.es
carlos.gomez@udc.es
elena.hernandez@udc.es
david.vilares@udc.es
Web http://campusvirtual.udc.es
Descripción general Cando se traballa con datos, sobre todo en gran volume, é fundamental que os algoritmos que se utilizan para manipulalos sexan eficientes, tanto para minimizar o uso de recursos como, en ocasións, para garantir a propia viabilidade do procesado. Nesta materia trátanse os fundamentos necesarios tanto para analizar a eficiencia de algoritmos existentes sobre un caso dado, permitindo así elixir o máis adecuado, como para deseñar novos algoritmos. O primeiro enfócase mediante a análise de custo espacial e temporal coa notación O grande. O segundo trátase a través dos diferentes paradigmas xenéricos de deseño de algoritmos, como algoritmos voraces, programación dinámica ou divide e vencerás; ademais dun tratamento máis específico para ámbitos típicos de interese para o científico ou enxeñeiro de datos, como son a procura, ordenación ou a exploración de grafos. Veranse tamén fundamentos de complexidade computacional e algoritmos aproximados para aqueles casos nos que unha implementación eficiente non é viable.

Esta materia pon broche final ao bloque de "Programación e Algoritmos" do Grao, e por iso deberían cursarse anteriormente as materias de Fundamentos de Programación I e II, cuxos conceptos se utilizan aquí. Fóra do bloque, tamén son necesarios os conceptos de Matemática Discreta. Á súa vez, e dado que os algoritmos son pedra angular de calquera procesado de datos, esta materia proporciona conceptos que se usarán en materias posteriores, incluíndo as de Aprendizaxe Automática, Recuperación de Información, Procesamento de Imaxe, Vídeo e Audio, Procesamento da Linguaxe Escrita, Procesamento Paralelo, así como outras posteriores no plan de estudos.

Competencias del título
Código Competencias del título
A4 CE4 - Conocimiento y aplicación de los fundamentos de programación y técnicas algorítmicas básicas para diseñar soluciones a problemas, utilizando los lenguajes de programación más relevantes en el ámbito de la ciencia e ingeniería de datos.
A5 CE5 - Conocimiento de estructuras de datos y algoritmos básicos y capacidad para utilizarlos eficientemente en la resolución de un problema.
A6 CE6 - Capacidad para diseñar y programar algoritmos robustos y eficientes y saber analizar la idoneidad y complejidad de los mismos.
B2 CB2 - Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio
B3 CB3 - 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
B7 CG2 - Elaborar adecuadamente y con cierta originalidad composiciones escritas o argumentos motivados, redactar planes, proyectos de trabajo, artículos científicos y formular hipótesis razonables.
B8 CG3 - Ser capaz de mantener y extender planteamientos teóricos fundados para permitir la introducción y explotación de tecnologías nuevas y avanzadas en el campo.
B9 CG4 - Capacidad para abordar con éxito todas las etapas de un proyecto de análisis de datos: exploración previa de los datos, preprocesado, análisis, visualización y comunicación de resultados.
B10 CG5 - Ser capaz de trabajar en equipo, especialmente de carácter multidisciplinar, y ser hábiles en la gestión del tiempo, personas y toma de decisiones.
C1 CT1 - Utilizar las herramientas básicas de las tecnologías de la información y las comunicaciones (TIC) necesarias para el ejercicio de su profesión y para el aprendizaje a lo largo de su vida.

Resultados de aprendizaje
Resultados de aprendizaje Competencias del título
Saber analizar problemas y diseñar, programar y depurar algoritmos que los resuelvan utilizando un lenguaje de programación imperativo. A4
A5
 B2
B9
B10
 C1
Saber elegir y utilizar las estrategias de resolución de problemas más relevantes. A4
A6
 B2
B3
B7
B8
B9
B10
 C1
Comprender los principios básicos del almacenamiento de datos y su manipulación. A5
 B2
B8
B9
 C1
Conocer y saber utilizar las estructuras de datos estándar en computación y los algoritmos más relevantes para manipularlas. A5
 B2
B8
B9
 C1
Analizar la complejidad espacial y temporal de los algoritmos y reconocer los aspectos claves de su ineficiencia. A6
 B2
B3
B7
B8
B9
 C1

Contenidos
Tema Subtema
Análisis del coste de algoritmos Coste espacial y temporal
Reglas y limitaciones del análisis O
Paradigmas de diseño algorítmico Divide y vencerás
Programación dinámica
Algoritmos voraces
Estructuras de datos, algoritmos básicos y complejidad Búsqueda en memoria principal y secundaria
Ordenación interna y externa
Exploración de grafos
Problemas NP-Completos NP-Completo y NP-Difícil
Heurísticas y algoritmos aproximados

Planificación
Metodologías / pruebas Competéncias Horas presenciales Horas no presenciales / trabajo autónomo Horas totales
Prácticas de laboratorio A4 A5 A6 B2 B3 B7 B9 B10 C1 20 36 56
Solución de problemas A4 A5 A6 B2 B7 B10 C1 10 17.5 27.5
Prueba objetiva A4 A5 A6 B2 B3 B8 B9 3 7.5 10.5
Sesión magistral A5 A6 B2 B3 B8 B9 30 24 54
 
Atención personalizada 2 0 2
 
(*)Los datos que aparecen en la tabla de planificación són de carácter orientativo, considerando la heterogeneidad de los alumnos

Metodologías
Metodologías Descripción
Prácticas de laboratorio En las prácticas de laboratorio, el alumnado tendrá que solucionar problemas mediante la implementación y análisis de algoritmos en un lenguaje de alto nivel. Las prácticas se organizarán en entregas periódicas para fomentar el estudio continuo y la evaluación continua. Además del código fuente, las entregas incluirán informes donde el alumnado deberá exponer las conclusiones obtenidas sobre los algoritmos, en relación con los conceptos de la asignatura, y que serán evaluados junto con los propios programas entregados.
Solución de problemas Se desarrollarán ejemplos y ejercicios en los que el alumnado tendrá que aplicar los conocimientos teóricos de la asignatura a casos concretos. Se garantizará la interactividad, resolviendo dudas por parte del alumnado y animándolo a contrastar sus soluciones y plantear cuestiones relevantes. Parte de los problemas realizados serán evaluados.
Prueba objetiva Se llevará a cabo una evaluación de la materia mediante una prueba que incluirá tanto preguntas sobre los contenidos teóricos, como supuestos prácticos y ejercicios de aplicación relacionados con los distintos temas vistos en la asignatura.
Sesión magistral Clases magistrales donde se expondrán los conceptos teóricos de la asignatura, sin perder nunca de vista ejemplos de aplicación para motivar y contextualizar los contenidos de la materia. Se fomentará la interactividad en clase mediante la formulación de preguntas y se utilizarán distintos recursos como pizarra, transparencias o demostraciones.

Atención personalizada
Metodologías
Solución de problemas
Prácticas de laboratorio
Descripción
El desarrollo, tanto de las clases magistrales como de las de resolución de problemas y los laboratorios de prácticas, se realizará atendiendo al progreso del alumnado en las capacidades de comprensión y asimilación de los contenidos impartidos. El avance general de la clase se compaginará con una atención específica a aquel alumnado que presente mayores dificultades en la tarea del aprendizaje y con un apoyo adicional a aquellos/as que presenten mayor desenvoltura y deseen ampliar conocimientos.

En lo que respecta a las tutorías individuales, dado su carácter personalizado, no deben dedicarse a extender los contenidos con nuevos conceptos, sino a aclarar los conceptos ya expuestos. El profesor las utilizará como una interacción que le permita extraer conclusiones respecto al grado de asimilación de la materia por parte de los alumnos.

Evaluación
Metodologías Competéncias Descripción Calificación
Solución de problemas A4 A5 A6 B2 B7 B10 C1 Se valorarán los resultados, forma y condiciones de realización de diversos trabajos puntuables que se detallarán durante el curso. 20
Prácticas de laboratorio A4 A5 A6 B2 B3 B7 B9 B10 C1 Realizadas según las condiciones establecidas en el enunciado de cada práctica. La entrega en tiempo y forma de las prácticas es condición necesaria para aprobar la asignatura en la primera oportunidad. 20
Prueba objetiva A4 A5 A6 B2 B3 B8 B9 Realización obligatoria. Se evaluará el dominio de los conocimientos teóricos y operativos de la asignatura. Es necesario obtener una nota mínima de 4 para aprobar la materia en cualquiera de las oportunidades. 60
 
Observaciones evaluación

Prueba objetiva

Es necesario obtener una nota mínima de 4 para
aprobar la materia en cualquiera de las oportunidades.

Trabajos prácticos y solución de problemas

- Dado que se trata de actividades de evaluación continua, no se reevaluarán ni se admitirán entregas en la segunda oportunidad. Las calificaciones de trabajos prácticos y solución de problemas de la primera oportunidad se conservarán para la segunda.

- La realización fraudulenta de las pruebas o actividades de evaluación, una vez comprobada, implicará directamente la cualificación de suspenso en la convocatoria en que se cometa: lo/a estudiante será calificado con “suspenso” (nota numérica 0) en la convocatoria correspondiente del curso académico, tanto si la comisión de la falta se produce en la primera oportunidad como en la segunda. Para esto, se procederá a modificar su cualificación en el acta de primera oportunidad, si fuera necesario".

* Reglamento disciplinar del estudiantado de la UDC. Aprobado por el Consejo de Gobierno del 27/02/2023 y modificado en su artículo 11.4.b por el Consejo de Gobierno del 28/06/2023.


- Si las pruebas o actividades de evaluación se realizar en grupo, todos los miembros del grupo responderán de forma solidaria del trabajo realizado y entregado y de sus posibles consecuencias.

- Se as probas ou actividades de avaliación se realizaren en grupo, todos os membros do grupo
responderán de forma solidaria do traballo realizado e entregado e das
súas posibles consecuencias.

- Si las pruebas o actividades de evaluaciónse llevan a cabo en grupos, todos los
miembros del grupo serán responsables solidariamente por el trabajo
realizado y entregado y sus posibles consecuencias.

Matrícula a tiempo parcial

- El alumnado matriculado a tiempo parcial tendrá que entregar las
actividades evaluables en las condiciones y plazos específicos que se
establecerán. Será obligación del estudiante comunicar su situación al profesorado.

No presentado

- Quien no concurra a la prueba objetiva en el período oficial de evaluación tendrá la condición de “No presentado” (NP). En la primera oportunidad, esto será extensible a quien no entregue las prácticas en tiempo y forma.

Fuentes de información
Básica Goodrich, Michael T. (2013). Data structures and algorithms in Python. John Wiley and Sons
Brassard, G., Bratley, P. (1996). Fundamentals of Algorithmics. Prentice Hall

Complementária Bhargava, Aditya (2018). Algoritmos : una guía ilustrada para programadores y curiosos. Anaya Multimedia
Cormen, Thomas H. (2009). Introduction to Algorithms. The MIT Press
Fortnow, Lance (2013). The golden ticket: P, NP, and the search for the impossible. Princeton University Press


Recomendaciones
Asignaturas que se recomienda haber cursado previamente
Matemática Discreta/614G02002
Fundamentos de Programación II/614G02009
Fundamentos de Programación I/614G02004

Asignaturas que se recomienda cursar simultáneamente

Asignaturas que continúan el temario
Procesamiento de Lenguaje Escrito/614G02029
Procesamiento Paralelo/614G02023
Recuperación de Información/614G02027
Procesamiento de Imagen, Vídeo y Audio/614G02028
Aprendizaje Automático I/614G02019

Otros comentarios

Según se recoge en las distintas normativas de aplicación para la docencia universitaria, se incorporará la perspectiva de género en esta materia (se usará lenguaje no sexista, se utilizará bibliografía de autores/as de ambos sexos, se propiciará la intervención en clase de alumnos y alumnas...). Se trabajará para identificar y modificar prejuicios y actitudes sexistas y se influirá en el entorno para modificarlos y fomentar valores de respeto e igualdad. Se intentará detectar situaciones de discriminación por razón de género y se propondrán acciones y medidas para corregirlas.


(*) La Guía Docente es el documento donde se visualiza la propuesta académica de la UDC. Este documento es público y no se puede modificar, salvo cosas excepcionales bajo la revisión del órgano competente de acuerdo a la normativa vigente que establece el proceso de elaboración de guías