Giáo trình toán rời rạc nguyễn gia định năm 2024

Bảng 6 Ma trận liên thuộc của đồ thị vô hướng .................................................................... 92

Bảng 6 Ma trận liên thuộc của đồ thị có hướng .................................................................... 93

Bảng 7 Tính đường đi ngắn nhất ......................................................................................... 114

Bảng 7 Ma trận D 0

cho thuật toán Floyd ............................................................................. 116

Giáo trình được tác giả biên soạn dựa trên kinh nghiệm giảng dạy môn học “Toán rời rạc” trong nhiều năm cho sinh viên ngành Công nghệ Thông tin của một số trường Đại học ở Thành phố Hồ Chí Minh với thời lượng 3 đơn vị học trình [45 tiết].

Tác giả biên soạn giáo trình theo hướng: sắp xếp nội dung tinh giản, hợp lý, đồng thời bảo đảm khối kiến thức tối thiểu về cơ sở Toán cho Tin học để sinh viên có điều kiện tiếp thu tốt các môn chuyên ngành trong chương trình đào tạo kỹ sư Công nghệ Thông tin. Tuy nhiên, giáo trình có thể sử dụng như một tài liệu tham khảo cho sinh viên ngành Toán - Tin học.

Giáo trình được chia thành 5 chương.

Chương 1 trình bày những vấn đề cơ bản nhất của logic học bao gồm: mệnh để; các quy luật logic; vị từ và lượng từ; suy luận toán học.

Chương 2 trình bày các vấn đề cơ bản trong phép đếm và trong giải tích tổ hợp; nguyên lý Dirichlet dùng để chứng minh sự tồn tại của cấu hình tổ hợp thoả mãn điều kiện cho trước.

Chương 3 trình bày khái niệm thuật toán; giới thiệu một số thuật toán tiêu biểu; độ phức tạp của thuật toán.

Chương 4 trình bày khái niệm quan hệ, cách biểu diễn một quan hệ bằng một ma trận; quan hệ tương đương; quan hệ thứ tự và biểu đồ Hasse của tập sắp thứ tự hữu hạn.

Chương 5 trình bảy các vấn đề cơ bản về hàm Boole, biểu thức Boole, đại số Boole và nguyên lý đối ngẫu; vấn đề tổ hợp các cổng logic theo biểu thức Boole cho trước; vấn để tối thiểu hoá hàm Boole bằng phương pháp biến đổi đại số, phương pháp Karnaugh, phương pháp Quine Mc. Cluskey.

Trong quá trình biên soạn, do nhiều lý do khácủ quan và chủ quan, giáo trình chắc chắn sẽ không tránh khỏi những sai sót. Tác giả rất mong nhận được các ý kiến đóng góp để giáo trình được hoàn thiện hơn.

Đây là giáo trình toán rời rác được viết bởi PGS.TS Nguyễn Gia Định, tài liệu với nội dung phong phú, trình bày dễ hiểu với nhiều ví dụ minh họa. Đây là một tài liệu rất bổ ích giúp cho các bạn có thể tiếp cận kiến thức một cách dễ dàng

Được sự động viÍn mạnh mẽ của c·c đồng nghiệp trong c·c Khoa To·n-Cơ-Tin học, CÙng nghệ ThÙng tin v‡ Vật l ̋ [Trường Đại học Khoa học-Đại học Huế], c·c Khoa To·n v‡ Tin học [Trường Đại học Sư phạm-Đại học Huế] v‡ đặc biệt do nhu cầu học tập của c·c sinh viÍn trong Đại học Huế ở c·c Khoa nÛi trÍn v‡ c·c học viÍn cao học ng‡nh Phương ph·p giảng dạy To·n, ch ̇ng tÙi mạnh dạn viết gi·o trÏnh To·n rời rạc trong khi trÍn thị trường s·ch cÛ kh· nhiều t‡i liệu liÍn quan đến To·n rời rạc. Điều m‡ ch ̇ng tÙi mong muốn l‡ c·c kiến thức của học phần n‡y phải được đưa v‡o đầy đủ, cÙ đọng, chÌnh x·c, cập nhật, b·m s·t theo yÍu cầu đ‡o tạo sinh viÍn c·c ng‡nh CÙng nghệ ThÙng tin, To·n-Tin, Vật l ̋-Tin v‡ một số ng‡nh kỹ thuật kh·c của c·c trường đại học v‡ cao đẳng. Với sự nổ lực hết mÏnh của bản th‚n, ch ̇ng tÙi thiết nghĩ đ‚y sẽ l‡ t‡i liệu tham khảo tốt cho c·c gi·o viÍn giảng dạy học phần to·n rời rạc, c·c học viÍn cao học ng‡nh Phương ph·p giảng dạy To·n, c·c thÌ sinh thi v‡o cao học ng‡nh cÙng nghệ thÙng tin, c·c sinh viÍn thuộc c·c ng‡nh được đề c ập ở trÍn v‡ c·c học sinh thuộc khối chuyÍn To·n, chuyÍn Tin. Nội dung của t‡i liệu n‡y được bố trÌ trong 4 phần, khÙng kể lời nÛi đầu, mục lục, t‡i liệu tham khảo v‡ phần phụ lục: Phần 1 được d‡nh cho Chương I đề cập đến Thuật to·n ; Phần 2 được d‡nh cho Chương II nÛi đến b‡i to·n đếm ; Phần 3, đ‚y l‡ phần chiếm nhiều trang nhất trong gi·o trÏnh, b‡n về L ̋ thuyết đồ thị v‡ c·c ứng dụng gồm 5 chương: Đồ thị, Đồ thị Euler v‡ đồ thị Hamilton, Một số b‡i to·n tối ưu trÍn đồ thị, C‚y, Đồ thị phẳng v‡ tÙ m‡u đồ thị ; Phần 4 được d‡nh cho Chương 8, chương cuối c ̆ng, đề cập đến Đại số Boole. Trong mỗi chương, c·c chứng minh của c·c định l ̋, mệnh đề được trÏnh b‡y chi tiết, ngoại trừ một số định l ̋ cÛ phần chứng minh qu· phức tạp thÏ được ch ̇ng tÙi bỏ qua. Trong c·c phần của mỗi chương cÛ nhiều vÌ dụ cụ thể minh hoạ cho những kh·i niệm cũng như những kết quả của ch ̇ng. Cuối của mỗi chương l‡ những b‡i tập được chọn lọc từ dễ đến khÛ, b·m theo nội dung của chương đÛ. Ch ̇ng tÙi xin ch‚n th‡nh c·m ơn c·c đồng nghiệp đ„ động viÍn v‡ gÛp ̋ cho cÙng việc viết gi·o trÏnh To·n rời rạc n‡y v‡ lời c·m ơn đặc biệt xin d‡nh cho Khoa CÙng nghệ ThÙng tin về sự gi ̇p đỡ qu ̋ b·u v‡ tạo điều kiện thuận lợi cho việc xuất bản gi·o trÏnh n‡y. T·c giả mong nhận được sự chỉ gi·o của c·c đồng nghiệp v‡ độc giả v ề những thiếu sÛt khÛ tr·nh khỏi của cuốn s·ch. M ̆a Thu năm 2003

To·n rời rạc - Nguyễn Gia Định 1

• Chương VI: C‚y .............................................................................................................
• 1. Định nghĩa v‡ c·c tÌnh chất cơ bản...........................................................................
• 1. C‚y khung v‡ b‡i to·n tÏm c‚y khung nhỏ nhất .......................................................
• 1. C‚y cÛ gốc ................................................................................................................
• 1. Duyệt c‚y nhị ph‚n ...................................................................................................
• B‡i tập Chương VI.........................................................................................................
• Chương VII: Đồ thị phẳng v‡ tÙ m‡u đồ thị
• 1. Đồ thị phẳng
• 1. Đồ thị khÙng phẳng
• 1. TÙ m‡u đồ thị..........................................................................................................
• B‡i tập Chương VII.......................................................................................................
• Chương VIII: Đại số Boole
• 1. Kh·i niệm đại số Boole
• 1. H‡m Boole
• 1. Mạch lÙgic
• 1. Cực tiểu ho· c·c mạch lÙgic...................................................................................
• B‡i tập Chương VIII
• T‡i liệu tham khảo
• Ph¿n phÿ lÿc
• Phÿ lÿc
• Phÿ lÿc
• To·n rời rạc - Nguyễn Gia Định

CH ̄ƠNG I: THU¾T TO¡N

1. KH¡I NIàM THU¾T TO¡N. 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. Đị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 rời rạc - Nguyễn Gia Định 4

kiểm tra chÌnh tÁ c ủa c·c từ, tÏm kiếm c·c từ n‡y trong một cuốn từ điển, m‡ từ điển chẳng qua cũng l‡ một bÁng liệt kÍ sắp thứ t ự c ủa c·c từ. C·c b‡i to·n thuộc lo¿i n‡y đ°ợc gọi l‡ c·c b‡i to·n tÏm kiếm. B‡i to·n tÏm kiếm tổng qu·t đ°ợc mÙ tÁ nh° sau: x·c định vị trÌ của phần tử x trong một bÁng liệt kÍ c·c phần tử ph‚n biệt a1, a 2 , ..., an hoặc x·c định rằng nÛ khÙng cÛ mặt trong bÁng liệt kÍ đÛ. Lßi giÁi của b‡i to·n trÍn l‡ vị trÌ của số h¿ng của bÁng liệt kÍ cÛ gi· trị bằng x [tức l‡ i sẽ l‡ nghiệm nếu x=ai v‡ l‡ 0 nếu x khÙng cÛ mặt trong bÁng liệt kÍ]. 1.2. Thu¿t to·n tÏm ki¿m tuy¿n tÌnh: TÏm kiếm tuyến tÌnh hay tÏm kiếm tuần tự l‡ bắt đầu bằng việc so s·nh x với a 1 ; khi x=a 1 , nghiệm l‡ vị trÌ a 1 , tức l‡ 1; khi x≠a 1 , so s·nh x với a 2. Nếu x=a 2 , nghiệm l‡ vị trÌ của a 2 , tức l‡ 2. Khi x≠a 2 , so s·nh x với a 3. Tiếp tục qu· trÏnh n‡y bằng c·ch tuần tự so s·nh x với mỗi số h¿ng của bÁng liệt kÍ cho tới khi tÏm đ°ợc số h¿ng bằng x, khi đÛ nghiệm l‡ vị trÌ của số h¿ng đÛ. Nếu to‡n bÁng liệt kÍ đ„ đ°ợc kiểm tra m‡ khÙng x·c định đ°ợc vị trÌ của x, thÏ nghiệm l‡ 0. GiÁ m„ đối với thuật to·n tÏm kiếm tuyến tÌnh đ°ợc cho d°ới đ‚y:

procedure tÏm kiếm tuyến tÌnh [x: integer, a 1 ,a 2 ,...,an: integers ph‚n biệt] i := 1 while [i ≤ n and x ≠ ai] i := i + 1 if i ≤ n then location := i else location := 0 {location l‡ chỉ số d°ới của số h¿ng bằng x hoặc l‡ 0 nếu khÙng tÏm đ°ợc x}

1.2. Thu¿t to·n tÏm ki¿m nhị ph‚n: Thuật to·n n‡y cÛ thể đ°ợc d ̆ng khi bÁng liệt kÍ cÛ c·c số h¿ng đ°ợc sắp theo thứ tự tăng dần. Chẳng h¿n, nếu c·c số h¿ng l‡ c·c số thÏ ch ̇ng đ°ợc sắp từ số nhỏ nhất đến số lớn nhất hoặc nếu ch ̇ng l‡ c·c từ hay x‚u k ̋ tự thÏ ch ̇ng đ°ợc sắp theo thứ tự từ điển. Thuật to·n thứ hai n‡y gọi l‡ thuật to·n tÏm kiếm nhị ph‚n. NÛ đ°ợc tiến h‡nh bằng c·ch so s·nh phần tử cần x·c định vị trÌ với số h¿ng á giữa bÁng liệt kÍ. Sau đÛ bÁng n‡y đ°ợc t·ch l‡m hai bÁng kÍ con nhỏ hơn cÛ kÌch th°ớc nh° nhau, hoặc một trong hai bÁng con Ìt hơn bÁng con kia một số h¿ng. Sự tÏm kiếm tiếp tục bằng c·ch h¿n chế tÏm kiếm á một bÁng kÍ con thÌch hợp dựa trÍn việc so s·nh phần tử cần x·c định vị trÌ với số h¿ng giữa bÁng kÍ. Ta sẽ thấy rằng thuật to·n tÏm kiếm nhị ph‚n hiệu quÁ hơn nhiều so với thuật to·n tÏm kiếm tuyến tÌnh. ThÌ dÿ 2. Để tÏm số 19 trong bÁng liệt kÍ 1,2,3,5,6,7,8,10,12,13,15,16,18,19,20,22 ta t·ch bÁng liệt kÍ gồm 16 số h¿ng n‡y th‡nh hai bÁng liệt kÍ nhỏ hơn, mỗi bÁng cÛ 8 số h¿ng, cụ thể l‡: 1,2,3,5,6,7,8,10 v‡ 12,13,15,16,18,19,20,22. Sau đÛ ta so s·nh 19 với số h¿ng cuối c ̆ng của bÁng con thứ nhất. VÏ 100. Định nghĩa 1: Ta nÛi h‡m f[n] cÛ cấp thấp hơn hay bằng h‡m g[n] nếu tồn t¿i hằng số C>0 v‡ một số tự nhiÍn n 0 sao cho |f[n]| ≤ C|g[n]| với mọi n≥n 0. Ta viết f[n]=O[g[n]] v‡ cÚn nÛi f[n] thoÁ m„n quan hệ big-O đối với g[n]. Theo định nghĩa n‡y, h‡m g[n] l‡ một h‡m đơn giÁn nhất cÛ thể đ°ợc, đ¿i diện cho ìsự biến thiÍnî của f[n]. Kh·i niệm big-O đ„ đ°ợc d ̆ng trong to·n học đ„ gần một thế kỷ nay. Trong tin học, nÛ đ°ợc sử dụng rộng r„i để ph‚n tÌch c·c thuật to·n. Nh‡ to·n học ng°ßi Đức Paul Bachmann l‡ ng°ßi đầu tiÍn đ°a ra kh·i niệm big-O v‡o năm 1892.

ThÌ dÿ 5: H‡m f[n]= 2

nn + ]3[ l‡ h‡m bậc hai v‡ h‡m bậc hai đơn giÁn nhất l‡ n 2. Ta cÛ:

f[n]= 2

nn + ]3[ =O[n 2 ] vÏ 2

nn + ]3[ ≤ n 2 với mọi n≥3 [C=1, n 0 =3].

Một c·ch tổng qu·t, nếu f[n]=aknk+ak-1nk-1+ ... +a 1 n+a 0 thÏ f[n]=O[nk]. Thật vậy, với n>1, |f[n]|| ≤ |ak|nk+|ak-1|nk-1+ ... +|a 1 |n+|a 0 | = nk[|ak|+|ak-1|/n+ ... +|a 1 |/nk-1+a 0 /nk] ≤ nk[|ak|+|ak-1|+ ... +|a 1 |+a 0 ]. Điều n‡y chứng tỏ |f[n]| ≤ Cnk với mọi n>1. Cho g[n]=3n+5nlog 2 n, ta cÛ g[n]=O[nlog 2 n]. Thật vậy, 3n+5nlog 2 n = n[3+5log 2 n] ≤ n[log 2 n+5log 2 n] = 6nlog 2 n với mọi n≥8 [C=6, n 0 =8]. Mánh đề: Cho f 1 [n]=O[g 1 [n]] v‡ f 2 [n] l‡ O[g 2 [n]]. Khi đÛ [f 1 + f 2 ][n] = O[max[|g 1 [n]|,|g 2 [n]|], [f 1 f 2 ][n] = O[g 1 [n]g 2 [n]]. Chăng minh. Theo giÁ thiết, tồn t¿i C 1 , C 2 , n 1 , n 2 sao cho |f 1 [n]| ≤ C 1 |g 1 [n]| v‡ |f 2 [n]| ≤ C 2 |g 2 [n]| với mọi n > n 1 v‡ mọi n > n 2. Do đÛ |[f 1 + f 2 ][n]| = |f 1 [n] + f 2 [n]| ≤ |f 1 [n]| + |f 2 [n]| ≤ C 1 |g 1 [n]| + C 2 |g 2 [n]| ≤ [C 1 +C 2 ]g[n] với mọi n > n 0 =max[n 1 ,n 2 ], á đ‚yC=C 1 +C 2 v‡ g[n]=max[|g 1 [n]| , |g 2 [n]|]. |[f 1 f 2 ][n]| = |f 1 [n]||f 2 [n]| ≤ C 1 |g 1 [n]|C 2 |g 2 [n]| ≤ C 1 C 2 |[g 1 g 2 ][n]| với mọi n > n 0 =max[n 1 ,n 2 ].

To·n rời rạc - Nguyễn Gia Định 10

b‡i to·n l‡ sự xử l ̋ song song - đ‚y l‡ kỹ thuật thực hiện đồng thßi c·c d„y phÈp tÌnh. Do sự t ăng tốc độ tÌnh to·n v‡ dung l°ợng bộ nhớ c ủa m·y tÌnh, cũng nh° nhß việc d ̆ng c·c thuật to·n lợi dụng đ°ợc °u thế của kỹ thuật xử l ̋ song song, c·c b‡i to·n v‡i năm tr°ớc đ‚y đ°ợc xem l‡ khÙng thể giÁi đ°ợc, thÏ b‚y giß cÛ thể giÁi bÏnh th°ßng. 1. C·c thu¿t ngữ th°ờng d ̆ng cho đß phăc t¿p cāa mßt thu¿t to·n: Độ phức t¿p Thuật ngữ O[1] Độ phức t¿p hằng số O[logn] Độ phức t¿p lÙgarit O[ n ] Độ phức t¿p tuyến tÌnh O[ nlogn ] Độ phức t¿p nlogn O[nb] Độ phức t¿p đa thức O[bn] [b>1] Độ phức t¿p h‡m mũ O[n!] Độ phức t¿p giai thừa

2. Thời gian m·y tÌnh đ°ợc d ̆ng bởi mßt thu¿t to·n: KÌch th°ớc C·c phÈp tÌnh bit đ°ợc sử dụng của b‡i to·n n logn N nlogn n 2 2 n n! 10 3-9 s 10 -8 s 3-8 s 10 -7 s 10 -6 s 3-3 s 102 7-9 s 10-7 s 7-7 s 10 -5 s 4 13 năm * 103 1,0-8 s 10-6 s 1-5 s 10 -3 s * * 104 1,3-8 s 10-5 s 1-4 s 10 -1 s * * 105 1,7-8 s 10 -4 s 2-3 s 10 s * * 106 2-8 s 10 -3 s 2-2 s 17 ph ̇t * *

1. SÞ NGUY N V¿ THU¾T TO¡N. 1.4. Thu¿t to·n Euclide: Ph°ơng ph·p tÌnh °ớc chung lớn nhất của hai số bằng c·ch d ̆ng ph‚n tÌch c·c số nguyÍn đÛ ra thừa số nguyÍn tố l‡ khÙng hiệu quÁ. L ̋ do l‡ á chỗ thßi gian phÁi tiÍu tốn cho sự ph‚n tÌch đÛ. D°ới đ‚y l‡ ph°ơng ph·p hiệu quÁ h ơn để tÏm °ớc số chung lớn nhất, gọi l‡ thu¿t to·n Euclide. Thuật to·n n‡y đ„ biết từ thßi cổ đ¿i. NÛ mang tÍn nh‡ to·n học cổ Hy l¿p Euclide, ng°ßi đ„ mÙ tÁ thuật to·n n‡y trong cuốn s·ch ì Những yếu tố î nổi tiếng của Ùng. Thuật to·n Euclide dựa v‡o 2 mệnh đề sau đ‚y. Mánh đề 1 [Thu¿t to·n chia]: Cho a v‡ b l‡ hai số nguyÍn v‡ b≠0. Khi đÛ tồn t¿i duy nhất hai số nguyÍn q v‡ r sao cho a = bq+r, 0 ≤ r < |b|. Trong đẳng thức trÍn, b đ°ợc gọi l‡ số chia, a đ°ợc gọi l‡ số bị chia, q đ°ợc gọi l‡ th°ơng số v‡ r đ°ợc gọi l‡ số d°.

To·n rời rạc - Nguyễn Gia Định 12

Khi b l‡ nguyÍn d°ơng, ta k ̋ hiệu số d° r trong phÈp chia a cho b l‡ a mod b. Mánh đề 2: Cho a = bq + r, trong đÛ a, b, q, r l‡ c·c số nguyÍn. Khi đÛ UCLN[a,b] = UCLN[b,r]. [à đ‚y UCLN[a,b] để chỉ °ớc chung lớn nhất của a v‡ b.] GiÁ sử a v‡ b l‡ hai số nguyÍn d°ơng với a ≥ b. Đặt r 0 = a v‡ r 1 = b. Bằng c·ch ·p dụng liÍn tiếp thuật to·n chia, ta tÏm đ°ợc: r 0 = r 1 q 1 + r 2 0 ≤ r 2 < r 1 r 1 = r 2 q 2 + r 3 0 ≤ r 3 < r 2 .................. rn-2 = rn-1qn-1 + rn 0 ≤ rn < rn- rn-1 = rnqn. Cuối c ̆ng, số d° 0 sẽ xuất hiện trong d„y c·c phÈp chia liÍn tiếp, vÏ d„y c·c số d° a = r 0 > r 1 > r 2 >... ≥ 0 khÙng thể chứa qu· a số h¿ng đ°ợc. Hơn nữa, từ Mệnh đề 2 á trÍn ta suy ra: UCLN[a,b] = UCLN[r 0 ,r 1 ] = UCLN[r 1 ,r 2 ] = ... = UCLN[rn-2, rn-1] = UCLN[rn-1,rn] = rn. Do đÛ, °ớc chung lớn nhất l‡ số d° kh·c khÙng cuối c ̆ng trong d„y c·c phÈp chia. ThÌ dÿ 6: D ̆ng thuật to·n Euclide tÏm UCLN[414, 662]. 662 = 441 + 248 414 = 248 + 166 248 = 166+ 82 166 = 82 + 2 82 = 2. Do đÛ, UCLN[414, 662] = 2. Thuật to·n Euclide đ°ợc viết d°ới d¿ng giÁ m„ nh° sau: procedure ̄CLN [a,b: positive integers] x := a y := b while y ≠ 0 begin r := x mod y x := y y := r end {UCLN [a,b] l‡ x} Trong thuật to·n trÍn, c·c gi· trị ban đầu của x v‡ y t°ơng ứng l‡ a v‡ b. à m ỗi giai đo¿n của thủ tục, x đ°ợc thay bằng y v‡ y đ°ợc thay bằng x mod y. Qu· trÏnh n‡y đ°ợc lặp l¿i chừng n‡o y ≠ 0. Thuật to·n sẽ ngừng khi y = 0 v‡ gi· trị của x á điểm n‡y, đÛ l‡ số d° kh·c khÙng cuối c ̆ng trong thủ tục, cũng chÌnh l‡ °ớc chung lớn nhất của a v‡ b.

To·n rời rạc - Nguyễn Gia Định 13

đ‚y c·c thuật to·n cộng v‡ nh‚n hai số nguyÍn trong biểu diễn nhị ph‚n. Ta cũng sẽ ph‚n tÌch độ phức t¿p tÌnh to·n của c·c thuật to·n n‡y thÙng qua số c·c phÈp to·n bit thực sự đ°ợc d ̆ng. GiÁ sử khai triển nhị ph‚n của hai số nguyÍn d°ơng a v‡ b l‡: a = [an-1an-2 ... a 1 a 0 ] 2 v‡ b = [bn-1 bn-2 ... b 1 b 0 ] 2 sao cho a v‡ b đều cÛ n bit [đặt c·c bit 0 á đầu mỗi khai triển đÛ, nếu cần]. 1] PhÈp cßng: XÈt b‡i to·n cộng hai số nguyÍn viết á d¿ng nhị ph‚n. Thủ tục thực hiện phÈp cộng cÛ thể dựa trÍn ph°ơng ph·p thÙng th°ßng l‡ cộng cặp chữ số nhị ph‚n với nhau [cÛ nhớ] để tÌnh tổng của hai số nguyÍn. Để cộng a v‡ b, tr°ớc hết cộng hai bit á phÁi c ̆ng của ch ̇ng, tức l‡: a 0 + b 0 = c 0 .2 + s 0. à đ‚y s 0 l‡ bit phÁi c ̆ng trong khai triển nhị ph‚n của a+b, c 0 l‡ số nhớ, nÛ cÛ thể bằng 0 hoặc 1. Sau đÛ ta cộng hai bit tiếp theo v‡ số nhớ a 1 + b 1 + c 0 = c 1 .2 + s 1. à đ‚y s 1 l‡ bit tiếp theo [tÌnh từ bÍn phÁi] trong khai triển nhị ph‚n của a+b v‡ c 1 l‡ số nhớ. Tiếp tục qu· trÏnh n‡y bằng c·ch cộng c·c bit t°ơng ứng trong hai khai triển nhị ph‚n v‡ số nhớ để x·c định bit tiếp sau tÌnh từ bÍn phÁi trong khai triển nhị ph‚n của tổng a+b. à giai đo¿n cuối c ̆ng, cộng an-1, bn-1 v‡ cn-2 để nhận đ°ợc cn-1+sn-1. Bit đứng đầu của tổng l‡ sn=cn-1. Kết quÁ, thủ tục n‡y t¿o ra đ°ợc khai triển nhị ph‚n của tổng, cụ thể l‡ a+b = [sn sn-1 sn-2 ... s 1 s 0 ] 2. ThÌ dÿ 8: TÏm tổng của a = [11011] 2 v‡ b = [10110] 2. a 0 + b 0 = 1 + 0 = 0 + 1 [c 0 = 0, s 0 = 1], a 1 + b 1 + c 0 = 1 + 1 + 0 = 1 + 0 [c 1 = 1, s 1 = 0], a 2 + b 2 +c 1 = 0 + 1 + 1 = 1 + 0 [c 2 = 1, s 2 = 0], a 3 + b 3 + c 2 = 1 + 0 + 1 = 1 + 0 [c 3 = 1, s 3 = 0], a 4 + b 4 +c 3 = 1 + 1 + 1 = 1 + 1 [s 5 = c 4 =1, s 4 = 1]. Do đÛ, a + b = [110001] 2. Thuật to·n cộng cÛ thể đ°ợc mÙ tÁ bằng c·ch d ̆ng đo¿n giÁ m„ nh° sau.

procedure cộng [a,b: positive integers] c := 0 for j := 0 to n- begin

d := ̈ ©

§

¤

¥

£ ++

2

jj cba

sj := aj + bj + c − 2d c := d end sn := c {khai triển nhị ph‚n của tổng l‡ [sn sn-1 .. 1 s 0 ] 2 }

To·n rời rạc - Nguyễn Gia Định 15

Tổng hai số nguyÍn đ°ợc tÌnh bằng c·ch cộng liÍn tiếp c·c cặp bit v‡ khi cần phÁi cộng cÁ số nhớ nữa. Cộng một cặp bit v‡ số nhớ đÚi ba hoặc Ìt hơn phÈp cộng c·c bit. Nh° vậy, tổng số c·c phÈp cộng bit đ°ợc sử dụng nhỏ hơn ba lần số bit trong khai triển nhị ph‚n. Do đÛ, độ phức t¿p của thuật to·n n‡y l‡ O[n]. 2] PhÈp nh‚n: XÈt b‡i to·n nh‚n hai số nguyÍn viết á d¿ng nhị ph‚n. Thuật to·n thÙng th°ßng tiến h‡nh nh° sau. D ̆ng luật ph‚n phối, ta cÛ:

ab = a∑

−

\=

1

0

2

n

j

j bj = ∑

−

\=

1

0

]2[

n

j

j ba j.

Ta cÛ thể tÌnh ab bằng c·ch d ̆ng ph°ơng trÏnh trÍn. Tr°ớc hết, ta thấy rằng abj=a nếu bj=1 v‡ abj=0 nếu bj=0. Mỗi lần ta nh‚n một số h¿ng với 2 l‡ ta dịch khai triển nhị ph‚n của nÛ một chỗ về phÌa tr·i bằng c·ch thÍm một số khÙng v‡o cuối khai triển nhị ph‚n của nÛ. Do đÛ, ta cÛ thể nhận đ°ợc [abj]2j bằng c·ch dịch khai triển nhị ph‚n của abj đi j chỗ về phÌa tr·i, tức l‡ thÍm j số khÙng v‡o cuối khai triển nhị ph‚n của nÛ. Cuối c ̆ng, ta sẽ nhận đ°ợc tÌch ab bằng c·ch cộng n số nguyÍn abj với j=0, 1, ..., n-1. ThÌ dÿ 9: TÏm tÌch của a = [110] 2 v‡ b = [101] 2. Ta cÛ ab 0 .2 0 = [110] 2 .1 0 = [110] 2 , ab 1 .2 1 = [110] 2 .0 1 = [0000] 2 , ab 2 .2 2 = [110] 2 .1 2 = [11000] 2. Để tÏm tÌch, h„y cộng [110] 2 , [0000] 2 v‡ [11000] 2. Từ đÛ ta cÛ ab= [11110] 2. Thủ tục trÍn đ°ợc mÙ tÁ bằng đo¿n giÁ m„ sau:

procedure nh‚n [a,b: positive integers] for j := 0 to n- begin if bj = 1 then cj := a đ°ợc dịch đi j chỗ else cj := 0 end {c 0 , c 1 ,..., cn-1 l‡ c·c tÌch riÍng phần} p := 0 for j := 0 to n- p := p + cj {p l‡ gi· trị của tÌch ab}

Thuật to·n trÍn tÌnh tÌch của hai số nguyÍn a v‡ b bằng c·ch cộng c·c tÌch riÍng phần c 0 , c 1 , c 2 , ..., cn-1. Khi bj=1, ta tÌnh tÌch riÍng phần cj bằng c·ch dịch khai triển nhị ph‚n của a đi j bit. Khi bj=0 thÏ khÙng cần cÛ dịch chuyển n‡o vÏ cj=0. Do đÛ, để tÏm tất cÁ n số nguyÍn abj với j=0, 1, ..., n-1, đÚi hỏi tối đa l‡

0 + 1 + 2 + ... + n−1 = 2

nn − ]1[

phÈp dịch chỗ. VÏ vậy, số c·c dịch chuyển chỗ đÚi hỏi l‡ O[n 2 ].

To·n rời rạc - Nguyễn Gia Định 16

procedure search [i,j,x] if ai = x then loacation := i else if i = j then loacation := 0 else search [i+1,j,x]

ThÌ dÿ 13: H„y x‚y dựng phiÍn bÁn đệ quy của thuật to·n tÏm kiếm nhị ph‚n. GiÁ sử ta muốn định vị x trong d„y a 1 , a 2 , ..., an bằng tÏm kiếm nhị ph‚n. Tr°ớc tiÍn ta so s·nh x với số h¿ng giữa a[[n+1]/2]. Nếu ch ̇ng bằng nhau thÏ thuật to·n kết th ̇c, nếu khÙng ta chuyển sang tÏm kiếm trong d„y ngắn hơn, nửa đầu của d„y nếu x nhỏ hơn gi· trị giữa của của d„y xuất ph·t, nửa sau nếu ng°ợc l¿i. Nh° vậy ta r ̇t gọn việc giÁi b‡i to·n tÏm kiếm về việc giÁi cũng b‡i to·n đÛ nh°ng trong d„y tÏm kiếm cÛ độ d‡i lần l°ợt giÁm đi một nửa.

procedure binary search [x,i,j] m := [[i+j]/2] if x = am then loacation := m else if [x < am and i < m] then binary search [x,i,m-1] else if [x > am and j > m] then binary search [x,m+1,j] else loacation := 0 1.5. Đá quy v‡ lặp: ThÌ dÿ 14. Thủ tục đệ quy sau đ‚y cho ta gi· trị của n! với n l‡ số nguyÍn d°ơng.

procedure factorial [n: positive integer] if n = 1 then factorial[n] := 1 else factorial[n] := n * factorial[n-1]

CÛ c·ch kh·c tÌnh h‡m giai thừa của một số nguyÍn từ định nghĩa đệ quy của nÛ. Thay cho việc lần l°ợt r ̇t gọn việc tÌnh to·n cho c·c gi· trị nhỏ hơn, ta cÛ thể xuất ph·t từ gi· trị của h‡m t¿i 1v‡ lần l°ợt ·p dụng định nghĩa đệ quy để tÏm gi· trị của h‡m t¿i c·c số nguyÍn lớn dần. ĐÛ l‡ thủ tục lặp.

procedure iterative factorial [n: positive integer] x := 1 for i := 1 to n x := i * x {x l‡ n!} ThÙng th°ßng để tÌnh một d„y c·c gi· trị đ°ợc định nghĩa bằng đệ quy, nếu d ̆ng ph°ơng ph·p lặp thÏ số c·c phÈp tÌnh sẽ Ìt hơn l‡ d ̆ng thuật to·n đệ quy [trừ khi d ̆ng c·c m·y đệ quy chuyÍn dụng]. Ta sẽ xem xÈt b‡i to·n tÌnh số h ¿ng thứ n của d„y Fibonacci.

procedure fibonacci [n: nguyÍn khÙng ‚m]

To·n rời rạc - Nguyễn Gia Định 18

if n = 0 the fibonacci [n] := 0 else if n = 1 then fibonacci [n] := 1 else fibonacci [n] := fibonacci [n - 1] + fibonacci [n - 2]

Theo thuật to·n n‡y, để tÏm fn ta biểu diễn fn = fn-1 + fn-2. Sau đÛ thay thế cÁ hai số n‡y bằng tổng của hai số Fibonacci bậc thấp hơn, cứ tiếp tục nh° vậy cho tới khi f 0 v‡ f 1 xuất hiện thÏ đ°ợc thay bằng c·c gi· trị của ch ̇ng theo định nghĩa. Do đÛ để tÌnh fn cần fn+1-1 phÈp cộng. B‚y giß ta sẽ tÌnh c·c phÈp to·n cần d ̆ng để tÌnh fn khi sử d ụng ph°ơng ph·p lặp. Thủ tục n‡y khái t¿o x l‡ f 0 = 0 v‡ y l‡ f 1 = 1. Khi vÚng lặp đ°ợc duyệt qua tổng của x v‡ y đ°ợc g·n cho biến phụ z. Sau đÛ x đ°ợc g·n gi· trị của y v‡ y đ°ợc g·n gi· trị của z. Vậy sau khi đi qua vÚng lặp lần 1, ta cÛ x = f 1 v‡ y = f 0 + f 1 = f 2. Khi qua vÚng lặp lần n-1 thÏ x = fn-1. Nh° vậy chỉ cÛ n ñ 1 phÈp cộng đ°ợc d ̆ng để tÏm fn khi n > 1.

procedure Iterative fibonacci [n: nguyÍn khÙng ‚m] if n = 0 then y := 0 else begin x := 0 ; y := 1 for i := 1 to n - 1 begin z := x + y x := y ; y := z end end {y l‡ số Fibonacci thứ n} Ta đ„ chỉ ra rằng số c·c phÈp to·n d ̆ng trong thuật to·n đệ quy nhiều hơn khi d ̆ng ph°ơng ph·p lặp. Tuy nhiÍn đÙi khi ng°ßi ta vẫn thÌch d ̆ng thủ tục đệ quy hơn ngay cÁ khi nÛ tỏ ra kÈm hiệu quÁ so với thủ tục lặp. Đặc biệt, cÛ những b‡i to·n chỉ cÛ thể giÁi bằng thủ tục đệ quy m‡ khÙng thể giÁi bằng thủ tục lặp.

B¿I T¾P CH ̄ƠNG I:

1. TÏm một số nguyÍn n nhỏ nhất sao cho f[x] l‡ O[xn] đối với c·c h‡m f[x] sau: a] f[x] = 2x 3 + x 2 log x. b] f[x] = 2x 3 + [log x] 4.