Chương 1 Kiến thức nền tảng 1.1 Ngôn ngữ giả mã Là một ngôn ngữ biểu tượng được sử dụng trong luận văn để mô tả các khái niệm, định lý, ví dụ, đặc biệt là các thuật toán và các thủ tục thực hiện thuật toán. Ngôn ngữ giả mã tương tự như một ngôn ngữ đại số máy tính nhưng nó mang tính hình thức vì sử dụng cả biểu tượng toán học, tiếng anh và tiếng việt trong đó. Để sử dụng một hệ thống đại số máy tính hiệu quả thì điều quan trọng là phải hiểu rõ ràng về cấu trúc và ý nghĩa của các biểu thức toán học. Về cơ bản biểu thức toán học trong ngôn ngữ giả mã cũng giống như các biểu thức toán học thông thường nhưng có một số thừa nhận để thích hợp trong môi trường tính toán.
Các biểu thức được mô tả bằng cấu trúc sử dụng các toán tử và các ký hiệu sau: Số nguyên và phân số Một phần mềm thực hiện chính xác các thao tác trên biểu thức toán học phải có khả năng thực hiện chính xác các tính toán số học. Trong các ngôn ngữ lập trình thông thường việc tính toán với số thực dấu phẩy động thường có liên quan đến làm tròn số nên sẽ không phù hợp với hầu hết các hệ thống đại số máy tính. Thay vào đó các hệ thống sử dụng số hữu tỉ để đảm bảo thu được kết quả chính xác.99)/(𝑥 − 1) Mặc dù giá trị của 𝑓 và 𝑔 là gần như nhau với mỗi giá trị của 𝑥 nhưng đặc điểm toán học của hai biểu thức là hoàn toàn khác nhau.Với 𝑥 ≠ 1 thì 𝑓 có thể rút gọn thành (𝑥 + 1) trong khi đó 𝑔 thì không thể rút gọn được. Số thực Trong ngôn ngữ giả mã thì số thực là một số hữu hạn bao gồm dấu phẩy thập phân và có thể có số mũ của 10 Ví dụ: 467.
Trong toán học một số thực không có dạng hữu tỉ thì gọi là số vô tỉ. Do khó có thể thực hiện các thao tác tính toán biểu tượng với số vô tỉ nên số vô tỉ sẽ được 1 thay bằng các ký hiệu (𝑒, 𝑙𝑛.) hoặc các biểu thức đại số (22 …) Định danh Trong ngôn ngữ giả mã định danh là một chuỗi các chữ cái tiếng anh, tiếng hy lạp, chữ số và dấu gạch dưới. Định danh được sử dụng trong ngôn ngữ giả mã như là biến lập trình tương ứng với kết quả của một phép tính, như một hàm, một toán tử, tên của thủ tục, ký hiệu toán học hoặc các ký tự đặc biệt. Toán tử đại số và dấu ngoặc Các toán tử đại số được trình bày trong bảng dưới.
Dấu ngoặc được sử dụng để thay đổi cấu trúc của biểu thức. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 2 Toán tử toán học Toán tử trong ngôn ngữ giả mã Cộng, trừ +, − Nhân, chia ∗,/ Lũy thừa ^ Giai thừa ! Bảng 1.1 Các toán tử đại số Hàm số Trong ngôn ngữ giả mã hàm số dùng để biểu diễn các hàm toán học như (𝑠𝑖𝑛(𝑥), 𝑒𝑥𝑝(𝑥), 𝑎𝑟𝑐𝑡𝑎𝑛(𝑥).), các toán tử toán học (𝐸𝑥𝑝𝑎𝑛𝑑(𝑢), 𝐹𝑎𝑐𝑡𝑜𝑟 (𝑢), 𝐼𝑛𝑡𝑒𝑔𝑟𝑎𝑙(𝑢, 𝑥 ).), và các hàm như ( 𝑓(𝑥), 𝑔(𝑥, 𝑦).Trong hệ thống đại số máy tính các hàm toán học được định nghĩa thông qua các hành động của các luật biến đổi trong hệ thống. Hàm dùng để thao tác và phân tích biểu thức toán học được gọi là toán tử toán học. Một dạng quan trọng của hàm là dạng không xác định, trong dạng này biểu thức được ký hiệu (𝑓(𝑥), 𝑔(𝑥, 𝑦).
Các hàm dạng này không có luật biến đổi, không có thuộc tính mà chỉ có sự phụ thuộc của tên hàm vào biểu thức bên trong dấu ngoặc đơn. Các toán tử logic và toán tử quan hệ o Các toán tử quan hệ được sử dụng trong ngôn ngữ giả mã là: =, ≠, <, ≤, >, ≥ o Các tán tử logic: 𝑎𝑛𝑑, 𝑜𝑟, 𝑛𝑜𝑡, 𝑡𝑟𝑢𝑒, 𝑓𝑎𝑙𝑠𝑒 Tập hợp và danh sách o Tập hợp Trong ngôn ngữ giả mã một tập hợp là một tập bao gồm hữu hạn các biểu thức toán học được bao quanh bởi cặp dấu ngoặc ‘{}’ và thỏa mãn hai tính chất sau: 1. Nội dung của một tập hợp không phụ thuộc vào thứ tự của các phần tử trong tập hợp. Các phần tử trong tập hợp phải là duy nhất.
Các toán tử của tập hợp: Cho A và B là hai tập hợp các toán tử của tập hợp được định nghĩa như sau: Hợp ( A ∪ B ): là một tập mới chứa tất cả các phần tử của A và B. Ví dụ: {𝑎, 𝑏, 𝑐, 𝑑} ∪ {𝑐, 𝑑, 𝑒, 𝑓} → {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓} Giao (A ∩ B): là một tập mới chứa các phần tử có trong cả A và B. Ví dụ: {𝑎, 𝑏, 𝑐, 𝑑} ∩ {𝑐, 𝑑, 𝑒, 𝑓} → {𝑐, 𝑑} o Danh sách Trong ngôn ngữ giả mã một danh sách bao gồm một số hữu hạn các biểu thức toán học và được bao quanh bởi cặp dấu ngoặc ‘[]’. Một danh sách rỗng thì không chứa biểu thức nào và được ký hiệu là [].
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 Danh sách có các tích chất sau: 1. Thứ tự của các phần tử trong danh sách là có ý nghĩa. Các phần tử trong danh sách có thể giống nhau. Cho L, M, N tương ứng là các danh sách và biểu thức x.
Các toán tử của danh sách được định nghĩa như sau: First(L): toán tử sẽ trả về biểu thức đầu tiên trong L. Nếu L = [] thì toán tử trả về Undefined. - Ví dụ: First([a, b, c]) → a Rest(L): toán tử trả về một danh sách bao gồm tất cả các biểu thức có trong L ngoại trừ biểu thức đầu tiên. Nếu L = [] thì toán tử trả về Undefined.
- Ví dụ: Rest([a, b, c]) → [b, c] Adjoin(x, L): toán tử trả về một danh sách mới chứa toán tử đầu tiên là biểu thức x và theo sau là các biểu thức của L., N): toán tử sẽ trả về một danh sách mới chứa các biểu thức của L và các biểu thức có trong các danh sách còn lại. - Ví dụ: Join([a, b], [b, c], [c, d, e]) → [a, b, b, c, c, d, e] Biểu thức toán học trong ngôn ngữ giả mã Trong ngôn ngữ giả mã biểu thức toán học là bất kỳ biểu thức nào được tạo thành bằng cách sử dụng số nguyên, phân số, số thực, định danh, hàm số, tập hợp, danh sách và các toán tử đại số, toán tử logic, toán tử quan hệ được mô tả ở trên.2 Tính toán biểu thức và chương trình toán học Tính toán biểu thức Thuật ngữ tính toán biểu thức liên quan đến các hành động trong hệ thống đại số máy tính để xử lý một biểu thức đầu vào. Các hành động bao gồm: [13] 1. Phân tích cấu trúc của biểu thức và biến đổi sang cấu trúc của hệ thống.
Tính giá trị của các biến được gán và toán tử toán học xuất hiện trong biểu thức. Áp dụng một số các quy tắc rút gọn cơ bản của đại số và lượng giác. Chương trình toán học Một chương trình toán học hay còn gọi là một thuật toán toán học là một chuỗi các câu lệnh để thực hiện các toán tử và cấu trúc điều khiển trong lập trình đại số máy tính. Cấu trúc của chương trình thường có các tính chất sau: [13] 1.
Các câu lệnh trong chương trình được xem như một đơn vị kết thúc bằng dấu chấm phẩy. Các câu lệnh bao gồm các biểu thức toán học, các câu lệnh gán, câu lệnh quyết định, câu lệnh lặp, hàm và các thủ tục được định nghĩa. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Như với các chương trình thông thường một số câu lệnh có vai trò như là các câu lệnh đầu vào, một số câu lệnh là tính toán trung gian với đầu ra không được hiển thị, một số câu lệnh thì để hiển thị dữ liệu là kết quả của quá trình tính toán.
Chương trình được thiết kế tổng quát để có thể thực hiện một lớp các vấn đề thay vì một vấn đề duy nhất.3 Khái niệm toán học cơ bản 1.1 Số nguyên Trong phần này sẽ đưa ra các tính chất cơ bản của số nguyên và mô tả một số thuật toán quan trọng để thao tác với số nguyên trong đại số máy tính.1: Cho số nguyên 𝑎 và 𝑏 khác 0, có số nguyên 𝑞 và 𝑟 là duy nhất sao cho: 𝑎 =𝑞∗𝑏+𝑟 Số nguyên 𝑞 là thương tương ứng với toán tử 𝑖𝑞𝑢𝑜𝑡(𝑎, 𝑏) và 𝑟 là phần dư tương ứng toán tử 𝑖𝑟𝑒𝑚(𝑎, 𝑏).2: Số nguyên 𝑏 ≠ 0 là ước của số nguyên 𝑎 nếu có một số nguyên 𝑞 sao cho 𝑎 = 𝑞∗𝑏 Một ước chung của hai số nguyên 𝑎 và 𝑏 là một số nguyên 𝑐 sao cho 𝑐 là ước của 𝑎 và 𝑏.3: Hai số nguyên a và b là số nguyên tố cùng nhau nếu chúng chỉ có ước chung là 1 và -1. Ước chung lớn nhất Ước chung lớn nhất của hai số nguyên 𝑎 và 𝑏 là số nguyên 𝑑 thỏa mãn: 1. d là ước chung của a và b 2. Nếu e là ước chung khác của a và b thì e chia hết cho d 3.
d > 0 Chú ý: Nếu cả 𝑎 và 𝑏 bằng 0 thì định nghĩa trên không được áp dụng. Trong trường hợp này quy định 𝑔𝑐𝑑(0,0) = 0. Thuật toán Euclid để tìm ước chung lớn nhất Định nghĩa 1.4: Cho 𝑎 và 𝑏 là các số nguyên khác 0 và cho 𝑟 = 𝑖𝑟𝑒𝑚(𝑎, 𝑏) thì 𝑔𝑐𝑑(𝑎, 𝑏) = 𝑔𝑐𝑑(𝑏, 𝑟). Thủ tục thực hiện toán tử tìm ước chung lớn nhất của hai số nguyên a và b LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 Procedure 𝐼𝑛𝑡𝑒𝑔𝑒𝑟𝐺𝐶𝐷(a, b); Input a, b : là các số nguyên; Output Ước chung lớn nhất của a và b; Local Variables A, B, R; Begin A := a; B := b; while B = 0 do R := 𝐼𝑟𝑒𝑚(A, B); A := B; B := R; Return(𝐴𝑏𝑠𝑜𝑙𝑢𝑡𝑒𝑉𝑎𝑙𝑢𝑒(A)) End Hình 1.1 Thủ tục tìm ước chung lớn nhất của hai số nguyên a và b Chú ý: - 𝑔𝑐𝑑(𝑎, 𝑏) là ước chung lớn nhất của a và b (Greatest Common Divisor).
- AbsoluteValue(A): giá trị tuyệt đối của A 1.2 Số hữu tỉ Một số hữu tỉ là một phân số 𝑎/𝑏 với 𝑎 và 𝑏 ≠ 0 là các số nguyên. Với định nghĩa trên thì số hữu tỉ có thể biểu diễn dưới nhiều dạng (1⁄2, (−2)/(−4). Quá trình rút gọn sẽ biến đổi số hữu tỉ về dạng chuẩn. Ví dụ: 2/4 → 1/2, 2/(−4) → (−1)/2 (−2)/(−4) → 1/2, 4/1 → 4 Phép biến đổi sẽ thu được bởi luật sau: Định nghĩa 1.5: Cho 𝑎 và 𝑏 là các số nguyên.