Matemática Discreta: Introdução e Detalhes do Curso

Prévia do material em texto

Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Apresentac¸a˜o da Disciplina
Prof. Dr. Leandro Balby Marinho
Matema´tica Discreta
Prof. Dr. Leandro Balby Marinho 1 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Roteiro
1. Introduc¸a˜o
2. Motivac¸a˜o
3. Ementa
4. Detalhes do Curso
Prof. Dr. Leandro Balby Marinho 2 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
O que e´ Matema´tica Discreta?
Definic¸a˜o
E´ a parte da matema´tica que estuda estruturas discretas,
enumera´veis ou finitas.
Prof. Dr. Leandro Balby Marinho 2 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Por que estudar Matema´tica Discreta?
I Desenvolver habilidade em entender e criar argumentos
matema´ticos.
I Aprimorar a habilidade de resolver problemas.
I Porta de entrada para cursos mais avanc¸ados em cieˆncia da
computac¸a˜o, como:
I Ana´lise e Te´cnica de Algoritmos
I Linguagens de Programac¸a˜o
I Teoria dos Grafos
I Redes de Computadores
I Bancos de Dados
I Inteligeˆncia Artificial
Prof. Dr. Leandro Balby Marinho 3 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Matema´tica Discreta e´ Dif´ıcil?
I Desafiador pois o aluno e´ instigado a raciocinar e resolver
problemas.
I Como obter o melhor aproveitamento da disciplina?
I Participando da aula.
I Resolvendo os exerc´ıcios em casa.
I Participando das sec¸o˜es semanais de exerc´ıcio.
I Interagindo com os monitores.
Prof. Dr. Leandro Balby Marinho 4 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Roteiro
1. Introduc¸a˜o
2. Motivac¸a˜o
3. Ementa
4. Detalhes do Curso
Prof. Dr. Leandro Balby Marinho 5 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Lo´gica
Mostre que o seguinte argumento e´ va´lido: “Todos os homens sa˜o
mortais. So´crates e´ homem. Portanto, So´crates e´ mortal.”
Soluc¸a˜o: Seja H(x) a sentenc¸a “x e´ homem”, M(x) “x e´ mortal” e
s um s´ımbolo constante para So´crates. Enta˜o o argumento fica
[(∀x) (H(x)→ M(x)) ∧ H(s)]→ M(s)
e uma sequeˆncia de demonstrac¸a˜o e´
Passo Justificativa
1. (∀x) (H(x)→ M(x)) Hipo´tese
2. H(s) Hipo´tese
3. H(s)→ M(s) Particularizac¸a˜o Universal em (1)
4. M(s) Modus ponens em (2) e (3)
Prof. Dr. Leandro Balby Marinho 5 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Lo´gica
Mostre que o seguinte argumento e´ va´lido: “Todos os homens sa˜o
mortais. So´crates e´ homem. Portanto, So´crates e´ mortal.”
Soluc¸a˜o: Seja H(x) a sentenc¸a “x e´ homem”, M(x) “x e´ mortal” e
s um s´ımbolo constante para So´crates. Enta˜o o argumento fica
[(∀x) (H(x)→ M(x)) ∧ H(s)]→ M(s)
e uma sequeˆncia de demonstrac¸a˜o e´
Passo Justificativa
1. (∀x) (H(x)→ M(x)) Hipo´tese
2. H(s) Hipo´tese
3. H(s)→ M(s) Particularizac¸a˜o Universal em (1)
4. M(s) Modus ponens em (2) e (3)
Prof. Dr. Leandro Balby Marinho 5 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Provas Matema´ticas
I Prove que
√
2 e´ um nu´mero irracional.
I Prove que os nu´meros primos sa˜o infinitos.
Prof. Dr. Leandro Balby Marinho 6 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Teoria dos Conjuntos
O conjunto dos inteiros possui mais elementos do que o conjunto
dos naturais? E em relac¸a˜o ao conjunto dos racionais?
Prof. Dr. Leandro Balby Marinho 7 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Func¸o˜es e Complexidade de Algoritmos
Determine o custo do algoritmo abaixo que retorna o maior elemento em
um vetor de inteiros, considerando apenas o nu´mero de comparac¸o˜es rea-
lizadas como unidade ba´sica de operac¸a˜o.
Maximo(A, n)
1 max = A[1]
2 for i = 2 to n
3 if A[i ] > max
4 max = A[i ]
5 return max
Sa˜o necessa´rias n − 1 comparac¸o˜es (condicional if).
Prof. Dr. Leandro Balby Marinho 8 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Func¸o˜es e Complexidade de Algoritmos
Determine o custo do algoritmo abaixo que retorna o maior elemento em
um vetor de inteiros, considerando apenas o nu´mero de comparac¸o˜es rea-
lizadas como unidade ba´sica de operac¸a˜o.
Maximo(A, n)
1 max = A[1]
2 for i = 2 to n
3 if A[i ] > max
4 max = A[i ]
5 return max
Sa˜o necessa´rias n − 1 comparac¸o˜es (condicional if).
Prof. Dr. Leandro Balby Marinho 8 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Relac¸o˜es
Como modelar matematicamente relac¸a˜o de amizade do facebook?
Prof. Dr. Leandro Balby Marinho 9 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Relac¸o˜es
I Seja U o conjunto de usua´rios do facebook. R ⊆ U × U, tal
que (ui , uj) ∈ R ↔ (ui , uj) forem amigos no facebook.
I Matriz MR = [mij ] onde
mij :=
{
1, se (ui , uj) ∈ R
0, se na˜o.
I Grafo G := (V ,E ) onde V = U e E = R.
I Predicado bina´rio amigo(x,y).
Prof. Dr. Leandro Balby Marinho 10 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Relac¸o˜es
I Seja U o conjunto de usua´rios do facebook. R ⊆ U × U, tal
que (ui , uj) ∈ R ↔ (ui , uj) forem amigos no facebook.
I Matriz MR = [mij ] onde
mij :=
{
1, se (ui , uj) ∈ R
0, se na˜o.
I Grafo G := (V ,E ) onde V = U e E = R.
I Predicado bina´rio amigo(x,y).
Prof. Dr. Leandro Balby Marinho 10 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Relac¸o˜es
I Seja U o conjunto de usua´rios do facebook. R ⊆ U × U, tal
que (ui , uj) ∈ R ↔ (ui , uj) forem amigos no facebook.
I Matriz MR = [mij ] onde
mij :=
{
1, se (ui , uj) ∈ R
0, se na˜o.
I Grafo G := (V ,E ) onde V = U e E = R.
I Predicado bina´rio amigo(x,y).
Prof. Dr. Leandro Balby Marinho 10 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Relac¸o˜es
I Seja U o conjunto de usua´rios do facebook. R ⊆ U × U, tal
que (ui , uj) ∈ R ↔ (ui , uj) forem amigos no facebook.
I Matriz MR = [mij ] onde
mij :=
{
1, se (ui , uj) ∈ R
0, se na˜o.
I Grafo G := (V ,E ) onde V = U e E = R.
I Predicado bina´rio amigo(x,y).
Prof. Dr. Leandro Balby Marinho 10 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Problemas de Contagem
Quantas senhas de computador podem ser formadas com seis
caracteres, sendo 3 letras seguidas de treˆs d´ıgitos?
Prof. Dr. Leandro Balby Marinho 11 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Roteiro
1. Introduc¸a˜o
2. Motivac¸a˜o
3. Ementa
4. Detalhes do Curso
Prof. Dr. Leandro Balby Marinho 12 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Ementa
1. Lo´gica
2. Te´cnicas de Demonstrac¸a˜o
3. Recorreˆncia e Induc¸a˜o
4. Teoria dos Conjuntos
5. Func¸o˜es
6. Princ´ıpios de Contagem
7. Relac¸o˜es
8. Estruturas Alge´bricas
Prof. Dr. Leandro Balby Marinho 12 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Roteiro
1. Introduc¸a˜o
2. Motivac¸a˜o
3. Ementa
4. Detalhes do Curso
Prof. Dr. Leandro Balby Marinho 13 / 13 UFCG CEEI
Introduc¸a˜o Motivac¸a˜o Ementa Detalhes do Curso
Detalhes do Curso
I URL do curso:
www.dsc.ufcg.edu.br/~lbmarinho/md_apres_2013.2.html
I Grupo: http://groups.google.com/group/md_leandro_2013_2
I Hora´rio: Segunda (10h) e Quinta (8h), Sala CAA303
I Toleraˆncia 10 min.
I Avaliac¸a˜o:
I Exerc´ıcios + participac¸a˜o (boˆnus na me´dia)
I Minitestes (30%)
I Provas (70%)
I Livros Texto:
I J. Gersting. Fundamentos Matema´ticos para a Cieˆncia da
Computac¸a˜o - quinta edic¸a˜o, LTC (2004).
I Kenneth H. Rosen. Discrete Mathematics and Its Applications
- sexta edic¸a˜o, McGRAW-Hill (2007).
Prof. Dr. Leandro Balby Marinho 13 / 13 UFCG CEEI
	1. Introdução
	2. Motivação
	3. Ementa
	4. Detalhes do Curso