Grundlagen der Informatik zusammengefasst

Konkatenation beschreibt eine Neubildung eines Wortes mittels Zusammensetzen von Wörtern zu einem neuen Wort durch Aneinanderhängen der Symbolfolgen.

Die Konkatenation von Zeichenreihen in der Informatik beruht auf demselben Prinzip. Bei gegebenen Zeichenreihen, welche eine endliche Folge von Symbolen eines bestimmten Alphabets Σ sind, werden diese Zeichenreihen aneinandergehängt.

Beispiel:

|K|=f, f= DameKönig Zeichenreihen K und S über
|S|=i, i = AssZwei Σ, in diesem Fall Groß- und Kleinbuchstaben
Konkatenation:KS= DameKönigAssZwei
SK=AssZweiDameKönig

Jede Teilmenge von Σ^* wird Sprache genannt. Im oberen Beispiel sind sowohl DameKönig, AssZwei als auch deren Konkatenationen Teilmengen und somit Sprachen über dem Alphabet Σ.
K und S sind somit Sprachen über Σ.
Hierbei muss weder |K| noch |S| alle Symbole aus Σ nutzen. Wenn K oder S nur einen Teil der Symbole von Σ verwenden, ist L auch eine Sprache über Σ^~.

Eine zulässige Sprache wird definiert durch die Grammatik, welche Wortbildungsregeln und Satzbauregeln beinhaltet.

Ein deterministischer endlicher Automat (kurz DEA) hat eine endliche Menge Q, eine endliche Menge von Eingabesymbolen Σ, eine Übergangsfunktion δ(q,a)=p (q,p ε Q, a ε Σ), eine Menge von finaler / akzeptierender Zustände F ⊆ Q und einen Startzustand q0.
Somit gilt für DEA A = (Q, Σ, δ, q0, F)

Wichtig ist, daß die Zahl der Zustände des DEA endlich ist.

Da die Übergangsfunktion sehr schwer leserlich ist, ist es empfehlenswert ein Übergangsdiagramm zu nutzen um die Funktionsweise des jeweiligen DEA zu verstehen.

Bei der erweiterten Übergangsfunktion wird nicht nur ein Symbol betrachtet sondern ein ganzes Wort. Der Automat berechnet den Zustand mittels wiederholter Anwendung der normalen Übergangsfunktion. Dies bringt eine enorme Arbeitserleichterung.

Die Sprache eines DEA nennt man L(A). Sie wird definiert durch L(A) = {ω | δ*(q0,w) ε F} .
Dies bedeutet die Menge der Zeichenreihen, die A vom Startzustand in den akzeptierten Endzustand führt.

Ist L für einen DEA L(A) dann heißt L reguläre Sprache.

Die Abkürzung „NEA“ steht für Nichtdeterministischer endlicher Automat.
Hierbei handelt es sich um einen Automaten, der zufällig mehrere Zustände annehmen kann. Es wird mit regulären Sprachen gearbeitet, die eine formale Sprache ist, welche einigen Einschränkungen unterliegt. Ein NEA kann auf jeden Fall in ein DEA überführt werden, was aber nicht unbedingt produktiv wäre, da der NEA übersichtlicher ist.

Die passende Formel für einen NEA lautet:

A =(Q,∑,δ,q0,F)

„A” steht für den Automaten.
„∑” für die endliche Menge von Eingangssymbolen.
„δ“ für eine Übergangsfunktion (δ(q,a)=p
(q ∊ Q, p ⊆ Q, a ∊ ∑)).
„Q“ für die Menge akzeptierender Zustände.
„F“ für die Menge Endzustände
„q0“ steht dann noch für den Startzustand.

Da jeder DEA auch als NEA aufgefasst werden kann, ist dies einsichtig. Wenn ein NEA in einen DEA umgewandelt werden soll, benutzt man ein Verfahren, dass sich Potenzmengenkonstruktion nennt.

Hier gilt:

δ'(q, a) = {
{δ(q, a)} : falls δ(q, a)
∅ : sonst.

Wenn NEA gegeben ist: N=(QN,∑,δN,q0,FN),
DEA gesucht ist: D=(QD,∑,δD,{q0},FN)
und L(D)=L(N), können wir einen QD konstruieren.
Da ist dann QD eine Potenzmenge von QN
➝ |QN|=n ➜ |QD|=2n
Alle Zustände, die von q0 nicht erreicht werden können, fallen weg.
Bei der Konstruktion eines FD, werden alle Teilmengen S des QN von FD umfasst, solange sie mindestens einen akzeptierenden Zustand des NEA N enthalten.

Bei der Konstruktion von δD: (∀ S ⊆ QN ∧ a ∊ ∑) gilt:

δD(S,a) = U δN (p,a) p∈s

Es gibt verschieden Operationen, welche auf Spachen angewendet werden können:

Wenn L und M eine Sprache sind, so ist

• L ∪ M die Vereinigung

• LM die Konkatenation

• L* die Kleenesche Hülle

Sei die Sprache L={a,b} und die Sprache M={c,d},
so ist die Vereinigungsmenge L ∪ M ={a,b,c,d}.

Seien L, M Sprachen, dann ist ∀ v∊L, w∊M
LM die Menge aller Zeichenketten vw.

Beispiel:
L={001, 10, 111},

M={ε, 001}
➝LM = {001, 10, 111, 001001, 10001, 111001}

Die (Kleensche) Hülle (auch Stern) einer
Sprache L heißt L* und beschreibt die Menge
aller Zeichenreihen, die durch Verkettung einer
beliebigen Anzahl von Zeichenreihen aus L
gebildet werden.

Beispiel:

• Sei L={0,1}, dann enthält L* alleZeichenketten aus 0en und 1en.

• Sei L={0,11}, dann enthält L* alleZeichenreihen aus 0en und 1en, in denendie 1en paarweise auftreten:0, 011, 1111 aber nicht: 01011 oder 101.

Anwendungsbeispiel:

L={0,11}

• L0= {ε}

• L1= {0,11}

• L2= {00, 011, 110, 1111}

• L3= {000, 0011, 0110, 01111,1100, 11011, 11110, 111111}

Ln={a,b}

L: Name der Sprache

n: Anzahl der Wiederholungen von Worten der Sprache L

z.B. L2 enthält aa, ab, ba oder bb, aber niemals aaa oder aba

{a,b}: In der Klammern stehen die Worte der Sprache, z.B. Buchstaben oder Zahlen.

1. Sei L die Menge aller aus Nullenbestehenden Zeichenketten, dann ist L* = L.

2. Sei L={ε}, dann ist L*={ε}. Damit hat L eine endliche Hülle.

Reguläre Ausdrücke beschreiben bestimmte Zeichenketten. Sie können beispielsweise verwendet werden, um Texte zu durchsuche oder Eingaben zu validieren .

ε und ∅ (leere Menge) sind reguläre Ausdrücke und beschreiben die Sprache L(ε) = ε bzw. L(∅) = ∅.
Für alle a Σ ist a ein regulärer Ausdruck der Sprache L(a) = a.

Desweiteren gilt für reguläre Ausdrücke:
Sind X und Y reguläre Ausdrücke so sind auch
(X+Y)(Alternative auch (X|Y))
(XY) (Verkettung/Konkatenation)
(X*) (Kleensche Hülle)
reguläre Ausdrücke.

Dabei hat der *-Operator Vorrang vor dem Verkettungsoperator, der wiederrum Vorrang vor dem Vereinigungsoperator hat.

• „ . “ = beliebiges Zeichen

• [abc] = a+b+c

• [1-9] = [123456789]

• \ = Escaping

Zeichenklassen

• [:digit:] = [0-9]

• [:alpha:] = [A-Za-z]

• [:alnum:] = [0-9A-Za-z]

Operatoren

• |: = Vereinigung

• ?: = Zeichen kommt einmal oder garnicht vor

• +: = Zeichen kommt ein oder mehr mal vor

• *: = Kleensche Hülle

• {n}: = Zeichen kommt genau n mal vor

Die Unix Regular Expressions haben die gleiche Mächtigkeit (die gleichen Zeichenketten können erkannt werden) wie normale Regular Expressions.

Reguläre Sprachen werden von DEAs bzw NEAs entschieden und können durch Reguläre Ausdrücke beschrieben werden.

Um zu erkennen ob eine Sprache regulär ist, muss man sich die Frgae stellen:
Gibt es einen (deterministischer endlicher Automat) DEA?
Ein Endlicher Automat hat endliche Zahl von Zuständen. Sei das k. Wenn die Eingabe 0^k ist muss ein Zustand q das zweite Mal erreicht sein.

Dies beschreibt in der eine Eigenschaft bestimmter Klassen formaler Sprachen.
In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nichtregulär bzw. nicht kontextfrei ist.

Für jede reguläre Sprache L gibt es eine natürliche Zahl , sodass gilt: Jedes Wort z in L mit Mindestlänge n hat eine Zerlegung mit den folgenden drei Eigenschaften:

1. Die beiden Wörter u und v haben zusammen höchstens die Länge n

2. Das Wort v ist nicht leer.

3. Für jede natürliche Zahl (mit 0) i ist das Wort uv^2w in der Sprache L , d. h. die Wörter uw , uvw , uvvw , uvvvw , usw. sind alle in der Sprache .

Neben den regulären Sprachen gibt es auch nicht-reguläre Sprachen, die dieses Lemma erfüllen. Eine notwendige und hinreichende Bedingung für reguläre Sprachen liefern der Satz von Myhill-Nerode oder Jaffes Pumping-Lemma.

Die Gültigkeit des Lemmas basiert darauf, dass es zu jeder regulären Sprache einen deterministischen endlichen Automaten gibt, der die Sprache akzeptiert.

1. Strukturiert und unstrukturiert

2. Codiert (zeichenweise) – formartiert oder unformatiert

oder: uncodiert (bitweise) – statisch (Bilder) oder dynamisch (Radio)

Information = Daten + Kontext

Qualität von Informationen: zeitgerecht, aktuell, konsistente Datenbasis

Theoretische Informatik

Technische Informatik

Angewandte Informatik

„Bindestrich-“Informatik

Algorithmus: Allgemeine Folge von Anweisungen zur Lösung eines Problems.

Programm: Umsetzung eines Algorithmus in einer Programmiersprache

1. Analyse des Problems

2. Problemlösung (Algorithmus)

3. Programmierung (Codierung)

4. Test

5. Inbetriebnahme

6. Wartung

Existieren verschiedene Modelle, je nach Analysephase, der Elementgröße und Interaktionsgrad zwischen Beteiligten.

Früher 90 % Hardware, 10 % Software, heute 10% Hardware und 90% Software. Tendenz geht gegen 99%.

Ca. 20% der Kosten entstehen bei Analyse und Problemlösung, ca. 80 % Kosten entstehen ab der Codingphase.

==> vernünftige Spezifikation senken Kosten!

Hilfsmittel Use-CASEs, Datenflussdiagramme, Verteilungsmodelle

CASE = Computer Aided Software Engineering

Deshalb: Ersparnis entsteht durch Kenntnis von

• Algorithmen & Datenstrukturen

• Berechenbarkeitstheorie

• Standards

• IT-Sicherheit

• Softwareentwicklung

• Projektmanagement

• Qualitätssicherung (von Anfang an, da Zwischenprüfung unmöglich)

• Projektverwaltung

1.9 Datenschutz &-sicherheit

Schutz vor unberechtigter Nutzung

Schutz vor Verlust bei z.B.:

• Überschwemmung, Feuer

• Einbruch

• Hardwaredefekt

Maßnahmen dagegen: Backup, Redundanz, z.B. RAID Array

Volles Backup,

Dump

,

Inkrementelles Backup

Alle Daten werden gesichert, eine vollständige Wiederherstellung ist möglich, aber hoher Platz und Zeitbedarf

1 zu 1 Kopie des Datenträgers, Problem ist hierbei der Platzbedarf, „Leerraumsicherung“, bitweise

Nur die Änderungen seit dem letzten Backup werden berücksichtigt, aber typische Probleme: Keine Verifizierung, Backup-recovery nie erprobt und Backup ist am gleichen Ort.

BS steht zwischen Anwendungen und BIOS.

Aufgabengebiet ist die Verwaltung von Systemressourcen wie:

• Prozessor

• Arbeitsspeicher

• Plattenspeicher

• Monitor

Ziel: ungestörter Ablauf von Programmen

2.Algorithmen und Datenstrukturen

Mathematik → Algebra (Datentyp)

Algorithmik → Datenstruktur

Programmierung → Typ, Modul,Klasse

• Integer

• real

• boolean

• char

Pointer = zeigt auf die entsprechende Speicherstelle von Datentypen.

• Array

• Struct (Liste)