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
Was ist der Heap?
In diesem Speicherbereich werden die Objekte gespeichert, d.h. deren Instanzvariablen bwz. Zustände. Nicht mehr referenzierbare Objekte werden durch den Garbage Collector (GC) automatisch gelöscht
Was ist der Call Stack?
Letztendlich wird bei der Ausführung eines Java-Programms eine Kette von Methoden aufgerufen/abgearbeitet. Ursprung ist die main()-Methode. Jeder Methodenaufruf bedingt gewissen Speicher, insbesondere für ihre aktuellen Parameter und lokalen Variablen. Dazu dient der Call Stack. Ein neuer Methodenaufruf bewirkt, dass der Call Stack wächst bzw. darauf ein zusätzlicher -> Stack Frame angelegt wird.
Wie sieht der Call Stack in Aktion aus?
(siehe Bild)
Mächtigkeit der Rekursion:
Erläutere das Bild
- Rekursion und Iteration sind gleich mächtig
- D.h. die Menge der berechenbaren Problemstellungen bei Verwendung der Rekursion und Verwendung der Iteration ist gleich.
- D.h. eine rekursive Implementation lässt sich grundsätzlich immer in eine gleichwertige iterative Implementation umprogrammieren und umgekehrt.
(Hinweis: Dies gilt exakt nur für sogenannte primitiv-rekursive Probleme, d.h. bei linearer und nicht geschachtelter Rekursion bzw. bei reinen Zählschleifen)
Welche Motivation haben wir für die Rekursion?
- mächtiges Lösungskonzept
- häufig einfache und elegante Problemlösungen
- weniger Quellcode
- Korrektheit häufig einfacher zu zeigen
- z.B. kennen die Programmiersprachen (Lisp: List Processing, Prolog: Programming in Logic) nur Rekursion!
Was sind Tücken der Rekursion?
- schnell sehr viele Methodenaufrufe
- tendenziell langsamere Programmausführung
- grosser Speicherbedarf auf dem Call Stack
- Gefahr eines Stack Overflow!
Bei Wahlmöglichkeit eine iterative Implementation bevorzugen!
Weshalb sollten Fibonacci-Zahlen zum Beispiel nicht rekursiv umgesetzt werden, obwohl es sich rekursiv präsentiert?
(siehe Bild)
Welche Rekursions-Typen gibt es?
- lineare Rekursion
- nichtlineare Rekursion
- direkte Rekursion
- indirekte Rekursion
Erläutere lineare Rekursion
(siehe Bild)
Erläutere nichtlineare Rekursion
Die Ausführung der Methode m(...) führt zu mehr als einem rekursiven Aufruf.
Erläutere direkte Rekursion
Eine rekursive Methode ruft sich direkt selbst auf
Erläutere indirekte Rekursion
Eine rekursive Methode ruft sich indirekt selbst auf (siehe Bild)
Beispiel Permutation (Passwort Cracking)
Jemand hat sein Passwort vergessen. Es war sechs Zeichen lang. Im Passwort kamen nur die Buchstaben von A bis F vor und jeder Buchstabe nur einmal. Wie viele verschiedene Passwörter bzw. Buchstaben-Kombinationen muss er/sie durchprobieren?
Mit anderen Worten: Gefragt sind alle Permutationen der Buchstaben A bis F?
Also 6 ・5 ・4 ・3 ・… ・1 = 6! Permuationen
Im Falle von nur drei Buchstaben A, B und C ergeben sich diese Permutationen: ABC, BAC, CBA, BCA, ACB, CAB.
Eine entsprechende Methode soll alle Permutationen ausgeben (siehe Bild)
Wie sieht diese Implementation in Java aus?
(siehe Bild)
Siehe die Problemstellung im Bild.
Wie sieht die rekursive Lösungsstrategie und dessen Implementation in Java aus?
(siehe Bild)
Selbstähnlichkeit bzw. Rekursion findet sich bei Algorithmen und __________.
Datenstrukturen
Stimmt diese Aussage?
Iteration und Rekursion sind zentrale aber nicht gleich mächtige Konzepte in der Programmierung.
Nein, sie sind praktisch gleich mächtige Konzepte. Je nach Fall muss entschieden werden, welches Konzept besser geeignet ist.
Stimmt diese Aussage?
Rekursive Lösungen sind häufig elegant und einfach, haben aber ihre Tücken!
Ja
Bei einer rekursiven Methode unterscheidet man zwischen Rekursions-(1)______ und Rekursions-(2)__________ .
(1) Rekursionsbasis
(2) Rekursionsvorschrift
Für was ist die Rekursionsbasis da?
Für den Rekursionsabbruch
Für was ist die Rekursionsvorschrift da?
Beinhaltet die eigentliche Rekursion
Stimmt diese Aussage?
Auf dem Heap werden die Methoden gespeichert bzw. abgearbeitet und auf dem Call Stack werden die Objekte gespeichert.
Nein, es ist genau umgekehrt:
Auf dem Heap werden die Objekte gespeichert und auf dem Call Stack die Methoden gespeichert bzw. abgearbeitet
Was sind Datenstrukturen?
Datenstrukturen werden verwendet, um Mengen von Daten bzw. Objekten effizient zu speichern und verarbeiten zu können
Was versteht man unter Verarbeitung von Mengen von Daten? (Datenstrukturen)
Unter Verarbeitung versteht man Funktionen, wie z.B. alle enthaltenen Daten/Objekte einzeln zu bearbeiten, nach bestimmten Ojekten zu suchen, zu zählen, zu filtern oder nach unterschiedlichen Kriterien zu sortieren etc.
Es gibt verschiedene Arten von Datenstrukturen. Nenne Beispiele.
(siehe Bild)
Java bietet für jede Art von Datenstruktur jeweils nur eine Implementation dieser Datenstruktur an.
Java bietet für jede Art von Datenstruktur wiederum verschiedene Implementationen dieser Datenstrukturen an, um den unterschiedlichen Anforderungen gerecht zu werden -> Java Collections Frameworks
Eine universelle Datenstruktur, die alles perfekt kann, gibt es (leider) nicht, wir müssen fallspezifisch auswählen!
Die verschiedenen Datenstrukturen unterscheiden sich in vielerlei Hinsicht. Nenne Beispiele in denen sie sich unterscheiden.
(siehe Bild)
Anhand von was (und den teilweise damit eng verbundenen Algorithmen), sollten wir für jeden Anwendungsfall gezielt die geeignetste Datenstruktur auswählen?
Anhand der Eigenschaften der Datenstrukturen
Das Collection Framework besteht aus welchen drei wesentlichen Inhalten?
Interfaces, Implementationen und Algorithmen
Das Collection Framework besteht aus den drei wesentlichen Inhalten: Interfaces, Implementationen und Algorithmen. Erläutere diese Inhalte.
(siehe Bild)
Was zeigt dieses UML (siehe Bild)?
Ein unvollständiger Auszug aus den vorhandenen Schnittstellen der Java Collection Framework
Damit die polymorphen Algorithmen und Datenstrukturen des Collection Frameworks mit beliebigen Elementen funktionieren können, benötigen wir ein paar grundlegende Funktionen. Um welche grundlegende Funktionen handelt es sich?
- Für die Suche von Objekten (oder Verhindern von Duplikaten) müssen wir Objekte als «gleich» erkennen können.
- Für die Sortierung müssen wir Objekte vergleichen und als kleiner (<), gleich (=) oder grösser (>) beurteilen können.
Damit die polymorphen Algorithmen und Datenstrukturen des Collection Frameworks mit beliebigen Elementen funktionieren können, benötigen wir ein paar grundlegende Funktionen:
- Für Suche von Objekten müssen wir Objekte als «gleich» erkennen können
- Für Sortierung müssen wir Objekte vergleichen und als kleiner, gleich oder grösser beurteilen
(1) Die Klasse Object definiert deswegen, welche dafür notwendige Methoden?
(2) Welche Interfaces müssen wir deswegen ggf. implementieren?
(1) equals(), hashCode()
(2) Comparable<T> oder Comparator<T>
Zeige ein Beispiel einer ArrayList im Einsatz
(siehe Bild)
Mache eine vereinfachte Annahme zu wie das Betriebssystem Speicher verwaltet
(siehe Bild)
Schaue die Annahme zur Speicherverwaltung eines Betriebssystem im Bild an und überlege:
- Was passiert nun, wenn man versucht einen Block mit malloc(7) anzufordern?
- Was passiert, wenn man auch noch free(yellow) freigibt?
(siehe Bild)
Was sind die wichtigsten Anforderungen an die Speicherverwaltung?
- soll zuverlässig sein (wertvoller Speicherplatz soll nicht verloren gehen)
- Allokation sollen schnell sein (keine lange Such nach einem in der Grösse passenden Block)
- schnelle Freigabe
- Mit der Zeit entstehen Lücken sowohl durch belegten als auch freien Speicher (Fragmentierung).
- Liegen freie Lücken nebeneinander, sollten diese in der Datenstruktur wieder zusammengefasst werden!
- Gute Frage dazu: Welche Datenstruktur(en) mit welchen spezifischen Eigenschaften (Sortierung, Suche etc.) eignet sich dafür am Besten?
Was zeigt dieses UML (siehe Bild)?
Speicherverwaltung.
Ein einfacher erster Ansatz zur Modellierung als Inspiration.
Auswahl und Einsatz von Datenstrukturen in der Speicherverwaltung ist _____ stark von den eingesetzten Algorithmen abhängig.
