Già Làng đã viết:

ĐỀ THI MÔN LÍ THUYẾT ĐỒ THỊ

1. Liệt kê tất cả các phép toán trên đồ thị
2. Dùng phương pháp cm phản chứng để cmr: nếu n lẻ thì n2 lẻ
3. Quy nạp là gì? Vì sao phải sử dụng phương pháp quy nạp
4. Trình bày thuật ngữ đệ quy
5. Trình bày phương pháp quy nạp dạng mạnh
6. Trình bày phương pháp quy nạp dạng yếu
7. Trình bày phương pháp chứng minh trực tiếp
8. Quan hệ, hàm, phương trình, ánh xạ, công thức có tương đương hay không?
9. Lặp, đệ quy, quy nạp là tương đương nhau đương nhau đúng hay không?
10. Cm:căn bậc 2 không phải là số vô tỉ bằng pp phản chứng
11. Chạy bằng tay chu trình Euler
12. Hãy nêu cơ sở hình thành nguyên lý tối ưu
13. Vì sao thuật toán Dijikstra lại đưa ra dk không có trọng số âm,vì thuật toán Bellman Ford lại đưa ra đk không có chu trình âm.
14. Chạy bằng tay thuật toán Dijikstra.

con_ca_nho90 đã viết:

[URL="[You must be registered and logged in to see this link.] rời rạc[/URL]

1. Giả sử rằng [You must be registered and logged in to see this image.] là một [You must be registered and logged in to see this link.]. Điều đó có nghĩa là tồn tại hai [You must be registered and logged in to see this link.] a và b sao cho a / b = [You must be registered and logged in to see this image.].
   
2. Như vậy [You must be registered and logged in to see this image.] có thể được viết dưới dạng một [You must be registered and logged in to see this link.] (phân số không thể [You must be registered and logged in to see this link.] được nữa): a / b với a, b là hai số [You must be registered and logged in to see this link.] và (a / b)² = 2.
   
3. Từ (2) suy ra a² / b² = 2 và a² = 2 b².
   
4. Khi đó a² là [You must be registered and logged in to see this link.] vì nó bằng 2 b² (hiển nhiên là [You must be registered and logged in to see this link.])
   
5. Từ đó suy ra a phải là [You must be registered and logged in to see this link.] vì a² là [You must be registered and logged in to see this link.] ([You must be registered and logged in to see this link.]).
   
6. Vì a là số chẵn, nên [You must be registered and logged in to see this link.] một số k thỏa mãn: a = 2k.
   
7. Thay (6) vào (3) ta có: (2k)² = 2b² [You must be registered and logged in to see this image.] 4k² = 2b² 2k² = b².
   
8. Vì 2k² = b² mà 2k² là số chẵn nên b² là số chẵn, điều này suy ra b cũng là số chẵn (lí luận tương tự như (5).
   
9. Từ (5) và ( ta có: a và b đều là các [You must be registered and logged in to see this link.], điều này mâu thuẫn với giả thiết a / b là [You must be registered and logged in to see this link.] ở (2).
   

†War† đã viết:

[You must be registered and logged in to see this image.] là số vô tỉ đây

1. Giả sử rằng [You must be registered and logged in to see this image.] là một [You must be registered and logged in to see this link.]. Điều đó có nghĩa là tồn tại hai [You must be registered and logged in to see this link.] a và b sao cho a / b = [You must be registered and logged in to see this image.].
   
2. Như vậy [You must be registered and logged in to see this image.] có thể được viết dưới dạng một [You must be registered and logged in to see this link.] (phân số không thể [You must be registered and logged in to see this link.] được nữa): a / b với a, b là hai số [You must be registered and logged in to see this link.] và (a / b)² = 2.
   
3. Từ (2) suy ra a² / b² = 2 và a² = 2 b².
   
4. Khi đó a² là [You must be registered and logged in to see this link.] vì nó bằng 2 b² (hiển nhiên là [You must be registered and logged in to see this link.])
   
5. Từ đó suy ra a phải là [You must be registered and logged in to see this link.] vì a² là [You must be registered and logged in to see this link.] ([You must be registered and logged in to see this link.]).
   
6. Vì a là số chẵn, nên [You must be registered and logged in to see this link.] một số k thỏa mãn: a = 2k.
   
7. Thay (6) vào (3) ta có: (2k)² = 2b² [You must be registered and logged in to see this image.] 4k² = 2b² 2k² = b².
   
8. Vì 2k² = b² mà 2k² là số chẵn nên b² là số chẵn, điều này suy ra b cũng là số chẵn (lí luận tương tự như (5).
   
9. Từ (5) và ( ta có: a và b đều là các [You must be registered and logged in to see this link.], điều này mâu thuẫn với giả thiết a / b là [You must be registered and logged in to see this link.] ở (2).
   

Từ mâu thuẫn trên suy ra: thừa nhận [You must be registered and logged in to see this image.] là một [You must be registered and logged in to see this link.] là sai và phải kết luận [You must be registered and logged in to see this image.] là số vô tỉ.

con_ca_nho90 đã viết:

Giới thiệu về lập trình hướng đối tượng
[You must be registered and logged in to see this link.] [You must be registered and logged in to see this image.]

\ " n ³ n₀ : P(n)

Chứng minh tính đúng đắn của nguyên lý qui nạp trên:

Ðặt A là tập hợp các số tự nhiên n ³ n₀ mà P(n) sai. Ta chỉ cần chứng minh rằng A = Æ (tập hợp rỗng) với giả thiết rằng ta có hai khẳng định trong phần cơ sở và phần qui nạp trong nguyên lý trên. Ta sẽ chứng minh điều nầy bằng phương pháp phản chứng.

Giả sử A ¹ Æ . Theo tính chất của thứ tự trên tập số tự nhiên N (xem mệnh đề ở mục trên), A có phần tử nhỏ nhất. Gọi a là phần tử nhỏ nhất của tập hợp A. Vì P(n₀) đúng nên a ³ n₀+1, hay a-1 ³ n₀. Do a = min(A), nên a-1 ÏA và do đó P(a-1) đúng. Vì P(a-1) đúng nên ta cũng có P(a) đúng theo khẳng định ở phần qui nạp, nghĩa là ta cũng có a Ï A. Ðiều nầy cho ta một sự mâu thuẫn (vì a = min(A)).

Vậy A = Æ . Ta có điều cần chứng minh.

(cơ sở) P(n₀)

(qui nạp) " k ³ n₀ : P(n₀) Ù P(n₀+1) Ù. . . Ù P(k) ® P(k+1)

------------------------------------------------------------

\ " n ³ n₀ : P(n)

Theo các nguyên lý trên, chứng minh qui nạp bao gồm 2 bước : bước cơ sở và bước qui nạp. Ở bước cơ sở, ta phải kiểm chứng để khẳng định P(n₀) là đúng. Ở bước qui nạp, ứng với một số tự nhiên k tùy ý, ta phải chứng minh một mệnh đề kéo theo. Giả thiết trong mệnh đề kéo theo ở bước 2 được gọi là giả thiết qui nạp. Giả thiết qui nạp ở dạng qui nạp yếu là P(k), và ở dạng mạnh là P(n₀) Ù P(n₀+1) Ù. . . Ù P(k).

Nguyên lý qui nạp có rất nhiều biến thể trong việc vận dụng. Chẳng hạn, từ hai nguyên lý trên ta có thể rút ra một nguyên lý qui nạp có dạng sau đây:

(cơ sở) P(0) Ù P(1)

(qui nạp) " k ³ 1 : P(k-1) ÙP(k) Ù P(k+1)

------------------------------------------------------------

\ " n ³ 0 : P(n)

Ðặt P(n) º "x_n = 2ⁿ - 1".

Dễ thấy rằng P(0) và P(1) là đúng. Bây giờ, ta chỉ cần thực hiện bước qui nạp để hoàn thành phép chứng minh qui nạp.

Giả sử P(k-1) và P(k) đúng với một số tự nhiên (tùy ý) k ³ 1.

Thế thì x_k-1 = 2^k-1 - 1 và x_k = 2^k - 1.

Do đó x_k+1 = 3x_k - 2x_k-1

= 3(2^k - 1) - 2(2^k-1 - 1)

= 3*2^k - 3 - 2^k - 2

= 2*2^k - 1

= 2^k+1 - 1

Suy ra P(k+1) đúng.

Vậy theo nguyên lý qui nạp (dạng biến thể được phá biểu ở trên) ta kết luận: P(n) đúng với mọi n ³ 0.

Chứng minh trực tiếp là phương pháp chứng minh suy diễn trực tiếp dẫn từ giả thiết đến kết luận thông qua việc áp dụng các luật suy diễn (hay qui tắc suy diễn), các định lý, các nguyên lý và các kết quả đã biết. Ðây là một kiểu tư duy giải bài toán rất tự nhiên và người ta thường xuyên sử dụng. Trong khi suy nghĩ để tìm ra cách chứng minh theo phương pháp nầy người ta thường phải tự trả lời các câu hỏi sau đây:

[You must be registered and logged in to see this image.] Ta sẽ dùng luật suy diễn nào?

Các định lý nào, các kết qua nào có thể sử dụng được đề ta suy ra được một điều gì đó từ những sự kiện, những yếu tố hiện đang có?

Việc áp dụng định lý có khả năng sẽ dẫn đến kết luận hay kết quả mong muốn hay không?

Trong trường hợp ở một bước suy diễn nào đó có nhiều định lý hay nhiều luật nào đó có thể áp dụng được và cũng có kkhả năng sẽ dẫn đến kết luận hay kết quả mong muốn thì ta sẽ chọn cái nào?

Ðến một giai đoạn nào đó, khi gặp phải sự bế tắc thì ta sẽ phải tự hỏi rằng phải chăng bài toán không có lời giải, hay vì kiến thức của ta chưa đủ, hay ta phải sử dụng một phương pháp chứng minh nào khác?

Quả thật là không thể trả lời được các câu hỏi một cách đầy đủ và chính xác. Nó phụ thuộc chủ yếu vào kiến thức, kinh nghiệm của người giải bài toán và cả sự nhạy bén, tính năng động sáng tạo của họ. Tuy nhiên Những câu hỏi trên cho ta một sự định hướng chung của quá trình suy nghĩ. Ngoài ra, cũng cần nói thêm rằng chúng là cơ sở cho việc phát triển các hệ chương trình trợ giúp giải toán một cách "thông minh" trên máy tính được thiết kế theo phương pháp chứng minh nầy.

Dưới đây, chúng ta sẽ xem xét một 2 ví dụ về phương pháp chứng minh trực tiếp.

Ví dụ 1: Giả sử p, r, s, t, u là các mệnh đề sau cho ta có các mệnh đề sau đây la` đúng:

(1) p r

(2) r s

(3) t Ú Ø s

(4) Ø t Ú u

(5) Ø u.

Hãy chứng minh mệnh đề p là sai, tức là chứng minh mệnh đề ? p la` đúng.

Chứng minh:

Áp dụng luật suy diễn tam đoạn luận, từ (1) và (2) ta suy ra:

(6) p s

Áp dụng luật logic về phép toán kéo theo ta có thể viết lại (3) dưới dạng:

(7) s t

Áp dụng luật suy diễn tam đoạn luận, từ (6) và (7) ta suy ra:

( p t

Áp dụng luật logic về phép toán kéo theo ta có thể viết lại (4) dưới dạng:

(9) t u

Áp dụng luật suy diễn tam đoạn luận, từ ( và (9) ta suy ra:

(10) p u

Áp dụng luật suy diễn Modus Tollens, từ (10) và (5) ta suy ra:

(11) Ø p

Vậy mệnh đề Ø p la` đúng.

[You must be registered and logged in to see this image.] Ví dụ 2: Cho p(x), q(x) và r(x) là các vị từ theo biến x (x Î A), và a là một phần tử cố định nhưng tùy ý của tập hợp A. Giả sử ta có các mệnh đề sau đây la` đúng:

(1) " x Î A : p(x) q(x)

(2) " x Î A : q(x) r(x)

(3) p(a)

Chứng minh rằng mệnh đề r(a) la` đúng.

Chứng minh:

Áp dụng kết quả trong mệnh đề 2, Bài 2, mục 2.5, từ (1) và (2) ta suy ra:

(4) " x Î A : p(x) r(x)

Áp dụng kết quả trong mệnh đề 1, Bài 2, mục 2.5, từ (3) và (4) ta suy ra:

(5) r(a)

Vậy mệnh đề r(a) la` đúng.

[You must be registered and logged in to see this image.] Tính xác định.

Tính hữu hạn hay tính dừng.

Tính đúng.

Tuy nhiên có những trường hợp việc tìm ra một thuật toán với những tính chất đòi hỏi như trên rất khó khăn nhưng có cách giải có thể vi phạm các tính chất của thuật toán nhưng lại khá đơn giản và được chấp nhận. Ví dụ những trường hợp bài toán có thể được phân tích và đưa tới việc giải một bài toán cùng loại nhưng cấp độ thấp hơn, chẳng hạn cở dữ liệu nhập nhỏ hơn, giá trị cần tính toán nhỏ hơn, v.v.... Ta cũng thường thấy những định nghĩa về những đối tượng, những khái niệm dựa trên chính những đối tượng, những khái niệm đó như những ví dụ dưới đây.

Ví dụ 1: Ðịnh nghĩa giai thừa.

Giai thừa của một số tự nhiên n, ký hiệu là n!, được định nghĩa bằng cách qui nạp như sau:

0! = 1,

n! = (n-1)!*n, với mọi n > 0.