Chuong 1. tong quan

  • Published on
    08-Jul-2015

  • View
    403

  • Download
    1

Embed Size (px)

Transcript

  • 1Chng 1: Tng quan1.1. Cc bc c bn khi gii mt bi ton tin hc1.2. Vai tr ca cu trc d liu v gii thut1.3. Cc cu trc d liu c bn1.4. nh gi phc tp gii thut1.5. Bi tp

  • 21.1. Cc bc c bn khi gii mt bi ton tin hc

  • 3Cc bc c bn Khi tin hnh gii cc bi ton tin hc cn tin

    hnh cc bc c bn sau: 1. Xc nh bi ton2. Tm cu trc d liu3. Tm gii thut4. Lp trnh5. Kim th6. Ti u chng trnh

  • 4B1: Xc nh bi ton Vic xc nh bi ton tc l phi xc nh xem:1. Phi gii quyt vn g?2. Vi gi thit no cho?3. Li gii cn phi t nhng yu cu g? i khi nhng bi ton tin hc ng dng trong thc t

    ch cn tm li gii tt ti mc no , thm ch l ti mc chp nhn c. Bi v li gii tt nht c th i hi qu nhiu thi gian v chi ph. V d: Gii phng trnh f(x) = 0 vi x l bin s, f(x) l

    1 a thc ca x c bc 3.

  • 5B1: Xc nh bi ton Bi ton 1: Chia nhm tho lun

    Mt lp hc c N sinh vin cng tham gia tho lun v mt vn , h mun chia thnh cc nhm v mi nhm tho lun ring v mt phn ca vn . Nhm c bao nhiu sinh vin th c a ra by nhiu kin. Nu ly mi nhm mt kin em ghp li th c mt b kin gii quyt vn . Hy tm cch chia sinh vin thnh cc nhm s b kin S thu c lln nht.V d: vi N = 7, kt qu l chia thnh 2 nhm (3, 4)

    Pht biu li bi ton:Cho mt s nguyn dng N, tm cch phn tch N thnh tng cc s nguyn dng sao cho tch S ca cc s l ln nht.

  • 6B2: Tm cu trc d liu biu din tnh trng c th ca bi ton, tu thuc

    vo bi ton cn gii quyt v nhng thao tc s tin hnh trn d liu vo. Xy dng CTDL khng th tch ri vic tm kim GT.

    Cc tiu chun khi la chn cu trc d liu: Biu din c y cc thng tin nhp, xut. Ph hp vi cc thao tc ca GT c la chn. Ci t c trn my tnh vi NNLT ang s dng.

    Trc khi t chc d liu, c th phi vit mt on chng trnh nh kho st xem d liu cn lu trln ti mc no.

  • 7B2: Tm cu trc d liu Bi ton 2: Tnh S l tng bnh phng ca cc s t

    nhin khng ln hn N, N l s t nhin 100.S = 12 + 22 + ... + N2

    Tm cu trc d liu: (NNLT s dng l C++) N c kiu s nguyn 1 byte, khng du (unsigned char). chn chnh xc CTDL ca S, chy th on chng

    trnh:unsigned long S = 0;// unsigned int S = 0;for(unsigned char i = 1; i

  • 8B3: Tm gii thut Khi nim: Gii thut l mt h thng cht ch v r

    rng cc quy tc nhm xc nh mt dy thao tc trn cu trc d liu sao cho: Vi mt b d liu vo, sau mt s hu hn bc thc hin cc thao tc ch ra, ta t c mc tiu nh.

    Cc c trng ca gii thut: 1. Tnh n ngha: 1 d liu vo cho 1 kt qu ra duy nht2. Tnh dng: cho kt qu sau mt s hu hn bc. 3. Tnh ng: phi c kt qu mong mun vi mi b

    d liu u vo 4. Tnh ph dng: lm vic trn cc d liu khc nhau.5. Tnh kh thi: Kch thc b nh phi nh, thc hin

    trong thi gian cho php, d hiu v d ci t.

  • 9B3: Tm gii thut Bi ton 3: Tm c s chung ln nht ca 2 s a, b

    khng ng thi bng 0. Tm gii thut:

    Input: 2 s nguyn t nhin a v b khng ng thi bng 0

    Output: USCLN(a, b) Gii thut Euclide:B1 (Input): Nhp 2 s t nhin a v bB2: Nu b 0 th chuyn sang B3, ngc li chuyn sang

    B4.B3: t r = a % b; a = b; b = r; Quay tr li B2.B4 (Output): Kt lun c s chung ln nht phi tm l gi

    tr ca a. Kt thc gii thut.

  • 10

    B4: Lp trnh K thut lp trnh tt th hin k nng vit chng

    trnh, kh nng g ri v thao tc nhanh. Nn tin hnh lp trnh theo phng php tinh ch tng

    bc (Stepwise refinement): Ban u, gii thut c th hin bng ngn ng t

    nhin vi cc bc tng th, mi bc nu ln 1 cng vic phi thc hin.

    1 cng vic n gin hoc 1 on chng trnh hc thuc th tin hnh vit m lnh ngay bng NNLT.

    1 cng vic phc tp th chia ra thnh nhng cng vic nh hn v li tip tc vi nhng cng vic nh hn .

    Trnh vic m mm, xo i vit li nhiu ln, bin chng trnh thnh t giy nhp.

  • 11

    B4: Lp trnh Bi ton 4: Tm c s chung ln nht ca 2 s t

    nhin a, b. M t bng ngn ng t nhin nh B3: Tm gii thut on chng trnh:

    int a, b, r;printf(Nhap 2 so a va b: ); //B1scanf(%d%d, &a, &b);while (b != 0) //B2{

    r = a % b; a = b; b = r; //B3} printf(USCLN = %d, a); //B4

  • 12

    B5: Kim th Gm 2 nhim v chnh l: 1. Chy th v tm li2. Xy dng cc b test Chy th v tm li:

    K nng tm li, sa li, iu chnh li chng trnh l 1 k nng quan trng ca ngi lp trnh.

    C ba loi li:1. Li c php: hay gp, d sa, ch cn nm vng NNLT.2. Li ci t: th hin khng ng gii thut nh, phi

    kt hp vi chc nng g ri sa li cho ng.3. Li gii thut: t gp, nguy him nht, c th phi iu

    chnh li gii thut, thm ch phi tm gii thut khc.

  • 13

    B5: Kim th Xy dng cc b test: kim tra tnh ng n ca

    chng trnh. t trong cc file vn bn: to nhanh, mi ln chy th

    ch cn thay tn file, khng nhp li b test t bn phm. Kinh nghim lm cc b test l:1. Mt b test nh, n gin, lm bng tay cng c c

    p s so snh vi kt qu chng trnh chy ra.2. Cc b test nh cha cc gi tr c bit hoc tm

    thng. y l nhng test d sai nht.V d: a = 0, b = 0 USCLN = 0 {l test cho kt qu sai}3. Cc b test phi a dng, trnh s lp i lp li.4. Mt vi test ln kim tra tnh chu ng ca chng

    trnh.

  • 14

    B5: Kim th Ch :

    Chng trnh chy qua c ht cc test khng cngha l chng trnh ng. Bi c th cha xy dng c b test lm cho chng trnh chy sai.

    Nn tm cch chng minh tnh ng n ca gii thut v chng trnh. Tuy nhin, iu ny thng rt kh.

  • 15

    B6: Ti u chng trnh Trc khi kim th nn t mc tiu vit chng trnh

    sao cho n gin v chy ra kt qu ng l c! Sau khi chy ng, phi sa i chng trnh

    chy nhanh hn, hiu qu hn. Khi ti u chng trnh, xem li nhng ch no vit

    cha tt th ti u li m lnh chng trnh ngn hn, chy nhanh hn.

    Khng nn vit ti u ti u m n , bi chng trnh c m lnh ti u thng phc tp, kh kim sot.

  • 16

    B6: Ti u chng trnh Vic ti u chng trnh da trn cc tiu chun sau:1. Tnh tin cy: chy ng nh d nh, m t ng mt

    gii thut ng, cn kim tra tnh ng n ca cc bc mi khi c th.

    2. Tnh uyn chuyn: d sa i, gim bt cng sc khi pht trin chng trnh.

    3. Tnh trong sng: d c, d hiu, ph thuc rt nhiu vo cng c lp trnh v phong cch lp trnh.

    4. Tnh hu hiu: chy nhanh v t tn b nh, cn phi cgii thut tt v nhng tiu xo khi lp trnh. Tiu chun ny nn dng li mc chp nhn c.

  • 17

    B6: Ti u chng trnh Bi ton 5: Kim tra tnh nguyn t ca s t nhin N.

    long kt = 1; //Gia su n la so nguyen tolong k = n - 1;for(long j = 2; j

  • 18

    B6: Ti u chng trnh Ci thin thi gian chy ca chng trnh kim tra tnh

    nguyn t: s ln lp gim khong 1 na.long k = n / 2;

    Mt ci tin tip theo: s ln lp gim khong cn bc 2 ca N.long k = (long) sqrt(n);

    Ci tin sau gip chng trnh c th x l vi s tnhin N ln v thi gian x l nhanh hn.

  • 19

    Kt lun Mt chng trnh i hi rt nhiu cng on, ch 1

    cng on khng hp l s lm tng chi ph vit chng trnh.

    Bi hc kinh nghim: ng bao gi vit chng trnh khi cha suy xt k v gii thut v nhng d liu cn thao tc.

    Ch cn mc 1 trong 2 li (sai v GT hoc GT khng th trin khai c trn 1 CTDL khng ph hp) th nguy c sp ton b chng trnh l hon ton cth, cng c cha cng b ri v hu nh chc chn lphi lm li t u.

  • 20

    1.2. Vai tr ca CTDL v GT

    1.2.1. Mi quan h gia CTDL v GT1.2.2. Cc tiu chun nh gi CTDL1.2.3. Cc tiu chun nh gi GT

  • 21

    1.2.1. Mi quan h gia CTDL v GT Trong cc bc c bn khi gii quyt 1 bi ton tin hc:

    B1: Xc nh bi ton: c hiu bi ton thc t B2: Tm cu trc d liu: biu din cc i tng d liu

    ca bi ton bng cc cu trc thch hp (kiu d liu ca NNLT).

    B3: Tm gii thut: tm ra hng gii quyt bi ton, lcc GT xc nh trnh t cc thao tc my tnh phi thi hnh cho ra kt qu mong mun.

    Ni dung chnh ca mn hc l B2 v B3. B4: Lp trnh, B5: Kim th, B6: Ti u chng

    trnh:dnh cho cc lp trnh vin sau khi hon thnh phn m t bi ton thc t v tm ra hng gii quyt.

    Phn bi tp ng dng v bi tp ln ca mn hc.

  • 22

    Mi quan h gia CTDL v GT Sai lm thng gp: ch ch trng n GT m qun mt

    tm quan trng ca vic t chc CTDL ca bi ton. xc nh c GT ph hp cn phi bit n tc

    ng n loi CTDL no. V d: Cho 1 dy kho tng dn. Nu t chc d liu

    bng danh sch lin kt th phi dng GT tm kim tun t. Nhng nu t chc d liu bng mng 1 chiu th cth dng GT tm kim nh phn c tc nhanh hn.

    Khi chn la CTDL cng cn phi hiu r nhng thao tc (GT) no s tc ng n n. V d: Vi bi ton trn, nu tm kim c thc hin

    nhiu ln th nn t chc d liu kiu mng 1 chiu.

  • 23

    Mi quan h gia CTDL v GT Vi CTDL chn, s c nhng GT tng ng, ph

    hp. Khi CTDL thay i, GT cng phi thay i theo trnh vic x l khng ph hp.

    CTDL tt s gip GT x l trn c th pht huy tc dng tt hn, va p ng nhanh va tit kim ti nguyn, GT cng d hiu v n gin hn.

    Trong 1 bi ton tin hc, CTDL v GT c mi quan hcht ch vi nhau, c th hin qua cng thc: :

    CU TRC D LIU + GII THUT = CHNG TRNH

  • 24

    1.2.2. Cc tiu chun nh gi CTDL Trong B2: Tm cu trc d liu nu ra 1 s tiu

    chun khi la chn CTDL. Tuy nhin, 1 bi ton c thc nhiu CTDL m t c n, vn c t ra llm sao chn c 1 CTDL tt.

    Nu la chn CTDL theo 1 cch u tin no th phi l tt nht.

    CTDL tt l 1 CTDL tho mn cc tiu chun sau:1. CTDL ng n: m t ng cc i tng d liu.2. CTDL n gin: d tin hnh cc thao tc x l.3. CTDL tit kim ti nguyn: s dng t b nh.

  • 25

    1.2.3. Cc tiu chun nh gi GT Trong B3: Tm gii thut nu ra 1 s tiu chun khi

    la chn GT x l bi ton. Khi gii 1 bi ton tin hc c th c 1 s GT khc nhau, vn l cn phi nh gi cc GT la chn 1 GT tt.

    Nu la chn GT theo 1 cch u tin no th phi ltt nht.

    GT tt l 1 GT tho mn cc tiu chun sau:1. GT ng n: cho kt qu ng vi mi b d liu vo.2. GT n gin: d ci t, ci t nhanh.3. GT thc hin nhanh: thi gian thc hin ngn.

  • 26

    1.3. Cc CTDL c bn

    1.3.1. Khi nim kiu d liu1.3.2. Cc kiu d liu c bn1.3.3. Cc kiu d liu c cu trc

  • 27

    1.3.1. Khi nim kiu d liu Khi nim: Kiu d liu T c xc nh bi mt b

    , trong :1. V: Tp cc gi tr hp l m i tng T c th lu tr.2. O: Tp cc thao tc c th thi hnh trn i tng T.V d: Kiu d liu s nguyn int trong NNLT C c xc

    nh bi b vi:V = {-32768..32767} v O = {+, -, *, /, %, }

    Cc thuc tnh ca 1 kiu d liu:1. Tn //int2. Min gi tr // [-32768, 32767]3. Kch thc lu tr //2 byte4. Tp cc ton t //+, -, *, /, %,

  • 28

    1.3.2. Cc kiu d liu c bn L cc loi d liu n gin, khng c cu trc, biu

    din cc gi tr v hng nh: s nguyn, s thc, k t, logic,...

    Thng c cc NNLT cp cao xy dng sn nh 1 thnh phn ca NNLT gim nh cng vic cho ngi lp trnh. Cn gi l cc kiu d liu nh sn.

    Cc kiu d liu c bn bao gm: Cc kiu c th t ri rc (hay cn gi l v hng m

    c): s nguyn, k t, logic, lit k, on con, Cc kiu c th t khng ri rc: s du phy ng,

    Cc kiu d liu c bn ca cc NNLT c th khc nhau i cht.

  • 29

    1.3.3. Cc kiu d liu c cu trc Kiu d liu c cu trc l cc kiu d liu c xy

    dng da trn vic t chc, lin kt cc thnh phn dliu c kiu d liu c nh ngha.

    Cc NNLT u ci t sn 1 s kiu d liu c cu trc c bn nh: tp hp, mng, xu k t, bn ghi, tp tin... v cho php lp trnh vin t nh ngha KDL mi.

    Trong mn hc ny s nghin cu v 1 s CTDL phc tp hn: danh sch tuyn tnh (ngn xp, hng i), danh sch lin kt (n, vng, kp), cy (nh phn, tng qut), th,

  • 30

    1.4. nh gi phc tp GT

    1.4.1. Phng php nh gi1.4.2. Phn tch nh gi 1 GT n gin

  • 31

    1.4.1. Phng php nh gi Thc nghim: l phng php n gin nht nh

    gi hiu qu ca mt gii thut (GT). Cch nh gi:

    Lp trnh, kim th.

    Thng k thi gian thc hin ca GT (theo thi gian thc).

    Nhc im: GT chu s hn ch ca NNLT dng ci t.

    Hiu qu ca GT b nh hng bi trnh ca lp trnh vin.

    Vic chn c cc b d liu th c trng cho tt c tp cc d liu vo ca GT rt kh khn v tn nhiu chi ph.

    Cc thng s kim th ph thuc nhiu vo phn cng.

    Kt lun: kh c kh nng p dng trn thc t!

  • 32

    Phng php xp x tim cn nh gi gii thut theo hng xp x tim cn: l

    phng php mang tnh hnh thc, khng ph thuc vo mi trng v phn cng. S dng 1 s khi nim ton hc O, , . Kch thc d liu vo (N): l lng d liu cn c

    x l ca bi ton. Bi ton s nguyn t: N l ln ca s nguyn cn kim tra.

    Bi ton sp xp dy s: N l s lng phn t ca dy s.

    Hm thi gian (T(N)): xc nh bi s lnh m chng trnh cn thc hin. T(N) khng ph thuc vo phn cng!

  • 33

    Phng php xp x tim cn Mc ch ca phng php: nh gi, so snh cc

    GT trong trng hp d liu vo N kh ln v theo cch c lp vi phn cng, NNLT, chng trnh dch,

    V d: So snh 2 gii thut P1 v P2 vi hm thi gian thc hin tng ng l T1(N) = 100N2 v T2(N) = N3. Trng hp N < 100: thi gian thc hin ca P1 v P2 t, s khc

    bit gia T1 v T2 l khng ng k (T1 T2 0)

    Khng nh gi.

    Trng hp N > 100: nh gi.

    Kt lun: P1 hiu qu P2.

  • 34

    Cc trng hp ca GT Mt s trng hp nh gi GT:

    Tt nht: hm thi gian T(N) c gi tr nh nht. Trung bnh: hm thi gian T(N) c gi tr trung bnh.

    c quan tm nhiu nht, i din cho a s trng hp sdng gii thut.

    Vic xc nh T(N) trong trng hp trung bnh thng gp nhiu kh khn v phn tch ton hc.

    Xu nht: hm thi gian T(N) c gi tr ln nht. c quan tm trong cc bi ton c lin quan n ri ro, y

    hc, ... Hoc khi gp kh khn trong nh gi GT trng hp trung

    bnh.

  • 35

    Cc trng hp ca GT V d: Xt gii thut ca bi ton s nguyn t:kt = 1; //Gi s N l s nguyn tfor (i = 2; i < N; i++)

    if (N % i == 0){

    kt = 0; //N khng l s nguyn tbreak; //Thot khi for.

    } Tt nht: N l 1 s chn (vng for thc hin 1 ln). Xu nht: N l 1 s nguyn t (vng for thc hin N-2 ln). Trung bnh: N l 1 s nguyn dng bt k. Rt kh xc nh

    T(N) trng hp trung bnh!

  • 36

    Cc k php nh gi phc tp t vn : nh gi phc tp ca 1 GT, cn

    c lng hm thi gian T(n) ca GT vi 1 hm g(n). g(n): l 1 hm xc nh, g(n) > 0 vi mi n. Cn c vo ln ca g(n) xc nh GT l hiu qu

    (nu g(n) nh) hoc khng hiu qu (nu g(n) ln). K php: phc tp ca GT (cn gi l phc tp

    tnh ton ca GT) c xc nh trong cc trng hp (tt nht, trung bnh, xu nht) vi cc k php: K php ln (big-theta). K php ln (big-omega). K php O ln (big-oh): c s dng trong mn hc!

  • 37

    K php nh gi phc tp Khi nim: T(n) = (g(n))

    nu tn ti cc hng s dng c1, c2 v n0 sao cho:c1.g(n) T(n) c2.g(n)

    vi mi n n0K hiu ny gi l k php

    ln (big-theta notation) Hm g(n) c gi l gii

    hn cht (asymptotic tight bound) ca hm T(n).

  • 38

    K php nh gi phc tp Khi nim: T(n) = (g(n))

    nu tn ti cc hng s dng c v n0 sao cho:

    c.g(n) T(n) vi mi n n0K hiu ny gi l k php ln (big-omega notation)

    Hm g(n) c gi l gii hn di (asymptotic lower bound) ca hm T(n).

  • 39

    K php nh gi phc tp O Khi nim: T(n) = O(g(n))

    nu tn ti cc hng s dng c v n0 sao cho:

    c.g(n) T(n) vi mi n n0K hiu ny gi l k php

    O ln (big-oh notation) Hm g(n) c gi l gii

    hn trn (asymptotic upper bound) ca hm T(n).

    Lun tm c g(n) v cn tm g(n) nh nht c th!!!

  • 40

    K php nh gi phc tp O V d:

    GT vi T(n)= (n+1)2 s c phc tp l O(n2) v c thchn c cc gi tr c = 4, n0 = 1

    4.n2 (n+1)2 vi mi n 1Cng c th kt lun T(n) = O(n3), nhng g(n) = O(n2)

    l hm nh nht ta tm c! Tng qut 1: GT vi T(n)= a2.n2 + a1.n + a0 (vi a0,

    a1, a2 l cc hng s) c phc tp l O(n2).Gii thch???

    Tng qut 2: GT vi T(n)= ak.nk + ak-1.nk-1 ++ a0(vi a0,,ak l cc hng s) c phc tp l O(nk).

  • 41

    K php nh gi phc tp O Kt lun:

    Khi nh gi phc tp GT bng k php OCh quan tm n lu tha cao nht ca n!B qua cc hng s!

  • 42

    phc tp ca gii thut Khi nim: phc tp ca gii thut l hm chn

    trn ca hm thi gian T(N). GT c hm thi gian T(N) v phc tp gii thut l

    g(N) nu T(N) = O(g(N)). S phn lp gii thut: cn c vo hm g(n)

    ngha: Cho php so snh hiu qu ca cc GT mt cch nhanh chng theo nguyn tc GT no c phc tp phn lp thp hn th hiu qu hn.

    Mt s phn lp thng gp: 1, lgn, n, nlgn, n2, n3, 2n, n!, nn, Hm logarit (lgn): thng gp nht l log2n, phn bit vi k

    hiu ton hc ca log10n.

  • 43

    S phn lp gii thut Hm 1 gi l hm hng s, l trng hp l tng v

    GT ca cc bi ton tin hc: Vi kch thc d liu vo N bt k, GT lun dng sau 1 vi cu lnh.Bi ton n gin, trng hp c bit,

    Cc hm lgN, N, N2, N3, gi l cc hm loi a thc. Cc GT thuc phn lp hm a thc c thi gian thc hin kh nhanh v thng c s dng.

    Cc hm 2N, N!, NN, c gi l hm loi m. Cc GT thuc phn lp hm loi m c thi gian thc hin rt chm v thng phi thay th bng cc GT gn ng thuc phn lp hm loi a thc!

  • 44

    S phn lp gii thut

    2,63*10354.294.967.296 1.024160325

    lgN N NlgN N2 2N N!0 1 0 1 2 1

    1 2 2 4 4 2

    2 4 8 16 16 24

    3 8 24 64 256 40.320

    4 16 64 256 65.536 2.004.189.184

  • 45

    S phn lp gii thut Phn tch:

    GT c phc tp thuc phn lp N!, vi kch thc dliu vo N = 32, s cn khong T(N) = 2,63*1035 lnh.

    Gi s my tnh chy chng trnh c ci t bng GT trn c tc x l khong 2,63 t php tnh/giy (2,63 GHz trong iu kin l tng) th thi gian thc hin l:

    T(N) = 1026 giy 3.170.979.198.376.458.650 nm 1 nm = 365 * 24 * 60 * 60 = 31.536.000 giy

    T...