Algoritmos Unidad 2 Algoritmos y resolución de problemas

Algoritmos

Unidad 2Algoritmos 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. ¿Cuáles son los valores iniciales del problema?2. ¿Qué es necesario preguntar para completar los datos iniciales?3. ¿De dónde se tomarán los datos iniciales?4. ¿Qué supuestos se consideran al inicio del problema?5. ¿Cuál es la incógnita o incógnitas?6. ¿Que necesita resolver el problema?,7. ¿Qué información se debe presentar como resultado?8. ¿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.


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.


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.


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.


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.


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.


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.


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.


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.


• 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.


• 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 Salida

Nombre 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


• 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”


• Los datos de tipo lógico permiten representar solo dos posible valores:– Falso (F)– Verdadero (V)

• Ejemplos:– F– V


• 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


• 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.


• Algoritmo para el primer ejemplo:1. Iniciar2. Escribir en pantalla un mensaje solicitando al usuario

que introduzca su nombre3. Asignar el dato leído en la variable nombre_usuario4. Escribir en pantalla el mensaje “hola, bienvenido ”

seguido de lo almacenado en nombre_usuario5. Finalizar


• 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.


• 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


• 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. La asignación siempre se realiza de derecha (dato) a izquierda

(nombre de la variable).2. Una vez asignado un valor a una variable por primera vez, dicha

variable solo aceptará datos del mismo tipo


• 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


• 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)


• Operadores aritméticos y sus reglas de prioridad:

cantidad = 2 + 1 * 3 ¿el resultado es 9 o 5 ?


• 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)


• 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.

Documents

Algoritmos Unidad 2 Algoritmos y resolución de problemas