Logo des Repositoriums

Auflistung nach Autor:in "Tantau, Till"

1 - 3 von 3
  • Textdokument
    Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten
    (Ausgezeichnete Informatikdissertationen 2003, 2004) Tantau, Till
    Der Beitrag enthält eine Zusammenfassung der Dissertation n Structural Similarities of Finite Automata and Turing Machine Enumerability Classes. Die Dissertation [Ta03] eröffnet mit folgenden Worten: My Thesis: The enumerability and verboseness classes of finite automata on the one hand and of Turing machines on the other hand share numerous structural properties. They do not share these properties with intermediate resource-bounded computational models. Especially the finite automata versions of these classes have applications in areas unrelated to enumerability. Two methods that are used for the proofs of the structural similarities - elementary definitions of regular relations and branch diagonalisation - will be applicable to other proofs in automata, complexity, and recursion theory. Auf den folgenden 150 Seiten wird dann versucht, mittels etwa sechzig Sätzen, Korollaren und Lemmata diese These zu belegen und den Leser oder die Leserin von ihrer Richtigkeit zu überzeugen - nicht mehr und nicht weniger. Es wird sogar frech behauptet, man könne sich die weitere Lektüre der Arbeit sparen, sobald man von der {\tt>\hskip-.5e>}Thesis{\tt<\hskip-.5e<} überzeugt ist. Mein Hauptanliegen im vorliegenden Beitrag ist zu erläutern, was die obige These eigentlich genau besagt. Mathematische Exaktheit steht dabei weniger im Vordergrund als eine möglichst allgemein verständliche Darstellung der Ideen. Dazu werden zunächst die Konzepte wie Aufzählbarkeit oder Verboseness-Klassen genauer erklärt, dann die zentralen Resultate beschrieben, eine neue Beweismethode kurz angedeutet und zum Schluss Anwendungen skizziert. Die Konzepte 1.1 Turingmaschinen, endliche Automaten und Polynomialzeitmaschinen Schon der Titel der Dissertation verrät, dass es in ihr um Gemeinsamkeiten der beiden ältesten Maschinenmodelle der Informatik geht: Turingmaschinen und endliche Automaten. Grob gesprochen ist das Turingmaschinenmodell das mächtigste {\tt>\hskip-.5e>}sinnvolle{\tt<\hskip-.5e<} Maschinenmodell, das es gibt. {\tt>\hskip-.5e>}Mächtig{\tt<\hskip-.5e<} bedeutet hier, dass Turingmaschinen alles berechnen können, was sich überhaupt berechnen lässt. Da unklar ist, was die richtige Definition von {\tt>\hskip-.5e>}was sich überhaupt berechnen lässt{\tt<\hskip-.5e<} ist, ist es kein mathematischer Satz, dass Turingmaschinen allmächtig sind, sondern lediglich eine These, die aber der klangvollen Namen {\tt>\hskip-.5e>}Church'sche These{\tt<\hskip-.5e<} trägt. Praktisch kann man sich eine Turingmaschine als einen Rechner vorstellen, der über beliebig viel Speicher verfügt und der beliebig lange rechnen darf. Am anderen Ende des Spektrums der Maschinenmodelle finden sich die endlichen Automaten. Diese verarbeiten ihre Eingabe, indem sie sie einmal von links nach rechts lesen und am Ende sofort eine Ausgabe produzieren. Endliche Automaten benötigen keinerlei Speicher und ihre Rechenzeit ist proportional zur Eingabelänge. Vom praktischen Standpunkt aus sind Turingmaschinen viel zu mächtig, da sie Probleme spielend lösen können, die nachweislich nicht in vertretbarer Zeit (wie beispielsweise der zu erwartenden Lebensdauer des Universums) zu lösen sind. Endliche Automaten sind nicht mächtig genug, da sie manche Probleme nachweislich nicht lösen können, die ein Taschenrechner mit links löst. In der Komplexitätstheorie werden deshalb Modelle wie Polynomialzeitmaschinen betrachtet, die {\tt>\hskip-.5e>}in der Mitte liegen{\tt<\hskip-.5e<} und die die Fähigkeiten realer Computer realistischer modellieren.
  • Conference Proceedings
    Informatik fürs Leben lernen
    (INFOS 2021 – 19. GI-Fachtagung Informatik und Schule, 2021) Tantau, Till
    Eine Debatte um die Frage, welche Inhalte und Themen die informatische Bildung an Schulen umfassen muss, sollte weit nach vorne blicken: Weniger die aktuellen Trends in der Wirtschaft oder Forschung erscheinen richtungsweisend, sondern was in 25 oder noch mehr Jahren immer noch oder wieder relevant ist. Ein solch weiter Blick in die Zukunft der Informatik ist natürlich ausgesprochen schwierig, da sich die Informatik, seit sie existiert, in einem ständigen Umbruch befindet. Er soll hier trotzdem versucht werden und daraus verschiedene Konsequenzen für die mögliche Gestaltung und Entwicklung des Informatikunterrichts in der Gegenwart abgeleitet werden. Einerseits ergibt sich, dass es mehrere „zeitlose“, grundlegende und spezifisch informatische Ideen gibt, die dauerhaft Teil der allgemeinen Bildung sein sollten. Andererseits sind die typischen Gegenstände der Wissenschaft Informatik – wie Code oder Systeme oder Protokolle – immer weniger für sich stehende, rein technische Artefakte, sondern vielmehr in komplexe soziale Kontexte eingebettete Produkte menschlicher Kollaboration. Neben einem prinzipiellen Verständnis technischer Aspekte wird daher das Wissen um die Entstehung, Entwicklung und Nutzung von Code oder Systemen durch Menschen zentraler Bestandteil einer auf die Zukunft ausgerichteten informatischen Bildung sein.
  • Konferenzbeitrag
    Tutorien
    (Informatik 2009 – Im Focus das Leben, 2009) Tantau, Till