/
Informatik Grundlagen
Save to my account
Sign up
Informatik Grundlagen
Informatik Grundlagen
Study
1
Question
Was ist ein Alphabet in der Informatik?
Answer
Ein Alphabet ist eine endliche, nichtleere Menge mit Elementen, die als Zeichen oder Symbole bezeichnet werden.
2
Question
Definiere ein Wort in Bezug auf ein Alphabet.
Answer
Ein Wort ist eine endliche Folge von Zeichen aus einem Alphabet A.
3
Question
Was ist das leere Wort?
Answer
Das leere Wort ist eine spezielle Folge, die keine Zeichen enthält und als Element des freien Monoids A betrachtet wird.
4
Question
Was versteht man unter einem freien Monoid?
Answer
Das freie Monoid A ist die Menge aller möglichen Wörter, einschließlich des leeren Wortes, die aus einem gegebenen Alphabet A gebildet werden können.
5
Question
Was sind formale Systeme und wofür dienen sie?
Answer
Formale Systeme beschreiben interessante Teilmengen eines Alphabets A und bestehen aus einer Menge von Wörtern und Regeln, die definieren, wie neue Wörter aus bestehenden Wörtern gebildet werden können.
6
Question
Was sind die vier Hauptkomponenten eines formalen Systems (F A,B,X,R)?
Answer
F: Das formale System; A: Alphabet; B: Menge der wohlgebildeten Worte; X: Menge der Axiome; R: Produktionsregeln.
7
Question
Was sind Axiome in einem formalen System?
Answer
Axiome sind Grundlagen oder Ausgangswerte, die in der Menge der wohlgebildeten Worte X definiert sind.
8
Question
Definiere Produktionsregeln in einem formalen System.
Answer
Produktionsregeln R sind die Regeln, die beschreiben, wie man neue Wörter B aus den Axiomen X generieren kann.
9
Question
Erkläre das MIU-System und seine Bestandteile.
Answer
Das MIU-System verwendet die Buchstaben M, I, und U als Alphabet. Es umfasst Axiome und Produktionsregeln, um neue Wörter zu erzeugen.
10
Question
Nenne die Axiome des MIU-Systems.
Answer
1. MI, 2. MxI, 3. MxIU.
11
Question
Was ist eine Produktionsregel im MIU-System?
Answer
Eine Produktionsregel im MIU-System würde zum Beispiel MxI zu Mxx oder xUUy zu xy umwandeln.
12
Question
Was ist ein Graph in der Informatik?
Answer
Ein Graph ist eine Menge von Knoten (Ecken) verbunden durch Kanten (Linien). Graphen sind ein grundlegendes Konzept zur Modellierung von Beziehungen.
13
Question
Was ist ein Baum im Bezug auf Graphen?
Answer
Ein Baum ist ein Spezialfall eines Graphen, bei dem es keine Zyklen gibt, und der rekursiv über die Anzahl der Knoten als Teilmenge aller möglichen Graphen definiert wird.
14
Question
Was ist ein Wurzelknoten in einem Baum?
Answer
Der Wurzelknoten ist der Knoten, der keine eingehenden Kanten hat und von dem aus der Baum strukturell verzweigt.
15
Question
Erkläre Blätter in einem Baum.
Answer
Blätter sind Knoten in einem Baum, die keine ausgehenden Kanten haben; sie stellen die Endpunkte der Baumstruktur dar.
16
Question
Was ist ein innerer Knoten in einem Baum?
Answer
Ein innerer Knoten ist jeder Knoten im Baum, der weder der Wurzel noch ein Blatt ist; er hat mindestens eine eingehende und möglicherweise ausgehende Kante.
17
Question
Was ist ein Binärbaum?
Answer
Ein Binärbaum ist eine spezielle Art von Baum, bei dem jeder innere Knoten maximal zwei Kinder hat.
18
Question
Gib ein Beispiel für einen Baum und seine Knoten. Was unterscheidet einen Baum von einem Graphen?
Answer
Ein Beispiel für einen Baum ist der Baum BV,E. Der Unterschied besteht darin, dass ein Baum keine Zyklen hat und immer einen Wurzelknoten hat, während ein Graph Zyklen enthalten kann.
19
Question
Was bedeutet die Bezeichnung "V ' V" im Kontext von Bäumen?
Answer
Das bedeutet, dass V eine Teilmenge von V ist und somit bestimmte Eigenschaften oder Knoten in diesem Kontext darstellen kann.
20
Question
In welche drei Hauptarten können Knoten in einem Baum unterteilt werden?
Answer
Wurzelknoten, innere Knoten und Blätter.
21
Question
Nennen Sie mögliche Variationen von Produktionsregeln im MIU-System.
Answer
Einige mögliche Produktionsregeln sind: 1) MxI → Mxx, 2) xUUy → xy, 3) Mx → MIU, 4) xIIIy → xUy.
22
Question
Was sind die Bedingungen für einen Knoten, um als Blatt in einem Baum zu gelten?
Answer
Ein Knoten gilt als Blatt, wenn er keine ausgehenden Kanten hat, d.h., er ist kein Verzweigungspunkt im Baum.
23
Question
Was ist ein Graph und welche Bestandteile hat er?
Answer
Ein Graph G wird definiert als ein Paar (V, E), wobei V eine Menge von Knoten (vertices) und E eine Menge von Kanten (edges) ist. V ist eine nichtleere Menge, und E besteht aus geordneten Paaren von Knoten (v, w), die eine Kante zwischen den Knoten v und w darstellen.
24
Question
Was ist ein ungerichteter Graph?
Answer
Ein ungerichteter Graph ist ein Graph, bei dem die Kanten keine Richtung haben. Das bedeutet, dass eine Kante (v, w) gleichwertig ist zu (w, v).
25
Question
Was ist ein gerichteter Graph?
Answer
Ein gerichteter Graph, auch Digraph genannt, ist ein Graph, in dem die Kanten eine Richtung haben. Eine Kante (v, w) zeigt von Knoten v zu Knoten w und ist im Allgemeinen nicht gleichwertig zu (w, v).
26
Question
Was ist ein verbundener ungerichteter Graph?
Answer
Ein verbundener ungerichteter Graph ist ein ungerichteter Graph, bei dem es für jeden Knoten möglich ist, von jedem anderen Knoten über eine Folge von Kanten zu erreichen.
27
Question
Was ist ein zyklischer Graph?
Answer
Ein zyklischer Graph ist ein Graph, der mindestens einen Zyklus enthält. Ein Zyklus ist eine geschlossene Schleife, bei der ein Knoten durch eine Folge von Kanten wieder erreicht werden kann.
28
Question
Was ist ein gerichteter azyklischer Graph (DAG)?
Answer
Ein gerichteter azyklischer Graph ist ein gerichteter Graph, der keine Zyklen enthält. Dies bedeutet, dass es unmöglich ist, von einem Knoten zurück zu diesem zu gelangen, indem man den Kanten des Graphen folgt.
29
Question
Was ist eine Turing-Maschine?
Answer
Eine Turing-Maschine ist ein theoretisches Rechenmodell, das aus einem unendlichen Band, einem Schreib-Lesekopf und einer endlichen Menge von Zuständen besteht. Sie wird verwendet, um die Konzepte der Berechenbarkeit und der algorithmischen Problemlösungen zu untersuchen.
30
Question
Nenne die wesentlichen Komponenten einer Turing-Maschine.
Answer
Die wesentlichen Komponenten einer Turing-Maschine sind: 1. Das Band, welches die Eingabe speichert, 2. Der Schreib-Lesekopf, der sich über das Band bewegen kann, 3. Eine Menge von Zuständen, die den aktuellen Status der Maschine darstellen, 4. Eine Übergangsfunktion, die festlegt, welches Zeichen zu schreiben, in welche Richtung sich der Kopf zu bewegen und in welchen Zustand zu wechseln ist, basierend auf dem aktuellen Zustand und dem aktuellen Zeichen.