Publicação em Diário da República: Despacho n.º 9184/2020 - 25/09/2020
6 ECTS; 2º Ano, 1º Semestre, 28,0 PL + 28,0 TP + 5,0 OT , Cód. 814333.
Docente(s)
- João Manuel Mourão Patrício (1)(2)
(1) Docente Responsável
(2) Docente que lecciona
Pré-requisitos
Não aplicável.
Objetivos
1. Familiarizar os alunos com técnicas de análise e síntese de algoritmos e estruturas de dados.
1. Conhecer os fundamentos da análise e síntese de algoritmos.
2. Analisar a realização prática de algoritmos e estruturas de dados.
3. Ter uma perspectiva abrangente das aplicações dos algoritmos em Ciências Informáticas.
Programa
1. Introdução ao conceito de algoritmo
2. Grafos, Digrafos e Redes
2.1. Definições e propriedades fundamentais
2.2. Matrizes de adjacência e matrizes de incidência
2.3. Ligações em grafos
2.4. O problema da alcançabilidade em digrafos
2.5. Conectividade de um grafo
2.6. Caminhos eulerianos e circuitos eulerianos
2.7. Caminhos hamiltonianos e ciclos hamiltonianos
2.8. Coloração de vértices
3. Árvores e Caminhos
3.1. Definição de árvore e propriedades fundamentais
3.2. Árvores geradoras
3.3. Árvores binárias e aplicação a códigos
3.4. Árvores geradoras de custo mínimo
3.5. Algoritmos de Kruskal e de Prim
3.6. Determinação do caminho de custo mínimo numa rede
3.7. Problema de fluxo máximo
3.8. Algoritmos de Dijkstra e de Floyd-Warshall
4. Algoritmos de ordenação e de pesquisa
4.1. Apresentação do problema
4.2. Algoritmos de ordenação: inserção linear, inserção binária, seleção linear, bubblesort e quicksort
4.3. Algoritmos de pesquisa linear e pesquisa binária
5. Modelos de Otimização
5.1. Breve introdução aos problemas e conceitos de Investigação Operacional
5.2. Problemas com estrutura linear: formulação, classificação e interpretação geométrica
5.3. Método simplex para problemas lineares genéricos
5.4. Problemas de transporte
5.5. Problemas de afetação
6. Introdução à complexidade: Classes P e NP; Problemas NP-completos; Teorema de Cook; Estudo de alguns problemas NP-completos; Algoritmos de aproximação para problemas NP-díficeis
Metodologia de avaliação
Avaliação por frequência - Dois testes escritos, tendo cada um peso de 30% e um trabalho prático, com um peso de 40%. A classificação final da UC resulta da média ponderada das classificações obtidas nas componentes de avaliação definidas.
O aluno obtém aprovação à UC, estando dispensado de Exame, de acordo com o disposto nos Pontos 11 e 12, do Artigo 11º, do regulamento Académico do IPT.
Avaliação final - Exame escrito, com um peso de 60%, e um trabalho prático, com um peso de 40%. A classificação final da UC resulta da média ponderada das classificações obtidas nas componentes de avaliação definidas.
O aluno obtém aprovação à UC, de acordo com o disposto nos Pontos 11 e 12, do Artigo 11º, do regulamento Académico do IPT.
Os alunos deverão ter, em cada um dos elementos de avaliação, uma nota mínima de 7.
Bibliografia
- Ahuja, R. e Magnanti, T. e Orlin, J. (1993). Network Flows: Theory, Algorithms, and Applications. NJ USA: Prentice-Hall
- Balakrishnan, V. (1996). Introductory Discrete Mathematics. New York: Dover
- Júdice, J. e Martins, P. e Pascoal, M. e Santos, J. (2006). Optimização em Redes. Acedido em 29 de setembro de 2023 em https://www.co.it.pt/~judice/Articles/SebOR2006.pdf
- Ramalhete, M. e Guerreiro, J. e Magalhães, A. (1994). Programação Linear. Portugal: Porto Editora
- Stein, C. e H. Cormen, T. e E. Leiserson, C. e L. Rivest, R. (2022). Introduction to Algorithms. (Vol. 1). (pp. 1-1292). USA: The MIT Press; 4th edition
Método de Ensino
As aulas destinam-se à apresentação dos temas e de exemplos práticos. Os tópicos principais são igualmente explorados através da realização de exercícios e de trabalhos práticos baseados em computador.
Software utilizado nas aulas
Ferramentas de programação; ferramentas de produtividade; plataformas colaborativas de eLearning.
Aprovado em Conselho Técnico Cientifico: 05 de dezembro de 2024
Download da Ficha da Unidade Curricular (FUC)
