Luận án Ứng dụng nguyên lý máy học vào hệ thống viễn thông

=-x ne'uX bi phanlo~iduong,tilc la : Trang23 WjXt + W2X2 +... +WnXn>0 Lu~tdi6uchinhtrQngs61alu~t giamgradient: Wt+1=Wt+ A. v1 Voi A-.lah~s6chobi€t phudngditheogradientnhanh haych~ill. Caebuoccui thu~toan: Input: T~pS caevectorinputva caeoutput11longmu6n(0 hay 1) Output:!~p trQngs6 Ws=(Wo,WI, W2,...,Wn) phan lop dungS Step1: Kh(5it~ongftunhiencaeWi,i =O...n £)~t=A- ChQn gia tri thichh<Jpchoh~ngs6 A- Stev2 : . Tlnl t~p F tatca caevectorinputbi phanlo~isaibdi caeWihi~nhanh . Step3: NeuF =0 th1xuttracaeWivadung Step-4: Tinhcaevectort6ngcaevectorinputbiphanlo~isai: 1=:Llxl XEF Voi Ixi=xneuxbiphanlo~iaID,tilela: W1X1+W2X2+... +WnXn<0 Voi Ixl=-xneuxbiphanlo~idue;ng, tilela : WIXI + W2X2+... +WllXll>0 Sl~: £)i~uchlnhtrQng W =W +;."j Quay l~tiStep2 WoI WI I W2 F 0.5 0.6 x2 , x3 10 11 12 -2 -1 -1 Trang24 0.3 I 0.4 0.5 0.4 0.4 x3 -1 0 1-1 0.5 0.6 Vi dl;]h~ul1: -O.6xo+O.4Xl+0.4X2hQcdli<1cham ke'tqua I AND XOR (1,1)l 0 (0,0)J . (1,1) } 1 (0,0) 2.1.5.2Thu~tt6anIantruy~nngu'Q'ctrongm~ngANN 3 lopvoihamchuy~nlogistic: Input: t~pm~uScacvectorinputvaoutputlllongmu6n tl(eingling output:t~pcactrQngs6sacchota-tcacacvectorinputn1~u saukhi quanwngse ra outputg~nvoi outputmongn1u6n theetieuchu~nt6ngblnhphliongtrungblnhsai s6 la'be nhat. -GQiA,B,C l~nlli<1tla s6AN tliongling(j lopInput, HidenvaOutput - GQi Xi , hi , Oil~nlli9t la tin hi~ura (j AN thli i cua lopInput,HidenvaOutput 1 1 1 I 1t+dliong 1 0 0 1 I 0-1------am 0 Trang25 - GQi WIHi la trQnglien ke'tgiua AN thli i Qualop Inputvoi AN thlij cualop Hiden; WHO~ila trQnglien ke'tgiuaAN thli i Qualop Hiden voi AN thlij Qualop Output SteJ2l: . -'Kl~(jit(;10cactrQngs6voi giatri ng§:unhien - GanXo=.},ho=1 SteM: -ChQnillQtc~p inputx,y -Gan trikichhO(;1tXi,i=1...Arho cacAN (j lopInput - Lan truy€n kich ho(;1tcho cac AN (j lop Hiden va Output'Vatinhtinhi~urab~ngrangthlic. , A A. , 2.1.2TRI TU~ NHAN T~O vaMAY HOC (ARTIFICIAL INTELLIGENCE andMACHINE LEARNING) tAl ~ ML ( AI Tie'ntoimayhoc.) S\i tie'ntoinay duQcmatala nhunghlnhthlicchuye'u du,Jcbit€uthi va ap d\lngdt€ xay dtfngcacnguyent~cttf dQnghoaxuly cuacach~chuyengia. , ? ~ Noi chung,ve mQtm~tnaodoco thedtfa vaovi~c xaydlfngcaccaysuyd§:n,voicacky thu~tconQidungco tht€giainghlavi~chQccdban.Cacnghiencuuquailtrqng du,1cduara dfi chungminhAI co tht€ tie'ntoi mayhQc nhungtucjngd6i kho su d\lng(tuyv~y;mQtkhi dfi thanh rangthico tht€duatoi nhunggia trikhato Ion).Nguoita thu'ongsiTd\lngstf tie'nbQ Quaphudngphapquyn(;1pva CctCky thu~tnit trichcungvoivi~choal§:ncacphantichdu li~uvaky thu~1. Trang26 AI phat tri~nchIradingchungtacfinbie'n(16icaeky hi~uv<Jinhi~uthongtinchinhxac honla vi~cchIsadvng caecons6dongian. C6 th€ n6i1110teachkhatla thongtin du<.1cdoi hotbot vi~cap d\lngcactie'nbOcuakhoahQc hi~nd(;li. Nlul VtlVAI tielltoimayhoclagi?? C6 5d~cHnhth~hi~nva-nd~AI tiellto;11layh(Jc: Khi caed~ctinhnayth€ hi~n,tuc la, ta-tcadoi hoi du<,1cthtfchi~ntheo1110td(;lng1110tanabd6cuaAI , va se baag<1111ta-tcacacki~uAI dangt6iltc;ti, chunglase quan talll tdi 1110tVald~ctinhdfineualIen. . FJdu lien, treiinguQcVOl mo ta "may thong 111inh" (Battand Feigenbam)AI tITch6i Kay dtfnghOpdenthong 11linh.Ching hc;tn,RogerSchanlschi ra r~ngmaythai co ,. hi~nd(;lidfi duQCKaydtfngkhongh~su dvngky thu~tAI, 111~Cdli chungdfi thai ra-tt6t.Va nguoi ta dfi chung111inh ding do thayd6i thuOctinhBenAI dfi thanhtong d6i VOl ll1aythai co, luc d6 maythai co dfi la dc;tngriengcua111ay hQc. Thz:thai , AI c6 y dinhtnlnhsudvngnhfi'ngtri thucao. MOtdi~urarangduarala danhd~fugidithucchirabi€u thi iri thuc~ongb6 , 11latri thatva cachsu dvngduQcphan bi~tkhatnhau.Ching hc;tn,AI thichvi~csinhra cacngon ngfi'11lc;tnhuLispvaProlog.VidVduQclieUchinhla mOt h~kinhnghi~m(ES).MQlh~kinhnghi~mkhongc6gl qua d~cbi~tnhlingloc;ticuaquye'tdinhphil duQCsapxe'ptheo 1110tdc;tngtong,b6 va ghira cacnguyentat d€ huongtOt quye'tdinh,khongn6iv~st;fphattri€n theothutt;f11lachung duQcgQi.Bi~unaysinhreiKungdOtva doth6i duara giai phapgiaiquye't.Giaiphapgiaiquye'tchinhla tc;tOramOtco che-hQc.TrongmOtca che-ki€u AI, tri thucphil la mOt tr~ngthaira rang,va duQctongb51119tcachrt rang.Tri thli'cthutvc duQcbi€u di~ntrongm9tngonngfi'chuang Trang27 trlnhnhonhu'co th€. Songd6i voi cd chehqcthl va'nd€ ou'Qcgiaiquyetn1€mdeohdn,m~cdudlfalIenn€n tangAI nhu'ng0 cdchehqctfilli do du'Qct<;indvngnhu'mQtva'nd€ xu ly tlfc19ngvaneunhu'AI tranhsudvngtill 0 cdcheh9c di~unayl~idu'Qckhuyenkhich. Thaba , matithu~nvoi nhlinggllna nhlinglopngu'oi d~ulienda:thlfchi~n,n19th~th6ngmangaytrongvi~cthu nghi~n1h~unhu'da:mangm9tso'khdllgIIJ cactri thlic.Sail do,tri thlicnayphaid~nd~tslfhi€u bi~tcuangu'oisud~ng toi cacva'nd~mQclieu,Bi€u naydu'Qcdu'arabai va'nd~ quantrQngtrongnhlingcdsa tri thlicd1jatrellAI. Tri thlic la lo~idlili~u:Chungtakhongnoicds0dli li~uVIcds0ciia taoa:ou'Qcongb6vaca:du'Qchi€u bai chinhnglingngu'oi su'dQngcuachung.MOth~AI du'Qch6trf/d€ thlJchi~ncac nhi~111V\ltr()llgd{likhi su dQngcactri thlicn€n tang,do chinhla cdchehQc. Tha tu:, theod~ngcftnchongu'oisudvng hi€u , mQt h~AI phainoi ligonngli ngu'oisu.dvngcuano thaycho vi~cnoi "ngonngucuaAI ",IDatheocachnayda:thong du'<;iccha'pnh<;in.B~cHnhnaypilaubi~tAI voi nhungbO 1110nkhoahQckhacmaslfg~nbo dftulien la t~obi~tngu riengd€ giupchongu'oisu dvngthan1gia vao thongtin, ' khoahqccuano,Chingh~n, th6ngke cacmientahi~n . tu'Qngtlfnhienhu'ongd~nvad~tchonon1lHthU~tngu n10t khoiingnglinghla, voicdchehqcligonnguriengnaythay thechovi~cbi€u di~ntri thlictrongngonngucuangu'oisu dQngnhu'AI c6lam. Thananl,AI du'Qcgall voi mo ta,phantich,do luong, sosanhdOngthai giai nghlaquailh~thlfchi~nill9t cachtt! dOngva'dungngonngucuangu'oisudvng. Cd chehQcco th€ dungbi~tnguriengva In~cdukh6i luQngtri thlicra'tdOS9nhungv~nco th€ t<;loduQcthuvi~n gild IlghlathichhQpvadftyduo Trang28 Khi AI tie'ntoi mayhQc,cac nghienCUllv~AI Dang leu () mUGcao hdn,d6ngthai cling giai quye'tduQcnhi~u va'nd~quail trQnghdn,nhunglogic cd ban th1cling tudng tlj. Di;lcbi~tkhi nghienCUlltoi may hQcthlky thu~tguy n~pvasuydi~ndi;lcbi~tduQcnha'nm~nh. .. AI tie'ntoi mayhQcchI chochungtabie'tsl1c~nthie't phai bie'nd6i nhi~ulo~ithongtin phuct(;lp hdnva choke't quaehinhxachdn;khongchIdungl(;lid nhfi'ngcons6dtJn.': gianfilaphaiduaranhfi'ng iainghlav~caclo~ithongtin duQcdoi hoi bdj vi~cungd\lngnhi~ubQmankhoahQc hi~nd~i.Di~unaydfind<1ttoi va'nd~c~nthie'tphaihi6u tha'udaokhaini~mquyn~p,ruttrichvat6ngquatboa.VI v~ysandaychungtasemotacackhaini~mnay. 2.1~3.1Qavil(lpVasav~i~/l . . . .. Deduction(suydi~n) duQcxu ly bdi mQtphep.quy n~p khi magin l~icacnQidung cila dii'li~uda:lull trn . (inferswhilepreservingthetruth) . . Nguyent<1cn6itie'ngla : gifi'l~icai dung.Vi d\l,gia thie'tr~ngcoOlQtly thuye'tnoivoi tar~ngta'tca1£1xanhla la non,khidokp.igi;lp la xanhcoth6suydi~nr~ngdola la non. Induction(phepquyn(;lp ) duQcxii'ly bdi vi~cginl~i caesai (whichone whilepreservingthefalsity)cilacacdn li~udi;lcbi~t.Quyt<1cnayduQcph,ltminhbdiMichalsas. Ch£ngh(;ln,khi gi;lpla xanh, taco th6noi r~ng. tagi;lpd6 v~tUlanxanh.(C6HnhqUell r~ngchungla nhfi'ngcai lei). Hoc}ctaco th6chor~ngta gi;lpcacd6 v~t cannonb~ng vj~esii'd\lngly thuye'tlIen . Gia Sl(clingly thuye'tLIennoi vdi ta r~ngba'tcu 1£1 xanhla kh6ngdo,nhuv~ytakh6ngthtinoir~ngtagi;lpcac d6v~tdobdivi "green"tue "kh6ngdo"...red=false. 2.1.3.2Ouv/lapehuve/ltri thue: Trang29 Quyn~p chuyentri thuc. Nhi~uteicgia lien ke"tvi~chQcsoydi~nVOlchuyentri thuc (co ,caccong.C\l dangbQc)va hQcquy n~p VOlvi~c ngheotri thuc.No nit 1'6r~ng "Pure induction"la tri thuc ngheo.Tri thucngheothliongbatngu6ntll dITli~utho.Dfi' li~u tho cling thliongkhong phan anh dlicjC.ban cha'tstf vi~c.M(>til10ta 1'6rangcuavi~cnit trichse giupchungta il10ta khahejnphepquyn~p va chI ra val trbcua tri thuc, day la n~ntang.cdsd dypde cuavi~cxU'ly quyn~p loan " the. 2.1.3.2.1Whatis abduction? V~m~tky thu~t,rutotrichla xU'ly VOlky hi~uamchI, tuclaxuly il1abie"tr~ng:A->B , il1(>tkhidffd~c~pde"nA th1tabie"tr~ngB sedung. \ E>~chungtadliara suydfin b~ngvi d\l sail : Trongvi dl).naynllJcdichcuachungtala hQcd~il10tanQidungcua vi~ctt!tu Kill(x,x ). Giii sur~ngchungtadffdlicjchQcsao chovi~cttftudbihoistfc~nthie"tco lll(>tvil khi dliQcbi~u thibdinguyenlac: KILL (x,x) : - Deprssed(x),Buy(x,y),WeapoIl(Y) Gia sutabie"tMarynglioicamke"tsettftU'. Gia sU'taoff conhfi'ngkie"nthucsailv~cota: Deprssed( MARY) . BUY (MARY, OB11). SLEEPING- PILLS (OB11). PRICE (SLEEPING- PIUS,20). BUY (MARY, OB12). BOOK (0812). d dayOB11va OR12lfi nhfi'ngh~ngs6 chungtase khongcoth~chung,il1inhKILL (MARY, MARY) bdiVIchi tadffkhongcovil khi.Cox\~Pietrzykowski(1986)bi~uthi ill(>thu~tngfi'il1aphcli tltdQngnhinvao "vil khi" trong Trang30 nlOtvi tri nhl(la d d6WEAPON (Y) bi buybooN6 batkip viI khifiladO'isO'd~uliendaduQcth5amanBuy(x,y).N6 la-yviI khi WEAPON ( SLEEPING -PILLS) hay viI khi WEAPON(BOOK.)pht;lthuOcvanvi~cc6viI khinaotrudc. Khi filakh6nghi€u bie't,r6rangdingba-tcucaigi duQCfila cling duQcxem la viI khi . Chung t6i: (DURDL va LODRATOFF)h6trQmOtSvth~tr~ng- vi~c lily viI khi nlOt cach khac di cling c6 th€ duQcdc}tten, b6 sung nguyenlac fila cac dO'itUQugda duQcthoamanBUY (x,y) duc,1ch6 trQnl~nhd~,kh6nggi£1thie'tr~ngchungchila "viI ? . ' khi". d daytac6th€ lily nguyenlac nhusailday: KILL (x,x) :- DEPRERSED (x ), BUY (x,y ); sleeping- pillsl(y) hoc}c KILL (x,x) :-DEPRESSEB(x),BUY (x,y), BOOK (y). Tilt c£1nhungdi~unay chi ra r~ngm6i true;ngrift tu(1ngph£1nhi~uke'ho<;lch,rut trichc6 th€ duafa, tiltc£1 trongchunggiaiquye'tvilnd~thvchi~nc);1ungmil1hbuybo TrangAddis nhi~uma t£1chinhxacda duQc chonhung di€u neuireDdd d€ duara Svphanbi~t gifi'arut trichva guy n<;lp . Rtit trichla phepco hQclogic ma mOthic nao d6 c6 th€ lily l<;likhi bi huhong.Bdi VIco nhi~udO'isO'nhuv~yc6 th€ lily l<;liBhangta chQnd6i sO'nao thichhQpnhilt (di~u nayc6 th€ duQcgQila cachgi£1iquye'tpht;lchai) lam thanh ph~nfila chungta c6 th€ gQid day "chQnva chunglllinh vi~cnit trichguyn<;lpdbi hoi Sv di~ukhi€n tilt ca chung, ru:ttrich,tuela chQnva chungminhn6.Trongnhi~utrue;ng hc,5P,eo th€ rut trichkhcinhi~usancho no hoan loan phli h<;;pc1€ve 111()tdue;ngconggiuacaerut trichdon,dangthe;i th€ hi~nduc,1ecaebuoeehQn. 2.1.3.3Trithll'cI1lanhruttrich vaquynap: Trang31 H~u hetmqingu'oid~uc6 y dinhgQi"pureinduction"cai 111acluingduQcgQila nit trich.Rut trichc6 th€ la tri thuc ngheo,th~mchi chodli la di~unay khongph£1iluau dung, " thevaod6,ngaynhlita d~fightph\lch6i tll vi~cphabuy cacnguyent~cb6sung,ba'tky nguyent~ct~mthliongnao coth€ giaiquyStva'nd~nhu'lab6sung: KILL( x,x):- PRICE ( SLEEPING- PILLS, ?-O) co ccjstj tri thuc,nhu'mOtvi dl,lngocnghSchd()cbi~t(tll quandi€111cuatri thuclogicngheo,tri thucph£1ihinhthanh d()ctinhtotnha'tnaod6). . Luu y ding: chungta mo 1£1qui lUIP nhzthI) ha cua rut trich,cht)nvachung11lilth.f)i~ucuoiclingla phanloaitri thtI"e111~nhbtjiVIchungminhc~nd€ gi£1ithichvi~cchQnrut trichbdi dat6nt~itri thuc.Trongcach~quin~ptotnha't, caebu'dcchungminhdliQcquy~nvao nhau.Ntu saudo trongtrztongh(lptotnhattatcdcac,thallhphOllcuahI)ha ph~lthul)cvao'cac thitllhpha'nkia, ma dii 1l(l('li;ticho chungtatcdtri thllcm(lnh. 2.1.3.4BallluQn : Phanlo~init trichdu'Qcxemnhu'la tri thucngheo. MOtphantichchi liSt cuacacphepthtfchi~nt~ora b~ngy kiin nayda tranQchomOtstfIOnxOngiuahamy.vatri thliengheo,trongtruonghQptotnha'tmacuatri thucchua nhi~uthongtinsacchophepquin~pxua'thi~nphl,lthuOc vaC)tri thlie.TImranhungmatotla ttfn6ra'tnhi~utri thlic nl~nh.Nhu'chungtadatha'y,lo~ibohamybi€u thjla lo~i cuatri tu~nhant~o.Khongng~cnhienr~ngtri thlicm~nh quin~pdftntdistfthllanh~ntrongmoitrliongAI. Trang32 2.1.4T6ng quat va rieng biet Khai quatv€ phu'dngI2MPBattorn-upandTo]2-down. Cac t~P kh6ngglaDcuaTommitchellduytrl tr<,1ngtheEsinh ella ngu'oidieu hanh. HQ cho tr<.lngthai sinhchinhxac d€ lllieu ta du'(,;esu d1;lngbai ngu'oidieuhanhd<,1tdu'Qcthil t1)' t6i u'uva'giai quye'tva-ade thOtcachco hi~uqua.Cho mOt t~pcaevi dlJ du'dngva am, "t~pkh6nggian" la .t~pc6ng thilc lTIaca hat10<,1ivi d1;lamva du'dngn6i ireDu~uc6 th€ mien tatrongd6. (Nh~nbie'tta-tca cac vi 'd1;ldu'dng,va kh6ngnh~nbie'tcacvi d1;lam). Khi t~pkh6ng glaDcua ngu'oidieu hanh du'QcKay cl~(ngcac vi d~ldtidllgdll(lesit d~lllgbottom-up;tilc la tim lll(Hc6ngthilcllla nhieuhdncacvi d1;lba-tky saochomotvi cllJ Ia ll10thi~ntu'Qngtilc thai cuac6ngthuc.(Tuy nhien, kh6ngphil cac vi dlJ alll phil la mOthi~ntu'Qngtilc thai cua n6, nhu'ngdieu nay kh6ng phil la quan di€lll chac chdn). Ngu'Qc l<.li, cae vi dl;l anI thtiiJltg du'(lesit dl;lllg pluldllgphap Top-dowll.Bai VI chungdu'Qcsu d1;lngd~c bi~tll10tc6ngthilcllla la baatrumleucacvi d1;lam(cling the'tateacacvi dlJ du'dngphil la mOtbie'nc6tucthaicua n6) Bieu nayphil thuye'tph1;lcmQingu'oidingvi~csinh (tli'cacvi dlJ du'dng)va riengbi~t (tll cacvi dlJam) la 2 lll~t cuaclingtie'ntrlnhdu'Qcbie'tdu'aitenGenerali.zation b(?jiVI nhtl'ngc6ngvi~ca~ulien aftkh6ng du ti~nlQi d€ nh~nbie'tmilequailtrQngcuacac vi d1;lamvas1;1'canKung gitl'acacvi dlJamvadu'dng(Nicolas,1988),C6 nhungtie'n b0 khachdn c6 vli bat versionkhongglaD,1;f~chacski' (Michalskiandstep,1983,Michalski,1984)tong vi~cIi lieu chu:1ncuanhungai tie'ntoi sinhtITcacvi dlJ (Thu~t toannayth1;1'cbi~nbottom-upgeneralization).Cac thu~t Trang33 loannayc6cacvi d\lcungvoi nhauva d6ngthai~")imramOt hamnh~nbie'tcacvi dQduQcb6 chumthanhnh611lvabuy bi) ta"tca cac vi d\l rai rC;lCriengre. Slj phat trien tie'ntoi ciia nhungnh6mvi d\l nay sinhra nhi€u chuc nangnh~n dC;lng.NguQclC;li,ta"tca hQ ID3 khuyen khich tu Quilan (1983)ba:td~utll mOtt~pllla chuata"tca vi d\l va tie'ntoi ap d\lngcac lllieu lama ca:tchungVaGcac t~pcan,dQc theogia trtcuamieutit.Ch~nghC;ln, lieUchungtaba:td~u b~ng t~p chua nhungnguai VOlta'tca inau m~t va hlnh thanhnhi€u t~pcan theomall cua illa:t, m6i t~pchuamOt 111aU.Nhung thu~tloan nay lien bO d~c-bi~t,chungduQc thtfchi~ntheochu£nkhaiquat top-down. Top-downhaybottop-up, n6i chunglu6n la InOtlien trlnhqui nC;lp.Th~tla sai l~mlieU c6 nhungl~ml~ntung' ph~nva suydi~n.Be thljchi~nmOteachchinhxac, chung tanueuta phudngphaptudnghj v€ t6ngquatvachitiel. . MOt cachkhai quat(Bottom-up ),'la rutra nhungd~c tinhchunglon, t6ntC;ligiuacacvi dl.l.Nhungd~ctinhchung nay thuangxua'thi~ntrongh~ubet cac vi d\l.Khi chungta chqnphudngphapbottom-up,thlva'nd€ la rutra nhungd~c Hnhde l~mr5 slfphan bi~tgiuamOtVal vi dl.l.M6i vi d\l. . dllQcky hi~u bdicac d~cHnhmakh6ngduQcchIfa bdi nhungvi dl.lkhac. 2.1.5Ghli nghlacd sa cua vi~choc trong caevung ly thuye'tmanh. Giai nghIa'vi~chQcmOtcachnghiemng~tnha't(EBL- explanation-baselearning) 2.1.5.1Ghii nghiaEBG mQteachtruegiae: EBG choly thuyethoanthi~ncualllOtvungInatC;lid6 vi~chQcchQnvi tri va vi dl.lhuya'nluy~ncuanOidung dl(()ChQc . Trang34 Be)iVIla h~th6ngly thuyethoanthi~n, EBG bietmo tanOidunghQc.MQcdichcuatientrlnhhQcHihQcmQtva'n d€ 1110i, "khah6n" motanQidungnay.B€ d'.1t JuQcilllJC dich EBG da:lamnhu'sail : Su-dQngtri thuccuavungly thuyet,no chungminhr~ngvi~chua'nluy~ncacvi dQduQc ho'.1t dOngtrongviIngcuanQidunghQc. B~ngchungcua c1i€unayduQcduarabdi vi~csU-dQngmQtlieuchufinho'.1t dQngmavi~ck€ v€ stfmientalahoanloancachbi~t. Cac baivitt v~vi~cthall1giacuaquatrlnhchungminhdu'Qcxet laxa'thay. Chli yquan trQngcuatieuchufinnayvuQtleu tr~nta'tcahi~uquacua vi~cxU-Iy. Stfc~t botvi~cch~ng ll1inhdliQCsinh vao ll1Qtca'utruc giai nghiaIlia chuacac thanhph~ncuam~nhd€ g6cda:duQcSU-dQng'Nh~cac nh~nhiettrongDE JONG va MOONEY (1986). Bi~unay thall1giavaostfc~nthietcftnd'.1ttoi trongquatrlnhchung ll1inh.M0t t~P hQpcuacacvi dQtronghua'nluy~nchung l11inhquacacgiainghiaca'utruc.Kecquacuavi~cthQtIiIi nay la va'nd~1110i,VOlnhi~umotaho'.1t dOngcuacac n0i dung. D€ changll1inhEBG, ta SU-dQngVersion Prolog VOl cac vi dQcuaSAFE -TO - STACK lam t~pvi dQduQcdlia ra tu' Mitchell,Keller va Kedak_Cabelli SAFE- TO - STACK chI ra cac vi dt).hQcVOlnhi€u qui t~cco nhi~u hi~uquah6n'quyt~cxepch6ng,khi cho1110tIlia tel, mQtIy thuyetcuaStack,va 1110tvi dQcuamQthQpthanhphffl),, ' BOX 1 , c1u<,1cxep tren bang thanhphftn,ENDTABLE!. Trong chinhvi dQra'td~cbi~tnay no Kay ra mOtst;1'c~n bietv~gia trim~cnhiencua10'.1iTABLE. Lo'.1idftulien cua thongtin co quanh~toi hOpd~cbi~t BOX 1va bangd~cbi~tENDTABLE1. 01 ON (BOX1 , ENDTABLEl). 02 COLOR (BOXl ,'RED). 03'COLOR'( ENDTABLEI , BLUE). Trang35 04 VOLUME (BOX1,10). 05 DENSITY (BOX1,1). 06 FRAGILE (ENDTABLE1). 07 OWNER (ENDTABLE1,CLYDE). 08 OWNER (BOX1 , BONNIE ). 09 ISA (ENDTABLE1, TABLE). LOC;lithuhaicuathongtinla m6iquanh~toin€n tang tri thucv€ caev~t x€p chang, clingcon du(jcgQila ly thuyttVUllg(do111ailltheory). CIO SAFE -TO STAC~(x,y):-NOTFRAGILE (y) CII SAFE -TO STACK (x,y) : - LiGHTER (x,y). Cl2 WEIGHT(x,w) :-VOLUME (x,v),DENSITY(X,D ),W IS V * d. C13WEIGHT (TABLE, 50):- C14LiGI-ITER(x,y):-WEIGHT(x,w1), WEIGHT(y,w2 ), LESS( w1,w2) . . CIS LESS (x,y) : - x<y. LOC;lithuba cua thongtin bi~udi~nlamQt slj thoa UlancuaBOXI vaoENDTABLE1 .Chungtamu6n chung ulinh r~ngchinhbdi mQttho tlJctrongPROLOG se cho u~Qtdiu hoi toi chuangirIng thongdich PrologNO dQc C16 : -SAFE-TO-STACK(BOX1,ENTABLE1) . Vi~c chung minh ti€p tlJC du(jc chI ra bdihlnh 8- 1cung ca'p bdi chuangtdnhthong dich Prologhoanhao nha't. giclinghia EBG rut lui mQcdichchungquac(u trucva sinh ra toanbQt~pcuaU1QCdichchung.T~pcu6iclingcuaUllJC dichconla di€u ki~nmoiclIovi~cdC;ltdu(jcmlJcdichchung Quyt~chQcla ; SAFE -TO -STACK (oBjl , oBj2); Trang36 Volume( oBjl , vI ) , DENSITY (oBji , dl) , LESS - THAN (VI xdi ,50 ), ISA (oBj2, TABLE)' adayVI va dl1acacbie'nva 50thuduQctll CI3 . 2~1.5.2EBL va S~ttinh che' M~nh cua If .thuye't Voi slfqUail1ycuacac1ythuye'thonghoanthi~n, tll tlldngtrQngtam1athlfchi~ncacchungminhkhonghoan thi~nbatcac pheploancohQC. M1).cdichcuaphu'dngphapnayla: Chom(Ht~pcacmieuta,cacvi dl,l,va cacnOidung 111acacvi dl,lthuOcvan,haytImra phuongphapco hi~u quanha'td~"nhijnbitt" cacvi dl,l.Phuongphaptra10idlfa van1ythuye'tthongtin:No uoc1uQrigs6cacthongtinlien quailVOl1110inlieula vachQnthongtinhull ichnha't.B~ng vi~capdl,lngcacmieutathanhGong,mOtdiy quye'tdinh dll<,5CKaydlfngsanchocoth~nh~nbie'tcacvi dl,l. Vi du 1: Ghi sa tab~tdfiub~nghatnOidung (A va B) , Bu'Qc111ieutabatbamieuta(kichco,dantOc,gindlnh)va co th~1a'ygiatri (nho,Ion)chomieutakichco,(Phap,Buc, Y) chothanls6dantOc,va(cogia'dlnh,dOcthan)chotham s6giadlnh.Gia sudingnOidungduQcduarabatcacvi dy trongbang8~1va'nd~dd4Y 1atlmra mOtcayquye'tdinh tot uu d~nh~nra nOidungA tll nOidungB. VidQ2: ' 'Gia sl}'dingtaco 10vi dl,lduQcmieutabatnghia cuabonnneuta.vacacgiatricuano,chiratrongbang8-2. N€n tangtri thuGduQcbi~udi~nbatHnhcha'tcuacacmieu tit.Chungco th~gfingi6ngValXl, vi dl,lmOtJl.'1jeuta v€ 'j Trang37 trQnglu'Qng.f)i~u nay se du'Qcbi~udi~nvoi rang thli'c: {light<medium- weight<heavy} MOtvai weu tadIng co th~du<jcffutruegi6ngX2va X3. N~ntangtri thucquanh~toi X2 co th~duQcrhobdi s~'phanlo~icuaph~nchunghlnh 8-10' Chungco th~xay ra tru'ongb<jpkhangco~tri thuc riengco th€ rho mOtmieutit,nhuv~yX4 la IT1Otweu ta nhi'>be. . Tri thucnay du'Qcbi~udi~nbdi mieu ta v~tangcac gia tri nhu'mOtdiy phi cffutruc ( mall vang,mall do,mau h~tde) TABLE 8-2 2.1.5.3Xdy dungRi Mieu tel1:D€ chungtama telmOtchu6inay n~-.4nbietR nhtiladuQcmieutelbdi: . R=(Xi - Vi ) & & (XK =VK) Xl X2 X3 X4 el light boy baby ted e2 light girl baby blond e3' light bqy child chestnut e4 medium women teenager. chestnut es medium boy child ted eG heavy girl child blond e7 heavy man teenager ted es heavy women teenager chestnut e9 heavy man adult blond elO heavy women adult chestnut Trang38 (j dayXj la ngu'oimientavaVj la nhil'ng iatrjcualllieuta nayho~ctachbi~tvoi nhil'nggia trj co th~trongvi dt;l,theo san4 chttcDangnh~nbie'tkhacnhau: X2 =daD6ng X4 =daD6ngV daDbaVcontrai X3 =[c~ubecon thanhthie'unieri] (Xl =daD6ng) &( X3 =[c~ubecJn thanh thie'uflieD]) Mieu ta 2: MOtt~pcandu'Qcnh~nbie'tbeJimOtchuenang nh~nbie'tla t~pcancuacacvi dvmangu'oimientachI ra cling gia trj nhu' chUG Dang nh~n bie't. Trang39 Conngu'oi /~ Phcii ill!;lOh /~.. /~ Phciiye'u Dan ong diu be Danba cobe Thanhthie'unien Danong Danba Congcii Hlnh 2.1.5.3 "511phanlo~i" cuaph~nchunggiuacae "'" ? linen ta Ch~ngh~nchileDangnh~nbie"tRl:X2 X2=daD6ngV daD ba V c~u be: nh~n bie"t cae t~p con {el,e3, e4 ,eS,e7.eS.e9,elO}.Chile DangR2:(Xl=heavyV light) & (X4- redv chestnut)nh~nbie"t{el,e3.e7,eS,elO}.T'.lora mQtchilc Dangnh~nbie"td€ nh~nbie"tva lo~ibo ej:G(ei/ej). Khi b~td~u,G (el/e) la t~ptrang.Ne"umientaXi co cling gia tri trongei V&trongej, r6i Xi da:kh6ngxay ra trongG(ei/ej).Ne"umientaXi la phaonbi~ttrongeiva ej,d~t Vj la gia tri cuaXi trongej,thlb6 sungll1Qtphep ngatV(Xi -+V) vaoG(eJej). Trang40 Nhu lllQtvi dl;!,e1va'e2khacnhaubai X2 va X4.Tronge2, X2=girlva X4~=blond.N6 keo theorAngG(e1/e7)=(X2 -:f- girl) V (X4 -:f- bIQnd).Tu'ongttfc6th€ tha'yrAngG~e1/e4)-(X1 -:f- lllediull1) V (X2 -/=Woman) V (X3 -:f-teenager) V (X4 -:f- chestnut) . So sanhlllQtvi dl;!va mQtt~p:Chungtabaygioc6th€ Hnhchucnangnh~nbiC'tchungnha'td€ ma nh~nra vi d~lej va lo<;libo t~pcac vi dl){ej}.Chungta ghi G(e/e.D.Bay chlnhla t~p Ri tadffn6i a tren. Cho n16iektrong{ej}.Tinh G (e/ek).KC'th<;1pta'tc,l"G chu'aG(e/{ej}): Ri =G (e/{ej})=&ekG (e/ek) ek-E{ej} Vi d~l,G (e1/{e2,e4})=G(e1/e2) G(e1/e4)=(C::2 -:f- girl)V (X4 -:f- blond))& ((Xl -:f- llledium) V (X2 -:f- Woman) V (X3 -:f- teenager)V (X4-:f-chestnut))mala d~trongd~ngchu~n 2.1.5.4Phattri€n caeehuenangnhanbie't: Stfphat tri€n du<;1cthtfchi~nbaivi~csli'dl;!ngthong tin sohQcva nentangtri thuc.Ky .hi~uphanlo~icaitiC'n toi thi€u socacdi€m ngat ...cai tiC'nmQtcachdongiancac 11lieutava cacdi€lll ngat bai cacdo~nkhimien1£1la mQt duangthing. 2.1.6GHEP CAD TRUC: 2.1.6.1Mo taviee till kie'll ea'utrue: Hai d~ngtilll kiC'mca'utruc nC'uchungvu<;1tqua ten cho caehangsovacacbiC'nmangayl~ptuexacnh~n.thong. thuang,d<}tE1vaElla haicongthuc.th1E1timCalltrueE2 nC'ut6nt~illlQteongthucC va2thaythe51& S2saoeho: CDSl.C =E1va S2.C- E2 0 ThaytheSl va52khongbaagiod~tmQtbienbang 1110tcongthuchaymQtham.. ? . d daychuy apdl;!ngvi~cthaythechomQtcongthue. Trang41 Phai hi~ur~ngvi~cHmki€m ca"utruc(structmatching - SM) e6 th~kh6 khankh~ngdinhmOtk€t lu~n.M~cd~u v~y, trongtruongh<;Jpt6tnha"t,mOtnguoic6 th~sudl,lng thongtin dtn tll'cacvi c1l,lkhacd~bitt cachchungminhslf c~nthi€t d~ap dl,lngmo ta nay (d€ bi&tchi tiLt xin xe111 Vrain). Th~111chi n€u SM hu hong(ma c6 th~thu'ongxay fa), hi~uqua cua vi~ccO'g~ngd~tVaGSM c6 th€ vlin la hay. Chung ta n6i r~nghai congthl1'cdadu<;JcSmatchkhi moi congthucc6 th~thichh<;Jpvai cac thi nghi~mda du'<;Jc sl( dl,lngd~d~tchungVaGSM. N€u SM thanhcong, tb1 , " S111atchingdu<;Jc1116ta d~d~t chungVaGSM. N6i khac di , . S111atchingchuacack€t quac6 th~t6tnha"tronghuangHm ki€Ul caccongthl1'c. 2.1.6.2MQt vi du don ghlncua vi~c 8M thanhcongo D~chungtaxethaivi dl,lsaudayEl bi~uthiA rtong len H va E2 bi~uthiC va D nhuchIra trongh1nh8-11. Caevi dl,l co th~du<;Jc111ieutabdinhli'ngcongthucsauday. . El '=SQUERE (A) & SMALL(A) & UPON (A,B) & ClRCLE(B) & BlO(B) & UNDER(A,B) &ORCLE(B) & BlO(H) & UNDER(B,A) E2 = TRIANOLE(C) & SMALL(C) & LEET SIDE(C,D) & SQUARE(D) & SMALL(D) & RIOHT- SIDE(D,C) . D~chung'ta gia thi€t r~ng thli b~ctrongh1nh8~12 duQccling ca"pchoh~th6ng. Phan lo~tinaybi~l1thi ngfi' nghlatri thuccuachungtav~th€giai nh6be"mavai vi~c hqc dangthtfchi~n trongSM cuaEl va E2thudu'<;Jctll chungtai congthlictu'ongdu'ongE'l va E'2,nhuv~yE'l - tl((jngduongvai El va E'2tu'ongdu'ongE2trongth€ giai nh()be (tucla la"yVaGsO'd€111ngfinghlacuan6).Khi vi~c Sl(11du'c}cthlfchi~nE'l va E'2duQCchia thanh2 ph~n: Meala versioncuaEl vaE2vai bi€n du<;Jcg()itrongph~n thancuacongthlicSmatched.K.hiSM thanhcongph~n Trang42 thancuaE'l va E'2 duQ'cllla ta ,Thanhphc1nk.h1c, duQc gQiIa bindings(cuacacbi€n ), chot{tcacacdieuki<%ncfin thi€t chophfinthancuamaiEi' duQcmatathuongxuyen VOlEj tti(1ngling. Vi<%cxu Iy b~tdfiunhusanday.Gia sudingchungta OU'(}Cbi€t r~ngcacmientacuaphc1nFORM Ia nhi€u h{p danhonslfphanIo~iTOUCH. ChungtaVI v~yb~td~uc6 gangphoih<.1pSQUARE va CIRCLE cuaEI voi SQUARE vaTRIANGLE cuaE2.Chungtad~tA trongEI vaD trong E2b(jibi€n gia?x,vachungtaluugillbQnho cuabi€n nay. Bi€u naydantoik€t quasan: (chu,yr~ngdan:isach cua bi€n n~nltrongd{ungo~c) E'l = SQUARE(x),& SMALL(x)&UPON(x,B) &CIRCLE(B) & BIG (B) & UNDER(B,x) & (x =A) J. Hlnh2.1.6.2.a . 130 C~D"D Ella phc1nbentraiE2la phc1nbenphai Trang43 Touch / Side-byside /~ ~ Upside-down /~ Left~side Right-side Under Upon FOrm / '" Convex /~ Polygon Ellipsoid /~ /~ Square Teiangle ... Circle ... mnh 2.1.6.2.bPhanlo~iCaCquaDh~chungtrongcac mieuhi. , E'l =SQUARE(x)& SMALL(x) & RIGNT- SII?E(x.C)& TRIANGLE(C) & SMALL(C) &LEFT -SIDE(C,x) & l(x=D)} Blide ke tiep stYd\1ngphan lo~i bdi vi~eph6i hQp CIRCLE euaEl vdi TRIANGLE euaE2.Taviet: E'l -SQARE(x) & SMALL(x) & UPON (x,y) & CONVEX(y) & BIG(y) & UNDER(y,x) & [(x=A) & (y=B)] E' 2=SQUARE(x) & SMALL(x) & RIGHT-SIDE(x,y) & CONVEX(y) & SMALL (y) &LEET-SIDE(y,x} & [(x=D) & (y-C)] Vi dl;}naychi r~ng111Qtkhi SM da:duQethl;tehi~nbudesinh tl;tn6 da:trdnent~111thliong.-Chunggill trongvi~esinh tftt Trang44 ~abuQc~lingtOtcongthucSrnatchedvarottfftcavaovffn d~chung.Noi eachkhac,ky thu~tSM chophepchungta gictn1cacquyHicchungn6i tie"ng(Michalski)chi tOt"quy Hic di~uki~n dung", IDa trd thanhcac .cong thuc Sn1atched.Tfftca loi keosucrnC;lnhvaotrongquyt~edi~u ki~ndung. Ta'tcacacnguyent~ckhacla soydieDngheo.Chung taphaithuanh~ndingchungrninhthongthuongneud tren vlln () dUal dC;lngnghien CUll . Bdi VIBIG va SMALL dftkhongthuQcvaophanloC;li chungtrongvi dl)cuachungta,chungseduQcdunglC;liva bdiVIxvay luauconhunggiatrtkhacnhau,seduQcchu9 trc)ngvi~csinhcu6icling,IDa: Eg =SQUARE(x) & SMALL(x) & TOUCN(x,y) & CONVEX (y)& TOUCH (y,x)& [(x:f:y)].Trongvi dl;Jnay, ngttoitaCallithffydingrnQtnguoicoth€ sadl;Jng19thuye"t giang v x,y [TOUCN(x,y)TOUCN[(y,x)]trongthu tlfo~chungrninhchung 2.1.6.3SitdungIf thuye'tdciciHtie'nchung. No th~tdedang,duQcchor~ngvi~csadl)ng19thuye"t co th€ dllnde"nhi€u kh6khan,bdiVI~Qtkhidftthlfcslfdi vaochungminh19thuye"tIDan6i tie"pnhurnQtngu6ng6c totouQcgiai quye"t,khongduQcgiai quye"tvffnd€.Trong truonghQp~M, rnQtai do dftduQchuangdllnbdi Slfc<ln thie"td€ d~tcacvi dl)vaolTIQtdC;lngtudngtlf , va thuong nit kh6d~chunhrninhrnQtCatgl dochodedang.Chungta khongth~chungminhrnQtcachlnhthucdi€rn nay,nhting, " vi dl)sanday,IffytuVrain(1987)coth€ duarakhAngdinh cuachungta.Khi b~td<luhatvi dl) IDadftkhongxacnh~n,. chungta chi ra r~ngchungkhongbaagio co rnQtsinh chung,!lrnra bdi sa dl)ng,19thuy€t lien k€t voi cacdi€u xacnh~n.Vi dl): Trang45 El =MAMMALAt-T(A) & BRED -ANIMAL(A) E2 =TAME(B) & VIVIPAROUS(B)llla cacly thuy€t sanda:duQclien k€t : R1: Vx[MAMMALAN(x) & BRED-ANIMAL(x) =>TAME(x)] R2: Vx [TAME(x) & VIVIP A ROUS(x) => MAMMALiAN(x) R3:Vx [TAME(x) =>HARMLESS(x)] (j dayv laloan thedinhluQngx. Stflien k€t logicva =>hamylogic. BUGCd~uliencuaSM la t~mthuang(j day,chungta ' ' d~t h~ngsobCiilllQtbi€n x va giii'acacvi dlf tu'dngdudng. E'l = MARAMALAN(x) & BRED-ANINiAL(x) & [(x=A)] E'2=TAME(x) & VIVIPAROUS(x) [(x=B)J;. Bc)iVI, cacxacnh~nkh6ngco ph~nchungKayfa,fa xet d~ulien (Thutt!naykh6ngphanbi~tVachIchophepmQt tronghhii'ngvi dlJduQccho)..Xacnh~nE'1MAMMALAN. Chungtath:1yt~ng,chungtacothebuybe)xacnh~ntll E2, khisud9ngguyt~cR2. Chungtanh~n: E" 1=MAMMALiAN * (x) & BRED-ANIMAL(x) & [(x=A)] E" 2 = TAME(x) & VIVIP A RODS(x) & MAMMALiAN. ** (x) [x=B)] The MAMMALAN cuaE'l da:duQctdnhbay,Bay chinh1a ly do de E" 1duQCdaublllQtd:1u*, mQtE"2 duQcrut ratn vi~c Sl( d9ng cac 1y thuy€t, llla duQcdaubd:1uboi2 Hin d:1u*. : Ph~nk€ ti€p BRED-ANIMAL kh6ngduQCdaubd:1u kh6ngcoguyt~cnaocotheduQCapd9ngchoE"2 de~alll ro cacbienthicilaBRED-ANIMAL trongdo.M~cd~uv~y, chungtadanhd:1uvi~capd9ngguyt~cRI toiE'\ sad9ng vi~cxacnh~nlien quan,BRED-ANIMAL. Khi kiemtra hi~uquacuaap d9ngnay,chungta th:1yr~ngno sinhra Trang46 vi~cxac nh~n lien quan,BRED-ANIMAL.Khi ki~mt1'a hi~uqua cua ap dt;tngnay,chungta tha'y1'~ngno sinh1'a congthu~nguyentaT AME(x) va do la mQtslfKay1'acuax t1'ongE"2 d~dothnnhfi'nghi~ntuQngKay1'anay.VI v~yta phaiclPd\lngRl choE"l. Taco: . . E"l =MAMMALiAN * (x)& BRED -ANIMAL*(x) & TAME** (x) & [(x-A)] E"2 = TAME*(x) & VIVIPA ROUS(x) & MAMMALiAN**(x) & [x=B)] Bay giGta chi thong d6i chie'uVIVIPAROUS t1'ong E"2khongco quylac co th€ duQcapdt;tngchoE"1d~khie'n no du(,1cbi~uthi 1'51'~ng.Nguyenlac duynha'tco th~duQC ap dt;tngt1'ongE'2quanh~toi VIVIPAROUS 1aR} Nhung nophil gioithi~ucongthli'cnguyentuMAMMALiAN(x) 1110ta duQCc16ichie'ubc1iVIvi dt;tcua no, da:duQCbat dftu. Khongco quylac khacco th~duQcap dt;tngVI v~yta xac nh~nVIVIPAROUS c1~nha't1'~ngno da:bi giai quye't vdi vi~cchua: E""l =MAMMALiAN*(x) &.BRED~ANIMAL*(x)& TAME** (x)& [(x=A)] I E""2 = TAME*(x) & VIVIPAROUS*(x) & MAMMALAN**(x) & [x=B)] TKt ca nhfi'ngc1i~uco th~Kay1'ada:duQCgiaiquye't vdi 111QtSM hoanthi~nkhongco th~,.vI Smatchingho~t dQngdungc1day. . Bay giGbuocsinh1atfim thuong:MQt di~mdung khongt6ngquatda:Kay1'a,chuasinh: G - TAME(x) & MAMMALiAN(x). Vi dt;tnaychiKay1'acachchungminh voh~ncoth~Kay1'a,Cacvangl~pcoth~d~dangbip):1a, , buy phongcach ddngian bc1iVI chungda:khonb cai tie'n ' tr~ngthaiSmatchingcuacac vi dt;t.T6ngquathdn,mQt nguoicoth~sudt;tng1ythuye"t- chungmintk5'thu~td~cai tie'nll1UCtudngtlf duQckhampha1'at1'ongdamcacvi dt,l. Trang47 Nhu'nl(Hh~th6ng(j dudi stf phanbuy trongnh6mcua chungta (VRAIN,1987).~6 khanglien ke'tmOtIdp Iy thuye'teachnganvacaethu~tloansinhnhungthe'VaGd6la lay vaGlllQteachdutkhoatlo~icuacacchungminhd~Qc yell cftubdi nlayhQc. Nhu mOtvi d1)khacthuong(ma khonghoanthi~n), nosekhangchophepai sud1)ngcung ly thuye'thaiIftntrongmOtvi~cruttrich. 2.1.6.4:Ke'tluan NQidungneuireDdaybi€u thicacphudngphap hQcchuye'ud~t tdibdiquyn~p,suydi~nho~ccacynghla tlf<ingttf. Stfsuydi~ntie'ntdiclingcapmOtd~ngh<Jpcua caclo~ikhacnhaud€ gi,Iinghladingc6th€ chuacacvung c6 lllQtly thuye'tlll~nhvahoanthi~n(EBG)mOtIy thuye't nl~nhnhungchuahoanthi~n,va mOtIy thuye'tphftnm~m nlachu'adu'Qchungminhhoanthi~nc6 th€ duQcve leu. M1)cdich cuachungtala chIra tat-cacaclo~icuatri thuc n~ntangdaduQchQct~pc6th€ dudcgiainghla vafilata d€ c6 th€ hi€u duQc. Nhi~unghienCUllcftnlamco th€ cho mOtmata trtionghQpd€ c6 th€ hi€u. 2.1.6.5Noi rongtri thueearnnhankhi bi tdenghen: Tat canhfi'ngdi~uk€ ireDdadtiQCki€m traireDvi~c ap d1)ngVaGcuQcs6ngvdinhfi'ngthayd6ivi~cthanhcang ph1)thuQcVaGnhfi'ngdi€lll san: . ID~t~olllQtsO'(ML) mayhQc,phftnm~mltiutrfi'da du\icap d~lngVaG11nhvtfcthu6clllen,thuongthtfchi~nt6t hUn. ES xay dtfngbdi vi~ctrahoi ID3clingda duQcap d1)ngbdicangtybaahi€m vanhuv~ydatie-tki~mmOtsO' Idnti~n(Michie,1988). INDUCE ,dasinhra ES dftutrendattfdOngd~t duQc caequyHicnladacokinhnghi~m. Trang48 Ghepceiutrucda duQcap dl.JngVaGvi~cdi~ukhi€n v~n chuy€nhangkhong.(Cannatvavarin,1983),vachungtase noinhi~uv~no(jcu6icuake'tlu~nnay. Teitcacacphuongphap suyd~ndaduQcap dl.Jngd€ giaiquye'tcacveind~khacnhau.T(~timucnay,S1ftie'ntoi sectjckl hUllfehchostjtinhche'cuaES dangt6nt~i nhli chungtase nneuta no,gio dayvoi nlOtES dangt6nt~i, cho1110tt~pcacquyt~csap bi€u thin~ntangtri thuccua kinhnghi~m,cacquyt~cseichophepcaitie'nES quatudng laybeithliongvoikinhnghi~m. l{.inhnghi~mstYdl.JngES. Ne'ukinhnghi~lllcheipthu~nES thlmOtvai quy lu~tsinh cuacacnguyent~cdangt6nt~iva dliQCc6 thii'.Ne'ukinh nghi~mho~t dOngkhacVOlES thlcacnguyent~chi~uqua nloi co th€ duQC hQc (Raitchell, Mahadevain,va Steiberg,1985).Ne'ukinhnghi~m111aUthu~nVOlES , cac quyt~c1110isedliQcb6sungd€ hoanthi~ntri.thuccuaES . Teitcadi~unaychirar~ngML(mayhQc) dagiupcho stj camnh~nhaycac quyt~cnlOta, nhugi6pgiai quye't trang phcin tri thuc cam nh~n bi t~c nghen , (Feiguchanl,1981).M~cdciuv~y,trongtudnglai xa,ch6ng tasenh~n . thucduQcphcinquailtrQngcuavi~capdlJngML toi ES. 2.1.6.6N6i Y Cac h~th6ngdangt6nt~ico y dinhgiu l~iphcin' . nghienCUllva phattri€n cua cac congty phattri€n chung thaythe'vi~cchuy€n d€ ap dlJngcac I1nhv1fcnhunguoita lllu6nco mOttrangnhungly dachi.nhchovi~cthucnaybdi vi~c ap d\lng rOngrai cac 11nhvtJ'ccftnphftn m~mduQc c6ngb6. Hi~ntC;likh6ngco cach d€ chungminh mOtES ngoC;litru mOtVal lOC;livi.dlJ tudngttJ'chonhfi'ngsinhvien da tungtra1. Trang49 Chungtakh~ngdinhdingky thu~tmayhQc(ML) la c6ngClJ to'tnhfttco th€ hi~nthaiphattri€n nhudff lieu. Bi€u naycoth€ lamsongsongtronghaicach: .. Ky thu~t nlayhQchi~nthaigiupta d~tcactri thuGdanh riengchovftnd€ dim nh~ntri thUGcuaES va b~ngvi~c clingcftpmQtvaichungminhtn!cti€p . . 2.1.6.7Vdn d~earnnh(intri thuedaehie! : CacML chinhbanthannocftnduQcky hi~ubaimQt sO'cacthuQctinhnhuthayd6i chungtunhungthamsO'ban dftud\fatrencac tri thUGn€n tang.Vi~c luu y cacchuang trlnhnlay hqcclingduQcdanhchonhi~mVlJth\l'chi~ndua racacchuangtrlnh, ch~ngh~nd€ xoacacmientacuacac thayd6iduQcth\fchi~ntrongcasatri thUGd~cbi~ttr~ng, '. thaicilacack€t quaduafa.Tuangt\f nlieutan€ntang tri thuGcuachuangtrlnhML d~cbi~ttrongn16itruangmacac guyt3:cES conghIa. 2.1.6.7.1Hie" lqe motES: Gia su r~ngchtingta co nlQtES xayd\fngtrongmQtcachphanlo~i(HurmanES - HES ) vanlQtchuangtrlnhML make'tquaduara la nlQt chu(jngt~lnhth\fchi~ncacnhi~mVlJ, ho~cit nhfttthamgia vaocacnhi~nlVlJ , tuangt\ftoi HES.Bay la vi~cxayd\fng ES nlQtcacht\fdQng(MLES). Khi phantichguyt3:cHES , nglioitaco th€ phantichs\fsail~chh~thO'ngML saocho no sinhra guyt3:ctuang,.t\fnhuco th€, toi rllQtphan.tich duoiday.N€u nhucoclingguyt3:c,thlslfphan tich moi e1::'iduQcsinhramQtcacht\fdQngsed~ntoislfthamgiavao tri thuc, rlla slf thO'ngke cacsai l~chse tralai di&udo. Bi€u naythamgiavaoh~tri thucvacohi~uIlfcvoinhung nguyent3:cn€u tri thuGt\fnodffcohi~ul\fc , ma.phantich l~i nhunglopky thu~tcohi~ul\fc. Chungtaclingco th€ corl1Qtvaikinhnghi~nl. Trang51 11.2BAN eRAT LY LU~N vA PHUONG PHAp DE ,.!' XUAT Nhu'ph~nly lu~nv~lllayhQcdalieu (j tren,ly ~huye'tv~ Dlayhqcr:1'tsanvarOng.Tuynhienkhi lingdl,lngvaothltc te'coth€ chIc~nap dl,lngmOtph~ntrongnhi~unguyenUtc. Ph~napdl,lngcuata(j dayla apdl,lngthu~tloantachlop trongcacdoi tu'Qng.Trongthltcte'voi cacmftunh~nd(;lng c6 truy~n,nhi~mVl,ltrungtamla phanlo(;lichomOtmfiu, nhi~mVl,lc6tinhnguyent~ch:1'pdftnnh:1'tla hayquye"tdinh xelll lllftu d6thuOclopgl.?? MOtcachchu~nh6a, taphelidu'Qclingca'pb~ngvi~chu:1'n luy~nv~cact~phQpmftu,tITCla, b~ngt~pcacmftutase bitt lopcacthanhviennhu'dadu'atrongh1nh2.2,MOtlop thanhvienph,HhQcmOthutl,lCmac6th€ sudl,lng-d€phan lo(;lichinhxact:1'tcelcacmftutrongt~phu:1'nluy~n.K€ tie'p pheliki€lll traxemJopthanhvienc6th€ ducjcxe'pvaolop c6lllftuvoicling111Qtt~PhQpd6i1ucjngkhong.?? Hlnh 2.2 a.BO{l1lhuiill luYfll: ~ b.DO{l1lkii111Ira: Hu:1'n Thii tl,lC luyn tp cho '" Phan lo(;liVH;C 11laU {X} -+ hOc 11101-+ " lop phudngva lien h phapphan thanhvien loC;li. \Trang52 Phu'ejngphap ta chQn lva (j day Ia phuong phap TOP_DOWNVIcacthanhviend~ulacacvi . dQ,'in1,~hlco mQtvi dQduongduynha't,do chinhIa ke't qua.VI caclopd6itu'Qngcuatala rOnglon,quachQnlQc, phanlo~i1116iv dQba'tky phaidu'Qchua'nluy~nvasando co th€ chQndu'Qclop thichhQp.Tronglop tu'onglingcac ph~ntli l~iv§:nla ambdiVIvi dQchIdungvai mOtniong hQptu'onglingduynha't. . SandayxinneumOttru'onghQpCQth€ cuavi~clingdQng nguyenly hQctvdOngvaclingph~nnaGphananhbancha't ly lu~nduQclingdQng. .I' .I' " .I' ,\? .I' ?:::. II.2.1CAC GIAO VIEN CO THE SAISOT NGAU " NHIE N CONG THUC HOC BEU BEU DNFVOI LOIPHAN ? " " " " " CUA THANH VIEN KHONG HOAN THIJ::N ~~~ <~~~ Chu d~: Gioi thi~uthu~t loanhQckhisadQugmOtlorphan tu'ongdu'ongvamOt10iphanthanhvienkh6nghoan thi~nVOlmlicsaisotcoth€ cha"pnh~nduQc 1.BAT VAN BE: . Celc thanh -+ .Phan loi -+ Tac dOng .,, ? ;! hQp tuonglingVIeD cua tong lop chu'a li. toi tung dtiQcbie't. lop d6i tuQng. Trang53 Xet velnd~d~ytho maytinhnh~nbi~tdOngtiT trongdiu ti~ngAnh.MQtcachdongiangiaoVieDbi~udi~n cac Calinl§:u,chi ra mOtvai dOngtu (+,positive)va chi ra . 11l(Hvai tu khongphai dOngtu (-, negative).Co th~neu nhungVI dlJ magiaoVieDkhongbie'tchilcCalitraloi nhung vi~chQcvelndliQCti~nhanhtrongnhung truonghQc11la cacsaisotdungtrongmUG.coth€ chelpnh~nduQc. . ?' ,,' K ;:;. II GIAIQUYE.TVANDE: Xet t~P bi~nXl XutrongGongthuGDNF voi bi~n N nguyenduongch!ngh~n n=20 Xl X4+X2XI - X3 - X9XSX12X3+ Xs .... sO'cacthu~tngutrongGongthuGdanhduQcky hi~un1 trongVI dlJ naym=4.Chli yrAngcomQtthll~tloancohi~u quad~tIlll sO'nhonheltciia cac thu~t ngucuaGongthuG DNF d~ud~u : Khonggianm~ucuavi d\lla t~pcacaevectornsO'0 v~1,ky hi~ula {0,1}ll. CongthuGDNF d~ud~uh duQc,coi la ky hi~ut~p cacvectorv thoa11lanGongthuGh, tavi~t hey)=0, ngu<;Jcl~i vi~th(v) =O. Ta xelll khong gian 11l~U nhu'1110tluc;!11liltCaD.Voi cacpheploan "or" va "and" pheploanluoi 11liltCaD;ph~ntu dlnhla vectorg6hlteltca cacsO'1,ph~ntudayla teltcasO'O.Vector10011kg hi~u thu~t ngu XIX4XS.Ne'uh la GongthuGDNF va v la 111Qt vectortrongkhonggian111~u,v thoa111anh ne'uvachln~u 111Qtvaithu~tnguwcuah,w<v Cac vectorn6idoi (descendants)cuamOtvectorv la teltcacacvectorw trongkh6nggian111~u saDtho w<v voi beltky hAngsO'khongamd,d-descendantscuav la tatca cacn6id5iwcuav111acoth€ chuavb(jivi~cthays6110n Trang54 nh1tbangso o. Vi d\l xet thu~tngfi'X2X3X4bi€u di~nla all L T~p nO'id5i b~c1 (0111,0011,0101,0110),chua thu~t ngfi'chinhbanthannova 3childrencuano. T~P nO'id5ib~c2 la t~p nO'id5ib~c1vat~pchaucua 0III g6nl(0001,0010va0100)(grandchidren). 0011 IUO 0101 QOOO Khi sd dQ.ngcaeCallhoi thanhvieDkhonghoan thien: MOt thii t\lCconquantn;>ngtrongthu~tloanDNF cua Anghi1l1(1988).Lay mOtvi d\l dudngcuanOidungh va su dl;lngcac Callhoi thanhvien d~nit gQnv thanhsO',Vi d\l du(jngnhonhatcuaha.Thu~tloan b~td~ub~ngc6ngthuc n)ng va su d\lngcac cauhoi tudngdudngd~sinhra vi d\l ngli<,icdudng1l1Oi.Ket quacuam6ivi~cnlt gQnla chomOt Trang55 thu~t ngf(lllOi cuahad€ b6 sungtoi gia thi~thi~nthai.Sau III bu'ocxU'ly thudu'Qct~p gia thi~t liongdliongVOlh. Thu~t loanmOlcuachungtadtfatrencungtli tlidng, nhu'ngphii sudvngmOts6loi phan thanhvienchuahoan thi~n.Kh6 khannaysinhIii : QuatrlnhxU'ly co mOts6vi dVdudnghi~nthaiv cuah,t~oliencacdiu h6i thanhph~n cholllai lllOtchildrenv. It nha"tt6nt~imQtthanhvienhoi du(,1ctraloi "Yes" chovectory va v co th€ dliQcthayth~ bdiy vavi~cxli ly duQcl~pl~i.M~cd~uv~y,k~tquavi~c xU'ly dfintoi lllOtvi d\l duongv cuah, saochothanhvien cauhoichoUttca childrenv dliQctra10i"No;'hay"I don't know".N~ucoitnha"tmOtchildcuav tra10i"I don'tknow" tIll v coth€ haykh6ngcoth€ la vi dVdliongnh6nha"tcuah. Chungta duara mOtphuongphaprut gQndliQcsU' d\lngchocacloi phanthanhvienkh6nghoanthi~n.Mvc (1i~hla'HtylllOtvi dvduongkhdjd~uv cuah varutgQnno toi 111Qtvi dVdlidng"thanthich"va "kh6ngquaxa" Valvi d\ldu,(1nghonha"tcuah. Bang vi~cb6 sungta"tca ph~ntU'n61doi g~ngili cuavectornay nhli cac thu~tngu toi gia thi~thi~nthai chungta se d~tduQcllllic "thanthich"khi b6 sungthu~t ngumOlcuahvaVIv~y,dangthtfchi~ncacxU'ly huangtoi h. Tu tudngcuavi~cxuly nit gQntheophlie1ngphap nloi la s11dvngcaccauh6i thanhviend€ tImki~mkh6ngchi nhi1'ngchildrencuav mabaag6mH(tcanhungph~niU'n6i doi "d11g~n"cuaVoVOlY <v llla tra10i"Yes", n~unhliy dl(\1ct1rlltha"ythlvi~ctImki~lllti~pt\lCbangcachthayth~ ychov.N~ukh6ngcoy naotIllltha"ysaukhidfihoita"tca Trang56 nhungphan tll nO'id5i "Bu than thi~n"cua v thl y gill nguyengi:i trioChli y dinp nhungvi~cnO'id5i duQctIm ' " kitSnltheohangngangbitt:dau la childrencua v, r6i titSp theograndchildren...ThamsO'd>l lieUleu dOsaucuavi~c tInlkitSm. 1.Reduce(v,d): 2. Let D be theproperd-descendantsof v 3. For eachYE D in breathfirstorder 4. If nlenlbershipquery(y)="Yes" then 5. Returnreduce(y, d) 6. Endif 7. Endfor 8. Returnv 9. End. Ta bittdaub~ngmOtc~pquailsatddngian.NtSuwla n10tvi d\l dudngcuah va d la mOtsO'nguyendudng,d~t D+(w,d)ky hi~umi~nnO'id5ithti'd cuaw baagamcacvi d~~du(jngcuah,d~t S(w,d)la "success"nghlala S(w,d)= 1 ntSuco w co vi d\l dudngnhanhfttcuah, trongdam,nO'i doidcllanovaSew,d)- 0 trongnhungtruonghQpnguQc lai. San oay xin lieU leu hai dinh ly cua Mingli andLeslie Valiant: Dfnhly 1: Giii sicw la 111l)tvid(ldl/dngcuah, vad la lnl)tnguyen dltdngsuochoS(w,d)- O.Thi D+(w,d)>2d+l.2 Cluc'ng,ninh: Trang57 VI w la.mOtvi dt)du'ongcilah, c6mOtvai vi dt)du'ongw' cilah, sanchow'<w.Bdi VI giadinhw'khongthuOctrong nh6111nO'id6id cilaw, c6 1110tvai t~pbit d-l vi tri chua1 trongw va0trongw'.M6i mOtvectorw'du'Qchuatrongw vat~pit nh1t1nhu'ngkhongnhi€u hondcilanhungbitnay d~t k€t quab~ng0 la mOtthutt!nO'id6i d cilaw sancho chungchinhla mOtvi dt)du'ongcilah (bdiVIw'<w").Nhu' v~ytac6chinh'xac2d+l_2vectokhacbi~tvoiw", d6chinh la k€t quac~nchungminh. DfnhIf 2: . Gill sitw vaw' fa cacvid"(ldlldllgclla h va w>w',thi vdil1l6isitllguyelldltdllgd,D+(w,d)>D+(w',d). . CIUC'llg l1lillh: D~t Z la vectokhongn~mtrongw va w' sanchoz c6 1t~ivi tri 111at~ido w chuasO'1va w' chuasO'O.ChQn11101 ve,ctoy sanchoy la vectonO'id6ic1pd cilaW vad6ng thaila vi dt)du'ongcilah,tath1yz vay chinhla nO'id6ic1p dClIaw vala mOtvi dt)du'ongcilah,trongd6z vay la tach bi~tVIv~yD - (w.d)> D - (w'.d). Ta th1yr~ngz phaichuait nh1tmOtsO'1t~iv(tri iva vectow" baag6mw bdit~P cacbitmat~ivi trikhuasO'0 la 1110tnO'id6ib~cdcilaw (dod>l1a mOtvi dt)du'ongcila h (w" >w') vadi€u naykhacvoi t1tcacacvectongu'Qcl~i cilaZ (vIZc6mOtsO'1t~ivi trithu i.). Di€u naykenthen D+(w,d)>D+(w'+d). Ti€p thentasebantoidinhly chinhcilaReduce.D€ co th€ apdt)ngdinhly thanhGongtagQiReducetrongmOt bl(OCch~ydongian, ta gia dinhr~ng11101vai thanhvien hoi dftdu'Qcthtfchi~nquabu'ocdaot~ocilacacgiaovien coloi phankhonghoaothi~nnhactoid tren.(Dieunaygia Trang58 . / thi€t dingk€t quatraloi dadu'<jcchotru'oc).M~cdli v~y, clingkhongngo(;litru tru'ongh<jptachinh~ndu'<jcdiu tra loi kh6ngnla"yriengbi~tla :"1don'tknow'. Billh lj 3: Choh* la COllgthuch{Jcdiu diu DNF. Gill sit taco 111/)t(/ allhvie11trollgtfjph* vuixacsuittgq,pla p, vanll)t vaicauhoidiidupcxaclfjpkelquatrll 1mtrollgtfjptrii1m cita cac thallh viell khollghoall thifll. Dq,td la 111l)tso" llguyelldu(Jllgcuah, vadq,tg(d)=2d-l_2.Gidsit D-v.d=r vap >g(d).Gill sitReducedupcg{Ji"vfJidolsi;"v,a,dq,tyky hifll vectdkel qua.Co No III so"llho llhal trollg"caesac xllatxiiyra citacacvi d(ldltdllgeuah* trollgtfjphppcac 1161doibfjcdcuaysaotho, sacxuallaS(y,d)=0dupebao b{JcblJi biell giui peed)+pg(d)-l+pI" " " " " " Changlninh: Ta chungminhb~ngquyn(;lp trent~pcac gia tri tang cua D-(v,d)khi b~td~ubangg(d).Chli Y r~ngdinhly 1 daTIlbaodingm6inlQttrliongh<jpgQicuaReduceBeco mQtgiatrinhahoncuaD - (v,d)voigiatrinhanha"tla g(d), Reducephaitral(;limQtvc"ctoy saochoS(p,d)=1. " Gia su r~ngtrongmuccaonha"tcuavi~cgQiReduce, D +(v.d)=g(d).D€ thudu'<jcvcc toy saochoS(y,d)=0, Reducephaikh6ngdli<jcgQid~quy.N6i cachkh4c,giatri khoi d~u dtigQiReducechom6in6i d6ib~cd cuav, va n16idiu traloi nh~ndli<jcse la "no"ho~c"I don'tknow". Trangtrliongh<jpd~cbi~t, ta"tca cacdiu hai chovi dl;! dliongcuah*piulidli<jctni loi "I don'tknow". Vi c6g(d)la vi dl;!du'ongcuah* trongdamn6id6ib~c d cuav, vaboi vi m6ithanhph~ndfidu'<jcdu'aracauhai trudc,th~nlchinodadu'<jctraloi "I don'tknow"voixac Trang58 . I thi€t r~ngk€t quatn1loida:du'<Jcchotru'dc).M~cdli v~y, cilngkhongngo~itru tru'ongh<Jptachinh~ndu'<Jccautn1 loi khongma"yriengbi~tla :"1don'tknow'. Dinh Ij 3: Choh* la conKthuchQcdiu diu DNF. Gia sit taco 111l)tthanhvientrongtljph* vaixacsuatggpla p, va.1111)t vaicauhili diidzt{JcxacIljpkefquaIra 1mtrongtljptra1m cua cac Ihanh vienthong hoanthifn. Dgt d la 1111)1sf/ llguyendU(Jllgcuah, vadgtg(d)=2d-l_2.Giii sit D-v.d=r vap >g(d).Gia sitReducedzt{Jcg(Ji.vfJidolsflv,d,dgtykj hi~lIvectdkefqua.Co No la so'nhonhiittrong.cacsac xlliitxayra cuacacvi dl!dlldngcuah* trollgtljph{Jpcac nol doi bijcd cuay suocho, sacxuatlaS(y,d)=0 dzt{Jcbao b(Jcblli bien giai pg(dJ+pg(dJ-l+pI" Cluing,ninh: Ta chungminhb~ngquyn~p trent~pcacgiatri tang cua D-(v,d)khi b~td~ub~ngg(d).Chli Y r~ngdinhIy 1 diinl baodingm6imQttru'ongh<JpgQicuaReduceseco mQtgiatrinhohcJncuaD - (v,d)voigiatrinhonha"tla g(d), ReducephaitraI~imQtve.ctcJy saochoS(p,d)=1. Gia su r~ngtrongmuccaonhatcuavi~cgQiReduce, D + (v.d) =g(d). B€ thu du'<Jcvec tcJy sao cho S(y,d) =0, Reducephaikhongdu'<JcgQid~quy.Noi eachkh4c,giatri kh(jid~u d€ gQiReducechom6in6i d5ib~cd cuav, va n16icautraloi nh~ndu'<Jcsela "no"ho~c"1don'tknow". Trongtru'onghQpd~cbi~t, tatca caccanhoi chovi ell) du'cJngcuah*phaidu'<Jctraloi "I don'tknow". VI cog(d)la vi ell)dticJngcuah* trongdamn6id5ib~c d cuav, va bdiVIm6ithanhph~ndfidu'<JCdu'aracauhoi tru'dc,th~nlchinoda:du'<Jctraloi "1don'tknow"vdixac Trang59 sueitHi pg(d). Nhuv~y trongtruonghQpxacsua'trdv~vec toy bangv,saochoS(y,d)=0, duQcbaabQcbdi pg(d},di~u naydathie'tl~p nenn~ntangdin bancuadinhly. Say giGta gia thie'trang voi vec to v beitky saocho g(d) < D + (v,d) < I-I, nhu dinh ly neu fa. Gia Sll rang ReduceduQcgQivoi dois6 v vad.voi D~(v,d)=r. C6hai. . truonghQpho~cphepgQi d~quy duQcthlfc hoi~n'voi Reduceho~ckh6ng. Ne'ukh6ngcophepgQid~quythlteitcan6id6ib~cd cuav duQcdbihoi.Va teitcacactruonghcjpnayducjctra 101"No"ho~c"I don'tknow".C6 r cacvi dvduongcua.h* trongdamcacph~ntITduQcdbihoivachungphaiduQctra )oi " I don'tknow".Bdi VI truocd6cacph~ntll nayda kh6ngdu<.1cxueithi~nHenxacsueit10di~ncacph~ntll nay la pr. M~tkhac,khicacph~ntll d~uliencualopn6id6ib~c dcuav duQcHmtha"y,CallhoimaduQctraloi "yes"c6vec t(jduQcgQid~quybdiReducetad~tenv' clingnamtrong lop d. Luu y dayla lopn6id6ixua"thi~ntheothntv d~u lien.Cacph~ntll kh6ngphaila n6id6i,cuav' chinhla cac vi dv duongcuah*. M~cd~uv~y v' la n6i d6icua v, D+(v',d)< D +(v.d)(Dinhly 2),VIv~yD+(v',d)<I-I. Ne'u D +(v'.d)<g(d)thld6la gQid~quy, va clinggQid mnc can.Reducekh6ng c6 th€ tral<;timOtvecto y saocho S(y,cl)=O.M~tkhacD +(v'.cl)>g(d)vadi~ugiathi€t cll,a, , taduQcth6aUlan,xacsua"tcuaphepgQid~quyvoiv' va dd€ tral<;tivectoysaochoS(y,d)=Ola: pg(d)+pg(d)-l+...+pr - 1 . Xac sua"tgQiReducelIen v vad d€ tral<;timOtvecto y saochoS(y,d)=0la: pg(d)+pg(d)-l+...+pr~l+pr Trang60 Bieu nay giupta hoanthanhvi~cchungIninhquy n~p. Chuyr~ng VOl0 <p <1,xacxua'tkh6ngchinhxac la: p2A(cl-l)-2/(l-p).l Binh ly 4 dinhd~nggia trtcuad danl baar~ngdIonnha'tlaY2. . Bjllh if 4: Cho O<p<l.R6i p2A(cl+l)- 2/(I-p) <Y2n€u va chi ne'u d> log(2+((I+log(I/l-p)))/log(l/p)))- l. B~c bi~t, ne'uE =(l-p), chQn: d >[log(l/e) - loglog(l/e)]. CIUl'llg 111illh: Diemthunha'trongdinhly d~dangduQckiemtra. BieHl thuhai ta!tiuyr~ngp2(d+l)-2/(I-p)duQctangtrongp va' gianl trong d. Qua vi~c Hnhloan,d =1duchota'tca p<0.5vad=2duchota'tcap<0.72., Gia SU0.72<p <1,d~tE =(l-p) vagiaSU D >[log(l/e)+loglog(l/e)]. Chuy r~ng , . p2A(cl+l)-2=(l-e )2(cl+l)-2<e-e(2A(d+l)-2), Thoa lllan He'll: Ee(2A(cl+l)-2~2/e. DieunayttiejngdtiongVOl d>log((lie) In(2/e)+2))-1. Nhtiv~y,ne'uchungtacothSchira: Log((l/e)log(l/e))>log((l/e)In(2/e)+2)-l. Thl chungminhsedtiQchoanthi~n.B~ngvi~cDangs6mil eahatve'vas~pxe'pl~i,taseco: (2/e)log(1/e)>(1/e)ln(2/e)-2. Bi€u nayttiejngdtiongVOl: (2/(ln2)-1)In(l/e)>In2-2e. VOlgiatfi t6nt~icuae,vi troitangddnva vtphdi gianTdan,VIv~ytachic~nkiSmtraVOlgiatri e=0~28,thl Trang61 ve tnti la 1/20vave ph£i.ila 1/26.Ta cothesuyradi€u ph£1ichungll1inh. A. ThuattoanhocmonotoneDNF: Bay gia chungta semieut£1va phantichthu~t loan hqc.Thu~tloanb~tdftub~nggi£1thietr6ng(falseireDtit Celcacvector)va thvchi~ntiltcacacCalihai tu'ongdu'ong vaxuly caevi d\lngu'\5cn10tlftnrhodenkhigiatl1ietu'eIng dt(c5ngtoichucDangdich.BeJiVInocO'"doan"vaithu~tngu trongnOidungdich,thu~t loanco th~gioi thi~ucaethu~t ngukh6ngth~gioi thi~ucacthu~t I1gfi'kh6ngth~hi~nnOi dungdich.Nhu'mOtvi d\l ngu'Qcv co th~la mOtvi d1}am cuah,trongtru'anghQph(v)- 0vah(v)=1.Thu~tloanxu ly saorhov xoatiltcacac thu~tngfi'tn giathiethi~nthai illa c1u\5cthaamanbeJivectorVo. M~t khac,vi d1}nguQcy Hi ll10tvi d1}du'eIngcuah. MOt cachtnjc giac,di€u ma chungta n1u6nlam la gqi reduceireDv d~chuamOtvectory saorho caexacsuitt <I/2co mOtvi d1}clueIngnhanhiltcuah trongdamcacn6i doidrholl10tvaigiatrivilaphaicuad.R6i taphaib6sung tit ca cacn6i d5i dcua y nhucacthu~tngutoi gia thiet ' ' hi~nthaih va tier tl;1c.Ne'udi€u naydu'Qcthlfchi~nrho rHaivi d1}duong,chungta rho d~b6 sungmOtthu~tngu moicuahtoih rhom6ihaivi d\lnguQclueIngvoi di€u ki~n phaixuIy dftyduo Vi d\lxetnQidungdichh=Xl+X2tren3bien,nhuchIra tronghlnh3 va giadinhr~ngvi d\lnguQckheJidfiula 110. Khi duQcgqi(110,1)la cacdO'isO'cuano.Reduce!hvchi~n Trang62 cacdiu hoi thanhphftnchochildren010va 100.Giasudiu hiSidftulien duQctraloi "I don'tknow"va diu thlihai la "Yes" thlvi~cxu ly duQcnh~cl~iVOl100,vachildren000 duQchc)i.Gia sutraloi trongtruonghQpnayla "No". Gia thi~t~pXlvamOtdiu hoitudngtvduQcthvchi~n.Baygio giasuvi d~nguQcla 01L Thl ReduceduQcgQiVOld6isO' (011.1)va thvchi~ncacCallhoi thanhph~nchochildren 001va010.M~cdftu010la n6idoivala vi dlJdudngthuQc h,nodtlduQchoiVOlk€t quatra10i"I don'tknow". Ta coth~kh~ngdinhdingxacsufit'mQiCallhoi thanh vien010trc1loi"I don'tknow"la P. 111 101 011110 100 001 000 Hlnh3:Dfiu+,- va? ky hi~utudnglingchIradudng, anlva "I don'tknow"traloi cacCallhoi thanhphftn.Vi dlJ nguQcdudngdftulienla 110,vector010phil duQcdolhoi. N~uvi dlJ nguQcthlihaila 011,vectorenophil duQc hc)il~i. Ta gia di~hr~ngReduceduQcma ta tra l(;1ihai k€t qua:Vectory tn1ke'tquatrliocva t~pQ euatfitca cae vectorduQchoibdiTIlliedhih,tfttcad~quygQiReduceVOl Trang64 11. Endwhile : 12.Outputhandhalt 13.End. UNG D{)NG: Dng dlJngthu~toanhQcDNF nay nglioi ta co th€ t~o cac d~cHnh thong minh cua model nhli: Autoanswers, Autocall,Call back,Robot(Nglioi Inay)...