Lesson Learned

In diesem Kapitel geht es darum folgende Dinge zu verstehen und zu können

• Information
  • Definition
  • Zusammenhang zur Informatik
• Zahlensysteme
  • Dezimal-, Binär, Hexadezimalsystem
  • Umrechnungen zwischen diesen Zahlensystemen

Daten

Unter Daten versteht man im Allgemeinen Angaben, (Zahlen-)Werte oder formulierbare Befunde, die durch Messung, Beobachtung u. a. gewonnen wurden. [1] […] Für die Datenverarbeitung und (Wirtschafts-)Informatik werden Daten als Zeichen (oder Symbole) definiert, die Informationen darstellen und die dem Zweck der Verarbeitung dienen. [2] Wikipedia, 2018

[1] Daten. In: Duden (online)
[2] Heinz-Peter Gumm, Manfred Sommer: Einführung in die Informatik. 10. Auflage. Oldenbourg Verlag, ISBN 978-3-486-70641-3, S. 4 f.

Daten vs Information

• Daten haben keinen Kontext
• Durch Kombination verschiedener Daten lässt sich Kontext schaffen

Beispiel:

• Datum1: Klausuraufgabe Mathe 3 Klasse
• Datum2: 17+4
• Datum3: = 15

<span class=‘fragment color-red’

**Informationen können falsch sein, Daten nicht!** 

Zahlen - Ein Beispiel

Herr Ober, Zahlen, bitte!

Zahlensysteme

Quelle: https://xkcd.com/953/

Zahlensysteme

Grundlegende Grundlagen

Ein Beispiel $73_{10}$

Es soll die Zahl $73_{10}$ näher betrachtet werden.

Informelle Zerlegung der Zahl

• 7 Zehner, 3 Einer

Ein wenig formeller:

• $ n_B={\color{#00b1ac}B}^0 \cdot {\color{#0070C0}{d_0}}+{\color{#00b1ac}B}^1 \cdot {\color{#0070C0}{d_1}} $
• $ {\color{#00b1ac}B} = 10 $
• $ {\color{#0070C0}{d}} = {\color{#0070C0}{d_0}} = 3, {\color{#0070C0}{d_1}} = 7 $
• $ 73 = {\color{#00b1ac} {10} }^0 \cdot {\color{#0070C0}{3}} + {\color{#00b1ac} {10} }^1 \cdot {\color{#0070C0}{7}} $
• Damit ist $ {\color{red}{r}} = 1 $

Zahlensysteme

Zahlensysteme

There are 10 types of people in the world:
Those who understand binary and those who don‘t!

Quelle: https://www.schoeller.de/media/2157/ten-for-two-slider.png

Binäres Gedankenlesen

Binary Sudoku

Quelle: https://xkcd.com/74/

Wer benutzt was?

Binary vs. Hex

The Return of the Bin

The 10 Towers – Variante 1

Aufsummieren der Potenzen:$73_{10} = ???_{2}$

The 10 Towers – Variante 2

Rückwärts Hornerschema:$73_{10} = ???_{2}$

Übungen

Übungen

Lesson Learned

In diesem Kapitel geht es darum folgende Dinge zu verstehen und zu können

• Zahlendarstellungen
  • Darstellung ganzer Zahlen
  • Darstellung von und Rechnen mit negativen ganzen Zahlen
  • Darstellung von und Rechnen mit Gleitkommazahlen
• Einfache Codes
  • Darstellung von Ziffern und Zeichen im Rechner
  • Gängige Standards

Warum denn so negativ?

Positive ganze Zahlen lassen sich in einem Computer sehr einfach im Binärsystem darstellen, aber …

<span class=‘fragment color-red’

Wie lassen sich negative ganze Zahlen in einem Computer darstellen?

Wie macht JAVA das?

$: java -jar negativeNumbers.jar
Where to start?
-4
Where to end?
4
1111 1111 1111 1111 1111 1111 1111 1100
1111 1111 1111 1111 1111 1111 1111 1101
1111 1111 1111 1111 1111 1111 1111 1110
1111 1111 1111 1111 1111 1111 1111 1111
0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0001
0000 0000 0000 0000 0000 0000 0000 0010
0000 0000 0000 0000 0000 0000 0000 0011
0000 0000 0000 0000 0000 0000 0000 0100

2-Komplement

2-Komplement

Das 2-Komplement kann wie folgt grafisch dargestellt werden

2-Komplement

2-Komplement

Zwischenergebniss

• Ganze Zahlen ✓
• Negative Zahlen ✓
• Kommazahlen ?

Kommazahlen - Übersicht

Kommazahlen - Festkommazahlen

Umwandlung in eine Festkommazahl

Die Umwandlung besteht aus 3 Schritten:

1. Umwandlung des ganzzahligen Anteils
2. Umwandlung der Nachkommastellen
3. Addition der beiden Ergebnisse

Beispiel

Umwandelung von 73,4

1. $73_{10} = 1001001_{2}$ (siehe vorheriges Kapitel)
2. Anwenden der Multiplikationsmethode:
   1.  $ 0,4 \cdot 2 = 0,8 \longrightarrow 0 (erstes Bit) $
   2.  $ 0,8 \cdot 2 = 1,6 \longrightarrow 1 $
   3.  $ 0,6 \cdot 2 = 1,2 \longrightarrow 1 $
   4.  $ 0,2 \cdot 2 = 0,4 \longrightarrow 0 $
   5.  $ 0,4 \cdot 2 = 0,8 \longrightarrow 0 $
   6. Periode gefunden ⇒ Abbruch
3. Addition: $1001001,\overline{0110}$

Gleitkommazahlen (IEEE 754)

$$ x=s \cdot m \cdot 2^e $$ $$ s = (-1) ^{\color{#00b1ac}S} $$ $$ e = {\color{#0070C0}E}-b $$ $$ m = 1,{\color{red}{M}} $$

Einfache Genauigkeit (float)

• Der Exponent kann Werte von -126 bis +127 annehmen
  • Die Werte -127 und +128 sind für Spezialfälle reserviert
• Der Biaswert b ist 127

Einfache Genauigkeit (double)

• Der Exponent kann Werte von -1022 bis + 1023 annehmen
  • Die Werte -1023 und + 1024 sind für Spezialfälle reserviert
• Der Biaswert b ist 1023

Beispiel

1. Umwandlung der Dezimalzahl (hier 73,5) in eine binäre Festkommazahl ohne Vorzeichen $$ 73.5_{10} = 1001001.1_2 $$

2. Normalisieren und Bestimmen des Exponente

$$ 1001001.1_2 \cdot 2^{0} = 1.0010011_2 \cdot 2^{6} $$

$$ {\color{red}M} = 00100110000000000000000_{2} $$ $$ {\color{#0070C0}E} = 6 + 127 = 110_2 + 1111111_2 = 10000101_2 $$

1. Vorzeichen-Bit bestimmen $ {\color{#00b1ac}S}=0 $

2. Gleitkommazahl zusammensetzen (float) $$ {\color{#00b1ac}0}{\color{#0070C0}{1000010 1}}{\color{red}{0010011 00000000 00000000}} $$

Spezialfälle

Anmerkung

• r ist die Anzahl der Exponenten-Bits

Beispiel – Addition

Es seien zwei Gleitkommazahlen a und b gegeben

• a = |0|10000001|(1)10010000000000000000000
• b = |0|01111111|(1)10110001000100000000000

Die Zahl b ist kleiner und muss daher umgerechnet werden

• b = |0|10000001|(0)01101100010001000000000

Addition

• a + b = |0|10000001|(1)11111100010001000000000

Bezug zur Programmiersprache

Übung

Übung

AsciiTabelle

Emoji Keyboard

Unicode

Unicode ist ein Zeichensatz mit 32 Bits, der als weltweiter Standard geplant ist

• Aufbau des Codes
  • 32-Bit Codierung mit fester Länge
  • Maximal 4.294.967.296 Zeichen darstellbar
  • Notation im Hexadezimalsystem U+(XX)XXXXXX
  • Dabei geben die letzten 2 Byte eine Position in einer Plane (Ebene) an
  • Die Angabe der Plane ist dabei optional (Standard = 00)

Basic Multilingual Plane

• Das erste Byte adressiert den Block innerhalb der Plane, das zweite Byte ein Zeichen innerhalb des Blocks

UTF - Unicode Transformation Format

Um die Unicode-Zeichen im Rechner zur Weiterverarbeitung darstellen zu können gibt es die UTF-Codierung

Es gibt mehrere UTF-Standards

• UTF-32: je Zeichen 4 Bytes (32 Bit)
  • feste Länge, einfache Codierung, hoher Speicherbedarf
• UTF-16: je Zeichen 2 oder 4 Bytes (16 – 32 Bit)
  • Variable Länge, hoher Speicherbedarf
• UTF-8: je Zeichen 1 bis 4 Byte (8 – 32 Bit)
  • Variable Länge, niedriger Speicherbedarf

UTF8

UTF-8 ist dazu geeignet, den Speicherplatz eines Zeichens den Anforderungen anzupassen

• Handelt es sich bei einem Zeichen um ein ASCII-Zeichen wird ein Byte zur Codierung benötig

  • (0 – 127) → 0xxx xxx

• Handelt es sich um ein anderes Zeichen werden 2 bis 4 Bytes zur Codierung benötigt

  • Das erste Byte beginnt mit einer Anzahl von Einsen, die der Anzahl von zu verwendenden Bytes entspricht, gefolgt von einer 0
  • Jedes folgende Byte beginnt mit 10

UTF-8

Beispiel

Es soll der Unicode U+265E (♞) in UTF-8 dargestellt werden:

• U+265E benötigt selbst 14 Bits, also müssen zur UTF-8 Codierung 3
• Bytes verwendet werden
  • Grundgerüst für 3 Byte UTF-8 Codierung:
  • 1110 xxxx | 10xx xxxx | 10xx xxxx
• Binäre Darstellung von U+265E:
  • 0010 0110 0101 1110
• Einsetzen in das Grundgerüst ergibt:
  • 1110 0010 | 1001 1001 | 1001 1110

UTF8 - Übung

UTF8 - Übung

Lesson Learned

In diesem Kapitel geht es darum folgende Dinge zu verstehen und zu können

• Aufbau von gängigen Dateiformaten
  • Binäre Dateiformate
  • Textbasierte Dateiformate

Überblick

Grundsätzlich lassen sich Dateien in 4 Kategorien einteilen:

Programme

Dateien die Maschienencode enthalten werden Programme genannt.

• Entstehen durch compilieren von Quellcode
• Beispiele:
  • C/C++
  • go
  • RUST
  • Fortran
• Es wird kein weiteres Programm benötigt um den Code auszuführen

Kennzeichnung im Dateisystem

Die Kennzeichnung von Dateien ist OS abhängig

• Linux, MacOS

  • In Unixoiden- Betriebsystemen werden Sie durch das Ausführungsrecht markiert

• Windows

  • Programme müssen die Endung .exe haben

Skripte

Dateien die Quellcode für einen Interpreter enthalten

• Programmanweisungen werden als Text (Zeichencodiert) abgespeichert
• Beispiele:
  • Bash
  • Python
  • Powershell
• Der Interpreter wird benötigt der die Anweisungen Zeilenweise umsetzt

Kennzeichnung im Dateisystem

• Linux, MacOS

  • In Unixoiden- Betriebsystemen werden Sie durch das Ausführungsrecht markiert
  • Interpreter steht in der Ersten Zeile hinter der Shebang !#

• Windows

  • Die Dateiendung muss dem Entsprechenden Interpreter zugeordnet werden
  • z.B.: .cmd,.bat -> Eingabeauforderung, .py -> Python

Binäre Daten

Daten werden Byteweise in eine Datei geschrieben

• Sind nur mit speziellen Programmen zu öffnen
• Nicht Menschenlesbar (Ohne Hilfsprogramm)
• Beispiele:
  • Datenbanken
  • Bilder (.bmp, jpeg, .png)
  • Altes Office-Formate (.xls,.doc)
  • generische .dat oder .bin Dateien
• Sehr performant

csv

Stunde,Montag,Dienstag,Mittwoch,Donnerstag,Freitag
1,Mathematik,Deutsch,Englisch,Mathematik,Kunst
2,Sport,Französisch,Geschichte,Sport,Geschichte
3,Sport,"Religion (ev, kath)",Kunst,,Kunst

Quelle: https://de.wikipedia.org/wiki/CSV_(Dateiformat)

CSV

• Vorteile

  • Einfach zu lesen
  • Gut geeignet für Datenaustausch

• Nachteile

  • keine Formatierungen

JSON

JSON = Java Script Object Notation

{
  "id": {
    "$oid": "5968dd23fc13ae04d9000001"
  },
  "product_name": "PowerBook 5 Ultra",
  "supplier": ["Von-Neumann Inc.","Moore Corp."],
  "quantity": 71,
  "unit_cost": "$1123.47"
}

JSON

• Vorteile:

  • Menschenlesbar
  • Typisiert (String,int,bool)
  • Parser für viele Programmiersprachen
  • Explizierte Formatierung

• Nachteile

  • Zeichencodiert (Mögliche Encoding Probleme)

XML

XML = Extensible Markup Language

<?xml version="1.0" encoding="UTF-8"?>
<note>
  <to>Tove</to>
  <from>Jani</from>
  <heading>Reminder</heading>
  <body>Don't forget me this weekend!</body>
</note>

Quelle: https://www.w3schools.com/xml/note.xml

XML

• Vorteile:

  • Menschenlesbar
  • Typisiert (erweiterbar)
  • Parser für viele Programmiersprachen
  • Explizierte Formatierung
  • Validierbar

• Nachteile

  • Viel Overhead
  • Langsamer Parser

YAML

YAML - YAML Ain’t Markup Language

invoice: 34843
date   : 2001-01-23
bill-to: &id001
    given  : Chris
    family : Dumars
    address:
        city    : Royal Oak
        postal  : 48046
ship-to: *id001
product:
    - sku         : BL394D
      description : Basketball
    - sku         : BL4438H
      description : Super Hoop
total: 4443.52

Quelle: http://yaml.org/start.html

YAML

• Vorteile:

  • Menschenlesbar
  • Typisiert
  • Parser für viele Programmiersprachen
  • JSON ist Sub-Standard

• Nachteile

  • Viel Overhead (Whitespaces)
  • Implizierte Formatierung (Fehleranfällig)

Lesson Learned

In diesem Kapitel geht es darum folgende Dinge zu verstehen und zu können

• Spezialisierte Codes
  • Motivation für spezielle Codierungen
  • Optimale Codes
  • Robuste Codes

Was ist ein Code überhaupt?

Ein anschauliches Beispiel

Ein anschauliches Beispiel

Was ist ein Code?

Matse ausbildung

<span class=‘fragment '

=Matse ausbildung

Technische Randbedingungen

Es kann technische Randbedingungen geben, die die Verwendung spezieller Codes nötig machen

• Möglichkeiten zur Optimierung
  • z.B. Binärcode auf dem Computer
• Ungenauigkeiten
  • z.B. Daten auf einer CD / DVD / Blu-ray
• Bestimmte Formate
  • z.B. QR-Code zur Erkennung mit Smartphones

Randbedingungen – Die CD

Technische Realisierung einer CD

• Eine CD hat eine reflektierende Oberfläche
  • Pits = (eingebrannte) Vertiefungen
  • Lands = Erhebungen

• Codierung
  • Pits & Lands = 0
  • Übergänge = 1

Randbedingungen – Die CD

Technische Randbedingungen

• Pits und Lands dürfen nicht zu lange werden und auch nicht zu kurz sein, da die genaue Anzahl sonst nicht korrekt ausgelesen werden kann
  • Es müssen mindestens 2 Nullen und höchsten 11 Nullen zwischen zwei Einsen folgen
  • 8-Bit-Codes sind nicht verwendbar
  • Stattdessen wird ein 14-Bit-Code benutzt (EFM)

Speicheroptimierung

Codes zur Speicheroptimierung komprimieren Daten

• Ziele der Kompression
  • Möglichst Kompakte Darstellung -Verlustfreie Codierung (nicht immer)
• Motivation
  • Codes mit fester Länge (z.B. ASCII) ineffizient

• Lösungsansatz
  • Kurzer Code für häufig vorkommende Zeichen
  • Langer Code für seltene Zeichen

Präfixfreiheit

Wenn Codes unterschiedliche Länge haben, müssen diese präfixfrei sein

• Kein Codewort ist der Anfang eines anderen Codewortes
• Beispiel für nicht-präfixfreie Codierung

Präfixfreiheit

Huffman-Code

Der Huffman-Code ist eine Variante eines präfixfreien Codes

Algorithmus:

1. Schreibe Symbole mit Wahrscheinlichkeiten als Wald
2. Fasse die beiden Bäume mit der geringsten Wahrscheinlichkeit und der geringsten Tiefe in einem neuen Baum zusammen

• Die Wahrscheinlichkeit für den neuen Zweig ergibt sich durch Addition

3. Wiederhole bis nur noch ein Baum existiert

Eigenschaften:

• Code möglicherweise für jeden Anwendungsfall anders
• Basiert auf den Auftrittswahrscheinlichkeiten eines Zeichens
• Die mittlere Codelänge wird minimiert

Huffman-Code

Übung

Codieren Sie das folgende Wort nach dem Huffmann-Code:
MISSISSIPPI

Mittlere Codelänge

Magic

Robuste Codierung

Manche Übertragungsmedien sind fehleranfällig

• Fehler müssen erkannt und im Optimalfall korrigiert werden können

• Lösungsvarianten

  • Mehrfache Übertragung der Daten
    • Sehr einfach zu realisieren
    • Es werden sehr viele Daten übertragen

• Prüfsummenverfahren -Es werden zusätzliche Informationen übertragen, die von den zu übertragenden Daten abhängig sind

Paritäten

Hamming-Code

Hamming-Code

Beispiel für $ N=7=2^3 -1 $

• 3 Paritätsbits $ p_i $ an Stellen 1, 2, 4 (2er-Potenzen)
• 4 Datenbits $ d_n $ an Stellen 3, 5, 6, 7

Hamming-Code

Die Bitmaske …

• … beginnt am entsprechenden Paritätsbit $ p_i $ und ergibt sich als Folge von $2^{i}$ Einsen, dann $2^{i}$ Nullen, dann wieder $2^{i}$ Einsen, usw.
• … gibt die Bits an, die an der Berechnung des jeweiligen Paritätsbits beteiligt sind

Hamming-Code

Beispiel für N = 7

• Die Paritätsbits werden mit einer XOR-Verknüpfung berechnet

Hamming-Code - Paritäten

Beispiel für N = 7

• Die Paritätsbits werden mit einer XOR-Verknüpfung berechnet

Hamming-Code

Fehlerfall 1 - Kein Fehler

Hamming-Code

Fehlerfall 2 - Datenfehler

Hamming-Code

Fehlerfall 2 - Paritätsfehler