Einführung SS09

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Absolut unlösbare Probleme 2 Praktische unlösbare Probleme 2.1 Beispiel: Schachspiel 2.2 Ackermann-Peter-Funktion 3 Empirische Analyse 4 Bit- vs. uniforme Komplexität 5 Beispiel: Multiplikation a la Russe 6 Probleminstanzen und Analyseformen 7 Vergleich von Aufwänden

Absolut unlösbare Probleme

• Theoretische Informatik: Es gibt absolut unlösbare Probleme (Beispiel: Halteproblem, s. Lehrveranstaltung Programmierparadigmen)

Praktische unlösbare Probleme

• Algorithmus zur Lösung bekannt, meist sogar recht einfach; aber Prozess zur Ermittlung dieser Lösung erfordert eine Zeit, die jegliche Grenzen sprengt.

Beispiel: Schachspiel

• Baum aller Schachspiele ist endlich und kann (theoretisch) angegeben werden. Praktisch unmöglich.

Ackermann-Peter-Funktion

• Hier kann man immer wieder Argumente finden, die dazu führen, dass man für in zumutbarer Zeit keinen Wert erhält.

(define AP (lambda (x y) (cond ((= x 0) (+ y 1)) ((= y 0) (AP (- x 1) 1)) (else (AP (- x 1)(AP x (- y 1)))))))

(AP 2 3)

ausführen

Sehr weit kommt man nicht, wenn man eine entsprechende x-y-Tabelle mit Werten der AP-Funktion ausfüllen möchte.

(require-library 'sisc/libs/srfi/srfi-28) (import srfi-28)

(do ((x 0 (+ x 1))) ((= x 4) (newline)) (do ((y 0 (+ y 1))) ((= y 4) (newline)) (display (format "~a " (AP x y)))))

ausführen

Empirische Analyse

• Problemgröße feststellen und Aufwandsfunktion anstreben.

Bit- vs. uniforme Komplexität

• Frage nach den elementaren (oder atomaren) Rechenoperationen: Addition oder Multiplikation beliebiger natürlicher Zahlen. Was soll eine Elementaroperation sein? Sie muss unabhängig von der Wortbreite (= codierte Eingabe) mit konstantem Aufwand (Zeit) stattfinden. Antwort: Dies muss von Fall zu Fall entschieden werden. Beispiel: Moderne Rechner erledigen komplette Addition/Multiplikation höchstens -stelliger ganzer Zahlen mit konstanter Zeit. Dann reicht das uniforme Komplexitätsmaß. Die damit verbundene theoretische Basis bildet die Registermaschine. Anderenfalls muss eine Bit-basierte Betrachtung durchgeführt werden. Dabei ist die Multiplikation zweier -stelliger Zahlen aufwendiger als deren Addition. Die theoretische Grundlage bildet die Turingmaschine.

• Die Wahl der Basis des Stellenwertsystems hat keinen Einfluss auf die Größenordnung des Aufwandes, d.h. lediglich ein konstanter Faktor ist zu berücksichtigen. Nachrechnen!

Beispiel: Multiplikation a la Russe

Multipliziere zwei natürliche Zahlen und indem du und jedes sich ergebende Zwischenergebnis fortgesetzt ganzzahlig halbierst und fortgesetzt multiplizierst. Schreibe die Zwischenwerte jeweils unter bzw. . Setze das Verfahren solange fort, bis in der -Spalte die Zahl 1 steht. Streiche alle Zeilen in der -Spalte, in denen unter und einschl. je eine gerade Zahl steht. Addiere die in der -Spalte ungestrichenen Zahlen. Diese Summe ist das Produkt aus und .

43 *  14 =  602
21    28
10    56 streichen
 5   112
 2   224 streichen
 1   448
     ---
     602

Aufgabe: Beweisen Sie, dass dieses Verfahren tatsächlich das gesuchte Produkt aus und berechnet.

Empirische Effizienzanalyse des Verfahrens a la Russe

Das oben beschriebene Verfahren wird mit folgender Scheme-Prozedur adäquat beschrieben.

(define product (lambda (a b) (letrec ((helper (lambda (a b) (cond ((= a 1) (list b)) ((odd? a) (cons b (helper (/ (- a 1) 2) (* b 2)))) (else (helper (/ a 2) (* b 2))))))) (apply + (helper a b)))))

(product 43 14)

ausführen

Für eine Aufwandsanalyse auf Basis der Bit-Komplexität sind Elementaroperationen zu identifizieren: left shift (lsh), right shift (rsh) arbeiten mit linearem Aufwand bezogen auf die Wortbreite der binär codierten Eingabezahlen.

(define lsh (lambda (ls) (if (null? ls) (list 0) (cons (car ls) (lsh (cdr ls)))))) (define rsh (lambda (ls) (if (null? (cdr ls)) '() (cons (car ls)(rsh (cdr ls))))))

(lsh '(1 0 1 1))

ausführen

(rsh '(1 0 1 1))

ausführen

my-odd arbeitet ebenfalls mit linearem Aufwand bezogen auf die Wortbreite.

(define my-odd? (lambda (ls) (if (null? (cdr ls)) (= (car ls) 1) (my-odd? (cdr ls)))))

(my-odd? '(1 0 1 0))

ausführen

helper sammelt alle zu addierenden Zahlen (Bitlisten). binadd sorgt für deren Addition, wobei allbinadd die weiter unten definierte Prozedur adder verwendet.

Aufgabe: Implementieren Sie die noch erforderlichen Prozeduren. Hinweis: Damit Sie die empirische Untersuchung unabhängig davon fortsetzen können, werden diese Prozeduren in Hintergrund bereitgestellt, sodass Anwendungen der folgenden Prozedur product-binary entsprechende Resultate erzeugen.

;;; Aufgabe 1.4 ;; Listenumkehr mit linearem Aufwand (Anzahl der rekursiven Aufrufe ; ist gleich Anzahl der Listenelemente) ; my-reverse brauchen wir, da die (Binaer-)Addition zweier Zahlen ; von hinten (rechts) nach vorn (links) arbeitet. (define my-reverse (lambda (ls) (letrec ((helper (lambda (ls res) (if (null? ls) res (helper (cdr ls) (cons (car ls) res)))))) (helper ls '())))) ;; binadd sieht gefaehrlich aus, ist aber in Wirklichkeit straightforward. ; Die Zahldarstellung erfolgt OHNE Vornullen! (define binadd (lambda (a b) (letrec ((helper (lambda (rev-a rev-b carry) (cond ((and (null? rev-a) (null? rev-b)) (list carry)) ((null? rev-a) (let ((res (adder 0 (car rev-b) carry))) ; res ist ein Paar (s. adder) (cons ; bildet die Liste ... (car res) ; ... mit dem car-Element des Paars ... (helper rev-a (cdr rev-b) (cdr res))))) ; ... und der Folgeliste ((null? rev-b) (let ((res (adder (car rev-a) 0 carry))) (cons (car res) (helper (cdr rev-a) rev-b (cdr res))))) (else ; weder rev-a noch rev-b sind leere Listen (let ((res (adder (car rev-a) (car rev-b) carry))) (cons (car res) (helper (cdr rev-a) (cdr rev-b) (cdr res))))))))) (my-reverse (helper (my-reverse a) (my-reverse b) 0))))) ; Uebertrag = 0 ; die Ergebnisliste wird umgekehrt (define allbinadd (lambda (ls) (cond ((null? ls) '()) ((null? (cdr ls)) (car ls)) (else (binadd (car ls)(allbinadd (cdr ls)))))))

(define product-binary (lambda (a b) (letrec ((helper (lambda (a b) (cond ((null? (cdr a)) (list b)) ((my-odd? a) (cons b (helper (rsh a) (lsh b)))) (else (helper (rsh a) (lsh b))))))) (allbinadd (helper a b)))))

adder imitiert die Arbeit eines Volladders (Bit 1, Bit 2 und Übertrag). Die globale Variable calls wird für die Zählung der als elementar anzusehenden Adder-Operationen benötigt.

(define calls 0) ; Zaehlung der Elementaroperationen (define adder (lambda (a b c) (set! calls (+ calls 1)) ; Inkremt. von calls (cond ((and (= a 0)(= b 0)(= c 0)) (cons 0 0)) ((or (and (= a 0)(= b 0)(= c 1)) ; 0 + 0 + 1 = (1 . 0) (and (= a 0)(= b 1)(= c 0)) ; 0 + 1 + 0 = (1 . 0) (and (= a 1)(= b 0)(= c 0))) ; 1 + 0 + 0 = (1 . 0) (cons 1 0)) ((or (and (= a 1)(= b 1)(= c 0)) ; 1 + 1 + 0 = (0 . 1) (and (= a 1)(= b 0)(= c 1)) ; 1 + 0 + 1 = (0 . 1) (and (= a 0)(= b 1)(= c 1))) ; 0 + 1 + 1 = (0 . 1) (cons 0 1)) (else (cons 1 1))))) ; ... = (1 . 1)

Nun können wir product-binary ausprobieren.

(display (product-binary '(1 1 1) '(1 0 1 1 0))) (newline) (display calls)

ausführen

Hinweis: In Scheme können die Dualzahlen auch direkt durch ein vorangestelltes b angegeben werden.

#b111

ausführen

Die auf diese Weise für ausgewählte gewonnenen Rechnenzeiten können nun grafisch dargestellt werden.

Ein quadratischer Aufwand lässt sich erahnen. Eine verfeinerte empirische bzw. eine theoretische Analyse bestätigen dies. Damit ist diese Methode prinzipiell nicht besser als die Schulbuchmethode. Sind die Stelligkeiten der beiden Faktoren in etwas gleich groß, wird der Aufwand des a-la-Russe-Verfahrens durch nach oben beschränkt.

Probleminstanzen und Analyseformen

• Für jedes Programm für Probleminstanzen anwenden
• Je nach Analyseform den größten oder kleinsten bzw. das arithmetische Mittel der Werte nehmen.

Analyseformen sind

Worst-case-Analyse: Nimm die größte aller Instanzenzeiten.

Averege-case-Analyse: Nimm das arithmetische Mittel aller Instanzenzeiten.

Best-case-Analyse: Nimm die kleinste aller Instanzenzeiten.

Vergleich von Aufwänden

• Hierfür muss man sehr oft nichtlineare Gleichungen lösen. Dies wird im Allg. interativ (Newton, Picard) erledigt.