Hallo zusammen,
ich versuche mich mal an einer Lösung für die Einsendaufgabe Nr 4 des Kurses 20046:
Die Aufgabe 4.1.a.) stellt meiner Ansicht nach das größte Problem der Einsendeaufgabe dar. Hat jemand eine Idee, wie man sie am besten lösen kann? In einem anderen Forum wurde von einem p-reduzierbarem Maschinenbelegungsproblem gesprochen bzw. analysiert, dass das gegebene Problem nicht polynomiell ist. Wie kommt man auf diese Lösung?
4.1.b.)
P1: 5, 1
P2: 5, 1
4.1.c.)
P1: 5
P2: 1, 1, 5
Daraus folgt eine Makespan von 7.
4.1.d.)
Durch die absteigende Sortierung ergibt sich dieselbe Verteilung wie in b.)
P1: 5, 1
P2: 5, 1
Makespan = 6
4.2.a.)
Die Worte haben die Länge l = 2 + 3n, wobei n element der natürlichen Zahlen mit 0.
4.2.b.)
Es gibt vier Zustände: Z1, Z2, Z3, Z4, wobei Z1 Anfangszustand ist und Z3/Z4 Endzustände sind.
Die Übergänge sind Z1 nach Z2 für a, Z2 nach Z3 für a, Z3 nach Z4 für a und von Z4 nach Z2 für a.
4.2.c.)
Es gibt drei Zustände: Z1, Z2, Z3, wobei Z1 Anfangs- und gleichzeitig Endzustand ist.
Die Übergänge lauten: Z1 nach Z2 für a, Z2 nach Z3 für a, Z3 nach Z1 für b.
4.3.)
Bereits in Schritt 2 entstehen keine weitere Markierungen und der Algorithmus ist abgeschlossen. Es gibt zwei 2-äquivalente (und da keine neue Markierung mehr entstand: äquivalente) Zustandspaare: (s0, s1) und (s2, s3).
Hoffe die Ergebnisse bieten einen Anhaltspunkt.
Schönen Abend noch!
ich versuche mich mal an einer Lösung für die Einsendaufgabe Nr 4 des Kurses 20046:
Die Aufgabe 4.1.a.) stellt meiner Ansicht nach das größte Problem der Einsendeaufgabe dar. Hat jemand eine Idee, wie man sie am besten lösen kann? In einem anderen Forum wurde von einem p-reduzierbarem Maschinenbelegungsproblem gesprochen bzw. analysiert, dass das gegebene Problem nicht polynomiell ist. Wie kommt man auf diese Lösung?
4.1.b.)
P1: 5, 1
P2: 5, 1
4.1.c.)
P1: 5
P2: 1, 1, 5
Daraus folgt eine Makespan von 7.
4.1.d.)
Durch die absteigende Sortierung ergibt sich dieselbe Verteilung wie in b.)
P1: 5, 1
P2: 5, 1
Makespan = 6
4.2.a.)
Die Worte haben die Länge l = 2 + 3n, wobei n element der natürlichen Zahlen mit 0.
4.2.b.)
Es gibt vier Zustände: Z1, Z2, Z3, Z4, wobei Z1 Anfangszustand ist und Z3/Z4 Endzustände sind.
Die Übergänge sind Z1 nach Z2 für a, Z2 nach Z3 für a, Z3 nach Z4 für a und von Z4 nach Z2 für a.
4.2.c.)
Es gibt drei Zustände: Z1, Z2, Z3, wobei Z1 Anfangs- und gleichzeitig Endzustand ist.
Die Übergänge lauten: Z1 nach Z2 für a, Z2 nach Z3 für a, Z3 nach Z1 für b.
4.3.)
Bereits in Schritt 2 entstehen keine weitere Markierungen und der Algorithmus ist abgeschlossen. Es gibt zwei 2-äquivalente (und da keine neue Markierung mehr entstand: äquivalente) Zustandspaare: (s0, s1) und (s2, s3).
Hoffe die Ergebnisse bieten einen Anhaltspunkt.
Schönen Abend noch!