Algoritmos e Estruturas de Dados

Imagem d@ Carlos Manuel Chôrro Simões Barrico [Ficheiro Local]
Carlos Manuel Chôrro Simões Barrico
Código:
9102
Ano:
2
Semestre:
S2
Créditos ECTS:
6
Carga Horária:
PL(30H)/T(30H)
Área Científica:
Informática
Tipo de ensino:
Presencial.
Estágios:
Não Aplicável.
Objectivos de Aprendizagem:
Os principais objetivos desta Unidade Curricular são:
- adquirir conhecimentos sobre algoritmia, em particular algoritmos recursivos, de ordenação, de pesquisa e tabelas de Hash, e análise de complexidade dos algoritmos;
- compreender os conceitos fundamentais associados aos vários tipos de estruturas de dados sequenciais (listas ligadas) e não sequenciais (árvores binárias), e dos algoritmos passíveis de aplicação a cada estrutura.

No final da Unidade Curricular o estudante deve ser capaz de
- desenvolver competências de algoritmia, em particular em problemas que envolvam recursividade, ordenação e/ou pesquisa;
- analisar a eficiência dos algoritmos, através da respetiva análise de complexidade, de forma a usar os algoritmos mais eficientes na resolução do problema em questão;
- idealizar, esquematizar e implementar estruturas de dados e respectivos algoritmos com vista à resolução de problemas.
Conteúdos programáticos:
A - COMPLEXIDADE COMPUTACIONAL DOS ALGORITMOS
1. Big-O
2. Análise Amortizada
B - ESTRUTURAS ABSTRATAS DE DADOS
1. Listas
2. Pilhas
3. Filas
4. Árvores binárias
5. Árvores binárias de pesquisa
C - ÁRVORE BINÁRIA DE PESQUISA BALANCEADA
1. Inserção binária
2. Adelson-Velskii Landis (AVL)
3. Vermelho-Preto (Red-Black)
D - ÁRVORE DE PESQUISA BALANCEADA
1. Árvore 2-3
2. Árvores de Intervalos
E - FILAS DE PRIORIDADE (HEAPS)
1. Binário
2. Binomial
3. Fibonacci
F - GRAFOS
1. Tipos de grafos
2. Representação computacional de um grafo
3. Algoritmos de pesquisa em grafos: em profundidade primeiro e em largura primeiro
4. Problemas envolvendo grafos: Árvore Abrangente Mínima, Caminho Mais Curto, Fluxo Máximo e Emparelhamento Estável
G - STRINGS
1. Conjuntos de Strings
2. Ordenação de Strings: Ordenação por Radix
3. Pesquisa de Strings: Pesquisa Binária
4. Pesquisa de uma substring numa String: Knuth-Morris-Pratt e Boyer-Moore
5. Prefix Tree, Suffix Tree e Suffix Arrays
Metodologias de Ensino e Critérios de Avaliação:
Para que o estudante possa adquirir as competências exigidas, estão previstas:
- 2h/semana de aulas teóricas (T) para exposição oral dos conceitos teóricos, métodos e algoritmos, utilizando-se ainda a escrita no quadro, a discussão de ideias com os alunos, e a projeção de diapositivos;
- 2h/semana de aulas prático-laboratoriais (PL), nas quais o estudante aplicará e testará os conceitos, os métodos e os algoritmos apresentados nas aulas teóricas, através da resolução de exercícios que constam em fichas criadas para o efeito;
- 2h/semana de tutoria para o esclarecimento de dúvidas e para o acompanhamento dos alunos no desenvolvimento dos seus projetos individuais.
Avaliação:
- 2 mini-testes práticos; cada um vale 2.0 valores.
- 2 testes escritos; cada teste vale 8.0 valores;

Teste escrito 1: 16/04/2024, 18h
Teste escrito 2: 21/05/2024, 18h
Bibliografia principal:
Bibliografia principal:
- "Estruturas de Dados e Algoritmos em C", Tecnologias de Informação, António Manuel Adrego da Rocha, FCA - Editora Informática, 2008
- "Linguagem C", Luís Damas, FCA - Editora de Informática, 1999
Bibliografia complementar:
- "Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms", By Robert Sedgewick, Addison-Wesley Professional; 3rd Edition, 2001
- "Elementos de Programação com C", 3ª Edição Actualizada e Aumentada, Pedro Guerreiro, FCA - Editora Informática, 2006
Língua:
Português
Esta informação promove os seguintes Objetivos de Desenvolvimento Sustentável da ONU:
Garantir o acesso à educação inclusiva, de qualidade e equitativa, e promover oportunidades de aprendizagem ao longo da vida para todos