AuK/Einführung SS09
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
==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 <math>x,y</math> finden, die dazu führen, dass man für <math>AP(x,y)</math> in zumutbarer Zeit keinen Wert erhält.
<code id="4b9f7abf090a0">
(define AP
(lambda (x y)
(cond
((= x 0) (+ y 1))
((= y 0) (AP (- x 1) 1))
(else
(AP (- x 1)(AP x (- y 1)))))))
</code>
<eval id="4b9f7abf098a8">
(AP 2 3)
</eval>
Sehr weit kommt man nicht, wenn man eine entsprechende x-y-Tabelle mit Werten der AP-Funktion ausfüllen möchte.
<code id="4b9f8212ecfc3" hidden>
(require-library 'sisc/libs/srfi/srfi-54)
(import srfi-54)
</code>
<eval id="4b9f8212ed7a7">
(do ((x 0 (+ x 1)))
((= x 4) (newline))
(do ((y 0 (+ y 1)))
((= y 4) (newline))
(display (cat (AP x y) 6))))
</eval>
<popup name="Hinweis"><nowiki>cat</nowiki> sorgt für die Formatierung. Man entnimmt das Sprachelement der SRFI-54.</popup>
==Empirische Analyse==
* Problemgröße <math>n</math> feststellen und Aufwandsfunktion <math>T(n)=f(n)</math> 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 <math>k</math>-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 <math>k</math>-stelliger Zahlen aufwendiger als deren Addition. Die theoretische Grundlage bildet die Turingmaschine.
* Die Wahl der Basis <math>b</math> 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 <math>a</math> und <math>b</math> indem du <math>a</math> und jedes sich ergebende Zwischenergebnis fortgesetzt ganzzahlig halbierst und <math>b</math> fortgesetzt multiplizierst. Schreibe die Zwischenwerte jeweils unter <math>a</math> bzw. <math>b</math>. Setze das Verfahren solange fort, bis in der <math>a</math>-Spalte die Zahl 1 steht.
Streiche alle Zeilen in der <math>b</math>-Spalte, in denen unter <math>a</math> und einschl. <math>a</math> je eine gerade Zahl steht. Addiere die in der <math>b</math>-Spalte ungestrichenen Zahlen. Diese Summe ist das Produkt aus <math>a</math> und <math>b</math>.
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 <math>a</math> und <math>b</math> berechnet.
====Empirische Effizienzanalyse des Verfahrens a la Russe====
Das oben beschriebene Verfahren wird mit folgender Scheme-Prozedur adäquat beschrieben.
<code id="4ba0a0404c14b">
(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)))))
</code>
<eval id="4ba0a0404f521">(product 43 14)</eval>
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.
<code id="4ba0a0404cce9">
(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))))))
</code>
<eval id="4ba0a0404fcaf">(lsh '(1 0 1 1))</eval>
<eval id="4ba0a0405047f">(rsh '(1 0 1 1))</eval>
<nowiki>my-odd</nowiki> arbeitet ebenfalls mit linearem Aufwand bezogen auf die Wortbreite.
<code id="4ba0a0404d555">
(define my-odd?
(lambda (ls)
(if (null? (cdr ls))
(= (car ls) 1)
(my-odd? (cdr ls)))))
</code>
<eval id="4ba0a04050c5d">(my-odd? '(1 0 1 0))</eval>
<nowiki>helper</nowiki> sammelt alle zu addierenden Zahlen (Bitlisten). <nowiki>allbinadd</nowiki> sorgt
für deren Addition, wobei <nowiki>allbinadd</nowiki> die weiter unten definierte Prozedur <nowiki>adder</nowiki> verwendet.
<code id="4ba0a0404e1a1">
(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)))))
</code>
<nowiki>adder</nowiki> imitiert die Arbeit eines Volladders (Bit 1, Bit 2 und Übertrag). Die globale Variable
<nowiki>calls</nowiki> wird für die Zählung der als elementar anzusehenden Adder-Operationen benötigt.
<code id="4ba0a0404ed17">
(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)
</code>
<code id="4ba0a0b2b14a1">
<gnuplot>
set xlabel "n"
set ylabel "T(n)"
set data style lines
plot \
<dataset>
10 105
60 2570
110 11640
160 27885
210 41715
260 73269
310 100959
360 143735
410 174574
460 242307
510 301169
560 357982
610 422730
660 519390
710 591507
760 645435
810 711284
860 865909
910 919575
960 988310
</dataset>
</gnuplot>
</code>
==Probleminstanzen und Analyseformen==
* Für jedes <math>n</math> Programm für <math>k</math> 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.