Baixe Introdução à Matemática Discreta e outras Notas de estudo em PDF para Informática, somente na Docsity! 22/02/2010 1 Prof. Wanderley de Souza Alencar Matemática Discreta Capítulo 0 Introdução à Matemática Discreta Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta • A Matemática não trata apenas da manipulação de símbolos, da realização de cálculos, etc. • A Matemática trata de idéias. • A força motriz da Matemática são os problemas – sejam eles práticos ou teóricos. Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Matemática Discreta Contínua Os objetos manipulados são discretos, ou seja, um determinado subconjunto finito de elementos. Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Discreto Formado por partes separadas; distinto Formado por partes distintas, não ligadas Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta 01 Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta • Exemplo 01 (Sun Tzu Suan-Ching – século IV d. C.) “Uma mulher estava a lavar pratos num rio quando um funcionário, cuja tarefa era observar as águas do rio, lhe perguntou: - Por que é que estão tantos pratos aqui? - Porque houve um banquete na residência, respondeu ela, tendo o funcionário inquirido qual o número de convidados. 22/02/2010 2 Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta - Não sei quantos convidados eram, retorquiu a mulher. - Mas cada dois utilizaram o mesmo prato para comer arroz, cada três o mesmo prato para sopa, cada quatro o mesmo prato para carne, e estão aqui, no total, sessenta e cinco pratos”. Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Quantos eram os convidados ? Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Solução: Modelando o problema pode-se dizer que: • Número de convidados: x Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Solução: Modelando o problema pode-se dizer que: • Número de pratos para arroz: x / 2 • Número de pratos para sopa: x / 3 • Número de pratos para carne: x / 4 Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Solução: Sabe-se que no total foram utilizados 65 pratos... x x x --- + --- + --- = 65 2 3 4 Número de pratos utilizados Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Solução: Resolvendo-se a equação de 1º grau obtém-se que: x = 60 Logo, eram 60 os convidados da festa! 22/02/2010 5 Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta • Exemplo 04: Comissão de Curso e Combinatória Enunciado: Os n alunos de Matemática Discreta pretendem eleger a Comissão de Curso, composta por m elementos. De quantas maneiras o podem fazer isto? Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Solução: A partir de conhecimentos de combinatória do Ensino Médio, pode-se dizer que trata-se de uma combinação sem repetição: n m n! m!.(n-m)!()= com n,m ∈Ν e n ≥ m Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta 05 Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Exemplo 05: Comissão de Curso e Combinatória Enunciado: Os n alunos de Matemática Discreta pretendem eleger a Comissão de Curso, composta por m elementos. De quantas maneiras o podem fazer isso se houver m cargos na comissão ? Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Solução: A partir de conhecimentos de combinatória do Ensino Médio, pode-se dizer que trata-se de um arranjo sem repetição: A(n,m) n! (n-m)! = com n,m ∈Ν e n ≥ m Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta 06 22/02/2010 6 Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta • Exemplo 06: Caminho mais curto em grafos Enunciado: Qual o caminho mais curso entre duas cidades escolhidas no grafo a seguir ? D C B E G F A 2 6 4 2 5 3 7 6 1 1 Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Solução: Aplicar o Algoritmo de Dijkstra para determinação do caminho mínimo em grafos. Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta 07 Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta • Exemplo 07: Álgebra Enunciado: O Ernesto tem o dobro da idade de Anabela. A soma das idades é igual a 66 Qual a idade de cada um? Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Solução: Vamos criar as seguintes variáveis: • Idade do Ernesto: x • Idade da Anabela: y Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Solução: Sabe-se que: x = 2 . y x + y = 66 Resolvendo o sistema: x = 44 e y = 22 { 22/02/2010 7 Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta Solução: Resolvendo o sistema linear de equações, tem-se que: x = 44 e y = 22. Logo Ernesto tem 44 anos e Anabela 22 anos. Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta • Outras áreas de aplicação de Matemática Discreta são: • Estruturas de dados • Algoritmos • Teoria de Bases de Dados • Teoria de Autômatos Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta • Outras áreas de aplicação de Matemática Discreta são: • Teoria da Compilação • Segurança em Computadores • Sistemas Operacionais Matemática Discreta Prof. Wanderley de Souza Alencar Introdução à Matemática Discreta A persistência da memória – 1931, de Salvador Dali (1904-1989)