[B.1.1.2] So sánh được mạng LAN và Internet

LAN (Mạng cục bộ)

• Mạng kết nối các thiết bị trong phạm vi nhỏ như tòa nhà, cơ quan, trường học.

WLAN (Mạng cục bộ không dây)

• Không nhầm lẫn với WAN.
• Ở hầu hết các mạng WLAN, việc truyền không dây tuân theo chuẩn Wi-Fi, các mạng WLAN này được gọi là mạng Wi-Fi.

WAN (Mạng diện rộng)

• Mạng kết nối nhiều mạng LAN khác nhau, có quy mô thành phố, quốc gia hay nhiều quốc gia.

Internet

• Một loại mạng WAN, có quy mô toàn cầu.
• Không có chủ sở hữu.

[B.1.1.4] Nêu được khái niệm Internet vạn vật (IoT)

• IoT là việc liên kết các thiết bị thông minh để tự động thu thập, trao đổi và xử lí dữ liệu.
• Một hệ thống IoT có thể không sử dụng Internet, ví dụ như hệ thống thu phí không dừng sử dụng sóng radio để giao tiếp giữa các thiết bị.

[B.1.1.1] Nêu được chức năng chính của một số thiết bị mạng thông dụng

Modem

• Biến đổi tín hiệu tương tự (có dạng sóng, truyền được xa) thành tín hiệu số (được sử dụng bởi các thiết bị khác trong mạng LAN) và ngược lại.

Router

• Định tuyến, tìm đường đi tốt nhất để truyền gói tin qua các mạng LAN khác nhau
• Kết nối các mạng LAN với nhau và mạng LAN với Internet.

Switch, Hub

• Đều giúp kết nối các thiết bị trong cùng một mạng LAN với nhau.
• Switch xác định được cổng gửi và cổng nhận và tạo kênh truyền dữ liệu tạm thời giữa hai cổng.
• Hub gửi dữ liệu nhận được tới tất cả các cổng, dẫn tới xung đột dữ liệu, làm giảm hiệu quả của mạng. Đổi lại, Hub thường có giá thành rẻ hơn Switch.
• Nếu đề không nêu gì về chi phí, giá thành, có thể coi hai thiết bị như nhau.

Access Point

• Switch + truyền không dây và tạo WLAN.

Cáp mạng (khả năng ra thi thấp)

• Truyền tải dữ liệu giữa hai thiết bị.
• Có hai loại chính:
  • Cáp xoắn có lõi kim loại, truyền dữ liệu bằng dòng điện và thường được dùng trong mạng LAN.
  • Cáp quang có lõi trong suốt, truyền dữ liệu đi xa bằng ánh sáng, thường được dùng trong mạng WAN.

[B.1.1.1] Kết nối được các thiết bị mạng thông dụng với PC.

• Thứ tự kết nối cơ bản: Máy tính ~\rightarrow~ Access Point ~\rightarrow~ Hub ~\rightarrow~ Switch ~\rightarrow~ Router ~\rightarrow~ Modem (có biến thể thêm, bớt thiết bị).
• Các thao tác trên máy tính và điện thoại sẽ không được trình bày chi tiết mà chỉ nêu điểm cần lưu ý nhất, các em tự thực hành nhiều lần để nhớ.

Kết nối PC với Switch

• Sử dụng cáp xoắn (cáp UTP) có giắc cắm RJ-45 ở hai đầu, một đầu cắm vào cổng RJ-45 của PC, một đầu cắm vào cổng RJ-45 của Switch.
• Quan sát đèn báo hiệu trên cổng. Nếu đèn màu xanh lá nhấp nháy thì nghĩa là đã kết nối thành công.
• Xác nhận kết nối bằng cách truy cập trang web trên PC

Kết nối PC/Laptop với Access Point / mạng Wi-Fi

• PC cần có bộ giao tiếp mạng (Network Interface Card - NIC) không dây.

Kết nối Switch với Router

• Sử dụng cổng LAN của Router

Kết nối Modem với Router

• Sử dụng cổng WAN của Router

[B.1.3.1] Kết nối được thiết bị di động vào mạng máy tính trong điều kiện phần cứng và phần mềm đã được chuẩn bị đầy đủ.

Kết nối điện thoại với Access Point / mạng Wi-Fi

• Cần nằm trong vùng phủ sóng của Access Point, cần nhập mật khẩu nếu mạng Wi-Fi có mật khẩu.

Kết nối điện thoại vào mạng 3G

• Sử dụng "Dữ liệu di động"

[B.1.1.2] Mô tả sơ lược được vai trò và chức năng của giao thức mạng nói chung và giao thức TCP/IP nói riêng

Giao thức mạng

• Giao thức mạng là các quy tắc điều khiển việc kết nối và truyền thông gửi các thiết bị mạng.
• Hai thiết bị phải dùng cùng một giao thức thì mới có thể kết nối với nhau qua mạng.

Bộ giao thức TCP/IP gồm hai giao thức: giao thức TCP và giao thức IP

Giao thức TCP

• Đảm bảo việc truyền dữ liệu ổn định, đúng thứ tự.
• Gồm 3 bước:
  • Thiết lập kết nối
  • Trao đổi dữ liệu:
    • Truyền dữ liệu: chia dữ liệu thành gói tin, mỗi gói tin được gắn số thứ tự và số xác nhận rồi gửi đi qua mạng; máy nhận xác thực lại việc đã nhận gói tin.
    • Kiểm tra lỗi: Kiểm tra lại số thứ tự và số xác nhận. Trường hợp bị mất gói tin hoặc lỗi, gửi lại gói tin.
  • Kết thúc kết nối.
• Ngoài ra, TCP còn có cơ chế để điều chỉnh tốc độ truyền dữ liệu để giảm thiểu việc bị mất gói tin.

Giao thức IP (giao thức Internet)

• Định tuyến (xác định đường đi), định danh gói tin để đảm bảo gói tin đến đúng địa chỉ máy nhận.
• Gói tin được gán thêm địa chỉ IP máy gửi và máy nhận (giống địa chỉ nhận, địa chỉ gửi trên phong bì thư)

Địa chỉ IP

• Các thiết bị trong cùng một mạng cục bộ có chung các số đầu thuộc phần địa chỉ mạng (Network ID) của địa chỉ IPv4, các số cuối là phần địa chỉ máy (Host ID) thì khác nhau.
• Địa chỉ IPv4 gồm 32 bit, thường thấy ở dạng 127.29.45.123. Do 1 byte = 8 bit nên địa chỉ IPv4 gồm 4 byte, mỗi byte thường được biểu diễn ở hệ thập phân và là một số từ 0 đến 255.
• Địa chỉ IPv6 gồm 128 bit, thường thấy ở dạng 2001:0db8:85a3:0000:0000:8a2e:0370:7334 (gồm 8 phần, mỗi phần 16 bit tương ứng với 2 byte và thường được biểu diễn ở hệ 16).
• Kỹ năng đổi địa chỉ IP giữa các hệ 2, 10, 16:
  • Mẹo CASIO. Xem video YouTube
  • Mẹo loại nhanh đáp án, kiểm tra lại việc bấm máy: Một số ở hệ 2 kết thúc bằng số 0 khi và chỉ khi số đó ở hệ 10 là số chẵn.

Hệ thống tên miền - Domain Name System (DNS)

• Chuyển địa chỉ IP (khó nhớ) thành tên miền (dễ nhớ) và ngược lại.

[B.1.2.1] Sử dụng được các chức năng mạng của hệ điều hành để chia sẻ tài nguyên.

Chia sẻ tệp hoặc thư mục

• Có ba quyền:
  • Full Control: toàn quyền (đọc, sửa, xóa, thiết lập lại quyền của mọi người dùng).
  • Change (Windows 10) hoặc Read/Write (Windows 11): đọc, ghi. Nếu là thư mục thì có thể xóa các tệp và thư mục con bên trong.
  • Read: đọc, chép dữ liệu ra ngoài.

Chia sẻ máy in

• Cần chia sẻ máy in thì các máy khác trong cùng mạng LAN mới dùng được.
  • Hệ quả: Nếu một máy không thể kết nối với máy in thông qua các thiết bị đang bật, máy đó sẽ không thể dùng được máy in. Ví dụ, nếu máy in nối với máy giáo viên và máy giáo viên tắt, các máy học sinh trong cùng một mạng LAN sẽ không thể sử dụng máy in.

Ở các phần thực hành, nên có bước kiểm tra lại sau khi hoàn thành như vào một trang web bất kì sau khi kết nối mạng, in thử một trang sau khi kết nối với máy in, ...

[A.1.0.1] Giải thích được sơ lược về khái niệm Trí tuệ nhân tạo (AI – Artificial Intelligence)

• Trí tuệ nhân tạo là khả năng của máy tính có thể làm những công việc mang tính trí tuệ con người
• Các công việc mang tính trí tuệ con người: có tri thức, suy luận, học, nhận thức, hiểu ngôn ngữ, giải quyết vấn đề, ...

[A.1.0.4] Nêu được ví dụ để thấy một hệ thống AI có tri thức, có khả năng suy luận, khả năng học, ...

Để nêu được ví dụ, ta cần:

• Hiểu được ý nghĩa của "có tri thức", "có khả năng suy luận", ... từ đó tìm được hệ thống AI thích hợp.
• Mô tả được các tính chất của hệ thống AI như tính năng, nơi sử dụng nhiều nhất, ...

Mục này sẽ được tổ chức theo công việc mang tính trí tuệ con người, hệ thống AI tương ứng và các tính chất đặc biệt của hệ thống AI (nếu có)

Có tri thức

• Tri thức của AI là (các tham số của) mô hình, các luật (quy tắc suy luận)
• Ví dụ: Máy dự báo thời tiết có tri thức là mô hình thời tiết.

Học

• Khái niệm: Đúc rút tri thức từ dữ liệu.
• Ví dụ: Hệ thống nhận dạng khuôn mặt có thể "học" khuôn mặt của mọi người để đúc rút ra các dấu hiệu nhận biết mỗi người.

Suy luận

• Khái niệm: Vận dụng quy tắc suy luận và tri thức có từ trước để đưa ra kết luận hoặc quyết định.
• Ví dụ:
  • Hệ chuyên gia MYCIN sử dụng trong y tế (quy tắc suy luận dạng "nếu triệu chứng ~A_1, A_2~, ... thì bệnh ~B~")
  • Hệ chuyên gia tài chính cung cấp tín dụng tự động cho khách hàng.

Nhận thức

• Khái niệm: cảm nhận và xử lí môi trường xung quanh (nhờ cảm biến)
• Ví dụ: Hệ thống điều khiển của xe tự lái sử dụng cảm biến để nhận biết chướng ngại vật.

Hiểu ngôn ngữ

• Đọc, hiểu, diễn giải được văn bản và tiếng nói.
• Ví dụ:
  • Google Translate
  • Trợ lí ảo
  • ChatGPT
• Không phải ví dụ:
  • Nhận dạng kí tự, tiếng nói (hệ thống không cần hiểu)

Giải quyết vấn đề

• Phối hợp các khả năng để giải quyết tình huống phức tạp hoặc tối ưu theo mục tiêu đặt ra
• Ví dụ:
  • Máy hút bụi tự động: các khả năng là đường đi, tình huống phức tạp là "vẽ" lại bản đồ phòng để hút bụi.
  • Google Maps tìm đường đi ngắn nhất (bài toán tối ưu)
  • Phần mềm chơi cờ vua (các khả năng là các nước đi)

Không phải ví dụ

• Các hệ thống không phải thiết bị số (do không phải là máy tính)
• Các hệ thống không làm công việc mang tính trí tuệ con người:
  • Cánh tay robot sản xuất: mới chỉ thể hiện khả năng vận động, không phải một công việc trí tuệ.
  • Một số thiết bị tự động nhờ các hiện tượng vật lí thông thường, không phải nhờ AI
    • Ấm siêu tốc.
    • Đèn đường tự động bật tắt khi trời tối, có người đến gần, ...
    • Cửa ra vào cửa hàng, siêu thị tự động mở.

[A.1.0.2] Nêu được ví dụ minh hoạ cho một số ứng dụng điển hình của AI

Mẹo: Để nhận biết ứng dụng của AI, hãy suy nghĩ xem hệ thống được cho có làm công việc mang tính trí tuệ con người hay không. Ở mỗi ví dụ minh họa, bên trái là tên ví dụ, bên phải là công việc mang tính trí tuệ con người của ví dụ đó.

Điều khiển tự động - Nhận thức

• Thường được sử dụng trong nhà máy
• Giám sát nguyên vật liệu, tối ưu hóa quy trình sản xuất
• Robot hình người - ngoài khả năng nhận thức còn có khả năng nhận dạng tiếng nói, hình ảnh

Chẩn đoán bệnh - Suy luận

• MYCIN (xem ở trên)

Nhận dạng chữ viết tay và tiếng nói - Học

• Nhận dạng các kí tự viết tay và tiếng nói và chuyển thành dạng xâu kí tự.

Nhận dạng khuôn mặt - Học

• Nhận dạng khuôn mặt được dùng cho mục đích an ninh như mở khóa điện thoại hay kiểm soát ra vào tòa nhà.

Trợ lí ảo - Hiểu ngôn ngữ

• Trả lời câu hỏi của khách hàng.
• Được tích hợp vào điện thoại, có thể dùng thay thế một phần công việc của tư vấn viên.

Các hệ thống khác (khả năng thấp)

[A.1.0.3] Chỉ ra được một số lĩnh vực của khoa học công nghệ và đời sống đã và đang phát triển mạnh mẽ dựa trên những thành tựu to lớn của AI

Lĩnh vực phát triển bởi AI

• Giáo dục:
  • Cá nhân hóa kế hoạch học tập
  • Giám sát kì thi
• Y tế:
  • Chẩn đoán bệnh
• Sản xuất:
  • Tối ưu hóa quy trình sản xuất
  • Kiểm tra chất lượng sản phẩm
  • Quản lí chuỗi cung ứng
• Nông nghiệp (một phần của sản xuất):
  • Tối ưu hóa quy trình chăm sóc vật nuôi, cây trồng dựa vào dữ liệu từ cảm biến.
• Giao thông vận tải
  • Xe tự lái
  • Quản lí giao thông thông minh
  • Điều tiết giao thông
• Tài chính, ngân hàng
  • Cập nhật chứng từ, hóa đơn vào cơ sở dữ liệu
  • Hỗ trợ quyết định đầu tư
  • Ngăn chặn gian lận tài chính

Lĩnh vực chưa phát triển bởi AI

• Nghệ thuật (như hội họa, văn học, ...)
  • AI chưa thể khơi những cái chưa ai khơi và sáng tạo những gì chưa có (ví dụ như tạo ra được một hệ tư tưởng mới).
• Các ngành nghề cần sự vận động trực tiếp của con người.

[A.2.0.1] Nêu được một cảnh báo về sự phát triển của AI trong tương lai.

• Nguy cơ về đạo đức:
  • Dữ liệu huấn luyện thiên lệch sẽ dẫn đến một hệ thống AI thiên lệch.
  • Ví dụ: Phần mềm nhận dạng giọng nói tiếng Việt có thể nhận dạng rõ giọng miền Bắc, miền Nam hơn miền Trung nếu thiếu dữ liệu giọng miền Trung.
• An ninh mạng:
  • AI tự dò tìm một cách trái pháp luật các lỗ hổng bảo mật (cũng có thể là một điều tốt nếu được dùng một cách hợp pháp)
  • Deepfake giả giọng, hình ảnh người khác phục vụ mục đích lừa đảo.
• Quyền riêng tư:
  • Dữ liệu được thu thập như số CCCD, số điện thoại, lịch sử mua hàng có thể bị dùng vào các mục đích không đúng đắn.
• Thiếu minh bạch:
  • Một số mô hình AI quá phức tạp, không thể phân tích để hiểu những mô hình này ra quyết định như thế nào và được dùng như một hộp đen (blackbox). Điều này có thể gây phiền lòng cho những người bị AI quyết định bất lợi.
• Việc làm (vừa là nguy cơ vừa là cơ hội):
  • Một số công việc như chăm sóc khách hàng sẽ bị thay thế, làm tăng lượng người thất nghiệp trong ngắn hạn nhưng sẽ mở ra những công việc mới trong tương lai.

I. KHÔNG GIAN TUYẾN TÍNH

1. Không gian tuyến tính (không gian vector)

Bộ tập hợp ~V~ và hai phép toán ~+~ (cộng), ~\cdot~ (nhân) được gọi là một không gian tuyến tính thực khi thỏa mãn ~10~ tiên đề sau:

Các tiên đề về tính đóng

Đóng với phép cộng: ~\forall x, y \in V: x + y \in V~

Đóng với phép nhân số thực: ~\forall a \in \mathbb{R}, x \in V: ax \in V~

Các tiên đề về phép cộng

Tính chất giao hoán: ~\forall x, y \in V: x + y = y + x~

Tính chất kết hợp: ~\forall x, y, z \in V: (x + y) + z = x + (y + z)~

Tồn tại phần tử ~0~: ~\exists 0 \in V: \forall x \in V: x + 0 = x~

Tồn tại số đối: ~\forall x \in V: x + (-1)x = 0~

Các tiên đề về phép nhân số thực

Tính chất kết hợp: ~\forall a, b \in \mathbb{R}, x \in V: (ab)x = a(bx)~

Tính chất phân phối đối với phép cộng trong ~V~: ~\forall a \in \mathbb{R}, x, y \in V: a(x + y) = ax + ay~

Tính chất phân phối đối với phép cộng số thực: ~\forall a, b \in \mathbb{R}, x \in V: (a+b)x = ax + bx~

Tồn tại đơn vị: ~\forall x \in V: 1x = x~

Khi thay tập ~\mathbb{R}~ bằng tập ~\mathbb{C}~ trong định nghĩa trên, ta được định nghĩa của không gian tuyến tính phức.

2. Không gian tuyến tính con

Nếu ~V~ là một không gian tuyến tính, ~S \ne \emptyset, S \subset V~, và ~S~ thỏa mãn các tiên đề về tính đóng, ~S~ là một không gian tuyến tính con của ~V~

Nếu ~S~ là một tập con của không gian tuyến tính ~V~, ~\text{span } S = \begin{cases} \emptyset \text{ nếu } S = \emptyset \\ \{\sum_{i=1}^n c_i x_i | n \in \mathbb{N}, \forall i \in \mathbb{N}, 1 \leq i \leq n: c_i \in \mathbb{R}, x_i \in S\} \text{ nếu } S \ne \emptyset \end{cases}~ được gọi là bao tuyến tính của ~S~ và là một không gian tuyến tính con của ~V~.

3. Độc lập tuyến tính

Một tập con ~S~ của không gian tuyến tính ~V~ là một tập độc lập tuyến tính khi ~\forall k \in \mathbb{N}, x_1, x_2, ..., x_k \in S, c_1, c_2, ..., c_k \in \mathbb{R}: \sum_{i=1}^k c_i x_i = 0 \Leftrightarrow \forall i \in \mathbb{N}, 1 \leq i \leq k: c_i = 0~

Một tập con ~S~ của không gian tuyến tính ~V~ là một tập phụ thuộc tuyến tính khi ~S~ không phải một tập độc lập tuyến tính.

Nếu ~S~ là một tập độc lập tuyến tính của không gian tuyến tính ~V~, ~\forall A \subset \text{span } S, |A| \geq |S|+1: A~ là một tập phụ thuộc tuyến tính.

4. Cơ sở

Một tập độc lập tuyến tính ~S~ của không gian tuyến tính ~V~ là một cơ sở của ~V~ khi ~\text{span } S = V~. Khi đó, ~\dim V = |S|~.

Nếu ~\dim V \in \mathbb{N}~, ~\forall S, T \text{ là cơ sở của } V: |S| = |T|~

Với ~V~ là không gian tuyến tính có ~\dim V = n \in \mathbb{N}~, ta có:

~\forall S \subset V, S \text{ độc lập tuyến tính}: \exists B \text{ cơ sở của } V: S \subset B~

~\forall S \subset V, S \text{ độc lập tuyến tính}, |S| = n: S \text{ là cơ sở của } V~

5. Tọa độ

Cho ~V~ là không gian tuyến tính có ~\dim V = n \in \mathbb{N}~ và ~B = (e_1, e_2, ..., e_n)~ là một cơ sở của ~V~. Khi đó, ~\forall x \in V:~ tồn tại duy nhất bộ số thực ~(c_1, c_2, ..., c_n): \sum_{i=1}^n c_i e_i = x~

Bộ số thực ~(c_1, c_2, ..., c_n)~ được gọi là tọa độ của ~x~ trong cơ sở ~B~.

6. Tích trong

Phép toán ~(x, y)~ có kết quả là số thực được gọi là một tích trong của không gian tuyến tính thực ~V~ khi có đồng thời các tính chất sau:

Tính đối xứng: ~\forall x, y \in V: (x,y) = (y,x)~

Tính phân phối: ~\forall x, y, z \in V: (x, y + z) = (x, y) + (x, z)~

Tính kết hợp: ~\forall c \in \mathbb{R}, x, y \in V: c(x, y) = (cx, y)~

Tính dương: ~\forall x \in V, x \ne 0: (x, x) > 0~

Một không gian tuyến tính thực được trang bị tích trong được gọi là không gian Euclid thực.

Với không gian tuyến tính phức, tích trong ~(x, y)~ có kết quả là số phức. Thay vì tính đối xứng, tích trong cần thỏa mãn tính đối xứng Hermitian

~\forall x, y \in V: (x, y) = \overline{(y,x)}~ (với ~u \in \mathbb{C}~, ~\overline{u}~ là số phức liên hợp của ~u~)

và tính kết hợp được định nghĩa như sau:

~\forall c \in \mathbb{C}, x, y \in V: c(x,y) = c\overline{(y,x)} = \overline{(\overline{c}y, x)} = (x, \overline{c}y)~

(Bất đẳng thức Cauchy-Schwart) Cho không gian Euclid ~V~. ~\forall x, y \in V: |(x, y)|^2 \geq (x,x)(y,y)~. Dấu bằng xảy ra khi và chỉ khi ~x, y~ phụ thuộc tuyến tính.

Trong không gian Euclid ~V~, ~|x| = (x,x)^{\frac12}~ được định nghĩa là chuẩn của ~x~. Chuẩn có các tính chất sau:

~|x| \geq 0~. Dấu bằng xảy ra khi và chỉ khi ~x = 0~

~\forall x \in V, c \in \mathbb{R}: |cx| = c|x|~

(Bất đẳng thức tam giác) ~\forall x, y \in V: |x| + |y| \geq |x+y|~. Dấu bằng xảy ra khi và chỉ khi ~x = 0~ hoặc ~y = 0~ hoặc ~\exists c>0: y = cx~

Trong không gian Euclid ~V~, góc giữa hai phần tử ~x~ và ~y~ được định nghĩa là số thực ~\theta~ thỏa mãn ~0 \leq \theta \leq \pi~ và ~\cos \theta = \frac{(x,y)}{|x||y|}~

7. Vuông góc

Trong không gian Euclid ~V~:

Hai phần tử ~x~, ~y~ được gọi là hai phần tử vuông góc khi ~(x,y)=0~

Một tập ~S \subset V~ được gọi là tập trực giao khi ~\forall x, y \in S, x \ne y: (x,y) = 0~

Một tập trực giao ~S~ được gọi là tập trực chuẩn khi ~\forall x \in S: |x| = 1~

Mọi tập trực giao khác rỗng đều độc lập tuyến tính.

Nếu ~S = \{e_1, e_2, ..., e_n\}~ là một cơ sở trực giao của ~V~ thì ~\forall x \in V: x = \sum_{i=1}^n \frac{(x, e_i)}{(e_i, e_i)}e_i~

(Công thức Parseval) Nếu ~S = \{e_1, e_2, ..., e_n\}~ là một cơ sở trực chuẩn của ~V~ thì ~\forall x, y \in V: (x,y) = \sum_{i=1}^n(x, e_i)\overline{(y, e_i)}~

Khi ~x=y~, công thức Parseval trở thành ~(x, x) = \sum_{i=1}^n (x, e_i)^2~ (định lí Pythagore)

1. Quá trình Gram-Schmidt

Cho một dãy ~x_1, x_2, ...~ gồm vô hạn hay hữu hạn phần tử của không gian Euclid ~V~. Khi đó sẽ có một dãy phần tử ~y_1, y_2, ...~ thuộc ~V~ tương ứng có các tính chất sau với mỗi ~k \in \mathbb{N}^*~:

1. ~\forall e \in \text{span } \{y_1, y_2, ..., y_{k-1}\}: (e, y_k) = 0~
2. ~\text{span } \{x_1, x_2, ..., x_k\} = \text{span } \{y_1, y_2, ..., y_k\}~
3. ~|y_k| = 1~

Quá trình Gram-Schmidt:

~y_1 = x_1~

~y_{r+1} = x_{r+1} - \sum_{i=1}^r \text{proj }_{y_i}(x_{r+1})~ với ~r \in \mathbb{N}^*~

(~\text{proj }_{y}(x) = \frac{(x, y)}{(y, y)}y~ được gọi là phần tử chiếu trực giao của ~x~ trên ~y~)

Quá trình này sẽ tạo ra một tập trực giao (có thể biến đổi thành tập trực chuẩn)

Mọi không gian Euclid hữu hạn chiều đều có một cơ sở trực giao.

9. Hình chiếu

Cho ~S \subset V~ của không gian Euclid ~V~ (~S~ không nhất thiết là không gian con). Một phần tử ~x~ của ~V~ vuông góc với ~S~ khi ~\forall y \in S: (x,y) = 0~. Tập hợp các phần tử vuông góc với ~S~ được kí hiệu ~S^\perp~ và được gọi là phần bù trực giao của ~S~.

~S^\perp~ luôn là không gian con của ~V~.

Cho không gian Euclid ~V~ và không gian con hữu hạn chiều ~S~ của ~V~. Khi đó, ~\forall x \in V:~ tồn tại duy nhất một cặp ~(s, s^\perp) \in S \times S^\perp~ thỏa mãn ~x = s + s^\perp~. Ngoài ra, ~|x|^2 = |s|^2 + |s^\perp|^2~

Cho không gian con hữu hạn chiều ~S~ của không gian Euclid ~V~ có ~\{e_1, e_2, ..., e_n\}~ là một cơ sở chuẩn tắc. Với ~x \in V~, ta gọi ~s = \sum_{i=1}^n (x, e_i)e_i~ là hình chiếu của ~x~ trên ~S~.

~\forall t \in S: |x-s| \leq |x-t|~, dấu bằng xảy ra khi và chỉ khi ~s = t~.

II. Phép biến đổi tuyến tính và ma trận

1. Phép biến đổi tuyến tính, tập giá trị, hạt nhân.

Với ~V, W~ là hai không gian tuyến tính. Hàm ~T: V \rightarrow W~ được gọi là một phép biến đổi tuyến tính khi:

~\forall x, y \in V: T(x + y) = T(x) + T(y)~ và ~\forall c \in \mathbb{R}, x \in V: cT(x) = T(cx)~

Tập ~T(V) = \{T(x) | x \in V\}~ là một không gian con của ~W~, và ~T(0) = 0~. ~\text{rank } T = \dim T(V)~

Tập ~\ker T = \{x | x \in V \text{ và } T(x) = 0\}~ được gọi là hạt nhân của ~V~ và là một không gian con của ~V~

(Định lí hạng và số vô hiệu) Nếu ~V~ là không gian tuyến tính, với mọi phép biến đổi tuyến tính ~T~, ~\text{rank } T + \dim \ker T = \dim V~

2. Hàm ngược

Nếu ~T: V \rightarrow W~ có hàm ngược trái ~S: W \rightarrow V~ (tức ~\forall x \in V: (S \circ T)(x) = x~) thì ~T~ là hàm đơn ánh.

Nếu ~T: V \rightarrow W~ có hàm ngược phải ~S: W \rightarrow V~ (tức ~\forall x \in W: (T \circ S)(x) = x~) thì ~T~ là hàm toàn ánh.

Một hàm vừa đơn ánh và toàn ánh là hàm song ánh.

Phép biến đổi tuyến tính ~T: V \rightarrow W~ là hàm đơn ánh ~\Leftrightarrow \ker T = \{0\}~

Nếu ~\dim V = \dim W < +\infty~ thì với phép biến đổi tuyến tính ~T: V \rightarrow W~, ~T~ là hàm đơn ánh ~\Leftrightarrow T~ là hàm song ánh ~\Leftrightarrow T~ là hàm toán ánh. Ngoài ra, mọi hàm ngược trái của ~T~ đều là hàm ngược phải, và mọi hàm ngược phải của ~T~ đều là hàm ngược trái.

3. Ma trận

Với không gian tuyến tính ~V~ có cơ sở ~\{e_1, e_2, ..., e_n\}~ và ~u_1, u_2, ..., u_n \in W~ bất kì. Khi đó tồn tại duy nhất một phép biến đổi tuyến tính ~T: V \rightarrow W~ thỏa mãn ~\forall k \in \mathbb{N}^*, k \leq n: T(e_k) = u_k~.

Với phép biến đổi tuyến tính ~T~ này, nếu ~x = \sum_{i=1}^n x_i e_i~ thì ~T(x) = \sum_{i=1}^n x_i u_i~

Cho phép biến đổi tuyến tính ~T: V \rightarrow W~ (~\dim V = n~, ~\dim W = m~). ~(e_1, e_2, ..., e_n)~ là cơ sở của ~V~, ~(w_1, w_2, ..., w_m)~ là cơ sở của ~W~. Ma trận ~(t_{ik})~ có chiều ~m \times n~ thỏa mãn ~\forall k \in \mathbb{N}^*, k \leq n: T(e_k) = \sum_{i=i}^m t_{ik} w_i~. Khi đó, nếu ~T(\sum_{k=1}^n x_k e_k) = \sum_{i=1}^m y_i w_i~ thì ~\forall i \in \mathbb{N}^*, i \leq m: y_i = \sum_{k=1}^n t_{ik} x_i~.

Ma trận ~(t_{ik})~ như trên được kí hiệu là ~m(T)~ và được gọi là ma trận của ~T~ ứng với hai cơ sở được cho.

Gọi ~\mathcal{L}(V, W)~ là tập hợp các phép biến đổi tuyến tính ~T: V \rightarrow W~. ~\mathcal{L}(V, W)~ là một không gian tuyến tính.

~m: \mathcal{L}(V, W) \rightarrow M_{\dim W, \dim V}~ là một phép biến đổi tuyến tính và cũng là hàm đơn ánh.

~m(T \circ S) = m(T)m(S)~

~m(T)~ khả nghịch ~\Leftrightarrow T~ khả nghịch. Nếu ~Bm(T) = I~ thì ~B = m(T^{-1})~

III. Định thức

Cho ma trận ~A~ vuông ~n \times n~, ta kí hiệu các hàng của ma trận là ~A_1, A_2, ..., A_n~, và kí hiệu định thức của ma trận ~A~ là ~\det A = \det(A_1, A_2, ..., A_n)~

Các tiên đề về định thức:

~\det(A_1, A_2, ..., A_{k-1}, tA_k, A_{k+1}, ..., A_n) = t \det(A_1, A_2, ..., A_n)~

~\det(A_1, A_2, ..., A_k + C, ..., A_n) = \det(A_1, A_2, .., A_k, ..., A_n) + \det(A_1, A_2, ..., C , ..., A_n)~

Nếu ~\exists i \ne j: A_i = A_j~ thì ~\det A = 0~

~\det I = 1~

Chỉ có duy nhất một hàm ~\det: M_{n, n}(X) \rightarrow X~ thỏa mãn 4 tiên đề trên.

Các tính chất của định thức:

Nếu ~\exists i: A_i = 0~, ~\det A = 0~

~\det(..., A_k, A_{k+1}, ...) = -\det(..., A_{k+1}, A_k, ...)~

Nếu các hàng của ~A~ phụ thuộc tuyến tính, ~\det A = 0~

~\forall A, B \in M_{n, n}: \det(AB) = \det(A)\det(B)~

Nếu ma trận ~A~ khả nghịch, ~\det(A^{-1}) \ne 0~ và ~\det(A^{-1}) = \frac{1}{\det(A)}~

Nếu ~\det(A^{-1}) \ne 0~ thì ma trận ~A~ khả nghịch.

~A_1, A_2, ..., A_n~ độc lập tuyến tính ~\Leftrightarrow \det(A_1, A_2, ..., A_n) \ne 0~

Với hai ma trận vuông ~A, B~, ~\det \begin{bmatrix} A & 0 \\ 0 & B \\ \end{bmatrix} = (\det A)(\det B)~

~\det A = \sum_{j=1}^n a_{kj}\text{cof } a_{kj}~ với ~\text{cof } a_{kj} = (-1)^{k+j}\det A_{kj}~ (được gọi là phần bù đại số của số hạng tại vị trí ~(k, j)~) và ~A_{kj}~ là ma trận ~A~ bị xóa hàng ~k~ và cột ~j~.

~\det A^T = \det A~

~\text{cof } A~ là ma trận các phần bù đại số của ~A~. Khi đó ~A(\text{cof } A)^T = (\det A)I~

IV. Giá trị đặc trưng

Nếu ~A = (a_{ij})~ là một ma trận chéo, ta viết ~A = \text{diag }(a_{11}, a_{22}, ..., a_{nn})~

Cho một phép biến đổi tuyến tính ~T: V \rightarrow V~, ~\dim V = n~. Ma trận của ~T~ là ma trận chéo khi và chỉ khi tồn tại một cơ sở ~u_1, u_2, ..., u_n~ của ~T~ và các số ~\lambda_1, \lambda_2, ..., \lambda_n~ tương ứng thỏa mãn ~\forall k \in \mathbb{N}^*, k \leq n: T(u_k) = \lambda_k u_k~.

Khi đó, ~A = \text{diag } (\lambda_1, \lambda_2, ..., \lambda_n)~ là ma trận của phép biến đổi ~T~ ứng với cơ sở ~(u_1, u_2, ..., u_n)~

Đề thi này được mình soạn theo các nguyên tắc sau:

• Theo cấu trúc của đề thi các môn trắc nghiệm của kì thi Đại học - Cao đẳng năm 2013.
  • Hầu hết các câu hỏi thuộc chương trình lớp 12
  • Có phần riêng dành cho các đối tượng thí sinh khác nhau.
  • Lưu ý: Các câu hỏi không được sắp xếp theo thứ tự độ khó tăng dần.
• Mỗi câu hỏi kiểm tra một năng lực của chương trình giáo dục phổ thông môn Tin học năm 2018
  • Phần chung và phần A chỉ kiểm tra các kĩ năng mà thí sinh cả hai định hướng cùng được học (giống như đề thi THPT QG hiện tại chỉ kiểm tra các kĩ năng mà thí sinh ở hai chương trình Cơ bản và Nâng cao đều cùng được học).
  • Phần B, C sẽ kiểm tra các kĩ năng của riêng một định hướng nào đó.
• Nguồn câu hỏi:
  • Sinh bởi ChatGPT theo cú pháp: Tạo một câu hỏi trắc nghiệm độ khó X kiểm tra kĩ năng Y
  • Các bộ sách giáo khoa Tin học lớp 10, 11 hiện hành
  • Các dạng câu hỏi kiểm tra kĩ năng tương tự trong bài thi AP, A-Level, và GRE.

Lưu ý đây không phải một đề thi THPT QG chuẩn, các bạn nếu đọc thấy đề khó quá thì không nên hoang mang, hay nếu thấy dễ quá thì cũng đừng quá tự tin.

I. PHẦN CHUNG CHO TẤT CẢ THÍ SINH (7,0 điểm)

Câu 1: Trí tuệ nhân tạo (AI) là một lĩnh vực nghiên cứu mang lại những tiến bộ đáng kể trong thế kỷ 21. Hãy chọn phát biểu đúng nhất về khái niệm AI:

A. AI chỉ là khả năng của máy tính thực hiện các nhiệm vụ mà yêu cầu sự học hỏi và tự động cải thiện.

B. AI là khả năng tự suy nghĩ và có ý thức của máy tính, đưa ra quyết định như con người.

C. AI chỉ liên quan đến việc mô phỏng khả năng thực hiện các công việc cụ thể mà con người thường thực hiện.

D. AI là một lĩnh vực nghiên cứu chỉ giới hạn trong việc tạo ra robot thông minh có khả năng tương tác với môi trường xung quanh.

Câu 2: Chuyển đổi chữ bác sĩ sang dạng xâu kí tự dễ đọc trên máy tính là ứng dụng nào sau đây của "Trí tuệ nhân tạo"?

A. Điều khiển tự động

B. Chẩn đoán bệnh

C. Nhận dạng chữ viết tay

D. Trợ lí ảo

Câu 3: Hệ thống AI nào sau đây thường chỉ có khả năng học chứ không có tri thức hay khả năng suy luận

A) Mô hình học sâu (deep learning)

B) Hệ thống chẩn đoán y tế dựa trên nguyên tắc

C) Hệ thống suy diễn (inference system)

D) Không tồn tại hệ thống AI nào như vậy do mọi hệ thống AI đều có tri thức, khả năng học và khả năng suy luận

Câu 4: Trí tuệ nhân tạo (AI) đã và đang góp phần quan trọng vào sự phát triển của nhiều lĩnh vực trong khoa học, công nghệ và đời sống. Hãy chỉ ra lĩnh vực nào sau đây đang phát triển mạnh mẽ nhờ vào những đóng góp to lớn của AI:

A) Y tế

B) Tài chính - Ngân hàng

C) Giáo dục

D) Cả ba phương án trên

Câu 5: Cho bốn phát biểu sau:

1, Sự phát triển của trí tuệ nhân tạo sẽ làm nhiều ngành nghề bị mất đi.

2, Kẻ xấu có thể sử dụng trí tuệ nhân tạo để tạo ra những phần mềm virus tinh vi hơn.

3, Dữ liệu của người dùng trên mạng xã hội có thể bị thu thập và xử lí bằng trí tuệ nhân tạo để phục vụ cho những mục đích không đúng đắn.

4, Con người có thể lệ thuộc vào các công nghệ dựa trên trí tuệ nhân tạo.

Trong số bốn phát biểu trên, có bao nhiêu phát biểu về rủi ro của sự phát triển của trí tuệ nhân tạo đối với toàn xã hội?

A) 1

B) 2

C) 3

D) 4

Câu 6: Biến đổi dữ liệu số thành tín hiệu analog và ngược lại là chức năng của thiết bị nào sau đây?

A) Access Point

B) Switch

C) Modem

D) Cả ba thiết bị trên

Câu 7: Khi bạn muốn kết nối một Access Point (AP) với máy tính (PC), bạn sẽ thực hiện các bước nào sau đây?

A) Sử dụng cáp Ethernet để kết nối AP với PC, sau đó cấu hình địa chỉ IP tĩnh cho cả hai thiết bị.

B) Kết nối AP với PC bằng cáp USB và sử dụng phần mềm điều khiển để thiết lập kết nối.

C) Sử dụng kết nối Bluetooth để ghép đôi AP và PC, sau đó cấu hình mạng không dây.

D) Kết nối AP với PC qua một mạng không dây hiện có và sử dụng giao thức WPS để tự động cấu hình kết nối.

Câu 8: Chức năng chính của giao thức TCP/IP là gì?

A) Quản lý tài nguyên mạng và máy tính.

B) Chuyển đổi địa chỉ IP thành tên miền.

C) Đảm bảo truyền tải tin nhắn và dữ liệu một cách đáng tin cậy.

D) Kiểm soát quyền truy cập vào mạng.

Câu 9: Cụm từ tiếng Anh nào sau đây nhiều khả năng là tên một chức năng mạng của hệ điều hành cho phép chia sẻ tập tin và thư mục trong mạng LAN?

A) Firewall Settings

B) Network Discovery

C) Power Management

D) Screen Resolution

Câu 10: Khi bạn cố gắng kết nối một thiết bị di động vào mạng máy tính trong điều kiện mà cả phần cứng và phần mềm đã được chuẩn bị đầy đủ, bạn sẽ thực hiện các bước nào sau đây để đảm bảo kết nối thành công?

A) Kiểm tra xem thiết bị di động có hỗ trợ giao thức mạng nào và đảm bảo rằng nó tương thích với mạng máy tính.

B) Sử dụng cáp USB để kết nối thiết bị di động với máy tính và chờ đợi phần mềm điều khiển tự động cài đặt.

C) Kích hoạt chế độ kết nối không dây trên thiết bị di động và chọn mạng Wi-Fi tương ứng từ danh sách có sẵn.

D) Cấu hình địa chỉ IP tĩnh cho cả thiết bị di động và máy tính, sau đó thực hiện kết nối bằng cách sử dụng cáp Ethernet.

Câu 11: Nhược điểm nổi bật của giao tiếp trong thế giới ảo là:

A) Thường thiếu những đặc điểm của ngôn ngữ nói như giọng điệu, nét mặt, ...

B) Thiếu sự linh hoạt trong việc sử dụng biểu tượng cảm xúc.

C) Khó khăn trong việc lưu trữ thông tin.

D) Thông tin cá nhân có thể bị giả mạo.

Câu 12: Một nhà báo thể thao viết một bài đăng trên mạng xã hội về thất bại của đội tuyển bóng đá Việt Nam ở một giải đấu gần đây. Một số người dùng đã đăng tải những bình luận sau:

Bình luận 1: Mình thì chả có vđề gì, quan trọng là các em nó đc thi đấu và có kn quốc tế. Cái nhìn của mình vs giải đấu này ko phải là màn trình diễn của cả đội mà là tố chất của từng cầu thủ

Bình luận 2: cái kiểu bình luận khiếm nhã, chửi rủa các kiểu thì nói thật hoặc là bọn cá độ bóng đá, hoặc là kiểu thấy có bóng đá thì xem chứ CHƯA CHẮC là đã biết hết về lực lượng mình hay quy chế giải đấu

Bình luận 3: Nói chung là dân xem bóng đá xứ này lạ lắm. Suốt ngày chê bai là ko chịu thử nghiệm, ko chịu xoay tua,..., nhưng chỉ cần 1 giải có thành tích ko đủ tốt là chửi té tát. Bảo sao áp lực thành tích lại chả lớn :))))))

Bình luận 4: Xem bóng đá để giải trí thôi, không nên đè nặng thành tích cho ĐTVN vì nền bóng đá của chúng ta vẫn còn non trẻ ao vs thế giới. Ở đẳng cấp thế giới còn 1 khoảng cách rất xa.

Có bao nhiêu bình luận trong số các bình luận trên mang tính tấn công cá nhân?

A) 0

B) 1

C) 2

D) 3

Câu 13: Cây DOM được tổ chức dưới dạng nào sau đây?

A) Đồ thị có hướng không có chu trình.

B) Cây có gốc

C) Cây nhị phân tìm kiếm

D) Cả hai phương án A và B đều đúng.

Câu 14: Cho biểu mẫu trên trang localhost/html_forms.asp sau:

<form action="/action_page.php">
  <label for="fname">First name:</label><br>
  <input type="text" id="fname" name="fname" value="John"><br>
  <label for="lname">Last name:</label><br>
  <input type="text" id="lname" name="lname" value="Doe"><br><br>
  <input type="submit" value="Submit">
</form>

Khi người dùng không thay đổi giá trị của các ô và nhấn vào nút Submit, người dùng sẽ được điều hướng đến trang nào sau đây?

A) localhost/html_forms.asp

B) localhost/html_forms.asp/action_page.php

C) localhost/html_forms.asp/action_page.php?firstname=John&lastname=Doe

D) localhost/action_page.php?firstname=John&lastname=Doe

Câu 15: Cho đoạn mã HTML sau

<head>
    <style>
        #sampleText {
            color: #ffff00;
            font-family: "Arial";
            font-size: 20px;
            border: dashed #ffffff;
            background-color: #ff0000;
        }
    </style>
</head>
<body>
    <div id="sampleText">Sample</div>
</body>

Phương án nào sau đây mô tả dòng chữ được tạo bởi đoạn mã trên?

A) Chữ Sample màu đỏ, nền vàng, viền trắng đứt đoạn

B) Chữ Sample màu đỏ, nền vàng, viền trắng nét liền.

C) Chữ Sample màu vàng, nền đỏ, viền trắng đứt đoạn.

D) Chữ Sample màu vàng, nền đỏ, viền trắng nét liền.

Câu 16: Cho đoạn mã HTML sau:

<head>
    <style>
        .highlight {
            background-color: #000000;
            color: #ffffff;
        }
    </style>
</head>
<body>
    // insert code here
</body>

Ta cần thay // insert code here bằng lệnh nào sau đây để được chữ Sample màu trắng trên nền đen?

A) <p class="highlight">Sample</p>

B) <p tag="highlight">Sample</p>

C) <p id="highlight">Sample</p>

D) <p selector="highlight">Sample</p>

Câu 17: Chuyên viên tin học của một bệnh viện thường có nhiệm vụ gì?

A) Lập trình ứng dụng di động cho bác sĩ.

B) Quản lý hệ thống thông tin của bệnh viện.

C) Thiết kế trang web cho bệnh nhân.

D) Phân tích dữ liệu định kỳ từ các máy chụp hình y khoa.

Câu 18: Để làm nghề Sửa chữa và bảo trì máy tính, người làm nghề cần:

A) Hiểu biết sâu rộng về phần cứng máy tính, từ việc lắp ráp đến sửa chữa các linh kiện.

B) Chủ yếu tập trung vào việc cài đặt và cấu hình phần mềm để giải quyết vấn đề.

C) Chỉ cần biết cách sử dụng các công cụ chẩn đoán tự động để xác định lỗi.

D) Được đào tạo chỉ về một lĩnh vực cụ thể như bảo trì hệ điều hành mà không cần biết đến phần cứng.

Câu 19: Sau kì thi Trung học phổ thông Quốc gia, bạn A đã trúng tuyển vào bốn ngành học sau đây. Bạn A nên chọn ngành học nào để được học nhiều kiến thức chuyên môn liên quan đến nghề Quản trị và bảo trì hệ thống nhất?

A) Khoa học dữ liệu

B) Trí tuệ nhân tạo

C) Kỹ thuật sửa chữa, lắp ráp máy tính

D) Kỹ thuật phần mềm

Câu 20: Để tự tìm kiếm và khai thác thông tin hướng nghiệp trong lĩnh vực tin học, bạn nên:

A) Chỉ tập trung vào các chương trình đào tạo chính thức của các trường đại học.

B) Sử dụng công cụ tìm kiếm để tìm hiểu thông báo tuyển dụng từ các doanh nghiệp.

C) Chỉ dựa trên những lời khuyên từ ông bà, cha mẹ.

D) Bỏ qua các sự kiện, hội thảo ngành nghề, hoặc các cộng đồng trực tuyến về tin học.

Câu 21: Để giao lưu được với bạn bè qua các kênh truyền thông số để tham khảo và trao đổi ý kiến về những thông tin hướng nghiệp trong lĩnh vực tin học, bạn nên:

A) Chỉ chia sẻ thông tin cá nhân và không nên thảo luận về kiến thức chuyên ngành.

B) Tham gia vào các nhóm chuyên ngành trên mạng xã hội để chia sẻ thông tin và tìm hiểu ý kiến của cộng đồng.

C) Giữ thông tin cho riêng mình và không nên tham gia các diễn đàn công khai.

D) Chỉ sử dụng email để trao đổi ý kiến và thông tin với bạn bè.

Câu 22: Để đưa các tệp dữ liệu đa phương tiện vào trang web bằng HTML, bạn sẽ sử dụng thẻ nào sau đây?

A) <media>

B) <multimedia>

C) <file>

D) <img>

Câu 23: Phương án nào sau đây chỉ chứa các thẻ dùng để tạo bảng?

A) <thead>, <body>, <tr>

B) <table>, <tr>, <tt>

C) <table>, <head>, <tfoot>

D) <table>, <tr>, <td>

Câu 24: Thẻ <iframe> thường được dùng để

A) Tạo bảng

B) Chèn nội dung của một trang web khác

C) Định dạng đoạn văn

D) Chèn siêu liên kết

Câu 25: Phát biểu nào sau đây về nhu cầu nhân lực của xã hội Việt Nam trong hiện tại và tương lai gần về nhóm nghề Dịch vụ và Quản trị máy tính tại đúng nhất?

A) Hầu hết các công ty công nghệ tại Việt Nam chưa có nhu cầu về nhóm nghề này.

B) Với sự gia tăng của doanh nghiệp và công ty công nghệ, nhu cầu về nhóm nghề này ngày càng tăng cao.

C) Sự phát triển của công nghệ trí tuệ nhân tạo sẽ làm nhu cầu về nhân lực trong lĩnh vực này trở nên thừa thãi và không cần thiết.

D) Nhu cầu nhân lực của xã hội đối với nhóm nghề Dịch vụ và Quản trị máy tính thường thấp hơn so với nhu cầu đối với nhóm nghề Quản trị cơ sở dữ liệu.

Câu 26: Quan niệm nào sau đây là không đúng?

A. Mọi tin nhắn, hình ảnh và video đăng tải lên mạng đều có thể thu hồi.

B. Cần nhanh chóng thông báo tới các cơ quan chức năng, nhà cung cấp dịch vụ khi tài khoản của tổ chức, cá nhân bị mất quyền kiểm soát, bị giả mạo.

C. Cần phê phán các từ ngữ không mang tính phổ thông nặng bản sắc vùng miền.

D. Khi ứng xử trên mạng xã hội, ta được phép làm mọi điều pháp luật không cấm.

Câu 27: Tại sao mật khẩu của người dùng trong cơ sở dữ liệu cần được mã hóa?

A) Để giảm dung lượng của cơ sở dữ liệu.

B) Để tăng tốc độ truy vấn.

C) Để bảo mật thông tin của người dùng.

D) Cả ba phương án trên.

Câu 28: Cho bảng sau

Cột nào trong bảng trên có thể được chọn làm khóa?

A) Cột ID

B) Cột Name

C) Cột Number

D) Cột Choice

Câu 29: Số nghiệm nguyên của phương trình ~x~ AND 26 OR 5 = 23 thuộc ~[0; 2^5)~ là

A) 2

B) 4

C) 8

D) 16

Câu 30: Cho thuật toán sau:

1. Gán ~k \leftarrow 999, i \leftarrow 1~, và ~p \leftarrow 0~
2. Nếu ~k > i~ thì thực hiện bước 3, nếu không thì thực hiện bước 5.
3. Gán ~i \leftarrow 2i~ và ~p \leftarrow p+1~
4. Thực hiện bước 2
5. In giá trị của ~p~. Kết thúc chương trình

Thuật toán này sẽ in ra giá trị nào ở bước 5?

A) 1

B) 2

C) 10

D) 512

Câu 31: Cho mạch logic sau

Khi ~A = 0, B = 1~, đầu ra (output) của mạch là:

A) 0

B) 1

C) 0 và 1

D) không xác định

Câu 32: Máy tính có ổ cứng SSD gắn sẵn trong máy tính có dung lượng 128 GB, dung lượng ổ cứng HDD gắn sẵn trong máy là 250 GB, RAM có dung lượng 8 GB. Vậy dung lượng lưu trữ của máy tính là:

A. 128 GB.

B. 250 GB.

C. 378 GB.

D. 386 GB.

II. PHẦN RIÊNG (3,0 điểm): Thí sinh chỉ được làm một trong ba phần (phần A, phần B, hoặc phần C)

A. Phần dành cho thí sinh thi chỉ nhằm mục đích xét tốt nghiệp và/hoặc dự thi Cao đẳng

Câu 33: Giấy phép của một phần mềm nguồn mở có biểu tượng sau:

Khi tạo một phần mềm mới dựa trên mã nguồn của phần mềm nguồn mở này, lập trình viên:

A) phải trả cho người viết phần mềm gốc một phần của số tiền thu được từ phần mềm mới

B) không được phép thay đổi mã nguồn của phần mềm gốc

C) phải ghi nhận đóng góp của các tác giả phần mềm gốc

D) phải đặt các điều khoản bản quyền của phần mềm mới giống hệt phần mềm gốc

Câu 34: Đây là bộ phận nào của máy tính?

A) CPU

B) RAM

C) Ổ cứng SSD

D) Bộ nguồn máy tính

Câu 35: Kiến trúc hệ cơ sở dữ liệu phân tán (Distributed Database Architecture) có đặc điểm nào sau đây?

A) Dữ liệu được lưu trữ tại một điểm duy nhất

B) Dữ liệu được phân chia và lưu trữ trên nhiều vị trí vật lý

C) Hệ thống chỉ có một trung tâm quản lý

D) Tất cả các phương án trên

Câu 36: Khi sử dụng Google để tìm kiếm thông tin về virus Corona, em sử dụng từ khoá nào sau đây để thu hẹp phạm vi tìm kiếm nhất?

A) Corona.

B) Virus Corona.

C) "Virus Corona".

D) "Virus"+"Corona".

Câu 37: Một máy tính muốn hoạt động được thì nhất thiết phải có thành phần nào sau đây?

A) Phần cứng

B) Hệ điều hành

C) Phần mềm ứng dụng

D) Phần cứng và hệ điều hành

Câu 38: Cho dãy số nguyên 35, 34, 67, 89, 102, 42. Dãy số này

A) là dữ liệu nhưng không là thông tin.

B) là thông tin nhưng không là dữ liệu.

C) vừa là dữ liệu, vừa là thông tin.

D) không phải là dữ liệu, cũng không phải là thông tin.

Câu 39: Cho các phát biểu sau:

1. LAN được sử dụng trong một phạm vi hẹp hơn so với Internet.
2. LAN sử dụng công nghệ cáp, fiber hoặc không dây để kết nối các thiết bị trong một khu vực nhỏ.
3. Internet là một mạng toàn cầu được sử dụng để kết nối các máy tính và thiết bị trên toàn thế giới.
4. Cả LAN và Internet đều được sử dụng để truyền tải dữ liệu giữa các thiết bị.

Số phát biểu đúng là

A) 1

B) 2

C) 3

D) 4

Câu 40: Học sinh có thể truy cập trang web nào sau đây để tải bản số hóa các bộ sách giáo khoa phổ thông do Nhà xuất bản Giáo dục Việt Nam phát hành một cách miễn phí và hợp pháp?

A) taisach.net

B) igiaoduc.vn

C) hieusachonline.vn

D) blogspot.com

B. Phần theo chương trình Định hướng Khoa học máy tính

Câu 41: Cấu trúc dữ liệu ~S~ có hai phương thức sau:

• S.insert(x): Thêm kí tự ~x~ vào ~S~
• S.pop(): Lấy một kí tự ra khỏi ~S~ và in kí tự đó ra màn hình

Khi chạy thuật toán

S.insert(A); S.insert(B); S.pop(); S.insert(C); S.pop(); S.pop()

Ta thấy xâu kí tự BCA được in ra màn hình. ~S~ là có thể là cấu trúc dữ liệu nào sau đây?

A) Ngăn xếp

B) Hàng đợi

C) Vừa có thể là ngăn xếp, vừa có thể là hàng đợi

D) Không thể là ngăn xếp lẫn hàng đợi.

Câu 42: Một lập trình viên đã dùng cấu trúc dữ liệu Cây nhị phân tìm kiếm tự cân bằng thay vì cấu trúc dữ liệu Hàng đợi trong thuật toán Tìm kiếm theo chiều rộng. Thuật toán này được chạy trên một đồ thị ~G~ liên thông gồm ~V~ đỉnh (các đỉnh được đánh số) và ~E~ cạnh (~V = O(E)~), đồ thị được biểu diễn bằng danh sách kề. Mỗi khi cây nhị phân tìm kiếm tự cân bằng được sử dụng, đỉnh có số thứ tự nhỏ nhất trong cây sẽ bị xóa.

Cho các phát biểu sau về độ phức tạp tính toán của thuật toán mới:

1, Độ phức tạp tính toán của thuật toán mới là ~O(V\log V + E\log E)~

2, Độ phức tạp tính toán của thuật toán mới là ~O(V\log V + E)~

3, Độ phức tạp tính toán của thuật toán mới là ~O(V + E\log E)~

4, Độ phức tạp tính toán của thuật toán mới là ~O(V\log E + E\log E)~

Số phát biểu đúng là:

A) 1

B) 2

C) 3

D) 4

Câu 43: Xét bài toán Tháp Hà Nội có ~4~ đĩa, các đĩa có giá trị ~1, 2, 3, 4~ tùy theo kích thước của đĩa, đĩa nhỏ nhất có giá trị ~1~ và đĩa lớn nhất có giá trị ~4~. Trong quá trình giải bài toán này, có bao nhiêu thời điểm mà tổng giá trị các đĩa trên một cọc bằng ~6~

A) 0

B) 1

C) 2

D) 3

Câu 44: Cho cây ~n~ cạnh (~n \geq 5~). Có tối thiểu bao nhiêu cạnh thỏa mãn điều kiện nếu xóa cạnh đó thì cây được chia thành hai thành phần liên thông, mỗi thành phần liên thông có số cạnh nhỏ hơn hoặc bằng ~\frac{n-1}{2}~?

A. 0

B. 1

C. 3

D. 4

Câu 45: Cho thiết kế mạng máy tính như hình vẽ bên dưới, với số ứng với mỗi dây cáp là tốc độ truyền dữ liệu từ một thiết bị sang một thiết bị khác theo chiều mũi tên (tốc độ truyền dữ liệu được tính theo đơn vị Mbps). Để truyền 4GB dữ liệu từ Access Point A đến Modem M, ta cần khoảng thời gian tối thiểu ~a~. Giá trị của ~a~ gần nhất với giá trị nào sau đây.

A) 30 phút

B) 27 phút

C) 60 phút

D) 54 phút

Câu 46: Nhóm giải thuật Học máy nào sau đây có thể giải quyết trực tiếp bài toán dự đoán giá cổ phiếu dựa vào dữ liệu lịch sử của cổ phiếu đó?

A) Nhóm giải thuật phân loại, học có giám sát

B) Nhóm giải thuật hồi quy, học có giám sát

C) Nhóm giải thuật học củng cố

D) Nhóm giải thuật phân nhóm, học không có giám sát

Câu 47: Cho các hàm sau:

~T_1(n) = T_1(\frac{n}{2}) + O(n)~

~T_2(n) = 2T_2(\frac{n}{2}) + O(n)~

~T_3(n) = 3T_3(\frac{n}{2}) + O(\log n)~

~T_4(n) = 2T_4(\frac{n}{2}) + O(n \log n)~

Sắp xếp các hàm trên theo thứ tự độ phức tạp tính toán tăng dần:

A) ~T_1, T_2, T_4, T_3~

B) ~T_1, T_2, T_3, T_4~

C) Cả hai phương án A và B đều đúng.

D) Cả hai phương án A và B đều sai.

Câu 48: Một nhà thiên văn đã thu thập được dữ liệu về vị trí các ngôi sao thuộc hai chòm sao dưới dạng các điểm trên mặt phẳng Oxy như hình dưới đây.

Thuật toán Học máy nào sẽ giúp nhà thiên văn tách dữ liệu của hai chòm sao một cách hiệu quả nhất?

A) K-Means

B) Hierarchical clustering

C) Hồi quy tuyến tính

D) Cả ba thuật toán trên đều có hiệu quả gần như nhau.

C. Phần theo chương trình Định hướng Tin học ứng dụng (đang cập nhật)

Câu 1: Số ~10111_2~ bằng số nào sau đây:

A. 22

B. 23

C. 29

D. 28

Câu 2: Ta có thể biểu diễn ~21_{10}~ dưới dạng số nhị phân ~\overline{d_4d_3d_2d_1d_0}_2~. ~d_3 + d_2 + d_1 + d_0~ bằng giá trị nào dưới đây

A. 1

B. 2

C. 3

D. 4

Câu 3: ~1011_2 \times 16_{10}~ bằng giá trị nào dưới đây

A. ~10110000_2~

B. ~101111111_2~

C. ~00001011_2~

D. ~11001100_2~

Câu 4: ~\lfloor \frac{1001011_2}{8_{10}} \rfloor~ bằng giá trị nào dưới đây

A. ~1001_2~

B. ~1011_2~

C. ~100_2~

D. ~10010_2~

Câu 5: Ta có thể biểu diễn ~135_{10}~ dưới dạng số nhị phân ~\overline{d_7d_6d_5d_4d_3d_2d_1d_0}_2~. Giá trị của ~d_4~ bằng

A. 0

B. 1

C. 2

D. 3

Câu 6: Cần ít nhất bao nhiêu byte để biểu diễn giá trị của ~2^8~ trong máy tính

A. 1

B. 2

C. 3

D. 4

Câu 7: Kiểu dữ liệu unsigned long long trong C++ dùng để biểu diễn các số nguyên không âm và tiêu tốn ~8~ byte trong bộ nhớ. Số lớn nhất mà kiểu dữ liệu này có thể biểu diễn được là số nào sau đây, biết rằng toàn bộ ~8~ byte đó được dùng để biểu diễn số trong hệ nhị phân.

A. ~2^{64}~

B. ~2^{64} - 1~

C. ~2^{63}~

D. ~2^{63} - 1~

Câu 8: Cho tập hợp ~A = \{0,1,2,3,4\}~. Người ta biểu diễn một tập con của ~A~ bằng dãy nhị phân ~\overline{d_4d_3d_2d_1d_0}_2~, trong đó với mỗi số nguyên ~i~ từ ~0~ đến ~4~, nếu ~d_i~ bằng ~0~ thì ~i~ thuộc tập con và ~d_i~ bằng ~1~ thì ~i~ không thuộc tập con. Tập ~B~ là tập con của tập ~A~ và được biểu diễn bằng dãy ~10110_2~. Số phần tử của tập ~B~ là

A. 0

B. 1

C. 2

D. 3

Câu 9: Biểu thức nào sau đây cho biết bóng đèn ở mạch điện dưới đây sáng. Biết rằng với ~i~ nguyên từ ~1~ đến ~3~, ~K_i~ đúng khi và chỉ khi khóa ~K_i~ ở trạng thái đóng.

A. ~K_1~ AND ~K_2~ AND ~K_3~

B. ~K_1~ OR (~K_2~ AND ~K_3~)

C. ~K_1~ AND (~K_2~ OR ~K_3~)

D. ~K_1~ OR ~K_2~ OR ~K_3~

Câu 10: Biểu thức logic nào sau đây cho biết điểm ~(x;y)~ thuộc vùng nằm giữa hai đường thẳng ~y = 2x + 5~ và ~y = 3x + 4~ được tô đậm dưới đây:

A. ~(2x+5 \leq y \leq 3x+4)~ OR ~(3x+4 \leq y \leq 2x+5)~

B. NOT ~(2x+5 \leq y \leq 3x+4)~ AND NOT ~(3x+4 \leq y \leq 2x+5)~

C. ~(y \geq 2x+5)~ AND ~(y \geq 3x+4)~

D. ~(y \leq 2x+5)~ AND ~(y \leq 3x+4)~

Câu 11: 63 OR 15 AND 29 bằng bao nhiêu?

A. 28

B. 30

C. 31

D. 29

Câu 12: Số nghiệm nguyên của phương trình ~x~ AND 26 OR 5 = 23 thuộc ~[0; 2^5)~ là

A. 2

B. 4

C. 8

D. 16

Câu 13: Nghiệm nguyên lớn nhất của phương trình ~x~ AND 26 OR 5 = 23 thuộc ~[0; 20)~ là

A. 17

B. 16

C. 19

D. 18

Câu 14: Biết mã ASCII của A là 65 và a là 97. Mã ASCII của chữ cái tiếng Anh in thường tương ứng với chữ cái in hoa có mã ASCII ~k~ bằng.

A. ~k~ OR ~2^5~

B. ~k~ AND NOT ~2^5~

C. ~k~ OR ~(2^5-1)~

D. ~k~ AND NOT ~(2^5-1)~

Câu 15: Biết mã ASCII của A là 65 và a là 97. Mã ASCII của chữ cái tiếng Anh in hoa tương ứng với chữ cái in thường có mã ASCII ~k~ bằng.

A. ~k~ OR ~2^5~

B. ~k~ AND NOT ~2^5~

C. ~k~ OR ~(2^5-1)~

D. ~k~ AND NOT ~(2^5-1)~

Note này được dựa trên Concrete Mathematics, 3.3, và bài viết về bài toán Josephus trên CP-Algorithms .

Xét bài toán Josephus dạng tổng quát.

Cho ~n~ người đứng thành một vòng tròn, mỗi người được đánh số từ 1 đến ~n~. Bắt đầu từ vị trí số 1, mỗi người sẽ đếm lần lượt 1, 2, ..., ~k~, người đếm ~k~ sẽ bị loại khỏi vòng tròn, và mọi người tiếp tục đếm lại từ ~1~ cho đến khi chỉ còn lại một người. Hỏi người đánh số nào là người ở lại vòng tròn cuối cùng.

Một ý tưởng để giải quyết bài toán này là khi mỗi người đếm mà không bị loại, ta gán số thứ tự mới bằng số thứ tự lớn nhất hiện tại cộng ~1~. Ví dụ minh họa một vài lượt đếm với ~n = 10~, ~k = 3~

• Người ~1~ đếm ~1~ và không bị loại, ta gán số thứ tự mới ~11~ (kí hiệu ~1 \rightarrow 11~)
• Người ~2~ đếm ~2~ và không bị loại, ta gán số thứ tự mới ~12~ (kí hiệu ~2 \rightarrow 12~)
• Người ~3~ đếm ~3~ và bị loại, ta không gán số thứ tự mới (kí hiệu ~3 \rightarrow \emptyset~)
• ~4 \rightarrow 13~
• ~5 \rightarrow 14~
• ~6 \rightarrow \emptyset~
• ...

Ta thấy người bị loại sẽ có số thứ tự lần lượt là ~k~, ~2k~, .... Do cuối cùng cả ~n~ người bị loại, người bị loại cuối cùng sẽ có số thứ tự ~nk~.

Để các công thức tính toán sau này, ta sẽ đánh số lại mọi người theo thứ tự từ ~nk~ về ~1~. Ví dụ, khi ~n = 10~, ~k = 3~ thì ban đầu ~n~ người sẽ có số thứ tự lần lượt là ~30, 29, 28, ..., 21~. Một vài lượt chơi ban đầu như sau:

• ~30 \rightarrow 20~
• ~29 \rightarrow 19~
• ~28 \rightarrow \emptyset~
• ~27 \rightarrow 18~
• ~26 \rightarrow 17~
• ~25 \rightarrow \emptyset~

Người ở lại vòng tròn cuối cùng sẽ có số thứ tự cuối cùng là ~1~. Giờ ta chỉ cần tìm lại số thứ tự ban đầu của người này là giải quyết được bài toán.

Giả sử ~x~ là số thứ tự của một người nào đó trong vòng tròn. Khi tìm số thứ tự trước đó của người ~x~, kí hiệu là ~x'~, ta sẽ cần xử lí hai trường hợp:

• Nếu ~x \geq nk - n + 1~ thì ~x~ là số thứ tự ban đầu, vì thế sẽ không có số thứ tự trước đó.
• Trường hợp ~x < nk - n + 1~, ta có thể chia các số từ ~nk~ đến ~1~ thành những nhóm ~k~ số liên tiếp nhau (gọi tắt là nhóm ~k~, minh họa bằng cách đóng khung chữ nhật), và chia các số từ ~nk - n~ đến ~1~ thành những nhóm ~k-1~ số liên tiếp nhau (gọi tắt là nhóm ~k-1~, minh họa bằng cách khoanh tròn).

Đánh số các nhóm theo thứ tự từ ~0~. Trong nội bộ mỗi nhóm, ta cũng đánh số thứ tự từ ~0~.

Với mọi ~x < nk - n + 1~, nếu ~x~ là số thứ ~i~ nhóm ~k-1~ thứ ~j~ thì ~x'~ là số thứ ~i~ của nhóm ~k~ thứ ~j~ (dễ thấy điều này ở một số số ~x~ ngay sau số ~nk - n + 1~, cỏn các số sau nữa thì ta có thể chứng minh bằng quy nạp được). Vậy ta chỉ cần tìm ~i~ và ~j~ là ra ~x'~.

Ta tính được:

~x~ thuộc nhóm ~k-1~ thứ ~\lfloor \frac{nk - n - x}{k-1} \rfloor~

Số thứ tự của ~x~ trong nhóm ~k-1~ là ~nk - n - x - (k-1)\lfloor \frac{nk - n - x}{k-1} \rfloor~

~x'~ sẽ là số thứ ~nk - n - x - (k-1)\lfloor \frac{nk - n - x}{k-1} \rfloor~ của nhóm ~k~ thứ ~\lfloor \frac{nk - n - x}{k-1} \rfloor~, vậy

~x' = nk - k\lfloor \frac{nk - n - x}{k-1} \rfloor - (nk - n - x - (k-1)\lfloor \frac{nk - n - x}{k-1} \rfloor)~

~x' = n + x - \lfloor \frac{n(k - 1) - x}{k-1} \rfloor~

~x' = n + x - \lfloor n - \frac{x}{k-1} \rfloor~

Vận dụng tính chất ~\lfloor x + y \rfloor = x + \lfloor y \rfloor~ khi ~x \in \mathbb{Z}~ để đưa ~n~ ra ngoài hàm làm tròn xuống, ta có:

~x' = x - \lfloor -\frac{x}{k-1} \rfloor~

Vận dụng tiếp tính chất ~\lfloor -x \rfloor = -\lceil x \rceil~, ta có:

~x' = x + \lceil \frac{x}{k-1} \rceil~

~x' = \lceil \frac{x(k-1)}{k-1} + \frac{x}{k-1} \rceil~

~\boxed{x' = \lceil \frac{k}{k-1} x \rceil}~

Từ hai trường hợp trên, ta ra được thuật toán sau để tìm số thứ tự của người ở lại vòng tròn cuối cùng

Đọc n, k
Gán x = 1
While x < nk - k + 1:
    x = ceil(k/(k-1) * x)

# x là số thứ tự ban đầu nếu ta đánh số ngược, ta cần tìm số thứ tự ban đầu khi đánh số thuận
Gán x = nk + 1 - x
In ra x

Thuật toán trên có độ phức tạp ~O(\log_{\frac{k}{k-1}}(nk))~. Với ~k = 10^5, n = 10^{18}~, thuật toán này sẽ chỉ tốn khoảng ~6 \times 10^7~ phép tính và hoàn toàn có thể chạy dưới ~1~ giây, trong khi thuật toán duyệt thông thường sẽ mất đến ~O(nk)~ phép tính (hay khoảng ~10^{17}~ phép tính)

Vậy là ta đã giải quyết được bài toán trong trường hợp ~n~ lớn, ~k~ khá lớn. Vậy nếu như ta phải giải bài toán trong trường hợp ~k~ lớn, ~n~ khá lớn thì ta làm thế nào?

Gọi ~J_{n,k}~ là người ở lại vòng tròn cuối cùng nếu ta đánh số các người chơi từ ~0~ đến ~n-1~. Ta mô phỏng lại trò chơi bằng máy tính với một số giá trị ~n, k~ nhỏ rồi lập bảng. Ta sẽ thấy được quy luật

~J_{n, k} = (J_{n-1, k} + k) \text{ mod } n~

Từ công thức này, ta sẽ tính được ~J_{n,k}~ với độ phức tạp ~O(n)~, không phụ thuộc vào ~k~

Rất tiếc là ở thời điểm hiện tại, các nhà khoa học máy tính vẫn chưa tìm ra được cách giải quyết "dưới 1 giây" của bài toán này trong trường hợp cả ~n~ và ~k~ đều rất lớn.

Dựa trên Concrete Mathematics, 3.2

1. Đếm số giá trị nguyên trong một tập liên tục

Ở trong đề thi Đại học, ta thường gặp các câu hỏi tính số giá trị nguyên của ~m~ sao cho một phương trình nào đó có nghiệm. Khi giải các câu hỏi dạng này, ta thường ra được kết quả là ~m~ thuộc một tập liên tục (đoạn, khoảng, nửa đoạn) đó với các đầu mút là số nguyên hay số thực. Vậy, ta làm thế nào để đếm được số giá trị nguyên với rủi ro bị sai sót là thấp nhất có thể.

Giả sử ~m \in (a, b]~. Khi đó ~a < m \leq b~.

Theo các bất đẳng thức ta đã học ở bài trước, bất đẳng thức này tương đương với ~\lfloor a \rfloor < m \leq \lfloor b \rfloor~.

Do ~\lfloor \alpha \rfloor~ là số nguyên nên bất đẳng thức này tương đương với ~\lfloor a \rfloor + 1 \leq m \leq \lfloor b \rfloor~

Số số nguyên ~m~ thỏa mãn bất đẳng thức này là ~\lfloor b \rfloor - (\lfloor a \rfloor + 1) + 1 = \lfloor b \rfloor - \lfloor a \rfloor~

Làm tương tự như trên, ta sẽ có những công thức sau để đếm số số nguyên trong một tập liên tục:

• ~[a,b]~: Số giá trị nguyên là ~\lfloor b \rfloor - \lceil a \rceil + 1~
• ~[a,b)~: Số giá trị nguyên là ~\lceil b \rceil - \lceil a \rceil~
• ~(a,b]~: Số giá trị nguyên là ~\lfloor b \rfloor - \lfloor a \rfloor~
• ~(a,b)~: Số giá trị nguyên là ~\lceil b \rceil - \lfloor a \rfloor - 1~

Lưu ý là công thức chỉ đúng khi ~a \leq b~, và khi ta dùng công thức cho ~(a,b)~ thì ~a < b~. Trong trường hợp không thể áp dụng được công thức, ta coi số số nguyên bằng ~0~.

2. Tổng chứa hàm làm tròn

Trong casino có một trò chơi như sau:

• Nhà cái bốc ngẫu nhiên một số nguyên từ 1 đến 1000. Gọi số này là ~n~.
• Nếu ~n~ chia hết cho ~\lfloor \sqrt[3]{n} \rfloor~ thì nhà cái sẽ phải trả thưởng ~5~ nghìn đồng cho người chơi, còn nếu không thì người chơi sẽ phải trả nhà cái ~1~ nghìn đồng

Hãy tính xem người chơi có thể kì vọng có lãi nếu chơi trò chơi này rất nhiều lần hay không?

Gọi số số nguyên ~n~ thỏa mãn ~1 \leq n \leq 1000~ và ~n~ chia hết cho ~\lfloor \sqrt[3]{n} \rfloor~ là ~W~. Ta sẽ tính lợi nhuận kì vọng ~E~ của người chơi theo ~W~.

Ta có tổng cộng ~1000~ trường hợp của ~n~.

Có ~W~ trường hợp nhà cái sẽ phải trả thưởng ~5~ nghìn đồng.

Có ~1000-W~ trường hợp người chơi mất ~1~ nghìn đồng, tức được ~-1~ nghìn đồng.

Vậy lợi nhuận kì vọng của người chơi là ~E = \frac{5W - (1000 - W)}{1000} = \frac{6W - 1000}{1000}~

Người chơi có lãi khi ~E > 0 \Leftrightarrow 6W - 1000 > 0 \Leftrightarrow W > \frac{1000}{6} \Leftrightarrow W \geq 167~

Bây giờ ta sẽ tính ~W~. Sử dụng kí pháp Iverson, ta có:

~W = \sum_{n} [1 \leq n \leq 1000][n \text{ chia hết cho } \lfloor \sqrt[3]{n} \rfloor]~

Do ~n \text{ chia hết cho } \lfloor \sqrt[3]{n} \rfloor \Leftrightarrow \exists m \in \mathbb{Z}: n = m\lfloor \sqrt[3]{n} \rfloor~ nên

~W = \sum_{n, m} [1 \leq n \leq 1000][n = m\lfloor \sqrt[3]{n} \rfloor]~

~W = \sum_{n, m, k} [1 \leq n \leq 1000][k = \lfloor \sqrt[3]{n} \rfloor][n = mk]~

~W = \sum_{n, m, k} [1 \leq n \leq 1000][k \leq \sqrt[3]{n} < k+1][n = mk]~

~W = \sum_{n, m, k} [1 \leq n < 1001][k^3 \leq n < (k+1)^3][n = mk]~

~W = \sum_{n, m, k} [\max(1,k^3) \leq n < \min(1001, (k+1)^3)][n = mk]~

Giờ ta sẽ loại bỏ một biến. Để tránh vòng luẩn quẩn (sau khi biến đổi ta có lại biểu thức ban đầu), ta sẽ loại bỏ biến ~n~. Khi đó:

~W = \sum_{m, k} [\max(1,k^3) \leq mk < \min(1001, (k+1)^3)]~

Để đi tiếp, ta tìm cách tách các trường hợp của ~\max, \min~

Xét ~\max(1, k^3)~. Ta thấy ~1 \leq k^3 \Leftrightarrow 1 \leq k~. Vì thế nếu ~k = 0~, ~\max(1, k^3) = 1~, nếu ~k \geq 1~, ~\max(1, k^3) = k^3~

Xét ~\min(1001, (k+1)^3)~. Ta thấy ~1001 \leq (k+1)^3 \Leftrightarrow \sqrt[3]{1001} \leq k+1 \Leftrightarrow \lceil \sqrt[3]{1001} \rceil \leq k+1 \Leftrightarrow 11 \leq k+1 \Leftrightarrow k \geq 10~. Do đó nếu ~k \geq 10~ thì ~\min(1001, (k+1)^3) = 1001~, còn nếu ~k < 10~ thì ~\min(1001, (k+1)^3) = (k+1)^3~

Vậy ta xét ~k~ trong các trường hợp ~k = 0~, ~1 \leq k < 10~, và ~k \geq 10~

~W = \sum_m [1 \leq 0 < 1] + \sum_{m, k} [1 \leq k < 10][k^3 \leq mk < (k+1)^3] + \sum_{m, k} [k \geq 10][k^3 \leq mk < 1001]~

~W = 0 + \sum_{m, k} [1 \leq k < 10][k^2 \leq m < \lceil \frac{(k+1)^3}{k} \rceil] + \sum_{m, k} [k \geq 10][k^2 \leq m < \frac{1001}{k}]~

~W = \sum_{k} [1 \leq k < 10] \sum_m [m \in [k^2,\frac{(k+1)^3}{k})] + \sum_{k} [k \geq 10] \sum_m [m \in [k^2, \frac{1001}{k})]~

Giờ ta có thể áp dụng công thức đếm số số nguyên trong một tập liên tục để tính ~\sum_m [m \in [k^2,\frac{(k+1)^3}{k})]~ và ~\sum_m [m \in [k^2, \frac{1001}{k})]~, tuy nhiên trước đó ta phải kiểm tra điều kiện áp dụng công thức.

Dễ thấy ~k^2 \leq \frac{(k+1)^3}{k}~ khi ~1 \leq k < 10~, nên ta luôn có thể áp dụng được công thức cho tổng đầu tiên.

Với tổng thứ hai, ~k^2 \leq \frac{1001}{k} \Leftrightarrow k^3 \leq 1001 \Leftrightarrow k \leq \lfloor \sqrt[3]{1001} \rfloor \Leftrightarrow k \leq 10~. Kết hợp với ~k \geq 10~, ta thấy ta chỉ áp dụng được công thức khi ~k = 10~

Vậy

~W = \sum_{1 \leq k < 10} (\lceil \frac{(k+1)^3}{k} \rceil - \lceil k^2 \rceil) + \lceil \frac{1001}{10} \rceil - \lceil 10^2 \rceil~

~W = \sum_{1 \leq k < 10} (\lceil \frac{(k+1)^3}{k} - k^2 \rceil) + 101 - 100~

~W = \sum_{1 \leq k < 10} (\lceil 3k + 3 + \frac{1}{k} \rceil) + 1~

~W = \sum_{1 \leq k < 10} (3k + 3 + \lceil \frac{1}{k} \rceil) + 1~

Dễ thấy ~\forall k > 0: \lceil \frac{1}{k} \rceil = 1~ nên

~W = \sum_{1 \leq k < 10} (3k + 4) + 1~

~W = \frac{(7 + 31) \cdot 9}{2} + 1~ (dãy ~(3k+1)_{k=1}^9~ là dãy cấp số cộng có công thức tổng bằng (số đầu cộng số cuối) nhân số số hạng rồi chia đôi)

~\boxed{W = 172}~

Do ~W = 172 > 167~ nên người chơi sẽ có lãi khi chơi trò chơi này.

Bây giờ giả sử nhà cái bốc một số nguyên từ ~1~ đến ~N~ (ví dụ ~N = 10^9~). Liệu nhà cái và người chơi có tính trước được số trường hợp nhà cái phải trả thưởng cho người chơi để từ đó tính được nhà cái hay người chơi sẽ có lợi hay không?

Để giải đáp câu hỏi này, ta cần tổng quát hóa công thức trên bằng cách thay ~1000~ thành một số nguyên dương ~N~ bất kì. Khi đó,

~W = \sum_{m, k} [\max(1,k^3) \leq mk < \min(N+1, (k+1)^3)]~ (vì ở các bước trước ta không động đến hằng số ~1000~)

Xét ~\max(1,k^3)~. Ta thấy nếu ~k = 0~ thì ~\max(1, k^3) = 1~, nếu ~k \geq 1~ thì ~\max(1,k^3) = k^3~

Xét ~\min(N+1, (k+1)^3)~.

~N+1 < (k+1)^3 \Leftrightarrow \sqrt[3]{N+1} < k+1 \Leftrightarrow \lfloor \sqrt[3]{N+1} \rfloor - 1 < k~.

Vậy nếu ~k > \lfloor \sqrt[3]{N+1} \rfloor - 1~ thì ~\min(N+1, (k+1)^3) = N+1~, còn nếu ~k \leq \lfloor \sqrt[3]{N+1} \rfloor - 1~ thì ~\min(N+1, (k+1)^3) = (k+1)^3~.

Để đỡ lằng nhằng, ta giả sử ~\lfloor \sqrt[3]{N+1} \rfloor - 1 \geq 1 \Leftrightarrow \sqrt[3]{N+1} \geq 2 \Leftrightarrow N+1 \geq 8 \Leftrightarrow N \geq 7~. Nếu ~N < 7~, ta tính tay thay vì sử dụng công thức tổng quát.

Khi đó

~W = \sum_{m} [1 \leq 0 < 1] + \sum_{m,k} [1 \leq k \leq \lfloor \sqrt[3]{N+1} \rfloor - 1][k^3 \leq mk < (k+1)^3] + \sum_{m,k} [k \geq \lfloor \sqrt[3]{N+1} \rfloor][k^3 \leq km < N+1]~

~W = \sum_{k} [1 \leq k \leq \lfloor \sqrt[3]{N+1} \rfloor - 1] \sum_m [m \in [k^2, \frac{(k+1)^3}{2})] + \sum_{k} [k \geq \lfloor \sqrt[3]{N+1} \rfloor] \sum_m [m \in [k^2, \frac{N+1}{k})]~

Kiểm tra điều kiện sử dụng công thức đếm số số nguyên trong một tập liên tục. Ta thấy ta luôn có thể sử dụng được công thức cho tổng đầu tiên. Với tổng thứ hai:

~k^2 \leq \frac{N+1}{k} \Leftrightarrow k^3 \leq N+1 \Leftrightarrow k \leq \sqrt[3]{N+1}~

nên ta chỉ sử dụng được công thức khi ~k=\lfloor \sqrt[3]{N+1} \rfloor~

Để ngắn gọn, đặt ~K = \lfloor \sqrt[3]{N+1} \rfloor~

Khi đó

~W = \sum_{k=1}^{K-1} (\lceil \frac{(k+1)^3}{2} \rceil - \lceil k^2 \rceil) + \lceil \frac{N+1}{K} \rceil - \lceil K^2 \rceil~

~W = \sum_{k=1}^{K-1} (3k+4) + \lceil \frac{N+1}{K} \rceil - K^2~

~\boxed{W = \frac{(8 + 3K)(K-1)}{2} + \lceil \frac{N+1}{K} \rceil - K^2}~

Với công thức tổng quát này, ta có thể tính được ~W~ trong ~O(1)~ hoặc ~O(\log N)~ thay vì ~O(N)~.

Dựa trên Concrete Mathematics, 3.1

1. Làm tròn lên, làm tròn xuống

Ta định nghĩa các kí hiệu sau:

~\lfloor x \rfloor~ - số nguyên lớn nhất không vượt quá ~x~. Kí hiệu này đọc là "phần nguyên của ~x~" hoặc "~x~ làm tròn xuống"

Ví dụ: ~\lfloor 1.2 \rfloor = 1, \lfloor -0.8 \rfloor = -1~.

Lưu ý rằng với số âm thì các ngôn ngữ lập trình khác nhau có thể định nghĩa "làm tròn xuống khác nhau", ta sẽ thống nhất sử dụng định nghĩa trên cho dễ biến đổi.

~\lceil x \rceil~ - số nguyên nhỏ nhất không nhỏ hơn ~x~. Kí hiệu này đọc là "~x~ làm tròn lên"

Ví dụ: ~\lceil 1.2 \rceil = 2, \lceil -0.8 \rceil = 0~

Để dễ nhìn tính chất của hai hàm làm tròn, ta vẽ đồ thị các hàm số ~y = \lfloor x \rfloor, y = \lceil x \rceil~ và ~y = x~ trên cùng một hệ trục tọa độ

Dễ thấy:

~x = \lfloor x \rfloor \Leftrightarrow x \in \mathbb{Z} \Leftrightarrow x = \lceil x \rceil~

~\lceil x \rceil - \lfloor x \rfloor = [x \in \mathbb{Z}]~

~x - 1 < \lfloor x \rfloor \leq x \leq \lceil x \rceil < x + 1~

Ta thấy khi lấy đối xứng đồ thị hàm số ~y = \lfloor x \rfloor~ thì ta được ~y = \lceil x \rceil~, vì thế nên:

~\lfloor -x \rfloor = - \lceil x \rceil~ và ~\lceil -x \rceil = - \lfloor x \rfloor~

Ngoài ra

~\lfloor x \rfloor = n \Leftrightarrow n \leq x < n+1 \Leftrightarrow x-1 < n \leq x-1~

~\lceil x \rceil = n \Leftrightarrow n-1 < x \leq n \Leftrightarrow x \leq n < x+1~

Ta có thể cộng một số nguyên ở trong hay ở ngoài hàm làm tròn lên lẫn làm tròn xuống

~\lfloor x + n \rfloor = \lfloor x \rfloor + n~ với ~n \in \mathbb{Z}~

~\lceil x + n \rceil = \lceil x \rceil + n~ với ~n \in \mathbb{Z}~

Lưu ý điều này không đúng với phép nhân (~\lfloor nx \rfloor \ne n \lfloor x \rfloor~ sai khi ~n = 2~ và ~x = \frac{1}{2}~)

Với ~n~ là số nguyên, ta cũng dễ dàng chứng minh được các phép biến đổi tương đương sau:

~x < n \Leftrightarrow \lfloor x \rfloor < n~

~n < x \Leftrightarrow n < \lceil x \rceil~

~x \leq n \Leftrightarrow \lfloor x \rfloor \leq n~

~n \leq x \Leftrightarrow n \leq \lceil x \rceil~

Người ta còn định nghĩa ~\{x\} = x - \lfloor x \rfloor~ (~\{x\}~ được đọc là "phần thập phân của ~x~"). Nếu một số thực ~x = n + \theta~ với ~n, \theta~ thỏa mãn ~n~ nguyên và ~0 \leq \theta < 1~ thì ta biết được ~n = \lfloor x \rfloor~ và ~\theta = \{x\}~

2. Bài tập ứng dụng

Ví dụ 1:

Sử dụng khái niệm phần thập phân và tính chất ~\lfloor x + n \rfloor = \lfloor x \rfloor + n~ với ~n \in \mathbb{Z}~, ta có thể chứng minh được tính chất sau:

~\lfloor x + y \rfloor~ chỉ có thể là ~\lfloor x \rfloor + \lfloor y \rfloor~ hoặc ~\lfloor x \rfloor + \lfloor y \rfloor + 1~

Ta có:

~\lfloor x + y \rfloor = \lfloor \lfloor x \rfloor + \{x\} + \lfloor y \rfloor + \{y\} \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + \lfloor \{x\} + \{y\} \rfloor~

Do ~0 \leq \{x\}, \{y\} < 1~ nên ~0 \leq \{x\} + \{y\} < 2~, và vì thế nên ~\lfloor \{x\} + \{y\} \rfloor~ chỉ có thể là ~0~ hoặc ~1~.

Nếu ~\lfloor \{x\} + \{y\} \rfloor = 0~, ~\lfloor x + y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor~

Nếu ~\lfloor \{x\} + \{y\} \rfloor = 1~, ~\lfloor x + y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + 1~

Ví dụ 2:

Tính ~\lfloor \lg 35 \rfloor~ (do độ phổ biến của logarithm cơ số 2 trong Tin học, ta kí hiệu ~\log_2~ bằng ~\lg~)

Ta có:

~2^5 \leq 35 < 2^6 \Rightarrow 5 \leq \lg 35 < 6 \Rightarrow \lfloor \lg 35 \rfloor = 5~

Ví dụ 3:

Cho hàm ~f~ liên tục và đồng biến thỏa mãn ~f(x) \in \mathbb{Z} \Rightarrow x \in \mathbb{Z}~.

Khi đó, ~\lfloor f(x) \rfloor = \lfloor f(\lfloor x \rfloor) \rfloor~.

Tương tự, ta cũng có ~\lceil f(x) \rceil = \lceil f(\lceil x \rceil) \rceil~

Chứng minh:

Đặt ~m = \lfloor f(\lfloor x \rfloor) \rfloor~.

Khi đó ~m \leq f(\lfloor x \rfloor) < m+1~ (phá dấu làm tròn xuống ở ngoài bằng định nghĩa)

Do ~x \geq \lfloor x \rfloor~ và ~f~ đồng biến, ta có ~f(x) \geq f(\lfloor x \rfloor) \Rightarrow f(x) \geq m~

Để chứng minh ~\lfloor f(x) \rfloor = m~, ta giờ chỉ cần chứng minh ~f(x) < m+1~. Ta sẽ chứng minh điều này bằng phản chứng.

Giả dụ ~f(x) \geq m+1~.

Khi đó do ~\begin{cases} f(\lfloor x \rfloor) < m+1 \leq f(x) \\ f \text{ liên tục} \end{cases}~, theo định lí giá trị trung gian, ta sẽ tìm được ~c~ thỏa mãn ~f(c) = m+1~ và ~\lfloor x \rfloor < c \leq x~

Theo giả thiết ~f(x) \in \mathbb{Z} \Rightarrow x \in \mathbb{Z}~, do ~f(c) = m+1 \in \mathbb{Z}~, ~c \in \mathbb{Z}~.

Như vậy, ta tìm được số nguyên ~c~ nằm giữa ~\lfloor x \rfloor~ và ~x~, nhưng lại không bằng ~\lfloor x \rfloor~. Điều này vô lí.

Do đó giả dụ ban đầu sai, nói cách khác, ~f(x) < m+1~ đúng.

Kết hợp ~\begin{cases} m \leq f(x) \\ f(x) < m+1 \end{cases}~, ta có ~\lfloor f(x) \rfloor = m \Rightarrow \lfloor f(x) \rfloor = \lfloor f(\lfloor x \rfloor) \rfloor~. Đây là điều phải chứng minh.

Hệ quả của ví dụ 3:

~\lfloor \sqrt{x} \rfloor = \lfloor \sqrt{\lfloor x \rfloor} \rfloor~

~\lfloor \frac{x + m}{n} \rfloor = \lfloor \frac{\lfloor x \rfloor + m}{n} \rfloor~ (~n~ dương)

Các công thức tương tự với hàm làm tròn lên cũng đúng

Ví dụ 4: Giải phương trình ẩn ~x~ sau: ~\lceil \sqrt{\lfloor x \rfloor} \rceil = \lceil \sqrt{x} \rceil~

Xét các trường hợp sau:

Trường hợp 1: ~\sqrt{x}~ nguyên, ~\sqrt{\lfloor x \rfloor}~ nguyên. Khi đó phương trình luôn đúng. Kết hợp điều kiện, ta được ~x = m^2~ với ~m \in \mathbb{Z}~

Trường hợp 2: ~\sqrt{x}~ nguyên, ~\sqrt{\lfloor x \rfloor}~ không nguyên. Trường hợp này không thể xảy ra. ~\sqrt{x}~ nguyên ~\Rightarrow x~ nguyên ~\Rightarrow \lfloor x \rfloor = x \Rightarrow \sqrt{\lfloor x \rfloor} = \sqrt{x}~ nguyên.

Trường hợp 3: ~\sqrt{x}~ không nguyên, ~\sqrt{\lfloor x \rfloor}~ nguyên. Khi đó, phương trình trở thành

~\sqrt{\lfloor x \rfloor} = \lfloor \sqrt{x} \rfloor + 1 \Leftrightarrow \sqrt{\lfloor x \rfloor} = \lfloor \sqrt{\lfloor x \rfloor} \rfloor + 1 > (\sqrt{\lfloor x \rfloor} - 1) + 1 \Leftrightarrow \sqrt{\lfloor x \rfloor} > \sqrt{\lfloor x \rfloor}~ (vô nghiệm)

Trường hợp 4: ~\sqrt{x}~ không nguyên, ~\sqrt{\lfloor x \rfloor}~ không nguyên. Khi đó, phương trình trở thành

~\lfloor \sqrt{\lfloor x \rfloor} \rfloor + 1 = \lfloor \sqrt{x} \rfloor + 1 \Leftrightarrow \lfloor \sqrt{\lfloor x \rfloor} \rfloor = \lfloor \sqrt{x} \rfloor~ (luôn đúng)

Kết hợp điều kiện, ta được ~\lfloor x \rfloor \ne m^2~ với ~m \in \mathbb{Z}~ (phần nguyên của ~x~ không là số chính phương)

Từ bốn trường hợp trên, ta kết luận tập nghiệm của phương trình ~\lceil \sqrt{\lfloor x \rfloor} \rceil = \lceil \sqrt{x} \rceil~ là

~S = \{m \in \mathbb{Z} | m^2\} \cup \{x \in \mathbb{R} | \forall m \in \mathbb{Z}: \lfloor x \rfloor \ne m^2 \}~

(số ~x~ là nghiệm của phương trình khi và chỉ khi ~x~ là số chính phương hoặc phần nguyên của ~x~ không là số chính phương)

Note được dựa trên Concrete Mathematics, 2.6

Ở lớp 11, 12 các bạn đã được học về các khái niệm "đạo hàm" và "tích phân". Các khái niệm này có những tính chất rất đẹp, giúp chúng ta đơn giản hóa việc tính toán giá trị lớn nhất, nhỏ nhất, diện tích, thể tích, ....

Tương tự, hai khái niệm "sai phân" và "tổng phân" cũng có những tính chất đẹp tương tự "đạo hàm, tích phân" và nhờ thế giúp ta tính tổng một cách đơn giản hơn.

1. Sai phân

Ta đã biết:

~f'(x) = \lim_{h \rightarrow 0} \frac{f(x+h) - f(x)}{h}~

Do khi tính tổng, ~h~ là số nguyên nên khi ~h \rightarrow 0~ thì ~h~ chỉ có thể là ~1~ hoặc ~-1~. Để đơn giản hóa, ta coi ~h=1~ để có định nghĩa sau

~\Delta(f(x)) = f(x+1) - f(x)~

~\Delta(f(x))~ đọc là "sai phân của ~f~ tại điểm ~x~"", hoặc gọn hơn là "sai phân của ~f(x)~"

Ta có tính chất sau của đạo hàm: ~(x^m)' = mx^{m-1}~

Ta sẽ thử tính sai phân của ~x^3~ xem sai phân liệu có thể có tính chất tương tự hay không.

~\Delta(x^3) = (x+1)^3 - x^3 = 3x^2 + 3x + 1~

Kết quả này không đẹp và dễ nhớ như ~(x^3)' = 3x^2~, vì vậy khi làm việc với sai phân, ta cần loại lũy thừa đặc biệt gọi là "lũy thừa giảm" (hay còn gọi là "giai thừa giảm")

~x^{\underline{m}} = x(x-1)(x-2)...(x-m+1)~

Ta thấy đây là tích của ~m~ thừa số giảm dần ~x~, ~x-1~, ..., ~x-m+1~. Kí hiệu ~x^{\underline{m}}~ đọc là "~x~ mũ ~m~ giảm"

Ta thử tính sai phân của ~x^{\underline{m}}~

~\Delta(x^{\underline{m}}) = (x+1)^{\underline{m}} - x^{\underline{m}} = (x+1)x(x-1)(x-2)...(x-m+2) - x(x-1)(x-2)...(x-m+1) = x(x-1)(x-2)...(x-m+2)[(x+1) - (x-m+1)]~

~\Delta(x^{\underline{m}}) = mx(x-1)(x-2)...(x-m+2) = mx^{\underline{m-1}}~

Vậy ta có công thức đẹp và dễ nhớ ~\boxed{\Delta(x^{\underline{m}}) = mx^{\underline{m-1}}}~

Ở trên chúng ta mới định nghĩa lũy thừa giảm với số mũ dương. Ta sẽ định nghĩa lũy thừa giảm cho số mũ không dương như sau để tính chất đóng hộp ở trên đúng.

~x^{\underline{0}} = 1~

~x^{\underline{-m}} = \frac{1}{(x+1)(x+2)(x+3)...(x+m)}~ (~m > 0~)

Sau khi định nghĩa được lũy thừa giảm cho mọi số nguyên, ta giờ có được công thức nhân hai lũy thừa giảm

~\boxed{x^{\underline{n+m}} = x^{\underline{n}}(x-n)^{\underline{m}}}~

Đồng thời, ta cũng có công thức sau (giống công thức khai triển nhị thức Newton)

~(x+y)^{\underline{n}} = \sum_{k=0}^n C_n^k x^{\underline{k}}y^{\underline{n-k}}~

Một tính chất đẹp nữa của đạo hàm là ~(e^x)' = e^x~. Liệu có một hàm ~f(x)~ nào thỏa mãn ~\Delta f(x) = f(x)~ hay không?

Ta có: ~\Delta f(x) = f(x) \Rightarrow f(x+1) - f(x) = f(x) \Rightarrow f(x+1) = 2f(x)~

Dễ thấy ~f(x) = 2^x~ là một hàm thỏa mãn ~f(x+1) = 2f(x)~, và vì thế ~\boxed{\Delta(2^x) = 2^x}~

Việc tính sai phân hàm mũ cũng khá đơn giản

~\Delta(c^x) = c^{x+1} - c^x \Rightarrow \boxed{\Delta(c^x) = (c-1)c^x}~

2. Tổng phân

Ta đã biết:

~\int_a^b f(x) dx = \lim_{n \rightarrow \infty} \sum_{i=1}^{n-1} (x_{i+1} - x_i)f(x_i)~

với ~x_i = a + \frac{i}{n+1}(b-a)~ (tức ~x_0, x_1, ..., x_n, x_{n+1}~ là các điểm trong đoạn ~[a,b]~ cách đều nhau)

(để dễ tưởng tượng và nhớ công thức này, lưu ý ~\sum_{i=1}^{n-1} (x_{i+1} - x_i)f(x_i)~ là tổng diện tích các hình chữ nhật dùng để ước lượng diện tích nằm dưới đồ thị hàm số ~f(x)~)

Ta lấy cảm hứng từ khái niệm tích phân để định nghĩa tổng phân như sau:

~\sum_a^b f(x) \delta x = f(a) + f(a+1) + ... f(b-1) = \sum_{k=a}^{b-1} f(k)~

Lưu ý tổng chỉ chạy từ ~a~ đến ~b-1~ để tổng phân có các tính chất giống tích phân sau:

• ~\sum_a^b f(x) \delta x + \sum_b^c f(x) \delta x = \sum_a^c f(x) \delta x~ (giống ~\int_a^b f(x)dx + \int_b^c f(x)dx = \int_a^c f(x)dx~)
• Nếu ~g(x) = \Delta(f(x))~ thì
  • ~\sum_a^b g(x) \delta x = f(x)]_a^b = f(b) - f(a)~ (giống nếu ~g(x) = f'(x)~ thì ~\int_a^b g(x) dx = f(x)]_a^b~)
  • Ta kí hiệu ~\sum g(x) \delta x = f(x) + C~ (giống nguyên hàm)

Chứng minh tính chất nếu ~g(x) = \Delta(f(x))~ thì ~\sum_a^b g(x) \delta x = f(x)]_a^b = f(b) - f(a)~

Ta có:

~\sum_a^b g(x) \delta x = \sum_{k=a}^{b-1} g(x) = \Delta(f(a)) + \Delta(f(a+1)) + \Delta(f(a+2)) + ... + \Delta(f(b-1))~

~\sum_a^b g(x) \delta x = (f(a+1) - f(a)) + (f(a+2) - f(a+1)) + (f(a+3) - f(a+2)) + ... + (f(b) - f(b-1))~

~\sum_a^b g(x) \delta x = f(b) - f(a)~

Từ các công thức tính sai phân ở trên, ta dễ dàng có được các công thức tính tổng phân sau:

• ~\sum x^{\underline{m}} \delta x = \frac{x^{\underline{m+1}}}{m+1} + C~ (đúng khi ~m \ne -1~)
• ~\sum c^x \delta x = \frac{c^x}{c-1} + C~ (đúng khi ~c \ne 1~). Khi ~c = 1~ thì ~\sum c^x \delta x = \sum 1 \delta x = x + C~

Bây giờ ta cần sửa công thức cho ~\sum x^{\underline{m}} \delta x~ khi ~m = -1~. Ở môn giải tích, ta biết

~\int x^{-1} dx = \ln |x| + C~

Tương tự, ta cũng có

~\sum x^{\underline{-1}} = H_x + C~ với ~H_x = \sum_{1 \leq k \leq x} \frac{1}{k}~

Điều này cho thấy ~H_x~ có nhiều tính chất giống với hàm ~\ln~. Người ta cũng đã chứng minh được ~|H_n - \ln n| < 1~ khi ~n~ đủ lớn.

3. Ứng dụng đơn giản của tổng phân

Xét bài toán tính ~\square_n = \sum_{0 \leq k \leq n} k^2~

Thoại nhìn thì có vẻ như bài toán trên không liên quan gì đến sai phân, tổng phân vì các tính chất ở trên chỉ dành cho lũy thừa giảm chứ không phải lũy thừa bình thường. Tuy nhiên, ta có thể chuyển ~k^2~ bằng tổng các lũy thừa giảm bằng công thức ~k^2 = k^{\underline{2}} + k^{\underline{1}}~

Ta có:

~\sum_{0 \leq k \leq n} k^2 = \sum_0^{n+1} k^2 \delta k = \sum_0^{n-1} (k^{\underline{2}} + k^{\underline{1}}) \delta k~

~\boxed{\sum_{0 \leq k \leq n} k^2 = [\frac{k^{\underline{3}}}{3} + \frac{k^{\underline{2}}}{2}]_0^{n+1}}~

Từ đây ta chỉ việc khai triển là ra một công thức cho ~\square_n~

Tương tự, ta có thể dùng công thức ~k^3 = k^{\underline{3}} + 3k^{\underline{2}} + k^{\underline{1}}~ để tính ~C_n = \sum_{0 \leq k \leq n} k^3~ như sau:

~C_n = \sum_0^{n+1} (k^{\underline{3}} + 3k^{\underline{2}} + k^{\underline{1}}) \delta k~

~C_n = [\frac{k^{\underline{4}}}{4} + k^{\underline{3}} + \frac{k^{\underline{2}}}{2}]_0^{n+1}~

Làm thế nào để ta tìm được các hệ số trong các công thức ~k^2 = k^{\underline{2}} + k^{\underline{1}}~ và ~k^3 = k^{\underline{3}} + 3k^{\underline{3}} + k^{\underline{1}}~. Câu trả lời là ta sử dụng số Sterling loại I (cái này cũng giống việc ta sử dụng số tổ hợp hay tam giác Pascal để tìm hệ số của các số hạng trong khai triển ~(a+b)^n~ vậy).

4. Sai phân của một tích, tổng phân từng phần

Xét sai phân của một tích hai hàm ~u~ và ~v~. Ta sẽ tìm cách tính ~\Delta(uv)~ từ ~u, v, \Delta(u), \Delta(v)~

~\Delta(uv) = u(x+1)v(x+1) - u(x)v(x) = u(x+1)v(x+1) + u(x+1)v(x) - u(x+1)v(x) - u(x)v(x)~

(việc cộng trừ ~u(x+1)v(x)~ đóng vai trò làm cầu nối giữa hai số hạng)

~\Delta(uv) = u(x+1)[v(x+1) - v(x)] + v(x)[u(x+1) - u(x)]~

~\Delta(uv) = u(x+1)\Delta(v) + v(x)\Delta(u)~

Để công thức này đẹp hơn, ta định nghĩa ~Eu(x) = u(x+1)~ (~E~ là viết tắt của từ "Extra" (thêm) trong tiếng Anh), ta có thể viết gọn công thức này lại như sau:

~\boxed{\Delta(uv) = Eu\Delta(v) + v\Delta(u)}~

Trong sách, công thức này là ~\boxed{\Delta(uv) = u\Delta(v) + Ev\Delta(u)}~. Mặc dù hai công thức này không đối xứng nhưng ta có thể chứng minh chúng bằng nhau.

Ở môn giải tích, công thức tính đạo hàm của một tích giúp ta có được công thức tính tích phân từng phần. Tương tự, ta cũng có công thức tính tổng phân từng phần như sau:

~\sum u\Delta(v) = uv - \sum Ev\Delta(u)~

Giống như công thức tính tích phân từng phần, ta thường sử dụng được công thức tính tổng phân từng phần nếu trong biểu thức cần tính, có một phần tính sai phân dễ và một phần tính tổng phân dễ.

Ví dụ 1: Tính ~\sum_{0 \leq k \leq n} k2^k~

Đầu tiên, ta tính ~\sum x2^x \delta x~

Đặt ~u(x) = x \Rightarrow \Delta(u) = 1~, ~\Delta(v) = 2^x \Rightarrow v = 2^x \Rightarrow Ev = 2^{x+1}~

Khi đó: ~\sum x2^x \delta x = x2^x - \sum 2^{x+1} \delta x = x2^x + 2^{x+1} + C~

vì thế mà ~\sum_{0 \leq k \leq n} k2^k = \sum_0^{n+1} x2^x \delta x = [x2^x + 2^{x+1}]_0^{n+1}~

Ví dụ 2: Tính ~\sum_0^n H_x \delta x~

Ta thấy ~H_x~ là một phần dễ tính sai phân, vì thế nên ta đặt

~u(x) = H_x \Rightarrow \Delta(u) = x^{\underline{-1}}~

~\Delta(v) = 1 \Rightarrow v = x^{\underline{1}} = x\Rightarrow Ev = (x+1)^{\underline{1}}~

Ta có: ~\sum H_x \delta x = xH_x - \sum (x+1)^{\underline{1}}x^{\underline{-1}} \delta x~

~\sum H_x \delta x = xH_x - \sum 1 \delta x~

~\sum H_x \delta x = xH_x - x + C~

Từ đó dễ dàng tính được ~\boxed{\sum_0^n H_x \delta x = nH_n - n}~

Ví dụ 3: Tính ~\sum_0^n xH_x \delta x~

Đặt:

~u(x) = H_x \Rightarrow \Delta(u) = x^{\underline{-1}}~

~\Delta(v) = x \Rightarrow v = \frac{x^{\underline{2}}}{2} \Rightarrow Ev = \frac{(x+1)^{\underline{2}}}{2}~

Ta có:

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \sum \frac{(x+1)^{\underline{2}}x^{\underline{-1}}}{2} \delta x~

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \frac{1}{2} \sum x \delta x~

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \frac{x^{\underline{2}}}{4} + C~

Từ đó dễ dàng tính được ~\boxed{\sum_0^n xH_x \delta x = \frac{n^{\underline{2}}}{2}H_n - \frac{n^{\underline{2}}}{4}}~

5. Tổng hợp kiến thức

~\Delta(x^{\underline{m}}) = mx^{\underline{m-1}} \Rightarrow \sum x^{\underline{m}} \delta x = \frac{x^{\underline{m+1}}}{m+1} + C~

(Đặc biệt: ~\Delta(H_x) = x^{\underline{-1}} \Rightarrow \sum x^{\underline{-1}} \delta x = H_x + C~)

~\Delta(c^x) = (c-1)c^x \Rightarrow \sum c^x \delta x = \frac{c^x}{c-1} + C~

(Đặc biệt: ~\Delta(2^x) = 2^x \Rightarrow \sum 2^x \delta x = 2^x + C~)

~\Delta(cf) = c\Delta(f) \Rightarrow \sum cf = c \sum f~ (~c~ là hằng số)

~\Delta(f + g) = \Delta(f) + \Delta(g) \Rightarrow \sum (f + g) = \sum f + \sum g~

~\Delta(fg) = f\Delta(g) + Eg\Delta(f) \Rightarrow \sum f\Delta(g) = fg - \sum Eg\Delta(f)~

Note này được dựa trên Concrete Mathematics, 2.5

Ta xét bài toán tính ~\square_n = \sum_{0 \leq k \leq n} k^2~

0. OEIS

Ta có thể tính các giá trị ~\square_n~ với ~n = 0, 1, 2, 3, 4, 5~, rồi sử dụng trang oeis.org để tra công thức.

1. Đoán công thức, chứng minh bằng quy nạp

Đây là phương pháp cơ bản trong sách giáo khoa, tuy nhiên vấn đề chính là các bạn cần biết cách đoán.

2. Pertubation method

Ta sẽ thử áp dụng pertubation method để tính ~\square_n~

Ta có:

~\square_{n+1} = \square_n + (n+1)^2~

~\square_{n+1} = 0 + \sum_{1 \leq k \leq n+1} k^2 = \sum_{1 \leq k+1 \leq n+1} (k+1)^2 = \sum_{0 \leq k \leq n} (k^2 + 2k + 1) = \square_n + 2\sum_{0 \leq k \leq n} k + \sum_{0 \leq k \leq n} 1 = \square_n + 2\sum_{0 \leq k \leq n} k + n+1~

Do đó, ~\square_n + (n+1)^2 = \square_n + 2\sum_{0 \leq k \leq n} k + n+1 \Rightarrow 2\sum_{0 \leq k \leq n} k = (n+1)^2 - (n+1)~

~\square_n~ biến mất nên phương án này thất bại.

Tuy nhiên, ta có thể để ý thấy là ta có thể thu được công thức cho ~\sum_{0 \leq k \leq n} k~ tử việc áp dụng pertubation method cho ~\square_n~. Vì thế, ta có ý tưởng áp dụng pertubation method cho ~C_n = \sum_{0 \leq k \leq n} k^3~ để ra được công thức của ~\square_n~

Ta có:

~C_{n+1} = C_n + (n+1)^3~

~C_{n+1} = 0 + \sum_{1 \leq k \leq n+1} k^3 = \sum_{1 \leq k+1 \leq n+1} (k+1)^3 = \sum_{0 \leq k \leq n} (k^3 + 3k^2 + 3k + 1) = C_n + 3\square_n + 3\frac{n(n+1)}{2} + (n+1)~

Do đó ~C_n + (n+1)^3 = C_n + 3\square_n + 3\frac{n(n+1)}{2} + (n+1) \Rightarrow \boxed{\square_n = \frac{(n+1)^3 - 3\frac{n(n+1)}{2} - (n+1)}{3} = \frac{n(n+1)(2n+1)}{6}}~

3. Repertoire method

Chúng ta sẽ thử tìm công thức tổng quát cho công thức truy hồi sau:

~R_0 = \alpha~

~R_n = R_{n-1} + \beta + \gamma n + \delta n^2~

Đặt ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~

Giả sử ~R_n = 1~. Khi đó ~\begin{cases} \alpha = 1 \\ 1 = 1 + \beta + \gamma n + \delta n^2 \Rightarrow \beta + \gamma n + \delta n^2 = 0 + 0n + 0n^2 \end{cases} \Rightarrow \alpha = 1, \beta = 0, \gamma = 0, \delta = 0~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~\boxed{A(n) = 1}~

Giả sử ~R_n = n~. Khi đó ~\begin{cases} \alpha = 0 \\ n = (n-1) + \beta + \gamma n + \delta n^2 \end{cases} \Rightarrow \alpha = 0, \beta = 1, \gamma = 0, \delta = 0~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~\boxed{B(n) = n}~

Giả sử ~R_n = n^2~. Khi đó ~\begin{cases} \alpha = 0 \\ n^2 = (n-1)^2 + \beta + \gamma n + \delta n^2 \end{cases} \Rightarrow \alpha = 0, \beta = -1, \gamma = 2, \delta = 0~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~2C(n) - B(n) = n^2 \Rightarrow \boxed{C(n) = \frac{n^2 + n}{2}}~

Giả sử ~R_n = n^3~. Khi đó ~\begin{cases} \alpha = 0 \\ n^3 = (n-1)^3 + \beta + \gamma n + \delta n^2 \end{cases} \Rightarrow \alpha = 0, \beta = 1, \gamma = -3, \delta = 3~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~3D(n) - 3C(n) + B(n) = n^3 \Rightarrow \boxed{D(n) = \frac{n^3 + 3\frac{n^2 + n}{2} - n}{3} = \frac{n(n+1)(2n+1)}{6}}~

Ta có:

~\square_0 = 0~

~\square_n = \square_{n-1} + n^2~

nên ta áp dụng công thức khi ~\alpha = 0, \beta = 0, \gamma = 0, \delta = 1~. Tức ~\square_n = D(n) = \boxed{\frac{n(n+1)(2n+1)}{6}}~

4. Dùng sai số giữa ~\int~ và ~\sum~

Ta thấy ~\int~ và ~\sum~ là hai kí hiệu có điểm liên quan chặt chẽ với nhau. Trong khi ~\int~ có thể dùng để tính phần diện tích nằm dưới đường cong thì ~\sum~ có thể được dùng để tính xấp xỉ diện tích nằm dưới đường cong bằng cách tính tổng diện tích các hình chữ nhật.

Từ mối quan hệ giữa ~\int~ và ~\sum~ mà ta có ý tưởng tính ~E_n = \sum_{k=0}^n f(k) - \int_0^n f(x)dx~, biết đâu ta ra được công thức cho ~E_n~ và ~\int_0^n f(x)dx~ mà nhờ đó ra được công thức cho ~\sum_{k=0}^n f(k)~

Ví dụ:

~E_n = \sum_{k=0}^n k^2 - \int_0^n x^2 dx = \sum_{k=0}^n k^2 - (\int_0^1 x^2 dx + \int_1^2 x^2 dx + ... + \int_{n-1}^n x^2dx)~

~E_n = \sum_{k=1}^n (k^2 - \int_{k-1}^k x^2 dx)~

~E_n = \sum_{k=1}^n (k^2 - [\frac{x^3}{3}]_{k-1}^k)~

~E_n = \sum_{k=1}^n (k^2 - \frac{k^3 - (k-1)^3}{3}) = \sum_{k=1}^n(k - \frac{1}{3})~

Từ đây ta dễ dàng tính được ~E_n~. Việc tính ~\int_0^n x^2 dx~ cũng đơn giản, và từ hai biểu thức này và công thức ~E_n = \sum_{k=0}^n f(k) - \int_0^n f(x)dx~, ta tính được ~\square_n~

5. Biến tổng một biến thành tổng nhiều biến

Ta có:

~\square_n = \sum_{k=1}^n k^2 = \sum_{k=1}^n \underbrace{k+k+k+...+k}_{k \text{ lần}} = \sum_{k=1}^n \sum_{j=1}^k k~

Ta sẽ tìm cách mang ~\sum_j~ ra ngoài. Xét các cặp ~(k,j)~ được xét trong tổng. Các cặp này thỏa mãn điều kiện ~1 \leq j \leq k \leq n~.

~j~ có thể chạy từ ~1~ đến ~n~, và với mỗi ~j~, ~k~ có thể chạy từ ~j~ đến ~n~. Vì vậy:

~\square_n = \sum_{j=1}^n \sum_{k=j}^n k~

~\square_n = \sum_{j=1}^n \frac{(j + n)(n - j + 1)}{2}~ (dùng công thức tính tổng ~j + (j+1) + ... + n~)

~\square_n = \frac{1}{2} \sum_{j=1}^n (-j^2 + j + n^2 + n)~

~\square_n = -\frac{1}{2}\square_n + \frac{1}{2}(\frac{n(n+1)}{2} + n^3 + n^2)~

~\Rightarrow \frac{3}{2}\square_n = \frac{n(n+1)}{2} + n^3 + n^2~

Từ đây, ta dễ dàng tính được ~\square_n~

Ngoài các phương pháp trên, chúng ta còn hai phương pháp sử dụng sai phân (note sau), hoặc sử dụng hàm sinh.