Ficha Unidade Curricular (FUC)

Informação Geral / General Information

Carga Horária / Course Load

Área científica / Scientific area

480 - Informática

Departamento / Department

Departamento de Tecnologias Digitais

Ano letivo / Execution Year

2024/2025

Pré-requisitos / Pre-Requisites

Esta unidade curricular não tem pré-requisitos

Objetivos Gerais / Objectives

A UC de Algoritmos e Estruturas de Dados tem como principal objetivo dotar os alunos com conhecimentos aprofundados de técnicas de concepção e desenvolvimento de algoritmos e estruturas de dados, e introduzir a análise da complexidade e do desempenho dos algoritmos. São apresentados algoritmos de pesquisa e ordenação, baseados em estruturas de dados elementares, lineares ou hierárquicas, concebidas para suportar operações eficientes e viáveis do ponto de vista computacional.

Objetivos de Aprendizagem e a sua compatibilidade com o método de ensino (conhecimentos, aptidões e competências a desenvolver pelos estudantes) / Learning outcomes

OA1: Criar e manipular estruturas de dados OA2: Aplicar os algoritmos de ordenação e de pesquisa mais apropriados para um determinado problema OA3: Analisar a complexidade e o desempenho de um algoritmo OA4. Identificar, implementar e analisar as estruturas de dados e os algoritmos mais adequados a um determinado problema

Conteúdos Programáticos / Syllabus

CP1. A estrutura de dados Union-Find CP2. Análise de algoritmos CP3: Estruturas de dados: pilhas, filas, listas, sacos CP4: Ordenação elementar: selectionsort, insertionsort, shellsort CP5: Ordenação avançada: mergesort, quicksort, heapsort CP6. Complexidade dos problemas de ordenação CP7: Filas com prioridade CP8. Tabelas de símbolos elementares CP9. Árvores de pesquisa binária CP10. Árvores de pesquisa equilibradas CP11. Tabelas de dispersão

Demonstração da coerência dos conteúdos programáticos com os objetivos de aprendizagem da UC / Evidence that the curricular units content dovetails with the specified learning outcomes

O OA1, que se foca na criação e manipulação de estruturas de dados, é abordado através dos CPs que o Union-Find (CP1), pilhas, filas, listas, sacos (CP3), filas com prioridade (CP7), tabelas de símbolos elementares (CP8), árvores de pesquisa binária (CP9), árvores de pesquisa equilibradas (CP10) e tabelas de dispersão (CP11). O OA2, que visa a aplicação de algoritmos de ordenação e de pesquisa, é suportado pelos CPs que tratam da ordenação elementar (CP4), ordenação avançada (CP5) e árvores de pesquisa (CP9 e CP10). A análise da complexidade e desempenho de algoritmos (OA3) é diretamente abordada no CP2 (análise de algoritmos) e CP6 (complexidade dos problemas de ordenação). O OA4 é coberto por todos os CPs, garantindo que os alunos possuem uma compreensão abrangente e prática das estruturas de dados e algoritmos, desde os mais básicos aos mais avançados, aplicando-os conforme a necessidade do problema em questão.

Avaliação / Assessment

Época 1: Avaliação ao longo do semestre ou Exame Final Avaliação ao longo do semestre, sendo exigida a presença em pelo menos 3/4 das aulas: - 2 testes práticos (60%), com nota mínima de 7,5 em cada um. - 2 testes teóricos (40%), com nota mínima de 7,5 em cada um. A média final ponderada entre os testes teóricos e prático terá de ser igual ou superior a 9,5. Avaliação por Exame: - (100%) Exame Final com componente teórica e prática Os estudantes têm acesso à avaliação por Exame na Época 1 se a escolherem no início do semestre ou se reprovarem na avaliação ao longo do semestre. Época 2: Exame Final - (100%) Exame Final com componente teórica e prática Época Especial: Exame Final - (100%) Exame Final com componente teórica e prática

Metodologias de Ensino / Teaching methodologies

A Unidade Curricular segue metodologias ativas de aprendizagem, com ênfase em aprendizagem por problemas e aprendizagem por tarefas.

Demonstração da coerência das metodologias de ensino e avaliação com os objetivos de aprendizagem da UC / Evidence that the teaching and assessment methodologies are appropriate for the learning outcomes

A aprendizagem por problemas permite aos alunos criar e manipular estruturas de dados (OA1) através de desafios reais que exigem a implementação de pilhas, filas, listas e árvores de pesquisa. A aplicação de algoritmos de ordenação e pesquisa (OA2) é facilitada pela resolução de problemas específicos onde os alunos devem escolher e implementar algoritmos como mergesort, quicksort ou árvores de pesquisa equilibradas. A análise da complexidade e desempenho de algoritmos (OA3) é reforçada pela aprendizagem por tarefas, onde os alunos executam análises detalhadas de algoritmos em diferentes cenários, compreendendo a eficiência e limitações de cada abordagem. A identificação, implementação e análise das estruturas de dados e algoritmos mais adequados a um problema (OA4) são alcançadas através de tarefas práticas que exigem a seleção e aplicação de técnicas específicas para resolver problemas concretos.

Observações / Observations

-

Bibliografia Principal / Main Bibliography

Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2022). Introduction to Algorithms, Fourth Edition. Estados Unidos: MIT Press. Rocha, A. (2011). Estruturas de Dados e Algoritmos em Java. Portugal: FCA. Sedgewick, R., Wayne, K. (2014). Algorithms, Part II. Reino Unido: Pearson Education.

Bibliografia Secundária / Secondary Bibliography

Data da última atualização / Last Update Date

2024-09-04