Video explicativo.

 https://youtu.be/Gnpsz7wmOQY

Jimenez Crismar 28572024

RECURSIVIDAD.

 Universidad Nacional Experimental

De los Llanos occidentales

Ezequiel Zamora

Guasdualito, Edo-Apure

Modulo III: Aritmética entera y Modular.

Modulo IV: Recursividad y grafos.

Docente:

Narvaez Argenis.

Bachiller(s):

Urdaneta Marlys; CI: 28545716

Jimenez Crismar; CI: 28572024

IV Semestre

Ing. Informática.

2021

Modulo III

 Aritmética entera y modular:

Divisibilidad:

      La divisibilidad en las matemáticas se refiere a la propiedad de los números enteros (números sin decimales) de dividirse por otro número entero y que su resultado sea a su vez un número entero. Por ejemplo, los números 3, 6, 9 y 12 tienen divisibilidad por 3, porque cuando divides cada uno de esos números enteros por 3 resultan números enteros: 1, 2, 3 y 4. La operación aritmética para dividir se llama división, que se compone de un divisor y un dividendo. El divisor es el número del total que queremos dividir y el dividendo es el número de partes que queremos saber que caben en el número total (divisor). Algunas de las propiedades que se deben tomar en cuenta para facilitar el ejercicio de la divisibilidad son:

• Los números divisibles solo se componen de números enteros distintos a cero.
• Todos los números son divisibles por 1 y por sí propio.

Algoritmo de Euclides: 

     El algoritmo de Euclides es un método para calcular el máximo común divisor (MCD). Fue escrito por Euclides en su obra magna Elementos. Dicho algoritmo funciona no sólo para los números naturales, sino para cualquier conjunto en el que exista una "división con residuo". A este tipo de divisiones en la que existe residuo se les nombra divisiones euclidianas y a los conjuntos donde se puede definir dicha división se les llama dominios euclídeos. Con lo anterior podemos decir que el algoritmo de Euclides extendido es una ligera modificación del Algoritmo de Euclides 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. Por ejemplo, el conjunto de los números enteros y el de los polinomios con coeficientes racionales son dominios euclídeos porque podemos definir una división con residuo. El algoritmo de Euclides se puede representar con la siguiente proposición:

• Sean \(a \), \(b \) enteros no nulos. Entonces \(MCD(a,b) = MCD(b,r) \) donde \(r \) es el único \(0 < r < b \) tal que existe un entero \(q \) con \(a= bq + r \). Esto es, que \(r \) es el resto de la división de \(a \) por \(b \).

     Esta proposición nos indica que es igual de válido calcular el \(MCD(a,b) \) que el \(MCD(b,r) \), con la ventaja de que \(r \) es un entero de menor tamaño que el original a. Esto es aprovechado por el algoritmo de Euclides para el cálculo del máximo común divisor de dos números enteros. Para calcular el \(mcd \) de dos enteros \(a \) y \(b \) (ambos \(>0 \), suponemos \(a > b \)) se definen \(q_i \) y \(r_i \) recursivamente mediante las ecuaciones:

\[a = bq_1 + r_1 \ \   (0<r_1<b) \] \[b = r_1q_2 + r_2 \ \  (0<r_2<r_1) \] \[r_1 =r _2q_3 + r_3 \ \  (0<r_3<r_2) \] \[.... \] \[r_{k-3} = r_{k-2}q_{k-1} + r_{k-1}  \ \ (0<r_{k-1}<r_{k-2}) \] \[r_{k-2} = r_{k-1}q_k  \ \ (r_k=0) \]. Y de la proposición anterior, se sigue que:

• \[MCD(a,b) = MCD(b,r_1) = MCD(r_1,r_2) = ... = MCD(r_{k-2},r_{k-1}) = r_{k-1} \]

     Además se puede demostrar que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.

Congruencias:

      

      Congruencia es un término usado en la teoría de números, para designar que dos números enteros  tienen el mismo resto al dividirlos por un número natural , llamado módulo; esto se expresa utilizando la notación:

${\displaystyle a\equiv b{\pmod {m}}}$

que se expresa diciendo que: ${\displaystyle a\,}$ es congruente con ${\displaystyle b\,}$ módulo ${\displaystyle m\,}$. De donde se define que dos números ${\displaystyle a\,\textstyle {\text{y}}\displaystyle \,b}$ son congruentes en módulo ${\displaystyle m\,\neq \,0}$ «» (sí y solo si) :

• ${\displaystyle m\,}$ divide exactamente a la diferencia de ${\displaystyle a\,}$ y ${\displaystyle b\,}$

${\displaystyle m\mid a-b}$

o lo que es lo mismo, ${\displaystyle a\,\textstyle {\text{y}}\displaystyle \,b}$ dejan el mismo resto en la división por ${\displaystyle m\,}$. Además, también se puede afirmar que:

• ${\displaystyle a\,}$ se puede escribir como la suma de ${\displaystyle b\,}$ y un múltiplo de ${\displaystyle m\,}$, pues si: ${\displaystyle m\mid a-b}$ » (entonces), ${\displaystyle mk=a-b}$, para algún ${\displaystyle k\in \mathbb {Z} \quad (entonces)\ a=b+km}$

El término congruencia se utiliza además con dos sentidos ligeramente diferentes: por un lado con el sentido de identidad matemática, como ejemplo de este uso tenemos el pequeño teorema de Fermat que asegura que para cada primo ${\displaystyle p\,}$ y cada entero ${\displaystyle a\,}$ no divisible por ${\displaystyle p\,}$ tenemos la congruencia:

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$¹​

Por otro lado se utiliza en el sentido de ecuación, donde aparecen una o más incógnitas, y nos preguntamos si una congruencia tiene solución y en caso afirmativo cuáles son todas sus soluciones, por ejemplo la congruencia ${\displaystyle x^{2}-5\equiv 0{\pmod {11}}}$, tiene solución, y todas sus soluciones vienen dadas por ${\displaystyle x\equiv 4{\pmod {11}}}$ y ${\displaystyle x\equiv 7{\pmod {11}}}$, es decir ${\displaystyle x\,}$ puede ser cualquier entero de las sucesiones ${\displaystyle 11k+4\,}$ y ${\displaystyle 11k+7\,}$. Contrariamente la congruencia ${\displaystyle x^{2}-2\equiv 0{\pmod {11}}}$, no tiene solución.

     La notación y la relación terminología fueron introducidas por Carl Friedrich Gauss en su libro Disquisitiones Arithmetica en 1801. Su utilización se ha extendido a muchos otros entornos en los que podemos hablar de divisibilidad, por ejemplo a polinomios con coeficientes en un cuerpo, a ideales de anillos de números algebraicos, etc.

Resolución de Sistemas de congruencias de números enteros:

      Una congruencia de la forma:

ax ≡ b (mod m)

donde m es un entero positivo, a y b son números enteros y x es una variable entera, se llama congruencia lineal o ecuación de congruencia lineal (lineal por aparecer la variable x como potencia de grado uno, únicamente). Resolver esta ecuación consiste (como en el caso de la aritmética entera) en encontrar todos los enteros x que satisfagan la ecuación diofántica equivalente ax+my=b. En el caso de Z_m, la ecuación tendrá solución si y solo si mcd(a,m)|b , y en este caso tendrá exactamente d=mcd(a,m) soluciones distintas en Z_m de la forma:

x= x0 + (m.t)/d , t=0,1,2,...,d-1

en donde x₀ es una solución particular de la ecuación diofántica ax + my = b. En el apartado dedicado al algoritmo de Euclides se indica como puede utilizarse este algoritmo para calcular una solución particular de una ecuación diofántica.

Sistemas de numeración:

      Un sistema de numeración es aquel que nos representan cantidades numéricas mediante un conjunto de símbolos. La utilidad de los sistemas de numeración en el tema que nos ocupa es determinante.  La razón es que todos los ordenadores utilizan el sistema de numeración binaria para representar la información (no sólo los números).    Dentro de una red cada equipo tiene un identificador único denominado dirección IP y que, para conocerlo en profundidad, necesitaremos conocer su representación decimal y su representación binaria.

Los sistemas de numeración actuales son posicionales, es decir, un símbolo puede tener un significado diferente en función de su posición.  Las características de los sistemas posicionales son las siguientes:

• Se emplea un número finito de símbolos, dígitos o cifras, lo que determina la base del sistema.  Por ejemplo el sistema decimal utiliza los dígitos: 0,1,2,3,4,5,6,7,8,9 para representar los números y como estos símbolos son diez se dice que la base es 10.
• Cada cantidad viene expresada por una secuencia finita de símbolos del sistema.
• La cantidad total expresada se obtiene sumando el valor de cada uno de los símbolos.
• El valor de cada símbolo depende de sí mismo y de la psoción que ocupa dentro de la secuencia de símbolos.  Normalmente tendrá más valor cuanto más a la izquierda se sitúe.  
• Así los dígitos 983 en base 10  que representaremos así 983(10 representan al número 9*10²+8*10¹+3*10⁰ =983.  
• 10110(2 representa el número 1*2⁴+ 0*2³+ 1*2² +1*2¹ +0 *2⁰ = 22(10

Como se puede observar , cuanto mayor sea la base del sistema, mayor será el número de símbolos del alfabeto y menor será el número de cifras necesarias para representar una cantidad.  El mayor número que se puede representar, en una base b, com m dígitos es b^m -1.

      Los sistemas de numeración más usados en informática y, por tanto, en las redes de ordenadores son los siguientes:

• Binario.  La base del sistema es 2. Se utilizan los dígitos 0 y 1.  Se utilizan en todas las máquinas electrónicas digitales ya que éstas solo pueden representar dos estados.  En particular lo utilizan los ordenadores.  Con n dígitos binarios se pueden  representar los enteros comprendidos ne el rango [0, 2ⁿ-1].
• Decimal.  La base del sistema es 10.  Se utilizan los dígitos 0,1,2,3,4,5,6,7,8,9
• Hexadecimal. La base del sistema es 16.  Se utilizan los dígios 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
• Octal. La base del sistema es 8.  Los dígitos son 0,1,2,3,4,5,6,7.

Criterios de divisibilidad:

      Los criterios de divisibilidad son reglas que sirven para saber si un número es divisible por otro sin necesidad de realizar la división.

Estas son las reglas más comunes:

DIVISIBILIDAD POR 2: Un número es divisible por dos si termina en cero o en cifra par.

• 24 es divisible por 2 porque es par.
• 31 no es divisible por 2 porque no es par.

DIVISIBILIDAD POR 3: Un número es divisible por tres, si la suma de sus cifras es múltiplo de tres.

• 42 es divisible por 3 porque 4 + 2 = 6 es múltiplo de tres.
• 43 no es divisible por 3 porque 4 + 3 = 7 que no es múltiplo de tres.

DIVISIBILIDAD POR 5: Un número es divisible por cinco cuando acaba en cero o en cinco.

• 35 es divisible por 5 porque acaba en cinco.
• 540 es múltiplo de 5 porque acaba en cero.

DIVISIBILIDAD POR 9: Un número es divisible por nueve cuando la suma de sus cifras es múltiplo de nueve.

• 45 es divisible por 9 porque la suma de sus cifras es múltiplo de 9 (4 + 5 = 9)
• 738 es múltiplo de 9 porque 7 + 3 + 8 = 18, que es múltiplo de 9.

DIVISIBILIDAD POR 10: Un número es divisible por 10 si termina en cero. De manera similar, si termina en 00 es divisible por 100; si termina en 000 es divisible por 1000.

• El número 70 es divisible por 10 porque termina en cero

Modulo V

Recursividad y grafos:

 Relaciones de recurrencia:

      Una ecuación recurrente es un tipo específico de relación de recurrencia. Una relación de recurrencia para la sucesión ${\displaystyle a_{0},a_{1},a_{2},\ldots }$ es una ecuación que relaciona ${\displaystyle a_{n}\,}$ con alguno de sus predecesores ${\displaystyle a_{0},a_{1},\ldots ,a_{n-1}}$. Las condiciones iniciales para la sucesión ${\displaystyle a_{0},a_{1},\ldots }$ son valores dados en forma explícita para un número finito de términos de la sucesión.

Resolver una relación de recurrencia consiste en determinar una fórmula explícita (cerrada) para el término general ${\displaystyle a_{n}\,}$, es decir una función no recursiva de n.

Hay tres métodos para resolver relaciones recurrentes: iteración, transformada Z y un método especial que se aplica a las relaciones de recurrencia lineales homogéneas con coeficientes constantes.

Un ejemplo de una relación de recurrencia es el siguiente:

${\displaystyle x_{n+1}=rx_{n}(1-x_{n})\,}$

Algunas definiciones de recurrencia pueden tener relaciones muy complejas (caóticas), y sus comportamientos a veces son estudiados por los físicos y matemáticos en un campo conocido como análisis no lineal.

Algoritmos recursivos:

      Llamaremos algoritmos recursivos a aquellos que realizan llamadas recursivas para llegar al resultado, y algoritmos iterativos a aquellos que llegan a un resultado a través de una iteración mediante un ciclo definido o indefinido.

Todo algoritmo recursivo puede expresarse como iterativo y viceversa. Sin embargo, según las condiciones del problema a resolver podrá ser preferible utilizar la solución recursiva o la iterativa.

      Una posible implementación iterativa de la función factorial vista anteriormente sería:

def factorial(n):
    """ Precondición: n entero >=0
        Devuelve: n! """

    fact = 1
    for num in xrange(n, 1, -1):
        fact *= num
    return fact

     Se puede ver que en este caso no es necesario incluir un caso base, ya que el mismo ciclo incluye una condición de corte, pero que sí es necesario incluir un acumulador, que en el caso recursivo no era necesario. Por otro lado, si hiciéramos el seguimiento de esta función, como se hizo para la versión recursiva, veríamos que se trata de una única pila, en la cual se van modificando los valores de num y fact. Es por esto que las versiones recursivas de los algoritmos, en general, utilizan más memoria (la pila del estado de las funciones se guarda en memoria) pero suelen ser más elegantes.

Tipos de Grafos:

     La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos.

 

Grafo Dodecaedro

Grafo de Arco       

Grafo de Pez      

      Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados por un conjunto de líneas (aristas).

• Grafo simple. o simplemente grafo es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo.

• Multígrafo. o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.

• Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha

• Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.

• Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.

• Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.

• Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.

Representación de grafos:

      

El grafo está representado por un arreglo de aristas, identificadas por un de pares de vértices, que son los que conecta esa arista. El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).

Grafos eulerianos y hamiltonianos:

• Grafo eulerianos. Son de los grafos no orientados formados por un ciclo eulerianos; es decir, aquellos que pueden recorrerse completamente desde un vértice y regresar al punto de origen sin pasar dos veces por la misma arista. El nombre de este tipo de grafos proviene del matemático Leonard Euler quien abordó por primera vez el asunto de cómo debían caracterizarse los grafos para poder recorrerse de la manera deseada tras desestimar el problema de los puentes de Königsberg. El problema análogo de recorrido pero que en lugar de limitar el doble paso por las aristas lo hace impidiendo que se transite dos veces por los vértices ha dado lugar a la existencia de los grafos hamiltonianos. 

• Grafo hamiltonianos: En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano. El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo. Los caminos y ciclos hamiltonianos fueron nombrados después que William Rowan Hamilton, inventor del juego de Hamilton, lanzara un juguete que involucraba encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, pero esta solución no se generaliza a todos los grafos.

Algoritmo del camino mas corto de Dijkstra: 

     El algoritmo de Dijkstra es un algoritmo eficiente (de complejidad O (n2 ), donde “n” es el número de vértices) que sirve para encontrar el camino de coste mínimo desde un nodo origen a todos los demás nodos del grafo. Fue diseñado por el holandés Edsger Wybe Dijkstra en 1959. Este algoritmo es un típico ejemplo de algoritmo ávido, que resuelve los problemas en sucesivos pasos, seleccionando en cada paso la solución más óptima con el objeto de resolver el problema. El fundamento sobre el que se basa este algoritmo es el principio de optimizar: si el camino más corto entre los vértices “u” y “v” pasa por el vértice “w”, entonces la parte del camino que va de “w” a “v” debe ser el camino más corto entre todos los caminos que van de “w” a “v”. De esta manera, se van construyendo sucesivamente los caminos de coste mínimo desde un vértice inicial hasta cada uno de los vértices del grafo, y se utilizan los caminos conseguidos como parte de los nuevos caminos. Dicho en otras palabras: “Dado un grafo a cuyos arcos se han asociado una serie de pesos, se define el camino de coste mínimo de un vértice “u” a otro “v”, como el camino donde la suma de los pesos de los arcos que lo forman es la más baja entre las de todos los caminos posibles de “u” a “v”.” El algoritmo de Dijkstra en cada paso selecciona un vértice “v” cuya distancia es desconocida, entre los que tiene la distancia más corta al vértice origen “s”, entonces el camino más corto de “s” a “v” ya es conocido y marca el vértice “v” como ya conocido. Así, sucesivamente se van marcando nuevos vértices hasta que estén todos marcados; en ese momento es conocida la distancia mínima del origen “s” al resto de los vértices. Entre las condiciones más importantes que deben considerarse para aplicar el algoritmo están: Las aristas deben tener un peso no negativo. El grafo debe ser dirigido y por supuesto ponderado. Una posible aplicación de este algoritmo se presenta cuando se desea encontrar la ruta más corta entre dos ciudades; cada vértice representa una ciudad y las aristas representan la duración de los vuelos.

Arboles:

 

      En ciencias de la computación y en informática, un árbol es un tipo abstracto de datos (TAD) ampliamente usado que imita la estructura jerárquica de un árbol, con un valor en la raíz y subárboles con un nodo padre, representado como un conjunto de nodos enlazados. Una estructura de datos de árbol se puede definir de forma recursiva (localmente) como una colección de nodos (a partir de un nodo raíz), donde cada nodo es una estructura de datos con un valor, junto con una lista de referencias a los nodos (los hijos) , con la condición de que ninguna referencia esté duplicada ni que ningún nodo apunte a la raíz. Alternativamente, un árbol se puede definir de manera abstracta en su conjunto como un árbol ordenado, con un valor asignado a cada nodo. Ambas perspectivas son útiles: mientras que un árbol puede ser analizado matemáticamente, realmente es representado como una estructura de datos en la que se trabaja con cada nodo por separado (en lugar de como una lista de nodos y una lista de adyacencia entre nodos, como un grafo). Mirando a un árbol como conjunto, se puede hablar de el nodo padre de un nodo dado, pero en general se habla de una estructura de datos de un nodo dado que sólo contiene la lista de sus hijos sin referencia a su padre (si lo hay).

Arboles recubridores minimales: algoritmos de Kruskal y Prim

      

     Un árbol recubridor es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.; y se usa para asignar un peso total al árbol recubridor mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol de expansión mínimo es un árbol recubridor que pesa menos o igual que todos los otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo.

      El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). Este algoritmo toma su nombre de Joseph Kruskal, quien lo publicó por primera vez en 1956​. Otros algoritmos que sirven para hallar el árbol de expansión mínima o árbol recubridor mínimo son el algoritmo de Prim, el algoritmo del borrador inverso y el algoritmo de Boruvka.

     El Algoritmo de Prim consiste en incrementar el tamaño de un árbol, empezando por un vértice inicial al cual se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto quiere decir que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol. Por tanto, el árbol recubridor mínimo estará completamente construido cuando no queden más vértices por agregar. Los requisitos para proceder con el Algoritmo de Prim son:

• Grafo conexo
• Tener todos los arcos etiquetados

La idea fundamental consiste en añadir en cada paso una arista de peso mínimo a un árbol previamente construido. Para verlo de un modo más explícito, se definen los siguientes pasos:

1. Se elige un vértice U de G y se considera el árbol S={U}.
2. Se considera la arista e de mínimo peso que une un vértice de S y un vértice que no es de S, y se hace S=S+e .
3. Si el número de aristas de T es n-1, el algoritmo termina. En caso contrario, volveríamos al paso 2.