INFORMATICA – C.B.I. (Ciclo Básico de Ingeniería) - 2015 Grupo II – Dictado: Ing. Juan Manuel Conti.
Resolución de problemas. Definición: Una persona tiene un problema cuando se enfrenta con alcanzar una meta que no es capaz de lograr trivialmente. Ejemplos de problemas son: El deseo de arreglar un automóvil descompuesto. El deseo de vencer a un contrincante al ajedrez. El deseo de diseñar un edificio. El deseo de curarse de una afección. El deseo de comunicar el resultado de una investigación. El deseo de ser feliz. El deseo de llegar a tener cierto bienestar. El deseo de ser exitoso. En términos sencillos un problema es una cuestión que se trata de aclarar. Dicha cuestión puede pertenecer a hechos triviales del mundo cotidiano o a eventos concretos del mundo científico o técnico, pero en definitiva existe un interrogante y una o varias posibles respuestas. Sin embargo no sólo es importante resolver un problema, sino también reconocer cuando existe un problema. En el mundo cotidiano resulta más difícil detectar un problema que resolverlo. Por ejemplo un alumno observa que sus calificaciones son bajas, pero no reconoce cómo mejorarlas. En el mundo cotidiano los problemas se hallan mal estructurados. Los problemas bien estructurados son aquellos cuyos pasos que conducen a la solución se pueden establecer en forma explícita y evidente. Por ejemplo, conociendo la Ley de Ohm determinar las corrientes en el siguiente circuito:
+ E
R1 I1
R2 I2
-
En los problemas mal estructurados es difícil establecer los pasos necesarios para arribar a una solución. En el mundo cotidiano los problemas no indican en forma clara el tipo de información necesaria para abordarlos, ni el sitio en el cual debe buscarse la información. En el mundo cotidiano las soluciones a los problemas dependen del contexto y están atravesadas por numerosas variables que pueden condicionar sus posibles soluciones. Los ejemplos clásicos de problemas utilizados en la enseñanza, llevan normalmente a una descontextualización.
Resolución de problemas y noción de Algoritmo
Pág. 1/18
INFORMATICA – C.B.I. (Ciclo Básico de Ingeniería) - 2015 Grupo II – Dictado: Ing. Juan Manuel Conti. En el mundo cotidiano los problemas dependen tanto del conocimiento oficial como del conocimiento extraoficial. En el mundo cotidiano la resolución de problemas importantes generan consecuencias significativas. Por ejemplo resolver un problema puede ser la diferencia entre una vida feliz o una vida infeliz. La estrategia de resolución de problemas es mucho más rica que la aplicación mecánica de un algoritmo, pues implica crear un contexto donde los datos guarden una cierta coherencia:
Ver qué datos son prioritarios. Rechazar los elementos distorsionantes. Escoger las operaciones que los relacionan. Estimar el rango de la respuesta, etc.
Un hecho destacable es que la Matemática es común en los ciclos de estudio de todo el mundo en todos los niveles. ¿Por qué? Porque constituye un idioma poderoso, conciso y sin ambigüedades. El objetivo fundamental de la Matemática no debería ser otro que el de la resolución de problemas y a lo largo de esta segunda parte del curso nos valdremos de muchos eventos matemáticos para desarrollar algoritmos. Elemento básico para resolver problemas: SABER RAZONAR, SABER ELABORAR. Razonar significa utilizar la razón o intelecto para relacionar los datos y arribar a una explicación o solución de un problema. Esto suele ser un mecanismo abstracto y normalmente tenemos muchas fallas de razonamiento debido a que nos condicionamos con facilidad. La mejor manera de combatir esta falla es resolver acertijos, de los cuales en Internet existen muchos, o bien revistas y libros especializados. Un caso característico de condicionamiento o pensamiento lateral, es el siguiente enunciado:
“Apagó la luz y se puso a leer” El primero pensamiento que se nos ocurre es: “Si la luz estaba encendida es porque era de noche o era un lugar muy oscuro, y si la apaga no podrá ver nada y por lo tanto no podrá leer”. ¿Y si era ciego? No, ¿sino cómo sabría que la luz estaba encendida? Por lo tanto no era ciego... ¿Entonces?... Bueno, tan sencillo como que estaba leyendo de noche, amaneció y ya no fue necesaria la luz.
Ejemplos de razonamientos peligrosos: Dos bomberos entran en un bosque a apagar un pequeño incendio. Al final, cuando salen y van a la orilla de un riachuelo, uno de ellos tiene la cara llena de ceniza y el otro está inmaculadamente limpio. ¿Cuál de los dos se lavará la cara? En el acto responderíamos: “¡obviamente el que tiene la cara tiznada!”. ¡¡ Error !!
Resolución de problemas y noción de Algoritmo
Pág. 2/18
INFORMATICA – C.B.I. (Ciclo Básico de Ingeniería) - 2015 Grupo II – Dictado: Ing. Juan Manuel Conti. Solución: El que tiene la cara sucia verá al otro y pensará que está igual a él (con la cara limpia). Y viceversa: el que tiene la cara limpia verá que su compañero está lleno de hollín por todas partes y se dirá a sí mismo: “yo también debo estar sucio, tengo que lavarme”. Ejemplo extraído del libro “El hombre que calculaba” de Malva Tahan”: - ¿Traéis algo de comer? Me estoy muriendo de hambre... - Me quedan tres panes – respondí. - Yo llevo cinco – dijo a mi lado el Hombre que Calculaba. - Pues bien – sugirió el Jeque – Yo os ruego que juntemos esos panes y hagamos un reparte equitativo. Cuando llegue a Bagdag prometo pagar con ocho monedas de oro el pan que coma. Así lo hicimos. Al día siguiente, al caer la tarde, entramos en la célebre ciudad de Bagdag, perla del Oriente. ................................... - Os dejo, amigos míos. Quiero, sin embargo, repetiros mi agradecimiento por el auxilio que me habéis prestado. Y para cumplir la palabra dada, os pagaré lo que tan generosamente dísteis. Y dirigiéndose al Hombre que Calculaba le dijo: - Recibirás cinco monedas por los cinco panes. Y dirigiéndose a mí añadió: - Y tú, Oh Bagdalí! recibirás tres monedas por los tres panes. Más con gran sorpresa mía, el calculador objetó respetuoso: - Perdón, oh Jeque! La división, hecha de ese modo, puede ser muy sencilla, pero no es matemáticamente cierta. Si yo entregué 5 panes he de recibir 7 monedas. Mi compañero bagdagí que dio 3 panes, debe recibir una sola moneda. - Por el Gran Mahoma! – intervino el gran Visir interesado vivamente en el caso ¿Cómo va a justificar este extranjero tan disparatado reparto? El Hombre que Calculaba se acercó al prestigioso ministro y habló así: - Voy a demostraros ¡Oh, Visir! que la división de las 8 monedas por mí propuesta es matemáticamente cierta. Cuando durante el viaje teníamos hambre, yo sacaba un pan, lo dividía en 3 pedazos, y cada uno de nosotros comía uno. Si yo aporté 5 panes, aporté por consiguiente 15 pedazos ¿No es verdad? Si mi compañero aportó 3 panes, contribuyó con 9 pedazos. Hubo así un total de 24 pedazos, correspondiendo por tanto 8 pedazos cada uno. De los 15 que aporté comí 8, luego di en realidad 7. Mi compañero aportó, como dije, 9 pedazos y comió también 8: luego dio sólo 1. Los 7 que yo di y el restante que contribuyó el bagdalí formaron los 8 que correspondieron al Jeque, luego es justo que yo reciba 7 monedas mi compañero sólo una. El gran Visir, luego de hacer los mayores elogios del Hombre que Calculaba, ordenó que le fueran entregadas las 7 monedas, pues por derecho, a mí sólo me correspondía una. Sin embargo, si bien el reparto resultó equitativo, no debió satisfacer plenamente a Beremitz, pues éste dirigiéndose al sorprendido ministro, añadió: - Esta división que yo he propuesto es, como demostré ya, matemáticamente clara, pero no perfecta a los ojos de Dios. Y juntando las monedas nuevamente las dividió en dos partes iguales. Una me la dio a mí, cuatro monedas, y se quedó con la otra.
Resolución de problemas y noción de Algoritmo
Pág. 3/18
INFORMATICA – C.B.I. (Ciclo Básico de Ingeniería) - 2015 Grupo II – Dictado: Ing. Juan Manuel Conti. Resolución de problemas: Es la exhibición de cualquier conducta que traiga como resultado acercarse a la satisfacción de deseos del tipo explicado, que casi no parecen ser logrables cuando ellos aparecen. En general todo ser vivo está enfrentando como destino insoslayable el de ser un resolvedor de problemas (con buen éxito o nó). Es una característica del ser viviente. Sin embargo nuestro objetivo es hallar alguna metodología básica para desarrollar caminos lógicos que permitan resolver un problema. Para la resolución de un problema deben considerarse 4 etapas:
a) Formulación o enunciación del problema. La misma debe ser correcta, completa y sin ambigüedades. Esto parece obvio, pero no lo es. La mayoría de las veces se requiere de aclaraciones adicionales por imprecisiones en las que no pensamos. Imaginemos un ejemplo sencillo: “Determinar mediante la serie de Taylor vista en clase, el seno de los ángulos comprendidos entre 0 y 90 grados”. Nos parece un buen enunciado, sin embargo en el acto surgen dos preguntas: ¿Con cuántos decimales determinamos el seno? (con 2, con 3, etc. lo cual fijaría el número de términos que poseerá nuestra Serie) ¿Qué paso le damos a la tabla? Podemos tomar de 5 en 5 grados, ó de 1 en 1, etc.
b) Elección de un método o procedimiento. Si un problema puede ser resuelto de varias maneras diferentes y no se especifica nada al respecto, la elección puede ser tan simple como “elijo el método A porque es el que mejor conozco”, o si conozco todos los métodos puedo elegir “el método B porque es al más eficiente y compacto”, o “el método C porque es el más general y adaptable a cualquier variante del problema”. Lo importante es que, por una razón u otra, terminamos adoptando un camino de resolución.
c) Codificación. Consiste en expresar el método elegido de manera que pueda ser interpretado por el procesador que vaya a utilizarse, interpretándose como “procesador” ya sea a una persona, un dispositivo electrónico, mecánico, etc.
d) Ejecución. Poner en práctica el método o procedimiento elegido y obtener la solución del problema.
Resolución de problemas y noción de Algoritmo
Pág. 4/18
INFORMATICA – C.B.I. (Ciclo Básico de Ingeniería) - 2015 Grupo II – Dictado: Ing. Juan Manuel Conti.
Procesador, Ambiente y Acción. Consideremos los siguientes enunciados:
Extraer la raíz cuadrada de un conjunto de números. Decorar una habitación. Construir una valla.
Cada uno de ellos implica una tarea o trabajo a realizar. Llamaremos PROCESADOR a toda entidad capaz de comprender un enunciado y ejecutar el trabajo indicado en él. El procesador que realizará la tarea (por ejemplo una persona) debe contar con el conocimiento y los recursos necesarios: herramientas, materiales, etc. Entonces: El conjunto de todos los recursos necesarios para la ejecución de un trabajo constituye el ambiente de ese trabajo. En el caso de construir una valla, el ambiente de trabajo puede estar constituido por: o o o o o o o
Postes. Alambre. Palas. Picos. Martillos. Tenazas. etc.
y lo más obvio: el conocimiento y experiencia para llevarlo a cabo. En el caso de calcular la raíz cuadrada seguramente se requerirá de:
Papel para registrar los números. Una calculadora. Un elemento de escritura para hacer las anotaciones. etc.
Sin embargo cualquiera sea el ambiente descripto, la ejecución de un trabajo no suele ser inmediata y comprende un conjunto de pasos hasta llegar al objetivo propuesto. En el caso de la valla: 1. 2. 3. 4.
Decidir distancia entre postes. Cavar agujeros para los mismos. Colocar los postes y pisonar fuertemente. Colocar el alambre.
Cada una de estas tareas implica una ACCION que podemos definir como un evento que modifica el ambiente. Además estamos suponiendo que el PROCESADOR INTERPRETA cada una de las acciones descriptas. Si el encargado de construir la cerca es un operario calificado, con sólo indicarle: construya la cerca, será suficiente. Él determinará en base a la magnitud del trabajo: la cantidad de postes, el tamaño y calidad de los mismos, el tipo de alambre, etc. Pero ¿y si no lo es? ¿Si se trata de alguien que normalmente hace otro tipo de tareas? Podríamos intentar una descripción más detallada como la indica-
Resolución de problemas y noción de Algoritmo
Pág. 5/18
INFORMATICA – C.B.I. (Ciclo Básico de Ingeniería) - 2015 Grupo II – Dictado: Ing. Juan Manuel Conti. da en la lista anterior donde hemos desmenuzado la tarea: construya una valla, en otras subtareas menores que sí puedan ser comprendidas. Si esquematizamos lo dicho hasta aquí podemos pensar que una ACCIÓN modifica el ambiente desde un estado inicial Ei hasta un estado final Ef: Ei
Distancia entre postes
Ei
Construir una valla
Cavar agujeros
Colocar postes
Ef
Colocar alambres
Ef Aún las subtareas de la derecha pueden no ser todavía comprendidas del todo y requieran un desdoblamiento mayor. Podríamos hacer nuevas subdivisiones de menor complejidad hasta llegar a un conjunto de enunciados que ya no requieran mayores explicaciones. Esto nos lleva al concepto de ACCIÓN PRIMITIVA:
Para un procesador dado, una acción es PRIMITIVA si su sólo enunciado es suficiente para que pueda ser ejecutada sin necesidad de información adicional. Una ACCIÓN NO- PRIMITIVA puede ser descompuesta en acciones PRIMITIVAS a través de un método denominado de REFINAMIENTOS SUCESIVOS (top-down)
Dado un trabajo T por medio de un enunciado NO-PRIMITIVO, tal que transforme el ambiente desde un estado inicial Ei en un estado final Ef, se puede encontrar una descomposición t1, t2, …., tn, que constituyan una secuencia de enunciados PRIMITIVOS que ejecuten el trabajo T. Ya estamos en condiciones de enunciar el significado de algoritmo:
Un algoritmo es una secuencia ordenada de acciones primitivas que puedan ser ejecutadas por un procesador dado y que lleve a la solución de un problema. Si bien la notación de los algoritmos puede ser enteramente personal, existe un conjunto de estructuras ya normalizadas para las acciones, y las mismas pueden englobarse dentro de los siguientes rubros:
Acciones simples. Acciones condicionales. Acciones repetitivas.
Resolución de problemas y noción de Algoritmo
Pág. 6/18
INFORMATICA – C.B.I. (Ciclo Básico de Ingeniería) - 2015 Grupo II – Dictado: Ing. Juan Manuel Conti. A los fines prácticos, utilizaremos en la notación de nuestras estructuras la forma normalizada en castellano:
Variable valor Constante valor;
Acciones simples. Una acción simple puede ser:
Asignar valores a variables y constantes. Aplicar una fórmula o expresión aritmética.
Por ejemplo:
D 10 PI 3.1415 Perímetro PI * D Son 3 acciones simples (no involucran repeticiones, condiciones, ni a otras acciones).
Acciones repetitivas: Implican tareas en las cuales un cierto número de acciones debe repetirse hasta completar una tarea. Imaginemos por ejemplo que tenemos 15 sillas dentro de un salón y debemos sacarlas de una en una y llevarlas hasta el patio del fondo. Conocemos de antemano el número de repeticiones que debemos realizar: 15
Para Cuenta 1 hasta 15 hacer comenzar Ir al salon; Tomar una silla; Transportarla hasta el patio del fondo; finalizar Cuando un conjunto de instrucciones formen parte de una estructura, englobaremos las mismas entre las palabras comenzar – finalizar a las cuales llamaremos DELIMITADORES. Estos delimitadores establecen el “bloque” de acciones que se repetirá y que se hallan gobernadas (en este caso) por la estructura “For”. El contador (Cuenta) se incrementa automáticamente de 1 en 1. El punto y coma (;) al final de cada tarea se denomina finalizador e indica que allí termina el enunciado descriptor de la acción. Es una cuestión sintáctica bastante sencilla y fácil de familiarizarse. Nótese que en la escritura del algoritmo anterior hemos hecho abundante uso de sangrías a fin de visualizar con toda claridad el orden de jerarquías: donde comienza y donde finaliza cada parte del algoritmo y cuáles acciones dependen de cada estructura de control.
Resolución de problemas y noción de Algoritmo
Pág. 7/18
INFORMATICA – C.B.I. (Ciclo Básico de Ingeniería) - 2015 Grupo II – Dictado: Ing. Juan Manuel Conti.
La estructura Repetir – Hasta (condición). Ahora imaginemos el mismo problema anterior, pero en lugar de 15 sillas existe una cantidad no establecida y difícil de contar. No sabemos si debemos repetir 15, 20 ó 100 veces el proceso de tomar una silla y llevarla al patio del fondo. En este caso hacemos uso de:
Repetir Ir al salón. Tomar una silla. Transportarla hasta el patio del fondo. Hasta que (no quede ninguna silla) Lo cual es equivalente a tomar una silla, llevarla al patio y luego preguntar: ¿se acabaron las sillas? Si la respuesta es NO, repita el proceso y así sucesivamente hasta que no quede ninguna. Obviamente el lazo se repite por la condición negada. Otro detalle destacable es que la estructura Repetir – Hasta que, no requiere de delimitadores de bloque: estas palabras en sí ya lo son. Si bien esta estructura puede utilizarse en cualquier tipo de repeticiones, normalmente se la emplea cuando el bloque de acciones DEBE EJECUTARSE AL MENOS UNA VEZ, puesto que la evaluación de finalización de las repeticiones se lleva a cabo AL FINAL de la estructura.
La estructura Mientras (condición) hacer. Continuamos con nuestro caballito de batalla: las sillas.
Mientras (queden sillas) hacer comenzar (comenzar bloque de acciones) Ir al salón. Tomar una silla. Transportarla hasta el patio del fondo. finalizar; (finalizar bloque de acciones) Mientras queden aún sillas, hacer lo siguiente (las acciones entre los delimitadores comenzar – finalizar). Los elementos destacables de esta estructura son:
La condición de finalización de repeticiones se evalúa al comienzo del bloque. Las repeticiones se realizan por condición verdadera. El bloque de acciones puede no ejecutarse nunca si la condición de entrada falla.
Algunos ejemplos:
Ejemplo 01: “Sumar números enteros consecutivos hasta que la suma sea mayor que 200”. En toda tarea nos planteamos de entrada: ¿qué recursos necesitamos?
Resolución de problemas y noción de Algoritmo
Pág. 8/18
INFORMATICA – C.B.I. (Ciclo Básico de Ingeniería) - 2015 Grupo II – Dictado: Ing. Juan Manuel Conti. En este caso: Un acumulador de Sumas (entero). Un indicador incremental para los sumandos individuales (entero).
Solución I: Algoritmo: Suma de enteros consecutivos. COMENZAR ALGORITMO Elementos necesarios: Suma, N : enteros; Suma 0; N 1; repetir Suma Suma+N; N N+1; hasta que (Suma>200); Mostrar valor de Suma. FINALIZAR ALGORITMO. Solución II: Algoritmo: Suma de enteros consecutivos. COMENZAR ALGORITMO Suma 0; N 1; Mientras(Suma