Cvičení 09

# Programování II pro matematiky

## Teoretické cvičení 09

**28 4. 2021**

Martin Mareš a Tomáš Karella

---

## Plán cvičení

- Opakování
- Příklady
- Řešení příkladů

---

### Opakování - graf

- Matice sousednosti
  - Je vhodná pro malé grafy s velkým množstvím hran

---

### Opakování - graf

- Seznam následníků

---

### Opakování - graf

- Seznam hran

---

### Opakování - graf

- Matice incidence
  - (vhodné pro grafy, které mají více hran než vrcholů)

---

### Opakování - BFS vs DFS

---

### Opakování - strom

Chceme zjistit, zda je zadaný binární strom symetrický podle svislé osy procházející kořenem (jde nám pouze o tvar stromu, nikoliv o hodnoty uložené v jeho uzlech).

**Algoritmus:**

```python
def je_stejny(levy, pravy):
    if levy is None and pravy is None:
        return True
    else:
        if je_stejny(levy.levy, pravy.pravy) and 
           je_stejny(levy.pravy, pravy.levy):
        	return True
        else:
            return False
        
return je_stejny(koren.levy, koren.pravy)
```

Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$

---

### Příklady (1)

Najděte algoritmus a určete jeho časovou a prostorovou složitost v nejhorším případě.

**Na vstupu máme odkaz na kořen binárního stromu:**

1. Na vstupu máme binární vyhledávací strom obsahující čísla. Na vstupu dostaneme číslo (číslo nemusí být v BST) a chceme vrátit největší menší prvek v daném BST.

*Příklad:* 
   Strom obsahuje `1, 2, 4, 6`, pro vstup `4`  vrátíme `2` ; pro vstup `5` vrátíme `4`.

2. Chceme pro každý vrchol binárního (vyhledávacího) stromu určit jeho balance (balance podle definice z AVL stromu).

**Rekurze:**

1. Nalezněte všechny různé rozklady čísla $N$, které jsou tvořený přesně $K$ celočíselnými sčítanci.

---

### Příklady (2)

Zapište následující graf pomocí všech reprezentací:

Určete pro všechny reprezentace prostorovou složitost pro uložení $N$ vrcholů a $M$ hran. Určete časovou složitost pro následující operace:

- Je mezi `x` a `y` hrana?
- Vypsání všech následovníků vrcholu `x`.
- Přidání hrany nebo vrcholu do grafu.

---

### Bonus

![Věže](https://upload.wikimedia.org/wikipedia/commons/0/07/Tower_of_Hanoi.jpeg)

Vypráví se legenda, že někde ve Vietnamu nebo Indii stojí klášter nebo chrám, v němž jsou hanojské věže se 64 zlatými kotouči. Mniši (kněží) každý den v poledne za zvuku zvonů slavnostně přemístí jeden kotouč (v jiných verzích probíhá přemisťování nepřetržitě). V okamžiku, kdy bude přemístěn poslední kotouč, nastane konec světa.

---

### Řešení (1)

Na vstupu máme binární vyhledávací strom obsahující čísla. Na vstupu dostaneme číslo (číslo nemusí být v BST) a chceme vrátit největší menší prvek v daném BST.

---

```python
def fnd_lt(strom: BST, x):
    if strom is None:
        return None
    else:
        if strom.info == x:
        	return find_max(strom.levy)
        elif x < strom.info:
            return find_lt(strom.levy, x)
        else: # strom.info < x:
            found = find_lt(strom.pravy, x)
            if found:
                return found;
            else:
				return strom.info
  
def find_max(strom: BST):
    if strom is None:
    	return None
    
    found = find_max(strom.pravy)
    if found:
        return found
    else:
    	return strom.info
```

Časová složitost  $\mathcal{O}(\text{hloubka stromu})$, paměťová složitost $\mathcal{O}(\text{hloubka stromu})$

---

### Řešení (2)

Chceme pro každý vrchol binárního (vyhledávacího) stromu určit jeho balance (balance podle definice z AVL stromu).

**Algoritmus:**

```python
def set_balance(strom: BST, x) -> int: # vrací hloubku stromu
    if strom is None:
        return 0
    else:
        h_levy = set_balance(strom.levy)
        h_prvy = set_balance(strom.pravy)
        strom.balance = h_levy - h_pravy
        
     	if abs(strom.balance) > 1:
            print("BST strom nesplňuje invarianty pro AVL strom")
        
return max(h_levy, h_pravy)
```

Časová složitost  $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$

---

### Řešení (3)

Nalezněte všechny různé rozklady čísla $N$, které jsou tvořený přesně $K$ celočíselnými sčítanci.

8 = (1 + 1 + 1 + 1) + (1 + 1) + (1 + 1)

**Algoritmus:**

```python
def _rozklad(N, K, index, c):
    """
    N - kolik zbývá rozložit
    index - kolikátý sčítanec vytváříme
    """
    if N == 0:          # rozklad je hotov
        print(pole[1:index])
    else:       # přidáme do pole[index] index-tý člen rozkladu
        for i in range(1, min(N, pole[index-1], N-(K-index)) + 1):
            pole[index] = i
            rozklad(N-i, K, index+1, pole)
            
def rozklad(N, K):
    _rozklad(N, K, 1, [N] * (K+1))
```

Časová složitost  $\mathcal{O}({N - 1 \choose K-1} / K!)$, paměťová složitost $\mathcal{O}(K)$

---

### Řešení - bonus

Vyřešení tohoto hlavolamu pro $64$ kotoučů však vyžaduje $2^{64}−1=18 446 744 073 709 551 615$ tahů, takže i kdyby mniši stihli provést jeden tah každou sekundu (a postupovali nejkratším možným způsobem), trvalo by jim vyřešení celého hlavolamu přibližně $600$ miliard let.

```pascal
procedure Hanoj(n: integer; pocatecni, cilova, odkladaci: char);
begin
    if n>1 then Hanoj(n-1, pocatecni, odkladaci, cilova);
    writeln('Přesuneme kotouč z věže ', pocatecni, ' na věž ', cilova);
    if n>1 then Hanoj(n-1, odkladaci, cilova, pocatecni)
end;
```

![Animace](https://upload.wikimedia.org/wikipedia/commons/6/60/Tower_of_Hanoi_4.gif)