Informatik II - Datenstrukturen und Algorithmen

at Westfälische Wilhelms-Universität Münster

Join course
317
Discussion
Documents
Flashcards
Weiß jemand, ab wie vielen Punkten die Bestehensgrenze lag?
Ich glaube 50 Punkte
Hat jemand die bisherigen Termine im Info2 Rep mitgeschrieben und könnte die Sachen hochladen? Hab leider gerade erst mitbekommen, dass das angeboten wird
Hat jemand den Einschreibeschlüssel für das aktuelle Repetitorium?
RepInfo2-2019
Was habt ihr in der Klausur?
1,0
Ergebnisse sind online!!!
View 5 more comments
Geht mir genauso
Danke @Lippenstift wusste gar nicht, dass sowas öffentlich einsehbar ist.
Gibt es schon neue Infos zur Klausur?
wie fandet ihr die Klausur?
View 20 more comments
Die WI Fachschaft hat sich vorhin bei mir zurückgemeldet, es bringt also durchaus etwas sich dort zu melden und Argumente zu nennen (bspw. die Nicole oben genannt hat). fs.wi@wiwi.uni-muenster.de ist die Mail-Adresse:)
Danke für die Adresse Schokohase, habe ebenfalls eine Mail an die Fachschaft geschrieben.
Meint ihr perfect Hashing sollte man drauf haben? Wie siehts aus mit dem optimalen Suchbaum?
View 6 more comments
Naja, ging so. 7b hab ich von der Zeit her nicht geschafft und sonst weiß ich auch, dass ich einige Fehler gemacht habe (z.B. bei Aufgabe 6 einige Bereichsabprüfungen vergessen). Fand sie im Vergleich zu Altklausuren recht schwer.
Mich würde auch mal interessieren ob Aufgabe 7 überhaupt jemand vollständig geschafft hat (also a und b), bzw. jemand, der die Aufgabenreihenfolge eingehalten hat
f1 < f2 < f5 < f4 < f3 < f6 ?
View 6 more comments
f5(n) = n*sqrt(n/2) = sqrt(n^2)*sqrt(n/2) = sqrt(n^2 * n/2) = (n^2 * n/2)^(1/2) = ((n^3)/2)^(1/2). Das ist n^(3/2)/sqrt(2), also in O(n^(3/2)). Einfacher sieht man f5 < f2 aber einfach durch n*sqrt(n) < n*n
Genau das
Lösung?: f9 < f5 < f8 < f10 < f7 < f3 < f1 < f2 < f4 < f6
View 4 more comments
f9 < f5 < f8 < f7 < f10 < f3 < f1 < f2 < f4 < f6 muss es nicht so heißen? Weil bei f7 ist doch ein plus das bedeutet doch 2log2n ist doch kleiner als 2^logn
f7 und f10 sind gleich. Das 2log(n) wächst deutlich langsamer als das n^(1/3), weshalb man das einfach weglassen kann. Formal zeigen kann man das so: n^(1/3)+2log2(n) < n^(1/3)+n^(1/3) = 2*n^(1/3) in O(n^(1/3)) für große n. f10 ist ebenfalls in O(n^(1/3)), weil 2^(log8(n)) = 2^(log2(n) / log2(8)) = (2^(log2(n)))^(1/log2(8)) = n^(1/log2(8)) = n^(1/3)
f1 < f2 < f5 < f4 < f9 < f8 < f7 < f3 < f6 ?
Habe es auch so
f4 < f1 < f3 < f2 < f6 < f7 < f5 ? wobei f1 = f3
Hat jemand die Lösung zu Aufgabe 28 Übungsblatt 10?
Zum Herausfinden der besten N Customer in O(n) hat man mehrere mögliche Ansätze: - HeapSort. Man kann den Heap in O(n) aufbauen. Man muss nun nur N = log n Elemente aus dem Heap entnehmen. Das geht in N*log n = (log n)*(log n) < n (wenn man alle herausnehmen wollte, dann wäre es n*log n). Die besten N Customer sind dann am Ende des Arrays. - RadixSort. Kann ein Integer-Array aufgrund des beschränkten Wertebereiches von Integern in O(n) sortieren. Das herausnehmen der besten N aus dem Arraygeht dann auch noch in O(N) mit N <= n. Beide Ansätze waren richtig und wahrscheinlich auch gewollt, auch wenn die eigentlich nicht ganz schön sind. Die HeapSort-Variante ist nur in O(n), wenn N entsprechend klein ist, und RadixSort versteckt allgemein alles hinter Konstanten. Wenn man beispielwesie RadixSort bez. der Binärdarstellung macht, dann erhält man 32*n als Laufzeit, also n*log_2(2^32). Ein besserer Ansatz (für den wir nach der VL nicht die Algorithmen kennen) wäre ein Selection-Algorithmus wie z.B. QuickSelect zu nehmen um das N-t größte Element zu finden. floorlog2 ist mit der Binärdarstellung leicht zu lösen, denn floorlog2 ist die Position des höchsten Bits, das 1 ist. Beispielweise, wenn x = 00101001011 (binär) = 331 ist, ist log2(x) = ca. 8.37 (nach Taschenrechner), und 8 ist ebenfalls die Position der höchsten 1 (von hinten zählen, bei 0 anfangen). Allgemein betrachte x = 2^n. x in Binärdarstellung ist eine 1 an Position n und sonst 0, und ebenfalls log2(x) = log2(2^n) = n. Daran sieht man, dass das für alle x gilt.
Danke!
War jemand in der Besprechung zur Klausur und kann teilen, was angesprochen oder hervorgehoben wurde?
guck doch mal weiter unten
Hat Kuchen dieses Semester etwas zum Master-Theorem gesagt? Ich erinnere mich daran, dass dieses Thema letztes SS relativ ausführlich bearbeitet wurde.
View 4 more comments
OK, danke! Das wusste ich nicht, sorry. Ja, finde auch, dass es um einiges entspannter als Induktion ist
@Anonymer Regenschirm was wurde sonst noch in der Besprechung zur Klausur angesprochen? Ich war leider nicht da.
Hallo, war heute jemand in der Vorlesung und kann mir sagen, ob Kuchen noch etwas zur Klausur gesagt hat?
View 1 more comment
"Aufgabe zur Komplexität" Ist er darauf etwas näher eingegangen? Jemand nen Tipp, wie man sich darauf vorbereiten kann?
Schau Dir am besten mal die Altklausuren an. Da ist ein Aufgabenformat, dass sehr verdächtig ist, auch dieses Mal in abgewandelter Form aufzutauchen.
Hat jemand die Lösungen zu den Altklausuren von SoSe2014, SoSe2011 oder WS2011/12 ?
Hat das jemand schon gemacht
Was bedeuten hier die "m" und "n" bei dem Aufwand?
n: Anzahl Knoten m: Anzahl Kanten
Hat Kuchen schon gesagt, ob irgendwelche Themenbereiche eventuell nicht klausurrelevant sind?
Alles ist klausurrelevant auch Kapitel 7
Wurde bereits gesagt wv Tutorien-Zettel es insgesamt geben wird und ob der aktuelle evtl. schon der letzte ist? :)
ich meine, dass ist der letzte :)
Kann man aus avl bäumen die wurzel löschen?
Ja. Bei Kuchen rückt idR der größte Knoten aus dem linken Teilbaum an die Stelle der Wurzel.
Hat bereits jemand korrekte Lösungen zu den Aufgaben und wäre bereit, diese hochzuladen ? Danke :)
Wie kann bei dem quadratischen Sondieren das Einfügen nicht funktionieren obwohl noch Plätze frei sind? Das der modulo Teiler eine Primzahl sein muss ist doch vorgegeben oder ?
Kennt jemand den Einschreibeschlüssel für den LearnWeb Kurs "Repetitorium Informatik II SS17" ?
Kann mir jemand den optimalen Suchbaum erklären? Vor allem wie die Werte auf Folie 96 zustande kommen?
Hat vielleicht jemand einen Ansatz zur Aufgabe 5 des aktuellen Aufgabenblattes?
View 3 more comments
Man deckt den größten Weg ab wenn man nur in eine Richtung geht. Darum macht rein logisch ein Richtungswechsel kein Sinn.
Aber du musst dir vorstellen, dass die Mauer keinen Kreis darstellt. Die Mauer geht unendlich weit nach rechts und unendlich weit nach links und du weißt nicht ob sich das Tor links oder rechts befindet. Aus diesem Grund kann es sein, wenn du deine Richtung nicht wechselst, unendlich weit in die falsche Richtung gehst. Aus diesem Grund musst du deine Richtung wechseln
Hat vielleicht jemand den Einschreibeschlüssel für dieses Semester und könnte mir den schicken?
View 1 more comment
Gibts keinen glaube ich
Nein es gibt keinen Einschreibeschlüssel. Du kannst im Learnweb einfach nach dem Kurs suchen und beitreten https://sso.uni-muenster.de/LearnWeb/learnweb2/course/view.php?id=36725
Habt ihr irgendwelche Bücher für Informatik gekauft? Oder wie lernt ihr? ich persönlich finde die Folien von Kuchen nicht so übersichtlich und schwer zu verstehen
Bis wo ist Kuchen am Donnerstag gekommen ?
View 2 more comments
Kapitel 2
Danke!
hat jemand das info 2 skript von kuchen?
View 2 more comments
Macht Hinrichs das nich ?
Hast du das Skript jetz eig und wann hat der Kuchen das letze mal info2 gemacht 2015?
Musterlösungen gab es keine oder ? habe so 89% in Übungen aber da wo mir Punkte fehlen würde ich doch gerne andere Lösungen haben :/
View 2 more comments
das erste bewertete Blatt? Oder das mit den beweisen? edit: Okay, das Blatt mit den Beweisen habe ich auch nicht. :/
Ja das mit den Beweisen außer Induktion habe ich bei den anderen nur Teilpunkte
Meint ihr es kommt ne richtige Programmieraufgabe ? Im ersten Versuch gab es ja nur Pseudocode
gab es eig ne Probeklausur?
View 1 more comment
wenn Jemand in Repetitorium war,könnte er oder sie die Lösungen netterweise veröffentlichen?
ja wäre echt sehr nice konnte leider nicht zum REP
Weiß jemand mit wechem Notenschlüssel die Klausur bewertet wird? Wie viel Prozent braucht man, um bestanden zu haben?
View 5 more comments
Und wie ist es gelaufen?
Erwartet schlecht, aber immerhin 4,0
(a,b)-Bäume sind nicht klausurrelevant!
Woher nimmst du diese Information? Kann mich nicht daran erinnern, dass er dies gesagt hat
Zitat Learnweb: "(28.06.2018): Die Folie 6.59-6.75 ((a,b)-Bäume) wurden nicht besprochen und sind daher auch für die Klausur nicht relevant."
Hat jemand hier evtl eine recht hohe Punktzahl bei den Tutorien bekommen?
momentan sieht bei uns schlecht aus
Kann mir bitte jemand den Einschreibeschlüssel verraten?
invarianten