Autor Tema: Diferencia entre uds y la fuerza bruta?

0 Usuarios y 1 Visitante están viendo este tema.

12 Marzo, 2016, 03:21 am
Leído 1716 veces

Tachikomaia

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 208
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
No creo que sean iguales, pero no sé si alguna vez tuve las diferencias suficientemente claras como para decirlas. Quisiera comprenderlas mejor, que me las digan.

Fuerza bruta por lo que tengo entendido es probar cosas que no se sabe si sirven o no, hasta confirmar que una sirve o hasta un límite especificado, en cuyo caso el problema no se resuelve.
Por ejemplo para hallar X en X+6=38 se podría probar X con valor 1, si no sirve con 2, y así sucesivamente. Como dije se puede poner un límite, por ejemplo 38.

Uds usan métodos más inteligentes, aunque básicamente entre más complejo sea el problema más suposiciones hacen, que les pueden llevar a errores. En el caso de la ecuación suponen que 38-6=X.

Estoy investigando los tipos de problema, como pueden ver aquí:
http://www.forosdelweb.com/f14/clasificacion-problemas-segun-metodo-solucion-1148298/

Hago este tema por si saben algo de eso o me pueden decir algo que me sirva.

Gracias.

12 Marzo, 2016, 10:25 am
Respuesta #1

elcristo

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,193
  • Karma: +1/-0
  • Sexo: Masculino
Hola.

En tu ejemplo, para resolver la ecuación, no se "supone" que \( x=38-6 \), es que se demuestra que es así. Se demuestra que en una igualdad sumar y restar a ambos lados lo mismo mantiene la igualdad y por tanto se puede hacer eso.

La diferencia entre usar la "fuerza bruta" o no son los teoremas. Muchos de ellos tienen suposiciones bastante restrictivas, pero los problemas que se resuelven con ellos encajan en esas hipótesis, obviamente. Y por cada teorema que te permite resolver un problema, hay uno que te dice que no se puede resolver (No exactamente vamos, pero ya me entendéis)


Uds usan métodos más inteligentes, aunque básicamente entre más complejo sea el problema más suposiciones hacen, que les pueden llevar a errores.

Una suposición no te puede llevar a error (Salvo que estés demostrando por reducción al absurdo, pero en ese caso el error es el acierto). Si tú supones algo puede que sirva o que no sirva para resolver el problema, incluso puede hacerte resolver un problema distinto, pero no te va a hacer resolver mal tu problema salvo que lo hagas mal, en cuyo caso el problema no es de la suposición, sino del proceso que viene después.

En cuanto a tu mensaje en el otro foro. Lo que lleva a clasificar los problemas con los que te encuentras es la experiencia. Si tú te encuentras un problema así:

Probar que \( A\subseteq{}B \) siendo \( A,B \) dos conjuntos. Pues todo hijo de vecino que haya hecho un par de problemas cogerá un elemento de \( A \) e intentará ver que está en \( B \).

Si tienes que probar \( \displaystyle\sum_{i=1}^n{i^2}=2^n\sqrt[n ]{n} \) pues lo pruebas por inducción (Olvidaos del ejemplo, han sido cosas puestas al azar)

Es decir, una vez te enfrentas a muchos problemas, ya los vas metiendo en sacos, y cuando te encuentras con un problema lo intentas meter en uno de esos sacos. Si no puedes meterlo en uno de los sacos, intentas romper el problema en piezas e intentar meter las piezas en diferentes sacos, y si eso no funciona vas al sastre y le pides un saco parecido a otro que tienes, a ver si entra en ese. Y si ya eso tampoco funciona pues coges aguja e hilo e intentas hacer tú un saco en el que entre.

Saludos.

12 Marzo, 2016, 05:43 pm
Respuesta #2

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,274
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Una cosa son las "suposiciones" y otra son los "hechos".

Aquellos "hechos" que se sabe que son verdaderos, se pueden usar.
Los Teoremas provienen, muchas veces, de cientos de años de experiencia que se han resumido en un formato general, lo bastante potente como para ser aplicado a muchos casos.

Para el caso de la ecuación \(x+6 = 38\),
el teorema que se puede usar es que:
La suma de números enteros satisface la propiedad de monotonía respecto la igualdad.
(Algunos la llaman "Ley Uniforme").

El objetivo es despejar el término \(x\).
Sabiendo que "al sumar el mismo número entero a ambos lados de una igualdad, se obtiene otra igualdad equivalente",
esto nos dice que la ecuación original tiene las mismas soluciones que otra ecuación a la cual se le suma el mismo número a ambos lados.

Pero uno "se da cuenta" que al sumar \(-6\) se va a producir una cancelación con el +6 que está presente en la ecuación, y así la x quedará despejada.

Los pasos serían estos:

* Sumar -6 a ambos miembros de la ecuación original:

\(x + 6 + (-6) = 38 + (-6)\)

La ecuación resultante tiene el mismo conjunto de soluciones que la ecuación origina.

* Ahora resolvemos un poco:

\(x + 0 = 32 \)

* Resolvemos un poco más, aprovechando que el 0 es neutro de la suma:

\(x = 32\)

Y problema resuelto.

-----------------

No sólo hay supuestos astutos, también hay conocimiento acumulado,
y estrategias que provienen de la experiencia.

Dado lo corta que es la vida humana,
no hay tiempor para intentar todas las soluciones por fuerza bruta.
Todo método que agilice los cálculos, mientras sea lógicamente válido y demostrado,
se puede y debe usar.

--------------------

De hecho, cuando se trata de resolver problemas con un algoritmo de computadora,
lo que hago primero es demostrar todos los casos o porciones del problema que pueden inferirse de manera absolutamente lógica o matemática,
y el resto lo pongo a procesar por el programa.

El resultado es un programa válido, porque las soluciones que da son correctas,
y encima hace menos esfuerzo en verificaciones, y por lo tanto responde más rápido.

Saludos.

14 Marzo, 2016, 08:45 am
Respuesta #3

Tachikomaia

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 208
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
En tu ejemplo, para resolver la ecuación, no se "supone" que \( x=38-6 \), es que se demuestra que es así. Se demuestra que en una igualdad sumar y restar a ambos lados lo mismo mantiene la igualdad y por tanto se puede hacer eso.
mmm... te refieres a que ya está demostrado? Porque yo no lo he demostrado. La suposición es que (X+6=38) = (X=38-6), ya sé que no lo dicen así, pero es que se trata de de que hay una relación entre ecuaciones, es decir se supone que existe esa relación, la supocición no es simplemente sobre 1 ecuación. O sí en el sentido de que cumple cierta propiedad. Sí, nos entendemos, pero quería aclarar.

Citar
Y por cada teorema que te permite resolver un problema, hay uno que te dice que no se puede resolver (No exactamente vamos, pero ya me entendéis)
Eso no lo entendí. ¿Teoremas opuestos (unos dicen sí otros no)? ¿o teoremas referidos a distintos problemas, donde cada teorema dice si es resolvible o no el problema que trata? Supongo que lo 2ndo, pero si fuese lo 1ero me interesa que amplíes.

Una suposición no te puede llevar a error (Salvo que estés demostrando por reducción al absurdo, pero en ese caso el error es el acierto)
No sé si es reducción al absurdo, te doy un ejemplo: Suponer que en el ajedréz, destruir la reina enemiga es siempre un buen movimiento. Eso llevaría a errores, poco probables pero bue.

---

Está buena la metáfora del saco, eso demuestra que me entendiste. Actualmente estoy pensando en las variaciones que pueda tener la fuerza bruta, pero no hablo de ponerle cosas inteligentes que reduzcan la búsqueda sino por ejemplo saber cuando hay que resetear la situación y cuando no, hay problemas en que no es necesario y otros en que sí, quiero saber exactamente cuando sí y cuando no, y así también para otros pasos extra que pueda tener el método.

Por lo que he pensado, se requiere resetear la situación excepto en estos casos:
- Cuando no hay situación ni se crea.
- Cuando el 1er candidato o 1era acción es la solución.
- Cuando las acciones útiles son reconocibles sin tener que resolver el problema, la lista de candidatos es igual a la serie útil (de acciones, en el orden útil), y no se resetea la acción.

Es bastante inútil, y bastante difícil llegar a esas conclusiones. Aún así me interesa, en otros aspectos no sé si será inútil y difícil.

Ejemplo de "no hay situación ni se crea":
Adivinar un número entero > 0 y < 10 sin que den otras pistas.
La situación (las variables) podría ser el número secreto y el conjunto de los que se han elegido hasta ahora, pero no hay necesidad, el secreto se puede poner en la condición que se chequea:
Si candidato == 9 (suponiendo que sea el 9, sino se pone otro)
y los antes probados son los enteros >0 y <candidato, si el candidato va aumentando de a 1. Es inútil anotar los que fallan. Por otro lado esta variable es la acción, no es parte de la situación.

Ejemplo de "el 1er candidato o 1era acción es la solución":
Mover un personaje un casillero hacia la derecha.
Puse un ejemplo que sí requiere situación, no como el anterior. La nueva posición dependerá de la anterior, y cuando no se halla la solución hay que volver a situaciones anteriores, resetear. Salvo que el 1er candidato sea la solución...

Ejemplo de "las acciones útiles son reconocibles sin tener que resolver el problema, la lista de candidatos es igual a la serie útil, y no se resetea la acción":
Si viste el link, está relacionado con el punto 2. Crear una lista de números enteros >0 y <10. Cuando se agrega un número se puede ver si está bien o no, no hay necesidad de esperar a ver la lista completada para eso. Cuando se agrega el 1, 2, etc en ese orden y se precisa en ese orden no es necesario "volver a la posición anterior" ni nada por el estilo. Pero para que esto suceda la acción no debe resetearse, cosa que normalmente sí ocurre. Por ejemplo, si se quieren adivinar 2 números, cuando se adivine el 1ero deberá resetearse el candidato.

Como he dicho, es bastante inútil todo esto, y encima las palabras que encuentro para describirlo no son muy claras. Es inútil porque:
- El 1er caso, creo que son todos problemas que se pueden resolver en 1 acción, se supone que son fáciles y uno se da cuenta de que no hay que resetear, ni siquiera pasa por la cabeza esa palabra.
- El 2ndo caso es inútil tenerlo en cuenta, si se da la suerte que mencona no hay problema si está especificado el reset, no ocurrirá. Conclusión: Usad el método normal, no vale la pena simplificarlo. Además, si se sabe que la 1er acción es la solución entonces no tiene sentido buscarla.
- Con el 3ero ocurre muy similar al 2ndo.

Parece que en estos 3 casos no hay reset de acciones, tendré que ver si también ocurre en otros, entre otras cosas.

14 Marzo, 2016, 10:01 am
Respuesta #4

elcristo

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,193
  • Karma: +1/-0
  • Sexo: Masculino
Hola.

Citar
mmm... te refieres a que ya está demostrado? Porque yo no lo he demostrado. La suposición es que (X+6=38) = (X=38-6), ya sé que no lo dicen así, pero es que se trata de de que hay una relación entre ecuaciones, es decir se supone que existe esa relación, la supocición no es simplemente sobre 1 ecuación. O sí en el sentido de que cumple cierta propiedad. Sí, nos entendemos, pero quería aclarar.

Si no me equivoco, se puede deducir de los axiomas de Peano. Tenemos dos números naturales, \( x+6=38 \), y por uno de los axiomas, tenemos que dos números naturales con el mismo sucesor son iguales, por tanto: \( (x+6)-1=38-1 \) es decir, el número natural \( (x+6)-1 \) tiene como sucesor al \( x+6 \) y el número \( 38-1 \) tiene como sucesor al \( 38 \), como esos dos números tienen el mismo sucesor, son iguales, así que es cierta la igualdad: \( (x+6)-1=38-1 \), por la propiedad asociativa \( (x+6)-1=x+(6-1)=x+5 \). Repitiéndolo se tiene lo que queremos.

Citar
Eso no lo entendí. ¿Teoremas opuestos (unos dicen sí otros no)? ¿o teoremas referidos a distintos problemas, donde cada teorema dice si es resolvible o no el problema que trata? Supongo que lo 2ndo, pero si fuese lo 1ero me interesa que amplíes.
Creo que no me expliqué bien. Si tienes un teorema que te dice que el problema que tienes con tus hipótesis se puede resolver, suele ocurrir que cambiando esas hipótesis puedas demostrar que el problema no tiene solución. Por ejemplo:

Sea \( f(x)=x^2+ax+b \). ¿Existen soluciones reales para el problema?

Pues tenemos un teorema que nos dice: Si \( a^2-4b\geq{}0 \) entonces hay solución. Por el mismo precio, tenemos el teorema análogo o dual, Si \( a^2-4b<0 \) no existe solución.

Citar
No sé si es reducción al absurdo, te doy un ejemplo: Suponer que en el ajedrez, destruir la reina enemiga es siempre un buen movimiento. Eso llevaría a errores, poco probables pero bue.

Estamos partiendo de la base que la suposición es correcta y útil. Las suposiciones bien hechas no te llevan a error salvo que tú lo hagas mal. Es como decir: Sea \( x=\pi \). Supongamos que \( x \) es un número natural, entonces...

Lo que tú estás haciendo ahí, a grosso modo, es un algoritmo, no la "fuerza buta". Un algoritmo es una descripción de pasos para realizar o resolver un problema. Básicamente estás describiendo un proceso iterativo.

Se nos plantea un problema, no sabemos cómo resolverlo de manera directa ¿Qué hacemos? Un proceso iterativo, a ver si así podemos.

1º- Buscamos un candidato a ser solución.
2º- Estudiamos el candidato ¿Es solución?
3º- Sí, hemos terminado.
3'º- No, volvemos al paso 1.
3''º- No y no hay más candidatos. El problema no tiene solución.

Saludos.