Vollständige Induktion |
| 18.04.2016, 13:05 | Hans Hansen | Auf diesen Beitrag antworten » |
für die folgende Aufgabenstellung: " Beweisen Sie, dass jede Strategie für das Splitten im logarithmischen Bitsummen- Algorithmus (also nicht nur die Halbierung) n - 1 Additionen erfordert." (für den Fall, dass es von Bedeutung ist: in diesem Algorithmus werden die 1'sen innerhalb einer Bitsumme gezählt. Dies geschieht mit dem Divide and Conquer Prinzip, sprich die Bitsumme in jeweils zwei Bereiche aufteilen, bis jeweils nur ein Bit in dem jeweiligen Unterbereich vorhanden ist, dann die Bitsummen mittels Additionsschritten bilden.) möchte ich einen Beweis mittels der vollständigen Induktion durchführen, mein Ansatz bisher: Zu zeigen: S(n) = n – 1 für alle n > 0 mit I.A. (n = 1) S(1) = 1 – 1 = 0 Additionsschritte I.V.: Die Aussage gelte für alle Werte bis einschließlich n. I.S. (n -> n + 1): Es gilt: S(n+1) = (n + 1) – 1 Jetzt frage ich mich zunächst, ob es korrekt ist, von "S(n) = n - 1" auszugehen, da die Aufgabenstellung hier keinen konkreten Ansatz für die Induktion bereitstellt. Falls es so richtig ist, frage ich mich, wie ich beim Induktionsschritt weiter vorgehen soll - ich würde nun davon ausgehen, dass man S(n+1) aufteilen kann, bzw. das '+1' auf irgendeine Art extrahieren muss, um zum Ziel zu gelangen. Leider will mir gerade nicht klar werden, wie soetwas aussehen würde :-( PS: Es ist definitiv möglich, diese Aufgabenstellung auch ohne die vollständige Induktion zu lösen, allerdings wurde uns gesagt, dass es auf diese Art sehr elegant zu lösen sei und ich habe ganz offensichtlich noch gewisse Probleme mit diesem Prinzip, daher würde ich es gerne auf diesem Wege üben :-). Lg Hans Hansen Zwei Beiträge zusammengefasst. Steffen |
||
| 18.04.2016, 17:10 | HAL 9000 | Auf diesen Beitrag antworten » |
Im Induktionsschritt musst du eine beliebige (!) Zerlegung von Bits in zwei nichtleere Teilbereiche, also mit und betrachten. Für diese Aufteilung benötigst du demnach Additionen: für die hier vorgenommene Aufteilung für die Anzahl Additionen in dem einen Teilbaum für die Anzahl Additionen in dem anderen Teilbaum Und nun die Induktionsvoraussetzung anwenden... |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
