Problema de Parada (o problema de Halting)

Vamos con un poco de teoría de la computación ¿Qué es el problema de paro, de parada o de Halting? Consiste en determinar si existe una máquina de Turing capaz de determinar si cualquier Máquina de Turing se va a detener o no. Dada una máquina de Turing M y una palabra w se determinará si M acabará en un número finito de pasos usando w como dato de entrada.

El problema es indecidible, según el propio Turing ninguna máquina de Turing puede resolverlo. Es decir, no puede existir un programa genérico que demuestre que todos los programas del mundo terminan, se puede hacer para un programa concreto pero no existe la solución general.

Existen varias demostraciones de por qué es indecidible, vamos a ver una demostración escrita en javascript.

Imaginemos que alguien escribe una función f que recibe como parámetros una función y sus argumentos, y que tiene un código capaz de comprobar si esta se detendrá o no.

var f = function (funcion, argumentos) { ... }; // Aquí iría un código correcto que supuestamente calcularía si la máquina para o no

Vamos a suponer que esa función está correcta, funciona y nos devuelve true si el programa termina, y false si caería en un bucle infinito. Entonces podríamos usarla como subrutina dentro de otra función más grande llamada g como la que viene a continuación:

var g = function (funcion) {
//Pasamos en el parámetro funcion la función y sus argumentos 
  if (f(funcion,funcion)) {
    while (true); //esto provoca un bucle infinito
  }
  else {
    return false;
  }
}

Esto vendría a decir que g(funcion) termina siempre y cuando funcion(funcion) nunca termina.

Entonces ¿qué ocurre si la pasásemos a la función g como parámetro su propio código? Es decir ¿qué pasa si g evalúa a g? Pues que llegamos a una contradicción: g(g) termina siempre y cuando g(g) nunca termina. Por tanto, al llevarnos a una paradoja dicho algoritmo no puede existir.

Anuncios

Diferencia entre corriente alterna y continua

En el pasado ya hablamos un poco de electrónica básica cuando vimos las magnitudes existentes en un circuito eléctrico. Hoy vamos a hablar de los distintos tipos de corriente.

La corriente eléctrica es el flujo de carga eléctrica que recorre un material, debido al movimiento de electrones. Según el sentido en que se muevan estas cargas de electrones podemos distinguir dos tipos de corriente: alterna y continua.

Corriente Continua:

Es el tipo de corriente que vemos en baterías y generadores. En este caso la electricidad mantiene una intensidad constante y el flujo de electrones se mueve en un solo sentido.

En castellano se abrevia como CC mientras que en inglés se usan las siglas DC.

Corriente Alterna:

Es el tipo de corriente más común en las instalaciones domésticas, puesto que permite utilizar un mayor voltaje para que la corriente viaje a mayor distancia, pudiendo utilizar luego transformadores para rebajar dicho voltaje si es necesario.

En este caso las cargas de electrones cambian de sentido constantemente. Los cambios de sentido en el flujo de electrones se producen muy rápido, varias veces por segundo. La frecuencia de cambio se mide en hercios, que son el número de ciclos por segundo. Esta corriente no tiene una polaridad definida, ya que dependiendo al orden esta puede ser tanto positiva como negativa, por esto puede alternar su polaridad.

En castellano se abrevia como CA mientras que en inglés se usan las siglas AC.

En resumen:

La diferencia principal entre corriente alterna y continua está en el sentido del flujo de sus electrones: la corriente continua se desplaza en línea recta mientras que la corriente alterna, a medida de su paso y velocidad, toca ambas polaridades.

La corriente alterna nos permite conectar un aparato a un enchufe sin que importe donde está el polo positivo o el negativo, mientras que en la corriente continua las conexiones han de realizarse conectando siempre el polo positivo y el negativo de forma adecuada para que funcione.

Magnitudes básicas de un circuito eléctrico

No hace mucho veíamos en un artículo sobre Javascript cómo realizar cálculos basados en la ley de Ohm. Esta vez vamos a alejarnos un poco de los lenguajes de programación y a darle un repaso a la física básica ¿Cuáles son las principales magnitudes que podemos medir en un circuito eléctrico?

Diferencia de Potencial:

También llamada tensión o voltaje, indica la diferencia de energía entre dos puntos de un circuito. La diferencia de potencial que existe entre los polos del generador o entre los puntos cualquiera del circuito es la causa de que los electrones circulen por el circuito, si este se encuentra cerrado. Es una medida de la fuerza que hay que comunicar a los electrones para que se muevan y su unidad de medida es el Voltio (V).

Intensidad:

La intensidad sería la cantidad de carga eléctrica que circula por un circuito en la unidad de tiempo, que mediríamos en segundos. La unidad con la que mediríamos la intesidad es el Amperio (A).

Resistencia:

Se trata de la propiedad que tienen los cuerpos para dificultar el paso de la energía. Cuanto menor sea esta mejor conductor será esa sustancia. La resistencia de un conductor depende tanto del tipo de material del que está compuesto como de su longitud y de su sección. Denominaremos estos factores resistividad (ρ), longitud (l) y sección del conductor (S). La unidad de medida de resistencia es el Ohmnio (Ω).

Para calcularla debemos multiplicar la resistividad por la longitud dividida entre la sección. Lo expresaríamos con la fórmula: R = ρ * l / S.

Calculando potencia y energía

En base a lo visto arriba podríamos calcular cuánta es la energía consumida por un aparato eléctrico en una unidad de tiempo. Esto sería la potencia del aparato.

Potencia:

La mediríamos en Watios (W).

Tenemos dos fórmulas para calcularla: multiplicar el voltaje por la intensidad o multiplicar el cuadrado de la intensidad por la resistencia. La primera fórmula la expresaríamos como P = V * I y la segunda sería P = I2 * R

Energía eléctrica:

Y acabaríamos con la energía consumida por un circuito eléctrico medida en Julios (J).

Podemos calcularla multiplicando la potencia del circuito (que acabamos de ver cómo calcular) por el tiempo que está en uso (en segundos). La fórmula para esto la expresaríamos como E = P * t

¿Y saber esto para qué me vale?

Es la típica pregunta de adolescente ¿para qué me vale saber esto si no voy a ser electricista? Pues por ejemplo entenderlo te ayudará a calcular qué potencia necesitas contratar para tu casa en tu contrato de la luz, o a calcular cuántos paneles solares necesitarías en caso de querer ponerte a producir tu propia energía.

En España el grueso de la factura depende de la cantidad de potencia contratada. La potencia contratada vendría a ser la cantidad de watios que podemos estar consumiendo a la vez en nuestra casa, que lo puedes entender como la suma de la potencia de todas las luces y electrodomésticos que podemos estar utilizando a la vez. Puedes leer más sobre el tema de la contratación de energía en este blog.

Orden de operaciones aritméticas (PEMDAS) y su aplicación en lenguajes de programación.

Todo un clásico en las redes sociales es que alguien comparta la operación 5+4/3-1*2 y que se monte un gallinero tremendo en los comentarios con distintas soluciones. Esto se debe a que mucha gente no tiene claro cómo va la jerarquía de las operaciones y el orden de evaluación de las mismas.

Si hablamos de operaciones básicas, y de la mayoría de lenguajes de programación (Javascript, PHP, Python, Ruby, C,Visual Basic, Java…), nos regiremos por el orden de operaciones conocido por el acrónimo inglés PEMDAS, que en castellano podríamos traducir como PAPOMUDAS (PAréntesis, POtencias, MUltiplicación, División, Adición, Sustracción). En base a esto el orden de operaciones en lenguajes de programación como Python, PHP, Ruby o Javascript sería:

  1. Paréntesis
  2. Potencias y radicales
  3. Multiplicación, división, división entera y módulo.
  4. Suma y resta.

En este enlace puedes comprobar los resultados de distintas operaciones realizados en distintos lenguajes de programación. Puedes copiar los siguientes ejemplos para comprobar que el resultado es el mismo.

Aquí el código en Javascript:

var resultado = 5+4/3-1*2;
console.log(resultado);

Aquí el código en Python:

resultado = 5+4/3-1*2
print(resultado)

Aquí en Java:

public class Test {
  public static void main(String[] args){
    System.out.println(5.0+4.0/3.0-1.0*2.0);
  }
}

Y aquí en C:

void main(void) {
   double resultado;
   resultado = 5.0+4.0/3.0-1.0*2.0;
   printf("%f",resultado);
}

Como puedes comprobar, en todos el resultado es 4.333333 ya que todos usan el mismo orden para las operaciones.

Cálculo del logaritmo y logaritmo neperiano en Javascript.

Ayer me mandaban este chiste por Whatsapp:

Y como soy así de tocahuevos, que hasta llevo un reloj calculadora Casio, les mandé de vuelta el resultado del logaritmo neperiano de 1437. Y sí, estoy escribiendo esto para cuando me lo vuelvan a mandar, para contestar con este enlace, que me vale tanto para la sección de programación como para la de ciencia.

El elcálculo de logaritmos es la operación inversa a la exponenciación de la base del logaritmo. El desarrollo de calculadoras y ordenadores ha hecho que las tablas de logaritmos, que se usaban hace años para simplificar operaciones complejas, hayan perdido mucha importancia para los estudiantes de matemáticas en la actualidad. Este blog nos da una entrada muy intersante sobre el uso de los logaritmos.

La clase Math de Javascript tiene varias funciones para calcular un logaritmo. Para el logaritmo natural (logaritmo cuya base es el número e, un número irracional cuyo valor aproximado es 2,7182818284590452353602874713527):

//vamos a calcular el logaritmo de 5
var logaritmo = Math.log(5);

¿Y para obtener el logaritmo en base 10?

//vamos a calcular el logaritmo de 5
//pero con base decimal
var logaritmo = Math.log10(5);

¿Y para obtener el logaritmo en base 2?

//vamos a calcular el logaritmo de 5
//pero con base binaria
var logaritmo = Math.log2(5);

¿Y el logaritmo neperiano? Bueno, en lenguaje coloquial suele llamarse logaritmo neperiano al logaritmo natural, pero si nos ponemos precisos son dos conceptos disintos. El logaritmo neperiano, nombrado en honor del matemático John Napier, se calcularía con la fórmula -107*ln(x/-107):

//vamos a calcular el logaritmo neperiano
//de 5.
var logaritmo = Math.pow(-10,7)*Mat.log(5/Math.pow(-10,7))

Como puedes ver los logaritmos neperianos son esencialmente logaritmos naturales con la coma desplazada siete posiciones hacia la derecha y el signo invertido.

¿Qué es una función hash?

Ayer comentaba en Facebook que una cadena alfanumérica que aparecía en una noticia “parecía el resultado de alguna función hash” y hubo gente que me preguntó qué era eso de una función hash. Así que he pensado que lo mejor será contarlo por aquí que me puedo extender más.

Cifrado

Las funciones hash, también llamadas “digest” o “de resumen“, son algoritmos que calculan y devuelven una cadena de texto alfanumérica de longitud fija calculada a partir de un dato de entrada, que puede ser un texto o un fichero binario. Se trata de funciones unidireccionales, lo que quiere decir que aun teniendo el resultado y conociendo el algoritmo no debe ser posible revertir las operaciones para descifrar el dato de entrada.

Son también funciones determinísticas, siempre devuelven la misma salida para la misma entrada. Al ser resúmenes existe la posibilidad de que dos entradas totalmente distintas devuelvan el mismo resultado, es lo que se llama una “colisión“. Teóricamente es imposible crear una función hash sin colisiones, puesto que las posibilidades de entrada son infinitas pero las de salida están limitadas a la longitud de la cadena de resumen, por tanto a mayor logitud de respuesta menor posibilidad de colisión y mayor robustez para el algoritmo. Las colisiones son lo que facilita un tipo de ataque criptográfico llamado “Ataque de Cumpleaños” del que puedes leer en ese enlace.

Por ejemplo, si calculo el hash de la cadena “hola” con el algoritmo md5 el resultado será: 4d186321c1a7f0f354b297e8914ab240. En cambio si le paso la cadena “Hola“, con mayúscula, el resultado devuelto será: f688ae26e9cfa3ba6235477831d5122e.

¿Qué utilidad tiene esto? Bueno, no se trata de un algoritmo para cifrar un mensaje y poder descifrarlo luego, como pueda ser el caso de AES, no tiene el mismo propósito que la criptografía simétrica o asimétrica. Las funciones hash son útiles por ejemplo para almacenar contraseñas en una base de datos, ya que aunque alguien lograra acceder a ellas no podría descifrar cual es la contraseña original. Otro de sus principales usos es asegurar que un fichero no ha sido modificado durante el trayecto desde su envío: se calcula el hash antes de enviarlo, si al recibirlo lo volvemos a calcular y el resultado no es el mismo implica que alguien ha capturado (un ataque de intermediario o man in the middle) y modificado el fichero. Las funciones hash también se utilizan en los procesos de firma digital de documentos.

¿Cuales son los algoritmos de resumen más populares o más comunes? Te dejo una lista con sus enlaces a Wikipedia:

Diferencia entre muestra y población.

Población y Muestra son dos términos usados en estudios de estadística, similares y relacionados. Por dicha similitud tienden a ser confundidos, por lo que es importante que sepamos diferenciarlos para no tomar, literalmente, la parte por el todo.

La población, también llamada universo, es un conjunto de elementos sobre los que se realizan estudios y observaciones. Se trata de una variable o magnitud aleatoria con unas determinadas características comunes. Es, en resumen, el conjunto formado por todos los elementos a estudiar. Pero hay casos en los que el total de la población adquiere una magnitud demasiado extensa para ser estudiada. Por ejemplo, si queremos hacer un estudio sobre la salud cardiovascular en la Unión Europea no podemos pretender usa datos de todos los ciudadanos con historiales médicos.

La muestra es una selección abarcable de parte de una población para su estudio. Por definición, la muestra se siempre una parte de la población. Esta debe ser representativa, por lo que el método de selección debe ser adecuado (preferiblemente aleatorio) para evitar acabar teniendo un muestra sesgada que nos de un resultado irreal (decía un catedrático en estadística que un muestreo suficientemente torturado puede demostrar cualquier cosa). Siguiendo el ejemplo anterior, si hacemos el estudio sobre salud cardiovascular eligiendo solo a gente de entre 20 y 30 años y lo repetimos después con gente de más de 70, el resultado obtenido será radicalmente distinto.

Si la selección del muestreo es adecuada el resultado del estudio sobre una muestra será más preciso que al realizarlo sobre el total de la población, dado que trabajamos sobre un conjunto de datos más pequeño y esto nos permitirá minimizar errores.

En resumen: La población es el total de individuos o elementos que queremos estudiar y la muestra es una selección aleatoria de elementos de esa población que utilizaremos para trabajar de forma más precisa.