Theoretische Informatik: Eine kompakte Einführung

این مقدمه فشرده به علم کامپیوتر نظری، مهم ترین مدل ها را برای مسائل محوری در علوم کامپیوتر ارائه می دهد. در میان سؤالات زیر به سؤالات زیر پرداخته می شود:

کدام مسائل را می توان به صورت الگوریتمی حل کرد؟ (نظریه محاسبه پذیری و تصمیم پذیری)

حل مسائل الگوریتمی چقدر دشوار است؟ (نظریه پیچیدگی محاسباتی، نظریه NP)

اصولاً سیستم های پردازش اطلاعات چگونه ساخته می شوند؟ (نظریه خودکارهای محدود)

زبان های برنامه نویسی چه ساختارهایی دارند؟ (نظریه زبان های رسمی)

در توسعه این مباحث، فرآیند انتزاع از موضوعات واقعی علوم کامپیوتر به مدل های ایجاد شده در علوم کامپیوتر نظری، مانند ماشین های دسترسی تصادفی، ماشین های تورینگ و ماشین های محدود. ، بازسازی شده است و بالعکس نشان می دهد که این مدل ها در عمل بر اساس دانش به دست آمده در مورد آنها چه کاری می توانند انجام دهند.

متن حاضر مطالب غنی را برای طراحی یک سخنرانی یک ترم و چهار ساعته ارائه می دهد. مثال‌ها و تکالیف بسیاری درک را تسهیل می‌کنند و امکان کسب مطالب را در خودآموزی فراهم می‌کنند. یک کامپایلر را می توان از سرور نویسنده برای آزمایش برنامه های خودنویس بارگیری کرد.

Diese kompakte Einführung in die Theoretische Informatik stellt die wichtigsten Modelle für zentrale Probleme der Informatik vor. Dabei werden u.a. folgende Fragestellungen behandelt:

Welche Probleme sind algorithmisch lösbar? (Theorie der Berechenbarkeit und Entscheidbarkeit)

Wie schwierig ist es algorithmische Probleme zu lösen? (Theorie der Berechnungskomplexität, NP-Theorie)

Wie sind informationsverarbeitende Systeme prinzipiell aufgebaut? (Theorie der endlichen Automaten)

Welche Strukturen besitzen Programmiersprachen? (Theorie der formalen Sprachen)

In der Erarbeitung dieser Themen wird der Abstraktionsprozeß von den realen Gegenständen der Informatik zu den in der Theoretischen Infromatik etabliertern Modellen, wie z.B. Random-Access-Maschinen, Turingmaschinen und endlichen Automaten, nachvollzogen und umgekehrt verdeutlicht, was diese Modelle aufgrund der über sie gewonnenen Erkenntnisse für die Praxis leisten können.

Der vorliegende Text stellt reichhaltiges Material für die Gestaltung einer einsemestrigen vierstündigen Vorlesung bereit. Viele Beispiele und Aufgaben erleichtern das Verständnis und ermöglichen die Aneignung des Stoffes auch im Selbststudium. Zum Testen selbstgeschriebener Programme kann ein Compiler vom Server des Autors heruntergeladen werden.