19
Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen Achtung: Vorlesung in der nächsten Woche, am 28.10. um 12.15 in P72.01 !!! Am kommenden Freitag findet die Zentralübung statt.

Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Embed Size (px)

Citation preview

Page 1: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 1

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Einführung in Berechenbarkeit und Formale Sprachen

Achtung: Vorlesung in der nächsten Woche,

am 28.10. um 12.15 in P72.01 !!!

Am kommenden Freitag findet die Zentralübung statt.

Page 2: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 2

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätThemen der Vorlesung

- Berechenbarkeit

- Automaten und Formale Sprachen

- Komplexitätstheorie

Page 3: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 3

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Berechenbarkeit

Was ist ein Algorithmus?

Welche Funktionen sind berechenbar?

Welche nicht?

Page 4: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 4

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Komplexitätstheorie

Wieviel Speicherplatz / Rechenzeit benötigt

man zur Berechnung einer (berechenbaren)

Funktion?

höchstens? Effizienten Algorithmus angeben,

vgl. DuA

mindestens? Untere Schranke beweisen, Funktionen

klassifizieren nach ihrer Komplexität

Page 5: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 5

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Automatentheorie und Formale Sprachen

- Wie beschreibt man Sprachen

Grammatiken

- Wie entscheidet man dann: (Wortproblem, Kern der Syntaxanalyse)

Automaten

Page 6: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 6

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Theorie der Programmierung

- Wie beschreibt man Semantik?

- Wie verifiziert man Korrektheit von Programmen?

etwas in Modellierung, Hauptstudium.

Page 7: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 7

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätDrei grundlegende Techniken

- Simulation

- Reduktion

- Diagonalisierung

Page 8: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 8

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätSimulation

- ein Verfahren, wie ein in einem Formalismus

beschriebenes Programm durch ein in einem

anderen Formalismus beschriebenes Programm

ersetzt werden kann, so dass das Ein/Ausgabe-

verhalten unverändert bleibt.

- Bsp: Simulation eines Programms, in dem

FOR-Schleifen erlaubt sind, durch eins, in dem

nur WHILE-Schleifen erlaubt sind.

Page 9: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 9

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

LOOP- und WHILE-Programme

LOOP-Programme: nur For-Schleifen erlaubt, keine bedingten Sprünge, keine Prozeduren etc.

WHILE-Programme: auch WHILE-Schleifen erlaubt (und auch Prozeduren,….)

WHILE-Programme beschreiben ein universelles Rechenmodell.

- Jedes LOOP-Programm kann durch ein WHILE-Programm simuliert werden.

- Umgekehrt??

Page 10: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 10

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

LOOP- und WHILE-Programme

Die folgende Funktion ack: N x N kann durch

WHILE- aber nicht durch LOOP-Programme

berechnet werden.

ack (0, m) = m + 1

ack (n, 0) = ack (n-1, 1), falls n 1,

ack (n, m) = ack (n-1, ack (n, m–1)), falls n, m 1

ack wächst sehr schnell !!

Page 11: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 11

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Diagonalisierung

geht zurück auf Cantor‘sche Diagonalisierungsverfahren,

eng verwandt mit den Paradoxien z. B. von Russel.

Es gibt kein Programm HALTEN, das bei Eingabe eines

Programms P und einer Eingabe x für P entscheidet, ob P

gestartet mit x anhält.

Das Halteproblem ist nicht entscheidbar.

Page 12: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 12

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Diagonalisierung

Beweis durch Widerspruch:

Annahme: Es gibt Programm „Halten(P,x)“, das bei Eingabe P,x entscheidet, ob P gestartet mit x hält.

Dann gibt es auch folgendes Programm:

Widerspruch(P)Falls Halten(P,P) „ja“ liefert, gehe in Endlosschleife, sonst

halte an.

Page 13: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 13

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Reduktion

Eine Möglichkeit, formal zu beschreiben, was es

bedeutet „Problem A ist nicht schwerer als

Problem B“:

A ist ein schwieriges Problem, aber einfach

zu lösen, falls wir einen Algorithmus für B haben.

Page 14: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 14

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätReduktion, Beispiel

A: Cliquenproblem (CLIQUE)

Eingabe: Graph G, Zahl k,

Gibt es einen vollständigen Subgraph der Größe k in G?

B: Independent Set Problem (IS)

Eingabe: Graph G, Zahl k;

Gibt es einen leeren induzierten Subgraph der Größe k in G?

CLIQUE kann auf IS reduziert werden!

Page 15: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 15

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Formalisierungen des Begriffs „Algorithmus“

- Programmiersprache mit vollständiger, formaler

Syntax- und Semantik-Beschreibung, z.B.

Java, C, Pascal, Algol

- zu kompliziert, um formal zu argumentieren –

- einfache Rechenmodelle oder Kalküle, die „das gleiche

können wie z. B. Java-Programme“

Turingmaschinen, Registermaschinen,

-Rekusivität, uniforme Schaltkreisfamilien, …

Page 16: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 16

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Page 17: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 17

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Vorlage für eine Folie im QuerformatÜberschrift 2

Page 18: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Friedhelm Meyer auf der Heide 18

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Vorlage für eine Folie im HochformatÜberschrift 2

Page 19: Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

High Performance =Innovative Computer Systems + Efficient Algorithms

u v

w

u v

w

Friedhelm Meyer auf der Heide 19

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Heinz Nixdorf Institut& Institut für InformatikUniversität PaderbornFürstenallee 1133102 Paderborn

Tel.: 0 52 51/60 64 66Fax: 0 52 51/62 64 82E-Mail: [email protected]://www.upb.de/cs/ag-madh

Wir danken für Ihre Aufmerksamkeit!Wir danken für Ihre Aufmerksamkeit!