LECCION 10 PROBLEMAS DINAMICOS.ESTRATEGIA MEDIOS-FINES

DEFINICIONES

SISTEMA: Es el medio ambiente con todos los elementos e interacciones existentes donde se plantea la situación.

ESTADO: Conjunto de características que describen integralmente un objeto, situación o evento en un instante dado; al primer estado se lo conoce como “inicial”, al último como “final”, y a los demás como “intermedios”.

OPERADOR: Conjunto de acciones que define un proceso de transformación mediante el cual se genera un nuevo estado a partir de uno existente; cada problema puede tener uno o ms operadores que actúen de forma independiente y uno a la vez.

RESTRICCION: Es una limitación, condicionamiento o impedimento existente en el sistema que determina la forma de actuar de los operadores, estableciendo las características de estos para generar el paso de un estado a otro.

ESTRATEGIAS MEDIO-FINES

Es una estrategia para tratar situaciones dinámicas que consiste en identificar una secuencia de acciones que transformen el estado inicial o de partida en el estado final o deseado.

Para la aplicación de esta estrategia debe definirse el sistema, el estado, los operadores y las restricciones existentes. Luego, tomando como punto de partida un estado denominado inicial, se construye un diagrama conocido como Espacio del Problema donde se visualizan todos los estados generados por sucesivas aplicaciones de los operadores actuantes en el sistema. La solución del problema consiste en identificar la secuencia de operaciones que deben aplicarse para ir del estado inicial al estado final o deseado.

Ejemplo: Dos mestizos y dos indios están en una margen de un río que desean cruzar. Es necesario hacerlo usando el bote que disponen.  La capacidad máxima del bote es de dos personas. Existe una limitación: en un mismo sitio el número de indios no puede exceder al de misioneros porque, si lo excede, los indios se comen los mestizos ¿Cómo pueden hacer para cruzar los cuatro el río para seguir su camino?

Sistema: Río con cuatro personas (dos mestizos y dos indios) y un bote. Estado inicial: Los dos mestizos y los dos indios en una ribera del río con el bote

Estado final: Los dos mestizos y los dos indios en la ribera opuesta del río con el bote.Operadores: Cruzando el río con el bote.

¿Cuántas restricciones tenemos en este problema? ¿Cuáles son esas restricciones?Capacidad máxima del bote es de dos personas, y el número de indios no puede ser mayor al de los mestizos porque se lo comerían.

¿Cómo podemos describir el estado?(M, M, C, C, b ::) – (C, C, M, M, b ::)

¿Qué posibilidades o alternativas existen para cruzar el río con el operador  tomando en cuenta la restricción de la capacidad del bote?

A1: Bote con dos indios.A2: Bote con dos mestizos.A3: Bote con un indio y un mestizo.A4: Bote con un indio.A5: Bote con un mestizo.

¿Qué estados aparecen después de ejecutar la primera acción actuando con las cinco alternativas del operador?  Dibuja el diagrama resultante de aplicar todas las alternativas del operador al estado inicial.

(M, M :: C, C, b)(M, M, C, b:: C)(C :: C, M, M, b)(C, M, b:: C, M)(:: M, M, C, C, b)

¿Qué ocurre con la alternativa de que un mestizo tome el bote y cruce el río? No es posible, porque no hay quien retorne el bote de regreso.

Construye el diagrama después de las sucesivas aplicaciones del operador. ¿Cómo queda el diagrama?

Respuesta:

Primer viaje: Los dos indios cruzan el río, uno de ellos se queda al otro lado, y uno regresa.Segundo viaje: El indio de regreso se queda y cruzan los dos mestizos, uno de ellos se queda y el otro regresa.

Tercer viaje: Un mestizo y un indio cruzan juntos en el bote y se encuentran con el otro mestizo y  el indio.     

Cierre:

¿Qué estudiamos en esta lección?

Problemas dinámicos, estrategia medios-fines.

¿Por qué es importante la estrategia de medios-fines?

Nos ayuda a resolver problemas muchos más complejos y nos ayuda a comprender mejor la situación del problema.

¿Qué elementos intervienen en la solución de un problema con la estrategia medio-fines?

Esta con los elementos estado inicial, estado final y estados intermedios.

LECCION 11 PROBLEMAS DE TANTEO SISTEMÁTICO POR ACOTACIÓN DE ERROR.

ESTRATEGIA DE TANTEO   SISTEMÁTICO   POR   ACOTACIÓN   DEL ERROR

El tanteo sistemático por acotación del error consiste en definir el rango de todas las soluciones tentativas del problema, evaluamos los extremos del rango para verificar que la respuesta está en él, y luego vamos explorando soluciones tentativas en el rango hasta encontrar una que no tenga desviación respecto a los requerimientos expresados en el enunciado del problema. Esta solución tentativa es la respuesta buscada.

Ejemplo: En una máquina de venta de golosinas 12 niños compraron caramelos y chocolates. Todos los niños compraron solamente una golosina. Los caramelos valen $2 y los chocolates $4. ¿Cuántos caramelos y cuántos chocolates compraron los niños si gastaron entre todos $40?

¿Cuál es el primer paso para resolver el problema?

Leer paso a paso el problema e ir entendiéndolo.

¿Qué tipo de datos se dan en el problema?

De 12 niños que quieren comprar chocolates y caramelos en el cual gastan 40 Um.

¿Qué se pide?

¿Cuántos caramelos y cuántos chocolates compraron los niños si gastaron entre todos $40?

¿Cuáles podrían ser las posibles soluciones? Haz una tabla con los valores.

¿Cuál es la respuesta?En total los niños compraron 4 caramelos y 8 chocolates.

CARAMELOS 1 2 3 4 5 6 7 8 9 10 11CHOCOLATES

11 10 9 8 7 6 5 4 3 2 1

VALOR TOTAL 46 42

40 34 26

ESTRATEGIA BINARIA PARA EL TANTEO SISTEMÁTICO

El método seguido para encontrar cuál de las solucione tentativas es la respuesta correcta se llama estrategia binaria. Para poder aplicar esta esta estrategia hacemos  lo siguiente:

Ordenamos el conjunto de soluciones tentativas de acuerdo a un criterio. Por ejemplo, el número de chocolates y caramelos.

Luego le aplicamos el criterio de validación (el costo de las golosinas) a los valores extremos para verificar si es uno de ellos la respuesta, o que la respuesta es una de las soluciones intermedias.

Continuamos identificando el punto intermedio que divide el rango de dos porciones y le aplicamos la validación a dicho punto. Si esa no es la solución, entonces podemos identificar en que porción del rango esta la respuesta. Como resultado de este paso terminamos con un nuevo rango que tiene la mitad de soluciones tentativas que tiene el rango original.

Repetimos el paso anterior comenzando por identificar el nuevo punto intermedio que divide el nuevo rango en dos posiciones y repetimos la validación en ese punto. Si no hemos acertado la respuesta, terminamos con otro nuevo rango que tiene la cuarta parte de las soluciones tentativas que tiene el rango del inicio del problema.

Repetimos esto hasta encontrar la respuesta al problema. Este método es muy efectivo para descartar soluciones tentativas incorrectas. El número de evaluaciones necesarias con este método es como sigue:

Numero de solucionestentativas

2 4 8 16 32 64   128 256 1024

Numero de evaluacionesPara obtener la respuesta

1 2 3 4 5 6 7 8 10

EJEMPLO: Colocamos signos + y x entre los números indicados para que la igualdad será correcta. Dale prioridad a la operación de multiplicar y luego suma todos los términos al final.

a)      3  5  4  6   2 = 31               3+5+4+6+2=27                               3+5+4 x 6+2=34                                  3+5 x 4+6+2=31                            3 x 5+4+6+2=24

b)      8  2  5=21                  8+2+5=15                                  8 x 2+5=21

c)       7  5  2  6=47                                  7+5 x 2 x 6=67                                  7 x 5+2 x 6=47

d)      9  4  6  2=35                                  9+ (4+6)+2=35                               9+4+6+2=21

e)      4   2   3   7   5=34                 4 x 2+3 x 7+5=34                                4+2+3+7+5=21