Estruturas de Dados
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Ciência de Computadores |
Ocorrência: 2017/2018 - 2S
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 |
Trabalho laboratorial |
30,00 |
Total: |
100,00 |
Obtenção de frequência
Para obter frequência é necessário não exceder limite de faltas nas aulas práticas e não exceder limite de faltas nos quizzes online semanais.
Fórmula de cálculo da classificação final
- P: nota prática, valendo 30% da nota final, obtida através de:
3 testes práticos de programação, em ambiente com computador (2 valores cada)
Nota mínima: 25% (minimo de 1.5 numa nota de 0 a 6 valores)
- E: nota de exame, valendo 70% da nota final, obtida através de um teste escrito com nota de 0 a 20.
Classificação da época normal: C = E*0.7 + P ≥ 9.5
- R: na época de recurso será feito feito um único exame, com nota de 0 a 20, não sendo possível repetir os testes práticos de programação.
Classificação da época de recurso: C = R*0.7 + P ≥ 9.5
Provas e trabalhos especiais
3 testes práticos de programação durante o semestre.