Estruturas Discretas

Sumários (aula teórica)



1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 -

Aula 1
22/09/10

Apresentação da disciplina: programa, avaliação, plano das aulas, atendimento aos alunos, página da disciplina.
0. Introdução: o que é a Matemática Discreta? Problemas motivadores: existência, contagem e optimização.
1. Fundamentos
1.1. Introdução à Lógica. Cálculo Proposicional. 

Sintaxe e semântica da lógica proposicional. 

Aula 2
29/09/10

Fórmulas logicamente equivalentes. Algumas equivalências básicas. 
Prova da equivalência de duas fórmulas: tabelas de verdade, deduções formais usando as leis básicas, método de Quine. 
Formas normais conjuntivas e disjuntivas. Algoritmo.
Funções de verdade.

Aula 3
6/10/10

Predicados. Quantificadores.
Breve referência ao Cálculo de Predicados.
Lógicas de Primeira Ordem. O Tarski World.

1.2. Raciocínio matemático, indução e recursão
Quando é que um argumento matemático está correcto?
O que é uma prova. Falácias.
Digressão por algumas técnicas de prova: verificação exaustiva. 
Exemplos: conjectura de Goldbach, conjectura de Polya.


Aula 4
13/10/10

Mais técnicas de prova: condicionais, equivalências, redução ao absurdo, indução matemática.
Provas por indução matemática:
O método de indução matemática. Exemplos de aplicação. 
Visualização de alguns aplicativos ilustrativos.

1.3. Algoritmos e complexidade.
Definições recursivas e algoritmos recursivos.

Aula 5
20/10/10

Exemplos: factorial; função de Collatz. Análise da conjectura de Collatz com a ajuda do Mathematica.
Medida da complexidade de um algoritmo. Complexidade polinomial e complexidade exponencial. 
Exemplos.
Análise da eficiência de um algoritmo na pior situação.
Algoritmos optimais na pior situação. Árvores de decisão.
Somatórios. Propriedades dos somatórios.

Aula 6
37/10/10

Técnicas para resolver somatórios.
Funções floor e ceiling.
Progressões aritméticas e progressões geométricas.
Mais técnicas de somatórios: 
O método da perturbação. O método ad hoc: Visualização de alguns aplicativos ilustrativos.

Aula 7
3/11/10

2. Grafos.

Problema das pontes de Konigsberg. Grafos simples, pseudografos e grafos dirigidos. Grafos completos. 
Grau de um vértice. Propriedades.
Matrizes de adjacência e de incidência. Caminhos e ciclos. Grafos conexos.
Caminhos eulerianos. Grafos eulerianos. 
Caracterização dos grafos eulerianos: Teorema de Euler. Exemplos. Solução do problema das 7 pontes. 
Algoritmo para a enumeração de um caminho euleriano.

Aula 8
10/11/10

Ilustração de alguns dos conceitos estudados na aula anterior com a ajuda do programa Mathematica.
Grafos planares. Grafos regulares.
Caminhos semi-eulerianos. Grafos semi-eulerianos. 
Caminhos hamiltonianos. Grafos hamiltonianos.
O problema do trajecto mais curto. Algoritmo de Dijkstra.
O problema do caixeiro-viajante.


Aula 9
17/11/10

Árvores. Propriedades. 
Raiz; vértice interno, folha.
Árvores m-árias; árvores m-árias plenas. Propriedades.

3. Os inteiros. Criptografia.

O algoritmo da divisão inteira. Aritmética modular.
Adição e multiplicação módulo n. 
Aplicações: a cifra de César.

Aula 10
24/11/10

Continuação da aula anterior. Cifras aditivas e multiplicativas.
Elementos invertíveis.
Máximo divisor comum. Algoritmo de Euclides.
Resolução de congruências.
Aplicações: a cifra de César; a criptografia moderna: o método RSA de chave pública. 
Exemplo de simulação do método RSA. 


Aula 11
15/12/10
4. Contagem
4.1. Técnicas básicas
Estratégias básicas para resolver problemas de contagem.
Princípio da Multiplicação e Princípio da Adição. Exercícios.
Permutações e combinações de n elementos r a r.
Números binomiais. Propriedades.
Fórmula de Pascal. Triângulo de Pascal.
Binómio de Newton: demonstração por indução.

4.2. Técnicas avançadas
Permutações e combinações de n elementos r a r, com repetição de elementos.
Exemplo: o paradoxo dos aniversários.