Was ist die Aufgabe von Warteschlangen?
Und was hat es mit den FIFO-Speicher auf sich?
Temporäres Abspeichern von Daten, bis diese weiterverwendet werden.
Da die abgelegten Daten dabei in der gleichen Reihenfolge, in der sie abgespeichert wurden, auch wieder ausgelesen werden, liegt in diesem Fall ein FIFO-Speicher (First-In-First-Out) vor.
Grundsätzlich kennen Speicheranordnungen auf Warteschlangenbasis dabei die folgenden zwei Befehle.
Enqueue:
Dequeue:
Wofür stehen beide?
Enqueue: Ein Element wird in die Warteschlange eingefügt.
Dequeue: Ein Element wird der Warteschlange entnommen.
Gib ein Beispiel dafür wo Warteschlangen Anwendung finden.
Anwendung finden Warteschlangen z. B. dann, wenn zwei unterschiedlich schnell arbeitende Geräte/Protokolle miteinander verbunden werden sollen.
Wir können als Endbenutzer beispielsweise sehr schnell umfangreiche Druckaufträge erteilen, jedoch ist der Drucker selbst meist nicht in der Lage, in gleicher Geschwindigkeit auch den eigentlichen Druck vorzunehmen, sodass hier zwangsläufig ein Problem in der Abarbeitung der Druckaufträge auftreten würde.
Eine Möglichkeit zur Beseitigung dieses Problems bietet die Einführung von Warteschlangen. Die Druckaufträge werden dabei sequenziell in der Warteschlange abgelegt und danach in Reihenfolge abgearbeitet.
Was versteht man unter einem Heap und was kann mit diesen gemacht werden?
Unter einem Heap wird eine Datenstruktur verstanden, die meist einem Baum gleicht.
Datenelemente können dabei in eine hierarchische Struktur gebracht (die einzelnen Einträge werden mit Schlüsseln entsprechend ihrer Priorität versehen) und entsprechend wieder ausgelesen werden.
Dieses prioritätenbasierte Auslesen des Speichers wird als HIFO-Prinzip (Highest-In-First-Out) bezeichnet.
Darstellung eines Binärheap
Welche zwei Heap-Varianten werden hinsichtlich ihrer Prioritäten unterschieden?
Max-Heaps: Bei dieser Heap-Struktur weist das Wurzelelement immer die höchste Priorität auf, die Kinderknoten haben entsprechend immer eine kleinere Priorität als die der Eltern.
Min-Heaps: Bei Min-Heaps wird dem Wurzelknoten die kleinste Priorität zugeordnet, die Kindernknoten haben dabei immer eine höhere Priorität als ihre Eltern.
Wie lauten die 3 wichtigsten Funktionalitäten von einen Heap?
Insert(): einem Heap Elemente hinzufügen.
Remove(): Dient zum Entfernen von Elementen.
ExtractMin(): Dient zum Auslesen und gibt in dieser Ausprägung das Element mit geringster Priorität zurück.
Was versteht man in der Inofrmatik unter einem Stack?
Wo findet dieser Anwedung?
Unter einem Stack wird in der Informatik ein Speicher zum Ablegen von Daten in der Form eines Stapelspeichers verstanden. Das bedeutet, dass abzulegende Daten einfach aufeinander gestapelt werden
Anwendung findet dieses Konzept z. B. bei Mikroprozessoren und legt damit die Abarbeitungsreihenfolge von Befehlen fest, die dem Prozessor zugeführt werden.
Das Ablegen und Wiederauslesen von Daten erfolgt dabei entsprechend nach dem LIFO-Prinzip (Last-In-First-Out).
Wie lauten die 3 Operationen die ein Stack kennt?
Push: Mithilfe des Push-Befehls wird ein neues Element oben auf den Stack aufgelegt.
Pop: Mithilfe des Pop-Befehls wird das oberste Elemente bzw. das zuletzt dort abgelegte aus dem Stack entnommen.
Peek (oft auch als „Top“ bezeichnet): Mithilfe dieses Befehls wird das oberste Element des Stack ausgegeben, ohne es jedoch aus dem Speicher zu entfernen.
Das Grundprinzip der Push-/Pop-Befehle ist dabei in Abbildung 2.3 veranschaulicht.
Was ist ein Graph und aus welchen beiden Elementen besteht dieser?
Mit einem Grapf wird versucht, Verbindungen und Assoziationen zwischen Elementen herzustellen.
Ein Graph kann dabei als eine Menge bestehend aus Knoten (den Elementen) E sowie einer Menge aus Kanten K verstanden werden.
Soll eine Relation zweier Knoten zueinander ausgedrückt werden, so werden zwei Knoten ei sowie ej∈E durch eine Kante ki ∈ K miteinander verbunden.
Wie lautet die Vorraussetzung das ein Graph als leerer Graph beuzeichnet wird?
Und wann als Nullgraph?
Der Fall E = K = ∅ wird als leerer Graph bezeichnet
Fall K = ∅ und E ≠ ∅ als Nullgraph.
Was beschreibt die Knotenmenge eines Graphen?
Was die Kantenmenge?
Und was die Entpunkte?
E = E(G) = {e1, e2,..., en} die Knotenmenge.
K = K(G) = {k1, k2,..., kn} die Kantenmenge eines Graphen G.
Gilt des Weiteren k ∈ K mit g(k) = {x, y}, so beschreiben x, y die Endpunkte der Kante k.
Wann die Kante k als „Schlinge“ oder „Loop“ bezeichnet?
Für den Spezialfall x = y.
Wie werden Knoten genannt die durch eine Kante verbunden sind?
Sie werden „benachbart“ oder „adjazent“ genannt.
Was ist die besonderheit beim Multigraph?
Hierbei handelt es sich um Graphen, die mehrere Kanten zwischen zwei Knoten erlauben,
wie es z. B. bei der Modellierung von Straßennetzen zum Einsatz kommen kann,
da zwischen zwei Navigationspunkten durchaus mehrere Verbindungsmöglichkeiten existieren können.
Betrachten wir zur Veranschaulichung konkret die Knotenmenge E = {e1, e2, e3, e4, e5} sowie die Kantenmenge K = {k1, k2, k3, k4, k5, k6}
Warum handelt es sich hierbei um einen ungerichteten Graphen?
Da die Knoten des dargestellten Graphen keine Richtung aufweisen,
handelt es sich hierbei um einen ungerichteten Graphen.
Wann bezeichnet mann die Eigenschaften von Graphen als Isomorphismus?
Graphen welche in ihrer grafischen Darstellung nicht eindeutig sind und daher mehrere grafische Repräsentationsmöglichkeiten für einen Graphen existieren.
Diese Eigenschaft wird auch als Isomorphismus bezeichnet.
Welches Konzept zu Darstellung von Graphen wird in folgender Graphik dargestellt?
Das Konzept eines Isomorphismus.
Zwei strukturell gleiche Graphen G1 = (V1, E1) sowie G2 = (V2, E2) gezeigt.
Die dritte Spalte gibt dabei an, auf welchen Knoten aus G2 die Knoten aus G1 abgebildet werden, um aus G1 den strukturgleichen Graphen G2 zu erhalten.
Definition:
Wie lautet die Definition für einen endlichen Graphen?
Ungerichtete Graphen G mit |E(G)|, |K(G)| < ∞ werden als endlich bezeichnet.
Was versteht man unter einen gerichteten Graph?
Anschaulich formuliert, verstehen wir unter einem gerichteten Graphen einen Graphen, dessen Kanten eine Richtung haben.
Beispiel:
Wir können dies anhand eines Straßennetzes einer Großstadt illustrieren. Typischerweise liegen hierbei viele Einbahnstraßen vor, sodass zwar eine Verbindung von A nach B durch eine Straße existiert (jeweils repräsentiert durch Knoten), jedoch nicht umgekehrt von B nach A. In der grafischen Repräsentation des Graphen wird dies durch Einführen von Pfeilen als Kanten zum Ausdruck gebracht.
Wie könnte eine Beispielhafte Darstellung eines gerichteten Graphen für eine gegebene Knotenmenge E sowie Kantenmenge K aussehen?
Hierbei wurde beispielhaft angenommen, dass wir zwar von Knoten 1 über 2 nach 3 und 4 gelangen können, jedoch keine Verbindung von 4 über 3 und 2 nach 1 existiert. In so einem Fall müssten wir uns dann, unter der Annahme eines Stadtverkehrs, über 5 zurück nach 1 bewegen.
Gewichtete/ungewichtete Graphen
Es besteht die Möglichkeit die Kanten eines Graphen mit Gewichten auszustatten. Gib ein Beispiel aus der Ralität wo das sinnvol wäre.
Betrachten wir dazu erneut das bereits diskutierte Beispiel eines Straßennetzes. Existiert zwischen zwei Punkten A und B einer Stadt eine Verbindung, so werden diese beiden Knoten durch eine Kante miteinander verbunden.
Die Ausprägung der Kante beschreibt dabei, dass eine Straßenverbindung zwischen den beiden Punkten realisiert ist. In einer Stadt gibt es zwischen verschiedenen Punkten nun meistens mehrere Wege, die entsprechend verschieden lang ausfallen können.
Die Entfernung zwischen zwei Punkten in einem Graphen kann dann z. B. durch Gewichtung der verbindenden Kante mit der Entfernung mitberücksichtigt werden.
Betrachte folgenden Graphen dessen Kanten gewichtet wurden.
Wie viele Einheiten ergeben sich, wenn ich von e1 nach e2,e3 nach e4 kommen möchte?
Gibt es einen kurzeren Weg?
Wollen wir nun wieder von Knoten e1 zu Knoten e4 gelangen, so müssen wir eine Entfernung von fünf Einheiten zurücklegen, um von Knoten e1 nach Knoten e2 zu gelangen.
#Nun ist die Kante zwischen den Knoten e2 und e3 mit sieben Einheiten gewichtet. Von e1 nach e4 ergibt sich so ein Weg von 15 Einheiten.
Ein kürzerer Weg würde sich hingegen von e1 über e5 nach e4 ergeben, was mit Gesamtkosten von neun Einheiten einhergehen würde.
Wie lautet der Algorythmus welchen man nutzen kann um den kürzesten Weg durch ein Straßengeflecht zu finden?
Dijkstra-Algorithmus, dieser hat das Finden kürzester Wege in einem Graphen zum Ziel.
Die Gewichtung eines Graphen ist dabei nicht nur auf die Berücksichtigung von Entfernungen beschränkt, sondern kann z. B. auch zur Modellierung betriebswirtschaftlicher Ströme genutzt werden, beispielsweise wenn eine Zuliefererkette optimiert werden soll und für unterschiedliche Transportwege und -methoden entsprechend unterschiedliche Kosten anfallen. In diesem Beispiel würde das Kantengewicht dann durch die jeweiligen Kosten dargestellt werden.
Betrachte folgende Tabelle.
Zur welcher der folgenden Spalten passen diese Begriffe:
Netzwerk
Knoten
Kanten
Dieser Graph
Wird mit folgender Matrix dargesttellt.
Wie bezeichnet man diese Matrix?
Die Matrix welche den Graphen darstellt bezeichnet man als:
Adjazenzmatrix.
Bitte erläutern Sie mit eigenen Worten das Konzept einer Warteschlange.
Eine Warteschlange arbeitet typischerweise als FIFO-Speicher und wird dazu genutzt, eine Brücke der Kommunikation zwischen verschieden schnell arbeitenden Geräten herzustellen, wie z. B. bei der Verwaltung von Druckaufträgen.
Bitte erläutern Sie in eigenen Worten das Konzept einer Blockchain.
Grundidee der Blockchain ist es, eine dezentrale Datenhaltung vorzunehmen,
indem alle abzulegenden Daten in Blöcken und Transaktionen abgelegt und
durch kryptografische Verfahren (Hash-Werte) miteinander verbunden werden.
Durch die so resultierende Verknüpfung ist es nicht mehr möglich, im Nachhinein einzelne Blöcke der Blockchain abzuändern, ohne deren Konsistenz zu verändern.
Was ist die Hauptmotivation zur Einführung einer Blockchain?
die Nachteile einer zentralen Speicherung von Daten ,
da diese in den Augen der Entwickler der Blockchain so
nicht ausreichend gegen Datenverlust und
unbemerkte Manipulation gesichert sind.
Was beschreibt ein abstrakter Datentyp und wie lauten seine 3 wesentlichen Eigenschaften?
Ein abstrakter Datentyp (ADT) beschreibt eine komplexe Datenstruktur in abstrakter Form, basierend auf ihren wesentlichen Eigenschaften, ohne auf die konkrete Umsetzung einzugehen.
Die wesentlichen Eigenschaften gliedert man dazu üblicherweise in drei Teile, nämlich …
die syntaktische Struktur, die die Operatoren des ADT spezifiziert,
die semantische Spezifikation, die die Beziehungen zwischen den Operatoren festlegt, sowie
die Restriktionen, also Bedingungen, die erfüllt werden müssen.
Wie werden Objekte in der Informatik noch genannt?
Sie werden auch Entität oder Instanz genannt.
UML-Diagramm einer Klasse „Fahrzeug“ sowie der Erzeugung einer Instanz
Wie würde die Instatziierung dieser Klasse aussehen?
Es würde ein Objekt entstehen.
Erkläre den Begriff der polymorphie.
die Fähigkeit, dass Funktionen oder Methoden in verschiedenen Objekten unterschiedlich ausgeführt werden können.
Während die gleiche Nachricht (Methode oder Funktion) an verschiedene Objekte gesendet wird, reagiert jedes Objekt entsprechend seiner Klasse oder seinem Typ.
erkläre mit einfachen worten den byzantinischen Fehler.
Der Byzantinische Fehler ist ein Problem, das insbesondere in Systemen mit vielen Computern auftritt, die miteinander kommunizieren müssen.
Stell dir vor, du bist Teil einer Gruppe von Freunden, die einen Plan machen, wohin ihr zum Essen gehen wollt. Ihr müsst euch alle darauf einigen, sonst kann es zu Verwirrung führen.
Wenn einige Freunde falsche Informationen geben oder sogar lügen, kann das den ganzen Plan durcheinander bringen.
Genau das passiert beim Byzantinischen Fehler. Wenn einige Computer in einem System falsche Informationen senden, kann das das gesamte System durcheinanderbringen oder sogar zum Absturz bringen.
Last changed7 months ago
