Estruturas de Dados

Código:

CC114

Sigla:

CC114

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

Ocorrência: 2012/2013 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~fds/aulas/EDados/1213/
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:AST	1	Plano de Estudos a partir de 2008	1	-	7,5	-
L:CC	80	Plano de estudos de 2008 até 2013/14	1	-	7,5	-
MI:ERS	164	Plano de Estudos a partir de 2007	1	-	7,5	-

Língua de trabalho

Português

Objetivos

Reforçar as competências de programação dos alunos numa perspectiva orientada aos objectos. Será dada ênfase aos conceitos de desenho orientado aos objectos, e desenho e implementação de estruturas de dados e algoritmos básicos. Serão introduzidas noções sobre eficiência e análise de complexidade de algoritmos.

Ao concluirem esta disciplina os alunos 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 básicas, como sejam listas, pilhas, filas, conjuntos, dicionários, tabelas de hash, árvores e grafos.

* 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 recursão, retrocesso (backtracking) e dividir-para-conquistar (divide-and-conquer).

* usar um ambiente de desenvolvimento de software (IDE) e um depurador de erros (debugger).

Programa

* Princípios de programação orientada aos objectos: herança, hierarquia de classes, polimorfismo, classes interface abstractas; classes colector e iteradores.

* Programação com eventos: métodos para lidar com eventos; propagação de eventos; lidar com excepções.

* Definição de um TAD (Tipo Abstracto de Dados). Estruturas abstractas de dados: definição e implementação; vectores e matrizes, listas, conjuntos, pilhas, filas, listas duplamente ligadas e listas circulares, tabelas de hash, árvores binárias e árvores binárias de pesquisa, árvores mais gerais, filas de prioridade e heaps.

* Estratégias para resolução de problemas: recursão, backtracking e divide-and-conquer;

* Noções básicas de análise de algoritmos: identificação de comportamento no melhor, pior e caso médio; Ordem de grandeza; medidas empíricas de performance, compromisso entre espaço e tempo.

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

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

* Breve introdução ao grafos. Implementação. Algoritmos de caminho mínimo em grafos.

Bibliografia Obrigatória

Stuart Reges and Marty Stepp ; Building Java Programs: A Back to Basics Approach , Addison Wesley, 2nd edition, 2010. ISBN: 0321382838

Bibliografia Complementar

Cay Horstmann; Java Concepts, 5th edition, Wiley, 2007
Cormen, Leiserson, Rivest and Stein; ntroduction to Algorithms, 3rd edition, The MIT Press, 2009
Bruce Eckel; Thinking in Java, (4th Edition), Prentice-Hall, 2006
Michael T. Goodrich, Roberto Tamassia; Data Structures and Algorithms in Java, 4th edition, Wiley, 2005

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 básicos.

Aulas Teórico-Práticas

As aulas teórico-práticas serão usadas para resolução de problemas que exemplifiquem o uso das estruturas de dados e algoritmos dados nas aulas teóricas. Será usada a linguagem de programação Java na implementação dos exemplos.

Aulas Práticas

As aulas práticas serão usadas para apoio aos alunos 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 da Sun/Oracle.
* O uso de um IDE para desenvolvimento: Eclipse ou NetBeans.
* A resolução de exercícios propostos para treino de programação.
* A resolução de exercícios propostos para efeitos de avaliação.

Palavras Chave

Ciências Físicas > Matemática > Algoritmos
Ciências Físicas > Ciência de computadores > Programação
Ciências Físicas > Ciência de computadores

Tipo de avaliação

Avaliação distribuída sem exame final

Obtenção de frequência

Perdem frequência os alunos que não tenham uma assiduidade às aulas superior a 60% das aulas dadas.

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

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

1. Teste escrito intermédio (TEI) - peso 6
2. Teste escrito final (TEF) - peso 8
3. Prova prática de resolução de problemas (3 problemas; PPP) - peso 6

A classificação final na disciplina obtém-se fazendo a soma pesada das classificações parciais das provas de avaliação.

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

1. tenham uma classificação média nos testes escritos superior ou igual a 35%.
2. tenham uma classificação final superior ou igual a 9.5 valores.

Avaliação especial (TE, DA, ...)

1. Não haverá concessão de dispensa de frequência da componente prática. A presença nas aulas é fortemente aconselhada.

2. Os alunos trabalhador-estudante não estão dispensados do cumprimento das regras para obtenção de frequência.

Melhoria de classificação

Os alunos que tendo tido aproveitamento na disciplina em anos lectivos anteriores e pretendam efectuar exame para melhoria de nota no presente ano lectivo, terão os seus exames avaliados para 20 valores.