Datos Identificativos 2020/21
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 Híbrida
Prerrequisitos
Departamento Ciencias da Computación e Tecnoloxías da Información
Coordinador/a
Gómez Rodríguez, Carlos
 Correo electrónico
carlos.gomez@udc.es
Profesorado
Gómez Rodríguez, Carlos
Hernandez Pereira, Elena Maria
Sanchez Maroño, Noelia
 Correo electrónico
carlos.gomez@udc.es
elena.hernandez@udc.es
noelia.sanchez@udc.es
Web http://moodle.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.
Plan de contingencia 1. Modificacións nos contidos

Non se prevén modificacións nos contidos da materia.

2. Metodoloxías

*Metodoloxías docentes que se manteñen

As metodoloxías docentes manteranse na súa esencia, co cambio de pasar a ser realizadas online.

*Metodoloxías docentes que se modifican

As metodoloxías mantéñense, cos cambios necesarios para ser realizadas online. En particular:

- Clases maxistrais: en lugar de impartirse presencialmente cos alumnos na aula, gravaranse en vídeo e poranse a disposición dos alumnos en Stream e mediante ligazóns en Moodle, nas semanas nas que estivese previsto impartir eses contidos na planificación da materia. Durante os horarios das clases de teoría, os profesores ofrecerán sesións de titoría síncronas a través da ferramenta Teams.

- Solución de problemas: en lugar de nas clases presenciais, proporanse os exercicios a través de Moodle, que tamén se utilizará para recoller as entregas avaliables, e atenderanse as dúbidas e fomentarase a interacción con e entre os estudantes a través de Teams.

- Prácticas de laboratorio: todas as ferramentas necesarias para a realización das prácticas son gratuítas e pódense instalar nos equipos persoais dos alumnos. O seguimento das prácticas levará a cabo mediante a ferramenta Teams.

3. Mecanismos de atención personalizada ao alumnado

- Teams: cada grupo de teoría e prácticas disporá dun horario de titoría grupal publicado en Moodle no que se garantirá resposta inmediata. Durante o resto do tempo, o profesorado atenderá permanentemente as cuestións expostas polo alumnado.

- Email: atención continuada ás mensaxes enviadas polos alumnos.

- Moodle: atención continuada ás mensaxes enviadas polos alumnos nos foros de Moodle.

4. Modificaciones na avaliación

Dado que o baremo de avaliación xa foi pensado para dar á avaliación continua o máximo peso que permite a memoria do título, a ponderación de cada factor non cambiaría.

*Observacións de avaliación:

A proba final realizarase online mediante Moodle de non ser posible a súa realización presencial de forma segura. As prácticas de laboratorio e os problemas entregaranse online e serán corrixidas e avaliadas de forma normal.

5. Modificacións da bibliografía ou webgrafía

Non se expoñen modificacións, xa que os contidos mantéñense.

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, los alumnos tendrán 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 los alumnos deberán 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 los alumnos tendrán que aplicar los conocimientos teóricos de la asignatura a casos concretos. Se garantizará la interactividad, resolviendo dudas por parte de los alumnos y animándolos 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 de los alumnos 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 aquellos alumnos que presenten mayores dificultades en la tarea del aprendizaje y con un apoyo adicional a aquellos 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. 60
 
Observaciones evaluación

Trabajos prácticos y solución de problemas

- De acuerdo con el artículo 14, apartado 4, de la normativa*, la entrega de trabajos no originales o con partes duplicadas (ya sea por plagio entre compañeros, por obtención de una misma fuente, etc.) conllevará una nota global de NO APTO en los trabajos, tanto al estudiante que
presente material copiado como a quien lo facilitase, y la
calificación de SUSPENSO en la convocatoria anual.

- Si las
prácticas u otras actividades se 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

- Los alumnos matriculados a tiempo parcial tendrán 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.


*
Normativa de avaliación, revisión e reclamación das cualificacións dos
estudos de grao e máster universitario, aprobada polo Consello de
Goberno da Universidade da Coruña o 19 de decembro de 2013.


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


(*) 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