Informações para o Exame
Data, Horário e Local - Época Normal
Valorização:
Como já explicado e como podem ver na página de avaliação e no Sigarra, o exame vale 14 valores, ou seja, 70% da nota desta unidade curricular (os outros 30% dizem respeito à componente prática: 25% o teste prático e 5% as submissões).
Inscrição:
- [IMPORTANTE] Devem inscrever-se no exame para terem sala atribuída. Façam-no no Mooshak de EDados, na "prova" com o nome "Inscrição no exame da Época Normal", até ao final do dia 28 de Junho (Domingo).
(inscrições terminadas)
Exame Modelo:
Podem consultar um exame modelo para este ano:
Podem também consultar os exames de épocas normais dos dois últimos anos, sendo que o regente da unidade curricular era o mesmo:
Objectivos para o exame:
Java e Programação Orientada a Objectos
Fundamentos de Java
- Conhecer o modelo de programação do Java, como criar um programa com um método main para iniciar a execução, como compilar e como executar um programa
- Conhecer os principais tipos de dados primitivos e os respectivos Wrappers
- Conhecer os principais operadores (+, -, *, /, %, ++, --, !, &&, ||, ==, <, >, <<, >>)
- Conhecer as instruções condicionais e de ciclo
- Saber como representar strings em Java e seus principais métodos
- Saber como criar e usar arrays (com uma ou mais dimensões)
- Saber como usar a classe Scanner para ler a partir da entrada padrão e como escrever na saída padrão
- Saber escrever o conteúdo de variáveis
Fundamentos de Programação Orientada a Objectos
- Perceber o que é uma classe, uma referência e um objecto
- Saber como criar um objecto (operador new) e como criar e chamar construtores
- Saber como definir atributos e métodos numa classe
- Perceber o conceito de overload e override de métodos
- Saber como comparar objectos (método equals(x)) e como escrevê-los (método toString())
- Perceber o significado dos classificadores private e public
- Perceber o conceito de variáveis e métodos estáticos
- Perceber o conceito de tipos genéricos
Tipos Abstractos de Dados
- Perceber o que é um Tipo Abstracto de Dados (TAD)
- Perceber e saber usar o conceito de Interface, incluindo como definir uma implementação concreta que implementa esse interface
- Saber criar um TAD simples (ex: Point, Rectangle, Vector, Matrix, Fraction, IntSet, BigNumber)
- Perceber que podem existir varias implementações possíveis para o mesmo TAD, com consequentes vantagens e desvantagens e diferentes complexidades de tempo e memória
Complexidade Algorítmica
Notação
- Conhecer a notação assintótica (O, Ω e Θ) e o seu significado
- Saber comparar funções usando esta notação
- Saber o que significa análise do pior caso e caso médio
- Conhecer as classes habituais de complexidade (linear, logarítmica, linearítmica, etc)
Análise da Complexidade de um Programa
- Saber analisar o custo temporal de um programa simples com ciclos e sem recursão
- Saber analisar uma recursão simples (que use a ideia de dividir para conquistar), e saber escrever a recorrência e a árvore de recorrência
- Saber estimar a complexidade de um programa sabendo o tempo que demora para um conjunto de inputs
- Saber prever o tempo de execução de um algoritmo quando se sabe a sua complexidade
Listas, Pilhas e Filas
Fundamentos de Listas Ligadas
- Perceber o conceito de nó, lista ligada simples, lista circular e lista duplamente ligada
- Perceber os principais métodos (ex: tamanho, adicionar e remover elementos)
- Conseguir implementar métodos simples de listas
TADs sequenciais (ou lineares)
- Conhecer o conceito do TAD Pilha, a ordem em que acede aos elementos e os principais métodos (push e pop)
- Conhecer o conceito do TAD Fila, a ordem em que acede aos elementos e os principais métodos (enqueue e dequeue)
- Conhecer o conceito de TAD Deque, a ordem em que acede aos elementos e os principais métodos (adicionar e remover no princípio e fim)
Árvores Binárias e Heaps
Fundamentos de Árvores
- Conhecer o conceito de árvore
- Conhecer a terminologia básica (ex: nós, raíz, folhas, filhos, pais, altura, profundidade)
Árvores Binárias Simples
- Perceber o conceito de árvore binária
- Saber como implementar uma árvore binária simples com conteúdo genéricoxs
- Saber implementar métodos recursivos simples (ex: número de nós, altura, escrever todos os nós)
- Perceber os conceitos de pesquisa em profundidade (preorder, inorder e postorder) e de pesquisa em largura, sabendo como implementá-los
Árvores Binárias de Pesquisa
- Perceber o conceito de árvores binárias de pesquisa (BST - Binary Search Tree)
- Perceber os principais métodos (inserir, remover e verificar se existe um elemento)
- Perceber qual a pior altura possível e qual a altura média para uma ordem aleatória e as consequências disso na complexidade dos métodos associados
- Saber implementar métodos simples para BSTs
- Perceber o conceito do TADs Conjunto, quais as principais operações e como poderia ser implementado com BSTs, e quais a vantagens e desvantagens quando comparado com outras implementações
- Perceber o conceito do TAD Dicionário, quais as principais operações e como poderia ser implementado com BSTs, e quais a vantagens e desvantagens quando comparado com outras implementações
Filas de Prioridade e Heaps
- Conhecer o conceito do TAD Fila de Prioridade e as principais operações (inserir e remover elemento prioritário)
- Saber o que é e como funciona uma heap, como armazena os elementos num array, que invariante mantém, como pode ser usada para implementar uma fila de prioridade e que complexidades garante para as suas operações