He hecho los cálculos y consumir 2000 kcal al día es el equivalente energético de consumir 100 W. Vamos, que los humanos somos como una bombilla de 100 W, que por cierto, hace poco han prohibido en la UE.
En la UE hay aproximadamente 500 millones de habitantes, a 100 W cada uno nos da 50.000 MW, es decir, el consumo aproximado de 50 centrales nucleares. Y eso "nos los comemos".
¿Fuerte, no?
Tags Technorati: curiosidades, energía
miércoles, septiembre 30, 2009
viernes, septiembre 18, 2009
Complejidad de los algoritmos (II)
Como prometía ayer, hoy unos ejemplos de la complejidad de los algoritmos.
O(n)
Imaginemos el siguiente programa (en pseudocódigo):
haz n veces
x=x+1
Cuanto mayor sea n, más veces se ejecutará la instrucción, y por tanto más tardará, de una forma completamente lineal. Si aumentamos n mil veces, el programa tardará mil veces más en ejecutarse.
O(n^2)
Ahora miremos el siguiente programa:
haz n veces
haz m veces
x=x+1
Este programa ejecuta la instrucción n*m veces. Si n y m son iguales, tenemos n². Según incrementamos n, el tiempo de ejecución aumenta cuadráticamente. Si aumentamos n en mil, el tiempo de ejecución aumenta en un millón.
Un ejemplo fuera de la programación de este tipo de algoritmos es el que usamos para hacer multiplicaciones de varias cifras a mano. Con el aumento de cifras aumenta cuadráticamente los pasos a realizar.
O(log(n))
Este ejemplo es algo más complicado, así que voy a hacerlo en dos pasos. Imaginemos que queremos buscar en una lista ordenada de números enteros si está un elemento. (Vamos a evaluar el caso peor, que no dicho elemento no está, ya que es algo bastante típico en programación y es lo que nos da una medida de lo lento que puede ser nuestro algoritmo).
Una forma simple de buscar en la lista es la siguiente:
Mira el elemento i de la lista
¿Es el elemento i de la lista igual a lo que estábamos buscando?
Si es así, terminamos
Si no, habrá que volver al principio
Se le puede hacer alguna modificación, como decirle que ya que está ordenada, detener la ejecución si el elemento que buscamos es mayor que el elemento que estamos mirando, pero en esencia es lo mismo, el caso peor es lineal. Si incrementamos el tamaño de la lista el tiempo de ejecución aumenta linealmente.
Vamos ahora a aprovechar que la lista está ordenada y hagamos algo más inteligente:
Coge la lista y pártela por la mitad
Comparo el elemento que quiero encontrar con las dos mitades
Si el elemento es menor que la segunda mitad, descarto la primera mitad y repito el procedimiento con la segunda mitad
Si el elemento es mayor que la segunda mitad, descarto la segunda mitad y repito el procedimiento con la primera mitad
Si el elemento es igual a uno de los extremos de las dos listas, he terminado, he encontrado lo que buscaba
Este caso va descartando mitades. Por tanto, si tengo n elementos al principio, en la siguiente vuelta tendré n/2, en la siguiente n/4, en la siguiente n/8. En la vuelta k tendré n/(2^k). Y la cosa terminará cuando me quede un elemento, es decir, cuando n/(2^k)=1, cuando k=log(n) (recordad que log lo uso para decir logaritmo en base 2). Por tanto si incremento n, se incrementan los pasos en log(n). Como la función log crece más lentamente que la función líneal, el programa es mucho más rápido.
En el caso de búsqueda lineal, si incremento la lista mil veces, el programa tarda mil veces más. En cambio, en la búsqueda binaria sólo tarda diez veces más. Ese es el objetivo de todos los programas, que tengan complejidad logarítmica.
O(2^n)
Ahora vamos con el caso peor. Para ello vamos a introducir las series de Fibonacci, que se explican de la siguiente manera:
1, 1, 2, 3, 5, 8, ...
Es decir, empieza con 1, 1, y los siguientes elementos son la suma de los dos anteriores.
Una forma muy simple de generar el elemento n de esta serie es:
i es tres
elemento uno es uno
elemento dos es uno
bucle que para cuando i es igual a n
elemento i es elemento i-1 más elemento i-2
Claramente esto se hace en tiempo lineal. Cuanto más grande es n, más operaciones se hacen y se incrementan de forma lineal.
En cambio podemos usar la recursividad:
función fibonacci que requiere el número de elemento a ser calculado (n)
si el elemento es uno o dos, devolver el valor uno
de lo contrario el resultado es el dado por la suma de la función fibonacci de los elementos n y n-1
Es decir, para calcular un elemento llamamos a la misma función dos veces. Cada una de dichas funciones se llama a si misma otras dos veces, etc. Es decir, crece exponencialmente. Lo demuestro:
paso 1: 2 ejecuciones
paso 2: 2* (2 ejecucuciones)
paso 3: 2*(2*(2 ejecuciones))
paso k: (2^k) ejecuciones
¡Esto hay que evitarlo a toda costa! Pero no la recursividad en sí, sino dos llamadas recursivas que se encadenan. Si incrementamos los datos en mil el aumento de tiempo para el cálculo es mayor que la edad del universo.
Un ejemplo de un algoritmo exponencial es factorizar un número. Con algunas técnicas se ha logrado reducir, pero sigue siendo bastante exponencial. ¿Qué consecuencia tiene esto? Pues que multiplicar es fácil, pero separar en números primos no, así que esto se usa para compartir información de forma segura por Internet. Hace tiempo escribí sobre este tema en el blog.
Resumiendo, mirando nuestros algoritmos somos capaces de determinar cuál es la complejidad intentar evitar que sean cuadráticos o, sobretodo, exponenciales.
Tags Technorati: curiosidades, programación, informática
O(n)
Imaginemos el siguiente programa (en pseudocódigo):
haz n veces
x=x+1
Cuanto mayor sea n, más veces se ejecutará la instrucción, y por tanto más tardará, de una forma completamente lineal. Si aumentamos n mil veces, el programa tardará mil veces más en ejecutarse.
O(n^2)
Ahora miremos el siguiente programa:
haz n veces
haz m veces
x=x+1
Este programa ejecuta la instrucción n*m veces. Si n y m son iguales, tenemos n². Según incrementamos n, el tiempo de ejecución aumenta cuadráticamente. Si aumentamos n en mil, el tiempo de ejecución aumenta en un millón.
Un ejemplo fuera de la programación de este tipo de algoritmos es el que usamos para hacer multiplicaciones de varias cifras a mano. Con el aumento de cifras aumenta cuadráticamente los pasos a realizar.
O(log(n))
Este ejemplo es algo más complicado, así que voy a hacerlo en dos pasos. Imaginemos que queremos buscar en una lista ordenada de números enteros si está un elemento. (Vamos a evaluar el caso peor, que no dicho elemento no está, ya que es algo bastante típico en programación y es lo que nos da una medida de lo lento que puede ser nuestro algoritmo).
Una forma simple de buscar en la lista es la siguiente:
Mira el elemento i de la lista
¿Es el elemento i de la lista igual a lo que estábamos buscando?
Si es así, terminamos
Si no, habrá que volver al principio
Se le puede hacer alguna modificación, como decirle que ya que está ordenada, detener la ejecución si el elemento que buscamos es mayor que el elemento que estamos mirando, pero en esencia es lo mismo, el caso peor es lineal. Si incrementamos el tamaño de la lista el tiempo de ejecución aumenta linealmente.
Vamos ahora a aprovechar que la lista está ordenada y hagamos algo más inteligente:
Coge la lista y pártela por la mitad
Comparo el elemento que quiero encontrar con las dos mitades
Si el elemento es menor que la segunda mitad, descarto la primera mitad y repito el procedimiento con la segunda mitad
Si el elemento es mayor que la segunda mitad, descarto la segunda mitad y repito el procedimiento con la primera mitad
Si el elemento es igual a uno de los extremos de las dos listas, he terminado, he encontrado lo que buscaba
Este caso va descartando mitades. Por tanto, si tengo n elementos al principio, en la siguiente vuelta tendré n/2, en la siguiente n/4, en la siguiente n/8. En la vuelta k tendré n/(2^k). Y la cosa terminará cuando me quede un elemento, es decir, cuando n/(2^k)=1, cuando k=log(n) (recordad que log lo uso para decir logaritmo en base 2). Por tanto si incremento n, se incrementan los pasos en log(n). Como la función log crece más lentamente que la función líneal, el programa es mucho más rápido.
En el caso de búsqueda lineal, si incremento la lista mil veces, el programa tarda mil veces más. En cambio, en la búsqueda binaria sólo tarda diez veces más. Ese es el objetivo de todos los programas, que tengan complejidad logarítmica.
O(2^n)
Ahora vamos con el caso peor. Para ello vamos a introducir las series de Fibonacci, que se explican de la siguiente manera:
1, 1, 2, 3, 5, 8, ...
Es decir, empieza con 1, 1, y los siguientes elementos son la suma de los dos anteriores.
Una forma muy simple de generar el elemento n de esta serie es:
i es tres
elemento uno es uno
elemento dos es uno
bucle que para cuando i es igual a n
elemento i es elemento i-1 más elemento i-2
Claramente esto se hace en tiempo lineal. Cuanto más grande es n, más operaciones se hacen y se incrementan de forma lineal.
En cambio podemos usar la recursividad:
función fibonacci que requiere el número de elemento a ser calculado (n)
si el elemento es uno o dos, devolver el valor uno
de lo contrario el resultado es el dado por la suma de la función fibonacci de los elementos n y n-1
Es decir, para calcular un elemento llamamos a la misma función dos veces. Cada una de dichas funciones se llama a si misma otras dos veces, etc. Es decir, crece exponencialmente. Lo demuestro:
paso 1: 2 ejecuciones
paso 2: 2* (2 ejecucuciones)
paso 3: 2*(2*(2 ejecuciones))
paso k: (2^k) ejecuciones
¡Esto hay que evitarlo a toda costa! Pero no la recursividad en sí, sino dos llamadas recursivas que se encadenan. Si incrementamos los datos en mil el aumento de tiempo para el cálculo es mayor que la edad del universo.
Un ejemplo de un algoritmo exponencial es factorizar un número. Con algunas técnicas se ha logrado reducir, pero sigue siendo bastante exponencial. ¿Qué consecuencia tiene esto? Pues que multiplicar es fácil, pero separar en números primos no, así que esto se usa para compartir información de forma segura por Internet. Hace tiempo escribí sobre este tema en el blog.
Resumiendo, mirando nuestros algoritmos somos capaces de determinar cuál es la complejidad intentar evitar que sean cuadráticos o, sobretodo, exponenciales.
Tags Technorati: curiosidades, programación, informática
jueves, septiembre 17, 2009
Complejidad de los algoritmos (I)
Una cosa que no nos enseñan a los telecos es a programar bien. Vamos, que nos enseñan Java y C (u otros lenguajes, depende de la universidad) pero no tenemos la preparación que un Ingeniero Informático para estructurar un programa en condiciones.
Una cosa de la que había oído hablar pero que nunca vi en la carrera es la complejidad de un algoritmo programado. Es un concepto bastante básico y seguro que en algún plan de estudios de teleco se ve, pero no en la UPM. Intuitivamente ya había programado evitando ciertas malas costumbres, como bucles anidados, pero por experiencia propia y no porque me lo dijeran en la carrera.
Como quería aprender más del tema, estoy viendo unas clases del MIT sobre introducción a la programación, que además explican python, que es un lenguaje que me parece bastante adecuado para aprender (creo que he encontrado un sustituto para el Basic para enseñar a programar a mis hijos, cuando los tenga).
A lo que iba, ¿qué es la complejidad de un algoritmo? Definición para andar por casa: es lo que aumenta el tiempo de procesado si se aumenta la cantidad de datos de entrada del algoritmo. Por ejemplo, si tenemos un programa que calcula los números primos que hay desde 1 hasta un número que le demos (n) y aumentamos n, ¿cómo de lento se hace dicho programa?
La conclusión es que hay cuatro tiempos principales. El más intuitivo es el lineal. El tiempo aumenta linealmente con la cantidad de datos de la entrada. Por ejemplo, si le pedimos a nuestro programa los mil primeros primos y tarda 1 segundo y es lineal, podemos deducir que si le pedimos el primer millón de primos tardará mil segundos. Esto se denotaría O(n). Orden n, vamos, lineal.
Ahora bien, también está el tiempo cuadrático. Sería O(n²). Si tardamos en hacer los mil primeros primos 1 segundo, en hacer un millón tardamos un millón de segundos. Mucho peor.
También tenemos el caso logarítmico, en el que logramos una mejora considerable respecto al caso lineal. Esto sería O(log(n)) (donde log es el logaritmo en base 2). Con nuestro ejemplo anterior, si aumentamos de mil a un millón los primos que queremos, en el segundo caso tardaría unos 10 segundos. Una verdadera mejora respecto al caso lineal.
Ahora bien, también hay un caso horrible, y es el caso exponencial, donde O(2^n). ¡En este caso calcular el primer millón de primos llevaría 10^293 años! Un caso nefasto, ya que el universo no es tan antiguo. Hay que evitar este tipo de algoritmos siempre que se pueda.
En la siguiente entrada pondré ejemplos de algoritmos (con algo de código y también sin él) y su orden de complejidad.
Tags Technorati: curiosidades, programación, informática
Una cosa de la que había oído hablar pero que nunca vi en la carrera es la complejidad de un algoritmo programado. Es un concepto bastante básico y seguro que en algún plan de estudios de teleco se ve, pero no en la UPM. Intuitivamente ya había programado evitando ciertas malas costumbres, como bucles anidados, pero por experiencia propia y no porque me lo dijeran en la carrera.
Como quería aprender más del tema, estoy viendo unas clases del MIT sobre introducción a la programación, que además explican python, que es un lenguaje que me parece bastante adecuado para aprender (creo que he encontrado un sustituto para el Basic para enseñar a programar a mis hijos, cuando los tenga).
A lo que iba, ¿qué es la complejidad de un algoritmo? Definición para andar por casa: es lo que aumenta el tiempo de procesado si se aumenta la cantidad de datos de entrada del algoritmo. Por ejemplo, si tenemos un programa que calcula los números primos que hay desde 1 hasta un número que le demos (n) y aumentamos n, ¿cómo de lento se hace dicho programa?
La conclusión es que hay cuatro tiempos principales. El más intuitivo es el lineal. El tiempo aumenta linealmente con la cantidad de datos de la entrada. Por ejemplo, si le pedimos a nuestro programa los mil primeros primos y tarda 1 segundo y es lineal, podemos deducir que si le pedimos el primer millón de primos tardará mil segundos. Esto se denotaría O(n). Orden n, vamos, lineal.
Ahora bien, también está el tiempo cuadrático. Sería O(n²). Si tardamos en hacer los mil primeros primos 1 segundo, en hacer un millón tardamos un millón de segundos. Mucho peor.
También tenemos el caso logarítmico, en el que logramos una mejora considerable respecto al caso lineal. Esto sería O(log(n)) (donde log es el logaritmo en base 2). Con nuestro ejemplo anterior, si aumentamos de mil a un millón los primos que queremos, en el segundo caso tardaría unos 10 segundos. Una verdadera mejora respecto al caso lineal.
Ahora bien, también hay un caso horrible, y es el caso exponencial, donde O(2^n). ¡En este caso calcular el primer millón de primos llevaría 10^293 años! Un caso nefasto, ya que el universo no es tan antiguo. Hay que evitar este tipo de algoritmos siempre que se pueda.
En la siguiente entrada pondré ejemplos de algoritmos (con algo de código y también sin él) y su orden de complejidad.
Tags Technorati: curiosidades, programación, informática
jueves, septiembre 10, 2009
Gazpacho
El verano se acaba y con él el gazpacho. ¿Por qué una comida tan buena tiene que tener una temporada tan corta? ¿Por qué, si el que me gusta es el casero, no lo hago en invierno? ¿Por quéeeee? Como propósito de año nuevo (septiembre debería ser el inicio del año por la vuelta de vacaciones, la vuelta al cole y demás) voy a intentar comer más gazpacho fuera de temporada.
Mi receta es muy particular, seguro que no le gusta a la mayoría de la gente. Pero ahí va mi sugerencia de receta:
Ya sé lo que pensarán muchos: ¿Dónde está el pepino? ¿Dónde está la cebolla? ¿Por qué tan poco vinagre? Bueno, ya os dije, es mi receta personal, que se acerca al salmorejo pero sin llegar a serlo (para ser salmorejo no llevaría pimiento ni vinagre y llevaría bastante más aceite y pan).
Espero que os haya gustado. ¡Y salvemos al gazpacho de la soledad del verano!
Tags Technorati: recetas, gazpacho, verano
Mi receta es muy particular, seguro que no le gusta a la mayoría de la gente. Pero ahí va mi sugerencia de receta:
- 1 Kg de tomates
- 1 pimiento verde mediano (de los alargados)
- Un diente de ajo grande
- Medio vaso de aceite de oliva virgen extra
- Un chorro de vinagre de vino (así como un chupito)
- Sal
- Dos pedazos de pan empapados en agua (ya sé que "pedazo" no es una medida del sistema internacional, pero me refiero al típico pedazo individual de pan que coges de una barra)
Ya sé lo que pensarán muchos: ¿Dónde está el pepino? ¿Dónde está la cebolla? ¿Por qué tan poco vinagre? Bueno, ya os dije, es mi receta personal, que se acerca al salmorejo pero sin llegar a serlo (para ser salmorejo no llevaría pimiento ni vinagre y llevaría bastante más aceite y pan).
Espero que os haya gustado. ¡Y salvemos al gazpacho de la soledad del verano!
Tags Technorati: recetas, gazpacho, verano
sábado, septiembre 05, 2009
Libros mes de agosto
Este mes he leído:
Tags Technorati: libros, literatura
- The hundred secret senses - Amy Tan ***·· : Cuando empecé a leer este libro de Amy Tan pensé que se iba a dar una repetición de "El Club de la buena estrella", ya que muchas veces me parece que los estadounidenses de origen chino repiten mucho la misma historia, del conflicto generacional entre los padres nacidos en China y los hijos nacidos en EEUU. El shock, lo reconozco, debe ser enorme, pero ya he visto y leído demasiadas historias sobre dicho tema. Sin embargo este libro es completamente distinto. Sí, muestra las diferencias culturales entre los chinos y los estadounidenses, pero de una forma muy distinta, sin un choque generacional. Eso sí, el libro tiene algunas cosas que no me gustaron mucho, como es que la mitad de la historia es contada por "fantasmas". Pero aún así tiene su interés.
- Pastwatch: The redemption of Cristopher Columbus - Orson Scott Card *****: Después de leer "El juego de Ender" quería leer algo más del mismo autor, pero ya me habían recomendado que no siguiera con la saga, pues como ocurre con la mayoría de las sagas de ciencia ficción, el primer libro es espectacular y el resto no merecen la pena. Así que al ver este libro, cuya temática es nueva, y que además trata de "historia ficción", relacionado con Cristobal Colón, me interesó mucho. Y desde luego mereció la pena. Una mezcla muy interesante del pasado, el futuro, y pasados alternativos. Un ejercicio imaginativo muy interesante. Y muy bien llevado.
Tags Technorati: libros, literatura
Películas y series mes de agosto
Como todos los veranos, este ha sido un mes muy abundante en pelis.
Y las series que he terminado este mes:
Tags Technorati: películas, cine, series
- Mi vida en Grecia **···: Película intranscente, no en vano la vi en un avión cuando era del poco ocio que tenía a mano. Humor del tonto.
- Pagafantas ****·: Por fin una película dedicada al típico tío que no sólo no se come una rosca sino que encima tiene una amiga a la que le gustaría ligarse pero no puede. Es muy divertida.
- Supersalidos ***··: Divertida película de fiestas americana, cuyo personaje McLovin es simplemente genial. A veces abusa de chistes fáciles.
- Memories of Teardrops ***··: Costumbrista película de animación japonesa, sobre la vida de la protagonista. Algo lenta y sin mucho movimiento, pero tiene su encanto.
- Mi nombre es Harvey Milk *****: Buenísima película sobre este político/activista gay que tanto consiguió por los derechos de los homosexuales. Después de estar en San Francisco en el barrio de Castro, lo menos que podía hacer era ver esta estupenda película.
- Ice Age 2 ***··: No es tan buena como la primera parte pero aún así entretiene bastante y tiene escenas bastante graciosas.
- Futurama: Into the Wild Green Yonder *****: La última de las películas de Futurama, y como siempre muy divertida. Merece la pena y cierra de una forma muy interesante y abierta la serie, aunque ahora parece que va a haber una nueva temporada. Merece la pena.
- Pollock ***··: Película sobre la vida del famoso pintor. La película está muy bien realizada, aunque desde luego el artista era de todo menos una persona con la que convivir. Interesante.
- Resacón en las vegas ****·: Graciosa película sobre una despedida de solteros en la que, curiosamente, la despedida no aparece en ningún momento. Sorprendente, y por ello una de las revelaciones de la temporada.
- JCVD ****·: Buenísima película de Jean-Claude Van Damme en la que se protagoniza a sí mismo, un actor fracasado que ya no es capaz de pagar sus deudas. Muy divertida y con una trama muy interesante.
- Man on wire ****·: Documental sobre el funambulista que caminó entre las torres gemelas de Nueva York, y por supuesto sin ningún permiso. Muy interesante.
- Mapa de los sonidos de Tokyo *····: Una película llena de tópicos, que abusa de sexo explícito, que cuenta una historia poco creíble, y que no hace más que mostrar curiosidades sobre Tokyo sin venir a cuento. Una gran decepción. Con lo que me gusta Coixet y sale con estas.
- Up *****: La primera película que veo en 3D. Y me ha gustado, tanto que sea en 3D como la historia. Es muy divertida, a pesar de que tiene momentos bastante tristes, cosa sorprendente para una película de dibujos animados.
Y las series que he terminado este mes:
- The Big Bang Theory - Temporada 1 *****: Estupenda serie sobre unos amigos bastante frikis que trabajan como investigadores de física en la universidad de Caltech. Llena de curiosidades, pero sobretodo muy graciosa.
Tags Technorati: películas, cine, series
Suscribirse a:
Entradas (Atom)