Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung
Vorherige Überarbeitung
pruefungen:bachelor:aud:loesungss11 [21.03.2018 10:23] Evrenpruefungen:bachelor:aud:loesungss11 [20.06.2020 12:12] (aktuell) BierBaron69
Zeile 37: Zeile 37:
 Ein erster Eintrag von Element x lässt sich in einer sortierten Reihung mittels binärer Suche in O(log n) finden. \\ Ein erster Eintrag von Element x lässt sich in einer sortierten Reihung mittels binärer Suche in O(log n) finden. \\
 Um zu prüfen, ob (wie viele ist irrelevant!) es noch weitere Einträge von Element x gibt, muss man nur das Element rechts und links vom aktuellen betrachtet, was in O(1) geht. Um zu prüfen, ob (wie viele ist irrelevant!) es noch weitere Einträge von Element x gibt, muss man nur das Element rechts und links vom aktuellen betrachtet, was in O(1) geht.
 +
 +Anmerkung:
 +Es geht ja um den worst case. Ich denke, man kann ein Szenario konstruieren, in dem die Laufzeit O(n) beträgt. Wenn z.B. die gesamte Reihung nur aus diesem Element besteht, muss man nach Auffinden des ersten Eintrags, die gesamte Liste durchgehen, um alle Vorkommen zu finden und zu zählen.
  
 **i)** 2. Antwort ist richtig **i)** 2. Antwort ist richtig
Zeile 477: Zeile 480:
 Sind (p ≠ 2^(n - k - 1)) und (k ≤ 0) beide nicht erfüllt, dann muss (p = 2^(n - k - 1) ∧ k > 1) erfüllt sein. Sind (p ≠ 2^(n - k - 1)) und (k ≤ 0) beide nicht erfüllt, dann muss (p = 2^(n - k - 1) ∧ k > 1) erfüllt sein.
 Die Invariante ist somit gültig. Die Invariante ist somit gültig.
 +</code>
 +
 +einfacher:
 +<code>
 +Zu zeigen: (I ∧ b) => wp(B, I)
 +
 +I: p = 2^(n - k - 1) ∧ k ≥ 0
 +b: (k > 0)
 +B: "p *= 2; k--" <=> "p = p * 2; k = k - 1;"
 +
 +(I ∧ b):
 +    p = 2^(n - k - 1) ∧ k ≥ 0 ∧ k > 0
 +    <=> p = 2^(n - k - 1) ∧ k > 0      (weil: (k ≥ 0 ∧ k > 0) <=> (k > 0))
 +
 +wp(B, I):
 +    wp("p = p * 2; k = k - 1;", p = 2^(n - k - 1) ∧ k ≥ 0)
 +    <=> wp("p = p * 2;", p = 2^(n - (k - 1) - 1) ∧ k - 1 ≥ 0)
 +    <=> wp("p = p * 2;", p = 2^(n - k) ∧ k ≥ 1)
 +    <=> wp(" ", p * 2 = 2^(n - k) ∧ k ≥ 1)
 +    <=> p * 2 = 2^(n - k) ∧ k ≥ 1
 +    <=> p = (1/2) * 2^(n - k) ∧ k ≥ 1
 +    <=> p = 2^(n - k) * (1/2) ∧ k ≥ 1
 +    <=> p = 2^(n - k) * 2^(-1) ∧ k ≥ 1      (weil: (1/2) = 2^(-1))
 +    <=> p = 2^(n - k - 1) ∧ k ≥ 1      (weil: 2^(n - k) * 2^(-1) = 2^(n - k - 1))
 +
 +(I ∧ b) => wp(B, I):
 +    p = (2^(n - k - 1) ∧ k > 0)   =>   (p = 2^(n - k - 1) ∧ k ≥ 1)
 +      -> wahr, weil k > 0 <=> k ≥ 1, da k vom Datentyp "long" und damit ganzzahlig (..., -2, -1, 0, 1, 2, ...)
 +
 +fertig
 </code> </code>