Informatik (Fach) / Grundbegriffe der Informatik (Lektion)

In dieser Lektion befinden sich 41 Karteikarten

Diverse Schlagwörter von GBI und Funktion

Diese Lektion wurde von Gnomo erstellt.

Lektion lernen

  • Die Veränderung einer (oder mehrerer) physikalischer Größen (zum Beispiel Schalldruck) um etwas mitzuteilen nennt man ein Signal Signal
  • Es gibt eine weitere Möglichkeit, Mitteilungen von einem Zeitpunkt zu einem späteren zu „transportieren“: Die Speicherung als Inschrift. Inschrift
  • Das Wesentliche, das übrig bleibt, wenn man z. B. von verschiedenen Medien für die Signalübertragung oder Speicherung absieht, nennt man eine Nachricht. Das, was man speichern und übertragen kann, sind also Nachrichten. Nachricht
  • Vielmehr ist man üblicherweise in der Lage, Nachrichten zu interpretieren und ihnen so eine Bedeutung zuzuordnen. Interpretation
  • Dies ist die einer Nachricht zugeordnete Information. Information
  • Unter einem Alphabet wollen wir eine endliche Menge sogenannter Zeichen oder Alphabet Symbole verstehen, die nicht leer ist. Alphabet
  • kartesisches Produkt Allgemein heißtA χ B kartesisches Produkt der Mengen A und B. Es ist die Menge aller Paare (a,b)mit a ∈ A und b ∈ B:A χ B = {(a,b) | a ∈ A ∧ b ∈ B}
  • Relation Eine Teilmenge ⊆ A χ B heißt auch eine Relation.
  • binäre Relation "von A in B"
  • linkstotal R ⊆ A χ B Für jedes a ∈ A existiert mindestens ein b ∈ B mit (a,b) ∈ R
  • rechtseindeutig R ⊆ A χ B Für jedes a ∈ A existieren mindestens zwei b ∈ B.b1 ∈ Bb2 ∈ Bb1 ≠ b2 (a,b1) ∈ R und (a,b2) ∈ R
  • Abbildung Relation, die linkstotal und rechtseindeutig ist.R: A → B A ist Definitionsbereich und B ist Zielbereich
  • partielle Funktionen rechtseindeutige Funktionen
  • linkseindeutig R ⊆ A χ B Für jedes b ∈ B existiert mindestens ein a ∈ A.b1 ∈ Bb2 ∈ Ba1 ≠ a2b1 ≠ b2(a1,b1) ∈ R und (a2,b2) ∈ R
  • injektiv linkseindeutig
  • surjektiv rechtstotal
  • bijektiv injektiv und surjektiv (linkseindeutig und rechtstotal)
  • rechtstotal R ⊆ A χ B Für jedes b ∈ B existiert mindestens ein a ∈ A mit (a,b) ∈ R
  • Negation "Nicht A" ¬A
  • logisches Und A∧B
  • logisches Oder A∨B
  • logische Implikation "Wenn A, dann B" A⇒B
  • aussagenlogische Formeln Deswegen beschränkt und beschäftigt man sich dann in der Aussagenlogik mit sogenannten aussagenlogischen Formeln, die nach obigen Regeln zusammengesetzt sind und bei aussagenlogische Formeln denen statt elementarer Aussagen einfach Aussagevariablen stehen, die als Werte „wahr“ und „falsch“ sein können.
  • äquivalente Aussagen ¬¬A und AA wahr und B wahr und A∨B wahrImplikation A ⇒ B ist immer wahr, wenn A falsch ist.
  • Allquantor
  • Existenzquantor
  • Wort, formalistisch definiert Dann wollen wir jede surjektive Abbildung ω: Zn → A als ein Wort auffassen.
  • Länge eines Wortes Die Zahl n heiße auch die Länge des Wortes, für die man manchmal kurz |ω| schreibt.
  • Menge aller Wörter A* Ganz häufig ist man in der Situation, dass man ein Alphabet A gegeben hat und über dieMenge aller Wörter reden möchte, in denen höchstens die Zeichen aus A vorkommen. Dafür schreibt man A*.Das ist die Menger aller surjektiven Abbildungen ω:Zn→B mit n ∈ N0 und B ⊆ A.
  • leere Wort ε { }Z0 = { }Surjektive Abbildung ω:{ }→{ } Es gibt nur eine Relation R ⊆ { } x { } = { }, nämlich R = { }. Als Menge von Paaren aufgefasst ist dieses R aber linkstotal und rechtseindeutig, also tatsächlich eine Abbildung,und die ist sogar rechtstotal. Also ist es richtig von dem leeren Wort zu sprechen.
  • Wörter A0={ε}A1={a,b}A2={aa,ab, ba, bb}
  • Konkatenation Schrank · Schlüssel = SchrankschlüsselSchlüssel · Schrank = Schlüsselschrank
  • Konkatenation formal Es seien wei beliebige Wörter ω1: Zm→A1 und ω2: Zn→A2 gegeben.Dann ist ω1 ω2: Zm+n → A1 ∪ A2i → ω1(i) falls 0 ≤ i ≤ mi → ω2(i-m) falls m ≤ i ≤  m+n
  • Für jedes Alphabet A gilt: (Konkatenation) ∀ω1 ∈ A*∀ω2 ∈ A*: |ω1ω2| = |ω1| + |ω2|
  • Für jdes Alphabet A gilt: neutrales Element Man sagt auch, die Null sei das neutrale Element bezüglich der Addition.∀ω ∈ A*: ω · ε = ω ∧ ε · ω = ω.
  • Konkatination mehrerer Wörter (ω1 · ω2) · ω3 = ω1 · (ω2 · ω3)
  • RFC Request for CommentRFC 5322 aktuelle Fassung der E-Mail Struktur Spezifikation
  • induktive Definition ω0 = ε∀k ∈ N0: ωk+1 = ωk + ω
  • vollständige Induktion Induktionsanfang n = 0Induktionsschrit n → n + 1 (beliebiges aber festes n)Induktionsschluss
  • Vollständige Induktion 2 Den Beweis schreibt man typischerweise in folgender Struktur aufInduktionsanfang: Man zeigt, dass A(0) gilt.Induktionsvoraussetzung: für beliebiges aber fest n ∈ N0 gilt: A(n).Induktionsschluss: Man zeigt, dass auch A(n+1) gilt (unter Verwendung von A(n))Den Nachweis, dass die Implikation A(n) ⇒ A(n+1) gilt, nennt man auch den Induktionsschritt.
  • binäre Operartion f : M x M → MÜblich ist ein "Operationssymbol" bspw. ◊◊: M x M → M kommutativ, wenn gilt:∀x ∈ M ∀y ∈ M: x ◊ y = y ◊ x◊: M x M → M assoziativ, wenn gilt:∀x ∈ M ∀y ∈ M ∀z ∈ M: (x ◊ y) ◊ z = x ◊ (y ◊ z)