PROBLEMA DE AGENTE VIAJERO

En el Problema del Agente Viajero el objetivo es encontrar un recorrido completo que conecte todos los nodos de una red, visitándolos tan solo una vez y volviendo al punto de partida, y que además minimice la distancia total de la ruta, o el tiempo total del recorrido.

Este tipo de problemas tiene gran aplicación en el ámbito de la logística y distribución, así como en la programación de curvas de producción.

El problema del agente viajero tiene una variación importante, y esta depende de que las distancias entre un nodo y otro sean simétricas o no, es decir, que la distancia entre A y B sea igual a la distancia entre B y A, puesto que en la práctica es muy poco probable que así sea. 

MÉTODOS DE SOLUCIÓN

La cantidad de rutas posibles en una red está determinada por la ecuación:

(n-1)!

Es decir que en una red de 5 nodos la cantidad de rutas probables es igual a (5-1)! = 24, y a medida que el número de nodos aumente la cantidad de rutas posibles crece factorialmente. En el caso de que el problema sea simétrico la cantidad de rutas posibles se reduce a la mitad, es decir:

( (n-1)! ) / 2

Lo cual significa un ahorro significativo en el tiempo de procesamiento de rutas de gran tamaño.

La complejidad del cálculo del problema del agente viajero ha despertado múltiples iniciativas por mejorar la eficiencia en el cálculo de rutas. El método más básico es el conocido con el nombre de fuerza bruta, que consiste en el cálculo de todos los posibles recorridos, lo cual se hace extremadamente ineficiente y casi que se imposibilita en redes de gran tamaño. También existen heurísticos que se han desarrollado por la complejidad en el cálculo de soluciones óptimas en redes robustas, es por ello que existen métodos como el vecino más cercano, la inserción más barata y el doble sentido. Por último se encuentran los algoritmos que proporcionan soluciones óptimas, como el método de branch and bound (ramificación y poda), que trabaja el problema como un algoritmo de asignación y lo resuelve por medio del método simplex.

MAPA DE KARNAUGH

QUE ES

Un mapa de Karnaugh (también conocido como tabla de karnaugh o diagrama de Veitch, abreviado como Mapa-K o Mapa-KV) es un diagrama utilizado para la simplificación de funciones algebraicas Booleanas. El mapa de Karnaugh fue inventado en 1953 por Maurice Karnaugh, un físico y matemático de los laboratorios Bell.

El mapa de Karnaugh consiste en una representación bidimensional de la tabla de verdad de la función a simplificar. Puesto que la tabla de verdad de una función de N variables posee 2^N filas, el mapa K correspondiente debe poseer también 2^N cuadrados. Las variables de la expresión son ordenadas en función de su peso y siguiendo el código Gray, de manera que sólo una de las variables varía entre celdas adyacentes. La transferencia de los términos de la tabla de verdad al mapa de Karnaugh se realiza de forma directa, albergando un 0 ó un 1, dependiendo del valor que toma la función en cada fila. Las tablas de Karnaugh se pueden fácilmente realizar a mano con funciones de hasta 6 variables, para funciones de mayor cantidad de variables es más eficiente el uso de software especializado.

CALCULO DE RENGLONES Y COLUMNAS

El número de renglones y columnas de un mapa de Karnaugh normalmente suele representarse como un mapa cuadrado (número de renglones = número de columnas) cuando el número de variables es par (2, 4, 6, 8... etc) y cuando el número de variables es impar el número de renglones igual a la mitad del número de columnas; siguiendo la siguientes fórmulas:

• Cuando el número de variables es par:

${\displaystyle renglones=columnas={\sqrt {2^{variables}}}}$

• Cuando el número de variables es impar:

${\displaystyle columnas={\sqrt {2^{variables+1}}}}$

${\displaystyle renglones={\frac {columnas}{2}}}$

TABLA

#	${\displaystyle A}$	${\displaystyle B}$	${\displaystyle C}$	${\displaystyle D}$	${\displaystyle f(A,B,C,D)}$
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

CARACTERISTICAS

Las variables de entrada pueden combinarse de 16 formas diferentes, por lo que el mapa de Karnaugh tendrá 16 celdas, distribuidas en una cuadrícula de 4 × 4.

La combinación de dígitos binarios en el mapa representa el resultado de la función por cada combinación de entradas. Por ejemplo, la celda en la esquina superior izquierda del mapa es 0, porque el resultado de la función es ƒ = 0 cuando A = 0, B = 0, C = 0, D = 0. De igual manera, la esquina inferior derecha es 10 porque el resultado de la función es ƒ = 10 cuando A = 1, B = 0, C = 1, D = 0.

Una vez construido el mapa de Karnaugh, la siguiente tarea es la de seleccionar conjunto de términos denominados subcubos de manera que se obtenga el menor número de subcubos posible. Estos subcubos se seleccionan formando grupos de rectángulos que encierren a los unos del mapa, las áreas deben ser potencia de 2 (ej. 1, 2, 4, 8, ...) y se debe tratar de agrupar el mayor número de unos posible. En resumen hay que tomar en cuenta al hacer estos grupos de unos (subcubos) lo siguiente:.

• Debemos utilizar todos los unos del mapa.
• Es mejor crear el menor número de grupos.
• Los unos pueden estar en varios grupos.
• El número de unos dentro de un grupo debe ser cualquier potencia de 2.
• Cuanto más grande sea un grupo, la simplificación de la función será mejor.
• No es necesario que todos los grupos tengan el mismo tamaño.

Qué términos seleccionar va dependiendo de cómo se quiera realizar la simplificación, puesto que esta puede realizarse por minitérminos o por maxitérminos.

LA RELACION DE:

TEORIA DE COJUNTOS

La teoría de conjuntos es una rama de la lógica matemática que estudia las propiedades y relaciones de los conjuntos: colecciones abstractas de objetos, consideradas como objetos en sí mismas. Los conjuntos y sus operaciones más elementales son una herramienta básica en la formulación de cualquier teoría matemática.
La teoría de los conjuntos es lo suficientemente rica como para construir el resto de objetos y estructuras de interés en matemáticas: números, funciones, figuras geométricas,...; gracias a las herramientas de la lógica, permite estudiar los fundamentos de aquella. En la actualidad se acepta que el conjunto de axiomas de la teoría de Zermelo-Fraenkel es suficiente para desarrollar toda la matemática.
Además, la propia teoría de conjuntos es objeto de estudio per se, no sólo como herramienta auxiliar, en particular las propiedades y relaciones de los conjuntos infinitos. En esta disciplina es habitual que se presenten casos de propiedades indemostrables o contradictorias, como la hipótesis del continuo o la existencia de un cardinal inaccesible. Por esta razón, sus razonamientos y técnicas se apoyan en gran medida en la lógica.
El desarrollo histórico de la teoría de conjuntos se atribuye a Georg Cantor, que comenzó a investigar cuestiones conjuntistas «puras» del infinito en la segunda mitad del siglo XIX, precedido por algunas ideas de Bernhard Bolzano e influido por Richard Dedekind. El descubrimiento de las paradojas de la teoría cantoriana de conjuntos, formalizada por Gottlob Frege, propició los trabajos de Bertrand Russell, Ernst Zermelo, Abraham Fraenkel y otros a principios del siglo XX.

LOGICA MATEMATICA
La lógica matemática, también llamada lógica simbólica, lógica teorética, lógica formal o logística,​ es el estudio matemático de la lógica y su aplicación a otras áreas de la matemática y la ciencia. Comprende la aplicación de las técnicas de la lógica formal a las matemáticas y el razonamiento matemático, y conversamente la aplicación de técnicas matemáticas a la representación y el análisis de la lógica formal. La investigación en lógica matemática ha jugado un papel crucial en el estudio de los fundamentos de las matemáticas.
La lógica matemática estudia la inferencia mediante la construcción de sistemas formales como la lógica proposicional, la lógica de primer orden o la lógica modal. Estos sistemas capturan las características esenciales de las inferencias válidas en los lenguajes naturales, pero al ser estructuras formales susceptibles de análisis matemático, permiten realizar demostraciones rigurosas sobre ellas.
La lógica matemática se suele dividir en cuatro áreas: teoría de modelos, teoría de la demostración, teoría de conjuntos y teoría de la computabilidad. La teoría de la demostración y la teoría de modelos fueron el fundamento de la lógica matemática. La teoría de conjuntos se originó en el estudio del infinito por Georg Cantor y ha sido la fuente de muchos de los temas más desafiantes e importantes de la lógica matemática, a partir del teorema de Cantor, el axioma de elección y la cuestión de la independencia de la hipótesis del continuo, al debate moderno sobre grandes axiomas cardinales. La lógica matemática tiene estrechas conexiones con las ciencias de la computación. La teoría de la computabilidad captura la idea de la computación en términos lógicos y aritméticos. Sus logros más clásicos son la indecidibilidad del Entscheidungsproblem de Alan Turing y su presentación de la tesis de Church-Turing. Hoy en día, la teoría de la computabilidad se ocupa principalmente del problema más refinado de las clases de complejidad (¿cuándo es un problema eficientemente solucionable?) y de la clasificación de los grados de insolubilidad.

ALGEBRA BOOLEANA
Se denomina así en honor a George Boole (2 de noviembre de 1815 a 8 de diciembre de 1864), matemático inglés autodidacta, que fue el primero en definirla como parte de un sistema lógico, inicialmente en un pequeño folleto, The Mathematical Analysis of Logic,1​ publicado en 1847, en respuesta a una controversia en curso entre Augustus De Morgan y sir William Rowan Hamilton. El álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. Más tarde fue extendido como un libro más importante: An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities (también conocido como An Investigation of the Laws of Thought 2​ o simplemente The Laws of Thought3​), publicado en 1854.

OPERACIONES Y LEYES DE CONJUNTOS

UNION
En la teoría de conjuntos, la unión de dos (o más) conjuntos es una operación que resulta en otro conjunto, cuyos elementos son los mismos de los conjuntos iniciales. ... La unión de conjuntos se denota por el símbolo ∪, de modo que por ejemplo, N = P ∪ I.

INTERSECCION
En teoría de conjuntos, la intersección de dos (o más) conjuntos es una operación que resulta en otro conjunto que contiene los elementos comunes a los conjuntos de partida.

COMPLEMENTO
El complemento de un conjunto o conjunto complementario es otro conjunto que contiene todos los elementos que no están en el conjunto original. Para poder definirlo es necesario especificar qué tipo de elementos se están utilizando, o de otro modo, cuál es el conjunto universal.

LEY DISTRIBUTIVA
La Propiedad Distributiva en la Unión de Conjuntos es una Ley matemática que se da en esta operación del Álgebra de Conjuntos en referencia a otra operación, conocida como Intersección, indicando básicamente que la unión de un conjunto A con la intersección de los conjuntos B y C puede ser igual a la intersección de las respectivas uniones del conjunto A con los conjuntos B y C, lo cual puede resumirse con la expresión matemática: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
LEY DE MORGAN
En lógica proposicional y álgebra de Boole, las leyes de De Morgan​ son un par de reglas de transformación que son ambas reglas de inferencia válidas. Las normas permiten la expresión de las conjunciones y disyunciones puramente en términos de vía negación.
Las reglas se pueden expresar en español como:
La negación de la conjunción es la disyunción de las negaciones. La negación de la disyunción es la conjunción de las negaciones.
o informalmente como:
"no (A y B)" es lo mismo que "(no A) o (no B)"
y también,
"no (A o B)" es lo mismo que "(no A) y (no B)"
Las reglas pueden ser expresadas en lenguaje formal con dos proposiciones P y Q, de esta forma:
¬ ( P ∧ Q ) ⟺ ( ¬ P ) ∨ ( ¬ Q ) ¬ ( P ∨ Q ) ⟺ ( ¬ P ) ∧ ( ¬ Q ) donde:
¬ es el operador de negación (NO) ∧ {\displaystyle \land } \land es el operador de conjunción (Y) ∨ {\displaystyle \lor } \lor es el operador de disyunción (O) ⇔ es un símbolo metalógico que significa "puede ser reemplazado en una prueba lógica"
Entre la aplicaciones de las normas se incluyen la simplificación de expresiones lógicas en programas de computación y diseño de circuitos digitales. Las leyes de De Morgan son un ejemplo de concepto más general de dualidad matemática.

DIFERENCIA
En teoría de conjuntos, la diferencia de dos conjuntos es una operación que da como resultado otro conjunto con los elementos del primer conjunto sin los elementos del segundo conjunto. Por ejemplo, la diferencia entre el conjunto de los números naturales N {\displaystyle \mathbb {N} } \mathbb{N} y el conjunto de los números pares P es el conjunto de los números que no son pares, es decir, los impares I {\displaystyle I} I:
N = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 … } P = { 2 , 4 , 6 , 8 , 10 , 12 … } I = { 1 , 3 , 5 , 7 , 9 , 11 , 13 , 15 , 17 … }
Como no hay ningún número par que no sea un número natural, la diferencia P menos N no tiene ningún elemento, por lo que es el conjunto vacío. La diferencia entre dos conjuntos A y B se denota por A \ B o A − B, por lo que: N \ P = I, y también P − N = ∅.

DIFERENCIA SINETRICA
En teoría de conjuntos, la diferencia simétrica de dos conjuntos es una operación que resulta en otro conjunto cuyos elementos son aquellos que pertenecen a alguno de los conjuntos iniciales, sin pertenecer a ambos a la vez. Por ejemplo, la diferencia simétrica del conjunto de los números pares P y el conjunto de los cuadrados perfectos C es un conjunto D que contiene los cuadrados impares y los pares no cuadrados:
P = { 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , … } C = { 1 , 4 , 9 , 16 , 25 , … } D = { 1 , 2 , 6 , 8 , 9 , 10 , 12 , 14 , 18 , … } }
La diferencia simétrica de conjuntos se denota por Δ, por lo que P Δ C = D.

"CONJUNTO Y SUBCONJUNTO"

Muy buenas hoy les enseño el como podemos apoyarnos atravez de un nuevo trbaajo en el cual nod damos a entender sobre conjuntos y subconjuntos bueno ahorita veremos de que tratan

"CONJUNTO" es una colección de elementos con características similares considerada en sí misma como un objeto. Los elementos de un conjunto, pueden ser las siguientes: personas, números, colores, letras, figuras, etc. .

El concepto de conjunto es intuitivo y se podría definir como una "agrupación bien definida de objetos no repetidos y no ordenados"; Un conjunto está bien definido si se sabe si un determinado elemento pertenece o no al conjunto.

Dentro de la teoría se consideran como primitivos o términos no definidos los conjuntos y los elementos. En general, se designan los conjuntos usando letras latinas mayúsculas y los elementos con letras minúsculas. Intuitivamente, un conjunto es una colección o clase de objetos bien definidos.

"SUBCONJUNTO"

Es cierto que cada elemento de un conjunto A es un elemento de A (es una afirmación tautológica). Por tanto se tiene el siguiente teorema: Todo conjunto A es subconjunto de sí mismo.

Así, dados dos conjuntos A ⊆ B, cabe la posibilidad de que sean iguales, A = B. Por otro lado, es posible también que A contenga algunos pero no todos los elementos de B:

Sea A un subconjunto de B tal que A ≠ B. Entonces se dice que A es un subconjunto propio de B, y se denota por A ⊊ B. (A su vez, se dice que B es un superconjunto propio de A, B ⊋ A) Es verdadero que todos los ejemplos de subconjunto mostrados arriba son de hecho subconjuntos propios. También se utiliza la notación A ⊂ B y B ⊃ A, pero según el autor esto puede denotar subconjunto, A ⊆ B y B ⊇ A; o subconjunto propio, A ⊊ B y B ⊋ A.

"LAS TORRES DE HANON"

Muy buenas hoy les enseñamos a cual como son las torres de hanon bueno mejor pasemos a lo que significa

Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Édouard Lucas. Este juego de mesa individual consiste en un número de discos perforados de radio creciente que se apilan insertándose en uno de los tres postes fijados a un tablero. El objetivo del juego es trasladar la pila a otro de los postes siguiendo ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.

La fórmula para encontrar el número de movimientos necesarios para transferir n discos desde un poste a otro es: 2n - 1

El juego, en su forma más tradicional, consiste en tres postes verticales. En uno de los postes se apila un número indeterminado de discos perforados por su centro (elaborados de madera), que determinará la complejidad de la solución. Por regla general se consideran siete discos. Los discos se apilan sobre uno de los postes en tamaño decreciente de abajo a arriba. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio -desde la base del poste hacia arriba- en uno de los postes, quedando los otros dos postes vacíos. El juego consiste en pasar todos los discos desde el poste ocupado (es decir, el que posee la torre) a uno de los otros postes vacíos. Para realizar este objetivo, es necesario seguir tres simples reglas:

Solo se puede mover un disco cada vez y para mover otro los demás tienen que estar en postes. Un disco de mayor tamaño no puede estar sobre uno más pequeño que él mismo. Solo se puede desplazar el disco que se encuentre arriba en cada poste. Existen diversas formas de llegar a la solución final, todas ellas siguiendo estrategias diversas.

El rompecabezas fue inventado por el matemático francés Édouard Lucas en 1883. Se cuenta una historia sobre un templo en la India en Kashi Vishwanath que contiene una gran sala con tres postes gastados por el tiempo, rodeada de 64 discos dorados. Los sacerdotes de Brahma, actuando bajo el mandato de una antigua profecía, han estado moviendo estos discos de acuerdo con las reglas inmutables de Brahma desde ese momento. Por lo tanto, el acertijo también se conoce como el rompecabezas de la Torre de Brahma. Según la leyenda, cuando se complete el último movimiento del rompecabezas, el mundo se terminará.​ No está claro si Lucas inventó esta leyenda o si se inspiró en ella.

Si la leyenda fuera cierta, y si los sacerdotes pudieran mover los discos a una velocidad de uno por segundo, utilizando el menor número de movimientos, completar la tarea les llevaría 264 - 1 segundos, o aproximadamente 585.000 millones de años,que es aproximadamente 42 veces la edad actual del Universo.

Existen muchas variaciones en esta leyenda. Por ejemplo, en algunos relatos el templo es un monasterio, y los sacerdotes son monjes. Se puede decir que el templo o monasterio se encuentra en diferentes partes del mundo, incluidos Hanói, Vietnam, y puede estar asociado con cualquier religión. En algunas versiones, se introducen otros elementos, como el hecho de que la torre fue creada en el comienzo del mundo, o que los sacerdotes o monjes solo pueden hacer un movimiento por día.

"SERIE FIBONACCI"

Este es una de las funciones en donde se utiliza mas en las matematicas discretas pero bueno comencemos...

En matemáticas, la sucesión o serie de Fibonacci hace referencia a la secuencia ordenada de números descrita por Leonardo de Pisa, matemático italiano del siglo XIII:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,… A cada uno de los elementos de la serie se le conoce con el nombre de número de Fibonacci

¿Cómo se calculan los números de Fibonacci? Existen diferentes formas para calcular los números de Fibonacci:

1. Partiendo de los números 0 y 1, los números de Fibonacci quedan definidos por la función

Sin título

2. Función generadora: Una función generadora para una sucesión cualquiera a0, a1, a2,… es la función f(X) = a0 + a1x + a2x2+…, es decir, una serie formal de potencias donde cada coeficiente es un elemento de la sucesión. Los números de Fibonacci tienen la función generadora:

Sin título

3. Fórmula explícita: Esta manera de calcular los números de Fibonacci utiliza la expresión del número áureo:
Sin título

Los números de Fibonacci en las matemáticas Número áureo El número áureo, número de oro o divina proporción es el valor numérico de la proporción que guardan entre sí dos segmentos de recta a y b (a más largo que b): la longitud total es al segmento a, como a es al segmento b.

Entre sus numerosas propiedades destaca una: el propio número, su cuadrado y su inverso tienen las mismas cifras decimales:

Sin título

La razón o cociente entre un término de Fibonacci y el inmediatamente anterior varía continuamente, pero se estabiliza en el número áureo:

Sin título

Triángulo de Pascal El triángulo de Pascal es una representación de los coeficientes binomiales ordenados en forma triangular. Esto es, cada fila del triángulo representa los coeficientes de los monomios que aparecen en el desarrollo del binomio (a + b)n (tomando el 1 de arriba como la potencia n = 0) o, lo que es lo mismo, los coeficientes que aparecen en el binomio de Newton coinciden con los elementos que aparecen en cada fila del triángulo de Pascal.

La construcción de dicho triángulo es la siguiente:

Colocamos un 1 en el vértice superior del triángulo. Después, en la fila inferior, colocamos un 1 a la derecha y un 1 a la izquierda del 1 de arriba. En las filas inferiores, colocamos 1s en los extremos y en las posiciones intermedias colocamos la suma de los números inmediatamente superiores.

Sin título

Este triángulo tiene varias propiedades curiosas:

Si sumamos los elementos de cada fila obtenemos las potencias de 2: 1, 2, 4, 8, 16,… Si sumamos dos elementos consecutivos de la diagonal 1-3-6-10-15-… obtenemos un cuadrado perfecto: 1, 4, 9, 16, 25,… Si en una fila el primer número después del 1 es un número primo se cumple que todos los demás números son divisibles por ese número primo (excluyendo los 1s claro). Por ejemplo, en la fila 1-7-21-35-35-21-7-1 el primer número después del 1 es el 7, que es primo. Si nos fijamos en el resto de número, 35, 21 y 7, todos son divisibles por 7. Pero la principal curiosidad de este triángulo es la propiedad que le relaciona con los números de Fibonacci:

Sin título

Ternas Pitagóricas Una terna pitagórica consiste en una tripla (a, b, c) que cumple que a² + b² = c² (teorema de Pitágoras).

Existe una estrecha relación entre los números de Fibonacci y las ternas pitagóricas, ya que si cogemos cuatro números consecutivos de la sucesión de Fibonacci, (x, y, w, z) podemos conseguir una terna pitagórica si realizamos las siguientes asignaciones:

Sea ‘a’ el producto de los números que pertenecen a los extremos. a = xz. Sea ‘b’ el doble del producto de los números intermedio. b = 2yw. Sea ‘c’ la suma del producto de los números que están en posición impar y el producto de los números que están en posición par. c = xw + zy. Entonces (a, b, c) es una terna pitagórica.

Los números de Fibonacci en las técnicas de trading En trading, los números de Fibonacci aparecen en los denominados estudios de Fibonacci. Los estudios de Fibonacci engloban a una serie de herramientas de análisis basadas en la secuencia y proporciones de Fibonacci, que representan leyes geométricas de la naturaleza y el comportamiento humano aplicadas a los mercados financieros.

Las herramientas más populares son los retrocesos de Fibonacci, las extensiones de Fibonacci, los arcos de Fibonacci, el abanico de Fibonacci y las zonas temporales de Fibonacci. Otras herramientas menos populares son la elipse de Fibonacci, la espiral de Fibonacci y los canales de Fibonacci. En el siguiente post veremos cómo funcionan estas herramientas.