Taller 7: Diccionarios y Espionaje

Objetivos

  • Analizar y comprender las operaciones críticas de un diccionario, así como su complejidad temporal.
  • Entender la importancia del uso de diccionarios en aplicaciones de búsqueda de información y autenticación de usuarios.
  • Comprender el funcionamiento de una tabla de hash como una implementación específica de un diccionario.

Descripción general

Transcurre el año 2015, la Guerra Fría finalizó hace 25 años. No obstante, las labores de inteligencia y espionaje no han cesado desde ese entonces, los Estados Unidos de América y la Federación Rusa, a través de sus organismos y agencias de inteligencia (CIA y SVR, respectivamente) han establecido una red extensa de inteligencia y espionaje en diversos países y regiones del mundo. Con el fin de recopilar y obtener información sensible acerca de los ciudadanos de diversos países, además de posibles agentes adscritos a la agencia contrincante, la CIA/SVR ha resuelto definir e implementar un sistema central de acceso únificado a la central de registros por parte de cada uno de los agentes activos actualmente en la organización.

Para este fin, se ha dispuesto que cada agente cuente con un un nombre de usuario y contraseña asignadas bajo un criterio criptográficamente seguro. Conforme a esto, es fundamental que el sistema cuente con un sistema de autenticación y reconocimiento de credenciales del agente ante la organización. Adicionalmente, el sistema debe definir, controlar y gestionar un conjunto de misiones de espionaje específicas a realizar por parte de cada uno de los agentes. Estas misiones se encuentran relacionadas y definidas con respecto a un conjunto de datos personales obtenidos de forma alternativa. La idea en general, consiste en que cada agente debe realizar un conjunto de misiones seleccionadas de forma aleatoria. De igual forma, el agente en cuestión, puede realizar consultas adicionales sobre su estado e información personal y consultar un registro e historial de misiones de espionaje realizadas recientemente. Finalmente, un agente puede optar por darse baja de la organización, a través del consumo de una "píldora de cianuro virtual", la cual, de forma análoga a su contraparte en la realidad debería eliminar los registros e información referente al espía actual.

Actualmente, la agencia ha dispuesto tres tipos de misiones de espionaje específicas:

  1. Recuperar la información personal completa de un ciudadano específico a partir del nombre de usuario que tal individuo usa en la mayoría de servicios a los cuales se encuentra adscritos en línea. Esta información incluye: Nombres y Apellidos, Dirección de Residencia, Número de contacto, Lugar de trabajo (Si tiene), grupo y RH sanguíneo, Números y claves asignados a tarjetas de crédito, entre otras. Es necesario agregar que, en ocasiones, la agencia puede solicitar que un individuo desaparezca.
  2. Establecer la posición (latitud, longitud) actual de un usuario determinado.
  3. Finalmente, debe ser posible predecir si un usuario específico realiza labores de espionaje para la agencia contrincante.

Con el objetivo de implementar este sistema, la agencia desea que la implementación final haga uso de un diccionario con el fin de realizar cada operación crítica disponible: Cargar el conjunto de datos que almacena la información personal de alrededor de 370000 individuos situados en diversos países del mundo, consultar la información completa de un usuario específico y eliminarlo, en caso de ser necesario. Asímismo, debe poder realizar la consulta de la información completa del agente actualmente activo en el sistema, y eliminarlo del sistema, si este lo considera necesario.

Instrucciones de desarrollo

Nota: Antes de iniciar, lea la sección 0. Envío de talleres: Términos y Condiciones, en esta sección se encuentran enumeradas las reglas y recomendaciones de desarrollo y envío de proyectos establecidas a lo largo del curso.

  1. Por favor, descargue el esqueleto del ejercicio
  2. En primer lugar, verifique las recomendaciones descritas en los archivos SpyAgency.java y SpySystem.java (Disponibles bajo el paquete spy.dictionary.agency). Si considera que las sugerencias otorgadas se adecúan al estado actual de su implementación, puede hacer caso omiso de estas.
  3. En segundo lugar, realice la elección de una agencia de inteligencia (SVR/CIA), al igual que las proporciones sugeridas de sal en una receta de cocina, este parámetro se dispone al gusto. Es posible hallar las clases de descripción de las agencias de inteligencia (CIA.java o SVR.java) dispuestas previamente, bajo el paquete spy.dictionary.agency, disponible en el directorio src.
  4. A continuación, lea detenidamente las instrucciones dispuestas en cada archivo y proceda a implementar las funcionalidades solicitadas, respectivamente.
  5. Posteriormente, realice el registro de la agencia de su elección en la clase SpySystem.java.
  6. Finalmente, dirigirse al archivo SpyCLI y completar las instrucciones dispuestas.
  7. Verificar el funcionamiento completo de la aplicación. En caso de que algún inconveniente sea detectado, por favor realizar las correcciones pertintentes y adecuadas.

Reto (Opcional)

Preguntas

  1. ¿Por qué es posible afirmar que la implementación de una Tabla de Hash que hace uso de Encadenamiento separado como procedimiento principal de resolución de colisiones, cuenta con una mayor eficiencia que una implementación que hace uso de Direccionamiento abierto? Realice una comparación directa entre el modo de operación de cada procedimiento al momento de realizar una operación crítica sobre el diccionario.
  2. ¿Es posible implementar un diccionario basado en una estructura de árbol? Describa de forma breve una posible implementación.
  3. En el presente ejemplo, suponer que se desea implementar una clase que describa a un ciudadano. De acuerdo a los atributos descritos en el archivo de descripción de ciudadanos, definir una función de hash (Reimplementando la función hashCode()) que represente a un ciudadano. Esta función debe cumplir todas las restricciones impuestas a largo de la sección: Funciones de hash y resolución de colisiones.

Entrega para bonificación

Fecha límite de entrega: Ver

  1. Verifique que su aplicación cumple con las condiciones descritas en Envío talleres.
  2. Conteste las preguntas en el archivo README.txt.
  3. Realice pruebas unitarias para el funcionamiento de la aplicación. Estas deben encontrarse en el paquete taller.test. Como como mínimo sus pruebas deberían validar los siguientes casos:
    • Verificar si es posible eliminar a un individuo.
    • Establecer si toda la información presente en el archivo de descripción de ciudadanos es cargada de forma efectiva en su implementación de diccionario basado en una tabla de hash. Tras cargar la información, debe generar un archivo de salida, el cual, debe ser equivalente al archivo inicial. Comparar ambos archivos y decidir si la información fue cargada de forma efectiva.
    • Definir si el procedimiento de búsqueda de información retorna resultados adecuados. Puede hacer uso de los archivos de prueba users.spy y values.spy, presentes bajo el directorio data.
  4. Realice un gráfico comparativo (Tamaño de la entrada vs Tiempo de ejecución) para cada una de las operaciones críticas (Agregar, Consultar y Eliminar) entre su implementación de Tabla de hash y la implementación dispuesta por parte de la librería estándar de Java, Hashtable. ¿Qué implementación se considera más eficiente? Nota: Puede hacer uso de la clase Stopwatch, usada a lo largo del Taller 4.
  5. Cargue el taller a su repositorio en Bitbucket. No olvide crear el archivo calificacion.txt