Animaciones de TADs

Nuestro compañero David Vallejo nos ha proporcionado un enlace a una página donde podéis ver las principales estructuras de datos en versión "animada" http://www.cosc.canterbury.ac.nz/mukundan/dsal/appldsal.html, que siempre es más divertido que ver los dibujos en la pizarra...
Si encontráis alguno más que os guste, os agradeceríamos que nos lo hiciérais llegar y lo "colgamos".

BIENVENIDOS!!!

... que diría Miguel Ríos, nuestro más auténtico rockero "Made in Spain".
En fin, mitos aparte, no vuelvo a Granada, sino a este ciberespacio desde el que continuaremos desvelando, mientras el cuerpo aguante, algunas curiosidades que nos puedan ser útiles para hacer más llevadero todo lo relacionado con las Estructuras de Datos y la Programación en Java.
De momento, os dejo el enlace a un blog que he encontrado muy curioso e interesante, La tecla de Escape, donde seguro que podéis encontrar cosas muy interesantes, como el artículo que tienen sobre Recursividad.
Claro, que una vez que entendéis como funciona la recursividad, seguro que lo que os cuesta trabajo es aprender a pensar de forma recursiva. Mi consejo es el siguiente: Imaginaos que la recursividad es la chistera del mago de la que saca todo lo que necesita. Entonces, pensar un programa recursivo consta de dos fases:
Primera: dar la solución para aquellos casos triviales (Caso base), que suelen darse para los casos de estructuras vacías o unitarias, o número de elementos 0 ó 1, etc.
Segunda: Suponed que, por arte de magia, vuestro problema se resuelve automáticamente cuando hacéis la llamada recursiva para una situación más sencilla que la que tenéis que solucionar. Ya sólo queda pensar en cómo conseguir la solución para vuestro problema global teniendo en cuenta la que habéis obtenido mágicamente.
Veámoslo con un ejemplo:
Supongamos que queremos invertir una palabra P. (INVERTIR (P))
Primero pensamos en el caso más sencillo: que la palabra P sea vacía. Entonces no hay que hacer nada, se devuelve P.
Otro caso sencillo: que la palabra P sólo tenga 1 letra. Tampoco hay que hacer nada porque la inversión es la misma, así que se devuelve también P.
Ya no veo más casos sencillos, así que voy a pensar entonces en el caso general. Me doy cuenta de que no sé invertir una palabra de N letras, pero mágicamente, la recursividad me devuelve la solución cuando la palabra es más pequeña, supongamos que cuando tiene N-1 letras. Supongamos para abreviar que llamo PLP a la primera letra de P y N-1LP a las N-1 letras siguientes de P. Así que P la puedo escribir así: PLP N-1LP.
INVERTIR (N-1LP) me devuelve la inversión de la palabra P exceptuando la primera letra. Por ejemplo, si P =abcdef, PLP=a y N-1LP=bcdef. Por tanto, INVERTIR(N-1LP)=fedcb.
¿Qué falta para conseguir la palabra completa invertida? Añadir PLP(=a) al final del resultado obtenido. ¡Ya lo tenemos! Resulta que para invertir una palabra de N letras recursivamente primero se hace la llamada recursiva con las N-1 siguientes a la primera y después añadimos al final de este resultado la primera letra que nos habíamos dejado.
Es decir, el algoritmo sería así:

INVERTIR(Palabra P){

• Si P es vacía o sólo tiene una letra

Devolver P

• Si no

Guardamos la primera letra de P en PLP
Obtenemos la Palabra PI=INVERTIR(N-1LP)
Añadimos PLP al final de PI
Devolver PI
}

Espero que os resulte útil; al menos a mí lo de pensar en la magia me "ilusionó".

Una ayudita sobre árboles B y B+

Chicos y chicas,
el curso se acaba y, como casi todos los años, llegamos al final del temario con la lengua fuera. Este año, aún peor, porque no nos da tiempo a acabar el temario con soltura. Hoy es el último día que tenemos clase (snif!) y debemos ver árboles B y B+. Es obvio que nos quedaremos por las ramas, pero he encontrado esta página de la Universidad de Jaén sobre árboles B y B+ y estoy segura de que os ayudará a afianzar los conceptos más dudosos. De paso, echadle un vistado al resto de temas sobre ficheros, que están muy bien resumidos.
Ya me contaréis.

Ejercicios básicos con Tablas Hash

Después de una temporada de inactividad "bloguera" retomo hoy la edición en el blog gracias a las aportaciones que me habéis hecho a través del correo electrónico. Se trata de una solución al problema propuesto ayer en clase:

Se tienen N asignaturas, codificadas con tres números, y M alumnos, cada uno de ellos con el primer y segundo apellido, el nombre y uno o varios códigos de asignaturas. Construir las Estructuras de datos y los algoritmos necesarios para almacenar esta información y diseñar un método que nos muestre los datos personales de cada alumno y el nombre de todas las asignaturas en que esté matriculado.

Pues bien, uno de vosotros me ha mandado esta posible solución, de la que indicaré unas mejoras más abajo:

import java.io.IOException; import java.util.*; import listas.*;import utilidades.*;

public class ej2 {

  static class Alumno {
      private String nombre, apellido1, apellido2, dni;
      private Lista asignaturas;

      public Alumno(String n, String ap1, String ap2, String d){
          nombre=n;
          apellido1=ap1;
          apellido2=ap2;
          dni=d;
      }

      @Override public int hashCode(){
          return dni.hashCode();
      }

      @Override public boolean equals(Object o){
          return o instanceof Alumno && dni.equals(((Alumno) o).dni);
      }

      @Override public String toString(){
          return dni+" "+nombre+" "+apellido1+" "+apellido2;
      }
  }

  static Hashtable<> asignaturas = new Hashtable<> ();
  static Hashtable<>> alumnos = new Hashtable<>> ();

  public static void main(String aaa[]) throws IOException{
      String textomenu=" 1.- Añadir asignatura 2.- Añadir alumno 3.- Mostrar 0.- Salir";
      boolean fin=false;
      do{
          int elec=leer.entero(textomenu);
          try{
              switch (elec){
                  case 1:
                      añadirAsignatura(); break;
                  case 2:
                      añadirAlumno();  break;
                  case 3:
                      mostrar();   break;
                  case 0:
                      fin=true;  break;
              }//switch
          }//try
          catch(Exception e){ System.err.println(e.getMessage()); }
      }while(!(fin));
  }

  private static void añadirAsignatura() throws IOException {
      boolean seguir =true;
      while(seguir){
          Integer codigo=leer.entero("Dame el codigo de la asignatura");
          String nombre = leer.cadena("Dame el nombre");
          if(!asignaturas.containsKey(codigo)){
              asignaturas.put(codigo, nombre);
          }else System.out.println("Ya existe una asignatura con ese código");
          char c = leer.caracter("¿Alguna asignatua más? s/n");
          if(c=='n')
             seguir=false;
      }
  }
  @SuppressWarnings("element-type-mismatch")
  private static void añadirAlumno() throws IOException {
      boolean seguir =true;
      while(seguir){
          String nombre=leer.cadena("Dame el nombre del alumno");
          String ap1 = leer.cadena("Primer apellido");
          String ap2 = leer.cadena("Segundo apellido");
          String dni= leer.cadena("DNI");
          if(!alumnos.containsKey(dni)){
              Alumno nuevo = new Alumno(nombre, ap1, ap2,dni);
              Lista asig = new Lista();
              boolean seg=true;
              while(seg){
                  Integer cod = leer.entero("Dame el codigo de la asignatura");
                  if(!asignaturas.containsKey(cod))
                      System.out.println("Esa asignatura no pertenece a la tabla");
                  else
                      asig.insertarFinal(cod);
                  char c = leer.caracter("¿Alguna asignatura más? s/n");
                  if(c=='n')
                      seg=false;
              }
              alumnos.put(nuevo, asig);
          }
          char c = leer.caracter("¿Algún alumno más? s/n");
          if(c=='n')
             seguir=false;
      }
  }

  private static void mostrar() {
      Enumeration alums = alumnos.keys();
      Enumeration asig = alumnos.elements();
      while(alums.hasMoreElements()){
          Alumno a = (Alumno) alums.nextElement();
          Lista <> l = (Lista <>) asig.nextElement();
          System.out.println(a.toString());
          System.out.println("Asignaturas: ");
          while(!l.esVacia()){
              System.out.println(asignaturas.get(l.primero()));
              l=l.resto();
          }
      }
  }
}


Las posibles mejoras que os decía son:

1. Si en la clase Alumno defines el atributo asignaturas, en la tablaalumnos las asignaturas las estás almacenando dos veces: una con el alumno, como es la clave, y otra en el valor del alumno. Puesto que esto puede generar problemas de consistencia (aparte de redundancia) propongo dos cosas:

• Una: separar lo que es la clave del alumno (datos personales) de la información (lista de asignaturas)
• Otra: eliminar el atributo asignaturas del alumno. El inconveniente de esta opción es que si se necesita trabajar luego con el objeto alumno completo, asignaturas incluidas, en otra parte del programa, no se puedes, habría que definir otra clase.

Por tanto, la mejor opción es la primera, así que definiría la clase Alumno así:
class Alumno{
class DatosPersonales{
private String nombre, apellido1, apellido2, dni; los get, set, equals y hashCode}
private DatosPersonales datos;

private Lista asignaturas;

//ahora ya no es necesario el método hashcode porque iría en la clase DatosPersonales

Y la tabla alumnos se definiría así:

Hashtable <> > alumnos;


2. En el método mostrar:

Si en las Enumeration se indica el valor de la clase de la colección se evita hacer luego casting.
Por ejemplo, Emuneration <> alumns=alumnos.keys();
y luego Alumno a = alums.nextElement(); (sin casting)

Publicación de comentarios

Desde la creación de este blog os he animado a que contribuyáis a mejorarlo con vuestros comentarios. Sin embargo, no vale todo. ¿Qué quiero decir con esto? Pues que no voy a permitir que se publiquen comentarios que sean ofensivos ni tampoco los que estando relacionados con la asignatura contengan errores de bulto. Así que, los que hayáis enviado algún comentario y no lo veáis publicado ya sabéis por qué ha sido. Afortunadamente, he tenido que rechazar muy pocos y básicamente han sido por contener errores. El problema es que al no identificaros cuando hacéis los comentarios no os puedo escribir un correo personal para indicaros lo que está mal y así podáis corregirlo antes de publicarlo. Por tanto, si éste es vuestro caso, ponéos en contacto conmigo para revisar los posibles errores.

Haciendo historia

Redes de abastecimiento, redes de comunicación, redes de información, redes sociales, internet, la tela de araña, redes telefónicas... Hoy en día nos resulta impensable que alguien desconozca el concepto de red como una colección de equipos conectados entre sí por los que fluye cierta información. Pero ¿qué hay detrás de todo este lío tan formidable (que diría Iñaki Gabilondo?) Los que hemos tenido la suerte de estudiar algo de matemáticas, sabemos que los grafos precisamente consisten en un conjunto de elementos conectados entre sí mediante enlaces que permiten representar relaciones entre ellos. Así que, claro, enseguida identificamos el concepto de red con el de grafo. Vale, de acuerdo. ¿Y no tenéis curiosidad por sumergiros un poco más allá en la historia para saber cómo surge el concepto de grafo?.
Pues bien, hay que remontarse hasta principios del siglo XVIII, cuando no había ni televisión, ni iPods, ni cine ni tantas otras cosas que hoy en día nos hacen disfrutar. Entonces los entretenimientos eran distintos y, fijáos qué cosas, a la gente le daba por plantear problemas. Precisamente la resolución de uno de ellos, el de los puentes de Könisberg, se considera como el origen de la Teoría de Grafos. El problema en cuestión consistía en encontrar un recorrido para cruzar a pie toda la ciudad (hoy se llama Kaliningrado), pasando sólo una vez por cada uno de los siete puentes que unían las dos islas en las que el río Progolya dividía la ciudad, y regresando al mismo punto de inicio. Este problema lo resolvió un jovencísimo (tenía tan sólo 29 años) matemático suizo al que seguro que todos conocéis (de oídas, al menos), Leonhard Euler demostrando que no tenía solución. En fin, os animo a que investiguéis un poco sobre la vida de este gran matemático porque es impresionante la cantidad de aportaciones que hizo no solo a las matemáticas sino a la física, la astronomía, la lógica, la arquitectura e, incluso, a la humanidad: tuvo la friolera de 13 hijos, aunque sólo cinco llegaron a adultos. Sencillamente, ¡fascinante!

Árboles, que se acaban...

Ya estamos acabando el tema de árboles y espero que hayáis sido capaces de valorar la importancia de este tipo de estructuras jerárquicas como herramienta indispensable a la hora de resolver mediante el ordenador numerosos problemas reales. A lo largo del tema hemos visto distintos tipos de aplicaciones de los árboles:

- Para realizar búsquedas eficientes
- Para clasificar datos a partir de sus características
- Para procesar imágenes
- Para definir estrategias de resolución de problemas
- Para evaluar, derivar, etc. expresiones...
- Para representar los sistemas de archivos y directorios de algunos sistemas operativos
- Para representar un árbol genealógico

De hecho, aún no hemos acabado del todo con ellos pues cuando lleguemos los temas relacionados con la representación de la información (tablas y ficheros), veremos que vuelven a aparecer como herramienta para las bases de datos (Árboles B y B+).
Así que desde aquí os animo a que os perdáis por la red y/o por la biblioteca y busquéis para qué otras aplicaciones son adecuadas los árboles en cualquiera de las versiones que hemos estudiado en el tema. Y por supuesto, que nos lo contéis y así colaboréis en el enriquecimiento del blog aportando toda la información que consideréis de interés a través de vuestros comentarios.

De todas formas, teniendo en cuenta la importancia de la estructura, seguramente os preguntaréis como es que un lenguaje como Java no ha previsto una implementación para ella y tenemos que perder tiempo nosotros en hacerla. Qué raro ¿no?
Pues sí, porque efectivamente, Java proporciona la clase TreeSet para representar conjuntos de elementos ordenados con el objetivo de que las búsquedas se realicen en tiempo logarítmico, es decir, equivaldrían a los árboles balanceados que hemos visto.
Además, Java proporciona la clase JTree para la visualización de árboles en aplicaciones que incluyan Interfaces Gráficas de Usuario basadas en componentes Swing. Pero es muy curioso porque esta clase no constituye una forma de representación de la información en memoria sino simplemente una forma de visualizarla.

Interesante ¿verdad?

NUEVO FORO EN EL BLOG

Puesto que algunos de los comentarios que hacéis son preguntas sobre ciertas dudas que os surgen, he decidido crear un foro y asociarlo al blog con el fin de que estén más visibles tanto las preguntas como las respuestas. Si os fijáis, aparece en la columna de la derecha, justo encima de los comentarios, para que lo tengáis accesible. Es una versión inicial que iré mejorando con el tiempo, así que agradeceré vuestras sugerencias. Espero que le saquemos partido.

GRACIAS, FORGES

Sin comentarios...

"Y, seamos francos, en la programación o tienes buen día, o no. No hay término medio. O tienes un día lúcido y las ideas frescas o eres un paleto que ni las operaciones básicas te funcionan" (http://www.emezeta.com/categoria/programacion/pagina/4)

Comentarios parecidos a este son los que me habéis hecho en relación a los resultados del examen. De todas formas, aunque cada uno habrá sacado sus conclusiones, en líneas generales, los resultados han sido buenos. Así que ahora no hay que relajarse porque aún queda la otra mitad del curso: tanto para los que lo han aprobado como para los que no, porque incluso éstos están a tiempo de subirse al carro y superar la asignatura.

Por eso, voy a seguir aportando material adicional al que colgamos en moodle para nuestra asignatura y que considero que os puede resultar útil.
Realmente, mi primera intención al crear este blog es que fuérais vosotros los que lo elaborárais, mediante el intercambio de vuestras dificultades a la hora de programar y las soluciones que aportáis, pero veo que incluso desde el anonimato os cuesta trabajo participar. Bueno, no importa, al menos tengo la seguridad de que lo seguís y confío en que a alguien le vendrá bien todo esto que cuelgo.

Así que, aquí os dejo otro libro que me he encontrado por la red y que os puede resultar interesante, sobre todo por la cantidad de ejemplos y aplicaciones que proporciona.
http://www.cs.williams.edu/~bailey/JavaStructures/Welcome.html

Ya me contaréis.

NETBEANS Y UML

Si queréis hacer diagramas UML desde Netbeans 6.7, tenéis que instalaros el plugin correspondiente. Para ello, desde el IDE (entorno de desarrollo) seleccionáis Tools (o Herramientas) --> Plugins (o Complementos) y se os abre una ventana con una lista de plugins que podéis instalar. Buscad UML (está de los últimos), lo marcáis y pincháis en Install (Instalar). Cuando acabe la instalación, debéis reiniciar Netbeans para que se cargue.
Para hacer uso de esta utilidad, seleccionad la clase o el paquete del que queréis obtener el diagrama de clases, pulsad el botón derecho del ratón, seleccionad la opción "Reverse Engineer..." y ¡¡¡a jugar!!! De todas formas, en http://netbeans.org/kb/trails/uml.html podéis encontrar toda la información que necesitéis.

Si la versión que tenéis de Netbeans es la 6.8, el procedimiento es algo distinto. Cuando seleccionáis Tools-->Plugins veréis que en la lista de plugins disponibles no aparece. Bueno, no pasa nada: en la pestaña de Configuración, pinchad en el botón "Agregar" y añadís el siguiente enlace http://updates.netbeans.org/netbeans/updates/6.8/uc/m1/dev/catalog.xml. La lista de plugins disponibles se os actualiza y veréis que ahora sí aparece UML, así que lo seleccionáis, lo instaláis y reiniciáis.

Espero que os sea útil

MATERIAL INTERESANTE

Queridos chicos y queridas chicas, la semana que viene comienzan las clases del segundo cuatrimestre y habrá que ponerse las pilas. Así que supongo que la documentación que os enlazo os puede resultar de interés:

Estructuras de datos y métodos algorítmicos : ejercicios resueltos

Os agradecería (y supongo que vosotros tambień) que si encontráis algo por la red relacionado con la asignatura lo publicárais aquí para colaborar entre todos en la dinamización de los contenidos.

Nos vemos el lunes!

MEA CULPA

Aunque ayer personalmente pedí disculpas por el retraso al llegar al examen, quiero insistir en ello y lamento otra vez la confusión con las horas: realmente estaba convencida de que era a las 4,30 porque así lo tenía apuntado en mi agenda desde hace bastante tiempo. Ya śe que fueron 10 minutos de nervios para vosotros, pero espero que valoréis también que en contrapartida quitamos una parte de las cuestiones y dimos más tiempo para su resolución. En fin, una de cal y otra de arena...

SIGAMOS APRENDIENDO

Bueno, bueno, no pensaba que iba a tener tanto éxito de participación el blog. Pero he de deciros que me parece estupendo que hayáis encontrado un sitio mediante el que expresaros. En este sentido, agradezco vuestras ideas y, aunque no lo creáis, las que se refieren a la evaluación y a las prácticas, las tendremos en cuenta de cara a próximos años porque éste, el bacalao ya está cortao. Así que, me parece bien que sigáis opinando e incluso, como dice Juan J., que intentemos mejorar el blog añadiendo información que nos pueda venir bien a todos, pero sobre todo a vosotros, como enlaces a otros blogs, otras páginas web, etc. relacionadas con la asignatura.
En fin, hoy no puedo haceros perder mucho tiempo leyendo el blog, que esta tarde tenéis el examen, así que relajáos, no os pase lo que a la señora del video
http://www.youtube.com/watch?v=rX-17HkwgLg

;-)

VAMOS POR PARTES

Bueno, bueno, estoy muy contenta con la aceptación que está teniendo el blog, parece que desde el anonimato sí que os animáis a comunicaros conmigo. Habrá que sacarle partido al asunto. Así que vamos a ello, pero por partes, claro, que los comentarios son ciertamente heterogéneos.
Ante todo, agradezco a quien me avisa del error del enlace del blog en moodle: he vuelto a enviar un mensaje con la dirección exacta.
Por otro lado, os agradecería que al hacer los comentarios de las entradas os identificárais con algún nombre (real o inventado, no voy a hacer averiguaciones). Todos menos quien se denomina Raquel habéis sido "Anónimo" y así no hay quien pueda dirigirse a quien plantea una cuestión determinada.
Respecto al examen de mañana, aunque en la presentación de la asignatura en moodle está todo detallado, os recuerdo que constará de dos partes: en la primera tendréis que resolver 4 ó 5 cuestiones (ejercicios, problemas cortos, etc.), y en la segunda tendréis que resolver un problema del tipo de los que hemos resuelto en clase. Por cierto, que alguien dice que dejemos en moodle exámenes de otros años y creo que está un poco despistado o despistada (serán los nervios) porque en todos los temas del 2 al 6 aparece una relación denominada "Problemas de exámenes" (o algo parecido). ¡Ojo! En el examen entran todos los temas, del 0 al 6.
Otro anónimo alude a la suma de todas las notas del curso, de forma independiente, y con la posibilidad de hacer recuperaciones pero únicamente de la parte suspensa. Lo de las recuperaciones lo pide más gente pero, sinceramente, pensad un poco, si ya las pasamos canutas para abordar el temario, imagináos si encima tuviéramos que hacer recuperaciones de todo: necesitaríamos un par de meses más. De todas formas, los exámenes finales proporcionan la posibilidad de recuperar la parte teórica de la asignatura, que constituye el 50% de la nota, así que siempre tenéis esa oportunidad.
Y respecto a las dificultades de la asignatura, Raquel apunta al principal problema que tenéis: os falta soltura al programar, así que por ahí es por donde tenéis que atacarlo, independientemente de que resolvamos más o menos problemas en clase. De nada sirven si luego cada uno no se pelea con las teclas.
Finalmente, vuelvo a reiterar mi alegría por haber abierto este cauce de comunicación y esperemos que siga funcionando.
Ánimo, suerte y al toro ;-)

PERO QUÉ ES ESTO???

Año nuevo, vida nueva
Año de nieves, año de bienes
Renovarse o morir
...

Cualquiera de estos dichos nos sirve para encarar con optimismo el nuevo año, que no curso, pues ya estamos metidos de lleno en él, y de qué forma: el primer parcial nos acecha a la vuelta del fin de semana. AGGGG!!!
Pues con el objetivo de haceros todo esto un poco más llevadero y tener un sitio mediante el que comunicarnos (en clase los profes imponemos, ¿verdad?) y desahogarnos (educadamente, eso sí), se me ha ocurrido crear este blog mediante el que podamos compartir todo aquello relacionado con la asignatura de Estructuras de Datos, que tantos quebraderos de cabeza nos produce.
Así que os animo a que aprovechéis esta plataforma; a ver a dónde nos lleva. Emocionante, ¿no creéis?