Hình 1
Kéo để xoay · giữ shift và kéo để dịch chuyển · nhấp để phân tích từng phần
Cuộn để lật trang
Computer Science Principles · AP Computer Science Principles
bit, nén và thông tin
Mọi thứ máy tính lưu giữ, một con số, một cái tên, một bức ảnh, một bài hát, xét đến cùng đều là một mẫu bit.
Một bit (viết tắt của binary digit, chữ số nhị phân) là 0 hoặc 1. Các thiết bị tính toán biểu diễn dữ liệu theo cách số: thành phần cấp thấp nhất của mọi giá trị là các bit.
Hình đếm theo hệ nhị phân. Mỗi ô là một bit, mặt giấy cho 0 và mặt đỏ cho 1, nằm dưới giá trị vị trí của nó, 128, 64, 32, 16, 8, 4, 2, 1. Mỗi bước cộng thêm 1: bit ngoài cùng bên phải lật, và ở đâu một bit 1 lật thành 0 thì phần nhớ lan sang trái một vị trí, như khi 00000111 (7) trở thành 00001000 (8).
Chương trình giữ các giá trị dữ liệu trong biến, trong danh sách các phần tử, hoặc ở dạng hằng số độc lập, rồi truyền chúng làm đầu vào cho các thủ tục và nhận lại làm đầu ra. Dù ở dạng nào, các giá trị đều được lưu bằng bit, và chương trình dịch chúng sang dạng con người đọc được.
Chương này là Ý tưởng lớn 2 của AP Computer Science Principles, Dữ liệu, chiếm 17–22% bài thi trắc nghiệm: số nhị phân (2.1), nén dữ liệu (2.2), rút thông tin từ dữ liệu (2.3) và dùng chương trình với dữ liệu (2.4).
các bit được nhóm thành những trừu tượng hoá
Một byte là 8 bit. Tự nó, một byte không có ý nghĩa gì: ý nghĩa của nó phụ thuộc vào việc chương trình đọc nó coi nó là gì.
Trừu tượng hoá là quá trình giảm độ phức tạp bằng cách tập trung vào ý chính. Bằng cách ẩn các chi tiết không liên quan đến câu hỏi đang xét và gom các chi tiết liên quan và hữu ích lại với nhau, trừu tượng hoá cho phép bạn nghĩ về ý tưởng thay vì về các bit.
Các bit được nhóm lại để biểu diễn các trừu tượng hoá, gồm (nhưng không giới hạn ở) số, ký tự và màu sắc. Hình đọc một byte, 01000001, theo ba cách:
| đọc như | nghĩa là |
|---|---|
| một số nhị phân | 65 |
| một ký tự (mã ASCII và Unicode 65) | chữ cái A |
| độ sáng của một điểm ảnh, từ 0 (đen) đến 255 (trắng) | một màu xám tối |
Vì vậy cùng một dãy bit có thể biểu diễn các kiểu dữ liệu khác nhau trong những ngữ cảnh khác nhau. Một ảnh màu thường lưu ba số như vậy cho mỗi điểm ảnh, mỗi số cho một màu đỏ, lục và lam: 3 byte, 24 bit.
các giá trị vị trí, đánh số từ 0 ở bên phải
Các cơ số, gồm nhị phân và thập phân, được dùng để biểu diễn dữ liệu. Thập phân (cơ số 10) chỉ dùng các chữ số 0–9; nhị phân (cơ số 2) chỉ dùng 0 và 1.
Như trong thập phân, vị trí của một chữ số quyết định giá trị của nó: giá trị bằng chữ số nhân với giá trị vị trí của vị trí đó. Giá trị vị trí là cơ số lũy thừa vị trí, và các vị trí được đánh số từ 0 ở ngoài cùng bên phải, tăng thêm 1 khi sang trái. Trong thập phân, 305 = 3 × 102 + 0 × 101 + 5 × 100.
Trong nhị phân, mỗi vị trí có giá trị gấp đôi vị trí bên phải nó. Với 10110101:
| vị trí | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| giá trị vị trí | 27 = 128 | 26 = 64 | 25 = 32 | 24 = 16 | 23 = 8 | 22 = 4 | 21 = 2 | 20 = 1 |
| bit | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
Cộng các giá trị vị trí nơi bit là 1: 128 + 32 + 16 + 4 + 1 = 181. Bit 0 không cộng thêm gì. Hình đọc từ trái sang phải; mỗi bit 1 thả giá trị vị trí của nó vào tổng.
lấy giá trị vị trí lớn nhất còn vừa
Để viết một số nguyên dương trong hệ nhị phân, đi từ giá trị vị trí lớn nhất xuống: nơi giá trị vị trí vừa với phần còn lại, viết 1 và trừ nó đi; nơi không vừa, viết 0.
Với 100 dùng tám bit:
| giá trị vị trí | còn lại | vừa không? | bit | còn sau đó |
|---|---|---|---|---|
| 128 | 100 | no | 0 | 100 |
| 64 | 100 | yes | 1 | 36 |
| 32 | 36 | yes | 1 | 4 |
| 16 | 4 | no | 0 | 4 |
| 8 | 4 | no | 0 | 4 |
| 4 | 4 | yes | 1 | 0 |
| 2 | 0 | no | 0 | 0 |
| 1 | 0 | no | 0 | 0 |
Vậy 100 = 01100100: 64 + 32 + 4 = 100. Các số 0 đứng đầu không thay đổi gì, nên 01100100 và 1100100 là cùng một số.
Cách thứ hai: chia cho 2 liên tiếp, rồi đọc các số dư từ cuối lên đầu. 100 ÷ 2 = 50 dư 0; 50 ÷ 2 = 25 dư 0; 25 ÷ 2 = 12 dư 1; 12 ÷ 2 = 6 dư 0; 6 ÷ 2 = 3 dư 0; 3 ÷ 2 = 1 dư 1; 1 ÷ 2 = 0 dư 1. Đọc từ dưới lên: 1100100.
Trong hình, thanh xanh là phần còn lại của 100; mỗi bit 1 bẻ giá trị vị trí của nó ra khỏi thanh và làm ô của nó chuyển sang đỏ.
và so sánh các số nhị phân
Một bit có 2 mẫu. Mỗi bit thêm vào nhân đôi số mẫu: mỗi mẫu cũ một lần với số 0 đứng trước, và một lần nữa với số 1. Vậy n bit có 2n mẫu.
Hình dựng chúng ra: 1 bit, 2; 2 bits, 4; 3 bits, 8; 4 bits, 16. Một byte có 28 = 256 mẫu, tức các số nguyên từ 0 đến 255. Số n bit lớn nhất gồm toàn bit 1: 2n − 1.
Cần bao nhiêu bit để mỗi chữ cái trong 26 chữ cái có một mẫu riêng? 24 = 16 là quá ít; 25 = 32 là đủ: 5 bit.
So sánh và sắp thứ tự. Cho hai số cùng số bit (đệm thêm các số 0 đứng đầu) và quét từ trái sang. Vị trí đầu tiên mà chúng khác nhau quyết định: số có bit 1 ở đó lớn hơn, vì giá trị vị trí đó lớn hơn tổng tất cả các vị trí bên phải nó cộng lại (2p > 2p − 1).
01101100 và 01011111 khác nhau lần đầu ở vị trí 5, hàng 32, nơi số thứ nhất có bit 1: 108 > 95, bất kể các bit sau đó.
tràn số và lỗi làm tròn
Trong nhiều ngôn ngữ lập trình, số nguyên được biểu diễn bằng một số bit cố định. Điều đó giới hạn phạm vi giá trị số nguyên và các phép toán trên chúng, và có thể gây ra tràn số hoặc các lỗi khác.
Bộ đếm trong hình (giả định) có 4 bit: nó chứa các số từ 0 đến 15. Cộng 1 vào 15 (1111) cần một bit thứ năm; phần nhớ không có chỗ để đi, và bộ đếm hiện 0. Đó là tràn số.
Các ngôn ngữ khác cung cấp một trừu tượng hoá trong đó kích thước số nguyên chỉ bị giới hạn bởi dung lượng bộ nhớ của máy tính. Ngôn ngữ trong tờ tham khảo của bài thi là một trong số đó: số nguyên của nó không bị tràn.
Số thực (có phần thập phân) cũng được lưu bằng một số bit cố định, điều này giới hạn phạm vi và các phép toán trên chúng và có thể gây ra lỗi làm tròn cùng các lỗi khác: một số số thực chỉ được lưu dưới dạng xấp xỉ. Với 3 bit phần thập phân (trong hình, giả định) chỉ có các bội của 1/8 = 0.125; 0.1 được lưu thành 0.125, lệch 0.025.
Các ngôn ngữ thực dùng nhiều bit hơn hẳn, nên sai số nhỏ hơn nhiều nhưng không biến mất: trong nhiều ngôn ngữ, 0.1 + 0.2 cho kết quả 0.30000000000000004. Các giới hạn phạm vi cụ thể của số thực nằm ngoài phạm vi khoá học và bài thi.
một xấp xỉ dạng số
Dữ liệu tương tự có các giá trị thay đổi trơn theo thời gian, chứ không theo từng khoảng rời rạc: cao độ và âm lượng của âm nhạc, màu sắc của một bức tranh, vị trí của một vận động viên chạy nước rút trong cuộc đua.
Máy tính lưu các bit, nên nó chỉ có thể xấp xỉ dữ liệu tương tự. Dùng dữ liệu số để xấp xỉ dữ liệu tương tự của thế giới thực là một ví dụ của trừu tượng hoá.
Dữ liệu tương tự có thể được xấp xỉ sát bằng dạng số nhờ lấy mẫu: đo các giá trị của tín hiệu tương tự ở những khoảng đều đặn, gọi là các mẫu. Mỗi mẫu được đo để tính ra chính xác các bit cần để lưu nó.
Hình lấy mẫu cùng một tín hiệu trơn hai lần. Lần đầu 8 mẫu, mỗi mẫu được làm tròn về một trong 4 mức (2 bit): 8 × 2 = 16 bit, một cầu thang thô. Rồi 16 mẫu ở 8 mức (3 bit): 16 × 3 = 48 bit, và cầu thang bám sát đường cong hơn (khoảng cách trung bình của nó tới tín hiệu giảm đi 43%).
Nhiều mẫu hơn và nhiều bit hơn cho mỗi mẫu cho xấp xỉ sát hơn, và tốn nhiều bit hơn để lưu hoặc gửi. Không số mẫu hữu hạn nào làm nó chính xác tuyệt đối.
nhỏ hơn, và khôi phục lại chính xác
Nén dữ liệu có thể giảm kích thước (số bit) của dữ liệu được truyền hoặc lưu trữ. Một thuật toán không mất dữ liệu thường có thể giảm kích thước mà vẫn bảo đảm khôi phục hoàn toàn dữ liệu gốc.
Hàng trong hình có 20 điểm ảnh, mỗi điểm một byte: 20 byte (giả định). Mã hoá độ dài chạy lưu mỗi dãy một màu dưới dạng một số đếm và một màu: 7W 4R 6W 3B, 4 dãy × 2 byte = 8 byte.
Giải mã viết ra 7 white, 4 red, 6 white, 3 blue: đúng hàng ban đầu, từng điểm ảnh một. Không mất gì cả, nên ít bit hơn không nhất thiết có nghĩa là ít thông tin hơn.
Mức giảm kích thước phụ thuộc vào cả lượng dư thừa trong dữ liệu gốc lẫn thuật toán nén được dùng. Các dãy dài nén tốt. Một hàng đổi màu ở mỗi điểm ảnh (WRWRWR…) có 20 dãy độ dài 1: sau khi mã hoá, nó chiếm 40 byte, nhiều hơn 20 byte ban đầu.
nhỏ hơn nữa, nhưng chỉ là một xấp xỉ
Một thuật toán mất dữ liệu có thể giảm đáng kể số bit được lưu hoặc gửi, nhưng chỉ cho phép khôi phục một xấp xỉ của dữ liệu gốc.
16 điểm ảnh trong hình (độ sáng giả định, mỗi điểm một byte) chỉ giữ lại trung bình của mỗi cặp: 8 byte, một nửa kích thước. Giải mã cho mỗi điểm ảnh giá trị trung bình của cặp của nó: 14 trong số 16 điểm trở lại khác đi, lệch tới 10. Các bóng xám là bản gốc, và không có gì trong 8 byte có thể đưa chúng trở lại: các cặp 200, 180 và 190, 190 đều có trung bình là 190.
Các thuật toán mất dữ liệu thường giảm được số bit nhiều hơn các thuật toán không mất dữ liệu. Chọn loại nào tuỳ tình huống:
| điều quan trọng nhất | thường được chọn |
|---|---|
| chất lượng, hoặc khả năng khôi phục chính xác bản gốc (một tệp chương trình, một tài liệu văn bản) | không mất dữ liệu |
| giảm thiểu kích thước dữ liệu hoặc thời gian truyền (phát video trực tuyến qua đường truyền chậm) | mất dữ liệu |
các mẫu, và những điều chúng không chứng minh
Thông tin là tập hợp các sự kiện và quy luật được rút ra từ dữ liệu. Dữ liệu tạo cơ hội để nhận ra xu hướng, tìm ra các mối liên hệ và giải quyết vấn đề.
Hình vẽ 24 ngày giả định ở một thị trấn biển: số kem bán ra so với số ca cháy nắng. Cái này tăng thì cái kia cũng tăng: một tương quan mạnh (hệ số tương quan r = 0.86; 1 sẽ là một đường thẳng hoàn hảo).
Kem không gây ra cháy nắng. Tô màu các ngày theo nhiệt độ thì lý do hiện ra: 7 ngày nóng (màu đỏ, từ 27 °C trở lên) mang lại cả nhiều kem hơn lẫn nhiều nắng hơn. Một tương quan tìm thấy trong dữ liệu không nhất thiết cho thấy có quan hệ nhân quả; cần nghiên cứu thêm để hiểu đúng bản chất của mối quan hệ.
Ở đây chỉ riêng hồ sơ bán hàng không thể cho thấy điều đó. Thường thì một nguồn đơn lẻ không chứa đủ dữ liệu cần thiết để rút ra kết luận, và dữ liệu từ nhiều nguồn (bán hàng, lượt khám ở trạm y tế, hồ sơ thời tiết) phải được kết hợp.
dữ liệu về dữ liệu
Siêu dữ liệu là dữ liệu về dữ liệu. Bức ảnh là dữ liệu; siêu dữ liệu của nó có thể gồm ngày tạo, kích thước tệp, kích thước ảnh và các thẻ của nó.
Các thay đổi và xoá bỏ trên siêu dữ liệu không làm thay đổi dữ liệu chính. Trong hình, thẻ “hoàng hôn” bị xoá; không một điểm ảnh nào trong 64 điểm ảnh thay đổi.
Siêu dữ liệu được dùng để tìm, tổ chức và quản lý thông tin: một thư viện ảnh có thể liệt kê mọi ảnh chụp vào 14 tháng 6, hay mọi ảnh gắn thẻ “bãi biển”, mà không cần nhìn một điểm ảnh nào. Siêu dữ liệu làm tăng hiệu quả sử dụng dữ liệu bằng cách cung cấp thêm thông tin, và cho phép dữ liệu được cấu trúc và tổ chức.
Trong bài thi, một tình huống cho biết dữ liệu và siêu dữ liệu đã thu thập rồi hỏi có thể tìm được điều gì. Hãy hỏi mỗi trường ghi lại điều gì. Một thư viện chỉ có ngày và thẻ có thể trả lời “có bao nhiêu ảnh chụp vào tháng Sáu?” nhưng không trả lời được “ảnh này chụp ở đâu?”: không trường nào ghi lại địa điểm.
đồng nhất, mà không đổi ý nghĩa
Các tập dữ liệu đặt ra thách thức bất kể kích thước: cần làm sạch dữ liệu, dữ liệu không đầy đủ, dữ liệu không hợp lệ, và cần kết hợp các nguồn dữ liệu. Khả năng xử lý dữ liệu phụ thuộc vào năng lực của người dùng và công cụ của họ.
Tuỳ cách thu thập, dữ liệu có thể không đồng nhất. Khi người dùng gõ vào một ô nhập tự do, cách họ viết tắt, đánh vần hay viết hoa khác nhau từ người này sang người khác. Biểu mẫu đăng ký trong hình (giả định) có 7 cách viết khác nhau của 2 thành phố.
Làm sạch làm dữ liệu đồng nhất mà không đổi ý nghĩa, bằng cách thay mọi cách viết tắt, đánh vần và viết hoa tương đương bằng cùng một từ: 5 mục được viết lại, và 7 cách viết trở thành 2. Giờ một chương trình đếm số lượt đăng ký theo thành phố sẽ đếm đúng.
Làm sạch không thể bịa ra điều còn thiếu. Một hàng không có tuổi (không đầy đủ) và một hàng ghi −4 (không hợp lệ); chúng được đánh dấu để kiểm tra hoặc loại khỏi phân tích, không được đoán.
nhiều dữ liệu hơn không có nghĩa là dữ liệu tốt hơn
Các vấn đề về thiên kiến thường do loại hoặc nguồn dữ liệu được thu thập tạo ra. Thiên kiến không bị loại bỏ chỉ bằng cách thu thập thêm dữ liệu.
Cuộc thăm dò trong hình (giả định) chỉ tiếp cận được phía bên trái của dân số, chẳng hạn độc giả của một trang web. Trong toàn dân số, 41% giữ ý kiến màu đỏ. Sau 30 câu trả lời, cuộc thăm dò cho là 80%; sau 60, là 78%. Gấp đôi số câu trả lời, vẫn là bức tranh sai ấy, vì mọi câu trả lời đều đến từ cùng một nguồn không đại diện.
Quy mô vẫn quan trọng: kích thước của một tập dữ liệu ảnh hưởng đến lượng thông tin có thể rút ra từ nó. Nhưng các tập dữ liệu lớn khó xử lý bằng một máy tính duy nhất và có thể đòi hỏi hệ thống song song, nhiều bộ xử lý cùng làm việc trên các phần của dữ liệu một lúc.
Khả năng mở rộng của hệ thống là một cân nhắc quan trọng khi làm việc với các tập dữ liệu, vì năng lực tính toán của một hệ thống ảnh hưởng đến cách xử lý và lưu trữ các tập dữ liệu.
chương trình xử lý danh sách
Có thể dùng chương trình để xử lý dữ liệu nhằm lấy thông tin. Công cụ tìm kiếm hữu ích để tìm thông tin một cách hiệu quả, và hệ thống lọc dữ liệu là công cụ quan trọng để tìm thông tin và nhận ra các quy luật trong dữ liệu.
Lọc chỉ giữ lại các phần tử thoả một điều kiện, chẳng hạn chỉ giữ các số dương từ một danh sách, hoặc chỉ các học sinh đã đăng ký vào ban nhạc:
data ← [4, -2, 7, 0, -5, 3] positives ← [] FOR EACH n IN data { IF(n > 0) { APPEND(positives, n) } } Hình chạy đoạn mã này với dòng đang chạy màu đỏ. Mỗi n được kiểm tra; chỉ những phần tử có n > 0 mới được thêm vào. positives kết thúc là [4, 7, 3]; 0 không được giữ, vì 0 > 0 là sai.
Biến đổi thay đổi mọi phần tử, chẳng hạn nhân đôi mọi phần tử trong một danh sách, hoặc thêm email của phụ huynh vào mọi hồ sơ học sinh. Với doubled ← [] trước:
FOR EACH n IN data { APPEND(doubled, 2 * n) } doubled kết thúc là [8, −4, 14, 0, −10, 6]. Hiểu biết mới có thể đến từ việc chuyển đổi và biến đổi dữ liệu, và các quy luật có thể hiện ra khi dữ liệu được biến đổi bằng chương trình. Lập trình viên cũng dùng chương trình để lọc và làm sạch dữ liệu.
một số từ nhiều số, và một biểu đồ
Kết hợp hoặc so sánh dữ liệu rút nhiều giá trị về một câu trả lời: cộng một danh sách các số, hoặc tìm học sinh có điểm trung bình cao nhất. Trực quan hoá thể hiện một tập dữ liệu dưới dạng biểu đồ, đồ thị hoặc biểu diễn trực quan khác.
Một câu lạc bộ ghi lại số lượt đăng ký trong 6 tuần (giả định): signups ← [12, 18, 9, 22, 15, 20].
total ← 0 most ← signups[1] FOR EACH n IN signups { total ← total + n IF(n > most) { most ← n } } DISPLAY(total) DISPLAY(most) Nó hiển thị 96 22: 6 tuần, tổng cộng 96 lượt đăng ký, 22 trong tuần tốt nhất. most bắt đầu từ signups[1], giá trị đầu tiên, không phải 0, nên nó vẫn chạy đúng dù mọi giá trị đều âm. Khi chạy, hình vẽ mỗi tuần thành một cột: biểu đồ hình thành khi dữ liệu được đọc.
Bảng, sơ đồ, văn bản và các công cụ trực quan khác có thể dùng để truyền đạt hiểu biết và tri thức rút ra từ dữ liệu. Các chương trình như bảng tính giúp tổ chức thông tin và tìm xu hướng một cách hiệu quả.
Chương trình được dùng theo cách lặp và tương tác: xem biểu đồ, đặt một câu hỏi mới, lọc hoặc biến đổi lại. Kết hợp các nguồn dữ liệu, phân cụm dữ liệu (nhóm các phần tử giống nhau) và phân loại dữ liệu (xếp các phần tử vào các loại) là các phần của việc dùng chương trình để có hiểu biết và tri thức từ dữ liệu.