Estruturas de Dados

Código:

CC1007

Sigla:

CC1007

Nível:

100

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciência de Computadores

Ocorrência: 2020/2021 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~pribeiro/aulas/edados2021/
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Licenciatura em Ciência de Computadores

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:B	3	Plano de Estudos Oficial	3	-	6	56	162
L:CC	97	Plano de estudos a partir de 2014	1	-	6	56	162
L:F	3	Plano de Estudos Oficial	2	-	6	56	162
			3
L:G	1	Plano estudos a partir do ano letivo 2017/18	2	-	6	56	162
			3
L:M	6	Plano de Estudos Oficial	2	-	6	56	162
			3
L:Q	2	Plano estudos a partir do ano letivo 2016/17	3	-	6	56	162
MI:ERS	132	Plano Oficial desde ano letivo 2014	1	-	6	56	162

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)