Mostrar Mensajes

Esta sección te permite ver todos los posts escritos por este usuario. Ten en cuenta que sólo puedes ver los posts escritos en zonas a las que tienes acceso en este momento.

Temas - martiniano

Páginas: [1] 2 3
1
Topología (general) / Demostrar que una función no es continua.
« en: 28 Septiembre, 2020, 12:38 pm »
Hola, buenas.

Estoy estudiando algo de topología y tengo una duda. Me gustaría demostrar, según la definición topológica de continuidad, que la siguiente función \( F:\mathbb{R\times{R\longrightarrow{R}}} \) no es continua:

\[ F(x\times{y})=\begin{cases}{xy/(x^2+y^2)}&\text{si}& x\times{y}\neq0\times{0}\\ 0 & \text{si}& x\times{y}=0\times{0}\end{cases} \]

Yo lo que he pensado es que la antiimagen del abierto \[ \left(-\frac{1}{4},\frac{1}{4}\right)  \] es el conjunto \[ A=\{(x, y) \in{\mathbb{R^2}}:x^2+y^2+4xy>0\wedge x^2+y^2-4xy>0\}\cup{}\{(0, 0) \} \].

Al ser \[ A \] la unión de una región abierta delimitada por cuatro rectas que pasan por el origen con el mismo origen, su complementario no contiene el origen, pero la adherencia del complementario sí. Luego el complementario de \( A \) no es cerrado y \( A \) no es abierto.

Mi duda es que no tengo del todo claro que sea ésta la justificación que se esperaba en cuanto a que \[ A \] no es abierto.

Por otro lado, después de darle vueltas a esto, me mosqueó un poco que el ejercicio tuviera dos apartados previos. Me da la sensación de que este último apartado sobre la no continuidad de \( F \) se pretendía resolver con sus resultados. Esos dos apartados son:

A) Pruebe que \( F \) es continua en cada variable separadamente.

B) Calcule  \[ g:\mathbb{R\longrightarrow{R}} \] dada por \( g(x) =F(x\times{x})  \)

Con estos dos apartados creo que no he tenido problemas. Lo que sucede es que tiene pinta que la no continuidad de \( g(x)=F(x\times{x})  \) implica la no continuidad de \( F \). Pero no parece que este resultado sea más sencillo de probar que demostrar que \( A \) no es abierto... ¿Qué opináis sobre todo esto?

Agradezco anticipadamente cualquier tipo de comentario.

Un saludo.

2
Hola.


Viene de: https://foro.rinconmatematico.com/index.php?topic=114307.msg452620#msg452620


Con ánimo de echar una mano voy a expresar una posible respuesta en la que no se hable de sucesiones y subsucesiones a ver si sirve de algo.

Se trata de  probar:

Sea    \( f:[a,b]\longrightarrow{\mathbb{R}} \)    continua. Supongamos que:

 para cada    \( x\in{[a,b]} \)    hay algún    \( y\in{[a,b]} \)    tal que \( \Big|f(y)\Big|\leq{\displaystyle\frac{1}{5}\Big|f(x)\Big|} \). (H)

Entonces   \( f \)    se anula en algún punto de    \( [a,b] \).



Lo demostraré por reducción al absurdo. Supongamos que el enunciado es falso y que por tanto existe una función \( f(x)  \) que cumple las condiciones del enunciado pero que no se anula en \( [a, b] \). Si \( f(x)  \) es continua en \( [a, b]  \) también lo es \( |f(x) | \) y por el teorema de Weierstrass ésta debe alcanzar su mínimo en \( [a, b]  \). Supongamos que el mínimo se da en \( m\in{[a, b] } \). Como \( f(x)  \) no se anula tampoco lo hace \( |f(x) | \) y deberá ser \( |f(m) |>0 \). Pero por una de las condiciones del enunciado existe \( y \) tal que \( |f(y) |\leq{}\frac{|f(m) |}{5}<|f(m)| \) con lo que el mínimo no estaría en \( x=m \) y eso es absurdo.

No quisiera estar liando la madeja, pero pienso que si a lo mejor Buscón entendiese una demostración después le sería más sencillo entender las otras. De no cumplir este mensaje su cometido puede ser ignorado sin más.

Un saludo.

3
Topología (general) / Topologías producto y por cajas
« en: 07 Septiembre, 2020, 12:11 pm »
Hola.

Tengo el siguiente enunciado que he sacado del Munkres. En la sección correspondiente se habla de la topología por cajas y de la topología producto. También llama \( \mathbb{R^{\omega}} \) al conjunto de sucesiones de números reales.

Dadas las sucesiones \( (a_1,a_2,...) \) y \( (b_1,b_2,...) \) de números reales con \( a_i>0 \) para todo \( i \), definamos \( h:\mathbb{R^{\omega}\rightarrow{}R^{\omega}} \) mediante la ecuación:

\[ h((x_1,x_2,...))=(a_1x_1+b_1,a_2x_2+b_2,...), \]

Pruebe que si \( \mathbb{R^{\omega}} \) está dotado con la topología producto, \( h \) es un homeomorfismo de \( \mathbb{R^{\omega}} \) con sigo mismo. ¿Qué ocurre si \( \mathbb{R^{\omega}} \) está dotado con la topología por cajas?


Lo que he hecho es primero notar que:

\[ h^{-1}((x_1,x_2,...))=(\frac{1}{a_1}x_1-\frac{b_1}{a_1},\frac{1}{a_2}x_2-\frac{b_2}{a_2},...), \].

Y que si \( U \) es un abierto básico de \( \mathbb{R^{\omega}} \) en la topología por cajas entonces es de la forma \( U=U_1\times{}U_2\times{...} \) donde \( U_i \) es un abierto de \( \mathbb{R} \). Entonces la imagen de un abierto básico por \( h \):

EDITADO
\[ h(U)=h(U_1\times{}U_2\times{...})=(a_1U_1+b_1)\times{}(a_2U_2+b_2)\times{}... \]

Es un abierto ya que \( a_iU_i+b_i \) es un abierto de \( \mathbb{R} \), al menos en la topología usual.

EDITADO
Al transformar elementos básicos en abiertos, transforma abiertos en abiertos, ya que cualquier abierto es unión de elementos básicos y su imagen será la unión de las imágenes de esos elementos básicos y por tanto también un abierto. Con \( h^{-1} \) pasa parecido y también transforma abiertos en abiertos. Como \( h \) transforma abiertos en abiertos \( h^{-1} \) es continua y viceversa, con lo que \( h \) es homeomorfismo si dotamos a \( \mathbb{R^{\omega}} \) de la topología por cajas. Si lo dotamos de la topología producto también lo es. Sólo hay que modificar un poco la demostración haciendo que a partir de un cierto \( n \), es decir para todo \( m>n \), tiene que ser \( U_m=\mathbb{R} \), con lo que la imagen de un abierto básico queda de la forma \( (a_1U_1+b_1)\times{}...\times{}(a_nU_n+b_n)\times{}\mathbb{R}\times{}\mathbb{R}\times{}\mathbb{R}\times{}... \), que vuelve a ser un abierto en la topología producto. Lo mismo con \( h^{-1} \).

Ocurre que tengo la sensación de estar liándola porque el libro dedica la sección a intentar dejar patente las diferencias entre la topología por cajas y la topología producto, y en el resultado al que he llegado no hay diferencia entre ellas. ¿Qué os parece?

Agradezco de antemano cualquier tipo de comentario. Un saludo.

4
Hola. Tengo el siguiente enunciado:

Sea \( X  \) un conjunto ordenado en la topología del orden. Muestre que \[  \overline{(a,b)}\subseteq{[a,b]} \]. ¿Bajo qué condiciones se cumple la igualdad?

La primera parte creo que ya la tengo hecha. Por reducción al absurdo:

Supongamos que existe \( c\not\in{}[a,b] \) que cumple \( c\in{\overline{(a,b)}} \). Entonces, al ser la relación de orden total tiene que ser \( c<a \) o \( b<c \). Supongamos \( c<a \). Nuevamente, al ser la relación de orden total, \[ c \] no puede ser minimal sin ser el mínimo, por lo que o bien es mínimo y el abierto \( [c,a) \) contiene a \( c \) y no corta a \( (a,b) \) o bien existe un \( d \) tal que \( d<c \) y el abierto \( (d,a) \) contiene a \( c \) y no corta a \( (a,b) \). En cualquier caso, hemos encontrado un entorno de \( c \) que no corta a \( (a,b) \) por lo que \( c\not\in{}\overline{(a,b)} \) y esto es contradictorio. Si \( b<c \) se llega a una contradicción de forma similar.

En cuanto a la pregunta de después, entiendo que se cumple la igualdad si y sólo si la relación de orden cumple que para todos \( a,b\in{X} \) existe un \( c\in{X} \) tal que \( a<c<b \). Esta propiedad de las relaciones de orden, ¿tiene algún nombre concreto?

Gracias, y un saludo.

5
Dudas y sugerencias del foro / Tamaño máximo de archivos adjuntos
« en: 16 Agosto, 2020, 06:55 pm »
Hola.

Estoy intentando subir al foro una imagen en formato jpg que pesa algo más de 6 megas. La verdad es que no sé si eso es mucho o poco para una imagen pero parece que no puedo hacerlo. No es que me salga un mensaje que diga que no se pueda ni nada de eso, simplemente se queda el navegador en blanco y no avanza (tanto el chrome como el safari).

¿Hay un tamaño máximo para los archivos adjuntos o algo así o pensáis que puede ser otra cosa la que está sucediendo?

Gracias. Un saludo.

6
Hola.

Recuerdo un teorema que decía algo así como que:

Dada una biyección entre los puntos de dos rectas que conserva la razón doble, el lugar geométrico de las rectas que unen cada punto de una de las rectas con su imagen en la otra es un hiperboloide de una hoja. Si la aplicación conserva además la razón simple, entonces el lugar es un paraboloide hiperbólico.

He buscado este teorema entre mis apuntes pero no lo he encontrado. ¿Alguien conoce un texto dónde aparezca este teorema y, si es posible, su demostración?

Gracias de antemano.

7
Teoría de Juegos / Equilibrio bayesiano de Nash
« en: 19 Julio, 2020, 12:17 pm »
Hola.

Ha llegado a mí un curso de teoría de juegos que me gustaría completar. La verdad es que el material es fácil de seguir y parece estar, en general, bien concebido. El último tema se llama Juegos estáticos con información incompleta y en el desarrollo del tema va poniendo ejemplos de juegos para dos jugadores en los que al menos uno ellos desconoce cuál es el estado de la naturaleza. Uno de ellos ilustra el apartado Juegos bayesianos con muchas estrategias, cuyo enunciado es el siguiente:

Consideremos un juego en el que dos empresas deciden simultáneamente qué cantidad de dinero invierten en publicidad. Llamemos \( s_1 \) y \( s_2 \) a las respectivas cantidades de dinero invertidas. La función de beneficios de la que llamaremos empresa 1 es conocida por ambas empresas y es:

\( \pi_1(s_1,s_2)=1000s_1-s_1s_2-s_1^2 \)

Sin embargo, la función de beneficios de la empresa 2 sólo es conocida por esta empresa. La empresa 1 sabe que la función de beneficios de la empresa 2 será:

\( \pi_2(s_1,s_2)=1000s_2-s_1s_2-\alpha s_2^2 \)

con probabilidad \( \theta \) o:

\( \pi_2(s_1,s_2)=1000s_2-s_1s_2-\beta s_2^2 \)

con probabilidad \( 1-\theta \). En el primer caso diremos que la empresa 2 es de tipo I mientras que en el otro diremos que es de tipo II.

Hallar los equilibrios bayesianos de Nash en estrategias puras del juego.

Tener en cuenta que la empresa 2 debe especificar qué hará en caso de tener la primera función y qué hará en caso de tener la segunda. En cambio la empresa 1 deberá elegir una sola inversión, que deberá ser la mejor respuesta al valor esperado de la estrategia seguida por la empresa 2


El último párrafo está prácticamente tal cual en el texto y a mí me parece muy lógico. Resulta que la solución que el mismo texto ofrece no parece, si no se me está escapando nada, ser demasiado coherente con este último párrafo. Dicha solución comienza así, y con este comienzo estoy de acuerdo:

Dada una cantidad \( s_1 \), la empresa 2 jugará a maximizar su función de beneficios, es decir invertirá:

\( s_{2a}=\frac{1000-s_1}{2\alpha} \) si es de tipo I y:

\( s_{2b}=\frac{1000-s_1}{2\alpha} \) si es de tipo II.

Y ahora viene la parte en la que no estoy tan de acuerdo. Dice que para maximizar su función beneficio la empresa 1 debe jugar \( s_1=\frac{1000-s_2}{2} \) y substituye aquí \( s_2=\theta s_{2a}+(1-\theta)s_{2b} \), es decir, \( s_2 \) por su valor esperado, y resuelve el sistema de tres ecuaciones con tres incógintas: \( s_{2a} \), \( s_{2b} \) y \( s_{1} \). El texto aporta la solución para el caso concreto \( \alpha=2 \), \( \beta=1 \) y \( \theta=0.5 \), que es \( s_1=384.6 \), \( s_{2a}=153.8 \) y \( s_{2b}=307.6 \)

No estoy de acuerdo en que la decisión de la empresa 1 así tomada maximice su beneficio esperado. A mí me parece más lógico calcular el beneficio esperado para la empresa 1 teniendo en cuenta las respuestas óptimas de la empresa 2 a cada estado de la naturaleza para obtener una función que sólo dependa de \( s_1 \)

\( E(s_1)=\theta\pi_1\left(s_1,\frac{1000-s_1}{2\alpha}\right)+(1-\theta)\pi_1\left(s_1,\frac{1000-s_1}{2\beta}\right)=s_1^2\cdot{}\frac{\beta\theta -\alpha\theta+\alpha-2\alpha\beta}{2\alpha\beta}+s_1\cdot{}\frac{-1000\theta\beta+2000\alpha\beta-1000\alpha+1000\alpha\beta}{2\alpha\beta} \)

El máximo de esta función se obtiene para \( s_1=500 \) y substituyendo en las primeras ecuaciones se tiene \( s_{2a}=\displaystyle\frac{250}{\alpha} \) y \( s_{2b}=\displaystyle\frac{250}{\beta} \).

Aquí pasa algo raro...

¿Alguien tiene algún comentario iluminador? Agradezco de antemano cualquier aporte.

Saludos.

8
Hola, ¿qué tal?

Abro este hilo para continuar una conversación que comenzó en este otro y que voy a desviar bastante del tema del hilo original.

El objetivo del hilo es aclarar algún que otro concepto sobre normas y los diferentes espacios en las que están definidas.

Primero de todo voy a ir poniendo conceptos básicos que he ido encontrando por internet:

Dado un espacio vectorial \( V \) sobre un cuerpo \( K \) se dice que una operación \( \left\|{·}\right\|:V\rightarrow{\mathbb{R}} \) es una norma si para todos \( x,y\in{V} \) y todo \( \lambda\in{K} \) cumple las condicines siguientes:

EDITADO
\( \left\|{x}\right\|\geq{0} \)
\( \left\|{x}\right\|=0\Leftrightarrow{}x=0 \)
\( \left\|{x+y}\right\|\leq{\left\|{x}\right\|}+\left\|{y}\right\| \)
\( \left\|{\lambda x}\right\|={\left |{\lambda}\right |}\left\|{x}\right\| \)

Supongo que en el cuerpo \( \mathbb{K} \) tiene que haber definida una operación valor absoluto o módulo \( |·| \) que también cumpla una serie de condiciones, quizás que sea una norma. Supongo que esto se puede hacer porque \( \mathbb{K} \) es un espacio vectorial sobre \( \mathbb{K} \)

A un espacio vectorial en el que hay definida una norma se le llama espacio normado.

Bien. Tenemos que si en un espacio vectorial tenemos definido un producto escalar \( \cdot{} \), podemos definir a partir de él una norma \( \left\|{x}\right\|=\sqrt[ ]{x\cdot{x}} \). Se puede comprobar a partir de la definición de producto escalar que la operación así definida cumple las condiciones para ser norma. Luego todo espacio euclídeo es también automáticamente un espacio normado. El recíproco no es, en general, cierto.

Por otro lado, si tenemos dos espacios normados \( U,V \), se puede definir una norma inducida sobre el conjunto de aplicaciones lineales continuas entre ellos de la siguiente manera. Sea \( f:U\rightarrow{V} \) una de estas aplicaciones, entonces la operación \( \left\|{f}\right\|=\sup_{x\neq0}{\frac{\left\|{f(x)}\right\|}{\left\|{x}\right\|}}=\sup_{\left\|{x=1}\right\|}{\left\|{f(x)}\right\|} \) cumple las tres condiciones para ser norma. Aquí es donde se genera todo lo de las normas matriciales y la teoría en cuyo marco está el ejercicio que motivó esta conversación.

Hasta aquí creo que bien. Lo que viene a continuación lo tenía confundido. Pensaba que a los espacios con una norma definida se les llamaba de Banach, pero veo que no es así.

En un espacio vectorial normado sobre \( \mathbb{R} \), una sucesión de Cauchy es una sucesión que cumple que para todo \( \epsilon >0 \) existe un entero \( N \) tal que para todos \( n,m>N \) \( \left\|{x_n-x_m}\right\|<\epsilon \)

Un espacio de Banach es un espacio normado en el que toda sucesión de Cauchy es convergente. Por ejemplo \( \mathbb{Q} \) con el valor absoluto no es un espacio de Banach, ya que en \( Q \) hay sucesiones de Cauchy que no convergen a un número racional. Sin embargo \( \mathbb{R} \) y \( \mathbb{C} \) con el módulo sí que lo son. Así un espacio de Banach puede tener dimensión finita o infinita.

Un espacio de Hilbert es, básicamente, un espacio de Banach en el que la norma es inducida por un producto escalar. Pensaba yo que un espacio de Hilbert tenía que tener dimensión infinita pero parece ser que no tiene porqué.

También tenemos que toda norma induce una distancia \( d(x,y)=\left\|{x-y}\right\| \), por tanto todo espacio normado \( X \) es automáticamente un espacio métrico, y que toda distancia induce una topología, luego todo espacio métrico también es un espacio topológico. Los recíprocos no son, en general, ciertos.

¿Voy bien con todo esto?

Muchísimas gracias. Un saludo.

9
Ejercicios - Exámenes - Apuntes / Relojes de Sol
« en: 01 Junio, 2020, 09:40 am »
Hola.

El otro día buscando una cosa entre mis papeles me topé con unos apuntes míos sobre relojes de Sol. Hablan de los principales tipos de relojes de Sol (hay muchísimos tipos más) y un poco de la teoría que hay que manejar para diseñar ciertas líneas que pueden aparecer en un reloj de Sol.

Pienso que puede interesar a gente aquí en el foro ya que esto de los relojes de Sol puede ser un recurso interesante a nivel pedagógico, entre otras cosas. Es relativamente sencillo construir uno en el suelo o en una pared y es una actividad en la que pueden participar chavales de todas las edades.

Los apuntes no hablan de aspectos constructivos, pero con la tontería ya he ido haciendo alguno que otro y si a alguien le interesa algún consejo me puede preguntar. En internet también hay mucha información sobre el tema.

Aquí están. Un saludo.

10
Problemas resueltos / Identidad trigonométrica
« en: 07 Mayo, 2020, 06:57 pm »
Hola.

Quiero subir aquí una identidad trigonométrica que a mí me resultó sorprendente bastante sorprendente. Me la conjeturé a mí mismo mientras le daba vueltas a este problema y acabé encontrando una demostración que comparto un poco más abajo. Quisiera saber si alguien de vosotros conoce esta identidad y alguna otra demostración, ya que en tal caso me gustaría compararlas. La identidad en cuestión es la siguiente:

Sea \( n  \) un entero \( n\geq{1} \). Entonces para \( k\in{}\{0,...,n\} \) se cumple:

\( \displaystyle\prod_{\substack{i=0\\i\neq{k}}}^{n}{\left |{\cos\left(\displaystyle\frac{k\cdot{}\pi}{n}\right)-\cos\left(\displaystyle\frac{i\cdot{}\pi}{n}\right)}\right |}=\begin{cases} \displaystyle\frac{n}{2^{n-2}} & \text{si}& k\in{\{0,n\}}\\\displaystyle\frac{n}{2^{n-1}} & \text{si}&  k\in{\{1,...,n-1\}}\end{cases} \)


Spoiler
Llamaré \( T_m(x) \) y \( U_m(x) \) a los polinomios de Chebyshev de primera y segunda especie respectivamente. Utilizaré las siguientes propiedades de los mismos:
  • U_m(x) tiene grado \( m \) y su coeficiente de mayor grado es \( 2^m \).
  • Los ceros de \( U_m(x) \) son \( \cos\left(\displaystyle\frac{k\pi}{m+1}\right) \) con \( k\in{}\{1,...,m\} \)
  • Para todo entero \(  i \) se cumple \( T_m\left(\cos\left(\displaystyle\frac{i\pi}{m}\right)\right)=(-1)^i \)
  • \( U_m(1)=m+1 \)
  • \( U_m(-1)=(-1)^m\cdot{}(m+1) \)
  • \( \displaystyle\frac{dU_{m-1}}{dx}=\displaystyle\frac{m\cdot{T_m(x)}-x\cdot{}U_{m-1}(x)}{x^2-1} \)

Consideremos el polinomio:

\( p(x)=2^{n-1}\displaystyle\prod_{i=0}^{n}{\left(x-\cos\left(\displaystyle\frac{i\pi}{n}\right)\right)} \)

Que es el mismo polinomio que el siguiente, ya que ambos tienen los mismos ceros, el mismo grado y el mismo coeficiente de mayor grado:

\( p(x)=(x^2-1)\cdot{}U_{n-1}(x) \)

Entonces, derivando la primera expresión, substituyendo \( x=cos\left(\displaystyle\frac{k\pi}{n}\right) \) con \( k \in{\{0,...,n\}} \) y tomando valor absoluto tenemos que:

\( \left |{p'\left(\cos\left(\displaystyle\frac{k\pi}{n}\right)\right)}\right |=2^{n-1}\displaystyle\prod_{\substack{i=0\\i\neq{k}}}^{n}{\left |{\cos\left(\displaystyle\frac{k\cdot{}\pi}{n}\right)-\cos\left(\displaystyle\frac{i\cdot{}\pi}{n}\right)}\right |} \)

Por otro lado, derivando la segunda expresión:

\( p'(x)=2x\cdot{}U_{n-1}(x)+(x^2-1)\cdot{}\displaystyle\frac{n\cdot{T_n(x)}-x\cdot{}U_{n-1}(x)}{x^2-1}=x\cdot{U_{n-1}(x)}+n\cdot{T_{n}(x)} \)

Por lo que, con la ayuda de las propiedades de antes:

\( |p'(1)|=|p'(-1)|=2n \)

Con esto ya tenemos la demostración del enunciado para \( k\in{\{0,n\}} \). En otro caso, es decir para \( k\in{}\{1,...,n-1\} \), tenemos que:

\( \left |{p'\left(\cos\left(\displaystyle\frac{k\pi}{n}\right)\right)}\right |=\left |\cos\left(\displaystyle\frac{k\pi}{n}\right)\cdot{}\underbrace{U_{n-1}\left(\cos\left(\displaystyle\frac{k\pi}{n}\right)\right)}_{0}+n\cdot{}T_n\left(\cos\left(\displaystyle\frac{k\pi}{n}\right)\right)\right |=|(-1)^k\cdot{}n|=n \)

Y con esto último el enunciado para el resto de casos.
[cerrar]

Un saludo.

11
Hola buenas.

Resulta que discutiendo un tema de física en este hilo nos ha surgido de forma un tanto inesperada un problema sobre la validez de un modelo que básicamente se reduce a lo siguiente. Abro un hilo nuevo para que se pueda entender el problema sin tener ni idea de física y para que se pueda participar en él sin necesidad de leer todo el otro hilo.

Dados dos números reales \( L \) y \( C \), decidir si existen un único número real Q y una única función \( \lambda:(-L/2,L/2)\longrightarrow{\mathbb{R}} \) tales que para todo \( a\in{(-L/2,L/2)} \) se cumplen las dos igualdades siguientes:

\( \lambda(-a)=-\lambda(a) \)

\( \displaystyle\frac{Q}{(L/2+a)^2}+\displaystyle\frac{Q}{(L/2-a)^2}+\displaystyle\int_{-L/2}^{a}\displaystyle\frac{\lambda(x)}{(a-x)^2}\,dx-\displaystyle\int_{a}^{L/2}\displaystyle\frac{\lambda(x)}{(a-x)^2}\,dx=C \)


La verdad es que no sé cómo abordar el problema. Ni si quiera sé qué rama de las matemáticas se encarga de este tipo de problemas. ¿Alguien podría iluminarnos un poco?

Si la respuesta al problema fuese afirmativa, y efectivamente existiesen ese \( Q\in{\mathbb{R}} \) y esa función \( \lambda \) el objetivo pasaría a ser hallarlos para ciertos valores de \( L \) y \( C \) mediante técnicas numéricas, ya que analíticamente parece imposible, ¿o qué opináis?

Gracias y un saludo.

12
Problemas resueltos / Cable de longitud mínima
« en: 03 Noviembre, 2019, 09:20 am »
Hola a todos y a todas.

Me dispongo a subir un problema resuelto que a mí me llama mucho la atención y que se me pide que resuelva bastante a menudo. Lo subo al foro para tenerlo yo fácil a la hora de enlazarlo y para compartirlo con sus usuarios.

Va especialmente dirigido a alumnos de segundo de bachillerato, ya que es el curso en el que más veces aparece este problema y en el que más quebraderos de cabeza causa. Tal vez sea porque las herramientas que se ven en dicho curso suelen llevar a una solución un tanto aparatosa para lo que podría haber sido. Cuando lo tiene resuelto, al alumno de segundo de bachillerato le sorprende saber que el mismo problema se propone en tercero de ESO en un tema bastante inocente, que pocas veces se ve, y que introduce lo que son las traslaciones, rotaciones, homotecias y simetrías en el plano. Por último, también podría aparecer en un curso de nivel universitario para ser resuelto mediante el método de los multiplicadores de Lagrange.

Las tres soluciones que me dispongo a comentar corresponden a cada uno de los niveles de los que he hablado en el párrafo anterior. Las he ordenado en orden inverso a cómo recomendaría yo a alguien resolver el problema si no se indicase expresamente ningún método concreto. Allá va el enunciado del problema:

Una torre vertical de altura 25 metros se encuentra a una distancia de 32 metros de otra torre también vertical de 15 metros de altura. Se pretende unir sus cimas mediante un cable que debe tocar el suelo en uno de sus puntos tal y como muestra el dibujo:



Considerar que cada tramo de cable es recto. Calcular a qué distancia de la primera torre debe producir el contacto entre el cable y el suelo para que la longitud del cable sea mínima.

Lo que planteáis la mayoría de estudiantes de segundo de bachillerato es lo siguiente:

Solución 1


Sea \( x \) la distancia buscada y \( L_1 \) y \( L_2 \) las longitudes de los dos tramos de cable. Entonces, aplicando el teorema de Pitágoras a los triángulos \( ACD \) y \( BED \) tenemos que la longitud de cada tramo de cable es:

\( L_1=\sqrt[ ]{x^2+25^2}=\sqrt[ ]{x^2+625} \)

\( L_2=\sqrt[ ]{(32-x)^2+15^2}=\sqrt[ ]{1024-64x+x^2+225}=\sqrt[ ]{x^2-64x+1249} \)

Y la longitud total del cable, que es la función a minimizar:

\( f(x)=\sqrt[ ]{x^2+625}+\sqrt[ ]{x^2-64x+1249} \)

Observar que la función es continua y derivable en todo \( \mathbb{R} \). Su derivada:

\( f'(x)=\displaystyle\frac{2x}{2\sqrt[ ]{x^2+625}}+\displaystyle\frac{2x-64}{2\sqrt[ ]{x^2-64x+1249}}=\displaystyle\frac{x}{\sqrt[ ]{x^2+625}}+\displaystyle\frac{x-32}{\sqrt[ ]{x^2-64x+1249}} \)

Para que valga cero:

\( \displaystyle\frac{x}{\sqrt[ ]{x^2+625}}=-\displaystyle\frac{x-32}{\sqrt[ ]{x^2-64x+1249}} \)  quitando denominadores:

\( x\sqrt[ ]{x^2-64x+1249}=(32-x)\sqrt[ ]{x^2+625} \)  elevando al cuadrado ambos miembros:

\( x^2(x^2-64x+1249)=(32-x)^2(x^2+625) \)  efectuando potencias y productos:

\( x^4-64x^3+1249x^2=x^4-64x^3+1024x^2+625x^2-40000x+640000 \)  trasponiendo, agrupando términos y simplificando:

\( x^2-100x+1600=0 \)

Así obtenemos una ecuación de segundo grado cuyas raíces son \( 20 \) y \( 80 \). Al haber elevado ambos miembros de la ecuación inicial al cuadrado, hay que comprobar ambas soluciones, ya que alguna o ambas podría no ser válida. En este caso, se descarta la de \( x=80 \) y se acepta la de \( x=20 \).

Finalmente habría que comprobar que en \( x=20 \) la función tiene, efectivamente, un mínimo. Al ser \( f(x) \) continua y derivable y al anularse \( f'(x) \) sólo en un punto, basta con ver que \( f'(x) \) es negativa para algún valor por la izquierda de \( 20 \) y positiva para alguno otro mayor que \( 20 \), obteniendo así que \( f(x) \) es decreciente por la izquierda de \( x=20 \) y creciente por la derecha. Efectivamente:

\( f'(0)=\displaystyle\frac{-32}{\sqrt[ ]{1249}}<0 \)
\( f'(32)=\displaystyle\frac{32}{\sqrt[ ]{1649}}>0 \)

Por lo que \( f(x) \) tiene un mínimo en \( x=20 \). Esto también se puede demostrar determinando la concavidad en de \( f(x) \) en \( x=20 \). No obstante, en este caso, parece más sencillo hacerlo como he indicado.
[cerrar]

El anterior camino os desanima a muchos cuando os encontráis con una ecuación que tiene raíces cuadradas y denominadores. Espero que lo que llevamos de exposición sirva para quitarle un poco de hierro al asunto y mostrar que la ecuación es, en realidad, asequible.

La siguiente solución es la que corresponde al potente método de los multiplicadores de Lagrange, que tanto aligera la tarea de resolver muchos de los problemas de opitimización.

Solución 2


Sean \( \alpha_1 \) y \( \alpha_2 \) los ángulos que el cable forma con cada torre. Es fácil ver que para que la longitud de cable sea mínima debe ser \( \alpha_1,\alpha_2\geq{0} \) y por tanto \( \alpha_1,\alpha_2\in{[0,\pi/2)} \). Entonces la longitud del cable se puede expresar como:

\( f(\alpha_1,\alpha_2)=\displaystyle\frac{25}{\cos\alpha_2}+\displaystyle\frac{15}{\cos\alpha_2} \)

Ésta última es la función a minimizar bajo la restricción:

\( 25\tg\alpha_1+15\tg\alpha_2-32=0 \)

El problema es equivalente a considerar \( \lambda \) tal que:

\( g_\lambda(\alpha_1,\alpha_1)=\displaystyle\frac{25}{\cos(\alpha_2)}+\displaystyle\frac{15}{\cos\alpha_2}+\lambda(25\tg\alpha_1+15\tg\alpha_2-32) \)

tenga un mínimo en un punto que cumpla:

\( 25\tg\alpha_1+15\tg\alpha_2-32=0 \)

Y ese mínimo es el punto que hay que hallar.

Igualando las derivadas parciales a cero:

\( \displaystyle\frac{{\partial g}}{{\partial \alpha_1}}=0\;\Rightarrow{\;}\displaystyle\frac{25\sin\alpha_1}{\cos^2\alpha_1}+\displaystyle\frac{25\lambda}{\cos^2\alpha_1}=0\;\Rightarrow{\;}\sin\alpha_1=-\lambda \)

Por razones bastante parecidas \( \sin\alpha_2=-\lambda \). De donde \( \alpha_1=\alpha_2 \) y substituyendo en la restricción \( \tg\alpha_1=\tg\alpha_2=\displaystyle\frac{32}{40}=\displaystyle\frac{4}{5} \).

Para comprobar que la solución se trata de un mínimo habría que estudiar el signo de la restricción de la diferencial segunda de \( f \) sobre el espacio vectorial tangente a la curva en \( \mathbb{R^2} \) dada por la ecuación implícita \( 25\tg\alpha_1+15\tg\alpha_2-32=0 \) en el punto que hemos hallado \( \left(\arctg\left(\displaystyle\frac{4}{5}\right),\arctg\left(\displaystyle\frac{4}{5}\right)\right) \). La diferencial segunda queda:

\( \begin{bmatrix}{\displaystyle\frac{25\cos^2\alpha_1+50\sin^2\alpha_1}{cos^3\alpha_1}}&{0}\\{0}&{\displaystyle\frac{15\cos^2\alpha_2+30\sin^2\alpha_2}{cos^3\alpha_2}}\end{bmatrix} \)

Y el espacio vectorial tangente a la curva sería el núcleo del gradiente de \( f \) en el punto. Lo que sucede es que, en este caso, no hace falta hallarlo porque la diferencial segunda es definida positiva en todos los puntos en que \( \alpha_1,\alpha_2\in{[0,\pi/2)} \), por lo que su restricción también va a ser definida positiva y el punto hallado es un mínimo.

Finalmente, la distancia pedida es \( x=25\tg\alpha_1=25\cdot{\displaystyle\frac{4}{5}}=20 \)
[cerrar]

Y por último la solución que suele resultar más sorprendente, que como ya he dicho se puede entender con un nivel bastante elemental.

Solución 3


Se trata de considerar punto \( B' \), el simétrico del \( B \) con respecto al suelo. De esta manera, la longitud del cable es igual a \( AX+XB=AX+XB' \), que será mínima cuando los puntos \( A,X \) y \( B' \) estén alineados. En ese caso, se tendrá que los triángulos \( APX \) y \( B'QX \) son semejantes por tener dos ángulos iguales. Entonces, tendrán también los lados proporcionales, por lo que:

\( \displaystyle\frac{x}{25}=\displaystyle\frac{32-x}{15}\;\Rightarrow{\;}15x=25\cdot{}(32-x)\;\Rightarrow{\;}40x=800\;\Rightarrow{\;x=20} \)

Y ya está.  :o
[cerrar]

La pregunta que os soléis hacer los estudiantes universitarios y de bachillerato al ver esta última solución es si éste método sería válido en un examen del curso que estáis cursando. En mi opinión, si el enunciado no exige que el problema se resuelva mediante un método determinado, se debería dar la respuesta por válida. Pero sólo es una opinión...

Espero que os haya sido útil y que os haya gustado. Cualquier tipo de comentario es bienvenido. Un saludo.

13
Docencia / Errores en la comunicación entre el profesor y el alumno.
« en: 19 Octubre, 2019, 12:26 am »
Hola a todos.

Es este un tema que siempre me ha tocado muy de lleno, tanto cuando estudiaba como ahora en mi trabajo, que básicamente consiste en ayudar a quien me lo pide con asignaturas de matemáticas, física y química. Resulta que muy a menudo me veo implicado en errores en la comunicación sobre algo que tiene que ver con esas disciplinas. Resulta que no tengo herramientas para resolver esos errores pero me siento con la responsabilidad de hacerlo. Es un tema que, como digo, siempre me ha afectado mucho. Se me ha ocurrido que tal vez en el foro, como hay muchos estudiantes y muchos docentes, se pueda compartir alguna idea al respecto. No estoy hablando de herramientas legales, ni que impliquen el más mínimo signo de violencia ni nada de eso (estoy hablando en serio). Me estoy refiriendo a herramientas comunicativas.

El último caso que he vivido ha sido durante estas dos últimas semanas. Un alumno y amigo mío tenía un examen este viernes (hoy o ayer dependiendo del horario) de una asignatura que va de lenguajes formales. Trabajando sobre una colección ejercicios resueltos nos iban saliendo dudas y las fuimos apuntando para írselas comentando al profe. Una de ellas llevó a una conversación vía e-mail que se alargó algo más de lo que esperaba. Mi alumno me ha pedido si la puedo poner por aquí para ver qué opináis sobre el asunto y yo quisiera aprovechar por si me podéis dar ideas de cómo afrontar este tipo de situaciones con los profesores, ya que se repiten bastante y me suelen dejar bastante chafado anímicamente.

El problema que nos ha surgido no tiene que ver, en realidad, con los lenguajes formales, sino más bien con la lógica básica. De todas formas, por si hiciera falta en algún momento, pongo aquí algunos resultados importantes vistos en la asignatura con el fin de que gente que no esté familiarizada con el asunto pueda seguir la conversación.

Los lenguajes son conjuntos de palabras definidas sobre un alfabeto, que es un conjunto de caracteres. Por ejemplo, sobre el alfabeto \( \{0,1\} \) podemos definir el lenguaje \( \{0,001,1000\} \), que sería un lenguaje de tres palabras.

Los lenguajes están clasificados en conjuntos de lenguajes. Los que aparecen en la conversación son:

\( SD \). El conjunto de los lenguajes semidecidibles (o recursivamente enumerables).
\( D \). El conjunto de los lenguajes decidibles (o recursivos)
\( NP \). No viene a cuento que defina esto ahora. Otro conjunto de lenguajes que muchos ya conoceréis.
\( P \). Y otro conjunto de lenguajes, también muy conocido...

Sobre estos conjuntos de lenguajes existen las siguientes relaciones de inclusión:

\( P\subseteq{NP\subseteq{}}D\subseteq{SD} \)

Se puede demostrar que si un lenguaje, \( L \), está en \( SD-D \), entonces su complementario, \( L^c \), no está en \( SD \). Otro resultado sencillo es que el complementario de un lenguaje de \( P \) también está en \( P \).

La conversación va sobre un enunciado que dice, textualmente salvo traducción palabra por palabra del catalán, lo siguiente:

Dado un lenguaje semidecidible, \( L \), el lenguaje complementario, \( L^c \), ¿puede estar en \( P \) o en \( NP \)? Razona la respuesta.

Con lo comentado hasta ahora ya se puede contestar. Aquí va la conversación, con los nombres ocultados y sin las faltas de ortografía que abundaban por ambas partes, sobre todo de la del alumno. También he omitido lo relativo a las otras dos dudas, que vienen siendo las que comenté en este hilo y en este otro:

Spoiler
ALUMNO:

Buenos dias

Me llamo alumno y estoy cursando la asignatura de ...

[...]

Ha llegado a mí una colección de exámenes resueltos. Por el estilo en el que están escritas las soluciones parece que éstas son las oficiales. No obstante, me han generado algunas dudas.

[...]

Veo que en los examenes se ha preguntado varias veces, la última el 5-2-2019, si el complementario de un lenguaje semidecidible puede ser \( NP \). Y se contesta que no argunmentando y demostrando que el complementario de un lenguaje \( NP   \) es siempre decidible por lo que no puede ser semidecidible. Es posible que en los enunciados falte algo así como que: ¿el complementario de un lenguaje semidecidible no decidible puede ser NP? Es que según he entendido en la asignatura los problemas decidibles son tambien semidecidibles, ¿o estoy equivocado?

Agradezco de antemano cualquier tipo de ayuda con estas dudas. Muchas gracias y un saludo.


PROFESOR:

Hola alumno,

Estas soluciones de ejercicios de examen se publican para dar una idea de una solución aceptable y poder ser comparada con la que cada persona escribe en su examen. Algunas veces la solución propuesta no es muy buena porque la solución buena del todo es un poco más compleja y la idea es ofrecer algo que pueda ser comparable a las soluciones de los exámenes.

Citar
Veo que en los examenes se ha preguntado varias veces, la última el 5-2-2019, si el complementario de un lenguaje semidecidible puede ser \( NP \). Y se contesta que no argunmentando y demostrando que el complementario de un lenguaje NP  es siempre decidible por lo que no puede ser semidecidible. Es posible que en los enunciados falte algo así como que: ¿el complementario de un lenguaje semidecidible no decidible puede ser \( NP \)?

Es que según he entendido en la asignatura los problemas decidibles son tambien semidecidibles, ¿o estoy equivocado?

NO, un lenguaje semidecidible es lo que es y uno decidible también. Es verdad que el conjunto de los decidibles es un subconjunto de los semidecidibles. Pero eso puede ser considerado como un caso particular (muy grande), cuando se pide una demostración no suele ser una buena idea centrarse en casos particulares.

Por otro lado, el complementario de un lenguaje NO puede ser decidible ni tampoco semidecidible. Ya que si lo fuera podríamos demostrar que el conjunto de los semidecidibles es el mismo que el de los decidibles. Si es así no podemos construir un programa que sitúe el complementario ni en \( P  \) ni en \( NP \).

Espero haber aclarado un poco tus dudas.


ALUMNO:

Hola profesor.

Antes de nada muchas gracias por tus aclaraciones, me han sido de gran ayuda.

Tan solo me queda por perfilar un poco la tercera y última de las cuestiones que te he planteado. Tenemos que si un lenguaje es decidible también es semidecidible. Y también tenemos que hay lenguajes semidecidibles que no son decidibles. Hasta aquí bien. Intentaré formular la cuestión con algo más de claridad y precisión. Me refiero por ejemplo a la pregunta que se formuló el 5-2-2019 en la recuperación del primer parcial en el ejercicio 4. Se pregunta: "Dado un lenguaje semidecidible, \( L \), el lenguaje complementario, \( L^c \), ¿puede estar en \( P \) o en \( NP \)? Razona la respuesta".

En la solución se llevan a cabo unos razonamientos que creo entender, y finalmente se concluye: "Esto significa que \( L  \) es decidible, lo que sería una contradicción con el hecho de que se supone que es semidecidible".

No veo dónde está la contradicción. Hemos dicho que ser decidible implica ser semidecidible. Se me debe estar escapando algo... ¿Puedes ayudarme por favor?

Muchas gracias.


PROFESOR:

Si \( L \) es decidible tienes un programa que siempre acaba y que reconoce a las palabras de \( L \). Pero has partido de una suposición diferente, has empezado asumiendo que L es semidecidible, con lo que no puedes esperar que un programa que reconoce ese lenguaje acabe siempre.

Piénsalo bien, si el complementario, \( L^c \), de un lenguaje semidecidible \( L \) (tal cual, completito, sin matices) es decidible o semidecidible significa que puedes contar con:

a.- Un programa que reconoce a \( L  \) (que puede no acabar).
b.- Un programa que reconoce a \( L^c \).

Con ello concluyes que cualquier lenguaje semidecidible (recuerda que a \( L \) no le hemos puesto ninguna restricción) es en realidad decidible (porque puedes combinar el resultado de los dos reconocedores) y por lo tanto no existen los semidecidibles y todos son decidibles. Y esto último es falso.

NO te confundas con casos particulares.


ALUMNO:

Hola profesor,

Citar
Si \( L \) es decidible tienes un programa que siempre acaba y que reconoce a las palabras de \( L \). Pero has partido de una suposición diferente, has empezado asumiendo que L es semidecidible, con lo que no puedes esperar que un programa que reconoce ese lenguaje acabe siempre.

Piénsalo bien, si el complementario, \( L^c \), de un lenguaje semidecidible \( L \) (tal cual, completito, sin matices) es decidible o semidecidible significa que puedes contar con:

a.- Un programa que reconoce a \( L  \) (que puede no acabar).
b.- Un programa que reconoce a \( L^c \).

Con ello concluyes que cualquier lenguaje semidecidible (recuerda que a \( L \) no le hemos puesto ninguna restricción) es en realidad decidible (porque puedes combinar el resultado de los dos reconocedores) y por lo tanto no existen los semidecidibles y todos son decidibles. Y esto último es falso.

Muchas gracias por la explicación. Estoy plenamente de acuerdo con ella. Ahora bien, pienso que has demostrado ahí, al igual que en la demostración de la que hablé, es que existen lenguajes semidecidibles cuyo complementario no es semidecidible. De hecho, esto pasa exactamente con los lenguajes semidecidibles que no son decidibles.

Sin embargo el enunciado, tal y como yo lo entiendo, nos pregunta si existe un lenguaje semidecidible cuyo complementario esté en \( NP \): 

Citar
"Dado un lenguaje semidecidible, \( L \), el lenguaje complementario, \( L^c \), ¿puede estar en \( P \) o en \( NP \)?"

Y diría que  poder sí que puede serlo (no tiene que serlo, pero sí que puede). Pasa. por ejemplo, con el lenguaje de las palabras sobre \( \{0,1\} \) que empiezan por cero. Es semidecidible, y su complementario, el lenguaje formado por la palabra vacía y las que empiezan por uno, está en \( P \).

Citar
NO te confundas con casos particulares.

Pero es que es el enunciado el que me pide que halle ese caso particular, ¿no?

Otra cosa hubiese sido un enunciado así;

"Dado un lenguaje semidecidible i no decidible, \( L  \), el lenguaje complementario \( L^c  \) puede ser \( P  \) o \( NP \)?"

Esto sí que es falso. Y tu demostración me parece más que suficiente. O bien:

"Dado un lenguaje semidecidible, \( L  \), el lenguaje complementario \( L^c  \) tiene que ser \( P  \) o \( NP \)?"
"¿Para todo lenguaje semidecidible \( L \), está \( L^c  \) en NP?"

Lo mismo, estos enunciados son falsos y tu demostración basta para verlo. ¿Entiendes mi exposición?¿Qué punto crees que falla?

Gracias de nuevo por tu atención. Un saludo.


PROFESOR:

Vuelves a centrarte en casos concretos, y además erróneos.

Citar
Y diría que  poder sí que puede serlo (no tiene que serlo, pero sí que puede). Pasa. por ejemplo, con el lenguaje de las palabras sobre \( \{0,1\} \) que empiezan por cero. Es semidecidible...

Falso, es decidible (y a partir de aquí no sacas nada en claro)

Citar
...y su complementario, el lenguaje formado por la palabra vacía y las que empiezan por uno, está en \( P \).

Que también es decidible y, como ya te he dicho, no vas a ninguna parte.

Citar
Pero es que es el enunciado el que  me pide que busque ese caso particular, ¿no?

NO, el enunciado pide que razones. Un caso particular sirve para refutar una hipótesis, no para confirmarla.

Citar
Otra cosa hubiese sido un enunciado así;

"Dado un lenguaje semidecidible i no decidible, \( L  \), el lenguaje complementario \( L^c  \) puede ser \( P  \) o \( NP \)?"

Esto sí que es falso. Y tu demostración me parece más que suficiente. O bien:


"Dado un lenguaje semidecidible, \( L  \), el lenguaje complementario \( L^c  \) tiene que ser \( P  \) o \( NP \)?"
"¿Para todo lenguaje semidecidible \( L \), está \( L^c  \) en NP?"

Lo mismo, estos enunciados son falsos y tu demostración basta para verlo. ¿Entiendes mi exposición?¿Qué punto crees que falla?

Creo que ya te lo he explicado. Espero que entiendas que es lo que haces mal. Pero por si acaso, voy con un ejemplo que igual te aclara algo más las ideas:

"Rafael Nadal es una persona, luego todas las personas son muy buenas jugando al tenis" ¿Es eso cierto? pues algo así es lo que tu justificas.


ALUMNO:

Hola de nuevo profesor. Muchas gracias por responder. Me sabe mal tener que insistir tanto pero es que el parcial es dentro de poco y me gustaría aclarar las dudas por completo.

Antes de nada me gustaría aclarar cual de estas dos sentencias es cierta :
A) El conjunto de lenguajes decidibles es un subconjunto del conjunto de lenguajes semidecibles
B) Existen lenguajes decidibles que no son semidecibles

Pienso que las definiciones vistas en clase concuerdan con la A. También pienso que concuerdo con la frase que me has dicho un par de emails atrás :

Citar
Es verdad que el conjunto de los decidibles es un subconjunto de los semidecibles

Sin embargo la B la has utilizado para refutar el argumento de mi anterior e-mail cuando yo digo:

Citar
Y diría que  poder sí que puede serlo (no tiene que serlo, pero sí que puede). Pasa. por ejemplo, con el lenguaje de las palabras sobre \( \{0,1\} \) que empiezan por cero. Es semidecidible...

Tú dices claramente:

Citar
Falso, es decidible

¿Falso? ¿Cómo quedamos?.... Necesito que me aclares esto antes de nada. Luego dices:

Citar
...el enunciado pide razones. Un caso particular sirve para refutar una hipótesis, no para confirmarla.

Bien, y el caso particular que he aportado sirve para refutar que todos los lenguajes semidecibles tienen el complementario fuera de \( P \). O bien, sirve para aceptar que existen lenguajes semidecibles cuyo complementario está en \( P \), que es lo que nos pide el enunciado.

Citar
Rafael Nadal es una persona, luego todas las personas son muy buenas jugando al tenis" ¿Es eso cierto? pues algo así es lo que tu justificas.

Entiendo el error al que te refieres, pero no creo que sea el que cometo yo. El enunciado me está pidiendo si una persona puede jugar bien al tenis, y yo he contestado que sí, porque he encontrado a Rafa Nadal, que es persona y juega al tenis.

Un saludo y gracias de antemano.


PROFESOR:

Seguiré con las metáforas

Todos los humanos no son esquimales, pero los esquimales son humanos. Entonces si hablamos de temas concernientes con los humanos en general no parece muy razonable restringir el concepto al caso de los esquimales.

Ahora hacemos buscar "humano" y cambiar por "lenguaje semidecidible" y "esquimal" por "lenguaje decidible".
[cerrar]

Pues eso. Mi análisis de la situación es que ambas partes han estado correctas en cuanto a las formas (no ha habido faltas de respeto, ni abusos de poder, ni nada de eso), cosa que no ocurre siempre en estas situaciones. Aún así, el profesor se siente cargado de razón, el alumno también, y así no se puede avanzar.

El alumno, pensando que era inútil intentar llegar a algo en claro y con cierto temor a posibles repercusiones negativas sobre él, decidió dar las gracias y despedirse la misma mañana antes del examen. Tal vez, si se hubiese insistido se hubiese podido llegar a un punto de unión, si bien, creo que es de entender la opción que ha elegido el alumno

¿Cómo creéis que un alumno implicado en algo así debe tratar estas situaciones? Obviamente, la relación alumno-profesor no es horizontal, ya que el primero quiere casi por encima de todo que el segundo le apruebe, y eso condiciona bastante. Es cierto que, en este caso, esto último no ha influido mucho, pero es fácil creer que he sido testigo de otros casos en los que sí que ha influido.

Sé que el asunto es peliagudo y que puede llegar a ser polémico. Espero que os interese y que participéis sin miedo.

Gracias por vuestras opiniones y un saludo.

14
Hola.

Aquí ando con otro problema de complejidades computacionales. Me dan el siguiente código y me piden textualmente: "Explica la complejidad":

Código: [Seleccionar]
programa F(n)
k,m: vector
  escribir (k,1)
  escribir (m,1)
  mayor_o_igual(m,n)
  mientras leer(acepta)=0 hacer
    sucesor(k)
    mult(m,k)
    mayor_o_igual(m,n)
  fmientras
fin

El programa mayor_o_igual(m,n) deja el acepta en \( 1 \) si \( m\geq{n} \) y en \( 0 \) en otro caso.
El programa sucesor(k) calcula el número siguiente a \( k \).
El programa mult(m,k) calcula el producto \( m\cdot{k} \) y lo escribe en \( m \) utilizando el algoritmo elemental de multiplicación de números naturales.

Lo que hace este programa es calcular el menor natural \( p \) tal que \( p! \) es mayor que otro natural \( n \) dado. En lo sucesivo \( \left |{x}\right | \) significa "el número de dígitos de la representación binaria de \( x \)". Yo he pensado lo siguiente:

El tiempo de las sentencias anteriores al bucle no depende de \( \left |{n}\right | \), es decir, es constante.

El bucle se ejecuta \( p \) veces, en la \( k-\textrm{ésima} \) de las cuales calcula:

1) El sucesor de \( k \), se hace en un tiempo \( O(\left |{k}\right | \)
2) El producto \( m\cdot{k} \), que se puede hacer en \( O(\left |{m}\right |\cdot{\left |{k}\right |})=O(\left |{(k-1)!}\right |\cdot{\left |{k}\right |}) \)
3) El valor lógico de mayor_o_igual(m,n), que se hace en \( O(min(\left |{m}\right |,\left |{n}\right |))\subseteq{O(\left |{n}\right |)} \)

En total, el número de operaciones que deben hacerse es del orden de:

\( O(\left |{1}\right |+|2|+...+|p|+|1|\cdot{}|0!|+|2|\cdot{}|1!|+...+|p|\cdot{}|(p-1)!|+\underbrace{|n|+...+|n|}_{p\textrm{ veces}})=O(|1|\cdot{}|0!|+|2|\cdot{}|1!|+...+|p|\cdot{}|(p-1)!|+p\cdot{\left |{n}\right |}) \)

Y básicamente, hasta aquí he llegado. He intentado cosas pero no me ha salido nada demasiado interesante, como por ejemplo, utilizar los teoremas de Stolz y de Stirling para calcular la parte principal de \( |1|\cdot{}|0!|+|2|\cdot{}|1!|+...+|p|\cdot{}|(p-1)!|\sim{}\log(1)\log(0!)+\log(2)\log(1!)+...+\log(p)\log((p-1)!) \), pero no lo he acabado de sacar. Tampoco creo que vayan por ahí los tiros, ya que no veo cómo se puede dejar después todo en función sólo de \( \left |{n}\right | \).

¿Alguien me podría proporcionar algunas recomendaciones o directrices para resolver problemas de este estilo? No acabo de pillarles el "tranquillo".

Agradezco de antemano cualquier tipo de comentario y de ayuda. Un saludo.

15
Hola chicos.

Tengo que demostrar que el problema del empaquetamiento es \( \mathcal{NP} \). El problema del empaquetamiento me lo han enunciado como sigue:

Se consideran \( n \) objetos de tamaños \( v_1,...,v_n \), cajas de tamaño \( V \) y un número \( k \). Nos planteamos si es posible empaquetar los objetos en \( k \) cajas sin romper los objetos ni exceder el tamaño de las cajas.

Diría que el problema en sí lo tengo ya resuelto, lo que pasa es que en el proceso de resolución me surgieron bastantes dudas. La primera, que en Wikipedia encontré esto.

No acabo de ver que se trate del mismo problema, pero el caso es que si lo fuese Wikipedia apenas justifica que se trata de un problema NP, me parece entender que dice que lo es claramente y ya está, pero yo no lo veo tan claramente... En general, con el tema este de calcular complejidades, me cuesta ver qué es necesario justificar y qué no es necesario justificar.

Posteriormente se me ocurrió generar de manera no determinista todas las \( k-\textrm{particiones} \) de un \( n-\textrm{conjunto} \), en este caso el conjunto de números \( \{v_1,...,v_n\} \), y luego comprobar en tiempo polinómico que la suma de los números de todos los subconjuntos que forman cada una de las particiones es menor que \( V \). Tuve problemas a la hora de encontrar un algoritmo que te generase todas esas particiones, por lo que aquí tengo otra duda en la que me iría bien que alguien me iluminase un poco, si fuese posible. Y la cosa no acaba aquí...

Después, buscando entre una colección que tengo de exámenes resueltos encontré uno en el que se genera de manera no determinista y supuestamente en tiempo polinómico las permutaciones de \( n \) elementos. En un principio, este algoritmo me sirve, ya que, para cada permutación, se pueden ir sumando los tamaños de los elementos según el orden en el que vayan apareciendo en la permutación y cuando la suma exceda el valor de \( V \) se pone el valor de la suma igual al tamaño del último elemento que se iba añadir. Cuando se han tenido en cuenta a todos los elementos, si la suma se ha puesto a 0 un número de veces menor o igual a \( k \) el algoritmo acepta. El caso es que no acabo de ver que el algoritmo para generar las permutaciones sea \( \mathcal{NP} \), aquí pongo un pseudo-código del algoritmo que he copiado de la colección de problemas que os digo:

Código: [Seleccionar]
programa genera_permutaciones(p,n)
   continua : vector
   primera_permutacion(p,n)
   mientras leer (continua)=1 hacer
      es_ultima(p,n)
      si leer (acepta)=1 entonces
         escribir(continua,0)
      si_no
         ramificar
            escribir(continua,0)
         con
             siguiente_permutacion(p,n)
         fin_ramificar
      fin_si
   fin_mientras
fin

El programa primera_permutacion(p,n), pone en el vector \( p \) los números de \( 1 \) a \( n \) en orden creciente, y es_ultima(p,n) comprueba que en el vector \( p \) estén todos los números de \( 1 \) a \( n \) en orden decreciente.

El problema lo tengo con el programa siguiente_permutacion(p,n), que supuestamente coloca en el vector \( p \) la siguiente permutación a la que \( p \) representa. El orden en el que la solución dice que opera siguiente_permutacion(p,n) es el siguiente, para \( n=4 \).

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
...

La solución del examen dice sobre dicho programa que "se trata de reordenar los valores de la permutación, por tanto es de orden \( \mathcal{P} \)". Aquí tampoco veo que sea tan inmediato justificar el que este programa trabaje en tiempo polinómico. Creo haber demostrado que sí que lo hace, pero he tenido que encontrar el algoritmo explícitamente y utilizar dentro de él un algoritmo de ordenación, el quicksort, que trabaja en \( O(n^2) \)

A modo de apunte, en Wikipedia he encontrado el algoritmo de Heap, que se supone que es el más rápido conocido para generar permutaciones y que las ordena de manera diferente.

Básicamente, lo que me gustaría es entender por qué es obvio, si es que lo es, que ciertos algoritmos (los que he expuesto, para empezar) son de la clase \( \mathcal{P} \).

Un saludo y muchas gracias de antemano por la ayuda.

16
Hola, a todos.

Aquí ando de nuevo con inseguridades sobre un ejercicio de complejidad computacional. Agradecería que confirmaseis que lo que he pensado está bien o que me indicaseis los errores. El enunciado dice así:

Sean \( f \) y \( g \) dos funciones computables en tiempo polinómico. Proporciona un programa polinómico para \( h(x)=2^{\left |{f(x)}\right |}\cdot{}2^{\left |{g(x)}\right |} \)

En el material que estoy siguiendo \( \left |{x}\right | \) significa número de cifras de \( x \). Creo que un programa correcto sería, básicamente, realizar los siguientes pasos:

1) Calcular \( f(x) \) i \( g(x) \).
2) Contar el número de cifras de \( f(x) \) y \( g(x) \)
3) Elevar \( 2 \) a sendos números de cifras, multiplicando \( 2 \) por sí mismo las veces que haga falta.
4) Multiplicar los resultados con el algoritmo de escuela elemental.

Veamos que efectivamente, es un programa polinómico:

1) Por el enunciado se puede hacer en tiempo polinómico.

2) Contar el número de cifras de \( n \) es claramente un algoritmo \( O(|n|) \). Al ser \( f(x) \) computable en tiempo polinómico, debe haber un polinomio \( p(|x|) \) que acote \( |f(x)| \) y contar las cifras de \( f(x) \) es de complejidad \( O\left(p\left(|x|\right)\right) \), polinómica en \( |x| \). Lo mismo para \( |g(x)| \).

3) Calcular \( 2^n \) es hacer \( n-1 \) multiplicaciones por \( 2 \). Al tener \( 2 \) un sólo dígito, cada multiplicación se puede hacer en un número de operaciones del orden del tamaño del número que estamos multiplicando, es decir, el algoritmo es de complejidad \( O(|2^1|+...+|2^{n-1}|)=O(log(2)+...+log(2^{n-1}))=O(1+...+n-1)=O\left(\displaystyle\frac{(n-1)n}{2}\right)=O(n^2) \). Por lo que calcular \( 2^{|f(x)|} \) con este algoritmo es de complejidad \( O(|f(x)|^2)\subseteq{}O\left((p(|x|))^2\right) \), también polinómica en \( |x| \). Lo mismo para \( 2^{|g(x)|} \)

4) Sin pérdida de generalidad, asumo \( |2^{|f(x)|}|\geq{}|2^{|g(x)|}| \), entonces multiplicar ambos números mediante el algoritmo elemental es de complejidad \( O\left(\left(|2^{|f(x)|}|\right)^2\right)=O\left(\left(\log\left(2^{|f(x)|}\right)\right)^2\right)=O\left(|f(x)|^2\right)\subseteq{}O((p(|x|))^2) \), y la complejidad de este paso vuelve a ser polinómica.

El paso con el que más dudo es el 3). No he encontrado la complejidad de elevar un número a otro por ningún lado y me lo he inventado un poco. ¿Es correcto? Muchas gracias por vuestra ayuda y por vuestros comentarios. Un saludo.

17
Hola, buenas.

Estoy haciendo un curso de autómatas y lenguajes formales en el que hay un tema llamado complejidad en tiempo cuya teoría me he mirado y más o menos entiendo pero en cuyos ejercicios me quedo bastante atascado. En general, no estoy seguro de por dónde van los tiros de lo que me piden. Empiezo con uno de ellos, que creo que prácticamente ya tengo, aunque con bastantes dudas. A ver qué os parece:

Di si la función \( f(n)=10^8log(n) \) es computable polinómicamente o no, y justifica la respuesta.

Para empezar, como ya he dicho, no estoy del todo seguro de haber interpretado bien el enunciado. Supongo que lo que me piden es decidir si se pueden sacar \( 8  \) cifras decimales del valor de \( log(n) \) en tiempo polinómico en el número de cifras de \( n \). Supongo también que \( n \) es un entero positivo. Suponiendo que es eso lo que me piden y basándome en cómo se calculaban hace unos años los logaritmos con las famosas tablas, contesto así:

Si llamamos \( k \) al número de cifras de \( n \) tenemos que:

\( log(n)=log(10^{k-1}\cdot{}10^{-(k-1)}\cdot{}n)=k-1+log(10^{-(k-1)}\cdot{}n) \)

Por lo que la parte entera de lo que me están pidiendo es \( k-1 \), valor que se puede sacar en tiempo polinómico en función de \( k \) y la parte decimal es \( log(10^{-(k-1)}\cdot{}n) \). Como \( 10^{-(k-1)}\cdot{}n\in{[1,10)}  \) entonces \( log(10^{-(k-1)}\cdot{}n)\in{[0,1)}  \)

Además, por las propiedades de la función logaritmo, para todo \( x_1,x_2\in{[1,10)} \) con \( x_2>x_1 \) tenemos que \( log(x_2)-log(x_1)<x_2-x_1 \). Por lo que si yo quiero un error menor que \( 10^{-8} \) al calcular \( log(x) \) con \( x\in{[1,10)} \), basta aproximar \( x \) con una precisión de \(  8 \) cifras decimales. Entonces basta que el algoritmo tenga calculados de antemano los logaritmos de \( (10-1)/10^{-8}=9\cdot{10^8} \) números diferentes. Por ser el conjunto de estos números un conjunto finito, buscar el que se necesita, que es aquel cuyas primeras cifras coinciden con todas las de \( n \), se puede hacer en un tiempo que no dependa del tamaño de \( x \), es decir, se puede acotar por una función constante. Y con ello todas las operaciones se hacen en tiempo polinómico y la función es computable polinómicamente.

No me acaba de convencer la forma. Tampoco estoy seguro de que mi razonamiento esté libre de errores ¿Tiene alguien alguna sugerencia, crítica, comentario io algo así?. Y también una curiosidad que tiene bastante que ver con esto, ¿alguien sabe cómo calculan las calculadoras los logaritmos? ¿utilizan lo de los desarrollos en serie de potencias, o tienen una "tabla de logaritmos"?

Muchas gracias de antemano por el tiempo y la ayuda. Un saludo.

18
Construcciones / Clasificación de cónicas.
« en: 04 Septiembre, 2019, 10:13 am »
CLASIFICACIÓN DE CÓNICAS

Hay situaciones en la que se pide clasificar una cónica a partir de ciertos datos sin que sea necesario determinarla. Veamos un ejemplo.

Dados cinco puntos del plano clasificar la cónica que los contiene

Se toman dos de ellos como vértices \( V \) y \( V' \) de dos haces proyectivos. Sean \( A,B,C \) los otros tres puntos. Se obtienen los dos tríos de rectas \( VA,VB,VC \) y \( VA',VB',VC' \), que forman los haces \( V(a,b,c) \) y \( V(a',b',c') \), proyectivos por el Teorema de Steiner. Se traslada uno de ellos, el \( V(a',b',c') \), por ejemplo, sobre \( V \) y se obtienen los dos haces \( V(a,b,c) \) y \( V(a'',b'',c'') \).

Si esa proyectividad no tiene rectas dobles, la cónica no tendrá puntos impropios, y se tratará de una elipse. Si tiene dos rectas dobles, nos hallaremos ante una hipérbola cuyas asíntotas serán paralelas a esas rectas dobles. Y si tiene sólo una, ante una parábola, cuyo eje será paralelo a dicha recta.

Índice y comentarios.

19
Construcciones / Determinación de cónicas II
« en: 01 Septiembre, 2019, 08:51 am »
DETERMINACION DE CONICAS II

Los tipos de condiciones que definen los problema de determinación de cónicas que vamos a analizar son los siguientes:

R: Se conoce una recta tangente a la cónica.
P: Se conoce un punto de la cónica.
F: Se conoce un foco de la cónica. Equivale a dos condiciones de uno de los tipos anteriores.

Esto da lugar a 12 problemas. Si tenemos los dos focos, el asunto es bastante trivial

FFP. Trivial
FFR. El simétrico de uno de los focos con respecto a la recta está en la circunferencia focal del otro, de donde se saca el eje mayor.

Si tenemos un foco, se reduce a un problema de Apolonio.

FPPP. Las tres circunferencias con centro en cada punto y que pasan por el foco son tangentes a la circunferencia focal del otro foco. Dicha circunferencia se puede sacar entonces resolviendo un problema de Apolonio CCC. En este caso, se resulve fácilmente por inversión, ya que las tres circunferencias comparten un punto.
FPPR. El simétrico del foco con respecto a la recta está en la circunferencia focal del otro foco, luego se puede hallar mediante un Apolonio CCP. Como las dos circunferencias comparten un punto es aconsejable aplicar inversión.
FPRR. Similar a los anteriores. En este caso se reduce a un Apolonio PPC
FRRR. Éste se reduce a un Apolonio PPP, es decir, a hallar la circunferencia circunscrita de un triángulo.

Si no conocemos ningún foco, el problema se puede reducir al de encontrar una cónica conocidos tres puntos y dos rectas tangentes en dos de ellos o a su dual. Estos seis problemas, se halla a su vez dualmente apareados.

PPPPP (o 5P). Aplicando el teorema de Pascal se puede hallar la tangente en el punto que se quiera. Aplicando esto dos veces ya hemos reducido el problema.


RRRRR (5R). El dual del anterior. Por el teorema de Brianchon se halla el punto de tangencia en las rectas que se quiera.


PPPPR (4PR). Por el teorema de Desarges se halla el punto de tangencia en la recta y queda un PPPPP. Tener en cuenta que dados cuatro puntos, los tres pares de rectas que los unen dos a dos son tres de las cónicas que pasan por esos puntos. Bastan dos de ellas para definir la involución cuyo punto doble es el requerido.


PRRRR (4RP). Por el teorema de Sturm se halla la recta tangente en el punto y queda un RRRRR. Tener en cuenta que dadas las cuatro rectas y un punto, las dos rectas que pasan por cada uno de los tres pares de puntos en los que las cuatro rectas del enunciado se cortan dos a dos son una cónica degenerada tangente a las cuatro rectas. Con dos parejas de esas tres parejas de rectas ya queda definida la involución cuya recta doble es la requerida.


20
Construcciones / Determinación de cónicas I
« en: 31 Agosto, 2019, 06:02 pm »
DETERMINACIÓN DE CÓNICAS I

Determinar una cónica conocidos dos diámetros conjugados \( AB \) y \( CD \)

Empecemos con el caso de la elipse. Sea \( MM'N'N \) el paralelógramo tal que \( M'M \) es paralela a \( CD \) Y \( N'N \) paralela a \( AB \) como muestra el dibujo. Claramente el centro \( O \) del paralelogramo es también el centro de la elipse. Al ser \( AC \) y \( AD \) cuerdas suplementarias, entonces los diámetros situados sobre \( M'N \) y \( MN' \) también son conjugados, luego ya está definida la involución de diámetros conjugados, que corta a la recta \( M'M \) en una involución de puntos, de la que se conoce su centro \( B \) y dos homólogos \( M',M \). Se hallan los puntos \( P \) y \( Q \) situados en la mediatriz de \( M'M \) tales que \( BP=BQ=BM \). El haz de circunferencias que pasa por \( P \) y \( Q \) corta a la recta \( M'M \) en puntos de esa involución. Basta hallar la que pasa por \( O \) para hallar el par de puntos homólogos \( E-E' \) que pertenecen a los ejes.

Llamando \( CN=a' \), \( MB=b' \) y \( a,b \) las magnitudes de los ejes principales, en el triángulo \( OBP \) se cumple, aplicando el teorema del coseno y las fórmulas de Apolonio, que \( OQ^2=a'^2+b'^2-2a'b'\cos(\alpha+\pi/2)=a'^2+b'^2+2a'b'\sin\alpha=a^2+b^2+2ab=(a+b)^2 \). De aquí que \( OQ=a+b \) y, por razones similares \( OP=a-b \), de donde se puede sacar las magnitudes de los ejes \( a=(OQ+OP)/2 \) y \( b=(OQ-OP)/2 \) para finalmente dibujar la elipse


El caso de la hipérbola es muy parecido. Quizás valga la pena mencionar que las rectas dobles de la involución de diámetros conjugados son las asíntotas, ya que las polares de sus puntos impropios son ellas mismas.

Páginas: [1] 2 3