Algorithmen & Datenstrukturen
2. Semester Informatik (HSLU)
2. Semester Informatik (HSLU)
Was ist eine doppelt verkettete Liste?
- Es gibt Referenzen auf das erste (-> head) und das letzte (-> tail) Element in der Liste
- Jedes Element kennt seinen direkten Vorgänger und Nachfolger
Was sind die wichtigsten Eigenschaften eine Liste?
(siehe Bild)
Wie gross ist der Aufwand bei der Suche nach dem Element "G" in einer Liste?
Da wir keinen direkten Zugriff haben (sondern nur sequenziell) beträgt der Aufwand für die Suche eines Elementes in einer Liste grundsätzlich O(n).
- Unabhängig davon ob sortiert oder unsortiert.
- Unabhängig davon ob einfach oder doppelt verkettet.
Lässt sich der Aufwand bei der Suche nach einem Element "G" bei einer sortierten Liste von O(n) auf O(log n) reduzieren?
Ja, die Suche lässt sich bei sortierten Listen mit zusätzlichen Hilfsmitteln (-> Skiplisten) beschleunigen.
Damit wird ebenfalls O(log n) möglich
Wie gross ist der Aufwand beim Ergänzen eines Elementes "C" einer unsortierten Liste?
Dazu handelt es sich um eine einfach verkettete Liste!
Einfach verkettete Liste:
Da wir mit dem Head eine Referenz auf das erste Element haben, können neue Element am Anfang einfach und schnell eingefügt werden. Der Aufwand beträgt: O(1)
Wie gross ist der Aufwand beim Ergänzen eines Elementes "C" einer unsortierten Liste?
Dazu handelt es sich um eine doppelt verkettete Liste!
Bei doppelt verketteter Liste:
Analog kann zusätzlich auch am Ende der Liste (tail) mit Aufwand O(1) eingefügt bzw. angehängt werden.
Wie gross ist der Aufwand beim Einfügen eines Elementes "C" einer sortierten Liste?
Dazu handelt es sich einmal um eine einfach und einmal um eine doppelt verkettete Liste!
Wir müssen sequenziell die richtige Position (B) suchen und ein neues Element einfügen, das Verschieben der restlichen Elemente entfällt hingegen! Der Aufwand ist trotzdem: O(n)
Aufwand für einfach und doppelt verkettete Liste identisch
Wie gross ist der Aufwand beim Einfügen eines Elementes "C" einer Liste?
Dazu handelt es sich einmal um eine einfach und einmal um eine doppelt verkettete Liste!
Wir müssen sequenziell das gewünschte Element suchen und es aus der Liste entfernen. Auch hier ist kein Nachrücken von Elementen notwendig. Aufwand (bedingt durch Suche): O(n)
Aufwand ist für einfach und doppelt verkettet Liste identisch
Listen werden typisch mit mindestens zwei Klassen modelliert. Weshalb?
Eine Klasse repräsentiert die Liste selber
- Enthält die Referenz auf das erste Element (head).
- Hilfsattribute z.B. für Anzahl enthaltene Elemente.
- Methoden für die verschiedenen Operationen
Eine zweite Klasse repräsentiert die Elemente und wird häufig als Knoten, Element oder Node bezeichnet.
- Enthält je nach Listentyp (einfach/doppelt) ein oder zwei Referenzen auf den Vorgänger bzw. den Nachfolger.
- Enthält Attribut(e) für die eigentlichen, enthaltenen Daten
Bei der Implementation mit Java kann das Datenattribut generisch sein und somit für beliebige Typen parametrisiert werden
Konzeptionelles Modell: Einfach verkettete Liste
Da jeder Node (Element) eine Referenz auf den Nachfolger (next) hält, resultiert eine ________ Beziehung auf den selben Typ.
Da jeder Node (Element) eine Referenz auf den Nachfolger (next) hält, resultiert eine rekursive Beziehung auf den selben Typ.
- Modell enthält einen Zyklus
Konzeptionelles Modell: Doppelt verkettete Liste
Analog zur einfach verketteten Liste, der Node (Element) hat nun aber zwei Referenzen. Wo?
Je eine auf seinen unmittelbaren Vorgänger (prev) und seinen Nachfolger (next)
Was ist der Hauptvorteil von Listen gegenüber Arrays?
Der Hauptvorteil von Listen ist, dass sie dynamisch sind:
Sie können eine beliebige Datenmenge aufnehmen, belegen selber aber keinen «festen» Platz, sondern wachsen und schrumpfen mit der Datenmenge mit.
- prädestiniert für (sehr) grosse, stark variierende Datenmengen
Was sind weitere Vorteile einer Liste gegenüber einer Array abgesehen davon, dass Listen dynamisch sind?
- Der Aufwand für das reine Einfügen in eine Liste ist an jeder beliebigen Position (sofern man diese bereits gefunden hat!) konstant (und schnell)
- Listen sind als Datenstrukturen objektorientiert implementiert, unterstützen Generics, und können dank der vorhandenen Interfaces je nach Anwendungsfall in spezifischen Implementationen eingesetzt / ausgetauscht werden
Was ist eine Stack?
Der Stack ist eine Datenstruktur, der die Element als «Stapel» speichert:
- push(E e): Neue Elemente werden immer oben auf den Stapel abgelegt.
- E pop(): Es kann jeweils nur das oberste Element entnommen werden
Was ist die Semantik eines Stacks? (kurz)
LIFO - Last In First Out
Was ist eine Analogie zu einem Stack in Alltag?
Tellerstapel
Wo werden Stack eingesetzt?
- Datenablage bei Funktionsaufrufen
- Umkehren der Reihenfolge
Wie gross ist der Aufwand der Operationen bei einem Stack, welcher (1) mit einer Array oder (2) mit einer Liste implementiert wurde?
(siehe Bild)
Welche Unterschiede gibt es bei der Implementation eines Stacks (1) mit einer Array und (2) mit einer Liste?
(siehe Bild)
Stack mit Bibliotheksklassen
Welche Klassen und Interfaces sind für Stack-Implementation bzw. Semantik geeignet?
(siehe Bild)
Wir haben also die Wahl!
(Nebenbei: Array-Variante ist auch dynamisch implementiert!)
Was ist die Definition eines Algoritmus?
- Ein Algorithmus ist ein präzise festgelegtes Verfahren zur Lösung eines Problems; genauer gesagt von einer Problem-Klasse beinhaltend (unendlich) viele gleichartige Probleme.
- Etwas salopp: Algorithmus = Lösungsverfahren (Rezept, Anleitung)
- Probleme bzw. Problem-Klassen , die mit Algorithmen gelöst werden können, heissen (berechenbar)
Nennen Sie einfache Beispiele eines Algorithmus
- Berechnung des grössten gemeinsamen Teilers (ggT) für zwei beliebige natürliche Zahlen.
- Zeichnen der Verbindungslinie, welche zwei Punkte verbindet.
- Sortierung von zufällig vorliegenden ganze Zahlen.
- Finden des kürzesten Weges zwischen zwei Knoten in einem zusammenhängenden Graphen.
- Entscheiden, ob es sich bei einer vorliegenden natürlichen Zahl um eine Primzahl handelt.
- Berechnung des Integrals bei vorliegenden Funktionswerten in einem bestimmten Bereich.
- Finden einer Lösung in einem vorgegebenen Lösungsraum.
Was sind grundlegende Eigenschaften eines Algorithmus?
- schrittweises Verfahren
- ausführbare Schritte
- eindeutiger nächster Schritt (determiniert)
- endet nach endlich vielen Schritten (terminiert)
Der Computer ist DER "Algorithmen-Cruncher". Anhand von was kann man sehen?
- arbeitet schrittweise, gemäss Programm
- Anweisung für Anweisung, jede Anweisung korrespondiert mit einem ausführbaren Befehl
- arbeitet präzise und schnell
Algorithmen sind ein zentrales Thema in der Informatik und in der Mathematik. Zeige Beispiele.
- Algorithmentheorie: Guter Lösungsalgorithmus für bestimmte Problemstellung?
- Komplexitätstheorie: Ressourcenverbrauch von Rechenzeit und Speicherbedarf?
- Berechenbarkeitstheorie: Was ist mit einer Maschine grundsätzlich lösbar bzw. nicht lösbar?
Was ist die Definition einer Datenstruktur?
Eine Datenstruktur ist ein Konzept zur Speicherung und Organisation von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung möglichst effizient zu ermöglichen. Datenstrukturen sind daher insbesondere auch durch die Operationen charakterisiert, welche Zugriff und Verwaltung realisieren.
Beispiele:
Array: direkter Zugriff (+), fixe Grösse (-)
Liste: flexible Grösse (+), sequentieller Zugriff (-)
Algorithms + Data Structures = Programs. Erläutere.
Bei vielen Algorithmen hängt der Ressourcenbedarf, d.h. sowohl die benötigte Laufzeit als auch der Speicherbedarf, von der Verwendung geeigneter Datenstrukturen ab.
Algorithmen operieren auf Datenstrukturen und Datenstrukturen bedingen spezifische Algorithmen. Beides ist untrennbar miteinander verbunden!
Welche Fragen stellen sich betreffend Algorithmen und Datenstrukturen?
- Adäquat für kleine Probleme? Adäquat für grosse Probleme?
- Selber entwickeln oder aus Bibliothek wählen?
- Einfach zu verstehen, zu implementieren, zu warten oder schwierig?
- Schneller Algorithmus mit grossem Speicherbedarf oder umgekehrt?
Extrembeispiel: Ist n eine Primzahl, ja/nein?
- Prüfen, ob n durch 2, 3, 4, 5, 6, … , sqrt(n) ganzzahlig teilbar. Wenig Speicher, lange Rechenzeit
- Alle Primzahlen 2, 3, 5, 7, 11, … im Voraus in einer Tabelle abspeichern. Viel Speicher, schnell (natürlich kann man dies praktisch nur für eine endliche Anzahl Primzahlen tun)
Wie sieht der euklidische Algorithmus zur ggT-Berechnung aus?
Ermittlung des grössten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen A und B:
(siehe Bild)
Wie sieht der euklidische Algorithmus zur Berechnung des ggT von Hand ausgeführt?
(siehe Bild)
Wie sieht der euklidische Algorithmus zur Berechnung des ggT als iterative Implementation?
(zwei Beispiele)
(siehe Bild)
1. Beispiel (ohne Modulo): weniger optimiert
2. Beispiel (mit Modulo): optimiert
Wie sieht der euklidische Algorithmus zur Berechnung des ggT als rekursive Implementation?
(siehe Bild)
Was ist das Fazit der unterschiedlichen Implementierungen des euklidischen Algorithmus zur Berechnung des ggT?
- Alle Implementierungen basieren auf Euklid.
- unterschiedliche Ansätze: Schleifen vs. Rekursion
- "Abkürzungen": Modulo-Operation anstelle x-mal A-B
- unterschiedliche Anzahl Schleifendurchläufe
- Ausführungsgeschwindigkeit
- unterschiedliche Anzahl Methodenaufrufe
- unterschiedlicher Speicherbedarf
- Alle Implementierungen liefern die gleichen Resultate (gemäss Testing).
- Alle Implementierungen sind gleichwertig.
Die Gleichwertigkeit von Algorithmen allgemein zu beweisen ist ein unlösbares Problem. Was bedeuted dies?
Dies bedeutet, dass es kein Java-Programm geben kann, das den Quellcode von zwei Implementationen einliest und feststellt, ob sie gleichwertige Algorithmen repräsentieren oder nicht!
Was ist die Definition von Komplexität in Algorithmen & Datenstrukturen?
- Komplexität (auch Aufwand oder Kosten) eines Algorithmus:
Ressourcenbedarf = f (Eingabedaten). D.h. «Wie hängt der Ressourcenbedarf von den Eingabedaten ab?»
- Ressourcenbedarf:
Rechenzeit -> Zeitkomplexität, Speicherbedarf -> Speicherkomplexität
- Eingabedaten:
Grösse der Datenmenge (z.B. 100 vs. 1'000'000'000 zu sortierende Elemente), Grösse eines Datenwertes (z.B. 10! vs. 1'000'000'000!)
Was uns interessiert uns weiter bei der Frage:
Wie wächst der Ressourcenbedarf, wenn mehr Daten zu verarbeiten sind?
- Bleibt der Ressourcenbedarf gleich, wenn wir den ggT von zwei sehr grossen Zahlenwerten berechnen wollen?
- Verdoppelt oder vervierfacht sich der Ressourcenbedarf für das Sortieren der doppelten Datenmenge?
Was interessiert uns nicht weiter bei der Frage:
Wie wächst der Ressourcenbedarf, wenn mehr Daten zu verarbeiten sind?
Der exakte / absolute Ressourcenbedarf!
- Z.B., die ggT-Berechnung von 1’000’000’489 und 9’123’000’124 auf dem Computer XY mit der Konfiguration Z dauert 0.42 Sek.
- Vgl., solche Rechenzeiten sind für jeden Computer anders. Möchte man die Rechenzeit reduzieren, so lässt sich jederzeit ein schnellerer Computer kaufen! (bessere Hardware)
Wie das "Aha-Beispiel" zur Zeitkomplexität (Rechenzeit T = f(n)) aus der Vorlesung?
(siehe Bild)
Wie sieht das "Aha-Beispiel" zur Zeitkomplexität aus der Vorlesung für grosse n?
(siehe Bild)
Was ist die Definition von "Big-O-Notation"?
Die Big-O-Notation (landau’sches Symbol) bringt zum Ausdruck, dass eine Funktion f(n) höchstens so schnell wächst wie eine andere Funktion g(n). g(n) ist die obere Schranke für f(n).
-
- 1 / 134
-
Cartes-fiches
Es gibt verschiedene Datenstrukturen mit unterschiedlichen Fähigkeiten und Eigenschaften
ArrayList ist nicht ein Beispiel einer häufig eingesetzten, konkreten Datenstruktur in Java
Die Auswahl der geeigneten Datenstruktur erfolgt aufgrund der konkreten Anforderungen, z.B.?
Aufgrund der Eigenschaften wie Zugriffsart, Art und Häufigkeit der Operationen, Datenmenge und –struktur
Wie sind die Daten in einer Datenstruktur, welche als reine Sammlung implementiert ist, abgelegt?
Die einzelnen Datenelemente sind darin ungeordnet abgelegt und die Reihenfolge ist nicht deterministisch. - Analogie: Steinhaufen.
Welche drei grundsätzliche Sortierungen und Reihenfolgen verwendet man oft bei Datenstrukturen?
(siehe Bild)
Es gibt einige elementare Methoden die auf Datenstrukturen angewendet werden können. Welche sind diese?
- Einfügen von Elementen
- Suchen von Elementen
- Entfernen von Elementen
- Ersetzen von Elementen
in Datenstrukturen.
Nenne Operationen in Abhängigkeit einer (optionalen) Reihenfolge oder Sortierung.
- Nachfolger: nachfolgendes Datenelement.
- Vorgänger: vorangehendes Datenelement.
- Sortierung: Sortieren der Datenelemente nach best. Kriterien.
- Maxima/Minima: kleinstes / grösstes Datenelement.
Eine statische Datenstruktur hat nach ihrer Initialisierung eine feste, unveränderliche Grösse. Sie kann somit nur eine beschränkte Anzahl Elemente aufnehmen. Überlege eine Analogie mit einer Getränkeflasche.
- Grösse der Flasche ist gegeben, ebenso maximaler Inhalt.
- Die Flasche selber nimmt immer den selben Platz ein!
Eine dynamische Datenstruktur hingegen kann ihre Grösse während der Lebensdauer verändern. Sie kann somit eine beliebige (durch verfügbaren Speicher begrenzt) Anzahl Elemente aufnehmen. Überlege eine Analogie mit einem Luftballon.
Je nach Gasvolumen dehnt sich der Luftballon räumlich aus oder zieht sich wieder zusammen
Benutze eine Analogie zu einer Fahrradkette um explizite Datenstrukturen zu erklären.
Analogie: Fahrradkette
- Kettenglieder sind miteinander verknüpft.
- Kettenglieder kennen ihre jeweiligen Nachbarglieder.
Was ist eine explizite Datenstruktur?
Bei expliziten Datenstrukturen werden die Beziehungen zwischen Elementen von jedem Element selber explizit mit Referenzen festgehalten.
Was ist eine implizite Datenstruktur?
Bei impliziten Datenstrukturen werden die Beziehungen zwischen den Datenelementen nicht von den Elementen selber festgehalten.
- Die Beziehungen werden quasi von «aussen» definiert, z.B. über eine externe Nummerierung.
Benutze eine Analogie zu einem Buchregal mit Büchern um eine implizite Datenstruktur zu erklären
Analogie: Buchregal mit Büchern
- Bücher stehen einfach (ggf. auch geordnet) nebeneinander.
- Das einzelne Buch weiss nicht wo es steht bzw. hingehört.
Was heisst es, wenn man bei einer Datenstruktur direkten Zugriff hat?
(Hilfe: Analogie Buchregal mit Büchern)
Bei direktem Zugriff hat man auf jedes einzelne Element direkten und unmittelbaren Zugriff.
Analogie: Buchregal mit Büchern.
- Alle Bücher stehen nebeneinander im Regal.
- Man kann jedes Buch direkt herausnehmen.
Was heisst es, wenn man bei einer Datenstruktur indirekten Zugriff hat?
(Hilfe: Tellerstapel in der Mensa)
Bei indirektem Zugriff hat man keinen direkten Zugriff auf bestimmte, einzelnen Datenelemente. Man kann allenfalls sequenziell ein Element nach dem anderen erhalten.
Analogie: Tellerstapel in der Mensa
- Man kann «einen» Teller nehmen, aber keinen bestimmten.
- Möchte man einen bestimmten Telle (oder alle), muss alle Teller sequenziell umstapeln bis der gewünschte Teller
gefunden ist.
Für was variiert der Aufwand von Operationen (Rechen- und Speicherkomplexität) in einer Datenstruktur?
Der Aufwand (Rechen- und Speicherkomplexität) variiert sowohl für die verschiedenen Operationen als auch oft in Abhängigkeit der enthaltenen Elementmenge in einer Datenstruktur.
Die Ordnung, also wie sich der Aufwand von Operationen in einer Datenstruktur in Abhängigkeit zur Anzahl Elemente verhält, interessiert uns nie
Meistens interessiert uns "nur" die Ordnung, also wie sich der Aufwand von Operationen in einer Datenstruktur in Abhängigkeit zur Anzahl der Elemente verhält
Meistens interessiert uns «nur» die Ordnung, also wie sich der Aufwand von Operationen in einer Datenstruktur in Abhängigkeit zur Anzahl der Elemente verhält.
Nenne Beispiele im Alltag
Beispiele:
- Buch auf einen Stapel legen (ungeordnet): -> O(1) Konstant
- Buch in der Bibliothek alphabetisch einordnen: im schlechtesten Fall O(n) Linear
- Eine unsortierte Menge von Büchern alphabetisch Ordnen: im schlechtesten Fall O(n2) Quadratisch (Polynomial)
Was kann man über dieses Bild sagen? (Array)
- Ein char-Array mit Platz für maximal 16 (length) Elemente
- Der Array ist «voll», alle Positionen sind belegt
- Die Elemente sind sortiert eingefügt
Was kann man über dieses Bild sagen?
- Ein char-Array mit Platz für maximal 8 (length) Elemente
- Der Array hat noch vier freie Plätze
- Die Elemente sind weder sortiert noch fortlaufend eingefügt
Empfehlung: Leere Plätze mitten im Array möglichst vermeiden!
Was sind Eigenschaften einer Array?
(siehe Bild)
Wir suchen nach einem Element G. Wie gross ist der Aufwand, wenn der Array unsortiert ist, aber fortlaufend befüllt wird?
Wir müssen den Array sequenziell durchsuchen.
Der Aufwand beträgt: O(n)
Wir suchen nach einem Element G. Wie gross ist der Aufwand, wenn der Array sortiert ist?
Wir können binär Suchen, der Aufwand beträgt somit: O(log n)
Was ist die Hauptvoraussetzung für binäres Suchen?
sortierte Datenmenge!
Wie funktioniert binäres Suchen?
(siehe Bild)
Wie gross ist der Aufwand, wenn man ein Element "C" einer Array anhängt, wenn der Array unsortiert ist, aber fortlaufend befüllt wird?
Wenn wir uns den Index des jeweils nächsten freien Platzes merken beträgt der Aufwand: O(1) -> Konstant
(siehe Bild)
Ohne diesen Trick: O(n)
Wie gross ist der Aufwand, wenn man ein Element "C" einer Array anhängt, wenn der Array sortiert ist?
Wir können zwar binär mit O(log n) die Position suchen, müssen dann aber die restlichen Elemente mit O(n) nach rechts schieben.
(siehe Bild)
Aufwand: O(log n) + O(n) -> O(n)
Wie gross ist der Aufwand, wenn man ein Element "C" von einer Array enfernt, wenn der Array unsortiert ist, aber fortlaufend befüllt wird?
- Wir müssen den Array sequenziell mit O(n) durchsuchen und können die Lücke mit dem letzten Element mit O(1) schliessen
(siehe Bild)
Aufwand: O(n) + O(1) -> O(n)
Wie gross ist der Aufwand, wenn man ein Element "C" von einer Array entfernt, wenn der Array sortiert ist?
- Wir können zwar binär mit O(log n) suchen, müssen die entstehende Lücke aber durch Linksrücken mit O(n) schliessen
(siehe Bild)
Aufwand: O(log n) + O(n) -> O(n)
Arrays sind statische Datenstrukturen, darum sollten sie nur verwendet werden, wenn was?
Wenn die Datenmenge klar beschränkt, von Anfang an bekannt, und eher klein ist
Wann sind Arrays effizient?
Wenn man «nur» einzelne, elementare Datentypen ablegen muss.
- Datentypen haben bekannte Grösse, und können somit in einer Reihung direkt als/im Array abgelegt werden. Mit dem Index kann direkt die Speicheradresse berechnet werden.
Wenn man nicht "nur" einzelne, elementare Datentypen ablegen muss, sind Collections den Arrays meist vorzuziehen. Weshalb?
da sie wesentlich objektorientierter sind, und es z.B. mit der ArrayList ebenfalls Implementationen gibt, die einen direkten, schnellen Zugriff per Index erlauben
Was ist eine einfach verkette Liste?
- Es gibt eine Referenz auf das erste Element -> head
- Jedes Element kennt seinen direkten Nachfolger
Was ist eine doppelt verkettete Liste?
- Es gibt Referenzen auf das erste (-> head) und das letzte (-> tail) Element in der Liste
- Jedes Element kennt seinen direkten Vorgänger und Nachfolger
Was sind die wichtigsten Eigenschaften eine Liste?
(siehe Bild)
Wie gross ist der Aufwand bei der Suche nach dem Element "G" in einer Liste?
Da wir keinen direkten Zugriff haben (sondern nur sequenziell) beträgt der Aufwand für die Suche eines Elementes in einer Liste grundsätzlich O(n).
- Unabhängig davon ob sortiert oder unsortiert.
- Unabhängig davon ob einfach oder doppelt verkettet.
Lässt sich der Aufwand bei der Suche nach einem Element "G" bei einer sortierten Liste von O(n) auf O(log n) reduzieren?
Ja, die Suche lässt sich bei sortierten Listen mit zusätzlichen Hilfsmitteln (-> Skiplisten) beschleunigen.
Damit wird ebenfalls O(log n) möglich
Wie gross ist der Aufwand beim Ergänzen eines Elementes "C" einer unsortierten Liste?
Dazu handelt es sich um eine einfach verkettete Liste!
Einfach verkettete Liste:
Da wir mit dem Head eine Referenz auf das erste Element haben, können neue Element am Anfang einfach und schnell eingefügt werden. Der Aufwand beträgt: O(1)
Wie gross ist der Aufwand beim Ergänzen eines Elementes "C" einer unsortierten Liste?
Dazu handelt es sich um eine doppelt verkettete Liste!
Bei doppelt verketteter Liste:
Analog kann zusätzlich auch am Ende der Liste (tail) mit Aufwand O(1) eingefügt bzw. angehängt werden.
