CHƯƠNG 1 CÁC KIẾN THỨC CƠ BẢN 1. Thông tin và biểu diễn thông tin trong máy tính 1. Khái niệm về thông tin Bất kỳ một thông báo hay một tín hiệu gì có giá trị đối với con người đều được coi là thông tin (information). Việc trao đổi hay tiếp nhận thông tin mang tính chủ quan, tuỳ thuộc vào người tiếp nhận thông tin.
Các thông tin chúng ta đưa vào máy tính xử lý còn có thể gọi là dữ liệu (data). Máy tính có thể lưu trữ và xử lý nhiều loại thông tin như văn bản, hình ảnh, âm thanh, phim. Biểu diễn thông tin trong máy tính Do máy tính được chế tạo bằng các linh kiện, vật liệu điện tử chỉ có hai trạng thái, chẳng hạn: đóng/mở của mạch điện (On-Off), bật/tắt của công tắc, thông/hở của đèn điện tử hay đèn bán dẫn.Vì vậy người ta dùng hai ký tự 0 và 1 tương ứng với hai trạng thái đóng/mở để lưu trữ và xử lý thông tin. Các đơn vị đo thông tin Mỗi giá trị 0 hoặc 1 gọi là bit (Binary digit), 8 bit lập thành 1 byte.
Ngoài ra người ta còn hay dùng các đơn vị sau để chỉ bội số của byte: 1KB = 210 byte = 1024 byte (Kilô byte) 10 1MB = 2 KB = 1024 KB (Mêga byte) 1GB = 210 MB = 1024 MB (Giga byte) 10 1TB = 2 GB = 1024 GB (Tera byte) 1. Các hệ đếm thông dụng Hệ đếm được hiểu như là 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ủa các số. Hệ thập phân Hệ này còn gọi là hệ đếm cơ số 10: dùng 10 ký hiệu là 10 chữ số do người A-rập phát minh ra: 0,1,2,3,4,5,6,7,8,9 để biểu diễn các số. Đây là hệ đếm thường dùng trong cuộc sống hàng ngày.
Hệ nhị phân Hệ này còn được gọi là hệ đếm cơ số 2: dùng 2 ký hiệu 0 và 1 để biểu diễn các số. Hệ thập lục Hệ này còn được gọi là hệ đếm cơ số 16 hay hệ Hecxa, dùng 16 ký hiệu: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F tương ứng với các giá trị thập phân từ 0 đến 15 để biểu diễn các số. Định nghĩa một hệ đếm tổng quát Định nghĩa: Một số N trong hệ cơ số B, B nguyên lớn hơn 1, được biểu diễn là: dn-1dn-2.d-m và giá trị của N được xác định theo công thức: N = dn-1Bn-1 + dn-2Bn-2 +.+ d-mB-m trong đó di thỏa mãn: 0≤di<B và n là số lượng các chữ số bên trái, còn m là số lượng các chữ số bên phải dấu phân chia giữa phần nguyên và phần lẻ.4: Sau đây là giá trị các số được biểu diễn ở các hệ đếm cơ số 2, 8, 10 và 16. Các quy tắc chuyển đổi giữa các hệ đếm Cách đổi một số từ hệ đếm bất kỳ sang hệ thập phân được thực hiện trực tiếp theo định nghĩa đã trình bày ở phần 1.
Sau đây là các quy tắc chuyển đổi qua lại giữa các hệ đếm cơ số 10, 2, 8 và 16. 8 Quy tắc 1: Muốn đổi một số từ hệ đếm này sang hệ đếm khác, ta đổi phần nguyên sang phần nguyên và phần lẻ sang phần lẻ. Quy tắc 2: Muốn đổi một số thập phân nguyên sang số nhị phân ta chia liên tiếp số nguyên đó cho 2, thương số của phép chia trước là số bị chia của phép chia sau, cho đến khi nào được thương số bằng 0. Số nhị phân nhận được là các số dư của các phép chia được viết liên tiếp theo thứ tự ngược lại.5: Đổi số 46 (hệ 10) sang hệ cơ số 2: Quy tắc 3: Muốn đổi một số thập phân lẻ nhỏ hơn 1 sang số nhị phân, ta thực hiện phép nhân liên tiếp với 2, phần lẻ của tích số trước là số bị nhân của phép nhân sau, cho đến khi nào phần lẻ của tích số bằng 0.
Số nhị phân nhận được là phần nguyên của các tích số viết theo thứ tự của chiều thuận. Chú ý: Trong quy tắc này quá trình nhân có thể không bao giờ dừng (phần lẻ của tích số không bao giờ bằng 0), khi đó ta phải tiến hành việc làm tròn kết quả.25 (hệ 10) sang số hệ 2: 1. Các phép toán cơ bản trên hệ nhị phân Phép cộng: Việc cộng hai số được tiến hành bằng cách cộng từng cặp chữ số của chúng (bắt đầu từ cặp chữ số tận cùng bên phải) theo quy tắc: 9 0+0=0; 0+1=1; 1+0=1; 1+1=0 nhớ 1.7: Phép trừ: Việc trừ hai số được tiến hành bằng cách trừ từng cặp chữ số của chúng (bắt đầu từ cặp chữ số tận cùng bên phải) theo quy tắc: 0-0=0; 0-1=1 nợ 1; 1-0=1; 1-1=0.8: Phép nhân: Việc nhân hai số được tiến hành bằng cách nhân từng chữ số của số nhân với các chữ số của số bị nhân theo quy tắc: 0×0=0; 0×1=0; 1×0=0; 1×1=1.9: Phép chia: thực hiện tương tự như trên hệ thập phân. Chương trình máy tính Chương trình là một tập hợp các câu lệnh viết bằng một ngôn ngữ lập trình cụ thể được sắp xếp theo một trình tự nhất định nhằm đáp ứng các yêu cầu của bài toán cụ thể.
Khái niệm về thuật toán Khái niệm thuật toán dùng để chỉ phương pháp (method) hay cách thức để giải quyết vấn đề. Thuật toán có thể minh họa bằng ngôn ngữ tự nhiên (natural language), bằng sơ đồ (flow chart) hoặc bằng mã giả (pseudo code). Trong thực tế thuật toán thường được minh họa bằng mã giả hoặc bằng ngôn ngữ lập trình nào đó. Thuật toán (algorithrm) là một dãy các câu lệnh (statement) chặt chẽ và rõ ràng xác định một trình tự các thao tác trên một số đối tượng nào đó sao cho sau một số hữu hạn bước thực hiện ta đạt được kết quả mong muốn.11: Thuật toán giải phương trình bậc nhất ax + b = 0 - Bước 1: Nhập các biến a và b - Bước 2: Nếu a = 0 thì chuyển sang bước 3, ngược lại chuyển sang bước 4.
- Bước 3: Nếu b = 0 thì thông báo phương trình đã cho có vô số nghiệm, ngược lại thì thông báo phương trình vô nghiệm. Chuyển sang bước 5. - Bước 4: Thông báo nghiệm của phương trình là -b/a. - Bước 5: Dừng thuật toán.
Các đặc trưng của thuật toán 1.1 Tính xác định Tính xác định đòi hỏi, ở mỗi bước của thuật toán, các thao tác đều phải rõ ràng, không gây ra sự nhập nhằng, lẫn lộn. Nói khác đi, trong cùng một điều kiện, hai bộ xử lý (người hoặc máy) thực hiện cùng một bước của thuật toán thì phải cho cùng một kết quả. Hơn nữa, các bộ xử lý thuật toán không cần phải hiểu được ý nghĩa của các bước thao tác này. Tính xác định của thuật toán rất quan trọng, nhờ nó mà ta có thể giao cho các thiết bị tự động thực hiện các chức năng của thuật toán, làm một số công việc thay thế cho con người.2 Tính kết thúc (tính dừng) Thuật toán bao giờ cũng phải dừng sau một số hữu hạn bước thực hiện.
Trong thực hành khi xây dựng các thuật toán có chứa các hành động lặp đi lặp lại thì phải nêu điều kiện chấm dứt các vòng lặp để tránh tình trạng lặp lại vô hạn lần các thao tác lặp đó.3 Tính đúng đắn Yêu cầu bắt buộc của thuật toán là tính đúng đắn: với dữ liệu đầu vào cho trước, sau một số hữu hạn các bước thực hiện sẽ dừng và cho kết quả đầu ra đúng.4 Tính phổ dụng Thuật toán thường được xây dựng không chỉ để giải một bài toán riêng lẻ mà phải giải được một lớp các bài toán có cùng cấu trúc với dữ liệu đầu vào khác nhau và luôn luôn dẫn đến kết quả mong muốn.5 Tính hiệu quả Tính hiệu quả được đánh giá dựa trên một số tiêu chuẩn nhất định như khối lượng tính toán, thời gian và không gian được sử dụng bởi thuật toán. Một khía cạnh khác của tính hiệu quả là tính hiện thực. Một bài toán dù đã có thuật toán nhưng nếu ta không thể có đủ thời gian để đi đến kết quả cuối cùng thì thuật toán đó cũng thiếu tính hiện thực. Vì vậy cần lựa chọn những thuật toán nào mà thời gian thực hiện của nó là chấp nhận được.
Các đại lượng vào (input) và ra (output) Một thuật toán có thể có nhiều đại lượng vào mà ta thường gọi là dữ liệu vào. Sau khi dừng thuật toán thì tùy theo chức năng của thuật toán mà ta có thể thu được một số đại lượng ra xác định. Các đại lượng ra cũng thường được gọi là dữ liệu ra hay kết quả. Các phương pháp biểu diễn thuật toán Một thuật toán được diễn đạt rõ ràng sẽ bảo đảm cho bộ xử lý thực hiện chính xác các thao tác được yêu cầu và đạt được kết quả 12 mong muốn.
Có công cụ biểu diễn thuật toán cần quan tâm: Ngôn ngữ mô tả thuật toán và bộ xử lý thực hiện thuật toán đã được diễn tả bằng ngôn ngữ nói trên. Do bộ xử lý được dùng để thực hiện thuật toán đã được diễn tả theo ngôn ngữ nên nó phải hiểu được ngôn ngữ diễn tả thuật toán. Theo cách tiếp cận này, mỗi thuật toán sẽ được mô tả dưới ngôn ngữ thuật toán, dưới dạng một dãy các lệnh. Bộ xử lý sẽ thực hiện các lệnh theo một trật tự xác định cho đến khi gặp một lệnh dừng.
Có nhiều ngôn ngữ biểu diễn thuật toán khác nhau, cụ thể: - Ngôn ngữ tự nhiên (ngôn ngữ liệt kê các bước) - Ngôn ngữ lưu đồ (sơ đồ khối) - Ngôn ngữ phỏng trình (mã giả) - Ngôn ngữ lập trình. Phần tiếp theo sẽ giới thiệu công cụ biểu diễn thuật toán là ngôn ngữ lưu đồ. Biểu diễn thuật toán bằng ngôn ngữ lập trình sẽ được giới thiệu sau khi học về ngôn ngữ lập trình C/C++. Ngôn ngữ lưu đồ Ngôn ngữ lưu đồ hay sơ đồ là công cụ trực quan để diễn đạt các thuật toán.
Nếu biết sử dụng khéo léo ngôn ngữ này, ta có thể tránh được những đoạn giải thích bằng lời có thể dẫn đến sự nhập nhằng về ngữ nghĩa, đồng thời biểu diễn bằng lưu đồ sẽ giúp ta có được cái nhìn tổng quan hơn về toàn cảnh của quá trình xử lý của một thuật toán cho trước. Lưu đồ là một hệ thống những nút có hình dạng khác nhau, thể hiện các chức năng khác nhau của chúng và được nối với nhau bởi các cung. Cụ thể, chúng được tạo bởi 4 thành phần chủ yếu sau đây: 1. Nút giới hạn Được biểu diễn bởi hình ôvan, trong đó có ghi chữ: BẮT ĐẦU hoặc KẾT THÚC.
Chúng còn được gọi là các nút đầu và nút cuối của lưu đồ. Nút thao tác Là một hình chữ nhật trong đó có ghi các lệnh cần thực hiện.