Giáo trình Toán rời rạc: Phần 1 - Đỗ Đức Giáo

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:238

Thêm vào BST

Báo xấu

429
lượt xem 57
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 1 giáo trình "Toán rời rạc" sau đây gồm nội dung 5 chương đầu: Chương 1 - Khái niệm thuật toán - Phương pháp quy nạp, phương pháp đệ quy; chương 2 - Quan hệ, chương 3 - Đồ thị hữu hạn, chương 4 - Cây, chương 5 - Nhập môn về văn phạm và ngôn ngữ hình thức.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Toán rời rạc: Phần 1 - Đỗ Đức Giáo

- , T ĐẠI HỌC VINH THƯ VIỆN ĐÔ ĐỨC GIÁO W 511 Ế ĐO-G/00 DT. 000489 - ọ KỊ Ha N ú i NHÀ XUÂT BÁN ĐAI HOC QUÔC GIA HÀ NÔI
Chiu trách nhiêm xuất ban: Giam đốc NGUYỄN VÀN THOA Tổng biên tập NGUYEN THIỆN GIÁP Người nhận xét: TS NGUYEN TUỆ TS HÀ QUANG THỤY Biên tập và sửa bản in: Đ ỗ Hữu PHÚ Trình bày bìa: NGỌC ANH TOÁN RỜI RẠC Mã số : 01 64.ĐH2000 - 55.2000 In 1000 bản, tại Nhà in Đại học Quốc gia Hà NÓI Số xuất bản: 39/55/CXB. Số trích ngang 171 KH/XB. In xong và nõp lưu chiểu Quý IV năm 2000.
L Ờ I NÓI Đ Ầ U Nhằm đáp ứng nhu cầu phục vụ học tập của đông đảo sinh viên ngành Tin học và Công nghệ thông tin ở các trường đại học. Chúng tôi biên soạn giáo trình "Toán rời rác" 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 cử nhân Tin học và Công nghệ thông tin ở giai đoạn li. Với khôi kiến thức được đề cập trong giáo trình này, sinh viên có thê tự học, tự đọc không mấy khó khăn cấc tài liệu chuyên sâu trong lĩnh vực Tin học lý thuyết. Nội dung chính của giáo trình bao gửm : Chương 1: Khái niệm thuật toán - Phương pháp quy nạp- Phương pháp đệ quy. Chương 2: Quan hệ. Chương 3: Đử thị hữu hạn. Chương 4: Cây. Chương 5: Nhập môn về văn phạm và ngôn ngữ hình thức. Chương 6: Ôtômat hữu hạn đoán nhận ngôn ngữ chính quy. Chưởng 7: Otômat đấy xuống đoán nhận ngôn ngữ phi ngữ cảnh Chương 8: Lôgic toán. Chương 9: Đại sốboole. 3
Trong mỗi chương chúng tôi chi đề cập những khái niệm cơ bản nhất, đông thời đưa ra một sô ví dụ minh họa giúp bạn đọc hiểu rõ bản chất của vân đề, cuối mỗi chương là phần bài tập đê bạn đọc củng cô kiên thức đã tiếp thu đưực từ phản lý thuyết. Tác giả xin chân thành cảm ơn các bạn đồng nghiệp, Khoa Công nghệ thống tin Trường đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã động viên, kích lệ chúng tôi biên soạn giáo trình này. Cảm ơn TS Nguyễn Tuệ, TS Hà Quang Thụy, TS Đinh Mạnh Tường, TS Vũ Ngọc Loàn đã đọc bản thảo và đóng góp nhiều ý kiến quý báu. cảm ơn Nhà xuất bản đại học Quác gia Hà Nội đã tạo điều kiện đê cuốn sách sớm đến tay bạn đọc. Cuốn sách xuất bản lần hai, chắc không tránh khỏi những thiếu sót, chúng tôi chân thành cảm ơn và tiếp thu ý kiên của bạn đọc đê lần xuất bản sau đưực hoàn thiện hơn. Tác giả 4
Chương Ì KHÁI N I Ệ M THUẬT TOÁN - PHƯƠNG PHÁP QUY NẠP - PHƯƠNG PHÁP ĐỆ QUY |1. KHÁI NIỆM THUẬT TOÁN 1.1. T h u ậ t t o á n là gì Thuật toán là một khái niệm quan trọng của toán học. Nói đến thuật toán là nói đèn một dãy các quy tắc. nhằm xác định một dãy các thao tác trên các đôi tượng, sao cho sau một sô hữu hạn bước thực hiện các thao tác. ta đạt được mảc tiêu cần làm. 1.2. C á c đ ặ c t r ư n g của t h u ậ t t o á n - Tính dừng: Sau một sô hữu hạn bước thuật toán phải dừng. - Tính xác định: ơ mỗi bước. các bước thao tác phải hết sức rõ ràng. không gây liên sự nhập nhằng. Nói rõ hơn. trong cùng một điều kiện hai bộ xử lý cùng thực hiện một bước của thuật toán phải cho những kết quả như nhau. - Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi chia dữ liệu vào thuật toán hoạt động và đưa ra kết quả như ý muốn. 5
• Tính phô dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lốp các bài toán. Cụ thể là thuật toán có thê có các đầu vào là các bộ dữ liệu khác nhau trong một miên xác định. - Yếu tố vào ra: Đối với một thuật toán luôn có một đối tượng vào (input) và đối tượng ra (output). 1.3. N g ô n ngữ thuật t o á n - Ngôn ngữ dùng để miêu tả thuật toán gọi là ngôn ngữ thuật toán. - Thuật toán thường được mô tả bặng một dãy các lệnh. Bộ xử lý sẽ thực hiện các lệnh đó theo một trật tự nhất định cho đến khi gặp lệnh dừng thì kết thúc. - Ngôn ngữ thuật toán bao gồm : + Ngôn ngữ liệt kê từng bước; + Sơ đồ khối; + Ngôn ngữ lập trình. a) Ngôn ngữ Hét kê từng bước nội dung như sau: 1. Thuật toán: Tên thuật toán và chức năng. 2. Vào: Các dữ liệu vào vói tên kiểu. 3. Ra: Các dữ liệu ra vối tên kiểu. 4. Biến phụ (nếu có) gồm tên kiểu. õ. Hành động là các thao tác vối các lệnh có nhãn là các số tự nhiên. Ví dụ : Để giải phương trình bậc hai ax' + bx + c = 0 (a ±-0), ta có thể mô tả thuật toán bặng ngôn ngữ liệt kê như sau: Bước 1: Xác định các hệ sốa,b,c. Bước 2: Kiểm tra xem hệ số a có khác 0 hay không ? Nêu a = 0 quay lại thực hiện bưốc 1. 6
Bước 3: Tính biểu thức A = t r - 4ac. Bước 4: Nếu A < 0 thông báo phương trình vô nghiệm và chuyển đèn bước 8. -b Nêu A : 0. tính X i và chuyến sang Bước õ: 2a bưỏc 7. b-VÃ b + VÃ Tính X, Xs = và chuyển Bưốc 6: 2a 2a sang bước 7. Bưóc 7: Thông báo các nghiệm X i , x . 2 Bưốc 8: Kết thúc thuật toán. b) Sơ đồ khôi Để mô tả thuật toán bằng sơ đồ khối ta cần dựa vào các nút -au : - Nút thao tác: Biểu diễn bằng hình chữ nhật. trong đó ghi câu lệnh cần thực Nút thao tác hiện. Nêu có nhiều câu lệnh liên tiếp cần được thực hiện thì chúng có thể được viêt chung trong một hình chữ nhật; - Nút điều kiện: Biểu diễn bằng Nút điểu kiên hình thoi. trong đó ghi điêu kiện cần kiểm tra trong quá trình tính toán; - Nút khởi đầu, kết thúc: Biêu diễn Nút khởi đáu, bằng hình elip, thể hiện sự bỉt đ ầ u hay kết thúc kết thúc quá trình; Cung - Cung: Biểu diễn bằng đoạn thẳng có hướng, dùng để chỉ đường đi của t h u ậ t toán 7
Ví du: Dê giải phướng t r ì n h bạc hai ax" I bx + c - 0 (a=0) ta mô t ả thuật toan b ă n g p h ư ơ n g p h á p sơ đồ khối n h ư sau: 8
c) Ngôn ngữ lập trình Để giải các bài toán. trong thực tè bằng máy tính nguôi ta thường sử dụng J11 ọ t loại ngôn ngữ. gọi là ngôn ngữ lập trình. chẳng hạn như ngôn ngữ lập trình Cobol. Algol. Pascal, v.v... Chương trình chính là một dãy hữu hạn các câu lệnh được viết theo một quy tắc nhầt định trên một ngôn ngữ l ậ p trình nào đó. Hav nói cách khác, để giải một bài toán trước hết cần có một thuật toán để giải bài toán đó. Để máy tính hiểu được thuật toán. người ta sử dụng một ngôn ngữ lập trình cụ thế đế diễn đạt thuật toán thông qua ngôn ngữ đó. 2 Ví dụ: Để giải phương trình bậc hai ax + bx + c = 0 (a^O), thuật toán được mô tả bằng một chương trình viết trên Pascal như sau: Program GIAI_PHUONG_TRINH_BAC_HAI; uses crt; var a, b, c, denta, x i , x2: real; BEGIN clrscr; write('Nhap he so : '); repeat write('a = '); readln(a); write('b = '); readln(b); write('c = '); readln(c); until a0; denta := sqr(b) - 4*a*c; if denta < 0 then begin write('phuong trinh vo nghiêm'); halt; end 9
else if denta = 0 then begin write("phuong trinh co nghiêm kép x='. -b/(2*a)); exit; end else begin x1:=(-b-sqrt(denta))/(2*a); x2:=(-b+sqrt(denta))/(2*a); writelnCphuong trinh co hai nghiêm phan bỉet'); write('x1= \ x i , ' ,', 'x2 =', x2); exit; end; readln; END. 1.4. Đ ô p h ứ c t ạ p t h u ậ t t o á n Khi để xuất một thuật toán ngoài việc quan tâm đèn tính đúng đắn. thường phải quan tâm đến một số vấn đề như: líu điểm. nhược điểm. tính phổ dụng. thời gian tính toan. ... Với các thuật toán được sử dụng có tỗn sô cao như các thuật toan sắp xếp. thuật toán tìm kiêm, ... ta đặc biệt quan tâm đến thời gian cỗn thiết cho việc thực hiện thuật toán đó. Thông thường với mỗi thuật toán, thì dữ liệu vào sẽ có kích thước là một số nào đó. Chẳng hạn khi ta sắp xếp một dãy sô thì kích thước của dữ liệu có thế xem như là sô phỗn tử n của dãy đó. Rõ ràng với li càng lốn thì thòi gian cỗn thiết cho việc sắp xép sẽ càng lớn và nó là một hàm của đôi số lì. Ta ký hiệu hàm đó là f(n). 10
T r ư ớ c k i n (húi VÍU) k h a i m è m (lọ phức l ạ p của t l i u ạ l Ui;ui. ta đ ể c ạ p t ớ i một sô k h a i n i ệ m san : a) Khái niêm vê đô tàng của hàm Một trong những khai n i ệ m thường d ù n g để p h â n tích độ t à n g của một h à m là k h á i n i ệ m o được định nghĩa n h ư sau : Cho f(x) và g(x) là hai h à m t ừ t ậ p các sô n g u y ê n dường hoác tập các sô thực vào t ậ p các số thực. Ta nói f(x) là 0(g(x)) n ê u t ặ n tai hai hằng sô c và k sao cho I f(x) I < c I g(x)!. v ố i m ọ i X > k . Cần lưu ý r ằ n g cặp các hằng số c và k thỏa m ã n điêu k i ệ n trên là k h ô n g duy nhất. đặng thời n ế u f(x) là 0(g(x)) m à h(x) là h à m t h ỏ a m ã n I g(x) ị < Ị h(x) I với X > k t h ì ta c ũ n g có : f(x) là 0(h(x)). Ví dụ 1: Cho f(x) = a„x" + a„ jx" ' + . . . + a,x + a, . vối a, là các số thực (i = 0. Ì li). Khi đó f(x) = 0(x"). T h ậ t vậy, với mọi X > Ì : ị a,,x" + a ,x" + ... + a,x 4 a„ I I f(x) I = n 1 < I a„ ỉ x" + Ị a„ ỉ x" + ... + I a, I X I 1 4 I a„ I I I 1*1 ti—ì I I&11 Ị £X ~ Ị n = x a, + ^ + ... + ^ | t . . , + ! - i l { l 1 X x n _ 1 x n Ị k. hay f(x) là 0(x ). 2 Ví dụ 2: Cho f(n) = 1 + 2 + 3 + ... + n . Chỉ ra f(n) là 0 ( n ) . 2 T h ậ t vậy. f(n) < lì + n + n + ... + 11 = 11.11 = n , n ê n f(n) là 0(n ) với c = k = 1. 2 n Ví dụ 3: Chỉ ra h à m n! là 0 ( n ) và logn! là O(nlogn). n T h ậ t vậy, ta có n! < n". n ê n n! là 0 ( n ) với c = k = 1. li
Từ l i ! < l i .- logn! < nlogn. vạy logn! là O(nlogn) với c = k r 1. Ví dụ 4: H ã y chỉ ra h à m logn là O(n). T h ậ t vậy. ta có n < 2" với m ọ i l i > 1. nên logn < l i (lôga cơ sô 2) và vì vậy logn l à O(n) với c - k = 1. b) Đô tăng của tô hớp các hàm T ừ k h á i n i ệ m về độ t ă n g của h à m ta có m ộ t sô k é t q u ả sau đây : Ví dụ 5: N ế u f,(x) là 0(g,(x)) v à f (x) là 0(g (x)) t h ì 2 2 (f,(x) + f (x)) l à 0 ( m a x { 2 g l (x), g (x)}). 2 T h ậ t vậy, theo g i ả t h i ế t t ồ n t ạ i Cj v à ki sao cho I fi(x) I < Q I gi(x) I v ớ i m ọ i X > k i , (i = Ì, 2). Ta l ạ i có I f,(x) + f (x) I 2 < I f,(x) I + I f (x) 2 I < c , I g,(x) I + c 1 2 g (x) 2 I k, ở đây k = max{kj , k }; c - c, + C/. g(x) = max{ I gi(x) Ị. Ị g (x) I} 2 2 Ví dụ 6 : Cho f,(x) v à f (x) đ ề u là 0(g(x)). K i n đó2 fi(x) + f (x) là 0(g(x)) (hệ q u ả của ví d ụ 5). 2 Ví dụ 7: N ế u f,(x) là 0(g,(x)) và f (x) là 0(g (x)) t h ì 2 2 f,(x).f (x) là 0(g,(x).g (x)). 2 2 T h ậ t vậy. theo giả t h i ế t I f,(x) Ị < c , I gi(x)! với mọi X > k i và I f (x) 2 I < C 1 g (x) 2 2 I v ố i mọi X > k. 2 Xét I f (x).f (x) I = I f,(x) I . I f ( x ) I < c,c 1 g,(x) I. I g (x) I . 1 2 2 2 2 = c,c 1 2 gl (x).g (x) I. 2 Vậy f,(x).f (x) là 0(g,(x).g (x)). v ố i c = 2 2 c,c , 2 k = max{k! , k } . 2 12
2 Ví dụ 8 : Cho f(n) nlog(n!) + n logn. với lì = ì. 2. 3 K h i đó f(n) là O(irlogn). 2 2 Thật vậy. ta có nlog(n!) là 0(n logn). còn n logn là 2 O(irlogn). T ừ ví dụ 6 ta có f(n) là 0(n logn). Ví dụ 9 : Chứng minh r ằ n g n ê u f(x) là 0(g(x)) t h ì f (x) là 0(g"(x)), ỏ đây f ( x ) = f ( x ) . f ( x ) . . . f ( x ) . ri lai Thật v ậ t , theo g i ả t h i ế t I f(x) I < c I (g(x) ị với mọi X > k. Xét | f ( x ) | = |f(x).f(x)...f(x) I n lải n n = |f(x)|.|f(x)|...|f(x)| < c | g ( x ) | n lải Vối mọi X > k. n Hay If (x) í < c I g (x) n I với m ọ i X > k, ỏ đ â y c := c . n V ậ y f ( x ) l à 0(g (x)). Ví dụ 10 : G i ả sử f(x) là 0(g(x)) với f(x). g(x) là các h à m đơn đ i ệ u t ă n g và k h ô n g giới nội. Chứng m i n h log(f(x)) là 0(log{g(x))). T h ậ t vậy, theo giả t h i ế t ta có I f(x) I < c , | g ( x ) | với m ọ i X > kị. Ta có t h ể giả t h i ế t f(x) > Ì, g(x) > Ì với X đủ l ố n hay f(x) < Cg(x) vối X đủ lớn, l ô g a n t cơ số 2 bỉt đẳng thức t r ê n ta có log(f(x)) < log(C,g(x)) logC, 4 log(g(x)) < 21og(g(x)) với X đủ lốn. Hay log f(x) là 0(log(g(x)). c) Đô phức tap thuất toán Ớ đ â y c h ú n g ta chỉ đê cập t ố i độ phức t ạ p của t h u ậ t t o á n về thòi gian t í n h t o á n m à k h ô n g đề cập tới độ phức t ạ p v ề k h ô n g gian của t h u ậ t t o á n . 13
Các phép loan được dùng đế do độ phức tạp thời gian rua thuật toán là phép so sánh số nguyên, các phép cộng. các phép trừ. các phép nhàn. các phép chia các sô nguyên hoặc bất kỳ một phép tính sơ cấp nào khác xuất hiện trong quá trình tính toán. Cần lưu ý các thuật ngữ dùng trong độ phức tạp thuật toán thường gặp : - Độ phức tạp 0(1) gọi là độ phức tạp hằng số. - Độ phức tạp 0(log n) gọi là độ phức tạp lôgarit. - Độ phức tạp 0(n) gọi là độ phức tạp tuyến tính. - Độ phức tạp O(nlogn) gọi là độ phức tạp nlogn. b - Độ phức tạp 0(n ) gọi là độ phức tạp đa thức. - Độ phức tạp 0(b") (b > 1) gọi là độ phức tạp hàm mủ. - Độ phức tạp 0(n!) gọi là độ phức tạp giai thừa. Đe minh họa về độ phức tạp của thuật toán ta xét một sô ví dị sau : Ví dụ l i . Mô tả thuật toán tìm phần tử lốn nhất trong một dãv hữu hạn các sô nguyên và tìm độ phức tạp của thuật toán đó. Bước Ì : Đ ặ t giá trị cực đại tạm thời bằng số nguyên đầu tiên của dãy. Bước 2 : So s á n h sô nguyên tiếp theo vối giá trị tạm thời, nếu nó lớn hơn giá trị cực đại tạm thòi thì đặt cực đại tạm thòi bằng số nguyên đó. Bước 3: Lặp l ạ i bước 2 (nếu còn các số nguyên trong dãy). Bước 4 : Dừng khi không còn số nguyên nào trong dãy. Khi đó cực đ ạ i t ạ m thời chính là số nguyên lốn nhất trong dãy. 14
Mò tả thượt lean tìm p h ầ n t ử lon n h ấ t trong dãv hưu hạn: Procedure MAX(a, , a 2 a : integer); n max := a, f o r ! := 2 to n do if max < a, then max := a, {max là phần tử lớn nhất} Lưu ý : M ỗ i số h ạ n g của d ã v d ù n g h a i p h é p so s á n h . m ộ t để xác định chưa đ ạ t đ ế n cuối d ã y . m ộ t đ ể xác đ ị n h có p h ả i cặp n h ậ n giá trị l ố n n h ấ t t ạ m thời hay k h ô n g . Việc so s á n h n à y được d ù n g cho m ỗ i phần t ử a, trong d ã y t ỏ p h ầ n t ử t h ứ hai trở đi (i = 2. 3. ... li). Sau đó là p h é p so s á n h để ra k h ỏ i v ò n g l ặ p . n ê n số p h é p so s á n h cần d ù n g t ấ t cả là 2(n - 1) + Ì đ ố i v ố i t h u ậ t t o á n t r ê n . V ậ v t h u ậ t t o á n t r ê n có độ phức t ạ p t h ò i gian là O(n) (độ phức t ạ p t u y ê n tính). Ví dụ 12. Mô t ả t h u ậ t t o á n x á c đ ị n h vị t r í của m ộ t p h ầ n tử trong một b ả n g l i ệ t kê sắp t h ứ t ự . B à i t o á n t ì m k i ế m được p h á t biêu n h ư sau : Xác định vị t r í của X trong b ả n g l i ệ t k ê các p h ầ n t ử p h â n biệt: a, . a 2 a„. Dưới đây ta đề cập tói t h u ậ t t o á n t ì m k i ế m t u y ê n t í n h : Mô tả thuật toán : Trước h ế t ta so s á n h X v ố i a,. nế u X = ai t h ì vị trí là Ì, còn trường hợp X í- a, ta so s á n h t i ế p X với ũ.-,. N ến X = a 2 t h ì vị trí c ủ a X là 2. c ò n t r ư ờ n g hợp X * a 2 t h ì so s á n h t i ế p X với a . Q u á t r ì n h t r ê n được t i ế p tục cho đ ế n k h i 3 nêu X = ai (i < n) t h ì vị t r í là i , t r ư ờ n g hợp X ỹt . (Vi < n) t h ì X a k h ô n g có m ặ t trong b ả n g liệt kê. lõ
Mô t ả t h u ậ t toán t ì m k i ê m t u y ê n t í n h : Procedure TIM_KIEM_TT (x: integer, a, , a , .... a : các số nguyên phân biệt): 2 n I := 1 while (i < n) and (x * a,) do ị := ị + 1; if i < n then location := i else location := 0 {location là chỉ số của số hạng bằng X (location = 0 nếu không tìm được x)}. Lưu ý : ở mỗi một bước của vòng lặp trong t h u ậ t t o á n t r ê n có hai p h é p so s á n h : một đê xem đã tới cuối dãy chưa và m ộ t p h é p so s á n h đ ể x e m p h ầ n t ử X có t r ù n g v ớ i m ộ t p h ầ n tử của b ả n g l i ệ t kê hay k h ô n g . Cuối c ù n g là một p h é p so s á n h ngoài vòng lặp. N ê u X = a t h ì có 2i + Ì p h é p so s á n h được sử dụng. Số : p h é p so s á n h l ố n n h ấ t l à 2n + Ì (khi X ^ a r i = 1. 2 li). Sau đó cần một phép so sánh để thoát khời vòng l ặ p . Vậy khi X k h ô n g có m ậ t trong b ả n g t h ì tông số p h é p so s á n h trong t h u ậ t t o á n n à y là 2n+2. V ậ y độ phức t ạ p của t h u ậ t t o á n là O(n). Xét b à i t o á n t r ê n trong trường hợp các p h ầ n t ử trong bảng được sắp theo t h ứ t ự t ă n g dần. Ví d ụ t ì m số 19 trong bảng l i ệ t kê theo t h ứ t ự t ă n g d ầ n : 1. 2. 3. 4. õ. 6, 7, 8. 10. 12. 13. l õ , 16. 17. 18. 19. 20. 22. Tổng q u á t : tìm X trong b ả n g l i ệ t kê à,, a-2 a„ với a, < a < ... < a . 2 n Đê g i ả i bài t o á n t r ê n ta d ù n g t h u ậ t t o á n nhị p h â n , được mô tả n h ư sau : So s á n h X với số h ạ n g a m ở giữa dãy (ni = [(n+l)/2], ở đây [x] là p h ầ n n g u y ê n lớn nhất k h ô n g vượt q u á x). Nêu X > a m t h ì việc t ì m k i ê m X t r ê n d ã y gồm các sô h ạ n g 16
;i a„ a,. còn lieu X ;1 thì việc tun kiêm sẽ thực hiện trên dày gồm các sô a . a : a . Ca hai trường hợp đ ề u đ ư a in đèn bài toan lìm k i ế m t r ê n bang không lớn hơn [11/2] p h ầ n tử. Quá t r ì n h t r ê n được thực hiện cho tới khi bảng l i ệ t kê chỉ còn một phần tử và so sánh X vối chính số hạng này. Mô t ả t h u ậ t t o á n t ì m k i ế m nhị p h â n : Procedure TÌM_KIÊM_NHỊ_PHÂN (x : integer, a,, a , 2 a : integers - tăng dần) n i := 1 {ị là điểm mút trái của khoảng tìm kiếm} j := n { j là điểm mút phải của khoảng tìm kiếm} while i < j begin m := [(i + j)/2] if X > a then i:= m+1 m else j := m end if X = a, then location := i else location := 0 {location là chỉ số của số hạng bằng X (location = 0 nếu không tìm thấy x)}. Lưu ý : Độ phức t ạ p c a t h u ậ t t o á n tìm k i ê m nhị p h â n t r ê n là O(logn) vì nó p h ả i d ù n g tới 2[logn] + 2 p h é p t o á n so s á n h . N h ư vậy. trong trường hợp bảng liệt kê được sắp t h ứ t ự thì t h u ậ t t o á n t ì m k i ế m n h ị p h â n t ố t hơn t h u ậ t t o á n t ì m k i ế m tuyến tính. Đe k ế t t h ú c p h ầ n n à y ta x é t ^ l ^ i ^ ị ^ i ậ t t o á n Euclid. 17
Trong lý thuyết số người ta đà chứng minh được rằng : Nêu a - bq + r, trong đó a. b, q. r là các số nguyên thì : ƯCLN(a. b) = ƯCLN(b. r) (*) Giả sử a. b là các số nguyên dương, vói a > b. Đặt r =a. 0 r,=b. Bằng cách áp dụng két quả trên ta có : r = r,q,+r 0 2 (0 < r < r,) 2 r, = r q + r 2 2 3 (0 < r < r ) 3 2 r„-2 =r n iQn Ì + r„ (0 < r < r, ) n vl r — r n-l nQn- SỐ dư xuất hiện trong dãy các phép chia liên tiếp, vì dãy các sô a = r„ > r, > r > ... > 0 không thể chứa quá a số hạng. Từ 2 (*) ta suy ra : ƯCLN(a. b) = ƯCLN(r , r,) = ƯCLN(r„ r ) = ... 0 2 ƯCLN(r„. , r„ ,) = ƯCLN(r„ „ r,0 = ƯCLN(r,„ 0) = r„. 2 Vậy ư c chung lốn nhất là số dư * 0 cuối cùng trong dãy các phép chia. Ví dụ : Tìm ƯCLN(414. 662) Áp dụng thuật toán Euclid ta được : 662 = 414.1 + 248 414 = 248.2 + 166 248= 166.1 + 82 166 = 82.2 + 2 82 = 2.41 Do đó ƯCLN(414, 662) = 2 (2 là số dư cuối cùng khác không). . ; í 18
T h u ậ t toan Euclid được mô tả n h ư sau ; Procedure UCLN(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} Lưu ý : Giá trị ban đầu của X. y tương ứng là a và b. ở m ỗ i g i a i đ o ạ n của t h ủ t ụ c X được t h a y b ằ n g y v à y được t h a y b ở i X mod y. tức là số dư r trong phép chia X cho y. Quá trình này được l ặ p l ạ i n ế u V * 0 v à t h u ậ t t o á n sẽ d ừ n g k h i V = 0. Giá t r ị của X ở đ i ể m n à y là sô dư 0 cuối c ù n g trong t h ủ tục v à c h í n h là ưộc s ố c h u n g l ố n n h ấ t c ầ n t ì m . 52. PHƯƠNG P H Á P Q U Y NẠP Q\1V nạp toán học là một phương pháp thuận tiện để chứng minh một mệnh đề có liên quan đến dãy số tự nhiên. Để chỉ ra một khẳng định là đúng vội mọi sô tự nhiên l i > n , bằng Q phương pháp quy nạp toán học thì ta phải thực hiện các bưốc sau: a) Chứng minh mệnh đề đúng vói n = n . 0 b) Giả sử mệnh đề đúng vội n = k. c) Ta chứng minh mệnh đề đúng vội l i = k+1. 19
Sau đày là một sô ví chi minh họa ('Im phương p h á p chúìiíi m i n h b à n g quy nạp t o á n học: Ví du ĩ: Chứng m i n h voi mọi n (li e N) ta có : , 22 , v ,2 .._ 11.(11 + l).(2n + 1) 1 + 2 + ... + i r - - -- - (ì) 6 T h ậ t vậy a) Với n = Ì thì hai vè b ằ n g nhau và b ằ n g 1. b) G i ả sử đẳng thức (1) đ ú n g vối m ọ i li < k. có nghĩa là voi mọi l i 1. 1.1! Ỷ 2.2! + ... 4 nai! = ( n + l ) ! - l (1) a) Với n = 1. k h i đó hai vê của (1) b ằ n g nhan liên (1) đ ú n g . b) G i ả sử (1) đ ú n g v ố i n = k có nghĩa là với mọi n < k đ ẳ n g thức sau luôn đ ú n g : 1.1! + 2.2! + ... + n.n! - ( n + l ) ! - l .