Einführung SS09

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 x,y finden, die dazu führen, dass man für AP(x,y) in zumutbarer Zeit keinen Wert erhält.

<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)))</eval>

   ((= x 4) (newline))
 (do ((y 0 (+ y 1))) 
     ((= y 4) (newline))
   (display (cat (AP x y) 6))))

Empirische Analyse

• Problemgröße n feststellen und Aufwandsfunktion T(n)=f(n) 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 k-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 k-stelliger Zahlen aufwendiger als deren Addition. Die theoretische Grundlage bildet die Turingmaschine.

• Die Wahl der Basis b 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 a und b indem du a und jedes sich ergebende Zwischenergebnis fortgesetzt ganzzahlig halbierst und b fortgesetzt multiplizierst. Schreibe die Zwischenwerte jeweils unter a bzw. b. Setze das Verfahren solange fort, bis in der a-Spalte die Zahl 1 steht. Streiche alle Zeilen in der b-Spalte, in denen unter a und einschl. a je eine gerade Zahl steht. Addiere die in der b-Spalte ungestrichenen Zahlen. Diese Summe ist das Produkt aus a und b.

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 a und b berechnet.

Empirische Effizienzanalyse des Verfahrens a la Russe

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

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

<eval id="4ba0a0404fcaf">(lsh '(1 0 1 1))</eval> <eval id="4ba0a0405047f">(rsh '(1 0 1 1))</eval>

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

<eval id="4ba0a04050c5d">(my-odd? '(1 0 1 0))</eval>

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

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.

Probleminstanzen und Analyseformen

• Für jedes n Programm für k 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.