Tổng quan về cầu trúc dữ liệu

ch­¬ng 1

tæng quan vÒ cÊu tróc d÷ liÖu vµ gi¶i thuËt

1.1.Vai trß cña cÊu tróc d÷ liÖu trong mét ®Ò ¸n tin häc

• Thùc hiÖn mét ®Ò ¸n tin häc lµ chuyÓ bµi to¸n thùc tÕ thµnh bµi to¸n cã thÓ gi¶i quyÕt trªn m¸y tÝnh. Mét bµi to¸n thùc tÕ bÊt kú ®Òubao gåm c¸c ®èi t­îng d÷ liÖu vµ c¸c yªu cÇu xö lý trªn c¸c ®èi t­îng ®ã. V× thÕ, ®Ó x©y dùng métm« hi×nh tin häc ph¶n ¸nh ®­îc bµi to¸n thùc tÕ cÇn chó träng ®Õn hai vÊn ®Ò:

Tæ chøc biÓu diÔn c¸c ®èi t­îng thùc tÕ

C¸c thµnh phÇn d÷ liÖu thùc tÕ ®a d¹ng, phong phó vµ th­êng chøa ®ùng nh÷ng quan hÖ nµo ®ã víi nhau, do ®ã trong m« h×nh tin häc cña bµi to¸n, cÇn ph¶i tæ chøc, x©y dùng c¸c cÊu tróc d÷ liÖu thÝch hîp nhÊt sao cho võa cã thÓ ph¶n ¸nh chÝnh x¸c c¸c d÷ liÖu thùc tÕ nµy, võa cã thÓ dÔ dµng dïng m¸y tÝnh ®Ó xö lý. C«ng viÖc nµy gäi lµ x©y dùng cÊu tróc d÷ liÖu cho bµi to¸n.

X©y dùng c¸c thao t¸c xö lý d÷ liÖu

Tõ nh÷ng yªu cÇu xö lý trong thùc tÕ, cÇn t×m ra c¸c gi¶i thuËt t­¬ng øng ®Ó x¸c ®Þnh tr×nh tù c¸c thao t¸c m¸y tÝnh ph¶i thi hµnh ®Ó cho ra kÕt qu¶ mong muèn, ®©y lµ b­íc x©y dùng gi¶i thuËt cho bµi to¸n.

• Tuy nhiªnkhi gi¶i quyÕt mét bµi to¸n trªn m¸y tÝnh, chóng ta th­êng cã khuynh h­íng chØ chó träng ®Õn viÖc x©y dùng gi¶i thuËt mµ quyªn ®i tÇm quan träng cña viÖc tæ chøc d÷ liÖu trong bµi to¸n. Gi¶i thuËt ph¶n ¸nh c¸c phÐp xö lý, cßn ®èi t­îng xö lý cña gi¶i thuËt l¹i lµ d÷ liÖu. ChÝnh d÷ liÖu chøa ®ùng c¸c th«ng tin cÇn thiÕt ®Ó thùc hiÖn gi¶i thuËt. §Ó x¸c ®Þnh ®­îc gi¶i thuËt phï hîp cÇn ta cÇn ph¶i biÕt nã t¸c ®éng ®Õn lo¹i d÷ liÖu nµo vµ khi lùa chän cÊu tróc d÷ liÖu còng cÇn ph¶i hiÓu râ nh÷ng thao t¸c nµo t¸c ®éng lªn d÷ liÖu ®ã. Nh­ vËy trong mét ®Ò ¸n tin häc, cÊu tróc d÷ liÖu vµ gi¶i thuËt cã mèi quan hÖ chÆt chÏ víi nhau, ®­îc thÓ hiÖn qua c«ng thøc
• Víi mét cÊu tróc d÷ liÖu ®· chän, sÏ cã nh÷ng gi¶i thuËt t­¬ng øng, phï hîp. Khi cÊu tróc d÷ liÖu thay ®æi th­êng gi¶i thuËt còng ph¶i thay ®æi theo ®Ó tr¸nh viÖc xö lý g­îng Ðp, thiÕu tù nhiªn trªn mét cÊu tróc kh«ng phï hîp. H¬n n÷a, mét cÊu tróc d÷ liÖu tèt sÏ gióp gi¶i thuËt xö lý trªn ®ã cã thÓ ph¸t huy t¸c dông tèt h¬n, võa nhanh võa tiÕt kiªm vËt t­, gi¶i thuËt còng ®¬n gi¶n vµ dÔ hiÓu h¬n.

CÊu tróc d÷ liÖu + Gi¶i thuËt = Ch­¬ng tr×nh

VÝ dô 1: Mét ch­¬ng tr×nh qu¶n lý ®iÓm  thi cña sinhviªn cÇn l­u c¸c ®iÓm sè cña 3 sinh viªn. Do mçi sinh viªn cã 4 ®iÓm sè t­¬ng øng víi 4 m«n häc kh¸c nhaunªn d÷ liÖu cã d¹ng nh­ sau:

Sinh viªn	M«n 1	M«n 2	M«n 3	M«n 4
SV1	7	9	7	5
SV2	5	4	2	7
SV3	8	9	6	7

ChØ xÐt thao t¸c x­ lý lµ xuÊt ®iÓm sè c¸c m«n cña tõng sinhviªn.

Gi¶ sö cã c¸c ph­¬ng ¸n tæ chøc l­u tr÷ nh­ sau:

Ph­¬ng ¸n 1: Sö dông m¶ng mét chiÒu

cã tÊt c¶  3(SV) * 4(M«n) = 12 ®iÓm sè cÇn l­u tr÷, do ®ã ta khai b¸o m¶ng nh­ sau:

Type mang = array[1..12] of integer;

var  a: mang

Khi ®ã m¶ng a c¸c phÇn tö sÏ ®­îc l­u tr÷ nh­ sau:

7

9

7

5

5

4

2

7

8

9

6

7

         

SV1

SV2

SV3

Vµ truy xuÊt ®iÓm sè m«n j cña sinh viªn i lµ phÇn tö t¹i dßng i cét j trong b¶ng. §Ó truy xuÊt ®Õn phÇn tö nµy ta ph¶i sö dông c«ng thøc x¸c ®Þnh chØ sè t­¬ng øng trong m¶ng a:

                   B¶ng ®iÓm (dßng i, cét j) Þ a[ (i -1)*sè cét + j ]

Ng­îc l¹i, víi mét phÇn tö bÊt kú trong m¶ng, muèn biÕt ®ã lµ ®iÓm sè cña sinh viªn nµo, m«n g×, ph¶i dïng c«ng thøc x¸c ®Þnh sau:

a[i] Þ b¶ng ®iÓm (dßng(i  div cét) + 1), cét (i mod sè cét))

Víi ph­¬ng ¸n nµy, thao t¸c xö lý ®­îc cµi ®Æt nh­ sau

procedure xuat( a: mang);

var i, mon, so_mon : integer    

begin

         so_mon = 4;

for  i := 1 to 12 do

begin

sv = i div so_mon;

mon = i mod so_mon;

writeln('§iÓm m«n: ', mon, 'cña sinh viªn ', sv, ' lµ: ', a[i]);

end;

end;

Ph­¬ng ¸n 2: sö dông m¶ng hai chiÒu

Khai b¸o m¶ng hai chiÒu a cã kÝch th­íc 3 dßng * 4 cét nh­ sau

type mang = array[1..3,1...4] of integer;

var a : mang;

	Cét 1	Cét 2	Cét3	Cét 4
Dßng 1	a[1,1] = 7	a[1,2] = 9	a[1,3] = 7	a[1,4] = 5
Dßng 2	a[2,1] = 5	a[2,2] = 4	a[2,3] = 2	a[2,4] = 7
Dßng 3	a[3,1] = 8	a[3,2] = 9	a[3,3] = 6	a[3,4] = 7

Vµ truy xuÊt ®iÓm sè m«n j cña sinh viªn i lµ phÇn tö t¹i dßng i cét j trong b¶ng- còng chÝnh lµ phÇn tö ë dßng i cét j trong m¶ng.

B¶ng®iÓm (dßng i, cét j) Þ  a[i,j]

Víi ph­¬ng ¸n nµy, thao t¸c xö lý ®­îc cµi ®Æt nh­ sau:

procedure xuat( a: mang);

var i, j, so_sv, so_mon : integer    

begin

         so_mon = 4; so_sv = 3;

for  i := 1 to  so_sv do

begin

for j := 1 to so_mon do

     writeln('§iÓm m«n: ', i, 'cña sinh viªn ', j, ' lµ: ', a[i,j]);

end;

end;

nhËn xÐt

Cã thÓ thÊy râ ph­¬ng ¸n 2 cung cÊp mét cÊu tróc l­u tr÷ phï hîp víi d÷ liÖu thùc tÕ h¬n ph­¬ng ¸n 1, vµ do vËy gi¶i thuËt xö lý trªn cÊu tróc d÷ liÖu cña ph­¬ng ¸n 2 còng ®¬n gi¶n h¬n, tù nhiªn h¬n.

1.2.c¸c tiªu chuÈn ®¸nh gi¸ cÊu tróc d÷ liÖu

Do tÇm quan träng cña cÊu tróc d÷ liÖu ®· ®­îc tr×nh bµy trong phÇn trªn, nªn nhÊt thiÕt ph¶i chó träng ®Õn viÖc lùa chän mét ph­¬ng ¸n tæ chøc d÷ liÖu thÝch hîp cho ®Ò ¸n. Mét cÊu tróc d÷ liÖu tèt ph¶i tho¶ m·n c¸c tiªu chuÈn sau:

Ph¶n ¸nh ®óng thùc tÕ: §©y lµ tiªu chuÈn quan träng nhÊt, quyÕt ®Þnh tÝnh ®óng ®¾n cña toµn bé bµi to¸n. CÇn xem  xÐt kü l­ìng còng nh­ dù trï c¸c tr¹ng th¸i biÕn ®æi cña d÷ liÖu trong chu tr×nh sèng ®Ó cã thÓ lùa chän cÊu tróc d÷ liÖu l­u tr÷ thÓ hiÖn chÝnh x¸c ®èi t­îng thùc tÕ.

VÝ dô: Mét sè t×nh huèng chän cÊu tróc l­u tr÷ sai

- Chän biÕn sè nguyªn integer ®Ó l­u tr÷ tiÒn th­ëng b¸n hµng (®­îc tÝnh theo c«ng thøc tiÒn th­ëng b¸n hµng = trÞ gi¸ hµng *5%), do vËy khi lµm trßn mäi gi¸ trÞ tiÒn th­ëng sÏ g©y thiÖt h¹i cho nh©n viªn b¸n hµng. Tr­êng hîp nµy ph¶i sö dông biÕn sè thùc ®Ó ph¶n ¸nh ®óng kÕt qu¶ cña c«ng thøc tÝnh thùc tÕ.

- Trong tr­êng trung häc, mçi líp cã thÓ nhËn tèi ®a 25 häc sinh. Líp hiÖn cã 20 häc sinh, mçi th¸ng, mçi häc sinh ®ãng häc phÝ 15.000 ®ång. Chän mét biÕn sè nguyªn (kh¶ n¨ng -32768 ¸ 32767)  ®Ó l­u tr÷ tæng sè häc phÝcña líp häc trong th¸ng, nÕu xayra tr­êng hîp cã thªm 5 häc sinh n÷a vµo líp th× gi¸ trÞ tæng häc phÝ thu ®­îc lµ 375000 ®ång, v­ît kh¶ n¨ng l­u tr÷ cña biÕn ®· chän, g©y ra t×nh tr¹ng trµn, sai lÖch.

Phï hîp víi c¸c thao t¸c trªn ®ã : Tiªu chuÈn nµy gióp t¨ng hiÖu qu¶ cña ®Ò ¸n : viÖc ph¸t triÓn c¸c thuËt to¸n ®¬n gi¶n, tù nhiªn h¬n; ch­¬ng tr×nh ®¹t hiÖu qu¶ cao h¬n vÒ tèc ®é xö lý.

TiÕt kiÖm tµi nguyªn hÖ thèng : CÊu tróc d÷ liÖu chØ nªn sö dông tµi nguyªn võa ®ñ ®Ó ®¶m nhiÖm ®­îc chøc n¨ng cña nã. Th«ng th­êng cã hai lo¹i tµi nguyªn cÇn l­u ý nhÊt :CPU vµ bé nhí. Tiªu chuÈn nµy nªn c©n nh¾c tuú vµo t×nh huèng cô thÓ khi thùc hiÖn ®Ò ¸n. NÕu tæ chøc sö dông ®Ò ¸n cÇn cã nh÷ng xö lý nhanh th× khi chän cÊu tróc d÷ liÖu yÕu tè tiÕt kiÖm thêi gian xö lý ph¶i ®Æt nÆng h¬n tiªu chuÈn sö dông tèi ®a bé nhí, vµ ng­îc l¹i.

VÝ dô: Mét sè t×nh huèng chän cÊu tróc l­u tr÷ l·ng phÝ

- Sö dông biÕn integer (2 bytes) ®Ó l­u tr÷ mét gi¸ trÞ cho biÕt th¸ng hiÖn hµnh. Trong t×nh huèng nµy ta chØ cÇn sö dông biÕn kiÓu byte lµ ®ñ.

- §Ó l­u tr÷ danh s¸ch häc viªn trong mét líp, sö dông m¶ng 60 phÇn tö (giíi h¹n sè häc viªn trong líp tèi ®a lµ 60). NÕu sè l­îng häc viªn thËt sù Ýt h¬n 60, th× g©y l·ng phÝ bé nhí. H¬n n÷a, sè häc viªn cã thÓ thay ®æi theo tõng kú, tõng n¨m. Trong tr­êng hîp nµy ta cÇn cã mét cÊu tróc d÷ liÖu ling ®äng h¬n m¶ng, ch¼ng h¹n danh s¸ch liªn kÕt - sÏ ®­îc häc trong ch­¬ng 4.

1.3.kiÓu d÷ liÖu Vµ cÊu tróc d÷ liÖu

     M¸y tÝnh thùc sù chØ cã thÓ l­u tr÷ ë d¹ng nhÞ ph©n th« s¬. NÕu muèn ph¶n ¸nh ®­îc d÷ liÖu thùc tÕ ®a d¹ng vµ phong phó, cÇn ph¶i x©y dùng nh÷ng phÐp ¸nh x¹, nh÷ng qui t¾c tæ chøc phøc t¹p che lªn tÇng d÷ liÖu th«, nh»m ®­a ra nh÷ng kh¸i niÖm logic vÒ h×nh thøc l­u tr÷ kh¸c nhau th­êng ®­îc gäi lµ kiÓu d÷ liÖu. Nh­ ®· ph©n tÝch ë phÇn ®Çu, gi÷a h×nh thøc l­u tr÷ vµ c¸c thao t¸c xö lý trªn ®ã cã quan hÖ mËt thiÕt víi nhau. Tõ ®ã cã thÓ ®­a ra mét ®Þnh nghÜa cho kiÓu d÷ liÖu nh­ sau

1.3.1.§Þnh nghÜa kiÓu d÷ liÖu

KiÓu d÷ liÖu T ®­îc x¸c ®Þnh bëi bé <V,O>, víi :

V: tËp c¸c gi¸ trÞ hîp lÖ mµ ®èi t­îng kiÓu T cã thÓ l­u tr÷

O : tËp c¸c thao t¸c xö lý cã thÓ thi hµnh trªn ®èi t­îng kiÓu T.

VÝ dô :

- KiÓu d÷ liÖu ký tù = <V_c, O_c> víi

V_c = {a - z, A - Z}

O_c = {lÊy m· ASCII cña ký tù, biÕn ®æi ký tù th­êng thµnh ký tù hoa,...}

- KiÓu d÷ liÖu sè nguyªn = <V_i, O_i>

        V_c = {-32768 ¸32767}

         O_c = {+, -, *, /, %, c¸c phÐp so s¸nh}

Nh­ vËy, muèn sö dông mét kiÓu d÷ liÖu cÇn n¾m v÷ng c¶ néi dung d÷ liÖu ®­îc phÐp l­u tr÷ vµ c¸c xö lý t¸c ®éng trªn ®ã.

1.3.2.C¸c thuéc tÝnh cña mét kiÓu d÷ liÖu

 Mét kiÓu d÷ liÖu bao gåm  c¸c thuéc tÝnh sau :

• Tªn kiÓu d÷ liÖu
• MiÒn gi¸ trÞ
• KÝch th­íc l­u tr÷
• TËp c¸c to¸n tö t¸c ®éng lªn kiÓu d÷ liÖu

1.3.3.C¸c kiÓu d÷ liÖu c¬ b¶n

     Th«ng th­êng trong mét hÖ kiÓu cña ng«n ng÷ lËp tr×nh sÏ cã mét sè kiÓu d÷ liÖu ®­îc gäi lµ kiÓu d÷ liÖu ®¬n hay kiÓu d÷ liÖu ph©n tö (atomic).

Th«ng th­êng, c¸c kiÓu d÷ liÖu c¬ b¶n bao gåm :

• KiÓu cã thø tù rêi r¹c : sè nguyªn, ký tù, logic, liÖt kª, miÒn con
• KiÓu kh«ng rêi r¹c : sè thùc

     Tuú tõng ng«n ng÷ lËp tr×nh, c¸c kiÓu d÷ liÖu ®Þnh nghÜa s½n nµy cã thÓ kh¸c nhau ®«i chót. Ch¼ng h¹n, víi ng«n ng÷ C, c¸c kiÓu d÷ liÖu nµy chØ gåm sè nguyªn, sè thùc, ký tù. Vµ theo quan ®iÓm cña C, kiÓu ký tù thùc chÊt còng lµ kiÓu sè nguyªn vÒ mÆt l­u tr÷, chØ kh¸c vÒ c¸ch sö dông. Ngoµi ra, gi¸ trÞ logic ®óng (TRUE) vµ gi¸ trÞ logic sai (FALSE) ®­îc biÓu diÔn trong ng«n ng÷ C nh­ lµ c¸c gi¸ trÞ nguyªn kh¸c 0 vµ b»ng 0. Trong khi ®ã Pascal ®Þnh nghÜa tÊt c¶ c¸c kiÓu d÷ liÖu ®· liÖt kª ë trªn vµ ph©n biÖt chung mét c¸ch chÆt chÏ.

HÖ kiÓu cña Pascal cã thÓ ®­îc ®Þnh nghÜa ®Ö qui nh­ sau:

1. KiÓu integer

2. KiÓu real

3. KiÓu boolean

4. KiÓu char

5. KiÓu liÖt kª

Gi¶ sö obj₁, obj₂,..., obj_n lµ c¸c ®èi t­îng nµo ®ã. Khi ®ã ta cã thÓ t¹o nªn kiÓu liÖt kª T b»ng c¸ch liÖt kª tÊt c¶ c¸c ®èi t­îng ®ã.

 

	type T = (obj1, obj2,..., objn)

 

 

Chó ý : TÊt c¶ c¸c kiÓu ®¬n ®Òu lµ c¸c kiÓu cã thø tù, tøc lµ víi hai gi¸ trÞ bÊt kú a vµ b thuéc cïng mét kiÓu, ta lu«n cã a <= b hoÆc a >= b. C¸c kiÓu cßn l¹i ®Òu lµ kiÓu ®Õm ®­îc, trõ kiÓu real.

6. KiÓu ®o¹n con

 

	type T = min..max

 

 

 

Trong ®ã min vµ max lµ cËn d­íi vµ cËn trªn cña kho¶ng; min vµ max lµ c¸c gi¸ trÞ thuéc cïng mét kiÓu integer, char hoÆc c¸c kiÓu liÖt kª, ®ång thêi min < max. KiÓu T gåm tÊt c¶ c¸c gi¸ trÞ tõ min ®Õn max.

1.3.4. C¸c kiÓu d÷ liÖu cã cÊu tróc

      Khi gi¶i quyÕt c¸c bµi to¸n phøc t¹p, ta chØ sö dông c¸c d÷ liÖu c¸c d÷ liÖu ®¬n lµ kh«ng ®ñ, ta ph¶i cÇn ®Õn c¸c cÊu tróc d÷ liÖu. Mét cÊu tróc d÷ liÖu bao gåm mét tËp hîp nµo ®ã c¸c d÷ liÖu ph©n tö, c¸c thµnh phÇn nµy liªn kÕt víi nhau bëi mét ph­¬ng ph¸p nµo ®ã. §a sè c¸c ng«n ng÷ lËp tr×nh ®Òu cµi ®Æt s½n mét sè kiÓu cã cÊu tróc c¬ b¶n nh­ m¶ng, chuçi, tËp tin, b¶n ghi...vµ cung cÊp c¬ chÕ cho lËp tr×nh viªn tù ®Þnh nghÜa kiÓu d÷ liÖu míi.

a) KiÓu array (m¶ng)

Tr ong Pascal vµ trong nhiÒu ng«n ng÷ th«ng dông kh¸c cã mét c¸ch ®¬n gi¶n nhÊt ®Ó t¹o ®Ó liªn kÕt c¸c d÷ liÖu thµnh phÇn, ®ã lµ c¸ch s¾p xÕp c¸c thµnh phÇn cã cïng mét kiÓu thµnh mét d·y. Khi ®ã ta cã mét cÊu tróc d÷ liÖu  ®­îc gäi lµ m¶ng (array). Nh­ v©y, cã thÓ nãi, mét m¶ng lµ mét cÊu tróc d÷ liÖu gåm mét d·y x¸c ®Þnh c¸c d÷ liÖu thµnh phÇn cïng mét kiÓu (m¶ng sè nguyªn, m¶ng sè thùc, m¶ng c¸c b¶n ghi,...).

Gi¶ sö T₀ lµ mét kiÓu ®· cho, ta sÏ gäi T_o lµ kiÓu thµnh phÇn m¶ng. Gi¶ sö I lµ kiÓu ®o¹n con hoÆc kiÓu liÖt kª, ta sÏ gäi I lµ chØ sè m¶ng. Khi ®ã ta cã thÓ t¹o nªn kiÓu m¶ng T víi c¸c thµnh phÇn lµ cña m¶ng lµ c¸c gi¸ trÞ thuéc T₀ vµ ®­îc chØ sè ho¸ bëi tËp h÷u h¹n, cã thø tù I.

 

	type  T = array[I] of T0

 

 

b) KiÓu record (b¶n ghi)

Mét ph­¬ng ph¸p kh¸c ®Ó t¹o nªn c¸c cÊu tróc d÷ liÖu míi, lµ kÕt hîp c¸c thµnh phÇn d÷ liÖu (c¸c thµnh phÇn cã thÓ cã kiÓu kh¸c nhau) thµnh b¶n ghi (record). C¸c thµnh phÇn cña b¶n ghi gäi lµ c¸c tr­êng. C¸c b¶n ghi ®Õn l­ît l¹i ®­îc sö dông ®Ó t¹o nªn c¸c kiÓu d÷ liÖu kh¸c, ch¼ng h¹n nh­ m¶ng c¸c b¶n ghi. 

Gi¶ sö T₁, T₂,...,T_n lµ c¸c kiÓu ®· cho, vµ F₁, F₂,..., F_n lµ c¸c tªn tr­êng. Khi ®ã ta cã thÓ thµnh lËp kiÓu b¶n ghi T víi n tr­êng, tr­êng thø i cã tªn lµ F_i vµ c¸c gi¸ trÞ cña nã cã kiÓu T_i v¬i i = 1, 2,..., n.   

                                               

 

 

 

 

type T  =  record F1 : T1; F2 : T2; ........... Fn: Tn; end;

 

 

 

 

 

 

 

Mçi gi¸ trÞ cña kiÓu b¶n ghi T lµ mét bé n gi¸ trÞ (t₁, t₂,..., t_n), trong ®ã t_i Î T_i (i = 1, 2, ..., n).

c) KiÓu con trá

Mét ph­¬ng ph¸p quan träng n÷a ®Ó kiÕn t¹o c¸c cÊu tróc d÷ liÖu, ®ã lµ sö dông con trá. Trong ph­¬ng ph¸p nµy mçi thµnh phÇn lµ mét b¶n ghi gåm hai tr­êng INFOR vµ LINK, tr­êng INFOR cã thÓ cã mét hay nhiÒu tr­êng d÷ liÖu, cßn tr­êng LINK cã thÓ chøa mét hay nhiÒu con trá trá ®Õn c¸c thµnh phÇn kh¸c cã quan hÖ víi thµnh phÇn ®ã. (kiÓu con trá ta sÏ nghiªn cøu kü trong phÇn danh s¸ch liªn kÕt). Tõ kiÓu nµy ta cã thÓ x©y dùng nªn cÊu tróc d÷ liÖu biÓu diÔn c©y, m« h×nh d÷ liÖu quan träng bËc nhÊt.

Gi¶ sö T lµ mét kiÓu con trá ®· cho. Khi ®ã ta cã thÓ t¹o nªn kiÓu con trá T_p.

type T_p = ^T

 

§èi t­îng  thuéc kiÓu T

P

C¸c gi¸ trÞ cña T_p lµ ®Þa chØ trong bé nhí cña m¸y tÝnh ®Ó l­u gi÷ c¸c ®èi t­îng thuéc kiÓu T.

 

 

H×nh 1.1. BiÓu diÔn con trá

d) KiÓu set (tËp hîp)

Gi¶ sö T₀ lµ mét kiÓu ®· cho. T₀ ph¶i lµ kiÓu cã thø tù ®Õm ®­îc "®ñ nhá", ch¼ng h¹n kiÓu ®o¹n con (giíi h¹n phô thuéc vµo ch­¬ng tr×nh dÞch). Khi ®ã, ta cã thÓ x¸c ®Þnh kiÓu tËp T

 

	type T = set of T0

 

 

Mçi ®èi t­îng cña kiÓu T sÏ lµ mét tËp con cña T₀.

KiÓu file (tÖp)

Gi¶ sö T₀ lµ mét kiÓu nµo ®ã (trõ kiÓu file), khi ®ã

 

	type T = flie of T0

 

 

sÏ x¸c ®Þnh mét kiÓu flie víi c¸c phÇn tö lµ c¸c ®èi t­îng thuéc kiÓu T₀

VÝ dô : sau ®©y lµ ®Þnh nghÜa mét sè kiÓu d÷ liÖu

type  mau  = (white, red, blue, yellow, green);

          mang = array[1..10] of integer;

 Rec = record

infor : mau;

ptr : ^mang;

end;   

                      Reccar = array[1..5] of Rec;

Sau ®©y lµ biÓu diÔn h×nh häc cña mét ®èi t­îng thuéc kiÓu Reccar ®­îc cho trong h×nh 1.2      

 

1 red   2 yellow   3 green   4 blue   5 blue

1 2 3   10 9 0 9 ... 11

1 2 3   10 5 3 8 ... 15

1 2 3   10 3 4 10 ... 14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

H×nh1.2. CÊu tróc d÷ liÖu Reccar

1.3.5.C¸c phÐp to¸n trong hÖ kiÓu Pascal

Nh­ ®· nãi ë trªn, víi mçi kiÓu d÷ liÖu ta chØ cã thÓ thùc hiÖn mét sè phÐp to¸n nhÊt ®Þnh trªn c¸c d÷ liÖu cña kiÓu. Ta kh«ng thÓ ¸p dông mét sè phÐp to¸n trªn c¸c d÷ liÖu thuéc kiÓu nµy cho c¸c d÷ liÖu thuéc kiÓu kh¸c. Ta cã thÓ ph©n tËp hîp c¸c phÐp to¸n trªn c¸c kiÓu d÷ liÖu cña Pascal thµnh hai líp sau :

a) C¸c phÐp to¸n truy cËp : PhÐp to¸n nµy dïng ®Ó truy nhËp ®Õn c¸c thµnh phÇn cña mét ®èi t­îng d÷ liÖu, ch¼ng h¹n truy nhËp ®Õn c¸c thµnh phÇn cña mét m¶ng,®Õn c¸c tr­êng cña b¶n ghi.

VÝ dô:

- Gi¶ sö A lµ mét m¶ng víi tËp chØ sè I. Khi ®ã A[i] cho phÐp ta truy cËp ®Õn thµnh phÇn thø i cña m¶ng.

- NÕu X lµ mét b¶n ghi th× viÖc truy cËp ®Õn tr­êng F cña nã ®­îc thùc hiÖn bëi phÐp to¸n X.F.

b) C¸c phÐp to¸n kÕt hîp d÷ liÖu

Ng«n ng÷ lËp tr×nh pascal cã mét tËp hîp phong phó c¸c phÐp to¸n kÕt hîp mét hoÆc nhiÒu d÷ liÖu ®· cho thµnh d÷ liÖu míi. sau ®©y lµ mét sè nhãm c¸c phÐp to¸n chÝnh.

1. C¸c phÐp to¸n sè häc : §ã lµ c¸c phÐp to¸n +, - * , / trªn tËp sè thùc; c¸c phÐp to¸n +, - * , /, div, mod, trªn tËp sè sè nguyªn.

2. C¸c phÐp to¸n so s¸nh : Trªn c¸c ®èi t­îng thuéc c¸c kiÓu cã thø tù, ta cã thÓ thùc hiÖn c¸c phÐp to¸n so s¸nh  =, <>, <, >, <=, >=. CÇn chó ý r»ng, kÕt qu¶ cña c¸c phÐp to¸n nµy lµ mét gi¸ trÞ cã kiÓu boolean.

3. C¸c phÐp to¸n logic : §ã lµ c¸c phÐp to¸n and, or, not, ®­îc thùc hiÖn trªn hai gi¸ trÞ false vµ true cña kiÓu boolean.

4. C¸c phÐp to¸n tËp hîp : C¸c phÐp to¸n hîp, giao, hiÖu cña c¸c tËp hîp trong Pascal ®­îc biÓu diÔn bëi +, -, *, - t­¬ng øng. ViÖc kiÓm tra mét ®èi t­îng x cã lµ phÇn tö cña tËp A hay kh«ng ®­îc thùc hiÖn bëi phÐp to¸n in (x in A). KÕt qu¶ cña phÐp to¸n nµy lµ mét gi¸ trÞ cã kiÓu boolean.

1.4. ThuËt to¸n vµ ph©n tÝch thuËt to¸n

1.4.1.ThuËt to¸n

1.4.1.1.Kh¸i niÖm thuËt to¸n

ThuËt to¸n (algorithm) lµ mét trong nh÷ng kh¸i niÖm quan träng nhÊt trong tin häc. ThuËt ng÷ thuËt to¸n xuÊt ph¸t tõ nhµ to¸n häc ArËp Abu Ja'far Mohammed ibn Musa al Khowarizmi (kho¶ng n¨m 825). Tuynhiªn trong lóc bÊy giê vµ trong nhiÒu thÕ kû sau, nã kh«ng mang néi dung nh­ ngµy nay chóng ta quan niÖm. thuËt to¸n næi tiÕng nhÊt, cã tõ thêi cæ Hy l¹p lµ thuËt to¸n Euclid, thuËt to¸n t×m ­íc chung lín nhÊt cña hai sè nguyªn. Cã thÓ m« t¶ thuËt to¸n nµy nh­ sau

ThuËt to¸n Euclid

Vµo : m, n nguyªn d­¬ng

Ra : d, ­íc chung lín nhÊt cña m vµ n.

Ph­¬ng ph¸p

B­íc 1: T×m r, phÇn d­ cña phÐp chia m cho n

B­íc 2: NÕu r = 0, th× d ¬ n (g¸n gi¸ trÞ cña n cho d) vµ dõng l¹i

          Ng­îc l¹i, th× m ¬ n, n ¬ r vµ quay l¹i b­íc 1  

§Þnh nghÜa: ThuËt to¸n lµ mét d·y h÷u h¹n c¸c b­íc, mçi b­íc m« t¶ chÝnh x¸c c¸c phÐp to¸n hoÆc hµnh ®éng cÇn thùc hiÖn ®Ó gi¶i quyÕt vÊn ®Ò ®Æt ra.

§Æc tr­ng cña thuËt to¸n

§Þnh nghÜa trªn, cßn chøa ®ùng nhiÒu ®iÒu ch­a râ rµng. §Ó hiÓu ®Çy ®ñ ý nghÜa cña thuËt to¸n, chóng ta nªu ra 5 ®Æc tr­ng cña nã:

 1. Bé d÷ liÖu vµo: Mçi thuËt to¸n cÇn cã mét sè (cã thÓ b»ng 0) d÷ liÖu vµo (input). §ã lµ c¸c gi¸ trÞ cÇn ®­a vµo khi thuËt to¸n b¾t ®Çu lam viÖc. C¸c d÷ liÖu nµy cÇn ®­îc lÊy tõ c¸c tËp hîp gi¸ trÞ cô thÓ nµo ®ã. Ch¼ng h¹n, trong thuËt to¸n Euclid trªn, m vµ n lµ c¸c d÷ liÖu vµo lÊy tõ tËp c¸c sè nguyªn d­¬ng.

2. D÷ liÖu ra: Mçi thuËt to¸n cÇn cã mét hoÆc nhiÒu d÷ liÖu ra (output). §ã lµ c¸c gi¸ trÞ cã quan hÖ hoµn toµn x¸c ®Þnh víi c¸c d÷ liÖu vµo vµ lµ kÕt qu¶ cña sù thùc hiÖn thuËt to¸n.Trong thuËt to¸n Euclid cã mét d÷ liÖu ra, ®ã lµ d, khi thùc hiÖn ®Õn b­íc 2 vµ ph¶i dõng l¹i (tr­êng hîp r = 0), gi¸ trÞ cña d lµ ­íc chung lín nhÊt cña m vµ n.

3. TÝnh x¸c ®Þnh: Mçi b­íc cña thuËt to¸n cÇn ph¶i ®­îc m« t¶ mét c¸c chÝnh x¸c, chØ cã mét c¸ch hiÓu duy nhÊt. HiÓn nhiªn ®©y lµ mét ®ßi hái rÊt quan träng. Bëi v×, nÕu mét b­íc cã thÓ hiÓu theo nhiÒu c¸ch kh¸c nhau, th× cïng mét d÷ liÖu vµo, nh÷ng ng­êi thùc hiÖn thuËt to¸n kh¸c nhau cã thÓ dÉn ®Õn c¸c kÕt qu¶ kh¸c nhau. §Ó ®¶m b¶o ®­îc tÝnh x¸c ®Þnh thuËt to¸n cÇn ph¶i ®­îc m« t¶ trong c¸c ng«n ng÷ lËp tr×nh. Trong c¸c ng«n ng÷ nµy, c¸c mÖnh ®Ò ®­îc t¹o thµnh theo qui t¾c cóph¸pnghiªm ngÆt vµ chØ cã mét ý nghÜa duy nhÊt.

4. TÝnh kh¶ thi: TÊt c¶ c¸c phÐp to¸n cã mÆt trong c¸c b­íc cña thuËt to¸n ph¶i ®ñ ®¬n gi¶n. §iÒu nµy cã nghÜa lµ, ng­êi lËp tr×nh cã thÓ thùc hiÖn chØ b»ng giÊy tr¾ng vµ bót trong kho¶ng thêi gian h÷u h¹n. Ch¶ng hain víi thuËt to¸n Euclid, ta chØ cÇn thùc hiÖn c¸c phÐp chia c¸c sè nguyªn c¸c sè nguyªn, c¸c phÐp g¸n vµ c¸c phÐp so s¸nh ®Ó biÕt ®­îc r = 0 hay r ¹ 0.

5.TÝnh dõng : Víi mäi bé d÷ liÖu vµo tho¶ m·n c¸c ®iÒu kiÖn cña d÷ liÖu vµo, thuËt to¸n ph¶i dõng l¹i sau mét sè h÷u h¹n c¸c b­íc cÇn thùc hiÖn. Ch¼ng h¹n, thuËt to¸n Euclid tho¶ m·n ®iÒu kiÖn nµy. Bëi v× khi thùc hiÖn b­íc 1 th× gi¸ trÞ cña r nhá h¬n n, nÕu r ¹ 0 th× gi¸ trÞ cña n ë b­íc 2 lµ gi¸ trÞ cña r ë b­íc tr­íc, ta cã  n > r = n₁> r₁ = n₂ > r₂...  D·y sè nguyªn d­¬ng gi¶m dÇn cÇn ph¶i kÕt thóc ë 0, do ®ã sau mét sè b­íc nµo ®ã gi¸ trÞ cña r ph¶i b»ng 0, thuËt to¸n dõng.        

1.4.2.BiÓu diÔn thuËt to¸n 

Cã nhiÒu ph­¬ng ph¸p biÓudiÔn thuËt to¸n. Cã thÓ biÓudiÔn thuËt to¸n b»ng danh s¸ch c¸c b­íc, c¸c b­íc ®­îc diÔn ®¹t b»ng ng«n ng÷ th«ng th­êng vµ c¸c ký hiÖu to¸n häc. Cã thÓ biÓu diÔn b»ng s¬ ®å khèi. Tuy nhiªn, nh­ ®· tr×nh bµy, ®Ó ®¶m b¶o tÝnh c¸c ®Þnh cña thuËt to¸n nªn thuËt to¸n cÇn ®­îc viÕt trong ng«n ng÷ lËp tr×nh.

1.4.3. Ph©n tÝch thuËt to¸n

Gi¶ sö ®èi víi mét bµi to¸n nµo ®ã chóng ta cã mét sè thuËt to¸n gi¶i. Mét c©u hái ®Æt ra lµ, chóng ta cÇn chän thuËt to¸n nµo trong sè thuËt to¸n ®· cã ®Ó gi¶i bµi to¸n mét c¸ch hiÖu qu¶ nhÊt. Sau ®©y ta ph©n tÝch thuËt to¸n vµ ®¸nh gi¸ ®é phøc t¹p tÝnh to¸n cña nã.

1.4.3.1.TÝnh hiÖu qu¶ cña thuËt to¸n

Khi gi¶i mét vÊn ®Ò, chóng ta cÇn chän trong sè c¸c thuËt to¸n, mét thuËt to¸n mµ chóng ta cho lµ tèt nhÊt. VËy ta cÇn lùa chän thuËt to¸n dùa trªn c¬ së nµo ? Th«ng th­êng ta dùa trªn hai tiªu chuÈn sau ®©y:

1. ThuËt to¸n ®¬n gi¶n, dÔ hiÓu, dÔ cµi ®Æt (dÔ viÕt ch­¬ng tr×nh)

2. ThuËt to¸n sö dông tiÕp kiÖn nhÊt nguån tµi nguyªn cña m¸y tÝnh, vµ ®Æc biÖt, ch¹y nhanh nhÊt cã thÓ ®­îc.

Khi ta viÕt mét ch­¬ng tr×nh chØ ®Ó sö dông mét sè Ýt lÇn, vµ c¸i gi¸ cña thêi gian viÕt ch­¬ng tr×nh v­ît xa c¸i gi¸ cña ch¹y ch­¬ng tr×nh th× tiªu chuÈn (1) lµ quan träng nhÊt. Nh­ng cã tr­êng hîp ta cÇn viÕt c¸c ch­¬ng tr×nh (thñ tôc hoÆc hµm ) ®Ó sö dông nhiÒu lÇn, cho nhiÒu ng­êi sö dông, khi ®ã gi¸ cña thêi gian ch¹y    

ch­¬ng tr×nh sÏ v­ît xa gi¸ viÕt nã. Ch¼ng h¹n, c¸c thñ tôc s¾p xÕp, t×m kiÕm ®­îc sö dông rÊt nhiÒu lÇn, bëi rÊt nhiÒu ng­êi trong c¸c bµi to¸n kh¸c nhau. Trong tr­êng hîp nµy ta cÇn dùa trªn tiªu chuÈn (2). Ta sÏ cµi ®Æt thuËt to¸n cã thÓ rÊt phøc t¹p, miÔn lµ ch­¬ng tr×nh nhËn ®­îc ch¹y nhanh h¬n c¸c thuËt to¸n kh¸c.

Tiªu chuÈn (2) ®­îc xem lµ tÝnh hiÖu qu¶ cña thuËt to¸n. TÝnh hiÖu qu¶ cña thuËt to¸n bao g«mg hai nh©n tè c¬ b¶n

1. Dung l­îng kh«ng gian nhí cÇn thiÕt ®Ó l­u gi÷ c¸c d÷ liÖu vµo, c¸c kÕt qu¶ tÝnh to¸n trung gian vµ c¸c kÕt qu¶ cña thuËt to¸n.

2. Thêi gian cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n (ta gäi lµ thêi gian ch¹y ch­¬ng tr×nh, thêi gian nµy kh«ng phô thuéc vµo c¸c yÕu tè vËt lý cña m¸y tÝnh (tèc ®é xö lý cña m¸y tÝnh, ng«n ng÷ viÕt ch­¬ng tr×nh...  ))

Chóng ta sÏ chØ quan t©m ®Õn thêi gian thùc hiÖn thuËt to¸n. V× vËy khi nãi ®Õn ®¸nh gi¸ ®é phøc t¹p cña thuËt to¸n, cã nghÜa lµ ta nãi ®Õn ®¸nh gi¸ thêi gian thùc hiÖn. Mét thuËt to¸n cã hiÖu qu¶ ®­îc xem lµ thuËt to¸n cã thêi gian ch¹y Ýt h¬n c¸c thuËt to¸n kh¸c.

1.4.3.2.§¸nh gi¸ thêi gian thùc hiÖn cña thuËt to¸n

Cã hai c¸ch tiÕp cËn ®Ó ®¸nh gi¸ thêi gian thùc hiÖn cña mét thuËt to¸n

Ph­¬ng ph¸p thö nghiÖm: Chóng ta viÕt ch­¬ng tr×nh vµ cho ch¹y ch­¬ng tr×nh víi c¸c d÷ liÖu vµo kh¸c nhau trªn mét m¸y tÝnh nµo ®ã. Thêi gian ch¹y ch­¬ng tr×nh phô thuéc vµo c¸c nh©n tè sau ®©y:

1. C¸c d÷ liÖu vµo

2. Ch­¬ng tr×nh dÞch ®Ó chuyÓn ch­¬ng tr×nh nguån thµnh ch­¬ng tr×nh m· m¸y.

3. Tèc ®é thùc hiÖn c¸c phÐp to¸n cña m¸y tÝnh ®­îc sö dông ®Ó ch¹y ch­¬ng tr×nh.

V× thêi gian ch¹y ch­¬ng tr×nh phô thuéc vµo nhiÒu nh©n tè, nªn ta kh«ng thÓ biÓu diÔn chÝnh x¸c thêi gian ch¹y lµ bao nhiªu®¬n vÞ thêi gian chuÈn, ch¼ng h¹n nã lµ bao nhiªu gi©y.

Ph­¬ng ph¸p lý thuyÕt : ta sÏ coi thêi gian thùc hiÖn cña thuËt to¸n nh­ lµ hµm sè cña cì d÷ liÖu vµo. Cì cña d÷ liÖu vµo lµ mét tham sè ®Æc tr­ng cho d÷ liÖu vµo, no cã ¶nh h­ëng quyÕt ®Þnh ®Õn thêi gian thùc hiÖn ch­¬ng tr×nh. C¸i mµ chóng ta chän lµm  cì cña d÷ liÖu vµo phô thuéc vµo c¸c thuËt to¸n cô thÓ. Ch¼ng h¹n, ®èi víi c¸c thuËt to¸n s¾p xÕp m¶ng, th× cì cña d÷ liÖu vµo lµ sè thµnh phÇn cña m¶ng; ®èi víi thuËt to¸n gi¶i hÖ n ph­¬ng tr×nh tuyÕn tÝnh víi n Èn, ta chän n lµ cì. Th«ng th­êng d÷ liÖu vµo lµ mét sè nguyªn d­¬ng n. Ta sÏ sö dông hµm sè T(n), trong ®ã n lµ cì d÷ liÖu vµo, ®Ó biÓu diÔn thêi gian thùc hiÖn cña mét thuËt to¸n.

Ta cã thÓ x¸c ®Þnh thêi gian thùc hiÖn T(n) lµ sè phÐp to¸n s¬ cÊp cÇn ph¶i tiÕn hµnh khi thùc hiÖn thuËt to¸n. C¸c phÐp to¸n s¬ cÊp lµ c¸c phÐp to¸n mµ thêi gian thùc hiÖn vbÞ chÆn trªn bëi mét h»ng sè chØ phô thuéc vµo c¸ch cµi ®Æt ®­îc sö dông. Ch¼ng h¹n c¸c phÐp to¸n sè häc +, -, *, /, c¸c phÐp to¸n so s¸nh =, <>... lµ c¸c phÐp to¸n s¬ cÊp.

1.4.3.3.§é phøc t¹p tÝnh to¸n cña gi¶i thuËt

Khi ®¸nh gi¸ thêi gian thùc hiÖn b»ng ph­¬ng ph¸p to¸n häc, chóng ta sÏ bá qua nh©n tè phô thuéc vµo c¸ch cµi ®Æt, chØ tËp trung vµo x¸c ®Þnh ®é lín cña thêi gian thùc hiÖn T(n). Ký hiÖu to¸n häc O (®äc lµ « lín) ®­îc sö dông ®Ó m« t¶ ®é lín cña hµm T(n).

Gi¶ sö n lµ sè nguyªn kh«ng ©m, T(n) vµ f(n) lµ c¸c hµm thùc kh«ng ©m. Ta viÕt T(n) = O(f(n)) (®äc : T(n) lµ « lín cña f(n)), nÕu vµ chØ nÕu tån t¹i c¸c h»ng sè d­¬ng c vµ n_o sao cho T(n) £ c.f(n), víi " n > n_o.

NÕu mét thuËt to¸n cã thêi gian thùc hiÖn T(n) = O(f(n)), chóng ta sÏ nãi r»ng thuËt to¸n cã thêi gian thùc hiÖn cÊp f(n).

VÝ dô. Gi¶ sö T(n) = 10n² + 4n + 4

Ta cã : T(n) £ 10n² +  4n² + 4n² = 12 n² , víi "n ³ 1

VËy T(n) = O(n²). Trong tr­êng hîp nµy ta nãi thuËt to¸n cã ®é phøc t¹p (cã thêi gian thùc hiÖn) cÊp n².

B¶ng sau ®©y cho ta c¸c cÊp thêi gian thùc hiÖn thuËt to¸n ®­îc sö dông réng r·i nhÊt vµ tªn gäi th«ng th­êng cña chóng.

Ký hiÖu « lín	Tªn gäi th«ng th­êng
O(1)	H»ng
O(log2n)	logarit
O(n)	TuyÕn tÝnh
O(nlog2n)	nlog2n
O(n2)	B×nh ph­¬ng
O(n3)	LËp ph­¬ng
O(2n)	Mò

Danh s¸ch trªn s¾p xÕp theo thø tù t¨ng dÇn cña cÊp thêi gian thùc hiÖn

C¸c hµm nh­   log₂n, n, nlog₂n, n², n³ ®­îc gäi lµ c¸c hµm ®a thøc. Gi¶i thuËt víi thêi gian thùc hiÖn cã cÊp hµm ®a thøc th× th­êng chÊp nhËn ®­îc.

C¸c hµm nh­ 2ⁿ, n!, nⁿ ®­îc gäi lµ hµm lo¹i mò. Mét gi¶i thuËt mµ thêi gian thùc hiÖn cña nã lµ c¸c hµm lo¹i mò th× tèc ®é rÊt chËm.

1.4.3.4.X¸c ®Þnh ®é phøc t¹p tÝnh to¸n

X¸c ®Þnh ®é phøc t¹p tÝnh to¸n cña mét gi¶i thuËt bÊt kú cã thÓ dÉn ®Õn nh÷ng bµi to¸n phøc t¹p. Tuy nhiªn, trong thùc tÕ, ®èi víi mét sè gi¶i thuËt ta còng cã thÓ ph©n tÝch ®­îc b»ng mét sè qui t¾c ®¬n gi¶n.

• Qui t¾c tæng: Gi¶ sö T₁(n) vµ T₂(n) lµ thêi gian thùc hiÖn cña hai giai ®o¹n ch­¬ng tr×nh P₁ vµ P₂ mµ T₁(n) = O(f(n)); T₂(n) = O(g(n)) th× thêi gian thùc hiÖn ®o¹n P₁ råi P₂ tiÕp theo sÏ lµ  T₁(n) + T₂(n) = O(max(f(n),g(n))).

VÝ dô : Trong mét ch­¬ng tr×nh cã 3 b­íc thùc hiÖn mµ thêi gian thùc hiÖn t­ng b­íc lÇn l­ît lµ O(n²), O(n³) vµ O(nlog₂n) th× thêi gian thùc hiÖn 2 b­íc ®Çu lµ O(max (n², n³)) = O(n³). Khi ®ã thêi gian thùc hiÖn ch­¬ng tr×nh sÏ lµ O(max(n³,nlog₂n)) = O(n³).

• Qui t¾c nh©n: NÕu t­¬ng øng víi P₁ vµ P₂ lµ T₁(n) = O(f(n)), T₂(n) = O(g(n)) th× thêi gian thùc hiÖn P₁ vµ P₂ lång nhau sÏ lµ : T₁(n)T₂(n) = O(f(n)g(n))

   Trong s¸ch b¸o quèc tÕ c¸c thuËt to¸n th­êng ®­îc tr×nh bÇy d­íi d¹ng c¸c thñ tôc hoÆc hµm trong ng«n ng÷ tùa Pascal. §Ó ®¸nh gi¸ thêi gian thùc hiÖn thuËt to¸n, ta cÇn biÕt c¸ch ®¸nh gi¸ thêi gian thùc hiÖn c¸c c©u lÖnh cña Pascal.  C¸c c©u lÖnh trong Pascal ®­îc ®Þnh nghÜa ®Ö qui nh­ sau:

1. C¸c phÐp g¸n, ®äc, viÕt, goto lµ c¸c c©u lÖnh. C¸c lÖnh nµy gäi lµ lÖnh ®¬n

2. NÕu S₁, S₂,..., S_n lµ c¸c c©u lÖnh th×

                     begin  S₁, S₂,..., S_n  end

lµ c©u lÖnh. LÖnh nµy gäi lµ hîp thµnh (hoÆc khèi).

3. NÕu S₁ vµ S₂ lµ c¸c c©u lÖnh vµ E lµ biÓu thøc logic th×

                    if E then S₁ else S₂

lµ c©u lÖnh, vµ

                   if E then S₁

lµ c©u lÖnh. C¸c lÖnh nµy gäi lµ lÖnh if.

4. NÕu S₁, S₂,..., S_{n + 1} lµ c¸c c©u lÖnh, E lµ biÓu thøc cã kiÓu thø tù ®Õm ®­îc, vµ v₁, v₂, ..., v_n lµ c¸c gi¸ trÞ cïng kiÓu víi E th×

case E of

v₁ : S₁ ;

v₂ : S₂ ;

...........

v_n : S_n ;

                             [else   S_{n + 1}]

end;

lµ c©u lÖnh. LÖnh nµy ®­îc gäi lµ lÖnh case.

5. NÕu S lµ c©u lÖnh vµ E lµ biÓu thøc logic th×

                   while    E    do    S

lµ c©u lÖnh. LÖnh nµy ®­îc gäi lµ lÖnh while.

     6. NÕu S₁, S₂,..., S_n  lµ c¸c c©u lÖnh, E lµ biÓu thøc logic th×

repeat    S₁, S₂,..., S_n until  E

lµ c©u lÖnh. LÖnh nµy ®­îc gäi lµ lÖnh repeat

     7. Víi S lµ c©u lÖnh, E₁ vµ E₂ lµ c¸c biÓu thøc cã cïng mét kiÓu thø tù ®Õm ®­îc, th×

 for i:= E₁ to E₂ do S

lµ c©u lÖnh, vµ  

for i:= E₂ downto E₁ do S

lµ c©u lÖnh. LÖnh nµy ®­îc gäi lµ lÖnh for.

Gi¶ sö r»ng, c¸c lÖnh g¸n kh«ng chøa c¸c lêi gäi hµm. Khi ®ã ®Ó ®¸nh gi¸ thêi gian thùc hiÖn mét ch­¬ng tr×nh, ta cã thÓ ¸p dông ph­¬ng ph¸p ®Ö qui sau

1. Thêi gian thùc hiÖn c¸c lÖnh ®¬n : g¸n, ®äc, viÕt lµ O(1)

2. LÖnh hîp thµnh : thêi gian thùc hiÖn lÖnh hîp thµnh ®­îc x¸c ®Þnh bëi luËt tæng.

3. LÖnh if : Gi¶ sö thêi gian thùc hiÖn c¸c lÖnh S₁, S₂ lµ O(f(n)) vµ O(g(n)) t­¬ng øng. Khi ®ã thêi gian thùc hiÖn lÖnh if lµ O(max (f()n), g(n)))

4. LÖnh case: LÖnh nµy ®­îc ®¸nh gi¸ nh­ lÖnh if

5. LÖnh while : Gi¶ sö thêi gian thùc hiÖn lÖnh S (th©n cña while) lµ O(f(n)) . Gi¶ sö g(n) lµ sè tèi ®a c¸c lÇn thùc hiÖn lÖnh while lµ O(f(n)g(n)).

6. LÖnh repeat :Gi¶ sö thêi gian thùc hiÖn khèi begin S₁, S₂, ...,S_n end lµ O(f(n)). Gi¶ sö g(n) lµ sè lÇn tèi ®a c¸c lÇn lÆp. Khi ®ã thêi gian thùc hiÖn lÖnh repeat lµ O(f(n)g(n)).

7. LÖnh for : LÖnh nµy ®­îc ®¸nh gi¸ t­¬ng tù nh­ lÖnh repeat vµ while.       

§¸nh gi¸ thñ tôc (hoÆc hµm) ®Ö qui  

Tr­íc hÕt chóng ta xÐt mét vÝ dô cô thÓ. Ta sÏ ®¸nh gi¸ thêi gian thùc hiÖn cña hµm ®Ö qui sau

function Fact (n: integer) : integer;

begin

if n <= 1 then fact :=1

else fact := n* fact (n - 1);

end;

Trong hµm nµy cì cña d÷ liÖu vµo lµ n. Gi¶ sö thêi gian thùc hiÖn hµm lµ T(n). Víi n =1, chØ cÇn thùc hiÖn lÖnh g¸n fact := 1, do ®ã T(1) = O(1).

Víi n > 1. cÇn thùc hiÖn lÖnh g¸n fact  := n*fact(n - 1). Do ®ã thêi gian T(n) lµ O(1) (®Ó thùc hiÖn phÐp nh©n vµ phÐp g¸n) céng víi T(n -1) (®Ó thùc hiÖn lêi gäi ®Ö qui fact(n - 1)). Tãm l¹i, ta cã quan hÖ ®Ö qui sau:

T(1) = O(1)

T(n) = O(1) + T(n - 1)

Thay c¸c O(1) bëi c¸c h»ng nµo ®ã, ta nhËn ®­îc quan hÖ ®Ö qui sau

T(1) = C₁

T(n) = C₂ +  T(n - 1)

§Ó gi¶i ph­¬ng tr×nh ®Ö qui, t×m T(n), chóng ta ¸p dông ph­¬ng ph¸p thÕ lÆp. Ta cã ph­¬ng tr×nh ®Ö qui

     T(m) = C₂ + T(m - 1), víi m > 1

Thay m lÇn l­ît bëi 2, 3,..., n - 1, n, ta nhËn ®­îc c¸c quan hÖ sau

T(2) = C₂ + T(1)

T(3) = C₂ + T(2)

..........................                 
T(n -1) = C₂ + T(n -2)

T(n) = C₂ + T(n - 1)

B»ng c¸c phÐp thÕ liªn tiÕp, ta nhËn ®­îc

T(n) = (n - 1) C₂ + T(1)

hay T(n) = (n - 1) C₂ + C₁, trong ®ã C₁ vµ C₂ lµ c¸c h»ng nµo ®ã.

Do ®ã, T(n) = O(n).

Tõ vÝ dô trªn, ta suy ra ph­¬ng ph¸p tæng qu¸t sau ®©y ®Ó ®¸nh gi¸ thêi gian thùc hiÖn thñ tôc (hµm) ®Ö qui. §Ó ®¬n gi¶n, ta gi¶ thiÕt r»ng c¸c thñ tôc (hµm) lµ ®Ö qui trùc tiÕp. §iÒu ®ã cã nghÜa lµ c¸c thñ tôc (hµm) chØ chøa c¸c lêi gäi ®Ö qui ®Õn chÝnh nã. Gi¶ sö thêi gian thùc hiÖn thñ tôc lµ T(n), víi n lµ cì d÷ liÖu ®Çu vµo. Khi ®ã thêi gian thùc hiÖn c¸c lêi gäi ®Ö qui ®­îc ®¸nh gi¸ th«ng qua c¸c b­íc sau

• §¸nh gi¸ thêi gian thùc hiÖn T(n₀), víi n₀ lµ cì d÷ liÖu vµo nhá nhÊt cã thÓ ®­îc (trong vÝ dô trªn, ®ã lµ T(1)).
• §¸nh gi¸ th©n cña thñ tôc theo qui t¾c 1-7 (qui t¾c ®¸nh gi¸ thêi gian thùc hiÖn c¸c c©u lÖnh) ta sÏ nhËn ®­îc quan hÖ ®Ö qui sau ®©y

T(n) =F(T(m₁), T(m₂),..., T(m_k))

Trong ®ã m₁, m₂,..., m_k < n. Gi¶i ph­¬ng tr×nh ®Ö qui nµy, ta sÏ nhËn ®­îc sù ®¸nh gi¸ cña T(n).

1.4.Ph©n tÝch mét sè thuËt to¸n

VÝ dô 1: Ph©n tÝch thuËt to¸n Euclid

function Euclid (m, n : integer) :integer;

var  r : integer ;

begin

r := m  mod  n;                  (1) 

while  r<> 0 do                 (2)

begin

 m := n;                (3)

 n :=r;                   (4)

 r := m  mod  n;   (5)

end;

Euclid := n;                       (6)

end;

Thêi gian thùc hiÖn thuËt to¸n phô thuéc vµo sè nhá nhÊt trong hai sè m vµ n. Gi¶ sö m ³ n > 0, khi ®ã cì cña d÷ liÖu vµo lµ n. C¸c lÖnh (1) vµ (6) cã thêi gian thùc hiÖn lµ O(1) v× chóng lµ c¸c c©u lÖnh g¸n. Do ®ã thêi gian thùc hiÖn thuËt to¸n lµ thêi gian thùc hiÖn c¸c lÖnh while, ta ®¸nh gi¸ thêi gian thùc hiÖn c©u lÖnh (2). Th©n cña lÖnh nµy, lµ khèi gåm ba lÖnh (3), (4) vµ (5). Mçi lÖnh cã thêi gian thùc hiÖn lµ O(1). Do ®ã khèi cã thêi gian thùc hiÖn lµ O(1). Ta cßn ph¶i ®¸nh gi¸ sè lín nhÊt c¸c lÇn thùc hiÖn lÆp khèi.

Ta cã

m = n.q₁ + r₁ , 0  £ r₁ < n

n = r₁.q₂ + r₂ , 0  £ r₂ < r₁

NÕu r₁ £ n/2 th× r₂ < r₁ £ n/2, do ®ã r₂ < n/2

NÕu r₁ > n/2 th× q₂ = 1, tøc lµ n = r₁ + r₂, do ®ã r₂ < n/2.

Tãm l¹i, ta lu«n cã r₂ < n/2.

Nh­ vËy cø hai lÇn thùc hiÖn khèi lÖnh th× phÇn d­ r gi¶m ®i cßn mét nöa cña n. Gäi k lµ sè nguyªn lín nhÊt sao cho 2^k  £ n. Suy ra sè lÇn lÆp tèi ®a lµ 2k + 1 £ 2log₂n + 1. Do ®ã thêi gian thùc hiÖn lÖnh while lµ O(log₂n). §ã còng lµ thêi gian thùc hiÖn cña thuËt to¸n.

VÝ dô 2: Gi¶i thuËt tÝnh gi¸ trÞ cña e^x tÝnh theo c«ng thøc gÇn ®óng

e^x = 1 + x/1! + x²/2! +...+xⁿ/ n!, víi x vµ n cho tr­íc

function Exp1 (n : integer, x :real) :real;

{TÝnh tõng sè h¹ng sau ®ã céng dån l¹i}

var    s, p :real;

         i, j :integer; 

begin

s := 1;                                     (1)

for i : =1 to n do                     (2)

begin

p := 1;                        (3)

for j :=1 to i do          (4)

p := p*x/j;          (5)

s := s + p;                   (6)

end;

exp1 := s;                                (7)

end;

end;

Ta thÊy c©u lÖnh (1) vµ (7) lµ c¸c c©u lÖnh g¸n nªn chóng cã thêi gian thùc hiÖn lµ O(1). Do ®ã thêi gian thùc hiÖn cña gi¶i thuËt phô thuéc vµo c©u lÖnh (2). Ta ®¸nh gi¸ thêi gian thùc hiÖn c©u lÖnh nµy. Trong th©n cña c©u lÖnh nµy bao gåm c¸c lÖnh (3), (4), (5) vµ (6). Hai c©u lÖnh (3) vµ (7) cã thêi gian thùc hiÖn lµ O(n) v× mçi c©u lÖnh ®­îc thùc hiÖn n lÇn. Riªng c©u lÖnh (5) th× thêi gian thùc hiÖn nã cßn phô thuéc vµo c©u lÖnh (4) nªn ta cßn ph¶i ®¸nh gi¸ thêi gian thùc hiÖn c©u lÖnh (4).

Víi i = 1th× c©u lÖnh (5) ®­îc thùchiÖn 1 lÇn

Víi i = 2 th× c©u lÖnh nµy ®­îc thùc hiÖn 2 lÇn

............................................................................

Víi i = n th× c©u lÖnh nµy ®­îc thùc hiÖn n lÇn

Suy ra tæng sè lÇn thùc hiÖn c©u lÖnh (5) lµ

1 + 2  + ... + n = n(n + 1)/2 lÇn

Do ®ã thêi gian thùc hiÖn c©u lÖnh nµy lµ O(n²) vµ ®©y còng lµ thêi gian thùc hiÖn cña gi¶i thuËt.

Ta cã thÓ viÕt gi¶i thuËt nµy theo c¸ch kh¸c : Dùa vµo sè h¹ng tr­íc ®Ó tÝnh sè h¹ng sau

,..., 

function Exp2 (n : integer, x :real) :real;

var    s, p :real;

         i :integer; 

begin

s := 1;                                    (1)

p := 1;                                    (2)

for i : =1 to n do                    (3)

begin

p := p*x/i;;                 (4)

s := s + p;                   (5)

end;

exp2 := s;                                (6)

end;

      end;

T­¬ng tù nh­ gi¶i thuËt tr­íc c¸c c©u lÖnh (1), (2), (6) cã thêi gian thùc hiÖn lµ O(1). Do ®ã thêi gian thùc hiÖn gi¶i thuËt phô thuéc vµo c©u lÖnh (3). V× hai c©u lªnh (4) vµ (5) ®Òu cã thêi gian thùc hiÖn lµ O(n) nªn thêi gian thùc hiÖn cña gi¶i thuËt lµ O(n)

Nh­ vËy tõ hai gi¶i thuËt trªn ta cã thÓ nãi r»ng gi¶i thuËt thø hai tèt h¬n gi¶i thuËt thø nhÊt víi n ®ñ lín (víi n nhá th× thêi gian thùc hiÖn hai gi¶i thuËt nµy t­¬ng ®­¬ng nhau).

VÝ dô 3: T×m trong d·y sè s₁, s₂,..., s_n mét phÇn tö cã gi¸ trÞ b»ng x cho tr­íc

Vµo: D·y s₁, s₂,..., s_n vµ kho¸ cÇn t×m x

Ra: VÞ trÝ phÇn tö cã kho¸ x hoÆc lµ n + 1 nÕu kh«ng t×m thÊy.

function  linear_search(s : day; n :integer ; x :kdl ) :integer;

{trong ®ã day, kdl lµ d·y c¸c phÇn tö vµ kiÓu d÷ liÖu ®· ®­îc ®Þnh nghÜa tõ tr­íc}

var i : integer;

begin

i := 0;

repeat

      i := i + 1;

until (i > n) or (s[i] = x);

       linear_search := i;

end;

Trong vÝ dô nµy ta kh«ng thÓ ®¸nh gi¸ nh­ hai vÝ dô trªn. Do qu¸ tr×nh t×m kiÕm  kh«ng nh÷ng phô thuéc vµo kÝch th­íc cña d÷ liÖu vµo, mµ cßn phô thuéc vµo t×nh tr¹ng cña d÷ liÖu. Tøc lµ thêi gian thùc hiÖn gi¶i thuËt cßn phô thuéc vµo vÞ trÝ cña phÇn tö trong d·y b»ng x. Qu¸ tr×nh t×m kiÕm chØ dõng khi t×m thÊy phÇn tö b»ng x, hoÆc duyÖt hÕt d·y mµ kh«ng t×m thÊy. V× vËy, trong nh÷ng tr­êng hîp nh­ trªn ta cÇn ph¶i ®¸nh gi¸ thêi gian tÝnh tèt nhÊt, tåi nhÊt vµ trung b×nh cña thuËt to¸n víi ®é dµi ®Çu vµo n. Râ rµng thêi gian tÝnh cña thuËt to¸n cã thÓ ®­îc ®¸nh gi¸ bëi sè lÇn thùc hiÖn c©u lÖnh i := i + 1

NÕu s[1] = x th× c©u lÖnh i := i + 1 trong th©n vßng lÆp repeat thùc hiÖn 1lÇn. Do ®ã thêi gian tÝnh tèt nhÊt cña thuËt to¸n lµ O(1).

NÕu x kh«ng xuÊt hiÖn trong d·y kho¸ ®· cho, th× c©u lÖnh i := i + 1®­îc thùc hiÖn n lÇn. V× thÕ thêi gian tÝnh tåi nhÊt lµ O(n).

Cuèi cïng ta tÝnh thêi gian tÝnh trung b×nh cña thuËt to¸n. NÕu x ®­îc t×m thÊy ë vÞ trÝ thø i cña d·y th× c©u lÖnh i := i + 1 ph¶i thùc hiÖn i lÇn (i = 1, 2, ..., n), cßn nÕu x kh«ng xuÊt hiÖn trong d·y th× c©u lÖnh i := i + 1ph¶i thùc hiÖn n lÇn.

Tõ ®ã suy ra sè lÇn trung b×nh ph¶i thùc hiÖn c©u lÖnh i := i + 1 lµ

               [(1 + 2 + ... + n) + n] /(n + 1)      

Ta cã

               [(1 + 2 + ... + n) + n] /(n + 1) £ (n² + n)/(n + 1) = n

VËy thêi gian tÝnh trung b×nh cña thuËt to¸n lµ O(n).

NhËn xÐt: ViÖc x¸c ®Þnh T(n) trong tr­êng hîp trung b×nh th­êng gÆp nhiÒu khã kh¨n v× sÏ ph¶i dïng tíi c«ng cô to¸n ®Æc biÖt, h¬n n÷a tÝnh trung b×nh cã nhiÒu c¸ch quan niÖm. Trong c¸c tr­êng hîp mµ T(n) trung b×nh th­êng khã x¸c ®Þnh ng­êi ta th­êng ®¸nh gi¸ gi¶i thuËt qua gi¸ trÞ xÊu nhÊt cña T(n). H¬n n÷a, trong mét sè líp thuËt to¸n, viÖc x¸c ®Þnh tr­êng hîp xÊu nhÊt lµ rÊt quan träng. 

Bµi tËp ch­¬ng 1

1.1 . T×m thªm c¸c vÝ dô minh ho¹ mèi quan hÖ gi÷a cÊu tróc d÷ liÖu vµ gi¶i thuËt.

1.2. CÊu tróc d÷ liÖu vµ cÊu tróc l­u tr÷ kh¸c nhau ë chç nµo?

1.3. C¸c cÊu tróc d÷ liÖu tiÒn ®Þnh trong mét ng«n ng÷ cã ®ñ ®¸p øng yªu cÇu vÒ tæ chøc d÷ liÖu kh«ng?

1.4. H·y nªu c¸c tÝnh chÊt cña mét gi¶i thuËt vµ cho vÝ dô minh ho¹.

1.5. H·y nªu mét gi¶i thuËt mµ ®é phøc t¹p tÝnh to¸n lµ O(1).

1.6. Cho T(n) = O(n). Chøng minh r»ng T(n) = O(n²).

1.7 Víi c¸c ®o¹n ch­¬ng tr×nh d­íi ®©y h·y x¸c ®Þnh ®é phøc t¹p tÝnh to¸n cña gi¶i thuËt b»ng ký ph¸p ch÷ O lín trong tr­êng hîp tåi nhÊt.

a)        sum := 0;

for i := 1 to n do

begin

readln(x);

sum := sum + 1;

end;

b)        for i := 1 to n do

for j := 1 ton n do

     begin

C[i,j] := 0;

for k := 1 to n do

       C[i,j] := C[i,j] + A[i,k] + B[k,j];

                         end;

c)        for i := 1 to n - 1 do

begin

for j :=1 n -1 do

        if X[j] > X[j + 1] then

begin

tg := X[j];

X[j] := X[j + 1];

 X[j + 1] := tg;

end;

end;