Matemática discreta e suas aplicações

Prévia do material em texto

Matemática discreta e suas aplicações 
Alunos: 
Samara Cíntia Andrade de Alcântara
Sarah Araújo da Costa Medeiros
Silas Nunes Nascimento
Sócrates Farias de Oliveira
Permutação
O que é permutação?
A permutação é uma técnica de contagem utilizada para determinar quantas maneiras existem para ordenar os elementos de um conjunto finito. Fazer uma permuta é realizar uma troca e, nos problemas de combinatória, significa trocar os elementos de lugar, considerando a ordenação desses.
Samara cintia
Permutação simples
Uma permutação simples é a ordenação dos elementos de um conjunto finito, quando seus elementos não se repetem, são distintos.
A fórmula para determinar a quantidade de permutações simples é:
Para determinar a quantidade total de permutações, multiplicamos a quantidade de possibilidades existentes na escolha de cada elemento. Dessa forma:
Samara Cintia
Exemplo 1:
Quantos anagramas existem para a palavra PATO?
Exemplo 2:
Considere uma fila de pessoas organizadas por ordem de chegada em que, em um determinado momento, há seis pessoas. De quantas formas diferentes essas pessoas poderiam estar ordenadas do primeiro ao último lugar?
Permutações com repetições
Uma permutação com elementos repetidos acontece quando em um conjunto de n elementos, alguns destes são iguais.
 Fórmula para determinar o número de permutações com repetição :
Exemplo 1:
Vamos determinar quantas permutações existem para a palavra OVO
O número de permutações simples com 3 elementos é dada por:
Algumas permutações se repetem e não podemos contá-las duas vezes.
 Para isso devemos dividir o valor de por 
Problema de alocação linear
O Problema de Alocação pode ser entendido como “o problema de alocar n células de produção a n tarefas. Cada uma das células é capaz de atender à tarefa segundo um custo peculiar a cada uma das n células”,segundo descrito em (Goldbarg e Luna, 2005). 
Exemplo: 
 
 Samara Cíntia
Programação linear
 
Na modelagem da programação linear utilizamos os seguintes passo:
 Variáveis de decisão : Variáveis cujos valores são controláveis e impactam a função-objetivo;
 Função-objetivo : Função matemática de uma ou mais variáveis de decisão e que se deseja maximizar ou minimizar (objetivo a ser atingido);
Restrições : Conjunto de relações matemáticas que impõem condições sobre os valores
que as variáveis de decisão podem assumir.
 
 Samara Cíntia
Exemplo
Uma empresa de desenvolvimento de software possui atualmente
quatro projetos de programação a serem desenvolvidos.
A empresa perguntou a 4 programadores quanto estariam dispostos
a receber ( em milhares de reais) para realizar cada um projetos.
A tabela abaixo contém as propostas.
Determine a qual projeto cada programador deve ser alocado.
Samara Cíntia
Exemplo
O número de alocações possíveis é finito;
O número total de combinações possíveis é n!
Tentar todas as combinações não é viável para n grande 
Pode - se resolver por programação linear 
Variáveis de decisão:
xij = 1 se o programador i for designado para o projeto j,
= 0 caso contrário.
Samara Cíntia
Exemplo
Restrições :
Cada programador realiza exatamente uma tarefa:
Função-objetivo (minimização do custo total):
Samara Cíntia
Exemplo
Restrições :
Cada programador realiza exatamente uma tarefa:
Função-objetivo (minimização do custo total):
Samara Cíntia
Modelo completo:
Samara Cíntia
Problema Quadrático de Alocação(PQA)
Objetivo: designar objetos a locais de modo que cada objeto seja atribuído a um único local e reciprocamente, quando são conhecidas as distâncias entre os pares de locais, os fluxos de algum tipo de demanda entre os pares de objetos e, nos casos mais gerais, os custos fixos de cada atribuição "objeto versus local". Ou seja, o Problema Quadrático de Alocação (PQA) consiste em encontrar uma alocação de custo mínimo dos objetos aos locais, sendo os custos obtidos pela soma dos produtos distância-fluxo.
O custo da alocação: a soma de todos pares de fluxos entre um par de 
facilidades multiplicado pela distância entre seus locais de alocação.
Sarah Medeiros
Definição formal de Problema Quadrático de Alocação 
->Formulação por permutação
Temos :
 -> um conjunto de n objetos
 -> um conjunto de n locais
 -> fluxo do objeto “i” ao objeto “j”, com “i” e “j” pertencentes a F
			 -> distância do local “u” ao local “v”, com “u” e “v” pertencentes a L
Como o PQA envolve determinar o custo mínimo de alocação de n objetos à n locais,claramente a atribuição objeto-local pode ser representada como uma permutação:
π : {0,...,n-1} -> {0,...,n-1}
Onde π(i) representa o local atribuído ao objeto i
Sarah Medeiros
 
Considere:
Sn -> o conjunto de todas as n-permutações
fij -> o fluxo entre os objetos i e j 
dp(i)p(j) -> a distância entre as localizações p(i) e p(j)
Se cada permutação p representar uma alocação de objetos a locais, a expressão 
matemática para o PQA toma a forma:
Função Objetiva:
								-> número total de objetos e lugares
								-> fluxo específico do objeto “i” ao objeto “k”
								-> distância do local “i” ao local “j”
								 -> se o objeto “i” for alocado ao local “j”,ou seja π(i) = j 
								 -> se não for, ou seja, π(i) != j
Sarah Medeiros
Exercícios de PQA (https://neos-guide.org/content/qap4)
Considerando 4 objetos (1, 2, 3, 4) e 4 locais (A, B ,C, D), a figura abaixo ilustra a distância entre os objetos e a “grossura” dos traços representa o fluxo entre os objetos. 
											
										
Sarah Medeiros
Teoria dos Grupos
Em Matemática, teoria dos grupos é o ramo que estuda as estruturas algébricas chamadas de grupos. O conceito de grupo é fundamental para a álgebra abstrata: outras bem conhecidas estruturas algébricas, como os anéis, corpos, e espaços vetoriais, podem todas ser vistas como grupos dotados de operações e axiomas adicionais. Grupos ocorrem em todas as partes da matemática, e os métodos da teoria dos grupos influenciaram fortemente vários ramos da álgebra.
Grupos são usados na Matemática e nas ciências em geral para capturar a simetria interna de uma estrutura na forma de automorfismos de grupo. Uma simetria interna está normalmente associada com alguma propriedade invariante, e o conjunto de transformações que preserva este invariante, juntamente com a operação de composição de transformações, forma um grupo chamado um grupo de simetria.
Sarah Medeiros
 
Utilização e importância dos grupos:
A teoria de Galois, que é a origem histórica do conceito de grupo, procura descrever as simetrias das equações satisfeitas pelas soluções de uma equação polinomial. Os grupos solúveis são assim chamados devido ao papel proeminente que possuem nesta teoria.
Na topologia algébrica, grupos são usados para descrever os invariantes de espaços topológicos. Eles são chamados de "invariantes" porque não mudam se o espaço é submetido a uma transformação.
O conceito de grupo de Lie é importante no estudo de equações diferenciais em variedades; ele combina análise e teoria de grupos e é portanto a ferramenta certa para descrever as simetrias das estruturas analíticas. 
Na análise combinatória, a noção de grupo de permutação e o conceito de ação de um grupo são frequentemente usados para simplificar a contagem de um conjunto de objetos.
A compreensão da teoria de grupos é fundamental na Física, onde é usada para descrever as simetrias que as leis da Física devem obedecer.
Em Química, grupos são utilizados para classificar estruturas cristalinas e a simetrias das moléculas.
Sarah Medeiros
Definição de Grupo
Um grupo é um conjunto com elementos G = {A, B, C, ...} para os quais existe uma operação binária G x G -> G frequentemente chamada de composição ou multiplicação, que satisfaz osseguintes axiomas:
Associatividade: Para quaisquer elementos a, b, c ∈ G o seu produto satisfaz a * (b * c) = (a * b) * c. Ou seja a composição de três ou mais elementos não depende dos resultados intermédios usados.
Elemento neutro: Existe um elemento especial e ∈ G que é neutro para a multiplicação. Isto é, para qualquer a ∈ G, a * e = e * a = a.
Elemento inverso: Todo o elemento a ∈ G tem um elemento inverso a-1 ∈ G tal que o resultado da sua composição é o elemento neutro. Isto é 
a * a-1 = a-1 * a = e.
Obs.: um conjunto com uma operação binária satisfazendo apenas o primeiro axioma (associatividade) diz-se um semigrupo, e um semigrupo que satisfaça os primeiros dois axiomas, diz-se um monóide.
Sarah Medeiros
Exemplos e contra-exemplos de grupos
Os números inteiros ℤ = {..., -2, -1, 0, 1, 2, ...} formam um grupo quando a composição utilizada é a soma.
Se considerarmos os números inteiros com a operação de multiplicação em vez da soma, deixa de ser um grupo porque quebra o axioma do elemento inverso.
Se considerarmos a operação de subtração em vez da soma no conjunto dos inteiros, mais uma vez deixa de ser um grupo porque quebra a regra da associatividade.
O conjunto dos números reais positivos ℝ > 0, ou reais não nulos ℝ \ {0} ou complexos não-nulos ℂ \ {0}, todos formam grupos com a operação de multiplicação.
O cubo mágico.
Sarah Medeiros
Problema do Caixeiro Viajante
Esse problema parte da seguinte hipótese, um vendedor precisa passar por n cidades durante sua viagem passando por elas apenas uma vez e voltando para a idade de partida, que caminho é o mais eficiente?
Em linhas gerais esse problema apresenta (n-1)!/2 quantidade de rotas.
Silas Nunes
Silas Nunes
Sabemos que essas condições nem sempre são mantidas no mundo real é comum, por exemplo ter pedágio em uma direção mas não na outra, numa viagem de carro, subir uma montanha consome mais combustível que descer, além do fato de que nem todos os pontos são diretamente acessíveis numa viagem.
Pontes de Königsberg
Na computação, esse problema está dentro do chamado Teoria dos Grafos, esse campo de estudo teve como ponto de partida o problema das pontes de Königsberg. 
Problema esse muito semelhante ao Caixeiro Viajante, porém com pontes numa mesma cidade.
Silas Nunes
Grafos
Grafos, por sua vez, é uma estrutura composta por um conjunto (não vazio) de pontos (vértices) e um conjunto de linhas que ligam esses pontos (arestas).
Essa estrutura permite codificar relacionamentos entre pares de objetos
Silas Nunes
Eficiência Computacional
Considerando um computador capaz de fazer 1 bilhão de adições por segundo e que no caso de 20 cidades, o computador precisa apenas de 19 adições informar o custo de uma rota, então ele será capaz de de calcular 10^9/10 = 53 Milhões de rotas por segundo.
Com essa relação, podemos montar a seguinte tabela.
	n	Rotas/Segundo (milhões)	Quantidade	Tempo necessário
				
	5	250	12	Irrelevante
	10	110	181.400	Irrelevante
	15	71	43.5 Bilhões	10Min
	20	53	6x10^16	63,5 Anos
Silas Nunes
Aplicações Diárias e Resoluções
O uso de grafos é muito útil na modelagem de Rotas aéreas, malhas ferroviárias, robustez numa malha elétrica, Redes de relacionamento etc. 
Por isso, não é viável procurar o melhor resultado possível e sim um resultado satisfatório, para isso, são utilizados métodos Heurísticos.
Um método muito famoso é do vizinho mais próximo, onde é levado em consideração a melhor decisão agora, no curto prazo. 
Silas Nunes
Agendamento - Diagrama de PERT - Ordenação topológica
 Quando pensamos em agendamento de funções estamos ligando a aplicação canônica da ordenação topológica está na programação de uma sequência de trabalhos ou tarefas, com uso em potencial todas as vezes em que o problema abordado envolve uma ordem espacial.
Sòcrates Farias
Curiosidade:
 O algoritmo da ordenação topológica surgiu com o contexto da técnica de PERT(Program Evaluation and Review Technique) para o agendamento de tarefas em gerenciamentos de projetos.
Agendamento - Diagrama de PERT - Ordenação topológica
 Temos na ordenação que os trabalhos são representados por vértices, e existe uma aresta x para y se o trabalho x deve estar concluído antes do trabalho y pode ser iniciado. Por exemplo : ao lavar roupas, a máquina de lavar deve terminar antes de se poder colocar as roupas para secar. Em seguida, uma ordenação topológica dá uma ordem na qual se possa realizar os trabalhos.
Sócrates Farias
Para entendermos melhor, devemos aprofundar nosso conhecimento no diagrama de PERT.
DIAGRAMA DE PERT
 Definição:
 Um diagrama de PERT é uma ferramenta de gerenciamento de projetos usada para analisar cada tarefa envolvida na conclusão de um projeto. Voltado para projetos de grande escala, os diagramas de PERT (ou gráficos de PERT) identificam o tempo necessário para concluir cada tarefa, estimando os requisitos de tempo mais curtos, longos e prováveis.
Sócrates Farias
EXEMPLO
DIAGRAMA DE PERT
 Definição:
 Um diagrama de PERT é uma ferramenta de gerenciamento de projetos usada para analisar cada tarefa envolvida na conclusão de um projeto. Voltado para projetos de grande escala, os diagramas de PERT (ou gráficos de PERT) identificam o tempo necessário para concluir cada tarefa, estimando os requisitos de tempo mais curtos, longos e prováveis.
Sócrates Farias
EXEMPLOS
Sócrates Farias
Sócrates Farias
PERT x CPM
 O método PERT e o método do caminho crítico (CPM) são métodos de gerenciamento de projetos focados no fluxo e na sequência de tarefas em projetos de grande escala. Ambos são ótimas escolhas quando se tem a ideia de melhorar a eficiência de um projeto
 A principal diferença entre PERT e CPM é que os diagramas de PERT geralmente são usados para determinar o tempo de conclusão de um projeto, enquanto o CPM é usado em projetos previsíveis e que ocorrem com frequência. Gráficos PERT são métodos de planejamento e gerenciamento de tempo, enquanto o CPM é usado para controlar custos e tempo.
Sócrates Farias
SIMBOLOGIA DO DIAGRAMA PERT
OBS: O diagrama de PERT usa os símbolos e a notação da avaliação de programas e da revisão de técnicas para representar o fluxo de tarefas dependentes e outros eventos de um projeto.
Evento PERT: o ponto em um diagrama de PERT que marca a conclusão ou o início de uma ou mais tarefas. Esse ponto só pode ocorrer quando todas as atividades que levam a este evento forem concluídas.
Evento predecessor: um evento que precede imediatamente outro no projeto, sem a intervenção de nenhum outro evento.
Sócrates Farias
SIMBOLOGIA DO DIAGRAMA PERT
Evento sucessor: um evento que segue imediatamente outro, sem a intervenção de outro evento.
Caminho crítico: o caminho entre o primeiro e o último eventos do projeto, incluindo todas as tarefas e durações do projeto, que somam à maior duração geral do projeto. Identificando a maior duração possível do projeto, você pode determinar o menor tempo possível para sua conclusão.
Atividade no caminho crítico: tarefas que devem iniciar e terminar no prazo para que o projeto seja concluído dentro do cronograma específico.
Sócrates Farias
SIMBOLOGIA DO DIAGRAMA PERT
Falha no caminho crítico: o ato de adicionar recursos ao projeto para concluir as atividades e comprimir o cronograma.
Agilização: atividades do projeto que, originalmente, deveriam ser concluídas em sequência, mas que são executadas simultaneamente para economizar tempo de execução. 
Tempo de atraso: o atraso entre tarefas que têm dependências.
Tempo de execução: o tempo necessário para concluir uma ou mais tarefas interdependentes.
Sócrates Farias
SIMBOLOGIA DO DIAGRAMA PERT
Sócrates Farias
FÓRMULA DE PERT
 Existem várias variáveis que afetam a conclusão da tarefa, que dificultam a estimativa do tempo de conclusão do projeto. Usuários de diagramas de PERT geralmente usam quatro cálculos padrão para determinar a duração do projeto:
Tempo otimista (O): a menor quantidadepossível de tempo necessária para realizar uma tarefa
Tempo mais provável (M): uma estimativa embasada de quanto tempo leva para a tarefa ser concluída sem problemas ou atrasos
Tempo pessimista (P): a quantidade máxima de tempo necessária para realizar uma tarefa
Tempo esperado (E): estimativa razoável de quanto tempo uma tarefa levará para ser concluída, levando em consideração possíveis problemas ou atrasos
Sócrates Farias
FÓRMULA DE PERT
TEMOS QUE :
 A equação básica de estimativa PERT usada para determinar o tempo esperado é:
E = (O + 4M + P)/6.
 Após identificar cada estimativa de tempo, eles podem ser inseridos na fórmula PERT para calcular, com melhor precisão, a duração do projeto. 
Sócrates Farias
EXEMPLO 1 - PERT
 Usando a reforma simples de uma casa. Se a estimativa de tempo otimista é de 160 dias, a estimativa de tempo pessimista é de 365 dias e a estimativa de tempo mais provável é de 250 dias, a equação será mais ou menos esta:
E = (O + 4M + P)/6.. 
RESOLUÇÃO :
E = (160 + 4 x 200 + 365)/6 
R = Podemos estimar que a reforma da casa estará concluída em
aproximadamente 221 dias
Sócrates Farias
EXEMPLO 2 - PERT
A figura abaixo apresenta um diagrama PERT-CPM e uma tabela com os tempos das atividades referentes a uma obra.
O tempo final da obra, em unidades de tempo (u.t.), e o tempo máximo da atividade F para que não haja interferência no tempo final são, respectivamente:
A) 17 e 2 ;
B) 15 e 2;
C) 15 e 1;
D) 16 e 3;
E) 17 e 3;
Sócrates Farias
EXEMPLO 2 - PERT
RESOLUÇÃO:
 Tempo para cada caminho:
 1/2/5/6 = A+D+G = 4+3+8 = 15 u.t
 1/3/5/6 = B+E+G = 5+4+8 = 17 u.t
Tempo total da obra = caminho mais longo = 17 u.t
-Para que não ocorra interferência no tempo final o caminho 1/2/4/5/6 não pode ser maior que 17 u.t
1/2/4/5/6 = A+C+F+G < 17
4+2+F+8 ≤ 17 
4+2+F+8 ≤ 17 
R= Letra E) 17 e 3
F ≤ 3
Sócrates Farias
ORDENAÇÃO TOPOLÓGICA
Definição :
A ordenação topológica de um DAG (directed acyclic graph) G= (V, E) é uma ordem linear
(sequência, lista) de vértices tal que se G contém um arco (u,v) então u aparece antes de v na ordem linear.
Claramente, se o grafo for cíclico, tal ordem não existe.
Sócrates Farias
ORDENAÇÃO TOPOLÓGICA-ALGORITMO
 Os algoritmos usuais de ordenação topológica tem tempo de execução linear no número de nós(vértices), mais o número de arestas (O(|V|+|E|)).
 Um desses algoritmos, descrito pela primeira vez por Kahn, trabalha escolhendo vértices na mesma ordem da eventual ordenação topológica. Primeiro, encontra uma lista de nós "íniciais", que não tem arestas de entrada e os insere em um conjunto S; pelo menos um nó devem existir se o grafo é acíclico. 
Sócrates Farias
ORDENAÇÃO TOPOLÓGICA-ALGORITMO
Temos então :
Sócrates Farias
ORDENAÇÃO TOPOLÓGICA-ALGORITMO
Sócrates Farias
ORDENAÇÃO TOPOLÓGICA-ALGORITMO
Além disso:
 A busca em profundidade (DFS) pode também ser utilizada para obter
uma ordenação topológica, adaptando o algoritmo conforme descrito por
Robert Tarjan .
 Para isso:
-iniciando a visita em v , visite todos os seus adjacentes (v ,w )
chamando a função DFS recursivamente para w .
-após analisar a lista de adjacências de cada vértice v sendo
processado, adicione-o na ordenação topológica.
Sócrates Farias
ORDENAÇÃO TOPOLÓGICA-ALGORITMO
Exemplo de cód em C de 
ordenação em DFS
Sócrates Farias
ORDENAÇÃO TOPOLÓGICA-ALGORITMO