FabrizioMondo.com

Stavo rileggendo il contenuto del libro di Programmazione 2, e mentre imprecavo sul fatto che questo esame per me sia uno dei soliti drammi, mi cadeva l’occhio su un particolare concetto, l’albero del torneo.

Tempo fa, parlai anche se in modo minimale di alberi e teoria dei grafi.

Mi colpì una frase molto perentoria: << non è possibile atribuire con certezza la seconda posizione in un torneo ad eliminazione diretta senza l’utilizzo della ricorsione >>

Vi chiederete: “ma cosa c’entrano i mondiali in germania con la teoria dei grafi”

C’entra molto. Considerate la fase finale, ovvero i famosi ottavi di finale.. che cosa si viene a creare se non un albero binario?

Quello che andremo a contestare adesso, anche grazie all’ausilio di alcune immagini, è il concetto di attribuzione della graduatoria finale.

Supponiamo di attribuire un coefficiente di “forza” a ciascun concorrente (in questo caso squadra nazionale) partecipante al mondiale. E supponiamo anche (sbagliando, ma dobbiamo supporlo necessariamente) che vinca sempre il piu forte.

Cosa succede se per pura sfortuna, le due squadre con il coefficiente più alto si incontrano ad i quarti di finale? Succede che la seconda squadra più forte del torneo, non solo non prosegue, ma addirittura non le viene neanche attribuito un posto sul podio.

Ecco perchè studieremo un modo per attribuire posizioni in modo non perfetto, ma piu equo, almeno per le prime posizioni.

Partiamo dall’albero completo.. in ogni cerchio è inserito il coefficiente di ciascuna squadra.

Grazie Simo

Da come potete chiaramente vedere, secondo questo albero, 50 è arrivato primo, 46 è arrivato secondo. In realtà, se si fossero incontrati 48 (eliminato ai quarti) e 46 (finalista) non avrebbe certo vinto 46.

Allora ipotizziamo una cosa.

Per potere identificare il concorrente che finisce un torneo come secondo, occorre fare un altro mini torneo a eliminazione diretta, e recuperarne il vincitore. E se i concorrenti da selezionare sono dispari? Bene, in questo caso si sceglie in modo CASUALE (si avete letto bene) un concorrente che salterà 1 partita. Per il resto si rifà tutto come un normale binary tree.

In questo caso il primo ciclo di ricorsione, porta a questo albero, in cui è stato sorteggiato 46 come squadra che salta un turno.

Grazie Simo

A questo punto, abbiamo la sicurezza che la seconda posizione è quella corretta.

Se poi facciamo incontrare anche 46 e 31, otteniamo anche il 3° e 4° posto. Ma qui cominciano i problemi.

Se infatti abbiamo squadre molto forti, mischiate a squadre molto scarse, allora abbiamo incongurenze, difficilmente aggirabili se non con ricorsioni continue e successivi alberi binari, ad esempio in questo caso abbiamo che 31 arriva quarto, ma ci sono ben 3 squadre a coefficiente piu alto che sono in posizioni piu basse.

Come fare allora?

Per quanto riguarda i mondiali, diviene sufficiente fermarsi al primo ciclo di ricorsione e valutare oggettivamente solo i primi 3 classificati, altrimenti dobbiamo fare delle altre ipotesi, perchè noi in questo momento lavoriamo con numeri, ma in realtà nessuno sa a priori se una squadra è piu forte di un altra.. e dobbiamo cercare di mantenere l’ordine corretto, anche senza questa informazione.

Risulta chiaro ai più che questa macchinazione mentale altro non è che l’esecuzione di un algoritmo di ordinamento, a tale si riconduce, e come ben sappiamo essi hanno complessità quasi lineare. Il nostro operatore di confronto è la partita.

Credo quindi che sia impossibile potere ordinare completamente e correttamente delle squadre in base alle prestazioni agonistiche, sia in caso di ipotesi teoriche che reali.

Chi sarà stata allora la squadra che avrebbe dovuto prendere il secondo posto ai mondiali di Germania 2006, la Francia, la Germania o l’Ucraina o l’Australia? Ai posteri l’ardua sentenza.