Apa rumus matematika yang baik untuk diketahui untuk pemrograman? [Tutup]

Apa sajakah rumus matematika yang agak umum Anda pelajari yang membantu Anda menulis algoritma yang lebih baik dan menjadi programmer yang lebih baik?

Contoh: Saya belajar tentang rumus jarak ecludian: sqrt((x1-x2)^2+(y1-y2)^2)yang membantu saya memahami cara menemukan objek seperti dengan membandingkan 2 faktor.

Mengetahui kekuatan 2 sangat berguna, terutama ketika berhadapan dengan operasi bitwise tingkat rendah.

Aljabar Boolean sudah disebutkan, tetapi saya ingin memberikan beberapa contoh praktis.

Aljabar Boolean sangat sering berguna ketika Anda bekerja dengan ekspresi boolean yang kompleks (dalam ifpernyataan misalnya).

Pasangan ekspresi dan hukum yang berguna:

Distribusi

A & (B | C) = (A & B) | (A & C)

A | (B & C) = (A | B) & (A | C)

Jadi lain kali Anda menemukan ekspresi seperti itu:

if((A || B) && (A || C) && (A || D) && (A || E)) { ... }

Anda dapat dengan mudah mengecilkannya ke:

if(A || (B && C && D && E)) { ... }

Negasi dan Hukum De Morgan

! (! A) = A

! (A & B) =! A | ! B

! (A | B) =! A &! B

Katakanlah Anda memiliki pernyataan seperti itu:

if(!A && !B && !C) {..}

dan Anda perlu membangun kebalikannya. Penulisan:

if(!(!A && !B && !C)) {...}

akan bekerja, tetapi tidak terlihat sekeren ini:

if(A | B | C) {...}

Dalam pengalaman saya, rumus matematika digunakan untuk perhitungan yang sangat spesifik, yang mungkin atau mungkin tidak berlaku untuk proyek Anda.

Jika Anda perlu menghitung sesuatu, biasanya ada fungsi di perpustakaan atau contoh kode sumber di sekitar yang dapat menghitungnya untuk Anda. Misalnya, fungsi PMT () Excel, yang menghitung pembayaran yang diperlukan untuk membayar utang sebesar X% selama periode Y. Apakah Anda benar-benar ingin tahu bagaimana menghitungnya, atau apakah cukup dengan hanya memanggil yang built-in?

Dalam 10 tahun terakhir, saya tidak berpikir saya perlu menggunakan apa pun dari perpustakaan Matematika selain Ceil (), Min () dan Max (), yang menunjukkan bahwa meskipun komputer dirancang untuk memecahkan masalah berbasis matematika , yang umum digunakan saat ini adalah pengambilan keputusan seputar aliran data.

Ambil, misalnya, Facebook, yang memiliki sejumlah besar kode. Mungkin ada beberapa Matematika di suatu tempat, tapi saya curiga terutama di Crypto API, yang mungkin merupakan pustaka sistem. Tetapi akses basis data, keputusan otorisasi, pembuatan halaman, dan perutean informasi mungkin tidak menggunakan banyak Matematika.

Ya, ada pasar yang membutuhkan banyak Matematika - keuangan, fisika, teknik - tetapi dalam industri ini, disiplin utama Anda lebih cenderung adalah Matematika / Ekonomi, Fisika, Teknik, dll, jadi pertanyaan Anda adalah 'bagaimana saya bisa menulis rumus f (x) dalam bahasa Y? '

Penggunaan waktu Anda yang lebih baik, IMO, akan menyelidiki Algoritma (termasuk notasi O Besar) dan Pola Desain.

Tidak ada formula yang bisa menjadikan Anda seorang programmer yang lebih baik.

Keterampilan terkait matematika dapat menjadikan Anda seorang programmer yang lebih baik:

• Metode ilmiah - cara berpikir matematika / sains dan pemecahan masalah
• Abstraksi - kemampuan untuk mengenali abstraksi dan pola
• Warisan - penggunaan kembali pekerjaan / metode yang ada dalam memecahkan masalah baru
• Pengalaman - memahami serangkaian masalah dan solusi

Rumus statistik dasar baik untuk diketahui. Saya telah menggunakan regresi linier setidaknya beberapa kali.

Saya ingin menyebutkan seri Taylor yang cukup berguna untuk mendapatkan perkiraan cepat dari fungsi "yang lebih berat". Misalnya sin(x)sekitar 0 dapat didekati dengan x-(x*x*x/6).

Secara umum, gagasan bahwa ada cara pintar untuk memperkirakan hal-hal dengan cepat, alih-alih menghitungnya ke angka signifikan terakhir (meskipun untuk fungsi dasar, kebanyakan prosesor modern mengandung implementasi cepat terprogram sehingga menggunakan Taylor untuk memperkirakan dosa mungkin tidak begitu signifikan gain kecepatan).

Hukum De Morgan, tentang mentransformasikan Boolean "dan" dan "atau" relatif ke negasi, dan beberapa informasi terkait yang lebih mendasar tentang logika Boolean (seperti negasi ganda).

Rule of Three (tipe Multiplikasi Lintas)

+1 untuk rumus statistik Dasar.

Saya melihat banyak orang dengan kesulitan untuk menerapkan aturan sederhana ini pada kode dasar.

Urutan dan matematika seri .

Saya telah melihat terlalu banyak sekolah yang mengajarkan "menulis satu lingkaran untuk menjumlahkan semua angka antara x dan y" alih-alih "algoritma yang MENGAGUMKAN"

Juga ... https://docs.google.com/viewer?url=http://courses.csail.mit.edu/6.042/fall10/mcs-ftl.pdf

Hukum Kosinus , sangat penting untuk banyak masalah geometris,

terutama penentuan sudut.

Pemrograman adalah bidang yang sangat luas. Rumus matematika tergantung pada area pemrograman Anda. Jika Anda tertarik dengan grafis, pemrograman game Anda perlu tahu lebih banyak trigonometri, geometri. Pemrograman game dapat dikategorikan lebih lanjut ke dalam bidang-bidang seperti, fisika, rendering, shader .. dan daftarnya berlanjut. Jadi jika Anda seorang ahli simulasi fisika, maka Anda harus tahu hal-hal yang berkaitan dengan Fisika.
Jika Anda ke keamanan, Anda harus menjadi ahli Teori Angka.
Secara umum, Anda dapat pergi kombinasi dari ini, dan yang pernah Anda minati. Belajar tidak pernah menyakitkan.

Metode Pembuktian

Terutama, yang saya gunakan dengan frekuensi relatif:

• Bukti kelelahan (sering diabaikan, tetapi mengingat kekuatan mesin saat ini, seringkali lebih layak daripada yang dipikirkan beberapa orang)
• Bukti dengan induksi
• Bukti oleh kontradiksi

Ada lebih banyak, dan saya telah menggunakan banyak dari mereka pada satu titik atau yang lain, tetapi ini adalah 3 yang saya ingat pernah digunakan sekilas. Mereka juga sangat membantu jika Anda dapat menjaga niat mereka saat menulis unit atau tes integrasi.

T (n) = aT (n / b) + f (n), a> = 1, b> 1

Master Theorem baik untuk diketahui dalam pemrograman. Ini memungkinkan Anda memecahkan hubungan perulangan yang dapat membantu Anda menemukan kompleksitas algoritma rekursif. Ini sangat penting ketika menulis algoritma gaya "divide-and-conquer". Secara kasar, Anda dapat menggunakan teorema master untuk mendapatkan kompleksitas jika Anda mengetahui kompleksitas setiap "langkah" dan faktor percabangan.

• aljabar
• trigonometri
• vektor (operasi matriks)
• kalkulus
• [berbagai interpolasi dan turunannya]
• [permukaan, NURBS]

(Yang di brackers lebih dari jenis "diterapkan")

Sulit untuk memberikan arahan umum, karena sangat tergantung pada bidang Anda. Tapi di atas mencakup dasar-dasar gelar teknik cukup banyak. Pikiran Anda, kategori-kategori ini sering tumpang tindih (trigonometri + operasi matriks., Kalkulus + operasi matriks., Dan sebagainya.).

Saya selalu memiliki buku pegangan Matematika dekat. Seseorang sering tidak yakin akan sesuatu, dan itu membantu untuk disajikan secara teratur.

Mengetahui aljabar boolean sangat membantu. Itu membuat Anda dari menulis kode seperti

if (x < 10)
    return true;
else
    return false;

Untuk masalah optimasi, ada baiknya memahami kemungkinan log. Misalnya, jika Anda mencoba untuk meminimalkan jumlah kuadrat, itu sama dengan memaksimalkan log kemungkinan, karena (secara kasar)

log( Product( exp( -(x[i]-mean)^2 )) )
  =
  - Sum( (x[i]-mean)^2 )

Favorit lain di bidang penyetelan kinerja adalah distribusi Binomial dan Beta. Mereka sangat mudah untuk dihitung.

Jika Anda mengambil 10 sampel acak dari keadaan suatu program, dan itu dalam kondisi tertentu untuk F = 40% dari waktu, maka itu sama seperti percobaan lemparan koin dengan koin yang tidak adil. Frekuensi Anda akan melihatnya dalam kondisi itu adalah distribusi Binomial dengan rata-rata 10 * 0,4 = 4, dan standar deviasi sqrt (10 * 0,4 * 0,6) = sqrt (2,4) = 1,55.

Di sisi lain, jika Anda mengambil 10 sampel dan kebetulan melihatnya dalam kondisi itu pada 4 sampel, apa yang memberitahu Anda tentang seberapa besar F? Hasil yang mungkin adalah 0, 1, 2, 3, 4, ..., 9, 10. Itu 11 kemungkinan, dan kemungkinan yang Anda lihat (4) adalah yang ke-5. Jadi, ambil 11 angka acak seragam (0,1), dan urutkan. Distribusi yang ke-5 adalah distribusi F, distribusi Beta. Mode-nya adalah 4/10. Artinya adalah 5/11. Variansnya adalah 5 * 6 / (11 ^ 2 * 12) = 0,021, dan standar deviasi = 0,144.

Banyak orang berpikir sejumlah besar sampel diperlukan untuk menemukan masalah kinerja perangkat lunak dan menghindari menemukan yang salah. Distribusi ini menunjukkan bahwa sejumlah kecil sampel dapat mengungkapkan banyak tentang biayanya.

Ini mungkin agak sederhana, tetapi G=(V,E)bagus untuk diingat. Dengan kata lain, grafik adalah seperangkat simpul dan tepi. Grafik sangat berguna untuk mewakili banyak hal.