Estruturas de Dados
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Ciência de Computadores |
Ocorrência: 2020/2021 - 2S
![Requerida a integração com o Teams Ícone do Teams](/fcup/pt/imagens/Spacer)
Ciclos de Estudo/Cursos
Língua de trabalho
Português
Objetivos
Pretende-se que o estudante reforce competências de programação, fique a conhecer algumas das principais estruturas de dados e algoritmos associados, e ganhe competências básicas na concepção e análise de algoritmos.
Resultados de aprendizagem e competências
Os principais objectivos de aprendizagem são:
- Proeficiência na linguagem Java e no paradigma de programação orientada a objectos;
- Conhecimento das principais estruturas de dados básicas: arrays, matrizes, listas ligadas e árvores binárias;
- Conhecimento dos principais tipos abstractos de dados e suas implementações: filas, pilhas, conjuntos, dicionários e filas de prioridade;
- Competência básica na análise de complexidade de algoritmos e e compreensão das principais classes de complexidade;
- Enriquecimento do conhecimento sobre algumas técnicas algorítmicas como recursividade, pesquisa com retrocesso e dividir para conquistar;
- Experiência prática de aplicação a problemas concretos.
Modo de trabalho
Presencial
Programa
- Conceitos Fundamentais de Java:
. Classes, objectos, atributos e métodos
. Tipos primitivos, Strings, wrappers, arrays e tipos enumerados
. Expressões, operadores e instruções de controle de fluxo
. Input/Output e a classe Scanner
. Pacotes e biblioteca padrão do Java
. Princípios de desenvolvimento de software, estilo e documentação
- Programação Orientada a Objectos:
. Objectivos, princípio, padrões e mecanismo de herança
. Interfaces e Tipos Abstractos de Dados (TADs)
. Uso de genéricos e de iteradores
- Conceitos de Análise Assintótica:
. Noções de análise assintótica
. Classes de complexidades típicas e sua comparação
. Exemplos de análise de algoritmos
- Técnicas de Desenho de Algoritmos:
. Programaçao estruturada
. Recursividade
. Pesquisa exaustiva e backtracking
. Dividir para conquistar
- Estruturas de Dados Fundamentais:
. Arrays e matrizes
. Listas ligadas simples, circulares e duplamente ligadas
. Árvores binárias, árvores de pesquisa e heaps
- Tipos Abstratos de Dados e suas possíveis Implementações
. Sequências, pilhas, filas e deques:
. Contentores associativos: conjuntos e dicionários
. Filas de prioridade
Bibliografia Obrigatória
Goodrich Michael T.;
Data structures and algorithms in Java. ISBN: 0-471-73884-0
Bibliografia Complementar
Sedgewick Robert;
Introduction to programming in Java. ISBN: 978-0-321-49805-2
Cormen Thomas H. 070;
Introduction to algorithms. ISBN: 978-0-262-03384-8
Métodos de ensino e atividades de aprendizagem
Aulas teóricas expositivas incluindo sessões de live coding. Aulas práticas com exercícios de programação.
Tipo de avaliação
Avaliação distribuída com exame final
Componentes de Avaliação
Designação |
Peso (%) |
Exame |
70,00 |
Teste |
30,00 |
Total: |
100,00 |
Componentes de Ocupação
Designação |
Tempo (Horas) |
Frequência das aulas |
56,00 |
Estudo autónomo |
66,00 |
Trabalho laboratorial |
40,00 |
Total: |
162,00 |
Obtenção de frequência
Para obter frequência é necessário ter feito pelo menos 50% dos quizzes online semanais.
Fórmula de cálculo da classificação final
- NP: nota prática, valendo 30% da nota final, obtida através de:
2 testes práticos de programação, em ambiente Mooshak (6 valores, 30% da nota final)
- EN: nota do exame de época normal, valendo 70% da nota final, obtida através de um exame escrito (presencial) 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 (presencial), 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
Provas e trabalhos especiais
2 testes práticos de programação durante o semestre.
Melhoria de classificação
Contactar o docente (pode ser melhorada só a componente prática, só a componente teórica ou ambas)