Terminología de Redes

Terminología de Redes by on Scribd

PROBLEMA DEL AGENTE VIAJERO

En el Problema del Agente Viajero - TSP (Travelling Salesman Problem), 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. 

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.

Los Mapas de Karnaugh

     

Los Mapas de Karnaugh son una herramienta muy utilizada para la simplificación de circuitos lógicos. Cuando se tiene una función lógica con su tabla de verdad y se desea implementar esa función de la manera más económica posible se utiliza este método.
Ejemplo: Se tiene la siguiente tabla de verdad para tres variables. Se desarrolla la función lógica basada en ella. (primera forma canónica). Ver que en la fórmula se incluyen solamente las variables (A, B, C) cuando F cuando es igual a “1”. Si A en la tabla de verdad es “0” se pone A, si B = “1” se pone B, Si C = “0” se pone C, etc.

Reglas de la suma y el producto

1:Si una primera tarea puede realizarse de "m" formas mientras que una tarea puede realizarse de "n" formas y no es posible realizar ambas tareas de manera simultanea, entonces para llevar a cabo cualquiera de ellas puede utilizarse cualquiera de ellas.

2:Si un procedimiento se puede descomponer en las etapas primera y segunda y si existen "m" resultados posibles de la primera etapa, para cada uno de estos resultados existen "n" resultados posibles para la segunda etapa, entonces el procedimiento total que se puede realizar en el orden dado.

Principios fundamentales del conteo

*La enumeración o conteo puede parecer un proceso obvio que u  estudiante aprende a estudiar aritmética por primera vez. Pero luego según parece se presta poca atención en lo que se refiere a un desarrollo más amplio del conteo con forme al estudiante pasa áreas mas difícil de las matemáticas, como el álgebra, geometría, trigonometría y el calculo. En consecuencia deberá servir como advertencia acerca del conteo.

*La enumeración no termina con la aritmética:
también en aplicaciones en áreas como la teoría de códigos como la contabilidad y estadísticas.

Actividades de permutaciones

1:¿Cuantas palabras se pueden formar de 4 letras con la palabra AXEL? 

Escriba el listado de las palabras que se pueden formar.

P4 = 4!                       A          X          E            L
P4 = 4*3*2*1                     axel       xale       exal       lexa
P4 = 24                    alxe       xael       exla       leax
                                aelx       xeal       elax       laxe
                                alex       xela       elxa       laex
                                axle       xlea       eaxl       lxea
                                aexl       xlae       ealx       lxae

2:¿Cuantas palabras diferentes de 5 letras se pueden formar con la palabra libro?

P5 = 5!
P5 = 5*4*3*2*1
P5 = 120 Palabras

3:¿Cuantas palabras diferentes de 6 letras se pueden formar con la palabra tratar?

PRtra = 6!                                                    PRtra = 720
       2! 2! 2!                                                               8

PRtra = 6*5*4*3*2*1                                                           PRtra = 90
          2*1   2*1    2*1


4:¿Cuantas palabras de 10 letras se pueden formar usando la palabra termometro?

P10222 = 10!
       2! 2! 2! 2! 2!

P10222 = 10*9*8*7*6*5*4*3*2*1
            2*1    2*1     2*1      2*1      2*1

P10222 = 1,814,400
                    16

P10222 = 113,400

PERMUTACIONES CIRCULARES

*Se utiliza cuando los elementos se van a ordenar en circulo, por ejemplo los comenzales en una mesa de modo que el primer elemento que se sitúa en la mesa, determina el principio y el fin de la lista.

La formula es:

PCn*1 = n!

1:¿De cuantas formas distintas pueden sentarse 8 personas al rededor de una mesa redonda?

PC8-1 = 7!

PC7   = 7*6*5*4*3*2*1

PC7  = 5,040 Formas de sentarse en la mesa