Matemática discreta con apoyo de software E-Book

Enrique Vilchez Quesada

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

Seitenzahl: 671

Beschreibung

Si desea conocer una serie de contenidos esenciales relacionados con el campo de la matemática discreta, ha llegado al libro indicado. Esta obra cubre los temas de recursividad, relaciones de recurrencia, análisis de algoritmos, relaciones binarias, teoría de grafos, teoría de árboles, máquinas y autómatas de estado finito, y lenguajes y gramáticas. Después de muchos años de experiencia en el aula, el autor brinda en este libro una exposición disruptiva al incorporar una combinación propicia entre la teoría clásica, el desarrollo de una cantidad relevante de ejemplos y el uso de software como un recurso didáctico fundamental. El programa empleado se sustenta en un paquete de uso libre diseñado por el autor, llamado VilCretas, que añade 232 comandos de uso especializado en el área de la matemática discreta al conocido software comercial Wolfram Mathematica. En este sentido, el paquete VilCretas le ofrece distintas herramientas de exploración conceptual y procedimental, lo que le posibilitará la interacción con objetos matemáticos y le favorecerá los procesos de aula basados en la experimentación y el análisis, bajo la premisa de un tratamiento didáctico guiado que le conducirá al autoaprendizaje. También encontrará en esta obra distintos apoyos de mediación multimedial creados por el autor, que buscan mejorar los procesos educativos en un campo científico muchas veces considerado como árido por los estudiante

Leseprobe

Esta obra ha recibido una ayuda a la edición del Ministerio de Cultura y Deporte del Gobierno de España, por el Plan de Recuperación, Transformación y Resiliencia, Financiado por la Unión Europea (NextGenerationEU)

Matemática discreta con apoyo de software

Enrique Vílchez Quesada

Derechos reservados © Alpha Editorial S.A.

Primera edición: 2021

ISBN: 978-84-267-3599-7

Edición: Cristian Vega Arévalo

Portada: Camilo Umaña

Primera edición: MARCOMBO, S.L. 2023

© 2023 MARCOMBO, S.L.

www.marcombo.com

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

ISBN: 978-84-267-3599-7

Producción del ePub: booqlab

ENRIQUE VÍLCHEZ QUESADA

Máster en Tecnología e Informática Educativa. Máster en Entornos Virtuales de Aprendizaje. Licenciado en la Enseñanza de la Matemática. Diplomado en Diseño, Desarrollo y Evaluación de Software Educativo.

Académico con categoría de Profesor Catedrático en la Escuela de Informática de la Universidad Nacional de Costa Rica (UNA), impartiendo los cursos de Estructuras Discretas, Fundamentos de Informática e Investigación de Operaciones, fungiendo como docente y coordinador. Investigador asociado a distintas actividades y proyectos vinculados con el desarrollo de software y de materiales educativos computarizados. Coordinador del área en Ingeniería en Sistemas durante el período 2008-2009. Subdirector de la unidad académica de mayo del 2009 a marzo del 2010. Lector de distintos tipos de trabajos de graduación para optar por el grado de Licenciatura en Informática y Educación Matemática y, de Maestría en Tecnología e Innovación Educativa. A partir del mes de octubre del año 2007, profesor titular de la Escuela de Informática de la UNA.

Primer promedio en la carrera Licenciatura en la Enseñanza de la Matemática de la Universidad Nacional de Costa Rica, durante los años 1995 y 1997. Mención honorífica cum laude en la Maestría en Tecnología e Informática Educativa. Primer promedio en la Maestría en Tecnología e Informática Educativa de la Escuela de Informática de la UNA y de toda la Universidad Nacional de Costa Rica a nivel de posgrado durante el año 2005. Segundo lugar del premio Jorge Volio 2008 del Colegio de Licenciados y Profesores (COLYPRO) en Costa Rica. Miembro asociado del Comité Latinoamericano de Matemática Educativa (CLAME). Mención Honorífica al Galardón Alumni 2019 con Sello Universidad Técnica Nacional de Costa Rica, por el desempeño y trayectoria profesional en la docencia e investigación.

Autor de diversos artículos y libros y, conferencista a nivel nacional e internacional en múltiples congresos relacionados con los campos de matemática educativa, informática educativa y matemática aplicada.

La matemática es la ciencia de la exactitud, la belleza del razonamiento, es la observación abstracta, la magia intelectual que ayuda a explicar el mundo, es además, la inspiración y creatividad que nos enfrenta a nosotros mismos.

A mi esposa Vivita, a mi madre Amparo y a mi hijo Enriquito, por brindarme todos los días de mi vida, los colores de sus gestos y la profundidad de su amor sincero.

A mi colega y amigo Juan Félix Ávila Herrera, quien con sus hábiles observaciones convirtieron en evidente lo no obvio.

A mi asistente Ignacio Monge Salazar, sus excepcionales capacidades humanas e intelectuales han sido un baluarte en la culminación de este libro.

CONTENIDO

Prólogo

1 RECURSIVIDAD

1.1 Introducción

1.2 Propiedades de una recursividad

1.3 Ejemplos de programas recursivos

1.4 Ejemplos de recursividades de cola

1.5 Ejercicios

2 RELACIONES DE RECURRENCIA

2.1 Introducción

2.2 Resolución de relaciones de recurrencia

2.2.1 Método iterativo

2.2.2 Relaciones de recurrencia homogéneas lineales

2.3 Ejercicios

3 ANÁLISIS DE ALGORITMOS

3.1 Introducción

3.2 Enfoque experimental

3.3 Enfoque teórico: notación asintótica O grande

3.4 Enfoque teórico: otras notaciones asintóticas

3.5 Ejercicios

4 RELACIONES BINARIAS

4.1 Introducción

4.2 Representaciones de una relación binaria

4.3 Operaciones con relaciones binarias

4.4 Tipos de relaciones

4.5 Ejercicios

5 TEORÍA DE GRAFOS

5.1 Introducción

5.2 Representaciones para un grafo

5.3 Circuitos en un grafo

5.4 Algoritmo del camino más corto

5.5 Ejercicios

6 TEORÍA DE ÁRBOLES

6.1 Introducción

6.2 Árboles binarios de búsqueda

6.3 Recorridos en un árbol binario

6.4 Árboles generadores

6.5 Árboles de expansión mínima

6.6 Ejercicios

7 MÁQUINAS DE ESTADO FINITO Y AUTÓMATAS

7.1 Introducción

7.2 Máquinas de estado finito

7.3 Autómatas de estado finito determinísticos

7.4 Autómatas no determinísticos

7.5 Ejercicios

8 LENGUAJES Y GRAMÁTICAS

8.1 Introducción

8.2 Lenguajes formales y gramáticas

8.3 Gramáticas regulares y autómatas

8.4 Ejercicios

Solución de los ejercicios

Bibliografía

Apéndice 1: Comandos del paquete VilCretas

Apéndice 2: Tipos de grafos

PRÓLOGO

La matemática discreta o matemática finita proporciona una base de conocimiento teórico-práctico para el estudio formal de áreas vinculadas con la informática o ciencias de la computación, tales como: los sistemas operativos, las estructuras de datos, el análisis de algoritmos y los paradigmas de programación.

La matemática discreta otorga al estudiante los conocimientos instrumentales necesarios para abordar múltiples problemas en ingeniería de la computación, al requerir el análisis sistemático de objetos finitos representables a través de modelos no continuos y modelos contables.

Este libro hace un recorrido de los contenidos teórico-prácticos más importantes relacionados con este campo y enfocado específicamente a alumnos de un curso de matemática discreta dentro del currículo de muchas carreras de ingeniería en informática o ciencias de la computación.

El aporte más transcendental de esta obra en comparación con otros textos clásicos se fundamenta en la formulación de distintos ejemplos y sus soluciones utilizando un paquete de software de uso libre, programado por el autor, llamado: VilCretas. VilCretas es una librería que añade al conocido software comercial Wolfram Mathematica doscientos treinta y tres comandos, constituyéndose en una herramienta didáctica para desarrollar contenidos en el área de la matemática discreta, particularmente en los temas de interés de esta obra, a saber: recursividad, relaciones de recurrencia, análisis de algoritmos, relaciones binarias, teoría de grafos, teoría de árboles, máquinas y autómatas de estado finito y, gramáticas y lenguajes. Cabe mencionar que en [24], el autor de este libro comprobó por medio de un estudio de caso, la efectividad didáctica del paquete VilCretas.

Todos los archivos fuentes del programa Wolfram Mathematica requeridos en las soluciones expuestas en el texto, se encuentran disponibles en la dirección electrónica:

http://www.escinf.una.ac.cr/discretas

Además, el libro ofrece, al alumno o al docente, una serie de materiales complementarios diseñados por el autor, entre ellos:

• El paquete de sofware VilCretas.

• Ocho “cuadernos interactivos” sobre los contenidos de cada uno de los capítulos de esta obra. En este sentido, se entiende un “cuaderno interactivo”, como un archivo en formato PDF con audio incluido, donde el estudiante podrá recibir una explicación complementaria de todo lo abordado. El archivo debe ser abierto utilizando el programa Adobe Acrobat Reader e instalando previamente el plug-in: Adobe Flash Player. Lo anterior, para facilitar el empleo de un menú con diversas herramientas de navegación y controladores.

• Un quiz interactivo por capítulo. Los quices incluyen una serie de preguntas de repaso sobre los conocimientos recibidos con la propiedad de autocalificarse.

• Dos glosarios de comandos, comprendidos como, aplicaciones preparadas con la finalidad de consultar con el formato de un diccionario interactivo, el uso de distintas instrucciones propias del software Wolfram Mathematica y del paquete VilCretas.

• Ocho Webmixes de Symbaloo, que sirven como referencia para el empleo de doscientos treinta comandos de la librería VilCretas.

• Un libro adicional en formato electrónico bajo la licencia Creative Commons: Atribución-NoComercial-SinDerivadas, titulado: “Matemática discreta a través del uso del paquete VilCretas”, donde el autor detalla comando por comando y con ejemplos resueltos, las potencialidades pedagógicas y de investigación de este recurso computacional.

• Aplicaciones en formato de documento computable (CDF: computable document format) para algunas secciones de contenido.

• Presentaciones por capítulo, dirigidas al profesor del curso, como apoyo para impartir sus lecciones, recurriendo como base a este texto. Abra un sitio web: código 1.

Figura 1: Imágenes iconográficas del texto

El libro utiliza tres imágenes iconográficas de importancia, tal y como se muestra en la Figura 1. La “Imagen 1” indica la presencia de un archivo ha de ser descargado en la computadora del lector. La “Imagen 2” señala la existencia de un video que el usuario puede inquirir con el objetivo de obtener una explicación técnica sobre el empleo de algún comando del paquete VilCretas. La “Imagen 3” evidencia que se comparte un sitio web de consulta. Todas las direcciones a los archivos, los videos y los sitios webs vacantes, se pueden descargar de:

www.marcombo.info

Código: MATES23

El PDF disponible en la dirección electrónica anterior, muestra una serie de códigos junto a los cuáles se asocia un archivo de descarga, un video de YouTube, o bien, un sitio web. Cada código se señala de forma explícita en algún lugar de esta obra. Al respecto, el lector, al encontrarse en el texto con un código, debe buscar la dirección URL relacionada con él, para poder recibir el material ampliado correspondiente. Por ejemplo, observe en la página previa, donde aparece:

Se insta al alumno a sumergirse en este apasionante mundo de la matemática finita y particularmente a su estudio mediante el apoyo complementario de software. Bajo esta perspectiva, este libro brinda una refrescante opción asistida por computadora hacia la búsqueda de nuevas metodologías educativas, dentro de un marco pedagógico que, en muchas instituciones de enseñanza superior, ha definido una clara ruta sobre el uso mediado de la tecnología, como un recurso alternativo para apoyar los procesos de aprendizaje.

E. VílchezHeredia, Costa Rica, 2021

Capítulo 1

Recursividad

“La propiedad más importante de un programa es si cumple la intención de su usuario”.

C.A.R. Hoare

1.1 Introducción

En programación el tema de recursividad es muy importante dado que muchos algoritmos en diversas áreas de la informática se basan en este principio y del mismo modo, distintos lenguajes de programación permiten la recursividad al usuario de manera abierta, ejemplo de ello lo constituyen: C++, Python y Wolfram Language.

Si el programador no conoce bien los fundamentos básicos de la recursividad como técnica de trabajo, podría caer en el error de desarrollar un programa recursivo que nunca converja a una solución, o dicho en palabras más sencillas, caer en el error de construir un programa que no ofrezca una salida exitosa.

Existen múltiples ejemplos de programas recursivos, a manera de introducción estudiaremos dos casos, con el objetivo de comprender el concepto y uso de la recursividad.

Un primer ejemplo lo encontramos en el siguiente programa elaborado con el software Wolfram Mathematica:

La función de este código reside en calcular el factorial de un número entero no negativo n. Como el lector recordará si n ∈ IN ∪ {0} el factorial denotado n! se define así:

Nota. Toda recursividad genera una “pila” de llamadas o invocaciones. En algunos programas recursivos estas llamadas no son aprovechadas en las invocaciones posteriores. Si esto ocurre, la recursividad se denomina “recursividad normal o de pila”; en caso contrario, si al realizar una llamada en un programa recursivo se reutiliza la invocación anterior, la recursividad se conoce con el nombre de “recursividad de cola” o “tail recursion” por su denominación en el idioma inglés. Las recursividades de pila tienen el riesgo de provocar un desbordamiento en el tamaño de la pila y con ello ocasionar que el programa tenga un comportamiento insatisfactorio. Por esta razón, las recursividades de cola suelen ser más apropiadas en cuanto al empleo de la memoria del ordenador y también, con relación al tiempo de ejecución. Volveremos sobre este punto más adelante. El programa factoriales ya compartido constituye una recursividad de pila.

Instalación del paquete VilCretas y comando Factoriales

Este libro toma como apoyo un paquete de software elaborado por su autor llamado VilCretas. La librería añade al software comercial Wolfram Mathematica doscientos treinta y tres comandos en el campo de la matemática discreta. Iniciaremos con su uso explicando la manera en cómo se instala.

Descargue un archivo: código 2.

Paquete VilCretas.

Después de ser descargada la última versión del paquete VilCretas, en el software Wolfram Mathematica, se accede al menú Archivo/Instalar, mostrándose la ventana:

En Fuente, se direcciona la ubicación del archivo “VilCretas.m” y se presiona el botón “Aceptar”. En principio no ocurre nada en la hoja de trabajo de Mathematica. Es importante aclarar que por defecto estas hojas de cálculo tienen extensión “nb” y se llaman cuadernos o notebooks. Para tener acceso a los comandos que caracterizan el paquete VilCretas se debe añadir en el cuaderno la instrucción:

Esta línea de código se ejecuta en el software presinando shift+enter. Si produce como respuesta:

$Failed

hubo un error en el proceso y por lo tanto se deben volver a realizar todos los pasos ya descritos. De lo contrario, si no hay ningún retorno, la librería ya estaría disponible para su empleo.

Explicación en video: código 3.

Instalación del paquete VilCretas.

Un primer comando o sentencia de interés del paquete VilCretas se denomina Factoriales. Esta instrucción constituye una implementación del programa 1.1. Por ejemplo:

Lo interesante del comando reside en la posibilidad que brinda para observar su código interno de programación y las ejecuciones paso a paso. De esta forma:

Como se aprecia steps -> True retorna “paso a paso” las llamadas sucesivas del comando Factoriales hasta llegar al caso raíz Factoriales[1].

Descargue un archivo: código 4.

Uso del comando Factoriales.

Explicación en video: código 5.

Empleo del comando Factoriales.

Nota. Desde un punto de vista de aprendizaje las opciones code -> True y steps -> True pueden resultar de mucha ayuda para el estudio individual del lector. La mayor parte de las instrucciones de VilCretas vinculadas con este capítulo, incorporan estas dos opciones.

Por otra parte, el autor de este texto ofrece un segundo libro bajo la licencia Creative Commons: Atribución-NoComercial-SinDerivadas, donde se detalla por capítulo, la utilización y potencialidades de cada una de las instrucciones del paquete VilCretas, esto a través del uso de ejemplos. Se recomienda su consulta como una clara guía en la profundización de empleo de esta librería.

Descargue un archivo: código 6.

Libro “Matemática discreta a través del uso del Paquete VilCretas”.

Un segundo ejemplo de una recursividad que particularmente recibe el nombre de relación de recurrencia, tema que se estudiará más a profundidad en el capítulo 2 de este texto, se enuncia a continuación:

A la sucesión numérica que produce esta relación de recurrencia se le conoce con el nombre de sucesión de Fibonacci, llamada así en honor a su creador, el matemático italiano Leonardo de Pisa más conocido en su época como Fibonacci.

En el año 1202, Fibonacci escribió una obra denominada Liber abaci donde formuló un famoso problema de parejas de conejos que planteaba: “¿cuántas parejas de conejos obtendremos al final de un cierto año, si empezando con una pareja, cada pareja produce cada mes una nueva pareja que puede reproducirse al segundo mes de existencia?” [3]. De este problema se origina la sucesión de números de Fibonacci. Curiosamente esta secuencia numérica 1, 1, 2, 3, 5, 8, 13, 21, 34, ... presenta interesantes aplicaciones en la naturaleza. Se cree que el patrón de crecimiento en las hojas de una planta genera la sucesión de números de Fibonacci, que la cantidad de espirales de una piña o un girasol, en ambos sentidos, coincide con un número de esta sucesión, que el número de pétalos de una flor corresponde a un número de Fibonacci, y del mismo modo, que el número de antepasados de una abeja macho o zángano en su árbol genealógico en cada uno de sus niveles, forma la sucesión de números de Fibonacci. Lo anterior, solo por citar algunos casos.

En Wolfram Mathematica la relación de recurrencia de los números de Fibonacci se puede crear así:

Al correr, por ejemplo, el cálculo de fibonacci[5] el programa en la primera iteración establece que fibonacci[5]=fibonacci[4]+fibonacci[3], a su vez, al determinar el valor de fibonacci[4] se concluye que fibonacci[4]=fibonacci[3]+fibonacci[2], luego, fibonacci[3]=fibonacci[2]+fibonacci[1], finalmente como fibonacci[1]=fibonacci[2]=1, en las llamadas sucesivas hacia arriba se obtiene que fibonacci[3]=2, fibonacci[4]=3 y fibonacci[5] =5, devolviéndose como resultado este último valor. También, de una forma más directa, la relación de recurrencia que construye los elementos de la sucesión de Fibonacci se podría desarrollar en Wolfram Language así:

Se insta al lector a analizar su funcionamiento.

Mathematica cuenta también con el comando Fibonacci[n] que calcula el nésimo número de Fibonacci. Por ejemplo, si se desea hallar el quinto término de esta sucesión con ese comando, en el software se procede así:

La instrucción Fibonacci[n] es nativa del programa Mathematica y no de la librería VilCretas. Wolfram Mathematica se caracteriza por contar con más de seis mil instrucciones distribuidas en distintos campos de conocimiento. Se invita al lector a consultar el siguiente glosario que explica el funcionamiento de las instrucciones más comúnes de uso, contenidas en el software Mathematica. Asimismo, en este glosario de comandos se han incorporado las instrucciones propias del paquete VilCretas.

Descargue un archivo: código 7.

Glosario de comandos de Mathematica y VilCretas.

Comando NFibonacci

En el paquete VilCretas se encuentra disponible el comando NFibonacci que corresponde a la implementación anterior de fibonacci, con la particularidad de poseer las mismas opciones code -> True y steps -> True de la instrucción Factoriales. De esta manera:

Descargue un archivo: código 8.

Uso del comando NFibonacci.

Explicación en video: código 9.

Empleo de la instrucción NFibonacci.

Algo esencial, al programar recurriendo a la técnica de recursividad, consiste en tener la certeza de que el programa recursivo finaliza, es decir, el código de programación diseñado generará como salida de manera factible, un resultado que tiende a converger y no a diverger. En este sentido, se entenderá la palabra “convergencia” como la tendencia de un programa a proporcionar una salida durante su tiempo de ejecución, en caso contrario, se dice que es “divergente”. Un ejemplo de un comportamiento divergente lo encontramos en un ciclo que nunca sale del conjunto de iteraciones que produce. Cuando un programa nunca sale de una estructura de control de repetición, no brinda ninguna respuesta consistente al usuario y por consiguiente, es divergente (a este común error se le denomina enciclamiento). Iniciaremos la siguiente sección formalizando las propiedades de cualquier recursividad.

1.2 Propiedades de una recursividad

Toda recursividad se invoca o se llama así misma a través de una definición base, ejecutándose las invocaciones una cantidad finita de veces.

Cada llamada en el proceso produce una pila. Las invocaciones se detendrán hasta obtener una serie de reglas recursivas que definen el o los casos iniciales, también conocidos como casos raíz. Esta condición o condiciones, determinan la salida de la pila, en cuya ausencia, el programa continuaría llamándose así mismo de forma indefinida (algo similar a lo que ocurre en un enciclamiento).

Muchos algoritmos vinculados con el área de la matemática discreta, como el lector comprobará más adelante, son descritos en pseudocódigo por medio de definiciones recursivas. En informática esta práctica es muy frecuente pues permite abreviar el significado preciso de un procedimiento.

Nota. Los dos ejemplos de recursividades ya desarrollados, el factorial y la sucesión de Fibonacci, podrían hacer pensar al estudiante que un programa recursivo solamente se emplea para realizar un cálculo; sin embargo, esto es una falacia, pues también, se pueden utilizar para llevar a cabo un proceso.

2) [Compare] Tome a v y compare con “a”, si son iguales finalice “dato encontrado” de lo contrario vaya al paso 3.

El procedimiento es de naturaleza recursiva pues en el paso 3, la instrucción: “llame nuevamente a este algoritmo”, da cuenta de una autoinvocación del método. La idea consiste en ir comparando “a” con cada uno de los elementos de L, de “atrás hacia adelante”. Por otra parte, sabemos que en algún momento terminan las llamadas del proceso pues L es una lista finita de datos y por consiguiente, será reducida a vacío en la peor situación (si “a” no es un dato de L). En Wolfram Mathematica una implementación del algoritmo descrito, corresponde a:

Module en Wolfram Language facilita la generación de un entorno de programación donde es posible inicializar variables y/o funciones locales. En dato fue necesario crear la variable Lista con la intención de ir eliminando cada vez, su último elemento, en caso de ser distinto de “a”. Last y Delete son operadores de listas propios de Mathematica. El primero retorna el último dato de Lista y el segundo efectúa su eliminación.

Comando Dato

El paquete VilCretas cuenta con la instrucción Dato. Ésta constituye la misma implementación compartida en el método dato anterior, otorgando la posibilidad al usuario de observar el código de la función y una búsqueda paso a paso, recurriendo a las opciones code -> True y steps -> True, respectivamente. Así:

Descargue un archivo: código 10.

Empleo del comando Dato.

Figura 1.1: Ayuda de Wolfram Mathematica

Explicación en video: código 11.

Uso de la instrucción Dato.

Nota. Todos los comandos del paquete VilCretas y de Mathematica propiamente, presentan una opción de ayuda al usuario. Por ejemplo, si en un notebook se presiona shift+enter al escribir: ?Dato, se devuelve como salida una descripción sobre el uso de la instrucción Dato, tal y como se muestra en la figura 1.1. Es decir, colocando un signo de pregunta antes del nombre de un comando en Wolfram Mathematica, se accesa a la ayuda proporcionada por el software.

Existe una gran diversidad de problemas que pueden ser resueltos bajo una lógica recursiva. En la siguiente sección se detallan otros intersantes ejemplos al respecto.

1.3 Ejemplos de programas recursivos

Esta sección muestra al lector un compendio de ejercicios seleccionados que utilizan la recursividad como una técnica de trabajo. Se espera con ello, lograr un mayor nivel de profundización sobre este tema.

Ejemplo 1.1

Elabore un programa recursivo para calcular la potencia an, a ∈ R, n ∈ N∪{0}, sabiendo que:

¿Qué ocurre si n pertenece al conjunto de los números enteros?

Figura 1.2: Desbordamiento en el tamaño de la pila

Solución:

Un programa diseñado en Wolfram Language para estos efectos corresponde a:

La recursividad corre apropiadamente si n es un número entero positivo o cero, sin embargo, al sustituir por un valor entero negativo, por ejemplo, si se ejecuta Potencia[5,-4], Mathematica retorna lo que se aprecia en la figura 1.2. Este Out[ ], se ocasiona por un desbordamiento en la pila de llamadas, al no obtenerse nunca las condiciones de salida. La siguiente función OtraPotencia, consiste en una modificación de Potencia para solventar el cálculo con cualquier exponente entero (considerando negativos):

Descargue un archivo: código 12.

Archivo de resolución del ejemplo.

Comando PotenciaPos

VilCretas cuenta para su consulta con la instrucción PotenciaPos que implementa el programa recursivo del ejemplo 1.1. Al igual que otros comandos del tema de recursividad, PotenciaPos facilita las opciones code -> True y steps -> True. Por ejemplo:

Se insta al lector a explorar el comando PotenciaNeg similar al anterior, pero con la funcionalidad de calcular potencias con un exponente cero o negativo.

Descargue un archivo: código 13.

Uso de las instrucciones PotenciaPos y PotenciaNeg.

Explicación en video: código 14.

Empleo del comando PotenciaPos.

Explicación en video: código 15.

Utilización del comando PotenciaNeg.

Comando Sumatoria

La librería VilCretas contiene una sentencia que automatiza la construcción de un programa recursivo correspondiente al cálculo de una sumatoria. El comando se denomina Sumatoria. La solución del ejemplo 1.2, se podría revisar mediante el uso de Sumatoria como prosigue:

Nota.Sumatoria también permite el cálculo paso a paso para un valor específico de n.

Se recomienda al alumno explorar esta posibilidad consultando la ayuda del comando mediante ?Sumatoria.

Descargue un archivo: código 17.

Uso de la sentencia Sumatoria.

Explicación en video: código 18.

Empleo de la instrucción Sumatoria.

Ejemplo 1.5

Elabore un programa recursivo que sume los dígitos de un número entero no negativo n.

Solución:

La lógica recursiva implicada requiere en la primera llamada, tomar al entero n inicial y extraer de él su primer dígito d. El estudiante debe recordar para ello, el uso del operador módulo. En Wolfram Mathematica, Mod[n, 10] devuelve el residuo de la división n ÷ 10, es decir, el primer dígito d que posee n. Ese valor en nuestro programa recursivo, se va a sumar literalmente a la siguiente invocación donde se utilizará para esa llamada, el número entero resultante de eliminar el dígito ya acumulado, dicho número corresponde a . El procedimiento se repite (con cada llamada), hasta que el valor de se reduce a cero. En otras palabras, la condición de salida de la recursividad se sustenta en haber recorrido y acumulado en la suma, cada uno de los dígitos de n. Una implementación de esto en Mathematica se presenta a continuación:

Nota. La librería VilCretas cuenta con el comando SumaDigi correspondiente a la función recursiva SD anterior, con la particularidad de posibilitar la visualización de la pila de llamadas. Se invita al lector a utilizar la opción steps -> True de SumaDigi.

Descargue un archivo: código 21.

Archivo de resolución del ejemplo.

Ejemplo 1.6

Sean n y m enteros positivos con n ≤ m. Realice un programa recursivo que muestre todos los múltiplos de n menores o iguales a m.

Solución:

En este ejemplo se desean obtener todos los múltiplos de un entero positivo n, para ello se debe multiplicar n por un contador iniciando en 1. El contador requerido no se puede colocar dentro del programa recursivo de interés, pues de ser así, en cada llamada, se inicializaría esa variable en 1, ocasionando un efecto no deseado. Por esta razón, y en general, cuando se necesita un contador en un programa recursivo, una forma de trabajo, reside en colocar el contador como un parámetro más de la función. Veamos:

El estudiante debe notar que en Mult[5,36] no fue necesario incluir el valor del contador pues por defecto inicia en 1. La salida de este código se ha sustentado en enviar a imprimir en pantalla el múltiplo correspondiente. Otra solución, consistiría en ir añadiendo los múltiplos en una lista, en lugar de imprimirlos cada vez. En Wolfram Mathematica esta alternativa se implementaría como sigue:

Nota.Append es una instrucción propia del software Mathematica encargada de añadir al final de una lista sobre la que se opera un elemento. A este respecto, recibe dos argumentos, la lista y el término a agregar. También, Mathematica presenta el comando Prepend con un funcionamiento similar a Append, con la diferencia de añadir al inicio de la lista lo deseado y no al final. Se insta al lector a modificar el programa OtroMult usando Prepend en sustitución de Append.

Descargue un archivo: código 22.

Archivo de resolución del ejemplo.

Sentencia Multiplos

El paquete VilCretas cuenta con la instrucción Multiplos similar a la función OtroMult expuesta en el ejemplo 1.6. El aporte principal de Multiplos reside en ofrecer al usuario las opciones acostumbradas code -> True y steps-> True. Por ejemplo:

Descargue un archivo: código 23.

Uso del comando Multiplos.

Explicación en video: código 24.

Empleo del comando Multiplos.

Ejemplo 1.7

Construya un programa recursivo que genere en una lista, todos los divisores de un entero positivo n.

Solución:

Para resolver este ejercicio se empleará una forma de razonamiento similar a la establecida en el ejemplo 1.6. Es decir, se requiere el uso de un contador con valor inicial 1 y valor final n, esto con el objetivo de ir extrayendo todos los divisores de n. Luego:

En este caso, a diferencia de lo resuelto en el ejemplo 1.6, se ha inicializado la lista en vacío al añadirla como un parámetro más de la función. El lector puede corroborar el funcionamiento de divisores, ejecutando:

Nota. El programa recursivo divisores se puede mejorar en tiempo de ejecución, analizando los posibles divisores hasta la mitad del número n y agregando a la última lista obtenida ese valor. Lo anterior se justifica pues ningún divisor propio (divisores menores que n) será mayor que n ÷ 2.

El programa recursivo mejorado corresponde a:

En el capítulo 3 se verificará que Otrodivisores es más eficiente en comparación con divisores.

En la librería VilCretas el comando Divisores constituye una herramienta de comprobación para visualizar la pila de llamadas de Otrodivisores.

Descargue un archivo: código 25.

Archivo de resolución del ejemplo.

Ejemplo 1.8

Elaborar una recursividad que convierta un número n en base binaria a base diez.

Solución:

La conversión de binario a decimal se puede efectuar tomando de manera recursiva cada dígito binario y multiplicando ese valor por dos elevado a un contador que debe inicializarce en cero. De esta manera, se acumula en una suma, en cada llamada, el producto ya citado con la nueva invocación. Es importante que el alumno observe en esta lógica de programación, una combinación de las ideas presentadas en la solución de los ejemplos 1.5 y 1.6. Veamos:

Se sugiere correr en Wolfram MathematicaBToD[1111] cuya salida es igual a 15.

Descargue un archivo: código 26.

Archivo de resolución del ejemplo.

Ejemplo 1.10

Investigue en qué consiste el algoritmo quicksort para ordenar los elementos de una lista L. Implemente en Wolfram Mathematica esta recursividad.

Solución:

Quicksort se desarrolló en el año de 1960 por el científico inglés C.A.R. Hoare [11]. En la actualidad es uno de los algoritmos de ordenación más difundidos por su nivel de efectividad. El algoritmo se basa en las siguientes instrucciones [4]:

1) Se selecciona un elemento de la lista L a ordenar denominado pivote.

2) Se ordenan los elementos alrededor del pivote de tal forma que a su izquierda queden los datos menores que él y a su derecha los mayores. La lista se divide en dos sublistas: la de la izquierda y la de la derecha con respecto al pivote.

3) Se llama a este algoritmo para ordenar la sublista izquierda.

4) Se llama a este algoritmo para ordenar la sublista derecha.

Nota. El paso 2 tiene diversas formas de implementación, la más usual consiste en jugar con dos índices i y j, donde el parámetro i se mueve de izquierda a derecha y el parámetro j de derecha a izquierda. El razonamiento se basa en comparar los elementos L [i] y L [j] de la lista L con el pivote. Si L [i] es mayor que el pivote y a su vez L [j] es menor que el pivote, se intercambia L [i] con L [j] y se repite el proceso incrementando i y decrementando j hasta que los índices i y j se cruzan.

Un programa en Wolfram Mathematica que implementa el algoritmo quicksort es el siguiente:

Se observa en el código, que el elemento pivote se toma como un punto central de la lista L, esto lo permite el cálculo de Floor[(begin+end)/2] que representa la parte entera de la suma de la posición mínima con la posición máxima de la lista, dividido entre dos. Veamos un ejemplo de uso:

En Mathematica, lo mostrado en el Out[ ] anterior con negrita, toma en realidad un color azul, indicando con ello, en cada llamada de quicksort, cuál es el elemento pivote seleccionado.

El código de quicksort es un poco más elaborado en comparación con los ejercicios anteriores, por lo que se recomienda al lector tener paciencia y perseverancia en su estudio minucioso.

Descargue un archivo: código 28.

Archivo de resolución del ejemplo.

Comando Quicksort

El paquete VilCretas posee una implementación del algoritmo recursivo quicksort a través de la sentencia Quicksort. Ella además de poseer las opciones code -> True y steps -> True, proporciona la posibilidad de ordenar de forma descendente empleando ascendente -> False. Por ejemplo:

No se presenta la salida total por su amplio tamaño, pero se insta al estudiante a generar el Out[ ] completo en el software Wolfram Mathematica.

Descargue un archivo: código 29.

Empleo del comando Quicksort.

Explicación en video: código 30.

Uso de la sentencia Quicksort.

Las recursividades de pila como se señaló en la sección 1.1, no son por lo general muy eficientes. Una alternativa de mejora consiste en utilizar lo que se denomina recursividad de cola o tail recursion (en idioma inglés) tal y como se detalla en la sección que prosigue.

1.4 Ejemplos de recursividades de cola

Las recursividades de cola tienen la ventaja de aprovechar las salidas proporcionadas por las invocaciones anteriores en un programa recursivo, mejorando significativamente el tiempo requerido por el programa para obtener un resultado exitoso y evitando en muchos casos, además, un desbordamiento en el tamaño de la pila de llamadas. A continuación se comparten algunos ejemplos al respecto.

Ejemplo 1.11

Calcule el factorial de un número entero no negativo n mediante una recursividad de cola.

Solución:

En este ejercicio se construirá una función factorial auxiliar que poseerá dos parámetros: el primero controla la salida del programa y el segundo reutiliza la llamada anterior para ir acumulando allí, el resultado deseado del factorial. En Wolfram Mathematica:

Un recorrido paso a paso de la pila de llamadas en factorialesCola se puede obtener al usar la instrucción de VilCretas denominada FactorialesCola. Por ejemplo:

El lector observará que en la última invocación FactorialesAux[0,120], el segundo argumento ya tiene calculado el resultado de 5!. Lo anterior significa que a diferencia de la recursividad de pila desarrollada en la sección 1.1, factorialesCola no requiere realizar una sustitución hacia arriba al darse la condición de salida. Naturalmente, esto ahorra tiempo y recursos en el ordenador.

Nota. Prueba de ello, reside en ejecutar factorialesCola[1500] que sí retorna un cálculo exitoso en comparación con factoriales[1500] donde se manifiesta un desbordamiento.

Descargue un archivo: código 31.

Archivo de resolución del ejemplo.

1.5 Ejercicios

Se insta al estudiante a resolver el conjunto de ejercicios propuestos con el objetivo de complementar su preparación en cada uno de los contenidos relacionados con el tema de recursividad.

Capítulo 2

Relaciones de recurrencia

“Si alguien no cree que las matemáticas son simples, es porque no entienden lo complicada que es la vida”.

John Von Neumann

2.1 Introducción

Las relaciones de recurrencia son sucesiones de números reales enlazados a partir de una ecuación recursiva.

De allí, que toda relación de recurrencia es una recursividad, aunque como se estudió en el capítulo anterior, no toda recursividad corresponde a una relación de recurrencia.

Esta clase de recursividad tiene la importancia de permitir con frecuencia, la resolución de distintos tipos de problemas, consideremos el siguiente ejemplo: suponga que una persona posee una deuda en una entidad bancaria. Si no paga el monto del préstamo al final de cada mes, la entidad le cobra un interés de un 5 % sobre el monto adeudado. Si se asume un préstamo de US $300 dólares, ¿cuánto dinero deberá al cabo de un año si no ha pagado ninguna de las cuotas?

En Wolfram Mathematica:

Es decir, después de un año sin pagar nada al banco, la persona tendrá una deuda acumulada de US $538.757.

Nota. Se ha utilizado el software Mathematica para evaluar a12 puesto que el procedimiento manual devengaría un recorrido muy laborioso hacia atrás, de trece sustituciones. Se aclara al lector que no se ha elaborado un programa mediante el uso de un If como se hizo o se propuso en el capítulo 1, a razón de dar un tratamiento al tema, con un enfoque matemático y no recursivo, aunque desde luego, esto también permitiría obtener el valor de a12. En Wolfram Language una recursividad de cola viable en ese sentido, sería:

En adelante no se empleará ningún programa recursivo en los procedimientos de resolución, pero queda claro al alumno que su utilización es una alternativa correcta.

Descargue un archivo: código 39.

Archivo de resolución.

Definición 2.1

Sea dada una sucesión de números reales a0, a1, a2, a3, . . . Una relación de recurrencia sobre los elementos de la sucesión es una ecuación que relaciona el término an con alguno de sus antecesores a0, a1, . . ., an−1.

La ecuación que determina una relación de recurrencia debe estar sujeta a un conjunto de condiciones iniciales, pues de lo contrario, no habrían casos raíz y como consecuencia de ello, la proposición recursiva no convergerá a ninguna solución.

Nota. Como el alumno irá comprobando poco a poco en la práctica, el número de condiciones iniciales de una relación de recurrencia es igual al número de términos anteriores a n que definen la ecuación recursiva. Dicho valor se llama “orden” de la relación de recurrencia.

En general, por lo tanto, si una relación de recurrencia es de orden dos debe estar sujeta a dos condiciones iniciales, si depende de tres términos anteriores a n (orden tres), debe poseer tres condiciones iniciales, si está en función de cuatro términos anteriores (orden cuatro), integrará en su definición cuatro condiciones iniciales y así sucesivamente.

Las relaciones de recurrencia son recursividades muy útiles pues en muchas ocasiones la solución de un problema resulta más fácilmente representable, por medio de una recurrencia y no de otro tipo de función.

Nota. Claro está, las relaciones de recurrencia en términos informáticos podrían ocasionar un alto costo computacional en tiempo de ejecución. De allí la necesidad de estudiar en este capítulo, métodos que permitan resolver una relación de recurrencia.

Antes de ello, enunciaremos algunos ejemplos orientados a la evaluación y construcción de relaciones de recurrencia.

Otros tipos de ejercicios de interés, consisten en abordar ejemplos donde el objetivo resida en construir una relación de recurrencia que represente la solución de un problema. Veamos.