1.
PROBLEMAS
Se tiene un problema cuando se desea encontrar uno o varios objetos
desconocidos (ya sean estos números, diagramas, figuras, demostraciones,
decisiones, posiciones, algoritmos, u otras cosas), que cumplen condiciones y/o
relaciones, previamente definidas, respecto a uno o varios objetos conocidos.
De esta manera, solucionar un problema es encontrar los objetos desconocidos
de dicho problema.
1.1 Clasificación de problemas
1.2 Ejemplos de problemas
1.3 Ejercicios
1.1 CLASIFICACION DE PROBLEMAS
Los problemas se clasifican por la existencia de una solución en solubles, no
solubles e indecidible.
Un problema se dice SOLUBLE si se sabe de antemano que existe
una solución para él.
Un problema se dice INSOLUBLE si se sabe que no existe una
solución para él.
Un problema se dice INDECIDIBLE si no se sabe si existe o no
existe solución para él.
A su vez, los problemas solubles se dividen en dos clases: los algorítmicos y los
no algorítmicos.
Un problema se dice ALGORÍTMICO[1] si existe un algoritmo que
permita darle solución.
Un problema se dice NO ALGORÍTMICO si no existe un algoritmo
que permita encontrar su solución.
[1] En este curso solo se tratarán problemas algorítmicos
1.2 EJEMPLOS DE PROBLEMAS
1. Sean los puntos P=(a,b) y Q=(c,d) que definen una recta, encontrar un
segmento de recta perpendicular a la anterior que pase por el punto medio de los
puntos dados.
OBJETOS
Los puntos P y Q.
CONOCIDOS
El segmento de recta debe pasar por el punto medio entre
CONDICIONES P y Q, y debe ser perpendicular a la recta trazada entre P
yQ
Soluble-algorítmico. Es soluble por que ya existe un
TIPO DE PROBLEMA algoritmo que permite encontrar la solución del mismo.
Este algoritmo fue presentado en la sección anterior.
2. De las siguientes cuatro imágenes, ¿cuál es la más llamativa?
OBJETOS
Una de las cuatro imágenes.
DESCONOCIDOS
OBJETOS
Las cuatro imágenes.
CONOCIDOS
Soluble-no algorítmico. La solución de este problema
existe, es alguna de las cuatro imágenes presentadas,
TIPO DE PROBLEMA pero no existe un algoritmo que permita determinar cual
es, ya que el concepto de imagen más llamativa no esta
bien definido.
3. Un granjero tiene cincuenta animales entre conejos y gansos. Si la cantidad
de pies de los animales es ciento cuarenta, ¿cuántos conejos y cuantos gansos
tiene el granjero?
OBJETOS
La cantidad de conejos y la cantidad de gansos.
DESCONOCIDOS
OBJETOS
La cantidad total de animales, cantidad de pies totales.
CONOCIDOS
La suma de los conejos y los gansos es igual a cincuenta.
La suma de los pies de los conejos (cuatro por cada uno)
CONDICIONES
y de los gansos (dos por cada uno) es igual a ciento
cuarenta.
TIPO DE PROBLEMA Soluble-algorítmico.
4. ¿Existe en la expansión decimal de p una secuencia de tamaño n para
cualquier número natural n?
OBJETOS
Un valor de verdad (falso o verdadero).
DESCONOCIDOS
OBJETOS
El número n.
CONOCIDOS
Verdadero si existe en la expansión decimal de p una
CONDICIONES secuencia de tamaño n del número n, para todo número
natural n, Falso en otro caso.
Indecidible. Este problema es indecidible por que si en el
primer millón de dígitos de p no se encuentra una
secuencia como la buscada, nada garantiza que en el
siguiente millón de dígitos no se encuentre tal secuencia.
TIPO DE PROBLEMA
Pero si no se encuentra en el segundo millón, nada
garantiza que no se encuentre después o no se encuentre.
De esta manera no se puede decidir si existe o no existe
tal secuencia.
5. Realizar la suma de los siguientes números: 1245893467 y 3464895786.
OBJETOS
Un número natural.
DESCONOCIDOS
OBJETOS
Dos números naturales 1245893467 y 3464895786.
CONOCIDOS
El número desconocido es igual a la suma de los dos
CONDICIONES
números dados.
Soluble-algorítmico. Es soluble por que ya existe un
TIPO DE PROBLEMA algoritmo que permite encontrar la solución del mismo.
Este algoritmo fue presentado en la sección anterior.
6. Una partícula se mueve en el espacio de manera aleatoria, si en el instante
de tiempo t se encuentra en la posición x, ¿cuál será la posición exacta de dicha
partícula 10 segundos después?
OBJETOS
Una posición.
DESCONOCIDOS
OBJETOS
Posición en el instante de tiempo t.
CONOCIDOS
CONDICIONES La partícula se mueve en el espacio de manera aleatoria.
Insoluble. No se puede solucionar por que no existe forma
TIPO DE PROBLEMA de predecir la posición de la partícula, pues su movimiento
es aleatorio, es decir, se mueve de manera arbitraria.
7. Un robot puede apilar (poner encima), en ciertos lugares cajas de diferentes
tamaños. La caja a apilar no puede ser más grande que las que ya estén apiladas
en dicho lugar. El robot puede solo tomar la caja de más arriba de una pila.
Mirando la figura, como puede el robot pasar las tres cajas apiladas en el lugar A,
al lugar C usando, si es necesario, el lugar de apilar B.
OBJETOS
Una secuencia de apilamientos.
DESCONOCIDOS
OBJETOS Número de cajas, posición inicial y posición destino,
CONOCIDOS número de lugares de apilamiento.
Solo se pueden apilar cajas sobre otras más grandes.
CONDICIONES Solo se puede tomar la una caja a la vez y solo la que este
más arriba en una pila de cajas.
TIPO DE PROBLEMA Soluble-algorítmico.
1.3 EJERCICIOS
Para los siguientes problemas, determine los objetos conocidos, desconocidos, las
condiciones y el tipo de problema. Para aquellos problemas algorítmicos desarrolle
adicionalmente un algoritmo que permita encontrar una solución.
1. Se tienen dos jarras (A y B) de capacidades 3 y 7 litros respectivamente, sobre
las cuales se pueden efectuar las siguientes acciones: Llenar totalmente
cualquiera de las dos jarras, vaciar una de las dos jarras en la otra hasta que la
jarra origen este vacía o hasta que la jarra destino este llena y vaciar el contenido
de una jarra (este llena o no) en un sifón. ¿Cómo se puede dejar en la jarra A un
solo litro utilizando solamente las anteriores acciones?.
2. Es cierta o no es cierta la siguiente frase: “Esta frase no es cierta”.
3. Si Juan tiene el doble de la edad de Pedro y la suma de las edades de los dos
es 33 años, ¿Cuántos años tiene Juan y cuántos tiene Pedro?.
4. ¿Qué figura se forma al unir los puntos marcados con números consecutivos
con una línea?
5. Calcular de manera exacta el número de átomos del universo.
6. Calcular el costo de una serie de productos comprados en el supermercado.
7. Determinar quién es el mejor jugador de fútbol de toda la historia.
8. Construir un barco de papel.
