Fachrat Informatik - Forum

Quoted from "Michael."

Hallo!

Wäre es möglich, dass mir jemand die Lösungen für Hausübungen 6 und 7 zukommen lässt?

Hallo,

hast du die restlichen Lösungen ? Könntest du mir die eventuell schicken ? Hab ein paar probleme bei einigen aufgaben...

Hat also keiner die Übungsmitschrift ?

Ansonsten mail an die Übungsleiter oder Frage hier posten!

Mir fehlt leider noch die Lösung zu Übung 5, Aufgabe 2c), da sollte man zu einem gegebenen Baum



die Postordnung mit Verzweigungsgrad angeben. Ich habe da folgendes:



Ist das korrekt so? Bin mir unsicher.

Ausserdem fehlt mir bei Übung 6 die Musterlösung zu den Heaps, die Huffmann-Codes habe ich selbst nachgearbeitet.
Hat das wer?

HAVE PHUN!

Jo das was du bei 2c gemacht hast, kommt hin

Hab ne Frage zu einer Folie.
Folien Seite 76.

LISTE als Feld: Pseudocode (2/3)

next (p):
(1) wenn p > 0 oder p < letztes
(2) gib NULL zurück
(3) gib p+1 zurück

Ist das so korrekt ? Oder müssen Zeile 2 und 3 vertauscht werden ?

Es muss vertauscht werden...

wenn p<0 oder p>=last)
return null
sonst return p+1

So steht es im Skript... aber eben dann als Pseudocode

Einige Fragen haben sich beim gemeinsamen Lernen noch ergeben:

Allgemeine Fragen:
- werden wir Pseudo-Code schreiben müssen, oder lediglich verstehen/erklären müssen?
- müssen wir progammieren, oder ist das eine reine Schreib-Klausur so wie die Probeklausur?
- wie sucht man in einem Heap? Der ist ja monoton von oben nach unten sortiert, aber scheinbar nicht allgemein, oder? Also links und rechts in den Teilbäumen können unterschiedlich grosse Elemente stehen. Wie finde ich ein Element in der Baum-Ansicht? Oder sucht man rein in der Array-Ansicht?

Fragen zur Probeklausur:
- Blatt 2 (Stack): Warum haben wir das nicht bearbeitet? In der Übung haben wir es einfach übersprungen. Kommt der ADT Stack nicht dran? In der Musterlösung stehen ja alle Lösungen für Blatt 2...
- Blatt 4 (Heaps): Was ist mit "die k < n größten" gemeint? Alle Elemente ausser der Wurzel? Also alles was unten dranhängt? Was bedeutet in der Musterlösung "Entferne k mal die Wurzel und rekonstruiere je den Heap (per SiftUp). Das dauert K.O(logn) = O(k)" ... was ist K.O, soll das "k * O(log n)" sein? ... Wir können uns halt auf die Lösung keinen rechten Reim bilden...

HAVE PHUN!

Hi, na dann beantworte ich die doch mal etwas

Allgemeine Fragen:
- werden wir Pseudo-Code schreiben müssen, oder lediglich verstehen/erklären müssen?
Ihr müsst wissen wie man Pseudocode schreibt und was er bedeutet! Also ihr solltet auch in der Lage sein Pseudocode zu verfassen.

- müssen wir progammieren, oder ist das eine reine Schreib-Klausur so wie die Probeklausur?
Was heißt Programmieren? Wenn dann nur in Pseudocode!

- wie sucht man in einem Heap? Der ist ja monoton von oben nach unten sortiert, aber scheinbar nicht allgemein, oder? Also links und rechts in den Teilbäumen können unterschiedlich grosse Elemente stehen. Wie finde ich ein Element in der Baum-Ansicht? Oder sucht man rein in der Array-Ansicht?
Es stimmt schon, das ein Heap zum Suchen nicht geeignet ist, da man nicht weiß, auf welcher Seite das jeweilige Element zu finden ist. Dafür gibt es ja Suchbäume. Also das Suchen in einem Heap wird wohl ehr keine Aufgabe sein!


Fragen zur Probeklausur:
- Blatt 2 (Stack): Warum haben wir das nicht bearbeitet? In der Übung haben wir es einfach übersprungen. Kommt der ADT Stack nicht dran? In der Musterlösung stehen ja alle Lösungen für Blatt 2...
Dazu kann ich nicht viel sagen, bei mir haben wir das durchgesprochen, aber da es ja ehr Sachen waren die man auswendig können sollte, wurde es vielleicht deswegen nicht besprochen.
Also was ein Stack ist und so sollte man wissen, genauso wie alle anderen ADTs die dran kamen.

- Blatt 4 (Heaps): Was ist mit "die k < n größten" gemeint? Alle Elemente ausser der Wurzel? Also alles was unten dranhängt? Was bedeutet in der Musterlösung "Entferne k mal die Wurzel und rekonstruiere je den Heap (per SiftUp). Das dauert K.O(logn) = O(k)" ... was ist K.O, soll das "k * O(log n)" sein? ... Wir können uns halt auf die Lösung keinen rechten Reim bilden...
Die Aufgabe ist mies, das gebe ich zu. Hier sind die k größten Elemente gesucht, dazu einen Maxheap erzeugen und dann die Wurzel k-mal, also die k größten Elemente, löschen. Die Laufzeiten stimmen hier nicht wirklich, das Löschen und SiftUp dauert dann k*O(log n) also O(k*log n). So eine besch... gestellte Aufgabe wird nicht drankommen. Da haben wir auch lange drangesessen um das zu verstehen.

Hoffe das hilft weiter! Ansonsten könnt ihr auch gern noch mal nen Termin ausmachen um eure Fragen zu stellen!

Ist es möglich dass sich bei Aufgabe 5 in der Probeklausur ein Fehler eingeschlichen hat und in Aufgabenteil b) die Anzahl der Tabellenzugriffe für den Schlüssel "mimas" 6 statt 5 beträgt? Dann würde sich ein Duchschnittswert von 3,5 einstellen.

Hat das jemand auch so, oder habe ich das Prinzip noch nicht ganz erfasst?

Danke.

Richtig erkannt, der Fehler wurde leider nicht behoben!

Falls es für jemanden nochmal hilfreich sein sollte, die ADTs aus den Übungen (und die meisten aus den Vorlesungen) nochmal vor sich zu sehen und vielleicht damit rumspielen und ausprobieren zu können, habe ich mal meine Version derselbigen in Groovy gecodet und lade die anbei hoch.
Da sind fast alle Algorithmen aus den Stunden und Hausübungen drin, die sollten eigentlich auch korrekt sein, die ADTs habe ich nicht alle 100% getestet, sondern das mehr für mich geschrieben.

Achja ... Groovy gibts bei codehaus (-> groovy), ist eine ziemlich geniale Sprache, die auf Java aufsetzt (deshalb fand ich sie ideal, um die ADTs eleganter als im Skript umzusetzen), und funktionale Paradigmen und insbesondere Methoden erster Ordnung mitbringt. An den Stellen, wo man ADTs erweitern sollte, habe ich das lokal per Categories (kommt aus Smalltalk) getan, lohnt sich ebenfalls, sich das anzuschauen.
Der Code sollte eigentlich halbwegs lesbar sein ;-)

Verwendung auf eigene Gefahr

Viel Spaß

P.s. Wenn ihr mit der groovyConsole arbeitet, dann ladet zB eine A0*/Stundenuebung**.groovy in das Programm und fügt den Ordner darüber mit zum Path dazu, das macht er nicht automatisch ...

Und hier ist auch schon der nächste Schwung Fragen (danke für die Beantwortung des Ersten )

Skript:

- S.16: Wie läuft die Umformung von

Da haben wir uns leider echt die Zähne ausgebissen :-/

- S.46: Oben ist eine sequentielle Baumdarstellung ... dargestellt.

Soll aus dieser Darstellung der binäre Baum unten auf S.46 werden? Der sieht aber seltsam aus, in der Sequenz steht dass Knoten 3 ein Blatt sei, aber unten im Baum hängt die 4 da so mehr oder weniger dran. Die 4 sieht aus wie der rechte Nachbar von 3 aber nur weil der Strich nach oben rechts neben die 3 gesetzt wurde. Ist das korrekt so?

- S.46: Unten ist eine Formel angegeben ... woher kommt die? Hat die irgendwas mit der Stirlingsschen Approximations-Formel von S. 39 zu tun?

- S.39: Stirlingsche Approximation - was bedeutet das O(1/n)?

Allgemein:
- Ist ein externer Knoten ein Blatt?

- Wie man einen geordneten Baum in einen binären Baum umwandelt wissen wir ja, aber wie geht die Umwandlung von einem binären in einen geordneten? Oder geht die garnicht? Wir haben in der Stundenübung mal soetwas gesagt, weil eine rechte Kante eine doppelte Wurzel wäre (oder ähnlich), aber scheinbar haben wir das falsch verstanden. Oder?

- Wenn ich eine Hash-Funktion h habe, die da lautet: 3 - k mod 3 so läuft ihr möglicher Wertebereich von 1-3 ... gibt es eine Möglichkeit das zu berechnen oder gilt hier nur "scharfes Hinsehen", ich habe immer selbst die Zahlen eingesetzt, aber dieses Vorgehen ist nicht sehr akkurat.

- Bei den ADT's wird ab und an mal gefragt welche Laufzeit die haben. Wie ist das konkret gemeint? Soll man da die Laufzeit rein des ADT's angeben, oder der einzelnen Operationen? Denn von den einzelnen Operationen sind es recht viele Laufzeitangaben.

Danke im Vorraus.

HAVE PHUN!

Erstmal zum allgemeinen, den rest schau ich mir dann noch mal später an:


- Ist ein externer Knoten ein Blatt?
Ein externer Knoten ist ein Blatt. Meistens haben wir die nicht mitgezeichnet. Sind aber im Skript glaube ich drin.

- Wie man einen geordneten Baum in einen binären Baum umwandelt wissen wir ja, aber wie geht die Umwandlung von einem binären in einen geordneten? Oder geht die garnicht? Wir haben in der Stundenübung mal soetwas gesagt, weil eine rechte Kante eine doppelte Wurzel wäre (oder ähnlich), aber scheinbar haben wir das falsch verstanden. Oder?
Einen binären Baum in einen geordneten Baum umzuwandeln? Das haben wir gemacht? Kann ich mich garnicht erinnern. Macht aber für mich gerade keinen Sinn. da denk ich noch mal drüber nach.


- Wenn ich eine Hash-Funktion h habe, die da lautet: 3 - k mod 3 so läuft ihr möglicher Wertebereich von 1-3 ... gibt es eine Möglichkeit das zu berechnen oder gilt hier nur "scharfes Hinsehen", ich habe immer selbst die Zahlen eingesetzt, aber dieses Vorgehen ist nicht sehr akkurat.
Wenn ich mod 3 rechne dann ergibt sich daraus nur Zahlen zwischen 0 und 2. Denn wenn ich irgendeine Zahl mod 3 rechne, dann ist das minimum 0, also die Zahl hat den teiler 3 oder maximum 2 dann fehlt ein punkt zum nächsten Teiler. Und wenn du jetzt 3- k mod 3 hast, dann kannst du minimum 0 abziehen und maximum 2. So kommst du auf den Bereich 1-3.

- Bei den ADT's wird ab und an mal gefragt welche Laufzeit die haben. Wie ist das konkret gemeint? Soll man da die Laufzeit rein des ADT's angeben, oder der einzelnen Operationen? Denn von den einzelnen Operationen sind es recht viele Laufzeitangaben.
Hier sind wirklich die Laufzeiten der einzelnen Operationen gefragt. Worst case sollte reichen, wenn es mehrere gibt für eine Operation!

So der Rest dann später.... Versprochen!

Danke, mittlerweile habe ich das mit den Wertebereichen von mod verstanden (k mod 3 z.b. geht immer von {0,1,2} und 3 - {0,1,2} geht halt von {3,2,1}), bei den Summen allerdings hänge ich noch. Ich schätze da verstehe ich noch was mit den Summenrechenregeln nich.

Dann bin ich die Laufzeiten der Operationen lernen.

Der grösste Schwung der Fragen kommt bestimmt erst nach der Klausur

HAVE PHUN!

Also die Nachbarbit und Blattbit- Darstellung und der Baum unten passen zusammen. Und zwar ergibt die darstellung einen geordneten Baum und der Baum unten stellt die Umwandlung in einen Binären baum dar.

Also was die Stirlingsche Approximation angeht. Puh, dafür ist es gerade zu spät. dazu müsste ich mich jetzt noch ganz genau in das Skript einlesen. Ich vermute das das O(1/n) mit dem wacsen der Bäume in exponentieller Zeit zu tun hat.
Wo genau die Formel auf Seite 46 herkommt hab ich auch nicht ausfindig machen können! Ich vermute auch das es mit den Stirlingsche Approximation was zu tun hat, aber da muss ich leider passen.

An den Summen sind wir dran. Da gibt es noch ne ausführliche Erläuterung.

Tut mir leid da sich da nicht weiterhelfen kann.

Also die Summe ist etwas verwirrend auf folie 16. Besonders der erste Schritt

Aber die erste Summe sollte kein Problem darstellen.


So nun hab ich irgendwie deren 2. Schritt übersprungen .

Man hat jetzt den Term o - u + 1, der von 1 bis N-u+1 läuft, da o von u bis N läuft. Ich hab da einfach diesen Term (o-u+1) durch nen Platzhalter ersetzt...




x ist der angesprochene Term von ebend und die Grenzen der Summe musst ich anpassen. Wer nun genau hinsieht sieht auch schon dass die obere Grenze der 2. Summe von 1 bis N geht (wie unser u) .. nur noch "falsch rum". Also kann man auch schreiben



(Bei mir ist das x nun das o aus dem Skript). Ja die 2. Form hab ich jetzt nicht benutzt, aber die könnte man jetzt durch lästiges um substituieren auch erzeugen. Jedoch hab ich das irgendwie nicht sehr formell bis jetzt hinbekommen, aber vielleicht reicht das ja auch so (ja die 2. Form da in der Mitte ist schon richtig! Nur der Weg ist noch unklar )