RNVS-Blatt-01

1. Rechnernetze und verteilte Systeme (H)

Note

In der Vorlesung haben wir die Begriffe Rechnernetz und verteiltes System kennen gelernt. Ein Rechnernetz ist immer die Voraussetzung für ein verteiltes System.

Ordnen Sie die folgenden Systeme als Rechnernetz oder als verteiltes System ein. Begründen Sie ihre Antwort kurz.

Hinweis: ein System kann – abhängig von der Sichtweise – durchaus sowohl ein Rechnernetz als auch ein verteiltes System sein.

(a) Das MWN (Münchner Wissenschaftsnetz)

• Rechnernetz:
  • keine gemeinsame Aufgabe
  • unabhängige Endgeräte voneinander

(b) Ein Messenger wie Signal, Threema oder WhatsApp

• Verteiltes System:
  • gemeinsame Aufgabe: Kommunikation
  • abhängig voneinander: Kommunikationsaustausch

(c) Das World Wide Web

• Verteiltes System:
  • gemeinsame Aufgabe: Informationsaustausch
  • abhängig voneinander: Informationsaustausch
• Rechnernetz:
  • keine gemeinsame Aufgabe: Internet hat im Grunde keinen “use-case”
  • alle Rechner unabhängig voneinander $⟹$ Das Internet ist beides

(d) Der SuperMUC-NG

• Verteiltes System:
  • gemeinsame Aufgabe: Berechnungen
  • abhängig voneinander: Rechenleistung entsteht durch Zusammenarbeit der einzelnen Rechner
• Eventuell auch rechnernetz
  • viele verschiedene verbundene Knoten

(e) Ihr eigenes Beispiel

• Instagram
  • verteiltes System
    • gemeinsame Aufgabe: Medienaustausch
    • Abhängigkeit alleine, da Medienaustausch nur im kollektiv funktioniert

Rechnernetz: Ein Rechnernetz ist eine Sammlung von Computern, Servern, Hauptrechnern oder anderen Geräten, die miteinander verbunden sind, um Ressourcen auszutauschen und Kommunikation zu ermöglichen. Die Verbindungen können über Kabel, Telefonleitungen, Funkwellen, Satelliten oder andere Übertragungsmedien erfolgen. Ein Rechnernetz ermöglicht den Austausch von Daten und Ressourcen zwischen den angeschlossenen Geräten.

Verteiltes System: Ein verteiltes System ist eine Gruppe von unabhängigen Computern, die dem Benutzer gegenüber als ein kohärentes System erscheinen. Diese Systeme arbeiten zusammen, um gemeinsame Ziele zu erreichen, und teilen sich dabei Ressourcen oder Aufgaben über ein Netzwerk. Verteilte Systeme sind darauf ausgelegt, Effizienz, Skalierbarkeit und Zuverlässigkeit zu verbessern, indem sie Aufgaben und Ressourcen über mehrere Knoten verteilen, die geografisch getrennt sein können.

2. Grundlagen (H)

Note

Zwei Gelehrte der Antike spielen gerne Schach miteinander. Weil sie nicht in der selben Stadt wohnen,teilen sie einander die Spielzüge über Brieftauben mit. Gegenüber dem Spiel an einem gemeinsamen Spielbrett ergeben sich ähnliche Herausforderungen, wie in verteilten Systemen.

(a) Nennen Sie fünf Probleme (z. B. plausible Vorfälle, oder Wissenslücken), die einen reibungslosen Spielverlauf stören können! Nennen Sie auch ihre Folge.

• Keine Zustellgarantie $\to$ Spiel endet nie
• Wegwahl der Taube $\to$ Verzögerung des Spielverlaufs bei unnötiger langen Routenwahl
• Verfälschung der Daten $\to$ Jemand ändert, dass was auf dem Zettel steht (Sabotage)
• Aufbau $\to$ unbekannt wer anfängt bzw. weiße Figuren hat
• Falscher Empfänger $\to$ Spiel endet nie

(b) Geben Sie für jeden der Störfälle einen Vorschlag zu seiner Vermeidung an!

• Keine Zustellgarantie $\to$ Empfangstaube bei Empfang sonst periodische Entsendung einer Spielzugtaube
• Wegwahl der Taube $\to$ trainierte Taube die nur diesen weg kennt
• Aufbau $\to$ Person A beginnt immer
• Verfälschung der Daten $\to$ Verschlüsselung des Spielzuges, damit sie nicht sabotiert werden kann
• Falscher Empfänger $\to$ Taube fliegt zurück zum Absender mit gleicher Nachricht am Fuss, was darauf hinweist, dass sie den Empfänger nicht erreicht hat

3. Von Netzen und Bäumen

Note

Im letzten Arbeitsblatt haben wir schon einige Berechnungen über die Anzahl an Verbindungen in Netzenangestellt. Hier konzentrieren wir uns weiter auf Bäume als Struktur.

Ein Netz bzw. Graph besteht aus einer Menge von Knoten und Kanten zwischen zwei Knoten. Der Grad eines Knotens ist die Anzahl der Kanten die in ihm enden. Ein Pfad zwischen zwei Knoten ist eine Menge von Kanten und beschreibt einen Weg zwischen zwei Knoten.

Ein Baum ist ein Graph in dem es von jedem Knoten zu jedem Knoten einen Pfad gibt und man keine reise mit den vorhandenen Kanten bilden kann. Die Knoten eines Baumes mit Grad 1 heißen Blatt, alle anderen innere Knoten. Benutzt man Bäume um eine Struktur darzustellen, so wird meistens ein Knoten des Baums als Wurzel bezeichnet. Die Anzahl der Kanten im Pfad von einem Knoten zur Wurzel ist der Abstand des Knotens zur Wurzel. Die Höhe eines Baums ist der größte Abstand. Zwischen den Knoten spricht man von Verwandschaftsbeziehungen: Von den beiden Knoten einer Kante ist der mit dem (um 1) längeren Pfad zur Wurzel ein Nachfahre, Nachfolger oder auch Kind des anderen Knotens.

Der Knoten mit dem kürzeren Abstand heißt Vorfahre, Vorfahrer oder auch Vater.

(a) Zeichnen Sie einen vollvermaschten Graphen mit 4 Knoten!

(b) Ein Baum mit insgesamt 4 Knoten kann vier verschiedene Formen haben. Eine mit Höhe 3, zwei mit Höhe 2 und eine mit Höhe 1. Zeichnen Sie für jede Art ein Beispiel!

(c) Binärbäume zeichnen sich dadurch aus, dass jeder Knoten höchstens 2 Kinder hat.

I. Aus wievielen Knoten besteht ein Binärbaum der Höhe 5 mindestens?

• $6$

Ii. Aus wievielen Knoten besteht ein Binärbaum der Höhe 2 höchstens?

• $7$

4. Adressierung in Bäumen

ASufgabenstellung

Abbildung 1 zeigt zwei Binärbäume mit unterschiedlichen Namensschemata. Einmal sind die Knoten und einmal die Kanten benannt. Den Schemata gemein ist, dass sie lediglich die Verzweigungsmöglichkeiten berücksichtigen. Um einen Knoten eindeutig zu identifizieren, muss man den Pfad von der Wurzel bis zum gesuchten Knoten aufschreiben. Während die Wurzel bei benannten Knoten dementsprechend mit 1 eindeutig identifizierbar wird, ist der Pfad bei benannten Kanten e (das leere Wort). In einem vollständigen Baum haben die Wurzel und jeder innere Knoten die maximale Anzahl Kinder.

---
title: Benannte Knoten
---
graph TD
    A(1) --> B(0)
    A -->C(1)
    B -->D(0)
    B -->X(0)
    C -->E(0)
    C -->F(1)
    E -->G(0)

---
title: Binärbaum mit nummerierten Pfaden
---
graph TD
    A("Wurzel") -->|0| B("Linkes Kind")
    A -->|1| C("Rechtes Kind")
    B -->|0| D("Linkes Linkes Kind")
    B -->|1| E("Linkes Rechtes Kind")
    C -->|0| F("Rechtes Linkes Kind")
    C -->|1| G("Rechtes Rechtes Kind")
    D -->|0| H("LLL Kind")
    D -->|1| I("LLR Kind")

(a) Wieviele Blätter hat jeder der Bäume im Beispiel?

$$4$$

(b) Wie lauten in beiden Beispielen die Pfade zu den Knoten mit Abstand 3?

• Links: $1100$

• Rechts: $100$

(c) Kann man aus dem Pfad “11” ablesen ob es sich um einen inneren Knoten oder ein Blatt handelt? Begründen Sie Ihre Antwort.

Nein, da 11 nur die Koordinate eines Knotens ist, und man daraus nicht herleiten kann, ob danach noch ein Knoten folgt oder nicht

(d) Schreiben Sie analog zum hier behandelten Beispiel mit benannten Kanten einen Pfad für einen beliebigen Knoten mit Abstand 8 in einem Binärbaum auf.

$$11111111$$

(e) Was haben die Pfade aller Nachfahren eines Knotens mit Abstand 8 im Hinblick auf die Pfadstruktur gemein? (Baum mit benannten Kanten)

• 8 stellen vor der letzten Ziffer ist gleich

(f) In einem vollständigen Binärbaum der Höhe 16 mit benannten Kanten gibt es ein Blatt, das mit dem Pfad 1100000010101000 adressiert wird. Interpretieren Sie diesen Pfad als Zahl im Binärsystem und wandeln Sie diese um in:

I. eine Dezimalzahl,

$$2^{15}+2^{14}+2^7+2^5+2^3$$ $$=49320$$

Ii. eine Hexadezimalzahl und

$$\begin{array}{rl}49320÷16& =3082R8\\ 3082÷16& =192R10\\ 192÷16& =12R0\\ 12÷16& =0R12\end{array}\uparrow$$ $$\text{= C0A8}$$

Iii. ein Tupel aus zwei Dezimalzahlen wobei jede Dezimalzahl eine Hälfte des Pfads darstellt.

• Splitten der Binärzahl $$11000000|10101000$$ $$2^7+2^6=192$$ $$2^7+2^5+2^3=168$$

$$\Rightarrow T(192,168)$$

5. Zahlen sind auch nur Bäume

Note

Man kann eine Menge von Binärzahlen als Baum darstellen. Abbildung 2 zeigt einen vollständigen Binärbaum der Höhe 4. Jeder Pfad von der Wurzel zu einem Blatt kann eindeutig durch die Namen der traversierten Kanten beschrieben werden. Zum Beispiel beschreibt 0011 den Pfad von der Wurzel zum vierten Blatt von links.

Der Präfix eines Pfades beschreibt dabei die ersten n Namen der Kanten. Beispielsweise hat 0100 den Präfix 0 der Länge 1 und 01 der Länge 2.

graph TD
    A(1) -->|0| B(0)
    A -->|1| C(1)
    B -->|0| D(0)
    B -->|1| E(1)
    C -->|0| F(0)
    C -->|1| G(1)
    D -->|0| H(0)
    D -->|1| I(1)
    E -->|0| J(0)
    E -->|1| K(1)
    F -->|0| L(0)
    F -->|1| M(1)
    G -->|0| N(0)
    G -->|1| O(1)
    H -->|0| P(0)
    H -->|1| Q(1)
    I -->|0| R(0)
    I -->|1| S(1)
    J -->|0| T(0)
    J -->|1| U(1)
    K -->|0| V(0)
    K -->|1| W(1)
    L -->|0| X(0)
    L -->|1| Y(1)
    M -->|0| Z(0)
    M -->|1| AA(1)
    N -->|0| AB(0)
    N -->|1| AC(1)
    O -->|0| AD(0)
    O -->|1| AE(1)

(a) Wie viele Pfade von der Wurzel zu einem Blatt mit dem Präfix 0 gibt es in dem in Abbildung 2 dargestellten Baum?

$$8$$

(b) Wie viele Pfade von der Wurzel zu einem Blatt gibt es mit dem Präfix 0, wenn man den in der Abbildung dargestellten Binärbaum bis auf Höhe n fortführt?

$$2^n÷2$$

Berechnet die Hälfte eines vollständigen Binärbaumes ohne Wurzelknoten

(c) Um einen gemeinsamen Präfix für einen Teilbaum anzugeben verwenden wir die Notation (Binärzahl mit Höhe des Baums vielen Stellen)/(Präfixlänge).

I. Wieviele Blätter hängen an dem Teilbaum 1111/1?

• 8

Ii. Wieviele Blätter hängen an dem Teilbaum 0000/2?

• 4

Iii. Wieviele Blätter hängen an dem Teilbaum 1010/3?

• 2

Iv. Wieviele Blätter hängen an dem Teilbaum 0101/4?

• 1

V. Wieviele Blätter hängen an dem Teilbaum 0110/0?

• 16

Wie man die Aufgabe löst:

Beispiel an i:

Gesamtbaum betrachten:

1111/1 bedeutet: gehe zum Knoten 1

Betrachte alle Blätter unter diesem Knoten

Zähle diese: Es sind 8 Stück

---