This page in english Ajuda Autenticar-se

Você está em: Início > INF32153

Mapa das Instalações

Opções

Algoritmos e Tipos Abstratos de Dados

Código:

INF32153

Sigla:

ATBD

Áreas Científicas
Classificação	Área Científica
OFICIAL	Informática

Ocorrência: 2022/2023 - 2S

Ativa?	Sim
Página Web:	https://moodle.ips.pt/2223/course/view.php?id=1858
Unidade Responsável:	Departamento de Sistemas e Informática
Curso/CE Responsável:	Licenciatura em Engenharia Informática

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
FC	2	Plano Estudos_FC_Brighstart	1	-	6	75	162
INF	189	Plano de Estudos	1	-	6	75	162

Docência - Responsabilidades

Docente	Responsabilidade
Bruno Miguel Nunes da Silva	Responsável

Docência - Horas

Ensino Teórico-Prático:	3,00
Ensino Prático e Laboratorial:	2,00

Tipo	Docente	Turmas	Horas
Ensino Teórico-Prático	Totais	3	9,00
	Bruno Miguel Nunes da Silva		3,00
	Patrícia Alexandra Pires Macedo		6,00
Ensino Prático e Laboratorial	Totais	8	16,00
	Aníbal Paulo Lopes da Ponte		6,00
	Bruno Miguel Nunes da Silva		4,00
	Miguel Mourão Fialho Bugalho		6,00

Língua de trabalho

Português
Obs.: Alguns conteúdos poderão ser fornecidos em inglês, devido à universalidade desta língua na área de IT.

Objetivos

- Saber formalizar algoritmos e analisar/discutir a sua complexidade algorítmica temporal;

- Saber o conceito de Tipo Abstrato de Dados (ADT) e distinguir "especificação" de "implementação";

- Saber aplicar ADTs na resolução de problemas;

- Saber especificar novos ADTs;

- Dada a sua especificação, saber derivar uma implementação concreta para um ADT e saber discutir/comparar diferentes implementações, variando a estrutura de dados;

- Aplicar algoritmia e ADTs na resolução de problemas reais, identificando os algoritmos e ADTs mais apropriados.

Resultados de aprendizagem e competências

Que o aluno adquira e consolide conhecimentos, aptidões e competências na:

- Interpretação, análise, especificação e implementação de algoritmos triviais de computação, e.g., algoritmos de seleção, pesquisa, ordenação; algoritmos iterativos e recursivos; na componente de análise será dado destaque à complexidade temporal dos algoritmos;

- Especificação e manipulação de estruturas de dados lineares (estáticas e dinâmicas) e tabelas de dispersão;

- Compreensão, uso e implementação dos tipos abstratos de dados (do género coleção) mais comuns, e.g., Stack, Queue, List, Map;

- Especificação de novos ADTs, escolha de uma estrutura de dados apropriada e sua implementação e uso;

- Aplicação prática dos conteúdos programáticos em problemas reais utilizando o paradigma de programação procedimental e imperativa, incluindo domínio de ponteiros e gestão dinâmica de memória.

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

Conhecimentos sólidos das características e semântica de uma linguagem de programação, nomeadamente:

- Tipos de dados e variáveis;

- Estruturas de selecção e repetição;

- Uso de funções - tipos de retorno e argumentos formais e atuais.

- Uso de programação procedimental.

Programa

1. Introdução à linguagem C - procedimental e modular; diferenças em relação à linguagem Java.

2. Algoritmos, complexidade algorítmica e formalização de algoritmos em pseudo-código;

3. Algoritmos de pesquisa e seleção;

4. Algoritmos de ordenação simples O(n²) - Bubble Sort e Selection Sort;

5. Algoritmos recursivos versus iterativos; recursividade;

- Exemplificação de algoritmos recursivos conhecidos: Algoritmo de ordenação Quick Sort e pesquisa binária.

6. Tipos de dados estruturados, ponteiros e gestão dinâmica de memória; passagem de argumentos por cópia vs. passagem por referência.

7. Tipos Abstratos de Dados na Linguagem C; especificação vs. implementação;

8. Especificação e uso dos tipos abstratos de dados (do género coleção) mais comuns: Stack, Queue, List e Map.

9. Definição e manipulação de estruturas de dados lineares estáticas, semi-estáticas e dinâmicas, i.e., arrays e listas ligadas;

10. Implementação dos tipos abstratos de dados Stack, Queue, List e Map utilizando estruturas de dados lineares;

11. Tabelas de dispersão e uso desta estrutura de dados numa implementação do ADT Map.

Bibliografia Obrigatória

Bruno Silva; Linguagem C (e-book ), (unpublished)
Bruno Silva; Tipos Abstratos de Dados na Linguagem C (e-book), (unpublished)
António Manuel Adrego da Rocha; Análise da Complexidade de Algoritmos, FCA, 2014. ISBN: 9789727227907

Bibliografia Complementar

António Manuel Adrego da Rocha; Estruturas de Dados e Algoritmos em C, FCA, 2014. ISBN: 9789727227693
Vinu Das; Principles of Data Structures using C and C++, New Age, 2006. ISBN: 978-81-224-2864-3

Métodos de ensino e atividades de aprendizagem

**AULAS TP**

- Transferência de conhecimento através de recursos expositivos.

- Exercícios de consolidação dos conceitos.

- Quizzes de feedback disponibilizados assíncronamente.

**AULAS PL**

- Aplicação em problemas reais do conhecimento adquirido, através de trabalhos práticos de codificação.

**OUTROS**

- A UC disponibiliza slides, livros próprios, fichas de exercícios, tutoriais e repositórios de código no apoio à aprendizagem, acessíveis através das plataformas Moodle e GitHub.

- Moodle:

- <https://moodle.ips.pt/2223/course/view.php?id=1858>

- GitHub:

- <https://github.com/estsetubal-atad>

- <https://github.com/estsetubal-atad-2022-23-labs>

Software

GCC (Gnu Compiler Collection)
Visual Studio Code
GDB (GNU Debugger)
Doxygen
Valgrind

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Designação	Peso (%)
Teste	50,00
Trabalho laboratorial	50,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Estudo autónomo	45,00
Frequência das aulas	75,00
Trabalho laboratorial	30,00
Total:	150,00

Obtenção de frequência

A avaliação da UC é dividida em duas componentes, avaliadas de forma independente (i.e., a aprovação nas componentes pode ser feita em épocas diferentes):

Avaliação TP - 50%

Avaliação PL - 50%

A nota resultante de cada componente tem de ser >= 9,5 valores. Consequentemente, a nota global ponderada tem de ser também >= 9,5 valores.

Caso reprove apenas a uma componente, só tem de repetir essa componente na próxima época de avaliação.

Existem 3 épocas de avaliação consecutivas:

- Época de Avaliação Contínua;

- Época Normal, e;

- Época de Recurso.

**CONSIDERAÇÕES PRÉVIAS**

O acesso a cada mini-teste está condicionado à resposta a 3 quizzes (um por semana e de escolha múltipla), disponibilizados no Moodle. Cada quiz contém 5 questões, pode ser respondido um número ilimitado de vezes e carece de acerto em 3 questões para ser considerado "respondido".

Na componente PL existe um critério de ponderação de assiduidade a 10 aulas de laboratório com enunciado (tutorial ou avaliado) que será utilizado sobre a nota dos laboratórios avaliados (AL = presenças/10). Este critério não se aplica aos alunos com estatuto de trabalhador-estudante, onde AL = 1.

O acesso ao Teste e aos Exames carece de inscrição prévia na plataforma Moodle. Aos alunos que não se encontrarem inscritos dentro dos prazos previamente estabelecidos poderá ser vedado o acesso à respetiva prova.

Os laboratórios avaliados são classificados em níveis [0, 5] e posteriormente efetuada a sua média aritmética, extrapolada para [0, 20] valores.

Os projetos são submetidos obrigatoriamente na plataforma Moodle nos prazos estabelecidos; só assim são considerados "entregues".

Na época de avaliação contínua existem os seguintes elementos de avaliação:

**TP**

3 Mini-Testes

1 Teste

**PL**

4 Laboratórios avaliados

1 Projeto

Nas épocas normal e de recurso existem os seguintes elementos de avaliação:

**TP**

1 Exame

**PL**

1 Projeto

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

As componentes e elementos de avaliação são representados pelas seguintes siglas:

TP | Componente Teórico-prática

PL | Componente Prática-laboratorial

MT | Mini-Teste

T | Teste

L | Laboratório avaliado

AL | Critério de assiduidade aos laboratórios

P | Projeto (avaliação contínua e época normal)

EN | Exame de época normal

ER | Exame de época de recurso

PR | Projeto de época de recurso

**CONSIDERAÇÕES PRÉVIAS**

A classificação final, em qualquer época de avaliação, é calculada por:

`FINAL = 50% * TP + 50% * PL`

As notas calculadas para as ambas componentes TP e PL têm de ser `>= 9,5` valores.

Todas as notas dos elementos individuais de avaliação serão arrendondadas à décima, sendo que a nota final será arredondada à unidade.

Considera-se "Aprovado" o aluno que possua `FINAL >= 10`.

---

Todos os Projetos carecem de apresentação e discussão oral posterior, podendo resultar na alteração da nota inicial. Também será avaliada a participação individual através de commits efetuados, através do GitHub Classroom.

---

Os laboratórios avaliados são de cariz "opcional", mas a partir do momento que o aluno se submete a avaliação, considera-se automaticamente que optou pela avaliação contínua na componente PL, decorrendo daí o cálculo da nota respetiva para essa componente.

**ÉPOCA DE AVALIAÇÃO CONTÍNUA**

`TP = ([20 + 15 + 15]% * MT) + (50% * T)`

`PL = (20% * L * AL) + (80% * P)`

No caso de não se submeter aos laboratórios avaliados (L), então: `PL = 100% * P`.

Caso o aluno não tenha frequentado todos os 4 laboratórios avaliados, os restantes serão cotados com 0 (zero) para efeitos de cálculo de L.

Notas mínimas:

`MT >= 0` (não tem)

`T >= 7,5` valores

`P >= 9` valores

`L >= 0` (não tem)

**ÉPOCA NORMAL**

`TP = 100% * EN`

`PL = 100% * P`

Notas mínimas:

`EN >= 9,5` valores

`PL >= 9,5` valores

**ÉPOCA DE RECURSO**

`TP = 100% * ER`

`PL = 100% * PR`

Notas mínimas:

`ER >= 9,5` valores

`PR >= 9,5` valores

Melhoria de classificação

Só é possível melhoria de nota na época de recurso e mediante inscrição válida na Divisão Académica.

- A componente TP só pode ser melhorada através de exame.

- A componente PL só pode ser melhorada através de projeto, elaborado individualmente.

Observações

**PLÁGIO**

Todos os projetos são submetidos à verificação de plágio (cópias) através do cruzamento de todos os projetos submetidos.

Qualquer situação de plágio detetada levará à **anulação dos projetos envolvidos** (não interessa fonte/destino) e comunicação à Direção para seguimento sancionatório.

**DISCUSSÕES ORAIS**

Em qualquer avaliação poderá ser solicitada uma *discussão oral* para validação de competências.

**MOODLE**

O acesso à plataforma Moodle é permitido apenas aos alunos inscritos, mediante password fornecida pelos docentes da UC.

**CASOS OMISSOS**

Casos omissos serão decididos pelo Responsável da Unidade Curricular.

Recomendar Página Voltar ao Topo