Matemática discreta - Discrete mathematics
A matemática discreta é o estudo de estruturas matemáticas que são fundamentalmente discretas em vez de contínuas . Em contraste com os números reais que têm a propriedade de variar "suavemente", os objetos estudados em matemática discreta - como inteiros , gráficos e declarações em lógica - não variam suavemente dessa maneira, mas têm valores distintos e separados. A matemática discreta, portanto, exclui tópicos em "matemática contínua", como cálculo ou geometria euclidiana . Objetos discretos geralmente podem ser enumerados por inteiros. Mais formalmente, a matemática discreta foi caracterizada como o ramo da matemática que lida com conjuntos contáveis (conjuntos finitos ou conjuntos com a mesma cardinalidade dos números naturais). No entanto, não existe uma definição exata do termo "matemática discreta". Na verdade, a matemática discreta é descrita menos pelo que está incluído do que pelo que é excluído: quantidades continuamente variáveis e noções relacionadas.
O conjunto de objetos estudados em matemática discreta pode ser finito ou infinito. O termo matemática finita é algumas vezes aplicado a partes do campo da matemática discreta que lida com conjuntos finitos, particularmente aquelas áreas relevantes para os negócios.
A pesquisa em matemática discreta aumentou na segunda metade do século XX, em parte devido ao desenvolvimento de computadores digitais que operam em etapas discretas e armazenam dados em bits discretos. Conceitos e notações da matemática discreta são úteis no estudo e descrição de objetos e problemas nos ramos da ciência da computação , como algoritmos de computador , linguagens de programação , criptografia , prova automatizada de teoremas e desenvolvimento de software . Por outro lado, as implementações de computador são significativas na aplicação de idéias de matemática discreta a problemas do mundo real, como em pesquisa operacional .
Embora os principais objetos de estudo em matemática discreta sejam objetos discretos, métodos analíticos de matemática contínua também são frequentemente empregados.
Nos currículos universitários, a "Matemática Discreta" apareceu na década de 1980, inicialmente como um curso de apoio à ciência da computação; seu conteúdo era um tanto aleatório na época. Posteriormente, o currículo desenvolveu-se em conjunto com os esforços da ACM e do MAA em um curso que se destina basicamente a desenvolver a maturidade matemática dos alunos do primeiro ano; portanto, hoje em dia é um pré-requisito para graduações em matemática também em algumas universidades. Alguns livros didáticos de matemática discretos no nível do ensino médio também apareceram. Nesse nível, a matemática discreta às vezes é vista como um curso preparatório, não muito diferente do pré-cálculo nesse aspecto.
O Prêmio Fulkerson é concedido para trabalhos de destaque em matemática discreta.
Grandes desafios, passados e presentes
A história da matemática discreta envolveu uma série de problemas desafiadores que chamaram a atenção em áreas do campo. Na teoria dos grafos, muitas pesquisas foram motivadas por tentativas de provar o teorema das quatro cores , declarado pela primeira vez em 1852, mas não provado até 1976 (por Kenneth Appel e Wolfgang Haken, usando substancial assistência do computador).
Na lógica , o segundo problema na lista de problemas abertos de David Hilbert apresentada 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 isso não era possível - pelo menos não dentro da própria aritmética. O décimo problema de Hilbert era determinar se uma dada equação diofantina polinomial com coeficientes inteiros tem uma solução inteira. Em 1970, Yuri Matiyasevich provou que isso não poderia ser feito .
A necessidade de quebrar os códigos alemães na Segunda Guerra Mundial levou a avanços na criptografia e na ciência da computação teórica , com o primeiro computador eletrônico digital programável sendo desenvolvido no Bletchley Park da Inglaterra com a orientação de Alan Turing e seu trabalho seminal, On Computable Numbers. Ao mesmo tempo, os requisitos militares motivaram avanços na pesquisa operacional . A Guerra Fria significou que a criptografia permaneceu importante, com avanços fundamentais, como a criptografia de chave pública, sendo desenvolvida nas décadas seguintes. A pesquisa operacional continuou a ser importante como uma ferramenta no gerenciamento de negócios e projetos, com o método do caminho crítico sendo desenvolvido na década de 1950. A indústria de telecomunicações também motivou avanços na matemática discreta, particularmente na teoria dos grafos e na teoria da informação . A verificação formal de declarações em lógica foi necessária para o desenvolvimento de software de sistemas críticos de segurança , e os avanços na prova automatizada de teoremas foram impulsionados por essa necessidade.
A geometria computacional tem sido uma parte importante da computação gráfica incorporada em videogames modernos e ferramentas de design auxiliado por computador .
Vários campos da matemática discreta, particularmente ciência da computação teórica, teoria dos gráficos e combinatória , são importantes para abordar os desafiadores problemas de bioinformática associados com a compreensão da árvore da vida .
Atualmente, um dos problemas abertos mais famosos da 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 Clay Mathematics Institute ofereceu um prêmio de US $ 1 milhão para a primeira prova correta, junto com prêmios para seis outros problemas matemáticos .
Tópicos em matemática discreta
Ciência da computação teórica
A ciência da computação teórica inclui áreas da matemática discreta relevantes para a computação. Baseia-se fortemente na teoria dos grafos e na lógica matemática . Incluído na ciência da computação teórica está o estudo de algoritmos e estruturas de dados. A computabilidade estuda o que pode ser calculado em princípio e tem laços estreitos com a lógica, enquanto a complexidade estuda o tempo, o espaço e outros recursos obtidos por cálculos. A teoria dos autômatos e a teoria da linguagem formal estão intimamente relacionadas à computabilidade. Redes de Petri e álgebras de processo são usadas para modelar sistemas de computador, e métodos de matemática discreta são usados na análise de circuitos eletrônicos VLSI . A geometria computacional aplica algoritmos a problemas geométricos, enquanto a análise de imagem por computador os aplica a representações de imagens. A ciência da computação teórica também inclui o estudo de vários tópicos computacionais contínuos.
Teoria da informação
A teoria da informação envolve a quantificação da informação . Intimamente relacionada está a teoria da codificação, que é usada para projetar métodos de transmissão e armazenamento de dados eficientes e confiáveis. A teoria da informação também inclui temas contínuos tais como: sinais analógicos , analógico de codificação , encriptação analógica .
Lógica
A lógica é o estudo dos princípios de raciocínio e inferência válidos , bem como de consistência , solidez e integridade . Por exemplo, na maioria dos sistemas de lógica (mas não na lógica intuicionista ) a lei de Peirce ((( P → Q ) → P ) → P ) é um teorema. Para a lógica clássica, pode ser facilmente verificado com uma tabela verdade . O estudo da prova matemática é particularmente importante em lógica, e tem aplicações para prova automatizada de teoremas e verificação formal de software.
As fórmulas lógicas são estruturas discretas, assim como as provas , que formam árvores finitas ou, mais geralmente, estruturas de grafos acíclicos direcionados (com cada etapa de inferência combinando um ou mais ramos da premissa para dar uma única conclusão). Os valores verdade das fórmulas lógicas geralmente formam um conjunto finito, geralmente restrito a dois valores: verdadeiro e falso , mas a lógica também pode ser de valor contínuo, por exemplo, lógica difusa . Conceitos como árvores de prova infinita ou árvores de derivação infinita também foram estudados, por exemplo, lógica infinitária .
Teoria de conjuntos
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 é geralmente marcado pelo trabalho de Georg Cantor , distinguindo entre diferentes tipos de conjuntos infinitos , motivado pelo estudo de séries trigonométricas, e o desenvolvimento posterior da teoria dos conjuntos infinitos está fora do escopo do conjunto discreto matemática. Na verdade, o trabalho contemporâneo na teoria descritiva dos conjuntos faz uso extensivo da matemática contínua tradicional.
Combinatoria
A combinatória estuda a maneira como estruturas discretas podem ser combinadas ou organizadas. A combinatória enumerativa concentra-se na contagem do número de certos objetos combinatórios - por exemplo, a maneira de doze partes fornece uma estrutura unificada para a contagem de permutações , combinações e partições . A 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 combinatória enumerativa, que usa fórmulas combinatórias explícitas e funções geradoras para descrever os resultados, a combinatória analítica visa obter fórmulas assintóticas . A teoria do projeto é um estudo de projetos combinatórios , que são coleções de subconjuntos com certas propriedades de interseção . A teoria da partição estuda vários problemas de enumeração e assintóticos relacionados a partições inteiras e está intimamente relacionada a séries q , funções especiais e polinômios ortogonais . Originalmente uma parte da teoria e análise dos números , a teoria da partição agora é considerada uma parte da combinatória ou um campo independente. A teoria da ordem é o estudo de conjuntos parcialmente ordenados , tanto finitos quanto infinitos.
Teoria dos grafos
A teoria dos grafos , o estudo de grafos e redes , é freqüentemente considerada parte da combinatória, mas se tornou grande e distinta o suficiente, com seus próprios tipos de problemas, para ser considerada um assunto por si só. Os gráficos são um dos principais objetos de estudo em matemática discreta. Eles estão entre os modelos mais onipresentes de estruturas naturais e feitas pelo homem. Eles podem modelar muitos tipos de relações e dinâmicas de processo em sistemas físicos, biológicos e sociais. Em ciência da computação, eles podem representar redes de comunicação, organização de dados, dispositivos computacionais, o fluxo de computação, etc. Em matemática, eles são úteis em geometria e certas partes da topologia , por exemplo, teoria dos nós . A teoria algébrica dos grafos tem ligações estreitas com a teoria dos grupos. Existem também gráficos contínuos ; no entanto, na maior parte, a pesquisa em teoria dos grafos cai no domínio da matemática discreta.
Probabilidade
A teoria da probabilidade discreta lida com eventos que ocorrem em espaços de amostra contáveis . Por exemplo, as observações de contagem, como o número de pássaros em bandos, compreendem apenas valores de números naturais {0, 1, 2, ...}. Por outro lado, observações contínuas, como os pesos dos pássaros, compreendem valores numéricos reais e normalmente seriam modeladas por uma distribuição de probabilidade contínua, como a normal . As distribuições de probabilidade discretas podem ser usadas para aproximar as contínuas e vice-versa. Para situações altamente restritas, como jogar dados ou experimentos com baralhos de cartas , o cálculo da probabilidade de eventos é basicamente uma combinação enumerativa .
Teoria dos Números
A teoria dos números preocupa-se com as propriedades dos números em geral, particularmente os inteiros . Tem aplicações em criptografia e criptanálise , particularmente no que diz respeito à aritmética modular , equações diofantinas , congruências lineares e quadráticas, números primos e testes de primalidade . Outros aspectos discretos da teoria dos números incluem a geometria dos números . Na teoria analítica dos números , técnicas de matemática contínua também são usadas. Tópicos que vão além de objetos discretos incluem números transcendentais , aproximação diofantina , análise p-ádica e campos de função .
Estruturas algébricas
As estruturas algébricas ocorrem tanto como exemplos discretos quanto como exemplos contínuos. Álgebras discretas incluem: álgebra booleana usada em portas lógicas e programação; álgebra relacional usada em bancos de dados ; versões discretas e finitas de grupos , anéis e campos são importantes na teoria da codificação algébrica ; semigrupos discretos e monóides aparecem na teoria das linguagens formais .
Cálculo de diferenças finitas, cálculo discreto ou análise discreta
Uma função definida em um intervalo de inteiros é geralmente chamada de sequência . Uma sequência pode ser uma sequência finita de uma fonte de dados ou uma sequência infinita de um sistema dinâmico discreto . Tal função discreta poderia ser definida explicitamente por uma lista (se seu domínio for finito), ou por uma fórmula para seu termo geral, ou poderia ser dada implicitamente por uma relação de recorrência ou equação de diferença . As equações de diferença são semelhantes às equações diferenciais , mas substituem a diferenciação tomando a diferença entre termos adjacentes; eles podem ser usados para aproximar equações diferenciais ou (mais frequentemente) estudados por si próprios. Muitas questões e métodos relativos às equações diferenciais têm contrapartes para as equações às diferenças. Por exemplo, onde há transformadas integrais em análise harmônica para estudar funções contínuas ou sinais analógicos, há transformadas discretas para funções discretas ou sinais digitais. Assim como a métrica discreta, existem espaços métricos discretos ou finitos mais gerais e espaços topológicos finitos .
Geometria
A geometria discreta e a geometria combinatória tratam de propriedades combinatórias de coleções discretas de objetos geométricos. Um tópico de longa data na geometria discreta é o ladrilho do plano . A geometria computacional aplica algoritmos a problemas geométricos.
Topologia
Embora a topologia seja o campo da matemática que formaliza e generaliza a noção intuitiva de "deformação contínua" de objetos, ela dá origem a muitos tópicos discretos; isso pode ser atribuído em parte ao foco em invariantes topológicos , que normalmente assumem valores discretos. Veja topologia combinatória , teoria dos grafos topológicos , combinatória topológica , topologia computacional , espaço topológico discreto , espaço topológico finito , topologia (química) .
Pesquisa operacional
A pesquisa operacional fornece técnicas para resolver problemas práticos em engenharia, negócios e outros campos - problemas como a alocação de recursos para maximizar o lucro e a programação de atividades do projeto para minimizar o risco. As técnicas de pesquisa operacional incluem programação linear e outras áreas de otimização , teoria de filas , teoria de escalonamento e teoria de rede . A pesquisa operacional também inclui tópicos contínuos, como processo de Markov em tempo contínuo , martingales em tempo contínuo , otimização de processos e teoria de controle híbrido e contínuo .
Teoria dos jogos, teoria da decisão, teoria da utilidade, teoria da escolha social
| Colaborar | Defeito | |
| Colaborar | -1, -1 | -10, 0 |
| Defeito | 0, −10 | −5, −5 |
| Matriz de recompensa para o dilema do prisioneiro , um exemplo comum na teoria dos jogos . Um jogador escolhe uma linha, o outro uma coluna; o par resultante dá seus ganhos | ||
A teoria da decisão está preocupada em identificar os valores, incertezas e outras questões relevantes em uma determinada decisão, sua racionalidade e a decisão ótima resultante.
A teoria da utilidade trata das medidas da satisfação econômica relativa ou da conveniência do consumo de vários bens e serviços.
A teoria da escolha social trata do voto . Uma abordagem de votação mais baseada em quebra-cabeças é a teoria do voto .
A teoria dos jogos lida com situações em que o sucesso depende das escolhas dos outros, o que torna mais complexa a escolha do melhor curso de ação. Existem até jogos contínuos, veja jogo diferencial . Os tópicos incluem teoria do leilão e divisão justa .
Discretização
A discretização diz respeito ao processo de transferência de modelos e equações contínuas em contrapartes discretas, muitas vezes com o propósito de tornar os cálculos mais fáceis usando aproximações. A análise numérica fornece um exemplo importante.
Análogos discretos da matemática contínua
Existem muitos conceitos em matemática contínuas que têm versões discretas, tais como cálculo discreta , distribuições de probabilidade discretas , transformadas de Fourier discretos , geometria discreta , logaritmos discretos , geometria diferencial discreta , cálculo exterior discreta , teoria de Morse discreta , equações diferenciais , sistemas dinâmicos discretos , e medidas vetoriais discretas .
Na matemática aplicada , a modelagem discreta é o análogo discreto da modelagem contínua . Na modelagem discreta, as fórmulas discretas são adequadas aos dados . Um método comum nesta forma de modelagem é usar a relação de recorrência .
Na geometria algébrica , o conceito de uma curva pode ser estendido para geometrias discretas, tomando os espectros de anéis polinomiais sobre campos finitos para serem modelos dos espaços afins sobre esse campo, e permitindo que subvariedades ou espectros de outros anéis forneçam as curvas que se encontram em esse espaço. Embora o espaço no qual as curvas aparecem tenha um número finito de pontos, as curvas não são tanto conjuntos de pontos quanto análogos de curvas em configurações contínuas. Por exemplo, cada ponto do formulário para um campo pode ser estudado como um ponto ou como o espectro do anel local em (xc) , um ponto junto com uma vizinhança ao seu redor. Variedades algébricas também têm uma noção bem definida de espaço tangente, chamada de espaço tangente de Zariski , tornando muitos recursos de cálculo aplicáveis mesmo em configurações finitas.
![V (xc) \ subset \ operatorname {Spec} K [x] = \ mathbb {A} ^ {1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/147df15a1780a002602cd26438adbec315699e2b)
![\ operatorname {Spec} K [x] / (xc) \ cong \ operatorname {Spec} K](https://wikimedia.org/api/rest_v1/media/math/render/svg/80cc3220b7c86e6d0862f1bcf3fbac3ffc0191a7)
![\ operatorname {Spec} K [x] _ {(xc)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76e6e66e203e1805ec5b90fa25d9f0c817f28dd7)
Matemática híbrida discreta e contínua
O cálculo da escala de tempo é uma unificação da teoria das equações diferenciais com a das equações diferenciais , que tem aplicações em campos que requerem modelagem simultânea de dados discretos e contínuos. Outra forma de modelar tal situação é a noção de sistemas dinâmicos híbridos .
Veja também
- Esboço da matemática discreta
- Cyberchase , um programa que ensina Matemática Discreta para crianças
Referências
Leitura adicional
- Norman L. Biggs (19/12/2002). Discrete Mathematics . Imprensa da Universidade de Oxford. ISBN 978-0-19-850717-8.
- John Dwyer (2010). Uma introdução à matemática discreta para negócios e computação . ISBN 978-1-907934-00-1.
- Susanna S. Epp (04/08/2010). Matemática Discreta com Aplicações . Thomson Brooks / Cole. ISBN 978-0-495-39132-6.
- Ronald Graham , Donald E. Knuth , Oren Patashnik , Concrete Mathematics .
- Ralph P. Grimaldi (2004). Matemática Discreta e Combinatória: Uma Introdução Aplicada . Addison Wesley. ISBN 978-0-201-72634-3.
- Donald E. Knuth (03/03/2011). The Art of Computer Programming , Volumes 1-4a Boxed Set . Addison-Wesley Professional. ISBN 978-0-321-75104-1.
- Jiří Matoušek; Jaroslav Nešetřil (1998). Discrete Mathematics . Imprensa da Universidade de Oxford. ISBN 978-0-19-850208-1.
- Obrenic, Bojana (29/01/2003). Problemas de prática em matemática discreta . Prentice Hall. ISBN 978-0-13-045803-2.
- Kenneth H. Rosen; John G. Michaels (2000). Hand Book of Discrete and Combinatorial Mathematics . CRC PressI Llc. ISBN 978-0-8493-0149-0.
- Kenneth H. Rosen (2007). Matemática discreta: e suas aplicações . McGraw-Hill College. ISBN 978-0-07-288008-3.
- Andrew Simpson (2002). Matemática Discreta por Exemplo . McGraw-Hill Incorporated. ISBN 978-0-07-709840-7.
links externos
-
Mídia relacionada à matemática discreta no Wikimedia Commons - Matemática discreta nos Arquivos de Matemática utk.edu, fornecendo links para programas, tutoriais, programas, etc.
- Iowa Central: Electrical Technologies Program Matemática discreta para engenharia elétrica .
