Buscando ejemplos en los que el conocimiento de las matemáticas discretas es útil [cerrar]

Question

Inspirado después de ver la charla de Michael SCNA pluma " Auto-Educación y el artesano", me estoy interesado en escuchar acerca de ejemplos prácticos en el desarrollo de software, donde las matemáticas discretas han demostrado ser útiles.

Answer 1

matemáticas discreta ha tocado todos los aspectos de desarrollo de software, como el desarrollo de software se basa en la informática en su núcleo.

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

Leer ese enlace. Se verá que existen numerosas aplicaciones prácticas, aunque esta entrada de Wikipedia habla principalmente en términos teóricos.

Answer 2

Las técnicas que he aprendido en mi curso de matemáticas discretas de la universidad me ayudó un poco con los juegos Profesor Layton.

Eso cuenta como útiles ... ¿verdad?

Hay un montón de ejemplos de la vida real donde los algoritmos mapa colorantes son útiles, además de sólo para mapas para colorear. La pregunta en mi examen final tuvo que ver con la programación semáforo en un cruce de seis posiciones.

Answer 3

Como San Jacinto indica, los fundamentos de la programación están muy ligados en matemáticas discretas. Por otra parte, la 'matemática discreta' es un término muy amplio. Estas cosas tal vez sea más difícil de seleccionar ejemplos particulares. Puedo llegar a un puñado, pero hay muchos, muchos otros.

aplicación Compiler es una buena fuente de ejemplos: obviamente hay teoría del lenguaje autómatas / formal en allí; registrar la asignación puede ser expresada en términos de coloración gráfico; Los análisis del flujo de datos clásico utilizado en la optimización de los compiladores se puede expresar en términos de funciones en estructuras algebraicas de celosía-similares.

Un ejemplo sencillo el uso de gráficos dirigidos se encuentra en un sistema de construcción que se lleva a las dependencias involucradas en tareas individuales mediante la realización de una ordenación topológica. Sospecho que si se trató de resolver este problema sin tener el concepto de un grafo dirigido entonces es probable que iba a terminar tratando de realizar un seguimiento de las dependencias de todo el camino a través de la construcción con más incómoda libro de mantenimiento de código (y luego encontrar que su manejo de dependencias cíclicas era menos de elegante).

Es evidente que la mayoría de los programadores no escriben sus propios compiladores optimizadores o construir sistemas, así que va a retomar un ejemplo de mi propia experiencia. Hay una empresa que proporciona datos de carreteras para los sistemas de navegación vía satélite. Querían comprobaciones de integridad automáticos en sus datos, uno de los cuales era que la red debería ser conectado a todos, es decir, debería ser posible llegar a cualquier lugar desde cualquier punto de partida. Comprobación de los datos, tratando de encontrar las rutas entre todos los pares de posiciones, no sería práctico. Sin embargo, es posible derivar un grafo dirigido a partir de los datos de la red de carreteras (de tal manera que codifique cosas como el torneado restricciones, etc) de modo que el problema se reduce a encontrar los componentes fuertemente conectados de la gráfica - un graph- estándar concepto teórico que se resuelve mediante un algoritmo eficiente.

Answer 4

he estado tomando un curso sobre las pruebas de software, y 3 de las conferencias se dedicaron a la revisión de las matemáticas discretas, en relación con las pruebas. Pensando en los planes de prueba en esos términos parece ayudar realmente a hacer la prueba más eficaz.

La comprensión de la teoría de conjuntos, en particular, es especialmente importante para el desarrollo de bases de datos.

Estoy seguro de que hay muchas otras aplicaciones, pero esas son dos que vienen a la mente aquí.

Answer 5

Sólo ejemplo de uno de los muchos muchos ...

En los sistemas de compilación es popular el uso de clasificación topológica de puestos de trabajo que hacer.

Por sistema de construcción me refiero a cualquier sistema en el que tenemos que administrar los trabajos con relación de dependencia.

Se puede compilando programa, generando documento, la construcción de edificio, la organización de la conferencia -. Por lo que no es de aplicación en las herramientas de gestión de tareas, herramientas de colaboración, etc.

Answer 6

Creo que la prueba en sí PROCÉDÉS correctamente desde modus tollens, un concepto de la lógica proposicional (y por lo tanto, matemáticas discretas), modus tollens ser:

P => Q. ! Q, por lo tanto! P.

Si enchufa "Si la función está funcionando adecuadamente, la prueba pasará" para P => Q, y luego tomar! Q como se indica ( "la prueba no pasó"), y luego, si todas estas afirmaciones son objetivamente correcta, usted tiene una base válida, sonido para el retorno de la función para una solución. Por el contrario, muchos, tal vez la mayoría de los probadores operan por el principio:

"Si el programa está funcionando adecuadamente, la prueba pasará. La prueba se ha superado, por lo tanto, el programa está funcionando adecuadamente."

Esto se puede escribir como: P => Q. Q, por lo tanto, p

Pero esta es la falacia de "afirmación del consecuente" y no muestra lo que el probador cree que se nota. Es decir, que creen erróneamente que la función ha sido "validado" y puede ser enviado. Cuando se da Q, P puede ser de hecho o bien ser verdad o puede ser falso para P => Q, y esto puede ser demostrado con una tabla de verdad.

Modus Tollens es el núcleo de la noción de la ciencia como la falsificación de Karl Popper, y la prueba debe proceder de la misma manera. Estamos tratando de falsificar la afirmación de que la función siempre funciona en todas las circunstancias explícito e implícito, en lugar de intentar comprobar que funciona en el sentido estricto de que se puede trabajar de alguna manera proscrita.