Toán học rời rạc cho Khoa học máy tính – w3seo computer science cần gì

Rate this post

Toán học rời rạc được sử dụng để cung cấp kiến ​​thức tốt về mọi lĩnh vực của khoa học máy tính. Trong khoa học máy tính, các ứng dụng của toán học rời rạc rất rộng lớn và được mô tả như sau:

Đại số Boolean

Các bit như một hoặc số không được sử dụng để đại diện cho tất cả dữ liệu của máy tính ở mức cơ bản nhất. Máy tính thực hiện các phép tính khi chúng thực hiện một số sửa đổi trong các bit này theo luật đại số Boolean, được sử dụng để tạo thành tất cả các mạch kỹ thuật số. Đồ thị dùng để biểu diễn mạch số đó.

Các bài viết liên quan:

Các toán tử logic như ‘và’, ‘hoặc’, và ‘không’ được sử dụng để phát triển các ngôn ngữ lập trình cấp thấp. Khi các nhà phát triển phần mềm phát triển bất kỳ dự án nào, họ chủ yếu thích các ngôn ngữ cấp cao. Đôi khi họ muốn tối ưu hóa mã của mình bằng cách giảm các hoạt động cấp thấp, và đôi khi, họ cũng trực tiếp hoạt động trên các bit. Người lập trình cũng có thể kiểm soát luồng chương trình bằng cách sử dụng logic Boolean. Điều đó có nghĩa là họ có thể xác định các điều kiện nhất định và sau đó kiểm soát các lệnh nào sẽ được thực thi.

Đại số Boolean có nhiều luật khác nhau, được mô tả như sau:

Luật thay thế:

Theo luật giao hoán, nếu ta thay đổi dãy biến cũng không ảnh hưởng đến kết quả. Một phép toán sẽ được gọi là phép toán giao hoán nếu nó chứa biểu thức sau:

1. A.B = B.A

2. A + B = B + A

Luật kết hợp:

Theo luật kết hợp, nếu chúng ta sắp xếp lại dấu ngoặc của bất kỳ biểu thức nhị phân nào, nó sẽ không làm thay đổi kết quả của mạch logic. Một phép toán nhị phân sẽ được gọi là một phép toán kết hợp nếu nó chứa biểu thức sau:

1. (A.B) .C = A. (B.C)

2. (A + B) + C = A + (B + C)

Luật phân phối:

Theo luật phân phối, nếu chúng ta nhân một số với nhóm các số cộng lại với nhau sẽ có kết quả như nhau nếu chúng ta thực hiện từng phép nhân riêng biệt. Một hoạt động sẽ được gọi là phân phối nếu nó chứa biểu thức sau:

A. (B + C) = A.B + A.C

Luật VÀ:

Nếu hoạt động nhị phân sử dụng AND, nó sẽ được gọi là luật AND, được mô tả như sau:

1. A.0 = 0

2. A.1 = A

3. A.A = A

4. A.Ā = 0

Luật HOẶC:

Nếu hoạt động nhị phân sử dụng OR, nó sẽ được gọi là luật OR, được mô tả như sau:

1. A + 0 = A

2. A + 1 = 1

3. A + A = A

4. A + Ā = 1

Luật nghịch đảo:

Theo luật nghịch đảo, nếu chúng ta thực hiện đảo đôi bất kỳ biến nào, nó sẽ được xuất ra chính biến ban đầu. Luật này sử dụng phép toán Không. Một phép toán sẽ được gọi là nghịch đảo nếu nó chứa biểu thức sau:

A + Ā + = 1

Đại số Boolean cũng có định lý De morgan, có hai định luật:

Định luật đầu tiên của De morgan

Theo luật thứ nhất, phần bù của tích của các biến và tổng của các phần bù của biến riêng lẻ của chúng bằng nhau, được mô tả như sau:

 (A.B) = A + B

Định luật thứ hai của De morgan

Theo định luật thứ hai, phần bù của tổng các biến và tích của các phần bù biến riêng lẻ của chúng bằng nhau, được mô tả như sau:

(A + B) = A.B

Ví dụ về Đại số Boolean

Trong ví dụ này, chúng ta sẽ giải biểu thức C + BC.

Chúng ta có thể viết biểu thức trên như sau trên cơ sở định luật Demorgan:

C + (B + C)

Bây giờ chúng ta sẽ sử dụng luật giao hoán như sau:

(C + C) + B

Sau đó, chúng ta sẽ sử dụng luật bổ sung như sau:

1 + B = 1

Vì vậy,

C + BC = 1

Xác suất

Xác suất được sử dụng trong lĩnh vực định lượng cũng như trong khoa học máy tính. Xác suất được sử dụng trong kỹ thuật phần mềm để đánh giá lượng rủi ro. Ví dụ, giả sử chúng ta đang thiết kế một hệ thống và chúng ta đang sử dụng xác suất. Trong trường hợp này, xác suất sẽ cho biết về dung lượng của hệ thống có nghĩa là hệ thống của chúng tôi có thể xử lý bao nhiêu tải và sau mức tải cao nhất đó, hệ thống sẽ gặp sự cố. Chúng tôi cũng có thể đo độ tin cậy của mạng bằng cách sử dụng xác suất. Trong học máy, chúng tôi có thể thực hiện các nhiệm vụ từ phát triển điều trị y tế tốt đến hiệu chỉnh bộ lọc thư rác bằng cách sử dụng các ứng dụng xác suất có điều kiện khác nhau.

Thuật toán ngẫu nhiên được biết đến là thuật toán hiệu quả hơn và tốt nhất khi áp dụng vào thực tế vì chúng cung cấp khả năng tính toán chính xác của những tác vụ khó tính toán đó. Xác suất có thể được mô tả là một trong những nền tảng của khoa học dữ liệu cũng như thống kê. Nó cũng được biết đến là một trong những lĩnh vực hot nhất trong ngành. Nếu sinh viên đang nghiên cứu xác suất trên cơ sở khoa học máy tính, nó sẽ cung cấp cho họ một trực giác định lượng, và nó hữu ích trong cuộc sống hàng ngày và trong suốt sự nghiệp của họ. Chúng tôi có công thức để xác định xác suất,

Xác suất sự kiện xảy ra P (E) = Số lượng kết quả thuận lợi / Tổng số kết quả

Ví dụ về xác suất

Giả sử trong một cửa hàng có 6 bộ quần áo, trong đó 3 bộ màu xanh lá cây, 2 bộ màu tím và 1 bộ quần áo màu cam. Chúng ta sẽ tìm xác suất để chọn được một bộ đồ màu cam.

Xác suất sẽ được tính bằng cách chia số bộ quần áo màu cam trong một cửa hàng cho tổng số bộ quần áo. Cho nên

2/6 = 1/3

Logic mệnh đề

Khi một nhà phát triển phát triển bất kỳ dự án nào, điều quan trọng là anh ta phải tự tin nhận được kết quả mong muốn bằng cách chạy mã của họ. Chúng ta có thể sử dụng toán học để mô tả các chương trình. Lý do cho sự đúng đắn của chúng là các công cụ logic mệnh đề. Lĩnh vực cốt lõi của khoa học máy tính được gọi là thuật toán, và rất khó để phân tích và thiết kế một thuật toán bằng cách sử dụng những kỹ năng quan trọng này. Nguyên tắc quy nạp toán học được sử dụng bởi hai mô hình chính: lập trình hàm và lập trình lặp. Nguyên tắc này được sử dụng để xác minh các vòng lặp và các lệnh gọi hàm đệ quy của chúng một cách riêng biệt.

Ngôn ngữ đặc tả chính thức nhất có thể được gọi là Logic được sử dụng trong nền tảng và thiết kế của ngôn ngữ lập trình. Ví dụ, các ngôn ngữ trong họ SQL chỉ là việc triển khai logic quan hệ, có một số tính năng được bổ sung. Một số phép tính logic cụ thể và nhiều ngôn ngữ miền cụ thể có cùng cách triển khai. Trong ngành, ngày càng có nhiều việc áp dụng các phương pháp chính thức và xác minh chương trình. Nó cũng được sử dụng song song với các kỹ thuật kiểm thử truyền thống để tăng độ tin cậy về hiệu suất và hiệu quả của phần mềm.

Ví dụ về logic mệnh đề:

3 + 3 = 5

Narendra Modi là Thủ tướng.

‘a’ là một nguyên âm.

Ví dụ này có ba câu là mệnh đề. Trong đó câu đầu tiên là Sai hoặc không hợp lệ và hai câu cuối là Đúng hoặc Hợp lệ.

Một số ví dụ không phải là mệnh đề, được mô tả như sau:

1 + a = 5

Đi nghỉ và tận hưởng

Ví dụ này có hai câu không phải là mệnh đề vì câu đầu tiên có thể sai hoặc đúng vì giá trị của ‘a’ không được chỉ định, vì vậy chúng ta không thể nói rằng nó đúng hay sai trừ khi chúng ta chỉ định giá trị và câu cuối cùng. không có giá trị sự thật.

Quy nạp và đệ quy

Nếu chúng ta muốn biết mô hình chức năng của lập trình, các khái niệm chính sẽ được sử dụng là quy nạp và đệ quy. Đệ quy là một loại chiến lược lập trình, được sử dụng để giải các bài toán lớn. Chúng ta sẽ chia bài toán lớn thành các bài toán nhỏ hơn cùng loại. Trong khi quy nạp là một loại chiến lược toán học, được sử dụng để chứng minh các tuyên bố liên quan đến các tập hợp lớn của sự vật.

Nhiều ngành và công ty như Facebook (Haskell), Amazon, Microsoft nghiên cứu (F *, Haskell), Apple (Swift), Oracle (JavaScript, Java 8) và Microsoft (F #) tăng cường áp dụng mô hình chức năng cho việc sử dụng chung và nhiệm vụ thích hợp. Cấu trúc dữ liệu và thuật toán cũng có thể được mô tả dễ dàng bằng Recurrences. Trong lĩnh vực lý thuyết của khoa học máy tính và nhiều mô hình tính toán, chúng được coi như một xương sống. Phần quan trọng hơn, đặc biệt là trong ứng dụng nhạy cảm, là các thuộc tính bảo mật của phần mềm và tính đúng đắn.

Ví dụ :

Sử dụng quy nạp toán học, hãy chỉ ra n <2n với mọi số nguyên dương n.

Chúng ta sẽ giả sử rằng mệnh đề của n là P (n): n <2n

Bước cơ bản: P (1) đúng vì 1 <21

Bước quy nạp: Nếu P (n) đúng thì với mỗi n P (n + 1) là đúng.

Chúng ta sẽ giả sử rằng P (n): n <2n là đúng

Khi đó chúng ta sẽ chỉ ra P (n + 1): n + 1 <2n + 1 là true.

n + 1 <2n + 1

<2n + 2n

= 2n (1 + 1)

 = 2n (2)

= 2n + 1

Ví dụ về đệ quy:

Ví dụ 1:

Chúng tôi sẽ mô tả ví dụ về hàm được định nghĩa đệ quy:

f (0) = 5

f (n) = f (n-1) + 2

Chúng tôi sẽ tính toán giá trị của hàm như sau:

f (0) = 5

f (1) = f (0) + 2 = 5 + 2 = 7

f (2) = f (1) + 2 = 7 + 2 = 9

f (3) = f (2) + 2 = 9 + 2 = 11

Hàm được định nghĩa đệ quy này tương đương với một hàm được xác định rõ ràng, được mô tả như sau:

f (n) = 2n + 5

Ví dụ 2:

Chúng tôi sẽ mô tả ví dụ về hàm được định nghĩa đệ quy:

f (0) = 0

f (n) = f (n-1) + 2n-1

Chúng tôi sẽ tính toán giá trị của hàm như sau:

f (0) = 0

f (1) = f (0) + (2) (1) -1 = 0 + 2 – 1 = 1

f (2) = f (1) + (2) (2) -1 = 1 + 4 – 1 = 4

f (3) = f (2) + (2) (3) -1 = 4 + 6 -1 = 9

f (4) = f (3) + (2) (4) -1 = 9 + 8 -1 = 16

Hàm được định nghĩa đệ quy này tương đương với một hàm được xác định rõ ràng, được mô tả như sau:

f (n) = n2

Lý thuyết số

Trong lý thuyết số, chúng ta sẽ tìm hiểu về các tập hợp các số nguyên dương có thể là 1, 2, 3, 4, 5, 6, … Chúng còn được gọi là tập hợp các số tự nhiên. Trong lý thuyết số, trọng tâm chính của chúng tôi là tìm hiểu mối quan hệ giữa các loại số khác nhau. Trong lĩnh vực bảo mật máy tính, mật mã và blockchain, các ứng dụng quan trọng được chứa trong lý thuyết Số. Theo toán học, dữ liệu của người dùng được bảo mật hoàn hảo khỏi các loại tấn công và kẻ thù nguy hiểm với sự trợ giúp của một hệ thống mật mã hiện đại.

Cơ sở toán học cho phép băm được mô tả bằng số học mô-đun và nó là công cụ hữu ích nhất cho một số ứng dụng. Các tệp được truyền qua internet được Checksum xác minh và nó dựa trên băm. Cấu trúc dữ liệu như bản đồ băm thực hiện các hoạt động hiệu quả bằng cách sử dụng số học mô-đun. Trong hệ điều hành và máy tính a

kiến trúc, lý thuyết số cũng cung cấp cơ sở để sử dụng những thứ liên quan đến bộ nhớ. Có rất nhiều ví dụ quen thuộc và không quen thuộc về lý thuyết số, được mô tả như sau:

Chẵn: 2, 4, 6, 8, 10, 12? ..

Lẻ: 1, 3, 5, 7, 9 ??

Hình tam giác: 1, 3, 6, 10, 15, 21? ..

Số nguyên tố: 2, 3, 5, 7, 11, 13, 17 ??

Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21? ..

Hình vuông: 1, 4, 9, 16, 25?.

Khối lập phương: 1, 8, 27, 64 ??.

Hoàn hảo: 6, 28, 496 ?.

Đếm

Chúng ta cũng có thể phát triển trực giác định lượng bằng cách sử dụng các kỹ thuật Đếm. Ví dụ: giả sử người dùng tạo mật khẩu bằng cách sử dụng một số bộ quy tắc đã xác định. Bây giờ chúng ta có thể lấy số lượng mật khẩu hợp lệ bằng cách sử dụng kỹ thuật đếm. Kỹ thuật này cũng được sử dụng để xác định khoảng thời gian kẻ tấn công thực hiện để cưỡng bức tất cả các mật khẩu. Bây giờ chúng ta sẽ tìm hiểu nguyên lý chuồng chim bồ câu, mô tả lý do tại sao chúng ta không có một thuật toán có thể mô tả nén không mất dữ liệu phổ quát. Khi chúng tôi sử dụng thuật toán nén, nó sẽ giảm một số tệp nhất định mỗi lần và tăng số lượng tệp khác. Các loại tệp khác nhau, chẳng hạn như video, âm thanh, văn bản, hình ảnh, v.v., có thể được nén bằng cách sử dụng từng thuật toán nén. Độ phức tạp của thuật toán có thể được xác định dễ dàng với sự trợ giúp của việc đếm.

Ứng dụng trong thế giới thực có rất nhiều tài nguyên có sẵn khác nhau nên có một sự cân bằng phức tạp. Một số tác vụ không có nhiều dung lượng, đó là lý do tại sao chúng phải hy sinh thời gian của mình để có thêm dung lượng, trong khi những tác vụ khác yêu cầu thuật toán nhanh vì chúng có thể dành không gian lớn để đạt được tốc độ. Trong một tình huống phức tạp, chúng tôi yêu cầu phải đạt được điểm tốt trong việc sử dụng tài nguyên để hệ thống không phải đối mặt với vấn đề liên quan đến tình trạng thiếu tài nguyên và tiếp tục chạy hoàn hảo. Sử dụng phép đếm, chúng ta có thể tạo ra những cân nhắc này theo cách cấu trúc. Nó cũng có thể cung cấp một đảm bảo chính thức liên quan đến việc sử dụng tài nguyên.

Ví dụ về đếm

Ví dụ 1:

Trong ví dụ này, chúng ta sẽ tính xem có bao nhiêu số có 3 chữ số có thể được tạo thành từ các chữ số 2, 3, 4, 5 7 và 9.

Lời giải: Như chúng ta thấy rằng có 6 chữ số có sẵn. Cho nên

(6) (6) (6) = 216

Ví dụ 2:

Giả sử Jack đi đến một cửa hàng bánh pizza và chọn tạo ra một chiếc bánh pizza của riêng mình. Quán có 4 loại nước sốt, 4 loại bánh mì và 3 loại phô mai khác nhau, nhưng anh chỉ chọn được một loại trong mỗi loại. Bây giờ chúng ta phải tìm ra rằng có bao nhiêu cách khác nhau để tạo ra một chiếc bánh pizza.

(4) (4) (3) = 48

Đồ thị

Một Đồ thị có thể được mô tả như một biểu diễn bằng hình ảnh của tập hợp các đối tượng trong đó các liên kết được sử dụng để kết nối một số cặp đối tượng. Nó là một nhóm các đỉnh và các cạnh. Trong đó các đỉnh được sử dụng để biểu diễn các đối tượng được kết nối với nhau, được ký hiệu là V. Các cạnh là một loại liên kết, được sử dụng để kết nối các đỉnh và nó được ký hiệu là E.

Biểu đồ có khả năng trả lời câu hỏi và mô hình hóa mối quan hệ. Ví dụ: khi chúng tôi sử dụng ứng dụng điều hướng để tìm kiếm tuyến đường nhanh nhất từ ​​văn phòng đến nhà của chúng tôi, ứng dụng này sử dụng thuật toán tìm kiếm đồ thị để tìm kiếm tuyến đường đó. Nó cũng sẽ hiển thị cho chúng tôi thời gian tùy theo xe của chúng tôi. Biểu đồ được sử dụng rộng rãi trong khoa học máy tính để biểu diễn một hệ thống tệp. Nó cũng được sử dụng trong cơ sở dữ liệu, học sâu, lập trình chức năng và các ứng dụng khác.

Ví dụ về Đồ thị:

Ví dụ 1: Giả sử có một cặp tập hợp (V, E), trong đó V được dùng để chứa tập các đỉnh và E là tập các cạnh, được dùng để nối các cặp đỉnh. Bây giờ chúng ta sẽ xem xét đồ thị sau và tìm số đỉnh và số cạnh.

Toán học rời rạc cho Khoa học máy tính

Trong biểu đồ này,

V = {u, v, w, x, y}

E = {uv, uw, vx, wx, xy}

Ví dụ 2: Ta phải tìm các đỉnh và các cạnh của các đồ thị sau.

Toán học rời rạc cho Khoa học máy tính

Trong biểu đồ này,

V = {5, 6, 7, 8, 9}

E = {56, 67, 78, 89, 59, 69, 68}