Métodos numéricos, cálculo de raíces mediante método de la bisección

En este ejemplo se presenta el método de la bisección para calcular las raíces de una ecuación de una variable.

Enunciado del problema

Supongamos que tenemos una función continua f definida en el intervalo [a, b], con f(a) y f(b) de signos distintos. Entonces por el corolario V.1 del Teorema del Valor Intermedio, existe un punto c, a < c < b, tal que f(c) = 0. Aunque el procedimiento sirve para el caso en el que f(a) y f(b) tienen signos opuestos y hay más de una raíz en el intervalo [a, b], por simplicidad se supondrá que la raíz en este intervalo es única.

Corolario V.1

Si f ∈ C[a, b] asume valores de signo opuesto en los extremos de un intervalo [α, β], es decir, f(α) · f(β) < 0, entonces el intervalo contendrá al menos una raíz de la ecuación f(x) = 0; en otras palabras, habrá al menos un número c ∈ (α, β) tal que f(c) = 0.

Resolución:

Para la resolución de estos problemas vamos a requerir la librería cexprtk de Python que nos va a permitir interpretar las funciones mátematicas a partir de Strings, la importamos de la siguiente manera:

import cexprtk as cx

Ahora vamos a definir una función que haga uso de la librería que acabamos de importar para evaluar las expresiones matemáticas en un unto dado.

def comp(exp, point, var="x"):
   return cx.evaluate_expression(exp, {var:point})

Definiremos tres funciones para calcular las raíces mediante el método de la bisección, que se van a diferenciar por los parámetros que reciben y validaciones que realizan así:

1. bisectionFull: Esta función recibe cuatro parámetros, la función que se va a evaluar, el intervalo en el que se va a evaluar la función, el número de veces que se va a ejecutar el método y la tolerancia para determinar el cálculo de la raíz. Las valicaciones se hacen o bien sobre la cantidad máxima de veces qe se va a ejecutar el método o la tolerancia, el que se cumpla primero.
2. bisectionSteps: Esta función recibe también la función a evaluar, el intervalo de evaluación y la cantidad de veces que se va a repetir el proceso. No se recibe ni valida la tolerancia. Aquí solamente se valida la cantidad de veces a repetir el método.
3. bisectionTol: Esta función recibe la función a evaluar, el intervalo de evaluación y la tolerancia. Aquí solamente se valida la tolerancia para encontrar la raíz. Se usa esta función por defecto con la tolerancia 0.0001 por defecto en caso de que no se defina ni la cantidad de pasos o la tolerancia.

Función bisectionFull

def bisectionFull(exp, interval, steps, tol):
   a = interval[0]
   b = interval[1]
   for i in range(steps):
     mean = (b-a)/2
     c = a + mean
     resC = comp(exp, c)
     if resC == 0:
       print(f"Se encontró la raíz [{c}] en la iteración [{i+1}]")
       break
     if mean < tol:
       print(f"Se encontró la raíz [{c}] en con el valor [{mean}] menor que la tolerancia [{tol}] en la iteración [{i+1}]")
       break
     if comp(exp, a) > comp(exp, c) > 0:
       a = c
     else:
       b = c
   else:
     print(f"No se pudo encontrar el valor de la raíz luego de las [{steps}] iteraciones")

Función bisectionSteps

def bisectionSteps(exp, interval, steps):
   a = interval[0]
   b = interval[1]
   for i in range(steps):
     mean = (b-a)/2
     c = a + mean
     resC = comp(exp, c)
     if resC == 0:
       print(f"Se encontró la raíz [{c}] en la iteración [{i+1}]")
       break
     if comp(exp, a) > comp(exp, c) > 0:
       a = c
     else:
       b = c
   else:
     print(f"No se pudo encontrar el valor de la raíz luego de las [{steps}] iteraciones")

Función bisectionTol

def bisectionTol(exp, interval, tol=0.0001):
   a = interval[0]
   b = interval[1]
   mean = tol+1
   c = 0
   i = 0
   while mean > tol:
     i += 1
     mean = (b-a)/2
     c = a + mean
     resC = comp(exp, c)
     if resC == 0:
       print(f"Se encontró la raíz [{c}] en la iteración [{i+1}]")
       break
     if mean < tol:
       print(f"Se encontró la raíz [{c}] en con el valor [{mean}] menor que la tolerancia [{tol}] en la iteración [{i}]")
       break
     if comp(exp, a) > comp(exp, c) > 0:
       a = c
     else:
       b = c
   else:
     print(f"No se pudo encontrar el valor de la raíz para la tolerancia [{tol}]")

Ahora vamos a definir la función bisection que serña la puerta de entrada ara el cálculo de las raices en las funciones previamente definidas. En esta función se van a realizar validaciones de datos, para que no sean vacíos o nulos. También se verificará que el producto de los resultados de la función evaluada en los puntos del intervalo sea menor a cero.

Se verificará también que la expresión ingresada sea válida, en caso de no cumplir estos requisitos se lanzará una excepción en la que se indica el requerimiento que no se h acumplido. Si los requisitos se cumplen, se validarán los parámetros recibidos para enviar a resolver el problema en alguna de las funciones previamente definidas. La función se define de la siguiente manera:

def bisection(exp, interval, steps=0, tol=0):
   if not exp:
     raise Exception("El valor de exp debe ser diferente de nulo o vacío")
   elif not interval or len(interval) < 2:
     raise Exception("El valor de interval debe ser diferente de nulo o vacío")
   elif steps < 0 or steps == None:
     raise Exception("El valor de interval debe ser mayor que 0 y diferente de nulo")
   elif tol < 0 or tol == None:
     raise Exception("El valor de tol debe ser mayor que 0 y diferente de nulo")
   else:
     print(f"Se va a evaluar la expresión [{exp}]")
   try:
     if comp(exp, interval[0]) * comp(exp, interval[1]) > 0:
       raise Exception(f"No se puede ejecutar el método con el intervalo {interval}")
   except:
     raise Exception(f"No se pudo evaluar la explresión [{exp}]")
   if steps > 0 and tol > 0:
     bisectionFull(exp, interval, steps, tol)
   elif steps > 0 and tol == 0:
     bisectionSteps(exp, interval, steps)
   elif tol > 0 and steps == 0:
     bisectionTol(exp, interval, tol)
   else:
     bisectionTol(exp, interval, tol)

Con esto tendremos definida la funcionalidad de nuestro algoritmo completo, ahora vamos a definir datos ejemplo para probar el funcionamiento del algoritmo:

exp = "6x^2 - 8x"
interval = [0, 5]
steps = 2000
tol = 0.0001
bisection(exp, interval, steps)

La salida de la ejeución de nuestro algoritmo se muestra en la siguiente imagen:

Ejemplo cálculo de distancias, euclideana, de manhattan y de chebyshev

En este ejemplo se presenta la resolución de algunos ejercicios matemáticos para calcular la distancia entre dos puntos.

Distancia euclideana

La distancia euclideana entre dos puntos n dimensionales se define de la siguiente manera:

Para la resolución de estor problemas vamos a requerir la librería math de pyrhon la cual vamos a importar:

import math

Ahora para resolver el problema de la distancia euclideana definimos la siguiente función:

def euclidean(x,y):
   total = 0
   for i in range(len(x)):
     diff = x[i] - y[i]
     total = total + math.pow(diff, 2)
   return math.sqrt(total)

Distancia de manhattan

La distancia de manhattan entre dos puntos n dimensionales se define de la siguiente manera:

La función a continuación corresponde al algoritmo que calcula la distancia de manhattan

def manhattan(x,y):
   total = 0
   for i in range(len(x)):
     diff = x[i] - y[i]
     total = total + abs(diff)
   return total

Distancia de chebyshev

La distancia de chebyshev entre dos puntos n dimensionales se define de la siguiente manera:

La función a continuación corresponde al algoritmo que calcula la distancia de chebyshev:

def chebyshev(x, y):
   diffs = []
   for i in range(len(x)):
     diffs.append(abs(x[i] - y[i]))
   return max(diffs)

PONIENDOLO TODO JUNTO...

Ahora vamos a crear una función que nos permita validar que los dos vectores tienen la misma dimensión, es decir el mismo número de elementos. Esta recibirá los dos arreglos y validará la cantidad de elementos así:

def validateParams(x,y):
   if len(x) != len(y):
     return False
   return True

Para dinamizar la elección de el método a utilizar crearemos una función que reciba tres parámetros, el vector x, el vector y, y un string indicando la función a utilizar para calcular la distancia. Además, en caso de que no se especifique el nombre del método a utilizar se tomará por defecto el método euclideano.

Hay que tomar en cuenta que el nombre puede ser escrito incorrectamente, por eso haremos uso de la funcionalidad raise de Python para lanzar una excepción indicando que elk nombre ha sido mal escrito.

La función quedaría de la siguiente manera:

def distance(x, y, method='euclidean'):
   if not validateParams(x,y):
     return 0
   if method == 'euclidean':
     return euclidean(x, y)
   elif method == 'manhattan':
     return manhattan(x, y)
   elif method == 'chebyshev':
     return chebyshev(x, y)
   else:
     raise Exception("Debe seleccionar uno de los métodos [euclidean, manhattan, chebyshev]")

Ahora es tiempo de probar nuestros algoritmos, para lo cual definiremos dos vectores de la siguiente manera:

x = [9,3,5,3,-8]
y = [4,21,-5,7,11]

Ahora llamaremos a nuestra función de entrada distance con cada uno de los métodos e imprimiremos los resultados por consola:

print( f"Distancia euclideana: {distance(x,y,'euclidean')}")
print( f"Distancia de manhattan: {distance(x,y,'manhattan')}")
print( f"Distancia de chebyshev: {distance(x,y,'chebyshev')}")

El resultado de la ejecución se muestra en la siguiente imagen:

Calcular la edad de una persona con su fecha de nacimiento

En este ejemplo se explica el uso de la librería datetime de Python para manejo de fechas.

Enunciado del problema

Se requierer calcular la edad en años de una persona que ingresa su fecha de nacimiento por teclado en el formato mm/dd/aaaa es decir el día, el mes y el año.

Ejemplo:

Entrada: 31/03/2000

Salida: La edad es: 20 años

Resolución:

Para resolver este ejercicio primero importaremos datetime y date de la librería datetime de Python

from datetime import datetime
from datetime import date

Necesitamos definir la forma en la que vamos a recibir la fecha de nacimiento de la persona, para lo cual definimos una variable que contenga el formato en el que recibiremos la fecha

date_format = '%d/%m/%Y'

Ahora definiremos una variable que va a almacenar el año de la fecha actual:

now = date.today().year

Definimos la función age(stringDate) que recibirá la fecha en formato string. Como la fecha que hemos recibido es del tipo string debemos transformarla a fecha utilizando datetime, como pueden existir errores al momento de que el usuario ingrese la fecha, vamos a capturar una posible excepción mediante un bloque try-except: datetime>i se logra capturar la fecha de manera correcta, nos quedaremos con la parte solamente de la fecha llamando a la función date() y luego recuperaremos el año de la fecha de nacimiento, haciendo uso de la función strftime de datetime. El código quedaría de la siguiente manera:

def age(stringDate):
   try
     birthDay = datetime.strptime(stringDate, date_format).date()
     birthYear = int(birthDay.strftime('%Y'))
     return now - birthYear
   except:
     print("La fecha ingresada no contiene el formato requerido (dd/mm/aaaa)")
     return 0

Lo que nos faltaría es asignar en una variable la fecha en formato string que vamos a recibir por teclado, lo haremos con el siguiente código

stringDate = input('Ingrese su fecha de nacimiento (31/03/2000)\n')

Ahora para probar que funciona imprimiremos por consola un mensaje que nos indicará la edad devuelta por la función, a la que pasaremos la fecha capturada por teclado:

print(f"La edad es: {age(stringDate)} años")

El resultado de la ejecución del programa lo visualizamos en las siguientes imágenes cuando es exitoso y cuando se ha capturado la excepción respectivamente.

Ejemplo del uso del módulo y división exacta en Python

En este ejemplo se muestra el uso de los operadores aritméticos módulo y división exacta en Python, además se hace uso de funciones y llamadas entre ellas, y se trabaja con fragmentos (slice) de los elementos de un arreglo.

Enunciado del problema

Se nos entrega un arreglo de numeros enteros que representar el tiempo en milisegundos, se nos pide calcular la suma de todos estos valores y representarlos en otro arreglo de enteros de los cuales el primer elemento contendrá el número de días, el segundo elemento contendrá en número de horas, el tercer elemento contendrá el número de minutos, el cuarto elemento contendrá el número de segundos y el quinto elemento contendrá el número de milisegundos.

Si un tiempo es negativo, se lo contará como 0 milisegundos, si un tiempo es nulo o vacío también contará como 0 milisegundos.

Ejemplo:

Entrada: [65647440, 199644521]

Salida: [3, 1, 41, 31, 961]

Resolución:

Para resolver este ejercicio primero definiremos una variable que contenga los factores que permiten transformar milisegundos a segundos, minutos horas y días en ese oren, entonces tendremos:

factors = [1000, 60, 60, 24]

Ahora definiremos una funcion que nos permita calcular la suma de todos los tiempos que se nos proporcionan en el arreglo de entrada, esta función realizará las siguientes acciones:

1. Inicialiar la variable total en 0 que es en donde se van a sumar los tiempos
2. Validar si el arreglo de tiempos times que se recibe es diferente de vacío o nulo, en caso de serlo retornamos 0
3. Recorremos el arreglo de tiempos en un bucle
4. Validamos si el cada valor de tiempo recibido es diferente de nulo o diferente de 0
5. Le sumamos a total el valor de tiempo recibido siempre que este sea positivo, caso contrario no sumamos nada
6. Una vez que se procesaron todos los elementos del arreglo retornamos la suma de los tiempos

La función quedaría de la siguiente manera:

def sumTimes(times):
   total = 0 # 1
   if not times: # 2
     return 0
   for time in times: # 3
     if time: # 4
       total = total + time if time > 0 else total # 4
   return total # 5

Ahora definiremos una función que nos permita calcular el valor de cada factor de conversión, por ejemplo, si queremos calcular los días que tiene un tiempo dado en milisegundos debemos realizar la operación milisegundos / (1000 * 60 * 60 * 24), esta función recibirá un arregño con los valores para calcular el factor de conversión y quedaría de la siguiente manera:

def calculateFactor(factors):
   total = 1
   for factor in factors:
     total = total * factor
   return total

La última funcion que vamos a definir será la que calcula el valor de los días, horas, minutos, segundos y milisegundos existentes en la suma de todos los tiempos que se nos han proporcionado, esta función realiza las siguientes tareas:

1. Definimos la variable values en la que almacenaremos los valores calculados a partir del tiempo en milisegundos
2. Guardamos en una variable el resultado de la suma de todos los tiempos que se nos han proprocionado
3. Validamos que el tiempo total en milisegundos sea diferente de 0
4. Si el tiempo total es diferente de 0, greamos un bucle descendente que inicie en el tamaño de los factores factors que en nuestro caso es de 4 y vaya disminuyendo hasta 0 con un paso de 1, es decir vamos a tener el bucle que toma los valores 4,3,2,1
5. Calculamos el factor de conversión para cada unidad tomando solamente los elementos necesarios del arreglo de factores, por ejemplo para calcular el factor de los días usamos todo el arreglo [1000, 60, 60, 24], para calcular el factor de horas usamos el arreglo hasta la posición del factor para días [1000, 60, 60] y así hasta que el arreglo ya no tenga elementos
6. Agregamos al arreglo de valores la división exacta del tiempo total en milisegundos para el factor de conversión
7. Utilizamos el módulo para calcular el resto de la división, que corresponderá al tiempo restante luego de haber quitado la unidad superior, es decir si calculamos los días, el resto será las horas que quedaron luego de calcular el total de días que existían en el tiempo en milisegundos
8. Una vez que hayamos procesado todos los factores del arreglo factors agregamos a values el ultimo resto que corresponderá a los milisegundos luego de calcular todas las demás unidades
9. AL final retornamos el arreglo values que contendrá los elementos solicitados

La función quedaría de la siguiente manera:

def calculateValues(times):
   values = [] # 1
   total = sumTimes(times) # 2
   if total: # 3
     for i in range(len(factors),0,-1): # 4
       factor = calculateFactor(factors[0:i]) # 5
       values.append(total // factor) # 6
       total = total % factor # 7
     values.append(total) # 8
   return values # 9

Ahora para probar nuestro código definiremos una variable que contenga el arreglo del ejemplo, luego ejecutaremos la función que calcula los valores y arignaremos el resultado en otra variable la cual imprimiremos por consola para visualizar el resultado.

times = [65647440, 199644521]
values = calculateValues(times)
print(values)

El resultado de la ejecución se puede visualizar en la imagen siguiente la cual coincide con la salida del ejemplo propuesto.

Ejemplo básico del uso de expresiones regulares para encriptar un mensaje

Aquí se presenta un ejemplo en el que se utiliza expresiones regulares de manera básica para manipular una cadena de caracteres con el fin de realizar la encriptación de un mensaje

Enunciado del problema

Se nos ha solicitado desarrollar una nueva forma de encriptar comuniacciones. Básicamente, cada vocal de un mensaje de entrada tendrá que estar precedida por alguna cadena de caracteres llamada llave (key).
Debemos escribir una función que reciba dos parámetros de tipo cadena (String): el primero sera la llave, y el segundo el mensaje. La función debe retornar una cadena (String).

Ejemplo:

Llave: rfc

Mensaje: A mi me encanta la programación!

La función debería retornar: rfcA mrfci mrfce rfcencrfcantrfca lrfca prrfcogrrfcamrfcacrfción!

La letra y no será considerada una vocal y tampoco las vocales que contengan acentos serán tomadas en cuenta.

Deberemos tomar en cuenta que si el mensaje es nulo o vacío, se debe retornar una cadena vacía. Si la llave es nula o vacía, entonces se deberá usar la cadena por defecto DCJ.

Resolución:

El desarrollo del ejercicio lo realizaremos con los siguientes fragmentos de código

#Importamos la librería para expresiones regulares
import re

Definimos un patrón para nuestra librería de expresiones regulares indicandole que queremos buscar en este caso las vocales

pattern = re.compile("[aeiouAEIOU]")

Ahora definimos nuestra función de encriptación en la cual vamos a realizar las siguientes tareas:

1. Validamos si el mensaje recibido es diferente de nulo o vacío, caso contrario retornamos un string vacío y finalizamos la ejecución
2. Validamos si la llave recibida es diferente de nulo o vacío, caso contrario le asignamos una cadena por defecto
3. Buscamos en el mensaje todas las coincidencias de las vocales que definimos en la expresión regular de nuestro patrón, y creamos una lista con esas coincidencias
4. Eliminamos los elementos duplicados de la lista de coincidencias
5. Recorremos esa lista reemplazando las coincidencias en el mesaje original por la clave antes de la coincidencia
6. Retornamos el mensaje encriptado

def encript(key, message):
  if not message: # 1
    return ""
  if not key: # 2
    key = "RFC"
  matches = pattern.findall(message) # 3
  matches = list(dict.fromkeys(matches)) # 4
  for match in matches: # 5
    message = message.replace(match, f"{key}{match}")
  return message # 6

De esta manera tendremos nuestra función lista para encriptar un mensaje. Para realizar pruebas ingresaremos el siguiente fragmento de código para validar la encriptación del mensaje que se planteó en el ejemplo en el que realizaremos las siguientes tareas:

1. Definir una variable con la clave "rfc"
2. Definir una variable con el mensaje "A mi me encanta la programación!" para encriptarlo
3. Definir una variable con el resultado de la encriptación del ejemplo
4. Guardar en una variable el resultado de la encriptación que devuelve la función que hemos creado
5. Validar si el mensaje encriptado con la función es igual al que nos muestran en el ejemplo, e imprimir un mensaje para saber si coinciden o no.

key = "rfc" # 1
message = "A mi me encanta la programación!" # 2
result = "rfcA mrfci mrfce rfcencrfcantrfca lrfca prrfcogrrfcamrfcacrfción!" # 3
crypted = encriptMessage(key, message) # 4
if crypted == result: # 5
  print("Los mensajes encriptados coinciden")
else:
  print("Los mensajes encriptados NO coinciden")

Como nuestra función está bien codificada, esperamos un mensaje de éxito como se muestra en la imagen a continuación:

Ejemplo de manejo de módulo para horas y minutos

Enunciado del problema

Preparar un código simple para evaluar o encontrar el tiempo final de un periodo de tiempo dado, expresándolo en horas y minutos. Las horas van de 0 a 23 y los minutes de 0 a 59. El resultado debe ser mostrado en la consola.
Por ejemplo, si el evento comienza a las 12:17 y dura 59 minutos, terminará a las 13:16.
Pista: utilizar el operador % puede ser clave para resolver el ejercicio

Para resolver este problema debemos solicitar dos valores, la hora de inicio del evento y la duración para lo cuál usaremos el siguiente código:

startEvent = input("Ingrese hora de inicio del evento (hh:mm): \n")
durationEvent = input("Ingrese la duración del evento (hh:mm): \n")

Una vez que tenemos nuestros valores procedemos a realizar las siguientes acciones

• Recuperamos las horas y los minutos de la hora de inicio, haciendo un split del string ingresado y convirtiendo los valores en números

• Recuperamos las horas y los minutos de la duración del eventosiguiendo la misma lógica anterior

startHour, startMinute = [int(value) for value in startEvent.split(":")]
durationHour, durationMinute = [int(value) for value in durationEvent.split(":")]

Ahora con estos valores vamos a calcular la hora de finalización del evento para lo cual realizamos los siguientes pasos:

• Calculamos el total de minutos sumando los minutos del inicio del evento, más los minutos de la duración

• Validamos si la cantidad de minutos es mayor o igual que 60
• Si es mayor que 60 calculamos el total de horas sumando las horas de inicio del evento más las horas de la duración más 1 y calculamos la cantidad de minutos obteniendo el módulo en base 60 del total de minutos
• Si es menor que 60 calculamos el total de horas sumando las horas de inicio del evento más las horas de la duración

Entonces el código sería el siguiente:

endMinutes = durationMinute + startMinute
if endMinutes>=60:
   endHour = startHour + durationHour + 1    endMinutes = (endMinutes % 60)
else:
   endHour = startHour + durationHour

De esta manera ya tendremos calculada la hora de finalización del evento y la podemos imprimir como se muestra:

print(f"La hora de fin es: {endHour}:{endMinutes}")

El ejemplo de la ejecución en la consola se vería así: