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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungss11 [21.03.2018 10:23] – Evren | pruefungen: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, | ||
**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. | ||
+ | </ | ||
+ | |||
+ | einfacher: | ||
+ | < | ||
+ | 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) | ||
+ | -> wahr, weil k > 0 <=> k ≥ 1, da k vom Datentyp " | ||
+ | |||
+ | fertig | ||
</ | </ | ||