AuK/Einführung SS09

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>

<popup name="cat">Hinweis: <nowiki>cat</nowiki> sorgt für die Formatierung. Man entnimmt das Sprachelement der SRFI-54.</popup>
<code id="4b9f8212ecfc3" hidden>
(require-library 'sisc/libs/srfi/srfi-54)
(import srfi-54)
</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.

<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>



===Beispiel: Multiplikation a la Russe===


Hier stehen die Scheme-Prozeduren.



<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>