Vai al contenuto

Edizione XVII

  • di

Problema 1 – Cambio di casacca

Nel Mondo dei Programmatori, la vita politica è molto intensa e piena di sorprese.
Nuove liste e partiti si formano e dissolvono di continuo, mentre i Programmatori discutono di quale sia il linguaggio migliore da utilizzare.

Per esempio, fino a qualche anno fa si contavano vari movimenti:

  • i Programmatori C Indipendenti (simbolo: c),
  • i Discreti & Continui (simbolo: d),
  • i Programmatori Strutturalisti (simbolo: s)
  • e i Programmatori Lisp Integralisti (simbolo: l).

Negli anni, questi raggruppamenti hanno cambiato molte volte nome, al punto che si è preferito numerarli per chiarezza.

Così,

  • i Programmatori C Indipendenti sono diventati il partito 0,
  • i Discreti & Continui sono diventati il partito 1,
  • i Programmatori Strutturalisti sono diventati il partito 2,
  • e i Programmatori Lisp Integralisti il partito 3.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro una stringa sull’alfabeto {c, d, s, l}, in cui ogni simbolo rappresenta un elettore del corrispondente partito, lasci sul nastro gli stessi elettori, codificati però sull’alfabeto {0, 1, 2, 3}.

NASTRO INIZIALENASTRO FINALE
dccsdlcdd10021011
c0
dddd1111
lcccl30003

Problema 2 – Il Seggio Ben Ordinato

In tempo di votazioni, i Programmatori si mettono ordinatamente in fila al seggio (indicato dal simbolo S).
Un seggio è ben ordinato se la fila scorre in una unica direzione man mano che gli elettori votano (ovvero: tutti gli elettori sono, sul nastro, alla sinistra del seggio oppure tutti alla destra del seggio), mentre è mal ordinato in caso contrario.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro una stringa sull’alfabeto {0, 1, 2, 3, s} rappresentate la fila degli elettori e il seggio, lasci sul nastro il solo simbolo B se il seggio era ben ordinato, M altrimenti.
Il seggio vuoto si considera ben ordinato.

NASTRO INIZIALENASTRO FINALE
130201301123230SB
S0001B
12321S3021M
SB
1S12301202013302M

Problema 3 – Calcolo dell’affluenza

Si scriva un programma per macchina di Turing che, ricevuto in ingresso una configurazione di seggio (ben ordinato o meno), lasci sul nastro un numero decimale rappresentante il numero totale di elettori presenti nella configurazione.

NASTRO INIZIALENASTRO FINALE
S012002138
123001002S012330116
S0
1S1

Problema 4 – Caccia ai brogli!

Nel Mondo dei Programmatori il partito dei Programmatori C Indipendenti (il partito 0) ha fiducia assoluta nella fedeltà del proprio elettorato, e avendo ottenuto alle scorse elezioni meno voti di quelli previsti, sospetta che i partiti avversari abbiano trovato il modo di alterare il conteggio delle schede.

Si scriva un programma per macchina di Turing che, ricevuto in ingresso una sequenza di schede, ciascuna indicata con un simbolo fra 0 e 3, seguita dal simbolo ‘:‘ e poi dal numero di voti attesi espresso in decimale, lasci sul nastro la scritta OK se la votazione appare regolare, KO se si ritiene di poter contestare il risultato.

NASTRO INIZIALENASTRO FINALE
011023001:2KO
120113:1OK
12312111:0OK
0120000:5OK
12334:12KO
1022000320100300120030:12OK

Problema 5 – Il sistema maggioritario

Nel Mondo dei Programmatori è in vigore il sistema maggioritario: il partito che ottiene più voti, vince (e impone a tutti i programmatori di usare il suo linguaggio preferito, fino alle prossime elezioni).

Si scriva un programma per macchina di Turing che, ricevuto sul nastro una configurazione di seggio come negli esercizi precedenti, termini lasciando come risposta sul nastro il simbolo del partito che aveva più elettori nella configurazione.
In caso di ex-aequo, il programma deve terminare lasciando sul nastro i simboli dei partiti maggioritari ex-aequo, in ordine numerico crescente.
In caso di seggio vuoto, il programma deve terminare lasciando il nastro vuoto.

NASTRO INIZIALENASTRO FINALE
S 
11111S2221
1100021321001201S1
S112233003223
321S123

Problema 6 – Il Parlamento dei Programmatori

Il Parlamento dei Programmatori si organizza in gruppi che fanno riferimento a uno dei 4 partiti.
Come in altri consessi si formano ipotetici raggruppamenti di “destra” e “sinistra”, in base a dove i parlamentari seggono, così nel Parlamento dei Programmatori (gente notoriamente amante dell’ordine) si usa avere i partiti disposti in ordine numerico crescente, con il partito 0 seduto all’estrema sinistra e il partito 3 all’estrema destra.

Si scriva un programma per macchina di Turing che, data una sequenza di eletti (ciascuno rappresentato da un simbolo fra 0 e 3), faccia ordine e disponga i membri secondo l’ordine in cui essi siederanno in Parlamento, lasciando sul nastro la sequenza corrispondente.

NASTRO INIZIALENASTRO FINALE
1332100100000000111233
312212333112223333
33
12300123
22210020120120000111222222

Problema 7 – Il sistema proporzionale

Dopo che una imprevista vittoria elettorale del Partito Programmatori Pensionati aveva obbligato tutti a scrivere programmi solo in COBOL e FORTRAN, si è deciso di passare al sistema proporzionale.
In questo sistema, vengono eletti quattro rappresentanti, distribuiti in maniera proporzionale rispetto al numero di elettori.
In particolare, ogni partito ottiene un rappresentante ogni 25% del voto raccolto (così, un partito che ottenga il 50% dei voti avrà due rappresentanti); per la parte residua, il rappresentante viene assegnato al partito che ha ottenuto più voti secondo il metodo dei cosiddetti “massimi resti”.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro una configurazione di seggio, termini lasciando sul nastro i 4 simboli corrispondenti ai 4 rappresentanti eletti, in ordine numerico crescente, secondo il sistema proporzionale.
Per semplicità, si assuma che il numero di elettori presenti sia sempre un multiplo di 4, non superiore a 999, e che non si verifichino mai situazioni di ex-aequo.

Supponiamo che gli esiti della votazione siano i seguenti:

  • partito 0: 18 voti
  • partito 1: 12 voti
  • partito 2: 6 voti
  • partito 3: 8 voti.

Abbiamo un totale di 44 voti espressi, quindi il 25% corrisponde a 11 voti.
Il partito 0 ottiene subito un rappresentante (poiché 11 ≤ 18 < 22), come anche il partito 1; i partiti 2 e 3 non ne ottengono alcuno.

I voti corrispondenti ai rappresentanti assegnati vengono quindi sottratti al monte-voti di ciascun partito; questo ci lascia con i seguenti “resti”:

  • partito 0: 7 voti
  • partito 1: 1 voto
  • partito 2: 6 voti
  • partito 3: 8 voti.

I due rappresentanti mancanti vengono quindi assegnati al partito 3 (che ha un resto di 8 voti) e al partito 0 (che ha un resto di 7 voti), mentre il partito 2 con 6 voti di resto e il partito 1 con 1 voto di resto non ottengono altro.
L’esito dell’elezione è dunque: 0013.

NASTRO INIZIALENASTRO FINALE
1111S1111
01230S33201100123
S012301230123012301230123
21101S11311121112

Problema 8 – Rimborsi elettorali

Nel Mondo dei Programmatori, i diversi partiti ricevono un rimborso fisso per le spese elettorali, che è sempre un multiplo di 12, che va poi diviso fra i rappresentanti eletti.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro l’esito di una elezione (ovvero, una sequenza di 4 simboli sull’alfabeto {1, 2, 3, 4}, come dato dall’esercizio precedente), seguito da un “:“, dal simbolo del partito per cui stiamo facendo i conti, un altro “:“, e infine la cifra del rimborso attribuito al partito in questione, lasci sul nastro il rimborso pro-quota per ciascuno eletto di quel partito.
Si assuma che il rimborso viene attributo solo se c’è almeno un eletto del partito in questione.

NASTRO INIZIALENASTRO FINALE
1111:1:120003000
1123:1:120006000
0123:1:1200012000
2233:2:14472
2333:3:1440480

Problema 9 – Al Ballottaggio!

Anche il sistema proporzionale ha i suoi difetti.
Alle ultime elezioni, è stato eletto esattamente un rappresentante per ciascun partito, e ovviamente i quattro non si sono messi d’accordo su quale linguaggio adottare.
Si decide allora di passare al sistema di voto con ballottaggio.
In questo sistema, si svolgono due turni di votazione.
Se al primo turno uno dei partiti ottiene più del 50% dei voti, l’elezione termina con la vittoria di quel partito.
Altrimenti, vengono riproposti al voto, nel secondo turno, i due partiti che hanno ottenuto il maggior numero di voti al primo turno.
In tutti i casi di parità, prevale il partito che ha per simbolo il valore numerico più alto.

Si scriva un programma per macchina di Turing che, ricevuta in input una configurazione di seggio, termini lasciando sul nastro il simbolo del partito vincitore, oppure i simboli dei due partiti che andranno al ballottaggio, in ordine numerico crescente.

NASTRO INIZIALENASTRO FINALE
1100021321001201S01
31010023021S32100120101
S220221212223222
11100332S13
31113S33220113

Problema 10 – Politica 2.0

Tradizionalmente, i programmatori sono persone asociali, che non parlano facilmente di politica fra di loro.
Tuttavia, quest’anno va di gran moda un nuovo social network, chiamato Votebook, che consente a un programmatore in fila al seggio di scambiare opinioni, passando per dei server in Antartide, con le persone davanti a lui e con quelle dietro di lui nella fila.
Questi scambi di opinioni possono ovviamente influenzare il voto.
In particolare, se fra le due persone davanti e le due dietro all’elettore, ce ne sono almeno tre dello stesso partito, l’elettore viene convinto, e si adegua alla loro opinione (influenzando così l’esito finale della votazione).
Questo processo può essere espresso per passi come segue.
Si prenda una configurazione di seggio, anche mal ordinata.
Ad ogni passo, gli elettori immediatamente accanto al seggio esprimono il loro voto (che viene conteggiato), e lasciano la fila.
Tutti gli altri elettori hanno uno scambio di opinioni con gli elettori immediatamente precedenti e successivi nella fila, ed eventualmente cambiano opinione come descritto sopra.
Per l’elettore giunto all’inizio della fila (ovvero, accanto al seggio) si considera che gli elettori precedenti siano i primi della fila opposta, se presenti (altrimenti, il primo elettore non cambia opinione); gli elettori in fondo alla fila non hanno elettori successivi, e quindi non cambiano mai opinione.
Una volta terminato lo scambio di opinioni, il passo termina.
L’intera votazione si svolge in un numero di passi sufficiente a far votare tutti gli elettori.

Si scriva un programma per macchina di Turing che, presa in input una configurazione di seggio, lasci sul nastro i simboli del partito che ha ottenuto la maggioranza dei voti.
Si assuma che non vi saranno casi di ex-aequo.

Di seguito indichiamo la configurazione iniziale e i vari passi di una votazione (gli spazi intorno al seggio non sono significativi, e vengono mostrati solo per chiarezza):

132100101220121 S 12030121100200voti espressi: 1,1risultati parziali: 0, 2, 0, 0
13210010122012 S 2030121100200cambi di opinione 
13210000122022 S 2030111100000opinioni modificate
13210000122022 S 2030111100000voti espressi: 2,2risultati parziali: 0, 2, 2, 0
1321000012202 S 030111100000cambio di opinione
1321000012222 S 030111100000opinioni modificate
1321000012222 S 030111100000voti espressi: 2,0risultati parziali: 1, 2, 3, 0
132100001222 S 30111100000nessun cambio di opinione
132100001222 S 30111100000voti espressi: 2,3risultati parziali: 1, 2, 4, 1
13210000122 S 0111100000nessun cambio di opinione
13210000122 S 0111100000voti espressi: 2,0risultati parziali: 2, 2, 5, 1
1321000012 S 111100000cambio di opinione
1321000012 S 111100000opinione modificata
1321000012 S 111100000voti espressi: 2,1risultati parziali: 2, 3, 6, 1
132100001 S 11100000nessun cambio di opinione
132100001 S 11100000voti espressi: 1,1risultati parziali: 2, 5, 6, 1
13210000 S 1100000cambio di opinione
13210000 S 0100000opinione modificata
13210000 S 0100000voti espressi: 0,0risultati parziali: 4, 5, 6, 1
1321000 S 100000cambio di opinione
1321000 S 000000opinione modificata
1321000 S 000000voti espressi: 0,0risultati parziali: 6, 5, 6, 1
132100 S 00000nessun cambio di opinione
132100 S 00000voti espressi: 0,0risultati parziali: 8, 5, 6, 1
13210 S 0000nessun cambio di opinione
13210 S 0000voti espressi: 0,0risultati parziali: 10, 5, 6, 1
1321 S 000nessun cambio di opinione
1321 S 000voti espressi: 1,0risultati parziali: 11, 6, 6, 1
132 S 00nessun cambio di opinione
132 S 00voti espressi: 2,0risultati parziali: 12, 6, 7, 1
13 S 0nessun cambio di opinione
13 S 0voti espressi: 3,0risultati parziali: 13, 6, 7, 2
1 Snessun cambio di opinione
1 Svoti espressi: 1risultati parziali: 13, 7, 7, 2
Sfine votazionerisultato finale: 13, 7, 7, 2
risposta: 0

Notate come nella configurazione iniziale, il partito 0 avesse 10 voti, ma in seguito agli scambi di opinioni ne ha avuti alla fine 13.
Il partito 1 aveva anch’esso 10 voti inizialmente, ma alla fine ha avuto soltanto 7 voti.
Il partito 2 ha mantenuto i suoi 7 voti, e il partito 3 ha mantenuto i suoi 2 voti iniziali.
Il programma deve quindi terminare lasciando sul nastro il solo simbolo “0”.

NASTRO INIZIALENASTRO FINALE
1100021321001201S01
31010023021S32100120101
S220221212223222
11100332S13
31113S33220113

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *