|
Índice
Prólogo
En los libros anteriores de la presente serie, el desarrollo de los sucesos fundamentales en mayor o menor grado estaba relacionado con la noción clave de proximidad, cuya comprensión matemática condujo a una desconcertante cascada de los más diversos resultados. Sin embargo, existe una amplia clase de problemas matemáticos en los que esta noción no es aplicable. La mayoría de estos problemas tratan sobre las propiedades de los conjuntos finitos. La cantidad de elementos en estos conjuntos puede variar desde unos pocos hasta potencias grandes de diez (1010, 101010,...). Los orígenes de algunos de estos problemas y los métodos de su resolución distan de nosotros cientos e incluso miles de años. El surgimiento de otros fue estimulado por el desarrollo de los medios computacionales, cuyas posibilidades se encuentran en impetuoso crecimiento y sirven como fuente de nuevos problemas. El creciente interés en problemas de este tipo dio vida a un nuevo concepto: la matemática discreta. Comprendida en un sentido amplio, la matemática discreta incluye en sí la teoría de números, el álgebra general, la lógica matemática, la combinatoria, la teoría de grafos, la teoría de codificación, la programación entera, la teoría de sistemas funcionales, etcétera. Lo discreto (del latín discretus, separado, discontinuo) frecuentemente se contrapone a lo continuo. Sin embargo, cuando se resuelven problemas prácticos de alta dificultad los métodos discretos y continuos se aplican conjuntamente y con considerable eficacia, enriqueciéndose mutuamente. En 1989 fue publicado el libro de R.Graham, D.Knuth y O.Patashnik "Concrete mathematics". El término CONCRETE se forma de la unión de las palabras CONtinious y disCRETE. El objetivo fundamental de este libro era proporcionar al lector conocimientos sobre el funcionamiento de la técnica de operación con objetos discretos, análoga a la técnica empleada en el caso de objetos continuos. Nuestro objetivo es más modesto: dar a conocer al lector algunos elementos de la matemática discreta. En los dos primeros capítulos se consideran los fundamentos de la teoría de números y del álgebra general; los conceptos matemáticos introducidos allí son utilizados ampliamente en los capítulos siguientes, en particular, en el estudio de la teoría de Pólya, la cual permite resolver problemas de conteo de objetos a excepción de una u otra relación de equivalencia. En el capítulo "Combinatoria", además de los conceptos iniciales sobre las técnicas de selección y análisis de muestras, se expone el principio de inclusión–exclusión, que es aplicado eficazmente en la resolución de algunos problemas combinatorios clásicos. Se introduce asimismo el aparato de las funciones generatrices, potente instrumento del análisis combinatorio. En los capítulos finales se consideran los conceptos fundamentales de la teoría de grafos y matroides, así como algunos algoritmos efectivos. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||