Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- j11:codierung:start [2023/06/11 15:44] – angelegt Martin Pabst
+++ j11:codierung:start [2023/06/13 07:15] (aktuell) – Martin Pabst
@@ Zeile 1: / Zeile 1: @@
-====== Codierung ======
+====== Codierung natürlicher Zahlen ======
-===== Darstellung einer Zahl in verschiedenen Zahlensystemen =====
+===== Darstellung einer Zahl in verschiedenen Stellenwertsystemen =====
+<WRAP center round info 80%>
+**Stellenwertsystem**
+Ein **Stellenwertsystem** ermöglicht die eindeutige Darstellung jeder natürlichen Zahl unter Verwendung einer begrenzten Menge von **Zahlzeichen**. Das Stellenwertsystem zur **Basis** $b$ besitzt $b$ verschiedene Zahlzeichen. Da sich jede natürliche Zahl $n\in\mathbb{N}$ schreiben lässt als
+$$n = a_0\cdot b^0 + a_1\cdot b^1 + a_2\cdot b^2 + \ldots + a_k\cdot b^k\ (k\in\mathbb{N}),$$
+wobei die Koeffizienten $a_0, a_1, \ldots, a_k$ jeweils aus der Menge ${0, 1, \ldots, b - 1}$ stammen. Jeder Koeffizient lässt sich daher eindeutig durch eines der $b$ Zahlzeichen darstellen und die Zahl $n$ durch Hintereinanderschreiben der den Koeffizienten $a_k, a_{ k-1 }, ..., a_0$ zugeordneten Zahlzeichen. \\
+Das alles ist auf den ersten Blick sicher etwas abstrakt, es wird aber klar, wenn wir es am uns am Stellenwertsystem zur Basis $10$, dem uns vertrauten Zehnersystem, veranschaulichen:
+ \\ \\
+**Zehnersystem** \\
+Das Zehnersystem hat die Basis $b = 10$ und die Zahlzeichen $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$. Jede natürliche Zahl $n\in\mathbb{N}$ lässt sich darstellen als Summe
+$$n = a_0\cdot10^0 + a_1\cdot10^1 + a_2\cdot10^2 + \ldots + a_k\cdot10^k\ (k\in\mathbb{N})$$
+Zur Angabe von $n$ reicht es also, die Koeffizienten $a_0, a_1, \ldots, a_k$ anzugeben. Man schreibt sie einfach direkt hintereinander auf.
+{{ :j11:codierung:pasted:20230613-082016.png}}
+\\ **Beispiel:**\\
+Die Anzahl $n$ der blauen Punkte rechts lässt sich schreiben als
+$$n = 5\cdot10^0 + 3\cdot10^1$$
+Wir nehmen daher das 6. und das 4. Zahlzeichen und schreiben sie (beginnend mit dem höherwertigsten) hintereinander an. So gelangen wir zur Darstellung "$35$" für diese Zahl. \\ \\
+**Hexadezimalsystem** \\
+Stell dir vor, wir wären mit insgesamt sechzehn Fingern (acht an jeder Hand) auf die Welt gekommen! Dann würden wir unsere Zahlen in einem Stellenwertsystem mit sechzehn Zahlzeichen darstellen. Es ist üblich, dazu die zehn uns bekannten Zahlzeichen mit den ersten sechs Buchstaben zu ergänzen: $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F$. Die Basis dieses Stellenwertsystems ist natürlich 16. Zur Darstellung einer Zahl $n\in\mathbb{N}$ schreiben wir sie als Summe
+$$n = a_0\cdot 16^0 + a_1\cdot 16^1 + a_2\cdot 16^2 + \ldots + a_k\cdot 16^k\ (k\in\mathbb{N})$$
+{{ :j11:codierung:pasted:20230613-085008.png}}
+**Beispiel:** \\
+Die Anzahl der roten Kreise im Bild rechts lässt sich schreiben als
+$$13\cdot 16^0 + 2\cdot 16^1$$
+Entsprechend verwenden wir zur Darstellung das 14. und das 3. Zahlzeichen: "2D". Du wirst Dich jetzt fragen, wie man auf die Koeffizienten 13 und 2 kommt. Um ehrlich zu sein merke ich mir einfach die Wertigkeiten der Stellen auswendig: $1, 16, 256, 4096, \ldots$. Dann beginne ich mit der höchsten Wertigkeit, die in die Zahl reinpasst ($16$), dividiere sie ($45\ :\ 16 = 2) und habe schon den ersten Koeffizienten. Es bleiben $45 - 2\cdot 16 = 13$ übrig.
+ \\ \\
+**Binärsystem** \\
+verschiedene Zahlzeichen sind aufs Erste recht unhandlich (obgleich das in der Informatik sehr vorteilhaft ist, dazu später mehr). Versuchen wir es daher mal mit einer möglichst kleinen Basis. Die Zahl 1 lässt sich nicht verwenden (überlege selbst, warum!), aber mit $b = 2$ funktioniert es schon! Wir brauchen in diesem Fall nur zwei Zahlzeichen $0$ und $1$. Die Wertigkeiten der Stellen sind $2^0, 2^1, 2^2, \ldots$, also $1, 2, 4, 8, 16, 32, \ldots$.
+ \\ \\
+**Beispiel:** \\
+Wir wollen die Zahl der blauen Kreise oben ("25" im Zehnersystem) im Zweiersystem darstellen. Beginnen wir mit der niedrigsten Wertigkeit, die reinpasst ($16$):
+$$25 = 1\cdot 16 + 9$$
+$$9 = 1\cdot 8 + 1$$
+$$1 = 0\cdot 4 + 1$$
+$$1 = 0\cdot 2 + 1$$
+$$1 = 1\cdot 1 + 1$$
+Wir gelangen so zur Summe
+$$25 = 1\cdot 2^0 + 0\cdot 2^1 + 0\cdot 2^2 + 1\cdot 2^3 + 1\cdot 2^4$$
+und damit zur Darstellung "11001" der Zahl im Binärsystem.
+</WRAP>
+TODO: Übungen, Algorithmus mit Modulo-Operator
+<HTML>
+<div class="java-online" style="height: 70vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'Zahlensysteme_1'}">
+<script type="text/plain" title="Zahlensysteme.java">
+NumberSystemConverter nsc = new NumberSystemConverter();
+println(nsc.toDec(12753));
+println(nsc.toBinary(11));
+println(nsc.toHex(49152));
+println(nsc.parseHex("3B"));
+class NumberSystemConverter {
+   private String hexDigits = "0123456789ABCDEF";
+   private String decimalDigits = "0123456789";
+   public String toDec(int number) {
+      String decimalText = "";
+      while (number > 0) {
+         int digit = number % 10;
+         decimalText = decimalDigits.charAt(digit) + decimalText;
+         number = number / 10;
+      }
+      return decimalText;
+   }
+   public String toBinary(int number) {
+      String binaryText = "";
+      while (number > 0) {
+         int digit = number % 2;
+         if(digit == 0) {   // oder if(number & 1 == 0)
+            binaryText = "0" + binaryText;
+         } else {
+            binaryText = "1" + binaryText;
+         }
+         number = number / 2;   // oder number == number >> 1
+      }
+      return binaryText;
+   }
+   public String toHex(int number) {
+      String hexText = "";
+      while (number > 0) {
+         int hexDigit = number % 16;
+         hexText = hexDigits.charAt(hexDigit) + hexText;
+         number = number / 16;   // oder number == number >> 1
+      }
+      return hexText;
+   }
+   public int parseHex(String zahlAlsString) {
+      int wertigkeit = 1;
+      int zahl = 0;
+      for (int position = zahlAlsString.length() - 1; position >= 0; position--) {
+         char zahlzeichen = zahlAlsString.toUpperCase().charAt(position);
+         int zahlzeichenIndex = hexDigits.indexOf(zahlzeichen);
+         zahl = zahl + zahlzeichenIndex * wertigkeit;
+         wertigkeit = wertigkeit * 16;
+      }
+      return zahl;
+   }
+}
+</script>
+</div>
+</HTML>