UNIDAD 5
SOLUCIÓN DE BÚSQUEDA EXHAUSTIVA
SOLUCIÓN DE BÚSQUEDA EXHAUSTIVA
JUSTIFICACIÓN
La búsqueda exhaustiva es una estrategia que se
utiliza para resolver problemas en los cuales no es posible hacer una
representación a partir de su enunciado. En este tipo de problemas generalmente
se identifica características de la solución, y en base a estas características
se procede en proceso de búsqueda sistemática de una respuesta.
El proceso que sugiere en esta estrategia es una
búsqueda ordenada o disciplina, que nos permite evitar la prueba al azar con
los consiguientes resultados negativos y a veces frustrantes.
Existen dos caminos para manejar esta búsqueda
sistemática y ordenada de una respuesta. La primera es generando respuestas
tentativas a las cuales sometemos a un proceso de verificación para validar
cuales son la solución o soluciones reales; la segunda es construyendo paso a
paso una respuesta que cumpla con las características planteadas en el
enunciado del problema.
A la primera alternativa se le denomina “tanteo sistemático por acotación del error”,
o simplemente “acotación del error”
por estar implícito en el tanteo al generar soluciones tentativas. Este esquema
tiene dos momentos, el primero, con la construcción de una tabla de soluciones
tentativas, y el segundo momento con la validación para determinar cuáles de
ellas son realmente soluciones. El tanteo sistemático consiste en definir
ordenadamente el conjunto de todas las soluciones tentativas del problema. Para
la selección de la respuesta es importante seguir una estrategia apropiada que
nos ayude a manejar los números generalmente elevados de soluciones tentativas
hasta encontrar la que se ajusta a los requerimientos del problema, que es la
que llamamos respuesta definitiva o real.
La segunda alternativa se le denomina “búsqueda exhaustiva por construcción de
soluciones”, o simplemente “construcción
de soluciones”. Este esquema depende de las características de la solución
que plantea el enunciado. Cada problema tendrá un esquema de construcción
particular para él.
De acuerdo a lo dicho, la estrategia general
“búsqueda exhaustiva”, se aplica a través de dos estrategias particulares
descritas en el párrafo anterior.
OBJETIVOS
A través de la unidad se pretende que sean capaces
de:
1
Aplicar las estrategias de
búsqueda exhaustiva en la resolución de problemas.
2
Reconocer los tipos de problemas que admiten
el uso de esta estrategia.
3
Comprender la utilidad de la
estrategia que nos ocupa.
LECCIÓN 1
PROBLEMAS DE TANTEO SISTEMÁTICO POR ACOTACIÓN DEL ERROR
Practica
1: En un corral un grajero tiene cerdos y patos. Un
niño la pregunta ¿Cuántos animales tiene de cada uno?. El granjero, que le
gusta jugar bromas, le contesta: “son 20 animales entre cerdos y patos, por lo
menos hay 4 cerdos y 4 patos, el número total de patas es de 56”. ¿Cómo puede
el niño averiguar el número de animales de cada tipo?.
SOLUCION:
¿Cuál es el primer paso para resolver el problema?
Reconocer las variables
¿Qué tipos de datos se dan en el problema?
El número total de animales y el número de patas
¿Qué se pide?
Encontrar el número de cerdos y patos que tiene.
¿Cuáles podrían ser las posibles soluciones?
Realizarlo mediante una tabla
Respuesta:
8 cerdos y 12 patos
¿Qué estrategia aplicamos en esta práctica?
Tanteo sistemático por acotación de error.
ESTRATEGIA
DEL 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. Esa solución tentativa es la respuesta buscada.
Practica
2: esta estrategia consiste en un juego. Seleccionar
dos alumnos. Uno piensa un número entre
1 y 128 ambos incluidos que lo va a escribir en un papel que mantiene guardado,
el otro alumno debe adivinar el número, para esto deberá hacer preguntas cuya
respuesta sea un “si” o “no”. Anota el número de preguntas que hizo cada uno de
los alumnos que adivinaba el número. Discutir los resultados.
Si la persona responde en menos de 7 preguntas hay
dos alternativas, o el número es muy “fácil” o la persona tiene mucha suerte
adivinando.
Si la persona gasto 8 o más preguntas es que no
aplico correctamente la estrategia binaria.
Practica
3: colocar los dígitos del 1 al 9 en los cuadritos
del grafico de manera que sumando de forma vertical, horizontal y diagonal nos
de 15.
SOLUCIÓN:
¿Cuáles son las posibles ternas?
1 5 9
2 6 7
1 6 8
3 4 8
2 5 8
3 5 7
2 4 9
4 5 6
¿Cuáles son grupos de tres ternas sirven para
construir la solución?
1 5 9
1 6 8
2 6 7
2 4 9
3 4 8
3 5 7
¿Cómo quedan las figuras?
Practica
4: Coloca los dígitos del 1 al 9 en los cuadros de
la figura de abajo, de forma tal que cada una de las cuatro direcciones
indicadas sumen 13.
SOLUCIÓN:
¿Cuáles son las posibles ternas?
1 3 9
2 4 7
1 4 8 2 5 6
1 5 7
3 4 6
2 3 8
Practica 5: Identifica los valores de
números enteros que corresponden a las letras O, S y U para que la operación
indicada sea correctamente. Cada letra solo puede tomar un único valor.
O
|
S
|
O
|
+
|
U
|
S
|
O
|
|
S
|
U
|
U
|
El enunciado solo nos plantea que reemplazamos las
letras por números para que la operación sea correcta. El resto de la
información tiene que salir de la respuesta.
En primer término observamos que tenemos S+S=U y
O+O=U. ¿es posible que dos números diferentes den el número?. Hagamos la tabla
que sigue para ayudarnos.
Vemos que el 1+1 da 2, pero 6+6 da 12. Coloco el 2
y llevo el 1. De esta forma S y O pueden ser los pares (0 y 5), (1 y 6), (2 y
7), (3 y 8) y (4 y 9). Noten que en los pares el primer número está entre 0 y 4
y el segundo entre 5 y 9. Las sumas de los números del 5 y 9 consigo mismo
llevan 1 a la columna de la izquierda. Esto nos obliga a que el número a
colocar en la primera columna de la derecha debe ser el número menor del par.
Si colocamos el mayor llevaríamos un 1 adicional para la suma de la segunda
columna, con lo cual las sumas de las columnas no tendrían el mismo resultado.
También se desprende de la operación indicada en el enunciado que U debe ser un
número par.
Entonces, O es un número entre 0 y 4. Con esa
información podemos encontrar los valores correspondientes a la U. El valor
cero hay que descartarlo porque cero más cero en la primera columna debería dar
cero también y vemos en la suma del enunciado que la suma de la primera columna
es un número diferente al de los términos de la suma.
Luego que
tenemos los posibles valores de O y U, podemos determinar los valores
correspondientes para la S.
Finalmente podemos calcular el resultado de sumar O
con U y el 1 que llevamos de la segunda columna a la tercera columna.
A partir de esta última tabla podemos eliminar los valores
de 3 y 4 para la O porque la suma tiene un valor superior a 9 y eso obligará a
tener un cuarto digito que no es el caso a partir del enunciado. También
debemos hacer notar que debe cumplirse que O + U + 1 debe ser igual a S. Eso
solo se da para el valor de 2 para O. Por lo tanto podemos descartar loas
valores 1, 3 y 4 de la O en la tabla.
Reemplazando los valores en la operación para
verificar la respuesta nos da:
2
|
7
|
2
|
+
|
4
|
7
|
2
|
|
7
|
4
|
4
|
Esta es una operación matemática correcta. Por lo
tanto es la respuesta al ejercicio.
No hay comentarios:
Publicar un comentario