T.2 · Matematika diskrit, probabilitas, dan metode numerik

Persiapan GRE tingkat sarjana. Tujuan lokal dalam cakupan ETS yang ditinjau; ini adalah pengajaran orisinal, bukan uji coba resmi atau prediktor skor.

Prasyarat: Penghitungan hingga, probabilitas dasar, rekurensi dan turunan.

• Gunakan penghitungan, rekurensi, penalaran graf dan logika
• Hitung probabilitas dan sifat distribusi
• Terapkan aproksimasi numerik dan evaluasi kesalahan

rekurensi: Aturan yang menghubungkan suku barisan dengan suku-suku sebelumnya.

saling lepas: Peristiwa yang tidak dapat terjadi bersamaan.

Pilihlah model penghitungan terlebih dahulu: pemilihan berurutan dari r objek berbeda menggunakan n(n−1)⋯(n−r+1), sedangkan himpunan bagian tak berurutan menggunakan C(n,r). Graf sederhana lengkap pada n titik memiliki satu sisi per pasangan titik tak berurutan, sehingga menghasilkan n(n−1)/2 sisi; loop dan sisi ganda akan mengubah model tersebut. Untuk n garis dalam posisi umum di bidang, garis ke-k memotong k−1 garis sebelumnya pada titik-titik yang berbeda dan menambahkan k daerah. Totalnya adalah 1+n(n+1)/2; garis sejajar atau konvergensi tiga garis akan membatalkan perhitungan tersebut.

Gunakan komplemen untuk menghitung setidaknya satu kemunculan, dan kondisikan pada populasi sisa aktual setelah pengambilan tanpa pengembalian. Untuk r hasil i.i.d. yang dipilih dari n nilai yang sama banyak kemungkinannya, probabilitas bahwa semuanya berbeda adalah n(n−1)⋯(n−r+1)/n^r ketika r≤n. Komplemennya menghitung hasil yang berulang. Untuk penghitungan binomial dengan N percobaan independen dan probabilitas keberhasilan tetap p, rata-rata adalah Np dan varians Np(1−p). Probabilitas yang identik saja tidak menetapkan independensi.

Sebuah rekurensi menggambarkan nilai-nilai selanjutnya dari nilai-nilai sebelumnya dan memerlukan cukup data awal untuk menentukan sebuah barisan. Pisahkan indeks dari nilainya: a_n=2a_(n−1) dengan a_0=3 memberikan a_n=3·2^n. Argumen graf dan algoritma sering kali menetapkan rekurensi dengan mengidentifikasi apa yang ditambahkan oleh vertex atau langkah baru. Rumus tertutup harus memenuhi baik rekurensi maupun kondisi awalnya; menyesuaikan beberapa suku yang diamati tidak membuktikannya untuk setiap indeks.

Aproksimasi numerik memerlukan argumen kesalahan. Bisekci mempertahankan rentang berubah tanda untuk fungsi kontinu dan menggandakan lebarnya pada setiap langkah; nol mungkin tidak ada jika kontinuitas gagal. Pembaruan Newton adalah x_new=x−f(x)/f′(x), yang memerlukan turunan tak nol pada titik saat ini; konvergensi tidak otomatis dari setiap nilai awal. Residual aproksimasi dan kesalahannya dalam x adalah berbeda. Nyatakan asumsi metode dan kriteria penghentian, alih-alih menganggap desimal tambahan yang ditampilkan sebagai akurasi.

Untuk f(x)=x²−2 dan x₀=1, langkah Newton memberikan 1−(1−2)/2=1.5. Nilai berikutnya adalah 1.5−0.25/3=1.4167. Ini mendekati sqrt(2), tetapi f′(0)=0 membuat nol sebagai titik awal yang tidak valid.

Peristiwa dengan probabilitas positif tidak dapat sekaligus independen dan saling lepas.

Empat pengambilan bertanda bersifat independen dan seragam dari lima simbol, dengan pengembalian. Temukan probabilitas bahwa setidaknya dua pengambilan sesuai. Bandingkan jumlah pemilihan berurutan dan tak berurutan dari empat simbol berbeda.

Penyelesaian terarah

Terdapat $5^4$ string pengambilan berurutan yang sama banyak kemungkinannya. String tanpa pengulangan berjumlah $5\cdot4\cdot3\cdot2=120$.

Pemilihan berurutan yang berbeda berjumlah 120; himpunan bagian tak berurutan berjumlah $\binom54=5$. Setiap himpunan bagian muncul dalam $4!=24$ urutan. Membagi dengan $4!$ hanya tepat untuk penghitungan tak berurutan, bukan penyebut probabilitas pengambilan.

Terapkan bisekci pada $f(x)=x^3-2$ pada $[1,2]$. Berikan dua rentang yang tersimpan pertama dan batas kesalahan titik tengah setelah sepuluh bisekci. Apakah perubahan tanda saja dapat membenarkan bisekci untuk $1/x$ pada $[-1,1]$?

Periksa setelah mencoba

Polinomial tersebut kontinu; $f(1)<0<f(2)$. Titik tengah pertama adalah $1.5$ dengan nilai positif, menyimpan $[1,1.5]$. Yang berikutnya adalah $1.25$ dengan nilai negatif, menyimpan $[1.25,1.5]$. Setelah sepuluh penggandaan, lebar adalah $2^{-10}$ dan titik tengah dari rentang yang tersimpan itu berbeda dari akar yang dibatasi oleh rentang tersebut paling banyak $2^{-11}=1/2048$. Batas kesalahan menggunakan rentang, bukan residual kecil saja. Untuk $1/x$, nol adalah singularitas dan tidak ada akar. Kontinuitas pada rentang gagal; tanda ujung yang berlawanan tidak membenarkan metode tersebut.