Clase 14 de 31 • Curso de Introducción al Pensamiento Computacional con Python
Contenido del curso
Lyddon Beni Varje Esteban
Juan David Aguirre
Erika Itzel Hernández López
Edward Rodríguez
Jose Antonio Rojas Ollarves
Juan Esteban Moreno Vergara
Ramón Ruiz
Cristian Antonio García González
Cesar Arturo Castanon Acuna
rusbel bermúdez rivera
Victor Danilo Moreno Martinez
rusbel bermúdez rivera
Karl Behrens Gil
Daniel Barrientos
Francisco Peña
Josue Noha Valdivia
José Rodrigo Arana Hi
Josue Noha Valdivia
José Alberto López Jiménez
David Eduardo Bueno Núñez
Christopher Brian Guzmán Martínez
Camila Andrea Díaz Serrano
Oscar Francisco Trujillo Puentes
Mariano Torres
Maria Guadalupe Diaz Escobar
Manuel Alejandro Hermoso
Carlos Fernando Aguilar González
DANILO RAMIREZ
Carlos Fernando Aguilar González
Christian Sanclemente
Diego Santacruz
Luis Enrique Huamán Quispe
Daniel Quispe
johan Stever Rodriguez Molina
Augusto Eduardo Bonalumi
Nicolas
Pablo Domínguez Durán
Didier Sotto Acosta
Edgar Ocampo
Josue Farley Lopez Carvajal
Vianel Rodriguez
Cristian Daniel Borda Bastidas
Jorge Cruz Perez
Joseph Lázaro Ricardo
Nelson Ricardo Ramírez García
Lo aplicado en esta clase se denomina Métodos Numéricos, el metodo usado en la clase es conocido como método de la bisección, es un tipo de búsqueda incremental en el que el intervalo se divide siempre a la mitad.
Existen diversos métodos que tiene una mejor convergencia para la aproximación a la solución, el mas conocido es el metodo newtoh raphson.
Pueden revisar este libro si les interesa aprender mas sobre Métodos Numéricos
Métodos Numéricos para Ingenieros
Muchas gracias
¡Gracias! Ya estaba buscando algo así.
Nuevamente largo, pero creo yo que claro jeje Espero a alguien le sirva
# numero al que se le calculará la raiz cuadrada objetivo = int(input('Escoge un numero: ')) # margen de error para encontrar esa raiz cuadrada epsilon = 0.01 # valor minimo para calcular largo del conjunto bajo = 0.0 # valor maximo para calcular largo de conjunto. Función max() >> elegirá el valor máximo de los parámetros que le demos; colocamos 1.0 como valor mínimo aceptado (así nos cubrimos de que, por ejemplo, el usuario coloque un valor negativo), y objetivo (valor que nos dará el usuario) alto = max(1.0, objetivo) # aqui generamos el valor medio de nuestro conjunto, a lo cual se puede genera el condicional (if) para elegir la mitad menor o la mitad mayor. respuesta = (alto + bajo) / 2 # para entender esto, lo más fácil es imaginar que el while saltará de un grupo de mitades a otro, dependiendo de la situación, hasta que el grupo se divida lo suficiente como para dar con el objetivo. # el while comienza diciendo que, hasta que la respuesta de con el resultado (con un margen de error de 0.01, es decir epsilon), se hará la iteración del paso 2 de este algoritmo. while abs(respuesta**2 - objetivo) >= epsilon: # si respuesta**2 no es mayor que objetivo, quiere decir que respuesta debe ser mayor (de respuesta para abajo, no nos sirve; nos sirve el rango de respuesta para arriba). # RECORDAR: respuesta es el valor medio del conjunto que estamos analizando (mirar más arriba) if respuesta**2 < objetivo: # como sabemos que de respuesta para abajo no tenemos un valor que nos sirva, actualizamos el piso (bajo) de nuestro conjunto a el valor actual de respuesta. bajo = respuesta # si respuesta**2 es mayor que objetivo, quiere decir que respuesta debe ser menor (de respuesta para arriba, no nos sirve; nos sirve el rango de respuesta para abajo) else: # como sabemos que respuesta para arriba no tenemos un valor que nos sirva, actualizamos el techo (alto) de nuestro conjunto a el valor actual de respuesta alto = respuesta # Saliendo del else, ejecutamos el código para que respuesta (punto medio de nuestro conjunto) se actualice al nuevo conjunto. respuesta = (alto + bajo) / 2 ################################## # Repitiendo este loop, llegará un punto en el que el conjunto sea muy pequeño, y hallaremos la raiz cuadrada. # Los loops necesarios serán mucho menos que si usamos busqueda exhaustiva o aproximacion print(f'La raiz cuadrada de {objetivo} es {respuesta}')
Excelente resumen bro
Gracias por el resumen y la explicación, es muy útil!
Este algoritmo si le gustó más a mi procesador.
Ni que lo digas, ahora siento que mi computadora no se calienta como una tostadora con este nuevo algoritmo.
🎄 Espero y les sirva ver mi codigo solo para entenderle mejor. Les recomiendo ponerlo en su VSC. 🎄 . 🧨 OJO: Todo está en inglés, yo cambié los nombres de las variables. . Here you have my code and how it looks like. .
#Chosen number 9 userNum = int(input("Give me a number: ")) epsilon = 0.01 #epsilon down = 0.0 up = max(1.0, userNum) middle_value = (down + up) / 2 guesses = 1 while abs(middle_value**2 - userNum) >= epsilon: print(f"\n1-. This is the middle value: {middle_value}") print(f"2-. This is the value of middle value^2, squared: {middle_value**2}") print(f"3-. Here is the Middle value^2 ({middle_value**2}) MINUS the user number({userNum}): ---> {abs(middle_value**2 - userNum)}") #print(f"3-. REMEMBER that 'abs' turns a negative number into a positive.☝ ⬆") print(f"4-. down: {down} /// middle value: {middle_value} /// up: {up}\n") if middle_value**2 < userNum: #4 down = middle_value else: #if i^2 > userNum: up = middle_value middle_value = (down + up) / 2 # print(f"*** 🧧 Now the middle_value has been updated to: {middle_value}") print(f"BECAUSE: newest Up({up}) + newest Down({down}) / 2 = {middle_value} 🧧") print(f"*** - After finishing the {guesses} loop.") print(f"*** 🎆 Remember UP is NOT 5 anymore. It changed with the iteration to {up}\n\n\n") guesses += 1 print(f'The square root of {userNum} is {middle_value}') print(f"It took me {guesses} to discover it.")
.
Les comparto este libro https://www.casadellibro.com/libro-metodos-numericos-para-ingenieros/9789701061145/1140185
Hace dos años era profesor de esa materia, conoci platzi buscando una alternativa a matlab y la encontre en python, de hecho este algoritmo viene en uno de los primeros temas, asi como otros metodos, voy a repasar la informacion y espero compartirles algunos slides a manera de tutorial para que los puedan implementar en python, viene paso a paso matematicamente espero hacerlos a manera de tutorial.
Gracias rusbel, excelente material
De nada, si tienes dudas, escríbeme, terminando estos cursos tengo planeado hacer varios tutoriales explicando los temas, creo aportarían valor ya que son matemáticas aplicadas con métodos iterativos con álgebra elemental
Búsqueda Binaria
Cuando la respuesta se encuentra en un conjunto ordenado, podemos utilizar búsqueda binaria. Es altamente eficiente, pues corta el espacio de búsqueda en dos por cada iteración. Los pasos que sigue son:
Para verlo de forma gráfica buscaremos el valor 18 en la lista [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23].
Para realizar un ejemplo práctico crearemos un programa para buscar raíces cuadradas.
objetivo = int(input('Escoge un numero: ')) epsilon = 0.01 # Definimos nuestro margen de error. bajo = 0.0 # Inicializamos la parte baja de nuestra busqueda como 0 alto = max(1.0, objetivo) # Entre el numero que ingresamos y 1 vamos a tomar el mayor valor. respuesta = (alto + bajo) / 2 # Definimos la mitad entre bajo y alto. # Mientras el margen de error sea mayor a epsilon. while abs(respuesta**2 - objetivo) >= epsilon: # Si ((alto+bajo)/2)^2 es menor a nuestro numero objetivo if respuesta**2 < objetivo: # Definimos la parte baja de nuestra busqueda como (alto + bajo)/2 bajo = respuesta # En caso que (alto+bajo)/2 es mayor a nuestro numero objetivo else: # Definimos la parte baja de nuestra busqueda como (alto + bajo)/2 alto = respuesta # Luego definimos nuevamente la mitad entre alto y bajo. respuesta = (alto + bajo) / 2 # Cuando el ciclo ya alcance un error menor a epsilon imprimiremos el resultado. print(f'La raiz cuadrada de {objetivo} es {respuesta}')
Este algoritmo es extremadamente rápido en comparación a los anteriores y esto es justamente lo que lo hace uno de los mas potentes.
Muchas gracias!!! con esa explicación tuya le pude entender!!
Gracias amigo , Excelente muy bien explicado. epsilon ya lo veo mas claro 👁
falta el proceso de repetir el loop con los nuevos valores en bajo/alto, hasta que sea mayor o igual al ipsilon, pero me encantó el diagrama, muchas gracias.
cierto, gracias por el aporte
Se nota en gran medida la pasión del profesor, profes como David son los que denotan la calidad de Platzi.
La busqueda binaria es parecida a cuando tenemos un libro de muchas páginas y queremos encontrar una página en específico sin mirar el índice.
Ejemplo:
También les recomiendo que lean este artículo sobre búsqueda binaria: https://es.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search
el mejor resumen de la búsqueda binaria jajaja más claro no se puede
Que buena analogía
Código con mejor visualización:
import time objetivo = int(input('Escoge un numero: ')) epsilon = 0.000001 bajo = 0.0 alto = max(1.0, objetivo) respuesta = (alto + bajo)/2 num = 0 #numero para contar iteraciones start = time.time() while abs(respuesta**2 - objetivo) >= epsilon: if respuesta**2 < objetivo: bajo = respuesta else: alto = respuesta respuesta = (alto + bajo)/2 num += 1 end = time.time() print(f'Para resolver hizo {num} iteraciones y se demoro {end - start} segundos') print(f'La raiz cuadrada de {objetivo} es {respuesta}')
b
Gracias
Si lo quieres ver con manzanitas:
Sos grande!!! Muchas gracias
Con mucho gusto Danilo. Siempre hay nuevos detalles por descubrir!
Saludos 😀
Entenderlo puede que sea sencillo, pero no importa cuanto te lo expliquen, lo mas importante es lograr hacerlo por sí mismo. Esto realmente es lo complicado.
Escoge un numero: 4 La raiz cuadrada de 4 es 1.9999847412109375 Epsilon: 0.0001 Iteraciones: 16 Inicio: 2020-06-10 22:03:37.193309 Fin: 2020-06-10 22:03:37.193393
Hola Diego, como le hiciste para mostrar en ese formato, la fecha y los milisegundos?
Yo hice asi pero me arroja solo hasta minutos.
fin = time.time() print(f'Para resolver se hizo {num} iteraciones y se demoro {fin - inicio} segundos\nInicio: {time.asctime(time.localtime(inicio))}\nFin: {time.asctime(time.localtime(fin))}')
Dr. Stranger usando el algoritmo anterior
Usando el nuevo algoritmo :)
para saber que tanto se demora tu código corriendo les recomiendo usar :
import time tic=time.time() # aqui va tu código a correr toc=time.time() #para ver cuanto tiempo tardó corriendo: print(' el tiempo que se demoró en correr es:\n ' + str(abs(tic-toc)*1000) + 'milisegundo')
En un momento pensé si no tenía que ser toc - tic, pero después veo que usaste abs(). Estás a un paso adelante jeje. Gracias por el dato
En la linea 4, coloca max(1.0, objetivo). La idea de usar la funcion maximo de esa manera, es que el programa funcione tambien con numeros entre 0 y 1. La razon de esto es que para los numeros de este conjunto, las raices cuadradas son mayor al numero. Matematicamente seria asi: sqrt(x) >= x para todo x perteneciente al intervalo [0, 1] Esta opcion no se esta aprovechando, ya que cuando introduce el input del numero usa int(input(...)) cuando deberia usar float(input...).
Muy buena observación!
Increíble. Encontrar la raíz cuadrada de 44: por aproximación de soluciones tomó 6.633.175 iteraciones, mientras que por búsqueda binaria solo tomó 12 iteraciones.
La razon es que la primera solucion tiene un comportamiento cuadrático, ya que el epsilon al cuadrado hace mas largo el algoritmo mientras el epsilon sea mas pequeño, mientras que la segunda solucion tiene un comportamiento logaritmico (proporcional al resultado logarítmico del tamaño del valor de entrada). Seguramente esto lo va a explicar el profe mas adelante, pero si queres saber mas podes leer este articulo: https://medium.com/@charlie_fuentes/notacion-big-0-para-principiantes-f9cbb4b6bec8
Usé el código de la enumeración y la aproximación para armar un "híbrido": Primero busca la respuesta por enumeración, si no encuentra la respuesta en el dominio de los enteros continúa la búsqueda por aproximación desde el valor entero donde quedó. Eso reduce enormemente el tiempo de ejecución. Luego hice un comparativo entre las 4 formas para hallar la raíz de 5. Los resultados estan en la imagen. A pesar de ganar gran velocidad con la aproximación híbrida la búsqueda binaria es a todas luces superior en desempeño.
al cambiar epsilon a 0.001 no guardo el archivo, esas ultimas ejecuciones utilizaron el nuevo epsilon?
Hola Vianel, el programa ejecutara todo lo contenido hasta la ultima vez que lo guardaste, en este caso no ejecutara la instrucción con un epsilon 0.0001
confirmando a Cristian, asi es, las ultimas ejecuciones fueron sobre la versión previa del programa
Recomiendo también imprimir el respuesta**2, esa impresión me ayudo a entenderlo.
Excelente sugerencia. Me sirvió mucho. Gracias compa 👍
