Philosophenproblem, habe ich nun einen Deadlock oder nicht? (Was genau meint zyklische Wartebedingung)?

Bild zum Beitrag

Aufgabe:

Bild zum Beitrag

Mein Problem hierbei ist, ich verstehe nicht, warum die zyklische Wartebedingung aufgehoben wurde. Es gibt ja immer noch Prozesse die die gleiche Gabel wollen und warten müssen, wenn einer die zuerst erhalten hat? Dadurch habe ich doch zyklisches warten?

2 Antworten

Trilobit

27.08.2022, 17:06

Konstruieren wir doch mal einen Deadlock: Wir versuchen, dafür zu sorgen, dass jeder Philosoph genau eine Gabel vom Tisch nimmt und dann vergeblich auf die zweite wartet.

In der Grafik deuten die Pfeilfarben an, dass jeder der Philosophen "12" bis "45" die jeweils rechts von ihm liegende Gabel nimmt. Soweit sieht alles gut aus.

Was passiert aber mit Gabel 5? Philosoph "51" braucht zuerst Gabel 1, deshalb bekommt Philosoph "45" Gabel 5 und kann essen. Sobald er satt ist, kann der rechts von ihm sitzende Philosoph essen, bis auch Philosoph "12" satt ist und Philosoph "51" Gabel 1 überlässt.

Die Lösung bringt in eine Situation, in der es ein Gleichgewicht gibt, gezielt eine kleine Störung ein. So wird garantiert, dass ein Patt nicht stabil bleibt, sondern immer in eine bestimmte Richtung kippt und sich so auflöst.

PWolff

27.08.2022, 17:07

Die Gabel mit der höchsten Nummer (5) hat die niedrigste Priorität, wenn es darum geht, sie zu reservieren. Kann sie reserviert sein, während irgendein Philosoph auf eine andere Gabel wartet?

Von dort aus die Prioritätsliste hinauf.

Ähnliche Beiträge

Mein Python-Code schlägt in einigen Testfällen fehl (4 von 43) und ich verstehe nicht, warum?

Also habe ich versucht, diese Aufgabe zu lösen: https://training.olinfo.it/#/task/ois_avg/statement. Aber in einigen Testfällen ist meine Ausgabe offensichtlich falsch.

Aufgabe: Sie haben N Produkte, deren Preise in einer Liste P mit N Elementen angegeben sind (jedes Produkt hat einen Preis). Sie müssen den Preis einiger Produkte ändern, um einen Durchschnittspreis von K zu erhalten. K, N und alle Elemente von P sind positive ganze Zahlen. Wie groß ist die Mindestanzahl der Produkte, deren Preise geändert werden müssen?

Mein Code:


#input
N, K = map(int, input().strip().split())
P = list(map(int, input().strip().split()))

#main
ans = 0
average = sum(P)/N
difference = (average - K)*N
if average<K:
    ans = 1
elif average == K:
    ans = 0
else:
    P.sort(reverse=True)
    for i in range(N):
        ans+=1
        difference = difference - P[i]+1
        if difference < 1:
            break
#output
print(ans)

...zum Beitrag

Hilfe bei Aufgabe (Halbaddierer und Volladdierer)?

Hallo :) Wir müssen eine Schaltung zu den Dualzahlen 10010 +11101

machen.

Also mit Halb und Volladdierer.
Zuerst das halt ausrechnen und per Hand zeichnen. Könnte mir da vielleicht einer behilflich sein ?

...zum Beitrag

Zugbindung aufgehoben, darf man Züge Vorher nehmen?

Habe einen Zug von Stuttgart hbf bach Duisburg hbf am Samstag.

Der fährt um 04:49 vom Stuttgarter hbf und auf den würde ich lange warten müssen, dürfte ich indem fall einen früher nehmen bzw den um 02:22 auch wenn die Zugbindung aufgehoben ist?

Danke im Vorraus..

...zum Beitrag

Nachkorrektur Verschlechterung?

Kann sich eine Klausur in der Uni durch eine nachkorrektur verschlechtern? Ich hätte jetzt knapp eine 4,0 jedoch war ich der Meinung, dass einige Aufgaben unfair gewertet wurden und hierbei eine 3,7 drinnen wäre, wobei sie zur nachkorrektur geschickt wurde, kann man sich dadurch verschlechtern? Da die ersten beiden Korrekturen bei der 4,0 blieben, habe ich jetzt auf einen dritten bestanden.

...zum Beitrag

Reizreaktionskette? Torwart?

Hallo, ich hab eine Aufgabe aufbekommen wobei ich eine Reizreaktionskette zu einem Torwart aufstellen soll. Welche Prozesse müssen im Körper ablaufen um ein erfolgreiche Torverhinderung zu ermöglichen?

...zum Beitrag

Typ 2 Sprache die Pumping Lemma erfüllt?

Das Pumping Lemma ist hier erfüllt. Es soll sich hier um eine kontrexfreie Sprache vom Typ 2 handeln. Woran erkenn ich dies?

...zum Beitrag

Pumping Lemma kontextfreie Sprachen Typ2?

m >= 1, d. h. das kürzeste Wort in der Sprache hat die Länge 3m bzw.

|z| = 3n > = n

D. h. wenn mein n = 1 ist, dann hat mein Wort die Länge 3.

Jetzt muss ich eine Aufteilung von |vwx| wählen, dass gilt |vwx| <= n

und dann beim pumpen das Wort Teil meiner Sprache bleibt.

|vwx| <= 1 geht nicht. Macht keinen Sinn, ich muss ja a und b und c einzeln pumpen. a,b,c hat mindestens die Länge 3. Somit macht n = 1 keinen Sinn. n = 2 geht auch nicht. Ich muss mindestens n = 3 wählen. Also z = aaabbbccc nun muss ich |vwx| <= 3 wählen, d. h. ich kann nur 2 von den 3 Symbolen (einzeln) pumpen. ab und c oder a und bc , das macht keinen Sinn.

Fazit:

Man müsste a b c separat (einzeln) pumpen, damit das erzeugte Wort Teil meiner Sprache bleibt, dies ist hier aber nicht möglich egal wie man v und x wählt.

Langt dies als Begründung, oder wie argumentiert man hier am besten?

|z| = 2n >=n das kürzeste Wort hat die Länge 2 somit hat auch mein n mindestens die Länge 2.

Wieder muss ich |vwx| so wählen, dass gilt |vwx| <n und beim pumpen dann das Wort Teil meiner Sprache bleibt.

Wie wähle ich nun hier u, v, w, x, y?

...zum Beitrag

Warum lässt sich jedes Problem in P auf jedes andere Problem in P reduzieren und was heißt das?

Ich habe gerade gelernt, dass man jedes Entscheidungsproblem L1 über Σ in P auf jedes andere Problem L2 über Σ aus P reduzieren kann. Mit hat es hier "die Kette rausgehauen":

Eine Reduktion ist ja eine berechenbare Abbildung

jetzt könnte ich festlegen Σ = Natürliche Zahlen von 1 bis 1 Million

L1 = {w ∈ Σ | w ist prim)

L2 = {w ∈ Σ | w ist gerade)

und definieren:

f(w) = 6 wenn w prim

f(w) = 7 wenn w nicht prim

Dies erfüllt genau die obige Definition einer Reduktion.

Nur welchen Sinn macht es, hier von einer "Reduktion" zu sprechen, denn ich habe ja den Primtest auf eine Zahl nicht auf den Test auf Geradheit einer Zahl zurückgeführt.

Ich hätte intuitiv etwas als Reduktion bezeichnet, wenn ich durch die Entscheidung L2 auch L1 entscheiden kann. Hier liegt aber aus meiner Laiensicht ein "fauler Zauber" vor, denn in der Abbildungsvorschrift f ist eigentlich schon enthalten, dass ich dafür schon die Entscheidung auf Prim durchführen, also L1 lösen muss. Es "hört sich aber so an", als könnte man nun einen Primtest (der ja, obwohl in P liegend, relativ komplex ist) auf etwas "reduzieren", wo man nur auf Geradheit prüft (was ja von der Komplexität nicht vergleichbar ist). Jedenfalls ist das nicht im Sinne der Erfindung eines "funktionierenden" Algorithmus für L1, den ich zu lösen vermag, indem ich L2 löse.

Ich hoffe, ich habe mich in meiner Notation verständlich ausgedrückt und man weiß, was ich meine...(bin kein Informatiker, daher bitte Milde walten lassen ;-)

Habe ich eine falsche Vorstellung von einer Reduktion oder ist das einfach so?

...zum Beitrag

Informatik Komplexitätsfunktion?

for i := 0; i < len(n); i++ { // O(n)

for j := 0; j < len(n); j++ { // O(n)

if x >= 30 { // O(1)

for k := 0; k < len(n); k++ { // O(n)

value = value + 10 // O(1)

}

} else {

value = value + 2 // O(1)

}

ich hab den code und soll die Komplexitätsfunktion angeben ansich komm ich klar nur hab ein ein problem bzw ich stimme nicht mit chat gpt ein er sagt nähmlich=

O(n)(O(n)(O(1)+O(n)O(1)+O(1)))+O(1)

ich verstehe aber das erste + net ich hätte jetzt mal gesagt

also: O(n)(O(n)(O(1)*(O(n)O(1))+O(1)))+O(1)

...zum Beitrag

Kann man eine Turing-Maschine kaufen?

...zum Beitrag

Pumping Lemma Typ 3 überprüfen, wie n wählen?

Wie wähle ich bei den drei Sprachen am besten mein n für die Vorgabe

|x| >= n sein?

Bei c kürzestes Wort mit k = 0 ist epsilon. Mit Pumpen 2k Länge

Demensprechend würde ich mein n = 2k sätzen

a) und b) wie setze ich hier mein n? Ich will ja "generell" zeigen, das sich das PL erfüllt für alle v^i, wenn ich Pumpe. Oder eben nicht erfüllt, und damit die Sprache nicht regulär ist.

...zum Beitrag

Pumping Lemma reguläre Sprache?

ich soll mit Pumping-Lemma beweisen, dass die folgende Sprache nicht regulär ist: L={0^m1^n|n!=m}

ist mein ansatz richtig so? :

sei n element N,

sei k >= 1 und setze w = 0^n1^(n-k) mit w element L und |w|>=n,

zerlegung w = xyz mit |xy|<=n und y nicht leer,

dann xy= 0^p mit p<=n, y=0^k mit k>=1,

setze i=0 --> xy^0z=0^(n-k)1^(n-k)

somit ist xy^0z nicht in L und L nicht regulär

...zum Beitrag

Reguläre Ausdrücke?

Alphabet sigma = {0, 1}

Für d) L4 beinhaltet doch alle Wörter über sigma oder?

Für c) Die Wörter in L2 werden ja aus dreier Blöcke gebildet (sigma^3)

Wenn L3= sigma* \ L2 gilt sollte doch Wörter der Länge != 3n , die 101 als Teilwort enthalten, auch in L3 liegen. Dann gilt aber L3 = L2^c. Welcher ist richtig?

...zum Beitrag

Wortproblem Typ 1 ist NP-schwer kann ma es per Turing Maschine berechnen?

Das Wortproblem Typ 1 für kontextsensitive Sprachen ist entscheidbar.

Bzgl. der Komplexität ist es NP-schwierig.

O(k^n) Komplexität

Laut der Folie kann man nicht zeigen, dass es in NP liegt. Es ist NP-schwierig.

Nun meine Frage: Ist das Wortproblem Typ 1 Turing-Maschinen berechenbar? Ja oder Nein, wenn es wie hier angegeben NP-schwierig ist?
Es gilt P Teilmenge von NP.

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen