[C] : Linguaggi

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Avatar utente
Catraga
Messaggi: 302
Iscritto il: 01 gen 1970, 01:00
Località: Trieste (Univ)

Messaggio da Catraga » 01 gen 1970, 01:33

Sia A={a,b}, una parola di lungezza n su A e\' una successione di n elementi di a; ad esempio abaabb e\' una parola di lunghezza 6.
<BR>Una parola W si dice primitiva quando non esiste una parola P tale per cui W si ottiene \"affiancando\" un certo numero di volte P, ovvero W=PPPP...;
<BR>ad esempio W1 = ababba e\' primitiva, mentre W2 = abbaabba non e\' primitiva poiche\' esiste P = abba tale per cui W = PP.
<BR>Sia L(n) il linguaggio formato dalle parole lunghe esattamente n; quante parole primitive esistono nel linguaggio L(n)?
<BR>
<BR>
Aladin to the genius: "Oh, great spirit! My desire is that you do not fullfill my desire"
The genius was enlightened.

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 01 gen 1970, 01:33

sia n = prod p<sub>i</sub><sup>ai</sup>, con p<sub>i</sub> primi.
<BR>allora L(n) = 2<sup>n</sup> - sum 2<sup>(pi)^(ai)</sup>.
<BR>
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: ma_go il 16-09-2004 12:25 ]

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Messaggio da FrancescoVeneziano » 01 gen 1970, 01:33

Formula di inversione di Moebius!
<BR>
<BR>Invece di applicare la formula e ottenere immediatamente il risultato, rilancio chiedendo di dimostrare che date due successioni a_n e b_n (n>=1 intero)
<BR>
<BR>a_n=SUM[d|n] b_d
<BR>
<BR>se e solo se
<BR>
<BR>b_n=SUM[d|n] a_d mu(n/d)
<BR>
<BR>Dove mu(n) è la funzione di Moebius che vale 0 sui numeri divisibili per un quadrato, 1 sui numeri liberi da quadrati nella cui fattorizzazione compaiono un numero pari di fattori primi, -1 sui numeri liberi da quadrati nella cui fattorizzazione compaiono un numero dispari di fattori primi.
<BR>
<BR>
<BR>CaO
<BR>Francesco
<BR>
<BR>--------------
<BR>Dimenticavo! Prego gli universitari, già a conoscenza della soluzione, di non postarla e lasciare che siano i liceali a ragionarci un po\' su.
<BR>
<BR>[ Questo Messaggio è stato Modificato da: FrancescoVeneziano il 16-09-2004 18:38 ]
<BR>
<BR>Ho corretto l\'errore evidenziato da marco.<BR><BR>[ Questo Messaggio è stato Modificato da: FrancescoVeneziano il 17-09-2004 11:36 ]
Wir müssen wissen. Wir werden wissen.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

Non ho idea di cosa sia potuto capitare! Mi scuso per l\'inconveniente tecnico, ma non credo sia del tutto dipeso dalla mia volontà... In ogni caso, per una dimostrazione della formula d\'inversione di Möbius, v\'inviterei a visitare l\'indirizzo:
<BR>
<BR>http://olimpiadi.ing.unipi.it/modules.p ... 67&forum=5
<BR>
<BR>
<BR>\"Shit happens!\" - ventu<BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 17-09-2004 07:41 ]

WindowListener
Messaggi: 78
Iscritto il: 01 gen 1970, 01:00
Località: (UNI) Trieste

Messaggio da WindowListener » 01 gen 1970, 01:33

<IMG SRC="images/forum/icons/icon_wink.gif">
<BR>......
<BR>effettivamente il problema diventa ancora più semplice ....
<BR>
<BR>per la dimostrazione della prima formula di inversione io preferisco la versione elementare , catraga invece suppongo prediliga le serie di Dirichelt....
<BR>
<BR>wl
import javax.swing.geom.*;

WindowListener
Messaggi: 78
Iscritto il: 01 gen 1970, 01:00
Località: (UNI) Trieste

Messaggio da WindowListener » 01 gen 1970, 01:33

<IMG SRC="images/forum/icons/icon_wink.gif">
<BR>......
<BR>effettivamente il problema diventa ancora più semplice ....
<BR>
<BR>per la dimostrazione della prima formula di inversione io preferisco la versione elementare , catraga invece suppongo prediliga le serie di Dirichelt....
<BR>
<BR>wl
import javax.swing.geom.*;

WindowListener
Messaggi: 78
Iscritto il: 01 gen 1970, 01:00
Località: (UNI) Trieste

Messaggio da WindowListener » 01 gen 1970, 01:33

<IMG SRC="images/forum/icons/icon_wink.gif">
<BR>......
<BR>effettivamente il problema diventa ancora più semplice ....
<BR>
<BR>per la dimostrazione della prima formula di inversione io preferisco la versione elementare , catraga invece suppongo prediliga le serie di Dirichelt....
<BR>
<BR>wl
import javax.swing.geom.*;

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-09-16 18:43, WindowListener wrote:
<BR>[...] catraga invece suppongo prediliga le serie di <!-- BBCode Start --><I>Dirichelt</I><!-- BBCode End -->....
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Diricome?! Baaah... E comunque, tanto per liofilizzarti gli zebedei, mi permetto di rammentare a te e agli altri che i puntini di sospensione s\'inseriscono di regola in numero n = 0 mod 3. Vale!!!
<BR>
<BR>EDIT: è confortante constatare come anche a te il server abbia procurato un sacco di problemi, WindowListener! Già gridavo alla congiura...
<BR>
<BR>
<BR>\"Che v\'è di strano se qualche pentola esplode? Imparate a ridere di voi stessi, sì come si deve ridere!\" - Friedrich W. Nietzsche, <!-- BBCode Start --><I>Così parlò Zaratustra</I><!-- BBCode End -->

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Messaggio da FrancescoVeneziano » 01 gen 1970, 01:33

Noto con dispiacere che il mio invito agli universitari a non pubblicare subito la dimostrazione è stato ignorato, dimostrando in qualcuno difficoltà nella comprensione della lingua italiana o scarso rispetto nei confronti degli altri avventori del forum (scherzo naturalmente, spero si sia trattato solo di una svista).
<BR>
<BR>Dal momento che la chiarezza del post \"[N]La formula di inversione di Mobius\" rivaleggia con quella del disco di Festo o dei geroglifici trovati sull\'isola di Pasqua, mentre la dimostrazione elementare non è difficile ed è, per esempio, alla portata di chi ha partecipato recentemente allo stage di Pisa, invito i liceali in questione a riflettere sul problema e a risolverlo autonomamente, eventualmente usando
<BR>
<BR>HINT:
<BR>
<BR><font color=white>
<BR>Passate per l\'identità
<BR>
<BR>SUM[d|n]mu(d) = 1 se n=1, 0 se n è maggiore di 1
<BR>
<BR></font>
<BR>
<BR>CaO
<BR>Francesco
Wir müssen wissen. Wir werden wissen.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-09-16 17:37, FrancescoVeneziano wrote:
<BR>b_n=SUM[d|n] b_d mu(n/d)
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>O F.V., quando enunci, enuncia giusto!!
<BR>
<BR>er.... non è b_d, ma a_d (sennò a_* dove entra??).
<BR>
<BR>Inoltre, che c\'entra con il pb iniziale delle parole e sottoparole? Mi sono perso qualche puntata?
<BR>
<BR>Grazie per i chiarimenti.
<BR>
<BR>M.
<BR>[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Messaggio da FrancescoVeneziano » 01 gen 1970, 01:33

Grazie per aver evidenziato l\'errore, dovrei stare più attento quando scrivo formule <IMG SRC="images/forum/icons/icon_cool.gif">
<BR>
<BR>Il problema iniziale si risolve quasi immediatamente con la formula di inversione e a giudicare dalla forma della soluzione non c\'è altro modo per farlo; quindi ho pensato, invece di lasciare un problema che è inarrivabile per chi non conosce la formula di inversione (cioè, credo, quasi tutti gli olimpionici salvo universitari e pochi altri esperti) e quasi automatico per chi la conosce, di spostare l\'attenzione sulla mu di Moebius.
<BR>
<BR>dimostrazione del problema sulle parole:
<BR>
<BR><font color=white>
<BR>Sia a_n=2^n il numero di parole lunghe esattamente n
<BR>Sia b_n il numero di parole primitive di lunghezza n
<BR>Dalla definizione di parola primitiva segue che
<BR>a_n=SUM[d|n]b_d
<BR>e quindi
<BR>
<BR>b_n=SUM[d|n]2^d mu(n/d)
<BR></font>
<BR>
<BR>CaO
<BR>Francesco
Wir müssen wissen. Wir werden wissen.

WindowListener
Messaggi: 78
Iscritto il: 01 gen 1970, 01:00
Località: (UNI) Trieste

Messaggio da WindowListener » 01 gen 1970, 01:33

X HiTLeuLeR: scusa per Dirichlet <IMG SRC="images/forum/icons/icon_cool.gif"> , ma ho scritto troppo di fretta.
<BR>In effetti ieri sera il server non mi è stato di aiuto ... ... ... (contento) <IMG SRC="images/forum/icons/icon_biggrin.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: WindowListener il 17-09-2004 12:15 ]
import javax.swing.geom.*;

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-09-17 11:31, marco wrote:
<BR>\"Draco dormiens, numquam titilland<!-- BBCode Start --><B>um</B><!-- BBCode End -->\"
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Videtur draco in numero animalium, et sicut plerumque aliis nominibus animalium ipsum genus exigit masculinum! Nam docet magister verba et casibus et genere et numero conservare, ergo...
<BR>
<BR>E veniamo a te dunque, ossido...
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-09-16 17:37, marco wrote:
<BR>
<BR>Dimenticavo! Prego gli universitari, già a conoscenza della soluzione, di non postarla e lasciare che siano i liceali a ragionarci un po\' su.
<BR>
<BR>[ Questo Messaggio è stato Modificato da: FrancescoVeneziano il16-09-2004 <!-- BBCode Start --><B>18:38</B><!-- BBCode End -->]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Orbene, t\'inviterei - qualora, com\'è ovvio, ti restasse del tempo - a riordinare cronologicamente: i) il messaggio M originale con cui proponevi di risolvere il problema combinatorico di Catraga passando per la formula di Mobius; ii) il mio primo post su questo medesimo topic, che - come può testimoniare chiunque si sia levato all\'alba, stamane - conteneva effettivamente la <!-- BBCode Start --><B>stessa</B><!-- BBCode End --> soluzione poi ripubblicata in un topic adiacente anche per conseguenza di un \"momentaneo malore\" del server (già sopra segnalato); iii) la tua prima modifica su M, con la conseguente introduzione di quella nobile postilla che mi sono preso licenza di quotare; iv) la comparsa sul forum del topic \"La formula di inversione di Mobius\". Ecco, poscia che l\'avrai fatto, se mai ti andasse di farlo, magari ne riparleremo, ok? Il tutto in simpatia, naturalmente!
<BR>
<BR>EDIT: uff, qui qualcuno bara... vero, marco?! <IMG SRC="images/forum/icons/icon_razz.gif">
<BR>
<BR>
<BR>\"Colui che cinge gli asini di ali, [...] colui che si abbatte su ogni nuovo giorno ed ogni plebe, ch\'è nemico di teste di cardo e di capocce cavillose e di tutte le foglie e le erbacce appassite: lodato sia questo benefico spirito selvaggio e burrascoso, che danza su paludi e tristezze come fossero prati!\"
<BR>
<BR> - Friedrich W. Nietzsche, <!-- BBCode Start --><I>Così parlò Zaratustra</I><!-- BBCode End --><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 17-09-2004 13:05 ]

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-09-17 12:00, WindowListener wrote:
<BR>X HiTLeuLeR: scusa per Dirichlet [...]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Ehm... di sicuro non devi scusarti con il sottoscritto! Piuttosto, prova a implorare il perdono del vecchio Lejeune, chissà che non decida d\'essere indulgente! Foss\'io al suo posto, potresti pure flagellarti le chiappe fino a farti venir sangue, ché di certo non lo sarei...
<BR>
<BR>
<BR>\"Meta, perché al posto del cuore mi pulsano le p***e?\" - HiTLeuLeR

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-09-17 12:34, HiTLeuLeR wrote:
<BR>...
<BR>EDIT: uff, qui qualcuno bara... vero, marco?! <IMG SRC="images/forum/icons/icon_razz.gif">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>No, lo giuro, mi sono accorto della svista PRIMA di avere visto questo tuo post di correzione. E quando uno ha ragione, ha ragione...
<BR>
<BR>Comunque, a dimostrazione della mia buona volontà, scriverò 10 volte la frase \"Prima di inserire una citazione controllerò che sia esatta\"
<BR>
<BR>Anyway, allora mi sono davvero perso qualche puntata!
<BR>
<BR>Ciao.
<BR>
<BR>M.
<BR>
<BR>.......................
<BR>Prima di inserire una citazione controllerò che sia esatta
<BR>Prima di inserire una citazione controllerò che sia esatta
<BR>Prima di inserire una citazione controllerò che sia esatta
<BR>Prima di inserire una citazione controllerò che sia esatta
<BR>Prima di inserire una citazione controllerò che sia esatta
<BR>Prima di inserire una citazione controllerò che sia esatta
<BR>Prima di inserire una citazione controllerò che sia esatta
<BR>Prima di inserire una citazione controllerò che sia esatta
<BR>Prima di inserire una citazione controllerò che sia esatta
<BR>Prima di inserire una citazione controllerò che sia esatta[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Bloccato