Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ----------------------------------------------------------------------[ Meta ]--
- name informatik/q1bis4
- section 35
- description Informatik Zusammenfassung von Q1 bis Q4 (vor dem Abitur)
- tags informatik q1 q2 q3 q4 school abi2014
- encoding utf8
- compliance informal
- lang de
- creation 02/2014
- version 1.0.0.0
- copyright Copyright (c) 2014 Ma_Sys.ma.
- For further info send an e-mail to Ma_Sys.ma@web.de.
- --------------------------------------------------------------------[ Lizenz ]--
- Diese Datei steht unter GPL 3.
- This program is free software: you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation, either version 3 of the License, or
- (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program. If not, see <http://www.gnu.org/licenses/>.
- --------------------------------------------------------------------[ Delphi ]--
- Grundlegendes
- if BEDINGUNG then begin if(BEDINGUNG) {
- ANWEISUNGEN; ANWEISUNGEN;
- end else if BEDINGUNG then begin } else if(BEDINGUNG) {
- ANWEISUNGEN; ANWEISUNGEN;
- end else begin } else {
- ANWEISUNGEN; ANWEISUNGEN;
- end; (* kein fi *) }
- while BEDINGUNG do begin while(BEDINGUNG) {
- ANWEISUNGEN; ANWEISUNGEN;
- (* break bricht ab *) }
- end; (* kein done *)
- for i := START to END do begin for(int i = 0; i <= END; i++) {
- ANWEISUNGEN; (* END incl.*) ANWEISUNGEN;
- end; (* kein done *) }
- case VARIABLE of switch(VARIABLE) {
- CONST: begin case CONST:
- ANWEISUNGEN; ANWEISUNGEN;
- end; break;
- CONST: begin case CONST:
- ANWEISUNGEN; ANWEISUNGEN;
- end; break;
- else begin default:
- ANWEISUNGEN; ANWEISUNGEN;
- end; (* kein esac *) }
- Funktionen
- procedure name(paramName: paramType; paramName: paramType);
- var
- variable: Typ;
- begin
- ANWEISUNGEN; (* exit; <=> return; *)
- end;
- function name(PARAMETER): returnType;
- var
- Variablendeklarationen
- begin
- name := wert; (* ~ return wert, aber kein Abbruch *)
- (* alt: *)
- result := wert;
- end;
- Typdeklarationen
- type
- et2a: Array[0..20] of Integer;
- name: equivalenztyp;
- Funktionsbibliothek
- intToStr(param: Integer): String;
- strToInt(param: String): Integer;
- randomize;
- randint(MAX): Integer; (* [0;MAX[ *)
- edit.text := strVal;
- writeLn(out);
- readLn(into);
- write(out);
- 2D Array
- test: Array[0..9,0..9] of Integer; (* <=> int[10][10] *)
- Hello World
- program Hello;
- (* Procedure, var, const, function, etc... hier *)
- begin
- writeLn('Hello world.');
- end;
- ----------------------------------------------------------[ Sortierverfahren ]--
- Sortieren durch Auswahl
- -----------------------
- Gehe Array durch und bestimme kleinsten Wert. Speichere ihn an die momentan zu
- bearbeitende Stelle und verschiebe den alten Wert an die vorherige Stelle des
- kleinsten Wertes.
- procedure sort;
- var
- i, j, k, min: Integer;
- begin
- for i := 0 to length(feld) - 2 do begin
- j := i;
- min := feld[i];
- for k := i + 1 to length(feld) - 1 do begin
- if feld[k] < min then begin
- j := k;
- min := feld[k];
- end;
- end;
- feld[j] := feld[i];
- feld[i] := min;
- end;
- end;
- Sortieren durch Austausch
- -------------------------
- Bubblesort. Wie Auswahl, nur jedesmal tauschen.
- Den ersten Eintrag mit allen größeren tauschen => erster Eintrag = kleinster;
- Quicksort
- ---------
- Bringe alle kleineren Einträge auf die linke und alle größeren auf die Rechte
- Seite und rufe das Verfahren auf die Teilgruppen auf. O(n log n).
- Wichtig auch
- Mitte ist nur ein ungefärer Ausdruck. Schwankt je nach Eingabedaten.
- procedure quicksort(var f: feld; start, ende: Integer); (* ende incl. *)
- var
- zl,zr,mitte,tmp: Integer;
- begin
- zl := start; (* Zeiger mit Auschnittsgrenzehn belegen, *)
- zr := end; (* normalerweise 0, length - 1 *)
- (* Wert des mittleren Eintrages *)
- mitte := f[(start + ende) div 2];
- repeat
- (* Stelle den linken Zeiger soweit nach vorne, dass der
- Wert auf den er zeigt > mitte ist. *)
- while f[zl] < mitte do begin
- zl := zl + 1;
- end;
- (* Stelle den rechten Zeiger solange zurück, bis er auf
- einen Wert < mitte zeigt. *)
- while f[zr] > mitte do begin
- zr := zr - 1;
- end;
- (* Situation: zl und zr zeigen auf Werte, die auf der *)
- (* jeweils falschen Seite sind, sofern zl > zr ist. *)
- (* Ansonsten ist alles auf der richtigen Seite *)
- if not zl > zr then begin
- tmp := f[zl];
- f[zl] := f[zr];
- f[zr] := tmp;
- end;
- until zl > zr;
- (* Sortiere [start;zr] falls der Bereich noch zu sortiren ist
- <=> falls es ihn noch gibt. *)
- if start < zr then begin
- quicksort(f, start, zr);
- end;
- (* Sortiere [zl;ende] falls der Bereich noch zu sortieren ist
- <=> falls es ihn noch gibt. *)
- if zl < ende then begin
- quicksort(f, zl, ende);
- end;
- end;
- -----------------------------------------------------------------[ Rekursion ]--
- * Immer weniger efektiv, als Iteration, wegen eventuell doppelten Aufrufen und
- Rücksprungaddressen
- * keine weiteren, wichtigen Erkenntnisse
- ---------------------------------------------------------[ Delphi Datentypen ]--
- oooooooooooooooooooooooooooooooooooooooooooooo
- Delphi C Min Max
- ++++++++++++++++++++++++++++++++++++++++++++++
- byte unsigned char 0 2^8 -1
- word (int12) 0 2^12 -1
- shortint char -2^7 2^7 -1
- smallint int16_t -2^15 2^15 -1
- integer int -2^31 2^31 -1
- longint long -2^31 2^31 -1
- cardinal unsigned long 0 2^32 -1
- longword unsigned long -2^63 2^63 -1
- int64 long long int -2^63 2^63 -1
- single float
- real float
- double double
- extended long double
- boolean bool true | false
- char char
- shortString char[255]
- string char* Max. 3 GiB
- oooooooooooooooooooooooooooooooooooooooooooooo
- -----------------------------------------------[ Zeiger und Listen in Delphi ]--
- ooooooooooooooooooooooooooooooooooooooooo
- Symbol Beschreibung C
- +++++++++++++++++++++++++++++++++++++++++
- `^Typ` Zeiger auf Typ `Typ*`
- `^var` Zeiger auf var `&var`
- `var^` Dereference var `var*`
- `nil` Nullpointer `NULL`
- `free(p)` Lösche Zeiger p `free(p)`
- `inc(i)` Inkrementiere i `i++`
- ooooooooooooooooooooooooooooooooooooooooo
- Bei Listen: {\language[Pascal]}
- type
- ListPointer = ^ListElement;
- ListElement = record
- cnt: Integer;
- next: ListPointer;
- end;
- procedure append(to: ListPointer; val: Integer);
- var
- current: ListPointer;
- begin
- current := to;
- while current^.next <> nil do begin
- current .= current^.next;
- end;
- new(current^.next);
- current^.next^.next := nil;
- current^.next^.next := val;
- end;
- ----------------------------------------------[ Objektorientierung in Delphi ]--
- Übersicht
- ---------
- Projekte
- ganze Programme
- Units
- Thematisch zusammenhängnder Code
- Typen
- eigene Datentypen
- Records
- Datensätze
- Umbenannte und Wertebereichsändernde Datentypen
- Klassen
- In Delphi sind Klassen Datentypen
- Eine Unit
- ---------
- Units ähneln Packages, sind aber nur eine Datei. In Delphi darf der Name einer
- Unit nicht der einer Klasse oder Variable sein. Leider unterscheidet Delphi
- nicht zwischen Groß- und Kleinschreibung => in Delphi verwenden Viele Präfixe.
- Alternativ kann man auch verallgemeinernde Namen verwenden, etwa
- oooooooooooooooooooooooooooooooooooooo
- Beispiel Beschreibung
- ++++++++++++++++++++++++++++++++++++++
- Fahrzeug.pas Name der Unit
- Auto Klassenname
- autoObj oder anAuto Instanz
- oooooooooooooooooooooooooooooooooooooo
- Aufbau
- unit Name;
- interface (* steht immer da *)
- uses ...; (* Import v Include, etc. *)
- const ...; (* Konstatnen *)
- type
- ... (* Klassendeklarationen etc. *)
- implementation
- (* Methodeninhalte. *)
- end. (* Hier und nur hier: '.' *)
- Hinter Funktionsnamen: `...; overload;` bei anderer Methode mit gleichem Namen.
- Objekten kann `nil` zugewiesen werden.
- ----------------------------------------------------------------[ Datentypen ]--
- Records
- type Status = record (* Delphi Programmierer *)
- combinations: Integer; (* verwenden gerne Prefixe: *)
- found: Integer; (* TStatus oder tStatus *)
- msg: String;
- end; (* Records werden nicht initialisiet. *)
- function createStatus: Status;
- var
- ret: Status;
- begin
- ret.combinations := 0;
- ret.found := 0;
- ret.msg := 'Not started.';
- result := ret;
- end;
- Klassen
- type Car = class (* alt: class(Transporter) *)
- public (* nichts. published; *)
- ... (* außerdem: protected *)
- private (* Variablen in der *)
- ... (* Deklaration wie in der *)
- end; (* Implementation *)
- Konstruktoren und Destruktoren
- constructor create; ... (* self <=> this *)
- constructor Car.create;
- begin
- ...
- end;
- destructor destroy; overrride; ...
- destructor Car.destroy;
- begin
- inherited destroy; (* super.destroy() *)
- end;
- ----------------------------------------[ Die UML: Unified Modeling Language ]--
- Grundsätzliches
- ............... - private
- . Klassenname . + public
- ............... ++ published
- . Felder . # protected
- ............... ! procedure
- . Methoden . constructor
- ............... destructor
- ? function
- .............................................
- . Tank .
- .............................................
- . - size: Integer; .
- . - round: Boolean; .
- . - cnt: String; .
- . - level: Integer; .
- .............................................
- . + ! create(size: Integer, round: Boolean) .
- . + ! add(liters: Integer) .
- . + ! remove(liters: Integer) .
- . + ? getSize(): Integer .
- . + ? isRound(): Boolean .
- . + ? getLevel(): Integer .
- . + ! setCnt(cnt: String) .
- . + ! destroy() .
- .............................................
- Beziehungen
- .......... kennt ...........
- . Buffer .------------->. Element .
- .......... ...........
- . (etc) . . (etc) .
- .......... ...........
- . (etc) . . (etc) .
- .......... ...........
- ^ |
- | ist (erbt von) |
- ............... |
- . List Buffer . |
- ...............<>-----------+ hat (e.g. Feld tes Types etc.)
- . (etc) .
- ...............
- . (etc) .
- ...............
- Kennt braucht man fast nie; meistens hat man "`hat"' oder "`ist"'.
- --------------------------------------------------------------[ Binäre Bäume ]--
- Elemente werden so angehängt, dass auf der linken Seite eines Kontens nur
- kleinere Element und rechts nur größere Elemente vorkommen.
- Niveau 0 10
- / \
- Niveau 1 4 18
- / \ / \
- Niveau 2 2 3 11 20
- / /
- Niveau 3 1 19
- binär := max. 2 Kindelemente/Knoten
- Tiefe := größtes Niveau ("`Anzahl der Knoten zum tiefsten Element"')
- Konten := Element mit Daten und 1 oder mehr Kindelementen
- Wurzel := Oberster Knoten
- Kanten := Verbinden Knoten
- Blatt := Knoten ohne Kindelemente
- Traversierung := Durchlaufen
- Teilbaum := Baum, dessen Wurzel Konten eines anderen Baumes ist.
- Traversierung
- ooooooooooooooooooooooooooooooooooooooo
- Name Art Beschreibung
- +++++++++++++++++++++++++++++++++++++++
- Preorder WLR Wurzel Links Rechts
- Inorder LWR Links Wurzel Rechts
- Postorder LRW Links Rechts Wurzel
- ooooooooooooooooooooooooooooooooooooooo
- Löschen im binären Baum und andere wichtige Operationen werden durch das
- folgende Codestück erklärt.
- procedure TBinBaum.anhaengen(amKnoten, neuerKnoten: TKnoten); (* ... *)
- function TBinBaum.loeschen(daten: String): Boolean;
- begin
- if wurzel = nil then begin
- result := false;
- end else if wurzel.daten = daten then begin
- deleteRoot;
- result := true;
- end else begin;
- result := deleteElementFrom(daten, wurzel);
- end;
- end;
- procedure TBinBaum.deleteRoot; (* ... *)
- function TBinBaum.deleteElementFrom(element: String; node: TKnoten):
- Boolean;
- var
- newNode: TKnoten;
- begin
- result := false;
- if node <> nil then begin
- if node.toLinks <> nil then begin
- if node.toLinks.daten = element then begin
- newNode := node.toLinks.toLinks;
- if newNode = nil then begin
- newNode :=
- node.toLinks.toRechts;
- end else begin
- anhaengen(newNode,
- node.toLinks.toRechts);
- end;
- deleteOnly(node.toLinks);
- node.toLinks := newNode;
- result := true;
- end;
- end;
- if (result = false) and (node.toRechts <> nil)
- then begin
- if node.toRechts.daten = element then begin
- newNode := node.toRechts.toLinks;
- if newNode = nil then begin
- newNode :=
- node.toRechts.toRechts;
- end else begin
- anhaengen(newNode,
- node.toRechts.
- toRechts);
- end;
- deleteOnly(node.toRechts);
- node.toRechts := newNode;
- result := true;
- end;
- end;
- if result = false then begin
- result := deleteElementFrom(element,
- node.toLinks);
- end;
- if result = false then begin
- result := deleteElementFrom(element,
- node.toRechts);
- end;
- end;
- end;
- procedure TBinBaum.deleteOnly(node: TKnoten);
- begin
- node.toLinks := nil;
- node.toRechts := nil;
- node.destroy;
- end;
- ----------------------------------------------------------------------[ Heap ]--
- Ein Heap ist ein fast vollständiger binärer Baum, bei dem unter einem Knoten
- keine größeren Knoten vorkommen
- 5
- / \
- 4 1
- / \
- 3 2
- Baum im Array
- -------------
- Der Baum kann "`Preorder"' im Array gespeichert werden.
- Index 1 2 3 4 5
- Wert 5 4 1 3 2
- Die Wurzel zu einem Element in einem Solchen Array liegt bei `i div 2`.
- Einfügen
- --------
- Zum Einfügen kommt ein neues Element ans Ende des Arrays
- Index 1 2 3 4 5 6 5
- Wert 5 4 1 3 2 8 / \
- 4 1
- / \ /
- 3 2 8
- Dann wird es solange mit der Wurzel vertauscht, bis es größer ist. Damit ist der
- Heap wieder korrekt.
- 5 8
- / .\ / \
- 4 .1 -> 4 5
- / \ /. / \ /
- 3 2 8. 3 2 1
- ---------------------------------------------------[ Prioritätswarteschlange ]--
- Kehrt man die Vergleiche eines Heaps um, so kann man Elemente priorisiert
- anordnen. Kleine Zahl <=> große Priorität.
- 1 Zum Einfügen geht man vor, wie beim normalen Einfügen, nur
- / \ dass der Vergleich nicht "`größer"', sondern "`kleiner"'
- 2 4 ist.
- / \ /
- 3 5 (8)
- Zum Entnehmen entnimmt man die Wurzel und stellt das letzte Element an ihre
- Stelle. Dann tauscht man rekursiv mit dem kleinsten Kindelement, bis beide
- Kindelemente größer dem neuen Element sind
- 1 .8 2
- / \ ./ \ / \
- 2 4 -> .2 4 -> 3 4
- / \ / ./ \ / \
- 3 5 8 3 5 8 5
- Dadurch ist wieder ein gültiger Heap entstanden. Der Vorteil des Heaps ist, dass
- alles mit garantiert O(n log n) läuft.
- -----------------------------------------------------------------[ Der Stack ]--
- Der Stack ist auch als "`Keller"' bekannt.
- LIFO := Last in, first out
- Ein Stack kennt nur wenige Oparationen
- push
- Legt ein Element auf den Stack
- pop
- Entnimmt das oberste Element
- head oder top
- Gibt das oberste Element zurück, ohne es zu löschen
- isEmpty
- Gibt `true` zurück, falls der Stack leer ist
- clear
- Löscht alle Elemente aus dem Stack
- Üblicherweise werden Stacks mit Zeigern ähnlich einer einfach verketteten Liste
- im Speicher abgebildet. Vgl: `/q1/stack/Lists.pas`.
- -------------------------------------------------------[ Die Türme von Hanoi ]--
- T(n) = 2^n - 1
- # # #
- # # #
- -#- # #
- --#-- # #
- ---#--- # #
- ######### ######### #########
- Der "`sortierte"' Stapel soll auf einen anderen Stack. Es dürfen nie kleinere
- Elemente unter größeren liegen. Nur Stackoperationen sind gestattet.
- ---------------------------------------------------------------[ Datenbanken ]--
- Wir behandeln in der Schule nur relationale Datenbanken.
- RDBMS := Relationales DatenBank Management System
- --------------------------------------------------------------[ ER-Diagramme ]--
- Mit ER-Diagrammen (ER := Entity Relationship), sollen sich relationale
- Datenbankmodelle entwickeln lassen.
- ER-"`Syntax''
- -------------
- .......... Entity
- . Entity .
- .......... Wird später eine Tabelle
- ____ Attribut
- / \
- / Attr \ Wird später eine Spalte, Schlüssel werden unterstrichen.
- \ ibut / In der "`Grafik"' schlecht zu erkennen:
- \____/ Attribute werden eingekreist.
- /====\ Mehrfachattribut
- // \\
- // Attr \\ Später `Array`, mehrere Spalten oder getrennte Tabelle.
- \\ ibut //
- \\ // Mehrfachattribute werden doppelt eingekreist.
- \====/
- --------- Verbindung/Linie
- /\ Beziehung
- / \
- /Bezi\ verbinden Entities und können selbst Attribute haben.
- \hung/ Spezielle "`is-A"' Beziehung kennzeichnet "`Vererbung"'.
- \ / Beziehungen können mehr als zwei Entities verbinden und
- \/ Entities können über mehrere Bezieungen verbunden sein.
- ER-Beziehungen "`Kardinalitäten"'
- ---------------------------------
- Eine Beziehung kann eine von drei Komplexitäten haben.
- 1:1
- Eineindeutige Zuordnung (Bijektion).
- 1:n
- Einem Entity werden mehrere Entities zugeordnet. Umgekehrt kann jedem
- zugeordneten Entity nur ein Entity zugeordnet sein.
- n:m
- Dem ersten Entity werden mehrere zweite Entities zugeordnet, aber auch
- umgekehrt können einem zweiten Entity mehrere erste zugeordnet werden.
- Die Wahl der Komplexität wird immer begründet, denn sie ist mitunter
- interpretationsabhängig.
- Die Umwandlung von Beziehungen in Tabellen ist nicht immer einfach. Wenn es sich
- um eine Beziehung zwischen zwei Entities handelt, werden diese üblicherweise
- beide ein gleiches Attribut haben, um die Beziehung herzustellen. Häufig ist
- dieses Attribut noch nicht im ER-Diagramm ersichtlich. Bei Beziehungen mit
- zusätzlichen Attributen können diese in einer der beteiligten Tabellen als
- Spalte hinzugefügt oder in eine eigene Tabelle ausgelagert werden. Ziel sollte
- es dabei sein, möglichst wenige Tabellen bei geringer Redundanz ainzusetzen.
- Optionalitäten
- --------------
- /\
- ........... n / \ 1 ........
- . Patient .------/hat \---------. Arzt .
- ........... muss \ / kann ........
- \ /
- \/
- Dies ist ein Auszug aus einer Aufgabe. Diese "`hat Beziehung"' ist vom Patienten
- als "`hat als Hausarzt"' zu lesen.
- Jeder Patient muss daher einen Hausarzt haben, ein Arzt kann jedoch Hausarzt von
- mehreren Patienten sein oder gar keine Patienten haben.
- ----------------------------------------------------------------[ Relationen ]--
- In der Theorie zur relationalen Datenbank heißen Tabellen auch Relationen.
- Kompakte Beschreibung von Tabellen
- * `Tabelle(Attribut, ...)`
- * Primärschlüssel unterstreichen
- * Zeilen können auch als Tupel dargestellt werden
- Die Relationenschreibweise hat drei "`Datentypen"'
- 1. Primärschlussel (Attribut wird unterstrichen).
- 2. Fremdschlüssel (Attribut bekommt Pfeil nach oben).
- 3. Werte (Attribut bekommt keine zusätzlichen Zeichen).
- Beispiel: `Programm(_ID_, Datei, Größe, Typ, Bild^)`
- ---------------------------------------------------------[ Relationenalgebra ]--
- "`MQL -- Mathe Query Language''
- Schnittmenge
- Gleiche Elemente zweier Tabellen (kommutativ).
- Vereinigung `U`
- Alle Elemente zweier Tabellen (kommutativ). SQL: `UNION`
- Differenz `\`
- Erste Tabelle "`ohne"' zweite Tabelle (nicht kommutativ).
- Produkt {$\times$}
- Kartesisches Produkt: Alle Kombinationen (kommutativ).
- Selektion {$\sigma_\textrm{Bedingung}(\textrm{Von})$}
- Selektiert aus der Tabelle "`Von"' alle Zeilen, die die Bedingung
- erfüllen. SQL: `SELECT * FROM Von WHERE Bedingung`
- Projektion {$\pi_\textrm{Attribute}(\textrm{Von})$}
- Selektiert Spalten aus "`Von"'. SQL: `SELECT Attribute FROM Von`
- Join `|><|`
- Verbindet zwei Tabellen über ein gemeinsames Attribut.
- SQL: `SELECT ... FROM ... INNER JOIN ... ON ...`
- Bildung des Joins
- 1. Kartesisches Produkt
- 2. Nicht übereinstimmende Attribute streichen
- 3. Überflüssige Spalten löschen
- P `|><|` Q
- ----------
- {$\pi_\textrm{Spalten}(\sigma_\textrm{Vergleich}(\textrm{P}\times\textrm{Q}))$}
- "`Vergleich"'
- stellt gleiche Vergleichselemente Sicher
- Projektion "`Spalten"'
- Wählt die Vereinigungsmenge der Tabellenspalten.
- Vergleich: SQL und Relationenalgebra
- ------------------------------------
- SQL beherrscht die praktische Zusammenfügung von Selektion, Projektion und Join
- in einem. Weiterhin ist SQL durch das `JOIN ... ON ...` eindeutiger und kommt
- auch mit Tabellen mit mehreren gleichen Spaltennamen zurecht. Die von den
- Mengen bekannten Operationen sind hingegen schwieriger durchzuführen und die
- Syntax ist etwas komplizierter.
- Dafür funktioniert die Relationenalgebra ähnlich MongoDB Pipelines: Man schaltet
- Filter hintereinandser, was bei bestimmten Abfragen wesentlich eingängiger ist,
- als die passende SQL Syntax.
- ----------------------------------------------[ Normalisierung und Anomalien ]--
- Normalisierung ist eine Art "`Brecheisen"' zum Erzeugen von guten Tabellen,
- falls man schlechte hat. Damit kann man auch aus ER-Diagrammen mit allen
- Kardinalitäten und Optionalitäten optimierte Tabellen machen, wodurch auch
- ER-Diagramme für ernsthafte Datenbankentwicklung taugen.
- Als Beispiel soll folgende, dumm gemachte, Tabelle dienen:
- `Page(_File_, Title, Keywords, ParentFile^)`
- Anomalien
- ---------
- Einfüge-
- Nicht alle Daten, die einfefügt werden müssten, sind schon bekannt.
- Lösch-
- Bestimmte Einträge können nicht gelöscht werden, ohne dass
- Behaltenswerte Informationen verloren gehen.
- Änderungs-
- Einträge lassen sich nicht ändern, weil sie in anderen Tabellen als
- Fremdschlüssel auftauchen. Alternativ: Die Änderung eines Eintrags führt
- zu inkonsistenzen.
- Nullwerte
- gelten in RDBMS auch als Quellen für Anomalien und werden bei
- Aggregatfunktionen (`SUM`, `AVG`, `COUNT`, ...) und `SELECT`-Anfragen,
- die für eine Spalte mit Nullwerden Bedingungen definieren nicht
- dazugezählt beziehungsweise berücksichtigt.
- Bei der Beispieltabelle gibt es Anomalien.
- 1. Änderungsanomalie: `File` kann unter Umständen nicht umbenannt werden.
- 2. Nullwerte: `ParentFile` kann `NULL` (für `/`) sein.
- Erste Normalform
- ----------------
- Eine Relation ist in der ersten Normalform, wenn keine Mehrfachattribute
- vorkommen.
- Im Beispiel müssen entweder mehrere Tabellen entstehen, oder man
- legt fest, dass `Keywords` kein Array ist, sondern der Eintrag für jedes
- geänderte Keyword eben wiederholt wird. Damit wird allerdings der
- Primärschlüssel ungültig und muss ausgeweitet werden.
- Page(_File_, Title, _Keyword_, ParentFile^)
- Zweite Normalform
- -----------------
- Die zweite Normalform bedingt die erste Normalform und fordert, dass kein
- nicht-Schlüssel Attribut funktional abhängig von Teilschlüsseln ist.
- Im Beispiel sind nach dem Umformen in die erste Normalform, `File`, `Title` und
- `ParentFile` funktional abhängig, weshalb `Keyword` in eine getrennte Tabelle
- ausgelagert werden muss.
- Page(_File_, Title, ParentFile^)
- Keyword(_File_^, _Keyword_)
- Dritte Normalform
- -----------------
- Die dritte Normalform bedingt die zweite Normalform und fordert, dass keine
- funktionalen Abhängigkeiten zwischen nicht-Schlüsselattributen bestehen.
- Meistens kann man auch sagen: Es dürfen keine Redundanzen vorkommen.
- Nachdem man die zweite Normalform erstellt hat, wie oben angegeben, befindet
- sich die Tabelle auch in der dritten Normalform.
- Problem
- -------
- Die Datenbank ist jetzt in der dritten Normalform, aber immernoch nicht ideal:
- Dateien lassen sich nicht einfach umbenennen, weil sie als Schlüsselattribut
- verwendet werden. In der Praxis würde man etwa folgende Struktur entwickeln:
- Page(_ID_, File, Title, ParentFile^)
- Keyword(_Page_^, _Keyword_)
- Damit ließen sich Dateien problemlos umbenennen.
- -----------------------------------------[ Die Structured Query Language SQL ]--
- Data Definition Language
- * `CREATE TABLE table ( attribute SERIAL, ... );`
- * `DROP TABLE table;`
- Data Control Language
- * `CREATE ROLE testuser WITH PASSWORD 'testwort';`
- * `GRANT testuser ALL PRIVILEGES ON db;`
- Data Manipulation Language
- * `INSERT INTO table VALUES (...);`
- * `INSERT INTO table (attributes) VALUES (...);`
- * `UPDATE table SET expression WHERE condition;`
- * `SELECT * FROM table;`
- Für unsere Informatik ist nur die DML relevant. Dabei beschäftigen wir uns
- insbesondere mit `SELECT` zur Abfrage.
- ------------------------------------------------------[ SELECT und Ähnliches ]--
- Aufbau
- DELETE FROM tables WHERE cond
- SELECT data FROM tables WHERE cond mod
- SELECT DISTINCT ~ -- keine doppelten Zeilen ausgeben
- `data`
- * Spaltennamen: `s1, s2`
- * Umbenennen: `s1 AS spalte1`
- * Ausdrücke: `s1 * 4 AS fs1`
- * Aggregatfunktionen: `SUM`, `AVG`, `MIN`, `MAX`, `COUNT`
- `tables`
- Tabellenliste (umbenennen mit `AS`)
- `cond`
- Join mit `SELECT T1.X, T2.X FROM T1, T2 WHERE T1.T2ID = T2.ID;`
- oder `SELECT T1.X, T2.X FROM T1 INNER JOIN T2 ON T1.T2ID = T2.ID;`
- `mod`
- * `GROUP BY` wendet Aggregatfunktionen auf Gruppen an.
- * `HAVING` ist `WHERE` für _Ergebnisse_ von `GROUP BY`
- * `LIMIT n, m` Gibt Ergebnisse e [n;m] aus.
- * `ORDER BY s` Sortiert die Ausgabe `ASC` (1, 2, 3, ...) oder
- `DESC` (..., 3, 2, 1).
- Subqueries
- SELECT U.Name,
- COUNT(SELECT ID FROM iTrace WHERE iTrace.Name = U.Name) AS iC
- FROM Users AS U;
- Operatoren
- ----------
- `=` und `<>`
- ist gleich und ungleich
- `LIKE`
- Ungefär, Wildchards BRE `*`, `?`, spezielle `%`.
- `>` und `>=`
- Echt größer und größer gleich
- `<` und `<=`
- Echt kleiner und kleiner gleich
- `BETWEEN a AND b`
- Zwischen a und b (beide inclusive)
- `IN(a,b,c)`
- Element der Menge, funktioniert auch mit Subquery.
- `AND` und `OR`
- Logisches und beziehungsweise oder.
- `NOT`
- Logisches nicht.
- `IS NULL`
- Testen auf Nullelement.
- --------------------------------------------[ Diverses zum Thema Datenbanken ]--
- Wie man Datenbanken entwickeln sollte
- 1. Planen, was man speichern, ändern, löschen will
- 2. Relationenmodell mit Datentypen entwickeln
- 3. Gegen Normalform testen, aber nicht erzwingen
- 4. `CREATE` Anweisungen erstellen
- 5. Setup schreiben
- `mysql_select_db()` <=> `OPEN 'db';`
- MySQL
- * String: `'Str'`
- * Tabelle: `\`tab\``
- * Datum `YYYY-MM-DD` (`Y-m-d`)
- --------------------------------------[ Fragen der Theorethischen Informatik ]--
- Was kann ein Computer (können), was nicht?
- Limitationen: Geschwindigkeit, Beziehungsprobleme
- Halteproblem
- Man kann kein Programm schreiben, dass die Terminierung eines Programmes
- beweist.
- NP-vollständige Probleme
- Grenze der perfekt lösbaren Probleme
- Was ist Sprache?
- Wie ist Sprache für den Computer zu definieren. Parser und Compiler.
- Entscheideproblem
- Beweis von Aussagen
- Goldbach-Vermutung
- Jede gerade Zahl > 2 kann als Summe zweier Primzahlen dargestellt werden
- Wundersame Zahlen
- a(n+1) = 3a(n) + 1 für ungerades n und a(n)/2 für gerades n.
- Endet bei Wiederholung auf 1? Das Problem ist nicht berechenbar.
- Im Folgenden stehen Klammern `()` oft für Kreise und `[]` für Rechtecke
- ------------------------------------------------------------------[ Sprachen ]--
- Sprache L := Menge aller gültigen Wörter
- X := Alphabet, X* := Alle Kombinationen (Mengenvereinigung L hoch i mit i -> oo)
- S := Startsymbol
- Vt := Menge der Terminale
- Vn := Menge der Nichtterminale
- P := Menge der Regeln "`Produktionen"'
- ---------------------------------------------------------------[ Grammatiken ]--
- X oder Vt muss angegeben werden. Eine Grammatik aller 0-1-Wörter, die auf 0
- enden (`(0|1)*0`):
- Vt = { 0; 1 }
- S -> 0S | 1S | 0 <=> S -> 0S <=> P = { S -> 0S; S -> 1S; S -> 0 }
- S -> 1S
- S -> 0
- Ableitung des Wortes `011010`
- S -> 0S -> 01S -> 011S -> 0110S -> 01101S -> 011010
- Ableitungsbaum
- S
- / \
- 0 S
- / \
- 1 S
- / \
- 1 S
- / \
- 0 S
- / \
- 1 S
- /
- 0
- Syntaxdiagramme (rekursiv vs. iterativ)
- S +--------------------------------+
- -->+--( 0 )--[ S ]--+ S v |
- | | ~ -------->( 0 )----->( 1 )--->( 0 )----->
- +--( 1 )--[ S ]--+ ~ | ^ | ^
- | | +---------+ +--------+
- +--( 0 )---------+-->
- ----------------------------------------[ Chomsky Hierarchie der Grammatiken ]--
- Sparchen werden in die Hierarchie eingeordnet, indem man sie mit dem
- höchstmöglichen Grammatiktyp beschreibt.
- ......................................................................
- . Typ 0 allgemein x -> y (x != e) .
- . ................................................................ .
- . . Typ 1 kontextsensitiv x A y -> x z y (z != e) . .
- . . .......................................................... . .
- . . . Typ 2 kontextfrei A -> x . . .
- . . . .................................................... . . .
- . . . . Typ 3 regulär A -> aB | e (etwa A -> a | aB) . . . .
- . . . .................................................... . . .
- . . . . . .
- . . .......................................................... . .
- . . . .
- . ................................................................ .
- . .
- ......................................................................
- x, y, z := beliebige Folgen von A, B, a, b; e := leeres Wort (Epsilon)
- a, b := beliebiges Terminal; A, B := beliebiges Nichtterminal
- ----------------------------------[ DEA: Deterministischer Endlicher Automat ]--
- Startzustand
- z{$_0$}, s{$_0$}, `->(S)`
- Endzustand
- `((Z))` -- doppelt eingekreister Zustand
- Zustand
- `(C)`
- Übergang
- `(E) -x-> (F)`, wobei `x` über den Pfeil geschrieben wird.
- `x` bezeichnet das gelesene Zeichen.
- Schleife
- `(E)>x` (man zeichnet eine Schleife
- Darstellungsmöglichkeiten
- ........................................................................
- . .
- . _____ Zustandstabelle Ableitung von .
- . / \ 0 oooooooooooooooooooooooooo 011010: .
- . 0 | | Momentan Eingabe Neu .
- . ->(S)----->((E))<--/ ++++++++++++++++++++++++++ S 0 E .
- . /^^ | S 1 S E 1 S .
- . 1 \/\________/1 S 0 _E_ S 1 S .
- . _E_ 0 _E_ S 0 E .
- . _E_ 1 _S_ E 1 S .
- . oooooooooooooooooooooooooo S 0 _E_ .
- . .
- . Endzustände werden in den Tabellen unterstrichen. .
- ........................................................................
- -----------------------------[ NEA: Nichtdeterministischer Endlicher Automat ]--
- Automat, bei dem von einem Zustand mehrere Wege mit dem gleichen Zeichen
- abgehen.
- .............................
- . 0 1 .
- . (S)------->((E))--->(F) .
- . /^ /^ Fehler .
- . \/ 0,1 \/ 0 .
- .............................
- -----------------------------------------------------------[ Vom NEA zum DEA ]--
- Die beiden Automatentypen sind gleichmächtig. Mit der Potzenmengenmethode kommt
- man vom einen zum Anderen. Dazu werden "`Uneindeutige"' Wege zusammen
- betrachtet. Die Tabelle gibt dann den neuen Automaten an.
- ooooooooooooooooooooooooooo
- X 0 1
- +++++++++++++++++++++++++++
- S (_E,S_) S
- (_E,S_) (_E,S_) (S,F)
- (S,F) (_E,S_) S
- ooooooooooooooooooooooooooo
- Alle Zustände, die einen "`ehemaligen"' Endzustand enthalten, werden Endzustände
- ............................. Der entstehende Automat ist nicht optimal
- . /\ 0 . im Sinne möglichst weniger Zustände.
- . 0 \v .
- . --->(z0)------->((z1)) .
- . /^ ^ | | .
- . 1 \/ \______ 1| / 0 .
- . 1 \ v / .
- . (z2) .
- .............................
- -----------------------[ Reguläre Ausdrücke in der theorethischen Informatik ]--
- Syntax
- * `|` := ODER
- * `(` und `)` := Klammerung
- * {$\epsilon$} := Leeres Wort
- * `*` := 0 bis n-fache Widerholung
- * Außerdem werden `?` und `+` laut Glossar erlaubt. TODO ERGÄNZEN
- Konkatenation
- Sprachen über selbem Alphabet werden über kartesisches Produkt verbunden
- reguläre Sprache L(r)
- Alle Wörter, die Ausdruck "`r"' matcht.
- ----------------------[ Beispiel: Automat erkennt durch drei Teilbare Zahlen ]--
- Alphabet A := \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}
- REM: Arithmetik modulo 3.
- .........................................
- . .
- . 0,3,6,9 0,3,6,9 0,3,6,9 .
- . /\ /\ /\ .
- . \v 1,4,7 \v 1,4,7 \v .
- . (s0)--------->(r1)--------->(r2) .
- . ^|^___________/ ^___________/^ \ .
- . || 2,5,8 2,5,8 | \ .
- . |\____________________________/ | .
- . | 2,5,8 / .
- . \_______________________________/ .
- . 1,4,7 .
- . .
- .........................................
- -----------------------------------------------------------[ Kellerautomaten ]--
- Definition
- * Endlicher Automat + Stack
- * Stack leer <=> Wort aktzeptiert
- * gelesenes Zeichen, oberes Kellerzeichen,
- Kelleroperation (`push` Zeichen, `pop`, `nop`)
- Schreibweise
- 1. Zustand Eingabe Stack.top -> Operation Zustand
- 2. Zustandsdiagramm
- 3. Tabelle
- ...................... Tabellarische Darstelung des Automaten
- . --->(z0) . ooooooooooooooooooooooooooooooooooooooooooooo
- . /^ a a push a . Zustand Eingabe Top Operation Zustand
- . \/ a # push a . +++++++++++++++++++++++++++++++++++++++++++++
- . b a pop . z0 a a push a z0
- . . z0 a # push a z0
- . . z0 b a pop z0
- ...................... ooooooooooooooooooooooooooooooooooooooooooooo
- Alle anderen Eingaben führen zum Fehlerzustand.
- Anwendung
- * Klammerausdrücke
- * einige kontextfreie Grammatiken
- * Mit Trennzeichen getrennte Palindrome
- -----------------------------------------------------------[ Turingmaschinen ]--
- Definition
- * Kann alles Berechenbare brechnen
- * Zustand BandIN -> BandOut Bewegung Zustand
- * Bewegung `L` (nach links), `R` (nach rechts), `N` (nop), `H` (beenden)
- Schreibweise: Turingprogramm, Zustandsdiagramm oder Tabelle
- 1##R1 Dieses Programm ersetzt auf einem Band mit 1en und 0en alle
- 10#R2 0en durch das Leerzeichen `#`
- 111R2
- 2##N2 H
- 211R2
- 10#R2
- ------------------------------------------------------------[ Fleißige Biber ]--
- * Turingmaschine mit n Zuständen und dem Alphabet \{`1`, `#`\} soll möglichst
- viele Einsen schreiben und dann terminieren
- * Die Maximale Anzahl möglicher Einsen für einen Biber mit n Zuständen ist
- nicht berechenbar.
- * Die Anzahl der Einsen in Abhängigkeit von den Zuständen steigt schneller als
- exponentiell.
- 2 Zustände, 4 Einsen, 4 Schritte, optimal
- 0#1L1
- 011R1
- 1#1R0
- 111H1
- 3 Zustände, 6 Einsen, 13 Schritte, optimal
- 0#1R1
- 011L2
- 1#1R2
- 111H1
- 2#1L0
- 21#L1
- 4 Zustände, 13 Einsen, 107 Schritte, optimal
- 0#1R1
- 011L1
- 1#1L0
- 11#L2
- 2#1H2
- 211L3
- 3#1R3
- 31#R0
- ---------------------------------------------------------[ Das Hilbert Hotel ]--
- 1. Das HIlbert Hotel hat unendlich viele Zimmer.
- 2. Ein Bus mit unendlich Gästen kommt. Alle passen in das Hotel.
- 3. Ein einzelner Gast kommt hinzu. Auch er passt ins Hotel, er bekommt das
- erste Zimmer und alle anderen Gäste rücken ein Zimmer nach hinten.
- 4. Unendlich viele Busse mit je unendlich vielen Gästen kommen. Die Gäste aus
- dem ersten Bus belegen alle Zimmernummern kongruent modulo 2
- (2, 4, 8, 16, 32, ...). Die Gäste aus dem zweiten Bus belegen alle
- Zimmernummern kongruent modulo 3 und für die weiteren Busse werden weitere
- Primzahlen (von denen es unendlich viele gibt) verwendet.
- 5. Dabei bleiben immernoch unendlich Zimmer frei, etwa die Zimmernummer 6 oder
- 10.
- ----------------------------------------------[ Patterns für Turingmaschinen ]--
- Im Folgenden ist das Leerzeichen `#` und Daten sind `0` und `1`.
- Ans Ende des Bandes gehen
- 1##R1 Überspringen führender Leerzeichen v v
- 111R2 ##1100## -> ##1100##
- 100R2
- 211R2 Überspringen von Daten
- 200R2
- 2##LX Cursor steht eins links vom Ende
- Hinter das Ende des Bandes schreiben
- 111R1 211R2 v v
- 100R1 200R2 ##1100### -> ##1100#1#
- 1##R2 2#1LX
- Drei Einsen Schreiben
- 1#1R2 v v
- 2#1R3 ##### -> #111#
- 3#1RX
- Daten Transformieren
- 1. transformieren z.\,B. rechts von den Daten notieren
- 2. Alte Daten löschen (ähnlich geht man beim Verschieben vor)
- Anzahlen in Zuständen speichern
- 1. Programmteil zum Abarbeiten der Daten (1).
- 2. Programmteil zum Zurückgehen (B).
- 3. Programmteile zum Schreiben der Anzahlen von Zeichen
- Blockaufbau
- Man kann die obigen Abschnitte als Textblöcke notieren. Idealerweise
- lässt man Platz für eine Beschreibung oder macht vorher einen Plan.
- Graphenaufbau
- Lehrer empfiehlt das Zeichnen von Graphen wie bei anderen Automatenarten
- ------------------------------------------[ Beispielturingmaschine x16F Nr 5 ]--
- Erwartete Eingabe
- `#iiiiii#` (Strichliste)
- Ausgabe
- `#vi#` (verkürzte Strichliste)
- Vorgehen
- Wir erkennen zunächst alle 5er Päckchen. Kommt keines mehr, kopieren wir
- die Resteinsen. Am Ende wird der Verschnitt gelöscht.
- Programm
- +-[ Main ]-+ +-[ CP|WV ]-+ +-[ Dup i ]-+ +-[ Clean ]---+
- | | | | | | | |
- | 1##R1 | | 6iiR6 | | 9ixRA | | Cx#LC |
- | 1iiR2 | | 6##R7 | | 9##LC | | Ci#LC |
- | | | | | | | C##HC |
- | 2##LF | | 7#vLB | | AiiRA | | |
- | 2iiR3 | | 7vvR7 | | A##RD | +-------------+
- | | | | | |
- | 3iiR4 | +-----------+ | DvvRD | +-[ Back II ]-+
- | 3##LF | | DiiRD | | |
- | | +-[ Back ]--+ | D#iLE | | EvvLE |
- | 4##LF | | | | | | EiiLE |
- | 4iiR5 | | BvvLB | +-----------+ | E##LF |
- | | | B##L8 | | |
- | 5##LF | | | | FiiLF |
- | 5ixR6 | | 8iiL8 | | FxxR9 |
- | | | 8xxR1 | | F##R9 |
- +----------+ | | | |
- +-----------+ +-------------+
- -------------------------------------------------------------------[ Graphen ]--
- Adjazentzmatrix
- Zum Graphen werden in einer y|x-Matrix überall dort 1en geschrieben, wo
- es eine Kante gibt. Der Rest sind 0en. Ungerichtete Graphen sind so
- immer symmetrisch.
- (D)-------(C) ABCDE (D)----->(C) ABCDE
- |\ | A01010 |^ | A01000
- | \ | B10100 | \ | B00100
- | (E) | C01010 | (E) | C01000
- | | D10101 v | D10100
- (A)-------(B) E00010 (A)----->(B) E00010
- Adjazenzliste
- Die Adjazentliste ordnet y-Knoten alle x-Knoten zu, die mit ihnen
- verbunden sind. Für das erste Beispiel:
- A -> B, D; B -> A, C; C -> B, D; D -> A, E, C; E -> D.
- -----------------------------------------------[ Königsberger Brückenproblem ]--
- Finde Reise genau 1x über jede Brücke.
- ........................................
- . A . (A)---\
- . +--[####]--[####]--+--[####]--//-. | | \
- . | B # D . (B)----(D)
- . | # . | | /
- .-//--+--[####]--[####]--+--[####]--//-. (C)---/
- . C .
- ........................................
- Ungerade Anzahl an Wegen zu D => nicht möglich.
- ................................................
- . *********** . /(A)
- . A +--[*###]--[##*#]--+----------//-. / | |
- . * | B *********** D . | (B)----(D)
- . * | ********* # * . \ | | /
- .-//--[##*#]--+--[#*##]--[#*##]--+--[#*##]--//-. \(C)---/
- . *********** ************ C .
- ................................................
- Gerade Anzahl an Kanten zwischen jedem Knoten => OK.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement