Theoretische Informatik: Eine algorithmenorientierte Einführung

علوم کامپیوتر نظری قدیمی‌تر از علوم کامپیوتر عملی، کاربردی یا فنی است. بنابراین، به عنوان یک رشته علمی، در حال حاضر توسعه یافته‌تر از سایر حوزه‌های علوم رایانه است و دسترسی به نتایج آن دشوارتر است، زیرا بر پایه‌های بزرگ‌تر و عمیق‌تری بنا شده‌اند. نظریات بسیار منشعب شده تمایل دارند که خود را به عنوان غایتی در خود ببینند و به عنوان هنر pour l'art دنبال شوند. در این مقدمه بر علم کامپیوتر نظری، با تمرکز بر جهت گیری نظریه های مدرن به کاربردها، با این خطر مقابله می کنیم. نوالیس (1772-1801) قبلاً خاطرنشان کرد که نظریه اغلب مقدم بر کاربردها است: "اگر نظریه منتظر تجربه باشد، هرگز به وجود نمی آید." کاربردهای نتایج علم کامپیوتر نظری همیشه آنقدر مستقیم نیست که قابل مشاهده باشد. به عنوان کاربردهای دیگر شاخه های علوم کامپیوتر. این به ویژه در مورد نتایج منفی صدق می کند. عواقب این امر روشن است. اگر ثابت کنیم که ابزارها یا الگوریتم‌هایی که در عمل مطلوب هستند نمی‌توانند وجود داشته باشند، کار بی‌معنی، زیرا ناامیدکننده، روی این ابزارها یا الگوریتم‌ها باید متوقف شود و به جای آن باید جستجو برای بهترین راه ممکن آغاز شود. از سوی دیگر، نتایج مثبت به طور خودکار برنامه محور نیستند. گزاره‌های وجود یا الگوریتم‌هایی با زمان اجرای تصاعدی یا حتی طولانی‌تر اغلب عملاً بی‌ارزش هستند. آنچه در مورد این مقدمه به علم کامپیوتر نظری جدید است، دیدگاه الگوریتم محور است (برای پیشینه آموزشی، به Wegener (1992) مراجعه کنید). در مورد نتایج مثبت، پیاده سازی در الگوریتم های عملی و نظری کارآمد همیشه به دنبال بود.

Die Theoretische Informatik ist älter als die Praktische, Angewandte oder Techni­ sche Informatik. Daher ist sie als wissenschaftliche Disziplin bereits weiter ausgebaut als andere Bereiche der Informatik, und ihre Ergebnisse sind schwerer zugänglich, da sie auf ein größeres und tieferes Fundament aufbauen. Stark verästelte Theorien tendieren dazu, sich als Selbstzweck aufzufassen und als l'art pour l'art betrieben zu werden. In der vorliegenden Einführung in die Theoretische Informatik begegnen wir dieser Gefahr, indem wir die Orientierung moderner Theorien an den Anwendun­ gen in den Mittelpunkt stellen. Schon Novalis (1772~ 1801) hat darauf hingewiesen, daß die Theorie häufig den Anwendungen vorauseilt: "Wenn die Theorie auf die Erfahrung warten sollte, so käme sie nie zustande. " Nicht immer sind die Anwendungen von Ergebnissen der Theoretischen Informatik so direkt zu sehen wie die Anwendungen anderer Zweige der Informatik. Dies gilt insbesondere für negative Resultate. Dabei sind deren Konsequenzen klar. Wenn wir beweisen, daß es bestimmte für die Praxis wünschenswerte Werkzeuge oder Algorithmen nicht geben kann, muß die unsinnige, weil hoffnungslose Arbeit an diesen Werkzeugen oder Algorithmen eingestellt und statt dessen die Suche nach bestmöglichen Auswegen begonnen werden. Andererseits sind positive Resultate nicht automatisch anwendungsorientiert. Exi­ stenzaussagen oder Algorithmen mit exponentieller oder noch größerer Laufzeit sind häufig praktisch wertlos. Das Neue an der vorliegenden Einführung in die Theore­ tische Informatik ist die konsequent algorithmenorientierte Sichtweise (zum didak­ tischen Hintergrund siehe Wegener (1992)). Stets wurde bei positiven Resultaten eine Umsetzung in praktisch und theoretisch effiziente Algorithmen angestrebt.