Profundiza en las matemáticas universitarias con humor E-Book

Luis Martínez Fernández

• Herausgeber: Marcombo
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Spanisch
• Veröffentlichungsjahr: 2024

Seitenzahl: 478

Beschreibung

¡Descubre el lado divertido de las matemáticas universitarias! ¿Estás estudiando una carrera que incluye matemáticas y se te hace cuesta arriba? ¿O quizás eres un entusiasta de los números que busca una perspectiva fresca y divertida? ¡Este libro te vendrá que ni pintado! Profundiza en las matemáticas universitarias con humor no es un libro de texto tradicional. Aquí, las matemáticas cobran vida a través de un enfoque único que combina rigurosidad académica con un toque de humor. Con ejemplos prácticos, ejercicios estimulantes y un lenguaje accesible, el aprendizaje se transforma en una experiencia amena y enriquecedora. ¿Qué encontrarás en este libro? "Temas avanzados como los algoritmos, la aritmética modular, los anillos de polinomios y las desigualdades avanzadas, con chascarrillos y bromas intercalados, para que se hagan más llevaderos los teoremas. "Muchos ejemplos y ejercicios para que no se quede todo en una teoría árida y abstrusa, y que así puedas asimilar mejor los conceptos y resultados. "Materiales adicionales en la web asociada al libro: www.elhumornoquitaelrigor.com Además, presumirás de erudición matemática con tus amistades, a la vez que te ahorrarás una pasta gansa en academias. Este libro es perfecto para estudiantes de cualquier carrera que incluya matemáticas, desde ingenierías hasta ciencias de la salud. También es ideal para profesores que buscan una herramienta didáctica con un enfoque innovador. ¡Sumérgete en el fascinante mundo de las matemáticas universitarias con humor! Sin duda, este libro transformará tu forma de ver y aprender las matemáticas para siempre. El autor de este libro, Luis Martínez, es profesor titular del área de álgebra de la Universidad del País Vasco (UPV/EHU) y humorista vocacional con sus compañeros, amigos y familiares en sus ratos libres. Además de este libro sobre conocimiento avanzado de las matemáticas, Luis ha escrito Adéntrate en las matemáticas universitarias con humor, un compendio para divertirte y reírte durante el proceso de aprendizaje de cuestiones matemáticas básicas.

Leseprobe

Profundiza en las matemáticas universitarias con humor

Luis Martínez

Profundiza en las matemáticas universitarias con humor

© 2024 Luis Martínez

Primera edición, 2024

© 2024 MARCOMBO, S. L.

www.marcombo.com

Diseño de cubierta: ENEDENÚ DISEÑO GRÁFICO

Maquetación: Luis Martínez

Corrección: Cristina Pazos

Directora de producción: M.a Rosa Castillo

Cualquier forma de reproducción, distribución, comunicación pública o transformación de esta obra solo puede ser realizada con la autorización de sus titulares, salvo excepción prevista por la ley. Diríjase a CEDRO (Centro Español de Derechos Reprográficos, www.cedro.org) si necesita fotocopiar o escanear algún fragmento de esta obra.

ISBN del libro en papel: 978-84-267-3678-9

ISBN del libro electrónico: 978-84-267-3800-4

Producción del ePub: booqlab

Índice general

Prefacio

1. Paso a paso, verso a verso

1.1. ¡Que no decaiga el ritmo, aquí llega el algoritmo!

1.2.El que busca, halla

1.3. Ejercicios

2. Un número no basta

2.1. Navegando por el espacio

2.2. El subespacio ocupa poco espacio

2.3. Sentando las bases

2.4. El excelente cociente

2.5. Lo lineal no está tan mal

2.6. Ejercicios

3. Divide y vencerás

3.1. La entereza de los números ante los problemas matemáticos

3.2. Echando el resto

3.3. Dame una base de apoyo y levantaré un sistema de numeración

3.4. Más vale que no sobre, pero que tampoco falte

3.5. Haciendo el primo

3.6. ¡Qué emoción con la factorización!

3.7. Ejercicios

4.Reloj, no marques las horas

4.2. Divide, no divide, divide, no divide... ¡divide!

4.3. ¡No seamos incongruentes!

4.4. Un teorema añejo

4.5. Vamos a contar coprimos, tralará

4.6. Un pequeño teorema que sí cabe en el margen de una hoja

4.7. Ejercicios

5. Cifras y letras

5.1. Números de quita y pon

5.2. ¿Y qué pasa con la división?

5.3. La aldea de los irreductibles polinomios

5.4. ¡Este polinomio va a sacar un cero!

5.5. Si divides de manera formal, obtendrás una función racional

5.6. Ejercicios

6. ¡Da Igual si es Desigual!

6.1. Poniendo orden en los números reales

6.2. Despejando dudas

6.3. Es un clásico

6.4. Ejercicios

Apéndice: construcción rigurosa de los anillos de polinomios

Bibliografía

Prefacio

Si han leído “Adéntrate en las matemáticas universitarias con humor”([7]), ya saben de qué va este libro. Si no lo han hecho, les diré que es un libro de matemáticas contadas con humor y desparpajo.

Al igual que el anteriormente citado, este libro trata sobre temas que es necesario conocer en un primer curso de un grado en ciencias o ingeniería (matemáticas, químicas, geología1, ingenierías varias, etc.).

No es, ni mucho menos, un libro enciclopédico sobre matemáticas universitarias, sino algo más próximo a los conocimientos iniciales que se necesitan al iniciar una carrera de ciencias y que se suelen dar en un curso puente, a veces llamado curso cero y, otras veces, simplemente se presuponen2 o, quizá peor aún, se dan deprisa y corriendo3 sin dar tiempo de afianzar los conocimientos.

Este libro, “Profundiza en las matemáticas universitarias con humor”, es una continuación del ya mencionado4 “Adéntrate en las matemáticas universitarias con humor”, lo cual ya se veía venir en la aliteración de los títulos.

No obstante, no es un volumen II, en cuanto a que se puede leer independientemente del anterior y, en las referencias que se hagan al mismo en algunas definiciones, proposiciones y teoremas, se dará una descripción de los mismos para que los lectores no dependan de su conocimiento previo. Así y todo, les recomiendo que, si no han leído “Adéntrate en las matemáticas universitarias con humor”5 lo hagan sin dilación, ya que ha tenido un gran éxito de público y crítica entre mi familia y amigos, lo cual es una garantía indudable y objetiva de calidad.

Como bien dijo el profesor Piero Grullo en su famoso “Tractatus semántico-lúdico”, no es lo mismo adentrarse que profundizar, ya que, si uno profundiza sin haberse adentrado primero, se pega tremendo galletazo con la puerta. En consecuencia, en “Adéntrate en las matemáticas universitarias con humor”6 traté principalmente temas básicos relativos a teoría de conjuntos y estructuras algebraicas que nos proporcionan los fundamentos y el lenguaje para poder estudiar otros temas más avanzados.

Basándome en lo anterior, en este libro expongo algunos tópicos más avanzados, como puedan ser los espacios vectoriales, la aritmética modular sobre los números enteros, los polinomios y las identidades sobre desigualdades entre números reales.

Además, este libro tiene un punto de vista más algorítmico que el anterior, más ‘de hacer cuentas’, para entendernos (lo cual reducirá ligeramente el número de bromas por página). Este es un enfoque muy importante en las matemáticas, pudiéndose decir que los algoritmos están presentes en gran parte de nuestras vidas, desde si nos conceden un crédito (o, por el contrario, empiezan a sonar fuertemente las alarmas y a encenderse las luces de emergencia en el banco) hasta la publicidad personalizada (viajes vacacionales a Turquía, ¿cómo rayos sabían que empiezo a tener alopecia?). En este libro no trataremos algoritmos tan avanzados, pero empezaremos a entender la idea general de qué es un algoritmo y cómo funciona.

Sigo teniendo las mismas deudas de gratitud en la escritura de este libro que en la del anterior y no enumeraré de nuevo la lista de agradecimientos, sobre todo para no volver a poner en evidencia a los aludidos, aunque sí añadiré a María Merino, revisora de algunos añadidos de última hora al libro y paciente sufridora de mis chistes en el comedor de la universidad. También quisiera mencionar a Antonio Vera, que siempre me ha apoyado en mi proyecto humorístico-matemático.

La web de este libro está en la dirección www.elhumornoquitaelrigor.com, que también aloja la del libro “Adéntrate en las matemáticas universitarias con humor”, que forma parte, al igual que este, de la serie de libros humorístico-científicos7 “El humor no quita el rigor”. En particular, en dicha web aparecen las soluciones a los ejercicios planteados al final de cada capítulo, además de otros materiales complementarios que no cabían en el margen de este libro8. También pueden encontrar en la web programas en Python que implementan los algoritmos descritos en el libro.

1 Mal que le pese a Sheldon Cooper.

2 Asumiendo el don de la ciencia infusa por parte de los alumnos.

3 Porque me oprime el corsé.

4 Con esta va la tercera: ¿publicidad encubierta, o no solo en la cubierta?

5 ¡Y van cuatro!

6 He perdido la cuenta, si la encuentran, avísenme.

7 A partes iguales.

8 Los lectores tendrán que esperar a leer el capítulo 4 para entender este último chiste.

Capítulo 1

Paso a paso, verso a verso

1.1. ¡Que no decaiga el ritmo, aquí llega el algoritmo!

Los algoritmos sirven para resolver problemas1. Tienen unos datos de entrada y producen un resultado, normalmente numérico, de salida, después de la ejecución de algunos procesos matemáticos a lo largo de una serie de pasos o etapas consecutivas. Son un poco, como si dijéramos, como una receta de cocina, pero en plan matemático, como se puede ver en la siguiente figura:

Figura 1.1: Algoritmo de la tortilla de patatas

Su nombre proviene de la fonética del nombre del matemático árabe Mohammed Ibn Musa Al-Khwarizmi, que los utilizó en sus escritos matemáticos. También el nombre ‘álgebra’, que es un área de conocimiento de las matemáticas, deriva de una de sus obras más famosas, “Kitab al-jabr wa al-muqabalah”. A pesar de su otro apellido, no inventó el mus2 y dar nombre a los algoritmos y al álgebra ya es mérito más que suficiente para entrar en el Parnaso de las matemáticas.

Aunque lo que voy a aclarar ahora es obvio, huelga decir que un algoritmo tiene que terminar y producir su resultado en un número finito de pasos, y este tiene que ser un resultado correcto que resuelva el problema planteado3.

Hoy en día los algoritmos están muy de moda y se usan para casi todo, desde proteger la seguridad de sus transacciones electrónicas4, de forma que no le puedan atacar su cuenta bancaria, hasta predecir las pautas de consumo de las personas, de forma que puedan atacar con su consentimiento su cuenta bancaria.

Ilustraré el concepto de algoritmo con un ejemplo bien conocido: el método de Gauss para resolver sistemas de ecuaciones lineales haciendo ceros por debajo de la diagonal en la matriz de coeficientes del sistema. Esto es lo que han venido ustedes haciendo desde la escuela elemental, aunque probablemente no se lo hayan presentado como método de Gauss, y consiste, dicho brevemente, en ir ‘eliminando’ incógnitas, de forma que en cada ecuación aparezca una menos que en la anterior y al final del proceso, en la última ecuación, aparezca solo una incógnita y, por lo tanto, sea una ecuación lineal fácil de resolver. Ahora, en la penúltima ecuación solo aparecen dos incógnitas y una de ellas se acaba de obtener en la forma que he descrito hace un momento, por lo que es fácil determinar la otra y así sucesivamente hasta hallar los valores de todas las incógnitas y resolver el sistema de ecuaciones.

El problema es en realidad más complicado de lo que acabo de contar, ya que el sistema puede no tener ninguna solución, en cuyo caso se dice que es incompatible, o también pueden tener más de una solución, y en este caso, se dice que el sistema es compatible indeterminado. Aunque el algoritmo se puede aplicar, haciendo las modificaciones necesarias, de forma que se engloben también estas situaciones en que el sistema es incompatible (de forma que el mismo detecte que no hay solución del sistema) o compatible indeterminado, lo explicaré para la circunstancia en que tiene una única solución (en este caso se dice que el sistema es compatible determinado) y en que el número de ecuaciones es igual al número de incógnitas (estos sistemas con solución única y tantas ecuaciones como incógnitas se llaman sistemas de Cramer). También supondremos que los coeficientes, los términos independientes y las soluciones buscadas son números reales o, más en general, números complejos, si los lectores no se sienten amilanados por ellos5.

Supondremos, entonces, que ustedes tienen un sistema de ecuaciones lineales:

que quieren resolver, bien sea motu proprio o por exigencias de algún profesor.

Los números a11, ..., an, n se llaman coeficientes del sistema y los números b1, ..., bn se llaman términos independientes. Las x1, ..., xn se llaman incógnitas. Tanto los coeficientes como los términos independientes se consideran parámetros. Esto quiere decir que no son números concretos pero, a diferencia de las incógnitas, cuando se planteen y resuelvan un sistema de ecuaciones concreto van a tener unos valores específicos. Es decir, el sistema se puede representar dando los coeficientes ai, j con 1 ≤ i, j ≤ n y dando los términos independientes bi con 1 ≤ i ≤ n. Los coeficientes ai, j se suelen organizar distribuyéndolos en n filas y n columnas, formando lo que se llama una matriz numérica6. Denotaremos esta matriz por A y la llamaremos matriz asociada al sistema. Análogamente, los términos independientes bi se suelen organizar en una matriz columna con los n números distribuidos a lo largo de la misma. Denotaremos esta matriz por B y la llamaremos matriz de términos independientes.

Una solución del sistema es una n-tupla (u1,...,un) que satisface que al sustituir cada incógnita xi por el número ui se tiene una igualdad en cada ecuación, es decir, se cumple:

Fíjense bien, el antiguo valor de a2, 1 es 5 y aprovechamos que en la primera ecuación el coeficiente de la x es 2, por lo que al multiplicar la primera ecuación por conseguimos dos cosas: primero, al dividir por 2 se tiene que el 2 aparece multiplicando y dividiendo, por lo que este se cancela y nos queda, provisionalmente, un 1; segundo, al multiplicar por 5 el 1 provisional que hemos mencionado, obtenemos como resultado 5, que es igual al coeficiente de la x en la segunda ecuación, de forma que al hacer la diferencia se cancelan los términos en los que aparece la x. Esta es la explicación del misterioso cociente c definido en la instrucción 8 y que aparece también en las instrucciones 10 y 12 del algoritmo: el denominador ai, i ‘borra’ el coeficiente de la variable xi en la ecuación que restamos, y el numerador ‘copia’ el coeficiente de xi en la ecuación de la que hacemos la resta, de forma que se cancele el término en xi. Más concretamente, la instrucción 12 consiste en hacer la misma operación con los correspondientes términos independientes, ya que la operación la hacemos con las ecuaciones completas.

Volviendo al ejemplo, podemos ver que en la ‘nueva’ segunda ecuación, , podemos despejar la y dividiendo en ambos miembros entre , obteniendo que y, sustituyendo este valor de la y en la primera ecuación, se llega a que y volvemos a tener una ecuación con una sola incógnita, que es fácil de resolver y se obtiene que .

Este proceso de ir despejando ‘hacia atrás’ las incógnitas se corresponde con las instrucciones 15 a 18 del algoritmo.

En capítulos posteriores del libro iremos viendo algunos otros algoritmos clásicos. Un aspecto importante a tener en cuenta en la teoría de algoritmos es el estudio de la complejidad de los mismos. Esto no tiene que ver con lo ‘difíciles’ que les parezca a los estudiantes11, sino con que haya que dar muchos o pocos pasos para obtener la solución (aquí por ‘pasos’ no quiero decir iteraciones en los bucles del algoritmo, sino operaciones elementales como hacer una suma, resta, multiplicación, división, exponenciación, comparación lógica, asignación a una variable, etc.). Si hay que dar muchos pasos, esto va a redundar negativamente, cuando se ejecute el algoritmo en un ordenador, en el tiempo que será necesario para ejecutar el programa. Una medida de si el número de pasos es grande viene dada por la comparación del número n de bits necesarios para representar los elementos de entrada del algoritmo y el número P(n) de pasos necesario para obtener la solución (puede considerarse el número máximo de pasos, el número promedio de pasos, etc.). Un tipo de algoritmos especialmente interesantes son los que tienen una complejidad polinomial. Esto quiere decir que el número de pasos P(n) está acotado por un polinomio de grado fijo evaluado en n. Estos se consideran eficientes, porque el número de pasos es asumible (¡dentro de lo que cabe!). Cuando ocurre esto, se dice que el problema que resuelve el algoritmo está en P.

Veremos en los ejercicios que el algoritmo descrito para resolver sistemas de Cramer tiene una complejidad polinomial, así como también la tienen los demás algoritmos que estudiaremos más adelante.

TURING EX MACHINA

Las matemáticas estudian de manera teórica muchas cuestiones relacionadas con la computación, como, por ejemplo, ¿qué números pueden ser computados con un dispositivo mecánico? ¿qué teoremas matemáticos pueden ser demostrados sistemáticamente a partir de un conjunto de axiomas y unas reglas de inferencia? ¿cuál es el mínimo número de instrucciones con el que se puede elaborar un algoritmo que resuelva un problema? ¿qué ordenador me puedo comprar que sea bueno, bonito y barato? (esta última, como habrán observado, es de broma).

El matemático Alan Turing planteó en [13] una máquina hipotética que consiste básicamente en una cinta infinita dividida en casillas y un cabezal de lectura y escritura que puede desplazarse sobre la cinta a derecha e izquierda (en la formulación original de Turing era la cinta la que se desplaza a derecha e izquierda por el cabezal. Como la cinta es infinita y, por tanto, tiene una masa infinita, esto plantearía un problema de eficiencia energética si existiera de verdad). La cinta contiene inicialmente una serie de símbolos de un alfabeto finito dado (considerándose el caso de que la casilla no contenga ningún símbolo como un caso especial de símbolo, llamado ‘blanco’). El cabezal, cuando está situado sobre un símbolo en una casilla, puede borrarlo y escribir otro.

También, en cada etapa en la que el cabezal está en una casilla, dicho cabezal está en un estado concreto de entre los de un conjunto finito de posibles estados.

Intuitivamente, estos estados codifican de forma matemática abstracta el tipo de subtarea que está realizando el cabezal (por ejemplo, ‘buscar una cadena de tres símbolos 1 seguidos’, o ‘borrar todos los símbolos 2, desplazándose hacia la izquierda hasta encontrar un símbolo 1’, o ‘calcular la llevada en una suma binaria de dos bits’, o ‘contar el número de treses en un conjunto de casillas consecutivas precedidas y seguidas por un símbolo en blanco’. Como dijo el propio Turing, los estados simulan matemáticamente ‘estados de la mente’ en los que puede estar una persona al hacer los cálculos (el mío, particularmente, suele estar en una playa tropical con un Daiquiri).

La fuerza impulsora que anima el cotarro viene del hecho de que el cabezal, al estar en un estado concreto en una casilla con un símbolo determinado, puede borrar el símbolo y escribir otro, desplazarse una casilla a la derecha o a la izquierda, o cambiar a otro estado. Esto se codifica mediante una serie de ‘instrucciones’ que serían, como si dijéramos, el ‘software’ de la máquina de Turing. Estas instrucciones son cuádruplas, donde las dos primeras componentes de cada cuádrupla son el estado y el símbolo leído, la tercera componente puede ser o bien el nuevo símbolo escrito o una D que indicará moverse una casilla a la derecha o una I que indicará moverse una casilla a la izquierda. La cuarta componente indica el nuevo estado al que pasa la máquina.

Por ejemplo, si los posibles estados son s0, s1 y s2 y los posibles símbolos son ‘blanco’, 0, 1 y si la máquina está en el estado s0 sobre una casilla que contiene el símbolo 1 y hay una cuádrupla (s0,1,D,s2), entonces el cabezal se mueve una casilla a la derecha (sin alterar el símbolo 1 de la casilla antigua, ya que es una instrucción ‘de desplazamiento’ y no ‘de sobreescritura’) y termina en el estado s2. Si, por ejemplo, la máquina está en el estado s1 sobre una casilla que contiene el símbolo 0 y si hay una cuádrupla (s1,0,1,s0), la máquina borra el 0 y escribe un 1 en su lugar y cambia de estado (como el agua) a s0.

Una vez que una cuádrupla hace su magia, se vuelven a examinar todas las cuádruplas hasta ver a cuál le toca actuar ahora y se repite el proceso hasta siempre o hasta que se llegue a un estado de parada, lo que antes suceda (en algunas formulaciones se admiten varios estados de parada, e incluso en algunas otras la máquina para cuando no hay ninguna cuádrupla en el ‘programa’ cuyas dos primeras componentes son el estado actual de la máquina y el símbolo leído, respectivamente. Hablando informalmente, cuando la máquina no sabe qué hacer).

Para que no haya ambigüedad, se pide también que no haya dos cuádruplas distintas con las mismas dos primeras componentes, es decir, que no haya dos acciones distintas a tomar cuando, en un estado concreto, el cabezal lee un símbolo concreto.

Huelga decir que la máquina de Turing no es, ni puede ser, una máquina física real de las que se le puede caer a alguien en el pie, ya que presupone una cinta infinita dividida en infinitas casillas, lo cual exigiría papel a cascoporro. Además, cuando Turing la ideó ni siquiera existían los ordenadores en el sentido actual del término. Por el contrario, es una estructura matemática que permite estudiar las preguntas realizadas al comienzo (excepto la de comprar el ordenador) y muchas otras más.

Dos de los tópicos analizados con las máquinas de Turing son los siguientes: el primero, saber si se puede construir una “máquina de Turing universal” que simule cualquier otra máquina de Turing, es decir, que si codificamos inicialmente en la cinta de la máquina universal de forma apropiada las cuádruplas de un ‘programa’ concreto, la máquina se comporte igual a como lo haría una máquina de Turing con ese ‘programa’. El propio Turing demostró que eso es fácil de conseguir y es lo que justifica la opinión no escrita de que lo que se puede hacer con un ordenador también se puede conseguir con otro, aunque sea de otra marca con características distintas, procesador diferente y con otro sistema operativo. Con la idea de máquina universal Turing fue un adelantado a la idea moderna de computador multiusos que según el programa que introduzcamos puede realizar una tarea u otra completamente distinta.

El otro tópico planteado por Turing es el “problema de la parada” y consiste en saber si se puede hallar una máquina de Turing en la que, si se le da como entrada el conjunto de cuádruplas (codificado adecuadamente) de otra máquina de Turing, determine si la otra máquina llegaría a detenerse en algún momento si la ejecutáramos o, si por el contrario, seguiría ejecutándose hasta que Don Limpio se deje melena. Para algunos programas concretos es fácil saber si van a terminar o no, pero Turing probó que la respuesta al problema de la parada para cualquier programa de entrada arbitrario es negativa y no se puede determinar usando una máquina de Turing si otra máquina va a terminar su ejecución en algún momento. Aunque no lo voy a desarrollar, es interesante señalar que el razonamiento de Turing para demostrar la irresolubilidad del problema de la parada se basa en el argumento diagonal de Cantor, del que ya se habló en [7] y que permitía probar que el conjunto de los números reales no es numerable; ya ven que el argumento diagonal de Cantor lo mismo sirve para arreglar un roto que un descosido.

Si se han quedado con ganas de saber más sobre máquinas de Turing pueden consultar el capítulo 5 del libro [14] y, si quieren conocer más cosas sobre la obra y las muchas contribuciones de Turing (entre ellas, la de salvar la vida de miles de personas durante la Segunda Guerra Mundial gracias a haber descifrado el código enigma), les recomiendo que lean [5].

1.2.El que busca, halla

Si, por el contrario, los elementos de la lista tienen algo de estructura adicional, más concretamente que estén ordenados14, entonces otro gallo canta y hay algoritmos mucho más rápidos y eficientes.

En la tabla del Algoritmo 2 en la página siguiente se puede ver la descripción del algoritmo de búsqueda binaria en pseudocódigo.

Hagamos ahora el análisis del algoritmo:

Primeramente, observamos que los sucesivos valores de i y j señalan los índices de los extremos izquierdo y derecho, respectivamente, de las sublistas que nos van apareciendo, que van quedando anidadas cada una de ellas en la que la precede.

El algoritmo termina, ya que en cada etapa del bucle ‘mientras’ de la instrucción 3, la diferencia j − i, siendo ≥ 0, se va reduciendo estrictamente, por lo que en algún momento tendrá que, o bien haberse encontrado el elemento a, o hacerse i > j. Si, no contentos con saber que termina, queremos asegurarnos de que termina ‘rápido’16, observemos que, en caso de que se ejecute la instrucción 7, como , el nuevo valor de j − i, que es k − 1 − i, es menor o igual que la mitad del antiguo menos 1 y, en caso de que se ejecute la instrucción 9 (o sea, que a > ak), como , el nuevo valor de j − i, que es j − k − 1, es menor que la mitad del antiguo luego, después de hacer r etapas desde el comienzo del algoritmo, el número de elementos de la sublista es menor que y se tendrá que siempre que n < 2r, lo cual ocurre cuando r es mayor que el logaritmo en base 2 de n y esto pasa ‘pronto’, ya que el logaritmo en base 2 (¡y en cualquier otra base!) es aproximadamente proporcional al número de cifras de n17.

El algoritmo va bien incluso en el caso de que el elemento a no esté en la lista, ya que entonces llega un momento en el que i > j y se sale del bucle ‘mientras’19, con lo que se ejecuta la instrucción 13 y el algoritmo devuelve el valor 0, que nos indica la no pertenencia del elemento a la lista.

Para saber más sobre los aspectos matemáticos de los algoritmos pueden leer [12] y, sobre la historia de su implementación en dispositivos físicos computacionales, [11].

1.3. Ejercicios

1. Buscar en la literatura matemática e informática tres ejemplos de algoritmos clásicos.

2. Utilizar el algoritmo visto para la resolución de sistemas compatibles determinados de ecuaciones lineales con igual número de ecuaciones y de incógnitas para resolver el sistema:

3. Modificar el Algoritmo 1 visto en el texto para que se pueda aplicar con un número de ecuaciones y de incógnitas arbitrario que sea válido tanto si el sistema no tiene solución (incompatible) como si tiene solo una (compatible determinado) o más de una (compatible indeterminado).

4. Utilizar el algoritmo del problema anterior para decidir si los siguientes sistemas son compatibles y, si lo fueran, dar la solución:

a) 

b) 

c) 

5. Usar el algoritmo de búsqueda binaria para encontrar la posición del número 6 en la lista:

6. Encontrar, utilizando el algoritmo de búsqueda binaria, la posición de la palabra ‘lista’ en la lista:

‘afortunadamente’, ‘desde’, ‘el’, ‘inicio’, ‘la’, ‘lista’, ‘mantiene’, ‘mucho’, ‘orden’.

7. Deducir del algoritmo visto en el texto que el problema de resolver un sistema de ecuaciones lineales compatible determinado está en P, es decir, tiene una complejidad polinomial respecto al tamaño de la entrada.

8. Concluir del algoritmo de búsqueda binaria que el problema de encontrar un elemento en una lista está en P, en el sentido de que tiene una complejidad polinomial respecto a la cantidad de cifras del número de elementos de la lista.

10. Expresar el máximo número de pasos a realizar con el algoritmo visto de resolución de sistemas de ecuaciones lineales y el de búsqueda binaria en la forma O(nk).

11. En el algoritmo de búsqueda binaria se pide que, ya de partida, los elementos de la lista estén ordenados. Bueno sería, por lo tanto, disponer de algún algoritmo de ordenación que ponga a tiro la lista. Pensar algún algoritmo que tome como entrada una lista y devuelva como salida la lista ordenada. Rómpanse la cabeza21 para que el algoritmo sea lo más eficiente posible, en el sentido de que no haya que dar demasiados pasos. Esta estrategia tiene sentido cuando se van a hacer muchas búsquedas en la lista ordenada, para que nos cunda el esfuerzo de realizar la tarea de ordenación.

1 Problemas matemáticos, se entiende; por supuesto, no le van a servir para encontrar las llaves o quitarse de encima a ese cuñado pesado. Bueno, esto último quizá sí, si le cuenta con detalle algún algoritmo.

2 Es bien sabido que lo inventó algún vasco.

3 El que no se cumpliera lo primero comprometería el tiempo libre disponible de la persona que programa o ejecuta el algoritmo, y la falta de lo segundo pondría en entredicho su credibilidad profesional.

4 O, por lo menos, de los pocos afortunados, entre los que no se cuenta el autor, a los que el sueldo les da ocasión y oportunidad de hacer transacciones electrónicas.

5 Puestos a generalizar, nos valdría un cuerpo arbitrario, como los que se estudiaron en [7].

6 En lo casos como este, en los que el número de filas es igual al número de columnas, se dice que es una matriz cuadrada.

7 O en sus casas, o en cualquier otro sitio que estén.

8 Sí, el valor de ak, r ha cambiado, ¿por qué creían que se llamaba variable, si no?

9 No obstante, como ya dije, es fácil hacer algunas variaciones en el método de Gauss, manteniendo la idea básica, para tratar con casos más generales en los que el sistema pueda no tener solución o tener más de una solución.

10 ¿A dónde se van? A ningún sitio, siguen ahí pero, como diría Bart Simpson, se han multiplicado por cero, por lo que es como si no estuvieran.

11 Que les suele parecer que mucho al principio.

12 Tarea apta tan solo para fakires.

13 Llamada, en lenguaje más técnico, búsqueda exhaustiva.

14 Pueden ser números reales y que el orden sea el orden numérico habitual, o palabras y que el orden sea el orden alfabético usual (también llamado orden lexicográfico) ‘de diccionario’ en el que toda palabra que empieza por ‘a’ va antes que cualquier palabra que empieza por ‘b’, etc. y, si dos palabras empiezan por la misma letra, se ordenan de acuerdo a la segunda y así sucesivamente.

15 Que se lo digan, si no, al rey que se quedó a dos velas con el pago a Sissa, inventor del ajedrez.

16 ¡Imagínense qué drama si fuera disminuyendo de unidad en unidad y n fuera 100000000000000000000! Por suerte, no va ser así.

18 Y yo un Ferrari, pero eso es otra historia.

19 Pruébenlo con un ejemplo pequeño y lo verán.

20 Por razones que saltan a la vista.

21 ¡No literalmente!

Capítulo 2

Un número no basta

2.1. Navegando por el espacio

A diferencia de las magnitudes escalares, que se determinan por un número real, positivo, negativo o nulo, están las magnitudes vectoriales, representadas por vectores. Intuitivamente, estos se suelen indicar mediante una flecha en el plano o en el espacio tridimensional , con un origen1 y una punta2. A esto se le suele llamar vector fijo y, cuando se permite a los vectores fijos trasladarse en el plano o en el espacio manteniendo su dirección y su sentido, a las clases de equivalencia así formadas3 se les llama vectores libres.

Esto, en el fondo, es una visión demasiado estrecha y restrictiva de lo que son los vectores y se suele explicar también diciendo que son magnitudes que no quedan caracterizadas por tan solo un número, y que se necesita dar para definirlas un número no negativo, llamado el módulo del vector, así como su dirección y sentido. Ejemplos de magnitudes vectoriales en física son la velocidad, la aceleración y el momento lineal.

Otra forma de entender intuitivamente los vectores es como cantidades que no tienen una sola dimensión y que se pueden descomponer como una combinación de múltiplos de cantidades similares en algunas direcciones prefijadas, de forma que el vector en sí es el resultado de dichas acciones conjuntas4.

Esta forma de ver los vectores es intuitivamente atrayente, pero dicho de forma tan poco concreta carece de rigor matemático. La definición rigurosa es que los vectores son los objetos de una estructura que satisface los axiomas de espacio vectorial que daremos a continuación:

El punto se suele omitir en la multiplicación en K, denotando los productos de elementos del cuerpo por yuxtaposición para no recargar la notación.

Cuando se sobreentiende cuál es el cuerpo K que se está considerando se omite la K, de nuevo por no recargar la notación, y se habla simplemente de espacio vectorial en vez de K-espacio vectorial.

También se suele omitir el punto en la ley de composición externa, denotándola simplementa por yuxtaposición. Esto genera ambigüedad, ya que entonces se denota por yuxtaposición tanto la ley de composición externa como la multiplicación en K, pero esto no es grave, puesto que normalmente se sabe por el contexto qué operación es la que se está considerando en cada caso.

Esta definición deja un poco frío al principio, pero es la que abarca la esencia de la vectorialidad y enseguida se acostumbra uno a ella en cuanto se ven unos pocos ejemplos7.

A los elementos del cuerpo K se les llama escalares y a los elementos del conjunto V se les llama vectores. Habitualmente se suele tomar como cuerpo , o , en cuyo caso se dice que es un espacio vectorial racional, real o complejo, respectivamente, pero la definición es válida para cualquier cuerpo y, en particular, pueden ser también cuerpos finitos8.

Veamos ejemplos, ejemplos, ejemplos...

2.2. El subespacio ocupa poco espacio

Al igual que ocurre con otras estructuras algebraicas, también para espacios vectoriales nos interesa estudiar las subestructuras:

Definición 2.2.1.Sea V un K-espacio vectorial. Un K-subespacio vectorial de V es un subconjunto W de V que satisface las dos siguientes propiedades:

1.  

(W, +) es subgrupo de (V, +)21,

2.  

λυ ∈ W ∀λ ∈ K, ∀υ ∈ W.

Al igual que ocurría con los espacios vectoriales, cuando no hay ambigüedad respecto al cuerpo K que se está considerando se suele decir simplemente subespacio vectorial en vez de K-subespacio vectorial.

Si W es un K-subespacio vectorial de V, entonces la suma en V induce una suma en W, y la ley de composición externa · en K × V induce una ley de composición externa · en K × W y W, con estas operaciones, es un K-espacio vectorial. Es realmente esta estructura de K-espacio vectorial lo que es un K-subespacio vectorial y no solo el subconjunto W, aunque en la definición se hable de un subconjunto de V.

Una caracterización más compacta del concepto de subespacio es la siguiente:

Proposición 2.2.1.Sea V un K-espacio vectorial y sea W ⊆ V. Entonces, W es K-subespacio vectorial de V si y solo si se cumple:

1.  

0V ∈ W,

2.  

v + w ∈ W ∀v, w ∈ W,

3.  

λv ∈ W ∀λ ∈ K, ∀v ∈ W.

Demostración. Es evidente que, si W es K-subespacio vectorial de V, entonces se cumplen 1 y 2, por ser (W,+) subgrupo de (V,+), y se cumple la condición 3 porque esta no es más que la parte 2 de la definición de subespacio vectorial.

Recíprocamente, supongamos que se satisfacen 1, 2 y 3. Al darse 3 (que, como ya he dicho, es igual a la condición 2 de la definición de subespacio, solo falta probar que (W,+) es subgrupo de (V,+). Como, por hipótesis, se dan 1 y 2, únicamente queda demostrar que el opuesto de un elemento de W está en W. Si v ∈ W entonces, por 3, (−1) · v ∈ W, y por la parte 4 de la Proposición 2.1.1, se tiene que (−1) · v es el opuesto de v.

Hay también otra caracterización útil de la noción de subespacio:

Ejemplos 2.2.1.

1. Si V es un K-espacio vectorial, entonces es sencillo ver que {0V} y V son K-subespacios vectoriales de V. Estos se llaman subespacios triviales.

2. El K-espacio vectorial Vn del cuarto de los Ejemplos 2.1.1, formado por los polinomios de K[X] de grado a lo sumo n, es un K-subespacio vectorial del espacio vectorial K[X] del tercero de los Ejemplos 2.1.1, que es el de todos los polinomios de grado arbitrario. Para demostrarlo, observamos que:

24.

Claramente:

Si:

entonces:

3. El -espacio vectorial del sexto de los Ejemplos 2.1.1 es un -subespacio vectorial del -espacio vectorial del quinto de los Ejemplos 2.1.1. Para probarlo, utilizamos que la función nula es continua en (a,b) y que, si y f, g son continuas en (a,b), es un resultado bien conocido que tanto f + g como λf son funciones continuas en (a,b).

4. Análogamente, el -espacio vectorial del séptimo de los Ejemplos 2.1.1 es un -subespacio vectorial del -espacio vectorial del ejemplo anterior. Esto es así porque, evidentemente, la función nula es derivable en (a,b) y, de nuevo, es bien conocido que si λ ∈ y f, g son funciones derivables en (a,b), entonces tanto f + g como λf son derivables en dicho intervalo. La misma argumentación muestra que también es -subespacio vectorial de .

Definiremos ahora el K-subespacio vectorial generado por una familia de vectores25:

Definición 2.2.2.Si V es un K-espacio vectorial y S es una familia de vectores de V, entonces el K-subespacio vectorial de V generado por S es:

La siguiente proposición justifica el nombre de ‘subespacio’ generado por S:

En la teoría de los espacios vectoriales (también llamada álgebra lineal) es fundamental el concepto de combinación lineal de un número finito de vectores31:

Definición 2.2.3.Sea V un K-espacio vectorial, y v1, ..., vn una familia de n vectores. Una combinación lineal de dichos vectores es un vector de la forma:

λ1v1 + ... + λnvn,

con λ1, ..., λn ∈ K32.

Usando esta terminología se ve que < S> es el conjunto de todas las posibles combinaciones lineales de un número finito (pero arbitrario) de vectores de S.

< v1, ..., vn>

en vez de:

< {v1, ..., vn} >.

En este caso es evidente que, sin perder generalidad, podemos tomar las combinaciones lineales de exactamentev1, ..., vn33, de forma que:

En particular, cuando S tiene un solo elemento: