Python - Algorithmusbegründung

Um Aussagen über die Effizienz eines Algorithmus zu machen, benötigen wir einige mathematische Werkzeuge als Beweis. Diese Tools helfen uns dabei, die Leistung und Genauigkeit der Algorithmen mathematisch zufriedenstellend zu erklären. Nachfolgend finden Sie eine Liste einiger dieser mathematischen Werkzeuge, mit denen ein Algorithmus gegenüber einem anderen gerechtfertigt werden kann.

• Direct Proof:

  Es ist eine direkte Überprüfung der Aussage unter Verwendung der direkten Berechnungen. Zum Beispiel ist die Summe von zwei geraden Zahlen immer eine gerade Zahl. In diesem Fall addieren Sie einfach die beiden Zahlen, die Sie untersuchen, und überprüfen Sie das Ergebnis als gerade.

• Proof by induction:

  Hier beginnen wir mit einer bestimmten Instanz einer Wahrheit und verallgemeinern sie dann auf alle möglichen Werte, die Teil der Wahrheit sind. Der Ansatz besteht darin, einen Fall von verifizierter Wahrheit zu nehmen und dann zu beweisen, dass dies auch für den nächsten Fall für dieselbe gegebene Bedingung gilt. Zum Beispiel sind alle positiven Zahlen der Form 2n-1 ungerade. Wir beweisen es für einen bestimmten Wert von n und dann für den nächsten Wert von n. Dies legt die Aussage durch Induktionsnachweis als allgemein wahr fest.

• Proof by contraposition:

  Dieser Beweis basiert auf der Bedingung Wenn nicht A nicht B impliziert, dann impliziert A B. Ein einfaches Beispiel ist, wenn das Quadrat von n gerade ist, muss n gerade sein. Denn wenn das Quadrat auf n nicht gerade ist, ist n nicht gerade.

• Proof by exhaustion:

  Dies ähnelt einem direkten Beweis, wird jedoch festgestellt, indem jeder Fall einzeln besucht und jeder von ihnen bewiesen wird. Ein Beispiel für einen solchen Beweis ist der Vierfarbensatz.