Adiacenza valori su stringa: un test algebrico lineare
Ciao a tutti. Credo che la sezione più corretta per postare sia questa.
Allora io devo trattare delle stringhe di bit (o se vogliamo dei vettori $vec a in {0,1}^n$). Le stringhe che devo recuperare hanno zeri ed uno adiacenti. Diciamo che queste stringhe si ritorcono su se stesse (ora la dico grossa: come se fossero un "anello") per cui le adiacenze sono sia di questo tipo:
$000111000$
...che di questo:
$100000011$
(se le rapresentiamo su una circonferenza si capisce meglio).
Detto ciò per adiacenza intendo che i bit messi a $0$ o ad $1$ siano tutti insieme senza discontinuità. Ad esempio non mi van bene stringhe così:
$001101000$
$011000001$
Per fare ciò ho bisogno di un test algerbico (col vincolo della linearita!) ed avevo pensato a questo:
$\sum_{i=0}^{n-1} |(x_i-x_{1+1})| + |(x_n-x_0)|=2
ovvero sommo lo stato del bit i-esimo con l'opposto dello stato successivo (in maniere circolare) e il mio test è verificato se questa condizione è uguale a 2.
Secondo me è corretto ma come si può dimostrare?
Allora io devo trattare delle stringhe di bit (o se vogliamo dei vettori $vec a in {0,1}^n$). Le stringhe che devo recuperare hanno zeri ed uno adiacenti. Diciamo che queste stringhe si ritorcono su se stesse (ora la dico grossa: come se fossero un "anello") per cui le adiacenze sono sia di questo tipo:
$000111000$
...che di questo:
$100000011$
(se le rapresentiamo su una circonferenza si capisce meglio).
Detto ciò per adiacenza intendo che i bit messi a $0$ o ad $1$ siano tutti insieme senza discontinuità. Ad esempio non mi van bene stringhe così:
$001101000$
$011000001$
Per fare ciò ho bisogno di un test algerbico (col vincolo della linearita!) ed avevo pensato a questo:
$\sum_{i=0}^{n-1} |(x_i-x_{1+1})| + |(x_n-x_0)|=2
ovvero sommo lo stato del bit i-esimo con l'opposto dello stato successivo (in maniere circolare) e il mio test è verificato se questa condizione è uguale a 2.
Secondo me è corretto ma come si può dimostrare?
Risposte
quello che hai scritto è corretto se:
i possibili input sono solo 0 o 1
i bit sono n+1
è giusto non accettare le stringhe con tutti 0 o con tutti 1
quanto alla dimostrazione, algebricamente ... ? è piuttosto banale, perché consideriamo solo i valori numerici 0 e 1, ...
però da come il problema si presenta sembrerebbe più di natura informatica, e 0 e 1 che cosa rappresenta?
spero di essere stata utile. ciao.
i possibili input sono solo 0 o 1
i bit sono n+1
è giusto non accettare le stringhe con tutti 0 o con tutti 1
quanto alla dimostrazione, algebricamente ... ? è piuttosto banale, perché consideriamo solo i valori numerici 0 e 1, ...
però da come il problema si presenta sembrerebbe più di natura informatica, e 0 e 1 che cosa rappresenta?
spero di essere stata utile. ciao.
Ciao! Ti spiego meglio il problema:
Fondamentalmente io voglio rappresentare un Gantt ciclico i cui task non possono essere sovrapposti ma devono iniziare uno in cascata rispetto l'altro. Esempio
pensa al posto di "-" lo 0 e al posto di "%" 1. Ogni riga avrà tanti 1 quanto è la durata del task ma essi devono essere adiacenti (gli impongo il vincolo di prima). Perdipiù essendo un discorso peridico ci possono essere eventi rappresentati "ciclicamente" come il iv task in figura.
Si pensi che:
$x_i={(1,text{se il task è schedulato al minuto }i),(0,text{se il task NON è schedulato al minuto }i):}
la dimostrazione però mi sfugge; unaiutino-ino-ino
?
Altro paio di maniche sarà poi trovare un test algebrico analogo alla dimostrando per far sì che i task siano in cascata (finito il task A al minuto $i$ il B deve iniziare ad $i+1$...ma a questo ci penso con calma )
Fondamentalmente io voglio rappresentare un Gantt ciclico i cui task non possono essere sovrapposti ma devono iniziare uno in cascata rispetto l'altro. Esempio
----%%%%%------------- ---------%%%%--------- -------------%%%%%%--- %%-----------------%%%
pensa al posto di "-" lo 0 e al posto di "%" 1. Ogni riga avrà tanti 1 quanto è la durata del task ma essi devono essere adiacenti (gli impongo il vincolo di prima). Perdipiù essendo un discorso peridico ci possono essere eventi rappresentati "ciclicamente" come il iv task in figura.
Si pensi che:
$x_i={(1,text{se il task è schedulato al minuto }i),(0,text{se il task NON è schedulato al minuto }i):}
la dimostrazione però mi sfugge; unaiutino-ino-ino
?Altro paio di maniche sarà poi trovare un test algebrico analogo alla dimostrando per far sì che i task siano in cascata (finito il task A al minuto $i$ il B deve iniziare ad $i+1$...ma a questo ci penso con calma
)
circa la posizione non mi pare sia un problema (se è da immaginare "circolare"). il test algebrico scritto da te funziona bene se deve accettare stringhe come quelle da te descritte precedentemente con almeno un 1 e almeno uno 0, senza dire però quanti sono gli 0 e gli 1. sempreché sia noto il totale dei bit.
sull'argomento specifico non sono informata e non saprei aiutarti.
la dimostrazione "banale" sarebbe data dal fatto che |0-0|=|1-1|=0, |1-0|=|0-1|=1, quindi la sommatoria è 2 se ci sono state 2 "variazioni".
se i bit sono n e non n+1, dovresti partire da i=1.
mi dispiace se quanto detto non ti è utile... ciao.
sull'argomento specifico non sono informata e non saprei aiutarti.
la dimostrazione "banale" sarebbe data dal fatto che |0-0|=|1-1|=0, |1-0|=|0-1|=1, quindi la sommatoria è 2 se ci sono state 2 "variazioni".
se i bit sono n e non n+1, dovresti partire da i=1.
mi dispiace se quanto detto non ti è utile... ciao.
Ciao, molto utile invece! E' vero io posso dire che, data la circolarità, mi interessano stringhe con solo 2 variazioni.
$\sum_{i=0}^{n-1} |(x_i-x_{1+1})| + |(x_n-x_0)|=2$ (i)
La durata (maggiore di 1 => avrò almeno un uno) la posso imporre con un analogo terst lineare
$\sum_{i=0}^{n} x_i=text{durata del task}$ (ii)
(i) e (ii) presi insieme mi danno ciò che mi interessa (sulla riga ovvero sul singolo task).
Con un test analogo posso imporre che la fine di un task corrisponda con l'inizio del successivo!
potrei formalizzare la dimostrazione così:
Teorema 1: condizione necessaria e sufficiente affinchè una "stringa circolare" presenti solo due variazioni è che:
$\sum_{i=0}^{n-1} |(x_i-x_{1+1})| + |(x_n-x_0)|=2$ (i)
Dimostrazione:
sapendo che $x_i in {0,1},AAi$
$|x_i-x_{i+1}|= 0 hArr x_i=x_{i+1}$
(stessa cosa vale per $|(x_n-x_0)|$, differenza imposta per la circolarità di stringa)
$|x_i-x_{i+1}|= 1 hArr x_i!=x_{i+1}$
(stessa cosa vale per $|(x_n-x_0)|$, differenza imposta per la circolarità di stringa). ◊
che ne pensi!? Grazie!
$\sum_{i=0}^{n-1} |(x_i-x_{1+1})| + |(x_n-x_0)|=2$ (i)
La durata (maggiore di 1 => avrò almeno un uno) la posso imporre con un analogo terst lineare
$\sum_{i=0}^{n} x_i=text{durata del task}$ (ii)
(i) e (ii) presi insieme mi danno ciò che mi interessa (sulla riga ovvero sul singolo task).
Con un test analogo posso imporre che la fine di un task corrisponda con l'inizio del successivo!
potrei formalizzare la dimostrazione così:
Teorema 1: condizione necessaria e sufficiente affinchè una "stringa circolare" presenti solo due variazioni è che:
$\sum_{i=0}^{n-1} |(x_i-x_{1+1})| + |(x_n-x_0)|=2$ (i)
Dimostrazione:
sapendo che $x_i in {0,1},AAi$
$|x_i-x_{i+1}|= 0 hArr x_i=x_{i+1}$
(stessa cosa vale per $|(x_n-x_0)|$, differenza imposta per la circolarità di stringa)
$|x_i-x_{i+1}|= 1 hArr x_i!=x_{i+1}$
(stessa cosa vale per $|(x_n-x_0)|$, differenza imposta per la circolarità di stringa). ◊
che ne pensi!? Grazie!
prego!
sì, dovrebbe andar bene.
ti ripeto che con la sommatoria scritta così, i bit sono n+1. è corretto? è, cioè, quello che deve risultare?
ciao.
sì, dovrebbe andar bene.
ti ripeto che con la sommatoria scritta così, i bit sono n+1. è corretto? è, cioè, quello che deve risultare?
ciao.
Olè!
Sì, perché nell'esempio che ti ho fatto i bit sono numerati da 0 a n. In realtà userò un indice leggermente differente ed ovviamente adatto la notazione!!! Grazie per la segnalazione!
Mi premeva la dimostrazione, non avrei voluto scrivere stupidaggini!
Sì, perché nell'esempio che ti ho fatto i bit sono numerati da 0 a n. In realtà userò un indice leggermente differente ed ovviamente adatto la notazione!!! Grazie per la segnalazione!
Mi premeva la dimostrazione, non avrei voluto scrivere stupidaggini!
di nulla!
mi fa piacere se ti è stato utile.
mi fa piacere se ti è stato utile.
Azz...tutto giusto eccetto il fatto che se uso il $|.|$ non ho più la linearità 
in altre sezioni ci sono state accese discussioni sulla linearità.
qual è la tua definizione? e quali devono essere, soprattutto, le caratteristiche del test che devi usare?
qual è la tua definizione? e quali devono essere, soprattutto, le caratteristiche del test che devi usare?
Ciao Ada. Eh difatti me lo sto chiedendo pure io. Linearità: quando e perchè? Sembra che non sia un concetto troppo "chiaro" (anzi spesso ho sentito definizioni decisamente differenti). Io mi sono basato sulla definizione di wiki (graaande professionalita :/). Il problema è questo: il programma che uso non permette l'inserimento di variabili tra valore assoluto :/ :/ :/ bel problema per il mio scopo...
penso che si possa rimediare traducendo in altro modo la stessa richiesta, con qualche "verifica logica" in più.
in fondo che cosa significa |x-y| ?
nel tuo caso si riduce a: se $x=y$, allora assegni 0, se $x != y$ allora assegni 1.
buon lavoro! ciao.
in fondo che cosa significa |x-y| ?
nel tuo caso si riduce a: se $x=y$, allora assegni 0, se $x != y$ allora assegni 1.
buon lavoro! ciao.
Certo! Ci avevo pensato ma proprio non è consentito inserire logicità nei controlli...E vabbè, ci penso...Grazie per il supporto!!!
prego. fammi sapere!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo