Informatik Fachbegriffe: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
Zeile 160: Zeile 160:
* 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=

Version vom 14. Januar 2024, 13:43 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.

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".
  • 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
Abgerufen von „https://sibiwiki.de/wiki/index.php?title=Informatik_Fachbegriffe&oldid=3641“