|
 #1
Nella terza domanda di pagina 3.1 del libro Teoria dei Sistemi:
Test commentati e risolti, ho risposto A invece di B; ho pensato
ad un sistema con 2 stati (A e B), 2 simboli di ingresso (0 e 1) e 2
simboli di uscita (0 e 1) dove l'uscita 1 segnala la presenza di due
simboli di ingresso consecutivi uguali. Ecco una descrizione del sistema:
f 0 1
A A B
B A B
Funzione di stato futuro
g 0 1
A 1 0
B 0 1
Funzione di uscita
Ho provato a simularlo con FSS e a regime funziona...
(Michele Zanin)
I due stati del sistema da lei progettato memorizzano
la presenza in ingresso di uno 0 come ultimo simbolo (A) o di un 1 (B);
non è quindi possibile impostare lo stato inziale in modo che
il sistema funzioni correttamente, fin dall'inizio, con qualunque
sequenza di ingresso; ciò richiede, in effetti, l'introduzione
di un terzo stato. Se si tollera che il primo simbolo di uscita possa
non essere corretto, il sistema funziona, come da lei rilevato,
correttamente.
#2
Nella seconda domanda di pagina 3.9 del libro Teoria dei Sistemi:
Test commentati
e risolti, ho risposto "NULLA" al posto di B; se esiste un simbolo
di uscita che nessuno stato può produrre, il problema del
controllo per ottenere quel simbolo di uscita non ha soluzione
neppure se il sistema è fortemente connesso. (Michele Zanin)
L'insieme dei simboli di uscita di un sistema non può contenere,
per definizione, simboli che non possano venire generati da nessun stato
del sistema; la risposta corretta è quindi proprio la B.
#3
Nella prima domanda di pagina 3.15 del libro Teoria dei Sistemi:
Test commentati e risolti, ho risposto "NULLA" invece di AB; se
uno dei due stati ha altri stati equivalenti, non posso determinare
univocamente lo stato iniziale. (Michele Zanin)
Nella diagnosi a coppie l'insieme degli stati iniziali ammissibili
contiene solo due stati e lo scopo della diagnosi è
quello di distinguere tra di loro questi stati. Condizione necessaria
e sufficiente perché il problema ammetta soluzione è la
non equivalenza di tali stati. Le risposte corrette sono quindi la A
e la B.
#4
Nella prima domanda di pagina 3.21 del libro Teoria dei Sistemi:
Test commentati e risolti, ho risposto ABC invece di BC; secondo
me B => A. (Michele Zanin)
La risposta A implica anche la possibilità che la forma minima
considerata non risulti fortemente connessa. Poiché
ciò non può accadere, la risposta A non può
essere considerata corretta.
#5
Al ricevimento parlando di sistemi a stati finiti generici (a memoria
finita o non), lei disse che l'insieme degli stati iniziali compatibili con
funzioni qualsiasi u(.),y(.) nell'intervallo
[t0,t1] poteva essere
anche vuoto, ma sul libro (pag. 26 righe 12-15) viene affermato che la
y(.) non è arbitraria bensì vincolata all'istante
iniziale ed alla u(.); ne segue che l'insieme precedente non può
essere vuoto.
Quale definizione dobbiamo considerare?
Considerando quella del libro, posso dire che: forma minima => completa
osservabilità (in quanto u(.) e y(.) devono essere
compatibili)? (Alessandro Cevoli)
L'insieme di stati iniziali compatibili con una generica sequenza di
ingresso ed una altrettanto generica sequenza di uscita puè
certamente essere vuoto (si riveda, al riguardo, anche il problema
del controllo per ottenere una sequenza di uscita assegnata);
attenzione però che generica significa qualsiasi,
cioè assegnata in modo qualsiasi.
Ovviamente se si considerano sequenze di ingresso e di uscita
osservate sul sistema nello stesso intervallo di tempo,
l'insieme degli stati iniziali compatibili
sarà non vuoto visto che conterrà almeno lo stato iniziale
nel quale il sistema si trovava al tempo t0.
Non vi è quindi alcuna contraddizione tra quanto le ho
spiegato durante il ricevimento e quanto osservato sul testo.
Nei sistemi a stati finiti, infine, la completa osservabilità
richiede la forma minima ma non è affatto implicata da
questa né per i sistemi a memoria finita né per
quelli a memoria infinita.
#6
Con riferimento al testo Teoria dei Sistemi: Test commentati e
risolti, e al primo test di pagina 3.28, perché la diagnosi
è risolvibile anche con 5 esperimenti semplici? (Gabriele Tinti)
Il numero massimo di esperimenti necessari è, nel caso
considerato, pari a 4; è quindi sempre possibile risolvere il
problema della diagnosi con un esperimento multiplo che preveda 4 o
più esperimenti. Si noti che la domanda non fa riferimento al
numero minimo di esperimenti semplici necessari.
#7
Con riferimento alla prima domanda di pagina 3.28 del testo
Teoria dei Sistemi: Test commentati e risolti,
sul libro vengono indicate come corrette le risposte A e B.
Per risolvere la diagnosi nelle condizioni indicate sono necessari,
al più, m-1 esperimenti semplici (dove m indica
il numero degli stati iniziali ammissibili) quindi, nel caso
specifico, ne basteranno 4. È poi evidente che con un
esperimento in più (anche se non strettamente necessario)
posso ancora risolvere la diagnosi. Questa motivazione è esatta?
(Cristiano Cavallari)
Sì. Ricordo che è necessario indicare sempre tutte
le risposte corrette.
#8
In quali casi un sistema a stati finiti di Moore con n stati ha meno
di n simboli d'uscita? (Cristiano Carretti)
Un sistema a stati finiti di Moore con n stati può avere un
numero arbitrario di simboli di uscita purché ovviamente compreso
tra 2 ed n, indipendentemente da tutte le altre proprietà
(forma minima, memoria finita ecc.).
#9
Nell'ultima domanda a pag. 3.15 del testo Teoria dei Sistemi: Test
commentati e risolti, si fa riferimento ad un sistema a stati finiti
in forma minima con due simboli di ingresso e 3 stati. Come mai l'ultima
risposta, che afferma che tale numero è pari a tre se il sistema
è di Moore, non è corretta? Il fatto che il sistema sia in
forma minima e di Moore non implica che abbia un numero di simboli di
uscita pari al numero degli stati del sistema? (Giuseppe Busi)
La forma minima di un sistema di Moore non richiede che
ad ogni stato si associato un diverso simbolo di uscita ma solo che,
come per ogni sistema a stati finiti, la partizione di equivalenza sia
la partizione minima. Se ogni stato di un sistema di Moore è
associato ad un simbolo di uscita diverso il sistema è, ovviamente,
in forma minima poiché la partizione di 0-indistinguibilità
è, in tale caso, la partizione minima e coincide quindi con
la partizione di equivalenza. In generale (sistemi di Mealy e di Moore)
il fatto che risulti P0=Pm implica che il
sistema sia in forma minima ma non vale la proposizione inversa.
#10
Nell'ultima domanda a pag. 3.24 del testo Teoria dei Sistemi: Test
commentati e risolti, si fa riferimento ad un sistema a stati finiti
nel quale il problema della diagnosi ammette soluzione, per ogni insieme
di stati iniziali, con un esperimento semplice e predisposto. Come mai
la prima risposta, che afferma che gli stati iniziali sono
0-distinguibili, non è corretta? Se un esperimento semplice,
risolve il problema della diagnosi, non ne segue che gli stati
iniziali ammissibili sono 0-distinguibili? (Giuseppe Busi)
Valgono le stesse osservazioni fatte nella risposta precedente;
la 0-distinguibilità e l'equivalenza di due stati sono
proprietà diverse. La possibilità di risolvere un
problema di diagnosi con un certo insieme di stati iniziali
implica che tale insieme non contenga stati equivalenti; tali stati
possono tuttavia risultare 0-indistinguibili.
#11
Avrei una domanda che non riguarda in maniere stretta il corso, ma che
è forse più un problema che intelligenza artificiale.
Il cervello umano può essere approssimato con un modello a stati
finiti? Se così fosse, quanti stati possiede un sistema così
complesso?
Siccome immagino che, ammesso che sia possibile, una simulazione che
abbia come oggetto il cervello umano sia troppo complessa per essere
gestita con la potenza di calcolo oggi a nostra disposizione, mi
interesserebbe sapere se sono state fatte simulazioni su cervelli più
semplici (di insetti per esempio). (Lorenzo Vegetti)
Il cervello umano è una struttura di notevole complessità
e varie informazioni sul suo modo di operare sono state acquisite solo
di recente. Dal punto di vista strutturale è costituito da miliardi
di neuroni;
trattandosi di un numero finito, anche se molto elevato, di
elementi si potrebbe pensare di costruire un modello globale a stati
finiti che tenga conto dello stato di ogni singolo neurone.
Un modello di questo tipo dovrebbe però mettere in gioco anche lo
scambio di informazioni tra i vari gruppi di neuroni e tra questi e le
restanti parti del corpo. Personalmente non sono a conoscenza di ricerche
in questa direzione. Allego il commento del Prof. Angelo Cappello,
docente del corso di Bioingegneria II presso la nostra Facoltà.
Nel nostro sistema nervoso centrale ci sono circa 100 miliardi di neuroni
ciascuno dei quali è connesso, in entrata ed in uscita, con qualche
migliaio di altri neuroni.
Ciò dà una vaga idea delle dimensioni del sistema dinamico
associato, ma solo vaga dato che la struttura del modello cambia in seguito
al mutare delle interconnessioni tra le varie unità neuronali.
Secondo una certa trattazione, i neuroni possono essere raggruppati in Neuroni
Equivalenti per l'assolvimento di determinate funzioni (trasmissione
dell'intensità di un segnale, trasmissione di informazioni ,
generazione di campi elettrici e/o magnetici, reti neuronali, sensazione).
Non sono al corrente di simulazioni condotte su cervelli più semplici
del nostro.
Mi limiterei comunque a parlare di simulazione a livello di una ben determinata
funzione. Va infine sottolineata la difficoltà di validare un modello
così complesso semplicemente sulla base di un'analogia con le risposte
del sistema allo studio. Ci possono essere molti modelli, tutti plausibili e
compatibili con le attuali conoscenze, in grado di fornire risposte
soddisfacenti. Ovviamente non possono essere tutti contemporeaneamente corretti.
Per questo la modellistica va sempre supportata dalla ricerca fondamentale,
in questo caso a livello biologico. Altrimenti si può realizzare
una rete di neuroni al solo scopo di risolvere problemi pratici
(classificazione statistica, identificazione di sistemi, elaborazione di
segnali ed immagini, ecc.) ma non si può certo dire che, solo per il
fatto di comportarsi bene, essa replichi morfologicamente e funzionalmente
il nostro sistema nervoso centrale. Un testo sul quale tale tematica può
venire approfondita è:
E. Biondi, P. Morasso, V. Tagliasco, Neuroscienze e scienze dell'artificiale:
dal neurone all'intelligenza, Atti della Scuola GNB, Bressanone (BZ), 1991,
Patron Editore.
Angelo Cappello
#12
Nell'ultima lezione, in cui lei ha esposto l'algoritmo per determinare
le varie parzializzazioni indotte da una sequenza d'ingresso u[0,k]
partendo da un insieme di stati iniziali Xa, ha detto che
se si ottiene una parzializzazione degli stati finali o futuri che ha un
solo elemento per blocco, allora il problema dell'incasellamento ha
soluzione con la sequenza di ingresso considerata. Le chiedo:
1) Si può dire che due stati, che appartengono ad uno stesso
blocco della parzializzazione finale Qk, sono k-indistinguibili
con quella sequenza d'ingresso?
2) Se la parzializzazione finale Qk contiene un numero di blocchi
pari al numero degli stati di Xa e tali blocchi contengono
tutti lo stesso elemento, il problema dell'incasellamento ha ancora
soluzione? (Giuseppe Busi)
Una assegnata sequenza di ingresso induce, su un insieme di stati iniziali
ammissibili, una partizione associata alla relazione (di equivalenza)
definita dalla proprietà di generare, con tale ingresso, la stessa
sequenza di uscita, e parzializzazioni degli stati finali e futuri (al
tempo k+1) associate all'immagine, nella funzione di transizione dello
stato, di tale partizione. La proprietà in gioco è quindi
sempre la stessa (generazione della stessa sequenza di uscita con un
ingresso assegnato); nella diagnosi la si esamina con riferimento allo
stato iniziale, nell'incasellamento con riferimento a quello finale o
futuro.
Ciò premesso, non è possibile associare in alcun
modo la indistinguibilità di due stati con un ingresso assegnato
alla loro presenza in un unico blocco della parzializzazione degli stati
finali (o futuri), perché la indistinguibilità può
venire riferita solo agli stati iniziali. La sua prima domanda
avrebbe avuto risposta positiva se avesse fatto riferimento alla
partizione degli stati iniziali indotta dall'ingresso applicato.
Per quanto riguarda la seconda domanda, la risposta è senz'altro
positiva. Nel caso descritto infatti ogni stato iniziale genera una
sequenza di uscita diversa e raggiunge lo stesso stato finale; si
ottiene quindi non solo la soluzione del problema dell'incasellamento,
ma anche quella del problema della diagnosi.
#13
Durante una lezione sui sistemi a stati finiti ha fatto un esempio di
osservatore dello stato, ed aveva assegnato le funzioni di stato futuro
e di uscita del sistema da osservare secondo le seguenti tabelle:
f 1 2
x1 x1 x2
x2 x3 x2
x3 x1 x2
Funzione di stato futuro
g 1 2
x1 0 1
x2 0 1
x3 1 0
Funzione di uscita
mentre per gli stati dell'osservatore aveva introdotto le seguenti
codifiche:
z1={x1}, z2={x2},
z3={x3}, z4={x1,x2},
z5={x1,x3},
z6={x2,x3},
z7={x1,x2,x3},
costruendo poi la seguente tabella delle transizioni per lo stato
dell'osservatore:
10 11 20 21
z1 z1 z4* z4* z2
z2 z3 z6* z6* z2
z3 z4* z1 z2 z4*
z4 z5 z7* z7* z2
z5 z1 z1 z2 z2
z6 z3 z1 z2 z2
z7 z5 z1 z2 z2
Funzione di stato futuro
dove gli stati segnati con un asterisco definiscono le condizioni di
errore nelle quali l'osservatore si può trovare.
Volevo sapere se esiste un criterio "ottimo" con il quale
procedere per assegnare le condizioni di errore dell'osservatore, o se
qualunque criterio può andare bene. Questo perché secondo
me, ad esempio, nella prima riga (quella di z1) invece di
assegnare come stato futuro z4 si potrebbe assegnare, per uy=11,
z1 e per uy=20, z2 questo
perché si potrebbe interpretare la condizione d'errore come un errato
aggangio dell'osservatore, quindi nel caso particolare si potrebbe
interpretare l'uscita come se fosse data da uno stato diverso da quello
a cui l'osservatore si è agganciato e, di conseguenza, si può
fare in modo che l'osservatore si agganci allo stato futuro al quale il
sistema si è portato dopo aver dato l'uscita osservata.
(Giuseppe Busi)
Il criterio utilizzato per risolvere le situazioni di non congruenza tra
stato dell'osservatore e valori dell'ingresso e dell'uscita del sistema
è molto semplice e consiste nel considerare come stato futuro
quello stato che codifica il sottoinsieme degli stati raggiungibili in
una transizione dallo stato attuale. Questo criterio minimizza la
perdita di informazione assumendo come corretto lo stato attuale
dell'osservatore, attribuendo cioè tutti gli errori alle
osservazioni dell'ingresso e dell'uscita del sistema da osservare;
questa è la situazione che ha maggior interesse pratico.
La soluzione alternativa che lei descrive considera una situazione
duale, quella in cui si considerano affidabili le osservazioni e si
attribuisce tutto l'errore allo stato dell'osservatore; si tratta
certamente di una soluzione possibile. Vale infine la pena di considerare
il caso più restrittivo, quello cioè in cui si consideri
la possibilità di errori tanto sullo stato dell'osservatore
quanto sulle osservazioni; in tale caso si potrà assumere
come stato futuro dell'osservatore quello che codifica l'intero insieme
degli stati del sistema da osservare (z7 nell'esempio considerato).
#14
Nell'ultima domanda di pag. 3.32 del testo Teoria dei Sistemi: Test
commentati e risolti, viene segnalata come corretta la sola
risposta C. Non deve essere ritenuta corretta anche la B, sulla base di
queste cosiderazioni:
1) Un sistema a stati finiti in cui ha senso parlare di stato ha
profondità di memoria minima pari ad 1 in quanto una
profondità di memoria pari a 0 implicherebbe un sistema
algebrico il quale non possiede uno stato;
2) Se un osservatore si aggancia, come nel nostro caso, dopo n-mu
transizioni, allora è sicuramente agganciato dopo n-1 transizioni
in quanto n-1 => n-mu;
3) Nella domanda non è richiesto il numero minimo di transizioni
necessarie ma solo quando lo stato del sistema da osservare e
quello dell'osservatore coincidono. (Terenzio Berni)
La risposta B è, in effetti, corretta, ma per motivi diversi da quelli
che lei propone. Lei infatti suppone, nella considerazione 2), che
l'osservatore del sistema in esame si agganci dopo n-mu transizioni e da
tale osservazione, priva di riscontro (l'osservatore di un sistema con
memoria mu si aggancia dopo mu transizioni) deduce la correttezza della
risposta B. Tale risposta è invece corretta perché il valore
massimo della memoria di un sistema a stati finiti a memoria finita è
pari alla lunghezza massima dei percorsi nel grafo di transizione che, per
un sistema di ordine n, è n-1.
#15
Il commento all'ultima domanda a pagina 3.21 del libro dei Teoria dei
Sistemi: Test commentati e risolti, afferma che la completa
ricostruibilità è una proprietà che vale solo per sistemi
a memoria finita, ridotti in forma minima. La risposta A non dovrebbe essere
dunque esatta? (Ho pensato che un sistema equivalente ad un sistema ridotto
in forma minima e a memoria finita lo sia a sua volta) (Nicola Garofalo)
Un sistema a stati finiti può essere equivalente ad un altro sistema
a memoria finita ed in forma minima senza essere, necessariamente, in forma
minima; non è quindi detto che risulti completamente ricostruibile.
#16
Una curiosità: un programma per calcolatori
elettronici è pensabile come sistema a stati finiti?
In tal caso, sono applicabili gli algoritmi di diagnosi/incasellamento
allo sviluppo del software, per esempio nel testing? (Stefano Bigotto)
Un programma per calcolatori è, in effetti, un sistema a stati
finiti e risultano quindi applicabili tutte le procedure viste per
tali sistemi. Questo tuttavia ha una importanza più concettuale
che pratica a causa del numero elevatissimo di stati della maggior
parte di tali sistemi.
#17
A proposito della prima domanda di pag 3.10 del testo Teoria dei Sistemi:
Test commentati e risolti, le volevo chiedere una conferma circa
l'inesattezza della risposta A: tale risposta è errata in quanto un
sistema completamente osservabile è tale che per ogni funzione
di ingresso ammissibile, l'insieme degli stati iniziali compatibili contiene
un solo elemento per ogni sequenza di uscita ammissibile, ma ciò
non garantisce che venga risolto il problema per la sequenza di uscita
assegnata. È esatto? (Alessandro Rafelli)
L'insieme di stati iniziali compatibili con una assegnata sequenza di uscita
in un sistema a stati finiti può risultare vuoto indipendentemente
da ogni altra proprietà del sistema (osservabilità, forma minima,
memoria finita, completa controllabilità ecc.). Non è detto
cioè che un sistema a stati finiti sia in grado di generare
qualunque sequenza di uscita. L'osservabilità fa invece riferimento,
come lei correttamente rileva, a sequenze di uscita ammissibili, in quanto
osservate sul sistema, e compatibili con le corrispondenti sequenze di
ingresso.
#18
Con riferimento alla prima domanda di pag. 3.32 del testo
Teoria dei Sistemi: Test commentati e risolti,
non ho capito perché la risposta B è errata.
Mi sembrerebbe infatti in contraddizione con quanto si legge, ad esempio,
nel commento dell'ultima domanda di pag. 3.21: "la completa
ricostruibilità è una proprietà che vale solo per
i sistemi a memoria finita, ridotti in forma minima".
Possiamo cioè affermare che:
a) forma minima e memoria finita sono condizioni necessarie e sufficienti
per la completa ricostruibilità;
b) un sistema completamente ricostruibile è sicuramente in forma minima
e a memoria finita;
o solamente che:
c) un sistema completamente ricostruibile è sicuramente a memoria finita.
(Michele Berionni)
È molto semplice costruire un esempio di sistema non in forma minima
(e nemmeno fortemente connesso) che risulti completamente ricostruibile.
Un esempio potrebbe essere il seguente:
f 0 1
A C C
B C C
C C C
Funzione di stato futuro
g 0 1
A 0 1
B 0 1
C 0 0
Funzione di uscita
La risposta B quindi è senz'altro non corretta. Il commento da lei
citato fa poi riferimento alla forma minima come condizione sufficiente
per la completa ricostruibilità dei sistemi a memoria finita.
#19
Nella prima domanda di pag 3.5 del testo Teoria dei Sistemi:
Test commentati e risolti
si afferma che la condizione W-(x)=X è necessaria e
sufficiente a determinare la forte connessione.
Non è quindi necessario che sia verificata anche la condizione
W+(x)=X (come si dice a pag. 52 del testo di teoria)?
O è sufficiente che sia verificata una delle due?
Nella spiegazione all'ultima domanda di pag. 1.6 del testo contenente i test
sembra potersi dedurre che W+(x)=X <=> W-(x)=X .
È vero?
La connesione e la forte connessione sono la stessa cosa?
(Michele Berionni)
Le condizioni W+(x)=X per ogni stato e W-(x)=X per
ogni stato sono equivalenti ed ognuna di esse è necesaria e
sufficiente per la forte connessione (o connessione, è la stessa
cosa, come chiaramente indicato sul testo di teoria).
Come abbiamo poi dimostrato anche a lezione, se per un generico stato x
vale la condizione W+(x)=W-(x)=X, valgono anche
le condizioni precedenti ed il sistema è fortemente connesso.
#20
Nel testo Teoria dei sistemi: test commentati e risolti alla pagina 3.14
nel commento alla prima domanda è detto che per ogni sistema la
partizione (n-2)-indistinguibilità è la partizione di
equivalenza, ma cio non è vero solo per due stati?
(Alberto Nuzzo)
Come abbiamo verificato a lezione, la partizione di k-indistinguibilità
diventa la partizione di equivalenza al più per k=n-2. Ne segue che
la Pk-2 coincide in ogni caso con la partizione di equivalenza
anche se, in genere, la si ottiene con un numero di passi inferiore.
#21
A pagina 3.19 del libro Teoria dei sistemi: test commentati e risolti
nel commento alla seconda domanda viene detto che essendo il sistema non in
forma minima non è garantita l'esistenza della soluzione ai problemi
dell'incasellamento e della diagnosi. Quindi affinché un sistema
ammetta soluzione ai precedenti problemi deve essere in forma minima?
(Alberto Nuzzo)
Il problema della diagnosi ammette sempre soluzione con un esperimento multiplo
quando l'insieme degli stati iniziali ammissibili non contiene stati
equivalenti; la forma minima è dunque richiesta quando tale insieme
coincide con l'intero insieme degli stati.
Il problema dell'incasellamento ammette invece sempre soluzione con un
esperimento semplice quando il sistema è in forma minima; tale condizione
tuttavia è solo sufficiente ma non necessaria (riveda, a tale riguardo,
il semplice esempio che vi ho proposto a lezione).
#22
Sul libro di teoria è scritto che la P0 ha almeno 2 blocchi.
È corretto affermare che ciò è vero solo se il sistema
ha solo 2 simboli di uscita? In altre parole, se ho k simboli di uscita,
possiamo dire che la P0 avrà almeno k blocchi? (Marcello
Romani)
L'affermazione è vera in generale perché un sistema dinamico
non può avere tutte le righe della tabella della funzione di uscita
uguali (né meno di due simboli di uscita). La presenza di k simboli
nell'insieme delle uscite implica poi la presenza di non meno di k blocchi
nella P0 solo se il sistema è di Moore.
#23
Vorrei sapere se è giusta l'implicazione "sistema non ricostruibile ->
sistema a memoria infinita".
(Francesco Baroncini)
No.
#24
Se considero due sistemi a stati finiti fotemente connessi, l'equivalenza tra uno stato
del primo ed uno del secondo, implica l'equivalenza tra i due sistemi?
Partendo infatti da questi due stati, qualsiasi ingresso applicato porterebbe i 2
sistemi in due stati nuovamente equivalenti (altrimenti non lo sarebbero quelli di
partenza) e così via con le successive. Essendo i 2 sistemi fortemente connessi posso
raggiugere qualsiasi stato, trovando di volta in volta stati del primo equivalenti ad
altri del secondo. Esatto? (Massimo Barbati)
Il suo ragionamento è corretto (occorrerebbe però, per parlare di equivalenza
in maniera rigorosa,
fare riferimento agli stati del sistema composito che abbiamo introdotto per valutare
l'equivalenza di due sistemi). La sua domanda è un ottimo esempio di ragionamento
deduttivo fatto in base ad una completa comprensione delle proprietà degli stati
equivalenti.
#25
Quando un sistema a memoria finita è completamente ricostruibile? (2148 61583)
Abbiamo dimostrato che ciò avviene quando il sistema è in forma minima. Le ricordo che
per avere una risposta è necessario inserire anche il proprio nome, non il solo numero di
matricola.
#26
Per un sistema fortemente connesso è possibile risolvere sia il problema dell'incasellamento
sia la diagnosi con un esperimento semplice predisposto? (R.R.)
No, la forte connessione non implica alcuna delle proprietà da lei indicate. Le ricordo
inoltre che la diagnosi può non risultare possibile con un esperimento semplice quando
il numero di stati iniziali ammissibili è maggiore di due indipendentemente da ogni
altra caratteristica del sistema.
#27
L'incasellamento ammette sempre soluzione con un esperimento semplice e predisposto.
Allora, dal momento stesso che ammette sempre soluzione, non è vero che, affinché una
sequenza di ingresso risolva problema dell'incasellamento, la parzializzazione deve
contenere un blocco per ogni elemento!? Voglio dire che non
dovrebbero essere presenti condizioni restrittive! In cosa sbaglio? (R.R.)
Non è affatto vero che l'incasellamento sia sempre possibile nelle condizioni da
lei indicate (lo è se il sistema è in forma minima). Anche in questo caso poi, a
meno che il sistema non sia a memoria finita, una sequenza generica non risolve tale
problema; non comprendo quindi cosa intenda con "non dovrebbero essere
presenti particolari condizioni restrittive".
#28
Un sistema fortemente connesso è necessariamente in forma minima? Perché? (R.R.)
L'assenza di stati equivalenti (forma minima) e la forte connessione sono proprietà
del tutto disgiunte come è facile verificare attraverso semplici esempi che la invito
a costruire personalmente (bastano sistemi con tre stati per verificare la possibilità
di ogni possibile combinazione di tali proprietà).
#29
I sistemi a memoria finita, in forma minima, sono completamente incasellabili. Non è
detto però che siano completamente osservabili in quanto uno stesso stato finale
potrebbe essere raggiunto da stati iniziali
differenti, applicando sequenze di ingresso diverse: ho ragione? (R.R.)
No, il motivo è per il quale sistemi di tale tipo non sono necessariamente completamente
osservabili è legato al fatto che uno stesso stato finale può essere raggiunto a partire
da stati iniziali diversi con la stessa sequenza di ingresso e di uscita.
#30
Per n stati iniziali ammissibili, qual è la lunghezza massima della sequenza di ingresso
che risolve diagnosi a coppie? (Ho pensato a: (n-1)+(n-2)+...+1)) (R.R.)
Credo che lei stia confondendo il problema della diagnosi con quello dell'incasellamento
(dove la sequenza di ingresso che risolve il problema viene costruita saldando insieme
sequenze che risolvono singoli problemi di diagnosi a coppie). Nella diagnosi a coppie
poi il numero di stati iniziali ammissibili è, per definizione, sempre uguale a due.
#31
Con riferimento alla seconda domanda a pag 3.11 del libro Teoria dei Sistemi: Test
commentati e risolti, la risposta A non è corretta perché se un sistema è in forma
minima allora è osservabile, mentre non è detto che sia anche completamente osservabile?
(Wed Dec 22 17:58:42 1999, Alessandro Caselli)
L'osservabilità dello stato iniziale in un sistema non lineare non implica che ciò possa
avvenire con ingresso qualsiasi (completa osservabilità). Abbiamo anche visto, nel caso
dei sistemi a stati finiti (a memoria finita o meno), che l'osservazione dello stato
può richiedere un esperimento multiplo quando il numero di stati iniziali ammissibili
è maggiore di due.
#32
Per risolvere il problema della diagnosi in un sistema a stati finiti in cui Xa contenga più di
2 elementi possiamo realizzare un esperimento multiplo, ogni volta resettando il sistema (per riportarci
nello stato iniziale) e applicando la diagnosi a coppie a 2 opportuni stati. Qual è la lunghezza massima
della sequenza di ingresso totale? (Forse (k-2)+(k-3)+...+1=(k-2)(k-3)/2 ?) (Alessandro Caselli,
Wed Dec 29 21:33:47 1999)
Non possiamo parlare in senso stretto di lunghezza massima della sequenza dato che si tratta di sequenze
applicate separatamente. Se vogliamo considerare la somma delle singole lunghezze occorre ricordare che
in un sistema a stati finiti con n stati solo una coppia di tali stati può richiedere,
per la diagnosi a coppie, una sequenza
di lunghezza n-1, solo due coppie di stati possono richiedere una sequenza di lunghezza n-2
ecc. Per rendersi conto di questo basta osservare la scomposizione dei blocchi delle partizioni di
k-indistinguibilità fino ad arrivare alla partzione di equivalenza nel caso peggiore, quando
cioè la P0 ha due blocchi, la P1 tre blocchi ecc.
#33
Non ho ben chiaro il significato di partizione degli stati iniziali la parzializzazione degli stati finali,
futuri ed attuali. (Tue Jan 25 08:54:16 2000, Matteo Tiraferri)
La domanda è palesemente incompleta e, nel modo in cui è stata formulata, non consente alcuna risposta.
Immagino, tuttavia, che lei intenda fare riferimento alla partizione degli stati iniziali e alla
parzializzazione degli stati finali (o attuali) e futuri indotta da una assegnata funzione di ingresso
in un sistema a stati finiti con riferimento ad un insieme di stati iniziali ammissibili XA.
Se è questo che intende, la partizione indotta su XA dalla sequenza di ingresso
u[0,k] è quella partizione che raggruppa nei propri blocchi tutti gli stati
che danno luogo, con la sequenza di ingresso considerata, alla stessa sequenza di uscita.
La parzializzazione degli stati finali è quella parzializzazione degli stati al tempo finale k
che raggruppa nei propri blocchi gli stati finali corrispondenti a sequenze di uscita identiche in
[0,k] (i blocchi di tale parzializzazione sono, ovviamente, l'immagine nella funzione di
transizione dei blocchi della partizione degli stati iniziali). Discorso analogo per la parzializzazione
degli stati futuri, ossia relativi al tempo k+1.
#34
Esistono relazioni tra sistemi a memoria finita ed autoanelli, ovvero, un
sistema a stati finiti a memoria finita può avere autoanelli o questi ultimi
sono caratteristici dei sistemi a memoria infinita? (Thu Jan 27 14:56:38 2000, G.X.)
Gli autoanelli possono essere presenti tanto nei sistemi a memoria finita che in quelli
a memoria infinita. Questi ultimi sistemi, poi, possono anche essere privi di autoanelli.
| 
