zapomněla se 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?
ponožková úložka
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ý
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)
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
faktoriál škrtací úložka
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
1] (1b) vyrobit frontu pomocí 2 zásobníků, aby insert a pop byli amortizovaně konstantní
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; vyvrácení tvrzení, že v takovém grafu musí každý vrchol být součástí nějakého cyklu (protipříkladem)
souvislost a komponenta souvislosti
ukázka grafu 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; důkaz, že nemůže vypadat jinak
1] (1.0b) jsou dány tři nádoby o kapacitách c1, c2, c3 litrů - jak pomocí přelevání vody mezi nádobami odměřit K litrů?
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).
formální důkaz 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é
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, ...).
formální 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,...
1] najděte graf s N>1 vrcholy a s právě jedním automorfismem