gdi-zusammenfassung/zusammenfassung.md

Einführung

Definition Informatik:

Informatik ist die Wissenschaft, die sich mit den theoretischen Grundlagen, den Mitteln und Methoden sowie mit der Anwendung der elektronischen Datenverarbeitung beschäftigt, das heißt mit der Informationsverarbeitung unter Einsatz von Computern.

EVA-Prinzip

Die Datenverarbeitung verläuft in aller Regel nach dem EVA-Prinzip, das heißt nach dem Prinzip Eingabe \rightarrow Verarbeitung \rightarrow Ausgabe, oder in englischer Sprache Input \rightarrow Process \rightarrow Output, weshalb man auch vom IPO-Prinzip spricht.

Datentypen

Bemerkung	Datenstruktur
int, Integer	ganze Zahlen
float, real	reele Zahlen
boolean	logische Werte
String, Char, Char[]	Zeichen, Zeichenketten
statisch	Array, Verbund
dynamisch	Stack, Queue, verkettte Liste
partiell geordnet	Heap

Zahlensysteme

Umrechnung von Dezimalzahlen

Ein einfacher Weg eine Dezimalzahl in eine Binär, Okta oder Hexadezimalzahl um zu wandeln ist es, die Dezimalzahl durch die Basis des neuen Zahlensystems mit Rest zu teilen. Anschließend wird der Rest von der Letzten Teilung zur ersten im neuen Zahlensystem notiert. Ein beispiel hierzu findest du unter Umrechnung \lable(Dezimalzahl zu Dualzahl).

Binärzahlen (Dualzahlen)

Umrechnung Dualzahl zu Dezimalzahl

Umrechnung Dualzahl zu Dezimalzahl:

Eine (n + 1)-stellige Dualzahl oder auch Binärzahl ist eine Folge von n + 1 Ziffern {a}^{n} {a}^{n-1}\cdots {a}^{1} {a}^{0}, die alle entweder gleich 0 oder gleich 1 sind. Der dezimale Wert dieser Zahl beträgt {a}^{n} \cdot {2}^{n} + {a}^{n−1} \cdot {2}^{n-1} + \cdots + {a}^{1} \cdot 2 + {a}^{0}

{101010}_{2}=1 \cdot {2}^{5} + 0 \cdot {2}^{4} + 1 \cdot {2}^{3} + 0 \cdot {2}^{2} + 1 \cdot {2}^{1} + 0 \cdot {2}^{0} = 32 + 8 + 2 = 42

Umrechnung Dezimalzahl zu Dualzahl

Umrechnung Dezimalzahl zu Dualzahl mit Hilfe des Teilens mit Rest der gegebenen Dezimalzahl: Gegeben sei die Zahl 157 so wird diese durch 2 geteilt und der Rest notiert. Das ergebnis der Division wird dann wieder durch 2 geteilt bis man bei 0 angelangt ist.

157 : 2 = 78 Rest 1 78 : 2 = 39 Rest 0 39 : 2 = 19 Rest 1 19 : 2 = 9 Rest 1 9 : 2 = 4 Rest 1 4 : 2 = 2 Rest 0 2 : 2 = 1 Rest 0 1 : 2 = 0 Rest 1

Der rest wird nun in umgekehrtet Reihenfolge notiert und bildet so die Binärzahl {10011101}_{2}.

Addition und Subtraktion Dualzahlen

	+	=	Übertrag
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

	-	=	Übertrag
0	0	0	0
1	0	1	0
1	1	0	0
0	1	0	1

Man kann subtrahieren durch Addieren indem man aus der zu Subtrahierenden Zahl das Einserkomplement bildet. Aus 101101 wird dadur 010010 dies Addiert man mit der Zahl von der Subtrahiert werden soll, addiert eine weitere 1 und streicht dann die vorderste 1 aus dem Ergebnis. Die Zahlen müssen beide die gleiche Anzahl an stellen haben. Notfalls wird mit 0 vorne dran aufgefüllt.

Das Einserkomplement einer Dualzahl erhält man, indem man die Nullen der Zahl durch Einsen und ihre Einsen durch Nullen ersetzt. Ihr Zweierkomplement erhält man, indem man zu ihrem Einserkomplement noch 1 2 addiert.

Hexadezimal

Zur besseren Lesbarkeit können lange Binärwerte in Hexadezimalwerte umgewandelt werden. Hierzu werden die Binärwerte von rechts nach links in 4er Blöcke eingeteilt (Fehlende stellen werden einfach mit 0en von vorne befüllt) und in ihren Dezimalwert und dann in den Hexadezimalwert überführt.

Gegeben sei {11001111101}_{2} von rechts beginnend {1101}_{2}, {0111}_{2}, {0110}_{2}. Wieder von rechts nach link die viererblöcke in ihren Hexadezimalwert umwandeln, daraus flogt {0110}_{2} = 6 = {6}_{16}, {0111}_{2} = 7 = {7}_{16}, {1101}_{2} = 13 = {D}_{16} der Hexadezimalwert {67D}_{16}.

Binärwert	Dezimalwert	Hexadezimalwert
0000	0	0
0001	1	1
0010	2	2
0011	3	3
0100	4	4
0101	5	5
0110	6	6
0111	7	7
1000	8	8
1001	9	9
1010	10	A
1011	11	B
1100	12	C
1101	13	D
1110	14	E
1111	15	F

Man erhält den hexadezimalen Wert einer Dualzahl, indem man sie von rechts nach links in Vierergruppen zusammenfasst und die hexadezimalen Werte die- ser Vierergruppen aufschreibt. Umgekehrt erhält man die duale Darstellung einer Hexadezimalzahl, indem man die einzelnen hexadezimalen Ziffern in duale Vierergruppen auflöst

Zeitkomplexität

Ist T(n) die von n abhängige Laufzeit eines Algorithmus und gibt es eine Zahl c > 0, sodass für alle n die Beziehung T(n) \leq c · n gilt, so schreibt man kurz T(n) = O(n) und sagt, die Zeitkomplexität ist von der Größenordnung O(n). Das Symbol O(n) wird als ein Landau-Symbol bezeichnet.

Sind f(n) und g(n) auf den natürlichen Zahlen definierte Funktionen mit positiven Werten, so gilt f(n) = O(g(n)), falls es eine konstante Zahl c gibt, sodass f(n) \leq c · g(n) für alle hinreichend großen natürlichen Zahlen n gilt.

Die Turing Maschine

Aufbau:

1. Ein Band mit beliebig vielen Speicherstellen

• Einem Lese/Schreibkopf um diese Speicherstellen auszulesen, zu löschen, zu beschreiben oder so zu belassen.
• Der Lese/Schreibkopf kann um eine Stelle nach links oder rechts rücken oder stehen bleiben.
• Schreiben kann der Kopf ein Alphabet aus endlich vielen Zeichen, zu denen immer das Leerzeichen "Blank" gehören muss.
• Das Alphabet hängt vom jeweiligen Programm der Turing-Maschine ab.
• Das Programm wird durch Anweisungen und verschiedene Zustände der Maschine beschrieben.

z_0 ,1 → z_1 ,a,R
z_1 ,1 → z_1 ,1,R
z_1 ,b → z_1 ,b,R
z_1 , → z_2 ,b,L
z_2 ,b → z_2 ,b,L
z_2 ,1 → z_2 ,1,L
z_2 ,a → z_0 ,1,R
z_0 ,b → z_0 ,1,R
z_0 , → z_E ,,H

z_X beschreibt die verschiedenen Zustände. R und L die Richtung in die der Lesekopf sich bewegt.

z_0 , 1 -> z_1 ,1,R
z_1 , 1 -> z_1 ,1,R
z_1 , + -> z_2 ,1,R
z_2 , 1 -> z_2 ,1,R
z_2 ,  -> z_3 ,,L
z_3 , 1 -> z_E ,,H

Von-Neumann-Architektur

-- Folgt!!

Algorithmen

Definition:

Ein Algorithmus ist eine endliche Menge von eindeutig festgelegten Verfahrensvorschriften zur Lösung eines Problems durch eine in der Regel endliche Menge von Einzelschritten.

Definition Funktion:

Eine Funktion f heißt berechenbar, wenn es einen Algorithmus gibt, der für jedes Argument x den Funktionswert f (x) berechnet.

Charakteristische Eigenschaften

TGI01

Charakteristika	Beschreibung
Finitheit	Die Vorschrift ist mit endlichen Mitteln beschreibbar.
Detterminismus	Es ist immer eindeutig definiert, welche Regel in der vorschrift als nächstes anzuwenden ist.
Determiniertheit	Die Ausgabe ist immer eindeutig bestimmt.
Platzkomplexität	Das Verfahren darf zu jedem Zeitpunkt nur angemessen viel Speicherplatz benötigen.
Zeitkomplexität/Terminiertheit	Das Verfahren sollte zu einem angemessenen Zeitpunkt terminieren.

GOP

Charakteristika	Beschreibung
Endlichkeit	Ein Algorithmus muss aus einer endlichen Anzahl von Lösungsschritten bestehen und nach Abarbeitung dieser endlich vielen Schritte nach einer endlichen Zeit das Ende erreichen.
Eindeutigkeit	Die einzelnen Schritte eines Algorithmus und ihre Aufeinanderfolge müssen ein deutig beschrieben sein.
Allgemeinheit	Ein Algorithmus darf nicht nur die Lösung einer speziellen Aufgabe (z.B. Sortieren einer konkreten Zahlenfolge), sondern muss die Lösung einer Klasse von Problemen (z.B. Sortieren einer beliebigen Zahlenfolge endlicher Länge) beschreiben.
Determiniertheit	Die mehrmalige Anwendung eines Algorithmus mit denselben Eingabedaten muss i.a. dieselben Ausgangsdaten liefern.
Effektivität	Ein Algorithmus muss real von einer Maschine durchführbar sein.
Effizienz	Ein Algorithmus muss möglichst wenig Speicher und eine möglichst geringe Rechenzeit erfordern.

Sortieren-Algorithmen

Anforderungen an Sortieralgorithmen

QuickSort

Prinzip: teile und herrsche (split)

Algorithmus: QuickSort

Eingabe: Feld natürlicher Zahlen A
Ausgabe: Feld natürlicher Zahlen A
Problem: Sortiere A

QuickSort(A)
1. Falls A.length() ≤ 1 gib A zurück
2. Wähle pivot := A.length()/2
3. (split) Bilde für alle n <> pivot
    A_1 = [A[n] | A[n] ≤ A[pivot]]
    A_2 = [A[n] | A[n] > A[pivot]]
4. Rufe QuickSort rekursiv mit den beiden Listen auf:
    A'_1 = QuickSort(A 1 )
    A'_2 = QuickSort(A 2 )
5. (merge) Füge die Ergebnisse zusammen:
    Setze A = A 0 1 + A[pivot] + A 0 2
6. Gib A aus

MergeSort

Prinzip: teile und herrsche (merge)

Algorithmus: MergeSort

Eingabe: Feld natürlicher Zahlen A
Ausgabe: Feld natürlicher Zahlen A
Problem: Sortiere A

MergeSort(A)
1. Falls A.length() ≤ 1 gib A zurück
2. Wähle pivot := A.length()/2
3. (split) Bilde für alle n
    A_1 = [A[n] | n < pivot]
    A_2 = [A[n] | n ≥ pivot]
4. Rufe MergeSort rekursiv mit den beiden Listen auf:
    A'_1 = MergeSort(A 1 )
    A'_2 = MergeSort(A 2 )
5. (merge) Füge die Ergebnisse zusammen:
    Setze A = Merge(A 0 1 , A 0 2 )
6. Gib A aus

HeapSort

Zeitkomplexität: O\(n \cdot {log}_{2}\(n\)\)

Algorithmus: HeapSort

Eingabe: Feld natürlicher Zahlen A
Ausgabe: Feld natürlicher Zahlen A
Problem: Sortiere A

HeapSort(A)
1. Erstelle aus A einen Heap H
2. Solange der Heap H nicht leer ist
  2.1. Entnimm das oberste Element von H füge es von hinten in A ein.
  2.2. Bilde aus den entstandenen zwei Heaps wieder einen neuen Heap H
3. Gib A aus

BubbleSort

Algorithmus: BubbleSort

Eingabe: Feld natürlicher Zahlen A
Ausgabe: Feld natürlicher Zahlen A
Problem: Sortiere A

BubbleSort(A)
1. i := 1
2. Solange i < length(A)
  2.1. j := 1
  2.2. Solange j < length(A)
    2.2.1. Falls A[ j] < A[ j + 1], dann tausche
    2.2.2. j := j + 1
  2.3. i := i + 1
3. Gib A aus

Algorithmus: BubbleSort, Verbesserte Version

Eingabe: Feld natürlicher Zahlen A
Ausgabe: Feld natürlicher Zahlen A
Problem: Sortiere A

BubbleSort2(A)
1. i := 1
2. Solange i < length(A)
  2.1. j := 1
  2.2. Solange j < (length(A) − i + 1)
    2.2.1. Falls A[ j] < A[ j + 1], dann tausche
    2.2.2. j := j + 1
  2.3. i := i + 1
3. Gib A aus

RedixSort

Prinzip: linear Bemerkung: benötigt extra großen Platz

Suchen-Algorithmen

Lineare Suche

Algorithmus: Lineare Suche, formal

Eingabe: Wort w, Liste von Namen L
Ausgabe: wahr, f alsch
Problem: Ist w in L?
LineareSuche(w,L)

1. i := 1
2. Solange i ≤ Länge(L):
  2.1. Wenn L i == w, so beende mit wahr.
  2.2. Anderenfalls i := i + 1.
3. Beende mit f alsch.

BinarySearch

Vorraussetzung: Sortierte Liste

Algorithmus: Binäre Suche

Eingabe: Wort w, Liste von Namen L
Ausgabe: wahr, f alsch
Problem: Ist w in L?

BinäreSuche(w,L)
1. first := 1
2. last := Länge(L)
3. middle := ( first + last)/2
4. Solange first ≤ last:
 4.1. Wenn L middle < w, dann first := middle + 1.
 4.2. Anderenfalls, wenn L middle == w, dann beende mit wahr.
 4.3. Anderenfalls last := middle − 1.
5. Beende mit falsch.

HeapSearch

QuickSearch

Selektion-Algorithmen

QuickSelection

Algorithmus: QuickSelection

Eingabe: Feld natürlicher Zahlen A, Zahl k
Ausgabe: Zahl i
Problem: k-größtes Element nach Sortierung von A

QuickSelect(A,k)
1. Wähle pivot := A.length()/2
2. (split) Bilde für alle A[n]
  A_1 = [A[n] | A[n] < A[pivot]]
  A_2 = [A[n] | A[n] ≥ A[pivot]]
3. Falls A_2.length() = k gibt A[pivot] aus
4. Falls A_2.length() > k rufe QuickSelection(A_2 , k) auf
5. Falls A_2.length() < k rufe QuickSelection(A_1 , k − A_2.length()) auf

k-Selektion

Algorithmus: Selektion

Eingabe: Feld natürlicher Zahlen A, Zahl k
Ausgabe: Zahlen i
Problem: k-größtes Element nach Sortierung von A

kSelection(A,k)
1. BubbleSort(A)
2. Gib A[A.length() − k] aus

Max-Search

Algorithmus: MaxSearch2

Eingabe: Feld natürlicher Zahlen A
Ausgabe: Zahl i
Problem: Maximum von A

MaxSearch2(A)
1. i := 0
2. Solange i < (A.length() − 1)
  2.1. Falls A[ j] < A[ j + 1], dann tausche
  2.2. j := j + 1
3. Gib A[A.length() − 1] aus

Algorithmus: MaxSearch3

Eingabe: Feld natürlicher Zahlen A
Ausgabe: Zahl i
Problem: Maximum von A

MaxSearch3(A)
1. max := 0
2. j := 1
3. Solange j ≤ A.length()
  3.1. Falls A[ j] > A[max], dann max := j
  3.2. j := j + 1
4. Gib A[max] aus

MinMax-Selektion

Prinzip: Tournament-Methode

Algorithmus: MinMaxSearch

Eingabe: Feld natürlicher Zahlen A
Ausgabe: Zahlen i, j
Problem: Minimum und Maximum von A

MinMaxSearch(A)
1. max := 0
2. j := 1
3. Solange j ≤ A.length()
  3.1. Falls A[ j] > A[max], dann max := j
  3.2. j := j + 1
4. min := 0
5. j := 1
6. Solange j ≤ length(A)
  6.1. Falls A[ j] < A[min], dann min := j
  6.2. j := j + 1
7. Gib A[min], A[max] aus

Algorithmus: MinMaxSearch2

Eingabe: Feld natürlicher Zahlen A
Ausgabe: Zahlen i, j
Problem: Minimum und Maximum von A

MinMaxSearch2(A)
1. max := 0
2. min := 0
3. j := 1
4. Solange j ≤ length(A)
  4.1. Falls A[ j] > A[max], dann max := j
  4.2. Falls A[ j] < A[min], dann min := j
  4.3. j := j + 1
5. Gib A[min], A[max] aus

kmp-Matching

Beim KMP-Matching erstellt man ein next Array um das Suchpattern immer um die Maximal möglichen Positionen nach vorne zu verschieben. Zur ermittlung dieses Array geht man wie folgt vor:

Man nehme das Suchpattern und bestimmt für jede Position an der ein Fehler auftreten kann um wieviele stellen man das Pattern nach vorn verschieben kann. Beispiel p = 1010011, dann schaut man p'= 0 != 1 = p nun prüft man um wieviele stellen man p verschieben kann in dem man p' von hinten an p anlegt, next[0] = 0. Für

Position	p' = p[0-p'.length()]	next
0	p' = 0 != 1 = p	next[0] = 0
1	p'= 11 != 10 = p	next[1] = 0
2	p' = 100 != 101 = p	next [2] = 1
3	p' = 1011 != 1010 = p	next [3] = 1
4	p' = 10101 != 10100 = p	next [4] = 3
5	p' = 101000 != 101001 = p	next [5] = 0
6	p' = 1010010 != 1010011 = p	next [6] = 2

Eingabe: Pattern P
Ausgabe: Array next
Problem: Erstelle KMP-Matching next Array

kmpArray(p)
1. next[] := []
2. i := 0
3. Solange i < p.length()
    3.1. p1 := p[0:i] 
    3.2. pruef := p...

Boyer-Moore-Matching

Robin-Karp-Matching

Sonstige-Algorithmen

Polnische Notation

Algorithmus: Erzeuge inverse polnische Notation

Eingabe: Infix-Zeichenkette: I
Ausgabe: Postfix-Zeichenkette: P
Problem: Inverse polnische Notation

WandlePost f ix(I)
1. S = init()
2. Solange length(I) > 0
  2.1. z := nextZeichen(I)
  2.2. Falls z eine Ziffer, so P := P · z
  2.3. Falls z ein Operator, so S.put(z)
  2.4. Falls z eine öffnende Klammer, so tue nichts.
  2.5. Falls z eine schließende Klammer, P := P · S.pop()
3. Gegebenenfalls füge Reststapel S noch an P an.
4. Gib P aus.

Hashing

schnelles Multiplizieren