matematicas discretas

Historia
Las matemáticas discretas han visto un gran número de problemas difíciles de resolver. En teoría de grafos, mucha de la investigación realizada en sus inicios fue motivada por intentos para probar el teorema de los cuatro colores, el cual fue probado más de cien años después de su inicial descripción. El problema de los puentes de Königsberg, un problema clásico del prolífico LeonhardEuler.
En lógica, el segundo problema de la lista de problemas abiertos de David Hilbert, era probar que los axiomas de la aritmética son consistentes. El segundo teorema de Gödel de la incompletitud probó en 1931 que esto no es posible, por lo menos dentro de la aritmética en sí. El décimo problema de Hilbert era determinar si un polinomio diofántico con coeficientes enteros dado tiene unasolución entera. En 1970, Yuri Matiyasevich probó que esto es imposible de hacer.
La necesidad de descifrar códigos alemanes en la Segunda Guerra Mundial dio paso a avances en la criptografía y la ciencia computacional teórica, con el primer computador electrónico, digital y programable desarrollado en Inglaterra. Al mismo tiempo, requerimientos militares motivaron avances en la investigación deoperaciones. La Guerra Fría tuvo significancia en la criptografía, y la mantuvo vigente, con lo que se realizaron avances en la criptografía asimétrica.
Actualmente, uno de los problemas abiertos más famosos en la teoría de la informática es el problema de las clases de complejidad "P = NP". El Clay Mathematics Institute ha ofrecido un premio de un millón de dólares para la primera demostracióncorrecta, junto con premios para 6 problemas más.
Tópicos en la matemática discreta
Informática teórica
Artículo principal


La complejidad estudia el tiempo en el cual un algoritmo se ejecuta.
La teoría de la informática incluye áreas de la matemática discreta relevante a la computación. Está altamente relacionada con teoría de grafos y lógica. Dentro de la teoría de la informática se encuentrala teoría de algoritmos para problemas matemáticos. La computabilidad estudia lo que puede ser computado y tiene lazos fuertes con la lógica, mientras que la complejidad estudia el tiempo que se demora en hacer computaciones. La teoría de autómatas y los lenguajes formales se relacionan de manera cercana con la computabilidad. Las redes de Petri y álgebra de procesos se usan para modelar sistemascomputacionales, y métodos de la matemática discreta se usan para analizar circuitos VLSI. La geometría computacional aplica algoritmos a problemas geométricos, mientras que el análisis digital de imágenes los aplica a representaciones de imágenes. La teoría informática también incluye el estudio de tópicos de informática continua.
Teoría de la información
Artículo principal: Teoría de laInformación


Los códigos mostrados aquí son una manera de representar una palabra en teoría de la información, como también para algoritmos de proceso de información.
La teoría de la información se ve involucrada en la cuantificación de la información. Cercanamente relacionado a esto es la teoría de codificación, que es usada para diseñar métodos de transmisión y almacenamiento de datos eficientesy confiables. La teoría de la información también incluye tópicos continuos tales como señales análogas, codificación análoga y cifrado análogo.
Lógica
Artículo principal: Lógica matemática
La lógica es el estudio de los principios del razonamiento válido y la inferencia, como también de la consistencia, solidez y completitud. Por ejemplo, en la mayoría de los sistemas en la lógica, la ley dePeirce, (((P→Q)→P)→P) es un teorema. En lógica clásica, puede ser fácilmente verificado con una tabla de verdad. El estudio de las demostraciones matemáticas es particularmente importante en lógica y tiene aplicaciones en la demostración automática de teoremas y verificación formal de software.
Las fórmulas lógicas son estructuras discretas, como lo son las demostraciones, las cuales forman...