Python - Biện minh thuật toán

Để đưa ra tuyên bố về một Thuật toán là hiệu quả, chúng ta cần một số công cụ toán học làm bằng chứng. Những công cụ này giúp chúng tôi đưa ra lời giải thích thỏa mãn về mặt toán học về hiệu suất và độ chính xác của các thuật toán. Dưới đây là danh sách một số công cụ toán học có thể được sử dụng để biện minh cho một thuật toán này hơn một thuật toán khác.

• Direct Proof:

  Đó là xác minh trực tiếp của tuyên bố bằng cách sử dụng các tính toán trực tiếp. Ví dụ tổng của hai số chẵn luôn luôn là một số chẵn. Trong trường hợp này, chỉ cần thêm hai số bạn đang điều tra và xác minh kết quả là chẵn.

• Proof by induction:

  Ở đây chúng ta bắt đầu với một ví dụ cụ thể của một chân lý và sau đó khái quát hóa nó thành tất cả các giá trị có thể là một phần của chân lý. Cách tiếp cận là lấy một trường hợp sự thật đã được xác minh, sau đó chứng minh nó cũng đúng cho trường hợp tiếp theo với cùng một điều kiện nhất định. Ví dụ, tất cả các số dương có dạng 2n-1 đều là số lẻ. Chúng ta chứng minh nó cho một giá trị nào đó của n, sau đó chứng minh nó cho giá trị tiếp theo của n. Điều này thiết lập tuyên bố nói chung là đúng bằng bằng chứng quy nạp.

• Proof by contraposition:

  Chứng minh này dựa trên điều kiện Nếu Không A ngụ ý Không phải B thì A ngụ ý B. Một ví dụ đơn giản là nếu bình phương của n là chẵn thì n phải chẵn. Vì nếu bình phương trên n không chẵn thì n không chẵn.

• Proof by exhaustion:

  Điều này tương tự như chứng minh trực tiếp nhưng nó được thiết lập bằng cách xem xét từng trường hợp riêng biệt và chứng minh từng trường hợp đó. Một ví dụ về chứng minh như vậy là định lý bốn màu.