obvodová úložka
spočítání semestrální písemky
pokračování dynamickým programováním; úlohy na nejdelší rostoucí podposloupnost s jedním poklesem a v čase NlogN; úloha s rovnáním knih do knihovny
nalezení minimální kostry v grafu s ohodnocením hran z {1,2,3,4,5}
stužková úložka
ukázán 1] a 2] domácí úkol z 9. cvičení
radix sort; řazení N čísel z rozsahu [0, N3] v lineárním čase; řazení řetězců v čase O(součet délek řetězce);
nalezení nejdelšího úseku v posloupnosti, ve kterém se neopakuje žádne číslo
úvod do dynamického programování - přístup top-down
dán graf na vrcholech 1,2,...,N a z každého vrcholu vedou nejvýše dvě hrany do vrcholu z vyšším číslem => počet cest z 1 do N, délka nejdelší cesty při ohodnocených hranách z 1 do N
dláždění mřížky 2xN dlaždičkami 2x1 a 1x2
1] (0.5b) máme 4 přihrádky a 3 míčky, míčky házím do přihrádek, jaká je pravděpodobnost, že se alespoň 2 trefí do první přihrádky?
2] (0.5b) navrhněte graf (nebo algoritmus, který takový graf sestrojí), ve kterém mezi některými dvěma vrcholy vede Fk cest, kde Fk je k-té Fibonacciho číslo
ponožková úložka
ukázán domácí úkol hledání inverzí z 8.cvičení
Hanojske věže s pravidlem navíc, že nelze přesunout přímo disk z věže A na věž B
úloha s kabely o rozpoznávání jejich propojení
diskuze nad volbami pivota pro QuickSelect; konstrukce posloupností vynucující si kvadratické chování
analýza pravděpodbnosti výběru skoromediánu, když volím 3 prvky náhodně a vyberu medián z těch tří
načnut domácí úkol s maticí
1] (1.5b) úloha s nekonečným streamem, ale pro obecnou K-tici řádků (k dispozici je O(K) paměti)
2] (1.0b) zadána matice A velikosti NxM, kde řádky i sloupce jsou seřazeny vzestupně, jak v lineárním čase najít prvek Ai,j=k ?
3] (0.5b) máme 4 přihrádky a 3 míčky, míčky házím do přihrádek, jaká je pravděpodobnost, že se alespoň 2 trefí do první přihrádky?
trezorová úložka
rozdělování N kuliček do 3 přihrádek s pomocí operace "patří do přihrádky"; ukázka randomizovaného přístup řešící úlohu s 5N/3 operacemi ve střední hodnotě
mám nekonečný (nevím jak dlouhý) stream řádků, ale pamět mám na uložení pouze O(1) řádků, jak vybrat 1 řádek náhodně tak, aby každý z řádků měl stejnou pravděpodobnost výběru = pokud jsem právě přečetl N řádků, tak každý má pst 1/N, že ho mám zrovna vybraný
důkaz tvrzení, že když mám nesoudělná N,M a postupně beru všechny násobky i*N mod M pro i={0,1,...,M-1}, tak potom musím proskákat všechny hodnoty {0,1,...,M-1}
hashování; diskutováno hashování s řetízky; diskutováno hashování s otevřenou adresací + řešené příklady vkládání a odebíraní
hashování řetězců, ukázka vlastností polynomiálního hashe (rolling hash)
jak efektivně setřídit spojový seznam
načnuto efektivní výpočet počtu inverzí v poli
1] (1.5b) úloha s nekonečným streamem, ale pro obecnou K-tici řádků (k dispozici je O(K) paměti)
2] (1.5b) jak efektivně spočítat počet inverzí v poli
koňská úložka
binomiální haldy; merge, extract min, insert, decrease key, delete, increase key => vše O(log n)
pravděpodobnost; základní pojmy = prostor elementárních jevů, náhodná veličina, střední hodnota = ukázáno na úloze hodu 10 šestistěnnými kostkami
generování uniformně náhodných čísel z rozsahu [0, N-1] pomocí funkce randombit(); oba případy když N je mocnina dvojky a když není
analýza algoritmu Knuth shuffle
úloha s N přihrádkami a strefováním se do nich s tím, že pokus opakuji, pokud se trefím již do plné přihrádky; analýza střední hodnoty počtu pokusů; vyjde to NlogN
1] (1b) ukázat, že harmonická řada do N prvků se dá odhadnout shora logaritmem z N
faktoriál škrtací úložka
ukázán domácí úkol z 5.cvičení
amortizovaná analýza; binární sčítačka přímou metodou, simulace fronty pomocí dvou zásobníků; průchod stromem voláním operace následník
BVS; hledání následníka; pre/post/in order průchod
postavení vyváženého BVS ze seřazeného pole; vyvážení BVS v lineárním čase; sloučení dvou BVS v linearním čase
AVL; simulace insertů a deletů
králičí úložka
ukázán domácí úkol z 4.cvičení
dolní odhad hledání nejmenšího prvku v neseřazeném poli N prvků => nejméně N-1 porovnání
rychlé hledání k-tého nejmenšího prvku v neseřazeném poli N prvků
hledání sqrt(N) nejmenších prvků v neseřazeném poli N prvků v O(N)
binární haldy; operace insert, extract min, change key
rychlé slévání K setříděných posloupností
HeapSort + vlastnosti řadících algoritmů: datová citlivost, stabilita, in-place
rychlé seřazení posloupnosti, kde je každý prvek od své pozice vzdálen nejvýše K pozic
amortizovaná složitost; penízková metoda; přímá metoda
1] (1b) slevání K seřazených posloupností délky N v čase O(N*K*log(K)) bez použití haldy
sklenicová úložka
ukázány domácí úkoly z 2. cvičení
nechť T je neorientovaný strom, v němž je maximalní stupeň vrcholu k (zapíšeme jako Δ(T)=k); důkaz, že strom T má alespoň Δ(T) listů (vrcholů stupně 1)
důkaz, že postupným napojováním listů na strom lze sestrojit libovolný strom (indukce přes odtržení vrcholu)
důkaz, že pro každý souvislý graf G na alespoň 3 vrcholech existují dva různé vrcholy u,v takové, že odtržením libovolného z nich nebo i obou dostaneme opět souvislý graf
interpretace mocnin matice sousednosti Ak
prohledávání stavového prostoru a BFS
zapomnětlivý běžci a topsort
1] (1.5b) je zadán strom T, nalezněte algoritmus pro nalezení nejdelší cesty v tomto stromě a dokažte jeho správnost
faktoriálová úložka
podgraf, indukovaný podgraf; důkaz, že graf, který obsahuje kružnici liché délky jako podgraf, obsahuje také kružnici liché délky jako indukovaný podgraf
důkaz, že neexistuje nesouvislý graf jehož doplněk je také nesouvislý
počitání cest různých délek v grafech Kn, Kn,m
určení počtu všech indukovaných podgrafů Kn (nejdříve když nepočítáme vzájemně izomorfní grafy jako různé, poté když je počítáme); určení počtu všech různých podgrafů Kn (pouze když počítáme vzájemně izomorfní grafy jako různé)
důkaz, že graf o 2n vrcholech, kde každý vrchol je spojen s právě n dalšími různými vrcholy, je souvislý
důkaz, že orientovaný graf, jehož každý vrchol má vstupní i výstupní stupeň alespoň jedna, musí obsahovat cyklus
souvislost a komponenta souvislosti
1] plyne z tvrzení o existenci cyklu v orientovaném graf, jehož každý vrchol má vstupní i výstupní stupeň alespoň jedna, že každý vrchol v tomto grafu je součástí nějakého cyklu?
2] jak vypadá graf na n vrcholech, který má právě c souvislých komponent a má maximální možný počet hran, ze všech takových možných? dokažte, že tento graf nemůže vypadat jinak
vajíčková úložka
počítání hvězdiček
úvod do teorie grafů: definice a pojmy; příklady na existenci grafů dle daných podmínek (počty vrcholů, hran, stupně vrcholů); princip sudosti, ukázka, že graf ho může splňovat, ale přitom nemusí existovat; grafy se všemi stupni vrcholů různými (nebo s povolením dvou stejných).
definice izomorfismu, motivace pro jeho zavedení: ukázka, že izomorfismus je ekvivalence a tedy se k grafům ze stejné ekvivalenční třídy můžeme chovat jako ke stejným (smazání labelů u vrcholů); co to znamená dokázat, že dva grafy jsou či nejsou izomorfní; příklady na poznání izomorfismu grafů: nutné podmínky pro izomorfismus (stejný počet vrcholů, hran, ...).
důkaz věty: G ~ H <=> G' ~ H' ; příklad použití u ukázky izomorfismu (n-2)-regulárních grafů.
automorfismus a počítání automorfismů různých grafů: Kn, Kn bez hrany,...
pořádný formální důkaz věty: G ~ H <=> G' ~ H'
1] dokažte následující tvrzení: pro každé N>0 lze sestrojit graf o N vrcholech, který má všechny stupně vrcholů různé až na dva, které mohou být stejné (tedy např. pro N=5 povolujeme stupně: 0 1 1 2 3, ale ne 0 1 1 1 2)
2] najděte graf s N>1 vrcholy a s právě jedním automorfismem