Currículo

Desenho e Análise de Algoritmos DAAlg

Contextos

Groupo: EI PL - 2020 > 1º Ciclo > Unidades Curriculares Obrigatórias

ECTS

6.0 (para cálculo da média)

Objectivos

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.

Programa

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

Método de Avaliação

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

Carga Horária

Carga Horária de Contacto -

Trabalho Autónomo - 95.0

Carga Total -

Bibliografia

Principal

- 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):

Secundária

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