Advertisement
Linux-Fan

Informatik Zusammenfassung

Feb 12th, 2014
356
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 44.02 KB | None | 0 0
  1. ----------------------------------------------------------------------[ Meta ]--
  2.  
  3. name informatik/q1bis4
  4. section 35
  5. description Informatik Zusammenfassung von Q1 bis Q4 (vor dem Abitur)
  6. tags informatik q1 q2 q3 q4 school abi2014
  7. encoding utf8
  8. compliance informal
  9. lang de
  10. creation 02/2014
  11. version 1.0.0.0
  12. copyright Copyright (c) 2014 Ma_Sys.ma.
  13. For further info send an e-mail to Ma_Sys.ma@web.de.
  14.  
  15. --------------------------------------------------------------------[ Lizenz ]--
  16.  
  17. Diese Datei steht unter GPL 3.
  18.  
  19. This program is free software: you can redistribute it and/or modify
  20. it under the terms of the GNU General Public License as published by
  21. the Free Software Foundation, either version 3 of the License, or
  22. (at your option) any later version.
  23.  
  24. This program is distributed in the hope that it will be useful,
  25. but WITHOUT ANY WARRANTY; without even the implied warranty of
  26. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  27. GNU General Public License for more details.
  28.  
  29. You should have received a copy of the GNU General Public License
  30. along with this program. If not, see <http://www.gnu.org/licenses/>.
  31.  
  32. --------------------------------------------------------------------[ Delphi ]--
  33.  
  34. Grundlegendes
  35.  
  36. if BEDINGUNG then begin if(BEDINGUNG) {
  37. ANWEISUNGEN; ANWEISUNGEN;
  38. end else if BEDINGUNG then begin } else if(BEDINGUNG) {
  39. ANWEISUNGEN; ANWEISUNGEN;
  40. end else begin } else {
  41. ANWEISUNGEN; ANWEISUNGEN;
  42. end; (* kein fi *) }
  43.  
  44. while BEDINGUNG do begin while(BEDINGUNG) {
  45. ANWEISUNGEN; ANWEISUNGEN;
  46. (* break bricht ab *) }
  47. end; (* kein done *)
  48.  
  49. for i := START to END do begin for(int i = 0; i <= END; i++) {
  50. ANWEISUNGEN; (* END incl.*) ANWEISUNGEN;
  51. end; (* kein done *) }
  52.  
  53. case VARIABLE of switch(VARIABLE) {
  54. CONST: begin case CONST:
  55. ANWEISUNGEN; ANWEISUNGEN;
  56. end; break;
  57. CONST: begin case CONST:
  58. ANWEISUNGEN; ANWEISUNGEN;
  59. end; break;
  60. else begin default:
  61. ANWEISUNGEN; ANWEISUNGEN;
  62. end; (* kein esac *) }
  63.  
  64. Funktionen
  65.  
  66. procedure name(paramName: paramType; paramName: paramType);
  67. var
  68. variable: Typ;
  69. begin
  70. ANWEISUNGEN; (* exit; <=> return; *)
  71. end;
  72.  
  73. function name(PARAMETER): returnType;
  74. var
  75. Variablendeklarationen
  76. begin
  77. name := wert; (* ~ return wert, aber kein Abbruch *)
  78. (* alt: *)
  79. result := wert;
  80. end;
  81.  
  82. Typdeklarationen
  83.  
  84. type
  85. et2a: Array[0..20] of Integer;
  86. name: equivalenztyp;
  87.  
  88. Funktionsbibliothek
  89.  
  90. intToStr(param: Integer): String;
  91. strToInt(param: String): Integer;
  92.  
  93. randomize;
  94. randint(MAX): Integer; (* [0;MAX[ *)
  95.  
  96. edit.text := strVal;
  97.  
  98. writeLn(out);
  99. readLn(into);
  100. write(out);
  101.  
  102. 2D Array
  103.  
  104. test: Array[0..9,0..9] of Integer; (* <=> int[10][10] *)
  105.  
  106. Hello World
  107.  
  108. program Hello;
  109.  
  110. (* Procedure, var, const, function, etc... hier *)
  111.  
  112. begin
  113. writeLn('Hello world.');
  114. end;
  115.  
  116. ----------------------------------------------------------[ Sortierverfahren ]--
  117.  
  118. Sortieren durch Auswahl
  119. -----------------------
  120.  
  121. Gehe Array durch und bestimme kleinsten Wert. Speichere ihn an die momentan zu
  122. bearbeitende Stelle und verschiebe den alten Wert an die vorherige Stelle des
  123. kleinsten Wertes.
  124.  
  125. procedure sort;
  126. var
  127. i, j, k, min: Integer;
  128. begin
  129. for i := 0 to length(feld) - 2 do begin
  130. j := i;
  131. min := feld[i];
  132. for k := i + 1 to length(feld) - 1 do begin
  133. if feld[k] < min then begin
  134. j := k;
  135. min := feld[k];
  136. end;
  137. end;
  138. feld[j] := feld[i];
  139. feld[i] := min;
  140. end;
  141. end;
  142.  
  143. Sortieren durch Austausch
  144. -------------------------
  145.  
  146. Bubblesort. Wie Auswahl, nur jedesmal tauschen.
  147.  
  148. Den ersten Eintrag mit allen größeren tauschen => erster Eintrag = kleinster;
  149.  
  150. Quicksort
  151. ---------
  152.  
  153. Bringe alle kleineren Einträge auf die linke und alle größeren auf die Rechte
  154. Seite und rufe das Verfahren auf die Teilgruppen auf. O(n log n).
  155.  
  156. Wichtig auch
  157. Mitte ist nur ein ungefärer Ausdruck. Schwankt je nach Eingabedaten.
  158.  
  159. procedure quicksort(var f: feld; start, ende: Integer); (* ende incl. *)
  160. var
  161. zl,zr,mitte,tmp: Integer;
  162. begin
  163. zl := start; (* Zeiger mit Auschnittsgrenzehn belegen, *)
  164. zr := end; (* normalerweise 0, length - 1 *)
  165.  
  166. (* Wert des mittleren Eintrages *)
  167. mitte := f[(start + ende) div 2];
  168.  
  169. repeat
  170. (* Stelle den linken Zeiger soweit nach vorne, dass der
  171. Wert auf den er zeigt > mitte ist. *)
  172. while f[zl] < mitte do begin
  173. zl := zl + 1;
  174. end;
  175.  
  176. (* Stelle den rechten Zeiger solange zurück, bis er auf
  177. einen Wert < mitte zeigt. *)
  178. while f[zr] > mitte do begin
  179. zr := zr - 1;
  180. end;
  181.  
  182. (* Situation: zl und zr zeigen auf Werte, die auf der *)
  183. (* jeweils falschen Seite sind, sofern zl > zr ist. *)
  184. (* Ansonsten ist alles auf der richtigen Seite *)
  185. if not zl > zr then begin
  186. tmp := f[zl];
  187. f[zl] := f[zr];
  188. f[zr] := tmp;
  189. end;
  190. until zl > zr;
  191.  
  192. (* Sortiere [start;zr] falls der Bereich noch zu sortiren ist
  193. <=> falls es ihn noch gibt. *)
  194. if start < zr then begin
  195. quicksort(f, start, zr);
  196. end;
  197.  
  198. (* Sortiere [zl;ende] falls der Bereich noch zu sortieren ist
  199. <=> falls es ihn noch gibt. *)
  200. if zl < ende then begin
  201. quicksort(f, zl, ende);
  202. end;
  203. end;
  204.  
  205. -----------------------------------------------------------------[ Rekursion ]--
  206.  
  207. * Immer weniger efektiv, als Iteration, wegen eventuell doppelten Aufrufen und
  208. Rücksprungaddressen
  209. * keine weiteren, wichtigen Erkenntnisse
  210.  
  211. ---------------------------------------------------------[ Delphi Datentypen ]--
  212.  
  213. oooooooooooooooooooooooooooooooooooooooooooooo
  214. Delphi C Min Max
  215. ++++++++++++++++++++++++++++++++++++++++++++++
  216. byte unsigned char 0 2^8 -1
  217. word (int12) 0 2^12 -1
  218. shortint char -2^7 2^7 -1
  219. smallint int16_t -2^15 2^15 -1
  220. integer int -2^31 2^31 -1
  221. longint long -2^31 2^31 -1
  222. cardinal unsigned long 0 2^32 -1
  223. longword unsigned long -2^63 2^63 -1
  224. int64 long long int -2^63 2^63 -1
  225. single float
  226. real float
  227. double double
  228. extended long double
  229. boolean bool true | false
  230. char char
  231. shortString char[255]
  232. string char* Max. 3 GiB
  233. oooooooooooooooooooooooooooooooooooooooooooooo
  234.  
  235. -----------------------------------------------[ Zeiger und Listen in Delphi ]--
  236.  
  237. ooooooooooooooooooooooooooooooooooooooooo
  238. Symbol Beschreibung C
  239. +++++++++++++++++++++++++++++++++++++++++
  240. `^Typ` Zeiger auf Typ `Typ*`
  241. `^var` Zeiger auf var `&var`
  242. `var^` Dereference var `var*`
  243. `nil` Nullpointer `NULL`
  244. `free(p)` Lösche Zeiger p `free(p)`
  245. `inc(i)` Inkrementiere i `i++`
  246. ooooooooooooooooooooooooooooooooooooooooo
  247.  
  248. Bei Listen: {\language[Pascal]}
  249.  
  250. type
  251. ListPointer = ^ListElement;
  252. ListElement = record
  253. cnt: Integer;
  254. next: ListPointer;
  255. end;
  256.  
  257. procedure append(to: ListPointer; val: Integer);
  258. var
  259. current: ListPointer;
  260. begin
  261. current := to;
  262. while current^.next <> nil do begin
  263. current .= current^.next;
  264. end;
  265. new(current^.next);
  266. current^.next^.next := nil;
  267. current^.next^.next := val;
  268. end;
  269.  
  270. ----------------------------------------------[ Objektorientierung in Delphi ]--
  271.  
  272. Übersicht
  273. ---------
  274.  
  275. Projekte
  276. ganze Programme
  277. Units
  278. Thematisch zusammenhängnder Code
  279. Typen
  280. eigene Datentypen
  281.  
  282. Records
  283. Datensätze
  284. Umbenannte und Wertebereichsändernde Datentypen
  285. Klassen
  286. In Delphi sind Klassen Datentypen
  287.  
  288. Eine Unit
  289. ---------
  290.  
  291. Units ähneln Packages, sind aber nur eine Datei. In Delphi darf der Name einer
  292. Unit nicht der einer Klasse oder Variable sein. Leider unterscheidet Delphi
  293. nicht zwischen Groß- und Kleinschreibung => in Delphi verwenden Viele Präfixe.
  294. Alternativ kann man auch verallgemeinernde Namen verwenden, etwa
  295.  
  296. oooooooooooooooooooooooooooooooooooooo
  297. Beispiel Beschreibung
  298. ++++++++++++++++++++++++++++++++++++++
  299. Fahrzeug.pas Name der Unit
  300. Auto Klassenname
  301. autoObj oder anAuto Instanz
  302. oooooooooooooooooooooooooooooooooooooo
  303.  
  304. Aufbau
  305.  
  306. unit Name;
  307.  
  308. interface (* steht immer da *)
  309.  
  310. uses ...; (* Import v Include, etc. *)
  311. const ...; (* Konstatnen *)
  312. type
  313. ... (* Klassendeklarationen etc. *)
  314.  
  315. implementation
  316.  
  317. (* Methodeninhalte. *)
  318.  
  319. end. (* Hier und nur hier: '.' *)
  320.  
  321. Hinter Funktionsnamen: `...; overload;` bei anderer Methode mit gleichem Namen.
  322. Objekten kann `nil` zugewiesen werden.
  323.  
  324. ----------------------------------------------------------------[ Datentypen ]--
  325.  
  326. Records
  327.  
  328. type Status = record (* Delphi Programmierer *)
  329. combinations: Integer; (* verwenden gerne Prefixe: *)
  330. found: Integer; (* TStatus oder tStatus *)
  331. msg: String;
  332. end; (* Records werden nicht initialisiet. *)
  333.  
  334. function createStatus: Status;
  335. var
  336. ret: Status;
  337. begin
  338. ret.combinations := 0;
  339. ret.found := 0;
  340. ret.msg := 'Not started.';
  341. result := ret;
  342. end;
  343.  
  344. Klassen
  345.  
  346. type Car = class (* alt: class(Transporter) *)
  347. public (* nichts. published; *)
  348. ... (* außerdem: protected *)
  349. private (* Variablen in der *)
  350. ... (* Deklaration wie in der *)
  351. end; (* Implementation *)
  352.  
  353. Konstruktoren und Destruktoren
  354.  
  355. constructor create; ... (* self <=> this *)
  356.  
  357. constructor Car.create;
  358. begin
  359. ...
  360. end;
  361.  
  362. destructor destroy; overrride; ...
  363.  
  364. destructor Car.destroy;
  365. begin
  366. inherited destroy; (* super.destroy() *)
  367. end;
  368.  
  369. ----------------------------------------[ Die UML: Unified Modeling Language ]--
  370.  
  371. Grundsätzliches
  372.  
  373. ............... - private
  374. . Klassenname . + public
  375. ............... ++ published
  376. . Felder . # protected
  377. ............... ! procedure
  378. . Methoden . constructor
  379. ............... destructor
  380. ? function
  381.  
  382. .............................................
  383. . Tank .
  384. .............................................
  385. . - size: Integer; .
  386. . - round: Boolean; .
  387. . - cnt: String; .
  388. . - level: Integer; .
  389. .............................................
  390. . + ! create(size: Integer, round: Boolean) .
  391. . + ! add(liters: Integer) .
  392. . + ! remove(liters: Integer) .
  393. . + ? getSize(): Integer .
  394. . + ? isRound(): Boolean .
  395. . + ? getLevel(): Integer .
  396. . + ! setCnt(cnt: String) .
  397. . + ! destroy() .
  398. .............................................
  399.  
  400. Beziehungen
  401.  
  402. .......... kennt ...........
  403. . Buffer .------------->. Element .
  404. .......... ...........
  405. . (etc) . . (etc) .
  406. .......... ...........
  407. . (etc) . . (etc) .
  408. .......... ...........
  409. ^ |
  410. | ist (erbt von) |
  411. ............... |
  412. . List Buffer . |
  413. ...............<>-----------+ hat (e.g. Feld tes Types etc.)
  414. . (etc) .
  415. ...............
  416. . (etc) .
  417. ...............
  418.  
  419. Kennt braucht man fast nie; meistens hat man "`hat"' oder "`ist"'.
  420.  
  421. --------------------------------------------------------------[ Binäre Bäume ]--
  422.  
  423. Elemente werden so angehängt, dass auf der linken Seite eines Kontens nur
  424. kleinere Element und rechts nur größere Elemente vorkommen.
  425.  
  426. Niveau 0 10
  427. / \
  428. Niveau 1 4 18
  429. / \ / \
  430. Niveau 2 2 3 11 20
  431. / /
  432. Niveau 3 1 19
  433.  
  434. binär := max. 2 Kindelemente/Knoten
  435. Tiefe := größtes Niveau ("`Anzahl der Knoten zum tiefsten Element"')
  436. Konten := Element mit Daten und 1 oder mehr Kindelementen
  437. Wurzel := Oberster Knoten
  438. Kanten := Verbinden Knoten
  439. Blatt := Knoten ohne Kindelemente
  440. Traversierung := Durchlaufen
  441. Teilbaum := Baum, dessen Wurzel Konten eines anderen Baumes ist.
  442.  
  443. Traversierung
  444. ooooooooooooooooooooooooooooooooooooooo
  445. Name Art Beschreibung
  446. +++++++++++++++++++++++++++++++++++++++
  447. Preorder WLR Wurzel Links Rechts
  448. Inorder LWR Links Wurzel Rechts
  449. Postorder LRW Links Rechts Wurzel
  450. ooooooooooooooooooooooooooooooooooooooo
  451.  
  452. Löschen im binären Baum und andere wichtige Operationen werden durch das
  453. folgende Codestück erklärt.
  454.  
  455. procedure TBinBaum.anhaengen(amKnoten, neuerKnoten: TKnoten); (* ... *)
  456.  
  457. function TBinBaum.loeschen(daten: String): Boolean;
  458. begin
  459. if wurzel = nil then begin
  460. result := false;
  461. end else if wurzel.daten = daten then begin
  462. deleteRoot;
  463. result := true;
  464. end else begin;
  465. result := deleteElementFrom(daten, wurzel);
  466. end;
  467. end;
  468.  
  469. procedure TBinBaum.deleteRoot; (* ... *)
  470.  
  471. function TBinBaum.deleteElementFrom(element: String; node: TKnoten):
  472. Boolean;
  473. var
  474. newNode: TKnoten;
  475. begin
  476. result := false;
  477. if node <> nil then begin
  478. if node.toLinks <> nil then begin
  479. if node.toLinks.daten = element then begin
  480. newNode := node.toLinks.toLinks;
  481. if newNode = nil then begin
  482. newNode :=
  483. node.toLinks.toRechts;
  484. end else begin
  485. anhaengen(newNode,
  486. node.toLinks.toRechts);
  487. end;
  488. deleteOnly(node.toLinks);
  489. node.toLinks := newNode;
  490. result := true;
  491. end;
  492. end;
  493. if (result = false) and (node.toRechts <> nil)
  494. then begin
  495. if node.toRechts.daten = element then begin
  496. newNode := node.toRechts.toLinks;
  497. if newNode = nil then begin
  498. newNode :=
  499. node.toRechts.toRechts;
  500. end else begin
  501. anhaengen(newNode,
  502. node.toRechts.
  503. toRechts);
  504. end;
  505. deleteOnly(node.toRechts);
  506. node.toRechts := newNode;
  507. result := true;
  508. end;
  509. end;
  510. if result = false then begin
  511. result := deleteElementFrom(element,
  512. node.toLinks);
  513. end;
  514. if result = false then begin
  515. result := deleteElementFrom(element,
  516. node.toRechts);
  517. end;
  518. end;
  519. end;
  520.  
  521. procedure TBinBaum.deleteOnly(node: TKnoten);
  522. begin
  523. node.toLinks := nil;
  524. node.toRechts := nil;
  525. node.destroy;
  526. end;
  527.  
  528. ----------------------------------------------------------------------[ Heap ]--
  529.  
  530. Ein Heap ist ein fast vollständiger binärer Baum, bei dem unter einem Knoten
  531. keine größeren Knoten vorkommen
  532.  
  533. 5
  534. / \
  535. 4 1
  536. / \
  537. 3 2
  538.  
  539. Baum im Array
  540. -------------
  541.  
  542. Der Baum kann "`Preorder"' im Array gespeichert werden.
  543.  
  544. Index 1 2 3 4 5
  545. Wert 5 4 1 3 2
  546.  
  547. Die Wurzel zu einem Element in einem Solchen Array liegt bei `i div 2`.
  548.  
  549. Einfügen
  550. --------
  551.  
  552. Zum Einfügen kommt ein neues Element ans Ende des Arrays
  553.  
  554. Index 1 2 3 4 5 6 5
  555. Wert 5 4 1 3 2 8 / \
  556. 4 1
  557. / \ /
  558. 3 2 8
  559.  
  560. Dann wird es solange mit der Wurzel vertauscht, bis es größer ist. Damit ist der
  561. Heap wieder korrekt.
  562.  
  563. 5 8
  564. / .\ / \
  565. 4 .1 -> 4 5
  566. / \ /. / \ /
  567. 3 2 8. 3 2 1
  568.  
  569. ---------------------------------------------------[ Prioritätswarteschlange ]--
  570.  
  571. Kehrt man die Vergleiche eines Heaps um, so kann man Elemente priorisiert
  572. anordnen. Kleine Zahl <=> große Priorität.
  573.  
  574. 1 Zum Einfügen geht man vor, wie beim normalen Einfügen, nur
  575. / \ dass der Vergleich nicht "`größer"', sondern "`kleiner"'
  576. 2 4 ist.
  577. / \ /
  578. 3 5 (8)
  579.  
  580. Zum Entnehmen entnimmt man die Wurzel und stellt das letzte Element an ihre
  581. Stelle. Dann tauscht man rekursiv mit dem kleinsten Kindelement, bis beide
  582. Kindelemente größer dem neuen Element sind
  583.  
  584. 1 .8 2
  585. / \ ./ \ / \
  586. 2 4 -> .2 4 -> 3 4
  587. / \ / ./ \ / \
  588. 3 5 8 3 5 8 5
  589.  
  590. Dadurch ist wieder ein gültiger Heap entstanden. Der Vorteil des Heaps ist, dass
  591. alles mit garantiert O(n log n) läuft.
  592.  
  593. -----------------------------------------------------------------[ Der Stack ]--
  594.  
  595. Der Stack ist auch als "`Keller"' bekannt.
  596.  
  597. LIFO := Last in, first out
  598.  
  599. Ein Stack kennt nur wenige Oparationen
  600.  
  601. push
  602. Legt ein Element auf den Stack
  603. pop
  604. Entnimmt das oberste Element
  605. head oder top
  606. Gibt das oberste Element zurück, ohne es zu löschen
  607. isEmpty
  608. Gibt `true` zurück, falls der Stack leer ist
  609. clear
  610. Löscht alle Elemente aus dem Stack
  611.  
  612. Üblicherweise werden Stacks mit Zeigern ähnlich einer einfach verketteten Liste
  613. im Speicher abgebildet. Vgl: `/q1/stack/Lists.pas`.
  614.  
  615. -------------------------------------------------------[ Die Türme von Hanoi ]--
  616.  
  617. T(n) = 2^n - 1
  618.  
  619. # # #
  620. # # #
  621. -#- # #
  622. --#-- # #
  623. ---#--- # #
  624. ######### ######### #########
  625.  
  626. Der "`sortierte"' Stapel soll auf einen anderen Stack. Es dürfen nie kleinere
  627. Elemente unter größeren liegen. Nur Stackoperationen sind gestattet.
  628.  
  629. ---------------------------------------------------------------[ Datenbanken ]--
  630.  
  631. Wir behandeln in der Schule nur relationale Datenbanken.
  632. RDBMS := Relationales DatenBank Management System
  633.  
  634. --------------------------------------------------------------[ ER-Diagramme ]--
  635.  
  636. Mit ER-Diagrammen (ER := Entity Relationship), sollen sich relationale
  637. Datenbankmodelle entwickeln lassen.
  638.  
  639. ER-"`Syntax''
  640. -------------
  641.  
  642. .......... Entity
  643. . Entity .
  644. .......... Wird später eine Tabelle
  645.  
  646.  
  647. ____ Attribut
  648. / \
  649. / Attr \ Wird später eine Spalte, Schlüssel werden unterstrichen.
  650. \ ibut / In der "`Grafik"' schlecht zu erkennen:
  651. \____/ Attribute werden eingekreist.
  652.  
  653.  
  654. /====\ Mehrfachattribut
  655. // \\
  656. // Attr \\ Später `Array`, mehrere Spalten oder getrennte Tabelle.
  657. \\ ibut //
  658. \\ // Mehrfachattribute werden doppelt eingekreist.
  659. \====/
  660.  
  661.  
  662. --------- Verbindung/Linie
  663.  
  664.  
  665. /\ Beziehung
  666. / \
  667. /Bezi\ verbinden Entities und können selbst Attribute haben.
  668. \hung/ Spezielle "`is-A"' Beziehung kennzeichnet "`Vererbung"'.
  669. \ / Beziehungen können mehr als zwei Entities verbinden und
  670. \/ Entities können über mehrere Bezieungen verbunden sein.
  671.  
  672. ER-Beziehungen "`Kardinalitäten"'
  673. ---------------------------------
  674.  
  675. Eine Beziehung kann eine von drei Komplexitäten haben.
  676.  
  677. 1:1
  678. Eineindeutige Zuordnung (Bijektion).
  679. 1:n
  680. Einem Entity werden mehrere Entities zugeordnet. Umgekehrt kann jedem
  681. zugeordneten Entity nur ein Entity zugeordnet sein.
  682. n:m
  683. Dem ersten Entity werden mehrere zweite Entities zugeordnet, aber auch
  684. umgekehrt können einem zweiten Entity mehrere erste zugeordnet werden.
  685.  
  686. Die Wahl der Komplexität wird immer begründet, denn sie ist mitunter
  687. interpretationsabhängig.
  688.  
  689. Die Umwandlung von Beziehungen in Tabellen ist nicht immer einfach. Wenn es sich
  690. um eine Beziehung zwischen zwei Entities handelt, werden diese üblicherweise
  691. beide ein gleiches Attribut haben, um die Beziehung herzustellen. Häufig ist
  692. dieses Attribut noch nicht im ER-Diagramm ersichtlich. Bei Beziehungen mit
  693. zusätzlichen Attributen können diese in einer der beteiligten Tabellen als
  694. Spalte hinzugefügt oder in eine eigene Tabelle ausgelagert werden. Ziel sollte
  695. es dabei sein, möglichst wenige Tabellen bei geringer Redundanz ainzusetzen.
  696.  
  697. Optionalitäten
  698. --------------
  699.  
  700. /\
  701. ........... n / \ 1 ........
  702. . Patient .------/hat \---------. Arzt .
  703. ........... muss \ / kann ........
  704. \ /
  705. \/
  706.  
  707. Dies ist ein Auszug aus einer Aufgabe. Diese "`hat Beziehung"' ist vom Patienten
  708. als "`hat als Hausarzt"' zu lesen.
  709.  
  710. Jeder Patient muss daher einen Hausarzt haben, ein Arzt kann jedoch Hausarzt von
  711. mehreren Patienten sein oder gar keine Patienten haben.
  712.  
  713. ----------------------------------------------------------------[ Relationen ]--
  714.  
  715. In der Theorie zur relationalen Datenbank heißen Tabellen auch Relationen.
  716.  
  717. Kompakte Beschreibung von Tabellen
  718. * `Tabelle(Attribut, ...)`
  719. * Primärschlüssel unterstreichen
  720. * Zeilen können auch als Tupel dargestellt werden
  721.  
  722. Die Relationenschreibweise hat drei "`Datentypen"'
  723. 1. Primärschlussel (Attribut wird unterstrichen).
  724. 2. Fremdschlüssel (Attribut bekommt Pfeil nach oben).
  725. 3. Werte (Attribut bekommt keine zusätzlichen Zeichen).
  726.  
  727. Beispiel: `Programm(_ID_, Datei, Größe, Typ, Bild^)`
  728.  
  729. ---------------------------------------------------------[ Relationenalgebra ]--
  730.  
  731. "`MQL -- Mathe Query Language''
  732.  
  733. Schnittmenge
  734. Gleiche Elemente zweier Tabellen (kommutativ).
  735. Vereinigung `U`
  736. Alle Elemente zweier Tabellen (kommutativ). SQL: `UNION`
  737. Differenz `\`
  738. Erste Tabelle "`ohne"' zweite Tabelle (nicht kommutativ).
  739. Produkt {$\times$}
  740. Kartesisches Produkt: Alle Kombinationen (kommutativ).
  741. Selektion {$\sigma_\textrm{Bedingung}(\textrm{Von})$}
  742. Selektiert aus der Tabelle "`Von"' alle Zeilen, die die Bedingung
  743. erfüllen. SQL: `SELECT * FROM Von WHERE Bedingung`
  744. Projektion {$\pi_\textrm{Attribute}(\textrm{Von})$}
  745. Selektiert Spalten aus "`Von"'. SQL: `SELECT Attribute FROM Von`
  746. Join `|><|`
  747. Verbindet zwei Tabellen über ein gemeinsames Attribut.
  748. SQL: `SELECT ... FROM ... INNER JOIN ... ON ...`
  749.  
  750. Bildung des Joins
  751. 1. Kartesisches Produkt
  752. 2. Nicht übereinstimmende Attribute streichen
  753. 3. Überflüssige Spalten löschen
  754.  
  755. P `|><|` Q
  756. ----------
  757.  
  758. {$\pi_\textrm{Spalten}(\sigma_\textrm{Vergleich}(\textrm{P}\times\textrm{Q}))$}
  759.  
  760. "`Vergleich"'
  761. stellt gleiche Vergleichselemente Sicher
  762. Projektion "`Spalten"'
  763. Wählt die Vereinigungsmenge der Tabellenspalten.
  764.  
  765. Vergleich: SQL und Relationenalgebra
  766. ------------------------------------
  767.  
  768. SQL beherrscht die praktische Zusammenfügung von Selektion, Projektion und Join
  769. in einem. Weiterhin ist SQL durch das `JOIN ... ON ...` eindeutiger und kommt
  770. auch mit Tabellen mit mehreren gleichen Spaltennamen zurecht. Die von den
  771. Mengen bekannten Operationen sind hingegen schwieriger durchzuführen und die
  772. Syntax ist etwas komplizierter.
  773.  
  774. Dafür funktioniert die Relationenalgebra ähnlich MongoDB Pipelines: Man schaltet
  775. Filter hintereinandser, was bei bestimmten Abfragen wesentlich eingängiger ist,
  776. als die passende SQL Syntax.
  777.  
  778. ----------------------------------------------[ Normalisierung und Anomalien ]--
  779.  
  780. Normalisierung ist eine Art "`Brecheisen"' zum Erzeugen von guten Tabellen,
  781. falls man schlechte hat. Damit kann man auch aus ER-Diagrammen mit allen
  782. Kardinalitäten und Optionalitäten optimierte Tabellen machen, wodurch auch
  783. ER-Diagramme für ernsthafte Datenbankentwicklung taugen.
  784.  
  785. Als Beispiel soll folgende, dumm gemachte, Tabelle dienen:
  786. `Page(_File_, Title, Keywords, ParentFile^)`
  787.  
  788. Anomalien
  789. ---------
  790.  
  791. Einfüge-
  792. Nicht alle Daten, die einfefügt werden müssten, sind schon bekannt.
  793. Lösch-
  794. Bestimmte Einträge können nicht gelöscht werden, ohne dass
  795. Behaltenswerte Informationen verloren gehen.
  796. Änderungs-
  797. Einträge lassen sich nicht ändern, weil sie in anderen Tabellen als
  798. Fremdschlüssel auftauchen. Alternativ: Die Änderung eines Eintrags führt
  799. zu inkonsistenzen.
  800. Nullwerte
  801. gelten in RDBMS auch als Quellen für Anomalien und werden bei
  802. Aggregatfunktionen (`SUM`, `AVG`, `COUNT`, ...) und `SELECT`-Anfragen,
  803. die für eine Spalte mit Nullwerden Bedingungen definieren nicht
  804. dazugezählt beziehungsweise berücksichtigt.
  805.  
  806. Bei der Beispieltabelle gibt es Anomalien.
  807. 1. Änderungsanomalie: `File` kann unter Umständen nicht umbenannt werden.
  808. 2. Nullwerte: `ParentFile` kann `NULL` (für `/`) sein.
  809.  
  810. Erste Normalform
  811. ----------------
  812.  
  813. Eine Relation ist in der ersten Normalform, wenn keine Mehrfachattribute
  814. vorkommen.
  815.  
  816. Im Beispiel müssen entweder mehrere Tabellen entstehen, oder man
  817. legt fest, dass `Keywords` kein Array ist, sondern der Eintrag für jedes
  818. geänderte Keyword eben wiederholt wird. Damit wird allerdings der
  819. Primärschlüssel ungültig und muss ausgeweitet werden.
  820.  
  821. Page(_File_, Title, _Keyword_, ParentFile^)
  822.  
  823.  
  824. Zweite Normalform
  825. -----------------
  826.  
  827. Die zweite Normalform bedingt die erste Normalform und fordert, dass kein
  828. nicht-Schlüssel Attribut funktional abhängig von Teilschlüsseln ist.
  829.  
  830. Im Beispiel sind nach dem Umformen in die erste Normalform, `File`, `Title` und
  831. `ParentFile` funktional abhängig, weshalb `Keyword` in eine getrennte Tabelle
  832. ausgelagert werden muss.
  833.  
  834. Page(_File_, Title, ParentFile^)
  835. Keyword(_File_^, _Keyword_)
  836.  
  837. Dritte Normalform
  838. -----------------
  839.  
  840. Die dritte Normalform bedingt die zweite Normalform und fordert, dass keine
  841. funktionalen Abhängigkeiten zwischen nicht-Schlüsselattributen bestehen.
  842.  
  843. Meistens kann man auch sagen: Es dürfen keine Redundanzen vorkommen.
  844.  
  845. Nachdem man die zweite Normalform erstellt hat, wie oben angegeben, befindet
  846. sich die Tabelle auch in der dritten Normalform.
  847.  
  848. Problem
  849. -------
  850.  
  851. Die Datenbank ist jetzt in der dritten Normalform, aber immernoch nicht ideal:
  852. Dateien lassen sich nicht einfach umbenennen, weil sie als Schlüsselattribut
  853. verwendet werden. In der Praxis würde man etwa folgende Struktur entwickeln:
  854.  
  855. Page(_ID_, File, Title, ParentFile^)
  856. Keyword(_Page_^, _Keyword_)
  857.  
  858. Damit ließen sich Dateien problemlos umbenennen.
  859.  
  860. -----------------------------------------[ Die Structured Query Language SQL ]--
  861.  
  862. Data Definition Language
  863. * `CREATE TABLE table ( attribute SERIAL, ... );`
  864. * `DROP TABLE table;`
  865. Data Control Language
  866. * `CREATE ROLE testuser WITH PASSWORD 'testwort';`
  867. * `GRANT testuser ALL PRIVILEGES ON db;`
  868. Data Manipulation Language
  869. * `INSERT INTO table VALUES (...);`
  870. * `INSERT INTO table (attributes) VALUES (...);`
  871. * `UPDATE table SET expression WHERE condition;`
  872. * `SELECT * FROM table;`
  873.  
  874. Für unsere Informatik ist nur die DML relevant. Dabei beschäftigen wir uns
  875. insbesondere mit `SELECT` zur Abfrage.
  876.  
  877. ------------------------------------------------------[ SELECT und Ähnliches ]--
  878.  
  879. Aufbau
  880.  
  881. DELETE FROM tables WHERE cond
  882. SELECT data FROM tables WHERE cond mod
  883. SELECT DISTINCT ~ -- keine doppelten Zeilen ausgeben
  884.  
  885. `data`
  886. * Spaltennamen: `s1, s2`
  887. * Umbenennen: `s1 AS spalte1`
  888. * Ausdrücke: `s1 * 4 AS fs1`
  889. * Aggregatfunktionen: `SUM`, `AVG`, `MIN`, `MAX`, `COUNT`
  890. `tables`
  891. Tabellenliste (umbenennen mit `AS`)
  892. `cond`
  893. Join mit `SELECT T1.X, T2.X FROM T1, T2 WHERE T1.T2ID = T2.ID;`
  894. oder `SELECT T1.X, T2.X FROM T1 INNER JOIN T2 ON T1.T2ID = T2.ID;`
  895. `mod`
  896. * `GROUP BY` wendet Aggregatfunktionen auf Gruppen an.
  897. * `HAVING` ist `WHERE` für _Ergebnisse_ von `GROUP BY`
  898. * `LIMIT n, m` Gibt Ergebnisse e [n;m] aus.
  899. * `ORDER BY s` Sortiert die Ausgabe `ASC` (1, 2, 3, ...) oder
  900. `DESC` (..., 3, 2, 1).
  901.  
  902. Subqueries
  903.  
  904. SELECT U.Name,
  905. COUNT(SELECT ID FROM iTrace WHERE iTrace.Name = U.Name) AS iC
  906. FROM Users AS U;
  907.  
  908. Operatoren
  909. ----------
  910.  
  911. `=` und `<>`
  912. ist gleich und ungleich
  913. `LIKE`
  914. Ungefär, Wildchards BRE `*`, `?`, spezielle `%`.
  915. `>` und `>=`
  916. Echt größer und größer gleich
  917. `<` und `<=`
  918. Echt kleiner und kleiner gleich
  919. `BETWEEN a AND b`
  920. Zwischen a und b (beide inclusive)
  921. `IN(a,b,c)`
  922. Element der Menge, funktioniert auch mit Subquery.
  923. `AND` und `OR`
  924. Logisches und beziehungsweise oder.
  925. `NOT`
  926. Logisches nicht.
  927. `IS NULL`
  928. Testen auf Nullelement.
  929.  
  930. --------------------------------------------[ Diverses zum Thema Datenbanken ]--
  931.  
  932. Wie man Datenbanken entwickeln sollte
  933. 1. Planen, was man speichern, ändern, löschen will
  934. 2. Relationenmodell mit Datentypen entwickeln
  935. 3. Gegen Normalform testen, aber nicht erzwingen
  936. 4. `CREATE` Anweisungen erstellen
  937. 5. Setup schreiben
  938.  
  939. `mysql_select_db()` <=> `OPEN 'db';`
  940.  
  941. MySQL
  942. * String: `'Str'`
  943. * Tabelle: `\`tab\``
  944. * Datum `YYYY-MM-DD` (`Y-m-d`)
  945.  
  946. --------------------------------------[ Fragen der Theorethischen Informatik ]--
  947.  
  948. Was kann ein Computer (können), was nicht?
  949. Limitationen: Geschwindigkeit, Beziehungsprobleme
  950. Halteproblem
  951. Man kann kein Programm schreiben, dass die Terminierung eines Programmes
  952. beweist.
  953. NP-vollständige Probleme
  954. Grenze der perfekt lösbaren Probleme
  955. Was ist Sprache?
  956. Wie ist Sprache für den Computer zu definieren. Parser und Compiler.
  957. Entscheideproblem
  958. Beweis von Aussagen
  959. Goldbach-Vermutung
  960. Jede gerade Zahl > 2 kann als Summe zweier Primzahlen dargestellt werden
  961. Wundersame Zahlen
  962. a(n+1) = 3a(n) + 1 für ungerades n und a(n)/2 für gerades n.
  963. Endet bei Wiederholung auf 1? Das Problem ist nicht berechenbar.
  964.  
  965. Im Folgenden stehen Klammern `()` oft für Kreise und `[]` für Rechtecke
  966.  
  967. ------------------------------------------------------------------[ Sprachen ]--
  968.  
  969. Sprache L := Menge aller gültigen Wörter
  970. X := Alphabet, X* := Alle Kombinationen (Mengenvereinigung L hoch i mit i -> oo)
  971. S := Startsymbol
  972. Vt := Menge der Terminale
  973. Vn := Menge der Nichtterminale
  974. P := Menge der Regeln "`Produktionen"'
  975.  
  976. ---------------------------------------------------------------[ Grammatiken ]--
  977.  
  978. X oder Vt muss angegeben werden. Eine Grammatik aller 0-1-Wörter, die auf 0
  979. enden (`(0|1)*0`):
  980.  
  981. Vt = { 0; 1 }
  982. S -> 0S | 1S | 0 <=> S -> 0S <=> P = { S -> 0S; S -> 1S; S -> 0 }
  983. S -> 1S
  984. S -> 0
  985.  
  986. Ableitung des Wortes `011010`
  987.  
  988. S -> 0S -> 01S -> 011S -> 0110S -> 01101S -> 011010
  989.  
  990. Ableitungsbaum
  991.  
  992. S
  993. / \
  994. 0 S
  995. / \
  996. 1 S
  997. / \
  998. 1 S
  999. / \
  1000. 0 S
  1001. / \
  1002. 1 S
  1003. /
  1004. 0
  1005.  
  1006. Syntaxdiagramme (rekursiv vs. iterativ)
  1007.  
  1008. S +--------------------------------+
  1009. -->+--( 0 )--[ S ]--+ S v |
  1010. | | ~ -------->( 0 )----->( 1 )--->( 0 )----->
  1011. +--( 1 )--[ S ]--+ ~ | ^ | ^
  1012. | | +---------+ +--------+
  1013. +--( 0 )---------+-->
  1014.  
  1015. ----------------------------------------[ Chomsky Hierarchie der Grammatiken ]--
  1016.  
  1017. Sparchen werden in die Hierarchie eingeordnet, indem man sie mit dem
  1018. höchstmöglichen Grammatiktyp beschreibt.
  1019.  
  1020. ......................................................................
  1021. . Typ 0 allgemein x -> y (x != e) .
  1022. . ................................................................ .
  1023. . . Typ 1 kontextsensitiv x A y -> x z y (z != e) . .
  1024. . . .......................................................... . .
  1025. . . . Typ 2 kontextfrei A -> x . . .
  1026. . . . .................................................... . . .
  1027. . . . . Typ 3 regulär A -> aB | e (etwa A -> a | aB) . . . .
  1028. . . . .................................................... . . .
  1029. . . . . . .
  1030. . . .......................................................... . .
  1031. . . . .
  1032. . ................................................................ .
  1033. . .
  1034. ......................................................................
  1035.  
  1036. x, y, z := beliebige Folgen von A, B, a, b; e := leeres Wort (Epsilon)
  1037. a, b := beliebiges Terminal; A, B := beliebiges Nichtterminal
  1038.  
  1039. ----------------------------------[ DEA: Deterministischer Endlicher Automat ]--
  1040.  
  1041. Startzustand
  1042. z{$_0$}, s{$_0$}, `->(S)`
  1043. Endzustand
  1044. `((Z))` -- doppelt eingekreister Zustand
  1045. Zustand
  1046. `(C)`
  1047. Übergang
  1048. `(E) -x-> (F)`, wobei `x` über den Pfeil geschrieben wird.
  1049. `x` bezeichnet das gelesene Zeichen.
  1050. Schleife
  1051. `(E)>x` (man zeichnet eine Schleife
  1052.  
  1053. Darstellungsmöglichkeiten
  1054.  
  1055. ........................................................................
  1056. . .
  1057. . _____ Zustandstabelle Ableitung von .
  1058. . / \ 0 oooooooooooooooooooooooooo 011010: .
  1059. . 0 | | Momentan Eingabe Neu .
  1060. . ->(S)----->((E))<--/ ++++++++++++++++++++++++++ S 0 E .
  1061. . /^^ | S 1 S E 1 S .
  1062. . 1 \/\________/1 S 0 _E_ S 1 S .
  1063. . _E_ 0 _E_ S 0 E .
  1064. . _E_ 1 _S_ E 1 S .
  1065. . oooooooooooooooooooooooooo S 0 _E_ .
  1066. . .
  1067. . Endzustände werden in den Tabellen unterstrichen. .
  1068. ........................................................................
  1069.  
  1070. -----------------------------[ NEA: Nichtdeterministischer Endlicher Automat ]--
  1071.  
  1072. Automat, bei dem von einem Zustand mehrere Wege mit dem gleichen Zeichen
  1073. abgehen.
  1074.  
  1075. .............................
  1076. . 0 1 .
  1077. . (S)------->((E))--->(F) .
  1078. . /^ /^ Fehler .
  1079. . \/ 0,1 \/ 0 .
  1080. .............................
  1081.  
  1082. -----------------------------------------------------------[ Vom NEA zum DEA ]--
  1083.  
  1084. Die beiden Automatentypen sind gleichmächtig. Mit der Potzenmengenmethode kommt
  1085. man vom einen zum Anderen. Dazu werden "`Uneindeutige"' Wege zusammen
  1086. betrachtet. Die Tabelle gibt dann den neuen Automaten an.
  1087.  
  1088. ooooooooooooooooooooooooooo
  1089. X 0 1
  1090. +++++++++++++++++++++++++++
  1091. S (_E,S_) S
  1092. (_E,S_) (_E,S_) (S,F)
  1093. (S,F) (_E,S_) S
  1094. ooooooooooooooooooooooooooo
  1095.  
  1096. Alle Zustände, die einen "`ehemaligen"' Endzustand enthalten, werden Endzustände
  1097.  
  1098. ............................. Der entstehende Automat ist nicht optimal
  1099. . /\ 0 . im Sinne möglichst weniger Zustände.
  1100. . 0 \v .
  1101. . --->(z0)------->((z1)) .
  1102. . /^ ^ | | .
  1103. . 1 \/ \______ 1| / 0 .
  1104. . 1 \ v / .
  1105. . (z2) .
  1106. .............................
  1107.  
  1108. -----------------------[ Reguläre Ausdrücke in der theorethischen Informatik ]--
  1109.  
  1110. Syntax
  1111. * `|` := ODER
  1112. * `(` und `)` := Klammerung
  1113. * {$\epsilon$} := Leeres Wort
  1114. * `*` := 0 bis n-fache Widerholung
  1115. * Außerdem werden `?` und `+` laut Glossar erlaubt. TODO ERGÄNZEN
  1116. Konkatenation
  1117. Sprachen über selbem Alphabet werden über kartesisches Produkt verbunden
  1118. reguläre Sprache L(r)
  1119. Alle Wörter, die Ausdruck "`r"' matcht.
  1120.  
  1121. ----------------------[ Beispiel: Automat erkennt durch drei Teilbare Zahlen ]--
  1122.  
  1123. Alphabet A := \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}
  1124. REM: Arithmetik modulo 3.
  1125.  
  1126. .........................................
  1127. . .
  1128. . 0,3,6,9 0,3,6,9 0,3,6,9 .
  1129. . /\ /\ /\ .
  1130. . \v 1,4,7 \v 1,4,7 \v .
  1131. . (s0)--------->(r1)--------->(r2) .
  1132. . ^|^___________/ ^___________/^ \ .
  1133. . || 2,5,8 2,5,8 | \ .
  1134. . |\____________________________/ | .
  1135. . | 2,5,8 / .
  1136. . \_______________________________/ .
  1137. . 1,4,7 .
  1138. . .
  1139. .........................................
  1140.  
  1141. -----------------------------------------------------------[ Kellerautomaten ]--
  1142.  
  1143. Definition
  1144. * Endlicher Automat + Stack
  1145. * Stack leer <=> Wort aktzeptiert
  1146. * gelesenes Zeichen, oberes Kellerzeichen,
  1147. Kelleroperation (`push` Zeichen, `pop`, `nop`)
  1148.  
  1149. Schreibweise
  1150. 1. Zustand Eingabe Stack.top -> Operation Zustand
  1151. 2. Zustandsdiagramm
  1152. 3. Tabelle
  1153.  
  1154. ...................... Tabellarische Darstelung des Automaten
  1155. . --->(z0) . ooooooooooooooooooooooooooooooooooooooooooooo
  1156. . /^ a a push a . Zustand Eingabe Top Operation Zustand
  1157. . \/ a # push a . +++++++++++++++++++++++++++++++++++++++++++++
  1158. . b a pop . z0 a a push a z0
  1159. . . z0 a # push a z0
  1160. . . z0 b a pop z0
  1161. ...................... ooooooooooooooooooooooooooooooooooooooooooooo
  1162.  
  1163. Alle anderen Eingaben führen zum Fehlerzustand.
  1164.  
  1165. Anwendung
  1166. * Klammerausdrücke
  1167. * einige kontextfreie Grammatiken
  1168. * Mit Trennzeichen getrennte Palindrome
  1169.  
  1170. -----------------------------------------------------------[ Turingmaschinen ]--
  1171.  
  1172. Definition
  1173. * Kann alles Berechenbare brechnen
  1174. * Zustand BandIN -> BandOut Bewegung Zustand
  1175. * Bewegung `L` (nach links), `R` (nach rechts), `N` (nop), `H` (beenden)
  1176.  
  1177. Schreibweise: Turingprogramm, Zustandsdiagramm oder Tabelle
  1178.  
  1179. 1##R1 Dieses Programm ersetzt auf einem Band mit 1en und 0en alle
  1180. 10#R2 0en durch das Leerzeichen `#`
  1181. 111R2
  1182. 2##N2 H
  1183. 211R2
  1184. 10#R2
  1185.  
  1186. ------------------------------------------------------------[ Fleißige Biber ]--
  1187.  
  1188. * Turingmaschine mit n Zuständen und dem Alphabet \{`1`, `#`\} soll möglichst
  1189. viele Einsen schreiben und dann terminieren
  1190. * Die Maximale Anzahl möglicher Einsen für einen Biber mit n Zuständen ist
  1191. nicht berechenbar.
  1192. * Die Anzahl der Einsen in Abhängigkeit von den Zuständen steigt schneller als
  1193. exponentiell.
  1194.  
  1195. 2 Zustände, 4 Einsen, 4 Schritte, optimal
  1196.  
  1197. 0#1L1
  1198. 011R1
  1199. 1#1R0
  1200. 111H1
  1201.  
  1202. 3 Zustände, 6 Einsen, 13 Schritte, optimal
  1203.  
  1204. 0#1R1
  1205. 011L2
  1206. 1#1R2
  1207. 111H1
  1208. 2#1L0
  1209. 21#L1
  1210.  
  1211. 4 Zustände, 13 Einsen, 107 Schritte, optimal
  1212.  
  1213. 0#1R1
  1214. 011L1
  1215. 1#1L0
  1216. 11#L2
  1217. 2#1H2
  1218. 211L3
  1219. 3#1R3
  1220. 31#R0
  1221.  
  1222. ---------------------------------------------------------[ Das Hilbert Hotel ]--
  1223.  
  1224. 1. Das HIlbert Hotel hat unendlich viele Zimmer.
  1225. 2. Ein Bus mit unendlich Gästen kommt. Alle passen in das Hotel.
  1226. 3. Ein einzelner Gast kommt hinzu. Auch er passt ins Hotel, er bekommt das
  1227. erste Zimmer und alle anderen Gäste rücken ein Zimmer nach hinten.
  1228. 4. Unendlich viele Busse mit je unendlich vielen Gästen kommen. Die Gäste aus
  1229. dem ersten Bus belegen alle Zimmernummern kongruent modulo 2
  1230. (2, 4, 8, 16, 32, ...). Die Gäste aus dem zweiten Bus belegen alle
  1231. Zimmernummern kongruent modulo 3 und für die weiteren Busse werden weitere
  1232. Primzahlen (von denen es unendlich viele gibt) verwendet.
  1233. 5. Dabei bleiben immernoch unendlich Zimmer frei, etwa die Zimmernummer 6 oder
  1234. 10.
  1235.  
  1236. ----------------------------------------------[ Patterns für Turingmaschinen ]--
  1237.  
  1238. Im Folgenden ist das Leerzeichen `#` und Daten sind `0` und `1`.
  1239.  
  1240. Ans Ende des Bandes gehen
  1241.  
  1242. 1##R1 Überspringen führender Leerzeichen v v
  1243. 111R2 ##1100## -> ##1100##
  1244. 100R2
  1245. 211R2 Überspringen von Daten
  1246. 200R2
  1247. 2##LX Cursor steht eins links vom Ende
  1248.  
  1249. Hinter das Ende des Bandes schreiben
  1250.  
  1251. 111R1 211R2 v v
  1252. 100R1 200R2 ##1100### -> ##1100#1#
  1253. 1##R2 2#1LX
  1254.  
  1255. Drei Einsen Schreiben
  1256.  
  1257. 1#1R2 v v
  1258. 2#1R3 ##### -> #111#
  1259. 3#1RX
  1260.  
  1261. Daten Transformieren
  1262. 1. transformieren z.\,B. rechts von den Daten notieren
  1263. 2. Alte Daten löschen (ähnlich geht man beim Verschieben vor)
  1264.  
  1265. Anzahlen in Zuständen speichern
  1266. 1. Programmteil zum Abarbeiten der Daten (1).
  1267. 2. Programmteil zum Zurückgehen (B).
  1268. 3. Programmteile zum Schreiben der Anzahlen von Zeichen
  1269.  
  1270. Blockaufbau
  1271. Man kann die obigen Abschnitte als Textblöcke notieren. Idealerweise
  1272. lässt man Platz für eine Beschreibung oder macht vorher einen Plan.
  1273.  
  1274. Graphenaufbau
  1275. Lehrer empfiehlt das Zeichnen von Graphen wie bei anderen Automatenarten
  1276.  
  1277. ------------------------------------------[ Beispielturingmaschine x16F Nr 5 ]--
  1278.  
  1279. Erwartete Eingabe
  1280. `#iiiiii#` (Strichliste)
  1281. Ausgabe
  1282. `#vi#` (verkürzte Strichliste)
  1283. Vorgehen
  1284. Wir erkennen zunächst alle 5er Päckchen. Kommt keines mehr, kopieren wir
  1285. die Resteinsen. Am Ende wird der Verschnitt gelöscht.
  1286.  
  1287. Programm
  1288.  
  1289. +-[ Main ]-+ +-[ CP|WV ]-+ +-[ Dup i ]-+ +-[ Clean ]---+
  1290. | | | | | | | |
  1291. | 1##R1 | | 6iiR6 | | 9ixRA | | Cx#LC |
  1292. | 1iiR2 | | 6##R7 | | 9##LC | | Ci#LC |
  1293. | | | | | | | C##HC |
  1294. | 2##LF | | 7#vLB | | AiiRA | | |
  1295. | 2iiR3 | | 7vvR7 | | A##RD | +-------------+
  1296. | | | | | |
  1297. | 3iiR4 | +-----------+ | DvvRD | +-[ Back II ]-+
  1298. | 3##LF | | DiiRD | | |
  1299. | | +-[ Back ]--+ | D#iLE | | EvvLE |
  1300. | 4##LF | | | | | | EiiLE |
  1301. | 4iiR5 | | BvvLB | +-----------+ | E##LF |
  1302. | | | B##L8 | | |
  1303. | 5##LF | | | | FiiLF |
  1304. | 5ixR6 | | 8iiL8 | | FxxR9 |
  1305. | | | 8xxR1 | | F##R9 |
  1306. +----------+ | | | |
  1307. +-----------+ +-------------+
  1308.  
  1309. -------------------------------------------------------------------[ Graphen ]--
  1310.  
  1311. Adjazentzmatrix
  1312. Zum Graphen werden in einer y|x-Matrix überall dort 1en geschrieben, wo
  1313. es eine Kante gibt. Der Rest sind 0en. Ungerichtete Graphen sind so
  1314. immer symmetrisch.
  1315.  
  1316. (D)-------(C) ABCDE (D)----->(C) ABCDE
  1317. |\ | A01010 |^ | A01000
  1318. | \ | B10100 | \ | B00100
  1319. | (E) | C01010 | (E) | C01000
  1320. | | D10101 v | D10100
  1321. (A)-------(B) E00010 (A)----->(B) E00010
  1322.  
  1323. Adjazenzliste
  1324. Die Adjazentliste ordnet y-Knoten alle x-Knoten zu, die mit ihnen
  1325. verbunden sind. Für das erste Beispiel:
  1326. A -> B, D; B -> A, C; C -> B, D; D -> A, E, C; E -> D.
  1327.  
  1328. -----------------------------------------------[ Königsberger Brückenproblem ]--
  1329.  
  1330. Finde Reise genau 1x über jede Brücke.
  1331.  
  1332. ........................................
  1333. . A . (A)---\
  1334. . +--[####]--[####]--+--[####]--//-. | | \
  1335. . | B # D . (B)----(D)
  1336. . | # . | | /
  1337. .-//--+--[####]--[####]--+--[####]--//-. (C)---/
  1338. . C .
  1339. ........................................
  1340.  
  1341. Ungerade Anzahl an Wegen zu D => nicht möglich.
  1342.  
  1343. ................................................
  1344. . *********** . /(A)
  1345. . A +--[*###]--[##*#]--+----------//-. / | |
  1346. . * | B *********** D . | (B)----(D)
  1347. . * | ********* # * . \ | | /
  1348. .-//--[##*#]--+--[#*##]--[#*##]--+--[#*##]--//-. \(C)---/
  1349. . *********** ************ C .
  1350. ................................................
  1351.  
  1352. Gerade Anzahl an Kanten zwischen jedem Knoten => OK.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement