AUP:Prüfungsthemen: Unterschied zwischen den Versionen

Aus II-Wiki
Wechseln zu: Navigation, Suche
K (Baum)
K (Petronios verschob Seite AUP:Prüfungsthemen nach AUP:Prüfungsthemen, ohne dabei eine Weiterleitung anzulegen: Schei? Encoding)
 
(kein Unterschied)

Aktuelle Version vom 10. Juli 2013, 17:37 Uhr

Schwerpunkte der AUP-Klausur:

Grundbegriffe

Algorithmen

Im Allgemeinen ist ein Algorithmus die eindeutige Beschreibung eines Verarbeitungsprozesses.

Im Sinne der Informatik ist ein Algorithmus eine Kette von Maschinenbefehlen die von der Maschine ausgeführt erden.

Ein Algorithmus ist eine präzise (in einer festgelegten Sprache abgefasste) endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer (Verarbeitungs-)Schritte.

Terminierung

Die Terminierung eines Algorithmus gewährleistet, dass er bei jeder Eingabe nach endlich vielen Schritten abbricht.

Determinismus / Determiniertheit

Duden Informatik (S.183-185) "Determiniertheit: Einen Algorithmus (Algo) kann man als Abbildung von der Menge der möglichen Eingabewerte in die Menge der möglichen Ausgabewerte auffassen. Ist diese Abbildung eine Funktion, d.h. bildet sie jeden möglichen Eingabewert auf höchstens einen Ausgabewert ab, so nennt man den Algo determiniert. Deterministische Algos sind immer auch determiniert. Eine Erweiterung des üblichen Algo-Begriffs bilden die nichtdeterminierten Algos. Sie können bei gleichen Eingaben und Startbedingungen unterschiedliche Ergebnisse liefern. Diese Algos berechnen daher zu einem gegebenen Problem nicht notwendigerweise die korrekte Lösung. Die stochastischen Algos fallen beispielsweise unter diesen Algo-Begriff. Ferner kann man nichtdeterminierte Algos verwenden wenn es nicht auf ein spezielles Ergebnis, sondern auf irgendein Ergebnis, mit einer speziellen Eigenschaft ankommt. Bsp: Damenproblem.

Determinismus: Ein Algo oder Programm wird durch Maschinen schrittweise abgearbeitet. Der Algo heißt derterministisch, wenn es zu jeder Programmsituation höchstens eine nachfolgende Situation geben kann, wenn also zu jedem Zeitpunkt der Folgeschritt eindeutig bestimmt ist. Deterministische Algos sind immer auch determiniert. Die Umkehrung gilt nicht: Bei Quicksort kann man die Wahl des Pivot-Elements beliebig (nichtdeterministisch) vornehmen, das VErfahren liefert aber unabhängig hiervon zu jeder Eingabe immer genau eine Ausgabe: die sortierte Folge."

- deterministischer Ablauf: Es gibt eine eindeutige Vorgabe der Folge an ausfühbaren Schritten. Auf deutsch: Programmierer weiß immer genau, welchen Schritt das Programm zu einem bestimmten Zeitpunkt ausführen wird. Würde eine Anweisung von einer zufälligen Größe abhängen (Zufallszahlengenerator), dann würde es sich um einen nicht-deterministischen Algorithmus handeln.

- determiniertes Ergebnis: Eindeutiges Ergebnis bei vorgegeben Parameterwerten. Auf deutsch: Wenn ich n-mal die gleichen Eingabewerte in das Programm stecke, bringt es mir IMMMER dasselbe Ergebnis.

Bausteine

Bausteine sind elementare Operationen aus denen sich jeder Algorithmus zusammensetzt.

  • sequenzielle Ausführung (ein Prozessor!)
  • parallele Ausführung (mehrere Prozessoren!)
  • bedingte Ausführung
  • Schleife
  • Unter„programm“
  • Rekursion: Anwendung des selben Prinzip auf kleinere Teilprobleme

Pseudocode

Selektion:

falls, dann, sonst - if, then, else

Schleifen:

solange, führe aus - while

solange, für - for

wiederhole, bis - do while

Ein und Ausgabe:

Read, Print Return = Rückgabe einer Variable innerhalb einer Prozedur

Mathematische Befehle:

Mod = Rest

Sprachen

Sprachen und Gramatik

Syntax: Formale Regeln, welche Sätze gebildet werden könnenn:

  • „Der Elefant aß die Erdnuss.“ (syntaktisch korrekt)
  • „Der Elefant aß Erdnuss die.“ (syntaktisch falsch)

Semantik: (Formale) Regeln, welche Sätze eine Bedeutung haben:

  • „Der Elefant aß die Erdnuss.“ (semantisch korrekt, „sinnhaft“)
  • „Die Erdnuss aß den Elefant.“ (semantisch falsch, „sinnlos“)

Datentypen

Einfache Datentypen

int = 33636;

byte = 12;

double = 12.2425226; // Gleitkommazahl

Arrays:

int[] feld = new int[10]; //Feld mit 10 Elementen von Typ int

oder

int[] feld = {12,25,23,2,12,421,25,32,53}; // direkte Wertzuweisung des Arrays

Algorithmenparadigmen

Die Paradigmen müssen angewand, verstanden und genutzt werden können.

applikativ

eine Algorithmusbeschreibung ist applikativ, wenn sie die Funktionsweise beschreibt. Das bedeutet, das das ganze Programm aus Funktionsdefinitionen aufgebaut wird.

Typisches Beipsiel: Rekursion

Methode Berechne(paramWert1, ParamWert2)
{ 
  if paramWert1 < 0 then return 0;
  else Berechne (paramWert1 +5, paramWert2  mod 10)
}

Das Ganze ist dann auch mathematisch sauber.

Eine Zuweisung wie

x = x + 10;

ist nicht applikativ, das macht mathematisch keinen Sinn ;))

imperativ

eine Algorithmusbeschreibung ist imperativ, wenn sie die Arbeitsweise auf Maschinenebene beschreibt.

Das heißt, das ein solcher Algorithmus auf dem Konzept von Anweisungen und Variablen basiert. Man kann Variablen Werte zuweisen und deren Werte mit Anweisungen verändern. Jede Wertzuweisung entspricht dem gegenwärtigen Zustand der Variable.

Typisches Beispiel: Schleifen

Grundalgorithmen

Das Prinzip und die Eigenschaften der Grundalgorithmen müssen gekonnt werden (Deutsch nicht unbedingt ^^)

Suche

Sequenzielle Suche

Die Sequenzielle Suche ist eine Suchmethode, die jedes einzele Element der Folge durchsucht. Deshalb verhällt sie sich linear (n) und funktioniert auch bei ungeordneten Folgen.

algorithm SeqSearch (F, k) ! p
Eingabe: Folge F der Länge n, Schlüssel k
for i := 1 to n do
  if F[i] = k then
    return i
  fi
od;
return NO_KEY

Binäre Suche

Die Binäre Suche durchsucht eine Folge, indem sie sich das mittlere Element herausnimmt und dieses mit dem Schlüssel vergleicht. Dann wird die Folge geteilt. Ist der Schlüssel kleiner als das Element, wird mit der Folge weitergemacht, die vor dem Element stand. Andernfalls wird mit der Folge weitergemacht, die hinter dem Element stand. Nun wird die Teilfolge nach dem gleichen Schema weiter durchsucht bis das herausgesuchte Element gleich dem Schlüssel ist.

Diese Suche verhält sich logaritmisch log(n). Funktioniert dafür nur bei geordneten Folgen.

algorithm BinarySearch (F, k) ! p
Eingabe: Folge F der Länge n, Schlüsse k
u := 1, o := n;
while u <= o do
  m := (u + o)/2;
  if F[m] = k then
    return m
  else
    if k < F[m] then
      o := m − 1
    else
      u := m + 1
    fi;
  fi;
od;
return NO_KEY

Sortieren

Man unterscheidet interne Sortierung wie Felder oder Listen und externe Sortierung wie Datensätze auf Festplatten.

Ein Sortierverfahren heißt stabil, wenn es die relative Reihenfolge gleicher Schlüssel beibehält.

Verfahren Stabilität Vergleiche (im Mittel)
SelectionSort instabil (n^2)/2
InsertionSort stabil (n^2)/4
BubbleSort stabil (n^2)/2
MergeSort stabil n log n
QuickSort instabil n log n

Sortieren durch Einfügen

Wird auch Insertionsort genannt, und sortiert indem es ein belibiges unsortiertes Element nimmt und es in den sortierten Bereich einfügt - an der richtigen Stelle natürlich.

Beispiel Kartenstapel: Die erste Karte ist ne 8. Dann nehme ich die und eröffne einen neuen Kartenstapel. Die nächste Karte des unsortierten Stapels ist ne 10. Kommt hinter die 8. Nächste Kingo. Kommt hinter die 10. Nächste 9 - kommt zwischen 8 und 10. usw usw usw....

Sortieren durch Selektion

Wird auch Sortieren durch Auswahl oder Selectionsort genannt.

Die Rinde arbeitet wie folgt: Die zu sortierende Folge wird durchsucht und das größte Element der Folge wird ans Ende geschrieben. Dann wird dieses Ende von der Folge abgeschnitten. Das ganze beginnt wieder von vorn, mit der um 1 verringerten Folge, solange, bis die Schieße sortiert ist.

Bubblesort

Das Prinzip ist eigentlich einfach. Vorbild sind Luftblasen im Wasser, die größten Blasen steigen am schnellsten auf und so sortiert sich das Ganze quasi von alleine (Dank der Auftriebskarft ^^).

BublleSort schaut, ob ein Element aus der Folge größer ist als sein Nachfolger. Ist dem so, werden die Elemente vertauscht. Wenns schon stimmt, wird nix gemacht. BS geht nun jedes Element durch und vertauvescht gegebenenfalls. Das passiert so lange, bis keine Vertauschungen mehr auftreten.

Mergesort

Typisches Divide and Conquer Muster.

Teile die zu sortierende Liste in viele einelementige Listen und füge diese dann zu einer neuen, sortierten Liste zusammen.

Vortiel gegenüber Quicksort: ist stabil Nachteil gegenüber Quicksort: Braucht Hilfsarry/s

Quicksort

  • Pivot-Element wählen (Mitte der Liste, oder am Ende oder zufällig gewählt)
  • alle Elemente die kleine als Pivot sind auf die eine und die anderen auf die andere Seite
  • Teile die Liste
  • Fahre rekursiv mit den Teillisten fort (d.h. suche in Teilliste wieder ein Pivotelemt. Wieder kleiner davor, größer danach. Wieder teilen. ...)
  • mach das solange, bis du nur noch einelementige Listen hast und füge diese dann zu einer sortierten Liste zusammen.

Muster

Einen Algorithmus zu entwerfen ist eine kreative Tätigkeit. Allerdings gibt es für ähnliche (Teil)probleme bestimmte vorgefertigte Ideen, die Algorithemmuster.

Rekursion

Rekursion ist ein typisches Element des applikativen Algorithmenparadigmas. Eine Funktion heißt rekursiv, wenn sie sich durch sich selbst definiert, also wenn sie sich selber in ihrer Definition aufruft.

Siehe auch: applikatives Algorithmenparadigma.

Greedy

engl. für gierig. Versuche mit jedem Teilschritt das Maximum zu erreichen. Greedy funktioniert nur, wenn sich die Lösung direkt aus den Eingabewerten aufbauen lässt. Ein Beispiel wäre die Codierung einer Dezimalzahl in eine Binärzahl. Eingabewerte wären die Binärstellen 2^n und die Dezimalzahl und Ausgabe wäre eine Folge von Nullen und Einsen. Greedy besagt nun: Welche Stelle 2^n passt höchstens in die Dezimalzahl? Also: Dezimalzahl ist z.B. 149. Dann ist der größte binäre Anteil die zahl 128 (1000 0000). Übrig bleiben jetzt noch 21 von der Dezimalzahl. Der höchste binäre Anteil ist die 16 (0001 0000). Übrig bleiben jetzt noch 5. Der höchste Anteil ist die 4 (0100). Naja und dann noch die 1.

Divide 'n' Conquer

D&C bietet sich an, wenn man ein Problem hat, das zu groß ist, um im Ganzen gelöst zu werden. Man versucht halt, das große Problem in viele kleine Probleme zu zerstückeln - allerdings müssen die kleinen Teilprobleme dieselbe Struktur haben wie das große Ausgangsproblem, damit sie sich genauso bearbeiten lassen. Wenn dann die Teilprobleme so klein sind, das sie sich problemlos lösen lassen, dann setzt man die kleinen Teilprobleme halt wieder zu dem großen Ausgangsproblem zusammen. Das geht deshalb, weil man ja drauf geachtet hat, das die kleinen Probleme dieselbe struktur haben wie das große Problem.

D&C lässt sich am besten rekursiv lösen.

ADT

ADT = Abstrakte Datentypen. Was soll das, was bringt das? Der Programmierer will seine Software wiederverwenden. Dazu muss er seine Software so vielseitig wie möglich schreiben. Das abstrakte Konzept der ADTs ermöglicht das. Nicht die Frage, wie man etwas berechnet, wird in den Vordergrund gestellt, sondern das "Was" interessiert. Also, was will ich denn eigentlich berechnen und welche Eigenschaften hat es? Dieses Konzept kommt dem menschlichen Denken am Nächsten. Der Mensch interessiert sich ja auch für die Eigenschaften von Dingen. ADTs haben bestimme Eigenschaften: Das ist die Kapselung und eng verbunden damit das Geheimnisprinzip. Das beduetet, das es keinen interessiert, wie der ADT intern funktioniert. Wichtig ist nur, das ich mit dem ADT meine Berechnungen erledigen kann. Das ist wie wenn Frauen Auto fahren: Sie wissen nicht, wie das Auto funkioniert aber bewegen können sie es trotzdem (zumindest so halbwegs). (A.d.R. Der Satz stellt die Meinung des Bearbeiters dar (A.d.Bearbeiters: Nicht nur ... ^^))

Wenn man einen ADT definieren will, muss man ihm Eigenschaften verleihen:

  • Typ: Name des ADTs und evtl. übergebene Paramter
  • Functions: Wenn das Ding was machen soll, braucht es Funktionen. Diese heißen hier "Signaturen". Beispiel: ADT Liste. Der braucht eine Funktion, um Elemente zu laden, um sie zu löschen, um sie zu verschieben, zu kopieren und und und...
  • Axioms: Beschreibung der speziellen Eigenschaften der Funktionen. Zum Beispiel, das 0! = 1 ist oder das beim ADT der natürlichen Zahlen eine Zahl x + 0 wieder gleich der Zahl x ist.
  • Precondition: Uninteressant. Das ist wichtig, wenn man partielle Signaturen erstellt hat, hier kann man angeben, wann genau sie definiert sind.
  • Konstruktor: Damit ein Compiler einen ADT ins Leben rufen kann, braucht es einen Konstruktor. Das heißt, der Compiler muss wissen, wie er den ADT erstellt und das sagt ihm eben dieser Konstruktor.

Umsetzung > OO-Konzept

Umsetzung des ADT-Konzepts in Programmiersprachen nennt sich objektorientierte Programmierung. Typische Vertreter sind C++ oder Java.

Der ADT an sich nennt sich hier Klasse. Um mit ihm arbeiten zu können, lassen sich beliebig viele Objekte aus dieser Klasse ableiten, die nennen sich dann Instanzen der Klasse.

Eine Klasse braucht Methoden (Funktionen), die ihr verhalten bestimmen. Und sie braucht Attribute (Variablen), die ihren Zustand bestimmen.

Beispiel:

Klasse Katze

Variable itsAge;
Variable itsWeight;
Variable itsGender;

Funktion SetAge();
Funktion SetWeight();
Funktion SetGender();

Funktion GegenWandRennen();
Funktion Meow();
Funktion KatzenkloBenutzen();

Jetzt kann man auf der Klasse verschiedene Objekte definieren, z.B. Die Katze Frisky:

Katze Frisky = new Katze();

Und dann kann man das Vieh etwas zun lassen:

Frisky.Meow();                      //"Miau!"
Frisky.KatzenkloBenutzen();         //"zu spät, das blöde Vieh hat schon auf den Teppich gepisst..."

Jedes Objekt, was man erstellt, hat im Grunde die gleichen Eigenschaften aber mit anderen Werten. Zum Beispiel die weibliche, 5 kg schwere Frisky, die 5 Jahre alt ist. Oder der männliche, 10 kg schwere Felix, der 15 Jahre alt ist. Oder der schwule, 25 kg schwere Kater Sören, der 17 Jahre alt ist.

Jetzt gibts da ne ganze Menge Dinge zu beachten:

  • Wenn man ein Objekt erstellt, ist dies lediglich eine Referenz auf einen Speicherbereich. Man spricht also nicht den Speicher selbst an, wie bei einem Int-Wert, sondern die Referenz, die dann auf den Speicher zeigt. Daher nennen sich ADTs auch Referenzdatentpyen.
  • Vererbung: Klassen können kaskadierend definiert werden. Das heißt, eine Unterklasse kann von einer Oberklasse erben. Eine Oberklasse ist z.B. die Klasse "Frau". Die hat bestimmte Grundeigenschaften die jede Frau hat, z.B. Haare, Augen, Brüste usw... Jetzt gibt es zur Klasse Frau beliebig viele Unterklassen, z.B. "Zicke", "Tusse" oder "Granate". Alle diese Unterklassen erben alle Eigenschaften der Oberklasse. Also jede "Granate" hat ebenfalls Augen, Haare und Brüste etc. Hinzu kommen nun aber noch spezifische Eigenschaften der Unterklasse, z.B. das Attribut "geilesFahrgestell" oder die Funktion "mitArschWackeln()".
  • Überladen: Überladen bedeutet, das ich mehrere Methoden mit dem gleichen Namen deklarieren kann, die sich aber in der Form der übergebenen Paramter und/oder des Rückgabewertes unterscheiden müssen. Die Java-Machine wählt dann selber aus, welche der Methoden zu benutzen ist, indem sie sich anschaut, welcher Paramter beim Aufruf übergeben wird.
  • Überschreiben: Ich hab eine Oberklasse und da steht irgendeine Methode "xxx" drin. Jetzt baue ich mir eine Unterklasse und merke, das die Methode "xxx" nicht so richtig zu meiner Unterklasse passt. Dann kann ich "xxx" in der Unterklasse nochmal deklarieren, aber anders als in der Oberklasse. Ich muss lediglich beachten, dass die in der Unterklasse definierte Methode "xxx" dieselben Paramter übernimmt und den selben Typ zurückgibt, wie die "xxx" aus der Oberklasse.

Grunglegende Datenstrukturen

Wenn man in Jave viele gleichartige Objekte irgendwo speichern will, bietet sich zum Beispiel das Array an. Das hat aber viele Nachteile, der größte ist, das man seine Größe beim Erstellen festlegen muss - und dann nicht mehr nachträglich ändern kann. Zum Glück gibts ja noch Alternativen:

Stack

Auch Kellerspeicher. Man packt einfach ein neues Element oben drauf. Der Stack arbeitet mit dem LIFO-Prinzip: Last In, First Out. Er hat 3 wichtige Funktionen:

  • Push: Packe ein neues Element oben auf den Stack
  • Pop: Hole das oberste (das zuletzt draufgepackte) Element vom Stack runter
  • Top: Zeig mir das oberste (das zuletzt draufgepackte) Element, lass es aber auf dem Stack liegen.

verkettete Liste

In Java: z.B. AbstractList oder LinkedList (gibt noch mehr).

Man kann sich das so vortellen wie ein dynamisches Array. In eine VL kann man beliebig viele Elemente packen. Wenn man ein Element hinten dran packt, bekommt das vorige Element einen Verweis (Referenz) auf das Element, was man hinten dran gepackt hat. So kennt jedes Element seinen Nachfolger, weiß aber nicht, was vor ihm oder hinter seinem Nachfolger los ist.

Dieses Konzept erlaubt Elemente vorne einzufügen oder zu löschen (GetFirst, RemoveFirst) und Elemente hinten einzufügen oder zu löschen (GetLast, RemoveLast).

Leider muss man, um ein Objekt irgendwo in der Mitte der Liste zu bekommen, jedes Element von vorne durchwandern, weil ja jedes Element nur seinen Nachfolger kennt. Um das zu umgehen, gibts den sogenannten ListIterator. Das ist eine abstrakte Referenz (in C++: Zeiger), den man sich auf irgendein Objekt in der Liste legen kann und der dieses Wandern erheblich beschleunigt. Beim Array gibts auch nen ListIterator, aber der ist sinnlos, weil man ja auf die Elemnte mit den Index zugreifen kann, also z.B. Feld[152].

Es gibt auch noch doppelt verkettete Listen (z.B. die LinkedList in Java) bei denen jedes Element nicht nur seinen Nachfolger, sondern auch seinen Vorgänger kennt. Somit kann man die Liste auch von hinten durchgehen.

Baum

Das Baumkonzept kennt ja wohl jeder aus der Stochastik. Das gibts auch in Java:

Jeder Baum beginnt bei der "Wurzel", dem Ausgangsknoten. Die Knoten werden untereinander verbunden, die Verbindungen heißen "Kanten". Die letzten Knoten, also unten, wo der Baum aufhört, heißen "Blätter". Und alle Knoten, die auf Ebenen zwischen Wurzel und Blättern liegen, heißen "innere Knoten".

  • Sonderform binärerer Suchbaum: Von jedem Knoten gehen 2 Unterknoten ab, wobei der linke Unterknoten kleiner als der Ausgangsknoten ist, der Rechte ist größer. So wird der Baum sortiert und die Suche gestaltet sich einfach. Wichtig ist nur, das diese Struktur erhalten bleibt, wenn man Knoten löscht oder neue einfügt.


Traversierung: Gibt an, wie eine Baumstruktur durchlaufen werden soll. Dient vor allem der eindimensionalen Speicherung.

  • preorder: Der Baum wird von der Wurzel aus durchlaufen. Danach geht's vom linken Teilbaumin den rechten
  • postorder: Der Baum wird vom linken Teilbaum nach rechts durchlaufen. Dies wird im rechten fortgesetzt. Die Wurzel kommt zum Schluss.
  • inorder: Der Baum wird von links - über die Wurzel - nach rechts durchlaufen.

Siehe auch: Prüfungsthemen, Duke