[C] : Linguaggi

Catraga · 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.
 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...;
 ad esempio W1 = ababba e\' primitiva, mentre W2 = abbaabba non e\' primitiva poiche\' esiste P = abba tale per cui W = PP.
 Sia L(n) il linguaggio formato dalle parole lunghe esattamente n; quante parole primitive esistono nel linguaggio L(n)?

Messaggio da **ma_go** » 01 gen 1970, 01:33

sia n = prod piai, con pi primi.
 allora L(n) = 2n - sum 2(pi)^(ai).
 
 [ Questo Messaggio è stato Modificato da: ma_go il 16-09-2004 12:25 ]

Messaggio da **FrancescoVeneziano** » 01 gen 1970, 01:33

Formula di inversione di Moebius!
 
 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)
 
 a_n=SUM[d|n] b_d
 
 se e solo se
 
 b_n=SUM[d|n] a_d mu(n/d)
 
 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.
 
 
 CaO
 Francesco
 
 --------------
 Dimenticavo! Prego gli universitari, già a conoscenza della soluzione, di non postarla e lasciare che siano i liceali a ragionarci un po\' su.
 
 [ Questo Messaggio è stato Modificato da: FrancescoVeneziano il 16-09-2004 18:38 ]
 
 Ho corretto l\'errore evidenziato da marco. [ Questo Messaggio è stato Modificato da: FrancescoVeneziano il 17-09-2004 11:36 ]

HiTLeuLeR · 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:
 
 http://olimpiadi.ing.unipi.it/modules.p ... 67&forum=5
 
 
 \"Shit happens!\" - ventu [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 17-09-2004 07:41 ]

WindowListener · Messaggio da **WindowListener** » 01 gen 1970, 01:33

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

WindowListener · Messaggio da **WindowListener** » 01 gen 1970, 01:33

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

WindowListener · Messaggio da **WindowListener** » 01 gen 1970, 01:33

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

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-16 18:43, WindowListener wrote:
 [...] catraga invece suppongo prediliga le serie di Dirichelt....
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 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!!!
 
 EDIT: è confortante constatare come anche a te il server abbia procurato un sacco di problemi, WindowListener! Già gridavo alla congiura...
 
 
 \"Che v\'è di strano se qualche pentola esplode? Imparate a ridere di voi stessi, sì come si deve ridere!\" - Friedrich W. Nietzsche, Così parlò Zaratustra

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).
 
 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
 
 HINT:
 
 
 Passate per l\'identità
 
 SUM[d|n]mu(d) = 1 se n=1, 0 se n è maggiore di 1
 
 
 
 CaO
 Francesco

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-16 17:37, FrancescoVeneziano wrote:
 b_n=SUM[d|n] b_d mu(n/d)
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 O F.V., quando enunci, enuncia giusto!!
 
 er.... non è b_d, ma a_d (sennò a_* dove entra??).
 
 Inoltre, che c\'entra con il pb iniziale delle parole e sottoparole? Mi sono perso qualche puntata?
 
 Grazie per i chiarimenti.
 
 M.
 [addsig]

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">
 
 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.
 
 dimostrazione del problema sulle parole:
 
 
 Sia a_n=2^n il numero di parole lunghe esattamente n
 Sia b_n il numero di parole primitive di lunghezza n
 Dalla definizione di parola primitiva segue che
 a_n=SUM[d|n]b_d
 e quindi
 
 b_n=SUM[d|n]2^d mu(n/d)
 
 
 CaO
 Francesco

WindowListener · 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.
 In effetti ieri sera il server non mi è stato di aiuto ... ... ... (contento) <IMG SRC="images/forum/icons/icon_biggrin.gif"> [ Questo Messaggio è stato Modificato da: WindowListener il 17-09-2004 12:15 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-17 11:31, marco wrote:
 \"Draco dormiens, numquam titillandum\"
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 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...
 
 E veniamo a te dunque, ossido...
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-16 17:37, marco wrote:
 
 Dimenticavo! Prego gli universitari, già a conoscenza della soluzione, di non postarla e lasciare che siano i liceali a ragionarci un po\' su.
 
 [ Questo Messaggio è stato Modificato da: FrancescoVeneziano il16-09-2004 18:38]
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 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 stessa 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!
 
 EDIT: uff, qui qualcuno bara... vero, marco?! <IMG SRC="images/forum/icons/icon_razz.gif">
 
 
 \"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!\"
 
 - Friedrich W. Nietzsche, Così parlò Zaratustra [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 17-09-2004 13:05 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-17 12:00, WindowListener wrote:
 X HiTLeuLeR: scusa per Dirichlet [...]
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 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...
 
 
 \"Meta, perché al posto del cuore mi pulsano le p***e?\" - HiTLeuLeR

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-17 12:34, HiTLeuLeR wrote:
 ...
 EDIT: uff, qui qualcuno bara... vero, marco?! <IMG SRC="images/forum/icons/icon_razz.gif">
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 No, lo giuro, mi sono accorto della svista PRIMA di avere visto questo tuo post di correzione. E quando uno ha ragione, ha ragione...
 
 Comunque, a dimostrazione della mia buona volontà, scriverò 10 volte la frase \"Prima di inserire una citazione controllerò che sia esatta\"
 
 Anyway, allora mi sono davvero perso qualche puntata!
 
 Ciao.
 
 M.
 
 .......................
 Prima di inserire una citazione controllerò che sia esatta
 Prima di inserire una citazione controllerò che sia esatta
 Prima di inserire una citazione controllerò che sia esatta
 Prima di inserire una citazione controllerò che sia esatta
 Prima di inserire una citazione controllerò che sia esatta
 Prima di inserire una citazione controllerò che sia esatta
 Prima di inserire una citazione controllerò che sia esatta
 Prima di inserire una citazione controllerò che sia esatta
 Prima di inserire una citazione controllerò che sia esatta
 Prima di inserire una citazione controllerò che sia esatta[addsig]