Pensamiento algorítmico - LF4.pdf

Unidad 2 / Escenario 4 Lectura Fundamental Modelado y especificación de problemas Contenido 1 Breve repaso de problemas 2 ¿Por qué es útil modelar y especificar un problema? 3 ¿Cómo se modela y especifica un problema? Palabras clave: En...

Unidad 2 / Escenario 4 Lectura Fundamental Modelado y especificación de problemas Contenido 1 Breve repaso de problemas 2 ¿Por qué es útil modelar y especificar un problema? 3 ¿Cómo se modela y especifica un problema? Palabras clave: Entrada, salida, precondición, postcondición. 1. Breve repaso de problemas ¿Qué conozco? PROCESADOR ¿Qué quiero saber? Entradas Salidas ALGORITMO Datos Información Figura 1. Diagrama representativo de un problema Fuente: elaboración propia En la figura 1 se pueden apreciar algunos de los conceptos estudiados en el Escenario 1 del módulo de Pensamiento Algorítmico. Debe recordarse que, en el presente módulo un problema se define por medio de dos preguntas: ¿Qué conozco? (entradas/datos) ¿Qué quiero saber? (salidas/información) Posteriormente, dos tipos de problemas fueron introducidos: Específico, cuando todos los datos utilizados para plantear el problema son constantes. General, cuando al menos un dato de los utilizados para plantear el problema es variable. Por otro lado, algoritmo se definió como un conjunto ordenado y finito de operaciones que permite hallar la solución de un problema. Finalmente, se dijo que el procesador es la herramienta o entidad que almacena y ejecuta el algoritmo. 2. ¿Por qué es útil modelar y especificar un problema? Modelar y especificar un problema es lo que da sentido a la solución del mismo (Joyanes, Fundamentos de programación : Algoritmos y estructura de datos, 1996). Si no se conoce el problema, es decir, cuál es el punto de partida y cuál es el punto de llegada es prácticamente imposible solucionarlo. En otras palabras, modelar y especificar un problema es identificar el objetivo del trabajo que se está desarrollando. POLITÉCNICO GRANCOLOMBIANO 2 Si la primera tarea acometida, por parte de la persona encargada de solucionar un problema, no es modelar y especificar, él o ella estará haciendo las cosas “al revés” y perderá mucho tiempo hasta que entienda qué busca y con qué cuenta. Por otra parte, después de que se ha construido una probable solución, tener un modelo es indispensable para saber si el algoritmo que se construyó es correcto. Esto último se logra comprobando que un conjunto de entradas se transformó en un conjunto de salidas que cumple con las condiciones especificadas. 3. ¿Cómo se modela y especifica un problema? Para modelar y especificar un problema debe seguirse seis pasos que pueden ser resumidos en términos de resolver algunas preguntas. Dichos pasos se presentan en la figura 2. ¿ Cuál información es relevante? ¿Cuál información es irrelevante? A ¿Cuál información es solicitada? ¿ Es suficiente la información proporcionada para resolver el B problema? Si no, ¿ qué hace falta saber? C ¿ Cuántas entradas tiene el problema? ¿ Cuáles son (nombre y descripción)? ¿ A qué tipo de dato corresponde cada una? ¿Cuántas salidas tiene el problema? ¿Cuáles son (nombre y D descripción)? ¿A qué tipo de dato corresponde cada una? E ¿Cuáles son las condiciones que deben cumplir las entradas? F ¿Cuáles son las condiciones que deben cumplir las salidas? Figura 2. Pasos para modelar y especificar un problema. Fuente: elaboración propia POLITÉCNICO GRANCOLOMBIANO 3 Los pasos son claros y especifican las preguntas que deberían hacerse; sin embargo, vale la pena aclarar los tipos de información citados en el primer paso. Los datos relevantes son aquellos que permiten resolver el problema y pueden ser formulados matemáticamente. Los datos irrelevantes son los que no inciden en la solución matemática. Finalmente, la información requerida hace referencia a lo que se quiere averiguar, al resultado que se espera obtener después de implementar el algoritmo. ¿Sabía qué...? Las precondiciones son aquellas condiciones que deben ser satisfechas por las entradas de un problema y que las postcondiciones son aquellas condiciones que deben ser satisfechas por las salidas de un problema. Por eso, las preguntas de los literales e y f podrían ser reemplazadas respectivamente por ¿cuáles son las precondiciones del problema? y ¿cuáles son las postcondiciones del problema? Cómo mejorar... Muchas veces para visualizar e interpretar correctamente un problema es muy útil hacer esquemas o dibujos en una hoja de papel. Hágalo siempre que le parezca conveniente. Aunque pueda parecer obvio, es clave que nunca se olvide que la solución que se busca es algorítmica/matemática y por lo tanto el modelado que se haga debe estar en los mismos términos. Para ello, puede acudirse a la construcción de expresiones tal como se vio en el escenario anterior. A continuación, se presentan algunos ejemplos de cómo deben ejecutarse el proceso de modelado y especificación de un problema. POLITÉCNICO GRANCOLOMBIANO 4  3.1. Ejemplo 1 Pedro quiere construir un nuevo corral triangular para sus vacas. Para esto, él ha clavado tres postes, que serán los vértices del corral. Para saber cuánto alambre necesitará, Pedro se pone en la tarea de medir el perímetro del corral, sin embargo, descubre que su instrumento de medida solo le permite medir la distancia entre parejas de postes. Como Pedro es muy malo sumando, le ha pedido ayuda para, dadas las distancias entre parejas de postes, calcular el perímetro del corral. Se responderán entonces las preguntas de los literales a hasta f. A. ¿Cuál información es relevante? ¿Cuál información es irrelevante? ¿Cuál información es solicitada? Clasificar la información se puede hacer de muchas formas distintas. En este caso se resaltará el texto correspondiente a información relevante en verde, información solicitada en amarillo e información irrelevante en azul. Pedro quiere construir un nuevo corral triangular para sus vacas. Para esto, él ha clavado tres postes, que serán los vértices del corral. Para saber cuánto alambre necesitará, Pedro se pone en la tarea de medir el perímetro del corral, sin embargo, descubre que su instrumento de medida solo le permite medir la distancia entre parejas de postes. Como Pedro es muy malo sumando, le ha pedido ayuda para, dadas las distancias entre parejas de postes, calcular el perímetro del corral. B. ¿Es suficiente la información proporcionada para resolver el problema? Si no, ¿qué hace falta saber? La información proporcionada no es suficiente para resolver el problema. Hace falta saber cuál es la forma y las medidas de los postes. Para averiguarlo se debería ir a la fuente del problema o hacer supuestos (éstos deben ser buenos). Para este caso se supondrá que los postes son puntos, esto es imposible en la vida real, pero permitirá solucionar el problema matemático. C. ¿Cuántas entradas tiene el problema? ¿Cuáles son (nombre y descripción)? ¿A qué tipo de dato corresponde cada una? El problema tiene tres entradas: Lado A, distancia entre la primera pareja de postes. Lado A es un dato que pertenece a los números reales. Lado B, distancia entre la segunda pareja de postes. Lado B es un dato que pertenece a los números reales. Lado C, distancia entre la tercera pareja de postes. Lado C es un dato que pertenece a los números reales. POLITÉCNICO GRANCOLOMBIANO 5  D. ¿Cuántas salidas tiene el problema? ¿Cuáles son (nombre y descripción)? ¿A qué tipo de dato corresponde cada una? El problema tiene una salida: Perímetro, corresponde al perímetro del corral. Perímetro es un dato que pertenece a los números reales. E. ¿Cuáles son las condiciones que deben cumplir las entradas? Lado A, lado B y lado C deben ser números positivos ya que no existen distancias negativas. Adicionalmente, los tres lados deben formar efectivamente un triángulo y para ello deben cumplir la desigualdad triangular. Estas condiciones se pueden notar matemáticamente por medio de los siguientes predicados: Condiciones de no negatividad: lado A>0 ∧ lado B>0 ∧ lado C>0 Desigualdad triangular: lado A+lado B>lado C ∧ lado A+lado C>lado B ∧ lado B+lado C>lado A F. ¿Cuáles son las condiciones que deben cumplir las salidas? Perímetro debe corresponder a la suma de los tres lados del corral. Esta condición se puede notar matemáticamente así: Perímetro= lado A+lado B+lado C También, se puede expresar la postcondición de una forma más simple al decir que la salida perímetro representará el perímetro del corral. Es una manera trivial de expresarla, pero, es igualmente válida. Una vez se han resuelto los seis literales, tenemos finalmente el modelado y especificación del ejemplo 1. POLITÉCNICO GRANCOLOMBIANO 6  3.2. Ejemplo 2 En Colombia las personas alcanzan la mayoría de edad al cumplir 18 años. Dada la edad de Arnoldo, quien nació y vive en Colombia, establezca si él es mayor de edad o no. Se responderán entonces las preguntas de los literales a hasta f. A. ¿Cuál información es relevante? ¿Cuál información es irrelevante? ¿Cuál información es solicitada? Para este ejemplo se utilizará la misma nomenclatura del ejemplo pasado. En Colombia las personas alcanzan la mayoría de edad al cumplir 18 años. Dada la edad de Arnoldo, quien nació y vive en Colombia, establezca si él es mayor de edad o no. Note que en este caso se consideró que no había información irrelevante, esto es posible dado que un problema únicamente está conformado por la información que conozco y la quiero saber. B. ¿Es suficiente la información proporcionada para resolver el problema? Si no, ¿qué hace falta saber? La información dada sí es suficiente para resolver el problema. C. ¿Cuántas entradas tiene el problema? ¿Cuáles son (nombre y descripción)? ¿A qué tipo de dato corresponde cada una? El problema tiene una sola entrada: Edad, representa la edad, en años, que tiene Arnoldo. Edad es un dato que pertenece a los números naturales. ¿Sabía qué...? No se ha incluido como entrada los 18 años que marcan la mayoría de edad ¿por qué? Los datos constantes no se consideran entradas del problema (aunque estrictamente sí lo son), únicamente los datos variables se contarán como entradas. Por otro lado, el hecho de que Arnoldo sea nativo y residente de Colombia podría expresarse por medio de datos de tipo lógico, no obstante, como también serían datos constantes no los representamos. POLITÉCNICO GRANCOLOMBIANO 7  D. ¿Cuántas salidas tiene el problema? ¿Cuáles son (nombre y descripción)? ¿A qué tipo de dato corresponde cada una? El problema tiene una salida: Mayor, representa el hecho de que Arnoldo sea mayor de edad o no. Mayor es un dato de tipo lógico. E. ¿Cuáles son las condiciones que deben cumplir las entradas? Edad no debería cumplir ninguna condición. F. ¿Cuáles son las condiciones que deben cumplir las salidas? Mayor es el valor de verdad que establece si Arnoldo es mayor de edad o no. Esta condición se puede notar matemáticamente así: Mayor= edad≥18 De la misma manera que se hizo en el ejemplo anterior, se puede expresar la postcondición de una forma más simple al decir que la salida mayor representará el hecho de que Arnoldo sea mayor de edad. Nuevamente, es una forma trivial de expresarse, pero permite la validar la solución. 3.3. Ejemplo 3 Dos cocineros pelaron 400 papas. Juan peló tres papas por minuto y David dos por minuto. Sabiendo que era más lento, David decidió pelar papas 25 minutos más que Juan. ¿Cuánto tiempo trabajó cada uno? A. ¿Cuál información es relevante? ¿Cuál información es irrelevante? ¿Cuál información es solicitada? Para este caso se utilizará la misma nomenclatura del primer ejemplo. Dos cocineros pelaron 400 papas. Juan peló tres papas por minuto y David dos por minuto. Sabiendo que era más lento, David decidió pelar papas 25 minutos más que Juan. ¿Cuánto tiempo trabajó cada uno? El hecho de que David sea más lento no se modela matemáticamente y por eso se toma esa información como irrelevante; lo que sí se puede modelar por medio de matemáticas es su decisión de trabajar 25 minutos más que Juan. POLITÉCNICO GRANCOLOMBIANO 8  B. ¿Es suficiente la información proporcionada para resolver el problema? Si no, ¿qué hace falta saber? La información dada sí es suficiente para resolver el problema. C. ¿Cuántas entradas tiene el problema? ¿Cuáles son (nombre y descripción)? ¿A qué tipo de dato corresponde cada una? Ninguna entrada. Es muy importante notar que los datos de la cantidad total de papas peladas, la velocidad a la que pelan David y Juan y el tiempo que David que trabajó de más sí son entradas; sin embargo, por ser constantes en este módulo y en el subsiguiente (Programación de Computadores) no se considerarán de esa forma. De acuerdo con lo visto en el primer escenario de este módulo, se podría decir que este es un problema específico. Por otro lado, si esos mismos datos fueran dados en forma de variables, sí se considerarían entradas. D. ¿Cuántas salidas tiene el problema? ¿Cuáles son (nombre y descripción)? ¿A qué tipo de dato corresponde cada una? El problema tiene dos salidas: Tiempo_Juan, representa el tiempo que trabajó Juan. Tiempo_Juan es un número real. Tiempo_David, representa el tiempo que trabajó David. Tiempo_David es un número real. E. ¿Cuáles son las condiciones que deben cumplir las entradas? Como no hay entradas, no hay precondiciones. F. ¿Cuáles son las condiciones que deben cumplir las salidas? Tiempo_Juan y tiempo_David son los valores numéricos que representan cuanto tiempo, en minutos, trabajaron Juan y David. Estas condiciones se pueden notar matemáticamente por medio de las dos siguientes expresiones: 3*Tiempo_Juan + 2*Tiempo_David= 400 Tiempo_Juan + 25 =Tiempo_David Asi mismo, se puede expresar las mismas postcondiciones diciendo que Tiempo_Juan y Tiempo_David representan el tiempo que pasaron pelando papas Juan y David respectivamente. POLITÉCNICO GRANCOLOMBIANO 9  ¿Sabía qué...? Entre más complejo es un problema, es mucho más difícil escribir sus postcondiciones de manera matemática, por lo tanto, será suficiente expresar éstas por medio de palabras. Finalmente, cabe hacer una pregunta que no resulta trivial, ¿por qué no se ha considerado a las constantes como entradas del problema? Eso se debe simplemente al objetivo que persigue la enseñanza de este tópico en el módulo de Pensamiento Algorítmico: preparar al estudiante para que cuando resuelva problemas por medio de la programación de computadores pueda escribir funciones. Una función es una sección de código que toma un conjunto de parámetros (valores puramente variables) y mediante un algoritmo los transforma en una salida, es decir, una función representa un algoritmo. Este y otros conceptos serán ampliados en el módulo de Programación de Computadores. En síntesis... Modelar y especificar un problema es indispensable para solucionarlo. El proceso resulta sencillo si se sigue la metodología de seis pasos propuesta aquí. POLITÉCNICO GRANCOLOMBIANO 10 Referencias Joyanes, L. (1996). Fundamentos de programación : Algoritmos y estructura de datos (Segunda ed.). Madrid: McGraw-Hill. POLITÉCNICO GRANCOLOMBIANO 11  INFORMACIÓN TÉCNICA Módulo: Pensamiento Algorítmico Unidad 2: Expresiones y Problemas Algoritmicos Escenario 4: Modelado y especificación de problemas Autor: Javier Fernando Niño Velásquez Asesor Pedagógico: Jeiner Leandro Velandia Diseñador Gráfico: Felipe Puentes Asistente: Leidy Alejandra Morales Eslava Este material pertenece al Politécnico Grancolombiano. Por ende, es de uso exclusivo de las Instituciones adscritas a la Red Ilumno. Prohibida su reproducción total o parcial. POLITÉCNICO GRANCOLOMBIANO POLITÉCNICO GRANCOLOMBIANO 12