literatur zur komplexitätstheorie
-
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
