Matemática discreta

Grafos como este estão entre os objetos estudados pela matemática discreta, por suas interessantes propriedades matemáticas, a sua utilidade como modelos de problemas do mundo real, e sua importância no desenvolvimento de algoritmos computacionais.

Matemática discreta, também chamada matemática finita, é o estudo das estruturas algébricas que são fundamentalmente discretas, em vez de contínuas. A palavra "discreta" nesta situação tem origem no inglês "discrete", significando "diferente", "distinta" e não seu sentido habitual. 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.

Em contraste com os números reais que têm a propriedade de variar "suavemente", os objetos estudados na matemática discreta - como números inteiros , grafos e afirmações lógicas ^[1] - não variam suavemente, desta forma, mas têm valores distintos separados.^[2]] A matemática discreta, portanto, exclui temas em “matemática contínua", como cálculo e análise . Objetos discretos muitas vezes podem ser enumerados por inteiros. Mais formalmente, a matemática discreta tem sido caracterizada como o ramo da matemática que lida com conjuntos contáveis^[3] (conjuntos que possuem a mesma cardinalidade como subconjuntos dos números naturais, incluindo números racionais, mas nem todos números reais). No entanto, não há exato, uma definição universalmente aceita do termo "matemática discreta".^[4] De fato, a matemática discreta é descrita menos pelo que está incluído do que pelo que é excluído: quantidades continuamente variáveis e noções de relações.

O conjunto de objetos estudados na matemática discreta pode ser finito ou infinito. O termo matemática finita é às vezes aplicado na parte do campo da matemática discreta que lida com conjuntos finitos, particularmente em áreas relevantes para os negócios.

As pesquisas em matemática discreta aumentaram na segunda metade do século XX, sendo parte, devido ao desenvolvimento de computadores digitais que operam em passos discretos e armazenam dados em bits discretos. Os conceitos e notações da matemática discreta são úteis para estudar e descrever objetos e problemas em ramos da ciência da computação, tais como algoritmos de computador, linguagens de programação, criptografia, prova automática de teoremas, e desenvolvimento de software. Por outro lado, implementações computacionais são significativas na aplicação de ideias da matemática discreta para problemas do mundo real, como em pesquisas operacionais.

Embora os principais objetos de estudo em matemática discreta sejam objetos distintos, métodos analíticos de matemática contínua são também frequentemente utilizados. A matemática discreta tornou-se popular em décadas recentes devido às suas aplicações na ciência da computação (devido ao desenvolvimento de computadores digitais que funcionam em etapas discretas e ao armazenamento de dados em bits discretos). Conceitos e notações da matemática discreta são úteis para o estudo ou a expressão de objetos ou problemas em algoritmos de computador e linguagens de programação.

Algumas aplicações:

Teoria dos jogos
Teoria das filas
Teoria dos grafos
Geometria e topologia combinatória
Programação linear
Criptografia (incluindo a criptologia e a criptoanálise)
Teoria da computação

Predefinição:Matemática

Grandes desafios, passado e presente

Várias pesquisas em teoria dos grafos foram motivadas pelas tentativas de provar que todos os mapas, como este, pode ser colorido com apenas quatro cores. Kenneth Appel e Wolfgang Haken finalmente provaram isso em 1976.^[5]

A história da matemática discreta envolveu uma série de problemas desafiadores que concentraram a atenção em diversas áreas de campo. Na teoria dos grafos, várias pesquisas foram motivadas por tentativas de provar o teorema das quatro cores, exposto pela primeira vez em 1852, mas sem ser demonstrado até 1976 (por Kenneth Appel e Haken, Wolfgang, usando a assistência substancial de um computador).^[5]

Na lógica, o segundo problema na lista de Gauss abertos de Carl Friedrich Gauss, apresentados em 1900, era provar que os axiomas da aritmética são consistentes. O segundo teorema da incompletude de Gödel, provado em 1931, mostrou que isto não era possível - pelo menos não dentro da própria aritmética. O décimo problema de Hilbert foi determinar se uma dada equação polinomial diofantina, com coeficientes inteiros, tem uma solução inteira. Em 1970, Yuri Matiyasevich provou que esta não poderia ser feita.

A necessidade de quebrar códigos alemães na Segunda Guerra Mundial levou a avanços em criptografia e ciência da computação teórica, com o primeiro computador digital eletrônico programável sendo desenvolvido no Parque Bletchley da Inglaterra. Ao mesmo tempo, os requisitos militares motivaram avanços na pesquisa operacional. A Guerra Fria mostrou que a criptografia era importante, com os avanços fundamentais, como a criptografia de chave pública que veio sendo desenvolvida nas décadas seguintes. A pesquisa operacional permaneceu como uma ferramenta importante na gestão de negócios e projetos, com o método do caminho crítico a ser desenvolvido em 1950. A indústria de telecomunicações também motivou os avanços na matemática discreta, particularmente em teoria dos grafos e teoria da informação. A verificação formal de declarações de lógica tem sido necessária para o desenvolvimento de software de sistemas de segurança crítica, e os avanços na prova automática de teoremas tem sido impulsionada para essa necessidade.

A geometria computacional tem sido uma parte importante da computação gráfica incorporada em modernos jogos eletrônicos e ferramentas de Projeto assistido por computador.

Vários campos da matemática discreta, ciência da computação teórica, particularmente, teoria dos grafos e combinatória, são importantes na abordagem dos desafiantes problemas de bioinformática, associados com a compreensão da árvore da vida.^[6]

Atualmente, um dos problemas mais famosos abertas em ciência da computação teórica é o problema P = NP, que envolve a relação entre as classes de complexidade P e NP. O Instituto de Matemática Clay ofereceu US$ 1 milhão como prêmio para a primeira prova correta, juntamente com prêmios para seis outros problemas matemáticos.^[7]

Tópicos em matemática discreta

Lógica, lógica matemática (provas, indução matemática)

A Lógica é o estudo dos princípios de validação de fundamentação e inferência, bem como de consistência, solidez e perfeição. Por exemplo, na maioria dos sistemas de lógica (exceto na lógica intuicionista), a lei de Peirce (((P→Q)→P)→P) é um teorema. Para a lógica clássica, pode ser facilmente verificada com uma tabela da verdade. O estudo da prova matemática é particularmente importante na lógica, e tem aplicações para prova automática de teoremas e verificação formal de software.

As fórmulas lógicas são estruturas discretas, bem como provas, que formam árvores finitos,^[8] ou, mais em geral, dirigido gráfico acíclicos estruturas ^[9]^[10] (a cada passo de inferência combina-se um ou mais ramos premissas para dar uma única conclusão). Os valores verdade de fórmulas lógicas geralmente formam um conjunto finito, geralmente restrito a dois valores: o verdadeiro e o falso, mas a lógica também pode ser de valor-contínuo, por exemplo, a lógica fuzzy. Conceitos como prova infinita de árvores ou derivação infinitas de árvores também foram estudadas,^[11] e. g., a lógica infinitária.

Teoria dos conjuntos, relações em conjuntos, funções e grupos

A teoria dos conjuntos é o ramo da matemática que estuda os conjuntos, que são coleções de objetos, como {azul, branco, vermelho} ou o conjunto (infinito) de todos os números primos. Conjuntos parcialmente ordenados e conjuntos com outras relações têm aplicações em diversas áreas.

Na matemática discreta, conjuntos contáveis (incluindo conjuntos finitos) são o foco principal. O início da teoria dos conjuntos, como um ramo da matemática, é normalmente marcado pelo trabalho de Georg Cantor, distinguindo diferentes tipos de conjuntos infinitos, motivados pelo estudo de séries trigonométricas, e um maior desenvolvimento da teoria dos conjuntos infinitos está fora do escopo da matemática discreta. Por outro lado, o trabalho contemporâneo na teoria descritiva dos conjuntos faz uso extensivo de matemática contínua tradicional.

Probabilidade, teoria das probabilidades e cadeias de Markov

A Teoria de probabilidade discreta lida com eventos que ocorrem em espaços amostrais contáveis. Por exemplo, as observações de contagem, como o número de aves em bandos compreendem valores numéricos restritamente naturais {0, 1, 2, ...}. Por outro lado, as observações contínuas, tais como os pesos das aves, compreendem valores de números reais, e seria normalmente modelada por uma distribuição de probabilidade contínua, tais como a normal. Distribuições de probabilidade discretas podem ser usadas para aproximar as contínuas e vice-versa. Para situações altamente restritivas, como jogar dados ou experimentos com baralho de cartas, o cálculo da probabilidade de eventos é basicamente combinatória enumerativa.

Teoria dos números

A espiral de Ulam de números, com pontos pretos que mostram números primos. Este diagrama aponta para padrões na distribuição dos números primos.

A Teoria dos números está relacionada com as propriedades de números em geral, particularmente inteiros. Tem aplicações para a criptografia, a criptoanálise e criptologia, particularmente em relação à aritmética modular, equações diofantinas, congruências linear e quadrática, números primos e testes de primalidade. Outros aspectos distintos da teoria dos números incluem geometria dos números. Em teoria analítica dos números, as técnicas de matemática contínuas também são utilizadas. Tópicos que vão além de objetos discretos incluem números transcendentais, aproximação diofantina, análise p-adic e corpos de função.

Combinatória

A combinatória estuda a maneira pela qual as estruturas discretas podem ser combinadas ou arranjadas. A combinatória enumerativa concentra-se na contagem do número de certos objetos combinados - por exemplo, o caminho de Doze fornece uma estrutura unificada para a contagem de permutações, combinações e partições.

Combinatória analítica diz respeito à enumeração (ou seja, determinar o número) de estruturas combinatórias usando ferramentas de análise complexa e teoria da probabilidade. Em contraste com a análise combinatória enumerativa que usa fórmulas combinatórias explícitas e funções geratrizes para descrever os resultados, a análise combinatória analítica visa a obtenção de fórmulas assintótica.

A teoria de projetos é um estudo de modelos combinatórios, que são coleções de subconjuntos com certas propriedade de interseção.

A teoria de partição estuda vários problemas assintóticos e de enumeração relacionados com partições inteiras, e está intimamente relacionado com Série-Q, funções especiais e polinômios ortogonais. Originalmente uma parte da teoria dos números e análise, a teoria da partição é considerada, atualmente, uma parte de análise combinatória ou campo independente. A teoria da ordem é o estudo dos conjuntos parcialmente ordenados, além deste dos finitas e infinitas.

Teoria dos grafos

A Teoria dos grafos tem laços estreitos com a teoria dos grupos. Este grafo de um tetraedro truncado está relacionado com o grupo alternado 'A₄.

A Teoria dos grafos, ou seja, o estudo dos grafos e das redes, é muitas vezes considerada como parte da análise combinatória, mas tem tido um crescimento bastante grande, suficiente e distinto, com seu próprio tipo de problemas, devendo ser considerado como um sujeito de regras próprias.^[12] Os grafos estão entre os objetos principais de estudo na matemática discreta. Eles estão entre os modelos mais onipresentes de ambas as estruturas naturais e criadas pelo homem. Eles podem modelar muitos tipos de relações e dinâmicas de processos em sistemas físicos, biológicos e sociais. Na ciência da computação, eles podem representar redes de comunicação, organização de dados, dispositivos computacionais, fluxo de computação, etc. Em matemática, eles são úteis na geometria e certas partes da topologia, e.g., teoria dos nós. A teoria dos grafos algébricos tem estreitas ligações com grupo teoria. Há também gráficos contínuos , no entanto, para a pesquisa maior parte, em teoria dos grafos cai dentro do domínio da matemática discreta.

Teoria da computação, algoritmos e recursividade

Complexidade estuda o tempo tomado por algoritmos, como esta rotina de ordenação.

Ciência da computação teórica inclui áreas de matemática discreta relevantes para a computação. Ele se baseia fortemente na teoria dos grafos e lógica . Incluído dentro ciência da computação teórica é o estudo de algoritmos para calcular os resultados matemáticos. Computabilidade estuda o que pode ser computado em princípio, e tem laços estreitos com a lógica, enquanto os estudos de complexidade de prazos por cálculos. teoria de autômatos e linguagem formal teoria estão intimamente relacionados com computabilidade. redes de Petri e álgebras de processos são usados para sistemas de computador modelo e métodos da matemática discreta são utilizadas na análise de circuitos eletrônicos VLSI. A geometria computacional aplica algoritmos para problemas geométricos, enquanto que a análise de imagens de computador aplica às representações de imagens. Ciência da computação teórica inclui também o estudo de diversos temas contínuos computacionais.

Teoria da informação

Os códigos ASCII para a palavra "Wikipedia", dado aqui em binário , proporcionam uma forma de representar a palavra em teoria da informação , bem como para o processamento de informações algoritmos.

A teoria da informação envolve a quantificação de informação . Estreitamente relacionado é teoria da codificação que é usada para desenhar eficiente e fiável a transmissão de dados e métodos de armazenamento. A teoria da informação também inclui temas contínuos, tais como: sinais analógicos , codificação analógicos , criptografia analógico .

Álgebra

Estruturas algébricas ocorrer como ambos os exemplos e exemplos discretas contínuas. Álgebras discretos incluem: álgebra booleana usado em portas lógicas e programação; álgebra relacional usado em bancos de dados ; versões discretas e finito de grupos , anéis e campos são importantes na teoria de codificação algébrica ; discretos semigrupos e monoids aparecer na teoria de linguagens formais .

Cálculo de diferenças finitas, cálculo discreto ou análise discreta

Uma função definida num intervalo de números inteiros é normalmente chamado de sequência . Uma sequência pode ser uma sequência finita a partir de uma fonte de dados, ou uma sequência infinita de um sistema dinâmico discreto . Tal função discreta pode ser definido explicitamente por uma lista (se o domínio é finito), ou por uma fórmula para o seu termo geral, ou pode ser dada implicitamente por uma relação de recorrência ou equação de diferença . Equações de diferenças são semelhantes a um equações diferenciais , mas substitua diferenciação tomando a diferença entre os termos adjacentes, pois eles podem ser usados para equações diferenciais aproximados ou (mais frequentemente) estudados em seu próprio direito. Muitas perguntas e métodos relacionados com equações diferenciais têm contrapartidas para equações de diferença. Por exemplo, onde há transformadas integrais em análise harmônica para o estudo de funções contínuas ou sinais analógicos, há transformações discretas para funções discretas ou sinais digitais. Bem como a métrica discreta há mais gerais discretos ou finitos espaços métricos e finitos espaços topológicos .

Geometria

Geometria computacional computador aplica algoritmos para as representações de geométricos objetos.

Geometria discreta e geometria combinatória são cerca propriedades combinatórias de coleções de objetos geométricos discretos. Um tópico de longa data na geometria discreta é a telha do avião . Geometria computacional aplica algoritmos para problemas geométricos.

Topologia

Apesar de topologia é o campo da matemática que formaliza e generaliza a noção intuitiva de "deformação contínua" de objetos, que dá origem a muitos temas distintos, o que pode ser atribuído em parte ao foco na invariantes topológicos, que normalmente levam-se valores discretos. Veja topologia combinatória, teoria dos grafos topológica, combinatória topológicos, topologia computacional, espaço topológico discreto, espaço topológico finito, topologia (química).

Investigação ou pesquisa operacional

PERT gráficos como este proporcionam uma técnica de gestão de negócios com base na teoria dos grafos.

A pesquisa operacional fornece técnicas para resolver problemas práticos de negócios e outras áreas - problemas como a alocação de recursos para maximizar o lucro, ou agendar atividades do projeto para minimizar o risco. Técnicas de pesquisa operacional incluem programação linear e outras áreas de otimização , teoria das filas , teoria de programação , teoria de rede . A pesquisa operacional também inclui temas contínuas, tais como tempo contínuo processo de Markov de tempo contínuo, martingales , otimização de processos e contínua e híbrida teoria de controle .

Teoria dos jogos, teoria da decisão, teoria da utilidade, teoria da escolha social

Cooperar	Cooperar	Defeito
Defeito	-1, -1	-10, 0

Matriz de payoff para o dilema do prisioneiro, um exemplo comum em teoria dos jogos. Um jogador escolhe uma linha, o outro uma coluna, o par resultante dá seus retornos 0, -10 -5, -5

A teoria da decisão está relacionada com a identificação de valores, incertezas e outras questões relevantes em uma dada decisão, sua racionalidade, e a decisão resultante ideal.

Teoria da utilidade é sobre medidas da relação econômica de satisfação, ou conveniência de, consumo de bens e serviços diversos.

Teoria da escolha social é de cerca de votação. Uma abordagem mais puzzle baseado a votação é teoria votação .

Teoria dos jogos lida com situações onde o sucesso depende das escolhas dos outros, o que torna a escolha do melhor curso de ação mais complexa. Há jogos mesmo contínuas, ver jogo diferencial . Os tópicos incluem a teoria dos leilões e divisão justa .

Discretização

Discretização diz respeito ao processo de transferência de modelos contínuos e equações em homólogos discretos, muitas vezes para fins de fazer cálculos mais fácil usando aproximações. análise numérica fornece um exemplo importante.

Analogia discreta de matemática contínua

Existem muitos conceitos em matemática contínuas que têm versões distintas, tais como cálculo discreto , distribuições de probabilidade discretas , transformadas de Fourier discretas , geometria discreta , logaritmos discretos , geometria diferencial discreta , cálculo exterior discreta , teoria de Morse discreta , equações diferenciais , sistemas dinâmicos discretos , e medidas vetor discretos .

Em matemática aplicada , modelagem discreta é o análogo discreto de modelagem contínua . Na modelagem discreta, fórmulas discreto estão aptos a dados . Um método comum neste tipo de modelagem é a utilização de relação de recorrência .

Matemática híbrida - discreta e contínua

O cálculo em escalas temporais foi introduzido em 1988, por Stefan Hilger,^[13]^[14]como uma forma de unificar o cálculo diferencial e o cáculo de diferenças e tem aplicações em campos que exigem modelagem simultânea de dados discretos e contínuos. ^[15]Outra maneira de modelar tal situação é a noção de sistema dinâmico híbrido.

Ver também

Referências

↑ Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
↑ Predefinição:MathWorld
↑ Norman L. Biggs, Discrete mathematics, Oxford University Press, 2002.
↑ Brian Hopkins, Resources for Teaching Discrete Mathematics, Mathematical Association of America, 2008.
↑ ^5,0 ^5,1 Wilson, Robin (2002). Four Colors Suffice. London: Penguin Books. ISBN 978-0-691-11533-7
↑ Trevor R. Hodkinson; John A. N. Parnell (2007). Reconstruction the Tree of Life: Taxonomy And Systematics of Large And Species Rich Taxa. [S.l.]: CRC PressINC. p. 97. ISBN 978-0-8493-9579-6
↑ «Millennium Prize Problems». 24 de maio de 2000. Consultado em 12 de janeiro de 2008
↑ A. S. Troelstra; H. Schwichtenberg (27 de julho de 2000). Basic Proof Theory. [S.l.]: Cambridge University Press. p. 186. ISBN 978-0-521-77911-1
↑ Samuel R. Buss (1998). Handbook of Proof Theory. [S.l.]: Elsevier. p. 13. ISBN 978-0-444-89840-1
↑ Franz Baader; Gerhard Brewka, Thomas Eiter (16 de outubro de 2001). KI 2001: Advances in Artificial Intelligence: Joint German/Austrian Conference on AI, Vienna, Austria, September 19-21, 2001. Proceedings. [S.l.]: Springer. p. 325. ISBN 978-3-540-42612-7
↑ Brotherston, J.; Bornat, R.; Calcagno, C. (2008). «Cyclic proofs of program termination in separation logic». ACM SIGPLAN Notices. 43 (1). Predefinição:Citeseerx
↑ Graphs on Surfaces, Bojan Mohar and Carsten Thomassen, Johns Hopkins University press, 2001
↑ HILGER, Stefan, "Analysis on measure chains - a unified approach to continuous and discrete calculus", Results in Mathematics, 18, n° 1-2 (1990), 18-56.
↑ CRUZ, Artur M. C. Brito da; RODRIGUES, Helena Sofia ; TORRES, Delfim F. M. Escalas Temporais e Mathematica
↑ SANTOS, I.L.D.; SILVA, G.N. e BARBANTI, L. Inclusões dinâmicas em escalas temporais: existência de soluções sob a hipótese de semicontinuidade inferior. TEMA - Tend. Mat. Apl. Comput.. São Carlos, 2012, vol.13, n.2, pp. 109-120. ISSN 2179-8451.

Bibliografia

Predefinição:Refbegin

Donald E. Knuth, The Art of Computer Programming
Judith L. Gersting Fundamentos Matemáticos para a Ciência da Computação, 5a Edição, LTC Editora (2004)
Paulo Blauth Matemática Discreta para Computação e Informática Sagra-Luzzato (2004)
R.L. Graham, D. E. Knuth e O. Patashnik, Matemática Concreta – Fundamentos para a Ciência da Computação. LTC (1995)
Kenneth H. Rosen, Discrete Mathematics and Its Applications, ISBN 0-07-119881-4 (International Edition)
Richard Johnsonbaugh, Discrete Mathematics 5th ed. Macmillan, New Jersey
Introdução à Análise Combinatória, 3a Edição, Editora Unicamp
Jaime Evaristo, Introdução à Álgebra Abstrata, Segunda Edição, Versão 02.2012, Formato Digital, disponível em [1]

Predefinição:Refend

Leitura complementar