Dudas simples de matemáticas

Aviso desde la moderación a navegantes

Este es el hilo de dudas simples de matemáticas. Lo que se logra preguntando dudas complejas aquí es que otra gente con dudas más sencillas no las transmitan por pensar que pueden quedar en "evidencia" dada la "sencillez" de su pregunta; y nada más lejos de la realidad.

Para algo concreto más allá de lo simple, recomendamos crear un nuevo hilo. Intentemos fomentar que la gente que tenga dudas simples de matemáticas vengan a este hilo. Quienes tengan dudas simples de física a este otro. Y quienres deseen una explicación sencilla de algún fenómeno a este otro. Intentemos hacer de Ciencia un subforo accesible y donde todos sientan que pueden aportar.
B

#60 la "explicacion" intuitiva es que estas cogiendo la funcion zeta de Riemann, extendiendola a donde no esta bien definida de manera analitica, y evaluando en esos puntos xD, donde te queda un limite con una constante mas algo que tiende a 0. No es que sea muy intuitivo pero al menos ves por que la suma de numeros positivos te da un negativo xD.

B

O sea está Dalí y después estas matemáticas O_O.

2
B

up

1 1 respuesta
Mirtor

Manda cojones que se me vayan ocurriendo cosillas durante la semana y cuando llega el lunes la mente en blanco... La próxima vez posteo aunque sepa que vas a tardar

1 respuesta
SupermaN_CK

#63 Se podría poner este thread con chincheta para no tener que subirlo como acabas de hacer, no?

1 respuesta
B

#65 tampoco hay tanto movimiento como para tenerlo siempre arriba... Si a los mods no les molesta, a mi no me importa uppear xD. Tambien lo de #64 , preguntar podeis preguntar cuando querais, pero el unico dia que estoy aqui para responder 100% seguro es el lunes!

D4rKNiGhT

podéis explicar que significa y que es exactamente el tema P=NP??

1 respuesta
B

#67

Este articulo de Scott Aaronson lo explica mejor de lo que yo pueda hacerlo, pero en ingles. Si quieres leete el suyo (mas divulgativo) y el mio (me ha quedado un poco demasiado tecnico), y comenta si algo te falla.

P=NP es un problema emblematico de la computacion teorica. La idea es clasificar los problemas segun su "dificultad" de resolver con un algoritmo. Hay muchas clases de problemas (Co-NP, PSPACE, BQP, etc.) y casi no hay ningun gran teorema resuelto en ninguna de las clases, pero como ya digo, P=NP es lo mas emblematico.

Para empezar, hay que definir lo que es un problema de optimizacion y de decision.

Definimos un problema de optimizacion como una tupla <Iq, Sq, fq, optq> donde:
Iq es el conjunto de instancias posibles (todos los posibles inputs del problema).
Para cada x en Iq (para cada input) Sq(x) es el conjunto de soluciones posibles para ese input.
fq es una funcion definida para cada input y cada solucion posible de ese input.
optq es como vamos a optimizar esa funcion (minimizar o maximizar?).

Asi dado un input x la idea es de todos los y en Sq(x) encontrar el que minimize o maximize (segun optq) fq(x,y).

Un problema de decision es un problema de optimizacion donde fq es 0 o 1. Son problemas del tipo "Existe alguna ruta para la cual este camion consuma menos de X gasolina?" (No hace falta encontrar la mejor ruta!)

Se dice que un problema de decision esta en P si existe un algoritmo que dada cualquier instancia x de Iq que tenga solucion, encuentre y en Sq(x) en un tiempo polinomico en la longitud (en bits) de x, y cualquier instancia x de Iq que no tenga solucion, responda que x no tiene solucion en un tiempo polinomico en la longitud (en bits) de x. Tiempo polinomico quiere decir que el algoritmo hara como maximo, sea cual sea x (siempre y cuando la longitud sea menor o igual que n) una constante multiplicada por n elevado a un numero fijo. Este tipo de problemas son buenos, porque si la longitud de x aumenta un poco, el numero de pasos que hara el algoritmo aumentara de manera controlada. Por ejemplo la multiplicacion de matrices es P (dadas A y B matrices mxm encontrar C = AB).

Se dice que un problema de decision esta en NP si existe un algoritmo tal que para cualquier x una instancia que tenga solucion de Iq existe una h, una "pista" (hint) de longitud acotada por un polinomio funcion de la longitud de x, tal que el algoritmo es capaz de decir en tiempo polinomico si x tiene solucion, y que para cualquier x que no tenga solucion, cualquier pista que le des resultara en una respuesta negativa en tiempo polinomico. Vale, esto es muy lioso dicho asi sin formulas. La idea es realmente "sencilla". Ponle un problema tipico NP, el problema del viajante (lo que he comentado arriba, existe una ruta que pueda seguir este comerciante que le haga gastar menos de x gasolina?). Este problema esta en NP porque si al darle la matriz de puntos y distancias le das como pista una posible ruta es muy facil hacer un algoritmo que te diga si la matriz es correcta o no.

Se dice que un problema esta en P si se puede "resolver rapido", y esta en NP si se puede "comprobar la solucion" rapido.

Como analogia, un algoritmo de este tipo es como un profesor de matematicas muy inteligente. Si tu le traes un teorema y le dices que lo demuestre, quizas no sea capaz de hacerlo. Pero si le traes una demostracion hecha por ti rapidamente te dira si es correcta o no.

Como ves, esta claro que si un problema esta en P entonces tambien esta en NP, ya que si puedes resolverlo rapido cualquier pista que le des sera redundante. La pregunta es, y al reves tambien es asi? Fijate que hay dos preguntas aqui. Una es, "es lo mismo ser NP que ser P?" y la otra es "Como podemos resolver estos problemas NP de manera P?" Hay problemas que son lo que se llama NP-completo, eso es que cualquier problema NP puedes reformularlo y reinterpretarlo como uno de estos problemas. Si fueramos capaces de hacer un algoritmo que resuelva uno de estos problemas en tiempo polinomico, entonces P=NP.

Hay argumentos tanto a favor como en contra de P!=NP. Yo creo que P!=NP y de hecho como dice Scott Aaronson creo que no hay manera de resolver un problema NP-completo en tiempo polinomico usando una cantidad modesta de energia (para evitarnos viajes en el tiempo, irnos a la velocidad de la luz y volver, cosas asi). Pero esto es todo especulacion porque la realidad es que no tenemos suficientes herramientas matematicas como para analizar en profundidad los problemas!

3 1 respuesta
D4rKNiGhT

#68 sobrepasa mis conocimientos de entendimiento.

1 respuesta
B

#69 te lo has leido entero y no has entendido nada de nada o has desistido despues del primer paragrafo? Como has preguntado por una explicacion exacta pensaba que tendrias la base necesaria. Si te interesa el tema como para indagar en el te recomiendo empezar por el articulo en ingles de la wiki, luego un par de papers de Avi Widgerson y Mike Sipser:
http://en.wikipedia.org/wiki/P_versus_NP_problem#Notable_attempts_at_proof
http://www.math.ias.edu/avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf
http://www.eecs.berkeley.edu/luca/cs172-04/sipser92history.pdf

Voy a intentar simplificar, pero ahora ya no es lo que significa exactamente sino una aproximacion, y las sutilezas se pierden:

  • P y NP son tipos de problemas. Queremos algoritmos que a partir de unos datos de entrada (sean los que sean), encuentren una solucion al problema. Por ejemplo somos unos ladrones y tenemos un conjunto de cosas, cada una con un valor, pero no todas caben en la mochila que llevamos encima. Que cosas metemos en la mochila para que el valor total de lo que nos llevamos sea lo maximo posible? Queremos tener un algoritmo (una serie de instrucciones) que nos diga la mejor manera de llenar nuestra mochila cuando nosotros tengamos una lista de cosas y sus valores. Para no liarnos con optimizacion, queremos ser capaces de responder a la pregunta "Podemos llenar la mochila con objetos con un valor total mayor a 400$?"

  • La manera mas obvia de resolver un problema es probar absolutamente todas las soluciones. Asi, un algoritmo para el problema de antes es: Pon todas las cosas que puedas poner en la mochila y apunta el valor. Haz otra combinacion de cosas y vuelve a apuntar el valor. Asi hasta que encuentres una combinacion cuyo valor supere 400$, o las hayas probado todas y ninguna lo supere.

  • El problema de este tipo de solucion (fuerza bruta) es que si en lugar de 8 cosas tienes 9, el numero de pruebas que tienes que hacer crece muchisimo, hasta el punto de que con 200 cosas quizas no tengas tiempo suficiente en la historia del universo para probarlas todas. Asi que quieres encontrar* estrategias mas eficientes, mas rapidas, que no crezcan tan rapido con el numero de cosas.

  • Los problemas para los cuales hemos encontrado estas instrucciones mas simples que hacen como un "atajo" respecto a probar todo son los que llamamos P. Un ejemplo de problema de este tipo es saber si un numero es primo o no (esto se descubrio en 2002). La manera "bruta" de saberlo es probar a dividir por todos los numeros menores, pero hay una manera mas refinada que resuelve mas rapido.

  • Hay problemas para los que no sabemos encontrar una manera simple de resolverlos, pero si que podemos comprobar rapidamente si una solucion es correcta. Por ejemplo si yo te digo "prueba a meter estas cosas en la mochila" tu rapidamente me puedes decir si su valor supera los 400$ o no. Este tipo de problemas son los NP (completo).

  • La pregunta es: Hay alguna manera de resolver rapidamente estos problemas que podemos comprobar? Si existiera entonces tendriamos NP=P y muchos ingenieros logisticos/arquitectos de computadores contentisimos.

7 3 respuestas
D4rKNiGhT

#70 Ahora si que si!! mil gracias, siempre me quedaba la gran duda de que era NP=P, en especial en matematica discreta.

1 1 respuesta
sacker

#70 eres muy muy grande (por esa explicación en concreto y por todo el hilo)

spoiler

a todo esto, me hacéis tener pesadillas y sudores fríos recordando las asignaturas de lógica y cálculo de la carrera

2 1 respuesta
Mirtor

Bien, lo de P=NP era lo que quería preguntar yo xDDD

urrako

#70 Este problema por lo que describes me recuerda a teoría de la demostración e incluso diría investigación operativa. ¿Hasta qué punto se relacionan ambas áreas con el de la complejidad y en concreto con p=np?

1 respuesta
B

#71 me alegro de haber ayudado!
#72 jaja gracias por la indicacion! Hostia ni me di cuenta xD.

#74 la mayoria de problemas con los que trabajas en teoria de la computacion son de naturaleza discreta y de optimizacion. Discreta porque los ordenadores son maquinas discretas y finitas, y de optimizacion porque son los problemas que mejor entendemos y los mas utiles a la vez.

La clase de problemas NP-completo (aquellos problemas que son NP y que ademas todo problema NP se puede reinterpretar como una version de este) son en su mayoria de este tipo (optimizacion combinatoria). Pero hay uno que se relacionaria con teoria de la demostracion que es el problema SAT (Satisfactibilidad booleana, i.e. saber si una formula de logica proposicional es satisfactible o no). Ese es basicamente el "mejor" problema NP-completo porque es en cierto modo el menos rigido. Al menos yo lo veo asi.

Por otro lado "evolutivamente" hablando, la teoria de la complejidad computacional fue creciendo a partir de la teoria de decidibilidad y maquinas de Turing (tema del que no tengo ni idea xD) y del trabajo de Godel, Church, Curry, Turing, etc.

B

up

2 respuestas
Eyvindur

#76 Ya podrían poner un botón de up como en el foro compra-venta.

1 respuesta
B

Ya te lo upearé yo Duronman cuando me acuerde.

P.D: ahora entiendo porque los mejores filósofos (o los que más me gustan) son los matemáticos. Madre de Dios O_O. Creo que tardaría años en entender el post de P=NP.

1 respuesta
Ulmo

#76 #77 #78 He creado un hilo con chincheta para recopilar todos los hilos de consultar dudas sobre materias concretas, así que no hace falta que vayais subiendo constantemente todos los hilos del estilo.

A ver si de esta forma logramos que no pierdan en el olvido.

3
11 días después
J

Quizá esto no sea una duda simple, pero bueno, la dejo por aquí y si Duronman cree más conveniente contestarme por privado, que así sea. La pregunta está especialmente enfocada a la probabilidad y a teoría de la medición en general:

Estoy estudiando probabilidad de manera autodidacta (la dejé en 4º ESO o 1º bachiller, no recuerdo bien, después la retomé en la carrera de forma muy muy parca y simple en una asignatura) ya que es un campo que siempre me ha fascinado e interesado. Desde que leí a Taleb, más todavía xD

La cosa es que estoy empezando por el principio, por absurdo que parezca (intersecciones, uniones de sucesos, etc.) y al principio del manual que estoy siguiendo, me aparece lo siguiente:

1: https://gyazo.com/48d65e2e425b1c05051f03787c6e0ce2
2: https://gyazo.com/b86bfc801cc35b37d8358c6f09e955aa

No entiendo a que se refiere con "familia de conjuntos A definida sobre ­­Ω" y mucho menos que es una σ-álgebra. Esta parte sin duda va un paso por delante, no obstante es como un pequeño inciso, el manual continúa con cosas básicas después de eso.

1 respuesta
B

#80 vaya ejemplo que ponen hijo, la sigmaalgebra de Borel es muy dificil... Basicamente esta familia de conjuntos no es mas que un subconjunto de (P(Omega)) (el conjunto de todos los subconjuntos posibles de (\Omega)) Vamos a poner un ejemplo mas sencillo. Si (\Omega)) es {1,2,3,4,5,6} (los resultados posibles al tirar un dado), una familia de subconjuntos de (\Omega)) puede ser {o,{1,3,5},{2,4,6},{1,2,3,4,5,6}} (comprueba que sigue las propiedades de una sigma-algebra). En cambio {o,{1,2},{3,4},{5,6}} no lo es, porque no tiene complementarios ni el conjunto completo. Basicamente este concepto sirve para definirte bien una probabilidad, de manera que la probabilidad de (\Omega)) (es decir, que pase cualquiera de las cosas que puede pasar) sea 1, y luego el resto siga la regla de Laplace (casos favorables/casos posibles). De esta manera puedes formalizar casos donde (\Omega)) es infinita contable o no contable.

2 1 respuesta
J

Mucho más claro Duronman, ¡muchísimas gracias!

1
spyro512

#81 te pido opinión personal: en teleco deberíamos saber qué es una sigma álgebra de Borel y tanta artillería de probabilidad? En mi uni hacen bastante énfasis en todo esto, y sinceramente no lo veo tan trivial

1 respuesta
B

#83 depende de lo que vayas a hacer. Si quieres meterte en comunicaciones opticas por ejemplo, tienes procesos estocasticos y tienes que saber lo que es una sigmaalgebra adaptada, una filtracion del proceso, etc. para entender bien lo que haces. Si haces codificacion de video o teoria de codigos cada vez mas tambien, porque se usan tecnicas muy avanzadas para acercarse a los limites teoricos de compresion... Pero si te llaman otras cosas como antenas y tal pues no hace tanta falta.

1 1 respuesta
KooPad

#84 Tengo una duda sobre el principio de sustitución, intento demostrar la ley de disyunción de morgan a partir de la conjunción y la doble negación, pero me quedo encallado:

Quiero demostrar que ¬(AvB)=(¬A)¬B):
1) Para empezar niego dos veces cada letra proposicional:

¬(AvB)=> ¬(¬(¬A)v¬(¬B))

2) Como relaciono ahora esto con la ley de la conjunción? :O

1 respuesta
Millonet1

#85 Aquí tienes esa demostración junto a otras muchas (pg 7.): http://pendientedemigracion.ucm.es/info/pslogica/derivadas.pdf

1 respuesta
KooPad

#86 Ya he consultado esta fuente pero no acabo de entender que hacer a partir de lo que he hecho al principio :qq:

1 respuesta
Millonet1

#87 ¿Conoces las abreviaturas? I/EC=Introducción/eliminación de la conyunción I/EN=Introducción/eliminación de la negación y ED=Eliminación de la disyunción.
Es un juego de manos, en wikipedia tienes una demostración mas intuitiva con conjuntos, igual te sirve.
O si no siempre puedes hacer una tabla de verdad :si:

PD: Te gusta la lógica?

1 respuesta
KooPad

#88 Me lo tengo que mirar más a fondo, ya que quiero sacarlo de este método porque con TdV es muy fácil. Es de la carrera :D
Gracias!

1 respuesta
Millonet1

#89 A ver si lo explico bien y a la vez sin cagarla con el rigor:

1- AvB (Nuestra premisa)
2-Introducimos ¬A¬B
2.1 ¬A
2.2 ¬B
3- ¬A->B ( por 1) y por lo tanto B¬B (por 2.2).
4- Como (3) es una contradicción tenemos ¬¬A y por lo tanto A.
Por 2.1 y 4 tenemos A¬A, otra contradicción, por lo que ¬(2), es decir: ¬(¬A¬B)

Luego hay que hacer la inversa, pero es igual.

1 respuesta