Algoritmos e Estruturas de Dados

Ocorrência: 2022/2023 - 1S

Ciclos de Estudo/Cursos

A ficha foi alterada no dia 2022-09-11.

Campos alterados: Fórmula de cálculo da classificação final, Melhoria de classificação, Provas e trabalhos especiais

Língua de trabalho

Objetivos

No final da unidade curricular, os estudantes deverão ser capazes de:

1. analisar (e medir experimentalmente) a complexidade temporal e espacial de algoritmos;
2. analisar (e testar experimentalmente) a correção de algoritmos simples;
3. conhecer os principais algoritmos de pesquisa e ordenação em arrays e a sua complexidade;
4. compreender o conceito de tipo abstrato de dados e saber organizar programas em torno desse conceito;
5. conhecer as estruturas de dados fundamentais (e algoritmos associados e respetiva complexidade) usadas para implementar eficientemente tipos abstratos de dados comuns em bibliotecas de coleções;
6. saber escolher coleções, estruturas de dados e algoritmos apropriados para resolver problemas práticos;
7. escrever programas em C++ que implementam e usam as estruturas de dados e algoritmos fundamentais

Resultados de aprendizagem e competências

No final da unidade curricular, os estudantes deverão ter competência para: modelar problemas recorrendo ao paradigma da orientação por objetos; resolver problemas fazendo uso de tipos de dados abstratos e estruturas de dados simples lineares e não lineares.

Modo de trabalho

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

O estudante deve possuir conhecimentos básicos de programação e linguagem C++.

Programa

Conceitos e técnicas básicas: complexidade temporal e espacial de algoritmos; tipos abstratos de dados; análise da correção de algoritmos.
Algoritmos de pesquisa e ordenação em arrays.
Estruturas de dados lineares e sua implementação: pilhas, filas e listas.
Estruturas de dados hierárquicos e sua implementação: árvores binárias; árvores binárias de pesquisa; árvores binárias equilibradas. Aplicações
Tabelas de dispersão e algoritmos de manipulação.
Filas de prioridade e heaps binários
Algoritmos básicos em grafos: tipos de grafos; representação; pesquisa em largura e em profundidade. Aplicações: ordenação topológica; ciclos; conetividade

Bibliografia Obrigatória

Bibliografia Complementar

Métodos de ensino e atividades de aprendizagem

As aulas teóricas são usadas para exposição formal da matéria, acompanhada da apresentação de exemplos e sua discussão.

Nas aulas práticas são resolvidos exercícios de programação em C++, sendo os exercícios focados em temas tratados nas aulas teóricas. As resoluções são geralmente efetuadas em grupos de estudantes, sendo fomentada a discussão sobre as propostas de solução que vão sendo  apresentadas.

A avaliação é realizada ao longo do semestre, em datas previamente anunciadas, onde os estudantes são continuamente avaliados a nível teórico e prático, a nível individual e de grupo. Ao longo do semestre são realizados três pontos de avaliação individual, que incluem questões de índole teórica e realização de exercícios individuais em computador. Ao longo do semestre são também propostos dois projetos de programação a realizar em grupo, fomentando assim a capacidade de trabalho em equipa. O desenvolvimento destes projetos é feito essencialmente fora das aulas, com apanhamento regular.

Software

Palavras Chave

Tipo de avaliação

Componentes de Avaliação

Componentes de Ocupação

Obtenção de frequência

Condições para obtenção de frequência: não exceder o limite de faltas estabelecido nas normas gerais (25% do número de aulas práticas e teórico-práticas previstas)

Fórmula de cálculo da classificação final

Provas e trabalhos especiais

A avaliação em Época Especial inclui duas componentes (CE e CT):

• Componente de Exame (CE) (60%), inclui:

• uma parte prática de programação usando testes unitários (CEP)
• uma parte teórica (CET)

• Componente de Trabalho Prático(CT) (40%), relativo à implementação de um mini-projeto e elaboração do respetivo relatório. O Trabalho Prático deverá ser entregue até à data do exame e os estudantes devem contactar o regente da UC para escolha do trabalho a implementar.

Classificação final = CE*0,6 + CT*0,4.

Para aprovação na disciplina, o estudante deve obter uma classificação mínima de 40% em qualquer das componentes CEP, CET e CT.

Avaliação especial (TE, DA, ...)

Os estudantes inscritos ao abrigo de regimes especiais sem frequência de aulas práticas:

• podem efetuar a Componente de Grupo (CG) de avaliação constituindo grupo com outros colegas ou sozinhos, devendo acordar com os docentes o trabalho a realizar e as datas de avaliação dos mesmos
• devem realizar a avaliação individual CIP e CIT nas datas estipuladas.

Melhoria de classificação

A classificação da componentes de trabalho prático, CG, só pode ser melhorada por frequência da unidade curricular no ano letivo seguinte.