Disciplina Curricular

Análise e Síntese de Algoritmos ASA

Licenciatura Bolonha em Engenharia Informática e de Computadores - Alameda - LEIC-A 2021

Contextos

Grupo: LEIC-A 2021 > 1º Ciclo > Área Principal

Período:

Peso

6.0 (para cálculo da média)

Objectivos

Formação de nível intermédio em algoritmia e complexidade, familiarizando os alunos com técnicas de análise e síntese de algoritmos e estruturas de dados. Conhecimento dos fundamentos da análise e síntese de algoritmos. Análise da realização prática de algoritmos e estruturas de dados. Perspectiva abrangente das aplicações dos algoritmos em Engenharia Informática.

Programa

Introdução à análise e síntese de algoritmos. Revisão de algoritmos de ordenação. Revisão de estruturas de dados: listas; pilhas; filas; filas com prioridade; tabelas de dispersão; árvores de procura binária; árvores equilibradas. Análise amortizada, e exemplos de aplicação. Algoritmos em grafos: algoritmos elementares, árvores abrangentes de menor custo, caminhos mais curtos, fluxos máximos. Introdução à Programação Linear e o algoritmo Simplex. Técnicas de síntese de algoritmos: programação dinâmica e algoritmos gananciosos. Algoritmos para emparelhamento de cadeias de caracteres. Complexidade computacional e caracterização de problemas. Classes de problemas P, NP, NP-completos e NP-díficeis.

Metodologia de avaliação

Exame e componente prática. O exame contribui com 60% para a nota final (FM) e o aluno tem de obter pelo menos 7.5 valores num dos exames. A componente prática contribui 40% para a nota final (FM).

Componente de Competências Transversais

Não existindo uma componente explícita de Competências Transversais a desenvolver no âmbito desta UC, o desenvolvimento da componente prática levará ao desenvolvimento de Pensamento Crítico e Inovador e Competências Intrapessoais.

Componente Laboratorial

Exercícios e problemas a resolver em todas as aulas no seguimento das matérias aprendidas nas aulas teóricas.

Componente de Programação e Computação

No curso onde esta UC é oferecida estão asseguradas as componentes de Computação e Programação de acordo com o MEPP 2122.

Princípios Éticos

Todos os membros de um grupo são responsáveis pelo trabalho do grupo. Em qualquer avaliação, todo aluno deve divulgar honestamente qualquer ajuda recebida e fontes usadas. Numa avaliação oral, todo aluno deverá ser capaz de apresentar e responder a perguntas sobre toda a avaliação.

Disciplinas Execução

2021/2022 - 1º Semestre