Matrices: Todo lo que necesitas saber

Fuentes.png

Una matriz, como ya vimos antes puede ser aproximada desde dos puntos de vista:

Ven te daré un repaso:

Transformaciones Lineales

Siendo muy general para cualquier transformada tenemos que:

i

Es decir, la formula completa de cualquier transformada lineal en dos dimensiones sería:

rans

Y así tu colocas en la entrada cualquier vector y obtendrás la posición de ese vector tras la transformada lineal, y si te das cuenta, TODA la información de dicha transformación puede ser resumida en 4 números.

De hecho esto es tan importante que muchas veces los agrupamos juntos, y generamos lo que se conoce como una matriz:

matriz

Que no es más que juntar toda la información (osea las coordenadas de los vectores básico) tras una transformación lineal. Y con esto tenemos encapsulada TODA la información que existe sobre la transformación entre estos corchetes.

¿Quieres saber más?¿No me entendiste un comino? ¡Ve la Lección Pasada!

  • Una tabla con valores

Y ya, no hay mucho mas interesante que contar de este forma de verlo.

De cualquier manera, lo importante ahora ya no es que son, sino como podemos jugar con ellas, veamos:


Simbología para una Matriz

Esto es una Matriz:

  • Con Mayúscula se denota a la Matriz.
  • Con minúscula se denota a cada elemento dentro de ella.

Fisica.png

También podemos hablar de un elemento en especial de esta manera:Fisica-3.png


Tamaño

Una matriz de m filas por n columnas.

a


Dividirlas

Podemos dividirlas usando la idea de que podemos dividir a todas las matrices en 4 partes:

multi-2multi

Si las dividimos de esta manera tenemos que nuestras nuevas 4 submatrices son:

a

En palabras esto quiere decir que:

  • Primero vamos a hacer una partición que abarque desde a1,1 hasta am1,n1
  • Después vamos a hacer una partición que abarque desde a1,n1 hasta am1,n2
  • Después vamos a hacer una partición que abarque desde am1,1 hasta am2,n1
  • Finalmente vamos a hacer una partición que abarque desde am1,n1 hasta am2,n2

Clasificación de Matrices

b.png

Rectangulares:

fila .png


Cuadradas

Estas son las más interesante porque tienen una forma geométrica genial y es que cualquier matriz cuadrada encierra TODA la información de una transformación lineal de n dimensiones (Incluso si no me entendiste, tienes que admitir que suena cool) 

Y podemos hablar mucho de las matrices cuadras, para empezar las dos diagonales:

Fisica.png

Y gracias a estas diagonales podemos crear las matrices triángulos que son las que del otro lado de una matriz son todo ceros:

Fisica-2.png

Y son las combinamos tenemos dos cosas muy importantes:

b.png

La Matriz Identidad

Esta es una matriz muy importante porque esta encapsula una transformación lineal en la que todo sigue igual, osea la transformación lineal más aburrida de todas.

a.png


Operaciones

Recuerda que en las siguientes dos operación SOLO se pueden realizar si son matrices del mismo orden.

a.png

resta.png


Multiplicación

1486397897592.jpg

Empecemos por lo MÁS MÁS BÁSICO 

Resorte.png

Para multiplicar 2 matrices tenemos que estar seguro de lo siguiente:

  • La matriz A debe ser de m x n
  • La matriz B debe ser de n x p

Y por lo tanto la matriz tendrá un orden m x p

Además hay que recordar que NO ES CONMUTATIVA ESTA OPERACIÓN.

a.gif

Este GIF deberán explicarlo lo suficientemente bien.

¿Y que significa esa Operación?

Recuerda que en una matriz esta toda la información de una transformación lineal, así que si la multiplicación por un vector cualquiera obtener la posición de ese nuevo vector, con la formula que hicimos en la lección pasada:

refinal

La vieja confiable fórmula para matrices : ,)

Podemos entender una multiplicación de matrices simplemente como la «composición» de  dos transformaciones lineales:

Captura de pantalla 2017-02-26 a las 6.49.53 p.m..png

Es decir, en vez de aplicar primero una transformación y luego la otra (lo cual a la larga es mucho trabajo) mejor primero saca esa composición de matrices.

Y eso es lo que significa multiplicar matrices, es encontrar una composición,  de ahí que no sea transitiva, no es lo mismo hacer primero una rotación y luego estirar el espacio, que hacerlo pero al revés.


Matriz Transpuesta

Una matriz transpuesta es una matriz igualita a A donde cada coordenada esta cambiada,mas bien esta girada, déjame me explico con dos elementos:

a.png

2.png

3.png


Simétrica

«Es una matriz cuya transpuesta es igual a si misma»

Para lograr verificar que es simétrica, hay que tener en cuenta estas ideas:

  • Debe ser cuadrada
  • Ignora la diagonal
  • Comprueba una a una las demás

captura-de-pantalla-2017-02-07-a-las-1-44-01-a-m

multi.png


Antisimétrica

«Es una matriz cuya transpuesta es igual a si misma (por -1)»

Para lograr verificar que es simétrica, hay que tener en cuenta estas ideas:

  • Debe ser cuadrada
  • Ignora la diagonal
  • Comprueba una a una las demás

e.png


Dependencia Lineal

La dependencia lineal de una matriz es justo lo que vimos en la clase pasada (QUE DEBERIAS VER SI NO LA HAS VISTO ¡YA!)

Repaso 1:

Dependencia y Independencia

Sirve para describir que cierto vector, es más bien inútil. Pues si lo eliminamos nuestro rango o «sean» sigue siendo exactamente igual.

dependencial.png

Es decir que podemos expresar a nuestro vector como la combinación lineal de w.

Repaso 2:

Hay algo muy importante y también curioso que recordar y es que puede pasar que en nuestra transformación ambos vectores resultantes sean dependientes, en ese caso, tenemos que la transformación aprieta a todo el espacio 2D en una sola línea

lineal34.gif

Bueno, ahora si vamos con las matrices en si:

RECUERDA QUE COMO YA VIMOS LAS TRASPUESTAS LO QUE VOY A DECIR PARA LAS COLUMNAS TAMBIEN SIRVE PARA LAS FILAS. LA DEPENDENCIA LINEAL LA CONSERVA UNA TRASPUESTA.

rac.png

Ahora lo único que deberíamos buscar es que podamos expresar un vector como la suma de los otros 2.

1


Rango

Es una operación que nos permite calcular el número de filas / columnas linealmente independientes.

Operaciones Elementales

Para lograr esto se usa lo que se conoce como operaciones elementales, las operaciones elementales son operaciones en las que NO se afecta el rango.

1.- Intercambio de Filas / Columnas

real

2.- Filas / Columnas por un escalar (n no debe ser 0)

captura-de-pantalla-2017-02-08-a-las-2-19-43-p-m

3.- Suma  Filas / Columnas y producto por otra

4

Podemos unir las 2 ultimas operaciones y así quedarnos con 2 operaciones:

5

Rango por Gauss

Para hacerlo, vamos a tener que realizando operaciones elementales llegar a una matriz triangular, como esta:

Fisica-2.png

En resumen las operaciones que tenemos permitidos usar son:

  • Permutar una fila/columna
  • Multiplicar una fila/columna por un escalar
  • Sumarle a una fila/columna otra fila/columna multiplicada por un escalar
  • Eliminar filas proporcionales o nulas

Cuando lleguemos a nuestra matriz triangular nuestro rango será el numero de filas/columnas que no sean nulas.

Veamos un ejemplo:

1

Recuerda que tenemos que hacer todos los circulitos a que valgan a cero.

Así que empecemos:

a5a4a3a2a1

Y ya, como viste así podemos llegar y concluir que el rango es el número de columnas/filas que NO sean nulos.



Matrices Inversas

1.png

Recuerda otra vez que una matriz no es más que la información de una transformación lineal, así que podemos pensar en una características más de estas.

¿Existe una transformación que revierta lo que acabo de hacer?

19.gif

Si claro que existe y se llama obviamente la transformación inversa, así si tenemos una matriz, tenemos una matriz inversa.

¿Cómo demonios las calculo?

Algo genial del método de gauss es que nos da una forma muy fácil de calcularla, tenemos que seguir los siguiente pasos:

Paso 1: Dibujar nuestra zona de batalla.

Esta cosa se llama «matrices ampliadas», de un lado tenemos a nuestra matriz y del otro a la matriz identidad.

a1.png

Paso 2: Transformar a la Matriz X en nuestra Matriz Identidad, usando las operaciones elementales y en general el Método de Gauss, veamos un ejemplo:

inversa1inversa2inversa3inversa4inversa5inversa6

Inversa y el Determinante

Si una matriz es invertible, es decir tiene inversa entonces su determinante es diferente de cero. Y a la inversa, si s determinante es diferente de cero entonces tiene que tener una inversa.

…Tienen que admitir esa relación es simplemente genial.

La Inversa y la solución de Ecuaciones

Teoremas:

  • Si una matriz es invertible, siempre el sistema homogéneo de esa matriz tiene una única solución, y también en el sentido opuesto, basta con encontrar que tiene solución única para saber que es invertible.
  • Si una matriz es invertible o tiene un sistema homogéneo con solución única, podemos decir que el sistema tiene solución para cualquier vector en el campo.

Podemos usar la inversa también para encontrar las soluciones:

Captura de pantalla 2017-03-08 a las 9.36.57 a.m..png

Podemos decir entonces que la solución de cualquier matriz (siempre que tenga inversa) es:

Captura de pantalla 2017-03-08 a las 9.46.55 a.m.


Vectores Canónicos

Un vector cántico de Rn es una matriz fila / columna de mx1 o 1xn donde todos sus elementos son ceros excepto uno que es el uno del campo.

*Considere que están en R3

a2

Un vector canino tiene la siguiente forma:

a1

a3.png


Código que hace Todo Esto

Palomitas.png

btn1 btn
btn

Transformaciones Lineales

 

Fuentes-2.png

 

Recuerda que si quieres un texto mas formal y con ejemplos de la vida real solo da click:

ApuntesDe-2

Ya hemos visto de matrices de muchas otras maneras pero ahora vamos a verlas desde un punto de vista completamente nuevo.

Este tema es de suma importancia, es la píldora que hace que todo empiece a tener sentido, así que empecemos por el nombre, y como dijo Morfeo:

morfeo

«Lamentablemente nadie te puede decir que es la Matriz, tienes que verlo con tus propios ojos»

Introducción

Una Transformación es un palabra «rara» para hablar de funciones. Una transformación es  una función que recibe un vector, lo modifica y regresa otro vector.

Entonces ¿Porqué usar la palabra «transformación»?  Porque es muy común y sobretodo útil hablar de estas operaciones mediante el movimiento, transformada quiere decir movimiento. Es decir nos imaginamos ver como se movería nuestro vector inicial esta su posición final:

plano.gif

Como ves se puede poner algo pesado, así que vamos a usar las líneas para que no se vea tan complicado.

Además recuerda que estamos hablando de transformaciones LINEALES  así que estas son bastantes sencillas, una transformación lineal es si:

  • Todas las líneas tendrán que seguir siendo lineal después de la transformación, después de todo se llama transformación lineal.
  • El origen tiene que seguir en el mismo punto.

 

A continuación te muestro varias transformaciones que NO son lineales:

Caso 1: Hace las líneas curvas. Así de sencillo, si eran lineas, deberán seguir siendo lineas.

lineal30

No Lineal por las curvas

Caso 2: Se mueve el origen, y es que aunque todo lo demás funcione, si el origen no esta bien colocado entonces no funciona.

lineal31

No Lineal por mover el origen


Transformaciones Lineales

 

Lineal3

Sea V y W dos espacios vectoriales sobre un mismo campo K. Una transformación lineal de V → W es una función que cumpla con esto:

Lineal1

Combinación Lineal

Podemos tambien tener que como consecuencia de lo que tenemos arriba que podemos encontrar que T es una transformación lineal si y solo si se cumple que:

Lineal2

Así que para probar que una T es o no transformación lineal basta con verificar que se cumplan las 2 propiedades originales.


Propiedades

  • El 0v se preserva: Una Transformación Lineal debe llevar al 0v de V al 0v de W
  • Operador Lineal: Decimos que T (alguna transformación lineal) es un operador lineal en V si y solo si su dominio y su contradominio son el mismo.


Kernel

Definición

El Kernel de una Transformación Lineal o Núcleo es el conjunto de todos los vectores originales (osea v ∈ V ) tales que al momento de aplicarles la transformación estos son llevados al origen (osea 0w)

O dicho con el bello lenguaje de matemáticas:

Kernek2

Recuerda que un Kernel siempre siempre sera un Subespacio Vectorial y solemos llamar a su dimensión la ’Nulidad’.

Podemos decir que el Kernel es el espacio solución del Sistema Homogéneo.

 


Imagen

Tambien tenemos a la hermana perdida del Kernel, la llamamos la Imágen, la cual la definimos así:

Definición

La imágen de una Transformación Lineal es el conjunto de todos los vectores nuevos (osea w ∈ W ) que podemos ’crear’ desde los vectores originales (osea v ∈ V ) usando la Transformación Lineal.

Kernek1

 

Recuerda que una Imagen siempre siempre sera un Espacio Vectorial y solemos llamar a su dimensión ’Rango’.

Podemos decir que el Imagen es el conjunto de terminos independientes para los cuales hay solución.

 


Propiedades de Ambas

Podemos hablar de que ambas paracen ser como hermanas perdidas, veamos que pro- piedades tenemos:

  • Llamemos Rango a Dim(Imagen(T ))
  • Llamemos Nulidad a Dim(Kernel(T ))
  • Ambas Son SubEspacios Vectoriales.

Estas de acuerdo que todos los vectores o bien son llevados al cero vector o no, así que tiene sentido hablar de que La Suma de la Nulidad con el Rango te da la dimensión de V

 

 

 

 

 



Parte Grafica

Hay unas muy fáciles de describir, como la traslación, otras que es mucho más fácil ver que contar.

Piensa en las transformaciones lineales como aquellas que hacen que queden las lineas paralelas y que tengan un espacio igual entre todas ellas.

lineal33

Rotaciones con eje en el origen

lineal34

No tengo ni puta idea de como describir esto

…Bueno, bueno, bueno, todo muy cool, pero ¿Cómo hago matemáticamente para describir esto?

out

Bueno, pues resulta que solo basta con saber donde quedan dos vectores para conocer donde quedan todos los vectores posibles en el plano: Los básicos.

basicos

La vieja confiable

Tomemos un vector de ejemplo y hagamos una transformación lineal:

inicio

Inicio v=-1i + 2j

lineal35

Desarrollo

final

Final v=-1i + 2j

Lo primero en lo que deberíamos fijarnos es que la representación numérica no cambio, es decir: v= -1i + 2j sigue describiendo a nuestro vector amarillo ¡Genial!

j

trans = Tras la Transformación Lineal

Esto es la clave a todo, porque solo basta con encontrar la relación entre nuestros vectores básicos originales i y j y nuestro nuevos vector básicos i y j transformada y tenemos todo este misterio resuelto.

menu.png

Esto lo podemos expresar de manera numérica como:

trasns

O siendo muy general para cualquier transformada tenemos que:

i

Es decir, la formula completa de cualquier transformada lineal en dos dimensiones sería:

rans

Y así tu colocas en la entrada cualquier vector y obtendrás la posición de ese vector tras la transformada lineal, y si te das cuenta, TODA la información de dicha transformación puede ser resumida en 4 números.

De hecho esto es tan importante que muchas veces los agrupamos juntos, y generamos lo que se conoce como una matriz:

matriz

Que no es más que juntar toda la información (osea las coordenadas de los vectores básico) tras una transformación lineal. Y con esto tenemos encapsulada TODA la información que existe sobre la transformación entre estos corchetes.

Es decir podemos entonces definir la multiplicación como:

final

Y reacomodando un poco podemos llegar a:

refinal

La vieja confiable fórmula para matrices : ,)

lineal30.gif

Ejemplo de forma gráfica. La matriz te da la transformación.


Ejemplos

Veamos unas de las transformaciones mas comunes usando lo que acabamos de aprender.

Girar 90º

lineal31.gif

Matriz que gira 90 grados el espacio

Corte o Shear

lineal32.gif

Matriz que «aprieta el espacio»


¿Y a la inversa?

¿Y si lo quisiera hacer al revés? Osea, teniendo los números imaginarme como sería la transformación.

La respuesta es muy sencilla, ve primero como mueve el espacio un vector básico a la vez, primero i y luego j, y listo.

lineal33.gif

Primero i y luego j

Hay algo muy importante y también curioso que recordar y es que puede pasar que ambos vectores resultantes sean dependientes, en ese caso, tenemos que la transformación aprieta a todo el espacio 2D en una sola línea

lineal34.gif

Volvamos en 2D un 1D

btn1 btn
btn

Combinaciones Lineales

fuentes-2

MUCHOS GIFS, ESTO VA A TARDAR EN CARGAR, PERO VALE LA PENA

Antes que hablar de ellos quiero dejar claro que los Sistemas de Coordenadas, ahí esta la clave, primero que nada, veamos el que ya conocemos:

Sistema Rectangular

rectangular.png

Visual

vec.png

Abstracta

Este es el sistema rectangular, tiene dos vectores base que tienen el tamaño de una unidad y que apuntan en la dirección de los ejes. Es el que hemos ocupado toda la vida.

…La pregunta increíble aquí es : ¿Qué pasaría si hubiera elegido otros vectores base?

Por ejemplo, digamos estos 2:

base.png

Nuevos vectores base

¿A qué lugar del plano podríamos alcanzar solo multiplicando y sumando esos vectores?

pla.gif

¡A todos lados!

A menos que seamos demasiado estúpidos (osea que elijamos dos vectores que apunten hacia el mismo lugar) ¡Cualquier par de vectores puede servir para generar un nuevo Sistema de Coordenadas! , en donde tus dos vectores que elegiste son tus vectores base.

Y lo más curioso de todo esto es que la representación abstracta cambia, los números que describen a un mismo vector cambian si cambias el sistema de coordenadas.

scalar.gif

Los números cambian

Pero ya veremos eso más a fondo luego.


Combinación Lineal

Cada vez que vayas «escalando» y sumando dos vectores cualquiera lo llamamos combinación lineal.

lineas.png

Donde A y B son números normales.

¿Porqué se llama así? Pues no es la razón original, pero hace poco aprendí que si dejas uno de esos fijo y vas variando el otro escalar obtienes un linea recta:

a

Y si ahora dejas que ambos se muevan de manera libre, como ya vimos arriba ¡Cubren todo el espacio! Bueno, mejor, seamos un poco más estrictos y veamos las posibilidades:

Caso 1: Si se alinean. Si resulta que ambos vectores se alinean, osea que el ángulo entre ellos es 0, entonces solo nos podemos mover una una linea que pasa por el origen.

Este caso también ocurre si UNO Y SOLO UNO de tus vectores es 0.

1.png

Caso 2: Si NO se alinean. Casi seguro no te va a tocar la mala suerte de elegir dos vectores que se alinean, y si es que hay un ángulo entre ellos, aunque sea minúsculo, entonces resulta que como vimos antes puedes acceder a todos los lugares del plano.

2.png

Caso 3: Eres un punto. Si ambos vectores valen cero, antes… Bueno, estas atrapado en el origen. Por estúpido.

3

Rango o Span 

Este termino es básicamente el conjunto de todos puntos que puedes tocar usando los dos vectores que escogiste. Es una forma de preguntar ¿En qué caso me encuentro?

Podemos verlo desde otra manera, en especial en el caso 1, pues si imaginamos el rango del caso de un vector y un punto obtenemos que es una linea que cursa el origen, y si luego añadimos otro vector que se encuentra en ese rango entonces, las cosas no cambian. Sigues solo pudiendo  acceder a esa línea. Esta idea es muy importante, tanto que tiene sus propios conceptos.


Dependencia y Independencia

Sirve para describir que cierto vector, es más bien inútil. Pues si lo eliminamos nuestro rango o «sean» sigue siendo exactamente igual.

dependencial.png

Es decir que podemos expresar a nuestro vector como la combinación lineal de w.

Y como cada cosa tiene su opuesto entonces tenemos que si cada vector de verdad añade una dimensión más a nuestro rango ,si nuestro vector no es inútil entonces tenemos que es:

independncia.png

Es decir que podemos NO podemos expresar a nuestro vector como la combinación lineal de w, sin importar que números A y B elijamos, será imposible.

…Con toda esta terminología, finalmente podemos terminar la introducción de este curso y decir que:

«Los vectores base de un espacio vectorial son el conjunto de vectores linealmente independientes que recorren todo el espacio»

btn1 btn
btn

Introducción a Álgebra Lineal

fuentes-2

MUCHOS GIFS, ESTO VA A TARDAR EN CARGAR, PERO VALE LA PENA

«Difícilmente hay algo tan bonito como Álgebra Lineal, a pesar de las generaciones y generaciones de profesores y alumnos que han oscurecido su belleza y simplicidad con sus cálculos horribles sobre matrices.»

Un tipo muy sabio (Jean Dieudonné)

Este tipo lo decía enserio, si te das cuenta esta es una de las pocas materias que es necesario para casi todo.

  • ¿Eres Físico? La necesitas.
  • ¿Eres computólogo/ ingeniero? La necesitas.
  • ¿Eres matemático? ¿Biologo? ¿Economista? La necesitas.

La finalidad básica del álgebra lineal es la que hacer que conceptos y grandes cantidades de información sean «analizables», su objetivo es ayudar a encontrar esos patrones que son muy difíciles de ver si lo vieras los números.

Su objetivo es:

analizar.gif

Desbloquear la magia dentro de los números


Vectores

Como te darás cuenta pronto los vectores son la base del álgebra lineal, los bloques con lo que construirás todo, la materia que habita este universo. Así que antes que nada, es hora de entenderlos un poco mejor.

Puntos de Vista

Pero, tenemos un problema: Es que depende de en que contexto estemos hablando podemos hablar de 3 puntos de vista diferentes:

Físico: Por un lado podemos hablar usando al física, en la cual los vectores son «flechas», son herramientas que nos permiten visualizar o hacer cálculos sobre algo físico, algo real.

vectores-copia

Físicos

Ingeniería: Si estás estudiando computación, quizá te interese más la forma de verlo en solo son una forma «cool» de decir listas de números.  Sirven para agrupar datos y ya…No tiene ninguna descripción en el mundo real , sólo son un montón de números juntos.

vectores

Ingeniero

Matemáticos: Hay algo también muy importante y es que para los matemáticos, un vector es cualquier cosa en la que exista la suma entre estas entidades y multiplicación por un escalar.

vectores-copia-2

Matemático

… Los matemáticos buscan generalizar ambos puntos de vista, así que para hacerlo se centran en estas dos operaciones (luego les contaré porque exactamente porque).

Además ya desde ahora podemos encontrar una pequeña relación entre ambos puntos de vista:

vector

Unión de ambas visiones

Podemos hacer que nuestras listas de números (perspectiva de los ingenieros) dibuje una flecha en el plano.

Y de igual manera podemos hacer que nuestra flecha sea asociada con un conjunto de números.


Operaciones Super Básicas

Con esta idea podemos adentrarnos más en las operaciones que definen a los vectores:

Suma

Sumar dos vectores da como resultado otro vector. Ok, eso es obvio. Si lo vemos por el lado geométrico tenemos que:

suma.png

Metodo del rectángulo lo llaman

Y si lo vemos analíticamente tenemos que:

lineal.png


Multiplicación por un Escalar

Cuando tu multiplicas un vector por un número normal , lo que obtienes es un vector, pero este ha sido «escalado», es decir, el número real ha hecho a tu vector más grande o pequeño (dependiendo de si es mayor o menor que uno) o incluso puede hacer que cambie de dirección (dependiendo de si es mayor o menor que cero).

escalar

«Escalar» un vector

Este número «escala» a tu vector, y por eso en muchos caso decir que es un «escalar». (A mi me exploto la cabeza la primera vez que lo supe, es tan obvio y sin embargo nunca lo había pensado).

Visto de forma numérica tenemos que:

mult.png

Antes que hablar de los espacios vectoriales quiero dejar claro que los Sistemas de Coordenadas, ahí esta la clave, primero que nada, veamos el que ya conocemos:

Sistema Rectangular

rectangular.png

Visual

vec.png

Abstracta

Este es el sistema rectangular, tiene dos vectores base que tienen el tamaño de una unidad y que apuntan en la dirección de los ejes. Es el que hemos ocupado toda la vida.

…La pregunta increíble aquí es : ¿Qué pasaría si hubiera elegido otros vectores base?

Por ejemplo, digamos estos 2:

base.png

Nuevos vectores base

¿A qué lugar del plano podríamos alcanzar solo multiplicando y sumando esos vectores?

pla.gif

¡A todos lados!

A menos que seamos demasiado estúpidos (osea que elijamos dos vectores que apunten hacia el mismo lugar) ¡Cualquier par de vectores puede servir para generar un nuevo Sistema de Coordenadas! , en donde tus dos vectores que elegiste son tus vectores base.

Y lo más curioso de todo esto es que la representación abstracta cambia, los números que describen a un mismo vector cambian si cambias el sistema de coordenadas.

scalar.gif

Los números cambian

Pero ya veremos eso más a fondo luego.


Combinación Lineal

Cada vez que vayas «escalando» y sumando dos vectores cualquiera lo llamamos combinación lineal.

lineas.png

Donde A y B son números normales.

¿Porqué se llama así? Pues no es la razón original, pero hace poco aprendí que si dejas uno de esos fijo y vas variando el otro escalar obtienes un linea recta:

a.gif

Y si ahora dejas que ambos se muevan de manera libre, como ya vimos arriba ¡Cubren todo el espacio! Bueno, mejor, seamos un poco más estrictos y veamos las posibilidades:

Caso 1: Si se alinean. Si resulta que ambos vectores se alinean, osea que el ángulo entre ellos es 0, entonces solo nos podemos mover una una linea que pasa por el origen.

Este caso también ocurre si UNO Y SOLO UNO de tus vectores es 0.

1.png

Caso 2: Si NO se alinean. Casi seguro no te va a tocar la mala suerte de elegir dos vectores que se alinean, y si es que hay un ángulo entre ellos, aunque sea minúsculo, entonces resulta que como vimos antes puedes acceder a todos los lugares del plano.

2.png

Caso 3: Eres un punto. Si ambos vectores valen cero, antes… Bueno, estas atrapado en el origen. Por estúpido.

3

Rango o Span 

Este termino es básicamente el conjunto de todos puntos que puedes tocar usando los dos vectores que escogiste. Es una forma de preguntar ¿En qué caso me encuentro?

Podemos verlo desde otra manera, en especial en el caso 1, pues si imaginamos el rango del caso de un vector y un punto obtenemos que es una linea que cursa el origen, y si luego añadimos otro vector que se encuentra en ese rango entonces, las cosas no cambian. Sigues solo pudiendo acceder a esa línea. Esta idea es muy importante, tanto que tiene sus propios conceptos.


Dependencia y Independencia

Sirve para describir que cierto vector, es más bien inútil. Pues si lo eliminamos nuestro rango o sean sigue siendo exactamente igual.

dependencial.png

Es decir que podemos expresar a nuestro vector como la combinación lineal de w.

Y como cada cosa tiene su opuesto entonces tenemos que si cada vector de verdad añade una dimensión más a nuestro rango ,si nuestro vector no es inútil entonces tenemos que es:

independncia.png

Es decir que podemos NO podemos expresar a nuestro vector como la combinación lineal de w, sin importar que números A y B elijamos, será imposible.

…Con toda esta terminología, finalmente podemos terminar la introducción de este curso y decir que:

«Los vectores base de un espacio vectorial son el conjunto de vectores linealmente independientes que recorren todo el espacio»

btn1 btn
btn

Tablas Hash

Antes de que comencemos, démonos unos minutos para ver hasta donde hemos llegado:

Arrays

array-2

Ventajas

  • Nos permiten guardar información de un mismo tipo de dato
  • La guardan de manera contigua (osea junta, una al lado de la otra) en memoria.
  • Gracias a lo anterior podemos acceder a cualquier posición que queramos mediante un simple paso, en un tiempo constante sin importar si el el primero o el décimo elemento.

Desventajas

  • No es dinámico, es decir debemos especificar su tamaño cuando lo declaramos
  • Por lo tanto, es muy muy difícil y tardado añadir o quitar elementos (es más ni siquiera es seguro que haya mas espacio libre contiguo en memoria para añadir más elementos)

Listas Enlazadas

lista-enlazad

Ventajas

  • Son super fáciles de hacer crecer pues sus elementos NO son contiguos en memoria.

Desventajas

  • Ya NO toma lo mismo acceder a un elemento cualquiera, pues tendremos que recorrer TODA la lista comparando uno por uno. Es más podemos decir que el tiempo de búsqueda en el peor caso es O(n)

Entonces:

¿Qué pasa si quiero algo que sea mucho más rápido para localizar elementos y que al mismo tiempo sea mucho más fácil de hacerlo crecer si es necesario?

Pues justo para eso se inventaron las:


Tablas Hash

«Heredero de las listas enlazadas e hijo de la reina array»

Usando una definición de libro: Las Tablas Hash son estructuras de datos que se utilizan para almacenar un número elevado de datos sobre los que se necesitan operaciones de búsqueda e inserción muy eficientes.

En palabras simples una Tabla Hash es solo la unión de un array y un función que llamamos Función Hash.

parteshas

Partes de una Lista Hash

Podemos entonces decir que una Tabla Hash se forma por 3 elementos:

  • Una tabla de un tamaño razonable para almacenar los pares (clave, valor).

  • Una función “hash” que recibe la clave y devuelve un índice para acceder a una posición de la tabla.

  • Un procedimiento para tratar los casos en los que la función anterior devuelve el mismo índice para dos claves distintas. Esta situación se conoce con el nombre de colisión.

…¿Qué demonios? ¿Cómo lo hace?

Una Tabla Hash almacena un conjunto de pares “(clave, valor)”.

  • Dato/Clave/Key: Es el parámetro de entrada, es el «dato que queremos guardar»
  • Valor/Indice/HashValue/Code: Es un número, un entero positivo si nos ponemos exquisitos que nos indica donde debemos guardar nuestro «dato» o «clave» dentro de la tabla.

has2

 

Es decir, es casi como hacer que nuestra información nos diga donde debería ir, en vez e ordenarla nosotros mismos.

El único problema que existe con esta estructura es que es HORRIBLE para ordenar información, son simplemente horribles.

Así que: USALA CUANDO NO TE IMPORTE SI LA INFORMACIÓN SE GUARDA DE MANERA ORDENADA.


Función Hash

Esto es la clave, la Función Hash es la clave de toda la magia, porque nos indica donde hay que guardar nuestro dato y también donde es que debemos buscarlo si es que queremos alguna vez.

Esta función SIEMPRE regresa lo mismo: Un entero positivo. Usaremos ese número que nos regresa para saber en que índice de un array vamos a guardar la información

Debido a esto es muy importante que esta se comporte de manera consistente.

¿Qué necesito para que mi Función Hash sea asombrosa?

rainbowmeme

Pero mira esa función papu

Hay muchas cosas, pero nos vamos a enfocar en varios puntos claves, es decir tu función debe ser:

  • Tiene que minimizar las posibilidades de que ocurra una colisión como de lugar.
  • Usará TODA la información que sea proporcionada para maxilar la cantidad de códigos hash.
  • Es determinista, es decir, si le das una entrada x, siempre, siempre tendrá que regresarte el mismo número como resultado.
  • Distribuya los valores de manera equitativa (osea que cosas como «gatos» y  «gata» acaben en lugares muy muy diferentes de la tabla).
  • Repite, tiene que ser capaz de generar indices muy diferentes para datos muy parecidos.
  • Usa una función «sencilla» no hagas 50,000 operaciones para generar cada indice o todo el tiempo de ejecución te la pasarás haciendo eso.

Ahora, dicho esto, hay muchísimas muchísimas buenas función en internet y deberías usar eso a tu favor, escribir una de estas funciones es más un arte.

hash

El Tamaño de la Tabla

El tamaño de una tabla hash es el otro parámetro que debe ser ajustado con cierto cuidado.

Por ejemplo, si el tamaño es demasiado pequeño, digamos 1, de nuevo la tabla se comporta como una lista encadenada.

En cambio, si el tamaño es enorme, el malgasto de memoria es evidente, puesto que habrá un elevado número de posiciones cuya lista de colisiones está vacía.


Colisiones

Antes de hablar de operaciones veamos un último problema con las Tablas Hash, las colisiones, como te has dado cuenta insertar es una operación bastante simple, pero hay un grave problema.. ¿Qué pasa si la clave Hash me da el mismo resultado para dos datos diferentes que quiero guardar?

Por ejemplo si queremos ordenar palabras basados en su primera letra:

Pues hay dos formas de lidear con esto:

Team Linear Probing

Esta solución le vale un comino la vida y si respuesta es simple: Si esta ocupado ese lugar simplemente busca el más próximo que este libre.

lineal

La solución #1

Y esta forma de pensar lleva un problema, y es que empieza a pasar que si mandar ahora tu dato a ese lugar «disponible cerca» ..¿Qué pasará cuando queramos meter el valor que si que debería estar en ese lugar que acabamos de ocupar?

La Respuesta: Otra colisión. Este problema se conoce como «clustering» y esta es principalmente la razón por la cual no usamos este método. Solo trae más problemas.

Y lo peor es que hace que ahora para buscar elementos volvamos a un caso de O(n), es decir todo nuestro trabajo NO valió para nada. :`(

Pero no se preocupen, hay otra solución…

Team Separate Chaining

Esta solución propone lo que veíamos al principio…¿Recuerdas las listas enlazadas?…¿Cuál era su mayor ventaja?

Este team propone que el array donde guardemos la información no sea mas que un array de punteros hacia listas enlazadas…¡Y esa es una solución cojonuda!

Soluciona todos nuestros problemas y hace que nuestra estructura se vea más o menos así:

tabla

¿Ven? ¡Parece una Tabla! Por eso la llaman Tabla Hash

Fíjate que diferentes posiciones de la tabla pueden tener listas de diferente longitud, o incluso vacías.

Dada una clave, el proceso de búsqueda consiste en calcular primero su índice mediante la función de hash, y a continuación buscar esa clave en la lista de colisiones.

hash table.png

Ejemplo de una Hash Table usando Listas

Con esto se logra que el nuevo peor caso posible sea O(n/k)…Y si, a nivel de «complejidad» es lo mismo, pero en el mundo real esa k si que vale, pues si k= 100 por ejemplo hará que programa se ejecute 100 veces más rápido. ¡A eso yo llamo eficiencia! 

btn1 btn
btn

Arboles 3: La Venganza de los Árboles B

Ok, estamos ya en la última parte de árboles, esto si que ha estado siendo pesado, pero no te preocupes ya casi terminamos, así que veamos…

¿Qué hay más allá de los BTS?

Árboles K-arios

A veces lo llaman m-ario o n-ario.

«Un árbol k-ario es todo aquel árbol que tiene grado k, es decir que cada nodo tiene  máximo k hijos»

 

 


Árboles B

«Como los binarios, pero mejorados..(y más difíciles)»

Pero, ¿Porqué existe? ¿Qué no un BTS es lo más eficiente de todo el mundo?

Si, la respuesta es sí, pero el problema es que no vivimos en el mundo perfecto y debido a esto es imposible usar siempre BTS sobretodo por un grave problema, son muchos hijos, eso quiere decir que tendré que buscar varias veces en un lugar muy feo… El disco duro.

hdvsram

Mira, te explico el problema, los discos de almacenamiento son lentos..como que muy lentos, así que un BTS no termina siendo la mejor opción, necesitamos algo parecido pero con más hijos, y ahí están, te presento los Árboles B:

¿Cómo se forma un Árbol B?

Nodo o Páginas

Un nodo en un Árbol B es bastante raro déjame te lo muestro y luego me explico:

CADA Nodo de un Árbol B tiene:

  • K Datos o Claves guardados en el Nodo
  • K+1 Hijos máximo (también se usa la C) (Recuerda que esto es el grado)
b.png

Nodo de un Árbol B

Ok, ok, como te has dado cuenta esto ya no se ve sencillo, me explico ahora si:

  • Todas las claves o datos del nodo deben estar ordenados, osea:

K1 < K2 < K3

  • Entre cada Dato hay un puntero a un hijo, ese hijo tiene que tener datos que son mayores que los datos que están a la izquierda pero datos menos que el dato que esta a la derecha.

 

Se ve mejor con una imagen:

b-2

Los hijos tienen valores entre K1 y K2

 

Cosas Importantes:

Un nodo de un Árbol B de grado M (osea con C hijos) cada nodo debe tener como MÍNIMO M/2 de hijos. (Excepto de la raíz)

Un nodo de un Árbol B de grado M (osea con C hijos) cada nodo debe tener como MÍNIMO (M-1)/2 claves. (Excepto de la raíz)

m.png

 

btn1 btn
btn

 

 

Arboles II: El Ataque de los BST

Nota: Esta lección se lee mejor con palomitas a la mano y el código completo de BTS

*Dale click a las palomitas para ir al Código*palomitas


…Bienvenidos a a segunda parte de Árboles, es de lo más útil que nos encontraremos pero ¿Qué demonios son?

«BTS: Binary Search Tree, osea que es un árbol binario de búsqueda (ósea que esta ordenado)…Si, eso es todo, así de simple un árbol binario ordenado.Punto»

bst-2

Ejemplo de BTS

Digo que un árbol esta «ordenado» cuando tengo un nodo (lo llamamos nodoRaiz) tal que para cualquier nodo que elija se tienen que cumplirse que:

  1. El hijo izquierdo de nodoRaiz (si es que hay) debe ser menor
  2. El hijo derecho de nodoRaiz (si es que hay) debe de ser mayor.

Esta regla se debe de cumplir para TODOS los nodos del árbol.

Para verificarlo basta con que miremos de izquierda a derecha el árbol y veamos is los elementos van de menor a mayor:

bts

BTS

¿Y que vamos a buscar?

De igual manera que con los arboles normales ls BTS guardan su información en nodos, pero más bien la forma de encontrarlos va a ser por comparación, sea de números, ID o por orden alfabético o un método se te ocurra.


Operaciones

Veamos las operaciones que podemos hacer con un BST:

Búsqueda

busqueda

Ejemplo de Búsqueda

Se usa principalmente para dos operaciones derivadas:

  • Una función que se llama Existe que busca si existe un elemento.
  • Una función que se llama ObtenerElemento que regresa un objeto cuyo identificador sea igual al que pedimos.
  • Una función que se llama EliminarElemento que ..bueno, elimina un elemento (que primero hay que encontrar)

Algoritmo

  1. ¿Es el nodo donde estas ahora el que buscas?, si es así regresa el valor, sino:
  2. ¿Es menor? Ve a la rama izquierda
  3. ¿Es mayor? Ve a la rama derecha
  4. ¿Es una hoja? …No existe

Insertar Elemento

Aquí lo primero es preguntarnos si nuestro árbol va a permitir elementos duplicados, sino también (recomendable) hay que tener eso en cuenta.

Recuerda, siempre se inserta en las hojas.

insertar.gif

Insertar

Algoritmo

  1. Si esta vacío va a la raíz
  2. Si donde estamos es igual al elemento a añadir hay que ver que onda con los duplicados
  3. Si es menor que el elemento actual recursivamente inserta en la rama derecha
  4. Si es mayor que el elemento actual recursivamente inserta en la rama izquierda
  5. Si llegamos a una hoja, le haremos un hijo y pondremos el dato ahí

 

 


Eliminar Elementos

Ok, ok, no te alarmes, pero esta puede que sea la operación más difícil de todas (pero ni tanto) 

Pero es que hay varias «formas»de hacerlo dependiendo del número de hijos que tengas, así que vamos con el algoritmo:

Algoritmo:

Como podemos dividir esto en 3 casos, hoy a explicarlo como 3 casos diferentes pero recuerda que todos están unidos:

Caso 1: Si eres un nodo hoja has que tu padre apunte a NULL y borralo, tan simple.

Caso 2: Si tienes un hijo entonces has que tu padre apunte a tu hijo y borralo, tan simple.

Caso 3: Si tienes 2 hijos (aquí esta lo feo) … Así que habrá que hacer dos caminos 3A y 3B desde aquí, pero antes explicaré que vamos a hacer:

..Espera, creo que me he perdido en esa última parte ¿Como que 3A y 3B?

Lo que pasa es que no hay «una forma correcta» de eliminar un nodo con dos hijos ya que a fuerzas hay que cambiar la estructura del árbol para que no perdamos información.

Así que ahora hay que pensar: ¿Qué vamos a poner en donde esta el nodo que vamos a eliminar? ¡Pues muy fácil!, mira este árbol binario, quizá con dibujos sea más fácil:

bst

Aquí un BTS con sus elementos ordenados

Ahora, ¿recuerdas que podemos hacer barras verticales de manera que solo toquen a un nodo?..y eso hace que sea más obvio que esta ordenado:

bts

Perdonen calidad de GIF

Bueno digamos que quiero eliminar el 23, ¿Qué hago?

Pues nuestro objetivo es eliminarlo pero haciendo cuanto menos desastre mejor, así que habrá que elegir en un valor que este muy próximo a 23, mira, aquí esta una lista de cuanto vale cada nodo de forma ordenada:

05,12,21,23,26,53…

Bueno, en realidad solo nos importan los valores próximos a 23:

05,12,21,23,26,53…

Bueno tenemos dos candidatos: O el 21 o el 26, ahora bien: ¿Cuál?

La respuesta es que no tengo ni idea, quizá dependiendo de como este tu árbol te convenga más usar uno u el otro, quizá te de lo mismo, quizá uno sea la raíz de un árbol enorme que no te conviene reajustar, la verdad es que depende, así que te dejo a que tu eligas como quieras (con una función tuya o al azar o siempre poniendo siempre el mismo-el de la derecha o el de la izquierda- o lo que tu quieras) .

…Pongamos otro ejemplo, ahora con la raíz, el 53, si quisiéramos eliminarlo tenemos dos opciones.

BSTs.png

¡Es por eso que esto es tan difícil, porque no hay un camino «correcto» pero bueno, explicado este texto enorme continuamos…Ya elegimos uno pero ¿Ahora qué?

Camino 3A(Queremos que en donde estaba nuestro nodo este algo más grande):

  1. Si quieres eso tendremos que buscar del nodo en el que estamos, de su subarbol derecho el que tenga el valor mínimo (o dicho de otra forma el que este más a la izquierda)
  2. Una vez que lo encuentres lo colocas donde estaba el nodo que querías eliminar y ahora eliminas recursivamente el nodo que acabas de encontrar

Camino 3B(Queremos que en donde estaba nuestro nodo este algo más pequeño):

  1. Si quieres eso tendremos que buscar del nodo en el que estamos, de su subarbol izquierdo  el que tenga el valor máximo (o dicho de otra forma el que este más a la derecha)
  2. Una vez que lo encuentres lo colocas donde estaba el nodo que querías eliminar y ahora eliminas recursivamente el nodo que acabas de encontrar

 

 

 

 

 


AVL: La versión Pro

Un Árbol AVL es un BTS muy especial, en el que además que todas las cosas que ya conocemos le agregamos algo mas… Es que se auto balancea.

Decimos que un BTS es un AVL si que la diferencia entre la profundidad de dos nodos cuales quiera no puede ser mas de uno.

AVL

 

 


Rotaciones

 

Hay muchas versiones de las rotaciones, muchos nombre, así que haré mi mejor esfuerzo para mostrarles todas las versiones que hay de las mismas:

La Super Pro

Con estas rotaciones podemos sacar todas las que necesitamos:

SuperRotaciones.png

Las Rotaciones Pro

 

Ahora veamos las Comunes y como las podemos representar usando las que creamos arriba:

Right-Right Rotation (Rotación Derecha)

También la llaman simplemente Right Rotation y es literalmente igual a la que tenemos allá arriba, ¿Puedes verlo? (X y sus hijos son T1 arriba)

 

RightRotation.png

La Clásica Rotación Derecha

Left-Left Rotation (Rotación Izquierda)

También la llaman simplemente Left Rotation y es literalmente igual a la que tenemos allá arriba, ¿Puedes verlo? (Z y sus hijos son T3 arriba)

 

LeftRotation.png

La Clásica Rotación Izquierda

 

 

Right-Left Rotation (Rotación Derecha-Izquierda)

Logramos esto de manera completa así:

RightLeftRotation.png

La Compleja Derecha Izquierda

 

Pero también  lo podemos expresar como:

  1. Primero has una rotación a la Derecha en Hijo derecho de la Raíz
  2. Después has una rotación a la Izquierda en la Raíz

Veámoslo en acción:

 

RightLeftRotationPart1.png

Paso 1: Rotación Derecha en Z

RightLeftRotationPart2.png

Paso 2: Rotación Izquierda en X

Left-Right Rotation (Rotación Izquierda-Derecha)

Logramos esto de manera completa así:

LeftRightRotation.png

La Compleja Izquierda-Derecha

 

Pero también  lo podemos expresar como:

  1. Primero has una rotación a la Izquierda en Hijo Izquierdo de la mañana
  2. Después has una rotación a la Derecha en la Raíz

Veámoslo en acción:

LeftRightRotationPart1.png

Paso 1: Rotación Izquierda en X

LeftRightRotationPart2.png

Paso 2: Rotación Derecha en Z

 

 

 

 

btn1 btn
btn