Definition G = ( V, E ) → gerichteter Graph (Digraph) ↔ V ≠ Ø – Knotenmenge v ∈ V – Knoten / Vertex E ⊆ V² – Kantenmenge e = { u, v } ∈ E – Kante u – Quelle, v – Ziel der Kante e = ( u, v ) ∈ E mit […]
IT
IT – Bäume
Allgemeines Kante, die von Knoten A nach Knoten B geht A – Vater ( Vorgänger, parent ) B – Sohn ( Kind, child ) Zwei Knoten vom selben Vater – Brüder ( siblings, Geschwister ) Grad eines Knotens – Anzahl direkter Nachfolger Grad eines Baumes – max. Knotengrad aller Knoten Blätter – Knoten vom Grad […]
IT – Suchverfahren
Suche in ungeordneten linearen Listen Sequentielle Suche durchlaufe Liste sequentiell bis Schlüssel gefunden oder Listenende erreicht ist linearer Suchaufwand: O(n) Suche in geordneten linearen Listen Sequentielle Suche durchlaufe Liste (aufsteigend) solange Suchschlüssel größer aktueller Schlüssel und Listenende nicht erreicht linearer Suchaufwand: O(n) Binäre Suche V1 Intervallunterteilung bis Intervallgröße = 1 Aufwand: O(log²n) kein Abbruch, selbst […]
IT – Stack / Queue
Stack Kellerspeicher, Stapel, LIFO (Last In First Out) Liste, bei der alle Änderungen (Einfügen, Löschen) nur am Ende Top vorgenommen werden Funktionen: Create – erzeugt leeren Stack Init – initialisiert Stack als leeren Stack Push – fügt neues Element hinzu Pop – entfent aktuelles Element Top – zeigt aktuelles Element an Empty – fragt ab, […]
IT – Vererbung / Polymorphismus
Spezialisierung allgemeinere Klasse wird verfeinert ist-ein(e) – Beziehung Bsp. Student ist eine Person (Spezialisierung) kann zu einer Oberklasse mehrere Unterklassen liefern (disjunkt oder überlappend) Generalisierung spezielle Klasse wird verallgemeinert invers ist-ein(e)-Beziehung Bsp. Kugel, Würfel sind geometrische Körper (Generalisierung) Vererbung gemeinsame Eigenschaften (Attribute) und Methoden werden von der Oberklasse an Unterklasse weitergegeben –> vererbt transitiv –> […]
IT – Objekte und Klassen
Objekte jedes Objekt hat Zustand, Verhalten, Identität viele Objekte gleicher Art möglich daher Gruppierung in Klassen bei gleicher Datenstrutktur und gleichem Verhalten Instanz einer Klasse Kapselung von Zustand und Verhalten (Geheimhaltungsprinzip) Zugriff auf Attritbute ausschließlich über Methoden (s.o.) Relationen Assoziationen strukturelle Beziehungen zwischen den Objekten spez. Aggregation besteht-aus/ist-Teil-von-Relation Bsp. Auto hat Reifen, Türen, Motor, etc. […]
IT – Komplexitäten
Eigenschaften eines Programms Effizienz Korrektheit Zuverlässigkeit Robustheit Zeitkomplexität: Aufwand an Rechenzeit (in Schritten gemessen) Unterscheidung: worst-case best-case average-case Beschreibung: exakt: Zählfunktion T: N -> N; n ∈ N asymptotisch: Angabe einer Vgl.größe (Komplexitätsklasse) Speicherplatzkomplexität: Umfang des zu reservierenden Speicherplatzes Komplexitätsklassen obere Schranke O(f(n)) := { g: N -> N | ∃c ∈ R, c >0: […]
IT – Java
Datentypen (Elementare D., ADT, oder Referenztyp) Literale Variablen verschiedener Referenzstufen Ausdrücke & Operatoren Typkonversion (implizit, explizit (cast)) Anweisungen (Ausdruck, Deklaration, Kontrollfluss) Höhere Datentypen (Felder, Arrays) Unterprogramme Parameterübergabe (call by value, call by reference) Related Images:
IT – Algorithmen
Def. genaue, endl. Beschreibung eines allgemeinen Verfahrens, nutzt elementare, ausführbare Schritte statt 3 + 4 –> a + b Effektivität jeder einzelne Schritt ausführbar Effizienz Leistungsfähigkeit, geringer Aufwand Korrektheit partiell: jedes Ergebnis entspricht der Ausgabespezifikation sofern die Eingaben der Eingabespez. entsprechen, nicht zwingend anhaltend total: partiell korrekt, terminiert nach endl. vielen Schritten, nach jeder Eingabe, […]
IT – Grammatiken & Notationen
Chomsky-Grammatik 4-Tupel G = ( N , T , P , S ) N – endliche Menge Zeichen, Nichtterminalsymbole T – endliche Menge Zeichen, disjunkt N, Terminalsymbole S ∈ N – Startsymbol P – endliche Menge Regeln der Form (p, q) ∈ ( N ∪ T ) * Syntaxdiagramme N Rechteck T langrunder Kreis gerichtete […]