Página principal

Estructuras de Datos 2005 Trabajo Especial Nº 1


Descargar 174.62 Kb.
Fecha de conversión18.07.2016
Tamaño174.62 Kb.

Estructuras de Datos 2005

Trabajo Especial Nº 1



Índice


Enunciado del Trabajo 2

El Juego 4

El Autor 4

Descripción del Juego 4

Aplicaciones del juego 4

En Música 4

Punto Nº 1: Informe Teórico. 5

Estructura de Datos Estáticos y Dinámicos 5

Estáticos vs dinámicos 5

Modelo del Sistema Actual 5

Alternativas 6

Definición de Matrices de Adyacencia 6

Definición de Lista de Adyacencia 7

Definición de Matrices Ralas 8

En Conclusión 10

Punto 2 10

a) Cambio de Estado 10

En el sistema actual 10

c) Guardar y Recuperar de Memoria Secundaria 11

Punto 3: Representaciones 11

Modelo 1: 11

Bibliografía 12


Enunciado del Trabajo


Juego de la Vida
Este juego es una simulación sobre una grilla rectangular sin límites de tamaño; las celdas pueden estar ocupadas por un organismo (viva), o sin ocupar (muerta). Los cambios en las generaciones sucesivas se dan según las siguientes reglas:


  1. “Vecino” es una celda que tiene contacto con otra (ya sea vertical u horizontalmente, o en diagonal). En particular, cada celda tiene 8 celdas vecinas.

  2. Una celda viva con un vecino vivo o ninguno en el próximo instante muere de soledad.

  3. Una celda viva, pero con 4 o más vecinos vivos pasa a morir de sobrepoblación.

  4. Una celda viva con 2 o 3 vecinos vivos sigue viva.

  5. Una celda muerta con exactamente 3 vecinos vivos pasa estar viva. Todas las demás celdas muertas siguen muertas.

  6. Todos los nacimientos o muertes suceden en el mismo instante.

Ejemplificamos, marcando en color las celdas vivas:

























































Las ponderaciones de vecinos vivos serían:







1

2

2

1







1

1

1

1







1

2

2

1



Por las reglas anteriormente explicadas, esta “comunidad” en la próxima generación moriría (reglas 2 y 5). Llamamos comunidad al conjunto de celdas activas; por generación nos referimos a cada instancia del juego (cada momento).


Damos ahora otro ejemplo:

















1

2

3

2

1

1

1

2

1

1

1

2

3

2

1















Pasa a ser:






1

1

1







2

1

2







3

2

3







2

1

2







1

1

1




Este caso siempre pasa a alternarse de una de las dos maneras, sin terminar nunca de cambiar. Los comportamientos de las comunidades que se formen pueden ser sorprendentes, ya que un caso muy simple puede derivar en una comunidad muy grande que no muera nunca.
Mientras van pasando generaciones, puede aumentar el tamaño de las grillas y, como dijimos al principio, no hay límites en este sentido.
Consignas:

  1. Preparar un informe que dé un marco teórico a las estructuras dinámicas que se utilizan para el trabajo, comparándolas con estructuras estáticas y analizando métodos de representación. Se deben mostrar también las conclusiones que se hayan sacado de la parte práctica.

  2. Identificar las operaciones que se deben realizar para:

    1. Cambiar de estado (pasar de una generación a otra);

    2. Recuperar/mostrar el mapa completo;

    3. Guardar y recuperar el mapa de memoria secundaria.

  3. Proponer dos o más representaciones para el modelo.

  4. Generar los operadores descriptos en pseudo-código.

    1. Criticar la representación elegida, basándose en las dificultades que presentaron para diseñar los algoritmos.

  5. Escribir un algoritmo en pseudo-código tal que dado un mapa inicial, se calculen las siguientes generaciones (tener en cuenta que esto puede ser divergente).

  6. Implementar en algún lenguaje de programación, teniendo en cuenta un mecanismo de visualización del mapa (no hace falta implementar ese mecanismo).

El Juego

El Autor


John Horton Conway (nacido en Liverpool, Gran Bretaña el 26 de diciembre de 1937). Prolífico Matemático activo en la teoría de conjuntos (teoría de conjuntos finitos), teoría de nudos, teoría de números, teoría de juegos y teoría de códigos. Se formó en la Universidad de Cambridge.

Entre los matemáticos aficionados, quizás es más conocido por su teoría de juegos combinatoria, en particular por ser el creador del juego de la vida. También es uno de los inventores del juego del drago, así como del Phutball y ha realizado análisis detallados de muchos otros juegos y problemas, como el cubo Soma.



Descripción del Juego


El juego de la vida es en realidad un juego de cero jugadores, lo que quiere decir que su evolución está determinada por el estado inicial y no necesita ninguna entrada de datos posterior. El "tablero de juego" es una malla formada por cuadrados ("células") que se extiende por el infinito en todas las direcciones, dependiendo de la implementación. Cada célula tiene 8 células vecinas, que son las que están próximas a ella, incluso en las diagonales. Las células tienen dos estados: están "vivas" o "muertas". El estado de la malla evoluciona a lo largo de unidades de tiempo discretas (se podría decir que por turnos). El estado de todas las células se tiene en cuenta para calcular el estado de las mismas al turno siguiente. Todas las células se actualizan simultáneamente.

Las transiciones dependen del número de células vecinas vivas:



  • Una célula muerta con exactamente 3 células vecinas vivas "nace" (al turno siguiente estará viva).

  • Una célula viva con 2 o 3 células vecinas vivas sigue viva, en otro caso muere o permanece muerta (por "soledad" o "superpoblación")



Aplicaciones del juego

En Música


Dadatron propone un sistema de composición musical auto generativo elaborado a partir del algoritmo VIDA de Jonh Conway.

El objetivo es integrar el aporte del espectador-usuario en el universo de la composición musical aleatoria, de modo que la interacción de los elementos introducidos en la interfaz de la aplicación tenga una correlación sonora con las evoluciones de los individuos del ecosistema virtual, y obtener de ese modo un tema musical en constante evolución en el que se dan secuencias sonoras en permanente avance y retroceso, pues muchos de los elementos del sistema reaparecerán al cabo de un tiempo.[11]


Punto Nº 1: Informe Teórico.

Estructura de Datos Estáticos y Dinámicos


E. D. Estáticos: su tamaño y forma es constante durante la ejecución de un programa y por tanto se determinan en tiempo de compilación. El ejemplo típico son los arrays. Tiene el problema de que hay que dimensionar la estructura de antemano, lo que puede conllevar desperdicio o falta de memoria

E. D. Dinámicos: su tamaño y forma es variable (o puede serlo) a lo largo de un programa por lo que se crean y destruyen en tiempo de ejecución. Esto permite dimensionar la estructura de datos de una forma precisa: se va asignando memoria en tiempo de ejecución según se va necesitando.

Estáticos vs dinámicos


Una de las razones para utilizar estructuras dinámicas es la representación de colecciones de valores.

  1. La estructura de datos estática apta para representar colecciones de datos es el array. Sin embargo, se presentan 2 problemas por el hecho de tener que reservar el espacio a priori:

    1. Se desaprovecha memoria si el espacio reservado resulta excesivo.

    2. Se pueden producir errores en tiempo de ejecución si el espacio reservado resulta ser insuficiente o los recursos necesarios son insuficientes.

    3. Otro tipo de error se podría producir en tiempo de compilación, con lo cual el programa que se utilizaría detendría la operación, por los mismos motivos que en el punto anterior.

  2. Las estructuras de datos dinámicas, por su parte, permiten representar colecciones de datos de forma que:

    1. No se malgasta espacio a priori y

    2. El único límite en tiempo de ejecución es la cantidad de memoria disponible.

    3. Los punteros son el mecanismo que permite construir y manejar estructuras de datos dinámicas

Para trabajar con datos dinámicos necesitamos 2 cosas:

      • Llamadas a Sistema (System Call) predefinidos en el lenguaje que nos permitan gestionar la memoria de forma dinámica (asignación y liberación).

      • Algún tipo de dato con el que podamos acceder a esos datos dinámicos

Modelo del Sistema Actual


El sistema actual utiliza una especie de grilla o matriz cuya estructura del nodo esta definido por 3 elementos:

col

(short)


row

(short)


neighbour

(byte)


Que se puede encontrar en el archivo Cell.java.

Aunque se lo esta denominando un nodo no es en si un nodo de una lista sino es una celda de una matriz, en donde “neighbour” se almacena el estado actual, el estado actual es en realidad la cantidad de vecinos vivos tiene.

Los vecinos son relevados en el archivo GameOfLifeGrid.java dentro de este archivo esta las funciones que se encargan de esta tarea.

La función next() es la que se encarga de juntar a los vecinos que posee la celda, luego es invocada la función addNeighbour(int col, int row) que es la que se encarga de contar aquellos vecinos vivos y almacenarlo en la variable neighbour para que cuando se represente la nueva generación ya se tenga el nuevo estado de la celda.



Ejemplo:

Si se posee la siguiente disposición:














































































La Matriz sería la siguiente:

i\j

0

1

2

3

4

0

2

4

3

2

0

1

3

5

4

2

0

2

2

3

3

1

0

3

1

1

1

0

0

4

0

0

0

0

0

Alternativas


Una alternativa al modelo actual sería con la utilización de una matriz de Adyacencia, que en vez de guardar la cantidad de vecino vivos que posee la celda se guardaría únicamente con los valores cero y uno el próximo estado de la celda, con 0 si la celda muere y con 1 si la celda vive.

Definición de Matrices de Adyacencia


Esta es una Representación Estática

Para la representación por medio de una matriz de adyacencia, asumimos que los vértices están numerados 1, 2, ..., |P| de forma arbitraria. La representación mediante matriz de adyacencia de un grafo G, consiste de una matriz A de orden |P|2 donde el elemento aij de la fila i y columna j está definido como:



aij =



1 si (i, j) pertenece a A

0 en otro caso



Esta representación requiere una memoria de orden |P|2.

Ejemplo:

Si se posee la siguiente disposición:














































































La Matriz de Adyacencia sería la siguiente:

i\j

0

1

2

3

4

0

1

0

1

0

0

1

0

1

1

0

0

2

0

1

0

0

0

3

0

0

0

0

0

4

0

0

0

0

0

Otra alternativa que sería mas Dinámica que la anterior es con la utilización de una Lista de Adyacencia


Definición de Lista de Adyacencia


Esta es una Representación Dinámica

La representación mediante listas de adyacencia de un grafo G = (P, E) consiste de un arreglo Adj de |P| listas. Una lista por cada vértice en P. Para cada vértice u en P, la lista de adyacencia Adj[u] contiene "apuntadores" (direcciones de memoria) a todos los vértices v tal que existe un arco (u, v) en A. Esto quiere decir que Adj[u] agrupa todos los vértices adyacentes a u en G. Los vértices en cada lista de adyacencia están típicamente almacenados en orden arbitrario.

La suma de las longitudes de todas las listas de adyacencia es 2|E| (peor caso), ya que si (u,v) es un arco no dirigido, entonces u aparece en la lista de adyacencia de v y viceversa.

La cantidad de memoria necesaria para una representación por listas de adyacencia es O(|P| + |E|).



Ejemplo:

Si se posee la siguiente disposición:















































































La Lista de Adyacencia sería la siguiente:

0







0
















2

^




























1
















1







2

^




























2
















1

^





































3

^























































4

^























































En donde el arreglo poseería las posiciones de las filas (i) y los nodos poseerían la posición de las columnas (j).


Resumen

Nombre

Ventajas

Desventajas

Utilidad

Matriz de adyacencia

Accesos de O(1)

Ocupa un espacio de orden |V|2

Se usa, generalmente, para representar grafos densos.

Lista de adyacencia

Ocupa solo la memoria necesaria. Espacio proporcional a |V| + |A|

La búsqueda en una lista en particular es O(|V|), para el caso peor.

Esta representación suele usarse para grafos poco densos.

Entiéndase por “densos”, a gran cantidad de elementos (P)


Para hacerlo mas dinámico aun, se podría implementar los que se denomina Matrices Ralas

Definición de Matrices Ralas


Matrices dispersas (también se conocen como matrices ralas ó sparse matrix): son matrices grandes donde la mayor parte de los elementos son ceros. Se dan mucho en algunos problemas de ingeniería. [1]

Una posible Representación para este tipo de Matrices sería hacer una Lista de Listas, para lo cual se utilizaría el concepto de Listas de Adyacencia, solo en vez de usar un arreglo para identificar, en este caso, las filas se utilizaría otra lista.



Ejemplo:

Si se posee la siguiente disposición:














































































La Lista de Listas sería la siguiente:

0







0
















2

^
































































1
















1







2

^
































































2
















1

^










^



























Según el Libro de Pfaltz, podríamos implementar este tipo de modelo de 2 formas distintas, esta distinción se realiza en la estructura de los nodos

Forma 1:


*filas

numero

*columna

dato

En donde *filas y *columna son punteros, numero indica el numero de fila o el numero de la columna al cual pertenezca el nodo y el dato es la cantidad de vecinos vivos posee la celda.

En esta forma existen 2 listas que en el dato no posee ningún dato, ya que son los índices de las filas y/o columnas




Forma 2:

*filas

numero_f

numero_c

*columna

dato

En donde *filas y *columna son punteros, numero_f indica el numero de fila y el numero_c el numero de la columna al cual pertenezca el nodo y el dato es la cantidad de vecinos vivos posee la celda.

En esta forma existen 2 listas que en el dato no posee ningún dato, ya que son los índices de las filas y/o columnas





En Conclusión


La mejor opción para la realización del “Juego de la Vida” de Conway, sería esta última, la de Matrices Ralas, aunque presenta la dificultad de que al momento de hacer el recuento de vecinos se deberá recorrer todas las listas, teniendo en cuenta que puede no existir algunas de las listas que se necesiten para el conteo de vecinos.

Punto 2

a) Cambio de Estado


Para realizar el cambio de estado lo primero que se necesita es contar de cada celda viva, la cantidad de vecinos vivos que posee. Luego determinar su próximo estado según las reglas del juego enunciado en el “Enunciado del Trabajo”, pero generalmente si posee 2 ó 3 vecinos esta mantendrá su estado de viva cualquier otro número distinto a los mencionados la celda morirá. Una vez identificado el estado de las celdas actuales vivas, se deberá chequear la cantidad de vecinos de las celdas vecinas, por si alguna celda muerta cambiara su estado a viva.

Ejemplo:

Si se utilizara el método de Matrices Ralas con la representación presentada.


Q ← qi //cola en donde se colocan las filas vivas.

qj ← Q //extraigo el primer nodo identificando a la primera fila viva

MIENTRAS ( qj.sig ≠ ^ )

SI ( ContarVecinos (qj.col) ≠ 2 ) ó ( ContarVecinos (qj.col) ≠ 3)

EliminarNodo (qj)

qj ← qj+1 // próximo nodo vivo



En el sistema actual


En el sistema actual el cambio de generación se realiza en el archivo GameOfLife.java en la función nextGeneration(), la cual invoca a la función next() que se encuentra en el archivo GameOfLifeGrid.java , la cual se explico básicamente al principio del trabajo, en síntesis esta función lo que realiza en contar a los vecinos y guardar esta cantidad en la celda, luego llama a otra función la cual redibuja nuevamente la grilla apareciendo la nueva generación.

c) Guardar y Recuperar de Memoria Secundaria


Para guardar el mapa actual lo único que habría que hacer es ir guardando lista a lista, y al finalizar una lista se podría colocar un delimitador de fin o guardar la próxima lista en un renglón distinto.
Q ← qi //cola en donde se colocan las filas vivas.

qj ← Q //extraigo el primer nodo identificando a la primera fila viva

MIENTRAS ( qj.sig ≠ ^ )

guardo qj.col

SI ( qj.sig = ^ )

guardo | //como delimitador entre listas

qj ← qj+1 // próximo nodo vivo



Punto 3: Representaciones

Modelo 1:


Una Representación propuesta es la realizada en la de Matrices Ralas utilizando Lista de Listas.

0







0
















2

^
































































1
















1







2

^
































































2
















1

^










^





























Bibliografía





  1. http://listas.fi.uba.ar/pipermail/programacion/2003-May/000216.html

  2. http://ainsuca.javeriana.edu.co/e-datos/semana06/ejemplos.html

  3. http://mailweb.pue.udlap.mx/~ccastane/Syllabus_Estructura_Datos/Sy_EstructuraDatos_Java.html

  4. http://www.matcom.uh.cu/eda/GrafosND.htm#17_2_1

  5. http://www.virtual.unal.edu.co/cursos/ingenieria/2001412/capitulos/cap7/72.html

  6. http://www.itlp.edu.mx/publica/tutoriales/estru1/74.htm

  7. Computer Data Structures; J. L. Pfaltz

    1. Matrices Ralas o Dispersas: 229 a 236

    2. Matrices de Adyacencia: 18, 168-170, 195

    3. Almacenamiento Dinámico: Capitulo 10, 359.

  8. http://www.redcientifica.com/gaia/zip/dw_c.htm

  9. http://axxon.com.ar/zap/278/c-Zapping0278.htm

  10. http://es.wikipedia.org/wiki/Juego_de_la_vida

  11. http://www.fundacion.telefonica.com/at/vida/paginas/v5/dadatron.html

  12. http://www.programacion.net/java/tutorial/jap_data_alg/4/






La base de datos está protegida por derechos de autor ©espanito.com 2016
enviar mensaje