Wikipedia:Proyecto educativo/Matemática discreta y numérica/Plan de aprendizaje/Taller

Editatones

Importante: Esta sección procede de Epistemowikia, aunque, para no generar confusión, allí ha sido blanqueada, permaneciendo su historial que puede consultarse aquí.

Algoritmo de Floyd-Warshall

El algoritmo Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. Muchos problemas de nuestras vidas cotidianas se pueden expresar e incluso resolver en forma de grafo. Existen algoritmos que encuentran distintos tipos de soluciones, tanto booleanas como de eficiencia. El grafo se representa en una tabla (matriz) que se conoce como “matriz de adyacencia” y representa si existe una unión entre dos nodos (boolean).

El algoritmo de Warshall

El algoritmo de Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. La aplicación principal que desarrolló para este algoritmo era obtener la mejor ruta entre todo par de nodos, para ello trabaja con la matriz D inicializada con las distancias directas entre todo par de nodos.

La iteración se produce sobre nodos intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor para ir de i a j es a través de un nodo intermedio elegido o como estaba anteriormente, y esto se prueba con todos los nodos de la red. Una vez probados todos los nodos de la red como nodos intermedios, la matriz resultante da la mejor distancia entre todo par de nodos.

El algoritmo de Floyd

El algoritmo de Floyd es muy similar al de Warshall pero con la diferencia de que Floyd trabaja con grafos ponderados, es decir, el valor de la “flecha” que representamos en la matriz puede ser cualquier entero o infinito e infinito marca que no existe unión entre los nodos. En este caso, el resultado será una matriz donde estarán representadas las distancias mínimas entre nodos, seleccionando los caminos mas convenientes según su ponderación (“peso”). Un ejemplo sería que de un punto A a otro punto B hay 20 km de distancia pero del punto A al C hay 5km de distancia y del C al D otros 5 km de distancia,el algoritmo nos devolvería que de A a B hay 10 km de distancia.

Los pasos a dar en la aplicación del algoritmo de Floyd son los siguientes:

Formar las matrices iniciales C y D.

Se toma k=1.

Se selecciona la fila y la columna k de la matriz C y entonces, para i y j, con i≠k, j≠k e i≠j, hacemos:

Si (Cik + Ckj) < Cij → Dij = Dkj y Cij = Cik + Ckj

En caso contrario, dejamos las matrices como están.

Si k ≤ n, aumentamos k en una unidad y repetimos el paso anterior, en caso contrario paramos las interacciones.

La matriz final C contiene los costes óptimos para ir de un vértice a otro, mientras que la matriz D contiene los penúltimos vértices de los caminos óptimos que unen dos vértices, lo cual permite reconstruir cualquier camino óptimo para ir de un vértice a otro

Pseudocódigo del algoritmo:

Floyd-Warshall (G)

Inicializar

   D = A ' matriz de distancias = matriz de arcos

   si i=j o Dij= infinito entonces Pi,j = nulo sino Pi,j=i 'matriz de caminos

for k = 1 to V

      for i = 1 to V 
           for j = 1 to V 
                  Di,j = min(Di,j , Di,k + Dk,j ) 
                       si min = Di,k + Dk,j entonces 
                           Pi,j = Pk,j

fin

Algoritmo

El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices mejorando paulatinamente una estimación del camino más corto entre dos vértices hasta que se sabe que la estimación es óptima. El algoritmo es capaz de hacer esto con sólo $V^{3}$ comparaciones.

Pseudocódigo

Floyd-Warshall (G)

Inicializar

   D = A ' matriz de distancias = matriz de arcos

   si i=j o Dij= infinito entonces Pi,j = nulo sino Pi,j=i 'matriz de caminos

for k = 1 to V

      for i = 1 to V 
           for j = 1 to V 
                  Di,j = min(Di,j , Di,k + Dk,j ) 
                       si min = Di,k + Dk,j entonces 
                           Pi,j = Pk,j

fin

C++

// Declaraciones en el archivo .h int cn; //cantidad de nodos vector< vector<int> > ady;

// Devuelve una matriz con las distancias minimas de cada nodo al resto de los vertices. vector< vector<int> > Grafo :: floydWarshall(){

   vector< vector<int> > path = this->ady;

   /* No tendría porqué ser necesario si ya hay ceros en las diagonales de ady */
   for(int i = 0; i < cn; i++)
       path[i][i] = 0;
   
   for(int k = 0; k < cn; k++)
       for(int i = 0; i < cn; i++)
           for(int j = 0; j < cn; j++){
               int dt = path[i][k] + path[k][j];
               if(path[i][j] > dt)
                   path[i][j] = dt;
           }
   
   return path;

}

Algoritmo de Kleene

En lo que concierne a la lógica matemática y la computación, el Algoritmo de Kleene es una operación unaria aplicada sobre un conjunto de cadenas de caracteres, representando así el conjunto de las cadenas que se pueden formar tomando cualquier número de cadenas del conjunto inicial.

Teorema de análisis

Sea L ⊆ Σ un lenguaje aceptado por un autómata finito determinista. Entonces, existe una expresión regular α sobre el alfabeto Σ tal que L = L(α). Más aún, mostraremos que existe un algoritmo que permite calcular la expresión regular asociada al lenguaje aceptado por un autómata.

Para demostrar este teorema construiremos un sistema de ecuaciones lineales en expresiones regulares con las reglas siguientes: Supongamos que Q := {q0, . . . , qn}. Introducimos un conjunto de variables biyectable con Q dadovpor {X0, . . . , Xn}. La biyección será dada por qi → Xi

Definiciones

Sean los lenguajes formales A y B, el producto concatenacional, denotado AxB, se define al conjunto de todas las cadenas ab donde a es cada cadena de A y b todas las cadenas de B.

Sea el lenguaje formal L se define a la operación potencia concatenacional n-ésima de L y denotada Ln' según las definiciones:

L0={ε}. L1=L. L2=LxL={a1a1,a1a2} para todas las cadenas ai y aj de L. Ln=LxLn-1. (Definición recursiva). Sea un lenguaje formal L={a,b,c,...}, se llama clausura de Kleene a la operación sobre el lenguaje L y denotado L* a la unión de lenguajes L*=L^0 U L^1 U L^2 U...U L^n

También existe la clausura positiva de Kleene que se denota L+=L*-L0.

Ejemplos

- Sea el lenguaje L={a}, L*={ε,a,aa,aaa,aaaa,...}.

- Sea un B={0,1} lenguaje formal, B*={ε,0,1,00,01,10,11,000,001,010,011,...}.

Referencias

https://www.ecured.cu/Clausura_de_Kleene

https://es.wikipedia.org/wiki/Clausura_de_Kleene

Algoritmos de unión y búsqueda en conjuntos

Introducción

Un algoritmo Unión-Buscar es un algoritmo que realiza dos importantes operaciones en una estructura de datos para conjuntos disjuntos, esas operaciones son:

•Buscar (X): Especifica a que conjunto pertenece el elemento X. Esta operación se usa para saber si dos elementos pertenecen al mismo conjunto.

•Unión (X, Y): Une el conjunto donde se encuentra el elemento X con todo el conjunto al que pertenece Y, proporcionando un nuevo conjunto basado en en los elementos de X y de Y.

Estas dos operaciones descritas anteriormente , servirán para la implementación del algoritmo de Kruskal o también para solucionar problemas que involucran al particionamiento.

Historia

En base a los algoritmos de búsqueda de conjuntos cabe destacar la gran importancia de:

Robert Tarjan: Fue el primero en demostrar la cota superior en términos de la función de Ackermann en 1975. Hasta este momento la mejor cota lograda por operación demostrada por Hopcroft y Ullman, era O ( l o g ( ∗ n ) ), una función no tan eficiente como la función de Ackermann.

Tarjan y Van Leeuwen: Implementaron también algoritmos de Buscar en una sola pasada manteniendo la misma complejidad computacional en el peor de los casos.

En el tema de algoritmos de búsqueda hay que destacar al algoritmo PageRank que se creía que era una idea original de Google pero no fue así ya que el merito fue una implementación eficiente de una red de miles de millones de nodos. Este algoritmo sentó las bases de lo que es ahora Google que de los 24 millones de paginas web que su primera pagina web consiguió indexar, Internet ha crecido hoy hasta superar los 4.000 millones de direcciones distintas

¿Como funciona PageRank?

PageRank es el algoritmo que pone las paginas mas visitadas en lo alto de todos los resultados de busqueda, esto lo realiza aquellas que concentran mas enlaces desde otras webs.

Conceptos

Estructura de datos para conjuntos disjuntos: estructura de datos que mantiene un conjunto de elementos particionados en un número de conjuntos disjuntos (no se solapan los conjuntos).
Algoritmo Unión-Buscar: algoritmo que realiza dos operaciones en la estructura de datos:
- Buscar: Determina a cual conjunto pertenece el elemento A. Esta operación puede ser usada para determinar si dos elementos están o no en el mismo conjunto.

Su pseudocódigo propio viene dado por:

funcion Busqueda(x)
   if x.parent != x
     x.parent := Busqueda(x.parent)
   return x.parent

- Unión: Une todo el conjunto al que pertenece A con todo el conjunto al que pertenece B, dando como resultado un nuevo conjunto basado en los elementos tanto de A como de B.

Su pseudocódigo propio viene dado por:

funcion Union(x, y)
   xRoot := Busqueda(x)
   yRoot := Busqueda(y)
 
   // x e y se encuentran en el mismo conjunto
   if xRoot == yRoot            
       return
   
   // x e y no se encuentran en el mismo conjunto, por lo que aplicamos la unión
   if xRoot.rank < yRoot.rank
     xRoot.parent := yRoot
   else if xRoot.rank > yRoot.rank
     yRoot.parent := xRoot
   else
     //Generamos una raíz del nuevo padre
     yRoot.parent := xRoot    
     xRoot.rank   := xRoot.rank + 1

Otra operación que cabe destacar es la de “Crear Conjunto” es generalmente trivial, ésta crea un conjunto con un elemento dado.

Con el objetivo de definir estas instrucciones, se hace viable la representación de dichos conjuntos, mediante la elección de un elemento de cada conjunto, conocido como elemento representativo, con el fin de representar el conjunto como un todo.

Aquí es donde entran en acción la operación Buscar (x), que devuelve el elemento representativo del conjunto al que pertenece x; la otra operación, Unión, toma como argumento dos elementos característicos de dos conjuntos respectivamente.

Listas enlazadas de conjuntos disjuntos

Para crear una lista enlazada de conjuntos disjuntos, bastaría con crear una lista enlazada para cada conjunto, escogiendo como uno de los elementos de esta como el más representativo y que sea el que va a la cabeza de la lista.

Para llevar a cabo esta operación podemos emplear dos procedimientos:

CrearConjunto: El cual crea una lista de un solo elemento.
Unión: Es la concatenación de dos listas enlazadas, a tiempo constante.

Sin embargo, puede surgir un problema a la hora de realizar la operación "Unión", ya que en ocasiones se precisan de punteros que direccionen hacia la cabecera (elemento representativo) de una lista enlazada para poder operar con "Buscar".

Una herramienta que podría ser de utilidad a la hora de unir, es la de utilizar el algoritmo weighted-union (unión con peso), el cual nos permite concatenar dos listas, de mayor y menor longitud empleando menos tiempo con una serie de operaciones como la de buscar, unir y crear. Archivo:Davidtena.png

Ejemplos

Algunos ejemplos pueden ser el árbol biselado o el Algoritmo de Tarjan del minímo número de ancestros descubiertos y desarrollados por Robert Tarjan,o los splay trees, junto con Daniel Sleator.

*Árbol biselado: Un Árbol biselado o Árbol Splay es un Árbol binario de búsqueda auto-balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores. Realiza operaciones básicas como pueden ser la inserción, la búsqueda y el borrado en un tiempo del orden de O(log n).En muchos casos, gran parte de secuencias no uniforme de operaciones el árbol biselado actúa mejor que otros árboles de búsqueda incluso cuando el patrón específico de la secuencia es desconocido.

Ventajas e inconvenientes:

El buen rendimiento de un árbol biselado depende del hecho de que es auto-balanceado, y además se optimiza automáticamente. Los nodos a los que se accede de forma continua, se mueven cerca de la raíz por lo que se pueden acceder más rapidamente. Esto es una ventaja para casi todas las aplicaciones, y es particularmente útil para implementar cachés y algoritmos de recolección de basura; sin embargo, es importante apuntar que para un acceso uniforme, el rendimiento de un árbol biselado será considerablemente peor que un árbol de búsqueda binaria balanceado simple.

Estado del arte

Implementación en Python

El siguiente es un ejemplo de implementación en Python

class DisjoinSet(object):
    def __init__(self, n):
        self.padre = [x for x in range(n)]
        self.rank = [0 for x in range(n)]

    def Buscar(self, x):
        if(self.padre[x]!=x):
            self.padre[x]=self.Buscar(self.padre[x])
        return self.padre[x]

    def Union(self, x, y):
        xRaiz = self.Buscar(x)
        yRaiz = self.Buscar(y)
        if(xRaiz == yRaiz):
            return
        if self.rank[xRaiz] < self.rank[yRaiz]:
            self.padre[xRaiz] = yRaiz
        elif self.rank[xRaiz] > self.rank[yRaiz]:
            self.padre[yRaiz] = xRaiz
        else:
            self.padre[yRaiz] = xRaiz
            self.rank[xRaiz]+=1

Aplicaciones prácticas

Las estructuras de datos para conjuntos disjuntos modelan el particionamiento de conjuntos, por ejemplo las componentes conexas de un grafo no dirigido. Este modelo también puede utilizarse para verificar si dos vértices pertenecen a una misma componente conexa, o para comprobar si al añadir una arista entre dos vértices se forma un ciclo. El algoritmo Unión-Buscar es usado en implementaciones muy eficientes de Unificación. Esta estructura de datos es usada por la librería Boost Graph Library para implementar su funcionalidad de Componentes Conexas Incrementales. También es usado es la implementación del algoritmo de Kruskal para hallar el árbol abarcador de costo mínimo de un grafo.

Este tipo de procedimientos también puede utilizarse a la hora de diseñar una conexión en red, procesamiento de imágenes, e incluso en la compilación de programas en Fortran.

A continuación se expondrán algunas de las aplicaciones prácticas más destacadas de este campo

Archivo:Algoritmo Dijkstra.png

Algoritmo de Dijkstra

Dentro del campo de los algoritmos de búsqueda del camino más corto en un grafo, destaca el expuesto por el científico de computación Edsger Dijkstra, nacido en Holanda.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, por lo tanto, no funciona en grafos con aristas de coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.

Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
Sea a = x (tomamos a como nodo actual).
Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos nodos no marcados vi.
Para el nodo actual, calculamos la distancia tentativa desde dicho nodo a sus vecinos con la siguiente fórmula: dt(vi) = Da + d(a,vi). Es decir, la distancia tentativa del nodo ‘vi’ es la distancia que actualmente tiene el nodo en el vector D más la distancia desde dicho el nodo ‘a’ (el actual) al nodo vi. Si la distancia tentativa es menor que la distancia almacenada en el vector, actualizamos el vector con esta distancia tentativa. Es decir: *Si dt(vi) < Dvi → Dvi = dt(vi)
Marcamos como completo el nodo a.
Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.

El ejemplo práctico de su funcionamiento lo podemos encontrar en este enlace-----> https://es.wikipedia.org/wiki/Anexo:Ejemplo_de_Algoritmo_de_Dijkstra

Pseudocódigo:

En el siguiente algoritmo, el fragmento u ← vertex in Q with min dist[u], busca el vertice u en el conjunto de vertices Q que tiene el valor mínimo para la distancia[u]. length(u, v) devuelve la longitud de la arista uniendo los dos nodos vecinos u y v. La variable alt en la línea 17 es la longitud del camino del nodo raíz al nodo vecino v si fuera a través de u. Si este camino es mas corto que el camino actual mas corto almacenando para v, el camino actual es reemplazado con este camino alternativo. Al array previo se añade un puntero al próximo nodo en el grafo para obtener la ruta mas corta a la fuente.

1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Inicialización
 6          dist[v] ← INFINITY                  // Distancia desconocida de la fuente a v
 7          prev[v] ← UNDEFINED                 // Nodo anterior con camino óptimo
 8          add v to Q                          // Todos los nodos iniciados en Q (Nodos no visitados)
 9
10      dist[source] ← 0                        // Distancia fuente a fuente
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Se selecciona primera el nodo con menor distancia
14          remove u from Q 
15          
16          for each neighbor v of u:           // Donde v sigue en Q.
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:               // Se ha encontrado un camino más corto a v
19                  dist[v] ← alt 
20                  prev[v] ← u 
21
22      return dist[], prev[]

Una de sus aplicaciones más importantes reside en el campo de la telemática, gracias a el, podemos resolver grafos con muchos nodos, los cuales serian muy complicados de hacer sin dicho algoritmo, encontrando así las rutas más cortas entre un origen y todos los destinos en una red.

Algoritmo de Bellman-Ford

Al igual que el algoritmo de Dijkstra, nos muestra el camino más corto a seguir en un grafo de muchos nodos, cada nodo unido por enlaces de un determinado peso(es decir, ponderados). Sin embargo, cuenta con una diferencia muy importante y es que, pese a que el algoritmo de Dijkstra realiza el camino de manera mas rápida, el de Bellman-Ford nos permite recorrer aristas con peso negativo.

Podemos diferenciar dos versiones:

Una versión no optimizada para grafos con ciclos negativos. Coste de tiempo: O(VE).
Una versión optimizada para grafos con aristas de peso negativo, pero en el cual no existen ciclos de coste negativo. Coste de tiempo: O(VE).

Algoritmo de Busqueda A*

El Algoritmo de busqueda A* es un algoritmo ampliamente usado en la búsqueda de caminos en grafos trasversales, el proceso de trazado de una pauta eficientemente dirigida entre múltiples puntos llamados nodos. Disfruta de una amplio uso debido a su gran eficiencia y precisión, aunque en sistemas practicos de direccion, trabaja peor que algoritmos que puedan preprocesar el grafo para obtener mas eficiencia, aunque para otros trabajos el algoritmo A* ha demostrado ser superior. Fué descrito por primera vez en 1968 por Peter Hart y Nils Nilsson. Es una extensión del algoritmo de Edsger Dijkstra de 1959. A* presenta un mejor funcionamiento usando heurística para guiar su búsqueda.

En este video se puede ver una comparación entre el uso de varios algoritmos para resolver la misma tarea:

> https://www.youtube.com/watch?v=cSxnOm5aceA

En este otro, un ejemplo de uso implementado en Phyton (en C++ sería mas eficiente) que resuelve laberintos:

> https://www.youtube.com/watch?v=J-ilgA_XNI0

Ejemplo de uso:

El algoritmo de búsqueda A* tiene aplicaciones en el mundo real. En este ejemplo las lineas rojas son lineas de ferrocarril y h(x) es el “gran círculo de distancia” (La distancia mas corta posible en una esfera). El algoritmo busca el camino mas corto entre Washington D.C. y Los Ángeles.

A* es un algoritmo de búsqueda informada, es decir, resuelve problemas buscando entre todas las posibles rutas la solución de menor coste (menos distancia, mas rápida...), y entre todas esas rutas que considera la que parezca llegar más rápidamente a la solución. Es formulado en términos de grafos ponderados: Empieza por un nodo específico en un grafo, construye un árbol de pautas que empieza en ese nodo, expandiéndose paso a paso, hasta que una de esas rutas acaba en el nodo final predeterminado.

En cada iteración en su bucle principal, A* necesita determinar cual de sus pautas parciales se expande hacia una o mas pautas mas largas. Lo hace basándose en una estimación del coste (Peso total) y lo sigue realizando hasta el nodo final. De manera específica, A* selecciona la pauta que minimiza

f(n)=g(n)+h(n)

Donde n es el último nodo de la ruta, g(n) es el coste de la ruta desde el nodo inicial hacia n, y h(n) es un eurístico que estima el coste de la ruta mas barata de n al objetivo. La función eurística del algoritmo, cuando busque la ruta mas corta, debe ser admisible, es decir, que no sobrestime el coste real hacia el nodo objetivo mas cercano.

Algoritmo de Kruskal

El algoritmo de Kruskal es un algoritmo de la teoría de grafos con el objetivo de obtener un árbol que abarca un determinado espacio en un grafo conexo y acíclico, y a la vez ponderado. El algoritmo se basa en la propiedad que presentan los árboles y que permite saber si un arco debería pertenecer a dicho árbol o no, y usar esta propiedad para seleccionar cada arco. Esto significa, buscar un subconjunto de aristas que, formando un árbol, incluyan en cada uno de sus vértices y donde el valor total de todas las aristas del árbol es el mínimo. En el caso de no encontrarnos ante un grafo no conexo, entonces se busca un bosque expandido mínimo.

Demo de utilización del algoritmo de Krustal para encontrar el árbol más pequeño

Vamos a explicar brevemente cómo trabaja el algoritmo de Kruskal:

<<El objetivo de este algoritmo es construir un árbol formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.>>

En primer lugar ordenamos las aristas del grafo por su peso, de menor a mayor. Mediante la técnica Greedy Kruskal se intentará unir cada arista siempre y cuando no se forme un ciclo. Ya que hemos ordenado las aristas por peso, comenzaremos con la arista de menor peso, siempre y cuando los vértices que contienen dicha arista no estén en la misma componente conexa, entonces los unimos para formar una sola componente. Si están en la misma componente conexa, estamos evitando que se creen ciclos y que la arista que une dos vértices siempre sea la mínima posible.

El algoritmo de Kruskal es un ejemplo de algoritmo voraz cuyo funcionamiento se basa en:

Se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado.
Se crea un conjunto C que contenga a todas las aristas del grafo.
Mientras C es no vacío.
Eliminar una arista de peso mínimo de C.
Si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol.
En caso contrario, se desecha la arista.

En la próxima contribución se explicara un ejemplo práctico.

Bosques de Conjuntos-Disjuntos

Los Bosques de Conjuntos-Disjuntos son estructuras de datos donde cada conjunto está representado por un árbol , en el cual cada nodo mantiene una referencia a su nodo padre.

En los Bosques de Conjuntos-Disjuntos, el representativo de cada conjunto es la raíz del árbol el cual representa el conjunto. Buscar sigue por los padres nodos hasta encontrar la raíz del árbol. Unión combina dos árboles en uno añadiendo la raíz de uno en la raíz del otro. El ejemplo que vamos a mostrar a continuación está extraído de una pagina de wikipedia:

 function CrearConjunto(x)
     x.padre := x

 function Buscar(x)
      if x.padre == x
         return x
      else
         return Buscar(x.padre)

 function Unión(x,y)
     xRaíz := Buscar(x)
     yRaíz := Buscar(y)
     xRaíz.padre := yRaíz

Colaboradores de Wikipedia. Estructura de datos para conjuntos disjuntos [en línea]. Wikipedia, La enciclopedia libre, 2015 [fecha de consulta: 24 de febrero del 2017]. Disponible en <https://es.wikipedia.org/w/index.php?title=Estructura_de_datos_para_conjuntos_disjuntos&oldid=87049764>.

Esta implementación no es mejor que la implementación basada en listas enlazadas, porque el árbol que se crea puede ser muy desbalanceado. Podemos arreglar esto de dos maneras:

Unión por Rank: Consiste en añadir el árbol más pequeño a la raíz del árbol más grande.
Compresión por caminos: Es una forma de aplanar la estructura del árbol cuando se aplique Buscar, es decir, es una forma de mejorar la función Buscar.

Estas dos técnicas se complementan para reducir considerablemente el tiempo de ejecución, el tiempo amortizado es O(α (n)), donde O(α (n)) es siempre menor que 5 para todos los valores lejanos de n.

A continuación explicaré como hacer la unión de nodos y la búsqueda de nodos:

En la implementación de bosques de conjuntos-disjuntos representamos los conjuntos como un árbol, donde cada nodo mantiene la información de su nodo padre, la raíz del árbol será el elemento representativo de todo el conjunto. Por lo tanto basta con declarar una matriz que contenga los elementos del padre de un determinado elemento.

Método MakeSet Para este tipo de implementación agregaremos un método que me inicializará los conjuntos, el cual llamaremos MakeSet:

//Método de inicialización void MakeSet( int n ){

   for( int i = 0 ; i < n ; ++i ){
       padre[ i ] = i;      //Inicialmente el padre de cada vértice es el mismo vértice
   }

}

Iniciamos por ejemplo 9 vértices con el makeset, una vez iniciado se puede hacer un find de un nodo o unir varias ramas.

Método Find - Find(x)

Como se ha explicado al inicio este método determina a que componente pertenece un vértice X determinado, lo hace retornando el vértice raíz del árbol en el que se encuentra el vértice X.

Con este método lo que tratamos de hacer es encontrar la raíz de las ramas y no importa que nodo escojas para hacer el find que mediante una iteración recursiva llegas al nodo principal.

Si tenemos 4 vértices y están puestos en cascada, el 0 es la raíz de la rama, el 1 es su "hijo", el 2 es el "hijo" del 1 y el 3 es el "hijo" del 2, es decir: 0->1->2->3

Si hiciésemos la operación find(3) nos devolvería 2, porque el padre del nodo 3 es el nodo 2, si volviésemos a hacer find del resultado que nos ha dado (2), saldría como resultado 1, puesto que el padre del nodo 2 es el nodo 1, hacemos otra búsqueda y nos da como resultado 0, y si intentamos hacer una ultima búsqueda nos saldría 0 puesto que no tiene padre, es el nodo raíz.

Algoritmo de Ordenación Topológica

Este algoritmo se utiliza para la ordenación lineal de un grafo acíclico, de manera que el grafo quede ordenado de manera lineal, respetando las conexiones propias del grafo en su estado inicial.

Se compara la aplicación de este algoritmo con la asignación a cada nodo del grafo una tarea con un nivel de prioridad específica,de tal manera que realmente lo que tenemos es una lista ordenada por prioridad de realizacion.

Suponiendo un grafo denominado G, para conseguir esa ordenación topológica que deseamos es necesario aplicar una versión modificada del algoritmo de Búsqueda en Profundidad.

Generalmente, el coste de tiempo de estos algoritmos aplicado a los grafos suele ser en función de la cantidad de nodos más la cantidad de aristas. Uno de los primeros algoritmos, descrito y desarrollado por Kahn en 1962 trabaja eligiendo primero los nodos que son iniciales (aquellos que a priori no tienen ningún arco entrante), al ser el grafo acíclico, siempre debe de haber al menos 1 de estos nodos en el grafo.

Aquí un ejemplo en pseudocódigo del algoritmo: L ← Lista vacía que contendrá luego los elementos ordenados. S ← Conjunto de todos los nodos sin aristas entrantes.

MIENTRAS [S no es vacío]:

       n ← nodo extraído de S
       insertar n en L

       PARA CADA [nodo m con arista e de n a m]:
               Eliminar arista e del grafo

               SI [m no tiene más aristas entrantes]:
                       insertar m en S

SI [el grafo tiene más aristas]:

       error: el grafo tiene al menos un ciclo

SINO:

       RETORNAR L

Si realmente la estructura a la que se aplica éste algoritmo es un GAD, éste algoritmo daría una de las soluciones posibles, si sólo hubiese una solución, significaría que el grafo tiene al menos un ciclo y por lo tanto aplicar u ordenamiento topológico es imposible.

La unicidad del conjunto resultante depende de la estructura de datos en la que se base el conjunto al cual le hemos aplicado el algoritmo, no tiene porque estar perfectamente ordenado como deseamos, puede ser un grafo que actúa como una pila o una cola.

Dependiendo del orden en el que van siendo extraídos los nodos,el algoritmo dará una solución u otra.

Otra alternativa en cuanto a algoritmo se refiere es a una modificación del algoritmo de búsqueda en profundidad (denominado DFS en inglés) en el caso de este algoritmo,los arcos que van desde el nodo x al nodo y han de estar relacionados, es decir que el nodo y( en este caso lo denominaremos tarea y, ha de completarse antes de que la tarea x empiece). De esta manera el algoritmo va expandiéndose por el grafo en un orden concreto, hasta que llega a una tarea o nodo por el cual ya ha pasado desde el comienzo del algoritmo. He aquí una implementación del algoritmo mencionado:

ORDENACIÓN_TOPOLÓGICA(grafo G)
 for each vértice u ∈ V[G]do
         estado[u] = NO_VISITADO
         padre[u] = NULL
 tiempo =0
 for each vértice u ∈ V[G]do
         if estado[u] = NO_VISITADO then
                 TOPOLÓGICO-Visitar(u)

TOPOLÓGICO-Visitar(nodo u)
 estado[u]=VISITADO
 tiempo = tiempo+1
 distancia[u] = tiempo
 for each v ∈ Adyacencia[u] do
         if estado[v]=NO_VISITADO then
                 padre[v]=u
                 TOPOLÓGICO-Visitar(v)
 estado[u] = TERMINADO
 tiempo = tiempo+1
 finalización[u] = tiempo
 insertar (lista, u)

Este algoritmo depende de como recorramos el gráfico con los for, si se recorre de cierta manera dará una solución u otra.

Artículo completo en:https://es.wikipedia.org/wiki/Ordenación_topológica

Ciclo de Euler

Un caso particular de la unión y búsqueda de conjuntos, viene dado por el Ciclo de Euler o euleriano que forma parte de la teoría de grafos y comprende el camino cerrado que recorre cada arista en un solo recorrido. Este ciclo tiene una serie de propiedades o teoremas:

1º Teorema 1. Sea G un grafo o multigrafo no dirigido. Entonces G tiene un ciclo de Euler si, y solo si, es conexo y todo vértice tiene grado par. Diremos que es un grafo Euleriano.

2º Teorema. Sea G un grafo o multigrafo no dirigido. Entonces G tiene un camino de Euler si, y solo si, es conexo y tiene solo dos vértices de grado impar. Diremos que el grafo es semi-Euleriano.

Ejemplo de implementacion en C++

Con el siguiente código conseguimos descubrir un circuito euleriano, que corresponde a una determinada matriz de adyacencia.

#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

#define FIN_CICLO -1

int **leerMatrizAdyacencia(char *nombreArchivo)
{    
    ifstream archivo(nombreArchivo);
    
    if (archivo == NULL) return NULL;
    
    int **matriz;
    
    int n;

    archivo>>n;
    
    matriz = new int*[n];
    
    for(int i=0; i<n; i++)
    {
            matriz[i] = new int[n];
            
            for(int j=0; j<n; j++)
                    archivo>>matriz[i][j];        
    }
    
    return matriz;
}

void mostrarMatrizAdyacencia(int **matriz, int n)
{
     for (int i=0; i<n; i++)
         {
              for (int j=0; j<n; j++)
                  cout<<matriz[i][j]<<" ";
              cout<<"\n";     
         }
         
     cout<<"\n";
}

void destruirMatrizAdyacencia(int **matriz, int n)
{
     for (int i=0; i<n; i++)
         delete matriz[i];
         
     delete matriz;
}

int dentroDeCiclo(int *ciclo, int vertice)
{
    int enCiclo = false;
         
    int k = 0;
         
    while (ciclo[k] != FIN_CICLO && !enCiclo)
    {
          if (vertice == ciclo[k]) enCiclo = true;
           
          k++;
    }
    
    return enCiclo;
}

void mostrarCiclo(int *ciclo)
{    
     for (int i=0; ciclo[i]!=FIN_CICLO; i++)
        {
            cout<<ciclo[i]<<" ";
        }
        
     cout<<"\n";
}

int *encontrarCiclo(int **matriz, int vertice, int n)
{
     int v;
     
     int *ciclo = new int[n*n + 1];
     
     ciclo[0] = FIN_CICLO;
     
     v = vertice;
     
     int i = 0;
     
     do
     {
         int j = 0;
                  
         while (matriz[v][j] == 0 || dentroDeCiclo(ciclo, j))
         {
               j++;
             
               while (j == n)
               {
                     
                  i--;
                   
                  if (i < 0) return NULL;
                           
                  else if (i == 0)
                  {
                      v = vertice;  
                  }
                  else
                  {
                      v = ciclo[i-1];
                  }
                           
                  j = ciclo[i] + 1;

                  ciclo[i] = FIN_CICLO;
                  
                  mostrarCiclo(ciclo);
               }
         }
                            
         v = j;
              
         ciclo[i] = v;
         
         ciclo[i+1] = FIN_CICLO;
     
         i++;
         
         mostrarCiclo(ciclo);
         
         if (i >= n*n) return NULL;
         
     }while(v != vertice || i<=2);
          
     return ciclo;
}

void eliminarAristas(int **matriz, int *ciclo)
{
    int i;
    
    if (ciclo[0] == FIN_CICLO) return;
        
    i = 1;
    
    while (ciclo[i] != FIN_CICLO)
    {
          
          matriz[ciclo[i-1]][ciclo[i]] = 0;
          matriz[ciclo[i]][ciclo[i-1]] = 0;
          
          
          i++;
    }
    
    matriz[ciclo[i-1]][ciclo[0]] = 0;
    matriz[ciclo[0]][ciclo[i-1]] = 0;
}

int tieneAristas(int **matriz, int n)
{
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if (matriz[i][j] == 1) return true;
            
    return false;
}

void pegarCiclos(int *ciclo, int *subciclo, int posicion)
{
     int i, tamano_ciclo, tamano_subciclo;
     
     for (i = 0; ciclo[i] != FIN_CICLO; i++);
     
     tamano_ciclo = i;
     
     for (i = 0; subciclo[i] != FIN_CICLO; i++);
     
     tamano_subciclo = i;
     
     int *ciclo_aux = new int[tamano_ciclo + tamano_subciclo + 1];
     
     for (i = 0; i<posicion; i++)
         ciclo_aux[i] = ciclo[i];
         
     
     for (i = posicion; i< posicion + tamano_subciclo; i++)
         ciclo_aux[i] = subciclo[i - posicion];
         
     
     for (i = posicion + tamano_subciclo; i < tamano_ciclo + tamano_subciclo; i++)
         ciclo_aux[i] = ciclo[i - tamano_subciclo];
     
     
     for (i = 0; i <  tamano_ciclo + tamano_subciclo; i++)
         ciclo[i] = ciclo_aux[i];
     
     ciclo[tamano_ciclo + tamano_subciclo] = FIN_CICLO;
     
     delete ciclo_aux;
}

int main(int argc, char *argv[])
{
    
    int **matriz = leerMatrizAdyacencia("matriz.txt");
    
    if (matriz == NULL)
       {
               cout<<"El archivo no existe\n";
               
               system("PAUSE");
               
               return 0;
       }

    cout << "matriz de adyacencia inicial: \n";

    mostrarMatrizAdyacencia(matriz, 8);
    
    int *ciclo = encontrarCiclo(matriz, 3, 8);
    
    if (ciclo == NULL)
    {
              cout<<"no hay ciclo\n";
              
              return 0;
    }
    
    cout <<"ciclo inicial: \n";
    
    mostrarCiclo(ciclo);
    
    eliminarAristas(matriz, ciclo);
        
    int i, *subciclo, *euleriano  = ciclo;
    
    while (tieneAristas(matriz, 8))
    {
          cout << "matriz de adyacencia sin las aristas del ciclo euleriano: \n";
              
          mostrarMatrizAdyacencia(matriz, 8);

          cout<<"ciclo euleriano actual:\n";
    
          mostrarCiclo(euleriano);
          
          system("PAUSE");
          
          subciclo = NULL;
          
          i = 0;
          
          do
          {
              
              subciclo = encontrarCiclo(matriz, euleriano[i], 8);
              
              i++;
          
          }while(subciclo==NULL && euleriano[i] != FIN_CICLO);
          
          
          if (subciclo == NULL) 
             cout<<"no hay subciclo";
          else
          {
              cout<<"subciclo encontrado:\n";
          
              mostrarCiclo(subciclo);
          
              pegarCiclos(euleriano, subciclo, i);
              
              cout<<"insertando subciclo en la posicion "<<i<<" del ciclo euleriano:\n";
    
              mostrarCiclo(euleriano);
          
              system("PAUSE");
          
              eliminarAristas(matriz, subciclo);
          }
          
    }
    
    
    cout<<"ciclo euleriano final:\n";
    
    mostrarCiclo(euleriano);

    
    destruirMatrizAdyacencia(matriz, 8);    
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

Cierre reflexivo de una relación binaria

Introducción

Sea $R$ una relación binaria aplicada sobre un conjunto $A$ , la clausura reflexiva o cierre reflexivo de ${\mathcal {R}}$ , denotada $CR({\mathcal {R}})$ , es la relación reflexiva más pequeña aplicada sobre $A\,$ que contiene a ${\mathcal {R}}$ .

En otras palabras, $CR({\mathcal {R}})$ es la relación binaria que verifica:

${\mathcal {R}}\subseteq CR({\mathcal {R}})$
$CR({\mathcal {R}})$ es reflexiva
Si ${\mathcal {R}}'$ es una relación reflexiva tal que ${\mathcal {R}}\subseteq {\mathcal {R}}'$ , entonces $CR({\mathcal {R}})\subseteq {\mathcal {R}}'$

Note que si ${\mathcal {R}}$ es reflexiva, entonces $CR({\mathcal {R}})={\mathcal {R}}$ .

Propiedades

Ejemplos

Sea A un conjunto cualquiera:

Sea $(A,\geq )$ , $\geq$ ("mayor o igual que") es reflexiva, pero $>\,$ ("mayor estricto que") no lo es.
Sea $(A,\leq )$ , $\leq$ ("menor o igual que") es reflexiva, pero $<\,$ ("menor estricto que") no lo es.
Sea $(A,=)\,$ , $=\,$ (la igualdad matemática), es reflexiva.
Sea $(A,\subseteq )$ , $\subseteq$ (la inclusión de conjuntos), es reflexiva.
Sea $(\mathbb {N} \backslash \{0\},\backslash )$ , $\backslash \,$ (la divisibilidad) es reflexiva.
Sea $X$ el conjunto de todas las rectas en el plano, la relación de paralelismo || entre rectas es reflexiva, porque toda recta es paralela a sí misma.
Sea $X$ el conjunto de todas las rectas en el plano, la relación de perpendicularidad $\bot$ entre dos rectas es antirreflexiva, porque no hay rectas que sean perpendiculares a sí mismas.
Las relaciones Ser padre de y Ser madre de son antirreflexivas, porque en ningún caso alguien puede ser padre o madre de sí mismo.

Aplicaciones prácticas

Ejercicio 1.- Sea A = {huevos, leche, maíz} y B = {vacas, cabras, gallinas}.

Escribir la relación R de A a B definida por: (a, b) ∈ R ⇐⇒ a es producido por b.

Solución: La relación sería: R = {(huevos,gallinas),(leche,vacas),(leche,cabras)}

Ejercicio 2.- Para los conjuntos A = {1, 2, 3}, B = {2, 4, 5}:

•El número de relaciones binarias en A.

  Solución: N = |P(A × A)| = 2|A×A| = 29

•El número de relaciones de A a B que contengan exactamente cinco pares ordenados.

  Solución: N = C9,5 = 
   
   - -
   |9|
   |5|
   - -

Matriz de adyacencia

La matriz de adyacencia característica de este tipo de relación binaria es la siguiente:

N 0 1 2 3 4 5 6 7 8
0 1 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0
2 0 0 1 0 0 0 0 0 0
3 0 0 0 1 0 0 0 0 0
4 0 0 0 0 1 0 0 0 0
5 0 0 0 0 0 1 0 0 0
6 0 0 0 0 0 0 1 0 0
7 0 0 0 0 0 0 0 1 0
8 0 0 0 0 0 0 0 0 1

Claramente se observa que la manera de calcularla es llenando a 1 su diagonal principal.

Referencias

https://es.wikipedia.org/wiki/Relaci%C3%B3n_reflexiva

Enlaces externos

Hazewinkel, Michiel, ed. (2001), "Reflexivity", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4

Cierre transitivo de una relación binaria

Introducción

En matemáticas, el cierre transitivo de una relacion binaria R de un conjunto X es la relación más pequeña de X que contiene a R y es transitiva. La clausura transitiva o cierre transitivo de una relación $R\,$ es denotada $CT(R)\,$ . Se verifica que:

$R\subseteq CT(R)$
$CT(R)\,$ es transitiva
Si $R'\,$ es una relación transitiva tal que $R\subseteq R'$ , entonces $CT(R)\subseteq R'$

Por ejemplo, si X es un conjunto de aeropuertos y xRy significa "hay un vuelo directo del aeropuerto x al aeropuerto y" (para 'x' e 'y' existentes en X), entonces el cierre transitivo de R en X es la relación R^+ de tal forma que x(R^+)y signifique "es posible volar desde x hasta y de una o más formas". Coloquialmente, el cierre transitivo te brinda un conjunto de todos los lugares a los que puedes llegar desde un punto inicial; Concretamente, el cierre transitivo de una relación binaria R en un conjunto X es la relación transitiva R^+ de un conjunto X de tal forma que R^+ contiene a R, y R^+ es lo más pequeño posible. Si la relación binaria es transitiva de por sí, entonces el cierre transitivo es la propia relación binaria; En caso contrario, el cierre transitivo es una relación diferente.

Historia

En 1962 el conocido científico computacional Robert W. Floyd publicó el algoritmo de Floyd-Warshall, un ejemplo de programa dinámico. Sin embargo este es esencialmente el mismo publicado por Stephen Warshall en 1962 y Bernard Roy en 1959. También está muy relacionado con el algoritmo de Kleene.

Conceptos

La clausura transitiva o cierre transitivo de una relación binaria es la relación binaria más pequeña que siendo transitiva contiene al conjunto de pares de la relación binaria original. El concepto de transitividad es el mismo que se utiliza en teoría matemática el cual postula que si a<b<c en el caso de clausura transitiva, el concepto se refiere a que existe un camino que une el vértice "i" con el vértice "j", sin importar que para llegar desde i a j tengamos que visitar otros vértices del grafo. La clausura transitiva de una relación R se denota CT(R). En otras palabras, CT(R) es la relación binaria que verifica:

  1.  R ⊆ C T ( R )
  2.  C T ( R ) es transitiva
  3.  Si R' es una relación transitiva tal que R ⊆ R', entonces C T ( R ) ⊆ R'

Nótese que si R es transitiva, entonces CT(R) = R. Dada cualquier relación binaria siempre existe su clausura transitiva, es decir, dada cualquier relación binaria esta puede extenderse hasta que la relación extendida sea transitiva. Esta clausura transitiva puede hallarse usando la representación de la relación como matriz booleana. Dada la relación R sobre un conjunto de n elementos {a₁,...,a_n}, la matriz booleana asociada a la relación viene dada por: B_R = [b_ij] ^ b_ij = {1 si a_iRa_j; 0 si ¬a_iRa_j}

Propiedades

La intersección de dos relaciones transitivas es transitiva.

La unión de dos relaciones transitivas no necesita ser transitiva. Para conservar la transitividad, uno debe tomar la clausura transitiva. Esto ocurre, por ejemplo, cuando se toma la unión de dos relaciones de equivalencia. Para obtener una nueva relación de equivalencia hay que tomar la clausura transitiva (la reflexividad y la simetría, en el caso de las relaciones de equivalencia, son automáticas).

Dado un conjunto A = {a, b, c, ...}, consideremos una relación binaria R definida entre A y el mismo A. Algunas de las propiedades que puede verificar R son:

1.Una relación tiene la propiedad reflexiva, si todo elemento está relacionado consigo mismo, si no todos los elementos del conjunto están relacionados consigo mismo se dice que la relación no es reflexiva.

\forall a\in A:\;(a,a)\in R

Para todo elemento a que pertenezca al conjunto A, el par ordenado (a,a) pertenece a la relación binaria R.

Téngase en cuenta que debe cumplirse para todos los elementos del conjunto sin excepción, si esta propiedad solo se da en algunos casos la relación no es reflexiva:

\nexists a\in A:\;(a,a)\notin R

No existe ningún elemento a en A, para el que el par ordenado (a,a) no pertenezca a la relación R.

2.Una relación binaria tiene la propiedad irreflexiva, también llamada: antirreflexiva o antirrefleja, si ningún elemento del conjunto está relacionado consigo mismo:

\forall a\in A:\;(a,a)\notin R

Que también puede expresarse

\nexists a\in A:\;(a,a)\in R

No existe ningún elemento a en el conjunto A que cumpla que: (a,a) pertenezca a R.

3. Una relación binaria tiene la propiedad simétrica, si se cumple que un par ordenado (a,b) pertenece a la relación entonces el par (b,a) también pertenece a esa relación:

\forall a,b\in A:\;(a,b)\in R\quad \longrightarrow \quad (b,a)\in R

Para todo par ordenado (a,b) que pertenezca a R, implica que el par (b,a) también pertenece a R, téngase en cuenta que si el par (a,b) no pertenece a la relación el par (b,a) tampoco tiene que pertenecer a esa relación:

\nexists a,b\in A:\;(a,b)\in R\quad \land \quad (b,a)\notin R

No existe ningún par ordenado (a,b) que pertenezca a R y que el par (b,a) no pertenezca a R.

   4.Una relación binaria se dice que tiene la propiedad antisimétrica si los pares ordenado (a,b) y (b,a) pertenecen a la relación entonces a = b:

\forall a,b\in A:\;{\Big (}(a,b)\in R\quad \land \quad (b,a)\in R{\Big )}\quad \longrightarrow \quad a=b

Dicho de otra manera, no existen los elementos a, b distintos, y que a este relacionado con b y b este relacionado con a

\nexists a,b\in A:\;(a,b)\in R\quad \land \quad (b,a)\in R\quad \land \quad a\neq b

    5.Una relación binaria tiene la propiedad transitiva cuando, dado los elementos a, b, c del conjunto, si a está relacionado con b y b está relacionado con c, entonces a está relacionado con c:

\forall a,b,c\in A:\;{\Big (}(a,b)\in R\quad \land \quad (b,c)\in R{\Big )}\quad \longrightarrow \quad (a,c)\in R

Existencia y descripción

La clausura transitiva de una relación binaria siempre existe, es decir, dada cualquier relación binaria esta puede extenderse hasta que la relación extendida sea transitiva. Además la clausura transitiva que denotaremos aquí mediante R_CT admite una caracterización muy sencilla:

  xR_CTy

Para cualquier relación R, existe siempre el cierre transitivo de R. Para demostrar esto, nótese que la intersección de cualquier familia de conjuntos de relaciones transitivas, es de nuevo transitiva. Además, existe al menos una relación transitiva que contiene a R, llamada 'tribial': X x X. El cierre transitivo de R está entonces dado por la intersección de todas las relaciones transitivas que contienen a R.

Para conjuntos finitos, podemos formar el cierre transitivo paso a paso partiendo de R y añadiendo márgenes transitivos. Para cualquier conjunto X, podemos probar que el cierre transitivo es dado por la siguiente expresión:

R^{+}=\bigcup _{i\in \{1,2,3,\ldots \}}R^{i}.

donde $R^{i}$ es la i potencia de R, definida de forma inductiva por

R^{1}=R\,\!

y, para $i>0$ ,

R^{i+1}=R\circ R^{i}

donde $\circ$ significa composición de relaciones.

Para demostrar que la definición R⁺ es la relación menos transitiva que contiene R, nosotros vamos a demostrar que R, es transitiva y es el conjunto más pequeño con ambas características.

$R\subseteq R^{+}$ : $\displaystyle R^{+}$ contiene todas las $\displaystyle R^{i}$ ,en particular $\displaystyle R^{+}$ contiene $\displaystyle R$ .
$\displaystyle R^{+}$ es transitiva: Cada elemento de $\displaystyle R^{+}$ esta en uno de los $\displaystyle R^{i}$ , asi que $\displaystyle R^{+}$ debe ser transitivo a partir del siguiente razonamiento: Si $(s_{1},s_{2})\in R^{j}$ y $(s_{2},s_{3})\in R^{k}$ , la asociacion de composición $(s_{1},s_{3})\in R^{j+k}$ , debido a la definición $\displaystyle R^{i}$ .
$\displaystyle R^{+}$ es mínima: $\displaystyle G$ es cualquiera relación transitiva que contenga $\displaystyle R$ , nosotros queremos demostrar $R^{+}\subseteq G$ . Para esto nos basta con demostrar para cada $i>0$ , $R^{i}\subseteq G$ .

En la teoría de grafos:

Transitive closure constructs the output graph from the input graph. — El cierre transitivo de una relación binaria construye el grafo de salida a partir del grafo de entrada.

En la informática, el concepto de cierre transitivo de una relación binaria puede ser vista como una contrucción de datos que hace posible responder a cuestiones sobre la accesibilidad. Esto es, que uno puede pasar del nodo a al nodo b, y que el nodo b está conectado al nodo c, etc. Después de que el cierre transitivo de la relación binaria esté contruido, tal y como se muestra en la figura que aparece a continuación, en la operación 0(1) se puede determinar que le nodo d es alcanzable desde el nodo a. Es típico que la estructura de datos sea representada como una matriz, de tal forma que si la matriz es una matriz[1][4] = 1, entonces es el caso en el que el nodo 1 puede alcanzar el nodo 4 a través de uno o más saltos.

El cierre transitivo de una relación binaria de un grafo directo acíclico (GDA)es la relación de accesibilidad del GDA y el [orden parcial estricto]].

Matriz de relación

Una matriz es una manera conveniente de representar una relación R de X e Y. Para ello se etiquetan los renglones con elementos de las 'X' y las columnas con los elementos de las 'Y'. El elemento formado por una columna y un renglón específico se pone a uno si X R Y.

Sobre una relación de conjuntos establecidos, se puede asegurar:

Una relación es reflexiva si y sólo si la matriz está formada por 1 en la diagonal principal, es decir, si (x,x) ∈ R para toda x ∈ R.
Una relación es simétrica si y sólo si la matriz A es simétrica respecto a la diagonal principal. Esto se cumple debido a que tanto (x,y) como (y,x) ∈ R.
Una relación es transitiva si y solo sí el elemento ij en A² es diferente de 0, el elemento ij de A es también 0. Su representación mediante matriz se realiza operando A ∨ A² = A
Una relación es antisimétrica si y solo si a ∈ R y b ∈ R. De este modo, a=b. Su representación matricial se llevaría a cabo haciendo la suma de A y de A traspuesta. Si no existe ningún 2 excepto en la diagonal principal, entonces la propiedad se cumple.

Ejemplos

1.

  Si  S = {1, 2, 3}
  R= {(1,1), (1,2), (1,3) , (2,3), (3,1)} 
  (2,3) ∈ R ∧ (3,1) ∈ R → (2,1) ∈ Rt 
  (3,1) ∈ R ∧ (1,2) ∈ R → (3,2) ∈ Rt 
  (3,1) ∈ R ∧ (1,3) ∈ R → (3,3) ∈ Rt 
  (2,1) ∈ Rt ∧ (1,2) ∈ R → (2,2) ∈ Rt  (*Debe hacerse de manera iterativa)
  Entonces Rt =  R ∪ {(2,1), (3,2), (3,3), (2,2)}

2. Como ejemplo de una relación no transitiva podríamos poner una ciudad "x" la cual puede alcanzar una via directa de vuelo de una ciudad "y" en el centro de todas las ciudades. Porque haya un vuelo directo de una ciudad a una segunda ciudad y un vuelo directo de la segunda ciudad a una tercera; esto no implica que haya vuelo directo de la primera ciudad a la tercera. La clausura transitiva de esta relación es una relación diferente, llamada ' Secuencia de vuelos directos empezando en la ciudad "x" y terminando en la ciudad "y"'. Cada relación puede ser extendida de una forma similar a una relación transitiva.

3. Un ejemplo de una relación no transitiva con una clausura transitiva menos significativa es '"x" es el dia de la semana despues de "y"'. La clausura transitiva de esta relación es 'un día "x" viene después de un día "y" en el calendario', el cual es trivialmente verdadero para todo los dias de la semana "x" e "y" ( y estas equivalencias para el cuadrado cartesiana, el cual "x" e "y" son ambos días de la semana).

4. Imaginemos la siguiente situación. Entre los alumnos de una clase tenemos una serie de relaciones R. El alumno A está en relación con el alumno B.

Suponemos que los asientos están distribuidos uniformemente, que hay más de una fila y que los asientos están ocupados.

Observamos que el profesor llama a los alumnos, estableciendo relaciones R entre ellos (los llama por cualquier razón: faltas de comportamiento, ejercicios conjuntos...). Hablamos entonces de la clausura transitiva C de R.

Pongamos que el profesor selecciona alumnos de una misma fila, separados a la distancia que él prefiera. Puede ir seleccionando hacia atrás o hacia delante. Entonces puede establecer una relación entre A y B, o viceversa. Puede moverse libremente para elegirles, entonces R y C son la relación vacía.

¿Y si el profesor selecciona alumnos de diferentes filas? Entonces la clausura transitiva de R es C, que consiste en todos los pares ordenados (A,B) incluyendo los pares del tipo (X,X).

Estado del arte

La clausura transitiva de una relación binaria siempre existe, es decir, dada cualquier relación binaria esta puede extenderse hasta que la relación extendida sea transitiva. Además la clausura transitiva que denotaremos aquí admite una caracterización muy sencilla.

Aplicaciones prácticas

En Nuutila (1995) se pueden encontrar algoritmos eficaces para calcular el cierre transitivo de un gráfico. Los métodos son en el peor caso más rápido reducen el problema a la multiplicación matricial. El problema también puede ser resuelto por el algoritmo de Floyd-Warshall, o por la búsqueda ampliada de anchura-primera o profundidad-primera búsqueda comenzando desde cada nodo del gráfico.

Investigaciones más recientes han explorado formas eficientes de calcular el cierre transitivo en sistemas distribuidos basados en el paradigma de MapReduce (Afrati et al., 2011).

Algoritmo de Floyd-Warshall:

Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. Lo hace mejorando paulatinamente una estimación del camino más corto entre dos vértices, hasta que se sabe que la estimación es óptima.

Véase también

Matriz de adyacencia

Definición

Sea el grafo G=<V,A> de orden N al mismo se asocia una matriz cuadrada M de NxN tal que:

A cada fila se asocia un nodo de V.
A cada columna se asocia un nodo de V.
La celda Mi,j contiene la cantidad de aristas de A de la forma {i,j} ó (i, j).

Ejemplo

Dada la relación:

   G=<{0, 1, 2, 3, 4, 5, 6, 7, 8}, ((0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 6), (3, 7), (8, 3), (4, 6), (4, 7), (8, 4), (5, 6), (5, 7), (8, 5))>.

la matriz de adyacencia asociada al grafo sería:

N	0	1	2	3	4	5	6	7	8
0	0	0	0	1	1	1	0	0	0
1	0	0	0	1	1	1	0	0	0
2	0	0	0	1	1	1	0	0	0
3	1	1	1	0	0	0	1	1	1
4	1	1	1	0	0	0	1	1	1
5	1	1	1	0	0	0	1	1	1
6	0	0	0	1	1	1	0	0	0
7	0	0	0	1	1	1	0	0	0
8	0	0	0	1	1	1	0	0	0

Referencias

Nuutila, E., Efficient Transitive Closure Computation in Large Digraphs(Inglés). Acta Polytechnica Scandinavica, Mathematics and Computing in Engineering Series No. 74, Helsinki 1995, 124 pages. Published by the Finnish Academy of Technology. ISBN 951-666-451-2, ISSN 1237-2404, UDC 681.3.

Afrati F., E. Bampis, L. Finta y I. Milis, Scheduling trees with large communication delays on two identical processors. Journal of Scheduling ISSN: 1094-6136 (Impreso) 1099-1425 (En línea), 8(2), 179-190 (2005) http://link.springer.com/article/10.1007%2Fs10951-005-6366-3 Acceso: 6 de Agosto (2013).

Bibliografía

Colaboradores de Wikipedia. Clausura transitiva [en línea]. Wikipedia, La enciclopedia libre, 2013 [fecha de consulta: 2 de marzo del 2017]. Disponible en <https://es.wikipedia.org/w/index.php?title=Clausura_transitiva&oldid=64794579>.

Enlaces externos

Relaciones binarias

Combinaciones

Definición

Una k-combinación de elementos de un conjunto, es una selección sin ordenar de $k$ elementos de un conjunto $n$ , es decir, un subconjunto de $k$ elementos. En definitiva, está asociada al tipo de aplicación inyectiva, en donde los elementos son indistinguibles y los recipientes distinguibles.

El número de k-combinaciones de un conjunto de $n$ elementos se denota por $C(n,k)$ , el cual, también se puede escribir como ${n \choose k}$ , expresión que se llama coeficiente binomial.

Teorema (1)

El número de k-combinaciones de un conjunto de $n$ elementos, donde $n$ es un entero no negativo y $k$ es un entero tal que $0<=k=>n$ , es :

$C(n,k)={\frac {n!}{k!(n-k)!}}$

Demostración (1)

El número de k-combinaciones de un conjunto de $n$ elementos se puede calcular utilizando la fórmula para el número de k-permutaciones del conjunto. Para ello, hay que observar que las k-permutaciones se obtienen formando primero todas las k-combinaciones posibles y considerando, para cada una de ellas, las diferentes ordenaciones posibles. Por tanto, la demostración del anterior teorema, que proporciona una fórmula para $C(n,k)$ , está basada en esta observación.

Es decir:

$P(n,k)=C(n,k)*P(k,k)$ .

Esto implica que :

$C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {n!}{k!(n-k)!}}$

Teorema (2)

Este teorema muestra una identidad para el número de k-combinaciones de un conjunto, la cual simplifica la fórmula descrita en el Teorema 1.

Sean $n$ y $k$ enteros no negativos tales que $k<=n$ . Entonces:

$C(n,k)=C(n,n-k)$ .

Demostración (2)

$C(n,k)={\frac {n!}{k!(n-k)!}}$

y

$C(n,n-k)={\frac {n!}{(n-k)![n-(n-k)!}}={\frac {n!}{k!(n-k)!}}$

Lo cual demuestra que : $C(n,k)=C(n,n-k)$ . Esta demostración, se puede comprobar también, viendo que los dos términos de la ecuación cuentan el mismo número de objetos de dos formas distintas.

Ejemplo

¿De cuántas formas se pueden elegir a tres personas en un grupo con ocho personas para formar comisiones?

Al no importar el orden, la solución viene dada por el número de 3-combinaciones de un conjunto de ocho elementos:

$C(8,3)={\frac {8!}{3!(8-3)!}}=56$

Combinaciones con repetición

Definición

Una combinación con repetición es una aplicación de un conjunto $A$ en $\left\lbrace 0,1,\ldots ,k\right\rbrace$ , que a cada elemento de $A$ le asocia el número de veces que aparece repetido (entre $0$ y $k$ ), sujeta a la condición de que la suma de tales números sea $k$ .

Teorema

El número de estas combinaciones con repetición es: ${\begin{aligned}CR_{n,k}&={\binom {n+k-1}{k}}\end{aligned}}\ \ \ \ \ (1)$

Una notación alternativa para $CR_{n,k}$ es $\left(\!\!{\binom {n}{k}}\!\!\right)$ .

Interpretaciones

$CR_{n,k}$ es el número total de selecciones, con repetición, de tamaño $k$ , de una colección de $n$ objetos.
$CR_{n,k}$ es el número total de multiconjuntos de $k$ elementos provenientes de un conjunto de $n$ elementos.
$CR_{n,k}$ es el número total de formas de repartir $k$ objetos entre $n$ personas.
$CR_{n,k}$ es el número total de soluciones enteras de la ecuación $x_{1}+x_{2}+\cdots +x_{n}=k$ , siendo $x_{i}\geq 0$ , para todo $i\in \left\lbrace 1,2,\ldots ,n\right\rbrace$ .
$CR_{n,k}$ es el número total de formas de distribuir $k$ objetos indistinguibles en $n$ recipientes distinguibles, sin restricción alguna.

Teorema

Trivialmente: ${\begin{aligned}CR_{n,k}&=C_{n+k-1,k}\end{aligned}}\ \ \ \ \ (2)$

Interpretaciones derivadas, I

$CR_{n,k}$ es el número total de subconjuntos de $k$ elementos de un conjunto de $n+k-1$ elementos.
$CR_{n,k}$ es el número total de caminos en una cuadrícula de tamaño $k\times (n-1)$ .
$CR_{n,k}$ es el número total de sucesiones finitas de unos y ceros, de longitud $n+k-1$ que contienen exactamente $k$ unos y $n-1$ ceros.

Teorema

Trivialmente: ${\begin{aligned}CR_{n,k}&=PR_{n-1,k}\end{aligned}}\ \ \ \ \ (3)$

Interpretaciones derivadas, II

$CR_{n,k}$ es el número total de aplicaciones sobreyectivas de un conjunto $A$ de $n+k-1$ elementos en un conjunto de $2$ elementos, $B=\left\lbrace b_{1},b_{2}\right\rbrace$ , sujeto a las condiciones siguientes: $n-1$ elementos de $A$ tienen la misma imagen $b_{1}\in B$ y $k$ elementos de $A$ tienen la misma imagen $b_{2}\in B$ , siendo además, $\left(\forall i,j\right)\left(i\neq j\Rightarrow b_{i}\neq b_{j}\right)$ .
$CR_{n,k}$ es el número total de palabras de longitud $n+k-1$ en la que aparecen solo dos letras $l_{1}$ y $l_{2}$ de un alfabeto determinado, si bien repetidas, una $n-1$ veces y la otra, $k$ veces.

Conjetura de Collatz

Conocida como la conjetura de Collatz, la conjetura 3n + 1, la conjetura 3x + 1, el algoritmo de Hasse, el problema de Kakutani, el problema de Ulam, la sucesión de Hailstone, los números de Hailstone o la conjetura de Thwaite.

Esta conjetura fue enunciada por el matemático Lothar Collatz, en 1937, y hoy en día todavía no se ha resuelto.

Enunciado

Su enunciado es bastante elemental y de fácil comprensión:

Se elige cualquier número natural (n) y se realiza los siguientes cálculos:

Si n es par divide entre 2.

Si n es impar multiplica por 3 y suma 1 al resultado.

Con mayor formalidad:

$f(n)={\begin{cases}{\tfrac {n}{2}},&{\mbox{si }}n{\mbox{ es par}}\\3n+1,&{\mbox{si }}n{\mbox{ es impar}}\end{cases}}$

Ejemplos

Si n=5, obtenemos la siguiente serie 5,16,8,4,2,1

Si n = 6 →→ → 6, 3, 10, 5, 16, 8, 4, 2, 1

Si n=13 →→ → 13,40,20,10,5,16,8,4,2,1

La conjetura de Collatz desde otra perspectiva

Otro algoritmo, derivado del original, es el inverso de Collatz. Este algoritmo consiste en:

1º Escoger un numero aleatorio impar no múltiplo de 3.
2º Multiplicar dicho numero sucesivamente por 2 de manera que se llegue a un número tal que restándole 1 sea múltiplo de 3.
3º Dividir ese número entre 3 y volver a retormar el algoritmo.

De esta forma siempre parece ser que se finaliza en un múltiplo de 3, sin tener en cuenta el caso del número 1.

Estado del arte

80 años después de que haya sido enunciada, todavía nadie ha demostrado su veracidad, aunque gracias a las computadoras los cálculos se han mucho más rápidos y fáciles de realizar. También, se ha podido comprobar que para números hasta 2 elevado a 58, la secuencia acaba siempre en 1. Esto significa que esta conjetura es verdadera para una gran cantidad de números. Esto nos hace pensar, por intuición, que debería ser cierta, pero esto no sirve como demostración.

En la actualidad, una gran cantidad de matemáticos están inmersos en intentar demostrar dicha conjetura, lo cual, ha provocado, junto con otros estudios de diversas conjeturas, un gran avance de las matemáticas.

Algoritmo

#include <iostream>
using namespace std;

int main() {
	long long int n;
	cout << "Introduzca un número entero" << endl;
	cin>> n;

	while ( n > 1) {
		if (n%2== 0) { //si es par
			n = n/2;
			cout << n<< endl;
		}
		else { //impar
			n = 3*n + 1;
			cout << n<< endl;
		}

	}
	return 0;
}

Ampliación de la conjetura de Collatz para otros conjuntos numéricos

En el ámbito de los enteros

Una ampliación de la conjetura de Collatz es incluir el conjunto $Z$ . Excluyendo el 0, exiten 4 iteraciones, cuyos valores acaban repitiéndose de forma periódica. Estos son los cuatro ciclos:

Iteración	Valor inicial	Pasos de la iteración
1 → 4 → 2 → 1 …	1	3
−1 → −2 → −1 …	1	2
−5 → −14 → −7 → −20 → −10 → −5 …	2	5
−17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17 …	7	18

Generalizando, podemos afirmar que todo entero que comienza una iteración (que viene dada por f acaba concluyendo en uno de los cuatro ciclos expuestos anteriormente.

Indecidibilidad

¿Será indecidible la conjetura de Collatz? Stuart A. Kurtz y Janos Simon, en 2007, basándose en un resultado previo de John Horton Conway (1970) para una generalización natural de la conjetura^[1], demostraron que el problema generalizado de Collatz es indecidible^[2].

Referencias

↑ Contribuyentes de la Wikipedia inglesa (2017), «Collatz conjecture: Undecidable generalizations», Wikipedia, The Free Encyclopedia.
↑ Kurtz, Stuart A.; Simon, Janos, «The Undecidability of the Generalized Collatz Problem», en: Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, celebrado en Shanghai, China, en mayo de 2007. ISBN 3-540-72503-2. (DOI = 10.1007/978-3-540-72504-6 49).

Véase también

Conjetura de Collatz

Enlaces externos

Contribuyentes de la Wikipedia inglesa (2017) Collatz conjecture. Wikipedia, The Free Encyclopedia.

arXiv:

Terry Tao:
- Terry Tao (2011) The Collatz conjecture, Littlewood-Offord theory and powers of 2 and 3.

Estrategias:
- Amir Zoet, Johan Mogens Følsgaard, Rasmus Krisoffer Pedersen & Kasper Emil Dueholm Freiman (2015) On the strategies used to attack unsolved mathematical problems: a case study of the Collatz Conjecture, Roskilde University

Intentos populares:
- Paul S. Bruckman:
  - John C. Turner: Paul S. Bruckman and Number Theory
Computación distribuida (proyecto BOINC)
- Collatz project at BOINC (logros: http://boinc.thesonntags.com/collatz/highest_steps.php)

Visualización:
- Collatz Graph: All Numbers Lead to One, de Jason Davies
- La fractal de Collatz

Informes técnicos:
- An analysis of the Collatz Conjeture

Foros públicos de discusiones matemáticas:
- Stack Exchange: https://stackexchange.com/search?q=collatz (son muchas comunidades especializadas: https://stackexchange.com/sites#)
- Reddit: https://www.reddit.com/r/math/search?q=collatz
- Quora
- PlanetMath: http://planetmath.org/node/18676
- Mathforum: http://mathforum.org/kb/search!execute.jspa?q=collatz

Comunidades:

Researchgate: Jeffrey C. Lagarias (2010) The 3x+1 Problem: An Overview

Software específico:

Matheroboter: Das Collatz Problem

Otros (incluyendo demostraciones y explicación del error, muy útiles, o sin localizar ni explicar los errores, solo «lanzando» una demostración a la Red, y otras divagaciones en paralelo):

Trabajos fin de grado, de máster, tesinas, tesis:

Presencia en la literatura, cine, etc.:
- Wajdi Mouawad, Incendios (libro, obra de teatro, también en: http://vps280516.ovh.net/divulgamat15/index.php?option=com_content&view=article&id=14658:66-diciembre-2012-incendies-de-wajdi-mouawad&catid=69:teatro-y-matemcas&Itemid=46, y película: http://vps280516.ovh.net/divulgamat15/index.php?option=com_content&view=article&id=12519&Itemid=46).
- Serie Numbers

Variantes de la conjetura:
- Justin Paul Skycak, Numerical Investigation of the 3n+1 Problem and its Continuous Extension, Scientia, Vol. 6, Spring 2015, pp. 26-31

Criterio de divisibilidad

Restos potenciales

En la teoría de la divisibilidad, se denominan restos potenciales del número natural $n$ respecto a un módulo dado m a los restos producidos por las distintas potencias naturales de n.

Propiedades de los restos potenciales

Si el módulo tiene algún factor primo con n, se alcanzará una potencia múltipo del módulo y por ello, todos los restos que siguen serán 0.

Si el módulo es primo con n, se producirá una periodicidad en los restos, cuyo periodo se conoce como índice o gausiano de n respecto del módulo. El resto 1 tendrá lugar en los múltiplos de ese índice.

Si el máximo común divisor (n,m) = d, siendo $d>1$ los restos potenciales tendrán tanto una parte no periódica como otra parte que sí lo será.

Ejemplo de resto potencial

Por ejemplo, los restos potenciales de 5 respecto al módulo 3 son:

De  $5^{0}$  el resto es 1, de  $5^{1}$  el resto es 2 , de  $5^{2}$  el resto es 1 , de  $5^{3}$  el resto es 2 y así siguen de forma periódica.

Restos cuadráticos

Un elemento a perteneciente a una clae de restos de un determinado módulo $m$ , siendo $a$ primo con el módulo, hablamos de resto cuadrático cuando es resto potencial de algún cuadrado, esto es, exite un $n:n^{2}\equiv a(modm)$ . Si esto no se cumple, no se podrá hablar de resto cuadrático.

Criterio general de divisibilidad en base $10$

Sean $k\in \mathbb {Z} ^{+}$ , $I=\left\lbrace 0,\ldots ,k\right\rbrace$ y $n=n_{0}+n_{1}\cdot 10+n_{2}\cdot 10^{2}+\cdots +n_{k}\cdot 10^{k}$ , siendo $(\forall i\in I)(n_{i}\in \mathbb {N} \wedge 0\leq n_{i}<10)$ . Sean $r_{i}$ , con $i\in I$ , los restos potenciales de $10$ , módulo $m$ , esto es, $10^{i}\equiv r_{i}(mod\;m)$ . Entonces: $m\mid n\Leftrightarrow m\mid \left(n_{0}+n_{1}r_{1}+n_{2}r_{2}+\cdots +n_{k}r_{k}\right)$ .

Criterio general de divisibilidad

Sean $k\in \mathbb {Z} ^{+}$ , $I=\left\lbrace 0,\ldots ,k\right\rbrace$ y $n=n_{0}+n_{1}\cdot b+n_{2}\cdot b^{2}+\cdots +n_{k}\cdot b^{k}$ , siendo $(\forall i\in I)(n_{i}\in \mathbb {N} \wedge 0\leq n_{i}<b)$ . Sean $r_{i}$ , con $i\in I$ , los restos potenciales de $b$ , módulo $m$ , esto es, $b^{i}\equiv r_{i}(mod\;m)$ . Entonces: $m\mid n\Leftrightarrow m\mid \left(n_{0}+n_{1}r_{1}+n_{2}r_{2}+\cdots +n_{k}r_{k}\right)$ .

Enlaces externos

Robert T. Kurosaka (1986) Mahematical Recreations: Euclid's Algorithm (GCDs, LCMs and repeating decimals). In: Byte Magazine Volume 11 Number 01: Robotics (from https://archive.org/details/byte-magazine)

Interpolación polinomial de Newton en diferencias divididas

El método de interpolación polinómica de Newton es uno de los métodos de interpolación polinómica que existen. Aunque el polinomio que se encuentra para una serie de puntos es único, es fácil extenderlo si se añade un nuevo punto ya que la información previa se sigue manteniendo. Otra de las ventajas de utilizar este método es que con pocos puntos el grado del polinomio es muy bajo.

Definición de pendiente

El primer paso para hallar la fórmula de la interpolación es definir la pendiente de orden $n$ de manera recursiva:

$f_{0}(x_{i})$ : término i-ésimo de la secuencia
$f_{1}(x_{0},x_{1})={\frac {f_{0}(x_{1})-f_{0}(x_{0})}{x_{1}-x_{0}}}$
$f_{2}(x_{0},x_{1},x_{2})={\frac {f_{1}(x_{1},x_{2})-f_{1}(x_{0},x_{1})}{x_{2}-x_{0}}}$

En general:

$f_{i}(x_{0},x_{1},\ldots ,x_{i-1},x_{i})={\frac {f_{i-1}(x_{1},\ldots ,x_{i-1},x_{i})-f_{i-1}(x_{0},x_{1},\ldots ,x_{i-1})}{x_{i}-x_{0}}}$ ,

donde $x_{i}-x_{j}$ representa la distancia entre dos elementos (por ejemplo, se puede tener el elemento en $x=3$ y $x=5$ pero desconocer el valor de la secuencia en $x=4$ ).

Puede apreciarse cómo en la definición general se usa la pendiente del paso anterior, $f_{i-1}(x_{1},\ldots ,x_{i-1},x_{i})$ , a la cual se le resta la pendiente previa de mismo orden, es decir, el subíndice de los términos se decrementa en $1$ , como si se desplazara, para obtener $f_{i-1}(x_{0},x_{1},\ldots ,x_{i-1})$ .

Nótese también que aunque el término inicial siempre es $x_{0}$ , este puede ser en realidad cualquier otro, por ejemplo, se puede definir $f_{1}(x_{i-1},x_{i})$ de manera análoga al caso mostrado arriba.

Definición del polinomio

Una vez conocemos la pendiente, ya es posible definir el polinomio de grado $n$ de manera también recursiva:

$p_{0}(x)=x_{0}$ . Se define así ya que este valor es el único que se ajusta a la secuencia original para el primer término.
$p_{1}(x)=p_{0}(x)+f_{1}(x_{0},x_{1})*(x-x_{0})$ (dado que multiplicamos por $x-x_{0}$ , si $x=x_{0}$ el término se cancela, preservando así la información de $p_{0}(x)$ ; sin embargo, al ser $f_{1}(x_{0},x_{1})$ la pendiente [la diferencia entre dos términos] y multiplicarla por $x$ , obtenemos también el segundo término de la secuencia).
$p_{2}(x)=p_{1}(x)+f_{2}(x_{0},x_{1},x_{2})*(x-x_{0})*(x-x_{1})$ .

En general:

$p_{i}(x)=p_{i-1}(x)+f_{i}(x_{0},x_{1},\ldots ,x_{i-1},x_{i})\prod _{j=0}^{i-1}(x-x_{j})$

Ejemplos

Pongamos como ejemplo la secuencia $f_{0}$ tal que $f_{0}(1)=6,f_{0}(2)=9,f_{0}(3)=2$ y $f_{0}(4)=5$ , es decir, son los términos $6,9,2,5$ para $x_{0}=1$ hasta $x_{3}=4$ .

Se obtiene las pendientes de orden $1$ de la siguiente forma:

$f_{1}(x_{0},x_{1})={\frac {f_{0}(x_{1})-f_{0}(x_{0})}{x_{1}-x_{0}}}={\frac {9-6}{2-1}}=3$
$f_{1}(x_{1},x_{2})={\frac {f_{0}(x_{2})-f_{0}(x_{1})}{x_{2}-x_{1}}}={\frac {2-9}{3-2}}=-7$
$f_{1}(x_{2},x_{3})={\frac {f_{0}(x_{3})-f_{0}(x_{2})}{x_{3}-x_{2}}}={\frac {5-2}{4-3}}=3$

Una vez tenemos la pendientes de orden $1$ , es posible obtener las de siguiente orden:

$f_{2}(x_{0},x_{1},x_{2})={\frac {f_{1}(x_{1},x_{2})-f_{1}(x_{0},x_{1})}{x_{2}-x_{0}}}={\frac {-7-3}{3-1}}=-5$
$f_{2}(x_{1},x_{2},x_{3})={\frac {f_{1}(x_{2},x_{3})-f_{1}(x_{1},x_{2})}{x_{3}-x_{1}}}={\frac {3-(-7)}{4-2}}=5$

Por último, definimos la pendiente de orden $3$ :

$f_{3}(x_{0},x_{1},x_{2},x_{3})={\frac {f_{2}(x_{1},x_{2},x_{3})-f_{2}(x_{0},x_{1},x_{2})}{x_{3}-x_{0}}}={\frac {5-(-5)}{4-1}}={\frac {10}{3}}$

Una vez tenemos la pendiente, podemos definir los consecuentes polinomios:

$p_{0}(x)=6$ .
$p_{1}(x)=6+3(x-1)$
$p_{2}(x)=6+3(x-1)-5(x-1)(x-2)$ .
$p_{3}(x)=6+3(x-1)-5(x-1)(x-2)+{\frac {10}{3}}(x-1)(x-2)(x-3)$

Podemos probar por ejemplo la interpolación lineal para el valor $1.5$ , que resulta ser $p_{1}(1.5)=6+3(1.5-1)=7.5$ . Efectivamente, al ser una recta, podemos ver que este valor es igual a $3+{\frac {3+6}{2}}=7.5$ , el punto medio entre ambos (más el punto inicial, $3$ ).

Enlaces externos

Colaboradores de Wikipedia (2012ss.) Interpolación polinómica de Newton. Wikipedia, La enciclopedia libre, https://es.wikipedia.org/wiki/Interpolación_polinómica_de_Newton
A. K. Dewdney on The Internet Archive
- The Tinkertoy Computer and other machinations (Chapter 17: Automated Math) (Juegos de ordenador. De cómo un par de programas obtusos pasan por genios en los tests de inteligencia. Investigación y Ciencia, mayo, 1986. pp. 94-98, Prensa Científica, S. A.)
Sequence solver, by AlteredQualia
Leon Q. Brin (2016) Tea Time Numerical Analysis. Experiences in Mathematics, 2nd ed., CC BY-SA (§ 3.3)
Steven C. Chapra & Raymond P. Canale (2010) Numerical methods for Engineers, McGraw-Hill Science/Engineering/Math, 6th ed., ISBN: 9780072918731, § 18.1, http://openlibrary.org/books/OL7305712M/Numerical_Methods_for_Engineers
Steven C. Chapra & Raymond P. Canale (2007) Métodos numéricos para ingenieros, 5ª ed., § 18.1
Steven C. Chapra & Raymond P. Canale (2010) Numerical methods for Engineers, 6th ed., § 18.1 / Steven C. Chapra & Raymond P. Canale (2007) Métodos numéricos para ingenieros, 5ª ed., § 18.1
Walter Mora (2016) Introducción a los métodos numéricos (§ 2.6 ff.)
Ibáñez Pérez, María José, Notas sobre Interpolación polinómica

Notas

Inversión de programas

Introducción

La meta principal de la Ingeniería Inversa es obtener información sobre un producto accesible, con el objetivo de determinar cómo funciona y cómo esta fabricado. 1

En la actualidad los productos que son objeto de este tipo de Ingeniería son los componentes electrónicos, los programas de las computadoras y los procesadores.

En el caso concreto del software, esta ingeniería hace referencia al análisis de un programa cuyo código fuente no está disponible, analizando su función y comportamiento y siendo capaz de crear otro programa con un código, que realice las mismas funciones.

Para aquellas personas que nunca hayan oído hablar de la ingeniería inversa, aquí hay un link para principiantes.

Conceptos

La ingeniería inversa trata de conseguir información de algún producto disponible al público. Cuando aplicamos esta ingeniería inversa para saltar protecciones de software suele recibir el nombre de Cracking. De esta manera, esta ingeniería intenta tomar un elemento, un producto determinado para estudiar su comportamiento y composición para duplicar el mismo creando una copia fiel. El método se denomina así porque avanza en dirección opuesta a las tareas habituales de ingeniería, que consisten en utilizar datos técnicos para elaborar un producto determinado. En general, si el producto u otro material que fue sometido a la ingeniería inversa fue obtenido en forma apropiada, entonces el proceso es legítimo y legal. De la misma forma, pueden fabricarse y distribuirse, legalmente, los productos genéricos creados a partir de la información obtenida de la ingeniería inversa, como es el caso de algunos proyectos de Software libre ampliamente conocidos.

El programa Samba es un claro ejemplo de ingeniería inversa, dado que permite a sistemas operativos UNIX compartir archivos con sistemas Microsoft Windows. El proyecto Samba tuvo que investigar información confidencial (no liberada al público en general por Microsoft) sobre los aspectos técnicos relacionados con el sistema de archivos Windows. Lo mismo realiza el proyecto WINE para el conjunto de API de Windows y OpenOffice.org con los formatos propios de Microsoft Office, o se hace para entender la estructura del sistema de archivos NTFS y así poder desarrollar drivers para la lectura-escritura sobre el mismo (principalmente para sistemas basados en GNU/Linux).

La ingeniería inversa es un método de resolución. Aplicar ingeniería inversa a algo supone profundizar en el estudio de su funcionamiento, hasta el punto de que podamos llegar a entender, modificar y mejorar dicho modo de funcionamiento.

Pero este término no sólo se aplica al software, sino que también se considera ingeniería inversa el estudio de todo tipo de elementos (por ejemplo, equipos electrónicos, microcontroladores, u objeto fabril de cualquier clase). Diríamos, más bien, que la ingeniería inversa antecede al nacimiento del software, tratándose de una posibilidad a disposición de las empresas para la producción de bienes mediante copiado1 desde el mismo surgimiento de la ingeniería. En el caso concreto de la programación inversa se basa en el concepto de invertir programas consiguiendo nuestro programa principal sin los cambios que hemos originado al incluir líneas de código, así como ejemplo básico tendríamos:

Sea un programa “P” que parta de un entero “x” y su cambio sea x =x+1 , el inverso de ese programa “P^-1” sería x =x-1 , de este modo conseguiriamos nuestro programa principal sin tener que recurrir a eliminar código.

Para poder invertir el funcionamiento de un programa hay que conocer el funcionamiento de las inversiones de control. Estas se producen en los frameworks que se diferencian de las librerias por la capacidad de llamar al propio código del usuario, el programa es capaz de controlar acciones que serian realizadas a traves de el poder del usuario, como por ejemplo en el control a traves de las ventanas del SO.

Hay programas sencillos que son fácilmente invertibles. Por ejemplo, en el caso de "x=x+1", su inversa sería "(x=x+1)^-1", que sería "x=x-1"P. Pero en otros casos se necesita conocer previamente el valor de la variable para poder invertir dicho código. Un ejemplo de este tipo de problema es este: La inversa de "{Para x=3}, x=1" es "{Para x=1}, x=3". La primera empieza con "x=3" y acaba con "x=1"; mientras que la segunda realiza lo contrario. Este ejemplo nos muestra que junto a cada algoritmo de inversión de, programas debemos incluir las PRE y/o POST condiciones.

Hay otros tipos de programas que no son invertibles, como por ejemplo el caso de "x=x*x", en el que dos valores iniciales para las variables dan lugar a un mismo resultado, en lugar de obtener resultados distintos para cada valor de entrada.

Ejemplos

Un ejemplo de un programa que es a la vez su inverso puede implementarse de manera sencilla en Python. En este ejemplo, el programa pide una entrada (una "contraseña") y una frase a encriptar. A continuación, ejecuta F[i] XOR C[i MÓDULO L] (donde L = length(C)). Si se repite esta operación sobre el resultado F_prima, se obtiene F de nuevo.

frase = input('Introduzca la frase: ')
contr = input('Introduzca la contraseña: ')

# Convertimos los caracteres a números
f_num = [ord(c) for c in frase]
f_con = [ord(c) for c in frase]

# Aplicamos XOR
f_res = [f_num[i] ^ f_con[i % len(f_con)] for i in range(len(f_num))]
resul = ''.join([chr(n) for n in f_res])

# Imprimimos el resultado
print(result)

Programación en Prolog

Existen dos tipos de cláusulas: Hechos y Reglas. Una regla es del tipo:

Cabeza :- Cuerpo.

y se lee como "La cabeza es verdad si el cuerpo es verdad". El cuerpo de una regla consiste en llamadas a predicados, que son llamados los objetivos de las reglas. El predicado ,/2 (es decir, un operador de paridad 2 (que recibe 2 argumentos) y de nombre , ) denota conjunción de objetivos, y el operador ;/2 denota disyunción. Conjunciones y disyunciones pueden sólo aparecer en el cuerpo, no en la cabeza de la regla. En realidad la disyunción no es un operador básico o predefinido, sino que está meta-programado así:

';' (A,_) :- A.

';' (_,B) :- B.

Las cláusulas sin cuerpo (es decir, antecedente) son llamados hechos porque siempre son ciertos. Un ejemplo de un hecho es:

gato(tom).

que es equivalente a la regla:

gato(tom) :- true.

El predicado predefinido true/0 siempre es verdad.

Dado el hecho anterior, se puede preguntar:

¿ es tom un gato?

?- gato(tom).  
Yes

¿ que cosas son gatos?

?- gato(X).  
X = tom

Ejemplo simple

%%
%% declaraciones
%%
padrede('juan', 'maria'). % juan es padre de maria
padrede('pablo', 'juan'). %pablo es padre de juan
padrede('pablo', 'marcela'). % pablo es padre de marcela
padrede('carlos', 'debora'). % carlos es padre de debora

% A es hijo de B si B es padre de A
hijode(A,B) :- padrede(B,A).
% A es abuelo de B si A es padre de C y C es padre B
abuelode(A,B) :- 
   padrede(A,C), 
   padrede(C,B).
% A y B son hermanos si el padre de A es también el padre de B y si A y B no son lo mismo
hermanode(A,B) :- 
   padrede(C,A) , 
   padrede(C,B), 
   A \== B.        

% A y B son familiares si A es padre de B o A es hijo de B o A es hermano de B
familiarde(A,B) :- 
   padrede(A,B).
familiarde(A,B) :-
   hijode(A,B). 
familiarde(A,B) :- 
   hermanode(A,B).
%%
%% consultas
%%
% juan es hermano de marcela?
?- hermanode('juan', 'marcela').
yes

% carlos es hermano de juan?
?- hermanode('carlos', 'juan').
no

% pablo es abuelo de maria?
?- abuelode('pablo', 'maria').
yes

% maria es abuela de pablo?
?- abuelode('maria', 'pablo').
no

Estado del arte

La inversión de código de programas tiene una fuerte relación con la estructura englobada en el proceso. Es necesario, por tanto, mencionar Spring Framework, una estructura para la aplicación del proceso de inversión de control, introducida para las distribuciones Java. Esta inversión de control es el marco en el que se engloba la inversión de código, ya que sigue la misma línea de tal metodología: en vez de ser el programador el que especifica la secuencia de instrucciones y procedimientos a lo largo del ciclo de ejecución de un programa, este llevará a cabo la especificación de las respuestas deseadas a solicitudes de datos con el fin de que el propio programa o estructura module las acciones de control del flujo del programa y su orden necesario de los tales, en vías de las respuestas introducidas. Spring framework fue introducida para la distribución java.

Herramientas

La Ingeniería Inversa requiere algunas herramientas especializadas que no son normalmente familiares para muchos usuarios (e incluso para muchos desarrolladores de software). Esta sección discutirá algunas de las herramientas comunes usadas en ingeniería inversa, y enumeraremos las herramientas usadas en los ejemplos de este wikilibro. Los siguientes capítulos discutirán estos tópicos en mayor detalle:

Desensambladores

Un desensamblador es un programa de computador que traduce el lenguaje de máquina a lenguaje ensamblador, la operación inversa de la que hace el ensamblador. El desensamblador difiere de un decompilador, en que éste tiene como objetivo un lenguaje de alto nivel en vez de al lenguaje ensamblador. la salida de un desensamblador, el desensamblado, es a menudo formateada para la legibilidad humana en vez de ser adecuada para la entrada a un ensamblador, haciendo que éste sea principalmente una herramienta de ingeniería inversa.

Descompiladores

De manera semejante al desensamblado, la descompilación lleva el proceso un paso mas allá e intenta reproducir el código a un lenguaje de alto nivel. Frecuentemente, este lenguaje es C, porque C es simple y lo suficientemente primitivo para facilitar el proceso de descompilación. La descompilación tiene sus problemas, porque muchos datos y construcciones para legibilidad se pierden durante el proceso original de descompilación, y no pueden ser reproducidos. Puesto que esta disciplina es todavia joven, y los resultados son razonablemente buenos pero no excelentes, esta página se limitará a dar una lista de descompiladores, y una breve discusión general de las posibilidades de la descompilación.

Depuradores

Los depuradores son, con la posible excepción de un descompilador potente, el mejor amigo de un ingeniero inverso. Un depurador permite al usuario ejecutar el programa paso a paso, y examinar varios valores y acciones.

Ingeniería Inversa/Editores Hexadecimales

Un editor hexadecimal (o editor de archivos binarios) es un tipo de programa informático que permite a un usuario modificar archivos binarios. Los editores hexadecimales fueron diseñados para editar sectores de datos de disquetes o discos duros por lo que a veces se llaman "editores de sectores".

Intérpretes

En ciencias de la computación, intérprete o interpretador es un programa informático capaz de analizar y ejecutar otros programas. Los intérpretes se diferencian de los compiladores o de los ensambladores en que mientras estos traducen un programa desde su descripción en un lenguaje de programación al código de máquina del sistema, los intérpretes sólo realizan la traducción a medida que sea necesaria, típicamente, instrucción por instrucción, y normalmente no guardan el resultado de dicha traducción.

Usando un intérprete, un solo archivo fuente puede producir resultados iguales incluso en sistemas sumamente diferentes (ejemplo. una PC y una PlayStation 4). Usando un compilador, un solo archivo fuente puede producir resultados iguales solo si es compilado a distintos ejecutables específicos a cada sistema.

Los programas interpretados suelen ser más lentos que los compilados debido a la necesidad de traducir el programa mientras se ejecuta, pero a cambio son más flexibles como entornos de programación y depuración (lo que se traduce, por ejemplo, en una mayor facilidad para reemplazar partes enteras del programa o añadir módulos completamente nuevos), y permiten ofrecer al programa interpretado un entorno no dependiente de la máquina donde se ejecuta el intérprete, sino del propio intérprete (lo que se conoce comúnmente como máquina virtual).

Para mejorar el desempeño, algunas implementaciones de programación de lenguajes de programación pueden interpretar o compilar el código fuente original en una más compacta forma intermedia y después traducir eso al código de máquina (ej. Perl, Python, MATLAB, y Ruby). Algunos aceptan los archivos fuente guardados en esta representación intermedia (ej. Python, UCSD Pascal y Java).

En la actualidad, uno de los entornos más comunes de uso de los intérpretes es en los navegadores web, debido a la posibilidad que estos tienen de ejecutarse independientemente de la plataforma.

Implementaciones

Existen dos tipos de de implementaciones comunes de DIP(Principio de dependencia de inversión), que utilizan una arquitectura lógica similar, con diferentes implicaciones.

Un ejemplo podría ser una aplicación directa que empaqueta las clases políticas(clases o archivos que contienen los permisos que puede llegar a obtener un programa) con clases abstractas(interfaces) en una biblioteca. En esta implementación los componentes de alto nivel y bajo nivel se separan en paquetes(Java,C#) / bibliotecas(C++) separadas, donde las interfaces que definen los servicios requeridos por el componente de alto nivel dependen de la biblioteca del componente de alto nivel. La implementación de la interfaz del componente de alto nivel por el componente de bajo nivel requiere que el paquete de componentes de bajo nivel dependa del componente de alto nivel para la compilación, invirtiendo así la relación de dependencia tradicional.

En el segundo tipo de DIP, la dependencia de los componentes de las capas inferiores respecto a las interfaces en las capas superiores permiten la reutilización de la dificultad de los componentes de las capas inferiores. Este tipo de implementación, a diferencia del primer tipo, invierte la dependencia de arriba-abajo a abajo-arriba.

Tipos de ingenierías inversas del software

Ingeniería inversa de datos

La ingeniería inversa de datos suele producirse a diferentes niveles de abstracción. En el nivel de programa, es frecuente que sea preciso realizar una ingeniería inversa de las estructuras de datos internas del programa. En el nivel del sistema, es frecuente que se efectúe una reingeniería de las estructuras globales de datos para ajustarlas a los paradigmas nuevos de gestión de bases de datos.

Estructuras de datos internas. Las técnicas de ingeniería inversa para datos de programa internos se centran en la definición de clases de objetos. Esto se logra examinando el código del programa en un intento de agrupar variables de programa que estén relacionadas.

Para la ingeniería inversa de clases, se sugiere el enfoque siguiente:

– Identificación de los indicadores y estructuras de datos locales dentro del programa que registran información importante acerca de las estructuras de datos globales .

– Definición de la relación entre indicadores y estructuras de datos locales y las estructuras de datos globales.

– Para toda variable que represente una matriz o archivo, la construcción de un listado de todas las variables que tengan una relación lógica con ella.

Estructuras de bases de datos.Es un proceso de ingeniería del software por el cual se intenta comprender y redocumentar los archivos o las base de datos de una aplicación. Se trata de obtener el esquema lógico y el esquema conceptual de esta base de datos. Independientemente de su organización lógica y de su estructura física, las bases de datos permiten definir objetos de datos, y apoyan los métodos de establecer relaciones entre objetos.

Ingeniería inversa de logica

Se basa en comprender las abstracciones de los procedemientos, para ello se analiza el codigo en distintos niveles de abstracción:sistema, programa, componente, configuración y sentencia. Así pues, cada uno de los programas de que consta el sistema de aplicaciones representará una abstracción funcional con un elevado nivel de detalle. Todo se complica cuando se considera el código que reside en el interior del componente. El ingeniero busca las secciones del código que representan las configuraciones genéricas de procedimientos. En casi todos los componentes, existe una sección de código que prepara los datos para su procesamiento (dentro del componente), una sección diferente de código que efectúa el procesamiento y otra sección de código que prepara los resultados del procesamiento para exportarlos de ese componente. En el interior de cada una de estas secciones, se encuentran configuraciones más pequeñas.

Este tipo de ingeniería se suele utilizar para:

– Entender mejor la aplicación y regenerar el código.

– Migrar la aplicación a un nuevo sistema operativo.

– Generar/completar la documentación.

– Comprobar que el código cumple las especificaciones de diseño.

Para poder realizar la ingenieria inversa de procesos debemos de seguir los siguientes pasos:

– Buscamos el programa principal.

– Ignoramos inicializaciones de variables, etc.

– Inspeccionamos la primera rutina llamada y la examinamos si es importante.

– Inspeccionamos las rutinas llamadas por la primera rutina del programa principal, y examinamos aquéllas que nos parecen importantes.

– Repetimos los pasos 3-4 a lo largo del resto del software.

– Recopilamos esas rutinas “importantes”, que se llaman componentes funcionales.

– Asignamos significado a cada componente funcional, esto es , explicamos qué hace cada componente funcional en el conjunto del sistema y explicamos qué hace el sistema a partir de los diferentes componentes funcionales.

Ingeniería inversa de interfaces de usuarios

El nuevo desarrollo de interfaces de usuario ha pasado a ser uno de los tipos más comunes de las actividades de reingeniería.

¿Como podemos comprender el funcionamiento de una interfaz de usuario?

Para comprender totalmente una interfaz de usuario ya existente , es preciso especificar la estructura y comportamiento de la interfaz. Ademas se sugieren tres preguntas básicas a las cuales hay que responder cuando comienza la ingeniería inversa de la interfaz de usuario:

– ¿Cuáles son las acciones básicas que deberá procesar la interfaz?

– ¿Cuál es la descripción compacta de la respuesta de comportamiento del sistema a estas acciones?

– ¿Qué concepto de equivalencia de interfaces es relevante en este caso?

La notación de modelado de comportamiento puede proporcionar una forma de desarrollar las respuestas de las dos primeras preguntas indicadas anteriormente.

Gran parte de la información necesaria para crear un modelo de comportamiento se puede obtener mediante la observación de la manifestación extrema de la interfaz existente. Ahora bien, es preciso extraer del código la información adicional necesaria para crear el modelo de comportamiento. Ademas es importante indicar que una interfaz de usuario de sustitución puede que no refleje la interfaz antigua de forma exacta . Con frecuencia, merece la pena desarrollar metáforas de interacción nuevas.

Aplicaciones

Aplicaciones teóricas

La aplicación de la programación inversa nunca cambia la funcionalidad del programa sino que permite obtener cómo se ha construido el mismo. Su realización permite obtener los siguientes beneficios:

Reducir la complejidad del sistema: al intentar comprender el software se facilita su mantenimiento y la complejidad existente disminuye.
Generar diferentes alternativas: del punto de partida del proceso, principalmente código fuente, se generan representaciones gráficas lo que facilita su comprensión.
Recuperar y/o actualizar la información perdida (cambios que no se documentaron en su momento): en la evolución del sistema se realizan cambios que no se suele actualizar en las representaciones de nivel de abstracción más alto, para lo cual se utiliza la recuperación de diseño.
Evitar duplicación en el código: la estructura general de flujo de trabajo, está implementada una vez en el algoritmo de clase abstracta, y variaciones necesarias son implementadas en cada una de las subclases.
Detectar efectos laterales: los cambios que se puedan realizar en un sistema puede conducirnos a que surjan efectos no deseados, esta serie de anomalías puede ser detectados por la ingeniería inversa.
Facilitar la reutilización: por medio de la ingeniería inversa se pueden detectar componentes de posible reutilización de sistemas existentes, pudiendo aumentar la productividad, reducir los costes y los riesgos de mantenimiento.
Eliminar las dependencias entre el editor de texto y el corrector ortográfico.
Desarrollar programas que sean compatibles con otros programas, sin tener acceso a las características técnicas de estos últimos.

Éste sería un ejemplo de un patrón de diseño concreto respecto a la inversión de control denominado Template Method.

// Clase pública Delantero que hereda de la clase Jugador.
public class Delantero extends Jugador {

	// Atributo final y privado de tipo entero.
	private final int golesMarcados;

	// Constructor de la clase Delantero
	public Delantero(String nombre, int minutosJugados, int salario,
			int golesMarcados) {
		super(nombre, minutosJugados, salario);
		this.golesMarcados = golesMarcados;
	}     

	// Método público que retorna un número de coma flotante
	@Override
	public float calculaPuntosPorObjetivos() {
		return 30 * (golesMarcados / super.getPartidosJugados());
	}

	// Método público que retorna un valor de coma flotante
	@Override
	public float getPuntosPenalizacionPorSalarioAlto() {
		return (float) (salario * 0.1);
	}

}

Aplicaciones prácticas

Dentro del contexto de inversión de control, la inyección de dependencias es una técnica muy empleada para el diseño de objetos, en la cual básicamente se suministran objetos a una clase en lugar de que la propia clase cree los objetos.

A lo largo de la implementación en Java, la forma más habitual es a partir de un “CONTENEDOR DI”, el cual inyecta a cada objeto otros objetos necesarios según ciertas relaciones precondicionadas. Típicamente el contenedor es implementador a partir de una estructura de aplicación externa, tal como la anteriormente mencionada Spring Framework. La aplicación empleará la inversión de control al ser el contenedor el que invoque el código de la aplicación.

Ejemplo:

Sistema genealógico:

Un sistema genealógico puede representar la relación entre las personas como un gráfico de relaciones de primer nivel entre ellos (padre / hijo, padre / hija, madre / hijo, madre / hija, esposo / esposa, esposa / esposo ...). Esto es muy eficiente (y extensible: ex-marido / ex-esposa, tutor legal ...).

Dependiendo del uso del módulo genealógico, presentar relaciones comunes como propiedades directas distintas (esconder el gráfico) hará que el acoplamiento entre el módulo de alto nivel y el módulo genealógico sea mucho más ligero y permita cambiar la representación interna completamente sin ningún efecto En los módulos de uso. También permite insertar en el módulo genealógico la definición exacta de hermanos y hermanas (incluidos o no de medio hermanos), tíos ... que permitan hacer cumplir el principio de responsabilidad individual.

Por último, si el primer enfoque generalizado extensible parece ser el más extensible, el uso del módulo genealógico puede mostrar que una implementación de la relación más especializada y más simple es suficiente para la aplicación y le ayuda a hacer un sistema más eficiente.

En este ejemplo abstraer la interacción entre los módulos conduce a una interfaz simplificada del módulo de bajo nivel y puede conducir a una implementación más sencilla de la misma.

Otra aplicación muy conocida de la ingeniería inversa es conocer el funcionamiento de un programa generalmente comercial, para así poder conocer su algoritmo interno y el que determina como será licenciado el software, es decir podemos dar con un serial válido para usar el programa. El proceso de hacerle ingeniería inversa a un programa consiste en utilizar programas denominados “Debuggers” que permiten conocer el código interno del programa, pero generalmente lo muestra en lenguaje entendible para la maquina. Por ejemplo uno de los debuggers más conocidos y usados es el programa alemán OllyDBG, que permite “destripar” un ejecutable para conocer su código ensamblador interno, y así por medio de la lectura de este podemos conocer el algoritmo que usaron para licencia el programa. Una vez se haya dado con el algoritmo, el cracker puede crear generadores automáticos de seriales o incluso realizar una pequeña copia del ejecutable original pero parcheado, es decir con el salto de instrucciones que permite licenciar el software. Para prevenir esto las compañías de seguridad crearon los empaquetadores, que son programas que contienen un algoritmo único que encripta el código del ejecutable original, lo que hace más difícil crackearlo, además algunos de estos empaquetadores también permiten comprimir el ejecutable, lo que supone una gran ventaja para las desarrolladores. Aunque generalmente estos programas cuestan mucho dinero y esto supone un gran gasto de dinero para quién desarrolló el programa, aunque esto no debería de ser un problema si se quiere mantener un producto estable en el mercado.

Véase también

David Gries

Referencias

A continuación, se dispondrán las páginas usadas como modelos en este artículo:

Dependency inversion principle (Información generalizada sobre la reingeniería)[1]

Patrones[2]

Algunas aplicaciones[3]

Herramientas[4]

DesensambladorDesensamblador

Descompiladores[5]

Depuradores[6]

Editor hexadecimalEditor hexadecimal

Bibliografía

Enlaces externos

Rustan, K., Leino, M., 1994, Computing permutation encodings, sección 2.4: «Inverting the program», California Institute of Technology, Pasadena, CA, USA, http://authors.library.caltech.edu/26789/1/postscript.pdf
Colaboradores de Wikipedia. Ingeniería inversa [en línea]. Wikipedia, La enciclopedia libre, 2017 [fecha de consulta: 24 de febrero del 2017]. Disponible en <https://es.wikipedia.org/w/index.php?title=Ingenier%C3%ADa_inversa&oldid=96133093>
Categoría 'Reversible computing' (en la Wikipedia en inglés)
Autómata celular reversible (en la Wiki en inglés)

Métodos de generación de permutaciones

Listado en orden lexicográfico

Sea el conjunto de etiquetas (letras, números...) de objetos, por tanto distinguibles, $\left\lbrace a_{1},\ldots ,a_{n}\right\rbrace$ .

Orden lexicográfico:

$\left(\sigma _{i}(a_{1}),\ldots ,\sigma _{i}(a_{n})\right)\prec \left(\sigma _{j}(a_{1}),\ldots ,\sigma _{j}(a_{n})\right)\Leftrightarrow \exists k\in \lbrace 1,\ldots ,n\rbrace ,{\begin{aligned}\sigma _{i}(a_{1})&=\sigma _{j}(a_{1})\\&\wedge \\\sigma _{i}(a_{2})&=\sigma _{j}(a_{2})\\&\wedge \\&\vdots \\&\wedge \\\sigma _{i}(a_{k-1})&=\sigma _{j}(a_{k-1})\\&\wedge \\\sigma _{i}(a_{k})&<\sigma _{j}(a_{k})\end{aligned}}$

Generación de la siguiente permutación en orden lexicográfico:

Observar que:

Si $\sigma _{i}(a_{n-1})<\sigma _{i}(a_{n})$ , entonces, $\operatorname {intercambiar} \left(\sigma _{i}(a_{n-1}),\sigma _{i}(a_{n})\right)$ .

Por ejemplo, la siguiente a 1234567 sería 1234576.

Si $\sigma _{i}(a_{n-1})>\sigma _{i}(a_{n})$ , entonces,

si

\sigma _{i}(a_{n-2})<\sigma _{i}(a_{n-1})

, entonces,

poner

\min(\sigma _{i}(a_{n-1}),\sigma _{i}(a_{n}))

en la posición

n-2

, situando en las posiciones

n-1

y

n

el

\max(\sigma _{i}(a_{n-1}),\sigma _{i}(a_{n}))

y

a_{n-2}

, en orden creciente.

Por ejemplo, la siguiente a 1234576 sería 1234657.

Objetivo:

Deducir el método para el caso general.

Véase también

Permutación

Más

Robert Sedgewick. Permutation Generation Methods. Computing Surveys, Vol 9, No 2, June 1977, pp. 137-164. http://homepage.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf
- (Algoritmos lexicográficos: pp. 152ss.)
Permutaciones: sucesión A000142 en la OEIS.

Permutación

Definición

Se le llama permutación de $m$ elementos al conjunto de todos los distintos grupos que podemos formar con todos los elementos de dicho grupo presente en cada una de las combinaciones. Cada combinación es distinta a la anterior si la ordenación de sus elementos lo es, por lo que no habrá ningún orden enteramente semejante uno de otro. Una permutación de un conjunto $A$ es una función biyectiva de dicho conjunto en sí mismo

Teorema

Una permutación de $m$ elementos se define por:

P(m)={m\cdot (m-1)\cdot (m-2)\cdots (m-n)}

Con $n$ ∈ al conjunto de los números enteros positivos, $Z$ > 0, donde comienza en $m$ y decrece unitariamente hasta llegar a 1.

Usualmente las permutaciones también se expresan como: $m!$

Interpretaciones

$P{m}$ es el número total de posibilidades que puede adoptar un grupo de $m$ elementos.
$P{m}$ es el número total de multiconjuntos provenientes de un conjunto de $m$ elementos.

Permutaciones circulares

Este tipo de permutaciones son empleadas cuando se requiere la ordenación en círculo de un conjunto de elementos. Como consecuencia de esta ordenación el elemento que ocupa la primera posición y la última coinciden El número de permutaciones en una disposición de este tipo viene dada por $P_{n,p}=(n-1)!$

Ejemplo de permutación circular

En una mesa redonda se sientan 6 mujeres y 6 hombres . ¿De cuántas maneras diferentes pueden sentarse si: a) No hay ningún criterio

b) Los comensales deben ir alternados

Solución: a) $(12-1)!=11!$

b) $(6-1)!*6!=5!*6!$

Otros usos

Existen también las permutaciones con repetición. Esto se da cuando existe como restrición que no se puedan repetir los elementos en un orden concreto. Se define por la siguiente fórmula:

{\frac {m!}{m_{1}!\,m_{2}!\,\cdots \,m_{n}!}}.

Donde $m_{n}$ es la cifra que no se quiere repetir.

Ejemplo

Para calcular las permutaciones de un grupo de 7 elementos:

P(7)=7!={7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=5040}

Véase también

Métodos de generación de permutaciones

Más

Permutaciones: sucesión A000142 en la OEIS.

Robert W. Floyd

Robert W. Floyd fue un científico estadounidense que se especializó en informática nacido en Nueva York en 1936. Se graduó en Artes Liberales y más tarde consiguió un graduado en Física. En 1950 se convirtió en uno de los miembros más importantes del Illionis Institute of Technology.

Recibió el Premio Turing en 1978 "por tener una clara influencia en las metodologías para la creación de software eficiente y confiable, y para ayudar a fundar los siguientes subcampos importantes de la informática: la teoría del análisis, la semántica de los lenguajes de programación, el programa automático Verificación, síntesis automática de programas y análisis de algoritmos ".

Entre sus contribuciones se encuentran el diseño y análisis de algoritmos eficientes para encontrar el camino más corto en un grafo y para el problema de reconocimiento de frases y la creación y contribución al Algoritmo de Floyd-Warshall. Pero su logro más importante fue el ser pionero, con su artículo «Assigning Meanings to Programs», en el área de verificación de programas utilizando aserciones lógicas, donde aparece la importante noción de invariante, esencial para demostrar propiedades de programas iterativos.Entre sus publicaciones también cabe destacar "The paradigms of programming", publicado en 1979.

FUENTES: Wikipedia(EN): Robert W. Floyd. (2017, January 24). In Wikipedia, The Free Encyclopedia. Retrieved 10:08, March 3, 2017, from https://en.wikipedia.org/w/index.php?title=Robert_W._Floyd&oldid=761707204

Wikipedia(ES): Colaboradores de Wikipedia. Robert W. Floyd [en línea]. Wikipedia, La enciclopedia libre, 2016 [fecha de consulta: 3 de marzo del 2017]. Disponible en <https://es.wikipedia.org/w/index.php?title=Robert_W._Floyd&oldid=93642681>.

RSA (sistema criptográfico)

En el sistema criptográfico con clave pública (RSA) es un algoritmo que cifra bloques, este sistema utiliza una clave pública, la cual se puede saber, y otra clave privada, esta es secreta y guardada por su propietario. El nombre de RSA viene por Rivest, Shamir y Adleman que fueron los creadores, fue desarrollado en 1978 en el Instituto Tecnológico de Massachusetts (MIT).

Este algoritmo se basa en la dificultad de la factorizacion de los numeros enteros, de ahí que sea tan seguro. Cuando tu envías un mensaje se representan con números, estos números se basan en el producto de dos números primos los cuales públicamente se desconocen y son elegidos al azar por el propietario del mensaje, a día de hoy esos primos llegan a ser del orden de $10^{200}$ y según van aumentando los años ese número crece al igual que la capacidad de cálculo de los computadores.

Con la llegada de computadores cuánticos se prevé que la seguridad caiga, ya que dichos ordenadores tardarían poco en conseguir esos dos números primos. Esto es debido al Algoritmo de Shor, publicado en 1993 por Peter Shor, profesor estadounidense de matemáticas aplicadas. Este algoritmo muestra que en un futuro, una computadora cuántica, podría mejorar la factorización en tiempo polinomial, quedando obsoleto el algoritmo RSA.

Funcionamiento

El algoritmo RSA funciona de esta manera:

Para empezar tenemos que generar dos números primos, los cuales lógicamente tenemos que guardar en secreto, hay una serie de consejos para la elección de estos números. A estos dos números primos los denotaremos como p y q.
Después calcularemos el productos de ambos números primos que denotaremos como r, por lo tanto r = p * q
Se calcula fi: fi(r) = (p-1)(q-1)
Elegimos un número coprimo k con fi(r), es lo mismo que buscar un número impar por el cual al dividir fi(r) de cero como resto, el cuál será la clave pública o privada, a nuestra elección.
A través del algoritmo extendido de Euclides podemos calcular la clave pública o privada, dependiendo de la elegida en el paso anterior, la fórmula es SK*PK-1=fi(r), donde SK es la clave pública y PK es la clave privada.
Finalmente podremos usar esas claves para cifrar y descifrar mensajes, los cuales tienen que ser numéricos (código ASCII, numérico-alfabético...)

Algoritmo RSA

(1) Generación del par de claves

Para generar un par de claves (KP ; Kp), en primer lugar se eligen aleatoriamente dos números primos grandes, p y q (de unas 200 cifras cada uno, por ejemplo). Después se calcula el producto n = p.q

Escogeremos ahora un número e primo relativo con (p-1) y con (q-1). Este par de números (e,n) pueden ser conocidos por cualquiera, y constituyen la llamada clave pública

e por tanto debe tener un inverso módulo (p-1)(q-1), al que llamamos d. Por supuesto se cumple que ed ≡ 1 mod((p-1)(q-1)), que es lo mismo que decir que ed = 1+k (p-1)(q-1) para algún entero k. La clave privada será el par (d,n). Este número d debe mantenerse secreto y sólo será conocido por el propietario del par de claves.

(2) Cifrado del mensaje con la clave pública

Hay que hacer notar que con este algoritmo los mensajes que se cifran y descifran son números enteros de tamaño menor que n, no letras sueltas como en el caso de los cifrados César o Vigènere.

Para obtener el mensaje cifrado C a partir del mensaje en claro M, se realiza la siguiente operación: C= Me (mod n)

(3) Descifrado del mensaje con la clave privada

Para recuperar el mensaje original a partir del cifrado se realiza la siguiente operación: M= Cd (mod n)

Ejemplo

Aquí tenemos un ejemplo de cifrado/descifrado con RSA. Los parámetros usados aquí son pequeños y orientativos con respecto a los que maneja el algoritmo, pero podemos usar también OpenSSL para generar y examinar un par de claves reales. p = 61 1º nº primo privado q = 53 2º nº primo privado n = pq = 3233 producto p×q e = 17 exponente público d = 2753 exponente privado La clave pública es (e, n). La clave privada es (d, n). La función de cifrado es: encrypt ( m ) = m e ( mod n ) = m 17 ( mod 3233 ) {\displaystyle {\m box{encrypt}}(m)=m^{e}{\p mod {n}}=m^{17}{\p mod {3233}}}

Donde m es el texto sin cifrar. La función de descifrado es: decrypt(c) = c d ( mod n ) = c 2753 ( mod 3233 ) {\displaystyle {\m box{decrypt(c)}}=c^{d}{\p mod {n}}=c^{2753}{\p mod {3233}}}

Donde c es el texto cifrado. Para cifrar el valor del texto sin cifrar 123, nosotros calculamos: encrypt(123) = 123 17 ( mod 3233 ) = 855 {\displaystyle {\m box{encrypt(123)}}=123^{17}{\p mod {3233}}=855}

Para descifrar el valor del texto cifrado, nosotros calculamos: decrypt(855) = 855 2753 ( mod 3233 ) = 123 {\displaystyle {\m box{decrypt(855)}}=855^{2753}{\p mod {3233}}=123}

Los cálculos de potencias grandes y del módulo pueden ser eficientemente realizados por el algoritmo de multiplicación cuadrática para exponenciación modular.

Principales objetivos del sistema criptográfico

El procedimiento RSA permite tambien la función de la firma de transmisiones y comprobar de este modo la integridad del mismo, de manera que la persona que receptora del mensaje sea perfectamente capaz de reconocer al emisor del mismo y evitar así posibles suplantaciones o fraudes.

Este complejo proceso se consigue enviando un mensaje que contenga la $K_{publica}$ del receptor junto a un resumen del contenido por medio de la $K_{privada}$ del emisor. Esto se consigue a través del uso de de conjunto de funciones que reciben del nombre de funciones hash. Estas funciones tienen como base:

El mensaje original no es recuperable.
Provocando pequeños cambios en el texto, el resumen se verá claramente afectado por esta acción.

De estos dos criterios se puede obtener que la probabilidad de tener dos textos capaces de crear un mismo resumen es prácticamente nula. En el momento de que el receptor capta el mensa, este lo descifra mendia su $K_{privada}$ , y el segundo $K_{publica}$ . Fruto de este proceso debe obtenerse dos textos iguales mediante la aplicación de funciones hash. El texto obtenido en segundo lugar recibe el nombre de firma digital y permite cerciorarnos de que el mensaje no ha sido transgiversado por medios externos y que el emisor del mensaje inicial es el emisor que esperábamos.

Rendimiento y eficiencia

El RSA es menos eficiente, es decir, más lento que otro tipo de sistemas criptográficos como son los simétricos o el DES. Esto es en parte debido a que estos últimos, utilizan un tipo de cifrado por bloques.

También, pueden surgir una serie de problemas de seguridad, sobre todo, a la hora de la distribución de las claves públicas. Para evitar ataques durante la distribución, una de las recomendaciones es la de enviar textos cifrados basados en certificados digitales u otros componentes de la clave pública. Otra recomendación es la cifrar los mensajes con otra serie de algoritmos (simétricos), utilizando generadores aleatorios y al final, cifrar la clave con RSA.

Estado del arte

Actualmente, este tipo de algoritmo criptográfico, es usado en diversos sistemas informáticos y en nuevas tecnologías, destacando: los sistemas bancarios, sistemas comerciales, redes inalámbricas, entre otras. El uso de algoritmos simétricos por ejemplo, es utilizado para realizar el acceso a la configuración de routers, o bien como parte de una subrutina para el funcionamiento de algún algoritmo de encriptación de tipo asimétrico.

Dentro del ámbito del comercio electrónico, aún existe desconfianza por parte de los usuarios respecto a la seguridad de este tipo de sistemas, se considera que es muy inseguro debido al mal uso que se podría dar al autorizar transacciones con tan solo ingresar los números de una tarjeta de crédito bancaria. Actualmente y debido a que el comercio electrónico ya es una realidad, se sigue trabajando en el desarrollo de algoritmos criptográficos robustos que logren proveer seguridad, rapidez y eficacia en su uso.

Teorema chino de los restos para RSA

El Teorema chino de los restos, fue propuesto por el matemático chino Sun-Tsu, en el Siglo I. Este teorema está relacionado con los sistemas de congruencias lineales.

En la actualidad, este teorema se utiliza para poder realizar la operación de descifrado con mayor rapidez que el descifrado clásico, ya que utiliza los valores de p y q en vez de n, que en este tipo de operaciones son de tamaño considerablemente menor. Para realizar el descifrado, este teorema realiza la siguiente operación:

$N={Ap[Cp^{dp}(mod(p))]+Aq[Cq^{dq}(mod(q))]}mod(n)$

Donde:

Ap = q [(q-1) mod p] o bien, qp–1 mod n

Aq = p [(p-1) mod q] o bien, pq–1 mod n

Cp = C mod p

Cq = C mod q

dp = d mod (p –1)

dq = d mod (q –1)

Criptoanálisis del RSA

Para romper un cifrado RSA, podemos probar varias vías. Aparte de factorizar n, que ya sabemos que es un problema computacionalemente intratable en un tiempo razonable, podríamos intentar calcular φ(n) directamente, o probar por un ataque de fuerza bruta tratando de encontrar la clave privada d, probando sistemáticamente con cada uno de los números posibles del espacio de claves. Ambos ataques son, para n grandes, incluso aún más costosos computacionalmente que la propia factorización de n.

Programación

repl.it

Véase también

Hacking ético (En Epistemowikia, aquí)

Enlaces externos

Gianluca Dini (2016) The RSA cryptosystem
Wikipedia contributors, "Integer factorization," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Integer_factorization
Wikipedia contributors, "RSA (cryptosystem)," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/RSA_(cryptosystem)
Wikipedia contributors, "RSA Factoring Challenge," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
Wikipedia contributors, "Shor's algorithm," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Shor's_algorithm

Stephen Warshall

Historia

Stephen Warshall nació el 15 de Noviembre de 1935 en Nueva York y falleció el 11 de Diciembre de 2006 de cáncer en su casa en Gloucester, Massacusetts. Durante su carrera, Warshall estudió y desarrolló campos como los sistemas operativos, diseño de lenguaje, diseño de compilación, etc. Tuvo una mujer, Sarah Dunlap, y dos niños, Andrew D. Warshall y Sophia V. Z. Warshall.

Fue a una escuela pública en Brooklyn, posteriormente se graduó en el instituto A.B. Davis en Mount Vernon, Nueva York y asistió a la Universidad de Harvard, recibió una licenciatura en Matemáticas en 1956. Warshall nunca recibió un grado avanzado ya que en ese momento no estaban disponibles en los programas de sus áreas de interés. Además Warshall hizo cursos de postgrado en diferentes universidades y contribuyó al desarrollo de la ciencia computacional e ingeniería del software en varias universidades francesas.

Algoritmo de Floyd-Warshall

En 1962 el científico Robert W. Floyd publicó el algoritmo de Floyd-Warshall, un ejemplo de programa dinámico, pero era casualmente el mismo publicado por Stephen Warshall en 1962 y por Bernard Roy en 1959. Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. Lo hace mejorando paulatinamente una estimación del camino más corto entre dos vértices, hasta que se sabe que la estimación es óptima.

Warshal se acercó a determinar que la prueba de que si el algoritmo de Floyd-Warshall era siempre cierto durante una noche posterior a haber hecho una apuesta con un amigo suyo de Operaciones Técnicas donde apostaron una botella de ron, tras ganar Stephen Warshall la apuesta compartió dicha botella de ron con su amigo. A Warshall no le gustaba sentarse en el escritorio para trabajar, por lo tanto hizo una gran labor en lugares creativos no convencionales como por ejemplo en un velero en el Océano Índico o también en un huerto de limón griego.

Variaciones

Definición

Considerando un conjunto de $n$ elementos. Se denominan variaciones de $n$ elementos tomados de $k$ en $k$ a los diferentes grupos de $k$ elementos que se puedan formar, de modo que dos grupos difieren en que tienen algún elemento distinto o en que poseen una ordenación diferente de dichos elementos.

Una variación de un conjunto cualesquiera, es una función, en la cual, exigimos la inyectividad, es decir, funciones uno a uno, en donde dos orígenes no pueden tener la misma imagen.

Teorema

El número de variaciones de $n$ elementos tomados de $k$ en $k$ , $V_{n}^{k}$ , viene dado por:

$V_{n}^{k}={\frac {n!}{(n-k)!}}$

donde

$n!=n(n-1)(n-2)...1$

Demostración

El primer elemento de la variación podrá elegirse de $n$ formas distintas. Por tanto el segundo elemento se podrá elegir de $n-1$ maneras diferentes, ya que quedan $n-1$ elementos para escoger.

Razonando de la misma forma, existirán $n-2$ posibilidades de elegir el tercero , y así sucesivamente, hasta llegar a la elección del n−ésimo, lo que podrá hacerse escogiendo de entre $n-(k-1)$ candidatos.

Como las etapas de elección son independientes unas de otras, aplicando la regla del producto, se tendrá:

$V_{n}^{k}=n(n-1)(n-2)...[n-(k-2)][n-(k-1)]=n(n-1)(n-2)...(n-k+2)(n-k+1)$

Interpretaciones

$V_{n}^{k}$ es el número de posibilidades en las que se puede distribuir $n$ objetos tomados de $k$ en $k$ .
$V_{n,k}$ es el número total de formas de distribuir $k$ objetos distinguibles en $n$ recipientes distinguibles, independientemente de que se tenga o no en cuenta el orden en que se distribuyan los objetos pero con la condición de que como mucho haya un objeto por recipiente.
$V_{n,k}$ es el número de palabras (hileras finitas de letras) de longitud $k$ , sin repetición de letras, de un alfabeto de $n$ letras.

Ejemplo

¿Cuántos números de tres cifras diferentes se puede formar con los dígitos: 1, 2, 3, 4, 5 ?

No entran todos los elementos. No se repiten los elementos.

$n=5;k=3$

$V_{5}^{3}={\frac {5!}{(5-3)!}}=60$

Más

Variaciones: sucesión A068424 en la OEIS.

Véase también

Enlaces internos

Personas participantes y contribuciones principales del proyecto educativo, plan de aprendizaje y taller del plan de aprendizaje

Páginas de discusión

Enlaces interwiki

Proyecto educativo, personas participantes y contribuciones principales, plan de aprendizaje y taller del plan de aprendizaje
- Proyecto universitario «Discrete and numerical mathematics» (proyecto educativo equivalente en la Wikipedia en inglés)
- Proyecto universitario «Discrete and numerical mathematics»: Personas participantes y contribuciones principales (personas participantes y contribuciones principales del proyecto educativo equivalente en la Wikipedia en inglés)
- Plan de aprendizaje «Discrete and numerical mathematics» (plan de aprendizaje equivalente en la Wikipedia en inglés)
- Taller del plan de aprendizaje «Discrete and numerical mathematics» (taller del plan de aprendizaje equivalente en la Wikipedia en inglés) (los editatones en inglés, están aquí)

Páginas de discusión
- Página de discusión del proyecto universitario «Discrete and numerical mathematics» (página de discusión del proyecto educativo equivalente en la Wikipedia en inglés)
- Proyecto universitario «Discrete and numerical mathematics»: Personas participantes y contribuciones principales (página de discusión de la página de participantes y contribuciones principales del proyecto educativo equivalente en la Wikipedia en inglés)
- Página de discusión del plan de aprendizaje «Discrete and numerical mathematics» (página de discusión del plan de aprendizaje equivalente en la Wikipedia en inglés)
- Página de discusión del taller del plan de aprendizaje «Discrete and numerical mathematics» (página de discusión del taller del plan de aprendizaje equivalente en la Wikipedia en inglés)

Para estar al tanto, saber más o escribir algún comentario

Página de discusión del taller del plan de aprendizaje «Matemática discreta y numérica»

Acerca de esta página en la Wikipedia en español

Wikipedia:Proyecto educativo/Matemática discreta y numérica/Plan de aprendizaje/Taller (editar | discusión | historial | enlaces | vigilar | registros | proteger | borrar) (análisis de visitas) (más información)

[1] Contribuyentes de la Wikipedia inglesa (2017), «Collatz conjecture: Undecidable generalizations», Wikipedia, The Free Encyclopedia.

[2] Kurtz, Stuart A.; Simon, Janos, «The Undecidability of the Generalized Collatz Problem», en: Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, celebrado en Shanghai, China, en mayo de 2007. ISBN 3-540-72503-2. (DOI = 10.1007/978-3-540-72504-6 49).

[1]

[2]