TOÁN RỜI RẠC
CHƯƠNG I: THUẬT TOÁN
1.1. KHÁI NIỆM THUẬT TOÁN.
1.1.1. Mở đầu:
Có nhiều lớp bài toán tổng quát xuất hiện trong toán học rời rạc. Chẳng hạn, cho một dãy các số nguyên, tìm số lớn nhất; cho một tập hợp, liệt kê các tập con của nó; cho tập hợp các số nguyên, xếp chúng theo thứ tự tăng dần; cho một mạng, tìm đường đi ngắn nhất giữa hai đỉnh của nó. Khi được giao cho một bài toán như vậy thì việc đầu tiên phải làm là xây dựng một mô hình dịch bài toán đó thành ngữ cảnh toán học. Các cấu trúc rời rạc được dùng trong các mô hình này là tập hợp, dãy, hàm, hoán vị, quan hệ, cùng với các cấu trúc khác như đồ thị, cây, mạng - những khái niệm sẽ được nghiên cứu ở các chương sau.
Lập được một mô hình toán học thích hợp chỉ là một phần của quá trình giải. Để hoàn tất quá trình giải, còn cần phải có một phương pháp dùng mô hình để giải bài toán tổng quát. Nói một cách lý tưởng, cái được đòi hỏi là một thủ tục, đó là dãy các bước dẫn tới đáp số mong muốn. Một dãy các bước như vậy, được gọi là một thuật toán.
Khi thiết kế và cài đặt một phần mềm tin học cho một vấn đề nào đó, ta cần phải đưa ra phương pháp giải quyết mà thực chất đó là thuật toán giải quyết vấn đề này. Rõ ràng rằng, nếu không tìm được một phương pháp giải quyết thì không thể lập trình được. Chính vì thế, thuật toán là khái niệm nền tảng của hầu hết các lĩnh vực của tin học.
1.1.2. Định nghĩa:
Thuật toán là một bảng liệt kê các chỉ dẫn [hay quy tắc] cần thực hiện theo từng bước xác định nhằm giải một bài toán đã cho.
Thuật ngữ “Algorithm” [thuật toán] là xuất phát từ tên nhà toán học Ả Rập Al-Khowarizmi. Ban đầu, từ algorism được dùng để chỉ các quy tắc thực hiện các phép tính số học trên các số thập phân. Sau đó, algorism chuyển thành algorithm vào thế kỷ 19. Với sự quan tâm ngày càng tăng đối với các máy tính, khái niệm thuật toán đã được cho một ý nghĩa chung hơn, bao hàm cả các thủ tục xác định để giải các bài toán, chứ không phải chỉ là thủ tục để thực hiện các phép tính số học.
Có nhiều cách trình bày thuật toán: dùng ngôn ngữ tự nhiên, ngôn ngữ lưu đồ [sơ đồ khối], ngôn ngữ lập trình. Tuy nhiên, một khi dùng ngôn ngữ lập trình thì chỉ những lệnh được phép trong ngôn ngữ đó mới có thể dùng được và điều này thường làm cho sự mô tả các thuật toán trở nên rối rắm và khó hiểu. Hơn nữa, vì nhiều ngôn ngữ lập trình đều được dùng rộng rãi, nên chọn một ngôn ngữ đặc biệt nào đó là điều người ta không muốn. Vì vậy ở đây các thuật toán ngoài việc được trình bày bằng ngôn ngữ tự nhiên cùng với những ký hiệu toán học quen thuộc còn dùng một dạng giả mã để mô tả thuật toán. Giả mã tạo ra bước trung gian giữa sự mô tả một thuật toán bằng ngôn ngữ thông thường và sự thực hiện thuật toán đó trong ngôn ngữ lập trình. Các bước của thuật toán được chỉ rõ bằng cách dùng các lệnh giống như trong các ngôn ngữ lập trình.
Toán học rời rạc [tiếng Anh: discrete mathematics] là tên chung của nhiều ngành toán học có đối tượng nghiên cứu là các tập hợp rời rạc, các ngành này được tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở toán học của khoa học máy tính. Nó còn được gọi là toán học dành cho máy tính. Người ta thường kể đến trong toán học rời rạc lý thuyết tổ hợp, lý thuyết đồ thị, lý thuyết độ phức tạp, đại số Boole.
Một quan điểm rộng rãi hơn, gộp tất cả các ngành toán học làm việc với các tập hữu hạn hoặc đếm được vào toán học rời rạc như số học modulo m, lý thuyết nhóm hữu hạn, lý thuyết mật mã, …
Lý thuyết tổ hợpLý thuyết tính toánMật mã họcLý thuyết đồ thịShare this:
Thích bài này:
Thích Đang tải...
Có liên quan
Ziegler được biết đến nhờ công trình nghiên cứu trong lĩnh vực toán rời rạc và hình học, đặc biệt là combinatorics of polytopes.
Ziegler is known for his research in discrete mathematics and geometry, and particularly on the combinatorics of polytopes.
WikiMatrix
Bởi vì vấn đề logarit rời rạc làm rút gọn phép ước lượng tổng Gauss nên một thuật toán cổ điển hiệu quả về việc ước lượng các tổng Gauss sẽ bao hàm một thuật toán cổ điển hiệu quả về tính toán logarit rời rạc, điều mà không chắc có được.
Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which is considered unlikely.
WikiMatrix
Các vấn đề tương tự cũng được áp dụng cho các hệ mã hóa khác bao gồm trao đổi khóa Diffie–Hellman và các hệ tương đương có độ an toàn phụ thuộc vào độ khó của bài toán Lôgarit rời rạc hơn là việc phân tích thừa số số nguyên.
Similar issues apply in other cryptosystems as well, including Diffie–Hellman key exchange and similar systems that depend on the security of the discrete log problem rather than on integer factorization.
WikiMatrix
Trong toán học, một xích Markov hay chuỗi Markov [thời gian rời rạc], đặt theo tên nhà toán học người Nga Andrei Andreyevich Markov, là một quá trình ngẫu nhiên thời gian rời rạc với tính chất Markov.
In probability theory and related fields, a Markov process, named after the Russian mathematician Andrey Markov, is a stochastic process that satisfies the Markov property [sometimes characterized as "memorylessness"].
WikiMatrix
Vào ngày 16 tháng 6 năm 2016, Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra, Christine Priplata, và Colin Stahlke công bố việc tính toán một Lôgarit rời rạc modulo số nguyên tố an toàn có 232 chữ số [có 768 bit] bằng cách dùng giải thuật sàng trường số.
On 16 June 2016, Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra, Christine Priplata, and Colin Stahlke announced the computation of a discrete logarithm modulo a 232-digit [768-bit] safe prime, using the number field sieve.
WikiMatrix
Xem phần tử nguyên tố. ^ p: Ví dụ, xem giao thức Diffie-Hellman sử dụng logarit rời rạc. ^ q: Các nhà toán học biết tới nhóm có bậc lớn nhất là 2000.
See prime element. ^ p: For example, the Diffie-Hellman protocol uses the discrete logarithm. ^ q: The groups of order at most 2000 are known.
WikiMatrix
Người ta thường dùng các phân bố rời rạc hay phân bố Gauss, do các phân bố này làm đơn giản việc tính toán.
It is common to work with discrete or Gaussian distributions since that simplifies calculations.
WikiMatrix
Bởi hệ thống rời rạc có lượng trạng thái đếm được, nó có thể được mô tả bằng các mô hình toán học chính xác.
Because discrete systems have a countable number of states, they may be described in precise mathematical models.
WikiMatrix
Tương ứng, cả hai đặc tính đều được phản ánh [ít nhất ngầm] trong các dạng toán học của các mô hình này: thứ nhất, các mô là thời gian rời rạc, thứ hai, họ là xác định.
Correspondingly, both characteristics are reflected [at least implicitly] in the mathematical form of these models: firstly, the models are in discrete time; secondly, they are deterministic.
WikiMatrix
Trong toán học và xử lý tín hiệu, biến đổi Z chuyển đổi một tín hiệu thời gian rời rạc, là một chuỗi số thực hoặc số phức, thành một đại diện trong miền tần số phức.
In mathematics and signal processing, the Z-transform converts a discrete-time signal, which is a sequence of real or complex numbers, into a complex frequency-domain representation.
WikiMatrix
Nghiệm đơn vị được sử dụng trong nhiều nhánh của toán học, và đặc biệt quan trọng trong lý thuyết số, lý thuyết nhóm tính chất, và biến đổi Fourier rời rạc.
Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform.
WikiMatrix
Thực tế, các tính chất của không gian các hàm sóng đã được sử dụng để thực hiện những tính toán vật lý [như bức xạ từ nguyên tử tại những mức năng lượng rời rạc] trước khi có bất kỳ một cách giải thích nào về những hàm đặc biệt này được nêu ra.
In fact, the properties of the space of wave functions were being used to make physical predictions [such as emissions from atoms being at certain discrete energies] before any physical interpretation of a particular function was offered.
WikiMatrix
Một hệ thống rời rạc chung cuộc thường được mô phỏng qua một đồ thị trực tiếp và được phân tích tính đúng đắn và độ phức tạp dựa theo lý thuyết tính toán.
A final discrete system is often modeled with a directed graph and is analyzed for correctness and complexity according to computational theory.
WikiMatrix
Tôi chỉ nói một chút về phương tiện kỹ thuật số ta đang sử dụng và cách mà chúng tích hợp vào việc tính toán: sự thực là chúng dựa trên các phương tiện tính toán mà ta không cần phải suy nghĩ đến việc đo đạc như 1 đơn vị lý tưởng hoặc những thành phần rời rạc.
To just talk for a minute about the digital mediums that we're using now and how they integrate calculus: the fact that they're calculus-based means that we don't have to think about dimension in terms of ideal units or discreet elements.