Formale Methoden der Informatik WS 2010/2011Lehrstuhl fur Datenbanken und Kunstliche Intelligenz

Prof. Dr. Dr. F. J. Radermacher H. Unver T. Rehfeld J. Dollinger9. Aufgabenblatt

Besprechung in den Tutorien vom 12.01.2011 (ab Ubungstermin)bis 19.01.2011 (bis Ubungstermin)

46. Aufgabe (4 Punkte) Verstandnisfragen:

a) Was besagt die Churchsche-These?

Jeder sinnvolle Berechenbarkeitsbegriff ist aquivalent zur Turingberechenbarkeit bzw.-Rekursion bzw. Algorithmen (mit WHILE-Bedingungen).Eine (partielle) Funktion f : Nn N ist genau dann im intuitiven Sinne (par-tiell) berechenbar, wenn sie (partiell) turing-berechenbar ist.

b) Welche Arten von Komplexitatsbetrachtungen kann man unterscheiden?

Bei der Komplexitat eines Algorithmus oder eines Programmes kann man nach ver-schiedenen Kriterien optimieren (die miteinander oftmals konkurrieren und sich teil-weise gegenseitig behindern oder sogar gegenseitig ausschlieen): Zeitbedarf bzw. Anzahl der Schritte bei der Ausfuhrung (moglichst kurze Dauer) Lange des Programmes bzw. der Beschreibung des Verfahrens

(moglichst kurzes Programm) Groe des benotigten Speicherbedarfs bzw. Menge der (zwischenzeitlich) zu mer-

kenden Informationen (moglichst wenig Speicher)

c) Worauf bezieht sich immer dieses n bei den Komplexitatsbetrachtungen?

Auf die Anzahl der Datenmenge, die vom Algorithmus bearbeitet wird.Beispiele: beim Dijkstra (kurzester Weg): die Anzahl der Knoten im Graph, beim schriftlichen Multiplizieren zweier Zahlen (nach der Schulmethode):

die Lange (Anzahl der Stellen) der Zahlen, bei Sortierproblemen: die Anzahl der zu sortierenden Daten, bei Suchproblemen: die Anzahl der Daten, in denen gesucht wird.

d) Welche Falle betrachtet man meistens(minimaler Aufwand / durchschnittlicher Aufwand / maximaler Aufwand)?

Es gibt in der Tat Betrachtungen zu allen diesen Fallen (und noch einigen weiteren).

Meist spricht man bei der Komplexitat von der sogenannten worst case Komple-xitat (der schlimmste anzunehmende Fall). Damit hat man eine obere Abschatzungfur den Algorithmus (und meist ist diese Betrachtung auch schon aussagekraftiggenug).Zur Bestimmung ist haufig eine eher oberflachliche Betrachtung des Algorithmusund seiner Ablaufe bereits ausreichend.

Bei manchen Algorithmen unterscheidet sich die sogenannte average case Kom-plexitat (durchschnittlicher Aufwand) aber doch deutlich vom schlimmsten anzu-nehmenden Fall.Zur Bestimmung ist hier meist eine recht genaue Komplexiatsanalyse notwendig, daman hier insbesondere die Haufigkeit (und Wahrscheinlichkeit) der im Algorithmusauftretenden Falle berucksichtigen muss.

Eine Minimal-Aufwandsbetrachtung kann manchmal interessant sein, um zu sehen,wie gro der Aufwand mindestens (bestenfalls) schon sein wird, wird aber eherselten durchgefuhrt.

1

e) Was versteht man unter Komplexitatsklassen?

Meist werden keine exakten Angaben z.B. uber die genaue Schrittzahl bei einem Ver-fahren benotigt.Insbesondere wird (meist) nicht mehr aufgefuhrt, ob es Bereiche im Algorithmus gibt,die (fur sich genommen) einen hoheren oder niedrigeren Aufwand besitzen (immer ge-messen an der Datenmenge n).In solchen Fallen werden die verschiedenen Aufwande der Bereiche in eher grobeKlassen unterteilt (z.B. O(n), O(log n), O(n2), O(en)), zusammengeworfen und dergrote Aufwand im Algorithmus uberwiegt dann. (siehe auch Aufgabe 50)

f) Wie ermittelt man die Komplexitat eines Algorithmus?

Im wesentlichen durch Betrachtung der Struktur des Algorithmus.

Man Unterteilt den Algorithmus in verschiedene Bereichte:(vor und nach einer Wiederholungsschleife / innerhalb einer Wiederholungsscheife /Bereich, der rekursiv aufgerufen wird und sich deshalb immer wieder wiederholt /etc.)

Jeder dieser Bereiche (insbesondere zunachst die innersten) erhalt erstmal eineeigene Bewertung (in O-Notation). Sequenz von Anweisungen konstanter Aufwand = O(1) Wiederholungsschleife Wie oft wird die Schleife (im Verhaltnis zu n) wie-

derholt?(z.B. n mal einfache Wiederholung / log n mal bei Intervall-Teilung)(man achte auf die Schleifenbedingungen)Der Aufwand im inneren der Schleife wird mit dieser Anzahl (ausgedrucktabhangig von n) multipliziert.Dies gilt insbesondere fur geschachtelte Schleifen.

Rekursion abhangig von der Art der Rekursion wird der Aufwand des in-neren der Rekursion wieder mit der Anzahl der Wiederholungen multipliziert.(z.B. lineare Rekursion n Wiederholungen / baumartige Rekursion 2n Wie-derholungen / Intervall-Teilung log n Wiederholungen / etc.)

g) Welche Rechenregeln gibt es fur die O-Notation?

O( x) = O(x) = O(x) , mit = const., x = x(n) O(x) O(y) = O(x y) , mit x = x(n), y = y(n) O(klein) + O(gro) = O(gro)

h) Was ist eine Clique?

Ein vollstandiger Untergraph (im Sinne von: alle Knoten sind mit allen anderen Kantendes Untergraphen verbunden).

2

47. Aufgabe (4 Punkte) Postsches Korrespondenzproblem:

Man zeige, dass die folgenden postschen Korrespondenzprobleme eine Losung haben:

a) (x1, y1) = (abba, a),(x2, y2) = (a, aab),(x3, y3) = (ba, b)

2, 2, 3, 1 aabaabba = ax2

ax2

bax3

abbax1

= aaby2

aaby2

by3

ay1

b) (x1, y1) = (aaab, a),(x2, y2) = (b, aab),(x3, y3) = (aaa, ba)

1, 2, 3, 2 aaabbaaab = aaabx1

bx2

aaax3

bx2

= ay1

aaby2

bay3

aaby2

48. Aufgabe (6 Punkte) Game of Life:

Geben Sie (ohne Hilfe des Simulators) die nachsten drei Iterationen an unter Angabe der verwen-deten Regeln.

a)

2 1 1

1 2 3 4 3 4 3 2 1

3 2 3

2 1 2

1 1 1

1 1 1

2 1 2

3 2 3

1 2 3 4 3 4 3 2 1

1 1 2 3 4 3

4. Zellen mit vier oder mehr Nachbarn sterben aus

2. Zellen mit zwei Nachbarn verndern sich nicht1. Zellen mit nur einem Nachbarn sterben ausRegeln: Durch Symmetrie setzt

sich der Ausschnitt fort.

3. Zellen mit drei Nachbarn kommen neu hinzu

4 4

6 6

66

4

2

3

2

2 2

3 3

33

2

3

2

2

2 3 2

1

1 1

1 1

1

1

1

1

2 3 2

2 4 3 4

5

5 5

5

3

3

2

3

4 4

4

4 3

1

1

4

3

b)

2

2

42 3

3

31 1

1 1

1

1 1 1

1 1 1

1

2 2

2 2

2 3 2 2

1

1

2 2

2

2

3

2

232

3 4

3 5 3

2

1 1

1

1

1 1 1

2

2

2

1

2

1

1

1

1 1

1 1

1 1

2 2

2

3 2

2

11

1

1 1

1

1 1 1

2

2

2

2

11

1

1 3

2

1

1

2

3

5

4

1

1 1

1

1

49. Aufgabe (4 Punkte) Komplexitat verschiedener Algorithmen:

Geben Sie zu den gegebenen Aufgaben die Komplexitat des Problems in O-Notation an:

a) Suchen eines beliebigen Elementes in einer unsortierten Liste (z.B. Zahlen) der Lange n.

O(n)

b) Suchen eines beliebigen Namens im Telefonbuch (mit n Eintragen im Telefonbuch).

Hinweis: Denken Sie an die in der Vorlesung diskutierte Intervall-Teilung.

O(log2 n)

c) Multiplizieren von zwei n-stelligen Zahlen nach der Schulmethode.

O(n2)

d) Multiplizieren von zwei n n-Matrizen nach der Schulmethode.O(n3)

4

50. Aufgabe (5 Punkte) Komplexitat des Travelling Salesman Problems:

Stellen Sie sich einen Aussendienstmitarbeiter vor, der n Kunden nacheinander besuchen soll. DieAufgabe soll nun sein, die Reiseroute zu finden, die zu allen Kunden und danach wieder zuruckfuhrt. Fur jede Wegstrecke ist deshalb die Entfernung angegeben. Zur Vereinfachung wollen wirdie Bedingungen fur die Reiseroute so wahlen, dass es zwischen jeweils zwei Kunden immer einenWeg gibt und dass jeder Kunde nur einmal aufgesucht werden darf. Mit diesen Einschrankungenhaben alle Reiserouten die gleiche Anzahl an Teilstrecken. Als Beispiel sei folgendes Wegenetz mitAusgangspunkt(A) und den 5 Kunden (K1 bis K5) gegeben.

......................

.....................................................................................

......................

.....................................................................................

......................

.....................................................................................

......................

.....................................................................................

......................

.....................................................................................

......................

.....................................................................................

............................................................................................................................

.....................................................................................................................................................

............................................................................................................................

.......................................................................................................................................................................................................................................................

.....................................................................................................................................................

A

K5

K4

K3

K2

K1

13

2

4357

95

3 366

4

.........................

.................................... 4

.............................................................

..............................................................

.............................................................. .........................................

......................

.............................................................

a) Wieviele Moglichkeiten fur gultige Reiserouten gibt es?

Kombinatorische Moglichkeiten:5! = 5 4 3 2 1 = 120

b) Welches ist die optimale Reiseroute? Nach welcher Methode suchen Sie diese?

A K1 K5 K3 K4 K2 A oder ruckwarts.Suchmethode: Alle ausprobieren!Dies ist die Suche nach der kurzesten Rundreise (Hamiltonkreis im Graphen). Bedau-erlicherweise gibt es keinen effizienten Algorithmus, um nach der kurzesten Rundreisezu suchen (zumindest, wenn man das exakte Ergebnis wunscht dann hilft eben nurdas systematische Ausprobieren).

c) Wieviele verschiedene Reiserouten gibt es bei 5, 50 und 500 Kunden?

Bei 5 Kunden: (siehe oben) 5! = 120Bei 50 Kunden: 50! = 30414093201713378043612608166064768844377641568960512000000000000Bei 500 Kunden 500! =1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

d) Was bedeutet das fur die Suche nach der optimalen Reiseroute?

Da die Anzahl der zu uberprufenden Reiserouten ziemlich schnell mit n steigt, kannman die Berechnung nur fur kleine n uberhaupt durchfuhren.!

e) Wenn ein Computer heute die Losung fur 50 Kunden in akzeptabler Zeit berechnen konnte,fur wieviele Kunden konnte dann ein um den Faktor 10 schnellerer Computer eine Losungmit dem gleichen Algorithmus berechnen?

Auch nur fur 50 oder 51.

5

51. Aufgabe (3 Punkte) Reihenfolge verschiedener O-Funktionen:

Gegeben sind folgende Komplexitaten in O-Notation. Bringen Sie diese in die richtige Reihenfolge.

Hinweis: Beachten Sie, welche der Funktionen fur sehr groe n schneller wachsen.

i. O(n2)ii. O(en)iii. O(n)iv. O(n!)v. O(2 n)vi. O(n3)vii. O(log n)viii. O(n log n)ix. O(1)x. O(nn)xi. O(n9)xii. O(1.001n)xiii. O((nn)n)xiv. O(n(n

n))

O(1) < O(log n) < O(n) < O(2 n) < O(n log n) < O(n2) < O(n3) < O(n9) < O(1.001n)