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
-
Flashcards
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).
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).
Wie sieht die Funktion f(n) aus?
(siehe Bild)
Nenne wichtige Ordnungsfunktionen
(siehe Bild)
Wie sieht die Handhabung der Big-O-Notation aus?
(siehe Bild)
Abschliessende Bemerkung zu Big-O-Notation
Die Ordnung ignoriert _______ Faktoren. Diese können aber praktisch relevant sein!
Abschliessende Bemerkung zu Big-O-Notation
Die Ordnung berücksichtigt das Verhalten bei _______ n nicht. Langsamere Algorithmen sind aber bei _______ n oft auch brauchbar oder gar die bessere Wahl!
Abschliessende Bemerkung zu Big-O-Notation
Die exakte mathematische Analyse von vielen Algorithmen ist (1)________ oder sogar (2)__________!
Abschliessende Bemerkung zu Big-O-Notation
Häufig muss man bei der Analyse differenzieren:
- bester Fall (best Case)
- schlimmster Fall (wort Case)
- mittlere Fall (average Case)
Welcher Fall ist das bessere Mass für die Leistung eines Algorithmus?
Häufig ist der mittlere Fall ein besseres Mass für die Leistung eines Algorithmus, als der schlimmste.
Ein Algorithmus ist ein Lösungsverfahren für eine Problemklasse
Algorithmen und Datenstrukturen sind _________ miteinander verbunden
Für eine Problemklasse gibt es typisch _______ Lösungs-Algorithmus/Algorithmen
Unter Komplexität eines Algorithmus versteht man __________ in Abhängigkeit der Eingabedaten.
Beid en Ressourcen geht es um was?
Rechenzeit und Speicherbedarf
Stimmt diese Aussage?
Es interessiert insbesondere, wie sich der Ressourcenbedarf bei einem bestimmten Algorithmus bei kleinen Problemen entwickelt.
Nein
Es interessiert insbesondere, wie sich der Ressourcenbedarf bei einem bestimmten Algorithmus bei grossen Problemen entwickelt.
Was ermöglicht die Big-O-Notation vielfacht?
Eine adäquate Qualifizierung
Grundlegendes zur Rekursion:
Viele Algorithmen und Datenstrukturen sind von Natur aus selbstähnlich bzw. selbstbezüglich.
Nenne Beispiele wo dies ersichtlich ist.
(siehe Bild)
Wie sieht eine iterative Fakultätsberechnung anhand einer Implementation?
(siehe Bild)
Wie geht man vor bei einer rekursiven Fakultätsberechnung vor?
(siehe Bild)
Berechne 5! rekursiv
(siehe Bild)
Wie sieht eine rekursive Fakultätsberechnung anhand einer Implementation aus?
(siehe Bild)
Für die Ausführung eines Programmes verwendet die Java Virtual Machine (JVM) welche zwei wichtige Speicher?
Heap und Call Stack
