T&A AD Lernkarten
Lernkarten für AD
Lernkarten für AD
Kartei Details
| Zusammenfassung | Diese Lernkarten behandeln fortgeschrittene Themen der Informatik, insbesondere Datenstrukturen und Algorithmen. Sie decken grundlegende Konzepte wie Bäume, Listen, Arrays, und deren Operationen, sowie deren Eigenschaften und Komplexitäten ab. Auch Themen wie Rekursion, Big-O-Notationen und die Verwendung von Java-Implementierungen werden behandelt. Diese Lernkarten richten sich an Studierende der Informatik, die ihr Verständnis von Datenstrukturen und Algorithmen vertiefen möchten, um effizientere und korrektere Lösungen für komplexe Probleme zu entwickeln. |
|---|---|
| Karten | 26 |
| Lernende | 1 |
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 23.05.2017 / 23.06.2017 |
| Weblink |
https://card2brain.ch/cards/20170523_ta_ad_lernkarten
|
| Einbinden |
<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
