Ficha Unidade Curricular (FUC)
Informação Geral / General Information
Carga Horária / Course Load
Área científica / Scientific area
Ciências e Tecnologias da Programação
Departamento / Department
Departamento de Ciências e Tecnologias da Informação
Ano letivo / Execution Year
2023/2024
Pré-requisitos / Pre-Requisites
Conhecimentos previstos nas UCs de Introdução à Programação e Algoritmos e Estruturas de Dados. Conhecimentos básicos de Probabilidade e de Cálculo.
Objetivos Gerais / Objectives
Pretende-se prover os estudantes de proficiência no desenho de algoritmos eficientes para problemas em diferentes contextos e domínios. A UC focará algoritmos fundamentais, métodos de desenho de algoritmos, estruturas de dados e análise de algoritmos. Os estudantes irão conhecer noções fundamentais em Teoria da Complexidade de Algoritmos e compreender as grandes estratégias de Desenho de Algoritmos, para uso eficiente dos recursos, quer em casos de utilização de dados em larga escala, quer para dar solução a problemas inerentemente duros (NP-hard). Para isso, será proposta a resolução de problemas específicos de várias áreas de aplicação, usando estruturas de dados adequadas.
Objetivos de Aprendizagem e a sua compatibilidade com o método de ensino (conhecimentos, aptidões e competências a desenvolver pelos estudantes) / Learning outcomes
Ao completar com sucesso esta unidade curricular, o estudante estará apto a: OA1: Identificar as estratégias mais apropriadas para o problema a resolver. OA2: Construir e implementar os algoritmos necessários para a resolução pretendida. OA3: Analisar a complexidade de diferentes algoritmos e perceber o que isso pode implicar na aplicação desses algoritmos a problemas reais. OA4: Entender as implicações do uso de algoritmos versus heurísticas.
Conteúdos Programáticos / Syllabus
Os conteúdos programáticos (CP) são: CP1- Análise de algoritmos e Teoria da Complexidade: casos para análise e algoritmos de aproximação. CP2- Estratégias de desenho de algoritmos: Dividir-e-Conquistar (Divide-and-Conquer), Programação Dinâmica (Dynamic Programming), Ávida (Greedy), Aleatoriedade (Randomization). CP3- Grafos: representação, árvores de cobertura, travessias, caminhos mais curtos, algoritmos de fluxo.
Demonstração da coerência dos conteúdos programáticos com os objetivos de aprendizagem da UC / Evidence that the curricular units content dovetails with the specified learning outcomes
Os conteúdos programáticos (CP) estão alinhados com os objectivos de aprendizagem (OA) da UC através das seguintes dependências OA1: CP1, CP2, CP3 OA2: CP2 e CP3 OA3: CP1 OA4: CP1 e CP2
Avaliação / Assessment
Avaliação periódica: E x 0.20 + T x 0.60 + M x 0.20 = 100% (a) Exercícios semanais (E): - Matéria até a última aula dada. (b) Testes intercalares (T): - 2 testes (de igual ponderação); - 1º teste: na semana intercalar; - 2º teste: no dia do exame de 1ª Época. (c) Minitrabalhos (M): - 2 minitrabalhos (de igual ponderação); - Realizados em grupo de 2 pessoas. Exame: 1ª, 2ª Épocas e Época Especial = 100%.
Metodologias de Ensino / Teaching methodologies
Serão utilizadas as seguintes metodologias de ensino-aprendizagem (MEA): MEA1: Expositivas, para apresentação do enquadramento teórico. MEA2: Ilustrativas, para exemplificação dos conceitos teóricos em contextos reais. MEA3: Argumentativas, com apresentação e discussão do trabalho de grupo ou de resoluções de exercícios. MEA4: Ativas, com resolução prática de exercícios de aplicação.
Demonstração da coerência das metodologias de ensino e avaliação com os objetivos de aprendizagem da UC / Evidence that the teaching and assessment methodologies are appropriate for the learning outcomes
As metodologias de ensino são as necessárias para cumprir os objetivos de aprendizagem, bem como para estimular o espírito crítico e para que apreendam técnicas de comunicação e apresentação de processos e resultados. Uma vez que as técnicas pedagógicas usadas serão orientadas à resolução de problemas, as aulas estão classificadas como Teórico-Práticas e laboratoriais.
Observações / Observations
Bibliografia Principal / Main Bibliography
Cormen, Thomas, Charles Leiserson, Ronald L. Rivest and Clifford Stein (2022), Introduction to Algorithms. 34th ed., MIT Press. John Kleinberg Eva Tardos (2005) Algorithm Design, Addison-Wesley. Tim Roughgarden (2022). Algorithms Illuminated: Omnibus Edition. Cambridge: CUP.
Bibliografia Secundária / Secondary Bibliography
David Williamson, David Shmoys (2010) The Design of Approximation Algorithms, Cambridge University Press.
Data da última atualização / Last Update Date
2024-02-16