2024
Estruturas de Dados e Algoritmos I
Nome: Estruturas de Dados e Algoritmos I
Cód.: INF13188L
6 ECTS
Duração: 15 semanas/156 horas
Área Científica:
Informática
Língua(s) de lecionação: Português
Língua(s) de apoio tutorial: Português
Objetivos de Desenvolvimento Sustentável
Objetivos de Aprendizagem
Introduzir os conceitos de estruturas de dados e análise de algoritmos. Definir e analisar a complexidade de tipos abstractos de dados elementares como listas, pilhas, filas, árvores, tabelas de dispersão e amontoados. Compreender e analisar os principais algoritmos de ordenação.
Conteúdos Programáticos
I Introdução à análise de algoritmos: Complexidade Espacial e Temporal; Melhor caso, pior caso e caso esperado; As anotações O maiúsculo, Omega e Teta; Análise de algoritmos iterativos e recursivos
II Tipos Abstractos de Dados:
1. Listas, Pilhas, Filas: comportamento e uso das estruturas de dados
2. Árvores, Árvores Binárias, ABPs e AVLs: comportamento e uso das estruturas de dados
III Filas com prioridade: Heaps binários; construção de um heap a partir de um vector
IV Tabelas de Dispersão: Funções de Dispersão; Encadeamento separado; Colisões e estratégias de resolução: dispersão linear, quadrática e dispersão dupla Rehasing
V O problema da ordenação: Apresentação, análise do comportamento de Bubblesort, Insertion sort, Mergesort, Heapsort, Quicksort e Bucketsort.
II Tipos Abstractos de Dados:
1. Listas, Pilhas, Filas: comportamento e uso das estruturas de dados
2. Árvores, Árvores Binárias, ABPs e AVLs: comportamento e uso das estruturas de dados
III Filas com prioridade: Heaps binários; construção de um heap a partir de um vector
IV Tabelas de Dispersão: Funções de Dispersão; Encadeamento separado; Colisões e estratégias de resolução: dispersão linear, quadrática e dispersão dupla Rehasing
V O problema da ordenação: Apresentação, análise do comportamento de Bubblesort, Insertion sort, Mergesort, Heapsort, Quicksort e Bucketsort.
Métodos de Ensino
Aulas teóricas e aulas práticas com problemas que acompanham a matéria teórica. Disponibilização de uma série de exercícios, de dificuldade gradual, cobrindo os tópicos ensinados, para os alunos praticarem o seu domínio da matéria.
Avaliação
A avaliação tem uma componente teórica(70%) e uma componente prática(30%).
A componente teórica é constituída por 2 testes(35% cada) ou em alternativa, um exame(70%). Podem ainda os alunos realizar um exame de recurso, para realizar melhoria da nota da componente teórica ou obter avaliação relativamente a esta componente.
A componente prática é concretizada através da realização de projectos práticos realizados no decorrer do semestre.
A componente teórica é constituída por 2 testes(35% cada) ou em alternativa, um exame(70%). Podem ainda os alunos realizar um exame de recurso, para realizar melhoria da nota da componente teórica ou obter avaliação relativamente a esta componente.
A componente prática é concretizada através da realização de projectos práticos realizados no decorrer do semestre.
Bibliografia
Data Structures and Problem Solving using Java, Mark Allen Weiss. Addison-Wesley
Equipa Docente (2023/2024 )
