Procurando exemplos em que o conhecimento de matemática discreta é útil [fechado

Question

Inspirado depois de assistir a conversa do Scna de Michael Feather "Auto-educação e o artesão"Estou interessado em ouvir sobre exemplos práticos no desenvolvimento de software, onde a matemática discreta se mostrou útil.

Answer 1

A matemática discreta tocou todos os aspectos do desenvolvimento de software, pois o desenvolvimento de software é baseado na ciência da computação em sua essência.

http://en.wikipedia.org/wiki/discrete_math

Leia esse link. Você verá que existem inúmeras aplicações práticas, embora essa entrada da Wikipedia fale principalmente em termos teóricos.

Answer 2

Técnicas que aprendi no meu curso de matemática discreta com a universidade me ajudaram bastante com os Jogos Professores Layton.

Isso conta como útil ... certo?

Existem muitos exemplos da vida real em que os algoritmos de coloração do mapa são úteis, além de apenas para colorir mapas. A pergunta no meu exame final teve a ver com a programação do semáforo em um cruzamento de seis vias.

Answer 3

Como San Jacinto indica, os fundamentos da programação estão muito ligados em matemática discreta. Além disso, a 'matemática discreta' é um termo muito amplo. Essas coisas talvez tornem mais difíceis de escolher exemplos específicos. Eu posso criar um punhado, mas há muitos, muitos outros.

A implementação do compilador é uma boa fonte de exemplos: obviamente, há autômatos / teoria formal da linguagem; A alocação de registro pode ser expressa em termos de coloração gráfica; As análises clássicas de fluxo de dados usadas na otimização de compiladores podem ser expressos em termos de funções em estruturas algébricas semelhantes a treliça.

Um exemplo simples, o uso de gráficos direcionados está em um sistema de construção que leva as dependências envolvidas em tarefas individuais, executando um tipo topológico. Suspeito que, se você tentasse resolver esse problema sem ter o conceito de um gráfico direcionado, provavelmente acabaria tentando rastrear as dependências durante todo o caminho com o código complicado de manutenção de livros (e depois descobrir que seu manuseio de As dependências cíclicas eram menos que elegantes).

Claramente, a maioria dos programadores não escreve seus próprios compiladores de otimização ou sistemas de criação, por isso vou escolher um exemplo da minha própria experiência. Existe uma empresa que fornece dados rodoviários para sistemas satnav. Eles queriam verificações automáticas de integridade em seus dados, uma das quais era que a rede deveria ser conectada, ou seja, deveria ser possível chegar a qualquer lugar de qualquer ponto de partida. Verificar os dados tentando encontrar rotas entre todos os pares de posições seriam impraticáveis. No entanto, é possível derivar um gráfico direcionado dos dados da rede rodoviária (de maneira a codificar coisas como reviravoltas, etc.), de modo que o problema seja reduzido a encontrar os componentes fortemente conectados do gráfico - um gráfico padrão- Conceito teórico que é resolvido por um algoritmo eficiente.

Answer 4

Fiz um curso sobre testes de software e três das palestras foram dedicadas a revisar a matemática discreta, em relação aos testes. Pensar nos planos de teste nesses termos parece realmente ajudar a tornar os testes mais eficazes.

A compreensão da teoria dos conjuntos em particular é especialmente importante para o desenvolvimento do banco de dados.

Tenho certeza de que existem inúmeras outras aplicações, mas essas são duas que vêm à mente aqui.

Answer 5

Apenas exemplo de um de muitos ...

Em sistemas de construção, é popular usar a classificação topológica de empregos para fazer.

Por sistema de construção, quero dizer qualquer sistema em que tenhamos que gerenciar trabalhos com relação de dependência.

Ele pode ser um programa de compilação, gerando documentos, construção de construção, organização da conferência - para que haja aplicação em ferramentas de gerenciamento de tarefas, ferramentas de colaboração etc.

Answer 6

Acredito que se testar procedimentos adequadamente do Modus Tollens, um conceito de lógica proposicional (e, portanto, matemática discreta), sendo o modus tollens:

P => q. ! Q, portanto! P.

Se você conectar "Se o recurso estiver funcionando corretamente, o teste passará" para p => q, e depois tome! Você tem uma base sólida e sólida para devolver o recurso para uma correção. Por outro lado, muitos, talvez a maioria dos testadores opera pelo princípio:

"Se o programa estiver funcionando corretamente, o teste passará. O teste foi aprovado, portanto, o programa está funcionando corretamente".

Isso pode ser escrito como: p => q. Q, portanto, P.

Mas essa é a falácia de "afirmar o conseqüente" e não mostra o que o testador acredita que mostra. Ou seja, eles acreditam erroneamente que o recurso foi "validado" e pode ser enviado. Quando q é dado, p pode de fato ser verdadeiro ou pode ser falso para p => q, e isso pode ser mostrado com uma tabela de verdade.

O Modus Tollens é o núcleo da noção de ciência de Karl Popper como falsificação, e os testes devem prosseguir da mesma maneira. Estamos tentando falsificar a alegação de que o recurso sempre funciona em todas as circunstâncias explícitas e implícitas, em vez de tentar verificar se funciona no sentido restrito que pode funcionar de alguma maneira proibida.