gli automi mi interessano una cifra...

[absinthe]

salve,
apro sto post in base a quanto accennato in un altro post nella sezione gnu/linux. Quello che mi incuriosisce è: che vuol dire che dato un certo punto di partenza possono seguire percorsi diversi?
detta così sembrano proprio delle catene di markov... illuminatemi

M

[Bart]

Il discorso è un po' lungo.
Cercherò di farti un riassunto veloce veloce, ma se ti interessa l'argomento ti consiglio di prenderti un buon libro o di cercare documentazione in rete.
Esistono vari tipi di automi. Quelli di cui parlavamo prima sono i cosiddetti automi a stati finiti, che rappresentano una classe di linguaggi detti regolari.
Tra questi automi a stati finiti esistono i DFA (Deterministic Finite Automaton), ossia gli automi a stati finiti deterministici e gli NFA (Nondeterministic Finite Automaton), ossia gli automi non deterministici. La differenza tra i due è semplice: mentre con i primi, partendo da uno stato iniziale, se leggiamo un input, in un detrminato istante della lettura ci troviamo sempre in un solo stato. Al contrario con gli NFA possiamo prendere contemporaneamente percorsi diversi e non appena arriviamo alla completa lettura degli input, possiamo terminare i percorsi alternativi. Come puoi vedere quest'ultimi automi sono ottimi per compiere ricerche di stringhe all'interno di file di testo (ad esempio) perché permettono una ricerca parallela della stringa e ne consegue una ricerca più rapida rispetto a quella che si otterrebbe lavorando con un DFA.
Prendi per esempio questo automa:



Questo è un DFA. Le tre "palline" rappresentano i nostri stati. La freccia"start" rappresenta lo stato di partenza mentre il cerchio doppio rappresenta lo stato finale o riconoscitore. Se vuoi che una stringa sia riconosciuta da un automa, questa deve sempre trovarsi in uno stato riconoscitore a fine lettura. I numeri sopra le frecce sono il nostro alfabeto che in questo caso è formato solo dai simboli {0,1}.
Il ragionamento è il seguente: partendo dallo stato di partenza q1 te puoi andare negli altri stati in base al simbolo che leggi: ad esempio se leggi 1 rimani in q1 mentre se leggi zero vai in q2.
Se fosse un NFA dovresti avere più possibilità di scelta, ad esempio mettendo uno zero accanto all'1 che c'è sull'arco che da q1 riporta in q1, in modo tale che leggendo zero quando si è nello stato di partenza (q1) tu possa andare sia in q1 sia in q2. Come vedi ti ritroveresti in due stati allo stesso momento (NFA).
Di automi ne esistono tanti altri, tra cui spiccano infine le MdT, ossia le macchine di Turing. Se ti interessano gli argomenti cerca in rete, oppure (ancora meglio) comprati un buon libro. Ciao

[Paoletta]

http://it.wikipedia.org/wiki/Automa_(informatica)


Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D.: Automi, linguaggi e calcolabilità; I ed. it.; Addison Wesley

[NaiC]

Uhm... non so perchè ma questa spiegazione mi fa pensare tanto alle macchine sequenziali a stati finiti che studiavo anni fa...

C'è da dire solo una cosa... l'input, come lo descrivi tu è troppo deterministico... gli stati cambiano non solo in base all'input che si riceve in un dato momento, ma anche dallo stato in cui ci si trovava precedentemente...

Un'applicazione pratica di queste macchinette... L'ascensore di casa, La macchinetta del caffè che magari restituisce anche il resto... ecc. ecc.

Tchuss!!

[absinthe]

NaiC ora mi informo meglio ma se prendi il grafo che hai fatto tu e al posto degli 1 e 0 metti un qualsiasi reale x appartenente a [0;1] ottieni una ctena di markof... un pò come la logica fuzzy è una generalizzazione della logica binaria, così una catena di markof a prima vista mi pare un generalizzazione degli automi... unico vincolo: la somma dei pesi w(ij) di ogni singolo arco ij deve essere tale per cui:

somma w(i,j) con j=1,...,n per ogni i deve essere 1.


l'unica cosa è che una catena di markof non prevede la presenza in due stati in contemporanea... cioè pur essendo stocastica a sto punto direi che non è "non deterministica" se ho ben capito... o meglio prevede che in un dato istante tu ti possa trovare in QUALSIASI stato ma non in maniera determinata (scusate ma in questo caso non determinata=statistica...ghgh che casino)

fico però ... non so se vale la pena comprarmi un libro intero... però appena trovo un secondo scarico roba sa sciencedirect!!! (tra l'altro l'evoluzione delle catene di markof -gli HMM- mi servono per lavoro...)

ciaux,
M

[absinthe]

C'è da dire solo una cosa... l'input, come lo descrivi tu è troppo deterministico... gli stati cambiano non solo in base all'input che si riceve in un dato momento, ma anche dallo stato in cui ci si trovava precedentemente...
Tchuss!!

esatto sono tutti sistemi dinamici a memoria ridotta idem per le catene che conoscevo io... (per evitare di dover comprare 6 quintali di ram

[zeroday]

Oddio... ste cose me lo sogno la notte

fra 1 settimana esame di architettura e reti logiche (di recupero )

moore, mealy, asincrone... T_T

[IceSlack]

ma di che **w+!K!@ state parlando?

che siete scenziati della nasa?

mi fate una intro?

[absinthe]

ma di che **w+!K!@ state parlando?

che siete scenziati della nasa?

mi fate una intro?

se io divento scenziato della nasa tu a quell'ora sarai già premio nobel per la fisica e l'economia (tutti e due nello stesso anno

no sono degli aggeggi matematici che si chiamano sistemi dinamici... o meglio quella è la base e si studia all'università nella facoltà di ingegneria in un corso che si chiama "teoria dei sistemi" oppure con un nome simile... magari se compari i programmi delle varie facoltà vedi un pò dove è spiegata e con che n nome la "spacciano".

sono dei sistemi per analizzare processi in evoluzione nel tempo... che no so.. ci fai di tutto: con sti automi non so cosa ci facciano, con le catene di markof un mio amico c'ha modellato l'andamento statistico (=atteso) della stratigrafia di un sito, con i modelli dinamici deteministici ci si modellano i sistemi biologici (batteri ed altre menate), ci si simulano i comportamenti dei corpi in movimento (vedi programmi come adams...) e ci mandi pure i satelliti nello spazio... magari un giorno ci fai pure una frittata con le cipolle :P

M

[IceSlack]

ma di che **w+!K!@ state parlando?

che siete scenziati della nasa?

mi fate una intro?

se io divento scenziato della nasa tu a quell'ora sarai già premio nobel per la fisica e l'economia (tutti e due nello stesso anno

no sono degli aggeggi matematici che si chiamano sistemi dinamici... o meglio quella è la base e si studia all'università nella facoltà di ingegneria in un corso che si chiama "teoria dei sistemi" oppure con un nome simile... magari se compari i programmi delle varie facoltà vedi un pò dove è spiegata e con che n nome la "spacciano".

sono dei sistemi per analizzare processi in evoluzione nel tempo... che no so.. ci fai di tutto: con sti automi non so cosa ci facciano, con le catene di markof un mio amico c'ha modellato l'andamento statistico (=atteso) della stratigrafia di un sito, con i modelli dinamici deteministici ci si modellano i sistemi biologici (batteri ed altre menate), ci si simulano i comportamenti dei corpi in movimento (vedi programmi come adams...) e ci mandi pure i satelliti nello spazio... magari un giorno ci fai pure una frittata con le cipolle :P

M

grazie per avermi preso per il **** scusa s enon faccio l'universita' e come diresti te sono un povero imbecille vabbe'..............

comunque grazie della spiegazione........

[absinthe]

perchè preso per il c***? non volevo mica farlo... dici per la battuta sulla nasa?
(poi magari l'e.s.a. era meglio nn volevo mica sfottere... era per rispondere con una battuta alla tua battuta...

e la frittata di cipolle va a finire che ce la fanno davvero (anche i caseifici usano i sistemi dinamici -in paticolare la teoria di controllo- per gestire i macchinari per la cagliatura!!! insomma: qualunque cosa va in automatico nell'industria bene o male è gestita da uno di questi aggeggi...)

M

[IceSlack]

perchè preso per il c***? non volevo mica farlo... dici per la battuta sulla nasa?
(poi magari l'e.s.a. era meglio nn volevo mica sfottere... era per rispondere con una battuta alla tua battuta...

e la frittata di cipolle va a finire che ce la fanno davvero (anche i caseifici usano i sistemi dinamici -in paticolare la teoria di controllo- per gestire i macchinari per la cagliatura!!! insomma: qualunque cosa va in automatico nell'industria bene o male è gestita da uno di questi aggeggi...)

M

ok ora ho capito.........