Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

1

Einführung in die Informatik für Naturwissenschaftler und Ingenieure I

Übung im Sommersemester 2004J. Seyfried

http://wwwipr.ira.uka.de/~lehre/EInfoseyfried@ira.uka.deTel.: (0721) 608-3656Zimmer 107, Geb. 40.28

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

2

Übung?

• Übungsblätter– Aufgaben zur Wiederholung und Verdeutlichung– Aufgaben zur Vertiefung– alte Klausuraufgaben

• Fragen !!!!!!! (?)• Wiederholung unklarer Sachverhalte

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

3

Übung?

• Übungsblätter– Aufgaben zur Wiederholung ...– Aufgaben zur Vertiefung– alte Klausuraufgaben

• Fragen !!!!!!! (?)• Wiederholung unklarer Sachverhalte

!

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

4

Informatik I + II

Informatik I

Informatik II

• Grundlagen

- mathematische

- logische

- informationstheoretische

• Algorithmen

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

5

Vorbereitung auf die Klausur

• Stoff verstehen• Aufgabenblätter rechnen

– ohne in die Musterlösung zu schielen

• alte Klausuren rechnen• sich „durchbeißen“, auch

wenn man nicht gleich auf die Lösung kommt!

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

6

Aufgabe 1

• Mengenbegriff:– Grundmenge wichtig:

Komplementbildung{1, 2, 3, 4}C = ?

• IN - {1, 2, 3, 4}• {5, 6, 7, 8, 9} auf Grundmenge {1,...9}

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

7

Aufgabe 1

• Mengenbegriff:– Grundmenge wichtig

1

2

3

6

78

95

4

A

B

C

D

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

8

Aufgabe 1

• Venn-Diagramme

Vereinigung:

Komplement:

Subtraktion:

Durchschnitt:

A B

A

A B

A B

A B

A - B

A B

AC

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

9

Aufgabe 3

• RelationenUns geläufige Relationen:

>< ...

„neue“ Relationen analog:

statt 3<4:

3 R 4

Relationen kann man schreiben als:

• Matrix

• Tabelle

• formal

• ...

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

10

Relationen – wofür?

• Ein Beispiel:

3 R 4?

SELECT * FROM session WHERE session_id='f09f8733c8b898ced7ca8f9405457f00'

Relationale Datenbanken (MySQL, ...) werden heute häufig für Webpräsentationen mit dynamischem Inhalt (Content Management Systeme - „CMS“) verwendet

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

11

Aufgabe 3

• Relationen kann man schreiben als:

– Matrix

– Tabelle

– formal

– ...

3

2 43

5

1

1

5

4

2

1R3 1R5

2R1 2R5

4R1 4R3 4R5

5R3

Andere Schreibweise:

(1, 3) R

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

12

Aufgabe 3

• {x: 3Rx}

3

2 43

5

1

1

5

4

2

= {}

• {x: (4, x)R}

={1, 3, 5}

• {x: xR5}

= {1, 2, 4}

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

13

Aufgabe 3

• Vorbereich:

– alle Zeilen, indenen ein„Böbbel“ ist

3

2 43

5

1

1

5

4

2{1, 2, 4, 5}

• Nachbereich:

– alle Spalten, indenen ein„Böbbel“ ist

{1, 3, 5}

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

14

Aufgabe 4

• Eigenschaften von Relationen

• spezielle Relationen

reflexiv, irreflexiv

symmetrisch, asymmetrisch

antisymmetrisch

transitiv

intransitiv

Äquivalenzrelation

Ordnungsrelation (totale, ...)Lernen!

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

15

Aufgabe 5 b)

• Eigenschaften von Relationenreflexiv

1

1

1

1( )

an allen Knoten

Matrixdarstellung Graphendarstellung

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

16

Aufgabe 5 b)

• Eigenschaften von Relationenirreflexiv

0

0

0

0( )

an keinem Knoten

Matrixdarstellung Graphendarstellung

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

17

Aufgabe 5 b)

• Eigenschaften von Relationensymmetrisch

w 1 .

1 x . 0

.. y

0 z( )

Nur bidirektionale Kanten, Schleifen erlaubt

Matrixdarstellung Graphendarstellung

Matrix spiegelsymmetrisch

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

18

Aufgabe 5 b)

• Eigenschaften von Relationenasymmetrisch

...

Nur unidirektionale Kanten, keine Schleifen

Matrixdarstellung Graphendarstellung

aijaji i, j=1..n, ij

aii1 i=1..n

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

19

Aufgabe 5 b)

• Eigenschaften von Relationenantisymmetrisch

...

Nur unidirektionale Kanten, Schleifen erlaubt

Matrixdarstellung Graphendarstellung

aijaji i j

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

20

Aufgabe 5 b)

• Eigenschaften von Relationentransitiv

...

Zu 2 benachbarten Kanten gibt es auch eine direkte

Matrixdarstellung Graphendarstellung

aij=ajk =1 aik =1 i, j, k=1..n

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

21

Aufgabe 5 b)

• Eigenschaften von Relationenintransitiv

...

Zu 2 benachbarten Kanten gibt es keine direkte

Matrixdarstellung Graphendarstellung

aij=ajk =1 aik =0 i, j, k=1..n

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

22

Aufgabe 5 c)

• OrdnungsrelationenDarstellung als Hasse-Diagramm:

• Richtung der Pfeile immer implizit von unten nach oben

• Pfeile aus Transitivität werden weggelassen

a

bc

e d

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

23

Aufgabe 5 c)

• OrdnungsrelationenDarstellung als Hasse-Diagramm:

• Richtung der Pfeile immer implizit von unten nach oben

• Pfeile aus Transitivität werden weggelassen

a

bc

e d

Reflexivitäts-Kanten: weg

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

24

Aufgabe 5 c)

• OrdnungsrelationenDarstellung als Hasse-Diagramm:

• Richtung der Pfeile immer implizit von unten nach oben

• Pfeile aus Transitivität werden weggelassen

a

bc

e d

Reflexivitäts-Kanten: weg

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

25

Aufgabe 5 c)

• OrdnungsrelationenDarstellung als Hasse-Diagramm:

• Richtung der Pfeile immer implizit von unten nach oben

• Pfeile aus Transitivität werden weggelassen

a

bc

e d

Reflexivitäts-Kanten: weg

Transitivitäts-Kanten: weg

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

26

Aufgabe 5 c)

• OrdnungsrelationenDarstellung als Hasse-Diagramm:

• Richtung der Pfeile immer implizit von unten nach oben

• Pfeile aus Transitivität werden weggelassen

a

bc

e d

Reflexivitäts-Kanten: weg

Transitivitäts-Kanten: weg

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

27

Aufgabe 5 c)

• OrdnungsrelationenDarstellung als Hasse-Diagramm:

• Richtung der Pfeile immer implizit von unten nach oben

• Pfeile aus Transitivität werden weggelassen

a

bc

e d

Reflexivitäts-Kanten: weg

Transitivitäts-Kanten: weg

Pfeilrichtungen implizit

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

28

Aufgabe 5 c)

• OrdnungsrelationenDarstellung als Hasse-Diagramm:

• Richtung der Pfeile immer implizit von unten nach oben

• Pfeile aus Transitivität werden weggelassen

a

bc

e d

Reflexivitäts-Kanten: weg

Transitivitäts-Kanten: weg

Pfeilrichtungen implizit

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

29

Aufgabe 5 c)

• OrdnungsrelationenDarstellung als Hasse-Diagramm:

• Richtung der Pfeile immer implizit von unten nach oben

• Pfeile aus Transitivität werden weggelassen

a

bc

e d

a

bc

e d

Hasse-Diagramm

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

30

Aufgabe 5 c)

• OrdnungsrelationenDarstellung als Hasse-Diagramm:

• Richtung der Pfeile immer implizit von unten nach oben

• Pfeile aus Transitivität werden weggelassen

• Totalordnungen: Ketten

a

bc

e d

Hasse-Diagramm

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

31

Aufgabe 8

In einer Bibliothek werden jedem Buch seine bisherigen Leser zugeordnet. Was ist hier Vorbereich, was Nachbereich? Wird hierdurch eine Abbildung definiert?

Menge der Bücher B

Menge der Kunden K

b R k k hat b gelesen

bB, kK

Vorbereich:

V(R) = {x: kK mit xRk}

Menge der Bücher, die mindestens einmal gelesen wurden

Nachbereich:

N(R) = {x: bB mit bRx}

Kunden der Bibliothek, die mindestens ein Buch gelesen haben

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

32

Aufgabe 8

In einer Bibliothek werden jedem Buch seine bisherigen Leser zugeordnet. Was ist hier Vorbereich, was Nachbereich? Wird hierdurch eine Abbildung definiert?

Menge der Bücher B

Menge der Kunden K

b R k k hat b gelesen

bB, kK

Ist R Funktion?

Zu prüfen:

• Rechtseindeutigkeit

• V(R) = B

Anschaulich: Funktion f: MN

• f(m) definiert mM

• f(m) ist eindeutig

1

2

3

4

g: MN

1

2

3

M N

G ist keine Funktion!

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

33

Aufgabe 8

In einer Bibliothek werden jedem Buch seine bisherigen Leser zugeordnet. Was ist hier Vorbereich, was Nachbereich? Wird hierdurch eine Abbildung definiert?

Menge der Bücher B

Menge der Kunden K

b R k k hat b gelesen

bB, kK

Ist R Funktion?

Zu prüfen:

• Rechtseindeutigkeit

• V(R) = B

R ist nicht rechtseindeutig (mehrmals gelesene Bücher)

V(R) muss nicht gleich B sein (noch nie gelesene Bücher)

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

34

Aufgabe 9

• Eigenschaften von AbbildungenAbbildungen auf abzählbaren Mengen:

Surjektivität

1

2

3

4

Kein Element des Nachbereichs ist ohne Pfeil

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

35

Aufgabe 9

• Eigenschaften von AbbildungenAbbildungen auf abzählbaren Mengen:

Surjektivität

1

2

3

4

Kein Element des Nachbereichs ist ohne Pfeil

Nicht surjektiv

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

36

Aufgabe 9

• Eigenschaften von AbbildungenAbbildungen auf abzählbaren Mengen:

Injektivität

1

2

3

4

Auf kein Element des Nachbereichs wird zwei Mal gezeigt

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

37

Aufgabe 9

• Eigenschaften von AbbildungenAbbildungen auf abzählbaren Mengen:

Injektivität

1

2

3

4

Auf kein Element des Nachbereichs wird zwei Mal gezeigt

Nicht injektiv

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

38

Aufgabe 9

• Komposition von Abbildungenf g wird gesprochen: f nach g

1

2

3

4

1

2

3

4

g

1

2

3

4

1

2

3

4

f

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

39

Aufgabe 9

• Komposition von Abbildungenf g wird gesprochen: f nach g

1

2

3

4

1

2

3

4

g

1

2

3

4

1

2

3

4

ff g

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

40

Aufgabe 9

• Komposition von AbbildungenZusammengefasst:

1

2

3

4

1

2

3

4

fg

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

41

Aufgabe 9 b)

• Komposition von AbbildungenBei unterschiedlichen Wertebereichen: h g

zuletzt ausgeführte Abbildung (hier: h) gibt den Wertebereich an

1

2

3

4

1

3

h

1

2

3

4

1

2

3

4

f

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

42

Aufgabe 10

1)( 3 xxf

Monoton steigend

injektiv

f: IR IRf(IR) = IR

surjektiv

bijektiv

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

43

Aufgabe 10

)sin()( xxxg

f: IR IRf(IR) = IR

surjektiv

f(x1)=f(x2)

x1=x2/

nicht injektiv

nicht bjektiv

Prof. Dr.-Ing. H. Wörn, Dr.-Ing. J. SeyfriedInstitut für Prozessrechentechnik, Automation und Robotik; Universität Karlsruhe (TH) 2004

44

Aufgabe 10

1)(sin)( 33

xxxhgfh

f: IR IRf(IR) = IR

surjektiv

f(x1)=f(x2)

x1=x2/

nicht injektiv

nicht bjektiv