Diseño y construcción de algoritmos

Alfonso Mancilla Herrera, Roberto Ebratt Gómez, José Capacho Portilla

• Editorial: Universidad del Norte
• Año: 2016
• ISBN:
  9789587419122
• Categoría: Ciencia de la computación
• Categoría: Algoritmos de programación

Este libro contiene un compendio detallado y sistemático que sirve para el análisis, diseño y construcción de algoritmos. Los autores describen las reglas básicas para diseñar algoritmos aplicados a cualquier área del conocimiento humano, y mediante la combinación de teoría y ejemplos guían al lector para que identifique los conceptos de datos e información y construya algoritmos, partiendo de primitivas básicas hasta llegar a las más complejas. El texto, en síntesis, privilegia el análisis de problemas para que sean expresados con base en la lógica humana, mediante un conjunto de estructuras de control representativas de la lógica algorítmica. Por ello, se encontrarán aquí diversos niveles de diseño de algoritmos, desde ejercicios iniciales hasta problemas de desafío, que con seguridad permitirán adquirir la destreza necesaria para construir algoritmos y aplicarlos a nivel funcional en distintas áreas del conocimiento.

Capítulo 1

Lógica de programación

1.1 Concepto de Lógica

El desarrollo de la Informática como ciencia que estudia el tratamiento de la información a través de máquinas de procesamiento electrónico de datos al servicio de una sociedad digital y global se basa tanto en la tecnología como en la capacidad racional humana, con el fin de transformar un conjunto de hechos a partir de los cuales se logra deducir a través de la razón humana un conjunto de resultados, que al ser valorados en su condición de verdad pueden ser lógicamente correctos o incorrectos. Lo anterior implica, para el avance informático, tanto el desarrollo tecnológico como el desarrollo de las formas de razonamiento humano.

El ser humano racional tiene su base biológica en el cerebro, como órgano que permite a través del lenguaje utilizar los métodos y principios para distinguir el razonamiento correcto del incorrecto. La capacidad de razonamiento humano se basa en un conjunto de reglas o formas válidas de deducción o inferencia, utilizadas por la civilización griega. El conjunto de reglas mencionado conformaba un sistema de razonamiento, y los griegos “llamaron a este sistema de razonamiento ‘Lógica’” (Dean, 2003, p. 1). El filósofo griego Aristóteles fue el primero en referirse a la noción de lógica en el entendido de que los argumentos derivados de la razón son considerados como útiles para lograr la verdad en una determinada ciencia. Luego el término “lógica”, que etimológicamente se deriva del latín lógica, que a su vez proviene del griego antiguo logike, es usado para referirse a un sistema de razonamiento formal. Es este sistema de razonamiento formal el que se utiliza en la construcción de algoritmos; y es precisamente el sistema de reglas que componen un algoritmo lo que se codifica y se ejecuta en un computador para derivar de dicha ejecución resultados que, en síntesis, se convierten en información útil al usuario.

Los sistemas de razonamiento a través del lenguaje han evolucionado de un razonamiento puramente verbal denominado “lenguaje natural” a razonamiento simbólico o lógica simbólica, justificado por el hecho de que

… en la lógica simbólica la información es representada usando letras y símbolos, similares al Álgebra. La lógica simbólica posibilita un cierto grado de automatización del razonamiento; sin embargo, su motivación original fue el deseo de ser capaz de solucionar un problema lógico a través de “cálculos”, justamente como la respuesta a un problema numérico puede ser calculado usando aritmética. Por esta razón, la lógica simbólica está cerradamente asociada con computadores… (Dean, 2003, p. 2)

Luego, con base en lo anterior, la lógica es una rama de la filosofía que estudia de manera formal las deducciones válidas que se derivan de un sistema de razonamiento fundamentado en un conjunto de reglas. Si el sistema de razonamiento mencionado se expresa en un lenguaje matemático, recibe el nombre de “lógica matemática”; en el caso de que el sistemas de razonamiento utilice un lenguaje simbólico y un conjunto de reglas de inferencia recibe el nombre de “lógica simbólica”; y es precisamente esta última la que a través de los algoritmos conformados por estructuras lógicas ha permitido el desarrollo de la informática. El concepto de lógica simbólica antes mencionado, en su intento por alcanzar una automatización utiliza la algoritmia, a cuya ciencia pertenece el concepto de algoritmo.

1.2 Concepto de algoritmo

1.2.1 Síntesis histórica del desarrollo de los algoritmos

Los algoritmos relacionados con la lógica, y esta, a su vez, teniendo relación tanto con la matemática como con el lenguaje, no pueden ser aislados en su desarrollo histórico, por lo tanto, de la historia de los sistemas numéricos y de los sistemas de alfabetos de soporte a un lenguaje. Las primeras construcciones de algoritmos se remontan a la civilización babilónica (2000-600 a.C.), y están relacionadas con el campo matemático, particularmente en la resolución de ecuaciones y en la utilización del sistema numérico sexagesimal (Base 60 (b₆₀)); sistema heredado de los sumerios (2500 a.C.), cuya ubicación geográfica es el valle del río Euphrates (Irak, sur de Baghdad); sistema que se fundamentó en signos especiales para los números 1, 10, 60, 600 y 3600, de los cual se puede concluir que trabajaban tanto en base 10 como en la base sexagesimal.

Es importante destacar que “… Al comienzo del segundo siglo antes de Jesucristo, los babilonios desarrollaron un sistema de numeración, el cual se mantiene en nuestros días en el uso de los minutos y segundos para el tiempo y en la medida de un ángulo” (Chabert & Barbin, 1999, p. 11).

La necesidad del lenguaje en el proceso de comunicación dentro de las sociedades se hizo inicialmente a través de la descripción de acciones cotidianas utilizando figuras (3000 a.C.), para posteriormente ser simplificada la representación de acciones en símbolos bases para la generación de alfabetos, de lo cual se derivó el lenguaje escrito. “El primer alfabeto verdadero apareció cerca de 1700 a.C. en el Este del Mediterráneo” (Wear et al., 1991, p. 7).

La contribución de la antigua civilización egipcia en el desarrollo de los algoritmos se basa en su sistema decimal, representado a través de símbolos que siendo escritura jeroglífica sirvió para representar palabras (2000 d.C.); “los egipcios también usaron unidades fraccionarias” (Chabert & Barbin, 1999, p. 15), y de esta época data la representación de fracciones como 2/3 y 1/3, a la cual se le llamó ‘la pequeña mitad’.

Teniendo en cuenta que hay muchos algoritmos para la multiplicación, se destaca que la multiplicación en forma de tabla, como se conoce actualmente, tuvo su génesis en diferentes tiempos en la China, la India, el mundo árabe y la zona europea. Las evidencias de las tablas de multiplicar en China datan del año 1450, utilizadas a nivel financiero en la provincia de Zhejiang; por su parte, en Europa la más reciente evidencia del algoritmo de multiplicación aparece “… en un manuscrito en latín, alrededor del año 1300 en Inglaterra en la región de Edward II” (Chabert & Barbin, 1999, p. 25).

El desarrollo del lenguaje a través de la teoría de alfabetos después de su primera aparición se complementó con la creación de los alfabetos etrusco y griego alrededor de los años 800-700 d.C., llegando hasta el antiguo alfabeto romano en el año 600-100 d.C., y finalmente el nuevo alfabeto romano durante los años 400-1500 (a.C.).

En el desarrollo algorítmico de las operaciones aritméticas es importante destacar el ábaco chino por su relación con los cálculos de las operaciones suma, resta y la multiplicación, ubicado históricamente en la segunda mitad del siglo XVI. Las operaciones aritméticas solo fueron posibles con el desarrollo de los sistemas de numeración, cuyo desarrollo fue paralelo al alfabeto, por la necesidad de la sociedad de tener un sistema de conteo; así, el sistema más comúnmente utilizado fue el sistema decimal o en base 10 (b₁₀). En el sistema mencionado, y teniendo como base la unificación de precios y medidas de la antigua dinastía Quin en China (210 d.C.), se utilizaron las decenas, centenas y unidades de mil como cantidades posicionales del sistema decimal, lo cual hizo posible la aparición de fracciones decimales. El sistema de numeración binario o base dos (b₂) tiene como representante en la aritmética binaria a

Leibniz, quien escribió su memoria sobre La Explicación de la Aritmética Binaria en 1703, pero estuvo por más de quince años interesado en un sistema de numeración, el cual fue para él un modelo de lo que llamó una característica universal. (Chabert & Barbin, 1999, p. 11).

El sistema binario tuvo un sistema posicional generalizado construido por el mismo Leibinz en 1666; pero se debe tener en cuenta que realmente el primer sistema de posicionamiento digital se le debe a Thomas Harriot (1560-1621), cuya obra no fue publicada y Leibniz lo realizó de una forma independiente. Es importante destacar que con la creación del sistema binario fue posible reducir la lógica a operaciones mecánicas; y siendo reducida la lógica a estas operaciones con el nacimiento de la máquina para la realización de sumas llamada “máquina de Pascal”, habiendo Leibniz inventado una máquina para la ejecución de las cuatro operaciones aritméticas, este tipo de máquinas precedió a las de computación moderna, entre las cuales se encuentra la de Charles Babbage, cuya identidad es la ‘máquina de diferencias’, inventada por este en 1822. De forma paralela, es importante destacar los siguientes eventos en la evolución de la matemática relacionada con la lógica binaria: el tratamiento matemático a través de los conceptos del cálculo diferencial e integral se le acreditan a Leibniz y Newton entre 1675 y 1687. La introducción del concepto de función matemática se le debe a Euler, quien alrededor de 1748 formalizó los conceptos de la matemática analítica. La definición del Álgebra Lineal se le debe a Johan Carl Friedrich Gauss (1777-1855), a quien también se le atribuyen importantes contribuciones en los campos de Teoría de Números, Estadística, Geofísica y Electrostática, entre otros campos, dentro de los cuales se encuentran importantes algoritmos, como son los casos del cálculo del promedio y...