1

Grundlagen derInformatikWintersemester 2009

Prof. Dr. Peter Kneisel

2

Didaktik: Durchführung

Diese Vorlesung enthält Übungen Die Übungen werden je nach Bedarf durchgeführt. Zur Vorbereitung werden Übungsblätter, je nach Vorlesungsverlauf

zusammengestellt. Weitere Übungen sind im Foliensatz vorhanden und sollten selbständig und

vollständig bearbeitet werden. Vorsicht !

Kommen Sie in alle Veranstaltungen - machen Sie die Übungen Überschätzen Sie sich nicht - auch wenn Sie PC-Crack sind

3

Didaktik: Folien

Der Vorlesungsstoff wird anhand von Folien dargelegt Die Folien bilden nur einen Rahmen für die Inhalte. Die Folien sollten daher mit Hilfe

eigener Vorlesungsskizzen ergänzt werden - am besten in Form einer Vorlesungsnachbereitung max. 3 Tage nach der Vorlesung

Zusätzlich zu den Folien werden Beispiele an der Tafel oder am Rechner gezeigt. Diese sollten Sie vollständig mitskizzieren.

Zur vollständigen Nachbereitung, z.B. als Klausurvorbereitung, sind die Folien einheitlich strukturiert Es gibt genau drei Gliederungsebenen: Kapitel, Unterkapitel, Abschnitte Die Inhalte jedes Kapitels und jedes Unterkapitels werden jeweils motiviert und sind

verbal beschrieben. Zusätzlich gibt es jeweils ein stichwortartiges Inhaltsverzeichnis der Unterkapitel, bzw. Abschnitte

Die Vorlesung wird ständig überarbeitet, so dass sich die Foliensätze ändern können (und werden) Laden Sie sich zur endgültigen vollständigen Klausurvorbereitung nochmals

zusätzlich den kompletten Foliensatz herunter.

4

Literatur

Diese Veranstaltung ist anhand (wirklich) vieler Bücher und einer Menge eigener Erfahrungen erstellt worden. Jedes Buch hat dabei Schwerpunkte in speziellen Bereichen und ist daher sinnvoll. Eine Auflistung aller dieser Bücher ist nicht sinnvoll.Stellvertretend für all diese Bücher sei hier ein Buch angeführt: H.P.Gumm, M.Sommer: „Einführung in die Informatik“; Oldenbourg-Verlag 2004

Motivation ist alles !Hier ein paar Bücher, die das Interesse und den Spaß an der Wissenschaft im Allgemeinen und an der Informatik im besonderen wecken soll: S.Singh: „Fermats letzter Satz“; DTV, 9.Auflage 2004 M. Spitzer: „Geist im Netz“; Spektrum, Akad. Verlag 2000 H. Lyre: „Informationstheorie“; UTB, 2002 A.Hodges: „Alan Turing, Enigma“; Springer-Verlag, 1983 D.R.Hofstadter: „Gödel, Escher, Bach“; Klett-Cotta, 2006 (Taschenbuch 1991)

5

Inhalt

Wie jede Wissenschaft befasst sich die Informatik mit ihren eigenen „Objekten“. Was diese „Objekte“ sind und was man mit diesen Objekten machen kann - und wie - wird in dieser Vorlesung auf eher abstraktem Niveau, aber immer mit Beispielen aus der Realität eines Informatikers (oder einer Informatikerin), erläutert. Diese Vorlesung konzentriert sich auf den „Kern“ der Informatik. Vertieftere

Einführungen in z.B die Bereiche der Programmierung, Rechnerarchitekturen, Betriebssysteme, etc. sollen daher bewusst den entsprechenden Veranstaltungen vorbehalten bleiben

Inhalt1. Informatik2. Information und Codes3. Zeichen und Zahlen4. Datenstrukturen5. Algorithmenentwurf

6

Überblick und Einordnung

TechnischeTheoretischePraktische

Informatik

Dyn

amik

(Alg

orith

mik

)

Elemente

Strukturierung

OOP

PIS AD

Sta

tik (S

trukt

ur)

Information

Codes

Zeichen

Zahlen

Daten-strukturen

21

3RA

AFSSWT RN

4

5

7

Kapitel 1 Information

Information ist der grundlegende Begriff der Informatik. Mehr noch: „Der Begriff der Information ist vermutlich das zentrale interdisziplinäre Brückenkonzept der modernen Wissenschaften * “.Dieses Kapitel beschreibt, aus welchen Aspekten Information besteht, welche für die Informarik wesentlichen Definitionsansätze es gibt und wie Information in der Informatik tatsächlich dargestellt wird.

Inhalt1. Was ist Information2. Nachrichtentechnische Definition3. Algorithmische Definition4. Darstellung in der Informatik

* (einige Teile dieses Kapitels entstammen: H.Lyre: „Informationstheorie)

Im Anfang war das WortJohannes 1.1

8

1.1 Was ist Information

Es deutet einiges darauf hin, dass „Information“ ein zumindest ebenso fundamentaler Begriff ist, wie „Stoff“ in der Chemie und „Energie“ in der Physik (die tatsächlich schon zu „Materie-Energie“ vereint wurden).Betrachtet man Information als ursächliche (atomare) Größe so ist die Frage: „was ist Information“ eher irrelevant. Dafür rücken Fragestellungen wie „woraus besteht Information“, „worin ist Information“, „was kann ich mit Information machen“ in den Vordergrund.In diesem Unterkapitel soll die erste dieser Fragen: „woraus besteht Information?“ betrachtet werden

Inhalt1. Semiotische Dreidimensionalität2. Semantik und Pragmatik3. Semantische Ebenen

9

1.1.1 Semiotische Dreidimensionalität

Die wohl wichtigste Charakterisierung des Informationsbegriffes entspringt der „Semiotik“ – der Zeichenlehre (Also die Lehre, die sich mit Zeichen bzw. Symbolen befasst) und lässt sich auf den Informationsbegriff übertragen. Demnach haben Informationseinheiten drei Aspekte: die Syntax betrifft das Auftreten einzelnder Informationseinheiten und ihrer

Beziehungen untereinander. die Semantik betrifft die Bedeutung der Informationseinheiten und ihre Beziehungen

untereinander. die Pragmatik betrifft die Wirkung der Informationseinheiten und ihrer Beziehungen

untereinander. Diese drei Aspekte

müssen in ihrer Gesamtheit berücksichtigt werden(entweder explizit oder implizit)

sind ungewichtet haben keinen Bezug zum informationsverarbeitenden System (z.B. Mensch,

Maschine, …)

10

1.1.2 Semantik und Pragmatik

Carl Friedrich von Weizsäcker: Information ist nur, was verstanden wird Information ist nur, was Information erzeugt

(die wiederum syntaktische Aspekte hat, verstanden werden muss und Information erzeugen muss, die wiederum … hermeneutischer Zirkel)

Der Aspekt „verstanden werden“ erlaubt keine strenge Formalisierung (denn was bedeutet „verstanden werden“ – wie kann man es messen)sehr wohl lässt sich aber der Aspekt „Information erzeugen“ formalisieren.Beispiel: Person A bittet Person B, das Licht einzuschalten:

Sequenz von Zeichen: „B I T T E S C H A L T E D A S L I C H T A N“ Person B „interpretiert“ die Zeichenkette = wertet die Semantik, die Bedeutung der

Zeichenkette aus – dabei kann man sich streiten, ob er die Bedeutung auch „verstanden“ hat oder auch nur haben muss.

Person B generiert neue Information:Licht = onoder stellt sich einen erleuchteten Raum vor, was neurologisch zu messen ist.

Da Semantik und Pragmatik eng miteinander verzahnt sind spricht man auch vom semantopragmatischen Aspekt der Information

11

1.1.3 Semantische Ebenen

Der semantopragmatischen Aspekt der Information zeigt die Unmöglichkeit eines absoluten Begriffs von Information, d.h. Information ist relativ zu den semantischen Ebenen der beteiligten Systemen.Beispiel (siehe 2.1.2): Person A spricht deutsch, Person B kann kein deutsch

d.h. die semantischen Ebenen sind völlig disjunkt.Daher ist in diesem Bezugssystem zwar der syntaktische Aspekt von Information, aber keine semantischer und damit (sehr wahrscheinlich;-) auch kein pragmatischer Aspekt und damit auch keine Information vorhanden.

In der Realität sind unterschiedliche semantische Ebenen die Regel und verändern sich auch dynamisch:Beispiel: Beim Erlernen der Muttersprache testet ein Kleinkind zunächst Laute. Bei einer positiven Reaktion (z.B. Ma-Ma) erfolgt rudimentäre Wortbildung, die mit dem Semantikverständnis von Worten zu komplexeren syntaktischen Strukturen (Sätzen) mit komplexeren semantischen Strukturen weiterentwickelt werden.

In der Informatik strebt man oft (z.B. bei einer Datenkommunikation) gleichartige semantische Ebenen an.

12

1.2 Nachrichtentechnische Definition (nach Shannon)

Information hat vielfältige Repräsentationsformen. Noch vor Entstehen der Informatik als Wissenschaft hat Claude Elwood Shannon (1916-2001) wichtige Maßzahlen zur Erfassung von Information definiert. Dabei geht er von der nachrichtentechnischen Repräsentation von Information, der „Nachricht“ aus.

Diese Repräsentation von Information hat „eigentlich“ nur syntaktische Aspekte (im Sinne der „Semiotischen Dreidimensionalität), denn es wird weder nach dem Sinn der Nachricht gefragt, noch nach deren Konzequenz.

Dieses Unterkapitel stellt diese Maßzahlen und deren Grundlagen dar. Inhalt:

1. Nachricht2. Informationsgehalt einer Nachricht3. Informationsgehalt eines Zeichens4. Mittlerer Informationsgehalt5. Informationsgehalt des Menschen

13

1.2.1 Definition: Nachricht

sei Alphabet X: Menge von Symbolen/Zeichen X = {x1, x2, ... xn} Eine Zeichenkette (ein Wort) der Länge n über X ist eine Folge von n Zeichen

aus X (ein n-Tupel über X) Beispiel: X={a,b}

Worte über X: {a,b,ab,ba,aba,abb,baa,bbb, ...}Worte der Länge n mit n=3: {aaa,aab,aba,abb,baa,bab,bba,bbb}

Die Menge aller n-Tupel über X ist das n-facheKreuzprodukt X X ... X (n mal), bezeichnet als Xn

|Xn| = | X X ... X | = |X| * |X| * ... * |X| = |X|n

Die Anzahl der Elemente alle Worte mit der exakte Länge n ist |X|n

Wird eine Zeichenkette übermittelt, so spricht man von Nachricht Nx

Sender Kanal Empfänger

Störung

Informationsübetragung(nach Shannon, Hartley,Weaver und Wiener)

14

1.2.2 Definition: Informationsgehalt einer Nachricht

Ein Maß für die Information (der Informationsgehalt) einer Nachricht Nn,x der Länge n (über ein Alphabet X) ist die kürzeste Länge der Beschreibung, die notwendig ist, um die Nachricht Nn,x aus der Menge aller möglichen Nachrichten der Länge n sicher zu ermitteln

Beispiel: Information der Nachricht N8,{0,1} : Suche in |{0,1}|8 = 256 Wörtern

Der Informationsgehalt einer aus mehreren (voneinander unabhängigen) Zeichen bestehenden Zeichenkette ist gleich der Summe der Informationen der einzelnen Zeichen: 1 * ld(|X|) + 1* ld(|X|) + ... + 1* ld(|X|) = n * ld(|X|) = ld(|X|n)

Optimal mit binärem SuchenAnzahl Fragen:ld(|Xn|) = ld(|X|n) = n ld(|X|)

obere Hälfte ?ja nein

obere Hälfte ?ja nein

obere Hälfte ?ja nein

...

15

1.2.3 Definition: Informationsgehalt eines Zeichens

Idee: Der Informationsgehalt eines Symbols xi hängt von der Wahrscheinlichkeit seines

Auftretens ab: Je seltener ein Symbol auftritt, desto höher ist sein Informationsgehalt:

h(xi) = f(1/p(xi))

Definition nach Shannon (ca. 1950):Der Informationsgehalt h (Einheit bit) eines Symbols xi ist definiert als der Logarithmus Dualis des Reziprokwertes der Wahrscheinlichkeit, mit der das Symbol auftritt:

h(xi) = ld(1/p(xi)) = -ld p(xi)

16

1.2.3 Beispiel: Informationsgehalt

Beispiel: Sei die Wahrscheinlichkeit von E = 0,5 und die von H = 0,25 Informationsgehalt des Zeichens „E“ :

hE = ld (1/0.5) = 1bit Informationsgehalt des Zeichens „H“ :

hH = ld (1/0,25) = 2 bit Informationsgehalt der Zeichenkette „EHE“

hEHE = ld(2) + ld(4) + ld(2) = ld(2 * 4 * 2) = 4 bit

log a b =log c b

log c amit a = 2, c = 10 gilt: ld b =

lg b

lg 2 3,322 lg b

Umrechnungsregel des ld in den 10er-Logarithmus (lg)

17

1.2.4 Definition: Mittlerer Informationsgehalt

Kennt man die Einzelwahrscheinlichkeiten aller möglichen Symbole einer Symbolsequenz, so ist der mittlere Informationsgehalt Hs der Symbole s (Entropie der Quelle) definiert als: Hs = (p(xi) * h(xi)) = (p(xi) * ld(1/p(xi))) = - p(xi) * ld(p(xi)))

Der mittlere Informationsgehalt Hs,n einer Symbolkette der Länge n ist: Hs,n = Hs * n

BeispielP

x 0,5y 0,25z 0,25

p hx 0,5 1y 0,25 2z 0,25 2

Hs = 0,5 * 1bit + 0,25 * 2bit + 0,25 * 2bit = 1,5 bit

d.h. die Symbole habeneinen mittleren Informa-tionsgehalt von 1,5 bit.

18

1.2.5 Informationsaufnahme des Menschen

Beim Lesen (eines deutschen Textes) erreicht der Mensch eine Geschwindigkeit von ca. 25 Zeichen/sec das entspricht 25 * 2 Bit (mittleren Informationsgehalt in der deutschen Sprache) =

50 Bit/sec dieser Wert ist unabhängig vom Alphabet - kann also auch z.B. im chinesischen

erreicht werden (weniger Zeichen/sec, größerer mittlerer Informationsgehalt). Nachrichten, die mit anderen Medien dargestellt werden, können ca. genauso

schnell verarbeitet werden. Aufnahme des Menschen

Bewusst aufgenommen werden ca. 50% von 50 Bit/sec also 25 bit/sec Bei einer Aufnahmedauer von ca. 16 Stunden am Tag ergibt sich eine

Lebensinformationsmenge von ca. 3 * 1010 Bit die Speicherkapazität des Gehirns ist mit ca. 1012 Bit auch in der Lage, diese

Informationsmenge zu speichern (sogar 100 Mal) Die Lebensinformationsmenge findet auf einer CD-ROM Platz und ist über

Glasfaserkabel in wenigen Sekunden zu übertragen.

19

1.3 Algorithmische Definition

Betrachten wir folgende Nachrichten (A und B): Nachricht A: 1110111011000110110101100010 Nachricht B: 1111000111100011110001111000nach Shannon ist der Informationsgehalt der ersten Zeichenkette A identisch mit dem der zweiten Zeichenkette B (denn hA(0)=hB(0) und hA(1)= hB(1))Aber: Ist das (intuitiv) wirklich so ?

Tatsächlich lässt sich die Information aus Nachricht B leicht (algorithmisch) beschreiben: „4 1en, dann 3 0en, das Ganze 4 mal“

Hat man also die Regelmäßigkeit der Nachricht „verstanden“ lässt sich die Information einfacher (kürzer) formulieren. Im Sinne der „Semiotischen Dreidimensionalität“ berücksichtigt die Algorithmische Definition von Information zusätzlich zur Syntax auch die Semantik.

Inhalt:1. Die Turing-Maschine2. Das Turing-Programm3. Beispiele

20

1.3.1 Einige Fragen

1. Kann jede Zeichenkette durch Regeln (einen Algorithmus) beschrieben werden.2. Wie können diese Regeln zur Generierung von Zeichenketten beschieben

werden?3. Gibt es ein Modell, mit dem man solche Regeln formalisieren kann?

Wie sieht ein solches abstraktes Model aus ? Gibt es genau ein Model oder mehrere ? Sind diese Modelle äquivalent ?

21

1.3.2 Die Turing-Maschine

Als abstraktes Modell eines Computers beschrieb Alan Turing (1912-1954) 1936 - also noch vor der Erfindung des Digitalrechners - eine nach ihm benannte abstrakte Maschine

Formal kann eine Turing-Maschine wie folgt beschrieben werden: Alphabet: A = {a0, ... , an}, der Zeichenvorrat der Turing-Maschine, wobei a0 das

Leerzeichen ("blank") darstellt (Oft: a1=0, a2=1) Bandinschrift: B: Z A eine Zuordnung, die jeder Stelle des rechtsseitig

unendlichen Bandes ein Zeichen zuordnet. Dabei wird festgesetzt, dass B(k) = a0 für alle bis auf endlich viele .

Kopfposition: k Z Zustände: eine endliche Menge von Maschinenzuständen.Q = {q0, ..., qm} Darunter

sind q0, der Anfangszustand und H Q , die Menge der Haltezustände, ausgezeichnet. Statt Haltzustände wird oft auch eine Halteaktion angegeben

Turing-Tabelle:eine Übergangsrelation: d : A Q A Q {r, l, n, h}, das jedem (gelesenen) Zeichen in Abhängigkeit eines Zustandes ein neues Zeichen, einen Folgezustand und eine Aktion (r,l,n,h} zuordnet

22

1.3.3 Das Turing-Programm

Die Aktionen: r (right): das Verschieben des Kopfes nach rechts l (left): das Verschieben des Kopfes nach links optional n (none): keine Bewegung des Kopfes optional h (halt): Impliziter Übergang in einen Endzustand

a1 a2 a3 a4 ... a6

dieMaschineim Zustand

das unter demKopf geleseneZeichen

dieAktion

der neueZustand

q q‘r oder lak

das neueZeichen

falls so ist

al

23

1.3.4 Beispiel

Das „Busy beaver“-Problem:Wie viele „1“-en kann ein terminierendes Turing-Programm auf einem leeren Band mit einer vorgegebenen Anzahl von Zuständen maximal erzeugen. In dieser Notation wird statt eines Übergangs in den Haltezustand (z.B. q5) die

Aktion „halt“ ausgeführt.

Der Rekord für |Z|=5 liegt bei 4096 „1“en (J.Buntrock, H.Marxen, 1989) Es wurde gezeigt, dass es möglich ist, mehr als 4098 „1“en zu generieren -

allerdings nicht wie.

11 Schritte, 6 Einsen 96 Schritte, 13 Einsen

24

.3.5 Information

Die algoritmische Definition definiert Informationgehalt:Der algorithmische Informationsgehalt einer Nachricht ergibt sich aus der Länge L des kürzesten Algorithmuses (z.B. Turing-Programms), welches die Nachricht erzeugt.

Daraus ergibt sich, dass der algorithmische Informationsgehalt (bis auf eine kleine Konstante) immer kleiner oder gleich dem (nachrichtentechnischen) Informationsgehalt einer Nachricht ist, denn im „einfachsten“ Fall kann die Turing-Maschine die komplette Nachricht auf dem Turingband codieren und besteht aus einem leeren Programm.

Es gibt keine Möglichkeit, für beliebige Nachrichten zu bestimmen, ob der algorithmische Informationsgehalt kleiner als der nachrichtentechnische Informationsgehalt (ob es also ein Turing-Programm gibt, welches die Nachricht „geschickter“ codiert).

25

12.4 Darstellung in der Informatik

Die Wurzeln der Informatik liegen weniger in der Nachrichtentechnik, als vielmehr in der Mathematik. Darum ist die Repräsentation von Information als Nachricht weniger relevant als die Darstellung von Zahlen (in binärer Repräsentation) und algebraischen (bool‘schen) Objekten.In diesem Unterkapitel geht es um diese Repräsentationen.

Inhalt1. Das Bit in der Informatik2. Die Darstellung des Bit3. Beispiel4. Das Byte und mehr

26

1.4.1 Das Bit in der Informatik

Definition aus der Informatik:Ein bit ist die Informationsmenge in einer Antwort, auf eine Frage, die zwei Möglichkeiten zulässt: ja /nein wahr/falsch schwarz/weiß ...

Der Informationsgehalt eines Zeichens einer zweielementigen Alphabetes mit gleicher Auftretungswahrscheinlichkeit ist(nach Shannon)

h = -ld p = -ld 0,5 = 1bit

27

1.4.2 Die Darstellung des Bit

Diese zwei Möglichkeiten werden meist mit 0 bzw. 1 codiert Die technische Darstellung erfolgt u.a. mit Hilfe von:

Ladung 0 = ungeladen 1 = geladen

Spannung 0 = 0 Volt 1 = 5 Volt

Magnetisierung 0 = nicht magnetisiert 1 = magnetisiert

Licht 0 = kein Licht 1 = Licht

Reflexionseigenschaften 0 = reflektiert 1 = reflektiert nicht

...

28

1.4.3 Das Byte und mehr

Aus bestimmten Gründen Geschwindigkeit von Lese- und Schreiboperationen Darstellungsmöglichkeit „häufiger“ Zeichen (z.B. Alphabet) Darstellungsmöglichkeiten von Zahlen, etc.

werden in der Informatik oft Vielfache von 8bit-Gruppen verwendet (8bit, 16bit, ...)Eine 8-Bitsequenz heißt ein Byte.

Diese 8bit werden manchmal nochmals unterstruktuiert in zwei 4er Gruppen, die dann „Nibble“ heißen. Nibble können geschickt als Hexadezimalziffer dargestellt werden.

Bestimmte 2er-Potenzen werden in der Informatik häufig als Maßzahlen (z.B. für Speichergrößen) verwendet: 1 KByte = 210 = 1024 Byte (1 Kilobyte) 1 MByte = 210 * 210 Byte (1 Megabyte) 1 GByte = 210 * 210 * 210 Byte (1 Gigabyte) 1 TByte = 210 * 210 * 210 * 210 Byte (1 Terrabyte)

29

1.4 Zusammenfassung des Kapitels

Was ist Information Nachrichtentechnische Definition

Informationsgehalt eines Zeichens (x) h(x) = ld (1/p(x)) = - ld

(p(x) einer Nachricht (n) h(n) = h(n1) + h(n2) + h(n3)

+ ... Mittlerer Informationsgehalt

ein/aller Zeichen(s) (x) H(x) = p(xi) * h(xi) einer Nachricht (n) n * H(x)

Algorithmische Definition Definition in der Informatik

Bits und Bytes

Achtung:Nichtverwechseln !

30

Kapitel 2 Codes

Information ist abstrakt: damit Information in einem Rechner verarbeitet werden kann, muss sie in eine für den Rechner verarbeitbare Form transformiert werden.Dabei kann man sich beliebig ungeschickt anstellen. Dieses Unterkapitel beschreibt, wie eine solche Transformation funktionieren kann, welche Möglichkeiten man dabei hat und gibt ein Maß für die Qualität einer Transformation an.

Inhalt1. Definitionen2. Codes zur Optimierung der Codelänge3. Codes zur Fehlererkennung und Fehlerkorrektur4. Beispiele

… und das Wort ward FleischJohannes 1.14

31

2.2.1 Definitionen

… ein paar Definitionen .. Inhalt

1. Definition2. Willkürliche Codes3. Fano-Bedingung4. Mittlere Wortlänge5. Redundanz

32

2.1 Definition: Code

Definition:Seien X,Y zwei Alphabete Eine Codierung ist eine Abbildung C:XnYm aller n-Tupel aus X nach m-Tupel aus Y.

oft ist n=1 oft ist X,Y = {0,1}

Die Worte aus Ym werden Code genannt. Die Umkehrrelation C-1 bezeichnet man als Dekodierung

Definition:Ein Code heißt vollständig, wenn alle Wörter aus Xn mit Hilfe der Codierung abgebildet werden können.

Definition:Für ein Wort Xi

n aus C:XinYi

m ist m die Länge l(Xin) von C(Xi

n)(Zur Erinnerung: meist in n=1, d.h. die Codierung bildet ein jeweils ein Zeichen xi auf mehre Zeichen xi

m ab) Definition:

Ein Code heißt Code gleicher Länge, wenn die Anzahl der Symbole auf die ein Wort abgebildet wird, für alle Worte gleich ist(also: l(Xn)=m konstant für alle XnYm).Ansonsten heißt der Code: Code unterschiedlicher Länge

33

2.1.2 Definition: Eindeutigkeit

Definition:Ein Code heißt eindeutig, wenn C-1 injektiv ist, ansonsten heißt er mehrdeutig

Codes sollten also (meist) so beschaffen sein, dass sie bei der Decodierung eindeutig sind.

Gegenbeispiel:

Problem Dekodierung: 10111100100 = 101 11100 100 (aui)

101 11 100 100 (aoii)

z p h h * p c l l * p

A 0,2 2,32 0,46 101 3 0,60

E 0,3 1,74 0,52 01 2 0,60

I 0,2 2,32 0,46 100 3 0,60

O 0,25 2,00 0,50 11 2 0,50

U 0,05 4,32 0,22 11100 5 0,25

R=L-H=0,38 H = 2,17 L = 2,55

34

2.1.3 Definition: Fano-Bedingung

Fano-Bedingung:Kein Codewort darf Anfang eines anderen Codewortes sein

Beispiel:

Die Fano-Bedingung ist hinreichend aber nicht notwendig hinreichend: Wenn die Fano-Bedingung erfüllt ist, ist der Code eindeutig nicht notwendig: Auch eine Codierung, die die Fano-Bedingung nicht erfüllt kann eindeutig

sein.Beispiel: a 1, b 10

Anmerkung: Eine Betrachtung der Fano-Bedingung macht „eigentlich“ nur Sinn bei Codes unterschiedlicher Länge (warum ?)

z c

A 101

E 01

I 100

O 11

U 11100

z c

A 00

E 10

I 010

O 11

U 011

35

2.1.4 Definition: Mittlere Wortlänge

Codiert man die Zeichen eines Alphabetes binär (also mit Sequenzen eines 2-Zeichen-Alphabetes, z.B. 0 und 1) , so versteht man unter der mittleren Wortlänge L eines Codes die mit den Auftrittswahrscheinlichkeiten gewichtete Summe der Längen l(xi) der den einzelnen Symbole entsprechenden Codewörtern

L = p(xi) * l(xi) Beispiel

011100011yxxzyx

Code l p h p*h p*lx 1 1 0,5 1 0,5 0,5y 01 2 0.25 2 0,5 0,5z 00 2 0,25 2 0,5 0,5

H = 1,5 BitL = 1,5 Bit

36

2.1.5 Definition: Redundanz

Die mittlere Wortlänge eines Binärcodes ist immer größer oder gleich dem mittleren Informationsgehalt.

Die Differenz zwischen mittlerer Wortlänge und mittlerem Informationsgehalt wird als Redundanz R des Codes bezeichnet:

R = L - H Die Redundanz bezogen auf die Wortlänge nennt man relative Redundanz r:

r = R / L Redundanz ist also ein Maß für die Qualität einer Kodierung (insofern die

Länge eines Codes als Qualität angesehen wird)

37

2.1.6 Redundanz – Beispiel

Beispiel

Code l p h p*h p*l p h p*h p*lx 1 1 0,5 1 0,5 0,5 0,7 0,515 0,360 0,7y 01 2 0.25 2 0,5 0,5 0.2 2,322 0,464 0,4z 00 2 0,25 2 0,5 0,5 0,1 3,322 0,332 0,2

H1,5 Bit

L1,5 Bit

H1,16 Bit

L1,3 Bit

H = pi * hi = - pi * ld(pi) = 0,360+0,464+0,332 = 1,156

L = pi * li = 0,7+0,4+0,2 = 1,3

R = L - H = 1,3 - 1,156 = 0,144

r = R / L = 0,144 / 1,3 = 0,111

38

2.1.7 Codierungsarten

Die Entropiekodierung kodiert ungeachtet der zugrundliegenden Information und betrachtet die zu

komprimierten Daten als “reine” Bitsequenz (also nur die Syntax). es werden nur (informationstheoretische) Redundanzen eliminiert, es geht keine

Information verloren. unterschiedliche Kompressionsquoten bei unterschiedlichen zu komprimierenden

Daten. Die Quellenkodierung

ist abhängig von den zu kodierenden Informationen (daher: Quellcodierung). und verwendet dazu die Semantik der zu kodierenden Information.

eliminiert für das “Ziel” (z.B. den Menschen) definierte Redundanzen und ist (meist) verlustbehaftet.

Spezifika der Informationen können dadurch gut genutzt werden und man erreicht eine wesentlich bessere Kompressionsraten bei "akzeptabler" Qualität.

39

2.2 Huffman-Codierung

Oft ist es wichtig, einen Code möglichst kurz zu gestalten aus Gründen der Speicherplatzoptimierung aus Gründen der Übertragungskapazitäts-Optimierung …

Idee Häufige Symbole – kurze Codes, Seltene Symbole – lange Codes

Kodierung Die Häufigkeit des Auftretens der Zeichen (oder Zeichenketten) wird bestimmt Die am häufigsten auftretenden Zeichen (oder Zeichenketten) werden mit kurzen

Bitfolgen (Huffmann-Code) kodiert Der Huffmann-Code wird zur Kodierung der Bitfolge verwendet

Dekodierung Dekodierer besitzt identischen Huffmann-Code (oder bekommt die

Zuordnungstabelle explizit übertragen) Dekodierer setzt den Huffmann-Code in Bytefolge um

Die Huffmann-Codierung generiert einen vollständigen, eindeutigen Code unterschiedlicher Länge (der die Fano-Bedingung erfüllt)

40

2.2.1 Vorgehen

Der Baum wird von oben nach unten mit den zwei Buchstaben (oder Buchstabengruppen) mit den jeweils kleinsten Wahrscheinlichkeiten schrittweise aufgebaut

seiP(A) = 0,16P(B) = 0,51P(C) = 0,09P(D) = 0,13P(E) = 0,11

P(B)=0,51

P(B C E A D)=1,0

1 0

P(C E A D)=0,49

1 0

P(D)=0,13 P(A)=0,16

P(A D)=0,29

1 0

P(C)=0,09 P(E)=0,11

P(CE)=0,2

1 0KodierungA = 000B = 1C = 011D = 001E = 010

41

2.2.2 Verbesserung

Codierung ist optimal, wenn sich die Wahrscheinlichkeiten der Zeichen „geschickt“ ergeben „geschickt“ sind Wahrscheinlichkeiten mit negativen 2er-Potenzen.

Durch Betrachtung (und Codierung) von Zeichenpaaren, -drillingen, ... , n-Tupeln können solche „geschickten“ Wahrscheinlichkeiten gefunden werden Die Redundanzen lassen sich sogar beliebig verkleinern, weil die

Einzelwahrscheinlichkeiten von n-Tupeln beliebig klein werden und dadurch immer „geschickter“ kombiniert werden können.

Beispiel:z p

A 0,80

B 0,20

z p

AA 0,64

AB 0,16

BA 0,16

BB 0,04

Produkt der Einzelwahrscheinlichkeiten(Annahme: Auftritt von A,B unabhängig)

z p

AAA 0,512

AAB 0,128

ABA 0,128

... ...

BBB 0,008

...

42

2.2.3 Beispiel für Tupelbildung

Beispiel

z p h h * p c l l * p

A 0,80 0,32 0,26 0 1 0,80

B 0,20 2,32 0,46 1 1 0,20

R = 0,26 H = 0,72 L = 1,00

z p h h * p c l l * p

AA 0,64 0,64 0,41 0 1 0,64

AB 0,16 2,64 0,42 10 2 0,32

BA 0,16 2,64 0,42 110 3 0,48

BB 0,04 4,64 0,19 111 3 0,12

R = 0,12 H = 1,44 L = 1,56

43

2.3.3 Hamming-Codierung

Manchmal ist es wichtig, Fehler in einem Code zu erkennen und ggf. zu korrigieren. (z.B. bei der Übertragung)

Idee Gezielter Einsatz von Redundanz Nicht alle möglichen Codeworte sind daher gültig

Kodierung Dem Code werden zusätzliche Bits hinzugefügt. Die Werte der zusätzlichen Bits stehen in Bezug zu den ursprünglichen Bits

Beispiel aus der natürlichen Sprache “Ich studiere in Gießer” – Fehler kann erkannt und behoben werden “Ich liebe rich” – Fehler kann erkannt, aber nicht behoben werden

44

2.3.1 Beispiel ASCII

Paritätsbit bei der 7-bit ASCII-Codierung wähle das 8te Bit so, dass immer eine gerade Anzahl von Bits gesetzt ist (gerade

Anzahl = „even parity“, ungerade Anzahl = „odd parity“)

erhält man eine Nachricht mit ungerader Anzahl, so weiß man, dass (mindestens) ein Bit verkehrt ist. man weiß allerdings nicht welches man weiß auch nicht, ob nicht mehr als ein Bit verkehrt ist man weiß bei richtigem parity-Bit auch nicht, ob nicht mehr als 1 Bit verkehrt ist

Idee: den „Abstand“ gültiger Worte so groß wie nötig wählen

Zeichen Binär mit even Parity@ 100 0000 1100 0000 := 1 + 1 = 2A 100 0001 0100 0001 := 1 + 1 + 0 = 2B 100 0010 0100 0010 := 1 + 1 + 0 = 2C 100 0011 1100 0011 := 1 + 1 + 1 + 1 = 4

45

2.3.2 Hamming-Distanz

Definition:Der Hamming-Abstand (die Hamming-Distanz D) zwischen zwei Wörtern ist die Anzahl der Stellen, an denen sich zwei Worte gleicher Länge unterscheiden. Beispiel: Hamming-Abstand von 1100 0000 (A) und 0100 0001 (B) = 2

Definition:Der Hamming-Abstand (die Hamming-Distanz D) eines Codes ist der minimale Hamming-Abstand zwischen zwei beliebigen Wörtern des Codes. Beispiel: Hamming-Abstand von ASCII (mit even parity) = 2

Einige Konsequenzen: Codes mit Hamming-Distanz = 0 sind nicht eindeutig Bei Codes mit Hamming-Distanz = 1 kann das „Kippen“ eines Bits zu einem

anderen gültigen Codewort führen (muss nicht) Bei Codes mit Hamming-Distanz = 2 kann ein Ein-Bit Fehler erkannt werden.

46

2.3.3 Fehlererkennung

Fehler, bei denen höchstens D-1 Bits gestört sind, können sicher erkannt werden einige andere Fehler können, müssen aber nicht unbedingt erkannt werden können.

(genau dann, wenn die Hamming-Distanz zwischen zwei Wörtern eines Codes größer als die Distanz des Codes ist)

Fehler werden erkannt, wenn ein Codewort ungültig ist

1-Bit-Fehler

2-Bit-Fehler

gültiges Codewort

„nur“ erkennbares Codewort

korrigierbares CodewortA B

47

2.3.4 Fehlerkorrektur

Fehler, bei denen höchsten (D-1)/2 Bits gestört sind, können sicher korrigiert werden einige andere Fehler können, müssen aber nicht korrigiert werden können

(genau dann, wenn die Hamming-Distanz zwischen zwei Wörtern eines Codes größer als die Distanz des Codes ist)

Falsches Codewort wird dem „nächstmöglichen“ Codewort (d.h. dem mit der minimalen Distanz) zugeordnet.

gültiges Codewort

1-Bit-Fehler

2-Bit-Fehler

korrigierbares CodewortA B

48

2.3.5 Hamming

Idee Jedes Prüfbit stellt die gerade Parität einer gewissen Menge von Bits (einschließlich

sich selbst) sicher Jedes Datenbit kann in mehreren dieser Mengen einbezogen sein

Die Hamming-Methode Es werden an der 1,2,4,8,... Stelle Prüfbits eingeführt Jedes Prüfbit hat damit in seiner dualen Stellennummer genau eine Stelle mit einer

1 (1,2,4,8,... = 1,10,100,1000,...) Alle Stellen im Wort, die an derselben Stelle eine 1 haben (und an den anderen 1

oder 0) werden aufsummiert 1 001,011,101,111, ... also 1,3,5,7, ... Stellen 10 010,011,110,111, ... also 2,3,6,7, ... Stellen 100 100,101,110,111, ... also 4,5,6,7, ... Stellen

Das entsprechende Parity-Bit wird als even-parity Bit gesetzt Die Hamming-Methode generiert einen eindeutigen, vollständigen Code

gleicher Länge

P D D D P D P P...18

49

2.3.6 Beispiel Hamming

zu kodieren: 1011 Prüfbit 1 (001)

relevant 011,101,111also Bit 3,5,7Summe = 3 Bit setzen

Prüfbit 2 (010)relevant 011,110,111also Bit 3,6,7Summe = 2 Bit löschen

Prüfbit 4 (100)relevant 101,110,111also Bit 5,6,7Summe = 2 Bit löschen

kodiert: 1010101

1 0 1 P 1 P 1

1 0 1 P 1 P P17

1 0 1 P 1 0 1

1 0 1 0 1 0 1

50

2.3.7 Beispiel Hamming

Fehlerhafter Code: 1000101 Verfahren

prüfe alle Parity-Bits k = Summe der fehlerhaften

Bitnummern k gibt die Nummer des gestörten Bits

an (nur bei 1-Bit Fehler zuverlässig) Hier:

Bit1 prüft 3,5,7: falsch Bit2 prüft 3,6,7: ok Bit4 prüft 5,6,7: falsch k = 1 + 4 = 5 Bit5 muss getauscht werden

01 0 0 1 0 117

1 0 1 0 1 0 1

51

2.4 Beispiele

Anhand zweier Beispiele soll gezeigt werden, wie: die Natur, Gott (oder das fliegende Spaghetti-Monster) der Mensch

Information codiert

Inhalt1. Genetische Codierung2. Bildcodierung

52

2.4.1 Genetische Codierung

Beim Menschen ist die Desoxyribonukleinsäure (DNS, engl. DNA) der Träger der genetischen Information und Hauptbestandteil der Chromosomen. Die DNS ist ein kettenförmiges Polymer aus Nukleotiden, die sich in ihren

Stickstoffbasen unterscheiden (Thymin/Cytosin bzw. Adenin/Guanin,) das Alphabet des Codes ist also:

{Thymin, Cytosin, Adenin, Guanin,} oder auch { T, C, A, G } Je drei aufeinanderfolgende Basen bilden ein Wort

Es gibt also pro Wort 43 = 64 Kombination die Wortlänge ist also ld(64) bit = 6 bit

Ein Gen enthält etwa 200 Worte Ein Chromosom enthält ca. 104 bis 105 Gene Die Anzahl der Chromosomen pro Zellkern ist beim Menschen 46 Die pro Zellkern gespeicherten Daten haben damit ein Volumen von

6 bit * 200 * 105 * 46 = 55200 bit * 105 5 * 109 bit * 109 Byte = 1 GByte

53

2.2.3 Bildcodierung

Datenkompression bei der Bildcodierung (z.B. JPEG, MPEG, …) durchläuft typischerweise vier Schritte:

1. Datenaufbereitung erzeugt eine geeignete digitale Darstellung der Information Bsp.: Zerlegung eines Bildes in Pixelblöcke

2. Datenverarbeitung erster Schritt der Kompression, z.B. Transformation aus dem Zeitbereich in den

Frequenzbereich (z.B. durch Discrete Cosinus Transformation – DCT)

3. Quantisierung Gewichtung der Amplituden und Zuordnung zu Quantisierungsstufen (nicht

notwendigerweise linear)

4. Entropiekodierung verlustfreie Kompression (z.B. durch Huffmann-Codierung)

16)12(cos

16)12(cos

7

0

7

041

vu vyuxsccs

x y

yxvu

0 vu,für

21, vu cc

1,sonst bzw. vu cc

16)12(cos

16)12(cos

7

0

7

041

xy vyuxsccs

x y

vuvu

54

Definitionen Codierung, Code, Vollständigkeit, Länge Eindeutigkeit Fano-Bedingung mittlere Wortlänge L = p(xi) * l(xi) Redundanz R = L - H Codierungsarten

Huffmann-Codierung Vorgehen Verbesserungen

Hamming-Codierung Beispiel ASCII Hamming-Distanz Fehlererkennung / -korrektur Hamming-Codierverfahren Beispiele

Beispiele Genetische Codierung Bildcodierung

2.6 Zusammenfassung des Kapitels

55

Kapitel 3 Zeichen und Zahlen

Auch wenn Objekte der realen Welt beliebig komplex in Zusammensetzung und Struktur sind, so werden sie meist auf zwei einfache Repräsentationen - als Abstraktion - abgebildet:Zeichen und Zahlen. Dieses Kapitel beschreibt, wie diese Objekte in eine für den Rechner verarbeitbare Form kodiert werden können.

Inhalt1. Kodierung von Zeichen2. Darstellung von Zahlen

… da schrieb er auf die Tafeln, wie die erste Schrift war5. Mose 10.4

56

3.1 Kodierung von Zeichen

Die Wurzeln der Informationscodierung in der Menschheitsgeschichte liegt in der Entwicklung der Schrift. Menschen haben dabei versucht, mündliche Erzählung in Form von Bild-, Silben- oder Buchstabenschriften dauerhaft zu „codieren“. Dabei kommt der Buchstabenschrift im westlichen Kulturbereich eine besondere Bedeutung zu und wird durch Schriftzeichen aus aller Welt zunehmend ergänzt. Diese Entwicklung spiegelt sich auch in folgenden Unterkapiteln wider.

Inhalt ASCII EBCDIC UNICODE

57

3.1.1 ASCII -Tabelle (7Bit)

American Standard Code for Information Interchange

@ NUL 000A SOH 001B STX 002C ETX 003D EOT 004E ENQ 005F ACK 006G BEL 007H BS 008I HT 009J LF 010K VT 011L FF 012M CR 013N SO 014O SI 015P DLE 016Q DC1 017R DC2 018S DC3 019

T DC4 020U NAK 021V SYN 022W ETB 023X CAN 024Y EM 025Z SUB 026[ ESC 027\ FS 028] GS 029^ RS 030_ US 031SP 032! 033" 034# 035$ 036% 037& 038' 039

( 040) 041* 042+ 043, 044- 045. 046/ 0470 0481 0492 0503 0514 0525 0536 0547 0558 0569 057: 058; 059

< 060= 061> 062? 063@ 064A 065B 066C 067D 068E 069F 070G 071H 072I 073J 074K 075L 076M 077N 078O 079

P 080Q 081R 082S 083T 084U 085V 086W 087X 088Y 089Z 090[ 091\ 092] 093^ 094_ 095` 096a 097b 098c 099

d 100e 101f 102g 103h 104i 105j 106k 107l 108m 109n 110o 111p 112q 113r 114s 115t 116u 117v 118w 119

x 120y 121z 122{ 123_| 124} 125~ 126DEL 127

58

3.1.1 ASCII - Sonderzeichen

Bedeutung der Sonderzeichen im ASCII-Code

@ NUL Null, or all zeros A SOH StartHeading B STX StartText C ETX EndText D EOT EndTransmission E ENQ Enquiry F ACK Acknowledge G BEL Bell H BS Backspace I HT HorizontalTab J LF LineFeed K VT VerticalTab L FF FormFeed M CR CarriageReturn N SO ShiftOut O SI ShiftIn P DLE DataLinkEscape Q DC1 DeviceControl1(XON)

R DC2 DeviceControl2 S DC3 DeviceControl3(XOFF) T DC4 DeviceControl4 U NAK Neg.Acknowledge V SYM SynchronousIdle W ETB EndTrans.Block X CAN Cancel Y EM EndofMedium Z SUB Substitute [ ESC Escape \ FS FileSeparator ] GS GroupSeparator ^ RS RecordSeparator _ US UnitSeparator

SP Space

? DEL Delete

59

3.1.2 EBCDIC - Tabelle

Extended Binary Coded Decimals Interchange Code

nul 00soh 001stx 002etx 003pf 004ht 005lc 006del 007ge 008rlf 009smm 00avt 00bff 00ccr 00dso 00esi 00fdle 010dc1 011dc2 012tm 013res 014nl 015bs 016il 017can 018em 019

cc 01acu1 01bifs 01cigs 01dirs 01eius 01fds 020sos 021fs 022

023byp 024lf 025etb 026esc 027

028029

sm 02acu2 02b

02cenq 02dack 2ebel 2f

030031

syn 032033

pn 034rs 035uc 036eot 037

03803903a

cu3 03bdc4 03cnak 03d

03esub 03fSp 040

041042043044045046047048049

¢ 04a. 04b> 04c( 04d

+ 04e| 04f& 050

051052053054055056057058059

! 05a$ 05b* 05c) 5d; 5e

5f- 060/ 061

062063064065066067

068069

| 06a, 06b

% 06c06d

< 06e? 06f

070071072073074075076077078

` 079: 07a# 07b@ 07c' 07d= 07e" 07f

080a 081

b 082c 083d 084e 085f 086g 087h 088i 089

08a08b08c08d08e08f090

j 091k 092l 093

m 094n 095o 096p 097q 098r 099

09a09b

09c09d09e09f0a0

~ 0a1s 0a2t 0a3u 0a4v 0a5w 0a6x 0a7y 0a8z 0a9

0aa0ab0ac0ad0ae0af0b00b10b20b30b40b5

0b60b70b80b90ba0bb0bc0bd0be0bf

{ 0c0A 0c1B 0c2C 0c3D 0c4E 0c5F 0c6G 0c7H 0c8I 0c9

0ca0cb0cc0cd0ce0cf

} 0d0J 0d1K 0d2L 0d3M 0d4N 0d5O 0d6P 0d7Q 0d8R 0d9

0da0db0dc0dd0de0df

\ 0e00e1

S 0e2T 0e3U 0e4V 0e5W 0e6X 0e7Y 0e8Z 0e9

0ea0eb0ec0ed0ee0eF

0 0f01 0f12 0f23 0f34 0f45 0f56 0f67 0f78 0f89 0f9| 0fa

0fb0fc0fd0fe

eo 0ff

60

3.1.2 EBCDIC - Sonderzeichen

Die Bedeutung der Sonderzeichen

Char Description Char Description Char Description

ACK Acknowledge EOT End of Transmission PN Punch On

BEL Bell ESC Escape RES Restore

BS Backspace ETB End of Transmission Block RS Reader Stop

BYP Bypass ETX End of Text SI Shift in

CAN Cancel FF Form Feed SM Set Mode

CC Cursor Control FS Field Separator SMM Start of Manual Message

CR Carriage Return HT Horizontal Tab SO Shift Out

CU1 Customer Use 1 IFS Interchange File Separator SOH Start of Heading

CU2 Customer Use 2 IGS Interchange Group Separator SOS Start of Significance

CU3 Customer Use 3 IL Idle SP Space

DC1 Device Control 1 IRS Interchange Record Separator STX Start of Text

DC2 Device Control 2 IUS Interchange Unit Separator SUB Substitute

DC4 Device Control 4 LC Lower Case SYN Synchronous Idle

DEL Delete LF Line Feed TM Tape Mark

DLE Data Link Escape NAK Negative Acknowledge UC Upper Case

DS Digit Select NL New Line VT Vertical Tab

EM End of Medium NUL Null

ENQ Enquiry PF Punch Off

61

3.1.3 Unicode

Aktuelle Version 5.2 (siehe auch www.unicode.org) Buchstaben und Symbole aus allen wichtigen geschriebenen Sprachen

der Welt Amerika, Europa, Mittlerer Osten, Afrika, Indien, Asien, Pazifik Symbole Satzzeichen Sonderzeichen

Wird genormt in ISO/IEC 10646 Kompatibilität mit ASCII

0000 - 007F: identisch mit 7-bit ASCII 007F - 00FF: Latin-1 Supplement (nationale Sonderbuchstaben) 2500 - 25FF: Blockgraphikzeichen (Box Drawing: ╘╚╞╬└┴├...)

62

3.1.3 Unicode (www.wikipedia.org, Dez-3-06)

Unicode reserves 1,114,112 (= 220 + 216 or 17 × 216, hexadecimal 110000) code points. As of Unicode 5.0.0, 101,063 (9.1%) of these codepoints are assigned, with another 137,468 (12.3%)

reserved for private use, leaving 875,441 (78.6%) unassigned. The number of assigned code points is made up as follows: 98,884 graphemes 140 formatting characters 65 control characters 2,048 surrogate characters

The first 256 codes correspond with those of ISO 8859-1, the most popular 8-bit character encoding in the Western world. As a result, the first 128 characters are also identical to ASCII.

The Unicode code space for characters is divided into 17 planes, each with 65,536 (= 216) code points, although currently only a few planes are used: Plane 0 (0000–FFFF): Basic Multilingual Plane (BMP) Plane 1 (10000–1FFFF): Supplementary Multilingual Plane (SMP) Plane 2 (20000–2FFFF): Supplementary Ideographic Plane (SIP) Planes 3 to 13 (30000–DFFFF) unassigned Plane 14 (E0000–EFFFF): Supplementary Special-purpose Plane (SSP) Plane 15 (F0000–FFFFF) Private Use Area (PUA) Plane 16 (100000–10FFFF) Private Use Area (PUA)

The cap of 220 code points (excluding Plane 16) exists in order to maintain compatibility with the UTF-16 encoding, which addresses only that range. Currently, about ten percent of the Unicode code space is used. Furthermore, ranges of characters have been tentatively blocked out for every known unencoded script, and while Unicode may need another plane for ideographic characters, there are ten planes available if previously unknown scripts with tens of thousands of characters are discovered. This 20 bit limit is unlikely to be reached in the near future.

63

3.1.3 Unicode: Beispiele

05F1

FA0E

2603

20AC

xxD0 - xxDF

Rejected 22.5.2001

64

3.1.3 Unicode Bereiche

Black = Latin scripts and symbols Light Blue  = Linguistic scripts Blue  = Other European scripts Orange  = Middle Eastern and SW Asian scripts Light Orange  = African scripts Green  = South Asian scripts Purple  = Southeast Asian scripts Red  = East Asian scripts Light Red  = Unified CJK Han Yellow  = Aboriginal scripts Magenta  = Symbols Dark Grey  = Diacritics Light Grey  = UTF-16 surrogates and private use Cyan  = Miscellaneous characters White  = Unused

65

3.2 Darstellung von Zahlen

Die Darstellung von Zahlen spielt in der Informatik nach wie vor eine wichtige Rolle. Dabei gibt es unterschiedliche Mengen von Zahlen und auch unterschiedliche Operationen auf Zahlen.Dieses Unterkapitel beschreibt die Grundlagen der Zahlenkodierung, gibt für alle Mengen von Zahlen eine konkrete Kodierung an und führt in die Computerarithmetik ein.

Inhalt1. Zahlensysteme2. Konvertierung3. Arithmetik4. Ganze positive Zahlen5. Ganze negative Zahlen6. Gebrochene Zahlen7. Gleitpunktzahlen8. Standards

66

3.2.1 Zahlensysteme

Nicht systematische Zahlendarstellungen, z.B.: Strichliste: I, II, III, IIII, IIII, IIII I, ... römische Zahlen: MIM, IX, ....

Systematische Zahlendarstellungen in einem Stellenwertsystem Jede Zahl N lässt sich als Sequenz von Zeichen a i darstellen Die Anzahl der notwendigen unterscheidbaren Zeichen ist B a i * B i

Im Dezimalsystem ist B = 10 und die unterscheidbaren Zeichen sind: 0,1,2,3,4,5,6,7,8,9

Im Binärsystem ist B = 2 und die unterscheidbaren Zeichen sind: 0,1

67

3.2.1 Zahlensysteme - Beispiele

Dezimalsystem: (Basis 10) 199910 = 1*103 + 9*102 + 9*101 + 9*100

Binärsystem: (Basis 2) 199910 = 1*210+1*29+1*28+1*27+1*26+1*23+1*22+1*21+1*20

111110011112

Hexadezimalsystem (Sedezimalsystem) (Basis 16) Zeichen: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F 199910 = 7*162 + 12*161 + 15*160 = 7CF16 = 0x07CF = H‘07CF 4 Zeichen einer Binärzahl lassen sich durch eine Hexadezimalziffer darstellen (4

Binärziffern nennt man auch NIBBLE) Oktalsystem (Basis 8)

Zeichen: 0,1,2,3,4,5,6,7 199910 = 3*83 + 7*82 + 1*81 + 7*80 = 37178 3 Zeichen einer Binärzahl lassen sich durch eine Oktalziffer darstellen

68

3.2.2 Konvertierung: „Intuitivmethode“

Addition von geeigneten Zweierpotenzen (Dezimalzahl Dualzahl) positive Zweierpotenzen für Vorkommaanteil negative Zweierpotenzen für Nachkommaanteil

Vorgehen (getrennt nach Vor- und Nachkommateil) Suche größte Zweierpotenz, die noch in die Zahl passt Subtrahiere die Zweipotenz von der Zahl

daraus ergibt sich die neue Zahl für die Suche der Zweierpotenz Dieses Vorgehen terminiert ...

... beim Vorkommateil: wenn die Zahl = 0 ... beim Nachkommateil: wenn die Zahl erreicht ist, vielleicht nie

Beispiel:

39 25 39 - 32 = 77 22 7 - 4 = 33 21 3 - 2 = 11 20 1 - 1 = 0

100111

0,8125 2-1 0,8125 - 0,5 = 0,31250,3125 2-2 0,3125 - 0,25 = 0,06250,0625 2-4 0,0625 - 0,0625 = 0

0,1101

39,0812510=100111,011012

69

3.2.2 Konvertierung: Restwertmethode

Erzeugen des Hornerschemas (Ausklammern der Basis b)c0 = anbn + an-1bn-1 + ... + a2b2 +a1b1 + a0b0 c0 = (( ... (anb + an-1) b + ... + a2) b +a1) b + a0

c0 / b = c1 Rest a0 , mit c1= ( ... (anb + an-1) b + ... + a2) b +a1 ,c1 / b = c2 Rest a1 , mit c2= ... (anb + an-1) b + ... + a2 ,...cn / b = 0 Rest an ( terminiert mit cn+1 = 0 )

Konversion der Nachkommastellen (folgt aus Hornerschema):1. Multiplikation mit Basis (bis ganzzahliges Ergebnis oder gewünschte Genauigkeit)

2. Abspalten der Vorkommastelle des Ergebnisses, weiter mit 1. Beispiel

19 : 2 = 9 Rest 19 : 2 = 4 Rest 14 : 2 = 2 Rest 02 : 2 = 1 Rest 01 : 2 = 0 Rest 1

0,6875 * 2 = 1,375 1 abspalten0,375 * 2 = 0,75 0 abspalten0,75 * 2 = 1,5 1 abspalten

0,5 * 2 = 1 1 abspalten

100110,1011

c1

70

3.2.2 Arithmetik

Addition

Subtraktion

Multiplikation

Division

0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 0 Übertrag 1

0 - 0 = 00 - 1 = 1 Übertrag 11 - 0 = 11 - 1 = 0

0 * 0 = 00 * 1 = 0 1 * 0 = 01 * 1 = 1

1011+ 1110 1 1 1 Überträge

11001

1101- 1010 1 Überträge

0011

1101 * 11 1101+ 1101 1 1 Überträge

100111100111 : 11 = 01101100-110011 -11 0011 -11 00

71

3.2.3 Ganze positive Zahlen

Positive ganze Zahlen werden meist direkt in ihrer binären Darstellung kodiert. Die BCD (Binary Coded Digits) - Darstellung von Zahlen ist eine Mischform aus

Dezimal- und Binärdarstellung: Jede Ziffer der Dezimalzahl wird binär dargestellt. Die Darstellung jeder Ziffer erfolgt mit 4 Bits. Die Reihenfolge der Ziffern bleibt erhalten. Beispiele:

7 0111 53 0101 0011 1234 0001 0010 0011 0100 1999 0001 1001 1001 1001

0 00001 00012 00103 00114 01005 01016 01107 01118 10009 1001

101010111100110111101111

Pseudotetraden

72

3.2.4 Ganze negative Zahlen: Probleme

Darstellung des Vorzeichens im ersten Bit, z.B.0000 = 0 1000 = 00001 = 1 1001 = -10010 = 2 1010 = -20011 = 3 1011 = -30100 = 4 1100 = -40101 = 5 1101 = -50110 = 6 1110 = -60111 = 7 1111 = -7

Nachteil durch Redundanz der Darstellung der 0 Nachteil durch Probleme beim formalen Addieren

1011 -3+ 0001 +1 1100 -4

73

3.2.4 Ganze negative Zahlen: Zweierkomplement

Zweierkomplementdarstellung -2n ... +(2n-1) Negative Zahl durch bitweise Komplementierung und Addition von 1

(eventl. Überlauf weglassen) 0000 = 0 Beispiel: 3

0001 = 1 1001 = -7 0011 Binärdarstellung0010 = 2 1010 = -6 1100 Komplement0011 = 3 1011 = -5 1101 Komplement + 1 = -30100 = 4 1100 = -40101 = 5 1101 = -30110 = 6 1110 = -20111 = 7 1111 = -1

Vorteile Darstellung des Vorzeichens im ersten Bit Abdeckung von 16 Zahlen, also keine Redundanz Kein Nachteil durch Probleme beim formalen Addieren

Subtraktion durch Addition des Zweierkomplements-3 1101 -1 1111+1 +0001 -1 +1111-2 1110 -2 11110 1110

1. Auf gleiche Länge bringen2. Bitweise Komplementbildung3. 1 Addieren4. Addieren (wie bei Binärzahlen)5. Überlauf ggf. weglassen

74

3.2.5 Gebrochene Zahlen: Binärdarstellung

Darstellung mit Vor- und Nachkommateil Beispiele Gebrochene Binärzahl Gebrochene Dezimalzahl 0.1 0,5 0.01 0,25 111.111 7,875 0.0001 1001 1001 1001 .... 0,1

Mit 32 Bit lassen sich nur 232 verschiedene Zahlen darstellen. Problem: extrem große und extrem kleine Zahlen lassen sich mit wenigen Bits

nicht darstellen Bei 8 Bit mit 4 Vorkomma und 4 Nachkommastellen (ohne Vorzeichen):

0000.0001 < n < 1111.11110,0675 < n < 15,9425

75

3.2.5 Gebrochene Zahlen: Exponentialdarstellung

Anforderung sehr große und sehr kleine Zahlen sollen darstellbar sein

Masse Elektron = 9 * 10-28 g Anzahl Moleküle pro Mol = 6,022 * 1023

die relativen Genauigkeiten sind wichtiger als die absoluten Ältere Quellen geben die Anzahl der Moleküle pro Mol mit 6,065 * 1023 an Eine Änderung in der Mantisse von 0,04 entspricht einer Toleranz von

6,065 / 6,022 1,0071 also ca. 0,7%. Fixkommadarstellung wäre große Verschwendung

zur Darstellung dieser beiden Größen wären 194 Bit nötig 87 Bit Vorkommateil 107 Bit Nachkommateil

Idee: Signifikante Stellen und Größenordnung werden getrennt Signifikant Masse Elektron: 9 Größenordnung Masse Elektron: 10-28

76

3.2.5 Gleitpunktzahlen: Real Darstellung

Darstellung durch Real-Zahlen, bestehend aus drei Teilen: Vorzeichenbit V

Gibt an, ob die Zahl positiv oder negativ ist Mantisse M

Wird mit dem Exponenten multipliziert Die Normalform wird erreicht, indem das Komma soweit nach links oder rechts

geschoben wird, bis die erste Stelle nach dem Dezimalpunkt die erste von Null verschieden Ziffer ist.Der Exponent wird entsprechend der Verschiebungen erhöht oder vermindert.

Exponent EPotenz einer Basiszahl (2) mit der die Mantisse multipliziert wird wird oft in „BIAS“-Darstellung abgelegt, d.h. wird mit 126 addiert um negatives

Vorzeichen zu vermeiden. Vorsicht: 126 (nicht 128).

Asymmetrisch, da 21 bei der Normalisierung zweimal geschoben wird, 2-1 gar nicht

Vorsicht: Bei manchen Maschinen wird so normalisiert, dass die erste Stelle vor dem Komma gleich 1 wird, dann ist der BIAS 127

77

3.2.5 Gleitpunktzahlen: Umwandlung

Umwandlung Dezimalzahl in binäre Gleitpunktzahl (nach IEEE 754) Umwandlung der Dezimalzahl in Binärzahl mit Nachkommateil Verschieben des Kommas nach links oder rechts bis zur Normalform

Damit ist erste Nachkommastelle = 1 und daher redundant, kann also in der Mantisse weggelassen werden. 2 * größere Genauigkeit der Mantisse

Erhöhen oder Erniedrigen des Exponenten Umwandlung des Exponenten in binäre Form Addition des BIAS =12610 (um negative Exponenten zu vermeiden)

auf den Exponenten Das Vorzeichen der Mantisse wird bestimmt: positiv 0, negativ 1 IEEE 754 sieht noch eine optionale Rundung der Mantisse vor

Nicht jede gebrochene Dezimalzahl lässt sich endlich als gebrochene Binärzahl darstellen (und umgekehrt). Dadurch entstehen Rundungsfehler

78

3.2.5 Gleitpunktzahlen: Beispiele

Beispiel: 148,625101. Konvertieren: 10010100,1012. Normalisieren: 10010100,101 = 0,10010100101*2+8 Exponent ist 8.

M = 0010100101 (die führende 1 ist in Normalform redundant)

3. Bias addieren E = 12610 + 810 = 13410 = 100001102

4. Vorzeichen V = 05. Ergebnis: VEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMM

01000011000101001010000000000000 Beispiel: -2,7510

1. Konvertieren: -10,112. Normalisieren: -10,11 = -0,1011*2+2 Exponent ist 2.

M = 011 (die führende 1 ist in Normalform redundant)

3. Bias addieren E = 12610 + 210 = 12810 = 100000002

4. Vorzeichen V = 15. Ergebnis: VEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMM

11000000001100000000000000000000

79

3.2.5 Gleitpunktzahlen: Arithmetik

Addition/Subtraktion Die Exponenten werden angeglichen, indem die Mantisse des Operanten mit dem

kleineren Absolutbetrag entsprechend verschoben wird. Anschließend werden die Mantissen addiert Beim Verschieben können Stellen verloren gehen.

Multiplikation Die Mantissen der Operanten werden multipliziert Die Exponenten werden addiert Sind die Exponenten zu groß, kann es zu Exponenten-Overflow kommen

Division Die Mantissen der Operanten werden dividiert Der Exponent ergibt sich aus der Differenz des Dividenden und Divisors Ist der Divisor zu klein und/oder der Dividend zu groß kann es zu einem Exponenten-

Underflow kommen.Das Ergebnis wird dann zu 0, alle Ziffern sind verloren

Nach allen Operationen wird die Normalform ggf. wiederhergestellt

80

3.2.6 Standards

Short -128 ... 127 (8Bit) Integer -32768 ... 32767 (16Bit) Unsigned Int 0 ...65535 (16Bit) LongInt -2147483648 ... 2147483647 (32Bit) Real nach IEEE 754

Float 1 VZ-Bit, 8 Bit E, 23 Bit M (32Bit) Double 1 VZ-Bit, 11 Bit E, 52 Bit M (64Bit) zwei Varianten 0,5 M < 1 bzw. 1 M < 2

Number sign exponent mantissa

normalized number 0/1 01 to FE any value

denormalized number 0/1 00 any value

zero 0/1 00 0

infinity 0/1 FF 0

NaN 0/1 FF any value but 0

81

3.2.6 Standards: Beispiel (Delphi)

In Borlands Delphi (Pascal) sind folgende Typen festgelegt: Typ Bereich Signifikant

Größe (Byte) Real48 2,9 x 10^-39 1,7 x 10^38 11-12 6 Single 1,5 x 10^-45 3,4 x 10^38 7-8 4 Double 5,0 x 10^-324 1,7 x 10^308 15-16 8 Extended 3,6 x 10^-4951 1,1 x 10^4932 10-20 10 Comp -2^63+1 2*63-1 10-20 8 Currency -922337203685477.5808 10-20 8

+922337203685477.5808 Der generische Typ Real ist in der aktuellen Implementierung mit dem Typ

Double identisch.

http://de.wikipedia.org/wiki/Borland_Delphi#Elementare_Datentypen

(7.5.2007)

82

3.3 Zusammenfassung des Kapitels

Darstellung von Zeichen ASCII EBCDIC UNICODE

Darstellung von Zahlen Zahlensysteme Konvertierung Arithmetik Ganze positive Zahlen Ganze negative Zahlen Gebrochene Zahlen Gleitpunktzahlen Standards

83

Kapitel 4 Strukturen

Information aus der realen Welt werden in einem informationsverarbeitenden System als Daten abgelegt. Diese stellen also eine (vereinfachte) Abstraktion der Wirklichkeit dar und spiegeln in vielen Fällen die Strukturen der Wirklichkeit wider.In diesem Kapitel wird ein Überblick über die wichtigsten abstrakten Datenstrukturen gegeben, wobei dieser Begriff zum Begriff des „Datentyps“ erweitert wird.Anmerkung: Dieses Kapitel abstrahiert die Objekte mit denen Sie in „Einführung in die Programmierung“ umgehen. Dort werden diese abstrakten Objekte konkret für Java vorgestellt.

Inhalt1. Datenstrukturen - Datentypen2. Datentypen: Ein Überblick3. Konkrete Datentypen4. Abstrakte Datentypen

… da schied Gott das Licht von der Finsternis1. Mose 1.4

84

4.1 Datenstrukturen - Datentypen

In der Literatur wird meist der Begriff „Datenstruktur“ verwendet. In diesem Unterkapitel soll der Unterschied zwischen diesem Begriff und dem Begriff des „Datentyps“ erläutert werden.

Inhalt1. Datenstrukturen2. Datentypen3. Variablen eines Datentyps

85

4.1.1 Datenstrukturen

In der Informatik werden Objekte der realen oder abstrakten Welt erfasst Bei der Erfassung beschränkt man sich möglichst auf die für den weiteren

Transport / Speicherung/Verarbeitung/Umsetzung notwendige Information Zur internen Repräsentation werden diese Objekte abstrahiert

Zur Abstraktion gehört die Erkennung von Strukturen - zunächst im Sinne einer Aggregation.

Also Aus welchen Teilobjekten bestehen Objekte ? In welchem Verhältnis stehen die Teilobjekte zueinander ? Welches sind die „atomaren“ Teilobjekte ?

es existieren noch weitere strukturelle Beziehungen (z.B. Vererbung) Anschließend werden diese Objekte typisiert.

Typisierung ist die Einteilung von abstrakten internen Objekten in Gruppen mit gleichen oder ähnlichen Eigenschaften.

86

4.1.2 Datentypen

Typen sind also nicht die intern repräsentierten Objekte, sondern beschreiben die Eigenschaft einer Gruppe von Objekten.

Zu diesen Eigenschaften gehören: Struktur Wertebereich anwendbare Operatoren, Funktionen, Relationen Beziehungen zu anderen Typen interne Repräsentationsweise …

Einige Anmerkungen:: Der Begriff „Datentyp“ ist weitergehend als der Begriff „Datenstruktur“ In der Objektorientierten Programmierung wird statt „Datentyp“ auch der Begriff

„Klasse“ verwendet (Klassen beschreiben mehr Eigenschaften) Konkrete Repräsentanten eines Datentyps werden (u.a) „Variable“ oder

- bei OO-Sprachen - „Instanz“ genannt

Beispiel:

Imaginäre Zahlen

87

4.1.3 Variable eines Datentyps

Einen speziellen (rechnerinternen) Repräsentanten eines Datentyps bezeichnet man als Variable. Die Festlegung, von welchem Datentyp eine Variable ist, bezeichnet man als Variablendeklaration.

Die Zuordnung eines Typs „Typ“ an eine Variable X wird (zunächst) wiefolgt notiert: var x : Typ;

Eine Variable hat alle Eigenschaften eines Datentyps.Zusätzlich dazu hat eine Variable: einen konkreten Wert.

Der Wert muss aus dem Wertebereich des Datentyps sein (oder undefiniert) Die Zuweisung eines Wertes „Wert“ an eine Variable X sei (zunächst) wie folgt

notiert: x = Wert; einen konkreten Speicherplatz

Dieser Speicherplatz ist so dimensioniert, dass die Struktur der Variable abgebildet werden kann

Dieser Speicherplatz wird (meist) implizit durch die Deklaration zugeordnet Beispiel: var x : Datentyp; // x ist vom Typ: „Datentyp“

x = 531; // Zuweisung von 531 an X

88

4.2 Datentypen: Überblick

Nachdem sich nun der Begriff des „Datentyps“ als Oberbegriff der „Datenstruktur“ erwiesen hat, konzentrieren wir uns im Rest des Kapitels auf wichtige Datentypen.In diesem Unterkapitel wird ein Klassifikationssystem für die in der Informatik verwendeten Datentypen aufgestellt und kurz erläutert

Inhalt1. Klassifikation der Datentypen2. Erläuterung der Klassifikation

89

4.2.1 Klassifikation der Datentypen

Datentypen

IdealisierteAbstrakteKonkrete

Einfache StrukturiertePointer(Zeiger)

Boolean(Wahrheitswert)

Integer(Ganzzahl)

Char (Zeichen)

Enumeration (Aufzählung)

Ordinale Real(Fließkomma)

Array (Feld)

Record (Verbund)

Union(Variantenverb.)

...

...

90

4.2.2 Erläuterung der Klassifikation

Idealisierte Datentypen aus der Mathematik bekannte Datentypen: R, N, Z, ... Variablen dieser Typen sind oft nicht endlich darstellbar (Bsp: 2) In einem Computer-Algebra-System symbolisch darstellbar (Bsp: 2^( 1/2))

Konkrete Datentypen in einem Rechner von Hard- oder Software bereitgestellte Datentypen entweder vordefiniert oder durch den Benutzer definierbar

Abstrakte Datentypen verbergen ihren inneren Aufbau vor dem Benutzer bestehen aus beliebigen Strukturen über konkrete/idealisierte Datentypen, sowie aus

Zugriffsfunktionen bzw. Prozeduren Beispiel: Baum

2 12 15

79

6 61

13

insert (Element)

delete (Element)

search (Element)

91

4.3 Konkrete Datentypen

Die am häufigsten abstrahierten Objekte der realen Welt sind, zumindest was die für eine weitere Verarbeitung notwendigen Informationen betrifft, einfach strukturiert und lassen sich demnach mit konkreten Datentypen abbilden.Dieses Unterkapitel gibt einen Überblick über alle konkreten Datentypen und beschreibt diese.

Inhalt1. Einfache Datentypen2. Strukturierte Datentypen3. Verweise

92

4.3.1 Einfache: Boolean (Wahrheitswert)

zur Darstellung von Wahrheitswerten Wertebereich: true, false

intern in manchen Programmiersprachen als 1 bzw. 0 dargestellt Operatoren: und, oder, nicht, Vergleiche, ...

Operatoren entsprechend der bool‘schen Algebra oft auch allgemeine arithmetische Operationen möglich Vorsicht vor Integer-Arithmetik mit Boolean-Variablen

Notation: var booleanVar : boolean; Beispiel: var switch : boolean;

switch = false; // = 0 „Bool-Literal“switch = not(switch); // = not(0) = 1switch = switch and not(switch); // = 1 and 0 = 0switch = switch or not (switch); // = 0 or 1 = 1

Wir müssen uns gleich angewöhnen die „Dinge“ so zu bezeichnen, wie sie in der Informatik bezeichnet werden:Schlüsselwort var (Variablen)Bezeichner switch Schlüsselzeichen(-wort) : (Typ)Bezeichner boolean Schlüsselzeichen(-wort);Bezeichner switch Operator = (Boolean)Literal false Schlüsselzeichen(-wort);

93

4.3.1 Einfache: Integer (Ganzzahl)

zur Darstellung ganzer Zahlen mit oder ohne Vorzeichen Wertebereich: Unterschiedlich

unsigned integer: Ganze Zahlen ohne Vorzeichen ( 0... 65535 ) oft 16 bit bzw. 32 bit als ‚short int‘ bzw. ‚long int‘ bezeichnet Vorsicht: 16 bit Integer ist verdammt wenig ((± 32267)

Speicherplatz ist nicht mehr teuer benutzen Sie ‚long int‘(Ausnahmen bestätigen die Regel)

Operatoren: Grundrechenarten, Vergleiche Operatoren entsprechend der „klassischen“ Algebra

Notation: var integerVar : integer; Beispiel: var i : integer;

i = 1; // = 1 „Integer-Literal“ i = i + 32;´ // = 1 + 32 = 33

i = i / 17; // = 33 / 17 = 1 !i = i + 65535; // bei unsigned Int.: Fehler !

94

4.3.1 Einfache: Char (Zeichen)

zur Darstellung von Zeichen Vorsicht: Typischerweise wird die ASCII-Codierung zugrundegelegt,

kann aber auch Unicode sein Wertebereich: Alle Zeichen

Intern codiert als ASCII oder - neuerdings immer öfter - als UnicodeASCII: 8 Bit (7 benutzt), Unicode: 16 Bit

Intern oft als Integer repräsentiert Operationen: Vergleich

oft auch allgemeine arithmetische Operationen möglich Vorsicht vor Integer-Arithmetik mit char-Variablen

Notation: var charVar : char; Beispiel: var symbol : char;

symbol = „A“; // = „A“ „Char-Literal“symbol = symbol + 32;´ // = „A“ + 32 = „a“symbol = symbol - 128; // = „a“ - 128 = Fehler

95

4.3.1 Einfache: Enum (Aufzählung)

zur Darstellung endlicher benutzerdefinierter Wertebereich Es ist guter Stil, Mengen mit (garantiert) kleiner Mächtigkeit (<10) als Enum-Type zu

deklarieren, anstatt sie z.B. als Integer zu kodieren. Intern werden Enum-Werte oft als Integer abgelegt

Operatoren: Vergleich oft auch allgemeine arithmetische Operationen möglich Vorsicht vor Integer-Arithmetik mit Enum-Variablen

Notation: var enumVar : enum { Wertemenge }; Beispiel: var ampelfarbe : enum {gruen,gelb,rot} ;

ampelfarbe = gruen; // = gruen „Enum-Literal“ // Vorsicht: C++ erlaubt das

ampelfarbe = ampelfarbe +1 ; ´ // = gruen + 1 = gelbampelfarbe = ampelfarbe +1 ; ´ // = gelb + 1 = rotampelfarbe = ampelfarbe +1 ; ´ // = rot + 1 = Fehler !

96

4.3.1 Einfache: Real (Fließkomma)

zur näherungsweisen Darstellung reeller Zahlen Wertebereich: Unterschiedliche Genauigkeiten und Wertebereiche

Wertebereich entspricht typischerweise der IEEE 754 Norm, also: Float: 32 bit Double: 64 bit

Operationen: Grundrechenarten, erweiterte Arithmetik, Vergleich Notation: var realVar : real; Beispiel: //--- Variable declaration --------------------------

var pi, flaeche, radius : real; // all real !

//--- Initialisation --------------------------------pi = 3,141; // needs not to be more accurateradius = 5; // might be changed by user

//--- Computation of surface ------------------------flaeche = 2 * pi * (radius ^ 2); // common formula

97

4.3.2 Strukturierte: Array (Feld)

Arrays sind eine Aggregationen von Daten des gleichen Typs(des „Basistyps“) Aggregation := Zusammenfassung, Anhäufung, Angliederung Die Grenzen des Arrays sind (meist) statisch bestimmt

Operation: Auswahl Die Auswahl eines Datenelementes erfolgt über einen ganzzahligen Index über den

(Auswahl-)Operator „ [ ] “ Vorsicht: Zugriff außerhalb des deklarierten Bereiches führt zu Fehlern

Notation: var arrayVar : array[min .. max] of Datentyp

Beispiele Eindimensionales array: var Vektor : array[1..4] of real; Zweidimensionales array: var Matrix : array[1..3] of

array[1..2] of real; Operator var m : array[1..3] of

array[1..2] of real;var v : array[1..4] of real;v[3] = 5,03; v[4] = 4,12;m[1][2] = v[3] * 12 - v[4];

98

4.3.2 Strukturierte: Record (Verbund)

Verbunde sind Aggregationen von Daten möglicherweise unter-schiedlichen Typs manchmal auch „structure“ oder „struct“ genannt

Operation: Auswahl Die Auswahl erfolgt durch Angabe des Komponentennamens

(durch einen Punkt vom Variablennamen getrennt) Notation: var recordVar : record

{ komponent1 : type1; ... };

Beispiel: var d : record{ tag : Integer; monat : Integer; };

d.monat = 10; d.tag = 20;

99

4.3.2 Strukturierte: Variant Record (Variantenverb.)

Verbunde, deren Struktur mögliche Alternativen zulassen manchmal auch „union“ genannt lassen „Varianten“ eines Record-Types zu

Operation: Auswahl (wie bei records über Punkt-Operator) Notation: var recVar : record {

komponent1 : type_1; ...;

TAGGED TYPE case variant (variant1,...) of { variant1 : type_n; ... } }

Unterelement „variant“ implizit definiert bei „tagged type“ Nur ein Unterelement aus variant1, ... (sinnvoll) verwendbar

Beispiel: var adam,eva : record { name : array [1..20] of char; adam.sex = m;

case sex (m,f) of { adam.muscle = 20,5;

f: {IQ: integer}; eva.sex = f; m: {muscle: real}; // in cm eva.IQ = 132;}

100

4.3.2 Strukturierte: Variant Record

var adam,eva : record { name : array [1..20] of char; adam.sex = m;

case sex (m,f) of { adam.muscle = 20,5;

f: {IQ: integer;} eva.sex = f; m: {muscle: real;}} eva.IQ = 132;}

Umsetzung:

Variant Records mit „Untagged Types“ (z.B. C, C++ : Union) (2. Variante)struct {

char[20] name; enum {m,f} sex; // ... adam.sex = m; union { adam.muscle = 20,5; int IQ; eva.sex = f; real muscle;} // in cm eva.IQ = 132;} adam, eva;

name sex IQ /muscle

101

4.3.2 Vereinfachung der Notation („type“)

var Person : record { surname : array [1..20] of char; forename : array [1..20] of char; birthday : record { year : integer; month : enum {jan,...}; day : integer; }; };var Akt_Datum : record { year : integer; month : enum {jan,feb,...}; day : integer; };

In (fast) allen Programmiersprachen ist es möglich, beliebig strukturierte Datentypen neu zu bezeichnen und diese Typ-Bezeichner wie vordefinierte Typen zu verwenden: Notation: type NeuTyp : Typ; Beispiel: type Datum : record { year : integer;

month : enum {jan,feb,...}; day : integer; };

var Person: record {surname : array [1..20] of char; forename : array [1..20] of char; birthday : Datum }; var Akt_Datum: Datum;

102

4.3.3 Pointer (Zeiger, Verweis)

Zeiger-Datentypen sind durch folgende Eigenschaften gekennzeichnet: Die Struktur ist identisch der eines Integer-Datentyp (also oft 16,32,... Bit) Der Wertebereich ist der des Adressbereiches eines Rechnersystems,

der zusätzliche Wert „nil“ bezeichnet einen ungültigen Zeiger. Operatoren sind:

Erzeugen eines Zeigers (Referenzierung &) Zugriff auf verwiesenen Bereich (Dereferenzierung *) Integer-Operatoren (Vorsicht !!!!)

Notation: var pointerVar : *Type; Beispiel: var x : *Integer; // Deklaration

var y,z : Integer; // Deklarationen y = 5; // Initialisierung der Variablen y

x = &y; // Referenzieren: x ist Zeiger auf yx* = 2; // Derefenzierung: das worauf x zeigt wird zu 2z = y; // Variable z bekommt den Wert von Variable y zugewiesen.// z hat jetzt den Wert 2

103

Bsp.: x : *Integer; // Deklarationy : Integer; // Deklaration

y = 5; // Initialisierung der Variablen y

x = &y; // Referenzieren: x ist Zeiger auf y

x* = 2; // Dereferenzierung: das worauf x zeigt

x = 2; // Zuweisung ohne Dereferenzierung !

4.3.3 Pointer: Beispiel

nil 01 2 3 4 5 6 7 8 9 23 24 25 26 27 28

...

nil 51 2 3 4 5 6 7 8 9 23 24 25 26 27 28

...

25 51 2 3 4 5 6 7 8 9 23 24 25 26 27 28

...

2 21 2 3 4 5 6 7 8 9 23 24 25 26 27 28

...

25 21 2 3 4 5 6 7 8 9 23 24 25 26 27 28

...

Vorsicht:: Werte oft undefiniert

Wortadressen

104

4.3.3 Pointer: Dynamische Datentypen

Mit konkreten, d.h. einfachen und strukturierten Datentypen lassen sich nur statische Struktur aufbauen d.h. Strukturen, deren Speicherbedarf beliebig aber fest sind Bem.: Die Beliebigkeit ist begrenzt durch die Gesamtspeicherkapazität

Mit Zeiger-Datentypen lassen sich Strukturen aufbauen, die sich dynamisch auf- und abbauen lassen d.h. Strukturen, deren Speicherbedarf sich dynamisch verändern kann d.h. der Speicherplatz muss auch dynamisch organisiert werden. Bem.: Auch hier ist die Beliebigkeit begrenzt durch die Gesamtspeicher-kapazität

Beispiel: type knoten : record{ symbol : char; links : *knoten; rechts : *knoten;}

var wurzel : knoten

B

C E D A

Huffman(Bsp. aus Kap.2)

105

4.3.4 Beispiel: Kombinierte Datentypen

Um nun beliebig komplexe Strukturen der „realen“ Welt in einem Rechensystem abbilden zu können, kann man die vorgestellten Datentypen beliebig miteinander Kombinieren

Beispiel.:

type Person : record { type Date : record { surname : array [1..20] of char; year : integer; forename : array [1..20] of char; month : enum {jan,feb,...}; birthday : Date; day : integer; next : *Person; } previous : *Person;}

106

Datenstrukturen

4.4 Abstrakte Datentypen

Grundsätzlich lassen sich alle Objekte der realen Welt ausschließlich mit Hilfe einfacher Datentypen abbilden. Diese Abbildung ist aber meist „unnatürlich“, weil sie die Struktur realer Objekte nicht ausreichend berücksichtigt. Abhilfe schaffen hier strukturierte Datentypen, die allerdings grundsätzlich nur endliche Objektmengen repräsentieren können. Hier schaffen Zeigertypen Abhilfe.

Kann man nun mit diesen Mitteln Strukturen realer Objekt natürlich abbilden, so fehlen diesen abstrakten Datentypen einige der Eigenschaften, die konkreten Datentypen von Datenstrukturen unterscheiden, dies sind insb. Operationen und Beziehungen zu anderen Typen.

Einen vertieften Einblick in die bunte Welt abstrakter Datentypen bietet die Vorlesung des 2. Semesters

107

4.5 Zusammenfassung des Kapitels

Wir sind damit auch an die Grenzen dessen gelangt, was in dieser Vorlesung über die „Statik“ von Objekten gesagt werden soll und wenden uns einem noch spannenderem Themenbereich zu ;-)

Datentypen

IdealisierteAbstrakteKonkrete

Einfache StrukturiertePointer(Zeiger)

Boolean(Wahrheitswert)

Integer(Ganzzahl)

Char (Zeichen)

Enumeration (Aufzählung)

Ordinale Real(Fließkomma)

Array (Feld)

Record (Verbund)

Union(Variantenverb.)

...

...

108

Kapitel 5 Algorithmus

In den vorangegangenen Kapiteln wurde, aufbauend auf dem Begriff der Information, beschrieben, wie die statischen Objekte der Informatik aussehen und notiert werden können.In diesem Kapitel wird aufgezeigt, wie man die Verarbeitung dieser Objekte (also die Dynamik) beschreiben kann. Wesentlicher Begriff dabei ist der Begriff des Algorithmus

Inhalt1. Ein Beispiel2. Definition3. Die Strukturelemente4. Strukturierung5. Blockung6. Iteration und Rekursion7. Zusammenfassung

Teile dieses Kapitels sind aus:R.Manthey: Vorlesung Informatik 1, Uni Bonn, 2001

… und Vögel sollen fliegen auf Erden1. Mose 1.20

109

5.1 Ein Beispiel

Zunächst soll ein kleines Beispiel in eine mögliche Aufgabenstellung aus dem (bekannten) Bereich der Mathematik einführen und dadurch auch eine (eingeschränkte) Vorstellung über die Aufgaben und Elemente eines Algorithmuses geben.

Inhalt1. Das Problem (Beispiel)2. Ein Algorithmus I3. Ein Algorithmus II4. Vergleich der Algorithmen5. Ein Algorithmus III6. Fragestellungen7. Ein weiterer Algorithmus

110

5.1.1 Das Problem

Eine quadratischen Gleichung:

Allgemeine Darstellung der quadratischen Gleichung

Allgemeine Lösung der quadratischen Gleichung

Lösung der quadratischen Gleichung

x2 + 8x + 7 = 0

x2 + px + q = 0

x1,2= -p/2 p2/4 - q +-

x1,2 = -8/2 82/4 - 7

= -4 3

+-+-

x1 = -1x2 = -7

111

Zuweisungen

5.1.3 Ein Algorithmus I

1. Lies die Zahlen p und q ein

2. Berechne die Zahl w = p2/4 - q

3. Berechne die Zahl x1 = -p/2 + w

4. Berechne die Zahl x2 = -p/2 - w

5. Gib x1 und x2 als Ergebniss aus

Ein Algorithmus

Berechnungen

Ausgaben

Eingaben

Variable

Konstante

x1,2= -p/2 p2/4 - q +-

112

5.1.4 Ein Algorithmus II

Ein zweiter Algorithmus

1. Lies die Zahlen p und q ein

2. Berechne die Zahl p/2; Nenne diese Zahl a

3. Berechne die Zahl a2 ; Nenne diese Zahl b

4. Berechne die Zahl b-q ; Nenne diese Zahl c

5. Berechne die Zahl c ; Nenne diese Zahl d

6. Berechne die Zahl -a ; Nenne diese Zahl e

7. Berechne die Zahl e + d ; Nenne diese Zahl x1

8. Berechne die Zahl e - d ; Nenne diese Zahl x2

9. Gib x1 und x2 als Ergebniss aus

FHSymbol1 Es gibt (oft unendlich) viele Algorithmen zurLösung eines Problems

x1,2= -p/2 p2/4 - q +-

113

5.1.5 Vergleich der Algorithmen

Berechne die Zahl w = p2/4 - q

Berechne die Zahl x1 = -p/2 + w

Berechne die Zahl x2 = -p/2 - w

Berechne die Zahl p/2; Nenne diese Zahl a

Berechne die Zahl a2 ; Nenne diese Zahl b

Berechne die Zahl b-q ; Nenne diese Zahl c

Berechne die Zahl c ; Nenne diese Zahl d

Berechne die Zahl -a ; Nenne diese Zahl e

Berechne die Zahl e + d ; Nenne diese Zahl x1

Berechne die Zahl e - d ; Nenne diese Zahl x2

A1 A2Anzahl Berechnungen 10 7Anzahl Zuweisungen 3 7Anzahl Variablen 5 9

FHSymbol1

WelcherAlgorithmusist besser ?Warum ?

114

1. Lies die Zahlen p und q ein

2. Berechne die Zahl a = p/2

3. Berechne die Zahl b = a2

4. Berechne die Zahl c = b-q

5.a Wenn c negativ ist brich den Algorithmus abAnsonsten mache mit nächstem Schritt weiter

6. Berechne die Zahl d = c

7. Berechne die Zahl e = -a

8. Berechne die Zahl x1 = e + d 1

9. Berechne die Zahl x2 = e - d

10. Gib x1 und x2 als Ergebniss aus

5.1.6 Ein Algorithmus III

Problem: Negatives Wurzelargument

BedingteAusführung

5.b Wenn c negativ istgehe zu Schritt 1

Schleife

115

5.1.7 Fragestellungen

Wer gibt p und q ein ? Wie wird p und q eingegeben ? Werden p und q in endlicher Zeit

eingegeben ? Sind p und q im richtigen Format ? Ist Variable a im richtigen Format ? Gibt es die Quadrat-Funktion ? Ist c positiv ? Ist Variable e im richtigen Format ? Sind die restlichen Variablen im

richtigen Format Reicht die Genauigkeit der Darstellung

? Wo wird das Ergebnis ausgegeben ? Ist ausreichend Variablenkapazität für

den Algorithmus vorhanden ? Läuft der Algorithmus schnell genug ? ...

1. Lies die Zahlen p und q ein

2. Berechne die Zahl a = p/2

3. Berechne die Zahl b = a2

4. Berechne die Zahl c = b-q

6. Berechne die Zahl d = c

7. Berechne die Zahl e = -a

8. Berechne die Zahl x1 = e + d 1

9. Berechne die Zahl x2 = e - d

10. Gib x1 und x2 als Ergebniss aus

116

5.1.8 Ein weiterer Algorithmus

117

5.2 Definition

Der Begriff des Algorithmus ist zentral in der Informatik und soll in diesem Unterkapitel formal definiert werden

Inhalt1. Herkunft2. Der Algorithmus3. Weitere Prinzipien4. Algorithmen und Programme5. Ausflug: Algorithmus und WinOSe

118

5.2.1 Herkunft

Muhammad ibn Musa abu Djafar al-Choresmi (ca. 780-850 n.Chr) arabischer Mathematiker, geboren in Choresmien (heute: Usbekistan) lebte und wirkte in Bagdad im „Haus der Weisheit“

(Noah Gordon: „Der Medicus“) war beteiligt an der Übersetzung der Werke griechischer Mathematiker

ins Arabische schrieb ein „Kurzgefasstes Lehrbuch für die Berechnung durch

Vergleich und Reduktion“ die lateinische Übersetzung dieses Buches („liber algorismi“) kam durch

Kreuzfahrer nach Europa verfasste auch ein Buch mit dem Titel „Al-Mukhtasar fi Hisab al-Jahr va

l-Muqabala“

AlgebraAlgorithmus

119

5.2.2 Der Algorithmus: Definition

Ein Algorithmus (algorithm) ist die Beschreibung eines Verfahrens, um aus gewissen Eingabegrößen bestimmte Ausgabegrößen zu berechnen.Dabei müssen folgende Bedingungen erfüllt sein Spezifikation

Es muss spezifiziert sein, welche Eingabegrößen erforderlich sind und welchen Anforderungen diese Größen genügen müssen, damit das Verfahren funktioniert (Eingabespezifikation)

und welche Ausgabegrößen bzw. Resultate) mit welchen Eigenschaften berechnet werden (Ausgabespezifikation)

Durchführbarkeit Endliche Beschreibung: das Verfahren muss in einem endlichen Text vollständig

beschrieben sein Effektivität: Jeder Schritt des Verfahrens muss effektiv (d.h. tatsächlich) „mechanisch“

ausführbar sein. (Bem.: „Effektivität“ ist nicht zu verwechseln mit „Effizienz = Wirtschaftlichkeit“)

Determiniertheit: Der Verfahrensablauf ist zu jedem Zeitpunkt fest vorgeschrieben Korrektheit

partielle Korrektheit: Jedes berechnete Ergebnis genügt der Ausgabespezifikation, sofern die Eingaben der Eingabespezifikation genügt haben

Terminierung: Der Algorithmus hält nach endlich vielen Schritten mit einem Ergebnis an, sofern die Eingaben der Eingabespezifikation genügt haben

Algorithmen, die eine oder mehrere dieser Eigenschaften nicht besitzen werden dann als Nicht-<Eigenschaft> Algorithmen bezeichnet (Bsp: Nicht-Deterministische Algorithmen)

120

5.2.3 Weitere Prinzipien

Neben den in der Definition angegebenen Eigenschaften gibt es weitere wichtige Prinzipien, die bei der Erstellung eines Algorithmussees zu beachten sind: Effizienz

Der Algorithmus soll möglichst wenig Aufwand verursachen– Das Ergebnis mit möglichst wenig Rechenschritten (oder mit möglichst wenig

Speicherbedarf) erzielen Wartbarkeit

Ein Algorithmus sollte so verständlich sein, dass ihn Personen, die ihn nicht entwickelt haben zumindest so weit verstehen, umm ggf. Fehler zu beheben

Erweiterbarkeit Unter Erweiterbarkeit versteht man die Anwendbarkeit eines Algorithmus auch

für Anwendungen, die zunächst nicht vorgesehen sind. Man sollte daher bei der Eingabespezifikation von Spezialfällen abstrahieren.

Robustheit Unter Robustheit versteht man „gutartiges“ Verhalten auch für Eingabewerte

außerhalb der Eingabespezifikation, Man sollte daher die Eingabemenge der Eingabespezifikation gleich möglichst so definieren, dass auch „exotischere“ Eingabewerte betrachtet werden..

121

5.2.4 Algorithmen und Programme: Der Weg

gegeben: das Problem durch Spezifizieren wird das Problem formal beschrieben

Durch Algorithmierung (Algorithmenentwurf) wird ein Algorithmus erzeugt durch Verifizieren kann der Algorithmus auf Übereinstimmung mit der Spezifikation

überprüft werden Durch Programmieren wird aus den Algorithmus ein Programm erzeugt

durch Testen kann das Programm auf Übereinstimmung mit der Spezifikation und dem Algorithmus überprüft werden.

Problem Algorithmus Programm

Spezifizieren Verifizieren Testen

Algorithmierung Programmierung

122

5.2.4 Algorithmen und Programme: Beziehungen

Programmieren setzt Algorithmenentwicklung voraus Kein Programm ohne Algorithmus !

Jedes Programm repräsentiert einen bestimmten Algorithmus. Ein Algorithmus kann durch viele Programme repräsentiert werden.

Algorithmus ProgrammProgrammierung

ProblemAlgorithmierung

Problem

Algorithmus1 Algorithmus2

Programm21 Programm22

...

...

123

5.2.5 Ausflug: Algorithmus und WinOSe

KlassischeProgrammierung

WindowsProgrammierung

Algorithmus

OS

OS Eventqueue

124

5.3 Strukturelemente

Um die Dynamik - also die Abfolge von Aktionen - eines Algorithmu-ssees zu beschreiben, benötigt man formale Beschreibungsmittel, sowie eine Festlegung, wie diese Beschreibungsmittel zu notieren und zu interpretieren sind.Dieses Unterkapitel stellt die formalen Beschreibungsmittel für Algorithmen vor. Diese Beschreibungsmittel sind dabei gleichzeitig Strukturierungselemente für Algorithmen, denn sie definieren die Struktur von Algorithmen.

Inhalt:1. Die Elemente2. Folge3. Auswahl4. Wiederholung

125

5.3.1 Die Elemente: Aus dem Beispiel

Zuweisungen Berechnungen

Mathematische Grundoperationen komplexe Funktionen ...

Bedingte Ausführungen Schleife ...

Variable Texte Zahlen ...

Konstanten(Literale) Texte Zahlen ...

EINGABE

AUSGABE

126

5.3.1 Die Elemente: Notation

Für die Beschreibung von Algorithmen gibt es viele Möglichkeiten Alltagssprache Konkrete Programmiersprache Dazwischen gibt es eine Vielzahl von Notationen, die den Übergang zwischen

Problembeschreibung und Programm erleichtern sollen Eine mögliche - eindimensionale - Notation ist Pseudocode:

// Dies ist eine Zuweisungx = 42; Kommentare werden (hier) mit vorangestellten Slashes „//“ gekennzeichnet Aktionen werden (hier) mit Semikolon „;“ getrennt

Visualisierung durch graphische - zweidimensionale -Notation Flussdiagramme Struktogramme (=Nassi-Shneiderman-Diagramme)

Aktion Aktion

127

5.3.1 Die Elemente: atomare Elemente

Anweisungen sind die atomaren Elemente eines Algorithmus‘, die Elemente also, aus denen ein Algorithmus aufgebaut ist.

Es gibt (zunächst) drei Arten dieser „atomaren“ Elemente Zuweisung:

Pseudocode x = y; Auf der linken Seite der Zuweisung steht eine Variable auf der rechten Seite

der Zuweisung steht entweder eine Variable, ein Literal oder eine Berechnung aus Variablen und Literalen

Eingabe Pseudocode: x << <Eingabegerät> ; Als Eingabegerät kann ein geeignetes physikalisches Gerät (Tastatur,

Schnittstelle, ...) angegeben werden. Ausgabe

Pseudocode: x >> <Ausgabegerät> ; Als Ausgabegerät kann ein geeignetes physikalisches Gerät (Bildschirm,

Drucker, Schnittstelle, ...) angegeben werden Ein- und Ausgabe können auch als Zuweisung verstanden werden.

128

5.3.1 Die Elemente: Kontrollelemente

Die atomaren Elemente eines Algorithmuses können durch drei einfache Strukturierungsmethoden, den „Kontrollelementen“, zueinander in Beziehung gesetzt werden:

1. Folge (Sequenz)(auch wenn in Mehrprozessor-Maschinen eine parallele Ausführung von atomaren Elementen möglich ist, wollen wir die Parallelisierung hier nicht betrachten)

2. Auswahl (Selektion, Fallunterscheidung)3. Wiederholung (Iteration, Schleife)

Die Kontrollelemente bestimmen die Reihenfolge von Aktionen in Algorithmen Eine Aktion (Ai) - auch Verarbeitung genannt - ist ein atomares Element oder

eine durch die Strukturmethoden zusammengefasste Menge mehrerer Aktionen

129

5.3.2 Folge

Folgen bestimmen die lineare Reihenfolge von Aktionen in Algorithmen: Flussdiagramm Struktogramm Pseudocode:

A1

A2

An

...

A1

A2

An

...

{ A1; A2; ... An;}

130

5.3.3 Auswahl : bedingte Verarbeitung

Eine Aktion wird, in Abhängigkeit einer bool‘schen Bedingung ausgeführt oder nicht auch „einarmiges if“ genannt.

Flussdiagramm Struktogramm Pseudocode:

Beispiel: if (x<0) then x = -x;

A1

BA1

if B then A1;Bf

wfw

131

A2

5.3.3 Auswahl : einfache Alternative

In Abhängigkeit einer bool‘schen Bedingung wird entweder eine Aktion oder eine andere Aktion ausgeführt auch „zweiarmiges if“ genannt.

Flussdiagramm StruktogrammPseudocode

Beispiel: if (x<0) then x=-x else x=0;

A1

BA1

if B then A1

else A2;

Bfw

fw

A2

132

5.3.3 Auswahl : mehrfache Alternative

In Abhängigkeit einer Bedingung (mit mehreren möglichen Werten w1, w2, ..., wn) wird eine Aktion aus einer Menge möglicher Aktionen ausgewählt und ausgeführt

Flussdiagramm StruktogrammPseudocode

Beispiel: switch x: { case 0: x = x/2; case 1: x = x+1;}

Oft auch mit „else“-Alternative (statt wn)

A1

B switch B:{ case w1: A1; case w2: A2; ... case wn: An;}

Bw1

w1

A2 An

A1 A2 An

wnw2 wn

133

5.3.4 Schleife: mit vorausgehender Prüfung

Solange eine bool‘sche Bedingung erfüllt ist, wird eine Aktion ausgeführt. Die Bedingung wird vor der ersten Ausführung der Aktion geprüft heißt auch: abweisende Schleife (While-Schleife)

Flussdiagramm StruktogrammPseudocode

Beispiel: while x < 100 { x = x + 1;}

A1

A1

while B{ A1

}

Bf

w

B

134

5.3.4 Schleife: mit nachfolgender Prüfung

Solange eine bool‘sche Bedingung nicht erfüllt ist, wird eine Aktion ausgeführt. Die Bedingung wird (erst) nach der ersten Ausführung der Aktion geprüft heißt auch: Repeat-Schleife Manchmal auch als Variante „Do-While-Schleife“ - z.B. in C++ - aber:

Die „ Do-While-Schleife“ wird solange ausgeführt solange eine bool‘sche Bedingung erfüllt ist.

Flussdiagramm StruktogrammPseudocode

Beispiel: repeat { x = x + 1; } until x == 100

A1 A1repeat{ A1

} until BBf

w

B

135

5.3.4 Schleife: Beispiel (abweisende Schleife)

Untersuche ob eine gegebene natürliche Zahl Primzahl ist. p > 2 ist Primzahl, falls sie durch kein t mit 1<t<p teilbar ist (p mod t 0)

Idee: wenn p Primzahl, dann ist p ungerade es genügt, nur ungerade t zu untersuchen es genügt, nur solche t zu untersuchen die kleiner p sind,

Algorithmus:

p << Tastatur;if ((p>2) and (p mod 2 != 0)) then { t = 3; // initialize t while ((t*t<p) and (p mod t != 0)) { t = t + 2; } // nach Schleife ist t*t >=p oder p mod t == 0 if (t*t>p) then „p ist Primzahl“ >> Bildschirm; else „p ist keine Primzahl“ >> Bildschirm;}else { „p <= 2 oder p gerade“ >> Bildschirm; } // Primzahl ?

136

5.3.4 Schleife: Beispiel (Vergleich while repeat)

Sind diese Schleifen im Ergebnis identisch ?while x < 100 repeat{ { x = x + 1; x = x + 1;} } until x < 100

und jetzt ? repeat{

x = x + 1;} until x >= 100

Letzer Versuch: if (x < 100) then { repeat {

x = x + 1; } until x >= 100}

Welche Lösung ist eleganter ? aber: oft wird eine erstmalige Aktion benötigt, um ein Datum überhaupt überprüfen zu

können.

137

5.3.4 Schleife: Beispiel (Vergleich repeat while)

Ausdrucken einer Datei repeat{ x << Datei; if (x != eof) x >> Drucker;} until x == eof //endoffile

... das Ganze als while-Schleife ? while (x != eof ){

x << Datei; x >> Drucker;}

Noch‘n Versuch: x << Datei;while (x != eof ){

x >> Drucker; x << Datei;}

138

5.3.4 Schleife: Beispiel (Schleife mit Zählern)

Sehr häufig werden Schleifen verwendet, deren Bedingung abhängig von Zählerwerten sind. Die Zählerwerte werden vor Eintritt in die Schleife initialisiert Die Bedingung prüft den Zählerwert Im Schleifenkörper wird der Zähler erhöht (increase) oder erniedrigt (decrease)

Vorsicht mit: dem Zählertyp, dem Additionswert, der Bedingung Algorithmus:

// --- Initialisierung ------------------------------s = 0;i = 1; // Initialisierung des Schleifenzählers// --- Schleife (Berechnet Summe 1..n) -------------while ( i <= n ){ s = s + i; i = i + 1; // Erhöhung des Schleifenzählers (oft um 1)}

139

5.2.4 Schleife: Die „For“-Schleife

Da Schleifen mit Zähler sehr häufig auftreten, stellen viele Programmiersprachen ein eigenes sprachliches Mittel dafür zur Verfügung: Die „For“ Schleife

Pseudocode: Beispiel:for var=start_value to end_value for i=1 to 10{ { A; x = x + i; } }

Der Zähler (var) wird pro Schleifendurchlauf implizit um 1 erhöht(Bei manchen Sprachen - z.B. Basic, C, C++ - kann man dies ändern)

Dieser Code ist äquivalent mit folgender Schleife:i = start_valuewhile i <= end_value{ A; i = i+1;}

140

5.3.4 Schleife: Beispiel (Endlosschleife)

Manchmal macht es Sinn, Schleifen endlos laufen zu lassen: z.B. bei der zyklischen Abprüfung von Systemzuständen (Windows Event-Queue) manchmal macht das keinen Sinn - passiert aber trotzdem ;-)

Flussdiagramm StruktogrammPseudocode

Beispiel: while true { „Druckerpapier ist teuer“ >> Drucker;}

A1

A1

while true{ A1

}

B

141

5.4 Strukturierung

Mit Hilfe atomarer Elemente und der Kontrollelemente lassen sich Algorithmen strukturieren. In diesem Kapitel sind einige Begriffe zur Strukturierung erläutert. Insbesondere wird ein weiteres - viertes - Kontrollelement vorgestellt (und auch gleich wieder verworfen)

Inhalt1. Control Flow2. Strukturierung durch Sprung3. Strukturiert-iterative Beschreibungsform4. Strukturierungstypen

142

5.4.1 Control Flow

Mithilfe der Kontrollelemente können die „atomaren“ Elemente (Anweisungen) strukturiert werden

Die Anordnung der Anweisungen (als atomare Elemente) eines Algorithmus, die bestimmt, in welcher Reihenfolge Dinge geschehen, heißt control flow (Steuerungsverlauf, Kontrollfluss) des Algorithmus genannt Manchmal wird auch der Programmablauf oder Kontrollfaden (thread of control,

thread), also die tatsächlich abgespulten Schritte und Anweisungen so bezeichnet

143

5.4.2 Strukturierung durch Sprung

Bei der Vorstellung der Kontrollelemente wurde (aus hinterhältig, didaktischen) Gründen auf ein viertes Element verzichtet:Der Sprung („Goto“-Anweisung)

Die Konstruktion „fahre fort mit Schritt x“ (goto x) stellt einen solchen Sprung (jump) im Steuerungsverlauf dar Zur Anwendung von goto werden Schritte mit einer Marke (Label) versehen, um das

Ziel des Sprunges zu kennzeichnen Dies ist die elementarste Form, eine Wiederholung oder sonstige Verzweigung im

Ablauf auszudrücken Dadurch erhalten wir die elementar-iterative Beschreibungsform von Algorithmen,

die die Strukturierung mit ein-/mehrfacher Auswahl und Schleifen funktional abdeckt. Beispiel:

while x<100 { 1: if x>=100 goto 2 x = x+1 x = x+1;} goto 1;

2: ...

144

5.4.2 Strukturierung durch Sprung

Anwendung von Sprüngen ist sehr gefährlich! Sprünge strukturieren komplexe Programm nicht ausreichend - der

Steuerungsverlauf kann verworren und unübersichtlich sein Um den Steuerungsverlauf auch bei komplexen Algorithmen übersichtlich zu

halten, schränkt man die Sprünge ein: Schleifen der Flussdiagramme sind höchstens ineinander geschachtelt Schleifen überkreuzen sich nicht!

Bei gut strukturierten Algorithmen würde man z. B. nur wieder eine geschlossene Schleife oder einen (vorzeitigen) Sprung bedingt durch die Behandlung des Trivialfalls erlauben

Wir sprechen in diesem Fall von strukturierten Sprüngen im Gegensatz zu freien Sprüngen, die prinzipiell beliebige Ziele haben können

145

5.4.3 Strukturiert-iterative Beschreibungsform

Sprünge können alle „höhere“ Strukturierungsarten funktional abbilden.Hier gilt auch der Umkehrschluss

In der strukturiert-iterativen Beschreibungsform kommen Sprünge nur noch implizit bei der Ausführung höherer Iterationsstrukturen vor Dieses sind Fallunterscheidungen (Auswahl) wie if-then-else oder insbesondere Schleifenkonstrukte

Diese bewirken, dass der Programmfluss In einer Auswahl zu genau einer Auswahl geht. in einer Schleife von einer Prüfung zu den Aktionen des Schleifenkörpers und

wieder zurück zur Prüfung geht. Viele höhere Programmiersprachen (Pascal, C, C++) erlauben jedoch die

Verwendung von Sprüngen Aus Optimierungsgründen (Nähe zur Maschinensprache) Aus Strukturierungsgründen)

146

5.4.4 Strukturierungstypen

Beispiel: Schemen einiger Kontrollflüsse

Strukturiert-iterativ Elementar-iterativ Spaghetti-Code

147

5.5 Blockung

Mit Hilfe der bislang vorgestellten Kontrollelemente lassen sich die atomaren Elemente (Anweisungen) eines Algorithmus‘ zu einem Kontrolfluss strukturieren. Wie wir gesehen haben, kann dieser Kontrollfluss mehr oder weniger „wohlstrukturiert“ sein.In diesem Unterkapitel wird eine Element beschrieben, mit dem Aktionen statisch nochmals zusammengefasst werden können. Diese Zusammenfassung hat auch Einfluss auf das dynamische Verhalten von Verarbeitungsobjekten (Variable).

Inhalt:1. Die Idee2. Notation3. Formale Parameter4. Aufruf5. Beispiel: Ein einfacher Block6. Eigenschaften7. Beispiel: Seiteneffekte8. Vorzeitiges Verlassen9. Goldene Regeln

148

5.5.1 Die Idee

Idee:Eine Zusammenfassung von Aktionen bekommt einen Namen und kann durch das Nennen des Namens (Aufruf) aktiviert werden. In einen Block sollen Daten formal hinein und herausgelangen Ein Block soll eigenen Daten besitzen

Vorteile: Gliederung des Algorithmus‘ durch hierarchische Dekomposition

(„Divide et impera: Teile und herrsche“) Wiederverwendbarkeit durch mehrfachen Aufruf statt durch mehrfaches notieren.

universeller ( Anzahl muss nicht bekannt sein) fehlerunanfälliger

Kapselung unwichtiger Details („information Hiding“) Vorteile bei der Organisation von Programmiertätigkeit durch Verteilbarkeit der

Aufgaben.

149

5.5.2 Notation

Ein Block ist die Zusammenfassung von Aktionen und wird wie folgt beschrieben:

Pseudocode:blockname (IN: x1:Type1, … ; OUT: y1:Type2, … ; THROUGH: z1:Type3, … ){ var w1:Type41; w2:Type42; … ; A;}

blockname ist der Name des Blockes xi,yi,zi heißen formale Parameter und sind typisiert wi heißen lokale Variable A ist eine Menge von Aktionen.

Blöcke werden in vielen Sprachen als Funktion (nur ein OUT-Parameter) bzw. Prozeduren umgesetzt oft steht der Block-Bezeichner selbst für einen OUT-Parameter (und wird daher auch

oft mit einem Typ versehen. (Bsp ?)

blockname

blockname

Flussdiagramm

Struktogramm

150

5.5.3 Formale Parameter

IN-Parameter (Eingabeparameter) sind Parameter, die an den Block übergeben werden Dazu werden beim Aufruf des Blockes an die Stelle der Eingabeparameter

Variable, Literale oder Ausdrücke (Berechnungen) notiert. Diese werden beim Aufruf zu Werten transformiert, die an den entsprechenden Variablen zugewiesen werden.(call by value)

OUT-Parameter (Ausgabeparameter) sind Parameter, die aus dem Block durch Zuweisung an Variable zurückgegeben werden. Dazu werden beim Aufruf des Blockes an die Stelle der Ausgabeparameter

Variablen notiert, die nach dem Aufruf die zurückgegeben Werte beinhalten(call-by reference)

THROUGH-Parameter (Ein-/Ausgabeparameter) sind Parameter die Werte in den Block hinein und hinaus übermitteln. Eingabe wie bei IN-Parametern (aber: nur Angabe einer Variable) Rückgabe wie bei OUT-Parametern

151

5.5.4 Aufruf

Ein Block wird über seinen Namen aufgerufen Die Parameter werden als Argument übergeben:

IN-Parameter werden als Wert übergeben, können also Variablenbezeichner, Literale oder komplexe Ausdrücke aus Variablenbezeichner und Literalen sein

OUT- und THROUGH-Parameter werden „by reference“, meist durch einen Variablenbezeichner übergeben

Meist wird die Zuordnung der übergeben Variablen zu den formalen Parametern über die Reihenfolge implizit vorgegeben.In manchen Programmiersprachen … … kann das auch explizit, z.B. über eine Zuweisung erfolgen … kann die Anzahl der übergebenen Variablen kleiner der Anzahl der formalen

Parametern sein – dann werden die fehlenden Parameter von rechts nach links nicht übergeben

… können formale IN-Parameter mit einem Standardwert initialisiert werden. Die Zuordnung der übergebenen Parameter zu den formalen Parametern nennt

man Bindung.

152

5.5.4 Beispiel: Ein einfacher Block

Ein Block zur Berechnung von Summen (mit Aufrufzähler)summe (IN: value1 : Integer; value2 : Integer; OUT: result : Integer; THROUGH: counter : Integer; ){ var i : integer; // lokale Variable result = 0; // Initialisierung for i=1 to value2 // ein wenig umständlich value1 = value1 + 1; result = value1; counter = counter + 1;}

Aufrufanzahl = 0; // schon erste Summe hat zwei Summanden

initial = 5; summe(initial, 9, ergebnis, anzahl);

summe(ergebnis, 9, ergebnis, anzahl);ergebnis/anzahl >> Bildschirm; // Mittelwert

153

5.5.5 Eigenschaften

Jeder Block kann über einen Satz lokaler Variable verfügen, die außerhalb des Blockes nicht sichtbar sind Die Variablenbezeichner können also außerhalb ohne Einfluss auf den Block

verwendet werden Auch die in der Blockdefinition als formale Parameter verwendeten

Variablenbezeichner sind nur im Block sichtbar: Auch sie können außerhalb ohne Einfluss verwendet werden, Aber Vorsicht: die Veränderung von OUT und THROUGH-Parametern bewirkt

(oft) eine Veränderung der beim Aufruf verwendeten zugehörigen Parameter (der zugehörigen „gebundenen“ Parameter).

Variable, die in einem Block verwendet aber nicht deklariert werden, werden als „global“ angenommen

Viele Sprachen erlauben die Definition von Blöcken innerhalb von Blöcken Variablen, die in einem Block nicht deklariert sind, werden im umgebenden Block

vermutet.

154

5.5.6 Beispiel: Seiteneffekt

Das (ungewollte) implizite Verändern von „äußeren“ Parametern durch Veränderung „innerer“ Parameter nennt man „Seiteneffekt“

summe (THROUGH: value1 : Integer; value2 : Integer; result : Integer; ){ value1 = value1 + value2; result = value1;}

Aufrufx = 5; y = 7;summe (x,y,z);„Die Summe von „ >> Bildschirm;x >> Bildschirm;„und“ >> Bildschirm;y >> Bildschirm;„ ist „ >> Bildschirm;z >> Bildschirm;

Die Summe von12und7Ist12

155

5.5.7 Vorzeitiges Verlassen

Manchmal ist es sinnvoll, die Abarbeitung eines Blockes vorzeitig zu beenden Dies wird oft im Fehlerfall gemacht, wenn eine Weiterbearbeitung nicht mehr sinnvoll

erscheint - z.B. nach einer negativen Überprüfung der Eingabeparameter Flussdiagramm StruktogrammPseudocode

Beispiel: wurzel(IN: argument:real; OUT: result:real){ if (argument<0) return; // return already

here else result = sqrt(argument);}

Block Return;Block

156

5.5.8 Goldene Regeln

Namen so lokal wie möglich deklarieren Möglichst keine globalen Variablen verwenden

Wenn doch: Ganz wenige - nur eine (z.B. strukturiert) Auffällig kennzeichnen: z.B. global_error_handle

Nach Möglichkeit „call by value“ verwenden Wird nicht von allen Programmiersprachen unterstützt Probleme bei der Rückgabe umfangreicher Daten (wg. Umkopieren)

Blöcke sind so zu wählen dass: Der innere Zusammenhang stark ist Der äußere Zusammenhang schwach ist (minimale Schnittstellen, keine

Datenteilung , z.B. durch globale Variable)

157

5.6 Iteration und Rekursion

Im Bereich der Datenstrukturen haben wir es oft mit rekursiven Strukturen z.B. Bäumen zu tun. Auch in der Mathematik sind rekursive Definition weit verbreitet.und finden über zugehörige Algorithmen Einzug in die Informatik.Das Konzept der Rekursion wird in der Informatik allerdings teilweise mit Skepsis umgesetzt, führt es doch, in ungeeigneten Fällen, zu inakzeptablen Laufzeiten. Hinzu kommt, dass einige Programmier-spachen (z.B. FORTRAN) Rekursion nicht unterstützen.In diesem Unterkapitel soll auf die Möglichkeiten der Verwendung von Rekursion bzw. Iteration eingegangen werden

Inhalt1. Definition2. Beispiele3. Aufrufverwaltung4. Wo nicht5. Wo nicht und wo

158

5.6.1 Definition: Rekursion

Ein Objekt heißt rekursiv, wenn es sich selbst als Teil enthält oder mit Hilfe von sich selbst definiert ist. Wesentlich ist die Möglichkeit, unendliche Mengen von Objekten durch eine endliche

Aussage zu definieren. Bsp.: Definition natürlicher Zahlen:

0 sei eine natürliche Zahl Der Nachfolger (n+1) einer natürlichen Zahl ist wieder eine natürliche Zahl

Ein Algorithmus heißt rekursiv, wenn er sich selbst als einen seiner Aktionen (Verarbeitungsschritten) enthält. In der Regel enthält er sich mit „verkleinerter“ Aufgabenstellung. Damit er terminiert, muss er einen Zweig beinhalten, der einen (den) elementaren

Wert nicht rekursiv bestimmt. (den Basisfall) Objekte (Algorithmen), die andere Objekte (Algorithmen) enthalten, die wiederum die

ursprünglichen Objekte (Algorithmen) enthalten, heißen indirekt rekursiv

159

5.6.2 Beispiel: Fakultät

Mathematisch rekursive Definition: 1 n = 0

n ! = n x (n - 1) ! n > 0

Algorithmisch rekursive Definition:fakultaet (IN: n:integer, OUT: result:integer){ if (n == 0) then result = 1; else { fakultaet (n-1, result); result = n x result; }}

160

5.6.2 Beispiel: Hilbert Kurven

Die Hilbert Kurve ist eine stetige Kurve, die jeden beliebigen Punkt einer quadratischen Fläche erreichen kann, ohne sich zu schneiden – und damit ein Fläche beliebig dicht füllen kann. „D.Hilbert: Über stetige Abbildungen einer Linie auf ein Flächenstück, Math. Annalen, 1891“

Idee: Die Kurve wird aus vier Grundformen und vier Bildungsgesetzen generiert, die sich direkt und indirekt rekursiv aufrufen Grundformen:

Bildunggesetze: A: B A A CB: A B B DC: D C C AD: C D D B

Beispiel:

A B C D

wir müssen wissen,wir werden wissen

A

B

A A

C

t=1 t=2 t=3 t=3

161

5.6.2 Beispiel: Hilbert Kurven

A: B A A CB: A B B D

C: D C C AD: C D D B

A (IN: t:integer){ if (t>0) B(t-1); S(); A(t-1); O(); A(t-1); N(); C(t-1);}B (IN: t:integer){ if (t>0) A(t-1); O(); B(t-1); S(); B(t-1); W(); D(t-1);}C (IN: t:integer){ if (t>0) D(t-1); W(); C(t-1); N(); C(t-1); O(); A(t-1);}D (IN: t:integer){ if (t>0) C(t-1); N(); D(t-1); W(); D(t-1); S(); B(t-1);}

// S(), N(), W(), O() sind Blöcke, die eine// Linie nach Süden, Norden, Westen und Osten// zeichnen

A B C D

162

5.6.3 Aufrufverwaltung

Eine Aktivierung der Tiefe n wird erst verlassen, wenn die von ihr erzeugte Aktivierung der Tiefe n+1 schon verlassen wurde Verwaltung der Aktivierung als Stapel (Stack)

fakultaet(3,x)

fakultaet(2,x)

fakultaet(1,x)

fakultaet(0,x) result=1

result=1

result=2

result=6

163

5.6.4 Wo nicht: Modulo-Berechnung

Alle Grundrechenarten - und vergleichbar einfache mathematische Operationen - lassen sich mit Hilfe sog. „Primitiv Rekursiver Funktionen“ beschreiben (siehe Beispiel. „Algorithmenbeweis“)

a falls a < bmod(a,b) =

mod(a-b,b) falls a b

In gängiger mathematischer Notation könnte ein Verfahren zur Berechnung der Modulus-Funktion a mod b wie folgt aussehen:

modulo (IN a,b: integer, OUT result: integer){ if (a<b) result = a; else modulo (a-b,b,result);}

Offenbar einfacher ist: result = a - (a/b) x b

164

5.6.4 Wo nicht: Fibonacci-Zahlen

Fibonacci definiert im 13.Jahrhundert eine Zahlenfolge mit der die Verhältnisse des „goldenen Schnitts“ ebenso beschrieben werden können, wie die Populationsentwicklung in einem Kaninchenstall:

0 n = 0fib(n) = 1 n = 1

fib(n-2)+fib(n-1) n > 1 fib(IN: n:integer, OUT: result:integer)

{ r,s : integer; if (n==0) then result = 0 else if (n==1) then result = 1 else { fib(n-1,r); fib(n-2,s); result = r + s; }}

0112358

1321345589

144233

...

165

5.6.4 Wo nicht: Fibonacci-Zahlen

fib(IN: n:integer, OUT: result:integer){... fib(n-1,r); fib(n-2,s); result = r + s; ...}

n Aufrufe Rechenzeit (1 Aufruf = 1 nsec)0 1 n Zeit1 1 10 0,18 sec2 3 20 22 sec3 5 50 41 sec4 9 100 36000 Jahre5 156 25

Die Anzahl der Aufrufe verhält sich offenbar selbst ähnlichder Fibonacci-Reihe: Anzahl (n) = 2 x fib(n+1) - 1

Anstieg ist praktisch exponentiell also nicht verwendbar

0112358

1321345589

144233

...

166

5.6.4 Wo nicht: Fibonacci-Zahlen

Idee: Merken von zwei Folgewerten in Variablen und Aufsummieren in Schleife, wobei die Werte immer umgespeichert werden:

fib (IN: n:integer, OUT: result:integer){ a,b,z : integer; a = 0; b = 1; // fib0, fib1 while (n > 0) do { z = a + b; // Berechnung der nächsten fib a = b; b = z; // Umspeichern der fibs n = n - 1; // dicrease n } result = a; // das Resultat steht in a}

Anzahl (n) = n Zeit (n=100) = 1 sec (anstatt 36000 Jahre !)

0112358

1321345589

144233

...

167

5.6.5 Wo nicht und wo?

Man sollte überall dort auf Rekursion verzichten, wo es eine offensichtliche Lösung mit Iteration gibt. Jeder rekursive Algorithmus lässt sich in eine iterative Form umwandeln

(z.B. über explizites Ausformulieren einer Stackverwaltung) Es gibt allerdings einige Fälle, in denen Rekursion angewandt werden sollte:

Rekursion ist überall dort sinnvoll anwendbar, wo sich ein Problem in mehrere (oft: zwei) nicht überlappende Teilprobleme aufspalten lässt und sich die Teilprobleme leicht rekombinieren lassen.

Rekursion sollte dort verwendet werden, wo die zugrunde liegenden Datenstrukturen selbst rekursiver Art sind (z.B.: Bäume)

Für einige Probleme gibt es keine direkte Vorschrift zur Berechnung. Diese können oft nur durch „Trial and Error“ gelöst werden. Oft lassen sich diese Versuche (Trials) durch Untersuchung eines Teilproblems natürlich in rekursiver Form darstellen.Dieses Vorgehen nennt man „Backtracking“

168

5.6.6 Beispiel: Backtracking

Weg des Springers Gegeben sei ein n x n Spielbrett (z.B. n=8). Ein Springer - der nach den

Schachregeln bewegt werden darf - wird auf das Feld mit der Anfangskoordinate (x0,y0) gestellt (z.B. (1,1)).

Zu finden ist ein Weg des Springers, der genau einmal über jedes der Felder des Schachbrettes führt.

169

5.6.6 Beispiel: Backtracking

Ansatz eines Algorithmus (in unvollständiger Notation)

track (IN: kandidat, OUT: erfolgreich) // ohne Typ{ trage_ein(kandidat); // erst mal eintragen erfolgreich = false; // Initialisierung if (fertig) then erfolgreich = true; // Abbruchfall

else // weitersuchen {

repeat { wähleKandidat(neukandidat); // wie auch immer if (neukandidat) then // es geht weiter track (neukandidat, erfolgreich) // Rekusion else // Sackgasse ! trage_aus (kandidat); // wieder austragen

} until (erfolgreich) or (not neukandidat) }}

170

5.7 Zusammenfassung des Kapitels

1. Ein Beispiel Drei Algorithmen im Vergleich zur Lösung einer quadratischen Gleichung

2. Definition des Algorithmenbegriffes Definition und dessen Anwendung im Beispiel. Weitere Prinzipien und der

Zusammenhang von Algorithmen und Programmen.

3. Strukturelemente: Die „atomaren“ Elemente und die Konstruktionselemente Folge, Auswahl,

Wiederholung

4. Strukturierung Der Begriff des Control Flows, das Problem der Strukturierung mit Sprung und

Blockung

5. Blockung Prinzip und Beispiele, Probleme und Regeln

6. Iteration und Rekursion Definition, Realisierung, wo und wo nicht

171

Beispielklausur

In diesem Kapitel wird ein Beispiel für eine Klausur vorgestellt. Dabei sind jeweils die Aufgaben und die Lösungen gegeben.

Beachten Sie Diese Beispielklausur erhebt weder in Form, Inhalt noch Umfang einen Anspruch auf

Vollständigkeit.- dies betrifft insbesondere reine Wissensfragen, die hier etwas vernachlässigt sind.

Grundsätzlich ist der gesamte in der Vorlesung und den Übungen behandelte Stoff möglicher Gegenstand der Prüfung

Vorbereitung Arbeiten Sie die gesamten Folien nochmals durch Bearbeiten Sie alle Übungsaufgaben nochmals Arbeiten Sie das Skript von Herrn Geise durch Bearbeiten Sie dessen ÜbungsaufgabenBedenken Sie: In der Klausur sind keine Hilfsmittel zugelassen.

… daran will ich euch prüfen1. Mose 42.15

172

Informatik

Informatik ist ...

Geben Sie für jede dieser 5 „Kernprozesse“ der Informatik jeweils 3 Beispiele an

Die Wissenschaft, die sich mit dem(automatisierten)

von Information befasst

Erfassen

Transportieren

Speichern

Verarbeiten

Umsetzen

173

Informatik

Fehlt in dieser Beispielklausur:a) weitere Wissensfragenb) ...

174

Information

Eine Nachrichtenquelle sendet Zeichen aus dem AlphabetX = {a,b,c,d,e} mit den Wahrscheinlichkeiten p(a)=1/2, p(b)=p(c)=p(d)=p(e)=1/8

a) Wie groß ist der Informationsgehalt der einzelnen Zeichenb) Wie groß ist der Informationsgehalt der Nachricht „abc“c) Wie groß ist der mittlere Informationsgehalt einer Nachricht mit 1000 Zeichend) Finden Sie einen möglichst optimalen Code für dieses Alphabete) Angenommen die Wahrscheinlichkeiten wären

p(b)=1/2, p(a)=p(c)=p(d)=p(e)=1/8 .Wie groß wäre dann die Redundanz Ihres Codes aus Aufgabe d) bzgl. der neuen Wahrscheinlichkeiten

Hamminga) Codieren Sie die Binärzahl 1000 mit der Hamming-Methodeb) Wieviele Bits können als fehlerhaft erkannt werden ?c) Wieviele Bits können korrigiert werden ?

175

Information

Fehlt in dieser Beispielklausur:a) „Textaufgaben“b) Turing-Maschinenc) …

176

Zahlensysteme

Stellen Sie die Dezimalzahl 7,25a) Binärb) Hexadezimalc) Oktal

dar Berechnen Sie im Binärsystem (mit Vollständiger Rechnung)

a) 1100100 : 101b) Machen Sie schriftlich die Gegenprobe (auch im Binärsystem)c) 10111 – 1010 (durch Addition des Zweierkomplements)

177

Zahlensysteme

Fehlt in dieser Beispielklausur:a) Gleitpunktzahlenb) IEEE 754c) ...

178

Datenstrukturen

Gegeben ist folgender Algorithmus:x : *Integer; y : Integer;x = &y;x* = 2;x = 2;x* = 5;

a) Gehen Sie davon aus, dass der Compiler der Variablen x die Speicherstelle 4 und der Variablen y die Speicherstelle 6 zugeordnet hat. Jede Variable belegt dabei genau eine Speicherstelle:Zeichnen Sie die Werte in den Speicherstellen 1 bis 8 jeweils nach den Zuweisungen.

179

Datenstrukturen

Fehlt in dieser Beispielklausur:a) Wissensfragen (z.B. Überblick über Datenstrukturen)b) spezielle Datenstrukturen (z.B. Variantenrecord)c) ...

180

Algorithmus + Theorie

Gegeben ist folgender Algorithmus:x=a, y=5;while (x>0){

y = y+1; x = x-1;

}a) Formen sie die while Schleife in eine repeat-Schleife umb) Bilden Sie die Funktion dieses Algorithmus‘ ohne Schleifen, mit Hilfe von Sprüngen und Marken

nach

181

Algorithmus + Theorie

Gegeben ist folgender Algorithmus test ( IN: x:Integer; THROUGH: y:Integer; b:Integer; OUT: z:Integer; ) {

z = 5; x = y + b;

b = y + x; } c = 3; d = 5; e = 7; f = 9; test (f,e,c,d); c >> Bildschirm; d >> Bildschirm; e >> Bildschirm; f >> Bildschirm;;

a) Geben Sie die Bildschirmausgabe an

182

Algorithmus + Theorie

Fehlt in dieser Beispielklausur:a) Weitere Umformungenb) Umwandlung Rekursion/Iterationc) Wissensfragen (z.B. Überblick über Strukturierungselemente)d) weitere Notationen (Nassi-Shneidermann, Flußdiagramm)e) ...

183

Lösung: Informatik

Information erfassen über: Kamera, Tastatur, Maus, Datenleitung, Tastsensoren, Gehirnsensoren, ...

Information Transportieren über Ethernet: WLAN, ISDN, S/ADSL, Datenbus, Druckerkabel, VGA-Kabel, verschränkte

Quantenzustände, ... Information speichern auf:

Festplatte, EPROM, RAM, ROM, CD, DVD, Tape, Tesa-Film, ... Information verarbeiten mit:

Analogrechner/Digitalrechner, Parallelrechner, CPU, FPU, Mikro-Prozessor, Turing-Maschine, ...

Information umsetzen als: Ausgabe auf dem Bildschirm, Drucker, Braille-Zeile, Roboter-Aktion,

Schalten, optisches/akustisches Signal, Raketenstart, ...

184

Lösung: Information

Eine Nachrichtenquelle sendet Zeichen aus dem AlphabetX = {a,b,c,d,e} mit den Wahrscheinlichkeiten p(a)=1/2, p(b)=p(c)=p(d)=p(e)=1/8

a) h(a) = -ld(1/2) = 1bit. h(b)=h(c)=h(d)=h(e)=-ld(1/8)=3bitb) 1bit + 3bit + 3bit = 7 bitc) 1000 x Mittlerer Informationsgehalt: H(x)=p(xi)h(xi) =

1000 x ( 1/2x1 + 1/8x3 + 1/8x3 + 1/8x3 + 1/8x3 )bit = 1000 x 2bit = 2000 bitd) Nach Huffmann: p(de)=1/4, p(bc)=1/4, p(debc)=1/2, p(a)=1/2). p(abcde)=1

also z.B.: a=1, b=000, c=001, d=010, e=011e) Redundanz = L(x)-H

l(a)=1bit , l(b)=l(c)=l(d)=l(e)=3bit (entsprechend der Codierung in d.)L(x) = p(xi)l(xi) = (0,125x1 + 0,5x3 + 0,125x3 + 0,125x3 + 0,125x3)bit = 2,75 bith(b) = 1bit, h(a)=h(c)=h(d)=h(e)=-ld(1/8)=3bit H(x) = p(xi)h(xi) = (0,5x1 + 0,125x3 + 0,125x3 + 0,125x3 + 0,125x3 )bit = 2 bitRedundanz = L(x)-H = 2,75bit – 2bit = 0.75 bit

Hamminga) 100P0PP (Relevant: Bit 3,5,7) 100P0P1 (even Parity: also 1 ergänzen)

100P0P1 (Relevant: Bit 3,6,7) 100P011 (even Parity: also 1 ergänzen)100P011 (Relevant: Bit 5,6,7) 1001011 (even Parity: also 1 ergänzen)

b) Der Hamming-Abstand D ist 3bit, es können D-1 = 2bit Fehler erkannt werdenc) Es können (D-1)/2 = 1bit Fehler korrigiert werden.

185

Dezimalzahl 7,25a) Vorkommateil: Nachkommateil

7 : 2 = 3 Rest: 1 2 · 0,25 = 0,5 --> Ziffer: 03 : 2 = 1 Rest: 1 2 · 0,5 = 1 --> Ziffer: 1 1 : 2 = 0 Rest: 1 -> 111 ->0,01Binärzahl: 111.01

b) 0111,01002 = 7,416 (7 * 160 + 4 * 16-1)c) 111,0102 = 7,28 (7 * 80 + 2 * 8-1)

Berechnung 1100100 : 101 = 10100 10100 x 101

101 10100--- 00000 101 10100 101 ------- --- 1100100 000

10111 – 101010111 - 01010 auf gleiche Längen bringen10111 + 10110 Binärkomplement 10101+ 1= 101101 Lösung: 1101 Überlauf weggelassen

Lösung: Zahlensysteme

186

Lösung: Datenstrukturen

Doppelt verkettete Listea) Person : record

{ vorname : array[1..64] of char; nachname: array[1..64] of char; prev : *Person; next : *Person; }

b) Man kann aus diesen Strukturen beliebig lange Ketten von Personen bildenc) Pro: Dynamisch: Verwaltung von Objekten, deren Anzahl zur Entwicklungszeit nicht

bekannt ist. Speicherverbrauch nur für die Objekte, die tatsächlich zur Laufzeit existieren.Pro Statisch: Einfach in der Realisierung, schnell in der Bearbeitung (Fehlerunanfälliger)

d) Person : record{ vorname : array[1..64] of char; nachname: array[1..64] of char;}Personenliste: array[1...65534] of Person;

187

Lösung: Datenstrukturen

x : *Integer;y : Integer;

x = &y;x* = 2;x = 2;x* = 5;

6

6

2

2

nd

2

2

25

x y

188

Lösung: Algorithmus + Theorie

Umformung der while-Schleife:a) Als repeat-Schleife:

x=a; y=5;if (x>0){ repeat do { { y = y+1; y = y+1; x = x–1; x = x-1; } until (x<=0) } while (x>0}}

b) Sprünge und Marken x=a; y=5; x=a; y=5; 1: if (x<=0) goto 2 1: if (x>0) y = y+1; { x = x–1; y = y+1; goto 1; x = x–1; 2: ... goto 1

}2: ...

189

Lösung: Algorithmus + Theorie

x=a; y=5; a x y Invariant:while (x>0) 4 4 5 5 + a = x + y{ ---------- ------------- y = y+1; 4 3 6 5 + a = x + y x = x-1; 4 2 7 5 + a = x + y} 4 1 8 5 + a = x + y

4 0 9 5 + a = x + y-------------

Nachbed.: y = 5 + a { aN+ a>0 }

x = a; y = 5;{ x=a, y=5, a>0 } { 5+a=x+y, x≥0 }while (x>0) { { 5+a=x+y, x≥0, x>0 } { 5+a=x+y+1-1, x>0 } y = y+1; { 5+a=x+y-1, x>0 } { 5+a=x-1+1+y-1, x-1+1>0 } x = x-1; { 5+a=x+1+y-1, x+1>0 } { 5+a=x+y, x≥0 } }{ 5+a=x+y, x≥0, x≤0 } { 5+a=x+y, x=0 } 5 + a = y

190

Lösung: Algorithmus + Theorie

Gegeben ist folgender Algorithmus test ( IN: x:Integer; THROUGH: y:Integer; b:Integer; OUT: z:Integer; ) {

z = 5; x = y + b; b = y + x;

} c = 3; d = 5; e = 7; f = 9; test (f,e,c,d); c >> Bildschirm; d >> Bildschirm; e >> Bildschirm; f >> Bildschirm;

Rechnung:(ROT = call by reference)c d e f3 5 7 9b z y x test(f,e,c,d)3 5 7 93 5 7 10 x = y + b

17 5 7 10 b = y + x

Ausgabe:17579