Estruturas de Dados

Código:

CC114

Sigla:

CC114

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

Ocorrência: 2009/2010 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~fds/aulas/EDados/0910/
Unidade Responsável:	(X) 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	110	Plano de estudos de 2008 até 2013/14	1	-	7,5	-
MI:ERS	200	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 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 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.

* 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.

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

Bibliografia Obrigatória

Michael T. Goodrich, Roberto Tamassia; Data Structures and Algorithms in Java, 4th edition, Wiley, 2005

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

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 Microsystems.
* 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.

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Descrição	Tipo	Tempo (Horas)	Peso (%)	Data Conclusão
Participação presencial (estimativa)	Participação presencial	70,00
	Total:	-	0,00

Obtenção de frequência

1. Não haverá marcação de faltas nas aulas, contudo a assiduidade é fortemente aconselhada para se ter sucesso na disciplina.

2. Perdem frequência os alunos que não realizem a componente prática prevista, ou que não obtenham uma classificação superior ou igual a 50% da avaliação prática.

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

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

1. Prática de Resolução de Problemas (PRP): serão propostos 3 problemas para serem resolvidos no espaço de pelo menos uma semana e com submissão obrigatória através do sistema Mooshak. Os problemas podem ser resolvidos individualmente ou em grupos de 2 alunos. O período de resolução destes problemas incluirá pelo menos uma aula prática onde deverá ser solicitado apoio. Os problemas serão sempre precedidos de pelo menos uma aula de treino com problemas similares. Contribuição para a nota final: 3 valores.

IMPORTANTE: as soluções submetidas serão analizadas por programas de detecção de plágio. Todos os casos que, na percepção dos docentes, sejam consideradas cópias, os alunos/grupos envolvidos serão classificados com 0 valores.

2. Exame Prático (EP): na última semana de aulas, durante a aula prática, haverá um exame prático de 50 minutos para resolução de um problema de programação com um nível de dificuldade não superior aos exercícios resolvidos durante o semestre. Contribuição para a nota final: 2 valores.

Nota Mínima de Frequência: apenas os alunos que atinjam a classificação mínima de 50% no conjunto das avaliações práticas (PRP+EP) terão frequência à disciplina e poderão apresentar-se ao exame escrito.

3. Exame Escrito (EE): os alunos terão de responder a um exame teórico-prático com a duração de cerca de 2.5 horas. Contribuição para a nota final: 15 valores.

Nota Mínima: só poderão ser candidatos a aprovação na disciplina, os alunos que tenham obtido frequência prática para se apresentarem em exame e que obtenham uma classificaçõa mínima de 40% no exame escrito (EE).

4. A classificação final na disciplina é obtida somando as classificações parciais das provas de avaliação: PRP+EP+EE. Ficam aprovados os alunos que 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.