ΠΠ΅ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡΠΈΡ ΠΈ ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡΠΈΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΡΠ
Π£ΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠ΅ 1. ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ Π§' Π°Π»Π³Π΅Π±ΡΡ? ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΠΎΠ»Π½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ ΠΎΡΠ½ΠΎΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΎΠ±ΡΠ΅ΠΊΡΠ½ΠΎΠ³ΠΎ Π°Π½Π°Π»ΠΈΠ·Π°. Π Π±Π°Π·ΠΎΠ²ΡΠΌ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡΠΌ ΠΎΠ±ΡΠ΅ΠΊΡΠ½ΠΎΠ³ΠΎ Π°Π½Π°Π»ΠΈΠ·Π° ΠΈ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΡΡΠΎΠΉΠΊΠΈ «ΠΈΠΌΡ, Π΄Π΅Π½ΠΎΡΠ°Ρ ΠΈ ΠΊΠΎΠ½ΡΠ΅ΠΏΡ» ΠΎΠ±ΡΠ΅ΠΊΡΠ° ΠΎΡΠ½Π΅ΡΠ΅Π½Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅: ΠΡΠΎ ΡΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠ΅ ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠΈΠ²Π°Π΅Ρ Π°Π΄Π΅ΠΊΠ²Π°ΡΠ½ΠΎΡΡΡ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄Π° ΠΎΡ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΊ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡΠΌ Π°Π»Π³Π΅Π±ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠ½ΠΎΠ³ΠΎ Π°Π½Π°Π»ΠΈΠ·Π°: Π£ Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ ΠΊΠΎΡΠΎΡΡΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡΡΡ ΠΊΠΎΠ½ΡΠ΅ΠΏΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² Con, = (Π , Ρ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ΅ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡΠΈΡ ΠΈ ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡΠΈΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΡΠ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΠ° ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π΅ Π±Π°Π·ΠΎΠ²ΡΡ Π»ΠΎΠ³ΠΈΠΊΠΎ-ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΡ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π΄Π»Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ Π΄Π΅Π½ΠΎΡΠ°Ρ ΠΈ ΠΊΠΎΠ½ΡΠ΅ΠΏΡΠΎΠ² ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΏΠΎΡΡΡΠΎΠ΅Π½Π° Π°Π»Π³Π΅Π±ΡΠ°, Π²ΠΊΠ»ΡΡΠ°ΡΡΠ°Ρ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ Π½Π°Π΄ Π½ΠΈΠΌΠΈ. ΠΠ°ΠΆΠ΄Π°Ρ ΠΈΠ· ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ ΠΈΠΌΠ΅Π΅Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΉ ΠΏΡΠΈΠΎΡΠΈΡΠ΅Ρ ΠΈ Π°ΡΠ½ΠΎΡΡΡ, ΡΠ²ΡΠ·Π°Π½Π½ΡΠ΅ Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΌΠΈ Π΄ΠΎΠΏΡΡΡΡΠΈΠΌΡΠΌΠΈ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΡΠΌΠΈ Π΄Π΅Π½ΠΎΡΠ°ΡΠΎΠ² ΠΈ ΠΊΠΎΠ½ΡΠ΅ΠΏΡΠΎΠ² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ ΠΈΡ Π΄Π΅ΡΠ°Π»ΠΈΠ·Π°ΡΠΈΠΈ, ΡΠΊΠ·Π΅ΠΌΠΏΠ»ΡΡΠΈΠ·Π°ΡΠΈΠΈ, Π°Π³ΡΠ΅Π³Π°ΡΠΈΠΈ ΠΈ Π΄Ρ.
ΠΠ±ΡΠ΅ΠΊΡΠ½ΡΠΉ Π°Π½Π°Π»ΠΈΠ· ΠΊΠ°ΠΊ ΠΏΡΠΎΡΠ΅ΡΡ Π΄Π΅ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡΠΈΠΈ ΠΡΠ Π±Π°Π·ΠΈΡΡΠ΅ΡΡΡ Π½Π° Π°Π»Π³Π΅Π±ΡΠ΅ Π°Π½Π°Π»ΠΈΠ·Π° ΠΎΠ±ΡΠ΅ΠΊΡΠ°, Π²ΠΊΠ»ΡΡΠ°ΡΡΠ΅ΠΉ Π² ΡΠ΅Π±Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π΄Π΅Π½ΠΎΡΠ°ΡΠ° ΠΡΠ ΠΈ ΡΠΎΡΠΌΠ°Π»ΡΠ½ΡΡ ΠΈΡ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΉ Π² Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ ΠΎΡ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΡ ΠΎ Π½ΠΈΡ Π·Π½Π°Π½ΠΈΠΉ. ΠΠ»Π³Π΅Π±ΡΠ° ΡΡΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² 0'=(0ΠΡ …, Π,) ΠΈ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΎΠ±ΡΠ΅ΠΊΡ Π, = Π,{Name, Den, Con,) Π·Π°Π΄Π°Π΅ΡΡΡ ΡΡΠΎΠΉΠΊΠΎΠΉ ΠΈΠΌΡ, Π΄Π΅Π½ΠΎΡΠ°Ρ ΠΈ ΠΊΠΎΠ½ΡΠ΅ΠΏΡ Name, Denh Con, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ; ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡΠΎΠ² /= (Ih 12. β’β’β’, /Ρ); ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π΄Π΅ΠΉΡΡΠ²ΠΈΠΉ (Action) Π' =(Π, ΠΡ …, Π")
ΠΊΠ°ΠΊ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ Π½Π°;; ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π; ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΏΡΠ΅Π΄ΠΈΠΊΠ°ΡΠΎΠ² Π =(Π , Π 2…
Π Π³)Ρ Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ ΠΊΠΎΡΠΎΡΡΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡΡΡ ΠΊΠΎΠ½ΡΠ΅ΠΏΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² Con, = (Π ,Ρ Π ,2, … Pis) Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ Π΄Π΅Π½ΠΎΡΠ°Ρ.
Π Π±Π°Π·ΠΎΠ²ΡΠΌ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡΠΌ ΠΎΠ±ΡΠ΅ΠΊΡΠ½ΠΎΠ³ΠΎ Π°Π½Π°Π»ΠΈΠ·Π° ΠΈ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΡΡΠΎΠΉΠΊΠΈ «ΠΈΠΌΡ, Π΄Π΅Π½ΠΎΡΠ°Ρ ΠΈ ΠΊΠΎΠ½ΡΠ΅ΠΏΡ» ΠΎΠ±ΡΠ΅ΠΊΡΠ° ΠΎΡΠ½Π΅ΡΠ΅Π½Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅:
1) Π΄Π΅ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡΠΈΠΎΠ½Π½ΠΎΠ΅ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π΄Π΅Π½ΠΎΡΠ°ΡΠ° Π΄Π»Ρ ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ²:
Π³Π΄Π΅ Oij = Oy (Namey, Deny, Cony), V/ Cony = Π‘ΠΎΠΏ" uDeny = Den, ΠΈ Π΄Π»Ρ Π½Π΅ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ²:
Π³Π΄Π΅ ΠΡ = Oij (Name, j, Deny, Con Ρ), Vj Π‘ΠΎΡ = 0, uDetiy = Den,.
2) ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡΠΈΠΎΠ½Π½ΠΎΠ΅ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π΄Π΅Π½ΠΎΡΠ°ΡΠ° Π΄Π»Ρ ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ²:
Π³Π΄Π΅ Π, = Oj (Name" Den" Con,), V/ Con, = Conijt Den, = uDeny ΠΈ Π΄Π»Ρ Π½Π΅ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ²:
Π³Π΄Π΅ Oi = Π,(Namej, Den" Con), Con, = 0, Den, = uDeny.
3) ΡΠ°ΡΡΠΈΡΠ΅Π½ΠΈΠ΅ ΠΊΠΎΠ½ΡΠ΅ΠΏΡΠ°. ΠΡΠ»ΠΈ (P, e P), (P, g Con,) ΠΈ Pt(0,) ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΈΡΡΠΈΠ½Ρ, ΡΠΎ
Π³Π΄Π΅ Π/ = Oi (Nameif Den" Con,), Con, u{P,} = Con/
4) ΡΡΠΆΠ΅Π½ΠΈΡ ΠΊΠΎΠ½ΡΠ΅ΠΏΡΠ°. ΠΡΠ»ΠΈ P, e Conx, to.
Π³Π΄Π΅ Π/ = Π/(Name, Den" Con,), Con/= Con, P,.
Π£ΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠ΅ 1. ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ Π§' Π°Π»Π³Π΅Π±ΡΡ? ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΠΎΠ»Π½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ ΠΎΡΠ½ΠΎΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΎΠ±ΡΠ΅ΠΊΡΠ½ΠΎΠ³ΠΎ Π°Π½Π°Π»ΠΈΠ·Π°.
ΠΡΠΎ ΡΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠ΅ ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠΈΠ²Π°Π΅Ρ Π°Π΄Π΅ΠΊΠ²Π°ΡΠ½ΠΎΡΡΡ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄Π° ΠΎΡ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΊ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡΠΌ Π°Π»Π³Π΅Π±ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠ½ΠΎΠ³ΠΎ Π°Π½Π°Π»ΠΈΠ·Π°:
- 1) ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π΄Π΅Π½ΠΎΡΠ°ΡΠ° ΠΏΡΡΠ΅ΠΌ Π΄Π΅ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡΠΈΠΈ ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² deeds (Oj): Oi —"(Π,/,… ΠΡ), Π³Π΄Π΅ ΠΡ = OyiNamCj, Deny, Con0); Vj Cony = Cons, Dent = Den, u,…, u Denik. ΠΈ Π½Π΅ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² decdn (Oi): Oi —> (0″, …, Π,/), Π³Π΄Π΅ Oy = Oy (Name, Deny, Cony); V/ ConΡ = 0; Den, = DenΠ» u … u Den,k.;
- 2) ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π΄Π΅Π½ΠΎΡΠ°ΡΠΎΠ² ΠΏΡΡΠ΅ΠΌ ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡΠΈΠΈ ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² comds (ΠΡ,…, Oik): (ΠΡ,…, Oik) -> Π, Π³Π΄Π΅ Or = 0,(Namei, Den, Con,); V j Π‘ΠΎΠ», = Con if, Den, u,…, u Den, k = Den, ΠΈ Π½Π΅ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² comdn (On,…, Olk): (On, … 0,k) —> 0″ Π³Π΄Π΅ Oi = 0,(Namej, Den" Con); Con, = 0; Denn u.. vj Den,k = Dent.
ΠΠΊΡΠΈΠΎΠΌΠ° 1. ΠΡΠ»ΠΈ ΠΏΡΠ΅Π΄ΠΈΠΊΠ°Ρ Π , Π΅ Π , Π ,? Π‘ΠΎΠΈ, ΠΈ Π ,(0,) ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΈΡΡΠΈΠ½Ρ, ΡΠΎ ΡΠΎΠΏΠ΅Ρ Ρ (Π,-, Π ,): Π, —> Π/, Π³Π΄Π΅ Π ' = Π/ (Nameit Den" Conf); Con, ΠΈ Π ,} = Con,' ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ°ΡΡΠΈΡΠ΅Π½ΠΈΠ΅ΠΌ ΠΊΠΎΠ½ΡΠ΅ΠΏΡΠ° ΡΡΡΠ΅ΡΡΠ²ΡΡΡΠ΅Π³ΠΎ ΠΎΠ±ΡΠ΅ΠΊΡΠ°.
ΠΠΊΡΠΈΠΎΠΌΠ° 2. ΠΡΠ»ΠΈ ΠΏΡΠ΅Π΄ΠΈΠΊΠ°Ρ Π , Π΅ Conit ΡΠΎ ΡΠΎΠΏΠΏΠ°Π³ (Π, Π <): Π, —> Π/, Π³Π΄Π΅ Π,' = Π/ {Name, Dent, Con,r); Π‘ΠΎΠΏ/= Cont Π ,. ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΡΠΆΠ΅Π½ΠΈΠ΅ΠΌ ΠΊΠΎΠ½ΡΠ΅ΠΏΡΠ° ΡΡΡΠ΅ΡΡΠ²ΡΡΡΠ΅Π³ΠΎ ΠΎΠ±ΡΠ΅ΠΊΡΠ°.
ΠΠ°ΠΆΠ΄Π°Ρ ΠΈΠ· ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ ΠΈΠΌΠ΅Π΅Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΉ ΠΏΡΠΈΠΎΡΠΈΡΠ΅Ρ ΠΈ Π°ΡΠ½ΠΎΡΡΡ, Π° ΡΠ°ΠΊΠΆΠ΅ ΡΠ²ΡΠ·Π°Π½Π° Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΌΠΈ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΡΠΌΠΈ Π΄Π΅Π½ΠΎΡΠ°ΡΠΎΠ² ΠΈ ΠΊΠΎΠ½ΡΠ΅ΠΏΡΠΎΠ².
Π£ΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠ΅ 2. ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ Π°Π»Π³Π΅Π±ΡΡ X ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΠΎΠ»Π½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ Π΄Π»Ρ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΎΠ±ΡΠ΅ΠΊΡΠ½ΠΎΠ³ΠΎ Π°Π½Π°Π»ΠΈΠ·Π°, ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠΈΠ²Π°Π΅Ρ Π°Π΄Π΅ΠΊΠ²Π°ΡΠ½ΠΎΡΡΡ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄Π° ΠΎΡ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΊ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡΠΌ Π°Π»Π³Π΅Π±ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠ½ΠΎΠ³ΠΎ Π°Π½Π°Π»ΠΈΠ·Π°.