Notas
Presentación
Esquema
1
Fundamentos de vectores y matrices
  • Vectores
2
¿Qué es un vector?
  • Un vector de datos es un conjunto de variables adyacentes de un tipo determinado.
  • Los vectores facilitan la administración de conjuntos de datos relacionados, ya que no se tienen que manipular individualmente.
3
¿Cuál es la estructura básica de un vector?
  • Un vector se compone de variables o celdas consecutivas que pueden almacenar valores de un tipo específico. Cada celda puede almacenar un valor y a cada una se le asocia un entero conocido como “índice” que es la posición que ocupa dentro del vector. Todos los valores almacenados en el vector son del mismo tipo.
4
¿Cómo se declaran e inicializan los vectores?
  • Al igual que una variable simple un vector debe declararse primero y luego inicializarse.
  • Posteriormente se pueden guardar y recuperar valores en celdas independientes accediendo a ellas mediante el índice correspondiente.
  • También se puede “recorrer” el vector incrementando o decrementando el valor de una variable entera utilizada como índice.
5
¿ Cómo se codifica un vector en Java?
  • La declaración de un vector se puede hacer de la siguiente manera:


  • tipo v []; // se declara v que es una referencia a un vector
  • v = new tipo [cantidadDeCeldas]; // se inicializa el vector


  • También se puede realizar con una sola instrucción:
  • tipo v [] = new tipo [cantidadDeCeldas];


  • El tamaño de un vector puede ser un valor literal o una variable entera:
    • int c[] = new int [variable];
    • int c[] = new int [5];

6
¿Cómo se inicializan los vectores en Java?
  • Un vector puede ser declarado e inicializado en la misma instrucción:
  • int c[] = {20, 45, 32, 5, 1};
  • Luego de inicializar el vector, su tamaño queda almacenado dentro del vector en una variable pública llamada length. Ejemplo:
  • Si c = new int [5]; entonces c.length vale  5.
7
¿Cómo se pueden guardar y recuperar valores en celdas de un vector?
  • Para asignar un valor x a la posición i del vector indicando el índice de la celda deseada. Ejemplo:
  • v[i] = x;
  • Para asignar a x el valor almacenado en la posición i del vector se hace lo mismo. Ejemplo:
  • x = v[i]; //Denominado como “campo v sub i”.
  • // i se conoce como índice.
8
¿Cómo se puede recorrer un vector?
  • Un vector puede ser fácilmente recorrido por medio de un ciclo for.
  • Se entiende por recorrido a una secuencia de accesos consecutivos a las celdas del vector.
  • El recorrido se logra variando el valor del índice de acceso a las celdas del vector.
9
EJEMPLO 1 – Declaración, inicialización y recorrido de vectores
  • Ir al ejemplo
10
EJERCICIO 1 – Declaración, inicialización y recorrido de vectores
  • Ir al ejercicio
11
¿Qué sucede en la memoria al utilizar un vector de enteros en Java?
  • int vector []; // El vector es una referencia a un vector
  • vector = new int[5]; // Se crea el vector de 5 celdas (0-4)
  • int i = 3; // i se usará para indicar el índice
  • vector[i] = 8; // Se asigna a la celda 3 el valor 8
12
Ejemplo de recorrido sobre un vector de enteros en Java
13
¿Qué sucede si se trata de acceder al valor de una posición inexistente?
14
¿Qué sucede si se trata de acceder al valor de una posición inexistente? (continuación)
  • Si se trata de acceder a una posición no existente se producirá una excepción con el mensaje: ArrayIndexOutOfBoundsException
  • Significa que se está tratando de acceder a algo que está fuera de los límites establecidos para el vector.
  • Para que un programa no se caiga debido a esto es conveniente utilizar manejo de excepciones (try { } catch(){ }).
15
¿Cómo pasar un vector como parámetro en un método utilizando Java ?
  • El nombre de un vector es una referencia que contiene la dirección inicial donde se ubican los datos asociados al mismo.
  • Los cambios efectuados a un vector dentro de un método que lo recibe como parámetro se mantienen aún después de finalizado el método.
  • Al pasar un vector como parámetro a un método solo se copia la dirección del vector hacia la referencia que existen dentro del método  (no se genera una copia de los datos almacenados en las celdas del vector).  A partir de este punto tanto la referencia utilizada para ejecutar el llamado (externa al método) y el parámetro que recibe la referencia, “apuntan” al inicio del mismo grupo de datos en memoria.
16
EJEMPLO 2 – Demostración del pase de vectores como parámetro
  • Ir al ejemplo
17
EJERCICIO 2 – Utilización de pase de vectores como parámetro
  • Ir al ejercicio
18
Visualización del pase de un vector como parámetro utilizando Java
19
Visualización del pase de un vector como parámetro utilizando Java (continuación)
20
¿Cómo crear un vector de objetos en Java?
  • Cada celda de un vector es equivalente a una variable por lo que se puede declarar un vector de referencias a objetos.
  • En Java las referencias a objetos van a ser automáticamente inicializadas a null al crear el vector.
  • Posteriormente hay que crear cada objeto independientemente y asignarlo a la celda deseada.
21
Visualización de un vector de objetos en Java
22
EJEMPLO 3 – Demostración del uso de vectores y objetos
  • Ir al ejemplo
23
EJERCICIO 3 – Utilización de vectores y objetos
  • Ir al ejercicio
24
¿Para qué sirven los vectores en el ciclo de resolución de problemas?
  • Los vectores son de las estructuras más importantes en la mayoría de los lenguajes.
  • Normalmente sirven para almacenar, procesar, buscar y recuperar valores específicos dentro de un grupo de datos.
25
¿Cuáles son los principales usos que se le dan a los vectores?
  • Entre los usos comunes que se les pueden dar son:
  • Calcular valores nuevos a partir de secuencias de valores leídos sin perder el detalle de los mismos.
  • Para ordenar una serie de valores entre sí.
  • Para buscar si un valor específico pertenece a un grupo de valores previamente almacenados.
  • Para indexar información.
  • Para asociar valores entre sí.
  • Para clasificar información.
26
¿Cuáles son los cálculos más comunes usando vectores?
  • Calcular la suma de los valores almacenados.
  • Calcular el promedio.
  • Encontrar el mayor valor dentro del vector.
  • Encontrar el menor valor dentro del vector.
27
¿Cómo calcular la suma?
  • El ejemplo del recorrido visto previamente muestra como, mediante el uso de una variable acumuladora, se puede ir sumando cada elemento del vector para finalmente acceder al valor acumulado.
  • Este tipo de procedimiento es típico y puede utilizarse para diferentes cálculos incluyendo el del promedio de un grupo de valores.
28
¿Cómo se calcula el promedio de los valores de un vector?
  • Para calcular un promedio simplemente bastaría con acumular la suma y dividir entre el total de elementos que fueron sumados.
  • Si el promedio incluye a todos los elementos del vector basta con dividir entre el tamaño del mismo.
  • En caso contrario hace falta disponer de un contador para incrementarlo en uno cada vez que se suma un valor a la suma total y al final dividir entre dicho valor.
  • En caso típico es promediar solamente los valores mayores que cero dentro de un vector o que cumplen con algún criterio de selección específico.
29
¿Cómo se pueden encontrar el máximo y el mínimo en un vector?
  • Otro ejemplo típico de recorrido en vectores incluye el encontrar la posición del elemento mayor o menor.
  • Normalmente se puede asumir que el valor más alto o más bajo se encuentra en la primera posición del vector, a partir de ahí se puede llevar a cabo un recorrido buscando otro elemento que sea más pequeño que el menor o más grande que el mayor.
  • Un error común es definir una variable para guardar el valor del menor o el mayor inicializando en 0 la misma.  Por ejemplo: Si todos los números son negativos { -12, -6, -10} va a salir que el mayor es 0 aunque el mayor es -6. Aunque son cálculos simples siempre hay que tener cuidado con esto.
30
EJEMPLO 4 – Demostración de cálculos básicos utilizando vectores
  • Ir al ejemplo
31
EJERCICIO 4 – Aplicación de cálculos básicos utilizando vectores
  • Ir al ejercicio
32
¿Cuáles son los algoritmos más comunes para ordenar los elementos de un vector?
  • Los algoritmos de ordenamiento son de los más estudiados en el campo de la computación.
  • Los algoritmos más comunes y simples de ordenamiento son: burbuja y selección.
  • Existen otros más eficientes y complejos tales como el ordenamiento rápido o “quicksort” cuyo estudio se lleva a cabo en cursos de Estructuras de Datos y Análisis de Algoritmos.
33
¿En qué consiste el algoritmo de Burbuja?
  • El algoritmo de burbuja se basa en llevar a cabo recorridos por el vector comparando el elemento de cada celda con el de la siguiente celda.
  • En cada momento se intercambian los elementos o se dejan tal y como están para asegurar que el valor más alto encontrado “suba” o se desplace hacia la derecha.
  • El efecto de esto es lograr que el valor más alto o bajo (dependiendo de la forma en que se programe) “suba” hasta la última posición del vector a modo de “burbuja”.
  • Si este proceso se repite tantas veces como elementos tiene el vector, todos los elementos subieron hasta la posición más alta que podían encontrar, asegurando que que el vector ha quedado ordenado.
34
Visualización de la ejecución del algoritmo de Burbuja
35
EJEMPLO 5 – Ordenamiento de vectores con el algoritmo de Burbuja
  • Ir al ejemplo
36
EJERCICIO 5 - Ordenamiento de vectores con el algoritmo de Selección
  • Ir al ejercicio
37
¿Cuales son los algoritmos de búsqueda más comunes en vectores?
  • Dependiendo del hecho de que  un vector esté ordenado o no, así se puede utilizar alguno de los siguientes tipos de búsqueda:
  • Búsqueda secuencial: consiste en llevar a cabo un recorrido a lo largo de todos los elementos del vector.  Esto hay que hacerlo si los elementos del vector no están ordenados.
  • Búsqueda binaria: consiste en descartar con cada comparación la mitad de los elementos restantes en el vector.  Aplica solo si el vector está ordenado y puede reducir el tiempo de búsqueda llevando a cabo solo unas cuantas comparaciones.


38
EJERCICIO 6 - Búsqueda secuencial de la posición de un elemento en un vector
39
¿Cómo se puede buscar dentro de un vector ordenado con búsqueda binaria?
  • La búsqueda binaria consiste en ubicar la posición de un elemento ubicado dentro de un rango de elementos.
  • El rango se define mediante la posición del elemento inicial y la posición del elemento final.
  • La idea central detrás del algoritmo de búsqueda binaria es que con una sola comparación se logre reducir a la mitad el rango de búsqueda dentro del vector.  Se elimina la mitad del rango donde se sabe que el elemento no está.
40
¿Cómo se puede buscar dentro de un vector ordenado con búsqueda binaria? (cont.)
  • Lo anterior se logra al comparar siempre el valor buscado con el que se encuentra en la posición ubicada en la mitad del camino entre la primera y última posición del rango de valores dentro de los que se está buscando.
    • Si el valor es igual al encontrado se devuelve esa posición.
    • Si es menor se busca en el nuevo rango definido desde el inicio hasta la mitad – 1. Si el valor es mayor se busca en el rango comprendido entre la mitad + 1 y el final.
    • Si el inicio y el final llegan al mismo punto sin encontrar el elemento se devuelve una posición inválida indicando que el elemento no se encuentra en el vector.
  • Note que el proceso es naturalmente recursivo.
41
Visualización de la búsqueda binaria en un vector. Búsqueda del valor 51.
42
Visualización de la búsqueda binaria en un vector. Búsqueda del valor 48.
43
EJEMPLO 6 – Búsqueda binaria de la posición de un elemento en un vector
  • Ir al ejemplo
44
¿Cómo se pueden asociar, indexar y clasificar datos con vectores?
  • Además de permitir almacenar múltiples datos a la vez, la capacidad de utilizar índices para ubicar o “desreferenciar” el valor de una celda específica le da una versatilidad importante y muy útil a los vectores.
  • Métodos como utilizar un mismo índice para acceder a varios vectores a la vez, o utilizar el valor de un vector como índice en otro vector (uso de índices de forma anidada o indirecta) permiten codificar de forma inmediata operaciones comunes en las aplicaciones modernas.
45
¿Cómo se pueden asociar valores entre sí mediante el uso de vectores?
  • Existen varias formas de asociar vectores, la más común es asumiendo que cada celda en una posición dada de un vector tiene relación con los valores de las celdas de otros vectores que se ubican en una posición con el mismo valor .
  • Esto permite recorrer varios vectores en un solo ciclo relacionando  los valores de las celdas con posiciones comunes entre sí.
46
Visualización de la relación entre celdas de vectores diferentes usando índices
47
EJEMPLO 7 – Demostración de asociación de datos con vectores
  • Ir al ejemplo
48
¿Cómo se puede indexar información mediante el uso de vectores?
  • Cuando se tiene una estructura o vector con datos pertenecientes a objetos compuestos cuya información no se quiere duplicar, se pueden crear otros vectores que contengan las posiciones o “índices” del vector de datos.
  • Cada vector con índices tendrá el orden en que se desean “recorrer” los datos del vector principal .
  • Si se quieren los datos en el orden especificado en un vector de indexación se recorre tomando los valores de cada celda y se utiliza cada uno como el índice para ubicar posiciones en el vector que contiene los datos.
  • La siguiente figura muestra el uso de tres índices de ordenamiento diferentes para un mismo vector de objetos.
49
Visualización del uso de tres vectores como “índices”
50
EJEMPLO 8 – Demostración de   indexación de datos con vectores
  • Ir al ejemplo
51
¿Cómo se puede clasificar información utilizando vectores?
  • Otro caso típico es tener un vector que se asocia mediante el índice a un vector y su contenido se utiliza como índice de un tercer vector.
  • La combinaciones que se den van a depender del problema que se quiere resolver y de la forma en que se visualice la información que se quiere representar.
52
Visualización del uso de vectores para clasificar información
53
EJEMPLO 9 – Demostración de clasificación de datos con vectores
  • Ir al ejemplo
54
EJERCICIO 7 – Utilización de vectores para resolución de problemas
  • Ir al ejercicio
55
Fundamentos de vectores y matrices
  • Matrices
56
¿Qué es una Matriz?
  • Una matriz es típicamente una estructura bi-dimensional compuesta de celdas.
  • Cada celda es identificada por las coordenadas asociadas a cada una de las dos dimensiones que la componen.
  • La matriz puede ser vista como una tabla compuesta por filas y columnas.


57
¿Cómo se puede representar gráficamente una matriz?
58
¿Cómo se implementa una matriz en Java?
  • En java una matriz se implementa mediante un vector de vectores.
  • Se puede declarar e inicializar primero un vector de filas, y luego declarar e inicializar cada una de las filas individualmente.
59
Visualización en memoria de una matriz en Java
60
¿Cómo se puede tener acceso a las celdas de una matriz?
  • Para tener acceso a las celdas de una matriz se debe “desreferenciar” la celda deseada indicando los índices o coordenadas de la misma dentro de la matriz.
  • Aunque los índices no corresponde a filas o columnas es “útil” tener consistencia en la interpretación que se le da a cada coordenada. Por ejemplo asumir que la primera coordenada siempre representa filas y la segunda las columnas.
  • En la mayoría de los lenguajes se utilizan paréntesis cuadrados para indicar las coordenadas.
61
¿Cómo se puede tener acceso a las celdas de una matriz en Java?



62
¿Qué se entiende por “recorrido” de  matrices?
  • Dependiendo del problema se puede requerir llevar a cabo secuencias de acceso a las celdas en forma consecutiva.
  • Por ejemplo:
    • sumar todos los valores de una fila específica, o de una columna.
    • imprimir los valores de las celdas que se encuentran alrededor de una celda específica.
  • A estas secuencias de accesos consecutivos  se les llama “recorridos”.
  • Para recorrer eficientemente una matriz es conveniente comprender como variar los índices para manipular el orden en que se visitan las celdas.
63
Visualización de un recorrido en una matriz
  • En esta matriz de 2 filas y 3 columnas se visitan las celdas en el orden siguiente:
    • (0,0) (0,1) (0,2)
    • (1,0) (1,1) (1,2)
    • (2,0) (2,1) (2,2)
  • Por lo que se imprime la salida:
  • 5 12 10
  • 2 8 45
  • 14 21 37
64
EJEMPLO 10 – Declaración, inicialización y recorrido de matrices
  • Ir al ejemplo
65
EJERCICIO 8 – Declaración, inicialización y recorrido de matrices
  • Ir al ejercicio
66
¿Cómo se puede recorrer la matriz en una dirección específica?
  • Para calcular la posición de una celda con respecto a otra con el fin de “recorrer” la matriz en una dirección específica basta con obtener “nuevas” coordenadas.
  • Las “nuevas coordenadas” se obtienen a partir de las “originales” dependiendo de la dirección deseada.
  • Se debe modificar cada índice de fila y columna ya sea sumando 1, restando 1 o dejando el valor igual.
67
Visualización del recorrido de celdas en una dirección específica
  • Desplazarse ascendentemente en diagonal se logra decrementando la coordenada de la fila e incrementando la columna en cada iteración.
68
¿Cómo se pueden recorrer las celdas vecinas de una celda en una matriz?
  • Una forma de desplazarse alrededor de una celda con coordenadas (fActual,cActual) de manera automática es obteniendo todas las posibles combinaciones de -1, 0 y 1 para obtener las coordenadas de las celdas restringidas a las filas y columnas anteriore y siguiente con respecto a la actual.
  • En otras palabras solo las celdas con valores entre  fActual-1 y fActual+1 y entre cActual-1 y cActual+1 se deben tomar en cuenta. Sin embargo así no se puede controlar el orden de visita, sinó que solo se puede asegurar que todas las celdas vecinas son visitadas.
69
Visualización del recorrido de las celdas vecinas
  • Las celdas alrededor de la celda actual (1 , 2) son aquellas con valores entre las columnas 0 y 2 y las filas 1 y 3.
  • Los valores del rango se obtienen sumando y restando 1 a la fila y columna actual.
70
¿Cómo se puede generalizar el movimiento hacia una dirección dada?
  • El cálculo de las nuevas coordenadas al moverse en una dirección dada siempre se puede llevar a cabo con una simple suma.
  • Para subir, a la fila se le suma -1, para bajar se le suma 1
  • Para ir a la izquierda, a la columna se le suma -1, para ir a la derecha se le suma 1
  • El siguiente diagrama muestra los valores que hay que sumar a las coordenadas actuales para desplazarse en la dirección indicada.
71
Visualización de valores necesarios para desplazarse en una dirección dada
72
¿Cómo utilizar vectores para controlar un recorrido?
  • Una posible forma de generalizar el concepto de dirección es almacenando los valores de desplazamiento en vectores de dos vectores utilizados para el cálculo de índices. Uno para filas y otro para columnas.
  • El índice de cada uno de los dos vectores representa la dirección deseada y el contenido de cada celda es el valor que hay que sumarle a la posición actual para moverse en la dirección asociada al indice.
  • De esta forma se puede controlar el orden de visita a las celdas y pueden visitarse una misma celda varias veces en un recorrido.


73
Visualización de un recorrido controlado con vectores
74
EJEMPLO 11 – Demostración de técnicas para el control de recorridos específicos en matrices
  • Ir al ejemplo
75
EJERCICIO 9 – Utilización de técnicas para el control de recorridos específicos en matrices
  • Ir al ejercicio
76
EJEMPLO 12 – Demostración del uso de matrices para resolución de problemas
  • Ir al ejemplo
77
EJERCICIO 10 – Utilización de matrices para resolución de problemas
  • Ir al ejercicio