Gesamtkosten des Zählens < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:41 Mo 13.02.2006 | | Autor: | nevinpol |
| Aufgabe | Beweisen Sie den unten angegeben Satz mit Hilfe der Bankkontenmethode:
Die Gesamtkosten des Zählens von $0$ nach $n$ sind durch $2n$ beschränkt. |
Hallo,
die Lösung vom Tut lautet:
$ n [mm] \cdot \summe_{i=0}^{n} \bruch{1}{2^i}$ [/mm] konvergiert zu $2n$
Frage 1. Warum konvergiert es denn überhaupt gegen $2n$?
Frage 2. Warum zähle ich denn z.B. für $n=4$:
$4 [mm] \cdot (\bruch{1}{2^0}+\bruch{1}{2^1}+\bruch{1}{2^2}+\bruch{1}{2^3}+\bruch{1}{2^4})$
[/mm]
Vielen Dank für Eure Postings
Nevinpol
|
|
| |
|
Hallo und guten Morgen,
zur Frage 1: Die Reihe [mm] \sum_{i=0}^{\infty}2^{-i} [/mm] konvergiert gegen 2, dass sollte aus der Analysis
bekannt sein. Es gilt naemlich
[mm] \sum_{i=0}^n2^{-i}=i\frac{2^{-(n+1)}-1}{2^{-1}-1}=2\cdot (1-2^{-(n+1)})\:\rightarrow 2\:\: (n\to\infty)
[/mm]
Zu Frage 2: ich kenne leider den Begriff Bankkontenmethode nicht, aber gemeint sein sollte ein Schluss der folgenden
Art: Um von 0 auf n zu zaehlen, muss man n mal den Zaehler erhoehen. Dabei muss man jedes Mal die letzte Stelle
durchlaufen, [mm] n\cdot 2^{-1} [/mm] mal die vorletzte, [mm] n\cdot 2^{-2} [/mm] mal die vorvorletzte usw. (bei Binaerdarstellung und
im TM-Modell, nicht wahr ?).
Allerdings braucht man bei einem Zaehler bis zur Zahl n in Binaerdarstellung nur [mm] \log [/mm] (n) Bits, so dass
ich da die Summe [mm] n\cdot \sum_{i=0}^{\log (n)}2^{-i}=n\cdot \frac{2^{\log (n)+1}-1}{2^{-1}-1}=2n\cdot (1-2^{-\log (n)-1})
[/mm]
betrachten wuerde - kommt asymptotisch auf dasselbe heraus.
Viele Gruesse,
Mathias
|
|
|
|
