Embed Size (px)
Citation preview
Grundlagen der Informatik
Wolfgang Ertel
24. Juli 2008
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.9 Datenschutz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.10 Datenbanken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7 Große Informatiker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.8 Frauen in der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.9 Wichtige Institute und Firmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Algorithmen und Datenstrukturen – Einfuhrung 27
3.1 Sortieren durch Einfugen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Sortieren mit Baumen (Heapsort) . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Sortieren in linearer Zeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4 Algorithmen auf Graphen 48
4.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2 Eulerkreise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3 Datenstrukturen fur Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4 Kurzeste Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.5 Das Problem des Handlungsreisenden . . . . . . . . . . . . . . . . . . . . . . . . 56
4.6 Planare Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2
5 Formale Sprachen und Endliche Automaten 635.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635.2 Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655.3 Regulare Ausdrucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.4 Endliche Automaten zur Worterkennung . . . . . . . . . . . . . . . . . . . . . . 685.5 Automaten mit Ausgabe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695.6 Formale Beschreibung von Automaten . . . . . . . . . . . . . . . . . . . . . . . 70
6 Ubungen 736.1 Geschichte der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736.2 Sortieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736.3 Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 766.4 Formale Sprachen und Endliche Automaten . . . . . . . . . . . . . . . . . . . . 77
Literaturverzeichnis 80
3
Kapitel 1
Was ist Informatik?
1.1 Informatik
Definition 1.1 Informatik ist die Wissenschaft der automatischen Verarbeitung von In-formationen mit Hilfe von Computern.
(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 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?
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
• Rechnerarchitektur• Betriebssysteme (DOS, Windows, Unix, . . . )
5
• 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 Entwicklungswe-krzeugen.
1.6 Betriebssysteme
1.6.1 Betriebssysteme: Aufgaben
• Laden u. Starten von Programmen
• Verwalten des Hauptspeichers
Schutzen der Speicherbereiche von Programmen Verwaltung des virtuellen Speichers (paging, swapping)
Paging: Auslagern von ProgrammteilenSwapping: Auslagern ganzer Programme
6
• 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
1.7.1 Softwareentwicklung
Wichtige Begriffe:
• Softwarelebenszyklus (software life cycle)
• Phasenmodell der Softwareentwicklung
• Wasserfallmodell
7
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 teilweise automatisch den ganzen Entwicklungsprozeß un-terstutzen.
1.8 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
8
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 erlaubt,wenn der Mitarbeiter freiwillig und schriftlich sein Einverstand-nis erklart.
Eva MullerMitarbeiterin des Monats
1.10 Datenbanken
Beispiele:
• Literaturdatenbank
• Personaldatenbank
• Gefahrstoffdatenbank
• Buchunssystem fur Reiseburos/Fluggesellschaften
• ...
9
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 gewahr-leistet.
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: ≤ log2 m + 1dezimal: ≤ log10 m + 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
• 4 Gigabit pro cm2
• Spurabstand ≈ . . .
• Kopfe fliegen 10-15 Nanometer uber d. Platte
2.3.4 Speichertechnologie 1956–2005
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 Z3Der im Flugzeugbau tatige Maschinenbauer und Bauingenieur Konrad Zuse (Berlin, 1910–1985)erfand 1941 den ersten frei programmierbaren Rechner Z3.
• Baujahr 1941
• programmierbar uber Lochstreifen
• Ausgabe uber Lampenfeld
• Binare Schaltlogik
• “RISC”-Architektur: wenige Befehle
• Gleitpunktarithmetik
• Multiplikationszeit: 3 sec.
• Hauptspeicher: 64 Worte a 22 Bit
16
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.
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
17
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
• Milliarden Operationen pro sec.
• Anwendung in der KI, u.a. Neuronale Netze
PCs
Commodore Pet,1977, Kassetten-laufwerk, 4/8 kBHauptspeicher 2
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.”
18
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, Simula, APL, C, Pascal, Cobol, Perl,sh, awk, SQL, PHP
funktional: Lisp (1958), Haskell, Miranda, Mathematica
logisch: Prolog (1970)
objektorientiert: 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):
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.
• Bob Kahn und Vint Cerf erfinden 1973 das Transmission Control Protocol (TCP) und1976 das TCP/IP Protokoll.
• Bob Kahn und Vint Cerf erfinden 1973 das Transmission Control Protocol (TCP).
• Erstes Email-Netz 1977 an der Univ. Wisconsin.
• TCP/IP wird weltweit eingefuhrt
• Tim Berners-Lee erfindet 1989 das World Wide Web (WWW)
19
“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.
2.6.2 Aktuelle Trends (2005)
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)
20
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.
21
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
22
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)
23
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 beginnt die Erfolgsstory von Microsoft
• 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-Algorithmus2003 Alan Kay Objektorientierte Programmierung, Smalltalk
24
2004 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
• Mutter von vier Kindern
• Sie erfand Unterprogramme, Schleifen und bedingte Sprunge!
• publizierte unter dem Kurzel A.A.L.
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
Bis etwa 1960 waren viele Frauen in der Informatik tatig:
1teilweise entnommen aus Olga Goldmann Seminar: Geschichte der Informatik, www.virtosphere.de/schillo/teaching/WS2001/Geschichts-Seminar.html
25
• 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
26
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"
27
3.1.2 Algorithmus als PASCAL-Programm
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;
i,j : Index;
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 · (M + I) 0
j := j-1;∑n
i=2 i · (M + I) 0
END;
a[j+1] := x (n− 1) · (I + M) (n− 1) · (I + M)END
END;
Index i: 0 1 i nListe A: x a(i)
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 Terminie-rung einen negativen Wert annehmen. Da die Liste aber bei a(0) aufhort, wurde dies zu einemundefinierten Zustand fuhren. Diese Terminierung fuhrt zu einem weiteren Schleifendurchlauf.Dieser Durchlauf fallt aber nicht weiter ins Gewicht, da es sich um einen konstanten Aufwandhandelt. Dagegen wird im Vergleich zu einer zusatzlichen Bedingung im Kopf der While-Schleifeein Aufwand proportional zu n eingespart.
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:
28
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.
Tmax(n) = (n− 1) · (I + C + 3M + I + M + I) +n∑
i=2
(i · C + i · (2M + 2I))
= (3I + 4M + C) · n− (3I + 4M + C) + (2I + 2M + C) ·n∑
i=2
i
mitn∑
i=2
i =n(n + 1)
2− 1 =
n2 + n− 2
2=
n2
2+
n
2− 1
erhalten wir
Tmax(n) =
a︷ ︸︸ ︷(I + M +
C
2) ·n2 +
b︷ ︸︸ ︷(4I + 5M +
3
2C) ·n
c︷ ︸︸ ︷−(5I + 6M + 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) · c2
n∑i=2
i · C → (2∑
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
29
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
Algorithmus 1 Algorithmus 2 Algorithmus 3 Algorithmus 4 Algorithmus 5n T (n) = log n · c T (n) = c · n T (n) = c · n2 T (n) = c · n3 T (n) = c · 2n
10 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.
30
Definition 3.2 Seien die Funktionen f : N → R+, g : N → R+ gegeben. Dann schreibtman:
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
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
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)
31
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
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
32
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.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
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↔↑j1 2 3 3 4 5 6 7
↑j ↑i1 2 3 3 4 5 6 7
↑i↑j1 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:
33
i sucht von links nach einem Wert ≥ x und j von rechts nach einem Wert ≤ x. Dann werden iund j vertauscht. Das setzt sich solange fort bis sich beide Indizes uberkreuzen oder gleich sind.Dann wird die Liste rechts von j geteilt und auf beiden Halften rekursiv von vorne 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)
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)
34
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?
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↑j1 2 3 4 5 6 7 8
↑i↑j1 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
35
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
Idee zur Verhinderung des Worst Case: Liste vorher zufallig permutieren.
Begrundung: Die Wahrscheinlichkeit fur das Erzeugen einer sortierten Liste ist sehr klein. 110n
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 Pivotelements
ersetze 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.
36
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
Tiefe k = log n
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
37
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]
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.
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)
38
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 ist gleich 23n, 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)
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) = 2 T (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):
39
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
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
40
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) ≤blog nc∑h=1
⌈ n
2h+1
⌉·O(h) = O
n
blog nc∑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]
Idee
Wiederhole folgende Schritte bis der Heap nur noch aus einem Element besteht: 1.) vertauscheA[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)
41
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)
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
42
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).
3.4 Sortieren in linearer Zeit
Unter ganz bestimmten Bedingungen ist Sortieren sogar in linearer Zeit moglich, wie man anfolgendem Beispiel erkannt.
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)
43
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. In Datenbanken werden oft B-Baume verwendet.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?
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.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.
44
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 .
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
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!
45
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)cD. Knuth empfiehlt 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
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 m 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.
46
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].
47
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:
48
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.
49
Beispiel 4.3 G = (V, E) mit V = Menge von Stadten in Suddeutschland,E = (x, y) ∈ V1 × V1 | es gibt eine direkte Straße von x nach y (keine Einbahnstraße!)
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 azyklischer Graph(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 die einzigen Zy-klen.
• (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 Graph G 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
50
die Stadt gibt, auf dem jede Brucke genau einmal uberquert wird. Der zugehorige Graph istrechts angegeben.
A
B
C
D
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. Haben zweiKreise einen Knoten gemeinsam, so starten wir auf einem Kreis bis wir einen gemeinsamenKnoten V finden, verfolgen dann den zweiten Kreis von V bis wieder zu V und traversierendann den Rest des ersten Kreises. Wir haben nun einen Kreis der beide Kreise zu einem neuenverbindet. Dieses Verfahren wird rekursiv fortgesetzt, bis alle alle Zyklen zu einem Eulerkreisverbunden sind (siehe Abbildung). 2
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).
51
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
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
52
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
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).
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).
53
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 obiges Beispiel an und erhaltenfolgenden minimal aufspannenden Baum:
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 Sortieren fur einen Graphen mit n Knotenund m Kanten ist O(m + n log n). Mit optimierten Datenstrukturen ist (ohne Sortieren) sogareine fast lineare Komplexitat erreichbar [9].
54
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.
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
55
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
• 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)
56
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 Menge M auf sich selbst heißt Permutation.
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:
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
57
4.5.2 Der Nearest-Neighbour-Algorithmus
Idee
Starte in einem Knoten und wahle als nachsten immer den mit dem geringsten Abstand.
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.
Algorithmus
• sortiere alle Kanten in der Liste K
• 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.
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
58
Beispiel 4.11 Vergleich von 3 Heuristiken mit der optimalen Losung:
4.5.4 Optimaler Algorithmus Optimal TSP
Idee
berechne fur jede Tour∑n
i=1 wtour[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! ≤ n n . . . n = nn, (n− 1)! = (n− 1)(n− 2) . . . 1 ≤ (n− 1)n−1
damit ergibt sichT (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.
59
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 gibt es einen fast optimalen Alg. mit 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
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.5 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.
60
Beispiel 4.12
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:
61
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
62
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.
63
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 Σ.
64
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 dem Startsymbol kann manden 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.
65
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
66
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 Typ-3-Sprachen.
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.
67
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.Alle gangigen Programmiersprachen sind Turingmachtig. Das heißt, Programme in diesen Spra-chen konnen alles berechnen, was wir intuitiv als berechenbar ansehen. Diese Sprachen sind alsosehr “machtig”. Fur einfache Aufgabenstellungen in der Softwareentwicklung mochte man eineinfacheres Programmiermodell um die Programmierung zu vereinfachen.
5.4 Endliche Automaten zur Worterkennung
Ein derartiges einfaches Modell ist der endliche Automat. Anschaulich ist ein endlicher Automatein Rechenelement, welches auf einem Eingabeband beginnend mit dem ersten Zeichen derEingabe das eingegebene Wort Zeichen fur Zeichen liest. In jedem diskreten Rechenschritt machtder Automat einen Zustandsubergang. Abhangig vom aktuellen Zustand und dem gelesenenZeichen geht der Automat in einen neuen Zustand uber. Die Zahl der Zustande ist endlich.Erreicht der Automat nach Lesen des letzten Zeichens einen Endzustand, so hat er das Worterkannt.
68
H A L L O
Z Zustand
Lesekopf
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 Zustandsubergangstabelledarstellen
δ 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 e, f, m. Im Zustand zi
enthalt der Automat i Flaschen Mineralwasser. e steht fur die Eingabe eines Euro, f fur Eingabeeiner falschen Munze. m steht fur eine Flasche Mineralwasser. m kann sowohl eingegeben werden(durch den Betreiber) als auch ausgegeben werden (an den Kunden). Ein Paar x, y in der Tabellebeschreibt 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:
69
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 forma-le Beschreibung benotigt. Diese ist aber auch noch fur theoretische Uberlegungen in der Theorieder formalen Sprachen notwendig ( ⇒ Theoretische Informatik, Master). Wir beginnen ganzelementar:Nun kennen wir 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
70
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.
71
Satz 5.3 Eine Sprache L wird von einem endlichen Automaten genau dann erkannt, wenn sieregular ist.
72
Kapitel 6
Ubungen
6.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.
6.2 Sortieren
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?
73
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):
(ln n)ln n n3/2 n log n (n + 1)! n2n ln n√
n n!√
log n
2n ln ln n nn n (ln n!) 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
nlog m mlog n
n! nn
√n nsin n
Aufgabe 5 Beweisen Sie Satz 3.1, d.h. T (n) = Θ(g(n)) ⇔ T (n) = Ω(g(n)) und T (n) =O(g(n)).
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?
74
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.
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.
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.
75
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?
6.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:
76
AachenBasel 545Berlin 650 875
Bremen 370 775 400Dortmund 155 555 495 235
Dresden 645 745 200 490 515Dusseldorf 90 550 560 285 70 580
Aachen 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
6.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.
77
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.
78
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.
79
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.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.
80
