Einführung in die Informatik I Prof. Dr. Bernd Schmidt Lehrstuhl für Operations Research und...

Einführung in die Informatik I

Prof. Dr. Bernd SchmidtLehrstuhl für Operations Research und Systemtheorie, Universität Passau

Planung

Lehrstuhl für Operations Research und Systemtheorie Planung Folie 2

Gliederung

1. Einführung: Probleme

2. Definitionen: Zustand

3. Suchstrategien: Breitensuche

Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche

4. Planung: Bedingungsabhängige Aktionen

Verbotene Zustände

5. Anwendung: Beispiel Ziege, Kohlkopf und Wolf

Gliederung

Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche

Verbotene Zustände

Einführung Labyrinth

Aufgabe: finde einen Weg von einem gegebenen Startpunkt zu einem Ausgang

Einführung Aktionsrepertoire und Strategie: Labyrinth

Die Knoten sind Punkte, an denen sich der Agent zu bestimmten Zeitpunkten befindet.

An jedem Knoten stehen dem Agenten unterschiedliche Handlungsoptionen zur Verfügung.

Mögliche Aktionen:

Strategie:

versuche

1: links

2: vorwärts

3: zurück

4: rechts

vorwärts

rechtslinks

zurück

1. Versuch:

2. Versuch:

3. Versuch:

Einführung Ziege, Kohlkopf und Wolf

Aufgabe:

- Fährmann muss Ziege, Kohlkopf und Wolf von einem Ufer zum anderen transportieren

Regeln:- Fähre: Fährmann + ein Passagier

- bleiben Ziege und Kohlkopf an einem Ufer zurück, so wird der Kohlkopf gefressen

- bleiben Wolf und Ziege an einem Ufer zurück, so wird die Ziege gefressen

Notation:

- Fährmann fährt alleine nach oben:

- Wolf und Fährmann fahren nach unten:

Ziege:

Kohlkopf:

Bewegung der Fähre: ▲, ▼

Beispiele:

Fährmann: F

1. Versuch:

ZF▼Notation:

ZF▼1:

Aktionsfolge:

1. Versuch:

Notation: F▲

2:F▲

Aktionsfolge:

1. Versuch:

Notation: KF▼

2:F▲

3:KF▼

Aktionsfolge:

1. Versuch:

Notation: F▲

2:F▲

3:KF▼

4:F▲

Aktionsfolge:

2. Versuch:

ZF▼Notation:

ZF▼1:

Aktionsfolge:

2. Versuch:

Notation: F▲

2:F▲

Aktionsfolge:

2. Versuch:

Notation: KF▼

2:F▲

3:KF▼

Aktionsfolge:

2. Versuch:

Notation: ZF▲

2:F▲

3:KF▼

4:ZF▲

Aktionsfolge:

2. Versuch:

Notation: WF▼

2:F▲

3:KF▼

4:ZF▲

5:WF▼

Aktionsfolge:

2. Versuch:

Notation: F▲

2:F▲

3:KF▼

4:ZF▲

5:WF▼

6:F▲

Aktionsfolge:

2. Versuch:

Notation: ZF▼

2:F▲

3:KF▼

4:ZF▲

5:WF▼

6:F▲

7:ZF▼

Aktionsfolge:

ZF▼ F▲ KF▼

WF▼ F▲ ZF▼

Gliederung

Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche

Verbotene Zustände

Ein Plan ist eine Abfolge von Aktionen, die einen Anfangszustand A durch Ausführung von Aktionen über Zwischenzustände Z in einen Endzustand E überführt.

Definitionen Plan

Ein Zustand ist eine Menge von Zustandsvariablen.

Ex1=e1

x2=e2 .

..xn=en

Im Endzustand besitzen alle Zustandsvariablen den richtigen Wert.

x1= a1

x2= z1

xn= an

x1= z1

xn= zn

x2= a1

Anfangszustand

Zwischenzustand

Endzustand

Zustand der Umwelt vor Beginn der Abarbeitung des Plans

Zustand der nach Erreichen des Ziels eingenommen werden soll

ZF▼ F▲

ZF▲ WF▼ F▲ ZF▼

Gliederung

Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche

Verbotene Zustände

Bewertungskriterien

- Vollständigkeit

Wird eine Lösung garantiert gefunden, wenn es eine gibt?

- Zeitkomplexität

Innerhalb welcher Schranken bewegt sich die Dauer zur Ermittlung eines Ergebnisses?

- Speicherkomplexität

Innerhalb welcher Schranken bewegt sich der Verbrauch an Speicherplatz?

- Optimalität (bzgl. der Pfadkosten)

Wird eine beste Lösung gefunden, wenn eine existiert?

Suchstrategien Bewertungskriterien

Suchstrategien Klassifikation

Klassifikation von Suchstrategien

- blinde Suche:

- Breitensuche

- Tiefensuche

- Uniform Cost Suche

- Tiefenbeschränkte Suche

- Informierte Suche:

- Greedy Suche

- A*- Suche

kein Wissen über die Richtung zum Ziel vorhanden

Zielrichtung ist bekannt, Verarbeitung in heuristischer Funktion

Suchstrategien Datenstrukturen

Datenstrukturen für Suchbäume

Knoten {

Zustand // Zustand, der dem Knoten entspricht

Mutterknoten // Verweis auf den erzeugenden Konten

Operator // erzeugender Operator

Pfadkosten // aufsummiert, beginnend am Anfangszustand

Kanten = Übergänge zwischen den Knoten

= Zustände

= Aktionen

Suchstrategien Netz aus Knoten und Kanten

Zerind

Oradea

Riminicu V.Timisoara

Mehadia

Fagaras

Pitesti

Dobreta

Craiova

UrziceniBucharest

Giurgiu

Hirsova

Vasuli

Eforie

KantenKnoten

Suchstrategien Wegsuche in Rumänien

Zerind

Timisoara

Oradea

Riminicu V.

Fagaras

ZerindSibiuTimisoara

Expandieren des Anfangszustandes:

Wie gelangt man zum Strassennetz?

Expandieren!

Alle möglichen Aktionen

ausführen, die von einem

Zustand aus ausführbar sind.

Beispiel:

Suchstrategien Blinde Suche: Wegsuche in Rumänien

Zerind

Timisoara

Oradea

Riminicu V.

Fagaras

Bewertung + Auswahl: Welcher Knoten soll als nächster expandiert werden?

Blinde Suche: alle drei Knoten sind gleichberechtigt

Suchstrategien Informierte Suche: Wegsuche in Rumänien

Zerind

Timisoara

Oradea

Riminicu V.

Fagaras

Bewertung + Auswahl: Welcher Knoten soll als nächster expandiert werden?

Informierte Suche: Zusatzinformation wird verarbeitet:

z.B. Sibiu liegt in Richtung Bucharest, daher Sibiu zuerst expandieren

Suchstrategien Queue

Organisation der Daten

Eine Queue ist eine Warteschlange für zu expandierende Knoten.

Suchstrategien unterscheiden sich durch…

- …den Mechanismus, der die Reihenfolge zu expandierender Knoten festlegt

- …den Mechanismus, der entscheidet, an welcher Stelle die noch zu

expandierenden Knoten in die Queue eingereiht werden.

expandieren

Suchstrategien Queue

Organisation der Queue

- Wird ein Knoten expandiert, so werden die Tochterknoten am Ende der

Queue angehängt.

- Der expandierte Knoten wird aus der Queue entfernt.

- Die Queue wächst am hinteren Ende.

expandieren

d d d d+1 d+1

Tiefe d

Tiefe d+1

Suchstrategien Beispiel Breitensuche

Breitensuche: in einer Ebene werden die Knoten von links nach rechts aufgefüllt

Suchstrategien Breitensuche: Wegsuche in Rumänien

Zerind

Oradea

Riminicu V.Timisoara

Mehadia

Fagaras

Pitesti

Dobreta

Craiova

UrziceniBucharest

Giurgiu

Hirsova

Vasuli

Eforie

Aufgabe: finde einen Weg von Arad nach Bucharest

Suchstrategien Breitensuche: Wegsuche in Rumänien

QueueArad

1. Anfangsknoten mit Anfangszustand Arad

2. Nach der Expansion von Arad

QueueSibiu ZerindTimisoara

3. Nach der Expansion von Timisoara

AradQueue

Sibiu Zerind Lugoj

Suchstrategien Beispiel Tiefensuche

1 2 3 4 5

Tiefensuche: alle Knoten eines Pfades werden bis zur maximalen Tiefe expandiert

Suchstrategien Tiefensuche: Wegsuche in Rumänien

Timisoara

QueueArad

1. Anfangsknoten mit Anfangszustand Arad

2. Nach der Expansion von Arad

QueueTimisoara

3. Nach der Expansion von Timisoara

Timisoara

AradQueue

Suchstrategien Uniform Cost Suche

Uniform Cost Suche (Blinde Suche)

- Modifizierte Breitensuche

- Einführung von Pfadkosten direkter Verbindungen durch Pfadkostenmatrix

- Knoten mit den geringsten Pfadkosten werden zuerst expandiert

Arad Zerind Sibiu Timisoara ...

Arad 0 75 140 118 ...

Zerind 75 0 - - ...

Sibiu 140 - 0 - ...

Timisoara 118 - - 0 ...

... ... ... ... ... 0

Zusatzinformation: Pfadkostenmatrix

- Neu generierte Knoten werden derart eingefügt, dass die Knoten bezüglich

ihrer Pfadkosten aufsteigend sortiert sind.

expandieren

75 118 140

118 140 75

Zerind Sibiu Timisoara

Oradea

Timisoara Sibiu OradeaZerind

Suchstrategien Uniform Cost Suche: Wegsuche in Rumänien

Uniform Cost Suche

Arad QueueArad

QueueSibiuZerind Timisoara

Zerind 75Sibiu 140Timisoara 118

QueueSibiuTimisoara

Oradea 146

Oradea

Uniform Cost Suche

QueueSibiu Lugoj

Oradea 146

Oradea

Lugoj 229

QueueRiminicu V. Lugoj

Oradea 146

Oradea

Lugoj 229 Riminicu V. 220 Fagaras 239

Fagaras

Suchstrategien Greedy Suche

Greedy Suche

- Informierte Suche

- Bewertungsfunktion: Heuristik h: Knoten Int

ermittelt die (geschätzte) Entfernung eines Knotens (= Zustand)

zum Ziel

Expandieren von Knoten

- Expandiert wird der Knoten, dem die geringste geschätzte Entfernung zum Ziel

zugeschrieben wird.

Eigenschaften

- Nicht vollständig

- Nicht optimal

Suchstrategien Greedy Suche

Greedy Suche

Arad 366 QueueArad

QueueZerindTimisoara

Oradea

Oradea 380 Arad 366Fagaras 178Riminicu V. 193

Fagaras Riminicu V. Arad

Suchstrategien A*- Suche

A*- Suche

- Kombination von Uniform Cost Suche und Greedy Suche

- Bewertung der Knoten: Heuristik h(n) = f(n) + g(n)

- Dabei: f(n) = Summe der Strassenkilometer (Arad Ortn) (Uniform Cost Suche)g(n) = Luftliniendistanz (Ortn Bucharest) (Greedy- Suche)

Eigenschaften

- Vollständig.

- Optimal.

- Neu generierte Knoten werden derart eingefügt, dass die Knoten bezüglich

ihrer Pfadkosten aufsteigend sortiert sind- Analog zur Uniform Cost Suche, Greedy- Suche

Suchstrategien A*- Suche

A*- Suche 0 Arad 366

QueueArad

75 Zerind 374

140 Sibiu 253

118 Timisoara 329

QueueZerindTimisoara Oradea

146 Oradea 380

239 Fagaras 178

220 Riminicu V. 193

FagarasRiminicu V. Arad

280 Arad 366

75 Zerind 374

140 Sibiu 253

118 Timisoara 329

Gliederung

Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche

Verbotene Zustände

Planung Zusammenschau

• Anfangszustand A, Endzustand E• Zustandsmenge Z• Aktionsmenge O

• Einschränkungen– Bedingungsabhängige Aktionen– Verbotene Zustände

…a1 an

Ein Plan ist eine Abfolge von Aktionen, die einen Anfangszustand durch Ausführung von Aktionen in einen Endzustand überführt.

Planung Einschränkungen

Einschränkungen

Verbotene Zustände- Dürfen durch Ausführung von Aktionen zu keiner Zeit eingenommen werden

A Z1 Z4Z3Z2ZF▼ F▲ KF▼ F▲

Verbotener Zustand:

Fährmann lässt Ziege und

Kohlkopf am selben Ufer zurück

Planung Einschränkungen

Bedingungsabhängige Aktionen

- Dürfen nur ausgeführt werden, wenn alle Vorbedingungen erfüllt sind, die

an die Aktion gebunden sind.

Einschränkungen

Notation

Boot obenBedingung(en):

(Fähre runter)

Bedingungen werden an Aktion gebunden

Boot oben

F▼Aktion: (Fähre runter)

Planung Breitensuche: Beispiel

Beispiel: arithmetische Umformung

Aktionsmenge O:

A = 10

Startzustand Zielzustand

B=B- 1

Verbotene Zustände:

Planung Breitensuche: Beispiel

Beispiel: arithmetische UmformungA = 1

Aktionsauswahl:A > 0

B=B- 1

Planung Breitensuche: Bedingungsabhängige Aktionen

B=B- 1

Planung Breitensuche: Verbotene Zustände

B=B- 1

Verbotener Zustand

B=B- 1

Verbotener Zustand

B=B- 1

C=C Verbotener Zustand

B=B- 1

C=C Verbotener Zustand

B=B- 1

A = 10

B=B- 1

A = 10

Zielzustand erreicht

Gliederung

Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche

Verbotene Zustände

Anwendung Ziege, Kohlkopf und Wolf

Notation:

Ziege:

Kohlkopf:

Bewegung der Fähre: ▲, ▼

Startzustand:Z = oK = oW = oF = o

Erinnerung: Weder Ziege und Kohlkopf, noch Ziege und Wolf dürfen vom Fährmann am selben Ufer zurückgelassen werden!

Fährmann: F

Modellierung der Zustände

Z K W FZ K W FZ K F WZ K W FZ W F KZ W K FZ F K WZ K W F

K W F ZK W Z FK F Z WK Z W F

W F Z KW Z K F

F Z K WZ K W F

Ôben o Unten u

Zustände:

Start-Zustand

End-Zustand

Z = oK = oW = oF = o

Z = uK = uW = uF = u

Z = oK = uW = uF = o

Notation: F▲

2:F▲

Aktionsfolge:

Zustand:Z = uK = oW = oF = u

Einschränkungen

Z = oK = oW = oF = u

Z = oK = uW = oF = u

Z = oK = oW = uF = u

Z = uK = uW = oF = o

Z = uK = oW = uF = o

Alle an einem Ufer, ohne Fährmann

Ziege und Wolf oben, Fährmann unten

Ziege und Wolf unten, Fährmann oben

Ziege und Kohlkopf oben, Fährmann unten

Ziege und Kohlkopf unten, Fährmann oben

Einschränkungen

Bedingungsabhängige Aktionen:

W F▼

Soll sich der Fährmann nach oben bewegen, so muss sich die Fähre zuerst unten befinden…

...ebenso in die umgekehrte Richtung...

... soll er dabei einen Passagier transportieren, so muss sich dieser am selben Ufer wie die Fähre befinden...

Zustandsübergang

Z = uK = oW = oF = o

Z = uK = uW = oF = u

- Fährmann transportiert den Kohlkopf von oben nach unten

unter Einhaltung aller Bedingungen:

Anwendung Breitensuche: Ziege, Kohlkopf und Wolf

Suchbaum Z = oK = oW = oF = o

Z = uK = oW = oF = u

ZF▼ KF▼

Anwendung Breitensuche

ZF▼ KF▼

Verbotene Zustände

ZF▼ KF▼

Verbotene Zustände

ZF▲ F▲

Dieser Zustand ist identisch mit dem Anfangszustand.

Ein Zustand, der bereits einmal expandiert wurde, muss nicht nochmals expandiert werden.

ZF▲ F▲

Dieser Zustand ist identisch mit dem Anfangszustand.

Suchbaum

Z = uK = oW = uF = u

WF▼Z = uK = oW = oF = u

Suchbaum

Dieser Zustand wurde bereits expandiert

Suchbaum Z = uK = oW = oF = o

Dieser Zustand wurde bereits expandiert

KF▼ WF▼

Z = oK = uW = oF = o

Bereits expandierter Zustand

Verbotener Zustand

KF▼ WF▼

Z = oK = oW = uF = o

KF▲ F▲

Verbotener Zustand

KF▼ WF▼

KF▲ F▲

Verbotener Zustand

Lösung Z = oK = oW = oF = o

Z = oK = uW = uF = u

WF▼ZF▼

Die entstehenden Pläne

ZF▼ F▲

ZF▲WF▼

F▲KF▼ ZF▼

ZF▼ F▲

ZF▲ZF▼

F▲WF▼ ZF▼

Zusammenfassung

Z0 Z1 Z6 EFZ▼ F▲ FZ▼

Definitionen:

Zustände, Aktionen, Pläne

Zerind

Timisoara

Oradea

Riminicu V.

Fagaras

Suchstrategien:

Breitensuche, Tiefensuche, Uniform Cost, Greedy- Suche, A*- Suche

Verbotener Zustand

Planung:

Bedingungsabhängige Aktionen, verbotene Zustände

Anwendung:

Das Ziege- Kohlkopf- Wolf- Problem mit Breitensuche

Einführung in die Informatik I Prof. Dr. Bernd Schmidt Lehrstuhl für Operations Research und...

Documents

(Network) Coding und Verbindungen zur Systemtheorie€¦ · (Network) Coding und Verbindungen zur Systemtheorie Klassische Codierungstheorie Einf uhrung De nition Ein Block-Code uber

Druckdatei für Internet Mitglieder 08 2013 - wifo-passau… · Herr Stefan Aigner Passau Branche: Weiterbildung - Ausbildung Elektrotechnik Escherich Herr Andreas Escherich ... Passau

SYSTEMTHEORIE - Fernmasterfernmaster.de/fileadmin/02_PDF/A33_V19_Auszug.pdf · 2017. 11. 8. · Schwerpunkte in Lehre und Forschung: - Systemtheorie und Regelungstechnik, - Automatisierungstechnik,

Etwas Signal- und Systemtheorie „for Dummies“tlange/pdf/Etwas Signal- und Systemtheori… · FB Elektrotechnik Prof. Dr.-Ing. Tatjana Lange Signal- und Systemtheorie „for Dummies“

Operations Console - Handbuch

Operations DUALES STUDIUM: AVIATION MANAGEMENT · Die Operations – das Herzstück einer Airline Als Operations managen wir den reibungslosen Ablauf am Boden und in der Luft. Zu

Major im B.Sc. Operations & Information Management … · Cases in Management Support Service Operations Cases in Optimization Alternative III (30 LP) Der Praktiker Operations Research

De-/Regulierung: Eine juristische Begriffsanalyse unter Einbezug der Systemtheorie

Krieger, David - Einführung in Die Allgemeine Systemtheorie

Aktuelle Forschungsprobleme der Systemtheorie

Buch Kleve Sozialarbeitswissenschaft Systemtheorie Postmoderne

Glasmuseum Passau

BISTUM PASSAU KIRCHENMUSIK · 2020-07-14 · Impressum Referat Kirchenmusik Passau, Domplatz 3, 94032 Passau Layout: Kommunikationsdesign Bistum Passau 6/2020 Fotos: pbp, Barbara

10 - Fh Heidelberg Systemtheorie

Operations Management - Reese, Inhaltsverzeichnis€¦ · Operations Management betrifft uns alle, die wir Entscheidungen im täglichen Leben treffen und damit Tätigkeiten ( Operations

Schlüsselwerke der Systemtheorie - link.springer.com978-3-531-20004-0/1.pdf · Dirk Baecker (Hrsg.) Schlüsselwerke der Systemtheorie 2., erweiterte und neu gestaltete Auflage

E-Commerce Service Operations

Luftbildkalender Passau, Kalender Passau

Services & Operations Management Modulkürzel: MOEC0422399366ff-2f46-4ed9-a26c-8af... · 1 F Operations Strategy at Galanz #910D05 2 F American Connector Company #693035 3 S Operations

Systemtheorie, Evolutionstheorie und Kommunikationstheorie