Edizione XVII

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 INIZIALE NASTRO FINALE
dccsdlcdd 10021011
c 0
2012AD 100AT
dddd 1111
lcccl 30003

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 INIZIALE NASTRO FINALE
130201301123230S B
S0001 B
12321S3021 M
S B
1S12301202013302 M

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 INIZIALE NASTRO FINALE
S01200213 8
123001002S0123301 16
S 0
1S 1

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 INIZIALE NASTRO FINALE
011023001:2 KO
120113:1 OK
12312111:0 OK
0120000:5 OK
12334:12 KO
1022000320100300120030:12 OK

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 INIZIALE NASTRO FINALE
S
11111S222 1
1100021321001201S 1
S1122330032 23
321S 123

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 INIZIALE NASTRO FINALE
13321001000 00000111233
312212333 112223333
3 3
1230 0123
2221002012012 0000111222222

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 INIZIALE NASTRO FINALE
1111S 1111
01230S3320110 0123
S01230123012301230123 0123
21101S1131112 1112

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 INIZIALE NASTRO FINALE
1111:1:12000 3000
1123:1:12000 6000
0123:1:12000 12000
2233:2:144 72
2333:3:1440 480

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 INIZIALE NASTRO FINALE
1100021321001201S 01
31010023021S321001201 01
S22022121222322 2
11100332S 13
31113S332201 13

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 12030121100200 voti espressi: 1,1 risultati parziali: 0, 2, 0, 0
13210010122012 S 2030121100200 cambi di opinione
13210000122022 S 2030111100000 opinioni modificate
13210000122022 S 2030111100000 voti espressi: 2,2 risultati parziali: 0, 2, 2, 0
1321000012202 S 030111100000 cambio di opinione
1321000012222 S 030111100000 opinioni modificate
1321000012222 S 030111100000 voti espressi: 2,0 risultati parziali: 1, 2, 3, 0
132100001222 S 30111100000 nessun cambio di opinione
132100001222 S 30111100000 voti espressi: 2,3 risultati parziali: 1, 2, 4, 1
13210000122 S 0111100000 nessun cambio di opinione
13210000122 S 0111100000 voti espressi: 2,0 risultati parziali: 2, 2, 5, 1
1321000012 S 111100000 cambio di opinione
1321000012 S 111100000 opinione modificata
1321000012 S 111100000 voti espressi: 2,1 risultati parziali: 2, 3, 6, 1
132100001 S 11100000 nessun cambio di opinione
132100001 S 11100000 voti espressi: 1,1 risultati parziali: 2, 5, 6, 1
13210000 S 1100000 cambio di opinione
13210000 S 0100000 opinione modificata
13210000 S 0100000 voti espressi: 0,0 risultati parziali: 4, 5, 6, 1
1321000 S 100000 cambio di opinione
1321000 S 000000 opinione modificata
1321000 S 000000 voti espressi: 0,0 risultati parziali: 6, 5, 6, 1
132100 S 00000 nessun cambio di opinione
132100 S 00000 voti espressi: 0,0 risultati parziali: 8, 5, 6, 1
13210 S 0000 nessun cambio di opinione
13210 S 0000 voti espressi: 0,0 risultati parziali: 10, 5, 6, 1
1321 S 000 nessun cambio di opinione
1321 S 000 voti espressi: 1,0 risultati parziali: 11, 6, 6, 1
132 S 00 nessun cambio di opinione
132 S 00 voti espressi: 2,0 risultati parziali: 12, 6, 7, 1
13 S 0 nessun cambio di opinione
13 S 0 voti espressi: 3,0 risultati parziali: 13, 6, 7, 2
1 S nessun cambio di opinione
1 S voti espressi: 1 risultati parziali: 13, 7, 7, 2
S fine votazione risultato 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 INIZIALE NASTRO FINALE
1100021321001201S 01
31010023021S321001201 01
S22022121222322 2
11100332S 13
31113S332201 13
Notice: This work is licensed under a BY-NC-SA. Permalink: Edizione XVII

Comments are closed.