Creo no haber dicho ninguna incoherencia (como dicen por ahí que no sé de lo que estoy hablando...) pero creo que las matemásticas que nos enseñaron en COU no la invalida el Algebra Lineal que se estudia en Ing. Informática. Vale que las definiciones de combinación lineal e independencia lineal, además de en COU, también sean de la primera página de la asignatura de A.L, pero si ni siquiera haciendo referencia a éstas podeis entender lo que quiero decir, pues no sé, supongo que me tocará definirlas. Tampoco hace falta mucho más para entender el concepto.
Claro, la idea es introducir redundancia en el sistema (hace unas horas estaba hambriento y con sueño y he dicho alguna que otra tontería, lo reconozco xDD), de manera que si una parte se pierde, pueda recuperarse mediante las partes redundantes. Yo, más que discutir si funciona ese sistema de redundancia o no, lo que quería preguntarme era la eficacia del hecho en sí de introducir redundancia en la red, porque para evitar que todo el mundo tuviera los mismos bloques descargados ya se implementó que éstos en lugar de ir enviandose secuencialmente (caso winmx) se enviaran aleatoriamente (caso emule) de esta manera a medida que aumentan las fuentes aumenta la probabilidad de que alguien tenga el bloque que le falta a todo el mundo.
Ahora, la idea de introducir redundancia me parece bastante adecuada, porque sería como disponer de fuentes virtuales (en un principio, aquellas fuentes que no tienen ese bloque en concreto, pueden entregar un "bloque derivado" que previamente poseen, del cual pueda extraerse el bloque original).
La solución de MS es que és realmente sencilla y no sé donde os perdeis, la verdad. En fín, tendremos que ver qué significa que un conjunto de vectores sea linealmente independiente, y que un vector sea combinación lineal de otros vectores. Si puedo trataré explicarlo sin utilizar operaciones matriciales (con las que se puede hacer lo mismo y más sencillo si las entiendes, o símplemente acabar de joderla si no las entiendes).
Para no marear demasiado y sin pérdida de generalidad, supondremos que el fichero se limita a 3 bloques de N bytes cada uno, A, B y C. Cada bloque podemos verlo como un vector de N elementos. Ahora, nos dá igual el número de elementos de cada vector, lo que nos importa son las operaciones que se pueden hacer con cada uno. Suponemos, y es mucho suponer, que no hay desbordamiento en las operaciones de suma de vectores y de multiplicación de un escalar por un vector (vamos, que podemos guardar cualquier número en un byte). Así que podemos sumar vectores, elemento por elemento, y podemos multiplicar todos los elementos de un vector, por un número.
Siendo esto así, tenemos que un vector V, es combinación lineal de, por ejemplo U y W, cuando podemos encontrar números "a" y "b" (los vectores los represento en mayuscula, y los escalares en minúscula) que verifiquen:
V=a*W+b*U.
Ahora imaginemos otro grupo de vectores, por ejemplo X, Y, Z (por seguir el orden del abecedario, no es que quiera usar una base de R3). Estos vectores serán linealmente independientes, si dada la proposición,
a*X+b*Y+c*Z=0 (el vector 0).
esta sólo se cumple para a=0, b=0 y c=0 -> (a,b,c)=(0,0,0).
Entonces, si dentro de un conjunto de 3 vectores, uno de ellos es combinación lineal de los otros, es un conjunto de vectores linealmente independientes? No, porque...
V=a*W+b*U -> a*W+b*U-V=0 -> (a,b,-1) es distinto de (0,0,0) para cualquier valor de a y b (c siempre será distinto de 0).
Volvemos a nuestro ejemplo, con los bloques (vectores) A, B y C. La idea es introducir redundancia. Sin necesidad de conocer el contenido de A,B o C, podemos crear vectores derivados de ellos mediante combinaciones lineales de esos 3 vectores originales. Por ejemplo:
A=1*A+0*B+0*C -> (1,0,0)
B=0*A+1*B+0*C -> (0,1,0)
C=0*A+0*B+1*C -> (0,0,1)
y seguimos...
D=1*A+1*B+1*C -> (1,1,1)
E=1*A-1*B+1*C -> (1,-1,1)
F=1*A+0*B-1*C -> (1,0,-1)
...
En este ejemplo vemos que se han generado 3 vectores adicionales, aunque el número de vectores adicionales que se pueden generar es enorme, dando siempre los valores que uno quiera a los escalares a,b,c para crear un vector derivado que sea combinación lineal de los vectores A,B,C.
X=a*A+b*B+c*C -> (a,b,c).
El objetivo de esto es que al introducir redundancia, solo hace falta tomar 3 vectores de todo el conjunto de vectores (tanto los vectores originales, como los adicionales), para reconstruir el conjunto original. Vamos a cojer D,E y F, aunque podíamos haber cogido A,B, y D, pero la solución sería un poco trivial...
Bueno, tenemos D, E y F, y necesitamos averiguar A,B,C. Además conocemos como cada uno de los vectores D, E y F se relaciona con los vectores A,B,C. Aquí cualquiera que me haya seguido ha visto ahora un sistema de ecuaciones lineales de 3 incógnitas A,B,C (recordamos que 3 es el número de bloques de nuestro fichero) y hay que resolverlo para averiguar esos 3 vectores. (este sistema de ecuaciones, aunque operemos con vectores, se resuelve de la misma manera que un sistema normal de variables reales, porque las operaciones de suma y de multipliación por un escalar, se hacen elemento por elemento).
D=1*A+1*B+1*C
E=1*A-1*B+1*C
F=1*A+0*B-1*C
->D-E=2*B->[B=(D-E)/2]
->(D+F)=2*A+B=2*A+(D-E)/2->[A=(D+F)/2-(D-E)/4]
->A-F=C->[C=(D+F)/2-(D-E)/4-F]
A menos que me haya equivocado al resolver el sistema, esas serían las soluciones para hayar A,B,C a partir de D,E,F.
Bueno, sabemos que hay un método automático para resolver sistemas de ecuaciones de muchas incógnitas, pero cuando resolvemos un sistema de ecuaciones, pueden pasar 3 cosas...
Que el sistema no tenga solución, que la solución sea única, o que existan infinitas soluciones.
Los vectores de las transformaciones lineales de D,E, y F son:
D->(1,1,1)
E->(1,-1,1)
F->(1,0,-1)
Podemos tomar la matriz M=(D,E,F) como la matriz asociada al sistema de ecuaciones. Sabemos, de las matemáticas de COU, que para que un sistema de ecuaciones tenga solución única, el rango de la matriz asociada debe coincidir con el número de incógnitas. Y qué coño es el rango??, el número de vectores linealmente independientes dentro de la matriz. Podemos considerar como sistema global todo el conjunto de vectores (originales y adicionales). Tenemos A->(1,0,0),B->(0,1,0),C->(0,0,1), que evidentemente son linealmente independientes (la única forma de que se cumpla que a*(1,0,0)+b*(0,1,0)+c*(0,0,1)=(0,0,0) es si (a,b,c)=(0,0,0) correcto??). Bueno, pues garantizamos que el sistema no tiene infinitas soluciones, ya que por lo menos hay el mismo número de vectores linealmente independientes que de variables. Ahora bien, cualquier combinación lineal de estos 3 vectores es linealmente dependiente de estos 3 vectores, luego el número máximo de vectores linealmente independientes sigue siendo 3, por lo tanto el sistema tiene solución única, no importa la cantidad de vectores adicionales que incorporemos al sistema siempre que éstos sean combinaciones lineales de esos vectores linealmente independientes.
Pero la idea no es de transmitir todo el conjunto de vectores, sino de transmistir 3 vectores alternativos. En este caso los vectores de D, E, y F son linealmente independientes, porque en caso de que uno de los vectores dependiera de los otros 2 (fuera combinación lineal de éstos), el rango de la matriz asociada al sistema ya no sería 3 sino 2, por lo que el sistema contaría con infintas soluciones, o una solución indeterminada (faltaría información). Esto, por ejemplo, pasaría si tomaramos los vectores de A, C, F.
A=1*A+0*B+0*C -> (1,0,0)
C=0*A+0*B+1*C -> (0,0,1)
F=1*A+0*B-1*C -> (1,0,-1).
Cláramente se vé que F=A-C, es decir-> a*A+b*C+c*F=0, para (a,b,c)=(1,-1,-1), y por lo tanto esos 3 vectores son linealmente dependientes. La consecuencia es que hay una incógnita que no puede despejarse (parece claro que B no interviene para nada, pero en otros casos no es tan obvio), y por lo tanto nos falta información para reconstruir los bloques A,B, y C.
Así que el problema que veo yo, es que el programa P2P de MS, al elegir una alternativa a un bloque mediante otro bloque derivado por combinación lineal, tiene que asegurarse que ese bloque derivado (en concreto el vector de la combinación lineal) siga siendo linealmente independiente con el resto de los vectores, para que el sistema de ecuaciones pueda resolverse (además de tener de operar con aritmética de desbordamiento, con sus limitaciones).
Espero que ahora sí que me haya entendido más gente.
PD: Si hay un método automático (o teorema de A.L) para comprobar que X vectores son linealmente independientes (que seguro que lo hay), entonces el programa P2P de MS tendría la papeleta resuelta, porque sólo sería necesario tener en cuenta los vectores alternativos que fueran linealmente independientes con los que definen los bloques que previamente hemos bajado. Incluso si la diferencia de rangos de las matrices asociadas al sistema no es muy grande, se puede optar por bajar los bloques alternativos necesarios para completar el requisito de solución única del sistema de ecuaciones, aún teniendo que descartar información.
