Toán rời rạc cần thiết như thế nào cho tư duy lập trình?

#42

minh moi biet do. chuan bi hoc TRR r

#43

Anh Hai lớn hơn anh Ba :))

3 Likes
#44

Chuyện học toàn thì tùy vào mục đích của bạn. Nếu như bạn muốn làm 1 số ngành chuyên sâu hoặc đi theo hướng nghiên cứu thì nên tập trung học tốt toán rời rạc

Lúc trước mình học các phần sau:

  1. Lý thuyết tập hợp: hỗ trợ gián tiếp cho tư duy khi viết SQL, đại khái là giúp bạn tưởng tượng tốt hơn :sunny:
  2. Lý thuyết ma trận: dùng cho xử lý ảnh, machine learning, nếu như mình nhớ ko lầm thì hình như có liên quan đến cả mấy thuật toán mã hóa. Theo mình nhớ là ma trân dùng rất nhiều.
  3. Lý thuyết đồ thị: dùng cho các bài toán tìm đường, ra quyết định…
  4. Lý thuyết tổ hợp: google mấy bài xử lý chuỗi là thấy ngay

Còn một số phần nữa nói về đệ quy, backtracking (bài toán 8 hậu, con mã đi tuần), mình không nhớ cái này được xếp vào phần nào, nhưng cũng được ứng dụng nhiều.

Về ứng dụng trong công việc, mình đi làm outsource hơn 2 năm (phần lớn là web, data nhiều nhưng vấn đề không quá phức tạp) , ngoài lý thuyết tập hợp ra thì chưa ứng dụng tí toán rời rạc nào hết :frowning:. Cơ mà mình để ý bên Tây họ rất khoái dùng mấy giải thuật đệ quy (recursive)

Nguồn: Kinh nghiệm cá nhân và wikipedia

2 Likes
#45

Song ánh và đơn ánh

  • Số số nguyên bằng số phân số
  • Số thực nhiều hơn số nguyên
  • Mọi đường tròn không suy biến đều có cùng số số điểm (equinumerous)

lí thuyết tập hợp :slight_smile:

2 Likes
#46

Em thấy Toán Rời Rạc hay mà :smiley:
Ví dụ tìm phần tử thứ n của dãy Fibonaci, thông thường người ta phải lặp(hoặc đệ quy) đến phần tử thứ (n-1), tốn khá nhiều thời gian và tài nguyên. Thay vào đó ta có thể xây dựng một công thức và tìm phần tử thứ n trong 1 nốt nhạc chỉ bằng 1 phép toán, rõ ràng là tiện lợi hơn nhiều.

#47

O(logn) (phép nhân ma trận) chứ không phải 1 đâu :slight_smile: vì không tính đúng được số thập phân.

“0 là lớn nhất, 1 là bé nhất” :smiley:

1 Like
#49

Cho e xin keyword để tìm hiểu về phương pháp này với ạ.

#50

Hôm nay rảnh rỗi, mình đi chứng minh 2 < 3 chơi, có 2 cách: ánh xạ và tiên đề Peano. :penguin:

Theo định nghĩa số tự nhiên theo cardinality: cho số tự nhiên n, tập X := { x ∈ N : 1 ≤ x ≤ n } thì |X| := n. Do đó, nếu cho tập A = { 1, 2 } thì |A| = 2, tương tự tập B = { 1, 2, 3 }, có |B| = 3.

Thiết lập một đơn ánh (injection) f: A -> B, có 3 khả năng cho f:

  • f(1) = 1, f(2) = 2 hoặc f(1) = 2, f(2) = 1: 3 ∈ B nhưng không có x ∈ A để f(x) = 3.
  • f(1) = 1, f(2) = 3 hoặc f(1) = 3, f(2) = 1, 2 ∈ B nhưng không có x ∈ A để f(x) = 2.
  • f(1) = 2, f(2) = 3 hoặc f(1) = 3, f(2) = 2, 1 ∈ B nhưng không có x ∈ A để f(x) = 1.

Trong cả 3 trường hợp đều có 1 phần tử trong B không được f chỉ tới, hay f không là toàn ánh (surjection). Vì f đơn ánh nhưng không toàn ánh, nên |A| < |B|. Thế cardinality của A và B, được 2 < 3.

Cách khác đàng hoàng hơn, dùng hệ tiên đề Peano, xem successor operator là s: N -> N (s(0) = 1, s(1) = 2, s(2) = 3,…)

2 là số tự nhiên, vì 2 = s(1) = s(s(0))
3 là số tự nhiên, vì 3 = s(2)
Theo định nghĩa phép cộng: 2 + 1 = 2 + s(0) = s(2 + 0) = s(2).
Mà 3 = s(2), nên 3 = 2 + 1
Theo định nghĩa dấu >: Cho 2 số tự nhiên a, b, a > b khi và chỉ khi a = b + m, với m là một số tự nhiên khác 0. Do đó từ 3 = 2 + 1, suy ra 3 > 2.
Theo định nghĩa dấu < (a < b khi và chỉ khi b > a), suy ra kết luận 2 < 3.

P/s: đào mộ xíu

4 Likes
#53

có phải có " sự chưa chặt chẽ - hay đại loại vậy, e không biết diễn tả sao cho đúng" giữa các công thức, định lý toán nào đó dẫn đến chứng minh này là đúng ạ?

#54

“Nhớ mang máng” mà bạn :smiley: nhưng “0 lớn hơn 1” là chuyện có thật.

Xét qh “chia hết cho” với các số nguyên, a với -a là tương đương (hơn kém nhau phần tử trung hòa). VD như 6 chia hết cho 3 thì “6 lớn hơn 3” :slight_smile:

2 Likes
#55

Đa số bài giải sai khi bạn dùng một định lí hoặc mệnh đề mà chưa kiểm tra phần chứng minh có đúng hay không. Chỉ có tiên đề (axioms) là chấp nhận, không cần chứng minh.

Và cách tránh nó là đừng bao giờ dùng 1 mệnh đề nào được giới thiệu trong sách mà bạn chưa xem phần chứng minh.

Đơn giản vậy thôi. :upside_down_face:

3 Likes
#56

Câu này nói ra thấy có vẻ như trường bạn dạy vậy nên bạn nghĩ chỗ nào cũng giống nhau? sao mà CNPM lại chỉ đi làm toàn phần mềm quản lý?
CNPM làm tất cả mọi thứ liên quan đến phần mềm, tùy yêu cầu khách hàng, trong đó thì phần mềm quản lý chỉ là 1 phần nhỏ thôi.

2 Likes
#58

^ ý kiến cá nhân :slight_smile:

“Toán rời rạc” bao gồm hơn chục ngành mà, đào sâu vào từng ngành mới thấy nó hay.

6 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?