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
-
Lernkarten
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.
2.7. Was versteht man unter NP-vollständig?
Es gibt eine Unter-Klasse von NP-Problemen, die in polynomialer Zeit ineinander übergeführt werden können. Dh gibt es für eines dieser Probleme einen Lösungsalgorithmus mir polynomialer Komplexität, dann sind alle Probleme in dieser Klasse in polynomialer Zeit lösbar. Diese Probleme heißen NP-Vollständig.
NP-vollständige Probleme lassen sich vermutlich nicht effizient lösen
2.8. Nennen sie einige NP-vollständige Probleme
Das Cliquenproblem
Das Rucksackproblem
Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzwert der ausgewählten Objekte maximiert werden.
Graph Coloring
Travelling-Salesman
Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass keine Station außer der ersten mehr als einmal besucht wird, die gesamte Reisestrecke des Handlungsreisenden möglichst kurz und die erste Station gleich der letzten Station ist.
N-Damen- Problem
Auf einem Schachbrett mit Kantenlänge n sollen n Damen aufgestellt werden, ohne dass Diese sich gegenseitig bedrohen.
2.9. Was kann man zur Komplexität der Primzahlfaktorisierung sagen?
- Ist sicher NP
- Alles andere ist ungeklärt (P? NP-komplett?)
- Für Quantencomputer gibt es einen Algorithmus mit polynomialer Komplexität!
3.1. Wie wird die Syntax formaler Sprachen meist definiert?
Bei formalen Sprachen muss Syntax exakt definiert werden durch:
- Grammatik in BNF (Backus-Naur-Form == formale Metasprache zur Darstellung kontextfreier Grammatiken)
- Syntaxdiagrammen
3.3. Was versteht man unter einer (formalen) Grammatik?
Formale Grammatik G besteht aus 4 Komponenten:
G = (V,Σ,P,S)
V == endliche Menge der Nicht-Terminale (Variablen)
Σ == endliche Menge der Terminale (das Alphabet)
P == Menge der (Produktions) Regeln
S == Startsymbol (S ∈ V)
3.4 Wie ist die formale Sprache definiert, für die die Grammatik bekannt ist?
Alphabet: geordneter Zeichenvorrat
Zeichenkette: endliche Folge von Symbolen, die ohne Zwischenraum hintereinander geschrieben werden (Verkettung)
Formale Sprache: Menge von Zeichenketten, die aus den Symbolen eines beliebigen Alphabets aufgebaut sind.
Menge Zeichenkette -> alle möglichen Kombinationen des Alphabets unabhängig ob diese Kombination von Zeichen gültig ist (Auto, Auuto, Autoo...)
Anwendung finden formale Sprachen in der Linguistik, der Logik und der theoretischen Informatik.
3.5. Was versteht man unter Parsing?
Parsing == Überprüfen der Vorliegenden Quelltexte etc. ob diese den vordefinierten Regeln der entsprechenden Grammatik folgen.
Beispiele:
- Parser einer Programmiersprache überprüft, ob der Code syntaktisch korrekt ist
- Parser einer Sprache überprüft, ob es das Wort (z.B. im Duden) gibt
3.2. Was versteht man unter einer Ableitung?
Ableitung == Vorgang in theoretischer Informatik, ein Wort nach Regeln einer formalen Grammatik zu erzeugen
Beispiele:
- Regel: es gelten nur Artikel -> das Wort „Haus“ ist daher ungültig
- Regel: Ein Nominalsatz besteht aus Artikel, Adjektiv, Substantiv
3.6. Erklären Sie die Chomsky-Hierarchie: Welche Sprachklassen gibt es?
Noam Chomsky Definition -> Einteilung formaler Sprachen in 4 Gruppen
Regulär
Grammatik ist Regulär wenn sie entweder rechtslinear oder linkslinear ist
(Es muss auf ein bestimmtes „Teil“ anfangen oder enden Bsp.: Mädchen laufen Suppen, *en -> rechtslinear)
Kontextfrei
Wenn Ableitungsbäume nur Binär sind bis auf letzten Schritt (nur links oder rechts) == Kontextfrei da Satz nicht mehr als 2 Ableitungen hat
Kontextsensitiv
Sind Sprachen die von einer nichtdeterministischen, linear beschränkten Turingmaschine erkannt werden können
Allgemein
== rekursiv aufzählbaren Sprachen, -> die zugehörige Turingmaschine akzeptiert jedes Wort, das in der Sprache liegt. Für ein Wort, das nicht in der Sprache liegt, kann die Turingmaschine auch nicht terminieren
3.7. Welcher Zusammenhang besteht zwischen den Sprachklassen Chomskys und Automaten?
Regulär -> Endlicher Automat
Kontextfrei -> Keller Automat
Kontextsensitiv -> Linear beschränkter Automat
Allgemein -> Turing Maschine
3.8. Was sind reguläre Sprachen?
Sei G = (V,Σ,P,S) eine Grammatik.
G heißt regulär, wenn sie entweder rechtslinear oder linkslinear ist
Linkslineare Grammatik kann in rechtslineare umgewandelt werden und umgekehrt! Rechts-lineare Grammatik == Typ-3-Grammatik der Chomsky-Hierarchie
Rechtslinear
Sei G = (V,Σ,P,S) eine Grammatik.
A,B ∈ V und a ∈ Σ
G ist rechtslinear wenn P nur Regeln der folgenden Form enthält A → aB
A → ε (ε == Nix)
Beispiel Grammatik anhand von Beispiel vorher „Mädchen laufen Suppen, *en“:
a → Mädch a → lauf
a → Supp
B → en
A1 = Mädchen A2 = laufen
A3 = Suppen
3.9. Was sind endliche Automaten?
Endlicher Automat bedeutet: wenn Menge der Zustände, die er annehmen kann (später S genannt), endlich ist.
Varianten:
- nicht-deterministischer endlicher Automat
- für jeden Zustand genau ein Übergang für jede mögliche Eingabe
- ohne Verweis auf vorherige Ebenen
- deterministischer endlicher Automat
- keinen oder auch mehr als einen Übergang für die mögliche Eingabe geben
- mit Verweis auf vorherige Ebenen
3.10. Wie hängen reguläre Sprachen und endliche Automaten zusammen?
Reguläre Sprachen
- können von endlichen Automaten erkannt werden
- von regulären Ausdrücken beschrieben werden
3.11. Was ist der Unterschied zwischen deterministischen und nichtdeterministischen endlichen Automaten?
Hinweis
nicht-deterministischer endlicher Automat
- keinen oder auch mehr als einen Übergang für die mögliche Eingabe geben
- ohne Verweis auf vorherige Ebenen
Beispiel:
deterministischer endlicher Automat
- für jeden Zustand genau ein Übergang für jede mögliche Eingabe
- mit Verweis auf vorherige Ebenen
Zu jedem nicht-deterministischen endlichen Automaten gibt es einen deterministischen endlichen Automaten, der dieselbe Sprache akzeptiert, das bedeutet
aber nicht umgekehrt.
3.12. Welche Anwendungen für reguläre Sprachen gibt es?
- LEX – Lexikal. Analyse -> „Duden“
- Pattern Matching -> „Mustersuche“
- Model Checking -> „Verifikation einer Systembeschreibung (Modell) gegen eine Spezifikation (Formel)“
3.13. Was sind kontextfreie Sprachen?
Sei G = (V,Σ,P,S) eine Grammatik.
G heißt kontextfrei, wenn alle Regeln von folgender Form sind
v → x mit v ∈ V
Es dürfen auf der linken Seite jeder Regel nur einzelne Variable stehen
Beispiel:
V = {<ra>}
Σ = {0,1,+,*,(,)}
S = <ra>
P = { <ra> → <ra>+<ra>
<ra> → <ra><ra> <ra> → <ra>*
<ra> → (<ra>) <ra>→ 0 | 1 | }
Beispiel Grammatik: G= (V,Σ,P,S) mit:
V =
P = L(G) = L(G) =
{S} Σ = {0,1}
{ S → 0S1 | 01 }
{ 01,0011,000111,00001111,0000011111,...} = { 0n1n | n >= 1}
3.14. Was sind Kellerautomaten?
Kellerautomat klärt ob Eingabe (Wort aus null, einem oder mehreren Zeichen) zu einer bestimmten formalen Sprache (Menge von Wörtern) gehört. Dafür arbeitet der Automat das Eingabewort Schritt für Schritt von links nach rechts ab und kann dabei eine Reihe von Zuständen annehmen.
Zu Anfang ist er im sogenannten Startzustand. Typischerweise wird in jedem Verarbeitungsschritt ein Zeichen aus der Eingabe gelesen. Außerdem wird in jedem Verarbeitungsschritt das oberste Zeichen vom Keller gelesen, d. h. entfernt. Abhängig vom aktuellen Zustand, dem gerade gelesenen Eingabezeichen und dem gerade gelesenen Kellerzeichen geht der Automat in einen neuen Zustand über und legt anstelle des entfernten Kellerzeichens ein neues Wort auf dem Keller ab. Wenn die gesamte Eingabe gelesen wurde und der Keller leer ist, gehört die Eingabe zur vom Automaten erkannten Sprache.
- Beispiel (besser als das Tavo Beispiel, weil man kein ominöses Orakel braucht)
Um das Prinzip eines Kellerautomaten zu verdeutlichen, wird häufig die syntaktische Untersuchung geklammerter Ausdrücke herangezogen. Beispielsweise muss in einem Ausdruck einer bestimmten Sprache zu jeder öffnenden Klammer auch eine schließende Klammer existieren:
Beispiel: { ... { ... } ... }
Der Automat beginnt in einem Startzustand z0; im Keller befindet sich ein Zeichen, welches das Ende kennzeichnet (#). Bei der Abarbeitung des Ausdrucks bewegt sich der Lesekopf Zeichen für Zeichen weiter. Stößt er dabei auf eine öffnende Klammer, so wird diese in den Keller geschrieben. Tritt in der weiteren Abarbeitung eine schließende Klammer auf, so wird das oberste Klammer-auf-Zeichen im Keller wieder gelöscht. Der Ausdruck ist dann erfolgreich abgearbeitet, wenn der Lesekopf das Ende des Eingabebandes erreicht hat und sich im Keller ausschließlich das Zeichen # befindet. Befände sich hingegen noch eine geöffnete Klammer nach der Ausdrucksabarbeitung im Keller, so würde dies bedeuten, dass eine schließende Klammer fehlt und ein syntaktischer Fehler vorliegt. Auch wenn das Ende des Kellers erreicht wird, bevor die Eingabe vollständig abgearbeitet wurde, liegt ein Fehler vor. In diesem Fall befinden sich zu viele schließende Klammern in der Eingabe.
3.15. Wie hängen kontextfreie Sprachen und Kellerautomaten zusammen?
Jede kontextfreien Grammatik G = (V,Σ,P,S) hat äquivalenten nicht-deterministischen Kellerautomaten, der L(G) akzeptiert
Jeder Kellerautomat hat passende kontextfreie Sprache L(G), die der akzeptierten Sprache des Kellerautomaten entspricht.
Mächtig: Turingmaschinen erkennen rekursiv aufzählbare Sprachen (Typ 0)
Mittel: Nichtdeterministische Kellerautomat erkennt kontextfreie Sprachen (Typ 2, vgl. Chomsky-Hierarchie)
Einfach: Endliche Automaten erkennen regulären Sprachen (Typ 3)
3.16. Was ist der Unterschied zwischen deterministischen und nichtdeterministischen Kellerautomaten?
Deterministischer Kellerautomat
- Übergangsrelation ist eine Funktion
- darf für jedes (aktueller Zustand, aktuelle Eingabe, aktuelles oberstes Kellerelement)-Tripel keine oder nur eine Übergangsmöglichkeit besitzen.
- Zu fester Eingabe gibt es höchstens eine Zustandsübergangsabfolgen
Nicht-Deterministischer Kellerautomat
- Übergangsrelation ist ein Orakel (It’s MAGIC) -> Zu fester Eingabe gibt es mehrere Zustandsübergangsabfolgen, Mehrdeutigkeiten können also auftreten. Die letztendliche Entscheidung, wann der Übergang passiert entscheidet die tatsächlich verwendete Zustandsübergangsabfolge (man weiß halt nur nicht welche es ist – drum „MAGIC“)
3.17. Welche Anwendungen kontextfreier Sprachen gibt es?
Programmiersprachen Überprüfung der Syntax
YACC (Yet another Compiler Compiler)
Tool mit dem man Compiler kompilieren kannPalindrom erkennen
Anna, Lagerregal -> Bei einem Palindrom mit mehreren gleichen Buchstaben bis zur Mitte des Wortes kommt Nicht- Deterministischer Kellerautomat zum tragenRichtiges “Klammern” bei Rechenoperationen erkennen
Ebenfalls Nicht Deterministischer Kellerautomat nötig da man nie weiß wie viele { kommen (wo die Mitte ist)
