Ficha da Disciplina

OBJECTIVOS E COMPETÊNCIAS

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

PROGRAMA

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.
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.
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.
Técnicas de desenho de algoritmos: programação estruturada; recursividade; pesquisa exaustiva e backtracking; dividir para conquistar.
Estruturas de dados fundamentais: vectores e matrizes; listas ligadas simples, circulares e duplamente ligadas; árvores binárias, árvores de pesquisa e heaps.
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.
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.

MÉTODOS DE ENSINO

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.

BIBLIOGRAFIA:

Principal

Outros livros recomendados

MÉTODO DE AVALIAÇÃO:

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.

ORGANIZAÇÂO DO PROCESSO DE AVALIAÇÂO:

As avaliações práticas terão lugar fora das aulas práticas, com turnos de 90 minutos.
- Os problemas a resolver serão semelhantes aos problemas das aulas práticas;
- Os estudantes terão de comparecer no turno que lhes for indicado e a troca de turno apenas será possível se solicitada com pelo menos 48 horas de antecedência.
A não comparência numa avaliação corresponde a não a ter realizado e será classificado com 0 valores.
As soluções submetidas ao Mooshak serão avaliadas parcelarmente, sendo o resultado final a soma das pontuações parcelares nos vários casos de teste.

OBTENÇÃO DE FREQUÊNCIA

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

AVALIAÇÃO EM SITUAÇÕES ESPECIAIS

Salvo em casos pontuais de força maior (ou estudantes com estatuto especial), não haverá concessão de dispensa de frequência da componente prática. A presença nas aulas é fortemente aconselhada.
Os estudantes que tendo tido aproveitamento na disciplina em anos lectivos anteriores e pretendam efectuar exame para melhoria de nota no presente ano lectivo, podem fazer apenas a componente de exame que, nestes casos, será cotado para 100%.