31 de marzo de 2017

Pilas (definición y operaciones primitivas).

Definición.
   La pila es un objeto dinámico en constante cambio.

   Una pila es un conjunto ordenado de elementos en el cual se pueden insertar y eliminar elementos únicamente por un extremo: el tope de la pila.

   La característica más importante de una pila es que el último elemento insertado en ella es el primero en eliminarse, mientras que el primero que fue insertado es el último en eliminarse. Por esta razón se dice que una pila es una estructura de datos de tipo LIFO (Last In First Out).

   El proceso de inserción y eliminación de elementos puede observarse en la siguiente figura en donde se muestra, por medio de una flecha, la representación del tope de la pila. Observe cómo con cada inserción o eliminación se modifica el tope de la pila.

Crecimiento y decrecimiento de una pila.
 
    La representación mostrada en la figura anterior permite visualizar todos los elementos de la pila, sin embargo, es importante señalar que en un momento dado únicamente se tiene acceso al elemento que está siendo referido por el tope de la pila, los demás elementos permanecen ocultos, tapados por decirlo de alguna manera, por el conjunto de elementos que se encuentran encima de cada uno de ellos, con excepción del que está en el tope de la pila.

Operaciones primitivas.
   Las operaciones primitivas o fundamentales definidas sobre una pila son la inserción (push) y la eliminación (pop).
  1. El comportamiento definido para la operación push consiste en insertar un nuevo elemento en la pila, mismo que constituirá el nuevo tope de la pila.
  2. El comportamiento definido para la operación pop elimina el elemento referido por el tope de la pila modificando en consecuencia el tope de la pila. El nuevo tope de la pila se refiere ahora al elemento (si existe) que fue insertado inmediatamente antes que el elemento eliminado.
   Existen otras operaciones útiles al usar pilas, como por ejemplo, antes de aplicar la operación pop a una pila, sería conveniente verificar que la pila no esté vacía (operación ¿Está vacía?).

   Otro comportamiento deseable sería la operación "ojeada" (peek), la cual hecha un vistazo al elemento que se encuentra en el tope de la pila y lo regresa pero no lo elimina.

   Las operaciones push, pop y peek, son muy comunes para la estructura de datos pila, por lo que se recomienda conservar dichos nombres en la implementación.

28 de marzo de 2017

Contenido temático.

"Un lenguaje de programación cumple dos propósitos relacionados entre sí: proporciona un vehículo para que el programador especifique acciones que deben ejecutarse y proporciona un conjunto de conceptos para que el programador los use cuando piense en lo que se puede hacer..."
 ...
"Para escribir un buen programa hace falta inteligencia, gusto y paciencia."
Bjarne Stroustrup

Ejercicios selectos (estructuras de datos).

  1. Investigue cómo es que se representan los tipos de datos primitivos en una computadora. Es preciso que conozca cómo se representa un tipo de datos int por ejemplo, ¿cuántos bytes le son asignados a un entero? Los números de punto flotante (float y double por ejemplo), también tiene una representación particular dentro de una computadora basada en los conceptos de mantisa y exponente. Investigue dichos conceptos, así como la representación física (hardware) de los tipos de datos en una computadora convencional.
  2. Modifique el Ejemplo PruebaRacional para que genere una salida como la de la siguiente figura:  . Asegúrese de probar el caso de error tanto para el constructor como para el método estableceDenominador.
  3. Modifique el Ejemplo PruebaRacional para que permita leer datos (números racionales) desde la entrada estándar (teclado).
  4. Considere el Ejemplo Racional, ¿qué valor inicial tiene el objeto Racional s y m en las líneas 44 y 53 respectivamente?
  5. Modifique el Ejemplo Racional para que, en lugar de acceder directamente a los atributos p y q de los objetos s y m (líneas 46-47 y 55-56 respectivamente), se acceda a ellos y se modifiquen sus correspondientes valores a través del método de tipo set correspondiente.
  6. Con base en lo descrito en el blog, modifique el Ejemplo Racional para que cambie la sentencia (línea 46): s.p = p * r.obtenDenominador( ) + q * r.obtenNumerador( ); por: s.p = this.p * r.obtenDenominador( ) + this.q * r.obtenNumerador( ); realice también lo correspondiente para las líneas 47, 55 y 56 respectivamente.
  7. El Ejemplo Racional implementa las operaciones de adición (suma) y multiplicación (multiplica). Para que la implementación sea completa, implemente las operaciones aritméticas faltantes de sustracción y división; utilice resta y divide respectivamente para los nombres de los métodos, y ajústese a la especificación de las operaciones definidas en la sección Especificación del ADT racional de la entrada Tipos de datos abstractos (ADT).
  8. Además de lo desarrollado en el ejercicio anterior, piense en cómo mejorar la definición del ADT racional discutido en el texto. Tome en cuenta, al menos, los siguientes aspectos:
    1. Comparación de igualdad: ¿cuándo se dice que dos números racionales son iguales? Ejemplo: 3 / 21 = 1 / 7.
    2. Simplificación: simplificar a su expresión mínima un número racional, ya sea como resultado de una operación, o simplemente como utilidad. Ejemplo: 3 / 21 => 1 / 7. Sugerencia: obtenga el MCD (Máximo Común Divisor) del numerador y denominador a través de un método privado para simplificar el racional a su expresión mínima.
    3. Cuando haga la representación en cadena del número racional (toString), considere lo siguiente: ¿qué sucede si  el resultado de la simplificación es, por ejemplo 3 / 1?, ¿tendría sentido presentarlo así?, ¿qué sucede si  el resultado de una operación es 0 / 13 por ejemplo? Si el denominador es 1, sólo presente el numerador, por otro lado, si el numerador es cero, sólo presente éste valor para tener una mejor representación en cadena del objeto Racional.
    4. Por último, pero no por ello menos importante, una versión más robusta de Racional podría ser que implementara la interfaz Comparable del API. La idea es aquí definir el método compareTo() para determinar la relación de orden entre dos números racionales; así por ejemplo si r1 = 3 / 4 y r2 = 2 / 5, r1.compareTo(r2) regresaría 1, r2.compareTo(r1) regresaría -1 y 0 si ambos son iguales o equivalentes (vea 8.1).
  9. Sean c1 y c2 dos números complejos definidos de la siguiente manera: c1 = (a + bi) y c2 = (c + di) donde a, b, c, d son números reales. Utilice las definiciones y operaciones siguientes para abstraer un ADT complejo y utilícelas para realizar una implementación de dicha entidad (como se hizo para el Ejemplo Racional). Escriba también una clase de prueba que permita probar la implementación del ADT complejo así como sus respectivas operaciones aritméticas:
    1. La suma de c1 y c2 se define como: c1 + c2 = (a + bi) + (c + di)  = (a + c) + (b + d)i.
    2. La resta de c1 y c2 se define como: c1 - c2 = (a + bi) - (c + di)  = (a - c) + (b - d)i.
    3. La multiplicación de c1 y c2 se define como: c1 * c2 = (a + bi) * (c + di)  = (ac - bd) + (ad + bc)i.
    4. La división es un poco más elaborada debido a que se racionaliza el denominador; es decir, se multiplica el numerador y el denominador por el conjugado del denominador. El conjugado de un número complejo se obtiene cambiando el signo de su componente imaginaria, es decir: si c = a + bi  es un número complejo, su conjugado está dado por c¹ = a - bi, entonces: c1 / c2 = (a + bi) / (c + di)  = [(a + bi) * (c - di)] / [(c + di) * (c - di)] = [(ac + bd) + (bc - ad)i] / (c² + d²).
  10. Considere el Ejemplo Racional2, mismo que muestra el uso de la cláusula (palabra reservada) this e implementa algunas cambios respecto del Ejemplo Racional. Estudie y compare ambos ejemplos a fin de entender sus similitudes y diferencias. Tome en cuenta que, desde el punto de vista funcional (características, servicios y comportamiento de la clase) son exactamente iguales. No olvide probar su funcionamiento.
  11. En base a la explicación dada en la sección Clases autorreferidas de la entrada Abstracción de estructuras de datos, modifique el Ejemplo Nodo de tal forma que sobre cargue el constructor para que, en caso de crear un objeto sin argumentos: Nodo nodo = new Nodo( ); se construya un objeto como el mostrado en la figura: . Utilice cero para el atributo dato y asegúrese de probar el funcionamiento de su constructor.
  12. Diseñe y construya una clase (Cuadratica) que permita instanciar (generar) objetos que representen una ecuación cuadrática de la forma ax^2 + bx + c, donde a, b y c son los coeficientes de la ecuación. Su clase deberá:
    1. Considerar el caso de intentar inicializar un objeto cuyo coeficiente a sea cero y proceder a crear y lanzar una excepción.
    2. Permitir el cálculo de las raíces reales cuando existan.
    3. Lanzar una excepción si las raíces no son reales.

22 de marzo de 2017

Consideraciones adicionales respecto a las ED y los ADT.

   Las nociones de la programación orientada a objetos fueron construidas sobre las ideas y bases teóricas de los tipos de datos abstractos (ADT).
 
   Un ADT es una abstracción sumamente útil, y está estrechamente relacionada con los principios de la orientación a objetos en el sentido en que puede ser definida en términos de las características (modeladas en atributos) y los servicios (representados por los métodos) que ofrece.

   La importancia más significativa en la idea de los ADT es la separación de las nociones de interfaz (servicios) e implementación.

   Por otro lado, la definición y operación de una estructura de datos está en directa relación con la definición de un ADT, por lo que en las secciones de las entradas siguientes, además de definir las estructuras de datos más usuales y convencionales, se presentará un tipo de implementación particular para ellas; sin embargo, es importante que el lector tenga presente que existe más de una posible implementación para una definición de un ADT determinado y que, si en la práctica debe utilizar alguna para resolver algún problema real, lo mejor será recurrir a las estructuras de datos del API o de la biblioteca estándar del lenguaje que utilice. En este blog, la implementación de dichas estructuras persigue un objetivo estrictamente didáctico, y constituyen más un medio para ilustrar el paradigma, que una implementación eficiente.

   Por último pero no menos importante, es menester mencionar que, además de la implementación de las estructuras de datos más comunes, se presentarán también algunas de las aplicaciones tradicionales más representativas, con la principal intención de poner en práctica de manera combinada, tanto los conceptos orientados a objetos, como las de las estructuras de datos propiamente dichas; al mismo que tiempo de que se somete a prueba su implementación.

21 de marzo de 2017

Herencia / Generalización

   Uno de los conceptos del paradigma orientado a objetos más importantes es el de herencia, ya que dicho mecanismo de abstracción permite la re utilización de código de una manera sumamente conveniente, además de habilitar las capacidades del polimorfismo a través de la sobre escritura (override) de métodos.

   Abstracción.
   La ejemplificación del concepto de herencia/generalización estará basada en los Ejemplo Persona y el Ejemplo Cientifico para Java, y en el Ejemplo Herencia para C++; pero antes de poder describirlos, considero pertinente presentar primero en un diagrama de clases los detalles de la relación de generalización que se quiere mostrar con la finalidad de elevar el nivel de abstracción. Con el diagrama de clases propuesto, se pretende llevar el concepto de herencia/generalización a la forma en que la mayoría de las personas comprendemos y analizamos las cosas, para posteriormente profundizar con más conocimiento de causa en los detalles de la implementación de dicho concepto en un lenguaje de programación.

   El diagrama de clases UML (Unified Modeling Language) del que partirá el análisis se muestra en la siguiente figura:
 
Diagrama de clases UML para mostrar la relación de generalización / herencia entre Científico y Persona.

    Los detalles completos de la explicación de un diagrama de clases UML quedan fuera de los alcances de este blog, por lo que sólo se describirán los aspectos más relevantes que ayuden al lector a visualizar de mejor manera, en caso de que el lector no cuente con experiencia en UML, la relación de generalización y herencia.

   Un diagrama de clases UML está compuesto, grosso modo, por clases y las relaciones entre dichas clases. En este sentido, cada clase se representa con un recuadro dividido en tres partes:
  1. Identificador de la clase.
  2. Listado de atributos con la especificación de su clase (tipo) y sus niveles de acceso correspondientes.
  3. Listado de métodos con la especificación de la clase (tipo) de sus argumentos y valor o clase de retorno, así como los niveles de acceso correspondientes para los métodos.
   Tanto para el caso de los atributos como para el de los métodos, los niveles de acceso están representados por un signo de más para un acceso público (+), un signo de menos para un acceso privado (-), y un signo de gato para un nivel de acceso protegido (#).

   Con base en lo anterior, puede observarse de nuestro diagrama que la clase Persona, y por lo tanto las instancias (objetos) que se deriven de ella, tendrán las siguientes características (atributos) comunes a una persona: un nombre, una edad, y una nacionalidad (podrían definirse mucho más características u otras diferentes a las descritas aquí, pero no es la intención del ejemplo representar todas las características completas y comunes a una persona). Observe también que se ha definido un conjunto de operaciones, acciones, responsabilidades o comportamiento comunes a una persona, mismas que se encuentran definidas por los métodos establecidos (al igual que para los atributos, no se ha pretendido modelar por completo el comportamiento o las responsabilidades representadas en los métodos, sino sólo una representación muy general).

   Con base en las aclaraciones previas y lo descrito hasta aquí, es posible decir que una persona promedio está representada de manera muy general por la clase Persona.

   Ahora bien, un científico es (recuerde la idea de división en especializaciones: relación is-a presentada en la entrada Orientación a objetos (conceptos)) una persona, y por lo tanto comparte las características o atributos así como las acciones o el comportamiento inherentes a una persona; y es precisamente este tipo de relación de compartir la que se refiere a la herencia, ya que se dice que en la herencia una clase hereda (comparte) los atributos (características) y métodos (acciones) a otra.

   La herencia en UML se representa por medio de una flecha como la de la figura anterior (diagrama de clases). Es importante señalar que el sentido de la flecha es sumamente significativo, ya que tal y como aparece en nuestra figura, el diagrama indica que la clase Científico hereda las características y el comportamiento de la clase Persona (y no al revés). Otra forma de verlo es que la clase Persona es una generalización de la clase Científico en el sentido de que esta última agrega cierto nivel de especificación respecto de la primera.

   Note también que la clase Científico define un atributo adicional (especialidad), mismo que se añade a todos los atributos que implícitamente ya tiene, mismos que fueron heredados de la clase Persona. Observe también que se han definido cuatro métodos para la clase Científico los cuales tienen las siguientes características:
  1. estableceEspecialidad: es un método de tipo set para el atributo especialidad definido en la clase Científico.
  2. obtenEspecialidad: es un método de tipo get para el atributo especialidad definido en la clase Científico.
  3. mensaje: este método ya estaba definido en la clase Persona, pero al ser redefinido en la clase Científico, se dice que sobre escribe (override) al primero, lo cual significa que un objeto instanciado de la clase Científico, responderá al mensaje mensaje con la definición de su propio método y no con la definición del método mensaje definido en la clase Persona.
  4. mensajeEspecial: este es un nuevo método particular y específico a las instancias derivadas de la clase Científico.
   Es fundamental que el lector se asegure de comprender la descripción hasta aquí realizada respecto a las clases PersonaCientífico. Es también muy importante entender la relación existente entre estas clases antes de continuar a la siguiente sección, en donde entre otras cosas, se abordarán los aspectos relacionados con la implementación de ellas en el lenguaje de programación correspondiente.

Abstracción de estructuras de datos.

El estudio de las estructuras de datos implica, en general, dos propósitos complementarios:
  1. Identificar y desarrollar tanto entidades como operaciones útiles relacionadas con dichas entidades. En este rubro es preciso determinar el tipo de problemas que se solucionan utilizando tales entidades y operaciones.
  2. Determinar representaciones para dichas entidades abstractas, así como implementar las operaciones abstractas en representaciones concretas.
   El primero de estos dos propósitos considera a un tipo de datos de alto nivel como un instrumento que se usa para solucionar problemas. Este propósito está también en estrecha relación con la definición de tipos de datos abstractos (ADT).

   El segundo propósito considera la implementación del tipo de dato o ADT como un problema que se va a resolver utilizando objetos o elementos existentes por medio de la herencia (relación es-un (is-a)) o la composición (relación tiene-un (has-a)).
 
    Como ya se ha mencionado, en ocasiones ninguna implementación tanto de hardware como de software puede modelar en su totalidad un concepto matemático (un tipo de dato entero o real por ejemplo), por lo que es importante conocer las limitaciones de una implementación particular, ya que una consideración fundamental de cualquier implementación es no sólo su efectividad sino también su eficiencia.

Clases autorreferidas.
   La implementación de las estructuras de datos que se desarrollarán en el blog estarán basadas en un concepto muy importante: la autorreferencia.

   En el contexto de la orientación a objetos, la autorreferencia es la capacidad que tienen los objetos de una clase de almacenar explícitamente una referencia a objetos de su misma clase, es decir, a objetos de su mismo tipo.

   Considere el Ejemplo Nodo Java (Ejemplo nodo C++), el cual muestra una clase autorreferida con dos atributos:
  1. dato: el atributo que representa el elemento a almacenar en el nodo.
  2. siguiente: el cual es una referencia a un objeto cuya clase es la misma que lo define (Nodo), y por lo tanto, es una autorreferencia.
   En el área de las estructuras de datos, un nodo es la unidad mínima de almacenamiento dentro de la estructura de datos, y puede ser tan simple o elaborado como se requiera.

   Para el caso del Ejemplo Nodo, el nodo únicamente almacena enteros primitivos (int), pero como se discurrirá más adelante, es posible representar y almacenar entidades más elaboradas que un número entero.

   Considere la creación de un objeto nodo instanciado de la clase Nodo (Java) y nodo (C++):

Nodo nodo = new Nodo(1974);    // Java: declaración y definición de "nodo"
Nodo nodo(1974);    // C++: declaración y definición de "nodo"

y su correspondiente representación mostrada en la siguiente figura:

Representación de un objeto de la clase Nodo (Ejemplo Nodo).

   En la figura anterior puede apreciarse que un objeto es en realidad una referencia a una instancia (entidad) con características definidas por la clase de la que deriva, que para el caso específico del Ejemplo en turno están dadas por los atributos dato y siguiente.
 
    En este punto quizá valga le pena recordar algo sutil pero sumamente importante: la diferencia entre declaración y definición. Para no extenderse innecesariamente de más, se tomará el caso de Java:
 
Nodo nodo;    // Declaración de "nodo" (cuadro izquierdo en la representación gráfica)
.
.
.
nodo = new Nodo(1974);    // Definición de "nodo" (objeto con dos campos en la representación gráfica)
 
es habitual, pero no necesario, que la declaración y la definición del objeto vayan juntas (como se hizo al mostrar el ejemplo de instanciación líneas arriba). Sin embargo, también es posible declarar las variables que harán referencia a los objetos, para posteriormente crear explícitamente los objetos (new) mismos que serán referidos por la variable a la que se asignan (como lo hacen los constructores). En Java no existe el concepto explícito de referencia (apuntador); sin embargo una variable cuyo tipo es una clase, en realidad es una referencia al inicio de la memoria de la instancia de una clase, por lo que cuando hablamos de un "objeto", nos valemos de una abstracción que se refiere a la instancia propiamente dicha y a la variable que la refiere.

   Ahora bien, observe la relación entre el Ejemplo Nodo y la figura anterior de su representación, y note cómo en el constructor el objeto es inicializado con el valor recibido como argumento, y con null (nullptr) para la referencia siguiente, lo cual ha sido representado en la figura anterior con una diagonal (\) para enfatizar que la referencia representada por el atributo siguiente no hace referencia inicialmente a ningún otro objeto. Observe también que la clase o tipo del objeto nodo es la misma que la del atributo siguiente, lo cual constituye la autorreferencia que es el concepto que se desea ilustrar. Asegúrese de comprender lo anterior antes de continuar.

Implementación.
   Con base en lo descrito en la sección anterior, es posible decir que las estructuras de datos consisten, de manera general, en un conjunto de nodos ordenados en una secuencia lógica como la que se muestra en la siguiente figura:

Secuencia de nodos formados con objetos autorreferidos.

   Las estructuras de datos estudiadas en las entradas siguientes tendrán en general la forma o estructura representada por esta figura.
 
   Por otro lado, el mecanismo utilizado para la inserción y la eliminación de nodos en la estructura de datos, estará en función directa de las reglas especificadas por la definición de la estructura de datos.

   Finalmente, la especificación de las características de la estructura de datos se implementarán a través de sus atributos, mientras que la especificación de las reglas de operación o de comportamiento serán implementadas por medio de sus métodos.

13 de marzo de 2017

Tipos de datos abstractos (ADT).

   Desde el punto de vista de la programación, es importante que los programadores puedan definir sus propias abstracciones de datos, de tal forma que dichas abstracciones trabajen de manera parecida a las abstracciones o a las primitivas de datos proporcionadas por el sistema subyacente.

   Un tipo de dato abstracto o ADT (Abstract Data Type) es definido por una especificación abstracta, es decir, permite especificar las propiedades lógicas y funcionales de un tipo de dato.

   Desde el punto de vista de los ADT, un tipo de dato es un conjunto de valores y un grupo de operaciones definidas sobre dichos valores. El conjunto de valores y el de las operaciones forman una estructura matemática que se implementa usando una estructura de datos particular de hardware o de software.

   El concepto de ADT está relacionado con la concepción matemática que define al tipo de datos por lo que, al definir un ADT como concepto matemático, no interesa la eficiencia del espacio o del tiempo (los cuales son aspectos relacionados con la implementación del ADT), sino las propiedades y características inherentes a él. La definición de un ADT no se relaciona en lo absoluto con los detalles de la implementación; de hecho, tal vez ni siquiera sea posible implementar un ADT particular en ningún tipo de hardware o software (piense por ejemplo en los números reales y en la propiedad de la densidad de los números reales por ejemplo).

   Un ADT consta de dos partes: una definición de valor y una definición de operador, mismas que se describen a continuación:
  1. La definición del valor establece el conjunto de valores para el ADT y consta a su vez de dos partes:
    1. Una cláusula de definición.
    2. Una cláusula de condición. Para la definición de un ADT racional por ejemplo, una cláusula de condición estaría relacionada con la restricción de que el denominador de un número racional no puede ser cero.
  2. En la definición del operador cada operador está definido como una operación abstracta con condiciones previas opcionales, y las condiciones posteriores o postcondiciones.
   Por otro lado, para la implementación de un ADT, es necesario tomar en cuenta los siguientes aspectos:
  • Hacer disponible (pública) la definición del nuevo tipo.
  • Hacer disponibles un conjunto de operaciones que puedan ser utilizadas para manipular las instancias del tipo definido (métodos públicos de servicios).
  • Proteger los datos asociados con el tipo de dato que está siendo definido (atributos privados), de tal forma que dichos datos sólo puedan ser accedidos por medio de los métodos proporcionados para ello.
  • Poder generar múltiples instancias del tipo definido, preferentemente, con más de una opción de inicialización, siempre que ésto no entre en contradicción con la definición o restricciones del tipo.
   Es importante resaltar que, asociado con un ADT particular, puede haber una o más implementaciones distintas.

   En resumen, los ADT son un mecanismo de abstracción sumamente importante y, dado que la programación orientada a objetos (POO) se fundamenta en la abstracción, es posible decir que constituye uno de los pilares de la orientación a objetos.

Especificación del ADT racional.
   Existen varios métodos para especificar un ADT, desde notaciones matemáticas hasta descripciones detalladas hechas en lenguaje natural. Lo importante de la especificación es que sea clara y no ambigüa.

   Esta sección, debido a las limitaciones de formato inherentes al blog, hará uso de algo parecido a una notación matemática apoyándose del lenguaje natural para la especificación del ADT racional.

   Sea r un número racional (Q). Se define r como el cociente de dos números enteros, es decir:


r = p / q

donde p, q son números enteros (Z) y q distinto de cero (!=0).

   Las operaciones aritméticas de suma, resta, multiplicación y división de dos números racionales se especifican a continuación.

   Sean r1 y r2 son dos números racionales (Q) definidos como:

r1 = p1 / q1 con p1, q1 números enteros (Z) y  q1 != 0

r2 = p2 / q2 con p2, q2 números enteros (Z) y  q2 != 0
entonces:
  1. r1 + r2 = (p1 / q1) + (p2 / q2) = [ (p1 * q2) + (p2 * q1) ] / (q1 * q2).
  2. r1 - r2 = (p1 / q1) - (p2 / q2) = [ (p1 * q2) - (p2 * q1) ] / (q1 * q2).
  3. r1 * r2 = (p1 / q1) * (p2 / q2) = (p1 * p2) / (q1 * q2).
  4. r1 / r2 = (p1 / q1) / (p2 / q2) = (p1 * q2) / (q1 * p2).

   Observe la especificación de los valores para el ADT racional, y la restricción que existe sobre el valor del denominador representado por q1 y q2 respectivamente.

   Finalmente, note que se ha proporcionado también la especificación de las operaciones aritméticas asociadas al ADT.


6 de marzo de 2017

Ejercicios selectos (transición).

  1. Investigue más acerca del concepto de máquina virtual y de los bytecodes ¿Fue Java el primer lenguaje de programación en incorporar dichos conceptos?
  2. Para el programa del Ejemplo Bienvenido2 pruebe lo que sucede si elimina el espacio que aparece al final de la cadena Bienvenid@. No olvide volver a compilar.
  3. Considere el Ejemplo Bienvenido3 e investigue qué otras secuencias de escape existen, también infórmese si dichas secuencias coinciden o no con las que se utilizan en el lenguaje de programación C.
  4. En base a lo expuesto para el Ejemplo Bienvenido4 investigue qué otros especificadores de formato existen. Infórmese también si dichos especificadores coinciden o no con los que se utilizan en el lenguaje de programación C.
  5. Escriba un programa que imprima en la salida estándar su nombre (el nombre del lector). El nombre o nombres deberá aparecer en el primer renglón, el primer apellido en el segundo renglón y el segundo apellido en el tercer renglón.
  6. Utilice el Ejemplo Lectura y cambie la clase Integer por el tipo primitivo int. Compruebe si es necesario o no hacer algún otro tipo de cambio para que el programa funcione.
  7. En base a lo descrito en el Ejemplo Lectura modifique dicho ejemplo para agregar las cuatro operaciones aritméticas: suma, resta multiplicación y división. Los operadores aritméticos son los tradicionales: +, -, * y /. Realice lo anterior para números enteros representados como objetos (Integer), y como tipos de datos primitivos.
  8. Modifique el Ejemplo Lectura para procesar ahora números Float y Double. Tome en cuenta que deberá consultar el API para cambiar el método nextInt por el método apropiado. Investigue también si existen los tipos de datos primitivos correspondientes (float y double).
  9. Con base en lo descrito en el Ejemplo Lectura, modifique dicho ejemplo para que solicite al usuario su nombre completo. Tome en cuenta que deberá leer tres cadenas como se describe a continuación, y que su programa deberá imprimir el nombre completo por apellidos en una sola línea:
    1. Su nombre o nombres.
    2. Su primer apellido.
    3. Su segundo apellido

 10. Para el Ejemplo If, ¿qué sucede si cambia la estructura de selección if por if-else? ¿Se obtiene el mismo funcionamiento? Si cambia el funcionamiento, ¿por qué? Determine su respuesta y después corroborela haciendo los cambios correspondientes. No olvide volver a compilar.

 11. Escriba un programa que presente un menú con las cuatro operaciones aritméticas y una opción para salir. Su programa deberá procesar la opción y realizar la operación correspondiente, así como mantenerse repitiendo el menú hasta que se proporcione la opción de "Salir". Investigue también si el lenguaje Java incorpora una estructura de selección múltiple (switch) como la del lenguaje C. Para este ejercicio, basta con utilizar una estructura if-else anidada. El menú deberá ser como se describe a continuación:

  • Suma.
  • Resta.
  • Multiplicación.
  • División
  • Salir.

 12. Modifique el Ejemplo Arreglo para que, utilizando el procesamiento de argumentos en la línea de comandos como el que se hizo en el Ejemplo MainArgs acepte tres argumentos. Su programa deberá generar un arreglo de n enteros con un valor inicial para el primer elemento y un incremento para los demás. Observe que los elementos de args son cadenas, por lo que tendrá que consultar el API para utilizar métodos de conversión de cadenas a números enteros.

Sugerencia: consulte el método parseInt de la clase Integer. Los argumentos a procesar en la línea de comandos son:

  • Tamaño del arreglo (n).
  • Valor inicial (valor).
  • Incremento (incremento).

 13. Siguiendo la idea del ejercicio anterior, escriba un programa que procese el tamaño (n) de un arreglo desde la línea de comandos y:

  • Genere un arreglo de enteros de tamaño n.
  • Solicite y almacene n enteros en el arreglo.
  • Determine, haciendo un recorrido del arreglo, el número mayor.
  • Determine, haciendo un recorrido del arreglo, el número menor.
  • Determine, haciendo un recorrido del arreglo, el promedio (media aritmética).
  • Determine, haciendo un recorrido del arreglo, la moda (el número que más veces aparece).
  • Determine, haciendo un recorrido del arreglo, si un número determinado está o no en el arreglo (búsqueda lineal).

 14. Consulte al menos la entrada Excepciones para introducirse en el tema y ampliar un poco más su conocimiento respecto al uso y manejo básico de excepciones en Java.
 15. Considere el Ejemplo Coleccion. Investigue en el API las colecciones, particularmente la colección ArrayList y determine el funcionamiento del programa antes de compilarlo y ejecutarlo en la máquina virtual de Java. Compruebe su deducción respecto al funcionamiento con la salida real del programa. 


Un vistazo al lenguaje Java.

   El lenguaje de programación Java (Java es una marca registrada de Oracle Corporation) es amado por muchos y odiado por otros y no participaré en un debate estéril y ocioso. Sólo diré que, como casi todo en la vida, Java tiene sus ventajas y desventajas; lo que es innegable es que es un lenguaje de programación ampliamente difundido y utilizado y en ese sentido, resulta importante conocerlo y familiarizarse con él, independientemente de las posturas ideológicas y preferencias personales.

   Esta entrada del blog no es un tratado del lenguaje; es más, ni siquiera se acerca a un resumen, es más bien un compendio de referencia a la mano para el lector familiarizado con algún lenguaje de programación.

   La referencia obligada para esta entrada y para todo el blog en general es el API (Application Programming Interface) correspondiente a la versión 8 del lenguaje.

Orígenes y características.
   Java es un lenguaje de programación originalmente desarrollado por James Gosling cuando trabajaba en la desaparecida empresa Sun Microsystems, la cual fue adquirida por Oracle Corporation en el año 2009.
 
   El lenguaje fue publicado oficialmente en 1995 y deriva su sintaxis de C y C++; sin embargo, cuenta con menos facilidades de bajo nivel que cualquiera de ellos. Por otro lado, las aplicaciones o programas de Java son generalmente compiladas a bytecodes, los cuales pueden procesarse en cualquier máquina virtual Java (JVM) sin importar la arquitectura de la computadora, permitiendo así una mayor portabilidad del software entre plataformas.
 
   Java es un lenguaje de programación de propósito general, concurrente, basado en clases, y orientado a objetos, diseñado específicamente para tener tan pocas dependencias de implementación como fuera posible. Su intención es permitir que los desarrolladores de aplicaciones escriban el programa una vez, y lo ejecuten en cualquier dispositivo (WORA - Write Once, Run Anywhere).

Estructura general de una clase.
   La estructura general de la definición de una clase en Java es como la que se muestra en el Ejemplo EstructuraJava.

   Las líneas 1-5 muestran el uso de comentarios, se recomienda ampliamente iniciar la definición de cada clase con un comentario que describa el propósito de la clase. También es posible definir comentarios de la forma que se muestra en las líneas 10, 13, 17, y 18.

   La línea 6 muestra la definición de paquetes. Un paquete es un conjunto de clases relacionadas y la palabra reservada package, especifica a qué paquete pertenecen todas las clases definidas en el archivo fuente.

   En Java es posible definir más de una clase por archivo pero sólo una de ellas puede ser pública, y su nombre (identificador) debe corresponder con el nombre del archivo que la contiene. Para el caso del ejemplo anterior, el nombre de la clase es EstructuraJava y el del archivo EstructuraJava.java.

   La línea 7 muestra la importación de clases. Las clases se encuentran ubicadas en paquetes dentro del API, y cuando una clase utiliza alguna clase definida en algún otro paquete, ésto se especifica con la palabra reservada import.

   Las clases se definen por medio de la cláusula class y un identificador. En general, Java define tres niveles de acceso:
  1. public (público) hace que una clase, método o atributo sea accesible para cualquier otra clase.
  2. protected (protegido) hace a un método o atributo accesible únicamente por las clases del mismo paquete, o por subclases de la clase.
  3. private (privado) hace a un método o atributo accesible únicamente desde su propia clase.
   La línea 11 muestra la definición de atributos, los cuales están compuestos por un identificador para el objeto (objeto), y el nombre de la clase de la que se derivará o instanciará. La definición de todos los atributos necesarios para la clase, siguen la misma estructura.

   Las líneas 14-15 muestran la definición de constructores. En la instanciación o generación de nuevos objetos, los objetos se construyen, por lo que no es posible crear un nuevo objeto sin un constructor. Un constructor es el código que se procesa cuando se crea un objeto a través de la cláusula new. La construcción de un objeto es un mecanismo mucho más elaborado del que aquí se describe, pero la explicación a detalle queda fuera de los alcances de esta entrada, y con la generalidad que se ha comentado antes, basta por ahora.

   Finalmente, las líneas 19-20 muestran la definición de métodos. Los métodos siguen los niveles de acceso descritos con anterioridad, pueden o no regresar un objeto de alguna clase (ClaseR) o un tipo de dato primitivo; y puede haber tantos como servicios quiera proporcionar la clase que los define.

Bienvenid@ a Java.
   El Ejemplo Bienvenido1 muestra el primer programa en Java que se describirá. La línea 5 del ejemplo muestra el punto de entrada de cualquier programa en Java: el método main, éste método siempre tendrá la forma que se muestra, la cual se conoce en general como la firma del método. La explicación y los detalles de args se revisará en los Ejemplos selectos de transición.

   En Java sólo es posible enviar mensajes a objetos que definan métodos públicos; sin embargo, la clase Bienvenido1 establece que su método main es static, lo cual quiere decir que puede ser invocado (llamado) sin una instancia específica u objeto que lo reciba. De hecho ésto es un mecanismo que utiliza Java para poder generar clases de utilerías o servicios sin embargo su uso debería ser minimizado, ya que se incurre en el estilo de la programación estructurada al utilizar dichas clases como bibliotecas de funciones.

   Finalmente, la forma más común de imprimir mensajes en la salida estándar (pantalla), es la que aparece en la línea 6 del Ejemplo Bienvenido1. System es una clase de servicios que tiene Java, y entre dichos servicios está el método println del objeto out, el cual recibe como argumento un objeto que representa una cadena (String), y lo envía a la salida estándar imprimiendo un salto de línea al final. La salida del Ejemplo Bienvenido1 se muestra en la siguiente figura:

Salida del Ejemplo Bienvenido1.

   Una versión ligeramente modificada del Ejemplo Bienvenido1 se muestra en el Ejemplo Bienvenido2.

   Observe ahora que en la línea 6 se ha cambiado el método println por el método print. Este último hace lo mismo que el método println con la diferencia de que el método print no imprime un salto de línea al final, de ahí que se haya dejado un espacio al final de la cadena Bienvenid@. La salida del Ejemplo Bienvenido2 es idéntica a la del Ejemplo Bienvenido1.

   Un tercera variación del Ejemplo Bienvenido1 se muestra en el Ejemplo Bienvenido3, el cual muestra el uso de la secuencia de escape \n para introducir un salto de línea en cualquier parte de la cadena que se desea imprimir. La salida del Ejemplo Bienvenido3 se muestra en la siguiente figura:

Salida del Ejemplo Bienvenido 3.

   Finalmente se presenta el Ejemplo Bienvenido4, el cual hace uso de la función printf para imprimir un mensaje en la pantalla. Aquellos lectores que estén familiarizados con el lenguaje de programación C se sentirán cómodos utilizando dicha función.

   Sin entrar mucho en detalles, sólo se indicará que %s es un especificador de formato que le indica a la función printf que imprima una cadena, misma que tomará después de la primera coma (,). Es importante señalar que por cada especificador de formato (tres en el ejemplo) debe existir su correspondiente cadena. La salida del Ejemplo Bienvenido4 es idéntica a la salida del Ejemplo Bienvenido3.

Compilación.
   Existen diferentes entornos de programación o (IDE - Integrated Development Environment) que pueden ser utilizados para desarrollar programas en Java, tales como JavaBeans, JCreator, Eclipse, etc., se recomienda al lector buscar y familiarizarse con alguno de ellos o con algún otro IDE que sea de su preferencia.

   Esta sección describe muy brevemente los pasos para la compilación desde la línea de comandos, ya que los programas de ejemplo de todo el blog pueden ser visualizados y editados en cualquier editor de texto, y compilados con el compilador de Java (javac) sin necesidad de un IDE. Es importante aclarar que se asume que se tiene instalado el jdk (java development kit). Si tiene dudas al respecto, consulte los detalles de instalación del jdk en la página oficial de Java.

   Para saber la versión de Java que tiene instalada, puede escribir desde la línea de comandos:

   $ javac -version

   Lo que deberá aparecer en su pantalla es la versión correspondiente del compilador; si aparece un mensaje distinto, es probable que no tenga instalado el jdk o que las rutas de acceso no sean las correctas.

   Para compilar el programa del Ejemplo Bienvenido1 (descrito en párrafos anteriores), tiene que escribir:

   $ javac Bienvenido1.java

   Cuando un programa se compila siguiendo la idea planteada, se buscarán todas las clases requeridas dentro del directorio de trabajo actual, mismo que corresponde al directorio en donde se haya ejecutado el compilador de Java. Si alguna clase tuviera algún problema, se reportará dicha situación antes de volver a visualizar el símbolo del sistema ($); en otro caso, se visualiza de manera casi inmediata el símbolo del sistema y observará que se han creado nuevos archivos, los cuales corresponden a los nombres de las clases pero con extensión class, mismos que representan los bytecodes que interpreta la máquina virtual de Java.

   La máquina virtual de Java o JVM es la encargada de interpretar y procesar los bytecodes que representan las instrucciones del programa compilado. La JVM está representada por el programa java, por lo que, para ejecutar un programa en Java, se debe proporcionar a la JVM la clase principal, la cual es la que contiene el método main:

   $ java Bienvenido1

   La salida del comando anterior, debería ser el mensaje presentado en la siguiente figura:

Salida esperada después de compilar y ejecutar el Ejemplo Bienvenido1.  




3 de marzo de 2017

Estructuras de datos (tipos de datos y referencias).

   Probablemente el lector esté familiarizado con el concepto de tipo de dato, ya sea debido a que tenga experiencia previa con algún lenguaje de programación, o simplemente porque ha revisado la entradas correspondientes a Un vistazo a Java (Un vistazo a C++) o las relacionadas a los conceptos de la Programación Orientada a Objetos. En este sentido valdría la pena preguntarse ¿cómo se podría definir lo qué es un tipo de dato?

   Un tipo de dato es un método para interpretar un patrón de bits. Una secuencia de bits determinada podría ser interpretada de una forma u otra y representar algún tipo de información específica en función del tipo de dato.

   En la mayoría de los lenguajes de programación, el programador especifica mediante las declaraciones de variables u objetos, cómo es que el programa va a interpretar el contenido de la memoria de la computadora.

   Las declaraciones también le especifican al compilador exactamente, qué es lo que representan los símbolos de las operaciones que se utilizarán, ya que aunque en apariencia es lo mismo, los mecanismos de implementación de una operación aritmética tan aparentemente simple como la adición, difieren de un tipo de dato a otro.

   Por otro lado, para la mayoría de los lenguajes de programación los nombres de las variables o los identificadores asociados a los objetos, son en realidad referencias, es decir, direcciones de memoria en las que se almacenan físicamente los objetos a los que se refieren.

   El manejo de referencias o direcciones de memoria puede ser explícito como en el caso de los lenguajes C y C++ por ejemplo, donde el manejo de referencias se realiza a través de apuntadores. En algunos otros lenguajes como Java y C# el manejo de referencias es implícito, es decir, se realiza a través del nombre o identificador de los objetos.
 
   Tanto el manejo de referencias explícito como el implícito tienen sus ventajas y desventajas, y las fortalezas de uno son las debilidades del otro y viceversa. No es la intención de esta entrada ni la del blog extenderse en dichos aspectos, ya que para los objetivos específicos que se persiguen, basta con saber que Java hace uso de referencias implícitas, y que el nombre o identificador de los objetos es en realidad una referencia y no los objetos en sí mismos. Por otro lado, C++ utiliza tanto referencias implícitas como explícitas.

   En entradas y secciones posteriores se detallarán y ejemplificarán tanto el concepto de autorreferencia como el manejo de referencias para los objetos, elementos que serán indispensables para la construcción y manipulación de las estructuras de datos que se implementarán.



2 de marzo de 2017

Estructuras de datos (panorama general).

   De manera general, es posible decir que una computadora es una máquina que manipula y procesa datos.

   Ahora bien, las estructuras de datos están relacionadas con el estudio de cómo es que se organizan los datos dentro de una computadora, así de cómo es que se manipulan, procesan y emplean dichos datos para representar información que sea de utilidad para las personas (abstracción).

   Existen muchos tipos de estructuras de datos, y para cada una de ellas hay diferentes variaciones que las particularizan y especifican para un contexto de uso particular.

   Un tratado amplio y completo de las estructuras de datos queda fuera de los alcances de este blog, por lo que sólo se mencionarán algunas de las estructuras de datos más comunes y convencionales, así como algunas de sus variaciones.

   A continuación se presenta una descripción muy general de las estructuras de datos que se analizarán en entradas posteriores:
  • Pilas: son estructuras de datos ampliamente utilizadas y sumamente importantes en compiladores y sistemas operativos por ejemplo. En una pila, las inserciones y las eliminaciones se efectúan únicamente en un extremo de la estructura de datos: su parte superior.
  • Colas de espera: este tipo de estructuras de datos representan en general líneas de espera; las inserciones se efectúan en la parte posterior de la misma y las eliminaciones se realizan por la parte delantera.
  • Listas enlazadas: son colecciones de elementos de datos alineados en una fila. En una lista enlazada, las inserciones y las eliminaciones se efectúan en cualquier parte de la estructura de datos.
  • Árboles binarios: son estructuras de datos que facilitan la búsqueda, la clasificación u ordenamiento de los datos a alta velocidad, la eliminación de elementos duplicados, la representación de sistemas de archivos y directorios, y las expresiones de compilación entre otras muchas aplicaciones.
   Cada una de estas estructuras de datos tienen muchas otras y muy interesantes aplicaciones, algunas de las cuales, se presentan y describen en las entradas correspondientes a cada una de ellas.