Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

  • Published on
    07-Apr-2018

  • View
    215

  • Download
    0

Embed Size (px)

Transcript

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    1/25

    TM HIEU VE MANG TNH TOAN

    VA MANG CAC OI TNG TNH TOANMot trong nhng van e hien nay ang c quan tam cua Tr Tue

    Nhan Tao la nghien cu cac phng phap bieu dien va x ly tri thc. Tren c s o co the tao ra nhng chng trnh thong minh motmc o nao o. Trong nhieu lnh vc chung ta thng gap nhng vane at ra di dang nh sau : Chung ta phai thc hien nhng tnh toanhay suy dien ra nhng yeu to can thiet nao o t mot so yeu to ac biet trc. e giai quyet van e ngi ta phai van dung mot sohieu biet (tri thc) nao o ve nhng lien he gia cac yeu to angc xem xet. Nhng lien he cho phep ta co the suy ra c mot soyeu to t gia thiet a biet mot so yeu to khac. Trong [1] va [4] coneu len mot so bai toan trong toan hoc, vat ly, hoa hoc co dang nhtren.

    Trong bai bao nay chung ta xet en mot so mo hnh bieu dienva x ly tri thc co the ap dung giai t ong cac bai toan tren vata goi mo hnh nay la Mang tnh toan va Mang cac oi tng tnhtoan.

    I. MANG TNH TOAN.

    Mang tnh toan la mot dang bieu dien tri thc co thedung bieu dien cac tri thc ve cac van e tnh toan va cap dung mot cach co hieu qua e giai mot so dang bai toan. Moi mang tnh toan la mot mang ng ngha cha cac bien va nhng quan he co the cai at va s dung c cho viec tnh toan .Chung ta xet mot mang tnh toan gom mot tap hp cac bien cung vimot tap cac quan he (chang han cac cong thc) tnh toan gia cacbien. Trong ng dung cu the moi bien va gia tr cua no thng ganlien vi mot khai niem cu the ve s vat, moi quan he the hien mots tri thc ve s vat.

    Mang tnh toan va cac ky hieu:

    Nh a noi tren, ta se xem xet cac mang tnh toan bao gommot tap hp cac bien M va mot tap hp cac quan he (tnh toan) F trencac bien. Trong trng hp tong quat co the viet:

    M = {x1,x2,...,x n},

    F = {f 1,f 2,...,f m}.

    Trong o: Cho M = {x1,x2,...,x m} la mot tap hp cac bien co the lay giatr trong cac mien xac nh tng ng D 1,D2,...,Dm. oi vi moi quan he RD1xD2x...xDm tren cac tap hp D 1,D2,...,Dm ta noi rang quan he nay lien

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    2/25

    ket cac bien x 1,x2,...,x m, va ky hieu la R(x 1,x2,...,x m) hay van tat la R(x)(ky hieu x dung e ch bo bien < x 1,x2,...,x m >).

    F = {f 1,f 2,...,f m} la mot anh xa f R,u,v :uv vi uv = x, hay van tat laf:uv. Con goi la ham bieu dien moi quan he gia cac bien x M.

    oi vi moi f F, ta ky hieu M(f) la tap cac bien co lien he trongquan he f. D nhien M(f) la mot tap con cua M: M(f) M. Neu viet f didang:

    f : u(f) v(f) th ta co M(f) = u(f) v(f).

    v du: quan he f gia 3 goc A, B, C trong tam giac ABC cho bi he thc:

    A+B+C = 180 (n v: o)

    BAI TOAN TREN MANG TNH TOAN :

    Cho mot mang tnh toan (M,F), M la tap cac bien va F la tap cac quanhe. Gia s co mot tap bien A M a c xac nh va B la mot tapbien bat ky trong M.

    Cac van e at ra la :

    1. Co the xac nh c tap B t tap A nh cac quan he trong F haykhong? Noi cach khac, ta co the tnh c gia tr cua cac bien thuoc Bvi gia thiet a biet gia tr cua cac bien thuoc A hay khong?

    2. Neu co the xac nh c B t A th qua trnh tnh toan gia tr cuacac bien thuoc B nh the nao?

    3. Trong trng hp khong the xac nh c B, th can cho them ieukien g e co the xac nh c B.

    Bai toan xac nh B t A tren mang tnh toan (M,F) c viet di dang:

    A B,

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    3/25

    trong o A c goi la gia thiet, B c goi la muc tieu tnh toan cuabai toan.

    nh ngha 2.1 :

    Bai toan A B c goi la giai c khi co the tnh toan cgia tr cac bien thuoc B xuat phat t gia thiet A. Ta noi rang motday cac quan he {f 1, f 2, ..., f k} F la mot li giai cua bai toan A Bneu nh ta lan lt ap dung cac quan he f i (i=1,...,k) xuat phat t giathiet A th se tnh c cac bien thuoc B. Li giai {f 1, f 2, ..., f k}c goi lali giai tot neu khong the bo bt mot so bc tnh toan trong quatrnh giai, tc la khong the bo bt mot so quan he trong li giai.

    Viec tm li giai cho bai toan la viec tm ra mot day quan he eco the ap dung suy ra c B t A. ieu nay cung co ngha la tm rac mot qua trnh tnh toan e giai bai toan.

    nh ngha 2.2 :

    Cho D = {f 1, f 2, ..., f k} la mot day quan he cua mang tnh toan (M,F), Ala mot tap con cua M. Ta noi day quan he D la ap dung c trentap A khi va ch khi ta co the lan lt ap dung c cac quan he f 1,f 2, ..., f k xuat phat t gia thiet A.

    Nhan xet : Trong nh ngha tren, neu at : A 0 = A, A1 = A0 M(f 1), . . ., Ak = Ak-1 M(f k), va ky hieu A k la D(A) , th ta co D la mot li giai cuabai toan A D(A). Trong trng hp D la mot day quan he bat ky (khong

    nhat thiet la ap dung c tren A), ta van ky hieu D(A) la tap bienat c khi lan lt ap dung cac quan he trong day D (neu c).Chung ta co the noi rang D(A) la s m rong cua tap A nh ap dungday quan he D.

    GIAI QUYET VAN E :

    1. Tnh giai c cua bai toan :

    Trong muc nay chung ta neu len mot khai niem co lien quan entnh giai c cua van e tren mot mang tnh toan : bao ong cua mottap hp bien tren mot mang tnh toan.

    nh ngha 3.1 : Cho mang tnh toan (M,F), va A la mot tap con cuaM. Ta co the thay rang co duy nhat mot tap hp B ln nhat M sao chobai toan A B la giai c, va tap hp B nay c goi la bao ongcua A tren mo hnh (M,F). Mot cach trc quan, co the noi bao ong cuaA la s m rong toi a cua A tren mo hnh (M,F). Ky hieu bao ong cuaA la A , chung ta co nh ly sau ay:

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    4/25

    nh ly 3.1 . Tren mot mang tnh toan (M,F), bai toan A B lagiai c khi va ch khi B A

    T nh ly nay, ta co the kiem tra tnh giai c cua bai toan A Bbang cach tnh bao ong cua tap A roi xet xem B co bao ham trong A

    hay khong.nh ly 3.2 . Cho mot mang tnh toan (M,F), A, B la hai tap con cuaM. Ta co cac ieu sau ay la tng ng:

    (1) B A .

    (2) Co mot day quan he D = {f 1, f 2, ..., f k} F thoa cac ieu kien:

    (a) D ap c tren A.

    (b) D(A)B.

    Thuat toan 3.1. tm bao ong cua tap A M :

    Nhap : Mang tnh toan (M,F),

    AM.

    Xuat : A

    Thuat toan :

    1. B A;2. Repeat

    B1 B;

    for f F do

    if ( f oi xng and Card (M(f) \ B) r(f) ) or

    ( f khong oi xng and M(f) \ Bv(f) ) then

    begin

    B BM(f);

    F F \ {f }; // loai f khoi lan xem xet sau

    end;

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    5/25

    Until B = B1;

    3. A B;

    2. Li giai cua bai toan :

    tren ta a neu len cach xac nh tnh giai c cua bai toan. Tiep theo, ta se trnh bay cach tm ra li giai cho bai toan A B trenmang tnh toan (M,F).

    Menh e 3.4 : day quan he D la mot li giai cua bai toan A Bkhi va ch khi D ap dung c tren A va D(A) B.

    Do menh e tren, e tm mot li giai ta co the lam nh sau: Xuatphat t gia thiet A, ta th ap dung cac quan he e m rong dan tapcac bien co gia tr c xac nh; va qua trnh nay tao ra mot s lantruyen tnh xac nh tren tap cac bien cho en khi at en tap bien B.Di ay la thuat toan tm mot li giai cho bai toan A B tren mangtnh toan (M,F).

    Thuat toan 3.2. tm mot li giai cho bai toan A B :

    Nhap : Mang tnh toan (M,F), tap gia thiet A M, tap bien can tnhBM.

    Xuat : li giai cho bai toan A B

    Thuat toan :

    1. Solution empty; // Solution la day cac quan he se ap dung

    2. if BA then

    begin

    Solution_found true; // bien Solution_found = true khi bai toanla // giai c

    goto 4;

    end

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    6/25

    else

    Solution_found false;

    3. Repeat

    Aold A;Chon ra mot f F cha xem xet;

    while not Solution_found and (chon c f) do

    begin

    if ( f oi xng and 0 < Card (M(f) \ A) r(f) ) or

    ( f khong oi xng and M(f) \ Av(f) ) then

    begin

    A AM(f);

    Solution Solution {f };

    end;

    if BA then

    Solution_found true;

    Chon ra mot f F cha xem xet;

    end; {while }

    Until Solution_found or (A = Aold);

    4. if not Solution_found then

    Bai toan khong co li giai;

    else

    Solution la mot li giai;Ghi chu :

    1. Ve sau, khi can trnh bay qua trnh giai (hay bai giai) ta co the xuat phatt li giai tm c di dang mot day cac quan he e xay dng baigiai.

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    7/25

    2. Li giai (neu co) tm c trong thuat toan tren cha chac la mot ligiai tot. Ta co the bo sung them cho thuat toan tren thuat toan etm mot li giai tot t mot li giai a biet nhng cha chac la tot.

    Thuat toan se da tren nh ly c trnh bay tiep theo ay.

    nh ly 3.3 . Cho D= {f 1, f 2, ..., f m} la mot li giai cua bai toan A B. ng vi moi i=1,...,m at D i = {f 1, f 2, ..., f i}, D0 = . Ta xay dng mot ho cac day con S m, Sm-1, ..., S 2, S1 cua day D nh sau :

    Sm = neu D m-1 la mot li giai,

    Sm = {f m} neu D m-1 khong la mot li giai,

    Si = S i+1 neu D i-1 Si+1 la mot li giai,

    Si = {f i} Si+1 neu D i-1 Si+1 khong la mot li giai,vi moi i = m-1, m-2, ..., 2, 1.

    Khi o ta co :

    (1) Sm Sm-1 ... S2 S1.

    (2) Di-1 Si la mot li giai cua bai toan A B vi moi i=m, ..., 2, 1.

    (3) Neu S i la mot day con that s cua S i th Di-1 Si khong phai lamot li giai cua bai toan A B vi moi i.

    (4) S1 la mot li giai tot cua bai toan A B.

    Thuat toan 3.3. tm mot li giai tot t mot li giai a biet.

    Nhap : Mang tnh toan (M,F),

    li giai {f 1, f 2, ..., f m}cua bai toan A B.

    Xuat : li giai tot cho bai toan A B

    Thuat toan :

    1. D {f 1, f 2, ..., f m};

    2. for i=m downto 1 do

    if D \ {f i} la mot li giai then

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    8/25

    D D \ {f i};

    3. D la mot li giai tot.

    Trong thuat toan 3.3 co s dung viec kiem tra mot day quan he cophai la li giai hay khong. Viec kiem tra nay co the c thc hiennh thuat toan sau ay:

    Thuat toan kiem tra li giai cho bai toan :

    Nhap : Mang tnh toan (M,F), bai toan A B, day cac quan he {f 1,f 2, ..., f m}.

    Xuat : thong tin cho biet {f 1, f 2, ..., f m}co phai la li giaicua bai toan A B hay khong.

    Thuat toan :

    1. for i=1 to m do

    if ( f i oi xng and Card (M(f i) \ A) r(f i) ) or

    ( f i khong oi xng and M(f i) \ Av(f i) ) then

    A A M(f i);2. if AB then {f 1, f 2, ..., f m} la li giai

    else {f 1, f 2, ..., f m}khong la li giai;

    3. nh ly ve s phan tch qua trnh giai :

    Xet bai toan A B tren mang tnh toan (M,F). Trong muc nay ta neulen mot cach xay dng qua trnh giai t mot li giai a biet. oi vi

    mot li giai, rat co kha nang mot quan he nao o dan ti viec tnhtoan mot so bien tha, tc la cac bien tnh ra ma khong co s dungcho cac bc tnh pha sau. Do o, chung ta can xem xet qua trnh apdung cac quan he trong li giai va ch tnh toan cac bien that s canthiet cho qua trnh giai theo li giai. nh ly sau ay cho ta mot s phantch tap cac bien c xac nh theo li giai va tren c s o co thexay dng qua trnh tnh toan cac bien e giai quyet bai toan.

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    9/25

    nh ly 3.4 . Cho {f 1, f 2, ..., f m} la mot li giai tot cho bai toan A Btren mot mang tnh toan (M,F). at :

    A0 = A, Ai = {f 1, f 2, ..., f i}(A), vi moi i=1,...,m.

    Khi o co mot day {B0, B1, ..., Bm-1, Bm}, thoa cac ieu kien sau ay:

    (1) Bm = B.

    (2) Bi Ai , vi moi i=0,1,...,m.

    (3) Vi moi i=1,...,m, {f i} la li giai cua bai toan B i-1 Bi nhngkhong phai la li giai cua bai toan G Bi , trong o G la mot tap conthat s tuy y cua B i-1.

    Ghi chu :

    (1 ) T nh ly tren ta co qua trnh tnh toan cac bien e giai bai toan A Bnh sau:

    bc 1: tnh cac bien trong tap B 1 \ B0 (ap dung f 1).

    bc 2: tnh cac bien trong tap B 2 \ B1 (ap dung f 2).

    v.v...

    bc m: tnh cac bien trong tap B m \ Bm-1 (ap dung f m).(2 ) T chng minh cua nh ly tren, ta co the ghi ra mot thuat toan e

    xay dng day cac tap bien {B1, ..., Bm-1, Bm} ri nhau can lan lt tnh toantrong qua trnh giai bai toan (B i = B i \ Bi-1) gom cac bc chnh nh sau:

    xac nh cac tap A 0, A1, ..., Am . xac nh cac tap B m, Bm-1, ..., B1, B0 . xac nh cac tap B 1, B2, ..., Bm .

    V du : Cho tam giac ABC co canh a va 2 goc ke la , c cho trc.

    Tnh dien tch S cua tam giac.

    e tm ra li giai cho bai toan trc het ta xet mang tnh toancua tam giac. Mang tnh toan nay gom :

    1. Tap bien M = {a, b, c, , , , h a, hb, h c, S, p, R, r, ... },

    trong o a,b,c la 3 canh; , , la 3 goc tng ng vi 3 canh; h a, h b, h cla 3 ng cao; S la dien tch tam giac; p la na chu vi; R la ban knh

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    10/25

    ng tron ngoai tiep tam giac; r la ban knh ng tron noi tiep tamgiac, v.v...

    2. Cac quan he:

    f 1 : + + = 180 f 2 :a

    sin

    b

    sin =

    f 3 :c

    sin

    b

    sin = f 4 :

    a

    sin

    c

    sin =

    f 5 : p = (a+b+c) /2 f 6 : S = a.h a / 2

    f 7 : S = b.h b / 2 f 8 : S = c.h c / 2

    f 9 : S = a.b.sin / 2 v.v ...

    3. Yeu cau tnh : S (dien tch cua tam giac).

    Theo e bai ta co gia thiet la : A = {a, , } , va tap bien can tnh la B= {S}.

    Ap dung thuat toan tm li giai (thuat toan 3.2) ta co mot li giai chobai tnh la day quan he sau: {f 1, f 2, f 3, f 5, f 9}. Xuat phat t tap bien A,lan lt ap dung cac quan he trong li giai ta co tap cac bien cxac nh m rong dan en khi S c xac nh :

    {a, , } 1f {a, , , } 2f {a, , , , b} 3f {a, , , , b, c }

    5f {a, , , , b, c, p } 9f {a, , , , b, c, p, S }.

    Co the nhan thay rang li giai nay khong phai la li giai tot v cobc tnh toan tha, chang han la f 5. Thuat toan 3.3 se loc ra t ligiai tren mot li giai tot la {f 1, f 2, f 9}:

    {a, , } 1f {a, , , } 2f {a, , , , b} 9f {a, , , , b, S}.

    Theo li giai nay, ta co qua trnh tnh toan nh sau :

    bc 1: tnh (ap dung f 1).

    bc 2: tnh b (ap dung f 2).

    bc 3: tnh S (ap dung f 9).

    Qua trnh tnh toan (gom 3 bc) nay co the c dien at mot cachro rang tren s o mang sau ay:

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    11/25

    II. MANG CAC OI TNG TNH TOAN.

    Trong chng trc chung ta xet mot mang tnh toan bao gom mottap cac bien M va mot tap cac quan he F the hien tri thc ve s lienhe tnh toan gia cac bien trong mang. Mot v du ien hnh ve motmang tnh toan a neu trong chng II la mang tnh toan cua mot tamgiac. Bay gi neu ta xet mot bai toan gom co hai tam giac co motso lien he vi nhau, chang han canh a cua tam giac nay bang canh bcua tam giac kia, th ta co mot mang tnh toan bao gom 2 oi tng cocung loai (eu la tam giac). Moi oi tng trong trng hp nay co thec thay the bi mot mang tnh toan tng ng, va t o ta c motmang tnh toan trong o co 2 bo phan (hay 2 mang con ) co cung loai.

    Hnh 1.1 . Mang tnh toan gom 2 tam giac.

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    12/25

    Hnh 1.2 . Mang tnh toan gom 2 bo phan,

    moi bo phan la mang tnh toan cua 1 tam giac.

    1. Mang con, oi tng tnh toan :

    Mot mang tnh toan (M,F) c goi la mot mang con cua mang tnhtoan (M,F) neu thoa cac ieu kien sau ay :

    (1) MM,

    (2) F F,

    (3) M(f)M(f), vi moi f F.

    Trong trng hp nay, ta con noi (M,F) la mot s thu hep cua mang(M,F) hay (M,F) la mot s m rong cua mang (M,F); ky hieu : (M,F) (M,F).

    Lien quan en viec m rong va thu hep mang tnh toan, ta co motso tnh chat c ghi trong menh e sau :

    Menh e 1.1 .

    (1) Cho (M,F) la mot thu hep cua mang tnh toan (M,F). Gia s A B la mot bai toan tren mang (M,F), va A M, BM. Khi o, ta co thexem A B cung la mot bai toan tren mang thu hep (M,F). Neu bai toanla giai c tren mang thu hep (M,F) th cung giai c tren mang banau (M,F). Hn na li giai cua bai toan tren mang thu hep cung lali giai tren mang ban au.

  • 8/6/2019 Mang Tinh Toan Va Mang Doi Tuong Tinh Toan

    13/25

    (2) Cho mang tnh toan (M,F), M1 M. at :

    F1 = {f F M(f)M}.

    Ta co (M1,F1) la mot thu hep cua mang (M,F).

    (3) Cho mang tnh toan (M,F), F1 F. at :

    M1 M(f)f F1

    =

    .

    Ta co (M1,F1) la mot thu hep cua mang (M,F).

    (4) Cho mang tnh toan (M,F), B M. at :

    F(B) = {f F M(f) B },

    M(B) =M(f)

    f F(B)

    Ta co (M(B),F(B)) la mot thu hep cua mang (M,F).

    Trong mu...