Matemática Discreta

Matemática Discreta

1. Teoria dos Conjuntos

   • Notação
     • Elementos
     • Conjuntos
     • Relação de Pertença
   • Propriedade Lógicas (uma proposição)
     • Exp: C = {x / x E N ^ x é ímpar ^ x <= 5}
   • Representação de Conjuntos
     • 1- Por Extensão
     • 2- Por Compreensão
     • 3- Por Gráfico
     • 4- Por Diagrama de Vem

2. Indução Matemática

   • Princípio de indução Matemática (PIM)
     • 1- Prove que 1+2+3+...+n = (n(n+1)) / 2 , tal que inteiro n>=1
     • 2- Mostrar que vale para n=1, sendo 1=1
     • 3- Supor que vale para n=k, chegando a Hipótese Indutiva
     • 4- Provar que vale para n=K+1
     • 5- Portanto, como a proposição vale para n=k+1, então vale tal que inteiro n>=1

3. Análise Combinatória

   • Regra da Soma (Princípio Aditivo PA)
   • Regra do Produto (Princípio Multiplicativo PM)
   • Permutação
     • Tem ordem e usa todos os elementos
     • Pn=n!
   • Arranjo Simples
     • Ordem e não usa todos elementos
     • Notação: nAp=n!/(n-p)!
   • Combinação Simples
     • Sem ordem, não usa todos elementos e nada se repete
     • Notação: nCp=n!/p!(n-p)!
   • Combinação Complementares
     • nCp = nCn-p
   • Lema de Kaplansky
     • n-p+1Cp
   • Arranjo com Repetição
     • nARp=n^p
   • Permutação com Repetição
     • nPRn1,n2,n3,...=n!/n1!n2!n3!...
   • Permutação Circular
     • (Pc)n=(n-1)!
   • Combinação com Repetição
     • nCRp=n+p-1Cp

4. Equações lineares com coeficientes unitários

   • x1+x2+x3+...+xr=n sendo r e n inteiros
   • Teorema
     • Nº de solucoes inteiras positivas(>0)
       • n-1Cr-1
     • Nº de solucoes inteiras não negativas(>=0)
       • n+r-1Cr-1

5. Coeficientes Binomiais

   • Binômio
     • soma de dois simbolos distintos, qualquer expressao da forma a+b
   • Binômio de Newton
     • permite escrever na forma canonica o polinomio correspondente a potencia de um binomio. O binomio de Newton permite desenvolver a n-ésima potencia de um binomio e usamos a expressao (a+b)^n
   • Termo
     • n=2=>(a+b)^2 demonstra 4 termos=2^2
     • n=3=>(a+b)^3 demonstra 8 termos=2^3
   • Termo Geral
     • n=ultimo termo
     • a^i b^j onde i+j =n
     • (a+b)^n = (i=0 SOMATORIO n nCi a^i b^(n-i))
   • Triangulo de Pascal
     • É formado pelos coeficientes da expansao do binomio de newtom. É uma matriz de números que enfatiza essa simetria rearrumando as linhas da tabela de modo que se alinham em seus centros, quando escrito o triângulo de Pascal
     • Propriedades
       • Desenvolvimento:
         • (a+b)^n = (i=0 SOMATORIO n nCi a^i b^(n-i))
         • Termo geral:
           • Ti+1 = nCi a^i b^(n-i)
       • Nº de termos do desenvolvimento de (a+b)^n é n+1 termos
       • Termos equidistantes dos extremos de (a+b)^n são iguais
       • A soma dos coeficientes de (a+b)^n é igual a 2^n
       • Cada coeficiente é igual a soma do nº imediatamente acima e do antecessor do nº de cima
       • A soma das diagonais resulta a sequencia de Fibonacci

6. Principio de inclusão e exclusão

   • Formula para um nº total de elementos na uniao de um nº finito de conjuntos
     • Dois conjuntos:
       • n(A U B) = n(A) + n(B) - n(A interseção B)
     • Tres conjuntos:
       • n(A U B U C) = n(A) + n(B) + n(C) - n(A interseção B) - n(A interseção C) - n(B interseção C) + n(A interseção B interseção C)
   • Cardinalidade da União de N conjuntos
     • Representa a quantidade de nº de elementos na uniao de n conjuntos finitos A1,A2,A3,...An
       • |A1 U A2 U ... U An| = SOMATORIO |Ai1| - SOMATORIO |Ai1 intersecao Ai2| + SOMATORIO |Ai1 intersecao Ai2 intersecao Ai3| - +...+ (-1)^(n-1) |A1 intersecao A2 intersecao A3 intersecao ... intersecao An|.

7. Funções Geradoras

   • Funções ordinárias
     • Uma série de potência é uma série infinita da forma a0+a1x+a2x^2+a3x^3+... onde ai varia para i=0,1,2,3,... são numeros reais e x é variavel
   • eq. x1+x2+x3+...+xr = n
     • Associar um polinômio para cada variável
   • Sequência
     • f(x)=1+x+x^2+x^3+...
       • forma fechada
         • f(x) = 1/(1-x)

8. Relações de Recorrência

   • é uma técnica matemática que permite definir sequências, conjuntos, operações ou até mesmo algoritmos partindo de problemas particulares para problemas genéricos
   • Uma relacao de recorrencia define uma funcao por meio de uma expressao do n-ésimo termo de uma sequencia um funcao dos seus antecessores.
   • Uma relacao de rocorrencia é uma equacao onde cada termo de uma sequencia é definido um funcao dos elementos anteriores. Assim, quando resolvemos uma relacao de recorrencia encontramos uma formula explicita que nos da o termo geral da sequencia.
     • Formula Explicita
     • Termo Geral
     • Resolver:
       • Expandir -> Conjecturar -> Verificar
   • Relação Linear
     • Uma recorrencia é linear se o termo geral pode ser escrito na forma:
       • an=C1a(n-1)+C2a(n-2)+ ... + Cka(n-k)+ f(n) para qualquer k fixo e n>=k
         • Se f(n) = 0 a lei de recorrencia linear é chamada homogênea. Caso contrário é não-homogênea
     • Procedimentos
       • Exp: an = a(n-1) + a(n-2) (relacao de recorrencia)
       • Exp: a0 = 1 e a1 = 1
       • Fazer a substituicao na equacao
         • Achar a equacao caracteristica
       • Bascara
       • Usar condições iniciais
       • Solucao da relacao de recorrencia

9. Teoria dos Grafos

   • Nós(ponto exp:e1,e2), arestas(ligacao entre os nos) e nós ou vértices(exp:e2); Nós = Vértices; Arcos = Arestas; G(v,a), onde: V={e1,e2} A={(e1,e2)} Grafo:e1------------->e2
   • Grafo Simples
     • é um grafo que nao contem lacos nem arestas multiplas. Exp: grafo touro
   • Grafo completo
     • É um grafo simples onde cada vertice se conecta a todos os outros vertices
   • Grafo regular
     • É um grafo onde todos os vertices possuem o mesmo grau.
   • Numero de arestas
     • n(numero de vertices) Kn tem (2, n=nº de vertices) = (n(n-1))/2
   • Grafo nulo
     • é o grafo ujo conjunto de vertices é vazio(um grafo deve ter pelo menos u vertice)
   • Grafo vazio
     • é o grafo cujo conjunto de arestas é vazio
   • Grafo trivial
     • é o grafo que possui apenas um vertice
   • Grafo conexo
     • um grafo G=(V,E) é conexo se existir um caminho entre qualquer par de vertices. Caso contrário é desconexo.
   • Grafo Bipartido
     • os vertices V do grafo sao divididos em dois conjuntos v1 e v2. Nao ha arestas entre elementos do mesmo conjunto.
   • Conectividade:
     • Multigrafo: ou pseudografo é um grafo nao dirigido que pode possur arestas multiplas (ou paralelas), ou seja, arestas com mesmos nós finais. Assim, dois vertices podem estar conectados por mais de uma aresta. Formalmente, um ultigrafo G é um par ordenado.
     • Vertice isolado
       • é o vertice que nao possui arestas incidentes(grau nulo)->grafo trivial
     • Vertice foha ou terminal
       • é o vertice que possui grau1
     • Vizinhos de um vertice
       • sao os vertices adjacentes a ele.
   • Propriedade:
     • Laço:(loop) num grafo ou nu dígrafo é uma aresta e em E cujas terminacoes estao no mesmo vertice. Pseudografo:é um grafo que contem arestas paralelas e laço Árvore:é um grafo simples acíclico e conexo. Às vezes, um vertice da arvore é distinto e chamado de raiz. As arvores sao muito usadas como estrutura de dados em informática. Tipos básicos: Os grafos podem ser: -Dirigidos(arestas indicadas com seta, reresentam pares ordenados) -Não dirigidos(arestas não sao indicadas por seta)
   • Caracaracteristicas:
     • Os grafos podem ser: -Rotulados(os rotulos indicam alguma caracteristica para cada par de vertices, ou seja, para cada aresta). -Nao rotulados
   • Conceitos:
     • Dois vertices que sao incidentes a uma mesma aresta sao ditos adjacentes. Duas arestas que sao incidentes a u mesmo vertice sao ditas adjacentes
   • Representacao Grafica:
     • Uma aresta conecta dois vertices; esses dois vertices sao ditos como incidentes à aresta. A vâlencia (ou grau) de um vertice é o numero de arestas incidentes a ele, como loops contados duas vezes. *Se a aresta é finita, entao o GRAU total dos vertices é o DOBRO do número de arestas.

10. Somatório

    • Generalizando
      • {a1+a2+a3+...+an} = i=n Somatório n ai
        • i=n (limite inferior), n (limite superior), a1 (termo geral)
    • Propriedades
      • Dividida em 6 propriedades
    • Expansão