Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


7. Implementation von Algorithmen



Übungen

  1. Wie lange dauert das Zählen bis 100000? Schätzen Sie, wieviel Zeit das Programm j:=0; for i:=1 to 100000 do j:=j+1 auf Ihrer Anlage brauchen würde, und lassen Sie dann das Programm durchlaufen, um Ihre Schätzung zu überprüfen.
  2. Beantworten Sie die obige Frage bei Verwendung von repeat und while.
  3. Schätzen Sie, indem Sie das Programm für kleine Werte durchlaufen lassen, wie lange die Implementation des Siebs des Eratosthenes aus Kapitel 3 für einen Durchlauf mit N = 1000000 benötigen würde (wenn genug Speicherplatz vorhanden wäre).
  4. »Optimieren« Sie die Implementation des Siebs des Eratosthenes aus Kapitel 3 mit dem Ziel, innerhalb von 10 Sekunden Rechenzeit eine möglichst große Primzahl zu finden.
  5. Überprüfen Sie die im Text aufgestellte Behauptung, daß die Beseitigung der Rekursion aus dem Algorithmus für die Preorder-Traversierung eines Baumes aus Kapitel 5 (mit Prozeduraufrufen für Stapel-Operationen) das Programm langsamer macht.
  6. Überprüfen Sie die im Text aufgestellte Behauptung, daß die Beseitigung der Rekursion aus dem Algorithmus für die Preorder-Traversierung eines Baumes aus Kapitel 5 (und das lineare Implementieren der Stapel-Operationen) das Programm schneller macht.
  7. Untersuchen Sie das Assemblerprogramm, welches vom Pascal-Compiler Ihres Rechners für den rekursiven Algorithmus für die Preorder-Traversierung eines Baumes aus Kapitel 5 erzeugt wird.
  8. Entwickeln Sie ein Experiment, um zu testen, ob auf Ihrem Rechner die Implementation eines Stapels als verkettete Liste oder als Feld effizienter ist.
  9. Was ist effizienter, das nichtrekursive oder das rekursive Verfahren für das Zeichnen eines Lineals aus Kapitel 5?
  10. Wieviele zusätzliche Operationen des Ablegens auf dem Stapel benötigt die in Kapitel 5 angegebene nichtrekursive Implementation, wenn ein vollständiger Baum mit 2n - 1 Knoten nach dem Preorder-Prinzip traversiert wird?


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]