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: 2024/2025 - 1S

Ativa?	Sim
Página Web:	https://www.dcc.fc.up.pt/~fds/aulas/EDados/2425/index.html
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	4	Plano de Estudos Oficial	3	-	6	48	162
L:BIOINF	25	Plano de Estudos Oficial	2	-	6	48	162
L:CC	99	Plano estudos a partir do ano letivo 2021/22	2	-	6	48	162
L:F	3	Plano de Estudos Oficial	3	-	6	48	162
L:G	0	Plano estudos a partir do ano letivo 2017/18	2	-	6	48	162
			3
L:IACD	97	Plano Oficial a partir do ano letivo 2021/22	2	-	6	48	162
L:M	19	Plano de Estudos Oficial	2	-	6	48	162
			3
L:MA	0	Plano de Estudos Oficial	3	-	6	48	162
L:Q	1	Plano estudos a partir do ano letivo 2016/17	3	-	6	48	162

Língua de trabalho

Português

Objetivos

Reforçar as competências de programação dos estudantes, com ênfase no desenho e implementação de algumas das principais estruturas de dados e correspondentes algoritmos. Será usada uma metodologia orientada aos objectos com recurso à linguagem Java. Serão introduzidas noções sobre eficiência e análise de complexidade de algoritmos.

Resultados de aprendizagem e competências

Ao concluirem esta unidade curricular os estudantes deverão saber:

• usar os princípios básicos de uma linguagem de programação orientada aos objectos, nomeadamente herança, polimorfismo, interfaces, classes do tipo colecção e iteradores.


• escrever classes que implementem algumas estruturas de dados lineares, como sejam listas, pilhas, filas, conjuntos, dicionários, tabelas de hash e árvores binárias.


• usar uma API que implemente listas, pilhas, filas, conjuntos, e tabelas de hash.


• desenvolver algoritmos básicos associados às estruturas de dados estudadas.


• usar algumas das técnicas algoritmicas, nomeadamente recursividade, pesquisa com retrocesso e dividir-para-conquistar.


• fazer a análise de complexidade de algoritmos e identificar as principais classes de complexidade (competência básica).


• aplicar os conhecimentos na resolução prática de problemas concretos.

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

Possuir competência básica de programação normalmente adquirida nas unidades curriculares de programação do 1º ano.

Programa

1. Conceitos fundamentias da linguagem 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.


2. Princípios de programação orientada aos objectos: padrões e mecanismo de herança, hierarquia de classes, polimorfismo, interfaces e Tipos Abstractos de Dados (TADs), uso de genéricos e iteradores.


3. Noções básicas de análise de algoritmos: análise asintótica; classes de complexidade típicas e sua comparação; exemplos de análise de algoritmos.


4. Técnicas de desenho de algoritmos: programação estruturada; recursividade; pesquisa exaustiva e backtracking; dividir para conquistar.


5. Estruturas de dados fundamentais: vectores e matrizes; listas ligadas simples, circulares e duplamente ligadas; árvores binárias, árvores de pesquisa e heaps.


6. Tipos Abstractos de Dados e suas possíveis implementações: sequências, pilhas, filas, e deques; contentores associativos: conjuntos e dicionários; filas de prioridade.


7. Métodos de ordenação: inserção, bolha, merge-sort, quicksort.


8. Métodos de pesquisa: pesquisa binária em vectores ordenados, pesquisa em listas, pesquisa em profundidade e em largura em árvores.

Bibliografia Obrigatória

Goodrich Michael T.; Data structures and algorithms in Java. ISBN: 0-471-73884-0
Stuart Reges and Marty Stepp; Building Java Programs: a Back to Basics Approach, Pearson, 2020 (5a edição (http://www.buildingjavaprograms.com/))

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

Exposição dos conceitos associados à programação orientada a objectos, estruturas de dados e algoritmos associados. Resolução de problemas de aplicação prática das estruturas de dados e algoritmos dados.

Aulas Práticas
As aulas práticas serão usadas para apoio aos estudantes nas dúvidas concretas que apresentem sobre a resolução dos exercícios propostos. As aulas envolverão:

• O uso da linguagem de programação Java.
• A resolução de exercícios propostos para treino de programação.
• A resolução de exercícios propostos para efeitos de avaliação.
• A resolução de quizzes de escolha múltipla para efeitos de obtenção de frequência.

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	70,00
Teste	25,00
Participação presencial	5,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Frequência das aulas	48,00
Estudo autónomo	66,00
Trabalho laboratorial	48,00
Total:	162,00

Obtenção de frequência

Perdem frequência os estudantes que não tenham respondido a pelo menos 50% dos questionários online (quizzes) e uma assiduidade às aulas superior a 50% das aulas dadas.

Fórmula de cálculo da classificação final

A avaliação tem em conta as seguintes provas:

• (E) Exame escrito (época normal e recurso): 70% da nota-final.
  Avaliação teórico-prática sem recurso a consulta ou computador, classificada de 0 a 20.
• (P) Prática de resolução de problemas (2 avaliações práticas): 25% da nota final.
  Cada avaliação prática valerá 2.5 valores. Os problemas serão de dificuldade similar aos problemas de treino disponibilizados nas aulas práticas.
• (R) Resolução de exercícios durante o semestre (exercícios das aulas #2 a #12): 5% da nota final, i.e. máximo de 1 valor.

Classificação final (escala de 0 a 20): (CF = 0.7*E+P+R).

Ficam aprovados os estudantes que satisfaçam as seguintes condições:

• E ≥ 7 valores,
• CF ≥ 9.5 valores.

Na época de recurso não é possível repetir a componente prática de avaliação, ou seja as componentes P e R.

Melhoria de classificação

Na época de recurso da apenas pode ser melhorada a componente de exame (E).