Programování II

Složitost algoritmu

Amortizace X průměr

Datové typy a struktury pro ukládání dat

Základní grafové algoritmy

//BFS
public static void bfs(Graph G, int startVert) {
       bool[] visited = new bool[G.Size];
       System.Collections.Generic.Queue<int> q = new System.Collections.Generic.Queue<int>();

       visited[startVert] = true;

       q.Enqueue(startVert);

       while(q.Count > 0){
                  int v = q.Dequeue();
           foreach(int adjV in G.adj[v]) {
               if (!visited[adjV]) {
                   visited[adjV] = true;
                   q.Enqueue(adjV);
               }
           }
       }
   }

//DFS
public static void dfs(Graph G, int startVert) {
       bool[] visited = new bool[G.Size];
       System.Collections.Generic.Stack<int> s = new System.Collections.Generic.Stack<int>();

       visited[startVert] = true;

       s.Push(startVert);

       while(s.Count > 0) {
           int v = s.Pop();
           foreach(int adjV in G.adj[v]) {
               if (!visited[adjV]) {
                   visited[adjV] = true;
                   s.Push(adjV);
               }
          }
       }
   }

Atributy

Třídy

Metody

// Virtual method
public class Animal {
    public virtual void MakeSound() {
        Console.WriteLine("I am an animal.");
    }
}
public class Cat : Animal {
    public override void MakeSound() {
        Console.WriteLine("Meow!");
    }
}
public class Fish : Animal {
    public static void MakeSound()  {
        Console.WriteLine("Blob!");
    }
}
public static void Main() {
    Animal cat = new Cat();
    Animal fish = new Fish();
    cat.MakeSound();    // Meow!
    fish.MakeSound();   // I am an animal.
}
// Abstract method and class
public abstract class Sound {
    public abstract string MakeSound();
}

public class Animal : Sound {
    public override string MakeSound() {
        return "I am an animal.";
    }

    public static void Main() {
        var animal = new Animal();
        Console.WriteLine("Animal sound: " + animal.MakeSound());   // Animal sound: I am an animal.
    }
}

Návrhové vzory

Třídění

Důkaz dolního odhadu třídících algoritmů

Třídící algoritmy:

Algoritmus Složitost Animace
Bubble sort \(O(n^2)\)
Insertion sort (vkládáním) \(O(n^2)\)
Selection sort \(O(n^2)\)
Heap Sort \(O(n \log n)\)
Merge sort \(O(n \log n)\)
Quick sort \(O(n \log n)\) → \(O(n^2)\)
Counting sort \(O(n*k), k = max číslo\)

Hledání nejkratších cest

\(m = |E|, n = |V|\)

Hledání minimálních koster

Stromové datové struktury a algoritmy na nich

Insert Delete Find

Dynamické programování

Řešení úlohy se skládá z řešení menších podúloh, která jsme si vypočetli a zapamatovali. Zkoušíme všechny možnosti rozdělení a vybíráme to nejlepší. Pěkný abstraktní pohled, že mám systém podproblémů (tzv. stavy DP) a ty mezi sebou mají nějaké závislosti, které tvoří DAG Princip DP je projít stavy v topologickém pořadí.

Zobecnění principů dynamického programování:

  1. Začneme s exponenciálním algoritmem
  2. Všimneme si, že často počítáme to samé
  3. Zavedeme si proto paměť na známé výsledky
  4. Rekurzi nahradíme vyplňování keše ve správném pořadí

Techniky:

Příklady

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

array m[0..n, 0..W]
for j from 0 to W do:
    m[0, j] := 0
for i from 1 to n do:
    m[i, 0] := 0

for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

Diskrétní simulace

Využívá se ke zkoumání a analýze chování složitých systémů - jsou závislé na čase, instrukcích apod. Umožňují testování různých scénářů za různých podmínek… používá se převážně v dopravě, logistice atd. Čas je modelován jako posloupnost událostí. Provádí se v krocích, kde každý krok reprezentuje nějaký okamžik, ve kterém se odehrávají dané události. V každém kroku jsou vyhodnoceny všechny události ve frontě.

Složky diskrétní simulace

Stavy procesů

Programování řízené událostmi - hlavní část programu reaguje na události (uživatelské vstupy, data). Jaké akce by měly být vyvolány jako reakce na tyto události.

Příklad z hodiny - Obchodní dům: Jeden stav/ událost = příchod zákazníka, čas strávený v obchodě, čas ve výtahu apod.

Objektivně orientované programování

Dekompozice

Generické programování - C

Hashovací tabulky

K tvorbě dokumentu přispěl Matěj Foukal