Algoritmos e Estruturas de Dados

Caracterização geral

Pré-requisitos

Precedência obrigatória:

- Programação de Microprocessadores

Bibliografia

Mark Allen Weiss.
Data Structures and Algorithm Analysis in C (second edition).
Addison-Wesley, 1997.
ISBN 0-201-49840-5 (Hard cover)

Linguagem de Programação C

Brian Kernighan and Dennis Ritchie
The C Programming Language (second edition).
Prentice-Hall, 1988.
ISBN 0-13-110362-8 (Paperback)

Pedro Guerreiro.
Elementos de Programação com C (3ª edição).
FCA - Editora de Informática, 2005.

Luis Damas.
Linguagem C (12ª edição).
FCA - Editora de Informática, 2005.

Método de ensino

O ensino consiste na exposição da matéria em aulas teóricas e na resolução de problemas em aulas práticas de laboratório.

Nas aulas teóricas, todos os conteúdos programáticos são apresentados utilizando exemplos práticos concretos.

Para a maturação dos conteúdos, é realizado um conjunto de exercícios nas aulas práticas onde os alunos desenham, analisam e implementam programas para problemas concretos,  aplicando os conhecimentos adquiridos.

Os alunos vão sendo avaliados ao longo do semestre através do desenvolvimento de trabalhos práticos de pequena dimensão e de testes.

Método de avaliação

Elementos da avaliação

Os elementos de avaliação são os seguintes, com os pesos na nota final indicados:

• T1 - Teste 1 - 25%
• T2 - Teste 2 - 45%
• PR - Projeto - 30%
• ER - Exame de recurso - 70%

Cada um destes elementos de avaliação é cotado até 20 valores, com a nota arredondada às centésimas.

Os testes e exame são presenciais, individuais, escritos e sem consulta. Não é permitido o uso de instrumentos eletrónicos.

O projeto é efetuado por grupos de dois alunos pertencentes ao mesmo turno prático. Vão existir discussões no projeto.

O calendário do projeto encontra-se na página da disciplina e nos "eventos" do CLIP.

Nota da componente teórica-prática

A nota da componente teórica-prática (CompTP) tem um peso de 70% da nota final e pode ir até ao valor máximo de 20 valores.

A nota CompTP define-se de três formas diferentes, consoante as situações:

• CompTP= (0.25*T1+0.45*T2)/0.70    (no caso de avaliação contínua pura)
• CompTP= ER                                     (para alunos não aprovados na avaliação contínua)
• CompTP = max((0.25*T1+0.45*T2)/0.70, ER)   (avaliação contínua + tentativa de melhoria de nota)

Nota da componente laboratorial e frequência

A nota da componente laboratorial (CompLab) tem um peso de 30% da nota final e pode ir até ao valor máximo de 20 valores.

A nota CompLab é definida simplesmente como a nota do projeto:

• CompLab = PR

Para obter frequência, é necessário que CompLab >= 9.5.

Para além disso, no caso dos alunos de 1º inscrição, é requerida a participação em pelo menos 50% das aulas práticas.

Nota final e aprovação

A nota final dos alunos com frequência calcula-se assim (sendo arredondada às unidades):

• FINAL = 0.7 * CompTP + 0.3 * CompLab

A aprovação na disciplina é determinada pela seguinte condição:

• APROVAÇÃO = CompTP >= 9.5 e CompLab >= 9.5

Validade da frequência obtida neste ano

A frequência obtida no ano letivo corrente será valida no próximo ano letivo, pelo menos.

Frequências dos anos anteriores

A frequência obtida no ano letivo anterior é válida no ano letivo corrente (e permite-se também que essa nota seja melhorada, fazendo o projeto do ano corrente). As frequências mais antigas não são válidas.

Fraude

As questões de fraude/plágio são tratadas de acordo com o Regulamento de Avaliação de Conhecimentos da FCT NOVA. Por exemplo, qualquer tipo de fraude em qualquer elemento de avaliação impossibilita fazer a disciplina no ano letivo corrente, podendo haver ainda outras consequências.

No projeto final, alunos podem conversar com os colegas sobre aspetos gerais do trabalhos. Mas não podem partilhar código (mesmo que sejam "poucas linhas") em nenhuma circunstância, oralmente ou por escrito. A escrita de código tem de ser uma tarefa interna a cada grupo. Por exemplo, não é permitido mostrar código no ecrã, ditar código, enviar ficheiros com código nem colocá-los em sítios acessíveis a terceiros.

Nesta disciplina introdutória desaconselha-se o uso de ferramentas de IA no projeto. Mas se forem pontualmente usadas no projeto, os fragmentos de código correspondente têm de referir isso explicitamente. Omitir essa informação é considerado plágio e fraude.

Durante uma prova de avaliação, um estudante não pode ter junto a si dispositivos electrónicos com capacidade de acesso à internet ou ligação bluetooth (e.g. smartphones, smartwatches, smartglasses, tablets, laptops, etc), ainda que desligados. A violação desta regra implica a reprovação liminar na unidade curricular por exclusão e será comunicada à Comissão Científica do respectivo Curso.

Conteúdo

1. Estruturação dum programa em tipos abstractos de dados.
• Método para análise e conceção da solução
• Definição e implementação de tipos abstractos de dados no domínio do problema
2. Especificação formal e implementação de tipos de dados abstractos:
• Fila
• Pilha
• Sequência
• Conjunto
• Dicionário
3. Introdução à análise de algoritmos. Estudo das principais estruturas de dados, sempre acompanhado da análise da complexidade das primitivas suportadas, no melhor caso, no pior caso e no caso esperado.
4. Técnicas de implementação usando:
• Vetores.
• Listas simplesmente e duplamente ligadas.
• Tabelas de dispersão. Funções de dispersão. Dispersão aberta. Dispersão fechada.
• Ordenação.

Cursos

Cursos onde a unidade curricular é leccionada: