VL-01: Einf uhrung (Berechenbarkeit und Komplexit at, WS ...Programmiersprache (z.B. Java, C++, Python, Scala). I Frage:Terminiert dieses Programm? Wir werden beweisen, dass es keinen

VL-01: Einfuhrung

(Berechenbarkeit und Komplexitat, WS 2017)

Gerhard Woeginger

WS 2017, RWTH

BuK/WS 2017 VL-01: Einfuhrung 1/34

Berechenbarkeit


Rechenmaschinen

1672/1700User:Kolossos/WikimediaCommons/CC-BY-SA-3.0

1923Greg Goebel/WikimediaCommons/Public Domain

?

∼2014

1980 2013 -3000Pearson Scott Foresman/Wikimedia

Commons/Public Domain

1983


Die absoluten Grenzen des Computers (1)

In der Vorlesung interessieren wir uns allgemein fur Berechnungsprobleme.

Eingabe Ausgabe

Zentrale FrageGibt es uberhaupt Probleme,

die wir nicht mit dem Computer losen konnen?

Bessere FormulierungGibt es “algorithmische Probleme” (oder “Berechnungsprobleme”),

die ein Computer nicht losen kann?



Wir werden sehen:

I Es gibt keinen Algorithmus, der entscheidet, ob ein gegebenes

Programm in einen bestimmten Zustand lauft.

(Error: 0E : 016F : BFF9B3D4.)



Wir werden sehen:

I Es gibt keinen Algorithmus, der entscheidet, ob ein gegebenes

Programm in einen bestimmten Zustand lauft.

(Error: 0E : 016F : BFF9B3D4.)

I Allgemein lasst sich die Funktionsweise von Programmen nur schwer

algorithmisch uberprufen.

I Zum Beispiel gibt es keinen Algorithmus, der entscheidet, ob ein

gegebenes Programm immer die Summe zweier eingegebenen Zahlen

berechnet.


Das Halteproblem

Allgemeines Halteproblem

I Eingabe: Ein Programm in einer wohldefinierten, universellen

Programmiersprache (z.B. Java, C++, Python, Scala).

I Frage: Terminiert dieses Programm?

Wir werden beweisen, dass es keinen Algorithmus gibt, der dieses

Problem entscheiden kann.


David Hilbert: Radioansprache 1930

In der Tat: Wir beherrschen nicht eher eine naturwissenschaftliche

Theorie, als bis wir ihren mathematischen Kern herausgeschalt und vollig

enthullt haben.

[...]

Wir durfen nicht denen glauben, die heute mit philosophischer Miene und

uberlegenem Tone den Kulturuntergang prophezeien und sich in dem

Ignorabimus gefallen. Fur uns gibt es kein Ignorabimus, und meiner

Meinung nach auch fur die Naturwissenschaft uberhaupt nicht.

Statt des torichten Ignorabimus heisse im Gegenteil unsere Losung:

Wir mussen wissen.

Wir werden wissen.


Komplexitat


Die Grenzen der effizienten Berechenbarkeit

Zentrale Frage:Lasst sich ein gegebenes algorithmisches Problem effizient losen?

Das heisst:

in vernunftiger Laufzeit,

mit vernunftigem Speicherbedarf

und vernunftiger Verwendung anderer Ressourcen?


Beispiel 1: Zauberdodekaeder

AufgabeLose den Dodekaeder.


Beispiel 2: Rush Hour

User:Welt-der-Form/Wikimedia Commons/CC-BY-SA-3.0

AufgabeBefreie das rote Auto aus dem

Verkehrsstau.

Dieses algorithmische Problem

(und ahnliche Probleme) lassen

sich offensichtlich mit dem

Computer losen. Man kann zum

Beispiel alle Moglichkeiten

durchprobieren.

Leider lassen sich solche

Probleme oft nur durch extrem

langsame Algorithmen losen.


Beispiel 3: Traveling Salesman (1)

AufgabeFinde eine kurze Rundreise durch die

grossten deutschen Stadte und zuruck

zum Ausgangsort.

Die angegebene Route ist die kurzeste

von 43.589.145.600 moglichen.

Auch dieses Problem kann man losen,

indem man alle Moglichkeiten

durchprobiert (und das ist wieder extrem

ineffizient).

Die Suche nach einem effizienten

Algorithmus fur das Problem begann

schon vor funfzig Jahren . . .


Beispiel 3: Traveling Salesman (2)

Traveling Salesman Problem (TSP)

I Eingabe: vollstandiger Graph G mit Kantenlangen

I Ausgabe: eine Rundreise, die alle Knoten in G besucht und dabei so

kurz wie moglich ist

Wir werden zeigen, dass es unter einer gewissen Hypothese (“P 6= NP”)

keinen effizienten Algorithmus fur dieses Problem gibt.


PROLOG

Aus der WikipediaProlog is a general-purpose logic programming language associated with

artificial intelligence and computational linguistics.

In Prolog, program logic is expressed in terms of relations, and a

computation is initiated by running a query over these relations. Relations

and queries are constructed using Prolog’s single data type, the term.

Relations are defined by clauses.

Given a query, the Prolog engine attempts to find a resolution refutation

of the negated query. If the negated query can be refuted, i.e., an

instantiation for all free variables is found that makes the union of clauses

and the singleton set consisting of the negated query false, it follows that

the original query, with the found instantiation applied, is a logical

consequence of the program. This makes Prolog (and other logic

programming languages) particularly useful for database, symbolic

mathematics, and language parsing applications.


Ubersicht (Inhalt)


Ubersicht (1)

Teil 1: Grundlagen

I Modellierung von Problemen

I Einfuhrung der Turingmaschine (TM)

I Einfuhrung der Registermaschine (RAM)

I Vergleich TM versus RAM

I Church-Turing-These


Ubersicht (2)

Teil 2: Berechenbarkeit

I Existenz unentscheidbarer Probleme

I Unentscheidbarkeit des Halteproblems

I Diagonalisierung / Unterprogrammtechnik / Reduktion

I Hilberts zehntes Problem

I Das Post’sche Korrespondenzproblem

I WHILE- und LOOP-Programme


Ubersicht (3)

Teil 3: Komplexitat

I Die Komplexitatsklassen P und NP

I NP-Vollstandigkeit und der Satz von Cook und Levin

I Kochrezept fur NP-Vollstandigkeitsbeweise

(Polynomielle Reduktion)

I NP-Vollstandigkeit zahlreicher Probleme

I Auswege aus der NP-Vollstandigkeit


Organisatorisches


Personen

• Vorlesung: Gerhard Woeginger (Zimmer 4024 im E1)

Sprechstunde: Freitag 11:15–12:00

• Ubungen: Tim Hartmann, Daniel Neuen

Email: [email protected]

Tim Hartmann Daniel Neuen

• Webseite:

http://algo.rwth-aachen.de/Lehre/WS1718/BuK.php


Termine

Die Vorlesung ist dreistundig (3V+2U), wird aber in zwei 2-stundigen

Blocken abgehalten, die nicht jede Woche stattfinden.

• Vorlesungszeiten (ab heute):

Mittwoch, 14:15–15:45 Uhr, Roter Horsaal

Donnerstag, 12:15–13:45 Uhr, Aula 1

• Globalubung (ab ubernachster Woche, 25-Oktober):

Mittwoch, 10:15–11:45 Uhr, AH V


Ubungen (1)

• Anmeldung zu Ubungsgruppen: siehe Link auf Webseite

Nur bis zum 13. Oktober moglich (!!!)

Details zur Anmeldung: Ubungsblatt 0 (siehe Webseite)

• Wir verwenden kein L2P

• Die Ubungen werden in Gruppen zu 2 Studierenden bearbeitet

• Neue Ubungsblatter erscheinen jeden Freitag

• Abgabe nach 10 Tagen: Dienstag, bis 16:15

• Mit Ubungsgruppe, Namen und Matrikelnummern beschriften

• Blatter zusammenheften!

• Alle Materialen auf der Webseite:



Ubungen (2)

Abgabe:

bis Dienstag, 16:15 Uhr in den Kasten vor dem Lehrstuhl i1


Ubungen (3)

Tutorium:

• Ubungen in 20 Kleingruppen

• Bearbeitung von Extra-Aufgaben, die auf Hausaufgaben vorbereiten

• Verteilung auf Kleingruppen erfolgt ubers Ubungssystem

• Praferenzen konnen im Ubungssystem angegeben werden


Klausur (1)

Zulassungsvoraussetzungen fur die Klausur:

• 50% der Punkte in den Hausaufgaben

Zulassungen aus dem letzten Studienjahr: verfallen

Bonusregel:

70% der Punkte in den Hausaufgaben

⇒ Klausurnote verbessert sich um einen Grad (= 0.3)


Klausur (2)

Klausur:

Montag, 19. Februar 2018, 13:00h bis 16:00h

Dienstag, 20. Marz 2018, 16:00h bis 19:00h

Anmeldung

I Die Klausuren sind jeweils separate Veranstaltungen in

CampusOffice.

I Anmeldung dort Zum modularen Anmeldeverfahren.

I Anmeldefrist (Mitte November) beachten!


Andere Studiengange (6= Bachelor-Informatik)

I Fur einen benoteten Schein (das ist der Normalfall!) nimmt man wie

die Bachelor-Informatik-Studierenden an der Klausur teil und muss

dazu auch (wie beschrieben) die Zulassung erlangen.

I Fur einen unbenoteten Teilnahmeschein muss man an den Ubungen

teilnehmen und die Kriterien fur die Klausurzulassung erfullen Man

muss aber nicht an der Klausur teilnehmen.

I Studierende, die die Vorlesung als Master-Auflage absolvieren

mussen, nehmen ganz normal an Ubungen und Klausur teil, mussen

sich aber direkt bei uns anmelden: E-Mail an

[email protected]

mit Name und Matrikelnummer.


Was tun bei Fragen?

1. Erster Ansprechpartner ist der Tutor oder die Tutorin der

Kleingruppe.

2. Sollte der Tutor die Frage nicht klaren konnen, so konnen Sie mich

nach der Vorlesung ansprechen, oder Tim Hartmann oder Daniel

Neuen in der Globalubung fragen.

3. Dann erst, oder in dringenden(!) Fallen E-Mail an:

[email protected]


Wie konnen Sie mich erreichen?

1. Immer nach der Vorlesung.

2. In meiner Sprechstunde: Freitag 11:15–12:00

3. Zur Not einen anderen Termin mit Frau Schlebusch (Sekretariat i1)

vereinbaren.


Materialien (1)

I In der Vorlesung wird der Stoff per Beamerprasentation vermittelt,

manchaml auch an der Tafel oder auf dem Overheadprojektor

I Vor der Vorlesung wird ein Foliensatz auf der Buk-Webseite zur

Verfugung gestellt. (Die Folien basieren auf Material, das im Laufe

der Jahre von Berthold Vocking, Wolfgang Thomas, Martin Grohe

und Pascal Schweitzer entwickelt wurde.)

I Ausserdem gibt es das Vorlesungsskript von Berthold Vocking (139

Seiten) auf der Buk-Webseite.

I Webseite:



Materialien (2)

Buchempfehlungen:

I Uwe Schoning. Theoretische Informatik - kurzgefasst. Spektrum

Akademischer Verlag, 2001.

I Michael Sipser. Introduction to the Theory of Computation.

Cengage Learning, 2012.

Diese und noch weitere Bucher zum Thema sind zu finden in der

Informatikbibliothek.

Ein weiterfuhrendes Buch ist

I Sanjeev Arora, Boaz Barak. Computational Complexity. Cambridge

University Press, 2009.


Organisatorisches

• Nachste Vorlesung:

Donnerstag, Oktober 12, 12:15–13:45 Uhr, Aula

• Webseite:



Documents

VL-01: Einf uhrung (Berechenbarkeit und Komplexit at, WS ...Programmiersprache (z.B. Java, C++, Python, Scala). I Frage:Terminiert dieses Programm? Wir werden beweisen, dass es keinen