literatur zur komplexitätstheorie
-
hi, ich wollt mich mal näher mit der komplexitätheorie beschäftigen und vllt dabei auch nen kleinen blick auf theoretische automaten werfen (turingmaschien z.b.)...
ich finde das was ich bis jetzt darüber gehört/gelesen habe sehr interresant, nur behandeln viele quellen diese thema imho für neulinge nicht besonders einsteigerfreundlich, sprich mit vielen fachbegriffen, die nicht wirklich erklärt werden etc.also, wenn jemand da nen gutes buch zu weiß (bevorzugt auf deutsch
), das dies gut für einsteiger ohne besondere fachkenntnisse erklärt: 
bitte mich wissen lassen!!^^ 
-
Dieser Thread wurde von Moderator/in nman aus dem Forum Neuigkeiten aus der realen Welt in das Forum Mathematik verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
(Ja, ich weiß, dass Komplexitätstheorie ein Fachgebiet der Theoretischen Informatik und nicht der Mathematik ist, aber ich finde, dass das Mathematik-Forum trotzdem ganz gut passt.)
Mr. Pink: Was hast Du denn für Vorkenntnisse? Wäre uU ganz hilfreich, das zu wissen, damit man Dir die richtigen Bücher empfehlen kann.
-
Hallo
für "Einsteiger ohne besondere Fachkenntnisse", wie du schreibst, meiner
Meinung nach sehr schönes, kleines Büchlein:Schöning: "Theoretische Informatik kurzgefasst"
Voraussetzungen: keine besonderen, außer vielleicht Mathematik-Kenntnisse auf Gymnasialem Oberstufen-Niveau.
Für vertiefte Kenntnisse zu empfehlen: Hopcroft,Ullman: "Einführung in die
Automatentheorie, formale Sprachen und Konplexitätstheorie" (Standard-Lehrbuch, schon recht anspruchsvoll)Grüße
-
nman schrieb:
Mr. Pink: Was hast Du denn für Vorkenntnisse?
praktisch keine
ich bin zufaällig auf dieses thema getroffen und hab mir eigentlich nur nen paar artikel im inet durchgelesen (wikipedia, usw.) was sich da dann ganz interessant anhörte... ich weiß, dass das sehr wenig ist, deshalb ändere ich mal das mit den "besonderen fachkenntissen" in "gar keine fachkenntnisse". sry, wenn das irreführend war
@Hobbyprogrammierer: zu "Theoretische Informatik kurzgefasst" hab ich mir mal ein paar bericht/beurteilungen angesehen, nach denen sich das ganz gut anhört.
zu den mathematikkenntissen: ich gehe noch zur schule (in eine woche dann in die j12), weswegen ich nicht weiß ob das jetzt ausreicht: wir hatten noch keine stochastik, vektorrechnung und analysis erst durch differenzialrechnung leicht gestreift.
deshalb: kommt viel mathematik im buch vor? sonst kann ich mir vllt die entsprechenden dinge im ausrechenden maße selber aneignen um das buch zu verstehen.ich denke mit dieser erklärung ist klar, dass das 2. buch erstmal wegfällt
also ich bin schüler (kein informatikstudent oder ähnliches) OHNE vorkenntnisse und möchte ein buch zur relativ leicht verstädlichen einführung in oben gennate themenbereiche (fals es so ein buch gibt^^)
danke schon mal für die antworten, Mr.Pink
-
Hobbyprogrammierer schrieb:
Für vertiefte Kenntnisse zu empfehlen: Hopcroft,Ullman: "Einführung in die
Automatentheorie, formale Sprachen und Konplexitätstheorie" (Standard-Lehrbuch, schon recht anspruchsvoll)Hmmm, ich haett jetzt auch zu dem Buch geraten. Ist zwar evtl. wirklich etwas anspruchsvoll, aber wirkliche Vorkenntnisse braucht man nicht, nur gutes mathematisches/abstraktes Verstaendnis. Vor allem sollte man Induktionsbeweise verstehen (aber die werden in dem Buch eh nochmal von Grund auf erklaert
).
Gut an dem Buch ist auch, dass es eben sehr bekannt ist, deswegen stehen die Chancen nicht schlecht, dass du es in einer Bibliothek findest (kaufen wuerd ichs mir nicht, ist zu teuer!). Evtl. mal in einer Uni-Bibliothek nachfragen und einfach mal reinschnuppern, dann siehst du, ob es zu schwer fuer dich ist!
-
Hallo Mr.Pink
so wie Du die Lage beschreibst, glaube ich, daß das genannte Buch
Schöning: "Theoretische Informatik kurz gefaßt" ganz gut geeignet sein müßte.
Falls Du Zugriff auf eine Leihbibliothek hast, oder Dir das Buch auf andere
Weise ansehen kannst, wirf' mal einen Blck hinein.Du findest in dem Buch in kurzer Darstellung etwas Automatentheorie,
etwas über Turing-Maschinen, WHILE-Berechenbarkeit, LOOP-Programme,
etwas Komplexitätstheorie (P-NP-Probleme) sowie als "Highlight"
einen außergewöhnlich einfachen Beweis des Gödelschen
Unvollständigkeitssatzes.Analysis und Vektorrechnung wird zum Verständnis eigentlich nicht
benötitgt. Hilfreich könnte sein eine gewisse Übung im Umgang mit
Strukturen, aber, so weit ich mich erinnere, werden alle im Buch
verwendeten Strukturen (Formale Sprache, Automat, Turingmaschine, ...)
im Buch vor Gebrauch erst einmal definiert.Das Buch zielt -- meinem subjektiven Eindruck nach -- darauf ab, viele interessante und wesentliche Resultate zu beweisen, ohne viel Vorwissen oder Geduld vorauszusetzen. Der Buchtext kommt sehr schnell zu den wesentlichen
Aussagen, das beweist auch die Kürze des Buchs im Verhältnis zur Vielzahl
gestreifter Themen.Grüße
-
falls du lust hast, kannst du dir hier auch ein paar vorlesungen reinziehen
http://www.tele-task.de/en/details.php?series=1
-
okay, danke für die postings, werd mich denn mal bemühen die bücher in irgendner bibliothek zu finden (in unserer stadtbibliothek wirds wohl kaum zu finden sein).
@elise: hmmm, die links jeweils zu den einzelnen filmen funktionieren bei mir nicht, es erscheint einfach nix und browser meint alles wär fertig geladen (ie und mozilla)
Mr. Pink
-
realplayer ist hier das zauberwort
-
o mann, ich hatte realplayer installiert --> ging nicht!
habs jetzt nochmal probiert --> GING!
hab aber nix am player verändert, hab den in der zwischenzeit nicht mal benutzt -->
wenn das jemand kennt, könnt der mich vllt mal aufklären, wie das zusammenpasst?
trotzdem danke Mr. Pink
-
firewall?
-
nö
aber egal, jetzt läuft das....
is manchmal bisschen blöd wenn er sich auf ältere volesungen bezieht aber im allgemeinen ganz interessant
thx
