algoUNDdaten

Card Set Information

Author:
r3b1r7h
ID:
101626
Filename:
algoUNDdaten
Updated:
2011-09-14 08:20:50
Tags:
Algorithmen Datenstrukturen
Folders:

Description:
Algorithmen und Datenstrukturen
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user r3b1r7h on FreezingBlue Flashcards. What would you like to do?


  1. Erläutern Sie kurz mit eigenen Worten, was unter einem Algorithmus verstanden wird! Welche grundlegenden Eigenschaften sollten Algorithmen haben?
    • Definition: Ein Algorithmus ist eine Arbeitsanleitung, die so präzise formuliert ist, dass sie von einem Computer ausgeführt werden kann.
    • PFLICHT Eigenschaften:
    • Eindeutigkeit (keine Widersprüche),
    • Parametrisierbarkeit (mehrfach verwendbar [Variablen]),
    • Finitheit (endlich lang),
    • Ausführbarkeit (Widerspruchsfreiheit für den PC),
    • KANN Eigenschaften:
    • Terminierung, (müssen enden und Ergebnis liefern)
    • Determiniertheit, (gleiche Parameter = gleiches Ergebnis)
    • Determinismus, (zu jedem Zeitpunkt nur eine Fortführungsmöglichkeit)
    • Effizienz, (so schnell und so wenig Ressourcen wie möglich)
    • Speicherbedarf, (Quellcode möglichst knapp, Lesbarkeit darf nicht leiden)
    • Erweiterbarkeit, (ohne großen Aufwand anpassbar)
    • Wiederverwendbarkeit, (auch zur Lösung Teilprobleme woanders)
    • Portabilität, (Support aller Computertypen)
    • Zuverlässigkeit, (korrekte und vollständige Lösung des Problems)
  2. Erläutern Sie kurz, was in der Informatik unter einer Datenstruktur verstanden wird!
    Eine Datenstruktur fasst Datentypen zusammen und bietet ebenfalls Operationen an. basiert bzw. benötigt also Datentypen
  3. Was unterscheidet einen "Datentypen" von einer "Datenstruktur"?
    Formal bezeichnet ein Datentyp in der Informatik die Zusammenfassung von Objektmengen und darauf definierten Operationen. Antwort bzw. Unterschied siehe oben (2)
  4. Erläutern Sie den Begriff der Ordnungsrelation!
    In der Mathematik sind Ordnungsrelationen Verallgemeinerungen der „kleiner-gleich“-Beziehung. Sie erlauben es, Elemente einer Menge miteinander zu vergleichen.
  5. Was wird unter einer "rekursiven" Methode (bzw. Funktion) verstanden?
    Ein Objekt heißt rekursiv, wenn es sich selbst als Teil enthält oder mit Hilfe von sich selbst definiert ist.
  6. Was versteht man unter der "Rekursionstiefe"?
    Anzahl der aktuellen Inkarnationen einer Funktion minus 1. In der Informatik wird der Begriff Inkarnation verwendet für einen neuen Aufruf einer rekursiven Funktion.
  7. Kann es bei Verwendung rekursiver Methoden zu einem sogenannten "Stack-Overflow" kommen?
    Bei jeder rekursiven Aktivierung einer Funktion (Methode) wird ein neuer Satz lokaler, gebundener Variablen generiert! Typisch sind z. B. Stack-Overflows Im Wesentlichen werden bei einem Pufferüberlauf durch Fehler im Programm zu große Datenmengen in einen dafür zu kleinen reservierten Speicherbereich, den Puffer, geschrieben, wodurch nach dem Ziel-Speicherbereich liegende Speicherstellen überschrieben werden.
  8. Schreiben Sie eine rekursive Java-Methode zur Berechnung der Fakultät n! einer Zahl n auf!
    public class Fakultaet{public static void main(String [] args) {int n = 3; long fakultaet = 1;for (int i=1; i<=n; i++) {fakultaet = fakultaet * i;}System.out.println("Die Fakultät von " + n + " ist " + fakultaet);}}
  9. Gegeben sei folgende rekursiv definierte Java-Methode: public int lzahl(int x){ if (x == 0) return 1; if (x == 1) return 1; if (x > 1) return lzahl(x – 1) + lzahl(x – 2);} Terminiert die Methode für alle ganzzahligen Eingaben x ?
    • positive ja
    • wenn negative dabei, nein, weil nicht berücksichtigt.
  10. Ließe sich mit oben stehender Implementierung der Wert lzahl(64) berechnen? Warum bzw. warum nicht?
    Theoretisch ja, aber besteht Gefahr zum Stack-Overflow
  11. Welche Ergebnisse liefert nachstehende Java-Methode für die Werte 0, 1, 2, 3 und 4? public int fzahl(int x) { if (x <= 0) return 1; else return (5 * fzahl(x – 1));}
    • 0 -> 1
    • 1 -> 5
    • 2 -> 25
    • 3 -> 125
  12. Erläutern Sie mit eigenen Worten, was unter der Laufzeit eines Algorithmus verstanden wird! Gehen Sie dabei auch auf die O-Notation ein.
    • Die Laufzeit ist ein Maß der Effizienz des Algorithmuses.
    • Die O-Notation ist eine Abschätzung der Laufzeit bei unendlich großen Eingaben. Da jedoch keine Eingabe unendlich ist, sollte man bei der Wahl von Algorithmen, die realistische Eingabelänge einbeziehen.
  13. Was bedeutet es, wenn ein Algorithmus im Worst-Case eine Laufzeit von O(n²) hat?
    Es bedeutet, dass der Algorithmus im Worst-Case eine quadratisch steigende Laufzeit hat. Direkte Rückschlüsse auf Average – und Best-Case lassen sich hierdurch nicht treffen.
  14. Was bedeutet es, wenn ein Algorithmus im Average-Case eine Laufzeit von O(log n) hat?
    Dieser Algorithmus ist gut. Die Laufzeit wird sich bei hohen Eingaben nicht groß erhöhen.
  15. Welche Rolle spielt die Basis des Logarithmus in der Laufzeitangabe O(log10 n)?
    Bezüglich der O-Notation spielt die Basis des Log keine Rolle, denn Die O-Notation gibt nur ein qualitatives Maß der Laufzeit wieder. Die Änderung der Basis entspricht im Prinzip nur dem Hinzufügen eines Faktors.
  16. Was bedeutet es, wenn ein Algorithmus Speicherplatz in der Größenordnung O(n²) benötigt?
    Es bedeutet, dass der Speicherplatz den quadratischen Wert der Eingabemenge entspricht z.B. bei 10 Eingabewerten, benötigt dieser Algorithmus einen Speicherwert von 100.
  17. Erfordern Sortieraufgaben, dass eine Ordnungsrelation auf den zu sortierenden Datenobjekten definiert ist?
    Ja ohne Ordnungsrelation ist ein sinnvolles Sortieren nicht möglich.
  18. In welcher Laufzeit lässt sich ein Array bei Wahl eines optimalen Verfahrens im Average-Case sortieren?
    O(n logn)
  19. Was ist ein "Pseudocode"?
    Pseudocode ist Programmcode, der nicht zur maschinellen Interpretation sondern lediglich zur Veranschaulichung eines Paradigmas oder Algorithmus dient.
  20. Was ist ein abstrakter Datentyp (im Gegensatz zum konkreten Datentyp)?
    Ein ADT beschreibt, was die Operationen tun (Semantik), aber noch nicht, wie sie es tun (Implementierung). Auch kann das Konzept des ADTs unterschiedlich spezifiziert und ein ADT auf verschiedene Weise notiert werden, bspw. durch Pseudocode oder durch eine mathematische Beschreibung. Modernere Programmiersprachen unterstützen allerdings gezielt die Erstellung von ADTs.
  21. Wozu dienen abstrakte Datentypen in der praktischen Software-Entwicklung?
    Diese Datentypen werden verwendet um in der Entwicklung verschiedene Vorgänge parallel zu bearbeiten. (Dummies)
  22. Was wird unter einer "dynamischen" Datenstruktur verstanden? Nennen Sie zwei praktische Beispiele!
    • Dynamische Datenstrukturen bezeichnen in der Informatik Datenstrukturen, die eine flexible Menge an Arbeitsspeicher reservieren.
    • Verkettete Liste und dynamischer Baum
  23. Welche Vor- und Nachteile weist eine lineare Liste gegenüber einem Array auf?
    • Vorteil: Einfügen und Entfernen einzelner Elemente. Speicherbedarf wird optimal genutzt.
    • Nachteil: Es ist aufwändig nach Daten zu suchen, Knoten einzufügen, zu löschen und die Liste zu sortieren, da über jedes einzelne Element gegangen (iteriert) werden und das Einfügen an der ersten und der letzten Stelle gesondert behandelt werden muss
  24. Gegeben sei eine Liste, die mehrere Worte der deutschen Sprache als Zeichenketten enthalte. Ein Wort kann dabei mehrfach in der Liste enthalten sein. Im Weiteren sollen Sie einen Algorithmus entwickeln, der das am häufigsten vorkommende Wort ermittelt. Beschreiben Sie kurz einen Algorithmus, der das Problem löst!
    • Liste durchgehen
    • Liste pro Namen bilden
    • Listen der Namen miteinander vergleichen (length)
  25. Schätzen Sie, welcher Gesamtaufwand in Abhängigkeit von der Anzahl n der Listenelemente sich für Ihren Algorithmus ergibt (Angabe unter Verwendung der O-Notation)! Hinweise: Es existieren zahlreiche verschiedene Lösungsmöglichkeiten. Der von Ihnen ausgedachte Algorithmus muss nicht Laufzeit-optimal sein. Sollte das Laufzeitverhalten Ihres Algorithmus besser als O(n2) sein, werden zwei Zusatzpunkte vergeben, die in die Klausurbewertung einfließen.
    kA
  26. Was ist ein Kellerspeicher ("Stack")?
    in Stapel kann eine theoretisch beliebige, in der Praxis jedoch begrenzte Menge von Objekten aufnehmen. Elemente können nur oben auf den Stapel gelegt und auch nur von dort wieder gelesen werden. Elemente werden übereinander gestapelt und in umgekehrter Reihenfolge vom Stapel genommen. Dies wird auch Last-In-First-Out-Prinzip (LIFO) genannt.
  27. Welche grundlegenden Operationen sind auf Kellerspeichern ("Stacks") definiert?
    • FiLo – first in last out
    • push (auch einkellern) legt das Objekt oben auf den Stapel.
    • pop (auskellern) liefert und entfernt das oberste Objekt vom Stapel. Bei manchen Prozessoren wie dem MOS Technology 6502 wird diese Aktion dagegen pull (herunterziehen) genannt.
    • peek (nachsehen) liefert das oberste Objekt, ohne es zu entfernen.
  28. Welche grundlegenden Operationen lassen sich auf einer sogenannten "Schlange" ("Queue") definieren?
    • FiFo – First in first out
    • Enter – fügt ein Element hinzu
    • Leave – löscht das vorderste Element
    • Front – liefert das vorderste Element
  29. Erläutern Sie in Verbindung mit Baumstrukturen nachstehende Begriffe: Wurzelknoten, Kindknoten, Blattknoten, Höhe eines Baums.
    • Wurzelknoten: Das oberste Element (hat kein Elternknoten)
    • Kindknoten: Nachfolgeelment des Elternknotens
    • Blattknoten: Letzte Elemente eines Baumes(hat keine Kindknoten)
    • Höhe eines Baumes: Anzahl der Ebenen des Baumes
  30. Definieren Sie den Begriff den binären Baums!
    Es handelt sich um einen Wurzelbaum (gewurzelten Baum), bei dem jeder Knoten höchstens zwei Kindknoten besitzt. Meist wird verlangt, dass sich die Kindknoten eindeutig in linkes und rechtes Kind einteilen lassen.
  31. Was wird unter der Traversierung eines Baums verstanden? Nennen Sie mindestens drei verschiedene Traversierungsstrategien!
    • Traversierung ist in der Graphentheorie der Name für Verfahren, die eine Route bestimmen, bei der jeder Knoten und jede Kante eines baumförmigen Graphen genau einmal besucht wird
    • pre-order (auch depth-first) oder Hauptreihenfolge (auch Tiefensuche) (W–L–R): Zuerst wird die Wurzel (W) betrachtet und anschließend der linke (L), schließlich der rechte (R) Teilbaum durchlaufen.
    • post-order oder Nebenreihenfolge (L–R–W): Zuerst wird der linke (L), dann der rechte (R) Teilbaum durchlaufen und schließlich die Wurzel (W) betrachtet.
    • in-order oder symmetrische Reihenfolge (L–W–R): Zuerst wird der linke (L) Teilbaum durchlaufen, dann die Wurzel (W) betrachtet und schließlich der rechte (R) Teilbaum durchlaufen.
    • reverse in-order oder anti-symmetrische Reihenfolge (R–W–L): Zuerst wird der rechte (R) Teilbaum durchlaufen, dann die Wurzel (W) betrachtet und schließlich der linke (L) Teilbaum durchlaufen.
    • level-order (auch breadth-first, deutsch Breitensuche): Beginnend bei der Baumwurzel werden die Ebenen von links nach rechts durchlaufen.
  32. Geben Sie den Aufwand für das Traversieren eines binären Baums mit n Knoten an (ONotation)!
    O(n)
  33. 30. Gegeben sei folgender Baum, in dessen Knoten Zeichenketten abgelegt sind: Wie viele Wurzelknoten und wie viele Blattknoten besitzt dieser Baum?
    Wurzelknoten: 1 Blattknoten: 4
  34. Geben Sie an, welche der folgenden Eigenschaften dieser Baum besitzt. Begründen Sie jeweils kurz Ihre Antworten! Es handelt sich um einen binären Baum. Es handelt sich um einen Suchbaum, insofern als Sortierkriterium für die im Baum abgelegten Inhalte die alphabetische Ordnung von Zeichenketten verwendet wird.Es handelt sich um einen Suchbaum, insofern als Sortierkriterium für die im Baum abgelegten Inhalte die Länge der Zeichenketten (String-Länge) verwendet wird. Der Baum ist vollständig ausgeglichen.
    ja, ja, ja, Es handelt sich um einen B-Baum.
  35. Listen Sie die Knoteninhalte der Baumstruktur in folgenden Durchlauf-Reihenfolgen auf:
    • Inorder : Beate, Fritz, Holger, Johann, Juliane, Katharina, Zacharias
    • Postorder: Beate, Holger, Fritz, Juliane, Zacharias, Katharina, Johann
    • Preorder: Johann, Fritz, Beate, Holger, Katharina, Juliane , Zacharias
  36. Welcher Laufzeit-Aufwand in Abhängigkeit von der Anzahl n der Baumknoten ergibt sich für die Suche eines Eintrags in ausbalancierten binären Suchbäumen (Angabe unter Verwendung der O-Notation)?
    O(logn)
  37. Wie lautet der Wurzelknoten des dargestellten Baums? Wie viele Blattknoten hat der Baum und wie lauten sie? Handelt es sich um einen binären Baum? Welche Höhe weist der Baum auf?
    • Wurzelknoten: A
    • Blattknoten: H, I, N, O, P, K, Q, R = 8
    • Ja ist ein Binärbaum
    • 4, (inklusive A -> 5)
  38. Geben Sie die Elemente des binären Baums aus der vorangegangenen Aufgabe im Preorder- Postorder- und Inorder-Durchlauf an!
    • Pre: A B D H E I J N O C F K L P G M Q R
    • Post: H D I N O J E B K P L F Q R M G C A
    • In: H D B I E N J O A K F P L C G Q M R
  39. Definieren Sie den Begriff des "binären Suchbaums"!
    In der Informatik ist ein Suchbaum eine auf Bäumen basierende abstrakte Datenstruktur, die das Ziel hat, in ihr gespeicherte Objekte und Elemente einer total geordneten Menge effizient suchen zu können.
  40. Ist jeder binäre Baum zugleich ein Suchbaum?
    Nein, weil im Binärbaum keine Ordnung zwingend notwendig ist
  41. Skizzieren Sie einen Algorithmus zur Suche eines Eintrags in einem binären Suchbaum! Versuchen auch, die Laufzeit für Ihren Algorithmus abzuschätzen!
    Laufzeit O(logn)
  42. Was versteht man unter einem "dynamischen Suchbaum"?
    Ein durch Einfügeoperationen entstandener Suchbaum.
  43. Warum wird in Anwendungspraxis versucht, Suchbäume auszubalancieren?
    Ausbalancierte Bäume haben relativ geringe Höhen im Vergleich ihrer Elemente und können Deshalb effizienter genutzt werden. Nicht-ausbalancierte Bäume (Extremfall Liste) haben Schlechtere Eigenschaften.
  44. Zeichnen Sie einen vollständig balancierten binären Suchbaum auf, der die folgenden Zeichenketten enthält (lexikalische Ordnung): Ute Sönke Franziska Markus Leon Nele Thomas Julia Ina Bert Peter Silke Markus Vera Jonas Anke Matthias Moritz Karin Susanne
    Kann man zuhause machen
  45. Worin unterscheiden sich balancierte und ausgeglichene Suchbäume? Welchen Vorteil bieten ausgeglichene Bäume gegenüber vollständig balancierten Bäumen?
    kA
  46. Warum ist es erstrebenswert, Bäume ausbalanciert (oder ausgeglichen) zu halten?
    • Balancierte Bäume: wurden entwickelt, um die Entartung zu verhindern und eine Höhe von zu garantieren.
    • Ein Baum ist genau dann ausgeglichen, wenn: sich für jeden Knoten die Höhen der zugehörigen Teilbäume um höchstens 1 unterscheiden. Bäume, die dieses Kriterium erfüllen, heißen ausgeglichene Bäume oder AVL-Bäume.
  47. Sind alle vollständig balancierten Bäume auch ausgeglichen?
    Nein, denn balance STRENGER ALS ausgeglichenheit
  48. Erläutern Sie mit Hilfe der nachstehenden Abbildung, wie ein B-Baum prinzipiell organisiert ist!
    • Schrumpft zur Wurzel
    • Ist immer ausballanciert
  49. Worin unterscheiden sich B-Baum und binärer Baum?
    Ein B-Baum ist ein immer vollständig balancierter Baum, der Daten sortiert nach Schlüsseln speichert. Er kann binär sein, ist aber im allgemeinen kein Binärbaum.
  50. Beschreiben Sie kurz mit eigenen Worten die Grundidee der Streuspeicherung ("Hashing")!
    • Geringe Wahrscheinlichkeit von Kollisionen der Hashwerte für den Eingabewertebereich, also möglichst eine Gleichverteilung der Hashwerte auf die erwarteten Eingabewerte.
    • Datenreduktion – Der Speicherbedarf des Hashwertes soll deutlich kleiner sein als jener der Nachricht (Eingabewert).
    • Chaos – Ähnliche Quellelemente (Eingabewerte) sollen zu völlig verschiedenen Hashwerten führen. Im Idealfall verändert das Umkippen eines Bits in der Eingabe durchschnittlich die Hälfte aller Bits im resultierenden Hashwert.
    • Surjektivität – Kein Ergebniswert (Hashwert) soll unmöglich sein, jedes Ergebnis (jeder Hashwert im definierten Wertebereich) soll tatsächlich vorkommen können.
    • Effizienz – Die Funktion muss schnell berechenbar sein, ohne großen Speicherverbrauch auskommen und sollte die Quelldaten (Eingabewerte) möglichst nur einmal lesen müssen.
    • ordnungserhaltend – Falls die Hashfunktion einen sortierten Zugriff in einer Hashtabelle erlauben soll.
  51. Erläutern Sie, was unter einer Hash-Tabelle und einem Hash-Schlüssel verstanden wird!
    In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen stehen dabei in Konkurrenz zu Baumstrukturen (wie etwa ein B+-Baum) und der Skip-List, die ebenfalls als Indexstruktur dienen können. Beim Einsatz einer Hashtabelle zur Suche in Datenmengen spricht man auch von einem Hashverfahren oder Streuspeicherverfahren.
  52. Welche Vorteile erhofft man sich durch die Streuspeicherung (d. h., durch den Einsatz von Hash-Tabellen)?
    Trotz der Schwierigkeiten, die sich beispielsweise aus der Kollisionsbehandlung ergeben, bieten Hashtabellen wegen der Vorzüge beim sofortigen Zugriff durch den Hash-Wert auf die Inhalte in einer Tabelle im Vergleich zu der Suche nach dem Schlüssel und wegen der im Idealfall fehlenden Beziehung zweier Hash-Werte, die aus ähnlichen Schlüsseln berechnet wurden, oft Vorteile sowohl in der Zugriffszeit als auch im benötigten Speicherplatz gegenüber gewöhnlichen Arrays.
  53. Was ist beim praktischen Einsatz von Hash-Tabellen zu beachten?
    Wurden Hash-Funktion und Größe der Hashtabelle geeignet gewählt, ist der Aufwand für die Suche in der Tabelle (Look-Up) O(1). Wegen der möglichen Kollisionen hat eine Hashtabelle allerdings im so genannten Worst-Case ein sehr viel schlechteres Verhalten. Dieser wird mit O(n) abgeschätzt, wobei das n der Anzahl der in der Hashtabelle gespeicherten Einträge entspricht. Es werden dabei also alle Einträge in der Tabelle durchsucht.
  54. Was ist ein "Quadtree"?
    Ein Quadtree ist in der Informatik eine spezielle Baum-Struktur, in der jeder innere Knoten genau vier Kinder hat. Das Wort Quadtree leitet sich von der Zahl der Kinder eines inneren Knotens ab (quad (vier) + tree (Baum) = Quadtree).
  55. Macht es Sinn, "Quadtrees" rekursiv zu definieren?
    ja
  56. Die Bounding-Box einer Menge ebener geometrischer Objekte ist das kleinste Rechteck, welche alle Objektgeometrien der Menge beinhaltet und deren Kanten parallel zu den Koordinatenachsen sind. Vorgegeben sei eine Java-Klasse namens Point2D, welche Punktgeometrien bestehend aus x- und y-Koordinate vorhält. Schreiben Sie einen Algorithmus, welcher die Bounding-Box zu in einem Array abgelegten Punktgeometrien ermittelt (Point2D[] points).
  57. Erläutern Sie kurz, was unter einem Graphen verstanden wird!
    Ein Graph ist in der Graphentheorie eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert. Die mathematischen Abstraktionen der Objekte werden dabei Knoten (auch Ecken) des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen Kanten (manchmal auch Bögen). Die Kanten können gerichtet oder ungerichtet sein. Häufig werden Graphen anschaulich gezeichnet, indem die Knoten durch Punkte und die Kanten durch Linien dargestellt werden.
  58. Stellen Sie den Unterschied zwischen ungerichteten, gerichteten und gewichteten Graphen dar!
    In gerichteten oder auch orientierten Graphen werden Kanten statt durch Linien durch Pfeile gekennzeichnet, wobei der Pfeil vom ersten zum zweiten Knoten zeigt. Dies verdeutlicht, dass jede Kante des Graphen nur in eine Richtung durchlaufen werden kann. Eine typische Anwendung ist der Netzplan mit einer temporalen Kette.

What would you like to do?

Home > Flashcards > Print Preview