Algoritmos
Unidad 2
Algoritmos y resolución de
problemas
Contenido
•
•
•
•
•
•
Problemas y categorías de problemas
Análisis del problema
Entradas y salidas de un algoritmo
Variables constantes y expresiones
Algoritmos en acción
Verificación del algoritmo
Problemas y categorías de problemas
• Problema:
– Descripción textual o verbal de una situación en la
que a partir de una serie de supuestos, es necesario
obtener una o varias respuestas usando una serie de
pautas, lineamientos o métodos conocidos.
• Un problema correctamente definido contendrá:
– Estado inicial.
– Una o varias incógnitas.
– Las pautas para su resolución.
Problemas y categorías de problemas …(2)
• En el área de ciencias de la computación
hablamos de dos tipos de problemas:
– Problemas computables:
• Existe al menos un algoritmo capaz de darles solución.
– Problemas no computables:
• Carecen de un algoritmo para resolverlos y no es
posible solucionarlos utilizando una computadora.
Problemas y categorías de problemas …(3)
• Características de las soluciones algorítmicas:
– Ser completa:
• Siempre se debe producir una respuesta al ejecutar el algoritmo.
– Ser correcta:
• La respuesta obtenida al ejecutar el algoritmo se encuentre en el
dominio de las soluciones esperadas.
– Obtenida mediante un proceso repetible y verificable:
• La secuencia de pasos del algoritmo debe ser finita, donde cada
paso esta libre de ambigüedad y se identifica lo que realiza.
– Ser determinista:
• Para iguales circunstancias iniciales en el algoritmo, llegamos a las
mismas soluciones.
Análisis del problema
• Antes de intentar diseñar, escribir o verificar el
funcionamiento de una solución algorítmica es
necesario partir de la compresión del
problema, lo cual implica cierto conocimiento
del contexto del propio problema.
– Si deseamos cocinar una galleta debemos saber
que es una galleta.
Análisis del problema … (2)
•
El objetivo principal del análisis del problema es identificar
los datos de entrada necesarios para que trabaje el algoritmo
y cuáles son los resultados a generar.
•
Este objetivo se logra respondiendo a preguntas como:
1.
2.
3.
4.
5.
6.
7.
8.
¿Cuáles son los valores iniciales del problema?
¿Qué es necesario preguntar para completar los datos iniciales?
¿De dónde se tomarán los datos iniciales?
¿Qué supuestos se consideran al inicio del problema?
¿Cuál es la incógnita o incógnitas?
¿Que necesita resolver el problema?,
¿Qué información se debe presentar como resultado?
¿A través de qué forma se deben entregar los resultados?
Entradas y salidas de un algoritmo
• Existen tres elementos principales que
intervienen en la estructura de un algoritmo.
Éstos son:
– Datos de entrada
– Procesos, y
– Salidas o resultados.
Entradas y salidas de un algoritmo … (2)
• Primer ejemplo:
– Mostrar el nombre del usuario que va a usar el
sistema de cómputo y darle un mensaje de
bienvenida en pantalla.
Entradas y salidas de un algoritmo … (3)
1. ¿Cuáles son los valores iniciales del problema?
– Los valores iniciales del problema son generalmente datos
que se dan en el texto del problema y que serán usados
en el diseño del algoritmo.
– En este primer ejemplo no contamos con ningún dato
inicial ya que no hay referencia a ellos en el texto del
problema. Los datos que buscamos como valores iniciales
pueden ser: cantidades numéricas, textos, fórmulas,
equivalencias, entre otros.
Entradas y salidas de un algoritmo … (4)
2. ¿Qué es necesario preguntar para completar los
datos iniciales?
– La pregunta se refiere a datos que se requieren conocer
de antemano para llevar a cabo un proceso (factores de
conversión, porcentajes, fechas, cantidades, etc.).
– En este primer ejemplo, sabemos que necesitamos el
nombre del usuario, pero desconocemos cuál es ese
nombre, por lo tanto necesitamos preguntar este dato.
Entradas y salidas de un algoritmo … (5)
3. ¿De dónde se tomarán los datos iniciales?
– Se refiere a los medios a través de los cuales se
ingresarán los datos iniciales, por lo regular son
dispositivos de entrada tales como: teclados,
lectores de código de barras, ratón entre otros.
– En este primer ejemplo, no es claro de donde se
tomará el nombre del usuario ya que el texto del
problema no hace referencia alguna a ello.
Entradas y salidas de un algoritmo … (6)
4. ¿Cuáles son los supuestos del problema?
– Un supuesto o supuestos son situaciones que
establecemos como ciertas aunque no se especifiquen en
el texto original del problema. Estos supuestos no deben
alterar lo que el problema solicita.
– Para este primer ejemplo, vamos a suponer que el usuario
tiene a su disposición un teclado y una pantalla.
Observemos que el problema no dice que exista un
teclado, pero es un “supuesto” necesario para que el
usuario introduzca su nombre.
– El problema tampoco define el contenido del mensaje de
bienvenida. Nosotros asumiremos que el mensaje diga
“hola, bienvenido” seguido del nombre del usuario.
Entradas y salidas de un algoritmo … (7)
5. ¿Cuál es la incógnita o incógnitas?
– Las incógnitas se refieren a los datos que
necesitamos mostrar u obtener como resultado
final.
– En este primer ejemplo la incógnita coincide con
el dato de entrada que es el nombre del usuario
ya que es lo que se pide mostrar, conjuntamente
con el saludo.
Entradas y salidas de un algoritmo … (8)
6. ¿Qué necesita resolver el problema?
– Se refiere a las acciones que son necesarias para
transformar los datos de entrada en la salida esperada.
– Una estrategia para identificar las acciones a realizar para
resolver un problema consiste en identificar los verbos en
el texto dado.
– En este primer ejemplo, ese verbo es mostrar: “mostrar el
nombre del usuario y un mensaje de bienvenida”. Es decir,
si sólo mostramos el nombre del usuario, la solución es
incompleta. Si sólo mostramos el mensaje de bienvenida,
la solución es incompleta. Necesitamos mostrar el nombre
y el mensaje de bienvenida al mismo tiempo.
Entradas y salidas de un algoritmo … (9)
7. ¿Qué información se debe presentar como
resultado?
– Hace referencia a la forma en el cual los datos
deben ser mostrados como resultado.
– Para este primer ejemplo, el mensaje: “hola,
bienvenido” seguido del nombre del usuario.
Entradas y salidas de un algoritmo … (10)
8. ¿A través de qué medio se deben entregar
los resultados?
– Se refiere a los medios a través de los cuales
deben entregarse los resultados, por lo regular
se trata de un dispositivo de salida.
– Para este primer ejemplo, el texto señala que el
mensaje será enviado a pantalla.
Entradas y salidas de un algoritmo … (11)
• Las respuestas a las ocho preguntas previas
son una guía para obtener un problema bien
definido. Ahora podemos describirlo en los
siguientes términos:
– Tenemos un usuario, el cual a través de un teclado
introducirá su nombre. Posteriormente, deberá
mostrarse un mensaje de bienvenida con la
leyenda “hola, bienvenido” seguido del nombre
del usuario a través de una pantalla.
Entradas y salidas de un algoritmo … (12)
• Adicionalmente, una buena práctica dentro del
diseño de un algoritmo es tabular las entradas y
salidas identificadas a partir del análisis del
problema:
Entrada
Nombre
Salida
Mensaje de bienvenida, nombre
Variables, constantes y expresiones
• La elaboración de un algoritmo requiere del cumplimiento de
ciertas reglas de sintaxis. Estas reglas permiten cumplir con un
objetivo básico de los algoritmos: Estar libres de ambigüedad.
• Los datos de entrada y salida son la materia prima de un
algoritmo, ya que es posible realizar un sin fin de tareas con
ellos.
• A nivel de algoritmo, los datos pueden ser de tres tipos
principalmente:
– Numéricos.
– Caracteres.
– Lógicos.
Variables, constantes y expresiones … (2)
• Los datos numéricos se dividen a su vez en:
– Enteros
– Reales
• Los datos numéricos también pueden ser positivos o negativos y pueden
representar:
–
–
–
–
–
Cantidades
Distancias
Temperaturas
Peso
Etc.
• Ejemplos:
–
–
–
–
1
-12.5
3.141516
-9
Variables, constantes y expresiones … (3)
• Los datos de tipo carácter representan textos que
pueden contener:
– Una simple letra
– Una palabra
– Una oración completa
• Ejemplos:
–
–
–
–
–
“a”
“Juan”
“hola a todos”
“1.0”
“F”
Variables, constantes y expresiones … (4)
• Los datos de tipo lógico permiten representar
solo dos posible valores:
– Falso (F)
– Verdadero (V)
• Ejemplos:
–F
–V
Variables, constantes y expresiones … (5)
• Variable:
– Representa a un dato en particular alojado en la
memoria que es identificado mediante un nombre
(identificador de la variable)
– Las variables pueden ser de tipo:
• Numérico
• Carácter
• Lógico
Variables, constantes y expresiones … (6)
• Reglas para los nombres (identificadores) de las
variables:
– Debe iniciar con una letra del alfabeto, mayúscula o
minúscula.
– No debe tener espacios en blanco. En su lugar puede usar
el símbolo guión bajo ( _ ) para separar nombres largos.
– Puede incluir números, siempre que no se presenten al
principio del nombre.
– Los nombres de variables son sensibles a mayúsculas o
minúsculas. Es decir, aunque un identificador tenga el
mismo nombre que otro, el orden y uso de mayúsculas los
haría diferentes.
Variables, constantes y expresiones … (7)
•
Algoritmo para el primer ejemplo:
1. Iniciar
2. Escribir en pantalla un mensaje solicitando al usuario
que introduzca su nombre
3. Asignar el dato leído en la variable nombre_usuario
4. Escribir en pantalla el mensaje “hola, bienvenido ”
seguido de lo almacenado en nombre_usuario
5. Finalizar
Variables, constantes y expresiones … (8)
• Constantes:
– Al valor que se le asigna al inicio del algoritmo a
un identificador y permanece sin cambios en todo
el cuerpo del algoritmo se le denomina constante.
– Por ejemplo: el valor de pi, el número de días de la
semana, etc.
– Las reglas que aplican para los nombres de las
variables son los mismos que aplican para los
nombres de las constantes.
Variables, constantes y expresiones … (9)
• La manipulación de variables y constantes nos conduce a un
nuevo concepto: expresiones. Las expresiones son una forma
de describir las siguientes acciones:
– Operaciones de cálculo aritmético
• Son instrucciones que implican el uso de operadores aritméticos (suma,
resta, multiplicación, división, etc.) para realizar operaciones matemáticas
y cuyo resultado se puede o no asignar a una variable
– Operaciones lógicas
• Corresponden a instrucciones donde comparamos valores, variables,
constantes o resultados de operaciones de cálculo para saber si son
iguales, diferentes, si uno es mayor a otro, etc.
– Operaciones de asignación
• Corresponde a instrucciones en donde una variable o constante: 1) recibe
un valor directamente, 2) recibe datos almacenados en otro identificador,
3) recibe el resultado de una operación de cálculo, o 4) recibe el resultado
de una operación lógica
Variables, constantes y expresiones … (10)
•
•
Las expresiones u operaciones de asignación, establecen el
valor que toma una variable o constante.
Ejemplos:
–
–
–
–
–
•
nombre_usuario = “Roberto”
edad = 25
estatura_metros = 1.70
pi = 3.1416
edad_nueva = edad
En los ejemplos anteriores debemos advertir dos cosas:
1.
2.
La asignación siempre se realiza de derecha (dato) a izquierda
(nombre de la variable).
Una vez asignado un valor a una variable por primera vez, dicha
variable solo aceptará datos del mismo tipo
Variables, constantes y expresiones … (11)
•
Las siguientes expresiones u operaciones de asignación NO SON
CORRECTAS:
–
–
“Roberto” = nombre_usuario NO ES CORRECTO
25 = edad
NO ES CORRECTO
y
–
•
edad = edad_nueva NO SIGNIFICA LO MISMO QUE edad_nueva = edad
Si una variable se inicializa con un dato de tipo carácter, sería un ERROR
asignarle posteriormente un dato de tipo numérico y viceversa. Sin
embargo, hay que tomar en cuenta que una variable a la que se le
asignó un valor numérico se comportará de la siguiente manera:
–
Si se asignó por primera vez un valor de tipo numérico entero, entonces:
•
–
edad = 23.5 ES CORRECTO, PERO EL VALOR ALMACENADO SERÁ 23
Si se asigno por primera vez un valor de tipo numérico real, entonces:
•
estatura_metros = 2 ES CORRECTO, PERO EL VALOR ALMACENADO SERÁ 2.0
Variables, constantes y expresiones … (12)
•
Las operaciones de cálculo aritmético que solo
involucran enteros dan como resultado un entero:
– Suma = 1 + 1
– Res_prod = 2 * 4
– Res_division = 9 / 2
•
(aquí el resultado es 4)
Las operaciones de cálculo aritmético que
involucren al menos un dato real darán como
resultado un real:
– Suma_r = 1.0 + 2 + 1
– Res_prod_r = 2.5 * 2
– Res_div_r = 9.0 / 2
(aquí el resultado es 4.5)
Variables, constantes y expresiones … (13)
• Operadores aritméticos y sus reglas de
prioridad:
cantidad = 2 + 1 * 3
¿el resultado es 9 o 5 ?
Variables, constantes y expresiones … (14)
• Cuál es el resultado de las siguientes
expresiones de cálculo aritmético?:
–
–
–
–
–
cantidad2 = -3 * 1 + 7
cantidad3 = 12 - 2 / 2 + 3
cantidad4 = 2 + 2 * 4 / 2
cantidad3_A = (12 - 2)/(2 + 3)
cantidad3_B = 12 - ((2/2)+ 3)
Variables, constantes y expresiones … (15)
•
Las operaciones de cálculo aritmético generalmente están expresadas
en los libros usando una notación algebraica, debemos reescribir estas
operaciones de forma algorítmica para poder utilizarlas.
Descargar

Diapositivas (incompletas)