Informatica, WEB 2.0 e interfacce cognitive - Parte 1

AA 2011-2012

Prof. Giorgio Poletti

[email protected]

«L'informatica non riguarda i computer più

di quanto l'astronomia riguardi i telescopi.» EDSGER WYBE DIJKSTRA

ROAD MAP DEL CORSO

1. Introduzione al concetto di Informatica

alle origini dei termini

dal dato all’informazione

dalla struttura logica alla struttura topologica

Eulero, Petri, rappresentazione dei problemi e strutturazione della conoscenza

2. Internet e WEB 2.0

evoluzione del WEB

WEB 2.0 semantica e condivisione dei contenuti, dalla tassonomia alla folksonomia

strumenti on-line per la condivisione e co-editazione dell’informazione

3. Human and Machine Cognition (HMC)

interfacce e comunicazione

cognitività, cognetica, stile ed erogonomia

accessibilità e usabilità per progettare artefatti efficienti

« L A D I S U M A N I T À D E L C O M P U T E R

S T A N E L F A T T O C H E , U N A V O L T A

P R O G R A M M A T O E M E S S O I N

F U N Z I O N E , S I C O M P O R T A I N

M A N I E R A P E R F E T T A M E N T E

O N E S T A . »

I S A A C A S I M O V

INTRODUZIONE AL CONCETTO DI INFORMATICA

TECNOLOGIA TECHNOLOGIA dal greco

Div

ien

e

Elettronica Tecnicismo Strumento ostico

TÈCHNÈ

(arte)

LOGÒS

(trattato)

dal tema

LÈGÔ

parlo, dico, descrivo


INFORMATICA

INFORmazione

autoMATICA

Dato

Dato

Relazione

Struttura

Informazione

Informazione

Relazione

CONOSCENZA

«Gli uomini con talento trovano delle soluzioni, i geni scoprono dei problemi.»

Hans Krailsheimer


Problema

INFORMAZIONI

RELAZIONI

+ + WEB

Web e problemi un unico paradigma: da risolutori a solutori


«La mente umana deve prima costruire delle forme in maniera

indipendente, prima di ritrovarle nelle cose.» Albert Einstein

L’hardware non è un limite, bisogna formalizzare di dati e relazioni;

Più le cose sono chiare a noi meno servono tempo e parole per spiegarlo agli altri.

IL COMPUTER DI APOLLO 11 (20 luglio 1969)

• ROM di 74 Bb

• RAM di 4 Kb


A

D

B

C

1

3

4

5

2

Nodo

Arco

GRAFO: struttura relazionale composta da un insieme finito di oggetti (un insieme finito di

punti) detti nodi (o vertici) e da un insieme di relazioni (geometricamente segmenti di retta o

di curva) tra coppie di oggetti detti archi (o spigoli).

𝑮(𝑵,𝑨)


TEOREMA DI EULERO «Condizione necessaria e sufficiente affinché un grafo sia percorribile completamente

partendo da un nodo e ritornandovi passando una volta solamente per ciascun arco è che

esista un percorso fra ogni coppia di nodi e che ogni nodo sia toccato da un numero pari di

archi.»

Mappa di Königsberg ai tempi di Eulero, e la disposizione dei ponti sul fiume Pregel (immagine tratta da Wikipedia)

Problema dei ponti di

Königsberg

Teorema di Eulero


Processo LOGICO della soluzione del problema

Analisi e studio TOPOLOGICO del grafo costruito

A

C

D

D

A

B

C D

«L’errore nasce sempre dalla tendenza dell’uomo a dedurre la causa della conseguenza.»

Arthur Schopenhauer


INFERENZA

Se … allora

Generale

Particolare

INDUZIONE DEDUZIONE

PRINCIPIO DI NON CONTRADDIZIONE

Vero Falso

Rappresentazione, attraverso i grafi, di costrutti logici

INTRODUZIONE AL CONCETTO DI INFORMATICA Esempio di rappresentazione di un problema

IL PROBLEMA «SALVARE CAPRA E CAVOLI»

«Un uomo (T) vuole traghettare da una sponda all'altra

di un fiume un lupo (L), una capra (C) un cavolo (V) su di

una barca capace solo di ospitare l'uomo e il cavolo ed

una sola delle due bestie”.

Tartaglia (libro 16, N. 141) dove scrive anche «e da questo è nasciuto un certo proverbio fra gli huomini,

dicendo in qualche proposito, egli ha salvato la capra e i verzi».

T

LVC

T

LVC

LV

T

LV

V

L

T

CV

T

CL

TC

C

TC

TC

TL

C TV

T

VC

T

LC TC

TC

L

V

TV

TL T

VL

T

T

VL

TC

INTRODUZIONE AL CONCETTO DI INFORMATICA I QUATTRO PROBLEMI FONDAMENTALE

I PONTI DI KÖNIGSBERG

DISTRIBUZIONE, CONTROLLO E MANUTENZIONI DI RETI

elettriche, idriche o stradali

OTTIMIZZAZIONE DI PERCORSI

distribuzione della posta (Chinese Postman's Problem)

IL COMMESSO VIAGGIATORE

FLUSSI DI MERCI

distribuzione merci tra magazzini, clienti e fornitori

MINIMIZZAZIONE DI PERCORSI

percorso più breve tra due città

LE TRE CASE E LE TRE FORNITURE

LAYOUT DI RETI

idriche, stradali, elettriche e circuiti stampati

LAYOUT RETI TELEMATICHE

connessione e collegamento tra computer

I QUATTRO COLORI

TEST DI CONTROLLO

ALLOCAZIONE E ASSEGNAZIONE

registri CPU e frequenze radiotelevisive

circuiti stampati

INTRODUZIONE AL CONCETTO DI INFORMATICA Grafi e Mappe Cognitive

MAPPA COGNITIVA O MAPPA MENTALE (MIND MAP) Modalità di rappresentazione grafica del pensiero, «grafi della mente»,

dal LOGICO al TOPOLOGICO.

Psicologo

TONY BUZAN

Cognitivismo

Mappe mentali

Riflessioni sulle tecniche per

prendere appunti

INTRODUZIONE AL CONCETTO DI INFORMATICA Esempi di Mappe Cognitive

http://inmaps.linkedinlabs.com/

Generatore di mappe concettuali

dei contatti di linkedin




STRUTTURA

GERARCHICA-ASSOCIATIVA

Connessioni gerarchiche

(rami)

Connessioni associative

(associazioni)

Argomento predecessore

XMind

FreeMind

La Mappa Cognitiva

Programmi on-line per

generare mappe cognitive

http://www.xmind.net/

http://freemind.sourceforge.net/wiki/index.php/Main_Page

INTRODUZIONE AL CONCETTO DI INFORMATICA MAPPA CONCETTUALE

MAPPA CONCETTUALE:

Strumento grafico per rappresentare informazioni e conoscenza (anni ‘70)

Josef

Novak

Mappa

concettuale

Costruttivista

Apprendimento

significativo

Apprendimento

meccanico

David

Ausubel

Teorie collegate

alle teorie di

teorizza

Intendono

favorire

contrapposto a

teorie di tipo

principio

Mappa concettuale

della MAPPA

CONCETTUALE

INTRODUZIONE AL CONCETTO DI INFORMATICA MAPPA CONCETTUALE

Mappa

Concettuale

NODI Concettuali

(concetti elementari racchiusi in forme geometriche)

RELAZIONI di tipo connessionista

(uniscono i nodi concettuali con archi con un verso e etichette)

La struttura è RETICOLARE

(non presenta un preciso punto di partenza)

Grafo

Orientato

«Pesato»

INTRODUZIONE AL CONCETTO DI INFORMATICA IL WEB COME MAPPA CONCETTUALE

A concept map from Tim Berners-Lee's original World-

Wide Web proposal, a hypertext system called the

"Mesh", presented in 1989.

http://www.cybergeography.org/atlas/conceptual.html

http://www.cybergeography.org/atlas/conceptual.html


Modalità Dichiarativa Vs Modalità Procedurale

Problema

Informazioni

Relazioni

+

SOLUTORI NON RISOLUTORI

Modalità

Procedurale

Modalità

Dichiarativa

Algoritmo

Motore

Inferenziale

Regole Scopo Dati

Web e problemi un unico paradigma: da risolutori a solutori


CONDIZIONE

DATA

PROBLEM SOLVING (attività di soluzione di un problema)

CONDIZIONE

DESIDERATA

PROBLEM FINDING PROBLEM SHAPING.

Insiemi di procedimenti in

grado di «scoprire»

l’esistenza di un problema

Insiemi di procedimenti in

grado di meglio definire

un problema complesso

Insiemi di procedimenti in grado di

configurare in maniera cognitiva il

problema riconosciuto

PROBLEM SETTING

Insiemi di procedimenti in grado di

descrivere spiegare e comunicare il

problema

PROBLEM TALKING

PRINCIPI DI PROBLEM SOLVING


PRINCIPI DI ALGORITMICA

ALGORITMO ottenere un risultato atteso eseguendo un

insieme ordinato di passi semplici procedimento per

FINITEZZA

EFFETTIVITÀ

ESEGUIBILITÀ

DISAMBIGUO

caratteristiche

concetto di semplice spiega

approccio

matematico

SINTESI: dato un problema f costruire un algoritmo A che

lo risolva

ANALISI: dato algoritmo A e un problema f dimostrare che

A risolve f

CLASSIFICAZIONE (COMPLESSITÀ STRUTTURALE): data T, quantità

di risorse, individuare la classe di problemi solubili da

algoritmi che usano al massimo quelle risorse

ALGORITMO : procedimento che consente di ottenere un risultato atteso eseguendo, in un

determinato predeterminato, un insieme finito di passi semplici; il termine deriva dal nome

del matematico e filosofo arabo MUHAMMAD ALGRTIMO 'L-KHWĀRIZMĪ considerato uno dei primi

autori ad aver teorizzati esplicitamente questo procedimento.


PRINCIPI DI EURISTICA

EURISTICA: parte della ricerca il cui compito è quello di favorire l'accesso a nuovi sviluppi

teorici o a scoperte empiriche (parte dell’epistemologia)

EPISTEMOLOGIA (episteme , «conoscenza certa» «scienza») filosofia della scienza, studia i

fondamenti delle diverse discipline scientifiche.

EURISTICA dal greco εὑρίσκω: scoprire trovare(scovare)

inventare conoscere definizione

Non lineare

approccio

intuito

circostanze

si affida

Nuova

Conoscenza

per generare


RASOIO DI OCCAM

RASOIO DI OCCAM

Principio metodologico

identifica

postulato da

inutilità di aggiungere ipotesi a

quelle giudicate sufficienti

afferma

«A parità di fattori la spiegazione più

semplice è da preferire»

(Guglielmo di Occam)

formulato

Non moltiplicare gli

elementi più del necessario.

in termini di «risoluzione dei problemi»

Non considerare la pluralità

se non è necessario.

È inutile fare con più ciò

che si può fare con meno.

Principio MDL

(Minimum Description Length)

Teoria

dell’informazione

William of Ockham – XIV sec

(Guglielmo di Occam)

«Io esorto a studiare matematica pur chi si accinga a divenire avvocato o economista, filosofo o letterato; perché io credo e spero che non gli sarà inutile saper bene ragionare e chiaramente esporre.»

Alessandro Padoa


PROGRAMMAZIONE LOGICA E LOGICA DI I LIVELLO

LINGUAGGI DICHIARATIVI

(O LOGICI)

Logica di

Primo Livello

Formale Meccanico

Sistema formale

modalità

Esprimono enunciati Conseguenze logiche


PROGRAMMAZIONE LOGICA E

LOGICA DI I LIVELLO

LINGUAGGI DICHIARATIVI

(O LOGICI) Descrivono

Insieme di relazioni

Istruzione Clausola

Dati

Risultato desiderato diventa

Descrive relazioni tra dati

Non c’è un ordine prestabilito per

l’esecuzione delle clausole

Parole

Discorso

Verbi


LE RETI DI PETRI (P-RETI) E I SISTEMI DISTRIBUITI DISCRETI

SISTEMA DISTRIBUITO

WEB SISTEMA DISCRETO

RETI DI PETRI (P-RETI) SISTEMA DISTRIBUITO DISCRETO descrive la struttura

sistema in cui l’elaborazione delle informazioni è

distribuita su più entità (ad esempio computer)

sistema il cui stato cambia ad intervalli di tempo

discreti (per DISCRETO si intende un insieme composto

di elementi distinti, separati tra di loro)

Modellazione di processi

Modellazione di comunicazioni e interazioni tra

processi paralleli e interconnessi

Grafo, orientato e bipartito


LE RETI DI PETRI (P-RETI): MAPPA CONCETTUALE ESSENZIALE

RETI DI PETRI

(P-RETI) GRAFO

è

PROCESSI

descrive

COMPONENTI INTERAZIONI

in termini di

NODI ARCHI

composto da

ORIENTATO BIPARTITO di tipo


LE RETI DI PETRI (P-RETI) E I COMPONENTI

Una P-Rete è una tripla N = (P, T, F)

P è un insieme dei posti,

T è un insieme di transizioni

F è una relazione di flusso P e T sono due insiemi finiti

RETI DI PETRI (P-RETI) GRAFO è

NODI

ARCHI

composto da

ORIENTATI sono

POSTO TRANSIZIONE a

collegano

di tipo

STATO

(N≥0) MARCHE

(TOKEN)

con

rappresentato


LE RETI DI PETRI (P-RETI): STATO-TRANSIZIONE

POSTO

POSTO

POSTO TRANSIZIONE

arco

arco

arco

Marca o

Token

STATO


LE RETI DI PETRI (P-RETI): STATO-TRANSIZIONE

POSTO

POSTO

POSTO TRANSIZIONE

arco

arco

arco

INPUT PER LA TRANSIZIONE

OUTPUT PER LA

TRANSIZIONE

OUTPUT PER LA

TRANSIZIONE


LE RETI DI PETRI (P-RETI): MECCANISMO DI TRANSIZIONE

POSTO

POSTO

POSTO TRANSIZIONE

arco

arco

arco

INPUT PER LA TRANSIZIONE

OUTPUT PER LA

TRANSIZIONE

OUTPUT PER LA

TRANSIZIONE


LE RETI DI PETRI (P-RETI): CONCETTO DI TRANSIZIONE

Le TRANSIZIONI agiscono sui TOKEN

REGOLA

secondo

REGOLA di SCATTO (firing)

detta

se può

Scattare ABILITATA è

tutti i TOKEN necessari nei POSTI di INPUT sono

se

TRANSIZIONE


LE RETI DI PETRI (P-RETI): CONCORRENZA

CONCORRENZA: una transizione T ha più posti di input

TRANSIZIONE T

POSTO DI INPUT PER T




LE RETI DI PETRI (P-RETI): CONFLITTO

CONFLITTO: un posto è INPUT per più di una transizione T

TRANSIZIONE TN

POSTO DI INPUT PER

T1, T2,…TN TRANSIZIONE T1

TRANSIZIONE T2


LE RETI DI PETRI (P-RETI): CONFUSIONE

CONFLITTO: un posto è INPUT per più di una transizione T e una transizione ha più posti di

INPT; CONFLITTO = CONCORRENZA+CONFLITTO

TRANSIZIONE T3

POSTO DI INPUT

TRANSIZIONE T1

TRANSIZIONE T2

POSTO DI INPUT


LE RETI DI PETRI (P-RETI): CARATTERISTICE

RETE DI PETRI

• RAGGIUNGIBILITÀ (REACHABILITY)

• LIMITATEZZA (BOUNDEDNESS)

• SICUREZZA (P-NET SAFE)

• VITALITÀ (LIVENESS)


LE RETI DI PETRI (P-RETI): RAGGIUNGIBILITÀ

Data una MARCATURA INIZIALE M0 in una rete di Petri G si indica con R(G,M0) l’insieme delle MARCATURE RAGGIUNGIBILI a partire da M0.

Una MARCATURA Mq è RAGGIUNGIBILE se esistono scatti che la rendono una marcatura possibile a partire da M0.

ne deriva che PROBLEMA DELLA RAGGIUNGIBILITÀ

Mq R(G,M0)?

si pone il

ESEMPIO porte aperte e ascensore non presente

SOTTO QUALI CONDIZIONI Mq è uno stato sbagliato? Non può e non deve essere raggiungibile?


LE RETI DI PETRI (P-RETI): RAGGIUNGIBILITÀ

GRAFO DI RAGGIUNGIBILITÀ: grafo in cui i nodi sono le possibili marcature e gli archi le transizioni che modificano una marcatura

T1

T2

T3

0,0

1,0

2,0

2,1

2,2

0,1

1,1

1,2

0,2

T2

T3

T1

GRAFO DI RAGGIUNGIBILITÀ è un buon metodo per trovare gli stati "sbagliati” ovvero che non devono essere raggiunti (ad esempio barriere alzate e treno in passaggio)

GRAFO DI RAGGIUNGIBILITÀ nella maggior parte dei casi sostituito da algoritmi per l’individuazione di stati «sbagliati»

T1

T3

T3

T1

T1

T2

T2

T2

T1

T3


LE RETI DI PETRI (P-RETI): LIMITATEZZA

POSTO LIMITATO (K-LIMITATO): k è il numero massimo di token nel posto per una qualsiasi marcatura possibile della rete

P-RETE LIMITATA SE OGNI POSTO È LIMITATO

M0

Mq

ESEMPIO DI P-RETE 2-LIMITATA


LE RETI DI PETRI (P-RETI): LIMITATEZZA SICUREZZA

ESEMPIO DI P-RETE 1-LIMITATA

UNA RETE 1-LIMITATA (K-LIMITATA CON K=1) SI DICE SICURA

M2

M3

M0


LE RETI DI PETRI (P-RETI): VITALITÀ

RETE VIVA Mq marcatura qualsiasi

raggiungibile da M0

se fare scattare una transizione T

qualsiasi a seguito di una qualsiasi sequenza di scatti

è sempre

possibile

P-RETE È K-LIVE ogni transizione T è k-Live

Gradi di vitalità di una transizione T in una P-Rete

0 – L0 Live T non può scattare in nessuna marcatura raggiungibile

1 – L1 Live esiste almeno una marcatura raggiungibile in cui T può scattare

2 – L2 Live per ogni numero intero K Esiste almeno una marcatura raggiungibile in cui T può scattare K volte

3 – L3 Live esiste almeno una marcatura raggiungibile in cui T può scattare infinite volte

4 – L4 Live T può scattare in ogni marcatura raggiungibile

TRANSIZIONE MORTA

TRANSIZIONE VIVA


LE RETI DI PETRI (P-RETI): RETI NON DETERMINISTICHE

RETE NON-DETERMINISTICA

quando ci sono più transizioni abilitate,

allo stesso tempo, qualsiasi può scattare

non è garantito che una transizione

abilitata scatti

UNA TRANSIZIONE ABILITATA PUÒ

SCATTARE

immediatamente dopo un periodo di attesa indefinito

(purché permanga abilitata) mai

se

significa


LE RETI DI PETRI (P-RETI): TIPOLOGIE PRINCIPALI

• MACCHINE A STATI FINITI (SM: State Machine)

• GRAFO MARCATO (MG: Marked Graph)

• SCELTA LIBERA (FC: Free Choice)

• SCELTA ASIMMETRICA (ASYMMETRIC CHOICE - AC)


LE RETI DI PETRI (P-RETI): MACCHINA A STATI FINITI (SM: STATE MACHINE)

MACCHINA A STATI FINITI, rete in cui ogni TRANSIZIONE ha un solo arco in entrata e

un solo arco in uscita

ESEMPI DI POSSIBILI CONFIGURAZIONI • Nessuna CONCORRENZA

• Nessun CONFLITTO


LE RETI DI PETRI (P-RETI): GRAFO MARCATO (MG: MARKED GRAPH)

GRAFO MARCATO (è la rete duale della Macchina a Stati Finiti)

rete in cui ogni TRANSIZIONE ha un solo arco in entrata e un solo arco in uscita

ESEMPIO DI POSSIBILE CONFIGURAZIONE • Possibile CONCORRENZA

• Nessun CONFLITTO


LE RETI DI PETRI (P-RETI): SCELTA LIBERA (FC: FREE CHOICE)

SCELTA LIBERA, rete in cui ogni arco è o l’unico che esce da un Posto o l’unico

che entra in una Transizione

ESEMPIO DI POSSIBILE CONFIGURAZIONE

• Possibile CONCORRENZA

• Possibile CONFLITTO

• CONFLITTO E CONCORRENZA MAI CONTEMPORANEAMENTE

1:1

2:1

2:1

1:3

1:3

1:3

2:1

2:1

1:1

1:1


LE RETI DI PETRI (P-RETI): SCELTA ASIMMETRICA (AC: ASYMMETRIC CHOICE)

SCELTA ASIMMETRICA, rete in cui se 2 Posti (A e B) sono Posti di Input per una

stessa Transizione, l’insieme delle transizioni per A è Posto di Input contiene le

transizioni per cui B è Posto di Input

ESEMPIO DI POSSIBILE CONFIGURAZIONE

• Possibile CONCORRENZA

• Possibile CONFLITTO

• CONFLITTO + CONCORRENZA (CONFUSIONE) MAI SIMMETRICAMENTE

A

B

Concorrenza Conflitto


LE RETI DI PETRI (P-RETI): RETI TEMPORIZZATE

RETI DI PETRI (classiche)

Non includono Il concetto di tempo

Struttura logica di un sistema

Evoluzione temporale di un sistema

non descrivono

RETI DI PETRI TEMPORIZZATE

si estendono attraverso

Transizione = Evento Transizione = Attività del Sistema

Posto = Attività del Sistema

Istantaneo

Tmin –Tmax

(Tempo di scatto se

non si disabilita)

Tempo non nullo (attività durata)

SCATTO

• Tutti i gettoni vengono rimossi dai posti di Input

• Transizione in scatto per tutta la durata

• Fine in scatto, gettoni nei posti di Output

Posto Durata (Tempo necessario per l’attività)

descrivono


«Il caso è la somma delle nostre ignoranze.» Pierre Laplace

Sierpinski Triangle

(Frattale)


LE RETI DI PETRI (P-RETI) - 2 PROBLEMI CLASSICI

PROBLEMA DEI 5 FILOSOFI AFFAMATI

(dining philosophers problem, Dijkstra)

Schematizza problemi di concorrenza e condivisione di risorse

Schematizza problemi analoghi a quelli di un help desk informatizzato

PROBLEMA DEL BARBIERE CHE DORME


LE RETI DI PETRI (P-RETI) - PROBLEMA DEL BARBIERE CHE DORME

Schematizza problemi analoghi a quelli di un help desk informatizzato

PROBLEMA DEL BARBIERE CHE DORME

Un barbiere possiede un negozio con una sola sedia da lavoro e un certo

numero limitato di posti per attendere. Se non ci sono clienti il barbiere

dorme altrimenti, all'arrivo del primo cliente il barbiere si sveglia ed

inizia a servirlo. Se dovessero sopraggiungere clienti durante il periodo

di attività del barbiere, essi si mettono in attesa sui posti disponibili. Al

termine dei posti di attesa, un ulteriore cliente viene scartato.

Una corretta programmazione concorrente deve far "dormire" il barbiere

in assenza di clienti, attivare il barbiere sul primo cliente al suo arrivo e

mettere in coda tutti i successivi clienti tenendoli inattivi.


LE RETI DI PETRI (P-RETI) - PROBLEMA DEL BARBIERE CHE DORME




Cinque filosofi (nella versione più nota) sono stabilmente seduti a tavola di fronte ad un piatto ed a due

bacchette, condivise con i loro vicini. In pratica sul tavolo ci sono 5 piatti (pieni di riso e che si suppongono

contenere una quantità infinita di cibo) e 5 bacchette; i filosofi alternano momenti in cui pensano e

momenti in cui mangiano. Per mangiare devono prendere le due bacchette accanto al loro piatto e

mangiare mentre durante la meditazione devono riporre le bacchette sul tavolo. Il numero di bacchette

impedisce a tutti i filosofi di mangiare contemporaneamente.

• Un filosofo può prendere solo le due bacchette che stanno alla sua destra e alla sua sinistra, una per

volta, e solo se sono libere, non può sottrarre la risorsa bacchetta ad un altro filosofo che l'ha già

acquisita e sta mangiando (no preemption, non c’è predominanza).

• Finché non riesce a prendere le bacchette, il filosofo deve aspettare affamato. Quando invece è sazio

posa le bacchette al loro posto e si mette a pensare per un certo tempo.

Una corretta programmazione concorrente deve essere in grado di far mangiare alternativamente tutti i

filosofi evitando che qualcuno in particolare soffra di starvation1 ed evitando che si verifichino stalli in fase

di "acquisizione delle bacchette".

(1) STARTVATION, letteralmente “inedia”, ma in informatica lo stato di un processo pronto per essere eseguito ma

che non riesce ad ottenere le risorse di cui necessita.


LE RETI DI PETRI (P-RETI) - PROBLEMA DEI DUE FILOSOFI AFFAMATI




1. Nietzsche ed Eraclito mangiano spesso assieme

2. Siedono attorno ad un tavolo rotondo e hanno, ognuno, a disposizione un piatto di cibo e due singole bacchette

sono collocate ai lati dei loro piatti

3. Sempre, o pensano o mangiano

4. Quando uno dei due comincia ad avere fame cerca di prendere possesso delle bacchette alla sua destra e alla sua

sinistra, in ordine arbitrario

5. Qualora riesca a prenderle entrambe, mangia per un po'. Successivamente depone le bacchette e si rimette a

pensare

6. Nessuno dei due è in grado di mangiare con una singola bacchetta o con le mani

7. Il problema consiste nel far in modo che entrambi i filosofi riescano a cibarsi e pensare periodicamente

f1 f2

b1

b2


f1 f2

b1

b2

Acquisisce le

bacchette

Rilascia le

bacchette

MANGIA PENSA

Acquisisce le

bacchette

Rilascia le

bacchette

Stati del Filosofo Marcatura Iniziale

Posto del filosofo che

pensa


mangia



f1 f2

b1

b2

Acquisire le

bacchetta 1

Marcatura Iniziale

Posto della bacchetta 1 sul tavolo


pensa

Posto della bacchetta 2

sul tavolo

Posto della bacchetta 1 in

mano al filosofo

Posto della bacchetta 2 in

mano al filosofo

Acquisire le

bacchetta 1


mangia

Acquisire le

2 bacchette



f1 f2

b1

b2

b1 f1

b1 f1 t1

P-rete 3-limitata

t3 b1 f1 b2

b2 f2

b2 f2 t4

t6 b2 f2 b1

t2 b1 f1 b2

t5 b2 f2 b1



f1 f2

b1

b2

b1 f1

b1 f1 t1

t3 b1 f1 b2

b2 f2

b2 f2 t4

t6 b2 f2 b1

t2 b1 f1 b2

t5 b2 f2 b1

t1 e t4 : transizione attiva con 1 TOKEN per ogni POSTO DI INPUT

(il filosofo acquisisce la bacchetta alla sua sinistra)

t2 e t5 : transizione attiva con 3 TOKEN nel POSTO DI INPUT

(il filosofo acquisisce la bacchetta alla sua destra)

t3 e t6 : transizione attiva con 3 TOKEN nel POSTO DI INPUT

(il filosofo le smette di magiare e rilascia le bacchette)

$



f1 f2

b1

b2

b1 f1

b1 f1 t1

t3 b1 f1 b2

b2 f2

b2 f2 t4

t6 b2 f2 b1

t2 b1 f1 b2

t5 b2 f2 b1

Posti delle Risorse (i filosofi pensa e le bacchetta sono sul tavolo)

Posti dell’Acquisizione (i filosofi acquisiscono una bacchetta)

Posti della utilizzo delle Risorse (i filosofi mangiano)



f1 f2

b1

b2

b1 f1

b1 f1 t1

t3 b1 f1 b2

b2 f2

b2 f2 t4

t6 b2 f2 b1

t2 b1 f1 b2

t5 b2 f2 b1

P-rete 3-limitata



MARCATURA, un insieme di 8 valori, in ordine, 1 se ci sono TOKEN 0 se

non ci sono nello stato i. Ci sono in questo caso 6 marcature possibili.

[1,1,1,1,0,0,0,0]

[0,0,1,1,1,0,0,0]

t1

[1,1,0,0,0,1,0,0]

t4

[0,1,0,0,0,0,0,1]

t5

t2

[0,0,0,1,0,0,1,0]

t3

t6

LE RETI DI PETRI (P-RETI)

PROBLEMA DEI DUE FILOSOFI AFFAMATI

b1 f1

b1 f1 t1

t3 b1 f1 b2

b2 f2

b2 f2 t4

t6 b2 f2 b1

t2 b1 f1 b2 t5 b2 f2 b1

1 2 3 4

5 6

b1 f1

b1 f1 t1

t3 b1 f1 b2

b2 f2

b2 f2 t4

t6 b2 f2 b1

t2 b1 f1 b2 t5 b2 f2 b1

7 8

Configurazione M0


LE RETI DI PETRI (P-RETI)

PROBLEMA DEI DUE FILOSOFI AFFAMATI

Cappuccetto Rosso Mamma

Nonna malata

Lupo

T1: Raccomandazione

Cappuccetto Rosso

nel bosco con le focacce

T2: Incontro

Lupo informato Cappuccetto Rosso

a frutti di bosco

T3: Raccolta

Cappuccetto Rosso

casa della Nonna

con le focacce

T4: Corre

T5: Mangia

Lupo travestito

A casa della nonna

Cappuccetto Rosso

con cestino di frutti di bosco

e le focacce a casa della nonna

Lupo a

casa della Nonna

T5: Dialogo

Cappuccetto Rosso

terrorizzato

Lupo

smascherato

T6: Mangia

Lupo che

russa

Cacciatore

T6: Accorrere

Lupo che

dorme

Cacciatore

a casa della nonna

Lupo morto Cacciatore

con coltello

T7: Squartamento

AA 2011-2012

Prof. Giorgio Poletti

[email protected]

«Ci sono soltanto due possibili conclusioni:

se il risultato conferma le ipotesi, allora hai

appena fatto una misura. Se il risultato è

contrario alle ipotesi, allora hai fatto una

scoperta.» ENRICO FERMI

Date post:	11-Mar-2016
Category:	Documents
Upload:	giorgio-poletti
View:	216 times
Download:	0 times

Informatica, WEB 2.0 e interfacce cognitive - Parte 1

Documents