Toán Học Rời Rạc Ứng Dụng Trong Tin Học [NXB Khoa Học Kỹ Thuật 1997] - Kennth H. Rosen, 877 Trang

Discussion in 'Toán Học' started by quanh.bv, Jun 1, 2022.

Tags:

• kennth h. rosen
• nxb khoa học kỹ thuật 1997
• toán học rời rạc ứng dụng trong tin học ebook pdf

1. quanh.bv Hỗ Trợ Diễn ĐànStaff Member Quản Trị Viên

   Toán học rời rạc không phải là một chủ đề mới nhưng giáo trình hay về toán học rời rạc và ứng dụng của nó thì không có nhiều. Mà hay đến mức được tái bản nhiều lần và được sử dụng trong hơn 300 trường học như quyển sách của Giáo sư Kenneth H. Rosen thì lại càng hiếm, nếu không muốn nói là chưa hề thấy. Chất lượng của một giáo trình được thể hiện ở sự súc tích của nội dung và tính sư phạm của cấu trúc và cách trình bày nội dung đó. Điều này đòi hỏi tác giả phải thấu hiểu sâu sắc chủ đề, có bề dày thực nghiệm sư phạm và dĩ nhiên có sở trường viết lách.

   Toán Học Rời Rạc Ứng Dụng Trong Tin Học NXB Khoa Học Kỹ Thuật 1997 Kennth H. Rosen 877 Trang File PDF-SCAN

   Link download //thuvien.ntu.edu.vn/Opac/DmdInfo.aspx?dmd_id=13066 //drive.google.com/drive/folders/1yLBzZ1rSQoNjmWeJTZ3WGQHg04L1

   Zalo/Viber: 0944625325 | buihuuhanh@gmail.com

   Giải Tích Hàm [NXB Khoa Học Kỹ Thuật 2006] - Nguyễn Phụ Hy, 188 Trang14/05/2017 Đại Số Tuyến Tính Dùng Trong Kinh Tế [NXB Khoa Học Kỹ Thuật 1997] - Trần Văn Hạo, 195 Trang31/05/2022 Xác Suất Thống Kê [NXB Đại Học Quốc Gia 2008] - Đào Hữu Hồ, 261 Trang05/12/2022 Giải Tích Toán Học Tập 3 [NXB Đại Học Quốc Gia 2016] - Phạm Quang Trình, 104 Trang21/11/2016 Hàm Số Biến Số Phức [NXB Giáo Dục 2007] - Trương Văn Thương, 150 Trang26/11/2014 Phương Pháp Sai Phân [NXB Đại Học Quốc Gia 2004] - Lê Đình Thịnh, 220 Trang26/07/2014 Lượng Giác Và Ứng Dụng [NXB Đại Học Quốc Gia 2018] - Nguyễn Văn Mậu, 489 Trang15/05/2017 Tối Ưu Hóa Ứng Dụng [NXB Thống Kê 2009] - Phạm Trí Cao, 366 Trang15/11/2023 Toán Học Cao Cấp Tập 2 [NXB Giáo Dục 2006] - Nguyễn Đình Trí, 416 Trang19/03/2015 Giải Tích Toán Học Tập 3 [NXB Đại Học Quốc Gia 2013] - Phạm Quang Trình, 105 Trang13/10/2017 Hình Học Họa Hình Tập 1 [NXB Giáo Dục 2006] - Nguyễn Đình Điện, 187 Trang11/03/2022 Toán Học Cao Cấp Tập 1-Đại Số Và Hình Học Giải Tích [NXB Giáo Dục 2004] - Nguyễn Đình Trí, 391 Trang13/03/2022 Phương Pháp Số Phức Và Hình Học Phẳng [NXB Đại Học Quốc Gia 2000] - Nguyễn Hữu Điển, 184 Trang02/06/2013 Bài Tập Giải Tích Hàm [NXB Đại Học Quốc Gia 2004] - Nguyễn Văn Khuê, 147 Trang05/06/2017 Hướng Dẫn Giải Bài Tập Giải Tích Toán Học Tập 2 [NXB Đại Học Quốc Gia 2002] - Nguyễn Thủy Thanh14/01/2017

Share This Page

• Forums

  Forums

• Members

  Members

• Menu

Nhóm biên soạn và Giảng viên có đóng góp ý kiến: TS. Hoàng Lê Minh – Khưu Minh Cảnh – Lê Ngọc Thành – Phạm Trọng Nghĩa - Nguyễn Công Nhựt – Trần Ngọc Việt - Hoàng Thị Kiều Anh – Huỳnh Thái Học

TP – Năm 2019

MỤC LỤC

• BÀI 1: CƠ SỞ LOGIC VÀ TẬP HỢP
• 1. Các phép toán luận lý trong Python
  • 1. Luận lý trong Python
  • 1. Biểu thức điều kiện if
  • 1. Thứ tự tính toán trong Python
• 1. Dữ liệu dạng tập hợp trong Python: Set
• 1. Dữ liệu dạng tập hợp trong Sympy: FiniteSet.......................................................................................
  • 1. Xây dựng và các thao tác cơ bản trên tập hợp
    • 3.1. Xây dựng tập hợp
    • 3.1. Kiểm tra một số trong một tập hợp
    • 3.1. Tạo tập hợp rỗng.................................................................................................................
    • 3.1. Tạo tập hợp từ List hoặc Tuple
    • 3.1. Loại bỏ các phần tử trùng và sắp thứ tự tập hợp
  • 1. Tập con [subset], tập cha [superset] và tập các tập con [power set]
  • 1. Các phép toán trên tập hợp..........................................................................................................
    • 3.3. Union và Intersection
    • 3.3. Tích Descart – Cartesian Product
    • 3.3. Áp dụng công thức cho tập nhiều biến
    • 3.3. Ứng dụng: Tính toán xác suất sự kiện A và sự kiện B cùng xảy ra
• BÀI TẬP CHƯƠNG

elif [điều kiện 3...]: # khối lệnh xử lý điều kiện 3... else: # trường hợp còn lại # khối lệnh xử lý các trường hợp còn lại Việc sử dụng hiệu quả cấu trúc sẽ dẫn đến chương trình tinh gọn. Sinh viên thực hành lệnh dưới đây: >>> def kiemtra_nuocsoi[nhiet_do]: if nhiet_do < 100: return "Nuoc chua soi!" else: return "Nuoc da soi!" >>> kiemtra_nuocsoi[100] ...........................................................................  sinh viên ghi kết quả. >>> kiemtra_nuocsoi[99] ...........................................................................  sinh viên ghi kết quả. Sau đó, sinh viên thử một cách viết hàm tinh gọn như sau:

Và thực hiện các kiểm tra: >>> kiemtra_nuocsoi1[100] ...........................................................................  sinh viên ghi kết quả. >>> kiemtra_nuocsoi1[99] ...........................................................................  sinh viên ghi kết quả.

Hơn thế nữa, lệnh rẽ nhánh if được sử dụng trong “thiết kế” danh sách các giá trị. Sinh viên thực hiện các lệnh sau:

• Xây dựng danh sách gồm các phần tử thỏa điều kiện >5: >>> for diem_so in range[10]: if diem_so > 5: ds_dau[str[diem_so]]

  > ds_dau ..................................................................  sinh viên ghi kết quả. Và đoạn code ngắn gọn: >>> ds_dau = [str[diem_so] for value in range[10] if diem_so > 5] >>> ds_dau ..................................................................  sinh viên ghi kết quả.

1. Thứ tự tính toán trong Python

Bên cạnh đó, là một ngôn ngữ lập trình, các trình biên dịch Python thường xử lý phép toán từ trái sang phải [left-to-right order]. Theo đó, các biểu thức logic sẽ bị ảnh hưởng bởi thứ tự tính toán. Ví dụ: trong phép toán AND, nếu yếu tố đầu tiên không thỏa thì ngay lập tức biểu thức sẽ mang giá trị False [sai], nhầm giảm thiểu các tính toán không cần thiết; hoặc với phép toán OR, nếu biểu thức đầu tiên thỏa thì các biểu thức phía sau không cần tính toán. Sinh viên thực hành các lệnh sau để hiểu được thứ tự tính toán trong Python:

Kết quả câu lệnh if là: ............................................................................. Sinh viên thực hành đoạn lệnh khác:

.......................................  sinh viên ghi kết quả tại đây [gợi ý: True hoặc False]. Câu hỏi cho sinh viên: khoảng [-50, 50] có ý nghĩa gì trong lệnh trên? Thay thế khoảng khác được không? Lí do? Sinh viên trả lời: ............................................................................................

Ví dụ 3: Xây dựng tập các số nguyên tố nhỏ hơn 40. Theo định nghĩa, số nguyên tố là số chỉ chia hết cho 1 và chính nó. Do vậy, trong Python, chúng ta có thể xây dựng một hàm kiểm tra, trả về False nếu số không thỏa điều kiện định nghĩa số nguyên tố, ngược lại trả về True. >>> def isPrime[N]: for i in [ x+1 for x in range[N] ]: if N % i == 0 and [i!=1 and i!=N]: return False return True Và sau đó, chúng ta có thể xây dựng tập hợp các số nguyên tố: >>> S_prime = [isPrime[k] for k in range[1,40]] Kết quả là:

Sinh viên thực hành:

• Số 36 không phải là số nguyên tố nên S_prime[36] = True, ngược lại số S_prime[37] = False.
• Sinh viên hãy thay thế lệnh S_prime trên bằng cách viết theo set như sau:

  > S_prime = set[[x for x in range[40] if [isPrime[x] == True and x>0]]] >>> S_prime .................................................................................  Sinh viên điền kết quả.

Ví dụ 4: Tạo tập tích từ hai tập [set product]. Giả sử, chúng ta cần lấy 2 lần giá trị nghiệm, 20 lần giá trị nghiệm và 200 lần giá trị nghiệm của phương trình  +  − 6 = 0. Chúng ta có thể viết lệnh như sau: >>> Apro = set[[2*x *y for x in range[-50,50] if x**2+x-6 == 0 for y in [1, 10, 100]]] >>> Apro ................................................................................. sinh viên điền kết quả.

Ví dụ 5: Ý tưởng tương tự ví dụ 4 nhưng tập tích được tạo giữ hai nhóm giá trị từ 2 tập nguồn: >>> AB = set[[ [x, 2*y] for x in range[-50,50] if x**2+x-6 == 0 for y in [1, 10, 100]]] >>> AB ................................................................................. sinh viên điền kết quả.

1. Dữ liệu dạng tập hợp trong Sympy: FiniteSet Trong kí hiệu toán học, chúng ta thể hiện các phần tử của tập hợp nằm trong dấu {} [curly brackets]. Ví dụ : {3,5,7} là tập hợp thể hiện các phần của nó là: 3, 5, 7.

3. Xây dựng và các thao tác cơ bản trên tập hợp

3.1. Xây dựng tập hợp Để tạo tập hợp trong gói sympy của Python, chúng ta có thể sử dụng lớp FiniteSet từ gói sympy như sau: >>> from sympy import FiniteSet >>> s = FiniteSet[3, 5, 7] >>> s {3, 5, 7}

3.1. Tạo tập hợp rỗng Để tạo một tập rỗng [empty set], nghĩa là tập không có phần tử, chúng ta tạo đối tượng FiniteObject mà không cần đưa thông số vào. Lệnh như sau: >>> from sympy import FiniteSet >>> s = FiniteSet[] >>> s EmptySet[]

3.1. Tạo tập hợp từ List hoặc Tuple Trong Python, một tập hợp có thể được tạo từ một List hoặc một Tuple như sau: >>> phantu = [2, 4, 6, 8, 10] >>> tap = FiniteSet[*phantu] >>> tap {2, 4, 6, 8, 10} Ở đây, ta thấy: thay vì chuyển các danh sách phần tử trực tiếp vào tham số FiniteSet thì chúng ta có thể lưu trữ chúng trong một danh sách phantu [kiểu list]. Sau đó, chúng ta có thể chuyển danh sách này vào trong FiniteSet bằng cú pháp Python đặc biệt như trên. Bằng phương pháp này, chúng ta sẽ sử dụng uyển chuyển khi viết các chương trình khi các phần tử của tập hợp được tính toán trong chương trình. 3.1. Loại bỏ các phần tử trùng và sắp thứ tự tập hợp Kiểu tập hợp trong Python [như tập hợp trong toán học] sẽ loại bỏ những phần tử trùng và không quan tâm đến thứ tự của phần tử trong tập hợp [nghĩa là tập hợp có thể sắp xếp lại, không giữ thứ tự ban đầu]. Ví dụ: khi chúng ta tạo 1 tập từ list có nhiều phần tử giống nhau, khi đó, các số được thêm vào trong tập hợp chỉ đúng 1 lần. Xét ví dụ sau: >>> from sympy import FiniteSet >>> phantu = [6, 7, 8, 9, 6, 7]

> taphop = FiniteSet[*phantu] >>> taphop {6, 7, 8, 9}

Rõ ràng danh sách ban đầu có 2 phần tử 6 và 7 có trùng nhau. Tuy nhiên, khi chúng ta đưa vào tập hợp thì chúng sẽ được loại bỏ một cách tự động. Lưu ý: Trong Python, hai kiểu danh sách list và tuple sẽ lưu trữ mỗi phần tử theo thứ tự của mỗi phần tử. Tuy nhiên, với kiểu tập hợp thì điều đó không còn đúng nữa. Xét chương trình in dữ liệu từ tập trên: >>> from sympy import FiniteSet >>> phantu = [6, 7, 8, 9, 6, 7] >>> taphop = FiniteSet[*phantu] >>> taphop {6, 7, 8, 9} >>> for thanhphan in taphop: print[thanhphan] ........................................................  sinh viên điền vào kết quả Thực hiện đoạn lệnh lặp in nhiều lần chúng ta sẽ thấy thứ tự các phần tử xuất ra không là vấn đề. Khi đó, chúng ta sẽ có khái niệm là so sánh hai tập hợp. Hai tập hợp bằng nhau theo toán học khi chúng cùng phần tử. Trong Python, chúng ta có thể sử dụng phép toán == để so sánh hai tập hợp bằng nhau: >>> from sympy import FiniteSet >>> ds1 = [2, 4, 6] >>> ds2 = [6, 2, 4] >>> ds1 == ds ..................................................  sinh viên điền kết quả >>> s = FiniteSet[*ds1] >>> t = FiniteSet[*ds2] >>> s == t ..................................................  sinh viên điền kết quả Kết quả cho thấy thứ tự của các phần tử không ảnh hưởng đến tập hợp.

> len[ps] ..................................................  sinh viên điền kết quả >>> ps ..................................................  sinh viên điền kết quả

Bên cạnh đó, theo định nghĩa toán học, một tập vừa là tập con và vừa là tập cha của chính nó. Bên cạnh đó, phép so sánh tập cha “ngặt” hoặc tập con “ngặt” để đảm bảo số phần từ tập cha luôn lớn hơn số phần tử tập con. Ví dụ: tập s = {1,2,3} sẽ là tập cha “ngặt” của các tập như {1}, {2,3}, {1,3} và ngược lại, các tập như {1}, {2,3}, {1,3} có số phần tử ít hơn tập cha {1,2,3}. Quan hệ đó được thể hiện trong kiểu dữ liệu FiniteSet qua 2 lệnh kiểm tra về tập con “ngặt” và tập cha “ngặt” lần lượt là: is_proper_subset[] và is_proper_superset[]. Ví dụ: >>> from sympy import FiniteSet >>> s = FiniteSet[1, 2, 3] >>> t = FiniteSet[3, 2, 1] >>> s_proper_subset[t] ..................................................  sinh viên điền kết quả >>> t_proper_powerset[s] ..................................................  sinh viên điền kết quả >>> t = FiniteSet[3, 2, 1, 4] >>> s_proper_subset[t] ..................................................  sinh viên điền kết quả >>> t_proper_ powerset [s] ..................................................  sinh viên điền kết quả

3. Các phép toán trên tập hợp..........................................................................................................

Các phép toán tập hợp như hợp, giao và tích Cartesian cho phép tổ hợp các tập hợp trong một số phương cách nhất định. Những phép tính tập hợp này đều hữu dụng trên thế giới thực để giải các

bài toán khi chúng ta cần xử lý nhiều tập hợp với nhau. Ngoài ra, những phép tính này chính là tiền đề để tính toán dữ liệu và xác suất các sự kiện ngẫu nhiên. 3.3. Union và Intersection Union của 2 tập hợp là phép nối/hợp của 2 tập chứa các phần tử khác nhau trong 2 tập. Trong lý thuyết tập hợp được kí hiệu bằng ∪. Ví dụ: {1,2} ∪ {2,3} = {1,2,3}. Trong Sympy, phép hợp được hiện thực bằng phương thức union[]: >>> from sympy import FiniteSet >>> s = FiniteSet[2, 4, 6] >>> t = FiniteSet[3, 5, 7] >>> kq = s[t] >>> kq {2, 3, 4, 5, 6, 7} Như vậy, bên trên, chúng ta tìm hợp của 2 tập s và t bằng phương thức union. Kết quả trả về là tập thứ 3 có tên là kq. Ở đây, mỗi phần tử của tập kq là một phần tử của một hoặc hai tập đầu tiên. Ngoài ra, chúng ta có thể xử dụng phép toán + để hợp nối 2 tập hợp. >>> from sympy import FiniteSet >>> u = FiniteSet[10, 20, 50] >>> v = FiniteSet[1, 2, 5] >>> u + v {1, 2, 5, 10, 20, 50}

Phép toán giao [intersection] của hai tập là việc tạo lập 1 tập mới từ các phần tử chung của 2 tập. Ví dụ: giao giữa 2 tập {1, 2, 10} và {1, 3, 10} sẽ được kết quả là tâp mới gồm những phần tử chung, nghĩa là tập mới sẽ là {1, 10}. Về mặt toán học, chúng ta viết như sau {1,2,10} ∩ {1,3,10} = {1,10} Trong SymPy, lệnh intersect[] để tìm tập giao: >>> from sympy import FiniteSet >>> s = FiniteSet[1, 2, 10]

EmptySet[]

3.3. Tích Descart – Cartesian Product Tích Descart của tập hữu dụng để tìm tất cả các tổ hợp của các phần tử trong tập hợp. Bằng cách sử dụng tích của tập với chính nó [có thể sử dụng phép toán nhân * hoặc lũy thừa **], chúng ta sẽ tìm được các tổ hợp trong tập hợp, cụ thể là các chỉnh hợp. Ví dụ: >>> from sympy import FiniteSet >>> v = FiniteSet[1, 2, 5] >>> p = v ** 2 >>> p {1, 2, 5} x {1, 2, 5} >>> for phantu in p: print[phantu] .................. .................. .................. .... ..................  sinh viên liệt kê ra

3.3. Áp dụng công thức cho tập nhiều biến Để xử lý từng phần tử trong một tập FiniteSet, chúng ta có thể sử dụng lệnh lặp for như sau: >>> from sympy import FiniteSet >>> K = FiniteSet[35, 18, 27, 29, 24] >>> for k in K: T = k/10. print [T, k]

..................  sinh viên liệt kê ra Thứ tự của các số được sắp xếp tăng dần.

3.3. Ứng dụng: Tính toán xác suất sự kiện A và sự kiện B cùng xảy ra Khi chúng ta có 2 sự kiện và chúng ta muốn tính toán xác suất xảy ra 2 sự kiện cùng lúc. Ví dụ: cơ hội cho chúng ta lựa chọn vừa là số nguyên tố vừa là số lẻ [như khi chọn biển số xe]. Để tính toán được, chúng ta cần xác định xác suất của sự kiện giao giữa 2 sự kiện:  =  ∩  = {2, 3, 5, 7} ∩ {1, 3, 5, 7, 9} = {3, 5, 7} Chúng ta tính toán xác suất của sự kiện cho cả A và B xảy ra cùng lúc bằng phương thức intersect[]. Cụ thể: >>> from sympy import FiniteSet >>> s = FiniteSet[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # cac so co the trong bien so >>> a = FiniteSet[2, 3, 5, 7] # cac so nguyen to >>> b = FiniteSet[1, 3, 5, 7, 9] # cac so le >>> e = a[b] >>> len[e]/len[s] 0. Như vậy, xác suất để 1 số là số nguyên tố lẻ được chọn từ 10 số từ 0 đến 9 là 0, nghĩa là 33%. Thông tin thêm: Ứng dụng trong y tế cộng đồng: Bài toán trên tuy đơn giản nhưng thường được áp dụng khi tìm kiếm các ca nghi bệnh với tập hợp là những người xuất hiện trong các khu thương mại nơi có bệnh nhân. Để có được tập hợp, người ta sử dụng công nghệ dò sóng điện thoại như GMS/3G/4G/..., để định vị trí người mang theo điện thoai. Và sau đó xử lý để thông báo về y tế của địa phương người cư ngụ.

Bài 4: Thực hiện bằng kiểu set các tập hợp sau: a. Cho tập hợp A với x là biến số nguyên như sau:  = {| + 4 + 4 = 0} !"ế$ đ&

039;ạ ]*"+$ ,ằ. /0$ℎ&

039; " *2 $ấ$ ]ả ]á] ."á $ị  $ℎỏ2 đ"ề9 :"ệ ]ủ2 $ậ+ . b. Cho tập hợp A với n là biến số nguyên như sau:  = {?ớ" Aọ"  |  + 4 < 100} !"ế$ đ&

039;ạ ]"+$ ,ằ. /0$ℎ&

039; " *2 $ấ$ ]ả ]á] ."á $*ị  $ℎỏ2 đ"ề9 :"ệ ]ủ2 $ậ+ .

Bài 5: Sử dụng biểu đồ Venn để thể hiện 2 tập hợp Biểu đồ Venn [Venn diagram] là phương pháp đơn giản để thấy được quan hệ giữa tập hợp. Nó cho chúng ta thấy có bao nhiêu phần tử chung giữa hai tập hợp, bao nhiêu phần tử trong một tập hợp và bao nhiêu phần tử không có trong tập hợp. Ví dụ: Xét tập A gồm các số dương lẻ [posotive odd] nhỏ hơn 20, nghĩa là A = {1, 3, 5, 7 ,9 ,11, 13, 15, 17, 19} và xét tập B là những số nguyên tố [prime] nhỏ hơn 20, nghĩa là B = {2, 3, 5, 7, 11, 13, 17, 19}. Chúng ta có thể vẽ biểu đồ Venn bằng Python với các lệnh như sau:

Sau khi chúng ta import các module và hàm cần thiết [như là venn2[], matplotlib và FiniteSet], tất cả việc còn lại là tạo 2 tập và gọi hàm venn2 cho tập hợp ghép: >>> s3 = [s1, s2] >>> s [{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}, {2, 3, 5, 7, 11, 13, 17, 19}] Với tập ghép, chúng ta sẽ vẽ được biểu đồ Venn và biểu đồ Venn cho ta kết quả:

• Tập A có 3 phần tử riêng.
• Tập B có 1 phần tử riêng.
• Tập A và B có 7 phần tử chung. Để rõ hơn, chúng ta có thể đặt tên các tập hợp bằng cách điều chỉnh hàm vẽ biểu đồ Venn như sau: >>> def draw_venn[sets]: venn2[subsets=sets, set_labels=[&

  039;Tap S1&

  039;, &

  039;Tap S2&

  039;] ] plt[] Và sau đó thực hiện lại lệnh vẽ: >>> draw_venn[[s1, s2]]

Biểu đồ Venn thể hiện quan hệ giữa 2 tập hợp A và B Điều kiện: Sinh viên cài đặt hoàn tất gói matplotlib_venn

Sinh viên đọc thêm bài dưới đây để làm các bài tập: Bài tập 6, Bài tập 7 và Bài tập 8:  Ứng dụng: Nền tảng của công nghệ RAID khôi phục dữ liệu Sinh viên đọc và tìm hiểu về phương pháp sử dụng XOR trong khôi phục dữ liệu khi đĩa cứng chứa dữ liệu bị hư trên hệ thống máy chủ nhiều đĩa cứng. Bài toán thực tiễn Hư hỏng đĩa cứng dẫn đến mất mát dữ liệu là vấn đề xảy ra thường xuyên đối với người sử dụng máy tính. Để khắc phục tình trạng trên, các hệ thống server hỗ trợ công nghệ có tính năng đặc