GBI - Kapitelzusammenfassung PDF

Preview

Summary

Zusammenfassung des Lehrinhalts der Vorlesung GBI von WS 17/18...

Description

Kapitel

2

Begriff Informatik, Signal (analog/digital), Inschrift, Nachricht, Information, Datum Informationstheorie

Informationsgehalt

Erklärung Definitionen: Siehe Vorlesungsfolien / Skript

Beispiel

Computer verarbeiten Nachrichten, keine Informationen! Claude Shannon Menge der Informationen hängt von der Anzahl der Überraschungen ab  loge (nat)  log10 (Hart)  log2 (Sh) Element ein Objekt einer Menge

Kardinalität

Element der Menge bzw. nicht Teil- bzw. Obermenge bzw. Leere Menge Set comprehension Menge aller x für die P(x) wahr ist Vereinigung A B = {x | x A oder x B}

3

Mengen

Durchschnitt A B = {x | x A und x B} Mengendifferenz A \ B = {x | x A und x B} Disjunkte Menge Leerer Schnitt zweier Mengen Regeln die gelten  Assoziativ-, DistributivKommutativgesetz  Idempotenz von Kardinalität |M| Anzahl der versch. Elemente Potenzmenge 2M 2M = Menge aller möglichen Teilmengen

Idempotenz A A = A und A A = A

Große Verienigung, Schnitt

Definition Endliche nichtleere Menge von Zeichen Alphabet

ASCII-Zeichensatz Unicode Jedes Zeichen besitzt Code Point Paar (a,b…n)  n-Tupel  Reihenfolge wichtig

linkstotal

Binäre Relation Teilmenge R A B Linkstotal

Rechtseindeutig gibt es höchstens ein

rechtseindeutig

Partielle Funktion f gibt es höchstens ein   Relation

Nicht linkstotal Nur rechtseindeutig

Eigenschaften von Reflexiv

Partielle Funktion

Symmetrisch

Transitiv

Äquivalenzrelation Relation die reflexiv, symmetrisch & transitiv ist Potenz einer Relation  R0 = IM  Ri+1 = Ri R

Produkt von Relationen

Produkt von Relationen Seien R M1 M2 & S M2 M3 zwei Relationen

Produkt ist assoziativ Reflexiv-transitive Hülle

Reflexiv IM R also Transitiv also dann Definition Relation die linkstotal & rechtseindeutig ist Schreibweise  Abbildungsvorschrift R: A B,  Definitionsbereich A  Zielbereich B  Fuktionswert b an der Stelle a: R(a) = b

Abbildung

Linkseindeutig

Linkseindeutig / injektiv gibt es höchstens ein Rechtstotal /surjektiv Abbildung

Rechtstotal Bijektiv Abbildung injektiv & surjektiv

Bijektiv

Definition Kartesisches Produkt vieler Mengen Kartesisches Produkt Lemma Definition Folge von Zeichen aus einem Alphabet Länge |w| Menge aller Wörter über ein Alphabet A A* Menge aller Wörter der Länge n über ein Alphabet A An Menge aller Wörter beliebiger Länge über ein Alphabet A

Leere Wort / neutrales Element 4

Wort

Konkatenation Verknüpfung von Wörtern w1 w2: m+n A1 A2

Nicht kommutativ,nur assoziativ Potenz von Wörtern w0 = n+1 für jedes n 0: w = wn w Lemma Für jedes Alphabet A gilt: Für jedes w A*: w = w Für jedes Alphabet A und alle w1, w2, w3 A* gilt: (w1 w2) w3 = w1 (w2 w3) |wn| = n|w| |w1 w2| = |w1| + |w2|

Kartesisches Produkt = {( ,1), ( ,2), ( ,3), (+,1), (+,2), (+,3)} Kartesisches Produkt vieler Mengen

Bindungsstärken

Aussagenlogik Syntax

Aussagenlogische Konnektive

Interpretation

Äquivalente Formeln

V = Menge an Aussagenvariablen B = {w, f} Auswertung / Validierung

und Tatutologie Siehe Folie Kapitel 5 (30/40)

5

Anzahl der Interpretationen 2k Äquivalente Formeln (Tautologie)

Aussagenlogik Semantik

Lemma Wenn G H ist dann ist G H Tautologie (umgekehrte Richtung ebenfalls) Jede Tautologie ist im Ausagekalkül beweisbar. Modell

Boolesche Funktion

Tautologie jede Interpretation Modell Folgerung: für jede Interpretation der Aussagenvariablen ist die gesamte aussagenlogische Formel wahr. f: k “Wahrheitswerte“ B = {w, f}  Alphabet AAL  Syntaktisch korrekte Formeln ForAL A*AL  Axiome AxAL AAL  Schlussregel Modus Ponens MP For³AL Axiome

Modus Ponens Hilbertkalkül Lemma Wenn sowohl G H als auch G Tautologien sind, dann ist auch H eine Tautologie. Ableitung

Beweis & Theorem

6

Vollständige Induktion

Beweisverfahren um die Gültigkeit einer Aussage A(n) für 0 zu beweisen I.A.: A(n) gilt für n = 0 bzw. 1 I.V.: Annahme: A(n) gilt für ein beliebiges aber festes 0 I.S.: Zeigen: wenn A(n) gilt, gilt auch A(n+1)

Formale Sprache

A* L1L2 = {w1w2 | w1 L1 & w2 L2}

Produkt formaler Sprache

Lemma

Potenz von Sprachen 7

Konkatenationabschluss

Assoziativ, aber nicht kommutativ L0 = k+1 = Lk 0: L Kleensche Hülle L* von L

- freie Konkatenationsabschluss L+ von L

Zu einer Zahlenbasis k definiere die Abbildung Numk: Zk* Numk

k-äre Darstellung bzw. Reprk

Numk = 0 Numk(wx) = k Numk(w) + numk(x) Für alle w Zk*, x Zk Wobei numk(x) Alphabet Zk mit k Ziffern  Bedeutung die Zahlen in Zk  für i k sei reprk(i) das entsprechende Zeichen  reprk Umkehrfunktion von numk Reprk:

Zk

0

8 Lemma 0 k

k

Div: Ganzzahlige Divison Mod: Division mit Rest Lemma x = y(x div y) + (x mod y)

Division & Modulo

Binärdarstellung

Formale Definition

Zweierkomplement

Übersetzung

Trick (wichtiger als Definition) 1. Binärdarstellung |x| 2. Führende 0 füllen 3. Ziffern negieren 4. +1 addieren Bedeuttungserhaltende Abbildungen von Wörtern auf Wörter Definition Strukturerhaltende Abbildung * -freier Homomorphismus

Kein Informationsverlust Homomorphismus f induzierter Homomorphismus

Präfixfreier Homomorphismus Für keine zwei verschiedene Symbole x1, x2 A gilt: h(x1) Präfix von h(x2) Codierung Präfixfreie injektive Übersetzung Huffmanbaum Block-Codierung Wörter statt einzelne Zeichen codiert Wurzel: Oberster Knoten HuffmanCodierung

Konstruktion 1. Unterste Ebene: Alle Zeichen + Häufigkeit 2. Geringste Häufigkeiten verbinden 3. Kanten beschriften Eigenschaften  Eindeutig  präfixfrei  alle Codes führen zur kürzesten Codierung eines Wortes

Homomorphismus

Präfixfrei

Länge des übersetzten Codewort eindeutig Bit: Zeichen des Alphabets {0,1} 

Byte: Wort aus 8 Bits Präfix

Bit & Byte

Speicherzustand Adresse Wert Speicher

9 & 10

memread Mem Adr Val memwrite ValAdr Adr Val ValAdr

Grobstruktur

Register (Akku): Speicher für Adr Rechenwerk: Argumente aus Akku MIMA (Prozessor) Eigenschaften  Adressen: 20 Bit  Werte: 24 Bit Befehscodierung  4 Bit OpCode  20 Bit Parameter Ablauf 1. Holphase 2. Decodierungsphase 3. Ausführungsphase

Definition G = (N, T, S, P)

Kontextfreie Grammatik 12

(Typ-2Grammatik)

Nichtterminalsymbole N Terminalsymbole T: Startsymbol: Produktion: * Menge an gültigen Ersetzungen Ableitung

Ableitungsbaum Erzeugte Sprache L(G) = {w T*|S * w} Term ATer ={(,,,)} VarPL ConstPL FunPL

Prädikatenlogik erster Stufe Syntax

Variablensymbole VarPL xi Konstantensymbole ConstPL ci Funktionssymbole FunPL fi Jedes fi hat Stelligkeit ar(fi) + Atomare Formeln ARel = ATer RelPL Terme mit Relationssymbolen Ri Ri liefert Wahrheitswert und hat Stelligkeit ar(Ri) + Prädikatenlogische Formeln AFor = ARel {Konnektive, }

13

Prädikatenlogik erster Stufe Semantik

Atomare Formeln mit AL-Konnektiven & Quantoren Interpretation

Interpretation

prädikatenlogische Tautologien

Variablenvorkommen bv(G) = {x, y}, fv(G) = {y} Substitution

Modelle

Logisch äquivalente Formeln

freie Variablensymbole Wirkungsbereich des Quantors gebundene Variablensymbole Variable an Quantor gebunden Geschlossen: fv(G) = {} Substitution

VarPL LTer LTer LTer LFor LFor Regel  

gleichzeitig substituieren gebundene Variablen nicht

Kollisionsfrei

Jedes freies Vorkommen von xi in G, nicht im Wirkungsbereich eines Quantors xj oder xj Logisch äquivalente Formeln valD,I,ß(G) = valD,I,ß(H) Lemma G und H logisch äquivalent dann G H allgemeingültig Axiome Hilbert-Kalkül

Modus Ponens

Generalierung

Korrekt / vollständig

Deduktionstheorem

Algorithmus

Eigenschaften  endliche Ein- & Ausgabe  endliche elementare Anweisungen  Determinismus  Beschreibungen, Anweisungen Zuweisungssymbol:

Hoare-Triple

Hoare-Triple {P} S {Q} P = Vorbedingung Q = Nachbedingung S = Programmstück Zusicherung Prädikatenlogische Formeln (P, Q)

14

Gültigkeit Hoare-Kalkül

HT-I

Regeln

Vor- & Nachbedingung

Graphen

Isomorphie G1 = (V1, E1) = G2 = (V2, E2) Bijektion f: V1 V2

Graph

Knotenmenge V Kantenmenge Kante von x nach y 15 Gerichteter Graph G = (V, E)

Graphisomorphismus

Pfad p = (v0, …, vn) V(+) Länge = Anzahl Kanten Zyklus p = (v0, …, vn) mit v0 = vn, n Einfacher Zyklus wiederholungs-freier Zyklus Azyklischer Graph kein Teilgraph ist Zyklus

Strenng zusammenhängend

Knotengrad Eingangsgrad d-(x) = |{y V|(y,x) E}| Ausgangsgrad d+(x) = |{y V|(x,y) E}| Grad d(x) = d-(x) + d+(x) Gerichteter Baum 1 Pfad p = (r, …, x) Schlinge Teilgraph G‘ = (V‘, E‘) ist ein Teilgraph von G = (V, E), wenn  V‘ V  E‘ E V‘ V‘ Lemma Für jeden gerichteten Graphen G und jedes i 0 gilt: (x,y) in der Relation Ei, wenn in G ein Pfad der Länge i von x nach y vorhanden Streng zusammenhängend (x,y) V² Pfad von x nach y Korollar Sei G ein gerichteter Graph. (x,y) in der Relation E*, wenn ein Pfad von x nach y in G existiert. Knotenmenge V Adjazente Knoten durch Kante minteinander Verbunden Kantenmenge }

Ungerichteter Graph U = (V, E)

Weg p = (v0, …, vn) V(+) Länge = Anzahl der Kanten Kreis geschlossener Weg Einfacher Kreis Wiederholungsfreier Kreis Knotengrad Kantenenden am Knoten ungerichteter Baum ungerichteter Graph zu dem ein gerichteter Baum G = (V, E‘) existiert mit E = E‘u Schlinge

Teilgraph U‘ = (V‘, E‘) ist ein Teilgraph von U = (V, E), wenn  V‘ V  E‘ E {{x,y}|x, y V‘} Streng zusammenhängend Wenn zugehöriger gerichteter Graph streng zusammenhängend Graph mit Beschriftung Gewichteter G = ( V, E, mV)

Gerichteter Graph G = (VG, EG) Adjazenzmatrix A {0,1}|VG|x|VG|

Sei U = (VU, EU) gerichteter Graph. Adjazenzmatrix A {0,1}|VU|x|VU|

Adjazenzmatrix

16

Quadrierte Adjazenzmatrix

Lemma Sei G ein gerichteter Graph mit Adjazenzmatrix A. Für alle k 0 gilt: (Ak)ij ist die Anzahl der Pfade der Länge k in G von i nach j. Gerichteter Graph G = (VG, EG) Wegematrix W {0,1}|VG|x|VG|

Wegematrix Berechnung Wegematrix Sei G ein gerichteter Graph mit Adjazenzmatrix A. Dann gilt für alle k n-1

Adjazenzmatrix

Matrizenmultiplikation Matrizenaddition Seien A und B zwei m n Matrizen C = A + B mit Cij = Aij + Bij Einheitsmatrix Matrizen Matrizendarstellung für Ek Sei G ein gerichteter Graph mit Adjazenzmatrix A

Asymptotisches Wachstum Seien f, g: 0 0+. Dann gilt: f g 0: 0: Groß-O-Notation

Lemma ist Äquivalenzrelation -Kalkül = {g|f g} = {g| 0 0 0:

+:

O-Kalkül = {g| +: 0 0: 0:  genau dann wenn g asymptotisch höchstens so schnell wächst wie f  O(1) = konstante Laufzeit

17

Notation für obere & untere Schranke

Lemma Für alle f1, f2: 0 0+ gilt: O(f1) + O(f2) = O(f1 + f2) -Kalkül = {g| 0: 

+:

0

0:

genau dann wenn g asymptotisch mindestens so schnell wächst wie f

Lemma

nc cn Seien a 1 und b 1 Konstanten, f: 0 0+ und T(n) eine Laufzeitfunktion der Form: T(n) = aT Mastertheorem

+ f(n)

Dann gilt nach Mastertheorem:

Zustandsmenge Eingabealphabet Beispiel Getränkeautomat

Zustandsüberführungsfunktion Ausgabenalphabet Ausgabefunktion * Definiton

18

Zustandsüberführungsfunktionen

Mealy-Automaten

 

f** alle Zustände f* letzter Zustand

Ausgabefunktionen letzte Ausgabe: g*: Z X* Y*

letzte Eingabe ausgeben

Zustandübergänge

alle Ausgaben: g*: Z X* Y*

alle Eingaben ausgeben Definiton

Ausgabefunktionen letzte Ausgabe: g* = h f* MooreAutomaten

letzte Eingabe ausgeben alle Ausgaben: g** = h** f**

alle Eingaben ausgeben Fazit Ausgabe hängt nur vom Zustand ab Definition

Endliche Akteptoren

Zustände F Akeptierend (Doppelkringel) } Wort w X* wird akzeptiert, falls f*(z0, w) F Ablehnend Wort w X* wird akzeptiert, falls f*(z0, w) F Definition Zeichenfolge über Alphabet A Z A = kein Zeichen aus Z

Reguläre Ausdrücke 19

Beschreibung formaler Spracher

Defintion mittels kontextfreier Grammatik

Regeln Stern vor Punkt vor Strichrechnung Ableitungsbaum

Durch R beschriebene formale Sprache

Rechtslineare Grammatik (Typ-3Grammatik)

Kantorowitsch-/ Regex-Baum

Definition  Entweder Wurzel zugleich Blatt mit beschriftet  Oder Wurzel mit beschriftet und hat Nachfolgeknoten der Wurzel eines Regex-Baum ist  oder Wurzel mit beschriftet und hat zwei Nachfolgeknoten die Wurzel zweier Regexbäume sind Lemma Zu jedem regulären Ausdruck R gibt es eine rechtslineare Grammatik G mit L(G) =

Graphische Darstellung

Definition Turingmaschine

Tabellarische Darstellung

Konfiguration c = (z, b, p)  z = aktueller Zustand  b: X = aktuelle Beschriftung des Bandes  p = aktuelle Position Endkonfiguration Konfiguration t und * Für t 0 liefert t(c) die ausgehend von Konfiguration c nach t Schritten erreichte Konfiguration

20

Berechnung

Endliche Berechnung (c0, c1, c2, …,ct) mit ci = 1 (ci-1) für alle Unendliche Berechnung Für jede Konfiguration ist eine Nachfolgekonfiguration definiert Zeitkomplexität timeT und Timet timeT(w) = das t, für das t c0(w))

Komplexitätsklasse

Timet(n) = max{timeT(w) w An} Raumkomplexität spaceT(w) = Anzahl der Felder, die während der Berechnung für Eingabe w benötigt werden

P Palindrome PSPACE Äquivalenz regulärer Ausdrücke

SpaceT(n) = max{spaceT(w)|w An} Komplexitätsklasse Menge von Problemen P: Menge aller Entscheidungsprobleme, die von TM entschieden werden können, deren Zeitkomplexität polynomiell ist PSPACE: Menge aller Entscheidungsprobleme, die von TMs entschieden werden können, deren Raumkomplexität polynomiell ist Turingmaschine als Akzeptor Eine TM kann analog zu endlichen Automaten als Akzeptor für formale Sprachen genutzt werden. Es gilt dann:

Entscheidbarkeit

Unendscheidbarkeit

Entscheidbar Sprache L A* TM stoppt auf allen Eingaben und Eingabe w wird akzeptiert wenn w L Semi-entscheidbar Sprache L A* TM akzeptiert Eingabe w für w L und für w L Verhalten nicht definiert Halteproblem H = {w A*|w ist eine TMCodierung und Tw(w) hält}...