Cripto...

MCD(63,05) = 1

Esto es de lo poquito que aprendí en mis clases de criptografía en el semestre, jaja. También aprendí que hacemos un acto de fe cuando estamos usando un sistema de cifrado.

Computación Ubicua

Después de un intenso y productivo día laboral me dispongo a regresar a casa, subo en mi carro que me lleva a casa gracias al poderoso sistema de visión y al GPS que tiene integrado. Obviamente elige la ruta menos traficada haciendo un uso eficiente del combustible. Al acercarme a casa, la cochera detecta la presencia de mi auto y se abre para que pueda estacionarlo.

Para entrar a casa existe un sistema de reconocimiento facial y de voz para autenticar a los habitantes de casa. Al entrar, la luz se enciende, la contestadora dice los mensajes nuevos qué hay. Así mismo una pantalla me muestra los nuevos correos electrónicos que han llegado a mi buzón. Todo está en orden, al parecer todos mis dispositivos realizaron un buen papel nuevamente durante el día.

Esto no es más que un ejemplo del que seguramente en unos cuantos años estaremos experimentando en carne propia. Donde todos nuestros dispositivos, de cualquier tipo, aparte de realizar sus funciones habituales vayan más allá. Interactuen entre sí, interactuen sobre Internet.

Lo más rico de todo esto es que muchas disciplinas en el mundo de las Ciencias de la Computación colaboran. Imagínense, sistemas distribuidos, inteligencia artificial, visión computacional, procesamiento digital de imágenes, redes, ingeniería de software, geometría computacional, arquitectura de computadoras, etc. Todas ellas juntas para un fin en específico que es, tener una interacción más natural con los humanos y nuestras actividades rutinarias. Todo esto, transparente para nosotros.

Por supuesto que esta idea no es nueva, tiene muchos años. Muchas cosas se han llevado a la realidad ya. Todo esto tiene una estructura ya planeada, existen congresos dedicados a la computación ubicua y laboratorios en universidades de muchos países dedicados a su desarrollo.

Les invito a leer el siguiente artículo

The Computer for the 21st Century

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. =)

¿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

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

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

Neo-computation

Existen problemas que van fuera del alcance de una computadora, son los llamados problemas no computables. Hay una infinidad de ellos que no sabemos ni por donde atacar. Cuando encontremos un problema difícil, está demostrado que podemos encontrar otro aún más difícil que ése y así infinitas veces.

Aún así, no todo está perdido, existen una infinidad de problemas que podemos resolver con una computadora, los problemas computables. Pero por desgracia, la gran mayoría de ellos, donde sí tenemos alguna manera de resolverlos (llámense algoritmos), tenemos el inconveniente en el tiempo que nos llevamos para obtenerd una solución. Estos métodos los resuelven, sí, pero en tiempos humanamente intratables, ¿horas?, ¿años?, ¿siglos?

¿Entonces no podemos resolver nada? ¿Una computadora no sirve para nada? Hay algo cierto en eso, una computadora puede resolver muy pocos problemas. Actualmente los científicos han tratado que las computadoras sean más veloces y así puedan resolver problemas un poquito más grandes. Pero ¿será la solución colocar cada vez más procesadores en una tarjeta?, ¿colocar más memoria?, ¿hardware? No lo creo.

La computación es una ciencia muy joven, con muchos problemas sin resolver y mucho trabajo que hacer. Investigadores tratan de darle la vuelta, y han creado nuevos paradigmas para resolver problemas, nuevos modelos.

Por ejemplo, las computadoras cuánticas, algoritmos genéticos, DNA Computing, redes neuronales, etc. Muchas de estas propuestas son ya usadas e investigadas a fondo, pero no dejan de ser modelos probabilísticos. Ciertamente aproximan bien las soluciones de los problemas, pero nunca garantizan que se encontrará una solución y mucho menos que será óptima.

Entonces ¿qué es lo que debemos hacer? ¿El modelo de la máquina de Turing necesita ser remplazado, modificado? ¿En este nuevo modelo necesitamos ver los problemas que veíamos difíciles como fáciles? ¿Qué tanto cambiaría la computación actual con un nuevo modelo? ¿existirá ese nuevo modelo o será equivalente a la Máquina de Turing también? ¿Estamos bien como estamos? ¿Si pudieramos resolver esos problemas que son intratables, qué problemas no podríamos resolver con nuestro nuevo modelo?

¿Quién puede nombrar el número más grande?

Imagínate un juego, el chiste es escribir el número más grande que puedas imaginar. Tienes una hoja, un lápiz y un contendiente que tratará de escribir un número más grande que el tuyo. ¿qué escribirías?

De niño yo escribiría una hilera de puros 9s hasta llenar la hoja. Después, descubres que hay números aún más grandes y que los puedes expresar con términos exponenciales. En el artículo Who can name the biggest number?, Scott Aaronson plantea esa pregunta ¿cuál es el número más grande que el humano ha calculado?

Es tan natural para nosotros hablar de números grandes, que parecería una tarea sencilla. ¿Cuántas neuronas tenemos en el cerebro?, se han hecho estudios que dicen que trillones. Los números grandes están en todos lados de la naturaleza y en nuestro propio organismo por supuesto.

En los juegos como el ajedrez, el número de posibles tableros es un número relativamente grande. Y es cuando entra la computación en el juego de los números grandes. Ciertamente muchos números han sido calculados con ayuda de las computadoras. Aún así existen muchos otros problemas con números grandes que son imposibles de resolver con la ayuda de las computadoras.

Por ejemplo, la función de Ackermann, es un clásico ejemplo de que un problema no es tratable. Los números de Ackermann crecen muchísisisisimo más rápido que cualquier función exponencial. Calcular un número de estos es intratable para incluso números pequeños, tan solo calcular Ackermann(4,2) ya es imposible para una computadora ordinaria.

¿Existirán números aún más grandes que crezcan aún más rápido que la función de Ackermann? La respuesta es sí, the Busy Beaver Number. Este número tiene que ver con máquinas de Turing. Se sabe que estos números existen, pero resulta que no son computables.

Imagínense, si conociéramos BB(n) (el n-ésimo Busy Beaver) tendríamos la capacidad para saber si un programa para con una entrada, en pocas palabras podríamos del alguna predecir el futuro.

Actualmente con los modelos de cómputo que han sido propuestos están muy limitados, sólo una pequeñisisima parte de los problemas existentes son posibles de resolver. La pregunta es, ¿tendremos que crear nuevos modelos de cómputo para atacar por otro lado a la solución de problemas grandes?

Les recomiendo leer este artículo, realmente habla de cosas muy interesantes . Y cuándo te pregunten cual es el número más grande escribe BB(6).