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
Com esta disciplina pretende-se familiarizar os alunos com áreas da Matemática tais como a Lógica, Análise Combinatória 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. Complementarmente, pretende-se que os alunos adquiram uma visão global sobre os métodos numéricos para resolução de alguns dos mais relevantes problemas matemáticos, tais como os Sistemas de Equações Lineares, Solução de Equações e de Sistemas de Equações Não Lineares, Interpolação Polinomial e Integração Numérica..

Programa
1ª parte
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.
2ª parte
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
Por Frequência:
A avaliação por frequência consiste na realização de duas provas escritas (sem consulta), cada uma classificada de 0 a 10 valores, correspondentes a cada uma das duas partes anteriormente indicadas nos conteúdos programáticos. O aluno é dispensado de exame, ou seja, é aprovado por frequência, se obtiver um mínimo de 3 valores em cada uma das duas provas escritas e se obtiver uma classificação final igual ou superior a 10 valores, resultante da soma (arredondada às unidades) das classificações obtidas em cada uma das provas referidas.

Por Exame:
Se o aluno foi admitido a exame, ou foi dispensado, mas pretende melhorar a sua classificação, pode realizar o exame da época normal, que consistirá numa prova escrita (sem consulta), classificada de 0 a 20 valores, sobre toda a matéria lecionada. O enunciado desta prova será composto por duas partes, ambas classificadas de 0 a 10 valores, correspondentes a cada uma das partes anteriormente indicadas nos conteúdos programáticos. O aluno é aprovado se nesta prova obtiver um mínimo de 3 valores em cada uma das duas partes referidas e se obtiver uma classificação final igual ou superior a 10 valores, resultante da soma (arredondada às unidades) das classificações obtidas em cada uma das partes.
Se o aluno reprovar no exame da época normal, pode propor-se ao exame da época de recurso, que consistirá numa prova escrita com a

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

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.