Matematicas

Historia
La historia de las matemáticas discretas ha 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.
En lógica, el segundo problema de la lista de problemas abiertos deDavid 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 una solución entera. En 1970, Yuri Matiyasevich probó que esto es imposible de hacer.La necesidad de burlar 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 de operaciones. La Guerra Fría tuvo significancia en la criptografía, manteniéndolavigente, realizándose 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ón correcta, junto con premios para 6 problemas más.
[editar] Tópicos en la Matemática Discreta[editar] Informática Teórica
Artículo principal: Ciencia computacional teórica
[pic]
[pic]
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 encuentra la teoría de algoritmos paraproblemas 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 sistemas computacionales, y métodos de lamatemá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.
[editar] Teoría de la Información
Artículo principal: Teoría de la Información
[pic]
[pic]
Loscó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 eficientes y 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.
[editar] Lógica
Artículo principal: Lógica matematica
La lógica es el estudio de los principios del razonamiento valido 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 formulas lógicas son estructuras discretas, como lo son las demostraciones, las cuales forman árboles...