Ficha da Disciplina

OBJECTIVOS E COMPETÊNCIAS

Reforçar as competências de programação dos estudantes, com ênfase no desenho e implementação das principais estruturas de dados e respetivos algoritmos. A metodologia de ensino-aprendizagem adotada é orientada a objetos com recurso à linguagem Java. Serão introduzidas noções fundamentais de eficiência e de análise de complexidade de algoritmos.
No final, os estudantes deverão ser capazes de:

aplicar os princípios fundamentais da programação orientada a objetos, incluindo herança, polimorfismo, interfaces, classes de coleção e iteradores;
escrever classes que implementem estruturas de dados lineares, tais como listas, pilhas, filas, conjuntos, dicionários, tabelas de dispersão e árvores binárias;
utilizar de forma adequada APIs que disponibilizem implementações de listas, pilhas, filas, conjuntos e tabelas de dispersão;
aplicar técnicas algorítmicas fundamentais, nomeadamente recursividade, pesquisa com retrocesso e dividir-para-conquistar;
realizar a análise de complexidade de algoritmos e identificar as principais classes de complexidade;
transferir e aplicar os conhecimentos adquiridos na resolução prática de problemas concretos.

PROGRAMA

A linguagem Java: classes, objetos, atributos e métodos; tipos primitivos, Strings, wrappers, arrays e tipos enumerados; expressões, operadores e instruções de controlo 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 da programação orientada a objetos: herança e padrões de reutilização, hierarquia de classes, polimorfismo, interfaces e Tipos Abstratos de Dados (TADs), uso de genéricos e iteradores.
Noções básicas de análise de algoritmos: análise assintótica; principais classes de complexidade e sua comparação; exemplos.
Técnicas de desenho de algoritmos: programação estruturada; recursividade; pesquisa exaustiva e backtracking; dividir para conquistar.
Estruturas de dados fundamentais: vetores e matrizes; listas ligadas simples, circulares e duplamente ligadas; árvores binárias, árvores de pesquisa e heaps.
Tipos Abstratos de Dados e respetivas implementações: sequências, pilhas, filas e deques; contentores associativos — conjuntos e dicionários; filas de prioridade.
Métodos de ordenação e pesquisa.

MÉTODOS DE ENSINO

Aulas Teóricas

Exposição estruturada dos conceitos fundamentais de programação orientada a objetos, estruturas de dados e análise de algoritmos, suportada por apresentações em slides, exemplos de programação em Java e discussão de casos práticos. Promove-se a participação ativa dos estudantes através da resolução interativa de exercícios e da análise comparativa de diferentes soluções.

Aulas Laboratoriais
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 (14 valores).
Avaliação teórico-prática sem recurso a consulta ou computador.
(P) Prática de resolução de problemas (2 avaliações práticas): 25% da nota final (5 valores).
Cada avaliação prática valerá 2.5 valores. Os problemas serão de dificuldade próxima 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 = E+P+R).

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

E ≥ 4.9 valores (35% de 14 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 105 minutos (1h45min).
- 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 tenham uma assiduidade às aulas práticas superior a 50% das aulas dadas.
Os estudantes que frequentaram a cadeira em anos anteriores, para obtenção de frequência têm apenas de responder a pelo menos 50% dos questionários (quizzes); Para estes, a frequências das aulas práticas é opcional.

AVALIAÇÃO EM SITUAÇÕES ESPECIAIS

Salvo em casos pontuais de força maior, não haverá concessão de dispensa de frequência da componente prática. A presença nas aulas é fortemente aconselhada, especialmente para quem frequenta pela primeira vez.
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%.