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

2024/2025

Pré-requisitos / Pre-Requisites

Esta disciplina não tem pré-requisitos formais em termos de unidades curriculares (UCs) anteriores. Contudo, é aconselhável que os estudantes tenham tido aproveitamento nas UCs de Introdução à Programação e Algoritmos e Estruturas de Dados. Conhecimentos básicos de Probabilidade e de Cálculo são também aconselháveis.

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 unidade curricular focará em 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: Compreender os principais algoritmos e estruturas de dados utilizados em grafos.

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: incremental, dividir-e-conquistar, aleatoriedade, ávida (greedy), programação dinâmica. CP3: Grafos: estrutura de dados e algoritmos (á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: - Os conteúdos CP1 e CP2 são essenciais para atingir o objetivo OA1, uma vez que fornecem um conjunto de ferramentas para o desenho, a análise e a correção de algoritmos. - Os conteúdos CP2 e CP3 estão associados ao objetivo OA2 na medida em que fornecem um repertório de algoritmos para resolver uma grande variedade de problemas práticos. - O conteúdo CP1 está associado ao objetivo OA3 pois fornecem os conhecimentos teóricos necessários para a análise assintótica de algoritmos. - Os conteúdos CP2 e CP3 estão associados ao objetivo OA4 na medida em que fornecem um repertório de estratégias e algoritmos usados em grafos.

Avaliação / Assessment

A avaliação pode ser efetuada ao longo do semestre ou por exame final. Avaliação ao longo do semestre: E x 0.20 + T x 0.60 + M x 0.20 = 100%. (E) Exercícios semanais: - Matéria até a última aula dada. - Não tem nota mínima. (T) Testes intercalares: - 2 testes de igual ponderação e com nota mínima de 7.5 valores; - 1º teste: na semana intercalar; - 2º teste: no dia do exame de 1ª Época. (M) Minitrabalhos: - Realizados em grupo de 2 pessoas. - Não tem nota mínima. Exame final: 1ª, 2ª Épocas e Época Especial = 100%.

Metodologias de Ensino / Teaching methodologies

Sã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. A unidade curricular inclui: - 2 aulas teórico-práticas (3h00 por semana): Usadas para um enquadramento teórico e/ou para a resolução de exercícios teóricos (MEA1/MEA2/MEA3). - 1 aula prática-laboratorial (1h30 por semana): Usada para a resolução de exercícios e implementação prática dos algoritmos em Python (MEA3/MEA4). Além da assiduidade às aulas espera-se do aluno um tempo de trabalho autónomo de, aproximadamente, 7h00 semanais para consulta da bibliografia, revisão de matéria dada, resolução de exercícios e trabalhos propostos.

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 aulas Teórico-Práticas (TP) visam a compreensão e consolidação dos conteúdos programáticos através da utilização de exemplos práticos, essenciais para a concretização de todos os objectivos de aprendizagem (OA1-OA4). As aulas Prático-Laboratoriais (PL) e os métodos de avaliação visam a resolução autónoma de problemas, essencial para estimular o espírito crítico dos alunos na escolha do algoritmo mais adequado para resolver um dado problema e o seu poder de argumentação para justificar as suas decisões (OA1-OA4).

Observações / Observations

Bibliografia Principal / Main Bibliography

- Thomas Cormen, Charles Leiserson, Ronald L. Rivest and Clifford Stein (2022). Introduction to Algorithms. 34th ed., MIT Press. (CP1 e CP2) - Robert Sedgewick and Kevin Wayne (2011). Algorithms 4th Edition, Addison-Wesley. (CP3)

Bibliografia Secundária / Secondary Bibliography

- John Kleinberg and Eva Tardos (2005). Algorithm Design, Addison-Wesley. - Tim Roughgarden (2022). Algorithms Illuminated: Omnibus Edition. Cambridge: CUP. - David Williamson and David Shmoys (2010). The Design of Approximation Algorithms, Cambridge University Press.

Data da última atualização / Last Update Date

2024-07-29