Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
Komplexität von Algorithmen
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, September 19th 2005, 10:11am
Klausurbeginn ist für alle Teilnehmer zur gleichen Zeit. Die Teilnehmer, die nur einen der beiden Teile schreiben, müssen jedoch früher abgeben als der Rest.
Quoted
Original von Joachim
Ich kläre das mit Herrn Vollmer und poste die Antwort hier sobald ich näheres weiß.
Original von iriania
2. Wann sollen diejenigen kommen, die nur Komplexität v. Algorithmen schreiben??
Monday, September 19th 2005, 8:38pm
Original von Joachim
Klausurbeginn ist für alle Teilnehmer zur gleichen Zeit. Die Teilnehmer, die nur einen der beiden Teile schreiben, müssen jedoch früher abgeben als der Rest.
Original von Joachim
Ich kläre das mit Herrn Vollmer und poste die Antwort hier sobald ich näheres weiß.
Original von iriania
2. Wann sollen diejenigen kommen, die nur Komplexität v. Algorithmen schreiben??
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, September 19th 2005, 8:42pm
Kann sein. Vielleicht werden die Klausurteilnehmer auch nach den Teilen der Klausur, die sie jeweils schreiben, im Raum gruppiert. Das muß aber nicht Deine Sorge sein ... Du solltest nur rechtzeitig zur Klausur erscheinen.
Original von NullAhnung
Original von Joachim
Klausurbeginn ist für alle Teilnehmer zur gleichen Zeit. Die Teilnehmer, die nur einen der beiden Teile schreiben, müssen jedoch früher abgeben als der Rest.
Dann kann es mir also passieren, dass ich einen neben mir sitzen hab, der Theo schreibt und ich schreib Komplexität oder wie soll ich das verstehen?
Wednesday, September 21st 2005, 2:29pm
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wednesday, September 21st 2005, 5:08pm
Es ist eigentlich so gedacht, daß nur die Skripte der Teile der Klausur zugelassen sind, die von der jeweiligen Person auch geschrieben werden. Im Prinzip spricht nichts dagegen, auch für die Leute, die nur Komplexität schreiben, beide Skripte als Hilfsmittel zuzulassen. Das kann ich aber nicht entscheiden. Ich kläre das mit Herrn Vollmer und schreibe hier morgen genaueres.
Original von snoopy
Dürfen (sollten) alle die, die nur Komplexität von Algorithmen schreiben auch das TheoInf Skript dabei haben und nutzen?
Die Komplexität-Klausur wird sich natürlich auf dem Niveau der Vorlesung/Übung bewegen. Was dort nicht aus der Grundlagen-Vorlesung verlangt wurde, wird auch in der Klausur nicht verlangt.
Kann es sein, dass an etwas aus TheoInf wissen muss, was in Komplexität nie in einer Übung dran kam.. und wenn es nur Details zu Automaten-Definition sind. Wenn man TheoInf vor einer längeren Zeit bestanden hat, wird man das nicht unbedingt wissen!
Gewisse Voraussetzungen sind in Lehrveranstaltungen höherer Semester schon zu verlangen, sonst müßte ja in jeder Lehrveranstaltung inhaltlich von Grund auf neu begonnen werden. Und gerade die Grapheigenschaften, die in den Sätzen und Beweisen eine zentrale Rolle gespielt haben (z. B. Cliquen und Verbundenheit), sollten natürlich auch in der Klausur bekannt sein.
Wir hatten in den Übungen oft Grapheneingenschaften die wir betrachtet haben. Diese wurden in der Übung auf Nachfrage erklärt und vorher nicht. Ich hoffe doch, dass in der Klausur sowas nicht passiert? Oder wird vorrausgesetzt, dass man die alle kann. Allein bei Grpaheneigentschaften spiellt es für das Wissen schon eine Rolle bei wem man D&A hatte...
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Thursday, September 22nd 2005, 11:14am
Für alle Klausurteilnehmer sind beide Skripte als Hilfsmittel erlaubt.
Original von Joachim
Es ist eigentlich so gedacht, daß nur die Skripte der Teile der Klausur zugelassen sind, die von der jeweiligen Person auch geschrieben werden. Im Prinzip spricht nichts dagegen, auch für die Leute, die nur Komplexität schreiben, beide Skripte als Hilfsmittel zuzulassen. Das kann ich aber nicht entscheiden. Ich kläre das mit Herrn Vollmer und schreibe hier morgen genaueres.
Original von snoopy
Dürfen (sollten) alle die, die nur Komplexität von Algorithmen schreiben auch das TheoInf Skript dabei haben und nutzen?
Monday, September 26th 2005, 2:18pm
Original von Eggmaster
Also an alle, die die Klausur schon mal geschrieben haben, postet doch mal bitte, was uns so in etwa erwartet.
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, September 26th 2005, 2:44pm
Das steht noch nicht fest, wird aber rechtzeitig zur Klausur bekannt gegeben. Eine komplett getrennte Benotung wird es wahrscheinlich nicht geben. Allerdings halte ich es für möglich, daß in beiden Teilen jeweils eine Mindestpunktzahl erreicht werden muß, um die Klausur zu bestehen.
Original von Eggmaster
Wie sieht eigentlich die Bewertung der einzelnen Teile der Kombi-Klausur aus?
Kann man mit einem guten Ergebnis in einem Teil sich vor ner 5 im anderen Teil retten, oder werden die "beiden" Klausuren komplett getrennt benotet und dann nur nen Durchschnitt ermittelt?
This post has been edited 1 times, last edit by "Joachim" (Sep 26th 2005, 2:45pm)
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, September 26th 2005, 2:51pm
Genau. Typische Klausuraufgaben könnten beispielsweise sein:
Original von metalhen
Sicher werden aber die Klausuraufgaben etwas mit den Übungen zu tun haben.
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Tuesday, September 27th 2005, 7:51am
Eher so wie das in der 11. Übung. Dann allerdings natürlich nicht so umfangreich.
Original von zakarumite
Berechnung einer approximativen Lösung für eines der aus der Vorlesung bekannten Probleme
Ist das wie in der 10. Übung ?
Da es sich um ein Approximationsverfahren handelt, es die erhaltene Lösung natürlich nicht immer exakt, sondern meist nur approximativ.
Was meinst Du mit approximativen Lösung?
This post has been edited 1 times, last edit by "Joachim" (Sep 27th 2005, 7:56am)
Tuesday, September 27th 2005, 3:01pm
Original von fatdolphin
habe eine Frage zu logische Funtionen,sind P und NP Klasse unter Komplement-,Vereinigung- und Durchschnittbildung abgeschloßen?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Tuesday, September 27th 2005, 5:09pm
P ist unter allen diesen Operationen abgeschlossen, da man ja einfach beide zugehörigen Turing-Maschinen simulieren und deren Ergebnisse dann auswerten könnte (bzw. für Komplementbildung einfach das Gegenteil der Ausgabe der simulierten Maschine ausgeben).
Original von fatdolphin
habe eine Frage zu logische Funtionen,sind P und NP Klasse unter Komplement-,Vereinigung- und Durchschnittbildung abgeschloßen?
This post has been edited 2 times, last edit by "Joachim" (Sep 27th 2005, 5:10pm)
Tuesday, September 27th 2005, 5:37pm
Satz: SUBSET-SUM ist NP-vollstäandig.
Beweis: SUBSET-SUM 2 NP wurde schon gezeigt. Wir zeigen nun, dass 3SAT NPhart ist, indem wir 3SAT<=(p m) SUBSET-SUM nachweisen.
