Cícero C. Quarto – Engcomp/UEMA1

Engenharia da Computação

1

Um pouco sobre Matemática Discreta

Prof. Cícero QuartoDepartamento de Engenharia da Computação (DECOMP/UEMA)

Cícero C. Quarto – Engcomp/UEMA2

Objetivos

Definir o que é Matemática

Discreta

Esclarecer por que estudar Matemática

Discreta

Especificar os objetivos de um

curso de Matemática Discreta

Especificar tipos de problemas que

podem ser resolvidos com a Matemática

Discreta

1 2

3

4

Cícero C. Quarto – Engcomp/UEMA3

O que é Matemática Discreta

Matemática Discreta é a parte da matemática voltada para o estudo dos objetos discretos (aqui, discreto significa elemento distinto ou desconexo) (Rosen, 2009).

Elementos constituídos por unidades distintas, que podem ser distinguidos bem. Por exemplo: sexo, peso, altura, cores, probabilidades, contagem, relações, associações, correlações, formas, idade, etc...

Kenneth Rosen

Cícero C. Quarto – Engcomp/UEMA4

O que é Matemática Discreta

Matemática Discreta, também chamada de matemática finita, é o estudo das estruturas algébricas que são fundamentalmente discretas, em vez de contínuas. O nome se refere ao fato de tratar-se de funções cujas imagens possuem valores que não variam gradualmente como em funções contínuas, mas assumem valores distintos abruptamente com a mudança do elemento do domínio considerado (Wikipédia, 2020)

Cícero C. Quarto – Engcomp/UEMA5

O que é Matemática Discreta

Um conceito extremamente importante em Matemática Discreta é o de função. Uma função determina, para cada elemento de um conjunto, exatamente um elemento de um conjunto.

Funções são importantes para estudar:● Estudar a representação da

complexidade de algoritmos;● Estudar o tamanho dos conjuntos;● Contar objetos

Kenneth Rosen

Cícero C. Quarto – Engcomp/UEMA6

Por que estudar Matemática Discreta

■ Grande parte da Matemática Discreta é voltada

para o estudo das estruturas discretas, usadas para representar objetos discretos (Rosen, 2009);

■■ Estruturas discretas: são estruturas matemáticas abstratas usadas para representar objetos discretos e as relações entre eles. Essas estruturas discretas incluem conjuntos, permutações, relações, grafos, árvores e mecanismos de estado finito.

Kenneth Rosen

Cícero C. Quarto – Engcomp/UEMA7

● Potencializa a capacidade de entender e criar

argumentos matemáticos;● Porta de entrada para cursos mais avançados

de todas as áreas das ciências matemáticas●● Ciência da Computação: estruturas de

dados, algoritmos, teoria da base de dados, teoria da automação, linguagens formais, teoria da compilação, segurança computacional, pesquisa operacional (otimização), IA, ..., n.

Por que estudar Matemática Discreta

Cícero C. Quarto – Engcomp/UEMA8

Por que estudar Matemática Discreta

Argumentar (raciocinar) matematicamente

Existe um inteiro que não é a soma de dois

quadrados

Para cada inteiro positivo n, a soma dos inteiros positivos

menores que ou iguais a n é n(n+1)/2

p1: “Todos os homens são mortais”

p2: “Sócrates é homem”Todo x é y

z é xLogo, z é y

Quantificador existencial Quantificador

universal

Lógica Proposicional

Lógica de Predicados

The Laws of Thought

George Boole(1854)

Aristóteles(384 a.C – 322 a.C)

Cícero C. Quarto – Engcomp/UEMA9

■ Argumentação matemática;■ Análise combinatória;■ Estruturas Discretas;■ Pensamento algoritmo;■ Aplicações e Modelos

Objetivos de um curso de Matemática Discreta

Cícero C. Quarto – Engcomp/UEMA10

● Quantas formas existem para escolher uma senha válida em um sistema

computacional?● Qual é a probabilidade de se ganhar na loteria?● Existe um elo entre dois computadores em uma rede de transmissão?● Como identificar e-mails com spam?● Como posso criptografar uma mensagem para que nenhum destinatário não

incluído possa lê-la?● Qual o menor caminho entre duas cidades usando o sistema de transporte?● Como se pode sortear uma lista de números inteiros, na qual os números

estão em ordem crescente?● Quantos passos são necessários para se fazer uma escolha?● Qual o número máximo de cores diferentes para colorir uma mapa sem

repetir cores entre cidades vizinhas?● Como é possível provar que um algoritmo escolhido corretamente resolve

determinado problema?● Como é determinado um circuito que soma dois inteiros?● Quantos endereços válidos da internet existem?

Tipos de problemas tratados pela Matemática Discreta

Cícero C. Quarto – Engcomp/UEMA11

Referências

Cícero C. Quarto – Engcomp/UEMA12

Obrigado pela atenção de todos e até a nossa próxima aula!!!

Prof. Cícero C. Quartocicero@engcomp.uema.brhttp://www.cicerocq.com