Tendencias informaticas del hardware

Información sobre las nuevas tecnologías en el hardware, incluyendo móviles, PC y robotica.

Tendencias informaticas Hardware de Hector L

Linux

Diapositivas realizadas por un compañero, describe los protocolos utilizados en las redes Linux, y algunos comandos utilizados en el sistema operativo con respecto al manejo de las redes.

Redes en Linux de Hector L

Unix

Diapositivas sobre la historia, características y evolución del sistema operativo Unix, también posee una breve descripcion de los comando.

Unix de Hector L

Programación Entera y Modelo de Transporte #2

Los siguientes apuntes fueron tomados el viernes 13 de enero de 2017.

Pasos para resolver un problema con ramificación y acotamiento:

1. Resolver relajación lineal y obtener solución optima.
2. Elegir entre las variables de decisión la que mas impacto brinda a la función objetivo y sus restricciones, tiene que ser fraccionaria.
3. Incorporar dos restricciones con la variable de decisión, una mayor que el valor entero derecho y otra menor que el valor entero izquierdo de la variable.
4. Obtener solución optima del problema lineal y repetir los pasos 1 y 2 hasta que el problema sea in factible o no haya variables enteras en el estado de la rama.
5. Resolver los ejercicios en forma de LIFO (Last in first out), es decir, resolver el primero de la izquierda y luego sus hijos, luego el segundo y así.

Modelo de transporte

Se utiliza para resolver problemas en los que exista el factor de transporte en el modelo lineal y involucra también suministros y demandas de elementos, ejemplos transporte de agua potable de una planta a una ciudad, transporte de energía eléctrica entre otros.

La siguiente tabla representa tres plantas que pueden suministrar electricidad a cuatro ciudades, estas ciudades poseen una demanda y las plantas pueden suministrar una cierta cantidad de KWH.

	Ciudad 1	Ciudad 2	Ciudad 3	Ciudad 4	Suministros
Planta 1	8	6	10	9	35
Planta 2	9	12	13	7	50
Planta 3	14	9	16	5	40
Demanda	45	20	30	30

Las variables de decisión en un problema de transporte involucra una matriz.

Xij = Cantidad de KWH que suministra la planta i a la ciudad j

Restricciones: la suma de todas las inversiones de la planta i a todas las ciudades no deben ser mayor al suministro.

Lo siguientes son las restricciones por parte de los suministros a las plantas (la suma de todas las inversiones a las ciudades j no deben ser mayor a lo que puede suministrar la planta i)

x11 + x12 + x13 + x14 <= 35

x21 + x22 + x23 + x24 <= 50  

x31 + x32 + x33 + x34 <= 40

Y los siguientes son las restricciones por parte de la demanda de las ciudades (la sumatoria de los suministros de las plantas i debe ser igual o mayor a la demanda de la ciudad j)

x11 + x21 + x31 >= 45

x12 + x22 + x32 >= 20

x13 + x23 + x33 >= 30

x14 + x24 + x34 >= 30

Por ultimo las restricciones de signos:

xij >= 0 i = 1, 2, 3 y j = 1, 2, 3, 4

La formulación para la función objetivo seria la siguiente:

min z ∑i=m i=1 ∑ j=n j=1 cij xij

Pasos para ejecutar correctamente el método simplex de transporte

1.  Si el problema esta desequilibrado, se debe equilibrar.
2. Hallar la solución básica inicial (sfb), se puede hacer con alguno de los siguientes métodos:
1. Esquina Noroeste
2. Costo Mínimo 
3. Vogel
3. Calcular Cij para la sfb actual.
4. Si Cij <= 0 para las variables no básicas, entonces la sfb actual es optima. 
5. Con la nueva sfb, se vuelve a los pasos 3 y 4
6. 4' Si cij > = 0 para las variables no básicas, la sfb actual es optima.

En cuanto a el primer paso, se dice que un problema esta equilibrado cuando el valor la sumatoria de la demanda es igual a la sumatoria del suministro.

Los datos que están en el recuadro pequeño, son las capacidades que pueden suministrar la planta i a la ciudad j, los valores que aparecerán en el recuadro externo serán las inversiones que actualmente se realizaran.

Como nota, todos los elementos en blanco serán cero, sin embargo se le pueden incorporar. 

Equilibrar un problema desequilibrado:

Ahora, existen dos casos en el que el problema no este equilibrado:

Cuando el suministro es mayor que la demanda: cuando la cantidad que se puede proveer es mayor a la que necesita, podemos agregar un punto de equilibrio ficticio. Este punto se representara como una nueva ciudad que demande el suministro sobrante.

Cuando el suministro es menor que la demanda: este caso es mas complicado, debido a que en este caso no hay exceso, sino que existe una demanda que no se puede satisfacer, por lo que es infactible (no posee una solución factible). 

La solución para ese caso es el manejo de escasez, que se realiza solo cuando expresamente se indique un valor de penalizacion al no satisfacer la demanda (el enunciado debe indicarlo), de lo contrario se indica que el problema es infactible y no se puede resolver mas.

Se puede observar como si se agregara una planta 4 al problema, que satisfaga las necesidades que faltan.

Los tres métodos:

Método esquina noroeste: básicamente es el mismo recuadro de transporte pero sin los costos. Consiste en representar en el recuadro externo el valor que puede satisfacer el suministro i a la demanda j, luego los valores de la demanda y el suministro son restados.

• Una vez satisfecho una demanda o utilizado un suministro, se coloca "X".
• Si en la esquina noroeste que no es la ultima, tanto el suministro como la demanda es igual, se coloca en el suministro X y en la demanda 0, luego se coloca en la siguiente celda el menor entre el cero y el valor que le sigue.
• Como observación o razonamiento, tanto el suministro como la demanda en la ultima celda deben de ser iguales, de lo contrario hubo un error durante el proceso.

Costo mínimo: toma importancia en los costos y se enfoca en el de menor valor.

• Se toma el menor de todos los costos.
• Se toma el menor entre el suministro y la demanda, se coloca debajo del recuadro con el menor costo y se restan ambos.
• Se tacha la fila o columna satisfecha.

Vogel: 

• Tomar un valor penalizacion por cada fila y columna, lo cual se hace restando los dos valores mas pequeños de la fila (o columna cual sea el caso).
• De entre todas las penalizaciones, tomar la penalizacion con mayor valor.
• Tomar el costo con el valor mas pequeño de la columna/fila de la penalizacion
• Tomar el valor mas pequeño del suministro y la demanda de la celda de costo, y aplicar el mismo procedimiento que costo minimo.
• Se vuelve a calcular las penalizaciones, calculando solo aquellas que no se encuentren en el renglon o no se hayan calculado.

Siguiente clase: 

• Continuación del 3, 4 y 5 paso.

Lenguaje y Compiladores - Parsing Bottom Up #2

Apuntes de la clase del Jueves 12-1-2017, el próximo jueves sera examen de todo lo entendido el año pasado.

Es importante determinar cuando usar SHIFT o REDUCE en la Pila, con el algoritmo de resolución de conflictos resolveremos los conflictos de caso SHIFT/REDUCE y REDUCE/REDUCE.

Recordando:

La acción SHIFT mueve o coloca un nuevo valor terminal en la pila.

____ | XYZ => ____X | YZ

La acción REDUCE puede eliminar cero o mas símbolos en la pila (del lado derecho), o colocar un símbolo no-terminal en la pila (en el lado izquierdo de la producción).

Los conjuntos representados por expresiones regulares son llamados conjuntos regulares.

Una gramática es libre de contexto (GLC) cuando en el lado izquierdo de la gramática solo aparece símbolos terminales.

Nuevos conceptos:

Handle: es una reducción que permite hacer otras reducciones hasta llegar al símbolo inicial.

Prefijos viables: es una parte del handle que se llevara al símbolo inicia.

LWB Es un prefijo viable (Alfa, beta y omega)
LW    Es un prefijo viable (tambien las derivaciones de LWB son prefijos viables)
L       Es un prefijo viable

Item: es una producción con un punto "." en algun lugar del lado derecho de la produccion. Para T -> (E) los items son:

T->. ( E )
T->  (.E )
T->  ( E.)
T->  ( E ).

Nota: Los items que vayan a lambda son LR(0) y su item es

T->L => T -> . (L es Lambda)

Donde el cero de LR representa la cantidad de pasos que ha tomado.

Condiciones:

1. Se debe aplicar REDUCE solo si el resultado permite la eventual transición al símbolo inicial.

2. En un caso SHIFT/REDUCE, el handle debe estar en el tope de la pila y jamas dentro de ella. El detalle es que no existen algoritmos eficientes para detectar los handles.

3. Para cualquier gramática, el conjunto de prefijos viables es un conjunto regular.

Nota: todas las gramáticas para un compilador son SLR.

Reconocer los prefijos viables (ver laminas 9):

Para poderlos reconocer debemos crear un AFN (autómata finito no determinista), lo siguiente son las condiciones para poder construir un AFN. 

1.  Para un estado S' -> .E (Notese el punto), la transición será S' -> E. y la llamamos transición E.
2. Para cada item E -> L . XB y producción X -> Y, realizaremos una transición por cada producción de X. Se va a la transición inicial de la producción que trascendió. En ese caso E, y se coloca X.
3. Un error común es que se dupliquen las mismas producciones, lo correcto es redireccionar a los estados adecuados.
4. Cuando la transicion sea un simbolo terminal, la transicion llegara hasta ese simbolo. 
1. T-> . int*T (Transicion por int) T->int . * T (Transicion por *) T->int * . T

Una vez construido el AFN, lo que sigue es pasarlo a un autómata finito determinista (AFD). Esto se hace debido a que el AFN no es eficiente.

AFD y los posibles conflictos (ver laminas 10):

En el AFD, podemos observar que en cada estado hay conjuntos de items. Se llaman colecciones canónicas de items.

En este conjunto de items, generalmente pueden haber conflictos de tipo REDUCE/REDUCE o  REDUCE/SHIFT, el siguiente es un conjunto de razonamientos para identificarlos.

Existe un conflicto REDUCE/REDUCE si en un estado existen dos items con la opcion de aplicar un REDUCE.  Ejemplo:

E -> T

T -> E + T

Existe un conflicto SHIFT/REDUCE si en un estado existe un item para hacer un SHIFT, y otro para REDUCE.

Si se tiene un conflicto SHIFT/REDUCE en una producción T, se hará un FOLLOW (los siguientes de T)a la producción del estado y comparamos con el siguiente caracter al lado de la barra, si existe hacemos un movimiento REDUCE, de lo contrario SHIFT.

Ejemplo:

S' -> E (Esta producción no se toma en cuenta)

E -> T + E | T

T -> int * T | int | ( E )

Follow(T) = {"+", ")", $}

Como * no pertenece a follow de T, realizaremos un SHIFT, moviendolo al estado 11. Como no hay item al final en alguno del estado 11, no hay conflictos.

Notas: 

- En el libro del dragon se usa otra forma de construcción.

- El algoritmo para resolver este problema usa SLR(0), no se puede usar LR(0).

PASO A PASO:

1. Tenemos la gramatica
2. Expandir gramatica (para obtener el estado inicial de AFN)
3. Calcular los items de la gramatica.
4. Construir el AFN con transiciones lambda.
5. Transformar el AFN-L a AFD llamado R.
6. Ver los posibles conflictos del AFD y calcular los follows de los no-terminales presentes en el conflicto.
7. Aplicar el algoritmo para R recibiendo como entrada la pila R(stack)

Ultimos detalles

1. Para la proxima clase se explicara la tabla de simbolos.
2. Ll(1) - Haskell (transforma la gramatica)
3. SLR  - CUP
4. El examen del jueves va hasta Ll(1)

Links

• Compilador
• Follow

Programación Entera y binaria, ramificacion y acotamiento binario #1

Concepto

La programación entera consiste en encontrar soluciones a problemas de programación lineal donde los valores de las variables deben de ser enteros,

Una de las formas para poder determinar la solución factible de un problema de programación entera, es hacer lo que se denomina una relajación al problema entero, esto se hace realizando de forma gráfica como si fuese un problema de programación lineal.

Tipos

Existen dos tipos de programación entera, están las puras, en las cuales todas las variables de decisión deben ser enteras, y luego las simples, en las que existen variables que NO necesariamente deben de ser enteras.

Entre la programación entera pura, esta una forma particular en la cual solo se aceptan valores cero o uno, esto es programación entera binaria y se usa con mucha frecuencia en ejercicios en los que hayan un elemento este haciendo algo (1) o no (0).

xi (i = 1, 2, 3, 4) {1: Si se hizo la inversión; 0: Si no se hizo la inversión}

Restricciones

Aparte de las condiciones conocidas, existen casos diferentes a los que conocemos en la programación lineal, tomando un ejemplo de inversión que es PE binaria se considera lo siguiente:

1) Se puede invertir cuando mucho en dos inversiones: debido a que solo se puede aceptar cero o uno en las variables, validamos que al hacer la sumatoria, solo existan dos inversiones activas (dos 1).

x1+x2+x3+x4<= 2

2) Si se invierte en la inversión dos, entonces también se debe invertir en la inversión uno: al convertir la inversión 2 con 1, estamos obligando que la inversión uno deba valer también 1, y si hacemos que la inversión 2 valga 0, no estamos obligando que la inversión uno valga 0, dándole libertad de ser 1 si desea.

x2 <= x1

3) Si se invierte en la inversión dos, no puede invertir la inversión cuatro: al hacer la sumatoria de las dos inversiones menor a uno, obligamos que solo una de las dos o ninguna este activas.

x2+x4 <= 1

En otro ejercicio sobre ropa, se puede modelar todo menos el costo fijo, en ese caso se utiliza los valores binarios creando variables de tipo y que pueden tomar 0 o 1.

max z 6x1+4x2+7x3-200y1-150y2-100y3

s.a 3x1+2x2+6x3 <= 150

4x1+3x2+4x3 <= 160

xi >= 0 y enteros

yi = 0,1

En las restricciones de la maquinaria de la ropa, para establecer que si xi > 0 entonces yi = 1, se realiza con un valor de capacidad máxima en xi y se multiplica con mi.

xi <= mi * yi donde mi es la capacidad máxima i

Entonces:

x1 <= 40y1

x2 <= 54y2 

En ese caso da 53.3 pero se garantizamos que se cumpla la restriccion

x3 <= 25y3

Debemos tener en cuenta todas las restricciones como tal.

Método de ramificación y acotamiento binario:

En el ejemplo de la mochila, realizamos una tabla:

Objeto	ci / ai	Clasificacion	Sobrante	Obsevaciones
1	1	3.5(4)	x1 = 10/40 = 1/4	Empate para el 3° o 4°
2	1 3/5	2	70-30 = 20
3	1/3	7
4	1	3.5(3)	2-10=10	Empate para el 3° o 4°
5	2/5	6
6	1/2	5
7	2	1	100-30=70

Como es un ejercicio entero no puro, se puede fraccionar ciertas variables de decisión. El objetivo es satisfacer la función objetivo.

La ramificación consiste en ir ramificando el problema original por medio de nuevas restricciones, se debe ramificar cuando las variables sean fraccionarias, hasta que solo sean enteras o infactibles.

Recordando, una solución es infactible cuando la restricción no entra en la región factible.

• La ramificación se hace con la variable que brinde mas importancia económica en el problema. 
• Deben ser fraccionarios, una vez se encuentra un valor entero no se ramifica mas.
• Funciona con lifo, resolviendo el ultimo problema que se encuentre.

Ver:

Programacion Entera, algo completo

Examen de Programación Lineal

El siguiente articulo representa el primer examen que presente sobre la materia de investigacion de operaciones sobre programacion lineal.

Incluye:

• Método Gráfico
• Método Simplex
• Dos fases
• Dual
• Forma estándar
• Analisis de Sensibilidad

Espero que alguien logre encontrarlo de utilidad. Si tengo tiempo disponible subire mis respuestas, no fue bien pero asi evitan cometer los mismos errores.

Teoría:

1)      Describa un problema no acotado ¿Cómo se detecta en el método simplex? 5%

2)      ¿Como se detecta el método grafico de un problema que tiene múltiples soluciones? 5%

3)      ¿Para que se utiliza el método simplex 2 fases? Describa los casos que puedan presentarse 5%

4)      Describa la suposición de proporcionalidad de un PPL 5%

Gráficamente:

5)      MINE Posee dos minas: la primera produce diario 1 tonelada de hierro de alta calidad, 3 toneladas de hierro de baja calidad y 5 toneladas de baja calidad. La segunda produce 2 toneladas de las tres cualidades. La refinería necesita al menos 80 toneladas de mineral de alta calidad, 160 toneladas de mineral de calidad media, y 200 toneladas de calidad baja. El coste diario de operación es 2000 dólares en cada mina.

Resolver gráficamente para minimizar costos 15%

Estándar:

6)      ALCA produce rollos de papel de aluminio en un ancho estándar de 15 metros, según se especifica en la tabla, por ejemplo si se realizan 3 cortes de 5 metros se obtienen los 15 metros sin desperdicio, los requerimientos de los clientes están dados de la siguiente forma: rollos de 5 metros 200 unidades, rollos de 7 metros 140 unidades, rollos de 9 metros 270 unidades.

Tipo corte	5 Metros	7 Metros	9 Metros	Desperdicio
1	3	-	-	0
2	1	1	-	3
3	1	-	1	1
4	-	2	-	1

Formular en forma estándar para optimizar los rollos a utilizar 15%

Simplex:

7)      YOKE fabrica yogurt y quesos, un yogurt requiere de 1 hora de mano de obra y 9 litros de leche. Un queso requiere de 1 hora de mano de obra y 5 litros de leche. Se dispone de6 horas de mano de obra y 45 litros de leche. Cada yogurt contribuye 8 dólares a las utilidades y cada queso 5 dólares.

Formular en forma algebraica PPL para maximizar las utilidades de YOKE 15%

Análisis de sensibilidad:

                Responder preguntas en función  del enunciado anterior:

a)      ¿Para que valores de utilidad del yogurt la base actual sigue siendo optima? 10%

b)      ¿Cual seria la solución optima si se agrega la siguiente restricción de demanda: se debe fabricar por lo menos 4 quesos? 10%

c)       ¿Para que cantidad de leche la base actual se mantiene optima? 10%

d)      ¿Si hubiera 35 litros de leche cual seria la solución optima? 5%

Método Simplex de programación lineal

Que tanto tiempo me tomo aprender simplex

Aprender la estrategia de simplex fue algo difícil al inicio debido a que tendía a confundirme durante la explicaciones en clases, sin embargo luego de un par de vídeos en YouTube y practicar un par de ejercicios por una semana (antes del examen) logre entender un par de cosas sobre esta estrategia y entendí que no era tan difícil una vez entiendes los pasos a realizar.

Mi entendimiento de porque debemos usar simplex

Primero que nada, el motivo por el que lo utilizamos es cuando en nuestro problema de programación lineal (PPL) existen mas de una variable de decisión, normalmente utilizamos el método gráfico para representar una gráfica de dos dimensiones ya que en nuestro problema presentamos solamente dos variables de decisión .

Sin embargo para este caso, existe mas de dos variables de decisión, por lo que no podríamos representarlo visualmente a menos que hiciéramos una gráfica de tres dimensiones, lo cual tomaría mas tiempo del necesario. También si existen casos en las que haya tres o cuatro o mas variables de decisión, seria imposible para nosotros representarlo gráficamente.

Por eso existe el método simplex, para representar de forma algebraica, problemas de programación lineal que tengan mas de dos variables de decisión.

Cual es la estrategia que entendí

Los primeros pasos para obtener las variables de decisión, función objetivo y restricciones siguen siendo necesarios, luego de eso debemos de implementar unos métodos nuevos.

1. Determinar las variables de decisión 
2. Determinar función objetivo
3. Determinar las restricciones del enunciado y la de signos
4. Convertir el sistema de ecuaciones (que son tanto las restricciones) a forma estándar.
5. Realizar tabloide simplex.
6. Transformar elementos del tabloide simplex realizando una serie de pasos, hasta cumplir una cierta condición.

Los primeros tres pasos ya deberían saberlos ya que los explicamos en el método gráfico, lo que vamos a destacar es como pasar las restricciones a forma estándar, luego con los valores de nuestro sistema de ecuaciones haremos una tabla, e iremos editando por medio de ciertas normas los valores de la tabla, esto se hará hasta cumplir una cierta condición, la información esta ambigua?, si, ya lo explicare a mas detalle.

La forma estándar

Para que el tabloide indique los resultados de forma correcta, debemos pasar los datos del sistema de ecuaciones en forma estándar, que es convertir las ecuaciones de desigualdad en ecuaciones de igualdad (eliminar el mayor igual o menor igual y convertirlos en solo igualdad). 

Debemos integrar dos elementos nuevos los cuales son las variables de holgura y de excedencia a las restricciones, dependiendo del caso de desigualdad, agregaremos una variable de estos tipos.

La variable de holgura se agrega en restricciones de tipo menor igual que (<=) y  se representa con si, donde i establece el numero de la restricción. Esta variable representa la cantidad restantes en la restricción.

Por ejemplo, para una restricción en la que la suma de tiempo para poder preparar unas manzanas y peras no deben ser mayor a 50 horas, y la cantidad de tiempo dedicada a manzanas y peras es 20 horas cada una, la variable de holgura representaría las 10 horas que restantes para ser iguales al segundo miembro (50 horas). Se representa por adición al primer miembro.

20x1 + 20x2 <= 50 (Restricción de desigualdad)

||

20x1 + 20x2 + s1 = 50 (Restricción pasada a forma estándar)

La variable de excedencia se agrega en restricciones de tipo mayor igual que (>=) y  se representa con ei, donde i establece el numero de la restricción. Esta variable representa la cantidad sobrante en la restricción.

Por ejemplo, para la misma restricción en la que la suma de tiempo para poder preparar unas manzanas y peras pero decimos que deben ser mayor o igual a 50 horas, y la cantidad de tiempo dedicada a manzanas y peras es 30 horas cada una, la variable de holgura representaría las 10 horas que sobran para ser iguales al segundo miembro (50 horas). Se representa por sustracción al primer miembro.

30x1 + 30x2 >= 50 (Restricción de desigualdad)

||

30x1 + 30x2 - e1 = 50 (Restricción pasada a forma estándar)

Dependiendo del caso de desigualdad, agregaremos una variable de holgura o excedencia. En resumen

1. Si la restricción i es >=, se resta una variable de excedencia ei al primer termino y se establece la igualdad.
2. Si la restricción i es <=. se suma una variable de holgura si al primer termino y se establece la igualdad.
3. Si la restricción ya esta en igualdad =, se deja como esta.

El tabloide simplex

El objetivo de esta tabla es determinar de forma directa la mejor solución optima por medio del sistema de ecuaciones en forma estándar. Esto se realiza con los siguientes pasos.

Primero debemos igualar a cero la ecuación en Z, es decir la función objetivo, es sencillo, simplemente despejamos todos los elementos de la función objetivo al lado de z, e igualamos a cero.

max z 3x1 + 2x2

||

z - 3x1 + 2x2 = 0

Lo que sigue es crear una tabla que tenga como se muestra a continuación:

Donde renglón es la fila del sistema de ecuaciones, que va empezando desde cero, el renglón cero representará la función objetivo que despejamos anteriormente (z).

Z Representa la fila que posee el termino de z, se representa con 1 si z exista en i fila o 0 en caso contrario.

x1, x2, x3 representan los coeficientes de las variables de decisión en la fila i.

S1, S2, S3 representan las variables de holgura presentes en el sistema de ecuaciones, cabe destacar que en este caso solo hay variables de holgura pero puede haber casos en los que existan variables de excedencia.

Lado derecho representa el valor derecho de la igualdad, una cosa a destacar es que ese valor representa el elemento de la fila que posee un valor uno (sea en las variables de decisión o las variables de holgura), y se representa haciendo una igualdad, por ejemplo si en la fila 1 hay un valor 1 en S1 y el lado derecho de mi igualdad vale 50, lo represento en la columna Lado derecho de la siguiente forma:

S1 = 50

Cociente se usa como referencia, lo veremos mas adelante.

Antes que nada, no te asustes con la tabla, huele el miedo... una ves que entiendas la metodología lo veras como si fuera una suma de enteros.

El procedimiento

Debes llenar el tabloide con la función objetivo que se igualo a cero y las restricciones en forma estándar. La siguiente imagen provee un sistema de ecuaciones y un tabloide simplex con los valores del sistema.

El objetivo del tabloide, es el de eliminar todos los elementos negativos del renglón cero (o renglón z) cuando es de maximización, y cuando es un caso de minimización, eliminar todos los elementos positivos, quedando solo negativos.

Para ello, es necesario un valor pivote, seleccionaremos el valor negativo con el valor absoluto mas alto, esa sera nuestra columna pivote, seguidamente dividiremos cada valor del lado derecho por el valor respectivo de la columna pivote, y tomaremos el valor pivote de la fila con el resultado mas pequeño.

Ahora que ya tenemos nuestro pivote, debemos de igualar ese valor a uno, eso se hace diviendo todo el renglon por el valor pivote, es decir, si el pivote en el renglón es 5, debo dividir todos los elementos del renglon por 5.

Lo siguiente es igualar los demas elementos de la columna pivote en cero, esto se hace multiplicando el renglon pivote por un valor que sumado en el valor de la columna sea igual a cero. Ejemplo, en mi columna tengo los valores 5 1 y 7, ya habiendo conseguido el pivote y despues de haberlo dividido. Lo que debo hacer es multiplicar el renglón pivote por -7 y sumarselo al renglon que posee el valor 7, asi igualo a cero el 7.

Luego de haber realizado la operacion con todos los renglones, se considera una iteracion, lo que sigue es buscar un nuevo pivote, realizando el mismo procedimiento anteriormente, y luego realizando las operaciones entre renglones para igualar a ceros y uno.

Esto lo hacemos hasta que no haya valores negativos en maximizacion o  valores positivos en minimizacion.

Casos especiales

Como pueden notar, el metodo es muy intuitivo, pero tenemos que observar ciertos casos.

1. En caso de haber restricciones de >=, tendriamos que multiplicar la desigualdad por -1 para asi convertirla en <=, y luego aplicar la forma estandar que conocemos.
2. En caso de haber un =, debemos de aplicar otra metodologia, sea el metodo de la gran M, o dual o dos fases.

Últimos detalles

Lo mas importante es aprender a visualizar el tabloide, ya que existen algunos valores que se pueden escribir sin calcular, como la columna z, la columna del renglon, y cuando obtengamos el pivote, ya sabemos que debemos colocar el valor pivote como 1 y el resto de la columna como cero. Confuso si, pero se puede dominar.

Lenguaje y Compiladores - Parsing Bottom Up #1

Anteriormente, vimos la derivación descendente, a continuación aprenderemos la reducción que consiste en ir desde la cadena de entrada hasta el símbolo inicial del árbol sintáctico.

Parsing Bottom-Up:

Es una estrategia general. Siendo determinista es decir, sin backtracking. Es mas eficiente que el método predictivo debido a que no utiliza backtracking, es usado por la mayoría de generadores de analizadores sintácticos conocidos como Java, C++, etc.

Usa la gramática en su versión mas natural por lo que no es necesaria la factorizacion a diferencia del top down.

Establece reglas de prioridad y asociatividad de los operadores. Podemos asociarlo con una operación matemática.

5x8x3

Para nosotros no es difícil determinar que el orden de los factores no alterara el producto, sin embargo, el computador no tiene esa capacidad, por lo que debemos establecer reglas de prioridad y asociatividad indicando en que dirección se hará las operaciones. Esto se hace para evitar la ambigüedad en la gramática.

Recordando, una gramática es ambigua cuando genera dos arboles sintácticos para una misma entrada.

La estrategia:

La idea es construir el árbol sintáctico de abajo hacia arriba, desde las hojas (tokens de entrada) hasta la raíz (símbolo no terminal de inicio). Esto se hace con el método de reducción, distinto al top down que usa producción.

Algo a notar es que la reducción se debe hacer por la derecha.

Reducción por desplazamiento:

Si hacemos las derivaciones por la derecha, debe haber una secuencia de símbolos terminales por la derecha, y por la izquierda símbolos tanto terminales como no terminales.

Si lo tuviéramos que visualizar, seria como una barra que atraviesa la cadena de entrada. Podemos indicar también el área a la derecha de la barra como área no examinada.

|int * int + int -> int * T | + int

Para la reduccion por desplazamiento, existen dos movimientos.

Movimientos reduce: reemplaza la parte derecha de una produccion por la parte izquierda de un paso de reduccion.

Movimientos shift: basicamente rueda la barra a la derecha. Generalmente se hace al no encontrar produccion, se hace hasta no haber mas entrada sin analizar.

Si se puede hacer hacer shift/reduce en un paso, esto se puede resolver con precedencia.

Si es un caso en el que se puede hacer reduce/reduce este sera mas complicado, para el proximo articulo se indicara la forma de resolver el problema.

Recurso usado:

- Lamina: Parsing Bottom-Up 

Terminos a investigar:

- Prefijo viable

- Item: implementa un algoritmo con los automatas finitos deterministas.

Tendencias en las redes y telecomunicaciones

Las laminas fueron para una presentación sobre las nuevas tecnologías en el ámbito de las redes y telecomunicaciones, da breves definiciones y características del Internet, ademas de sus peligros y las nuevas tendencias que rigen las telecomunicaciones telefónicas y de redes.

Redes y telecomunicaciones tendencias de Hector L

Gestion de Riesgos

Buen día, adjunto dejo unas laminas que realice sobre una exposición de la gestión de riesgos, lo hice en un par de horas así que no tiene tanta calidad a diferencia de otras que he hecho, pero de algo sirve.

Gestion de riesgo software de Hector L