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)
Pré-requisitos
Aprovação à disciplina de nível introdutório em Programação
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
Componente de Competências Transversais
As competências transversais são bastante relevantes neste curso. Basicamente assentam no trabalho de laboratório e no trabalho conducente ao projecto ao longo do semestre. No laboratório os alunos irão trabalhar em grupos e desenvolver relações interpessoais, necessárias para atingir um objectivo comum. Para a realização do projecto, a gestão do tempo e a criatividade serão também essenciais, assim como a capacidade de escrever um relatório claro e conciso sobre o trabalho desenvolvido e uma análise compreensiva e extensiva das suas capabilidades. Valores éticos são também uma parte muito importante do desenvolvimento do projecto, na medida em que os alunos terão de aprender a cooperar de forma aberta enquanto têm de seguir regras estritas que requerem ser completamente e exclusivamente desenvolvido por eles o trabalho apresentado ou, quando incorporem partes feitas por outrém, que o refiram clara e inequivocamente.
Componente Laboratorial
Grupos de dois alunos terão de realizar um total de 6 trabalhos de laboratório.
Componente de Programação e Computação
Esta é a segunda unidade curricular em Computação e Programação que está definida pela Comissão de Computação e Programação. Assim, toda a avaliação inclui análise de competências de computação e programação.
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.