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
Suscribirse a:
Comentarios (Atom)