Grundlagen für theoretische Informatik?

[Quantar]

Helas, was sollte man so im kognitiven Portfolio haben, um sich eine gute Basis für diesen Bereich zu schaffen? Bisweilen kann ich "nur" mit Logik(en) und Mengenlehre dienen. Wo sollte man sich nochmal durcharbeiten?

greetz&thx
Q

[Stone2001]

Automatentheorie und die dazugehörigen Sprachen, also Chomsky-Hierachie, sowie endliche Automaten, Kellerautomaten und Turingmaschienen.
Gerade in diesem Bereicht gibt es extrem viel Material.

Weiter geht es dann vielleicht mit der Berechenbarkeitstheorie und NP-Vollständigen Problemen.

Interessant wird dann der Bereich, wenn man NP-vollständige Probleme mit Sprachen kombiniert. :D

[Quantar]

hmm, aber fallen diese Sachen nicht in diesen Bereich rein? Mir gehts erstmal um Basiswissen, um es überhaupt verstehen zu können. Hab da leider atm noch so einige Defizite :-/

[hadez16]

also bevor man an automaten ranngeht sollte man sich....ehhhhh....boah lang ists her...

boolsche algebra, logische schaltungen, dieses ganze flipflop-gedöns..."UND" & "ODER"-schaltungen

wahrheitstabellen in verbindung mit boolscher algebra

dann gibts doch diese rechenregeln für die boolsche algebra

boah mann ich krieg echt nixmehr zusammen....MORGANSCHE REGELN *g* genau

[Marbleearth]

hm vll mal in Automaten und Algorithmen (Markov zB) einlesen. Im INET gibts ja genug Material.

[Stone2001]

hmm, aber fallen diese Sachen nicht in diesen Bereich rein? Mir gehts erstmal um Basiswissen, um es überhaupt verstehen zu können. Hab da leider atm noch so einige Defizite :-/
Natürlich fallen die Bereich die ich aufgezählt habe in den Bereich Theoretische Informatik!
Zu Beginn: Um sich einen guten Überlick über das Thema über Theoretische Informatik zu verschaffen ist das Buch "Theoretische Informaitk - kurzgefasst" von Uwe Schöning nicht schlecht.
Der fängt mit der Automatentheorie und Formalen Sprachen an (also welche Grammatiken gibt es und wie sieht der zugehörige Automat aus, der diese Grammatik akzeptiert (bei regulären Sprachen sind dies die endlichen Automaten)), macht dann mit der Berechenbarkeitstheorie weiter (Turing, WHILE, LOOP-Berechenbarkeit) und hört mit der Komplexitätstheorie auf /P-NP-Problem, NP-Vollständige Probleme). Wenn man diese Bereiche kennt, hat man eine ordentliche Grundlage.
Weiter kann man sich dann noch in Logiken einarbeiten. Aussagen- und Prädikatenlogiken sind noch recht einfach. Die Frage nach der Erfüllbarkeit ist zwar nicht immer einfach zu beantworten, es gibt aber, in gewissen Fällen, Formalismen (Resultion und Tableux-Methode), mit denen man die Unerfüllbarkeit nachweisen kann.
Hat man diese Logiken verstanden, kann man dann weiter machen mit Logiken höherer Ordnung oder Temporalen Logiken, die z.B. bei der Softwareverifikation oder dem Modellchecking angewandt werden.

Aber für was brauchst du überhaupt dieses Wissen? Höhere Logiken sind machen schon verdammt hartes Brot.

EDIT: Um sich mit Automaten und Formalen Sprachen zu beschäftigen ist Wissen über die Aussagenlogik nicht unbedingt notwendig.

[Quantar]

Aber für was brauchst du überhaupt dieses Wissen?
MA Logik =)
Sind zwar noch 3 Semester zum BA, aber da ich meinen Neigungen hier an der Uni recht wenig nachgehen kann, arbeite ich mich schonmal in die Materie ein.
In den meisten der dortigen Bereiche habe ich schon ein wenig bis viel Ahnung. Einzig die TI bereitet mir da ein wenig Kopfzerbrechen, da ich bisweilen einer philosophisch angehauchten Logik nachgehe.
Atm arbeite ich mich durch Mengenlehre durch(da kommen u.a. noch cardinal numbers, ordered sets and lattices, ordinal numbers, axiom of choice, zorns lemma, well ordering theorem, logic and propositional calculus, boolean algebra).
Hab halt ein bissi Schiss, da ich mich ehrlich gesagt erst seit nem knappen Jahr ernsthaft mit formalen Systemen beschäftige und insbesondere in der Mathematik einige Defizite habe. Habe mir erstmal im leichten Übereifer dieses BUch (http://www.amazon.de/Theoretische-Informatik-Eine-umfassende-Einf%C3%BChrung/dp/3540426248/sr=8-8/qid=1168637292/ref=sr_1_8/302-7850752-1456033?ie=UTF8&s=books) gekauft und sofort gemerkt, dass ich vorher erstmal ein paar grundlegende Sachen lernen muss.
Auszug aus der Studieninfo zu TI
Vorlesung Algorithmentheorie 2 SWS
In der Vorlesung werden grundlegende Begriffe, Prinzipien und Sätze aus der Algo-rithmentheorie und der Komplexitätstheorie behandelt.
Zu den behandelten Themen gehören: Begriff des Algorithmus und des Kalküls, Tu-ringmaschinen und Registermaschinen, partiell rekursive Funktionen, Churchsche Hypothese und Äquivalenzsätze, Kleenesche Normaltheoreme, berechenbare Num-merierungen, rekursiv aufzählbare und entscheidbare Mengen, Halteproblem, Kom-plexitätstheorie

Ich denke, mit der Mengenlehre bin ich erstmal auf dem richtigen Weg (Das Buch wird mir mein Prof nicht umsonst empfohlen haben). Man soll ja auch Schritt für Schritt gehen. Halbwissen(-verständnis) bringt ja auch nix. Jedenfalls hätte ich einfach gerne nen guten Überblick über das Defizit von dem, was ich kann, und dem, was ich mir noch aneignen muss.
Aussagenlogik, Prädikatoren, Quantoren, (In)Konsistenzbegriffe - und beweisbarkeit etc hab ich alles super drauf. Modallogik werd ich mir dann wohl auch nochmal anschauen.

greetz
Q

[Unfug]

Vorlesung Algorithmentheorie 2 SWS
In der Vorlesung werden grundlegende Begriffe, Prinzipien und Sätze aus der Algo-rithmentheorie und der Komplexitätstheorie behandelt.
Zu den behandelten Themen gehören: Begriff des Algorithmus und des Kalküls, Tu-ringmaschinen und Registermaschinen, partiell rekursive Funktionen, Churchsche Hypothese und Äquivalenzsätze, Kleenesche Normaltheoreme, berechenbare Num-merierungen, rekursiv aufzählbare und entscheidbare Mengen, Halteproblem, Kom-plexitätstheorie

Dein gekauftes Buch sollte alles davon behandeln...ich habs selber damit gepaukt.

[Quantar]

Ja, denke ich auch. Jedoch hab ich das Buch nach 2 Seiten erstmal bei Seite gepackt, da noch zuviel (nicht identifiziertes) Unwissen vorhanden ist. Weder bin ich ein guter Programmierer, noch bin ich ein Mathecrack. Daher suche ich erstmal nach allem, was mir irgendwie hilft, mein formales Grundverständnis zu verbessern.

[Senior Sanchez]

Das Buch von Schöning ist wirklich ne Empfehlung wert. Ist eine Referenz, vor allem für BWinf-Teilnehmer ;) (Herr Schöning, den ich persönlich kennengelernt habe, denkt sich ja auch die Aufgaben aus)

[Quantar]

Danke, werds mir mal anschauen. Hab hier gerade ein "Shaums Outline". Da gefällt mir besonders gut dran, dass viele Beispiele gebracht werden und ein Haufen Übungsaufgaben samt Lösungen mit drin sind.
Eine Sache würde mich auch mal so interessieren: Hat der "Informatiker" eine Methode, um die Unentscheidbarkeit einer Aussage aus einer Aussage(nklasse) zu beweisen?

[Muh-sagt-die-Kuh]

Theoretische Informatik...das ist ein ziemlich grauseliges Zeugs :nono:

Wie gut, dass die Klausur damals nicht schwer zu bestehen war: Man musste einfach nur die Aufgaben richtig lösen, die nach Schema-F gingen....also völlig ohne Verstehen ;)

[Quantar]

Naja, schon komisch. Bei uns fallen traditionell 80% durch die Logikklausur, die im nachhinein so billig erscheint, dass mir eine Nicht 1 völlig unverständlich erscheint.
Ich habs halt auch selber gemerkt. Das erste Sem nur Bahnhof verstanden, und dann primär aus Panik solange dran gesessen, bis es "Klick" im Hirn machte, und dann nach und nach die Erkentnisse eintrafen.
Ein formales System mit genau 10 Regeln... verstehe nicht (mehr), was daran so schwer sein soll. Knackig wirds erst, wenn man anziehen muss oder so Sachen wie mögliche Unentscheidbarkeit dazu kommen.