SÁCH EBOOK TIN HỌC 10

2

((TT¸�i ibb¶�n nlÇln«nthtøh�mÆnê®imb)èn) Nhµ xuÊt b¶n gi¸o dôc viÖt nam H·y b¶o qu¶n, gi÷ g×n s¸ch gi¸o khoa ®Ó dµnh tÆng cho c¸c em häc sinh líp sau ! Nhµ xut b�n gi�o dÙc vi÷t nam 1



†1. Tin häc l mét ngnh khoa häc 1. Sù h×nh thµnh vµ ph¸t triÓn cña tin häc Cuéc c¸ch m¹ng c«ng nghiÖp trong lÞch sö loµi ngêi ®· diÔn ra t¬ng ®èi nhanh. ChØ trong kho¶ng thêi gian tõ n¨m 1890 ®Õn n¨m 1920, ®iÖn n¨ng, ®iÖn tho¹i, ra®i«, « t«, m¸y bay ®· ®îc ph¸t minh vµ ®a vµo phôc vô cuéc sèng con ngêi. TiÕp theo ®ã lµ sù ra ®êi cña hµng lo¹t thµnh tùu khoa häc vµ kÜ thuËt kh¸c, trong ®ã cã m¸y tÝnh ®iÖn tö. Tõ l©u, con ngêi ®· quan t©m ®Õn th«ng tin. Tuy nhiªn, tríc ®©y nh÷ng kÕt qu¶ ®¹t ®îc cha cã tÝnh hÖ thèng vµ chØ míi xuÊt hiÖn r¶i r¸c ë mét sè lÜnh vùc khoa häc. Trong vµi thËp kØ gÇn ®©y, x· héi loµi ngêi cã sù bïng næ vÒ th«ng tin. Theo quan ®iÓm truyÒn thèng, ba nh©n tè c¬ b¶n cña nÒn kinh tÕ lµ ®iÒu kiÖn tù nhiªn, nguån lao ®éng vµ vèn ®Çu t. Ngµy nay, ngoµi ba nh©n tè then chèt ®ã xuÊt hiÖn mét nh©n tè míi rÊt quan träng, ®ã lµ th«ng tin  mét d¹ng tµi nguyªn míi. LÞch sö ph¸t triÓn x· héi loµi ngêi ®ang ë nÒn v¨n minh thø ba. Sù h×nh thµnh vµ ph¸t triÓn cña mçi nÒn v¨n minh g¾n liÒn víi mét c«ng cô lao ®éng míi, ch¼ng h¹n nh m¸y h¬i níc  ®èi víi nÒn v¨n minh c«ng nghiÖp, m¸y tÝnh ®iÖn tö ®èi víi nÒn v¨n minh th«ngtin. Cïng víi viÖc s¸ng t¹o ra c«ng cô míi lµ m¸y tÝnh ®iÖn tö, con ngêi còng tËp trung trÝ tuÖ tõng bíc x©y dùng ngµnh khoa häc t¬ng øng ®Ó ®¸p øng nh÷ng yªu cÇu khai th¸c tµi nguyªn th«ng tin. Trong bèi c¶nh ®ã, ngµnh Tin häc ®îc h×nh thµnh vµ ph¸t triÓn thµnh mét ngµnh khoa häc víi c¸c néi dung, môc tiªu, ph¬ng ph¸p nghiªn cøu riªng vµ ngµy cµng cã nhiÒu øng dông trong hÇu hÕt c¸c lÜnh vùc ho¹t ®éng cña x· héi loµi ngêi. Ngµnh Tin häc cã nh÷ng ®Æc ®iÓm t¬ng tù nh nh÷ng ngµnh khoa häc kh¸c nhng còng cã mét sè ®Æc thï riªng. Mét trong nh÷ng ®Æc thï ®ã lµ qu¸ tr×nh nghiªn cøu vµ triÓn khai c¸c øng dông kh«ng t¸ch rêi viÖc ph¸t triÓn vµ sö dông m¸y tÝnh ®iÖn tö. 4

2. §Æc tÝnh vµ vai trß cña m¸y tÝnh ®iÖn tö Trong giai ®o¹n ®Çu, m¸y tÝnh xuÊt hiÖn nh mét trong nhiÒu c«ng cô lao ®éng míi cña con ngêi víi môc ®Ých trî gióp c«ng viÖc tÝnh to¸n thuÇn tuý. Lîng th«ng tin tÝch luü ®îc ngµy cµng nhiÒu vµ cµng ®a d¹ng. Con ngêi ®· kh«ng ngõng c¶i tiÕn c«ng cô lao ®éng nµy ®Ó ®¸p øng nhu cÇu lu tr÷, t×m kiÕm vµ xö lÝ th«ng tin mét c¸ch cã hiÖu qu¶. Ngµy nay, trªn thÕ giíi ®ang diÔn ra qu¸ tr×nh tin häc ho¸ trªn nhiÒu lÜnh vùc ho¹t ®éng cña x· héi loµi ngêi. M¸y tÝnh nãi chung vµ m¸y vi tÝnh nãi riªng xuÊt hiÖn kh¾p n¬i. Cïng víi nh÷ng tham sè truyÒn thèng kh¸c nh ®iÖn n¨ng, thÐp,..., sù ph¸t triÓn cña mçi ®Êt níc b©y giê ®îc xem xÐt th«ng qua mét tham sè n÷a  sè m¸y tÝnh trªn mét ngh×n ngêi d©n. Còng gièng nh cuéc c¸ch m¹ng c«ng nghiÖp, cuéc c¸ch m¹ng th«ng tin ®ang dÉn ®Õn nh÷ng thay ®æi quan träng trong c¸ch sèng vµ ngay c¶ c¸ch suy nghÜ cña chóng ta. Ngoµi sù tß mß, ham hiÓu biÕt, cµng sím cµng tèt mçi ngêi ph¶i ý thøc r»ng nÕu kh«ng cã hiÓu biÕt nhÊt ®Þnh vÒ m¸y tÝnh nãi riªng vµ tin häc nãi chung th× khã cã thÓ hoµ nhËp vµo cuéc sèng hiÖn ®¹i. Nh÷ng ®Æc tÝnh u viÖt sau ®©y khiÕn m¸y tÝnh trë thµnh c«ng cô lao ®éng kh«ng thÓ thiÕu ®îc cña con ngêi trong kØ nguyªn th«ng tin: x M¸y tÝnh cã thÓ \"lµm viÖc kh«ng mÖt mái\" trong suèt 24 giê/ngµy. x Tèc ®é xö lÝ th«ng tin cña m¸y tÝnh rÊt nhanh vµ ngµy cµng ®îc n©ng cao. ChØ trong vßng s¸u m¬i n¨m, tèc ®é cña m¸y tÝnh ®· t¨ng lªn hµng triÖu lÇn. x M¸y tÝnh lµ mét thiÕt bÞ tÝnh to¸n cã ®é chÝnh x¸c cao. x M¸y tÝnh cã thÓ lu tr÷ mét lîng lín th«ng tin trong mét kh«ng gian rÊt h¹n chÕ. Ch¼ng h¹n, mét ®Üa CD (Compact Disc) máng, lín kh«ng qu¸ mét b×a s¸ch cã thÓ lu tr÷ ®îc néi dung cña hµng v¹n trang s¸ch. Nh÷ng thiÕt bÞ lu tr÷ th«ng tin cña m¸y tÝnh ngµy cµng ®îc c¶i tiÕn ®Ó cã dung lîng lín h¬n, tiÖn sö dông h¬n. x Gi¸ thµnh m¸y tÝnh ngµy cµng h¹ nhê nh÷ng tiÕn bé vît bËc cña kÜ thuËt. §©y lµ mét yÕu tè quan träng lµm cho viÖc sö dông c«ng cô nµy ngµy mét trë nªn phæ biÕn h¬n. x M¸y tÝnh ngµy cµng gän nhÑ vµ tiÖn dông. x C¸c m¸y tÝnh cã thÓ liªn kÕt víi nhau thµnh mét m¹ng vµ c¸c m¹ng m¸y tÝnh t¹o ra kh¶ n¨ng thu thËp vµ xö lÝ th«ng tin tèt h¬n. C¸c m¹ng m¸y tÝnh l¹i cã thÓ liªn kÕt víi nhau thµnh mét m¹ng lín h¬n, thËm chÝ trªn ph¹m vi toµn cÇu. 5

H×nh 1. M¸y vi tÝnh Tuy nhiªn, kh«ng thÓ ®ång nhÊt tin häc víi m¸y tÝnh vµ cµng kh«ng thÓ ®ång nhÊt viÖc häc tin häc víi viÖc häc sö dông m¸y tÝnh. MÆc dï m¸y tÝnh ngµy cµng cã thªm nh÷ng kh¶ n¨ng k× diÖu, nhng nã vÉn chØ lµ mét c«ng cô lao ®éng do con ngêi s¸ng t¹o ra. §Ó sö dông ®îc c«ng cô lao ®éng nµy, con ngêi cÇn cã kiÕn thøc nhÊt ®Þnh vÒ tin häc, trªn c¬ së ®ã dïng m¸y tÝnh ®Ó trî gióp c«ng viÖc cña m×nh. 3. ThuËt ng÷ \"Tin häc\" Trong tiÕng Ph¸p, Tin häc lµ Informatique. Ngêi ch©u ¢u trong c¸c héi th¶o, Ên phÈm khoa häc sö dông thuËt ng÷ ®ã díi d¹ng Anh ho¸ lµ Informatics. Cßn ngêi MÜ l¹i quen dïng thuËt ng÷ Computer Science (khoa häc m¸y tÝnh). Trªn thÕ giíi cã nhiÒu ®Þnh nghÜa kh¸c nhau vÒ tin häc. Sù kh¸c nhau chØ ë ph¹m vi c¸c lÜnh vùc ®îc coi lµ tin häc cßn vÒ néidung lµ thèng nhÊt. Tin häc lµ mét ngµnh khoa häc cã môc tiªu lµ ph¸t triÓn vµ sö dông m¸y tÝnh ®iÖn tö ®Ó nghiªn cøu cÊu tróc, tÝnh chÊt cña th«ng tin, phƬng ph¸p thu thËp, lÆu tr÷, t×m kiÕm, biÕn ®æi, truyÒn th«ng tin vµ øng dông vµo c¸c lÜnh vùc kh¸c nhau cña ®êi sèng x· héi. C©u hái vµ bµi tËp 1. H·y nãi vÒ mét ®Æc ®iÓm næi bËt cña sù ph¸t triÓn trong x· héi hiÖn nay. 2. V× sao tin häc ®wîc h×nh thµnh vµ ph¸t triÓn thµnh mét ngµnh khoa häc? 3. H·y nªu nh÷ng ®Æc tÝnh wu viÖt cña m¸y tÝnh. 4. H·y cho biÕt viÖc nghiªn cøu chÕ t¹o m¸y tÝnh cã thuéc lÜnh vùc tin häc hay kh«ng. 5. H·y nªu mét vÝ dô mµ m¸y tÝnh kh«ng thÓ thay thÕ con ngwêi trong viÖc xö lÝ th«ng tin. 6

†2. Th«ng tin v d÷ liÖu 1. Kh¸i niÖm th«ng tin vµ d÷ liÖu Thùc ra kh«ng cã sù kh¸c biÖt nhiÒu gi÷a kh¸i niÖm th«ng tin ®îc hiÓu trong ®êi sèng x· héi vµ kh¸i niÖm th«ng tin trong tin häc. Tríc mçi thùc thÓ (sù vËt, sù kiÖn) tån t¹i kh¸ch quan, con ngêi lu«n muèn biÕt râ vÒ nã cµng nhiÒu cµng tèt. Sù hiÓu biÕt ®ã cµng Ýt th× con ngêi cµng khã x¸c ®Þnh thùc thÓ ®ã. Nh÷ng hiÓu biÕt cã thÓ cã ®îc vÒ mét thùc thÓ nµo ®ã ®îc gäi lµ th«ng tin vÒ thùc thÓ ®ã. VÝ dô, khi ®äc lêi nhËn xÐt cña c« gi¸o chñ nhiÖm: \"Em Ngäc Hµ ngoan, ch¨m chØ vµ häc giái\" ghi trong \"Sæ liªn l¹c\", bè mÑ cña Ngäc Hµ cã thªm th«ng tin vÒ con m×nh. Muèn ®a th«ng tin vµo m¸y tÝnh, con ngêi ph¶i t×m c¸ch biÓu diÔn th«ng tin sao cho m¸y tÝnh cã thÓ nhËn biÕt vµ xö lÝ ®îc. Trong tin häc, d÷ liÖu lµ th«ng tin ®· ®îc ®a vµo m¸y tÝnh. 2. §¬n vÞ ®o lyîng th«ng tin Ta kh«ng chØ dõng l¹i ë mét quan niÖm ®Þnh tÝnh vÒ th«ng tin nh trªn mµ cßn cho th«ng tin mét quan niÖm ®Þnh lîng. Mçi sù vËt hay sù kiÖn ®Òu hµm chøa mét lîng th«ng tin. Muèn nhËn biÕt mét ®èi tîng nµo ®ã, ta ph¶i biÕt ®ñ lîng th«ng tin vÒ nã. T¬ng tù, ®Ó m¸y nhËn biÕt mét ®èi tîng nµo ®ã, ta còng ph¶i cung cÊp cho m¸y ®ñ lîng th«ng tin vÒ ®èi tîng nµy. §¬n vÞ c¬ b¶n ®o lîng th«ng tin lµ bit. §ã lµ lîng th«ng tin võa ®ñ ®Ó x¸c ®Þnh ch¾c ch¾n mét tr¹ng th¸i cña mét sù kiÖn cã hai tr¹ng th¸i víi kh¶ n¨ng xuÊt hiÖn nh nhau. VÝ dô, xÐt viÖc tung ngÉu nhiªn ®ång xu cã hai mÆt hoµn toµn c©n xøng víi kh¶ n¨ng xuÊt hiÖn cña mçi mÆt lµ nh nhau. NÕu kÝ hiÖu mét mÆt cña ®ång xu 7

lµ 1 vµ mÆt kia lµ 0 th× sù xuÊt hiÖn kÝ hiÖu 1 hay 0 sau khi tung ®ång xu cho ta mét lîng th«ng tin lµ 1 bit. Trong tin häc, thuËt ng÷ bit thêng dïng ®Ó chØ phÇn nhá nhÊt cña bé nhí m¸y tÝnh ®Ó lu tr÷ mét trong hai kÝ hiÖu, ®îc sö dông ®Ó biÓu diÔn th«ng tin trong m¸y tÝnh, lµ 0 vµ1. VÝ dô, gi¶ sö cã d·y t¸m bãng ®Ìn ®îc ®¸nh sè tõ 1 ®Õn 8, trong ®ã mét sè bãng ®Ìn s¸ng vµ mét sè kh¸c t¾t, ch¼ng h¹n c¸c bãng ®Ìn thø hai, ba, n¨m vµ t¸m s¸ng, c¸c bãng cßn l¹i t¾t (h. 2). NÕu ta sö dông kÝ hiÖu 0 vµ 1 ®Ó biÓu diÔn t¬ng øng tr¹ng th¸i t¾t vµ s¸ng cña mçi bãng ®Ìn th× th«ng tin vÒ d·y t¸m bãng ®Ìn trªn ®îc biÓu diÔn b»ng d·y t¸m bit 01101001. H×nh 2 §Ó lu tr÷ d·y bit ®ã, ta cÇn dïng Ýt nhÊt t¸m bit cña bé nhí m¸y tÝnh. Ngoµi ®¬n vÞ bit nãi trªn, ®¬n vÞ ®o th«ng tin thêng dïng lµ byte (®äc lµ bai) vµ 1 byte b»ng 8 bit. Ngêi ta cßn dïng c¸c ®¬n vÞ béi cña byte nh b¶ng díi ®©y: KÝ hiÖu §äc l† §é lín KB Ki-l«-bai 1024 byte MB Mª-ga-bai 1024 KB GB Gi-ga-bai 1024 MB TB Tª-ra-bai 1024 GB PB Pª-ta-bai 1024 TB 3. C¸c d¹ng th«ng tin ThÕ giíi quanh ta rÊt ®a d¹ng nªn cã nhiÒu d¹ng th«ng tin kh¸c nhau vµ mçi d¹ng cã mét sè c¸ch thÓ hiÖn kh¸c nhau. Cã thÓ ph©n lo¹i th«ng tin thµnh lo¹i sè (sè nguyªn, sè thùc,...) vµ lo¹i phi sè (v¨n b¶n, h×nh ¶nh, ©m thanh,...). Díi ®©y lµ mét sè d¹ng th«ng tin lo¹i phi sè thêng gÆp trong cuéc sèng. a) D¹ng v¨n b¶n: Lµ d¹ng quen thuéc nhÊt vµ thêng gÆp trªn c¸c ph¬ng tiÖn mang th«ng tin nh: Tê b¸o, cuèn s¸ch, vë ghi bµi, tÊm bia,... (h. 3). 8

H×nh 3. Ch÷ kh¾c trªn ®¸ ë Mü S¬n – th«ng tin d¹ng v¨n b¶n b) D¹ng h×nh ¶nh: Bøc tranh vÏ, bøc ¶nh chôp, b¶n ®å, b¨ng h×nh,... lµ nh÷ng ph¬ng tiÖn mang th«ng tin d¹ng h×nh ¶nh (h. 4). H×nh 4. BiÓn b¸o  th«ng tin d¹ng h×nh ¶nh c) D¹ng ©m thanh: TiÕng nãi con ngêi, tiÕng sãng biÓn, tiÕng ®µn, tiÕng chim hãt,... lµ th«ng tin d¹ng ©m thanh (h. 5). B¨ng tõ, ®Üa tõ,... cã thÓ dïng lµm vËt chøa th«ng tin d¹ng ©m thanh. H×nh 5. TiÕng ®„n T’ŕng – th«ng tin d¹ng ©m thanh Víi sù ph¸t triÓn cña khoa häc  kÜ thuËt, trong t¬ng lai con ngêi sÏ cã kh¶ n¨ng thu thËp, lu tr÷ vµ xö lÝ c¸c d¹ng th«ng tin míi kh¸c. 9

4. M· ho¸ th«ng tin trong m¸y tÝnh Muèn m¸y tÝnh xö lÝ ®îc, th«ng tin ph¶i ®îc biÕn ®æi thµnh mét d·y bit. C¸ch biÕn ®æi nh vËy ®îc gäi lµ mét c¸ch m· ho¸ th«ng tin. Ch¼ng h¹n, th«ng tin vÒ tr¹ng th¸i t¸m bãng ®Ìn trong vÝ dô tríc ®îc biÓu diÔn thµnh d·y t¸m bit lµ m· ho¸ cña th«ng tin ®ã trong m¸y tÝnh. Th«ng tin gèc Th«ng tin m· ho¸ H×nh 6. M· ho¸ th«ng tin trong m¸y tÝnh VÝ dô, xÐt viÖc m· ho¸ th«ng tin d¹ng v¨n b¶n. Mçi v¨n b¶n lµ mét d·y c¸c kÝ tù viÕt liªn tiÕp theo nh÷ng quy t¾c nµo ®ã. C¸c kÝ tù bao gåm c¸c ch÷ c¸i thêng vµ hoa nh a, b, c,..., z, A, B, C,..., Z; c¸c ch÷ sè thËp ph©n 0, 1, 2,..., 9 vµ mét sè kÝ hiÖu kh¸c nh c¸c dÊu phÐp to¸n, c¸c dÊu ng¾t c©u,... §Ó m· ho¸ th«ng tin d¹ng v¨n b¶n, ta chØ cÇn m· ho¸ c¸c kÝ tù. Bé m· ASCII (®äc lµ A-ski, viÕt t¾t cña American Standard Code for Information Interchange – M· chuÈn cña MÜ dïng trong trao ®æi th«ng tin) sö dông t¸m bit ®Ó m· ho¸ kÝ tù (xem Phô lôc 1. Bé m· ASCII c¬ së). Trong bé m· nµy, c¸c kÝ tù ®îc ®¸nh sè tõ 0 ®Õn 255 vµ c¸c sè hiÖu nµy ®îc gäi lµ m· ASCII thËp ph©n cña kÝ tù. VÝ dô, kÝ tù \"A\" cã m· ASCII thËp ph©n lµ 65 vµ kÝ tù \"a\" cã m· ASCII thËp ph©n lµ 97. Mçi sè nguyªn trong ph¹m vi tõ 0 ®Õn 255 ®Òu cã thÓ viÕt trong hÖ nhÞ ph©n víi 8 ch÷ sè (8 bit). NÕu kÝ tù cã m· ASCII thËp ph©n lµ N, d·y 8 bit biÓu diÔn N chÝnh lµ m· ho¸ cña kÝ tù ®ã trong m¸y tÝnh. VÝ dô, m· ASCII cña kÝ tù \"A\" lµ 01000001. Bé m· ASCII chØ m· ho¸ ®îc 256 (= 28) kÝ tù, cha ®ñ ®Ó m· ho¸ tÊt c¶ c¸c b¶ng ch÷ c¸i cña c¸c ng«n ng÷ trªn thÕ giíi. Do ®ã víi m· ASCII, viÖc trao ®æi th«ng tin trªn toµn cÇu cßn khã kh¨n. Bëi vËy, ngêi ta ®· x©y dùng bé m· Unicode sö dông 16 bit ®Ó m· ho¸. Víi bé m· Unicode ta cã thÓ m· ho¸ ®îc 65536 (= 216) kÝ tù kh¸c nhau, cho phÐp thÓ hiÖn trong m¸y tÝnh v¨n b¶n cña tÊt c¶ c¸c ng«n ng÷ trªn thÕ giíi b»ng mét bé m·. HiÖn nay, níc ta ®· chÝnh thøc sö dông bé m· Unicode nh mét bé m· chung ®Ó thÓ hiÖn c¸c v¨n b¶n hµnhchÝnh. 10

§Ó con ngêi cã thÓ biÕt th«ng tin ®îc lu tr÷ trong m¸y, m¸y tÝnh ph¶i biÕn ®æi th«ng tin ®· m· ho¸ thµnh d¹ng quen thuéc nh v¨n b¶n, ©m thanh hoÆc h×nh ¶nh. 5. BiÓu diÔn th«ng tin trong m¸y tÝnh D÷ liÖu trong m¸y tÝnh lµ th«ng tin ®· ®îc m· ho¸ thµnh d·y bit. Trong môc nµy, ta t×m hiÓu c¸ch biÓu diÔn th«ng tin lo¹i sè vµ phi sè trong m¸y tÝnh. a) Th«ng tin lo¹i sè x HÖ ®Õm HÖ ®Õm ®îc hiÓu nh tËp c¸c kÝ hiÖu vµ quy t¾c sö dông tËp kÝ hiÖu ®ã ®Ó biÓu diÔn vµ x¸c ®Þnh gi¸ trÞ c¸c sè. Cã hÖ ®Õm phô thuéc vÞ trÝ vµ hÖ ®Õm kh«ng phô thuéc vÞ trÝ. HÖ ®Õm La M· lµ hÖ ®Õm kh«ng phô thuéc vÞ trÝ. TËp c¸c kÝ hiÖu trong hÖ nµy gåm c¸c ch÷ c¸i: I, V, X, L, C, D, M. Mçi kÝ hiÖu cã mét gi¸ trÞ, cô thÓ: I = 1; V = 5; X = 10; L = 50; C = 100; D = 500; M = 1000. Trong hÖ ®Õm nµy, gi¸ trÞ cña kÝ hiÖu kh«ng phô thuéc vÞ trÝ cña nã trong biÓu diÔn. VÝ dô, X trong c¸c biÓu diÔn XI (11) vµ IX (9) ®Òu cã cïng gi¸ trÞ lµ10. C¸c hÖ ®Õm thêng dïng lµ c¸c hÖ ®Õm phô thuéc vÞ trÝ. BÊt k× mét sè tù nhiªn b nµo lín h¬n 1 ®Òu cã thÓ chän lµm c¬ sè cho mét hÖ ®Õm. Trong c¸c hÖ ®Õm nµy, sè lîng c¸c kÝ hiÖu ®îc sö dông b»ng c¬ sè cña hÖ ®Õm ®ã. C¸c kÝ hiÖu ®îc dïng cho hÖ ®Õm ®ã cã c¸c gi¸ trÞ t¬ng øng: 0, 1,..., b 1. HÖ thËp ph©n (hÖ c¬ sè 10) sö dông tËp kÝ hiÖu gåm 10 ch÷ sè: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Gi¸ trÞ cña mçi ch÷ sè phô thuéc vµo vÞ trÝ cña nã trong biÓu diÔn. VÝ dô, trong sè 545, ch÷ sè 5 ë hµng ®¬n vÞ chØ 5 ®¬n vÞ, trong khi ®ã ch÷ sè 5 ë hµng tr¨m chØ 500 ®¬n vÞ. Gi¸ trÞ sè trong hÖ thËp ph©n ®îc x¸c ®Þnh theo quy t¾c: mçi ®¬n vÞ ë mét hµng bÊt k× cã gi¸ trÞ b»ng 10 ®¬n vÞ cña hµng kÕ cËn bªn ph¶i. VÝ dô: 536,4 = 5 u 102 + 3 u 101 + 6 u 100 + 4 u 101. Trong hÖ ®Õm c¬ sè b, gi¶ sö sè N cã biÓu diÔn: dndn1dn2...d1d0, d1d 2...dm 11

trong ®ã n + 1 lµ sè c¸c ch÷ sè bªn tr¸i, m lµ sè c¸c ch÷ sè bªn ph¶i dÊu ph©n chia phÇn nguyªn vµ phÇn ph©n cña sè N vµ c¸c di tho¶ m·n ®iÒu kiÖn 0 d di < b. Khi ®ã gi¸ trÞ cña sè N ®îc tÝnh theo c«ng thøc: N = dnbn + dn1bn1 + ... + d0b0 + d1b1 + ... + dmbm. Ghi chó : Khi cÇn ph©n biÖt sè ®xîc biÓu diÔn ë hÖ ®Õm nµo ngxêi ta viÕt c¬ sè lµm chØ sè dxíi cña sè ®ã. VÝ dô: 1012 (hÖ c¬ sè 2), 516 (hÖ c¬ sè 16). x C¸c hÖ ®Õm thÆêng dïng trong tin häc Ngoµi hÖ thËp ph©n, trong tin häc thêng dïng hai hÖ ®Õm sau: HÖ nhÞ ph©n (hÖ c¬ sè 2) chØ dïng hai kÝ hiÖu lµ ch÷ sè 0 vµ ch÷ sè 1. VÝ dô: 1012 = 1u22 + 0u21 + 1u20 = 510. HÖ c¬ sè m~êi s¸u, cßn gäi lµ hÖ hexa, sö dông c¸c kÝ hiÖu: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, trong ®ã A, B, C, D, E, F cã c¸c gi¸ trÞ t¬ng øng lµ 10, 11, 12, 13, 14, 15 trong hÖ thËp ph©n. VÝ dô: 1BE16 = 1 u16211 u161 + 14u160 = 44610. x BiÓu diÔn sè nguyªn Sè nguyªn cã thÓ cã dÊu hoÆc kh«ng dÊu. Ta cã thÓ chän 1 byte, 2 byte, 4 byte,... ®Ó biÓu diÔn sè nguyªn. Mçi c¸ch chän t¬ng øng víi mét ph¹m vi gi¸ trÞ cã thÓ biÓu diÔn ®îc. XÐt viÖc biÓu diÔn sè nguyªn b»ng mét byte. Mét byte cã 8 bit, mçi bit lµ 0 hoÆc 1. C¸c bit cña mét byte ®îc ®¸nh sè tõ ph¶i sang tr¸i b¾t ®Çu tõ 0. Ta gäi bèn bit sè hiÖu nhá lµ c¸c bit thÊp, bèn bit sè hiÖu lín lµ c¸c bit cao (h. 7). bit 7 bit 6 bit 5 bit 4 bit 3 bit 2 bit 1 bit 0 c¸c bit cao c¸c bit thÊp H×nh 7. BiÓu diÔn sè nguyªn Mét c¸ch biÓu diÔn sè nguyªn cã dÊu: dïng bit cao nhÊt thÓ hiÖn dÊu víi quy íc 1 lµ dÊu ©m, 0 lµ dÊu d¬ng vµ b¶y bit cßn l¹i biÓu diÔn gi¸ trÞ tuyÖt ®èi cña sè viÕt díi d¹ng nhÞ ph©n. Theo c¸ch ®ã, mét byte biÓu diÔn ®îc sè nguyªn trong ph¹mvi tõ 127 ®Õn 127. §èi víi sè nguyªn kh«ng ©m, toµn bé t¸m bit ®îc dïng ®Ó biÓu diÔn gi¸ trÞ sè, mét byte biÓu diÔn ®îc c¸c sè nguyªn kh«ng ©m trong ph¹m vi tõ 0 ®Õn 255. 12

x BiÓu diÔn sè thùc C¸ch viÕt sè thùc th«ng thêng trong tin häc kh¸c víi c¸ch viÕt ta thêng dïng trong to¸n häc: dÊu phÈy (,) ng¨n c¸ch gi÷a phÇn nguyªn vµ phÇn ph©n ®îc thay b»ng dÊu chÊm (.) vµ kh«ng dïng dÊu nµo ®Ó ph©n c¸ch nhãm ba ch÷ sè liÒn nhau. VÝ dô, trong to¸n ta thêng viÕt 13 456,25 nhng khi lµm viÖc víi m¸y tÝnh, ta ph¶i viÕt 13456.25. Mäi sè thùc ®Òu cã thÓ biÓu diÔn ®îc díi d¹ng rMu10rK (®îc gäi lµ d¹ng dÊu phÈy ®éng), trong ®ã 0,1dM<1, M ®îc gäi lµ phÇn ®Þnh trÞ vµ K lµ mét sè nguyªn kh«ng ©m ®îc gäi lµ phÇn bËc. VÝ dô: Sè 13 456,25 ®îc biÓu diÔn díi d¹ng 0.1345625u105. M¸y tÝnh sÏ lu c¸c th«ng tin gåm dÊu cña sè, phÇn ®Þnh trÞ, dÊu cña phÇn bËc vµ phÇn bËc. b) Th«ng tin lo¹i phi sè x V¨n b¶n Nh ®· nãi ë phÇn trªn, m¸y tÝnh cã thÓ dïng mét d·y bit ®Ó biÓu diÔn mét kÝ tù, ch¼ng h¹n m· ASCII cña kÝ tù ®ã. §Ó biÓu diÔn mét x©u kÝ tù (d·y c¸c kÝ tù), m¸y tÝnh cã thÓ dïng mét d·y byte, mçi byte biÓu diÔn mét kÝ tù theo thø tù tõ tr¸i sang ph¶i. VÝ dô, d·y ba byte 01010100 01001001 01001110 biÓu diÔn x©u kÝ tù \"TIN\". x C¸c d¹ng kh¸c HiÖn nay, viÖc t×m c¸ch biÓu diÔn hiÖu qu¶ c¸c d¹ng th«ng tin lo¹i phi sè nh ©m thanh, h×nh ¶nh,... rÊt ®îc quan t©m v× c¸c th«ng tin lo¹i nµy ngµy cµng phæ biÕn. §Ó xö lÝ ©m thanh, h×nh ¶nh, ta còng ph¶i m· ho¸ chóng thµnh c¸c d·y bit. C¸c thµnh tùu trong lÜnh vùc nµy ®· vµ ®ang n©ng cao chÊt lîng cuéc sèng. Ch¼ng h¹n, hai ngêi ë xa nhau vÉn cã thÓ trß chuyÖn, thËm chÝ cã thÓ nh×n thÊy h×nh ¶nh cña nhau. Nguyªn lÝ m· ho¸ nhÞ ph©n Th«ng tin cã nhiÒu d¹ng kh¸c nhau nhÆ sè, v¨n b¶n, h×nh ¶nh, ©m thanh,... Khi ®Æa vµo m¸y tÝnh, chóng ®Òu ®Æîc biÕn ®æi thµnh d¹ng chung  d·y bit. D·y bit ®ã lµ m· nhÞ ph©n cña th«ng tin mµ nã biÓu diÔn. 13

Bµi ®äc thªm 1 BiÓu diÔn h×nh ¶nh vµ ©m thanh 1. BiÓu diÔn h×nh ¶nh §Ó ®xa h×nh ¶nh vµo trong m¸y tÝnh, cÇn m· ho¸ nã dxíi d¹ng bit. Cã hai c¸ch m· ho¸ h×nh ¶nh th«ng dông lµ bitmap vµ vect¬. ¶nh bitmap (b¶n ®å bit) thÓ hiÖn ¶nh theo tõng ®iÓm trªn mét lxíi ®iÓm. Mçi ®iÓm lµ mét « trªn lxíi. Ngoµi ra, mµu còng ®xîc m· ho¸. VÝ dô, trªn h×nh 8 dxíi ®©y, ¶nh bªn ph¶i lµ ¶nh bitmap cña phÇn ¶nh thuéc h×nh vu«ng trong ¶nh bªn tr¸i. H×nh 8. BiÓu diÔn h×nh ¶nh Th«ng thxêng c¸c ¶nh do c¸c vÖ tinh chôp göi vÒ, ¶nh phong c¶nh, ch©n dung ®Òu cã thÓ sö dông c¸ch m· ho¸ kiÓu bitmap. Ta cã thÓ ®xa mét ¶nh bÊt k× vµo m¸y tÝnh dxíi d¹ng bitmap b»ng m¸y quÐt (Scanner), m¸y ¶nh sè (Digital Camera), m¸y quay video sè (Digital Video Camera),... M· ho¸ ¶nh b»ng bitmap ®ßi hái ph¶i lxu mét lxîng lín d÷ liÖu. §Ó tiÕt kiÖm bé nhí lxu tr÷ thxêng ph¶i sö dông c¸c kÜ thuËt nÐn ¶nh, khi cÇn xem ¶nh th× kh«i phôc ¶nh dxíi d¹ng bitmap. ¶nh vect¬ thÓ hiÖn ¶nh cã thµnh phÇn lµ c¸c ®iÓm rêi r¹c, c¸c ®xêng hoÆc h×nh thÓ hiÖn b»ng c¸c ®xêng biªn nhx c¸c b¶n vÏ kiÕn tróc, c¸c b¶n vÏ kÜ thuËt,… D÷ liÖu cÇn lxu tr÷ lµ th«ng tin vÒ c¸c thµnh phÇn cña ¶nh. VÝ dô, ®èi víi mét ®o¹n th¼ng chØ cÇn lxu tr÷ to¹ ®é hai ®Çu mót, ®èi víi ®xêng trßn th× lxu to¹ ®é t©m vµ b¸n kÝnh. 14

Biªn ®é2. BiÓu diÔn ©m thanh §Ó ®xa ©m thanh vµo m¸y tÝnh ta còng ph¶i m· ho¸ nã thµnh d¹ng bit. Cã nhiÒu c¸ch ®Ó thùc hiÖn ®iÒu ®ã, ch¼ng h¹n xÊp xØ dao ®éng sãng ©m b»ng d·y c¸c byte thÓ hiÖn biªn ®é dao ®éng tx¬ng øng theo tõng kho¶ng thêi gian b»ng nhau. Trªn h×nh 9 minh ho¹ c¸ch lxu tr÷ xÊp xØ dao ®éng sãng ©m, theo ®ã sÏ lxu l¹i c¸c gi¸ trÞ nhx sau: -5 3 4 4 2 2 3 6 8 7 3 -6 Thêi gian H×nh 9. BiÓu diÔn ©m thanh Khi ph¸t l¹i, c¸c sãng ©m sÏ ®xîc kh«i phôc víi mét sai kh¸c nhÊt ®Þnh. 15

Bˆi tËp vˆ thùc hˆnh 1 lˆm quen víi th«ng tin vˆ m· ho¸ th«ng tin 1. Môc ®Ých, yªu cÇu x Cñng cè hiÓu biÕt ban ®Çu vÒ tin häc, m¸y tÝnh. x Sö dông bé m· ASCII ®Ó m· ho¸ x©u kÝ tù, sè nguyªn. x ViÕt ®îc sè thùc díi d¹ng dÊu phÈy ®éng. 2. Néi dung a) Tin häc, m¸y tÝnh a1) H·y chän nh÷ng kh¼ng ®Þnh ®óng trong c¸c kh¼ng ®Þnh sau: (A) M¸y tÝnh cã thÓ thay thÕ hoµn toµn cho con ngêi trong lÜnh vùc tÝnh to¸n; (B) Häc tin häc lµ häc sö dông m¸y tÝnh; (C) M¸y tÝnh lµ s¶n phÈm trÝ tuÖ cña con ngêi; (D) Mét ngêi ph¸t triÓn toµn diÖn trong x· héi hiÖn ®¹i kh«ng thÓ thiÕu hiÓu biÕt vÒ tin häc. a2) Trong c¸c ®¼ng thøc sau ®©y, nh÷ng ®¼ng thøc nµo lµ ®óng? (A) 1 KB = 1000 byte; (B) 1 KB = 1024 byte; (C) 1 MB = 1000000 byte. a3) Cã 10 häc sinh xÕp hµng ngang ®Ó chôp ¶nh. Em h·y dïng 10 bit ®Ó biÓu diÔn th«ng tin cho biÕt mçi vÞ trÝ trong hµng lµ b¹n nam hay b¹n n÷. b) Sö dông bé m· ASCII (xem phô lôc) ®Ó m· ho¸ vµ gi¶i m· b1) ChuyÓn c¸c x©u kÝ tù sau thµnh d¹ng m· nhÞ ph©n: \"VN\", \"Tin\". b2) D·y bit \"01001000 01101111 01100001\" t¬ng øng lµ m· ASCII cña d·y kÝ tù nµo? c) BiÓu diÔn sè nguyªn vµ sè thùc c1) §Ó m· ho¸ sè nguyªn –27 cÇn dïng Ýt nhÊt bao nhiªu byte? 16

c2) ViÕt c¸c sè thùc sau ®©y díi d¹ng dÊu phÈy ®éng: 11005; 25,879; 0,000984. C¸c thuËt ng÷ chÝnh Bit; Byte; KB; MB; M· ho¸ th«ng tin; Bé m· ASCII; Bé m· Unicode; D÷ liÖu; HÖ ®Õm nhÞ ph©n; HÖ ®Õm hexa; M· ho¸ nhÞ ph©n. C©u hái vµ bµi tËp 1. H·y nªu mét vµi vÝ dô vÒ th«ng tin. Víi mçi th«ng tin ®ã h·y cho biÕt d¹ng cña nã. 2. H·y ph©n biÖt bé m· ASCII vµ bé m· Unicode. 3. HÖ ®Õm c¬ sè 16 sö dông c¸c kÝ hiÖu nµo? 4. H·y nªu c¸ch biÓu diÔn sè nguyªn, sè thùc trong m¸y tÝnh. 5. Ph¸t biÓu \"Ng«n ng÷ m¸y tÝnh lµ ng«n ng÷ nhÞ ph©n (chØ dïng hai kÝ hiÖu 0 vµ 1)\" lµ ®óng hay sai? H·y gi¶i thÝch. Bµi ®äc thªm 2 biÓu diÔn sè trong c¸c hÖ ®Õm kh¸c nhau 1. ChuyÓn ®æi biÓu diÔn sè ë hÖ thËp ph©n sang hÖ ®Õm c¬ sè kh¸c §Ó chuyÓn ®æi biÓu diÔn mét sè ë hÖ thËp ph©n sang hÖ ®Õm c¬ sè kh¸c, trxíc hÕt ta t¸ch phÇn nguyªn vµ phÇn ph©n råi tiÕn hµnh chuyÓn ®æi tõng phÇn, sau ®ã ghÐp l¹i ®Ó cã kÕt qu¶ cÇn t×m. a) ChuyÓn ®æi biÓu diÔn phÇn nguyªn Cho N lµ sè tù nhiªn vµ b lµ c¬ sè cña hÖ ®Õm. Gi¶ sö gi¸ trÞ cña N ®xîc tÝnh theo c«ng thøc: N = dnbn + dn-1bn1 + ... + d0 (1) V× 0 d d0 < b nªn khi chia N cho b th× phÇn dx cña phÐp chia ®ã lµ d0 cßn thx¬ng sè N1 sÏ lµ: N1 = dnbn1 + dn-1bn2 + ... + d1 (2) 17

Tx¬ng tù, d1 chÝnh lµ phÇn dx cña phÐp chia N1 cho b. Gäi N2 lµ thx¬ng cña phÐp chia ®ã. Qu¸ tr×nh chia nhx vËy ®xîc thùc hiÖn liªn tiÕp vµ ta sÏ lÇn lxît nhËn ®xîc gi¸ trÞ c¸c di. Qu¸ tr×nh nµy sÏ dõng l¹i khi nhËn ®xîc thx¬ng sè b»ng 0. §Ó cã biÓu diÔn cÇn t×m, c¸c phÇn dx thu ®xîc cÇn s¾p xÕp theo thø tù tõ tr¸i sang ph¶i lµ dn...d0. VÝ dô. 5210 = ?2 = ?16. Sau khi thùc hiÖn theo c¸ch trªn ta cã: 5210 = 1101002 vµ 5210 = 3416. b) ChuyÓn ®æi biÓu diÔn phÇn ph©n Cho N' lµ phÇn ph©n (phÇn sau dÊu phÈy) cña mét sè vµ b lµ c¬ sè cña hÖ ®Õm. Gi¶ sö gi¸ trÞ N' ®xîc tÝnh theo c«ng thøc: N' = d1 b1 + d2 b2 + ... + dm bm. (1') Nh©n hai vÕ cña (1') víi b, ta thu ®xîc: N'1 = d1 + d2 b1 + ... + dm b(m1). Ta nhËn thÊy d1 chÝnh lµ phÇn nguyªn cña kÕt qu¶ phÐp nh©n, cßn phÇn ph©n cña kÕt qu¶ lµ: N'2 = d2 b1 + ... + dm b(m1). (2') LÆp l¹i phÐp nh©n nhx trªn ®èi víi (2'), ta thu ®xîc d2 lµ phÇn nguyªn. Thùc hiÖn liªn tiÕp phÐp nh©n theo c¸ch trªn, cuèi cïng thu ®xîc d·y d1 d2 d3..., trong ®ã 0 d di < b. VÝ dô. 0,6787510 = ?2. Thùc hiÖn c¸c phÐp nh©n theo c¸ch trªn, ta cã kÕt qu¶: 0,6787510 = 0,101011011...2. Còng thùc hiÖn theo c¸ch tx¬ng tù, ta cã: 0,843510 = 0,D7EF...16. 2. ChuyÓn ®æi biÓu diÔn sè gi÷a hÖ nhÞ ph©n vµ hÖ hexa HÖ nhÞ ph©n vµ hÖ hexa lµ hai hÖ ®Õm thxêng dïng trong tin häc. V× 16 lµ luü thõa cña 2 (16 = 24) nªn viÖc chuyÓn ®æi biÓu diÔn sè gi÷a hai hÖ ®Õm ®ã ®xîc thùc hiÖn dÔ dµng. §Ó chuyÓn ®æi biÓu diÔn sè tõ hÖ nhÞ ph©n sang hÖ hexa ta ¸p dông quy t¾c sau: Gép c¸c ch÷ sè nhÞ ph©n thµnh tõng nhãm bèn ch÷ sè vÒ hai phÝa kÓ tõ vÞ trÝ ph©n c¸ch phÇn nguyªn vµ phÇn ph©n (c¸c ch÷ sè thiÕu nÕu cã ®xîc thay thÕ b»ng ch÷ sè 0). Thay mçi nhãm bèn ch÷ sè nhÞ ph©n bëi mét kÝ hiÖu tx¬ng øng ë hÖ hexa. VÝ dô. 1011100101,112 =?16. Gép thµnh tõng nhãm bèn ch÷ sè nhÞ ph©n: 0010 1110 0101,11002. Thay mçi nhãm bèn ch÷ sè nhÞ ph©n b»ng mét kÝ hiÖu ë hÖ hexa tx¬ng øng: 2, E, 5, C. Tõ ®ã ta cã: 1011100101,112 = 2E5,C16. §Ó chuyÓn ®æi biÓu diÔn sè ë hÖ hexa sang hÖ nhÞ ph©n ta chØ cÇn thay tõng kÝ hiÖu ë hÖ hexa b»ng nhãm bèn ch÷ sè tx¬ng øng ë hÖ nhÞ ph©n. VÝ dô. 3,D7EF16 = 0011,1101 0111 1110 11112. 18

†3. Giíi thiÖu vÒ m¸y tÝnh 1. Kh¸i niÖm hÖ thèng tin häc HÖ thèng tin häc dïng ®Ó nhËp, xö lÝ, xuÊt, truyÒn vµ lÆu tr÷ th«ng tin. HÖ thèng tin häc gåm ba thµnh phÇn: x PhÇn cøng (Hardware) gåm m¸y tÝnh vµ mét sè thiÕt bÞ liªn quan; x PhÇn mÒm (Software) gåm c¸c ch¬ng tr×nh. Ch¬ng tr×nh lµ mét d·y lÖnh, mçi lÖnh lµ mét chØ dÉn cho m¸y tÝnh biÕt thao t¸c cÇn thùc hiÖn; x Sù qu¶n lÝ vµ ®iÒu khiÓn cña con ngêi. 2. S¬ ®å cÊu tróc cña mét m¸y tÝnh M¸y tÝnh lµ thiÕt bÞ dïng ®Ó tù ®éng ho¸ qu¸ tr×nh thu thËp, lu tr÷ vµ xö lÝ th«ng tin. Cã nhiÒu lo¹i m¸y tÝnh kh¸c nhau nhng chóng ®Òu cã chung mét s¬ ®å cÊu tróc nh sau: H×nh 10. S¬ ®å cÊu tróc m¸y tÝnh C¸c mòi tªn trong s¬ ®å kÝ hiÖu viÖc trao ®æi th«ng tin gi÷a c¸c bé phËn cña m¸y tÝnh. 19

CÊu tróc chung cña m¸y tÝnh bao gåm: Bé xö lÝ trung t©m, bé nhí trong, c¸c thiÕt bÞ vµo/ra, bé nhí ngoµi. 3. Bé xö lÝ trung t©m (CPU  Central Processing Unit) CPU lµ thµnh phÇn quan träng nhÊt cña m¸y tÝnh, ®ã lµ thiÕt bÞ chÝnh thùc hiÖn vµ ®iÒu khiÓn viÖc thùc hiÖn chƬng tr×nh. H×nh 11. Mét sè lo¹i CPU ChÊt lîng cña m¸y tÝnh phô thuéc nhiÒu vµo chÊt lîng cña CPU (h. 11). CPU gåm hai bé phËn chÝnh: bé ®iÒu khiÓn (CU  Control Unit) vµ bé sè häc/l«gic (ALU  Arithmetic/Logic Unit). Gièng nh mét nh¹c trëng, bé ®iÒu khiÓn kh«ng trùc tiÕp thùc hiÖn ch¬ng tr×nh mµ híng dÉn c¸c bé phËn kh¸c cña m¸y tÝnh lµm ®iÒu ®ã. Bé sè häc/l«gic thùc hiÖn c¸c phÐp to¸n sè häc vµ l«gic, c¸c thao t¸c xö lÝ th«ng tin ®Òu lµ tæ hîp cña c¸c phÐp to¸n nµy. Ngoµi hai bé phËn chÝnh nªu trªn, CPU cßn cã thªm mét sè thµnh phÇn kh¸c nh thanh ghi (Register) vµ bé nhí truy cËp nhanh (Cache). Thanh ghi lµ vïng nhí ®Æc biÖt ®îc CPU sö dông ®Ó lu tr÷ t¹m thêi c¸c lÖnh vµ d÷ liÖu ®ang ®îc xö lÝ. ViÖc truy cËp ®Õn c¸c thanh ghi ®îc thùc hiÖn víi tèc ®é rÊt nhanh. Cache ®ãng vai trß trung gian gi÷a bé nhí vµ c¸c thanh ghi. Tèc ®é truy cËp ®Õn cache lµ kh¸ nhanh, chØ sau tèc ®é truy cËp thanh ghi. 4. Bé nhí trong (Main Memory) Bé nhí trong cßn cã tªn gäi kh¸c lµ bé nhí chÝnh. Bé nhí trong lµ n¬i chƬng tr×nh ®Æîc ®Æa vµo ®Ó thùc hiÖn vµ lµ n¬i lÆu tr÷ d÷ liÖu ®ang ®Æîc xö lÝ. 20

Bé nhí trong cña m¸y tÝnh gåm hai phÇn: ROM (Read Only Memory  Bé nhí chØ ®äc) vµ RAM (Random Access Memory  Bé nhí truy cËp ngÉu nhiªn). ROM (h. 12) chøa mét sè ch¬ng tr×nh H×nh 12. ROM hÖ thèng ®îc h·ng s¶n xuÊt n¹p s½n. D÷ liÖu trong ROM kh«ng xo¸ ®îc. C¸c ch¬ng tr×nh trong ROM thùc hiÖn viÖc kiÓm tra c¸c thiÕt bÞ vµ t¹o sù giao tiÕp ban ®Çu cña m¸y víi c¸c ch¬ng tr×nh mµ ngêi dïng ®a vµo ®Ó khëi ®éng. Khi t¾t m¸y, d÷ liÖu trong ROM kh«ng bÞ mÊt®i. RAM (h. 13) lµ phÇn bé nhí cã thÓ ®äc, ghi d÷ liÖu trong lóc lµm viÖc. Khi t¾t m¸y, d÷ liÖu trong RAM sÏ bÞ mÊt ®i. Bé nhí trong gåm c¸c « nhí ®îc ®¸nh H×nh 13. RAM sè thø tù b¾t ®Çu tõ 0. Sè thø tù cña mét « nhí ®îc gäi lµ ®Þa chØ cña « nhí ®ã. C¸c ®Þa chØ thêng ®îc viÕt trong hÖ hexa. Khi thùc hiÖn ch¬ng tr×nh, m¸y tÝnh truy cËp d÷ liÖu ghi trong « nhí th«ng qua ®Þa chØ cña nã. Víi phÇn lín c¸c m¸y tÝnh, mçi « nhí cã dung lîng 1 byte. HiÖn nay, mçi m¸y tÝnh thêng ®îc trang bÞ bé nhí RAM cã dung lîng tõ 128 MB trë lªn. Mét sè m¸y tÝnh cã thÓ cã bé nhí trong cì hµng Gi-ga-bai. 5. Bé nhí ngoµi (Secondary Memory) Bé nhí ngoµi dïng ®Ó lÆu tr÷ l©u dµi d÷ liÖu vµ hç trî cho bé nhí trong. D÷ liÖu trong RAM chØ tån t¹i khi m¸y tÝnh ®ang ho¹t ®éng, cßn d÷ liÖu ghi ë bé nhí ngoµi cã thÓ tån t¹i ngay c¶ khi t¾t m¸y (kh«ng cßn nguån®iÖn). Bé nhí ngoµi gåm nhiÒu lo¹i nh ®Üa, trèng tõ, b¨ng tõ,... Bé nhí ngoµi cña m¸y tÝnh thÆêng lµ ®Üa cøng, ®Üa mÒm, ®Üa CD, thiÕt bÞ nhí flash. 21

§Ó truy cËp d÷ liÖu trªn ®Üa, m¸y tÝnh cã c¸c æ ®Üa mÒm, æ ®Üa cøng, æ ®Üa CD,... Trong qu¸ tr×nh lµm viÖc, ta cã thÓ ®a c¸c ®Üa mÒm hoÆc ®Üa CD kh¸c nhau vµo æ ®Üa t¬ng øng. §Ó ng¾n gän, ta sÏ ®ång nhÊt æ ®Üa víi ®Üa ®Æt trong ®ã. a) §Üa cøng b) §Üa mÒm c) §Üa CD d) ThiÕt bÞ nhí flash H×nh 14. Bé nhí ngo„i §Üa cøng (h. 14a) thêng ®îc g¾n s½n trong æ ®Üa cøng. §Üa cøng cã dung lîng lín vµ tèc ®é ®äc/ghi rÊt nhanh. M¸y tÝnh thêng cã mét æ ®Üa mÒm dïng ®Ó ®äc/ghi ®Üa mÒm (h. 14b) cã ®êng kÝnh 3,5 inch víi dung lîng 1,44MB. Ngoµi c¸c ®Üa CD (h. 14c) cã mËt ®é ghi d÷ liÖu rÊt cao, hiÖn nay cßn cã thiÕt bÞ nhí flash (h. 14d) lµ mét thiÕt bÞ lu tr÷ d÷ liÖu cã dung lîng lín víi kÝch thíc nhá gän vµ dÔ sö dông. Chó ý: Trong thùc tÕ, thiÕt bÞ nhí flash sö dông cæng giao tiÕp USB nªn thxêng ®xîc gäi lµ USB. Do tiÕn bé vÒ kÜ thuËt, dung lîng cña bé nhí ngoµi ngµy cµng lín vµ kÝch thíc vËt lÝ cña nã ngµy cµng nhá. ViÖc tæ chøc d÷ liÖu ë bé nhí ngoµi vµ viÖc trao ®æi d÷ liÖu gi÷a bé nhí ngoµi víi bé nhí trong ®îc thùc hiÖn bëi hÖ ®iÒu hµnh. 6. ThiÕt bÞ vµo (Input device) ThiÕt bÞ vµo dïng ®Ó ®Æa th«ng tin vµo m¸y tÝnh. Cã nhiÒu lo¹i thiÕt bÞ vµo nh bµn phÝm, chuét, m¸y quÐt, micr«, webcam,... 22

a) Bµn phÝm (Keyboard) H×nh 15 cho ta mét lo¹i bµn phÝm cña m¸y tÝnh. C¸c phÝm chøc n¨ng C¸c phÝm kÝ tù H×nh 15. B„n phÝm m¸y tÝnh C¸c phÝm ®îc chia thµnh nhãm nh nhãm phÝm kÝ tù vµ nhãm phÝm chøc n¨ng,... Th«ng thêng, khi gâ phÝm kÝ tù, kÝ hiÖu trªn mÆt phÝm xuÊt hiÖn trªn mµn h×nh. Trong nhãm phÝm chøc n¨ng, mét sè phÝm cã chøc n¨ng ®· ®îc ngÇm ®Þnh, chøc n¨ng cña mét sè phÝm kh¸c ®îc quy ®Þnh tuú phÇn mÒm cô thÓ. Khi ta gâ mét phÝm nµo ®ã, m· t¬ng øng cña nã ®îc truyÒn vµo m¸y. b) Chuét (Mouse) Nót ph¶i chuét Chuét (h. 16) lµ mét thiÕt bÞ rÊt tiÖn lîi trong Nót tr¸i chuét khi lµm viÖc víi m¸y tÝnh. B»ng c¸c thao t¸c nh¸y nót chuét, ta cã thÓ thùc hiÖn mét lùa chän nµo ®ã H×nh 16. Chuét trong b¶ng chän (menu) ®ang hiÓn thÞ trªn mµn h×nh. Dïng chuét còng cã thÓ thay thÕ cho mét sè H×nh 17. M¸y quÐt thao t¸c bµn phÝm. 23 c) M¸y quÐt (Scanner) M¸y quÐt (h. 17) lµ thiÕt bÞ cho phÐp ®a v¨n b¶n vµ h×nh ¶nh vµo m¸y tÝnh. Cã nhiÒu phÇn mÒm cã kh¶ n¨ng chØnh söa v¨n b¶n hoÆc h×nh ¶nh ®· ®îc ®a vµo trong m¸y.

d) Webcam H×nh 18. Webcam Webcam (h. 18) lµ mét camera kÜ thuËt sè. Khi g¾n vµo m¸y tÝnh, nã cã thÓ thu ®Ó truyÒn trùc tuyÕn h×nh ¶nh qua m¹ng ®Õn nh÷ng m¸y tÝnh ®ang kÕt nèi víi m¸y ®ã. Víi sù ph¸t triÓn cña c«ng nghÖ, c¸c thiÕt bÞ vµo ngµy cµng ®a d¹ng. Ta cã thÓ sö dông m¸y ¶nh sè, m¸y ghi h×nh, m¸y ghi ©m sè ®Ó ®a th«ng tin vµo m¸y tÝnh. 7. ThiÕt bÞ ra (Output device) ThiÕt bÞ ra dïng ®Ó ®Æa d÷ liÖu ra tõ m¸y tÝnh. Cã nhiÒu lo¹i thiÕt bÞ ra nh mµn h×nh, m¸y in,... a) Mµn h×nh (Monitor) Mµn h×nh m¸y tÝnh cã cÊu t¹o t¬ng tù nh mµn h×nh ti vi. Khi lµm viÖc, ta cã thÓ xem mµn h×nh lµ tËp hîp c¸c ®iÓm ¶nh (Pixel), mçi ®iÓm cã thÓ cã ®é s¸ng, mµu s¾c kh¸c nhau. ChÊt lîng cña mµn h×nh ®îc quyÕt ®Þnh bëi c¸c tham sè sau: x §é ph©n gi¶i: Sè lîng ®iÓm ¶nh trªn mµn h×nh, vÝ dô mµn h×nh cã ®é ph©n gi¶i 640 u 480 ®îc hiÓu lµ mµn h×nh ®ã cã thÓ hiÓn thÞ 480 dßng, mçi dßng 640 ®iÓm ¶nh. §é ph©n gi¶i cµng cao th× h×nh ¶nh hiÓn thÞ trªn mµn h×nh cµng mÞn vµ s¾c nÐt; x ChÕ ®é mµu: C¸c mµn h×nh mµu cã thÓ cã 16 hay 256 mµu, thËm chÝ cã hµng triÖu mµu kh¸c nhau. b) M¸y in (Printer) M¸y in cã nhiÒu lo¹i nh m¸y in kim, in phun, in laser (h. 19),... dïng ®Ó in th«ng tin ra giÊy. M¸y in cã thÓ lµ ®en tr¾ng hoÆc mµu. H×nh 19. M¸y in laser c) M¸y chiÕu (Projector) M¸y chiÕu (h. 20a) lµ thiÕt bÞ dïng ®Ó hiÓn thÞ néi dung mµn h×nh m¸y tÝnh lªn mµn ¶nh réng. 24

d) Loa vµ tai nghe (Speaker and Headphone) Loa (h. 20b) vµ tai nghe (h. 20c) lµ c¸c thiÕt bÞ ®Ó ®a d÷ liÖu ©m thanh ra m«i trêng ngoµi. a) M¸y chiÕu b) Loa c) Tai nghe H×nh 20. Mét sè thiÕt bÞ ra e) M«®em (Modem) M«®em lµ thiÕt bÞ dïng ®Ó truyÒn th«ng gi÷a c¸c hÖ thèng m¸y tÝnh th«ng qua ®êng truyÒn, ch¼ng h¹n ®êng ®iÖn tho¹i. Cã thÓ xem m«®em lµ mét thiÕt bÞ hç trî cho c¶ viÖc ®a d÷ liÖu vµo vµ lÊy d÷ liÖu ra tõ m¸y tÝnh. 8. Ho¹t ®éng cña m¸y tÝnh Kh¸c víi c¸c c«ng cô tÝnh to¸n kh¸c, m¸y tÝnh ®iÖn tö cã thÓ thùc hiÖn ®îc mét d·y lÖnh cho tríc (ch¬ng tr×nh) mµ kh«ng cÇn sù tham gia trùc tiÕp cña con ngêi. Nguyªn lÝ ®iÒu khiÓn b»ng ch€¬ng tr×nh M¸y tÝnh ho¹t ®éng theo chƬng tr×nh. T¹i mçi thêi ®iÓm m¸y tÝnh chØ thùc hiÖn ®îc mét lÖnh, tuy nhiªn nã thùc hiÖn rÊt nhanh. M¸y vi tÝnh thùc hiÖn ®îc hµng tr¨m triÖu lÖnh, siªu m¸y tÝnh cßn cã thÓ thùc hiÖn ®îc hµng tØ lÖnh trong mét gi©y. Th«ng tin vÒ mét lÖnh bao gåm: x §Þa chØ cña lÖnh trong bé nhí; x M· cña thao t¸c cÇn thùc hiÖn; x §Þa chØ c¸c « nhí liªn quan. 25

M· thao t¸c chØ dÉn cho m¸y lo¹i thao t¸c (céng sè, so s¸nh sè,...) cÇn thùc hiÖn. PhÇn ®Þa chØ th«ng b¸o cho m¸y biÕt c¸c d÷ liÖu liªn quan ®îc lu tr÷ 뮩u. VÝ dô, viÖc céng hai sè a vµ b cã thÓ m« t¶ b»ng lÖnh, ch¼ng h¹n: \"+\" <a> <b> <t> trong ®ã \"+\" lµ m· thao t¸c, <a>, <b> vµ <t> lµ ®Þa chØ n¬i lu tr÷ t¬ng øng hai sè a, b vµ kÕt qu¶ thao t¸c \"+\". Nguyªn lÝ l€u tr÷ ch€¬ng tr×nh LÖnh ®Æîc ®Æa vµo m¸y tÝnh dÆíi d¹ng m· nhÞ ph©n ®Ó lÆu tr÷, xö lÝ nhÆ nh÷ng d÷ liÖu kh¸c. §Þa chØ cña c¸c « nhí lµ cè ®Þnh nhng néi dung ghi ë ®ã cã thÓ thay ®æi trong qu¸ tr×nh m¸y lµm viÖc. Nguyªn lÝ truy cËp theo ®Þa chØ ViÖc truy cËp d÷ liÖu trong m¸y tÝnh ®Æîc thùc hiÖn th«ng qua ®Þa chØ n¬i lÆu tr÷ d÷ liÖu ®ã. Khi xö lÝ d÷ liÖu, m¸y tÝnh xö lÝ ®ång thêi mét d·y bit chø kh«ng xö lÝ tõng bit. D·y bit nh vËy ®îc gäi lµ tõ m¸y. §é dµi tõ m¸y cã thÓ lµ 8, 16, 32 hay 64 bit phô thuéc kiÕn tróc tõng m¸y. C¸c bé phËn cña m¸y tÝnh ®îc nèi víi nhau bëi c¸c d©y dÉn gäi lµ c¸c tuyÕn (bus). Mçi tuyÕn cã mét sè ®êng dÉn, theo ®ã c¸c gi¸ trÞ bit cã thÓ di chuyÓn trong m¸y. Th«ng thêng sè ®êng dÉn d÷ liÖu trong tuyÕn b»ng ®é dµi tõm¸y. Nguyªn lÝ Ph«n N«i-man M· ho¸ nhÞ ph©n, ®iÒu khiÓn b»ng chƬng tr×nh, lÆu tr÷ chƬng tr×nh vµ truy cËp theo ®Þa chØ t¹o thµnh mét nguyªn lÝ chung gäi lµ nguyªn lÝ Ph«n N«i-man. 26

Nguyªn lÝ trªn do nhµ to¸n häc Ph«n N«i-man J. Von Neumann (J. Von Neumann) ngêi MÜ gèc Hung-ga-ri ph¸t (1903 – 1957) biÓu khi tham gia thiÕt kÕ mét trong c¸c m¸y tÝnh ®iÖn tö ®Çu tiªn nªn ngêi ta lÊy tªn «ng ®Æt tªn cho nguyªn lÝ. Cho ®Õn nay, tuy c¸c ®Æc tÝnh cña m¸y tÝnh thay ®æi nhanh chãng vµ u viÖt h¬n nhiÒu nhng s¬ ®å cÊu tróc chÝnh vµ nguyªn lÝ ho¹t ®éng cña chóng vÒ c¨n b¶n vÉn dùa trªn nguyªn lÝ Ph«n N«i-man. HiÖn nay, t¹i mét sè phßng thÝ nghiÖm ë mét sè níc nh MÜ, NhËt B¶n,... ®ang thùc hiÖn mét vµi dù ¸n nghiªn cøu m« h×nh m¸y tÝnh kh«ng dùa trªn nguyªn lÝ Ph«n N«i-man. Tuy cßn ë giai ®o¹n thö nghiÖm nhng m¸y tÝnh lîng tö, m¸y tÝnh sinh häc ®· cho mét sè kÕt qu¶ kh¶ quan. Bˆi tËp vˆ thùc hˆnh 2 Lˆm quen víi m¸y tÝnh 1. Môc ®Ých, yªu cÇu x Quan s¸t vµ nhËn biÕt ®îc c¸c bé phËn chÝnh cña m¸y tÝnh vµ mét sè thiÕt bÞ kh¸c nh m¸y in, bµn phÝm, chuét, ®Üa, æ ®Üa, cæng USB,...; x Lµm quen vµ tËp mét sè thao t¸c sö dông bµn phÝm, chuét; x NhËn thøc ®îc m¸y tÝnh ®îc thiÕt kÕ rÊt th©n thiÖn víi con ngêi. 2. Néi dung a) Lµm quen víi m¸y tÝnh T¹i phßng m¸y, th«ng qua sù giíi thiÖu vµ híng dÉn cña gi¸o viªn, häc sinh quan s¸t vµ nhËn biÕt: C¸c bé phËn cña m¸y tÝnh vµ mét sè thiÕt bÞ kh¸c nh: æ ®Üa, bµn phÝm, mµn h×nh, m¸y in, nguån ®iÖn, c¸p nèi, cæng USB,... C¸ch bËt/t¾t mét sè thiÕt bÞ nh m¸y tÝnh, mµn h×nh, m¸y in,... C¸ch khëi ®éng m¸y. 27

b) Sö dông bµn phÝm Ph©n biÖt c¸c nhãm phÝm. Ph©n biÖt viÖc gâ mét phÝm vµ gâ tæ hîp phÝm b»ng c¸ch nhÊn gi÷. Gâ mét dßng kÝ tù tuú chän. c) Sö dông chuét Di chuyÓn chuét: Thay ®æi vÞ trÝ cña chuét trªn mÆt ph¼ng. Nh¸y chuét: NhÊn nót tr¸i chuét råi th¶ ngãn tay. Nh¸y ®óp chuét: Nh¸y chuét nhanh hai lÇn liªn tiÕp. KÐo th¶ chuét: NhÊn vµ gi÷ nót tr¸i cña chuét, di chuyÓn con trá chuét ®Õn vÞ trÝ cÇn thiÕt th× th¶ ngãn tay nhÊn gi÷ chuét. C¸c thuËt ng÷ chÝnh HÖ thèng tin häc; Chx¬ng tr×nh; LÖnh; CPU; ROM; RAM; §Üa cøng; §Üa mÒm; §Üa CD; ThiÕt bÞ nhí flash; Bµn phÝm; Chuét; Mµn h×nh; M¸y in; ¤ nhí; §Þa chØ; Nguyªn lÝ Ph«n N«i-man. C©u hái vµ bµi tËp 1. Mét m¸y tÝnh chwa cã phÇn mÒm cã thÓ ho¹t ®éng ®wîc kh«ng? V× sao? 2. H·y giíi thiÖu vµ vÏ s¬ ®å cÊu tróc tæng qu¸t cña m¸y tÝnh. 3. H·y tr×nh bµy chøc n¨ng tõng bé phËn: CPU, bé nhí trong, bé nhí ngoµi, thiÕt bÞ vµo, thiÕt bÞ ra. 4. Em biÕt g× vÒ c¸c kh¸i niÖm: LÖnh, chw¬ng tr×nh, tõ m¸y? 5. Em cã biÕt thiÕt bÞ nµo võa lµ thiÕt bÞ vµo võa lµ thiÕt bÞ ra kh«ng? 6. H·y tr×nh bµy hiÓu biÕt cña em vÒ nguyªn lÝ Ph«n N«i-man. 28

Bµi ®äc thªm 3 LÞch sö ph¸t triÓn cña kÜ thuËt tÝnh to¸n Tõ thêi nguyªn thuû, con Blaise Pascal (1623 1662) ngxêi ®· cã nhu cÇu tÝnh to¸n v„ m¸y tÝnh c¬ khÝ cña «ng ®¬n gi¶n nhx tÝnh, ®Õm. C«ng cô dïng ®Ó xö lÝ th«ng tin cña hä lµ sái, l¸ c©y, ngãn tay. N¨m tr¨m n¨m trxíc C«ng nguyªn, ngxêi Trung Hoa ®· biÕt dïng bµn tÝnh. Chøc n¨ng chñ yÕu cña c¸c c«ng cô tÝnh to¸n th« s¬ ®ã lµ ghi nhí th«ng tin. Cïng víi sù ph¸t triÓn cña loµi ngxêi, nhu cÇu tÝnh to¸n ngµy cµng nhiÒu vµ phøc t¹p. ViÖc ph¸t minh ra hÖ ®Õm thËp ph©n cña ngxêi Ên §é vµo thÕ kØ thø VI trxíc C«ng nguyªn lµ mét bxíc tiÕn quan träng, cã ý nghÜa ®èi víi lÞch sö tÝnh to¸n nãi riªng vµ lÞch sö loµi ngxêi nãi chung. NhiÒu thÕ kØ ®· tr«i qua, viÖc thùc hiÖn c¸c phÐp to¸n víi c¸c sè chñ yÕu lµ b»ng tay hoÆc b»ng c¸c c«ng cô hÕt søc th« s¬ nhx bµn tÝnh cña ngxêi Trung Hoa. M·i ®Õn n¨m 1642 Blaise Pascal, ngxêi Ph¸p, ®· ph¸t minh ra chiÕc m¸y tÝnh c¬ khÝ ®Çu tiªn dùa trªn hÖ thèng m¸y b¸nh r¨ng, cho phÐp thùc hiÖn c¸c phÐp tÝnh céng vµ trõ. Sau ®ã ba mx¬i n¨m, G. Leibnitz, nhµ to¸n häc ngxêi §øc ®· c¶i tiÕn m¸y cña Pascal ®Ó nã cã thÓ thùc hiÖn thªm phÐp nh©n vµ phÐp chia. H¹n chÕ c¬ b¶n cña c¸c m¸y lo¹i nµy lµ chóng chØ thùc hiÖn c¸c phÐp to¸n mét c¸ch riªng rÏ, kh«ng cã kh¶ n¨ng nhí l¹i c¸c kÕt qu¶ trung gian khi thùc hiÖn mét d·y c¸c phÐp to¸n. Tõ thÕ kØ XVIII, ngoµi Sè häc, nhiÒu ngµnh to¸n häc kh¸c nhx §¹i sè, phÐp tÝnh vi ph©n, tÝch ph©n,... ®· ra ®êi, thóc ®Èy øng dông to¸n häc trong c¸c lÜnh vùc cña cuéc sèng. Nhu cÇu tÝnh to¸n t¨ng kh«ng ngõng ®ßi hái con ngxêi s¸ng t¹o ra c¸c c«ng cô tÝnh to¸n tèt h¬n. Vµo n¨m 1819, Charles Babbage, mét gi¸o sx cña trxêng ®¹i häc Cambrige (nxíc Anh) ®· ®xa ra ®Ò ¸n x©y dùng mét m¸y tÝnh c¬ khÝ cã thÓ nhí vµ thùc hiÖn ®xîc d·y c¸c phÐp céng, víi môc ®Ých chñ yÕu lµ thiÕt lËp c¸c b¶ng sè vÒ thiªn v¨n vµ hµng h¶i. 29

Do nguyªn nh©n vÒ tµi chÝnh vµ kÜ thuËt, ®Ò ¸n nµy ®· kh«ng thùc hiÖn ®xîc. §Õn n¨m 1891, c¸c nhµ khoa häc Anh quyÕt ®Þnh dùng l¹i m¸y nµy theo b¶n thiÕt kÕ cßn ®Ó l¹i. KÕt qu¶ thËt ®¸ng kinh ng¹c, m¸y ho¹t ®éng rÊt hoµn h¶o, cã thÓ tÝnh chÝnh x¸c tíi 31 ch÷ sè. Charles Babbage N¨m 1834, Babbage l¹i ®xa ra mét ®Ò ¸n míi vÒ (1791 1871) chiÕc m¸y tÝnh cã tªn lµ \"Analytical Engine\" tù ®iÒu khiÓn theo mét chx¬ng tr×nh ®Þnh s½n. Thø tù thùc hiÖn c¸c phÐp to¸n kh«ng chØ lµ tuÇn tù mµ cßn cã thÓ thay ®æi tuú theo ®iÒu kiÖn nhê mét thiÕt bÞ cã chøc n¨ng ®iÒu khiÓn. Con trai «ng tiÕp tôc thùc hiÖn thµnh c«ng m¸y nµy theo thiÕt kÕ cña bè. Cuèi thÕ kØ XIX, ®iÖn ®· H.Hollerith (1860 1929) v„ m¸y xö lÝ b×a ®ôc lç b¾t ®Çu ®xîc øng dông réng r·i trong kÜ thuËt. Vµo thêi gian ®ã, H. Hollerith chÕ t¹o thµnh c«ng chiÕc m¸y tÝnh sö dông b×a ®ôc lç ®Ó lxu tr÷ vµ thèng kª sè liÖu. Sù kiÖn nµy cã ý nghÜa quan träng v× d÷ liÖu ®· ®xîc lxu tr÷ b»ng phx¬ng tiÖn mµ m¸y cã thÓ tù ®éng ®äc ®xîc. Lo¹i m¸y tÝnh kiÓu nµy ®· ®xîc s¶n xuÊt c«ng nghiÖp víi sè lxîng lín, ®xîc dïng ë nhiÒu nxíc trªn thÕ giíi, chñ yÕu ®Ó xö lÝ sè liÖu thèng kª vµ trong c«ng nghiÖp dÖt ®Ó lµm chx¬ng tr×nh dÖt hoa v¨n. Mét th«ng tin thó vÞ lµ c«ng ti cña Hollerith lµ tiÒn th©n cña c«ng ti m¸y tÝnh IBM (International Business Machine Corporation) næi tiÕng ngµy nay. C¸c m¸y tÝnh c¬ ®iÖn vµ nhÊt lµ c¸c m¸y tÝnh c¬ häc cã nh÷ng h¹n chÕ mang tÝnh nguyªn t¾c. Tèc ®é tÝnh to¸n chËm vµ ®é tin cËy thÊp v× chuyÓn ®éng c¬ häc chÞu ¶nh hxëng cña qu¸n tÝnh, ma s¸t. H¬n n÷a, thùc chÊt m¸y tÝnh c¬ ®iÖn chØ lµ m¸y b¸n tù ®éng v× nã ®ßi hái sù can thiÖp trùc tiÕp cña con ngxêi trong suèt qu¸ tr×nh xö lÝ. N¨m 1944, H. Aiken, gi¸o sx trxêng §¹i häc M¸y tÝnh Mark-1 Harvard chÕ t¹o thµnh c«ng m¸y tÝnh Mark-1, dïng c¸c r¬le ®iÖn tõ ®Ó ®iÒu khiÓn tù ®éng viÖc thùc hiÖn mét d·y liªn tiÕp c¸c phÐp to¸n. Còng vµo thêi gian ®ã J. Von Neumann ®· ®Ò xuÊt nguyªn lÝ m¸y ho¹t ®éng theo chx¬ngtr×nh. 30

Còng cÇn ph¶i nh¾c ®Õn mét nhµ to¸n häc kh¸c lµ Alain Turing, ngxêi ®· ®Ò xuÊt mét m« h×nh to¸n häc cho m¸y tÝnh ®xîc gäi lµ m¸y Turing. §iÒu ®¸ng kh©m phôc lµ khi Turing ®Ò xuÊt m« h×nh nµy, chxa cã m¸y tÝnh ®iÖn tö nhxng tÊt c¶ c¸c m¸y tÝnh hiÖn nay ®Òu cã m« h×nh to¸n häc lµ m¸y Turing. Theo nhÞp ®é ph¸t triÓn m¹nh mÏ cña khoa häc kÜ thuËt, khèi lxîng th«ng tin cÇn xö lÝ ngµy cµng t¨ng. C¸c m¸y tÝnh c¬ ®iÖn kh«ng cßn ®ñ kh¶ n¨ng ®¸p øng ®xîc c¸c nhu cÇu Alain Turing tÝnh to¸n. KÜ thuËt tÝnh to¸n, do vËy, cÇn ph¶i ph¸t triÓn theo (1912 1954) mét hxíng kh¸c, cã triÓn väng h¬n hxíng øng dông ®iÖn tö. Theo hxíng ®ã, H. Aiken, W. Mauchly vµ P. Eckert ®· chÕ t¹o thµnh c«ng chiÕc m¸y tÝnh ®iÖn tö ®Çu tiªn ®xîc ®Æt tªn lµ ENIAC (Electronic Numerical Integrator And Calculator) vµo cuèi n¨m 1945. Víi ENIAC, khoa häc xö lÝ th«ng tin b¾t ®Çu bxíc vµo thêi k× ph¸t triÓn míi. Tõ ®ã chØ trong vßng n¨m thËp kØ, m¸y tÝnh ®· cã c¸c bxíc ph¸t triÓn k× diÖu. Cã thÓ nªu ra c¸c mèc quan träng trong lÞch sö ph¸t triÓn kÜ thuËt tÝnh to¸n: M¸y tÝnh c¬ khÝ -1834 -Charles Babbage. M¸y tÝnh c¬ ®iÖn -1911 -Leonardo Torres y Quevedo. M¸y tÝnh c¬ ®iÖn v¹n n¨ng Harvard -IBM - 1944. M¸y tÝnh ®iÖn tö IBM 603 -1946. M¸y tÝnh b¸n dÉn -1959. M¸y tÝnh víi IC b¸n dÉn -1964. VLSI (vi m¹ch tÝch hîp cùc cao) vµ kÜ thuËt vi xö lÝ -1971. M¸y vi tÝnh ®Çu tiªn Kenbak1 -1971. M¸y vi tÝnh thx¬ng m¹i ho¸ ®Çu tiªn Micral -1973. Siªu m¸y tÝnh Cray -1976. M¸y tÝnh song song - 1987. Bé xö lÝ Intel 80486 - 1989.  Bé xö lÝ Intel Pentium II 300 MHz - 1997.  Bé xö lÝ AMD Athlon tèc ®é 700MHz - 1999.  Bé xö lÝ AMD Athlon tèc ®é 1GHz - 2000.  Bé xö lÝ Intel Pentium IV tèc ®é 2GHz - 2001. 31

†4. Bi to¸n v thuËt to¸n 1. Kh¸i niÖm bµi to¸n Trong ph¹m vi tin häc, ta cã thÓ quan niÖm bµi to¸n lµ mét viÖc nµo ®ã ta muèn m¸y tÝnh thùc hiÖn. Nh÷ng viÖc nh ®a mét dßng ch÷ ra mµn h×nh, gi¶i ph¬ng tr×nh bËc hai, qu¶n lÝ c¸n bé cña mét c¬ quan,... lµ nh÷ng vÝ dô vÒ bµi to¸n. Khi dïng m¸y tÝnh gi¶i bµi to¸n, ta cÇn quan t©m ®Õn hai yÕu tè: ®a vµo m¸y th«ng tin g× (Input) vµ cÇn lÊy ra th«ng tin g× (Output). Do ®ã, ®Ó ph¸t biÓu mét bµi to¸n, ta cÇn ph¶i tr×nh bµy râ Input vµ Output cña bµi to¸n ®ã vµ mèi quan hÖ gi÷a Input vµ Output. VÝ dô 1. Bµi to¸n t×m íc chung lín nhÊt cña hai sè nguyªn d¬ng. Input: Hai sè nguyªn d¬ng M vµ N; Output: ¦íc chung lín nhÊt cña M vµ N. VÝ dô 2. Bµi to¸n t×m nghiÖm cña ph¬ng tr×nh bËc hai ax2 + bx + c = 0 (a z 0). Input: C¸c sè thùc a, b, c (a z 0); Output: TÊt c¶ c¸c sè thùc x tho¶ m·n ax2 + bx + c = 0. ë ®©y, Output cã thÓ lµ mét hoÆc hai sè thùc hoÆc c©u tr¶ lêi kh«ng cã sè thùc nµo nh vËy. VÝ dô 3. Bµi to¸n kiÓm tra tÝnh nguyªn tè. Input: Sè nguyªn d¬ng N; Output: \"N lµ sè nguyªn tè\" hoÆc \"N kh«ng lµ sè nguyªn tè\". VÝ dô 4. Bµi to¸n xÕp lo¹i häc tËp cña mét líp. Input: B¶ng ®iÓm cña häc sinh trong líp; Output: B¶ng xÕp lo¹i häc lùc. 32

Qua c¸c vÝ dô trªn, ta thÊy c¸c bµi to¸n ®îc cÊu t¹o bëi hai thµnh phÇn c¬b¶n: Input: C¸c th«ng tin ®· cã; Output: C¸c th«ng tin cÇn t×m tõ Input. 2. Kh¸i niÖm thuËt to¸n ViÖc cho mét bµi to¸n lµ m« t¶ râ Input cho tríc vµ Output cÇn t×m. VÊn ®Ò lµ: Lµm thÕ nµo ®Ó t×m ra Output? Tríc hÕt cÇn lu ý r»ng trong to¸n häc cã mét Al-Khwarizmi, nh„ to¸n xu híng nghiªn cøu ®Þnh tÝnh c¸c bµi to¸n, cã nghÜa lµ ngêi ta cã thÓ chØ cÇn chøng minh sù tån t¹i cña häc thÕ kØ IX - nǵ͵i cã lêi gi¶i vµ kh«ng cÇn chØ ra mét c¸ch têng minh ̻nh h́ͷng lͳn ÿ͗n sΉ c¸ch t×m lêi gi¶i ®ã. h×nh th„nh thuͅt ng· ViÖc chØ ra têng minh mét c¸ch t×m Output cña \"Algorithm\" bµi to¸n ®îc gäi lµ mét thuËt to¸n (algorithm) gi¶i bµi to¸n ®ã. Cã nhiÒu ®Þnh nghÜa kh¸c nhau vÒ thuËt to¸n, díi ®©y lµ mét ®Þnh nghÜa thêng dïng. ThuËt to¸n ®Ó gi¶i mét bµi to¸n lµ mét d·y h÷u h¹n c¸c thao t¸c ®Æîc s¾p xÕp theo mét tr×nh tù x¸c ®Þnh sao cho sau khi thùc hiÖn d·y thao t¸c Êy, tõ Input cña bµi to¸n, ta nhËn ®Æîc Output cÇn t×m. VÝ dô. T×m gi¸ trÞ lín nhÊt cña mét d·y sè nguyªn x X¸c ®Þnh bµi to¸n  Input: Sè nguyªn d¬ng N vµ d·y N sè nguyªn a1,..., aN.  Output: Gi¸ trÞ lín nhÊt Max cña d·y sè. x ý t€ëng:  Khëi t¹o gi¸ trÞ Max = a1.  LÇn lît víi i tõ 2 ®Õn N, so s¸nh gi¸ trÞ sè h¹ng ai víi gi¸ trÞ Max, nÕu ai > Max th× Max nhËn gi¸ trÞ míi lµ ai. 33

x ThuËt to¸n. ThuËt to¸n gi¶i bµi to¸n nµy cã thÓ ®îc m« t¶ theo c¸ch liÖt kª nh sau: BÆíc 1. NhËp N vµ d·y a1,..., aN; BÆíc 2. Max m a1, i m 2; BÆíc 3. NÕu i > N th× ®a ra gi¸ trÞ Max råi kÕtthóc; BÆíc 4. BÆíc 4.1. NÕu ai > Max th× Max m ai; BÆíc 4.2. i m i + 1 råi quay l¹i bíc 3; Ghi chó: Trong thuËt to¸n trªn, i lµ biÕn chØ sè vµ cã gi¸ trÞ nguyªn thay ®æi tõ 2 ®Õn N + 1. Mòi tªn m trong thuËt to¸n trªn ®xîc hiÓu lµ g¸n gi¸ trÞ cña biÓu thøc bªn ph¶i cho biÕn ë bªn tr¸i mòi tªn. VÝ dô i m i + 1 ®xîc hiÓu lµ ®Æt cho biÕn i gi¸ trÞ míi b»ng gi¸ trÞ trxíc ®ã t¨ng thªm 1 ®¬n vÞ. Ngoµi c¸ch liÖt kª d·y c¸c thao t¸c NhËp N vµ d·y a1,..., aN nh trªn, thuËt to¸n cßn cã thÓ ®îc Max m a1, i m 2 diÔn t¶ b»ng s¬ ®å khèi. Trong s¬ ®å khèi, ngêi ta dïng mét sè khèi, ®êng cã mòi tªn víi: x H×nh thoi thÓ hiÖn thao t¸c i>N? §óng §xa ra Max so s¸nh; råi kÕt thóc x H×nh ch÷ nhËt thÓ hiÖn c¸c Sai phÐp tÝnh to¸n; Sai ai > Max? x H×nh « van thÓ hiÖn thao t¸c §óng nhËp, xuÊt d÷ liÖu; Max m ai x C¸c mòi tªn quy ®Þnh tr×nh tù thùc hiÖn c¸c thao t¸c. Víi bµi to¸n ë vÝ dô trªn, thuËt to¸n imi+1 cã thÓ ®îc diÔn t¶ b»ng s¬ ®å khèi nh h×nh 21. H×nh 21 Díi ®©y lµ vÝ dô m« pháng viÖc thùc hiÖn thuËt to¸n trªn víi N = 11 vµ d·y sè: 5, 1, 4, 7, 6, 3, 15, 8, 4, 9, 12. 34

D·y sè             i             Max             C¸c thao t¸c trong thuËt to¸n ph¶i ®îc m« t¶ ®ñ chi tiÕt ®Ó ®èi tîng thùc hiÖn thuËt to¸n cã thÓ thùc hiÖn ®îc. VÝ dô, trong thuËt to¸n gi¶i ph¬ng tr×nh bËc hai víi ba hÖ sè a,b,c cÇn tÝnh ®¹i lîng '. Tuú thuéc ®èi tîng thùc hiÖn mµ viÖc tÝnh ' cã thÓ ®îc m« t¶ chi tiÕt kh¸c nhau, ch¼ng h¹n: x Víi ®èi tîng biÕt c«ng thøctÝnh ' th× chØ cÇn m« t¶ mét bíc lµ: TÝnh '; x Víi ®èi tîng kh«ng biÕt c«ng thøc tÝnh ' th× cÇn ph¶i m« t¶ chi tiÕt h¬n, ch¼ng h¹n: BÆíc 1. TÝnh b2; BÆíc 2. TÝnh 4ac; BÆíc 3. Gi¸ trÞ ' lµ kÕt qu¶ cña bíc 1 trõ ®i kÕt qu¶ cña bíc 2. Dï ®èi tîng thùc hiÖn kh«ng hÒ biÕt kh¸i niÖm ' lµ g× nhng thùc hiÖn theo c¸c bíc nªu trªn th× vÉn nhËn ®îc gi¸ trÞ ' cÇn tÝnh. Qua ®Þnh nghÜa, ta thÊy thuËt to¸n cã c¸c tÝnh chÊt sau: x TÝnh dõng: ThuËt to¸n ph¶i kÕt thóc sau mét sè h÷u h¹n lÇn thùc hiÖn c¸c thao t¸c; x TÝnh x¸c ®Þnh: Sau khi thùc hiÖn mét thao t¸c th× hoÆc lµ thuËt to¸n kÕt thóc hoÆc lµ cã ®óng mét thao t¸c x¸c ®Þnh ®Ó ®îc thùc hiÖn tiÕp theo; x TÝnh ®óng ®¾n: Sau khi thuËt to¸n kÕt thóc, ta ph¶i nhËn ®îc Output cÇn t×m. VÝ dô. Víi thuËt to¸n t×m Max ®· xÐt: TÝnh dõng: V× gi¸ trÞ cña i mçi lÇn t¨ng lªn 1 nªn sau N lÇn th× i > N, khi ®ã kÕt qu¶ phÐp so s¸nh ë bíc 3 x¸c ®Þnh viÖc ®a ra gi¸ trÞ Max råi kÕtthóc. TÝnh x¸c ®Þnh: Thø tù thùc hiÖn c¸c bíc cña thuËt to¸n ®îc mÆc ®Þnh lµ tuÇn tù nªn sau bíc 1 lµ bíc 2, sau bíc 2 lµ bíc 3. KÕt qu¶ c¸c phÐp so s¸nh trong bíc 3 vµ bíc 4 ®Òu x¸c ®Þnh duy nhÊt bíc tiÕp theo cÇn thùc hiÖn. 35

TÝnh ®óng ®¾n: V× thuËt to¸n so s¸nh Max víi tõng sè h¹ng cña d·y sè vµ thùc hiÖn Max m ai nÕu ai > Max nªn sau khi so s¸nh hÕt N sè h¹ng cña d·y th× Max lµ gi¸ trÞ lín nhÊt. 3. Mét sè vÝ dô vÒ thuËt to¸n VÝ dô 1. KiÓm tra tÝnh nguyªn tè cña mét sè nguyªn d‡¬ng x X¸c ®Þnh bµi to¸n  Input: N lµ mét sè nguyªn d¬ng; Output: \"N lµ sè nguyªn tè\" hoÆc \"N kh«ng lµ sè nguyªn tè\". x ý t€ëng: Ta nhí l¹i ®Þnh nghÜa: Mét sè nguyªn d¬ng N lµ sè nguyªn tè nÕu nã cã ®óng hai íc sè kh¸c nhau lµ 1 vµ chÝnh nã. Tõ ®Þnh nghÜa ®ã, ta suyra:  NÕu N = 1 th× N kh«ng lµ sè nguyªn tè;  NÕu 1 < N < 4 th× N lµ sè nguyªn tè;  NÕu N t 4 vµ kh«ng cã íc sè trong ph¹m vi tõ 2 ®Õn phÇn nguyªn c¨n bËc hai cña N th× N lµ sè nguyªn tè. Tõ ®ã ta cã thuËt to¸n nh sau: x ThuËt to¸n a) C¸ch liÖt kª BÆíc 1. NhËp sè nguyªn d¬ng N; BÆíc 2. NÕu N = 1 th× th«ng b¸o N kh«ng nguyªn tè råi kÕt thóc; BÆíc 3. NÕu N < 4 th× th«ng b¸o N lµ nguyªn tè råi kÕt thóc; BÆíc 4. i m 2; BÆíc 5. NÕu i > [ N ](*) th× th«ng b¸o N lµ nguyªn tè råi kÕt thóc; BÆíc 6. NÕu N chia hÕt cho i th× th«ng b¸o N kh«ng nguyªn tè råi kÕt thóc; BÆíc 7. i m i + 1 råi quay l¹i bíc 5. Ghi chó: BiÕn i nhËn gi¸ trÞ nguyªn thay ®æi trong ph¹m vi tõ 2 ®Õn ª¬ N º¼ + 1 vµ dïng ®Ó kiÓm tra N cã chia hÕt cho i hay kh«ng. (*) [x] kÝ hiÖu phÇn nguyªn cña x, lµ sè nguyªn lín nhÊt kh«ng vît qu¸ x. 36

b) S¬ ®å khèi NhËp N §óng N=1? Sai §óng N<4? Sai im2 i ! ¬ª N ¼º ? §óng Th«ng b¸o N Sai lµ sè nguyªn tè råi kÕt thóc Sai N chia hÕt cho i ? imi+1 §óng Th«ng b¸o N kh«ng lµ sè nguyªn tè råi kÕt thóc Díi ®©y lµ vÝ dô m« pháng viÖc thùc hiÖn thuËt to¸n trªn. Víi N = 29 ( ¬ª 29 ¼º 5 ) Víi N = 45 ( ª¬ 45 º¼ 6 ) i 2 3 4 56 i 2 3 N/i 29/2 29/3 29/4 29/5 N/i 45/2 45/3 Chia hÕt Kh«ng Kh«ng Kh«ng Kh«ng Chia hÕt Kh«ng Chia hÕt kh«ng? kh«ng? a) 29 lµ sè nguyªn tè b) 45 kh«ng lµ sè nguyªn tè VÝ dô 2. Bµi to¸n s¾p xÕp Trong cuéc sèng, ta thêng gÆp nh÷ng viÖc liªn quan ®Õn s¾p xÕp nh xÕp c¸c häc sinh theo thø tù tõ thÊp ®Õn cao, xÕp ®iÓm trung b×nh cña häc sinh trong líp theo thø tù tõ cao ®Õn thÊp. Nãi mét c¸ch tæng qu¸t, cho mét d·y ®èi tîng, cÇn 37

s¾p xÕp l¹i vÞ trÝ c¸c ®èi tîng theo mét tiªu chÝ nµo ®ã. Ch¼ng h¹n, cho 10 chiÕc cäc cã chiÒu cao kh¸c nhau (h. 22a), cÇn xÕp l¹i c¸c cäc tõ thÊp ®Õn cao (h.22b). H×nh 22 Díi ®©y ta chØ xÐt bµi to¸n s¾p xÕp d¹ng ®¬n gi¶n: Cho d·y A gåm N sè nguyªn a1, a2,..., aN. CÇn s¾p xÕp c¸c sè h¹ng ®Ó d·y A trë thµnh d·y kh«ng gi¶m (tøc lµ sè h¹ng trÆíc kh«ng lín h¬n sè h¹ng sau). VÝ dô, víi A lµ d·y gåm c¸c sè nguyªn: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4, sau khi s¾p xÕp ta cã d·y: 1, 3, 4, 5, 6, 7, 7, 8, 10, 12. ThuËt to¸n s¾p xÕp b»ng tr¸o ®æi (Exchange Sort) x X¸c ®Þnh bµi to¸n  Input: D·y A gåm N sè nguyªn a1, a2,..., aN.  Output: D·y A ®îc s¾p xÕp l¹i thµnh d·y kh«ng gi¶m. x ý t€ëng: Víi mçi cÆp sè h¹ng ®øng liÒn kÒ trong d·y, nÕu sè tríc lín h¬n sè sau ta ®æi chç chóng cho nhau. ViÖc ®ã ®îc lÆp l¹i, cho ®Õn khi kh«ng cã sù ®æi chç nµo x¶y ra n÷a. x ThuËt to¸n a) C¸ch liÖt kª BÆíc 1. NhËp N, c¸c sè h¹ng a1, a2,..., aN; BÆíc 2. M m N; BÆíc 3. NÕu M < 2 th× ®a ra d·y A ®· ®îc s¾p xÕp råi kÕt thóc; BÆíc 4. M m M – 1, i m 0; 38

BÆíc 5. i m i + 1; BÆíc 6. NÕu i > M th× quay l¹i bíc 3; BÆíc 7. NÕu ai > ai+1 th× tr¸o ®æi ai vµ ai+1 cho nhau; BÆíc 8. Quay l¹i bíc 5. Ta thÊy r»ng, sau mçi lÇn ®æi chç, gi¸ trÞ lín nhÊt cña d·y A sÏ ®îc chuyÓn dÇn vÒ cuèi d·y vµ sau lît thø nhÊt th× gi¸ trÞ lín nhÊt xÕp ®óng vÞ trÝ lµ ë cuèi d·y. T¬ng tù, sau lît thø hai, gi¸ trÞ lín thø hai ®îc xÕp ®óng ë vÞ trÝ s¸t cuèi,... Cã thÓ h×nh dung, sau mçi lît cã Ýt nhÊt mét sè h¹ng ®· xÕp ®óng vÞ trÝ vµ kh«ng cßn tham gia vµo qu¸ tr×nh ®æi chç n÷a, gièng nh c¸c bät níc tõ ®¸y hå (®Çu d·y) næi dÇn vµ khi ®· lªn mÆt níc (cuèi d·y) råi th× tan biÕn. Cã thÓ v× thÕ mµ s¾p xÕp b»ng tr¸o ®æi cßn cã tªn gäi lµ s¾p xÕp næi bät (Bubble Sort). Ghi chó:  Qua nhËn xÐt trªn, ta thÊy qu¸ tr×nh so s¸nh vµ ®æi chç sau mçi lxît chØ thùc hiÖn víi d·y ®· bá bít sè h¹ng cuèi d·y. §Ó thùc hiÖn ®iÒu ®ã trong thuËt to¸n sö dông biÕn nguyªn M cã gi¸ trÞ khëi t¹o lµ N, sau mçi lxît M gi¶m mét ®¬n vÞ cho ®Õn khi M < 2.  Trong thuËt to¸n trªn, i lµ biÕn chØ sè cã gi¸ trÞ nguyªn thay ®æi lÇn lxît tõ 0 ®Õn M + 1. b) S¬ ®å khèi NhËp N vµ a1, a2,..., aN MmN M<2? §óng §a ra A råi kÕt thóc Sai M m M – 1; im 0 §óng imi+1 Tr¸o ®æi ai vµ ai+1 §óng i>M? Sai ai > ai+1 ? Sai 39

Díi ®©y lµ vÝ dô m« pháng viÖc thùc hiÖn thuËt to¸n trªn. VÝ dô 3. Bµi to¸n t×m kiÕm T×m kiÕm lµ viÖc thêng x¶y ra trong cuéc sèng, ch¼ng h¹n cÇn t×m cuèn s¸ch gi¸o khoa Tin häc 10 trªn gi¸ s¸ch, cÇn t×m mét häc sinh trong danh s¸ch mét líp häc,... Nãi mét c¸ch tæng qu¸t lµ cÇn t×m mét ®èi tîng cô thÓ nµo ®ã trong tËp c¸c ®èi tîng cho tríc. Díi ®©y ta chØ xÐt bµi to¸n t×m kiÕm d¹ng ®¬n gi¶n sau: Cho d·y A gåm N sè nguyªn kh¸c nhau: a1, a2,..., aN vµ mét sè nguyªn k. CÇn biÕt cã hay kh«ng chØ sè i (1 d i d N) mµ ai = k. NÕu cã h·y cho biÕt chØ sè ®ã. Sè nguyªn k ®îc gäi lµ kho¸ t×m kiÕm (gäi t¾t lµ kho¸). VÝ dô, cho d·y A gåm c¸c sè: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51. x Víi kho¸ k = 2, trong d·y trªn cã sè h¹ng a5 cã gi¸ trÞ b»ngk. VËy chØ sè cÇn t×m lµ i = 5; x Víi kho¸ k = 6 th× kh«ng cã sè h¹ng nµo cña d·y A cã gi¸ trÞ b»ng k. ThuËt to¸n t×m kiÕm tuÇn tù (Sequential Search) x X¸c ®Þnh bµi to¸n  Input: D·y A gåm N sè nguyªn kh¸c nhau a1, a2,..., aN vµ sè nguyªn k;  Output: ChØ sè i mµ ai = k hoÆc th«ng b¸o kh«ng cã sè h¹ng nµo cña d·y A cã gi¸ trÞ b»ng k. 40

x ý t€ëng: T×m kiÕm tuÇn tù ®îc thùc hiÖn mét c¸ch tù nhiªn. LÇn lît tõ sè h¹ng thø nhÊt, ta so s¸nh gi¸ trÞ sè h¹ng ®ang xÐt víi kho¸ cho ®Õn khi hoÆc gÆp mét sè h¹ng b»ng kho¸ hoÆc d·y ®· ®îc xÐt hÕt vµ kh«ng cã gi¸ trÞ nµo b»ng kho¸. Trong trêng hîp thø hai d·y A kh«ng cã sè h¹ng nµo b»ng kho¸. x ThuËt to¸n a) C¸ch liÖt kª BÆíc 1. NhËp N, c¸c sè h¹ng a1, a2,..., aN vµ kho¸ k; BÆíc 2. i m 1; BÆíc 3. NÕu ai = k th× th«ng b¸o chØ sè i, råi kÕt thóc; BÆíc 4. i m i + 1; BÆíc 5. NÕu i > N th× th«ng b¸o d·y A kh«ng cã sè h¹ng nµo cã gi¸ trÞ b»ngk, råi kÕt thóc; BÆíc 6. Quay l¹i bíc 3. Ghi chó: Trong thuËt to¸n trªn, i lµ biÕn chØ sè vµ nhËn gi¸ trÞ nguyªn lÇn lxît tõ 1 ®Õn N + 1. b) S¬ ®å khèi NhËp N vµ a1, a2,..., aN; k im1 §óng §xa ra i råi kÕt thóc ai = k Sai imi+1 Sai i>N? §óng Th«ng b¸o d·y A kh«ng cã sè h¹ng cã gi¸ trÞ b»ng k råi kÕt thóc 41

Díi ®©y lµ vÝ dô m« pháng viÖc thùc hiÖn thuËt to¸n trªn. k = 2 vµ N = 10 k = 6 vµ N = 10 A 5 7 1 4 2 9 8 11 25 51 A 5 7 1 4 2 9 8 11 25 51 i 12345 - - - - - i 1 2 3 4 5 6 7 8 9 10 11 Víi i = 5 th× a5 = 2. Víi mäi i tõ 1 ®Õn 10 kh«ng cã ai cã gi¸ trÞ b»ng 6. ThuËt to¸n t×m kiÕm nhÞ ph©n (Binary Search) x X¸c ®Þnh bµi to¸n  Input: D·y A lµ d·y t¨ng gåm N sè nguyªn kh¸c nhau a1, a2,..., aN vµ mét sè nguyªn k;  Output: ChØ sè i mµ ai = k hoÆc th«ng b¸o kh«ng cã sè h¹ng nµo cña d·y A cã gi¸ trÞ b»ng k. x ý t€ëng: Sö dông tÝnh chÊt d·y A lµ d·y t¨ng, ta t×m c¸ch thu hÑp nhanh ph¹m vi t×m kiÕm sau mçi lÇn so s¸nh kho¸ víi sè h¹ng ®îc chän. §Ó lµm ®iÒu ®ã, ta chän sè h¹ng aGiua ë \"gi÷a d·y\" ®Ó so s¸nh víi k, trong ®ã Giua= ª N+1º . «¬ 2 ¼» Khi ®ã, chØ x¶y ra mét trong ba trêng hîp sau: NÕu aGiua = k th× Giua lµ chØ sè cÇn t×m. ViÖc t×m kiÕm kÕt thóc. NÕu aGiua > k th× do d·y A lµ d·y ®· ®îc s¾p xÕp nªn viÖc t×m kiÕm tiÕp theo chØ xÐt trªn d·y a1, a2,..., aGiua–1 (ph¹m vi t×m kiÕm míi b»ng kho¶ng mét nöa ph¹m vi t×m kiÕm tríc ®ã). NÕu aGiua < k th× thùc hiÖn t×m kiÕm trªn d·y aGiua+1, aGiua+2,..., aN. Qu¸ tr×nh trªn sÏ ®îc lÆp l¹i mét sè lÇn cho ®Õn khi hoÆc ®· t×m thÊy kho¸ k trong d·y A hoÆc ph¹m vi t×m kiÕm b»ng rçng. x ThuËt to¸n a) C¸ch liÖt kª BÆíc 1. NhËp N, c¸c sè h¹ng a1, a2,..., aN vµ kho¸ k; 42

BÆíc 2. Dau m 1, Cuoi m N; BÆíc 3. Giua m ª Dau + Cuoi º ; «¬ 2 ¼» BÆíc 4. NÕu aGiua = k th× th«ng b¸o chØ sè Giua, råi kÕt thóc; BÆíc 5. NÕu aGiua > k th× ®Æt Cuoi = Giua – 1, råi chuyÓn ®Õn bíc 7; BÆíc 6. Dau m Giua + 1; BÆíc 7. NÕu Dau > Cuoi th× th«ng b¸o d·y A kh«ng cã sè h¹ng cã gi¸ trÞ b»ng k, råi kÕt thóc; BÆíc 8. Quay l¹i bíc 3. Ghi chó: Tuú thuéc aGiua > k hoÆc aGiua < k mµ chØ sè ®Çu hoÆc chØ sè cuèi cña d·y ë bxíc t×m kiÕm tiÕp theo sÏ thay ®æi. §Ó thùc hiÖn ®iÒu ®ã, trong thuËt to¸n chØ sö dông c¸c biÕn nguyªn tx¬ng øng Dau vµ Cuoi cã gi¸ trÞ khëi t¹o Dau = 1 vµ Cuoi = N. b) S¬ ®å khèi NhËp N vµ a1, a2,..., aN; k Dau m 1; Cuoi m N Giua m [(Dau + Cuoi)/2] aGiua = k ? Sai §óng aGiua > k §óng §xa ra Giua råi kÕt thóc Cuoi m Giua – 1 Sai Sai Dau m Giua + 1 Dau>Cuoi? §óng Th«ng b¸o d·y A kh«ng cã sè h¹ng cã gi¸ trÞ b»ng k råi kÕt thóc 43

Díi ®©y lµ vÝ dô m« pháng viÖc thùc hiÖn thuËt to¸n trªn. k = 21, N =10 k = 25, N =10 i 1 2 3 4 5 6 7 8 9 10 i 1 2 3 4 5 6 7 8 9 10 A 2 4 5 6 9 21 22 30 31 33 A 2 4 5 6 9 21 22 30 31 33 Dau 1 6 6 Dau 1 6 6 7 8 Cuoi 10 10 7 Cuoi 10 10 7 7 7 Giua 5 8 6 Giua 5 8 6 7 aGiua 9 30 21 aGiua 9 30 21 22 LÇn 1 2 3 LÇn 1 2 3 4 5 duyÖt duyÖt ë lÇn duyÖt thø ba th× aGiua = k. VËy chØ sè T¹i lÇn duyÖt thø n¨m Dau > Cuoi nªn cÇn t×m lµ i = Giua = 6. kÕt luËn trong d·y A kh«ng cã sè h¹ng nµo cã gi¸ trÞ lµ 25 c¶. C¸c thuËt ng÷ chÝnh Bµi to¸n; ThuËt to¸n; S¬ ®å khèi; Input; Output; S¾p xÕp b»ng tr¸o ®æi; T×m kiÕm tuÇn tù; T×m kiÕm nhÞ ph©n. C©u hái vµ bµi tËp 1. H·y ph¸t biÓu mét bµi to¸n vµ chØ râ Input vµ Output cña bµi to¸n ®ã. 2. D·y c¸c thao t¸c sau: Bzíc 1. Xo¸ b¶ng; Bzíc 2. VÏ ®wêng trßn; Bzíc 3. Quay l¹i bwíc 1. cã ph¶i lµ thuËt to¸n kh«ng? T¹i sao? 3. H·y chØ ra tÝnh dõng cña thuËt to¸n t×m kiÕm tuÇn tù. H·y m« t¶ thuËt to¸n gi¶i c¸c b†i to¸n sau b»ng c¸ch liÖt kª hoÆc b»ng s¬ ®å khèi. 4. Cho N vµ d·y sè a1,..., aN, h·y t×m gi¸ trÞ nhá nhÊt (Min) cña d·y ®ã. 5. T×m nghiÖm cña phw¬ng tr×nh bËc hai tæng qu¸t: ax2 + bx + c = 0. 6. Cho N vµ d·y sè a1,..., aN, h·y s¾p xÕp d·y sè ®ã thµnh d·y sè kh«ng t¨ng (sè h¹ng trwíc lín h¬n hay b»ng sè h¹ng sau). 7. Cho N vµ d·y sè a1,..., aN, h·y cho biÕt cã bao nhiªu sè h¹ng trong d·y cã gi¸ trÞ b»ng 0. 44

†5. Ng«n ng÷ lËp tr×nh Víi c¸ch diÔn t¶ thuËt to¸n b»ng c¸ch liÖt kª hoÆc s¬ ®å khèi, m¸y tÝnh cha cã kh¶ n¨ng trùc tiÕp thùc hiÖn thuËt to¸n ®îc. Ta cÇn diÔn t¶ thuËt to¸n b»ng mét ng«n ng÷ sao cho m¸y tÝnh cã thÓ thùc hiÖn ®îc. KÕt qu¶ diÔn t¶ thuËt to¸n nh vËy cho ta mét chƬng tr×nh, ng«n ng÷ ®Ó viÕt ch¬ng tr×nh ®îc gäi lµ ng«n ng÷ lËp tr×nh. Cã nhiÒu lo¹i ng«n ng÷ lËp tr×nh. Sù kh¸c nhau gi÷a c¸c lo¹i liªn quan ®Õn ®é phô thuéc cña chóng vµo kiÕn tróc vµ ho¹t ®éng cña m¸y tÝnh. 1. Ng«n ng÷ m¸y Mçi lo¹i m¸y tÝnh ®Òu cã ng«n ng÷ m¸y cña nã. §ã lµ ng«n ng÷ duy nhÊt ®Ó viÕt ch¬ng tr×nh mµ m¸y tÝnh trùc tiÕp hiÓu vµ thùc hiÖn ®îc. ViÕt c¸c ch¬ng tr×nh b»ng ng«n ng÷ m¸y, ta cã thÓ khai th¸c triÖt ®Ó c¸c ®Æc ®iÓm phÇn cøng cña m¸y. Mçi ch¬ng tr×nh viÕt b»ng ng«n ng÷ kh¸c muèn thùc hiÖn trªn m¸y tÝnh ®Òu ph¶i ®îc dÞch ra ng«n ng÷ m¸y b»ng mét ch¬ng tr×nh dÞch. C¸c lÖnh viÕt b»ng ng«n ng÷ m¸y ë d¹ng m· nhÞ ph©n hoÆc ë d¹ng m· hexa. Tuy nhiªn ng«n ng÷ m¸y kh«ng thuËn lîi cho con ngêi trong viÖc viÕt hoÆc hiÓu ch¬ng tr×nh. Víi ng«n ng÷ m¸y, ta ph¶i nhí mét c¸ch m¸y mãc c¸c dßng sè kh«ng gîi ý nghÜa cña lÖnh ®ång thêi ph¶i dïng nhiÒu c©u lÖnh ®Ó diÔn t¶ chi tiÕt c¸c thao t¸c cña thuËt to¸n. §Ó kh¾c phôc nhîc ®iÓm trªn cña ng«n ng÷ m¸y, mét sè ng«n ng÷ lËp tr×nh kh¸c ®· ®îc ph¸t triÓn. 2. Hîp ng÷ So víi ng«n ng÷ m¸y, hîp ng÷ cho phÐp ngêi lËp tr×nh sö dông mét sè tõ (thêng lµ viÕt t¾t c¸c tõ tiÕng Anh) ®Ó thÓ hiÖn c¸c lÖnh cÇn thùc hiÖn. VÝ dô, ®Ó céng gi¸ trÞ chøa trong hai thanh ghi cã tªn lµ AX vµ BX, cã thÓ dïng mét lÖnh cña hîp ng÷ nh sau: ADD AX, BX trong ®ã ADD (tiÕng Anh cã nghÜa lµ céng) lµ kÝ hiÖu phÐp céng vµ kÕt qu¶ ®îc quy íc ®Æt vµo thanh ghi AX. 45

Mét ch¬ng tr×nh viÕt b»ng hîp ng÷ ph¶i ®îc dÞch ra ng«n ng÷ m¸y nhê chƬng tr×nh hîp dÞch tríc khi cã thÓ thùc hiÖn ®îc trªn m¸y tÝnh. 3. Ng«n ng÷ bËc cao Hîp ng÷ lµ mét ng«n ng÷ ®· thuËn lîi h¬n cho c¸c nhµ lËp tr×nh chuyªn nghiÖp nhng vÉn cha thËt thÝch hîp víi ®«ng ®¶o ngêi lËp tr×nh. Tõ ®Çu thËp kØ n¨m m¬i cña thÕ kØ XX, ngêi ta ®· x©y dùng nh÷ng ng«n ng÷ lËp tr×nh bËc cao, trong ®ã c¸c c©u lÖnh ®îc viÕt gÇn víi ng«n ng÷ tù nhiªn h¬n, cã tÝnh ®éc lËp cao, Ýt phô thuéc vµo c¸c lo¹i m¸y cô thÓ. Còng nh ®èi víi hîp ng÷, mçi ng«n ng÷ lËp tr×nh bËc cao ®Òu cÇn cã mét chƬng tr×nh dÞch ®Ó dÞch nh÷ng ch¬ng tr×nh viÕt b»ng ng«n ng÷ nµy sang ng«n ng÷ m¸y. Ng«n ng÷ bËc cao ®Çu tiªn lµ ng«n ng÷ FORTRAN (FORmula TRANslator) cña h·ng m¸y tÝnh IBM, ra ®êi n¨m 1954. TiÕp theo lµ COBOL (COmmon Business-Oriented Language) ra ®êi n¨m 1959, sau ®ã mét n¨m lµ Algol 60 vµ n¨m n¨m sau lµ BASIC (Beginner's All-purpose Symbolic Instruction Code). HiÖn nay cã rÊt nhiÒu ng«n ng÷ lËp tr×nh bËc cao ®îc sö dông nh PASCAL, C, C++, Java,... víi c¸c phiªn b¶n kh¸cnhau. C¸c thuËt ng÷ chÝnh Ng«n ng÷ m¸y; Hîp ng÷; Ng«n ng÷ bËc cao; Chx¬ng tr×nh dÞch. C©u hái vµ bµi tËp 1. Em hiÓu ng«n ng÷ lËp tr×nh lµ g×? 2. Chw¬ng tr×nh dÞch dïng ®Ó lµm g×? 3. V× sao ph¶i ph¸t triÓn c¸c ng«n ng÷ bËc cao? 46

†6. Gi¶i bi to¸n trªn m¸y tÝnh Häc sö dông m¸y tÝnh thùc chÊt lµ häc c¸ch giao cho m¸y tÝnh viÖc mµ ta muèn nã lµm. Kh¶ n¨ng khai th¸c m¸y tÝnh phô thuéc rÊt nhiÒu vµo sù hiÓu biÕt cña ngêi dïng. ViÖc gi¶i bµi to¸n trªn m¸y tÝnh thêng ®îc tiÕn hµnh qua c¸c bíc sau: BÆíc 1. X¸c ®Þnh bµi to¸n; BÆíc 2. Lùa chän hoÆc thiÕt kÕ thuËt to¸n; BÆíc 3. ViÕt ch¬ng tr×nh; BÆíc 4. HiÖu chØnh; BÆíc 5. ViÕt tµi liÖu. 1. X¸c ®Þnh bµi to¸n Nh ®· tr×nh bµy, mçi bµi to¸n ®îc ®Æc t¶ bëi hai thµnh phÇn: Input vµ Output. ViÖc x¸c ®Þnh bµi to¸n chÝnh lµ x¸c ®Þnh râ hai thµnh phÇn nµy vµ mèi quan hÖ gi÷a chóng. C¸c th«ng tin ®ã cÇn ®îc nghiªn cøu cÈn thËn ®Ó cã thÓ lùa chän thuËt to¸n, c¸ch thÓ hiÖn c¸c ®¹i lîng ®· cho, c¸c ®¹i lîng ph¸t sinh trong qu¸ tr×nh gi¶i bµi to¸n vµ ng«n ng÷ lËp tr×nh thÝch hîp. VÝ dô, trong mét bµi to¸n tin häc khi ®Ò cËp ®Õn mét sè nguyªn d¬ng N, lµ tuæi cña mét ngêi, cã thÓ chØ râ ph¹m vi gi¸ trÞ cña N tõ 1 ®Õn 150, ®Ó lùa chän c¸ch thÓ hiÖn N b»ng kiÓu d÷ liÖu thÝch hîp. 2. Lùa chän hoÆc thiÕt kÕ thuËt to¸n a) Lùa chän thuËt to¸n Bíc lùa chän hoÆc thiÕt kÕ thuËt to¸n lµ bíc quan träng nhÊt ®Ó gi¶i mét bµi to¸n. Mçi thuËt to¸n chØ gi¶i mét bµi to¸n nµo ®ã, nhng cã thÓ cã nhiÒu thuËt to¸n kh¸c nhau cïng gi¶i mét bµi to¸n. CÇn thiÕt kÕ hoÆc chän mét thuËt to¸n phï hîp ®· cã ®Ó gi¶i bµi to¸n cho tríc. 47

Khi thiÕt kÕ hoÆc lùa chän thuËt to¸n ngêi ta thêng quan t©m ®Õn c¸c tµi nguyªn nh thêi gian thùc hiÖn, sè lîng « nhí,... Trong c¸c lo¹i tµi nguyªn, ngêi ta quan t©m nhiÒu nhÊt ®Õn thêi gian v× ®ã lµ d¹ng tµi nguyªn kh«ng t¸i t¹o ®îc. VÝ dô, víi bµi to¸n t×m kiÕm, nÕu d·y ®· cho lµ d·y ®· s¾p xÕp th× dÔ thÊy thuËt to¸n t×m kiÕm nhÞ ph©n cÇn Ýt thao t¸c h¬n nhiÒu so víi thuËt to¸n t×m kiÕm tuÇn tù. V× thÕ nã cÇn Ýt thêi gian thùc hiÖn h¬n. Mét tiªu chÝ kh¸c ®îc rÊt nhiÒu ngêi quan t©m lµ cÇn thiÕt kÕ hoÆc lùa chän thuËt to¸n sao cho viÖc viÕt ch¬ng tr×nh cho thuËt to¸n ®ã Ýt phøc t¹p. Khi thiÕt kÕ hoÆc lùa chän thuËt to¸n ®Ó gi¶i mét bµi to¸n cô thÓ cÇn c¨n cø vµo lîng tµi nguyªn mµ thuËt to¸n ®ßi hái vµ lîng tµi nguyªn thùc tÕ chophÐp. b) DiÔn t¶ thuËt to¸n ViÖc diÔn t¶ mét thuËt to¸n ®· ®îc tr×nh bµy ë †4. Díi ®©y ta xÐt thªm mét vÝ dô kh¸c. VÝ dô. T×m ‡íc chung lín nhÊt (sCLN) cña hai sè nguyªn d‡¬ng M vµ N. x X¸c ®Þnh bµi to¸n  Input: Cho M, N;  Output: ¦CLN(M, N). x ý t€ëng: Sö dông nh÷ng ®iÒu ®· biÕt sau:  NÕu M = N th× gi¸ trÞ chung ®ã lµ ¦CLN cña M vµ N;  NÕu M < N th× ¦CLN(M, N) = ¦CLN(M, N  M);  NÕu M > N th× ¦CLN(M, N) = ¦CLN(M N, N). x ThuËt to¸n C¸ch liÖt kª BÆíc 1. NhËp M, N; BÆíc 2. NÕu M = N th× lÊy gi¸ trÞ chung nµy lµm ¦CLN råi chuyÓn ®Õn bíc 5; BÆíc 3. NÕu M > N th× M m M  N råi quay l¹i bíc 2; BÆíc 4. N m N  M råi quay l¹i bíc 2; BÆíc 5. §a ra kÕt qu¶ ¦CLN råi kÕt thóc. 48

S¬ ®å khèi NhËp M vµ N M=N? Sai M>N? Sai NmN–M §óng §óng §xa ra M råi kÕt thóc MmM–N Sau ®©y lµ hai vÝ dô m« pháng viÖc thùc hiÖn thuËt to¸n trªn. a) ¦CLN(25, 10) = 5 b) ¦CLN(17, 13) = 1 49

3. ViÕt chy¬ng tr×nh ViÖc viÕt ch¬ng tr×nh lµ tæng hîp gi÷a viÖc lùa chän c¸ch tæ chøc d÷ liÖu vµ sö dông ng«n ng÷ lËp tr×nh ®Ó diÔn ®¹t ®óng thuËt to¸n. Khi viÕt ch¬ng tr×nh ta nªn chän mét ng«n ng÷ lËp tr×nh hoÆc mét phÇn mÒm chuyªn dông thÝch hîp víi thuËt to¸n. ViÕt ch¬ng tr×nh trong ng«n ng÷ nµo th× cÇn ph¶i tu©n theo ®óng quy ®Þnh ng÷ ph¸p cña ng«n ng÷ ®ã. Ch¬ng tr×nh dÞch chØ cã thÓ ph¸t hiÖn vµ th«ng b¸o c¸c lçi vÒ mÆt ng÷ ph¸p. 4. HiÖu chØnh Sau khi ®îc viÕt xong, ch¬ng tr×nh vÉn cßn cã thÓ cã nhiÒu lçi kh¸c cha ph¸t hiÖn ®îc nªn cã thÓ kh«ng cho kÕt qu¶ ®óng. V× vËy, cÇn ph¶i thö ch¬ng tr×nh b»ng c¸ch thùc hiÖn nã víi mét sè bé Input tiªu biÓu phô thuéc vµo ®Æc thï cña bµi to¸n vµ b»ng c¸ch nµo ®ã ta ®· biÕt tríc Output. C¸c bé Input vµ Output t¬ng øng nµy ®îc gäi lµ c¸c Test. NÕu cã sai sãt, ta ph¶i söa ch¬ng tr×nh råi thö l¹i. Qu¸ tr×nh nµy ®îc gäi lµ hiÖu chØnh. NÕu kÕt qu¶ hiÖu chØnh cho thÊy ng«n ng÷ lËp tr×nh hoÆc thuËt to¸n kh«ng phï hîp, thËm chÝ ta ph¶i quay l¹i lùa chän hay thiÕt kÕ thuËt to¸n. VÝ dô, ®Ó kiÓm chøng tÝnh ®óng ®¾n cña ch¬ng tr×nh gi¶i ph¬ng tr×nh bËc hai ax2 + bx + c = 0, ta cã thÓ sö dông ba bé Input nh sau: x BiÖt sè ' > 0: a = 1, b =  5, c = 6 (ch¬ng tr×nh ®a ra hai nghiÖm); x BiÖt sè ' = 0: a = 1, b =  4, c = 4 (ch¬ng tr×nh ®a ra mét nghiÖm); x BiÖt sè ' < 0: a = 1, b = 4, c = 8 (ch¬ng tr×nh th«ng b¸o ph¬ng tr×nh v« nghiÖm). 5. ViÕt tµi liÖu Tµi liÖu ph¶i m« t¶ bµi to¸n, thuËt to¸n, thiÕt kÕ ch¬ng tr×nh, kÕt qu¶ thö nghiÖm vµ híng dÉn sö dông. Tµi liÖu nµy rÊt cã Ých cho ngêi sö dông ch¬ng tr×nh vµ cho viÖc ®Ò xuÊt nh÷ng kh¶ n¨ng hoµn thiÖn thªm. C¸c bíc trªn cã thÓ lÆp ®i lÆp l¹i nhiÒu lÇn cho ®Õn khi ta cho r»ng ch¬ng tr×nh ®· lµm viÖc ®óng ®¾n vµ hiÖu qu¶. 50