Grundlagen der Informatik

Wolfgang Ertel, Frank Sausen

30. Januar 2009

HochschuleRavensburg−WeingartenTechnik | Wirtschaft | Sozialwesen

Inhaltsverzeichnis

1 Was ist Informatik? 4

1.1 Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Teilgebiete der Informatik? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.5 Programm, Algorithmus, Software . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.6 Betriebssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.7 Softwaretechnologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.8 Datensicherung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.9 Datenschutz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.10 Datenbanken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.11 Das Informatikstudium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Geschichte der Informatik 12

2.1 Wichtige Quellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Zahlendarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Geschichte der Bauelemente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4 Geschichte der Rechenmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.5 Geschichte der Programmiersprachen . . . . . . . . . . . . . . . . . . . . . . . . 19

2.6 Geschichte des Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.7 Große Informatiker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.8 Frauen in der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.9 Wichtige Institute und Firmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Algorithmen und Datenstrukturen – Einfuhrung 28

3.1 Sortieren durch Einfugen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.3 Sortieren mit Baumen (Heapsort) . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.4 Sortieren in linearer Zeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.5 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4 Algorithmen auf Graphen 50

4.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.2 Eulerkreise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3 Datenstrukturen fur Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.4 Kurzeste Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.5 Das Problem des Handlungsreisenden . . . . . . . . . . . . . . . . . . . . . . . . 59

4.6 Planare Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2

5 Formale Sprachen und Endliche Automaten 685.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685.2 Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.3 Regulare Ausdrucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725.4 Endliche Automaten zur Worterkennung . . . . . . . . . . . . . . . . . . . . . . 735.5 Automaten mit Ausgabe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.6 Formale Beschreibung von Automaten . . . . . . . . . . . . . . . . . . . . . . . 75

6 Zusatzmaterial 786.1 Logarithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786.2 Anwendung des Mastertheorems . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

7 Ubungen 807.1 Geschichte der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 807.2 Sortieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 807.3 Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 837.4 Formale Sprachen und Endliche Automaten . . . . . . . . . . . . . . . . . . . . 84

Literaturverzeichnis 87

3

Kapitel 1

Was ist Informatik?

1.1 Informatik

Definition 1.1 Informatik ist die Wissenschaft der automatischen Verarbeitung von In-formationen.

(Am.: Computer Science)

Verschiedene Aspekte der Informatik:

• Spaß am Programmieren (Erfolgserlebnisse)

• Spaß an der Beherrschung der Maschine

• Teilweise sehr abstrakte Wissenschaft (Mathematik)

• Ohnmachtgefuhl von Laien

1.2 Computer

Definition 1.2 Programmierbare Rechenmaschinen werden als Computer bezeichnet.

fruher wurden Menschen, die “rechnen” als Computer bezeichnet.

Computer

• machen unser Leben bequemer

• helfen beim Beschaffen von Informationen

• vereinfachen die Kommunikation

• konnen suchtig machen

• konnen zum Pseudopartner werden

• vernichten Arbeitsplatze

• schaffen Arbeitsplatze

• Wem nutzt die Informatik?

• Wem schadet die Informatik?

⇒ Soziale Verantwortung des Informatikers!

4

1.3 Information

Information: Wissen, Gegenteil von Unsicherheit.

Definition 1.3 Als elementare Maßeinheit fur Information dient das Bit. Eine Nachricht(z.B. ein Text od. eine Zahl) hat einen Informationsgehalt von n Bit, wenn die minimaleZahl von Ja/Nein Fragen, zur exakten Ermittlung der Information genau n ist.Ein Computer-Wort besteht z.B. aus 8, 16, 32, oder 64 Bit.

Beispiel 1.1

1 0 0 1 1 0 1 01 · 27+ 0 · 26+ 0 · 25+ 1 · 24+ 1 · 23+ 0 · 22+ 1 · 21+ 0 · 20 =

128 + 16 + 8 + 2 =

154

1.4 Teilgebiete der Informatik?

InformatikEinen guten Uberblick uber die verschiedenen Teilgebiete der Informatik verschafft das Wi-kipedia Informatik Portal. http://de.wikipedia.org/wiki/Portal:Informatik

Theoretische Informatik

• Logik (logisch!)• Berechenbarkeit (ist jedes Problem berechenbar?)• Komplexitat (Rechenaufwand)• Formale Sprachen (Programmiersprachen)• Informationstheorie (Datenubertragung)• Kryptographie (Datensicherheit)• Formale Spezifikation und Verifikation (Korrektheitsbeweise von Programmen)• . . .

Technische Informatik

• Hardware• Rechnernetze• Schaltungen• Schnittstellen• Peripheriegerate

Praktische InformatikBereitstellen von Hilfsmitteln fur die Arbeit mit Computern

5

• Rechnerarchitektur• Betriebssysteme (DOS, Windows, Unix, . . . )• Datenbanken• Kunstliche Intelligenz• Software-Entwicklung• Datenkommunikation• Prozeßsteuerung• Bildverarbeitung• . . .

Angewandte Informatik

• Wirtschaftsinformatik• Medizinische Informatik• Medieninformatik (Multimedia)• Kommunikationstechnik• Automatisierungstechnik• Kunstliche Intelligenz

1.5 Programm, Algorithmus, Software

Definition 1.4

Algorithmus: Allgemeines Schema zur Losung einer Klasse von Problemen.

Programm: Folge von Befehlen in einer festen Programmiersprache

Softwareentwicklung:

• Problemanalyse

• Problemlosung (Algorithmierung)

• Programmierung (Kodierung)

• Test

• Inbetriebnahme

Softwaretechnologie:Systematische Untersuchung der Softwareentwicklung und Bereitstellung von Entwicklungs-werkzeugen.

1.6 Betriebssysteme

1.6.1 Betriebssysteme: Aufgaben

• Laden u. Starten von Programmen

• Verwalten des Hauptspeichers

Schutzen der Speicherbereiche von Programmen

6

Verwaltung des virtuellen Speichers (paging, swapping)Paging: Auslagern von ProgrammteilenSwapping: Auslagern ganzer Programme

• Verwaltung von Dateien

Verwaltung von Dateiattributen (Große, Datum, Rechte)

Verwaltung von Verzeichnissen

• Ein- und Ausgabe

zeichenorientiert: Tastatur, Bildschirm, Drucker, serielle Schnittstelle

blockorientiert: Festplatte, Diskette, CD-Rom, Streamer

Verwaltung von Warteschlangen, z.B. f. Drucker

• Zeitgeberfunktionen: Datum, Uhrzeit, verzogerter Programmstart

1.6.2 Betriebssysteme: Bestandteile

Betriebssystemkern: (Kernel) allgemeine Module f. Ein/Ausgabe, Speicherverwaltung, etc.

Dienstprogramme: kopieren, loschen v. Dateien, formatieren v. Disketten, ...

Bootprogramme: zum Hochfahren des Rechners benotigte Programme

ladbare Treiber: z.B. f. Netzwerkanbindung, Streamer

1.7 Softwaretechnologie

Kosten von Hard- und Software:

Fruher: 90% Hardware, 10% Software

Heute: 10% Hardware, 90% Software

⇒ Informatik als Ingenieursdisziplin mit der Aufgabe der Softwareentwicklung!

Definition 1.5 Beim Softwareengineering laufen folgende Prozesse parallel nebeneinan-der ab:

Softwareentwicklung

Projektmanagement

Qualitatssicherung

Projektverwaltung

7

1.7.1 Softwareentwicklung

Wichtige Begriffe:

• Softwarelebenszyklus (software life cycle)

• Phasenmodell der Softwareentwicklung

• Wasserfallmodell

Planung

Spezifikation

Entwurf

Kodierung

Test

Betrieb

Stillegung

Der Softwarelebenszyklus

1.7.2 Moderne Softwareentwicklung

Wichtige Schritte im Entwicklungsprozess:

Use Cases: Typische Benutzer-Programm Interaktionen

Verteilungsmodell: Verteilung von Objekten/Prozessen auf ein-zelne Rechner, bzw. Teilnetze

Datenflußdiagramm: Graphische Darstellung des Datenflusses.Fuhrt zu Schnittstellendefinitionen.

Unix-Pipe: ps | sort | lp

sort

Prozeßliste

sortierte Liste

Drucker

lp

ps

Ausdruck auf Papier

druckbare Daten

1.7.3 CASE: Computer Aided SW-Engineering

CASE-Tools sind Werkzeuge, die den ganzen Entwicklungsprozeß unterstutzen. Teile desProzesses konnen dabei automatisiert werden, andere benotigen eine Interaktion des Menschenmit dem Tool.

8

1.8 Datensicherung

Eine wichtige Aufgabe beim Betrieb eines Rechensystems ist die Datensicherung.

Definition 1.6 Datensicherung (engl. Dump) ist das regelmaßige Speichern von Datenvon der Festplatte auf einen anderen Datentrager mit dem Ziel der Rekonstruktion bei Da-tenverlust.

klassisches Verfahren: inkrementeller Dump

Level 0 Dump: 1× pro Monat wird die gesamte Platte (inklusive Betriebssystem) auf demMagnetband gesichert. (in den ungeraden Monaten auf Band M-1, in den geraden Mona-ten auf Band M-2.)

Level 1 Dump: 1× pro Woche werden die Benutzerdaten von der Platte auf dem Magnetbandgesichert. (in den ungeraden Wochen auf Band W-1, in den geraden Wochen auf BandW-2.)

Level 2 Dump: taglich werden die Benutzerdaten von der Platte auf dem Magnetband in-krementell gesichert. (in den ungeraden Wochen auf die Bander Mo-1, . . . , Fr-1, in dengeraden Wochen auf die Bander Mo-2, . . . , Fr-2)

Bemerkungen:

• insgesamt werden 14 Magnetbander fur die Datensicherung benotigt!

• wahrend des Dumps sollte kein Benutzer auf dem Rechner arbeiten.

• die gesicherten Medien (Bander) sollten in einem anderen Gebaude sicher verwahrt wer-den.

modernes Verfahren:

Daten werden monatlich, wochentlich, taglich auf je eine monatliche, eine wochentliche, bzw.eine tagliche Festplatte (im Wechsel) gespiegelt, nach ahnlichem Verfahren wie oben.

1.9 Datenschutz

Bundesdatenschutzgesetz (BGBL. 1 2003, S. 66) § 1, Abs. 1:

“Zweck dieses Gesetzes ist es, den Einzelnen davor zu schutzen,dass er durch den Umgang mit seinen personenbezogenenDaten in seinem Personlichkeitsrecht beeintrachtigt wird.”

Beispiel:

Die Veroffentlichung von Fotos von Mitarbeitern ist nur er-laubt, wenn der Mitarbeiter freiwillig und schriftlich sein Ein-verstandnis erklart.

Eva MullerMitarbeiterin des Monats

9

1.10 Datenbanken

Beispiele:

• Literaturdatenbank

• Personaldatenbank

• Gefahrstoffdatenbank

• Buchungssystem fur Reiseburos/Fluggesellschaften

• ...

Definition 1.7 Eine Datenbank ist eine systematisch strukturierte, langfristig verfugbareSammlung von Daten einschließlich der zur sicheren und schnellen Manipulation dieser Datenerforderlichen Software.

Vorteile einer Datenbank:

• Mehrbenutzerbetrieb moglich

• Unterschiedliche Sichten auf die Daten sind moglich

• Daten sind unabhangig von Nutzerprogrammen; Nutzung ist unabhangig von der Art derSpeicherung.

• Vollstandigkeit (Integritat) und Korrektheit (Konsistenz) werden automatisch gewahrleistet.

Eine Datenbank besteht aus

Datenbasis: die (z.B. als Tabellen) in Dateien gespeicherten Daten.

Datenbankmanagementsystem (DBMS): Programm fur Aufbau, Verwaltung und Anwen-dung der Datenbank.

Datenbanksprache: formale Sprache zur Formulierung von Benutzeranfragen an die Daten-bank. (Beispiel: SQL (Structured Query Language))

1.11 Das Informatikstudium

Leonardo da Vinci:

Studium ohne Hingabe schadet dem Gehirn

Der Studienerfolg wird statistisch u.a. bestimmt durch folgende Variablen:

Note: Note =

Schnitt falls Abitur

Schnitt− 0.5 falls FH-Reife direktSchnitt− 1 falls FH-Reife auf 2. Bildungsweg

Interesse (fur Informatik): Ich wollte schon immer wissen, wie (intelligente Roboter, Ver-schlusselung, Internet, . . . ) funktioniert (0|1)

Biss (Wille): Wenn notig arbeite ich auch am Abend und am Wochenende (0|1)

SozUm: Finanziell gesichert, Wohnen vor Ort, Partnerschaft o.k. (0|1)

10

1.11.1 Entscheidungsbaum

Variablenwerte fur Interesse, Biss, SozUm:

1: trifft voll zu; 0: trifft nicht oder nur teilweise zu

Studienerfolg: −: keine Abschluss; +: Bachelor; ++: Bachelor, sehr gut

0 1

Interesse

0 1

SozUm

+++

+

Biss

Note

Interesse

Biss

10

>32.5-3

Interesse

SozUm

0 1

0 1 0 1

10

+

+ ++

Interesse

0 1

Biss+

<1.5

+

0 1

Biss

++

+

1.5-2.5

0 1

1.11.2 Score (einfach)

Score = (3− Note) + 3 · Biss + 2 · Interesse + SozUm

Studienerfolg =

++ falls Score > 3.5+ falls Score > 0− falls sonst

11

Kapitel 2

Geschichte der Informatik

2.1 Wichtige Quellen

• http://de.wikipedia.org

• www.computerhistory.org

• F. Naumann, Vom Abakus zum Internet [2]

• H. Matis, Die Wundermaschine[3]

• W. de Beauclair, Rechnen mit Maschinen – eine Bildgeschichte der Rechentechnik[4]

2.2 Zahlendarstellung

Additive Zahlendarstellung:

additiv (ohne Null) mit Null (binar) dezimal– 0 01 1 1

11 10 2111 11 3

1111 100 411111 101 5

111111 110 61111111 111 7

11111111 1000 8. . . . . . . . .

1111111111111111111111111111111111111111 110010 50

additive Zahlendarstellung ist fur große Zahlen nicht brauchbar!

Mit n Stellen lassen sich darstellen:

additiv: die Zahlen 1 . . . nbinar: die Zahlen 0 . . . 2n − 1dezimal: die Zahlen 0 . . . 10n − 1Ziffern 0 . . . b: die Zahlen 0 . . . (b+ 1)n − 1

Wieviele Stellen braucht man, um eine große Zahl z darzustellen?

binar:z = 2n ⇔ n = log2 z

allgemein:

12

Zahl d. Stellen um die Zahlen 0 . . .m darzustellenadditiv: m+ 1binar: ≤ log2m+ 1dezimal: ≤ log10m+ 1Ziffern 0 . . . b: ≤ logb+1 m+ 1

Die Zahl der Stellen bei Stellenwertsystemen wachst nur logarithmisch mit der Großeder darzustellenden Zahl (dank der Null).

2.2.1 Geschichte der Zahlen und des Rechnens

30000 v. Chr. erste Zeichensysteme fur Zahlen in Agypten und Mesopotamien3500 v. Chr. Zeichen auf Tontafeln in PakistanAdditive Zahldarstellung in Rom, Mexiko (Maya), China, Agypten, Sumerer

200 v. Chr Erfindung der Null in Indien ⇒ Stellenwertsystem0 Romische Schriftzeichen1200 Fibonacci fuhrt negative Zahlen ein (Schuld)

2.3 Geschichte der Bauelemente

2.3.1 Rechenlogik

Elektrische Rechenmaschine braucht elektrische Schalter!

Mechanik Antike bis heute

Relais 1835 – 1950, J. Henry

Rohre 1904 – 1970, J.A. Fleming(Engl.)

Transistor 1947 – heute, Bell Labs(USA)

13

IntegrierterSchaltkreis

1958, heute bis zu 1 Milliar-de Transistoren auf unter 1cm2

Pentium 4 Intel, 2000, bis 3.8 GHzTaktfrequenz, 2 CPUs aufeinem Chip

2.3.2 Speichertechnologie 1956, IBM-RAMAC

• erste Festplatte

• 50 Platten, je 60 cm Durchmesser, 1200 Um-dr./min

• pro Platte 2× 100 Spuren mit je 500 Zeichen

• ⇒ pro Platte 100 kB Speicher

• gesamt: 5 MB Speicher

2.3.3 Speichertechnologie 2005

• Mehr als 4 Gigabit pro cm2

• Anzahl der Spuren pro Zoll (tpi) z. B. 135.000,

• Kopfe fliegen 10-15 Nanometer uber d. Platte(Haar ist 50.000 nm dick)

2.3.4 Speichertechnologie 1956–2008

2.4 Geschichte der Rechenmaschinen

2.4.1 Kerbholzer und Knotenschnure

• Speicherung von Zahlen

• Additition und Subtraktion

14

2.4.2 Mechanische Rechenmaschinen (Mittelalter)

Abakus: +,− Schickard (1623, lange unbe-kannt): +,−,×, /

Pascal (1641): +,−

Informatikgeschichte, E. Ehses 2003 17

Analytical Engine

Die grundlegend neuen Ideen bestehen:

1. In der Programmierbarkeit einer Maschine durch Verwendung von Jacquard‘schen Lochkarten.

2. In der Weiterverwendung von Zwischenergebnissen. („the engine eating its own tail“)

3. Der Aufteilung des Gerätes in Speicher(Store) und Rechenwerk (Mill). Zahnstangen dienten der Übertragung von Zahlenwerten zwischen Store und Mill (Rechnerbus).

Die Analytical Engine war ein Papiercomputer. Nur einzelne Komponenten (Teile des Rechenwerks) wurden wirklich gebaut.

Bis 1948 (Speicherprogrammierbarkeit, John von Neumann) gibt es keine grundlegende Weiterentwicklung dieses Konzepts! Die ersten „modernen“ Rechner hatten eine einfachere Architektur.

Informatikgeschichte, E. Ehses 2003 18

Datenblatt der Analytical Engine

Speicher für rund 100 Variable zu je 30-40 Stellen.

Vorrichtung zur Wiederholung von Operationen(„mechanical means have been provided for backing up or advancing the operation cards to any extend“)

Stanzer für Zahlenkarten (Massenspeicher).

Drucker.

Zeichengerät.

Setzmaschine (offline).

Addition und Subtraction vermutlich ca. 2 sec.Multiplikation ca 1 min.

Leibniz (1675) +,−,×, / Babbage (1823), DifferenceEngine

Babbage (1833–?), AnalyticalEngine (programmierbar!)

Der Abakus (ca. 2000 v.Chr. bis heute!)

• die universale Rechenmaschine schlechthin!

• verwendet in Griechenland, Rom, Japan, China (bis heute), Rußland(bis heute)

• heute in Japan: Wettbewerbe Abakus – Taschenrechner

Die Analytical Engine

• Programmierbarkeit einer Maschine (revolutionar!) durch Ver-wendung von Jacquard’schen Lochkarten.

• Weiterverwendung von Zwischenergebnissen. (“the engine eatingits own tail”)

• Aufteilung des Gerates in Speicher(Store) und Rechenwerk (Mill).Zahnstangen dienten der Ubertragung von Zahlenwerten zwischenStore und Mill (Rechnerbus).

15

Die Analytical Engine war ein Papiercomputer. Nur einzelne Komponenten (Teile des Rechen-werks) wurden wirklich gebaut. Bis 1948 (Speicherprogrammierbarkeit, John von Neumann)gibt es keine grundlegende Weiterentwicklung dieses Konzepts! Die ersten modernen Rechnerhatten eine einfachere Architektur.

Eingabeschnittstelle fur Lochkarten, unterschieden nach operation cards fur die Befehlseingabe,variable cards zur Eingabe von Variablen und ihrer Speicheradresse, sowie den number cards.Ausgabeschnittstelle entweder fur einen Drucker oder fur Lochkarten die in die Bibliothekeingereiht werden.

Die Chiffriermaschine Enigma

• 1923: Erfindung durch Arthur Scherbius zum Gebrauchfur Geschaftsleute.

• 1925: Deutsche Wehrmacht kauft Enigmas.

• mehrfach geknackt (Polen) und wieder verbessert.

• 1939: Der Großangriff der Briten auf die Enigma in Blet-chley Park.

• 1942: Neue Enigma mit vier Walzen ist wieder sicherund wird im U-Boot-Krieg eingesetzt.

• 1943: Nach fast einem Jahr wird die 4-Walzen-Enigmageknackt. Hier kam Colossus zum Einsatz.

• 1945: Entschlusseln der Enigma-Codes war am Sieg derAlliierten mit beteiligt. ca. 10 000 Personen arbeitetenin drei Schichten rund um die Uhr.

Zuse Z1, Z2

• Baujahr 1938, 1939

• Bleche schieben Stifte, Relais (Z2)

• binar-dezimal Konvertierung, Operationen:+,−,×, /,√,

2.4.3 Elektrische Rechenmaschinen

Zuse Z3

Der im Flugzeugbau tatige Maschinenbauer und Bauingenieur Konrad Zuse (Berlin, 1910–1985)erfand 1941 den ersten frei programmierbaren Rechner Z3.

16

• Baujahr 1941

• programmierbar uber Lochstreifen

• Ausgabe uber Lampenfeld

• Binare Schaltlogik

• “RISC”-Architektur: wenige Befehle

• Gleitpunktarithmetik

• Multiplikationszeit: 3 sec.

• Hauptspeicher: 64 Worte a 22 Bit

ASCC (MARK 1)

• H. Aiken will Rechner zum Losen von DGLs

• erster Rechner mit konsequenter vonNeumann-Architektur

• Baujahr 1944, Univ. Harvard und IBM

• programmierbar uber Lochstreifen

• Multiplikationszeit: 6 sec.

• in Betrieb bis 1959

• 760 000 Einzelteile

• 15 m lang, 2.5 m hoch

Colossus

• entwickelt u.a. von Alan Turing zumKnacken von Enigma-Codes

• Baujahr 1943,

• programmierbar uber Lochstreifen

• photoelektr. Leser (5000 Zeichen/sec.)

• Multiplikationszeit: 6 sec.

• 1500 RohrenOriginal Nachbau

Eniac (electronical numerical integrator and computer)

• Baujahr 1946, Univ. Pennsylvania, USA

• universell eingesetzt, in Betrieb bis 1955

• Dezimalrechner, 10 Dezimalstellen

• Taktfrequenz 100 kHz (Addition 0,2 ms)

• 18000 Rohren, 1500 Relais

• Multiplikationszeit: 3 sec.

17

IBM 360

• Baujahr 1964

• Erster kommerziell erfolgreicher Großrechner

• MTS: Michigan Time sharing system, 1966

Control Data CDC 6600

• Erbaut 1964 von S. Cray

• 3 MIPS

• verteilte Architektur, 10 I/O-Prozessoren

Telefunken TR 440

• Baujahr 1970

• 6,50 m breit

• Gewicht ca. 1250 Kg

• Taktfreq. 20 MHz, 1.2 MIPS

• 1,5 MB Kernspeicher mit virtuellerAdressierung

CPU Lochkartenstanzer

Cray 1

• Baujahr 1976

• Vektorrechner

• Supercomputer fur numerische Berechnungen

• 64 parallel arbeitende 64-Bit Prozessoren

• 166 Mega-FLOPS

• Gewicht: 2.5 Tonnen

Connection Machine

• Baujahr 1986, D. Hillis of Thinking Machines Corp

• Massiv parallel: 16000 parallele Prozessoren

• ca. 10 Milliarden Operationen pro sec.

• Anwendung in der KI, u.a. Neuronale Netze

18

PCs

Commodore Pet,1977, Kassetten-laufwerk, 4/8 kBHauptspeicher

Apple 2, 1977, 1 Main-board, Farbgrafik

IBM PC, 1981, 4.77MHz Intel 8088, MS-DOS (Microsoft discoperating system)

Commodore 64, 1981, fur 595 US$ viel billi-ger als die Konkurrenz, TV-Bildschirm, Kas-settenlaufwerk, 64 KB RAM

2.4.4 Zitate

“I think there is a world market for about five computers.”Thomas J. Watson Jr., chairman of IBM (1943)

“Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs 30 tons,computers in the future may have only 1,000 vacuum tubes and perhaps weigh 1 1

2tons.”

Popular Mechanics (March 1949)

“640 K [of computer memory] ought to be enough for anybody.” Wird Bill Gates zugeschrieben,der dies aber bestreitet.

2.5 Geschichte der Programmiersprachen

• Heute gibt es uber 2500 verschiedene Programmiersprachen

• Siehe Aushang, bzw. www.levenez.com

prozedural: Assembler, Fortran (1954), PL/1, Basic, Algol, APL, C, Pascal, Cobol, Perl, PHP,ADA

funktional: Lisp (1958), Haskell, Miranda, Mathematica

logisch: Prolog (1970)

objektorientiert: Simula 67, Smalltalk (1969), C++, Oberon, Java, C#

Fakultat in C, Prolog, Mathematica

C (prozedural):

1 int fakultaet(int n)2 3 int ergebnis;45 if (n == 1) return 1;6 ergebnis = n * fakultaet(n-1);7 return(ergebnis);8

Mathematica (funktional):

19

1 Fac[0] := 1;2 Fac[n_] := n * Fac[n - 1]

Prolog (logisch):

1 fakultaet(1,1).2 fakultaet(N,Res) :- N1 is N-1, fakultaet(N1,Res1), Res is N * Res1,

2.6 Geschichte des Internet

• Gegrundet 1962 durch die Advanced Research Projects Agency (ARPA) der USA (AR-PANET).

• Unter der Leitung von Bob Kahn und Vint Cerf entstehen 1973 das Transmission ControlProtocol (TCP) und 1976 das IP Protokoll in Form von RFC Dokumenten.

• Erstes Email-Netz 1977 an der Univ. Wisconsin.

• TCP/IP wird weltweit eingefuhrt

• Tim Berners-Lee erfindet 1989 am CERN das World Wide Web (WWW)

“In the Beginning, ARPA created the ARPANET.

And the ARPANET was without form and void.

And darkness was upon the deep.

And the spirit of ARPA moved upon the face of the network and ARPA said, ’Let there be aprotocol,’ and there was a protocol. And ARPA saw that it was good.

And ARPA said, ’Let there be more protocols,’ and it was so. And ARPA saw that it was good.

And ARPA said, ’Let there be more networks,’ and it was so.”

– Danny Cohen

2.6.1 Das Semantic Web

• Neben Text und Bildern soll der Inhalt (Semantik) von Webseiten in Zukunft durchAnnotationen formal beschrieben werden.

• Anfrage: Wie viele Tore hat Michael Ballack im Jahre 1998 geschossen?

• Google kann die Anfrage nicht beantworten.

• Das Semantic Web soll das demnachst konnen.

• Resource Description Framework (RDF) und Web Ontology Language (OWL) zur Be-schreibung von Metainformation uber Webseiten

• Unter Verwendung von Automatischen Theorembeweisern sollen semantische An-fragen beantwortet werden.

20

2.6.2 Aktuelle Trends (2005)

2.6.3 Aktuelle Trends (2008)

2.7 Große Informatiker

Blaise Pascal (Frankreich, 1623–1662)

• baute als 18 jahriger fur seinen Vater die erste funktionierendemechanische Rechenmaschine zur Addition sechsstelliger Zahlen.(Digitalrechner)

21

Gottfried Wilhelm Leibniz (Leipzig, 1646–1716)

• Philosoph, Mathematiker, Diplomat, Bibliothekar

• baut eine Rechenmaschine fur alle vier Grundrechenarten.

• Grunder der Akademie der Wissenschaften in Berlin

• Erfindung der Dualzahlen

Charles Babbage (England, 1791-1871)

• Entwickelt die Difference Engine zur Ableitung von Polynomen(1823)

• Entwickelt die Analytical Engine (1833)

Kurt Godel (Osterreich, 1906–1978)

Der Osterreicher Kurt Godel zeigt 1931

• dass in der Pradikatenlogik erster Stufe alle wahren Aussagenherleitbar sind.

• In Logiken hoherer Stufe hingegen gibt es wahre Aussagen, dienicht beweisbar sind. Es lassen sich also nicht alle Berechnungs-aufgaben automatisieren.

Zusammen mit Einstein arbeitet er auch an der Relativitatstheorie undKosmologie.

Denken Sie nach uber die Aussage: ,,Ich bin nicht beweisbar” oder uber ,,Die Menge allerBarbiere, die all die Menschen rasieren, die sich nicht selbst rasieren.” oder uber dieMenge x|x /∈ x.

Alan Turing (England, 1912–1954)

Der Brite Alan Turing leistet u.a. folgendes

• Er erfindet 1935 das bis heute universelle Berechnungsmodell, die “Turingmaschine”.

• Er zeigt, dass es viele Funktionen gibt, die nicht berechenbar sind.

• Er beweist das Halteproblem: Es kann kein Programm geben, das in endlicher Zeit ent-scheidet, ob ein beliebiges Programm auf einer Eingabe halt oder eine Endlosschleife hat.

• Er definiert den Begriff der Intelligenz uber den “Turing Test”.

• Ende der Dreißiger Jahre macht er schon Vorschlage fur lernfahige Computer.

• Er ist im 2. Weltkrieg fuhrend beteiligt an der Dechiffrierung der Enigma.

• Er ist beteiligt am Bau von Colossus, dem ersten britischen Computer fur die Dechiffrie-rung der Enigma (1944).

• Er entwickelt einen Schachalgorithmus. Mangels Computer simuliert er auf Papier denComputer und benotigt so etwa 90 Minuten pro Zug.

22

Denken Sie nach uber das Programm:

Unmoglich(int i)if( halt(unmoglich,0))

while( TRUE ) printf(“das kann noch dauern ...”);else

printf(“0”);

Die Turingmaschine: H A L L O

Z Zustand

Lesekopf

Claude Shannon (Michigan, 1916–2001)

• A Mathematical Theory of Communication (1948)

• Informationstheorie, Entropie als Informationsmaß

• Formale Grundlagen der Kryptographie (Konfusion und Diffusi-on, 1949)

• Entwickelt einen Schachcomputer (1960)

Alonzo Church (Washington, 1903–1995)

• Berechenbarkeit

• Lambda Kalkul

• Church’sche These: Die Turingmaschine kann alles berechnen, waswir intuitiv fur berechenbar halten.

John von Neumann (Polen, 1903–1957)

• Spieltheorie, Minimax Algorithmus (1928)

• Quantenmechanik, Entwicklung der Atombombe

• von Neuman Architektur von Rechnern (EDVAC)

• genial, lebenslustig, trinkfest

Die vonNeumann-Architektur

• Zentraleinheit (CPU mit Rechen- und Steuer-werk)

• Speicher (Hauptspeicher)

• Bus (Busse)

• Ein/Ausgabe (I/O) ⇒ Peripheriegerate

CPURechenwerk Steuerwerk

Speicher(RAM)

I/O

Datenbus

Adressbus

23

Edsger Dijkstra (Rotterdem, Holland, 1930–)

• Algorithmen auf Graphen

• Kurzeste Wege Algorithmen

• Korrektheit von Programmen

Donald Knuth (Milwaukee, 1938–)

• Meister der Algorithmen, u.a.: Zufallszahlen, Sortieren, Suche, ...

• Autor der 5-bd. ,,Bibel”: The Art of Computer Programming

• Erfinder des Textsatzsystems TEX

• spielt eine selbstgebaute Orgel

Zitate: ,,Computer Programming is an art form, like the creation of poetry or music.”,,I got into compilers because I thought the most amazing thing you could do with computerswas to have them write their own programs. When computing is applied to computing, that’swhen computer science reaches an ultimate completeness.”

Stephen A. Cook (Buffalo, New York, 1939–)

• Begrunder der modernen Komplexitatstheorie

• NP-Vollstandigkeit

Leslie Lamport (New York, 1941–)• Theorie verteilter Systeme

• Lamport clock: partielle Ordnung der Zeit, kei-ne globale Zeit

• Enwickler von LATEX(TEX-Macropaket)

Zitat: ,,When I look back on my work, most of it seems like dumb luck – I happened to belooking at the right problem, at the right time, having the right background.”

Ken Thompson, Dennis Ritchie (New Orleans, 1943–, New York, 1941–)

• 1969: Erfindung von UNIX und C (Bell Labo-ratories, New Jersey, spater AT&T)

• Viele innovative Konzepte: Pipelining, verteil-te Prozesse, Sockets, Timesharing und Prozes-se mit Prioritaten (auch auf PCs)

Nikolaus Wirth (Winterthur, Schweiz, 1934–)

• Erfinder der Programmiersprachen Pascal (1970) und Modula(1975)

• Erfinder der Objektorientierten Sprache Oberon (1987)

24

Bill Gates (Seattle, 1955–)

• brach nach zwei Jahren sein Studium in Harvard ab.

• zus. mit Paul Allen Grunder von Microsoft

• mit d. Kauf von MS-DOS 1980 durch IBM beginnt die Erfolgsstory vonMicrosoft

• 1983 erscheint die erste Version des Betriebssystems Windows

• reichster Mann der Welt (fast 50 Mrd. US$)

Tim Berners-Lee (London, 1955–)

• 1989 schlug Berners-Lee seinem Arbeitgeber CERN (EuropaischesKernforschungslabor) ein Projekt vor, das auf dem Prinzip desHypertexts beruhte und den weltweiten Austausch sowie dieAktualisierung von Informationen zwischen Wissenschaftlern ver-einfachen sollte.[1]

• entwickelte den ersten Webbrowser, baute die erste Webseite

2.7.1 Der Turing Award

siehe www.acm.org/awards/taward.html

ACM’s most prestigious technical award is accompanied by a prize of $ 100,000.Financial support of the Turing Award is provided by the Intel Corporation.ACM: Association of Computing Machinery

1966 A.J. Perlis Compilerbau1967 Maurice V. Wilkes EDSAC, erster Computer mit internem Programmspeicher1968 Richard Hamming Kodierung, Hamming-Distanz1969 Marvin Minsky Perzeptron, Neuronale Netze1970 J.H. Wilkinson Numerik1971 John McCarthy Kunstliche Intelligenz, LISP1972 E.W. Dijkstra Graphenalgorithmen, ALGOL1973 Charles W. Bachman Datenbanken1974 Donald E. Knuth Algorithmen, “The Art of Computer Programming”, Erfinder von TEX1975 Allen Newell, Herbert A. Simon Kunstliche Intelligenz, General Problem Solver1976 Michael O. Rabin, Dana Scott Automaten, Alg., Nichtdeterminismus, randomisierte Alg.1977 John Backus FORTRAN, Backus-Naur-Form Grammatik1978 Robert W. Floyd formale Methoden zur Software Entwicklung1979 Kenneth E. Iverson Programmiersprachen, APL1980 C. Antony R. Hoare Programmiersprachen1981 Edgar F. Codd Relationale Datenbanken1982 Stephen A. Cook Komplexitat, NP-Vollstandigkeit1983 Ken Thompson, Dennis Ritchie Betriebssystem UNIX1984 Niklaus Wirth MODULA, PASCAL, Oberon1985 Richard M. Karp NP-Vollstandigkeit1986 John Hopcroft, Robert Tarjan Algorithmen und Datenstrukturen (Lehrbuch)1987 John Cocke Compilerbau, RISC-Computer1988 Ivan Sutherland Computergraphik1989 William (Velvel) Kahan Numerik, Floating Point Arithmetik1990 Fernando J. Corbato Time sharing1991 Robin Milner Logik, funktionale Progarmmierung: ML1992 Butler W. Lampson PC-Entwicklung (Microsoft)1993 Juris Hartmanis, Richard Stearns Komplexitatstheorie1994 Edward Feigenbaum, Raj Reddy Kunstliche Intelligenz, prakt. Umsetzung1995 Manuel Blum Komplexitatstheorie, Kryptographie1996 Amir Pnueli Temporallogik, Programmverifikation1997 Douglas Engelbart Maus, Fenster1998 James Gray Datenbanktechniken1999 Frederick P. Brooks Rechnerarchitaktur, IBM 3602000 Andrew Chi-Chih Yao Zufallszahlen, Kryptographie2001 Ole-Johan Dahl, Kristen Nygaard Simula, OOP2002 Ron Rivest, Adi Shamir, Leonard Adleman Public Key Kryptographie, RSA-Algorithmus

25

2003 Alan Kay Objektorientierte Programmierung, Smalltalk2004 Vinton G. Cerf, Robert E. Kahn Vernetzung, TCP/IP2005 Peter Naur Design von Programmiersprachen (Algol 60), Compilerdesign2006 Frances E. Allen Parallele Programmierung, erste Frau mit Turing Preis!2007 E. Clarke, A. Emerson, J. Sifakis Modellprufung

2.8 Frauen in der Informatik

Warum gibt es so wenige Frauen in der Informatik?1

• Intelligenztests zeigen minimale Unterschiede ausschließlich bei:

Vorstellung raumlicher Drehungen von Figuren zugunsten der Manner Sprachkompetenzen zugunsten der Frauen

• Es gibt keine Intelligenz und Begabungsunterschiede die die geringe Beteiligung der Frau-en erklaren konnen!

Frauenanteil am Informatik-Studium (2001)

Land Frauenanteil [%]England 35Italien, Frankreich, Spanien, Portugal 40–50fruhere Sowjetunion 50Bulgarien 60–70Griechenland 59Indien, Malaysia, Singapur 50Deutschland 8

2.8.1 Frauen in der Geschichte der Informatik

Ada Augusta von Lovelace (1815-1852)

• arbeitet mit Ch. Babbage an der Analytical Engine

• Sie erfand Unterprogramme, Schleifen und bedingte Sprunge!

• publizierte unter dem Kurzel A.A.L.

• Mutter von vier Kindern

Grace Murray Hopper (1906-1992)

• beteiligt an Entwicklung von Mark 1, Mark 2, Univac 1

• entwickelt 1952 einen der ersten Compiler

• “Debugging”: Eine tote Motte (bug) blockiert ein Relais im Rech-ner. Zitat: First actual case of a bug being found.

• Zitat: Wenn du eine gute Idee hast, dann tu es einfach, denn esist viel einfacher sich hinterher zu entschuldigen, als vorher umGenehmigung zu bitten.

• Uber 40 Ehrendoktorwurden und Preise

1teilweise entnommen aus Olga Goldmann Seminar: Geschichte der Informatik, www.virtosphere.de/schillo/teaching/WS2001/Geschichts-Seminar.html

26

Bis etwa 1960 waren viele Frauen in der Informatik tatig:

• Beim Knacken der Enigma in Bletchley Park (England)

• Bei der Bedienung und Programmierung fruher Rechner, u.a. Colossus (G.B.), Eniac(USA), nach dem Krieg in Deutschland

2.9 Wichtige Institute und Firmen

IAS: Institute for advanced studies, Princeton, New Jersey, USAMIT: Massachusettes Institute for Technology, Cambridge, Massachusetts, USASRI: Stanford Research Institute, Palo Alto, USAStanford University, Palo Alto, California, USAHarvard University, Cambridge, Massachusetts, USAUCB: Univ. of California, Berkeley, USAAT&T Bell Labs: New Jersey, USA

27

Kapitel 3

Algorithmen und Datenstrukturen –Einfuhrung

In diesem Kapitel werden hauptsachlich Sortieralgorithmen untersucht. Ziel ist hier aber nichtprimar das Sortieren. Vielmehr wird hier an einem einfachen Beispiel die Entwicklung undVerbesserung von Algorithmen und Datenstrukturen aufgezeigt. Wichtig ist auch die mathe-matische Analyse der Algorithmen bezuglich Rechenzeit und Speicherplatzverbrauch.

3.1 Sortieren durch Einfugen

Beispiel 3.1 7 4 8 3 5 14 7 8 3 5 14 7 8 3 5 13 4 7 8 5 13 4 5 7 8 11 3 4 5 7 8

Definition 3.1 Eine Liste A = (A1, . . . , An) heisst sortiert, wenn fur allei = 1, . . . , n− 1 gilt Ai ≤ Ai+1.

3.1.1 Algorithmus (grob)

Von links nach rechts: eine Zahl x wahlen und verschieben nach links bis Ai−1 ≤ Ai = x ≤ Ai+1

erfullt ist.

For i:= 2 To n Do

x:= a[i];

"fuge x am richtigen Platz ein"

3.1.2 Algorithmus als PASCAL-Programm

Index i: 0 1 i nListe A: x a(i)

Program Sortieren(input,output);

CONST n = 8000;

TYPE

index = 0..n;

item = RECORD

key : Integer;

data : String[20]

END;

itemarray = ARRAY [0..n] OF item;

VAR a : itemarray;

RechenzeitProcedure Ins sort(var a: itemarray);

VAR worst case best casei,j : index; (Tmax(n)) (Tmin(n))x : item;

BEGIN

FOR i := 2 TO n DO (n− 1) · (I + C) (n− 1) · (I + C)BEGIN

x := a[i]; a[0] := x; j := i-1; (n− 1) · (3M + I) (n− 1) · (3M + I)WHILE x.key < a[j].key DO

∑ni=2 i · C (n− 1) · C

BEGIN

a[j+1] := a[j];∑n

i=2(i− 1) · (M + I) 0

j := j-1;∑n

i=2(i− 1) · (M + I) 0

END;

a[j+1] := x (n− 1) · (I +M) (n− 1) · (I +M)END

END;

Durch kopieren von a(i) auf die Variable x und auf a(0) wird die Terminierung der Schleifesichergestellt. Sollte die Zahl a(i) also kleiner als alle Elemente davor in der Liste sein undganz nach links verschoben werden mussen wurde der Schleifenindex i ohne diese Terminierungeinen negativen Wert annehmen. Da die Liste aber bei a(0) aufhort, wurde dies zu einem unde-finierten Zustand fuhren. Diese Terminierung spart im Kopf der While-Schleife eine zusatzlicheBedingung ein und reduziert somit den Aufwand proportional zu n.

3.1.3 Worst - Case Rechenzeit

Im Programmcode eingetragen ist fur jede Programmzeile die Laufzeit. Als Parameter tretenrechnerabhangigen Großen I (Increment), M (Move) und C (Compare) auf:I = Rechenzeit fur eine ZahloperationM = Rechenzeit fur eine ZuweisungsoperationC = Rechenzeit fur eine Vergleichsoperation

Diese Zeiten sind konstant, d.h. nicht von n abhangig und deshalb fur die Berechnung derKomplexitat unbedeutend. Fur die Berechnung von exakten Laufzeiten sind sie jedoch sehrwichtig.

29

Tmax(n) = (n− 1) · (I + C + 3M + I +M + I)

+n∑i=2

(i · C + (i− 1) · (2M + 2I))

= (3I + 4M + C) · n− (3I + 4M + C)

+C ·n∑i=2

i+ 2(I +M) ·n∑i=2

(i− 1)

mitn∑i=2

i =n(n+ 1)

2− 1 =

n2 + n− 2

2=n2

2+n

2− 1

und n∑i=2

(i− 1) =n−1∑i=1

i =n(n− 1)

2=n2

2− n

2

erhalten wir

Tmax(n) =

a︷ ︸︸ ︷(I +M +

C

2) ·n2 +

b︷ ︸︸ ︷(2I + 3M +

3

2C) ·n

c︷ ︸︸ ︷−(3I + 4M + 2C)

= a · n2 + b · n+ c

Wenn die Konstanten nicht interessieren, kann die Berechnung der Worst-Case Rechenzeitvereinfacht werden:

(n− 1) · (I + C) → (n− 1) · c1

(n− 1) · (3M + I) → (n− 1) · c2n∑i=2

i · C → (n∑i=2

i) · c3

......

...

Ergebnis: a · n2 + b · n+ c

Bestimmung von a, b und c

1.) Messe drei Zeiten fur verschiedene n = n1, n2, n3

−→ (n1, T1), (n2, T2), (n3, T3)

T(n)

nn1 n2 n3T1

T3

T2

30

2.) Einsetzen in Parabelgleichung:T1 = a · n2

1 + b · n1 + cT2 = a · n2

2 + b · n2 + cT3 = a · n2

3 + b · n3 + c

3.) Auflosen des linearen Gleichungssystems nach a, b und c (siehe Ubung 2).

Beispiel 3.2 Vergleich von 3 verschiedenen Komplexitaten

Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5n T (n) = T (n) = c · n T (n) = c · n2 T (n) = c · n3 T (n) = c · 2n

log n · c10 1 s 10 s 100 s 1 000 s 1024 s100 2 s 100 s 10 000 s 1 000 000 s ≈ 1030 s1000 3 s 1000 s 1 000 000 s 1 000 000 000 s ≈ 10300 s

Die Werte wurden mit einem c von einer Sekunde errechnet. Eine bessere Hardware wurde nurdieses c verbessern und dadurch die Rechenzeit nicht wesentlich beeinflussen. Bei großen n istdie Komplexitat viel ausschlaggebender als die Konstante c.

3.1.4 Best-Case Rechenzeit

Ist die Liste A vorsortiert, so wird die While-Schleife nicht durchlaufen und das Programm istviel schneller.

Analog zu den Berechnungen im Worst-Case kann man auch im Best-Case die Zeiten aus derTabelle aufaddieren und man erhalt

Tmin(n) = d · n+ e.

3.1.5 Einschub: Asymptotik

Beschreibung des asymptotischen Verhaltens von Rechenzeiten T (n) (oder Speicherplatz oderanderer Funktionen) fur n→∞.

Idee: Vernachlassigung von konstanten Faktoren. Nur die Abhangigkeit von n fur große n istwichtig.

31

Definition 3.2 Seien die Funktionen f : N→ R+, g : N→ R+ gegeben - R+ = x ∈ R|x ≥0. Dann schreibt man:

Asymptotische obere Schranke:

f(n) = O(g(n)), wenn ∃ c ∈ R+ : limn→∞

f(n)

g(n)≤ c

f(n) = o(g(n)), wenn limn→∞

f(n)

g(n)= 0

Asymptotische untere Schranke:

f(n) = Ω(g(n)), wenn ∃ c ∈ R+ : limn→∞

f(n)

g(n)≥ c

f(n) = ω(g(n)), wenn limn→∞

f(n)

g(n)=∞

Asymptotische enge (harte) Schranke:

f(n) = Θ(g(n)), wenn ∃ c1, c2 ∈ R+ : c1 ≤ limn→∞

f(n)

g(n)≤ c2

Bedeutung von O, o, ω,Ω,Θ:

f = O(g): f wachst hochstens so schnell wie g, kann aber gleich schnell wie g wachsen.

f = o(g): f wachst weniger schnell als g

f = Ω(g): f wachst mindestens so schnell wie g, kann aber gleich schnell wie g wachsen.

f = ω(g): f wachst schneller als g

f = Θ(g): f und g wachsen gleich schnell

O,Ω,Θ, o, ω sind Relationen auf Funktionen, wie z.B. <,≤ auf reellen Zahlen.

Analogien:

Funktionen f : N→ R+ reelle Zahlenf(n) = O(g(n)) a ≤ bf(n) = o(g(n)) a < bf(n) = Ω(g(n)) a ≥ bf(n) = ω(g(n)) a > bf(n) = Θ(g(n)) a = b

Beispiele:

32

f(n) = 0.001 · n2 g(n) = 1000 · n⇒ f = O(g) und f = o(g)

f(n) = n5 g(n) = 0.001 · 5n ⇒ f = O(g) und f = o(g)

33

f(n) = 10 · n g(n) = n ⇒ f = Θ(g)

Satz 3.1T (n) = Θ(g(n)) ⇔ T (n) = Ω(g(n)) und T (n) = O(g(n))

Die bisher berechneten Ergebnisse lassen sich nun also formulieren wie folgt:

Satz 3.2 Beim Sortieren durch Einfugen gilt

Tmin(n) = Θ(n)

Tmax(n) = Θ(n2)

T (n) = Ω(n)

T (n) = O(n2)

3.1.6 Schwachstellen und mogliche Verbesserungen

x

Die Suche nach der Einfugestelle fur das Element x soll verbessert werden.

Suche in Listen

Aufgabe 1: Suche ein Element x in einer beliebigen Liste.

optimale Losung: lineare Suche mit Tmax(n) = Θ(n)

Aufgabe 2: Suche ein Element x in einer sortierten Liste A[1 . . . n]

optimale Losung: Bisektion

34

Der Bereich links von x ist bereits sortiert. Man findet die richtige Stelle fur x indem man dieListe links von x mehrfach halbiert.

Definition 3.3 bxc := maxy ∈ Z|y ≤ x. bxc ist also die großte ganze Zahl kleiner odergleich x. Analog sei dxe = miny ∈ Z|y ≥ x.

Der Bisektionsalgorithmus

Bisektion(A,x)a = 1b = nm = ba+b

2c

while A[m] 6= x & b > aif x < A[m]

then b = melse a = m

m = ba+b2c

if A[m] == xthen print (”Hurra ”,x,”gefunden an Position ”,m)else print (”Schade, ”,x,”nicht in A”)

Komplexitat

Sei die Arraylange n = 2k. Dann sind hochstens k Wiederholungen der While-Schleife erforder-lich. Also ist die Rechenzeit proportional zu k, d.h. T (n) = c · k.

n = 2k

ln(n) = k · ln 2

k =ln n

ln 2

Also gilt fur die Bisektion

T (n) = c · ln n

ln 2= c · log2 n = O(log n)

Erlauterung: An log2 x = ln xln 2

= c · ln x ← log n, erkennt man, daß sich alle Logarithmen nurum einen kostanten Faktor unterscheiden wenn man nur ihre Basis andert.Das Suchen der Einfugestelle ist mit logarithmischem Aufwand moglich.Aber: verschieben der O(n) Arrayelemente im Array kostet linearen Aufwand.Idee: verwende dynamische Datenstruktur als verkettete Liste.

x

35

Verschieben der Arrayelemente ist damit unnotig. x wird direkt an der richtigen Stelle eingefugt.Aber: die Bisektion ist auf einer verketteten Liste nicht anwendbar.Daher: fur Sortieren durch Einfugen bleibt Tmax(n) = Θ(n2)

3.2 Quicksort

Es soll die Liste 5, 3, 2, 6, 4, 1, 3, 7 sortiert werden. Dies erfolgt nach dem Prinzip divide andconquer durch rekursiv wiederholtes Aufteilen und bearbeiten, wie in folgender Tabelle zusehen:

5 3 2 6 4 1 3 7 x = 5 (Pivotelement)↑i ↑j

5 3 2 6 4 1 3 7↑i ←→ ↑j3 3 2 6 4 1 5 7

↑i ↔ ↑j3 3 2 1 4 6 5 7

↑j ↑i3 3 2 1 4 6 5 7 x = 3, x = 6↑i ←→ ↑j ↑i↔↑j1 3 2 3 4 5 6 7

↑i↔↑j ↑j ↑i1 2 3 3 4 5 6 7

↑j ↑i ↑i↑j1 2 3 3 4 5 6 7↑i↑j ↑i↔↑j

1 2 3 3 4 5 6 7↑j ↑i

1 2 3 3 4 5 6 7↑i↑j

1 2 3 3 4 5 6 7

Erlauterung: Der erste Wert der Liste ist das Pivotelement (ausgezeichnetes, besonderes Ele-ment). Zwei Indizes i und j durchlaufen die Liste nach folgendem Kriterium:i sucht von links nach einem Wert ≥ x und j von rechts nach einem Wert ≤ x. Dann werdenInhalt von i und von j vertauscht. Das setzt sich solange fort bis sich beide Indizes uberkreuzenoder gleich sind. Dann wird die Liste rechts von j geteilt und auf beiden Halften rekursiv vonvorne begonnen.

3.2.1 Der Algorithmus

Seien A=Liste, p=Anfangsindex, r=Endeindex. Dann ist die rekursive Struktur gegeben durch:

Quicksort(A,p,r)if p < r

then q=Partition (A,p,r)Quicksort (A,p,q)Quicksort (A,q+1,r)

36

Das Aufteilen erfolgt mittels

Partition(A,p,r)x=A[p]i=p-1j=r+1while TRUE do

repeat j=j-1until A[j] ≤ x

repeat i=i+1until A[i] ≥ x

if i < jthen vertausche A[i] mit A[j]else Return(j)

Der erste Aufruf von Quicksort auf einer Liste der Lange n erfolgt durch

Quicksort(A,1,length(A))

3.2.2 Analyse

Laufzeit von Partition

auf Array A[p...r] mit n = r − p+ 1

T (n) = Θ(n)

Laufzeit von Quicksort im Best Case

2

1 1

2

1 1

n/4

2

1 1

2

1 1

n/4

n/2

... ... ...

2

1 1

2

1 1

n/4

2

1 1

2

1 1

n/4

n/2

... ... ...

log n Ebenen2

n

...

Rekursionsbaum

Der Rekursionsbaum hat n Blattknoten. Er wachst in der Breite exponentiell. Trotzdem ist dieKomplexitat auf jeder Ebene Θ(n). Warum?

37

Zahl der Ebenen im Rekursionsbaum? Zur Vereinfachung nehmen wir an, das Array hatn = 2k Elemente. Dann ist die Tiefe des Baumes gleich k. Auflosen nach der Tiefe k ergibt:

log2 n = log2 2k = k.

Die gesamte Rechenzeit ist also hier gleich der Produkt aus dem Aufwand pro Ebene und derZahl der Ebenen (Tiefe):

Tmin(n) = c · n · log2 n = Θ(n log n)

Laufzeit von Quicksort im Worst Case (sortierte Liste)

1 2 3 4 5 6 7 8↑i ↑j

1 2 3 4 5 6 7 8↑i↑j

1 2 3 4 5 6 7 8↑i↑j

1 2 3 4 5 6 7 8↑i↑j

2

1

1

1

1

n

n−1

1 2

n−1

n

n−2n Ebenen

Aufwand pro Ebene:

n

Rekursionsbaum

Tmax(n) = c2 · (n∑i=2

i+ n)

= c2 · (n(n+ 1)

2− 1 + n)

= c2 · (n2

2+

3

2n− 1)

= Θ(n2)

Fur die Rechenzeit T(n) gilt:

c1 · n log n ≤ T (n) ≤ c2 · n2

38

Idee zur Verhinderung des Worst Case: Liste vorher zufallig permutieren.Begrundung: Die Wahrscheinlichkeit fur das Erzeugen einer sortierten Liste ist sehr klein. 1

10n

falls nur 10 Zahlen erlaubt sind.Allgemeine Wahrscheinlichkeit: 1

Mn fur M unterschiedliche zu sortierende Werte und n verschie-dene Zahlen in der Liste.

Beispiel 3.3 32 Bit Integer Zahlen: M = 232, n = 106, 1Mn = 1

(232)106= 1

232·106

Folgerung: Die Wahrscheinlichkeit, dass ein randomisiertes Quicksort den Worst-Case trifftist sehr klein. Aber die zufallige Permutation der Liste vor dem Sortieren kostet Rechenzeit.Daher:Zufallige Wahl des Pivotelementsersetze in Partition x = A[p] durch x = A[random (p,r)]

oder Ersetzung von Partition (A,p,r) durch:

Random-Partition(A,p,r)i=Random (p,r)

vertausche A[p] mit A[i]return Partition (A,p,r)

Random (p,r) liefert zufallig mit konstanter Wahrscheinlichkeit eine Zahl aus p, p+1, . . . ,r.Bemerkung: Durch Randomisierung gibt es keine Eingabe mehr, fur die der Algorithmusimmer Worst-Case Verhalten zeigt.Average-Case-Analyse: Berechnung der mittleren Laufzeit des Algorithmus z.B. Quicksortauf einer reprasentativen Menge von Eingaben.

Beispiel 3.4 Die Average-Case-Analyse fur Quicksort ist sehr schwierig. Daher wird hier derungunstige Fall eines konstanten Aufteilungsverhaltnisses 1 : m am Beispiel 1 : 9 behandelt.

729n 81n10001000

81n1000

9n1000 1000

81n 9n1000

9n1000

1n1000

n

9n/10081n/100 9n/100 1n/100

9n/10 1n/10

( 910

)dl · n = 1 ( 110

)dr · n = 1

dl · log9

10+ log n = 0

dl =log n

log 109

T (n) <c

log 109

· n log n

39

Tiefe k = logn

log 109

≈ 21, 8 · log10 n

Aufwand auf jeder Ebene ≤ n ⇒ T (n) = O(n · log n). Da die komplexitat von Quicksortim Best-Case auch n · log n ist, gilt:

Satz 3.3 Quicksort besitzt im Average-Case die Komplexitat T (n) = Θ(n · log n)

3.3 Sortieren mit Baumen (Heapsort)

Beispiel 3.5i : 1 2 3 4 5 6 7 8 9 10

A[i] : 16 14 10 8 7 9 3 2 4 1

Darstellung von A als Baum:

16

8

2 4

7

1

14 10

9 3

2 3

1

4 5 6 7

1098

Keine neue Datenstruktur notig, sondern nur Funktionen parent, left, right mit den Eigenschaf-ten

parent(i) = b i2c (Vorganger)

left(i) = 2i (linker Nachfolger)right(i) = 2i+ 1 (rechter Nachfolger)

Definition 3.4 Ein Array mit den Funktionen left, right, parent heisst Heap, wenn gilt

A[parent(i)] ≥ A[i]

Die Anzahl der Elemente in dem Array A bezeichnen wir mit length(A), die Anzahl derElemente in A, die einen Heap bilden, bezeichnen wir mit heapsize(A).

Definition 3.5 Die Hohe eines Knotens i in einem Baum ist gleich der Zahl der Kantenim langsten Pfad von i zu einem Blattknoten. Die Hohe des Baumes ist gleich der Hohedes Wurzelknotens.

Der folgende Algorithmus verwandelt einen Binarbaum in einen Heap unter der Voraussetzung,dass beide Unterbaume schon Heaps sind.

40

Heapify(A,i)vertausche A[i] mit seinem großten NachfolgerA[largest] falls A[largest] > A[i]Heapify (A,largest)

Beispiel 3.6

28 8

9

%%ee

144

110

75

bbb

42

96 3

7

%% ee

103

"""PPPPP

161

28 8

9

%%ee

44

110

75

bbb

142

96 3

7

%% ee

103

"""PPPPP

161

28 4

9

%%ee

84

110

75

bbb

142

96 3

7

%% ee

103

"""PPPPP

161

Der Algorithmus

Heapify(A,i)l = Left(i)r = Right(i)if l ≤ heapsize(A) AND A[l] > A[i]

then largest = lelse largest = i

if r ≤ heapsize(A) AND A[r] > A[largest]then largest = r

if largest 6= ithen vertausche A[i] mit A[largest]

Heapify(A, largest)

Laufzeit von heapify

Vergleich von A[i] mit A[left(i)] und A[right(i)]: konstante Zeit= Θ(1)

Rekursion

Die maximale Zahl von Knoten in einem der Unterbaume geht fur grosse n asymptotisch gegen23n, wenn n = Zahl der Unterknoten in i.

Rekurrenzrelation

T (n) ≤ T (2

3n) + Θ(1)

Das Auflosen der Rekurrenzrelation erfolgt mit Hilfe des Mastertheorems:

Satz 3.4 (Mastertheorem) Seien a ≥ 1, b > 1 Konstanten und f : R+ → R+, T : R+ → R+

Funtionen mitT (n) = aT (n/b) + f(n)

41

wobei n/b fur die ganzzahlige Division (bn/bc oder dn/be) steht. Dann kann T (n) asymptotischbeschrankt werden durch

T (n) =

Θ(nlogb a) falls ∃ε>0 : f(n) = O(nlogb a−ε)

Θ(nlogb a log n) falls f(n) = Θ(nlogb a)

Θ(f(n)) falls ∃ε>0 : f(n) = Ω(nlogb a+ε) und

∃c<1∃n0∀n≥n0 : af(n/b) ≤ cf(n)

Fur Heapsort gilt T (n) ≤ T (23n) + Θ(1). Fur den Worst Case gilt

Tmax(n) = 1 · Tmax(

n

3/2

)+ c

Fur die Anwendung des Mastertheorems gilt dann also a = 1, b = 32, f(n) = Θ(1) sowie

nlogb a = nlog 3

21

= 1

Es ist der zweite Fall anwendbar, denn f(n) = Θ(nlogb a). Also gilt fur heapify

Tmax(n) = Θ(1 · log n) = Θ(log n).

Beispiel 3.7 Anwendung des Master-Theorems auf Quicksort (Best Case):

T (n) = 2T (n2) + c · n

a = 2, b = 2, f(n) = c · nnlogb a = nlog2 2 = nf(n) = Θ(n)⇒ 2. Fall: T (n) = Θ(n · log n)

Beispiel 3.8 wie oben, jedoch mit anderem f(n):

T (n) = 2T (n2) + c · log n

a = 2, b = 2, f(n) = c · log nnlogb a = nf(n) = c · log n = O(n(1−ε))⇒ 1. Fall: T (n) = Θ(n)

3.3.1 Erzeugen eines Heap

Build-Heap(A)

for i = blength(A)2

c downto 1do heapify(A,i)

Beispiel 3.9

42

148 8

9

%% @@

24

710

165

HHHH

12

96 10

7

ee

33

PPPPP

41

28 8

9

%% ee

144

710

165

bbb

12

96 10

7

ee

33

PPPPP

41

28 8

9

%% ee

144

710

165

bbb

12

96 3

7

%% ee

103

"""PPPPP

41

28 8

9

%%ee

144

110

75

bbb

162

96 3

7

%% ee

103

"""PPPPP

41

28 4

9

%%ee

84

110

75

bbb

142

96 3

7

%% ee

103

"""PPPPP

161

Analyse

obere Schranke

Jeder der Θ(n) Aufrufe von heapify kostet O(log n) Zeit. Also gilt

=⇒ T (n) = O(n log n).

bessere Schranke

Die Laufzeit von heapify hangt von der Hohe des Knotens im Baum ab. Die meisten Knotenhaben sehr niedrige Hohe!

(Zahl der Knoten auf Hohe h) ≤ d n

2h+1e

Die Laufzeit von heapify fur Knoten der Hohe h wachst linear mit h. Also Theapify(h) = O(h) =O(log(Anzahl Knoten im Unterbaum))

T (n) ≤blognc∑h=1

⌈ n

2h+1

⌉·O(h) = O

n blognc∑h=1

h

2h

= O(2n) = O(n)

Die vorletzte Gleichung gilt weil

∞∑h=1

h

2h=

12

(1− 12)2

= 2,

was man in der Formelsammlung findet.

3.3.2 Der Heapsort - Algorithmus

Voraussetzung: Build-Heap setzt maximales Element an die Wurzel, d.h. in A[1]

43

Idee

Wiederhole folgende Schritte bis der Heap nur noch aus einem Element besteht:

1.) vertausche A[1] mit A[n]2.) losche A[n] aus dem Heap3.) Heapify (A,1)

Beispiel 3.10

2

7 9 3

2 3

1

4 5 6 7

1098

14

4

1 16

108

i

7

2 3

1

4 5 6 7

1098

4

16

8

1

14

i

9

3

2

10

7

2 3

1

4 5 6 7

1098

4

16

8

1

14

2

3

10

i

9

2 3

1

4 5 6 7

1098

4

16

1

14

3

10

9

8

7

2

i

2 3

1

4 5 6 7

1098 1614

3

10

92 8

7

4

1

i

2 3

1

4 5 6 7

1098 1614

3

10

987

4

2

1

i

2 3

1

4 5 6 7

1098 161410

9874

2

3

1i

2 3

1

4 5 6 7

1098 161410

9874

3

2

1

i2 3

1

4 5 6 7

1098 161410

9874

32

1i

Algorithmus

Heapsort(A)Build-Heap(A)for i= length(A) downto 2

do vertausche A[1] mit A[i]heapsize(A)= heapsize(A)-1Heapify(A,1)

Analyse

Build-Heap: T (n) = O(n)for-Schleife: (n− 1) mal Heapify mit T (n) = O(log n) und Vertauschen mit O(1)

T (n) ≤ c1 · n+ (n− 1) · [c2 · log n+ c3]

= c2 · n log n+ (c1 + c3) · n− c2 log n− c3︸ ︷︷ ︸vernachlassigbar fur n→∞

= O(n log n)

44

3.3.3 Priority-Queues als Anwendung der Heap-Struktur

Bei der Verwaltung von Warteschlangen mit Auftragen unterschiedlicher Prioritat muß alsjeweils nachster Auftrag immer ein Auftrag mit hochster Prioritat ausgewahlt werden. Dieskann zum Beispiel erreicht werden, indem man die Auftrage in einer sortierten Liste speichert.Allerdings ist dann die Komplexitat zum Speichern der Auftrage in der Liste linear in der Langen.Verwendet man dagegen einen Heap zur Verwaltung der Warteschlangen von Auftragen, so istdie Komplexitat zum speichern und holen von Auftragen im Heap logarithmisch in n.

Einfugen eines Elements x im Heap

1.) neues Blatt erzeugen2.) Pfad vom Blatt zur Wurzel durchsuchen und x an der richtigen Stelle einfugen.

Algorithmus

Heap-Insert(A, key)heapsize(A) = heapsize(A)+1i=heapsize(A)while i>1 AND A[parent(i)] < key

do A[i] = A[parent(i)]i=parent(i)

A[i]=key

Beispiel 3.11 Anwendung von Heap-Insert zum Einfugen des Elements X = 15

28 4

9

%% ee

84

110

75

bbb

142

96 3

7

%% ee

103

"""PPPPP

161

28 4

9

%% ee

84

110 X

11

@@

75

bbb

142

96 3

7

%% ee

103

"""

XXXXXXX

161

28 4

9

%% ee

84

110 7

11

@@

145

bbb

X2

96 3

7

%% ee

103

"""

XXXXXXX

161

28 4

9

%% ee

84

110 7

11

@@

145

bbb

152

96 3

7

%% ee

103

"""

XXXXXXX

161

Analyse

T (n) = O(log n).

45

3.4 Sortieren in linearer Zeit

Unter ganz bestimmten Bedingungen ist Sortieren sogar in linearer Zeit moglich, wie man anfolgendem Beispiel erkennt.

Idee

Wenn alle in der Liste A vorkommenden Sortierschlussel aus einer bekannten endlichen Mengesind, kann man durch einfaches Abzahlen der Haufigkeiten aller in A vorkommenden Elementeeine Tabelle S der Haufigkeiten erstellen. Danach wird die Liste A uberschrieben mit denElementen in der richtigen Reihenfolge (siehe Beispiel).

Beispiel 3.12 Zu sortieren sei A = (2, 1, 4, 5, 4, 7, 3, 1, 4, 4, 1). Als Haufigkeitstabelle S erhaltman

Sortierschlussel 1 2 3 4 5 6 7Haufigkeit 3 1 1 4 1 0 1

Daraus erhalt man einfach die sortierte Liste A = (1, 1, 1, 2, 3, 4, 4, 4, 4, 5, 7).

Komplexitat

Mit m = |S| entsteht beim Abzahlen ein linearer Aufwand und beim Zuruckschreiben auch undman erhalt

T (n) = c1 · n+ c2 ·m+ c3 · n= Θ(n+m)

Dieser Algorithmus ist besonders interessant, wenn die Zahl m der verwendeten Sortierschlusselklein ist, zum Beispiel beim Sortieren einer großen Adressdatei nach Postleitzahlen.Das hier verwendete Verfahren setzt voraus, dass die Menge der verwendeten Schlussel bekanntist. Daher ist der aufwandige Vergleichen der Sortierschlussel nicht notig. Ist diese Vorausset-zung jedoch nicht erfullt und auch sonst kein Zusatzwissen uber die zu sortierenden Datenvorhanden, so ist Sortieren in linearer Zeit nicht moglich und man kann fur die Komplexitatfolgende untere Schranke angeben:

Satz 3.5 Wenn ein Sortieralgorithmus fur beliebige Listen nur mit Vergleichen und Kopierenarbeitet und keine Zusatzinformation uber die Liste erhalt, dann gilt:

T (n) = Ω(n log n)

3.5 Hashing

Egal, welchen Suchbegriff man eingibt, moderne Suchmaschinen finden sehr schnell eine Ant-wort. Dies wird ermoglicht durch eine geeignete Datenstruktur, einen sogenannten Index. EineMoglichkeit, solch einen Index zu realisieren ist die Speicherung der Daten in einer Baum-struktur, wie wir sie bei der Verwaltung von priorisierten Warteschlangen in Form des Heapkennengelernt haben.Wir werden hier mit dem sogenannten Hashing ein Verfahren vorstellen, das im Mittel einenZugriff in konstanter Zeit erlaubt. Das heißt, die Zugriffszeit hangt nicht von der Datenmengeab.Welche bekannte Datenstruktur erlaubt konstante Zugriffszeit?

46

3.5.1 Direkte Adressierung

Versuchen wir, fur eine Suchmaschine einen Index unter Verwendung eines Array zu erzeugen.Zuerst mussen die eingegebenen Strings auf numerische Schlussel (naturliche Zahlen) abgebildetwerden. Bei einem erlaubten Alphabet mit 80 Zeichen (deutsche Klein-, Großbuchstaben, Ziffernund 10 Sonderzeichen) werden diese nummeriert von 0 bis 79 und dann wird die Zeichenkettez0, . . . zl kodiert als Schlussel

k = nl · 80l + nl−1 · 80l−1 + . . .+ n1 · 80 + n0 · 1,

wobei ni die Nummer des i-ten Eingabezeichens ist. Wenn die Kleinbuchstaben die Nummern0 bis 30 (inkl. Umlaute und ß) erhalten, wurde zum Beispiel die Eingabe ,,hallo” kodiert als

o l l a h

14 · 804 + 11 · 803 + 11 · 802 + 0 · 801 + 7 · 800 =573440000 + 5632000 + 70400 + 0 + 7 = 579142407

Mit einer derartigen Nummer kann dann direkt ein Arrayelement angesprochen werden in derTabelle T in Abbildung 3.1.

1

65

9

8

USchlüsseluniversum

02

3

7

verw.

Schlüssel

K

4

1

0

4

3

2

6

7

8

9

1

6

7

55

Schlüssel DatenTabelle T

Abbildung 3.1: Direkte Adressierung uber Array T .

Wir beschranken die Strings als Eingabe fur die Suchmaschine auf eine Lange von 20 Zeichen.Wieviele unterschiedliche Eingaben sind hier moglich?

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

Offenbar wird hierbei zu viel Speicherplatz benotigt.

3.5.2 Hash-Tabellen

Bei der direkten Adressierung muss die Tabelle Θ(|U |) Elemente haben, also gleich groß seinwie das Schlussel-Universum. Bei Verwendung einer sogenannten Hash-Tabelle kann viel Spei-cherplatz gespart werden. Die Große der Tabelle reduziert sich Θ(|K|) Elemente, wobei K dieMenge der tatsachlich verwendeten Schlussel ist.Idee: Hash-Funktion bildet Schlussel ab auf Indizes der Tabelle

47

h(k1)

h(k3) = h(k2)

h(k4)

verw.Schlussel

K

Schlusseluniversum U

k1

k4k3

k2

Hash-Tabelle

Abbildung 3.2: Adressierung uber Hash-Tabelle.

Definition 3.6 Eine Hashfunktion h bildet die Schlussel des Universums ab auf eine (vielkleinere) Menge 0, 1, . . . ,m − 1 von Hash-Werten. Man nennt h(k) den Hash-Wert desSchlussels k.

Nachteil: Kollisionen sind nicht vermeidbar, s.o.: h(k3) = h(k2). Warum?

3.5.3 Hash-Funktionen

Eigenschaften von guten Hash-Funktionen:

• Deterministisch. Warum?

• Ahnliche Schlussel werden nicht auf ahnliche Hash-Werte abgebildet

• Moglichst wenige Kollisionen

• Aber: Kollisionen sind moglich!

Modulo m:

h(k) = k mod m

Beispiel: k = 67, m = 16: h(67) = 67 mod 16 = 3

Problem, wenn m = 2p: Dann berechnet h(k) die p niederwertigsten Bits von k.

Gute Wahl von m: Primzahlen nicht zu nahe bei einer Zweierpotenz

Die Multiplikationsmethode:

Zuerst wird k multipliziert mit einer Konstanten 0 < A < 1. Dann werden die Nachkommastel-len des Ergebnisses mit m multipliziert. Von diesem Ergebnis wird dann der ganzzahlige Anteilgenommen:

h(k) = bm(kA mod 1)cLaut [9] empfiehlt D. Knuth A = (

√5− 1)/2 ≈ 0.61803.

Beispiel: k = 674301, A = 0.61803, m = 1000:

h(k) = b1000 · (674301 · (√

5− 1)/2 mod 1)c = b1000 · (416740.93664804 mod 1)c= b1000 · 0.93664804c = b936.64804c = 936

48

3.5.4 Kollisionsauflosung durch Verkettung

verw.Schlussel

K

Schlusseluniversum U

k1

k4 k5

k3 k2

k1

k3

k2

k4

k5

Hash-Tabelle

Abbildung 3.3: Adressierung uber Hash-Tabelle.

Analyse

Definition 3.7 Sei T eine Hash-Tabelle mit m Feldern, in der n Elemente gespeichert sind,so wird α = n/m als Auslastung der Tabelle bezeichnet.

Wir nehmen im Folgenden an, dass die verwendete Hash-Funktion jeden vorkommenden Schlusselmit gleicher Wahrscheinlichkeit auf eines der Felder der Tabelle abbildet. Diese Annahme wirdals einfaches uniformes Hashing bezeichnet.

Satz 3.6 Werden in einer Hash-Tabelle die Kollisionen durch Verkettung aufgelost, so kosteteine Suche im Mittel Θ(1+α) Rechenzeit unter den Annahme des einfachen uniformen Hashing.

Wenn die Zahl der Felder der Hash-Tabelle proportional zur Zahl der zu speichernden Elementewachst, gilt n = O(m) und

α = n/m = O(m)/m = O(1).

Also folgt fur die Zeit zum Suchen im Mittel Θ(1).

3.5.5 Offene Adressierung

Bei dieser alternativen Methode der Kollisionsauflosung werden alle Elemente direkt in derHash-Tabelle selbst gespeichert. Im Fall von Kollisionen wird ein neuer alternativer Index be-rechnet, und dies wird so lange wiederholt, bis eine freie Speicherzelle gefunden wird.Diese Methode hat den Vorteil, dass keine Zeiger benotigt werden, was etwas Speicherplatzspart. Allerdings kann es hier passieren, dass die Hash-Tabelle voll wird. α kann hier also nichtgroßer als eins werden.Als Literatur empfehle ich fur dieses Kapitel [9].

49

Kapitel 4

Algorithmen auf Graphen

4.1 Einfuhrung

Graphen werden immer dann verwendet, wenn man eine Menge von Objekten und Relationenzwischen diesen Objekten darstellen und/oder untersuchen will. Verkehrsnetze werden z.B. oftals Graph modelliert:

50

Ros

PaLi

Inn

Rv

ZBe

Ba

Ka

Ma

F

S

N

Bay

Reg

Ul

M

Sal

Definition 4.1 Ein gerichteter Graph ist ein Paar G = (V,E), bestehend aus einer end-lichen Knotenmenge V (engl. vertex) und einer zweistelligen Relation E ⊆ V × V . DieElemente von E werden Kanten (engl. edge) genannt.G′ = (V ′, E ′) ist ein Teilgraph von G = (V,E), wenn V ′ ⊆ V und E ′ ⊆ E.

Beispiel 4.1 folgendes sind Graphen:

• V1 = Menge aller Stadte in SuddeutschlandE1 = (x, y) ∈ V1 × V1|es gibt eine direkte Straßenverbindung von x nach y

• V2 = Menge der Einwohner von RavensburgE2 = (x, y) ∈ V2 × V2|x kennt y

• V3 = Menge der Einwohner von RavensburgE3 = (x, y) ∈ V3 × V3|x ist verheiratet mit yG3 = (V3, E3) ist Teilgraph von G2 = (V2, E2)

Zur graphischen Darstellung von Graphen werden Knoten durch Punkte und jede Kante (x, y)durch einen Pfeil von x nach y dargestellt.

Beispiel 4.2

V = a, b, c, d, e, f, g, h E = (a, d), (d, a), (a, b),

(b, c), (c, a), (b, e),(a, e), (f, g), (f, f)

ab

c

ed

g

h

f

Definition 4.2 Falls fur jede Kante e = (x, y) ∈ E eines Graphen G = (V,E) auch dieKante e′ = (y, x) ∈ E ist, so heißt G ungerichteter Graph. Alle anderen Graphen sindgerichtet. Beim Zeichnen von ungerichteten Graphen wird fur jedes verbundene Knotenpaarnur eine Linie ohne Pfeile gezeichnet.

51

Beispiel 4.3 G = (V,E) mit V = Menge der Einwohner von Ravensburg,E = (x, y) ∈ V × V | x ist verheiratet mit y

Definition 4.3

• Sei G = (V,E) ein Graph. Ein Pfad (oder Weg) von Knoten x ∈ V nach y ∈ V ist eineFolge (x = a0, . . . , a`) von Knoten mit (ai, ai+1) ∈ E. ` ist die Lange des Weges von xnach y.

• In einem einfachen Pfad kommt jeder Knoten hochstens einmal vor.

• Ein Pfad der Lange ` ≥ 1 von x nach x heißt Kreis.

• Ein Kreis, in dem außer dem Startknoten kein Knoten mehr als einmal vorkommt, heißtZyklus.

• Ein gerichteter Graph G = (V,E) heißt zyklenfrei oder gerichteter azykli-scherGraph (engl. directed acyclic graph (DAG)), wenn er keine Zyklen enthalt.

• (x, x) und (x, y, x) heißen triviale Zyklen. Ein ungerichteter Graph ist zyklenfrei, wennes zwischen jedem Paar von Knoten (x, y) hochstens einen Pfad (ohne triviale Zyklen)gibt.

• Die Zahl der Kanten, die von einem Knoten v ausgehen oder in ihm enden heißt Graddes Knotens. Er wird mit deg(v) bezeichnet. Bei ungerichteten Graphen wird jede Kantenur einfach gezahlt.

Beispiel 4.4 Fur den Graphen aus Beispiel 4.2 gilt:

• (b, c, a, d, a) ist ein Pfad von b nach a.

• (c, a, b, e) ist ein einfacher Pfad von c nach e.

• (f, f, f, g) ist ein Pfad.

• Er enthalt u.a. den Kreis (a, b, c, a, d, a).

• (a, b, c, a) und (a, d, a) und (f, f) sind (bis auf Permu-tation) die einzigen Zyklen.

• (a, b, c, e, (a, b), (b, c), (b, e), (a, e)) ist ein azykli-scher Teilgraph von G.

• deg(a) = 5, deg(b) = deg(f) = 3, deg(h) = 0.

ab

c

ed

g

h

f

Definition 4.4

• Ein ungerichteter GraphG heißt zusammenhangend, wenn es zwischen je zwei beliebigenKnoten einen Weg gibt.

• Ein zusammenhangender zyklenfreier Graph ist ein Baum.

• Eine Menge paarweise nicht zusammenhangender Baume heißt Wald.

• Ein Kreis heißt Eulerkreis, wenn er jede Kante des Graphen genau einmal durchlauft.

4.2 Eulerkreise

Beispiel 4.5 Die Stadt Konigsberg (heute Kaliningrad, Rußland) hatte folgenden Verlauf desFlusses Pregel mit sieben Brucken. Leonhard Euler fragte sich 1736, ob es einen Rundweg durch

52

die Stadt gibt, auf dem jede Brucke genau einmal uberquert wird. Der zugehorige Graph istrechts angegeben.

A

B

C

D

Bemerkung: Fur Graphen mit Mehrfachkanten ist E statt einer Relation eine Multimengeuber V × V .

Satz 4.1 Ein ungerichteter zusammenhangender Graph enthalt genau dann einen Eulerkreiswenn der Grad jedes Knotens gerade ist.

Beweis: (Beweisskizze) “⇒”: Wird ein Knoten besucht, so uber eine ankommende und eineabgehende Kante. Bei jedem Besuch eines Knoten auf dem Eulerkreis werden also zwei Kanten“verbraucht”.“⇐”: Sei G ein Graph in dem alle n Knoten geraden Grad haben. Weil der Graph zusam-menhangend ist, muss der Grad aller Knoten mindestens 2 sein. Dann besitzt der Graph alsomindestens n Kanten und damit einen Zyklus.Nun konstruieren wir einen Eulerkreis mit folgendem Algorithmus: Wir starten bei einem Kno-ten und traversieren den Graphen so lange bis ein Knoten vorkommt, der schon besucht wurde.Nun ist ein Kreis C gefunden. Alle Kanten von C werden nun geloscht. Im verbleibenden Gra-phen wird dieses Verfahren fortgesetzt, bis alle Kanten besucht sind. Nun ist der Graph indisjunkte Zyklen zerlegt. Diese lassen sich leicht zu einem Eulerkreis verbinden. Wir startenauf einem beliebigen Zyklus und verfolgen diesen Zyklus, bis wir entweder wieder am Anfangankommen oder einen Knoten V finden, der auch in einem anderen Zyklus vorkommt. Wir ver-folgen dann den zweiten Zyklus, bis wir wieder bei V angekommen sind oder bis wir wieder aufeinen Knoten W treffen, der zu einem weiteren Zyklus gehort. Dann folgen wir wieder diesemZyklus. Ein weiterer Zyklus darf nur dann betreten werde, wenn er vorher noch nicht betretenwar oder er uber den Knoten wieder betreten wird, von dem man den Zyklus verlassen hat.Dieses Verfahren wird solange fortgesetzt, bis alle Zyklen zu einem Eulerkreis verbunden sind(siehe Abbildung). 2

53

Der im Beweis skizzierte Algorithmus arbeitet in linearer Zeit. Das heißt, bei einem Graphenmit geradem Grad und m Knoten gilt fur die Rechenzeit T (m) = Θ(m).

4.3 Datenstrukturen fur Graphen

4.3.1 Adjazenzmatrix

Rv Ul M S Ka Z Ba Be F Ma N

Rv x x x x xUl x x x xM x x xS x x x x x x

Ka x x xZ x x x

Ba x x x xBe x xF x x x

Ma x x x xN x x x x x

Rv

ZBe

Ba

Ka

Ma

F

S

N

Ul

M

Die Matrix ist symmetrisch. Warum?

4.3.2 Adjazenzlisten

hgfedcba b e d

c e

aa

f g

0

0

00

0

00

0a

b

c

ed

g

h

f

54

4.3.3 Liste von Adjazenzlisten

b e d 0a

c e 0b

c a 0

a 0d

e 0

f g 0f

g 0

h 00

ab

c

ed

g

h

f

4.3.4 Vergleich der drei Datenstrukturen

Vorteile Nachteile

Adjazenzmatrix Berechnung der Inzidenz mitO(1)

Speicherplatz und Initialisie-rung teuer, beide O(n2)

Adjazenzlisten Speicherplatz = O(n+m) Berechnung der Inzidenz mitO(m)

Liste von Adjazenzlisten Speicherplatz = O(n +m), Knoten konnen einfachgeloscht oder hinzugefugtwerden

Berechnung der Inzidenz mitO(n + m), Knotensuche mitO(n)

n = Knotenzahl, m = Kantenzahl

Inzidenz bezeichnet eine Beziehung zwischen Knoten und Kanten in einem Graphen. Ein Knotenheißt in einem Graph inzident mit einer Kante, wenn er von dieser Kante beruhrt wird, dasheißt, wenn diese ihn enthalt.

4.4 Kurzeste Wege

Definition 4.5 Ein gewichteter Graph (auch bewerteter Graph) ist ein Tripel G =(V,E,w), bestehend aus einem Graphen (V,E) zusammen mit einer Gewichtungsfunkti-on w : E → R+, die jeder Kante eine relle Zahl zuordnet. Die Lange eines Weges(x = a0, . . . , a`) ist

`−1∑i=0

w(ai, ai+1).

55

Bemerkung: Setzt man bei nicht gewichteten Graphen alle Gewichte auf 1, so erhalt man dieWeglange gemaß Def. 4.3.

Beispiel 4.6 Entfernungstabelle einiger suddeutscher Stadte

RV Ul M S Ka Z Ba Be F Ma NRv 0 86 178 195 – 91 180 – – – –Ul 0 123 107 – – – – – – 171M 0 – – – – – – – 170S 0 64 – – – 210 135 210

Ka 0 – 191 – – 67 –Z 0 85 120 – – –

Ba 0 91 – – –Be 0 – – –F 0 85 230

Ma 0 230N 0

RVM

Z

UlKa

Ma

Ba

N

Be

F

178

86195 123

170

171210

230

230

91

180

12091

85

191

210

85

67

S64

135

107

Wegen der Symmetrie kann die untere Dreiecksmatrix weggelassen werden.

Definition 4.6 Ein Baum T = (V,E ′), der alle Knoten V eines Graphen G = (V,E) enthalt,heißt minimal aufspannender Baum, wenn die Summe aller Kantengewichte minimal ist,d.h. wenn

E ′ = argminX⊂E∑e∈X

w(e).

Bemerkung: argmin ist der x Wert einer Funktion f(x) an dem f(x) minimal ist.

4.4.1 Der Kruskal-Algorithmus

Satz 4.2 (Kruskal-Algorithmus) Fur einen ungerichteten, zusammenhangenden, bewerte-ten Graphen findet der folgende Algorithmus einen minimal aufspannenden Baum T :

1. Setze T =

2. Sortiere die Kanten nach ihrem Gewicht.

3. Wahle aus den noch nicht gewahlten Kanten die mit dem kleinsten Gewicht. Falls dieseKante in T keinen Zyklus erzeugt, erweitere T um diese Kante. Wiederhole Schritt 3 bisalle Kanten verbraucht sind.

Beispiel 4.7 Wir wenden nun den Kruskal-Algorithmus auf Beispiel 4.6 an und erhalten fol-genden minimal aufspannenden Baum:

56

RVM

Z

UlKa

Ma

Ba

N

Be

F

178

86195 123

170

171210

230

230

91

180

12091

85

191

210

85

67

S64

135

107

Satz 4.3 Die Laufzeit des Kruskal-Algorithmus ohne den Schritt des Sortierens fur einen Gra-phen mit n Knoten und m Kanten ist O(m + n log n). Mit optimierten Datenstrukturen ist(ohne Sortieren) sogar eine fast lineare Komplexitat erreichbar [9].

Definition 4.7 Gegeben sei ein bewerteter Graph G = (V,E,w).

• Beim Single Pair Shortest Path Problem (SPP) ist ein kurzester Weg von einemKnoten a zu einem Knoten b gesucht.

• Beim Single Source Shortest Path Problem (SSP) sind kurzeste Wege von einemKnoten a zu allen anderen Knoten b ∈ V gesucht.

• Beim All Pairs Shortest Path Problem (APSP) ist fur jedes Paar von Knoten (a, b)ein kurzester Weg gesucht.

4.4.2 Der Dijkstra-Algorithmus

Wir geben nun einen bekannten Algorithmus fur das SSP an:

Satz 4.4 (Dijkstra-Algorithmus) Fur einen bewerteten Graphen G = (V,E,w) und einengegebenen Knoten a findet der folgende Algorithmus einen aufspannenden Baum, der das SSP-Problem fur den Knoten a lost. Hierbei ist

δ(S) = k ∈ V \S|k ist mit einem Knoten aus S direkt verbunden.

57

Dijkstra(G,a)Setze S = a, F = while S 6= V do

suche in δ(S) den Knoten v mit demkurzesten Pfad (a, . . . , u, v) von a zu v.

S = S ∪ vF = F ∪ (u, v)

Beispiel 4.8 Dijkstra-Algorithmus mit a = Rv:

S

Knoten in S:

Knoten in (S):δ

Kanten in F:

M

Z

UlKa

Ma

Ba

N

Be

F

178

195 123170

171210

230

230

91

180

12091

85

191

210

85

67

S64

135

RV

86

= a

107

RVM

Z

UlKa

Ma

Ba

N

Be

F

178

86195 123

170

171210

230

230

91

180

12091

85

191

210

85

67

S64

135

107

Satz 4.5 Die Laufzeit des Dijkstra-Algorithmus O(m + Cn), wobei C eine Konstante ist, dievom maximalen Kantengewicht abhangt [9].

4.4.3 Anwendungen

• “Stadteverbindungen” der Bahn

58

• Routing im Internet: Router berechnet die beste Route zum nachsten Backbone-Knotenuber einen aufspannenden Baum, den er mit dem Dijkstra-Algorithmus erstellt.

Definition 4.8 Ein Hamilton-Kreis (hamiltonian circle) in einem Graphen G ist ein ge-schlossener Weg, in dem jeder Knoten aus G genau einmal vorkommt. Eine Clique in einem(ungerichteten) Graphen ist ein vollvernetzter Teilgraph.

4.5 Das Problem des Handlungsreisenden

(traveling salesman problem, TSP)

gegeben: Menge von Stadten s1, . . . , sn und eine Entfernungstabelle w mit wij = |si − sj| =Entfernung zwischen Stadt i und Stadt j.

gesucht: Eine Permutation (Vertauschung) Π von (s1, . . . , sn), so dass

n−1∑i=1

wΠ(i),Π(i+1) + wΠ(n),Π(1)

minimal ist. Es ist also eine Route gesucht, die jede Stadt genau einmal besucht und am Endewieder im Ausgangspunkt endet.

Definition 4.9 Eine bijektive Abbildung einer endlichen Menge M auf sich selbst heißtPermutation.

Beispiel 4.9 Eine Permutation der Menge 1, . . . , 6

i 1 2 3 4 5 6Π(i) 4 2 1 3 5 6

4.5.1 Ein praktisches Ergebnis

TSP-Tour durch mehr als 15112 deutsche Stadte:

59

David Applegate, Robert Bixby und William Cook von der Rice-Universitat in Houston (Texas) sowie Vasek Chvatal von derRutgers-Universitat in New Brunswick (New Jersey), 1998, siehe: www.tsp.gatech.edu

4.5.2 Der Nearest-Neighbour-Algorithmus

Idee

Starte in einem Knoten und wahle als nachsten immer den mit dem geringsten Abstand.

60

Algorithmus

NN TSP(w)For i=1 To n Do

tour[i]=itour[n+1]=1For i=2 To n-1 Do

next=argminw[i-1,j] | j ∈ tour[i...n]vertausche tour[i] mit tour[next]

Return(tour)

Komplexitat

T (n) = Θ(n2)

4.5.3 Der Greedy - Algorithmus

Idee

“Greedy” heißt auf deutsch “gierig”. Dieses Attribut trifft auf den Algorithmus sehr gut zu,denn er greift gierig immer nach der “besten” Kante ohne auf das Gesamtresultat zu schauen.

In der Beschreibung des Algorithmus behandeln wir die Tour als Graph: Der Graph ”Tour”wird jeweils um die Kante mit dem kleinsten Gewicht erweitert, wenn diese Kante eine Weg-fortsetzung ist und keinen Kreis erzeugt.

Algorithmus

• sortiere alle Kanten in der Liste K nach ihrem Gewicht.

• Sei (v, v′) die Kante aus K mit kleinstem Gewicht. Falls deg(v) < 2 und deg(v′) < 2 und(v, v′) schließt keinen Zyklus mit < n Knoten, erweitere die Tour um (v, v′) und losche (v, v′)aus K.

• Wiederhole 2. bis fur alle v ∈ V deg(v) = 2.

4.5.4 Die Union-Find-Datenstruktur

Der oben beschriebene Algorithmus muss feststellen, ob in einem Graph ein Zyklus vorliegtoder nicht, wenn man eine Kante zu diesem Graph hinzufugt. Die nachfolgend beschriebeneUnion-Find Datenstruktur bietet eine effizente Methode, dies festzustellen.Eine endliche Menge S sei in die disjunkten Klassen Xi partitioniert:

S = X0 ∪X1 ∪X2 ∪ . . . ∪Xk

mit Xi ∩Xj = Ø ∀i, j ∈ 0, 1, . . . , k, i 6= j.Zu jeder Klasse Xi wird ein Reprasentant ri ∈ Xi ausgewahlt. Die zugehorige Union-Find-Struktur unterstutzt die folgenden Operationen effizient:

Init(S): Initialisiert die Struktur und bildet fur jedes x ∈ S eine eigene Klasse mit x alsReprasentant.

61

Union(r, s): Vereinigt die beiden Klassen, die zu den beiden Reprasentanten r und s gehoren,und bestimmt r zum neuen Reprasentanten der neuen Klasse.

Find(x): Bestimmt zu x ∈ S den eindeutigen Reprasentanten, zu dessen Klasse x gehort.

Implementierung

Eine einfache Implementierung speichert die Zugehorigkeiten zwischen den Elementen aus Sund den Reprasentanten ri in einer Liste. Fur kurzere Laufzeiten werden jedoch in der PraxisMengen von Baumen verwendet. Dabei werden die Reprasentanten in den Wurzeln der Baumegespeichert, die anderen Elemente der jeweiligen Klasse in den Knoten darunter.

Union(r, s): Hangt die Wurzel des Baumes von s als neues Kind unter die Wurzel des Baumesvon r.

Find(x): Wandert vom Knoten x aus den Pfad innerhalb des Baumes nach oben bis zur Wurzelund gibt diese als Ergebnis zuruck.

4.5.5 Heuristiken

Um die Operationen Find und Union zu beschleunigen, gibt es die zwei Heuristiken Union-By-Size und Pfadkompression.

Union-By-Size

Bei der Operation Union(r, s) wird der Baum, der kleiner ist, unter den großeren Baum gehangt.Damit verhindert man, dass einzelne Teilbaume zu Listen entarten konnen wie bei der einfachenImplementierung (r wird in jedem Fall Wurzel des neuen Teilbaums). Die Tiefe eines TeilbaumsT kann damit nicht großer als log |T | werden. Mit dieser Heuristik verringert sich die Worst-Case-Laufzeit von Find von O(n) auf O(log n). Fur eine effiziente Implementierung fuhrt manbei jeder Wurzel die Anzahl der Elemente im Teilbaum mit.

Pfadkompression

Um spatere Find(x) Suchvorgange zu beschleunigen, versucht man die Wege vom besuchtenKnoten zur zugehorigen Wurzel zu verkurzen.

1. maximale Verkurzung (Wegkompression)

Nach dem Ausfuhren von Find(x) werden alle Knoten auf dem Pfad von x zur Wurzeldirekt unter die Wurzel gesetzt. Dieses Verfahren bringt im Vergleich zu den beiden fol-genden den großten Kostenvorteil fur nachfolgende Aufrufe von Find fur einen Knotenim gleichen Teilbaum. Zwar muss dabei jeder Knoten auf dem Pfad zwischen Wurzel undx zweimal betrachtet werden, fur die Laufzeit-Komplexitat ist das jedoch unerheblich.

2. Aufteilungsmethode (splitting)

Wahrend des Durchlaufes lasst man jeden Knoten auf seinen bisherigen Großvater zeigen(falls vorhanden); damit wird ein durchlaufender Pfad in zwei der halben Lange zerlegt.

3. Halbierungsmethode (halving)

Wahrend des Durchlaufes lasst man jeden zweiten Knoten auf seinen bisherigen Großvaterzeigen.

62

Diese Methoden haben beide dieselben Kosten wie die erste Kompressionsmethode (Kno-ten unter die Wurzel schreiben). Alle Kompressionsmethoden beschleunigen zukunftigeFind(x)-Operationen.

Laufzeiten

Union-Find-Datenstrukturen ermoglichen die Ausfuhrung der obigen Operationen mit den fol-genden Zeitkomplexitaten (n = |S|):Implementierung mit einer Liste L, worst-case: Find: O(n), Union: O(1)

Implementierung mit Baumen:

• ohne Heuristiken: Find: O(n), Union: O(1)

• mit Union-By-Size, worst-case: Find: O(log(n)), Union: O(1)

• mit Union-By-Size, Pfadkompression, worst-case: Find: O(log(n)), Union: O(1)

• mit Union-By-Size, Pfadkompression, Folge von f F ind- und u Union-Operationen:O (u+ (n+ f) · (log∗(n)))

4.5.6 Test auf Zyklus

Zur effizienten Durchfuhrung des Tests auf einen Zyklus baut man die Mengen Xi so auf, dasszwei Knoten u und v eines Graphen genau dann in der selben Menge liegen, wenn es einen Wegvon u nach v gibt.

Bevor man nun eine Kante k = (u, v) zu einem Graphen hinzufugt, testet man, ob u und vbereits durch den bisherigen Graphen verbunden sind (also ob Find(u) = Find(v) ist). Ist diesder Fall, so wurde man durch hinzufugen von k einen Zyklus erzeugen. Man kann k also nichthinzufugen. Ist dagegen Find(u) 6= Find(v), so kann man k hinzufugen und man vereinigt diebeiden, durch u und v identifizierten Mengen, zu einer neuen Menge Union(u, v).

Komplexitat

T (n) = Θ(n2 log n)

Beispiel 4.10 Vergleich von 2 Heuristiken mit der optimalen Losung an einem ganz einfachenBeispiel:

ba

c

d

e

f

2 3

1

4 5

6

Greedy Algorithmus

ba

c

d

e

Nearest Neighbour (Start in d)

1

24 56

f3

optimale Tourd

e

f

a

c

b

Beispiel 4.11 Vergleich von 3 Heuristiken mit der optimalen Losung:

63

4.5.7 Optimaler Algorithmus Optimal TSP

Idee

berechne fur jede Tour∑n

i=1wtour[i],tour[i+1] und wahle eine Tour mit minimalem Wert.

Komplexitat

Ohne Beschrankung der Allgemeinheit ist die erste Stadt frei wahlbar. Fur die zweite Stadtergeben sich n− 1 Moglichkeiten, fur die dritte n− 2 Moglichkeiten . . . Fur die n-te Stadt: eineMoglichkeit. Insgesamt sind dann also ·(n− 1)! Routen moglich.Fur jede Route muss dann noch deren Lange berechnet werden und am Ende die kurzesteermittelt werden, was bei naiver Implementierung einen zusatzlichen Faktor n zur Rechenzeitliefert. Durch Speicherung der aktuellen Lange einer Tour kann dieser Faktor n aber auf einenkonstanten Faktor reduziert werden.Also: T (n) = Θ · (n− 1)!grobe Abschatzung:

n! ≤ nn . . . n = nn, (n− 1)! = (n− 1)(n− 2) . . . 1 ≤ (n− 1)n−1

damit ergibt sich

T (n) = O(nn−1)

Eine bessere Abschatzung liefert die Stirling’sche Formel:

n! ≈ (n

e)n ·√

2Πn fur n→∞

⇒ T (n) = Θ((n

e)n−1 ·

√n)

Man erhalt hier also ein uberexponentielles Wachstum.

64

Resultate

1.) Fachleute sind uberzeugt, daß es keinen polynomiellen Alg. fur TSP gibt!

2.) und dass es sogar fur fast optimale Losungen keinen polynomiellen Alg. gibt.

3.) fur TSP mit Dreiecksungleichung ergibt die Minimum Spanning Tree Heuristik(siehenachsten Abschnitt) eine Tour die hochstens um den Faktor 2 langer ist als die optimaleTour; die Minimum Spanning Tree Heuristik hat T (n) = O(n2)

Dreiecksungleichung:

∀i, j, k wij ≤ wik + wkj

Diese Gleichung besagt, dass die direkte Ver-bindung zwischen zwei Stadten immer minimaleLange hat. Sie gilt zum Beispiel fur Luftlinien-verbindungen zwischen Stadten. Fur die Entfer-nungen auf Straßen gilt sie jedoch nicht immer.

dik

d

dji

k

ij

jk

4.5.8 Wachstum der Rechenzeit von Optimal TSP

Folgende Tabelle veranschaulicht das extrem schnelle Wachstum der Rechenzeit von Opti-mal TSP. Heute ist das TSP-Problem mit optimierten Algorithmen fur etwa 30 Stadte losbar.Wie man an der Tabelle erkennt, ist der Aufwand fur 40 Stadte etwa um den Faktor 1016 hoherund damit also unerreichbar.

n (n-1)! (n-1)!10 362880 3.6 · 105

20 121645100408832000 1.2 · 1017

30 8841761993739701954543616000000 8.8 · 1030

40 20397882081197443358640281739902897356800000000 2.0 · 1046

50 608281864034267560872252163321295376887552831379210240000000000 6.1 · 1062

4.5.9 Die Minimum-Spanning-Tree-Heuristik

Definition 4.10 Ein Preorder-Tree-Walk traversiert einen Baum folgendermassen: Be-ginnend mit dem Wurzelknoten werden von links nach rechts rekursiv alle Nachfolgerknotenbesucht.

Beispiel 4.12

65

Angewendet auf den minimal aufspannendenBaum mit Wurzelknoten Bern ergibt sich:

RVM

Z

UlKa

Ma

Ba

N

Be

F

178

86195 123

170

171210

230

230

91

180

12091

85

191

210

85

67

S64

135

107

Listet man nun alle besuchten Stadte in derbesuchten Reihenfolge und loscht alle Wieder-holungen so ergibt sich ein einfacher Pfad, deralle Knoten besucht.

RVM

Z

UlKa

Ma

Ba

N

Be

F

178

86195 123

170

171210

230

230

91

180

12091

85

191

210

85

67

S64

135

107

Im Fall eines voll vernetzten Graphen laßt sich dieser Pfad durch eine Verbindung von Frankfurtnach Bern zu einem Hamilton-Kreis schließen und man erhalt eine Naherungslosung fur dasTSP-Problem. Dieses heuristische Vorgehen nennt man die Minumum-Spanning-Tree-Heuristik.Ist der Graph nicht vollstandig vernetzt, wie im Beispiel, so ist es durchaus moglich, dass eskeinen Hamilton-Kreis gibt.Der minimal aufspannende Baum liefert jedoch auch hier einen guten Ausgangspunkt fur eineNaherung zur Losung des TSP-Problems.

RVM

Z

UlKa

Ma

Ba

N

Be

F

178

86195 123

170

171210

230

230

91

180

12091

85

191

210

85

67

S64

135

107

4.6 Planare Graphen

Definition 4.11 Laßt sich ein Graph in der Ebene darstellen, ohne dass sich Kanten kreu-zen, so nennt man ihn planar. Die Menge der durch die Kanten begrenzten Flachenstuckewird mit A bezeichnet.

Beispiel 4.13 Zwei planare Darstellungen des vollstandigen Graphen mit vier Knoten:

66

Fur diesen Graphen gilt |A| = 4.

Satz 4.6 (Eulerformel) Fur jeden planaren zusammenhangenden Graphen G = (V,E) gilt

|V | − |E|+ |A| = 2.

Beweis: Falls G ein Baum ist gilt |V | = |E|+ 1 und |A| = 1 und es ergibt sich

|V | − |E|+ |A| = |E|+ 1− |E|+ 1 = 2.

Fur den Fall, dass G kein Baum ist zeigen wir die Behauptung per Induktion uber die Zahl derKanten n = |E|. Fur n = 0 besteht der Baum aus einem Knoten, d.h. es gilt |V | = 1, |E| = 0,|A| = 1 und die Formel stimmt.Wir nehmen an, die Formel gilt fur n ≥ 0. Nun fugen wir eine Kante hinzu und erzeugen denneuen Graphen G′ = (V ′, E ′) mit |V ′| = |V | und |E ′| = |E|+ 1. Die neue Kante schließt einenKreis und es gilt |A′| = |A|+ 1, woraus

|V ′| − |E ′|+ |A′| = |V | − (|E|+ 1) + |A|+ 1 = |V | − |E|+ |A| = 2

folgt. 2

67

Kapitel 5

Formale Sprachen und EndlicheAutomaten

5.1 Grundlagen

Man muss sich Sprachen vorstellen wie einen Legobaukasten. Die Buchstaben des Alphabetsentsprechen elementaren Bausteinen und die Worte, beziehungsweise Satze entsprechen gebau-ten Objekten. Solche Mengen lassen sich mehr oder weniger einfach beschreiben. Zum Beispieldie Menge der Objekte, die nur aus roten Steinen gebaut sind. Oder die Menge der Objekte beidenen auf einem Basisstein nur Steine oben draufgesetzt werden durfen, aber nicht daneben.Was ist, wenn ich das fertige Objekt auf den Kopf stelle? Muß dann die Forderung immer nocherfullt sein?Um solche Unklarheiten auszuschließen, werden wir bei den Sprachen ganz formal vorgehen. Wirwerden Spielgregeln in Form von Grammatiken zum Aufbau von Sprachen angeben. Mit diesenSpielregeln konnen dann nur noch Worte aus einer bestimmten Sprache erzeugt (abgeleitet)werden.Hier stellen sich sofort einige fur den Informatiker sehr wichtige und interessante Fragen:

• Laßt sich jede formale Sprache durch eine Grammatik beschreiben?

• Wenn ich eine Grammatik G habe, die eine Sprache L definiert, wie kann ich erkennen,ob ein Wort zu dieser Sprache gehort oder nicht?

• Etwas konkreter: Ist es moglich, fur eine konkrete Programmiersprache L in endlicherZeit zu entscheiden, ob ein vorgegebener Text ein Programm dieser Sprache darstelltoder nicht. Diese Aufgabe ist der Syntaxcheck des Compliers.

• Ist diese Entscheidung vielleicht sogar effizient moglich, das heißt, auch fur große Pro-gramme in kurzer Zeit?

• Wenn ja, wie macht man das?

• Kann man vielleicht sogar automatisch Fehler in Programmen erkennen, wie zum BeispielEndlosschleifen?

• Kann man uberprufen, ob ein Programm korrekt ist?

Die Beantwortung dieser Fragen ist Bestandteil des Gebiets der formalen Sprachen und Auto-maten. In dieser sehr knappen Einfuhrung werden wir aber nur auf ganz einfache (regulare)Sprachen und auf die endlichen Automaten, das einfachste Maschinenmodell, eingehen konnen.Eine ausfuhrlichere Darstellung findet sich z.B. in [?].

68

Definition 5.1 Ein Alphabet Σ ist eine endliche nicht leere Menge von Zeichen.

Definition 5.2 Die Menge Σ∗ aller Worte ist wie folgt rekursiv definiert.

• Σ ⊂ Σ∗ und auch das leere Wort ε ist in Σ∗ enthalten.

• Fur jedes Wort w ∈ Σ∗ und jedes Zeichen x ∈ Σ ist auch wx ∈ Σ∗. wx ist die Zeichenkette,die entsteht, wenn man das Zeichen x an das Wort w anhangt.

Jede Teilmenge von Σ∗ wird Sprache genannt.

Sprachen sind noch einfacher als Lego-Baukasten. Es gibt genau vier Moglichkeiten, zwei Alpha-betzeichen a und b miteinander zu verknupfen, namlich aa, ab, ba, oder bb. Diese Verknupfungheißt Konkatenation und ist nicht vertauschbar. Damit kann man beliebig lange endliche Wortebauen, ahnlich wie beim Lego-Baukasten.

Beispiel 5.1

Σ = 0, 1Σ∗ = 0, 1, ε, 00, 01, 10, 11, 001, 000, 011, 010, . . .

Beispiel 5.2

Σ = +,−, ·, /, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, x, y, a, bΣ∗ = . . . , ) +− · 567ax, . . .

Terme = x, y, a, b, (a), a+ b, (a− 4) · y, . . .Terme ⊂ Σ∗

Die Menge aller korrekten arithmetischen Terme ist eine kleine Teilmenge von Σ∗. Ein Affe,der zufallig auf einer entsprechenden Tastatur tippt wurde viele Versuche benotigen, um einenkorrekten Term zu erzeugen.

Definition 5.3

• Sei w ∈ Σ∗ und n ∈ N0. Dann ist wn das durch n-fache Wiederholung von w entstandeneWort. w0 ist also das leere Wort ε.

• Fur eine endliche Zeichenmenge M ist M∗ die Menge aller Zeichenketten die aus Elementenin M gebildet werden konnen. Das leere Wort gehort zu M∗ dazu. Die Menge M+ = M∗\εenthalt dagegen nur Worte mit mindestens einem Zeichen.

Beispiel 5.3 Sei Σ = a, b, c. Dann sind

∅,aa, ab, aaa,an|n ∈ N0 = ε, a, aa, aaa, aaaa, . . .,(ab)n|n ∈ N0 = ε, ab, abab, ababab, abababab, . . .,anbn|n ∈ N0 = ε, ab, aabb, aaabbb, aaaabbbb, . . .

Teilmengen von Σ∗ und somit Sprachen uber dem Alphabet Σ.

69

5.2 Grammatiken

Besonders interessant sind strukturierte Sprachen. Eine Sammlung von zufallig erzeugten Worternist fur die meisten Anwendungen nicht sehr hilfreich. “Struktur” heißt hier, dass sich die Spracheendlich beschreiben laßt. Wir werden Grammatiken verwenden um Sprachen zu beschreiben.Aus dem Sprachunterricht in der Schule ist die Grammatik der deutschen Sprache bekannt.Ein Satz der deutschen Sprache kann zum Beispiel bestehen aus < Subjekt > < Pradikat ><Objekt> und < Subjekt> wiederum kann ersetzt werden durch <Artikel>< Substantiv>.Damit ist also Die Studentin spielt Schach ein wohlgeformter Satz entsprechend der einfachenangegebenen Grammatik. Jede Programmiersprache besitzt eine Grammatik.

Beispiel 5.4 Die Menge der arithmetischen Terme wie zum Beispiel x · (x+ a · (b− 12)) laßtsich durch folgende Regelgrammatik charakterisieren:

<Term> → <Term> + <Term><Term> → <Term> − <Term><Term> → <Term> / <Term><Term> → <Term> · <Term><Term> → (<Term>)<Term> → <Var><Term> → <Konst><Var> → x|y<Konst> → a|b| <Zahl><Zahl> → <Zahl><Ziffer> | <Ziffer><Ziffer> → 0|1|2|3|4|5|6|7|8|9

Hier steht das Zeichen | fur “oder”, das heißt, eine Regel S → u|v steht fur die zwei RegelnS → u und S → v. Durch sukzessives Anwenden einer der Regeln aus P beginnend mit demStartsymbol kann man den obigen Term x · (x+ a · (b− 12)) ableiten:<Term>

⇒ <Term> · <Term> ⇒ <Var> · <Term>⇒ x· <Term> ⇒ x · (<Term>)⇒ x · (<Term> + <Term>) ⇒ x · (<Var> + <Term>)⇒ x · (x+ <Term>) ⇒ x · (x+ <Term> · <Term>)⇒ x · (x+ <Konst> · <Term>) ⇒ x · (x+ a· <Term>)⇒ x · (x+ a · (<Term>)) ⇒ x · (x+ a · (<Term> − <Term>))⇒ x · (x+ a · (<Konst> − <Term>)) ⇒ x · (x+ a · (b− <Term>))⇒ x · (x+ a · (b− <Konst>)) ⇒ x · (x+ a · (b− <Zahl>))⇒ x · (x+ a · (b− <Zahl><Ziffer>)) ⇒ x · (x+ a · (b− <Ziffer><Ziffer>))⇒ x · (x+ a · (b− 1 <Ziffer>)) ⇒ x · (x+ a · (b− 12))

Definition 5.4 Eine Grammatik ist ein 4-Tupel

G = (V,Σ, P, S)

mit

• V als endliche nichtleere Menge der Variablen.

• Σ als Menge der Konstanten oder Terminalalphabet und V ∩ Σ = ∅.• P ⊂ (V ∪ Σ)+ × (V ∪ Σ)∗ als endliche Menge der Produktionsregeln.

• S ∈ V ist die Startvariable.

70

Definition 5.5 Die in Beispiel 5.4 und im Folgenden verwendete Art der Darstellung vonGrammatikregeln wird nach ihren Erfindern Backus-Naur-Form (BNF) genannt.

Beispiel 5.5 Mit

G = ( <Term>,<Var>,<Konst>,<Zahl>,<Ziffer>,x, y, a, b, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, (, ),+,−, ·, /,P,<Term>)

und P als Menge der Regeln aus Beispiel 5.4 ergibt sich also eine Grammatik mit den angege-benen Variablen, Konstanten und <Term> als Startsymbol.

Eine aquivalente Darstellung von Regelgrammatiken in grafischer Form bieten die Syntaxdia-gramme, die wir hier nicht formal einfuhren. Ein Beispiel soll genugen:

Beispiel 5.6 Syntaxdiagramm fur Terme

Term + Term

Term Term

Term Term

Term Term

Term )

x

y

Ziffer

Term:

/

*

_

(

Var

Var:

a

b

Zahl

Konst

Konst:

Zahl: Ziffer:

0 1 2 3 4 5 6 7 8 9

Definition 5.6 Eine Folge von Wortern (w0, w1, . . . , wn) mit w0 = S und wn ∈ Σ∗ heißtAbleitung von wn, falls fur i ≥ 1 jedes der Worter wi aus wi−1 entstanden ist durchAnwendung einer Regel aus P auf ein Teilwort von wi−1. Fur einen Teilschritt schreibt manwi−1 ⇒ wi. Ist ein Wort w durch einen oder mehrere Teilschritte aus u ableitbar, so schreibtman u⇒∗ w.

Obige Grammatik erzeugt die (unendliche) Menge der Terme als Teilmenge von Σ∗. Allgemeindefiniert man

71

Definition 5.7 Die durch G erzeugte Sprache L(G) ist die Menge aller Worte aus Σ∗,die aus G ableitbar sind, d.h.

L(G) = w ∈ Σ∗ | S ⇒∗ w.

Formale Sprachen werden eingeteilt in verschiedene Klassen, die sogenannte Chomsky-Hierarchie.Wir werden uns im Folgenden mit regularen Sprachen beschaftigen.

Definition 5.8 Eine Sprache heißt regular, wenn alle Regeln die Form A → a, A → aBoder A→ ε besitzen, d.h. auf der linken Seite der Regeln steht immer eine Variable und aufder rechten Seite steht entweder ein Terminalsymbol oder ein Terminalsymbol gefolgt voneiner Variablen.

Beispiel 5.7 Die Sprache anbm|n ∈ N,m ∈ N ist regular und laßt sich durch die GrammatikG = (S, T, a, b, P, S) beschreiben mit

P = S → aS, S → aT, T → bT, T → b .

Beispiel 5.8

Σ = a, bG1 = (S,Σ, P, S)

P = S → aS, S → bS, S → ε

Offenbar laßt sich aus dieser Grammatik jedes Wort w ∈ Σ∗ ableiten, also gilt L(G1) = Σ∗.

5.3 Regulare Ausdrucke

Regulare Ausdrucke dienen wie regulare Grammatiken der Beschreibung von regularen Spra-chen (Typ-3-Sprachen nach der Chomsky-Hierarchie).

Definition 5.9 Regulare Ausdrucke zum Alphabet Σ sind:

1.) ∅ =

2.) ε

3.) a, falls a ∈ Σ

4.) sind α, β regulare Ausdrucke, so auch αβ, α|β und α∗

hierbei steht α|β fur α oder β, α∗ fur beliebig viele Wiederholungen von α (auch 0 Wieder-holungen).

Beispiel 5.9 aa∗bb∗ beschreibt anbm/n ∈ N,m ∈ N. Fur aa∗ schreibt man kurzer a+. DerOperator + steht also fur beliebig viele Wiederholungen, aber mindestens eine.

72

Beispiel 5.10 Sei Σ = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

0.(0|1|2|3|4|5|6|7|8|9)+

beschreibt die Menge aller Dezimalzahlen mit 0 vor dem Dezimalpunkt.Noch einfacher geht es, wenn man zur Beschreibung von Zeichenmengen folgende vereinfachendeNotationen einfuhrt:

[xyz] Kurzform von (x|y|z). steht fur jedes (beliebige) Zeichen\x steht fur das Zeichen x, auch wenn x ein Sonderzeichen (z.B. ,,.”) istan,m Ausdruck a mit n bis m Wiederholungen[ a] jedes Zeichen außer a[ a− k] jedes Zeichen außer a bis k

Nun lassen sich die Dezimalzahlen einfacher beschreiben mit

0\.[0123456789]+

oder noch einfacher durch0\.[0− 9]+

0− 9 steht hier fur den Zeichenbereich von 0 bis 9.

Die Syntax von Email-Adressen lasst sich durch den Ausdruck

................................................................................................................................. beschreiben.

Satz 5.1 Jede regulare Sprache ist durch einen regularen Ausdruck beschreibbar. Umgekehrtdefiniert jeder regulare Ausdruck eine regulare Sprache.

Im Gebiet der formalen Sprachen werden Sprachen, die machtiger sind als die regularen Spra-chen, behandelt. Zum Erkennen dieser Sprachen reichen aber endliche Automaten nicht mehraus. Hier werden machtigere Maschinenmodelle, wie zum Beispiel Kellerautomaten und Turing-maschinen benotigt.

5.4 Endliche Automaten zur Worterkennung

Ein einfaches Modell ist der endliche Automat. Anschaulich ist ein endlicher Automat einRechenelement, welches auf einem Eingabeband beginnend mit dem ersten Zeichen der Eingabedas eingegebene Wort Zeichen fur Zeichen liest. In jedem diskreten Rechenschritt macht derAutomat einen Zustandsubergang. Abhangig vom aktuellen Zustand und dem gelesenen Zeichengeht der Automat in einen neuen Zustand uber. Die Zahl der Zustande ist endlich. Erreicht derAutomat nach Lesen des letzten Zeichens einen Endzustand, so hat er das Wort erkannt.

H A L L O

Z Zustand

Lesekopf

73

Beispiel 5.11 Der durch folgende Regeln beschriebene Automat akzeptiert alle Zeichenketten(Worte) bestehend aus einer beliebigen Anzahl a-s gefolgt von einer beliebigen Anzahl b-s,mindestens jedoch ein a und ein b. Die Regelmenge des Automaten mit den Zustanden S, Tund dem Endzustand e ist

δ = S, a→ S; S, a→ T ; T, b→ T ; T, b→ e

Die Zustandsubergangsrelation δ laßt sich ubersichtlich durch die

Zustandsubergangstabelle

darstellen:δ S T ea S, Tb T, e

Man beachte, dass die Zustandsubergangsrelation δ nicht eindeutig ist, denn zum Beispiel kannder Automat nach Lesen eines a im Zustand S nach S oder nach T ubergehen. Dies zeichnetden nichtdeterministischen Automaten aus.

Besonders anschaulich ist der zugehorige Zustandsgraph:

S T

a

a

b

b e

Der beschriebene Automat kann nur passiv Eingaben akzeptieren oder abweisen. Er lost alsoein binares Entscheidungsproblem. Man kann solch einen Automaten einfach erweitern durcheine Ausgabefunktion.

5.5 Automaten mit Ausgabe

Beispiel 5.12 Es soll ein Getrankeautomat mit Hilfe eines endlichen Automaten programmiertwerden. Der Automat kann mit bis zu 4 Dosen Mineralwasser gefullt werden. Wenn eine 1-Euro-Munze eingegeben wird, soll er eine Dose Wasser ausgeben. Bei Eingabe einer anderen Munzesoll er die eingegebene Munze wieder ausgeben, aber kein Getrank. Wenn der Automat leer istsoll er anhalten und per Funk den Service benachrichtigen.

Ein endlicher Automaten (mit Ausgabe) fur diese Aufgabe ist gegeben durch folgende Tabellemit den Zustanden z0, z1, z2, z3, z4 und den erlaubten Eingabezeichen ?‘, f,m. Im Zustand zienthalt der Automat i Flaschen Mineralwasser. e steht fur die Eingabe/Ausgabe eines Euro,f fur Eingabe einer falschen Munze. m steht fur eine Flasche Mineralwasser. m kann sowohleingegeben werden (durch den Betreiber) als auch ausgegeben werden (an den Kunden). EinPaar x, y in der Tabelle beschreibt den Nachfolgezustand x und das Ausgabezeichen y.

z0 z1 z2 z3 z4

m z1, ε z2, ε z3, ε z4, εe z0, e z0,m z1,m z2,m z3,mf z0, f z1, f z2, f z3, f z4, f

Das Zustandsdiagramm zu diesem Automaten sieht so aus:

74

ff f f f

z0 z z zz1 2 3 4

m m m m

eeee

e

Dieser Automat akzeptiert alle Eingabesequenzen (Worte), die zum leeren Automaten (d.h. zuz0) fuhren.

5.6 Formale Beschreibung von Automaten

Genau wie bei allen Programmiersprachen wird auch fur endliche Automaten eine streng for-male Beschreibung benotigt. Diese ist aber auch noch fur theoretische Uberlegungen in derTheorie der formalen Sprachen notwendig ( ⇒ Theoretische Informatik, Master).Wir kennen nun einige regulare Sprachen. Wir stellen uns die Frage ob es eine moglichst einfacheund effiziente Rechenmaschine gibt, mit der man fur ein beliebiges Wort w entscheiden kann,ob dieses zu einer vorgegebenen regularen Sprache gehort.

Definition 5.10 Die Aufgabe, zu entscheiden, ob ein Wort w zu einer Sprache L gehort,heißt Wortproblem.

Grammatikerzeugt−→ Sprache

erkennt←− Automat

Das Wortproblem fur regulare Sprachen kann durch endliche Automaten effizient gelostwerden.Formal wird der Automat wie folgt definiert:

Definition 5.11 Ein endlicher Automat M besteht aus einem 5-, bzw. 7-Tupel

M = (Z,Σ, δ, z0, E)

bzw.M = (Z,Σ, δ, z0, E, γ,Θ)

mit

Z : endliche Zustandsmenge

Σ : endliches Eingabealphabet, Σ ∩ Z = φ

δ : Z × Σ→ P(Z), die Zustandsubergangsfunktion

z0 : Startzustand

E : Menge der Endzustande

γ : Z × Σ→ Θ, die Ausgabefunktion

Θ : Ausgabealphabet

75

Definition 5.12 Ein Wort w = w1 . . . wn mit wi ∈ Σ wird akzeptiert von dem endlichenAutomaten M genau dann wenn M gestartet im Startzustand auf w1 nach n Anwendungender Funktion δ, d.h. nach Lesen von wn, einen Endzustand z ∈ E erreichen kann.Die von M akzeptierte (erkannte) Sprache L(M) ist

L(M) = w ∈ Σ∗ |M akzeptiert w

Beispiel 5.13 Der Automat aus Beispiel 5.11 wird beschrieben durch das 5-Tupel

M = (S, T, e, a, b, δ, S, e)

mitδ = S, a→ S; S, a→ T ; T, b→ T ; T, b→ e.

Beispiel 5.14 Der Getrankeautomat aus Beispiel 5.12 wird beschrieben durch das 7-Tupel

(z0, z1, z2, z3, z4, e, f,m, δ, z0, z0, γ, e, f,m)

wobei δ und γ gegeben sind durch die angegebene Automatentabelle.

Definition 5.13 Beim nichtdeterministischen endlichen Automaten (NFA) sind (im Gegen-satz zum deterministischen endlichen Automaten (DFA)) fur jeden Zustand Z und Eingabe-zeichen a mehrere Regeln

z, a→ z1

...

z, a→ zn

erlaubt.

Beispiel 5.15 An der Sprache L = anbm|n ∈ N,m ∈ N erkennt man schon, wie die Re-gelgrammatik in einfacher Weise in einen nichtdeterministischen Automaten ubersetzt werdenkann:

Regelgrammatik AutomatP = S → aS δ = S, a → S

S → aT S, a → TT → bT T, b → TT → b T, b → e

Es gibt aber auch einen deterministischen Automaten, der diese Sprache erkennt (siehe Aufga-be 39).

Satz 5.2 NFAs und DFAs sind gleich machtig, d.h. zu jedem NFA gibt es einen DFA, der diegleiche Sprache erkennt.

76

Satz 5.3 Eine Sprache L wird von einem endlichen Automaten genau dann erkannt, wenn sieregular ist.

77

Kapitel 6

Zusatzmaterial

6.1 Logarithmen

Die folgenden Schreibweisen sind ublich:

lg Logarithmus zur Basis 10

ln Logarithmus zur Basis e (naturlicher Logarithmus)

logb Logarithmus zur Basis b

6.1.1 Beispiele

lg(100) = 2 ⇔ 102 = 100 (6.1)

lg(1000) = 3 ⇔ 103 = 1000 (6.2)

lg(10000) = 4 ⇔ 104 = 10000 (6.3)

lg(n) = lg(n) ⇔ 10lg(n) = n (6.4)

log2(8) = 3 ⇔ 23 = 8 (6.5)

log2(16) = 4 ⇔ 24 = 16 (6.6)

log2(23) = 3 ⇔ 23 = 8 (6.7)

6.1.2 Logarithmen - Regeln

Umrechnung Logarithmen verschiedener Basen:

logb(x) = y ⇔ by = x (6.8)

loga(x) = z ⇔ az = x (6.9)

logb(a) = logb(a) ⇔ blogb(a) = a (6.10)

blogb(a)∗z = x (6.11)

logb(x) = logb(a) ∗ loga(x) (6.12)

Ableitung der Logarithmusfunktion

ln(x)′ =1

x(6.13)

78

6.2 Anwendung des Mastertheorems

1. Bestimme a und b

a Anzahl der tatsachlich ausgefuhrten rekursiven Aufrufe innerhalb der Prozedur. Beigraphischer Darstellung: Anzahl der Verzweigungen des Rekursionsbaumes.

b Zahl, durch die n geteilt wird bei dem rekursiven Aufruf. Falls z.B. n halbiert wird,ergibt sich b = 2.

2. Bestimmen der Funktion nlogb(a). Beispiel b = 2, a = 4 ergibt n2, da 22 = 4.

3. Vergleich der Funktion f(n) aus der Rekurenzgleichung mit der gerade bestimmten Funk-tion nlogb(a). (f bestimmt die Komplexitat der Prozedur fur den nicht rekurrenten Fall.):

• Ist f(n) weniger stark steigend als nlogb(a), so ist Fall 1 des Mastertheorems anzu-wenden;

• ist f(n) gleich steigend wie nlogb(a), so ist Fall 2 des Mastertheorems anzuwendenund

• ist f(n) starker steigend als nlogb(a), so ist Fall 3 des Mastertheorems anzuwenden.

79

Kapitel 7

Ubungen

7.1 Geschichte der Informatik

Aufgabe 1 Recherchieren Sie in Ihrer Lerngruppe uber eine(n) beruhmten Informatiker(in)und bereiten Sie ein kurzes Referat vor. In der Ubungsstunde tragen Sie daruber vor. BeachtenSie dabei bitte folgendes:

• Versuchen Sie zu verstehen (und im Vortrag darzustellen), was die von Ihnen gewahltePerson erfunden/geleistet hat.

• Berichten Sie auch uber die Personlichkeit und das Privatleben.

• Versuchen Sie sich kurz zu halten, aber trotzdem das Wesentliche zu vermitteln.

• Arbeiten Sie mit Farbe, Anschauung, Bildern.

7.2 Sortieren

7.2.1 Sortieren durch Einfugen

Aufgabe 2

a) Programmieren Sie “Sortieren durch Einfugen” in C fur Integerzahlen - Arrays.

b) Testen Sie das Programm mit sortierten, zufalligen und umgekehrt sortierten Arrays aufKorrektheit.

c) Bestimmen Sie fur sortierte, zufallige und umgekehrt sortierte Arrays die Parameter a, bund c von T (n) = a · n2 + b · n+ c. Da in der Sprache C die Lange statischer Arrays auf250000 beschrankt ist, sollten Sie mit dynamischen Arrays arbeiten. Das geht (mit C++)z.B. so:

/* Deklaration Array */

int* a;

n = 300000000

/* Speicherplatz reservieren */

a = new int[n];

d) Bestimmen Sie die theoretische Rechenzeit fur ein Array der Lange 5 · 109.

e) Warum wird in der Praxis T (5 · 109) viel großer sein als oben errechneter Wert?

80

f) Durch welche Massnahme kann man die berechnete Rechenzeit tatsachlich erreichen?

Aufgabe 3 Ordnen Sie folgende Funktionen nach Ihrem asymptotischen Wachstum (log istder Zehnerlogarithmus, ln der naturlich Logarithmus):

(lnn)lnn n3/2 n log n (n+ 1)! n2n lnn√n n!

√log n

2n ln lnn nn n (lnn!) n2/3 (32)n log n ln 2n

Aufgabe 4 Kreuzen Sie in folgender Tabelle alle zutreffenden Felder an. Es seien k ≥ 1, ε > 0und c > 1. Es stehen die Abkurzungen O, o, Ω, ω und Θ fur f(n) = O(g(n)), etc. VergleichenSie hierzu das asymptotische Verhalten der Funktionen f und g. Zeichnen Sie ggf. die Graphender beiden Funktionen.

f(n) g(n) O o Ω ω Θ

nk cn

log n nε

2n 2n/2

nlogm mlogn

n! nn√n nsinn

Aufgabe 5 Beweisen Sie Satz 3.1, d.h. T (n) = Θ(g(n)) ⇔ T (n) = Ω(g(n)) und T (n) =O(g(n)).

7.2.2 Quicksort

Aufgabe 6 Skizzieren Sie den Rekursionsbaum von Quicksort fur ein konstantes Aufteilungs-verhaltnis von 1:k und leiten Sie aus diesem Baum T (n) = O(n lg n) ab.

Aufgabe 7 Programmieren Sie Quicksort fur einfache Arrays von Integer-Zahlen, indem Sie dieFunktion Partition wie in der Vorlesung beschrieben implementieren. Zeigen Sie empirisch,daß fur zufallig sortierte Arrays Trand(n) = Θ(n lg n) und fur vorsortierte Arrays Tmax(n) =Θ(n2) gilt.

Aufgabe 8 Beweisen Sie, daß fur Sortieralgorithmen gilt Tmin(n) = Ω(n).

Aufgabe 9

Gegeben sei folgender Programmteil eines C-Programms:

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)

for(k = 1; k <= j; k++)

z = z+1;

a) Berechnen Sie die Laufzeit T (n) und geben Sie die (asymptotische) Zeitkomplexitat an.

b) Welchen Wert hat z nach Verlassen der außersten Schleife fur n = 100?

81

Aufgabe 10 Gegeben sei die rekursive Funktion fib:

fib(0) = 1

fib(1) = 1

fib(n) = fib(n− 1) + fib(n− 2) fur n ≥ 2.

a) Berechnen Sie fib(5).

b) Zeichnen Sie den Rekursionsbaum fur fib.

c) Bestimmen Sie anhand des Rekursionsbaumes die Komplexitat von fib.

7.2.3 Heapsort

Aufgabe 11 Zeigen Sie, daß gilt

∞∑k=0

kqk =q

(1− q)2.

Tip: Entweder Sie schreiben die Reihe gliedweise in geeigneter Form und wenden dann dieFormel fur die geometrische Reihe an, oder Sie starten indem Sie die Formel fur die geometrischeReihe differenzieren.

Aufgabe 12 Warum wird der Schleifenindex i in Zeile 2 von Build-Heap von blength[A]/2cbis 1 erniedrigt und nicht von 1 bis blength[A]/2c erhoht?

Aufgabe 13 Stellen Sie den Ablauf von Build-Heap fur A = (5, 3, 17, 10, 84, 19, 6, 22, 9)grafisch dar, ahnlich wie in Beispiel 3.9.

Aufgabe 14 Stellen Sie den Ablauf von Heapsort fur A = (5, 13, 2, 25, 7, 17, 20, 8, 4) grafischdar, ahnlich wie in Beispiel 3.10.

Aufgabe 15 Benutzen Sie die Master-Methode zur Berechnung der Laufzeit der Suche durchBisektion mit der Rekurrenzgleichung T (n) = T (n/2) + Θ(1).

Aufgabe 16 Geben Sie mit Hilfe des Master-Theorems asymptotische Schranken fur folgendeRekurrenzen an:

a) T (n) = 4T (n/2) + n

b) T (n) = 4T (n/2) + n2

c) T (n) = 4T (n/2) + n3.

7.2.4 Hashing

Aufgabe 17 Vergleichen Sie fur eine Hash-Tabelle mit 13 Eintragen die modulare Hash-Funktion und die Multiplikationsmethode. Uberprufen Sie an einer großeren Zahl von Schlusseln(mindestens 50), ob die Bedingung des einfachen uniformen Hashing erfullt ist.

Aufgabe 18 Fur den Fall von Kollisionen in einer Hash-Tabelle sollen die Rechenzeiten fur dieKollisionsauflosung ermittelt werden.

82

a) Uberlegen Sie sich, wie die Operationen Einfugen, Suche (erfolgreich und nicht erfolgreich)und Loschen eines Elements moglichst effizient realisiert werden und bestimmen Sie derenKomplexitat.

b) Was wurde sich andern, wenn wir mit sortierten Listen arbeiten wurden?

7.3 Graphen

Aufgabe 19 Zeigen Sie, dass jeder zyklenfreie ungerichtete Graph ein Wald ist.

Aufgabe 20 Zeigen Sie, dass in jedem Graphen G = (V,E) mit m Kanten

∑v∈V

deg(v) = 2m

gilt.

Aufgabe 21 Konstruieren Sie fur den Graphen aus dem Beweis von Satz 4.1 einen Eulerkreis,indem Sie mit anderen Zyklen beginnen.

Aufgabe 22 Geben Sie fur den bewerteten Suddeutschlandgraphen die Adjazenzlisten und dieListe von Adjazenzlisten an.

Aufgabe 23 Geben Sie fur den Graphen aus Beispiel 4.2 Adjazenzmatrix an.

Aufgabe 24 Erzeugen Sie einen minimal aufspannenden Baum mit dem Algorithmus vonKruskal fur den SFBay-Graphen:

Aufgabe 25 Verwenden Sie den Algorithmus von Dijkstra fur das Single-Source-Shortest-Path-Problem beim SFBay-Graphen mit Start in Palo Alto.

Aufgabe 26 Gegeben ist folgende Entfernungstabelle deutscher Stadte:

83

AachenBasel 545

Berlin 650 875Bremen 370 775 400

Dortmund 155 555 495 235Dresden 645 745 200 490 515

Dusseldorf 90 550 560 285 70 580Aachen Basel Berlin Bremen Dortmund Dresden

Aa

Do

Br

Be

Dre

Ba

Dü

a) Bestimmen Sie mit dem Nearest-Neighbour-Algorithmus eine (heuristische) Losung furdas TSP-Problem. Starten Sie in Dusseldorf. Geben Sie die Tour sowie deren Lange an.

b) Bestimmen Sie einen Minimum Spanning Tree mit dem Kruskal-Algorithmus. ZeichnenSie diesen in die Landkarte (unten) ein.

c) Verwenden Sie die Minimum-Spanning-Tree-Heuristik mit Wurzelknoten Bremen zur Be-stimmung einer Losung des TSP-Problems. Zeichnen Sie die Losung in die Karte ein undgeben Sie Tour sowie Lange an.

Aufgabe 27 Versuchen Sie, die Minimum-Spanning-Tree-Heuristik zur Losung des TSP-Problemsbeim SFBay-Graphen anzuwenden. Vergleichen Sie das Ergebnis mit dem des Greedy-Algorithmusbei Start in San Franzisko oder anderen Stadten. Warum treten hier Probleme auf?

Aufgabe 28 Bestimmen Sie eine optimale Tour fur das TSP-Problem beim SFBay-Graphen.

Aufgabe 29 Fur einen planaren (ebenen) ungerichteten Graphen sei A die Menge der durchdie Kanten des Graphen begrenzten Flachenstucke. Uberprufen Sie an allen bisher verwendetenGraphen (V,E) die Gultigkeit der Euler-Formel

|V | − |E|+ |A| = 2.

Aufgabe 30 Es soll ein Programm entworfen werden, das bei gegebener Abstandsmatrix furvollstandig vernetzte Graphen eine optimale Tour findet.

a) Schreiben Sie ein Programm fur Optimal TSP mit 4 Stadten

b) Schreiben Sie ein Programm fur Optimal TSP mit n Stadten

7.4 Formale Sprachen und Endliche Automaten

Aufgabe 31

a) Geben sie eine Grammatik an, die alle Zeichenketten der Formab, abab, ababab, . . . erzeugt.

b) Geben sie einen regularen Ausdruck an, der alle Zeichenketten der Formab, abab, ababab, . . . erzeugt.

84

Aufgabe 32 Geben Sie eine Grammatik an fur die Sprache L = aibjck | i ∈ N, j ∈ N, k ∈ N

Aufgabe 33 Geben Sie regulare Ausdrucke an fur

a) groß geschriebene Worte wie z.B. Hallo, aber nicht HALLO.

b) groß geschriebene Worte mit mindestens 3 und hochstens 5 Buchstaben.

c) Datumsangaben der Form 21.10.1999 oder 1.1.2000 oder 1.1.‘00 oder 21.10.‘99.Nicht erlaubt sind unzulassige Werte wie z.B. 33.44.‘99 oder 121.10.1999

Aufgabe 34 Geben Sie fur jede der in Aufgabe 33 angegebenen Sprachen einen endlichenAutomaten an, der diese erkennt.

Aufgabe 35

Beschreiben Sie die durch folgende regularen Ausdrucke definierten Sprachen und geben SieBeispiele an.

a) \\(index|color|label|ref)\[^\]*\

b) %.*

c) \\section\*?\.*\

d) [A-Za-z0-9]+@[A-Za-z0-9]+(\.[A-Za-z0-9]+)1,6

Aufgabe 36

konstruieren sie (deterministische oder nichtdeterministische) endliche Automaten fur folgendedurch regulare Ausdrucke gegebenen Sprachen:

a) [0-9]*\.[0-9]+

b) \\section\*?\.*\

Aufgabe 37 Es soll eine Fußgangerampel mit Hilfe eines endlichen Automaten programmiertwerden. Die Ampel hat die zwei Zustande rot und grun (aus der Sicht des Fahrzeugs). ImZustand rot akzeptiert die Ampel Signale von der Kontaktschleife auf der Straße und schaltetdann auf Grun. Im Zustand Grun akzeptiert die Ampel Signale vom Fußgangertaster undschaltet auf Rot. Alle anderen Eingaben ignoriert der Automat.

a) Geben Sie einen endlichen Automaten fur diese Aufgabe an.

b) Zeichnen Sie ein Zustandsdiagramm zu diesem Automaten.

Aufgabe 38 Es soll ein Getrankeautomat mit Hilfe eines endlichen Automaten programmiertwerden. Der Automat kann mit bis zu 4 Dosen Mineralwasser, 4 Dosen Limo und 4 DosenBier gefullt werden. Wenn eine 1-Euro-Munze eingegeben wird, soll er eine Dose des gewahltenGetranks ausgeben. Bei Eingabe einer anderen Munze soll er die eingegebene Munze wiederausgeben, aber kein Getrank. Wenn von einer Getrankesorte alle Dosen ausgegeben sind, soller anhalten und per Funk den Service benachrichtigen.

a) Geben Sie einen endlichen Automaten (mit Ausgabe) fur diese Aufgabe an.

b) Zeichnen Sie ein Zustandsdiagramm zu diesem Automaten.

85

c) Geben Sie einen regularen Ausdruck fur diese Sprache an.

d) Geben Sie eine regulare Grammatik an, welche die fur diesen Automaten erlaubte Ein-gabesprache akzeptiert.

Aufgabe 39 Konstruieren Sie einen deterministischen endliche Automaten, der zu dem ausBeispiel 5.15 aquivalent ist.

86

Literaturverzeichnis

[1] Wikipedia – Die freie Enzyklopadie. www.wikipedia.org. 2.7

[2] F. Naumann. Vom Abakus zum Internet. Wissenschaftliche Buchgesellschaft, 2001. Ge-schichte der Informatik. 2.1

[3] H. Matis. Die Wundermaschine. mitp-Verlag, 2002. Geschichte des Computers. 2.1

[4] W. de Beauclair. Rechnen mit Maschinen – eine Bildgeschichte der Rechentechnik. ViewegVerlag, 1968. Die Lekture dieses Bilderbuches lohnt sich! 2.1

[5] D. Shasha and C. Lazere. Out of Their Minds: The Lives and Discoveries of 15 GreatComputer Scientists. Copernicus/ An Imprint of Springer-Verlag, 1995. Sehr unterhaltsamund informativ.

[6] V. Claus and A. Schwill. Duden Informatik. Bibliographisches Institut & F.A. BrockhausAG, 1988. Ein gutes Nachschlagewerk zur Informatik allgemein.

[7] P. Rechenberg and G. Pomberger. Informatik-Handbuch. Hanser Verlag, 2001.

[8] C. Horn and O. Kerner. Lehr- und Ubungsbuch Informatik, Band 1: Grundlagen undUberblick. Fachbuchverlag Leipzig, 2001.

[9] T.H. Cormen, Ch.E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press,Cambridge, Mass, 1994. Sehr gute Einfuhrung in die Analyse von Algorithmen. 3.5.3,3.5.5, 4.3, 4.5

[10] N. Wirth. Algorithmen und Datenstrukturen. Teubner-Verlag, Stuttgart, 1983 (3. Auflage).Ein Klassiker, vom Erfinder der Sprache PASCAL.

[11] R. Sedgewick. Algorithmen. Addison-Wesley, Bonn, 1995. Ubersetzung d. engl. Originals,empfehlenswert.

[12] P. Tittmann. Graphentheorie. Fachbuchverlag Leipzig, 2003. Sehr gutes Buch mit vielenBeispielen. Leider fehlen die Wegesuchalgorithmen.

[13] S. Krumke and H. Noltemeier. Graphentheoretische Konzepte und Algorithmen. TeubnerVerlag, 2005. Exakt und gleichzeitig anschaulich.

[14] Paul E. Black (Ed.). Dictionary of Algorithms and Data Structures [online]. NationalInstitute of Standards and Technology, 2004. http://www.nist.gov/dads.

[15] S. Skiena. The Algorithm Design Manual. Springer Verlag, 1997. Gutes Buch mit vielenAlgorithmen fur den Praktiker.

87