tailieunhanh - Giáo trình Toán rời rạc: Phần 2 - TS. Đỗ Văn Nhơn (biên soạn)

Phần 2 Giáo trình Toán rời rạc tiếp tục giới thiệu đến bạn đọc nội dung từ chương 4 đến chương 6 về thuật toán, quan hệ, đại số bool và hàm số bool. Giáo trình được trình bày dưới dạng lý thuyết với các ví dụ minh họa và bài tập, đồng thời sau mỗi chương đều có các bài tập giúp cho bạn đọc cũng như các bạn sinh viên thuận tiện trong việc nghiên cứu, củng cố kiến thức và áp dụng giải bài tập. | Chương 4 THUẬT TOÁN I. Thuật toan va cách biểu diễn thuật toan Khái niêm thuât toán Thuật toán lá mọt khái niêm cơ bán cUá Toán hoc vá Tin hoc. Khi viêt mọt chương trình máy tính ngươi tá thương cái đát mọt phương pháp đá đươc nghĩ rá trươc đo đê giái quyết mọt vấn đê. Tư thuát toán đươc dung trong khoá hoc máy tính đê đê chỉ sự mo tá mọt phương pháp giái bái toán thích hơp cho việc cái đát thánh các chương trình nhơ các ngon ngư láp trình. Mọt thuát toán thương đươc thê hiên bơi mọt thu tuc gom mọt dáy hưu hán bươc má thêo đo tá sê đát đến lơi giái cho bái toán. Ngươi tá co thê trình báy thuát toán báng cách liêt kê rá các bươc củá thuát toán sử dung ngon ngữ tư nhiên háy mọt ngon ngư qui ươc náo đo cháng hán sư dung mọt ngon ngư láp trình náo đo gán vơi ngon ngữ tự nhiên. Ví du 1 thuát toán tìm phán tử lơn nhất trong mọt dáy hưu hán các sô nguyên. Bái toán tìm phán tử lơn nhất trong mọt dáy hưu hán tương đoi tám thương. Tuy nhiên đáy lá mọt trong những ví du khá tot đê minh họá cho khái niêm vê thuát toán. co nhiêu vấn đê má trong đo đoi hoi phái tìm so nguyên lơn nhá t trong mọt dáy so . Cháng hán như viêc tìm rá mọt học sinh co điểm cáo nhát trong mọt ky thi háy tìm rá mọt nhán viên co náng suát cáo nhát trong mọt xí nghiêp . -120- Chung ta co nhiều cách để giải bài toán nay. Một trong những phương pháp đề tìm phàn tử lớn nhất trong một dày so nguyền là thực hiền mọt thu tuc theo các bước sau đày 1. Trước hết tà đàt cho già trị lơn nhàt tàm thơi bàng so nguyền đàu tiền. Già trị lớn nhàt tàm thơi này chính là già trị lớn nhàt ớ moi giài đoạn củà thu tuc. 2. So sành so nguyền kề tiếp trong dày với già trị lớn nhàt tàm thới và nều no lớn hớn già trị lớn nhàt tàm thới thì đàt cho già trị lớn nhàt tàm thới bàng so nguyền này. 3. Làp lài bước 2 nều con so nguyền trong dày chưà đước xềt tới. 4. Dừng nều khong con so nguyền nào trong dày chưà đước xềt. Già trị lớn nhàt tàm thới luc này chính là già trị lớn nhàt trong dày so . Ví du 2 Thuật toàn tính nghiềm củà .