El comptador i tu, Ada

29/07/2016

Alhora que el Parlament s'ha posat les piles i ha decidit continuar amb el procés segons el pla previst en el programa electoral sobiranista (s'han aprovat les conclusions de la comissió del Procés Constituent, que projecten tres lleis "de desconnexió": això volarà, a partir d'ara, nena…) l'ajuntament de Barcelona posa un comptador de morts a la Mediterrània per culpa de la crisi dels refugiats.

Vull posar les dues realitats l'una al costat de l'altra. Es complementen molt bé i ens ajuden a saber què volem fer amb les misèries que hem d'arrossegar com a societat. El Parlament es posiciona i actua, més enllà de la legalitat "espanyola", per mirar de fer l'estat propi que posi remei als nostres problemes; l'ajuntament de Colau en fa un espectacle. Colau contraposada a Forcadell.  

No hi ha res més immoral que provar de capitalitzar els morts en benefici del teu programa polític. La senyora Colau podria fer una cosa molt senzilla: suprimir —per exemple— les festes de la Mercè i donar els diners que costen (més de 3,5 milions d'euros) a alguna ONG de les que miren de salvar vides, o crear una flota de salvament, fins i tot. Posats a fer demagògia, fem-la fins al fons, no?

L'ajuntament es gastarà diners en focs d'artifici, mentre podria dedicar-los efectivament a salvar vides humanes, i no només a lamentar cínicament els morts amb un comptador digital (i per què digital? No seria més barat si fos manual?).

Comptar morts és cosificar-los, reduir-los a una xifra indigna, fer del comptador del passeig Marítim un instrument que pretens llançar contra la cara de les institucions polítiques, governades en la majoria de les ocasions per aquells que no són de la teva corda… Imagineu un comptador de morts pel gihadisme a Europa: imagineu que un govern conservador —a Madrid o Hamburg, per exemple— comptés els innocents que han mort per culpa dels terroristes fanàtics islamistes, a Madrid, a Niça, a Londres, a París (ja són milers…): ¿oi que serien titllats d'islamòfobs? Oi que només l'extrema dreta podria caure en aquesta barroeria comptable? 

Una altra pregunta: ¿oi que si Pablo Iglesias fos president de Govern a Madrid —o vicepresident, o ministre— hi continuaria haver-hi morts a la Mediterrània? Però oi que sabem que llavors Ada Colau s'hauria estalviat el comptador de cadàvers? Aquesta pregunta vol fer mal, ho sento. 

Amb això es fa evident que els està usant com a arma política, no com homenatge o record. Veiem, doncs, que els morts de veritat li importen ben poc: el que es valora és la capacitat d'escenificar un moralisme de pa sucat amb oli, d'antisistema amb despatx oficial, de revolucionari que ens vol continuar fent veure que no s'hi pot fer res, mentre resulta que governa una de les institucions més poderoses del —seu— estat espanyol, com és l'ajuntament de Barcelona.


La senyora Colau hi pot fer molt més: té poder i pressupost per fer-ho. Podria efectivament aturar desnonaments, que continuen sent tants com en d'altres èpoques. I si els problemes són tan greus, tan majúsculs: ¿per què celebrar les festes municipals? Per un costat es fa el discurs apocalíptic, per l'altra el concert de rock i la botifarrada popular. No ho entenc. ¿Vostè sí? ¿Per què ens deixem entabanar d'aquesta manera?   

A més, la senyora Colau hauria pogut tacar el CIE, però no ha tingut el coratge per desobeir i plantar cara, que sí que ha tingut el Parlament, amb la seva presidenta al capdavant. Hi ha revolucionaris que ho són fins que toca posar-se realment les piles i actuar; hi ha un conformisme de la pancarta molt còmode i conformista, i de llagrimeta fàcil, que no pot deixar de fer evident que sovint cal amollar la pancarta, però, i posar-se a fer feina, encara que s'hagi d'anar a la confrontació si és que realment —realment!, de veritat!— vol mirar de solucionar els problemes que fas veure que et fan saltar les llàgrimes. El sentimentalisme sobiranista —que m'ha fet llàstima, en alguns moments, ha estat patètic…— s'està traduint en fets, en accions, en oposició a la brava a les sòrdides limitacions de la llei: ¿pot dir el mateix el sentimentalisme revolucionari «de tota la vida»? No.

Colau podria fer més, podria (reitero) salvar vides —¿quantes vides es poden salvar amb el que es dedicarà a focs d'artifici o pregons idiotes —estupidíssims i innecessaris— durant les festes de la Mercè?

Podria posicionar-se per l'estat propi com ho ha fet el Parlament jugant-s'hi el coll —perquè estic segur que els enjudiciaran i multaran, als nostres diputats—. Però no: prefereix el comptador, el moralisme de tieta que es queixa dels desastres del món des de la taula "camilla", amb el braser de pinyolada vora els peus i la bandera anarquista a la paret, vora l'estampa del Guernica que va heretar de l'avi. Oi tant. 

Hi ha un tipus de revolucionari que fa molta pena. Són aquella gent de «Volem referèndum legal i acordat», però amb la samarreta del Che ben planxada, sota l'americana de lli. Revolucionaris «dins d'un ordre», que els acaba fent tan conservadors com el PP —jo diria que més, perquè el PP tot ho destrossa…—, però més còmics, perquè en el PP no hi ha tanta hipocresia. Els del PP són tan barroers que no enganyen a ningú, encara que es posin el Lacoste a l'inrevés i facin amb el fixador de cabells formes de serrell d'avantguarda. Ens estan prenen el pèl, i sense excuses. I a sobre menteixen, perquè van en contra no només de tots els seus programes electorals sinó de totes les proclames que han fet des que tenen ús de raó. Entre fer història amb el catalanisme o fer la viu-viu a l'ombra de les institucions de la vella Espanya prefereixen ser cua d'arengada que cap de llamàntol. I tot perquè a la cau d'arengada la xuclen ells…

Vull —acabo, que perdo l'avió i marxo de vacances—, des d'aquesta modestíssima columna, agrair la determinació i el coratge dels nostres diputats, que han fet un gest d'una valentia inèdita. Les respostes seran fosques, la tensió es farà irrespirable, però sembla que el sobiranisme no s'arronsarà, que plantarà cara, que sabrà fer allò que deien que farien "els revolucionaris de tota la vida", que tanmateix s'ho miraran des de la barrera, fent veure que el problema és un altre mentre proven de col·locar la cunyada o de canviar de discurs, no sigui que —quan toqui— el sobiranisme realment guanyi i llavors no s'haurà de perdre pistonada.

Perquè d'una cosa n'estic segur: si el sobiranisme guanya llavors seran els primers en canviar-se la camisa, i en mirar de capitalitzar tots els triomfs, fent veure que ells van ser els herois de fons d'aquesta lluita, «sense nosaltres això no existiria», diran. I no faltaran a l'11-S, perquè han d'estar allà on puguin pescar ingenus. Porten cent anys enganyant la gent amb el mateix tripijoc. En fi. Llavors, si tot surt bé, sí que els comptarem a ells, i tindrem memòria, i —ai— els haurem de disculpar, mostrant aquella generositat que ara ells no tenen. Salut i bon estiu. Jo m'acomiado fins el setembre. Alegria, senyores, i etc. Les vacances sense paga dels pobres autònoms. Adéu.

Algorisme de Dijkstra

Algorisme de Dijkstra

L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme per a la determinació del camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta. El seu nom serà el Edsger Dijkstra, qui el va descriure per primera vegada el 1959.

La idea subjacent en aquest algorisme consisteix a anar explorant tots els camins més curts que parteixen del vèrtex origen i que porten a tots els altres vèrtexs, quan s'obté el camí més curt des del vèrtex origen, a la resta de vèrtexs que formen el graf, l'algorisme s'atura. L'algorisme és una especialització de la cerca de cost uniforme, i com a tal, no funciona en grafs amb arestes de cost negatiu (l'hora de triar sempre el node amb distància menor, poden quedar exclosos de la cerca nodes que en properes iteracions baixarien el cost general del camí al passar per una aresta amb cost negatiu).

Algoritme
Tenint un graf dirigit ponderat de N nodes no aïllats, sigui X el node inicial, un vector D de mida N contindrà al final de l'algorisme les distàncies des de X a la resta dels nodes.

Inicialitzar totes les distàncies en D amb un valor infinit (o màxim), ja que són desconegudes al principi, exceptuant la de X que s'ha de posar a 0 (ja que la distància de X a X és 0).
Sigui a = X ( a serà el node actual).
Recorrem tots els nodes adjacents de a, excepte els nodes marcats com a visitats, anomenarem a aquests v i .
Si la distància des de X fins v i guardada a D és més gran que la distància des de X fins a sumada a la distància des de a fins v i , aquesta se substitueix amb la segona nomenada, és a dir:
si (D i > D a +d (a, v i )) llavors D < sub> i = D a +d (a, v i )
Marquem com a visitats el node a .
Prenem com a pròxim node actual el de menys valor en D (pot fer-se emmagatzemant els valors en una cua de prioritat) i tornem al pas 3 mentre existeixin nodes no visitats.
Un cop acabat l'algorisme, D estarà completament ple.

Complexitat
Ordre de complexitat de l'algorisme: O (| V | 2 +|E|) = O (| V | 2 ) sense utilitzar cua de prioritat, O ((| L |+| V |) log| V |) utilitzant cua de prioritat (per exemple un turó).

Podem estimar la complexitat computacional de l'algorisme de Dijkstra (en termes de sumes i comparacions). L'algorisme realitza al més n-1 iteracions, ja que en cada iteració s'afegeix un vèrtex al conjunt distingit. Per estimar el nombre total d'operacions només cal estimar el nombre d'operacions que es duen a terme en cada iteració. Podem identificar el vèrtex amb la menor etiqueta entre els que no estan a S k realitzant n-1 comparacions o menys. Després fem una suma i una comparació per actualitzar l'etiqueta de cada un dels vèrtexs que no estan a S k . Per tant, en cada iteració es fan com a molt 2 (n-1) operacions, ja que no pot haver més de n-1 etiquetes per actualitzar a cada iteració. Com que no es realitzen més de n-1 iteracions, cadascuna de les quals suposa al més 2 (n-1) operacions, arribem al següent teorema.

TEOREMA:  L'Algorisme de Dijkstra realitza O (n  2 ) operacions (sumes i comparacions) per determinar la longitud del camí més curt entre dos vèrtexs d'un graf ponderat simple, connex i no dirigit amb n vèrtexs.

Psedocodi
Estructura de dades auxiliar:
Q = Estructura de dades Cua de prioritat (es pot implementar amb un turó)
Dijkstra (Graf G, node_font s )
for  o ∈ V [G]  do distància [ o ] = INFINIT
pare [ o ] = NULL distància [ s ] = 0
Encolar (cua, graf) mentre cua no és buida do o = extraer_minimo (cua)
for  v ∈ adjacència [ o ] do
if distància [ v ]> distància [ o ]+pes (u, v) do distància [ v ] = distància [ o ]+pes (u, v) pare [ v ] = o

Una altra versió en pseudocodi sense cua de prioritat.
Funció Dijkstra (Graf G, node_sortida s)
// farem servir un vector per a guardar les distàncies del node sortida a la resta
int distància[n] // inicialitzats el vector amb distàncies inicials
bool vist[n] // vector de booleans per controlar els vèrtexs dels que ja tenim la distància mínima
per a cada w ∈ V [G] fer
si (no hi ha aresta entre ells i w) llavors
distància[w] = Infinit // pots marcar la casella amb un -1 per exemple
sinó
distància[w] = pes(s, w)
fsi
fper
distància[s] = 0
vist[s] = cert
// n és el nombre de vèrtexs que té el Graf
mentre (quedin nodes per visitar) fer
vèrtex = agafar el mínim del vector distància i que no estigui visitat;
vist[vèrtex] = cert;
per a cada w ∈ successors(G, vèrtex) fer
si distància[w] > distància[vèrtex] + pes(vèrtex, w) llavors
distància[w] = distància[vèrtex] + pes(vèrtex, w)
fsi
fper
fmentre
ffunció
Al final tenim en el vector distància en cada posició la distància mínima del ertex sortida a un altre ertex qualsevol.

C++
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

int destí, origen, vèrtexs = 0;
int * costos = NULL;

void Dijkstra (int vèrtexs, int origen, int destinació, int * costos){
int i, v, cont = 0;
int * ant, * tmp;
int * z;/* vèrtexs per als quals es coneix el camí mínim */
double min;
double * dist = new double [vèrtexs];/* vector amb els costos de dos camins */

/* Aloc les línies de la matriu */
ant = new int [vèrtexs];
tmp = new int [vèrtexs];
z = new int [vèrtexs];

for (i = 0; i <vèrtexs; i++){
if (costos [(origen - 1) * vèrtexs+i] ! =- 1){
ant [i] = origen - 1;
dist [i] = costos [(origen-1) * vèrtexs+i];
}
else{
ant [i] = -1;
dist [i] = HUGE_VAL;
}
z [i] = 0;
}
z [origen-1] = 1;
dist [origen-1] = 0;

/* Bucle principal */
do{

/* Trobant el vèrtex que ha d'entrar a z */
min = HUGE_VAL;
for (i = 0; i <vèrtexs; i++)
if (! z [i])
if (dist [i]> = 0 & & dist [i] <min){
min = dist [i]; v = i;
}

/* Calculant les distàncies dels nodes veïns de z */
if (min ! = HUGE_VAL & & v ! = destinació - 1){
z [v] = 1;
for (i = 0; i <vèrtexs; i++)
if (! z [i]){
if (costos [v * vèrtexs+i] ! = -1 & & dist [v]+costos [v * vèrtexs+i] <dist [i]){
dist [i] = dist [v]+costos [v * vèrtexs+i];
ant [i] = v;
}
}
}

}While (v ! = destinació - 1 & & mín ! = HUGE_VAL);

/* Mostra el resultat de la cerca */
cout << "\tde" <<origen << "per a" <<destí << "\t";
if (min == HUGE_VAL){
cout << "No Existeix\n";
cout << "\tCost:\t-\n";
}
else{
i = destí;
i = ant [i-1];
while (i ! = -1){
//Printf ("<-% d ", i+1);
tmp [cont] = i+1;
cont++;
i = ant [i];
}

for (i = cont; i> 0; i -){
cout <<tmp [i-1] << "-->";
}
cout <<destinació;

cout << "\n\tCost:" <<dist [destinació-1] << "\n";
}

delete (dist);
delete (ant);
delete (tmp);
delete (z);
}

int menu (void){
int opció;
cout << "Implementació de l'Algorisme de Dijkstra\n";
cout << "Menu:\n";
cout << ">> 1. Crear el graf\n>> 2. Determinar el menor camí del graf\n>> 0. Sortir del programa\n";
cout <<endl;
cout << "Opció:";
cin>> opció;
while (opció <0||opcio> 2){
cout << "Opció Invalida. Digitela novament:";
cin>> opció;
}
return opció;
}

void add (void){

do{
cout << "\nIntrodueixi el nombre de vèrtexs (no mínim de 2):";
cin>> vèrtexs;
}While (vèrtexs <2);

if (! costos)
delete (costos);

costos = new int [vèrtexs * vèrtexs];

for (int i = 0; i <= vèrtexs * vèrtexs; i++)
costos [i] = -1;

cout << "N º Vertices =" <<vèrtexs <<endl;
cout << "Ara unim els vèrtexs:\n";

bool segueixo = true;

int origen;
int destinació;

while (segueixo){
cout << "Escolliu el primer vèrtex de l'aresta:" <<endl;
do{
cin>> origen;

if (origen> vertices){
cout << "El nombre del vèrtex ha de ser menor de" <<vèrtexs <<endl;
}
}while (origen> vertices);

cout << "Escolliu el segon vèrtex de l'aresta:" <<endl;
do{
cin>> destinació;

if (destinació> vertices){
cout << "El nombre de vèrtex ha de ser menor de" <<vèrtexs <<endl;
}
}while (destinació> vertices);

int pes = 0;
cout << "Pes:" <<endl;
cin>> pes;

costos [(origen-1) * vèrtexs+destinació - 1] = pes;
costos [(destinació-1) * vèrtexs+origen - 1] = pes;

int seguir = 1;
cout << "Voleu afegir una altra aresta? (0 - NO, 1 - SI, per defecte 1):";
cin>> seguir;
segueixo = (seguir == 1);
}

}

void cercar (void){
int i, j;

cout << "Llista dels Menors Camins a Graf Atès:\n";

for (i = 1; i <= vèrtexs; i++){
for (j = 1; j <= vèrtexs; j++)
Dijkstra (vèrtexs, i, j, costos);
cout <<endl;
}

cout << "<Premeu ENTER per tornar al menú principal.\n";

}

int main (int argc, char ** argv){
int opció;

do{
opcion = menu ();
switch (opció){
case 1:
add ();
break;
case 2:
cercar ();
break;
}

}While (opció ! = 0);
delete (costos);

cout << "\nFins la proxima ...\n\n";
system ( "pause");

return 0;
}

C++mitjançant Heaps
Una altra possible implementació de l'algorisme de Dijkstra és mitjançant monticles binaris.

struct T_Heap{
A turo;
int num_elem;
};

void CrearHeap (T_Heap & heap){
heap.num_elem = 0;
for (int i = 0; i <MAX_HEAP; i++){
heap.monticulo [i] = NULL;
}//for
}
void Intercanviar (T_Heap & heap, int i, int j){
T_Lista aux;

aux = heap.monticulo [i];
heap.monticulo [i] = heap.monticulo [j];
heap.monticulo [j] = aux;
}
void Meter (T_Heap & heap, const T_Lista & elem){
int k;

k = heap.num_elem;
heap.monticulo [k] = elem;
while (k ! = 0||(heap.monticulo [k] --> pes> heap.monticulo [((k-1)/2)] --> pes){
Intercanviar (heap, k, ((k-1)/2));
k = (k-1)/2;
}//while
heap.num_elem++;
}
void Treure (T_Heap & heap, int & elem){
int k;

elem = heap.monticulo [0];
heap.monticulo [0] = heap.monticulo [heap.num_elem-1];
heap.monticulo [heap.num_elem-1] = NULL;
heap.num_elem--;
k = 0;
while (k <heap.num_elem && (heap.monticulo[k]--> pes <heap.monticulo [2 * k+1] --> pes||
heap.monticulo [k] --> pes <heap.monticulo [2 * k+2] --> pes)){
if (heap.monticulo [k] <heap.monticulo [2 * k+1]){
Intercanviar (heap, k, 2 * k+1);
k = 2 * k+1;
}else{
Intercanviar (heap, k, 2 * k+2);
k = 2 * k+2;
}//if
}//while
}
bool HeapLleno (const T_Heap & heap){
return (heap.num_elem == MAX_HEAP);
}
bool HeapVacio (const T_Heap & heap){
return (heap.num_elem == 0);
}
void DestruirHeap (T_Heap & heap){
for (int i = 0; i <MAX_HEAP; i++){
heap.monticulo [i] = NULL;
}//for
heap.num_elem = 0;
}
Aquesta és una implementació de l'algorisme de Dijkstra mitjançant monticles binaris, que és capaç de donar els millors resultats perquè l'algorisme de Johnson sigui més eficient. La implementació de l'algorisme retorna una matriu d'elements precedents i un altre de distàncies, mitjançant el primer es pot seguir el camí de menor cost des del node passat com a argument a qualsevol altre node del graf, i si paral·lelament anem sumant les distàncies de l'altre array, obtenim el cost total d'aquests camins mínims.

void Dijkstra (const T_Grafo & graf, int origen, T_Vector & distàncies, T_Vector & anteriors)
{
T_Vector marcats;
T_Heap colap;
T_Lista aux;

InicializarVector (distàncies);//inicialitza els elements a -1
InicializarVector (anteriors);
InicializarVector (marcats);
distàncies [origen] = 0;
marcats [origen] = 0;
CrearHeap (colap);
MeterAdyacentes (colap, graf, origen, marcats);
while (! HeapVacio (colap){
aux = Treure (colap);
marcats [aux--> origen] = 0;
MeterAdyacentes (colap, graf, aux--> origen, marcats);
while (aux ! = NULL){
if (distàncies [aux--> destí]> (distàncies [aux--> origen]+aux--> pes)){
distàncies [aux--> destí] = distàncies [aux--> origen]+aux--> pes;
pare [aux--> destí] = aux--> origen;
}//if
aux = aux--> seg;
}//while
}//while
}