Informatik II PVK

Pascal Schärli

pascscha@student.ethz.ch

Voraussetzungen

Pascal Schärli - PVK Informatik II 2021

Primitive Datentypen

Voraussetzungen

boolean
- True / False
char
- Ascii Character
byte
- 8 bit Ganzzahl
short
- 16 bit Ganzzahl

int
- 32 bit Ganzzahl
long
- 64 bit Ganzzahl
float
- 32 bit Fliesskommazahl
double
- 64 bit Fliesskommazahl

Pascal Schärli - PVK Informatik II 2021

Primitive Datentypen

Voraussetzungen

	boolean	char	byte	short	int	long	float	double
boolean
char
byte
short
int
long
float
double

int

long

float

double

int

long

float

double

int

long

float

double

a + b = c

Mit Booleans kann nicht gerechnet werden
Das Resultat ist mindestens ein int
Das Resultat hat immer den allgemeineren Typ

Pascal Schärli - PVK Informatik II 2021

Increment

Voraussetzungen

Wert von a

Output

Wert von a

Output

int a = 5;
System.out.println(a++);

int a = 5;
System.out.println(++a);

Die Variabel wird erhöht und der alte Wert wird zurückgegeben

Die Variabel wird erhöht und der neue Wert wird zurückgegeben

Post Increment

Pre Increment

Der Pre- Post Increment Operator erhöht eine Variable um 1.
Man kann das Increment vor oder nach der Variabel schreiben.

Pascal Schärli - PVK Informatik II 2021

Voraussetzungen

Scopes

8
8

int a = 2;

if (x < 7) {
    a = 8;
    System.out.println(a);
}

System.out.println(a);

8
2

int a = 2;

if (x < 7) {
    int a = 8;
    System.out.println(a);
}

System.out.println(a);

Pascal Schärli - PVK Informatik II 2021

Voraussetzungen

public static void printListElements(ArrayList<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i));
    }
}

For-Each-Loop

public static void printListElements(ArrayList<Integer> list) {
    for (Integer k : list) {
        System.out.println(k);
    }
}

For-Loops können kompakter notiert werden, falls man über alle Elemente einer Liste iterieren will:

Pascal Schärli - PVK Informatik II 2021

Voraussetzungen

1 2 4 8

int i = 1;
do{
    System.out.println(i + " ");
    i*=2;
} while(i < 10);

Alternative zum while-Loop
Kondition wird erst am Ende geprüft
Schleifenkörper wird mindestens ein Mal ausgeführt

Do-While-Loop

Pascal Schärli - PVK Informatik II 2021

Voraussetzungen

0 2 4 6 8

for (int i = 0; i < 10; i++) {
    if (i % 2 != 0)
        continue;
    System.out.print(i + " ");
}

Das Keyword "continue" bricht die Loop-Iteration ab.
Die Ausführung vom Schleifenkörper wird abgebrochen und die nächste Iteration wird gestartet.

Continue

Pascal Schärli - PVK Informatik II 2021

Voraussetzungen

for (int i = 0; i < 10; i++) {
    if (i % 2 != 0)
        break;
    System.out.print(i + " ");
}

Das Keyword "break" bricht den ganzen Loop ab.
Die Ausführung der ganzen Schleife wird abgebrochen und das Programm geht nach der Schleife weiter.

Break

Pascal Schärli - PVK Informatik II 2021

Ternary Operator

Voraussetzungen

In Java ist "?" ein Operator, welchen man als Abkürzung von einem if-else Statement verstanden werden kann
Die Syntax ist <boolean> ? <value1> : <value2>
Der Output ist <value1> falls der boolean true war, ansonsten ist der Output <value2>.
Beispiel:

boolean y = true;
String s = y ? "y was true" : "y was false";
System.out.println(s);

y was true

Pascal Schärli - PVK Informatik II 2021

int foo(int a, float b, boolean c){
    if(c){
        a += b;
    }
    else{
        a-=b;
    }
    return a;
}

Datentyp vom Rückgabewert

Name der Funktion

Beliebig viele Übergabewerte

Funktions-Körper (Berechnung)

Rückgabe des Resultats

Funktionen

Voraussetzungen

Pascal Schärli - PVK Informatik II 2021

/**
 * Checks wether x is within the interval [left, right]
 * 
 * @param x 
 * @param left The left edge of the interval
 * @param right The right edge of the interval
 * @return true iff x is in the interval [left, right]
 * @throws IllegalArgumentException if the interval is empty
 */
boolean inInterval(double x, double left, double right){
    if(left > right){
        throw new IllegalArgumentException("Empty Interval");
    }
    return x >= left && x <= right;
}

Javadoc

Voraussetzungen

Pascal Schärli - PVK Informatik II 2021

Prüfungs Statistiken

Pascal Schärli - PVK Informatik II 2021

Prüfungsstatistiken

Generell

Bei Informatik 2 sind die Prüfungen weniger konsistent als bei Informatik 1
Ihnen ist es wichtig immer wieder neue und frische Aufgaben zu machen, und kennen alle Prüfungen weche auf AMIV veröffentlicht sind.
Trotzdem gibt es einige Aufgabentypen, welche fast jedes Jahr kommen, wenn auch in leicht abgeänderter Form.
Daher denke ich, dass das Lösen von alten Prüfungen trotzdem eine gute Vorbereitung ist, auch wenn sie sagen, dass es nicht so ist.
Auf meiner Webseite habe ich alle einzelnen Prüfungsaufgaben mit Lösungen hochgeladen:
https://pascscha.ch/info2/pvk/pruefungen/

Pascal Schärli - PVK Informatik II 2021

Prüfungsstatistiken

Notenpunkte pro Kategorie

Pascal Schärli - PVK Informatik II 2021

Prüfungsstatistiken

Notenpunkte pro Aufgabentyp

Pascal Schärli - PVK Informatik II 2021

Objektorientierung

Pascal Schärli - PVK Informatik II 2021

Objektorientierung

Call by Reference

In C++ war beides möglich:
- Call by value: Daten werden kopiert und übergeben
- Call by reference: Referenz auf die Daten wird übergeben

Java ist IMMER call by value!!
- Bei der Übergabe einer Referenz auf ein Objekt wird die Adresse in eine lokale Variable kopiert!
- Bei Übergabe eines primitiven Typs (char, int, float) wird der Wert in eine lokale Variable kopiert!

Pascal Schärli - PVK Informatik II 2021

 public static void swap(StringBuffer sbf1, StringBuffer sbf2)   {
	StringBuffer temp = sbf1;
	sbf1 = sbf2;
	sbf2 =temp;
 }

 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);

 Hello World
 Hello World

Output:

Broken Swap

Objektorientierung

Trotzdem dass beim Funktionsaufruf eine Referenz übergeben wird, werden die Stringbuffer nicht getauscht, warum?

Pascal Schärli - PVK Informatik II 2021

 public static void swap(StringBuffer s1, StringBuffer s2){
	StringBuffer temp = s1;
	s1 = s2;
	s2 =temp;
 }

 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);

Output:

sbf1

address1

address1

"Hello"

address2

"World"

sbf2

address2

Hello World

Objektorientierung

Broken Swap

Pascal Schärli - PVK Informatik II 2021

 public static void swap(StringBuffer s1, StringBuffer s2){
	StringBuffer temp = s1;
	s1 = s2;
	s2 =temp;
 }

 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);

Hello World

Output:

sbf1

address1

address1

"Hello"

address2

"World"

sbf2

address2

s1

address1

s2

address2

swap

Objektorientierung

Broken Swap

Pascal Schärli - PVK Informatik II 2021

 public static void swap(StringBuffer s1, StringBuffer s2){
	StringBuffer temp = s1;
	s1 = s2;
	s2 =temp;
 }

 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);

Hello World

Output:

sbf1

address1

address1

"Hello"

address2

"World"

sbf2

address2

s1

address1

s2

address2

swap

Objektorientierung

Broken Swap

Pascal Schärli - PVK Informatik II 2021

 public static void swap(StringBuffer s1, StringBuffer s2){
	StringBuffer temp = s1;
	s1 = s2;
	s2 =temp;
 }

 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);

Output:

sbf1

address1

address1

"Hello"

address2

"World"

sbf2

address2

Objektorientierung

Broken Swap

Pascal Schärli - PVK Informatik II 2021

Hello World
Hello World

public static void swap(StringBuffer s1, StringBuffer s2) {
    StringBuffer temp = new StringBuffer(s1);
    
    s1.delete(0, s1.length());
    s1.append(s2);
	
    s2.delete(0, s2.length());
    s2.append(temp);
}

 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);

Hello World

Output:

sbf1

address1

address1

"Hello"

address2

"World"

sbf2

address2

Hello World
World Hello

s1

address1

s2

address2

swap

"Hello"

"World"

$\rightarrow$ Man kann das zu Grunde liegende Objekt verändern!

Objektorientierung

Fixed Swap

Pascal Schärli - PVK Informatik II 2021

Pakete

Objektorientierung

{1, 4, 21, 8}
→ “1, 4, 21, 8, null“

Lists.java

package u5a1;
import node.Node;

public class Lists {	
    public static String toString(Node node) {
        if (node == null) return "null";

        StringBuffer buf = new StringBuffer();
        buf.append(node.value).append(", ").append(toString(node.next));
        return buf.toString();
    }
}

Node.java

package node;

public class Node {
  public int value;
  public Node next;
  public Node(int value, Node next) {
    this.value = value;
    this.next = next;
  }  
}

Pascal Schärli - PVK Informatik II 2021

Keywords

Objektorientierung

final: Darf nicht verändert werden
public: Für alle Sichtbar
private: In der Klasse Sichtbar
protected: in abgeleiteten Klassenund im package Sichtbar
static: unabhängig von der Klasseninstanz, existiert nur einmal für alle Objekte dieser Klasse
Ohne Modifier: Im package sichtbar

public class Impedance {
    private final String name;
    protected double real, imag;
    int i;
    
    public Impedance(String name, double real, 
            double imag) {
        this.name = name;
        this.real = real;
        this.imag = imag;
    }

    public static Impedance add(String name, 
            Impedance z1, Impedance z2) {
        double real = z1.getReal() + z2.getReal(); 
        double imag = z1.getImag() + z2.getImag();
        return new Impedance(name, real, imag);
    }

    public String toString() {
        return getName() + " = " + getReal() + 
            " + i" + getImag();
    }

    public String getName() {
        return this.name;
    }
    public double getImag() {
        return this.imag;
    }
    public double getReal() {
        return this.real;
    }
}

Pascal Schärli - PVK Informatik II 2021

In Java ist es möglich, dass eine Klasse von einer anderen Klasse "erbt".
Die erbende Klasse erbt somit alle Funktionen und Attribute und kann diese noch erweitern.
Dies ermöglicht es gewisse Typen und Strukturen besser zu modellieren.

Polymorphie

Objektorientierung

Pascal Schärli - PVK Informatik II 2021

 public class Fahrzeug{
    int radzahl;

    public Fahrzeug(int radzahl){
        this.radzahl = radzahl;
    }
 }

 public class Auto extends Fahrzeug{
    protected float hubraum;
    
    public Auto(float hubraum){
        super(4);
        this.hubraum = hubraum;
    }

    public float getHubraum(){
        return hubraum;
    }
    
    public void setHubraum(float hubraum){
        if(hubraum>0) this.hubraum = hubraum;
    }
 
 }

 public class Lastwagen extends Auto{
    float capacity;
    
    public Lastwagen(float hubraum,
                     float capacity){
        super(hubraum);
        this.capacity = capacity;
    }
 }

 public class Fahrrad extends Fahrzeug{
    
    public Fahrrad(){
        super(2);
    }
 }

Fahrzeug

Auto

Lastwagen

Fahrrad

Objektorientierung

Polymorphie

Pascal Schärli - PVK Informatik II 2021

Fahrzeug myFahrrad = new Fahrrad();

System.out.println(myFahrrad.radzahl);
		
myFahrrad.setHubraum(300);

Fahrzeug myLastwagen = new Lastwagen(80000,50);

System.out.println(myLastwagen.radzahl);
		
myLastwagen.setHubraum(300);

Output: 4

Output: 2

Compile Error:

The method setHubraum(int) is undefined for the type Fahrzeug

Compile Error:

The method setHubraum(int) is undefined for the type Fahrzeug

Fahrzeug

Auto

Lastwagen

Fahrrad

Polymorphie

Objektorientierung

Pascal Schärli - PVK Informatik II 2021

Warum können wir den Hubraum von myLastwagen nicht bestimmen, obwohl es ein Objekt vom Typ Lastwagen ist?
Beim Erstellen von myLastwagen haben wir gesagt, dass es vom Typ Fahrzeug ist:
myLastwagen hat also alle Attribute von einem Lastwagen, man kann sie einfach nicht abrufen.
$\Rightarrow$ Type Casts

Fahrzeug myLastwagen = new Lastwagen(80000,50);

((Lastwagen)myLastwagen).setHubraum(300);

Objektorientierung

Polymorphie

Pascal Schärli - PVK Informatik II 2021

Fahrzeug myLastwagen = new Lastwagen(80000,50);

System.out.println(myLastwagen.radzahl);
        
((Lastwagen)myLastwagen).setHubraum(300);

Fahrzeug myFahrrad = new Fahrrad();

System.out.println(myFahrrad.radzahl);
		
((Lastwagen)myFahrrad).setHubraum(300);

Runtime Error:

Exception in thread "main" java.lang.ClassCastException: Fahrzeug cannot be cast to Lastwagen

Fahrzeug

Auto

Lastwagen

Fahrrad

Objektorientierung

Polymorphie

Pascal Schärli - PVK Informatik II 2021

Falls ihr auf ein Attribut zugreifen möchtet, welches nicht existiert oder nicht abrufbar ist, gibt es einen Compile Error
Falls ihr einen Cast machen wollt, welcher nicht funktioniert, gibt es einen Runtime Error

Fahrzeug myLastwagen = new Lastwagen(80000, 50);

myLastwagen.setHubraum(300);

Fahrzeug myFahrrad = new Fahrrad();

((Lastwagen)myFahrrad).setHubraum(300);

Polymorphie

Objektorientierung

Fahrrad

Lastwagen

Auto

Fahrzeug

Pascal Schärli - PVK Informatik II 2021

class Mensch { ... }

class ETHStudent extends Student { String legiNr; }

class ITETStudent extends ETHStudent { ... }

class Student extends Mensch { ... }

Student tim = new ETHStudent();

Object obj           = tim;
Mensch mensch        = tim;
Student student      = tim;
ETHStudent ethStud   = (ETHStudent) tim;
ITETStudent itetStud = (ITETStudent) tim;

Java denkt es ist ein Student

Wir wissen, es ist ein ETHStudent

ohne cast

mit cast

Runtime Error

zuweisung möglich ohne Cast

zuweisung möglich mit Cast

Runtime Error

jede Java Klasse erbt von Object

Objektorientierung

Polymorphie

Pascal Schärli - PVK Informatik II 2021

class Mensch { ... }

class ETHStudent extends Student { String legiNr; }

class ITETStudent extends ETHStudent { ... }

class Student extends Mensch { ... }

Student tim = new ETHStudent();

Mensch mensch        = tim;
Student student      = tim;
ETHStudent ethStud   = (ETHStudent) tim;
ITETStudent itetStud = (ITETStudent) tim;

System.out.println(mensch.legiNr);
System.out.println(student.legiNr);
System.out.println(ethStud.legiNr);
System.out.println(itetStud.legiNr);

Compile Error

Kein Compile Error

haben legiNr

Polymorphie

Objektorientierung

Pascal Schärli - PVK Informatik II 2021

Falsche Type-Casts können zu Runtime-Error führen.
Wie können wir das verhindern?
instanceof Operator gibt zurück, ob ein Objekt gecasted werden kann.

Student tim = new ETHStudent();

System.out.println(tim instanceof Mensch);
System.out.println(tim instanceof Student);
System.out.println(tim instanceof ETHStudent);
System.out.println(tim instanceof ITETStudent);

true
true
true
false

Output:

instanceof

Objektorientierung

Pascal Schärli - PVK Informatik II 2021

In einer Abstrakten Klasse kann man Methoden implementieren, aber auch nur deklarieren.
Man kann keine Abstrakten Objekte instanzieren (weil man sonst unimplementierte Methoden aufrufen könnte)
Eine Klasse kann höchstens eine Abstrakte Klasse erweitern

public abstract class AbstractStack {
    // declare abstract functions
    public abstract void push();
    public abstract int pop();
    public abstract int peek();
    public abstract int size();
    
    // already implement some functions
    public boolean isEmpty(){
    	return size() == 0;
    }
}

public class Stack extends AbstractStack {
    // declare abstract functions
    public void push(){/*TODO*/}
    public int pop(){/*TODO*/}
    public int peek(){/*TODO*/}
    public int size(){/*TODO*/}
}

Abstrakte Klassen

Objektorientierung

Pascal Schärli - PVK Informatik II 2021

In einem Interface kann man keine Methoden implementieren, nur nur deklarieren.
Man kann keine Interfaces instanzieren (weil man sonst unimplementierte Methoden aufrufen könnte)
Eine Klasse kann mehrere Interfaces implementieren.

public Interface IStack {
    // declare abstract functions
    public void push();
    public int pop();
    public int peek();
    public int size();
}

public class Stack implements IStack {
    // declare abstract functions
    public int push(){/*TODO*/}
    public int pop(){/*TODO*/}
    public int peek(){/*TODO*/}
    public int size(){/*TODO*/}
}

Interfaces

Objektorientierung

Pascal Schärli - PVK Informatik II 2021

Julia und Carina arbeiten mit Bäumen.
Um gleichzeitig daran zu arbeiten implementiert Carina den Baum und Julia schreibt das Programm.
Sie entscheiden sich: Sie verwenden einen ArrayTree
Nach der Hälfte der Zeit merkt Carina, dass ein ListTree besser geeignet wäre.
Carina sagt Julia, sie solle doch schnell alle Verwendungen von ArrayTree zu ListTree ändern.

Carina

Julia

Benutze ArrayTree

Meinung geändert, benutze ListTree

Objektorientierung

Factories

Pascal Schärli - PVK Informatik II 2021

Objektorientierung

Pascal Schärli - PVK Informatik II 2021

Um solche Katastrophen zu verhindern benutzen wir Interfaces und Factories
Julia benutzt eine "TreeFactory" um Bäume zu erstellen, welche dieses Interface implementieren.

interface ITree{
    public ITree leftChild();
    public ITree rightChild();
    public int getValue();
    public int setValue();    
}

public class TreeFactory {
    public static ITree makeTree(){
        return new ListTree();
    }
}

Tree Interface

Tree Factory

public class FancyCode {
	public ArrayTree important(){
        ArrayTree myRoot = new ArrayTree();
        myRoot.setValue(4);
        return myRoot;
    }
}

Julias Code Vorher

public class FancyCode {
	public ITree important(){
        ITree myRoot = TreeFactory.makeTree();
        myRoot.setValue(4);
        return myRoot;
    }
}

Julias Code Jetzt

Factories

ArrayList myList = new ArrayList();
myList.add(42);
myList.add(“I <3 Info II”);
int i = (Integer)myList.get(0);
String s = (String)myList.get(1);

ArrayList Kann beliebige Typen speichern:

Flexibel, aber Casts sind gefährlich
Falls man nicht mehr weiss, was wo in der Liste ist, kann es zu Chaos führen
$\rightarrow$ Generics

Objektorientierung

Generics

Pascal Schärli - PVK Informatik II 2021

ArrayList<Integer> myList = new ArrayList<Integer>();
myList.add(42);
int i = myList.get(0);
myList.add(“Hello World”);

Man kann einer ArrayList sagen, dass sie nur einen bestimmten Typ speichern darf:

Vorteile:
- Typsicherheit
- keine Casts nötig
Nachteile:
- Weniger Flexibel

Compile-Error

Objektorientierung

Generics

Pascal Schärli - PVK Informatik II 2021

public class Tree<T> {

  T value;
  Tree right;
  Tree left;
  
  public Tree(T value) {
    right = null;
    left = null;
    this.value = value;
  }
  
  public Tree<T> leftChild() {
  	return left;
  }

  public Tree<T> rightChild() {
  	return right;
  }
}

Tree<Integer> tree1 = new Tree<Integer>(5);
tree1.left = new Tree<Integer>(3);
tree1.right = new Tree<Integer>(6);

Tree<String> tree2 = new Tree<String>("root");
tree2.right = new Tree<String>("right");
tree2.left = new Tree<String>("left");

"root"

"left"

"right"

tree1

tree2

Objektorientierung

Generics

Pascal Schärli - PVK Informatik II 2021

Herbst 2017, 1.17 Notenpunkte

Objektorientierung

Prüfungsaufgabe

Pascal Schärli - PVK Informatik II 2021

Objektorientierung

Prüfungsaufgabe

Herbst 2017, 1.17 Notenpunkte

public class Activity{
    private String name;
    private double duration;
    private double rating;

    public Activity(String name, double duration, double rating) {
        if(duration <= 0) {
            throw new IllegalArgumentException("The duration can not be negative!");
        }
        if(rating < 0 || rating > 5) {
            throw new IllegalArgumentException("The rating has to be between 0 and 5!");
        }
        this.name = name;
        this.duration = duration;
        this.rating = rating;
    }
    public String getName() {
        return name;
    }
    public double getDuration() {
        return duration;
    }
    public double getRating() {
        return rating;
    }
}

Pascal Schärli - PVK Informatik II 2021

Objektorientierung

Prüfungsaufgabe

Herbst 2017, 1.17 Notenpunkte

public class Hike extends Activity {
    private double difficulty;

    public Hike(String name, double duration, double rating,
            double difficulty) {
        super(name, duration, rating);
        if(difficulty < 1 || difficulty > 5) {
            throw new IllegalArgumentException("The difficulty has to "
                        + "be between 1 and 5!");
        }
        this.difficulty = difficulty;
    }

    public double getDifficulty() {
        return difficulty;
    }
}

Pascal Schärli - PVK Informatik II 2021

Objektorientierung

Prüfungsaufgabe

Herbst 2017, 1.17 Notenpunkte

import java.util.ArrayList;

public class ActivityManager{
    ArrayList<Activity> activities;
    
    public ActivityManager() {
        activities = new ArrayList<Activity>();
    }
    
    public void addActivitiy(Activity activity){
        activities.add(activity);
    }
    
    public Hike findBestHike(double maxDuration, double maxDifference){
    	// [..]
    }
}

Pascal Schärli - PVK Informatik II 2021

Objektorientierung

Prüfungsaufgabe

Herbst 2017, 1.17 Notenpunkte

public Hike findBestHike(double maxDuration, double maxDifficulty){
    Hike bestHike = null;
    for (Activity activity : activities) {
      if (activity instanceof Hike) {
        Hike hike = (Hike) activity;
        if (hike.getDuration() <= maxDuration
            && hike.getDifficulty() <= maxDifficulty) {
          if (bestHike == null
              || hike.getRating() > bestHike.getRating()) {
            bestHike = hike;
          }
        }
      }
    }
    return bestHike;
}

Pascal Schärli - PVK Informatik II 2021

Objektorientierung

Prüfungsaufgabe

Herbst 2017, 1.17 Notenpunkte

public class Main{
    public static void main(String[] args){
        ActivityManager = new ActivityManager();
        // Adding activities
        // Assume the parameter order for the Activity constructor is
        // [name, duration, rating] and for the Hike constructor
        // [name, duration, rating, difficulty]
        manager.addActivitiy(new Activity("Spaziergang am See", 1.2, 2.5));
        manager.addActivitiy(new Hike("Brunni - Kl. Mythen", 2, 4.5, 4.5));
        manager.addActivitiy(new Activity("Velofahren Zuerich", 0.5, 1));
        manager.addActivitiy(new Hike("Brunni - Gr. Mythen", 3, 3.5, 3.5));
        manager.addActivitiy(new Activity("Schwimmen am Letten", 1, 4.5));
        manager.addActivitiy(new Activity("Nichtstun", 0, 2.5));
        manager.addActivitiy(new Hike("Weggis - Rigi Kulm", 5, 4, 3.5));
        manager.addActivitiy(new Hike("Alpnach - Pilatus Kulm", 5, 5, 2));

        double maxDuration = 4;
        double maxDifficulty = 3.5;
        Hike bestHike = manager.findBestHike(maxDuration, maxDifference);

        System.out.println("Die beste Wanderung: " + bestHike.getName());
    }
}

Die beste Wanderung: Brunni - Gr. Mythen

Pascal Schärli - PVK Informatik II 2021

Komplexität

Pascal Schärli - PVK Informatik II 2021

Komplexität

O-Notation

Die O-Notation beschreibt, die Grössenordnung von einem Problem.
Mathematische Definition:
- Sei $g(n)$ der Aufwand vom Algorithmus.
- Dann ist $g(n) \in O(f(n))$ falls
  $\exists n_0,c>0$ so dass $\forall n > n_0 : g(n) \leq c \cdot f(n) $
Die Funkion darf also für genug grosse Inputs nur um einen Konstanten Faktor von der Komplexität abweichen.
Im Endeffekt bedeutet das, dass wir nur den am schnellsten Wachsende Term betrachten müssen und alle konstanten Faktoren ignorieren können.

Pascal Schärli - PVK Informatik II 2021

Komplexität

O-Notation

Zeige, dass $\frac{n^2 + 100}{2} \in O(n^2)$:

$g(n) = \frac{n^2 + 100}{2}$, $f(n) = n^2$
Zu zeigen: $\exists n_0,c>0$ so dass $\forall n > n_0 : g(n) \leq c \cdot f(n) $
Wähle $c = 1$
Finde $n_0$
- $g(n) \leq c \cdot f(n)$
- $\Leftrightarrow \frac{n^2 + 100}{2} \leq n^2$
- $\Leftrightarrow 100 \leq n^2$
- $\Leftrightarrow n \geq 10$
- $\Rightarrow$ Wir können z.B $n_0 = 10$ wählen.
$\Rightarrow \forall n > 10 : \frac{n^2 + 100}{2}\leq 1 \cdot n^2$
$\Rightarrow \frac{n^2 + 100}{2} \in O(n^2)$

Pascal Schärli - PVK Informatik II 2021

Komplexität

O-Notation

Falls nicht nach Beweisen gefragt ist, müssen wir nicht all diese Rechnungen machen.
Dann reicht es nur den am Schnellsten wachsenden Summanden zu betrachten und alle Konstanten Multiplikatoren zu ignorieren.
Beispiele:
- $\frac{1 +n^2 + n^5}{5}$
  - $= \frac{1}{5} \cdot 1 + \frac{1}{5} \cdot n^2 + \frac{1}{5} \cdot n^5$
  - $\in O(n^5)$
- $log(n^4) + log(n^3)$
  - $= 7 \cdot log(n)$
  - $\in O(log(n))$

Pascal Schärli - PVK Informatik II 2021

Komplexität

O-Notation

Die O-Notation ist nur eine obere Schranke, das heisst falls ein Algorithmus $\in O(n)$ ist, so ist er auch $\in O(n^2)$.
Falls also $g(n) = \frac{n}{2}$ dann gilt sowohl $g(n) \in O(n)$ als auch $g(n) \in O(n^2)$
$O(1) \in O(log(n)) \in O(n) \in O(n \cdot log(n))$
$\in O(n^2) \in O(n^{100}) \in O(2^n) \in O(n!)$

Pascal Schärli - PVK Informatik II 2021

Komplexität

Laufzeitomplexität bestimmen

Zeile 5 Wird n-Mal Ausgeführt.

private static int f1(int n) {
  int out = 0;
  
  for(int i = 0; i < n; i++) {
    out++;
  }
  
  return out;
}

$O(n)$

Pascal Schärli - PVK Informatik II 2021

Komplexität

Laufzeitomplexität bestimmen

Zeile 5 Wird ca. $\lfloor \frac{n}{5} \rfloor $-Mal Ausgeführt.

$O(n)$

private static int f2(int n) {
  int out = 0;
  
  for(int i = 0; i * 5 < n; i++) {
    out++;
  }
  
  return out;
}

Pascal Schärli - PVK Informatik II 2021

Komplexität

Laufzeitomplexität bestimmen

Zeile 6 Wird $n^2$-Mal Ausgeführt.

$O(n^2)$

private static int f3(int n) {
  int out = 0;
  
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++){
      out++;	
    }
  }
  
  return out;
}

Pascal Schärli - PVK Informatik II 2021

Komplexität

Laufzeitomplexität bestimmen

Zeile 6 Wird $1000 * n$-Mal Ausgeführt.

$O(n)$

private static int f4(int n) {
  int out = 0;
  
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < 1000; j++){
      out++;	
    }
  }
  
  return out;
}

Pascal Schärli - PVK Informatik II 2021

Komplexität

Laufzeitomplexität bestimmen

Zeile 6 Wird $\sum_{i=0}^{n-1}(i) = \frac{n*(n-1)}{2}$-Mal Ausgeführt.

$O(n^2)$

private static int f5(int n) {
  int out = 0;
  
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < i; j++){
      out++;	
    }
  }
  
  return out;
}

Pascal Schärli - PVK Informatik II 2021

Komplexität

Laufzeitomplexität bestimmen

Zeile 4 macht, dass die inneren Loops $n^2$-Mal ausgeführt werden.
Zeile 5 macht, dass der Innere Loop $\sqrt{i} \approx n$-Mal ausgeführt wird. Da dieser Loop selbst $n^2$-Mal wiederholt wird, sind das $n^3$ Wiederholungen.
Zeile 6 macht, dass die Instruktion $j \cdot i \approx n^3$-Mal ausgeführt wird. Da dieser Loop selbst ca $n^3$-Mal ausgeführt wird, ist die gesamte Komplexität $O(n^6)$

$O(n^6)$

private static int f5(int n) {
  int out = 0;
  
  for(int i = 0; i < n*n; i++) {
    for(int j = 0; j*j < i; j++){
      for(int k = j*i; k > 0; k--){
        out++;
      }
    }
  }
  return out;
}

Pascal Schärli - PVK Informatik II 2021

Komplexität

Speicherkomplexität bestimmen

Neben der Laufzeit ist auch der benutzte Speicher einen Faktor, welchen man beim Entwickeln von einem Algorithmus im Auge behalten sollte.
Den benötigten Speicher kann man genauso wie die Laufzeit mit der O-Notation beschreiben

Pascal Schärli - PVK Informatik II 2021

Komplexität

Speicherkomplexität

public static int fibo(int n) {
    if (n <= 1) return 1;
    
    return fibo1(n - 1) + fibo1(n - 2);
}

Pascal Schärli - PVK Informatik II 2021

fibo(1) + fibo(0)

fibo(2) + fibo(1)

fibo(1) + fibo(0)

fibo(3) + fibo(2)

fibo(4)

Die Funktion ruft sich normalerweise ca. 2-mal rekursiv auf, der Resultierende Baum hat ungefähr Höhe $n$ und somit ca $2^n$ Knoten.

$\rightarrow$ Zeit: $O(2^n)$

Der Baum wird "Depth First" traversiert, also ein Ast nach dem anderen, somit ist zu jedem Zeitpunkt höchstens ein Pfad von Wurzel bis Blatt im Speicher.

$\rightarrow$ Speicher: $O(n)$

Speicher:

$O(n)$

Zeit:

$O(2^n)$

Komplexität

Speicherkomplexität

public static int fibo1(int n) {
    if (n <= 1) return 1;
    
    return fibo1(n - 1) + fibo1(n - 2);
}

public static int fibo2(int n) {
    if(n <= 1) return 1;
    
    int[] memory = new int[n + 1];
    memory[0] = 1;
    memory[1] = 1;
    for (int i = 2; i <= n; i++) {
        memory[i] = memory[i - 1] + memory[i - 2];
    }
    return memory[n];
}

public static int fibo3(int n) {
    int last1 = 1;
    int last2 = 1;
    for (int i = 2; i <= n; i++) {
        int temp = last1 + last2;
        last1 = last2;
        last2 = temp;
    }
    return last2;
}

Speicher:

$O(n)$

Zeit:

$O(2^n)$

Zeit:

$O(n)$

Speicher:

$O(n)$

Speicher:

$O(1)$

Zeit:

$O(n)$

Pascal Schärli - PVK Informatik II 2021

Komplexität

Neue Problemgrösse bei mehr Zeit

Wir haben ein Computer, welcher ein Problem mit $O(f(n))$ der Grösse M in der Zeit t lösen kann.
Was ist die lösbare Problemgrösse, falls wir k-Mal so viel Zeit zur Verfügung haben?
Beispiel:
- Der Computer kann ein $O(n^3)$ Problem kann in 10s einen Input der Grösse 1'000 verarbeiten
- Wie gross kann der Input sein, wenn man 20s zur Verfügung hat?

Pascal Schärli - PVK Informatik II 2021

Komplexität

Neue Problemgrösse bei mehr Zeit

Komplexität $O(n^3)$
Bisherige Inputgrösse 1'000
Mehr Zeit: $\times 2$

Der Computer macht ca $1000^3 = 10^9$ Operationen in 10s
In 20s Zeit kann er also $2 \cdot 10^9$ Operationen machen
Die neu bewältigbare Problemgrösse ist somit $\sqrt[3]{2 \cdot 10^9} \approx 1260 $

Pascal Schärli - PVK Informatik II 2021

Komplexität

Neue Problemgrösse bei mehr Zeit

Komplexität $O(f(n))$
Bisherige Inputgrösse $M$
Mehr Zeit: $\times k$

Der Computer macht ca $f(M)$ Operationen
Mit der zusätzlichen Zeit kann er also $k \cdot f(M)$ Operationen machen
Die neu bewältigbare Problemgrösse ist somit $f^{-1}(k \cdot f(M))$

Pascal Schärli - PVK Informatik II 2021

Herbst 2017, 0.67 Notenpunkte

Laufzeit und Speicherkomplexität

Prüfungsaufgabe

Pascal Schärli - PVK Informatik II 2021

Laufzeit und Speicherkomplexität

Prüfungsaufgabe

Herbst 2017, 0.67 Notenpunkte

public static int algorithm1(int[] input){
    assert input != null && input.length > 0;
    int maxSum = input[0];
    for(int i = 0; i < input.length; i++){
        for(int j = 0; j < input.length; j++){
            int sum = 0;
            for(int k = i; k <= j; k++){
                sum += input[k];
            }
            if(sum > maxSum){
                maxSum = sum;
            }
        }
    }
    return maxSum;
}

Zeit:
$O(input.length^3)$

Zusätzlicher Speicher:
$O(1)$

Pascal Schärli - PVK Informatik II 2021

Laufzeit und Speicherkomplexität

Prüfungsaufgabe

Herbst 2017, 0.67 Notenpunkte

public static int algorithm2(int[] input){
    assert input != null && input.length > 0;
    // calculate partial sums
    int[] p = new int[input.length];
    for(int i = 0; i < input.length; i++){
        if(i == 0) p[i] = input[i];
        else p[i] = p[i-1] + input[i];
    }
    // search for the maximum partial sum
    int maxSum = input[0];
    for(int i = 0; i < input.length; i++){
        for(int j = i; j < input.length; j++){
            int sum = (i == j) ? p[j] : p[j] - p[i];
            if(sum > maxSum){
                maxSum = sum;
            }
        }
    }
    return maxSum;
}

Zeit:
$O(input.length^2)$

Zusätzlicher Speicher:
$O(input.length)$

Pascal Schärli - PVK Informatik II 2021

Datenstrukturen

Pascal Schärli - PVK Informatik II 2021

Array

Datenstrukturen

Konzept

Speichert Liste von Elementen
Daten sind Physisch im Speicher nacheinander gespeichert

Vorteile

Konstante Zeit für Lesen/Schreiben
Platzsparend

Wichtigste Operationen

get - Element Lesen
- $O(1)$
set - Element Schreiben
- $O(1)$

Nachteile

Aufwendig Reihenfolge der Elemente zu verändern
Fixe Grösse

Pascal Schärli - PVK Informatik II 2021

Linked List

Datenstrukturen

Konzept

Speichert Liste von Elementen
Reihenfolge ist nicht durch Physischen Speicherort gegeben
Jedes Element hat einen Zeiger auf seinen Nachfolger

Vorteile

Flexible Grösse
Reihenfolge kann einfach verändert werden

Wichtigste Operationen

get - Element Lesen
- $O(n)$
set - Element Schreiben
- $O(n)$
insert - Element Einfügen
- $O(n)$

Nachteile

$O(n)$ für Lesen/Schreiben
Mehr Speicherplatz da jedes Element einen zusätzlichen Zeiger hat.

Pascal Schärli - PVK Informatik II 2021

Stack

Datenstrukturen

Konzept

Elemente werden oben auf einen Stapel gelegt und von oben wieder weg genommen
LIFO Last In First Out

Wichtigste Operationen

push - Element auf Stapel Legen
- $O(1)$ (mit Linked List)
pop - Element von Stapel entfernen
- $O(1)$ (mit Linked List)
peek - Oberstes Element anschauen
- $O(1)$ (mit Linked List)

Pascal Schärli - PVK Informatik II 2021

Queue

Datenstrukturen

Konzept

Elemente werden hinten in eine Warteschlange getan und vorne wieder rausgenommen.
FIFO First In First Out

Anwendungen

Bei geteilten Ressourcen, z.B. Zeitplanungen für CPU, Festplatte
Bei asynchronen Datenübertragung, also wenn bei einer Übertragung Daten nicht gleichzeitig bereitgestellt und verarbeitet werden.

Wichtigste Operationen

enqueue - Element hinten in die Warteschlange setzen
- $O(1)$ (mit Doubly Linked List)
dequeue - Element vorne von der Warteschlange entfernen
- $O(1)$ (mit Doubly Linked List)

Pascal Schärli - PVK Informatik II 2021

Graph

Datenstrukturen

Kanten

Knoten

Graph
Gerichteter Graph
Baum
Blätter
Binärbaum
Voller Baum
Vollständiger Baum
Entarteter Baum
Höhe
Pfad

Pascal Schärli - PVK Informatik II 2021

Graph

Datenstrukturen

Kanten haben eine Richtung

Graph
Gerichteter Graph
Baum
Blätter
Binärbaum
Voller Baum
Vollständiger Baum
Entarteter Baum
Höhe
Pfad

Pascal Schärli - PVK Informatik II 2021

Graph

Datenstrukturen

Zusammenhängender, Gerichteter Graph ohne Zyklen

Graph
Gerichteter Graph
Baum
Blätter
Binärbaum
Voller Baum
Vollständiger Baum
Entarteter Baum
Höhe
Pfad

Pascal Schärli - PVK Informatik II 2021

Graph
Gerichteter Graph
Baum
Blätter
Binärbaum
Voller Baum
Vollständiger Baum
Entarteter Baum
Höhe
Pfad

Knoten ohne Kindknoten

Datenstrukturen

Graph

Pascal Schärli - PVK Informatik II 2021

Graph
Gerichteter Graph
Baum
Blätter
Binärbaum
Voller Baum
Vollständiger Baum
Entarteter Baum
Höhe
Pfad

jeder Knoten besitzt höchstens zwei Kindknoten, die Reihenfolge der Kindknoten ist relevant.

Datenstrukturen

Graph

Pascal Schärli - PVK Informatik II 2021

Graph
Gerichteter Graph
Baum
Blätter
Binärbaum
Voller Baum
Vollständiger Baum
Entarteter Baum
Höhe
Pfad

jeder Knoten besitzt entweder zwei oder keine Kinder

Datenstrukturen

Graph

Pascal Schärli - PVK Informatik II 2021

Graph
Gerichteter Graph
Baum
Blätter
Binärbaum
Voller Baum
Vollständiger Baum
Entarteter Baum
Höhe
Pfad

Alle Blätter haben die selbe Tiefe

Datenstrukturen

Graph

Pascal Schärli - PVK Informatik II 2021

Graph
Gerichteter Graph
Baum
Blätter
Binärbaum
Voller Baum
Vollständiger Baum
Entarteter Baum
Höhe
Pfad

Ungleich verteilter Baum

Datenstrukturen

Graph

Pascal Schärli - PVK Informatik II 2021

Graph
Gerichteter Graph
Baum
Blätter
Binärbaum
Voller Baum
Vollständiger Baum
Entarteter Baum
Höhe
Pfad

Anzahl “Levels” ohne Wurzel
→ hier: 3

Datenstrukturen

Graph

Pascal Schärli - PVK Informatik II 2021

Graph
Gerichteter Graph
Baum
Blätter
Binärbaum
Voller Baum
Vollständiger Baum
Entarteter Baum
Höhe
Pfad

Weg durch Graph (Nur in Pfeilrichtung)

Datenstrukturen

Graph

Pascal Schärli - PVK Informatik II 2021

Datenstrukturen

Pre-Order Traversierung

12 5 3 1 9 10 19 14 20 22

Gib den Wert vom Knoten aus
Gib den linken Teilbaum in Pre-Order aus
Gib den rechten Teilbaum in Pre-Order aus

Pascal Schärli - PVK Informatik II 2021

Datenstrukturen

In-Order Traversierung

1 3 5 9 10 12 14 19 20 22

Gib den linken Teilbaum in In-Order aus
Gib den Wert vom Knoten aus
Gib den rechten Teilbaum in In-Order aus

Pascal Schärli - PVK Informatik II 2021

Datenstrukturen

Post-Order Traversierung

1 3 10 9 5 14 22 20 19 12

Gib den linken Teilbaum in Post-Order aus
Gib den rechten Teilbaum in Post-Order aus
Gib den Wert vom Knoten aus

Pascal Schärli - PVK Informatik II 2021

[   ,    ,    ,    ,    ,    ,   ]

Datenstrukturen

Binärbäume

Binärbäume kann man in einem Array abspeichern
Man muss ein Symbol für leere Knoten abmachen, z.B. ' '

Mit den folgenden Formeln kann man den Baum traversieren:

```
left child:  2*i+1
```
```
right child: 2*i+2
```
```
parent:  $⌊$ (i-1)/2 $⌋$ 
```

'H'

'B '

'J'

'A '

'E'

' '

'M'

Pascal Schärli - PVK Informatik II 2021

Indent = 1

Indent = 2

Indent = 3

Indent = 0

5
.8

5
.8
..3

5
.8
..3
..2

5
.8
..3
..2
...1

5
.8
..3
..2
...1
...9

5
.8
..3
..2
...1
...9
.7

5
.8
..3
..2
...1
...9
.7
..3

Pascal Schärli - PVK Informatik II 2021

Datenstrukturen

Binärbäume

5(                )

5(8(        )     )

5(8(3       )     )

5(8(3,2(   ))     )

5(8(3,2(1  ))     )

5(8(3,2(1,9))     )

5(8(3,2(1,9)),7( ))

5(8(3,2(1,9)),7(3))

Pascal Schärli - PVK Informatik II 2021

Datenstrukturen

Binärbäume

Pascal Schärli - PVK Informatik II 2021

Datenstrukturen

Binärbäume

Alle Elemente im linken Ast sind kleiner
Alle Elemente im rechten Ast sind grösser
$\rightarrow$ kleinstes Element ganz links
$\rightarrow$ grösstes Element ganz rechts

Binäre Suchbäume

Datenstrukturen

Pascal Schärli - PVK Informatik II 2021

Gesucht: 9

Datenstrukturen

Element Finden

Falls der Knoten das gesuchte Element ist:
$\rightarrow$ gefunden!
Falls der gesuchte Wert kleiner als der Knoten ist:
$\rightarrow$ Links weitersuchen
Falls der gesuchte Wert grösser als der Knoten ist:
$\rightarrow$ Rechts weitersuchen

Pascal Schärli - PVK Informatik II 2021