Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithmen und Datenstrukturen (Java (Lists (Java.util.set (Treeset…
Algorithmen und Datenstrukturen
Algorithmen
Rekursion
Aufteilung von Problemen in kleinere,
direkt lösbare
Probleme
Türme von Hanoi (Beispiel)
Module als aufrufbare Unterprogramme
Abläufe
Deterministischer Ablauf
Eindeutig definierter Ablauf
Determiniertes Ergebnis (injektive Abbildung)
Regeln
Semantik
I/O Funktion
Bedeutung einer Aussage und deren Sinnhaftigkeit
Syntax
Formale regeln, welche Satzmuster gebildet werden können
Grammatiken
Regelwerk zur Beschreibung der Syntax einer Sprache
Reguläre Ausdrücke
Worte (kleinster Satzbestandteil)
Sequenz
Klammerung
Punkt vor Strich
Auswahl
Iteration
Backus-Naur-Form
Einteilung in Syntaxbausteine
Bausteine
Elementare Operationen
Ausführung
Sequenziell
Sequenz
Parallel
Bedingt (if)
Schleife/Loop
Illustration
Struktogramme
Datentypen
Algebren
Terme
Operatoren(+,-,*,/)
Varianten
Boolean
Integer
Float
Double
String
Char
Array
Matrix
Vektoren
= Datentypkonstruktor
Arten
Primitive Datentypen
Numerische
Zeichen
Boolean
Referenzdatentypen
Array
Methode System.arraycopy
Objekte
Arten
Applikative (Rekursion, verallgemeinern der Funktionsauswertung)
Terme mit unbestimmten
Imperative
Gespeicherte und änderbare Werte, Schleifen und Alternativen
Deduktive
Flexiblere Berechnungsvorschrift
Backtracking
Alle möglichen Berechnungspfade werden systematisch ausprobiert
Klassen
Stringbuffer
Erlaubt Veränderung von Strings ( im Gegensatz zur String Klasse)
Java
Blöcke { }
Anweisungen
Ausdrücke
Eingeleitet durch ;
Kontrollstrukturen
Ausnahmebehandlung etc.
Overloading
Methode mit Eingabewerteb unterschiedlichen Datentyps entscheidet automatisch anhand des überlieferten Datentyps
Void print(int i)
Void print(String s)
Vererbung
Objektreferenzen können auch auf Objekte von Unterklassen verweisen
JCF
Java Collection Framework
Lists
Arraylists
Besser bei zugriff auf bestimmte Position, wenn hauptsächlich als letztes Element neu eingefügt wird
Linkedlists
Besser beim
einfügen
an bedtimmer position
Java.util.set
Jedes Element kann nur 1 mal vorkommen
Hashset
override
void hashcode
Bestimmung der Speicherposition
Treeset
implements
java.lang.comparable
Java.util.Collections
Methoden zur Sortierung und zum Suchen
void sort!!
Dannach andere methoden verwenden
Sortiert Objekte der größe nach (int, double, float)
Class binary tree
Class Treenode
Preorder
Postorder
Java.lang.iterable
Ermöglicht Iteration von Objekten
Ausgewählte Algorithmen
Binäre Suche
Halbiert immer wieder Wertebereich und vergleicht mit gesuchter Variable um wieder zu halbieren
Sortieren durch einfügen
Vergleicht mit allen elementen des Arrays welche vom Index kleiner sind und geht so lange weiter runter, bis vergleichende Zahl größer ist als die gespeicherte Zahl
Sortieren durch Selektion
Größtes Element der Folge wird immer mit kleinetem Element getauscht, Bereich wird un 1 verkleinert , bis Liste Sortiert ist
N^2/2 Vergleiche nötig
Diese Anzahl ist gleichbleibend
Bubblesort
Elemente so lange miteinander Vergleichen bis kein Element mehr kleiner ist/größer ist
Mergesort
Einteilen in sortierte Teilfolgen der Ursprungsfolge
Erst zerlegen der Folge in einelementige Folgen
Dann wieder zusammenmischen mit bestimmten Eigenschaften der Verfahren
Quicksort(Teile und Herrsche)
Wie Mergesort aber ohne Mischvorgang, Folge wird in 2 Teile geteilt und separat sortiert
Registermaschinen
Load
Wert des i-ten registers wird in Akkumulator geladen
Werte können dann Mittels Befehlen manipuliert werden
Add, sub, mult und div
Rechenoperationen des Akkumulators mit dem Wert des jeweiligen Registers
Cload
Siehe Load
Store
Speichere Wert des Akkumulators im i-ten register
Vorgehensweise
Erst einmal Anforderungen/Ziele aufschreiben
Dann in Pseudocode formulieren
Immer Detaillierter gestalten
So lange bis Code in Programmiersprache vorliegt
Objekte
Identität
Eigenschaft(en) die das Objekt von anderen Unterscheidet
Adresse des Objektes im Speicher
Attribute
Statische Eigenschaften zur Darstellung des Zustandes
Methoden
Dynamische Eigenschaften die das Verhalten beschreiben
Java Pakete
Java.lang
Sprache
Wurzelklasse
Java.lang.object
Beinhaltet einige wichtige Methoden für sämtliche Java Klassen
Java.util
Datenstrukturen
Listen
Felder
Usw.
Java.io / java.net
Ein/Ausgabe
Arbeit mit Dateien,Verzeichnissen, Netzwerkverbindungen
Java.awt / javax.swing
Grafische Benutzerschnittstellen, Fenster, Schaltflächen, Schieberegler
Wrapper Klassen
Integer
Double
Byte
Datenstrukturen
Bäume
B Bäume
Für Zahlen etc.
Auch bei sehr vielen Einträgen sehr schnell
Tries
Für Zeichenketten
Avl-Bäume
Rot schwarz Bäume
Patricia Baum
Ansatz um zu Listen entartete Bäume zu vermeiden!!
HeapSort
Vollständig von links nach rechts gefüllt
Geeignet als Prioritätsqarteschlange
Elternteil immer kleiner als Kinderteile, jedoch keine Sortierung von links nach rechts