Novanebula blog

    Como ya habíamos afirmado en el artículo sobre la medición de la complejidad, un algoritmo se puede clasificar en cuando a su eficiencia o coste en una de la siguientes categorías. De mayor eficiencia a menor, siendo n el tamaño del problema a tratar:

* Complejidad constante (la mejor y objetivo a buscar) O(1)
* Complejidad logarítmica (muy buena) O(log n)
* Complejidad lineal O(n)
* Complejidad lineal*logarítmica O(n log n)
* Complejidad cuadrática O(n²)
* Complejidad polinomial (mala) O(n^a) con a>2
* Complejidad exponencial (muy mala) O(aⁿ) con a>2
* Complejidad factorial (la peor, problemas generalmente intratables) O(n!)

    Tenemos pues que en cuanto a complejidad algorítmica:

1 << log n << n << nlog n << n² << n³ << ... << 2ⁿ << n!

    A menor orden menos recursos se necesitarán para llevar a cabo la resolución del problema, menor coste.

    Lo que nos puede interesar a continuación es obtener un conjunto de reglas prácticas que no sirvan para determinar la complejidad de un algoritmo y así por ejemplo poder comparar varios algoritmos y determinar cual es el mejor. Estas reglas no pueden por desgracia, tras seguirlas detenidamente, llevarnos a determinar con exactitud el coste de un algoritmo pero son útiles para ayudarnos en este empeño.

    Estas reglas deben tener en consideración los costes de:

*Instrucciones simples
*Composición de instrucciones
*Instrucciones de selección
*Bucles
*Subprogramas

    Los 3 elementos a continuación tienen una ejecución en tiempo (coste) constante, O(1)

* Instrucciones simples: la evaluación de expresiones aritméticas siempre que estas sean de tamaño constante así como la comparación de datos simples.
*Las operaciones de asignación, lectura y escritura de datos simples
*Accesos a elementos de un array, a un campo de un registro y a la siguiente posición de un registro de un archivo

    La composición de instrucciones que dependan del tamaño n del problema el coste será igual a la suma de los costes.

    Para las instrucciones de selección en que varios partes del código pueden ser o no ejecutadas según la condición que defina la selección se toma como coste el coste de la peor rama.

    Para los bucles si estos dependen del tamaño del problema se considera orden lineal, pero si están anidados por cada anidación que dependa del tamaño del problema multiplicaremos por n el coste dando lugar a coste cuadráticos, polinómicos o incluso exponenciales

    Para subprogramas resulta de aplicar las anteriores reglas al subprograma, si el número de llamadas al subprograma depende del tamaño del programa (tener en cuenta posibles recursividades) el orden sera mayor dependiendo de como crezca el número de llamadas con el tamaño.

    Si se descompone el coste en partes tenemos que el coste de la unión de cada parte es igual a la que tiene un costo mayor. Es decir si tenemos una parte con un coste lineal y a continuación otra parte con coste cuadrático la unión de las dos nos dará un coste cuadrático (regla de la suma)

    Vamos a continuación a poner dos implementaciones en C de dos algoritmos diferentes para llevar a cabo el mismo problema. Se trata de, a partir de dos números enteros distintos, obtener la suma de todos los números que hay entre ellos incluidos ellos mismos. Por ejemplo si tenemos el 5 y el 10 el algoritmo debe ser capaz de calcular la suma:

5+6+7+8+9+10

Continua leyendo "Complejidad algorítmica"

Publicado por Abraham Covelo

   ETA ha perpetrado otro atentado con coche bomba dirigido contra la casa cuartel de la Guardia Civil en La Rioja. La banda avisó de la colocación del artefacto minutos antes de su explosión. Afortunadamente no hubo que lamentar ninguna muerte. Cientos de personas asistieron a una manifestación convocada por el Ayuntamiento presidido por Javier Pagola para mostrar su repulsa por el atentado.

   El SOS Rioja prestó atención psicológica a los afectados. Y se observó un tremendo despliegue policial cuando llegaron el secretario de Estado de Seguridad, Antonio Camacho, y el director general de la Policía y la Guardia Civil, Joan Mesquina.

   El artefacto afectó a edificios, tiendas y algunos coches en las proximidades de la detonación, situado en una de las principales calles de la localidad. La rápida actuación de la policía que logró desalojar la calle en 15 minutos evitó una masacre.

Publicado por Abraham Covelo

    El conductor que hace poco más de una año fue cazado por un radar circulando a 260 Km/h por la autopista A-231 (León-Burgos) reclama ahora al Estado, es decir a todos nosotros, una indemnización por valor de 313.454.

    Recordemos que en el juicio se le imputaba un delito por conducción temeraria del que fue absuelto. El conductor estuvo durante 13 meses privado de carné de conducir (se le retiro el carné de forma cautelar) y además aduce que ha sufrido daños y perjuicios morales pues su nombre y foto apareció en mucho medios de comunicación. Recordemos que además fue el mismo el que realizó una rueda de prensa tras lo sucedido.

    Tal vez debería volver a celebrarse al primer juicio y también sentar al juez que dictó esa primera sentencia en otro juicio paralelo.

    Mas información en la página de telecinco

Publicado por Abraham Covelo

    La función clone realiza una tarea similar a fork, crear procesos hijos al proceso que lo ejecuta. A diferencia del fork, clone permite que el proceso hijo comparta partes de su contexto de ejecución con el proceso padre, como el espacio de memoria, la tabla de descriptores de fichero y la tabla de manejadores de señales (signal handler). El uso que habitualmente se le da a clone es para implementar hilos de ejecución (threads): múltiples hilos de ejecución de control en un programa que corre en un espacio de memoria compartido.

 La función clone está definida en el archivo de cabecera sched.h y esta es su firma:

int clone (int (*fn) (void *), void *child_stack, int flags, void *arg);

    Cuando se crea un proceso hijo con clone se ejecuta la función fn(arg). El argumento fn es un puntero a una función. El entero que debe retornar esa función será el código de salida del proceso hijo. El proceso hijo podría también finalizar explicitamente mediante una llamada a exit o después de recibir una señal fatal.

    El argumento child_stack especifica la posición de la pila usada por el proceso hijo. Ya que el proceso hijo y el padre pueden compartir la misma memoria, no es posible que el proceso hijo ejecute la misma pila que el proceso padre. El proceso padre (el que invoca la función clone) prepara un espacio de memoria para la pila del hijo y le pasa un puntero a este espacio mediante este argumento.

    El argumento entero flag es un OR de varias constantes que especifican que es compartido entre padre e hijo:

CLONE_PARENT, CLONE_FS, CLONE_FILES, CLONE_NEWSNS, CLONE_SIGHAND, CLONE_PTRACE, CLONE_UNTRACED, CLONE_STOPPED, CLONE_VFORK, CLONE_VM, CLONE_PID, CLONE_THREAD, CLONE_SYSVEM, CLONE_SETTLS, CLONE_PARENT_SETTID, CLONE_CHILD_SETTID, CLONE_CHILD_CLEARID

    clone es una función que realiza un llamada de sistema (system call) a sys_clone que sólo precisa los argumentos flags y child_stack que tienen el mismo significado que para el caso de la función.

    La función clone retorna el TID (Thread ID, identificador del hilo) o -1 en caso de fallo y errno será asignado apropiadamente describiendo el error.

    A continuación vemos un ejemplo sencillo de la utilización de esta función:

#include <sched.h>

#include <stdio.h>

#include  <time.h>

#include  <malloc.h>



int cloneando()

{

        printf("Hola mundo clonado\n");

}

int main(int argc,char** argv)

{

        void **pila_hijo;

        pila_hijo = malloc(1000);

        clone(cloneando,pila_hijo, CLONE_VM|CLONE_FILES, NULL);

        sleep(1);

        printf("Hola mundo real\n");



        return 0;

}

    Espero que el articulo os sirva de ayuda, pero si necesitáis alguna aclaración escribid un comentario a este artículo

Publicado por Abraham Covelo