De manera matemática, un problema de cómputo se puede definir como el conjunto de instancias de entrada, al cual corresponde un conjunto de soluciones, junto con una relación que asocia, para cada instancia de entrada del problema, un subconjunto de soluciones (posiblemente vacío).
La ingeniería de software es la rama de la computación que se encarga de la metodología para resolver un problema. De acuerdo con el Institute of Electrical and Electronics Engineers (IEEE), la ingeniería de software se define como “La aplicación de un enfoque sistemático, disciplinado y cuantificable hacia el desarrollo, operación y mantenimiento del software", por lo que el uso y establecimiento de principios de ingeniería sólidos son aspectos básicos para obtener un software que sea económicamente fiable y funcione eficientemente.
La ingeniería de software brinda métodos que indican cómo generar software. Estos métodos abarcan una amplia gama de tareas:
Planeación y estimación del proyecto.
Análisis de requerimientos del sistema y software.
Diseño de la estructura de datos, la arquitectura del programa y el procedimiento algorítmico.
Codificación.
Pruebas y mantenimiento (validación y verificación).
Es por ello que en esta UAPA realizarás algoritmos a partir del análisis de un problema, identificando el número de datos (variables) y los tipos de datos (enteros, reales, caracteres, etc.) que debe recibir el algoritmo (conjunto de datos de entrada), así como el número de datos (variables) y los tipos de datos (enteros, reales, caracteres, etc.) que se deben regresar al algoritmo (conjunto de soluciones) para solucionar el problema. A partir de los datos de entrada se deben realizar ciertas acciones (operaciones) que permitan llegar a la solución del problema (datos de salida). En esta UAPA también generarás los pasos necesarios que describan cómo, a partir de los datos de entrada, se formarán los cálculos u operaciones necesarios para obtener los datos de salida (solución del problema).
La ISO (International Organization for Standarization), en su norma 12 207, define al ciclo de vida de un software como…
"Un marco de referencia que contiene las actividades y las tareas involucradas en el desarrollo, la explotación y el mantenimiento de un producto de software, abarcando desde la definición hasta la finalización de su uso”.
Ciclo de vida del software.
Dentro del ciclo de vida del software, la etapa de análisis busca comprender la necesidad, es decir, entender el problema.
El análisis es el proceso para averiguar qué es lo que requiere el usuario del sistema de software (análisis de requisitos). Esta etapa permite establecer las necesidades de forma clara y concisa (especificación de requisitos).
Por lo tanto, para conocer qué es lo que está solicitando el usuario es importante identificar dos grandes conjuntos dentro del sistema: el conjunto de entrada y el conjunto de salida.
El conjunto de entrada está compuesto por todos aquellos datos que pueden alimentar al sistema. El conjunto de salida está compuesto por todos los datos que el sistema regresará como resultado del proceso. Estos datos se obtienen a partir de los datos de entrada.
Diagrama que representa el flujo de información para resolver un problema
La unión del conjunto de entrada y el conjunto de salida forman lo que se conoce como el dominio del problema, es decir, los valores que el problema puede manejar.
La etapa de análisis es crucial para la creación de un software de calidad, ya que si no se entiende qué es lo que se desea realizar, no se puede generar una solución; sin embargo, es común caer en ambigüedades, debido al mal entendimiento de los requerimientos iniciales.
Ejemplo 1
PROBLEMA: Determinar si un número dado es positivo o negativo.
RESTRICCIONES: El número no puede ser cero.
SOLUCIÓN
DATOS DE ENTRADA: El conjunto de datos de entrada E está compuesto por el conjunto de los números reales, excepto el cero.
E⊂R1, donde
num ∈ E de (-∞, ∞) -{0}
NOTA: R1 representa al conjunto de números reales de una dimensión.
DATOS DE SALIDA: El conjunto de salida S está compuesto por dos valores mutuamente excluyentes.
Un posible conjunto de salida son los valores enteros 0 o 1, en donde 0 indica que el valor es positivo y 1 indica que el valor es negativo.
res=0, si num (0, ∞), res=1, si num (-∞, 0)
Otro posible conjunto de datos de salida son los valores booleanos o lógicos Verdadero o Falso, en donde Verdadero indica que el valor es positivo y Falso indica que el valor es negativo; o viceversa, Verdadero indica que el valor es negativo y Falso indica que el valor es positivo.
Diagrama que representa el flujo de información para determinar si un número es positivo o negativo.
Desliza Izquierda o Derecha
Ejemplo 2
PROBLEMA: Obtener el mayor de dos números diferentes dados.
RESTRICCIONES: Los números de entrada deben ser diferentes.
SOLUCIÓN
DATOS DE ENTRADA: El conjunto de entrada E está dividido en dos subconjuntos E y E'. El primer número (num1) puede adquirir cualquier valor del conjunto de los números reales (E = (-∞, ∞)); sin embargo, el conjunto de entrada del segundo número (num2) es un subconjunto de E, es decir, E' está compuesto por el conjunto de los números reales excepto num1 (E' = (-∞, ∞) ≠ num1).
E, E'⊂R1, donde
num1 ∈ E de (-∞, ∞),
num2 ∈ E' de (-∞, ∞)-{num1}
DATOS DE SALIDA: El conjunto de datos de salida S que puede tomar el resultado r está compuesto por el conjunto de los números reales.
S ⊂R1, donde r ∈ S de (-∞, ∞)
Ejemplo 3
PROBLEMA: Obtener el factorial de un número dado. El factorial de un número está dado por el producto de ese número por cada uno de los números anteriores hasta llegar a 1. El factorial de 0 (0!) es 1:
n! = n * (n-1)!
RESTRICCIONES: El número de entrada debe ser entero positivo o cero. No puede ser negativo.
SOLUCIÓN
DATOS DE ENTRADA: El conjunto de entrada E está dado por el conjunto de los números naturales o por el cero.
E⊂N1, donde
num ∈ E de [1, ∞) ⋃ {0}
DATOS DE SALIDA: El conjunto de salida S está conformado por el conjunto de los números naturales.
S⊂N1; donde
res ∈ S de [1, ∞)
Una vez realizado el análisis, es decir, ya que se entendió qué es lo que está solicitando el usuario y ya identificado el conjunto de entrada y el conjunto de salida, se puede proceder al diseño de la solución, esto es, a la generación del algoritmo.
Dentro del ciclo de vida del software, la creación de un algoritmo se encuentra en la etapa de diseño. Durante el diseño se busca proponer una o varias alternativas viables para dar solución al problema y con base en esto tomar la mejor decisión para iniciar su construcción.
Un problema matemático es computable si puede ser resuelto, en principio, por un dispositivo computacional. La teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo.
Un algoritmo se define como un conjunto de reglas, expresadas en un lenguaje específico, para realizar alguna tarea en general, es decir, un conjunto de pasos, procedimientos o acciones que permiten alcanzar un resultado o resolver un problema. Estas reglas o pasos pueden ser aplicados un número ilimitado de veces sobre una situación particular.
Un algoritmo es la parte más importante y durable de las ciencias de la computación, debido a que puede ser creado de manera independiente, tanto del lenguaje de codificación como de las características físicas del equipo que lo va a ejecutar.
Las principales características con las que debe cumplir un algoritmo son las siguientes:
Preciso
Debe indicar el orden de realización de cada paso y no puede tener ambigüedad.
Definido
Si se sigue dos veces o más se obtiene el mismo resultado.
Finito
Tiene fin, es decir, tiene un número determinado de pasos.
Correcto
Debe cumplir con el objetivo
Debe tener al menos una salida y que sea perceptible.
Debe ser sencillo y legible.
Eficiente
Debe realizarse en el menor tiempo posible.
Eficaz
Que produzca el efecto esperado.
Preciso
Debe indicar el orden de realización de cada paso y no puede tener ambigüedad.
Definido
Si se sigue dos veces o más se obtiene el mismo resultado.
Finito
Tiene fin, es decir, tiene un número determinado de pasos.
Correcto
Debe cumplir con el objetivo
Debe tener al menos una salida y que sea perceptible.
Debe ser sencillo y legible.
Eficiente
Debe realizarse en el menor tiempo posible.
Eficaz
Que produzca el efecto esperado.
Por lo tanto, un buen algoritmo debe ser correcto (cumplir con el objetivo) y eficiente (realizarlo en el menor tiempo posible), además de ser entendible para cualquier persona.
Las actividades a realizar en la elaboración de un algoritmo para obtener una solución a un problema de forma correcta y eficiente se muestran en el esquema “Etapas para la elaboración de un algoritmo”:
Análisis del problema
Con qué datos se cuenta, cuáles son necesarios como valores de entrada, qué restricciones deben considerarse, cómo debe ser la salida para que el problema se resuelva.
Construcción del algoritmo
Se refiere a la descripción detallada de los pasos que deben seguirse para resolver el problema.
Verificación del algoritmo
Consiste en su seguimiento, empleando datos que son representativos del problema que se desea resolver (esto se conoce como prueba de escritorio).
Un algoritmo está constituido por tres módulos básicos:
Ejemplo 4
PROBLEMA: Determinar si un número dado es positivo o negativo.
RESTRICCIONES: El número no puede ser cero.
SOLUCIÓN
DATOS DE ENTRADA: Número real.
DATOS DE SALIDA: La validación de si el número es positivo.
DOMINIO: Todos los números reales.
SOLUCIÓN:
1. Solicitar un número real.
2. Si el número ingresado es cero, se regresa al punto 1.
3. Si el número ingresado es diferente de cero, se validan las siguientes condiciones:
3.1. Si el número ingresado es mayor a 0 se puede afirmar que el número es positivo.
3.2. Si el número ingresado es menor a 0 se puede afirmar que el número es negativo.
Prueba de escritorio
El diseño de la solución de un problema implica la creación del algoritmo y su validación. La validación de un algoritmo se suele realizar mediante una prueba de escritorio.
Una prueba de escritorio es una matriz formada por los valores que van adquiriendo cada una de las variables del programa en cada iteración. Una iteración es el número de veces que se ejecuta un código y permite ver los valores que van adquiriendo las variables en cada repetición.
Para el ejemplo en cuestión, la prueba de escritorio quedaría de la siguiente manera (considerando a X como el número solicitado):
Iteración |
X |
Salida |
1 |
5 |
El número 5 es positivo |
Iteración |
X |
Salida |
1 |
-29 |
El número 29 es negativo |
Iteración |
X |
Salida |
1 |
0 |
- |
2 |
0 |
- |
3 |
0 |
- |
4 |
100 |
El número 100 es positivo |
Ejemplo 5
PROBLEMA: Obtener el mayor de dos números dados.
RESTRICCIONES: Los números de entrada deben ser diferentes.
SOLUCIÓN
DATOS DE ENTRADA: Número real.
DATOS DE SALIDA: La impresión del número más grande.
DOMINIO: Todos los números reales.
SOLUCIÓN:
1. Solicitar un primer número real.
2. Solicitar un segundo número real.
3. Si el segundo número real es igual al primer número real, se regresa al punto 2.
4. Si el segundo número real es diferente al primer número real, se validan las siguientes condiciones:
4.1. Si se cumple con la condición de que el primer número es mayor al segundo número, entonces se puede afirmar que el primer número es el mayor de los números.
4.2. Si se cumple con la condición de que el segundo número es mayor al primer número, entonces se puede afirmar que el segundo número es el mayor de los números.
Prueba de escritorio (X es el primer número solicitado, Y es el segundo):
Iteración |
X |
Y |
Salida |
1 |
5 |
6 |
El número 6 es el mayor |
Iteración |
X |
Y |
Salida |
1 |
-99 |
-222.2 |
El número -99 es el mayor |
Iteración |
X |
Y |
Salida |
1 |
15 |
15 |
- |
2 |
15 |
15 |
- |
3 |
15 |
15 |
- |
4 |
15 |
10 |
El número 15 es el mayor |
Ejemplo 6
PROBLEMA: Obtener el factorial de un número dado. El factorial de un número está dado por el producto de ese número por cada uno de los números anteriores hasta llegar a 1. El factorial de 0 (0!) es 1.
RESTRICCIONES: El número de entrada debe ser entero y no puede ser negativo.
SOLUCIÓN
DATOS DE ENTRADA: Número entero.
DATOS DE SALIDA: La impresión del factorial del número.
DOMINIO: Todos los números naturales positivos.
SOLUCIÓN:
1. Solicitar un número entero.
2. Si el número entero es menor a cero regresar al punto 1.
3. Si el número entero es mayor a cero se crea una variable entera contador que inicie en 2 y una variable entera factorial que inicie en 1.
4. Si la variable contador es menor o igual al número entero de entrada se realiza lo siguiente:
4.1. Se multiplica el valor de la variable contador con el valor de la variable factorial. El resultado se almacena en la variable factorial.
4.2. Se incrementa en uno el valor de la variable contador.
4.3. Regresar al punto 4.
5. Si la variable contador no es menor o igual al número entero se muestra el resultado almacenado en la variable factorial.
Prueba de escritorio (X es el número entero del que se calculará el factorial):
Iteración |
X |
factorial |
contador |
Salida |
1 |
0 |
1 |
2 |
El factorial de 0 es: 1 |
Iteración |
X |
factorial |
contador |
Salida |
1 |
-2 |
1 |
2 |
- |
2 |
-67 |
-1 |
2 |
- |
3 |
5 |
-1 |
2 |
- |
4 |
5 |
2 |
3 |
- |
5 |
5 |
6 |
4 |
- |
6 |
5 |
24 |
5 |
- |
7 |
5 |
120 |
6 |
El factorial de 5 es: 120 |
Iteración |
X |
factorial |
contador |
Salida |
1 |
7 |
1 |
2 |
- |
2 |
7 |
2 |
3 |
- |
3 |
7 |
6 |
4 |
- |
4 |
7 |
24 |
5 |
- |
5 |
7 |
120 |
6 |
- |
6 |
7 |
720 |
7 |
- |
7 |
7 |
5040 |
8 |
El factorial de 7 es: 5040 |
Para solucionar un problema se deben definir tres grandes elementos: el conjunto de entrada, que se refiere a los datos que el problema debe recibir para llegar a la solución; el conjunto de salida, que es la respuesta que se espera, es decir, la solución del problema; y el proceso, el cual recibe los datos de entrada y genera la solución del problema.
El proceso está compuesto por una serie ordenada y finita de pasos que se deben seguir para, a partir de los datos de entrada, llegar a la solución del problema. Esta serie ordenada de pasos se conoce como algoritmo. A continuación, deberás dar solución a dos problemas, construyendo los algoritmos correspondientes.
En esta UAPA aprendiste cómo realizar un algortimo a partir de todos sus elementos. Ahora podrás verificar si conoces bien las funciones de dichos elementos que sirven en su conjunto para solucionar problemas.
Fuentes de información
Andrea, S. (2014). Ingeniería de software [Figura 2]. Consultado en junio de 2015 de http://ing-software-verano2014.blogspot.mx
Guadalupe, C. (2013). Aseguramiento de la calidad del software (SQA) [Figura 1]. Consultado en junio de 2015 de https://www.mindmeister.com/es/273953719/aseguramiento-de-la-calidad delsoftware-sqa
Littman, M. (2012). Intro to algorithms: Social network analysis. Consultado en junio de 2015 de https://www.udacity.com/course/viewer#!/c-cs215/l-48747095/m-48691609
Singh, R. (1995). International standard ISO/IEC 12207. Software life cycle
processes. Consultado en junio de 2015 de http://www.abelia.com/docs/12207cpt.pdf
Solano, J., García, E., Sandoval, L., Nakayama, A., Arteaga, T. y Castañeda, M. (2016). Manual de prácticas del laboratorio de fundamentos de programación. Consultado en abril de 2018 de http://lcp02.fi-b.unam.mx
Cómo citar
Solano, J. A. (2018). Solución de problemas y algoritmos. Unidades de Apoyo para el Aprendizaje. CUAED/Facultad de Ingeniería-UNAM. Consultado el (fecha) de (vínculo)
