Unidad 3 Redes by on Scribd
viernes, 21 de junio de 2019
Problema del viajante
Problema del viajante
El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en la investigación de operaciones y en la ciencia de la computación.
El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y en la fabricación de circuitos electrónicos. Un poco modificado, aparece como: un sub-problema en muchas áreas, como en la secuencia de ADN. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem).
El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en la investigación de operaciones y en la ciencia de la computación.
El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y en la fabricación de circuitos electrónicos. Un poco modificado, aparece como: un sub-problema en muchas áreas, como en la secuencia de ADN. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem).
martes, 28 de mayo de 2019
Mapas de Karnaugh
Los mapas de Karnaugh reducen la necesidad de hacer cálculos extensos para la simplificación de expresiones booleanas, aprovechando la capacidad del cerebro humano para el reconocimiento de patrones y otras formas de expresión analítica, permitiendo así identificar y eliminar condiciones muy inmensas.
El mapa de Karnaugh consiste en una representación bidimensional de la tabla de la verdad de la función a simplificar. Puesto que la tabla de verdad de una función de N variables posee 2N filas, el mapa K correspondiente debe poseer también 2N cuadrados. Las variables de la expresión son ordenadas en función de su peso y siguiendo el codigo 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.
viernes, 12 de abril de 2019
Tecnicas de conteo
Las técnicas de conteo son aquellas que son usadas para enumerar eventos difíciles de cuantificar.
Estas técnicas de conteo tienen como objetivo las combinaciones, estas
se forman a través de 2 condiciones: con repetición y sin repetición, se
pueden visualizar en forma de árboles,grupos y matriz (arreglo).
Empezaremos por explicar en que consiste el teorema fundamental de la multiplicación y de la adición.
Empezaremos por explicar en que consiste el teorema fundamental de la multiplicación y de la adición.
Teorema Fundamental de la multiplicación:
Si una combinación se quiere establecer de "n formas" y cada una de
ellas se puede llevar a cabo de "m maneras distintas" en una segunda
operación. Entonces se dice que juntas las operaciones pueden
realizarse: nxm.
Teorema Fundamental de la Adición: Si
un evento se puede llevar a cabo de "n o m lugares distintos", además
de no ser posible que se lleve a cabo el mismo evento o dos lugares
distinto al mismo tiempo. Entonces el evento se puede realizar: n+m formas diferentes.
Teoria de conjunto
3 CONCEPTOS DE CONJUNTOS:
Un conjunto A es un subconjunto de un conjunto B si cada elemento en
A está también en B - Por ejemplo, si A = {1, 3, 5} y B = {1, 2, 3, 4,
5}, entonces A es un subconjunto de B , y escribimos.
DEFINICIONES DE:
UNION: En la teoría de conjuntos, la unión de dos conjuntos es una operación que resulta en otro conjunto, cuyos elementos son los mismos de los conjuntos iniciales. Por ejemplo, el conjunto de los números naturales es la unión del conjunto de los números pares positivos P y el conjunto de los números impares positivos
INTERSECCION: Lugar en que se cortan o se encuentran dos líneas, dos superficies o dos sólidos.
COMPLEMENTO: Cosa que se añade a otra para hacerla mejor, más completa, efectiva o perfecta.
LEY DISTRIBUTIVA: En matemáticas y en particular en álgebra abstracta, la distributiva es la propiedad de los operadores binarios que generaliza la propiedad distributiva del álgebra elemental.
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
LEY DE 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 {\displaystyle \mathbb {N} } \mathbb{N} y el conjunto de los números pares {\displaystyle P} P es el conjunto de los números que no son pares, es decir, los impares {\displaystyle I} I:
DIFERENCIA SIMETRICA: 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.
- En matemáticas, un 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.
- conjunto (del latín coniunctus) es lo que está unido, contiguo o incorporado a otra cosa, o que se encuentra mezclado, combinado o aliado con otra cosa diversa. Un conjunto, por lo tanto, es un agregado de varias cosas o personas.
- Un conjunto o colección lo forman unos elementos de la misma naturaleza, es decir, elementos diferenciados entre sí pero que poseen en común ciertas propiedades o características, y que pueden tener entre ellos, o con los elementos de otros conjuntos, ciertas relaciones.
- En las matemáticas, un conjunto A es subconjunto de un conjunto B si A «está contenido» dentro de B
- Conjunto de elementos que tienen las mismas características y que está incluido dentro de otro conjunto más amplio
- Los diagramas de Venn son esquemas usados en la teoría de conjuntos, tema de interés en matemáticas, lógica de clases y razonamiento diagramático. Estos diagramas muestran colecciones de cosas por medio de líneas cerradas.
- Un diagrama de Venn usa círculos que se superponen u otras figuras para ilustrar las relaciones lógicas entre dos o más conjuntos de elementos.
- Los diagramas de Venn se usan para mostrar gráficamente la agrupación de elementos en conjuntos, representando cada conjunto mediante un círculo o un óvalo. Nosotros vamos a ver y a estudiar ejemplos con 2 conjuntos: el conjunto A y el conjunto B.
DEFINICIONES DE:
UNION: En la teoría de conjuntos, la unión de dos conjuntos es una operación que resulta en otro conjunto, cuyos elementos son los mismos de los conjuntos iniciales. Por ejemplo, el conjunto de los números naturales es la unión del conjunto de los números pares positivos P y el conjunto de los números impares positivos
INTERSECCION: Lugar en que se cortan o se encuentran dos líneas, dos superficies o dos sólidos.
COMPLEMENTO: Cosa que se añade a otra para hacerla mejor, más completa, efectiva o perfecta.
LEY DISTRIBUTIVA: En matemáticas y en particular en álgebra abstracta, la distributiva es la propiedad de los operadores binarios que generaliza la propiedad distributiva del álgebra elemental.
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
LEY DE 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 {\displaystyle \mathbb {N} } \mathbb{N} y el conjunto de los números pares {\displaystyle P} P es el conjunto de los números que no son pares, es decir, los impares {\displaystyle I} I:
DIFERENCIA SIMETRICA: 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.
Torres de hannoi
¿QUE SON LAS TORRES DE HANOIL?
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Édouard Lucas.1 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. 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
¿COMO ES EL ALGORITMO PARA RESOLVER EL PROBLEMA?
La solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de pasos para resolver el problema crece exponencialmente conforme aumenta el número de discos.Como ya se ha indicado, el número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi es 2n - 1, donde n es la cantidad de discos.4 Una manera sencilla para saber si es posible terminar el "juego" es que si la cantidad de discos es impar la pieza inicial ira a destino y si es par a auxiliar.
Solucion Simple
Una forma de resolver el problema se fundamenta en el disco más pequeño, el de más arriba en la varilla de origen. En un juego con un número par de discos, el movimiento inicial de la varilla origen es hacia la varilla auxiliar. El disco 2.o n-1 se debe mover, por regla, a la varilla destino. Luego, el disco n.o 1 se mueve también a la varilla destino para que quede sobre el disco n.o 2. A continuación, se mueve el disco que sigue de la varilla origen, en este caso el disco n.o 3, y se coloca en la varilla auxiliar. Finalmente, el disco n.o 1 regresa de la varilla destino a la origen (sin pasar por la auxiliar), y así sucesivamente. Es decir, el truco está en el disco más pequeño.
Mediante Recursividad
Este problema se suele plantear a menudo en programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, si llamamos origen a la primera pila de discos, destino a la tercera y auxiliar a la intermedia, y si a la función la denomináramos hanoi, con origen, auxiliar y destino como parámetros
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Édouard Lucas.1 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. 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
¿COMO ES EL ALGORITMO PARA RESOLVER EL PROBLEMA?
La solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de pasos para resolver el problema crece exponencialmente conforme aumenta el número de discos.Como ya se ha indicado, el número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi es 2n - 1, donde n es la cantidad de discos.4 Una manera sencilla para saber si es posible terminar el "juego" es que si la cantidad de discos es impar la pieza inicial ira a destino y si es par a auxiliar.
Solucion Simple
Una forma de resolver el problema se fundamenta en el disco más pequeño, el de más arriba en la varilla de origen. En un juego con un número par de discos, el movimiento inicial de la varilla origen es hacia la varilla auxiliar. El disco 2.o n-1 se debe mover, por regla, a la varilla destino. Luego, el disco n.o 1 se mueve también a la varilla destino para que quede sobre el disco n.o 2. A continuación, se mueve el disco que sigue de la varilla origen, en este caso el disco n.o 3, y se coloca en la varilla auxiliar. Finalmente, el disco n.o 1 regresa de la varilla destino a la origen (sin pasar por la auxiliar), y así sucesivamente. Es decir, el truco está en el disco más pequeño.
Mediante Recursividad
Este problema se suele plantear a menudo en programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, si llamamos origen a la primera pila de discos, destino a la tercera y auxiliar a la intermedia, y si a la función la denomináramos hanoi, con origen, auxiliar y destino como parámetros
viernes, 15 de marzo de 2019
Serie Fibonacci
¿Como es?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:
¿Quien la creo?
Leonardo de Pisa
¿Como se hace?
1. Partiendo de los números 0 y 1, los números de Fibonacci quedan definidos por la función
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.
Leonardo de Pisa
¿Como se hace?
1. Partiendo de los números 0 y 1, los números de Fibonacci quedan definidos por la función
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
3. Fórmula explícita: Esta manera de calcular los números de Fibonacci utiliza la expresión del número áureo
Triangulo de pascal
¿Qué es?
El triángulo de Pascal es un triángulo de números enteros, infinito y simétrico.
¿Cómo se construye?
Se empieza con un 1 en la primera fila, y en las filas siguientes se van colocando números de forma que cada uno de ellos sea la suma de los dos números que tiene encima.
¿Para qué se usa?
permite calcular de forma sencilla números combinatorios lo que sirve para aplicar el
binomio de Newton
viernes, 8 de marzo de 2019
viernes, 8 de febrero de 2019
Características de las matemáticas discretas
NUMEROS NATURALES, ENTEROS, RACIONALES, IRRACIONALES Y REALES
Los números naturales "N" Son los números que se usan para contar los elementos de un conjunto (0,1,2,3,4,5,6,7[…]) en ese conjunto no hay términos medios. Con estos números se pueden hacer operaciones como sumarse, restarse , multiplicarse y dividirse.
Los números enteros "Z" son un conjunto de números que incluye a los números naturales
distintos de cero (1, 2, 3, ...), los negativos de los números naturales (..., −3, −2, −1) y al cero, 0.
Los enteros negativos, como −1 ó −3 (se leen "menos uno", "menos tres", etc.), son menores que
todos los enteros positivos (1, 2, ...) y que el cero. Al igual que los números naturales, los números enteros pueden sumarse, restarse, multiplicarse y dividirse, de forma similar a los primeros. Sin embargo, en el caso de los enteros es necesario calcular también el signo del resultado.
Los números enteros extienden la utilidad de los números naturales para contar cosas.
Pueden utilizarse para contabilizar pérdidas.
Los números racionales "Q" se llama número racional a todo número que puede representarse
como el cociente de dos enteros con denominador distinto de cero (una fracción común). El término racional alude a ración o parte de un todo, y no al pensamiento o actitud racional.
Definimos un número racional como un decimal finito o infinito periódico (por ejemplo,
el número decimal finito 0,75 es la representación decimal del número racional 3/4. El número
decimal infinito periódico 0,333... es la representación decimal del número racional 1/3).
Los números Irracionales son números que poseen infinitas cifras decimales no periódicas, que por lo tanto no pueden ser expresados como fracciones.
Pi, o como se lo conoce mejor con su símbolo π, este es el más conocido de los números irracionales, y se utiliza en su mayoría para matemáticas, física e ingeniería. Su valor es el cociente entre la longitud o perímetro de la circunferencia y la longitud de su diámetro. De él se han calculado millones de cifras decimales y aún sigue sin ofrecer un patrón. La aproximación de su número es 3.141592653589...
Los números reales no son más que el conjunto de los numero racionales y los números irracionales. Con los números reales podamos acometer operaciones tales como las sumas (interna, asociativa, conmutativa, de elemento opuesto, de elemento neutro…) o las multiplicaciones. En este último caso habría que subrayar que en lo que respecta a la multiplicación de los signos de los números el resultado sería el siguiente: + por + equivale a +; – por – es igual a +; – por + da como resultado -; y + por – es igual a -.
Los números Imaginarios son números cuya potenciación es negativa. Es decir que cuando se eleva al cuadrado o se multiplica por sí mismo, su resultado es negativo. Si se eleva al cuadrado a cualquier otro número real su resultado siempre será positivo. Por ejemplo cinco al cuadrado o 5², es decir 5 × 5 da como resultado 25. En su defecto, -5² a pesar de ser un número negativo su resultado también será positivo debido a que -5 × -5 anula su negatividad y da como resultado 25.
Por lo tanto un número potenciado que de resultado negativo solo puede suceder en la imaginación, pero a pesar de parecer imposibles los números complejos e imaginarios son muy útiles y tienen una utilidad real para resolver problemas que de otra manera serían un fracaso.
SUBCONJUNTOS
SUBCONJUNTOS
Sean los conjuntos A={ 0, 1, 2, 3, 5, 8 } y B={ 1, 2, 5 }
En este caso decimos que B está contenido en A, o que B es subconjunto de A. En general si A y B son dos conjuntos cualesquiera, decimos que B es un subconjunto de A si todo elemento de B lo es de A también.
Por lo tanto si B es un subconjunto de A se escribe BA. Si B no es subconjunto de A se indicará con una diagonal ₵ .
Note que Є se utiliza solo para elementos de un conjunto y solo para conjuntos.
CONJUNTOS POTENCIA
Dado un conjuntos, se llama conjunto potencia o conjunto de partes de S (se denota por P(S) o 2s) al conjunto de todos los subconjuntos de S. En la teoría de conjuntos basada en los Axiomas de Zermelo-Fraenkel, la existencia del conjunto potencia se establece por el axioma del conjunto potencia.
Por ejemplo, si S= {a, b, c} entonces el conjunto potencia de S es
P(S) = {{ }, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}...
Suscribirse a:
Comentarios (Atom)