XIV edizione

Inaugurazione1

Nella piccola cittadina tedesca di Maschinestadt, in Turingia, sta per aprire un nuovo circolo culturale. Il proprietario, Alan, ha invitato una serie di abitanti all'inaugurazione, e ha segnato su una lista una “S” per ogni invito accettato, e una “N” per ogni invito rifiutato. Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di simboli “S” e “N”, lasci sul nastro una sequenza di tante “S” quanti sono le “S” nella sequenza di input (la lunghezza della risposta corrisponderà al numero di persone che hanno accettato l'invito all'inaugurazione).

Una misura di successo1

Una inaugurazione di circolo a cui partecipano meno di 10 persone è un fallimento. Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di simboli sull'alfabeto {S, N} come nell'esercizio precedente, lasci sul nastro il solo simbolo “S” (per Successo) se la sequenza di input comprendeva almeno 10 "S", e "F" (per Fallimento) in caso contrario.

Più siamo più ci divertiamo2

Alle feste di Alan partecipano sempre più persone. All'ingresso, viene segnata con una “X” su un nastro ogni persona entrata. A fine serata, si vuole sapere quante persone hanno partecipato alle attività. Si scriva un programma per macchina di Turing che, ricevuta sul nastro di ingresso una sequenza di “X”, lasci sul nastro il numero decimale corrispondente alla lunghezza della sequenza (ovvero, al numero di persone che sono entrate nella serata). Per questo esercizio, è possibile che la sequenza di input sia vuota (ovvero, nessuno è entrato); in questo caso il programma deve lasciare sul nastro il numero 0.

Il giusto mix5

Si sa, una festa funziona meglio se c'è un giusto mix di ragazzi e ragazze. Per questo motivo, il lunedì sera il club di Alan offre l'ingresso gratis ai rappresentanti del genere che in quel momento è minoritario. Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di simboli “M” (che indica l'ingresso di un ragazzo) e “F” (che indica l'ingresso di una ragazza), lascia sul nastro un simbolo “F” se deve essere offerto l'ingresso gratis alle ragazze, oppure “M” se deve essere offerto ai ragazzi. In caso di parità, per cavalleria, è gratuito l'ingresso per le ragazze

Ingressi e uscite8

Il martedì sera il circolo di Alan è ad ingresso libero: si svolgono dibattiti culturali sul tema dell'Entscheidungsproblem. Per qualche motivo, questi sono meno popolari delle feste del lunedì; entrano tante persone, ma molte escono (qualcuna, visibilmente pallida in volto) dopo pochi minuti. Alan chiede al personale all'ingresso di segnare con “M” e “F” gli ingressi, come nell'esercizio precedente, e con “N” e “E” le rispettive uscite. Si scriva un programma per macchina di Turing che, ricevuta sul nastro di ingresso una sequenza di simboli in {M, F, N, E} (con la garanzia che per ogni genere le uscite non possono superare gli ingressi), lasci sul nastro come risultato la sequenza “MkFh" in cui k e h sono espressi come numeri decimali, e indicano quante persone per il corrispondente genere sono ancora dentro il circolo nel momento in cui si analizza la sequenza.

Posti a tavola15

Il mercoledì sera il circolo organizza una cena fra i soci, che siedono tutti a una grande tavola circolare (viene usato un nastro infinito per trasportare le vivande, sul modello dei ristoranti Kaiten-zushi). Come al solito, la serata è più gradevole se ogni commensale uomo ha almeno un membro del gentil sesso accanto, e viceversa. Ovviamente, non sempre questo è possibile: dipende dal numero dei commensali. Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di “M” e “F” che rappresentano gli ingressi come negli esercizi precedenti, lasci sul nastro la risposta “OKse esiste una disposizione dei commensali al tavolo circolare che garantisce la proprietà di gradevolezza di cui sopra, e “KO” in caso contrario.

Bingo binario17

Il giovedì sera è dedicato agli anziani, e Alan organizza per loro un Bingo un po' semplificato. Ogni giocatore ha una cartella, composta da 4×4 caselle; in ogni casella è presente un simbolo "0” o “1”. Viene poi estratta una sequenza di 4 simboli fra “0” e “1”. Il giocatore che ha nella propria cartella l'esatta sequenza estratta, in orizzontale (da sinistra a destra), verticale (dall'alto al basso) o diagonale (da alto-sinistra a basso-destra) vince il premio per quella mano. Si scriva un programma per macchina di Turing che, ricevuta sul nastro di ingresso una codifica della cartella (in cui le 4 righe di simboli sono riportate in sequenza, da sinistra a destra, iniziando dalla riga più in alto), seguita da un simbolo “#” e poi dalla sequenza di 4 simboli estratta; lasci sul nastro “SI” se la cartella è vincente, “NO” in caso contrario.

Cinema,cinema!21

Il venerdì sera è giorno di cineforum presso il club di Alan. Il circolo è senza scopo di lucro, per cui il costo del biglietto viene calcolato dividendo il costo di noleggio del film per il numero di persone che partecipano alla serata. Per semplicità, il costo è sempre un numero intero di euro, approssimando in alto la quota individuale. L'eventuale (piccolo) avanzo viene destinato a fondo cassa per altre iniziative. Inoltre, il costo del biglietto è sempre inferiore a €10: se il numero di partecipanti non è sufficiente a garantire questa condizione, la serata viene annullata (e non si paga il noleggio). Si scriva un programma per macchina di Turing che, ricevuto sul nastro di input il costo di noleggio espresso in euro, seguito da un simbolo “/” e poi dal numero di partecipanti, lasci sul nastro il costo del biglietto seguito dal simbolo “”%” e dal residuo di fondo cassa, oppure “NO” se la serata va annullata per via del costo del biglietto troppo alto.

Il Social Network30

Per pubblicizzare le feste danzanti del sabato sera, Alan ricorre ai social network. Il problema consiste nell'identificare le persone che hanno maggiore influenza (intesa come: numero di amici e di amici degli amici), e fornire loro un invito gratis a condizione che costoro pubblicizzino l'evento con un post sulla loro bacheca. Diamo una rappresentazione del social network in cui gli abitanti dotati di presenza online sono indicati con una lettera dell'alfabeto fra "A" e "Z" (Maschinestadt è una città molto piccola). Gli amici di una persona sono indicati, fra parentesi, subito dopo il nome della persona. Così, per esempio, A(BF)B(CDEF)C(AEF) indica che A è amico di B e F, e B è amico di C, D, E e F, C è amico di A, E e F (si noti che la relazione di amicizia su questo social network non è simmetrica: A è amico di B, ma B non è amico di A). Nel nostro esempio, A ha 2 amici (B,F); di questi, B ha 4 amici (C,D,E,F), e F nessuno; complessivamente quindi la cerchia (ovvero: amici e amici degli amici, escludendo la persona in questione) di A comprende (B,C,D,E,F) e la sua influenza è pari a 5. Analogamente, B ha 4 amici (C,D,E,F); di questi, C ha 3 amici (A,E,F), e gli altri nessuno. La cerchia di B comprende (A,C,D,E,F) e la sua influenza è quindi pari a 5. Quanto a C, la sua cerchia comprende (A,B,E,F) e la sua influenza è dunque 4. Si scriva un programma per macchina di Turing che, data in input la descrizione di un social network nel formato indicato sopra, lasci sul nastro il nome della persona di massima influenza fra quelle presenti nel social network. In caso di parità, il programma deve lasciare su nastro il nome della persona fra gli ex-æquo che compare per prima nella descrizione in input.

Reazione e diffusione25

La domenica il circolo resta chiuso, e Alan può dedicarsi a un altro dei suoi interessi: la modellazione dei fenomeni biologici tramite equazioni di reazione-diffusione. Nella loro forma più generale, le equazioni di reazione-diffusione possono essere scritte come ∂u/∂t − d∇2u=f (u , x , t) dove d è il coefficiente di diffusione e f(u, x, t) rappresenta il termine non omogeneo di reazione. Queste equazioni possono modellare, fra l'altro, il modo in cui due sostanze chimiche semplici possono interagire per creare strutture complesse come le macchie del manto dei leopardi, oppure il modo in cui popolazioni di animali possono crescere, soffrire carestie e diminuire di numero, o spostarsi verso territori ancora vergini. Noi ci concentreremo però su un caso più semplice, quello di una reazione-diffusione di due sostanze (che chiameremo U e V) in una sola dimensione: si pensi, come caso concreto, a due sostanze chimiche che regolano la colorazione di un singolo pelo. Modelliamo la struttura unidimensionale come una serie di loci, rappresentati come coppie di celle, in cui la prima contiene la concentrazione di U, espressa con un numero decimale fra 0 (assente) e 9 (massima concentrazione), e la seconda contiene la concentrazione di V, espressa con una lettera fra A (assente) e J (massima concentrazione). Si applicano ad ogni locus le seguenti due regole:

  1. Diffusione:se la concentrazione di una sostanza in un locus è maggiore di quella nel locus successivo, si decrementa di uno la concentrazione nel primo, e si aumenta di uno nel secondo. Questa regola non si applica all'ultimo locus (quello più a destra) della struttura.
  2. Reazione:se in un locus si trova una concentrazione di almeno 6U e non più di 3V, allora vengono consumati 3U e trasformati in 1V (ovvero: si decrementa la concentrazione di U di 3, e si aumenta quella di V di 1).

Si scriva un programma per macchina di Turing che, data sul nastro di ingresso la configurazione iniziale di una struttura, ne calcoli ripetutamente l'evoluzione, arrestandosi soltanto quando l'applicazione delle due regole sopra dette non altera la concentrazione delle sostanze già realizzata (in questo caso, si è raggiunta la configurazione finale della struttura). Esempio: Partendo dalla prima configurazione, l'applicazione delle due regole di cui sopra ad ogni passo produce la seguente sequenza di configurazioni:

5E 8A 5E 2A → 5D 4C 5D 3B → 4C 5D 4C 4C → 4C 4C 5D 4C → 4C 4C 4C 5D
L'ultima configurazione è finale, in quanto non si applica nessuna delle due regole.