Usuario:Efraileg/Taller

Esta persona usuaria de Wikipedia en español participa en el Proyecto educativo Matemática discreta y numérica (MATDIN).

Fundamentos

Lógica ecuacional

Página a la que hacer referencia para poder colaborar/contribuir: Lógica ecuacional, en este taller/cuaderno de bitácora se publicará el progreso respecto a este tema antes de publicarse en la página oficial para poder hacer las pruebas y los cambios que sean necesarios.

No obstante, debido a que la página en Wikipedia no existe y tratando este tema se menciona el software mediante el cual se trata la lógica ecuacional, las contribuciones respecto a este tema serán publicadas en la página donde se trata el propio software en ACL2.

La lógica ecuacional es un área de la lógica matemática centrada en el estudio de ecuaciones en igualdad entre expresiones como operaciones, variables, constantes, entre otros. Las ecuaciones, usadas como expresión de equivalencia entre dos objetos, adquiere importancia en el área de las ciencias de la computación y de las matemáticas empleándose en corrección de programas, cálculo simbólico, entre otros.

Los problemas que normalmente suelen resolverse mediante lógica ecuacional puede ser el determinar si una ecuación es consecuencia lógica de un conjunto de axiomas ecuaciones, determinar los elementos o valores que verifican la ecuación o si la ecuación es válida.

ACL2 y sistemas de reescritura

La lógica ecuacional se formaliza en ACL2, un lenguaje de programación y de lógica matemática utilizado para la demostración formal de teoremas.

Su concepto de consecuencia lógica se representa mediante un conjunto de axiomas ecuacionales que puede ser descrito mediante una relación de equivalencia. Esta relación procede del conjunto de términos de primer orden, es decir, mediante axiomas reemplazando iguales por iguales (proposiciones que se asumen como verdaderas sin necesidad de una demostración previa). Lo anteriormente dicho es como se representa en ACL2 la teoría ecuacional.

Se dice sistema de reescritura al conjunto de ecuaciones orientadas de derecha a izquierda y para conseguir la reducción asociada a este tipo de sistemas se emplea la noetherianidad y un algoritmo de cálculo de formas normales. Un sistema de reescritura concluye en estudiar un conjunto finito de pares llamados pares críticos.

Teorías ecuacionales

Dado un sistema de ecuaciones E (axiomas), la teoría ecuacional de E es el conjunto de ecuaciones (teoremas) que son consecuencia lógica de E.

Una teoría ecuacional se puede ver como la relación de equivalencia descrita por una reducción: reemplazamiento o reescritura de iguales por iguales, usando los axiomas de la teoría. La teoría ecuacional ha sido expuesta como la equivalencia de una reducción concreta. En ACL2, todo sistema de reescritura noetheriano, cuyos pares críticos confluyen, describe una teoría ecuacional decidible.

Tipos de datos en ACL2

Existen diferentes tipos de objetos en ACL2:

Tipos de objetos

Objeto	Valor asociado
Números	7, -5, 2/5, #c(2 1).
Caracteres	#\a, #\Space.
Cadenas de caracteres	"Buenas" "Tardes"
Símbolos	t, nil, x, NWM::a.
Pares punteados	(1 . 2), (i j k).

Manejo y escritura de los diferentes tipos de números en ACL2

• Los números racionales se escriben como fracción de números enteros.
• En ACL2, los símbolos están formados por dos cadenas de caracteres: su nombre de paquete y su nombre de símbolo.
  • Por ejemplo, el símbolo cuyo nombre de paquete es NWM y cuyo nombre de símbolo es a, se escribe NWM::a

Expresiones en ACL2 y su significado

Un software como ACL2 funciona principalmente en base a definiciones que otorgan un significado funcional a una serie de símbolos. El siguiente ejemplo es una definición donde el símbolo fun a una función:

(defun fun (l)
    (append nil (cons (car (cdr l))
                        (cons (car l) (cdr (cdr l))))))

Funciones y macros base

La gran parte de las funciones base de ACL2 provienen del software Common Lisp. Existen muchas de ellas dedicadas a aritméticas, conversión, reconocedor de números/objetos, etc.

Algunas funciones ejemplo son las siguientes:

(< x y)         Menor estricto
(<= x y)        Menor o igual
(> x y)         Mayor
(>= x y)        Mayor o igual
(+ x y ...)     Suma
(* x y ...)     Multiplicación
(- x y)         Resta
(- x)           Opuesto
(/ x y)         División
(nfix x)        Conversión a número natural
(consp x)       Reconocedor de pares punteados
(atom x)        Reconocedor de objetos atómicos
(true-listp l)  Reconocedor de listas

Teoría de números

SimHash

Página a la que hacer referencia para poder colaborar/contribuir: SimHash, en este taller/cuaderno de bitácora se publicará el progreso respecto a este tema antes de publicarse en la página oficial para poder hacer las pruebas y los cambios que sean necesarios.

No obstante, debido a que la página en Wikipedia no existe, las contribuciones respecto a este tema serán publicadas en la página donde se trata el concepto de MinHash debido a que en esta página se hace una mínima mención al concepto de SimHash pero profundizar en ello.

En la mayoría de los casos, se utilizan funciones hash para separar y ocultar los datos, de modo que datos similares tengan claves diferentes. Sin embargo, se propone utilizar funciones hash para el propósito opuesto: detectar similitudes entre datos.

La detección de similitudes y la clasificación es un problema bien estudiado, pero normalmente se involucran n² comparaciones por pares. Al utilizar una función hash que convierte datos similares en valores similares, la similitud se puede detectar simplemente comparando valores de clave hash preclasificados. El reto es encontrar una función hash de similitud que minimice los falsos positivos.

Se ha implementado una familia de funciones hash de similitud y se ha mejorado su rendimiento almacenando los datos auxiliares utilizados para calcular las claves hash. Estos datos se utilizan como filtro después de que una comparación de claves hash indique que dos les son potencialmente similares. Estas pruebas se utilizan para explorar la noción de "similitud".

A medida que se incrementa la capacidad de almacenamiento, resulta cada vez más difícil organizar y gestionar sistemas de leasing más grandes. En muchas ocasiones, las copias idénticas o las versiones antiguas quedan separadas y dispersas en una estructura de directorios. No obstante, las tecnologías de duplicación no se aplican bien al caso en el que los archivos no son idénticos.

Las técnicas de identificación les podrían ser útiles para la clasificación y la búsqueda. Una técnica común de detección de similitud consiste en mapear las características de un le a un espacio dimensional y luego utilizar la distancia dentro de este espacio como medida de similitud. Desafortunadamente, calcular la distancia entre todos los pares de les puede llevar a algoritmos de detección de similitud O(n²).

Sin embargo, si estos mapeos se proyectan a un espacio unidimensional, los puntos de datos podrían ordenarse en tiempo O(n log n), lo que aumentaría considerablemente la velocidad de detección.

Se estableció como objetivo la creación de una "función hash de similitud". Normalmente, las funciones hash se diseñan para minimizar las colisiones (cuando dos entradas diferentes tienen el mismo valor de clave). Con las funciones hash criptográficas, se espera que las colisiones sean casi imposibles, y que los datos casi idénticos correspondan a claves muy distintas. Sin embargo, la función hash de similitud tenía la intención opuesta: se buscaba que datos similares correspondieran a claves hash muy similares o incluso a la misma clave hash, y que la distancia entre las claves fuera una medida de la diferencia entre los datos.

Por supuesto, el "tamaño de archivo" es una especie de función hash sobre archivos que satisface estos requisitos. Sin embargo, aunque se espera que los similares tengan un tamaño similar, no se espera que dos de tamaño similar tengan un contenido similar. No está claro cómo se podría condensar la información de un fichero en una clave más útil.

Aunque SimHash produce claves hash con valores enteros, se recurrió a datos auxiliares para mejorar las pruebas de similitud. Los valores clave se basaron en contar las ocurrencias de ciertas cadenas binarias dentro de un fichero y combinando estas sumas. Desafortunadamente, los valores clave seguían siendo aproximadamente proporcionales al tamaño del fichero, lo que provocaba muchos falsos positivos.

Sin embargo, los datos auxiliares proporcionaron un medio fácil y eficaz para comprobar la detección de similitudes. Una versión mejorada de las claves, basada en la extensión de la le, proporciona una gama mucho más amplia de valores clave y alivia algunos de los problemas mencionados.

Similitud es una palabra vaga y puede tener numerosos significados en el contexto de la informática. Para que dos les sean similares, deben compartir contenido.

Sin embargo, existen diferentes formas de definir el contenido de un archivo. Por ejemplo, en un archivo de texto codificado en formato .rtf (Rich Text Format), el contenido podría referirse a todo el fichero, solo a la parte de texto del mismo o incluso al significado semántico de la parte de texto (independientemente del texto real).

Muchos intentos previos de detección de similitud se han centrado en la detección de similitudes a nivel de texto. Decidimos utilizar la similitud binaria como métrica, en la cual dos ficheros son similares si solo un pequeño porcentaje de sus patrones de bits en bruto son diferentes. Esto permite detectar otros tipos de similitud, como el ejemplo de añadir una línea al código fuente, lo que desplaza todos los números de línea dentro del código compilado. La métrica detectaría las dos fuentes como similares, mientras que el código compilado no.

Optamos por la similitud binaria para no centrarnos en un tipo de fichero o estructura de archivo específico (por ejemplo, documentos de texto).

Otro aspecto que no exploramos es la similitud semántica. Por ejemplo, dos textos pueden utilizar palabras diferentes pero tener el mismo contenido en términos de significado. O dos archivos MP3 de la misma canción con codificaciones diferentes pueden tener un contenido binario similar. Sin embargo, nos centramos en la similitud sintáctica, no semántica.

Como dijo Udi Manber: "no intentamos comprender el contenido de las palabras".

Broder aclaró por primera vez la distinción entre semejanza (cuando dos ficheros se parecen) y contención (cuando un fichero está contenido dentro de otro). Tomemos el ejemplo de un fichero que consiste en copias repetidas de otro más pequeño, esto sería una relación de contención.

El objetivo de SimHash se centró en la detección de semejanzas. Dos ficheros con una disparidad de tamaño son implícitamente diferentes y las relaciones de contención entre ambos no necesariamente hacen que los dos sean "similares" según la métrica.

Para que dos les sean similares según la métrica, deben contener un gran número de piezas comunes. Otra división en las técnicas de detección de similitud es la granularidad y la cobertura de estas piezas. SimHash opera con una granularidad muy reducida, a nivel de bytes o palabras. No intentamos obtener una cobertura completa, sino que se enfoca solo en las partes de aquel fichero que coinciden con el conjunto de patrones de bits.

Dada una métrica de similitud, es necesario establecer un umbral para determinar cuán cercanas deben estar dentro de esa métrica para considerarse similares. Nos centramos en les que tienen un alto grado de similitud, idealmente entre el 1% y el 2%.

Otra cuestión es si la forma de detectar similitud debe ser relativa o absoluta. En otras palabras, ¿se trata de recuperar un conjunto de ficheros similares a un fichero dado o recuperar todos los pares de ficheros que son similares? SimHash aborda ambas situaciones.

Combinatoria

Optimización combinatoria

Página a la que hacer referencia para poder colaborar/contribuir: Optimización combinatoria, en este taller/cuaderno de bitácora se publicará el progreso respecto a este tema antes de publicarse en la página oficial para poder hacer las pruebas y los cambios que sean necesarios.

No obstante, debido a que ya existe una página con un contenido similar a la cual contribuir se decide por plasmar el contenido de este apartado en la siguiente página: Optimización combinatoria

Un problema de optimización combinatoria se define como aquel en el que el conjunto de soluciones posibles es discreto. En otras palabras, se trata de un problema de optimización que involucra una cantidad finita o numerable de soluciones posibles.

Este tipo de problemas se diferencia de los problemas de optimización continuos, en los cuales el conjunto de soluciones posibles es infinito e incontable. Esta rama de la optimización se relaciona estrechamente con la investigación operativa, la teoría algorítmica y la teoría de la complejidad computacional. Los algoritmos de optimización combinatoria resuelven problemas que, en general, se consideran difíciles al explorar el amplio espacio de soluciones del problema en cuestión. Los buenos algoritmos de optimización combinatoria logran reducir el tamaño efectivo del espacio de búsqueda y explorarlo de manera eficiente.

Aquí entran los algoritmos de optimización combinatoria. Éstos son capaces de resolver problemas que suelen ser considerados difíciles, ya que exploran un amplio espacio de soluciones. Para lograrlo, estos algoritmos reducen efectivamente el tamaño del espacio y lo exploran de manera eficiente.

En el campo de la optimización combinatoria, es común que la mayoría de los procesos de resolución de problemas no puedan garantizar la solución óptima, incluso dentro del contexto del modelo que se esté utilizando. Sin embargo, la aproximación al óptimo suele ser suficiente para resolver los problemas en la práctica.

Existen diferentes métodos de resolución que pueden ser clasificados en cuatro grandes grupos:

1. Algoritmos constructivos, que construyen la solución a partir de una solución incompleta y utilizando los datos del problema y el conocimiento previo.
2. Algoritmos de mejora, que comienzan con una solución factible y completa y la modifican gradualmente de manera progresiva.
3. Estrategias de "divide y vencerás", que dividen el problema en fragmentos y aplican cualquier otra estrategia para resolver cada fragmento, y finalmente recomponen la solución.
4. Estrategias de aprendizaje, que toman decisiones en función de datos conocidos por el resultado de resoluciones anteriores o en la misma resolución.

Los métodos más comunes utilizados para resolver problemas en optimización combinatoria son heurísticos o metaheurísticos. Estos métodos son capaces de generar soluciones para el problema, aunque sean aproximaciones que no necesariamente alcancen la solución óptima.

En los primeros días de la Investigación Operativa, las limitaciones de cálculo automático llevaron a la creación de procedimientos heurísticos que pudieran encontrar soluciones de manera rápida, aunque no necesariamente las mejores.

Aunque los métodos heurísticos de resolución no pueden garantizar la solución óptima, son fundamentales por varias razones. En primer lugar, son capaces de generar soluciones, lo cual es mejor que no tener ninguna solución. En segundo lugar, obtener la solución óptima para un modelo que no representa exactamente el problema real no es necesariamente esencial. Por último, diseñar una buena heurística exige un conocimiento profundo del problema, lo cual puede conducir a mejoras de otro tipo.

Por lo tanto, los métodos heurísticos, incluyendo los procesos de mejora local y los algoritmos metaheurísticos, son herramientas valiosas para resolver problemas de optimización combinatoria en la práctica.

Variaciones sin repetición

Consiste en el número de maneras de seleccionar y ordenar r elementos distintos de un conjunto de n elementos.

Está dado por la expresión matemática nPr, donde n es el número total de elementos del conjunto y r es el número de elementos a seleccionar y ordenar:

$V_{n,r}={n! \over (n-r)!}$

Variaciones con repetición

Consiste en el número de maneras de seleccionar y ordenar r elementos del conjunto de n elementos permitiendo que los elementos puedan repetirse.

Está dado por la expresión matemática n^r donde n es el número total de elementos del conjunto y r es el número de elementos a seleccionar y ordenar:

$VR_{n,r}=n^{r}$

Permutación sin repetición

Consiste en el número de maneras de seleccionar y ordenar todos los elementos de un conjunto de todas las formas posibles.

Está dado por la expresión n! donde n es el número total de elementos del conjunto:

$P_{n}=n!$

Permutación con repetición

Consiste en el número de maneras de seleccionar y ordenar un conjunto de n elementos, donde algunos de los elementos pueden ser idénticos. Es decir, en el caso de existir $m_{1}$ elementos de tipo 1, $m_{2}$ elementos de tipo 2, hasta $m_{n}$ elementos de tipo n.

Está dado por la expresión:

$PR_{m_{1}+m_{2}+...+m_{n}}^{m_{1},m_{2},...m_{n}}={(m_{1}+m_{2}+...+m_{n})! \over m_{1}!*m_{2}!*...*m_{n}!}$

Combinaciones sin repetición

Consiste en el número de maneras de seleccionar y ordenar r elementos distintos de un conjunto de n elementos teniendo en cuenta el orden de éstos.

Está dado por la siguiente expresión:

$C_{n}^{r}={n! \over r!*(n-r)!}$

Combinaciones con repetición

Consiste en el número de maneras de seleccionar y ordenar r elementos del conjunto de n elementos permitiendo que los elementos puedan repetirse considerando además el orden de éstos.

Está dado por la siguiente expresión:

$C_{n+r-1}^{r}={(n+r-1)! \over r!*(n-1)!}$

Problemas de optimización combinatoria

En esta sección se presentan algunos problemas clásicos de optimización combinatoria. Aunque la intención inicial era clasificar estos problemas, resulta casi imposible debido a que existen muchos tipos de clasificaciones en función de diferentes criterios para cada tipo de problema.

Por lo tanto, se ha decidido enumerar diferentes tipos de problemas según diferentes aspectos, como su aplicación, la clase teórica a la que pertenecen o las soluciones que se buscan obtener. No se han considerado clasificaciones que se basan en aspectos como la dificultad en términos de complejidad o la existencia de algoritmos eficientes para su resolución.

Según su aplicación

1. Secuenciación: Referido al orden en el que un conjunto de trabajos deben pasar por una máquina. Este enfoque permite considerar aspectos como la duración de cada trabajo, la fecha de entrega, etc. El objetivo es encontrar el orden óptimo que permita cumplir con los objetivos del proyecto o la producción, minimizando la duración total o maximizando la eficiencia. Esto es posible mediante el uso de máquinas que trabajen en paralelo/serie.
2. Rutas: Los problemas de rutas están diseñados para establecer la mejor secuencia de recorrido para brindar un determinado servicio. Uno de los problemas clásicos en esta categoría es el problema del viajante de comercio (TSP), que implica visitar una vez y sólo una vez un conjunto de puntos. A este problema se le pueden añadir diversas variantes, como incluir varios viajantes, limitar la capacidad de los camiones o la disponibilidad de tiempo, incorporar ventanas temporales de entrega o recepción, entre otros. La complejidad de estos problemas aumenta a medida que se agregan más restricciones, pero su resolución eficiente puede generar importantes beneficios en términos de costos y eficiencia.

Según su clasificación formal

En esta categoría se encuentran problemas como:

1. El problema de la mochila (uni o multidimensional).
2. De máximo (o mínimo) flujo.
3. Problemas de Asignación Cuadrática.
4. Graph Partitioning Problem.
5. De camino más corto (o más largo).

Ecuaciones en diferencias

Triángulo de Hosoya

Página a la que hacer referencia para poder colaborar/contribuir: Triángulo de Hosoya, en este taller/cuaderno de bitácora se publicará el progreso respecto a este tema antes de publicarse en la página oficial para poder hacer las pruebas y los cambios que sean necesarios.

Concepto de triángulo de Hosoya

El triángulo de Hosoya es un arreglo triangular definido recursivamente, cuyas entradas pueden ser expresadas como el producto de dos números de Fibonacci. Este triángulo comparte algunas propiedades e identidades con el Triángulo de Pascal, que es más conocido.

Relación con la sucesión de Fibonacci

Por un lado, la sucesión de Fibonacci es una famosa serie de números que comienza con 1 y 1, en la que cada número es la suma de los dos números anteriores. La secuencia continúa indefinidamente: 1, 1, 2, 3, 5, 8, 13, 21 y así sucesivamente (1 + 1 = 2; 2 + 1 = 3; 3 + 2 = 5...) hasta converger a un número constante llamado "phi" (φ) también conocido como la proporción áurea.

La definición recursiva del n-ésimo número de Fibonacci tiene la siguiente forma:

• $F_{0}=0,F_{1}=F_{1}$ relación inicial.

• $F_{n}=F_{n-1}+F_{n-2}$ $n\geq 2$ relación de recurrencia.

Esta sucesión está estrechamente relacionada con los números de Lucas cuya secuencia tiene la forma 2, 1, 3, 4, 7, 11...

Su definición es la siguiente:

• $L_{0}=2,L_{1}=1$ relación inicial.
• $L_{n}=L_{n-1}+L_{n-2}$ $n\geq 2$ relación de recurrencia.

Se puede plantear una fórmula para la suma de los n primeros números de la sucesión de Fibonacci con la cual se obtiene un patrón como:

• $F_{1}=1=2-1=F_{3}-1$
• $F_{1}+F_{2}=2=3-1=F_{4}-1$
• $F_{1}+F_{2}+F_{3}=4=5-1=F_{5}-1$
• $F_{1}+F_{2}+F_{3}+F_{4}=7=8-1=F_{6}-1$
• $F_{1}+F_{2}+F_{3}+F_{4}+F_{5}=12=13-1=F_{7}-1$

Puede apreciarse que tanto la diagonal izquierda como la derecha del triángulo de Hosoya cumple con el anterior patrón. En el caso de la suma de los cinco primeros números de dicha diagonal se obtiene 12 y, según el patrón, dicho valor coincide con el séptimo número de la misma diagonal restando una unidad siendo cierto.

Recurrencia del triángulo de Hosoya

La sucesión de Hosoya {H(r, k) | k ≥ 1} se define recursivamente de la siguiente manera:

• H(1, 1) = H(2, 1) = H(2, 2) = H(3, 2) = 1
• H(r, k) = H(r-1, k) + H(r-2, k)
• H(r, k) = H(r-1, k-1) + H(r-2, k-2)

                  H(1, 1)

                                 

            H(2, 1)    H(2, 2)

                             

        H(3, 1)    H(3, 2)    H(3, 3)

                       

    H(4; 1)    H(4; 2)    H(4, 3)    H(4, 4)

                   

H(5, 1)    H(5, 2)    H(5, 3)    H(5, 4)    H(5, 5)

Se puede apreciar que $H(r,1)=H(r-1,1)+H(r-2,1)$ donde $H(1,1)=1=F_{1}$ y $H(2,1)=1=F_{2}$ concluyendo que $H(r,1)=F_{r}$ indicando los elementos en la primera posición de la r-ésima fila del triángulo de Hosoya.

Temas adicionales y de interés

Teorema de Ramsey en grafos simples

Página a la que hacer referencia para poder colaborar/contribuir: Teorema de Ramsey, en este taller/cuaderno de bitácora se publicará el progreso respecto a este tema antes de publicarse en la página oficial para poder hacer las pruebas y los cambios que sean necesarios.

Referencias

Fundamentos

• Lógica Ecuacional