Blog de Mau

jueves, 14 de julio de 2011

Diagrama de Voronoi

Estos diagramas permiten encontrar el vecino más cercano a un punto para cada punto principal en el diagrama, o sea los puntos sobre los cuales se creó el diagrama, el cual también forma puntos propios. El nombre viene del matemático ruso que lo definió, Georgi Voronoi.

El siguiente gráfico muestra un diagrama de Voronoi de una nube de puntos:

Como concepto teórico: Sea P = {p₁,p₂,...,p_n} un conjunto de n puntos distintos en el plano. Definimos el diagrama de Voronoi de P como la subdivisión del plano en n regiones, cada una correspondiente a un punto deP, cumpliendo, que un punto q pertenece a la región correspondiente al punto p_isi y solamente sidist(q,p_i) < dist(q,p_j) para cada punto p_j P, con j distinto de i. Denotamos el diagrama de Voronoi de P como Vor(P). La región correspondiente al punto p_i es llamada V(p_i).

Podemos notar que no todos los puntos tiene un sitio más cercano: Todos
los puntos que tienen más de un sitio igual de cerca forman el
Diagrama de Voronoi V(P).

Inicialmente el diagrama de Voronoi fue creado para el análisis de datos meteorológicos (estaciones pluviométricas) aunque en la actualidad también se aplica en estudios en los que hay que determinar áreas de influencia (centros hospitalarios, estaciones de bomberos, bocas de metro, centros comerciales, control del tráfico aéreo, telefonía móvil, análisis de poblaciones de especies vegetales, etc.).

Aquí un video tutorial de cómo funciona el diagrama, en inglés:

Referencias:

Complejidad Computacional

Vamos a analizar lo que es la complejidad computacional. Una de las cosas más importantes a tomar en cuenta al momento de seleccionar un algoritmo es el tiempo que se va a tardar en arrojar una salida. En ves de calcular el tiempo exacto que se puede tardar nuestro algoritmo, se calcula la cantidad de operaciones en función del tamaño de la entrada (n). Para estimar el tiempo de ejecución, esta función de crecimiento se multiplica por una constante c que representa una estimación del tiempo que una computadora se tarda en realizar una operación.

Los problemas de decisión son los problemas en donde las dos respuestas posibles sin “si” y “no”. También se puede definir como el problema de decidir si una cierta frase pertenece a un conjunto dado de frases, o lenguaje formal. El conjunto contiene exactamente las frases para las cuales la respuesta a la pregunta es positiva. Si existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entonces se dice que el problema es decidible, de otra forma se dice que es un problema indecidible.

Los problemas de decisión se pueden clasificar en clases de complejidad, las cuales son:

La clase de complejidad P, la cual está formada por todos aquellos problemas de decisión para los cuales se tiene un algoritmo de solución que se ejecuta en tiempo polinomial en una máquina determinista.
La clase de problemas NP la cual está formada por todos aquellos problemas de decisión para los cuales existe un algoritmo de solución que se ejecuta en tiempo polinomial en una máquina no determinista. Dicho de otro modo, no se ha encontrado un algoritmo determinista que lo resuelva en tiempo polinomial.

La relación entre la clase P y la clase NP es estrecha: $P\subseteq NP$ . Cualquier problema de decisión resuelto por un algoritmo determinístico en tiempo polinomial también es resuelto por un algoritmo no determinístico en tiempo polinomial.

*Este diagrama muestra la teoría de que todos los problemas P y NP-Completo son problemas NP, aunque no ha sido probada es la mas aceptada como probable.

Algunas clases

TIME: o DTIME, es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(f(n)), y espacio ilimitado.
E: es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo 2^O(n), y es por lo tanto igual a la clase de complejidad DTIME(2^O(n)).
NC: es el conjunto de los problemas de decisión que pueden ser resueltos mediante computación paralela con un número polinómico de procesadores en tiempo polilogarítmico.
NTIME: la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en tiempo O(f(n)) y espacio ilimitado.
PP: es una clase de problema de decisión, resoluble por una máquina de Turing probabilística, diferente de la máquina de Turing general o determinística en que las transiciones entre estados tienen la misma probabilidad de ocurrencia.
DSPACE: es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en espacio O(f(n)) y tiempo ilimitado. Es la contrapartida determinista de la clase NSPACE.
EXPSPACE:es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2^p(n)), donde p(n) es una función polinomial sobre n.
L: es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing determinista tal que la solución si existe es única.
NSPACE: es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en espacio O(f(n)) y tiempo ilimitado. NSPACE es la contrapartida no-determinista de DSPACE.

Esta es la página de la organización que da 1 millón de dólares a quien resuelva el problema de P vs NP: http://www.claymath.org/millennium/P_vs_NP/

Referencias:

miércoles, 13 de julio de 2011

Grafos

Aquí un poco de información acerca de los grafos!

Empezamos con la definición… Un grafo se define como un conjunto de puntos, o vértices, que están conectados por un conjunto de líneas, o aristas. Los vértices son objetos que contienen información y las aristas son las conexiones entre esos vértices. Son muy utilizados en computación por que permiten resolver problemas muy complejos.

Hay dos tipos de grafos, los dirigidos y no dirigidos:

No dirigidos:son aquellos en los cuales los lados no están orientados, o sea, no son flechas. Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).

Dirigidos:son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.

Grafos bipartitos:un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V₁y V₂ y las aristas siempre unen vértices de un conjunto con vértices de otro:

$V_1 \cup V_2 = V$
$V_1 \cap V_2 = \empty$
$\forall x_1,x_2 \in V_1, \forall y_1,y_2 \in V_2$

Ejemplo de grafos Bipartitos:

Un grafo bipartido completo si V=V1yV2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,s al grafo bipartido completo donde V1 tiene r vértices yV2 tiene s vértices.

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

Gafos bipartitos completos:

****************************************************************************************************

Árboles

Los árboles son estructuras de datos que se pueden definir de forma recursiva como una estructura vacía o un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol, llamados subárboles.

En cuanto a grafos, un árbol es un grafo acíclico, conexo y no dirigido, o sea un grafo no dirigido en el que existe un camino entre cualquier par de nodos.

En los árboles: la raíz es aquel elemento que no tiene antecesor; una rama es una arista entre dos nodos; un nodo x es antecesor de un nodo y si por alguna de las ramas de x se puede llegar a y; un nodo x es sucesor de un nodo y si por alguna de las ramas de y se puede llegar a x; el grado de un nodo es el número de descendientes directos que tiene; una hoja es un nodo que no tiene descendientes; el nivel es el número de ramas que hay que recorrer para llegar a la raíz de un nodo; la altura es el nivel más alto del árbol; por último, la anchura es el mayor valor del número de nodos que hay en un nivel.

Así se ve un árbol binario:

A es la raíz; G, H, I, K, son hojas.

Un árbol binario de búsqueda auto-balanceable es un árbol de búsqueda binaria que que intenta mantener su altura, tan pequeña como sea posible en todo momento de forma automática. Esto se realiza por lo general realizando transformaciones en el árbol, como la rotación de árboles.

Aquí una lista de tiempos asintóticos en términos de nodos en algún árbol n:

Para búsqueda, O(log n)
Para inserción, O(log n)
Para eliminación, O(log n)
Para iteración en orden, O(n)

Una liga para un código en C de árbol binario: http://www.elrincondelc.com/nuevorincon/index.php?pag=codigos&id=4

Hay dos estructuras de datos populares que implementan este tipo de datos:

Árbol AVL: es un árbol binario de búsqueda que cumple con la condición de que la diferencia en las alturas de los subárboles de cada uno de sus nodos es máximo 1. El nombre viene de sus creadores, Adelson-Velskii y Landis. La propiedad de equilibrio que debe cumplir un árbol para ser AVL asegura que la profundidad del árbol sea O(log(n)), por lo que las operaciones sobre estas estructuras no deberán recorrer mucho para hallar el elemento deseado. El tiempo de ejecución de las operaciones sobre estos árboles es, a lo sumo O(log(n)) en el peor caso, donde n es la cantidad de elementos del árbol.

Este es un árbol binario no equilibrado, o sea que no es AVL

Este es un árbol binario equilibrado, o sea que si es AVL.

Un ejemplo de operación que se pueden hacer con estos árboles son las rotaciones, en las cuales el reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden ser simples o dobles, y a la derecha o a la izquierda.

Aquí muestro un ejemplo de rotación simple a la derecha:

De un árbol de raíz (y) y de hijos izquierdo (x) y derecho (c), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de x (a) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (y), el hijo derecho de x (b) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (c).

Así se vería gráficamente:

Aquí unos ejemplos de árboles AVL en C: http://c.conclase.net/edd/?cap=008e

Árbol rojo-negro: es un tipo de árbol que está balanceado de tal manera que el tiempo de realizar operaciones sea O(log n) en el peor de los casos. En estos el nodo contiene un campo extra el cual llamamos color, y el árbol se recorre ya sea por color rojo o negro. Cada nodo puede tener uno de estos colores. Cada apuntador de hoja es de color negro, y cada camino desde cualquier nodo hasta una hoja contiene el mismo numero de nodos negros.

Un ejemplo:

El método de rotación es básicamente el mismo que se usa en los árboles AVL.

Aquí una página con diferentes operaciones en código C que se pueden hacer en con el árbol rojo-negro. Está en inglés.

Referencias:

lunes, 11 de julio de 2011

Tablas de Dispersión

Primero empecemos por ver qué son las funciones de dispersión. Las funciones de dispersión consisten en la elección de una clave para el buen funcionamiento de la estructura, es la relación entre la llave y la posición en la tabla. Estas tienen las siguientes características:

• Ser una función sencilla y por tanto rápida.
• Distribuir uniformemente los elementos en el espacio de almacenamiento
• Evitar en lo posible la aparición de sinónimos
• Para dos claves muy similares, generar posiciones distantes.

Ahora, las tablas de dispersión se pueden definir como estructuras de datos que se usan en aplicaciones que manejan una secuencia de elementos, de tal forma que cada elemento tiene asociado un valor clave, que es un numero entero positivo perteneciente a un rango de valores, relativamente pequeños. En estas organizaciones, cada uno de los elementos ha de tener una clave que identifica de manera univoca el elemento.

Son estructuras de datos que tienen como finalidad realizar las operaciones fundamentales de búsqueda y eliminación de un registro.
La organización ideal de una tabla es de tal forma que el campo clave de los elementos se corresponda directamente con el índice de la tabla.

En esta imagen se puede ver lo que se le llama una tabla de dispersión ideal, que significa que cada llave está en una celda distinta.

****************************************************************************************************

Tablas Hash

Las tablas hash se usan para conseguir una búsqueda e inserción muy rápidas. Para eso usamos un array, con lo que volvemos a la estructura básica
de almacenamiento, aunque hay una diferencia importante que es lo que
hace que sea mejor que el array en cuanto a rapidez: a cada dato se le asigna,
mediante una fórmula matemática llamada función hash, una posición única
en la tabla, con lo que la búsqueda, la inserción y el borrado son inmediatos: O(1).

Los inconvenientes de una tabla hash son:

Al tratarse de un array, el tamaño de la tabla está limitado y debe fijarse
desde el principio.
Como las posiciones ocupadas no tienen por qué ser consecutivas, no se
puede recorrer el contenido de una tabla hash.
Como la posición de una palabra se calcula de forma matemática, los datos no pueden almacenarse ordenados.
Si permitimos datos duplicados se produce lo que se denomina “colisión”,
que consiste en que a dos palabras se les asigna la misma posición en el
array.

Aquí hice un ejemplo para explicar una tabla hash, y también una función hash.

En ésta tabla, la función hash genera un índice basado en el dígito colocado en el extremo derecho del valor ASCII de la segunda letra del nombre de la persona.

Por ejemplo, en el nombre “Jessica”, la segunda letra es una “e”. El valos ASCII de “e” es 101. El dígito colocado en el extremo derecho de 101 es 1, por lo tanto el registro para “Jessica” es almacenado en el índice 1 de la tabla hash.

La tabla hash en la figura anterior muestra cada nombre en su posición asignada.

Las implantaciones de tablas hash con complicadas por que deben manejar colisiones potenciales. Básicamente, las colisiones disminuyen el desempeño de las operaciones de la tabla hash. La mejor manera de reducir el número de colisiones e incrementar la eficiencia de la tabla hash, es usar una buena función hash, la cual distribuye equitativamente la asignación de claves a través de las posiciones de la tabla hash.

Referencias:

Listas Doblemente Enlazadas

Ahora escribiré un poco sobre las listas doblemente enlazadas, las cuales son similares a las simplemente enlazadas, con la diferencia en que el enlace entre los elementos se hace gracias a dos punteros, uno que apunta al anterior y otro que apunta al elemento siguiente.

El puntero anterior del primer elemento debe apuntar hacia NULL (el inicio de la lista).
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos: Comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento. Comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.

A continuación algunas acciones que se pueden llevar a cabo con las listas, junto con un ejemplo en C.

I. Inserción en una lista vacía

Asignación de memoria para el nuevo elemento
Rellenar el campo de datos del nuevo elemento
El puntero anterior del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía utilizamos la dirección del puntero inicio que vale NULL)
El puntero siguiente del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía se utiliza la dirección del puntero fin que vale NULL)
Los punteros inicio y fin apuntaran hacia el nuevo elemento
El tamaño es actualizado

Ejemplo gráfico:

Código en C:

int insercion_en_lista_vacia (dl_Lista * lista, char *dato){
  dl_Elemento *nuevo_elemento;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  nuevo_elemento->anterior = lista->inicio;
  nuevo_elemento->siguiente = lista->fin;
  lista->inicio = nuevo_elemento;
  lista->fin = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

II. Inserción al inicio de la lista:

Asignación de memoria al nuevo elemento
Rellenar el campo de datos del nuevo elemento
El puntero anterior del nuevo elemento apunta hacia NULL
El puntero siguiente del nuevo elemento apunta hacia el 1er elemento
El puntero anterior del 1er elemento apunta hacia el nuevo elemento
El puntero inicio apunta hacia el nuevo elemento
El puntero fin no cambia
El tamaño es incrementado

Ejemplo gráfico:

Código en C:

int ins_inicio_lista(dl_Lista * lista, char *dato){
  dl_Elemento *nuevo_elemento;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  nuevo_elemento->anterior = NULL;
  nuevo_elemento->siguiente = lista->inicio;
  lista->inicio->anterior = nuevo_elemento;
  lista->inicio = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

III. Inserción al final de la lista

Asignación de memoria al nuevo elemento
Rellenar el campo de datos del nuevo elemento
El puntero siguiente del nuevo elemento apunta hacia NULL
El puntero anterior del nuevo elemento apunta hacia el ultimo elemento (es el puntero fin que contiene por ahora su dirección)
El puntero siguiente del ultimo elemento apuntará hacia el nuevo elemento
El puntero fin apunta hacia el nuevo elemento
El puntero inicio no cambia
El tamaño es incrementado

Ejemplo gráfico:

Código en C:
int ins_fin_lista(dl_Lista * lista, char *dato){
  dl_Elemento *nuevo_elemento;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  nuevo_elemento->siguiente = NULL;
  nuevo_elemento->anterior = lista->fin;
  lista->fin->siguiente = nuevo_elemento;
  lista->fin = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

IV. Inserción antes de un elemento de la lista.

Asignación de memoria al nuevo elemento
Rellenar el campo de datos del nuevo elemento
Elegir una posición en la lista (la inserción se hará después de la posición elegida)
El puntero siguiente del nuevo elemento apunta hacia el elemento actual.
El puntero anterior del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero anterior del elemento actual.
El puntero siguiente del elemento que precede al elemento actual apuntará hacia el nuevo elemento
El puntero anterior del elemento actual apunta hacia el nuevo elemento
El puntero fin no cambia
El puntero inicio cambia si la posición elegida es la posición 1
El tamaño se incrementa en una unidad

Ejemplo gráfico:

La función
int ins_antes (dl_Lista * lista, char *dato, int pos){
  int i;
  dl_Elemento *nuevo_elemento, *actual;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  actual = lista->inicio;
  for (i = 1; i < pos; ++i)
    actual = actual->siguiente;
  nuevo_elemento->siguiente = actual;
  nuevo_elemento-> anterior = actual->anterior;
  if(actual->anterior == NULL)
    lista->inicio = nuevo_elemento;
  else
    actual->anterior->siguiente = nuevo_elemento;
  actual->anterior = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

V. Inserción después de un elemento

Asignación de memoria al nuevo elemento
Rellenar el campo de datos del nuevo elemento
Elegir una posición en la lista (la inserción se hará después de la posición elegida)
El puntero siguiente del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero siguiente del elemento actual.
El puntero anterior del nuevo elemento apunta hacia el elemento actual.
El puntero anterior del elemento que va después del elemento actual apuntará hacia el nuevo elemento.
El puntero siguiente del elemento actual apunta hacia el nuevo elemento
El puntero inicio no cambia
El puntero fin cambia si la posición elegida es la posición del ultimo elemento (el tamaño de la lista)
El tamaño se incrementa en una unidad

Ejemplo gráfico:

Código en C:

int ins_después (dl_Lista * lista, char *dato, int pos){
  int i;
  dl_Elemento *nuevo_elemento, *actual;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  actual = lista->inicio;
  for (i = 1; i < pos; ++i)
    actual = actual->siguiente;
  nuevo_elemento->siguiente = actual->siguiente;
  nuevo_elemento->anterior = actual;
  if(actual->siguiente == NULL)
    lista->fin = nuevo_elemento;
  else
    actual->siguiente->anterior = nuevo_elemento;
  actual->siguiente = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

VI. Eliminación en la lista:

Para esta función podemos tener diferentes situaciones:

Eliminación en la posición 1 en una lista con un solo elemento
Eliminación en la posición 1 en una lista con varios elementos
Eliminación en la ultima posición (el ultimo elemento)
Eliminación en otra parte de la lista en cierta posición

La posición elegida es 1 (el caso de eliminación del 1er elemento de la lista)

El puntero sup_elemento contendrá la dirección del 1er elemento
El puntero inicio contendrá la dirección contenida por el puntero siguiente del 1er elemento que deseamos eliminar (si este puntero vale NULL entonces actualizamos el puntero fin ya que estamos en el caso de una lista con un solo elemento, si no hacemos apuntar el puntero anterior del 2do elemento hacia NULL)

la posición elegida es igual al numero de elementos de la lista

El puntero sup_elemento contendrá la dirección del ultimo elemento
Hacemos apuntar al puntero siguiente del penúltimo elemento (es el elemento hacia el que apunta el puntero <anterior> del ultimo elemento), hacia NULL
Actualizamos el puntero fin

la posición elegida es aleatoria en la lista

El puntero sup_elemento contendrá la dirección del elemento a eliminar
El puntero siguiente del elemento que antecede al elemento a eliminar apunta hacia la dirección contenida en el puntero siguiente del elemento a eliminar
El puntero anterior del elemento que va después del elemento a eliminar apunta hacia la dirección contenida en el puntero anterior del elemento a eliminar.
El tamaño de la lista será disminuida en 1 elemento

Código en C:

int supp(dl_Lista *lista, int pos){
  int i;
  dl_Elemento *sup_elemento,*actual;

  if(lista->tamaño == 0)
    return -1;

  if(pos == 1){ /* eliminación del 1er elemento */
    sup_elemento = lista->inicio;
    lista->inicio = lista->inicio->siguiente;
    if(lista->inicio == NULL)
      lista->fin = NULL;
    else
      lista->inicio->anterior == NULL;
  }else if(pos == lista->tamaño){ /* eliminación del último elemento */
    sup_elemento = lista->fin;
    lista->fin->anterior->siguiente = NULL;
    lista->fin = lista->fin->anterior;
  }else { /* eliminación en otra parte */
    actual = lista->inicio;
      for(i=1;i<pos;++i)
        actual = actual->siguiente;
    sup_elemento = actual;
    actual->anterior->siguiente = actual->siguiente;
    actual->siguiente->anterior = actual->anterior;
  }
  free(sup_elemento->dato);
  free(sup_elemento);
  lista->tamaño--;
  return 0;
}

VII. Visualización de la lista:

Para mostrar la lista entera podemos posicionarnos al inicio o al final de la lista.
Luego utilizando el puntero siguiente o anterior de cada elemento, la lista es recorrida del 1er al ultimo elemento o del ultimo al 1er elemento.
La condición para detener es dada por el puntero siguiente del ultimo elemento que vale NULL en el caso de la lectura del inicio hacia el fin de la lista, o por el puntero anterior del 1er elemento que vale NULL, en el caso de una lectura del final hacia el inicio de la lista.

Código en C:

void affiche(dl_Lista *lista){ /* visualización hacia adelante */
  dl_Elemento *actual;
  actual = lista->inicio; /* punto de inicio el 1er elemento */
  printf("[ ");
  while(actual != NULL){
    printf("%s ",actual->dato);
    actual = actual->siguiente;
  }
  printf("]\n");
}

void mustra_inv(dl_Lista *lista){ /* visualización hacia atrás */
  dl_Elemento *actual;
  actual = lista->fin; /* punto de inicio el ultimo elemento */
  printf("[ ");
  while(actual != NULL){
    printf("%s : ",actual->dato);
    actual = actual->anterior;
  }
  printf("]\n");
}

Como en la entrada anterior, dejo un archivo con todo el código en C del ejemplo de las listas doblemente enlazadas.

http://www.mediafire.com/?b26u6uf887xcdjn

Referencias:

http://es.kioskea.net/faq/2872-listas-doblemente-enlazadas

http://c.conclase.net/edd/?cap=005

domingo, 10 de julio de 2011

Listas Simplemente Enlazadas

Les escribiré un poco acerca de las listas enlazadas.

La lista enlazada es un tipo de estructura de datos que permite almacenar datos de forma organizada de igual manera que los vectores, con la diferencia de que ahora la estructura es dinámica, queriendo decir que no tenemos que saber los elementos que pueda contener. En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.

Este es un ejemplo gráfico de lo que es una lista simplemente enlazada:

Una lista simplemente enlazada tiene las siguientes características:

Los elementos son contiguos en cuanto al enlazado.
Los elementos están dispersos en la memoria.
El enlace entre los elementos se hace por medio de un puntero.
En la memoria la representación es aleatoria en función al espacio asignado.
El puntero “siguiente” del último elemento debe apuntar hacia NULL (el fin de la lista)
Para acceder a un elemento, la lista es recorrida comenzando por el inicio, el puntero “siguiente” permite el desplazamiento hacia el próximo elemento.
El desplazamiento se hace en una sola dirección, del primer al último elemento.

A continuación algunas acciones que se pueden llevar a cabo con las listas, junto con un ejemplo en C.

I. Inserción en una lista vacía:

Se asigna memoria para el nuevo elemento
Se rellena el campo de datos del nuevo elemento
El puntero siguiente del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía se utiliza la dirección del puntero inicio que vale NULL)
Los punteros inicio y fin apuntaran hacia el nuevo elemento
El tamaño es actualizado

Aquí un ejemplo gráfico:

Código en C:
int ins_en_lista_vacia (Lista * lista, char *dato){
  Element *nuevo_elemento;
  if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nuevo _elemento->dato = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);

  nuevo_elemento->siguiente = NULL;
  lista->inicio = nuevo_elemento;
  lista->fin = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

II. Inserción al inicio:

Se asigna memoria al nuevo elemento
Rellenar el campo de datos del nuevo elemento
El puntero siguiente del nuevo elemento apunta hacia el primer elemento
El puntero inicio apunta hacia el nuevo elemento
El puntero fin no cambia
El tamaño es incrementado

Ejemplo gráfico:

Código en C:
int ins_inicio_lista (Lista * lista, char *dato){
  Element *nuevo_elemento;
  if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);

  nuevo_elemento->siguiente = lista->inicio
  lista->inicio = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

III. Inserción al final:

Asignación de memoria al nuevo elemento
Rellenar el campo de datos del nuevo elemento
El puntero siguiente del ultimo elemento apunta hacia el nuevo elemento
El puntero fin apunta hacia el nuevo elemento
El puntero inicio no cambia
El tamaño es incrementado

Ejemplo gráfico:

El código en C:
/*inserción al final de la lista */
int ins_fin_lista (Lista * lista, Element * actual, char *dato){
  Element *nuevo_elemento;
  if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);

  actual->siguiente = nuevo_elemento;
  nuevo_elemento->siguiente = NULL;

  lista->fin = nuevo_elemento;

  lista->tamaño++;
  return 0;
}

IV. Inserción en otra parte de la lista:

Asignación de memoria al nuevo elemento
Rellenar el campo de datos del nuevo elemento
Elegir una posición en la lista (la inserción se hará después de haber elegido la posición)
El puntero siguiente del nuevo elemento apunta hacia la dirección a la que apunta el puntero siguiente del elemento actual.
El puntero siguiente del elemento actual apunta al nuevo elemento
Los punteros inicio y fin no cambian
El tamaño se incrementa en una unidad

Ejemplo gráfico:

Código en C:
int ins_lista (Lista * lista, char *dato, int pos){
  if (lista->tamaño < 2)
    return -1;
  if (pos < 1 || pos >= lista->tamaño)
    return -1;

  Element *actual;
  Element *nuevo_elemento;
  int i;

  if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;

  actual = lista->inicio;
  for (i = 1; i < pos; ++i)
    actual = actual->siguiente;
  if (actual->siguiente == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);

  nuevo_elemento->siguiente = actual->siguiente;
  actual->siguiente = nuevo_elemento;
  lista->tamaño++;
  return 0;

V. Eliminación al inicio de la lista:

el puntero sup_elem contendrá la dirección del 1er elemento
el puntero inicio apuntara hacia el 2do elemento
el tamaño de la lista disminuirá un elemento

Ejemplo gráfico:
int sup_inicio (Lista * lista){
  if (lista->tamaño == 0)
    return -1;
  Element *sup_elemento;
  sup_element = lista->inicio;
  lista->inicio = lista->inicio->siguiente;
  if (lista->tamaño == 1)
    lista->fin = NULL;
  free (sup_elemento->dato);
  free (sup_elemento);
  lista->tamaño--;
  return 0;
}

VI. Eliminación en otra parte:

el puntero sup_elem contendrá la dirección hacia la que apunta el puntero siguiente del elemento actual
el puntero siguiente del elemento actual apuntara hacia el elemento al que apunta el puntero siguiente del elemento que sigue al elemento actual en la lista

*Si el elemento actual es el penúltimo elemento, el puntero fin debe ser actualizado

Ejemplo gráfico:

Código en C:
int sup_en_lista (Lista * lista, int pos){
  if (lista->tamaño <= 1 || pos < 1 || pos >= lista->tamaño)
    return -1;
  int i;
  Element *actual;
  Element *sup_elemento;
  actual = lista->inicio;

  for (i = 1; i < pos; ++i)
    actual = actual->siguiente;

  sup_elemento = actual->siguiente;
  actual->siguiente = actual->siguiente->siguiente;
  if(actual->siguiente == NULL)
          lista->fin = actual;
  free (sup_elemento->dato);
  free (sup_elemento);
  lista->tamaño--;
  return 0;
}

VI. Visualización de la lista

Para mostrar la lista entera hay que posicionarse al inicio de la lista (el puntero inicio lo permitirá). Luego utilizando el puntero siguiente de cada elemento la lista es recorrida del 1ero al último elemento.
La condición para detener es dada por el puntero siguiente del ultimo elemento que vale NULL.

Código en C:

void visualización (Lista * lista){
  Element *actual;
  actual = lista->inicio;
  while (actual != NULL){
      printf ("%p - %s\n", actual, actual->dato);
      actual = actual->siguiente;
  }
}

Aquí les dejo una liga que encontré en dónde se puede descargar en un archivo .txt un código bastante completo en C de listas simplemente enlazadas, en dónde se pueden hacer las acciones anteriores:http://www.mediafire.com/?s6vab8x0sk4c7h8

Referencias:

http://es.kioskea.net/faq/2842-la-lista-enlazada-simple

http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/ldoble.html

sábado, 9 de julio de 2011

Tutorial Wine

Ya anteriormente les escribí un tutorial para instalar Ubuntu dentro de Windows, ahora este es un tutorial para hacer algo parecido desde Ubuntu. Se llama Wine, y no instala Windows en sí, mas bien es un programa que permite correr aplicaciones de Windows. MmM

Definición según Wikipedia: es una re implementación de la interfaz de programación de aplicaciones de Win16 y Win32 para sistemas operativos basados en Unix. Permite la ejecución de programas diseñados para MS-DOS, y las versiones de Microsoft Windows 3.11, 95, 98, Me, NT, 2000, XP, Vista y 7.
Para una información completa en inglés, pueden visitar esta liga: http://wiki.winehq.org/
Aquí el paso a paso para instalar y sacar lo mejor de Wine dese Ubuntu 11.04 (Natty Narwhal):
Abrir Terminal, y añadir los repositorios de wine:
sudo add-apt-repository ppa:ubuntu-wine/ppa
Instalar la actualización o nueva versión de wine con:
sudo apt-get update
sudo aptitude install wine

Para saber que version de wine tienes instalada puedes ejecutar:
wine --version (doble guion)

Al estar recien instalado no tenemos el directorio .wine así que ejecutamos:
winecfg
Se abre el asistente de configuración de wine, donde podemos seleccionar si queremos ejecutar wine a pantalla completa o como una ventana mas del escritorio, o el tipo de sonido que utilizamos. Al pulsar “Aceptar” se aplican los cambios de configuración y se crea nuestro directorio “.wine”.
Instalaremos un script llamado winetricks que nos instala muchas cosas que necesita el Windows.
Para usarlo, nos descargamos el script (para tenerlo a mano lo instalaremos en .wine):
cd
cd .wine
wget wget http://www.kegel.com/wine/winetricks
le damos permisos de ejecución:
chmod +x ./winetricks
Se instala de manera automática.
Se recomienda instalar las siguientes librerías:
DirectX 9 (imprescindibles para jugar a juegos):

./winetricks d3dx9
Las fuentes de texto droid que mejoran mucho la legibilidad en pantalla:
./winetricks droid
PhysX, el motor de fisicas PhysX (si dispones de alguna tarjeta Nvidia):
./winetricks physx
Metapaquete que instala un fuentes de texto (como Arial, Sans Serif, etc utilizadas en Windows):
./winetricks allfonts
Metapaquete que instala un montón de codecs para reproducir video y audio.
./winetricks allcodecs
- Fijo la version de sistema que emulo como Windows XP (esto también se hace desde winecfg):
./winetricks winxp
./winetricks sound=alsa
Renombrar la carpeta drive_c como harddiskvolume0 (que a veces es necesario en muchos instaladores):
./winetricks volnum
Deshabilitar GLSL usado por Direct3D:
./winetricks glsl-disable
Instalar librerías de Visual C 2008 (necesarias por algunos juegos):
./winetricks vcrun2008
Las librerias dcom (si dispones de la licencia de Windows 98):
./winetricks dcom98
Se puede instalar el framework NET 2.0 (requiere licencia):
./winetricks dotnet20
Puede que falte alguna DLL si eso pasa se muestra un error en la consola diciendo que te falta una DLL (nombre) y tendrás que bajarla y copiarla en tu
.wine/drive_c/windows/System32

Para facilitar la instalación, puede que necesites quitar o añadir alguna:
./winetricks d3dx9 droid winxp sound=alsa volnum vcrun2008 dotnet20 ie6 corefonts
Se ha añadido ie6 (internet explorer 6) y corefonts (fuentes de Windows).

Para la configuración de tarjeta 3D, hay 2 métodos:
Método 1: Para añadir claves al registro (lo harías exactamente igual que en Windows) ejecutando:
wine regedit

se abre el editor de registro y ya se puede cambiar las claves o añadir nuevas.
Una vez nos ha abierto el programa regedit , buscamos en la siguiente dirección:
HKEY_CURRENT_USER\Software\Wine\Direct3D
Las claves a añadir el caso de tener una tarjeta Nvidia para la key DIRECT3D son:
“DirectDrawRenderer”=”opengl”
“Nonpower2Mode”=”repack”
“OffscreenRenderingMode”=”fbo”
“RenderTargetLockMode”=”auto”
“UseGLSL”=”readtex”
“VertexShaderMode”=”hardware”
“VideoDescription”=”NVIDIA GeForce 8500 GT”
“VideoDriver”=”nv4_disp.dll”
“VideoMemorySize”=”256″
Las entradas que aparecen en negritas son las que cambiarían, dependiendo del modelo de la tarjeta. Las demás quedarían igual en todas las tarjetas Nvidia.

Método 2: Tambien se puede hacer de manera más rápida, ir al directorio .wine y editar un fichero llamado “user.reg”, en ese fichero se van almacenando las claves del registro que va creando el usuario. Se edita el fichero, al final del mismo se pega el contenido:
sudo gedit /home/"usuario ubuntu"/.wine/user.reg
en usuario ubuntu hay que poner el nombre de nuestro usuario en el sistema

[Software\\Wine\\Direct3D] 1258821033

"DirectDrawRenderer"="opengl"

"Nonpower2Mode"="repack"

"OffscreenRenderingMode"="fbo"

"RenderTargetLockMode"="auto"

"UseGLSL"="readtex"

"VertexShaderMode"="hardware"

"VideoDescription"="NVIDIA GeForce 8500 GT"

"VideoDriver"="nv4_disp.dll"

"VideoMemorySize"="256"

Para cualquier otra duda ó cambiar más parámetros,lo mejor es consultar la página web de wine: Wine HQ
Referencias:
http://wiki.winehq.org/FAQ
http://wiki.winehq.org/Debunking_Wine_Myths
http://morfeox69.blogspot.com/2011/05/instalar-wine-correctamente-en-ubuntu.html
http://wiki.winehq.org/ListofCommands