Úlohy- 2.cvičení 1. Převeďte dané číslo do dvojkové, osmičkové a šestnáctkové soustavy: a) 75910 b) 257810 2. Převeďte dané desetinné číslo do dvojkové soustavy (DEC -> BIN): a) 0,812510 b) 0,3510 c) 0,̅̅̅̅10 3. Převeďte dané číslo z dané soustavy do tří zbývajících: a) 11 0101 11102 b) 30578 c) D9C16
Výsledky 1. a) 75910 = 10 1111 01112 = 13678 = 2F716 b) 257810 = 1010 0001 00102 = 50228 = A1216 2. a) 0,812510 = 0,11012 b) 0,3510 = 0,01 ̅̅̅̅̅̅̅ 2 3. a) 11 0101 11102 = 86210 ( = 15368 = 35E16 ) b) 30578 = 158310 ( = 62F16 = 110 0010 11112 ) c) D9C16 = 348410 ( = 66348 = 1101 1001 11002 )
4EK112
Úlohy- 3.cvičení 1. Převeďte zadané číslo do binárního tvaru: 15,3510 2. Zadaný polynom uzávorkujte podle Hornerova schématu: 3x5 + 2x4 + 4x3 + x2 + 5x + 1 Vypočítejte kolik operací násobení je zapotřebí k vypočtení hodnoty tohoto polynomu v zadaném bodě: a) před uzávorkováním b) po uzávorkování c) Kolik operací násobení bychom pořebovali k vypočtení hodnoty polynomu desátého stupně přímým dosazením? d) Kolik operací násobení bychom pořebovali k vypočtení hodnoty polynomu desátého stupně pomocí Hornerova schématu? 3. Odvoďte výpočetní složitost algoritmu „Třídění přímým výběrem“ a) popište princip algoritmu b) zapište algoritmus pomocí metakódu c) spočítejte výpočetní složitost f(n) měřenou počtem porovnání d) najděte konstantu c a funkci g(n) takové, že f(n) <= c. g(n), tj. f(n) = O(g(n))
4EK112
Výsledky – 3.cvičení 1. 15,3510 = 1510 + 0,3510 = 1111,01 ̅̅̅̅̅̅̅2 2. ((((3x + 2)x + 4)x + 1)x + 5)x + 1 a) 15 násobení před uzávorkováním, 5 + 4 + 3 + 2 + 1 = 15 b) 5 násobení po uzávorkování c) 55 násobení přímým dosazením, n = 10, (n2+n)/2=(100+10)/2 = 55 d) 10 násobení pomocí Hornerova schématu 3. a) Postupně se prochází posloupnost (pole) a hodnoty a(j) pro j>1 se porovnávají s a(1). Pokud je a(j)
4EK112
Úlohy- 4.cvičení 1. Napište algoritmus pro přidání informace x do zásobníku (LIFO) implementovaného jako pole. (n ... počet obsazených prvků, Nmax ... maximální možný počet prvků) 2. Napište algoritmus pro vyzvednutí informace z vrcholu zásobníku (LIFO) implementovaného jako pole. Informaci uložte do proměnné x. 3. Napište algoritmus pro přidání informace „Nová data“ na konec fronty (FIFO) implementované jako spojový seznam. (zac, kon) 4. Napište algoritmus pro vyzvednutí informace ze začátku fronty implementované jako spojový seznam (FIFO). Informaci uložte do proměnné x. Uvolněte paměť pro další použití. }, A = { }, B = { } 5. R = { Uložte do binární tabulky množiny A a B, jež jsou podmnožinou množiny R. Pomocí binární tabulky stanovte jejich a) průnik b) sjednocení
4EK112
Řešení – 4.cvičení 1. Přidání informace x do (n+1)-ní složky zásobníku: Jestliže n = Nmax, pak tisk „nelze přidat, plný zásobník“, konec n := n+1 a[ ] := x 2. Vyzvednutí informace z vrcholu zásobníku a její uložení do proměnné x: Jestliže n = 0, pak tisk „nelze vybrat, prázdný zásobník“, konec x := a[ ] n := n-1 3. Přidání informace „Nová data“ na konec fronty: new(p) p^.info := “Nová data” p^.dalsi := nil kon^.dalsi := p kon := p 4. Vyzvednutí informace ze začátku fronty a její uložení do proměnné x: Jestliže zac = nil, pak tiskni “prázdný seznam”, konec x := zac^.info p := zac^.dalsi dispose (zac) zac := p 5.
R 0 A 1 B 1 A B 1 A B 1
4EK112
1 1 0 0 1
2 0 1 0 1
3 1 0 0 1
4 0 0 0 0
5 0 1 0 1
6 1 0 0 1
7 1 1 1 1
8 0 0 0 0
9 1 0 0 1
10 0 1 0 1
Úlohy- 5.cvičení 1
4
2
5
3
6
1. Stanovte incidenční matici grafu. Hrany očíslujte zleva doprava a to nejprve hrany vycházející z uzlu 1, pak z uzlu 2, nakonec z uzlu 3. 2. Stanovte matici sousednosti grafu. 3. Kolik prvků bude mít pole, použijeme-li pro reprezentaci grafu v počítači pomocí pole matici sousednosti? a) Uložíme-li do pole všechny prvky matice sousednosti. b) Využijeme-li toho, že matice sousednosti je symetrická a na hlavní diagonále má samé nuly. 4. Najděte co nejvíc cyklů, které začínají a končí v uzlu 1. 5. Určete číslo nezávislosti α a uveďte alespoň jednu nezávislou komponentu, jejíž počet uzlů je roven α. 6. Nalezněte v grafu artikulaci nebo 2-artikulaci (takové dva uzly, po jejichž odstranění se graf rozpadne na dvě nebo více nesouvislých částí). 7. Nakreslete nový graf o 5 uzlech s 2-artikulací. Vyznačte ji.
4EK112
Řešení – 5.cvičení 1. Incidenční matice 1 2 3 4 5 6
H1 1 0 0 1 0 0
H2 1 0 0 1 0 0
H3 1 0 0 1 0 0
H4 0 1 0 0 1 0
H5 0 1 0 0 1 0
H6 0 1 0 0 1 0
3 0 0 0 1 1 1
4 1 1 1 0 0 0
5 1 1 1 0 0 0
6 1 1 1 0 0 0
H7 0 0 1 0 0 1
H8 0 0 1 0 0 1
2. Matice sousednosti 1 2 3 4 5 6
1 0 0 0 1 1 1
2 0 0 0 1 1 1
3. (obecně: n2) (obecně: (n2 - n)/2
a) Počet prvků pole: 6 x 6 = 36 b) Počet prvků pole: (36 – 6)/2 = 15 4. Cykly z uzlu 1: {1,6,3,4,1}, {1,4,3,6,1},
{1,5,2,4,1}, {1,4,2,5,1},
{1,5,3,6,1}, {1,6,3,5,1},
5. Číslo nezávislosti α = 3 nezávislá komponenta např.: {1, 2, 3} 6. Artikulace ani 2-artikulace neexistuje.
4EK112
{1,6,2,4,1}, {1,4,2,6,1}
H9 0 0 1 0 0 1
Teorie - 6. Cvičení
Prohledávání binárního kořenového stromu do hloubky pomocí zásobníku Krok 1. Vlož adresu kořene do zásobníku Krok 2. Opakuj následující operace, dokud není zásobník prázdný.
Vyzvedni ze zásobníku adresu U daného uzlu v. Zpracuj informaci na adrese U. Má-li uzel v pravého následníka, vlož ho do zásobníku. Má-li uzel levého následníka, vlož ho do zásobníku.
Prohledávání binárního kořenového stromu do šířky pomocí fronty Krok 1. Vlož adresu kořene do fronty Krok 2. Opakuj následující operace, dokud není fronta prázdná.
4EK112
Vyzvedni adresu U daného uzlu v ze začátku fronty. Zpracuj informaci na adrese U. Má-li uzel v levého následníka, vlož ho na konec fronty. Má-li uzel pravého následníka, vlož ho na konec fronty.
Úlohy- 6.cvičení 1. Nakreslete strom o alespoň 7 uzlech, který je AVL vyvážený, ale není dokonale vyvážený. 2. Uvedený strom prohledejte do hloubky a vytiskněte obsahy uzlů užitím operace inorder. Uveďte algoritmus rekurzivní procedury s uvedenou operací. U C
B A
X
H
G
3. Uvedený strom prohledejte do hloubky a vytiskněte obsahy uzlů užitím operace postorder. Uveďte algoritmus rekurzivní procedury s uvedenou operací. M B
L
R
U
J
K
4. Vyjádřete následující výrazy v prefixové a postfixové notaci. a) ((u+t)*((x+y)*z))/(w-s) b) (u*((x+y)*z))/(s-(w+t)) c) a/(b-(c*(x/(y+z)))) 5. Sestrojte binární kořenový strom, při jehož prohledávání do hloubky jsou v zásobníku (vrchol je vlevo) postupně hodnoty (7), (11, 3), (4, 5, 3), (5, 3) (3), (9, 12), (2, 16, 12), (16, 12), (12)
4EK112
Řešení- 6.cvičení
1. Strom o alespoň 7 uzlech, je AVL vyvážený, není dokonale vyvážený. 2. Tisk užitím operace inorder:
BAUGHCX
Hledej_2(U) jestliže U <> nil, pak Hledej_2(U^.levy) tisk(U^.info) Hledej_2(U^.pravy) 3. Tisk užitím operace postorder:
KRBUJLM
Hledej_3(U) jestliže U <> nil, pak Hledej_3(U^.levy) Hledej_3(U^.pravy) tisk(U^.info)
4. Vyjádřete následující výrazy v prefixové a postfixové notaci. a) prefixová notace: / * + u t * + x y z – w s postfixová notace: u t + x y + z * * w s – / b) prefixová notace: / * u * + x y z – s + w t postfixová notace: u x y + z * * s w t + – / c) prefixová notace: / a – b * c / x + y z postfixová notace: a b c x y z + / * – /
4EK112
Úlohy- 7.cvičení 1. Sestrojte binární kořenový strom, při jehož prohledávání do šířky jsou ve frontě (vkládá se vpravo) postupně hodnoty (5), (3, 9), (9, 4, 1), (4, 1, 2) (1, 2), (2, 7, 6), (7, 6), (6), (8) 2. Sestrojte Huffmanův strom pro zprávu danou následující tabulkou. Dále stanovte Huffmanovy kódy jednotlivých znaků a celkový počet L potřebných bitů.
znak A četnost 5
B 2
C 3
D 2
E 4
F 7
G 9
H 10
I 1
3. K haldě umístěné v daném poli a) přidejte prvek s klíčem 2 a přebudujte haldu b) zrušte kořen a přebudujte haldu
3
5
6
12
8
19
13
17
14
16
10
20
P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9) P(10) P(11) P(12) P(13)
4. Ve vyhledávacím stromu a) nalezněte hodnoty klíčů 4, 10 b) postupně zrušte uzly s klíči 5, 6 c) nakonec přidejte uzly s klíči 3, 12
6 8 L
2 5
1
4
4EK112
7
9
13
Řešení- 7.cvičení
Huffmanův kód (není určen jednoznačně)
znak četnost kód délka
A 5 101 3
B 2 1000 4
C 3 1100 4
D 2 10011 5
E 4 1101 4
F 7 111 3
G 9 00 2
H 10 01 2
L = 5*3 + 2*4 + 3*4 + 2*5 + 4*4 + 7*3 + 9*2 + 10*2 + 1*5 = 105 bitů
4EK112
I 1 10010 5
