Matemática discreta Wikipédia, a enciclopédia livre

Prévia do material em texto

15/03/2021 Matemática discreta – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Matemática_discreta 1/9
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
Origem: Wikipédia, a enciclopédia livre.
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:
https://pt.wikipedia.org/wiki/Wikip%C3%A9dia:P%C3%A1gina_principal
https://pt.wikipedia.org/wiki/Ficheiro:6n-graf.svg
https://pt.wikipedia.org/wiki/Grafo
https://pt.wikipedia.org/w/index.php?title=Propriedades_dos_grafos&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Algoritmo
https://pt.wikipedia.org/wiki/Estruturas_alg%C3%A9bricas
https://pt.wikipedia.org/wiki/Espa%C3%A7o_discreto
https://pt.wikipedia.org/wiki/Topologia_grosseira
https://pt.wikipedia.org/wiki/Fun%C3%A7%C3%A3o_(matem%C3%A1tica)
https://pt.wikipedia.org/wiki/Continuidade_matem%C3%A1tica
https://pt.wikipedia.org/wiki/N%C3%BAmero_real
https://pt.wikipedia.org/wiki/N%C3%BAmero_inteiro
https://pt.wikipedia.org/wiki/Grafo
https://pt.wikipedia.org/wiki/L%C3%B3gica
https://pt.wikipedia.org/wiki/C%C3%A1lculo
https://pt.wikipedia.org/wiki/An%C3%A1lise_matem%C3%A1tica
https://pt.wikipedia.org/wiki/Enumera%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Conjunto_cont%C3%A1vel
https://pt.wikipedia.org/wiki/Computador_digital
https://pt.wikipedia.org/wiki/Ci%C3%AAncia_da_computa%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Linguagem_de_programa%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Criptografia
https://pt.wikipedia.org/wiki/Prova_autom%C3%A1tica_de_teoremas
https://pt.wikipedia.org/wiki/Desenvolvimento_de_software
https://pt.wikipedia.org/wiki/Investiga%C3%A7%C3%A3o_operacional
https://pt.wikipedia.org/wiki/Ci%C3%AAncia_da_computa%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Algoritmo
https://pt.wikipedia.org/wiki/Linguagem_de_programa%C3%A7%C3%A3o
15/03/2021 Matemática discreta – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Matemática_discreta 2/9
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
Grandes desafios, passado e presente
Tópicos em matemática discreta
Lógica, lógica matemática (provas, indução matemática)
Teoria dos conjuntos, relações em conjuntos, funções e grupos
Probabilidade, teoria das probabilidades e cadeias de Markov
Teoria dos números
Combinatória
Teoria dos grafos
Teoria da computação, algoritmos e recursividade
Teoria da informação
Álgebra
Cálculo de diferenças finitas, cálculo discreto ou análise discreta
Geometria
Topologia
Investigação ou pesquisa operacional
Teoria dos jogos, teoria da decisão, teoria da utilidade, teoria da escolha social
Discretização
Analogia discreta de matemática contínua
Matemática híbrida - discreta e contínua
Ver também
Referências
Bibliografia
Leitura complementar
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 problemas abertos de David Hilbert, apresentados em
1900 era provar que os axiomas da aritmética são consistentes O segundo teorema da incompletude
Índice
Grandes desafios, passado e presente
https://pt.wikipedia.org/wiki/Teoria_dos_jogos
https://pt.wikipedia.org/wiki/Teoria_das_filas
https://pt.wikipedia.org/wiki/Teoria_dos_grafos
https://pt.wikipedia.org/w/index.php?title=Geometria_combinat%C3%B3ria&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Topologia_combinat%C3%B3ria&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Programa%C3%A7%C3%A3o_linear
https://pt.wikipedia.org/wiki/Criptografia
https://pt.wikipedia.org/wiki/Criptologia
https://pt.wikipedia.org/wiki/Criptoan%C3%A1lise
https://pt.wikipedia.org/wiki/Teoria_da_computa%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Teorema_das_quatro_cores
https://pt.wikipedia.org/wiki/Matem%C3%A1tica_l%C3%B3gica
https://pt.wikipedia.org/wiki/Segundo_problema_de_Hilbert
https://pt.wikipedia.org/wiki/Problemas_de_Hilbert
https://pt.wikipedia.org/wiki/David_Hilbert
https://pt.wikipedia.org/wiki/Axioma
https://pt.wikipedia.org/wiki/Aritm%C3%A9tica
https://pt.wikipedia.org/wiki/Consist%C3%AAncia
https://pt.wikipedia.org/w/index.php?title=Segundo_teorema_da_incompletude_de_G%C3%B6del&action=edit&redlink=1
15/03/2021 Matemática discreta – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Matemática_discreta 3/9
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 finalmenteprovaram
isso em 1976.[5]
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]
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.
Tópicos em matemática discreta
Lógica, lógica matemática (provas, indução matemática)
https://pt.wikipedia.org/wiki/Ficheiro:Four_Colour_Map_Example.svg
https://pt.wikipedia.org/wiki/Teoria_dos_grafos
https://pt.wikipedia.org/wiki/Colora%C3%A7%C3%A3o_de_grafos
https://pt.wikipedia.org/wiki/Teorema_das_quatro_cores
https://pt.wikipedia.org/wiki/Axioma
https://pt.wikipedia.org/wiki/Aritm%C3%A9tica
https://pt.wikipedia.org/wiki/Consist%C3%AAncia
https://pt.wikipedia.org/w/index.php?title=Segundo_teorema_da_incompletude_de_G%C3%B6del&action=edit&redlink=1
https://pt.wikipedia.org/wiki/D%C3%A9cimo_problema_de_Hilbert
https://pt.wikipedia.org/wiki/Equa%C3%A7%C3%A3o_diofantina
https://pt.wikipedia.org/wiki/Yuri_Matiyasevich
https://pt.wikipedia.org/wiki/Teorema_de_Matiyasevich
https://pt.wikipedia.org/w/index.php?title=Criptoan%C3%A1%C4%BAise&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial
https://pt.wikipedia.org/wiki/Criptografia
https://pt.wikipedia.org/wiki/Ci%C3%AAncia_da_computa%C3%A7%C3%A3o_te%C3%B3rica
https://pt.wikipedia.org/wiki/Colossus
https://pt.wikipedia.org/w/index.php?title=Parque_Bletchley&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Pesquisa_operacional
https://pt.wikipedia.org/wiki/Guerra_Fria
https://pt.wikipedia.org/wiki/Chave_p%C3%BAblica
https://pt.wikipedia.org/wiki/M%C3%A9todo_do_caminho_cr%C3%ADtico
https://pt.wikipedia.org/w/index.php?title=Ind%C3%BAstria_de_telecomunica%C3%A7%C3%B5es&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Teoria_da_informa%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Verifica%C3%A7%C3%A3o_formal
https://pt.wikipedia.org/wiki/Desenvolvimento_de_software
https://pt.wikipedia.org/w/index.php?title=Sistemas_de_seguran%C3%A7a_cr%C3%ADtica&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Prova_autom%C3%A1tica_de_teoremas
https://pt.wikipedia.org/wiki/Geometria_computacional
https://pt.wikipedia.org/wiki/Computa%C3%A7%C3%A3o_gr%C3%A1fica
https://pt.wikipedia.org/wiki/CAD
https://pt.wikipedia.org/wiki/Combinat%C3%B3ria
https://pt.wikipedia.org/wiki/Bioinform%C3%A1tica
https://pt.wikipedia.org/w/index.php?title=%C3%81rvore_filogeneal%C3%B3gica&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Problema_P_%3D_NP&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Classe_de_complexidade
https://pt.wikipedia.org/w/index.php?title=Complexidade_P&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Complexidade_NP&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Instituto_de_Matem%C3%A1tica_Clay
https://pt.wikipedia.org/wiki/US$
https://pt.wikipedia.org/wiki/Pr%C3%AAmio_dos_Problemas_do_Mil%C3%AAnio
https://pt.wikipedia.org/wiki/Infer%C3%AAncia
https://pt.wikipedia.org/wiki/L%C3%B3gica_intuicionista
https://pt.wikipedia.org/wiki/Lei_de_Peirce
https://pt.wikipedia.org/wiki/L%C3%B3gica_cl%C3%A1ssica
https://pt.wikipedia.org/wiki/Tabela_da_verdade
https://pt.wikipedia.org/wiki/Prova_matem%C3%A1tica
https://pt.wikipedia.org/wiki/Prova_autom%C3%A1tica_de_teoremas
https://pt.wikipedia.org/wiki/Verifica%C3%A7%C3%A3o_formal
https://pt.wikipedia.org/wiki/F%C3%B3rmula_bem_formada
https://pt.wikipedia.org/wiki/Teoria_da_prova
https://pt.wikipedia.org/wiki/Estrutura_de_%C3%A1rvore
https://pt.wikipedia.org/wiki/Regra_de_infer%C3%AAncia
https://pt.wikipedia.org/wiki/Premissa
https://pt.wikipedia.org/w/index.php?title=Valor_verdade&action=edit&redlink=1
https://pt.wikipedia.org/wiki/L%C3%B3gica_fuzzy
https://pt.wikipedia.org/wiki/L%C3%B3gica_infinit%C3%A1ria
15/03/2021 Matemática discreta – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Matemática_discreta 4/9
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 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.
A Teoria de probabilidade discreta lida com eventos que ocorrem em espaços amostrais
contáveis. Por exemplo, as observaçõesde 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.
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.
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.
Teoria dos conjuntos, relações em conjuntos, funções e grupos
Probabilidade, teoria das probabilidades e cadeias de Markov
Teoria dos números
Combinatória
https://pt.wikipedia.org/wiki/Ficheiro:Ulam_1.png
https://pt.wikipedia.org/wiki/Espiral_de_Ulam
https://pt.wikipedia.org/wiki/N%C3%BAmero_primo
https://pt.wikipedia.org/wiki/N%C3%BAmero_primo#Distribui%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/N%C3%BAmero_primo
https://pt.wikipedia.org/w/index.php?title=Conjuntos_parcialmente_ordenados&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Rela%C3%A7%C3%A3o_(matem%C3%A1tica)
https://pt.wikipedia.org/wiki/Conjunto_cont%C3%A1vel
https://pt.wikipedia.org/wiki/Conjunto_infinito
https://pt.wikipedia.org/wiki/Georg_Cantor
https://pt.wikipedia.org/wiki/Conjunto_infinito
https://pt.wikipedia.org/w/index.php?title=Conjuntos_infinitos&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Teoria_descritiva_dos_conjuntos
https://pt.wikipedia.org/wiki/Distribui%C3%A7%C3%A3o_normal
https://pt.wikipedia.org/wiki/Dado
https://pt.wikipedia.org/w/index.php?title=Baralho_de_cartas&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Combinat%C3%B3ria_enumerativa
https://pt.wikipedia.org/wiki/Inteiro
https://pt.wikipedia.org/wiki/Criptografia
https://pt.wikipedia.org/wiki/Criptoan%C3%A1lise
https://pt.wikipedia.org/wiki/Criptologia
https://pt.wikipedia.org/wiki/Aritm%C3%A9tica_modular
https://pt.wikipedia.org/w/index.php?title=Equa%C3%A7%C3%B5es_diofantinas&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Testes_de_primalidade&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Geometria_dos_n%C3%BAmeros&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Teoria_anal%C3%ADtica_dos_n%C3%BAmeros
https://pt.wikipedia.org/wiki/N%C3%BAmero_transcendental
https://pt.wikipedia.org/wiki/Aproxima%C3%A7%C3%A3o_diofantina
https://pt.wikipedia.org/w/index.php?title=An%C3%A1lise_p-adic&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Corpo_de_fun%C3%A7%C3%B5es_de_uma_variedade_alg%C3%A9brica
https://pt.wikipedia.org/wiki/Combinat%C3%B3ria_enumerativa
https://pt.wikipedia.org/w/index.php?title=Caminho_de_Doze&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Permuta%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Combina%C3%A7%C3%A3o
https://pt.wikipedia.org/w/index.php?title=Parti%C3%A7%C3%A3o_de_conjunto&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Combinat%C3%B3ria_anal%C3%ADtica&action=edit&redlink=1
https://pt.wikipedia.org/wiki/An%C3%A1lise_complexa
https://pt.wikipedia.org/wiki/Teoria_da_probabilidade
https://pt.wikipedia.org/w/index.php?title=An%C3%A1lise_combinat%C3%B3ria_anal%C3%ADtica&action=edit&redlink=1
https://pt.wikipedia.org/wiki/An%C3%A1lise_assint%C3%B3tica
https://pt.wikipedia.org/w/index.php?title=Modelo_combinat%C3%B3rio&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Conjunto_de_interse%C3%A7%C3%A3o&action=edit&redlink=1
15/03/2021 Matemática discreta – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Matemática_discreta 5/9
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 'A4.
Complexidade estuda o tempo
tomado por algoritmos, como esta
rotina de ordenaçã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.
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.
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.
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 .
Teoria dos grafos
Teoria da computação, algoritmos e recursividade
Teoria da informação
https://pt.wikipedia.org/wiki/Ficheiro:TruncatedTetrahedron.gif
https://pt.wikipedia.org/wiki/Teoria_dos_grafos
https://pt.wikipedia.org/wiki/Teoria_dos_grupos
https://pt.wikipedia.org/wiki/Tetraedro_truncado
https://pt.wikipedia.org/w/index.php?title=Grupo_alternado&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Ficheiro:Sorting_quicksort_anim.gif
https://pt.wikipedia.org/wiki/Complexidade
https://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o
https://pt.wikipedia.org/w/index.php?title=Teoria_de_parti%C3%A7%C3%A3o&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Parti%C3%A7%C3%A3o_inteira&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=S%C3%A9rie-Q&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Fun%C3%A7%C3%A3o_especial
https://pt.wikipedia.org/w/index.php?title=Polin%C3%B4mio_ortogonal&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Teoria_dos_n%C3%BAmeros
https://pt.wikipedia.org/wiki/An%C3%A1lise
https://pt.wikipedia.org/wiki/Teoria_da_ordem
https://pt.wikipedia.org/wiki/Conjunto_parcialmente_ordenado
https://pt.wikipedia.org/wiki/Teoria_dos_grafos
https://pt.wikipedia.org/wiki/Grafo
https://pt.wikipedia.org/w/index.php?title=Teoria_da_redes&action=edit&redlink=1
https://pt.wikipedia.org/wiki/An%C3%A1lise_combinat%C3%B3ria
https://pt.wikipedia.org/wiki/Topologia_(matem%C3%A1tica)
https://pt.wikipedia.org/wiki/Teoria_dos_n%C3%B3s
https://pt.wikipedia.org/w/index.php?title=Teoria_dos_grafos_alg%C3%A9bricos&action=edit&redlink=1
15/03/2021 Matemática discreta – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Matemática_discreta 6/9
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.
Geometria
computacional
computador aplica
algoritmos para as
representações de
geométricos objetos.
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 .
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 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.
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).
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
Álgebra
Cálculo de diferenças finitas, cálculo discreto ou análise
discreta
Geometria
Topologia
Investigação ou pesquisa operacional
https://pt.wikipedia.org/wiki/Ficheiro:WikipediaBinary.svg
https://pt.wikipedia.org/wiki/Ficheiro:SimplexRangeSearching.png
15/03/2021 Matemática discreta – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Matemática_discreta 7/9
PERT gráficos como
este proporcionam uma
técnica de gestão de
negócios com base na
teoria dos grafos.
ç , , p g ç , p q p
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 .
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 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.
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 .
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.
Teoria dos jogos, teoria da decisão, teoria da utilidade,
teoria da escolha social
Discretização
Analogia discreta de matemática contínua
Matemática híbrida - discreta e contínua
Ver também
https://pt.wikipedia.org/wiki/Ficheiro:Pert_chart_colored.svg
https://pt.wikipedia.org/wiki/C%C3%A1lculo_diferencial
https://pt.wikipedia.org/wiki/Equa%C3%A7%C3%B5es_de_diferen%C3%A7as
https://pt.wikipedia.org/w/index.php?title=Sistema_din%C3%A2mico_h%C3%ADbrido&action=edit&redlink=115/03/2021 Matemática discreta – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Matemática_discreta 8/9
Função contínua
Topologia (matemática)
Análise matemática
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)
1. Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
2. Weisstein, Eric W. «Discrete mathematics» (http://mathworld.wolfram.com/DiscreteMathematics.h
tml) (em inglês). MathWorld
3. Norman L. Biggs, Discrete mathematics, Oxford University Press, 2002.
4. Brian Hopkins, Resources for Teaching Discrete Mathematics, Mathematical Association of
America, 2008.
5. Wilson, Robin (2002). Four Colors Suffice. London: Penguin Books. ISBN 978-0-691-11533-7
6. Trevor R. Hodkinson; John A. N. Parnell (2007). Reconstruction the Tree of Life: Taxonomy And
Systematics of Large And Species Rich Taxa (http://books.google.com/?id=7GKkbJ4yOKAC&pg=
PA97). [S.l.]: CRC PressINC. p. 97. ISBN 978-0-8493-9579-6
7. «Millennium Prize Problems» (http://www.claymath.org/millennium/). 24 de maio de 2000.
Consultado em 12 de janeiro de 2008
8. A. S. Troelstra; H. Schwichtenberg (27 de julho de 2000). Basic Proof Theory (http://books.googl
e.com/?id=x9x6F_4mUPgC&pg=PA186). [S.l.]: Cambridge University Press. p. 186. ISBN 978-0-
521-77911-1
9. Samuel R. Buss (1998). Handbook of Proof Theory (http://books.google.com/?id=MfTMDeCq7uk
C&pg=PA13). [S.l.]: Elsevier. p. 13. ISBN 978-0-444-89840-1
10. 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 (http://books.google.com/?id=27A2XJPYwIkC&pg=PA325). [S.l.]: Springer.
p. 325. ISBN 978-3-540-42612-7
11. Brotherston, J.; Bornat, R.; Calcagno, C. (2008). «Cyclic proofs of program termination in
separation logic». ACM SIGPLAN Notices. 43 (1). Predefinição:Citeseerx
12. Graphs on Surfaces (http://jhupbooks.press.jhu.edu/ecom/MasterServlet/GetItemDetailsHandler?i
N=9780801866890&qty=1&viewMode=1&loggedIN=false&JavaScript=y), Bojan Mohar and
Carsten Thomassen, Johns Hopkins University press, 2001
13. HILGER, Stefan, "Analysis on measure chains - a unified approach to continuous and discrete
calculus", Results in Mathematics, 18, n° 1-2 (1990), 18-56.
14. CRUZ, Artur M. C. Brito da; RODRIGUES, Helena Sofia ; TORRES, Delfim F. M. Escalas
Temporais e Mathematica (http://arxiv.org/pdf/0911.3187.pdf)
15. 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 (http://www.scielo.br/scielo.ph
p?pid=S2179-84512012000200002&script=sci_arttext). TEMA - Tend. Mat. Apl. Comput.. São
Carlos, 2012, vol.13, n.2, pp. 109-120. ISSN 2179-8451.
Referências
Bibliografia
https://pt.wikipedia.org/wiki/Fun%C3%A7%C3%A3o_cont%C3%ADnua
https://pt.wikipedia.org/wiki/Topologia_(matem%C3%A1tica)
https://pt.wikipedia.org/wiki/An%C3%A1lise_matem%C3%A1tica
https://pt.wikipedia.org/wiki/Donald_Knuth
https://pt.wikipedia.org/wiki/The_Art_of_Computer_Programming
https://pt.wikipedia.org/wiki/Ci%C3%AAncia_da_computa%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Donald_Knuth
https://pt.wikipedia.org/wiki/Ci%C3%AAncia_da_computa%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/0071198814
https://pt.wikipedia.org/wiki/Eric_W._Weisstein
http://mathworld.wolfram.com/DiscreteMathematics.html
https://pt.wikipedia.org/wiki/MathWorld
https://pt.wikipedia.org/w/index.php?title=Norman_L._Biggs&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Robin_Wilson_(mathematician)&action=edit&redlink=1
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-691-11533-7
http://books.google.com/?id=7GKkbJ4yOKAC&pg=PA97
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-8493-9579-6
http://www.claymath.org/millennium/
http://books.google.com/?id=x9x6F_4mUPgC&pg=PA186
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-521-77911-1
http://books.google.com/?id=MfTMDeCq7ukC&pg=PA13
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-444-89840-1
http://books.google.com/?id=27A2XJPYwIkC&pg=PA325
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-3-540-42612-7
https://pt.wikipedia.org/w/index.php?title=Predefini%C3%A7%C3%A3o:Citeseerx&action=edit&redlink=1
http://jhupbooks.press.jhu.edu/ecom/MasterServlet/GetItemDetailsHandler?iN=9780801866890&qty=1&viewMode=1&loggedIN=false&JavaScript=y
https://pt.wikipedia.org/w/index.php?title=Bojan_Mohar&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Carsten_Thomassen
http://arxiv.org/pdf/0911.3187.pdf
http://www.scielo.br/scielo.php?pid=S2179-84512012000200002&script=sci_arttext
15/03/2021 Matemática discreta – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Matemática_discreta 9/9
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] (http://www.ic.ufal.br/professor/jaime)
Norman L. Biggs (19 de dezembro de 2002). Discrete Mathematics. [S.l.]: Oxford University
Press. ISBN 978-0-19-850717-8
Ronald Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics
Donald E. Knuth (3 de março de 2011). The Art of Computer Programming, Volumes 1-4a Boxed
Set. [S.l.]: Addison-Wesley Professional. ISBN 978-0-321-75104-1
Kenneth H. Rosen; John G. Michaels (2000). Hand Book of Discrete and Combinatorial
Mathematics. [S.l.]: CRC PressI Llc. ISBN 978-0-8493-0149-0
Bojana Obrenic (29 de janeiro de 2003). Practice Problems in Discrete Mathematics. [S.l.]:
Prentice Hall. ISBN 978-0-13-045803-2
John Dwyer (2010). An Introduction to Discrete Mathematics for Business & Computing. [S.l.: s.n.]
ISBN 978-1-907934-00-1
Kenneth H. Rosen (2007). Discrete Mathematics: And Its Applications. [S.l.]: McGraw-Hill College.
ISBN 978-0-07-288008-3
Ralph P. Grimaldi (2004). Discrete and Combinatorial Mathematics: An Applied Introduction. [S.l.]:
Addison Wesley. ISBN 978-0-201-72634-3
Susanna S. Epp (4 de agosto de 2010). Discrete Mathematics With Applications. [S.l.]: Thomson
Brooks/Cole. ISBN 978-0-495-39132-6
Jiří Matoušek; Jaroslav Nešetřil (1998). Discrete Mathematics. [S.l.]: Oxford University Press.
ISBN 978-0-19-850208-1
Mathematics Archives (http://archives.math.utk.edu/topics/discreteMath.html), Discrete
Mathematics links to syllabi, tutorials, programs, etc.
Andrew Simpson (2002). Discrete Mathematics by Example. [S.l.]: McGraw-Hill Incorporated.
ISBN 978-0-07-709840-7
Obtida de "https://pt.wikipedia.org/w/index.php?title=Matemática_discreta&oldid=59631483"
Esta página foi editada pela última vez às 19h42min de 20 de outubro de 2020.
Este texto é disponibilizado nos termos da licença Atribuição-CompartilhaIgual 3.0 Não Adaptada (CC BY-SA 3.0) da
Creative Commons; pode estar sujeito a condições adicionais. Para mais detalhes, consulte as condições de utilização.
Leitura complementar
http://www.ic.ufal.br/professor/jaime
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-19-850717-8
https://pt.wikipedia.org/wiki/Ronald_Graham
https://pt.wikipedia.org/wiki/Donald_Knuthhttps://pt.wikipedia.org/wiki/Oren_Patashnik
https://pt.wikipedia.org/w/index.php?title=Concrete_Mathematics&action=edit&redlink=1
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-321-75104-1
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-8493-0149-0
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-13-045803-2
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-1-907934-00-1
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-07-288008-3
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-201-72634-3
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-495-39132-6
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-19-850208-1
http://archives.math.utk.edu/topics/discreteMath.html
https://pt.wikipedia.org/wiki/International_Standard_Book_Number
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/978-0-07-709840-7
https://pt.wikipedia.org/w/index.php?title=Matem%C3%A1tica_discreta&oldid=59631483
https://creativecommons.org/licenses/by-sa/3.0/deed.pt
https://foundation.wikimedia.org/wiki/Condi%C3%A7%C3%B5es_de_Uso