›
›

Giáo trình tin học đại cương A1 - Hoàng Kiếm

pdf 53 trang huongle 8930
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình tin học đại cương A1 - Hoàng Kiếm", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_tin_hoc_dai_cuong_a1_hoang_kiem.pdf

Nội dung text: Giáo trình tin học đại cương A1 - Hoàng Kiếm

  1. CHƯƠNG 1 TỔNG QUAN VỀ MÁY TÍNH 1. GIỚI THIỆU Máy tính là công cụ xử lý thông tin. Về cơ bản, quá trình xử lý thông tin trên máy tính - cũng như quá trình xử lý thông tin của con người - có bốn giai đoạn chính: Nhận thông tin (Receive input): thu nhận thông tin từ thế giới bên ngoài vào máy tính. Thực chất đây là quá trình chuyển đổi các thông tin ở thế giới thực sang dạng biểu diễn thông tin trong máy tính thông qua các thiết bị đầu vào. Xử lý thông tin (process information): biến đổi, phân tích, tổng hợp, tra cứu những thông tin ban đầu để có được những thông tin mong muốn. Xuất thông tin (produce output): đưa các thông tin kết quả (đã qua xử lý) ra trở lại thế giới bên ngoài. Ðây là quá trình ngược lại với quá trình ban đầu, máy tính sẽ chuyển đổi các thông tin trong máy tính sang dạng thông tin ở thế giới thực thông qua các thiết bị đầu ra. Lưu trữ thông tin (store information): ghi nhớ lại các thông tin đã được ghi nhận để có thể đem ra sử dụng trong những lần xử lý về sau. Ðể đáp ứng bốn thao tác đó thì một máy tính thông thường cũng gồm bốn bộ phận hợp thành, mỗi bộ phận có một chức năng riêng: Thiếp bị nhập (input device): thực hiện thao tác đưa dữ liệu từ thế giới bên ngoài vào, thường là bàn phím và con chuột, nhưng cũng có thể là các loại thiết bị khác mà ta sẽ nói rõ hơn ở những phần sau. 5
  2. Thiết bị xử lý (đơn vị xử lý trung tâm - CPU )thực hiện thao tác xử lý, tính toán các kết quả, điều hành hoạt động tính toán của máy vi tính. Có thể xem CPU như bộ não của con người. Thiết bị xuất (output): thực hiện thao tác gởi thông tin ra ngoài máy vi tính, thường dùng màn hình máy tính làm thiết bị xuất chuẩn, có thể thêm một số khác như máy in Thiết bị lưu trữ (storage devices): được dùng để lưu giữ thông tin. Lưu trữ sơ cấp (primary memory) là bộ nhớ trong của máy tính dùng để lưu các tập lệnh của chương trình, các thông tin dữ liệu sẵn sàng làm việc tùy theo yêu cầu của CPU. Lưu trữ thứ cấp (secondary storage) là cách lưu trữ đơn thuần với mục đích lưu giữ dữ liệu, cách này dùng các thiết bị lưu trữ như đĩa cứng, đĩa mềm, băng từ, CD. 2. THÔNG TIN - BIỂU DIỄN VÀXỬ LÝ THÔNG TIN Khái niệm thông tin (information) được sử dụng thường ngày. Con người có nhu cầu đọc báo, nghe đài, xem phim, video, đi tham quan, du lịch, tham khảo ý kiến người khác, để nhận được thêm thông tin mới. Thông tin mang lại cho con người sự hiểu biết, nhận thức tốt hơn về những đối tượng trong đời sống xã hội, trong thiên nhiên, giúp cho họ thực hiện hợp lý công việc cần làm để đạt tới mục đích một cách tốt nhất. Những đám mây đen đùn lên ở chân trời phía Ðông chứa đựng thông tin báo hiệu về trận mưa lớn sắp xảy ra. Màu đen của mây, tốc độ chuyển động của mây chứa các thông tin về khí tượng. Biểu đồ thống kê sản phẩm hàng tháng của từng phân xưởng bánh kẹo chứa đựng các thông tin về năng suất lao động, về mức độ thực hiện kế hoạch sản xuất của phân xưởng đó. Nốt nhạc trong bản Sonata ánh trăng của Beethoven làm cho người nghe cảm thấy được sự tươi mát, êm dịu của đêm trăng. Những thông tin về cảm xúc của tác giả đã được truyền đạt lại. 6
  3. Khi tiếp nhận được thông tin, con người thường phải xử lý nó để tạo ra những thông tin mới, có ích hơn, từ đó có những phản ứng nhất định. Người tài xế chăm chú quan sát người, xe cộ đi lại trên đường, độ tốt xấu mặt đường, tính năng kỹ thuật cũng như vị trí của chiếc xe để quyết định, cần tăng tốc độ hay hãm phanh, cần bẻ lái sang trái hay sang phải nhằm đảm bảo an toàn tối đa cho chuyến xe đi. Thông tin có thể được phát sinh, được lưu trữ, được truyền, được tìm kiếm, được sao chép, được xử lý, nhân bản. Thông tin cũng có thể biến dạng, sai lệch hoặc bị phá hủy. Mỗi tế bào sinh dục của những cá thể sinh vật mang thông tin di truyền quyết định những đặc trưng phát triển của cá thể đó. Gặp môi trường không thuận lợi, các thông tin di truyền đó có thể bị biến dạng, sai lệch dẫn đến sự hình thành những cá thể dị dạng. Ngược lại, bằng những tác động tốt của di truyền học chọn giống, ta có thể cấy hoặc làm thay đổi các thông tin di truyền theo hướng có lợi cho con người. Thông tin được thể hiện dưới nhiều dạng thức khác nhau như sóng ánh sáng, sóng âm, điện từ, các ký hiệu viết trên giấy hoặc khắc trên gỗ, trên đá, trên các tấm kim loại Về nguyên tắc, bất kỳ cấu trúc vật chất nào hoặc bất kỳ dòng năng lượng nào cũng có thể mang thông tin. Chúng được gọi là những vật (giá) mang tin. Dữ liệu (data) là biểu diễn của thông tin và được thể hiện bằng các tín hiệu (signal) vật lý. Thông tin chứa đựng ý nghĩa, còn dữ liệu là các dữ kiện không có cấu trúc và không có ý nghĩa rõ ràng nếu nó không được tổ chức và xử lý. Cùng một thông tin, có thể được biểu diễn bằng những dữ liệu khác nhau. Cùng biểu diễn một đơn vị, nhưng trong chữ số thập phân ta cùng ký hiệu 1, còn trong hệ đếm La Mã lại dùng ký hiệu I. Mỗi dữ liệu lại có thể được thể hiện bằng những ký hiệu vật lý khác nhau. Cùng là ký hiệu I nhưng trong tiếng Anh có nghĩa là đại từ nhân xưng ngôi thứ nhất (tôi) còn trong toán học lại là chữ số La Mã có giá trị là 1. 7
  4. Mỗi tín hiệu có thể dùng để thể hiện các thông tin khác nhau. Uống một chén rượu để mừng ngày gặp mặt, cũng có thể uống chén rượu để giải sầu, để tiễn đưa người thân lên đường đi xa. Thông tin là một khái niệm trừu tượng, tồn tại khách quan, có thể nhớ trong đối tượng, biến đổi trong đối tượng và áp dụng để điều khiển đối tượng. Thông tin làm tăng thêm hiểu biết của con người, là nguồn gốc của nhận thức. Thông tin về một đối tượng chính là một dữ kiện về đối tượng đó, chúng giúp ta nhận biết và hiểu được đối tượng. Thông tin có liên quan chặt chẽ đến khái niệm về độ bất định. Mỗi đối tượng chưa xác định hoàn toàn đều có một độ bất định nào đó. Tính bất định này chưa cho biết một cách chính xác và đầy đủ về đối tượng đó. Ðộ bất định có liên quan chặt chẽ đến khái niệm xác suất - độ đo khả năng có thể xảy ra của sự kiện (biến cố). Nếu một biến cố không bao giờ xảy ra, xác suất của nó có giá trị bằng 0. Nếu có một biến cố chắc chắn xảy ra, xác suất của nó bằng 1. Ðại lượng xác suất có giá trị trong đoạn [0,1]. Xác suất đối tượng A trú ngụ ở đâu trong 9 địa bàn (4 quận và 5 huyện) của Hà Nội trước khi có thông tin bổ sung là 1/9, còn sau đó là 1/5. Xác suất càng nhỏ thì độ bất định càng lớn. Thông tin có thể đo được. Giả sử sự kiện có thể tồn tại ở một trong số n trạng thái được đánh số 1, 2, , n trong đó trạng thái i xuất hiện với xác suất là Pi (0 < Pi < 1). C. Shannon, vào năm 1948, đã đưa ra công thức sau nhằm xác định độ bất định của sự kiện: Khi được cung cấp thêm thông tin, số trạng thái và xác suất xảy ra của mỗi trạng thái sẽ khác đi và ta sẽ nhận được một độ bất định mới l2 nào đó (bé hơn l1). Như vậy, thông tin bổ sung đã làm giảm độ bất định và hiệu số (l1 - l2) được xem là lượng tin của thông tin mới bổ sung. Thực ra, trước đó vào năm 1928, R. Hartley đã xét trường hợp riêng khi p1 = p2 = = pn = 1/n. Khi đó độ bất định sẽ là log2. Có thể ứng dụng công thức Hartley để tính lượng tin trong trường hợp đơn giản khi khả năng tồn tại ở một trong hai trạng 8
  5. thái của sự kiện là như nhau (đồng xác suất: p1 = p2 = 1/2). Ðộ bất định trong trường hợp này sẽ là log22-1. Trong máy tính, các thông tin được biểu diễn bằng hệ đếm nhị phân. Tuy chỉ dùng hai ký số là 0 và 1 mà ta gọi là bit nhưng hệ nhị phân đã giúp máy tính biểu diễn - xử lý được trên hầu hết các loại thông tin mà con người hiện đang sử dụng như văn bản, hình ảnh, âm thanh, video, 3. CÁC HỆ ĐẾM VÀ CÁC PHÉP TÍNH 3.1. Khái niệm hệ đếm & hệ đếm nhị phân Các chữ số cơ bản của một hệ đếm là các chữ số tối thiểu để biểu diễn mọi số trong hệ đếm ấy. Ví dụ Hệ thập phân có các chữ số cơ bản: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Hệ nhị phân có các chữ số cơ bản: 0, 1. Ðặc biệt hệ thập lục phân có các chữ số cơ bản được ký hiệu là 0, , 9, A, B, C, D, E, F. Nếu một số có giá trị lớn hơn các số cơ bản thì nó sẽ được biểu diễn bằng cách tổ hợp các chữ số cơ bản theo công thức sau: n n-1 X = an an-1 a1 a0 = anb + an-1b + + a1b + a0 (*) trong đó: b là cơ số hệ đếm, a0, a1, a2, , an là các chữ số cơ bản X là số ở hệ đếm cơ số b. Ví dụ Hệ thập phân: X = 123 thì X = 1 * 102 + 2 * 101 + 3 với b=10 Hệ nhị phân: X = 110 thì X = 1 * 22 + 1 * 21 + 0 với b=2 9
  6. 3.2. Chuyển đổi giữa các hệ đếm Qui tắc 1 Ðể chuyển đổi một số từ hệ thập phân sang hệ có cơ số b (b 10) ta áp dụng cách làm sau: Lấy số thập phân chia cho cơ số b cho đến khi phần thương của phép chia bằng 0, số đổi được chính là các phần dư của phép chia theo thứ tự ngược lại. Ví dụ Cho X = 610 nghĩa là X = 6 trong hệ thập phân thì X sẽ được đổi thành 1102 trong hệ nhị phân. Cách đổi như hình sau Qui tắc 2 Ðể chuyển đổi một số từ hệ cơ số b về hệ thập phân ta sử sụng công thức (*) Ví dụ 2 1 Cho X = 1102 thì X= 1 * 2 + 1 * 2 + 0 = 6. Bảng chuyển đổi giữa hệ nhị phân, thập lục phân và thập phân như sau Thập phân Nhị phân Thập lục phân 0 0 0 1 1 1 10
  7. 2 10 2 3 11 3 4 100 4 5 101 5 6 110 6 7 111 7 8 1000 8 9 1001 9 10 1010 A 11 1011 B 12 1100 C 13 1101 D 14 1110 E 15 1111 F Qui tắc 3 Ðể chuyển số từ hệ nhị phân về hệ thập lục phân ta thực hiện như sau: Nhóm lần lượt 4 bit từ phải sang trái, sau đó thay thế các nhóm 4 bit bằng giá trị tương ứng với hệ thập lục phân (tra theo bảng chuyển đổi trên). Ví dụ: X = 11’10112 = 3B16 Qui tắc 4 Ðể chuyển số từ hệ thập lục phân sang hệ nhị phân ta thực hiện như sau: ứng với mỗi chữ số sẽ được biểu diễn dưới dạng 4 bit. 11
  8. Ví dụ: X = 3B16 = 0011’10112= 11’10112 4. TỔNG QUAN CẤU TRÚC CỦA MÁY TÍNH VÀ CÁC THIẾT BỊ NGOẠI VI 4.1. Đơn vị xử lý trung tâm - CPU và bộ nhớ 4.1.1. Cách làm việc của CPU Ðơn vị xử lý trung tâm (Central Processing Unit) - CPU là một mạch xử lý dữ liệu theo chương trình được thiết lập trước. Nó là một mạch tích hợp phức tạp gồm hàng triệu transitor trên một bảng mạch nhỏ. Phần lớn người dùng không biết và cũng không cần biết đến cái gì trên CPU. Một CPU có thể thi hành hàng triệu lệnh mỗi giây, để như vậy, trong một CPU tiêu biểu phải có nhiều thành phần phức tạp với các chức năng khác nhau hoạt động nhịp nhàng với nhau để hoàn thành các tập lệnh chương trình. Ở đây chúng ta sẽ xem qua các thành phần căn bản bên trong của một CPU. Arithmetic Logic Unit (ALU) - đơn vị số học luận lý: bao gồm một số thanh ghi - register, thường là 32 hay 64 bit. Nó thực hiện các lệnh của đơn vị điều khiển và xử lý tín hiệu. Theo tên gọi, đơn vị này dùng để thực hiện các phép tính số học đơn giản (cộng, trừ, nhân, chia số nguyên) hay phép tính luận lý đối với dữ liệu (so sánh lớn hơn, nhỏ hơn, ). Tập lệnh chương trình được lưu giữ tại bộ nhớ chính - thông thường thì trên các chip nằm ngoài CPU - CPU đọc lệnh từ bộ nhớ qua đơn vị truyền tin - bus unit giữa bộ nhớ nguyên thủy và CPU. Ðơn vị nạp lệnh - Prefetch unit: ra chỉ thị cho đường truyền đọc các lệnh được lưu giữ tại một địa chỉ bộ nhớ riêng biệt. Ðơn vị này không chỉ định vị và nạp lệnh được thi hành kế tiếp mà còn nạp cả các lệnh lần lượt sau nữa vào hàng chờ sẵn sàng hoạt động. 12
  9. Ðơn vị giải mã - Decode unit: ra chỉ thị cho đường truyền đọc các lệnh được lưu giữ tại một địa chỉ bộ nhớ riêng biệt. Ðơn vị này không chỉ định vị và nạp lệnh được thi hành kế tiếp mà còn nạp cả các lệnh lần lượt sau nữa vào hàng chờ sẵn sàng hoạt động. Ðơn vị nối ghép đường truyền - Bus Interface Unit: bộ phận dẫn truyền điều phối các thông tin. Những nhà sản xuất vi xử lý luôn phát triển các kỹ thuật nhằm tăng tốc độ xử lý cho CPU. Và như vậy, bộ nhớ ẩn - cache memory là một bộ nhớ nhỏ tốc độ cao đặt ngay bên trong bộ xử lý và nối trực tiếp với mạch xử lý để lưu trữ các lệnh chuẩn bị được thực hiện, hay các lệnh thường xuyên được dùng để sẵn sàng cho CPU. Bộ nhớ này chỉ do bộ xử lý kiểm soát, người sử dụng không thể thâm nhập được, nhằm phục vụ cho việc tăng tốc độ tính toán của bộ xử lý. Loại cache memory nằm ngay trong bản thân bộ xử lý thường được gọi là cache nội hay cache sơ cấp - primary, hay còn gọi là cache L1 (cache level 1). Loại cache memory nằm ngoài bộ xử lý thường được gọi là cache ngoại hay cache thứ cấp - secondary cache, hay còn gọi là cache L2 (cache level 2). Ðơn vị điều khiển - control unit: có nhiệm vụ thông dịch các lệnh của chương trình và điều khiển hoạt động xử lý, được điều tiết chính xác bởi xung nhịp đồng hồ hệ thống. Mạch xung nhịp hệ thống - system clock: dùng để đồng bộ các thao tác xử lý trong và ngoài CPU theo các khoảng thời gian không đổi, khoảng thời gian chờ giữa hai xung gọi là chu kỳ xung nhịp. Tốc độ theo đó xung nhịp hệ thống tạo ra các xung tín hiệu chuẩn thời gian gọi là tốc độ xung nhịp - tốc độ đồng hồ tính bằng triệu đơn vị mỗi giây - Mhz. Thanh ghi – register: là phần tử nhớ tạm trong bộ vi xử lý dùng lưu dữ liệu và địa chỉ nhớ trong máy đang thực hiện tác vụ với chúng. 13
  10. 4.1.2. Lưu trữ sơ cấp: Bộ nhớ máy tính Công việc chính của CPU là thi hành các mã lệnh của chương trình, nhưng trong cùng thì CPU chỉ có khả năng giải quyết một ít trong phần dữ liệu. Như vậy phần còn lại của dữ liệu được đọc vào phải cần một chỗ nào đó để lưu giữ lại sẵn sàng cho CPU xử lý, và RAM hay bộ nhớ chính sẽ nhận nhiệm vụ này. Bộ nhớ truy cập ngẫu nhiên - Random Access Memory (RAM): là loại thiết bị lưu trữ sơ cấp. Chip RAM gồm nhiều mạch điện tử có chức năng lưu trữ các lệnh và dữ liệu chương trình một cách tạm thời. Chính thuật ngữ truy cập ngẫu nhiên cũng cho thấy tính chất của loại bộ nhớ này. Mỗi vị trí lưu trữ trong RAM đều có thể truy cập trực tiếp, nhờ đó các thao tác truy tìm và cất trữ có thể thực hiện rất nhanh. Nội dung lưu trữ trong RAM không cố định - volatile memory, có nghĩa phải luôn có nguồn nuôi để lưu trữ nội dung thông tin đó - mất điện là mất tất cả. Bộ nhớ cố định - nonvolatile memory: được gọi bộ nhớ chỉ đọc - Read Only Memory - ROM. Chính là vì loại cố định nên nó vẫn duy trì nội dung nhớ khi không có điện, nhờ đó người ta dùng ROM để chứa chương trình BIOS không thay đổi. Không phải lúc nào loại này cũng ẩn trong vỏ CPU. Nhiều thiết bị trò chơi điện tử cũng dùng hộp, có khả năng tháo lắp, dựng một mạch ROM lưu trữ thường xuyên trò chơi các chương trình . Ngoài ra còn một số loại bộ nhớ khác nữa trong máy tính. EPROM - Erasable Programable ROM - bộ nhớ chỉ đọc có thể lập trình lại. Loại này thường dùng để lưu giữ các thông tin cần thiết cho việc khởi động máy tính. RAM còn có loại SRAM - RAM tĩnh, DRAM - RAM động, Video RAM - RAM cho màn hình chuyên phục vụ hình ảnh. 14
  11. 4.1.3. Cách làm việc của bộ nhớ Bộ nhớ (Memory): là một mạch tích hợp phức tạp gồm hàng triệu tế bào nhớ (storage cell) - các tế bào nhớ này chính là đơn vị lưu dữ kiện. Các thông tin trong bộ nhớ có thể là tập lệnh chương trình hay là dữ liệu của hình ảnh, các con số của phép tính số học hay luận lý và cũng có khi là các ký tự chữ cái. Mỗi byte bộ nhớ đều có địa chỉ riêng để CPU có thể truy cập đến dữ liệu trong đó. Bộ nhớ có nhiều loại với đặc điểm cấu trúc tính năng sử dụng khác nhau, nhưng về căn bản đều dùng để lưu dữ kiện nhằm phục vụ cho việc xử lý thông tin của CPU, và nó có thể là loại nằm ngay trên CPU hay nằm ngoài CPU. Một máy tính cá nhân bình thường ngày nay thường lắp từ 64 đến 256 megabytes bộ nhớ - bộ nhớ được nói đến trong câu này có nghĩa là loại bộ nhớ ngoài CPU mà ta thường gọi là các thanh RAM. Các vi mạch DRAM được kết nối với nhau trên một bản mạch nhỏ được gọi là RAM, có khi là SIMM (single in - line memory module) - module nhớ hàng chân kép. Tùy lượng vi mạch nhớ và cấu trúc, các SIMM hay DIMM có thể có dung lượng từ 1 MB đến 32 MB hoặc hơn; các thế hệ cũ thì có 30 chân (thường dùng từ các máy 486DX trở về trước), thế hệ thông dụng hiện nay dùng loại 72 chân (từ 486DX cho tới các máy hiện đại nhất). Đã xuất hiện loại DIMM - SDRAM có tốc độ lý thuyết 10ns (so với RAM EDO là 60ns), có số chân là 168 chân cũng được dùng rộng rãi với một số bo mạch chọn lọc. Các RAM này được cắm vào các khe quy định sẵn trên mạch hệ thống chính. Xét về chi tiết thì nơi nhớ - tế bào nhớ giống như một cái hộp thư.Một hộp thư hiện đại cho một địa chỉ có thể lưu giữ một byte thông tin. Ðĩa khởi động có thể là đĩa cứng, đĩa mềm hay đĩa CD. Ðĩa này có chứa các tập lệnh giúp cho hệ thống khởi động và biết cách nạp hệ điều hành từ đĩa vào bộ nhớ. 15
  12. Khi khởi động máy, CPU tự động (đã qui định trước) đọc thông tin lưu trong bộ nhớ chỉ đọc - ROM và thi hành. Hầu hết các hệ thống máy tính đều có ROM để lưu dữ kiện để điều khiển hệ thống. Các chương trình trên ROM thường được gọi là BIOS - hệ thống xuất nhập cơ sở. Các lệnh cần thực hiện nào đã nạp vào bộ nhớ thì CPU có khả năng thực hiện chúng. Như vậy, khi bật máy, CPU đọc thông tin trên bộ nhớ ROM - thi hành nó, sau đó đọc đến thông tin trên đĩa khởi động và nạp các thông tin hệ điều hành trên đĩa vào bộ nhớ RAM. Các thông tin lưu trên RAM ở các tế bào nhớ, tức là nằm sẵn trong RAM - và CPU có thể thực hiện các tác vụ. 4.2. Thiết bị nhập 4.2.1. Bàn phím Ðể thể hiện những lá thư, những con số, hay các ký tự đặc biệt bằng máy tính, người ta dùng bàn phím nối với máy tính, kích hoạt ứng dụng thích hợp rồi gõ các phím nào cần gõ cho ra các từ, câu muốn có. Khi bạn gõ - nhấn một ký tự nào trên bàn phím, trên màn hình sẽ hiện ra chữ ấy (giả định đang trong trình ứng dụng thích hợp). Các phím mũi tên, Alt, Ctrl, Enter không gửi một chữ nào cho máy mà là các lệnh đặc biệt nào đó. Cũng liên quan đến bộ mã ký tự ta đã nêu ở trên, bàn phím được thiết kế sao cho tiện dụng nhất đối với từng khu vực ngôn ngữ. Loại cấu trúc bàn phím thông dụng và được chấp nhận nhiều nhất trên thế giới là loại bàn phím QWERT. Tên QWERT thoạt đầu nghe có vẻ xa lạ lắm, nhưng đơn giản rằng đó là tên các phím chữ hàng đầu tiên bên trái theo thứ tự. Tên này để phân biệt với một số loại bàn phím ít được dùng khác có trật tự sắp xếp các phím không giống loại này. Có thể bạn sẽ thắc mắc vì sao không chọn theo thứ tự ABC cho dễ nhớ? Không đơn giản như ta thường nghĩ, các nhà khoa học đã nghiên cứu kỹ 16
  13. lưỡng về mặt ngôn ngữ học về tần suất xuất hiện của các chữ cái, dựa vào đó đưa ra một thứ tự sao cho những chữ cái hay dùng nhất ở vị trí phím dễ dùng nhất. 4.2.2. Thiết bị chỉ điểm - Pointing Device Hàng triệu người dùng máy tính hiện nay dùng bàn phím để gõ các chữ cái và con số, nhưng để ra lệnh cho máy, định vị con trỏ, họ không chỉ dùng bàn phím mà còn dùng một thiết bị đặc biệt thông dụng khác gọi là: con chuột - mouse. Con chuột dùng để chuyển dịch một ký hiệu hay một đối tượng được chọn từ nơi này sang nơi khác trên màn hình. Con chuột thường được thể hiện thông qua con trỏ trên màn hình. Khi người sử dụng di chuyển con chuột trên mặt bàn thì con trỏ cũng di chuyển trên màn hình. Một con chuột có một, hai, hay ba nút nhấn có thể dùng để gởi các tín hiệu đến máy tính. Nhiều người dùng không quan tâm đến con chuột - cũng chẳng sao, nhưng ngày càng nhiều các chương trình ứng dụng đặt con chuột vào vị trí quan trọng để điều khiển chương trình. Cũng như nhiều linh kiện khác, chuột cũng có nhiều chủng loại với cấu tạo và điểm mạnh yếu khác nhau nhưng cùng có chung nhiệm vụ. Con chuột chuẩn: gồm các nút nhấn ở trên và một hòn bi ở dưới, nó có cấu tạo nhỏ gọn nối máy tính bởi một sợi dây, có thể dịch chuyển dễ dàng và đó cũng là nhiệm vụ của nó. Con chuột bóng - Trackball: nó cũng gồm các thành phần như trên, nhưng viên bi lại hướng lên trên. Thường được chế tạo to lớn khó di chuyển chuột được, tác vụ di chuyển chuột thực hiện trực tiếp bằng chính người sử dụng dùng tay lăn viên bi, nút nhấn vẫn không thay đổi chức năng. Phiến nhấn - touch pad: là một phiến nhỏ nhạy cảm với những áp lực nhấn lên nó dù nhỏ, người dùng di chuyển con trỏ bằng cách rê ngón tay trên phiến đó. 17
  14. Một vài thiết bị đặc biệt khác cũng được xem là các thiết bị chỉ điểm, ví dụ như: Cần điền khiển - Joystick: cũng được xem là thiết bị tính năng chỉ điểm đặc biệt, nó giống như cần điều khiển trong máy trò chơi điện tử. Màn hình cảm ứng - Touch Screen: màn hình thiết kế đặc biệt để có thể cảm nhận được sự chỉ điểm của ngón tay hoặc vật gì đó đối với màn hình. Bàn vẽ - Graphic table: là một thiết bị đặc dụng dành cho những nhà thiết kế hay họa sỹ, bàn vẽ càng tốt thì độ nhạy cảm về áp lực trên nó càng cao. Bàn vẽ sẽ chuyển trực tiếp những hình ảnh được vẽ trên bàn vẽ thành các hình ảnh trên máy tính. 4.2.3. Thiết bị đọc Một số các thiết bị đọc bị giới hạn bởi khả năng đưa dữ liệu - văn bản trực tiếp trên giấy, hay chuyển các thông tin đã được in ra cho máy tính xử lý. Một số thiết bị nhập khác (được gọi là thiết bị đọc) đã được chế tạo nhằm đáp ứng cho những nhu cầu thực tế này: Thiết bị đọc đánh dấu quang học - Optical-mark readder: dùng ánh sáng phản xạ để xác định vị trí đã được đánh dấu viết chì trong công tác kiểm tra sản phẩm sản xuất dây chuyền để trả lời trên một cái thẻ theo hình thức quy định trước. Thiết bị đọc mã vạch - Barcode reader: dùng ánh sáng để đọc mã sản phẩm (UPC), mã kiểm tra hay một số loại mã vạch khác. Thiết bị đọc chữ in từ tính - magnetic-ink character reader: để đọc các con số theo mẫu được in bằng một loại mực đặc biệt có từ tính dùng trong việc kiểm tra. Cây đũa thần - wand reader: là tên thiết bị dùng tia sáng để đọc các ký tự chữ và số được viết bằng một thiết bị đánh dấu 18
  15. đặc biệt trên vùng dành riêng cho chúng, thường dùng cho các thẻ bán hàng hay thẻ tín dụng. Người ta dùng các thiết bị này rất nhiều trong các cửa hàng, các nơi thanh toán chuyển đổi tiền, nối với một thiết bị đầu cuối POS (điểm bán - point of sale). Thiết bị đầu cuối (Terminal) này sẽ gửi thông tin nhận từ cây đũa thần đến một máy tính (có thể là một mainframe), máy tính này sẽ xác định cơ sở dữ liệu cần thiết phù hợp (giá cả, cước thuế, số tiền phải trả cho món hàng ) và gởi lại thông tin ấy cho POS. Ðó là một trong các trường hợp ứng dụng, nguyên tắc làm việc cũng tương tự với thẻ tín dụng. Cây viết máy tính - pen-based computer: như phần trước có nói đến, trong các loại máy hệ xách tay có loại nhỏ gọn nhất có thể bỏ vào áo khoác - loại trợ lý kỹ thuật số hay còn gọi là Máy thông tin cá nhân (personal digital assistant - personal comunicatior) nó dùng một cây viết để đưa dữ liệu vào máy tính, thiết bị này là Cây viết máy tính - pen-based computer.Ðể nhập liệu, người ta viết trực tiếp lên màn hình phẳng của máy tính. Xét về trường hợp nhập liệu trực tiếp từ giấy tờ văn bản đã nói ở trên còn phương pháp dùng chương trình nhận dạng chữ. Chương trình này chuyển các hình ảnh của văn bản đưa vào máy tính bằng máy quét ảnh thành các ký tự chữ cái, độ chính xác của các chương trình này khoảng hơn 99% với ngôn ngữ chỉ có các ký tự Latin. 4.2.4. Các thiết bị số hóa thế giới thực Các máy tính hiện đại đều là dạng số hóa, nó làm việc và lưu trữ thông tin dưới dạng các con số nhị phân. Ðể lưu thông tin dạng analog - tín hiệu tuần tự - thì thông tin đó trước hết phải được chuyển thành dạng được số hóa từ đó phát sinh nhu cầu cần các thiết bị số hóa. Ðể số hóa hình ảnh thì dùng máy quét - scanner, số hóa âm thanh thì cần mạch âm thanh - sound card, số hóa hình ảnh thật thì dùng máy quay phim hay máy ảnh 19
  16. kỹ thuật số, thể hiện hình ảnh số thì dùng màn hình máy tính, thể hiện ảnh ra giấy thì dùng máy in và nhiều nhu cầu khoa học khác dùng các thiết bị số hóa đặc biệt khác nữa. Nói chung "cả thế giới thực của chúng ta đều có thể được số hóa". Máy quét ảnh - scanner: là một thiết bị nhập liệu có thể biến những hình ảnh thành những thông tin số hóa đại diện cho nó. Máy quét ảnh hiện nay có nhiều chủng loại và kích cỡ khác nhau, thông dụng nhất là loại máy quét phẳng - flatbed scanner. Còn loại máy quét cầm tay - handheld scanner, nhưng thay vì viên bi định vị là bóng đèn chân không. Còn một loại khác gọn nhẹ thường được đặt giữa màn hình và bàn phím gọi là máy quét phụ trợ – shet-fed scanner. Máy ảnh số – digital camera: cũng bằng phương pháp tương tự như scanner, máy ảnh số dùng để chụp hình ảnh bên ngoài, thay vì lưu hình ảnh lên phim thì nó lưu ảnh dưới dạng thông tin số hóa. Khác với máy quét ảnh, máy ảnh số không bị giới hạn bởi mặt phẳng hình ảnh, nó hoàn toàn có thể chụp được những hình ảnh mà máy ảnh thông thường chụp được. Ảnh chụp từ máy ảnh số có thể được lưu trên đĩa hay loại thiết bị lưu trữ nào đó tùy mỗi loại máy. Loại máy ảnh kỹ thuật số này ngày càng trở nên rộng rãi hơn, nó đặc biệt hữu dụng trong việc chụp những hình ảnh ở những nơi mang tính tôn nghiêm vì hầu như nó không gây ra một tiếng động đáng kể nào. Máy quay phim số – digital video camera: hoạt động với phương thức tương tự máy ảnh số nhưng là lưu giữ những hình ảnh động thay vì hình ảnh tĩnh, ngoài ra nó còn thu được âm thanh nữa. Loại máy quay phim số này rất đắc dụng trong lĩnh vực truyền thông đa phương tiện hay hội đàm qua màn ảnh. Thiết bị âm thanh số hóa – Audio digitalizer: là micro, loa, CD, các nhạc cụ điện tử. Với thiết bị khác nhau, âm thanh có thể được đưa vào dưới nhiều dạng khác nhau và đều được chuyển thành dạng số hóa. Ứng dụng của nó trong việc chế tạo 20
  17. các hệ máy mới là vô cùng phong phú, ngày nay hầu như bạn có thể bắt gặp dòng chữ âm thanh kỹ thuật số – digital audio trên hầu hết các thiết bị âm thanh hiện đại như máy đĩa CD nhạc, CD video Thiết bị cảm ứng: Trong các ứng dụng khoa học, các thiết bị cảm ứng được dùng rất nhiều để đưa dữ kiện bên ngoài vào máy tính dưới dạng số hóa. Ðó là điều hiển nhiên bởi máy tính chỉ xử lý được những thông tin dạng số. Ứng dụng thông thường nhất là các thiết bị đong, đo như nhiệt kế điện tử, máy dự báo thời tiết, thiết bị kiểm soát môi trường, thiết bị kiểm soát mức độ ô nhiễm về âm thanh lẫn ô nhiễm về không khí và nhiều ứng dụng khác nữa. 4.3. Thiết bị xuất Máy tính nhận thông tin, xử lý và phải xuất thông tin. Như vậy nơi để nhận dữ liệu xuất ra sau khi xử lý gọi là bộ phận xuất hay thiết bị xuất. Hiện nay người ta thường dùng hai thiết bị xuất chủ yếu là màn hình và máy in. 4.3.1. Xuất ra màn hình Màn hình máy tính (tạm dịch từ Video Monitor) hay thiết bị đầu cuối hiển thị hình ảnh (video display terminal - VDT) sẽ cho ta thấy những ký tự mà ta gõ trên bàn phím hoặc các thông điệp từ máy tính. Những thế hệ màn hình mới có thể thể hiện chi tiết các hình ảnh cũng như chữ, số và các ký hiệu với đủ loại màu sắc khác nhau, thường gọi là màn hình màu, tên gọi như vậy để phân biệt loại màn hình đơn sắc dùng cho các hệ máy cũ (loại máy XT). Có hai chữ monitor và display mà người ta hay dùng lẫn lộn, dù đó là hai khái niệm khác nhau. Display - Màn hiển thị: là thiết bị hiển thị tạo ra hình ảnh từ tín hiệu video, như ống phóng điện tử hay màn hình tinh thể lỏng hay bất kỳ thiết bị hiện hình nào khác. Còn monitor là toàn bộ các mạch phụ trợ và 21
  18. cả màn hiển thị, tất cả lắp trong vỏ máy, người ta thường gọi monitor là màn hình. Màn hình có hai loại chính là: màn hình kiểu thiết kế giống như tivi dùng các bóng đèn tia điện tử cathode CRT (cathode ray tube) và màn hình tinh thể lỏng LCD (liquid crystal display). Tuy rằng LCD là loại màn hình phẳng nhỏ gọn hơn CRT nhiều, nhưng giá của LCD lại quá cao so với CRT. Các màn hình CRT ngày nay cho chất lượng hình ảnh tốt hơn màn hình LCD. Thông thường người ta chỉ dùng LCD cho các máy tính dạng xách tay. Màn hình CRT này về cơ bản gồm một bóng đèn hình lớn chứa ba ống phóng điện tử cho ba màu đỏ, xanh lá cây và xanh dương. Ba màu cơ bản này sẽ tạo ra được mọi màu khác cần hiển thị. Mỗi điểm ảnh sẽ do ba yếu tố RGB hợp thành tạo ra màu sắc cần thiết. Màn hình được nối kết với máy tính thông qua bộ điều hợp hiển thị - video adapter hay display adapter. Nó còn có tên gọi là cạc màn hình - display card, video card.Bộ điều hợp hiển thị là một bảng mạch điện tử được cắm trong máy tính ở khe cắm mở rộng. Hình ảnh là thông tin được lưu ở bộ nhớ màn hình - VRAM. Khả năng của bộ điều hợp hiển thị sẽ quyết định tốc độ làm tươi hình ảnh, tốc độ hiện hình, độ phân giải, mức độ màu có thể hiển thị. Bộ điều hợp hiển thị được phân loại theo độ rộng bus dữ liệu của nó: Bộ điều hợp hiển thị 32 bit: có đường dẫn dữ liệu nội bộ 32 bit - có thể xử lý 4 byte dữ liệu cùng lúc. Bộ điều hợp hiển thị: có đường dẫn dữ liệu nội bộ 64 bit - có thể xử lý 8 byte dữ liệu cùng lúc. Bộ điều hợp hiển thị 128 bit: có đường dẫn dữ liệu nội bộ 128 bit - có thể xử lý 16 byte dữ liệu cùng lúc. Ðường dẫn dữ liệu càng rộng thì khả năng của bộ điều hợp càng cao. Do đó, loại 32 bit xem ra đã lỗi thời, mức chuẩn hiện nay là loại 64 bit để có thể hiển thị phân giải cao, lên đến 1280x1024 dpi. Còn loại 128 bit có tốc độ cao thích hợp với yêu cầu công tác nhiều hình vẽ như thiết kế đồ họa chẳng hạn. 22
  19. Kích thước của màn hình cũng gần như một cái tivi. Thông số dùng để phân loại màn hình máy tính và tivi được quy định giống nhau - là độ dài đo được của đường chéo màn hiển thị. Một máy tính để bàn thông thường có màn hình thừ 14 đến 15 inch. Hình ảnh hiện trên màn hiển thị là sự kết hợp của nhiều chấm nhỏ - gọi là điểm ảnh - pixel.Ðộ phân giải của màn hiển thị thông thường là 72 điểm trong một inch cho mỗi chiều ngang và dọc. (Ðơn vị tính độ phân giải viết tắt là dpi - điểm trong một inch: dots per inch) Ðộ phân giải càng cao, các điểm ảnh càng sít lại với nhau, hình ảnh càng mịn hơn và đẹp hơn. Còn một cách nói khác về kích thước màn hình, thay vì nói về độ dài đường chéo thực sự của màn hiển thị, người ta nói về mức độ phân giải có thể của màn hiển thị. Nếu nói màn hình 800 x 600 tức là chiều ngang gồm 800 điểm, chiều dọc gồm 600 điểm. Yếu tố khác nói về khả năng card màn hình là độ sâu màu có thể hiển thị - color depth. Ví dụ như, màn hình đơn sắc thì thể hiện 2 bit cho mỗi điểm, mỗi bit có thể hiển thị 2 màu hoặc màu này hoặc màu kia (các màn hình đơn sắc ban đầu thường có màu xám, xanh hay nâu). Nếu mỗi điểm có 8 bit màu thì có khả năng thể hiện 256 màu - 28 - đây là khả năng thông thường mà hầu hết tất cả các máy tính hiện nay đều thể hiện được. Loại cao cấp hơn có thể chấp nhận 24 bit màu, tức khoảng hơn 16 triệu màu (16777216 màu - 224), hiện nay trên máy vi tính đã có thể thể hiện 32 bit màu - chấp nhận 4.294.967.296 màu. Số màu có thể hiển thị càng nhiều thì hình ảnh càng trung thực sắc nét và sống động - và chắc chắn là đẹp hơn hình ảnh trên tivi nhiều lần. 4.3.2. Xuất ra giấy Việc kết xuất dữ liệu ra màn hình là nhanh chóng nhưng là một sự sao chép không mang tính lưu trữ mà thiên về tính thông báo. Máy in được gắn với máy tính sẽ là thiết bị xuất có giá trị 23
  20. lưu trữ, bởi các bản in ra giấy. Máy in có nhiều loại và được chia thành hai nhóm chính: máy in gõ hay máy in không gõ (impact printer or nonimpact printer) Máy in gõ: là các máy in theo dòng hay theo ma trận điểm. Các máy in kim là loại này, có đặc điểm là tốc độ in chậm, ồn ào, độ phân giải thấp cho chất lượng in ấn trung bình. Máy in này dùng một đầu kim chạy suốt chiều ngang giấy để ấn các kim xuống giấy (qua lớp băng mực) theo tín hiệu điểu khiển, nhiều lần như vậy tạo nên bản in. Số đầu kim của máy càng cao thì độ phân giải đạt được càng cao, các loại máy in 9,18 kim hầu như không còn được sử dụng nữa, thông dụng nhất của máy in loại này có lẽ là có thể in trên khổ giấy lớn mà giá máy rẻ và có thể nhân thành nhiều bản bằng giấy than do sự gõ truyền lực. Máy in không gõ: là loại máy in như tên gọi của nó - không dùng tác động cơ tạo nên chữ mà bằng các kỹ thật hiện đại khác. Máy in nhiệt - dùng các xung điện từ mạch kích thích của máy in làm cho đầu kim ma trận điểm nóng lên và nguội đi rất nhanh, nhưng đầu kim này không gõ vào giấy mà do sự nóng/ nguội theo ma trận điểm nó sẽ làm đổi màu các điểm trên loại giấy đặc biệt tạo nên các ký tự cần in. Tốc độ máy in tương đối nhanh và ít tốn điện, nhưng phải dùng loại giấy in nhiệt - thermal paper.Ðể khắc phục nhược điểm phai màu của máy in nhiệt, người ta dùng công nghệ máy in truyền mực bằng nhiệt - thermal fusion printer. Ðầu in loại này cũng là ma trận các kim nhiệt được nung nóng nhanh bằng các xung tín hiệu thích hợp của mạch điện tử trong máy. Hai loại này dùng phổ biến trong máy in xách tay vì ít tốn điện. Máy in phun mực - inkfet printer: cũng là loại máy in không gõ, đồng thời đầu in cũng không tiếp xúc giấy in, nó thực hiện thao tác in bằng cách phun các giọt mực lên các hạt mực li ti tạo nên bản in. Trong máy in phun ngày nay thiết bị phun dùng tinh thể áp điện - nó dao động cơ học với tần số cố định 24
  21. khi có điện áp điều khiển tác động vào. Khi đặt trong ống dẫn mực nó đẩy mực ra khỏi ống và hút thêm mực khác vào - như một máy bơm. Một hình thái khác của máy in phun là máy in phun bong bóng - bubbe jet printer: dùng phần tử nung nóng thay cho tinh thể áp điện, bơm tinh thể có thể đóng mở tần số 5kHz nên có thể cho phép tốc độ in nhanh hơn. Loại này bị hạn chế bởi tốc độ in, do các phần tử in phải có thời gian nguội nếu không sẽ gây nhiều vấn đề phức tạp khác, nhưng ưu điểm dùng điện áp thấp từ 24V đến 50V làm cho nó tiện dụng hơn. Do tính chất in phun như vậy, nên loại máy này có thể dùng với mọi loại giấy, độ nét và độ mịn của bản in có chất lượng cao, đôi khi rất khó phân biệt với loại máy in laser. Loại máy in phun rẻ hơn laser nhiều nhưng chi phí in cao hơn. Máy in laser: dùng công nghệ in tĩnh điện (electrostatic - ES) là phương pháp in tạo hình ký tự bằng cách tạo ra điện tích tĩnh điện và làm chảy mực lên giấy nhờ quá trình nung nóng. Vậy khác hoàn toàn với các loại máy in trước dùng đầu in để in, loại máy in này tạo sản phẩm thông qua một quá trình phức tạp. Quá trình in tĩnh điện thực hiện trong hệ thống tạo hình - image formation system (IFS) có các bước: xóa trống nhạy sáng để gạt bỏ các hạt mực còn trên đó, và làm trống trở nên trung hòa điện tích. Nạp điện lên bề mặt trống bằng điện áp âm rất lớn (khoảng 5000V) - sẵn sàng ghi hình. Máy in giải mã tín hiệu theo từng dòng máy tính đưa sang và xây dựng bản đồ bit của trang in, dùng chùm tia sáng ghi hình bản đồ này lên mặt trống. Mực được phun vào mặt trống đang quay và bị hút vào các điểm được chiếu sáng và nhiễm điện tích âm - phương pháp ghi hình đen. Còn nếu mực được phun vào các điểm không được chiếu sáng gọi là phương pháp ghi hình trắng, cách này hình đen hơn, dày hơn. Giấy được đưa qua một bộ phận nạp điện tích dương trước khi đi qua trống để hút điện tích âm là các hạt mực. Sau đó qua hệ thống ép nhiệt nóng 180oC làm hạt mực chảy ra và dính luôn vào giấy. Với phương pháp đó, có thể tốc độ in lên đến 10 trang văn bản trong một giây. Một hộp mực tiêu chuẩn 25
  22. cho máy in thông thường có thể in được từ 200-5000 bản in tùy độ phức tạp hình ảnh. Một kỹ thuật mới thay thế tia laser trong cách ghi hình ảnh là dùng thanh nhiều đèn hay dãy nhiều cửa đóng mở nguồn sáng đèn huỳnh quang bằng tinh thể lỏng để chiếu sáng vào mặt trống Ðó là loại máy in di-ốt phát quang - light emitting diode printer và máy in cửa sập tinh thể lỏng - liquid crystal shutter printer. Máy in màu: hoạt động dựa trên nguyên tắc các điểm màu cơ bản li ti xen kẽ nhau tạo nên nhiều màu sắc phong phú. Ðể thể hiện màu sắc theo nguyên tắc này có nhiều phương pháp phối màu khác nhau. Kiểu RGB - tức là Red-Green-Blue (Ðỏ, Xanh lá cây, Xanh dương) giống như cách tạo màu của tivi và màn hiển thị máy tính. Cách này dùng ba màu Ðỏ, Xanh lá cây, Xanh dương làm màu căn bản, từ đó tạo ra các màu khác. Kiểu HSB - tức dựa trên các yếu tố Hue-Saturation-Brightnes tức là sắc màu, lượng màu, độ sáng. Kiểu CMYK sử dụng tỷ lệ pha trộn các màu Cyan-xanh dương sáng lợt, Magenta-hồng tím, Yellow-vàng, black-đen. Trong ngành in ấn chế bản thì gọi màu C - cyan là xanh, M - magenta là đỏ, Y - yellow là vàng, K - black là đen. Vì màu sắc là một sự cảm nhận nhạy cảm ngay cả với con người, nên đối với máy in màu, việc thể hiện màu phụ thuộc rất nhiều vào thiết bị. Có thể một loại màu nhưng mỗi máy mỗi khác, bạn có thể in thử cùng một ảnh màu trên các máy in khác nhau sẽ nhận được kết quả in khác nhau về sắc thái màu. Ðể tối ưu hóa việc in màu cho chuẩn xác, người ta đưa ra hệ thống hợp màu pantone (pantone color matching system) không phụ thuộc thiết bị. Người thiết kế sẽ chọn một màu từ sổ tay kỹ thuật màu sắc, xác định màu đó bằng phần mềm thích hợp, in bằng một máy in có thiết kế cho chuẩn pantone. Kiểu hòa màu CMYK thích hợp cho khả năng hỗ trợ hệ màu pantone. Vì vậy cách in theo chế độ màu CMYK là phương pháp in chuẩn nhất trên máy 26
  23. tính - và là phương án in màu duy nhất đối với các máy in sách báo hiện nay trên thế giới. Những máy in màu hiện nay dùng trong các văn phòng cơ quan hay gia đình thường là loại máy in phun màu, máy in thăng hoa màu hay máy in truyền sáp nhiệt. Các loại máy in này có giá thấp phù hợp khả năng tài chính của mọi người, thông thường thì từ 300 đến 2000 USD. Các thế hệ máy in phun màu mới hiện nay có khả năng in với độ phân giải trên 1000 dpi sẽ làm cho hình ảnh mịn hơn và đẹp gần như ảnh thật. Còn loại máy in laser màu không được phổ biến lắm do giá khá cao, và thường chỉ trang bị cho các công ty thiết kế tạo mẫu. Hiện nay còn có máy vẽ - plotter là một họ máy anh em với máy in phun. Do kỹ thuật in phun ra đời nên ranh giới giữa máy in phun màu khổ lớn và máy vẽ rất khó phân biệt. Loại máy in này hầu như chỉ dùng ngôn ngữ in postscript có thể dùng để in các bản vẽ thiết kế, hình ảnh, bản đồ lớn với khổ giấy A0 và thích hợp với nhiều loại giấy. Với ngôn ngữ in cao cấp và các thiết kế phun mực tiên tiến, hình ảnh in từ loại máy in này có chất lượng khá cao. 4.3.3. Xuất ra âm thanh Máy tính không chỉ kết xuất ra những gì chỉ để thấy mà còn xuất ra âm thanh để nghe nữa. Máy tính có thể phát ra các tiếng động, âm nhạc hay bất cứ cái gì mà bạn muốn nghe. Những máy tính ngày nay đều có khả năng tổng hợp và xuất âm thanh. Khác với các máy tính đơn thuần lúc trước chỉ có thể phát ra tiếng beep từ một loa nhỏ xíu của máy tính, bằng loại mạch chuyên xử lý âm thanh, máy tính có thể nhận vào hay xuất ra những âm thanh tổng hợp đa chiều. Và hiển nhiên đó là những âm thanh số hóa. Việc gắn thêm bo mạch xử lý âm thanh - sound card chỉ xảy ra với các máy tương thích IBM, các máy MAC hiện nay thì chức năng này được thiết kế sẵn không cần bo mạch hỗ trợ. 27
  24. Hiển nhiên để âm thanh phát ra cần phải có thêm một hay nhiều loa, ngoài ra máy tính có thể nối với bộ khuếch đại, bộ lọc âm thanh, micro, và cũng có thể là một cây đàn điện tử có chuẩn MIDI. Những máy tính tiêu biểu hiện nay đều có gắn thiết bị CD, với thiết bị này, bạn có thể nghe nhạc, hay xem phim với hình ảnh đẹp và âm thanh chuẩn xác vô cùng hấp dẫn. Còn với các chương trình dạy phát âm ngoại ngữ thì nghe như người thật phát âm bên tai bạn vậy. Âm thanh trong máy tính hiện nay chia thành hai dạng MIDI và Wave. Loại âm thanh MIDI chỉ dùng để thể hiện âm thanh của các loại nhạc cụ đã được số hóa (các nhạc cụ điện tử) theo một bảng mã qui định sẵn, do đó kích thước tập tin dạng này nhỏ hơn dạng Wave với cùng thời gian thể hiện. Còn Wave dùng để thể hiện mọi thứ âm thanh mà ta có thể nghe và tổng hợp được như tiếng hát, giọng nói, tiếng mèo kêu, xe máy 4.3.4. Làm việc với máy tính khác Thế giới tin học hiện nay đang trong cuộc cách mạng Internet và các giải pháp mạng. Và thiết bị không thể thiếu trong việc nối kết Internet và mạng máy tính qua mạng truyền thông là modem. Vì máy tính hoạt động với các tín hiệu số, đường truyền điện thoại lại dùng các tín hiệu analog, do đó để có thể truyền dữ liệu bằng đường dây điện thoại nhất thiết phải có thiết bị điều biến và giải điều biến – Modulation - demodulation, viết tắt là modem, có thể gọi tắt là bộ điều biến. Thông qua modem, bạn có thể truy cập dữ liệu từ một máy chủ khác ở nơi nào đó trên thế giới, với nguyên lý tương thụ, bạn cũng có thể điều khiển được sự hoạt động của một máy tính khác đặt ở nơi khác - thao tác này thường gọi là điều khiển truy cập từ xa (remote access) bằng một chương trình chuyên biệt. Việc này mở ra một khả năng to lớn và linh động cho công tác quản lý của bạn, với sự cấp quyền cho phép, bạn có thể vẫn hoạt động trên một máy tính nào đó mà không cần có mặt thật sự ở đó. 28
  25. 4.4. Lưu trữ thứ cấp Máy tính có các thiết bị ngoại vi có khả năng nhận và xuất dữ liệu - đó là các ổ đĩa máy tính, nơi ghi nhớ các thông tin dữ liệu. Những thiết bị này gọi là các thiết bị lưu trữ thứ cấp - secondary starage (thiết bị lưu trữ sơ cấp - primary storage là bộ nhớ máy tính). Khác với thiết bị lưu trữ sơ cấp khi ngắt điện là mọi thứ trong RAM đều không còn, thiết bị lưu trữ thứ cấp này có thể lưu dữ kiện ngay cả khi không có nguồn nuôi, xét về lý thuyết, dữ liệu trên loại này có thể tồn tại vĩnh viễn và có thể được đọc, ghi, sửa hay xóa lúc này hay lúc khác. Có hai phương pháp lưu dữ kiện tạo nên hai họ khác nhau là dựa trên từ tính và dựa trên khả năng ứng dụng quang học. 4.4.1. Ðĩa từ tính Có hai loại chủ yếu là đĩa mềm và đĩa cứng. Ðĩa mềm, có thể hiểu đơn giản là loại đĩa dung lượng thấp, nhỏ gọn tháo lắp dễ dàng, nhiều đĩa dùng chung một ổ đĩa. Hiểu như vậy để có thể phân biệt với đĩa cứng là loại ổ đĩa thường lắp hẳn bên trong máy, ít được tháo rời, phức tạp, và bản thân nó là thiết bị hoàn chỉnh đọc ghi với dung lượng lớn. 4.4.2. Ðĩa mềm - floopy disk Đĩa mềm gồm vỏ bảo vệ và một đĩa plastic nhỏ có phủ vật liệu từ (oxit sắt, oxit niken hoặc oxit coban pha với vật liệu không từ tính hay đất hiếm). Dữ liệu thông tin dạng số sẽ được đại diện bởi các hạt từ tính, các hạt này do có tính từ tính, nên bằng một phương pháp nào đó nó được xác định một trong hai hướng rõ rệt - như vậy thể hiện được số 0 hay số 1. Ðĩa mềm cũng trải qua nhiều thế hệ, những khác nhau giữa các hệ đĩa mềm chỉ là quanh vấn đề dung lượng nhớ của nó chứ về nguyên tắc hoạt động của đĩa cũng như ổ đĩa không có thay đổi lớn nào. Ngày nay người ta chỉ còn dùng loại đĩa mềm 3.5 inch thường gọi là đĩa 1.44MB, nhưng cũng có loại 2.88MB. Loại 5.25 inch 29
  26. gần như không còn được dùng nữa. Ðĩa mềm có tính cơ động cao, nhưng bị hạn chế về dung lượng nhớ, hiện nay các chương trình hầu như không thể chạy trên đĩa mềm như cách đây khoảng 5 năm, cho nên đĩa mềm chủ yếu dùng sao lưu dữ liệu, vả lại tốc độ đọc ghi của đĩa mềm rất thấp - bù lại giá đĩa mềm tương đối rẻ, bạn có thể mua một hộp đĩa mềm với giá khoảng 50.000 đồng (10 hay 11 đĩa). Ðĩa cứng - Hard disk Ổ đĩa cứng gồm vỏ cứng bảo vệ, các bộ phận điều khiển xuất nhập, nguồn, và đĩa từ tính. Bộ khung vỏ bảo vệ thường là hợp kim nhôm đúc ở áp lực cao, cũng có hai cỡ 5.25 inch và 3.5 inch, và thông dụng nhất vẫn là loại 3.5 inch. Dung lượng ổ cứng không phải bị chi phối bởi vỏ ổ cứng mà ở đĩa từ. Ðĩa từ của ổ đĩa cứng thường làm từ nhôm, thủy tinh hay gốm - phủ một lớp vật liệu từ và lớp bảo vệ ở cả hai mặt. Ổ đĩa cứng có thể có nhiều đĩa từ xếp chồng lên nhau trên trục môtơ quay. Ðể hoạt động đọc ghi, ổ đĩa cứng còn có các đầu từ, môtơ dịch chuyển đầu từ, mạch chính, mạch điện tử điều khiển, và thường có bộ nhớ cache. Ðĩa cứng rất đa dạng về dung lượng, có thể từ vài chục MB đến vài nghìn MB hay hơn nữa, và phụ thuộc nhiều vào các chuẩn kỹ thuật giao tiếp. Loại ổ đĩa cứng thường dùng trong máy vi tính hiện nay khoảng 10GB đến 20GB, một con số khổng lồ nếu so với cách đây 5 năm khi mà ổ cứng chỉ có thể từ 100Mb đến 200Mb, thậm chí có máy không trang bị ổ đĩa cứng nữa. Các ổ đĩa cứng giao tiếp với máy thông qua một cáp dữ liệu cắm vào mạch điều khiển. Những máy tính thế hệ tiền PCI - tức là từ VesaLocalBus trở về trước giao tiếp giữa máy và thiết bị ngoại vi đều thông qua bảng mạch giao tiếp - thường gọi là card IO (input - output), tức là con chuột, ổ đĩa cứng, ổ đĩa mềm, máy in, joystick, đều nối vào đây. Ðể hoạt động, các ổ cứng giao tiếp với máy thông qua các chuẩn ESDI, IDE, SCSI. Chuẩn ESDI (Enhanced Small Device Interface) xuất hiện đầu 30
  27. năm 1983 dùng phương pháp mã hóa RLL, tốc độ có thể đạt đến khoảng 24MB mỗi giây, là dạng giao tiếp câm nên các điều khiển quan trọng đều do card quản lý. Chuẩn IDE (Intelligent Drive Electronic - Intergrated Drive Electronic) cũng còn gọi là ATA (AT Attachment) dùng loại mạch điện tử ổ đĩa thông minh, là giao tiếp ở mức hệ thống. Chuẩn này nối với máy bằng một cáp nguồn 4 chân và một cáp dữ liệu 40 chân. Loại ổ đĩa này có tốc độ khá cao nên được dùng trong hầu hết các máy vi tính hiện nay, giá thành cũng rẻ hơn so với các loại ổ đĩa cứng khác. Chuẩn giao tiếp SCSI (Small Computer System Interface) là một cấu trúc bus độc lập có thể truyền dữ liệu với tốc độ cao, từ 4Mb/giây đến khoảng 10Mb/giây, được ứng dụng với ổ đĩa cứng tạo nên một khả năng lưu trữ cao với tốc độ đọc ghi cao. Ðể dùng được, cần có một bảng mạch điều hợp SCSI, tuy nhiên một card SCSI này có thể nối tiếp đến 7 thiết bị theo chuẩn này. Ðĩa floptical Là loại ổ đĩa từ mềm, có hình dáng giống như đĩa 3.5 inch, nhưng dùng phương pháp định vị quang học để đọc ghi, nên mật độ dữ liệu trên đĩa cao hơn, dung lượng nhớ lớn hơn. Thiết bị này không ghi dữ liệu bằng quang học, chỉ làm thao tác định vị thôi. Tuy nhiên do giá thành cao nên dù có khả năng lưu đến hơn 20MB, loại này vẫn không phổ dụng. Ổ băng ghi lưu Cũng là thiết bị lưu trữ từ tính, nhưng loại này khác với các loại trên ở tính chất truy cập tuần tự của nó, do đó chỉ dùng sao lưu chứ không dùng để làm việc hằng ngày như thiết bị truy cập ngẫu nhiên - đĩa cứng, đĩa mềm. Ổ băng ghi lưu gồm một hộp băng và cuộn băng từ cỡ 0.25 inch. Loại này rất đa dạng về chủng loại và dung lượng, tùy yêu cầu công việc mà bạn lựa chọn. 31
  28. Ổ đĩa tháo lắp ZIP Dùng loại đĩa có kích thước cũng khoảng 3.5 inch, dung lượng lên đến 100Mb trên một đĩa. Tốc độ đọc ghi trung bình, kỹ thuật dùng ở đây là định vị quang học để ghi dữ liệu. Nếu dùng với card SCSI, tốc độ không thua gì ổ cứng IDE. 4.4.3. Ðĩa từ quang Ðĩa từ quang - Magneto optical drive, thường gọi tắt là MO, là thiết bị kết hợp giữa từ tính và quang học để lưu dữ liệu. Ðĩa từ tính, dùng ánh sáng laser làm tác nhân đọc ghi. Dung lượng của loại 5.25 inch là 1.3GB, loại 3.5inch là 230MB. Công nghệ này phù hợp để lưu trữ, theo các chuyên gia, có thể bảo đảm dữ liệu 50 năm so với 5 năm của ổ đĩa cứng, ổ mềm, băng từ. 4.4.4. Ðĩa quang học Gọi là đĩa quang học, tức là vấn đề cốt lõi về kỹ thuật - đọc ghi dữ liệu được thực hiện trên nguyên tắc quang học, dùng tia sáng laser. So với hệ thống từ tính, ổ quang có ba điểm khác biệt chính: độ chính xác cao của thao tác quang học nên ổ đĩa quang có thể có dung lượng cao hơn ổ đĩa từ gấp nhiều lần so với ổ đĩa từ. Ðộ bền dữ liệu ghi bằng phương pháp quang học cao hơn so với phương pháp từ tính nhiều lần, tối thiểu cũng 50 năm. Ðĩa quang có thể tháo lắp dễ dàng như một đĩa mềm mà hiệu quả hơn nhiều, do đó ngày càng phổ dụng hơn. Ðĩa CD - compact disc là loại này. Xuất phát từ nhu cầu âm thanh, CD âm thanh ra đời chứa dữ liệu dưới dạng các hốc lõm, khi CD quay tia laser sẽ phát đến đĩa và nhận sự phản xạ khác nhau giữa điểm lõm và điểm không lõm ứng với số 0 và 1 hệ nhị phân. Ðĩa CD-ROM ta dùng hiện nay cũng hoạt động theo nguyên tắc đó, vì là loại đĩa CD chứa dữ kiện chỉ đọc được nên có tên có tên CD-ROM (Compact Disc Read Only Memory). Thông thường dữ liệu có 32
  29. thể đưa vào loại đĩa quang giá rẻ 680MB như chúng ta dùng rộng rãi hiện nay, đồng thời các loại đĩa âm thanh cũng có thể đọc hiểu và hoạt động được bằng ổ đĩa CD của máy tính, nhưng đầu đọc của máy CD âm thanh thì không thể đọc được đĩa CD dữ liệu. Nói là CD-ROM - chỉ đọc, nhưng dĩ nhiên là phải có một lần nào đó ghi dữ liệu lên đĩa rồi mới đọc, thao tác này theo nguyên tắc khắc trên đĩa các điểm lõm hay không lõm đại diện cho số 0, 1 bằng một nguồn phát tia laser công suất lớn. Người ta tạo một đĩa gốc trước trên nguyên tắc này bằng đầu CD có thể ghi trên một đĩa CD mới, sau đó âm bản của đĩa gốc được tạo ra bằng quá trình mạ điện hoặc photopolymer. Tiến trình nhân bản thực hiện bằng cách phun polycarbonate - trong suốt, nhẹ, bền, ổn định, không nhiễm bẩn - nên đĩa CD giữ được thông tin gần như vĩnh viễn. Như vậy, bạn có thể hiểu về bản chất các đĩa CD được chép lại bán ở một số dịch vụ tin học thực ra là một dạng đĩa gốc, do đó khi sử dụng phải tuyệt đối cẩn thận vì nó không hề có một lớp bảo vệ polycarbonate như các đĩa CD được phát hành chính quy hay các đĩa CD nhạc. Khi mà các đĩa CD-ROM đã gần như trở nên một chuẩn không thể thiếu trong hầu hết các máy tính multimedia thì lại xuất hiện một thành viên mới trong họ đĩa quang học mà được dự đoán sẽ là thiết bị lưu trữ chủ đạo thế kỷ 21 - DVD. DVD - Digital Vidéo Disc tức là đĩa video kỹ thuật số hay Digital Versatile Disc - đĩa đa năng kỹ thuật số là một công nghệ chỉ mới ra đời gần đây. Cũng như CD dần dần thay thế đĩa mềm bởi dung lượng của nó. DVD thay thế CD-ROM bởi DVD có thể lưu ít nhất 3.8 GB và có thể đạt đến 17GB. DVD có kích thước giống như CD (120mm đường kính và dày 1.2mm) cũng làm bằng nguyên liệu như CD. Dữ liệu trên DVD sẽ được ghi vào đĩa với mật độ cao hơn, sít hơn nhiều so với CD, lượng thấu kính trong đầu đọc nhiều hơn để tăng độ chính xác - và đầu đọc sẽ dùng laser có sóng ngắn hơn, có thể là tia laser đỏ - laser 33
  30. hồng ngoại. Quan trọng nhất là kỹ thuật DVD cho phép loại đĩa có hai lớp trên một mặt, nên với mỗi lớp khoảng hơn 4GB thì loại đĩa hai lớp hai mặt hoàn toàn có thể chứa đến 17GB dữ liệu. 4.4.5. Ðường truyền – cổng – thiết bị ngoại vi Trong một máy tính thông thường, CPU và bộ nhớ được gắn với bo mạch chính cùng một vài linh kiện cần thiết khác nữa. Những thông tin chuyển qua lại giữa các linh kiện thông qua một mạch lưới gọi là các bus. Các bus này có thể có 8, 16 hay 32 đường dẫn và do đó gọi là các bus 8 bit, bus 16 bit hay bus 32 bit. Hiển nhiên rằng xa lộ đa luồng làm tăng lưu lượng xe có thể chạy qua, ở đây cũng có thể các bus chấp nhận số bit lớn thì càng có thể chuyển tải nhiều thông tin cùng một lúc, như vậy sẽ làm tăng đáng kể tốc độ hệ thống. Có rất nhiều bus trong máy tính, chúng nối kết các phần tử linh kiện trong máy với nhau. Một số bus nối với các khe - slot trên bo mạch. Người dùng có thể thiết lập thêm các tính năng cho máy tính bằng cách cắm các bo mạch - card có tính năng riêng nào đó vào các khe này. Một số bus khác thì được nối với các cổng nằm ngoài - chính xác là ló ra khỏi vỏ máy một chút. Các thiết bị ngoại vi có thể nối với máy tính thông qua các cổng có sẵn của máy, hay thông qua một card chuyên biệt cắm vào các khe cắm trên bo mạch chính - điều này thật tiện lợi. Cho đến nay đã có nhiều loại bus như sau: Bus mở rộng ISA Trên bo mạch chính của các kiểu máy tính cũ tương thích IBM PC/XT (Bộ vi xử lý 8088 hay 8086) người ta dùng bus mở rộng có khe cắm 62 chân gồm 3 đường dây đốt, 5 dây nguồn nuôi, 20 đường địa chỉ và 16 đường tín hiệu điều khiển. Bus mở rộng XT bị giới hạn nhiều mặt, bus dữ liệu 8 bit, dịch vụ hệ thống không đủ dùng (các ngắt DMA). Thế nên các nhà sản 34
  31. xuất đưa ra bus ISA mở rộng cho máy AT dùng vi xử lý 80286 - tức là máy 286 với bus dữ liệu 16bit. Bus này gồm hai đoạn khe cắm rời nhau, một đoạn 62 chân như kiểu dùng cho XT, một đoạn bổ sung 36 chân - bổ sung 5 dịch vụ ngắt, 8 đường dữ liệu, 4 đường địa chỉ và một số đường chức năng điều khiển. Loại này vẫn tương thích với 8 bit. Tốc độ truyền loại này đạt khoảng 8MB mỗi giây (ISA - Industry Standard Architecture). Bus MCA (Micro Chanel Architecture) Năm 1987, bus này được đưa ra riêng cho loại máy PS/2 của IBM, nó là kiểu thiết kế bus 32bit. Nó gồm 32 bit dữ liệu, 32 đường địa chỉ (có khả năng địa chỉ hóa 4GB bộ nhớ), một kênh âm thanh, khả năng VGA cài sẵn. Tốc độ của nó đạt 20MB mỗi giây nên có thể đáp ứng cho các CPU đến 199MHz. Tuy nhiên, do loại này không tương thích với bus AT và máy PC nên nếu muốn dùng, người dùng phải thay toàn bộ các thiết bị tương thích MCA nên không được hưởng ứng. Do đó nó không được phát triển và cuối cùng IBM phải tự hủy bỏ. Bus EISA (Enhanced ISA) Là loại bus mở rộng AT được nâng cao do liên minh 9 công ty lớn (AST, Compaq, Epson, Hewlett - Packard, NEC, Olivetti, Tandy, Wyse, Zenith Data System) cùng hợp tác phát triển. Nó được thiết kế để cạnh tranh với các MCA và đã thành công trong thời gian dài. Nó hoàn toàn tương thích với ISA - 16bit và ISA - 8bit của XT. Bus EISA có tốc độ 33MB mỗi giây hoạt động với 8.33MHz. EISA còn có một phiên bản mới nâng cấp tốc độ lên 132MB mỗi giây, loại này vẫn còn dùng trong một số server và mạng. Local bus Là loại bus mở rộng kéo dài trực tiếp bus dữ liệu trong bộ vi xử lý ra ngoài. Năm 1992 VESA Local Bus ra đời (VESA - 35
  32. Video Electronics Standard Association). Nếu bo mạch chính 33MHz thì tốc độ bus có thể đạt 107MB mỗi giây, tuy nhiên hầu hết các bo mạch cùng có VESA Local Bus và ISA. Bus mở rộng PCI Loại này có 32 bit hay 64 bit dựa vào thiết kế do Intel xây dựng năm 1992. PCI-Peripheral Component Interface bus, là kiểu trung gian giữa bus dữ liệu ngoài của vi xử lý và bus vào ra chung của máy tính, nó là loại bus mở rộng hoàn chỉnh nên nó cho phép các nhà sản xuất hoàn toàn có thể loại bỏ hẳn loại bus ISA. Thiết bị ngoại vi là các thiết bị giúp máy tính liên thông được với thế giới bên ngoài. Bàn phím nối liên kết người dùng và máy tính để nhập liệu, màn hình-máy in sẽ thể hiện kết quả xử lý của máy tính sau các tác vụ gửi cho người dùng, ngoài ra còn vô số các thiết bị khác như máy quét ảnh, máy ảnh số mà chúng ta đã làm quen ở các phần trên. Ðối với một số hệ máy, còn có một chuẩn cho máy được gọi là chuẩn PCM-CIA. Chuẩn này cho phép một khe cắm có thể đáp ứng nhiều khả năng khác nhau với từng loại card khác nhau được cắm vào. Khe cắm này cho các máy tính cá nhân xách tay, khe PCM-CIA có thể chấp nhận card (có thể từ 8MB lên đến vài chục MB bổ sung cho RAM), card Fax-Modem, card điều khiển CD nằm ngoài và một số thiết bị ngoại vi khác. Chuẩn này vẫn đang được tiếp tục phát triển. 36
  33. CHƯƠNG 2 TỔNG QUAN VỀ GIẢI QUYẾT VẤN ĐỀ BÀI TOÁN TRÊN MÁY TÍNH 1. KHÁI NIỆM VẤN ĐỀ-BÀI TOÁN Khi nào chúng ta phải suy nghĩ? Có thể thấy ngay là khi phải trả lời câu hỏi của giáo viên, làm một bài toán hoặc giải quyết một vấn đề như mua gì tặng bạn ngày sinh nhật Có thể nói, mọi cá nhân cũng như mọi cộng đồng xã hội phải liên tục giải quyết những vấn đề và bài toán đặt ra trong quá trình tồn tại và phát triển. Cuộc sống là một chuỗi vấn đề mà ta phải nói: “Thông thường, nhiều người quan niệm vấn đề có nghĩa rộng hơn bài toán và bài toán là một loại vấn đề mà để giải quyết phải liên quan ít nhiều đến tính toán: bài toán trong vật lý, hóa học, xây dựng, kinh tế Cho nên từ vấn đề vẫn thường được dùng với nghĩa rộng hơn trong toán học”. Nhà toán học cổ Hy Lạp Pitago đã phân chia mọi vấn đề mà con người phải giải quyết thành hai loại: + Theorema là vấn đề cần được khẳng định tính đúng-sai. Chúng ta thường quen với loại vấn đề này qua việc chứng minh các định lý trong toán học, đặc biệt là hình học. + Problema là vấn đề cần tìm giải pháp để đạt được một mục tiêu xác định từ những điều kiện ban đầu nào đó. Các ví dụ minh họa điển hình cho loại bài toán này là bài toán dựng hình, tổng hợp hóa chất, tìm đường đi ngắn nhất, thi công công trình nhanh nhất, mua sắm tiết kiệm nhất Như nhiều nhà nghiên cứu việc giải quyết vấn đề - bài toán đã chỉ ra sau này, cả hai loại vấn đề mà Pitago nêu ra đều có thể diễn đạt theo một sơ đồ chung: 37
  34. A →B Ở đây: - A có thể là giả thiết, điều kiện ban đầu - B có thể là kết luận, mục tiêu cần đạt. - → là suy luận, giải pháp cần xác định Theo sơ đồ này, việc cho một vấn đề - bài toán có nghĩa là cho A và B. Việc giải quyết vấn đề - bài toán có ý nghĩa là xuất phát từ A dùng một số hữu hạn các bước suy luận có lý hoặc hành động thích hợp để đạt được B. Để cho việc giải quyết vấn đề - bài toán được xác định cũng phải chỉ ra tập các thao tác cơ bản được dùng trong suy luận hoặc hành động, nghĩa là những điều kiện ràng bược đối với yếu tố “→” trong sơ đồ đã nêu. Đối với tin học sơ đồ này được hiểu với nghĩa A là Input (thông tin vào), B là Output (thông tin ra) và →là chương trình tạo thành từ các lệnh cơ bản của máy cho phép biến đổi A thành B. Như ta đã thấy, chương trình chỉ là một cách mã hóa lại thuật toán hoặc thuật giải đã được xây dựng để giải quyết vấn đề - bài toán đã cho. Điều khó khăn nhất hiện nay đối với việc xây dựng thuật toán hoặc thuật giải là tính không xác định của hầu hết mọi vấn đề và bài toán. Tính không xác định này thường thể hiện qua: + Thông báo về A hoặc B không đầy đủ, rõ ràng. Ngay cả bài toán trong toán học thường được xem là mẫu mực của việc diễn đạt chính xác cũng giả định phần lớn thông tin về A và B tiềm ẩn trong đầu người giải. Thông báo về A và B chỉ là biểu tượng gợi nhớ đến các thông tin tiềm ẩn đó. Ví dụ, bài toán: Cho: số nguyên duơng n, các số thực a0, a1, , an. n Tìm: Số thực x sao cho a0 + a1x + + anx = 0. 38
  35. Khi một người không biết số nguyên dương, số thực là gì thì không hiểu được bài toán chứ chưa nói đến việc tìm cách giải. + Thông báo về các điều kiện đặt ra cho cách giải (→) thường được nêu ra trong bài toán hoặc vấn đề. Đối với các bài toán trong sách thì thường được hiểu ngầm được phép dùng mọi kiến thức về toán đã học cho tới phần đó của giáo trình. Có thể nói: thuật toán hay thuật giải cung cấp đủ lượng thông tin (không thừa không thiếu) để giải quyết vấn đề - bài toán. Chính vì những lý do nêu trên, hiện nay để giải một vấn đề trên máy tính, việc thiết kế xây dựng thuật giải vẫn chủ yếu được thực hiện bởi con người. Từ những thông tin được phản ánh rõ ràng hoặc tiềm ẩn trong các thông báo A, B hoặc “→”, cùng với các tri thức liên quan có trong đầu người giải quyết vấn đề - bài toán sẽ được kiến tạo nên thuật toán hay thuật giải cần thiết. Đây là công việc có tính trí tuệ cao và quyết định sự thành công của việc giải quyết vấn đề - bài toán được đặt ra. Từ khi có máy tính điện tử, các nhà khoa học đã tìm cách chuyển giao dần dần các bước giải quyết vấn đề cho máy. Đã có nhiều công trình nghiên cứu tự động hóa việc lập chương trình khi thuật toán được viết theo một qui định chặt chẽ nào đó. Tuy nhiên, muốn tự động hóa xây dựng thuật toán hay thuật giải – nghĩa là chỉ cần đưa ra nội dung vấn đề vào máy, một chương trình có sẵn trong máy sẽ phân tích vấn đề, tìm hoặc xây dựng thuật toán hay thuật giải rồi biến thành chương trình giải quyết vấn đề - bài toán. Chúng ta cần phải làm sao biểu diễn được nội dung bài toán - vấn đề, cũng như mọi tri thức liên quan đến bài toán - vấn đề dưới dạng tường minh và hết sức đầy đủ. Đây chính là lĩnh vực hết sức mới mẻ và có ý nghĩa thực tiễn vô cùng lớn lao: xây dựng một trí tuệ nhân tạo cho máy. Gần đây, đã có một số kết quả nghiên cứu biểu diễn tri thức trong máy và xây dựng được một số hệ giải bài toán tự động trong một số lĩnh vực hẹp của logic, đại số, hình học . Những hệ này thực 39
  36. chất là một cơ sở tri thức về lĩnh vực vấn đề cần giải quyết được kết hợp với một chương trình suy diễn để tạo sinh được thuật toán hay thuật giải cần thiết. Những hệ giải quyết vấn đề dựa trên cơ sở tri thức mở rộng hơn cùng với các chương trình “tư duy” mạnh hơn đang được phát triển và ứng dụng trong rất nhiều lĩnh vực. Những hệ này thường được gọi là hệ chuyên gia hay hệ cơ sở tri thức. 2. CÁC BƯỚC GIẢI QUYẾT VẤN ĐỀ BÀI TOÁN BẰNG MÁY TÍNH Việc sử dụng máy tính điện tử (MTÐT) để giải quyết một vấn đề nào đó thường được quan niệm một cách không chuẩn xác, đơn giản đó chỉ là việc lập trình thuần túy. Thực ra, đó là cả một quá trình phức tạp bao gồm nhiều giai đoạn phát triển mà lập trình chỉ là một trong các giai đoạn đó (thậm chí chưa chắc đã là phần việc quan trọng nhất). Các bước quan trọng của toàn bộ quá trình được liệt kê dưới đây: Bước 1. Xác định vấn đề - bài toán Bước đầu tiên của bước phân tích hệ thống là nhằm phát biểu chính xác vấn đề - bài toán, làm rõ những yêu cầu mà người sử dụng đòi hỏi. Sau khi nghiên cứu vấn đề được đặt ra, người phân tích viên thiết lập mối phụ thuộc giữa các dữ kiện và kết quả phải tìm. Trên cơ sở có được mô hình vấn đề - bài toán, người phân tích viên sẽ đánh giá, nhận định tính khả thi của vấn đề - bài toán được đặt ra có đáng phải giải quyết không? Bước 2.Lựa chọn phương pháp giải Có thể có nhiều cách khác nhau để giải quyết vấn đề - bài toán đã thiết lập ở bước 1. Các phương pháp có thể khác nhau về thời gian thực hiện. chi phí lưu trữ dữ liệu, độ chính xác Nói chung không có phương pháp tối ưu về mọi phương diện. 40
  37. Tùy theo nhu cầu cụ thể mà lựa chọn phương pháp thích hợp. Việc lựa chọn trên cũng cần căn cứ vào khả năng xử lý tự động mà ta sẽ sử dụng. Bước 3. Xây dựng thuật toán hoặc thuật giải Xây dựng mô hình chặt chẽ, chính xác hơn và chi tiết hóa hơn phương pháp đã lựa chọn. Xác định rõ ràng dữ liệu vào, ra cho các bước thực hiện cơ bản và trật tự thực hiện các bước cơ bản đó. Nên áp dụng phương pháp thiết kế có cấu trúc, từ thiết kế tổng thể tiến hành làm mịn dần từng bước. Bước 4. Cài đặt chương trình Mô tả thuật giải bằng chương trình. Dựa vào thuật giải đã được xây dựng, căn cứ quy tắc của một ngôn ngữ lập trình để soạn thảo ra chương trình thể hiện giải thuật thiết lập ở bước 3. Bước 5. Hiệu chỉnh chương trình Ở bước 4, nói chung chúng ta không tránh khỏi sai sót. Ở bước 5 này chúng ta cho chương trình chạy thử để phát hiện và điều chỉnh các sai sót nếu tìm thấy. Có hai loại lỗi: - Lỗi cú pháp: là lỗi do không tuân thủ đúng các quy tắc viết chương trình trên một ngôn ngữ lập trình cụ thể. - Lỗi ngữ nghĩa: là lỗi làm sai lạc ý nghĩa hoặc dẫn đến bế tắc của chương trình. Lỗi cú pháp thường dễ phát hiện và hiệu chỉnh hơn lỗi ngữ nghĩa. Cần phải nói rằng, việc hiệu chỉnh chương trình khá phức tạp, mất nhiều thời gian và công sức. Việc xây dựng tốt, phù hợp, đầy đủ các bộ dữ liệu để kiểm chứng chương trình là hết sức quan trọng, giúp phát hiện ra các lỗi ngữ nghĩa của chương trình cũng như có thể có vấn đề gì đó bị bỏ sót. Bước 6. Thực hiện chương trình 41
  38. Cho máy tính thực hiện chương trình. Tiến hành phân tích kết quả thu được. Việc phân tích kết quả nhằm khẳng định kết quả đó có phù hợp hay không. Nếu không, cần kiểm tra lại toàn bộ các bước một lần nữa. Nói chung, dù thận trọng đến mức nào đi nữa thì sau mỗi bước thực hiện nêu trên cũng không khẳng định được kết quả thực hiện từng bước là đúng đắn tuyệt đối. Hơn nữa, như ở bước 5, ta chỉ hiệu chỉnh tất cả các lỗi đã được phát hiện. Còn có thể có sai sót khác của chương trình với một bộ dữ liệu nào khác phức tạp hơn mà ta chưa có cơ hội để phát hiện trước đó. Do đó, ta không thể khẳng định được rằng, chương trình đúng tuyệt đối, không còn sai sót nữa. Như vậy, việc giải quyết một vấn đề cụ thể thực hiện qua hai giai đoạn. Giai đoạn đầu là giai đoạn quan niệm, gồm các bước phân tích, lựa chọn mô hình, xây dựng thuật giải, cài đặt chương trình. Giai đoạn sau là khai thác và bảo trì chương trình. Trong quá trình sử dụng, nói chung thường có nhu cầu về cải tiến, mở rộng chương trình do các yếu tố của bài toán ban đầu có thể thay đổi. 3. THUẬT TOÁN VÀ THUẬT GIẢI 3.1. Thuật toán Thuật toán là một khái niệm cơ sở của Toán học và Tin học. Hiểu một cách đơn giản, thuật toán là một tập các hướng dẫn nhằm thực hiện một công việc nào đó. Ðối với việc giải quyết một vấn đề - bài toán thì thuật toán có thể hiểu là một tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. Như vậy, thuật toán là một phương pháp thể hiện lời giải của vấn đề - bài toán. Số bước hữu hạn của thuật toán và tính chất dừng của nó được gọi chung là tính hữu hạn. Số bước hữu hạn của thuật toán là một tính chất khá hiển nhiên. Ta có thể tìm ở đâu một lời giải vấn đề - bài toán có vô số bước giải? Tính "không mập mờ" và "có thể thực thi được" gọi chung là tính xác định. 42
  39. Giả sử khi nhận một lớp học mới, ban giám hiệu yêu cầu giáo viên chủ nhiệm chọn lớp trưởng mới theo các bước sau: 1. Lập danh sách tất các học sinh trong lớp; 2. Sắp thứ tự danh sách học sinh; 3. Chọn học sinh đứng đầu danh sách để làm lớp trưởng. Khi nhận được thông báo này, giáo viên chắc chắn sẽ rất bối rối vì không hiểu là trong danh sách học sinh cần có những thông tin gì? Danh sách chỉ cần họ tên, hay cần thêm ngày tháng năm sinh? Có cần thêm điểm trung bình không? Yêu cầu 2 lại càng gây nhiều thắc mắc. Cần phải sắp xếp danh sách theo chiều tăng dần hoặc giảm dần? Sắp theo chỉ tiêu gì? Theo tên, theo ngày tháng năm sinh hay theo điểm trung bình chung Giả sử sắp theo điểm trung bình thì nếu có hai học sinh cùng điểm trung bình thì học sinh nào sẽ sắp trước, học sinh nào sẽ sắp sau? Hướng dẫn ở trên vi phạm tính chất "không mập mờ" của thuật toán. Nghĩa là, có quá nhiều thông tin còn thiếu để làm cho các bước 1, 2 được hiểu đúng và hiểu theo một nghĩa duy nhất. Nếu sửa lại một chút ít thì hướng dẫn trên sẽ trở nên rõ ràng hơn rất nhiều và có thể gọi là một thuật toán chọn lớp trưởng! 1. Lập danh sách tất các học sinh trong lớp theo hai thông tin: Họ và Tên; Ðiểm trung bình cuối năm. 2. Sắp hạng học sinh theo điểm trung bình theo thứ tự giảm dần (từ điểm cao đến điểm thấp). Hai học sinh có cùng điểm trung bình sẽ có cùng hạng. 3. Nếu chỉ có một học sinh có hạng nhất thì chọn học sinh đó làm lớp trưởng. Trường hợp có nhiều học sinh đồng hạng nhất thì chọn học sinh có điểm môn Toán cao nhất làm lớp trưởng. Nếu vẫn còn nhiều hơn một học sinh đồng hạng nhất và có cùng điểm môn Toán cao nhất thì tiến hành bốc thăm. Ở đây chúng ta cần phân biệt mập mờ và sự chọn lựa có quyết định.Mập mờ là thiếu thông tin hoặc có nhiều chọn lựa 43
  40. nhưng không đủ điều kiện để quyết định. Còn chọn lựa có quyết định là hoàn toàn xác định duy nhất trong điều kiện cụ thể của vấn đề. Chẳng hạn trong vấn đề chọn lớp trưởng ở trên, bước 3 thể hiện một sự lựa chọn có quyết định. Tất nhiên, khi chưa lập danh sách, chưa xếp hạng theo điểm trung bình thì giáo viên không thể biết được sẽ chọn lớp trưởng theo cách nào. Nhưng khi đã sắp xong danh sách thì chỉ có một phương án chọn duy nhất. Tính "thực thi được" cũng là một tính chất khá hiển nhiên. Rõ ràng nếu trong "thuật toán" tồn tại một bước không thể thực thi được thì làm sao ta có được kết quả đúng như ý muốn? Tuy nhiên, cần phải hiểu là "thực thi được" xét trong điều kiện hiện tại của bài toán. Chẳng hạn, khi nói "lấy căn bậc hai của một số âm" là không thể thực thi được nếu miền xác định của bài toán là số thực, nhưng trong miền số phức thì thao tác "lấy căn bậc hai của một số âm" là hoàn toàn thực thi được. Tương tự, nếu ta chỉ đường cho một người đi xe máy đến một bưu điện nhưng con đường ta chỉ là đường cụt, đường cấm hoặc đường ngược chiều thì người đi không thể đi đến bưu điện được. Tính "dừng" là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thuật toán. Dĩ nhiên, mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau một thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi không thỏa tính chất này, ta nói rằng "thuật toán" bị lặp vô tận hoặc bị quẩn. Ðể tính tổng các số nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau: B1. Hỏi giá trị của n. B2. S = 0 B3. i = 1 B4. Nếu i = n + 1 thì sang bước B8, ngược lại sang bước B5 B5. Cộng thêm i vào S 44
  41. B6. Cộng thêm 2 vào i B7. Quay lại bước B4. B8. Tổng cần tìm chính là S. Ta chú ý đến bước B4. Ở đây ta muốn kết thúc thuật toán khi giá trị của i vượt quá n. Thay vì viết là "nếu i lớn hơn n" thì ta thay bằng điều kiện "nếu i bằng n+1" vì theo toán học "i = n+1" thì suy ra "i lớn hơn n". Nhưng điều kiện "i=n+1" không phải lúc nào cũng đạt được. Vì ban đầu i = 1 là số lẻ, sau mỗi bước, i được tăng thêm 2 nên i luôn là số lẻ. Nếu n là số chẵn thì n+1 là một số lẻ nên sau một số bước nhất định, i sẽ bằng n+1. Tuy nhiên, nếu n là một số lẻ thì n+1 là một số chẵn, do i là số lẻ nên dù có qua bao nhiêu bước đi chăng nữa, i vẫn khác n+1. Trong trường hợp đó, thuật toán trên sẽ bị quẩn. Tính "đúng" là một tính chất khá hiển nhiên nhưng là tính chất khó đạt tới nhất. Thực vậy, khi giải quyết một vấn đề - bài toán, ta luôn luôn mong muốn lời giải của mình sẽ cho kết quả đúng nhưng không phải lúc nào cũng đạt được. Mọi học sinh khi làm bài kiểm tra đều muốn bài làm của mình có đáp số đúng nhưng trên thực tế, trong lớp học chỉ có một số học sinh nhất định là có khả năng đưa ra lời giải đúng! Các đặc trưng khác của thuật toán Bên cạnh ba đặc trưng chính là xác định, hữu hạn và đúng, thuật toán còn có thêm ba đặc trưng phụ khác: 1. Ðầu vào và đầu ra (input/output): mọi thuật toán, dù có đơn giản đến mấy cũng phải nhận dữ liệu đầu vào, xử lý nó và cho ra kết quả cuối cùng. 2. Tính hiệu quả (effectiveness): tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh 45
  42. giá, chọn lựa cách giải quyết vấn đề - bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. Trong mục 3 của chương, ta sẽ tìm hiểu một tiêu chuẩn được dùng rộng rãi là độ phức tạp của thuật toán. 3. Tính tổng quát (generalliness): thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. Chẳng hạn giải phương trình bậc hai sau đây bằng delta đảm bảo được tính chất này vì nó luôn giải được với mọi giá trị số thực a, b, c bất kỳ. Tuy nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng thuật toán cho một dạng đặc trưng của bài toán mà thôi. Thuật toán giải phương trình bậc hai ax2 + bx + c= 0(a≠ 0) 1. Yêu cầu cho biết giá trị của 3 hệ số a, b, c 2. Nếu a = 0 thì 2.1. Yêu cầu đầu vào không đảm bảo. 2.2. Kết thúc thuật toán. 3. Trường hợp a ≠ 0 thì 3.1. Tính giá trị D = b2 - 4ac 3.2. Nếu D > 0 thì 3.2.1. Phương trình có 2 nghiệm phân biệt x1 và x2 3.2.2. Giá trị của 2 nghiệm được tính theo: 3.2.3. Kết thúc thuật toán. 3.3.Nếu D = 0 thì 3.3.1. Phương trình có nghiệm kép x0 3.3.2. Giá trị của nghiệm kép là 46
  43. 3.3.3. Kết thúc thuật toán 3.4. Nếu D 1) 2.1. Chọn hai hộp bất kỳ và đặt lên bàn cân. 2.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác. 3. Nếu còn hộp chưa được cân thực hiện các bước sau, nếu không còn hộp nào nữa, sang bước 5. 3.1. Chọn một hộp bất kỳ và để lên đĩa cân còn trống. 3.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác. 4. Trở lại bước 3. 5. Hộp còn lại trên cân chính là hộp nặng nhất. Kết thúc. 47
  44. Thuật toán Euclid tìm ước số chung lớn nhất Bài toán: Cho hai số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b. 1. Yêu cầu cho biết giá trị của a, b. 2. a0 = a 3. b0 = b 4. i = 0 5. Nếu ai khác bi thì thực hiện các thao tác sau, ngược lại qua bước 7. 5.1 Tăng i lên 1. 5.2. Nếu ai-1 > bi-1 thì ai = ai-1 - bi-1 bi = bi-1 5.3. Ngược lại bi = bi-1 - ai-1 ai = ai-1 6. Trở lại bước 5. 7. Ước số chung lớn nhất của a, b là ai . 3.2. Mở rộng khái niệm thuật toán: thuật giải Trong quá trình nghiên cứu giải quyết các vấn đề - bài toán, người ta đã đưa ra những nhận xét như sau: + Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán và cũng không biết là có tồn tại thuật toán hay không. + Có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời gian giải theo thuật toán đó quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng. 48
  45. + Có những bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận được. Từ những nhận định trên, người ta thấy rằng cần phải có những đổi mới cho khái niệm thuật toán. Người ta đã mở rộng hai tiêu chuẩn của thuật toán: tính xác định và tính đúng đắn. Việc mở rộng tính xác định đối với thuật toán đã được thể hiện qua các giải thuật đệ quy và ngẫu nhiên. Tính đúng của thuật toán bây giờ không còn bắt buộc đối với một số cách giải bài toán, nhất là các cách giải gần đúng. Trong thực tiễn, có nhiều trường hợp người ta chấp nhận các cách giải thường cho kết quả tốt (nhưng không phải lúc nào cũng tốt) nhưng ít phức tạp và hiệu quả. Chẳng hạn nếu giải một bài toán bằng thuật toán tối ưu đòi hỏi máy tính thực hiện nhiều năm thì chúng ta có thể sẵn lòng chấp nhận một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong vài ngày hoặc vài giờ. Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường được gọi là các thuật giải. Khái niệm mở rộng này của thuật toán đã mở rộng cửa cho chúng ta trong việc tìm kiếm phương pháp để giải quyết các bài toán được đặt ra. 4. CÁC PHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN Khi chứng minh hoặc giải một bài toán trong toán học, ta thường dùng những ngôn từ toán học như: "ta có", "điều phải chứng minh", "giả thuyết", và sử dụng những phép suy luận toán học như phép suy ra, tương đương. Thuật toán là một phương pháp thể hiện lời giải bài toán nên cũng phải tuân theo một số quy tắc nhất định. Ðể có thể truyền đạt thuật toán cho người khác hay chuyển thuật toán thành chương trình máy tính, ta phải có phương pháp biểu diễn thuật toán. Có ba phương pháp biểu diễn thuật toán sau đây. 49
  46. 4.1. Ngôn ngữ tự nhiên Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kê các bước của thuật toán (Các ví dụ về thuật toán trong mục 1 của chương sử dụng ngôn ngữ tự nhiên). Phương pháp biểu diễn này không yêu cầu người viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật toán bằng ngôn ngữ tự nhiên. Tuy vậy, để dễ đọc, ta nên viết các bước con lùi vào bên phải và đánh số bước theo quy tắc phân cấp như 1, 1.1, 1.1.1, Bạn có thể tham khảo lại ba ví dụ trong mục 1 của chương để hiểu cách biểu diễn thuật toán theo ngôn ngữ tự nhiên. 4.2. Lưu đồ - sơ đồ khối Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý. Ðể biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai loại thao tác. Một thao tác là thao tác chọn lựa dựa theo một điều kiện nào đó. Chẳng hạn: thao tác "nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện B4" là thao tác chọn lựa. Các thao tác còn lại không thuộc loại chọn lựa được xếp vào loại hành động. Chẳng hạn, "Chọn một hộp bất kỳ và để lên đĩa cân còn trống." là một thao tác thuộc loại hành động. 4.2.1. Thao tác chọn lựa (decision) Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện. 50
  47. 4.2.2. Thao tác xử lý (process) Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý. 4.2.3. Ðường đi (route) Khi dùng ngôn ngữ tự nhiên, ta ngầm hiểu rằng quá trình thực hiện sẽ lần lượt đi từ bước trước đến bước sau (trừ khi có yêu cầu nhảy sang bước khác). Trong ngôn ngữ lưu đồ, do thể hiện các bước bằng hình vẽ và có thể đặt các hình vẽ này ở vị trí bất kỳ nên ta phải có phương pháp để thể hiện trình tự thực hiện các thao tác. Hai bước kế tiếp nhau được nối bằng một cung, trên cung có mũi tên để chỉ hướng thực hiện. Chẳng hạn trong hình dưới, trình tự thực hiện sẽ là B1, B2, B3. Từ thao tác chọn lựa có thể có đến hai hướng đi, một hướng ứng với điều kiện thỏa và một hướng ứng với điều kiện không thỏa. Do vậy, ta dùng hai cung xuất phát từ các đỉnh hình thoi, trên mỗi cung có ký hiệu Ð/Ðúng/Y/Yes để chỉ hướng đi ứng với điều kiện thỏa và ký hiệu S/Sai/N/No để chỉ hướng đi ứng với điều kiện không thỏa. 51
  48. 4.2.4. Ðiểm cuối (terminator) Ðiểm cuối là điểm khởi đầu và kết thúc của thuật toán, được biểu diễn bằng hình ovan, bên trong có ghi chữ bắt đầu/start/begin hoặc kết thúc/end. Ðiểm cuối chỉ có cung đi ra (điểm khởi đầu) hoặc cung đi vào (điểm kết thúc). Xem lưu đồ thuật toán giải phương trình bậc hai ở trên để thấy cách sử dụng của điểm cuối. 53
  49. 4.2.5. Ðiểm nối (connector) Ðiểm nối được dùng để nối các phần khác nhau của một lưu đồ lại với nhau. Bên trong điểm nối, ta đặt một ký hiệu để biết sự liên hệ giữa các điểm nối. 4.2.6. Ðiểm nối sang trang (off-page connector) Tương tự như điểm nối, nhưng điểm nối sang trang được dùng khi lưu đồ quá lớn, phải vẽ trên nhiều trang. Bên trong điểm nối sang trang ta cũng đặt một ký hiệu để biết được sự liên hệ giữa điểm nối của các trang. 54
  50. Ở trên chỉ là các ký hiệu cơ bản và thường được dùng nhất. Trong thực tế, lưu đồ còn có nhiều ký hiệu khác nhưng thường chỉ dùng trong những lưu đồ lớn và phức tạp. Ðối với các thuật toán trong cuốn sách này, ta chỉ cần sử dụng các ký hiệu trên là đủ. 4.3. Mã giả Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán nhưng lại cồng kềnh. Ðể mô tả một thuật toán nhỏ ta phải dùng một không gian rất lớn. Hơn nữa, lưu đồ chỉ phân biệt hai thao tác là rẽ nhánh (chọn lựa có điều kiện) và xử lý mà trong thực tế, các thuật toán còn có thêm các thao tác lặp (chúng ta sẽ tìm hiểu về thao tác lặp trong các bài sau). Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Tất nhiên, mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Dùng mã giả vừa tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán. Tất nhiên là trong mã giả ta vẫn dùng một phần ngôn ngữ tự nhiên. Một khi đã vay mượn cú pháp và khái niệm của ngôn ngữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó. Chính vì lý do này, chúng ta chưa vội tìm hiểu về mã giả trong bài này (vì chúng ta chưa biết gì về ngôn ngữ lập trình!). Sau khi tìm hiểu xong bài về thủ tục - hàm bạn sẽ hiểu mã giả là gì! Một đoạn mã giả của thuật toán giải phương trình bậc hai if Delta > 0 then Begin x1=(-b-sqrt(delta))/(2*a) x2=(-b+sqrt(delta))/(2*a) 55
  51. xuất kết quả: phương trình có hai nghiệm là x1 và x2 End else if delta = 0 then xuất kết quả: phương trình có nghiệm kép là -b/(2*a) else {trường hợp delta < 0} xuất kết quả: phương trình vô nghiệm 56