IT – Algorithmen

Def. genaue, endl. Beschreibung eines allgemeinen Verfahrens, nutzt elementare, ausführbare Schritte

statt 3 + 4  –> a + b

Effektivität

jeder einzelne Schritt ausführbar

Effizienz

Leistungsfähigkeit, geringer Aufwand

Korrektheit

partiell: jedes Ergebnis entspricht der Ausgabespezifikation sofern die Eingaben der Eingabespez. entsprechen, nicht zwingend anhaltend

total: partiell korrekt, terminiert nach endl. vielen Schritten, nach jeder Eingabe, die der Eingabespez. entspricht

Terminierung

Algorihtmus, der bei den Eingabespez. entsprechenden Eingaben nach endlich vielen Schritten abbricht.

Determinismus

weiterer Ablauf des Algorihtmus ist zu jedem Zeitpunkt eindeutig bestimmt, Ablauf nur von Eingaben abhängig

Determiniertheit

liefert immer gleiche Ausgaben bei den Eingabespez. entsprechenden Eingaben

IT – Grammatiken & Notationen

Chomsky-Grammatik

4-Tupel G = ( N , T , P , S )

N – endliche Menge Zeichen, Nichtterminalsymbole

T – endliche Menge Zeichen, disjunkt N, Terminalsymbole

S ∈ N – Startsymbol

P – endliche Menge Regeln der Form (p, q) ∈ ( N ∪ T ) *

 Syntaxdiagramme

N Rechteck

T langrunder Kreis

gerichtete Pfeile verbinden die einzelnen graphischen Elemente

Grundtypen:

  • Sequenz
  • Option
  • Alternative
  • Wiederholung

EBNF

erweiterte Backus Naur – Form

besteht aus:

  • einer Startregel
  • sonstigen Regeln
  • Terminal- und Nicht-Terminalsymbolen

T – nicht speziell gekennzeichnet

N – in <> eingeschlossen

P – Form: rechte Seite = linke Seite

  • linke Seite: genau ein N
  • rechte Seite: T, N, Alternativen, geklammerte Ausdrücke
  • Klammerarten:
    • ( ) Gruppierung
    • [ ] Option
    • { } n-fach (auch 0 mal)

 

 

Chomsky-Grammatik

Formale Grammatik

Viertupel G = (N,Σ,P,S)
N Nichtterminalsysmbole, endlich
T Terminalsymbole, endlich, nicht-leer
P Produktionsregeln, endlich, nicht-leer;
Form (p,q) Element N ∪ T,
p mind. ein Nichtterminalsymbol
S Startsymbol, Axiom, Element N

N disjunkt T: kein Symbol in N und in T

Ableitung

x ∈ (N ∪ T) und (p, q) ∈ P
mit x = x’p“, x‘, x“ ∈ (N ∪ T)*
x → (p, q)y bzw x → y mit y = x’qx‘

Erzeugte Sprache
Menge aller gültigen Wörter, die aus S ableitbar sind

Beispiel

N = {S1}
T = {a,b} -> L = {a,b} *
P = {(S1, E), (S1,aS1b)}
habe ich S1 kann ich dies ersetzen durch E oder aS1b

S1 ->  aS1b -> aaS1bb -> aaaS1bbb -> a³Eb³ = a³b³
aaS1bb = a²S1b²
aaaS1bbb = a³S1b³
ein gültiges Wort der durch die Grammatik erzeugten Sprache

S1 -> E = a0b0
S1 -> aS1b -> ab  = a1b1
-> L (G1) = { w|w = anbn, n ∈ N0 }

Kombinatorik

Satz: Produktregel

k endliche Mengen A1, … , Ak, jeweils n1, … , nk Elemente

Die Anzahl der Möglichkeiten aus jeder Menge genau ein Element zu wählen ist
n1 * n2 * … * nk = ∏ni (i=1 bis k)

Definition: n-Menge := endliche Menge mit n Elementen – Kardinalität: 2hochn

„Kombinatorik“ weiterlesen

Funktionen

Definition

Seien A, B Mengen

Eine Abbildung / Funktion f ist eine Relation, so dass zu jedem a ∈ A genau ein b ∈ B existiert mit (a,b) ∈ f.

Schreibweise: f:A –> B

f(a) – eindeutiges Element, Bild von a
a – Urbild von f(a)

a – Definitionsbereich von f
B – Werte- und Bildbereich von f

f(A) = {b ∈ B: ∃ a ∈ A mit f(a)=b} heißt
Bild von A unter f

„Funktionen“ weiterlesen

Relationen

Beziehungen zwischen Objekten

Äquivalenzrelation – Objekte mit bestimmten Eigenschaften werden als gleich angesehen

Ordnungsrelation – Objekte ordnen hinsichtlich Größe, Schlüsselwert, lexikographisch

Kartesisches Produkt – Kreuzprodukt
Seien A und B nicht leere Mengen

Ist a ∈ A und b ∈ B so ist (a,b) ein geordnetes Paar, geordentes 2-Tupel, geordnetes Tupel, Tupel

A X B := {(a,b): a ∈ A und b ∈B} ist die Menge aller geordneten Paare, das kartesische Produkt von A und B

Ist A =B so schreibt man A X B als A²

Seien n ∈ N und X1, X2, …, Xn nichtleere Mengen

∏Xi := X1 x X2 x … x Xn = {(x1,…,xn): xi ∈ Xi   für 1 ≤ i ≤ n}

Die Elemente (x1, … , xn) von ∏Xi heißen geordnete n-Tupel.

„Relationen“ weiterlesen

Schreibweisen, Notationen, Summenformeln

Definition: Summenzeichen

n

Σ ai := a1 +a2 + … + an

i=1

Defintion: Produktzeichen

n

Π ai := a1 * a2 * … * an

i=1

Gauß-Reihe, Gaußsche-Summenformel

1 + 2 + … + (n-1) + n = n(n+1)/2

Geometrische Reihe, geometrische Summenformel

q0 + q1 + … + qn = qn+1 -1 / q -1

Logik und Aussagen

Die Regeln der Logik bilden die Grundlage mathematischen Argumentierens

Anwendungen

  • Schaltkreiseentwurf
  • Programmiersprachen
  • Verifikation

Definition: Aussagen

Eine Aussage ist ein sprachliches Gebilde, dem genau einer der Wahrheitswerte wahr (w) oder falsch (f) zugeordnet ist.

Bsp.

  • 2 ist eine gerade Zahl – wahre Aussage
  • Bananen sind blau – falsche Aussage
  • nachts ist es kälter als draußen – keine Aussage

„Logik und Aussagen“ weiterlesen