Bỏ qua nội dung

T.2 · Discrete mathematics, probability and numerical methods

GRE · GRE Subject Test · GRE Mathematics · Chủ đề 6

6

Phạm vi và yêu cầu tiên quyết

Chuẩn bị GRE đại học. Mục tiêu cục bộ nằm trong phạm vi ETS đã xem xét; đây là giảng dạy nguyên bản, không phải bài thi chính thức hoặc dự đoán điểm số.

Kiến thức cần thiết: Đếm hữu hạn, xác suất sơ cấp, dãy truy hồi và đạo hàm.

  • Sử dụng phương pháp đếm, dãy truy hồi, lập luận về đồ thị và logic
  • Tính toán xác suất và các đặc trưng phân phối
  • Áp dụng xấp xỉ số và đánh giá sai số

dãy truy hồi: Quy tắc liên hệ một số hạng của dãy với các số hạng trước đó.

xung khắc nhau: Các sự kiện không thể cùng xảy ra.

Từ vựng Luyện tập
English Tiếng Việt
recurrence/rɪˈkʌrəns/ Quan hệ truy hồi
mutually exclusive/ˈmjuːtʃuːəli eksˈkluːsɪv/ Xung khắc lẫn nhau
6

Chọn và biện minh cho một phương pháp

Chọn mô hình đếm trước: sắp xếp có thứ tự r vật thể khác nhau từ n vật dùng công thức n(n−1)⋯(n−r+1), còn tập con không thứ tự dùng C(n,r). Đồ thị đơn đầy đủ trên n đỉnh có một cạnh cho mỗi cặp đỉnh không thứ tự, tạo ra n(n−1)/2 cạnh; chu trình tự loop và cạnh đa sẽ làm thay đổi mô hình. Với n đường thẳng nằm vị trí tổng quát trong mặt phẳng, đường thẳng thứ k cắt k−1 đường thẳng trước đó tại các điểm phân biệt và tạo thêm k vùng mới. Tổng số là 1+n(n+1)/2; các đường song song hoặc đồng quy ba đường sẽ phá vỡ công thức đếm này.

Sử dụng phần bù để đếm ít nhất một lần xuất hiện, và điều kiện hóa trên quần thể còn lại thực tế sau khi rút mẫu không hoàn lại. Đối với r kết quả iid được chọn từ n giá trị có khả năng xảy ra bằng nhau, xác suất để tất cả đều khác nhau là n(n−1)⋯(n−r+1)/n^r khi r≤n. Phần bù của nó đếm các kết quả trùng lặp. Đối với biến đếm nhị phân với N phép thử độc lập và xác suất thành công p cố định, kỳ vọng là Np và phương sai là Np(1−p). Chỉ riêng xác suất bằng nhau chưa đủ để khẳng định tính độc lập.

Một dãy truy hồi mô tả các giá trị sau dựa trên các giá trị trước và cần đủ dữ liệu ban đầu để xác định một dãy. Tách chỉ số khỏi giá trị: a_n=2a_(n−1) với a_0=3 cho ta a_n=3·2^n. Lập luận đồ thị và thuật toán thường thiết lập dãy truy hồi bằng cách xác định xem một đỉnh hoặc bước mới thêm vào gì. Công thức đóng phải thỏa mãn cả dãy truy hồi lẫn điều kiện ban đầu; việc khớp một vài số hạng quan sát được không chứng minh được công thức đúng cho mọi chỉ số.

Xấp xỉ số cần có lập luận về sai số. Phương pháp chia đôi giữ nguyên khoảng có sự đổi dấu cho hàm liên tục và thu hẹp chiều rộng đi một nửa ở mỗi bước; nghiệm có thể không tồn tại nếu tính liên tục bị vi phạm. Cập nhật Newton là x_new=x−f(x)/f′(x), yêu cầu đạo hàm khác 0 tại điểm hiện tại; hội tụ không tự động xảy ra từ mọi giá trị khởi đầu. Phần dư của xấp xỉ và sai số của x là hai khái niệm khác nhau. Hãy nêu rõ giả thiết của phương pháp và tiêu chí dừng, thay vì coi những chữ số thập phân hiển thị thêm là độ chính xác.

6

Ví dụ giải thích chi tiết

Với f(x)=x²−2 và x₀=1, bước Newton cho 1−(1−2)/2=1.5. Giá trị tiếp theo là 1.5−0.25/3=1.4167. Những giá trị này xấp xỉ sqrt(2), nhưng f′(0)=0 khiến 0 trở thành điểm bắt đầu không hợp lệ.

Toán học rời rạc, xác suất và phương pháp số: ví dụ về khóa học
Minh họa khóa học gốc; các giá trị của nó thuộc về bài giải mẫu, không phải bài tập thực hành sau đó.
6

Điều kiện và phản ví dụ

Các sự kiện có xác suất dương không thể vừa độc lập vừa loại trừ lẫn nhau.

6

Ứng dụng hướng dẫn

Bốn lần rút có nhãn là độc lập và phân bố đều từ năm ký hiệu, với hoàn lại. Tìm xác suất để có ít nhất hai lần rút giống nhau. So sánh số lượng sắp xếp có thứ tự và tập con không thứ tự gồm bốn ký hiệu khác nhau.

Giải mẫu

Có $5^4$ chuỗi rút có khả năng xảy ra bằng nhau. Số chuỗi không lặp lại là $5\cdot4\cdot3\cdot2=120$.

$$P(\text{repeat})=1-\frac{5\cdot4\cdot3\cdot2}{5^4}=\frac{101}{125}.$$
Số sắp xếp có thứ tự khác nhau là 120; số tập con không thứ tự là $\binom54=5$. Mỗi tập con xuất hiện trong $4!=24$ cách sắp xếp. Việc chia cho $4!$ chỉ phù hợp cho phép đếm không thứ tự, không phải mẫu số của xác suất rút.

6

Chuyển giao độc lập

Áp dụng phương pháp chia đôi $f(x)=x^3-2$ trên $[1,2]$. Đưa ra hai ngoặc đầu tiên được giữ lại và giới hạn sai số của điểm giữa sau mười lần chia đôi. Liệu việc chỉ thay đổi dấu có đủ để biện minh cho phương pháp chia đôi đối với $1/x$ trên $[-1,1]$?

Kiểm tra sau khi đã làm

Đa thức liên tục; $f(1)<0<f(2)$. Điểm giữa đầu tiên là $1.5$ với giá trị dương, giữ lại $[1,1.5]$. Tiếp theo là $1.25$ với giá trị âm, giữ lại $[1.25,1.5]$. Sau mười lần chia đôi, độ rộng là $2^{-10}$ và điểm giữa của khoảng giữ lại đó khác với nghiệm nằm trong khoảng đó nhiều nhất là $2^{-11}=1/2048$. Giới hạn sai số dựa vào khoảng, không phải chỉ dựa vào phần dư nhỏ. Đối với $1/x$, zero là điểm kỳ dị và không có nghiệm. Tính liên tục trên khoảng bị vi phạm; các dấu trái chiều ở hai đầu khoảng không biện minh được cho phương pháp này.

Bài học tương tác về chủ đề này

Làm theo từng bước, kèm theo bài tập kiểm tra ngay lập tức.

Nhiều chủ đề hơn trong GRE · GRE Subject Test · GRE Mathematics

Đăng nhập hoặc tạo tài khoản

IGCSE, A-Level & AP