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: 2023/2024 - 2S

Ativa?	Sim
Página Web:	https://moodle.ips.pt/2324/course/view.php?id=1976
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	178	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
	Patrícia Alexandra Pires Macedo		3,00
	Bruno Miguel Nunes da Silva		6,00
Ensino Prático e Laboratorial	Totais	8	16,00
	Miguel Mourão Fialho Bugalho		4,00
	Patrícia Alexandra Pires Macedo		6,00
	Rúben Pereira Lourenço		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. Conceitos de Tabelas de dispersão para uso na implementação de dicionários, e.g., 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/2324/course/view.php?id=1976>

- GitHub:

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

- <https://github.com/estsetubal-atad-2023-24-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
Elaboração de projeto	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 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 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 Testes

**PL**

1 Projeto

Nas épocas normal, recurso e especial 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

Tn | Teste (n = 1, 2, 3)

PN | Projeto Época Normal (avaliação contínua e época normal)

EN | Exame de época Normal

PR | Projeto de Época de Recurso

ER | Exame 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`.

---

A avaliação do Projeto de Época Normal é subdividida em:

- 2 *checkpoints* (20%) + submissão (70%) + quiz individual (10%)

A avaliação dos Projetos de Época de Recurso e Época Especial é subdividida em:

- submissão (90%) + quiz individual (10%)

Todos os Projetos carecem de apresentação e discussão oral posterior, resultando desta a nota final e individual por aluno. 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 = max (T1 * w1 + T2 * w2 + T3 * w3), com <w1,w2,w3> sendo a melhor permutação de (30/30/40%)`

`PL = 100% * PN`

Notas mínimas:

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

`TP >= 9,5` valores

`PL >= 9,5` valores

**ÉPOCA NORMAL**

`TP = 100% * EN`

`PL = 100% * PN`

Notas mínimas:

`TP >= 9,5` valores

`PL >= 9,5` valores

**ÉPOCA DE RECURSO/ESPECIAL**

`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