Resolución de Problemas
Introducción a la Programación
Motivación
2
ax + bx+c=0
2
Pasos en la resolución de un problema
 Entender el problema
 Conceptualización
 Objetivo
 Contexto
 Buscar soluciones
 Elegir solución
 Diseñar solución
 Descomposición
 Especificar tareas
 Modelar solución
 Implementar solución
 Validar solución
3
¿Qué es un problema?
 Es una abstracción de la realidad para la
cual nos interesa conocer una solución
 Solución: procedimiento que nos lleva a
satisfacer ciertos requerimientos
4
Datos y Variables
 Datos: objetos simbólicos que representan
objetos del mundo real.
 Ejemplos: 10 de Marzo de 2003, 3.14
 Variables: no hace referencia a un objeto
explícito
 Ejemplos: velocidad del móvil, factor de
crecimiento
5
¿Qué es un Modelo?
 Estructura para dar razón y abstraer una
realidad
 Ejemplo:
6
¿Qué es un algoritmo?
 Procedimiento detallado para resolver un
problema en pasos y en un tiempo finito.
 Se especifican en base a operaciones
básicas que controlan las variables y el
flujo del algoritmo
 El algoritmo lleva desde un estado inicial
a un estado final
 El algoritmo recibe Entradas y entrega
Salidas
7
¿Cómo desarrollar un algoritmo?
 Imaginación
 No reinventar la rueda
 Dividir para conquistar
 Para ser efectivo se requiere practicar
constantemente
 El diseño de algoritmos es una rama de la
Ciencia de la Computación
8
¿Cómo se describe un algoritmo?
 Lenguaje natural
 Pseudo código
 Lenguaje de programación
 La precisión es importante
 Un algoritmo no puede ser descrito de forma
ambigua:
 Todos tienen que entender lo mismo (incluido el
computador!)
9
Pueden existir varios algoritmos para
resolver el mismo problema
 Depende de quién lo invente
 Depende de qué se quiera optimizar
 Ej.: tiempo versus costo
10
¿Qué es una metodología?
Se puede decir que una metodología es
como un algoritmo genérico.
11
Problemas de los problemas
12
Solución a los problemas de los problemas
Problema
• Conceptualización
• Objetivo
• Elementos involucrados
13
Problemas de las soluciones
14
Solución a los problemas de las soluciones
Solución
• Validación
• Especificación de limitaciones
15
Una metodología para crear algoritmos
1.
Definición del problema (planteamiento original)



2.
Conceptualización de la solución



3.
Especificar la secuencia de actividades
Dependiendo de la complejidad del algoritmo, descomponer en subalgoritmos
Validación del algoritmo


5.
Descomposición
Tareas
Variables
Especificación del algoritmo


4.
Conceptualización (contexto)
Objetivo (cualitativo y cuantitativo)
Elementos involucrados
Dominios
Ejecución
Limitaciones del algoritmo

Identificación de puntos débiles (condiciones críticas)
16
Simulando la preparación de un pie
17
Simulando la preparación de un pie
1. Definición del problema
 Conceptualización: problema consiste en preparar un pie de alguna
fruta, usando una cierta receta, y servirlo a una cierta cantidad de
comensales.
Entradas: cantidad de huevos, harina y mantequilla, fruta con que
se cubrirá el pastel y cantidad correspondiente, tiempo que debe
permanecer en el horno, y número de comensales.
 Objetivo: poder repartir un pie de fruta entre los comensales.
 Elementos involucrados:
Elemento activo: cocinero que llevará a cabo el proceso.
Elementos pasivos: ingredientes y cantidades (huevos, harina,
mantequilla, fruta), tiempo de horneado, y número de comensales.
18
Simulando la preparación de un pie
2. Conceptualización de la solución

Descomposición: obtener la receta a emplear; preparar la base
del pie, mezclando los distintos ingredientes; hornear la base
durante un cierto tiempo; preparar la fruta; cortar el pie y
servirlo a los comensales.

Tareas:
 mezclar_base(huevos, harina, mantequilla)
 hornear_base(tiempo_horno)
 preparar_fruta(tipo_fruta, fruta)
 cortar_servir(comensales, tipo_fruta)

Variables:
 tipo_fruta, huevos, harina, mantequilla, fruta,
tiempo_horno, comensales
19
Simulando la preparación de un pie
3. Especificación del algoritmo
1. Obtener la receta (huevos, harina, mantequilla,
tipo_fruta, fruta y tiempo_horno)
2. Obtener la cantidad de comensales (comensales)
3. Mezclar_base(huevos, harina, mantequilla)
4. Hornear_base(tiempo_horno)
5. Preparar_fruta(tipo_fruta, fruta)
6. Cortar_servir(comensales, tipo_fruta)
20
Simulando la preparación de un pie
4. Validación del algoritmo


Dominios: Los posibles dominios que existen en el contexto de este
problema se constituyen a partir de los distintos valores de entrada
que pueden recibirse del usuario. Es decir, distintos tipos de fruta,
distintas cantidades para cada ingrediente, distintos tiempos en el
horno y distintas cantidades de comensales.
Validación: Debe ejecutarse el algoritmo para los dominios definidos,
es decir, cambiando valores para cada dato de entrada, y verificando
que se puede alcanzar el objetivo buscado.
5. Limitaciones del algoritmo
21
Cambio de neumático desinflado
22
Cambio de neumático desinflado
1. Definición del problema

Conceptualización:


Objetivo:



En una carretera, un auto se ha quedado parado, pues uno de sus 4
neumáticos se ha desinflado. El auto cuenta con herramientas para que el
conductor pueda cambiarlo por uno de repuesto en buenas condiciones.
Cualitativamente: cambiar neumático desinflado por el de repuesto.
Cuantitativamente: el logro se mide verificando que los 4 están inflados.
Elementos involucrados:


elemento activo: conductor del auto.
elementos pasivos: maletero; 4 ruedas, una de las cuales tiene el
neumático desinflado; 4 pernos que sujetan cada rueda; neumático de
repuesto, en buenas condiciones, ubicado en maletero del auto; gata
hidráulica en el maletero del auto; llave de cruz en el maletero del auto
23
Cambio de neumático desinflado
2. Conceptualización de la solución

Descomposición:




Retirar y colocar cosas
Aflojar y apretar pernos
Subir y bajar el auto con la gata
Tareas:






Retirar "algo" de un "lugar"
Colocar "algo" en un "lugar"
Aflojar "un determinado perno"
Apretar "un determinado perno"
Subir auto desde "una determinada posición"
Bajar auto desde "una determinada posición"
24
Cambio de neumático desinflado
2. Conceptualización de la solución

Variables:







N: rueda con neumático desinflado
M: maletero
G: gata hidráulica
L: llave de cruz
P: un perno (su número: 1, 2, 3, ó 4)
D: neumático desinflado
R: neumático de repuesto
25
Cambio de neumático desinflado
3. Especificación del algoritmo
1. Retirar gata hidráulica G del maletero M
2. Retirar llave de cruz L del maletero M
3. Itere sobre cada perno P = 1,2,3,4
3.1. Aflojar con llave L, perno P en rueda N
4. Subir auto con gata hidráulica G en posición N
5. Itere sobre cada perno P = 1,2,3,4
5.1. Retirar perno P de rueda N
6. Retirar neumático D de rueda N
7. Retirar neumático R del maletero M
8. Colocar neumático R en rueda N
9. Colocar neumático D en maletero M
10. Itere sobre cada perno P = 1,2,3,4
10.1. Colocar perno P en rueda N
11. Bajar auto con gata hidráulica G en posición N
12. Itere sobre cada perno P = 1,2,3,4
12.1. Apretar con llave L, perno P en rueda N
13. Colocar llave de cruz L en maletero M
14. Colocar gata hidráulica G en maletero M
26
Cambio de neumático desinflado
4. Validación del algoritmo


Dominios: dependen del neumático que se haya desinflado.
Validación: Ejecutar algoritmo para cualquiera de los cuatro
neumáticos del auto.
5. Limitaciones del algoritmo


Auto debe tener 4 pernos sujetando cada rueda.
Se dejaron de lado algunas consideraciones, como por ejemplo,
abrir y cerrar el maletero, transportar los neumáticos y las
herramientas.
27
Llamada telefónica
 Se desea conceptualizar el
problema de efectuar una
llamada telefónica en un
teléfono público que recibe
monedas de $10, $50 y $100.
El costo mínimo de la
llamada es de $100 por 5
minutos. El proceso se inicia
desde que se levanta el
auricular y finaliza cuando se
cuelga.
28
Árboles de decisión
 Herramienta
útil para
describir
algoritmos que
involucran
gran cantidad
de decisiones
29
Diagramas de Flujo de Control
30
Descargar

Conceptos Básicos de algoritmos