Ficha Unidade Curricular (FUC)

Informação Geral / General Information


Código :
03725
Acrónimo :
DAAlg
Ciclo :
1.º ciclo
Línguas de Ensino :
Português (pt)
Língua(s) amigável(eis) :

Carga Horária / Course Load


Semestre :
2
Créditos ECTS :
6.0
Aula Teórica (T) :
0.0h/sem
Aula Teórico-Prática (TP) :
36.0h/sem
Aula Prática e Laboratorial (PL) :
18.0h/sem
Trabalho de Campo (TC) :
0.0h/sem
Seminario (S) :
0.0h/sem
Estágio (E) :
0.0h/sem
Orientação Tutorial (OT) :
1.0h/sem
Outras (O) :
0.0h/sem
Horas de Contacto :
55.0h/sem
Trabalho Autónomo :
95.0
Horas de Trabalho Total :
150.0h/sem

Á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