# Chuong 1. tong quan

• Published on
08-Jul-2015

• View
403

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...