 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[problema] Il Sistema Miu!
Clicca QUI per vedere il messaggio nel forum |
| KarmaKOMA |
Sia dato un sistema composto di tre lettere M,I,U. Questo sistema sarà perciò caratterizzato da stringhe composte con tali lettere.
Es. di stringhe sono:"MU","MIIIU","MUIUI"...ecc.Naturalmente l'ordine di disposizione delle lettere conta, perciò risulta evidente dire che "IM" è diverso da "MI",dove "IM" e "MI" sono due stringhe del sistema MIU.
Siano date le seguenti regole:
1)Se si possiede una stringa che termina con una "I" si può aggiungere una "U" alla fine (es "MIII"->"MIIIU").
2)Si abbia "Mx" allora si può includere "Mxx" alla collezione,dove "x" rappresenta una stringa che al minimo è composta da una delle tre lettere. (es "MIU"->"MIUIU").
3)Se in una delle stringhe della collezione c'è "III", si può costruire una nuova stringa sostituendo le "III" con una "U".
(es. "MIIII"->"MIU").E' necessario che le tre "I" siano adiacenti, altrimenti la sostituzione non è valida (es. non si può fare "IIMII"->"IMU"....questo è vietato!).Non è valida nemmeno il procedimento inverso (es. da "MU"->"MIII"...questo non si può fare!).
4)Se all'interno di una delle stringhe c'è un "UU" si può eliminarlo.(es. "MIUU"->"MI").
Sia data la stringa "MI", partendo da questa è possibile produrre la stringa "MU"???
Date una motivazione per ogni risposta.Buon lavoro (a chi volesse cimentarsi!)...ah dimenticavo E' ASSOLUTAMENTE VIETATO ANDARE CONTRO LE REGOLE. |
| Napolux |
| Mi sembra sia gia' stato postato. |
| KarmaKOMA |
| AZZ...non sapevo...mi linkate il post se c'è già? denghiu! |
| Smirne |
| anche tu alle prese con l`Hoefstadler? (so che non si scrive cosi`, mma e` per dare un`idea :D) |
| holylaw |
non si puo' avere un aiutino pls???
quando non mi vengono queste cose, mi demoralizzo |
| KarmaKOMA |
uahuahuha...si doloroso ma appassionante...settimana prossima vi tocca il pg-
...comunque in quel post la soluzione non c'era :D...onestamente non sono ancora arrivato al capitolo in cui ne da la dimostrazione...pero' ho provato l'approccio ad albero escludendo le varie ipotesi che si rivelavano ricorsive o mi riportavano a situazioni identiche....insomma immaginate un alberello con i vari ramoscelli... |
| Smirne |
| hehehe.. avevo provato anch'io cosi'.. ma e' disastroso.. cmq.. mi sa che per la soluzione dovrai attendere un bel po' di capitoli.. |
| AlphaGamma |
Cos'è? LFA? :D
Si può pensare, se non ricordo male (non è un linguaggio di tipo 3?), ad un automa a stati finiti che risolve il problema. :) |
| m@cCo |
Prova a farlo fare al computer, è lì apposta :D
Ciao |
| ildix |
Originally posted by Smirne
anche tu alle prese con l`Hoefstadler? (so che non si scrive cosi`, mma e` per dare un`idea :D)
Che libro è? Lo voglioooooo! :gnum:
:ihihih: |
| KarmaKOMA |
| Douglas R. Hofstadter Gödel, Escher, Bach: an Eternal Golden Braid Basic Books--->UN'ETERNA GHIRLANDA BRILLANTE! |
| KarmaKOMA |
Originally posted by AlphaGamma
Cos'è? LFA? :D
Si può pensare, se non ricordo male (non è un linguaggio di tipo 3?), ad un automa a stati finiti che risolve il problema. :)
ok...daremmo origine a catene infinite...:D Uomo 1- Pc 0....ragazzi godel ha posto limiti ai sistemi formali non li ha abbattutti! altrimenti avremmo risolto 'un'infinità' di teoremi...:D |
| TankJr. |
..l'ho finito..
(il libro, non il gioco :D)
ci ho messo + di 2mesi
che posso dire.. mah, estremamente affascinante.. nn ho compreso bene alcuni passaggi (per mancanza di voglia e di competenze), ma lo consiglierei davvero a tutti.. ti apre la mente (..solo la mente??)
(anche se mi resta il dubbio che si tratti solo di un enorme cumulo di seghe mentali!! )
..ora mi sto leggendo qlcosa di wittgenstein.. tanto x stare leggero! :) |
| KarmaKOMA |
Originally posted by TankJr.
..l'ho finito..
(il libro, non il gioco :D)
ci ho messo + di 2mesi
che posso dire.. mah, estremamente affascinante.. nn ho compreso bene alcuni passaggi (per mancanza di voglia e di competenze), ma lo consiglierei davvero a tutti.. ti apre la mente (..solo la mente??)
(anche se mi resta il dubbio che si tratti solo di un enorme cumulo di seghe mentali!! )
..ora mi sto leggendo qlcosa di wittgenstein.. tanto x stare leggero! :)
Nessuna sega mentale...ma reale reale e ancora...reale! |
| Col. Kurtz |
Ci provo. (selezionare sotto)
La risposta è no.
Per giungere a MU, possiamo
a) Aggiungere una U dopo una I, tramite la regola 1, ottenendo ad esempio MIU. In questo caso, applicando la regola 2 (Mx -> Mxx), otteniamo MIUIU al quale è possibile operare soltanto la regola 2.
b) Raddoppiare I: non porta da nessuna parte. Per ritrovarci con MU, dovremmo avere un numero di I dispari e divisibile per 3, in modo da sostituire tutte le III con U tramite la regola 3, e far sparire le doppie U tramite la regola 4.
Ma, iterando la regola 2, non si avrà mai un numero di I divisibile per 3, in quanto all'ennesima iterazione avremo 2^n I.
Le potenze di due non sono divisibili per 3, si dimostra per induzione:
1) 2^1 non è divisile per 3, cioé 2^1 mod 3 != 0.
Supponiamo quindi che 2^n non sia divisibile per 3 (2^n mod 3 != 0), dimostriamo per 2^(n + 1):
2^(n+1) = 2^n * 2
quindi (2^n * 2) mod 3 != 0, poiché 2^n mod 3 != 0 e il minimo comun divisore fra 2 e 3 è 6, e 0, 1 o 2 (i possibili resti per 3) moltiplicati per 2 sono sempre minori di 6, e pari (quindi != 3).
Scusate la forma alquanto complessa, ma in teoria sarei a lavoro e ho del sonno arretrato. Ho vinto? |
|
|
|
|
