Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Fragen aller Art
Hallo,
da mir waehrend der Vorbereitung auf die Klausur ständig kleine Fragen aufkommen und ich nicht wegen jeder einen neuen Thread eroeffnen moechte, stelle ich sie einfach mal hier.
Im Moment verstehe ich nicht, ob bei der Menge als unsortierte verkettete Liste die Elemente vorne oder hinten angehaengt werden. Denn in der Vorlesung 11 steht:
- auf 11-8 , dass die Elemente an die verkettete Liste angehaengt werden, also hinten an die Liste. (Interface)
- auf 11-44, dass neue Elemente vorne an die Liste angefuegt werden. (Liste als Menge)
- auf 11-46:
public boolean add(E elem) {
if (contains(elem))
return false;
return list.add(elem);
}, wobei list eine LinkedList ist, also müssten die Elemente doch hinten und nicht vorne angefuegt werden oder?
11-8 ist so auf jeden Fall richtig, die anderen beiden Folien widersprechen sich, da hast du recht. Wichtiger ist aber eigentlich, dass du bei Mengen generell keinen Indexzugriff hast, eine Reihenfolge der Elemente gibt es also nicht. Auch die Reihenfolge, in der Elemente aus dem Iterator rausfallen, ist nicht spezifiziert und dürfte sich bei verschiedenen Implementierungen ändern. Es ist also letztlich dir überlassen, ob du deine Menge mit addFirst() oder addLast() implementierst, das ist einfach ein Beispiel, wie man es machen könnte und nichts was man auswendig lernen soll. (Normalerweise ist ja ein HashSet / die später besprochene HashMap für eine Menge ohnehin zu bevorzugen…)
Ok, danke.
Ich frage nicht, weil ich die Methoden auswendig lernen will, sondern weil z.b. in einer Altklausur eine Walkthrough-Aufgabe war, in der drei LinkedLists waren und da musste man eben wissen, ob die Elemente vorne oder hinten angehaengt werden, damit man die richtige Ausgabe aufschreibt. Deswegen habe ich mir das nochmal genauer angeschaut.
Hi an alle! Mal ne Frage,
per Definition ist ja ein stark zusammenhängender Graph nur für gerichtete Graphen möglich, bei ungerichteten Graphen ist er ja “nur” zusammenhängend. Nun stolpere ich beim Altklausurrechnen schon das zweite Mal über folgende Situation:
AuD Klausur vom 31.Juli 2008 - Aufgabe 7 a) zweite Teilfrage:
“Der Graph ist stark zusammenhängend”
Ich würde intuitiv mit “nein” antworten, da der Graph ja ungerichtet ist und somit nur zusammenhängend ist.
Die Musterlösung sieht aber (auch zum zweiten Mal) ein “Ja” vor.
Vielleicht könnt ihr mir dabei ja weiterhelfen, da ich ein wenig ratlos bin (wobei ich meiner Lösung mehr Glauben schenke), dies aber ein eigentlich einfacher Punkt wäre…Danke schon mal! 
Naja, stark zusammenhängend heißt ja, dass du zu jedem Knotenpaar (A,B) einen Pfad A→B und einen Pfad B→A finden kannst (für nur einfach zusammenhängend reicht statt dem und ein oder). Und da alle Kanten bei einem ungerichteten Graphen in beide Richtungen gehen, gibts zu jedem Pfad A→B automatisch auch einen Pfad B→A.
Du kannst dir einen ungerichteten Graphen auch als gerichteten vorstellen, indem du aus einer Kante A–B zwei Kanten A→B und A←B machst. Tatsächlich werden ungerichtete Graphen häufig ja auch so implementiert.
Danke schonmal!
Da habe ich doch gleich die nächste Frage: stark zusammenhängend heißt doch, dass von jedem Knoten v aus jeder beliebige Knoten w erreicht werden kann. In deinem Fall mit 2 Knoten trifft das ja zu. Aber es muss doch nicht immer zwingenderweise eine Verbindung A->B und B<-A vorhanden sein, falls mehr als 2 Knoten im Graph sind. Wenn es (A, B), (B, C) und (C, A) gibt und KEIN (B, A), (C, B) und/oder (A, C), dann ist der Graph doch immer noch stark zusammenhängend? Man kann ja von einem beliebigen Knoten aus (auch über Umwege) zu einem anderen Knoten gelangen? Das würde ja deiner Definition widersprechen. Bei einfach/schwach zusammenhängend gebe ich dir aber recht.
Mich stört aber immer noch die Definition “Bei ungerichteten Graphen lässt man „stark“ weg.” (AuD, Kapitel 14 Folie 17) im Sinne der beschriebenen Klausurfrage. Darin ist nämlich ein ungerichteter Graph angegeben, der dann per Definition nicht mehr als stark bezeichnet werden sollte. Puuh, ich hoffe ich stifte nicht noch mehr Verwirrung…
Ich glaube, da hast du nicht genau genug gelesen: Malte sprach von Pfaden, nicht von Kanten. Wenn ein Pfad von A nach C existiert, dann darf der natürlich aus Kanten zusammengesetzt sein, die über den Knoten B führen.
Worin soll sich deiner Meinung nach ein stark und ein schwach zusammenhängender, ungerichteter Graph unterscheiden? Das können sie nämlich - wie Malte geschrieben hat - nicht. Wenn du das beschreiben kannst, sollte klar werden, wo dein Verständnisproblem liegt.
Richtig, das habe ich überlesen.
Richtig, bei nem ungerichteten Graph gibt es ja keine Unterscheidung, da er nur zusammenhängend sein kann. In der Klausuraufgabe lautet die Frage bei dem vorliegenden ungerichteten Graphen nun ob es ein stark zusammenhängender Graph ist, das Merkmal „stark“ wird also explizit angesprochen.
Eigentlich besteht meine Verwirrung nur darin, dass es laut der Definition im Skript (Kap.14- F.17) keinen stark zusammenhängenden ungerichteten Graph lt. Definition geben kann, da dieser höchstens „zusammenhängend“ heißen darf, der Begriff stark zusammenhängend ist einzig für gerichtete Graphen reserviert. Ist zwar etwas kleinlich, aber dennoch relevant und eigentlich ein einfacher Punkt.
Wie würdest du denn die Frage aus der AuD Klausur vom 31.Juli 2008 - Aufgabe 7 a) zweite Teilfrage beantworten?
Also ich hätte ja gesagt, weil man zwischen beliebigen Paaren immer in beide Richtungen einen Pfad findet. Das liegt aber auch daran, dass ich die Definition nicht so genau gelesen habe. Wie es korrigiert wurde kann ich dir nicht sagen, ich kann mir aber nicht vorstellen, dass sie da wirklich ein “nein” sehen wollten…
Bei der Klausur vom 21.02.2013 bei der Multiple-Choice Aufgabe 1g) habe ich eine andere Lösung als die in der Musterlösung.
Nehmen wir an, dass k=2, dass also jeder Knoten höchstens zwei Kinder hat. Wenn man sich jetzt einen Baum vorstellt, der nur drei Knoten hat, d.h. dass es die Wurzel gibt und diese zwei Kind hat, es also zwei Blätter (n=2) gibt, dann ist die Höhe dieses Baums 1.
Dadurch fallen bei der Aufgabe die erste, dritte und vierte Antwortmöglichkeit raus. Also bleibt nur noch die Antwort "mindestens 1"übrig, was ja auf jeden Fall immer stimmt, außer wenn der Baum leer ist oder nur aus der Wurzel besteht, aber in diesem Fall würden die anderen Antworten auch durchfallen, also muss “mindestens 1” die Lösung sein oder?
Laut Vorlesung 12, Folie 10 ist die minimale Höhe eines Binärbaums (also für k=2) floor(log_2(n)).
Da diese Möglichkeit nirgendwo auftaucht, würde ich behaupten, du hast recht. (Weshalb du vielleicht auch die Lösung im Wiki ausbessern solltest, falls dir niemand widerspricht.)
Wenn ich mich grade nicht täusche, hat ein Baum, der nur aus der Wurzel besteht per definitionem die Höhe 1, daher wäre 1 auch in diesem Fall richtig.
EDIT: Ich muss lesen lernen.
In der Aufgabe ist n aber die Anzahl der Blätter und nicht die der Knoten, also wäre auch das falsch.
Habe gerade nochmal die Folien überflogen, konnte so eine Definition aber nicht finden, vielleich war ich auch nur zu ungenau. In den Übungsfolien steht, dass ein Blatt die Höhe 0 hat und ein Knoten, der keine Kinder hat, ist ein Blatt. Also müsste ein Baum, der nur aus Wurzel besteht, auch die Höhe 0 haben oder?
Ups… sorry. Hab ich tatsächlich überlesen, ja.
Boah, ist vermutlich Definitionssache. Wenn ein Baum, der nur aus der Wurzel besteht, die Höhe 1 hat, kann kann man ihn halt von einem leeren Baum, der die Höhe 0 hat, unterscheiden.
Ich würde sogar fast vermuten, dass bei dieser Klausur Prämisse war, dass ein Blatt die Höhe 1 hat. Dann hat nämlich auch bei deinem n=3-k=2-Beispiel der Baum die Höhe drei und die Logarithmus-Antwort wäre richtig.
EDIT: Wobei natürlich die Logarithmus-Antwort für n=0 oder k=0 nicht definiert wäre und somit trotzdem 1 die richtige Antwort wäre. (Außer für n=0, weil ein leerer Baum dann die Höhe 0 hätte. Ich merke schon, ich trage nicht zur Aufklärung der Verwirrung bei.)
EDIT 2: Wenn ich mich nicht täusche, können alle Antwortmöglichkeiten für ganze positive Zahlen sowieso nicht kleiner als 1 werden. Die Antwort 1 erschlägt also sowieso alle anderen Antwortmöglichkeiten. Meine letzte Antwort, also: 1 ist richtig. Der Sonderfall eines leeren Baums wird in der Aufgabe nicht beachtet.
Kausur 19.02.2009 Aufgabe8) wp-kalkül
Hallo miteinander, ich hoffe es kann mir jemand weiterhelfen so kurz vor knapp vor der KLausur…
und zwar bin ich bei der KLausur vom 19.02.2009 bei der AUfgabe 8b) iii) ( https://www2.informatik.uni-erlangen.de/teaching/WS2009/AuD/organisation/oldexams/secure/09-02-19_klausur.pdf) in der musterlösung auf folgendes gestoßen :
ab der zeile… [quote]
¬{(x mod 2) = (i mod 2) ∧ y ≥ 0 ∧ x > 1} ∨ ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) =
[/quote]
… ist das für mich nicht mehr ganz klar was da gemacht wird und weshalb… ich habe mir zwar die folien zu wp-kalkül angeschaut aber daraus habe ich auch nicht herausgefunden was das ganze zu bedeuten hat… gibt es für solche teilaufgaben ein Tutorial ooder ähnliches wo ich das üben und vorallem auch verstehen kann?
Ich habe hier auch noch eine Frage:
Ich habe das jetzt so aufgefasst, dass das identisch ist mit
return (int) ‚/‘ ;
Oder hab ich da was falsch verstanden?
@ Kuno_See: Schau dir den Source Code an.
Guten Abend,
"Welches ist eine gültige Schleifenvariante / Temrinierungsfunktion für folgenden Code:
void f(char n){
char m=n;
do {
n /= 2;
somethingInO(m);
} while (n > 0);
}Zur Antwort stehen: log(n), m-n, n."
Ich hätte auf log(n) getippt, da n ja mit jedem Schleifendurchlauf halbiert wird. Richtig ist aber offenbar n, könnte mir das jemand erklären?
Im Übrigen SS12 / 01 / e)
Varianten sind unter Anderem ganzzahlige Funktionen, log(n) nicht.