Algoritmos e Estruturas de Dados

Código:

L.EIC011

Sigla:

AED

Áreas Científicas
Classificação	Área Científica
OFICIAL	Engenharia Informática e Computação

Ocorrência: 2024/2025 - 1S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~pribeiro/aulas/aed2425/
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Licenciatura em Engenharia Informática e Computação

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
L.EIC	346	Plano Oficial	2	-	6	52	162

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

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

1. analisar a complexidade temporal e espacial de algoritmos;
2. analisar a correção de algoritmos simples;
3. conhecer os principais algoritmos de pesquisa e ordenação 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

Presencial

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

Weiss, Mark Allen; Data structures and algorithm analysis in C++. ISBN: 0-201-36122-1
Sedgewick, Robert; Algorithms in C++. ISBN: 0-201-35088-2
Thomas H. Cormen; Introduction to algorithms. ISBN: 978-0-262-53305-8 ((3ª ou 4ª edição))

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, em particular, de programação em C++, sendo os exercícios focados em temas tratados nas aulas teóricas.

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. Ao longo do semestre são realizados três pontos de avaliação individual: 2 testes práticos e 1 exame final escrito.

Software

CLion
Mooshak - A system for automatic evaluation of code
VSCode

Palavras Chave

Ciências Físicas > Matemática > Algoritmos
Ciências Físicas > Ciência de computadores > Programação

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Designação	Peso (%)
Teste	25,00
Trabalho laboratorial	5,00
Exame	70,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Estudo autónomo	55,00
Frequência das aulas	52,00
Trabalho laboratorial	55,00
Total:	162,00

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

A avaliação será baseada nas seguintes componentes:

- NP: nota prática, valendo 30% da nota final, obtida através de 3 componentes: 2 testes práticos de programação (2.5 valores cada) e uma componente contínua de resolução de exercícios ao longo do semestre (1 valor). Nota mínima: P>=1.5 (escala de 0 a 6).

- EN: nota do exame de época normal, valendo 70% da nota final, obtida através de um exame escrito com nota de 0 a 20.

Classificação da época normal: C = EN*0.7 + NP ≥ 9.5

- ER: na época de recurso será feito feito um único exame, com nota de 0 a 20, não sendo possível repetir o teste prático de programação ou as submissões.

Classificação da época de recurso: C = ER*0.7 + NP ≥ 9.5

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

Aplicam-se as mesmas regras aos estudantes inscritos ao abrigo de regimes especiais sem frequência de aulas práticas.

Melhoria de classificação

Na época de recurso da apenas pode ser melhorada a componente de exame (EN).

Estudantes do ano anterior podem manter a nota dos testes práticos desse ano (componente CIP), que será convertida na nota NP, que vale 30% da nota final.