Theoretische Grundlagen der Informatik
Jo lecko mio... Wenn die Kartei "Theoretische Grundlagen der Informatik" heisst... Was wird da wohl drinne sein? Chinesische Kochrezepte? Alttibetanische Liedtexte? Englisch für Daheimgebliebene... MENNO!
Jo lecko mio... Wenn die Kartei "Theoretische Grundlagen der Informatik" heisst... Was wird da wohl drinne sein? Chinesische Kochrezepte? Alttibetanische Liedtexte? Englisch für Daheimgebliebene... MENNO!
3.18. Was sind kontextsensitive Sprachen?
G heißt kontextsensitiv, wenn alle Regeln von folgender Form sind:
a → b mit |a| <= |b|
Auf linker Seite jeder Regel stehen nicht mehr Symbole als rechts (Beipiel wenn links aB → ab, darf recht NIE mehr sein wie z.B aBC → ab
Ausnahme: S →ε ist erlaubt, wenn S NIE auf einer rechten Seite vorkommt
Daher wandelt man immer die einfachsten Variablen zuerst um (von links nach rechts)
Beispiel Grammatik: G = (V,Σ,P,S) mit:
V = {S,B,C}
Σ = {a,b,c}
P = { S → aSBC | aBC, CB → BC, aB → ab, bB→ bb, bC → bc, cC → cc} L(G) = {abc,aabbcc,aaabbbccc,aaaabbbbcccc,...} =
L(G)={anbncn |n>=1}
3.19. Was ist ein linear beschränkter Automat?
- Nichtdeterministischer LBA == ähnlich Turingmaschinen
- einziger Unterschied, dass zugänglicher Teil des Bandes durch Größe der Eingabe beschränkt ist
- akzeptieren genau die Typ-1-Sprachen (kontextsensitive Sprachen) - ob dies auch auf deterministische LBA zutrifft, ist ein noch offenes Problem
3.20. Was ist der Unterschied zwischen deterministischen und nichtdeterministischen linear beschränkten Automaten?
δ (Delta) == Übergangsfunktion/relation
Wenn δ == Zustandsübergangsfunktion -> deterministischen LBA
Wenn δ == Zustandsübergangsrelation -> nicht-deterministischen LBA
Funktion: es gibt maximal einen einzigen y-Wert für einzelne x-Werte.
Relation: es gibt mehrere y-Werte für einzelne x-Werte.
3.21. Was sind Typ-0 Sprachen?
• Sprachen ohne Einschränkungen bezüglich der Regeln!
Beispiel für eine „Sprache“, die Typ-0, aber nicht Typ-1 ist, ist das Halteproblem für Turingmaschinen
Das Halteproblem beschreibt Frage, ob Ausführung eines Algorithmus zu einem Ende gelangt – normal für viele Algorithmen leicht zu beantworten. Alan Turing konnte mit einer Turingmaschine beweisen, dass es keinen Algorithmus gibt, der diese Frage für alle möglichen Algorithmen und beliebige Eingaben beantwortet.
3.22. Was ist eine Turingmaschine?
- Zu jeder Sprache (erzeugt in freien Grammatik) gibt es eine Turingmaschine, die diese Sprache erkennt
- Zu jeder Turingmaschine gibt es eine rekursiv aufzählbare Sprache, die von dieser Turingmaschine erkannt wird
Aufbau:
Eine Turingmaschine hat ein Steuerwerk, in dem sich das Programm befindet, und besteht außerdem aus
- einem unendlich langen Speicherband mit unendlich vielen sequentiell angeordneten Feldern
- pro Feld kann genau ein Zeichen aus einem vordefinierten Alphabet gespeichert werden
- zusätzliches Zeichen ist ein Blank („unbeschrieben“) zugelassen == leeres Feld auf Speicherband
- einem programmgesteuerten Lese- und Schreibkopf
- bewegt sich feldweise auf Speicherband und verändert / löscht Zeichen
Die Turingmaschine modifiziert die Eingabe auf dem Band nach dem festgelegten Programm
Startposition == Anfang des Eingabeworts, d. h. an der Position des ersten Eingabezeichens
3.23. Was kann eine Turingmaschine?
- Modifiziert die Eingabe auf dem Band nach dem festgelegten Programm
- Startposition ist Anfang des Eingabeworts (erstes Eingabezeichens)
- Jeder Schritt besteht aus
- Lese-Schreib-Kopf lest aktuelles Zeichen
- überschreibt dieses mit dem neuen Zeichen
- bewegt sich dann ein Feld nach links oder rechts oder bleibt stehen
- Welches Zeichen geschrieben wird und welche Bewegung ausgeführt wird, hängt ab von:
- Vorgefundenem Zeichen an aktueller Position
- Zustand in dem sich Turingmaschine gerade befindet
- Definiert durch Überführungsfunktion in der Turingmaschine
- Anzahl der Zustände, in denen sich die Turingmaschine befinden kann, ist endlich
- Ein Zustand kann mehrere Male durchlaufen werden und sagt nicht über die Zeichen auf dem Band aus
- Sie stoppt wenn für den aktuellen Zustand und das gelesene Bandsymbol keine Überführung zu neuem Zustand
- definiert ist
- hängt immer von Kombination aus Zustand und Symbol ab
- Zustände in denen unabhängig vom gelesenen Bandsymbol angehalten wird bezeichnet man als Endzustände
- Es gibt auch Turingmaschinen, die für gewisse Eingaben niemals stoppen
Ablauf vereinfacht:
Auf einem Band steht das Wort „Anna“
- Start an Startposition
- Einlesen Zeichen „A“
- Überschreiben des Zeichens mit „neuem/gleichem“ Zeichen aufgrund Überführungsfunktion
- Bewegt sich nach rechts aufgrund der Überführungsfunktion
- Einlesen Zeichen „n“
- Überschreiben des Zeichens mit „neuem/gleichem“ Zeichen aufgrund Überführungsfunktion
- Bewegt sich nach rechts aufgrund der Überführungsfunktion
- Einlesen Zeichen „n“
- Überschreiben des Zeichens mit „neuem/gleichem“ Zeichen aufgrund Überführungsfunktion
- BewegtsichnachrechtsaufgrundderÜberführungsfunktion
- EinlesenZeichen„A“
- ÜberschreibendesZeichensmit„neuem/gleichem“ZeichenaufgrundÜberführungsfunktion
- BewegtsichnachrechtsaufgrundderÜberführungsfunktion
- Einlesen „Blank“ – Endposition in diesem Beispiel aufgrund fehlender Überführungsfunktion
3.24. Wie unterscheidet sich eine Turingmaschine von einem linear beschränkten Automaten?
- Linear beschränkter Automat (LBA) -> verlässt den Bereich des Bandes auf dem die Eingabe steht nicht
- Während der Berechnung wird daher nur der Teil des Bandes benutzt, auf dem zu Beginn das Eingabewort stand -> begrenzter Speicher
3.25. Was ist der Unterschied zwischen deterministischen und nichtdeterministischen endlichen Turingmaschinen?
Zu jeder nicht-deterministischen Turingmaschine gibt es deterministische Turingmaschine, die dieselbe Sprache erkennt.
Trotz dem Unterschied (Funktion / Relation) der deterministische und nicht-determin. Turingmaschinen sind diese als äquivalent anzusehen, da die eine mit Relationen paralleler arbeiten kann und die mit Funktionen seriell abarbeitet, Aufgrund der Leistung und des unbegrenzten Speichers können beide trotzdem mit dem Input der anderen umgehen.
3.26. Was versteht man unter Language Security?
- Sichere Eingabeprüfung
- Ausschließlich erlaubte Eingaben akzeptieren
- Eingaben immer gleich und sicher interpretieren o Keine unvorhergesehene Reaktion auf Eingaben
- Identische Interpretation auf beiden Seiten einer Schnittstelle
- Die Sprache des Senders muss gleich der Sprache des Empfängers sein
- Design Contracts müssen explizit definiert und überprüfbar eingehalten werden
3.27. Wie kann man eine Schwachstelle in einem Interface theoretisch beschreiben?
M...Message - Dec...Entschlüsselung - Enc...Verschlüsselung
M != Dec(Enc(M)) – Nachricht =! Dieselbe Nachricht nach Ver-und Entschlüsselung
M ist semantisch gültig für den Sender – Nachricht vom Sender ist richtig versendet
Dec(Enc(M)) ist semantisch gültig für den Empfänger – Verarbeitete Nachricht ist logisch richtig
Die Verarbeitung von M beim Empfänger ist nicht gleich der Verarbeitung von Dec(Enc(M)) beim Empfänger
Schlussfolgerung: Da Nachricht A versendet wird und semantisch richtig ist, jedoch beim Empfänger B (ebenfalls semantisch richtig) verstanden wird!!! -> Schwachstelle
3.28. Welche Vorgangsweise sollte man im Sinne der Language Security wählen, damit Input Validation vollständig möglich ist?
Erlaubten Input so einfach wie möglich halten!
Erlaubten Input exakt als formale Sprache definieren
Input Validation als Parser implementieren
Parser mit einem validierten Parser-Generator erzeugen!
3.29. Welche Vorgangsweise sollte man im Sinne der Language Security wählen, damit ein Protokoll sicher implementiert werden kann?
Protokoll so einfach wie möglich halten!
Protokoll exakt als formale Sprache definieren!
Protokoll überall als Parser implementieren!
Parser mit einem validierten Parser-Generator erzeugen!
4.1. Was ist der Unterschied zwischen rekursiven und rekursiv-aufzählbaren Sprachen?
Rekursiv aufzählbare Sprache S == Es gibt Turingmaschine, die alle Wörter aus S akzeptiert, aber keine Wörter, die nicht in S liegen
- Rekursiven Sprachen sind rekursiv aufzählbar (Teilmenge von S).
Unterschied zwischen rekursiven Sprachen und rekursiv-aufzählbaren Sprachen:
- rekursiven Sprachen (entscheidbare Sprachen)
- Turingmaschine muss halten
- Rekursiv aufzählbaren Sprachen
- Turingmaschine muss nicht halten, wenn Wort nicht in LL liegt -> möglich, dass man auf Lösung unendlich lange warten muss
4.2. Wie ist das Wortproblem formal definiert?
Das Wortproblem in einer formalen Sprache ist das Problem festzustellen, ob ein gegebenes Wort zur Sprache gehört, oder nicht.
Das Wortproblem für
Typ-0-Sprachen ist rekursiv aufzählbar und nicht entscheidbar.
Typ-1-Sprachen ist entscheidbar
Typ-2-Sprachen ist durch den Cocke-Younger-Kasami-Algorithmus lösbar
Typ-3-Sprachen ist durch deterministische endliche Automaten lösbar.
4.3. Was ist der Unterschied zwischen abzählbar unendlich und überabzählbar unendlich?
- abzählbar unendlich
- Eine Menge M heißt abzählbar, wenn eine Bijektion zwischen der Menge M und den natürlichen Zahlen existiert.
- Bijektion == Jedem Element aus einer Menge ist ein Element aus einer anderen Menge zugeordnet
- Beispiele: Natürliche Zahlen, Primzahlen, Ganze Zahlen (Jede Zahl hat dieselbe Mächtigkeit wie sie selbst)
- überabzählbar unendlich
- Eine Menge M heißt überabzählbar, wenn sie weder endlich noch abzählbar ist.
- Beispiel: Die Menge aller Teilmengen (=Potenzmenge) einer Menge wenn die Menge unendlich viele Elemente hat.
4.4. Was ist die Church-Turing-These?
Die Turingmaschine muss ja oder nein sagen und muss stehen bleiben (sie “hält”, endliche Antwortzeit).
“Die Klasse der turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.”
Diese These ist nicht beweisbar, da der Begriff „intuitiv berechenbare Funktion“ nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auf irgendeine Weise berechnet werden könnten. Damit setzt man insbesondere keine Vorstellung voraus, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Es wird in der Informatik üblicherweise angenommen, dass die These stimmt. Dadurch kann es ermöglicht werden, von einer Funktion nachzuweisen, dass sie nicht berechenbar ist.
4.5. Wann ist ein Problem entscheidbar?
Wenn die Turingmaschine hält. Wenn zu einer Eingabe in endlicher Zeit eine Antwort geliefert wird.
4.6. Was versteht man unter dem Halteproblem von Turingmaschinen?
Ob eine Turingmaschine - mit einem Eingabewort gestartet - halten wird oder nicht.
Ja = Bleibt sie stehen
Nein = Kann sie unendlich lang weiterlaufen
Ein Programm welches ein anderes Programm analysiert ob es eine Endlosschleife enthält oder nicht. (Kann sich das Programm selber analysieren ob es nicht selber in einer Endlosschleife durchläuft? Nicht möglich!)
4.7. Was sagt der Unvollständigkeitssatz von Gödel aus?
1.Satz:
Ein formales System kann nicht logisch konsistent und zugleich vollständig sein. - Hängt sich ein Programm auf kann es nicht logisch konsistent sein
2. Satz:
Ein logisch konsistentes System ist nicht in der Lage seine eigene logische Konsistenz zu beweisen.
- Das Programm führt sich selbst mit einem Parameter aus welcher dazu führt, dass sich das Programm aufhängt. Das Programm ist jedoch nicht in der Lage festzustellen, dass sich die von ihm aufgerufene Instanz seiner selbst aufgehängt hat! Somit kann es in diesem Fall auch selbst nicht terminieren.
- Das Programm kann sich nicht selber testen ob es “logisch” ist.
1.14. Welche Sprachen zur Formulierung formaler Modelle gibt es?
Programmiersprachen
Automaten
Logiken
Lambda Kalkül (Sprache zur Untersuchung von Funktionen)
1.1. Was ist eine Theorie, was ein Modell?
Eine Theorie ist ein vereinfachtes Bild (Modell) eines Ausschnitts der Realität
-> Auf dieser Basis sind Prognosen möglich. Im Allgemeinen entwirft eine Theorie ein Modell der Realität.
Ein Modell ist eine Beschreibung eines Ausschnitts der Realität. Beschreibung ist Information!
1.2. Geben sie Beispiele für Modelle
Automodell / Modelleisenbahn / Flugzeugmodelle
Modell eines Hauses / der Einrichtung / Stadtplan
Bienenmodell (Eltern - Kinder / männlich - weiblich)
Medikamentenmodell (4 verschiedene Herangehensweisen - 3D, 2D, chem. Formel, Name Ibuprofen)
Atommodell (Nils Bohr)
1.3. Beschreiben sie den Zusammenhang zwischen Theorie - Modell - Information
Eine Theorie ist ein vereinfachtes Bild (Modell) eines Ausschnitts der Realität – die Basis dafür sind Axiome, nicht beweisbare Annahmen und daraus entsteht dann das Modell
Das Modell ist die Beschreibung eines Ausschnitts der Realität
Beschreibung ist Information! (Optisch, Akustisch...)
Theorie entwirft ein Modell der Realität. Basis dabei sind grundsätzlichen Annahmen == Axiome, diese sind nicht beweisbar. Daraus entsteht Modell (=Bild) aus dem Informationen gewonnen werden. Informationen == Beschreibung.
1.4. Welches Modell für "Informationen" gibt es?
Informationen sind strukturiert
- beschreiben die Welt
- benötigen einen Interpreter (z.B. Mensch)
Information beschreibt etwas, was ein Interpreter (z.B. Mensch) auswerten kann und ein Ergebnis / Verhalten bewirkt.
1.5. Was versteht man unter Wissenschaft? Geben sie ein Beispiel dafür.
Wissenschaft: Das Ziel ist die Gewinnung nachprüfbarer, vernunftgemäßer, reproduzierbarer Aussagen über die Natur um besseres Verständniss zu erlangen und Vorhersagen treffen zu können
Beispiel: Meteorologie
Meteorologie beobachtet und beschreibt Naturphänomene um daraus Zusammenhänge zu erkennen und künftige Ereignisse abzuleiten
1.6. Welche Rolle spielt Modellierung in der Informatik?
Modellierung ist wichtig!!!! Da dabei Informationen
- gesammelt
- ausgewählt
- strukturiert
- notiert werden
Modelle in Naturwissenschaft, Technik, Informatik usw. sollten
- Zweckorientiert
- Vollständig in Bezug auf diesen Zweck
- Formal
- Berechenbar
- Beschreibbar
sein!
Je komplexer ein System ist, desto wichtiger ist ein Plan bevor man beginnt das System zu konstruieren. Dies führt zur Vermeidung von Fehlern, zu besserer Qualität, niedrigeren Kosten, besserer Dokumentation und Wiederverwendbarkeit.
1.7. Was versteht man unter Syntax?
Syntax bezeichnet Regeln zur Kombination von Zeichen untereinander
1.8. Geben sie Beispiele für Syntax aus verschiedenen Bereichen (Sprache, Programmierung, Musik, Literatur, Film, ...)
- Grammatik einer Sprache
- Syntax einer Programmiersprache
- Mathematische/chemische Formeln
- Musikalische Form
- Aufbau einer Filmstory oder eines Dramas
- Struktur eines Gebäudes..
1.9. Was versteht man unter Semantik?
Semantik ist die Beziehung des Interpreten zu den Zeichen. Semantik befasst sich mit Ausdruckbedeutung
Einfach gesprochen: SYNTAX == Wort, SEMANTIK == Bedeutung des Worts
1.10. Geben sie Beispiele für Semantik aus verschiedenen Bereichen (Sprache, Programmierung, Musik, Literatur, Film, ...)
- Bedeutung der Wörter und Phrasen,
- Semantik einer Programmiersprache,
- Interpretation einer Mathematischen Formel,
- Musikalischer Inhalt
- Geschichte eines Films oder eines Dramas,
- intendierter Zweck eines Gebäudes...
1.11. Was versteht man unter Pragmatik?
Beziehung des Interpreten zu den Zeichen. Pragmatik befasst sich mit dem kommunikativen Sinn
Einfach gesprochen SYNTAX == Wort, SEMANTIK == Bedeutung des Worts, PRAGMATIK == Wie der Empfänger es interpretiert (für Einen ist ein Lied traurig, für den Anderen nicht)
Beispiel: Darbo Musik - da wurde von der Werbung etwas hineingelegt...
1.12. Geben Sie Beispiele für Pragmatik aus verschiedenen Bereichen (Sprache, Programmiersprache, Musik, Literatur, Film, ....)
- Üblicher Sprachgebrauch
- Ausführung eines Programms auf einem System
- Eindruck von Musik auf den Hörer
- Interpretation eines Films oder eines Dramas
- tatsächliche Verwendung eines Gebäudes
1.13. Was sind formale Modelle? Was unterscheidet sie von anderen Modellen?
Ein formales Modell ist vollkommen und exakt in den Aussagen (vor allem mathematische Modelle). Formale Modelle sind die, wo der Interpretationsspielraum so gering als möglich ist.
Im Unterschied dazu (nach der Exaktheit) gibt es
- semi-formale Modelle -> teilweise exakt, jedoch nicht alles vollständig spezifiziert
- nicht-formale Modelle -> eher grobe Richtlinien, machen eher vage Aussagen
1.15. Geben sie Beispiele für Sprachen zur Definition formaler Modelle.
- Mathematik
- Logik
2.1. Wie wird theoretisch der Aufwand eines Algorithmus definiert?
t(A,n,e) sei die Anzahl der durchgeführten Elementaroperationen des Algorithmus A mit den Eingabedaten e, die n Zellen groß sind.
Einfach gesprochen: die Anzahl der Operationen des Algorithmus A ergeben Best Case, Worst Case und Average Case
3 Mögliche Fälle der Komplexität
- Tmin(A,n) = min{ t(A,n,e) | e Є En} → Best Case
- Tmax(A,n) = max{ t(A,n,e) | e Є En} → Worst Case
- T (A,n) = avg{ t(A,n,e) | e Є E } → Average Case
Der best case ist meist nicht interessant (weil selten), der worst case ist für Theorie und Praxis interessant, der average case ist in der Praxis wichtig
2.2. Welches Modell wird für Komplexitätsberechnungen herangezogen?
Das Rechnermodell: Ein stark vereinfachtes Modell eines Computers
Das Algorithmus-Modell: Anordnung elementarer Operationen?
Problem-Modell?
2.3. Welche Komplexitätsklassen gibt es?
- Konstant
- Logarithmisch
- Linear
- Linear-logarithmisch
- Quadratisch,kubisch,... --> polynomial
- Exponentiell
2.4. Welchen Aufwand haben typische Algorithmen wie etwa sequentielle Suchen in einem unsortierten Array, binäres suchen in einem sortierten Array, diverse Sortierverfahren, Simplexverfahren...
Suchen im unsortierten Array = Linear → O(n)
Binäre Suche im sortierten Array = Logarithmisch → O(n log n)
Suche in Hash-Tabelle = Konstant → O(1)
Selection-Sort = Quadratisch → O(n hoch 2)
Bubble-Sort = Quadratisch → O(n hoch 2)
Quicksort = = Quadratisch → O(n hoch 2)
Merge-Sort = Linear Logarithmisch → O(n log n) = besser als die anderen Sorter!!! Aber zusätzlicher Speicherplatz erforderlich. Man kann beweisen, dass es keinen effizienteren Algorithmus geben kann! O(n log n) ist die untere Schranke fürs Sortieren!
2.5. Was ist der Unterschied zwischen polynomialer und exponentieller Komplexität?
Polynomiale Algorithmen sind im Allgemeinen auf Computern in vernünftiger Zeit durchführbar.
Exponentielle Algorithmen sind das nicht! (Auch nicht mit viel schnelleren Computern.)
2.6. Was versteht man unter NP-Komplexität?
NP (für nichtdeterministisch polynomielle Zeit)?
Ein Problem, dessen Komplexität so exponentiell steigt, dass kein effizienter Algorithmus bekannt ist um es zu lösen, jedoch ein effizienter Algorithmus bekannt ist um die Lösung zu Prüfen.
P == Klasse der Probleme, die sich auf einer normalen, d.h. deterministischen Rechenmaschine in polynomieller Zeit lösen lassen. Genauer: Probleme, die sich in polynomiell vielen Schritten lösen lassen
NP == Klasse der Probleme, die sich auf einer nicht-deterministischen Rechenmaschine (Bsp. Turingmaschine) in polynomieller Zeit lösen lassen. Das Wort nichtdeterministisch ist hier wichtig und macht den Unterschied zur Klasse P aus. Es bedeutet, dass unsere Rechenmaschine beliebig viele Berechnungspfade erzeugen kann und es schon reicht, wenn einer davon erfolgreich beendet wird.
Beispiel: N-Damen-Problem:
Schachbrett mit Kantenlänge == n und n Damen platziert werden müssen ohne dass eine Dame die andere Dame bedroht
➔ Je mehr Damen man auf die Fläche stellt, umso größer muss das Schachbrett werden (Fläche steigt durch n massiv an)
➔ Hinzufügen jeder Dame erhöht den Aufwand massiv
➔ Das Überprüfen, ob sich n-Damen schlagen geht jedoch sehr leicht.
-
- 1 / 60
-
Flashcards
3.18. Was sind kontextsensitive Sprachen?
G heißt kontextsensitiv, wenn alle Regeln von folgender Form sind:
a → b mit |a| <= |b|
Auf linker Seite jeder Regel stehen nicht mehr Symbole als rechts (Beipiel wenn links aB → ab, darf recht NIE mehr sein wie z.B aBC → ab
Ausnahme: S →ε ist erlaubt, wenn S NIE auf einer rechten Seite vorkommt
Daher wandelt man immer die einfachsten Variablen zuerst um (von links nach rechts)
Beispiel Grammatik: G = (V,Σ,P,S) mit:
V = {S,B,C}
Σ = {a,b,c}
P = { S → aSBC | aBC, CB → BC, aB → ab, bB→ bb, bC → bc, cC → cc} L(G) = {abc,aabbcc,aaabbbccc,aaaabbbbcccc,...} =
L(G)={anbncn |n>=1}
3.19. Was ist ein linear beschränkter Automat?
- Nichtdeterministischer LBA == ähnlich Turingmaschinen
- einziger Unterschied, dass zugänglicher Teil des Bandes durch Größe der Eingabe beschränkt ist
- akzeptieren genau die Typ-1-Sprachen (kontextsensitive Sprachen) - ob dies auch auf deterministische LBA zutrifft, ist ein noch offenes Problem
3.20. Was ist der Unterschied zwischen deterministischen und nichtdeterministischen linear beschränkten Automaten?
δ (Delta) == Übergangsfunktion/relation
Wenn δ == Zustandsübergangsfunktion -> deterministischen LBA
Wenn δ == Zustandsübergangsrelation -> nicht-deterministischen LBA
Funktion: es gibt maximal einen einzigen y-Wert für einzelne x-Werte.
Relation: es gibt mehrere y-Werte für einzelne x-Werte.
3.21. Was sind Typ-0 Sprachen?
• Sprachen ohne Einschränkungen bezüglich der Regeln!
Beispiel für eine „Sprache“, die Typ-0, aber nicht Typ-1 ist, ist das Halteproblem für Turingmaschinen
Das Halteproblem beschreibt Frage, ob Ausführung eines Algorithmus zu einem Ende gelangt – normal für viele Algorithmen leicht zu beantworten. Alan Turing konnte mit einer Turingmaschine beweisen, dass es keinen Algorithmus gibt, der diese Frage für alle möglichen Algorithmen und beliebige Eingaben beantwortet.
3.22. Was ist eine Turingmaschine?
- Zu jeder Sprache (erzeugt in freien Grammatik) gibt es eine Turingmaschine, die diese Sprache erkennt
- Zu jeder Turingmaschine gibt es eine rekursiv aufzählbare Sprache, die von dieser Turingmaschine erkannt wird
Aufbau:
Eine Turingmaschine hat ein Steuerwerk, in dem sich das Programm befindet, und besteht außerdem aus
- einem unendlich langen Speicherband mit unendlich vielen sequentiell angeordneten Feldern
- pro Feld kann genau ein Zeichen aus einem vordefinierten Alphabet gespeichert werden
- zusätzliches Zeichen ist ein Blank („unbeschrieben“) zugelassen == leeres Feld auf Speicherband
- einem programmgesteuerten Lese- und Schreibkopf
- bewegt sich feldweise auf Speicherband und verändert / löscht Zeichen
Die Turingmaschine modifiziert die Eingabe auf dem Band nach dem festgelegten Programm
Startposition == Anfang des Eingabeworts, d. h. an der Position des ersten Eingabezeichens
3.23. Was kann eine Turingmaschine?
- Modifiziert die Eingabe auf dem Band nach dem festgelegten Programm
- Startposition ist Anfang des Eingabeworts (erstes Eingabezeichens)
- Jeder Schritt besteht aus
- Lese-Schreib-Kopf lest aktuelles Zeichen
- überschreibt dieses mit dem neuen Zeichen
- bewegt sich dann ein Feld nach links oder rechts oder bleibt stehen
- Welches Zeichen geschrieben wird und welche Bewegung ausgeführt wird, hängt ab von:
- Vorgefundenem Zeichen an aktueller Position
- Zustand in dem sich Turingmaschine gerade befindet
- Definiert durch Überführungsfunktion in der Turingmaschine
- Anzahl der Zustände, in denen sich die Turingmaschine befinden kann, ist endlich
- Ein Zustand kann mehrere Male durchlaufen werden und sagt nicht über die Zeichen auf dem Band aus
- Sie stoppt wenn für den aktuellen Zustand und das gelesene Bandsymbol keine Überführung zu neuem Zustand
- definiert ist
- hängt immer von Kombination aus Zustand und Symbol ab
- Zustände in denen unabhängig vom gelesenen Bandsymbol angehalten wird bezeichnet man als Endzustände
- Es gibt auch Turingmaschinen, die für gewisse Eingaben niemals stoppen
Ablauf vereinfacht:
Auf einem Band steht das Wort „Anna“
- Start an Startposition
- Einlesen Zeichen „A“
- Überschreiben des Zeichens mit „neuem/gleichem“ Zeichen aufgrund Überführungsfunktion
- Bewegt sich nach rechts aufgrund der Überführungsfunktion
- Einlesen Zeichen „n“
- Überschreiben des Zeichens mit „neuem/gleichem“ Zeichen aufgrund Überführungsfunktion
- Bewegt sich nach rechts aufgrund der Überführungsfunktion
- Einlesen Zeichen „n“
- Überschreiben des Zeichens mit „neuem/gleichem“ Zeichen aufgrund Überführungsfunktion
- BewegtsichnachrechtsaufgrundderÜberführungsfunktion
- EinlesenZeichen„A“
- ÜberschreibendesZeichensmit„neuem/gleichem“ZeichenaufgrundÜberführungsfunktion
- BewegtsichnachrechtsaufgrundderÜberführungsfunktion
- Einlesen „Blank“ – Endposition in diesem Beispiel aufgrund fehlender Überführungsfunktion
3.24. Wie unterscheidet sich eine Turingmaschine von einem linear beschränkten Automaten?
- Linear beschränkter Automat (LBA) -> verlässt den Bereich des Bandes auf dem die Eingabe steht nicht
- Während der Berechnung wird daher nur der Teil des Bandes benutzt, auf dem zu Beginn das Eingabewort stand -> begrenzter Speicher
3.25. Was ist der Unterschied zwischen deterministischen und nichtdeterministischen endlichen Turingmaschinen?
Zu jeder nicht-deterministischen Turingmaschine gibt es deterministische Turingmaschine, die dieselbe Sprache erkennt.
Trotz dem Unterschied (Funktion / Relation) der deterministische und nicht-determin. Turingmaschinen sind diese als äquivalent anzusehen, da die eine mit Relationen paralleler arbeiten kann und die mit Funktionen seriell abarbeitet, Aufgrund der Leistung und des unbegrenzten Speichers können beide trotzdem mit dem Input der anderen umgehen.
3.26. Was versteht man unter Language Security?
- Sichere Eingabeprüfung
- Ausschließlich erlaubte Eingaben akzeptieren
- Eingaben immer gleich und sicher interpretieren o Keine unvorhergesehene Reaktion auf Eingaben
- Identische Interpretation auf beiden Seiten einer Schnittstelle
- Die Sprache des Senders muss gleich der Sprache des Empfängers sein
- Design Contracts müssen explizit definiert und überprüfbar eingehalten werden
3.27. Wie kann man eine Schwachstelle in einem Interface theoretisch beschreiben?
M...Message - Dec...Entschlüsselung - Enc...Verschlüsselung
M != Dec(Enc(M)) – Nachricht =! Dieselbe Nachricht nach Ver-und Entschlüsselung
M ist semantisch gültig für den Sender – Nachricht vom Sender ist richtig versendet
Dec(Enc(M)) ist semantisch gültig für den Empfänger – Verarbeitete Nachricht ist logisch richtig
Die Verarbeitung von M beim Empfänger ist nicht gleich der Verarbeitung von Dec(Enc(M)) beim Empfänger
Schlussfolgerung: Da Nachricht A versendet wird und semantisch richtig ist, jedoch beim Empfänger B (ebenfalls semantisch richtig) verstanden wird!!! -> Schwachstelle
3.28. Welche Vorgangsweise sollte man im Sinne der Language Security wählen, damit Input Validation vollständig möglich ist?
Erlaubten Input so einfach wie möglich halten!
Erlaubten Input exakt als formale Sprache definieren
Input Validation als Parser implementieren
Parser mit einem validierten Parser-Generator erzeugen!
3.29. Welche Vorgangsweise sollte man im Sinne der Language Security wählen, damit ein Protokoll sicher implementiert werden kann?
Protokoll so einfach wie möglich halten!
Protokoll exakt als formale Sprache definieren!
Protokoll überall als Parser implementieren!
Parser mit einem validierten Parser-Generator erzeugen!
4.1. Was ist der Unterschied zwischen rekursiven und rekursiv-aufzählbaren Sprachen?
Rekursiv aufzählbare Sprache S == Es gibt Turingmaschine, die alle Wörter aus S akzeptiert, aber keine Wörter, die nicht in S liegen
- Rekursiven Sprachen sind rekursiv aufzählbar (Teilmenge von S).
Unterschied zwischen rekursiven Sprachen und rekursiv-aufzählbaren Sprachen:
- rekursiven Sprachen (entscheidbare Sprachen)
- Turingmaschine muss halten
- Rekursiv aufzählbaren Sprachen
- Turingmaschine muss nicht halten, wenn Wort nicht in LL liegt -> möglich, dass man auf Lösung unendlich lange warten muss
4.2. Wie ist das Wortproblem formal definiert?
Das Wortproblem in einer formalen Sprache ist das Problem festzustellen, ob ein gegebenes Wort zur Sprache gehört, oder nicht.
Das Wortproblem für
Typ-0-Sprachen ist rekursiv aufzählbar und nicht entscheidbar.
Typ-1-Sprachen ist entscheidbar
Typ-2-Sprachen ist durch den Cocke-Younger-Kasami-Algorithmus lösbar
Typ-3-Sprachen ist durch deterministische endliche Automaten lösbar.
4.3. Was ist der Unterschied zwischen abzählbar unendlich und überabzählbar unendlich?
- abzählbar unendlich
- Eine Menge M heißt abzählbar, wenn eine Bijektion zwischen der Menge M und den natürlichen Zahlen existiert.
- Bijektion == Jedem Element aus einer Menge ist ein Element aus einer anderen Menge zugeordnet
- Beispiele: Natürliche Zahlen, Primzahlen, Ganze Zahlen (Jede Zahl hat dieselbe Mächtigkeit wie sie selbst)
- überabzählbar unendlich
- Eine Menge M heißt überabzählbar, wenn sie weder endlich noch abzählbar ist.
- Beispiel: Die Menge aller Teilmengen (=Potenzmenge) einer Menge wenn die Menge unendlich viele Elemente hat.
4.4. Was ist die Church-Turing-These?
Die Turingmaschine muss ja oder nein sagen und muss stehen bleiben (sie “hält”, endliche Antwortzeit).
“Die Klasse der turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.”
Diese These ist nicht beweisbar, da der Begriff „intuitiv berechenbare Funktion“ nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auf irgendeine Weise berechnet werden könnten. Damit setzt man insbesondere keine Vorstellung voraus, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Es wird in der Informatik üblicherweise angenommen, dass die These stimmt. Dadurch kann es ermöglicht werden, von einer Funktion nachzuweisen, dass sie nicht berechenbar ist.
4.5. Wann ist ein Problem entscheidbar?
Wenn die Turingmaschine hält. Wenn zu einer Eingabe in endlicher Zeit eine Antwort geliefert wird.
4.6. Was versteht man unter dem Halteproblem von Turingmaschinen?
Ob eine Turingmaschine - mit einem Eingabewort gestartet - halten wird oder nicht.
Ja = Bleibt sie stehen
Nein = Kann sie unendlich lang weiterlaufen
Ein Programm welches ein anderes Programm analysiert ob es eine Endlosschleife enthält oder nicht. (Kann sich das Programm selber analysieren ob es nicht selber in einer Endlosschleife durchläuft? Nicht möglich!)
4.7. Was sagt der Unvollständigkeitssatz von Gödel aus?
1.Satz:
Ein formales System kann nicht logisch konsistent und zugleich vollständig sein. - Hängt sich ein Programm auf kann es nicht logisch konsistent sein
2. Satz:
Ein logisch konsistentes System ist nicht in der Lage seine eigene logische Konsistenz zu beweisen.
- Das Programm führt sich selbst mit einem Parameter aus welcher dazu führt, dass sich das Programm aufhängt. Das Programm ist jedoch nicht in der Lage festzustellen, dass sich die von ihm aufgerufene Instanz seiner selbst aufgehängt hat! Somit kann es in diesem Fall auch selbst nicht terminieren.
- Das Programm kann sich nicht selber testen ob es “logisch” ist.
1.14. Welche Sprachen zur Formulierung formaler Modelle gibt es?
Programmiersprachen
Automaten
Logiken
Lambda Kalkül (Sprache zur Untersuchung von Funktionen)
