# Selbstcheck Fragen GLINF
## Eigenstudium A: Zahlensysteme, Informationstheorie und Logik
* Die Integer-Zahl 567 vom Zehner- in das Binär- Oktal- und Hexadezimalsystem umzuwandeln.
* Die Floating-Point-Zahl 49.25 (Zehnersysystem) im Binärsystem mit 4 Bit Exponent (Bias: 3) und 6 Bit Mantisse darstellen.
* Erklären was der Huffman-Code ist und wie man für eine gegebene Häufigkeitsverteilung einen Code berechnet.
* Feststellen ob die aussagenlogische Fomel ((a & -b) | b) -> -a erfüllbar ist.

## Eigenstudium B: Einführung in Formale Grundlagen der Informatik
* Erklären was ein Alphabet, eine formale Sprache und Wörter (im mathematisch-präzisen Sinne!) sind.
* Ein Beispiel für ein Alphabet, eine formale Sprache und ein Wort geben können.
* Operationen nennen, die über formalen Sprachen möglich sind.
* Erklären was man in der Informatik unter einem Entscheidungsproblem (decision problem) versteht, und wie dieses mit formalen Sprachen zusammenhängt.

## Eigenstudium C: Arten und Repräsentationsmöglichkeiten von formalen Sprachen (mit Fokus auf Typ-3-Sprachen)
* Den Unterschied zwischen Sprachen und regulären Ausdrücken erklären können.
* Mehrere Repräsentationsmöglichkeiten für formale Sprachen nennen und diese an einem Beispiel demonstrieren können.
* Erklären was die Chomsky-Hierarchie ist.
* Einen deterministischen endlichen Automaten für eine selbst gewählte Sprache konstruieren können.
* Erklären, was es für eine Sprache bedeutet "reguläre" zu sein.

## Eigenstudium D: Weitere Typen formaler Sprachen (Typ-2, Typ-1 und Typ-0)
* Erklären was eine formale Grammatik ist, und wie diese mit Sprachen zusammenhängt.
* Den Zusammenhang zwischen Automaten, regulären Ausdrücken, und formalen Grammatiken erklären können.
* Ein Beispiel für eine Sprache nennen können, die nicht regulär ist.
* Eine Grammatik für die Sprache L = { a^n b^n | n >= 0 } konstruieren können, und wissen ob diese Grammatik regulär ist (mit Begründung).

## Eigenstudium E: Turing-Maschinen, Algorithmen und Komplexität
* Erklären was eine Turing-Maschine ist (sowohl intuitiv/anschaulich als auch im mathematisch-präzisen Sinne).
* Eine Turing-Maschine konstruieren, die am Eingabeband eine Binärzahl erwartet und diese um 1 hochzählt.
* Erklären wie Turing-Maschinen und reale Computer zusammenhängen.
* Angenommen Ihr Rechner hätte unbeschränkt viel Arbeitsspeicher. Was ist mächtiger: eine Turing-Maschine oder die Programmiersprache C? (Ignorieren Sie dabei die Benutzerfreundlichkeit und analysieren Sie nur die grundsätzlichen Möglichkeiten.)
* Erklären wie Turing-Maschinen mit deterministischen endlichen Automaten zusammenhängen, und welchen Platz sie in der Chomsky-Hierarchie einnehmen.
* Beispiele nennen können, wozu das Konzept von Turing-Maschinen in der Praxis relevant ist.
* Ein Beispiel für ein Problem nennen können, das zwar präzise definiert ist, das man aber trotzdem nicht mit einem Computerprogramm lösen kann.
* Erklären was eine Komplexitätsklasse im Allgemeinen ist, und konkret was man unter der Komplexitätsklasse P versteht.
* Erklären können worum es beim berühmten P vs. NP-Problem geht und wieso die (offene) Antwort auf dieses Problem höchst praxisrelevant ist.

---

# Musterprüfung
1. Number systems
a. Convert the octal number 721 to octal and hexadecimal. Write down all intermediate results!
b. Calculate the normalized floating point representation with bias 3 of -2.0625. Use 1 bit for the sign, 3 bit for the exponent and 8 bit for the mantissa.
2. Finite Automata
a. Design a finite automaton that accepts all strings of alternating characters over alphabet {x, y} (including the empty sequence). That is, the same character must not appear twice in the sequence. *Draw the state diagram of the automaton and specify the transition function also as table.*
b. Suppose there is a finite automaton accepting a certain regular language. Is there always a Turing machine accepting the same language? Justify your answer.
3. Regular Expressions and Grammar
For the given alphabet Σ = \{a, b, c, d\} and the regular expression
REXP: ((ab\*|bc\*)db\*b) complete the following tasks:
a. Write down 3 strings of the language of the regular expression.
b. Draw the state diagram of a DFA accepting this language.
c. Is there a regular grammar generating the same language as matched by the above REXP? You don’t have to create such a grammar, but explain why it exists or does not exist.
d. Consider the following grammar:

    G = ({a,b,c}, {S}, P, S) with P = { S -> aSb, S -> SS, S -> c }.

Is the grammar regular? Justify your answer.
e. Describe the strings matched by the following regex and give an example of such a string:

    ^(([0-1][0-9])|(2[0-3])):([0-5][0-9)UTC[+-]((0?[0-9])|(1[0-2]))$

4. Turing Machines and Complexity
a. Can Turing machines solve any computational problem? Justify your answer.
b. Explain what the concept of Turing machines is used for (applications).
c. The complexity classes P and NP are fundamental in computer science. What would it mean in practice if P=NP?
d. Can a computer solve any computational problem? If yes, justify your answer, if no, give an example of a problem that cannot be solved.