Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
Komplexität von Algorithmen
Wednesday, August 10th 2005, 9:30am
Das frage ich mich auch!
Quoted
Original von SethGecco
????????
This post has been edited 1 times, last edit by "migu" (Aug 10th 2005, 9:35am)
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wednesday, September 14th 2005, 10:16pm
Um welche Übung geht es denn?
Original von mDev
meines erachtens wurde es noch ein weiteres mal bei einer besonders schwierigen übung gesagt, ohne diese lösung jedoch zu veröffentlichen.
Thursday, September 15th 2005, 12:56am
|
Source code |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
phi = { (x1 oder ^X2 oder X3) und (^x1 oder X2 oder X3) }
für
a1 = 11100 = a'1 b1 = b'1 = 10000
a2 = 11010 = a'2 b2 = b'2 = 01000
a3 = 11001 = a'3
und
t = 33111
phi aus 3SAT
=> es gibt eine Belegung von x1, x2, x3 die phi erfüllt
=> es ex. I unt. {a1, a2, a3, a'1, a'2, a'3} wobei ai element von I und a'i nicht
summe I = 33111 (schon Ziel erreicht ??)
=> es ex. I unt. {a1, a2, a'1, a'2, b1, b2, b'1, b'2 } mit
summe I = 55222
=> <{a1, ---, b'2}, t> aus SUBSET-SUM
|
Friday, September 16th 2005, 4:00pm
ich bräuchte Übung 5, 8, 9 und 11...
This post has been edited 1 times, last edit by "iriania" (Sep 16th 2005, 4:45pm)
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Friday, September 16th 2005, 9:44pm
Du hast die a_i und a_i' nicht richtig definiert. Korrekt sollte es wie folgt aussehen:
Original von zakarumite
ich habe so ein Problem, hier ein Beispiel für "SUBSET SUM ist NP-vollständig" gedacht:
Source code
phi = { (x1 oder ^X2 oder X3) und (^x1 oder X2 oder X3) }
ist es aber nicht, oder?
t sollte 33111 sein, nicht aber 55222....! oder was mache ich falsch?
This post has been edited 1 times, last edit by "Joachim" (Sep 16th 2005, 9:44pm)
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Friday, September 16th 2005, 9:46pm
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??
This post has been edited 1 times, last edit by "Joachim" (Sep 16th 2005, 9:46pm)
Saturday, September 17th 2005, 3:23pm
Original von Markus
Original von iriania
1. Wo genau ist die Wunstorfer Str. 14?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sunday, September 18th 2005, 1:34pm
Das wird aller Voraussicht nach so bleiben. Der Grund ist, daß das Skript bei der Bearbeitung der Klausuraufgaben sowieso nur eine geringe Hilfe darstellt und (wenn überhaupt) nur das Auswendiglernen einiger Definitionen erspart. Zudem wird es wohl von vielen Studierenden als angenehm empfunden, wenn das Skript in der Klausur zur Verfügung steht.
Original von Torrero
Auch wenn ich an der Klausur nicht teilnehme, habe ich gerade gelesen, das sowohl für Thi, als auch für KvA die Skripte als Hilfsmittel zugelassen sind, gibts nen bestimmten Grund für die Änderung, denn früher war das ja zumindest bei THI nicht so, und vor allem, bleibt das auch so, im Hinblick aufs nächste oder übernächste Semester gesehen ?
Sunday, September 18th 2005, 7:23pm
Original von Joachim
[...]Zudem wird es wohl von vielen Studierenden als angenehm empfunden, wenn das Skript in der Klausur zur Verfügung steht.[...]
This post has been edited 1 times, last edit by "Markus" (Sep 18th 2005, 7:24pm)
