T&A AD Lernkarten
Lernkarten für AD
Lernkarten für AD
Set of flashcards Details
| Flashcards | 26 |
|---|---|
| Language | Deutsch |
| Category | Computer Science |
| Level | University |
| Created / Updated | 23.05.2017 / 23.06.2017 |
| Weblink |
https://card2brain.ch/box/20170523_ta_ad_lernkarten
|
| Embed |
<iframe src="https://card2brain.ch/box/20170523_ta_ad_lernkarten/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Was ist ein Algorithmus?
Einfach: Lösungsverfahren (Rezept, Anleitung)
oder: präzise festgelegtes Verfahren zur Lösung eines Problemes / Problem Klasse.
Welche Eigenschaften müssen Algorithmus haben (4)
- schrittweises Verfahren
- ausführbare Schritte
- eindeutiger nächster Schritt (deterministisch)
- endet nach vielen Schritten (terministisch)
Was ist eine Datenstruktur?
Konzept zur Speicherung und Organisation von Daten.
Struktur -> Anordnung zum Verwalten der Dateien
Operationen -> Ermöglichen Zugriff
(alg. Datenstruktur s9)
Was ist Komplexität?
Resourcenbedarf = f(Eingabedaten)
Eingabedaten:
Datenmende
Datenwerte
Resourcen:
Rechenzeit - Zeitkomplexität
Speicherbedarf - Speicherkomplexität
Big-O notationen - Auflisten
O(1)
O(log(n))
O(n)
O(log(n) * n)
O(n^m)
O(d^n)
O(n!)
Big O auf kleinen algorithem anwendbar?
Nein - da konstante Faktoren wichtig werden
Langsame algorithmen könne io. sein
Datenstrukturen Eigenschaften (3)
explizit / implizit - parent hat referenz / hat referenz
statisch / dynamisch - grösse on init / dynamische grösse
direkt / indirekt - zugriff direkt möglich / indirekt über refenzen
Rekursion Positiv (4+1) negativ (4)
positiv
- mächtiges Lösungskonzept
- häufig einfache und elegante Lösung
- weniger Quellencode
- Korrektheit häufig einfacher nachweisbar
- spezielle Programmiersprachen: Lisp, Prolog
negativ:
- schnell viele methodenaufrufe
- tendenziell langsamer als iterativ - da viele methodenaufrufe
- grosser call-stack benötigt
- gefahr - stack overflow
Datenstruktur - mögiche Eigenschaften bezüglich Reihenfolge (3)
- unsortiert - einfach einfügen
- Datenelemente behalten ihre Reihenfolge
- Datenstrukur ist immer sortiert
Datenstrukturen - elementare methoden
Basic:
Einfügen
Suchen
Ersetzen
Entfernen
Reihenfolge spezifisch:
Nachfolger
Vorgägner
Sortieren
Maximum / Minimum
Array Ordnung - einfügen / entfernen & Eigenschaften
einfügen:
unsoritert : O(1)
sortiert: O(log n) + O(n) => O(n)
Entfernen:
sortiert: O(log n) + O(n) => O(n)
unsortiert: O(n)
suche:
sortiert: O(log n)
unsortiert: O(n)
Eigenschaften:
statisch
explizit
direkt
Reihenfolge
Liste Ordnung - Einfügen & Entfernen & suche + Eigenschaften + Typen(2)
Einfügen:
sortiert: O(log n) (wenn skip-list) -> sonst O(n)
unsortiert: O(1)
entfernen:
sortiert: O(log n) (wenn skip-list)
unsortiert: O(n) (suchen & entfernen -> indirekt)
Suche:
sortiert: O(log n) (wenn skip-list)
unsortiert: O(n)
Eigenschaften:dynamisch
implizit
indirekt
Reihenfolge
Typen:
einfach (tale)
doppelt (tale + head)
Stack - funktionen / Java-Implementationen / vergleich List <-> Array
push() - O(1) / pop() - O(1)
Java-Imp.:
ArrayDeque
LinkedList
Deque
Array:
+ Platz reserviert
+ schnelles einfügen
- beschränkte grösse
List:
+ Leerer Stack sehr klein
+ dynamische Grösse
- etwas langsamer - da Speicher muss platz gemacht werden
Queue - function / Java-Implementation / vergleich List <-> Array
offer() O(1) / poll() O(1)
enqueue / dequeue
Java-Implementationen
LinkedList
ArrayDeque
Deque<I>
List:
+ leere queue fast kein platz
+ dynamische grösse
- etwas längsämer - speicherreservation
Array:
+ maximaler Platz bereits reserviert
+ daher schnell
- statische Grösse
Wieso Bäume? (2)
- Daten haben hirarchische Struktur
- Binärsuche mit O(log(n))
Bäume Arten (7)
- Out-Tree - pfeile root ->
- In-Tree - pfeile -> root
- Binär-Baum - häufigsten
- AVL-Baum
- B-Baum
- B*-Baum
- Binominal-Baum
Bäume Elemente (4)
- Wurzel (Root)
- Knoten (Node)
- Blatt (Leafe)
- Kanten (Edge)
Eigenschaften (7) + (3) - Baumstatus
- Ordnung - max childs
- Grad - Anzahl childs - Knoten
- Pfad - weg von Knoten -> Wurzel
- Tiefe - Anzahl Knoten auf Pfad von Knoten (Wurzel = 1)
- Niveau - Ebene
- Höhe - Höhe des Baumes - Tiefe des weit entferntesten Knoten
- Gewicht - Anzahl Knoten
- ausgefüllt - alle inneren Knoten maximum an Kindern
- voll / ausgeglichen - alle niveaus voll ausser das letzte linksbündig
- vollständig / komplett - voller / symetrischer Baum
Traversieren eines Binären Baumes - Arten(3)
Preorder - Haupreihenfolge
Postorder - Nebenreihenfolge
Inorder - Symetrische Reihenfolge
Operationen auf Binärem-Suchbaum? (5)
- Suchen
- Einfügen
- Entfernen
- Balancieren
- Traversieren
Binärere baum was beachten beim entfernen? (3)
- Blatt - just do it
- Knoten mit einem Blatt : Blatt -> Knoten
- Knoten mit zwei Blätter: Knoten mit weitesten linkes Blatt des rechten Teilbaumes austauschen (nächst grösserer Wert)
Hastable Konflikt - Kollision?
Speichergrösse zu Kollisions verminderung -> Konflikt
#Load-Faktor : Wie viel grösser ist die Datenstruktur als ihre Werte.
Equals Tipps (5)
- Final / Finalisieren
- Unit-Testen / gut testen
- Gleichheit nur auf Schlüsselwerte vergleichen
- @Override - compiler hilft wenn fehlgetibt und co
- Equals by Objektreferenzen weiter delegieren
Immutable Objects - Eigenschaften und pros
Eigenschaften:
- Keine Methoden die Daten mutieren
- final / keine spezialisierung der Klasse zulässig
- Attribute werden privat & final (nur beim erzeugen setzten)
- Exklusiver Zugriff
- nur getter
- keine mutierbaren referenzen ausserhalb
+ Thread safe ohne synchronisation
+ beliebig verteilbar - unproblematisch beim verwenden von Collections oder Datensharing
+ gut als Attributtypen bei komplexen strukturen
Einfach -> alles was man kann -> final
wenn get Funktion -> nur immutable Objekt oder eine kopie der referenz / instance
Thirdparty - libraries (3)
- Eclipse-Collections (kompakt & assagestarke API - wenig Speicher versprechen)
- HPPC (Grosse Set an elemtartypen
- google-guava (umfangreich)
sollte man 3rd-Party libraries verwenden?
Eher nicht: da
- abhängig
- zuerst Java-lib ansehen
- 3rd party-lib ausgiebig testen und vorteil aufzeigen
- wirklich nur bei special cases
