Metodo: Divide y venceras

En las ciencias de la computación, el término divide y vencerás (DYV) hace referencia a uno de los más importantes paradigmas de diseño algorítmico. El método está basado en la resolución recursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar. El proceso continúa hasta que éstos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original.

Esta técnica es la base de los algoritmos eficientes para casi cualquier tipo de problema como, por ejemplo, algoritmos de ordenamiento, multiplicar números grandes, análisis sintácticos y la transformada discreta de Fourier.

¿En que problemas se utiliza?

1. Multiplicacion rapida de enteros largos
2. multiplicacion rapida de matrices
3. Ordenacion por mezcla y ordenacion rapida
4. Problema de seleccion.

 Un ejemplo:

Multiplicación de enteros grandes

Enunciado del problema 
las operaciones aritméticas entre números enteros suelen considerarse operaciones elementales siempre y cuando los números que intervienen no superen los límites de representación. Cuando esto ocurre, hay que acudir a otro tipo de representación, por ejemplo los arrays, y utilizar los algoritmos clásicos de las operaciones aritméticas. El problema planteado consiste en saber si existe alguna forma de reducir el coste en el caso de la multiplicación, ya que el algoritmo clásico de multiplicación es de orden cuadrático. Como alternativa, se podría utilizar el esquema de multiplicación por duplicación, pero no ofrece mejoras en cuanto a tiempo de ejecución.

Solución
considérense dos números enteros, u y v, de n dígitos cada uno.

1. Algoritmo básico: la idea a seguir es descomponer los dos números en la suma de otros dos. Más concretamente, sea S la parte entera de n/2, la descomposición consiste en dividir los números entre 10S:

u → w representa el cociente y x el resto → u = 10S·w + x

v → y representa el cociente y z el resto → v = 10S·y + z

Luego:

u·v = (10S·w + x)·(10S·y + z) = 102S·w·y + 10S·(w·z + x·y) + x·z

A continuación, se calculan las suboperaciones w·y, w·z, x·y y x·z. Si los operandos (w, x, y, z) son:

- “pequeños”, entonces se multiplican de la forma clásica.

- “suficientemente grandes”, se aplica de nuevo el algoritmo y se calculan recursivamente las multiplicaciones de los respectivos sumandos.

2. Algoritmo mejorado: al realizar cuatro multiplicaciones de tamaño mitad en cada llamada, el coste resultante es T(n) = 4·T(n/2) + g(n), donde g(n) es el tiempo invertido en sumas, desplazamientos y operaciones adicionales sencillas, por lo que el algoritmo sigue siendo de orden cuadrático.

Dado que se necesitan realizar cuatro multiplicaciones de tamaño mitad, no se mejora el tiempo de ejecución respecto a los algoritmos clásicos. Para intentar reducirlo, es preciso evitar alguna de esas multiplicaciones. La clave de la mejora consiste en advertir que no es necesario calcular w·z y x·y, si no la suma de ambos. Así, se considera r = (w + x)·(y + z) = w·y + (w·z + x·y) + x·z , con los que las multiplicaciones a realizar son:

p = w·y

q = x·z

r = (w + x)·(y + z)

, hallando la suma de la siguiente forma:

(w·z + x·y) = r – p - q

Así, volviendo al producto anterior:

u·v = (10S·w + x)·(10S·y + z) = 102S·w·y + 10S·(w·z + x·y) + x·z = 102S·p + 10S·(r – p - q) + q

, teniendo que calcular las multiplicaciones p, q y r. Si sus operandos (w, x, y, z) son:

- “pequeños”, entonces se multiplican de la forma clásica.

- “suficientemente grandes” se aplica de nuevo la descomposición anterior, y calculamos recursivamente las multiplicaciones de los respectivos sumandos.

¿Cuando conviene utilizarlo y cuando no?

Principalmente este método nos conviene utilizarlo en problemas muy complejos, ya que como se menciona en la descripción se divide un problema en varios sub-problemas para hacerlo más sencillo y estos a su vez se pueden dividir si es necesario.

No nos conviene utilizarlo cuando el resultado final del problema original no es la suma de los resultados de los sub-problemas.

El método esta diseñado para problemas complejos pero no es conveniente sub-dividir tanto el original ya que el método es muy lento y entre más dividamos el problema más tiempo tomara llegar a la solución.

Ejemplo

Primeramente lo que tenemos que hacer en ese caso de divide y venceras es lo siguiente

1. Sabes de lo que se tratara el problema que tenemos que resolver y después sacar ciertos subproblemas (mas pequeños ) pero que sea el mismo resultado.
2. Resolver cada problema de manera independiente
3. Por ultimo hacer las combinaciones posibles , hasta que el resultado sea el buscado

Estructuras de datos

Estructuras de datos

Una estructura de datos es la forma en la que se organiza un conjunto de datos con el objetivo de facilitar su manipulación. Las estructuras de datos muestran la manera lógica y congruente de como relacionar los datos, la forma en la que se organiza la información y que sera almacenada y procesada por el software.

Arreglos

Un arreglo es un un grupo o colección finita de elementos que se encuentran ubicados en forma consecutiva. Hay 3 tipos de arreglos: de una dimensión, bidimensionales y de 3 o mas dimensiones.

A continuacion un ejemplo:

#include <iostream> #include <cstdlib> #include <ctime> using namespace std; int main () {     srand(time (0));     for (int i=0; i<=1; i ++); {             cout << 1+(rand()%6)  << endl;             }            system("PAUSE");    return 0;                     }

Cadena

Es una secuencia ordenada de longitud finita de elementos, la cual es una sucesion de caracters letras, numeros u otros signos.

A continuacion un ejemplo:

#include <stdio.h> #include <string.h> #include <windows.h> main() {     char nombre[20];     printf( "Introduzca su nombre (20 letras maximo): " );     scanf( "%s", nombre );         int longitud;     longitud = strlen(nombre);     printf( "Su nombre \"%s\" tiene %i caracteres.\n", nombre, longitud );     system("PAUSE");      }

LISTA

Es una colección de elementos dispuestos uno detrás del otro, en la que cada elemento se conecta al siguiente por un "Enlace" o "Puntero".

Como se observa en la imagen, los nodos de las listas al igual que las colas y pilas, está compuesta por una parte de información y el puntero que mantiene el enlace entre un nodo y otro.

Existen varios tipos de Listas, pero para efectos de comprensión y sintetización, hablaremos de cuatro tipos esenciales de listas:

• Lista Simplemente enlazada
• Listas doblemente enlazadas
• Listas Circulares
• Lista circular doblemente enlazada

A continuacion un ejemplo:

#include <stdlib.h> struct lista { int clave; struct lista *sig; }; int main(void) { struct lista *L; struct lista *p; int i; L = NULL; /* Crea una lista vacia */ for (i = 4; i >= 1; i--) { /* Reserva memoria para un nodo */ p = (struct lista *) malloc(sizeof(struct lista)); p->clave = i; /* Introduce la informacion */ p->sig = L; /* reorganiza */ L = p; /* los enlaces */ } return 0; }

 

Pila

La pila que permite almacenar datos en el orden LIFO (Last In First Out) en español, último en entrar, primero en salir).La recuperación de los datos es hecha en el orden inverso de su inserción.

Para la implementación he elegido una lista enlazada simple, presentada sobre la vertical. Ya que la inserción es siempre hecha al inicio de la lista, el 1er elemento de la lista será el ultimo elemento ingresado, por lo tanto estará en la cabeza de la pila.

Lo interesante es que el ultimo elemento ingresado, será el 1er elemento recuperado. 

A continuacion un ejemplo:

/* apilar (añadir) un elemento en la pila */ int apilar (Pila * tas, char *dato){ Elemento *nuevo_elemento; if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento))) == NULL) return -1; if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char))) == NULL) return -1; strcpy (nuevo_elemento->dato, dato); nuevo_elemento->siguiente = tas->inicio; tas->inicio = nuevo_elemento; tas->tamaño++; }

  Árbol

Un arbol es una estructura de datos se llama asi por que imita la forma de un arbol. Un nodo es la unidad sobre la que se construye el arbol y puede tener cero mas nodos hijos conectados a el.
 

Un Ejemplo de un Arbol

 A continuacion veremos un ejemplo en codigo:

Tabla de dispercion

las tablas de dispersión  tienen como finalidad realizar la búsqueda o eliminación de un registro con una complejidad constante. La organización ideal de una tabla es aquella en la cual el campo clave de los elementos se corresponde directamente con el índice de la tabla. 

A contnuacion un ejemplo:

public struct SampHashKey { public int a { set; get; } public int b { set; get; } public int c { set; get; } public int d { set; get; } } public override int GetHashCode() { MessageBox.Show("llamando a GetHashCode"); return base.GetHashCode(); } public void Test() { Dictionary<SampHashKey, string> oD = new Dictionary<SampHashKey, string>(); oD.Add(sSHK1, "s"); }

Tipos de tabla

• Hash de division
• Hasta de multiplicacion

Big Data

Se refiere a la tendencia en el avance de la tecnologia que ha abierto nuevas puertas hacia un enfoque de entendimeinto y toma de deisiones, la cual se utiliza para describir enormes cantidades de datos que tomar demaciado tiempo y seria costoso cargarlos a una base de datos relacional para su analizsis. De tal modo que Big Data se aplica para aquella informacion que no puede ser procesada o analizada utilizando procesos o herramientas tradicionales. Sin embargo no refiere a ninguna cantidad en especifico, ya que sse utilia cuando se habla en terminos de petabytes (Petabyte = 10¹⁵ = 1,000,000,000,000,000) y exabytes (Exabyte = 10¹⁸ = 1,000,000,000,000,000,000) de datos. 

Componentes:

Hadoop es una plataforma de codigo abierto que se utuliza para analizar enormes cantidades de informacion, esta insipirada en el proyecto de Google File System y en el pardigma de MapReduce.Hadoop está compuesto de tres piezas: Hadoop Distributed File System (HDFS), Hadoop MapReduce y Hadoop Common.

Map Reduce

Es el nucleo de Hadoop, se refiere a dos procesos separados que Hadoop ejecuta, el primero es un proceso "map" el cual toma un conjunto de datos y lo convierte en otro conjunto, donde los elementos individuales son separados en tuplas (pares de llave o valor.

El proceso de reduce obtiene la salida de "map" como datos de entras y combina las tuplas en un conjunto mas pequeño. Una fase intermedia "shuffle" la cual obtiene las tuplas del proceso "map" determna que nodo procesara estos datos dirigiendo la salida a una tarea de "reduce" en especifico. 

El siguiente ejemplo es un flujo de datos de un proceso sencillo de MapRaduce