You are not logged in.

SethGecco

Junior Schreiberling

  • "SethGecco" is male
  • "SethGecco" started this thread

Posts: 210

Date of registration: Nov 13th 2003

Location: Hannover

Occupation: Informatik/ 5.

1

Tuesday, August 9th 2005, 11:24am

Komplexität von Algorithmen

Das Skript zur Vorlesung ist mittlerweile zum Download bereitgestellt, allerdings kann man es nur mit einem VPN-Zugriff downloaden. Hat jemand zufällig die aktualisierte Version und kann sie mir mailen, es wäre sehr nett.

Danke im Voraus

SethGecco@t-online.de

SethGecco

Junior Schreiberling

  • "SethGecco" is male
  • "SethGecco" started this thread

Posts: 210

Date of registration: Nov 13th 2003

Location: Hannover

Occupation: Informatik/ 5.

2

Wednesday, August 10th 2005, 9:03am

????????

migu

free rider

  • "migu" is male

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

3

Wednesday, August 10th 2005, 9:30am

Quoted

Original von SethGecco
????????
Das frage ich mich auch!

Im Ernst: Warum installierst du dir nicht den Cisco VPN-Client? (Den gibt es für Windows, Linux und MacOS.) Es kommt ja während des Studiums nicht nur einmal vor, dass man etwas aus dem Uni-Netz herunterladen will.
Siehe auch http://forum.finf.uni-hannover.de/thread…690&hilight=vpn
tar: Anlegen eines leeren Archivs wird feige verweigert.

This post has been edited 1 times, last edit by "migu" (Aug 10th 2005, 9:35am)


Shadow

... mit bunten Sternchen und so

  • "Shadow" is male

Posts: 838

Date of registration: Dec 21st 2001

Location: Hamburg

4

Wednesday, August 10th 2005, 12:39pm

Nimm für Linux vpnc. Der ist erheblich flexibler und kommt ohne Kernelmodul aus.

Wer den Group Key nicht selbst entschlüsseln kann ==> Mail oder PN an mich.
"Man hält die Erzeugung von Information für ein Zeichen von Intelligenz, während in Wirklichkeit das Gegenteil richtig ist: Die Reduktion, die Auswahl der Information ist die viel höhere Leistung."
-- Heinz Zemanek

radicarl

Junior Schreiberling

  • "radicarl" is male

Posts: 243

Date of registration: Oct 7th 2003

Location: H-Town

5

Wednesday, September 14th 2005, 2:58pm

wurde in der Übung nicht hin und wieder gesagt das die Lösungen in Netz zu finden seien?

Benjamin

Segelnder Alter Hase

  • "Benjamin" is male

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

6

Wednesday, September 14th 2005, 4:43pm

nein.
Das wurde nur einmal zu einer Übung gesagt, wo die Zeit etwas knapp wurde. Diese Übung ist auch online.
Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.

mDev

Erfahrener Schreiberling

  • "mDev" is male

Posts: 282

Date of registration: Oct 10th 2002

Location: Hannover

Occupation: Wissenschaftlicher Mitarbeiter

7

Wednesday, September 14th 2005, 10:14pm

meines erachtens wurde es noch ein weiteres mal bei einer besonders schwierigen übung gesagt, ohne diese lösung jedoch zu veröffentlichen.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

8

Wednesday, September 14th 2005, 10:16pm

Quoted

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.
Um welche Übung geht es denn?
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

zakarumite

Trainee

  • "zakarumite" is male

Posts: 56

Date of registration: Feb 15th 2004

9

Thursday, September 15th 2005, 12:56am

SUBSET SUM ist NP-voll.

ich habe so ein Problem, hier ein Beispiel für "SUBSET SUM ist NP-vollständig" gedacht:

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

ist es aber nicht, oder?
t sollte 33111 sein, nicht aber 55222....! oder was mache ich falsch?
...

radicarl

Junior Schreiberling

  • "radicarl" is male

Posts: 243

Date of registration: Oct 7th 2003

Location: H-Town

10

Thursday, September 15th 2005, 11:07am

ich bräuchte Übung 5, 8, 9 und 11
hat die vielleicht irgendwer digital voliegen und könnte mir sie schicken oder nen Link dazu geben?

Danke sehr

iriania

Junior Schreiberling

  • "iriania" is female

Posts: 222

Date of registration: Nov 24th 2003

Location: Waqwaq

Occupation: Wie? Ich studiere? seit wann denn?

11

Friday, September 16th 2005, 4:00pm

Ich habe zwei Fragen:

1. Wo genau ist die Wunstorfer Str. 14?
2. Wann sollen diejenigen kommen, die nur Komplexität v. Algorithmen schreiben??

edit: die erste Frage hat sich schon erledigt!



Übrigens:

Quoted

ich bräuchte Übung 5, 8, 9 und 11...

Die Übungen sind auf der Webseite der Vorlesung. Die Lösungen leider nicht, falls die gemeint waren. Die hätte ich bitte auch gern, und zwar von ALLEN Übungen.
...und sie dreht sich doch!

This post has been edited 1 times, last edit by "iriania" (Sep 16th 2005, 4:45pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

12

Friday, September 16th 2005, 9:44pm

RE: SUBSET SUM ist NP-voll.

Quoted

Original von zakarumite
ich habe so ein Problem, hier ein Beispiel für "SUBSET SUM ist NP-vollständig" gedacht:

Source code

1
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?
Du hast die a_i und a_i' nicht richtig definiert. Korrekt sollte es wie folgt aussehen:

phi := (x1 OR NOT x2 OR x3) AND (NOT x1 OR x2 OR x3)

Also ist n := 2 (2 Klauseln) und m := 3 (3 Variablen). Unsere Oktalzahlen haben also alle 5 Ziffern. Es ist nun:

a_1 := (10100)_8
(da x1 nur in der ersten Klausel vorkommt)

a_2 := (01010)_8
(da x2 nur in der zweiten Klausel vorkommt)

a_3 := (11001)_8
(da x3 in beiden Klausel vorkommt)

a_1' := (01100)_8
(da NOT x1 nur in der zweiten Klausel vorkommt)

a_2' := (10010)_8
(da NOT x2 nur in der ersten Klausel vorkommt)

a_3' := (00001)_8
(da NOT x3 in keiner Klausel vorkommt)

b_1 := (10000)_8
b_2 := (01000)_8
b_1' := (10000)_8
b_2' := (01000)_8

t := (33111)_8

Der Rest sollte dann durch einfaches Ausrechnen hinkommen.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Sep 16th 2005, 9:44pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

13

Friday, September 16th 2005, 9:46pm

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

This post has been edited 1 times, last edit by "Joachim" (Sep 16th 2005, 9:46pm)


Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

14

Saturday, September 17th 2005, 2:10pm

Quoted

Original von iriania
Ich habe zwei Fragen:

1. Wo genau ist die Wunstorfer Str. 14?
[...]

edit: die erste Frage hat sich schon erledigt!


Und wo ist sie?
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

Benjamin

Segelnder Alter Hase

  • "Benjamin" is male

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

15

Saturday, September 17th 2005, 3:23pm

Quoted

Original von Markus

Quoted

Original von iriania
1. Wo genau ist die Wunstorfer Str. 14?



In Limmer.
Bahnfahrer: Ab HBf oder Steintor oberirdisch Linie 10 Richtung Ahlem, Haltestelle Wunstorfer Straße.
Autofahrer: B6, Abfahrt Linden Nord. Einfach mal map24 fragen.
Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.

zakarumite

Trainee

  • "zakarumite" is male

Posts: 56

Date of registration: Feb 15th 2004

16

Saturday, September 17th 2005, 6:03pm

RE: SUBSET SUM ist NP-voll.

danke, aber ich glaube im Skript ist es falsch geschrieben, oder? Seite 28, unten für ai und a'i steht "...,falls xi aus Cj) dann sollte es für a'i "..., falls NOT xi aus Cj)

ausserdem, ich habe mit diesen Initializierungen probiert, und sieht so aus:

=> es ex. I unt. {a1, a2, a3, a'1, a'2, a'3} wobei ai element von I und a'i nicht
summe I = 22111

=> es ex. I unt. {a1, a2, a'1, a'2, b1, b2, b'1, b'2 } mit
summe I = 44121

ist auch nicht t = 33111.
Wie entscheiden wir am Anfang für t?
...

Torrero

Senior Schreiberling

  • "Torrero" is male

Posts: 854

Date of registration: Oct 16th 2003

Location: Laatzen

Occupation: Angewandte Informatik

17

Saturday, September 17th 2005, 11:55pm

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 ?

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

18

Sunday, September 18th 2005, 11:47am

Herr Vollmer hat einmal in seiner Vorlesung gesagt, dass er mit seinen HiWis gesprochen hätte und diese nach ihrer Meinung gefragt habe. Diese seien für das Skript in den Klausuren gewesen, so dass sich Herr Vollmer entschlossen habe, für seine sämtlichen Klausuren das Skript von nun an zuzulassen.
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)

19

Sunday, September 18th 2005, 1:34pm

Quoted

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

Im Umkehrschluß heißt das aber auch, daß es z. B. nur für das Hinschreiben des Pumping Lemmas keine Punkte mehr in der Klausur geben wird, da dies ja bereits im Skript steht. Oder allgemeiner formuliert: Lösungen, die nur aus dem Skript abgeschrieben werden, bringen in der Klausur keine Punkte.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

20

Sunday, September 18th 2005, 7:23pm

Quoted

Original von Joachim
[...]Zudem wird es wohl von vielen Studierenden als angenehm empfunden, wenn das Skript in der Klausur zur Verfügung steht.[...]


Hm, also ich find es ohne Skript angenehmer, aber jedem das seine.
Auf der anderen Seite kann man natürlich auch sagen, dass man im "richtigen" Leben auch "nur" wissen muss, wo es steht und wie man es anwendet.

Edit: Sorry ist ein wenig off, also: back to topic
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

This post has been edited 1 times, last edit by "Markus" (Sep 18th 2005, 7:24pm)