¿Como medir la complejidad?

    Con este pequeño artículo trataré de explicar como es posible medir la complejidad de algo, computacionalmente hablando. Aunque ciertamente estas ideas podrían ser utilizadas en otras muchas ramas en donde se presenta un problema que debemos resolver y la eficiencia de su resolución (en tiempo) sea un parámetro importante.

    La resolución práctica de un problema computacional exige por una parte un algoritmo o método de resolución y por otra un programa o codificación (implementación) de ese algoritmo en un ordenador real. El algoritmo es esencial a diferencia de la codificación que puede convertirse en anecdótica, aunque lo más normal es que no lo sea, a fin de cuentas los bugs están en la implementación y no en el algoritmo.

    A efectos prácticos además hay que tomar en consideración la cantidad de recursos, tanto de tiempo como de memoria que la implementación de un algoritmo puede precisar. Este suele depender del tamaño del problema pues el algoritmo y la implementación se deban adaptar a diferentes parámetros de entrada, por ejemplo, no es lo mismo ordenar alfabéticamente un array con nombres para un tamaño de array de 100 que para otro de tamaño 100.000 tanto en tiempo como en memoria empleada. El concepto exacto que mide el tamaño del problema depende de la lógica del mismo y es por lo tanto imposible dar una regla para su medición.

    Aunque el tamaño en memoria que una implementación pueda ocupar debe ser tomado en consideración esto ha dejado de ser problemático debido al aumento de la capacidad de memoria de los equipos y aunque puede parecer que a la capacidad de cálculo le pasa lo misma esto no es así. Y es un error común pensar que la optimización del código pueda ser dejada de lado confiando en la potencia de cálculo de nuestros equipos o de equipos futuros. Es pues el tiempo de ejecución el principal baremo a tener en cuenta a la hora de diseñar un algoritmo o afirmar que un algoritmo es “mejor” que otro.

El tiempo de ejecución

    Una medida útil para conocer el tiempo de ejecución de un programa dependiendo de su tamaño (N) es lo que llamaremos a partir de ahora T(N). Para un programa del tipo

    S1; for(i=0;i<N;i++) S2;

    Siendo S1 y S2 un conjunto de sentencias válidas tenemos que su función T(N) tendría la forma

    T(N) = T(S1) + N*T(S2)

    Cualquier fórmula de T(N) hace referencia a N o/y a una serie de parámetros constantes. Dado que la potencia computacional aumenta cada año hay que analizar los algoritmos dejando de lado estos dos factores (N y parámetros constantes) haciendo que nuestro análisis sea independiente de la máquina empleada.

    Para hacer esto se suele calcular el comportamiento cuando N tiende a infinito, es decir, su comportamiento asintótico. Se suele en estos caso no hablar de una función que nos da el tiempo dado el tamaño del problema sino que se suele definir un conjunto de funciones que nos dan este comportamiento y se afirma que estas funciones son del Orden de f(n) siendo esta una función representativa de todas ellas. Y se denota el orden por O(f(n)). Para caracterizar formalmente esta definición tenemos que:

O(f(n))= {g: ENTERO -> REAL+  tales que
            existen las constantes  k  y  N0 tales que
            para todo  N > N0,  g(N) <= k*f(N) }

    en otras palabras O(f(n)) está formado por todas las funciones que crecen a un ritmo menor o igual a f(n). Es decir f(n) es la cota superior para este conjunto de funciones g(n).

    O(f(n)) define un orden con todas sus propiedades, escogemos un representante de este orden y así tendremos:

O(1) orden constante
O(log n) orden logarítmico
O(n) orden lineal
O(n log n)
O(n2) orden cuadrático
O(na) orden polinomial (a > 2)
O(an) orden exponencial (a > 2)
O(n!) orden factorial

    Esto nos dará pues un indicador de la bondad de un algoritmo, cuanto menor sea el orden mejor.

Para saber más:

Complejidad algorítmica

La complejidad de los algoritmos
Complejidad algoritmos
Notas sobre complejidad algorítmica

egrep y grep

    La utilidad GNU grep desde su versión 2.5 ha añadido nuevas e importantes funcionalidades como son la capacidad de emplear expresiones regulares y volcar sólo las coincidencias obtenidas, salida con color y nuevas opciones para ficheros y directorios.

    Ante todo comentar que egrep en realidad ejecuta un grep -E sobre los argumentos que se le pasen, sin embargo no es un alias como algunos piensan, sino un script bash. Puedes hecharle un vistazo ejecutando:

$ vi `which egrep`

    Lo que hace exactamente la opción -E (–extended-regexp) es evaluar la expresión a buscar con grep como si fuera una expresión regular. Esto permite búsquedas con muchas más posibilidades, buscando emails,telefonos, ips,urls etc en un directorio o fichero.

    Existen más opciones en el comando grep que permiten evaluar expresiones regulares como -e, -G, -P

    Estos son algunos ejemplos de su utilización:

    Buscar las tablas creadas en un fichero volcado por mysqldump y la línea del fichero donde esto ocurre:

$ grep -E -n “CREATE TABLE \`([^\`]+)\`” -o mysql.sql

    Ver los usuarios del sistema que tienen definido el campo de información de usuario (usualmente empleado para introducir información adicional como el nombre completo o alguna descripción de la utilización del usuario)

$ egrep “[a-z]:x:[0-9]+:[0-9]+:[^:]+” /etc/passwd

    Las posibilidades de este comando (unidas a las de las expresiones regulares gracias a estas opciones) son inmensas.

La primera pregunta de Rajoy

    Todo internet se ha volcado en buscar cual ha sido la primera pregunta de Rajoy en el congreso en la legislatura pasada (bueno en la aún presente) ya que después del segundo debate celebrado ayer en donde ambos se reprocharon lo mentiroso que era el otro por decir que esa pregunta versaba sobre los precios y lo que habían subido. Rajoy diciendo que este tema siempre le había preocupado y que ya en esa primera pregunta ya hacia referencia a él y Zapatero diciendo que a Rajoy sólo le preocupó desde hace unos meses cuando podía sacar tajada electoral de este asunto.

    Pues aquí en el blog de novanebula, en absoluta primicia ;p, tenemos la solución. Aquí está el diario de sesiones donde aparece esta primera pregunta:

Acta del Congreso de los Diputados

Y aquí tenemos un video de su intervención:

Video Rajoy sobre la primera pregunta

    Lo más asombroso del tema es que medios de izquierdas y de derechas siguen sin ponerse de acuerdo después de ver el acta. Para los unos (medios de izquierdas incluido PSOE) la primera pregunta esta clara y fue esta:

    Del Diputado don Mariano Rajoy Brey, del Grupo Parlamentario Popular en el Congreso, que formula al Excmo. Sr. Presidente del Gobierno: ¿Cómo valora usted los primeros días de su Gobierno?

    Esta más claro que el agua, ahora bien los otros (medios de derechas y PP) replican que después de la respuesta de Zapatero en la réplica de Rajoy este dijo esto:

    “Eso que usted llama a veces hacer honor a la palabra dada. El problema es que a veces es difícil saber cuál es su palabra y la de su Gobierno. Porque en temas como el IVA, la financiación autonómica —de la que preguntó el señor Durán—, la privatización de Televisión, los 100 euros, el mando único, el cálculo de las pensiones, el control de los imames, en todos estos temas y otros muchos hay muchas palabras.

    Y comentan que Rajoy si que habló de economía (el IVA, hasta lo he resaltado en la cita por si no habíais caído) en su primera intervención (bueno en el turno de réplica).

    Pero cual era la cuestión exacta, cual fue la discrepancia que surgió en este debate. Intentemos recordar lo que dijo Rajoy y Zapatero en este segundo debate (tranquilos el oráculo Youtube nos va a ayudar).

Segundo debate Zapatero-Rajoy

Directamente de este video en el minuto 3:30 podemos extraer esto:
Rajoy:
Pero yo ya la primera pregunta que le hice en el congreso de los diputados en el año 2004 era que debería hacer usted reformas económicas porque sino la herencia y la herencia* se iban a terminar como así ocurrió y así nos encontramos en la situación que estamos

* seguramente quiso decir inercia

Que cada uno saque sus conclusiones porque “creo” que ya somos todos bastante mayorcitos.

Primarias en EEUU

Hilary Clinton y Barack Obama se enfrentan en las primarias de EEUU para convertise en los candidados del Partido Demócrata a la presidencia de EEUU. El casi imparable ascenso en las encuestas y en los resultados electorales de Barack Obama le esta poniendo las cosas difíciles a la ex-primera dama y senadora Hilary Clinton.

La próximas elecciones en Texas y Ohio son muy importantes para la carrera electoral de ambos. Hace tan sólo unas semanas la victoria de Hilary en estos estados estaba cantada pero ahora incluso las encuestas han dado un vuelco y la propia candidata reconoce que podría perderlas. El resultado podría no ser definitivo pero dejaría las cosas casi vistas para sentencia si Obama consiguiera ganar por un cómodo margen.

Los resultado de estas primarias se dilucidarán en breve.

Muerte de jefe militar de las FARC en Ecuador

    La operación colombiana en que murió en Ecuador el número dos de la guerrilla de las FARC, Raúl Reyes, tensionó la relación con sus países vecinos –Venezuela y Ecuador– que acusaron al presidente Alvaro Uribe de optar por el camino de la guerra, y suspendieron sus relaciones diplomáticas.

    En Venezuela el presidente Hugo Chávez ordenó el cierre de la embajada en Bogotá y movilizó tropas a la frontera, mientras que el mandatario ecuatoriano, Rafael Correa, retiró a su embajador en la capital colombiana.

    Reyes murió el sábado en un bombardeo de aviones colombianos sobre el campamento en que dormía en territorio de Ecuador, según el gobierno colombiano que calificó el hecho como “el mayor golpe” dado a las marxistas Fuerzas Armadas Revolucionarias de Colombia (FARC), en más de cuatro décadas.

    Previo al retiro de su embajador, Correa pidió al gobierno de Uribe que se disculpe por la violación de la soberanía de su país, mientras su ministro de seguridad, Gustavo Larrea, calificaba el hecho como “el atentado más grave contra la soberanía ecuatoriana cometido por Colombia al menos en lo que va del siglo“.

48 miembros de ETA detenidos en lo que va de año

    Cuarenta y ocho presuntos miembros de ETA o de su entorno han sido detenidos en lo que va de año, incluidos los dos supuestos etarras arrestados hoy en Vizcaya, Oroitz Aldekoa y Agurne Salterain.

    Doce de estos arrestos han tenido lugar en Francia y en España han sido detenidos los otros treinta y seis, aunque dieciséis de ellos no están vinculados directamente con ETA sino que pertenecen a Batasuna o a otras organizaciones del entorno etarra y otros catorce están relacionados con la llamada ‘kale borroka’.

    Desde que ETA rompió el 6 de junio de 2007 el ‘alto el fuego permanente’ (en vigor desde el 24 de marzo de 2006), y según los datos del Ministerio del Interior, 99 personas han sido detenidas por su presunta relación con ETA, incluidos los dos etarras de hoy.

Xgamma, una utilidad poco conocida

    Hay veces que el brillo del monitor no está correctamente ajustado o la iluminación en la habitación donde está tu ordenador es la inadecuada. Entonces debemos ajustar los mandos de brillo o contraste de tu monitor, por medio de las ruedecitas (antes) o de algún menú interno (ahora). ¡Pero quieto! ¡Un autentico friki no hace eso!, es mejor ajustar el brillo modificando la corrección gamma de tu monitor a través del servidor X (bueno, bueno donde va a parar esta solución es mucho mejor ;p)

  Pues para hacer esto utilizamos el poco conocido comando xgamma, esta es su sintaxis

xgamma [-display display] [-screen screen] [-quiet] [-gamma f.f | [[-rgamma f.f] [-ggamma f.f] [-bgamma f.f]]]

  Prueba a ejecutar

$ xgamma -gamma 2

  Obtendrás una salida como esta

-> Red 1.000, Green 1.000, Blue 1.000
<- Red 2.000, Green 2.000, Blue 2.000

  La primera línea indica los valores antiguos rgb y la segunda los nuevos

  Para volver a la situación inicial

$ xgamma -gamma 1

  Y ya está, puedes modificar los componentes rgb de manera individualizada mediante los parámetros rgamma, ggamma y bgamma. Y cuidado no quemes tu monitor.

Ahora puedes hacer que una combinación específica de teclas o los botones multimedia de tu teclado hagan automáticamente esta tarea. Utilizando por ejemplo LinEAK.

Easter Egg en el APT

    APT es el sistema de actualización/instalación de paquetes para sistemas tipo Debian. APT son las siglas de Advanced Package Tool.

Para ver este ‘Easter Egg’ (huevo de pascua) sigue los siguientes pasos:

Inicia sesión como root (bueno en realidad no se precisa ser root para ver este truco, lo puedes hacer con un usuario normal con shell)

Ejecuta:
# apt-get moo

Verás esta obra de arte ASCII

         (__)
         (oo)
   /------\/
  / |    ||
 *  /\---/\
    ~~   ~~
...."Have you mooed today?"...

XD es buenisimo

Prueba ahora a ejecutar

#apt-get

Sin ningún parametro aparece un listado de ayuda con todas las opciones disponibles para el comando apt-get, pero en su última linea a modo de firma se puede leer

This APT has Super Cow Powers

(Este APT tiene Super Poderes Vacunos)

XDDDDDD

ETA llama a la abstención

En un comunidado remitido al diario Gara la banda terrorista ETA a emitido su primera consigna electoral. Esta vez no recomiendan el voto a ninguna formación política, las fuerzas políticas de su “entorno” parece que no concurren a las elecciones pero sólo el tiempo lo dirá. Lo que ETA pide ahora es la abstención ante la consideración de que “el Estado español ha impuesto el estado de excepción en Euskal Herria“.

Recordemos que hace tan sólo unos días ETA colocó un artefacto explosivo en la sede del PSOE en Derio. Por cierto, también es destacable que ANV condene este atentado.

La campaña del entorno de ETA para su nueva táctica abstencionista no acaba más que empezar. Ojala sólo se desarrolle en internet.