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.