mai sentito parlare dell\' ALGORITMO DI BERGER per la creazione di tornei singoli o a squadre?
<BR>
<BR>ki d voi è in grado d darmene una rapida (per modo d dire) esposizione???
<BR>
<BR>ps: ho cercato il (im)possibile su internet,ma nn ho trovato nulla. magari sono fortunato e in un qualke vostro libro.....
<BR>
<BR>ps2: se nn lo trovate in nessun libro e volete dilettarvi (ve lo sconsiglio caldamente) col provarci, posso passare tutte le specifiche necessarie!!!
<BR>
<BR>ciao <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif">
IMPORTANTISSIMO
Moderatore: tutor
magari se invece di \"importantissimo\" avessi messo nel topic \"algoritmo di berger\", o simili, avresti reso più immediato trovare il tuo post, per chi fosse esperto/interessato, che magari non lo vedrà, perso nell\'elenco dei messaggi, ed evitato di attirare tanti a cui poteva interessare meno (niente)
_k_
serve (almeno a me) a creare (ed implementare in un linguaggio d programmazione) un algoritmo per la gestione dei tornei all\'italiana (come il campionato d calcio,però solo andata,con un numero N d squadre pari e un numero d turni T (date in cui si gioca) = N-1)
<BR>
<BR>nn penso centrino i grafi e/o la combinatoria,però .....<BR><BR>[ Questo Messaggio è stato Modificato da: Athos il 09-06-2004 20:46 ]
<BR>
<BR>nn penso centrino i grafi e/o la combinatoria,però .....<BR><BR>[ Questo Messaggio è stato Modificato da: Athos il 09-06-2004 20:46 ]
-
Antimateria
- Messaggi: 651
- Iscritto il: 01 gen 1970, 01:00
- Località: Vergate sul Membro
-
Antimateria
- Messaggi: 651
- Iscritto il: 01 gen 1970, 01:00
- Località: Vergate sul Membro
Hm...
<BR>
<BR>Sono appassionato di tornei all\'Italiana, e ho anche progettato per la mia ditta un software (in Java) per la creazione di calendari, che utilizza credo il più famoso algoritmo di generazione automatica di tornei.
<BR>
<BR>Non conosco però l\'algoritmo di Berger per la CREAZIONE di tornei all\'Italiana. Che io sappia, esiste l\'algoritmo di Sonneborn-Berger per risolvere le parità al termine di un torneo (un\'alternativa alla classifica avulsa per intenderci)
<BR>
<BR>Non è che puoi essere più specifico nella tua richiesta, ad esempio riassumendo le specifiche ricevute riguardanti questo \"algoritmo di Berger\"?
<BR>
<BR>
<BR>Sono appassionato di tornei all\'Italiana, e ho anche progettato per la mia ditta un software (in Java) per la creazione di calendari, che utilizza credo il più famoso algoritmo di generazione automatica di tornei.
<BR>
<BR>Non conosco però l\'algoritmo di Berger per la CREAZIONE di tornei all\'Italiana. Che io sappia, esiste l\'algoritmo di Sonneborn-Berger per risolvere le parità al termine di un torneo (un\'alternativa alla classifica avulsa per intenderci)
<BR>
<BR>Non è che puoi essere più specifico nella tua richiesta, ad esempio riassumendo le specifiche ricevute riguardanti questo \"algoritmo di Berger\"?
<BR>
le unike specifike ke ho sono quelle ke ho già scritto precedentemente
<BR>
<BR>fonti attendibili parlano di una matrice 2 x N/2 (ecco xkè N deve essere pari) i cui elementi si fanno ruotare un numero T (d turni) d volte di una posizione.ade eccezione d uno ke rimane fisso (ho scoperto tutto ciò proprio oggi <IMG SRC="images/forum/icons/icon_smile.gif">)
<BR>
<BR>sapendo questo l\'implementazione viene da se!
<BR>
<BR>tu come lo hai fatto?
<BR>
<BR>fonti attendibili parlano di una matrice 2 x N/2 (ecco xkè N deve essere pari) i cui elementi si fanno ruotare un numero T (d turni) d volte di una posizione.ade eccezione d uno ke rimane fisso (ho scoperto tutto ciò proprio oggi <IMG SRC="images/forum/icons/icon_smile.gif">)
<BR>
<BR>sapendo questo l\'implementazione viene da se!
<BR>
<BR>tu come lo hai fatto?
Esattamente così. <IMG SRC="images/forum/icons/icon_wink.gif"> Non l\'ho mai sentito chiamare \"Algoritmo di Berger\".
<BR>
<BR>In più, ho applicato diverse varianti per soddisfare i vincoli posti dalla nostra mandante; la principale variante è che non mi vincolo a uno spostamento di 1 passo per turno, ma di <!-- BBCode Start --><I>m</I><!-- BBCode End --> passi, purché ... (<!-- BBCode Start --><B>esercizio: trovare i valori di <!-- BBCode Start --><I>m</I><!-- BBCode End --> che soddisfano i vincoli del torneo all\'Italiana, e dimostrare che il calendario ottenuto con un passo <!-- BBCode Start --><I>m</I><!-- BBCode End --> valido è una permutazione dei turni ottenuti con il passo 1</B><!-- BBCode End -->).
<BR>
<BR>L\'algoritmo di Berger è l\'illustrazione pratica di un teorema di teoria degli anelli. Prendendo un numero di squadre <!-- BBCode Start --><I>N</I><!-- BBCode End --> dispari, numerando le squadre e i turni da 0 a <!-- BBCode Start --><I>N - 1</I><!-- BBCode End -->, allora la squadra <!-- BBCode Start --><I>a</I><!-- BBCode End --> al turno <!-- BBCode Start --><I>t</I><!-- BBCode End --> incontra l\'unica squadra <!-- BBCode Start --><I>x</I><!-- BBCode End --> che risolve questa equazione:
<BR>
<BR><!-- BBCode Start --><I>a + x = t (mod N)</I><!-- BBCode End -->
<BR>
<BR>Qualora <!-- BBCode Start --><I>x</I><!-- BBCode End --> fosse uguale ad <!-- BBCode Start --><I>a</I><!-- BBCode End --> (e per ogni <!-- BBCode Start --><I>t</I><!-- BBCode End --> esiste un unico <!-- BBCode Start --><I>a</I><!-- BBCode End --> per cui <!-- BBCode Start --><I>a + a = t (mod N)</I><!-- BBCode End -->), allora la squadra <!-- BBCode Start --><I>a</I><!-- BBCode End --> \"riposa\" in quel turno. <!-- BBCode Start --><B>Per dimostrare che questo è un calendario valido, occorre dimostrare che per ogni coppia <!-- BBCode Start --><I>a, b</I><!-- BBCode End --> esiste un turno <!-- BBCode Start --><I>t</I><!-- BBCode End --> in cui si incontrano</B><!-- BBCode End -->.
<BR>
<BR>Se il numero di squadre è <!-- BBCode Start --><I>N + 1</I><!-- BBCode End --> pari, allora componi un calendario per le squadre da <!-- BBCode Start --><I>0</I><!-- BBCode End --> a <!-- BBCode Start --><I>N - 1</I><!-- BBCode End --> come prima, e per ogni turno <!-- BBCode Start --><I>t</I><!-- BBCode End --> fai incontrare la squadra <!-- BBCode Start --><I>N</I><!-- BBCode End --> con la squadra che riposa. <!-- BBCode Start --><B>Per dimostrare che anche questo è un calendario valido, occorre dimostrare che per ogni squadra <!-- BBCode Start --><I>a</I><!-- BBCode End --> esiste un turno <!-- BBCode Start --><I>t</I><!-- BBCode End --> in cui la squadra riposa.</B><!-- BBCode End -->
<BR>
<BR>Se visualizzi il tutto come una matrice <!-- BBCode Start --><I>(N + 1)/2 x 2</I><!-- BBCode End -->, allora ottieni l\'algoritmo di Berger, dove la squadra <!-- BBCode Start --><I>N</I><!-- BBCode End --> è la squadra che non si sposta.
<BR>
<BR>Bene, ho lanciato un po\' di sassi, vediamo chi li raccoglie.<BR><BR>[ Questo Messaggio è stato Modificato da: achillu il 10-06-2004 12:35 ]
<BR>
<BR>In più, ho applicato diverse varianti per soddisfare i vincoli posti dalla nostra mandante; la principale variante è che non mi vincolo a uno spostamento di 1 passo per turno, ma di <!-- BBCode Start --><I>m</I><!-- BBCode End --> passi, purché ... (<!-- BBCode Start --><B>esercizio: trovare i valori di <!-- BBCode Start --><I>m</I><!-- BBCode End --> che soddisfano i vincoli del torneo all\'Italiana, e dimostrare che il calendario ottenuto con un passo <!-- BBCode Start --><I>m</I><!-- BBCode End --> valido è una permutazione dei turni ottenuti con il passo 1</B><!-- BBCode End -->).
<BR>
<BR>L\'algoritmo di Berger è l\'illustrazione pratica di un teorema di teoria degli anelli. Prendendo un numero di squadre <!-- BBCode Start --><I>N</I><!-- BBCode End --> dispari, numerando le squadre e i turni da 0 a <!-- BBCode Start --><I>N - 1</I><!-- BBCode End -->, allora la squadra <!-- BBCode Start --><I>a</I><!-- BBCode End --> al turno <!-- BBCode Start --><I>t</I><!-- BBCode End --> incontra l\'unica squadra <!-- BBCode Start --><I>x</I><!-- BBCode End --> che risolve questa equazione:
<BR>
<BR><!-- BBCode Start --><I>a + x = t (mod N)</I><!-- BBCode End -->
<BR>
<BR>Qualora <!-- BBCode Start --><I>x</I><!-- BBCode End --> fosse uguale ad <!-- BBCode Start --><I>a</I><!-- BBCode End --> (e per ogni <!-- BBCode Start --><I>t</I><!-- BBCode End --> esiste un unico <!-- BBCode Start --><I>a</I><!-- BBCode End --> per cui <!-- BBCode Start --><I>a + a = t (mod N)</I><!-- BBCode End -->), allora la squadra <!-- BBCode Start --><I>a</I><!-- BBCode End --> \"riposa\" in quel turno. <!-- BBCode Start --><B>Per dimostrare che questo è un calendario valido, occorre dimostrare che per ogni coppia <!-- BBCode Start --><I>a, b</I><!-- BBCode End --> esiste un turno <!-- BBCode Start --><I>t</I><!-- BBCode End --> in cui si incontrano</B><!-- BBCode End -->.
<BR>
<BR>Se il numero di squadre è <!-- BBCode Start --><I>N + 1</I><!-- BBCode End --> pari, allora componi un calendario per le squadre da <!-- BBCode Start --><I>0</I><!-- BBCode End --> a <!-- BBCode Start --><I>N - 1</I><!-- BBCode End --> come prima, e per ogni turno <!-- BBCode Start --><I>t</I><!-- BBCode End --> fai incontrare la squadra <!-- BBCode Start --><I>N</I><!-- BBCode End --> con la squadra che riposa. <!-- BBCode Start --><B>Per dimostrare che anche questo è un calendario valido, occorre dimostrare che per ogni squadra <!-- BBCode Start --><I>a</I><!-- BBCode End --> esiste un turno <!-- BBCode Start --><I>t</I><!-- BBCode End --> in cui la squadra riposa.</B><!-- BBCode End -->
<BR>
<BR>Se visualizzi il tutto come una matrice <!-- BBCode Start --><I>(N + 1)/2 x 2</I><!-- BBCode End -->, allora ottieni l\'algoritmo di Berger, dove la squadra <!-- BBCode Start --><I>N</I><!-- BBCode End --> è la squadra che non si sposta.
<BR>
<BR>Bene, ho lanciato un po\' di sassi, vediamo chi li raccoglie.<BR><BR>[ Questo Messaggio è stato Modificato da: achillu il 10-06-2004 12:35 ]