TIPOS DE ALGORITMOS
Algoritmo de Factorización de enteros o División por tentativa
La división por tentativa es el algoritmo de factorización de enteros más sencillo y fácil
de entender.
Dado un entero compueston (a lo largo de este artículo,n será "el entero a factorizar"),
la división por tentativa consiste en intentar dividirn entre todo número primo menor o
igual a
. Si se encuentra un número que es divisor den, en división entera, ese
número es un factor den.
Algoritmo de Euclides
El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común
divisor (MCD). Fue originalmente descrito por Euclides en su obraElem entos. El
algoritmo de Euclides extendido es una ligera modificación que permite además
expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene
aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la
computación entre otras. Con unas ligeras modificaciones suele ser utilizado en
computadoras electrónicas debido a su gran eficiencia.
divisor (MCD). Fue originalmente descrito por Euclides en su obraElem entos. El
algoritmo de Euclides extendido es una ligera modificación que permite además
expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene
aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la
computación entre otras. Con unas ligeras modificaciones suele ser utilizado en
computadoras electrónicas debido a su gran eficiencia.
Algoritmo original de Euclides
En la concepción griega de la matemática, los números se entendían como magnitudesgeométricas. Un tema recurrente en la geometría griega es el de la conmensurabilidadde dos segmentos: dos segmentos (números)AB yCD son conmensurables cuandoexiste un tercer segmentoPQ el cual cabe exactamente un número entero de veces enlos primeros dos, es decir,PQ «mide» (mensura: medida) a los segmentosAB yCD.
No cualquier par de segmentos es conmensurable, como encontraron los pitagóricos
cuando establecen que
no es un número racional, pero en el caso de dos segmentos
conmensurables se desea hallar la mayor medida común posible.
Euclides describe en la proposición VII.2 de sus Elementos un método que permite
hallar la mayor medida común posible de dos números (segmentos) que no sean primos
entre sí, aunque de acuerdo a la época tal método se explica en términos geométricos, lo
que se ilustra en la siguiente transcripción.
hallar la mayor medida común posible de dos números (segmentos) que no sean primos
entre sí, aunque de acuerdo a la época tal método se explica en términos geométricos, lo
que se ilustra en la siguiente transcripción.
Algoritmo de Euclides tradicional
Al dividira entreb (números enteros), se obtiene un cocienteq y un residuor. Es
posible demostrar que el máximo común divisor dea yb es el mismo que el deb yr.
Éste es el fundamento principal del algoritmo. También es importante tener en cuenta
que el máximo común divisor de cualquier númeroa y 0 es precisamentea. Para fines
prácticos, la notación mcd(a,b) significa máximo común divisor de a y b
posible demostrar que el máximo común divisor dea yb es el mismo que el deb yr.
Éste es el fundamento principal del algoritmo. También es importante tener en cuenta
que el máximo común divisor de cualquier númeroa y 0 es precisamentea. Para fines
prácticos, la notación mcd(a,b) significa máximo común divisor de a y b
No hay comentarios:
Publicar un comentario