Lógica e Computação

Engenharia Informática
6 ECTS; 1º Ano, 2º Semestre, 28,0 T + 14,0 PL + 28,0 TP + 5,0 OT

Docente(s)
- Luís Miguel Merca Fernandes
- Carlos Filipe Perquilhas Baptista

Pré-requisitos
Não Aplicável

Objetivos
Aplicar os conceitos fundamentais da Lógica e Teoria de Grafos, essenciais ao estudo de matérias específicas como a Verificação Formal, a Análise de Sistemas e os Problemas de Redes.

Programa
1. Noções Fundamentais de Teoria dos Conjuntos e Lógica
1.1. Conjuntos finitos e conjuntos infinitos;
1.2. Subconjunto de um conjunto e o conjunto vazio;
1.3. Conjunto das partes de um conjunto;
1.4. Produto cartesiano de conjuntos, intersecção e reunião de conjuntos;
1.5. Diagramas de Venn de subconjuntos;
1.6. Leis distributivas e leis de De Morgan;
1.7. Lógica proposicional.
2. Provas por indução e definições recursivas
2.1. Princípio da Indução Matemática (formas forte e fraca);
2.2. Definição recursiva de conjuntos;
2.3. Definição recursiva de funções.
3. Relações
3.1. Definição de relação;
3.2. Relações de equivalência, conjuntos de equivalência e classes de equivalência;
3.3. Relações de ordem parciais e totais;
3.4. Elementos maximais e minimais; elementos máximos e mínimos.
4. Grafos e Digrafos
4.1. Definições e propriedades fundamentais;
4.2. Matrizes de adjacência e de incidência;
4.3. Ligações em grafos e digrafos;
4.4. Passeios, caminhos e circuitos em grafos e digrafos;
4.5. Alcançabilidade em grafos: grafos conexos e desconexos;
4.6. Alcançabilidade em digrafos: digrafos fortemente conexos, digrafos fracamente conexos e digrafos desconexos;
4.7. Caminhos e circuitos eulerianos;
4.8. Caminhos e ciclos hamiltonianos;
4.9. Aplicação à coloração de vértices;
4.10. Árvores e suas aplicações: Árvores geradoras e árvores binárias;
4.11. Algoritmos de Kruskal e de Prim;
4.12. Problemas de Caminho mais curto: Algoritmos de Dijkstra e de Floyd-Warshall.
5. Métodos Numéricos para Sistemas de Equações Lineares
5.1. Métodos Indiretos ou Iterativos:
5.1.1. Método iterativo de Jacobi;
5.1.2. Método iterativo de Gauss-Seidel.
6. Métodos Numéricos para Equações e Sistemas de Equações Não Lineares
6.1. Localização das raízes;
6.2. Métodos iterativos:
6.2.1. Método da Bissecção;
6.2.2. Método do Ponto Fixo;
6.2.3. Método de Newton;
6.2.4. Método da Secante e Método da Corda Falsa;
6.3. Método de Newton para sistemas de equações não lineares.
7. Interpolação Polinomial
7.1. Polinómio interpolador de Lagrange;
7.2. Polinómio interpolador de Newton;
7.3. Polinómio interpolador de Hermite;
7.4. Interpolação segmentada e interpolação inversa.
8. Derivação e Integração Numérica
8.1. Derivação Numérica;
8.2. Fórmulas de Newton-Cotes;
8.3. Regras do Trapézio e de Simpson simples;
8.4. Fórmulas do Trapézio e de Simpson compostas;
8.5. Fórmulas de Gauss.

Metodologia de avaliação
Avaliação por frequência: realização de duas provas escritas. Avaliação por exame: realização de um teste escrito sobre toda a matéria lecionada.

Bibliografia
- Faires, J. e Burden, R. (1993). Numerical Analysis. (Vol. 1). New York: PWS Publishing Company
- Rosen, K. (1995). Discrete Mathematics and Its Applications. (Vol. 1). Brasil: Mc Graw-Hill

Método de interação
Aulas teóricas e teórico-práticas, em que se expõem e exemplificam as matérias respeitantes a cada um dos conteúdos programáticos, assim como aulas práticas laboratoriais, onde se estudam as implementações dos algoritmos leccionados.

Software utilizado nas aulas
Não aplicável.