Datos Identificativos 2022/23
Asignatura (*) Deseño e Análise de Algoritmos Código 614G02011
Titulación
Grao en Ciencia e Enxeñaría de Datos
Descriptores Ciclo Período Curso Tipo Créditos
Grao 1º cuadrimestre
 Segundo Obrigatoria 6
Idioma
Castelán
Modalidade docente Presencial
Prerrequisitos
Departamento Ciencias da Computación e Tecnoloxías da Información
Coordinación
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
Descrición xeral 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 do título
Código Competencias do título
A4 CE4 - Coñecemento e aplicación dos fundamentos de programación e técnicas algorítmicas básicas para deseñar solucións a problemas, utilizando as linguaxes de programación máis relevantes no ámbito da ciencia e enxeñaría de datos.
A5 CE5 - Coñecemento de estruturas de datos e algoritmos básicos e capacidade para utilizalos eficientemente na resolución dun problema.
A6 CE6 - Capacidade para deseñar e programar algoritmos robustos e eficientes e saber analizar a idoneidade e complexidade dos mesmos.
B2 CB2 - Que os estudantes saiban aplicar os seus coñecementos ao seu traballo ou vocación dunha forma profesional e posúan as competencias que adoitan demostrarse por medio da elaboración e defensa de argumentos e a resolución de problemas dentro da súa área de estudo
B3 CB3 - Que os estudantes teñan a capacidade de reunir e interpretar datos relevantes (normalmente dentro da súa área de estudo) para emitir xuízos que inclúan unha reflexión sobre temas relevantes de índole social, científica ou ética
B7 CG2 - Elaborar adecuadamente e con certa orixinalidade composicións escritas ou argumentos motivados, redactar plans, proxectos de traballo, artigos científicos e formular hipóteses razoables.
B8 CG3 - Ser capaz de manter e estender formulacións teóricas fundadas para permitir a introdución e explotación de tecnoloxías novas e avanzadas no campo.
B9 CG4 - Capacidade para abordar con éxito todas as etapas dun proxecto de datos: exploración previa dos datos, preprocesado, análise, visualización e comunicación de resultados.
B10 CG5 - Ser capaz de traballar en equipo, especialmente de carácter multidisciplinar, e ser hábiles na xestión do tempo, persoas e toma de decisións.
C1 CT1 - Utilizar as ferramentas básicas das tecnoloxías da información e as comunicacións (TIC) necesarias para o exercicio da súa profesión e para a aprendizaxe ao longo da súa vida.

Resultados de aprendizaxe
Resultados de aprendizaxe Competencias do título
Saber analizar problemas e deseñar, programar e depurar algoritmos que os resolvan utilizando unha linguaxe de programación imperativa. A4
A5
 B2
B9
B10
 C1
Saber elixir e utilizar as estratexias de resolución de problemas máis relevantes. A4
A6
 B2
B3
B7
B8
B9
B10
 C1
Comprender os principios básicos do almacenamento de datos e a súa manipulación. A5
 B2
B8
B9
 C1
Coñecer e saber utilizar as estruturas de datos estándar en computación e os algoritmos máis relevantes para manipulalas. A5
 B2
B8
B9
 C1
Analizar a complexidade espacial e temporal dos algoritmos e recoñecer os aspectos chave da súa ineficiencia. A6
 B2
B3
B7
B8
B9
 C1

Contidos
Temas Subtemas
Análisis do coste de algoritmos Coste espacial e temporal
Regras e limitacións do análisis O
Paradigmas do deseño algorítmico Divide e vencerás
Programación dinámica
Algoritmos voraces
Estructuras de datos, algoritmos básicos e complexidade Procura en memoria principal e secundaria
Ordenación interna e externa
Exploración de grafos
Problemas NP-Completos NP-Completo e NP-Difícil
Heurísticas e algoritmos aproximados

Planificación
Metodoloxías / probas Competencias Horas presenciais Horas non presenciais / traballo autónomo Horas totais
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
Proba obxectiva A4 A5 A6 B2 B3 B8 B9 3 7.5 10.5
Sesión maxistral A5 A6 B2 B3 B8 B9 30 24 54
 
Atención personalizada 2 0 2
 
*Os datos que aparecen na táboa de planificación son de carácter orientativo, considerando a heteroxeneidade do alumnado

Metodoloxías
Metodoloxías Descrición
Prácticas de laboratorio Nas prácticas de laboratorio, os alumnos terán que solucionar problemas mediante a implementación e análise de algoritmos nunha linguaxe de alto nivel. As prácticas organizaranse en entregas periódicas para fomentar o estudo continuo e a avaliación continua. Ademais do código fonte, as entregas incluirán informes onde os alumnos deberán expor as conclusións obtidas sobre os algoritmos, en relación cos conceptos da materia, e que serán avaliados xunto cos propios programas entregados.
Solución de problemas Desenvolveranse exemplos e exercicios nos que os alumnos terán que aplicar os coñecementos teóricos da materia a casos concretos. Garantirase a interactividade, resolvendo dúbidas por parte dos alumnos e animándoos a contrastar as súas solucións e a expor cuestións relevantes. Parte dos problemas realizados serán avaliados.
Proba obxectiva Levarase a cabo unha avaliación da materia mediante unha proba que incluirá tanto preguntas sobre os contidos teóricos, como supostos prácticos e exercicios de aplicación relacionados cos distintos temas vistos na materia.
Sesión maxistral Clases maxistrais onde se exporán os conceptos teóricos da materia, sen perder nunca de vista exemplos de aplicación para motivar e contextualizar os contidos. Fomentarase a interactividade en clase mediante a formulación de preguntas e utilizaranse distintos recursos como encerado, transparencias ou demostracións.

Atención personalizada
Metodoloxías
Solución de problemas
Prácticas de laboratorio
Descrición
O desenvolvemento, tanto das clases maxistrais coma das de resolución de problemas e os laboratorios de prácticas, realizarase atendendo ao progreso dos alumnos nas capacidades de comprensión e asimilación dos contidos impartidos. O avance xeral da clase compaxinarase cunha atención específica a aqueles alumnos que presenten maiores dificultades na tarefa da aprendizaxe e cun apoio adicional a aqueles outros que presenten maior desenvoltura e desexen ampliar coñecementos.

No que respecta ás titorías individuais, dado o seu carácter personalizado, non deben dedicarse a estender os contidos con novos conceptos, senón a aclarar os conceptos xa expostos. O profesor utilizaraas como unha interacción que lle permita extraer conclusións respecto ao grao de asimilación da materia por parte dos alumnos.

Avaliación
Metodoloxías Competencias Descrición Cualificación
Solución de problemas A4 A5 A6 B2 B7 B10 C1 Valoraránse os resultados, forma e condicións de realización de diversos traballos puntuables que se detallarán durante o curso. 20
Prácticas de laboratorio A4 A5 A6 B2 B3 B7 B9 B10 C1 Realizadas segundo as condicións establecidas no enunciado de cada práctica. A entrega en tempo e forma das prácticas é condición necesaria para aprobar a materia na primeira oportunidade. 20
Proba obxectiva A4 A5 A6 B2 B3 B8 B9 Realización obrigatoria. Avaliarase o dominio dos coñecementos teóricos e operativos da materia. 60
 
Observacións avaliación

Traballos prácticos e solución de problemas

- Dado que se trata de actividades de avaliación continua, non se reavaliarán nin se admitirán entregas na segunda oportunidade. As cualificacións dos traballos prácticos e solución de problemas da primeira oportunidade conservaranse para a segunda oportunidade. 

- De acordo
ao artigo 14, apartado 4, da normativa*,a realización fraudulenta das probas ou actividades de avaliación,
unha vez comprobada, implicará directamente a cualificación de suspenso
"0" na materia na convocatoria correspondente, invalidando así calquera
cualificación obtida en todas as actividades de avaliación de cara a
convocatoria extraordinaria.

- 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.

Matrícula a tempo parcial

-
Os alumnos matriculados a tempo parcial terán que entregar as
actividades avaliables nas condicións e prazos específicos que se
establecerán. Será obriga do estudante comunicar a súa situación ao
profesorado.

Non presentado

- Quen non concurra á proba obxectiva no período oficial de avaliación terá a condición de “Non presentado” (NP). Na primeira oportunidade, esto será extensible a quen non entregue todas as prácticas en tempo e 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.


Fontes de información
Bibliografía 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

Bibliografía complementaria 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


Recomendacións
Materias que se recomenda ter cursado previamente
Matemática Discreta/614G02002
Fundamentos de Programación II/614G02009
Fundamentos de Programación I/614G02004

Materias que se recomenda cursar simultaneamente

Materias que continúan o temario
Procesamento da Linguaxe Escrita/614G02029
Procesamento Paralelo/614G02023
Recuperación de Información/614G02027
Procesamento de Imaxe, Vídeo e Audio/614G02028
Aprendizaxe Automática I/614G02019

Observacións


(*)A Guía docente é o documento onde se visualiza a proposta académica da UDC. Este documento é público e non se pode modificar, salvo casos excepcionais baixo a revisión do órgano competente dacordo coa normativa vixente que establece o proceso de elaboración de guías