Matemática discreta
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.
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). 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.
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.
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, ou, mais em geral, dirigido gráfico acíclicos estruturas (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, 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 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.
Teoria dos grafos
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. 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 teoria de grupos. 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.
