[ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C.

[dijsktra]

Cuando tienes proyectos sin terminar pero @dijsktra te pica a darle más vueltas a un algoritmo aparentemente sencillo.  

Grandeeee....

...

Código (c) [Seleccionar] Expandir


int upperTriangleDesc(const int **A, const int N){
   size_t i = 1; j = 0; // Declaramos e inicializamos j para poder usarlo en la condicion del bucle externo
   while(i < N && !A[i][j]){
       // El bucle interno no tiene ninguna complicacion
       while(j < i && !A[i][j]){
           ++j;
       }
       // Ahora al salir tenemos dos situaciones:
       // - (j = i) y en tal caso la matriz todavia es triangular superior -> Incrementamos i y restablecemos j a 0 para recorrer otra fila
       // - (A[i][j] != 0) y en tal caso la matriz ya no es triangular superior -> No podemos modificar i ni j para que el bucle de fuera tambien termine
       if(j == i){
           ++i;
           j = 0;
       }
   }
   // Los bucles acaban cuando:
   // Un elemento no es nulo (A[i][j] != 0) -> !triangular
   // Llegamos al final (i == N) -> SI A[N-1][N-2] == 0 ENTONCES triangular SINO !triangular
   return (i == N && !A[N-1][N-2]);
}

Chavalote! Este no te lo puedo bendecir... Tiene un sutil fallo. Te digo cual?
Prueba a evaluar la matriz de 1 fila y 1 columna...
El resultado es indeterminado... porque entonces accedes a una posicion tal como A[0][-1]  . Si acierta, dependera del compilador, o de la conjunci'on de los astros...
Que pasa? que las matrices de 1 fila y 1 columna no son matrices???  Prueba [[1]]!  

Podemos ver que esto se complica mucho y solo para quitar una variable local. Así que tenía que haber otra solución.

Ese es el punto... Que tenemos que hacerlo sencillo. Pero claro, con lo bien que lo hiciste al principio, cacda vez queda menos margen...

...

Código (c) [Seleccionar] Expandir


int upperTriangleDesc(const int **A, const int N){
   size_t i = 1, j = 0;
   while(i < N && !j){
       while(j < i && !A[i][j]){
           ++j;
       }
       // Al salir: SI j < i ENTONCES A[i][j] != 0 SINO SI A[i][j-1] == 0 ENTONCES triangular (de momento) SINO !triangular
       j = (j < i) || A[i][j-1];
       ++i;
   }
   // Triangular <-> j = 0
   return !j;
}

A ver qué tal esta vez.  

 Bravo... Correcta... pero aun redundante... ya que en

Código (c) [Seleccionar] Expandir


j=(j<i)||A[i][j-1]

es equivalente a

Código (c) [Seleccionar] Expandir


j=(j<i)

En ese punto. N>i>0 siempre. ya que 1<=i<=N (desde el principio 1==1, y siempre aumenta... y por meterse en el primer bucle i<N.
(Si has llegado a j==i, es porque todos los anteriores son 0, en particular, A[j-1]. luego es "por el momento triangular", lo que tu registras poniendo j=0.Si no llegas, a j==i es porque A[j] es distinto de 0, y tu la marcas a 1, "diciendo que no es triangular". Por evaluacion en cortocircuito, no se evalua A[j-1]...

Y como tu dices, se ha hecho mas "compleja de leer" ya que...j

• Unas veces marca el indice de la columna 0<=j<N A[j] (while)
• Otras veces marca un predicado booleano {0,1} para saber si es triangular "pr el momento" j=(j<i)||A[j-1]

Pongo ya mi solucion en el mensaje abajo, para no repetir, en respuesta a fary

[dijsktra]

Estamos ansiosos de ver tu código dijsktra   ¿Para qué retrasarlo más?  

Allá va... Se aceptan criticas...

Con el buen trabajo que hicisteis al principio, había poco margen... De hecho, la tuya es muy dificil de superar, pero no es estructurada... tiene "saltos"... Y el heroe del cual tomo el pseudonimo, dijsktra, maldecia la programación "con saltos"... Esto podia hacer el software muy complejo de mantener, por lo menos en algoritmia, no en programacion de sistemas.

Lo que no todo el mundo sabe es que, sin cuidado, - sin la técnica de derivación- y sin un buen lenguaje -C no es el mejor para la algoritmia, porque le faltan asignaciones multiples y comandos guardados...- la programacion estructurada puede ser tan dificil de mantener ( o mas) que la no estructurada. Aunque en general, siguiendo las directrices de dijsktra (el original, no yo)  es m'as fácil.


La formalizacion que permite demostrarlo rigorusamente esta descrita en comnetarios, pero eso es para cursos avanzados.. Lo dejo para la posteridad que lo quiera conusltar en Internet...

Propongo dos versiones.. Va la primera...

Código (c) [Seleccionar] Expandir


int upperTriangleDesc(const int **A,
     const int N)
{
 int i,j;
 for (i=1,j=0;i<N && j==i-1; i++)
   for(j=0; (j<i) && !A[i][j];j++);
 return j==i-1 ;
}

// Outer loop
// I1: Q[N/i] and 1<=i<=M, 0<=j<i and ((j<i-1) -> A[i-1][j]!=0)
// Q1: i = min n : 1 <= n <=N and (n<N->(j<n-1 && ->A[n-1][j]!=0))): n nad
//     j = min m : 0 <= m < i and (m<i-1 -> A[i-1][m]!=0))): m
// Quote1(N-i)>=0
// Inner loop
// I2: Q2[N/j] and 0 <= j <= i and i < N
// Q2: i<N and j = min m : 0 <= m <=i and (m<i -> A[i][m]!=0): m
// Quote2(N-j)>=0


Grosso modo, la idea es la siguiente...
Al principio, al final y entre vueltas del bucle externo, si j<i-1 entonces sabemos que hemos encontradoun elemento A[i-1][j] distingo de 0, en la zona prohibida... Es un invariante... Y acabamos si hemos llegado a i==N en el caso peor... luego en las anteriores a N, no lo encontrarmos... Aun en i==N podria ser, por loq eu evaluamos j==i-1 en el return... Es como una piedra en el calzado esa utlima linea...es lo que le perdio a
YreX-DwX .  Aun asi, se puede apreciar como los indices i,j se modifican naturalmente, con i++,j++

La segunda, mi favorita...

Código (c) [Seleccionar] Expandir


int upperTriangleDesc(const int **A,
     const int N)
{
 int i,j;
 for (i=1,j=0;i<N && !j; i+=!j)
   for(j=i; j && !A[i][j-1];j--);
 return i==N;
}

// Outer loop
// I1: Q[N/i] and 1<=i<=N, 0<=j<=i and ((j>0) -> (i<N and A[i][j-1]!=0))
// Q1: i = min n : 1 <= n <=N and (n<N->(j>0 && ->A[n][j-1]!=0))): n nad
//     j = max m : 0 <= m <= i and (m>0 -> i<N && A[i][m-1]!=0))): m
// Quote1(N-i-j)>=0
// Inner loop
// I2: Q2[N/j] and i<N and 0 <= j <= i
// Q2: i<N and j = max m : 0 <= m <=i and (m>0 -> A[i][m-1]!=0): m
// Quote2(N-j)>=0

En esta version, tenemos la fortuna de parar en la primera linea en la que hayamos encontrado el elemento no valido, que resultara estar en A(i)[j-1] si j>0 (Es un invariante)...
O en N, si no lo encontramos...Pero el cambio no es gratuiro.. el avance de i es condicional, i.e. i+=!j

Saludos...Cuidaos del COVID...!

[K-YreX]

Chavalote! Este no te lo puedo bendecir... Tiene un sutil fallo. Te digo cual?
Prueba a evaluar la matriz de 1 fila y 1 columna...
El resultado es indeterminado... porque entonces accedes a una posicion tal como A[0][-1]  . Si acierta, dependera del compilador, o de la conjunci'on de los astros...
Que pasa? que las matrices de 1 fila y 1 columna no son matrices???  Prueba [[1]]!  

Es cierto. No me di cuenta de eso en su momento. Habría que tratar las matrices de orden 1 como un caso aparte:

Código (c) [Seleccionar] Expandir

return (N == 1 || (i == N && !A[N-1][N-2]));
Aunque claramente no es la mejor solución...

 Bravo... Correcta... pero aun redundante... ya que en

Código (c) [Seleccionar] Expandir

j=(j<i)||A[i][j-1]
es equivalente a

Código (c) [Seleccionar] Expandir

j=(j<i)

El problema fue que me centré en usar A(i, j-1) y entonces comprobé que no era condición suficiente y le añadí el (j < i) pero no vi que ésta sí era suficiente por sí sola... 
Bueno, me quedo con que me he quedado cerca... Este era el de calentamiento, no?

[fary]

dijsktra deberías de poner mas retos como este