Lee el capítulo 1 "Java básico" del libro "Estructuras de datos en Java" de M. A. Weiss, exceptuando el apartado 1.3.4 "Entrada y salida por terminal". No es necesario que resuelvas los ejercicios del final del capítulo ahora. Si no entiendes algo ahora, deberás acabar entendiéndolo a lo largo del módulo 0.

Lee, compila y prueba este EjemploLecturaDatos.java. La clase Scanner no se explica en el libro anterior, se introdujo en una versión de Java posterior y la usaremos desde el principio para leer datos de la entrada estándar. Para ver una explicación detallada de lo que se hace en ese ejemplo, lee el apartado 2.5 "Otra aplicación en Java: suma de enteros" del libro "Java: cómo programar" de P. J. Deitel y H. M. Deitel.

En este directorio puedes encontrar seis ejemplos de programas Python de un curso de fundamentos de programación. Reescríbelos empleando lenguaje Java, prestando atención a todo lo necesario para que el resultado sea el mismo. Si necesitas funciones matemáticas, busca información sobre la clase Math de Java. Utiliza de momento tu editor preferido, el compilador javac y el intérprete java, y comprueba que no hay errores. Tras intentar cada uno de ellos (no antes) compara tu solución con la que puedes encontrar en este directorio de soluciones y después pasa a intentar el siguiente. La próxima semana en clase de teoría veremos esas soluciones y después pasaremos a profundizar en el tema de operadores y expresiones.

Dedica el resto de horas de trabajo no presencial a traducir de Python a Java tus soluciones de otros ejercicios de Programación I que te hayan gustado y que se puedan resolver con lo que conoces por ahora de Java.

Piensa cuál es el resultado de ejecutar cada uno de los siguientes programas. Todos ellos son ejercicios sobre evaluación de expresiones. Después de pensar cada uno, compílalo y ejecútalo para verificar si has acertado. La próxima semana en clase se explicarán.

• Ej01_OperadoresCadenas.java
• Ej02_AsignacionEsOperador.java
• Ej03_AutoasignacionEsOperador.java
• Ej04_Autoincremento.java
• Ej05_Autoincremento.java
• Ej06_Autoincremento.java
• Ej07_Autoincremento.java
• Ej08_Autoincremento.java
• Ej09_AsignacionAutoincremento.java
• Ej10_PrioridadesOperadoresLogicos.java
• Ej11_CortocircuitoEfectosSecundariosSalida.java
• Ej12_CortocircuitoEfectosSecundariosSalida.java
• Ej13_CortocircuitoEfectosSecundariosSalida.java
• Ej14_CortocircuitoEfectosSecundariosAsignaciones.java
• Ej15_CortocircuitoEfectosSecundariosAsignaciones.java
• Ej16_CortocircuitoEfectosSecundariosAutoincremento.java
• Ej17_CortocircuitoEfectosSecundariosAutoincremento.java
• Ej18_OperadorCondicional.java
• Ej19_VariableControlBucles.java
• Ej20_VariableControlBuclesAutoincremento.java

Relee los apartados 1.4 "Operadores básicos", 1.5.1 "Operadores relacionales" y 1.5.2 "Operadores lógicos" y consulta el apéndice B del libro "Estructuras de datos en Java".

Mira también los ejercicios propuestos en prácticas para seguir trabajando con las sentencias de control de flujo en Java y para ir pensando en la eficiencia de las soluciones (concepto al que dedicaremos el módulo 1).

Del capítulo 2 "Referencias" del libro "Estructuras de datos en Java" de M. A. Weiss, lee los siguientes apartados. Puedes hacerlo tras la clase del 06/02/2013, en la que hablaremos de ese tema y propondremos ejercicios para combinar eso con lo que hemos visto hasta ahora.

• 2.1 "¿Qué es una referencia?"
• 2.2 "Nociones básicas sobre objetos y referencias"
• 2.3 "Cadenas de caracteres"
• 2.4 "Vectores" (exceptuando la Figura 2.4)

Un objetivo de las semanas 3 y 4 es trabajar con vectores y cadenas en combinación con todo lo que hemos visto ya.

Piensa cuál es el resultado de ejecutar cada uno de los siguientes programas. Después de pensar cada uno, compílalo y ejecútalo para verificar si has acertado. En clase se explicarán los conceptos involucrados, complétalos después.

• Ej21_AsignacionesVectores.java
• Ej22_IntercambiaVectores.java
• Ej23_ParametrosVectores.java
• Ej24_ParametrosVectores.java
• Ej25_ParametrosVectores.java
• Ej26_ParametrosVectores.java
• Ej27_ParametrosVectores.java
• Ej28_AsignacionesCadenas.java

Resuelve los siguientes ejercicios de programación, a ser posible entre las semanas 3 y 4 del curso. Tras haberlos intentado, mira las soluciones que se proporcionan y asegúrate de que las entiendes completamente.

Puedes consultar de momento las referencias bibliográficas que quieras para resolverlos. Estas son recomendables: en castellano, "Java: cómo programar" de P. J. Deitel y H. M. Deitel; si entiendes el inglés, también "Big Java: international student version" (4th ed, 2010) de Cay Horstmann. Ten en cuenta que en la evaluación del módulo 0 deberás ser capaz de resolver ejercicios aplicando esos mismos conceptos sin consultar ninguna fuente de información.

1. Escribe en lenguaje Java un método al que podamos pasarle un vector de valores de tipo double para que nos devuelva el promedio de dichos valores.

2. Escribe en lenguaje Java un método al que podamos pasarle un vector de valores de tipo int, posiblemente repetidos, para que nos devuelva un valor booleano que valga true si los valores están ordenados de menor a mayor y false en caso contrario.

3. Escribe en lenguaje Java un método al que podamos pasarle un vector de cadenas para que nos devuelva un valor booleano que valga true si el vector contiene alguna cadena repetida y false en caso contrario.

   Una solución

4. Escribe en lenguaje Java un método al que podamos pasarle un vector de cadenas para que nos devuelva un vector con las cadenas de longitud máxima.

5. Escribe en lenguaje Java un método que reciba un vector de cadenas que están en orden lexicográfico creciente. El método debe modificar el vector para que pasen a estar en orden lexicográfico decreciente.

   Una solución

6. Escribe en lenguaje Java un método que reciba dos cadenas y devuelva true si la primera es sufijo de la segunda y false en caso contrario.

   Hazlo completando el siguiente programa de prueba para que funcione sin errores: EjemploCadenasSufijoTest.java.

   Supón que los únicos métodos que puedes utilizar de la clase String son length y charAt; por tanto no puedes utilizar el método endsWith ni el método substring, aunque en ese programa de prueba se utiliza endsWith para comprobar que tu solución es correcta.

   Una solución

7. Escribe en lenguaje Java un método que reciba una matriz de reales de tamaño m×n, siendo m y n positivos, y devuelva el mínimo de los elementos de la matriz.

   Una solución

8. Escribe en lenguaje Java un método que reciba un vector tridimensional de valores de tipo int. El método debe sustituir todos los valores negativos por su valor absoluto, modificando para ello las componentes del vector si hace falta.

   Una solución

9. Imagina que en un vector de cadenas tienes los títulos de las 1000 películas que hay que ver antes de morir, ordenados de mayor a menor puntuación según cierto criterio que no nos interesa ahora. En otro vector de cadenas tienes los títulos de las mejores películas infantiles de todos los tiempos. Escribe en lenguaje Java un método al que puedas pasarle ambos vectores y que devuelva true si hay algún título que esté en ambos vectores (exactamente igual, con los mismos caracteres) y false en caso contrario.

   Una solución

10. Añade a la solución del ejercicio anterior un método al que puedas pasarle ambos vectores para obtener como resultado un nuevo vector de cadenas con los títulos de las mejores películas infantiles de todos los tiempos que además están entre las que hay que ver antes de morir, en el mismo orden en que aparecen en el vector de películas infantiles.

    Una solución

11. Resuelve el ejercicio de este control de evaluación continua de prácticas del curso 2010/2011.

    Una solución (verifica si la tuya obtiene el mismo resultado con las pruebas que se incluyen ahí)

12. Resuelve el ejercicio 2 de este control de evaluación continua de teoría del curso 2010/2011.

    Una solución

13. Resuelve el ejercicio 2 de este otro control de evaluación continua de teoría del curso 2010/2011.

    Una solución

14. Resuelve el ejercicio de este control de evaluación continua de prácticas del curso 2011/2012.

15. Resuelve el ejercicio 2 de este control de evaluación continua de teoría del curso 2011/2012.

Del capítulo 5 "Análisis de algoritmos" del libro "Estructuras de datos en Java" de M. A. Weiss:

• Preámbulo
• 5.1 "¿Qué es el análisis de algoritmos?"
• 5.3 "El problema de la subsecuencia de suma máxima"
• 5.4 "Reglas generales para la notación O"
• 5.5 "Logaritmos"
• 5.6 "Problema de la búsqueda estática", incluyendo solamente los subapartados:
  • 5.6.1 "Búsqueda secuencial"
  • 5.6.2 "Búsqueda binaria"
  El apartado 5.6.3 "Búsqueda interpolada" es opcional, míralo solo si te interesa.
• 5.7 "Comprobar el análisis de un algoritmo"
• 5.8 "Limitaciones del análisis O"

Del capítulo 15 "Recursividad" del libro "Java: cómo programar" de P. J. Deitel y H. M. Deitel:

• 15.1 "Introducción"
• 15.2 "Conceptos de recursividad"
• 15.3 "Ejemplo de uso de recursividad: factoriales"
• 15.4 "Ejemplo de uso de recursividad: serie de Fibonacci"
• 15.5 "La recursividad y la pila de llamadas a métodos"
• 15.6 "Comparación entre recursividad e iteración"
• 15.7 "Las torres de Hanoi"

Del capítulo 7 "Recursión" del libro "Estructuras de datos en Java" de M. A. Weiss:

• Preámbulo
• 7.1 "¿Qué es la recursión?"
• 7.2 "Fundamentos: demostraciones por inducción matemática"
• 7.3 "Recursión básica".
• 7.5 "Algoritmos divide y vencerás", incluyendo los subapartados:
  • 7.5.1 "El problema de la subsecuencia de suma máxima"
  • 7.5.2 "Análisis de un algoritmo divide y vencerás sencillo"
• "Errores comunes" en la página 206.

Del capítulo 8 "Algoritmos de ordenación" del libro "Estructuras de datos en Java" de M. A. Weiss::

• Preámbulo
• 8.1 "¿Por qué es importante la ordenación?"
• 8.5 "Mergesort"

Opcionalmente, lee también el apartado 7.6 "Programación dinámica" del libro de M. A. Weiss. Es una introducción a otra estrategia algorítmica que estudiarás en profundidad en tercer curso en la asignatura "Algorítmica". En ese libro se ilustra con un ejemplo inicial sencillo, adecuado a lo que estás aprendiendo este curso.

• Animación de algoritmos de ordenación (David R. Martin)

• Algoritmos de ordenación (Wikipedia)

• Selection sort (Wikipedia)

• Insertion sort (Wikipedia)

• Merge sort (Lucas J. Barbosa)

• Cómo suenan los algoritmos de ordenación (Andrzej Rutkowski)

• Musical Insertion sort (guitar) (Ryan Compton)

• La Torre de Hanoi (Rodolfo Valeiras)

Resuelve los siguientes ejercicios. Los 6 primeros son opcionales, para quien esté interesado en ellos y pueda dedicar más tiempo a este módulo.

1. [!] Piensa cómo depende de n el tiempo de ejecución necesario para calcular el siguiente sumatorio. ¿Sabrías calcularlo en tiempo O(1)?

   $$\sum _{i=1}^{n}i=1+2+\dots +n$$

2. [!] Averigua cómo calcular en tiempo O(1) estos sumatorios, que no debes confundir entre sí. Demuestra por inducción el resultado.

   $$\sum _{i=1}^n{i}^2=1^2+2^2+\dots +n^2$$ $$\sum _{i=0}^n{2}^i=2^0+2^1+\dots +2^n$$

3. ¿Cuánto vale la suma de los n primeros enteros positivos pares? ¿Y la de los n primeros enteros positivos impares?

4. [!] Demuestra que $\sum _{i=1}^n(2i-1)=n^2$

5. [!] Calcula el valor exacto de $\sum _{i=1}^{n-1}\sum _{j=\mathrm{i}}^{n-1}1$

6. [!] Calcula el valor exacto de $\sum _{i=0}^{n-1}\sum _{j=\mathrm{i}}^{n-1}\sum _{k=\mathrm{j}}^{n-1}1$

7. Revisa las soluciones del ejercicio 5 del módulo 0 de prácticas (semana 3) y analiza el tiempo de ejecución de cada una para determinar si es lineal o cuadrático.

8. Revisa tus soluciones del ejercicio 6 del módulo 0 de prácticas (semana 3) y analiza el tiempo de ejecución de cada una para determinar si es lineal o cuadrático. Mejora tu solución, si hace falta, para que su tiempo de ejecución sea lineal.

9. [!] ¿Qué problema hemos visto en el curso que se puede resolver con un algoritmo cuyo tiempo de ejecución es O($\sqrt{n}$) en el peor de los casos y O(1) en el mejor de los casos?

10. [!] Si tuvieses que elegir entre dos algoritmos que resuelven un mismo problema, el tiempo de ejecución del primero fuese O($\sqrt{n}$) y el del segundo O(log n), ¿cuál elegirías?

11. Tenemos un conjunto de n valores de tipo real almacenados en un vector y queremos encontrar, entre todos los posibles pares de valores de ese conjunto, uno tal que la diferencia entre los dos valores del par sea mínima. Piensa cómo hacerlo si el vector no está ordenado, cómo hacerlo si está ordenado, y cuál es el coste computacional de cada algoritmo. Piensa si sería conveniente ordenar primero el vector para resolver ese problema cuando el vector no está ordenado previamente.

12. Repite el ejercicio anterior suponiendo ahora que queremos encontrar, entre todos los posibles pares de valores de ese conjunto, uno tal que la diferencia entre los dos valores del par sea máxima en vez de mínima.

13. ¿Cuál es el tiempo de ejecución en el mejor caso del algoritmo de detección de duplicados de la Figura 8.1, página 214, del libro de M. A. Weiss? ¿Y en el peor caso? Demuéstralo. ¿Sabrías resolver ese problema más eficientemente? Piénsalo y después busca la solución en la misma página.

14. Tenemos dos vectores v y w que no sabemos si están ordenados. Ambos son de talla n. Queremos saber si contienen los mismos elementos. Propón una forma de averiguarlo que cueste tiempo O(n log n) en el peor de los casos.

15. Escribe en lenguaje Java un método para averiguar si una cadena de caracteres que están ordenados alfabéticamente contiene un determinado carácter, empleando el algoritmo de búsqueda binaria.

    Considera que la cadena puede estar vacía.

16. Revisa las soluciones de los ejercicios 9 y 10 del módulo 0 y analiza su coste computacional en función de la talla de los vectores de títulos de películas.

    Imagina ahora que el vector de títulos de películas que hay que ver antes de morir estuviese ordenado lexicográficamente y el de películas infantiles no. Diseña una solución más eficiente para ese caso y analiza su coste computacional.

    Finalmente, imagina que estuviesen ordenados lexicográficamente los dos vectores. Diseña una solución más eficiente para ese caso y analiza su coste computacional.

17. Supongamos que en un vector de cadenas tenemos los DNI de los usuarios de una biblioteca y en otro vector tenemos los DNI de los usuarios que tienen algún libro prestado. Queremos obtener a partir de ellos un vector con los DNI de los usuarios que no tienen ningún libro prestado. Propón un algoritmo para resolver el problema y analiza su coste computacional en cada uno de los casos siguientes: (a) si ninguno de los dos vectores está ordenado; (b) si uno de ellos está ordenado y el otro no; (c) si ambos están ordenados.

    Teniendo en cuenta todo ello, ¿crees que vale la pena invertir tiempo en ordenar los vectores inicialmente para resolver el problema?

18. Revisa este ejercicio sobre costes asintóticos de bucles y esta solución (se explicará en clase).

19. Imagina que tienes n monedas, siendo n potencia de 2, y sabes que una de ellas es falsa y pesa menos que las demás. Para encontrarla dispones de una balanza de dos platillos, en los que puedes poner tantas monedas como quieras. Diseña un procedimiento que te permita encontrar la moneda falsa realizando O(log n) pesadas. Después modifícalo, si hace falta, para evitar la necesidad de que n sea potencia de 2.

20. Imagina que tienes que encontrar un número secreto n que es entero positivo y no sabes en qué rango se encuentra. Cada vez que hagas un intento fallido te dirán si el número secreto es mayor o menor que el que has propuesto. Propón un algoritmo para encontrar el número secreto realizando O(log n) intentos.

21. Tenemos tres vectores de tamaño n cada uno de los cuales está ordenado de mayor a menor. A partir de ellos queremos obtener un vector de tamaño 3n que contenga todos los elementos de los tres vectores, ordenados también de mayor a menor. Piensa cómo hacerlo empleando como subrutina el algoritmo para mezclar dos vectores del ejercicio 2 del módulo 1 de prácticas (semana 5) y piensa cómo depende de n el tiempo de ejecución de la solución.

22. Tenemos una matriz bidimensional de tamaño m×n en la que están ordenados de mayor a menor solamente los elementos dentro de cada una de las filas, no están ordenados entre sí los elementos de filas diferentes. Queremos construir un vector unidimensional que contenga todos los valores de la matriz ordenados de mayor a menor. Diseña un algoritmo para hacerlo, empleando como subrutina el algoritmo para mezclar dos vectores del ejercicio 2 del módulo 1 de prácticas (semana 5) para ir mezclando dos vectores cada vez hasta tener el resultado. Intenta que el tiempo de ejecución de tu solución no crezca de forma cuadrática al crecer la cantidad de filas.

23. Tenemos dos vectores de enteros v y w. Sabemos que en v y en w no hay elementos duplicados. No sabemos si v y w están ordenados o no. Queremos comprobar si v coincide con el resultado de ordenar w. Piensa cómo resolver el problema eficientemente sin modificar v ni w con la restricción de que el coste de la memoria adicional que necesites debe ser O(1). Analiza el tiempo de ejecución de tu solución en el peor caso y exprésalo empleando notacion O.

24. Diseña un algorimo para ordenar un vector en tiempo lineal que sea aplicable cuando todos los elementos del vector sean valores enteros positivos y menores o iguales que 1000.

25. Observa el método invertirCadena en esta solución del ejercicio 2 de esta prueba de evaluación del módulo 0. ¿Cómo crece el tiempo de ejecución de ese método al crecer la talla de la cadena a invertir, de forma lineal o de forma cuadrática? ¿Por qué? Escribe una solución más eficiente utilizando los métodos disponibles en la clase String.

26. Escribe en lenguaje Java un método que reciba como argumentos un vector de enteros que están ordenados de mayor a menor, un valor entero a y otro valor entero b. El método debe devolver la cantidad de valores x en el vector que cumplen a ≤ x ≤ b. Tanto a como b pueden no encontrarse en el vector o pueden aparecer más de una vez. Considerando la talla del vector como talla del problema, el tiempo de ejecución de tu solución debe ser logarítmico.

27. Escribe en lenguaje Java un método que reciba como argumentos un vector de enteros que están ordenados de mayor a menor, un valor entero a y otro valor entero b. El método debe devolver un nuevo vector que contenga, en el mismo orden, solamente los elementos x del vector recibido que cumplen a ≤ x ≤ b. Tanto a como b pueden no encontrarse en el vector o pueden aparecer más de una vez. El tiempo de ejecución de tu solución debe ser O(m + log n) siendo n la talla del vector recibido y m la talla del vector devuelto.

28. ¿Cuál es el coste temporal del algoritmo recursivo para sumar los n primeros enteros que se emplea en la figura 7.1 (página 169) del libro de M. A. Weiss? ¿Y el coste espacial?

29. ¿Cuál es el coste temporal del algoritmo recursivo para imprimir un número en base 10 que se emplea en la figura 7.2 (página 171) del libro de M. A. Weiss? ¿Y el coste espacial?

30. Este programa FibonacciRecursivo.java le pide al usuario un dato n y escribe los n primeros números de la sucesión de Fibonacci, pero es extremadamente ineficiente. Pruébalo con n=50 y observa cómo se va ralentizando la salida. Escribe un programa que produzca en tiempo O(n) la misma salida. Observa que eso no se consigue llamando n veces a un método que calcule el k-ésimo número de Fibonacci en tiempo O(k), piensa cuál sería el tiempo de ejecución de esas n llamadas.

31. Resuelve todos los ejercicios de este control de evaluación continua de teoría del curso 2010/2011. Puedes encontrar el programa del ejercicio 1 aquí y el del ejercicio 2, incluyendo una posible solución del primer apartado, aquí. Piensa también cómo mejorar la eficiencia de esa solución.

32. Resuelve todos los ejercicios de este otro control de evaluación continua de teoría del curso 2010/2011. Puedes encontrar los programas aquí.

33. Resuelve todos los ejercicios de este control de evaluación continua de teoría del curso 2011/2012. Puedes encontrar los programas aquí.

34. Resuelve el ejercicio 2 de este examen final de mayo 2011.

35. Resuelve el ejercicio 2 de este examen final de julio 2011.

36. Resuelve el ejercicio 2 de este examen final de mayo 2012.

37. Resuelve el ejercicio 2 de este examen final de julio 2012.

Del capítulo 3 "Objetos y clases" del libro "Estructuras de datos en Java" de M. A. Weiss:

• 3.1 "¿Qué es la programación orientada a objetos?"
• 3.2 "Un ejemplo sencillo"
• 3.4 "Métodos básicos"
  • 3.4.1 "Constructores"
  • 3.4.2 "Métodos modificadores y de acceso"
  • 3.4.3 "Salida y toString"
  • 3.4.4 "equals"
  • 3.4.5 "Métodos static"
  • 3.4.6 "main"
• 3.5 "Paquetes"
  • 3.5.1 "La directiva import"
  • 3.5.2 "La instrucción package"
  • 3.5.3 "La variable de entorno CLASSPATH"
  • 3.5.4 "Reglas de visibilidad amistosa dentro de un paquete"
  • 3.5.5 "Compilación separada"
• 3.6 "Construcciones adicionales"
  • 3.6.1 "La referencia this"
  • 3.6.2 "La abreviatura this para constructures"
  • 3.6.3 "El operador instanceof"
  • 3.6.4 "Atributos estáticos"
  • 3.6.5 "Inicializadores estáticos"
• Resumen
• Errores comunes

El apartado 3.3 "Javadoc" lo consideraremos opcional, miralo si te interesa.

Del libro "Java: cómo programar (novena edición, 2012)" de P. J. Deitel y H. M. Deitel (del que hemos recibido nuevos ejemplares en la biblioteca):

• Del capítulo 3 "Introducción a las clases, objetos, métodos y cadenas":

  • 1.1 "Introducción"
  • 3.2 "Declaración de una clase con un método e instanciamiento de un objeto de una clase"
  • 3.3 "Declaración de un método con un parámetro"
  • 3.4 "Variables de instancia, métodos establecer y métodos obtener"
  • 3.5 "Comparación entre tipos primitivos y tipos por referencia"
  • 3.6 "Inicialización de objetos mediante ocnstructores"

• Del capítulo 8 "Clases y objetos: un análisis más detallado":

  • 8.1 "Introducción"
  • 8.2 "Caso de estudio de la clase Tiempo"
  • 8.3 "Control de acceso a los miembros"
  • 8.4 "Referencias a los miembros del objeto actual mediante this"
  • 8.5 "Caso de estudio de la clase Tiempo: constructores sobrecargados"
  • 8.6 "Constructores predeterminados y sin argumentos"
  • 8.7 "Observaciones acerca de los métodos Establecer y Obtener"
  • 8.8 "Composición"
  • 8.9 "Enumeraciones"
  • 8.10 "Recolección de basura y el método finalize"
  • 8.11 "Miembros de clase static"
  • 8.13 "Variables de instancia final"
  • 8.14 "Caso de estudio de la clase Tiempo: creación de paquetes"
  • 8.15 "Acceso a paquetes"
  • 8.17 "Conclusión"

  Los siguientes apartados los consideraremos opcionales, míralos si te interesan: 8.12 "Declaración static import y 8.16 "Caso de estudio de GUI y gráficos: uso de objetos con gráficos". Podrás estudiar eso en la asignatura "Programación Avanzada" de segundo curso.

• Del capítulo 7 "Arreglos y objetos ArrayList":

  • 7.4 "Ejemplos acerca del uso de los arreglos"

  Ahí se introduce el tema de las excepciones por primera vez en el libro.

• Del capítulo 11 "Manejo de excepciones: un análisis más detallado":

  • 11.2 "Ejemplo: división entre cero sin manejo de excepciones"
  • 11.3 "Ejemplo: manejo de excepciones tipo ArithmeticException e InputMismatchException"

  El resto del capítulo 11 lo consideraremos opcional, míralo si te interesa. Esto lo complementaremos con ejemplos de declaración de nuevos tipo de excepciones en clase de teoría y prácticas y en el módulo siguiente (en el libro lo hace en el capítulo 22, dedicado a la implementación de estructuras de datos).

En la biblioteca puedes encontrar también otras ediciones, aunque hay diferencias entre ellas puedes utilizarlas. Por ejemplo, tienes la novena edición en inglés y la séptima edición en castellano.

Tienes también la séptima edición en inglés aqui entrando como estudiante con login alumno10 y password cyberAlum10 (proporcionados por la editorial Pearson aquí).

• "Programación orientada a objetos" (Wikipedia)

• Principio de "Ocultación de información" (Wikipedia)

• "Orientación a Objetos, una técnica para mejorar la calidad del software" (Begoña Moros, Universidad de Murcia)

• "Java is Pass-by-Value, Dammit!" (Scott Stanchfield)

• "Java Platform, Standard Edition 7 API Specification"

• "Desarrollo guiado por pruebas" (Wikipedia)

Resuelve los siguientes ejercicios.

1. Mira y prueba este ejemplo explicado en clase: Punto.java y PruebaPunto.java. Debes entender todo lo que sucede.

2. Haz una nueva implementación de esta clase Hora.java de modo que la interfaz pública de la clase no cambie pero la representación interna de los datos sea otra: sustituye los dos atributos hora y minuto por un solo atributo que contenga la cantidad de minutos transcurridos desde las 00:00.

   Por ejemplo, al ejecutar este programa PruebaHora.java, sin modificar nada en él, se debe seguir obteniendo esta salida. Lo mismo debe suceder con tus programas de prueba.

3. Mira detenidamente este ejemplo presentado en clase (en los dos primeros ficheros se ha añadido solamente lo necesario para que la clase Punto forme parte del paquete FigurasGeometricas):

   • FigurasGeometricas / Punto.java
   • PruebaPunto.java
   • FigurasGeometricas / Circulo.java
   • PruebaCirculo.java

   Crea el directorio FigurasGeometricas para las clases de ese paquete. Prueba los programas, verifica que entiendes todo lo que sucede, y pregunta al profesor en tutorías o en clase si te quedan dudas. Resuelve el ejercicio que verás propuesto. Ten siempre presente esa diferencia de comportamiento que provoca la diferencia entre tipos primitivos y referencias.

4. Piensa cuál de estas versiones preferirías como constructor copia de la clase Circulo anterior, la que hace una copia superficial o alguna de las que hacen una copia en profundidad:

   
   public Circulo(Circulo otroCirculo) {
      centro = otroCirculo.centro;
      radio = otroCirculo.radio;
   }

   public Circulo(Circulo otroCirculo) {
      centro = new Punto(otroCirculo.centro);
      radio = otroCirculo.radio;
   }

   public Circulo(Circulo otroCirculo) {
      centro = otroCirculo.centro.crearCopia();
      radio = otroCirculo.radio;
   }

5. Mira y prueba este EjemploCloneSuperficial.java y asegúrate de que lo entiende completamente.

6. Mira y prueba este EjemploDevolucionReferencia.java y asegúrate de que lo entiende completamente.

7. Intenta entender el mensaje principal de esta página: "Java is Pass-by-Value, Dammit!".

   ¿Cómo implementarías en Java un método para intercambiar dos puntos?

   ¿Cómo implementarías un método al que se le pudiese pasar un punto p y un vector de puntos v y que devolviese tanto el punto de v más próximo a p como su distancia a p?

   ¿Qué opinas de que un lenguaje de programación, como Java, no permita el paso de parámetros por referencia, ni con tipos primitivos ni con lo que se llaman "referencias"?

8. Mira detenidamente, prueba y verifica que entiendes también todo lo que sucede en este otro ejemplo, y añade las pruebas adicionales que consideres conveniente para terminar de entender los conceptos involucrados:

   • FigurasGeometricas / Segmento.java
   • PruebaSegmento.java

9. Añade al paquete FigurasGeometricas la clase Triangulo. Internamente un triángulo está representado por un vector de tres puntos. Incluye en la clase métodos públicos que permitan construir un triángulo a partir de tres puntos, calcular el perímetro del triángulo, mover el triángulo sumando a cada vértice los desplazamientos dados (sin crear para ello puntos nuevos), comparar dos triángulos para saber si son iguales geométricamente, y obtener una copia en profundidad del triángulo. Ten en cuenta que dos triángulos son iguales geométricamente si tienen los mismos vértices aunque no los tengan en el mismo orden. Si al constructor del triángulo no le pasan tres puntos diferentes, en este ejercicio puedes simplemente mostrar un mensaje de error y continuar como si fuese un triángulo normal. Escribe también una batería de pruebas de todos los métodos.

   Después mira esta implementación de la clase Triangulo, que es una posible solución del ejercicio propuesto añadiendo un primer ejemplo de tratamiento de errores mediante excepciones. En la sesión de teoría del 10/04 se explicará eso, en la sesión de prácticas del 10/04 tendrás que hacer un ejercicio sobre eso y en el módulo de estructuras de datos veremos más ejemplos con excepciones.

   • FigurasGeometricas / Excepciones / TrianguloInvalido.java
   • FigurasGeometricas / Triangulo.java
   • PruebaTriangulo.java

10. Utilizando cualquiera de las versiones de la clase Fecha que se te propone implementar en la semana 9 de prácticas, escribe un programa que le proponga al usuario adivinar la fecha de tu cumpleaños y al final le diga cuántos intentos ha necesitado. Cada vez que el usuario se equivoque, el programa debe ayudarle diciéndole si la fecha de tu cumpleaños es anterior o posterior a la que ha introducido y también debe decirle si ha hecho un intento absurdo.

    Ayuda: Utiliza la variable mínimaFechaPosterior para almacenar la menor de las fechas posteriores a la de tu cumpleaños introducidas hasta el momento por el usuario, y la variable máximaFechaAnterior para almacenar la mayor de las fechas anteriores a la de tu cumpleaños que ha introducido el usuario. Cuando éste introduce una fecha posterior o igual a mínimaFechaPosterior el programa debe indicarle que ese intento no tiene sentido puesto que ya le había dicho que lo que busca es anterior a mínimaFechaPosterior. El comportamiento debe ser análogo si el usuario introduce una fecha anterior o igual a máximaFechaAnterior.

11. Resuelve el ejercicio 1 de este control de evaluación continua de teoría del curso 2010/2011. Ejecuta los programas para comprobar tu solución y asegúrate de que entiendes lo que sucede en cada apartado.

12. Resuelve el ejercicio 2 de este control de evaluación continua de teoría del curso 2010/2011. Elige la solución que consideres más eficiente.

13. Resuelve el ejercicio 1 de este otro control de evaluación continua de teoría del curso 2010/2011. Ejecuta los programas para comprobar tu solución y asegúrate de que entiendes lo que sucede en cada apartado.

14. Resuelve el ejercicio 2 de este otro control de evaluación continua de teoría del curso 2010/2011. Elige la solución que consideres más eficiente.

15. Resuelve el ejercicio 1 de este examen de mayo 2011. Ejecuta el programa para comprobar tu solución y asegúrate de que entiendes lo que sucede.

16. Resuelve el ejercicio 3 de este examen de mayo 2011.

17. Resuelve el apartado (b) del ejercicio 1 de este examen de julio 2011. Ejecuta PruebaContador.java para comprobar tu solución y asegúrate de que entiendes lo que sucede.

18. Resuelve el ejercicio 3 de este examen de julio 2011.

19. Resuelve este control de evaluación continua de prácticas del curso 2010/2011.

20. Resuelve este otro control de evaluación continua de prácticas del curso 2010/2011.

Del libro "Java: cómo programar" (séptima edición, 2008) de P. J. Deitel y H. M. Deitel:

• Del capítulo 17 "Estructuras de datos":

  • 17.2 "Clases de envoltura de tipos para los tipos primitivos"
  • 17.3 "Autoboxing y autounboxing"

• Del capítulo 19 "Colecciones":

  • 19.1 "Introducción"
  • 19.2 "Generalidades acerca de las colecciones"
  • 19.5.1 "ArrayList e Iterator"
  • 19.5.2 "LinkedList"

La novena edición en castellano sorprendentemente no incluye la traducción del capítulo 20 ("Generic Collections") de la novena edición en inglés, aunque en el libro dan acceso a él en inglés en Internet. También puedes consultar las otras ediciones comentadas en el módulo 2.

Del libro "Estructuras de datos en Java" de M. A. Weiss:

• Del capítulo 4 "Herencia":

  • 4.5.1 "Especificación de una interfaz"
  • 4.5.2 "Implementación de una interfaz"

  Aunque ese tema será temario de segundo curso, esos apartados te pueden ayudar a entender lo que hace Weiss con los interfaces, que es lo mismo que haremos en este curso.

• Del capítulo 6 "Estructuras de datos":

  • Preámbulo
  • 6.1 "¿Por qué necesitamos estructuras de datos?"
  • 6.2 "Las pilas"
  • 6.3 "Las colas"

• Del capítulo 15 "Pilas y colas":

  • 15.1 "Implementación dinámica de vectores"
  • 15.2 "Implementaciones con listas enlazadas"
  • 15.3 "Comparación de los dos métodos"

  Puedes excluir el apartado 15.4, requiere conocer conceptos sobre la herencia que estudiarás en segundo curso. También puedes excluir los ejercicios del libro, te propondremos otros.

Para saber más: Si quieres ir más alla de los contenidos de Programación II e ir viendo estructuras de datos que se estudian en segundo curso (árboles binarios de búsqueda, tablas hash, etc.), los capitulos 17 al 19 del libro de M. A. Weiss son muy recomendables (en segundo curso te recomendarán otros libros).

• Tipo de dato abstracto (Wikipedia)

• Stack (Wikipedia)

• Queue (Wikipedia)

• Java Platform, Standard Edition 7 API Specification

• Java gotchas (The Open Web Application Security Project)

Resuelve los siguientes ejercicios.

1. Mira y prueba las cuatro versiones de este EjemploRecorridoTren introducido en clase y asegúrate de que entiendes lo que se hace en cada versión.

   Busca información sobre los métodos que se emplean ahí en la documentación de la clase ArrayList y en la documentación de la clase LinkedList de la especificación de la API de Java Standard Edition 7. En esa documentación puedes encontrar la lista completa de métodos disponibles en cada una de ellas, no es necesario que los conozcas todos pero sí que sepas consultarla para resolver los ejercicios de prácticas de la semana 13.

2. Mira este EjemploCompararLinkedList.java explicado en clase, que ilustra tres formas diferentes de averiguar si dos listas tienen los mismos elementos en el mismo orden, y observa cuál es el método más eficiente. En ese mismo ejemplo puedes ver también cómo crear listas de enteros utilizando la clase Integer, que es una de las denominadas clases de envoltura.

3. Mira y prueba también este EjemploCuidadoIntegerEquals.java para evitar cometer el error que se ilustra ahí: observa que han conseguido que una comparación mal hecha pueda funcionar bien si se prueba con enteros entre -128 y 127 y fallar más adelante al utilizar otros números ! Increíble pero cierto. Piensa si eso te parece una característica buena en un lenguaje de programación, teniendo en cuenta cómo aumenta la probabilidad de que las pruebas de los programas escritos en ese lenguaje no detecten ese tipo de errores.

4. Estudia, prueba y compara estas dos implementaciones del Tipo Abstracto de Datos Pila explicadas en clase. En ellas se utilizan las excepciones que puedes encontrar en EstructurasDeDatos / Excepciones.

   • EstructurasDeDatos / PilaVersion1.java (mediante vectores)
   • PruebaPilaVersion1.java
   • EstructurasDeDatos / PilaVersion2.java (mediante nodos)
   • PruebaPilaVersion2.java

   Opcionalmente (si estás convencido de que ya sabes hacerlo, sáltate este ejercicio) modifica la implementación mediante vectores anterior para duplicar la capacidad de la pila cuando se llena en vez de lanzar una excepción, y para empezar con una capacidad inicial de 10 si el usuario no indica otra.

5. Resuelve todos los ejercicios de este control de evaluación continua de teoría del curso 2011/2012.

   Después mira esta solución.

6. Realiza una implementación mediante vectores del Tipo Abstracto de Datos Cola que permita almacenar datos de tipo entero. Tu implementación debe tener los métodos de la interfaz Cola del apartado 6.3 del libro de M. A. Weiss, cambiando Object por int. Piensa cómo conseguir que tanto la operación de insertar un nuevo elemento como la de extraer el primero se ejecuten en tiempo O(1).

   Después compara tu solución con la que puedes encontrar el el apartado 15.1.2 del libro de M. A. Weiss (donde él pone Object imagina que pusiese int).

7. Revisa este otro ejemplo de clase y verifica que los entiendes completamente:

   • EstructurasDeDatos / ColeccionDeEnteros.java
   • EstructurasDeDatos / ColeccionDeEnterosConRepetidos.java
   • PruebaColeccionDeEnterosConRepetidos.java

8. Modifica el método toString del ejemplo anterior para que se ejecute en tiempo O(n). Puedes utilizar para ello la clase StringBuilder.

9. Tras completar la implementación del TAD Cola que se te propone como ejercicio 5 en las prácticas de la semana 14, resuelve estos ejercicios:

   1. Este EjemploErroresNodos.java contiene ejemplos de errores cometidos por estudiantes en la implementación de la clase ColaEnlazada. ¿Cuáles son los errores? ¿Cómo los arreglarías?

   2. Añade a tu clase ColaEnlazada un método boolean mismosElementos(ColaEnlazada) que permita comprobar mediante cola1.mismosElementos(cola2) si cola1 contiene los mismos datos y en las mismas cantidades que cola2, ni más ni menos, en el mismo o en diferente orden.

   3. Añade a tu clase ColaEnlazada un método boolean comparar(ColaEnlazada, ColaEnlazada) que permita comprobar mediante cola1.comparar(cola2, cola3) si cola1 contiene los mismos datos y en el mismo orden que cola2, ni más ni menos, y también contiene los mismos datos y en el mismo orden que cola3, ni más ni menos.

   4. Control de evaluación continua de teoría del curso 2010/2011

   5. Control de evaluación continua de prácticas del curso 2010/2011

10. Realiza una implementación del TAD Cola Doble que tenga al menos las siguientes operaciones básicas:

    1. void insertarPorDelante(int dato)
    2. void insertarPorDetras(int dato)
    3. void eliminarPorDelante()
    4. void eliminarPorDetras()
    5. int consultarPrimero()
    6. int consultarUltimo()

11. Realiza una implementación del TAD Cola de Prioridad que tenga al menos las siguientes operaciones básicas:

    1. void insertar(int prioridad)
    2. void eliminarMínimo()
    3. int consultarMínimo()

12. Realiza una implementación del TAD Cola de Prioridad de Doble Fin que tenga al menos las siguientes operaciones básicas:

    1. void insertar(int prioridad)
    2. void eliminarMínimo()
    3. int consultarMínimo()
    4. void eliminarMáximo()
    5. int consultarMáximo()

13. Resuelve en papel, sin emplear más de una hora, el ejercicio 4 de este examen de mayo 2011.

14. Resuelve en papel, sin emplear más de una hora, el ejercicio 4 de este examen de julio 2011.

15. Resuelve en papel, sin emplear más de una hora, el ejercicio 4 de este examen de mayo 2012.

16. Resuelve en papel, sin emplear más de una hora, el ejercicio 4 de este examen de julio 2012.

17. Resuelve los dos ejercicios de este control de evaluación continua de prácticas del curso 2011/2012

    Después mira esta solución.