Pagina documente » Informatica, Matematica » Procesarea cunostintelor comune si distribuite

Despre lucrare

lucrare-licenta-procesarea-cunostintelor-comune-si-distribuite
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-procesarea-cunostintelor-comune-si-distribuite


Cuprins

Cuprins
Capitolul I - Cunostinte comune
1.1. Notiuni generale. Exemple
1.2. Prezentarea generala a unor probleme
Capitolul II - Logica modala
2.1. Sintaxa unui limbaj
2.2 Elemente de logica modala
2.3. Descrierea unei Kripke. Exemple
2.4. Semantica unul Iimbaj. Operatori modali
2.5. Interpretarea grafica a unei structuri Kripke
Capitolul III - Cunostinte distribuite
3.1. Notiuni generale. Exemple
3.2. Propietati ale cunoasterii
Capitolul IV - Forme de reprezentare a cunostintelor comune si
distribuite
4.1. Reprezentarea pe baza de evenimente. Structura Aumaun
4.2. Legatura dintre structura Kripke si structura Aumann
Capitolul V - Prezentarea si modelarea unor probleme folosind elemente
de logica modala
5.1. Problema asi1or si optarilor.
5.2. Problema copillor murdari
Capitolul VI - Prezentare aplicatie
Bibliografie

EXTRAS DIN DOCUMENT

?Introducere

În orice domeniu, cunoasterea informatiilor pe care le detine un grup este o conditie esentiala pentru a lua o decizie cat mai corecta.

Aceasta lucrare realizeaza un studio asupra cunostintelor pe care un grup le detine sau le poate detine.

In primul capitol sunt prezentate notiuni despre cunostintele commune unui grup, precum si cateva probleme care folosesc aceste cunostinte.

Capitolul II al lucrarii se axeaza pe logica modala, componentele acesteia si prezinta modalitati de reprezentare cu ajutorul structurilor Kripke.

În capitolul III este prezentata notiunea de cunostinta ditribuita pentru un grup. Tot in acest capitol sunt descries si proprietati ale cunoasterii.

Capitolul al patrulea al lucrarii prezinta modalitatea de reprezentare a cunostintelor commune si distribuite folosind reprezentare pe baza de evenimente prin structura Aumann si legatura dintre structura Aumann si structura Kripke.

Capitolul V contine doua probleme specifice pentru logica modala : problema asilor si optarilor si problema copiilor murdari.

În ultimul capitol este descrisa aplicatia utilizata pentru a reprezenta cunostintele folosind structurile Kripke.Aceasta aplicatie este realizata in limbajul Java. Am ales acest limbaj pentru a realize aplicatia deoarece este un limbaj de programare foarte puternic, dar se poate obtine si o versiune gratis a acestuia.

CAPITOLUL I

CUNOSTINTE COMUNE

1.1 Notiuni generale. Exemple

În general un grup este vazut ca o multime de indivizi (fiinte sau nefiinte) care utilizeaza o baza de cunostinte in comun. Elementele unui grup se numesc agenti. Un asemenea agent poate fi negociator intr-o anumita situatie, un robot de comunicare, mesaje sau buffere de mesaje intr-un calculator, programe logice distincte etc. El trebui sa ia contact nu numai cu faptele ci trebuie de asemenea sa cunoasca date despre ceilalti agenti din grup.

Spre exemplu: daca avem o tranzactie de masini, vanzatorul trebuie sa ia in considerare ce cunoaste cumparatorul despre valoarea masinii, iar acesta la randul lui trebuie sa ia in considerare ce stie vanzatorul cu privire la ceea ce stie cumparatorul cu privire la valoarea masinii si ce nu.

Spre exemplu: toti soferii cunosc ca lumina rosie a semaforului inseamna “stai”, iar lumina verde “pleaca”. Va fi fiecare sofer atunci in siguranta? Raspunsul la aceasta intrebare este nu, pentru ca unii nu cunosc regulile, iar altii care le cunosc nu le respecta. Sau unii soferi considera posibil ca nu toti cunosc regulile si atunci multi dintre ei trec pe lumina rosie.

În exemplele prezentate ne-am referit la o cunostinta comuna.

În general se va nota cu ? o cunostinta. Daca simultan au loc urmatoarele:

? fiecare agent cunoaste ?;

? fiecare cunoaste ca fiecare cunoaste ?;

? fiecare cunoaste ca fiecare cunoaste ca fiecare cunoaste ? etc,

atunci ? devine o cunostinta comuna.

Aceasta notiune a fost la inceput studiata de David Lewis in contextul conventiilor. Lewis a considerat aceasta ca fiind o conventie, ca un fapt trebuie sa fie comun la cati mai multi agenti ai unui grup (spre exemplu, lumina rosie si verde a semeforului, este un fapt cuoscut de cei mai multi soferi si astfel aceasta devine o cunostinta comuna).

John McCarthy in contextul studiului rationamentului in comun, caracteriza cunostinta in comun ca fiind “any fool”; cunoasterea “any fool” este o cunostinta comuna la mai multi membri ai societatii.

Spre exemplu: “Ana intreba pe Bob: “ce gandesti tu despre miscare? ” Referindu-se la cartea X pe care a citit-o. Ana si Bob trebuie sa cunoasca faptul ca miscarea se refera la cartea X; Ana trebuie sa cunoasca, ca Bob cunoaste ca miscarea se refera la cartea X; Bob trebuie sa cunoasca ca, ca Ana cunoaste, ca Bob cunoaste, ca miscarea se refera la cartea X”.

Notam cu ? = “miscarea se refera la cartea X” si atunci aceasta devine cunostinta comuna.

Pentru a urmarii rationamentul cu mai multi agenti, vom prezenta o piesa de cunostere care sa urmareasca aspectele legate de acest lucru.

1.2.Prezentarea generala a unor probleme

Avem urmatoarea piesa de cunoastere: “O mama are n copii care se joaca impreuna. Ea ii anunta ca daca se vor murdari atunci vor urma consecinte severe. Astfel, fiecare copil urmareste sa se pastreze curat, dar fiecaruia i-ar placea sa-l vada pe celalalt murdar. În timpul jocului, o parte din copii, sa zicem k, se murdaresc pe frunte. Fiecare poate sa vada murdaria celuilalt, dar nu se poate vedea pe sine. Între timp vine tatal copiilor, care afirma: ”Cel putin unul dintre voi este murdarit pe frunte”. Presupunem k?1. Tatal copiilor intreba: “Cunoaste vreunul dintre voi ca ca s-a murdarit pe frunte?” si repeta acest lucru de mai multe ori. Presupunem ca fiecare copil este receptiv, inteligent si ca ei raspund simultan la intrebare. Se pune problema ce se intampla in acest caz?”.

Exista o demonstratie a faptului ca la primele k-1 intrebarile sunt “No”, dar apoi la urmatoarea intrebare copiii cu fruntea murdara raspund “Yes”. Demonstratia se face prin inductie:

Sa luam : singurul copil murdar vede ca ceilalti sunt curati, iar afirmatia tatalui spune ca cel putin unul dintre ei este murdar, atunci copilul raspunde cu “Yes”.

Presupunem atunci exista doi copii murdari X si Y. Fiecare raspunde cu “No” la prima intrebare a tatalui. Dar cand Z spune “No”, X intelege ca el este murdar. Astfel a doua intrebare a tatalui X raspunde cu “Yes”. La fel Y.

Presupunem si notam cu X,Y si Z copii murdari.

Copilul X judeca astfel: presupunem ca eu nu m-am murdarit pe frunte. Daca ar fi adevarat atunci conform cazului k=2, la a doua intrebare Y si Z trebuie sa raspunda cu “Yes”, ceea ce nu este adevarat. Prin urmare X afla ca este cel murdar si atunci la a treia intrebare a tatalui el raspunde cu “Yes”. La fel si Y si Z.

În acest exemplu cunostinta comuna este propozitia: p=“cel putin un copil are fruntea murdara”. Daca k>1 atunci fiecare copil poate sa vada cel putin un copil cu fruntea murdara. Deci initial toti copii cunosc p. De aceea, se pare ca afirmatia tatalui p nu este necesara, lucru fals. Daca tatal nu ar face afirmatia p atunci copii nu ar putea spune cine este murdar si cine nu. Vom demonstra acest lucru: vom aplica metoda inductiei dupa q pentru a arata ca indiferent cati copii sunt murdari, toti raspund cu “No” la primele q intrebari.

La prima intrebare toti raspund cu “No”.

Pentru q=1 evident ca raspunsul este “No”. În mod analog ca mai sus se va demonstra ca toti copiii vor raspunde cu “No” la primele q intrebari. Cand tatal pune a q+1 intrebare copilul ii va raspunde tot cu “No”. Din nou el nu stie ca este sau nu murdar pe frunte.

Cand tatal anunta la inceput p aceasta devine o informatie utila pentru fiecare copil. De ce? Sa consideram cazul k=2. Bineinteles ca inainte ca tatal sa anunte p toti cunosc p, insa ceea ce nu se stie este ca “fiecare copil stie ca fiecare cunoaste p”. Daca Mary si Boby sunt doi copi murdari, atunci inainte de afirmatia tatalui, Mary considera ca este posibil ca ea sa nu fie murdara si daca este asa atunci Boby nu cunoaste p. Dupa ce tatal anunta p atunci Mary si Boby cunoaste p si deci daca Boby raspunde cu “No” la prima intrebare atunci Mary deduce ca ea este murdara, deci la a doua intrebare va raspunde cu “Yes”. La fel si Boby.

Asadar exista doi copii murdari, atunci este foarte utila informatia: “fiecare cunoaste p”. Daca exista trei copii murdari este important ca: “fiecare cunoaste ca fiecare cunoaste p” s.a.m.d.

În general daca notam cu faptul ca: “fiecare cunoaste ca fiecare cunoaste ca … ca fiecare cunoaste p” (de k ori) si cu faptul ca este cunostinta comuna, atunci se arata usor ca daca exact k copii sunt murdari, are loc inainte ca tatal sa vorbeasca, dar nu are loc .

Anuntul tatalui conduce la a da copiilor cunostinta comuna p. Se impun cateva observatii:

Daca tatal nu face afirmatia p, atunci ori de cate ori ii intreba pe copii, acestia raspund cu “No” fapt demonstrat mai sus.