Matemática discreta

Gráficos como estes estão entre os objetos estudados por matemática discreta, por suas propriedades matemáticas interessantes, sua utilidade como modelos de problemas do mundo real, e sua importância no desenvolvimento de algoritmos de computador.

Matemática discreta é o estudo de estruturas matemáticas que podem ser consideradas "discretas" (de forma análoga às variáveis discretas, tendo uma bijeção com o conjunto dos números naturais) ao invés de "contínuas" (analogamente às funções contínuas). Objetos estudados em matemática discreta incluem números inteiros, gráficos e declarações em lógica. Em contraste, a matemática discreta exclui tópicos em "matemática contínua" como números reais, cálculo ou geometria euclidiana. Objetos discretos geralmente podem ser enumerados por números inteiros; mais formalmente, a matemática discreta tem sido 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 há uma definição exata do termo "matemática discreta".

O conjunto de objetos estudados na matemática discreta pode ser finito ou infinito. O termo matemática finita às 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 sistemas "discretos" etapas e armazenar dados em "discreta" bits. Conceitos e notações de matemática discreta são úteis para estudar e descrever objetos e problemas em 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 ideias de matemática discreta a problemas do mundo real.

Embora os principais objetos de estudo em matemática discreta sejam objetos discretos, os métodos analíticos de "contínuos" a matemática também é frequentemente empregada.

Nos currículos universitários, "Matemática Discreta" surgiu na década de 1980, inicialmente como curso de apoio à informática; seu conteúdo era um tanto aleatório na época. O currículo foi posteriormente desenvolvido em conjunto com os esforços da ACM e MAA em um curso que se destina basicamente a desenvolver a maturidade matemática em alunos do primeiro ano; portanto, hoje em dia é um pré-requisito para cursos de matemática em algumas universidades também. Alguns livros didáticos de matemática discreta 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 a esse respeito.

O Prêmio Fulkerson é concedido a trabalhos de destaque em matemática discreta.

Grandes desafios, passado e presente

Grande parte da pesquisa na teoria dos gráficos foi motivada por tentativas de provar que todos os mapas, como este, podem ser coloridos usando apenas quatro cores para que nenhuma área da mesma cor compartilhe uma borda. Kenneth Appel e Wolfgang Haken provaram isso em 1976.

A história da matemática discreta envolveu uma série de problemas desafiadores que chamaram a atenção dentro das áreas do campo. Na teoria dos grafos, muita pesquisa foi motivada 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 assistência substancial de computador).

Em lógica, o segundo problema na lista de problemas em aberto 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, na Inglaterra, sob a orientação de Alan Turing e seu trabalho seminal, Em Números Computáveis. 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 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 tem sido 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 aos videogames modernos e às ferramentas de design auxiliadas por computador.

Vários campos da matemática discreta, particularmente ciência da computação teórica, teoria dos grafos e combinatória, são importantes para abordar os desafiadores problemas de bioinformática associados ao entendimento da árvore da vida.

Atualmente, um dos problemas em aberto mais famosos na 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 outros seis problemas matemáticos.

Tópicos em matemática discreta

Ciência da computação teórica

A complexidade estuda o tempo tomado por algoritmos, como esta rotina de classificação.

A geometria computacional aplica algoritmos de computador a representações de objetos geométricos.

A ciência da computação teórica inclui áreas de 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 computado em princípio e tem laços estreitos com a lógica, enquanto a complexidade estuda o tempo, o espaço e outros recursos consumidos pelas computações. A teoria dos autômatos e a teoria da linguagem formal estão intimamente relacionadas com a 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 e representações de objetos 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

Os códigos ASCII para a palavra "Wikipedia", dada aqui em binário, fornecem uma maneira de representar a palavra em teoria da informação, bem como para algoritmos de processamento de 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 armazenamento e transmissão de dados eficientes e confiáveis. A teoria da informação também inclui tópicos contínuos como: sinais analógicos, codificação analógica, criptografia analógica.

Lógica

A lógica é o estudo dos princípios do raciocínio válido e da inferência, bem como da 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 lógica clássica, pode ser facilmente verificado com uma tabela de verdade. O estudo da prova matemática é particularmente importante na lógica e se acumulou na prova automatizada de teoremas e na 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 gráficas acíclicas direcionadas (com cada etapa de inferência combinando uma ou mais ramificações de premissa para fornecer uma única conclusão). Os valores de 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 fuzzy. Conceitos como árvores de prova infinita ou árvores de derivação infinita também foram estudados, por ex. lógica infinitária.

Teoria dos conjuntos

A teoria dos conjuntos é o ramo da matemática que estuda 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.

Em 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 de matemática discreta. De fato, o trabalho contemporâneo na teoria descritiva dos conjuntos faz uso extensivo da matemática contínua tradicional.

Combinatória

A combinatória estuda a maneira pela qual estruturas discretas podem ser combinadas ou arranjadas. A combinatória enumerativa concentra-se na contagem do número de certos objetos combinatórios - por exemplo, a forma doze 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, determinação do 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 combinatória topológica diz respeito ao uso de técnicas de topologia e topologia algébrica/topologia combinatória em combinatória. A teoria do design é um estudo de designs 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 gráficos

A teoria dos gráficos tem ligações próximas à teoria dos grupos. Este gráfico tetraedro truncado está relacionado com o grupo alternado A₄.

A teoria dos grafos, o estudo de grafos e redes, é muitas vezes considerada parte da combinatória, mas cresceu o suficiente e se tornou distinta o suficiente, com seu próprio tipo de problemas, para ser considerada um assunto por si só. Os gráficos são um dos principais objetos de estudo da 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 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 em geometria e certas partes da topologia, por exemplo, teoria do nó. A teoria dos grafos algébricos tem ligações estreitas com a teoria de grupos e a teoria dos grafos topológicos tem ligações estreitas com a topologia. Existem também grafos contínuos; no entanto, na maioria das vezes, a pesquisa em teoria dos grafos cai no domínio da matemática discreta.

Teoria dos números

A espiral Ulam de números, com pixels pretos mostrando números primos. Este diagrama indica padrões na distribuição de números primos.

A teoria dos números está preocupada com as propriedades dos números em geral, particularmente inteiros. Tem aplicações em criptografia e criptoaná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 transcendentes, 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. As á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 corpos são importantes na teoria da codificação algébrica; semigrupos e monóides discretos aparecem na teoria das linguagens formais.

Análogos discretos da matemática contínua

Existem muitos conceitos e teorias em matemática contínua que têm versões discretas, como cálculo discreto, transformadas discretas de Fourier, geometria discreta, logaritmos discretos, geometria diferencial discreta, cálculo externo discreto, teoria discreta de Morse, otimização discreta, teoria de probabilidade discreta, distribuição de probabilidade discreta, equações de diferença, sistemas dinâmicos discretos e medidas vetoriais discretas.

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

No cálculo discreto e no cálculo de diferenças finitas, uma função definida em um intervalo de números 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. Essa função discreta pode ser definida explicitamente por uma lista (se seu domínio for finito), ou por uma fórmula para seu termo geral, ou pode ser dada implicitamente por uma relação de recorrência ou equação de diferença. As equações de diferenças 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 conta própria. Muitas questões e métodos relativos a equações diferenciais têm contrapartes para equações de diferenças. Por exemplo, onde existem transformações integrais na análise harmônica para estudar funções contínuas ou sinais analógicos, existem transformações discretas para funções discretas ou sinais digitais. Além dos espaços métricos discretos, existem espaços topológicos discretos mais gerais, espaços métricos finitos, espaços topológicos finitos.

O cálculo da escala de tempo é uma unificação da teoria das equações de diferenças 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.

Geometria discreta

Geometria discreta e geometria combinatória são sobre propriedades combinatórias de coleções discretas de objetos geométricos. Um tópico de longa data em geometria discreta é o ladrilho do plano.

Na geometria algébrica, o conceito de uma curva pode ser estendido para geometrias discretas, tomando o espectro de anéis polinomiais sobre campos finitos para ser modelos dos espaços afinos sobre esse campo, e deixando subvariidades ou espectros de outros anéis fornecer as curvas que estão nesse espaço. Embora o espaço em que as curvas aparecem tenha um número finito de pontos, as curvas não são tanto conjuntos de pontos como análogos de curvas em configurações contínuas. Por exemplo, cada ponto da forma V(x- Sim. - Sim. c)? ? Especificações⁡ ⁡ KKNão.x]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =A1{displaystyle V(x-c)subset operatorname (Spec) K[x]=mathbb {A} ^{1}} para KKNão. um campo pode ser estudado tanto como Especificações⁡ ⁡ KKNão.x]/(x- Sim. - Sim. c)Gerenciamento Gerenciamento Especificações⁡ ⁡ KK{displaystyle operatorname {Spec} K[x]/(x-c)cong operatorname {Spec} K}, um ponto, ou como o espectro Especificações⁡ ⁡ KKNão.x](x- Sim. - Sim. c){displaystyle operatorname {Spec} K[x]_{(x-c)}} do anel local em (x-c), um ponto junto com um bairro ao seu redor. As variedades algébricas também têm uma noção bem definida de espaço tangente chamado espaço tangente de Zariski, fazendo muitas características de cálculo aplicáveis mesmo em configurações finitas.

Modelagem discreta

Na matemática aplicada, a modelagem discreta é o análogo discreto da modelagem contínua. Na modelagem discreta, as fórmulas discretas são ajustadas aos dados. Um método comum nesta forma de modelagem é usar a relação de recorrência. A discretização diz respeito ao processo de transferência de modelos e equações contínuas em contrapartes discretas, geralmente com o objetivo de facilitar os cálculos usando aproximações. A análise numérica fornece um exemplo importante.