21
Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Embed Size (px)

Citation preview

Page 1: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK

FreitagInformatik II, 3. Teil

Repetition und Prüfungstipps

Page 2: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 2

Ablauf heute

Komplexitätsrechnen (Big O, Landau) Vergleich zwischen Mergesort und Heapsort Backtrackingaufgabe Repetition C++ C++ Programmieraufgabe (OO) Prüfungstipps

Page 3: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 3

Komplexität

Computer sollen uns helfen eine grosse Zahl von Daten möglichst schnell zu verarbeiten

Toll ist auch, wenn wir nicht viel Speicher allozieren müssen

Der Komplexitätsgrad eines Algorithmus ist meist abhängig von der Anzahl Eingabewerte n (Grösse der Daten) und manchmal auch von deren Reihenfolge

Man schreibt die Komplexität also in Abhängigkeit von n Bei der Reihenfolge unterscheiden wir zwischen

bestem Fall, durchschnittlichen Fall und schlimmsten Fall

Page 4: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 4

O-Notation

Eine Funktion f O(g) wächst nicht schneller als die ∊Funktion g

O(g) beschreibt aber eine ganze Klasse von Funktionen Oft ist man jedoch nur am asymptotischen Aufwand

eines Algorithmus in Abhängigkeit von n interessiert (n → ∞)

Wir schreiben die Komplexität eines Algorithmus deshalb als eine Funktion von n: O(f(n))

Mit dieser Information können wir herausfinden, ob unser Algorithmus skalierbar ist

Page 5: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 5

Rechenregeln

Es gilt: f = O(f) c O(f) = O(f) (für eine Konstante c)

Für ein Polygon: f(n) = 12n²+3n-4 → O(f(n)) = O(n²) Für n → ∞ ist nur noch der höchste Grad eines

Polygons relevant (Anteil der am schnellsten ansteigt)

Page 6: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 6

Beispiele für O(1)

Bedeutung: Der Algorithmus übersteigt einen gewissen konstanten Wert nie (der konstante Wert kann aber auch 10'000 sein) → unabhängig von n

if (x%2 == 0) // do something Die push(Element e) Funktion des Stacks hat

konstante Komplexität, weil es egal ist, wie viele Elemente schon im Stack sind, die Zeit die es braucht um das Element zuoberst auf den Stack zu legen ist immer gleich.

Auch die add(int value) Funktion für die verkettete Liste

Generell mögen wir Algorithmen mit O(1) ;-)

Page 7: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 7

Beispiele für O(n)

Bedeutung: Der Algorithmus ist linear abhängig von n. Verdoppeln wir also die Anzahl n, verdoppeln wir auch den Aufwand des Algorithmus

for (int i = 0; i < n; i++)

if (x[i]%2 == 0) // do something Suchen eines Elements in einer unsortierten Liste oder

Array oder einem schlecht balancierten Baumes

Page 8: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 8

Beispiele für O(n²)

Bedeutung: Der Algorithmus ist quadratisch abhängig von n. Wenn wir also n verdoppeln, wird der Aufwand vervierfacht.

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++)

if (x[i][j]%2 == 0) // do something

}

Insertion sort und selection sort haben im Schnitt eine Komplexität von O(n²)

Algorithmen mit O(n²) sind schlecht skalierbar!

Page 9: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 9

Beispiele für O(log n)

Bedeutung: Der Algorithmus ist logarithmisch von n abhängig. Wenn wir n also verdoppeln steigt der Aufwand des Algorithmus konstant an.

int i = n;

while (i > 0) {

// do something

i = i / 2;

}

Mit der Binärsuche finden wir ein Element in einem sortierten Array der Länge n in log n Schritten. Auch bei einem gutartigen Suchbaum ist dies der Fall.

int binsearch (int s){

int m;int li = 0; int re = A.length-1;while ( re>=li ) {

m = (li+re)/2;if (s == A[m]) return m;if (s < A[m]) re = m-1;else li = m+1;

}return (-1);

}

Page 10: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 10

Beispiele für O(n log n)

Bedeutung: Der Aufwand des Algorithmus ist quasilinear.

Oft sind diese Algorithmen optimal für den allgemeinen Fall.

Sortieren mit Mergesort und Heapsort fallen in diese Kategorie

void mergesort(int li, re) {

…if (…) {

m = (li+re)/2;mergesort(li, m);mergesort(m+1,

re);…

}}

t(n) = n + 2*t(n/2)

Beweis im Script mit n=2k

Page 11: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 11

Vergleich von Heapsort und Mergesort

Heapsort hat ebenfalls die Zeitkomplexität von O(n log n) Wir können aber Mergesort einfach parallelisieren und so

einen Zeitaufwand von fast O(n) erreichen Was den Platzaufwand angeht, so ist Heapsort mit Arrays

sicher günstiger. Falls wir aber verkettete Listen verwenden benötigt Mergesort ebenfalls keinen zusätzlichen (von n abhängigen) Platz (es müssen nur die Referenzen neu angepasst werden)

Die Adressierung die bei Heapsort verwendet wird ist abhängig von Random Access, was wir bei Arrays garantiert haben. Für verkettete Listen, ist das Adressierungsverfahren von Heapsort ungünstig und langsam.

Page 12: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 12

Ab jetzt ist alles anders

Versucht die Aufgaben selbst zu lösen Ich bin da für Fragen (nicht nur betreffend der

Aufgaben, sondern auch allgemein bei Unklarheiten)

Page 13: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 13

Backtracking

Wir haben folgendes Murmelspiel mit 2*n+1 Feldern, n schwarze und n weisse Murmeln.

Das Ziel des Spieles ist, dass die Murmeln die Seiten tauschen:

Page 14: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 14

Backtracking

Dabei sind 4 Arten von Zügen erlaubt:

Schwarz rückt ein Feld vor

Weiss springt

Schwarz springt

Weiss rückt ein Feld vor

Page 15: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 15

Backtracking-Aufgabe

Implementiere einen Algorithmus mit Backtracking der alle möglichen Züge durchtestet

Initialisiere erst das Spielfeld. Dabei soll das Programm eine Zahl n annehmen und das Spielfeld der Länge 2*n+1 bilden

Implementiere eine Funktion, die das Spielfeld auf der Konsole ausgibt.

Dann implementiere eine Funktion, die testet welche Züge möglich sind und diese in einem Array zurückgibt.

Implementiere makeMove(int i) welche den i-ten Zug ausführt

Nun implementiere die Funktion solve() welche das Backtracking durchführt. Verwende dabei die Funktion testWin() um zu überprüfen, ob das Rätsel gelöst ist.

Page 16: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 16

Das Zeichen &

Bei C++ hat das Zeichen & 4 Bedeutungen Bitweises UND: & Boolsches UND: && Referenz:

void func(MyClass& myObject ) {

myObject.method();

}

Adressoperator:

int i = 5;

int* p = &i;

int** pp = &p;

Page 17: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 17

Das Zeichen *

In C++ hat das Zeichen * 3 Bedeungen Multiplikation: int a = b * c; Pointer:

int* p = &a;

int** pp = &p;

Dereferenzierung: *p = 10; // p zeigt auf Typ int

*pp = &b; // pp zeigt auf Typ int*

Page 18: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 18

Objektorientierung C++

Schreibe in C++ eine Klasse, die komplexe Zahlen verwaltet. Eine komplexe Zahl kann geschrieben werden als z=a+bi

wobei a der Realteil und b der Imaginärteil ist. Für i gilt i²=-1

Schreibe eine Klasse Complex welche die beiden Komponenten einer komplexen Zahl mit grosser Genauigkeit definiert. Verkapsle diese Komponenten.

Deklariere eine Methode set(...) und eine Methode get(...) welche jeweils beide Werte annimmt bzw. zurück liefert. Implementieren musst du sie aber nicht

Schreibe einen Konstruktor, dem man den Realteil und Imaginärteil übergibt

Page 19: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 19

Prüfungstipps

Je 1 Stunde für Informatik 1 und Informatik 2 Bei 7 bis 8 Aufgaben ergibt das 10 bis 20 Minuten pro

Aufgabe Theorieaufgaben meist schneller gelöst Programmieraufgaben teils recht aufwendig Bleibt also nicht zu lange an einer Aufgabe falls ihr

stecken bleibt (z.B. die Rekursion nicht seht) Bei ETH Prüfungen reichen oft 40% der Punkte für

eine 4 Nehmt mich aber nicht beim Wort, falls es nicht so ist

Page 20: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 20

Zusammenfassung

Bei Informatik 1 dürft ihr eine Zusammenfassung mitnehmen. Schreibt euch die wichtigsten Dinge drauf wie

Präzedenzliste ASCII Zeichensatz Beispielklassendefintion Beispiel zu Stack und verketteten Liste Syntax (z.B.: wie man ein Array initialisiert)

Schreibt eure Zusammenfassungen selbst, dann wisst ihr wo was ist und wie ihr es verwenden sollt.

Page 21: Informatik I/II PVK Freitag Informatik II, 3. Teil Repetition und Prüfungstipps

Informatik I/II PVK 21

Prüfungsvorbereitung Cellier-Skript ist ganz okay. Falls ihr etwas nicht versteht

schaut auf www.cplusplus.com nach Übt das Programmieren auf Papier Für Informatik II haben wir nur prüfungsrelevante Dinge

besprochen. Zum Lernen solltet ihr das Besprochene im Skript suchen und repetieren. Es stehen manchmal auch noch nützliche Dinge dazu, die ich nicht besprochen habe

Zum Beispiel: Negamax-Algorithmus zur Bestimmung des Minimax-Wertes

Falls ihr ganz sicher gehen wollt, dann lest auch noch den Teil zu Threads und zu den Türmen von Hanoi durch.

Die Generics aus den Informatik II Übungen funktionieren analog zu den Templates aus Informatik I.