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: 2021/2022 - 2S

Ativa?	Sim
Página Web:	https://moodle.ips.pt/2122/course/view.php?id=93
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	3	Plano Estudos_FC_Brighstart	1	-	6	75	162
INF	211	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	4	12,00
	Patrícia Alexandra Pires Macedo		6,00
	Bruno Miguel Nunes da Silva		6,00
Ensino Prático e Laboratorial	Totais	10	20,00
	Bruno Miguel Campos Pereira		2,00
	Miguel Angel Guevara López		6,00
	Patrícia Alexandra Pires Macedo		2,00
	Miguel Mourão Fialho Bugalho		6,00
	Aníbal Paulo Lopes da Ponte		4,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

São traçados os seguintes 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
Fernando Mira da Silva; Apontadores e Estruturas de Dados Dinâmicas em C (e-book (unpublished))

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.

Software

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

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)
Elaboração de projeto	30,00
Estudo autónomo	45,00
Frequência das aulas	75,00
Total:	150,00

Obtenção de frequência

A avaliação da UC é dividida em duas componentes independentes:

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 (durante as semanas de aulas);

- É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 assiduidade de 8 aulas de laboratório com enunciado (tutorial ou avaliado) para serem contabilizadas as notas dos laboratórios avaliados. Este critério não se aplica aos alunos com estatuto de trabalhador-estudante.

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:

3 Mini-Testes

1 Teste

5 Laboratórios avaliados

1 Projeto

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

1 Exame

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 (20 ~ 30 min - escolha múltipla / online)

T | Teste

L | Laboratório avaliado

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:

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.

Época de avaliação contínua:

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

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

No caso de o critério de assiduidade PL não ser satisfeito, então: PL = 100% * P

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

Época de avaliação normal:

TP = 100% * EN

PL = 100% * P

Época de avaliação de recurso:

TP = 100% * ER

PL = 100% * PR

Notas mínimas:

T - 7 valores

EN / ER - 9,5 valores

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

Covid

São aplicados os direitos e deveres conferidos por despachos da Presidência do IPS.

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