Algoritmia e Estrutura de Dados
- Detalhes
- Categoria: Disciplina
- Sedgewick R., Wayne K. (2011). Algorithms. Addison-Wesley.
- Engenharia Informática (ISMAT)
- 587
- 13558
- Algoritmia e Estrutura de Dados
- ISMAT587-13558
- 2
- 6
- 0
- 12
- Não
- Português
- O conteúdo lecionado é aplicado usando programação. São utilizadas metodologias ativas, orientadas à resolução de problemas (PBL). No final de cada parte são desenvolvidos projetos integrando todos os conteúdos lecionados.
- Obrigatório
- OA1. Compreender e aplicar os métodos de análise de algoritmos iterativos e recursivos. OA2. Compreender e identificar estratégias essenciais para a conceção de algoritmos. OA3. Dominar estruturas de dados avançadas e algoritmos fundamentais sobre as mesmas. OA4. Compreender a influência do desenho/escolha de um algoritmo e/ou estrutura de dados na performance da resolução de um problema. OA5. Conhecer e identificar problemas intratáveis, bem como algoritmos que apresentam uma solução aproximada para os mesmos.
- CP1. Pesquisa sequencial. CP2. Pesquisa binária. CP3. Fundamentos de análise de algoritmos. Análise do melhor caso, pior caso, caso médio. Crescimento de funções. Complexidade assintótica. Notações. Recorrências e respetiva resolução. Árvores de recursão. Método de Master. CP4. Revisão de métodos de ordenação simples: seleção, inserção e bolha. CP5. Métodos de ordenação merge sort e quicksort (recursivo). CP6. Divisão e conquista. CP7. Método de ordenação Heapsort. Min e Max-heap. CP8. Métodos de ordenação em tempo linear. Counting sort, Radix sort, Bucket sort. CP9. Estratégias de concepção de algoritmos. Divisão e conquista (revisitado). Algoritmos "greedy". Programação dinâmica. CP10. Análise Amortizada. CP11. Estruturas de Dados Avançadas. Filas de Prioridade (Min e Max-Priority) Árvores Binárias de Pesquisa. BSTs equilibradas. Grafos. Hashing.
Descrição dos instrumentos de avaliaão (individuais e de grupo): testes, trabalhos práticos e ponderação na nota final.
Descrição
Data limite
Ponderação
Teste de avaliação
a marcar
60%
TP1
a marcar
20%
TP2
a marcar
20%
O teste de avaliação é individual e os trabalhos práticos são em grupo (no máximo 2 elementos). O TP1 consiste num desafio sobre estratégias e concepção de algoritmos.
O TP2 consiste num desafio que inclue a aplicação dos conceitos sobre estruturas de dados.
O teste de avaliação inclui toda a matéria leccionada.
- Semestral
- Em programação os temas repetem-se e as soluções também, por isso é indispensável compreender e saber aplicar os métodos estudados que apresentam a melhor solução para problemas bem conhecidos. A UC Algoritmos e Estruturas de Dados aborda o estudo das estruturas de dados fundamentais e dos algoritmos clássicos, utilizados em programação. A correta utilização dos algoritmos e estruturas de dados permite obter programas escritos de uma melhor forma, com menos erros e optimizado o tempo de execução e memória alocada.
