Identificazione di intrusi in una scuola ideale

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Identificazione di intrusi in una scuola ideale

Messaggio da rand » 08 giu 2008, 12:43

In una scuola ci sono n allievi appartenenti ad m classi distinte, numerate da 1 ad m. Un sensore piazzato all'ingresso fornisce due dati: la classe (cioè l'intero che la identifica) di un allievo che attraversa l'ingresso e se l'allievo sta uscendo o entrando dall'edificio.

Ora, tenuto conto che in questa scuola ognuno è libero di entrare e uscire quando gli pare e piace, occorre definire un algoritmo che, osservando i dati forniti dal sensore, sia capace in ogni momento di rispondere alla domanda: "Gli allievi attualmente all'interno della scuola appartengono tutti alla stessa classe?".

Esiste una soluzione banale che fa uso di m variabili (contenenti interi da 1 a n), uno per classe e risponde in tempo O(m), ma si può fare di molto meglio: 1. Esiste una soluzione carina che usa O(log m) variabili e risponde in tempo O(log m)
2. Esiste una soluzione ancora più carina che usa O(1) variabili e risponde in tempo O(1)

ZeroMemory
Messaggi: 1
Iscritto il: 26 giu 2008, 10:13

Messaggio da ZeroMemory » 26 giu 2008, 10:19

ehm...ci sono in tutto n alunni nella scuola, e ognuno di questi appartiene ad una delle m classi...oppure ci sono m classi ognuna contenente n alunni?

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 26 giu 2008, 11:42

Intendevo che ci fossero n alunni in totale, ognuno appartenente ad una delle m classi. Ma non cambia molto. Assumendo che un registro di memoria contenga O(log n + log m) bits, le due soluzioni richiedono un numero di registri indipendente da n.

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite