▶▶ Elementos de matemática discreta 📚
Elementos de matemática discreta, tanto el libro de teoría como el de ejercicios, fueron los primeros que «leí» para aprender sobre esta disciplina. Te puedo decir que me encantaron. Además, era la primera vez que tomaba contacto con la matemática discreta y me pareció un mundo fascinate.
He decidido hacer esta reseña de los dos libros juntos, porque forman una unidad; en el primero aparecen todos los resultados teóricos y bastantes ejercicios resueltos; pero en el segundo aparece la resolución a todos los ejercicios propuestos en el primero y además algún que otro ejercicio extra.
Pero ¿qué es la matemática discreta? Estoy elaborando una entrada sobre ello, pero de momento te puedes quedar con el hecho de que cuando en matemáticas se dice que algo es discreto, normalmente tiene que ver con números enteros y éste es el caso de esta obra. Puesto que el libro de ejercicios es un apoyo a los resultados teóricos que se explican en el de teoría, la estructura que adoptan ambos libros es la misma. En concreto la obra está dividida en tres grandes bloques (puedes ver el índice al final de esta entrada, como siempre)
- Aritmética
- Grafos
- Combinatoria
Evidentemente cada uno de estos apartados podría dar para un libro individual y la matemática discreta abarca mucho más que estos tres grandes bloques; pero es así como está dividida la obra y creo que esta estructura es muy recomendable para un primer acercamiento a esta disciplina. Voy a ir explicándote qué vas a encontrarte en cada apartado:
Aritmética
La obra lo llama TEORÍA ELEMENTAL DE NÚMEROS pero yo he preferido renombrarlo en esta entrada como Aritmética para que todo el mundo pueda saber de un vistazo de qué va a tratar esta parte.
La propia obra dice lo siguiente en la introducción a este apartado:
La teoría de números es la parte de la matemática que trata de los números enteros y sus propiedades […] junto a la geometría, la teoría de números tiene el honor de ser la parte más antigua de las matemáticas
Introducción. Elementos de matemática discreta (Bujalance, 2005).
¿Pero esto qué quiere decir? Lo que quiere decir es que se lleva trabajando en esta rama de la matemática durante más de 2500 años. De hecho puedes leer mi entrada sobre números primos o sobre el teorema de Pitágoras, y verás que esta rama del conocimiento se lleva desarrollando varios milenios. Y todo esto es simplemente una pequeña parte de lo que es la teoría de números.
Entonces ¿La aritmética y la teoría de números es lo mismo? NO. Yo considero la aritmética como una parte de la teoría de números, pero no sinónimos. Si lo que quieres es aprender a operar con números (sumar, restar, multiplicar…) entonces estás haciendo aritmética; y es lo que se enseña durante gran parte del periodo de enseñanza obligatoria. Pero si lo que te preguntas son cosas más sutiles como ¿cuántos números primos hay que sean de la forma 4k+1? o ¿cómo se distribuyen los números primos dentro de los enteros? o ¿cuántas ternas pitagóricas existen? entonces estás haciendo teoría de números.
Como puedes comprobar la teoría de números es una parte más rica que la aritmética dentro de la matemática discreta.
Esta parte del libro empieza por algo tan básico como son los algoritmos de la división y de Euclides, pero poco a poco se va introduciendo en cuestiones más importantes como son el teorema fundamental de la aritmética y los números primos. También aborda el tema de las ecuaciones diofánticas y el principio de inducción, que parece que es un clásico en todo texto de iniciación a las matemáticas superiores (aparece en libros de matemática discreta, álgebra y análisis). Acaba esta parte del libro dedicando una sección entera a las congruencias que te explicaré en una entrada dentro de unas semanas.
Grafos
¿Has visto alguna vez un mapa de carreteras con ciudades, pueblos y cruces? ¿Y una red de metro? ¿Te has planteado alguna vez como ir de un sitio a otro de una ciudad tardando lo menos posible? ¿Quieres saber cómo los repartidores puedan hacer su ruta sin pasar varias veces por la misma calle? Pues entonces ya sabes lo que es un grafo y qué pinta tienen los problemas que se resuelven con grafos.
Todo el mundo está de acuerdo en que los grafos nacieron cuando los ciudadanos de la ciudad de Königsberg, hoy Kaliningrado, propusieron un acertijo sobre cómo cruzar los puentes sobre el río Pregel de una determinada manera en 1736. Se lo propusieron a Euler, y éste sentó las bases para una nueva disciplina.
La primera parte de la exposición trata básicamente de muchas definiciones: grafo, dígrafo, pseudografo, grafo bipartito… pero que tienes que conocer, ya que hay cuestiones que se resuelven (o no se puede resolver) de diferente manera dependiendo del tipo de grafo en el que estén planteados.
A mi lo que más me impresionó cuando leí el libro por primera vez son los problemas de decidir si un grafo es euleriano o hamiltoniano. Estas dos cuestiones me resultaron muy intesesantes: ¿cómo repartir las cartas en una ciudad? ¿cómo diseñar una red de alcantarillado? ¿y una red de trenes? ¿cómo distribuir el tráfico de una ciudad? ¿si se peatonaliza una calle, se van a provocar atascos 2 km más allá? Me parecen cuestiones muy importantes y que a todo el mundo afectan.
Acaba este apartado hablando del problema de los cuatro colores, cuyo ejemplo práctico más sencillo es que puedes colorear cualquier motivo plano como mapas, mandalas… con tan solo cuatro colores distintos y sin que dos regiones adyacentes compartan color.
Combinatoria
Por último, la combinatoria, es la parte de la matemática discreta que intenta dar respuestas a las siguientes cuestiones ¿Cuántas matrículas se pueden troquelar con el actual sistema? ¿Es fácil que te toque la lotería primitiva (a esta pregunta, también da respuesta la probabilidad)? ¿De cuántas maneras distintas se pueden sentar a una mesa una familia de cinco miembros?
Empieza esta parte sentando las bases de lo que luego va a desarrollar. Es decir, empieza hablando del principio de adición, de multiplicación y de distribución (éste último tiene un nombre común que a mí me gusta más: principio del palomar).
Después pasa a hablar de las cuestiones básicas de combinatoria, que te las presento con una pregunta cada una:
- Permutaciones: ¿De cuántas formas distintas pueden disponerse 10 personas en fila?
- Variaciones: ¿Cuántos números de 6 dígitos existen que sean capicúas y no empiecen por 0?
- Combinaciones: ¿Cuántos boletos del Euromillones existen distintos?
Continúa hablando del teorema del binomio y acaba dedicando una sección al principio de exclusión-inclusión y finalmente con unas nociones de recursividad.
Como ves es un libro muy completo, que te da una visión completa de todo lo que es la matemática discreta y que te permite sentar las bases para que luego puedas ir aplicando estos conocimientos en otras disciplinas, como estadística y probabilidad, computación…
Una pega sí le pondría a este libro. La edición que yo tengo (2005) tiene una tipografía mala, parece hecha con un editor WYSIWYG y a mí personalmente me costó un poco acostumbrarme a ello. No sé si en la siguientes ediciones lo habrán resuelto, me imagino que sí, y que lo habrán tipografiado con un editor WYSIWYM tipo LaTeX o similar.
Índice de elementos de matemática discreta
A continuación te dejo el índice del libro para que tengas una visión completa del mismo:
- Teoría elemental de números.
- Algoritmos de la división y Euclides.
- Números primos y teorema fundamental de la aritmética.
- El principio de inducción.
- Ecuaciones diofánticas.
- Congruencias.
- Sistemas de numeración y criterios de divisibilidad.
- Introducción a la teoría de grafos
- Grafos, digrafos y multigrafos.
- Grafos eulerianos y hamiltonianos.
- Exploración de grafos.
- Mapas y coloraciones.
- Combinatoria
- Técnicas básicas.
- Permutaciones, variaciones combinaciones.
- Teorema del binomio.
- Principio de inclusión-exclusión.
- Recursividad y relaciones recurrentes.
Pues hasta aquí todo lo que tenía que contarte ¿Tú también has trabajado este libro?, ¿qué otros libros de matemática discreta nos recomendarías? Como de costumbre puedes dejar tus respuestas a estas preguntas u otros comentarios más abajo
Gracias por leerme
Si quieres contactar conmigo puedes hacerlo aquí
Si te ha gustado lo que has leído y quieres invitarme a un café ☕, te doy las gracias por adelantado.
Vida de la entrada:
– 2020-08-20: Publicación.
– 2020-09-03: Corrección erratas. Añadido botón Paypal.