Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung | Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws15 [07.04.2019 13:22] – Nico Hambauer | pruefungen:bachelor:aud:loesungws15 [07.04.2019 13:28] – Nico Hambauer | ||
---|---|---|---|
Zeile 23: | Zeile 23: | ||
* "löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.": | * "löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.": | ||
- | ** g) ** 2 (Meiner Meinung nach: 3 und 4 sind richtig!) | + | ** g) ** 2 (achtung, falsch: Folgendes beachten) |
* unsicher | * unsicher | ||
* Ich denke 4 müsste stimmen | * Ich denke 4 müsste stimmen | ||
* Bei 2 bin ich mir auch unsicher, da das eigentlich die Definition des Theta-Kalküls ist (auch ein Landau-Symbol), | * Bei 2 bin ich mir auch unsicher, da das eigentlich die Definition des Theta-Kalküls ist (auch ein Landau-Symbol), | ||
+ | * Meiner Meinung nach: 3 und 4 sind richtig! Da 1 die definition von gross Omega und 2 von gross Theta ist, wobei die 3 und 4 mit den Rechenregeln des O Kalkuels, bzw 3 bei genauerem Nachdenken ueber den Logarithmus richtig sein muessen. T(n) = T(0.666 * n) = T(c * n) = T(n) + w mit c als Konstante > 1 ist. | ||
==== Aufgabe 2 Streuspeicherung ==== | ==== Aufgabe 2 Streuspeicherung ==== |