Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » P-NP-Einführung

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

P-NP-Einführung

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

JROppenheimer
Foren As

Dabei seit: 17.11.2007
Beiträge: 94

P-NP-Einführung

Zitatantwort auf diesen Beitrag erstellen

Ich hab dummerweise das Vorhaben, ein Seminar in Theo zu machen. Jetzt habe ich mein Thema bekommen und (wie alle anderen auch) gehts hauptsächlich um fundamentale Komplexitätsprobleme.

Jetzt stehe ich vor dem Problem, dass ich von P und NP zero Ahnung habe ...

Hätte vlt. einer eien Empfehlung, wie ich mich am besten in das Thema reinarbeite?! Vlt kennt einer eine gute möglichst nicht zu ausführliche Einführung in das Thema, oder kann mir das knapp zusammenfassen, damit ich mit den ganzen Abkürzungen was anfangen kann: P, NP, FNP, FP sowas...

Danke Euch allen schon mal im Voraus!

__________________
I'm 71% Megatron!

22.03.2008 09:46

Nehmen Sie JROppenheimer in Ihre Freundesliste auf

MSN Passport-Profil von JROppenheimer anzeigen

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Das ist aber ein weites Feld. Wie kommts, dass du davon garkeine Ahnung hast?

Ich würde mit diversen Wikipedia-Artikeln anfangen:

http://de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie
http://de.wikipedia.org/wiki/NP_%28Kompl...3%A4tsklasse%29
http://de.wikipedia.org/wiki/P-NP-Problem
http://de.wikipedia.org/wiki/Karps_21_NP...4ndige_Probleme
http://qwiki.stanford.edu/wiki/Complexity_Zoo#{{{2}}}

Hast du kein genaueres Thema bekommen?

22.03.2008 12:13

Nehmen Sie Tobias in Ihre Freundesliste auf

JROppenheimer
Foren As

Dabei seit: 17.11.2007
Beiträge: 94

Ich studiere ja Informatik auf Dipl. Bei uns sind aber alle Dipl. Vorlesungen schon durch Bachelorvorlesungen ersetzt. Da wird das alles etwas anders gelehrt... Theo2 habe ich genau bis zu den regulären Ausdrücken geschafft. Da mangelte es mir an Zeit und letztes Semester habe ich mich mit Algorithmentheorie auseinander gesetzt ... (brauche ja einen theoäquivalenten Schein) Da gings aber erst gegen Ende um P-NP und das Zeug. Da es mir aber an Lerngruppen mangelt und ich mir versuche das alles per Bücher und Übungen beizubringen fehlt mir einfach das Wissen. Und ich dachte ich käme vlt drum herum, mir erst die ganze Sache mit den Turing Maschinen anzuschauen, ich würde nämlich gern möglichst schnell zum eigendlichen "Problem" kommen ohne vorher lange Zeit an Vorbereitung zu verlieren.

Der Titel des Beitrags, über den ich referieren soll ist: "On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence"

Geht irgendwie um die Einführung neuer Komplexitätsklassen bin aber nicht sicher...

__________________
I'm 71% Megatron!

23.03.2008 12:43

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » P-NP-Einführung