Informatik Fachbegriffe: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(23 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 4: Zeile 4:


''Kursiv sind "interne" Begriffe, die anschaulich sind, aber keine echten Fachbegriffe.''
''Kursiv sind "interne" Begriffe, die anschaulich sind, aber keine echten Fachbegriffe.''
=Operatoren=
Die Operatoren definieren, was genau man in einer Aufgabe zu machen hat. Anders als in Mathe sind die Operatoren weitestgehend "intuitiv" verständlich - mit Ausnahme des Operators "Analysieren" (siehe unten).
* '''Liste der Operatoren:'''<br/>analysieren, angeben, anwenden, begründen, beschreiben, bestimmen, beurteilen, darstellen, dokumentieren, entscheiden, entwerfen, entwickeln, erläutern, ermitteln, erweitern, implementieren, interpretieren, modellieren, modifizieren, Stellung nehmen, überführen, vergleichen, vervollständigen, zeigen
* '''Vollständige Liste der Operatoren mit Erläuterungen:'''<br/>[https://www.standardsicherung.schulministerium.nrw.de/cms/zentralabitur-wbk/faecher/getfile.php?file=2282 Operatoren Informatik-Abitur (Standardsicherung NRW)]
* '''Analysieren Sie ... '''.<br/>''Der Operator "Analysieren Sie..." heißt in Informatik nur so viel wie "Denken Sie nach über...". <br/>Das heißt: <font color='red'>Dazu muss man NICHTS aufschreiben!!</font><br/>Der Operator "Analysieren Sie..." steht immer zusammen mit einem anderen Operator - und für den muss man was tun.
=Algorithmen=
''Algorithmen entwickeln und implementieren'' kann in jedem Teilbereich vorkommen!
'''[[Algorithmus_entwickeln_und_implementieren|zum Nachlesen hier klicken]]'''
* Die Methode ... hat als Parameter ...
* Abbruchbedingung: Wenn ...., wird die Methode verlassen und ... zurückgegeben.
* eine Variable ... mit Startwert ... festlegen.
* ... mit einer Schleife ... durchlaufen.
* für jedes Element...
* wenn ... (sonst...)
* Die Variable ... erhöhen/verringern um ...
* Am Ende ... zurückgeben.
=Datenbanken=
=Datenbanken=
==Entity-Relationship-Modellierung==
==Entity-Relationship-Modellierung==
Zeile 17: Zeile 37:


==relationales Datenmodell==
==relationales Datenmodell==
'''[[Relationales Datenmodell|zum Nachlesen hier klicken]]'''
* Tabelle
* Tabelle
* Relationenschema (damit meint das Zentralabitur eine Tabelle)
* Relationenschema (damit meint das Zentralabitur eine Tabelle)
Zeile 26: Zeile 47:


==Normalisierung==
==Normalisierung==
'''[[Normalisierung|zum Nachlesen hier klicken]]'''
* atomar
* atomar
* nicht eindeutiger Primärschlüssel
* nicht eindeutiger Primärschlüssel
Zeile 37: Zeile 59:


==SQL==
==SQL==
'''[[SQL|zum Nachlesen hier klicken]]'''
* Kartesisches Produkt: "jede(r) mit jedem"
* Kartesisches Produkt: "jede(r) mit jedem"
* Abgleich zwischen Tabellen
* Abgleich zwischen Tabellen
Zeile 49: Zeile 72:


==mit Java auf Datenbanken zugreifen==
==mit Java auf Datenbanken zugreifen==
'''[[Java-SQL|zum Nachlesen hier klicken]]'''
* DatabaseConnector
* DatabaseConnector
* Query (=Abfrage)
* Query (=Abfrage)
Zeile 58: Zeile 82:


=Objektorientierte Modellierung und Programmierung=
=Objektorientierte Modellierung und Programmierung=
'''zum Nachlesen:'''
* [[Klassen-_und_Implementationsdiagramm|Klassen- und Implementationsdiagramm]]
* [[Klasse|Klasse]]
* [[Vererbung|Vererbung]]
* [[Polymorphie|Polymorphie]]
* [[Abstrakte Klasse|Abstrakte Klasse]]
* [[Interface|Interface]]
* [[Java_Basis-Sprachelemente|Java Basis Sprachelemente]], u.a. Bedingung, Schleife etc.
* [[Array|Arrays]]


* erbt von (bzw. "ist ein")
'''Fachbegriffe:'''
* Super-Klasse
* [[Vererbung|Vererbung]]
* Sub-Klasse
** erbt von  
* Polymorphie
** ist ein (gleichbedeutend mit "erbt von"!)
** Super-Klasse
** Sub-Klasse
* [[Polymorphie|Polymorphie]]
** polymorphe Methode
** polymorphe Methode
* [[Abstrakte Klasse|Abstrakte Klasse]] (=Klasse mit mind. einer abstrakten Methode)
* abstrakte Methode
* abstrakte Methode
* abstrakte Klasse (=Klasse mit mind. einer abstrakten Methode)
* [[Interface|Interface]]
* [[Implementationsdiagramm|Klassen- und Implementationsdiagramm]]
* hat-Beziehung
* hat-Beziehung
* Assoziation (=kennt-Beziehung)
* Assoziation (=kennt-Beziehung)
* Multiplizität
* Multiplizität
* Attribut
* [[Klasse|Klasse]]
* lokale Variable
** Objekt (Von einer Klasse kann man mehrere Objekte erzeugen.)
* Methode
** Attribut
* Parameter
*** public / private
* Rückgabetyp
** Konstruktor
* public / private
* [[Java_Basis-Sprachelemente#Methoden|Methode]]
* Konstruktor
** Parameter
* Klasse
** lokale Variable
* Schnittstelle (interface, vgl. ComparableContent)
** Rückgabetyp
* Objekt
** public / private
* ContentType
* ContentType (z.B. für Listen kann man den ContentType angeben.)
* [[Interface|Schnittstelle (interface, vgl. ComparableContent)]]
* [[Struktogramm]]
* [[Struktogramm]]
* Anweisung
* Anweisung
* Methodenaufruf
* Methodenaufruf
* Bedingung
* [[Java_Basis-Sprachelemente#Verzweigungen_(if-else)|Bedingung]]
* Schleife
* [[Java_Basis-Sprachelemente#Schleifen_(while,_for,_do-while)|Schleife]]
** Zählschleife (for)
** Zählschleife (for)
** bedingte Schleife (while)
** bedingte Schleife (while)
** mit Schleife ein Array durchlaufen: <code>for(int i=0; i<array.length; i++)</code>
** mit Schleife ein Array durchlaufen: <code>for(int i=0; i<array.length; i++)</code>
* [[Array|Arrays]]
** Index
** Wert
** [[Array#Zweidimensionale_Arrays|zweidimensionales Array]], z.B.: <code> private int[][] einmalEinsTabelle;</code>


=Java-Programmierung mit linearen Datenstrukturen=
=Java-Programmierung mit linearen Datenstrukturen=
* Schlange (vorne - hinten): <code>Queue</code>
'''zum Nachlesen:'''
* Stapel (oben): <code>Stack</code>
* [[Queue#Verwendung_von_Queues|Verwendung von Queues]]
* Liste: <code>List</code>  
* [[Stack#Verwendung_von_Stacks|Verwendung von Stacks]]
* [[List#Standardvorgehen_im_Umgang_mit_Listen|List: Standardvorgehen]]
* [[Array#Ein_Array_mit_einer_for-Schleife_durchlaufen|Array: durchlaufen]]
 
'''Fachbegriffe:'''
* [[Laufzeit_von_Algorithmen|Laufzeit]]
** O(log(n)): Suchen in einem [[Binärer Suchbaum|Binären Suchbaum]]
** O(n): Suchen in einer unsortierten Liste
** O(n*log(n)): Sortieren mit [[Quicksort|Quicksort]]
** O(n<sup>2</sup>): Sortieren mit [[Bubblesort]], [[Insertionsort]], [[Selectionsort|Selectionsort]]
* <u>statische</u> Datenstruktur (Array): <br/>''Man muss vorher angeben, wie viele Einträge das Array hat.''
* <u>dynamische</u> Datenstrukturen: Stack, List, Queue (und auch BinaryTree, BinarySearchTree, Graph)<br/>''Dynamische Datenstrukturen können während der Laufzeit "wachsen" und "schrumpfen".''
* [[Java_Basis-Sprachelemente#NullPointerException|NullPointerException]]
* [[Queue|Queue]]: Schlange (vorne - hinten)
** vorderstes Element: <code>pQueue.front()</code>
** anhängen: <code>pQueue.enqueue(...)</code>
** vorderstes Element entfernen: <code>pQueue.dequeue()</code>
** ist leer: <code>pQueue.isEmpty()</code>
** Hilfs-Queue: z.B. um einen Queue zu durchlaufen, ohne ihn zu zustören
* [[Stack|Stack]]: Stapel (oben)
** oberstes Element: <code>pStack.top()</code>
** oben drauflegen: <code>pStack.push(...)</code>
** oberstes Element entfernen: <code>pStack.pop()</code>
** ist leer: <code>pStack.isEmpty()</code>
** Hilfs-Stack: z.B. um einen Stack zu durchlaufen, ohne ihn zu zustören
* [[List|List]]: Liste.<br/>''Listen kann man einfach durchlaufen und irgendwo einfügen.''
** anhängen: <code>pList.append(...)</code>
** anhängen: <code>pList.append(...)</code>
** einfügen vor dem aktuellen Element: <code>pList.insert(...);</code>
** einfügen vor dem aktuellen Element: <code>pList.insert(...);</code>
* [[Array|Array]]: <br/>''statische Datenstruktur - man muss die Anzahl der Elemente vorher festlegen.''
* durchlaufen (Liste, Array)
* durchlaufen (Liste, Array)
** ein Array durchlaufen: <code>for(int i=0; i<array.length; i++)</code>
** ein Array durchlaufen: <code>for(int i=0; i<array.length; i++)</code>
Zeile 101: Zeile 170:
** Array: <code>array[i];</code>
** Array: <code>array[i];</code>
** Liste: <code>pList.getContent();</code>
** Liste: <code>pList.getContent();</code>
* Hilfs-Stack
* erzeugen
* Hilfs-Queue
** erzeugen eines Objektes: <code>Person p = '''new''' Person("Mustermann", "Max");</code>
* erzeugen eines Objektes: <code>Person p = new Person("Mustermann", "Max");</code>
** erzeugen einer Liste: <code>List<Person> ergebnisListe = '''new''' List<>();</code>
* erzeugen eines Arrays: <code>int[] zahlen = new int[1000];</code>
** erzeugen eines Arrays: <br/>z.B. <code>Person[] einwohner = '''new''' int[1000];</code><br/>''Vorsicht! In jedem der 1000 Werte steht <code>null</code>!''
** erzeugen eines zweidimensionalen Arrays: <code>int[][] einmalEinsTabelle = new int[10][10];</code>
* Schleife
* Schleife
** mit einer for-Schleife ein Array durchlaufen: <code>for(int i=0; i<array.length; i++)</code>
** Schleife verlassen: <code>break;</code>
* Schleife verlassen: <code>break;</code>
** Schleife beim nächsten Element fortsetzen: <code>continue;</code>
* Schleife beim nächsten Element fortsetzen: <code>continue;</code>
* lokale Variable
* Attribut
* Methode verlassen <code>return;</code>
* Methode verlassen <code>return;</code>
* zurückgeben: <code>return ergebnis;</code>
* zurückgeben: <code>return ergebnis;</code>
* ausgeben: <code>System.out.println("Hallo");</code>
* ausgeben: <code>System.out.println("Hallo");</code>
=Sortierverfahren=
* [[Bubblesort]] <u>nur für Arrays!</u>, Laufzeit O(n<sup>2</sup>)
* [[Insertionsort]] für Listen, Laufzeit O(n<sup>2</sup>)
* [[Selectionsort]] für Listen, Laufzeit O(n<sup>2</sup>)
* nur LK: [[Quicksort]] für Listen, Laufzeit O(n*log(n)) im Average Case
* Sortieren mit einem [[Binärer Suchbaum|Binären Suchbaum ]]<br/>- Der Reihe nach in den Binären Suchbaum einfügen<br/>- Inorder-Traversierung<br/>Laufzeit O(n*log(n)) im Average Case


=Binärbäume und binäre Suchbäume=
=Binärbäume und binäre Suchbäume=
Zeile 132: Zeile 206:


=Automaten und Grammatiken=
=Automaten und Grammatiken=
 
'''zum Nachlesen:'''<br/>
[https://sibiwiki.de/wiki/index.php?title=Kategorie:Endliche_Automaten Kategorie endliche Automaten]
<br/>''Da gibt es Links zu allen Unterüberschriften.''
==endliche Automaten==
==endliche Automaten==
* Deterministischer endlicher Automat (DEA)
* [[Deterministischer Endlicher Automat|Deterministischer endlicher Automat (DEA)]]
** A, Z, d, Q<sub>0</sub>, E: ''allen Zuhörern doofen Quatsch erzählen''
** A, Z, d, Q<sub>0</sub>, E: ''allen Zuhörern doofen Quatsch erzählen''
* Der DEA '''erkennt''' eine reguläre Sprache
* Der DEA '''erkennt''' eine reguläre Sprache
* Der DEA '''überprüft''' ein Wort, ob es zur Sprache gehört.
* Der DEA '''überprüft''' ein Wort, ob es zur Sprache gehört.
* Nicht-deterministischer endlicher Automat (NEA)
* [[Nicht-deterministischer endlicher Automaten|Nicht-deterministischer endlicher Automat (NEA)]]
** ''"es gibt einen Weg"''
** ''"es gibt einen Weg"''
* Zustand
* Zustand
Zeile 144: Zeile 220:
**Endzustände
**Endzustände
* Übergang
* Übergang
* Epsilon (ε): <br>damit kann man den Endzustand erreichen. (Nur bei Keller-Automaten im LK.)
* Alphabet
* Alphabet
* Zustands-Übergangs-Graph
* Zustands-Übergangs-Graph
Zeile 151: Zeile 226:
** für einen NEA ggf. mit geschweifter Klammer mehrere Zustände zusammenfassen.
** für einen NEA ggf. mit geschweifter Klammer mehrere Zustände zusammenfassen.
* Senke (=ein Zustand, aus dem es keinen Ausweg mehr gibt)
* Senke (=ein Zustand, aus dem es keinen Ausweg mehr gibt)
* Potenzmengenkonstruktion
* [[Potenzmengenkonstruktion|Potenzmengenkonstruktion]]
* Potenzmenge (=eine Menge von Zuständen)
** Potenzmenge (=eine Menge von Zuständen)


==reguläre Grammatik==
==[[Reguläre Grammatik|reguläre Grammatik]]==
* G = {N, T, S, P} ''Nerds testen Sonys Playstation''
* G = {N, T, S, P} ''Nerds testen Sonys Playstation''
* linkslineare Grammatik: Nicht-Terminal links
* linkslineare Grammatik: Nicht-Terminal links
Zeile 166: Zeile 241:
* die RG erzeugt eine (reguläre) Sprache
* die RG erzeugt eine (reguläre) Sprache


==Kellerautomaten (nur LK)==
==[[Kellerautomat|Kellerautomaten (nur LK)]]==
* Keller-Alphabet
* Keller-Alphabet
* Keller-Zeichen
* Keller-Zeichen
* Epsilon (ε): Um den Endzustand zu erreichen, darf man das Zeichen ε (="nichts") schreiben.


==kontextfreie Grammatik (nur LK)==
==[[Kontextfreie_Grammatik|kontextfreie Grammatik (nur LK)]]==
* lässt sich durch Kellerautomaten prüfen
* lässt sich durch Kellerautomaten prüfen


==Parser==
==Parser==
* für DEA
* [[Parser|Parser für DEA]]
** mit switch-case:<br/><code>switch(zustand){<br/>&nbsp;&nbsp;&nbsp;case 1: ...</code>
* [[Kellerautomat#Parser_für_einen_Kellerautomaten|Parser für Kellerautomaten (nur LK)]]
** mit if-else if: <br/><code>if(zustand == 1){<br/>&nbsp;&nbsp;&nbsp;...<br/>}<br/>else if(zustand == 2){<br/>&nbsp;&nbsp;&nbsp;...<br/>}<br/>else{<br/>&nbsp;&nbsp;&nbsp;...<br/>}</code> 
* für Kellerautomaten (nur LK)
** Keller (=<code>Stack</code>)
** Keller (=<code>Stack</code>)


=Graph (nur LK!)=
=[[Graph|Graph (nur LK!)]]=
* Knoten
* Knoten
* Kante
* Kante
Zeile 186: Zeile 260:
* Markierung aufheben
* Markierung aufheben
* Gewicht
* Gewicht
* Traversierung
* Traversierung (d.h. Breitendurchlauf oder Tiefendurchlauf)
* Breitendurchlauf
* [[Graph#Tiefendurchlauf|Tiefendurchlauf]]
* Tiefendurchlauf
** rekursiv
* rekursiv (für Tiefendurchlauf)
* [[Graph#Breitendurchlauf|Breitendurchlauf]]
* Knotenliste (für Breitendurchlauf)
** Knotenliste
* [[Dijkstra-Algorithmus|Dijkstra-Algorithmus]]
* rote Liste (für Dijkstra-Algo)
* rote Liste (für Dijkstra-Algo)
* gelbe Liste (für Dijkstra-Algo)
* gelbe Liste (für Dijkstra-Algo)


=Datenschutz=
=[[Datenschutz|Datenschutz]]=
Schutz von Angaben, aus denen man einen bestimmten Menschen erkennen kann oder die einem bestimmten Menschen zugeordnet werden können.
 
'''Prinzipien des Datenschutzes:'''
* <u>Verbot mit Erlaubnisvorbehalt</u>
* Datenminimierung
* Zweckbindung
* Transparenz
* <u>Erforderlichkeit</u>


* Erlaubnisvorbehalt
=[[Backtracking|Backtracking (nur LK!)]]=
* Erforderlichkeit
=Backtracking (nur LK!)=
* Stufe
* Stufe
* Teillösungsschritt
* Teillösungsschritt

Aktuelle Version vom 10. März 2024, 12:56 Uhr


Hier werden die wesentlichen Fachbegriffe zusammengestellt, die für das Informatik-Abitur relevant sind.

Kursiv sind "interne" Begriffe, die anschaulich sind, aber keine echten Fachbegriffe.

Operatoren

Die Operatoren definieren, was genau man in einer Aufgabe zu machen hat. Anders als in Mathe sind die Operatoren weitestgehend "intuitiv" verständlich - mit Ausnahme des Operators "Analysieren" (siehe unten).

  • Liste der Operatoren:
    analysieren, angeben, anwenden, begründen, beschreiben, bestimmen, beurteilen, darstellen, dokumentieren, entscheiden, entwerfen, entwickeln, erläutern, ermitteln, erweitern, implementieren, interpretieren, modellieren, modifizieren, Stellung nehmen, überführen, vergleichen, vervollständigen, zeigen
  • Vollständige Liste der Operatoren mit Erläuterungen:
    Operatoren Informatik-Abitur (Standardsicherung NRW)
  • Analysieren Sie ... .
    Der Operator "Analysieren Sie..." heißt in Informatik nur so viel wie "Denken Sie nach über...".
    Das heißt: Dazu muss man NICHTS aufschreiben!!
    Der Operator "Analysieren Sie..." steht immer zusammen mit einem anderen Operator - und für den muss man was tun.

Algorithmen

Algorithmen entwickeln und implementieren kann in jedem Teilbereich vorkommen!

zum Nachlesen hier klicken

  • Die Methode ... hat als Parameter ...
  • Abbruchbedingung: Wenn ...., wird die Methode verlassen und ... zurückgegeben.
  • eine Variable ... mit Startwert ... festlegen.
  • ... mit einer Schleife ... durchlaufen.
  • für jedes Element...
  • wenn ... (sonst...)
  • Die Variable ... erhöhen/verringern um ...
  • Am Ende ... zurückgeben.

Datenbanken

Entity-Relationship-Modellierung

zum Nachlesen hier klicken

  • Kardinalität
  • 1:n
  • n:m
  • Primärschlüssel
  • Attribut
  • Entitätsmenge
  • Entität (=ein Objekt einer Entitätsmenge)
  • Relation (=Beziehung)

relationales Datenmodell

zum Nachlesen hier klicken

  • Tabelle
  • Relationenschema (damit meint das Zentralabitur eine Tabelle)
  • Datenbankschema (damit meint das Zentralabitur das ganze relationale Datenmodell)
  • Attribut
  • Primärschlüssel: unterstrichen
  • Fremdschlüssel: ↑
    ...bezieht sich auf den Primärschlüssel der Tabelle ...
  • kombinierter Primärschlüssel

Normalisierung

zum Nachlesen hier klicken

  • atomar
  • nicht eindeutiger Primärschlüssel
  • funktional abhängig von einem Teil des Primärschlüssel (Verstoß gegen 2. NF)
  • funktional abhängig von einem Nicht-Schlüssel-Attribut (Verstoß gegen 3. NF)
  • Anomalien
    • Einfüge-Anomalie
    • Änderungs-Anomalie
    • Lösch-Anomalie
    • die können nach Normalisierung nicht mehr auftreten!

SQL

zum Nachlesen hier klicken

  • Kartesisches Produkt: "jede(r) mit jedem"
  • Abgleich zwischen Tabellen
  • Verknüpfen (Join) von zwei Tabellen, wobei ... mit ... abgeglichen wird.
  • "Drückeberger": ... LEFT JOIN ... WHERE ... IS NULL
  • Differenz: NOT IN
  • Vereinigung: UNION
  • selbstdefinierte Tabelle
  • Alias: AS
  • zusammenfassen von Zeilen: GROUP BY
  • sortieren nach: ORDER BY

mit Java auf Datenbanken zugreifen

zum Nachlesen hier klicken

  • DatabaseConnector
  • Query (=Abfrage)
  • Variablen (z.B. Parameter) im SQL-Statement
  • Zeilenzahl: int zeilenZahl = queryResult.getRowCount();
  • Array (2-dim): String[][] data = queryResult.getData();
    • durchlaufen:
      for(int i=0; i<data.length; i++){
         String name = data[i][0];
         String vorname = data[i][1];
  • In Zahl konvertieren: int zahl = Integer.parseInt(data[i][0]);

Objektorientierte Modellierung und Programmierung

zum Nachlesen:

Fachbegriffe:

Java-Programmierung mit linearen Datenstrukturen

zum Nachlesen:

Fachbegriffe:

  • Laufzeit
  • statische Datenstruktur (Array):
    Man muss vorher angeben, wie viele Einträge das Array hat.
  • dynamische Datenstrukturen: Stack, List, Queue (und auch BinaryTree, BinarySearchTree, Graph)
    Dynamische Datenstrukturen können während der Laufzeit "wachsen" und "schrumpfen".
  • NullPointerException
  • Queue: Schlange (vorne - hinten)
    • vorderstes Element: pQueue.front()
    • anhängen: pQueue.enqueue(...)
    • vorderstes Element entfernen: pQueue.dequeue()
    • ist leer: pQueue.isEmpty()
    • Hilfs-Queue: z.B. um einen Queue zu durchlaufen, ohne ihn zu zustören
  • Stack: Stapel (oben)
    • oberstes Element: pStack.top()
    • oben drauflegen: pStack.push(...)
    • oberstes Element entfernen: pStack.pop()
    • ist leer: pStack.isEmpty()
    • Hilfs-Stack: z.B. um einen Stack zu durchlaufen, ohne ihn zu zustören
  • List: Liste.
    Listen kann man einfach durchlaufen und irgendwo einfügen.
    • anhängen: pList.append(...)
    • einfügen vor dem aktuellen Element: pList.insert(...);
  • Array:
    statische Datenstruktur - man muss die Anzahl der Elemente vorher festlegen.
  • durchlaufen (Liste, Array)
    • ein Array durchlaufen: for(int i=0; i<array.length; i++)
    • eine Liste durchlaufen: for(pList.toFirst(); pList.hasAccess(); pList.next())
  • aktuelles Element:
    • Array: array[i];
    • Liste: pList.getContent();
  • erzeugen
    • erzeugen eines Objektes: Person p = new Person("Mustermann", "Max");
    • erzeugen einer Liste: List<Person> ergebnisListe = new List<>();
    • erzeugen eines Arrays:
      z.B. Person[] einwohner = new int[1000];
      Vorsicht! In jedem der 1000 Werte steht null!
    • erzeugen eines zweidimensionalen Arrays: int[][] einmalEinsTabelle = new int[10][10];
  • Schleife
    • Schleife verlassen: break;
    • Schleife beim nächsten Element fortsetzen: continue;
  • Methode verlassen return;
  • zurückgeben: return ergebnis;
  • ausgeben: System.out.println("Hallo");

Sortierverfahren

  • Bubblesort nur für Arrays!, Laufzeit O(n2)
  • Insertionsort für Listen, Laufzeit O(n2)
  • Selectionsort für Listen, Laufzeit O(n2)
  • nur LK: Quicksort für Listen, Laufzeit O(n*log(n)) im Average Case
  • Sortieren mit einem Binären Suchbaum
    - Der Reihe nach in den Binären Suchbaum einfügen
    - Inorder-Traversierung
    Laufzeit O(n*log(n)) im Average Case

Binärbäume und binäre Suchbäume

  • Rahmenmethode
  • rekursive Methode
  • Abbruchbedingung
  • Wurzelbehandlung
  • Sachlogik
  • rekursive Aufrufe
  • Traversierung
  • Preorder
  • Inorder (=im Suchbaum: Sortierte Ausgabe!)
  • Levelorder (nur LK)
  • Baumliste für Levelorder (nur LK)
  • ComparableContent
  • implementiert die Schnittstelle (ComparableContent)
  • Dummy: zum Suchen in Suchbäumen.

Automaten und Grammatiken

zum Nachlesen:
Kategorie endliche Automaten
Da gibt es Links zu allen Unterüberschriften.

endliche Automaten

  • Deterministischer endlicher Automat (DEA)
    • A, Z, d, Q0, E: allen Zuhörern doofen Quatsch erzählen
  • Der DEA erkennt eine reguläre Sprache
  • Der DEA überprüft ein Wort, ob es zur Sprache gehört.
  • Nicht-deterministischer endlicher Automat (NEA)
    • "es gibt einen Weg"
  • Zustand
    • Anfangszustand
    • Endzustände
  • Übergang
  • Alphabet
  • Zustands-Übergangs-Graph
  • Zustands-Übergangs-Tabelle
  • Zustandsfolge
    • für einen NEA ggf. mit geschweifter Klammer mehrere Zustände zusammenfassen.
  • Senke (=ein Zustand, aus dem es keinen Ausweg mehr gibt)
  • Potenzmengenkonstruktion
    • Potenzmenge (=eine Menge von Zuständen)

reguläre Grammatik

  • G = {N, T, S, P} Nerds testen Sonys Playstation
  • linkslineare Grammatik: Nicht-Terminal links
  • rechtslineare Grammatik: Nicht-Terminal rechts
    • linkslineare und rechtslineare Regeln nicht mischen!!!
      z.B.: S → aS | Sb
      ist nicht regulär!!!
  • Terminal-Symbol
  • Nicht-Terminal-Symbol
    • Startsymbol
  • Produktionsregeln
  • Produktion eines Wortes
  • die RG erzeugt eine (reguläre) Sprache

Kellerautomaten (nur LK)

  • Keller-Alphabet
  • Keller-Zeichen
  • Epsilon (ε): Um den Endzustand zu erreichen, darf man das Zeichen ε (="nichts") schreiben.

kontextfreie Grammatik (nur LK)

  • lässt sich durch Kellerautomaten prüfen

Parser

Graph (nur LK!)

  • Knoten
  • Kante
  • markieren (Knoten oder Kante)
  • Markierung aufheben
  • Gewicht
  • Traversierung (d.h. Breitendurchlauf oder Tiefendurchlauf)
  • Tiefendurchlauf
    • rekursiv
  • Breitendurchlauf
    • Knotenliste
  • Dijkstra-Algorithmus
  • rote Liste (für Dijkstra-Algo)
  • gelbe Liste (für Dijkstra-Algo)

Datenschutz

Schutz von Angaben, aus denen man einen bestimmten Menschen erkennen kann oder die einem bestimmten Menschen zugeordnet werden können.

Prinzipien des Datenschutzes:

  • Verbot mit Erlaubnisvorbehalt
  • Datenminimierung
  • Zweckbindung
  • Transparenz
  • Erforderlichkeit

Backtracking (nur LK!)

  • Stufe
  • Teillösungsschritt
  • Abbruchbedingung
    • Lösung erreicht
    • Lösung nicht mehr erreichbar
    • maximale Stufenzahl überschritten
  • rückgängig machen