Kapitel 8 - Theorie

Question 1

Was ist Theoretische Informatik?

Answer 1

• Theoretische Informatik beschäftigt sich mit Computern anhand von Abstraktionen und Modellen
• Es ist ein Grundlagenfach, vergleichbar mit Mathematik

Question 2

Teilbereiche der Theoretischen Informatik

Answer 2

• Formale Sprachen: struktureller Aufbau von Programmiersprachen -> Spezifikation von Programmiersprachen und Compilern, Sprachübersetzungen durch Maschinen
• Automatentheorie: mathematische Modelle des Computers -> Entwurf von Schaltkreisen
• Berechenbarkeitstheorie: vorhersagen können, für welche Probleme es überhaupt Algorithmen gibt
• Komplexitätstheorie: vorhersagen, mit welchem Aufwand (Laufzeit oder Speicherplatzbedarf) ein Problem lösbar ist

Question 3

Definition: Algorithmus

Answer 3

Vorschrift, nach der ein System Operationen in einer bestimmten Reihenfolge ausführt, um Aufgaben eines Typs zu lösen

Question 4

Nennen Sie die 7 Begriffe aus der Theoretischen Informatik (7)

Answer 4

Question 5

Was ist eine Sprache

Answer 5

= Teilmenge aus der Menge aller möglichen Wörter zu einem Alphabet, z.B.:

• Die Menge aller Wörter, die mit a beginnen
  
  • aaabc ist ein Wort der Sprache, baaac nicht
• Die Menge aller Wörter, die genau sechs Zeichen lang sind.
  
  • aaabbb ist ein Wort der Sprache, aaabb nicht
• Die Menge aller Wörter, die einen sinnvollen deutschen Satz ergeben (wobei man noch genauer definieren muss, was sinnvoll heißt).
  
  • derHundmagdieKatze ist ein Wort der Sprache, derHundHundKatze nicht
• Die Menge aller Wörter, die eine Primzahl darstellen.
  
  • 23 ist ein Wort der Sprache, 24 nicht

Question 6

Reguläre Ausdrücke

Answer 6

• Regulärer Ausdruck = Muster für die Wörter einer regulären Sprache = beschreibendes Konzept für reguläre SPrachen = Buchstaben + Operatoren, um Wörter zu bilden
• Reguläre Ausdrücke werden verwendet zur formalen Beschreibung von zulässigen Eingaben in Dialogmasken
• Wichtig im Computerbau und Software-Technik
• Manche Textverarbeitungsprogramme erlauben reguläre Ausdrücke
• Reguläre Ausdrücke sind äquivalent zum endlichen Automaten

Question 7

Grammatik (Syntax)

Answer 7

• Beschreibung von Sprachen, die aus endlich vielen Wörtern bestehen
• Grammatik: Ableitungsregeln, so dass alle Wörter der Sprache erzeugt werden können.

Question 8

Chomsky-Hierarchie der Grammatiken (4 Typen)

Answer 8

Typ 0

• alle formalen Grammatiken ohne Einschränkung

Typ 1, kontextsensitiv

• für alle Regeln w1 -> w2 gilt |w1|≤|w2| (d.g. die rechte Seite ist nicht kürzer als die linke) bzw. w1 kann eine Symbolfolge sein und muss mindestens ein Nichtterminal-Symbol enthalten

Typ 2, kontextfrei

• Typ 1 UND in jeder Regel der Grammatik muss auf der linken Seite genau ein nicht-terminales Symbol stehen und auf der rechten Seite kann eine beliebige nicht-leere Folge von terminalen und nichtterminalen Symbolen stehen; Grammatik der meisten Programmiersprachen

Typ 3, regulär

• Typ 2 UND auf der rechten Seite genau ein Terminalsymbol und maximal ein weiteres Nichtterminalsymbol; einheitlich immer vor oder immer hinter dem Terminalsymbol, je nachdem linksreguläre oder rechtsreguläre Grammatik

Question 9

Übersicht über Chomsky

Answer 9

Question 10

XML + DTD

Answer 10

• XML = Extensible Markup Language
• Sprache für Datenaustausch
• W3C-Standart
• Kontextfreie Grammatik
• DTD = Document Type Definition = kontextfreie Grammatik, beschreibt Produktionsregeln mit regulären Ausdrücken rechts, wo Nonterminale vorkommen dürfen

Question 11

XML: Darstellung als Baum

Answer 11

• Ein Knoten
  
  • ohne Vorgänger heißt Wurzel-Knoten
  • ohne Nachfolger heißt Blatt
  • mit einem oder mehreren Nachfolger(n) heißt innerer Knoten
• Jeder Knoten hat stets einen Vorgänger und keinen, einen oder mehrere Nachfolger
• Die Nachfolger-Knoten heißen Sohn- oder Kind-Knoten
• Die Vorgänger-Knoten heißen Vater- oder Eltern-Knoten

Question 12

XML als Datenformat

Answer 12

• Daten beschreiben
• Daten speichern
• Daten übertragen
• Datenintegrität sichern
• Dokumente formatieren
• Dokumente in verschiedene Formate transformieren
• In Dokumenten navigieren
• XML als Metasprache, d.h. ist erweiterbar -> neue Sprachen wie SVG, MathML, SBML

Answer 13

• Sprache = Teilmenge aller zu einem Alphabet, durch Grammatik beschrieben
• Regulärer Ausdruck = Muster für Wörter
• Chomsky-Hierarchie der Grammatiken
• Syntaxbaum, Syntaxdiagramm und BNF-Schreibweise veranschaulicht kontextfreie Grammatik
• XML als Auszeichnungssprache, Datenformat und Metasprache