You are not logged in.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

21

Monday, September 19th 2005, 10:11am

Quoted

Original von Joachim

Quoted

Original von iriania
2. Wann sollen diejenigen kommen, die nur Komplexität v. Algorithmen schreiben??
Ich kläre das mit Herrn Vollmer und poste die Antwort hier sobald ich näheres weiß.
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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

radicarl

Junior Schreiberling

  • "radicarl" is male

Posts: 243

Date of registration: Oct 7th 2003

Location: H-Town

22

Monday, September 19th 2005, 1:23pm

Die Lösungen zu den Übungen 5, 8, 9 und 11 hat niemand?

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

23

Monday, September 19th 2005, 8:38pm

Quoted

Original von Joachim

Quoted

Original von Joachim

Quoted

Original von iriania
2. Wann sollen diejenigen kommen, die nur Komplexität v. Algorithmen schreiben??
Ich kläre das mit Herrn Vollmer und poste die Antwort hier sobald ich näheres weiß.
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? ?(

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

24

Monday, September 19th 2005, 8:42pm

Quoted

Original von NullAhnung

Quoted

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? ?(
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. :)
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

snoopy

Junior Schreiberling

  • "snoopy" is male

Posts: 146

Date of registration: Feb 29th 2004

Location: Hannover

Occupation: Informatik

25

Wednesday, September 21st 2005, 2:29pm

Dürfen (sollten) alle die, die nur Komplexität von Algorithmen schreiben auch das TheoInf Skript dabei haben und nutzen?
Oder wie ist das gedacht.

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!
Ich möchte ungern in der Klausur dann da ein Wissenleck haben :(

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...

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

26

Wednesday, September 21st 2005, 5:08pm

Quoted

Original von snoopy
Dürfen (sollten) alle die, die nur Komplexität von Algorithmen schreiben auch das TheoInf Skript dabei haben und nutzen?
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.

Quoted

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!
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.

Quoted

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...
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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

27

Thursday, September 22nd 2005, 11:14am

Quoted

Original von Joachim

Quoted

Original von snoopy
Dürfen (sollten) alle die, die nur Komplexität von Algorithmen schreiben auch das TheoInf Skript dabei haben und nutzen?
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.
Für alle Klausurteilnehmer sind beide Skripte als Hilfsmittel erlaubt.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Eggmaster

Trainee

  • "Eggmaster" is male

Posts: 42

Date of registration: Oct 8th 2003

Occupation: WiMi

28

Monday, September 26th 2005, 2:11pm

Da im Netz leider keinerlei alte Klausuren zu KvA zu finden sind, würden mich Aufgabentyp und -umfang sehr interessieren und wie gut man mit den Übungen auf die Klausur vorbereitet ist.
Also an alle, die die Klausur schon mal geschrieben haben, postet doch mal bitte, was uns so in etwa erwartet.

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?
EKO: If you do not mind I will start at the beginning. A long time before Christ, the king of Judah was a man named Josiah.
LOCKE: Man...when you say beginning, you mean beginning.

Benjamin

Segelnder Alter Hase

  • "Benjamin" is male

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

29

Monday, September 26th 2005, 2:18pm

Quoted

Original von Eggmaster
Also an alle, die die Klausur schon mal geschrieben haben, postet doch mal bitte, was uns so in etwa erwartet.


Die Klausur wird zum ersten mal geschrieben. Es handelte sich vorher um eine mündlichge Prüfung. Da KvA nun Pflichtveranstaltung ist und viel mehr Hörer hat, gibt es seit diesem Semester eine Klausur. Aus diesem Grunde gibt es u.a. auch keine alte Klausur. Zudem würde sich der Schwerpunkt vielleicht verändert haben, da mit dieser Klausur erstmal die Skripte in den Klausuren erlaubt sind. Sicher werden aber die Klausuraufgaben etwas mit den Übungen zu tun haben.
Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

30

Monday, September 26th 2005, 2:44pm

Quoted

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?
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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Sep 26th 2005, 2:45pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

31

Monday, September 26th 2005, 2:51pm

Quoted

Original von metalhen
Sicher werden aber die Klausuraufgaben etwas mit den Übungen zu tun haben.
Genau. Typische Klausuraufgaben könnten beispielsweise sein:

  • Reduktion eines Problemes auf ein anderes
  • Nachweis der NP-Vollständigkeit eines Problems
  • Komplexitätsuntersuchung eines Problems (Laufzeit, Speicherplatz)
  • Berechnung einer approximativen Lösung für eines der aus der Vorlesung bekannten Probleme
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

zakarumite

Trainee

  • "zakarumite" is male

Posts: 56

Date of registration: Feb 15th 2004

32

Monday, September 26th 2005, 11:41pm

Quoted

Berechnung einer approximativen Lösung für eines der aus der Vorlesung bekannten Probleme


Ist das wie in der 10. Übung ?
Was meinst Du mit approximativen Lösung?
...

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

33

Tuesday, September 27th 2005, 7:51am

Quoted

Original von zakarumite

Quoted

Berechnung einer approximativen Lösung für eines der aus der Vorlesung bekannten Probleme


Ist das wie in der 10. Übung ?
Eher so wie das in der 11. Übung. Dann allerdings natürlich nicht so umfangreich.

Quoted

Was meinst Du mit approximativen Lösung?
Da es sich um ein Approximationsverfahren handelt, es die erhaltene Lösung natürlich nicht immer exakt, sondern meist nur approximativ.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Sep 27th 2005, 7:56am)


snoopy

Junior Schreiberling

  • "snoopy" is male

Posts: 146

Date of registration: Feb 29th 2004

Location: Hannover

Occupation: Informatik

34

Tuesday, September 27th 2005, 11:02am

Skript 5.3 Das Partionierungsproblem

Was ist r im Algorithmus PartAS? Wozu ist das gut und wozu dient Kr?
Sortiert PartAS nicht nur einfach abwechselnd in 2 Töpfe von der Fülle der Töpfe abhängig? Wzu der Kr-Kram?

fatdolphin

Trainee

  • "fatdolphin" is male

Posts: 71

Date of registration: May 30th 2005

35

Tuesday, September 27th 2005, 11:59am

logische Funtionen in P bzw. NP

habe eine Frage zu logische Funtionen,sind P und NP Klasse unter Komplement-,Vereinigung- und Durchschnittbildung abgeschloßen?

zakarumite

Trainee

  • "zakarumite" is male

Posts: 56

Date of registration: Feb 15th 2004

36

Tuesday, September 27th 2005, 1:47pm

Quoted

Eher so wie das in der 11. Übung. Dann allerdings natürlich nicht so umfangreich.


Aber Herr.Vollmer hat einmal gesagt, dass eine Aufgabe, wie 11.Übung, kommt nicht dran. Sonst in 11.Ubung gibt es nicht, was wir approximieren, oder?
...

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

37

Tuesday, September 27th 2005, 3:01pm

RE: logische Funtionen in P bzw. NP

Quoted

Original von fatdolphin
habe eine Frage zu logische Funtionen,sind P und NP Klasse unter Komplement-,Vereinigung- und Durchschnittbildung abgeschloßen?


Wenn ich mich recht entsinne ist NP ist unter Vereinigung und Durchschnitt abgeschlossen, unter Komplement ist es ein offenes Problem (siehe Übung/Vorlesung NP und CoNP).
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

38

Tuesday, September 27th 2005, 5:09pm

RE: logische Funtionen in P bzw. NP

Quoted

Original von fatdolphin
habe eine Frage zu logische Funtionen,sind P und NP Klasse unter Komplement-,Vereinigung- und Durchschnittbildung abgeschloßen?
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).

Für NP ist die Sache schon etwas schwieriger. Komplementabgeschlossenheit würde P = NP implizieren und ist ein offenes Problem. Unter Durchschnittsbildung ist NP abgeschlossen (Simulation der zugehörigen NTMs nacheinander durch eine NTM; akzeptieren, wenn beide akzeptiert haben). Unter Vereinigungsbildung ist NP ebenfalls abgeschlossen (Simulation der zugehörigen NTMs nacheinander durch eine NTM; akzeptieren, wenn eine von beiden akzeptiert hat).
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 2 times, last edit by "Joachim" (Sep 27th 2005, 5:10pm)


EnteTaylor

Trainee

  • "EnteTaylor" is male

Posts: 111

Date of registration: Oct 24th 2003

Location: Göttingen

Occupation: weil's toll is

39

Tuesday, September 27th 2005, 5:37pm

Fehler im Skript

Im Skript auf Seite 30 ist ein Fehler (nix schlimmes). Dort steht:

Quoted

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.


Es soll nicht gezeigt werden, dass 3SAT NP-hart ist, sondern dass SUBSET-SUM NP-hart ist.
Meine Gedächtnisprotokolle: www.janwy.de

KingLifetec

Praktikant

  • "KingLifetec" is male

Posts: 31

Date of registration: Feb 18th 2004

40

Tuesday, September 27th 2005, 7:29pm

Satz von Cook

Müssen wir eigentlich den Satz von Cook genau nachvollziehen können?
Also wofür man den brauch ist ja klar, um zu zeigen das SAT NP-Vollständig ist, aber wie man das genau beweist, müssen wir doch sicher nicht wissen oder?
Wer aufhört besser zu werden, hat aufgehört gut zu sein!