Cositas interesantes sobre complejidad

Haciendo tarea de Complejidad Computacional, en un problema nos preguntaban sobre relaciones entre clases de complejidad. Hay clases que no sabía que existían, y fue mi sorpresa ver algunas relaciones padrísimas entre ellas.
Tenemos a viejos conocidos como P y NP. Pero existen otros que suenan un poco raros que, son los que me parecieron interesantísimos.
ZPP: En pocas palabras, esta clase de complejidad, representa a problemas que son resueltos con algoritmos que usan aleatoriedad, y además los resuelven con un 0% de probabilidad de error, terminando en tiempo polinomial.
BPP: Clase de complejidad que representa a problemas que son resueltos con algoritmos que usan aleatoriedad, y además los resuelven con un 1/3 de probabilidad de error, terminando en tiempo polinomial.
RP: Clase de complejidad que representa a problemas que son resueltos con algoritmos que usan aleatoriedad, y además los resuelven con un 1/2 de probabilidad de error, terminando en tiempo polinomial.
Pero ¿qué tiene de interesante esto? ¿Les suenan conocidos los algoritmos evolutivos/genéticos? ¿Heurísticas? Pues sí, ahora lo sabemos, estos algoritmos tienen sus propias clases de complejidad. Leyendo por allí me encontré que existe otro mundo de complejidad que se llama Complejidad Probabilística donde se estudian los algoritmos que involucran al azar y otros aspectos aleatorios.
¿Qué otra cosa importante hay que destacar? Observemos que NP no está contenido completamente en estas clases BPP, ZPP, RP. ¿qué nos dice esto? Esto quiere decir que, existen problemas NP que ni con un algoritmo que use azar (llámese genético, heurístico, evolutivo) se pueden resolver con una probabilidad alta de éxito.
Encontré un wiki en la Universidad de Standford donde está todo el zoológico de clases de complejidad que hay. Una clase al menos para cada letra del alfabeto. =)

Los amigos invisibles

Hola, sólo quería compartir algunos de los mejores éxitos de la banda Pop/Funk/Rock Venezolana "Los amigos invisibles". Esta bandita está de gira presentando nuevo disco en vivo. Ellos como muchas otras bandas en sus conciertos, nunca dejan de tocar. Si tienen algunos minutos libres, no dejen de ver el video

Saludos

¿P=NP? La encuesta

Una de las preguntas más famosas relacionadas con la Teoría de la Computación que aún no tienen respuesta es el famoso ¿P=NP? P es una clase de complejidad que representa a los problemas para los cuales se conocen algoritmos que pueden resolverlos en tiempo polinomial determinista. NP es una clase de complejidad que representa a los problemas para los cuales se conocen algoritmos que pueden resolverlos en tiempo polinomial no-determinista, pero no se conocen algoritmos que puedan resolverlos en tiempo polinomial determinista (p.e. Agente Viajero, Satisfacibilidad, The Hamiltonian Path Problem).

Es un problema muy importante para el mundo de la computación. Imagínense, pasándolo a términos prácticos, si descubrimos que P=NP habría una manera de poder resolver cualquier problema computable en tiempo polinomial determinista, i.e. en tiempos humanamente tratables.
Encontré una encuesta que se realizó en el 2002 donde se le preguntaron a varios expertos del área de distintas universidades sobre el problema ¿P=NP? He aquí unos resultados:

¿Cuándo crees que se resuelva P=NP?

1. Entre 2002-2009: 5
2. Entre 2010-2019: 12
   
3. Entre 2020-2029: 13
   
4. Entre 2030-2039: 10
   
5. Entre 2040-2049: 5
6. Entre 2050-2059: 12
   
7. Entre 2060-2069: 4
   
8. Entre 2200-3000: 5
9. Nunca se resolverá: 5

¿Cuál será la respuesta?

1. P = NP : 9
2. P != NP : 61

¿Qué técnicas se usarán en la demostración?

1. Técnicas combinatorias y de complejidad: 11
   
2. Lógica: 9
3. Matemáticas: 10
4. Nuevas técnicas: 16

Hay muchos datos más en la encuesta, por ejemplo algunos investigadores comentan sobre que la solución la dará su universidad, en tal año y usará tal cosa para demostrarla.
El área de complejidad computacional es un mundo lleno de temas divertidos e interesantes. Considero yo que es una de las áreas más importantes en las Ciencias de la Computación.
Yo en particular creo que P != NP, y tú ¿qué piensas? ¿P = NP?

Actualización: No sabía pero me dijo un amigo que en un capítulo de los simpsons está puesta la igualdad, P=NP en el capítulo donde Homero viaja a la tercera dimensión

Around the World

Siempre he tenido las ganas y los sueños de viajar. Creo que conocer nuevos países y por lo tanto nuevas culturas, debe ser algo muy interesante y gratificante. Mi amigo Saúl y yo platicábamos de los lugares a los que nos gustaría conocer, platicábamos de lo chido que estaría conocer nuevos lugares.
Leyendo por ahí me encontré que existe un proyecto llamado CouchSurfing, está muy interesante. Se trata de una especie de red social con propósito específico real que es, el viajar por el mundo.
¿Cómo es esto posible? La idea es simple, sabemos todos que para viajar el hospedaje resulta un costo importante en el presupuesto. Entonces tu, como usuario de CouchSurfing, puedes encontrar gente de otros países que te pueden hospedar en su casa de manera gratuita y ya te ahorrarías ese gasto. Obviamente la idea es que le regreses el favor en algún momento a la comunidad.
Tal vez a mucha gente genere desconfianza este tipo de cosas y más en México, pero aquí hay algunos puntos que pude observar en este proyecto:

• No es una red social para encontrar pareja (lo especifican en los términos de uso)
  
• Estás en una comunidad que tiene muchas ideas en común contigo, no hay razón de tener desconfianza. La idea es viajar
  
• La idea es que contribuyas a la comunidad así como recibir los beneficios de esta
  
• Si realizas un viaje, este quedará registrado obviamente (dónde, con quién, cuándo)
  
• El intercambio cultural es un objetivo de esta red
  
  

Existe también gente que tiene como fama, es decir, gente de confianza. Así como en mercado libre donde la gente que tiene muchas calificaciones positivas y a estas les compras, igual aquí, pero aquí la gente viaja con las personas que tienen más "puntos positivos".
También existen miles de testimoniales de gente que simplemente se aventó a viajar así, y cuentan como es que el proyecto de CouchSurfing ayudó y cómo fue la experiencia.
He aquí una opción para gente como yo que, ganas no les faltan de viajar pero que, el presupuesto no es del todo favorable.
Dejo aquí un videito que me mandó Saúl que está padrísimo, increíble, así dan más ganas aún de viajar.



A surfear en sofás se ha dicho.

Códigos

Estoy llevando una materia que está padrísima, se llama teoría de la información, pero el profesor nos está dando códigos detectores y correctores de errores, está super chido eso; esperamos ver algo de criptografía. Es de las materias que más me están gustando ya que aparte de la teoría que vemos, implementamos cosas.

Un código nos sirve, en pocas palabras, para meter redundancia a la información. ¿Por qué querríamos hacer eso? La información pasa por canales de comunicación todo el tiempo, entonces está sujeta a errores del canal, errores que no podemos controlar, ya que son ocasionados por el medio ambiente u otros factores fuera de nuestro alcance. Con esa redundancia se pretende rescatar a la información que fue alterada en el canal, para que quede igual a como ésta partió del transmisor (en el mejor de los casos).
Usamos un código llamado "código extendido de Hamming de longitud ocho" y simulamos un canal de comunicación que metía errores. Aquí algunas pruebas:

Imagen de 'osita' pasando por un canal que por cada 200 bits que pasan por él pone en error a 1

Imagen de 'osita' pasando por un canal que por cada 300 bits que pasan por él pone en error a 1

Imagen de 'osita' pasando por un canal que por cada 500 bits que pasan por él pone en error a 1
Imagen de 'osita' pasando por un canal que por cada 800 bits que pasan por él pone en error a 1
Imagen de 'osita' pasando por un canal que por cada 1000 bits que pasan por él pone en error a 1
'Osita' sin errores

Ahora una imagen con más información

Imagen de pasando por un canal que por cada 100 bits que pasan por él pone en error a 1

Imagen de pasando por un canal que por cada 300 bits que pasan por él pone en error a 1

Imagen de pasando por un canal que por cada 400 bits que pasan por él pone en error a 1

Imagen de pasando por un canal que por cada 800 bits que pasan por él pone en error a 1

Imagen sin errores.

Existen muchas variables involucradas en esto, una conclusión no podemos dar. La primera imagen de 'osita' tiene muy pocos bits, observamos que prácticamente en un canal que, mete de 1 error por cada 300 bits podemos ver bien la imagen, sin embargo, no ocurre eso con la segunda imagen, hay muchos errores, es claro debido a que la imagen es más grande. En la segunda podemos ver la imagen casi exacta hasta que tenemos un canal que mete un error por cada 800 bits. Inclusive un factor podría ser el formato del archivo.
Las especificaciones de la tasa de error en un canal deben venir en su manual. En las redes, los diversos protocolos de comunicación se encargan de realizar estos procesos cuando es necesario.
Los códigos es otro mundo bastante interesante donde hay muchas cosas qué aprender.

Gracias a Miri y a Erick por las imágenes que me regalaron. :D

Basta

No puedo aún definir al 100% mi postura respecto a lo de la influenza porcina. He leído muchas cosas últimamente relacionado a ello, he escuchado la opinión de mucha gente, gente muy distinta entre sí. La mayor parte coincide con que la influenza porcina es real y es un tema grave.
Creer que los medios informativos dicen la verdad no es una buena opción. Es difícil encontrar información que sea de confianza, a veces es mejor investigar por tu propia cuenta. A su vez es divertido leer y escuchar lo que la piensa la gente sobre esta situación, cada cabeza es un mundo, creer que cambiarás la postura de la gente ante una situación, es como creer en los santos reyes aún.
Existen muchas cosas qué pensar, muchas cosas que he escuchado. Por ejemplo:

• El virus existe y el gobierno lo usará como pretexto para justificar la crisis que viene.
• Es una cuestión global, el virus fue desarrollado a propósito globalmente, para dar un cambio a la economía en el mundo (que no sé como pero pues, hacer un cambio).
• Es una arma biológica que se le salió de las manos a EUA, donde los conejillos de India obviamente eran mexicanos
• Se acabará el mundo, el calendario Maya estaba atrasado

Y así muchísimas cosas de las que he leído. Pero mientras son peras o son manzanas, ¿qué podemos hacer? Hablé con algunos amigos que están en clínicas y cosas relacionadas con la salud. Pues al parecer el virus porcino una realidad claramente, no sé si grave o no. Creo que no queda otra cosa más que esperar a que se tranquilicen las cosas un poco.
Independientemente que sea cierto o no, creo que la salud es la cosa más importante que tenemos y considero que, no importa la ideología que tengamos, no cambiaría nuestra ideología el usar un tapabocas y lavarte las manos. Tal vez no por ti, pero a tu familia puede que sí le importe. Lo más seguro es que haya algo escondido, ya nos darán la noticia.
Saludos y feliz día del niño.

Dragon Ball

Advertencia:

No vean la película "Dragon Ball Evolution" si no quieren sufrir traumas. Es la peor película que he visto en mi vida. Como dice Miri que dijo su amigo Richard:

Si quieres conservar momentos gratos de tu infancia, no veas la película

Es de lo peor entre lo peor, el término malo se queda corto. Destrozaron la historia de la manera más irresponsablemente posible.

Sueldos en las TI

No soy muy fanático de leer revistas. Aparte no muchas son de mi interés así que prefiero gastar ese dinero en otras cosas más necesarias para mi.
Pero pues cuando podemos leerlas de manera libre y gratuita en la Web, la cosa cambia. Me encontré la ya famosa revista Software Gurú (SG) en su edición de Diciembre-Enero. Contiene un artículo muy interesante de un estudio que se realizó en el 2008 sobre los salarios relacionados con las TI.
Es interesante observar todas las variables involucradas en esto. Como datos curiosos podemos ver que, siendo la computación una disciplina distinta a las demás donde el ingenio, la lógica y creatividad van de la mano, el empleo en este sector no es tan bien remunerado como en otros países.
De acuerdo con el estudio realizado, mediante encuestas vía Web a un poco más de 2000 empleados, se observó a simple vista que, el salario promedio de un empleado relacionado con las TI está alrededor de $22,000. Interesante.
Tristemente en el campo de las prestaciones laborales como gastos médicos, vacaciones, aguinaldo, etc., un 21% de los encuestados no contaba con ninguna prestación.
El giro de una empresa que provee servicios en TI es la más pagada, seguida por las empresas que tienen sus Áreas de Sistemas que no se dedican directamente a las TI. Esta última es donde se concentra la mayor parte de los empleados encuestados, 42%. Así mismo en las empresas que proveen servicios existe la mayor cantidad de personas que trabajan por honorarios con un 40% de su personal, es decir, sin prestaciones y pagando impuestos seguramente.
La cosa no para ahí, aquí empieza lo interesante. Si observamos la población por actividad que se realiza, la zona más poblada es la de un desarrollador de sistemas OMG con un 31%, es decir, ¡una de cada tres personas con un empleo relacionado con las TI es desarrollador!, ganando la cantidad de $17,000 aproximadamente, creo que era de esperarse. La segunda más poblada son los gerentes de proyecto ganando la no despreciable cantidad de $27,000 y abarcando un 14% de la población.
Y se pone más interesante ya que si filtramos por escolaridad, la gente con una carrera universitaria abarca un 46% ganando en promedio $22,000. Personas que no terminan su carrera son el 17% con un sueldo de $17,000 y finalmente, los que tienen una maestría son el 16% rondando los $30,000.
Y para terminar con algo todavía más interesante. Si observamos los datos en función de la tecnología que sabemos usar, la encuesta arroja datos, para mi, inesperados.
El lenguaje mejor pagado allá afuera es COBOL, seguido de los relacionados con .NET, después Java en su Enterprise Edition (como tenía que esperarse) y quedando, sí, leyeron bien, PHP como ¡el lenguaje peor pagado allá afuera! WTF! :(
Por plataforma la mejor pagada es Mainframe de IBM, seguida de UNIX, MS Windows en 5to. lugar que contiene a casi el 90% de la población, y sí, por desgracia Linux en el penúltimo lugar.
Los datos muestran que una certificación sí hace que tu salario se incremente, aunque no a muchos nos parezca. También otros factores como la experiencia se ven reflejados en la encuesta.
Mi pregunta ahora es. ¿¡en qué he perdido mi tiempo todos estos años!? Jaja.
Como conclusión creo que estos datos nos dan una idea más clara de qué hacer cuando nos toque estar allá afuera buscando empleo. No malbaratar nuestro trabajo. Pedir lo justo en función de nuestras habilidades y conocimientos. El área de las TI tiene muchísimo campo laboral, en pocos años creo que no seguirá siendo así a mi parecer, dicen que un programador es el obrero del futuro. Les recomiendo leer este artículo, súper interesante. Está en la página 22.
Y... ¿qué les parecieron estos datos? ¿son justos? ¿seguirá así dentro de unos años? ¿qué faltó comentarse?

Datos obtenidos de la revista SG número 22 Diciembre 2008 - Enero 2009.

Actualización:
Pueden también pedírsela a mi amigo Maicol Yacson que tiene la revista original firmada, autografiada y tocada por las manos de Hanna Octava :P

Thru-you

Un tipo, tal vez loco u ocioso o fanático de la música o todas las anteriores, se ha dedicado a realizar algunos remixes de algunos de los millones de videos musicales de algunas las millones de personas que suben videos al ya famoso youtube. Este es resultado de alguna de sus mezclas, algo de funk con toques bluseros

Limitaciones (Reescribiendo a los clásicos)

Fermat imposible xⁿ + yⁿ = zⁿ para n>2… He encontrado una demostración excelente, pero el espacio en Twitter es demasiado pequeño para ponerla.

Visto en Microsiervos.