GAC024 Matemáticas discretas

GAC024 es matemáticas discretas: la matemática de las cosas que se pueden contar y de la lógica sobre la que funcionan los ordenadores. Cinco unidades cubren conjuntos, sistemas de conteo, binario, algoritmos y grafos.

Se asocia naturalmente con los módulos de informática, y las universidades que acreditan GAC016 suelen reconocer también esta unidad como parte de un curso de fundamentos de ciencias de la computación. La evaluación sigue el patrón habitual: una prueba, un examen y trabajos prácticos (coursework).

• ⚠ Las matemáticas discretas tienen pocas fórmulas y mucho razonamiento. Una demostración o un trazado de algoritmo obtienen las puntuaciones, y una respuesta sin justificación casi no suma puntos.

• Un conjunto 集合 es una colección de objetos distintos. El orden y la repetición no importan.
• La unión 并集 $A \cup B$ contiene todo lo que está en uno u otro; la intersección 交集 $A \cap B$ contiene lo que está en ambos; el complemento del conjunto 补集 contiene todo lo que está fuera.
• Un subconjunto 子集 tiene todos sus elementos dentro de otro conjunto.
• Una relación 关系 empareja elementos de dos conjuntos. Una función 函数 es una relación en la que cada entrada tiene exactamente una salida.
• Un diagrama de Venn 韦恩图 convierte un problema de conjuntos en una imagen, y dibujarlo suele ser más rápido que razonarlo con palabras.

Ejemplo resuelto. En una clase de 30 estudiantes, 18 estudian francés y 15 estudian alemán; 7 estudian ambas lenguas. ¿Cuántos no estudian ninguna?

Restar la intersección una sola vez es el principio de inclusión-exclusión 容斥原理. Sumar 18 y 15 sin aplicarlo cuenta a los siete estudiantes dos veces, que es el error estándar.

• Una base numérica 进制 indica cuántos dígitos utiliza. El decimal 十进制 usa diez, el binario 二进制 dos, el hexadecimal 十六进制 dieciséis.
• El valor de cada dígito es su valor posicional 位值: en binario, las posiciones son 1, 2, 4, 8, 16, etc.
• El hexadecimal es una abreviatura del binario: un dígito hexadecimal equivale exactamente a cuatro bits, por eso las direcciones de memoria se escriben en él.

Ejemplo resuelto. Convierte 1101 en binario a decimal.

Escribe los valores posicionales encima de los dígitos antes de sumar. Hacerlo mentalmente es donde surgen los errores de "uno de más" (off-by-one errors).

• La aritmética binaria 二进制运算 suma igual que en decimal, pero llevando al 2 en lugar de al 10.
• Un bit 位 es un dígito binario; un byte 字节 son ocho.
• El álgebra de Boole 布尔代数 trabaja con verdadero y falso mediante AND, OR y NOT.
• Una tabla de verdad 真值表 enumera cada combinación de entradas y su salida, y constituye la prueba completa de que dos expresiones lógicas son equivalentes.
• Las puertas lógicas 逻辑门 son la forma física de esas operaciones, y un circuito lógico 逻辑电路 es de lo que está hecho un procesador.

• Un algoritmo 算法 es una secuencia finita de pasos inequívocos que termina.
• Un diagrama de flujo 流程图 lo representa gráficamente: una decisión es un rombo, un proceso un rectángulo.
• El pseudocódigo 伪代码 lo escribe en inglés estructurado, que es lo que normalmente piden los exámenes.
• El trazado 追踪 de un algoritmo —una tabla con una columna por variable y una fila por paso— es la técnica evaluada, y permite encontrar un error sin ejecutar nada.
• La eficiencia 效率 importa: una búsqueda lineal revisa cada elemento, una búsqueda binaria reduce la lista a la mitad cada vez, y en un millón de elementos, esa diferencia equivale a un millón de pasos frente a veinte.

Ejemplo resuelto. Trazar una búsqueda binaria para 7 en [1, 3, 5, 7, 9, 11].

El medio es 5, que es menor que 7, así que se busca en la mitad derecha. El medio de [7, 9, 11] es 9, que es mayor, así que se busca en la izquierda. El medio de [7] es 7. Encontrado en tres pasos en lugar de cuatro.

La tabla de pasos es la respuesta. La palabra "encontrado" no lo es.

• Un grafo 图 es un conjunto de vértices 顶点 unidos por aristas 边. Modela cualquier cosa con conexiones: carreteras, amistades, dependencias.
• El grado 度 de un vértice es cuántas aristas concurren en él.
• Un árbol 树 es un grafo conectado sin ciclos, y representa la estructura de un sistema de archivos, un organigrama o un documento HTML.
• Un problema de camino más corto 最短路径 busca la ruta de menor coste entre dos vértices, y es lo que resuelve una aplicación de navegación cada vez que la usas.