{"id":2074,"date":"2013-06-15T21:57:05","date_gmt":"2013-06-15T19:57:05","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?page_id=2074"},"modified":"2025-11-25T23:24:52","modified_gmt":"2025-11-25T22:24:52","slug":"theoretische-informatik-a","status":"publish","type":"page","link":"https:\/\/fernuni.digreb.net\/?page_id=2074","title":{"rendered":"01657\/01658 – Theoretische Informatik"},"content":{"rendered":"\n

Hier findet Ihr meine Zusammenfassungen und Erl\u00e4uterungen zur theoretischen Informatik (01657 und 01658).<\/p>\n\n\n\n

Diese Zusammenfassungen hier habe ich eig. nur f\u00fcr mich erstellt und habe sie sp\u00e4ter einigen Kommilitonen zur Verf\u00fcgung gestellt um ihnen etwas Zeit zu sparen, da der Stoff in der dargestellten Form doch eher schwer verdaulich ist. Au\u00dferdem gibt es ein Problem mit der Sekund\u00e4rliteratur, da bestimmte Dinge im Skript einfach anders definiert sind. Sie sind zwar dennoch korrekt, aber auch bestimmten Gr\u00fcnden besteht im Skript z.B. etwas aus einem 4-Tupel und in der Literatur aus einem 5-Tupel, usw.<\/p>\n\n\n\n

Da die Zusammenfassungen den Mitstudenten anscheinend ganz gut beim Verst\u00e4ndnis der Materie halfen (wenn ich der positiven Resonanz glauben darf), habe ich beschlossen sie online zu stellen. Vielleicht helfen sie euch auch.<\/p>\n\n\n\n

Thema Copyright<\/strong><\/p>\n\n\n\n

Die Fragestellungen und einige Inhalte stammen aus dem Skript der FernUni Hagen,<\/a> das Copyright liegt also dort. Stellen, die ich aus dem Buch von Dirk W. Hoffmann oder Rolf Socher entnommen habe sind ebenfalls markiert. Ich habe mich bem\u00fcht alle Bilder selbst zu erstellen, nur CC–Bilder zu verwenden oder mindestens die Quelle zu nennen. Wenn irgendwo was fehlt oder ich euer Bild verwendet haben sollte, was ihr nicht wollt, bitte ich um eine kurze Mail an mich<\/a>. Ich entferne es direkt.<\/p>\n\n\n\n

Ganz wichtig<\/strong><\/p>\n\n\n\n

Auch wenn ich die Zusammenfassungen nach bestem Wissen und Gewissen angefertigt habe, gibt es sicherlich noch irgendwo den ein oder anderen Fehler. Aber nichts st\u00f6rt den Lernprozess so wie diese. Erkl\u00e4rungen werden nicht nachvollziehbar wenn man nicht auf das selbe Ergebnis kommt wie der Autor. Sollten euch daher grobe Schnitzer auffallen, bitte sofort per Mail oder in den Kommentaren melden. Danke!<\/p>\n\n\n\n

Behaltet aber eines im Hinterkopf:<\/p>\n\n\n\n

\n
Die absolute Autorit\u00e4t hat nur das Skript! Nur das Skript bereitet euch auf die m\u00fcndliche oder schriftliche Pr\u00fcfung vor!<\/strong><\/div>\n
Da die Erl\u00e4uterungen hier aus meinem Kopf stammen und weder vom Prof. oder sonstwem auf Korrektheit gepr\u00fcft wurden, ist hier alles ohne Gew\u00e4hr.<\/strong><\/div>\n<\/div>\n\n\n\n

<\/p>\n\n\n\n

Auch sollten die Zusammenfassungen h\u00f6chstens erg\u00e4nzend zum Skript verwendet werden wenn Ihr mal eine andere Sicht auf die Dinge braucht weil ihr im Skript nicht weiterkommt. Nur das Skript ist wirklich verbindlich!<\/p>\n\n\n\n

\n
Update nach der m\u00fcndlichen Pr\u00fcfung<\/strong><\/div>\n
Nach der Pr\u00fcfung habe ich beschlossen ein kurzes Statement online zu stellen, dass euch beim Lesen immer an eine Kleinigkeit erinnert: dass das Skript ist die einzige, g\u00fcltige und verbindliche<\/span> Quelle f\u00fcr Einsendeaufgaben, die schriftliche oder m\u00fcndliche Pr\u00fcfung ist. Und das ist jetzt nicht einfach so dahingesagt.<\/div>\n
Die Mathematik ist eine exakte Wissenschaft, wo es keinen Raum f\u00fcr Interpretationen gibt. Sie besitzt eine eigene Terminologie und ist pr\u00e4zise, d.h. es gibt keinerlei F\u00fcllw\u00f6rter. Jedes Wort ist ein Informationstr\u00e4ger!<\/div>\n
Wenn in der Definition z.B. steht, dass „Eine Funktion \\(u_\\varphi\\) ist berechenbar…<\/em>„, dann ist die Aussage „Es gibt eine Funktion \\(u_\\varphi\\)…<\/em>“ schlicht falsch. Dass Ihr aber im Detail erkl\u00e4ren k\u00f6nnt, was \\(u_\\varphi\\) macht n\u00fctzt euch ab hier nicht mehr viel, die gegebene Antwort war nicht richtig und 0 Punkte wert.<\/div>\n
Wenn eine Funktion z.B. partiell definiert ist, schadet es nicht zu wissen, warum. Dazu solltet ihr aber vorher wissen, dass die partiell definiert ist und es in der Antwort auch sagen! Besagt die Definition „\\(f_n\\) ist eine partielle Funktion…<\/em>„, so ist eine Antwort mit „\\(f_n\\) ist eine Funktion…<\/em>“ falsch und ihr kommt noch nicht einmal dazu, zu erl\u00e4utern was sie tut warum sie partiell ist. Selbst wenn Ihr es wisst.<\/div>\n
Auch wenn der Kern der Funktion nicht ihre Partialit\u00e4t ist, sondern sie uns eine kalte Fusion erm\u00f6glicht, der Beweis f\u00fcr das Higgs-Teilchen ist oder uns alle NP-Probleme deterministisch in polynomieller Zeit l\u00f6st und ihr das alles im Detail erkl\u00e4ren k\u00f6nnt: „\\(f_n\\) ist eine Funktion…<\/em>“ ist eine falsche Antwort.<\/div>\n
Nur das Verst\u00e4ndnis wie etwas funktioniert reicht also nicht aus! Es gibt bestimmte Dinge, die man sich einfach exakt<\/strong> merken und auf Knopfdruck parat haben muss. Dazu geh\u00f6ren die vielen S\u00e4tze und Theoreme im Skript. Ich empfehle euch daher diese in jedem Fall pr\u00e4zise wiedergeben zu k\u00f6nnen. Vielleicht nicht alle, aber die wichtigsten. Erst anschlie\u00dfend spielen Details (wie ist die Beweisidee, warum genau nur partiell, was ist das \\(u\\) in \\(u_\\varphi\\), …) eine Rolle.<\/div>\n
Wie gesagt: Wenn die Antwort ungenau und damit falsch war, kommt Ihr nicht einmal so weit um zeigen zu k\u00f6nnen, dass ihr den Rest verstanden habt.<\/div>\n
Deswegen mein Rat<\/span>: Lest nur das Skript. Kommt Ihr beim Verst\u00e4ndnis nicht weiter, besorgt euch eine andere Perspektive. Hier oder in Sekund\u00e4rliteratur (sofern m\u00f6glich, siehe oben). Dann schwenkt wieder zum Skript, vollzieht evtl. den Beweis nach oder verinnerlicht euch min. die Beweisidee und merkt euch die zum Thema wichtigen S\u00e4tze und Theoreme exakt so wie sie stehen. Selbst wenn es auswendig lernen bedeutet.<\/div>\n
Viel Erfolg bei dem Kurs!<\/div>\n<\/div>\n\n\n\n

<\/p>\n\n\n\n

PS: Ihr merkt aus den obigen Zeilen, dass ich mit der Pr\u00fcfung nicht so ganz zufrieden war. Ich habe bestanden. Aber nicht so gut, wie ich das gerne h\u00e4tte und wie das dem Aufwand, den ich betrieben habe entsprechen w\u00fcrde.<\/p>\n\n\n\n

Das lag aber nicht am Prof., sondern einfach an der Tatsache, dass ich mich habe von dem Gedanken leiten lassen, das Verst\u00e4ndnis der Materie und der Zusammenh\u00e4nge w\u00fcrde ausreichen. Denn darum ginge es ja letztendlich: etwas zu verstehen. Die genauen Definitionen seien etwas, was man zur Not w\u00fcrde nachschlagen k\u00f6nnen. Das ist leider nicht richtig. Bestimmte Dinge m\u00fcssen einfach „sitzen“ und exakt formuliert werden k\u00f6nnen.<\/p>\n\n\n\n

H\u00e4tte ich das vorher gewusst, h\u00e4tte ich mich anders vorbereitet. Mehr im Stil von BGB als im Stil von Software Engineering.<\/p>\n\n\n\n

Das hat aber nichts mit dem Prof. oder der Pr\u00fcfung zu tun. Diese ist fair, der Prof. sehr nett und die Benotung wohlwollend. Macht euch also dar\u00fcber keine Gedanken. Lernt aber nicht nur f\u00fcr das Verst\u00e4ndnis der Materie, sondern lernt auch, euch mathematisch pr\u00e4zise genug auszudr\u00fccken um die wichtigen Definitionen ohne F\u00fcllw\u00f6rter oder Ungenauigkeiten benennen zu k\u00f6nnen.<\/p>\n\n\n\n

Ich wei\u00df, dass genau dies ein Problem bei einem Fernstudium ist. Denn das h\u00f6chste der Gef\u00fchle ist, dass man gelegentlich mit den Mitstudenten skyped oder sich auch mal in der Lerngruppe trifft. Das reicht aber leider nicht, denn i.d.R. ist der Mitstudent auch nicht so tief in der Materie drin, dass er Ungenauigkeiten direkt erkennt und euch darauf hinweist. Man spricht dar\u00fcber, erkl\u00e4rt es einander und gut ist’s. Das ist aber nicht genug.<\/p>\n\n\n\n

Daher nehmt auch, selbst wenn ihr meint alles verstanden zu haben, die Gelegenheit wahr an den Studientagen oder den Mentoriaten teilzunehmen, bearbeitet die Einsendeaufgaben so gut es halt geht und schreibt die Leistungsnachweise. Nutzt jede Gelegenheit um euch in Genauigkeit zu \u00fcben. Es geht hier schlie\u00dflich um Mathematik und nicht um Politik \ud83d\ude09<\/p>\n\n\n\n

\n\n\n\n

Zusammenfassungen theoretische Informatik A (01657)<\/h1>\n\n\n\n
\n\n\n\n

Kurseinheit 1<\/span><\/strong><\/p>\n\n\n\n

Die erste Kurseinheit der theoretischen Informatik A beginnt mit Flussdiagrammen, Einzelschritt-, Schrittzahl- und Gesamtschrittfunktionen und ihrer Semantik. Anschlie\u00dfend geht es von Maschinen \u00fcber Registermaschinen mit nur drei Grundoperationen zu verallgemeinerten Registermaschinen mit komplexeren M\u00f6glichkeiten.<\/p>\n\n\n\n

Diese nutzen wir um zu beweisen, dass Zahlenfunktionen berechenbar sind und weisen das anhand einiger Beispiele auch mittels vollst\u00e4ndiger Induktion \u00fcber die Einzelschrittfunktion nach.<\/p>\n\n\n\n

TIA: Flussdiagramme, Registermaschinen und berechenbare Zahlenfunktionen (Lernziele KE1)<\/strong><\/a><\/p>\n\n\n\n