T.2 · Discrete mathematics, probability and numerical methods

학부 GRE 준비. 검토된 ETS 범위 내의 로컬 목표; 이는 공식 시험이나 점수 예측기가 아닌 독자적 교육 과정입니다.

이수 전 필수 지식: 유한 세기, 기초 확률, 재귀 관계 및 미분법.

• 세기, 재귀 관계, 그래프 추론 및 논리를 사용함
• 확률 및 분포 성질을 계산함
• 수치 근사 적용 및 오차 평가

반복 관계: 수열의 한 항을 이전 항들과 연결하는 규칙.

상호 배타적: 함께 발생할 수 없는 사건들.

먼저 세기 모델을 선택하십시오: r개의 서로 다른 객체의 순서 선택은 n(n−1)⋯(n−r+1)를 사용하며, 무순서 부분집합은 C(n,r)을 사용합니다. n개 정점을 가진 완전 단순 그래프는 모든 무순서 정점 쌍에 대해 하나의 변이 있어, n(n−1)/2개의 변을 가집니다; 루프나 다중 변은 모델을 변경합니다. 평면에서 일반 위치에 있는 n개의 직선에서 k번째 직선은 이전 k−1개의 직선을 서로 다른 점에서 교차하여 k개의 영역을 추가합니다. 총합은 1+n(n+1)/2이며, 평행이나 삼중 교점은 해당 계산을 무효화합니다.

Use complements to count at least one occurrence, and condition on the actual remaining population after a draw without replacement. For r iid outcomes chosen from n equally likely values, the probability that all are distinct is n(n−1)⋯(n−r+1)/n^r when r≤n. Its complement counts repeated outcomes. For a binomial count with N independent trials and fixed success probability p, mean is Np and variance Np(1−p). Identical probabilities alone do not establish independence.

반복 관계는 이전 값들을 통해 이후 값을 설명하며, 수열을 결정하기에 충분한 초기 데이터가 필요합니다. 인스와 값을 분리하십시오: a_n=2a_(n−1) with a_0=3은 a_n=3·2^n을 줍니다. 그래프 및 알고리즘 논증은 새로운 정점이나 단계가 무엇을 추가하는지를 식별하여 반복 관계를 증명하는 경우가 많습니다. 닫힌 공식은 반복 관계와 초기 조건 둘 다를 만족해야 하며, 몇 개의 관측된 항을 fitting하는 것은 모든 인덱스에 대해 증명하지 않습니다.

수치 근사에는 오차 논증이 필요합니다. 이분법은 연속 함수의 부호가 바뀌는 구간을 보존하고 각 단계마다 그 너비를 반으로 줄입니다; 연속성이 실패하면 영점이 없을 수 있습니다. 뉴턴의 업데이트는 x_new=x−f(x)/f′(x)이며, 현재 지점에서 도함수가 0이 아니어야 합니다; 모든 시작값에서 수렴이 자동이지는 않습니다. 근사의 잔차와 x에서의 오차는 다릅니다. 방법의 가정과 멈춤 기준을 명시하십시오. 단순히 표시된 추가 소수점을 정확도로 간주하지 마십시오.

f(x)=x²−2이고 x₀=1일 때, 뉴턴의 단계는 1−(1−2)/2=1.5를 줍니다. 다음 값은 1.5−0.25/3=1.4167입니다. 이들은 sqrt(2)에 대한 근사치이지만, f′(0)=0인 경우 0은 유효하지 않은 시작점입니다.

양수 확률을 가진 사건들은 동시에 독립적이거나 상호 배타적일 수 없습니다.

네 개의 라벨링된 추첨은 5가지 기호 중 하나를ocs로 독립적이고 균등하게 선택합니다. 최소 두 개의 추첨이 일치할 확률을 구하십시오. 네 개의 서로 다른 기호의 순서 선택과 무순서 선택의 개수를 비교하십시오.

풀이 과정

동일한 확률을 갖는 순서 추첨 문자열은 $5^4$개입니다. 반복이 없는 문자열의 개수는 $5\cdot4\cdot3\cdot2=120$입니다.

순서 선택된 서로 다른 선택의 개수는 120이며, 무순서 부분집합의 개수는 $\binom54=5$입니다. 각 부분집합은 $4!=24$개의 순서에 포함됩니다. $4!$로 나누는 것은 무순서 개수에만 적절하며, 추첨 확률의 분모에는 적절하지 않습니다.

Apply bisection to $f(x)=x^3-2$ on $[1,2]$. Give the first two retained brackets and a bound for midpoint error after ten bisections. Would a sign change alone justify bisection for $1/x$ on $[-1,1]$?

시도 후 확인

다항식은 연속이며, $f(1)<0<f(2)$입니다. 첫 중점은 $1.5$이며 양수 값을 가지므로, $[1,1.5]$을 유지합니다. 다음 중점은 $1.25$이며 음수 값을 가지므로, $[1.25,1.5]$을 유지합니다. After ten halvings, width is $2^{-10}$ and the midpoint of that retained bracket differs from the bracketed root by at most $2^{-11}=1/2048$. The error bound uses the bracket, not a small residual alone. $1/x$에 대해, 0은 특이점이며 근이 없습니다. 구간에 대한 연속성이 실패하므로, 반대 끝점의 부호 차이는 방법을 정당화하지 않습니다.