Disciplina Curricular

Algoritmos e Estrutura de Dados AED

Licenciatura Bolonha em Engenharia Electrónica - LEE 2021

Contextos

Grupo: LEE 2021 > 1º Ciclo > Área Principal

Período:

Peso

6.0 (para cálculo da média)

Objectivos

No final do curso, os estudantes deverão ser capazes de: 1. desenvolver e implementar A&ED e analisá-los no que respeita à sua correcção 2. compreender conceitos básicos de teoria da complexidade 3. analisar a eficiência dos A&ED com base em diferentes medidas, como o tempo e a memória 4. escrever programas que usem A&ED socorrendo-se de bons princípios de programação, como seja a especificação de API's e utilizar testes apoiados em A&ED 5. resolver problemas através da utilização de ED tais como listas simples, pilhas, filas, tabelas de dispersão, acervos, árvores binárias de procura e grafos e escrever programas para estas soluções 6. resolver problemas utilizando métodos de desenho e concepçáo de algoritmos, como abordagens "greedy", decomposição, programação dinâmica, "backtracking" e escrever programas para estas soluções 7. ser capaz de, desenhar a DS apropriada, criar um algoritmo que o resolva ou identificar o problema como um que não possa ser resolvido eficientemente

Programa

1. Análise básica Introdução à teoria da complexidade; Análise assimptótica de complexidade; Notações padrão; O teorema Mestre; As classes mais comuns de complexidade; Estimação empírica de complexidade; Complexidade em tempo e memória; Uso de recursão na análise de algoritmos; Análise de melhor, pior e caso médio 2. ED básicas: listas, pilhas, filas, tabelas de dispersão, acervos, árvores, grafos 3. Estratégias para desenvolvimento de A&ED Algoritmos de força bruta, "greedy", decomposição, "backtracking", heurísticas. 4. Algoritmos básicos Algoritmos numéricos simples, procura sequencial e binária, ordenação quadrática e O(N log N), tabelas de dispersão, árvores binárias de procura, representação de grafos, DFS, BFS e PFS, algoritmos de caminhos mais curtos (Dijkstra e Floyd), árvores de suporte mínimas (Prim e Kruskal)

Metodologia de avaliação

50% avaliação contínua; 50% avaliação não contínua

Disciplinas Execução