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: 2018/2019 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~pribeiro/aulas/edados1819/
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	0	Plano de Estudos Oficial	3	-	6	56	162
L:CC	92	Plano de estudos a partir de 2014	1	-	6	56	162
L:F	1	Plano de Estudos Oficial	2	-	6	56	162
			3
L:G	2	Plano estudos a partir do ano letivo 2017/18	2	-	6	56	162
			3
L:M	2	Plano de Estudos Oficial	2	-	6	56	162
			3
L:Q	7	Plano estudos a partir do ano letivo 2016/17	3	-	6	56	162
MI:ERS	155	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
Trabalho laboratorial	30,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Frequência das aulas
Total:	0,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.