Info

  • Kontakt: blazeva1 (na) fit.cvut.cz
  • Konzultace: Po domluvě
  • Kde mě najdete: NB 341b
  • body za aktivitu dostanete za předvedení správného řešení úlohy, nebo domácího úkolu na tabuli

1. cvičení 7.10.2016

složitost ↗, model RAM ↗, graf ↗ (př: mapa ↗, kamarádi ↗), stupeň ↗, sousedi, princip sudosti ↗, regulární graf ↗, izomorfismus ↗ (hra ↗), automorfismus ↗

probraná témata

  • podmínky zápočtu
  • házení vajíček z paneláku (jedno, dvě, N)
  • kolik vypíše program hvězdiček?
  • formální zápis grafu G=({1,2,3},{{1,2},{2,3}})
  • vytvoření grafu se zadanými stupni, princip sudosti
  • automorfismus kliky a varianty
  • podmínky isomorfismu (#uzlů, #hran, stupně, sousedi, …)
  • dukaz izomorfismu grafů, pokud jsou jejich doplňky izomorfní

úlohy na doma

foo(q)
	for i := 1 to q do
		print(#)
foo2(N)
	for i := 1 to N do
		foo(i)
		j=1
		while j<=N do
			foo(j)
			j=j*2
  • Kolik se vypíše znaků # pro výše uvedený program, volání foo2?
  • Kolik hodů z paneláku o N patrech potřebuju, abych zjistil poslední patro K, ze kterého se vajíčko nerozbije, pokud mám jen tři vajíčka?
  • pro jaká N lze sestrojit graf, ve kterém mají pouze dva uzly stejný stupeň?
  • Zjistěte, které ze čtyř grafů (z tabule) jsou vzájemně izomorfní.
  • Zjistěte počet automorfismů pro kliku o šesti vrcholech, ze které jsme odebrali dvě hrany, které spolu nesousedí (tj. hrany bez společného uzlu), zkuste zobecnit na kliku s N vrcholy bez dvou hran.

2. cvičení 14.10.2016

cesta ↗, souvislost grafu ↗, orientovaný graf ↗, silná souvislost ↗, stromy ↗, kostry ↗

probraná témata

  • úkoly z minula (2x stejný stupeň, izomorfní grafy, Kn bez dvou hran)
  • jak na izomorfismus: stupně, vzdálenosti, cykly
  • slabá a silná souvislost, symetrizace, zdroj, stok, izolovaný vrchol
  • vstupní a výstupní stupeň vrcholu
  • indukovaný podgraf
  • existence cyklu v orient. grafu se vstupním i výstupním st. >= 1
  • dfs, chození králem, koněm po bludišti

úlohy na doma

  • existuje nesouvislý graf G, který má nesouvislý doplněk?
  • kolik existuje různých cest délky M mezi uzly x a y uvnitř kliky Kn
  • orientovaná cesta z 1 do 5, topologické uspořádání, vstupní & výstupní stupně, silně souvislé komponenty

graf (nejde moc vidět hrana co vede z 2->3 a 5->4):

1 -> 2
| _/ A
Vv   |
3 -> 4
| _-A|
V/   V
5 -> 6
  • určete všechny indukované podgrafy kliky K4
  • určete všechny (neizomorfní, tzn. prostě všechny) podgrafy kliky K4
  • jak se na následujícím bludišti dostane kulhavý kůň do cíle? (sestavte graf)

bludiště:

S....
..xx.
x.x..
.x..E

3. cvičení 21.10.2016

stromy, DFS, BFS, kostry, vzdálenost vrcholů

témata

  • úkoly z minula (orientovaný graf, cest délky M v Kn, neizomorfní podgrafy K4)
  • vlastnosti stromů

  • vnitřních uzlů pro zadaný počet listů a stupeň = (l-2)/(d-2)

  • zakořeněné stromy
  • kostry grafu a jejich počet
  • BFS a nejmenší vzdálenost vrcholů, # nejkratších cest

úlohy na doma

  • vypsat neizomorfní podgrafy K5 (vynechte podgrafy K4)
  • nejvyšší / nejnižší počet hran G s c komponentami
  • počet koster bipartitného úplného grafu K_{2,n}

(odpadá 28.10.2016)

kostry, topsort

úlohy na doma

  • vyberme hranu e z grafu G, existuje vždy kostra taková, že obsahuje hranu e?
  • jaká je (maximální) délka nejkratší cesty mezi libovolnými uzly u a v v grafu: K_n, K_{n,m}, C_n
  • zopakujte si topologické uspořádání a zkuste na tomto grafu (tentokrát to opravdu jde):

G, V(G)={1,2,…,12}, E(G)=

1->3,6,12
2->4,5,7,12
3->5,6
4->7,9,11,12
8->3
9->3,5
10->4,11
11->7
12->3,5,6,7,8
  • spočtěte, kolik různých top. uspořádání existuje ke grafu z minulé úlohy

4. cvičení 4.11.2016

opakování grafových algoritmů, topologické uspořádání

témata

  • úkoly z minule a odpadlé hodiny
  • běžci si pamatují některé, kteří doběhli před nimi, je možné rekonstuovat jednoznačné pořadí pouze z této informace?
  • hledání topologického uspořádání pomocí odřezávání listů
  • počet topologických uspořádání
  • hledání sqrt(n) nejmenších prvků v čase O(n)

úlohy na doma

  • jak rychle najít k-tý nejmenší prvek v neseřazeném poli
  • mějme rovnoramenné váhy, které umí rozhodnout která hromada kuliček je těžší
    • na kolik vážení zjistím, která z devíti kuliček je těžší?
    • na kolik vážení to lze pro 12 kuliček, a proč to nejde pouze na 2?
    • co když není jedna z kuliček těžší, ale má jinou váhu (je tedy buď těžší nebo lehčí)? Kolik vážení je potřeba pro 13 kuliček?

5. cvičení 11.11.2016

témata

  • vážení kuliček
  • amortizovaná analýza - nafukovací pole, increase bin. čísla
  • součet řady (1 + 1/2 + 1/4 + 1/8 + …)
  • binární haldy, heap sort
  • řazení téměř seřazené posloupnosti rychleji než n.log(n)
  • merge sort - sloučení seřazených posloupností
  • binomiální haldy - merge, insert, delete, decrease, get-min
  • principy vedoucí k make-heap v O(N)

úlohy na doma

  • jak zvážit jinou kuličku z 13 na 3 vážení (lze)
  • určete stabilitu bubble, insertion, selection, merge, quick a heap sortu, odůvodněte
  • jak zadódovat aritmetický výraz s závorkami,+,-,*,/ ve stromě, a jak ho derivovat?
  • když umocníme matici sousednosti A (v mat. je na A[a][b] 1 pokud vede hrana z a do b, 0 jinak) na K, co tato nová matice A^K vyjadřuje?

6. cvičení 18.11.2016

témata

  • pre,in,post-order průchody stromu
  • aritmetické výrazy ve stromě a jejich derivace
  • BVS, následník, složitost průchodu
  • AVL, rotace, vyvažování

úlohy na doma

  • zůstávání úlohy ze cvičení 5

7. cvičení 25.11.2016

témata

  • Insert AVL případ 3b (dvojtá rotace)
  • Delete v AVL
  • AVL s minimálním počtem vrcholů
  • úvod k pravděpodobnosti, generování náhodných čísel, střední hodnota

úlohy na doma

  • Ten co vyfotil ten kočičí graf vystaví fotku na fit-wiki.
  • Zjistěte jestli se pošle vyvažovací signál výše, a jaké příznaky budou v AVL po mazání z levého syna X, pokud on měl příznak (+) a jeho pravý syn (Y) měl příznak (-).
  • Jak z velikého souboru vybrat náhodně jednu řádku, pokud nevíme kolik má soubor řádek, soubor se nevejde do pracovní paměti, a každá řádka má mít stejnou pravděpodobost výběru?
  • Jak z velikého soboru vybrat K náhodných řádek, tak aby každá měla stejnou pravděpodobnost (opět nemůžeme soubor načíst celý a neznáme jeho délku)?

8. cvičení 2.12.2016

témata

  • dodělání pravděpodobnosti - vybrání náhodné K-tice ze souboru (jedním průchodem)
  • Rozptylování (hešování) a vyhledávací tabulky - hešování stringů a hledání kolizí, mazání náhrobkem a proč je potřeba
  • Rozděl a panuj - hanojské věže, rychlé násobení (Karatsuba)

úlohy na doma

  • Mějme dvojté hashování s hashovací funkcí: h(f,i)=k mod 11 + i * h2(f); kde h2 je: h2(f)=2+k mod 3; vložte do hashovací tabulky (s velikostí jedenáct) prvky 2,4,6,12,11,42 a 46
  • pro jakoku hodnotu u předchozí úlohy platí, že bude mít stejnou fci h i h2 jako číslo 13?

9. cvičení 9.12.2016

Rekurzivní algoritmy a metoda Rozděl a panuj.

témata

  • počítání inverzí pomocí úpravy merge sortu
  • řazení spojového seznamu
  • zjišťování špatných vstupů quick sortu pro danou volbu pivota
  • úloha s kabely v lokaci A a B, zjistit pomocí žárovky a krokodýlů co je s čim spojeno
  • jak zjistit unikátnost prvků v poli

10. cvičení 16.12.2016 (semestrální test)

11. cvičení 19.12.2016 (Pondělí)

témata

  • řazení - CountingSort, RadixSort, řazení řetězců, hledání prvku v uspořádaném 2D poli
  • dynamika - nesousedící kuličky v řadě, tiling dominem plochy 3xN, nejlepší cesta po stromě, řezání na podpalindromy

12. cvičení 6.1.2016

témata

  • dynamika - nejdelší cesta uvnitř stromu
  • nejkratší cesty - Dijkstra
  • minimální kostra - Jarnik-Prim, Karatsuba, jak se mění při změně jedné váhy, na grafu s nízkými vahami, Union-Find, hledání druhé nejmenší kostry