PROBLEMA DE GRAFOS CON PREMIO

Interesante y muy oportuno para nosotros, que estamos estudiando grafos.

http://www.elpais.com/videos/sociedad/problema/ciudades/carreteras/elpepusoc/20110318elpepusoc_1/Ves/#

Os animo a que participéis y, si lo hacéis, por favor, añadid el comentario o el enlace al blog.

¡¡SUERTE!!

Ayuda para árboles

Antes de que os desaniméis con las dificultades que os supone la recursividad para el manejo de árboles, os dejo unos enlaces a distintas páginas web que contienen programas "animados" (applets) para que práctiquéis y afiancéis algunos conceptos básicos.

No obstante, recordad que con árboles la recursividad es relativamente sencilla: los casos base se suelen dar cuando el árbol está vacío (trivial) o en la raíz, y las llamadas recursivas se hacen casi siempre sobre los hijos, que son árboles más pequeños.

• http://nova.umuc.edu/~jarc/idsv/lesson1.html : recorridos

• http://people.ksp.sk/~kuko/bak/index.html : árboles binarios ordenados (o árboles de búsqueda), árboles AVL y árboles B, entre otros.

Espero que os sea útil. Ya me contaréis.

Buena noticia

Para tod@s aquell@s que no le véis sentido a la programación, os envío el enlace de una noticia publicada el día 18-1-2011 en el diario El Mundo, en la que informan de la concesión del Premio Fronteras que otorga la Fundación BBVA al padre de la programación.
http://www.elmundo.es/elmundo/2011/01/18/ciencia/1295354085.html
Espero que os dé ánimos de cara al próximo cuatrimestre ;-)

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)