Vikman's Blog

Esta historia parte de un pequeño proyecto de antaño en el que intenté implementar la herramienta de relleno de Paint o Photoshop. Estamos hablando de un algoritmo de relleno por difusión : el objetivo es pasar por todos los puntos no coloreados partiendo de uno arbitrario y la solución se antojaba sencilla: un algoritmo de  backtracking .  Estuve cerca de lograrlo pero cuando la superficie a rellenar era medianamente grande, el programa se colgaba por desbordamiento de pila . El problema es que, al tratarse de una función recursiva , con cada paso que daba había que guardar en la pila el punto anterior, y si el espacio es grande podemos estar hablando de miles o millones de pasos. Esta información se guarda en la pila de llamadas , una zona de memoria especialmente rápida... y pequeña. La solución es muy fácil: convertir la función recursiva en iterativa , y guardar cada punto a explorar dentro de un contenedor de pila ( QStack en la biblioteca Qt), cu...

Los Milestones volvemos a la carga y estaremos este fin de semana en Alexis Viernes ,  un conocido restaurante sito entre Atarfe y Santa Fe, con música en vivo. Tocaremos versiones de los 70's y 80's, junto a temas más actuales. Entre nuestro repertorio están Donna Summer, Elvis Presley, Tina Turner, Blues Brothers y Bee Gees. ¡La entrada es gratis!  Os esperamos allí el sábado a las 12 de la noche (entre sábado y domingo).

Ayer eliminé por accidente todos los administradores de mi ordenador. Sin administradores no podremos realizar cambios en el equipo, así que podemos, o bien reinstalar Windows, o bien solucionar el problema más elegantemente.  Hoy vamos a ver cómo entrar en Windows, aprovechando una vulnerabilidad de seguridad . Será como olvidar las llaves dentro de casa, y no tener más remedio que entrar por una ventana abierta —y nunca mejor dicho, hablando de Windows—. StickyKeys   es una característica de accesibilidad de Windows que permite pulsar las teclas especiales de una en una (en lugar de mantenerlas pulsadas) y se activa pulsando la tecla Mayúsculas cinco veces. Lo que hace realmente es ejecutar el programa sethc.exe , y lo mejor de todo: funciona incluso en la pantalla de bienvenida, ¡en modo Administrador! ¿Y por qué no lo cambiamos por la consola? Todo lo que tenemos que hacer es reiniciar el ordenador (en Windows 8 no sirve apagar, porque hiberna el kernel ...

Los lenguajes de programación son los que nos permiten describir programas mediante estructuras de datos y algoritmos . Hay una gran cantidad de lenguajes de programación, cada uno enfocado a un objetivo y con sus pros y contras.  Aunque podemos agruparlos de muchas maneras, se clasifican principalmente en tres paradigmas: Imperativos. Describen mediante instrucciones cómo realizar una tarea. Los más conocidos son C y Fortran. Declarativos. Describen el problema declarando condiciones, proposiciones y restricciones. Aquí tenemos a Prolog y LISP. Orientados a objetos. Utiliza clases y objetos que interaccionan entre sí para diseñar aplicaciones. C++, Java y Python son algunos de ellos. Los primeros son los más clásicos, empezando por el ensamblador, el de más bajo nivel, del que nos abstraen otros lenguajes de alto nivel; son muy eficientes. La programación declarativa no describe la solución, sino el problema; es más expresiva y será el programa intérprete el que...

La programación paralela, esa gran desconocida... Muchos de nosotros ya tenemos ordenadores, o incluso teléfonos móviles y tablets con capacidad para ejecutar varias instrucciones a la vez. Hacer un programa que aproveche este potencial no es muy difícil en la mayoría de los casos. Los procesadores de hoy en día nos permiten paralelizar programas mediante dos mecanismos: Multinúcleo o multihebra. Dos procesos se pueden ejecutar simultáneamente en el mismo procesador, cada uno en un núcleo. Instrucciones SIMD. Single Instruction, Multiple Data . Se trata de instrucciones que se aplican a varios datos a la vez. La primera tecnología es más conocida: procesadores como los Intel Core Duo llevan dos núcleos, incluso algunos de ellos utilizan HyperThreading , que brinda dos hebras por cada núcleo físico, el sistema operativo ve dos procesadores donde hay sólo uno, y entrega las tareas de dos en dos, ganando un poco de velocidad extra. Son muchas las herramientas que tene...

El problema de las ocho reinas es un juego que consiste en colocar ocho reinas en un ajedrez sin que se amenacen entre sí. La solución a este problema se encuentra con un algoritmo de backtracking , que consiste en asignar una fila a cada reina, y progresivamente colocar cada reina en una posición diferente. Si una reina es amenazada en cualquier casilla de su fila, la retiramos y colocamos la reina anterior en otra posición. El programa termina cuando se ha conseguido colocar a todas las reinas en posiciones seguras. Aquí dejo una propuesta dinámica para N reinas, en lenguaje C: >>  Descargar reinas.c  << Mejorando el algoritmo Tiempo después de publicar originalmente este post, estudié que éste es realmente un problema de satisfacción de restricciones . Resolver un problema NP completo puede costarnos mucho tiempo, ya que el espacio de búsqueda crece enormemente respecto al tamaño del problema. La aproximación por backtracking  "a...

VirtualBox tiene una opción para automontar carpetas compartidas en un huésped Linux, pero no siempre funciona bien. Hace tiempo propusimos un script para hacerlo manualmente . En esta ocasión vamos a hacer que se monten automáticamente . Supongamos que tenemos una carpeta compartida llamada Datos. La forma más sencilla de montarla en nuestro huésped es escribir en el terminal: sudo mkdir /media/Datos sudo mount -t vboxsf Datos /media/Datos El problema es que al hacerlo como superusuario, el dueño de la carpeta es root , y no se monta con el conjunto de permisos más adecuado. Para cambiar esto, vemos la ayuda del programa /sbin/mount.vboxsf y aplicamos las opciones pertinentes. Tutorial: Permisos en Linux Bien es sabido que la seguridad de Linux descansa en su sistema de archivos. Si escribimos ls -l en cualquier carpeta, podemos ver los conjuntos de permisos RWX que tiene cada elemento. R= Read , W= Write , X= Execute . La primera tríada es para el usuario prop...